FAILURE MAP
← Case archive

FA-52696 / Raster memory layout / Open access

Small Mip Tail Packing: Large mip allocation truncates or caps page count · case 01

The returned physical layout descriptor disagrees with the declared buffer mapping at large_pages.

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

ROOT CAUSE

Large mip allocation truncates or caps page count The faulty expression is [s//64 for s in p["sizes"][:tail_first]].

VERIFIED REPAIR

Apply the stipulated layout rule at large_pages: [(s+63)//64 for s in p["sizes"][:tail_first]].

Unsuccessful approach: The attempted repair uses [1 for s in p["sizes"][:tail_first]] and still violates the layout contract.

Case contract

Mip levels below a threshold share one fixed-size tail page. Larger levels each own whole pages. Tail levels are packed in reverse level order, each with a two-byte tag; tail capacity is caller-provided and sufficient. Return the named intermediate layout descriptor and final address fields; all quantities are integer byte offsets unless explicitly stated.

Why this case matters

Offline raster resource, upload, readback, and storage-layout regression model.

1 / The failure

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

N = 1
observations = []
def solve(p):
    p = dict(p)
    tail_first = next(i for i,s in enumerate(p["sizes"]) if s<p["threshold"])
    large_pages = [s//64 for s in p["sizes"][:tail_first]]
    tail_levels = list(range(len(p["sizes"])-1,tail_first-1,-1))
    tail_origin = p["base"]+sum(large_pages)*64
    tail_spans = [p["sizes"][i]+2 for i in tail_levels]
    tail_map = {level:tail_origin+sum(tail_spans[:j])+2 for j,level in enumerate(tail_levels)}
    large_map = {i:p["base"]+sum(large_pages[:i])*64 for i in range(tail_first)}
    selected = dict(large_map,**{}).get(p["level"],tail_map.get(p["level"],-1))
    tail_used = sum(tail_spans)
    allocation_end = tail_origin+p["tail_capacity"]
    return {'tail_first': tail_first, 'large_pages': large_pages, 'tail_levels': tail_levels, 'tail_origin': tail_origin, 'tail_spans': tail_spans, 'tail_map': tail_map, 'large_map': large_map, 'selected': selected, 'tail_used': tail_used, 'allocation_end': allocation_end}
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = {1: [({'sizes': [121, 61, 17, 5, 1], 'threshold': 32, 'page': 64, 'level': 0, 'base': 7, 'tail_capacity': 128}, {'tail_first': 2, 'large_pages': [2, 1], 'tail_levels': [4, 3, 2], 'tail_origin': 199, 'tail_spans': [3, 7, 19], 'tail_map': {4: 201, 3: 204, 2: 211}, 'large_map': {0: 7, 1: 135}, 'selected': 7, 'tail_used': 29, 'allocation_end': 327}), ({'sizes': [122, 62, 18, 6, 1], 'threshold': 32, 'page': 64, 'level': 1, 'base': 7, 'tail_capacity': 128}, {'tail_first': 2, 'large_pages': [2, 1], 'tail_levels': [4, 3, 2], 'tail_origin': 199, 'tail_spans': [3, 8, 20], 'tail_map': {4: 201, 3: 204, 2: 212}, 'large_map': {0: 7, 1: 135}, 'selected': 135, 'tail_used': 31, 'allocation_end': 327}), ({'sizes': [123, 63, 19, 7, 1], 'threshold': 32, 'page': 64, 'level': 2, 'base': 7, 'tail_capacity': 128}, {'tail_first': 2, 'large_pages': [2, 1], 'tail_levels': [4, 3, 2], 'tail_origin': 199, 'tail_spans': [3, 9, 21], 'tail_map': {4: 201, 3: 204, 2: 213}, 'large_map': {0: 7, 1: 135}, 'selected': 213, 'tail_used': 33, 'allocation_end': 327}), ({'sizes': [124, 64, 20, 8, 1], 'threshold': 32, 'page': 64, 'level': 3, 'base': 7, 'tail_capacity': 128}, {'tail_first': 2, 'large_pages': [2, 1], 'tail_levels': [4, 3, 2], 'tail_origin': 199, 'tail_spans': [3, 10, 22], 'tail_map': {4: 201, 3: 204, 2: 214}, 'large_map': {0: 7, 1: 135}, 'selected': 204, 'tail_used': 35, 'allocation_end': 327}), ({'sizes': [125, 65, 21, 9, 1], 'threshold': 32, 'page': 64, 'level': 4, 'base': 7, 'tail_capacity': 128}, {'tail_first': 2, 'large_pages': [2, 2], 'tail_levels': [4, 3, 2], 'tail_origin': 263, 'tail_spans': [3, 11, 23], 'tail_map': {4: 265, 3: 268, 2: 279}, 'large_map': {0: 7, 1: 135}, 'selected': 265, 'tail_used': 37, 'allocation_end': 391}), ({'sizes': [126, 66, 22, 10, 1], 'threshold': 32, 'page': 64, 'level': 0, 'base': 7, 'tail_capacity': 128}, {'tail_first': 2, 'large_pages': [2, 2], 'tail_levels': [4, 3, 2], 'tail_origin': 263, 'tail_spans': [3, 12, 24], 'tail_map': {4: 265, 3: 268, 2: 280}, 'large_map': {0: 7, 1: 135}, 'selected': 7, 'tail_used': 39, 'allocation_end': 391})], 2: [({'sizes': [122, 61, 17, 5, 1], 'threshold': 32, 'page': 64, 'level': 0, 'base': 14, 'tail_capacity': 128}, {'tail_first': 2, 'large_pages': [2, 1], 'tail_levels': [4, 3, 2], 'tail_origin': 206, 'tail_spans': [3, 7, 19], 'tail_map': {4: 208, 3: 211, 2: 218}, 'large_map': {0: 14, 1: 142}, 'selected': 14, 'tail_used': 29, 'allocation_end': 334}), ({'sizes': [123, 62, 18, 6, 1], 'threshold': 32, 'page': 64, 'level': 1, 'base': 14, 'tail_capacity': 128}, {'tail_first': 2, 'large_pages': [2, 1], 'tail_levels': [4, 3, 2], 'tail_origin': 206, 'tail_spans': [3, 8, 20], 'tail_map': {4: 208, 3: 211, 2: 219}, 'large_map': {0: 14, 1: 142}, 'selected': 142, 'tail_used': 31, 'allocation_end': 334}), ({'sizes': [124, 63, 19, 7, 1], 'threshold': 32, 'page': 64, 'level': 2, 'base': 14, 'tail_capacity': 128}, {'tail_first': 2, 'large_pages': [2, 1], 'tail_levels': [4, 3, 2], 'tail_origin': 206, 'tail_spans': [3, 9, 21], 'tail_map': {4: 208, 3: 211, 2: 220}, 'large_map': {0: 14, 1: 142}, 'selected': 220, 'tail_used': 33, 'allocation_end': 334}), ({'sizes': [125, 64, 20, 8, 1], 'threshold': 32, 'page': 64, 'level': 3, 'base': 14, 'tail_capacity': 128}, {'tail_first': 2, 'large_pages': [2, 1], 'tail_levels': [4, 3, 2], 'tail_origin': 206, 'tail_spans': [3, 10, 22], 'tail_map': {4: 208, 3: 211, 2: 221}, 'large_map': {0: 14, 1: 142}, 'selected': 211, 'tail_used': 35, 'allocation_end': 334}), ({'sizes': [126, 65, 21, 9, 1], 'threshold': 32, 'page': 64, 'level': 4, 'base': 14, 'tail_capacity': 128}, {'tail_first': 2, 'large_pages': [2, 2], 'tail_levels': [4, 3, 2], 'tail_origin': 270, 'tail_spans': [3, 11, 23], 'tail_map': {4: 272, 3: 275, 2: 286}, 'large_map': {0: 14, 1: 142}, 'selected': 272, 'tail_used': 37, 'allocation_end': 398}), ({'sizes': [127, 66, 22, 10, 1], 'threshold': 32, 'page': 64, 'level': 0, 'base': 14, 'tail_capacity': 128}, {'tail_first': 2, 'large_pages': [2, 2], 'tail_levels': [4, 3, 2], 'tail_origin': 270, 'tail_spans': [3, 12, 24], 'tail_map': {4: 272, 3: 275, 2: 287}, 'large_map': {0: 14, 1: 142}, 'selected': 14, 'tail_used': 39, 'allocation_end': 398})], 3: [({'sizes': [123, 61, 17, 5, 1], 'threshold': 32, 'page': 64, 'level': 0, 'base': 21, 'tail_capacity': 128}, {'tail_first': 2, 'large_pages': [2, 1], 'tail_levels': [4, 3, 2], 'tail_origin': 213, 'tail_spans': [3, 7, 19], 'tail_map': {4: 215, 3: 218, 2: 225}, 'large_map': {0: 21, 1: 149}, 'selected': 21, 'tail_used': 29, 'allocation_end': 341}), ({'sizes': [124, 62, 18, 6, 1], 'threshold': 32, 'page': 64, 'level': 1, 'base': 21, 'tail_capacity': 128}, {'tail_first': 2, 'large_pages': [2, 1], 'tail_levels': [4, 3, 2], 'tail_origin': 213, 'tail_spans': [3, 8, 20], 'tail_map': {4: 215, 3: 218, 2: 226}, 'large_map': {0: 21, 1: 149}, 'selected': 149, 'tail_used': 31, 'allocation_end': 341}), ({'sizes': [125, 63, 19, 7, 1], 'threshold': 32, 'page': 64, 'level': 2, 'base': 21, 'tail_capacity': 128}, {'tail_first': 2, 'large_pages': [2, 1], 'tail_levels': [4, 3, 2], 'tail_origin': 213, 'tail_spans': [3, 9, 21], 'tail_map': {4: 215, 3: 218, 2: 227}, 'large_map': {0: 21, 1: 149}, 'selected': 227, 'tail_used': 33, 'allocation_end': 341}), ({'sizes': [126, 64, 20, 8, 1], 'threshold': 32, 'page': 64, 'level': 3, 'base': 21, 'tail_capacity': 128}, {'tail_first': 2, 'large_pages': [2, 1], 'tail_levels': [4, 3, 2], 'tail_origin': 213, 'tail_spans': [3, 10, 22], 'tail_map': {4: 215, 3: 218, 2: 228}, 'large_map': {0: 21, 1: 149}, 'selected': 218, 'tail_used': 35, 'allocation_end': 341}), ({'sizes': [127, 65, 21, 9, 1], 'threshold': 32, 'page': 64, 'level': 4, 'base': 21, 'tail_capacity': 128}, {'tail_first': 2, 'large_pages': [2, 2], 'tail_levels': [4, 3, 2], 'tail_origin': 277, 'tail_spans': [3, 11, 23], 'tail_map': {4: 279, 3: 282, 2: 293}, 'large_map': {0: 21, 1: 149}, 'selected': 279, 'tail_used': 37, 'allocation_end': 405}), ({'sizes': [128, 66, 22, 10, 1], 'threshold': 32, 'page': 64, 'level': 0, 'base': 21, 'tail_capacity': 128}, {'tail_first': 2, 'large_pages': [2, 2], 'tail_levels': [4, 3, 2], 'tail_origin': 277, 'tail_spans': [3, 12, 24], 'tail_map': {4: 279, 3: 282, 2: 294}, 'large_map': {0: 21, 1: 149}, 'selected': 21, 'tail_used': 39, 'allocation_end': 405})], 4: [({'sizes': [124, 61, 17, 5, 1], 'threshold': 32, 'page': 64, 'level': 0, 'base': 28, 'tail_capacity': 128}, {'tail_first': 2, 'large_pages': [2, 1], 'tail_levels': [4, 3, 2], 'tail_origin': 220, 'tail_spans': [3, 7, 19], 'tail_map': {4: 222, 3: 225, 2: 232}, 'large_map': {0: 28, 1: 156}, 'selected': 28, 'tail_used': 29, 'allocation_end': 348}), ({'sizes': [125, 62, 18, 6, 1], 'threshold': 32, 'page': 64, 'level': 1, 'base': 28, 'tail_capacity': 128}, {'tail_first': 2, 'large_pages': [2, 1], 'tail_levels': [4, 3, 2], 'tail_origin': 220, 'tail_spans': [3, 8, 20], 'tail_map': {4: 222, 3: 225, 2: 233}, 'large_map': {0: 28, 1: 156}, 'selected': 156, 'tail_used': 31, 'allocation_end': 348}), ({'sizes': [126, 63, 19, 7, 1], 'threshold': 32, 'page': 64, 'level': 2, 'base': 28, 'tail_capacity': 128}, {'tail_first': 2, 'large_pages': [2, 1], 'tail_levels': [4, 3, 2], 'tail_origin': 220, 'tail_spans': [3, 9, 21], 'tail_map': {4: 222, 3: 225, 2: 234}, 'large_map': {0: 28, 1: 156}, 'selected': 234, 'tail_used': 33, 'allocation_end': 348}), ({'sizes': [127, 64, 20, 8, 1], 'threshold': 32, 'page': 64, 'level': 3, 'base': 28, 'tail_capacity': 128}, {'tail_first': 2, 'large_pages': [2, 1], 'tail_levels': [4, 3, 2], 'tail_origin': 220, 'tail_spans': [3, 10, 22], 'tail_map': {4: 222, 3: 225, 2: 235}, 'large_map': {0: 28, 1: 156}, 'selected': 225, 'tail_used': 35, 'allocation_end': 348}), ({'sizes': [128, 65, 21, 9, 1], 'threshold': 32, 'page': 64, 'level': 4, 'base': 28, 'tail_capacity': 128}, {'tail_first': 2, 'large_pages': [2, 2], 'tail_levels': [4, 3, 2], 'tail_origin': 284, 'tail_spans': [3, 11, 23], 'tail_map': {4: 286, 3: 289, 2: 300}, 'large_map': {0: 28, 1: 156}, 'selected': 286, 'tail_used': 37, 'allocation_end': 412}), ({'sizes': [129, 66, 22, 10, 1], 'threshold': 32, 'page': 64, 'level': 0, 'base': 28, 'tail_capacity': 128}, {'tail_first': 2, 'large_pages': [3, 2], 'tail_levels': [4, 3, 2], 'tail_origin': 348, 'tail_spans': [3, 12, 24], 'tail_map': {4: 350, 3: 353, 2: 365}, 'large_map': {0: 28, 1: 220}, 'selected': 28, 'tail_used': 39, 'allocation_end': 476})], 5: [({'sizes': [125, 61, 17, 5, 1], 'threshold': 32, 'page': 64, 'level': 0, 'base': 35, 'tail_capacity': 128}, {'tail_first': 2, 'large_pages': [2, 1], 'tail_levels': [4, 3, 2], 'tail_origin': 227, 'tail_spans': [3, 7, 19], 'tail_map': {4: 229, 3: 232, 2: 239}, 'large_map': {0: 35, 1: 163}, 'selected': 35, 'tail_used': 29, 'allocation_end': 355}), ({'sizes': [126, 62, 18, 6, 1], 'threshold': 32, 'page': 64, 'level': 1, 'base': 35, 'tail_capacity': 128}, {'tail_first': 2, 'large_pages': [2, 1], 'tail_levels': [4, 3, 2], 'tail_origin': 227, 'tail_spans': [3, 8, 20], 'tail_map': {4: 229, 3: 232, 2: 240}, 'large_map': {0: 35, 1: 163}, 'selected': 163, 'tail_used': 31, 'allocation_end': 355}), ({'sizes': [127, 63, 19, 7, 1], 'threshold': 32, 'page': 64, 'level': 2, 'base': 35, 'tail_capacity': 128}, {'tail_first': 2, 'large_pages': [2, 1], 'tail_levels': [4, 3, 2], 'tail_origin': 227, 'tail_spans': [3, 9, 21], 'tail_map': {4: 229, 3: 232, 2: 241}, 'large_map': {0: 35, 1: 163}, 'selected': 241, 'tail_used': 33, 'allocation_end': 355}), ({'sizes': [128, 64, 20, 8, 1], 'threshold': 32, 'page': 64, 'level': 3, 'base': 35, 'tail_capacity': 128}, {'tail_first': 2, 'large_pages': [2, 1], 'tail_levels': [4, 3, 2], 'tail_origin': 227, 'tail_spans': [3, 10, 22], 'tail_map': {4: 229, 3: 232, 2: 242}, 'large_map': {0: 35, 1: 163}, 'selected': 232, 'tail_used': 35, 'allocation_end': 355}), ({'sizes': [129, 65, 21, 9, 1], 'threshold': 32, 'page': 64, 'level': 4, 'base': 35, 'tail_capacity': 128}, {'tail_first': 2, 'large_pages': [3, 2], 'tail_levels': [4, 3, 2], 'tail_origin': 355, 'tail_spans': [3, 11, 23], 'tail_map': {4: 357, 3: 360, 2: 371}, 'large_map': {0: 35, 1: 227}, 'selected': 357, 'tail_used': 37, 'allocation_end': 483}), ({'sizes': [130, 66, 22, 10, 1], 'threshold': 32, 'page': 64, 'level': 0, 'base': 35, 'tail_capacity': 128}, {'tail_first': 2, 'large_pages': [3, 2], 'tail_levels': [4, 3, 2], 'tail_origin': 355, 'tail_spans': [3, 12, 24], 'tail_map': {4: 357, 3: 360, 2: 372}, 'large_map': {0: 35, 1: 227}, 'selected': 35, 'tail_used': 39, 'allocation_end': 483})]}
for i, (p, expected) in enumerate(cases[N]):
    check("layout fixture " + str(i + 1), solve(p), 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
layout fixture 1{'allocation_end': 199, 'large_map': {'0': 7, '1': 71}, 'large_pages': [1, 0], 'selected': 7, 'tail_first': 2, 'tail_levels': [4, 3, 2], 'tail_map': {'2': 83, '3': 76, '4': 73}, 'tail_origin': 71, 'tail_spans': [3, 7, 19], 'tail_used': 29}{'allocation_end': 327, 'large_map': {'0': 7, '1': 135}, 'large_pages': [2, 1], 'selected': 7, 'tail_first': 2, 'tail_levels': [4, 3, 2], 'tail_map': {'2': 211, '3': 204, '4': 201}, 'tail_origin': 199, 'tail_spans': [3, 7, 19], 'tail_used': 29}Failed
layout fixture 2{'allocation_end': 199, 'large_map': {'0': 7, '1': 71}, 'large_pages': [1, 0], 'selected': 71, 'tail_first': 2, 'tail_levels': [4, 3, 2], 'tail_map': {'2': 84, '3': 76, '4': 73}, 'tail_origin': 71, 'tail_spans': [3, 8, 20], 'tail_used': 31}{'allocation_end': 327, 'large_map': {'0': 7, '1': 135}, 'large_pages': [2, 1], 'selected': 135, 'tail_first': 2, 'tail_levels': [4, 3, 2], 'tail_map': {'2': 212, '3': 204, '4': 201}, 'tail_origin': 199, 'tail_spans': [3, 8, 20], 'tail_used': 31}Failed
layout fixture 3{'allocation_end': 199, 'large_map': {'0': 7, '1': 71}, 'large_pages': [1, 0], 'selected': 85, 'tail_first': 2, 'tail_levels': [4, 3, 2], 'tail_map': {'2': 85, '3': 76, '4': 73}, 'tail_origin': 71, 'tail_spans': [3, 9, 21], 'tail_used': 33}{'allocation_end': 327, 'large_map': {'0': 7, '1': 135}, 'large_pages': [2, 1], 'selected': 213, 'tail_first': 2, 'tail_levels': [4, 3, 2], 'tail_map': {'2': 213, '3': 204, '4': 201}, 'tail_origin': 199, 'tail_spans': [3, 9, 21], 'tail_used': 33}Failed
layout fixture 4{'allocation_end': 263, 'large_map': {'0': 7, '1': 71}, 'large_pages': [1, 1], 'selected': 140, 'tail_first': 2, 'tail_levels': [4, 3, 2], 'tail_map': {'2': 150, '3': 140, '4': 137}, 'tail_origin': 135, 'tail_spans': [3, 10, 22], 'tail_used': 35}{'allocation_end': 327, 'large_map': {'0': 7, '1': 135}, 'large_pages': [2, 1], 'selected': 204, 'tail_first': 2, 'tail_levels': [4, 3, 2], 'tail_map': {'2': 214, '3': 204, '4': 201}, 'tail_origin': 199, 'tail_spans': [3, 10, 22], 'tail_used': 35}Failed
layout fixture 5{'allocation_end': 263, 'large_map': {'0': 7, '1': 71}, 'large_pages': [1, 1], 'selected': 137, 'tail_first': 2, 'tail_levels': [4, 3, 2], 'tail_map': {'2': 151, '3': 140, '4': 137}, 'tail_origin': 135, 'tail_spans': [3, 11, 23], 'tail_used': 37}{'allocation_end': 391, 'large_map': {'0': 7, '1': 135}, 'large_pages': [2, 2], 'selected': 265, 'tail_first': 2, 'tail_levels': [4, 3, 2], 'tail_map': {'2': 279, '3': 268, '4': 265}, 'tail_origin': 263, 'tail_spans': [3, 11, 23], 'tail_used': 37}Failed
layout fixture 6{'allocation_end': 263, 'large_map': {'0': 7, '1': 71}, 'large_pages': [1, 1], 'selected': 7, 'tail_first': 2, 'tail_levels': [4, 3, 2], 'tail_map': {'2': 152, '3': 140, '4': 137}, 'tail_origin': 135, 'tail_spans': [3, 12, 24], 'tail_used': 39}{'allocation_end': 391, 'large_map': {'0': 7, '1': 135}, 'large_pages': [2, 2], 'selected': 7, 'tail_first': 2, 'tail_levels': [4, 3, 2], 'tail_map': {'2': 280, '3': 268, '4': 265}, 'tail_origin': 263, 'tail_spans': [3, 12, 24], 'tail_used': 39}Failed

SHA-256 / e09b6f9bf0213cd4fdd6e2e06a801578f593d8680ae5188f1badc8809100cbcf

2 / The unsuccessful fix

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

N = 1
observations = []
def solve(p):
    p = dict(p)
    tail_first = next(i for i,s in enumerate(p["sizes"]) if s<p["threshold"])
    large_pages = [1 for s in p["sizes"][:tail_first]]
    tail_levels = list(range(len(p["sizes"])-1,tail_first-1,-1))
    tail_origin = p["base"]+sum(large_pages)*64
    tail_spans = [p["sizes"][i]+2 for i in tail_levels]
    tail_map = {level:tail_origin+sum(tail_spans[:j])+2 for j,level in enumerate(tail_levels)}
    large_map = {i:p["base"]+sum(large_pages[:i])*64 for i in range(tail_first)}
    selected = dict(large_map,**{}).get(p["level"],tail_map.get(p["level"],-1))
    tail_used = sum(tail_spans)
    allocation_end = tail_origin+p["tail_capacity"]
    return {'tail_first': tail_first, 'large_pages': large_pages, 'tail_levels': tail_levels, 'tail_origin': tail_origin, 'tail_spans': tail_spans, 'tail_map': tail_map, 'large_map': large_map, 'selected': selected, 'tail_used': tail_used, 'allocation_end': allocation_end}
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = {1: [({'sizes': [121, 61, 17, 5, 1], 'threshold': 32, 'page': 64, 'level': 0, 'base': 7, 'tail_capacity': 128}, {'tail_first': 2, 'large_pages': [2, 1], 'tail_levels': [4, 3, 2], 'tail_origin': 199, 'tail_spans': [3, 7, 19], 'tail_map': {4: 201, 3: 204, 2: 211}, 'large_map': {0: 7, 1: 135}, 'selected': 7, 'tail_used': 29, 'allocation_end': 327}), ({'sizes': [122, 62, 18, 6, 1], 'threshold': 32, 'page': 64, 'level': 1, 'base': 7, 'tail_capacity': 128}, {'tail_first': 2, 'large_pages': [2, 1], 'tail_levels': [4, 3, 2], 'tail_origin': 199, 'tail_spans': [3, 8, 20], 'tail_map': {4: 201, 3: 204, 2: 212}, 'large_map': {0: 7, 1: 135}, 'selected': 135, 'tail_used': 31, 'allocation_end': 327}), ({'sizes': [123, 63, 19, 7, 1], 'threshold': 32, 'page': 64, 'level': 2, 'base': 7, 'tail_capacity': 128}, {'tail_first': 2, 'large_pages': [2, 1], 'tail_levels': [4, 3, 2], 'tail_origin': 199, 'tail_spans': [3, 9, 21], 'tail_map': {4: 201, 3: 204, 2: 213}, 'large_map': {0: 7, 1: 135}, 'selected': 213, 'tail_used': 33, 'allocation_end': 327}), ({'sizes': [124, 64, 20, 8, 1], 'threshold': 32, 'page': 64, 'level': 3, 'base': 7, 'tail_capacity': 128}, {'tail_first': 2, 'large_pages': [2, 1], 'tail_levels': [4, 3, 2], 'tail_origin': 199, 'tail_spans': [3, 10, 22], 'tail_map': {4: 201, 3: 204, 2: 214}, 'large_map': {0: 7, 1: 135}, 'selected': 204, 'tail_used': 35, 'allocation_end': 327}), ({'sizes': [125, 65, 21, 9, 1], 'threshold': 32, 'page': 64, 'level': 4, 'base': 7, 'tail_capacity': 128}, {'tail_first': 2, 'large_pages': [2, 2], 'tail_levels': [4, 3, 2], 'tail_origin': 263, 'tail_spans': [3, 11, 23], 'tail_map': {4: 265, 3: 268, 2: 279}, 'large_map': {0: 7, 1: 135}, 'selected': 265, 'tail_used': 37, 'allocation_end': 391}), ({'sizes': [126, 66, 22, 10, 1], 'threshold': 32, 'page': 64, 'level': 0, 'base': 7, 'tail_capacity': 128}, {'tail_first': 2, 'large_pages': [2, 2], 'tail_levels': [4, 3, 2], 'tail_origin': 263, 'tail_spans': [3, 12, 24], 'tail_map': {4: 265, 3: 268, 2: 280}, 'large_map': {0: 7, 1: 135}, 'selected': 7, 'tail_used': 39, 'allocation_end': 391})], 2: [({'sizes': [122, 61, 17, 5, 1], 'threshold': 32, 'page': 64, 'level': 0, 'base': 14, 'tail_capacity': 128}, {'tail_first': 2, 'large_pages': [2, 1], 'tail_levels': [4, 3, 2], 'tail_origin': 206, 'tail_spans': [3, 7, 19], 'tail_map': {4: 208, 3: 211, 2: 218}, 'large_map': {0: 14, 1: 142}, 'selected': 14, 'tail_used': 29, 'allocation_end': 334}), ({'sizes': [123, 62, 18, 6, 1], 'threshold': 32, 'page': 64, 'level': 1, 'base': 14, 'tail_capacity': 128}, {'tail_first': 2, 'large_pages': [2, 1], 'tail_levels': [4, 3, 2], 'tail_origin': 206, 'tail_spans': [3, 8, 20], 'tail_map': {4: 208, 3: 211, 2: 219}, 'large_map': {0: 14, 1: 142}, 'selected': 142, 'tail_used': 31, 'allocation_end': 334}), ({'sizes': [124, 63, 19, 7, 1], 'threshold': 32, 'page': 64, 'level': 2, 'base': 14, 'tail_capacity': 128}, {'tail_first': 2, 'large_pages': [2, 1], 'tail_levels': [4, 3, 2], 'tail_origin': 206, 'tail_spans': [3, 9, 21], 'tail_map': {4: 208, 3: 211, 2: 220}, 'large_map': {0: 14, 1: 142}, 'selected': 220, 'tail_used': 33, 'allocation_end': 334}), ({'sizes': [125, 64, 20, 8, 1], 'threshold': 32, 'page': 64, 'level': 3, 'base': 14, 'tail_capacity': 128}, {'tail_first': 2, 'large_pages': [2, 1], 'tail_levels': [4, 3, 2], 'tail_origin': 206, 'tail_spans': [3, 10, 22], 'tail_map': {4: 208, 3: 211, 2: 221}, 'large_map': {0: 14, 1: 142}, 'selected': 211, 'tail_used': 35, 'allocation_end': 334}), ({'sizes': [126, 65, 21, 9, 1], 'threshold': 32, 'page': 64, 'level': 4, 'base': 14, 'tail_capacity': 128}, {'tail_first': 2, 'large_pages': [2, 2], 'tail_levels': [4, 3, 2], 'tail_origin': 270, 'tail_spans': [3, 11, 23], 'tail_map': {4: 272, 3: 275, 2: 286}, 'large_map': {0: 14, 1: 142}, 'selected': 272, 'tail_used': 37, 'allocation_end': 398}), ({'sizes': [127, 66, 22, 10, 1], 'threshold': 32, 'page': 64, 'level': 0, 'base': 14, 'tail_capacity': 128}, {'tail_first': 2, 'large_pages': [2, 2], 'tail_levels': [4, 3, 2], 'tail_origin': 270, 'tail_spans': [3, 12, 24], 'tail_map': {4: 272, 3: 275, 2: 287}, 'large_map': {0: 14, 1: 142}, 'selected': 14, 'tail_used': 39, 'allocation_end': 398})], 3: [({'sizes': [123, 61, 17, 5, 1], 'threshold': 32, 'page': 64, 'level': 0, 'base': 21, 'tail_capacity': 128}, {'tail_first': 2, 'large_pages': [2, 1], 'tail_levels': [4, 3, 2], 'tail_origin': 213, 'tail_spans': [3, 7, 19], 'tail_map': {4: 215, 3: 218, 2: 225}, 'large_map': {0: 21, 1: 149}, 'selected': 21, 'tail_used': 29, 'allocation_end': 341}), ({'sizes': [124, 62, 18, 6, 1], 'threshold': 32, 'page': 64, 'level': 1, 'base': 21, 'tail_capacity': 128}, {'tail_first': 2, 'large_pages': [2, 1], 'tail_levels': [4, 3, 2], 'tail_origin': 213, 'tail_spans': [3, 8, 20], 'tail_map': {4: 215, 3: 218, 2: 226}, 'large_map': {0: 21, 1: 149}, 'selected': 149, 'tail_used': 31, 'allocation_end': 341}), ({'sizes': [125, 63, 19, 7, 1], 'threshold': 32, 'page': 64, 'level': 2, 'base': 21, 'tail_capacity': 128}, {'tail_first': 2, 'large_pages': [2, 1], 'tail_levels': [4, 3, 2], 'tail_origin': 213, 'tail_spans': [3, 9, 21], 'tail_map': {4: 215, 3: 218, 2: 227}, 'large_map': {0: 21, 1: 149}, 'selected': 227, 'tail_used': 33, 'allocation_end': 341}), ({'sizes': [126, 64, 20, 8, 1], 'threshold': 32, 'page': 64, 'level': 3, 'base': 21, 'tail_capacity': 128}, {'tail_first': 2, 'large_pages': [2, 1], 'tail_levels': [4, 3, 2], 'tail_origin': 213, 'tail_spans': [3, 10, 22], 'tail_map': {4: 215, 3: 218, 2: 228}, 'large_map': {0: 21, 1: 149}, 'selected': 218, 'tail_used': 35, 'allocation_end': 341}), ({'sizes': [127, 65, 21, 9, 1], 'threshold': 32, 'page': 64, 'level': 4, 'base': 21, 'tail_capacity': 128}, {'tail_first': 2, 'large_pages': [2, 2], 'tail_levels': [4, 3, 2], 'tail_origin': 277, 'tail_spans': [3, 11, 23], 'tail_map': {4: 279, 3: 282, 2: 293}, 'large_map': {0: 21, 1: 149}, 'selected': 279, 'tail_used': 37, 'allocation_end': 405}), ({'sizes': [128, 66, 22, 10, 1], 'threshold': 32, 'page': 64, 'level': 0, 'base': 21, 'tail_capacity': 128}, {'tail_first': 2, 'large_pages': [2, 2], 'tail_levels': [4, 3, 2], 'tail_origin': 277, 'tail_spans': [3, 12, 24], 'tail_map': {4: 279, 3: 282, 2: 294}, 'large_map': {0: 21, 1: 149}, 'selected': 21, 'tail_used': 39, 'allocation_end': 405})], 4: [({'sizes': [124, 61, 17, 5, 1], 'threshold': 32, 'page': 64, 'level': 0, 'base': 28, 'tail_capacity': 128}, {'tail_first': 2, 'large_pages': [2, 1], 'tail_levels': [4, 3, 2], 'tail_origin': 220, 'tail_spans': [3, 7, 19], 'tail_map': {4: 222, 3: 225, 2: 232}, 'large_map': {0: 28, 1: 156}, 'selected': 28, 'tail_used': 29, 'allocation_end': 348}), ({'sizes': [125, 62, 18, 6, 1], 'threshold': 32, 'page': 64, 'level': 1, 'base': 28, 'tail_capacity': 128}, {'tail_first': 2, 'large_pages': [2, 1], 'tail_levels': [4, 3, 2], 'tail_origin': 220, 'tail_spans': [3, 8, 20], 'tail_map': {4: 222, 3: 225, 2: 233}, 'large_map': {0: 28, 1: 156}, 'selected': 156, 'tail_used': 31, 'allocation_end': 348}), ({'sizes': [126, 63, 19, 7, 1], 'threshold': 32, 'page': 64, 'level': 2, 'base': 28, 'tail_capacity': 128}, {'tail_first': 2, 'large_pages': [2, 1], 'tail_levels': [4, 3, 2], 'tail_origin': 220, 'tail_spans': [3, 9, 21], 'tail_map': {4: 222, 3: 225, 2: 234}, 'large_map': {0: 28, 1: 156}, 'selected': 234, 'tail_used': 33, 'allocation_end': 348}), ({'sizes': [127, 64, 20, 8, 1], 'threshold': 32, 'page': 64, 'level': 3, 'base': 28, 'tail_capacity': 128}, {'tail_first': 2, 'large_pages': [2, 1], 'tail_levels': [4, 3, 2], 'tail_origin': 220, 'tail_spans': [3, 10, 22], 'tail_map': {4: 222, 3: 225, 2: 235}, 'large_map': {0: 28, 1: 156}, 'selected': 225, 'tail_used': 35, 'allocation_end': 348}), ({'sizes': [128, 65, 21, 9, 1], 'threshold': 32, 'page': 64, 'level': 4, 'base': 28, 'tail_capacity': 128}, {'tail_first': 2, 'large_pages': [2, 2], 'tail_levels': [4, 3, 2], 'tail_origin': 284, 'tail_spans': [3, 11, 23], 'tail_map': {4: 286, 3: 289, 2: 300}, 'large_map': {0: 28, 1: 156}, 'selected': 286, 'tail_used': 37, 'allocation_end': 412}), ({'sizes': [129, 66, 22, 10, 1], 'threshold': 32, 'page': 64, 'level': 0, 'base': 28, 'tail_capacity': 128}, {'tail_first': 2, 'large_pages': [3, 2], 'tail_levels': [4, 3, 2], 'tail_origin': 348, 'tail_spans': [3, 12, 24], 'tail_map': {4: 350, 3: 353, 2: 365}, 'large_map': {0: 28, 1: 220}, 'selected': 28, 'tail_used': 39, 'allocation_end': 476})], 5: [({'sizes': [125, 61, 17, 5, 1], 'threshold': 32, 'page': 64, 'level': 0, 'base': 35, 'tail_capacity': 128}, {'tail_first': 2, 'large_pages': [2, 1], 'tail_levels': [4, 3, 2], 'tail_origin': 227, 'tail_spans': [3, 7, 19], 'tail_map': {4: 229, 3: 232, 2: 239}, 'large_map': {0: 35, 1: 163}, 'selected': 35, 'tail_used': 29, 'allocation_end': 355}), ({'sizes': [126, 62, 18, 6, 1], 'threshold': 32, 'page': 64, 'level': 1, 'base': 35, 'tail_capacity': 128}, {'tail_first': 2, 'large_pages': [2, 1], 'tail_levels': [4, 3, 2], 'tail_origin': 227, 'tail_spans': [3, 8, 20], 'tail_map': {4: 229, 3: 232, 2: 240}, 'large_map': {0: 35, 1: 163}, 'selected': 163, 'tail_used': 31, 'allocation_end': 355}), ({'sizes': [127, 63, 19, 7, 1], 'threshold': 32, 'page': 64, 'level': 2, 'base': 35, 'tail_capacity': 128}, {'tail_first': 2, 'large_pages': [2, 1], 'tail_levels': [4, 3, 2], 'tail_origin': 227, 'tail_spans': [3, 9, 21], 'tail_map': {4: 229, 3: 232, 2: 241}, 'large_map': {0: 35, 1: 163}, 'selected': 241, 'tail_used': 33, 'allocation_end': 355}), ({'sizes': [128, 64, 20, 8, 1], 'threshold': 32, 'page': 64, 'level': 3, 'base': 35, 'tail_capacity': 128}, {'tail_first': 2, 'large_pages': [2, 1], 'tail_levels': [4, 3, 2], 'tail_origin': 227, 'tail_spans': [3, 10, 22], 'tail_map': {4: 229, 3: 232, 2: 242}, 'large_map': {0: 35, 1: 163}, 'selected': 232, 'tail_used': 35, 'allocation_end': 355}), ({'sizes': [129, 65, 21, 9, 1], 'threshold': 32, 'page': 64, 'level': 4, 'base': 35, 'tail_capacity': 128}, {'tail_first': 2, 'large_pages': [3, 2], 'tail_levels': [4, 3, 2], 'tail_origin': 355, 'tail_spans': [3, 11, 23], 'tail_map': {4: 357, 3: 360, 2: 371}, 'large_map': {0: 35, 1: 227}, 'selected': 357, 'tail_used': 37, 'allocation_end': 483}), ({'sizes': [130, 66, 22, 10, 1], 'threshold': 32, 'page': 64, 'level': 0, 'base': 35, 'tail_capacity': 128}, {'tail_first': 2, 'large_pages': [3, 2], 'tail_levels': [4, 3, 2], 'tail_origin': 355, 'tail_spans': [3, 12, 24], 'tail_map': {4: 357, 3: 360, 2: 372}, 'large_map': {0: 35, 1: 227}, 'selected': 35, 'tail_used': 39, 'allocation_end': 483})]}
for i, (p, expected) in enumerate(cases[N]):
    check("layout fixture " + str(i + 1), solve(p), 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
layout fixture 1{'allocation_end': 263, 'large_map': {'0': 7, '1': 71}, 'large_pages': [1, 1], 'selected': 7, 'tail_first': 2, 'tail_levels': [4, 3, 2], 'tail_map': {'2': 147, '3': 140, '4': 137}, 'tail_origin': 135, 'tail_spans': [3, 7, 19], 'tail_used': 29}{'allocation_end': 327, 'large_map': {'0': 7, '1': 135}, 'large_pages': [2, 1], 'selected': 7, 'tail_first': 2, 'tail_levels': [4, 3, 2], 'tail_map': {'2': 211, '3': 204, '4': 201}, 'tail_origin': 199, 'tail_spans': [3, 7, 19], 'tail_used': 29}Failed
layout fixture 2{'allocation_end': 263, 'large_map': {'0': 7, '1': 71}, 'large_pages': [1, 1], 'selected': 71, 'tail_first': 2, 'tail_levels': [4, 3, 2], 'tail_map': {'2': 148, '3': 140, '4': 137}, 'tail_origin': 135, 'tail_spans': [3, 8, 20], 'tail_used': 31}{'allocation_end': 327, 'large_map': {'0': 7, '1': 135}, 'large_pages': [2, 1], 'selected': 135, 'tail_first': 2, 'tail_levels': [4, 3, 2], 'tail_map': {'2': 212, '3': 204, '4': 201}, 'tail_origin': 199, 'tail_spans': [3, 8, 20], 'tail_used': 31}Failed
layout fixture 3{'allocation_end': 263, 'large_map': {'0': 7, '1': 71}, 'large_pages': [1, 1], 'selected': 149, 'tail_first': 2, 'tail_levels': [4, 3, 2], 'tail_map': {'2': 149, '3': 140, '4': 137}, 'tail_origin': 135, 'tail_spans': [3, 9, 21], 'tail_used': 33}{'allocation_end': 327, 'large_map': {'0': 7, '1': 135}, 'large_pages': [2, 1], 'selected': 213, 'tail_first': 2, 'tail_levels': [4, 3, 2], 'tail_map': {'2': 213, '3': 204, '4': 201}, 'tail_origin': 199, 'tail_spans': [3, 9, 21], 'tail_used': 33}Failed
layout fixture 4{'allocation_end': 263, 'large_map': {'0': 7, '1': 71}, 'large_pages': [1, 1], 'selected': 140, 'tail_first': 2, 'tail_levels': [4, 3, 2], 'tail_map': {'2': 150, '3': 140, '4': 137}, 'tail_origin': 135, 'tail_spans': [3, 10, 22], 'tail_used': 35}{'allocation_end': 327, 'large_map': {'0': 7, '1': 135}, 'large_pages': [2, 1], 'selected': 204, 'tail_first': 2, 'tail_levels': [4, 3, 2], 'tail_map': {'2': 214, '3': 204, '4': 201}, 'tail_origin': 199, 'tail_spans': [3, 10, 22], 'tail_used': 35}Failed
layout fixture 5{'allocation_end': 263, 'large_map': {'0': 7, '1': 71}, 'large_pages': [1, 1], 'selected': 137, 'tail_first': 2, 'tail_levels': [4, 3, 2], 'tail_map': {'2': 151, '3': 140, '4': 137}, 'tail_origin': 135, 'tail_spans': [3, 11, 23], 'tail_used': 37}{'allocation_end': 391, 'large_map': {'0': 7, '1': 135}, 'large_pages': [2, 2], 'selected': 265, 'tail_first': 2, 'tail_levels': [4, 3, 2], 'tail_map': {'2': 279, '3': 268, '4': 265}, 'tail_origin': 263, 'tail_spans': [3, 11, 23], 'tail_used': 37}Failed
layout fixture 6{'allocation_end': 263, 'large_map': {'0': 7, '1': 71}, 'large_pages': [1, 1], 'selected': 7, 'tail_first': 2, 'tail_levels': [4, 3, 2], 'tail_map': {'2': 152, '3': 140, '4': 137}, 'tail_origin': 135, 'tail_spans': [3, 12, 24], 'tail_used': 39}{'allocation_end': 391, 'large_map': {'0': 7, '1': 135}, 'large_pages': [2, 2], 'selected': 7, 'tail_first': 2, 'tail_levels': [4, 3, 2], 'tail_map': {'2': 280, '3': 268, '4': 265}, 'tail_origin': 263, 'tail_spans': [3, 12, 24], 'tail_used': 39}Failed

SHA-256 / 9eb5fe3d5658278dc7f884ba56d694af973f04a4d5d6943b33df4300fc2444eb

3 / The verified repair

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

N = 1
observations = []
def solve(p):
    p = dict(p)
    tail_first = next(i for i,s in enumerate(p["sizes"]) if s<p["threshold"])
    large_pages = [(s+63)//64 for s in p["sizes"][:tail_first]]
    tail_levels = list(range(len(p["sizes"])-1,tail_first-1,-1))
    tail_origin = p["base"]+sum(large_pages)*64
    tail_spans = [p["sizes"][i]+2 for i in tail_levels]
    tail_map = {level:tail_origin+sum(tail_spans[:j])+2 for j,level in enumerate(tail_levels)}
    large_map = {i:p["base"]+sum(large_pages[:i])*64 for i in range(tail_first)}
    selected = dict(large_map,**{}).get(p["level"],tail_map.get(p["level"],-1))
    tail_used = sum(tail_spans)
    allocation_end = tail_origin+p["tail_capacity"]
    return {'tail_first': tail_first, 'large_pages': large_pages, 'tail_levels': tail_levels, 'tail_origin': tail_origin, 'tail_spans': tail_spans, 'tail_map': tail_map, 'large_map': large_map, 'selected': selected, 'tail_used': tail_used, 'allocation_end': allocation_end}
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = {1: [({'sizes': [121, 61, 17, 5, 1], 'threshold': 32, 'page': 64, 'level': 0, 'base': 7, 'tail_capacity': 128}, {'tail_first': 2, 'large_pages': [2, 1], 'tail_levels': [4, 3, 2], 'tail_origin': 199, 'tail_spans': [3, 7, 19], 'tail_map': {4: 201, 3: 204, 2: 211}, 'large_map': {0: 7, 1: 135}, 'selected': 7, 'tail_used': 29, 'allocation_end': 327}), ({'sizes': [122, 62, 18, 6, 1], 'threshold': 32, 'page': 64, 'level': 1, 'base': 7, 'tail_capacity': 128}, {'tail_first': 2, 'large_pages': [2, 1], 'tail_levels': [4, 3, 2], 'tail_origin': 199, 'tail_spans': [3, 8, 20], 'tail_map': {4: 201, 3: 204, 2: 212}, 'large_map': {0: 7, 1: 135}, 'selected': 135, 'tail_used': 31, 'allocation_end': 327}), ({'sizes': [123, 63, 19, 7, 1], 'threshold': 32, 'page': 64, 'level': 2, 'base': 7, 'tail_capacity': 128}, {'tail_first': 2, 'large_pages': [2, 1], 'tail_levels': [4, 3, 2], 'tail_origin': 199, 'tail_spans': [3, 9, 21], 'tail_map': {4: 201, 3: 204, 2: 213}, 'large_map': {0: 7, 1: 135}, 'selected': 213, 'tail_used': 33, 'allocation_end': 327}), ({'sizes': [124, 64, 20, 8, 1], 'threshold': 32, 'page': 64, 'level': 3, 'base': 7, 'tail_capacity': 128}, {'tail_first': 2, 'large_pages': [2, 1], 'tail_levels': [4, 3, 2], 'tail_origin': 199, 'tail_spans': [3, 10, 22], 'tail_map': {4: 201, 3: 204, 2: 214}, 'large_map': {0: 7, 1: 135}, 'selected': 204, 'tail_used': 35, 'allocation_end': 327}), ({'sizes': [125, 65, 21, 9, 1], 'threshold': 32, 'page': 64, 'level': 4, 'base': 7, 'tail_capacity': 128}, {'tail_first': 2, 'large_pages': [2, 2], 'tail_levels': [4, 3, 2], 'tail_origin': 263, 'tail_spans': [3, 11, 23], 'tail_map': {4: 265, 3: 268, 2: 279}, 'large_map': {0: 7, 1: 135}, 'selected': 265, 'tail_used': 37, 'allocation_end': 391}), ({'sizes': [126, 66, 22, 10, 1], 'threshold': 32, 'page': 64, 'level': 0, 'base': 7, 'tail_capacity': 128}, {'tail_first': 2, 'large_pages': [2, 2], 'tail_levels': [4, 3, 2], 'tail_origin': 263, 'tail_spans': [3, 12, 24], 'tail_map': {4: 265, 3: 268, 2: 280}, 'large_map': {0: 7, 1: 135}, 'selected': 7, 'tail_used': 39, 'allocation_end': 391})], 2: [({'sizes': [122, 61, 17, 5, 1], 'threshold': 32, 'page': 64, 'level': 0, 'base': 14, 'tail_capacity': 128}, {'tail_first': 2, 'large_pages': [2, 1], 'tail_levels': [4, 3, 2], 'tail_origin': 206, 'tail_spans': [3, 7, 19], 'tail_map': {4: 208, 3: 211, 2: 218}, 'large_map': {0: 14, 1: 142}, 'selected': 14, 'tail_used': 29, 'allocation_end': 334}), ({'sizes': [123, 62, 18, 6, 1], 'threshold': 32, 'page': 64, 'level': 1, 'base': 14, 'tail_capacity': 128}, {'tail_first': 2, 'large_pages': [2, 1], 'tail_levels': [4, 3, 2], 'tail_origin': 206, 'tail_spans': [3, 8, 20], 'tail_map': {4: 208, 3: 211, 2: 219}, 'large_map': {0: 14, 1: 142}, 'selected': 142, 'tail_used': 31, 'allocation_end': 334}), ({'sizes': [124, 63, 19, 7, 1], 'threshold': 32, 'page': 64, 'level': 2, 'base': 14, 'tail_capacity': 128}, {'tail_first': 2, 'large_pages': [2, 1], 'tail_levels': [4, 3, 2], 'tail_origin': 206, 'tail_spans': [3, 9, 21], 'tail_map': {4: 208, 3: 211, 2: 220}, 'large_map': {0: 14, 1: 142}, 'selected': 220, 'tail_used': 33, 'allocation_end': 334}), ({'sizes': [125, 64, 20, 8, 1], 'threshold': 32, 'page': 64, 'level': 3, 'base': 14, 'tail_capacity': 128}, {'tail_first': 2, 'large_pages': [2, 1], 'tail_levels': [4, 3, 2], 'tail_origin': 206, 'tail_spans': [3, 10, 22], 'tail_map': {4: 208, 3: 211, 2: 221}, 'large_map': {0: 14, 1: 142}, 'selected': 211, 'tail_used': 35, 'allocation_end': 334}), ({'sizes': [126, 65, 21, 9, 1], 'threshold': 32, 'page': 64, 'level': 4, 'base': 14, 'tail_capacity': 128}, {'tail_first': 2, 'large_pages': [2, 2], 'tail_levels': [4, 3, 2], 'tail_origin': 270, 'tail_spans': [3, 11, 23], 'tail_map': {4: 272, 3: 275, 2: 286}, 'large_map': {0: 14, 1: 142}, 'selected': 272, 'tail_used': 37, 'allocation_end': 398}), ({'sizes': [127, 66, 22, 10, 1], 'threshold': 32, 'page': 64, 'level': 0, 'base': 14, 'tail_capacity': 128}, {'tail_first': 2, 'large_pages': [2, 2], 'tail_levels': [4, 3, 2], 'tail_origin': 270, 'tail_spans': [3, 12, 24], 'tail_map': {4: 272, 3: 275, 2: 287}, 'large_map': {0: 14, 1: 142}, 'selected': 14, 'tail_used': 39, 'allocation_end': 398})], 3: [({'sizes': [123, 61, 17, 5, 1], 'threshold': 32, 'page': 64, 'level': 0, 'base': 21, 'tail_capacity': 128}, {'tail_first': 2, 'large_pages': [2, 1], 'tail_levels': [4, 3, 2], 'tail_origin': 213, 'tail_spans': [3, 7, 19], 'tail_map': {4: 215, 3: 218, 2: 225}, 'large_map': {0: 21, 1: 149}, 'selected': 21, 'tail_used': 29, 'allocation_end': 341}), ({'sizes': [124, 62, 18, 6, 1], 'threshold': 32, 'page': 64, 'level': 1, 'base': 21, 'tail_capacity': 128}, {'tail_first': 2, 'large_pages': [2, 1], 'tail_levels': [4, 3, 2], 'tail_origin': 213, 'tail_spans': [3, 8, 20], 'tail_map': {4: 215, 3: 218, 2: 226}, 'large_map': {0: 21, 1: 149}, 'selected': 149, 'tail_used': 31, 'allocation_end': 341}), ({'sizes': [125, 63, 19, 7, 1], 'threshold': 32, 'page': 64, 'level': 2, 'base': 21, 'tail_capacity': 128}, {'tail_first': 2, 'large_pages': [2, 1], 'tail_levels': [4, 3, 2], 'tail_origin': 213, 'tail_spans': [3, 9, 21], 'tail_map': {4: 215, 3: 218, 2: 227}, 'large_map': {0: 21, 1: 149}, 'selected': 227, 'tail_used': 33, 'allocation_end': 341}), ({'sizes': [126, 64, 20, 8, 1], 'threshold': 32, 'page': 64, 'level': 3, 'base': 21, 'tail_capacity': 128}, {'tail_first': 2, 'large_pages': [2, 1], 'tail_levels': [4, 3, 2], 'tail_origin': 213, 'tail_spans': [3, 10, 22], 'tail_map': {4: 215, 3: 218, 2: 228}, 'large_map': {0: 21, 1: 149}, 'selected': 218, 'tail_used': 35, 'allocation_end': 341}), ({'sizes': [127, 65, 21, 9, 1], 'threshold': 32, 'page': 64, 'level': 4, 'base': 21, 'tail_capacity': 128}, {'tail_first': 2, 'large_pages': [2, 2], 'tail_levels': [4, 3, 2], 'tail_origin': 277, 'tail_spans': [3, 11, 23], 'tail_map': {4: 279, 3: 282, 2: 293}, 'large_map': {0: 21, 1: 149}, 'selected': 279, 'tail_used': 37, 'allocation_end': 405}), ({'sizes': [128, 66, 22, 10, 1], 'threshold': 32, 'page': 64, 'level': 0, 'base': 21, 'tail_capacity': 128}, {'tail_first': 2, 'large_pages': [2, 2], 'tail_levels': [4, 3, 2], 'tail_origin': 277, 'tail_spans': [3, 12, 24], 'tail_map': {4: 279, 3: 282, 2: 294}, 'large_map': {0: 21, 1: 149}, 'selected': 21, 'tail_used': 39, 'allocation_end': 405})], 4: [({'sizes': [124, 61, 17, 5, 1], 'threshold': 32, 'page': 64, 'level': 0, 'base': 28, 'tail_capacity': 128}, {'tail_first': 2, 'large_pages': [2, 1], 'tail_levels': [4, 3, 2], 'tail_origin': 220, 'tail_spans': [3, 7, 19], 'tail_map': {4: 222, 3: 225, 2: 232}, 'large_map': {0: 28, 1: 156}, 'selected': 28, 'tail_used': 29, 'allocation_end': 348}), ({'sizes': [125, 62, 18, 6, 1], 'threshold': 32, 'page': 64, 'level': 1, 'base': 28, 'tail_capacity': 128}, {'tail_first': 2, 'large_pages': [2, 1], 'tail_levels': [4, 3, 2], 'tail_origin': 220, 'tail_spans': [3, 8, 20], 'tail_map': {4: 222, 3: 225, 2: 233}, 'large_map': {0: 28, 1: 156}, 'selected': 156, 'tail_used': 31, 'allocation_end': 348}), ({'sizes': [126, 63, 19, 7, 1], 'threshold': 32, 'page': 64, 'level': 2, 'base': 28, 'tail_capacity': 128}, {'tail_first': 2, 'large_pages': [2, 1], 'tail_levels': [4, 3, 2], 'tail_origin': 220, 'tail_spans': [3, 9, 21], 'tail_map': {4: 222, 3: 225, 2: 234}, 'large_map': {0: 28, 1: 156}, 'selected': 234, 'tail_used': 33, 'allocation_end': 348}), ({'sizes': [127, 64, 20, 8, 1], 'threshold': 32, 'page': 64, 'level': 3, 'base': 28, 'tail_capacity': 128}, {'tail_first': 2, 'large_pages': [2, 1], 'tail_levels': [4, 3, 2], 'tail_origin': 220, 'tail_spans': [3, 10, 22], 'tail_map': {4: 222, 3: 225, 2: 235}, 'large_map': {0: 28, 1: 156}, 'selected': 225, 'tail_used': 35, 'allocation_end': 348}), ({'sizes': [128, 65, 21, 9, 1], 'threshold': 32, 'page': 64, 'level': 4, 'base': 28, 'tail_capacity': 128}, {'tail_first': 2, 'large_pages': [2, 2], 'tail_levels': [4, 3, 2], 'tail_origin': 284, 'tail_spans': [3, 11, 23], 'tail_map': {4: 286, 3: 289, 2: 300}, 'large_map': {0: 28, 1: 156}, 'selected': 286, 'tail_used': 37, 'allocation_end': 412}), ({'sizes': [129, 66, 22, 10, 1], 'threshold': 32, 'page': 64, 'level': 0, 'base': 28, 'tail_capacity': 128}, {'tail_first': 2, 'large_pages': [3, 2], 'tail_levels': [4, 3, 2], 'tail_origin': 348, 'tail_spans': [3, 12, 24], 'tail_map': {4: 350, 3: 353, 2: 365}, 'large_map': {0: 28, 1: 220}, 'selected': 28, 'tail_used': 39, 'allocation_end': 476})], 5: [({'sizes': [125, 61, 17, 5, 1], 'threshold': 32, 'page': 64, 'level': 0, 'base': 35, 'tail_capacity': 128}, {'tail_first': 2, 'large_pages': [2, 1], 'tail_levels': [4, 3, 2], 'tail_origin': 227, 'tail_spans': [3, 7, 19], 'tail_map': {4: 229, 3: 232, 2: 239}, 'large_map': {0: 35, 1: 163}, 'selected': 35, 'tail_used': 29, 'allocation_end': 355}), ({'sizes': [126, 62, 18, 6, 1], 'threshold': 32, 'page': 64, 'level': 1, 'base': 35, 'tail_capacity': 128}, {'tail_first': 2, 'large_pages': [2, 1], 'tail_levels': [4, 3, 2], 'tail_origin': 227, 'tail_spans': [3, 8, 20], 'tail_map': {4: 229, 3: 232, 2: 240}, 'large_map': {0: 35, 1: 163}, 'selected': 163, 'tail_used': 31, 'allocation_end': 355}), ({'sizes': [127, 63, 19, 7, 1], 'threshold': 32, 'page': 64, 'level': 2, 'base': 35, 'tail_capacity': 128}, {'tail_first': 2, 'large_pages': [2, 1], 'tail_levels': [4, 3, 2], 'tail_origin': 227, 'tail_spans': [3, 9, 21], 'tail_map': {4: 229, 3: 232, 2: 241}, 'large_map': {0: 35, 1: 163}, 'selected': 241, 'tail_used': 33, 'allocation_end': 355}), ({'sizes': [128, 64, 20, 8, 1], 'threshold': 32, 'page': 64, 'level': 3, 'base': 35, 'tail_capacity': 128}, {'tail_first': 2, 'large_pages': [2, 1], 'tail_levels': [4, 3, 2], 'tail_origin': 227, 'tail_spans': [3, 10, 22], 'tail_map': {4: 229, 3: 232, 2: 242}, 'large_map': {0: 35, 1: 163}, 'selected': 232, 'tail_used': 35, 'allocation_end': 355}), ({'sizes': [129, 65, 21, 9, 1], 'threshold': 32, 'page': 64, 'level': 4, 'base': 35, 'tail_capacity': 128}, {'tail_first': 2, 'large_pages': [3, 2], 'tail_levels': [4, 3, 2], 'tail_origin': 355, 'tail_spans': [3, 11, 23], 'tail_map': {4: 357, 3: 360, 2: 371}, 'large_map': {0: 35, 1: 227}, 'selected': 357, 'tail_used': 37, 'allocation_end': 483}), ({'sizes': [130, 66, 22, 10, 1], 'threshold': 32, 'page': 64, 'level': 0, 'base': 35, 'tail_capacity': 128}, {'tail_first': 2, 'large_pages': [3, 2], 'tail_levels': [4, 3, 2], 'tail_origin': 355, 'tail_spans': [3, 12, 24], 'tail_map': {4: 357, 3: 360, 2: 372}, 'large_map': {0: 35, 1: 227}, 'selected': 35, 'tail_used': 39, 'allocation_end': 483})]}
for i, (p, expected) in enumerate(cases[N]):
    check("layout fixture " + str(i + 1), solve(p), 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
layout fixture 1{'allocation_end': 327, 'large_map': {'0': 7, '1': 135}, 'large_pages': [2, 1], 'selected': 7, 'tail_first': 2, 'tail_levels': [4, 3, 2], 'tail_map': {'2': 211, '3': 204, '4': 201}, 'tail_origin': 199, 'tail_spans': [3, 7, 19], 'tail_used': 29}{'allocation_end': 327, 'large_map': {'0': 7, '1': 135}, 'large_pages': [2, 1], 'selected': 7, 'tail_first': 2, 'tail_levels': [4, 3, 2], 'tail_map': {'2': 211, '3': 204, '4': 201}, 'tail_origin': 199, 'tail_spans': [3, 7, 19], 'tail_used': 29}Passed
layout fixture 2{'allocation_end': 327, 'large_map': {'0': 7, '1': 135}, 'large_pages': [2, 1], 'selected': 135, 'tail_first': 2, 'tail_levels': [4, 3, 2], 'tail_map': {'2': 212, '3': 204, '4': 201}, 'tail_origin': 199, 'tail_spans': [3, 8, 20], 'tail_used': 31}{'allocation_end': 327, 'large_map': {'0': 7, '1': 135}, 'large_pages': [2, 1], 'selected': 135, 'tail_first': 2, 'tail_levels': [4, 3, 2], 'tail_map': {'2': 212, '3': 204, '4': 201}, 'tail_origin': 199, 'tail_spans': [3, 8, 20], 'tail_used': 31}Passed
layout fixture 3{'allocation_end': 327, 'large_map': {'0': 7, '1': 135}, 'large_pages': [2, 1], 'selected': 213, 'tail_first': 2, 'tail_levels': [4, 3, 2], 'tail_map': {'2': 213, '3': 204, '4': 201}, 'tail_origin': 199, 'tail_spans': [3, 9, 21], 'tail_used': 33}{'allocation_end': 327, 'large_map': {'0': 7, '1': 135}, 'large_pages': [2, 1], 'selected': 213, 'tail_first': 2, 'tail_levels': [4, 3, 2], 'tail_map': {'2': 213, '3': 204, '4': 201}, 'tail_origin': 199, 'tail_spans': [3, 9, 21], 'tail_used': 33}Passed
layout fixture 4{'allocation_end': 327, 'large_map': {'0': 7, '1': 135}, 'large_pages': [2, 1], 'selected': 204, 'tail_first': 2, 'tail_levels': [4, 3, 2], 'tail_map': {'2': 214, '3': 204, '4': 201}, 'tail_origin': 199, 'tail_spans': [3, 10, 22], 'tail_used': 35}{'allocation_end': 327, 'large_map': {'0': 7, '1': 135}, 'large_pages': [2, 1], 'selected': 204, 'tail_first': 2, 'tail_levels': [4, 3, 2], 'tail_map': {'2': 214, '3': 204, '4': 201}, 'tail_origin': 199, 'tail_spans': [3, 10, 22], 'tail_used': 35}Passed
layout fixture 5{'allocation_end': 391, 'large_map': {'0': 7, '1': 135}, 'large_pages': [2, 2], 'selected': 265, 'tail_first': 2, 'tail_levels': [4, 3, 2], 'tail_map': {'2': 279, '3': 268, '4': 265}, 'tail_origin': 263, 'tail_spans': [3, 11, 23], 'tail_used': 37}{'allocation_end': 391, 'large_map': {'0': 7, '1': 135}, 'large_pages': [2, 2], 'selected': 265, 'tail_first': 2, 'tail_levels': [4, 3, 2], 'tail_map': {'2': 279, '3': 268, '4': 265}, 'tail_origin': 263, 'tail_spans': [3, 11, 23], 'tail_used': 37}Passed
layout fixture 6{'allocation_end': 391, 'large_map': {'0': 7, '1': 135}, 'large_pages': [2, 2], 'selected': 7, 'tail_first': 2, 'tail_levels': [4, 3, 2], 'tail_map': {'2': 280, '3': 268, '4': 265}, 'tail_origin': 263, 'tail_spans': [3, 12, 24], 'tail_used': 39}{'allocation_end': 391, 'large_map': {'0': 7, '1': 135}, 'large_pages': [2, 2], 'selected': 7, 'tail_first': 2, 'tail_levels': [4, 3, 2], 'tail_map': {'2': 280, '3': 268, '4': 265}, 'tail_origin': 263, 'tail_spans': [3, 12, 24], 'tail_used': 39}Passed

SHA-256 / d46c75c87e5248cb41d37223b6126e391807ef83f1c04a3178c0cd3f9ca9d8b8

Verification & scope

Stipulated deterministic toy buffer layout; not a graphics API, codec, GPU vendor tiling specification, or hardware-conformance claim. Inputs satisfy the dimensions and bounds stated by the model. 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:45:31.536779+00:00.

Case digest / 0f02f7d24c9dd434751e22d5352acf941b7e831e07d5912555c6549ebdd655b7