Development

Master Memory Management: Create Your Own malloc Library from Scratch

Dynamically allocated memory in C

Are you curious about how dynamically allocated memory works? I was too, so I decided to build my own malloc implementation.

In this article, I’ll share everything you need to know about malloc — why it exists, how it works, and how to build it yourself using mmap/munmap functions and memory handling algorithms. I’ve even included my completed project on GitHub for you to reference. Join me in learning about memory management by building your own malloc library! 👷

Memory management

C manages variables in memory, but there are some limitations to this.

Static and global variables are stored in main memory along with the program’s executable code and they remain there for the entire duration of the program.

Automatic duration variables, like a local int variable in a function, are stored on the stack and are created and destroyed every time a function is called or returned.

This can be problematic for 2 reasons:

Because the size of the allocation must be set at compile time
Because the lifespan of a variable can’t be adjusted — it’s not possible to choose when to create or delete them.

Dynamic allocation and mmap

Fortunately, the UNIX kernel provides a system call that allows us to allocate memory with a specified size. In this article, we’ll be using the mmap() function to map physical memory to virtual addresses and get a pointer to the start, but you can also use sbrk. mmap is a great tool for managing memory and virtual addresses.

Here comes malloc

If mmap can return a memory zone, why do we need malloc? System calls are time-consuming and most programs often request and release a large amount of memory frequently. Making a system call every time would greatly reduce performance.

Malloc helps to solve this problem by acting as a performance wrapper around mmap. We can preallocate more memory than needed to avoid system calls, at the cost of a small memory overhead. New malloc calls will use the preallocated space until more space is required.

Implementation

The library

The malloc library allocates a block of memory and returns a pointer to its start. When the program is finished with the memory, the pointer is passed to free() to release it. realloc increases or decreases the size of a malloc pointer and preserves its data, returning a new pointer.

Data structure

A memory zone allocated by mmap is called a heap. The heap is filled with blocks. Both heaps and blocks have metadata at their start. The following is the structure of a heap with one block (resulting from a single call to malloc).

We can use the following metadata structures:

By chaining blocks with next and prev pointers, we can iterate through the heap and access any block. C structures always have a fixed size, which we can use to move safely from a metadata pointer to the start of the data. This helps us manage the heap and blocks effectively.

Performance

To efficiently preallocate memory, we categorize blocks into 3 sizes: SMALL, TINY, and LARGE. As a general rule, at least 100 SMALL and TINY blocks should fit inside their own heap. Larger blocks, on the other hand, are not preallocated.

getpagesize()

It’s more efficient to use a multiple of getpagesize() when defining the size of a heap. For example, on my system the page size is 4096 bytes (run getconf PAGE_SIZE).

Let’s say we use 128 bytes as the maximum size for tiny blocks. If we fill a heap with 128 of them, it gives us a TINY_HEAP_ALLOCATION_SIZE of 16KB (128 * 128). However, since each malloc must store its metadata (sizeof(t_block) = 32 bytes), we won’t be able to fit all 128 blocks in the heap. 16 KB / (128 + 32) = 102.4, so we can fit 102 128-byte mallocs in the 16KB heap, including the t_heap at the start of the heap.

Let’s use the following values:

The malloc algorithm

When malloc is called, it searches for an available space and returns its address. However, since the virtual addresses of old blocks can’t be changed, we must manage free space that may be fragmented between them. To do this:

Malloc searches for a reference to the heap list (if it exists) and stores it in a global variable.
It goes through each heap to try and fill a freed space using the first fit strategy — it iterates through each block from start to end until it finds a freed block with enough space.
If no suitable block is found, malloc appends a new block to the end of the last heap.
If the last heap doesn’t have enough available space, the algorithm creates a new heap by calling mmap.

Free and the fragmentation problem

When the free function is called, the program sets the status of the requested block to freed. However, since the virtual addresses of blocks can’t be changed, we often end up with fragmented freed memory in the heap (as shown in the graph above).

If block->prev->freed || block->next->freed, we merge them.
It it was the last block in the heap, we munmap to release memory to the system (but we must still keep one preallocated)

Realloc

Realloc is essentially the same as calling malloc + memcpy + free.

If the requested space is zero, the behavior is implementation-defined. I chose to implement a “lazy” version that simply returns ptr. However, it’s important to note that realloc(ptr, 0) should not be used as a replacement for free.

Testing

The best way to test our malloc is to use it in usual commands, like ls or vim. Create the following run.sh file and execute it before the desired command sh run.sh ${CMD}.

Align memory on MacOS

I had difficulty understanding why certain commands, like vim, would cause a segmentation fault on my system. It turns out that the MacOS malloc aligns data on 16 bytes. To implement this, simply set size = (size + 15) & ~15.

I hope that this has helped you gain a better understanding of the malloc library. If you need more information, please feel free to check out the completed implementation on my GitHub. I’ll also be happy to answer any questions or comments you may have. 😁

Tired of supporting big corporations every time you shop online? Switch to open.mt, the decentralized marketplace that uses blockchain technology to enable peer-to-peer commerce with no intermediaries. Not only can you get better prices and faster transactions, but you can also support your local merchants and keep your community thriving.

Follow us for updates on our progress and be the first to join the open.mt community when we launch. Thank you for your support and we can’t wait to welcome you to our open market!