jszhn

Recent Notes

Heap allocation

5 min read

An important type of memory allocation is done on the heap instead of the stack, called dynamic memory allocation. This is done by us at runtime (hence the “dynamic”), instead of it being defined at compile-time.

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

The alternative to this is to define on the stack. Resizing operations on the stack are expensive and possibly unsafe (via an alloca), 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 types are allocated on the stack. Certain data structures may be allocated on the heap by default. Conversely, many interpreted languages allocate on the heap by default.

For example, strings in both Rust and C++ are allocated on the heap. Many containers in the STL are also heap-allocated.

The core mechanism of heap allocation relies on the allocator. For the developer, it consists of two parts:

  • A memory allocation, which is done when we need heap space.
  • And a memory free, which is when we’re done using it.

Generally

Programming considerations

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).
  • 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 effectively compulsory.

Invisible allocations

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.

Context-specific

Kernel-mode

Heap memory is generally more constrained in kernel-mode drivers. In Windows, requested allocations are fine-grained and are specified by the developer:1

  • Cache-aligned or not
  • Non-pageable or pageable

Language-specific

note: some memory might not actually be allocated might return an address and only be allocated after a write tldr: values that haven’t been initialised aren’t dependable. we might not have anything to work with

memset(s, 0, sizeof(*s));
s->a = 1;
s->b = 2;
s->c = 3;

compresses to one write memset is FAST

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.
    • Note in general: sizeof on a pointer will return the machine size.
  • 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.

Footnotes

  1. From Windows kernel - Windows drivers | Microsoft Learn ↩

Graph View

Backlinks