FA-90478 / Garbage collector invariants / Member archive

Free-list sweep: exact fits skipped · case 03

A request that exactly matches a free block is served from a later, larger block.

Member previewVariant 3 · 3 implementations · 6 checks per implementation

Case contract

blocks are [address, size, marked] covering the heap in any order. Sweep in address order: unmarked blocks become free and physically adjacent free blocks coalesce. Then serve requests first-fit in address order: round the request up to 8 bytes; split the chosen block when the remainder is at least 16 bytes (the allocation takes the low end), otherwise hand out the whole block; no fit yields None. Return the swept free list (as it was right after sweeping), the allocation addresses and the final free list.

Why this case matters

Sweepers and free-list allocators must keep block boundaries exact or they hand out overlapping memory.

One recorded failure

Sample boundary fixture

This sample comes from the broken implementation of a controlled reproducer.

Boundary fixture	Actual	Expected	Outcome
regression: sweep, split and exhaust	`{"alloc": [3088, 3144, null, 3112, 3168], "free": [[3176, 32]], "swept": [[3088, 48], [3144, 64]]}`	`{"alloc": [3088, 3112, 3144, 3184, null], "free": [], "swept": [[3088, 48], [3144, 64]]}`	Failed

MEMBER ARCHIVE

The complete case is available to members.

This record includes three runnable implementations, regression fixtures, execution results, and source hashes.

Member access is invitation-based. Sign in with your invited account to inspect the sources.