How free Recovers a Size From a Bare Pointer

The signature of free is void free(void *ptr). No length, no size, no handle. Yet the allocator must know exactly how many bytes to return to its free structures, which class list to push the block onto, and which neighbours to coalesce with. Everything it needs has to be recoverable from the pointer alone. That constraint shapes the entire layout of a heap, and it explains why certain apparently reasonable allocation APIs cannot be layered on top of a standard one.

Metadata in front of the payload

The conventional solution places a header immediately before the returned pointer, holding at least the block size. Recovery is then a fixed negative offset:

struct header {
    size_t size;   /* block size, low bits used as flags */
    size_t pad;    /* keeps the header one full alignment unit */
};

/* Returns the block start and stores its extent in *bytes_out. */
struct header *block_of(void *ptr, size_t *bytes_out)
{
    /* ptr is the payload; the header begins sizeof(struct header) bytes earlier */
    struct header *h = (struct header *)ptr - 1;
    *bytes_out = h->size & ~(size_t)7;
    return h;
}

This works only because malloc guarantees that the returned pointer is aligned to alignof(max_align_t), which is 16 bytes on the common 64-bit ABIs, and the header occupies exactly one such unit. Subtracting 16 bytes from a 16-aligned pointer lands on the header’s own 16-aligned address, which is where the allocator placed it, and the size field it reads there is naturally aligned as well. A 12-byte header would leave the payload 4 bytes off a 16-byte boundary, so the implementation would have to insert 4 bytes of padding ahead of the payload; that padding counts as part of the header for the arithmetic, and the offset returns to 16.

The alignment guarantee does double duty. It is what the C standard requires of the returned pointer, and it is simultaneously the invariant the allocator relies on to find its own metadata. Any implementation that returns a pointer not aligned to the header granularity breaks free for every caller, not just the misaligned one.

Where the header sits relative to the payload also determines how an overflow is expressed. A write past the end of a buffer hits whatever follows; a write before the start, usually an underflow from a negative index, hits the size field. Both are memory corruption, but the second is more damaging because it corrupts the allocator’s own view of the block, and the resulting merge can hand out overlapping regions.

Size classes remove the need for a size field

An allocator with size classes can drop the per-block size entirely for small objects. If every object in a span is the same size, and the pointer identifies the span, then the block size is a property of the span, not of the block. The page metadata holds the object size and the offset of the span’s base, and the free path computes:

size_t off  = (char *)ptr - span->base;    /* byte offset within the span */
size_t idx  = off / span->obj_size;        /* object index */

No per-object header at all. That is why some allocators return pointers with zero bytes of overhead for small classes: the metadata has moved to a table indexed by page, and the table entry is amortised over every object in the span. The cost is the lookup, a page-table-style mapping from address to span descriptor, which must be fast because it is on the free path as well as the allocation path.

The lookup is usually a two-level radix over the address space, or a hash of the page number, and its cost is a few memory accesses. Those accesses are to a table that is itself cache-resident for hot regions, so the amortised cost is low, but it is not zero, and it is the reason the header-based approach survives in allocators that favour simplicity.

The over-aligned case that cannot be reconstructed

C++17 introduced aligned allocation: operator new(size_t, align_val_t) and the matching operator delete(void *, align_val_t). The alignment is passed to the delete as well, which is a deliberate admission that the allocator cannot always recover what it needs from the pointer alone: for an over-aligned allocation the returned pointer need not sit at a fixed offset from any header the allocator placed.

Consider a request for 4096-byte alignment. The allocator obtains a page-aligned region and returns a pointer at the region’s start; the header, if any, must live elsewhere, because the bytes before the payload belong to the previous page. Implementations therefore keep a separate map from aligned pointer to the original allocation, or store the original pointer in a slot immediately before the payload, but only when the alignment leaves room, which it does not for page alignment on a page boundary.

C’s aligned_alloc and POSIX’s posix_memalign face the same problem with a different resolution: free is called with only the pointer, so the implementation must have arranged at allocation time for recovery to be possible. The common technique over-allocates and leaves a back-pointer in the word immediately before the aligned payload, where the alignment leaves room for one. When it does not, as with page alignment on a page boundary, the allocation must be served from a page-aligned mapping so that the block start and the payload coincide.

raw:      [ ......... usable ......... ]
aligned:        ^ payload, at raw + delta
                delta <= align - 1, and (raw + delta) % align == 0

Recovery from a back-pointer is a single load at a fixed displacement. Recovery from a page mapping is arithmetic on the page base. The two cases are different enough that an allocator usually routes aligned requests above the page size to the mapping path rather than trying to make one formula cover both. Getting the arithmetic wrong in either case produces a pointer into the middle of the block, which free will then merge incorrectly.

What the contract does and does not guarantee

The C standard requires that free accept a pointer returned by malloc, calloc, or realloc, and that it accept a null pointer as a no-op. It does not require free to accept a pointer that was not returned by those functions, and doing so is undefined behaviour. Every allocator therefore has a choice about what to do with a foreign pointer: crash, corrupt, or check.

Checking costs. A full validity check would verify that the pointer lies within a managed region, that it is aligned to the class granularity, and that the block it points into is marked allocated, which requires reading metadata that a use-after-free may already have overwritten. Debug allocators do all of this and quarantine freed blocks so a second free is detected. Release allocators do less, because the checks are on the hottest path in the program.

The same gap explains why some interfaces take the old size at deallocation. Given only a pointer, a growing reallocation needs the old extent to know how many bytes to carry over and whether the block can be extended in place. Header-based allocators recover it; class-based allocators recover it from the span; an allocator that stores no size anywhere cannot implement realloc without the caller supplying the length. This is the reason some interfaces require a size on free: it moves the recovery problem to the caller, at the cost of a footgun when the size is wrong.

Degenerate inputs and their symptoms

A few cases recur across implementations.

A double free pushes the same block onto a free list twice, so two later allocations return the same address. With a singly linked free list the second push writes a pointer into the block that the first allocation may already be using, and the corruption appears in the application’s data rather than in the allocator’s. Allocators that keep a bitmap of allocation state per span can detect this in a few instructions; those that do not rely on the corruption being noticed elsewhere.

A free of a pointer interior to a block, such as free(p + 8), computes a header at an address that is not the block’s start, reads a size that is actually payload data, and merges nonsense. The symptom is usually a crash in the allocator’s coalescing path, far from the offending call.

A free after the heap has been trimmed or released touches unmapped memory and faults. This is the benign case: the program dies at the site of the bug rather than corrupting silently, which is why some hardened allocators deliberately unmap freed large blocks.

Zero-size allocations are implementation-defined: malloc(0) may return a unique pointer that must be freed, or null. Both are conforming, and code that assumes one behaviour is non-portable. An allocator that rounds zero up to the minimum block size will return a valid pointer; one that returns null makes free(NULL) the required cleanup, which is a no-op.

The unifying point is that free’s one-argument signature forces the allocator to encode ownership and extent in memory adjacent to the object or in tables indexed by address. Which of those it chooses determines its overhead per allocation, its speed on the free path, and the kinds of corruption that turn a small bug into a heap-wide failure. That is the subject of hardening. The alternative, passing sizes explicitly, appears in C++‘s sized deallocation and in arena interfaces that take a size for accounting; it removes the recovery problem and adds an obligation on the caller that the compiler cannot verify.