Dive Into Systems

2.4. Dynamic Memory Allocation

In addition to pass-by-pointer parameters, programs commonly use pointer variables to dynamically allocate memory. Such dynamic memory allocation allows a C program to request more memory as it’s running, and a pointer variable stores the address of the dynamically allocated space. Programs often allocate memory dynamically to tailor the size of an array for a particular run.

Dynamic memory allocation grants flexibility to programs that:

do not know the size of arrays or other data structures until runtime (e.g. the size depends on user input)
need to allow for a variety of input sizes (not just up to some fixed capacity)
want to allocate exactly the size of data structures needed for a particular execution (don’t waste capacity)
grow or shrink the sizes of memory allocated as the program runs, reallocating more space when needed and freeing up space when it’s no longer required.

2.4.1. Heap Memory

Every byte of memory in a program’s memory space has an associated address. Everything the program needs to run is in its memory space, and different types of entities reside in different parts of a program’s memory space. For example, the code region contains the program’s instructions, global variables reside in the data region, local variables and parameters occupy the stack, and dynamically allocated memory comes from the heap. Because the stack and the heap grow at runtime (as functions are called and return and as dynamic memory is allocated and freed), they are typically far apart in a program’s address space to leave a large amount of space for each to grow into as the program runs.

Dynamically allocated memory occupies the heap memory region of a program’s address space. When a program dynamically requests memory at runtime, the heap provides a chunk of memory whose address must be assigned to a pointer variable.

Figure 1 illustrates the parts of a running program’s memory with an example of a pointer variable (ptr) on the stack that stores the address of dynamically allocated heap memory (it points to heap memory).

The parts of program memory showing a stack variable pointing to dynamically allocated heap memory.

Figure 1. A pointer on the stack points to a block of memory that was allocated from the heap.

It’s important to remember that heap memory is anonymous memory, where "anonymous" means that addresses in the heap are not bound to variable names. Declaring a named program variable allocates it on the stack or in the data part of program memory. A local or global pointer variable can store the address of an anonymous heap memory location (e.g. a local pointer variable on the stack can point to heap memory), and dereferencing such a pointer enables a program to store data in the heap.

2.4.2. malloc and free

malloc and free are functions in the standard C library (stdlib) that a program can call to allocate and deallocate memory in the heap. Heap memory must be explicitly allocated (malloc’ed) and deallocated (freed) by a C program.

To allocate heap memory, call malloc, passing in the total number of bytes of contiguous heap memory to allocate. Use the sizeof operator to compute the number of bytes to request. For example, to allocate space on the heap to store a single integer, a program could call:

// Determine the size of an integer and allocate that much heap space.
malloc(sizeof(int));

The malloc function returns the base address of the allocated heap memory to the caller (or NULL if an error occurs). Here’s a full example program with a call to malloc to allocate heap space to store a single int value:

#include <stdio.h>
#include <stdlib.h>

int main(void) {
    int *p;

    p = malloc(sizeof(int));  // allocate heap memory for storing an int

    if (p != NULL) {
        *p = 6;   // the heap memory p points to gets the value 6
    }
}

The malloc function returns a void * type, which represents a generic pointer to a non-specified type (or to any type). When a program calls malloc and assigns the result to a pointer variable, the program associates the allocated memory with the type of the pointer variable.

Sometimes you may see calls to malloc that explicitly recast its return type from void * to match the type of the pointer variable. For example:

p = (int *) malloc(sizeof(int));

The (int *) before malloc tells the compiler that the void * type returned by malloc will be used as an int * in this call (it recasts the return type of malloc to an int *). We discuss type recasting and the void * type in more detail later in this chapter.

A call to malloc fails if there is not enough free heap memory to satisfy the requested number of bytes to allocate. Usually, malloc failing indicates an error in the program such as passing malloc a very large request, passing a negative number of bytes, or calling malloc in an infinite loop and running out of heap memory. Because any call to malloc can fail, you should always test its return value for NULL (indicating malloc failed) before dereferencing the pointer value. Dereferencing a NULL pointer will cause your program to crash! For example:

