FAILURE MAP
← Case archive

FA-90636 / Garbage collector invariants / Open access

Adaptive tenuring: survivor space never filled exactly · case 01

An object that would fill the survivor space exactly is promoted instead.

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

ROOT CAUSE

The fit test uses < capacity.

THE FAILURE

The fit test uses < capacity.

Unsuccessful approach: Checking only the used bytes lets the last object overrun the space.

Case contract

Survivors are [id, age, size] after a minor collection. desired = capacity * ratio // 100. Walking ages 1..max_threshold, accumulate sizes; the first age at which the running total exceeds desired becomes the tenuring threshold (max_threshold if never exceeded). Objects with age >= threshold are promoted; the rest are placed youngest first (ties by id) into the survivor space of the given capacity, and any that do not fit overflow into promotion. Return threshold, promoted ids, kept ids and bytes used.

Why this case matters

Tenuring policy controls premature promotion and survivor overflow in generational collectors.

1 / The failure

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

N = 1
observations = []
def solve(ages, capacity, ratio, max_threshold):
    desired = capacity * ratio // 100
    by_age = {}
    for _, age, size in ages:
        by_age[age] = by_age.get(age, 0) + size
    total = 0
    threshold = max_threshold
    for age in range(1, max_threshold + 1):
        total += by_age.get(age, 0)
        if total > desired:
            threshold = age
            break
    promote = [o for o, age, size in ages if age >= threshold]
    stay = sorted([x for x in ages if x[1] < threshold], key=lambda x: (x[1], x[0]))
    used = 0
    kept = []
    for o, age, size in stay:
        if used + size < capacity:
            kept.append(o)
            used += size
        else:
            promote.append(o)
    return {'threshold': threshold, 'promoted': sorted(promote), 'kept': sorted(kept), 'used': used}
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = [[('regression: cumulative sizes cross the desired size',
   ([[1, 1, 20], [2, 2, 25], [3, 3, 10], [4, 4, 30], [5, 1, 1]], 100, 50, 15),
   {'kept': [1, 2, 5], 'promoted': [3, 4], 'threshold': 3, 'used': 46}),
  ('cumulative size exactly at the desired size',
   ([[1, 1, 30], [2, 2, 20], [3, 3, 6]], 100, 50, 15),
   {'kept': [1, 2], 'promoted': [3], 'threshold': 3, 'used': 50}),
  ('ratio of a capacity that is not a multiple of 100',
   ([[1, 1, 40], [2, 2, 30], [3, 3, 1]], 150, 50, 15),
   {'kept': [1, 2, 3], 'promoted': [], 'threshold': 15, 'used': 71}),
  ('survivors overflow the survivor space',
   ([[1, 1, 30], [2, 1, 30], [3, 2, 30], [4, 1, 11], [5, 2, 40]], 100, 200, 3),
   {'kept': [1, 2, 4], 'promoted': [3, 5], 'threshold': 3, 'used': 71}),
  ('survivors fill the space exactly',
   ([[1, 1, 60], [2, 1, 40], [3, 2, 1]], 100, 200, 2),
   {'kept': [1, 2], 'promoted': [3], 'threshold': 2, 'used': 100}),
  ('threshold never crossed',
   ([[1, 1, 5], [2, 3, 6]], 100, 50, 6),
   {'kept': [1, 2], 'promoted': [], 'threshold': 6, 'used': 11}),
  ('control: empty survivor set',
   ([], 101, 50, 15),
   {'kept': [], 'promoted': [], 'threshold': 15, 'used': 0})],
 [('regression: cumulative sizes cross the desired size',
   ([[1, 1, 20], [2, 2, 25], [3, 3, 10], [4, 4, 30], [5, 1, 2]], 100, 50, 15),
   {'kept': [1, 2, 5], 'promoted': [3, 4], 'threshold': 3, 'used': 47}),
  ('cumulative size exactly at the desired size',
   ([[1, 1, 30], [2, 2, 20], [3, 3, 7]], 100, 50, 15),
   {'kept': [1, 2], 'promoted': [3], 'threshold': 3, 'used': 50}),
  ('ratio of a capacity that is not a multiple of 100',
   ([[1, 1, 40], [2, 2, 30], [3, 3, 2]], 150, 50, 15),
   {'kept': [1, 2, 3], 'promoted': [], 'threshold': 15, 'used': 72}),
  ('survivors overflow the survivor space',
   ([[1, 1, 30], [2, 1, 30], [3, 2, 30], [4, 1, 12], [5, 2, 40]], 100, 200, 3),
   {'kept': [1, 2, 4], 'promoted': [3, 5], 'threshold': 3, 'used': 72}),
  ('survivors fill the space exactly',
   ([[1, 1, 60], [2, 1, 40], [3, 2, 2]], 100, 200, 2),
   {'kept': [1, 2], 'promoted': [3], 'threshold': 2, 'used': 100}),
  ('threshold never crossed',
   ([[1, 1, 5], [2, 3, 7]], 100, 50, 6),
   {'kept': [1, 2], 'promoted': [], 'threshold': 6, 'used': 12}),
  ('control: empty survivor set',
   ([], 102, 50, 15),
   {'kept': [], 'promoted': [], 'threshold': 15, 'used': 0})],
 [('regression: cumulative sizes cross the desired size',
   ([[1, 1, 20], [2, 2, 25], [3, 3, 10], [4, 4, 30], [5, 1, 3]], 100, 50, 15),
   {'kept': [1, 2, 5], 'promoted': [3, 4], 'threshold': 3, 'used': 48}),
  ('cumulative size exactly at the desired size',
   ([[1, 1, 30], [2, 2, 20], [3, 3, 8]], 100, 50, 15),
   {'kept': [1, 2], 'promoted': [3], 'threshold': 3, 'used': 50}),
  ('ratio of a capacity that is not a multiple of 100',
   ([[1, 1, 40], [2, 2, 30], [3, 3, 3]], 150, 50, 15),
   {'kept': [1, 2, 3], 'promoted': [], 'threshold': 15, 'used': 73}),
  ('survivors overflow the survivor space',
   ([[1, 1, 30], [2, 1, 30], [3, 2, 30], [4, 1, 13], [5, 2, 40]], 100, 200, 3),
   {'kept': [1, 2, 4], 'promoted': [3, 5], 'threshold': 3, 'used': 73}),
  ('survivors fill the space exactly',
   ([[1, 1, 60], [2, 1, 40], [3, 2, 3]], 100, 200, 2),
   {'kept': [1, 2], 'promoted': [3], 'threshold': 2, 'used': 100}),
  ('threshold never crossed',
   ([[1, 1, 5], [2, 3, 8]], 100, 50, 6),
   {'kept': [1, 2], 'promoted': [], 'threshold': 6, 'used': 13}),
  ('control: empty survivor set',
   ([], 103, 50, 15),
   {'kept': [], 'promoted': [], 'threshold': 15, 'used': 0})],
 [('regression: cumulative sizes cross the desired size',
   ([[1, 1, 20], [2, 2, 25], [3, 3, 10], [4, 4, 30], [5, 1, 4]], 100, 50, 15),
   {'kept': [1, 2, 5], 'promoted': [3, 4], 'threshold': 3, 'used': 49}),
  ('cumulative size exactly at the desired size',
   ([[1, 1, 30], [2, 2, 20], [3, 3, 9]], 100, 50, 15),
   {'kept': [1, 2], 'promoted': [3], 'threshold': 3, 'used': 50}),
  ('ratio of a capacity that is not a multiple of 100',
   ([[1, 1, 40], [2, 2, 30], [3, 3, 4]], 150, 50, 15),
   {'kept': [1, 2, 3], 'promoted': [], 'threshold': 15, 'used': 74}),
  ('survivors overflow the survivor space',
   ([[1, 1, 30], [2, 1, 30], [3, 2, 30], [4, 1, 14], [5, 2, 40]], 100, 200, 3),
   {'kept': [1, 2, 4], 'promoted': [3, 5], 'threshold': 3, 'used': 74}),
  ('survivors fill the space exactly',
   ([[1, 1, 60], [2, 1, 40], [3, 2, 4]], 100, 200, 2),
   {'kept': [1, 2], 'promoted': [3], 'threshold': 2, 'used': 100}),
  ('threshold never crossed',
   ([[1, 1, 5], [2, 3, 9]], 100, 50, 6),
   {'kept': [1, 2], 'promoted': [], 'threshold': 6, 'used': 14}),
  ('control: empty survivor set',
   ([], 104, 50, 15),
   {'kept': [], 'promoted': [], 'threshold': 15, 'used': 0})],
 [('regression: cumulative sizes cross the desired size',
   ([[1, 1, 20], [2, 2, 25], [3, 3, 10], [4, 4, 30], [5, 1, 5]], 100, 50, 15),
   {'kept': [1, 2, 5], 'promoted': [3, 4], 'threshold': 3, 'used': 50}),
  ('cumulative size exactly at the desired size',
   ([[1, 1, 30], [2, 2, 20], [3, 3, 10]], 100, 50, 15),
   {'kept': [1, 2], 'promoted': [3], 'threshold': 3, 'used': 50}),
  ('ratio of a capacity that is not a multiple of 100',
   ([[1, 1, 40], [2, 2, 30], [3, 3, 5]], 150, 50, 15),
   {'kept': [1, 2, 3], 'promoted': [], 'threshold': 15, 'used': 75}),
  ('survivors overflow the survivor space',
   ([[1, 1, 30], [2, 1, 30], [3, 2, 30], [4, 1, 15], [5, 2, 40]], 100, 200, 3),
   {'kept': [1, 2, 4], 'promoted': [3, 5], 'threshold': 3, 'used': 75}),
  ('survivors fill the space exactly',
   ([[1, 1, 60], [2, 1, 40], [3, 2, 5]], 100, 200, 2),
   {'kept': [1, 2], 'promoted': [3], 'threshold': 2, 'used': 100}),
  ('threshold never crossed',
   ([[1, 1, 5], [2, 3, 10]], 100, 50, 6),
   {'kept': [1, 2], 'promoted': [], 'threshold': 6, 'used': 15}),
  ('control: empty survivor set',
   ([], 105, 50, 15),
   {'kept': [], 'promoted': [], 'threshold': 15, 'used': 0})]]
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: cumulative sizes cross the desired size{'kept': [1, 2, 5], 'promoted': [3, 4], 'threshold': 3, 'used': 46}{'kept': [1, 2, 5], 'promoted': [3, 4], 'threshold': 3, 'used': 46}Passed
cumulative size exactly at the desired size{'kept': [1, 2], 'promoted': [3], 'threshold': 3, 'used': 50}{'kept': [1, 2], 'promoted': [3], 'threshold': 3, 'used': 50}Passed
ratio of a capacity that is not a multiple of 100{'kept': [1, 2, 3], 'promoted': [], 'threshold': 15, 'used': 71}{'kept': [1, 2, 3], 'promoted': [], 'threshold': 15, 'used': 71}Passed
survivors overflow the survivor space{'kept': [1, 2, 4], 'promoted': [3, 5], 'threshold': 3, 'used': 71}{'kept': [1, 2, 4], 'promoted': [3, 5], 'threshold': 3, 'used': 71}Passed
survivors fill the space exactly{'kept': [1], 'promoted': [2, 3], 'threshold': 2, 'used': 60}{'kept': [1, 2], 'promoted': [3], 'threshold': 2, 'used': 100}Failed
threshold never crossed{'kept': [1, 2], 'promoted': [], 'threshold': 6, 'used': 11}{'kept': [1, 2], 'promoted': [], 'threshold': 6, 'used': 11}Passed
control: empty survivor set{'kept': [], 'promoted': [], 'threshold': 15, 'used': 0}{'kept': [], 'promoted': [], 'threshold': 15, 'used': 0}Passed

