How does the free() function work?

[Sharing my answer to the above question on quora]

Assuming the reader is interested in knowing the internal details of free(), I would like to explain in one of the ways I implemented it.

Overall, a free() function releases a chunk of dynamically allocated memory from the heap region of the process address space. It takes a void pointer — starting address of the chunk to be freed.

Before beginning the internal details, let me tell a little bit about the internal data structure maintained and manipulated by calls to malloc, calloc, realloc, free().

Lets keep the performance and other optimizations aside, as the general idea behind any malloc/free implementation will typically remain the same regardless of any sorts of optimizations or improvements.

It is a typical linked-list of blocks. A block is a contiguous region of space usually partitioned into two chunks:

Meta-Data Chunk: This is the very first region. A fixed size space used to maintain the information for the data chunk. In majority of the implementations, following information is stored in this space:

1. Free or allocated – Whether the data chunk is free or allocated.
2. Size of the data chunk.
3. Pointer to the next block or the address of the next block’s meta-data chunk.
4. If allocated, store the starting address of the data chunk that was returned when the space was allocated by some prior call to malloc.

The above information is encapsulated in a struct. Note that this chunk is not writable by users or client applications that make use of dynamic memory allocations. This is purely a part of internal space management data structures.

Data Chunk: This is writable by users or client applications. In other words, address returned by malloc SHOULD always point to the data chunk part of the block and not to the metadata chunk. Size  and other information(referred to as meta-data) about this chunk is stored in the meta-data region/chunk.

For a better understanding, a pictorial representation would be like:

The above diagram shows a linked list of 3 blocks. As mentioned before, each block has two regions for storing meta-data and data respectively, the latter region being writable by the clients of the malloc/calloc/realloc APIs.
The second block is highlighted to depict a free block. Again different implementations might have a separate linked list of free blocks(also known as explicit list based implementation). Let’s not digress from the main topic by going into various approaches and their pros/cons.

The starting address of the data region is what malloc() returns and is then later on passed to free() when the user decides to release the memory for the corresponding data chunk.

Now that we know a little bit about the internal data structures, it is easy to guess that free function just takes in the address of a data chunk and marks the block as free by modifying some sort of a flag in the corresponding meta-data chunk followed by some other bookkeeping type of operations — adding the newly freed block to an explicit list of free blocks etc.

We now need to think about two important things:

1. free() function receives an address of a previously allocated data chunk. This definitely needs to be verified — the address passed into free function SHOULD have been returned by a prior call to malloc.

2. As we need to make some modification to the corresponding meta-data portion of the block, we somehow need to get the address of meta-data chunk i.e the starting address of entire data block.

It is fairly simple to implement these things. In majority of the implementations, size of the meta-data region is referenced using a macro. Let’s name that macro as METADATA_SIZE

As the address is of void type, and is an aligned one(malloc should always return an aligned address), it is safe to cast it to (char *) type. This is basically done to simplify the pointer arithmetic. Assuming the argument passed to free() is void *ptr, we would do:

char * data_chunk_addr = (char *)ptr;
char *metadata_chunk_addr = data_chunk_addr - METADATA_SIZE;

Almost all the implementations will use a “struct” to represent/store the information in meta-data chunk(commonly known as block header).

In my implementation, I had the following struct:

typededef struct block_header
{
    size_t size;
    struct block_header *next;
    struct block_header *previous;
    char start_data_region[1];
} block_header;

The first three fields are pretty much self explanatory. The last field is very important and useful as you will see below.

Now that we have the address of meta-data chunk, just cast it to the block header type.

block_header *data_block = (block_header *)metadata_chunk_addr;

To verify that address passed to free() was really returned by a prior call to malloc, we just need to check:

if(data_block->start_data_region == data_chunk_addr)
{
    /* Valid Address */
    data_block->size  = data_block->size | (0x0001);
}
else
{
    /* Invalid address */
    return or signal error;
}

Other than this, we can also maintain a lookup table to store the addresses returned by malloc. Later during calls to free(), realloc(), hash the address into the lookup table to do the verification. This also looks like a feasible approach,

Note that I am not using a separate field to mark the block as free. Taking the case when the address returned by malloc is always aligned at a 4 byte boundary, the size of the region allocated should also be a multiple of 4. Hence, the lower 2 bits are anyways available to store some meta-data. Hence, I use the LSB to mark the block as free(1) and allocated(0).

Note that this bit won’t count towards the size computations and other internal calculations. So remember to mask off this bit, when dealing with the size of data-chunk.

I hope this gives a fair idea of how free() works.

How does the free() function work?