FA-90591 / Garbage collector invariants / Open access
Conservative scan: free blocks pinned · case 01
Stale stack words keep free-list blocks reserved.
ROOT CAUSE
The allocated flag of the candidate block is never checked.
VERIFIED REPAIR
Skip candidates that fall in free blocks.
Unsuccessful approach: Rejecting only exact starts of free blocks still pins them through interior addresses.
Case contract
Conservative scanning of machine words. A word whose low three bits are 011 is a tagged heap pointer to address word - 3; all other words are immediates. objs are [start, size, allocated] in any order. A candidate address pins the allocated object whose start equals it, or, when interior pointers are enabled, the allocated object whose [start, start+size) contains it; addresses in gaps, in free blocks or outside the heap pin nothing. Return the sorted starts of pinned objects.
Why this case matters
Conservative collectors must neither miss real references nor pin unrelated or free memory.
1 / The failure
Exit 1"""Failure Map reference implementation. Python standard library only."""
import json
import bisect
N = 1
observations = []
def solve(objs, words, interior):
starts = sorted(o[0] for o in objs)
size_of = {o[0]: o[1] for o in objs}
alloc = {o[0]: o[2] for o in objs}
lo = min(starts) if starts else 0
hi = max(s + size_of[s] for s in starts) if starts else 0
found = set()
for w in words:
if w & 7 != 3:
continue
a = w - 3
if not (lo <= a < hi):
continue
i = bisect.bisect_right(starts, a) - 1
s = starts[i]
if a == s or (interior and a < s + size_of[s]):
found.add(s)
return sorted(found)
def check(label, actual, expected):
observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = [[('regression: tagged start pointers only',
([[416, 32, True], [320, 32, True], [352, 16, True], [384, 16, False]], [323, 355, 322, 363], False),
[320, 352]),
('interior pointers when allowed',
([[416, 32, True], [320, 32, True], [352, 16, True], [384, 16, False]], [363, 427, 339], True),
[320, 352, 416]),
('interior pointer rejected when not allowed',
([[416, 32, True], [320, 32, True], [352, 16, True], [384, 16, False]], [363, 427], False),
[]),
('one-past-the-end pointer into a gap',
([[416, 32, True], [320, 32, True], [352, 16, True], [384, 16, False]], [371, 403], True),
[]),
('pointers to a free block',
([[416, 32, True], [320, 32, True], [352, 16, True], [384, 16, False]], [387, 395], True),
[]),
('pointer exactly at a later object start',
([[416, 32, True], [320, 32, True], [352, 16, True], [384, 16, False]], [419, 451, 267], False),
[416]),
('control: untagged words ignored',
([[416, 32, True], [320, 32, True], [352, 16, True], [384, 16, False]], [320, 352, 416], True),
[])],
[('regression: tagged start pointers only',
([[672, 32, True], [576, 32, True], [608, 16, True], [640, 16, False]], [579, 611, 578, 619], False),
[576, 608]),
('interior pointers when allowed',
([[672, 32, True], [576, 32, True], [608, 16, True], [640, 16, False]], [619, 683, 595], True),
[576, 608, 672]),
('interior pointer rejected when not allowed',
([[672, 32, True], [576, 32, True], [608, 16, True], [640, 16, False]], [619, 683], False),
[]),
('one-past-the-end pointer into a gap',
([[672, 32, True], [576, 32, True], [608, 16, True], [640, 16, False]], [627, 659], True),
[]),
('pointers to a free block',
([[672, 32, True], [576, 32, True], [608, 16, True], [640, 16, False]], [643, 651], True),
[]),
('pointer exactly at a later object start',
([[672, 32, True], [576, 32, True], [608, 16, True], [640, 16, False]], [675, 707, 523], False),
[672]),
('control: untagged words ignored',
([[672, 32, True], [576, 32, True], [608, 16, True], [640, 16, False]], [576, 608, 672], True),
[])],
[('regression: tagged start pointers only',
([[928, 32, True], [832, 32, True], [864, 16, True], [896, 16, False]], [835, 867, 834, 875], False),
[832, 864]),
('interior pointers when allowed',
([[928, 32, True], [832, 32, True], [864, 16, True], [896, 16, False]], [875, 939, 851], True),
[832, 864, 928]),
('interior pointer rejected when not allowed',
([[928, 32, True], [832, 32, True], [864, 16, True], [896, 16, False]], [875, 939], False),
[]),
('one-past-the-end pointer into a gap',
([[928, 32, True], [832, 32, True], [864, 16, True], [896, 16, False]], [883, 915], True),
[]),
('pointers to a free block',
([[928, 32, True], [832, 32, True], [864, 16, True], [896, 16, False]], [899, 907], True),
[]),
('pointer exactly at a later object start',
([[928, 32, True], [832, 32, True], [864, 16, True], [896, 16, False]], [931, 963, 779], False),
[928]),
('control: untagged words ignored',
([[928, 32, True], [832, 32, True], [864, 16, True], [896, 16, False]], [832, 864, 928], True),
[])],
[('regression: tagged start pointers only',
([[1184, 32, True], [1088, 32, True], [1120, 16, True], [1152, 16, False]],
[1091, 1123, 1090, 1131],
False),
[1088, 1120]),
('interior pointers when allowed',
([[1184, 32, True], [1088, 32, True], [1120, 16, True], [1152, 16, False]], [1131, 1195, 1107], True),
[1088, 1120, 1184]),
('interior pointer rejected when not allowed',
([[1184, 32, True], [1088, 32, True], [1120, 16, True], [1152, 16, False]], [1131, 1195], False),
[]),
('one-past-the-end pointer into a gap',
([[1184, 32, True], [1088, 32, True], [1120, 16, True], [1152, 16, False]], [1139, 1171], True),
[]),
('pointers to a free block',
([[1184, 32, True], [1088, 32, True], [1120, 16, True], [1152, 16, False]], [1155, 1163], True),
[]),
('pointer exactly at a later object start',
([[1184, 32, True], [1088, 32, True], [1120, 16, True], [1152, 16, False]], [1187, 1219, 1035], False),
[1184]),
('control: untagged words ignored',
([[1184, 32, True], [1088, 32, True], [1120, 16, True], [1152, 16, False]], [1088, 1120, 1184], True),
[])],
[('regression: tagged start pointers only',
([[1440, 32, True], [1344, 32, True], [1376, 16, True], [1408, 16, False]],
[1347, 1379, 1346, 1387],
False),
[1344, 1376]),
('interior pointers when allowed',
([[1440, 32, True], [1344, 32, True], [1376, 16, True], [1408, 16, False]], [1387, 1451, 1363], True),
[1344, 1376, 1440]),
('interior pointer rejected when not allowed',
([[1440, 32, True], [1344, 32, True], [1376, 16, True], [1408, 16, False]], [1387, 1451], False),
[]),
('one-past-the-end pointer into a gap',
([[1440, 32, True], [1344, 32, True], [1376, 16, True], [1408, 16, False]], [1395, 1427], True),
[]),
('pointers to a free block',
([[1440, 32, True], [1344, 32, True], [1376, 16, True], [1408, 16, False]], [1411, 1419], True),
[]),
('pointer exactly at a later object start',
([[1440, 32, True], [1344, 32, True], [1376, 16, True], [1408, 16, False]], [1443, 1475, 1291], False),
[1440]),
('control: untagged words ignored',
([[1440, 32, True], [1344, 32, True], [1376, 16, True], [1408, 16, False]], [1344, 1376, 1440], True),
[])]]
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: tagged start pointers only | [320, 352] | [320, 352] | Passed |
| interior pointers when allowed | [320, 352, 416] | [320, 352, 416] | Passed |
| interior pointer rejected when not allowed | [] | [] | Passed |
| one-past-the-end pointer into a gap | [] | [] | Passed |
| pointers to a free block | [384] | [] | Failed |
| pointer exactly at a later object start | [416] | [416] | Passed |
| control: untagged words ignored | [] | [] | Passed |
SHA-256 / 09925502d6c616da202648781929cabc5636a3b91a284f39e4be99e02ccbcb1e
2 / The unsuccessful fix
Exit 1"""Failure Map reference implementation. Python standard library only."""
import json
import bisect
N = 1
observations = []
def solve(objs, words, interior):
starts = sorted(o[0] for o in objs)
size_of = {o[0]: o[1] for o in objs}
alloc = {o[0]: o[2] for o in objs}
lo = min(starts) if starts else 0
hi = max(s + size_of[s] for s in starts) if starts else 0
found = set()
for w in words:
if w & 7 != 3:
continue
a = w - 3
if not (lo <= a < hi):
continue
i = bisect.bisect_right(starts, a) - 1
s = starts[i]
if not alloc[s] and a == s:
continue
if a == s or (interior and a < s + size_of[s]):
found.add(s)
return sorted(found)
def check(label, actual, expected):
observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = [[('regression: tagged start pointers only',
([[416, 32, True], [320, 32, True], [352, 16, True], [384, 16, False]], [323, 355, 322, 363], False),
[320, 352]),
('interior pointers when allowed',
([[416, 32, True], [320, 32, True], [352, 16, True], [384, 16, False]], [363, 427, 339], True),
[320, 352, 416]),
('interior pointer rejected when not allowed',
([[416, 32, True], [320, 32, True], [352, 16, True], [384, 16, False]], [363, 427], False),
[]),
('one-past-the-end pointer into a gap',
([[416, 32, True], [320, 32, True], [352, 16, True], [384, 16, False]], [371, 403], True),
[]),
('pointers to a free block',
([[416, 32, True], [320, 32, True], [352, 16, True], [384, 16, False]], [387, 395], True),
[]),
('pointer exactly at a later object start',
([[416, 32, True], [320, 32, True], [352, 16, True], [384, 16, False]], [419, 451, 267], False),
[416]),
('control: untagged words ignored',
([[416, 32, True], [320, 32, True], [352, 16, True], [384, 16, False]], [320, 352, 416], True),
[])],
[('regression: tagged start pointers only',
([[672, 32, True], [576, 32, True], [608, 16, True], [640, 16, False]], [579, 611, 578, 619], False),
[576, 608]),
('interior pointers when allowed',
([[672, 32, True], [576, 32, True], [608, 16, True], [640, 16, False]], [619, 683, 595], True),
[576, 608, 672]),
('interior pointer rejected when not allowed',
([[672, 32, True], [576, 32, True], [608, 16, True], [640, 16, False]], [619, 683], False),
[]),
('one-past-the-end pointer into a gap',
([[672, 32, True], [576, 32, True], [608, 16, True], [640, 16, False]], [627, 659], True),
[]),
('pointers to a free block',
([[672, 32, True], [576, 32, True], [608, 16, True], [640, 16, False]], [643, 651], True),
[]),
('pointer exactly at a later object start',
([[672, 32, True], [576, 32, True], [608, 16, True], [640, 16, False]], [675, 707, 523], False),
[672]),
('control: untagged words ignored',
([[672, 32, True], [576, 32, True], [608, 16, True], [640, 16, False]], [576, 608, 672], True),
[])],
[('regression: tagged start pointers only',
([[928, 32, True], [832, 32, True], [864, 16, True], [896, 16, False]], [835, 867, 834, 875], False),
[832, 864]),
('interior pointers when allowed',
([[928, 32, True], [832, 32, True], [864, 16, True], [896, 16, False]], [875, 939, 851], True),
[832, 864, 928]),
('interior pointer rejected when not allowed',
([[928, 32, True], [832, 32, True], [864, 16, True], [896, 16, False]], [875, 939], False),
[]),
('one-past-the-end pointer into a gap',
([[928, 32, True], [832, 32, True], [864, 16, True], [896, 16, False]], [883, 915], True),
[]),
('pointers to a free block',
([[928, 32, True], [832, 32, True], [864, 16, True], [896, 16, False]], [899, 907], True),
[]),
('pointer exactly at a later object start',
([[928, 32, True], [832, 32, True], [864, 16, True], [896, 16, False]], [931, 963, 779], False),
[928]),
('control: untagged words ignored',
([[928, 32, True], [832, 32, True], [864, 16, True], [896, 16, False]], [832, 864, 928], True),
[])],
[('regression: tagged start pointers only',
([[1184, 32, True], [1088, 32, True], [1120, 16, True], [1152, 16, False]],
[1091, 1123, 1090, 1131],
False),
[1088, 1120]),
('interior pointers when allowed',
([[1184, 32, True], [1088, 32, True], [1120, 16, True], [1152, 16, False]], [1131, 1195, 1107], True),
[1088, 1120, 1184]),
('interior pointer rejected when not allowed',
([[1184, 32, True], [1088, 32, True], [1120, 16, True], [1152, 16, False]], [1131, 1195], False),
[]),
('one-past-the-end pointer into a gap',
([[1184, 32, True], [1088, 32, True], [1120, 16, True], [1152, 16, False]], [1139, 1171], True),
[]),
('pointers to a free block',
([[1184, 32, True], [1088, 32, True], [1120, 16, True], [1152, 16, False]], [1155, 1163], True),
[]),
('pointer exactly at a later object start',
([[1184, 32, True], [1088, 32, True], [1120, 16, True], [1152, 16, False]], [1187, 1219, 1035], False),
[1184]),
('control: untagged words ignored',
([[1184, 32, True], [1088, 32, True], [1120, 16, True], [1152, 16, False]], [1088, 1120, 1184], True),
[])],
[('regression: tagged start pointers only',
([[1440, 32, True], [1344, 32, True], [1376, 16, True], [1408, 16, False]],
[1347, 1379, 1346, 1387],
False),
[1344, 1376]),
('interior pointers when allowed',
([[1440, 32, True], [1344, 32, True], [1376, 16, True], [1408, 16, False]], [1387, 1451, 1363], True),
[1344, 1376, 1440]),
('interior pointer rejected when not allowed',
([[1440, 32, True], [1344, 32, True], [1376, 16, True], [1408, 16, False]], [1387, 1451], False),
[]),
('one-past-the-end pointer into a gap',
([[1440, 32, True], [1344, 32, True], [1376, 16, True], [1408, 16, False]], [1395, 1427], True),
[]),
('pointers to a free block',
([[1440, 32, True], [1344, 32, True], [1376, 16, True], [1408, 16, False]], [1411, 1419], True),
[]),
('pointer exactly at a later object start',
([[1440, 32, True], [1344, 32, True], [1376, 16, True], [1408, 16, False]], [1443, 1475, 1291], False),
[1440]),
('control: untagged words ignored',
([[1440, 32, True], [1344, 32, True], [1376, 16, True], [1408, 16, False]], [1344, 1376, 1440], True),
[])]]
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: tagged start pointers only | [320, 352] | [320, 352] | Passed |
| interior pointers when allowed | [320, 352, 416] | [320, 352, 416] | Passed |
| interior pointer rejected when not allowed | [] | [] | Passed |
| one-past-the-end pointer into a gap | [] | [] | Passed |
| pointers to a free block | [384] | [] | Failed |
| pointer exactly at a later object start | [416] | [416] | Passed |
| control: untagged words ignored | [] | [] | Passed |
SHA-256 / 9e0698b1fedbaeb925030ef240b808a20d914182e08af66e558cf091e25cc6f9
3 / The verified repair
Exit 0"""Failure Map reference implementation. Python standard library only."""
import json
import bisect
N = 1
observations = []
def solve(objs, words, interior):
starts = sorted(o[0] for o in objs)
size_of = {o[0]: o[1] for o in objs}
alloc = {o[0]: o[2] for o in objs}
lo = min(starts) if starts else 0
hi = max(s + size_of[s] for s in starts) if starts else 0
found = set()
for w in words:
if w & 7 != 3:
continue
a = w - 3
if not (lo <= a < hi):
continue
i = bisect.bisect_right(starts, a) - 1
s = starts[i]
if not alloc[s]:
continue
if a == s or (interior and a < s + size_of[s]):
found.add(s)
return sorted(found)
def check(label, actual, expected):
observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = [[('regression: tagged start pointers only',
([[416, 32, True], [320, 32, True], [352, 16, True], [384, 16, False]], [323, 355, 322, 363], False),
[320, 352]),
('interior pointers when allowed',
([[416, 32, True], [320, 32, True], [352, 16, True], [384, 16, False]], [363, 427, 339], True),
[320, 352, 416]),
('interior pointer rejected when not allowed',
([[416, 32, True], [320, 32, True], [352, 16, True], [384, 16, False]], [363, 427], False),
[]),
('one-past-the-end pointer into a gap',
([[416, 32, True], [320, 32, True], [352, 16, True], [384, 16, False]], [371, 403], True),
[]),
('pointers to a free block',
([[416, 32, True], [320, 32, True], [352, 16, True], [384, 16, False]], [387, 395], True),
[]),
('pointer exactly at a later object start',
([[416, 32, True], [320, 32, True], [352, 16, True], [384, 16, False]], [419, 451, 267], False),
[416]),
('control: untagged words ignored',
([[416, 32, True], [320, 32, True], [352, 16, True], [384, 16, False]], [320, 352, 416], True),
[])],
[('regression: tagged start pointers only',
([[672, 32, True], [576, 32, True], [608, 16, True], [640, 16, False]], [579, 611, 578, 619], False),
[576, 608]),
('interior pointers when allowed',
([[672, 32, True], [576, 32, True], [608, 16, True], [640, 16, False]], [619, 683, 595], True),
[576, 608, 672]),
('interior pointer rejected when not allowed',
([[672, 32, True], [576, 32, True], [608, 16, True], [640, 16, False]], [619, 683], False),
[]),
('one-past-the-end pointer into a gap',
([[672, 32, True], [576, 32, True], [608, 16, True], [640, 16, False]], [627, 659], True),
[]),
('pointers to a free block',
([[672, 32, True], [576, 32, True], [608, 16, True], [640, 16, False]], [643, 651], True),
[]),
('pointer exactly at a later object start',
([[672, 32, True], [576, 32, True], [608, 16, True], [640, 16, False]], [675, 707, 523], False),
[672]),
('control: untagged words ignored',
([[672, 32, True], [576, 32, True], [608, 16, True], [640, 16, False]], [576, 608, 672], True),
[])],
[('regression: tagged start pointers only',
([[928, 32, True], [832, 32, True], [864, 16, True], [896, 16, False]], [835, 867, 834, 875], False),
[832, 864]),
('interior pointers when allowed',
([[928, 32, True], [832, 32, True], [864, 16, True], [896, 16, False]], [875, 939, 851], True),
[832, 864, 928]),
('interior pointer rejected when not allowed',
([[928, 32, True], [832, 32, True], [864, 16, True], [896, 16, False]], [875, 939], False),
[]),
('one-past-the-end pointer into a gap',
([[928, 32, True], [832, 32, True], [864, 16, True], [896, 16, False]], [883, 915], True),
[]),
('pointers to a free block',
([[928, 32, True], [832, 32, True], [864, 16, True], [896, 16, False]], [899, 907], True),
[]),
('pointer exactly at a later object start',
([[928, 32, True], [832, 32, True], [864, 16, True], [896, 16, False]], [931, 963, 779], False),
[928]),
('control: untagged words ignored',
([[928, 32, True], [832, 32, True], [864, 16, True], [896, 16, False]], [832, 864, 928], True),
[])],
[('regression: tagged start pointers only',
([[1184, 32, True], [1088, 32, True], [1120, 16, True], [1152, 16, False]],
[1091, 1123, 1090, 1131],
False),
[1088, 1120]),
('interior pointers when allowed',
([[1184, 32, True], [1088, 32, True], [1120, 16, True], [1152, 16, False]], [1131, 1195, 1107], True),
[1088, 1120, 1184]),
('interior pointer rejected when not allowed',
([[1184, 32, True], [1088, 32, True], [1120, 16, True], [1152, 16, False]], [1131, 1195], False),
[]),
('one-past-the-end pointer into a gap',
([[1184, 32, True], [1088, 32, True], [1120, 16, True], [1152, 16, False]], [1139, 1171], True),
[]),
('pointers to a free block',
([[1184, 32, True], [1088, 32, True], [1120, 16, True], [1152, 16, False]], [1155, 1163], True),
[]),
('pointer exactly at a later object start',
([[1184, 32, True], [1088, 32, True], [1120, 16, True], [1152, 16, False]], [1187, 1219, 1035], False),
[1184]),
('control: untagged words ignored',
([[1184, 32, True], [1088, 32, True], [1120, 16, True], [1152, 16, False]], [1088, 1120, 1184], True),
[])],
[('regression: tagged start pointers only',
([[1440, 32, True], [1344, 32, True], [1376, 16, True], [1408, 16, False]],
[1347, 1379, 1346, 1387],
False),
[1344, 1376]),
('interior pointers when allowed',
([[1440, 32, True], [1344, 32, True], [1376, 16, True], [1408, 16, False]], [1387, 1451, 1363], True),
[1344, 1376, 1440]),
('interior pointer rejected when not allowed',
([[1440, 32, True], [1344, 32, True], [1376, 16, True], [1408, 16, False]], [1387, 1451], False),
[]),
('one-past-the-end pointer into a gap',
([[1440, 32, True], [1344, 32, True], [1376, 16, True], [1408, 16, False]], [1395, 1427], True),
[]),
('pointers to a free block',
([[1440, 32, True], [1344, 32, True], [1376, 16, True], [1408, 16, False]], [1411, 1419], True),
[]),
('pointer exactly at a later object start',
([[1440, 32, True], [1344, 32, True], [1376, 16, True], [1408, 16, False]], [1443, 1475, 1291], False),
[1440]),
('control: untagged words ignored',
([[1440, 32, True], [1344, 32, True], [1376, 16, True], [1408, 16, False]], [1344, 1376, 1440], True),
[])]]
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: tagged start pointers only | [320, 352] | [320, 352] | Passed |
| interior pointers when allowed | [320, 352, 416] | [320, 352, 416] | Passed |
| interior pointer rejected when not allowed | [] | [] | Passed |
| one-past-the-end pointer into a gap | [] | [] | Passed |
| pointers to a free block | [] | [] | Passed |
| pointer exactly at a later object start | [416] | [416] | Passed |
| control: untagged words ignored | [] | [] | Passed |
SHA-256 / 88c624baa790711c052bb22c1a40d1cd2a55316d728faa810ff124ef93b1a39d
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:28.144674+00:00.
Case digest / a23c772edca7a80c2d27fa55c6ef1bc8eeda717c2723734e59960952bf5d5ea4