FA-90456 / Garbage collector invariants / Open access
Free-list sweep: free blocks merged across live blocks · case 01
Coalesced free blocks swallow live objects that sit between them.
ROOT CAUSE
Coalescing only checks that the previous free block ends at or before the current block.
VERIFIED REPAIR
Merge only when the previous free block ends exactly where this block starts.
Unsuccessful approach: Using the current block's size to test adjacency fails whenever neighbouring sizes differ.
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.
1 / The failure
Exit 1"""Failure Map reference implementation. Python standard library only."""
import json
N = 1
observations = []
def solve(blocks, requests):
free = []
for addr, size, marked in sorted(blocks):
if marked:
continue
if free and free[-1][0] + free[-1][1] <= addr:
free[-1][1] += size
else:
free.append([addr, size])
swept = [list(b) for b in free]
got = []
for req in requests:
need = (req + 7) // 8 * 8
choice = None
for b in free:
if b[1] >= need:
choice = b
break
if choice is None:
got.append(None)
continue
got.append(choice[0])
rem = choice[1] - need
if rem >= 16:
choice[0] += need
choice[1] = rem
else:
free.remove(choice)
return {'swept': swept, 'alloc': got, 'free': free}
def check(label, actual, expected):
observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = [[('regression: sweep, split and exhaust',
([[1088, 8, True],
[1040, 32, False],
[1024, 16, True],
[1072, 16, False],
[1096, 24, False],
[1120, 40, False],
[1160, 16, True]],
[20, 24, 40, 10, 8]),
{'alloc': [1040, 1064, 1096, 1136, None], 'free': [], 'swept': [[1040, 48], [1096, 64]]}),
('exact fit uses the first block',
([[1088, 8, True],
[1040, 32, False],
[1024, 16, True],
[1072, 16, False],
[1096, 24, False],
[1120, 40, False],
[1160, 16, True]],
[48, 64]),
{'alloc': [1040, 1096], 'free': [], 'swept': [[1040, 48], [1096, 64]]}),
('remainder of exactly the minimum block size',
([[1088, 8, True],
[1040, 32, False],
[1024, 16, True],
[1072, 16, False],
[1096, 24, False],
[1120, 40, False],
[1160, 16, True]],
[32, 40]),
{'alloc': [1040, 1096], 'free': [[1072, 16], [1136, 24]], 'swept': [[1040, 48], [1096, 64]]}),
('remainder too small to split',
([[1088, 8, True],
[1040, 32, False],
[1024, 16, True],
[1072, 16, False],
[1096, 24, False],
[1120, 40, False],
[1160, 16, True]],
[44, 50, 1]),
{'alloc': [1040, 1096, None], 'free': [], 'swept': [[1040, 48], [1096, 64]]}),
('sweep snapshot is independent of allocation',
([[1088, 8, True],
[1040, 32, False],
[1024, 16, True],
[1072, 16, False],
[1096, 24, False],
[1120, 40, False],
[1160, 16, True]],
[1]),
{'alloc': [1040], 'free': [[1048, 40], [1096, 64]], 'swept': [[1040, 48], [1096, 64]]}),
('control: fully marked heap',
([[1024, 32, True], [1056, 16, True]], [8]),
{'alloc': [None], 'free': [], 'swept': []})],
[('regression: sweep, split and exhaust',
([[2112, 8, True],
[2064, 32, False],
[2048, 16, True],
[2096, 16, False],
[2120, 24, False],
[2144, 40, False],
[2184, 16, True]],
[20, 24, 40, 10, 8]),
{'alloc': [2064, 2088, 2120, 2160, None], 'free': [], 'swept': [[2064, 48], [2120, 64]]}),
('exact fit uses the first block',
([[2112, 8, True],
[2064, 32, False],
[2048, 16, True],
[2096, 16, False],
[2120, 24, False],
[2144, 40, False],
[2184, 16, True]],
[48, 64]),
{'alloc': [2064, 2120], 'free': [], 'swept': [[2064, 48], [2120, 64]]}),
('remainder of exactly the minimum block size',
([[2112, 8, True],
[2064, 32, False],
[2048, 16, True],
[2096, 16, False],
[2120, 24, False],
[2144, 40, False],
[2184, 16, True]],
[32, 40]),
{'alloc': [2064, 2120], 'free': [[2096, 16], [2160, 24]], 'swept': [[2064, 48], [2120, 64]]}),
('remainder too small to split',
([[2112, 8, True],
[2064, 32, False],
[2048, 16, True],
[2096, 16, False],
[2120, 24, False],
[2144, 40, False],
[2184, 16, True]],
[44, 50, 1]),
{'alloc': [2064, 2120, None], 'free': [], 'swept': [[2064, 48], [2120, 64]]}),
('sweep snapshot is independent of allocation',
([[2112, 8, True],
[2064, 32, False],
[2048, 16, True],
[2096, 16, False],
[2120, 24, False],
[2144, 40, False],
[2184, 16, True]],
[1]),
{'alloc': [2064], 'free': [[2072, 40], [2120, 64]], 'swept': [[2064, 48], [2120, 64]]}),
('control: fully marked heap',
([[2048, 32, True], [2080, 16, True]], [8]),
{'alloc': [None], 'free': [], 'swept': []})],
[('regression: sweep, split and exhaust',
([[3136, 8, True],
[3088, 32, False],
[3072, 16, True],
[3120, 16, False],
[3144, 24, False],
[3168, 40, False],
[3208, 16, True]],
[20, 24, 40, 10, 8]),
{'alloc': [3088, 3112, 3144, 3184, None], 'free': [], 'swept': [[3088, 48], [3144, 64]]}),
('exact fit uses the first block',
([[3136, 8, True],
[3088, 32, False],
[3072, 16, True],
[3120, 16, False],
[3144, 24, False],
[3168, 40, False],
[3208, 16, True]],
[48, 64]),
{'alloc': [3088, 3144], 'free': [], 'swept': [[3088, 48], [3144, 64]]}),
('remainder of exactly the minimum block size',
([[3136, 8, True],
[3088, 32, False],
[3072, 16, True],
[3120, 16, False],
[3144, 24, False],
[3168, 40, False],
[3208, 16, True]],
[32, 40]),
{'alloc': [3088, 3144], 'free': [[3120, 16], [3184, 24]], 'swept': [[3088, 48], [3144, 64]]}),
('remainder too small to split',
([[3136, 8, True],
[3088, 32, False],
[3072, 16, True],
[3120, 16, False],
[3144, 24, False],
[3168, 40, False],
[3208, 16, True]],
[44, 50, 1]),
{'alloc': [3088, 3144, None], 'free': [], 'swept': [[3088, 48], [3144, 64]]}),
('sweep snapshot is independent of allocation',
([[3136, 8, True],
[3088, 32, False],
[3072, 16, True],
[3120, 16, False],
[3144, 24, False],
[3168, 40, False],
[3208, 16, True]],
[1]),
{'alloc': [3088], 'free': [[3096, 40], [3144, 64]], 'swept': [[3088, 48], [3144, 64]]}),
('control: fully marked heap',
([[3072, 32, True], [3104, 16, True]], [8]),
{'alloc': [None], 'free': [], 'swept': []})],
[('regression: sweep, split and exhaust',
([[4160, 8, True],
[4112, 32, False],
[4096, 16, True],
[4144, 16, False],
[4168, 24, False],
[4192, 40, False],
[4232, 16, True]],
[20, 24, 40, 10, 8]),
{'alloc': [4112, 4136, 4168, 4208, None], 'free': [], 'swept': [[4112, 48], [4168, 64]]}),
('exact fit uses the first block',
([[4160, 8, True],
[4112, 32, False],
[4096, 16, True],
[4144, 16, False],
[4168, 24, False],
[4192, 40, False],
[4232, 16, True]],
[48, 64]),
{'alloc': [4112, 4168], 'free': [], 'swept': [[4112, 48], [4168, 64]]}),
('remainder of exactly the minimum block size',
([[4160, 8, True],
[4112, 32, False],
[4096, 16, True],
[4144, 16, False],
[4168, 24, False],
[4192, 40, False],
[4232, 16, True]],
[32, 40]),
{'alloc': [4112, 4168], 'free': [[4144, 16], [4208, 24]], 'swept': [[4112, 48], [4168, 64]]}),
('remainder too small to split',
([[4160, 8, True],
[4112, 32, False],
[4096, 16, True],
[4144, 16, False],
[4168, 24, False],
[4192, 40, False],
[4232, 16, True]],
[44, 50, 1]),
{'alloc': [4112, 4168, None], 'free': [], 'swept': [[4112, 48], [4168, 64]]}),
('sweep snapshot is independent of allocation',
([[4160, 8, True],
[4112, 32, False],
[4096, 16, True],
[4144, 16, False],
[4168, 24, False],
[4192, 40, False],
[4232, 16, True]],
[1]),
{'alloc': [4112], 'free': [[4120, 40], [4168, 64]], 'swept': [[4112, 48], [4168, 64]]}),
('control: fully marked heap',
([[4096, 32, True], [4128, 16, True]], [8]),
{'alloc': [None], 'free': [], 'swept': []})],
[('regression: sweep, split and exhaust',
([[5184, 8, True],
[5136, 32, False],
[5120, 16, True],
[5168, 16, False],
[5192, 24, False],
[5216, 40, False],
[5256, 16, True]],
[20, 24, 40, 10, 8]),
{'alloc': [5136, 5160, 5192, 5232, None], 'free': [], 'swept': [[5136, 48], [5192, 64]]}),
('exact fit uses the first block',
([[5184, 8, True],
[5136, 32, False],
[5120, 16, True],
[5168, 16, False],
[5192, 24, False],
[5216, 40, False],
[5256, 16, True]],
[48, 64]),
{'alloc': [5136, 5192], 'free': [], 'swept': [[5136, 48], [5192, 64]]}),
('remainder of exactly the minimum block size',
([[5184, 8, True],
[5136, 32, False],
[5120, 16, True],
[5168, 16, False],
[5192, 24, False],
[5216, 40, False],
[5256, 16, True]],
[32, 40]),
{'alloc': [5136, 5192], 'free': [[5168, 16], [5232, 24]], 'swept': [[5136, 48], [5192, 64]]}),
('remainder too small to split',
([[5184, 8, True],
[5136, 32, False],
[5120, 16, True],
[5168, 16, False],
[5192, 24, False],
[5216, 40, False],
[5256, 16, True]],
[44, 50, 1]),
{'alloc': [5136, 5192, None], 'free': [], 'swept': [[5136, 48], [5192, 64]]}),
('sweep snapshot is independent of allocation',
([[5184, 8, True],
[5136, 32, False],
[5120, 16, True],
[5168, 16, False],
[5192, 24, False],
[5216, 40, False],
[5256, 16, True]],
[1]),
{'alloc': [5136], 'free': [[5144, 40], [5192, 64]], 'swept': [[5136, 48], [5192, 64]]}),
('control: fully marked heap',
([[5120, 32, True], [5152, 16, True]], [8]),
{'alloc': [None], 'free': [], 'swept': []})]]
for label, args, expected in cases[N - 1]:
check(label, solve(*args), expected)
print(json.dumps({"observations": observations, "passed": all(x["passed"] for x in observations)}, ensure_ascii=False))
raise SystemExit(0 if all(x["passed"] for x in observations) else 1)
| Boundary fixture | Actual | Expected | Outcome |
|---|---|---|---|
| regression: sweep, split and exhaust | {'alloc': [1040, 1064, 1088, 1128, None], 'free': [], 'swept': [[1040, 112]]} | {'alloc': [1040, 1064, 1096, 1136, None], 'free': [], 'swept': [[1040, 48], [1096, 64]]} | Failed |
| exact fit uses the first block | {'alloc': [1040, 1088], 'free': [], 'swept': [[1040, 112]]} | {'alloc': [1040, 1096], 'free': [], 'swept': [[1040, 48], [1096, 64]]} | Failed |
| remainder of exactly the minimum block size | {'alloc': [1040, 1072], 'free': [[1112, 40]], 'swept': [[1040, 112]]} | {'alloc': [1040, 1096], 'free': [[1072, 16], [1136, 24]], 'swept': [[1040, 48], [1096, 64]]} | Failed |
| remainder too small to split | {'alloc': [1040, 1088, None], 'free': [], 'swept': [[1040, 112]]} | {'alloc': [1040, 1096, None], 'free': [], 'swept': [[1040, 48], [1096, 64]]} | Failed |
| sweep snapshot is independent of allocation | {'alloc': [1040], 'free': [[1048, 104]], 'swept': [[1040, 112]]} | {'alloc': [1040], 'free': [[1048, 40], [1096, 64]], 'swept': [[1040, 48], [1096, 64]]} | Failed |
| control: fully marked heap | {'alloc': [None], 'free': [], 'swept': []} | {'alloc': [None], 'free': [], 'swept': []} | Passed |
SHA-256 / 796ccecbb9cfe5259a1d6badc54c4069699c8320b3706383562e36c50a599ef5
2 / The unsuccessful fix
Exit 1"""Failure Map reference implementation. Python standard library only."""
import json
N = 1
observations = []
def solve(blocks, requests):
free = []
for addr, size, marked in sorted(blocks):
if marked:
continue
if free and free[-1][0] + size == addr:
free[-1][1] += size
else:
free.append([addr, size])
swept = [list(b) for b in free]
got = []
for req in requests:
need = (req + 7) // 8 * 8
choice = None
for b in free:
if b[1] >= need:
choice = b
break
if choice is None:
got.append(None)
continue
got.append(choice[0])
rem = choice[1] - need
if rem >= 16:
choice[0] += need
choice[1] = rem
else:
free.remove(choice)
return {'swept': swept, 'alloc': got, 'free': free}
def check(label, actual, expected):
observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = [[('regression: sweep, split and exhaust',
([[1088, 8, True],
[1040, 32, False],
[1024, 16, True],
[1072, 16, False],
[1096, 24, False],
[1120, 40, False],
[1160, 16, True]],
[20, 24, 40, 10, 8]),
{'alloc': [1040, 1064, 1096, 1136, None], 'free': [], 'swept': [[1040, 48], [1096, 64]]}),
('exact fit uses the first block',
([[1088, 8, True],
[1040, 32, False],
[1024, 16, True],
[1072, 16, False],
[1096, 24, False],
[1120, 40, False],
[1160, 16, True]],
[48, 64]),
{'alloc': [1040, 1096], 'free': [], 'swept': [[1040, 48], [1096, 64]]}),
('remainder of exactly the minimum block size',
([[1088, 8, True],
[1040, 32, False],
[1024, 16, True],
[1072, 16, False],
[1096, 24, False],
[1120, 40, False],
[1160, 16, True]],
[32, 40]),
{'alloc': [1040, 1096], 'free': [[1072, 16], [1136, 24]], 'swept': [[1040, 48], [1096, 64]]}),
('remainder too small to split',
([[1088, 8, True],
[1040, 32, False],
[1024, 16, True],
[1072, 16, False],
[1096, 24, False],
[1120, 40, False],
[1160, 16, True]],
[44, 50, 1]),
{'alloc': [1040, 1096, None], 'free': [], 'swept': [[1040, 48], [1096, 64]]}),
('sweep snapshot is independent of allocation',
([[1088, 8, True],
[1040, 32, False],
[1024, 16, True],
[1072, 16, False],
[1096, 24, False],
[1120, 40, False],
[1160, 16, True]],
[1]),
{'alloc': [1040], 'free': [[1048, 40], [1096, 64]], 'swept': [[1040, 48], [1096, 64]]}),
('control: fully marked heap',
([[1024, 32, True], [1056, 16, True]], [8]),
{'alloc': [None], 'free': [], 'swept': []})],
[('regression: sweep, split and exhaust',
([[2112, 8, True],
[2064, 32, False],
[2048, 16, True],
[2096, 16, False],
[2120, 24, False],
[2144, 40, False],
[2184, 16, True]],
[20, 24, 40, 10, 8]),
{'alloc': [2064, 2088, 2120, 2160, None], 'free': [], 'swept': [[2064, 48], [2120, 64]]}),
('exact fit uses the first block',
([[2112, 8, True],
[2064, 32, False],
[2048, 16, True],
[2096, 16, False],
[2120, 24, False],
[2144, 40, False],
[2184, 16, True]],
[48, 64]),
{'alloc': [2064, 2120], 'free': [], 'swept': [[2064, 48], [2120, 64]]}),
('remainder of exactly the minimum block size',
([[2112, 8, True],
[2064, 32, False],
[2048, 16, True],
[2096, 16, False],
[2120, 24, False],
[2144, 40, False],
[2184, 16, True]],
[32, 40]),
{'alloc': [2064, 2120], 'free': [[2096, 16], [2160, 24]], 'swept': [[2064, 48], [2120, 64]]}),
('remainder too small to split',
([[2112, 8, True],
[2064, 32, False],
[2048, 16, True],
[2096, 16, False],
[2120, 24, False],
[2144, 40, False],
[2184, 16, True]],
[44, 50, 1]),
{'alloc': [2064, 2120, None], 'free': [], 'swept': [[2064, 48], [2120, 64]]}),
('sweep snapshot is independent of allocation',
([[2112, 8, True],
[2064, 32, False],
[2048, 16, True],
[2096, 16, False],
[2120, 24, False],
[2144, 40, False],
[2184, 16, True]],
[1]),
{'alloc': [2064], 'free': [[2072, 40], [2120, 64]], 'swept': [[2064, 48], [2120, 64]]}),
('control: fully marked heap',
([[2048, 32, True], [2080, 16, True]], [8]),
{'alloc': [None], 'free': [], 'swept': []})],
[('regression: sweep, split and exhaust',
([[3136, 8, True],
[3088, 32, False],
[3072, 16, True],
[3120, 16, False],
[3144, 24, False],
[3168, 40, False],
[3208, 16, True]],
[20, 24, 40, 10, 8]),
{'alloc': [3088, 3112, 3144, 3184, None], 'free': [], 'swept': [[3088, 48], [3144, 64]]}),
('exact fit uses the first block',
([[3136, 8, True],
[3088, 32, False],
[3072, 16, True],
[3120, 16, False],
[3144, 24, False],
[3168, 40, False],
[3208, 16, True]],
[48, 64]),
{'alloc': [3088, 3144], 'free': [], 'swept': [[3088, 48], [3144, 64]]}),
('remainder of exactly the minimum block size',
([[3136, 8, True],
[3088, 32, False],
[3072, 16, True],
[3120, 16, False],
[3144, 24, False],
[3168, 40, False],
[3208, 16, True]],
[32, 40]),
{'alloc': [3088, 3144], 'free': [[3120, 16], [3184, 24]], 'swept': [[3088, 48], [3144, 64]]}),
('remainder too small to split',
([[3136, 8, True],
[3088, 32, False],
[3072, 16, True],
[3120, 16, False],
[3144, 24, False],
[3168, 40, False],
[3208, 16, True]],
[44, 50, 1]),
{'alloc': [3088, 3144, None], 'free': [], 'swept': [[3088, 48], [3144, 64]]}),
('sweep snapshot is independent of allocation',
([[3136, 8, True],
[3088, 32, False],
[3072, 16, True],
[3120, 16, False],
[3144, 24, False],
[3168, 40, False],
[3208, 16, True]],
[1]),
{'alloc': [3088], 'free': [[3096, 40], [3144, 64]], 'swept': [[3088, 48], [3144, 64]]}),
('control: fully marked heap',
([[3072, 32, True], [3104, 16, True]], [8]),
{'alloc': [None], 'free': [], 'swept': []})],
[('regression: sweep, split and exhaust',
([[4160, 8, True],
[4112, 32, False],
[4096, 16, True],
[4144, 16, False],
[4168, 24, False],
[4192, 40, False],
[4232, 16, True]],
[20, 24, 40, 10, 8]),
{'alloc': [4112, 4136, 4168, 4208, None], 'free': [], 'swept': [[4112, 48], [4168, 64]]}),
('exact fit uses the first block',
([[4160, 8, True],
[4112, 32, False],
[4096, 16, True],
[4144, 16, False],
[4168, 24, False],
[4192, 40, False],
[4232, 16, True]],
[48, 64]),
{'alloc': [4112, 4168], 'free': [], 'swept': [[4112, 48], [4168, 64]]}),
('remainder of exactly the minimum block size',
([[4160, 8, True],
[4112, 32, False],
[4096, 16, True],
[4144, 16, False],
[4168, 24, False],
[4192, 40, False],
[4232, 16, True]],
[32, 40]),
{'alloc': [4112, 4168], 'free': [[4144, 16], [4208, 24]], 'swept': [[4112, 48], [4168, 64]]}),
('remainder too small to split',
([[4160, 8, True],
[4112, 32, False],
[4096, 16, True],
[4144, 16, False],
[4168, 24, False],
[4192, 40, False],
[4232, 16, True]],
[44, 50, 1]),
{'alloc': [4112, 4168, None], 'free': [], 'swept': [[4112, 48], [4168, 64]]}),
('sweep snapshot is independent of allocation',
([[4160, 8, True],
[4112, 32, False],
[4096, 16, True],
[4144, 16, False],
[4168, 24, False],
[4192, 40, False],
[4232, 16, True]],
[1]),
{'alloc': [4112], 'free': [[4120, 40], [4168, 64]], 'swept': [[4112, 48], [4168, 64]]}),
('control: fully marked heap',
([[4096, 32, True], [4128, 16, True]], [8]),
{'alloc': [None], 'free': [], 'swept': []})],
[('regression: sweep, split and exhaust',
([[5184, 8, True],
[5136, 32, False],
[5120, 16, True],
[5168, 16, False],
[5192, 24, False],
[5216, 40, False],
[5256, 16, True]],
[20, 24, 40, 10, 8]),
{'alloc': [5136, 5160, 5192, 5232, None], 'free': [], 'swept': [[5136, 48], [5192, 64]]}),
('exact fit uses the first block',
([[5184, 8, True],
[5136, 32, False],
[5120, 16, True],
[5168, 16, False],
[5192, 24, False],
[5216, 40, False],
[5256, 16, True]],
[48, 64]),
{'alloc': [5136, 5192], 'free': [], 'swept': [[5136, 48], [5192, 64]]}),
('remainder of exactly the minimum block size',
([[5184, 8, True],
[5136, 32, False],
[5120, 16, True],
[5168, 16, False],
[5192, 24, False],
[5216, 40, False],
[5256, 16, True]],
[32, 40]),
{'alloc': [5136, 5192], 'free': [[5168, 16], [5232, 24]], 'swept': [[5136, 48], [5192, 64]]}),
('remainder too small to split',
([[5184, 8, True],
[5136, 32, False],
[5120, 16, True],
[5168, 16, False],
[5192, 24, False],
[5216, 40, False],
[5256, 16, True]],
[44, 50, 1]),
{'alloc': [5136, 5192, None], 'free': [], 'swept': [[5136, 48], [5192, 64]]}),
('sweep snapshot is independent of allocation',
([[5184, 8, True],
[5136, 32, False],
[5120, 16, True],
[5168, 16, False],
[5192, 24, False],
[5216, 40, False],
[5256, 16, True]],
[1]),
{'alloc': [5136], 'free': [[5144, 40], [5192, 64]], 'swept': [[5136, 48], [5192, 64]]}),
('control: fully marked heap',
([[5120, 32, True], [5152, 16, True]], [8]),
{'alloc': [None], 'free': [], 'swept': []})]]
for label, args, expected in cases[N - 1]:
check(label, solve(*args), expected)
print(json.dumps({"observations": observations, "passed": all(x["passed"] for x in observations)}, ensure_ascii=False))
raise SystemExit(0 if all(x["passed"] for x in observations) else 1)
| Boundary fixture | Actual | Expected | Outcome |
|---|---|---|---|
| regression: sweep, split and exhaust | {'alloc': [1040, 1072, 1120, 1096, None], 'free': [], 'swept': [[1040, 32], [1072, 40], [1120, 40]]} | {'alloc': [1040, 1064, 1096, 1136, None], 'free': [], 'swept': [[1040, 48], [1096, 64]]} | Failed |
| exact fit uses the first block | {'alloc': [None, None], 'free': [[1040, 32], [1072, 40], [1120, 40]], 'swept': [[1040, 32], [1072, 40], [1120, 40]]} | {'alloc': [1040, 1096], 'free': [], 'swept': [[1040, 48], [1096, 64]]} | Failed |
| remainder of exactly the minimum block size | {'alloc': [1040, 1072], 'free': [[1120, 40]], 'swept': [[1040, 32], [1072, 40], [1120, 40]]} | {'alloc': [1040, 1096], 'free': [[1072, 16], [1136, 24]], 'swept': [[1040, 48], [1096, 64]]} | Failed |
| remainder too small to split | {'alloc': [None, None, 1040], 'free': [[1048, 24], [1072, 40], [1120, 40]], 'swept': [[1040, 32], [1072, 40], [1120, 40]]} | {'alloc': [1040, 1096, None], 'free': [], 'swept': [[1040, 48], [1096, 64]]} | Failed |
| sweep snapshot is independent of allocation | {'alloc': [1040], 'free': [[1048, 24], [1072, 40], [1120, 40]], 'swept': [[1040, 32], [1072, 40], [1120, 40]]} | {'alloc': [1040], 'free': [[1048, 40], [1096, 64]], 'swept': [[1040, 48], [1096, 64]]} | Failed |
| control: fully marked heap | {'alloc': [None], 'free': [], 'swept': []} | {'alloc': [None], 'free': [], 'swept': []} | Passed |
SHA-256 / 36701a9363eded7343044ddfa9e6c866ad0909da61d73d8014e4f302c00b8022
3 / The verified repair
Exit 0"""Failure Map reference implementation. Python standard library only."""
import json
N = 1
observations = []
def solve(blocks, requests):
free = []
for addr, size, marked in sorted(blocks):
if marked:
continue
if free and free[-1][0] + free[-1][1] == addr:
free[-1][1] += size
else:
free.append([addr, size])
swept = [list(b) for b in free]
got = []
for req in requests:
need = (req + 7) // 8 * 8
choice = None
for b in free:
if b[1] >= need:
choice = b
break
if choice is None:
got.append(None)
continue
got.append(choice[0])
rem = choice[1] - need
if rem >= 16:
choice[0] += need
choice[1] = rem
else:
free.remove(choice)
return {'swept': swept, 'alloc': got, 'free': free}
def check(label, actual, expected):
observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = [[('regression: sweep, split and exhaust',
([[1088, 8, True],
[1040, 32, False],
[1024, 16, True],
[1072, 16, False],
[1096, 24, False],
[1120, 40, False],
[1160, 16, True]],
[20, 24, 40, 10, 8]),
{'alloc': [1040, 1064, 1096, 1136, None], 'free': [], 'swept': [[1040, 48], [1096, 64]]}),
('exact fit uses the first block',
([[1088, 8, True],
[1040, 32, False],
[1024, 16, True],
[1072, 16, False],
[1096, 24, False],
[1120, 40, False],
[1160, 16, True]],
[48, 64]),
{'alloc': [1040, 1096], 'free': [], 'swept': [[1040, 48], [1096, 64]]}),
('remainder of exactly the minimum block size',
([[1088, 8, True],
[1040, 32, False],
[1024, 16, True],
[1072, 16, False],
[1096, 24, False],
[1120, 40, False],
[1160, 16, True]],
[32, 40]),
{'alloc': [1040, 1096], 'free': [[1072, 16], [1136, 24]], 'swept': [[1040, 48], [1096, 64]]}),
('remainder too small to split',
([[1088, 8, True],
[1040, 32, False],
[1024, 16, True],
[1072, 16, False],
[1096, 24, False],
[1120, 40, False],
[1160, 16, True]],
[44, 50, 1]),
{'alloc': [1040, 1096, None], 'free': [], 'swept': [[1040, 48], [1096, 64]]}),
('sweep snapshot is independent of allocation',
([[1088, 8, True],
[1040, 32, False],
[1024, 16, True],
[1072, 16, False],
[1096, 24, False],
[1120, 40, False],
[1160, 16, True]],
[1]),
{'alloc': [1040], 'free': [[1048, 40], [1096, 64]], 'swept': [[1040, 48], [1096, 64]]}),
('control: fully marked heap',
([[1024, 32, True], [1056, 16, True]], [8]),
{'alloc': [None], 'free': [], 'swept': []})],
[('regression: sweep, split and exhaust',
([[2112, 8, True],
[2064, 32, False],
[2048, 16, True],
[2096, 16, False],
[2120, 24, False],
[2144, 40, False],
[2184, 16, True]],
[20, 24, 40, 10, 8]),
{'alloc': [2064, 2088, 2120, 2160, None], 'free': [], 'swept': [[2064, 48], [2120, 64]]}),
('exact fit uses the first block',
([[2112, 8, True],
[2064, 32, False],
[2048, 16, True],
[2096, 16, False],
[2120, 24, False],
[2144, 40, False],
[2184, 16, True]],
[48, 64]),
{'alloc': [2064, 2120], 'free': [], 'swept': [[2064, 48], [2120, 64]]}),
('remainder of exactly the minimum block size',
([[2112, 8, True],
[2064, 32, False],
[2048, 16, True],
[2096, 16, False],
[2120, 24, False],
[2144, 40, False],
[2184, 16, True]],
[32, 40]),
{'alloc': [2064, 2120], 'free': [[2096, 16], [2160, 24]], 'swept': [[2064, 48], [2120, 64]]}),
('remainder too small to split',
([[2112, 8, True],
[2064, 32, False],
[2048, 16, True],
[2096, 16, False],
[2120, 24, False],
[2144, 40, False],
[2184, 16, True]],
[44, 50, 1]),
{'alloc': [2064, 2120, None], 'free': [], 'swept': [[2064, 48], [2120, 64]]}),
('sweep snapshot is independent of allocation',
([[2112, 8, True],
[2064, 32, False],
[2048, 16, True],
[2096, 16, False],
[2120, 24, False],
[2144, 40, False],
[2184, 16, True]],
[1]),
{'alloc': [2064], 'free': [[2072, 40], [2120, 64]], 'swept': [[2064, 48], [2120, 64]]}),
('control: fully marked heap',
([[2048, 32, True], [2080, 16, True]], [8]),
{'alloc': [None], 'free': [], 'swept': []})],
[('regression: sweep, split and exhaust',
([[3136, 8, True],
[3088, 32, False],
[3072, 16, True],
[3120, 16, False],
[3144, 24, False],
[3168, 40, False],
[3208, 16, True]],
[20, 24, 40, 10, 8]),
{'alloc': [3088, 3112, 3144, 3184, None], 'free': [], 'swept': [[3088, 48], [3144, 64]]}),
('exact fit uses the first block',
([[3136, 8, True],
[3088, 32, False],
[3072, 16, True],
[3120, 16, False],
[3144, 24, False],
[3168, 40, False],
[3208, 16, True]],
[48, 64]),
{'alloc': [3088, 3144], 'free': [], 'swept': [[3088, 48], [3144, 64]]}),
('remainder of exactly the minimum block size',
([[3136, 8, True],
[3088, 32, False],
[3072, 16, True],
[3120, 16, False],
[3144, 24, False],
[3168, 40, False],
[3208, 16, True]],
[32, 40]),
{'alloc': [3088, 3144], 'free': [[3120, 16], [3184, 24]], 'swept': [[3088, 48], [3144, 64]]}),
('remainder too small to split',
([[3136, 8, True],
[3088, 32, False],
[3072, 16, True],
[3120, 16, False],
[3144, 24, False],
[3168, 40, False],
[3208, 16, True]],
[44, 50, 1]),
{'alloc': [3088, 3144, None], 'free': [], 'swept': [[3088, 48], [3144, 64]]}),
('sweep snapshot is independent of allocation',
([[3136, 8, True],
[3088, 32, False],
[3072, 16, True],
[3120, 16, False],
[3144, 24, False],
[3168, 40, False],
[3208, 16, True]],
[1]),
{'alloc': [3088], 'free': [[3096, 40], [3144, 64]], 'swept': [[3088, 48], [3144, 64]]}),
('control: fully marked heap',
([[3072, 32, True], [3104, 16, True]], [8]),
{'alloc': [None], 'free': [], 'swept': []})],
[('regression: sweep, split and exhaust',
([[4160, 8, True],
[4112, 32, False],
[4096, 16, True],
[4144, 16, False],
[4168, 24, False],
[4192, 40, False],
[4232, 16, True]],
[20, 24, 40, 10, 8]),
{'alloc': [4112, 4136, 4168, 4208, None], 'free': [], 'swept': [[4112, 48], [4168, 64]]}),
('exact fit uses the first block',
([[4160, 8, True],
[4112, 32, False],
[4096, 16, True],
[4144, 16, False],
[4168, 24, False],
[4192, 40, False],
[4232, 16, True]],
[48, 64]),
{'alloc': [4112, 4168], 'free': [], 'swept': [[4112, 48], [4168, 64]]}),
('remainder of exactly the minimum block size',
([[4160, 8, True],
[4112, 32, False],
[4096, 16, True],
[4144, 16, False],
[4168, 24, False],
[4192, 40, False],
[4232, 16, True]],
[32, 40]),
{'alloc': [4112, 4168], 'free': [[4144, 16], [4208, 24]], 'swept': [[4112, 48], [4168, 64]]}),
('remainder too small to split',
([[4160, 8, True],
[4112, 32, False],
[4096, 16, True],
[4144, 16, False],
[4168, 24, False],
[4192, 40, False],
[4232, 16, True]],
[44, 50, 1]),
{'alloc': [4112, 4168, None], 'free': [], 'swept': [[4112, 48], [4168, 64]]}),
('sweep snapshot is independent of allocation',
([[4160, 8, True],
[4112, 32, False],
[4096, 16, True],
[4144, 16, False],
[4168, 24, False],
[4192, 40, False],
[4232, 16, True]],
[1]),
{'alloc': [4112], 'free': [[4120, 40], [4168, 64]], 'swept': [[4112, 48], [4168, 64]]}),
('control: fully marked heap',
([[4096, 32, True], [4128, 16, True]], [8]),
{'alloc': [None], 'free': [], 'swept': []})],
[('regression: sweep, split and exhaust',
([[5184, 8, True],
[5136, 32, False],
[5120, 16, True],
[5168, 16, False],
[5192, 24, False],
[5216, 40, False],
[5256, 16, True]],
[20, 24, 40, 10, 8]),
{'alloc': [5136, 5160, 5192, 5232, None], 'free': [], 'swept': [[5136, 48], [5192, 64]]}),
('exact fit uses the first block',
([[5184, 8, True],
[5136, 32, False],
[5120, 16, True],
[5168, 16, False],
[5192, 24, False],
[5216, 40, False],
[5256, 16, True]],
[48, 64]),
{'alloc': [5136, 5192], 'free': [], 'swept': [[5136, 48], [5192, 64]]}),
('remainder of exactly the minimum block size',
([[5184, 8, True],
[5136, 32, False],
[5120, 16, True],
[5168, 16, False],
[5192, 24, False],
[5216, 40, False],
[5256, 16, True]],
[32, 40]),
{'alloc': [5136, 5192], 'free': [[5168, 16], [5232, 24]], 'swept': [[5136, 48], [5192, 64]]}),
('remainder too small to split',
([[5184, 8, True],
[5136, 32, False],
[5120, 16, True],
[5168, 16, False],
[5192, 24, False],
[5216, 40, False],
[5256, 16, True]],
[44, 50, 1]),
{'alloc': [5136, 5192, None], 'free': [], 'swept': [[5136, 48], [5192, 64]]}),
('sweep snapshot is independent of allocation',
([[5184, 8, True],
[5136, 32, False],
[5120, 16, True],
[5168, 16, False],
[5192, 24, False],
[5216, 40, False],
[5256, 16, True]],
[1]),
{'alloc': [5136], 'free': [[5144, 40], [5192, 64]], 'swept': [[5136, 48], [5192, 64]]}),
('control: fully marked heap',
([[5120, 32, True], [5152, 16, True]], [8]),
{'alloc': [None], 'free': [], 'swept': []})]]
for label, args, expected in cases[N - 1]:
check(label, solve(*args), expected)
print(json.dumps({"observations": observations, "passed": all(x["passed"] for x in observations)}, ensure_ascii=False))
raise SystemExit(0 if all(x["passed"] for x in observations) else 1)
| Boundary fixture | Actual | Expected | Outcome |
|---|---|---|---|
| regression: sweep, split and exhaust | {'alloc': [1040, 1064, 1096, 1136, None], 'free': [], 'swept': [[1040, 48], [1096, 64]]} | {'alloc': [1040, 1064, 1096, 1136, None], 'free': [], 'swept': [[1040, 48], [1096, 64]]} | Passed |
| exact fit uses the first block | {'alloc': [1040, 1096], 'free': [], 'swept': [[1040, 48], [1096, 64]]} | {'alloc': [1040, 1096], 'free': [], 'swept': [[1040, 48], [1096, 64]]} | Passed |
| remainder of exactly the minimum block size | {'alloc': [1040, 1096], 'free': [[1072, 16], [1136, 24]], 'swept': [[1040, 48], [1096, 64]]} | {'alloc': [1040, 1096], 'free': [[1072, 16], [1136, 24]], 'swept': [[1040, 48], [1096, 64]]} | Passed |
| remainder too small to split | {'alloc': [1040, 1096, None], 'free': [], 'swept': [[1040, 48], [1096, 64]]} | {'alloc': [1040, 1096, None], 'free': [], 'swept': [[1040, 48], [1096, 64]]} | Passed |
| sweep snapshot is independent of allocation | {'alloc': [1040], 'free': [[1048, 40], [1096, 64]], 'swept': [[1040, 48], [1096, 64]]} | {'alloc': [1040], 'free': [[1048, 40], [1096, 64]], 'swept': [[1040, 48], [1096, 64]]} | Passed |
| control: fully marked heap | {'alloc': [None], 'free': [], 'swept': []} | {'alloc': [None], 'free': [], 'swept': []} | Passed |
SHA-256 / 85d9ca4ce9716863a5678dcbf1a69f329730cd6e642031ef6b9b9cf2f63f8138
Verification & scope
A deterministic, bounded teaching model of one garbage-collector mechanism with stipulated rules; it is not a production collector and claims no conformance to any particular runtime. This reproducer isolates one failure mechanism. Results cover the supplied fixtures. Variants within a family share a test contract and should remain grouped when constructing evaluation splits. Related mechanisms with a shared evaluation_group must also remain together; these controlled models are not independent production incidents.
Observations recorded using Python 3.12.14 at 2026-09-29T14:51:26.987430+00:00.
Case digest / 4ee1882c33f1e968c3d9f91cf44a042b7819bc8bf8f59e8f8998968218a4287e