What is malloc doing, anyway?

malloc has a very nice and simple interface: you ask for a certain amount of memory, and you’re given a void pointer to your block of contiguous bytes that’s been magicked into existence. Once you’re done with it, you call free with the same pointer and the memory disappears into the ether. But what’s actually happening here? Obviously, as we’re running as a userspace program, malloc must be asking the kernel for the memory through syscalls . However, we may be allocating many small blocks, and syscalls are expensive (575 ns for an empty one, as measured below), so some bookkeeping is done in the background. We’ll demonstrate this on GNU libc ( glibc ) with the program snippet below, which calls malloc(16) a thousand times. static void * ptrs [ 1000 ] ; int main ( void ) { for ( int i = 0 ; i < 1000 ; i ++ ) ptrs [ i ] = malloc ( 16 ) ; } Using strace , we can see that the whole loop makes only two brk syscalls: the first asks where the program break is (the address where the process’s heap ends), and the second grows the heap by 132 KiB. These are both done in the first malloc call — the other 999 just take from that already allocated memory. $ strace -e trace = brk,mmap,munmap,write \ ./malloc1000 > /dev/null ... brk(NULL) = 0x59faca231000 brk(0x59faca252000) = 0x59faca252000 +++ exited with 0 +++ You may see both brk and sbrk mentioned in discussions. brk is a syscall that sets the program break to the address it is provided, and sbrk is a libc convenience wrapper that takes a delta , increasing the program break by that amount. The Address Space # A running process gets its own address space , split into a number of regions. These include text for executable code, data for initialised global variables, and bss for uninitialised global variables, among others. The following program prints one address from each region of the process. # define SHOW ( label , p ) \ printf ( "%-22s %p\n" , label , ( void * ) ( p ) ) SHOW ( "main (text)" , main ) ; SHOW ( "initialised (data)" , & initialised ) ; SHOW ( "uninitialised (bss)" , & uninitialised ) ; SHOW ( "malloc(16) (heap)" , malloc ( 16 ) ) ; SHOW ( "program break" , sbrk ( 0 ) ) ; SHOW ( "printf (libc)" , printf ) ; SHOW ( "local (stack)" , & local ) ; The addresses rise from the binary’s code up to its stack. $ ./layout main (text) 0x59c0791d7149 initialised (data) 0x59c0791da020 uninitialised (bss) 0x59c0791da028 malloc(16) (heap) 0x59c0903182b0 program break 0x59c090338000 printf (libc) 0x711dcf7c15b0 local (stack) 0x7ffff86c45ec Some of these regions can change as the program runs. For example, malloc(16) grows the heap and moves the break up. Note that in this run, the break and printf in libc are 23.4 TiB apart, about 1,530 times the machine’s 15.6 GiB of RAM. Nearly all of that range is unmapped, so it costs no physical memory. low high at start text data BSS gap break 23 TiB unmapped libc stack malloc(16) text data BSS gap heap break 23 TiB unmapped libc stack A Toy Allocator with sbrk # Because we can move the program break directly, we can write a little allocator of our own. This is called a bump allocator, because each call simply bumps up the amount of memory that we are allowed to use. void * my_malloc ( size_t size ) { void * p = sbrk ( align_up ( size ) ) ; return p == ( void * ) - 1 ? NULL : p ; } void my_free ( void * ptr ) { ( void ) ptr ; } This allocator is not very good! It moves the break on every single request, and each move is a syscall. We can time a syscall against malloc to see why malloc requests large blocks from the kernel and cuts them up itself. Each of the following three functions is timed over a million calls. static void * volatile sink ; static void call_getppid ( void ) { syscall ( SYS_getppid ) ; } static void call_sbrk ( void ) { sink = sbrk ( 16 ) ; } static void call_malloc ( void ) { sink = malloc ( 16 ) ; } sbrk(16) costs only 35 ns more than the empty syscall, whereas malloc(16) runs 22.7 times faster than sbrk(16) . $ ./syscall-cost syscall(SYS_getppid) 575.2 ns per call sbrk(16) 610.1 ns per call malloc(16) 26.9 ns per call sbrk(16) / malloc(16) 22.7x The bump allocator also has no way to reuse freed memory. Each request lands straight after the one before, so in the following example, d goes after c even though b has been freed. $ ./my-bump-1 a = my_malloc(16) start+0 b = my_malloc(1) start+16 c = my_malloc(100) start+32 my_free(b) d = my_malloc(1) start+144 break start+160 The rest of the post improves the allocator one stage at a time. Chunks and Headers # malloc actually allocates more memory than you request. This is because each allocation, or chunk , has a size header just before the returned pointer; this is how free works without passing an explicit size. Chunk sizes are always multiples of 16, so the low bits of the size are always zero, and glibc keeps three flags in them. header 24 bytes for the caller header p = malloc(24) next chunk chunk : 32 bytes size = 32 0 A 0 M 1 P one 8-byte word A : another arena M : own mapping P : chunk before in use size_t requests [ ] = { 1 , 24 , 25 , 1000 } ; size_t count = sizeof requests / sizeof requests [ 0 ] ; for ( size_t i = 0 ; i < count ; i ++ ) { char * p = malloc ( requests [ i ] ) ; size_t chunk = ( ( size_t * ) p ) [ - 1 ] & ~ ( size_t ) 7 ; printf ( "%8zu %8zu\n" , requests [ i ] , chunk ) ; } Each chunk is the request plus 8 bytes for the header, rounded up to a multiple of 16, with a minimum of 32. The rounding keeps every pointer that malloc returns 16-byte aligned, which is the alignment x86-64 gives max_align_t , so the memory suits any C type. The 32-byte minimum leaves room for the list pointers that a chunk stores once it is freed. $ ./chunk-header request chunk 1 32 24 32 25 48 1000 1008 When we free a chunk, it is put into what’s called a free list to allow reuse. When more data is requested, malloc looks through this free list and splits large chunks to fit small requests, and free merges free neighbours back together. Each chunk in the free list needs two pieces of information: its size (which we already have), and a pointer to the next chunk in the free list. glibc stores the pointer after the size, reusing the memory that the user stored their data in before it was freed! The toy allocator stores the same two fields in each chunk. typedef struct chunk { size_t size ; struct chunk * next ; } chunk_t ; Splitting and Coalescing # We can improve our my_malloc by rounding the request plus its header up to a multiple of 16 bytes, and taking the first chunk in the free list that is big enough. To keep things simple, the toy’s header is the whole chunk_t , so a chunk keeps room for next even while it is in use. That makes the header 16 bytes where glibc ’s is 8, and my_malloc(100) takes a 128-byte chunk where malloc(100) takes 112. void * my_malloc ( size_t size ) { size_t need = align_up ( size + HEADER_SIZE , ALIGN ) ; for ( chunk_t * * link = & free_list ; * link != NULL ; link = & ( * link ) -> next ) if ( ( * link ) -> size >= need ) return take ( link , need ) ; if ( grow_heap ( need ) != 0 ) return NULL ; return my_malloc ( size ) ; } We define take to split that chunk, leaving whatever the request does not need in t