FAILURE MAP
← Case archive

FA-90381 / Garbage collector invariants / Open access

Reference counting: control block freed while weak references remain · case 01

A later upgrade or unweak through a surviving weak reference touches freed memory.

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

ROOT CAUSE

Destruction deallocates the block by testing the strong count, which is always zero there.

VERIFIED REPAIR

Keep the block until the weak count is zero as well.

Unsuccessful approach: Tolerating one outstanding weak reference still frees the block under it.

Case contract

Objects carry a strong count and a weak count. new id k: strong 1 (the creating reference), k null fields. drop id: release one strong reference. store src i dst: retain dst, then write, then release the old value. When the strong count reaches 0 the object is destroyed (recorded in freed, its fields released recursively in field order) and, if no weak references remain, its control block is deallocated too; unweak deallocates a destroyed object's block when the last weak reference goes. upgrade id succeeds (and adds a strong reference) only while the strong count is positive. Touching a deallocated block reports "use-after-free".

Why this case matters

Reference-counting collectors must order retains and releases and separate destruction from deallocation.

1 / The failure

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

N = 1
observations = []
def solve(events):
    objs = {}
    freed = []
    dealloc = []
    out = []
    def release(o):
        if o is None:
            return
        b = objs[o]
        b['rc'] -= 1
        if b['rc'] == 0:
            freed.append(o)
            kids, b['fields'] = b['fields'], []
            if b['rc'] == 0:
                dealloc.append(o)
                del objs[o]
            for c in kids:
                release(c)
    try:
        for ev in events:
            op = ev[0]
            if op == 'new':
                objs[ev[1]] = {'rc': 1, 'weak': 0, 'fields': [None] * ev[2]}
            elif op == 'drop':
                release(ev[1])
            elif op == 'store':
                _, src, field, dst = ev
                if dst is not None:
                    objs[dst]['rc'] += 1
                old = objs[src]['fields'][field]
                objs[src]['fields'][field] = dst
                release(old)
            elif op == 'weak':
                objs[ev[1]]['weak'] += 1
            elif op == 'unweak':
                b = objs[ev[1]]
                b['weak'] -= 1
                if b['weak'] == 0 and b['rc'] == 0:
                    dealloc.append(ev[1])
                    del objs[ev[1]]
            else:
                b = objs[ev[1]]
                if b['rc'] > 0:
                    b['rc'] += 1
                    out.append(True)
                else:
                    out.append(False)
    except (KeyError, IndexError):
        out.append('use-after-free')
    return {'out': out, 'freed': freed, 'dealloc': dealloc,
            'rc': {str(k): [v['rc'], v['weak']] for k, v in sorted(objs.items())}}
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = [[('regression: overwrite with a child of the old value',
   ([['new', 11, 1],
     ['new', 12, 1],
     ['new', 13, 0],
     ['store', 12, 0, 13],
     ['drop', 13],
     ['store', 11, 0, 12],
     ['drop', 12],
     ['store', 11, 0, 13]],),
   {'dealloc': [12], 'freed': [12], 'out': [], 'rc': {'11': [1, 0], '13': [1, 0]}}),
  ('self-assignment of the only reference',
   ([['new', 11, 1],
     ['new', 12, 0],
     ['store', 11, 0, 12],
     ['drop', 12],
     ['store', 11, 0, 12],
     ['upgrade', 12]],),
   {'dealloc': [], 'freed': [], 'out': [True], 'rc': {'11': [1, 0], '12': [2, 0]}}),
  ('object referenced twice by one parent',
   ([['new', 11, 2],
     ['new', 12, 0],
     ['store', 11, 0, 12],
     ['store', 11, 1, 12],
     ['drop', 12],
     ['drop', 11]],),
   {'dealloc': [11, 12], 'freed': [11, 12], 'out': [], 'rc': {}}),
  ('upgrade after the last strong reference dies',
   ([['new', 11, 0], ['weak', 11], ['drop', 11], ['upgrade', 11], ['unweak', 11]],),
   {'dealloc': [11], 'freed': [11], 'out': [False], 'rc': {}}),
  ('weak reference keeps the control block only',
   ([['new', 11, 1],
     ['new', 12, 0],
     ['store', 11, 0, 12],
     ['weak', 11],
     ['drop', 11],
     ['upgrade', 11],
     ['unweak', 11]],),
   {'dealloc': [11], 'freed': [11], 'out': [False], 'rc': {'12': [1, 0]}}),
  ('dropping a weak reference to a live object',
   ([['new', 11, 0], ['weak', 11], ['unweak', 11], ['upgrade', 11], ['drop', 11], ['drop', 11]],),
   {'dealloc': [11], 'freed': [11], 'out': [True], 'rc': {}}),
  ('control: chain release order',
   ([['new', 11, 1],
     ['new', 12, 1],
     ['new', 13, 0],
     ['store', 11, 0, 12],
     ['store', 12, 0, 13],
     ['drop', 12],
     ['drop', 13],
     ['drop', 11]],),
   {'dealloc': [11, 12, 13], 'freed': [11, 12, 13], 'out': [], 'rc': {}})],
 [('regression: overwrite with a child of the old value',
   ([['new', 21, 1],
     ['new', 22, 1],
     ['new', 23, 0],
     ['store', 22, 0, 23],
     ['drop', 23],
     ['store', 21, 0, 22],
     ['drop', 22],
     ['store', 21, 0, 23]],),
   {'dealloc': [22], 'freed': [22], 'out': [], 'rc': {'21': [1, 0], '23': [1, 0]}}),
  ('self-assignment of the only reference',
   ([['new', 21, 1],
     ['new', 22, 0],
     ['store', 21, 0, 22],
     ['drop', 22],
     ['store', 21, 0, 22],
     ['upgrade', 22]],),
   {'dealloc': [], 'freed': [], 'out': [True], 'rc': {'21': [1, 0], '22': [2, 0]}}),
  ('object referenced twice by one parent',
   ([['new', 21, 2],
     ['new', 22, 0],
     ['store', 21, 0, 22],
     ['store', 21, 1, 22],
     ['drop', 22],
     ['drop', 21]],),
   {'dealloc': [21, 22], 'freed': [21, 22], 'out': [], 'rc': {}}),
  ('upgrade after the last strong reference dies',
   ([['new', 21, 0], ['weak', 21], ['drop', 21], ['upgrade', 21], ['unweak', 21]],),
   {'dealloc': [21], 'freed': [21], 'out': [False], 'rc': {}}),
  ('weak reference keeps the control block only',
   ([['new', 21, 1],
     ['new', 22, 0],
     ['store', 21, 0, 22],
     ['weak', 21],
     ['drop', 21],
     ['upgrade', 21],
     ['unweak', 21]],),
   {'dealloc': [21], 'freed': [21], 'out': [False], 'rc': {'22': [1, 0]}}),
  ('dropping a weak reference to a live object',
   ([['new', 21, 0], ['weak', 21], ['unweak', 21], ['upgrade', 21], ['drop', 21], ['drop', 21]],),
   {'dealloc': [21], 'freed': [21], 'out': [True], 'rc': {}}),
  ('control: chain release order',
   ([['new', 21, 1],
     ['new', 22, 1],
     ['new', 23, 0],
     ['store', 21, 0, 22],
     ['store', 22, 0, 23],
     ['drop', 22],
     ['drop', 23],
     ['drop', 21]],),
   {'dealloc': [21, 22, 23], 'freed': [21, 22, 23], 'out': [], 'rc': {}})],
 [('regression: overwrite with a child of the old value',
   ([['new', 31, 1],
     ['new', 32, 1],
     ['new', 33, 0],
     ['store', 32, 0, 33],
     ['drop', 33],
     ['store', 31, 0, 32],
     ['drop', 32],
     ['store', 31, 0, 33]],),
   {'dealloc': [32], 'freed': [32], 'out': [], 'rc': {'31': [1, 0], '33': [1, 0]}}),
  ('self-assignment of the only reference',
   ([['new', 31, 1],
     ['new', 32, 0],
     ['store', 31, 0, 32],
     ['drop', 32],
     ['store', 31, 0, 32],
     ['upgrade', 32]],),
   {'dealloc': [], 'freed': [], 'out': [True], 'rc': {'31': [1, 0], '32': [2, 0]}}),
  ('object referenced twice by one parent',
   ([['new', 31, 2],
     ['new', 32, 0],
     ['store', 31, 0, 32],
     ['store', 31, 1, 32],
     ['drop', 32],
     ['drop', 31]],),
   {'dealloc': [31, 32], 'freed': [31, 32], 'out': [], 'rc': {}}),
  ('upgrade after the last strong reference dies',
   ([['new', 31, 0], ['weak', 31], ['drop', 31], ['upgrade', 31], ['unweak', 31]],),
   {'dealloc': [31], 'freed': [31], 'out': [False], 'rc': {}}),
  ('weak reference keeps the control block only',
   ([['new', 31, 1],
     ['new', 32, 0],
     ['store', 31, 0, 32],
     ['weak', 31],
     ['drop', 31],
     ['upgrade', 31],
     ['unweak', 31]],),
   {'dealloc': [31], 'freed': [31], 'out': [False], 'rc': {'32': [1, 0]}}),
  ('dropping a weak reference to a live object',
   ([['new', 31, 0], ['weak', 31], ['unweak', 31], ['upgrade', 31], ['drop', 31], ['drop', 31]],),
   {'dealloc': [31], 'freed': [31], 'out': [True], 'rc': {}}),
  ('control: chain release order',
   ([['new', 31, 1],
     ['new', 32, 1],
     ['new', 33, 0],
     ['store', 31, 0, 32],
     ['store', 32, 0, 33],
     ['drop', 32],
     ['drop', 33],
     ['drop', 31]],),
   {'dealloc': [31, 32, 33], 'freed': [31, 32, 33], 'out': [], 'rc': {}})],
 [('regression: overwrite with a child of the old value',
   ([['new', 41, 1],
     ['new', 42, 1],
     ['new', 43, 0],
     ['store', 42, 0, 43],
     ['drop', 43],
     ['store', 41, 0, 42],
     ['drop', 42],
     ['store', 41, 0, 43]],),
   {'dealloc': [42], 'freed': [42], 'out': [], 'rc': {'41': [1, 0], '43': [1, 0]}}),
  ('self-assignment of the only reference',
   ([['new', 41, 1],
     ['new', 42, 0],
     ['store', 41, 0, 42],
     ['drop', 42],
     ['store', 41, 0, 42],
     ['upgrade', 42]],),
   {'dealloc': [], 'freed': [], 'out': [True], 'rc': {'41': [1, 0], '42': [2, 0]}}),
  ('object referenced twice by one parent',
   ([['new', 41, 2],
     ['new', 42, 0],
     ['store', 41, 0, 42],
     ['store', 41, 1, 42],
     ['drop', 42],
     ['drop', 41]],),
   {'dealloc': [41, 42], 'freed': [41, 42], 'out': [], 'rc': {}}),
  ('upgrade after the last strong reference dies',
   ([['new', 41, 0], ['weak', 41], ['drop', 41], ['upgrade', 41], ['unweak', 41]],),
   {'dealloc': [41], 'freed': [41], 'out': [False], 'rc': {}}),
  ('weak reference keeps the control block only',
   ([['new', 41, 1],
     ['new', 42, 0],
     ['store', 41, 0, 42],
     ['weak', 41],
     ['drop', 41],
     ['upgrade', 41],
     ['unweak', 41]],),
   {'dealloc': [41], 'freed': [41], 'out': [False], 'rc': {'42': [1, 0]}}),
  ('dropping a weak reference to a live object',
   ([['new', 41, 0], ['weak', 41], ['unweak', 41], ['upgrade', 41], ['drop', 41], ['drop', 41]],),
   {'dealloc': [41], 'freed': [41], 'out': [True], 'rc': {}}),
  ('control: chain release order',
   ([['new', 41, 1],
     ['new', 42, 1],
     ['new', 43, 0],
     ['store', 41, 0, 42],
     ['store', 42, 0, 43],
     ['drop', 42],
     ['drop', 43],
     ['drop', 41]],),
   {'dealloc': [41, 42, 43], 'freed': [41, 42, 43], 'out': [], 'rc': {}})],
 [('regression: overwrite with a child of the old value',
   ([['new', 51, 1],
     ['new', 52, 1],
     ['new', 53, 0],
     ['store', 52, 0, 53],
     ['drop', 53],
     ['store', 51, 0, 52],
     ['drop', 52],
     ['store', 51, 0, 53]],),
   {'dealloc': [52], 'freed': [52], 'out': [], 'rc': {'51': [1, 0], '53': [1, 0]}}),
  ('self-assignment of the only reference',
   ([['new', 51, 1],
     ['new', 52, 0],
     ['store', 51, 0, 52],
     ['drop', 52],
     ['store', 51, 0, 52],
     ['upgrade', 52]],),
   {'dealloc': [], 'freed': [], 'out': [True], 'rc': {'51': [1, 0], '52': [2, 0]}}),
  ('object referenced twice by one parent',
   ([['new', 51, 2],
     ['new', 52, 0],
     ['store', 51, 0, 52],
     ['store', 51, 1, 52],
     ['drop', 52],
     ['drop', 51]],),
   {'dealloc': [51, 52], 'freed': [51, 52], 'out': [], 'rc': {}}),
  ('upgrade after the last strong reference dies',
   ([['new', 51, 0], ['weak', 51], ['drop', 51], ['upgrade', 51], ['unweak', 51]],),
   {'dealloc': [51], 'freed': [51], 'out': [False], 'rc': {}}),
  ('weak reference keeps the control block only',
   ([['new', 51, 1],
     ['new', 52, 0],
     ['store', 51, 0, 52],
     ['weak', 51],
     ['drop', 51],
     ['upgrade', 51],
     ['unweak', 51]],),
   {'dealloc': [51], 'freed': [51], 'out': [False], 'rc': {'52': [1, 0]}}),
  ('dropping a weak reference to a live object',
   ([['new', 51, 0], ['weak', 51], ['unweak', 51], ['upgrade', 51], ['drop', 51], ['drop', 51]],),
   {'dealloc': [51], 'freed': [51], 'out': [True], 'rc': {}}),
  ('control: chain release order',
   ([['new', 51, 1],
     ['new', 52, 1],
     ['new', 53, 0],
     ['store', 51, 0, 52],
     ['store', 52, 0, 53],
     ['drop', 52],
     ['drop', 53],
     ['drop', 51]],),
   {'dealloc': [51, 52, 53], 'freed': [51, 52, 53], 'out': [], 'rc': {}})]]
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: overwrite with a child of the old value{'dealloc': [12], 'freed': [12], 'out': [], 'rc': {'11': [1, 0], '13': [1, 0]}}{'dealloc': [12], 'freed': [12], 'out': [], 'rc': {'11': [1, 0], '13': [1, 0]}}Passed
self-assignment of the only reference{'dealloc': [], 'freed': [], 'out': [True], 'rc': {'11': [1, 0], '12': [2, 0]}}{'dealloc': [], 'freed': [], 'out': [True], 'rc': {'11': [1, 0], '12': [2, 0]}}Passed
object referenced twice by one parent{'dealloc': [11, 12], 'freed': [11, 12], 'out': [], 'rc': {}}{'dealloc': [11, 12], 'freed': [11, 12], 'out': [], 'rc': {}}Passed
upgrade after the last strong reference dies{'dealloc': [11], 'freed': [11], 'out': ['use-after-free'], 'rc': {}}{'dealloc': [11], 'freed': [11], 'out': [False], 'rc': {}}Failed
weak reference keeps the control block only{'dealloc': [11], 'freed': [11], 'out': ['use-after-free'], 'rc': {'12': [1, 0]}}{'dealloc': [11], 'freed': [11], 'out': [False], 'rc': {'12': [1, 0]}}Failed
dropping a weak reference to a live object{'dealloc': [11], 'freed': [11], 'out': [True], 'rc': {}}{'dealloc': [11], 'freed': [11], 'out': [True], 'rc': {}}Passed
control: chain release order{'dealloc': [11, 12, 13], 'freed': [11, 12, 13], 'out': [], 'rc': {}}{'dealloc': [11, 12, 13], 'freed': [11, 12, 13], 'out': [], 'rc': {}}Passed