SHA-256 / ecfbaa74b217219f667ffd932afcf04c547151e122f1ebd78d25130b5a588e7c

2 / The unsuccessful fix

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

N = 1
observations = []
def solve(ages, capacity, ratio, max_threshold):
    desired = capacity * ratio // 100
    by_age = {}
    for _, age, size in ages:
        by_age[age] = by_age.get(age, 0) + size
    total = 0
    threshold = max_threshold
    for age in range(1, max_threshold + 1):
        total += by_age.get(age, 0)
        if total > desired:
            threshold = age
            break
    promote = [o for o, age, size in ages if age >= threshold]
    stay = sorted([x for x in ages if x[1] < threshold], key=lambda x: (x[1], x[0]))
    used = 0
    kept = []
    for o, age, size in stay:
        if used < capacity:
            kept.append(o)
            used += size
        else:
            promote.append(o)
    return {'threshold': threshold, 'promoted': sorted(promote), 'kept': sorted(kept), 'used': used}
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = [[('regression: cumulative sizes cross the desired size',
   ([[1, 1, 20], [2, 2, 25], [3, 3, 10], [4, 4, 30], [5, 1, 1]], 100, 50, 15),
   {'kept': [1, 2, 5], 'promoted': [3, 4], 'threshold': 3, 'used': 46}),
  ('cumulative size exactly at the desired size',
   ([[1, 1, 30], [2, 2, 20], [3, 3, 6]], 100, 50, 15),
   {'kept': [1, 2], 'promoted': [3], 'threshold': 3, 'used': 50}),
  ('ratio of a capacity that is not a multiple of 100',
   ([[1, 1, 40], [2, 2, 30], [3, 3, 1]], 150, 50, 15),
   {'kept': [1, 2, 3], 'promoted': [], 'threshold': 15, 'used': 71}),
  ('survivors overflow the survivor space',
   ([[1, 1, 30], [2, 1, 30], [3, 2, 30], [4, 1, 11], [5, 2, 40]], 100, 200, 3),
   {'kept': [1, 2, 4], 'promoted': [3, 5], 'threshold': 3, 'used': 71}),
  ('survivors fill the space exactly',
   ([[1, 1, 60], [2, 1, 40], [3, 2, 1]], 100, 200, 2),
   {'kept': [1, 2], 'promoted': [3], 'threshold': 2, 'used': 100}),
  ('threshold never crossed',
   ([[1, 1, 5], [2, 3, 6]], 100, 50, 6),
   {'kept': [1, 2], 'promoted': [], 'threshold': 6, 'used': 11}),
  ('control: empty survivor set',
   ([], 101, 50, 15),
   {'kept': [], 'promoted': [], 'threshold': 15, 'used': 0})],
 [('regression: cumulative sizes cross the desired size',
   ([[1, 1, 20], [2, 2, 25], [3, 3, 10], [4, 4, 30], [5, 1, 2]], 100, 50, 15),
   {'kept': [1, 2, 5], 'promoted': [3, 4], 'threshold': 3, 'used': 47}),
  ('cumulative size exactly at the desired size',
   ([[1, 1, 30], [2, 2, 20], [3, 3, 7]], 100, 50, 15),
   {'kept': [1, 2], 'promoted': [3], 'threshold': 3, 'used': 50}),
  ('ratio of a capacity that is not a multiple of 100',
   ([[1, 1, 40], [2, 2, 30], [3, 3, 2]], 150, 50, 15),
   {'kept': [1, 2, 3], 'promoted': [], 'threshold': 15, 'used': 72}),
  ('survivors overflow the survivor space',
   ([[1, 1, 30], [2, 1, 30], [3, 2, 30], [4, 1, 12], [5, 2, 40]], 100, 200, 3),
   {'kept': [1, 2, 4], 'promoted': [3, 5], 'threshold': 3, 'used': 72}),
  ('survivors fill the space exactly',
   ([[1, 1, 60], [2, 1, 40], [3, 2, 2]], 100, 200, 2),
   {'kept': [1, 2], 'promoted': [3], 'threshold': 2, 'used': 100}),
  ('threshold never crossed',
   ([[1, 1, 5], [2, 3, 7]], 100, 50, 6),
   {'kept': [1, 2], 'promoted': [], 'threshold': 6, 'used': 12}),
  ('control: empty survivor set',
   ([], 102, 50, 15),
   {'kept': [], 'promoted': [], 'threshold': 15, 'used': 0})],
 [('regression: cumulative sizes cross the desired size',
   ([[1, 1, 20], [2, 2, 25], [3, 3, 10], [4, 4, 30], [5, 1, 3]], 100, 50, 15),
   {'kept': [1, 2, 5], 'promoted': [3, 4], 'threshold': 3, 'used': 48}),
  ('cumulative size exactly at the desired size',
   ([[1, 1, 30], [2, 2, 20], [3, 3, 8]], 100, 50, 15),
   {'kept': [1, 2], 'promoted': [3], 'threshold': 3, 'used': 50}),
  ('ratio of a capacity that is not a multiple of 100',
   ([[1, 1, 40], [2, 2, 30], [3, 3, 3]], 150, 50, 15),
   {'kept': [1, 2, 3], 'promoted': [], 'threshold': 15, 'used': 73}),
  ('survivors overflow the survivor space',
   ([[1, 1, 30], [2, 1, 30], [3, 2, 30], [4, 1, 13], [5, 2, 40]], 100, 200, 3),
   {'kept': [1, 2, 4], 'promoted': [3, 5], 'threshold': 3, 'used': 73}),
  ('survivors fill the space exactly',
   ([[1, 1, 60], [2, 1, 40], [3, 2, 3]], 100, 200, 2),
   {'kept': [1, 2], 'promoted': [3], 'threshold': 2, 'used': 100}),
  ('threshold never crossed',
   ([[1, 1, 5], [2, 3, 8]], 100, 50, 6),
   {'kept': [1, 2], 'promoted': [], 'threshold': 6, 'used': 13}),
  ('control: empty survivor set',
   ([], 103, 50, 15),
   {'kept': [], 'promoted': [], 'threshold': 15, 'used': 0})],
 [('regression: cumulative sizes cross the desired size',
   ([[1, 1, 20], [2, 2, 25], [3, 3, 10], [4, 4, 30], [5, 1, 4]], 100, 50, 15),
   {'kept': [1, 2, 5], 'promoted': [3, 4], 'threshold': 3, 'used': 49}),
  ('cumulative size exactly at the desired size',
   ([[1, 1, 30], [2, 2, 20], [3, 3, 9]], 100, 50, 15),
   {'kept': [1, 2], 'promoted': [3], 'threshold': 3, 'used': 50}),
  ('ratio of a capacity that is not a multiple of 100',
   ([[1, 1, 40], [2, 2, 30], [3, 3, 4]], 150, 50, 15),
   {'kept': [1, 2, 3], 'promoted': [], 'threshold': 15, 'used': 74}),
  ('survivors overflow the survivor space',
   ([[1, 1, 30], [2, 1, 30], [3, 2, 30], [4, 1, 14], [5, 2, 40]], 100, 200, 3),
   {'kept': [1, 2, 4], 'promoted': [3, 5], 'threshold': 3, 'used': 74}),
  ('survivors fill the space exactly',
   ([[1, 1, 60], [2, 1, 40], [3, 2, 4]], 100, 200, 2),
   {'kept': [1, 2], 'promoted': [3], 'threshold': 2, 'used': 100}),
  ('threshold never crossed',
   ([[1, 1, 5], [2, 3, 9]], 100, 50, 6),
   {'kept': [1, 2], 'promoted': [], 'threshold': 6, 'used': 14}),
  ('control: empty survivor set',
   ([], 104, 50, 15),
   {'kept': [], 'promoted': [], 'threshold': 15, 'used': 0})],
 [('regression: cumulative sizes cross the desired size',
   ([[1, 1, 20], [2, 2, 25], [3, 3, 10], [4, 4, 30], [5, 1, 5]], 100, 50, 15),
   {'kept': [1, 2, 5], 'promoted': [3, 4], 'threshold': 3, 'used': 50}),
  ('cumulative size exactly at the desired size',
   ([[1, 1, 30], [2, 2, 20], [3, 3, 10]], 100, 50, 15),
   {'kept': [1, 2], 'promoted': [3], 'threshold': 3, 'used': 50}),
  ('ratio of a capacity that is not a multiple of 100',
   ([[1, 1, 40], [2, 2, 30], [3, 3, 5]], 150, 50, 15),
   {'kept': [1, 2, 3], 'promoted': [], 'threshold': 15, 'used': 75}),
  ('survivors overflow the survivor space',
   ([[1, 1, 30], [2, 1, 30], [3, 2, 30], [4, 1, 15], [5, 2, 40]], 100, 200, 3),
   {'kept': [1, 2, 4], 'promoted': [3, 5], 'threshold': 3, 'used': 75}),
  ('survivors fill the space exactly',
   ([[1, 1, 60], [2, 1, 40], [3, 2, 5]], 100, 200, 2),
   {'kept': [1, 2], 'promoted': [3], 'threshold': 2, 'used': 100}),
  ('threshold never crossed',
   ([[1, 1, 5], [2, 3, 10]], 100, 50, 6),
   {'kept': [1, 2], 'promoted': [], 'threshold': 6, 'used': 15}),
  ('control: empty survivor set',
   ([], 105, 50, 15),
   {'kept': [], 'promoted': [], 'threshold': 15, 'used': 0})]]
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: cumulative sizes cross the desired size{'kept': [1, 2, 5], 'promoted': [3, 4], 'threshold': 3, 'used': 46}{'kept': [1, 2, 5], 'promoted': [3, 4], 'threshold': 3, 'used': 46}Passed
cumulative size exactly at the desired size{'kept': [1, 2], 'promoted': [3], 'threshold': 3, 'used': 50}{'kept': [1, 2], 'promoted': [3], 'threshold': 3, 'used': 50}Passed
ratio of a capacity that is not a multiple of 100{'kept': [1, 2, 3], 'promoted': [], 'threshold': 15, 'used': 71}{'kept': [1, 2, 3], 'promoted': [], 'threshold': 15, 'used': 71}Passed
survivors overflow the survivor space{'kept': [1, 2, 3, 4], 'promoted': [5], 'threshold': 3, 'used': 101}{'kept': [1, 2, 4], 'promoted': [3, 5], 'threshold': 3, 'used': 71}Failed
survivors fill the space exactly{'kept': [1, 2], 'promoted': [3], 'threshold': 2, 'used': 100}{'kept': [1, 2], 'promoted': [3], 'threshold': 2, 'used': 100}Passed
threshold never crossed{'kept': [1, 2], 'promoted': [], 'threshold': 6, 'used': 11}{'kept': [1, 2], 'promoted': [], 'threshold': 6, 'used': 11}Passed
control: empty survivor set{'kept': [], 'promoted': [], 'threshold': 15, 'used': 0}{'kept': [], 'promoted': [], 'threshold': 15, 'used': 0}Passed

SHA-256 / 0892a78d227ff445bb8632377da7c0d373f0e380f30d7e93cf5c08416002ca3c

HELD IN THE MEMBER ARCHIVE

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

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

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

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

Sign in to the archive ↗

Verification & scope

A deterministic, bounded teaching model of one garbage-collector mechanism with stipulated rules; it is not a production collector and claims no conformance to any particular runtime. This reproducer isolates one failure mechanism. Results cover the supplied fixtures. Variants within a family share a test contract and should remain grouped when constructing evaluation splits. Related mechanisms with a shared evaluation_group must also remain together; these controlled models are not independent production incidents.

Observations recorded using Python 3.12.14 at 2026-09-29T14:51:28.488741+00:00.

Case digest / 588d2e5f918254c0934b8e41eaa4590ce7a198506027dea7da74f89ee2fc50c7