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.

Download the file malloc.tar.gz to get the starter code for today’s lab. Then run the following commands to extract it and get started:

$ cd csc161/labs
$ tar xvzf ~/Downloads/malloc.tar.gz
$ 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 = (int*)malloc(sizeof(int));
if (q == NULL) {
  perror("Failed to allocate memory");
  exit(EXIT_FAILURE);
}

int x = 5;
p = &x;
*q = 100;
*p = 200;
p = (int*)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;
   }
   

   You can check your code for correctness by compiling this with AddressSanitizer. To do this you’ll need to pass -g and -fsanitize=address to clang when you compile your code. If you write your code in a file named b1.c you would run:

   $ clang -g -fsanitize=address -o b1 b1.c
   

   To test your code, run the program with this extra AddressSanitizer option:

   $ ASAN_OPTIONS=detect_leaks=0 ./b1
   

   The program should run to completion with no AddressSanitizer errors.

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);
   

   Again, you can check your work using AddressSanitizer. When you run the program with the ASAN_OPTION=detect_leaks=0 option it should complete without reporting any errors.

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. You can check your work by compiling your program with AddressSanitizer.

   When you run the program this time, do not pass in the extra AddressSanitizer option. Just compile and run it like this:

   $ clang -g -fsanitize=address -o c2 c2.c
   $ ./c2
   

   The program should run without reporting any errors. If you forget to free any memory, AddressSanitizer will report a memory leak when the program exits. Note: the version of clang provided with macOS does not support leak detection on some macs. You may need to install a standard version of clang instead of Apple’s variant, or just use MathLAN.

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. There is an additional starter code file you’ll need for these exercises. If the file wasn’t included in your original download, please download dynamic-array.c and move it to the directory you’re using for this lab:

   $ mv ~/Downloads/dynamic-array.c ~/csc161/labs/malloc/
   

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.

E. Common Errors when Allocating Memory (if you have time)

It’s easy to accidentally misuse allocated memory in C. Some of the errors related to allocated memory are analogous to errors with local arrays or variables, but other errors are specific to heap-allocated memory. The important errors you should be aware of are:

Memory Leaks

A memory leak happens any time you call malloc (or one of its relatives) and fail to free the allocated memory before the program exits. Leaks are especially bad if the allocation occurs in a loop because the program will continue to use more and more memory as it runs. Eventually, the program may be unable to continue.

Heap Buffer Overruns

If you read or write beyond the end of a malloced array, that’s a heap buffer overrun. This is similar to reading or writing past the end of a local array. As a rule, only access memory you’ve requested; if you call malloc(5), only access five bytes of space starting at the pointer malloc returns.

Use After Free

Never use heap-allocated memory after you’ve freed it. You might get away with this in some cases, but it’s always an error; it just doesn’t always cause an immediate crash in some cases. That’s actually worse than an error that crashes right away, since it can lie dormant in your code and wait until 11:58pm the night an assignment is due to start causing trouble.

Double Free

You’re required to free allocated memory exactly once. If you free the memory zero times that’s a leak, and if you free it more than once that’s a double free. Sometimes the allocator will catch this and warn you, but if it doesn’t you could end up with corrupted data later in the program’s execution.

Exercises

If you have time before the end of the lab, try writing programs that contain each of these errors. What happens when you run a program containing each of these errors? AddressSanitizer will catch all of these errors, so you should also try running the program to see how it reports the error.