#!/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 · 0x2f8 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, 0x2f8, fl, mem, HEAP, region, framed=[(0, 2), (0x98, 8)], bare=True, x=x, rows_shown=[0, 9, 10], changed=changed) 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)", ["Two more pushes, at a run: three chunks in a row, each with P", "set, the chunk before it in use. Settled: no marks, the arcs standing."]), ("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, the old link stays."]), ] 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, ()), touched={0x405030} if inst == "D" else ()) # 2 is a run's end: settled, no marks # the tcache's loupe lies over the stack, never over the registers: in 18-heap-free, not on this sheet for i, line in enumerate(cap): g.t(LX, 440 + i * 44, line, 32, VELLUM, "sans") g.o.append("") g.save(name) # ---- beat 3 whole: the first free, mid-step, in the working frame (`subject`) --------------------------------- H_, S_, C_, D_ = HEAP, C.STACK, C.CODE, DATA SRC = open(__file__.replace("heap.py", "heap.c")).read().split("\n") RBP = [(0x7fffffffed00, S_), (0x7fffffffedb0, S_), (0x7fffffffee10, S_)] REGS = [("rax", [], ("int", 0)), ("rbx", [], ("int", 0)), ("rcx", [], ("int", 0x405)), ("rdx", [], ("int", 0xf)), ("rsi", [], ("int", 0xe2263c1be1246b56)), ("rdi", [(0x405050, H_)], ("int", 0x405)), ("rbp", [(0x7fffffffecf0, S_)] + RBP, ("int", 0)), ("rsp", [(0x7fffffffece0, S_)], ("int", 0)), ("r8", [(0x405070, H_)], ("int", 0x10001000100f)), ("r9", [], ("int", 0x20)), ("r10", [], ("int", 0x21)), ("r11", [(0x7ffff7e19ac8, D_)], None), ("r12", [(0x7fffffffee38, S_), (0x7fffffffefea, S_)], ("str", "./heap")), ("r13", [], ("int", 1)), ("r14", [(0x7ffff7ffd000, D_), (0x7ffff7ffe3c0, D_)], ("int", 0)), ("r15", [(0x403df0, D_), (0x401110, C_, "__do_global_dtors_aux")], None), ("rip", [(0x4011b6, C_, "pop+46")], None)] FLAGS = [("CF", 0, 0), ("PF", 1, 0), ("AF", 0, 0), ("ZF", 0, 0), ("SF", 0, 0), ("IF", 1, 0), ("DF", 0, 0), ("OF", 0, 0)] STACK = [(0x7fffffffece0, ["rsp"], [], ("int", 0)), (0x7fffffffece8, [], [(0x405050, H_)], ("int", 0x405)), (0x7fffffffecf0, ["rbp"], RBP, ("int", 0)), (0x7fffffffecf8, [], [(0x4011e0, C_, "main+39")], None), (0x7fffffffed00, [], RBP[1:], ("int", 0)), (0x7fffffffed08, [], [(0x7ffff7c27781, C_, "libc+27781")], None)] P = VELLUM DIS = [(0x40119b, 19, "mov", "rax, qword ptr [rbp - 8]", None, None), (0x40119f, 19, "mov", "rax, qword ptr [rax + 8]", None, None), (0x4011a3, 19, "mov", "qword ptr [rip + 0x2e7e], rax", None, ("text", "head", DATA)), (0x4011aa, 20, "mov", "rax, qword ptr [rbp - 8]", "trail1", None), (0x4011ae, 20, "mov", "rdi, rax", "trail0", None), (0x4011b1, 20, "call", (0x401030, "free@plt"), "cur", ("runs", [("free", BRIGHT), (" in libc, stepped over", FAINT)])), (0x4011b6, 21, "nop", "", None, ("set", "rdi", [(0x405050, H_)], ("int", 0x405))), (0x4011b7, 21, "leave", "", None, None), (0x4011b8, 21, "ret", "", None, None)] def frame_free(name): """The first free in the working frame: the register wave struck, the chunk's words struck on the bytes that changed, the node gone down to the bin's row, and the loupe on the tcache over the stack, never the registers.""" gen.W, gen.H = 1920, 1080 g = Svg() sp = C.SUBJECT y = 48 + sp["band"] + 12 ys = C.source(g, y, sp["src"], SRC, 14, 20, [19, 18], "heap.c", 31) at = C.disasm(g, y + ph(sp["src"]) + 12, [(a, ln, mn, [(ops, C.CODE)] if isinstance(ops, tuple) else ([(ops, P)] if ops else []), st, note) for a, ln, mn, ops, st, note in DIS], "pop", 20) C.thread(g, ys, [(at[0x4011aa], at[0x4011b1] + ROW)]) yr = 48 + sp["view"] + 12 C.registers(g, yr, REGS, FLAGS, {r: {0: "strike"} for r in ("rax", "rcx", "rdx", "rsi", "r8", "r10")}) C.stack(g, yr + ph(17) + 12, STACK, [("pop", 0, 3), ("main", 4, 5)], rsp=0x7fffffffece0, roles={1: ("n", VELLUM), 2: ("saved rbp", DIM), 4: ("saved rbp", DIM)}) drawing(g, 48, sp["band"], "C") rows_y = C.fields(g, 48, sp["view"], "the heap, 405000 to 40506f", BASE, 0x70, chunk_fields("C"), MEM["C"], HEAP, region, rows_shown=list(range(7)), more_rows=False, changed=CHANGED["C"]) ly = 888 - ph(5) # over the stack, clamped to the stage loupe(g, RX, ly, "C", LOUPE_CHANGED["C"]) foot = rows_y[0x405060] + ROW + 2 # the stem: from under the row's address, down the gutter's right lane g.rect(RX + 34 - 2, foot - 2, 6 * A + 4, 4, HEAP) gen.arrow(g, [(RX + 32, foot), (962, foot), (962, ly + 12), (RX - 1, ly + 12)], HEAP, 3, r=8, hl=10, hw=10) C.clock(g, 7, 12) gen.caption(g, [[("free gave 9's chunk to the tcache, malloc's bin for ",), ("0x20", "mono"), (". Its first",)], [("word is the link now: ",), ("405", "mono"), (", which is NULL, safe-linked.",)]]) g.save(name) if __name__ == "__main__": assert 0x405455 ^ (0x405030 >> 12) == 0x405050 and 0x405 ^ (0x405050 >> 12) == 0 # safe-linking, as stored storyboard("18-heap") frame_free("18-heap-free")