int *p;

p = malloc(sizeof(int));
if (p == NULL) {
    printf("Bad malloc error\n");
    exit(1);   // exit the program and indicate error
}
*p = 6;

When a program no longer needs the heap memory it dynamically allocated with malloc, it should explicitly deallocate the memory by calling the free function. It’s also a good idea to set the pointer’s value to NULL after calling free, so that if an error in the program causes it to be accidentally dereferenced after the call to free, the program will crash rather than modify parts of heap memory that have been reallocated by subsequent calls to malloc. Such unintended memory references can result in undefined program behavior that is often very difficult to debug, whereas a null pointer dereference will fail immediately, making it a relatively easy bug to find and to fix.

free(p);
p = NULL;

2.4.3. Dynamically Allocated Arrays and Strings

C programmers often dynamically allocate memory to store arrays. A successful call to malloc allocates one contiguous chunk of heap memory of the requested size. It returns the address of the start of this chunk of memory to the caller, making the returned address value suitable for the base address of a dynamically allocated array in heap memory.

To dynamically allocate space for an array of elements, pass malloc the total number of bytes in the desired array. That is, the program should request from malloc the total number of bytes in each array element times the number of elements in the array. Pass malloc an expression for the total number of bytes in the form of sizeof(<type>) * <number of elements>. For example:

int *arr;
char *c_arr;

// allocate an array of 20 ints on the heap:
arr = malloc(sizeof(int) * 20);

// allocate an array of 10 chars on the heap:
c_arr = malloc(sizeof(char) * 10);

After the calls to malloc in this example, the int pointer variable arr stores the base address of an array of 20 contiguous integer storage locations in heap memory, and the c_arr char pointer variable stores the base address of an array of 10 contiguous char storage locations in heap memory. Figure 2 depicts what this might look like.

Main’s stack holds two pointer variables. The first, arr, contains the address of a block of memory on the heap with enough space for 20 integers. The second, c_arr, contains the address of a different block of memory on the heap with enough space for 10 characters.

Figure 2. A 20-element integer array and 10-element character array allocated on the heap.

Note that while malloc returns a pointer to dynamically allocated space in heap memory, C programs store the pointer to heap locations on the stack. The pointer variables contain only the base address (the starting address) of the array storage space in the heap. Just like statically declared arrays, the memory locations for dynamically allocated arrays are in contiguous memory locations. While a single call to malloc results in a chunk of memory of the requested number of bytes being allocated, multiple calls to malloc will not result in heap addresses that are contiguous (on most systems). In the example above, the char array elements and the int array elements may be at addresses that are far apart in the heap.

After dynamically allocating heap space for an array, a program can access the array through the pointer variable. Because the pointer variable’s value represents the base address of the array in the heap, we can use the same syntax to access elements in dynamically allocated arrays as we use to access elements in statically declared arrays. Here’s an example:

int i;
int s_array[20];
int *d_array;

d_array = malloc(sizeof(int) * 20);
if (d_array == NULL) {
    printf("Error: malloc failed\n");
    exit(1);
}

for (i=0; i < 20; i++) {
    s_array[i] = i;
    d_array[i] = i;
}

printf("%d %d \n", s_array[3], d_array[3]);  // prints 3 3

It may not be obvious why the same syntax can be used for accessing elements in dynamically allocated arrays as is used in accessing elements in statically declared arrays. However, even though their types are different, the values of s_array and d_array both evaluate to the base address of the array in memory.

Table 1. Comparison of Statically Allocated s_array and Dynamically Allocated d_array
Expression	Value	Type
s_array	base address of array in memory	(static) array of int
d_array	base address of array in memory	int pointer (int *)

