FAILURE MAP
← Case archive

FA-90571 / Garbage collector invariants / Open access

Conservative scan: tag bits left on candidate addresses · case 01

Exact references never match an object start, so objects referenced from the stack are not pinned.

Verified by executionVariant 1 · 7 checks per implementationDownload source bundle ↓JSON ↗

ROOT CAUSE

The tag is not removed before the address lookup.

THE FAILURE

The tag is not removed before the address lookup.

Unsuccessful approach: Clearing only the lowest bit leaves the address two bytes off.

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
        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 fixtureActualExpectedOutcome
regression: tagged start pointers only[][320, 352]Failed
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]Failed
control: untagged words ignored[][]Passed

SHA-256 / 0fa9ea61a6e7bd8489682727c82e168e0301c9061864c15d37884e240f483c79

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 & ~1
        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 fixtureActualExpectedOutcome
regression: tagged start pointers only[][320, 352]Failed
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]Failed
control: untagged words ignored[][]Passed

SHA-256 / d7d8d0905f3c54d4f1353067e686d10237d42a6b68e65cb4032aa133eef4dbed

HELD IN THE MEMBER ARCHIVE

The verified repair and its recorded checks are member-only.

This mechanism has 7 recorded checks per implementation. The open-access tier publishes the failure and the unsuccessful fix; the repaired source that passes every check, and the observations that prove it, are available to members.

Every case sharing this mechanism uses the same contract and the same repair, so this one record is held back for all of them.

Member access is invitation-based. Sign in with your invited account to inspect the repair.

Sign in to the archive ↗

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 / 75f4c40478f005a56a3496a12dfcb677b5313da5896be868212ad9af89a0c7f6