#!/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.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.save(name) if __name__ == "__main__": assert 0x405455 ^ (0x405030 >> 12) == 0x405050 and 0x405 ^ (0x405050 >> 12) == 0 # safe-linking, as stored storyboard("18-heap")