1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
|
#!/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 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, ()),
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>")
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")
|