FAILURE MAP
← Case archive

FA-90696 / Garbage collector invariants / Open access

Block offset table: back-skips always point one card back · case 01

Lookups deep inside large objects take one hop per card and the table encoding differs from the contract.

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

ROOT CAUSE

Every spanned card stores -1 instead of the distance to the object's start card.

VERIFIED REPAIR

Store the full distance back to the card where the object starts.

Unsuccessful approach: Storing one less makes the first spanned card look like it contains an object start at offset 0.

Case contract

A contiguous heap of [start, size] objects is covered by cards of the given size. For each card the table stores the offset of the first object that starts inside the card; a card with no object start that is covered by an object from card c stores -(k - c), a direct back-skip to that card. To find the object containing address q: from q's card follow back-skips; if the card's first start lies after q, move to the previous card; then walk objects forward until one contains q (an entry that does not land on an object start yields corrupt-table). Return the table and the owner start for each query.

Why this case matters

Card scanning needs to locate object starts quickly; a stale or wrong table misparses the heap.

1 / The failure

Exit 1
"""Failure Map reference implementation. Python standard library only."""
import json

N = 1
observations = []
def solve(objs, card, heap_end, queries):
    size_of = {s: z for s, z in objs}
    ncards = (heap_end + card - 1) // card
    table = [None] * ncards
    for start, size in sorted(objs):
        c = start // card
        if table[c] is None or table[c] < 0:
            table[c] = start - c * card
        last = (start + size - 1) // card
        for k in range(c + 1, min(last, ncards - 1) + 1):
            if table[k] is None:
                table[k] = -1
    def owner(q):
        c = q // card
        while c >= 0:
            e = table[c]
            if e is None:
                return None
            if e < 0:
                c += e
                continue
            a = c * card + e
            if a not in size_of:
                return 'corrupt-table'
            if a > q:
                c -= 1
                continue
            while a + size_of[a] <= q:
                a += size_of[a]
                if a not in size_of:
                    return None
            return a
        return None
    return {'table': table, 'owners': [owner(q) for q in queries]}
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = [[('regression: owners across spanning objects',
   ([[0, 48], [48, 100], [148, 20], [168, 200], [368, 24], [392, 16], [408, 64]], 64, 472, [53, 318, 368]),
   {'owners': [48, 168, 368], 'table': [0, -1, 20, -1, -2, 48, 8, -1]}),
  ('addresses just before a card-internal start',
   ([[0, 48], [48, 100], [148, 20], [168, 200], [368, 24], [392, 16], [408, 64]],
    64,
    472,
    [47, 147, 167, 367, 391, 407]),
   {'owners': [0, 48, 148, 168, 368, 392], 'table': [0, -1, 20, -1, -2, 48, 8, -1]}),
  ('first address of every card',
   ([[0, 48], [48, 100], [148, 20], [168, 200], [368, 24], [392, 16], [408, 64]],
    64,
    472,
    [0, 64, 128, 192, 256, 320, 384, 448]),
   {'owners': [0, 48, 48, 168, 168, 168, 368, 408], 'table': [0, -1, 20, -1, -2, 48, 8, -1]}),
  ('object ends and starts',
   ([[0, 48], [48, 100], [148, 20], [168, 200], [368, 24], [392, 16], [408, 64]],
    64,
    472,
    [147, 148, 168, 391, 408]),
   {'owners': [48, 148, 168, 368, 408], 'table': [0, -1, 20, -1, -2, 48, 8, -1]}),
  ('smaller cards',
   ([[0, 48], [48, 100], [148, 20], [168, 200], [368, 24], [392, 16], [408, 64]], 32, 472, [238, 411, 5]),
   {'owners': [168, 408, 0], 'table': [0, 16, -1, -2, 20, 8, -1, -2, -3, -4, -5, 16, 8, -1, -2]}),
  ('control: single object heap',
   ([[0, 264]], 64, 264, [0, 100, 255]),
   {'owners': [0, 0, 0], 'table': [0, -1, -2, -3, -4]})],
 [('regression: owners across spanning objects',
   ([[0, 56], [56, 100], [156, 20], [176, 200], [376, 24], [400, 16], [416, 64]], 64, 480, [61, 326, 376]),
   {'owners': [56, 176, 376], 'table': [0, -1, 28, -1, -2, 56, 16, -1]}),
  ('addresses just before a card-internal start',
   ([[0, 56], [56, 100], [156, 20], [176, 200], [376, 24], [400, 16], [416, 64]],
    64,
    480,
    [55, 155, 175, 375, 399, 415]),
   {'owners': [0, 56, 156, 176, 376, 400], 'table': [0, -1, 28, -1, -2, 56, 16, -1]}),
  ('first address of every card',
   ([[0, 56], [56, 100], [156, 20], [176, 200], [376, 24], [400, 16], [416, 64]],
    64,
    480,
    [0, 64, 128, 192, 256, 320, 384, 448]),
   {'owners': [0, 56, 56, 176, 176, 176, 376, 416], 'table': [0, -1, 28, -1, -2, 56, 16, -1]}),
  ('object ends and starts',
   ([[0, 56], [56, 100], [156, 20], [176, 200], [376, 24], [400, 16], [416, 64]],
    64,
    480,
    [155, 156, 176, 399, 416]),
   {'owners': [56, 156, 176, 376, 416], 'table': [0, -1, 28, -1, -2, 56, 16, -1]}),
  ('smaller cards',
   ([[0, 56], [56, 100], [156, 20], [176, 200], [376, 24], [400, 16], [416, 64]], 32, 480, [246, 419, 5]),
   {'owners': [176, 416, 0], 'table': [0, 24, -1, -2, 28, 16, -1, -2, -3, -4, -5, 24, 16, 0, -1]}),
  ('control: single object heap',
   ([[0, 272]], 64, 272, [0, 100, 255]),
   {'owners': [0, 0, 0], 'table': [0, -1, -2, -3, -4]})],
 [('regression: owners across spanning objects',
   ([[0, 64], [64, 100], [164, 20], [184, 200], [384, 24], [408, 16], [424, 64]], 64, 488, [69, 334, 384]),
   {'owners': [64, 184, 384], 'table': [0, 0, 36, -1, -2, -3, 0, -1]}),
  ('addresses just before a card-internal start',
   ([[0, 64], [64, 100], [164, 20], [184, 200], [384, 24], [408, 16], [424, 64]],
    64,
    488,
    [63, 163, 183, 383, 407, 423]),
   {'owners': [0, 64, 164, 184, 384, 408], 'table': [0, 0, 36, -1, -2, -3, 0, -1]}),
  ('first address of every card',
   ([[0, 64], [64, 100], [164, 20], [184, 200], [384, 24], [408, 16], [424, 64]],
    64,
    488,
    [0, 64, 128, 192, 256, 320, 384, 448]),
   {'owners': [0, 64, 64, 184, 184, 184, 384, 424], 'table': [0, 0, 36, -1, -2, -3, 0, -1]}),
  ('object ends and starts',
   ([[0, 64], [64, 100], [164, 20], [184, 200], [384, 24], [408, 16], [424, 64]],
    64,
    488,
    [163, 164, 184, 407, 424]),
   {'owners': [64, 164, 184, 384, 424], 'table': [0, 0, 36, -1, -2, -3, 0, -1]}),
  ('smaller cards',
   ([[0, 64], [64, 100], [164, 20], [184, 200], [384, 24], [408, 16], [424, 64]], 32, 488, [254, 427, 5]),
   {'owners': [184, 424, 0], 'table': [0, -1, 0, -1, -2, 4, -1, -2, -3, -4, -5, -6, 0, 8, -1, -2]}),
  ('control: single object heap',
   ([[0, 280]], 64, 280, [0, 100, 255]),
   {'owners': [0, 0, 0], 'table': [0, -1, -2, -3, -4]})],
 [('regression: owners across spanning objects',
   ([[0, 72], [72, 100], [172, 20], [192, 200], [392, 24], [416, 16], [432, 64]], 64, 496, [77, 342, 392]),
   {'owners': [72, 192, 392], 'table': [0, 8, 44, 0, -1, -2, 8, -1]}),
  ('addresses just before a card-internal start',
   ([[0, 72], [72, 100], [172, 20], [192, 200], [392, 24], [416, 16], [432, 64]],
    64,
    496,
    [71, 171, 191, 391, 415, 431]),
   {'owners': [0, 72, 172, 192, 392, 416], 'table': [0, 8, 44, 0, -1, -2, 8, -1]}),
  ('first address of every card',
   ([[0, 72], [72, 100], [172, 20], [192, 200], [392, 24], [416, 16], [432, 64]],
    64,
    496,
    [0, 64, 128, 192, 256, 320, 384, 448]),
   {'owners': [0, 0, 72, 192, 192, 192, 192, 432], 'table': [0, 8, 44, 0, -1, -2, 8, -1]}),
  ('object ends and starts',
   ([[0, 72], [72, 100], [172, 20], [192, 200], [392, 24], [416, 16], [432, 64]],
    64,
    496,
    [171, 172, 192, 415, 432]),
   {'owners': [72, 172, 192, 392, 432], 'table': [0, 8, 44, 0, -1, -2, 8, -1]}),
  ('smaller cards',
   ([[0, 72], [72, 100], [172, 20], [192, 200], [392, 24], [416, 16], [432, 64]], 32, 496, [262, 435, 5]),
   {'owners': [192, 432, 0], 'table': [0, -1, 8, -1, -2, 12, 0, -1, -2, -3, -4, -5, 8, 0, -1, -2]}),
  ('control: single object heap',
   ([[0, 288]], 64, 288, [0, 100, 255]),
   {'owners': [0, 0, 0], 'table': [0, -1, -2, -3, -4]})],
 [('regression: owners across spanning objects',
   ([[0, 80], [80, 100], [180, 20], [200, 200], [400, 24], [424, 16], [440, 64]], 64, 504, [85, 350, 400]),
   {'owners': [80, 200, 400], 'table': [0, 16, 52, 8, -1, -2, 16, -1]}),
  ('addresses just before a card-internal start',
   ([[0, 80], [80, 100], [180, 20], [200, 200], [400, 24], [424, 16], [440, 64]],
    64,
    504,
    [79, 179, 199, 399, 423, 439]),
   {'owners': [0, 80, 180, 200, 400, 424], 'table': [0, 16, 52, 8, -1, -2, 16, -1]}),
  ('first address of every card',
   ([[0, 80], [80, 100], [180, 20], [200, 200], [400, 24], [424, 16], [440, 64]],
    64,
    504,
    [0, 64, 128, 192, 256, 320, 384, 448]),
   {'owners': [0, 0, 80, 180, 200, 200, 200, 440], 'table': [0, 16, 52, 8, -1, -2, 16, -1]}),
  ('object ends and starts',
   ([[0, 80], [80, 100], [180, 20], [200, 200], [400, 24], [424, 16], [440, 64]],
    64,
    504,
    [179, 180, 200, 423, 440]),
   {'owners': [80, 180, 200, 400, 440], 'table': [0, 16, 52, 8, -1, -2, 16, -1]}),
  ('smaller cards',
   ([[0, 80], [80, 100], [180, 20], [200, 200], [400, 24], [424, 16], [440, 64]], 32, 504, [270, 443, 5]),
   {'owners': [200, 440, 0], 'table': [0, -1, 16, -1, -2, 20, 8, -1, -2, -3, -4, -5, 16, 8, -1, -2]}),
  ('control: single object heap',
   ([[0, 296]], 64, 296, [0, 100, 255]),
   {'owners': [0, 0, 0], 'table': [0, -1, -2, -3, -4]})]]
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: owners across spanning objects{'owners': [48, 168, 368], 'table': [0, -1, 20, -1, -1, 48, 8, -1]}{'owners': [48, 168, 368], 'table': [0, -1, 20, -1, -2, 48, 8, -1]}Failed
addresses just before a card-internal start{'owners': [0, 48, 148, 168, 368, 392], 'table': [0, -1, 20, -1, -1, 48, 8, -1]}{'owners': [0, 48, 148, 168, 368, 392], 'table': [0, -1, 20, -1, -2, 48, 8, -1]}Failed
first address of every card{'owners': [0, 48, 48, 168, 168, 168, 368, 408], 'table': [0, -1, 20, -1, -1, 48, 8, -1]}{'owners': [0, 48, 48, 168, 168, 168, 368, 408], 'table': [0, -1, 20, -1, -2, 48, 8, -1]}Failed
object ends and starts{'owners': [48, 148, 168, 368, 408], 'table': [0, -1, 20, -1, -1, 48, 8, -1]}{'owners': [48, 148, 168, 368, 408], 'table': [0, -1, 20, -1, -2, 48, 8, -1]}Failed
smaller cards{'owners': [168, 408, 0], 'table': [0, 16, -1, -1, 20, 8, -1, -1, -1, -1, -1, 16, 8, -1, -1]}{'owners': [168, 408, 0], 'table': [0, 16, -1, -2, 20, 8, -1, -2, -3, -4, -5, 16, 8, -1, -2]}Failed
control: single object heap{'owners': [0, 0, 0], 'table': [0, -1, -1, -1, -1]}{'owners': [0, 0, 0], 'table': [0, -1, -2, -3, -4]}Failed

