Dynamic memory allocation

Dynamic memory allocation gives us, as programmers, mechanisms to define variables and use memory within the heap instead of the stack. This is done by us during runtime, where we define the size of the data, instead of pre-defining it at compile-time.

DMA 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.

Basics

The core mechanism of DMA 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.

Many bugs exist with DMA 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.

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.

C++

C++‘s DMA 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!

Rust

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