FA-90476 / Garbage collector invariants / Open access
Free-list sweep: exact fits skipped · case 01
A request that exactly matches a free block is served from a later, larger block.
ROOT CAUSE
The fit test requires the block to be strictly larger than the request.
VERIFIED REPAIR
A block fits when it is at least the rounded request size.
Unsuccessful approach: Rejecting blocks that would leave a small remainder skips valid whole-block fits.
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, 1096, None, 1064, 1120], 'free': [[1128, 32]], 'swept': [[1040, 48], [1096, 64]]} | {'alloc': [1040, 1064, 1096, 1136, None], 'free': [], 'swept': [[1040, 48], [1096, 64]]} | Failed |
| exact fit uses the first block | {'alloc': [1096, None], 'free': [[1040, 48], [1144, 16]], 'swept': [[1040, 48], [1096, 64]]} | {'alloc': [1040, 1096], 'free': [], 'swept': [[1040, 48], [1096, 64]]} | Failed |
| 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': [1096, None, 1040], 'free': [[1048, 40], [1144, 16]], 'swept': [[1040, 48], [1096, 64]]} | {'alloc': [1040, 1096, None], 'free': [], 'swept': [[1040, 48], [1096, 64]]} | Failed |
| 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 / 40acbfa39f22c6eaa775a652132be1326e3771a13aa96c99831aaa1c41e9f0c9
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] + 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 >= 16 or 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, None, 1136], 'free': [[1144, 16]], 'swept': [[1040, 48], [1096, 64]]} | {'alloc': [1040, 1064, 1096, 1136, None], 'free': [], 'swept': [[1040, 48], [1096, 64]]} | Failed |
| 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, None, 1096], 'free': [[1104, 56]], 'swept': [[1040, 48], [1096, 64]]} | {'alloc': [1040, 1096, None], 'free': [], 'swept': [[1040, 48], [1096, 64]]} | Failed |
| 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 / e5031165ca2b1fca8c58c66ecabaab0be21123ea6109ca6d6d24a69955ceedfe
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:27.078906+00:00.
Case digest / 90f48b4134c49a57d56749ea7c788dc159a5dc81a54c4db605b6c02a21292320