how does dynamic memory allocation work?

Have you ever created an array and later realized it was too small for your data, or way larger than you actually needed? For example, if you write int users[100];, this reserves memory for exactly 100 integers, but if you only require 5, the rest is wasted. If you later need 150, the array is not large enough. So this is a very static flavor of memory allocation.

So we solve this issue using dynamic memory allocation, where we request memory while the program is running instead of fixing the exact amount we will need at compile time.

Where Does Dynamic Memory Come From?

Every running process has its own virtual address space. It has code, global and static data, heap, and stack. The stack usually stores local variables, return information, function call data, etc. Dynamic memory allocation is usually associated with the heap, which is a region managed by a memory allocator. The heap often grows towards higher addresses while the stack grows towards lower addresses, but this can vary across operating systems and architectures.

Stack v/s Heap

Consider this code:

void function() {
    int x = 10;
    int *ptr = malloc(sizeof(int));
}

Now x and ptr are local variables, and these will always be stored in the function stack. However, the memory returned by the malloc function (which we will discuss later in detail) is dynamically allocated. The pointer itself and the memory it points to are completely different things.

The dynamically allocated memory will not automatically disappear just because, for example, the local pointer goes out of scope. In C, the only way you can do this deallocation is by using the free function.

Now, C has four very important functions that we actually need for managing dynamically allocated memory. They all live inside this library: #include <stdlib.h>

1. malloc
2. calloc
3. realloc
4. free

malloc()

Let's say I have a fixed number of bytes I want to reserve, so malloc is used for that case.

int *ptr = malloc(10 * sizeof(int));

Now, how does this work? You see sizeof(int). sizeof(int) returns the number of bytes the integer data type takes, and then we multiply that size by 10. Let's say the size is 4 bytes; then the total is 40. When I say malloc(40), it reserves 40 bytes of memory, and the pointer ptr points to that allocation.

If the allocation is successful, malloc will return a pointer to that memory. If it fails, it returns a null value. Hence, you should always check whether the allocation succeeded before using the pointer.

The return type for malloc is always void*.

What Actually Happens Inside malloc()?

When you call malloc, it does not normally mean that the program will immediately ask the operating system, "Please allocate 100 bytes." There are several layers that happen.

In a simple way, the program executes malloc. That call goes to the memory allocator, which asks the operating system for memory. The allocation lives in virtual memory, and physical frames are mapped underneath when needed.

The implementation of malloc is a part of the memory allocator. There are many kinds of allocators, like jemalloc, tcmalloc, and mimalloc. The allocator usually obtains larger regions of virtual memory from the operating system and then divides them into smaller allocations for the program. This is more efficient than performing an operating system request for every small malloc call.

How Does the Allocator Track Memory?

The allocator must know which blocks are free, the size of each block, and which free blocks it can use for a new allocation. Hence, the allocator needs some kind of internal metadata. A simplified block can have metadata near the user memory. The metadata may contain information like size, allocation state, and links to the next free blocks. The exact structure depends on the allocator.

The pointer returned by malloc points to the usable memory provided to the program. The allocator metadata is internal, and the program can never access it.

Finding a Free Block

Suppose the allocator has this kind of scenario.

+---------+---------+---------+---------+
| 100 B   | 300 B   | 200 B   | 500 B   |
| USED    | FREE    | USED    | FREE    |
+---------+---------+---------+---------+

Now the program executes malloc(250). The allocator now needs to find a free block that is large enough for this. The 300-byte free block should be the best answer, but instead of wasting the entire 300-byte block, the allocator splits it into 250 bytes and some free space.

Real allocators also need extra space for metadata and minimum block sizes, so a real split is more complicated than this simple explanation.

How Does malloc() Find Blocks Quickly?

Searching through every block of memory is very inefficient, so modern allocators use structures like bins, trees, size classes, thread-local caches, free lists, etc.

Suppose small allocations may be grouped according to sizes like 8, 16, 32, and so on. If a program requests a particular size, the allocator can search the appropriate category and get that size rather than scanning the whole heap. There are many different strategies. We will not go into detail.

free()