SHA-256 / b4e800b72f9d7ecce72b343a6e77655f73463595bc796539b5901a5d5dbce826

2 / The unsuccessful fix

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

N = 1
observations = []
def solve(events):
    objs = {}
    freed = []
    dealloc = []
    out = []
    def release(o):
        if o is None:
            return
        b = objs[o]
        b['rc'] -= 1
        if b['rc'] == 0:
            freed.append(o)
            kids, b['fields'] = b['fields'], []
            if b['weak'] <= 1:
                dealloc.append(o)
                del objs[o]
            for c in kids:
                release(c)
    try:
        for ev in events:
            op = ev[0]
            if op == 'new':
                objs[ev[1]] = {'rc': 1, 'weak': 0, 'fields': [None] * ev[2]}
            elif op == 'drop':
                release(ev[1])
            elif op == 'store':
                _, src, field, dst = ev
                if dst is not None:
                    objs[dst]['rc'] += 1
                old = objs[src]['fields'][field]
                objs[src]['fields'][field] = dst
                release(old)
            elif op == 'weak':
                objs[ev[1]]['weak'] += 1
            elif op == 'unweak':
                b = objs[ev[1]]
                b['weak'] -= 1
                if b['weak'] == 0 and b['rc'] == 0:
                    dealloc.append(ev[1])
                    del objs[ev[1]]
            else:
                b = objs[ev[1]]
                if b['rc'] > 0:
                    b['rc'] += 1
                    out.append(True)
                else:
                    out.append(False)
    except (KeyError, IndexError):
        out.append('use-after-free')
    return {'out': out, 'freed': freed, 'dealloc': dealloc,
            'rc': {str(k): [v['rc'], v['weak']] for k, v in sorted(objs.items())}}
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = [[('regression: overwrite with a child of the old value',
   ([['new', 11, 1],
     ['new', 12, 1],
     ['new', 13, 0],
     ['store', 12, 0, 13],
     ['drop', 13],
     ['store', 11, 0, 12],
     ['drop', 12],
     ['store', 11, 0, 13]],),
   {'dealloc': [12], 'freed': [12], 'out': [], 'rc': {'11': [1, 0], '13': [1, 0]}}),
  ('self-assignment of the only reference',
   ([['new', 11, 1],
     ['new', 12, 0],
     ['store', 11, 0, 12],
     ['drop', 12],
     ['store', 11, 0, 12],
     ['upgrade', 12]],),
   {'dealloc': [], 'freed': [], 'out': [True], 'rc': {'11': [1, 0], '12': [2, 0]}}),
  ('object referenced twice by one parent',
   ([['new', 11, 2],
     ['new', 12, 0],
     ['store', 11, 0, 12],
     ['store', 11, 1, 12],
     ['drop', 12],
     ['drop', 11]],),
   {'dealloc': [11, 12], 'freed': [11, 12], 'out': [], 'rc': {}}),
  ('upgrade after the last strong reference dies',
   ([['new', 11, 0], ['weak', 11], ['drop', 11], ['upgrade', 11], ['unweak', 11]],),
   {'dealloc': [11], 'freed': [11], 'out': [False], 'rc': {}}),
  ('weak reference keeps the control block only',
   ([['new', 11, 1],
     ['new', 12, 0],
     ['store', 11, 0, 12],
     ['weak', 11],
     ['drop', 11],
     ['upgrade', 11],
     ['unweak', 11]],),
   {'dealloc': [11], 'freed': [11], 'out': [False], 'rc': {'12': [1, 0]}}),
  ('dropping a weak reference to a live object',
   ([['new', 11, 0], ['weak', 11], ['unweak', 11], ['upgrade', 11], ['drop', 11], ['drop', 11]],),
   {'dealloc': [11], 'freed': [11], 'out': [True], 'rc': {}}),
  ('control: chain release order',
   ([['new', 11, 1],
     ['new', 12, 1],
     ['new', 13, 0],
     ['store', 11, 0, 12],
     ['store', 12, 0, 13],
     ['drop', 12],
     ['drop', 13],
     ['drop', 11]],),
   {'dealloc': [11, 12, 13], 'freed': [11, 12, 13], 'out': [], 'rc': {}})],
 [('regression: overwrite with a child of the old value',
   ([['new', 21, 1],
     ['new', 22, 1],
     ['new', 23, 0],
     ['store', 22, 0, 23],
     ['drop', 23],
     ['store', 21, 0, 22],
     ['drop', 22],
     ['store', 21, 0, 23]],),
   {'dealloc': [22], 'freed': [22], 'out': [], 'rc': {'21': [1, 0], '23': [1, 0]}}),
  ('self-assignment of the only reference',
   ([['new', 21, 1],
     ['new', 22, 0],
     ['store', 21, 0, 22],
     ['drop', 22],
     ['store', 21, 0, 22],
     ['upgrade', 22]],),
   {'dealloc': [], 'freed': [], 'out': [True], 'rc': {'21': [1, 0], '22': [2, 0]}}),
  ('object referenced twice by one parent',
   ([['new', 21, 2],
     ['new', 22, 0],
     ['store', 21, 0, 22],
     ['store', 21, 1, 22],
     ['drop', 22],
     ['drop', 21]],),
   {'dealloc': [21, 22], 'freed': [21, 22], 'out': [], 'rc': {}}),
  ('upgrade after the last strong reference dies',
   ([['new', 21, 0], ['weak', 21], ['drop', 21], ['upgrade', 21], ['unweak', 21]],),
   {'dealloc': [21], 'freed': [21], 'out': [False], 'rc': {}}),
  ('weak reference keeps the control block only',
   ([['new', 21, 1],
     ['new', 22, 0],
     ['store', 21, 0, 22],
     ['weak', 21],
     ['drop', 21],
     ['upgrade', 21],
     ['unweak', 21]],),
   {'dealloc': [21], 'freed': [21], 'out': [False], 'rc': {'22': [1, 0]}}),
  ('dropping a weak reference to a live object',
   ([['new', 21, 0], ['weak', 21], ['unweak', 21], ['upgrade', 21], ['drop', 21], ['drop', 21]],),
   {'dealloc': [21], 'freed': [21], 'out': [True], 'rc': {}}),
  ('control: chain release order',
   ([['new', 21, 1],
     ['new', 22, 1],
     ['new', 23, 0],
     ['store', 21, 0, 22],
     ['store', 22, 0, 23],
     ['drop', 22],
     ['drop', 23],
     ['drop', 21]],),
   {'dealloc': [21, 22, 23], 'freed': [21, 22, 23], 'out': [], 'rc': {}})],
 [('regression: overwrite with a child of the old value',
   ([['new', 31, 1],
     ['new', 32, 1],
     ['new', 33, 0],
     ['store', 32, 0, 33],
     ['drop', 33],
     ['store', 31, 0, 32],
     ['drop', 32],
     ['store', 31, 0, 33]],),
   {'dealloc': [32], 'freed': [32], 'out': [], 'rc': {'31': [1, 0], '33': [1, 0]}}),
  ('self-assignment of the only reference',
   ([['new', 31, 1],
     ['new', 32, 0],
     ['store', 31, 0, 32],
     ['drop', 32],
     ['store', 31, 0, 32],
     ['upgrade', 32]],),
   {'dealloc': [], 'freed': [], 'out': [True], 'rc': {'31': [1, 0], '32': [2, 0]}}),
  ('object referenced twice by one parent',
   ([['new', 31, 2],
     ['new', 32, 0],
     ['store', 31, 0, 32],
     ['store', 31, 1, 32],
     ['drop', 32],
     ['drop', 31]],),
   {'dealloc': [31, 32], 'freed': [31, 32], 'out': [], 'rc': {}}),
  ('upgrade after the last strong reference dies',
   ([['new', 31, 0], ['weak', 31], ['drop', 31], ['upgrade', 31], ['unweak', 31]],),
   {'dealloc': [31], 'freed': [31], 'out': [False], 'rc': {}}),
  ('weak reference keeps the control block only',
   ([['new', 31, 1],
     ['new', 32, 0],
     ['store', 31, 0, 32],
     ['weak', 31],
     ['drop', 31],
     ['upgrade', 31],
     ['unweak', 31]],),
   {'dealloc': [31], 'freed': [31], 'out': [False], 'rc': {'32': [1, 0]}}),
  ('dropping a weak reference to a live object',
   ([['new', 31, 0], ['weak', 31], ['unweak', 31], ['upgrade', 31], ['drop', 31], ['drop', 31]],),
   {'dealloc': [31], 'freed': [31], 'out': [True], 'rc': {}}),
  ('control: chain release order',
   ([['new', 31, 1],
     ['new', 32, 1],
     ['new', 33, 0],
     ['store', 31, 0, 32],
     ['store', 32, 0, 33],
     ['drop', 32],
     ['drop', 33],
     ['drop', 31]],),
   {'dealloc': [31, 32, 33], 'freed': [31, 32, 33], 'out': [], 'rc': {}})],
 [('regression: overwrite with a child of the old value',
   ([['new', 41, 1],
     ['new', 42, 1],
     ['new', 43, 0],
     ['store', 42, 0, 43],
     ['drop', 43],
     ['store', 41, 0, 42],
     ['drop', 42],
     ['store', 41, 0, 43]],),
   {'dealloc': [42], 'freed': [42], 'out': [], 'rc': {'41': [1, 0], '43': [1, 0]}}),
  ('self-assignment of the only reference',
   ([['new', 41, 1],
     ['new', 42, 0],
     ['store', 41, 0, 42],
     ['drop', 42],
     ['store', 41, 0, 42],
     ['upgrade', 42]],),
   {'dealloc': [], 'freed': [], 'out': [True], 'rc': {'41': [1, 0], '42': [2, 0]}}),
  ('object referenced twice by one parent',
   ([['new', 41, 2],
     ['new', 42, 0],
     ['store', 41, 0, 42],
     ['store', 41, 1, 42],
     ['drop', 42],
     ['drop', 41]],),
   {'dealloc': [41, 42], 'freed': [41, 42], 'out': [], 'rc': {}}),
  ('upgrade after the last strong reference dies',
   ([['new', 41, 0], ['weak', 41], ['drop', 41], ['upgrade', 41], ['unweak', 41]],),
   {'dealloc': [41], 'freed': [41], 'out': [False], 'rc': {}}),
  ('weak reference keeps the control block only',
   ([['new', 41, 1],
     ['new', 42, 0],
     ['store', 41, 0, 42],
     ['weak', 41],
     ['drop', 41],
     ['upgrade', 41],
     ['unweak', 41]],),
   {'dealloc': [41], 'freed': [41], 'out': [False], 'rc': {'42': [1, 0]}}),
  ('dropping a weak reference to a live object',
   ([['new', 41, 0], ['weak', 41], ['unweak', 41], ['upgrade', 41], ['drop', 41], ['drop', 41]],),
   {'dealloc': [41], 'freed': [41], 'out': [True], 'rc': {}}),
  ('control: chain release order',
   ([['new', 41, 1],
     ['new', 42, 1],
     ['new', 43, 0],
     ['store', 41, 0, 42],
     ['store', 42, 0, 43],
     ['drop', 42],
     ['drop', 43],
     ['drop', 41]],),
   {'dealloc': [41, 42, 43], 'freed': [41, 42, 43], 'out': [], 'rc': {}})],
 [('regression: overwrite with a child of the old value',
   ([['new', 51, 1],
     ['new', 52, 1],
     ['new', 53, 0],
     ['store', 52, 0, 53],
     ['drop', 53],
     ['store', 51, 0, 52],
     ['drop', 52],
     ['store', 51, 0, 53]],),
   {'dealloc': [52], 'freed': [52], 'out': [], 'rc': {'51': [1, 0], '53': [1, 0]}}),
  ('self-assignment of the only reference',
   ([['new', 51, 1],
     ['new', 52, 0],
     ['store', 51, 0, 52],
     ['drop', 52],
     ['store', 51, 0, 52],
     ['upgrade', 52]],),
   {'dealloc': [], 'freed': [], 'out': [True], 'rc': {'51': [1, 0], '52': [2, 0]}}),
  ('object referenced twice by one parent',
   ([['new', 51, 2],
     ['new', 52, 0],
     ['store', 51, 0, 52],
     ['store', 51, 1, 52],
     ['drop', 52],
     ['drop', 51]],),
   {'dealloc': [51, 52], 'freed': [51, 52], 'out': [], 'rc': {}}),
  ('upgrade after the last strong reference dies',
   ([['new', 51, 0], ['weak', 51], ['drop', 51], ['upgrade', 51], ['unweak', 51]],),
   {'dealloc': [51], 'freed': [51], 'out': [False], 'rc': {}}),
  ('weak reference keeps the control block only',
   ([['new', 51, 1],
     ['new', 52, 0],
     ['store', 51, 0, 52],
     ['weak', 51],
     ['drop', 51],
     ['upgrade', 51],
     ['unweak', 51]],),
   {'dealloc': [51], 'freed': [51], 'out': [False], 'rc': {'52': [1, 0]}}),
  ('dropping a weak reference to a live object',
   ([['new', 51, 0], ['weak', 51], ['unweak', 51], ['upgrade', 51], ['drop', 51], ['drop', 51]],),
   {'dealloc': [51], 'freed': [51], 'out': [True], 'rc': {}}),
  ('control: chain release order',
   ([['new', 51, 1],
     ['new', 52, 1],
     ['new', 53, 0],
     ['store', 51, 0, 52],
     ['store', 52, 0, 53],
     ['drop', 52],
     ['drop', 53],
     ['drop', 51]],),
   {'dealloc': [51, 52, 53], 'freed': [51, 52, 53], 'out': [], 'rc': {}})]]
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: overwrite with a child of the old value{'dealloc': [12], 'freed': [12], 'out': [], 'rc': {'11': [1, 0], '13': [1, 0]}}{'dealloc': [12], 'freed': [12], 'out': [], 'rc': {'11': [1, 0], '13': [1, 0]}}Passed
self-assignment of the only reference{'dealloc': [], 'freed': [], 'out': [True], 'rc': {'11': [1, 0], '12': [2, 0]}}{'dealloc': [], 'freed': [], 'out': [True], 'rc': {'11': [1, 0], '12': [2, 0]}}Passed
object referenced twice by one parent{'dealloc': [11, 12], 'freed': [11, 12], 'out': [], 'rc': {}}{'dealloc': [11, 12], 'freed': [11, 12], 'out': [], 'rc': {}}Passed
upgrade after the last strong reference dies{'dealloc': [11], 'freed': [11], 'out': ['use-after-free'], 'rc': {}}{'dealloc': [11], 'freed': [11], 'out': [False], 'rc': {}}Failed
weak reference keeps the control block only{'dealloc': [11], 'freed': [11], 'out': ['use-after-free'], 'rc': {'12': [1, 0]}}{'dealloc': [11], 'freed': [11], 'out': [False], 'rc': {'12': [1, 0]}}Failed
dropping a weak reference to a live object{'dealloc': [11], 'freed': [11], 'out': [True], 'rc': {}}{'dealloc': [11], 'freed': [11], 'out': [True], 'rc': {}}Passed
control: chain release order{'dealloc': [11, 12, 13], 'freed': [11, 12, 13], 'out': [], 'rc': {}}{'dealloc': [11, 12, 13], 'freed': [11, 12, 13], 'out': [], 'rc': {}}Passed

