diff options
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") |
