FA-90761 / Garbage collector invariants / Open access
TLAB: refill waste limit reset instead of raised · case 01
After a slow-path allocation the limit collapses, so a thread keeps retiring buffers too eagerly or never adapts.
ROOT CAUSE
The limit is overwritten with the increment instead of being raised by it.
VERIFIED REPAIR
Increase the limit by the increment on every slow-path allocation.
Unsuccessful approach: Resetting to the initial limit plus one increment does not accumulate.
Case contract
Bump allocation through a thread-local buffer (TLAB). Requests are rounded up to 8 bytes. Requests larger than half a TLAB go straight to shared eden. Otherwise allocate in the TLAB when it fits (end inclusive). If not, and the TLAB still has more free space than the refill waste limit, allocate this object in eden, keep the TLAB and raise the limit by waste_inc; else retire the TLAB (its remaining space counts as waste) and carve a new TLAB from eden. Eden allocations fail (None) when they would end beyond eden_end. Return addresses, total waste, eden top and the final limit.
Why this case matters
Allocation fast paths decide heap layout and GC frequency; boundary slips waste memory or overlap objects.
1 / The failure
Exit 1"""Failure Map reference implementation. Python standard library only."""
import json
N = 1
observations = []
def solve(reqs, eden_start, eden_end, tlab_size, waste_limit, waste_inc):
top = eden_start
tlab_end = 0
cur = 0
limit = waste_limit
waste = 0
out = []
def eden_alloc(n):
nonlocal top
if top + n > eden_end:
return None
a = top
top += n
return a
for r in reqs:
n = (r + 7) // 8 * 8
if n > tlab_size // 2:
out.append(eden_alloc(n))
continue
if cur + n <= tlab_end:
out.append(cur)
cur += n
continue
remaining = tlab_end - cur
if remaining > limit:
limit = waste_inc
out.append(eden_alloc(n))
continue
start = eden_alloc(tlab_size)
if start is None:
out.append(None)
continue
waste += remaining
tlab_end = start + tlab_size
cur = start + n
out.append(start)
return {'addrs': out, 'waste': waste, 'top': top, 'limit': limit}
def check(label, actual, expected):
observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = [[('regression: refill, slow path and adaptation',
([40, 40, 40, 16, 24, 8, 48, 64], 0, 2048, 128, 16, 8),
{'addrs': [0, 40, 80, 128, 144, 168, 176, 256], 'limit': 24, 'top': 320, 'waste': 8}),
('allocation exactly filling the buffer',
([64, 56, 8, 8], 0, 4096, 128, 17, 8),
{'addrs': [0, 64, 120, 128], 'limit': 17, 'top': 256, 'waste': 0}),
('unaligned requests near the buffer end',
([60, 57, 1], 0, 4096, 128, 16, 8),
{'addrs': [0, 64, 128], 'limit': 16, 'top': 256, 'waste': 0}),
('remaining space exactly at the waste limit',
([56, 56, 24, 8], 0, 4096, 128, 16, 8),
{'addrs': [0, 56, 128, 152], 'limit': 16, 'top': 256, 'waste': 16}),
('repeated slow paths raise the limit',
([64, 40, 40, 40, 40, 40, 8], 0, 4096, 128, 16, 4),
{'addrs': [0, 64, 128, 168, 208, 248, 288], 'limit': 24, 'top': 336, 'waste': 24}),
('request of exactly half a buffer and just above',
([64, 8, 72, 8], 0, 4096, 128, 8, 8),
{'addrs': [0, 64, 128, 72], 'limit': 8, 'top': 200, 'waste': 0}),
('eden filled exactly',
([64, 64, 64, 64, 8], 0, 256, 128, 8, 8),
{'addrs': [0, 64, 128, 192, None], 'limit': 8, 'top': 256, 'waste': 0}),
('eden refill that would overrun',
([64, 64, 8], 0, 200, 128, 8, 8),
{'addrs': [0, 64, None], 'limit': 8, 'top': 128, 'waste': 0})],
[('regression: refill, slow path and adaptation',
([40, 40, 40, 16, 24, 8, 48, 64], 0, 2048, 128, 16, 8),
{'addrs': [0, 40, 80, 128, 144, 168, 176, 256], 'limit': 24, 'top': 320, 'waste': 8}),
('allocation exactly filling the buffer',
([64, 56, 8, 8], 0, 4096, 128, 18, 8),
{'addrs': [0, 64, 120, 128], 'limit': 18, 'top': 256, 'waste': 0}),
('unaligned requests near the buffer end',
([60, 57, 1], 0, 4096, 128, 16, 8),
{'addrs': [0, 64, 128], 'limit': 16, 'top': 256, 'waste': 0}),
('remaining space exactly at the waste limit',
([56, 56, 24, 16], 0, 4096, 128, 16, 8),
{'addrs': [0, 56, 128, 152], 'limit': 16, 'top': 256, 'waste': 16}),
('repeated slow paths raise the limit',
([64, 40, 40, 40, 40, 40, 16], 0, 4096, 128, 16, 4),
{'addrs': [0, 64, 128, 168, 208, 248, 288], 'limit': 24, 'top': 336, 'waste': 24}),
('request of exactly half a buffer and just above',
([64, 8, 72, 16], 0, 4096, 128, 8, 8),
{'addrs': [0, 64, 128, 72], 'limit': 8, 'top': 200, 'waste': 0}),
('eden filled exactly',
([64, 64, 64, 64, 16], 0, 256, 128, 8, 8),
{'addrs': [0, 64, 128, 192, None], 'limit': 8, 'top': 256, 'waste': 0}),
('eden refill that would overrun',
([64, 64, 16], 0, 200, 128, 8, 8),
{'addrs': [0, 64, None], 'limit': 8, 'top': 128, 'waste': 0})],
[('regression: refill, slow path and adaptation',
([40, 40, 40, 16, 24, 8, 48, 64], 0, 2048, 128, 16, 8),
{'addrs': [0, 40, 80, 128, 144, 168, 176, 256], 'limit': 24, 'top': 320, 'waste': 8}),
('allocation exactly filling the buffer',
([64, 56, 8, 8], 0, 4096, 128, 19, 8),
{'addrs': [0, 64, 120, 128], 'limit': 19, 'top': 256, 'waste': 0}),
('unaligned requests near the buffer end',
([60, 57, 1], 0, 4096, 128, 16, 8),
{'addrs': [0, 64, 128], 'limit': 16, 'top': 256, 'waste': 0}),
('remaining space exactly at the waste limit',
([56, 56, 24, 24], 0, 4096, 128, 16, 8),
{'addrs': [0, 56, 128, 152], 'limit': 16, 'top': 256, 'waste': 16}),
('repeated slow paths raise the limit',
([64, 40, 40, 40, 40, 40, 24], 0, 4096, 128, 16, 4),
{'addrs': [0, 64, 128, 168, 208, 248, 288], 'limit': 24, 'top': 336, 'waste': 24}),
('request of exactly half a buffer and just above',
([64, 8, 72, 24], 0, 4096, 128, 8, 8),
{'addrs': [0, 64, 128, 72], 'limit': 8, 'top': 200, 'waste': 0}),
('eden filled exactly',
([64, 64, 64, 64, 24], 0, 256, 128, 8, 8),
{'addrs': [0, 64, 128, 192, None], 'limit': 8, 'top': 256, 'waste': 0}),
('eden refill that would overrun',
([64, 64, 24], 0, 200, 128, 8, 8),
{'addrs': [0, 64, None], 'limit': 8, 'top': 128, 'waste': 0})],
[('regression: refill, slow path and adaptation',
([40, 40, 40, 16, 24, 8, 48, 64], 0, 2048, 128, 16, 8),
{'addrs': [0, 40, 80, 128, 144, 168, 176, 256], 'limit': 24, 'top': 320, 'waste': 8}),
('allocation exactly filling the buffer',
([64, 56, 8, 8], 0, 4096, 128, 20, 8),
{'addrs': [0, 64, 120, 128], 'limit': 20, 'top': 256, 'waste': 0}),
('unaligned requests near the buffer end',
([60, 57, 1], 0, 4096, 128, 16, 8),
{'addrs': [0, 64, 128], 'limit': 16, 'top': 256, 'waste': 0}),
('remaining space exactly at the waste limit',
([56, 56, 24, 32], 0, 4096, 128, 16, 8),
{'addrs': [0, 56, 128, 152], 'limit': 16, 'top': 256, 'waste': 16}),
('repeated slow paths raise the limit',
([64, 40, 40, 40, 40, 40, 32], 0, 4096, 128, 16, 4),
{'addrs': [0, 64, 128, 168, 208, 248, 288], 'limit': 24, 'top': 336, 'waste': 24}),
('request of exactly half a buffer and just above',
([64, 8, 72, 32], 0, 4096, 128, 8, 8),
{'addrs': [0, 64, 128, 72], 'limit': 8, 'top': 200, 'waste': 0}),
('eden filled exactly',
([64, 64, 64, 64, 32], 0, 256, 128, 8, 8),
{'addrs': [0, 64, 128, 192, None], 'limit': 8, 'top': 256, 'waste': 0}),
('eden refill that would overrun',
([64, 64, 32], 0, 200, 128, 8, 8),
{'addrs': [0, 64, None], 'limit': 8, 'top': 128, 'waste': 0})],
[('regression: refill, slow path and adaptation',
([40, 40, 40, 16, 24, 8, 48, 64], 0, 2048, 128, 16, 8),
{'addrs': [0, 40, 80, 128, 144, 168, 176, 256], 'limit': 24, 'top': 320, 'waste': 8}),
('allocation exactly filling the buffer',
([64, 56, 8, 8], 0, 4096, 128, 21, 8),
{'addrs': [0, 64, 120, 128], 'limit': 21, 'top': 256, 'waste': 0}),
('unaligned requests near the buffer end',
([60, 57, 1], 0, 4096, 128, 16, 8),
{'addrs': [0, 64, 128], 'limit': 16, 'top': 256, 'waste': 0}),
('remaining space exactly at the waste limit',
([56, 56, 24, 40], 0, 4096, 128, 16, 8),
{'addrs': [0, 56, 128, 152], 'limit': 16, 'top': 256, 'waste': 16}),
('repeated slow paths raise the limit',
([64, 40, 40, 40, 40, 40, 40], 0, 4096, 128, 16, 4),
{'addrs': [0, 64, 128, 168, 208, 248, 288], 'limit': 24, 'top': 336, 'waste': 24}),
('request of exactly half a buffer and just above',
([64, 8, 72, 40], 0, 4096, 128, 8, 8),
{'addrs': [0, 64, 128, 72], 'limit': 8, 'top': 200, 'waste': 0}),
('eden filled exactly',
([64, 64, 64, 64, 40], 0, 256, 128, 8, 8),
{'addrs': [0, 64, 128, 192, None], 'limit': 8, 'top': 256, 'waste': 0}),
('eden refill that would overrun',
([64, 64, 40], 0, 200, 128, 8, 8),
{'addrs': [0, 64, None], 'limit': 8, 'top': 128, 'waste': 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 fixture | Actual | Expected | Outcome |
|---|---|---|---|
| regression: refill, slow path and adaptation | {'addrs': [0, 40, 80, 128, 144, 168, 176, 256], 'limit': 8, 'top': 320, 'waste': 8} | {'addrs': [0, 40, 80, 128, 144, 168, 176, 256], 'limit': 24, 'top': 320, 'waste': 8} | Failed |
| allocation exactly filling the buffer | {'addrs': [0, 64, 120, 128], 'limit': 17, 'top': 256, 'waste': 0} | {'addrs': [0, 64, 120, 128], 'limit': 17, 'top': 256, 'waste': 0} | Passed |
| unaligned requests near the buffer end | {'addrs': [0, 64, 128], 'limit': 16, 'top': 256, 'waste': 0} | {'addrs': [0, 64, 128], 'limit': 16, 'top': 256, 'waste': 0} | Passed |
| remaining space exactly at the waste limit | {'addrs': [0, 56, 128, 152], 'limit': 16, 'top': 256, 'waste': 16} | {'addrs': [0, 56, 128, 152], 'limit': 16, 'top': 256, 'waste': 16} | Passed |
| repeated slow paths raise the limit | {'addrs': [0, 64, 128, 168, 208, 248, 104], 'limit': 4, 'top': 288, 'waste': 0} | {'addrs': [0, 64, 128, 168, 208, 248, 288], 'limit': 24, 'top': 336, 'waste': 24} | Failed |
| request of exactly half a buffer and just above | {'addrs': [0, 64, 128, 72], 'limit': 8, 'top': 200, 'waste': 0} | {'addrs': [0, 64, 128, 72], 'limit': 8, 'top': 200, 'waste': 0} | Passed |
| eden filled exactly | {'addrs': [0, 64, 128, 192, None], 'limit': 8, 'top': 256, 'waste': 0} | {'addrs': [0, 64, 128, 192, None], 'limit': 8, 'top': 256, 'waste': 0} | Passed |
| eden refill that would overrun | {'addrs': [0, 64, None], 'limit': 8, 'top': 128, 'waste': 0} | {'addrs': [0, 64, None], 'limit': 8, 'top': 128, 'waste': 0} | Passed |
SHA-256 / 9b5e14ab87bdf466620605af1028d829e17ad5ef264375a4d6e5a6452e04a2ee
2 / The unsuccessful fix
Exit 1"""Failure Map reference implementation. Python standard library only."""
import json
N = 1
observations = []
def solve(reqs, eden_start, eden_end, tlab_size, waste_limit, waste_inc):
top = eden_start
tlab_end = 0
cur = 0
limit = waste_limit
waste = 0
out = []
def eden_alloc(n):
nonlocal top
if top + n > eden_end:
return None
a = top
top += n
return a
for r in reqs:
n = (r + 7) // 8 * 8
if n > tlab_size // 2:
out.append(eden_alloc(n))
continue
if cur + n <= tlab_end:
out.append(cur)
cur += n
continue
remaining = tlab_end - cur
if remaining > limit:
limit = waste_limit + waste_inc
out.append(eden_alloc(n))
continue
start = eden_alloc(tlab_size)
if start is None:
out.append(None)
continue
waste += remaining
tlab_end = start + tlab_size
cur = start + n
out.append(start)
return {'addrs': out, 'waste': waste, 'top': top, 'limit': limit}
def check(label, actual, expected):
observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = [[('regression: refill, slow path and adaptation',
([40, 40, 40, 16, 24, 8, 48, 64], 0, 2048, 128, 16, 8),
{'addrs': [0, 40, 80, 128, 144, 168, 176, 256], 'limit': 24, 'top': 320, 'waste': 8}),
('allocation exactly filling the buffer',
([64, 56, 8, 8], 0, 4096, 128, 17, 8),
{'addrs': [0, 64, 120, 128], 'limit': 17, 'top': 256, 'waste': 0}),
('unaligned requests near the buffer end',
([60, 57, 1], 0, 4096, 128, 16, 8),
{'addrs': [0, 64, 128], 'limit': 16, 'top': 256, 'waste': 0}),
('remaining space exactly at the waste limit',
([56, 56, 24, 8], 0, 4096, 128, 16, 8),
{'addrs': [0, 56, 128, 152], 'limit': 16, 'top': 256, 'waste': 16}),
('repeated slow paths raise the limit',
([64, 40, 40, 40, 40, 40, 8], 0, 4096, 128, 16, 4),
{'addrs': [0, 64, 128, 168, 208, 248, 288], 'limit': 24, 'top': 336, 'waste': 24}),
('request of exactly half a buffer and just above',
([64, 8, 72, 8], 0, 4096, 128, 8, 8),
{'addrs': [0, 64, 128, 72], 'limit': 8, 'top': 200, 'waste': 0}),
('eden filled exactly',
([64, 64, 64, 64, 8], 0, 256, 128, 8, 8),
{'addrs': [0, 64, 128, 192, None], 'limit': 8, 'top': 256, 'waste': 0}),
('eden refill that would overrun',
([64, 64, 8], 0, 200, 128, 8, 8),
{'addrs': [0, 64, None], 'limit': 8, 'top': 128, 'waste': 0})],
[('regression: refill, slow path and adaptation',
([40, 40, 40, 16, 24, 8, 48, 64], 0, 2048, 128, 16, 8),
{'addrs': [0, 40, 80, 128, 144, 168, 176, 256], 'limit': 24, 'top': 320, 'waste': 8}),
('allocation exactly filling the buffer',
([64, 56, 8, 8], 0, 4096, 128, 18, 8),
{'addrs': [0, 64, 120, 128], 'limit': 18, 'top': 256, 'waste': 0}),
('unaligned requests near the buffer end',
([60, 57, 1], 0, 4096, 128, 16, 8),
{'addrs': [0, 64, 128], 'limit': 16, 'top': 256, 'waste': 0}),
('remaining space exactly at the waste limit',
([56, 56, 24, 16], 0, 4096, 128, 16, 8),
{'addrs': [0, 56, 128, 152], 'limit': 16, 'top': 256, 'waste': 16}),
('repeated slow paths raise the limit',
([64, 40, 40, 40, 40, 40, 16], 0, 4096, 128, 16, 4),
{'addrs': [0, 64, 128, 168, 208, 248, 288], 'limit': 24, 'top': 336, 'waste': 24}),
('request of exactly half a buffer and just above',
([64, 8, 72, 16], 0, 4096, 128, 8, 8),
{'addrs': [0, 64, 128, 72], 'limit': 8, 'top': 200, 'waste': 0}),
('eden filled exactly',
([64, 64, 64, 64, 16], 0, 256, 128, 8, 8),
{'addrs': [0, 64, 128, 192, None], 'limit': 8, 'top': 256, 'waste': 0}),
('eden refill that would overrun',
([64, 64, 16], 0, 200, 128, 8, 8),
{'addrs': [0, 64, None], 'limit': 8, 'top': 128, 'waste': 0})],
[('regression: refill, slow path and adaptation',
([40, 40, 40, 16, 24, 8, 48, 64], 0, 2048, 128, 16, 8),
{'addrs': [0, 40, 80, 128, 144, 168, 176, 256], 'limit': 24, 'top': 320, 'waste': 8}),
('allocation exactly filling the buffer',
([64, 56, 8, 8], 0, 4096, 128, 19, 8),
{'addrs': [0, 64, 120, 128], 'limit': 19, 'top': 256, 'waste': 0}),
('unaligned requests near the buffer end',
([60, 57, 1], 0, 4096, 128, 16, 8),
{'addrs': [0, 64, 128], 'limit': 16, 'top': 256, 'waste': 0}),
('remaining space exactly at the waste limit',
([56, 56, 24, 24], 0, 4096, 128, 16, 8),
{'addrs': [0, 56, 128, 152], 'limit': 16, 'top': 256, 'waste': 16}),
('repeated slow paths raise the limit',
([64, 40, 40, 40, 40, 40, 24], 0, 4096, 128, 16, 4),
{'addrs': [0, 64, 128, 168, 208, 248, 288], 'limit': 24, 'top': 336, 'waste': 24}),
('request of exactly half a buffer and just above',
([64, 8, 72, 24], 0, 4096, 128, 8, 8),
{'addrs': [0, 64, 128, 72], 'limit': 8, 'top': 200, 'waste': 0}),
('eden filled exactly',
([64, 64, 64, 64, 24], 0, 256, 128, 8, 8),
{'addrs': [0, 64, 128, 192, None], 'limit': 8, 'top': 256, 'waste': 0}),
('eden refill that would overrun',
([64, 64, 24], 0, 200, 128, 8, 8),
{'addrs': [0, 64, None], 'limit': 8, 'top': 128, 'waste': 0})],
[('regression: refill, slow path and adaptation',
([40, 40, 40, 16, 24, 8, 48, 64], 0, 2048, 128, 16, 8),
{'addrs': [0, 40, 80, 128, 144, 168, 176, 256], 'limit': 24, 'top': 320, 'waste': 8}),
('allocation exactly filling the buffer',
([64, 56, 8, 8], 0, 4096, 128, 20, 8),
{'addrs': [0, 64, 120, 128], 'limit': 20, 'top': 256, 'waste': 0}),
('unaligned requests near the buffer end',
([60, 57, 1], 0, 4096, 128, 16, 8),
{'addrs': [0, 64, 128], 'limit': 16, 'top': 256, 'waste': 0}),
('remaining space exactly at the waste limit',
([56, 56, 24, 32], 0, 4096, 128, 16, 8),
{'addrs': [0, 56, 128, 152], 'limit': 16, 'top': 256, 'waste': 16}),
('repeated slow paths raise the limit',
([64, 40, 40, 40, 40, 40, 32], 0, 4096, 128, 16, 4),
{'addrs': [0, 64, 128, 168, 208, 248, 288], 'limit': 24, 'top': 336, 'waste': 24}),
('request of exactly half a buffer and just above',
([64, 8, 72, 32], 0, 4096, 128, 8, 8),
{'addrs': [0, 64, 128, 72], 'limit': 8, 'top': 200, 'waste': 0}),
('eden filled exactly',
([64, 64, 64, 64, 32], 0, 256, 128, 8, 8),
{'addrs': [0, 64, 128, 192, None], 'limit': 8, 'top': 256, 'waste': 0}),
('eden refill that would overrun',
([64, 64, 32], 0, 200, 128, 8, 8),
{'addrs': [0, 64, None], 'limit': 8, 'top': 128, 'waste': 0})],
[('regression: refill, slow path and adaptation',
([40, 40, 40, 16, 24, 8, 48, 64], 0, 2048, 128, 16, 8),
{'addrs': [0, 40, 80, 128, 144, 168, 176, 256], 'limit': 24, 'top': 320, 'waste': 8}),
('allocation exactly filling the buffer',
([64, 56, 8, 8], 0, 4096, 128, 21, 8),
{'addrs': [0, 64, 120, 128], 'limit': 21, 'top': 256, 'waste': 0}),
('unaligned requests near the buffer end',
([60, 57, 1], 0, 4096, 128, 16, 8),
{'addrs': [0, 64, 128], 'limit': 16, 'top': 256, 'waste': 0}),
('remaining space exactly at the waste limit',
([56, 56, 24, 40], 0, 4096, 128, 16, 8),
{'addrs': [0, 56, 128, 152], 'limit': 16, 'top': 256, 'waste': 16}),
('repeated slow paths raise the limit',
([64, 40, 40, 40, 40, 40, 40], 0, 4096, 128, 16, 4),
{'addrs': [0, 64, 128, 168, 208, 248, 288], 'limit': 24, 'top': 336, 'waste': 24}),
('request of exactly half a buffer and just above',
([64, 8, 72, 40], 0, 4096, 128, 8, 8),
{'addrs': [0, 64, 128, 72], 'limit': 8, 'top': 200, 'waste': 0}),
('eden filled exactly',
([64, 64, 64, 64, 40], 0, 256, 128, 8, 8),
{'addrs': [0, 64, 128, 192, None], 'limit': 8, 'top': 256, 'waste': 0}),
('eden refill that would overrun',
([64, 64, 40], 0, 200, 128, 8, 8),
{'addrs': [0, 64, None], 'limit': 8, 'top': 128, 'waste': 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 fixture | Actual | Expected | Outcome |
|---|---|---|---|
| regression: refill, slow path and adaptation | {'addrs': [0, 40, 80, 128, 144, 168, 176, 256], 'limit': 24, 'top': 320, 'waste': 8} | {'addrs': [0, 40, 80, 128, 144, 168, 176, 256], 'limit': 24, 'top': 320, 'waste': 8} | Passed |
| allocation exactly filling the buffer | {'addrs': [0, 64, 120, 128], 'limit': 17, 'top': 256, 'waste': 0} | {'addrs': [0, 64, 120, 128], 'limit': 17, 'top': 256, 'waste': 0} | Passed |
| unaligned requests near the buffer end | {'addrs': [0, 64, 128], 'limit': 16, 'top': 256, 'waste': 0} | {'addrs': [0, 64, 128], 'limit': 16, 'top': 256, 'waste': 0} | Passed |
| remaining space exactly at the waste limit | {'addrs': [0, 56, 128, 152], 'limit': 16, 'top': 256, 'waste': 16} | {'addrs': [0, 56, 128, 152], 'limit': 16, 'top': 256, 'waste': 16} | Passed |
| repeated slow paths raise the limit | {'addrs': [0, 64, 128, 168, 208, 248, 104], 'limit': 20, 'top': 288, 'waste': 0} | {'addrs': [0, 64, 128, 168, 208, 248, 288], 'limit': 24, 'top': 336, 'waste': 24} | Failed |
| request of exactly half a buffer and just above | {'addrs': [0, 64, 128, 72], 'limit': 8, 'top': 200, 'waste': 0} | {'addrs': [0, 64, 128, 72], 'limit': 8, 'top': 200, 'waste': 0} | Passed |
| eden filled exactly | {'addrs': [0, 64, 128, 192, None], 'limit': 8, 'top': 256, 'waste': 0} | {'addrs': [0, 64, 128, 192, None], 'limit': 8, 'top': 256, 'waste': 0} | Passed |
| eden refill that would overrun | {'addrs': [0, 64, None], 'limit': 8, 'top': 128, 'waste': 0} | {'addrs': [0, 64, None], 'limit': 8, 'top': 128, 'waste': 0} | Passed |
SHA-256 / 7965806849fb5e20be0c2cd7a756399bb07f165c0feb334a6d896a2359a9b1bc
3 / The verified repair
Exit 0"""Failure Map reference implementation. Python standard library only."""
import json
N = 1
observations = []
def solve(reqs, eden_start, eden_end, tlab_size, waste_limit, waste_inc):
top = eden_start
tlab_end = 0
cur = 0
limit = waste_limit
waste = 0
out = []
def eden_alloc(n):
nonlocal top
if top + n > eden_end:
return None
a = top
top += n
return a
for r in reqs:
n = (r + 7) // 8 * 8
if n > tlab_size // 2:
out.append(eden_alloc(n))
continue
if cur + n <= tlab_end:
out.append(cur)
cur += n
continue
remaining = tlab_end - cur
if remaining > limit:
limit += waste_inc
out.append(eden_alloc(n))
continue
start = eden_alloc(tlab_size)
if start is None:
out.append(None)
continue
waste += remaining
tlab_end = start + tlab_size
cur = start + n
out.append(start)
return {'addrs': out, 'waste': waste, 'top': top, 'limit': limit}
def check(label, actual, expected):
observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = [[('regression: refill, slow path and adaptation',
([40, 40, 40, 16, 24, 8, 48, 64], 0, 2048, 128, 16, 8),
{'addrs': [0, 40, 80, 128, 144, 168, 176, 256], 'limit': 24, 'top': 320, 'waste': 8}),
('allocation exactly filling the buffer',
([64, 56, 8, 8], 0, 4096, 128, 17, 8),
{'addrs': [0, 64, 120, 128], 'limit': 17, 'top': 256, 'waste': 0}),
('unaligned requests near the buffer end',
([60, 57, 1], 0, 4096, 128, 16, 8),
{'addrs': [0, 64, 128], 'limit': 16, 'top': 256, 'waste': 0}),
('remaining space exactly at the waste limit',
([56, 56, 24, 8], 0, 4096, 128, 16, 8),
{'addrs': [0, 56, 128, 152], 'limit': 16, 'top': 256, 'waste': 16}),
('repeated slow paths raise the limit',
([64, 40, 40, 40, 40, 40, 8], 0, 4096, 128, 16, 4),
{'addrs': [0, 64, 128, 168, 208, 248, 288], 'limit': 24, 'top': 336, 'waste': 24}),
('request of exactly half a buffer and just above',
([64, 8, 72, 8], 0, 4096, 128, 8, 8),
{'addrs': [0, 64, 128, 72], 'limit': 8, 'top': 200, 'waste': 0}),
('eden filled exactly',
([64, 64, 64, 64, 8], 0, 256, 128, 8, 8),
{'addrs': [0, 64, 128, 192, None], 'limit': 8, 'top': 256, 'waste': 0}),
('eden refill that would overrun',
([64, 64, 8], 0, 200, 128, 8, 8),
{'addrs': [0, 64, None], 'limit': 8, 'top': 128, 'waste': 0})],
[('regression: refill, slow path and adaptation',
([40, 40, 40, 16, 24, 8, 48, 64], 0, 2048, 128, 16, 8),
{'addrs': [0, 40, 80, 128, 144, 168, 176, 256], 'limit': 24, 'top': 320, 'waste': 8}),
('allocation exactly filling the buffer',
([64, 56, 8, 8], 0, 4096, 128, 18, 8),
{'addrs': [0, 64, 120, 128], 'limit': 18, 'top': 256, 'waste': 0}),
('unaligned requests near the buffer end',
([60, 57, 1], 0, 4096, 128, 16, 8),
{'addrs': [0, 64, 128], 'limit': 16, 'top': 256, 'waste': 0}),
('remaining space exactly at the waste limit',
([56, 56, 24, 16], 0, 4096, 128, 16, 8),
{'addrs': [0, 56, 128, 152], 'limit': 16, 'top': 256, 'waste': 16}),
('repeated slow paths raise the limit',
([64, 40, 40, 40, 40, 40, 16], 0, 4096, 128, 16, 4),
{'addrs': [0, 64, 128, 168, 208, 248, 288], 'limit': 24, 'top': 336, 'waste': 24}),
('request of exactly half a buffer and just above',
([64, 8, 72, 16], 0, 4096, 128, 8, 8),
{'addrs': [0, 64, 128, 72], 'limit': 8, 'top': 200, 'waste': 0}),
('eden filled exactly',
([64, 64, 64, 64, 16], 0, 256, 128, 8, 8),
{'addrs': [0, 64, 128, 192, None], 'limit': 8, 'top': 256, 'waste': 0}),
('eden refill that would overrun',
([64, 64, 16], 0, 200, 128, 8, 8),
{'addrs': [0, 64, None], 'limit': 8, 'top': 128, 'waste': 0})],
[('regression: refill, slow path and adaptation',
([40, 40, 40, 16, 24, 8, 48, 64], 0, 2048, 128, 16, 8),
{'addrs': [0, 40, 80, 128, 144, 168, 176, 256], 'limit': 24, 'top': 320, 'waste': 8}),
('allocation exactly filling the buffer',
([64, 56, 8, 8], 0, 4096, 128, 19, 8),
{'addrs': [0, 64, 120, 128], 'limit': 19, 'top': 256, 'waste': 0}),
('unaligned requests near the buffer end',
([60, 57, 1], 0, 4096, 128, 16, 8),
{'addrs': [0, 64, 128], 'limit': 16, 'top': 256, 'waste': 0}),
('remaining space exactly at the waste limit',
([56, 56, 24, 24], 0, 4096, 128, 16, 8),
{'addrs': [0, 56, 128, 152], 'limit': 16, 'top': 256, 'waste': 16}),
('repeated slow paths raise the limit',
([64, 40, 40, 40, 40, 40, 24], 0, 4096, 128, 16, 4),
{'addrs': [0, 64, 128, 168, 208, 248, 288], 'limit': 24, 'top': 336, 'waste': 24}),
('request of exactly half a buffer and just above',
([64, 8, 72, 24], 0, 4096, 128, 8, 8),
{'addrs': [0, 64, 128, 72], 'limit': 8, 'top': 200, 'waste': 0}),
('eden filled exactly',
([64, 64, 64, 64, 24], 0, 256, 128, 8, 8),
{'addrs': [0, 64, 128, 192, None], 'limit': 8, 'top': 256, 'waste': 0}),
('eden refill that would overrun',
([64, 64, 24], 0, 200, 128, 8, 8),
{'addrs': [0, 64, None], 'limit': 8, 'top': 128, 'waste': 0})],
[('regression: refill, slow path and adaptation',
([40, 40, 40, 16, 24, 8, 48, 64], 0, 2048, 128, 16, 8),
{'addrs': [0, 40, 80, 128, 144, 168, 176, 256], 'limit': 24, 'top': 320, 'waste': 8}),
('allocation exactly filling the buffer',
([64, 56, 8, 8], 0, 4096, 128, 20, 8),
{'addrs': [0, 64, 120, 128], 'limit': 20, 'top': 256, 'waste': 0}),
('unaligned requests near the buffer end',
([60, 57, 1], 0, 4096, 128, 16, 8),
{'addrs': [0, 64, 128], 'limit': 16, 'top': 256, 'waste': 0}),
('remaining space exactly at the waste limit',
([56, 56, 24, 32], 0, 4096, 128, 16, 8),
{'addrs': [0, 56, 128, 152], 'limit': 16, 'top': 256, 'waste': 16}),
('repeated slow paths raise the limit',
([64, 40, 40, 40, 40, 40, 32], 0, 4096, 128, 16, 4),
{'addrs': [0, 64, 128, 168, 208, 248, 288], 'limit': 24, 'top': 336, 'waste': 24}),
('request of exactly half a buffer and just above',
([64, 8, 72, 32], 0, 4096, 128, 8, 8),
{'addrs': [0, 64, 128, 72], 'limit': 8, 'top': 200, 'waste': 0}),
('eden filled exactly',
([64, 64, 64, 64, 32], 0, 256, 128, 8, 8),
{'addrs': [0, 64, 128, 192, None], 'limit': 8, 'top': 256, 'waste': 0}),
('eden refill that would overrun',
([64, 64, 32], 0, 200, 128, 8, 8),
{'addrs': [0, 64, None], 'limit': 8, 'top': 128, 'waste': 0})],
[('regression: refill, slow path and adaptation',
([40, 40, 40, 16, 24, 8, 48, 64], 0, 2048, 128, 16, 8),
{'addrs': [0, 40, 80, 128, 144, 168, 176, 256], 'limit': 24, 'top': 320, 'waste': 8}),
('allocation exactly filling the buffer',
([64, 56, 8, 8], 0, 4096, 128, 21, 8),
{'addrs': [0, 64, 120, 128], 'limit': 21, 'top': 256, 'waste': 0}),
('unaligned requests near the buffer end',
([60, 57, 1], 0, 4096, 128, 16, 8),
{'addrs': [0, 64, 128], 'limit': 16, 'top': 256, 'waste': 0}),
('remaining space exactly at the waste limit',
([56, 56, 24, 40], 0, 4096, 128, 16, 8),
{'addrs': [0, 56, 128, 152], 'limit': 16, 'top': 256, 'waste': 16}),
('repeated slow paths raise the limit',
([64, 40, 40, 40, 40, 40, 40], 0, 4096, 128, 16, 4),
{'addrs': [0, 64, 128, 168, 208, 248, 288], 'limit': 24, 'top': 336, 'waste': 24}),
('request of exactly half a buffer and just above',
([64, 8, 72, 40], 0, 4096, 128, 8, 8),
{'addrs': [0, 64, 128, 72], 'limit': 8, 'top': 200, 'waste': 0}),
('eden filled exactly',
([64, 64, 64, 64, 40], 0, 256, 128, 8, 8),
{'addrs': [0, 64, 128, 192, None], 'limit': 8, 'top': 256, 'waste': 0}),
('eden refill that would overrun',
([64, 64, 40], 0, 200, 128, 8, 8),
{'addrs': [0, 64, None], 'limit': 8, 'top': 128, 'waste': 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 fixture | Actual | Expected | Outcome |
|---|---|---|---|
| regression: refill, slow path and adaptation | {'addrs': [0, 40, 80, 128, 144, 168, 176, 256], 'limit': 24, 'top': 320, 'waste': 8} | {'addrs': [0, 40, 80, 128, 144, 168, 176, 256], 'limit': 24, 'top': 320, 'waste': 8} | Passed |
| allocation exactly filling the buffer | {'addrs': [0, 64, 120, 128], 'limit': 17, 'top': 256, 'waste': 0} | {'addrs': [0, 64, 120, 128], 'limit': 17, 'top': 256, 'waste': 0} | Passed |
| unaligned requests near the buffer end | {'addrs': [0, 64, 128], 'limit': 16, 'top': 256, 'waste': 0} | {'addrs': [0, 64, 128], 'limit': 16, 'top': 256, 'waste': 0} | Passed |
| remaining space exactly at the waste limit | {'addrs': [0, 56, 128, 152], 'limit': 16, 'top': 256, 'waste': 16} | {'addrs': [0, 56, 128, 152], 'limit': 16, 'top': 256, 'waste': 16} | Passed |
| repeated slow paths raise the limit | {'addrs': [0, 64, 128, 168, 208, 248, 288], 'limit': 24, 'top': 336, 'waste': 24} | {'addrs': [0, 64, 128, 168, 208, 248, 288], 'limit': 24, 'top': 336, 'waste': 24} | Passed |
| request of exactly half a buffer and just above | {'addrs': [0, 64, 128, 72], 'limit': 8, 'top': 200, 'waste': 0} | {'addrs': [0, 64, 128, 72], 'limit': 8, 'top': 200, 'waste': 0} | Passed |
| eden filled exactly | {'addrs': [0, 64, 128, 192, None], 'limit': 8, 'top': 256, 'waste': 0} | {'addrs': [0, 64, 128, 192, None], 'limit': 8, 'top': 256, 'waste': 0} | Passed |
| eden refill that would overrun | {'addrs': [0, 64, None], 'limit': 8, 'top': 128, 'waste': 0} | {'addrs': [0, 64, None], 'limit': 8, 'top': 128, 'waste': 0} | Passed |
SHA-256 / 4ab965eec17e97897a8432f4ef495b22de3ff271451efe598bc4d8d19ba0c992
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:29.738026+00:00.
Case digest / c35f5ec2a8cb3d3ac336d7b27390f0997fcdcd49d46cd19b0e8908cefa23f1ea