SHA-256 / a851c84a67fb609e7929245cdd5420c5c93b7f0cb1e3c9d6251d0d8d027aa155

3 / The verified repair

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

N = 1
observations = []
def solve(events):
    objs = {}
    freed = []
    dealloc = []
    out = []
    def release(o):
        if o is None:
            return
        b = objs[o]
        b['rc'] -= 1
        if b['rc'] == 0:
            freed.append(o)
            kids, b['fields'] = b['fields'], []
            if b['weak'] == 0:
                dealloc.append(o)
                del objs[o]
            for c in kids:
                release(c)
    try:
        for ev in events:
            op = ev[0]
            if op == 'new':
                objs[ev[1]] = {'rc': 1, 'weak': 0, 'fields': [None] * ev[2]}
            elif op == 'drop':
                release(ev[1])
            elif op == 'store':
                _, src, field, dst = ev
                if dst is not None:
                    objs[dst]['rc'] += 1
                old = objs[src]['fields'][field]
                objs[src]['fields'][field] = dst
                release(old)
            elif op == 'weak':
                objs[ev[1]]['weak'] += 1
            elif op == 'unweak':
                b = objs[ev[1]]
                b['weak'] -= 1
                if b['weak'] == 0 and b['rc'] == 0:
                    dealloc.append(ev[1])
                    del objs[ev[1]]
            else:
                b = objs[ev[1]]
                if b['rc'] > 0:
                    b['rc'] += 1
                    out.append(True)
                else:
                    out.append(False)
    except (KeyError, IndexError):
        out.append('use-after-free')
    return {'out': out, 'freed': freed, 'dealloc': dealloc,
            'rc': {str(k): [v['rc'], v['weak']] for k, v in sorted(objs.items())}}
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = [[('regression: overwrite with a child of the old value',
   ([['new', 11, 1],
     ['new', 12, 1],
     ['new', 13, 0],
     ['store', 12, 0, 13],
     ['drop', 13],
     ['store', 11, 0, 12],
     ['drop', 12],
     ['store', 11, 0, 13]],),
   {'dealloc': [12], 'freed': [12], 'out': [], 'rc': {'11': [1, 0], '13': [1, 0]}}),
  ('self-assignment of the only reference',
   ([['new', 11, 1],
     ['new', 12, 0],
     ['store', 11, 0, 12],
     ['drop', 12],
     ['store', 11, 0, 12],
     ['upgrade', 12]],),
   {'dealloc': [], 'freed': [], 'out': [True], 'rc': {'11': [1, 0], '12': [2, 0]}}),
  ('object referenced twice by one parent',
   ([['new', 11, 2],
     ['new', 12, 0],
     ['store', 11, 0, 12],
     ['store', 11, 1, 12],
     ['drop', 12],
     ['drop', 11]],),
   {'dealloc': [11, 12], 'freed': [11, 12], 'out': [], 'rc': {}}),
  ('upgrade after the last strong reference dies',
   ([['new', 11, 0], ['weak', 11], ['drop', 11], ['upgrade', 11], ['unweak', 11]],),
   {'dealloc': [11], 'freed': [11], 'out': [False], 'rc': {}}),
  ('weak reference keeps the control block only',
   ([['new', 11, 1],
     ['new', 12, 0],
     ['store', 11, 0, 12],
     ['weak', 11],
     ['drop', 11],
     ['upgrade', 11],
     ['unweak', 11]],),
   {'dealloc': [11], 'freed': [11], 'out': [False], 'rc': {'12': [1, 0]}}),
  ('dropping a weak reference to a live object',
   ([['new', 11, 0], ['weak', 11], ['unweak', 11], ['upgrade', 11], ['drop', 11], ['drop', 11]],),
   {'dealloc': [11], 'freed': [11], 'out': [True], 'rc': {}}),
  ('control: chain release order',
   ([['new', 11, 1],
     ['new', 12, 1],
     ['new', 13, 0],
     ['store', 11, 0, 12],
     ['store', 12, 0, 13],
     ['drop', 12],
     ['drop', 13],
     ['drop', 11]],),
   {'dealloc': [11, 12, 13], 'freed': [11, 12, 13], 'out': [], 'rc': {}})],
 [('regression: overwrite with a child of the old value',
   ([['new', 21, 1],
     ['new', 22, 1],
     ['new', 23, 0],
     ['store', 22, 0, 23],
     ['drop', 23],
     ['store', 21, 0, 22],
     ['drop', 22],
     ['store', 21, 0, 23]],),
   {'dealloc': [22], 'freed': [22], 'out': [], 'rc': {'21': [1, 0], '23': [1, 0]}}),
  ('self-assignment of the only reference',
   ([['new', 21, 1],
     ['new', 22, 0],
     ['store', 21, 0, 22],
     ['drop', 22],
     ['store', 21, 0, 22],
     ['upgrade', 22]],),
   {'dealloc': [], 'freed': [], 'out': [True], 'rc': {'21': [1, 0], '22': [2, 0]}}),
  ('object referenced twice by one parent',
   ([['new', 21, 2],
     ['new', 22, 0],
     ['store', 21, 0, 22],
     ['store', 21, 1, 22],
     ['drop', 22],
     ['drop', 21]],),
   {'dealloc': [21, 22], 'freed': [21, 22], 'out': [], 'rc': {}}),
  ('upgrade after the last strong reference dies',
   ([['new', 21, 0], ['weak', 21], ['drop', 21], ['upgrade', 21], ['unweak', 21]],),
   {'dealloc': [21], 'freed': [21], 'out': [False], 'rc': {}}),
  ('weak reference keeps the control block only',
   ([['new', 21, 1],
     ['new', 22, 0],
     ['store', 21, 0, 22],
     ['weak', 21],
     ['drop', 21],
     ['upgrade', 21],
     ['unweak', 21]],),
   {'dealloc': [21], 'freed': [21], 'out': [False], 'rc': {'22': [1, 0]}}),
  ('dropping a weak reference to a live object',
   ([['new', 21, 0], ['weak', 21], ['unweak', 21], ['upgrade', 21], ['drop', 21], ['drop', 21]],),
   {'dealloc': [21], 'freed': [21], 'out': [True], 'rc': {}}),
  ('control: chain release order',
   ([['new', 21, 1],
     ['new', 22, 1],
     ['new', 23, 0],
     ['store', 21, 0, 22],
     ['store', 22, 0, 23],
     ['drop', 22],
     ['drop', 23],
     ['drop', 21]],),
   {'dealloc': [21, 22, 23], 'freed': [21, 22, 23], 'out': [], 'rc': {}})],
 [('regression: overwrite with a child of the old value',
   ([['new', 31, 1],
     ['new', 32, 1],
     ['new', 33, 0],
     ['store', 32, 0, 33],
     ['drop', 33],
     ['store', 31, 0, 32],
     ['drop', 32],
     ['store', 31, 0, 33]],),
   {'dealloc': [32], 'freed': [32], 'out': [], 'rc': {'31': [1, 0], '33': [1, 0]}}),
  ('self-assignment of the only reference',
   ([['new', 31, 1],
     ['new', 32, 0],
     ['store', 31, 0, 32],
     ['drop', 32],
     ['store', 31, 0, 32],
     ['upgrade', 32]],),
   {'dealloc': [], 'freed': [], 'out': [True], 'rc': {'31': [1, 0], '32': [2, 0]}}),
  ('object referenced twice by one parent',
   ([['new', 31, 2],
     ['new', 32, 0],
     ['store', 31, 0, 32],
     ['store', 31, 1, 32],
     ['drop', 32],
     ['drop', 31]],),
   {'dealloc': [31, 32], 'freed': [31, 32], 'out': [], 'rc': {}}),
  ('upgrade after the last strong reference dies',
   ([['new', 31, 0], ['weak', 31], ['drop', 31], ['upgrade', 31], ['unweak', 31]],),
   {'dealloc': [31], 'freed': [31], 'out': [False], 'rc': {}}),
  ('weak reference keeps the control block only',
   ([['new', 31, 1],
     ['new', 32, 0],
     ['store', 31, 0, 32],
     ['weak', 31],
     ['drop', 31],
     ['upgrade', 31],
     ['unweak', 31]],),
   {'dealloc': [31], 'freed': [31], 'out': [False], 'rc': {'32': [1, 0]}}),
  ('dropping a weak reference to a live object',
   ([['new', 31, 0], ['weak', 31], ['unweak', 31], ['upgrade', 31], ['drop', 31], ['drop', 31]],),
   {'dealloc': [31], 'freed': [31], 'out': [True], 'rc': {}}),
  ('control: chain release order',
   ([['new', 31, 1],
     ['new', 32, 1],
     ['new', 33, 0],
     ['store', 31, 0, 32],
     ['store', 32, 0, 33],
     ['drop', 32],
     ['drop', 33],
     ['drop', 31]],),
   {'dealloc': [31, 32, 33], 'freed': [31, 32, 33], 'out': [], 'rc': {}})],
 [('regression: overwrite with a child of the old value',
   ([['new', 41, 1],
     ['new', 42, 1],
     ['new', 43, 0],
     ['store', 42, 0, 43],
     ['drop', 43],
     ['store', 41, 0, 42],
     ['drop', 42],
     ['store', 41, 0, 43]],),
   {'dealloc': [42], 'freed': [42], 'out': [], 'rc': {'41': [1, 0], '43': [1, 0]}}),
  ('self-assignment of the only reference',
   ([['new', 41, 1],
     ['new', 42, 0],
     ['store', 41, 0, 42],
     ['drop', 42],
     ['store', 41, 0, 42],
     ['upgrade', 42]],),
   {'dealloc': [], 'freed': [], 'out': [True], 'rc': {'41': [1, 0], '42': [2, 0]}}),
  ('object referenced twice by one parent',
   ([['new', 41, 2],
     ['new', 42, 0],
     ['store', 41, 0, 42],
     ['store', 41, 1, 42],
     ['drop', 42],
     ['drop', 41]],),
   {'dealloc': [41, 42], 'freed': [41, 42], 'out': [], 'rc': {}}),
  ('upgrade after the last strong reference dies',
   ([['new', 41, 0], ['weak', 41], ['drop', 41], ['upgrade', 41], ['unweak', 41]],),
   {'dealloc': [41], 'freed': [41], 'out': [False], 'rc': {}}),
  ('weak reference keeps the control block only',
   ([['new', 41, 1],
     ['new', 42, 0],
     ['store', 41, 0, 42],
     ['weak', 41],
     ['drop', 41],
     ['upgrade', 41],
     ['unweak', 41]],),
   {'dealloc': [41], 'freed': [41], 'out': [False], 'rc': {'42': [1, 0]}}),
  ('dropping a weak reference to a live object',
   ([['new', 41, 0], ['weak', 41], ['unweak', 41], ['upgrade', 41], ['drop', 41], ['drop', 41]],),
   {'dealloc': [41], 'freed': [41], 'out': [True], 'rc': {}}),
  ('control: chain release order',
   ([['new', 41, 1],
     ['new', 42, 1],
     ['new', 43, 0],
     ['store', 41, 0, 42],
     ['store', 42, 0, 43],
     ['drop', 42],
     ['drop', 43],
     ['drop', 41]],),
   {'dealloc': [41, 42, 43], 'freed': [41, 42, 43], 'out': [], 'rc': {}})],
 [('regression: overwrite with a child of the old value',
   ([['new', 51, 1],
     ['new', 52, 1],
     ['new', 53, 0],
     ['store', 52, 0, 53],
     ['drop', 53],
     ['store', 51, 0, 52],
     ['drop', 52],
     ['store', 51, 0, 53]],),
   {'dealloc': [52], 'freed': [52], 'out': [], 'rc': {'51': [1, 0], '53': [1, 0]}}),
  ('self-assignment of the only reference',
   ([['new', 51, 1],
     ['new', 52, 0],
     ['store', 51, 0, 52],
     ['drop', 52],
     ['store', 51, 0, 52],
     ['upgrade', 52]],),
   {'dealloc': [], 'freed': [], 'out': [True], 'rc': {'51': [1, 0], '52': [2, 0]}}),
  ('object referenced twice by one parent',
   ([['new', 51, 2],
     ['new', 52, 0],
     ['store', 51, 0, 52],
     ['store', 51, 1, 52],
     ['drop', 52],
     ['drop', 51]],),
   {'dealloc': [51, 52], 'freed': [51, 52], 'out': [], 'rc': {}}),
  ('upgrade after the last strong reference dies',
   ([['new', 51, 0], ['weak', 51], ['drop', 51], ['upgrade', 51], ['unweak', 51]],),
   {'dealloc': [51], 'freed': [51], 'out': [False], 'rc': {}}),
  ('weak reference keeps the control block only',
   ([['new', 51, 1],
     ['new', 52, 0],
     ['store', 51, 0, 52],
     ['weak', 51],
     ['drop', 51],
     ['upgrade', 51],
     ['unweak', 51]],),
   {'dealloc': [51], 'freed': [51], 'out': [False], 'rc': {'52': [1, 0]}}),
  ('dropping a weak reference to a live object',
   ([['new', 51, 0], ['weak', 51], ['unweak', 51], ['upgrade', 51], ['drop', 51], ['drop', 51]],),
   {'dealloc': [51], 'freed': [51], 'out': [True], 'rc': {}}),
  ('control: chain release order',
   ([['new', 51, 1],
     ['new', 52, 1],
     ['new', 53, 0],
     ['store', 51, 0, 52],
     ['store', 52, 0, 53],
     ['drop', 52],
     ['drop', 53],
     ['drop', 51]],),
   {'dealloc': [51, 52, 53], 'freed': [51, 52, 53], 'out': [], 'rc': {}})]]
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: overwrite with a child of the old value{'dealloc': [12], 'freed': [12], 'out': [], 'rc': {'11': [1, 0], '13': [1, 0]}}{'dealloc': [12], 'freed': [12], 'out': [], 'rc': {'11': [1, 0], '13': [1, 0]}}Passed
self-assignment of the only reference{'dealloc': [], 'freed': [], 'out': [True], 'rc': {'11': [1, 0], '12': [2, 0]}}{'dealloc': [], 'freed': [], 'out': [True], 'rc': {'11': [1, 0], '12': [2, 0]}}Passed
object referenced twice by one parent{'dealloc': [11, 12], 'freed': [11, 12], 'out': [], 'rc': {}}{'dealloc': [11, 12], 'freed': [11, 12], 'out': [], 'rc': {}}Passed
upgrade after the last strong reference dies{'dealloc': [11], 'freed': [11], 'out': [False], 'rc': {}}{'dealloc': [11], 'freed': [11], 'out': [False], 'rc': {}}Passed
weak reference keeps the control block only{'dealloc': [11], 'freed': [11], 'out': [False], 'rc': {'12': [1, 0]}}{'dealloc': [11], 'freed': [11], 'out': [False], 'rc': {'12': [1, 0]}}Passed
dropping a weak reference to a live object{'dealloc': [11], 'freed': [11], 'out': [True], 'rc': {}}{'dealloc': [11], 'freed': [11], 'out': [True], 'rc': {}}Passed
control: chain release order{'dealloc': [11, 12, 13], 'freed': [11, 12, 13], 'out': [], 'rc': {}}{'dealloc': [11, 12, 13], 'freed': [11, 12, 13], 'out': [], 'rc': {}}Passed

SHA-256 / bb0a242343e9a77d89dc0d20b2d39e1043b2ec3079fa8c8f2860209e66e25442

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

Case digest / e1f2973f932849e87eaaa795d90cc92e55b3ddb52bc4d8acff07cd2e7a8146ad