How a C allocator packs the allocated flag into a block size

A block header zoomed to show the lowest metadata bit distinguished from the grouped block-size bits, with the remaining payload shown beside it.

A C allocator can store a block’s size and its allocated/free state in one header word when every block span is aligned: alignment makes the low size bits zero, so a flag can use one of them. For 16-byte-aligned blocks, a span of 80 bytes is 0x50; setting the low bit produces 0x51, and masking the low four bits recovers the span.

Why can an allocator store a flag in the block size?

A block span is the total number of bytes in a block, including its metadata and padding. If every span is a multiple of 16, its hexadecimal representation ends in 0, and its lowest four binary bits are zero. One of those spare bits can record whether the block is allocated, without adding another word.

This is a representation choice, not a requirement of C or of every allocator. The format works only if the allocator enforces the alignment rule that leaves those bits available. The CS:APP implicit-block diagram shows the familiar size-and-allocation-bit header.

Pack and unpack a 16-byte-aligned span

Suppose the allocator uses 16-byte block spans and stores the total span with an allocation flag in the low bit. Since 16 is a power of two, the lowest four bits of each valid span are zero.

For an 80-byte span:

  • Free: 80 is 0x50.
  • Allocated: 0x50 | 0x1 is 0x51.
  • Decode the state with word & 0x1.
  • Recover the span with word & ~0xF.

In C, the essential operations on an unsigned header word can look like this:

#include <stdbool.h>
#include <stddef.h>

size_t h = 80;
bool a = true;
if (a) h |= 1;

bool used = (h & 1) != 0;
size_t span = h & ~(size_t)0xF;

This example assumes the input block span has already been checked as a multiple of 16, and the flag has no other bits set. The mask clears all four low bits; the state test reads only bit zero. Use an unsigned type for the packed word and masks so the bit operations have the intended unsigned behavior.

What must stay true for the packed header to work?

Keep the alignment invariant true for every block, not just the first. If a split produces a span that is not a multiple of 16, the next header is misaligned and the size bits can overlap the flag. Round each complete block span—including header footprint and padding—before placing the next block. See how payload offset and block span alignment work separately.

Validate a decoded span before using it to walk the arena. It must be large enough for a valid block and no larger than the remaining arena. Otherwise corrupted flag or size bits can turn the next-block calculation into an out-of-bounds walk.

Also, a bit mask only decodes an integer value. It does not make an arbitrary address aligned, or make a cast from byte storage to size_t * valid C. The header’s actual access still has to satisfy the chosen storage, alignment and object rules. The small allocator design walkthrough uses separate logical span and state fields as a simpler alternative.

When should you use a packed size-and-state word?

Packing is useful when an allocator controls the block-span alignment and wants a compact header. Keeping size and state as separate fields is easier to inspect and can be clearer in an early teaching implementation. Boundary tags, free-list links and other flags add their own space and invariants; they do not come for free just because the allocation bit fits in a low bit.

Use the packed form only after writing down the exact block-span alignment, the mask for all reserved low bits, and the range checks for decoded spans. Then test both values—allocated and free—at the smallest and largest valid spans, plus a split that leaves a new block at the next aligned boundary.

How a C allocator packs the allocated flag into a block size · Heapcraft