FA-90836 / Garbage collector invariants / Open access
Heap resizing: free share truncated to zero · case 01
Every collection grows the heap regardless of free space.
ROOT CAUSE
free // cap is evaluated first and is 0 whenever free < cap.
VERIFIED REPAIR
Compare free * 100 with min_free * cap.
Unsuccessful approach: Measuring free space relative to the live bytes understates the shortage.
Case contract
After each full collection with live bytes L and capacity C: if the free share (C - L) / C is below min_free percent, grow to the smallest capacity whose free share is at least min_free, i.e. ceil(L * 100 / (100 - min_free)), never shrinking and never above max_heap; if the free share exceeds max_free percent, compute ceil(L * 100 / (100 - max_free)) floored at min_heap and move shrink_pct percent of the way from C toward it (integer arithmetic). Otherwise keep C. Return the capacity after each collection.
Why this case matters
Heap sizing policies decide footprint and GC frequency; rounding and clamping errors oscillate or overshoot.
1 / The failure
Exit 1"""Failure Map reference implementation. Python standard library only."""
import json
N = 1
observations = []
def solve(lives, cap0, min_heap, max_heap, min_free, max_free, shrink_pct):
cap = cap0
out = []
for live in lives:
free = cap - live
if free // cap * 100 < min_free:
want = -(-live * 100 // (100 - min_free))
cap = min(max(want, cap), max_heap)
elif free * 100 > max_free * cap:
want = -(-live * 100 // (100 - max_free))
want = max(want, min_heap)
cap = cap - (cap - want) * shrink_pct // 100
out.append(cap)
return out
def check(label, actual, expected):
observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = [[('regression: grow, hold and shrink',
([150, 150, 61, 20], 200, 100, 1000, 40, 70, 50),
[250, 250, 227, 164]),
('growth target rounds up', ([102], 150, 100, 1000, 40, 70, 50), [170]),
('growth clamped at the maximum heap', ([701, 900], 800, 100, 1000, 40, 70, 50), [1000, 1000]),
('shrinking stops at the minimum heap', ([11, 10, 10], 400, 150, 1000, 40, 70, 50), [275, 213, 182]),
('shrink moves part of the way', ([31], 600, 100, 1000, 40, 70, 25), [476]),
('free ratio exactly at the minimum', ([120, 181], 200, 100, 1000, 40, 70, 50), [200, 302]),
('control: within the band', ([101], 200, 100, 1000, 40, 70, 50), [200])],
[('regression: grow, hold and shrink',
([150, 150, 62, 20], 200, 100, 1000, 40, 70, 50),
[250, 250, 229, 165]),
('growth target rounds up', ([103], 150, 100, 1000, 40, 70, 50), [172]),
('growth clamped at the maximum heap', ([702, 900], 800, 100, 1000, 40, 70, 50), [1000, 1000]),
('shrinking stops at the minimum heap', ([12, 10, 10], 400, 150, 1000, 40, 70, 50), [275, 213, 182]),
('shrink moves part of the way', ([32], 600, 100, 1000, 40, 70, 25), [477]),
('free ratio exactly at the minimum', ([120, 182], 200, 100, 1000, 40, 70, 50), [200, 304]),
('control: within the band', ([102], 200, 100, 1000, 40, 70, 50), [200])],
[('regression: grow, hold and shrink',
([150, 150, 63, 20], 200, 100, 1000, 40, 70, 50),
[250, 250, 230, 165]),
('growth target rounds up', ([104], 150, 100, 1000, 40, 70, 50), [174]),
('growth clamped at the maximum heap', ([703, 900], 800, 100, 1000, 40, 70, 50), [1000, 1000]),
('shrinking stops at the minimum heap', ([13, 10, 10], 400, 150, 1000, 40, 70, 50), [275, 213, 182]),
('shrink moves part of the way', ([33], 600, 100, 1000, 40, 70, 25), [478]),
('free ratio exactly at the minimum', ([120, 183], 200, 100, 1000, 40, 70, 50), [200, 305]),
('control: within the band', ([103], 200, 100, 1000, 40, 70, 50), [200])],
[('regression: grow, hold and shrink',
([150, 150, 64, 20], 200, 100, 1000, 40, 70, 50),
[250, 250, 232, 166]),
('growth target rounds up', ([105], 150, 100, 1000, 40, 70, 50), [175]),
('growth clamped at the maximum heap', ([704, 900], 800, 100, 1000, 40, 70, 50), [1000, 1000]),
('shrinking stops at the minimum heap', ([14, 10, 10], 400, 150, 1000, 40, 70, 50), [275, 213, 182]),
('shrink moves part of the way', ([34], 600, 100, 1000, 40, 70, 25), [479]),
('free ratio exactly at the minimum', ([120, 184], 200, 100, 1000, 40, 70, 50), [200, 307]),
('control: within the band', ([104], 200, 100, 1000, 40, 70, 50), [200])],
[('regression: grow, hold and shrink',
([150, 150, 65, 20], 200, 100, 1000, 40, 70, 50),
[250, 250, 234, 167]),
('growth target rounds up', ([106], 150, 100, 1000, 40, 70, 50), [177]),
('growth clamped at the maximum heap', ([705, 900], 800, 100, 1000, 40, 70, 50), [1000, 1000]),
('shrinking stops at the minimum heap', ([15, 10, 10], 400, 150, 1000, 40, 70, 50), [275, 213, 182]),
('shrink moves part of the way', ([35], 600, 100, 1000, 40, 70, 25), [480]),
('free ratio exactly at the minimum', ([120, 185], 200, 100, 1000, 40, 70, 50), [200, 309]),
('control: within the band', ([105], 200, 100, 1000, 40, 70, 50), [200])]]
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: grow, hold and shrink | [250, 250, 250, 250] | [250, 250, 227, 164] | Failed |
| growth target rounds up | [170] | [170] | Passed |
| growth clamped at the maximum heap | [1000, 1000] | [1000, 1000] | Passed |
| shrinking stops at the minimum heap | [400, 400, 400] | [275, 213, 182] | Failed |
| shrink moves part of the way | [600] | [476] | Failed |
| free ratio exactly at the minimum | [200, 302] | [200, 302] | Passed |
| control: within the band | [200] | [200] | Passed |
SHA-256 / eec7348bea52aed59ad4330cbf688723c44726d09abec69d67b2c2dfdb72d16e
2 / The unsuccessful fix
Exit 1"""Failure Map reference implementation. Python standard library only."""
import json
N = 1
observations = []
def solve(lives, cap0, min_heap, max_heap, min_free, max_free, shrink_pct):
cap = cap0
out = []
for live in lives:
free = cap - live
if free * 100 < min_free * live:
want = -(-live * 100 // (100 - min_free))
cap = min(max(want, cap), max_heap)
elif free * 100 > max_free * cap:
want = -(-live * 100 // (100 - max_free))
want = max(want, min_heap)
cap = cap - (cap - want) * shrink_pct // 100
out.append(cap)
return out
def check(label, actual, expected):
observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = [[('regression: grow, hold and shrink',
([150, 150, 61, 20], 200, 100, 1000, 40, 70, 50),
[250, 250, 227, 164]),
('growth target rounds up', ([102], 150, 100, 1000, 40, 70, 50), [170]),
('growth clamped at the maximum heap', ([701, 900], 800, 100, 1000, 40, 70, 50), [1000, 1000]),
('shrinking stops at the minimum heap', ([11, 10, 10], 400, 150, 1000, 40, 70, 50), [275, 213, 182]),
('shrink moves part of the way', ([31], 600, 100, 1000, 40, 70, 25), [476]),
('free ratio exactly at the minimum', ([120, 181], 200, 100, 1000, 40, 70, 50), [200, 302]),
('control: within the band', ([101], 200, 100, 1000, 40, 70, 50), [200])],
[('regression: grow, hold and shrink',
([150, 150, 62, 20], 200, 100, 1000, 40, 70, 50),
[250, 250, 229, 165]),
('growth target rounds up', ([103], 150, 100, 1000, 40, 70, 50), [172]),
('growth clamped at the maximum heap', ([702, 900], 800, 100, 1000, 40, 70, 50), [1000, 1000]),
('shrinking stops at the minimum heap', ([12, 10, 10], 400, 150, 1000, 40, 70, 50), [275, 213, 182]),
('shrink moves part of the way', ([32], 600, 100, 1000, 40, 70, 25), [477]),
('free ratio exactly at the minimum', ([120, 182], 200, 100, 1000, 40, 70, 50), [200, 304]),
('control: within the band', ([102], 200, 100, 1000, 40, 70, 50), [200])],
[('regression: grow, hold and shrink',
([150, 150, 63, 20], 200, 100, 1000, 40, 70, 50),
[250, 250, 230, 165]),
('growth target rounds up', ([104], 150, 100, 1000, 40, 70, 50), [174]),
('growth clamped at the maximum heap', ([703, 900], 800, 100, 1000, 40, 70, 50), [1000, 1000]),
('shrinking stops at the minimum heap', ([13, 10, 10], 400, 150, 1000, 40, 70, 50), [275, 213, 182]),
('shrink moves part of the way', ([33], 600, 100, 1000, 40, 70, 25), [478]),
('free ratio exactly at the minimum', ([120, 183], 200, 100, 1000, 40, 70, 50), [200, 305]),
('control: within the band', ([103], 200, 100, 1000, 40, 70, 50), [200])],
[('regression: grow, hold and shrink',
([150, 150, 64, 20], 200, 100, 1000, 40, 70, 50),
[250, 250, 232, 166]),
('growth target rounds up', ([105], 150, 100, 1000, 40, 70, 50), [175]),
('growth clamped at the maximum heap', ([704, 900], 800, 100, 1000, 40, 70, 50), [1000, 1000]),
('shrinking stops at the minimum heap', ([14, 10, 10], 400, 150, 1000, 40, 70, 50), [275, 213, 182]),
('shrink moves part of the way', ([34], 600, 100, 1000, 40, 70, 25), [479]),
('free ratio exactly at the minimum', ([120, 184], 200, 100, 1000, 40, 70, 50), [200, 307]),
('control: within the band', ([104], 200, 100, 1000, 40, 70, 50), [200])],
[('regression: grow, hold and shrink',
([150, 150, 65, 20], 200, 100, 1000, 40, 70, 50),
[250, 250, 234, 167]),
('growth target rounds up', ([106], 150, 100, 1000, 40, 70, 50), [177]),
('growth clamped at the maximum heap', ([705, 900], 800, 100, 1000, 40, 70, 50), [1000, 1000]),
('shrinking stops at the minimum heap', ([15, 10, 10], 400, 150, 1000, 40, 70, 50), [275, 213, 182]),
('shrink moves part of the way', ([35], 600, 100, 1000, 40, 70, 25), [480]),
('free ratio exactly at the minimum', ([120, 185], 200, 100, 1000, 40, 70, 50), [200, 309]),
('control: within the band', ([105], 200, 100, 1000, 40, 70, 50), [200])]]
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: grow, hold and shrink | [250, 250, 227, 164] | [250, 250, 227, 164] | Passed |
| growth target rounds up | [150] | [170] | Failed |
| growth clamped at the maximum heap | [1000, 1000] | [1000, 1000] | Passed |
| shrinking stops at the minimum heap | [275, 213, 182] | [275, 213, 182] | Passed |
| shrink moves part of the way | [476] | [476] | Passed |
| free ratio exactly at the minimum | [200, 302] | [200, 302] | Passed |
| control: within the band | [200] | [200] | Passed |
SHA-256 / bb0728481a3df23b149598a6b89fc518065b92d874ee878d209afcebbd2ef15f
3 / The verified repair
Exit 0"""Failure Map reference implementation. Python standard library only."""
import json
N = 1
observations = []
def solve(lives, cap0, min_heap, max_heap, min_free, max_free, shrink_pct):
cap = cap0
out = []
for live in lives:
free = cap - live
if free * 100 < min_free * cap:
want = -(-live * 100 // (100 - min_free))
cap = min(max(want, cap), max_heap)
elif free * 100 > max_free * cap:
want = -(-live * 100 // (100 - max_free))
want = max(want, min_heap)
cap = cap - (cap - want) * shrink_pct // 100
out.append(cap)
return out
def check(label, actual, expected):
observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = [[('regression: grow, hold and shrink',
([150, 150, 61, 20], 200, 100, 1000, 40, 70, 50),
[250, 250, 227, 164]),
('growth target rounds up', ([102], 150, 100, 1000, 40, 70, 50), [170]),
('growth clamped at the maximum heap', ([701, 900], 800, 100, 1000, 40, 70, 50), [1000, 1000]),
('shrinking stops at the minimum heap', ([11, 10, 10], 400, 150, 1000, 40, 70, 50), [275, 213, 182]),
('shrink moves part of the way', ([31], 600, 100, 1000, 40, 70, 25), [476]),
('free ratio exactly at the minimum', ([120, 181], 200, 100, 1000, 40, 70, 50), [200, 302]),
('control: within the band', ([101], 200, 100, 1000, 40, 70, 50), [200])],
[('regression: grow, hold and shrink',
([150, 150, 62, 20], 200, 100, 1000, 40, 70, 50),
[250, 250, 229, 165]),
('growth target rounds up', ([103], 150, 100, 1000, 40, 70, 50), [172]),
('growth clamped at the maximum heap', ([702, 900], 800, 100, 1000, 40, 70, 50), [1000, 1000]),
('shrinking stops at the minimum heap', ([12, 10, 10], 400, 150, 1000, 40, 70, 50), [275, 213, 182]),
('shrink moves part of the way', ([32], 600, 100, 1000, 40, 70, 25), [477]),
('free ratio exactly at the minimum', ([120, 182], 200, 100, 1000, 40, 70, 50), [200, 304]),
('control: within the band', ([102], 200, 100, 1000, 40, 70, 50), [200])],
[('regression: grow, hold and shrink',
([150, 150, 63, 20], 200, 100, 1000, 40, 70, 50),
[250, 250, 230, 165]),
('growth target rounds up', ([104], 150, 100, 1000, 40, 70, 50), [174]),
('growth clamped at the maximum heap', ([703, 900], 800, 100, 1000, 40, 70, 50), [1000, 1000]),
('shrinking stops at the minimum heap', ([13, 10, 10], 400, 150, 1000, 40, 70, 50), [275, 213, 182]),
('shrink moves part of the way', ([33], 600, 100, 1000, 40, 70, 25), [478]),
('free ratio exactly at the minimum', ([120, 183], 200, 100, 1000, 40, 70, 50), [200, 305]),
('control: within the band', ([103], 200, 100, 1000, 40, 70, 50), [200])],
[('regression: grow, hold and shrink',
([150, 150, 64, 20], 200, 100, 1000, 40, 70, 50),
[250, 250, 232, 166]),
('growth target rounds up', ([105], 150, 100, 1000, 40, 70, 50), [175]),
('growth clamped at the maximum heap', ([704, 900], 800, 100, 1000, 40, 70, 50), [1000, 1000]),
('shrinking stops at the minimum heap', ([14, 10, 10], 400, 150, 1000, 40, 70, 50), [275, 213, 182]),
('shrink moves part of the way', ([34], 600, 100, 1000, 40, 70, 25), [479]),
('free ratio exactly at the minimum', ([120, 184], 200, 100, 1000, 40, 70, 50), [200, 307]),
('control: within the band', ([104], 200, 100, 1000, 40, 70, 50), [200])],
[('regression: grow, hold and shrink',
([150, 150, 65, 20], 200, 100, 1000, 40, 70, 50),
[250, 250, 234, 167]),
('growth target rounds up', ([106], 150, 100, 1000, 40, 70, 50), [177]),
('growth clamped at the maximum heap', ([705, 900], 800, 100, 1000, 40, 70, 50), [1000, 1000]),
('shrinking stops at the minimum heap', ([15, 10, 10], 400, 150, 1000, 40, 70, 50), [275, 213, 182]),
('shrink moves part of the way', ([35], 600, 100, 1000, 40, 70, 25), [480]),
('free ratio exactly at the minimum', ([120, 185], 200, 100, 1000, 40, 70, 50), [200, 309]),
('control: within the band', ([105], 200, 100, 1000, 40, 70, 50), [200])]]
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: grow, hold and shrink | [250, 250, 227, 164] | [250, 250, 227, 164] | Passed |
| growth target rounds up | [170] | [170] | Passed |
| growth clamped at the maximum heap | [1000, 1000] | [1000, 1000] | Passed |
| shrinking stops at the minimum heap | [275, 213, 182] | [275, 213, 182] | Passed |
| shrink moves part of the way | [476] | [476] | Passed |
| free ratio exactly at the minimum | [200, 302] | [200, 302] | Passed |
| control: within the band | [200] | [200] | Passed |
SHA-256 / fd89ff53c5c2b06e6a4b623cc9dcce1577997d25a8f653da92d09555431b27ee
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:30.374533+00:00.
Case digest / 2e7d0ecefa69ef298f204d5333820aed828bacd3befd2da0411b9cb936a4a775