SHA-256 / b2562c2d9ad9e6b7b482fc77870c1101b6763f15cf52407e2823af7a59175d00

2 / The unsuccessful fix

Exit 1
"""Failure Map reference implementation. Python standard library only."""
import json

N = 1
observations = []
def solve(objs, card, heap_end, queries):
    size_of = {s: z for s, z in objs}
    ncards = (heap_end + card - 1) // card
    table = [None] * ncards
    for start, size in sorted(objs):
        c = start // card
        if table[c] is None or table[c] < 0:
            table[c] = start - c * card
        last = (start + size - 1) // card
        for k in range(c + 1, min(last, ncards - 1) + 1):
            if table[k] is None:
                table[k] = -(k - c - 1)
    def owner(q):
        c = q // card
        while c >= 0:
            e = table[c]
            if e is None:
                return None
            if e < 0:
                c += e
                continue
            a = c * card + e
            if a not in size_of:
                return 'corrupt-table'
            if a > q:
                c -= 1
                continue
            while a + size_of[a] <= q:
                a += size_of[a]
                if a not in size_of:
                    return None
            return a
        return None
    return {'table': table, 'owners': [owner(q) for q in queries]}
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = [[('regression: owners across spanning objects',
   ([[0, 48], [48, 100], [148, 20], [168, 200], [368, 24], [392, 16], [408, 64]], 64, 472, [53, 318, 368]),
   {'owners': [48, 168, 368], 'table': [0, -1, 20, -1, -2, 48, 8, -1]}),
  ('addresses just before a card-internal start',
   ([[0, 48], [48, 100], [148, 20], [168, 200], [368, 24], [392, 16], [408, 64]],
    64,
    472,
    [47, 147, 167, 367, 391, 407]),
   {'owners': [0, 48, 148, 168, 368, 392], 'table': [0, -1, 20, -1, -2, 48, 8, -1]}),
  ('first address of every card',
   ([[0, 48], [48, 100], [148, 20], [168, 200], [368, 24], [392, 16], [408, 64]],
    64,
    472,
    [0, 64, 128, 192, 256, 320, 384, 448]),
   {'owners': [0, 48, 48, 168, 168, 168, 368, 408], 'table': [0, -1, 20, -1, -2, 48, 8, -1]}),
  ('object ends and starts',
   ([[0, 48], [48, 100], [148, 20], [168, 200], [368, 24], [392, 16], [408, 64]],
    64,
    472,
    [147, 148, 168, 391, 408]),
   {'owners': [48, 148, 168, 368, 408], 'table': [0, -1, 20, -1, -2, 48, 8, -1]}),
  ('smaller cards',
   ([[0, 48], [48, 100], [148, 20], [168, 200], [368, 24], [392, 16], [408, 64]], 32, 472, [238, 411, 5]),
   {'owners': [168, 408, 0], 'table': [0, 16, -1, -2, 20, 8, -1, -2, -3, -4, -5, 16, 8, -1, -2]}),
  ('control: single object heap',
   ([[0, 264]], 64, 264, [0, 100, 255]),
   {'owners': [0, 0, 0], 'table': [0, -1, -2, -3, -4]})],
 [('regression: owners across spanning objects',
   ([[0, 56], [56, 100], [156, 20], [176, 200], [376, 24], [400, 16], [416, 64]], 64, 480, [61, 326, 376]),
   {'owners': [56, 176, 376], 'table': [0, -1, 28, -1, -2, 56, 16, -1]}),
  ('addresses just before a card-internal start',
   ([[0, 56], [56, 100], [156, 20], [176, 200], [376, 24], [400, 16], [416, 64]],
    64,
    480,
    [55, 155, 175, 375, 399, 415]),
   {'owners': [0, 56, 156, 176, 376, 400], 'table': [0, -1, 28, -1, -2, 56, 16, -1]}),
  ('first address of every card',
   ([[0, 56], [56, 100], [156, 20], [176, 200], [376, 24], [400, 16], [416, 64]],
    64,
    480,
    [0, 64, 128, 192, 256, 320, 384, 448]),
   {'owners': [0, 56, 56, 176, 176, 176, 376, 416], 'table': [0, -1, 28, -1, -2, 56, 16, -1]}),
  ('object ends and starts',
   ([[0, 56], [56, 100], [156, 20], [176, 200], [376, 24], [400, 16], [416, 64]],
    64,
    480,
    [155, 156, 176, 399, 416]),
   {'owners': [56, 156, 176, 376, 416], 'table': [0, -1, 28, -1, -2, 56, 16, -1]}),
  ('smaller cards',
   ([[0, 56], [56, 100], [156, 20], [176, 200], [376, 24], [400, 16], [416, 64]], 32, 480, [246, 419, 5]),
   {'owners': [176, 416, 0], 'table': [0, 24, -1, -2, 28, 16, -1, -2, -3, -4, -5, 24, 16, 0, -1]}),
  ('control: single object heap',
   ([[0, 272]], 64, 272, [0, 100, 255]),
   {'owners': [0, 0, 0], 'table': [0, -1, -2, -3, -4]})],
 [('regression: owners across spanning objects',
   ([[0, 64], [64, 100], [164, 20], [184, 200], [384, 24], [408, 16], [424, 64]], 64, 488, [69, 334, 384]),
   {'owners': [64, 184, 384], 'table': [0, 0, 36, -1, -2, -3, 0, -1]}),
  ('addresses just before a card-internal start',
   ([[0, 64], [64, 100], [164, 20], [184, 200], [384, 24], [408, 16], [424, 64]],
    64,
    488,
    [63, 163, 183, 383, 407, 423]),
   {'owners': [0, 64, 164, 184, 384, 408], 'table': [0, 0, 36, -1, -2, -3, 0, -1]}),
  ('first address of every card',
   ([[0, 64], [64, 100], [164, 20], [184, 200], [384, 24], [408, 16], [424, 64]],
    64,
    488,
    [0, 64, 128, 192, 256, 320, 384, 448]),
   {'owners': [0, 64, 64, 184, 184, 184, 384, 424], 'table': [0, 0, 36, -1, -2, -3, 0, -1]}),
  ('object ends and starts',
   ([[0, 64], [64, 100], [164, 20], [184, 200], [384, 24], [408, 16], [424, 64]],
    64,
    488,
    [163, 164, 184, 407, 424]),
   {'owners': [64, 164, 184, 384, 424], 'table': [0, 0, 36, -1, -2, -3, 0, -1]}),
  ('smaller cards',
   ([[0, 64], [64, 100], [164, 20], [184, 200], [384, 24], [408, 16], [424, 64]], 32, 488, [254, 427, 5]),
   {'owners': [184, 424, 0], 'table': [0, -1, 0, -1, -2, 4, -1, -2, -3, -4, -5, -6, 0, 8, -1, -2]}),
  ('control: single object heap',
   ([[0, 280]], 64, 280, [0, 100, 255]),
   {'owners': [0, 0, 0], 'table': [0, -1, -2, -3, -4]})],
 [('regression: owners across spanning objects',
   ([[0, 72], [72, 100], [172, 20], [192, 200], [392, 24], [416, 16], [432, 64]], 64, 496, [77, 342, 392]),
   {'owners': [72, 192, 392], 'table': [0, 8, 44, 0, -1, -2, 8, -1]}),
  ('addresses just before a card-internal start',
   ([[0, 72], [72, 100], [172, 20], [192, 200], [392, 24], [416, 16], [432, 64]],
    64,
    496,
    [71, 171, 191, 391, 415, 431]),
   {'owners': [0, 72, 172, 192, 392, 416], 'table': [0, 8, 44, 0, -1, -2, 8, -1]}),
  ('first address of every card',
   ([[0, 72], [72, 100], [172, 20], [192, 200], [392, 24], [416, 16], [432, 64]],
    64,
    496,
    [0, 64, 128, 192, 256, 320, 384, 448]),
   {'owners': [0, 0, 72, 192, 192, 192, 192, 432], 'table': [0, 8, 44, 0, -1, -2, 8, -1]}),
  ('object ends and starts',
   ([[0, 72], [72, 100], [172, 20], [192, 200], [392, 24], [416, 16], [432, 64]],
    64,
    496,
    [171, 172, 192, 415, 432]),
   {'owners': [72, 172, 192, 392, 432], 'table': [0, 8, 44, 0, -1, -2, 8, -1]}),
  ('smaller cards',
   ([[0, 72], [72, 100], [172, 20], [192, 200], [392, 24], [416, 16], [432, 64]], 32, 496, [262, 435, 5]),
   {'owners': [192, 432, 0], 'table': [0, -1, 8, -1, -2, 12, 0, -1, -2, -3, -4, -5, 8, 0, -1, -2]}),
  ('control: single object heap',
   ([[0, 288]], 64, 288, [0, 100, 255]),
   {'owners': [0, 0, 0], 'table': [0, -1, -2, -3, -4]})],
 [('regression: owners across spanning objects',
   ([[0, 80], [80, 100], [180, 20], [200, 200], [400, 24], [424, 16], [440, 64]], 64, 504, [85, 350, 400]),
   {'owners': [80, 200, 400], 'table': [0, 16, 52, 8, -1, -2, 16, -1]}),
  ('addresses just before a card-internal start',
   ([[0, 80], [80, 100], [180, 20], [200, 200], [400, 24], [424, 16], [440, 64]],
    64,
    504,
    [79, 179, 199, 399, 423, 439]),
   {'owners': [0, 80, 180, 200, 400, 424], 'table': [0, 16, 52, 8, -1, -2, 16, -1]}),
  ('first address of every card',
   ([[0, 80], [80, 100], [180, 20], [200, 200], [400, 24], [424, 16], [440, 64]],
    64,
    504,
    [0, 64, 128, 192, 256, 320, 384, 448]),
   {'owners': [0, 0, 80, 180, 200, 200, 200, 440], 'table': [0, 16, 52, 8, -1, -2, 16, -1]}),
  ('object ends and starts',
   ([[0, 80], [80, 100], [180, 20], [200, 200], [400, 24], [424, 16], [440, 64]],
    64,
    504,
    [179, 180, 200, 423, 440]),
   {'owners': [80, 180, 200, 400, 440], 'table': [0, 16, 52, 8, -1, -2, 16, -1]}),
  ('smaller cards',
   ([[0, 80], [80, 100], [180, 20], [200, 200], [400, 24], [424, 16], [440, 64]], 32, 504, [270, 443, 5]),
   {'owners': [200, 440, 0], 'table': [0, -1, 16, -1, -2, 20, 8, -1, -2, -3, -4, -5, 16, 8, -1, -2]}),
  ('control: single object heap',
   ([[0, 296]], 64, 296, [0, 100, 255]),
   {'owners': [0, 0, 0], 'table': [0, -1, -2, -3, -4]})]]
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: owners across spanning objects{'owners': [48, 'corrupt-table', 368], 'table': [0, 0, 20, 0, -1, 48, 0, 0]}{'owners': [48, 168, 368], 'table': [0, -1, 20, -1, -2, 48, 8, -1]}Failed
addresses just before a card-internal start{'owners': [0, 'corrupt-table', 148, 'corrupt-table', 'corrupt-table', 'corrupt-table'], 'table': [0, 0, 20, 0, -1, 48, 0, 0]}{'owners': [0, 48, 148, 168, 368, 392], 'table': [0, -1, 20, -1, -2, 48, 8, -1]}Failed
first address of every card{'owners': [0, 'corrupt-table', 'corrupt-table', 'corrupt-table', 'corrupt-table', 'corrupt-table', 'corrupt-table', 'corrupt-table'], 'table': [0, 0, 20, 0, -1, 48, 0, 0]}{'owners': [0, 48, 48, 168, 168, 168, 368, 408], 'table': [0, -1, 20, -1, -2, 48, 8, -1]}Failed
object ends and starts{'owners': ['corrupt-table', 148, 168, 'corrupt-table', 'corrupt-table'], 'table': [0, 0, 20, 0, -1, 48, 0, 0]}{'owners': [48, 148, 168, 368, 408], 'table': [0, -1, 20, -1, -2, 48, 8, -1]}Failed
smaller cards{'owners': ['corrupt-table', 'corrupt-table', 0], 'table': [0, 0, 0, -1, 20, 0, 0, -1, -2, -3, -4, 16, 0, 0, -1]}{'owners': [168, 408, 0], 'table': [0, 16, -1, -2, 20, 8, -1, -2, -3, -4, -5, 16, 8, -1, -2]}Failed
control: single object heap{'owners': [0, 'corrupt-table', 'corrupt-table'], 'table': [0, 0, -1, -2, -3]}{'owners': [0, 0, 0], 'table': [0, -1, -2, -3, -4]}Failed

