FAILURE MAP
← Case archive

FA-90756 / Garbage collector invariants / Open access

TLAB: nearly empty buffers kept and nearly full ones discarded · case 01

Buffers with plenty of free space are retired while almost-full ones force slow-path allocations.

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

ROOT CAUSE

The refill waste comparison is inverted.

VERIFIED REPAIR

Keep the TLAB (and use eden) only when its remaining space exceeds the waste limit.

Unsuccessful approach: Keeping the TLAB when the remainder equals the limit is off by one.

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 fixtureActualExpectedOutcome
regression: refill, slow path and adaptation{'addrs': [0, 40, 80, 120, 136, 160, 168, 216], 'limit': 80, 'top': 280, 'waste': 0}{'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': 49, 'top': 136, 'waste': 0}{'addrs': [0, 64, 120, 128], 'limit': 17, 'top': 256, 'waste': 0}Failed
unaligned requests near the buffer end{'addrs': [0, 64, 128], 'limit': 40, 'top': 136, 'waste': 0}{'addrs': [0, 64, 128], 'limit': 16, 'top': 256, 'waste': 0}Failed
remaining space exactly at the waste limit{'addrs': [0, 56, 112, 136], 'limit': 48, 'top': 144, 'waste': 0}{'addrs': [0, 56, 128, 152], 'limit': 16, 'top': 256, 'waste': 16}Failed
repeated slow paths raise the limit{'addrs': [0, 64, 104, 144, 184, 224, 264], 'limit': 44, 'top': 272, '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, 72, 144], 'limit': 32, 'top': 152, 'waste': 0}{'addrs': [0, 64, 128, 72], 'limit': 8, 'top': 200, 'waste': 0}Failed
eden filled exactly{'addrs': [0, 64, 128, 192, None], 'limit': 48, 'top': 256, 'waste': 0}{'addrs': [0, 64, 128, 192, None], 'limit': 8, 'top': 256, 'waste': 0}Failed
eden refill that would overrun{'addrs': [0, 64, 128], 'limit': 32, 'top': 136, 'waste': 0}{'addrs': [0, 64, None], 'limit': 8, 'top': 128, 'waste': 0}Failed

SHA-256 / 76d773af4e34665b65d2c6a7091ddd72847bb34dac2bfbc54e05feab7974cefa

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_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 fixtureActualExpectedOutcome
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, 112], 'limit': 24, 'top': 152, 'waste': 0}{'addrs': [0, 56, 128, 152], 'limit': 16, 'top': 256, 'waste': 16}Failed
repeated slow paths raise the limit{'addrs': [0, 64, 128, 168, 208, 248, 288], 'limit': 28, 'top': 376, 'waste': 24}{'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 / 9d0022f0e125e82186a4284ef82b78a37f052fc2c04008ca5430bc91d9dfe939

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 fixtureActualExpectedOutcome
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.694688+00:00.

Case digest / 5997896ff58699512fd1612772eec7575770fd2b62418f23edb0da0dc627aec0