post-mortem · custom_mem_alloc · C, pthreads · 3 pages
The Block That Was Too Small to Free
an intrusive free list stores its next pointer inside the freed block. ask it for four bytes and the pointer does not fit, so freeing corrupts the block next door.
abstract
It presented as a double free, it was reported at a point in the program unrelated to the actual fault, and the root cause was that I had never asked what happens when a caller requests fewer bytes than my own bookkeeping needs to occupy. The fix is two lines. Finding it was not.
the symptom
A test program allocating and freeing mixed sizes in a loop would segfault, but not at the same iteration twice, and sometimes not at all. The stack trace always pointed inside my free list traversal, on the line that follows a next pointer.
root cause
The free list is intrusive: a free block stores the address of the next free block inside its own payload. A caller asks for four bytes, gets four bytes, and frees them. free casts that payload to a node pointer and writes eight bytes into it. The other four land in the header of the physically adjacent block. A block never corrupts itself, it corrupts its neighbour, and the neighbour does not complain until something traverses it.
the fix
Enforce a floor of sizeof(free_node) on every allocation before aligning, not after. Splitting follows the same rule: only split if the remainder is still large enough to be a legal free block. The wider lesson is that intrusive containers impose a minimum element size that belongs to the container, not to the caller.