FA-90371 / Garbage collector invariants / Open access
Reference counting: destroying an object leaks its children · case 01
Objects reachable only from a destroyed object keep positive counts forever.
ROOT CAUSE
Destruction detaches the fields but never releases the references they held.
VERIFIED REPAIR
Release every field reference of a destroyed object, one release per field.
Unsuccessful approach: Deduplicating the fields releases a child only once even when two fields reference 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['weak'] == 0:
dealloc.append(o)
del objs[o]
del kids
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 fixture | Actual | Expected | Outcome |
|---|---|---|---|
| regression: overwrite with a child of the old value | {'dealloc': [12], 'freed': [12], 'out': [], 'rc': {'11': [1, 0], '13': [2, 0]}} | {'dealloc': [12], 'freed': [12], 'out': [], 'rc': {'11': [1, 0], '13': [1, 0]}} | Failed |
| 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], 'freed': [11], 'out': [], 'rc': {'12': [2, 0]}} | {'dealloc': [11, 12], 'freed': [11, 12], 'out': [], 'rc': {}} | Failed |
| 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': [2, 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], 'freed': [11], 'out': [], 'rc': {'12': [1, 0], '13': [1, 0]}} | {'dealloc': [11, 12, 13], 'freed': [11, 12, 13], 'out': [], 'rc': {}} | Failed |
SHA-256 / 752f026f0d66379f8cd57bd0f3dfba237d79a8a5756eb1691e03c118df5cc70b
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'] == 0:
dealloc.append(o)
del objs[o]
for c in set(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 fixture | Actual | Expected | Outcome |
|---|---|---|---|
| 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], 'freed': [11], 'out': [], 'rc': {'12': [1, 0]}} | {'dealloc': [11, 12], 'freed': [11, 12], 'out': [], 'rc': {}} | Failed |
| 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 / f8649f42218c79bb6c9a12437ba4b0906d3dd352bbd3014a060b0c7f0957cd22
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 fixture | Actual | Expected | Outcome |
|---|---|---|---|
| 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:25.986616+00:00.
Case digest / 2f49056d6012d703e37600f13cbeee575de7ff47a32924d93262309af80b44f9