Rewriting malloc

August 02, 2024

Mandatory part

Rewrite malloc, free, and realloc functions.

Also, write a show_alloc_mem function to print memory allocations.

Like the real malloc, the allocated memory must be stored in pre-allocated “zones” (bins), unless the requested size is too big, then the allocation must be fitted.

Note
Fitted allocations are allocations that are outside of a bin, meaning it’s allocated directly with a call to mmap.

Two zone types are required:

Tiny zones of N size, storing allocations from 0 to n size
Small zones of M size, storing allocations from n+1 to m size
Large allocations, fitted allocations beginning from m+1

Zones size must be a multiple of the page size, acquired with sysconf(_SC_PAGESIZE). Allocations (and internally required allocations) must be executed with mmap, de-allocations with munmap.

Bonus part

Making mandatory functions thread-safe
Additional info print (mem dump, allocations history…) through flags or extra functions
De-fragmentation of the bins
Debug flags

Mandatory part code explanation

Slightly inspired by debian glibc malloc

Important
When words related to allocation are put between double quotes, it means that it is not necessarily an allocation. Attributing a portion of a bin is not an allocation; a fitted allocation is indeed an allocation.

Since most of the explanations are not linked to real memory allocations made with mmap and applies to bin or fitted “allocations”, whether it is an attribution or an allocation does not change how it is organized.

Brief explanation of memory alignment

The computer reads memory by sections of 4/8 bytes, or 32/64 bits; this determines the name of the architecture.

Aligning memory corresponds to setting variables at the start of 4/8 bytes sections. If this is not respected, it raises:

Constraint violation: an alignment error interrupts the execution of instructions.
Non-optimal alignment: twice 4 well-aligned bytes are read, then the 4 misaligned bytes are extracted from these 8 bytes, which takes much longer than reading 4 well-aligned bytes.

Considering this, compilers will automatically align memory when possible by padding memory with char. When the fields of a structure are not positioned properly or the total size of a structure is not a multiple of 4/8, it will take more memory than it should, due to padding.

However, when freely attributing values in memory, it is required to be careful with alignment to prevent unnecessary slowdowns.

Chunks

Every memory “allocation” (bin or fitted) is preceded by a header. The combination of a memory “allocation” (data) and its header is called a chunk.

The header bears the following information:

Allocation size (unsigned long)
Allocation real size (unsigned long)
Pointer to the next chunk (void *)
Pointer to the previous chunk (void *)

For a total of 16/32 bytes on 32/64 bits architectures. The structure itself is memory aligned, and the start of the data is also aligned. The data size is always set to a multiple of 16, forcing memory alignment on every architecture.

The data size is often larger than what was asked, to keep memory aligned. The portion of data that matches the size asked by the user (real size) is called provided data, the remainder is called tail.

To sum things up, this is how a chunk is organized in memory (assuming a line is 4/8 bytes):

Section	Data stored	Type of data
Header	size of data (size)	`unsigned long`
Header	size of provided data (real size)	`unsigned long`
Header	pointer to next chunk (next)	`void *`
Header	pointer to previous chunk (prev)	`void *`
data	provided data (could be any size)	N/R
data	tail (could be any size)	N/R

The size of the provided data is only here for debug information and show_alloc_mem.

Pros and cons

The pros of overhead instead of exported bookkeeping are that it is faster to retrieve data related to a chunk with a pointer (in free or realloc, for example) since it only requires subtracting the header size from the pointer to retrieve its header.

It also takes less space since it does not contain pointers to data.

It also requires fewer calls to mmap (which are fairly slow) since it is not allocated elsewhere; data and header are allocated in a single call.

The cons are that a non-cautious user writing out of provided data bounds might ruin the bookkeeping data and ruin malloc… But well, nobody is supposed to write out of bounds, right?

Bins

Similarly to a chunk, bins have a preceding header. The only differences are that the size corresponds to the full zone size, header included, that the real size field is unused, and that pointers point to bins instead of chunks.

malloc

When calling malloc, if the size is not too high for a bin (then it just performs a fitted allocation), it will iterate in the proper bin (corresponding to the requested size) and find a free chunk with the proper size. This helps to prevent bin fragmentation. If it reaches the end of a bin and there is enough space left in the bin, it will attribute a chunk in the bin. If there is not enough space left in the bin, it will create a new bin.

If several contiguous freed chunks’ total size matches the new chunk’s size, they will be joined as a single chunk, again, to prevent fragmentation.

free

When calling free, if the size is not too high for a bin (then it will just unmap the chunk and sort out next/prev pointers), it will check if the provided chunk is at the end of a bin. If so, the chunk will be de-attributed, then it will iterate backward to find contiguous chunks to de-attribute them. This helps to prevent bin fragmentation.

If the bin ends up being empty, it is de-allocated to reduce the program’s memory footprint.

realloc

When calling realloc, if the size is not too high for a bin (which will be covered in a few lines), it will run a few checks:

If the new size equals the current real size, it will just return the provided pointer.
If the new size is less than the current real size, it will adjust the chunk’s real size and return the provided pointer.
If it is greater than the current real size but less than the chunk’s data size, it will adjust the chunk’s real size and return the provided pointer.

In the two previous cases, if the chunk is at the end of a bin, the chunk will be expanded (if there is enough space left) or trimmed to fit the new size.

If the new size is greater than the chunk’s data size (or bin’s left size if it is at the end of a bin), it will store the chunk’s data in a buffer, free the chunk, call malloc to get a new chunk, and copy the buffer into the new chunk’s data.

Similarly, if the size is too big for a bin, it will try to expand or trim the chunk with mmap. If it works, the chunk’s size and real size are changed accordingly and the provided pointer is returned. If it does not work, it will copy the chunk’s data to the new chunk and return a pointer to the new chunk’s data.

Bonus part code explanation

None of the bonuses really require an explanation, besides eventually de-fragmentation…

Preventing fragmentation is already covered in the mandatory part (to be fair, if one wants to do this bonus, it is recommended to code the mandatory part with de-fragmentation in mind…).

Making the lib thread-safe is not that hard; the easiest implementation is to lock/unlock a mutex before each call of the exposed functions. It could eventually be optimized, but for little to no gain at my scale.

To make it fancier, I added macros to exclude thread-safe logic at build time when not required.

I also added some debug information on show_alloc_mem when building with a specific flag, it prints a dump of the chunks, along with more details about the sizes of the chunks and bins.