SHA-256 / 043f2361fbc7f163c9e339145c2098eaf6af2562c9515061e96378796353efb3

3 / The verified repair

Exit 0
"""Failure Map reference implementation. Python standard library only."""
import json

N = 1
observations = []
def solve(objs, card, heap_end, queries):
    size_of = {s: z for s, z in objs}
    ncards = (heap_end + card - 1) // card
    table = [None] * ncards
    for start, size in sorted(objs):
        c = start // card
        if table[c] is None or table[c] < 0:
            table[c] = start - c * card
        last = (start + size - 1) // card
        for k in range(c + 1, min(last, ncards - 1) + 1):
            if table[k] is None:
                table[k] = -(k - c)
    def owner(q):
        c = q // card
        while c >= 0:
            e = table[c]
            if e is None:
                return None
            if e < 0:
                c += e
                continue
            a = c * card + e
            if a not in size_of:
                return 'corrupt-table'
            if a > q:
                c -= 1
                continue
            while a + size_of[a] <= q:
                a += size_of[a]
                if a not in size_of:
                    return None
            return a
        return None
    return {'table': table, 'owners': [owner(q) for q in queries]}
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = [[('regression: owners across spanning objects',
   ([[0, 48], [48, 100], [148, 20], [168, 200], [368, 24], [392, 16], [408, 64]], 64, 472, [53, 318, 368]),
   {'owners': [48, 168, 368], 'table': [0, -1, 20, -1, -2, 48, 8, -1]}),
  ('addresses just before a card-internal start',
   ([[0, 48], [48, 100], [148, 20], [168, 200], [368, 24], [392, 16], [408, 64]],
    64,
    472,
    [47, 147, 167, 367, 391, 407]),
   {'owners': [0, 48, 148, 168, 368, 392], 'table': [0, -1, 20, -1, -2, 48, 8, -1]}),
  ('first address of every card',
   ([[0, 48], [48, 100], [148, 20], [168, 200], [368, 24], [392, 16], [408, 64]],
    64,
    472,
    [0, 64, 128, 192, 256, 320, 384, 448]),
   {'owners': [0, 48, 48, 168, 168, 168, 368, 408], 'table': [0, -1, 20, -1, -2, 48, 8, -1]}),
  ('object ends and starts',
   ([[0, 48], [48, 100], [148, 20], [168, 200], [368, 24], [392, 16], [408, 64]],
    64,
    472,
    [147, 148, 168, 391, 408]),
   {'owners': [48, 148, 168, 368, 408], 'table': [0, -1, 20, -1, -2, 48, 8, -1]}),
  ('smaller cards',
   ([[0, 48], [48, 100], [148, 20], [168, 200], [368, 24], [392, 16], [408, 64]], 32, 472, [238, 411, 5]),
   {'owners': [168, 408, 0], 'table': [0, 16, -1, -2, 20, 8, -1, -2, -3, -4, -5, 16, 8, -1, -2]}),
  ('control: single object heap',
   ([[0, 264]], 64, 264, [0, 100, 255]),
   {'owners': [0, 0, 0], 'table': [0, -1, -2, -3, -4]})],
 [('regression: owners across spanning objects',
   ([[0, 56], [56, 100], [156, 20], [176, 200], [376, 24], [400, 16], [416, 64]], 64, 480, [61, 326, 376]),
   {'owners': [56, 176, 376], 'table': [0, -1, 28, -1, -2, 56, 16, -1]}),
  ('addresses just before a card-internal start',
   ([[0, 56], [56, 100], [156, 20], [176, 200], [376, 24], [400, 16], [416, 64]],
    64,
    480,
    [55, 155, 175, 375, 399, 415]),
   {'owners': [0, 56, 156, 176, 376, 400], 'table': [0, -1, 28, -1, -2, 56, 16, -1]}),
  ('first address of every card',
   ([[0, 56], [56, 100], [156, 20], [176, 200], [376, 24], [400, 16], [416, 64]],
    64,
    480,
    [0, 64, 128, 192, 256, 320, 384, 448]),
   {'owners': [0, 56, 56, 176, 176, 176, 376, 416], 'table': [0, -1, 28, -1, -2, 56, 16, -1]}),
  ('object ends and starts',
   ([[0, 56], [56, 100], [156, 20], [176, 200], [376, 24], [400, 16], [416, 64]],
    64,
    480,
    [155, 156, 176, 399, 416]),
   {'owners': [56, 156, 176, 376, 416], 'table': [0, -1, 28, -1, -2, 56, 16, -1]}),
  ('smaller cards',
   ([[0, 56], [56, 100], [156, 20], [176, 200], [376, 24], [400, 16], [416, 64]], 32, 480, [246, 419, 5]),
   {'owners': [176, 416, 0], 'table': [0, 24, -1, -2, 28, 16, -1, -2, -3, -4, -5, 24, 16, 0, -1]}),
  ('control: single object heap',
   ([[0, 272]], 64, 272, [0, 100, 255]),
   {'owners': [0, 0, 0], 'table': [0, -1, -2, -3, -4]})],
 [('regression: owners across spanning objects',
   ([[0, 64], [64, 100], [164, 20], [184, 200], [384, 24], [408, 16], [424, 64]], 64, 488, [69, 334, 384]),
   {'owners': [64, 184, 384], 'table': [0, 0, 36, -1, -2, -3, 0, -1]}),
  ('addresses just before a card-internal start',
   ([[0, 64], [64, 100], [164, 20], [184, 200], [384, 24], [408, 16], [424, 64]],
    64,
    488,
    [63, 163, 183, 383, 407, 423]),
   {'owners': [0, 64, 164, 184, 384, 408], 'table': [0, 0, 36, -1, -2, -3, 0, -1]}),
  ('first address of every card',
   ([[0, 64], [64, 100], [164, 20], [184, 200], [384, 24], [408, 16], [424, 64]],
    64,
    488,
    [0, 64, 128, 192, 256, 320, 384, 448]),
   {'owners': [0, 64, 64, 184, 184, 184, 384, 424], 'table': [0, 0, 36, -1, -2, -3, 0, -1]}),
  ('object ends and starts',
   ([[0, 64], [64, 100], [164, 20], [184, 200], [384, 24], [408, 16], [424, 64]],
    64,
    488,
    [163, 164, 184, 407, 424]),
   {'owners': [64, 164, 184, 384, 424], 'table': [0, 0, 36, -1, -2, -3, 0, -1]}),
  ('smaller cards',
   ([[0, 64], [64, 100], [164, 20], [184, 200], [384, 24], [408, 16], [424, 64]], 32, 488, [254, 427, 5]),
   {'owners': [184, 424, 0], 'table': [0, -1, 0, -1, -2, 4, -1, -2, -3, -4, -5, -6, 0, 8, -1, -2]}),
  ('control: single object heap',
   ([[0, 280]], 64, 280, [0, 100, 255]),
   {'owners': [0, 0, 0], 'table': [0, -1, -2, -3, -4]})],
 [('regression: owners across spanning objects',
   ([[0, 72], [72, 100], [172, 20], [192, 200], [392, 24], [416, 16], [432, 64]], 64, 496, [77, 342, 392]),
   {'owners': [72, 192, 392], 'table': [0, 8, 44, 0, -1, -2, 8, -1]}),
  ('addresses just before a card-internal start',
   ([[0, 72], [72, 100], [172, 20], [192, 200], [392, 24], [416, 16], [432, 64]],
    64,
    496,
    [71, 171, 191, 391, 415, 431]),
   {'owners': [0, 72, 172, 192, 392, 416], 'table': [0, 8, 44, 0, -1, -2, 8, -1]}),
  ('first address of every card',
   ([[0, 72], [72, 100], [172, 20], [192, 200], [392, 24], [416, 16], [432, 64]],
    64,
    496,
    [0, 64, 128, 192, 256, 320, 384, 448]),
   {'owners': [0, 0, 72, 192, 192, 192, 192, 432], 'table': [0, 8, 44, 0, -1, -2, 8, -1]}),
  ('object ends and starts',
   ([[0, 72], [72, 100], [172, 20], [192, 200], [392, 24], [416, 16], [432, 64]],
    64,
    496,
    [171, 172, 192, 415, 432]),
   {'owners': [72, 172, 192, 392, 432], 'table': [0, 8, 44, 0, -1, -2, 8, -1]}),
  ('smaller cards',
   ([[0, 72], [72, 100], [172, 20], [192, 200], [392, 24], [416, 16], [432, 64]], 32, 496, [262, 435, 5]),
   {'owners': [192, 432, 0], 'table': [0, -1, 8, -1, -2, 12, 0, -1, -2, -3, -4, -5, 8, 0, -1, -2]}),
  ('control: single object heap',
   ([[0, 288]], 64, 288, [0, 100, 255]),
   {'owners': [0, 0, 0], 'table': [0, -1, -2, -3, -4]})],
 [('regression: owners across spanning objects',
   ([[0, 80], [80, 100], [180, 20], [200, 200], [400, 24], [424, 16], [440, 64]], 64, 504, [85, 350, 400]),
   {'owners': [80, 200, 400], 'table': [0, 16, 52, 8, -1, -2, 16, -1]}),
  ('addresses just before a card-internal start',
   ([[0, 80], [80, 100], [180, 20], [200, 200], [400, 24], [424, 16], [440, 64]],
    64,
    504,
    [79, 179, 199, 399, 423, 439]),
   {'owners': [0, 80, 180, 200, 400, 424], 'table': [0, 16, 52, 8, -1, -2, 16, -1]}),
  ('first address of every card',
   ([[0, 80], [80, 100], [180, 20], [200, 200], [400, 24], [424, 16], [440, 64]],
    64,
    504,
    [0, 64, 128, 192, 256, 320, 384, 448]),
   {'owners': [0, 0, 80, 180, 200, 200, 200, 440], 'table': [0, 16, 52, 8, -1, -2, 16, -1]}),
  ('object ends and starts',
   ([[0, 80], [80, 100], [180, 20], [200, 200], [400, 24], [424, 16], [440, 64]],
    64,
    504,
    [179, 180, 200, 423, 440]),
   {'owners': [80, 180, 200, 400, 440], 'table': [0, 16, 52, 8, -1, -2, 16, -1]}),
  ('smaller cards',
   ([[0, 80], [80, 100], [180, 20], [200, 200], [400, 24], [424, 16], [440, 64]], 32, 504, [270, 443, 5]),
   {'owners': [200, 440, 0], 'table': [0, -1, 16, -1, -2, 20, 8, -1, -2, -3, -4, -5, 16, 8, -1, -2]}),
  ('control: single object heap',
   ([[0, 296]], 64, 296, [0, 100, 255]),
   {'owners': [0, 0, 0], 'table': [0, -1, -2, -3, -4]})]]
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: owners across spanning objects{'owners': [48, 168, 368], 'table': [0, -1, 20, -1, -2, 48, 8, -1]}{'owners': [48, 168, 368], 'table': [0, -1, 20, -1, -2, 48, 8, -1]}Passed
addresses just before a card-internal start{'owners': [0, 48, 148, 168, 368, 392], 'table': [0, -1, 20, -1, -2, 48, 8, -1]}{'owners': [0, 48, 148, 168, 368, 392], 'table': [0, -1, 20, -1, -2, 48, 8, -1]}Passed
first address of every card{'owners': [0, 48, 48, 168, 168, 168, 368, 408], 'table': [0, -1, 20, -1, -2, 48, 8, -1]}{'owners': [0, 48, 48, 168, 168, 168, 368, 408], 'table': [0, -1, 20, -1, -2, 48, 8, -1]}Passed
object ends and starts{'owners': [48, 148, 168, 368, 408], 'table': [0, -1, 20, -1, -2, 48, 8, -1]}{'owners': [48, 148, 168, 368, 408], 'table': [0, -1, 20, -1, -2, 48, 8, -1]}Passed
smaller cards{'owners': [168, 408, 0], 'table': [0, 16, -1, -2, 20, 8, -1, -2, -3, -4, -5, 16, 8, -1, -2]}{'owners': [168, 408, 0], 'table': [0, 16, -1, -2, 20, 8, -1, -2, -3, -4, -5, 16, 8, -1, -2]}Passed
control: single object heap{'owners': [0, 0, 0], 'table': [0, -1, -2, -3, -4]}{'owners': [0, 0, 0], 'table': [0, -1, -2, -3, -4]}Passed

SHA-256 / 429b796ebe6a29dc46c0d23387dc8dedec0954e5c693f7ebd64e4beef84bcdce

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:29.094101+00:00.

Case digest / 50a4a0ae7265d3a72b9e6f74f793a6f4e76797433b6f707965d8c2cdc107b16b