summaryrefslogtreecommitdiff
path: root/design/mock/heap.py
blob: e4c3e3a0b6b1fe79e8b80173544157d354c68af8 (plain) (blame)
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
#!/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")