diff options
| author | Gabriel Schneider <[email protected]> | 2026-11-10 23:25:40 -0300 |
|---|---|---|
| committer | Gabriel Schneider <[email protected]> | 2026-11-10 23:34:16 -0300 |
| commit | 2a97030c9743d4680d698414c28e8d8739614215 (patch) | |
| tree | 8415bb3aeeb5d5d909a2d311c2a30ab07f91c9fa /design/mock/heap.py | |
| parent | 58643dab07a803dbb579d84f68419911f5a2a16d (diff) | |
| download | computeranim-2a97030c9743d4680d698414c28e8d8739614215.tar.gz computeranim-2a97030c9743d4680d698414c28e8d8739614215.zip | |
design: down is deeper; a call followed down; operands without size words; the heap as a scene
From the user. Direction and nearness are rules: the idea, the source,
its instructions, the callee and the kernel go down the frame, a call
goes down and a return comes up, and every tie runs one of those ways.
The disassembly can descend: a window a call depth, the caller keeping
three rows with its call waiting, a PLT stub its jump, the kernel at the
bottom on vellum, with verbs descend, cross and ascend. The kernel leaves
the band, which keeps the calls so far as strace writes them; the
backtrace has its newest frame at the bottom. Size words are dropped
from operands and a width is shown as byte cells where nothing else says
it; a compare shows its values and flags, a jump the flags it reads, an
indirect call its target and the slot it was read from. libc's heap is a
scene of blocks that exist (a dump by fields with a size and a protected
pointer read, arcs as the free list, a loupe into the tcache, the list
drawn over malloc's own), storyboarded on glibc 2.44. Mocks 16 to 18.
Co-Authored-By: Claude Fable 5.2 <[email protected]>
Claude-Session: https://claude.ai/code/session_016Y9MNCKgYCGiANnEwcEQxa
Diffstat (limited to 'design/mock/heap.py')
| -rw-r--r-- | design/mock/heap.py | 229 |
1 files changed, 229 insertions, 0 deletions
diff --git a/design/mock/heap.py b/design/mock/heap.py new file mode 100644 index 0000000..e4c3e3a --- /dev/null +++ b/design/mock/heap.py @@ -0,0 +1,229 @@ +#!/usr/bin/env python3 +"""Mock 18: libc's heap from the inside, a storyboard of five instants, drawn with the blocks the language has. + + python3 -B heap.py # writes 18-heap.svg + +The program is heap.c (three pushes, two pops, a push). The data is a fresh recording: `ztrace dbg` on it (cc -O0 +-no-pie, glibc 2.44, env -i setarch -R), stopped after each malloc and free returns, `x 0x405000 1024` at each +stop. Each instant is the band as the scene's `subject` split draws it (the drawing, its view of seven rows) and +the loupe on the tcache under the view; the caption under it is the scene's. +""" +import gen +import dense as D +import context as C +from context import (PAGE, RAISED, RULE, VELLUM, BRIGHT, DIM, FAINT, GOLD, HEAP, DATA, A, S, ROW, TAG, PAD, + MONO, BOLD, LX, RX, CW, b, ph, mix, Svg) + +BASE = 0x405000 + + +def rows(*hexrows): + """{address: byte} from rows of 32 hex digits, from BASE.""" + out = {} + for r, h in enumerate(hexrows): + for i, v in enumerate(bytes.fromhex(h.replace(" ", ""))): + out[BASE + 16 * r + i] = v + return out + + +Z, SZ = "00" * 8, "2100000000000000" +KEY = "538903 0acfc59f6b" +# the heap's first seven rows at each stop, as `x` printed them +MEM = { + "A": rows(Z + SZ, "00" * 16, Z + "e10f020000000000", "00" * 16, "00" * 16, "00" * 16, "00" * 16), + "B": rows(Z + SZ, "0700000000000000" + Z, Z + SZ, "0c00000000000000" + "1050400000000000", Z + SZ, + "0900000000000000" + "3050400000000000", Z + "a10f020000000000"), + "C": rows(Z + SZ, "0700000000000000" + Z, Z + SZ, "0c00000000000000" + "1050400000000000", Z + SZ, + "0504000000000000" + KEY, Z + "0103000000000000"), + "D": rows(Z + SZ, "0700000000000000" + Z, Z + SZ, "5554400000000000" + KEY, Z + SZ, + "0504000000000000" + KEY, Z + "0103000000000000"), + "E": rows(Z + SZ, "0700000000000000" + Z, Z + SZ, "5554400000000000" + Z, Z + SZ, + "0504000000000000" + KEY, Z + "0103000000000000"), +} +# the tcache: num_slots[0] at 405070 (slots left for 0x20: 16 less the chunks in the bin), entries[0] at 405108 +TC = {"C": (0x0f, 0x405050), "D": (0x0e, 0x405030), "E": (0x0f, 0x405050)} + + +def region(v): + return HEAP if 0x405000 <= v < 0x426000 else DATA if 0x404000 <= v < 0x405000 else None + + +def chunk_fields(inst): + """The view's fields: each chunk's size word (`size`: the size and its flags), and its body as the program + has it (a node's value and next) or as malloc does (the protected link and the key).""" + free = {"C": {0x405050}, "D": {0x405030, 0x405050}, "E": {0x405050}}.get(inst, set()) + out = [] + for c in (0x405000, 0x405020, 0x405040): + body = c + 16 - BASE + if inst == "A" and c != 0x405000: + continue + out.append((c + 8 - BASE, 8, "size", False, None)) + if c + 16 in free: + out += [(body, 8, "protected", False, None), (body + 8, 8, "bytes", False, None, "key")] + elif inst == "E" and c == 0x405020: # malloc's again the program's, not yet written: the stale link + out += [(body, 8, "bytes", False, None, "the old link"), (body + 8, 8, "pointer", False, None)] + else: + out += [(body, 8, "number", False, None), (body + 8, 8, "pointer", False, None)] + top = 0x405020 if inst == "A" else 0x405060 + out.append((top + 8 - BASE, 8, "size", False, None, "tcache" if inst in "CDE" else "top")) + return out + + +def node(g, x, y, value=None, nxt=None, xs=None, free=False, stale=None, k=1): + """A chunk as the `nodes` drawing has it: the value's half and the pointer's. Free: the first word is the + link now (its square, its arrow) and the second the key, hatched; the outline dashed, as `freed`.""" + NW, NH, VW = 136, 44, 88 + if free: + g.rect(x, y, VW - 2, NH, C.WELL) + g.rect(x + VW, y, NW - VW, NH, "url(#hatch)") + g.t(x + VW + (NW - VW) / 2, y + 17, "key", S, FAINT, MONO, "middle") # over the link's line + g.frame(x - 3, y - 3, NW + 6, NH + 6, DIM, 2, "12 8") + cx, cy = x + VW / 2, y + NH / 2 + else: + g.rect(x, y, VW - 2, NH, RAISED) + if stale is not None: # allocated, not yet written: what the bytes still hold + g.t(x + VW / 2 - 1, b(y + 10), "%x" % stale, S, FAINT, MONO, "middle") + else: + g.t(x + VW / 2 - 1, y + NH / 2 + 0.36 * 25, str(value), 25, VELLUM, MONO, "middle") + g.rect(x + VW, y, NW - VW, NH, C.WELL) + cx, cy = x + VW + (NW - VW) / 2, y + NH / 2 + if nxt: + g.rect(cx - 5, cy - 5, 10, 10, HEAP) + gen.arrow(g, [(cx + 8, cy), (xs[nxt] - 3, cy)], HEAP, 3, hl=12, hw=10) + elif nxt == 0: + sx = x + 10 if free else x + VW + 10 + g.path(f"M{sx},{y + NH - 8} L{sx + (VW if free else NW - VW) - 20},{y + 8}", DIM, 2) + + +def drawing(g, y, h, inst): + """The heap's chunks as two lists: the program's, from `head`, over malloc's bin for 0x20, from the tcache. + A chunk moves between the rows; its bytes are the view's.""" + C.tag(g, LX, y, CW, h, "the chunks of 0x20", focus=True, note="the program's list · malloc's free list") + NW, P0, PITCH = 136, LX + 200, 160 + y1, y2 = y + TAG + 52, y + TAG + 162 + top = {"A": [0x405010], "B": [0x405050, 0x405030, 0x405010], "C": [0x405030, 0x405010], + "D": [0x405010], "E": [0x405030, 0x405010]}[inst] + tbin = {"C": [0x405050], "D": [0x405030, 0x405050], "E": [0x405050]}.get(inst, []) + vals = {0x405010: 7, 0x405030: 12, 0x405050: 9} + links = {"B": {0x405050: 0x405030, 0x405030: 0x405010, 0x405010: 0}, "C": {0x405030: 0x405010, 0x405010: 0}, + "D": {0x405010: 0}, "E": {0x405010: 0}}.get(inst, {}) + g.t(LX + 16, b(y1 + 10), "the program's", 18, FAINT, "sans") + xs = {a: P0 + i * PITCH for i, a in enumerate(top)} + for a in top: + g.t(xs[a] + NW / 2, y1 - 8, "%x" % a, 20, HEAP, MONO, "middle") + for a in top: + if inst == "A" or (inst == "E" and a == 0x405030): + node(g, xs[a], y1, stale=0 if inst == "A" else 0x405455, nxt=None, xs=xs) + else: + node(g, xs[a], y1, vals[a], links[a], xs) + # malloc's row: the bin's head, a box with the count on its shoulder, then the free chunks, then the top + bx = LX + 16 + if inst in "AB": # glibc 2.44 makes the tcache at the first free; till then a dummy in libc + g.frame(bx, y2, 160, 44, FAINT, 2, "12 8") + g.t(bx + 80, y2 + 22 + 0.36 * 20, "dummy tcache", S, FAINT, MONO, "middle") + else: + g.rect(bx, y2, 160, 44, RAISED) + g.t(bx + 80, y2 + 22 + 0.36 * 20, "tcache 0x20", S, VELLUM, MONO, "middle") + g.rect(bx + 160 - 18, y2 - 26, 30, 30, PAGE) + g.frame(bx + 160 - 18, y2 - 26, 30, 30, FAINT, 2) + g.t(bx + 160 - 3, y2 - 11 + 0.36 * 25, str(len(tbin)), 25, VELLUM, MONO, "middle") + xb = {a: P0 + i * PITCH for i, a in enumerate(tbin)} + if tbin: + gen.arrow(g, [(bx + 160, y2 + 22), (xb[tbin[0]] - 3, y2 + 22)], HEAP, 3, hl=12, hw=10) + for i, a in enumerate(tbin): + g.t(xb[a] + NW / 2, y2 - 8, "%x" % a, 20, HEAP, MONO, "middle") + node(g, xb[a], y2, free=True, nxt=tbin[i + 1] if i + 1 < len(tbin) else 0, xs=xb) + tx = LX + 680 + g.rect(tx, y2, 164, 44, RAISED) + g.frame(tx, y2, 164, 44, FAINT, 2, "12 8") + size = {"A": 0x20fe0, "B": 0x20fa0}.get(inst, 0x20ca0) + g.t(tx + 12, y2 + 22 + 0.36 * 20, "top", S, DIM, MONO) + g.t(tx + 152, y2 + 22 + 0.36 * 20, "0x%x" % size, S, VELLUM, MONO, "end") + g.t(tx + 82, y2 - 8, "%x" % (0x405020 if inst == "A" else 0x405060 if inst == "B" else 0x405360), 20, HEAP, MONO, + "middle") + # pins: a variable in the ink of where it lives (head, a global: data), a register in primary + pins = {"A": [(top, 0x405010, ["rax"])], "B": [(top, 0x405050, ["head"])], + "C": [(top, 0x405030, ["head"]), (tbin, 0x405050, ["rdi"])], + "D": [(top, 0x405010, ["head"]), (tbin, 0x405030, ["rdi"])], + "E": [(top, 0x405030, ["rax"]), (top, 0x405010, ["head"])]}[inst] + for row, a, names in pins: + x0 = (xs if row is top else xb)[a] + yy = (y1 if row is top else y2) + 44 + C.pin_up(g, x0 + NW / 2, yy, names, HEAP, 20) + if names == ["head"]: # a global's name in data's ink: redraw it over the primary one + g.t(x0 + NW / 2 - 9, yy + 8 + 20 * 0.86, "head", 20, DATA, BOLD, "end") + + +def loupe(g, x, y, inst, changed): + """The tcache, opened from the row of the chunk it is: its count for 0x20 and its head.""" + h = ph(5) + g.rect(x + 12, y + 16, CW, h, D.SHADE) + g.rect(x, y, CW, h, D.LIFT) + g.rect(x, y, CW, TAG, D.LIFT_TAG) + g.frame(x, y, CW, h, DIM, 2) + xx = x + 12 + for s_, ink in [("tcache", DIM), (" → ", FAINT), ("405070", HEAP)]: + g.t(xx, y + 18, s_, S, ink, MONO) + xx += len(s_) * A + g.t(x + CW - 10, y + 18, "tcache_perthread_struct · 0x2f0 bytes", 18, DIM, "sans", "end") + slots, head = TC[inst] + base = 0x405070 + mem = {base + i: v for i, v in enumerate(bytes([slots, 0] + [0x10, 0] * 7))} + mem.update({base + 0x90 + i: v for i, v in enumerate(bytes([0x10, 0] * 4) + head.to_bytes(8, "little"))}) + mem.update({base + 0xa0 + i: 0 for i in range(16)}) + fl = [(0, 2, "number", False, None, "slots left · %d in the bin" % (16 - slots)), + (0x98, 8, "pointer", False, None, "the head of 0x20")] + C.fields(g, y, h, "", base, 0x2f0, fl, mem, HEAP, region, framed=[(0, 2), (0x98, 8)], bare=True, x=x, + rows_shown=[0, 9, 10], changed=changed) + g.rect(RX + 34 - 2, y - 4, 6 * A + 4, 4, HEAP) # the stem: a bracket under the row's address, on the tag + + +INSTANTS = [ + ("A", "1", "the first malloc", "stop 1, back from malloc in push(7)", + ["malloc(16) cut a chunk of 0x20 off the top: its size word, 0x21,", + "then the 16 bytes rax points at. The top is 0x20 smaller."]), + ("B", "2", "three chunks", "stop 6, after push(9)", + ["Three pushes, three chunks in a row, each with P: the chunk", + "before it is in use. The list's next pointers are arcs in the bytes."]), + ("C", "3", "a free", "stop 7, back from free in the first pop", + ["free gave 9's chunk to the tcache, malloc's bin for 0x20. Its first", + "word is the link now: 405, which is NULL, safe-linked."]), + ("D", "4", "a second free", "stop 8, back from free in the second pop", + ["The second chains to the first: 405455 is 405050 xor 405, the", + "chunk's own address shifted 12. The arc is the pointer it hides."]), + ("E", "5", "malloc takes it back", "stop 9, back from malloc in push(25)", + ["malloc(16) took the bin's head, 405030: the tcache points at 405050", + "again, the key is wiped, and the old link stays until push writes."]), +] +CHANGED = { # the bytes each stop changed, of those on screen: struck + "C": {0x405050, 0x405051} | set(range(0x405058, 0x405060)) | {0x405068, 0x405069, 0x40506a}, + "D": {0x405030, 0x405031, 0x405032} | set(range(0x405038, 0x405040)), + "E": set(range(0x405038, 0x405040)), +} +LOUPE_CHANGED = {"C": {0x405070} | {0x405108, 0x405109, 0x40510a}, "D": {0x405070, 0x405108}, "E": {0x405070, 0x405108}} + + +def storyboard(name): + gen.W, gen.H = 1920, 5 * 560 + 40 + g = Svg() + for k, (inst, num, title, when, cap) in enumerate(INSTANTS): + dy = k * 560 + g.o.append(f'<g transform="translate(0,{dy})">') + g.t(LX, 34, num, 28, GOLD, "sansb") + g.t(LX + 28, 34, title, 28, VELLUM, "sansm") + g.t(LX + 1792, 34, when, 20, FAINT, "sans", "end") + drawing(g, 48, 296, inst) + C.fields(g, 48, 200, "the heap, 405000 to 40506f", BASE, 0x70, chunk_fields(inst), MEM[inst], HEAP, region, + rows_shown=list(range(7)), more_rows=False, changed=CHANGED.get(inst, ()), + held_at={0x405050, 0x405058} if inst == "B" else (), touched={0x405030} if inst == "D" else ()) + if inst in TC: # hung from the view's last row: the chunk that is the tcache + loupe(g, RX + 34 - 92, 48 + TAG + PAD + 7 * ROW + 2, inst, LOUPE_CHANGED[inst]) + for i, line in enumerate(cap): + g.t(LX, 440 + i * 44, line, 32, VELLUM, "sans") + g.o.append("</g>") + g.save(name) + + +if __name__ == "__main__": + assert 0x405455 ^ (0x405030 >> 12) == 0x405050 and 0x405 ^ (0x405050 >> 12) == 0 # safe-linking, as stored + storyboard("18-heap") |
