Dynamic memory allocation

Dynamic memory allocation allows us to use memory within the heap instead of the stack. This is done by us during runtime (hence the “dynamic”), where we define the size of the data, instead of pre-defining it at compile-time.

Heap allocation is primarily useful for structures that may change sizes or otherwise be defined during runtime, like strings or dynamic arrays.

The alternative to this is to define on the stack. Resizing operations on the stack are expensive, and pre-defining a structure with a large size is inefficient. We also might not be sure how much memory we need until runtime.

In compiled languages, many fixed-size variables and classes are allocated on the stack. Some languages may by default allocate certain structures on the heap (in Rust, this is done with strings and vectors; in C++, this is done with many standard containers). On the other hand, many other languages (especially interpreted ones) allocate data on the heap, by default.

The core mechanism of heap allocation requires two parts: a memory allocation and a memory free. When we need heap space, we allocate memory on it to our program. When we’re done using it, we free it.

Problems

Many bugs exist with heap allocation in C/C++. Most of these are mitigated in some way by the Rust memory ownership model, where rustc can catch most of these problems.

• Use after frees are bugs where we de-reference or otherwise use data after the associated memory has been freed. This often happens via a dangling pointer (multiple pointers to freed memory), or if we use the same pointer after we’ve freed it. This can be difficult to debug and can lead to unexpected behaviour (like a segfault).
  • If possible, we should also be using smart pointers or unique pointers if the language supports it (in our case, C++).
• Double frees happen when we free allocated memory, then try to free the memory again (often in a different part of the code). This leads to undefined behaviour and can meaningfully affect the program, since the heap could get corrupted, or memory might not be allocated properly.
  • This can be mitigated by setting freed pointers to the null pointer (NULL, nullptr), since freeing a null pointer doesn’t do anything.
• Memory leaks occur when we don’t free memory. Optionally, the pointer may have gone out of scope, meaning the underlying allocated memory cannot be accessed again. This builds up non-reusable memory, wastes resources, and can lead to allocation failures.
• Allocation failures are very possible. Memory allocation functionality may fail (usually due to a lack of available heap memory), and allocators will return a null pointer instead of a valid pointer to the heap.
  • This is mitigated by checking for a null pointer on any malloc calls. For many small programs, this shouldn’t be a big concern, but for safety-critical or large applications, this is important to do.

Note also that the language’s standard libraries (including in the GNU C library) may allocate memory for its own uses on top of what users allocate. It usually doesn’t bother explicitly freeing that memory when the program ends, since the operating system kernel will reclaim all process resources when it exits anyways.

Dynamic allocation results in fragmentation. Since we allocate in contiguous blocks, and we can’t move memory around after allocation (for the programmer’s sanity), we get fragments: small contiguous blocks of memory that can’t handle allocation (like a “hole” in memory). There are three requirements for fragmentation:

• Different allocation lifetimes
• Different allocation sizes
• Inability to relocate previous allocations

Language-specific

In C

A basic premise might be to try executing the code below, which instantiates an array specified by the user at runtime:

int size;
scanf("%d", &size);
int array[size];

Beginning in C99, user-defined array sizes at runtime was supported. Systems we’re programming may require older versions, like C89.

DMA’s main mechanisms are supported in the standard library file stdlib.h.

• malloc() — takes in the number of bytes we should allocate in the heap, often with n * sizeof(<TYPE>). Returns a void pointer, which we can type cast to the pointer type we want.
• free() — takes a pointer that frees allocated memory back to the heap.

Let’s break down what this snippet does:

int numOfStudents = 5;
int* marksArray;
marksArray = (int*)malloc(numOfStudents * sizeof(int));
free(marksArray);

• When we use malloc() in this snippet, what we’re doing it asking the function to allocate 20 bytes (i.e. 4 bytes for each student) on the heap.

• malloc() returns a pointer to the first byte in the dynamically allocated memory space.
• We also have to type cast malloc() to an integer pointer.
• That way, marksArray will be pointing to the first integer in the dynamically allocated array.
• Why don’t we explicitly say it’s a pointer? Because integers are 4 bytes anyways so anything more is an array?
• Once we use free(), we return the allocated memory space back to the heap.

In C++

C++‘s dynamic memory allocation interface is done via the new and delete operators, which are built into the language. They’re equivalent to malloc and free, and may use the same allocator back-end.

For example, to dynamically allocate and de-allocate an array and a class Time, we can:

int *ptr = new int [3];
time_v = new Time;
delete time_v;
delete [] ptr; // note the brackets!

In Rust

Heap-allocated memory is supported in Rust via the Box<T> type.