FA-90466 / Garbage collector invariants / Open access
Free-list sweep: split block keeps the allocated address · case 01
The next allocation is handed the same address again.
ROOT CAUSE
After splitting, the free block's size shrinks but its start is not moved past the allocation.
VERIFIED REPAIR
Advance the free block start by the allocated size.
Unsuccessful approach: Advancing by the remainder instead of the allocation size misplaces the free block.
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[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, 1040, 1096, 1096, None], 'free': [], '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': [[1040, 16], [1096, 24]], 'swept': [[1040, 48], [1096, 64]]} | {'alloc': [1040, 1096], 'free': [[1072, 16], [1136, 24]], 'swept': [[1040, 48], [1096, 64]]} | Failed |
| 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': [[1040, 40], [1096, 64]], 'swept': [[1040, 48], [1096, 64]]} | {'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 / 7d7fa2e454d2a8cb8d3f99a5bc0587f458a612caace555da66da92ce090a6fdf
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:
choice = b
break
if choice is None:
got.append(None)
continue
got.append(choice[0])
rem = choice[1] - need
if rem >= 16:
choice[0] += rem
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, 1120, None], 'free': [], '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': [[1056, 16], [1120, 24]], 'swept': [[1040, 48], [1096, 64]]} | {'alloc': [1040, 1096], 'free': [[1072, 16], [1136, 24]], 'swept': [[1040, 48], [1096, 64]]} | Failed |
| 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': [[1080, 40], [1096, 64]], 'swept': [[1040, 48], [1096, 64]]} | {'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 / 26ff75345d63bdbb123592f96627aec2bb11bd0af340e315a8d7ad6a4d519f25
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.030552+00:00.
Case digest / 53c91e47ecefd55f529ad4400ea5625a21e97a3f84dbde1ba50b87d06ad7748f