C: Dynamic Memory Allocation

You can access the slides 🖼️ for this lecture.

Here we cover dynamic memory allocation, which corresponds to manual allocation of memory by the programmer. This is extensively used in C to allocate memory for large quantities of data or for data structures whose size is not known at compile time (e.g., user input).

Motivation

So far we looked at programs in which the total amount of memory needed for their data and code was known at compile time. As a result, the compiler handles all memory allocation automatically. This is called static memory allocation. However, there are situations where we need to reserve some memory whose size is not known until runtime.

Consider the following program:

void process_array(int size) {
    int arr[size];  // variable-size array,
                    // not a great solution
    for (int i = 0; i < size; i++){
        arr[i] = i * i;
        printf("%d\n", arr[i]);
    }
}

int main() {
    int n;
    printf("Enter the size of the array: ");
    scanf("%d", &n);
    if (n > 0) process_array(n);

    printf("all good\n");
    return 0;
}

This code asks the user for a number with the scanf function. That number is then passed to a function that allocates an array whose size is based on that number. The size will only be known at runtime because it depends on the number entered by the user. What we have here is a variable-sized array, which is generally a bad practice in C. As a local variable, arr is stored in an area of the address space called the stack. The stack has a very small size, just a few megabytes on modern general-purpose OSes such as Linux. As a result, if the user enters a number that is too large, the stack will overflow and the program will crash or misbehave. If you try it out and input 100000000000000, the program will crash and be terminated by the OS as follows:

$ gcc variable-size-array.c -o prog
$ ./prog
Enter the size of the array: 100000000000000
[1]    17467 segmentation fault (core dumped)  ./prog

We need a better solution.

malloc and free

The programmer manually allocates memory with a function called malloc, and when that memory is no longer needed by the program it must be released manually with a function called free.

malloc. To allocate at runtime memory whose size is 1) unknown at compile-time and/or 2) potentially large, in C we must use the malloc function. Its prototype is as follows:

void *malloc(size_t size);

malloc accepts a single parameter, size, which specifies the amount of bytes to allocate. It allocates a contiguous area of memory in the address space (we call that a buffer), and returns a pointer to the first byte of that area, or NULL if the allocation failed. One important point to note is that, although for allocation requests of reasonable sizes malloc will almost always succeed, in practice we can never be certain of the outcome of the allocation. Indeed, the system may be running low on memory and unable to satisfy certain calls to malloc. As a result, it is important to always check that the return value of malloc is not NULL before starting to use the allocated memory. If malloc returns NULL, you also need to take appropriate action, for example exit the program with an error message.

Also note that malloc returns a void * pointer: it is a generic pointer that can be transformed into a pointer to any other type through an operation called a cast. As a result, malloc can allocate memory that can hold any type of data.

free. Any area of memory allocated manually by the programmer with malloc must also be released manually when it is no longer needed. This is done with the free function, whose prototype is:

void free(void *p);

free takes the pointer returned by malloc as a parameter, i.e., the first byte of the memory area to release.

We can now see malloc and free in action in the following example. This is an adaptation of our previous program that was using variable-sized arrays, this time using dynamic memory allocation:

void process_array(int size) {
  // Allocate an area of memory large enough to contain n integers:
  int *arr = (int *)malloc(size * sizeof(int));

  if(arr == NULL) { // ALWAYS check malloc's return value, if it fails we just exit
    printf("ERROR: cannot allocate memory\n");
    exit(-1);
  }

  for (int i = 0; i < size; i++)
        arr[i] = i * i;

  free(arr); // release memory with free
}

You can observe that the function allocating the array starts by calling malloc. It requests enough space to store size integers, so the parameter passed to malloc is size * sizeof(int). The (int *) before malloc is our cast: we transform the void pointer it returns into an int pointer, which, as you recall from the previous video, points to an array of integers. We then need to check that the allocation succeeds. If it fails, we print an error message and exit. If successful, we can iterate over the array normally and populate it. Once we are done, we can release the memory using free.

Memory Leaks

It is important not to forget to release memory allocated with malloc when it is no longer needed. A program that fails to release memory it has allocated with malloc is said to have a memory leak. Leaks are a security issue: they can be exploited by an attacker to crash the program or starve the machine of resources.

The code below is a buggy program, an adaptation of our previous example in which the free call was removed:

void process_array(int size) {
  // Allocate an area of memory large enough to contain n integers:
  int *arr = (int *)malloc(size * sizeof(int));

  if(arr == NULL) { // ALWAYS check malloc's return value, if it fails we just exit
    printf("ERROR: cannot allocate memory\n");
    exit(-1);
  }

  for (int i = 0; i < size; i++)
        arr[i] = i * i;

  // No free! At that stage the pointer arr is gone so the memory will never be freed!
  // It's a leak of size * sizeof(int) bytes
}

This program is incorrect and allocates memory that is never freed: it leaks memory. On Linux, a command-line tool named Valgrind can help identify leaks, among other memory errors. To help understand the output of Valgrind, it is useful to embed debug symbols into the program’s binary at compile time with the -g switch:

$ gcc -g my-leaky-program.c -o my-leaky-program

We can then run the program under Valgrind:

$ valgrind --leak-check=full  ./my-leaky-program   # invoke valgrind
# ...
Enter the size of the array: 100
==144325== 
==144325== HEAP SUMMARY:
==144325==     in use at exit: 400 bytes in 1 blocks
==144325==   total heap usage: 3 allocs, 2 frees, 2,448 bytes allocated
==144325== 
==144325== 400 bytes in 1 blocks are definitely lost in loss record 1 of 1
==144325==    at 0x48407B4: malloc (vg_replace_malloc.c:381)
==144325==    by 0x109194: process_array (my-leaky-program.c:5)
==144325==    by 0x109235: main (my-leaky-program.c:25)
==144325== 
==144325== LEAK SUMMARY:
==144325==    definitely lost: 400 bytes in 1 blocks
==144325==    indirectly lost: 0 bytes in 0 blocks
==144325==      possibly lost: 0 bytes in 0 blocks
==144325==    still reachable: 0 bytes in 0 blocks
==144325==         suppressed: 0 bytes in 0 blocks

Valgrind reports that 400 bytes of memory have been leaked, and provides some information about where the leak comes from, so it can be fixed. Please make sure to use Valgrind to check for leaks in all the C code you produce as part of this unit. Leaks are a bug and a security issue, and your code should be free from them.