How does free work in C? • CodeFade

How does `free` work in C?

If you’ve worked in C and ever dynamically allocated memory, you’ve probably used malloc and free calls. You put in the amount of memory to be allocated in the malloc function, it allocates the memory and returns back the starting address of the allocated memory that you store in a pointer variable. Something like this

void *address = malloc(512);

Before we understand how free works, we need to quickly look into how does malloc allocates memory. When you call malloc with size 512 (say), it will find a place in heap which is atleast 512 bytes wide, mark it as allocated and return the address of the allocated memory. The heap is just a block of memory allocated to the process that maps to an address range. Let’s take the following simple program

#include<stdio.h>
#include<stdlib.h>

int main() {
   int total_size = 512;
   void* first = (void*)malloc(total_size);
   printf("First Address: 0x%x\n", first );
   void* second = (void*)malloc(total_size);
   printf("Second Address: 0x%x\n", second );
   return 0;
}
// Output:
// First Address: 0x602010
// Second Address: 0x602220

If you run this program in gdb and look at the memory map using info proc map, you can see that this address belongs to an address range that’s in the heap region.

Start Addr         End Addr       Size     Offset objfile
  0x602000         0x623000    0x21000        0x0  [heap]

The first address does not start from the address 0x602000 instead there is some space ( 16 bits ) before it. Similarly, the next allocated address 0x602220 should be 0x602010 + 512 but it’s not, it’s 0x602010 + 512 + 16. These extra 2 bytes is where allocation information is stored and while calling free, this information is utilized to free correct amount of memory. This block is called the header for the allocated memory chunk.

Let’s look at this metadata stored in the previous 2 bytes.

(gdb) x /8 0x602000
0x602000:       0x00000000      0x00000000      0x00000211      0x00000000
0x602010:       0x00000000      0x00000000      0x00000000      0x00000000

The byte just before 0x602010 has the value 0x211 which represents the size of the chunk allocated. Let’s ignore the last bit for a second. If you add, 0x602010 + 0x210, it gives you the address of the next allocated chunk, i.e. 0x602220. The last bit represents that block is allocated. When you call free on this chunk (0x602010), the value in the meta data is changed to 0x210 which means that this block of size 0x210 is free to be allocated again.

This linked list of dynamically allocated memory is called free list. We iterate this list to find out the which chunk is allocated and which chunk is free. There can be various methods to implement free depending upon the allocator. One can write a custom allocator with a different free implementation with better time/space efficiency. Maybe I’ll write an article on that too 😇.