Because the names of both variables evaluate to the base address of the array in memory (the address of the first element memory), the semantics of the [i] syntax following the name of the variable remain the same for both: [i] dereferences the int storage location at offset i from the base address of the array in memory — it’s accessing the _i_th element.

For most purposes, we recommend using the [i] syntax to access the elements of a dynamically allocated array. However, programs can also use the pointer dereferencing syntax (the * operator) to access array elements. For example, placing a * in front of a pointer that refers to a dynamically allocated array will dereference the pointer to access element 0 of the array:

/* these two statements are identical: both put 8 in index 0 */
d_array[0] = 8; // put 8 in index 0 of the d_array
*d_array = 8;   // in the location pointed to by d_array store 8

The Arrays section describes arrays in more detail, and the Pointer Arithmetic section discusses accessing array elements through pointer variables.

When a program is finished using a dynamically allocated array, it should call free to deallocate the heap space. As mentioned earlier, we recommend setting the pointer to NULL after freeing it:

free(arr);
arr = NULL;

free(c_arr);
c_arr = NULL;

free(d_array);
d_array = NULL;

Heap Memory Management, malloc and free

The C standard library implements malloc and free, which are the programming interface to its heap memory manager. When called, malloc needs to find a contiguous chunk of unallocated heap memory space that can satisfy the size of the request. The heap memory manager maintains a free list of unallocated extents of heap memory, where each extent specifies the start address and size of a contiguous unallocated chunk of heap space.

Initially, all of heap memory is empty, meaning that the free list has a single extent consisting of the entire heap region. After a program has made some calls to malloc and free, heap memory can become fragmented, meaning that there are chunks of free heap space interspersed with chunks of allocated heap space. The heap memory manager typically keeps lists of different ranges of sizes of heap space to enable fast searching for a free extent of a particular size. In addition, it implements one or more policies for choosing among multiple free extents that could be used to satisfy a request.

The free function may seem odd in that it only expects to receive the address of the heap space to free without needing the size of the heap space to free at that address. That’s because malloc not only allocates the requested memory bytes, but it also allocates a few additional bytes right before the allocated chunk to store a header structure. The header stores metadata about the allocated chunk of heap space, such as the size. As a result, a call to free only needs to pass the address of heap memory to free. The implementation of free can get the size of the memory to free from the header information that is in memory right before the address passed to free.

For more information about heap memory management, see an OS textbook (for example, Chapter 17 ``Free Space Management'', in OS in Three Easy Pieces covers these details).

2.4.4. Pointers to Heap Memory and Functions

When passing a dynamically allocated array to a function, the pointer variable argument’s value is passed to the function (i.e., the base address of the array in the heap is passed to the function). Thus, when passing either statically declared or dynamically allocated arrays to functions, the parameter gets exactly the same value — the base address of the array in memory. As a result, the same function can be used for statically and dynamically allocated arrays of the same type, and identical syntax can be used inside the function for accessing array elements. The parameter declarations int *arr and int arr[] are equivalent. However, by convention, the pointer syntax tends to be used for functions that may be called with dynamically allocated arrays:

int main(void) {
    int *arr1;

    arr1 = malloc(sizeof(int) * 10);
    if (arr1 == NULL) {
        printf("malloc error\n");
        exit(1);
    }

    /* pass the value of arr1 (base address of array in heap) */
    init_array(arr1, 10);
    ...
}

void init_array(int *arr, int size) {
    int i;
    for (i = 0; i < size; i++) {
        arr[i] = i;
    }
}

At the point just before returning from the init_array function, the contents of memory will look like Figure 3. Note that when main passes arr1 to init_array, it’s passing only the base address of the array. The array’s large block of contiguous memory remains on the heap, and the function can access it by dereferencing the arr pointer parameter. It also passes the size of the array so that init_array knows how many elements to access.

Main’s arr1 and init_array’s arr variable both store the same base address of a block of heap memory.

Figure 3. The contents of memory prior to returning from init_array. Both main’s arr1 and init_array’s arr variable point to the same block of heap memory.