FA-90821 / Garbage collector invariants / Open access
Heap resizing: growth ignores the maximum heap size · case 01
The heap grows past its configured maximum.
ROOT CAUSE
The expanded capacity is not clamped.
VERIFIED REPAIR
Clamp the new capacity at max_heap.
Unsuccessful approach: Refusing to grow at all when the target exceeds the maximum leaves the heap too small.
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 * 100 < min_free * cap:
want = -(-live * 100 // (100 - min_free))
cap = max(want, cap)
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 | [1169, 1500] | [1000, 1000] | Failed |
| 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 / 3075c7909b45be1a846e5bad57f5643727535d6bc682deeefeb56c9f8a633cad
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 * cap:
want = -(-live * 100 // (100 - min_free))
cap = want if want <= max_heap else cap
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 | [800, 800] | [1000, 1000] | Failed |
| 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 / deffd47282b53abc973374c13fa982c80ac5b47f302aaf836b3a05869e5eed1e
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.296205+00:00.
Case digest / 6ca88d4c8a0a33a126df86f1b73fe59194040146cb450c3ecf6cf589a6dc0a30