summaryrefslogtreecommitdiff
path: root/design/mock/heap.py
diff options
context:
space:
mode:
Diffstat (limited to 'design/mock/heap.py')
-rw-r--r--design/mock/heap.py229
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")