Lab: Memory Allocation

Today’s lab will help you practice using dynamically allocated memory in C. The reading and our discussion focused on two main functions: malloc and free. Later exercises will look at another function that’s useful for allocating memory: realloc.

To get started, create a fork of the starter code repository at https://git.cs.grinnell.edu/csc161/malloc. Make sure you add your lab group members as collaborators on the repository, and then clone and open the repository:

$ cd csc161/labs
$ git clone https://git.cs.grinnell.edu/YOUR_USERNAME/malloc
$ cd malloc
$ code .

A. Allocating Memory for Single Values

The exercises for this part of the lab reference the following code fragment:

int* p;
int* q = malloc(sizeof(int));
if (q == NULL) {
  perror("Failed to allocate memory");
  exit(EXIT_FAILURE);
}

int x = 5;
p = &x;
*q = 100;
*p = 200;
p = malloc(sizeof(int));
if (p == NULL) {
  perror("Failed to allocate memory");
  exit(EXIT_FAILURE);
}

q = &x;

Exercises

1. Draw box and arrow diagrams for the code fragment above. Update the diagram line-by-line until you reach a diagram that shows the final state after all of the code has run. You can think of malloc as a function that gives you new boxes to store values in, but it does not give the box a name. Remember, when we create a variable x we can draw that as a box labeled with an “x”. Any time we want the value stored in that box we can just write x in our code. Boxes returned by malloc do not have names, and the only way we can reach them is to keep a pointer to the box.

2. Describe, in your own words, the state at the end of the code fragment above. What are the stored values and pointers, and how could you access each value? Are there any stored values you can’t access? Are there any uninitialized boxes?

3. Make a copy of the code fragment above and modify it so it does not lose access to any memory returned from malloc. You will need to create a new int* variable to keep track of each memory location. Your updates should affect only new variables; the values of p, q, and x should be unchanged.

B. Allocating Memory for Strings and Arrays

While it is perfectly normal to use malloc to make space for single variables, we often use malloc to request space for strings and arrays. That’s because we know the sizes of individual values at compile time, so we can usually set aside space for them without malloc. Arrays and strings are different, since we may want them to grow to accommodate user-provided input or data generated as our program runs.

Remember that when we use malloc we get a pointer to space of the requested size, but that space is not initialized. The calloc function does the same thing as malloc, except it zeroes-out the allocated space. In some situations it can be more efficient to use calloc rather than malloc followed by a call to memset to initialize memory, but these cases are rare. The exercises below will ask you to use both malloc and calloc so you’re familiar with both.

Exercises

1. Write a line of C code that uses malloc to allocate space for an array of eight integers. You may want to test your implementation with this code fragment:

   int* arr = /* Your allocation goes here */
   if (arr == NULL) {
      perror("Failed to allocate memory");
      exit(EXIT_FAILURE);
   }
   for (int i=0; i<8; i++) {
      arr[i] = i;
   }
   

2. Repeat exercise 1, but use calloc instead of malloc.

3. Write a line of C code that uses malloc to allocate space for a string with 13 non-null characters. You may want to test your line with this code fragment:

   char* str = /* Your allocation goes here */
   if (str == NULL) {
     perror("Failed to allocate memory");
     exit(EXIT_FAILURE);
   }
   strcpy(str, "Hello");
   strcat(str, ", world.");
   printf("%s\n", str);
   

4. Repeat exercise 3, but use calloc instead of malloc.

5. As a final challenge, you’ll complete a program that allocates an array of strings. This will require multiple allocations: once to make space for the array, and then once for each string that goes in the array. The starter code includes a file, b5.c, that you will need to complete. Instructions appear in the comments in that file. Don’t forget to check to see if your calls to malloc and/or calloc were successful.

C. Freeing Memory

Allocating memory can be tricky on its own, but it comes with an additional responsibility: freeing the memory we’ve allocated. Some languages do this for you, but C does not. This is consistent with C’s overall philosophy: the language does exactly what you ask it to do, and nothing more.

Keeping track of memory can be tricky, especially once we start looking at more complicated data structures built of dynamically allocated memory. For now, you just need to focus on cleaning up the memory you allocate. We will discuss common conventions in C that help us reason about allocated memory and when it should be freed later this week.

Exercises

1. C requires us to free memory returned by malloc and its relatives. Why do you think it is important to free allocated memory? Give at least one specific example of a program that might not work if you allocate memory but never free it.

2. Make a copy of your solution to exercise B.5 above and save it in a file named c2.c. Update your code to free all the memory the program allocates. You’ll need to free each string allocated in the loop, as well as the outer array.

3. Now that we know how to allocate and free memory we can make sense of some of the C standard library functions that allocate memory. Look at the man pages for these string functions: strcat, strcpy, and strdup. All three functions return a char*. Do you think any of them return memory that was allocated with malloc? How do you know?

D. Growing and Shrinking Arrays with realloc

As we’ve discussed in class, one of the reasons we use malloc to that we don’t know how much space we’ll need to store a program’s data until the program is running. Even with that flexibility, we often need to adjust the amount of space we need for an array during a program’s execution. The realloc function is perfectly suited to this use case.

When we allocate an array with malloc we are not allowed to use more space than we asked for. If we need to grow an array we can use malloc to request a larger space, memcpy to copy the bytes from the old space to the new space, and then free the old space. The realloc function does this for us, so it’s usually the cleanest way to grow (or shrink) arrays.

The realloc function does have one advantage over using malloc, memcpy, and free: it can sometimes grow an array without allocating new space. That’s because malloc often returns more space than we request. For example, if we call malloc(5), odds are we’ll end up with an allocated space that could hold 8 or 16 bytes. We’re not allowed to assume this, but realloc can check for this situation and save the copying step when we ask it to grow an array to a size that still fits in the allocated space.

The exercises below will walk you through using realloc to create, grow, and shrink arrays stored on the heap.

Exercises

1. We’re going to need to keep track of two values to manage a dynamic array: a pointer to the start of the array, and its current capacity. Open the dynamic-array.c file included with your starter code and find the variables that track these important values.

2. Now it’s time to allocate space for the array. Let’s expand the array so it can hold three integers. To do this, update capacity to 3 and then request space from the heap. We could do this with malloc, but there’s a convenient way to do this using realloc that you should use for this exercise. You’ll need to review the man page for realloc to see how to use it; you’ll need to pay close attention to how you’re supposed to use realloc’s return value.

   The provided code tests the expanded array by writing to it. You can compile and run the code, but you don’t want to run the checks for later exercises; comment them out or add return 0; before the code for exercise 3.

3. Next, you’ll need to grow the array to hold ten integers. Again, use realloc to do this. Once you’ve made your modification you should be able to run the provided code up through the section for exercise 3.

4. Now use realloc to shrink the array down to hold just nine integers.

5. Finally, you should free the memory used to hold the dynamic array before exiting the program. You could use free to do this, but you can also do it with realloc; give that a try if you want an extra challenge.