When dynamically allocated memory is no longer needed, you should always release it using free. The way you use it is free(ptr);. This tells the allocator that the allocation can now be reused. Any used section can now be freed, and another allocation can reuse it later, but there is one neat caveat here: free does not necessarily return that memory directly back to the operating system. The allocator may keep the memory available so that a future malloc can reuse it quickly.

Coalescing Free Blocks

Suppose the heap contains adjacent free blocks. Instead of treating two free regions separately, an allocator may combine them into a larger free region. Conceptually, this process is called coalescing.

This helps the allocator satisfy larger future allocations and reduce external fragmentation.

calloc()

This is a different kind of allocation function. It does the same thing as malloc, but in a different way.

calloc(number_of_elements, size_of_each_element);

Whenever I do something like calloc(10, sizeof(int)), it allocates enough memory for 10 integers, just like malloc, but all allocated bytes are initialized to 0. With malloc(40), you request one 40-byte region. With calloc(10, sizeof(int)), you express the request as 10 elements, each of size sizeof(int). That is the main difference between calloc and malloc.

realloc()

Sometimes an existing allocation needs to become larger or smaller, so we use realloc. It is a function that will resize the existing allocation. It works like this.

ptr = realloc(ptr, 200);

Safer pattern (avoid losing the original pointer if realloc fails):

int *new_ptr = realloc(ptr, new_size);
if (new_ptr != NULL) {
    ptr = new_ptr;
}

There are two possibilities that can happen with realloc:

Case 1: The block can grow in place

If enough suitable free space exists near the allocation, the allocator will expand the existing block without just moving it.

Case 2: The block has to move

If another allocated block prevents the expansion, the allocator will first allocate a new larger block, preserve the old contents, release the old block, and return the new pointer. This is why the address returned by realloc may be different from any kind of original address as well.

If realloc fails for a non-zero requested size, the original allocation still remains, so assigning the result directly to the only pointer can make you lose access to it. Always use the safer pattern above.

Memory Leaks

Back in 2024, the US government also urged developers to move away from C and C++ in some contexts because memory safety bugs are common when you have to manage memory manually.

This is one of the most common dynamic memory bugs. For example, let's see this example.

int *ptr = malloc(100);
ptr = NULL;

Initially, the pointer pointed to the allocated memory. Now, when you write ptr = NULL, that pointer no longer points to the original allocated memory. The allocation still exists, but the program has now lost the pointer to actually access it. You have not freed that memory, so it can still contain sensitive data.

Another by-product is that the process will now consume more and more memory if you continue doing this. If returned pointers are discarded, memory usage can keep increasing until the process terminates, and with that, you will see memory usage explode over time.

Dangling Pointers

The opposite can also happen.

int *ptr = malloc(sizeof(int));
free(ptr);
*ptr = 10;

After the free, the allocation no longer exists or belongs to the program through that pointer, but the pointer still contains the older address. This kind of situation is called a dangling pointer. Dereferencing a dangling pointer results in undefined behavior.

A defensive pattern is to set the pointer to null after you free it. It does not fix aliases, but it at least prevents that particular variable from being dereferenced later by mistake.

Fragmentation

Repeated allocation and deallocation can cause memory to break into small fragments, so there are two common forms of fragmentation.

External Fragmentation

Suppose a free space is scattered throughout memory. There may be plenty of free memory in total, but not a suitable contiguous free region for a particular allocation. This situation is called external fragmentation.

Internal Fragmentation

Suppose an allocator uses a 64-byte size class. The application requires 50 bytes, but internally the allocator reserves 64 bytes. Then 14 bytes of that allocation are unused from the application's perspective. This wasted space inside an allocated block is called internal fragmentation.

You should try to avoid patterns that fragment the heap too much. Allocators try their best to reduce fragmentation through many methods, like splitting blocks, size classes, bins, etc.

Finally

So now, the main purpose of dynamic memory allocation is simple: we want to request memory according to our needs at runtime, not pre-allocate a static memory block early. We also learned that malloc, calloc, and realloc look like simple function calls, but underneath, they are part of an end-to-end memory management system that coordinates the program allocator, virtual memory, operating system, and physical RAM.

Also, keep in mind that whenever you do malloc(10000000), the system may not immediately reserve 10 million bytes of physical memory. It can reserve virtual address space and map physical pages whenever the memory is actually used. As we learned earlier, the mapping is handled completely by the operating system.