FA-90581 / Garbage collector invariants / Open access
Conservative scan: interior pointers accepted when disabled · case 01
Configurations that only recognise object-start pointers pin objects through interior addresses.
ROOT CAUSE
The interior-pointer flag is not consulted.
VERIFIED REPAIR
Only accept interior addresses when interior pointers are enabled.
Unsuccessful approach: Or-ing in the flag makes every in-heap address pin when interior pointers are on, including gaps.
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 not alloc[s]:
continue
if a == s or (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 | [352, 416] | [] | Failed |
| 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 / b6843565b0c54666591d85db917e5f6485304cd53006c1c31879873d7c2a03a4
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]:
continue
if a == s or (interior or a - s < 8):
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 | [352] | [] | Failed |
| pointers to a free block | [] | [] | Passed |
| pointer exactly at a later object start | [416] | [416] | Passed |
| control: untagged words ignored | [] | [] | Passed |
SHA-256 / 380b32416a137e60814bc3225544616e8090059e84fdd05505b9037ebf5a37aa
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:27.969907+00:00.
Case digest / 2822204d9b62b88903afbb577a20c875b1645de5a13d6c9af8692e012129c4db