Double Free and the Integrity of Free Lists

A free list is a linked list threaded through the free blocks themselves, and that single design decision is the root of the double-free problem. Because the links live inside the blocks rather than in a separate array, inserting a block into the list means writing to the block’s first sixteen bytes. When the block is already on a list, because it was freed twice or because the program freed a pointer it had already returned, those same bytes are being used as links by the list traversal. The insertion overwrites them with new values, and the list’s shape changes.

Nothing about the second free call is distinguishable from the first at the interface level. The allocator receives a pointer and must decide whether the pointer denotes a block it can release. The cheap answer is to trust it; the safe answer requires knowing the block’s state, which means keeping state somewhere the caller cannot reach.

Insertion is a write into the block

A simple explicit free list stores two pointers in each free block: forward and backward. Removal is a two-store operation that patches the two neighbours’ link fields, and insertion at the head is four stores when the list is non-empty: two to set the new node’s link fields, one to repoint the old head’s back link, and one to install the new head.

struct free_block {
    struct free_block *next;
    struct free_block *prev;
};

void list_push(struct free_block **head, struct free_block *b)
{
    b->prev = NULL;
    b->next = *head;
    if (*head)
        (*head)->prev = b;    /* the old head now points back at b */
    *head = b;
}

If b is already in the list, the second call does not remove it from its old position. Its old neighbours still point at it, but its prev and next now describe a different place in the list. The result is a list with a node reachable from two paths, or a cycle, or a node whose prev pointer names a block that is not actually its predecessor. Which of these occurs depends on the list’s length and on where the block was, so the failure is state-dependent rather than deterministic.

The dangerous case is the interaction with allocation. After the double free, two malloc calls can return the same address, because the doubly-linked block is reachable twice. The program then holds two live pointers to one block, which is exactly the aliasing that a use-after-free produces, except that here it is produced without any stale pointer at all: both pointers are returned by malloc and both are, by the allocator’s contract, valid.

If the block was reallocated between the two frees, the situation is worse. The second free inserts a block that is currently owned by a live object. The allocator’s metadata now says the block is free while the program writes through its pointer. A subsequent allocation splits it, and the live object’s payload becomes part of another object.

Size fields and the overlapping-chunk check

Consolidation is the second path by which a double free damages state. On free, the allocator examines the flags in the neighbouring chunks’ size fields to decide whether to merge. If a block was freed twice and reallocated in between, the block released as a neighbour may already belong to a live object, so the merge joins an in-use payload into a free chunk and the resulting chunk’s size covers memory it does not own.

Modern glibc checks this explicitly. Before consolidating, the allocator computes the boundaries implied by the size fields and verifies that the next chunk’s prev_size agrees with the current chunk’s size, and that the next chunk’s size is a plausible value. A mismatch is reported as a corrupted or double-linked list, and the process aborts. These checks were introduced in response to the exploitation techniques that used precisely this inconsistency, and they are why a double free in current glibc usually produces a deterministic abort rather than a silent corruption.

The check is a consistency test on a data structure, not a proof of correctness. It catches inconsistencies the allocator can see from the block it is working on; a double free whose consequences are confined to a size class that never consolidates, or one that happens after the block has been reallocated and rewritten into a self-consistent state, can pass.

Fast paths that trade detection for speed

The per-thread cache adds a layer that is faster and, by design, less checked. A small array of singly linked free lists, one per size class, held without locks in thread-local storage. Allocation pops the head; free pushes onto the head. The link is stored in the first word of the freed block, and because the cache is per-thread and the blocks are never merged while they are in it, no neighbouring metadata is consulted.

/* Shape of a per-thread cache push, as allocators implement it. */
struct tcache { void *head[64]; };     /* one list per size class */

static void tcache_push(struct tcache *tc, void *p, unsigned cls)
{
    *(void **)p = tc->head[cls];       /* link stored in the block's first word */
    tc->head[cls] = p;
}

Two consequences follow. First, the second free of a block that is still in the cache pushes it onto the list a second time, and the list now has a cycle: the block’s link points at itself, or at a block that points back at it. The cache has a fixed small capacity per size class, so an allocation-heavy sequence can fill it, but the cycle exists as soon as the double push happens. Second, the link is stored at the very start of the block, which means a double free overwrites whatever the first word of the payload held, frequently a vtable pointer or a length field of the object that used to live there.

Implementations defend with a key. The stored link is not the raw pointer but the pointer exclusive-ORed with a value derived from the address of the slot that holds it, so a forged link has to know both the target address and the location the link will be read from. A second word holds the cache’s own identity, and a push of a block that already carries that identity is rejected as a double free; the check is a single comparison.

Detecting the second release

Because the allocator is the only component that knows a block’s state, detection belongs there, and there are three viable places to keep the state.

The first is in the block. A freed block can carry a marker in a field the allocator controls. The marker is not foolproof, since a stale write can restore it, but it converts the common double free into an immediate report. The marker has to live where the program cannot legitimately write after the free, which in practice means inside the allocator’s header rather than the payload.

The second is out of band. A bitmap or a hash set of freed addresses, consulted on every free, is exact while it is accurate, and its accuracy depends on clearing an entry the moment the address is handed out again: an entry that survives reallocation makes the next legitimate free of that block look like a second release. An allocator that sees both allocation and deallocation can maintain the set at one update per operation; a layer that observes only frees cannot, and can drop an entry only when the address leaves the allocator’s control entirely. The bookkeeping then grows with the allocation rate, which is why the check is usually confined to a debug configuration.

The third is instrumentation. A tool that tracks every allocation and free can report the second release with a stack trace for both, which is what a debugger needs. The shadow-memory checkers implement this by marking freed regions as poisoned in a side table: the second free sees the poison and reports, and so does any access in between.

Why the caller’s discipline is not enough

The usual advice is to set the pointer to null after freeing, which turns the second free into a free of null, which is defined as a no-op. It works for the single-owner case and fails for every other one. Aliased pointers mean two variables name the block; clearing one leaves the other dangling. A pointer stored in a structure that outlives the function cannot be cleared by the function. A container that frees its elements on destruction, and a caller that frees an element it borrowed, produce a double free with no single place to insert the null assignment.

Ownership discipline in the type system removes the possibility, as the ownership discussion describes, because a value that has been moved cannot be used again. For code that must keep manual management, the allocator’s own checks are the practical layer: they cannot repair the program, but they turn a silent aliasing into a crash at the point of the second release, which is a bug report rather than an exploit primitive. The pattern repeats across these mechanisms: the allocator knows more about a block than the caller does, so the checks that work are the ones placed where that knowledge lives.