From af2d2cfdcdf5976f06fbcc4b1f8507f0b7d4af89 Mon Sep 17 00:00:00 2001 From: Gabriel Schneider Date: Tue, 10 Nov 2026 12:01:16 -0300 Subject: design: the visual system canim follows, with eight mock frames Lapis page and vellum ink; a role is a form as well as a colour (current, write, read, pointer, allocated, freed, fault, kernel); panels as acme windows; Go Mono for the machine and Go for the narrator; motion as whole frames at 60 fps. design/mock/gen.py redraws the mocks from the tokens. --- design/mock/01-fib-recursion-480.png | Bin 0 -> 29901 bytes design/mock/01-fib-recursion.png | Bin 0 -> 130973 bytes design/mock/01-fib-recursion.svg | 282 +++++++ design/mock/02-list-insert-480.png | Bin 0 -> 28715 bytes design/mock/02-list-insert.png | Bin 0 -> 142848 bytes design/mock/02-list-insert.svg | 286 +++++++ design/mock/03-syscall-write-480.png | Bin 0 -> 29669 bytes design/mock/03-syscall-write.png | Bin 0 -> 135294 bytes design/mock/03-syscall-write.svg | 293 +++++++ design/mock/04-malloc-glibc-musl-480.png | Bin 0 -> 25492 bytes design/mock/04-malloc-glibc-musl.png | Bin 0 -> 124884 bytes design/mock/04-malloc-glibc-musl.svg | 273 +++++++ design/mock/05-memory-write-480.png | Bin 0 -> 33443 bytes design/mock/05-memory-write.png | Bin 0 -> 168817 bytes design/mock/05-memory-write.svg | 401 +++++++++ design/mock/06-title-legend-480.png | Bin 0 -> 19214 bytes design/mock/06-title-legend.png | Bin 0 -> 85492 bytes design/mock/06-title-legend.svg | 79 ++ design/mock/07-sort-swap-480.png | Bin 0 -> 19377 bytes design/mock/07-sort-swap.png | Bin 0 -> 88330 bytes design/mock/07-sort-swap.svg | 129 +++ design/mock/08-far-view-480.png | Bin 0 -> 29949 bytes design/mock/08-far-view.png | Bin 0 -> 157996 bytes design/mock/08-far-view.svg | 329 ++++++++ design/mock/gen.py | 1304 ++++++++++++++++++++++++++++++ 25 files changed, 3376 insertions(+) create mode 100644 design/mock/01-fib-recursion-480.png create mode 100644 design/mock/01-fib-recursion.png create mode 100644 design/mock/01-fib-recursion.svg create mode 100644 design/mock/02-list-insert-480.png create mode 100644 design/mock/02-list-insert.png create mode 100644 design/mock/02-list-insert.svg create mode 100644 design/mock/03-syscall-write-480.png create mode 100644 design/mock/03-syscall-write.png create mode 100644 design/mock/03-syscall-write.svg create mode 100644 design/mock/04-malloc-glibc-musl-480.png create mode 100644 design/mock/04-malloc-glibc-musl.png create mode 100644 design/mock/04-malloc-glibc-musl.svg create mode 100644 design/mock/05-memory-write-480.png create mode 100644 design/mock/05-memory-write.png create mode 100644 design/mock/05-memory-write.svg create mode 100644 design/mock/06-title-legend-480.png create mode 100644 design/mock/06-title-legend.png create mode 100644 design/mock/06-title-legend.svg create mode 100644 design/mock/07-sort-swap-480.png create mode 100644 design/mock/07-sort-swap.png create mode 100644 design/mock/07-sort-swap.svg create mode 100644 design/mock/08-far-view-480.png create mode 100644 design/mock/08-far-view.png create mode 100644 design/mock/08-far-view.svg create mode 100644 design/mock/gen.py (limited to 'design/mock') diff --git a/design/mock/01-fib-recursion-480.png b/design/mock/01-fib-recursion-480.png new file mode 100644 index 0000000..167fc50 Binary files /dev/null and b/design/mock/01-fib-recursion-480.png differ diff --git a/design/mock/01-fib-recursion.png b/design/mock/01-fib-recursion.png new file mode 100644 index 0000000..aefa55a Binary files /dev/null and b/design/mock/01-fib-recursion.png differ diff --git a/design/mock/01-fib-recursion.svg b/design/mock/01-fib-recursion.svg new file mode 100644 index 0000000..1cb0378 --- /dev/null +++ b/design/mock/01-fib-recursion.svg @@ -0,0 +1,282 @@ + + + +Recursion +fib(5) +kernel + +memory + +cpu + +source + + + + + + +fib.c +1 +#include +<stdio.h> +2 + +3 +long +fib( +long +n) { + + +4 +if +(n < +2 +) +5 +return +n; + +6 +return +fib(n- +1 +) + fib(n- +2 +); +7 +} +8 +9 +int +main( +void +) { +10 +printf( +"%ld\n" +, fib( +5 +)); +11 +return +0 +; +12 +} + +n = 1 + + + + +calls of fib(n) +each result on its call's shoulder + + + + + + + + + + + + + +5 + +4 + + +3 + +3 + +3 + + +2 + +2 + + +1 + +2 + +2 + + +1 + +1 + + +1 + +1 + + +1 + +0 + + +0 + +1 + +1 + + +1 + +0 + + +0 + + + + +call stack +newest on top + + +fib +n = 1 +:4 + + +fib +n = 2 +:6 + + +fib +n = 3 +:6 + + +fib +n = 5 +:6 + + +main +:10 + + + + +registers +x86-64 + + +0 +0 +0 +0 +5 +5 +d +4 +a +1 +c +0 +1 +1 +4 +1 +rip + + +0 +0 +0 +0 +0 +0 +0 +0 +0 +0 +0 +0 +0 +0 +0 +1 +rax + +0 +0 +0 +0 +0 +0 +0 +0 +0 +0 +0 +0 +0 +0 +0 +1 +rdi + + +0 +0 +0 +0 +7 +f +f +d +3 +a +2 +c +1 +d +c +0 +rsp +0 +0 +0 +0 +7 +f +f +d +3 +a +2 +c +1 +d +e +0 +rbp + +CF + +ZF + + + +SF + + +OF +Four calls to fib are still waiting, each with its own n. +The newest one just received 1 in rdi. + diff --git a/design/mock/02-list-insert-480.png b/design/mock/02-list-insert-480.png new file mode 100644 index 0000000..8cc538f Binary files /dev/null and b/design/mock/02-list-insert-480.png differ diff --git a/design/mock/02-list-insert.png b/design/mock/02-list-insert.png new file mode 100644 index 0000000..6e99916 Binary files /dev/null and b/design/mock/02-list-insert.png differ diff --git a/design/mock/02-list-insert.svg b/design/mock/02-list-insert.svg new file mode 100644 index 0000000..878740d --- /dev/null +++ b/design/mock/02-list-insert.svg @@ -0,0 +1,286 @@ + + + +Linked lists +insert after a node +kernel + +memory + +cpu + +source + + + + + + +list.c +3 +struct +node { +4 +long +value; +5 +struct +node *next; +6 +}; + + + +21 +n = malloc( +sizeof +*n); + +22 +n->value = v; + +23 +n->next = at->next; + + +24 +at->next = n; +25 +return +n; + +locals + +at +0 +0 +0 +0 +5 +5 +d +4 +a +1 +c +0 +3 +2 +a +0 +node 7 + +n +0 +0 +0 +0 +5 +5 +d +4 +a +1 +c +0 +3 +2 +e +0 +node 9 +v +9 + + + + +the list +what the code means + +head + + + +7 + + + +12 + + + +9 + + + + + + + + +at +n +the end + + + + +heap +eight bytes a row, as one number · low addresses on top + + + +malloc's own 16 bytes +55d4 +a1c0 +32a0 + +0 +0 +0 +0 +0 +0 +0 +0 +0 +0 +0 +0 +0 +0 +0 +7 +value += 7 + +at + +55d4 +a1c0 +32a8 + +0 +0 +0 +0 +5 +5 +d +4 +a +1 +c +0 +3 +2 +e +0 +next + + + +55d4 +a1c0 +32c0 + +0 +0 +0 +0 +0 +0 +0 +0 +0 +0 +0 +0 +0 +0 +0 +c +value += 12 +55d4 +a1c0 +32c8 + +0 +0 +0 +0 +0 +0 +0 +0 +0 +0 +0 +0 +0 +0 +0 +0 +next += NULL + + + +55d4 +a1c0 +32e0 + +0 +0 +0 +0 +0 +0 +0 +0 +0 +0 +0 +0 +0 +0 +0 +9 +value += 9 + +n + +55d4 +a1c0 +32e8 + + +0 +0 +0 +0 +5 +5 +d +4 +a +1 +c +0 +3 +2 +c +0 +next + + + + + + + +Inserting moves nothing. One word changes: the next field of at +now holds the address of the new node. + diff --git a/design/mock/03-syscall-write-480.png b/design/mock/03-syscall-write-480.png new file mode 100644 index 0000000..ebaf2af Binary files /dev/null and b/design/mock/03-syscall-write-480.png differ diff --git a/design/mock/03-syscall-write.png b/design/mock/03-syscall-write.png new file mode 100644 index 0000000..b56f743 Binary files /dev/null and b/design/mock/03-syscall-write.png differ diff --git a/design/mock/03-syscall-write.svg b/design/mock/03-syscall-write.svg new file mode 100644 index 0000000..140369e --- /dev/null +++ b/design/mock/03-syscall-write.svg @@ -0,0 +1,293 @@ + + + + +System calls +write(1, msg, 14) +kernel + +memory + +cpu + +source + + + + + + +hello.c + + +11 +write( +1 +, msg, +14 +); + +mov +eax, 1 +mov +edi, 1 +lea +rsi, [msg] +mov +edx, 14 + + +syscall +12 +return +0 +; + + + + +registers +x86-64 + + +0 +0 +0 +0 +5 +5 +d +4 +a +1 +c +0 +1 +1 +5 +c +rip + + +0 +0 +0 +0 +0 +0 +0 +0 +0 +0 +0 +0 +0 +0 +0 +1 +rax + + +0 +0 +0 +0 +0 +0 +0 +0 +0 +0 +0 +0 +0 +0 +0 +1 +rdi + + +0 +0 +0 +0 +5 +5 +d +4 +a +1 +c +0 +2 +0 +0 +4 +rsi + + +0 +0 +0 +0 +0 +0 +0 +0 +0 +0 +0 +0 +0 +0 +0 +e +rdx +which call +1st +2nd +3rd +four registers, read by the kernel + + + + +memory +read-only data +a1c0 +2004 + +H +48 + +e +65 + +l +6c + +l +6c + +o +6f + +, +2c + + +20 + +w +77 +a1c0 +200c + +o +6f + +r +72 + +l +6c + +d +64 + +! +21 + +\n +0a + +00 + + + + +14 bytes, read by the kernel +user +kernel + + + +syscall + + + +the bytes +what it runs + + +tty_write + +vfs_write + +ksys_write +write +system call 1 + +rdi +fd +1 +the terminal + +rsi +buf +5 +5 +d +4 +a +1 +c +0 +2 +0 +0 +4 + +rdx +count +14 +bytes + +rax +returns +not yet +the terminal's buffer + + +H + + +e + + +l + + +l + + +o + + +, + + + + + +w + + +o + + + +9 of 14 copied +The program cannot reach the terminal. It leaves four numbers +in registers, and syscall hands them to the kernel. + diff --git a/design/mock/04-malloc-glibc-musl-480.png b/design/mock/04-malloc-glibc-musl-480.png new file mode 100644 index 0000000..d69374f Binary files /dev/null and b/design/mock/04-malloc-glibc-musl-480.png differ diff --git a/design/mock/04-malloc-glibc-musl.png b/design/mock/04-malloc-glibc-musl.png new file mode 100644 index 0000000..8d392dd Binary files /dev/null and b/design/mock/04-malloc-glibc-musl.png differ diff --git a/design/mock/04-malloc-glibc-musl.svg b/design/mock/04-malloc-glibc-musl.svg new file mode 100644 index 0000000..a638d28 --- /dev/null +++ b/design/mock/04-malloc-glibc-musl.svg @@ -0,0 +1,273 @@ + + + +malloc: glibc and musl +heap.c:9 free(b); +kernel + +memory + +cpu + +source + + + + + + +glibc 2.39 +ptmalloc +the heap: one run of chunks + + + + +a + + + + + + +b + + + +c + + + + +tcache +unused + +32 bytes +inside b + + +0 +0 +0 +0 +0 +0 +0 +0 +0 +0 +0 +0 +0 +0 +2 +1 +size +of this chunk + +0 +0 +0 +0 +0 +0 +0 +5 +5 +d +4 +a +1 +c +0 +3 +next +free chunk: none + +8 +f +3 +a +6 +1 +c +2 +d +0 +7 +b +4 +e +1 +9 +key +marks it freed + +0 +0 +0 +0 +0 +0 +0 +0 +0 +0 +0 +0 +0 +0 +2 +a +your old data +0x20 + +1 free +0x30 + +0 +0x40 + +0 +0x50 + +0 +0x60 + +0 +0x70 + +0 + + +its notes: a list for each size, kept in the heap itself + + + + +musl 1.2.5 +mallocng +the heap: groups of equal slots + + + +c + + + + +112-byte slots + + + +a + + + + +b + + + + + + +32-byte slots +inside b + + + +f +f +0 +0 +0 +0 +0 +0 +its tag, cleared + +0 +0 +0 +0 +0 +0 +0 +0 +0 +0 +0 +0 +0 +0 +2 +a +your old data, + +0 +0 +0 +0 +0 +0 +0 +0 +0 +0 +0 +0 +0 +0 +0 +0 +all of it untouched +can hand out + +0 + +0 + +1 + +1 + +1 + +1 + +1 + +1 + +1 + +1 +freed + +0 + +1 + +0 + +0 + +0 + +0 + +0 + +0 + +0 + +0 +a +b +one bit for each slot +its notes: one record for each group, kept apart +glibc threads its free list through the freed chunk itself. +musl flips one bit in a record it keeps apart from your data. + diff --git a/design/mock/05-memory-write-480.png b/design/mock/05-memory-write-480.png new file mode 100644 index 0000000..37f6caf Binary files /dev/null and b/design/mock/05-memory-write-480.png differ diff --git a/design/mock/05-memory-write.png b/design/mock/05-memory-write.png new file mode 100644 index 0000000..370aa82 Binary files /dev/null and b/design/mock/05-memory-write.png differ diff --git a/design/mock/05-memory-write.svg b/design/mock/05-memory-write.svg new file mode 100644 index 0000000..2d0d264 --- /dev/null +++ b/design/mock/05-memory-write.svg @@ -0,0 +1,401 @@ + + + +Where a pointer lives +hello.c:8 +kernel + +memory + +cpu + +source + + + + + + +hello.c + +7 +char +buf[ +16 +] = +"Hello, world!\n" +; + + +8 +char +*p = buf; + +lea +rax, [rbp-0x20] + + +mov +[rbp-0x8], rax +9 +write( +1 +, p, +14 +); +10 +return +0 +; + + + + +registers +x86-64 + + +0 +0 +0 +0 +5 +5 +d +4 +a +1 +c +0 +1 +1 +6 +d +rip + + +0 +0 +0 +0 +7 +f +f +d +3 +a +2 +c +1 +e +4 +0 +rax +0 +0 +0 +0 +0 +0 +0 +0 +0 +0 +0 +0 +0 +0 +0 +1 +rdi +0 +0 +0 +0 +7 +f +f +d +3 +a +2 +c +1 +e +3 +0 +rsp +0 +0 +0 +0 +7 +f +f +d +3 +a +2 +c +1 +e +6 +0 +rbp + + + + +stack +from 7ffd 3a2c 1e30 · low addresses on top ++0 ++1 ++2 ++3 ++4 ++5 ++6 ++7 +as text + +main + +3a2c +1e30 + + + + + + + + + + + + + + + + +3a2c +1e38 + + + + + + + + + + + + + + + + +3a2c +1e40 + +48 + +65 + +6c + +6c + +6f + +2c + +20 + +77 +H +e +l +l +o +, + +w +buf +3a2c +1e48 + +6f + +72 + +6c + +64 + +21 + +0a + +00 + +00 +o +r +l +d +! +· +· +· +3a2c +1e50 + +00 + +3f + +9a + +c1 + +77 + +d2 + +8e + +5b +· +? +· +· +w +· +· +[ +canary +3a2c +1e58 + +40 + +1e + +2c + +3a + +fd + +7f + +00 + +00 +@ +· +, +: +· +· +· +· +p +3a2c +1e60 + +00 + +1f + +2c + +3a + +fd + +7f + +00 + +00 +· +· +, +: +· +· +· +· +saved rbp +3a2c +1e68 + +90 + +9d + +22 + +5e + +3c + +7f + +00 + +00 +· +· +" +^ +< +· +· +· +return to + + +__libc_start_call_main + + + + + + +rsp + + + +rbp + + + +the same eight bytes, low byte first, as one number + +0 +0 +0 +0 +7 +f +f +d +3 +a +2 +c +1 +e +4 +0 + += where +buf +starts +The pointer p is eight ordinary bytes on the stack. +Read as one number, they are the address of buf. + diff --git a/design/mock/06-title-legend-480.png b/design/mock/06-title-legend-480.png new file mode 100644 index 0000000..7daa823 Binary files /dev/null and b/design/mock/06-title-legend-480.png differ diff --git a/design/mock/06-title-legend.png b/design/mock/06-title-legend.png new file mode 100644 index 0000000..696b59a Binary files /dev/null and b/design/mock/06-title-legend.png differ diff --git a/design/mock/06-title-legend.svg b/design/mock/06-title-legend.svg new file mode 100644 index 0000000..8e57394 --- /dev/null +++ b/design/mock/06-title-legend.svg @@ -0,0 +1,79 @@ + + + + +How programs really run +part 3 +Where does malloc +keep its notes? +glibc and musl, one free() at a time + + + + +legend +the same marks in every picture + +rip +current +executing now + +2a + +00 +written +by this step + + +2a + + +00 +changed +a moment ago + + +2a + + +00 +read +by this step + + + + +pointer +an address + + +moving +in transit + + +allocated +handed out + + +freed +handed back + + + + +not seen +never observed + +sys +kernel +the other side + + +SEGV +fault +signal or error + + +one object +in every view + diff --git a/design/mock/07-sort-swap-480.png b/design/mock/07-sort-swap-480.png new file mode 100644 index 0000000..a2b75f0 Binary files /dev/null and b/design/mock/07-sort-swap-480.png differ diff --git a/design/mock/07-sort-swap.png b/design/mock/07-sort-swap.png new file mode 100644 index 0000000..e6127b2 Binary files /dev/null and b/design/mock/07-sort-swap.png differ diff --git a/design/mock/07-sort-swap.svg b/design/mock/07-sort-swap.svg new file mode 100644 index 0000000..6e866e5 --- /dev/null +++ b/design/mock/07-sort-swap.svg @@ -0,0 +1,129 @@ + + + +Insertion sort +sort.c:6 +kernel + +memory + +cpu + +source + + + + + + +a +int a[8] + +0 +4 + +1 +9 + +2 +17 + + +3 + +j-1 +31 + + +4 + +j +12 + + +5 + +i +26 + +6 +5 + +7 +20 + +31 > 12 +so they trade places + + + + +31 + + + + +12 + + + + +sort.c +3 +for +( +int +i = +1 +; i < n; i++) { +4 +int +j = i; + +5 +while +(j > +0 +&& a[j-1] > a[j]) { + + +6 +swap(&a[j-1], &a[j]); + +7 +j--; + + + + +locals +of sort() +i +int +5 +j +int + + +4 +n +int +8 +a +int * +7 +f +f +d +3 +a +2 +c +1 +e +2 +0 +where a[0] is +While the one on the left is larger, they trade places, +and j follows the smaller value down. + diff --git a/design/mock/08-far-view-480.png b/design/mock/08-far-view-480.png new file mode 100644 index 0000000..d182a84 Binary files /dev/null and b/design/mock/08-far-view-480.png differ diff --git a/design/mock/08-far-view.png b/design/mock/08-far-view.png new file mode 100644 index 0000000..e148dd4 Binary files /dev/null and b/design/mock/08-far-view.png differ diff --git a/design/mock/08-far-view.svg b/design/mock/08-far-view.svg new file mode 100644 index 0000000..d97688f --- /dev/null +++ b/design/mock/08-far-view.svg @@ -0,0 +1,329 @@ + + + +A process, from far away +hello +kernel + +memory + +cpu + +source + + + + + + +address space +one square a page of 4096 bytes · low addresses on top +55d4 +a1c0 +1000 + +r + + +x +hello +4K + +55d4 +a1c0 +2000 + +r + + +hello +4K + +55d4 +a1c0 +3000 + +r + +w + +hello +8K + + + +55d4 +a2e5 +f000 + +r + +w + +heap +132K + + + + + + + + + + + + + + + + + + + +7f3c +5e20 +0000 + +r + + +x +libc.so.6 +2.1M + + + + + + + + + + + + + + + + + + + +7f3c +5e5c +2000 + +r + + +x +ld.so +216K + + + + + + + + + + + + + + + + + + + +7ffd +3a2a +2000 + +r + +w + +stack +132K + + + + + + + + + + + + + + + + + + + +7ffd +3a3d +1000 + +r + + +x +vdso +8K + + + +ffff 8000 0000 +kernel +the upper half of every address space + + + + +one page of the stack +4096 bytes + + + +3640 bytes above +3a2c +1e38 + + + + + + + + + + + + + + + + +3a2c +1e40 + +48 + +65 + +6c + +6c + +6f + +2c + +20 + +77 +3a2c +1e48 + +6f + +72 + +6c + +64 + +21 + +0a + +00 + +00 +3a2c +1e50 + +00 + +3f + +9a + +c1 + +77 + +d2 + +8e + +5b +3a2c +1e58 + +40 + +1e + +2c + +3a + +fd + +7f + +00 + +00 + + + +416 below + + + + + + +system calls +time runs right · width is time spent in the kernel + +user +kernel + +execve + + + +openat + + + + + +mprotect + + + + + +write + +exit_group + +the dynamic loader + +main + +Before main runs a single line, the loader has already +asked the kernel for memory a dozen times. + diff --git a/design/mock/gen.py b/design/mock/gen.py new file mode 100644 index 0000000..6a9733e --- /dev/null +++ b/design/mock/gen.py @@ -0,0 +1,1304 @@ +#!/usr/bin/env python3 +"""Mock frames for the canim design system (see ../README.md). + + python3 gen.py [n ...] # writes NN-name.svg next to this file + for f in 0?-*.svg; do resvg $f ${f%.svg}.png; resvg -w 480 $f ${f%.svg}-480.png; done + +The numbers here mirror src/anim/theme.zig; that file is the truth. +Needs the Go fonts (ttf-go) where resvg can find them; fontTools is optional. +""" +import math +import os + +W, H = 1920, 1080 +HERE = os.path.dirname(os.path.abspath(__file__)) + +# ---- tokens (mirror of theme.zig) ----------------------------------------- +PAGE, RAISED, RULE = "#0a1030", "#16245f", "#3a4a8a" +VELLUM, BRIGHT, DIM, FAINT = "#eee6d2", "#fff8e8", "#9aa6d9", "#6a7ab8" +INK = "#050a24" # letters on a bright fill +GOLD, VERM, READ, PTR, ALLOC = "#e8c46a", "#ff6a4a", "#6fd6e6", "#d59cf5", "#7fdc9a" +# An accent's ember: its hold state. Chosen, not alpha-blended: gold over lapis blends to grey. +EMBER = {GOLD: "#4a3d1c", VERM: "#5a2218", READ: "#1c4652", PTR: "#45305a", ALLOC: "#1f4a33"} +TRAIL = ["#ae9350", "#746235", "#463b20"] # gold, cooling: newest first +KERNEL, KERNEL_RULE, KERNEL_DIM, KERNEL_HELD = "#eee6d2", "#b9ad8e", "#4a5488", "#f3b9a0" +KW, LIT, COMMENT = "#c0dcff", "#c8f0d8", "#9aa6d9" +OCHRE, TEAL = "#8a5e0c", "#17707c" # the first two pigments: identity + +MX, MY = 64, 48 # margins +COL, GUT, VGAP = 120, 32, 24 +HEAD_Y, HEAD_H = 48, 48 +STAGE_Y, STAGE_H = 120, 768 +CAP_Y, CAP_H = 912, 120 +TAG_H = 48 +CELL = 48 # byte cell pitch; drawn 46 +ROW = 60 # memory row pitch +LH = 48 # code line, register row +ADV = 0.6 # Go Mono advance, em +SM, DATA, VAL, HERO = 25, 30, 35, 60 # mono sizes: multiples of 5, so an advance is whole units + + +def colx(i): + return MX + i * (COL + GUT) + + +def span(n): + return n * COL + (n - 1) * GUT + + +def mix(fg, bg, a): + f, b = fg.lstrip("#"), bg.lstrip("#") + return "#" + "".join("%02x" % round(int(f[i:i + 2], 16) * a + int(b[i:i + 2], 16) * (1 - a)) for i in (0, 2, 4)) + + +def esc(s): + return s.replace("&", "&").replace("<", "<").replace(">", ">") + + +FONTS = { + "mono": ("Go Mono", "normal", "normal"), + "monob": ("Go Mono", "bold", "normal"), + "monoi": ("Go Mono", "normal", "italic"), + "sans": ("Go", "normal", "normal"), + "sansm": ("Go Medium", "normal", "normal"), + "sansb": ("Go", "bold", "normal"), +} + + +def mw(s, size): + return len(s) * round(ADV * size) + + +try: + from fontTools.ttLib import TTFont + _F = {} + + def tw(s, size, font="sans"): + """Width of proportional text, from the font's own metrics.""" + if font.startswith("mono"): + return mw(s, size) + name = {"sans": "Go-Regular", "sansm": "Go-Medium", "sansb": "Go-Bold"}[font] + if name not in _F: + f = TTFont(f"/usr/share/fonts/go/{name}.ttf") + _F[name] = (f.getBestCmap(), f["hmtx"], f["head"].unitsPerEm) + cmap, hmtx, upm = _F[name] + return sum(hmtx[cmap.get(ord(c), cmap[ord("n")])][0] for c in s) * size / upm +except ImportError: + def tw(s, size, font="sans"): + return mw(s, size) if font.startswith("mono") else len(s) * size * 0.52 + + +class Svg: + def __init__(self): + self.o = [f'', + # Freed: a coarse hatch (5 wide on a 20 pitch; anything finer is mush at 480p). + '' + f'' + '' + f'', + f''] + + def rect(self, x, y, w, h, fill="none", stroke=None, sw=2, dash=None): + a = f'") + + def frame(self, x, y, w, h, stroke, sw=2, dash=None): + """A stroke drawn wholly inside the rect.""" + self.rect(x + sw / 2, y + sw / 2, w - sw, h - sw, "none", stroke, sw, dash) + + def line(self, x1, y1, x2, y2, stroke=RULE, sw=2): + self.o.append(f'') + + def path(self, d, stroke=None, sw=3, fill="none", dash=None, join="round", cap="butt"): + a = f'") + + def circle(self, cx, cy, r, fill="none", stroke=None, sw=3): + a = f'") + + def t(self, x, y, s, size=DATA, fill=VELLUM, font="mono", anchor="start"): + """One run of text; y is the baseline. Mono is laid a character at a time on its + whole-unit advance, as the renderer does.""" + fam, wt, st = FONTS[font] + a = f' font-family="{fam}" font-size="{size}" fill="{fill}" xml:space="preserve"' + if wt != "normal": + a += f' font-weight="{wt}"' + if st != "normal": + a += f' font-style="{st}"' + if font.startswith("mono"): + adv = round(ADV * size) + if anchor == "middle": + x -= len(s) * adv / 2 + elif anchor == "end": + x -= len(s) * adv + xs = " ".join(f"{x + i * adv:.1f}" for i in range(len(s))) + self.o.append(f'{esc(s)}') + return + if anchor != "start": + a += f' text-anchor="{anchor}"' + self.o.append(f'{esc(s)}') + + def tc(self, x, y, w, h, s, size=DATA, fill=VELLUM, font="mono"): + """Text centred in a box, on its cap height.""" + self.t(x + w / 2, y + h / 2 + 0.36 * size, s, size, fill, font, "middle") + + def rich(self, x, y, parts, size=40): + """Proportional text with inline mono runs: [(text, fill[, font])], one so it flows.""" + a = f'' + for p in parts: + fam, wt, st = FONTS[p[2] if len(p) > 2 else "sans"] + sz = f' font-size="{round(size * 0.875)}"' if fam == "Go Mono" else "" + a += f'{esc(p[0])}' + self.o.append(a + "") + + def save(self, name): + self.o.append("") + open(os.path.join(HERE, name + ".svg"), "w").write("\n".join(self.o) + "\n") + + +def base(y, h, size): + """Baseline that centres cap-height text of `size` in a box at y, h tall.""" + return y + h / 2 + 0.36 * size + + +# ---- lines ---------------------------------------------------------------- +def head_tri(g, x2, y2, ux, uy, color, hl, hw): + bx, by = x2 - ux * hl, y2 - uy * hl + nx, ny = -uy * hw / 2, ux * hw / 2 + g.path(f"M{x2:.1f},{y2:.1f} L{bx + nx:.1f},{by + ny:.1f} L{bx - nx:.1f},{by - ny:.1f} Z", fill=color) + + +def arrow(g, pts, color=PTR, sw=4, r=12, head=True, dash=None, hl=18, hw=16): + """A polyline with filleted elbows and a filled head on its last point.""" + pts = [tuple(map(float, p)) for p in pts] + (x1, y1), (x2, y2) = pts[-2], pts[-1] + L = math.hypot(x2 - x1, y2 - y1) + ux, uy = (x2 - x1) / L, (y2 - y1) / L + q = pts[:-1] + [(x2 - ux * (hl - 2), y2 - uy * (hl - 2)) if head else (x2, y2)] + d = f"M{q[0][0]:.1f},{q[0][1]:.1f}" + for i in range(1, len(q) - 1): + (ax, ay), (bx, by), (cx, cy) = q[i - 1], q[i], q[i + 1] + la, lb = math.hypot(bx - ax, by - ay), math.hypot(cx - bx, cy - by) + rr = min(r, la / 2, lb / 2) + d += (f" L{bx - (bx - ax) / la * rr:.1f},{by - (by - ay) / la * rr:.1f}" + f" Q{bx:.1f},{by:.1f} {bx + (cx - bx) / lb * rr:.1f},{by + (cy - by) / lb * rr:.1f}") + d += f" L{q[-1][0]:.1f},{q[-1][1]:.1f}" + g.path(d, color, sw, dash=dash) + if head: + head_tri(g, x2, y2, ux, uy, color, hl, hw) + + +def flow(g, pts): + """A value in transit: bright, thinner than a pointer, gone a second after it lands.""" + arrow(g, pts, VELLUM, 3, hl=16, hw=14) + + +def wedge(g, x, y0, y1, X, Y0, Y1): + """This, magnified: two rules from a thing's corners to its enlargement's.""" + g.path(f"M{x},{y0} L{X},{Y0} M{x},{y1} L{X},{Y1}", RULE, 2) + + +def wedge_down(g, x0, x1, y, X0, X1, Y): + g.path(f"M{x0},{y} L{X0},{Y} M{x1},{y} L{X1},{Y}", RULE, 2) + + +# ---- frame furniture ------------------------------------------------------ +def panel(g, x, y, w, h, title, focus=False, right=None): + """An acme window: a tag with its box, a rule round the body. Returns the body rect.""" + g.rect(x, y, w, TAG_H, RAISED) + g.frame(x, y, w, h, DIM if focus else RULE, 2) + g.line(x, y + TAG_H, x + w, y + TAG_H, DIM if focus else RULE, 2) + if focus: + g.rect(x + 14, y + 14, 20, 20, GOLD) + else: + g.frame(x + 14, y + 14, 20, 20, FAINT, 2) + g.t(x + 48, y + 34, title, 28, VELLUM if focus else DIM, "sansm") + if right: + g.t(x + w - 16, y + 32, right, 22, FAINT, "sans", "end") + return x, y + TAG_H, w, h - TAG_H + + +LEVELS = ["source", "cpu", "memory", "kernel"] + + +def head(g, title, lit=(), focus=None, where=None): + """Running head: what the video is on, where the program is, and the level rail.""" + g.t(MX, HEAD_Y + 33, title, 28, DIM, "sansm") + if where: + g.t(MX + tw(title, 28, "sansm") + 36, HEAD_Y + 33, where, SM, FAINT, "mono") + x = W - MX + for name in reversed(LEVELS): + on, cur = name in lit, name == focus + x -= tw(name, 22, "sansm") + 2 + g.t(x, HEAD_Y + 32, name, 22, VELLUM if cur else (DIM if on else FAINT), "sansm") + x -= 24 + if cur: + g.rect(x, HEAD_Y + 17, 16, 16, GOLD) + elif on: + g.rect(x, HEAD_Y + 17, 16, 16, DIM) + else: + g.frame(x, HEAD_Y + 17, 16, 16, RULE, 2) + x -= 36 + g.line(MX, HEAD_Y + HEAD_H + 8, W - MX, HEAD_Y + HEAD_H + 8, RULE, 2) + + +def caption(g, lines, ink=VELLUM): + """One or two lines, ranged left on the margin. Each line: [(text[, font])].""" + y = CAP_Y + (52 if len(lines) == 2 else 78) + for parts in lines: + g.rich(MX, y, [(p[0], ink) + tuple(p[1:]) for p in parts], 40) + y += 54 + + +def plaque(g, x, y, s, size=SM, ink=VELLUM, fill=RAISED, stroke=None, h=40, pad=12, font="mono"): + w = tw(s, size, font) + 2 * pad + if fill != "none": + g.rect(x, y, w, h, fill) + if stroke: + g.frame(x, y, w, h, stroke, 2) + g.t(x + pad, base(y, h, size), s, size, ink, font) + return w + + +def elide(g, x, y, label="", h=24): + """Bytes (or lines) that are there and not shown: three squares and what they are.""" + for i in range(3): + g.rect(x + i * 14, y + h / 2 - 3, 6, 6, FAINT) + if label: + g.t(x + 56, y + h / 2 + 8, label, 22, FAINT, "sans") + + +# ---- numbers -------------------------------------------------------------- +def hexw(n, size=DATA): + adv = round(ADV * size) + return n * adv + (n // 4 - 1) * round(adv / 2) + + +def hexgroups(g, x, y, digits, size=DATA, lead=FAINT, fill=VELLUM, font="mono", right=False, all_fill=None): + """Hex in fours, half an advance apart; leading zeros in `lead`.""" + adv = round(ADV * size) + if right: + x -= hexw(len(digits), size) + nz = len(digits) - len(digits.lstrip("0")) + if nz == len(digits): + nz -= 1 + for i in range(0, len(digits), 4): + for k in range(i, min(i + 4, len(digits))): + g.t(x + (k - i) * adv, y, digits[k], size, all_fill or (lead if k < nz else fill), font) + x += 4 * adv + round(adv / 2) + + +def address(g, x, y, addr, h=CELL - 2, digits=12): + """An address gutter: only the end that changes row to row is in full ink. + digits=8 drops the top group where a panel is narrow (its tag names the region).""" + a = ("%012x" % addr)[12 - digits:] + n = digits // 4 + for i in range(n): + g.t(x + i * (4 * 15 + 8), base(y, h, SM), a[4 * i:4 * i + 4], SM, VELLUM if i == n - 1 else FAINT, "mono") + + +# ---- cells ---------------------------------------------------------------- +def space_glyph(g, cx, by, color=VELLUM): + """A visible space: Go Mono has no U+2423, and a drawn one is the same everywhere.""" + g.path(f"M{cx - 8},{by - 8} v8 h16 v-8", color, 3, join="miter") + + +def byte(g, x, y, v, state="plain"): + """One byte at pitch CELL. v: two hex digits, or None for never observed.""" + w = CELL - 2 + if v is None: + g.rect(x + 12, y + 20, 6, 6, FAINT) + g.rect(x + 28, y + 20, 6, 6, FAINT) + return + fill, ink, font = RAISED, VELLUM, "mono" + if v == "00" and state == "plain": + ink = FAINT + if state == "write": + fill, ink, font = VERM, INK, "monob" + elif state == "held": + fill = EMBER[VERM] + elif state == "read": + fill = EMBER[READ] + g.rect(x, y, w, w, fill) + if state == "held": + g.rect(x, y + w - 6, w, 6, VERM) + if state == "read": + g.frame(x, y, w, w, READ, 3) + g.tc(x, y, w, w, v, DATA, ink, font) + + +def word(g, x, y, digits, state="plain", nbytes=8): + """Bytes read as one number, on the footprint of the byte cells it is made of.""" + w, h = nbytes * CELL - 2, CELL - 2 + fill, all_fill, font = RAISED, None, "mono" + if state == "write": + fill, all_fill, font = VERM, INK, "monob" + elif state == "held": + fill = EMBER[VERM] + elif state == "read": + fill = EMBER[READ] + g.rect(x, y, w, h, fill) + if state == "held": + g.rect(x, y + h - 6, w, 6, VERM) + if state == "read": + g.frame(x, y, w, h, READ, 3) + hexgroups(g, x + (w - hexw(len(digits))) / 2, base(y, h, DATA), digits, all_fill=all_fill, font=font) + return w + + +def ptr_frame(g, x, y, nbytes=8): + """These bytes are one pointer.""" + g.frame(x - 6, y - 6, nbytes * CELL - 2 + 12, CELL - 2 + 12, PTR, 4) + + +def regmark(g, xr, y, name, fill=RAISED, rows=1): + """A register or pointer variable holding this row's address: left of the gutter, pointing in. + With a pigment, a spine runs down the rows of its object.""" + w = mw(name, SM) + 20 + x = xr - w - 16 + g.rect(x, y + 3, w, 40, fill) + if fill == RAISED: + g.frame(x, y + 3, w, 40, PTR, 2) + g.t(x + 10, base(y, CELL - 2, SM), name, SM, VELLUM, "mono") + if fill == RAISED: + g.path(f"M{xr},{y + 23} l-14,-9 v18 Z", fill=PTR) + else: + g.rect(xr - 12, y, 6, (rows - 1) * ROW + CELL - 2, fill) + + +# ---- components ----------------------------------------------------------- +def code(g, x, y, w, lines, cur=None, trail=(), unfold=None): + """Source lines: (number, [(text, class)]) with class in none|kw|lit|com. + cur: the current line. trail: recently executed, newest first. + unfold: (line, [(mnemonic, operands)], current instruction). Returns {line: baseline}.""" + ink = {"none": VELLUM, "kw": KW, "lit": LIT, "com": COMMENT} + fnt = {"none": "mono", "kw": "monob", "lit": "mono", "com": "monoi"} + gut = 3 * 18 + 16 + ys = {} + for num, parts in lines: + b = base(y, LH, DATA) + ys[num] = b + if num == cur: + g.rect(x, y + 2, w, LH - 4, EMBER[GOLD]) + g.rect(x, y + 2, gut + 4, LH - 4, GOLD) + g.t(x + gut - 6, b, str(num), DATA, INK, "monob", "end") + else: + if num in trail: + g.rect(x, y + 2, 6, LH - 4, TRAIL[min(trail.index(num), 2)]) + g.t(x + gut - 6, b, str(num), DATA, FAINT, "mono", "end") + xx = x + gut + 20 + for s, cls in parts: + if s.strip(): + g.t(xx + (len(s) - len(s.lstrip())) * 18, b, s.lstrip(), DATA, ink[cls], fnt[cls]) + xx += mw(s, DATA) + y += LH + if unfold and unfold[0] == num: + ax = x + gut + 20 + 36 + g.line(ax - 18, y + 2, ax - 18, y + len(unfold[1]) * LH - 2, RULE, 2) + for i, (op, args) in enumerate(unfold[1]): + b2 = base(y, LH, DATA) + on = i == unfold[2] + if on: + g.rect(ax - 22, y + 3, w - (ax - 22 - x), LH - 6, EMBER[GOLD]) + g.rect(ax - 22, y + 3, 8, LH - 6, GOLD) + g.t(ax, b2, op, DATA, VELLUM if on else DIM, "monob" if on else "mono") + if args: + g.t(ax + 5 * 18, b2, args, DATA, VELLUM if on else DIM, "mono") + ys[("asm", i)] = b2 + y += LH + return ys + + +def regs(g, x, y, w, rows, flags=None): + """rows: (name, 16 hex digits, state) with state in plain|write|held|read|pc. + Returns {name: row top}.""" + out = {} + vx = x + w - 18 + vw = hexw(16) + for name, val, st in rows: + b = base(y, LH, DATA) + cell = (vx - vw - 10, y + 3, vw + 20, LH - 6) + if st == "pc": + g.rect(x, y + 3, w, LH - 6, EMBER[GOLD]) + g.rect(x, y + 3, 16 + 3 * 18 + 14, LH - 6, GOLD) + if st == "write": + g.rect(*cell, VERM) + hexgroups(g, vx, b, val, right=True, all_fill=INK, font="monob") + else: + if st == "held": + g.rect(*cell, EMBER[VERM]) + g.rect(cell[0], cell[1] + cell[3] - 6, cell[2], 6, VERM) + if st == "read": + g.rect(*cell, EMBER[READ]) + g.frame(*cell, READ, 3) + hexgroups(g, vx, b, val, right=True) + g.t(x + 18, b, name, DATA, INK if st == "pc" else DIM, "monob" if st == "pc" else "mono") + out[name] = y + y += LH + if flags: + y += 10 + fx = x + 18 + for name, on, changed in flags: + if on: + g.rect(fx, y, 60, 36, RAISED) + g.frame(fx, y, 60, 36, VELLUM, 3) + g.tc(fx, y, 60, 36, name, SM, BRIGHT, "monob") + else: + g.frame(fx, y, 60, 36, RULE, 2) + g.tc(fx, y, 60, 36, name, SM, FAINT, "mono") + if changed: + g.rect(fx, y + 40, 60, 6, VERM) + fx += 72 + return out + + +def cards(g, x, y, w, items, h=56, gap=12, on_kernel=False): + """A call stack, newest on top. items: (name, args, where, current).""" + ink, dim = (PAGE, KERNEL_DIM) if on_kernel else (VELLUM, DIM) + for name, args, where, cur in items: + if on_kernel: + if cur: + g.rect(x, y, w, h, GOLD) + g.frame(x, y, w, h, PAGE, 2) + else: + g.rect(x, y, w, h, EMBER[GOLD] if cur else RAISED) + g.rect(x, y, 12, h, GOLD if cur else RULE) + b = base(y, h, DATA) + g.t(x + 28, b, name, DATA, ink, "monob" if cur else "mono") + if args: + g.t(x + 28 + mw(name, DATA) + 18, b, args, DATA, ink if cur else dim, "mono") + if where: + g.t(x + w - 14, base(y, h, SM), where, SM, dim if cur or on_kernel else FAINT, "mono", "end") + y += h + gap + + +def node(g, x, y, value, state="plain", body=RAISED, null=False, w=180, h=72): + """A list node: [ value | next ]. Returns the point its pointer leaves from.""" + pw = 72 + g.rect(x, y, w - pw, h, body) + g.t(x + (w - pw) / 2, base(y, h, VAL), str(value), VAL, VELLUM, "mono", "middle") + nx = x + w - pw + g.rect(nx + 2, y, pw - 2, h, {"write": VERM, "held": EMBER[VERM]}.get(state, mix(body, PAGE, 0.55))) + if state == "held": + g.rect(nx + 2, y + h - 6, pw - 2, 6, VERM) + cx, cy = nx + pw / 2 + 1, y + h / 2 + if null: + g.path(f"M{nx + 16},{y + h - 14} L{nx + pw - 14},{y + 14}", DIM, 3) + else: + g.rect(cx - 7, cy - 7, 14, 14, INK if state == "write" else PTR) + return cx, cy + + +def chunk(g, x, y, w, h, kind, name=None, hdr=32, writes=(), name_x=None): + """A block of the heap, to scale. kind: used | free | avail | meta. + hdr: width of the allocator's own bytes at its start. writes: (offset, width) struck.""" + if kind == "used": + g.rect(x, y, w, h, EMBER[ALLOC]) + g.frame(x, y, w, h, ALLOC, 3) + elif kind == "free": + g.rect(x, y, w, h, "url(#hatch)") + g.frame(x, y, w, h, DIM, 3, dash="12 8") + elif kind == "avail": + g.frame(x, y, w, h, RULE, 2) + elif kind == "meta": + g.rect(x, y, w, h, RULE) + if hdr and kind in ("used", "free"): + g.rect(x + 3, y + 3, hdr - 3, h - 6, RULE) + for off, ww_ in writes: + g.rect(x + off, y + 3, ww_, h - 6, VERM) + if name: + nx = name_x if name_x is not None else (w + (hdr if kind in ("used", "free") else 0)) / 2 + if kind == "free": + g.rect(x + nx - 16, y + h / 2 - 22, 32, 44, PAGE) + g.t(x + nx, base(y, h, VAL), name, VAL, VELLUM, "mono", "middle") + + +K, N, L = "kw", "none", "lit" + + +# ---- frame 1: recursive fib, four views ----------------------------------- +def frame1(): + g = Svg() + head(g, "Recursion", lit=("source", "cpu"), focus="source", where="fib(5)") + + bx, by, bw, bh = panel(g, colx(0), STAGE_Y, span(5), STAGE_H, "fib.c", focus=True) + lines = [ + (1, [("#include", K), (" ", L)]), + (2, []), + (3, [("long", K), (" fib(", N), ("long", K), (" n) {", N)]), + (4, [(" ", N), ("if", K), (" (n < ", N), ("2", L), (")", N)]), + (5, [(" ", N), ("return", K), (" n;", N)]), + (6, [(" ", N), ("return", K), (" fib(n-", N), ("1", L), (") + fib(n-", N), ("2", L), (");", N)]), + (7, [("}", N)]), + (8, []), + (9, [("int", K), (" main(", N), ("void", K), (") {", N)]), + (10, [(" printf(", N), ('"%ld\\n"', L), (", fib(", N), ("5", L), ("));", N)]), + (11, [(" ", N), ("return", K), (" ", N), ("0", L), (";", N)]), + (12, [("}", N)]), + ] + code(g, bx + 2, by + 16, bw - 4, lines, cur=4, trail=(3, 6)) + # what the current frame sees, at the end of its line + plaque(g, bx + 2 + 70 + 20 + mw(" if (n < 2)", DATA) + 36, by + 16 + 3 * LH + 4, "n = 1", SM, VELLUM, "none", DIM) + + # the calls so far + tx, ty, tw_, th = panel(g, colx(5), STAGE_Y, span(7), 336, "calls of fib(n)", right="each result on its call's shoulder") + Y = [ty + 42, ty + 96, ty + 150, ty + 204, ty + 258] + nodes = [ # id, n, x, level, parent, state, result + ("r", 5, 1340, 0, None, "active", None), + ("a", 4, 1100, 1, "r", "done", 3), ("b", 3, 1600, 1, "r", "active", None), + ("aa", 3, 980, 2, "a", "done", 2), ("ab", 2, 1220, 2, "a", "done", 1), ("ba", 2, 1520, 2, "b", "active", None), + ("aaa", 2, 916, 3, "aa", "done", 1), ("aab", 1, 1044, 3, "aa", "done", 1), + ("aba", 1, 1176, 3, "ab", "done", 1), ("abb", 0, 1264, 3, "ab", "done", 0), + ("baa", 1, 1476, 3, "ba", "current", None), + ("aaaa", 1, 880, 4, "aaa", "done", 1), ("aaab", 0, 952, 4, "aaa", "done", 0), + ] + pos = {i: (x, Y[l]) for i, n, x, l, p, s, r in nodes} + for i, n, x, l, p, s, r in nodes: + if p: + live = s in ("active", "current") + g.line(*pos[p], x, Y[l], VELLUM if live else RULE, 4 if live else 3) + R = 24 + for i, n, x, l, p, s, r in nodes: + y = Y[l] + if s == "current": + g.circle(x, y, R, GOLD) + g.t(x, y + 0.36 * DATA, str(n), DATA, INK, "monob", "middle") + elif s == "active": + g.circle(x, y, R - 2, PAGE, VELLUM, 4) + g.t(x, y + 0.36 * DATA, str(n), DATA, VELLUM, "mono", "middle") + else: + g.circle(x, y, R, RAISED) + g.t(x, y + 0.36 * DATA, str(n), DATA, DIM, "mono", "middle") + g.rect(x + 14, y - 34, 28, 28, PAGE) + g.frame(x + 14, y - 34, 28, 28, FAINT, 2) + g.t(x + 28, y - 20 + 0.36 * SM, str(r), SM, VELLUM, "mono", "middle") + + # the stack of calls + sx, sy, sw, sh = panel(g, colx(5), STAGE_Y + 336 + VGAP, span(3), 408, "call stack", right="newest on top") + cards(g, sx + 14, sy + 16, sw - 28, [ + ("fib", "n = 1", ":4", True), + ("fib", "n = 2", ":6", False), + ("fib", "n = 3", ":6", False), + ("fib", "n = 5", ":6", False), + ("main", "", ":10", False), + ]) + + rx, ry, rw, rh = panel(g, colx(8), STAGE_Y + 336 + VGAP, span(4), 408, "registers", right="x86-64") + regs(g, rx + 2, ry + 14, rw - 4, [ + ("rip", "000055d4a1c01141", "pc"), + ("rax", "0000000000000001", "held"), + ("rdi", "0000000000000001", "write"), + ("rsp", "00007ffd3a2c1dc0", "held"), + ("rbp", "00007ffd3a2c1de0", "plain"), + ], flags=[("CF", False, False), ("ZF", False, True), ("SF", True, True), ("OF", False, False)]) + + caption(g, [[("Four calls to ",), ("fib", "mono"), (" are still waiting, each with its own ",), ("n", "mono"), (".",)], + [("The newest one just received ",), ("1", "mono"), (" in ",), ("rdi", "mono"), (".",)]]) + g.save("01-fib-recursion") + + +# ---- frame 2: linked-list insert, nodes above the heap that holds them ---- +def frame2(): + g = Svg() + head(g, "Linked lists", lit=("source", "memory"), focus="memory", where="insert after a node") + + bx, by, bw, bh = panel(g, colx(0), STAGE_Y, span(5), STAGE_H, "list.c") + code(g, bx + 2, by + 16, bw - 4, [ + (3, [("struct", K), (" node {", N)]), + (4, [(" ", N), ("long", K), (" value;", N)]), + (5, [(" ", N), ("struct", K), (" node *next;", N)]), + (6, [("};", N)]), + ]) + elide(g, bx + 2 + 70 + 20, by + 16 + 4 * LH + 8) + y2 = by + 16 + 4 * LH + 40 + code(g, bx + 2, y2, bw - 4, [ + (21, [("n = malloc(", N), ("sizeof", K), (" *n);", N)]), + (22, [("n->value = v;", N)]), + (23, [("n->next = at->next;", N)]), + (24, [("at->next = n;", N)]), + (25, [("return", K), (" n;", N)]), + ], cur=24, trail=(23, 22)) + # locals: what the names hold right now + ly = y2 + 5 * LH + 40 + g.line(bx + 20, ly - 20, bx + bw - 20, ly - 20, RULE, 2) + g.t(bx + 22, ly + 10, "locals", 22, FAINT, "sansm") + for i, (name, pig, val, note) in enumerate((("at", OCHRE, "000055d4a1c032a0", "node 7"), ("n", TEAL, "000055d4a1c032e0", "node 9"), ("v", None, None, "9"))): + y = ly + 28 + i * 52 + if pig: + g.rect(bx + 20, y, 12, 46, pig) + g.t(bx + 48, base(y, 46, DATA), name, DATA, VELLUM, "mono") + if val: + hexgroups(g, bx + 118, base(y, 46, DATA), val) + g.t(bx + 118 + hexw(16) + 24, base(y, 46, 28) - 1, note, 28, DIM, "sans") + else: + g.t(bx + 118, base(y, 46, DATA), note, DATA, VELLUM, "mono") + + # the list, as the program thinks of it + lx, ly_, lw, lh = panel(g, colx(5), STAGE_Y, span(7), 240, "the list", right="what the code means") + y0 = ly_ + 14 + xh = lx + 36 + hw_ = plaque(g, xh, y0 + 16, "head", SM, VELLUM, "none", DIM) + n7 = (lx + 196, y0) + n12 = (lx + 640, y0) + n9 = (lx + 418, y0 + 96) + arrow(g, [(xh + hw_, y0 + 36), (n7[0] - 4, y0 + 36)]) + p7 = node(g, *n7, 7, "write", OCHRE) + p12 = node(g, *n12, 12, null=True) + p9 = node(g, *n9, 9, "held", TEAL) + # the old link on its way out; the new link; the link made a step ago + arrow(g, [(p7[0] + 14, p7[1]), (n12[0] - 6, p7[1])], FAINT, 3, dash="12 8", head=False) + arrow(g, [(p7[0], p7[1] + 14), (p7[0], n9[1] + 36), (n9[0] - 4, n9[1] + 36)]) + arrow(g, [(p9[0] + 14, p9[1]), (n12[0] + 54, p9[1]), (n12[0] + 54, n12[1] + 72 + 4)]) + g.t(n7[0] + 2, y0 + 72 + 30, "at", SM, VELLUM, "mono") + g.t(n9[0] + 180 + 16, n9[1] + 66, "n", SM, VELLUM, "mono") + g.t(n12[0] + 180 + 24, base(n12[1], 72, 24), "the end", 24, DIM, "sans") + + # the heap that holds it + hx, hy, hw, hh = panel(g, colx(5), STAGE_Y + 240 + VGAP, span(7), 504, "heap", focus=True, right="eight bytes a row, as one number · low addresses on top") + gx = hx + 108 + cx = gx + hexw(12, SM) + 96 + fx = cx + 8 * CELL + 18 + rows = [ + ("e", "malloc's own 16 bytes"), + (0x55d4a1c032a0, "0000000000000007", "plain", "value", "= 7", OCHRE, "at"), + (0x55d4a1c032a8, "000055d4a1c032e0", "write", "next", None, OCHRE, None), + ("e", ""), + (0x55d4a1c032c0, "000000000000000c", "plain", "value", "= 12", None, None), + (0x55d4a1c032c8, "0000000000000000", "plain", "next", "= NULL", None, None), + ("e", ""), + (0x55d4a1c032e0, "0000000000000009", "plain", "value", "= 9", TEAL, "n"), + (0x55d4a1c032e8, "000055d4a1c032c0", "held", "next", None, TEAL, None), + ] + y = hy + 10 + ry = {} + for r in rows: + if r[0] == "e": + elide(g, cx, y, r[1], 22) + y += 24 + continue + addr, digits, st, field, meaning, pig, name = r + ry[addr] = y + address(g, gx, y, addr) + word(g, cx, y, digits, st) + g.t(fx, base(y, CELL - 2, SM), field, SM, VELLUM if st == "write" else DIM, "mono") + if meaning: + g.t(fx + 6 * 15, base(y, CELL - 2, SM), meaning, SM, DIM, "mono") + if name: + regmark(g, gx - 4, y, name, pig, rows=2) + y += ROW + + # pointers, in the lane left of the words; the longest outermost + def ptr(src, dst, lane, color=PTR, dash=None, sw=4, head=True): + ys_, yd = ry[src] + 23, ry[dst] + 23 + arrow(g, [(cx - 6, ys_), (cx - lane, ys_), (cx - lane, yd), (cx - 4, yd)], color, sw, dash=dash, head=head) + ptr(0x55d4a1c032a8, 0x55d4a1c032c0, 30, FAINT, "12 8", 3, False) + ptr(0x55d4a1c032e8, 0x55d4a1c032c0, 52) + ptr(0x55d4a1c032a8, 0x55d4a1c032e0, 74) + for a in (0x55d4a1c032a8, 0x55d4a1c032e8): + ptr_frame(g, cx, ry[a]) + + caption(g, [[("Inserting moves nothing. One word changes: the ",), ("next", "mono"), (" field of ",), ("at", "mono")], + [("now holds the address of the new node.",)]]) + g.save("02-list-insert") + + +# ---- frame 3: a write() crossing from user to kernel ---------------------- +def frame3(): + g = Svg() + UH = 408 + BY = STAGE_Y + UH + 48 # the boundary: 576 + g.rect(0, BY, W, H - BY, KERNEL) + head(g, "System calls", lit=("source", "cpu", "memory", "kernel"), focus="kernel", where="write(1, msg, 14)") + + bx, by, bw, bh = panel(g, colx(0), STAGE_Y, span(4), UH, "hello.c") + asm = [("mov", "eax, 1"), ("mov", "edi, 1"), ("lea", "rsi, [msg]"), ("mov", "edx, 14"), ("syscall", "")] + code(g, bx + 2, by + 12, bw - 4, [ + (11, [("write(", N), ("1", L), (", msg, ", N), ("14", L), (");", N)]), + (12, [("return", K), (" ", N), ("0", L), (";", N)]), + ], cur=11, unfold=(11, asm, 4)) + + rx, ry, rw, rh = panel(g, colx(4), STAGE_Y, span(4), UH, "registers", right="x86-64") + rr = regs(g, rx + 2, ry + 12, rw - 4, [ + ("rip", "000055d4a1c0115c", "pc"), + ("rax", "0000000000000001", "read"), + ("rdi", "0000000000000001", "read"), + ("rsi", "000055d4a1c02004", "read"), + ("rdx", "000000000000000e", "read"), + ]) + for name, role in (("rax", "which call"), ("rdi", "1st"), ("rsi", "2nd"), ("rdx", "3rd")): + g.t(rx + 2 + 18 + 3 * 18 + 20, rr[name] + 24 + 8, role, 22, DIM, "sans") + g.t(rx + 20, rr["rdx"] + LH + 44, "four registers, read by the kernel", 24, DIM, "sans") + + mx_, my_, mw_, mh_ = panel(g, colx(8), STAGE_Y, span(4), UH, "memory", right="read-only data") + gx = mx_ + 20 + cx = gx + hexw(8, SM) + 28 + text = [("H", "48"), ("e", "65"), ("l", "6c"), ("l", "6c"), ("o", "6f"), (",", "2c"), (" ", "20"), ("w", "77"), + ("o", "6f"), ("r", "72"), ("l", "6c"), ("d", "64"), ("!", "21"), ("\\n", "0a"), (None, "00"), (None, None)] + TH = 84 # a text cell: the character over its byte + for r in range(2): + y = my_ + 36 + r * 104 + address(g, gx, y, 0x55d4a1c02004 + 8 * r, h=TH, digits=8) + for j in range(8): + ch, hx_ = text[r * 8 + j] + x = cx + j * CELL + if hx_ is None: + g.rect(x + 12, y + 39, 6, 6, FAINT) + g.rect(x + 28, y + 39, 6, 6, FAINT) + continue + rd = ch is not None + g.rect(x, y, CELL - 2, TH, EMBER[READ] if rd else RAISED) + if ch == " ": + space_glyph(g, x + 23, y + 38) + elif rd: + g.t(x + 23, y + 38, ch, DATA, VELLUM, "mono", "middle") + g.t(x + 23, y + 72, hx_, SM, DIM if rd else FAINT, "mono", "middle") + y1 = my_ + 36 + g.frame(cx - 5, y1 - 5, 8 * CELL + 8, TH + 10, READ, 3) + g.frame(cx - 5, y1 + 104 - 5, 6 * CELL + 8, TH + 10, READ, 3) + g.t(cx, y1 + 2 * 104 + 22, "14 bytes, read by the kernel", 24, DIM, "sans") + + # the boundary. The same three columns continue through it. + g.t(MX, BY - 16, "user", 28, VELLUM, "sansm") + g.t(MX, BY + 42, "kernel", 28, PAGE, "sansm") + # crossings: vellum above the line, ink below it + ax = colx(4) + span(4) / 2 + g.line(ax, STAGE_Y + UH, ax, BY, VELLUM, 6) + arrow(g, [(ax, BY), (ax, BY + 64)], PAGE, 6, hl=24, hw=24) + g.t(ax + 22, BY - 14, "syscall", SM, VELLUM, "mono") + dx = cx + 4 * CELL + g.line(dx, STAGE_Y + UH, dx, BY, READ, 6) + arrow(g, [(dx, BY), (dx, BY + 116)], PAGE, 6, hl=24, hw=24) + g.t(dx + 22, BY - 14, "the bytes", 24, VELLUM, "sans") + + # kernel, left: what it runs + g.t(MX, BY + 92, "what it runs", 24, KERNEL_DIM, "sans") + cards(g, MX, BY + 108, span(4), [ + ("tty_write", "", "", True), + ("vfs_write", "", "", False), + ("ksys_write", "", "", False), + ], on_kernel=True) + + # kernel, middle: the call, decoded + kx = colx(4) + g.t(kx, BY + 122, "write", HERO, PAGE, "monob") + g.t(kx + mw("write", HERO) + 24, BY + 122, "system call 1", 28, KERNEL_DIM, "sans") + for i, (reg, name, val, note) in enumerate((("rdi", "fd", "1", "the terminal"), ("rsi", "buf", "55d4a1c02004", ""), + ("rdx", "count", "14", "bytes"), ("rax", "returns", "", "not yet"))): + y = BY + 146 + i * 44 + g.line(kx, y, kx + span(4), y, KERNEL_RULE, 2) + b = base(y, 44, DATA) + g.t(kx, b, reg, DATA, KERNEL_DIM, "mono") + g.t(kx + 84, b - 1, name, 28, PAGE, "sansm") + vw = 0 + if len(val) > 4: + hexgroups(g, kx + 220, b, val, all_fill=PAGE) + vw = hexw(len(val)) + elif val: + g.t(kx + 220, b, val, DATA, PAGE, "mono") + vw = mw(val, DATA) + if note: + g.t(kx + 220 + (vw + 20 if val else 0), b - 1, note, 28, KERNEL_DIM, "sans") + + # kernel, right: the bytes arriving + tx = colx(8) + g.t(tx, BY + 160, "the terminal's buffer", 24, KERNEL_DIM, "sans") + chars = ["H", "e", "l", "l", "o", ",", " ", "w", "o", "r", "l", "d"] + for j in range(12): + x, y = tx + j * CELL, BY + 176 + if j < 9: + g.rect(x, y, CELL - 2, CELL - 2, VERM if j == 8 else KERNEL_HELD) + g.frame(x, y, CELL - 2, CELL - 2, PAGE, 2) + if chars[j] == " ": + space_glyph(g, x + 23, base(y, CELL - 2, DATA), INK) + else: + g.tc(x, y, CELL - 2, CELL - 2, chars[j], DATA, INK, "monob" if j == 8 else "mono") + else: + g.frame(x, y, CELL - 2, CELL - 2, KERNEL_RULE, 2) + g.t(tx, BY + 176 + 78, "9 of 14 copied", 24, KERNEL_DIM, "sans") + + caption(g, [[("The program cannot reach the terminal. It leaves four numbers",)], + [("in registers, and ",), ("syscall", "mono"), (" hands them to the kernel.",)]], PAGE) + g.save("03-syscall-write") + + +# ---- frame 4: glibc and musl malloc, side by side ------------------------- +def frame4(): + g = Svg() + head(g, "malloc: glibc and musl", lit=("source", "memory"), focus="memory", where="heap.c:9 free(b);") + S = 4 # logical units per byte, in the strips + T1, T2, T3 = 72, 288, 580 # three tiers, from the body's top, the same both sides + + def more(x, y, h): + for i in range(3): + g.rect(x + i * 14, y + h / 2 - 3, 6, 6, FAINT) + + # ---- glibc + x, y, w, h = panel(g, colx(0), STAGE_Y, span(6), STAGE_H, "glibc 2.39", right="ptmalloc") + px, pr = x + 28, x + w - 28 + g.t(px, y + 44, "the heap: one run of chunks", 24, DIM, "sans") + SH = 88 + sy = y + T1 + 26 + chunk(g, px, sy, 70, SH, "meta") + xa = px + 72 + chunk(g, xa, sy, 32 * S - 2, SH, "used", "a") + xb = xa + 32 * S + chunk(g, xb, sy, 32 * S - 2, SH, "free", "b", writes=((32, 31), (64, 31)), name_x=110) + xc = xb + 32 * S + chunk(g, xc, sy, 112 * S - 2, SH, "used", "c") + xt = xc + 112 * S + chunk(g, xt, sy, pr - xt, SH, "avail") + more(xt + 18, sy, SH) + g.t(px, sy - 14, "tcache", 22, FAINT, "sans") + g.t(pr, sy - 14, "unused", 22, FAINT, "sans", "end") + x1s = xc + 112 * S - 2 # scale, under the far end of c + g.path(f"M{x1s - 32 * S + 1},{sy + SH + 12} v16 m0,-8 H{x1s - 1} m0,-8 v16", FAINT, 3) + g.t(x1s - 32 * S - 14, sy + SH + 28, "32 bytes", 22, FAINT, "sans", "end") + + zy = y + T2 + zx = px + 86 + g.t(zx + 4 * CELL, zy - 4, "inside b", 24, DIM, "sans", "middle") + wedge_down(g, xb, xb + 32 * S - 2, sy + SH + 4, zx, zx + 8 * CELL - 2, zy + 16) + rowy = [] + for i, (d, st, f, note) in enumerate((("0000000000000021", "plain", "size", "of this chunk"), + ("000000055d4a1c03", "write", "next", "free chunk: none"), + ("8f3a61c2d07b4e19", "write", "key", "marks it freed"), + ("000000000000002a", "plain", "", "your old data"))): + yy = zy + 22 + i * ROW + rowy.append(yy) + word(g, zx, yy, d, st) + xx = zx + 8 * CELL + 18 + if f: + g.t(xx, base(yy, CELL - 2, SM), f, SM, VELLUM if st == "write" else DIM, "mono") + xx += mw(f, SM) + 14 + g.t(xx, base(yy, CELL - 2, 24), note, 24, DIM, "sans") + + ty = y + T3 + for i, (size, cnt) in enumerate((("0x20", 1), ("0x30", 0), ("0x40", 0), ("0x50", 0), ("0x60", 0), ("0x70", 0))): + bx_ = px + i * 136 + g.t(bx_ + 60, ty + CELL + 28, size, SM, DIM, "mono", "middle") + g.rect(bx_, ty, 120, CELL - 2, VERM if cnt else RAISED) + if cnt: + g.tc(bx_, ty, 120, CELL - 2, "1 free", DATA, INK, "monob") + else: + g.tc(bx_, ty, 120, CELL - 2, "0", DATA, FAINT, "mono") + arrow(g, [(px + 30, ty), (px + 30, rowy[1] + 23), (zx - 4, rowy[1] + 23)]) + g.t(px, ty + CELL + 72, "its notes: a list for each size, kept in the heap itself", 24, DIM, "sans") + + # ---- musl + x2, y2, w2, h2 = panel(g, colx(6), STAGE_Y, span(6), STAGE_H, "musl 1.2.5", right="mallocng") + qx, qr = x2 + 28, x2 + w2 - 28 + g.t(qx, y2 + 44, "the heap: groups of equal slots", 24, DIM, "sans") + SH2 = 56 + s1 = y2 + T1 - 2 + xs = qx + 64 + chunk(g, qx, s1, 62, SH2, "meta") + chunk(g, xs, s1, 112 * S - 2, SH2, "used", "c", hdr=0) + chunk(g, xs + 112 * S, s1, qr - xs - 112 * S, SH2, "avail") + more(xs + 112 * S + 18, s1, SH2) + g.t(qr, s1 - 12, "112-byte slots", 22, FAINT, "sans", "end") + s2 = s1 + SH2 + 40 + chunk(g, qx, s2, 62, SH2, "meta") + chunk(g, xs, s2, 32 * S - 2, SH2, "used", "a", hdr=0) + xb2 = xs + 32 * S + chunk(g, xb2, s2, 32 * S - 2, SH2, "free", "b", hdr=0, writes=((3, 14),)) + for i in range(2, 5): + chunk(g, xs + i * 32 * S, s2, 32 * S - 2, SH2, "avail") + more(xs + 5 * 32 * S + 14, s2, SH2) + g.t(qr, s2 - 12, "32-byte slots", 22, FAINT, "sans", "end") + + zx2 = qx + 86 + g.t(zx2 + 4 * CELL, zy - 4, "inside b", 24, DIM, "sans", "middle") + wedge_down(g, xb2, xb2 + 32 * S - 2, s2 + SH2 + 4, zx2, zx2 + 8 * CELL - 2, zy + 16) + for i, (d, st, nb, note) in enumerate((("ff000000", "held", 4, "its tag, cleared"), + ("000000000000002a", "plain", 8, "your old data,"), + ("0000000000000000", "plain", 8, "all of it untouched"))): + yy = zy + 22 + i * ROW + ww_ = word(g, zx2, yy, d, st, nb) + g.t(zx2 + ww_ + 20, base(yy, CELL - 2, 24), note, 24, DIM, "sans") + + bx0 = qx + 196 + for r, (label, bits, struck) in enumerate((("can hand out", "0011111111", None), ("freed", "0100000000", 1))): + yy = ty - 60 + r * 52 + g.t(bx0 - 20, base(yy, CELL - 2, 24), label, 24, DIM, "sans", "end") + for i, bch in enumerate(bits): + bx_ = bx0 + i * CELL + g.rect(bx_, yy, CELL - 2, CELL - 2, VERM if i == struck else RAISED) + if i == struck: + g.tc(bx_, yy, CELL - 2, CELL - 2, bch, DATA, INK, "monob") + else: + g.tc(bx_, yy, CELL - 2, CELL - 2, bch, DATA, VELLUM if bch == "1" else FAINT, "mono") + g.t(bx0 + 23, ty + CELL + 28, "a", SM, DIM, "mono", "middle") + g.t(bx0 + CELL + 23, ty + CELL + 28, "b", SM, VELLUM, "mono", "middle") + g.t(bx0 + 2 * CELL + 10, ty + CELL + 28, "one bit for each slot", 22, FAINT, "sans") + g.t(qx, ty + CELL + 72, "its notes: one record for each group, kept apart", 24, DIM, "sans") + + caption(g, [[("glibc threads its free list through the freed chunk itself.",)], + [("musl flips one bit in a record it keeps apart from your data.",)]]) + g.save("04-malloc-glibc-musl") + + +# ---- frame 5: a memory grid mid-write, with a pointer --------------------- +def frame5(): + g = Svg() + head(g, "Where a pointer lives", lit=("source", "cpu", "memory"), focus="memory", where="hello.c:8") + + sh = 384 + bx, by, bw, bh = panel(g, colx(0), STAGE_Y, span(5), sh, "hello.c") + code(g, bx + 2, by + 16, bw - 4, [ + (7, [("char", K), (" buf[", N), ("16", L), ("] = ", N), ('"Hello, world!\\n"', L), (";", N)]), + (8, [("char", K), (" *p = buf;", N)]), + (9, [("write(", N), ("1", L), (", p, ", N), ("14", L), (");", N)]), + (10, [("return", K), (" ", N), ("0", L), (";", N)]), + ], cur=8, trail=(7,), unfold=(8, [("lea", "rax, [rbp-0x20]"), ("mov", "[rbp-0x8], rax")], 1)) + + rx, ry, rw, rh = panel(g, colx(0), STAGE_Y + sh + VGAP, span(5), STAGE_H - sh - VGAP, "registers", right="x86-64") + rr = regs(g, rx + 2, ry + 14, rw - 4, [ + ("rip", "000055d4a1c0116d", "pc"), + ("rax", "00007ffd3a2c1e40", "read"), + ("rdi", "0000000000000001", "plain"), + ("rsp", "00007ffd3a2c1e30", "plain"), + ("rbp", "00007ffd3a2c1e60", "plain"), + ]) + + mx_, my_, mw_, mh_ = panel(g, colx(5), STAGE_Y, span(7), STAGE_H, "stack", focus=True, right="from 7ffd 3a2c 1e30 · low addresses on top") + gx = mx_ + 112 # gutter; register marks sit left of it + cx = gx + hexw(8, SM) + 52 # bytes + ax = cx + 8 * CELL + 22 # as text + lx = ax + 8 * 18 + 34 # names + top = my_ + 86 + for i in range(8): + g.t(cx + i * CELL + 23, top - 50, "+%d" % i, SM, FAINT, "mono", "middle") + g.t(ax, top - 50, "as text", 22, FAINT, "sansm") + # whose bytes these are + g.rect(mx_ + 18, top - 30, 12, 12, GOLD) + g.t(mx_ + 42, top - 16, "main", SM, VELLUM, "mono") + g.line(mx_ + 42 + mw("main", SM) + 16, top - 24, mx_ + mw_ - 18, top - 24, RULE, 2) + rows = [ + (0x7ffd3a2c1e30, [None] * 8, "plain", None, ""), + (0x7ffd3a2c1e38, [None] * 8, "plain", None, ""), + (0x7ffd3a2c1e40, "48 65 6c 6c 6f 2c 20 77".split(), "plain", "Hello, w", "buf"), + (0x7ffd3a2c1e48, "6f 72 6c 64 21 0a 00 00".split(), "plain", "orld!···", ""), + (0x7ffd3a2c1e50, "00 3f 9a c1 77 d2 8e 5b".split(), "plain", "·?··w··[", "canary"), + (0x7ffd3a2c1e58, "40 1e 2c 3a fd 7f 00 00".split(), "write", "@·,:····", "p"), + (0x7ffd3a2c1e60, "00 1f 2c 3a fd 7f 00 00".split(), "plain", "··,:····", "saved rbp"), + (0x7ffd3a2c1e68, "90 9d 22 5e 3c 7f 00 00".split(), "plain", "··\"^<···", "return to"), + ] + rowy = {} + for i, (addr, bs, st, asc, label) in enumerate(rows): + y = top + i * ROW + rowy[addr] = y + address(g, gx, y, addr, digits=8) + for j, v in enumerate(bs): + byte(g, cx + j * CELL, y, v, st) + if asc: + for j, ch in enumerate(asc): + g.t(ax + j * 18, base(y, CELL - 2, DATA), ch, DATA, FAINT if ch == "·" else VELLUM, "mono") + if label in ("buf", "p"): + g.t(lx, base(y, CELL - 2, DATA), label, DATA, VELLUM if st == "write" else DIM, "mono") + elif label: + g.t(lx, base(y, CELL - 2, 28), label, 28, DIM, "sans") + yb = rowy[0x7ffd3a2c1e40] + g.path(f"M{lx - 20},{yb + 2} h8 V{yb + ROW + 44} h-8", DIM, 3, join="miter") + yend = top + 8 * ROW + 2 + g.frame(mx_ + 18, yend, 12, 12, FAINT, 2) + g.t(mx_ + 42, yend + 14, "__libc_start_call_main", SM, DIM, "mono") + g.line(mx_ + 42 + mw("__libc_start_call_main", SM) + 16, yend + 6, mx_ + mw_ - 18, yend + 6, RULE, 2) + + # the pointer: the word at ...1e58 holds ...1e40 + yp = rowy[0x7ffd3a2c1e58] + ptr_frame(g, cx, yp) + lane = cx - 30 + arrow(g, [(cx - 6, yp + 23), (lane, yp + 23), (lane, yb + 23), (cx - 3, yb + 23)]) + regmark(g, gx - 6, rowy[0x7ffd3a2c1e30], "rsp") + regmark(g, gx - 6, rowy[0x7ffd3a2c1e60], "rbp") + + # the value in transit: rax to the row it is stored in + xk = colx(5) - 16 + flow(g, [(rx + rw - 14, rr["rax"] + 24), (xk, rr["rax"] + 24), (xk, yp + 23), (gx - 10, yp + 23)]) + + # the same eight bytes, read as one number + cy = yend + 46 + g.t(cx, cy + 12, "the same eight bytes, low byte first, as one number", 24, DIM, "sans", "start") + wy = cy + 34 + word(g, cx, wy, "00007ffd3a2c1e40") + ptr_frame(g, cx, wy) + g.t(cx + 8 * CELL + 22, base(wy, CELL - 2, 28), "= where ", 28, DIM, "sans") + g.t(cx + 8 * CELL + 22 + tw("= where ", 28), base(wy, CELL - 2, DATA), "buf", DATA, VELLUM, "mono") + g.t(cx + 8 * CELL + 22 + tw("= where ", 28) + 3 * 18 + 10, base(wy, CELL - 2, 28), "starts", 28, DIM, "sans") + + caption(g, [[("The pointer ",), ("p", "mono"), (" is eight ordinary bytes on the stack.",)], + [("Read as one number, they are the address of ",), ("buf", "mono"), (".",)]]) + g.save("05-memory-write") + + +# ---- frame 6: a title card and the legend --------------------------------- +def frame6(): + g = Svg() + g.rect(MX, 150, 24, 24, GOLD) + g.t(MX + 44, 172, "How programs really run", 30, DIM, "sansm") + g.t(W - MX, 172, "part 3", 30, FAINT, "sansm", "end") + g.t(MX - 4, 330, "Where does malloc", 116, BRIGHT, "sansb") + g.t(MX - 4, 458, "keep its notes?", 116, BRIGHT, "sansb") + g.rich(MX, 540, [("glibc and musl, one ", DIM), ("free()", VELLUM, "mono"), (" at a time", DIM)], 44) + + x, y, w, h = panel(g, MX, 624, W - 2 * MX, 264, "legend", right="the same marks in every picture") + EW = (w - 40) / 6 + entries = [ + ("current", "executing now", "cur"), ("written", "by this step", "write"), ("changed", "a moment ago", "held"), + ("read", "by this step", "read"), ("pointer", "an address", "ptr"), ("moving", "in transit", "flow"), + ("allocated", "handed out", "alloc"), ("freed", "handed back", "free"), ("not seen", "never observed", "unk"), + ("kernel", "the other side", "kern"), ("fault", "signal or error", "err"), ("one object", "in every view", "pig"), + ] + c = CELL - 2 + for i, (name, gloss, kind) in enumerate(entries): + ex = x + 24 + (i % 6) * EW + ey = y + 24 + (i // 6) * 96 + sx, sy = ex, ey + 10 + if kind == "cur": + g.rect(sx, sy, 94, c, GOLD) + g.tc(sx, sy, 94, c, "rip", DATA, INK, "monob") + elif kind in ("write", "held", "read"): + byte(g, sx, sy, "2a", kind) + byte(g, sx + CELL, sy, "00", kind) + elif kind == "ptr": + g.rect(sx, sy, 34, c, RAISED) + g.frame(sx - 6, sy - 6, 46, c + 12, PTR, 4) + arrow(g, [(sx + 40, sy + 23), (sx + 94, sy + 23)]) + elif kind == "flow": + flow(g, [(sx, sy + 23), (sx + 94, sy + 23)]) + elif kind == "alloc": + g.rect(sx, sy, 94, c, EMBER[ALLOC]) + g.frame(sx, sy, 94, c, ALLOC, 3) + elif kind == "free": + g.rect(sx, sy, 94, c, "url(#hatch)") + g.frame(sx, sy, 94, c, DIM, 3, dash="12 8") + elif kind == "unk": + byte(g, sx, sy, None) + byte(g, sx + CELL, sy, None) + elif kind == "kern": + g.rect(sx, sy, 94, c, KERNEL) + g.tc(sx, sy, 94, c, "sys", DATA, PAGE, "monob") + elif kind == "err": + g.rect(sx, sy, 94, c, "url(#hazard)") + g.rect(sx + 8, sy + 8, 78, c - 16, INK) + g.tc(sx + 8, sy + 8, 78, c - 16, "SEGV", SM, BRIGHT, "monob") + elif kind == "pig": + g.rect(sx, sy, 43, c, OCHRE) + g.rect(sx + 51, sy, 43, c, TEAL) + g.t(ex + 110, ey + 28, name, 28, VELLUM, "sansm") + g.t(ex + 110, ey + 58, gloss, 22, DIM, "sans") + g.save("06-title-legend") + + +# ---- frame 7: insertion sort, a compare and a swap ------------------------ +def frame7(): + g = Svg() + head(g, "Insertion sort", lit=("source",), focus="source", where="sort.c:6") + AH = 408 + x, y, w, h = panel(g, MX, STAGE_Y, W - 2 * MX, AH, "a", focus=True, right="int a[8]") + vals = [4, 9, 17, 31, 12, 26, 5, 20] + CW, CH = 168, 132 + x0 = MX + (W - 2 * MX - 8 * CW) / 2 + cy = y + 140 + J = 4 + tags = {J - 1: "j-1", J: "j", 5: "i"} + for i, v in enumerate(vals): + cx = x0 + i * CW + st = "read" if i in (J - 1, J) else ("held" if i == 5 else "plain") + g.rect(cx, cy, CW - 2, CH, {"read": EMBER[READ], "held": EMBER[VERM]}.get(st, RAISED)) + if st == "read": + g.frame(cx, cy, CW - 2, CH, READ, 4) + if st == "held": + g.rect(cx, cy + CH - 6, CW - 2, 6, VERM) + g.t(cx + 14, cy + 34, str(i), SM, DIM if i in tags else FAINT, "mono") + if i in tags: + pw = mw(tags[i], SM) + 20 + g.rect(cx + CW - 2 - pw - 10, cy + 10, pw, 36, PAGE) + g.t(cx + CW - 2 - pw, base(cy + 10, 36, SM), tags[i], SM, VELLUM, "monob") + g.t(cx + CW / 2 - 1, cy + CH / 2 + 18 + 0.36 * HERO, str(v), HERO, FAINT if i in (J - 1, J) else VELLUM, "mono", "middle") + # the comparison that decided it + xa, xb = x0 + (J - 1) * CW + CW / 2, x0 + J * CW + CW / 2 + mid = (xa + xb) / 2 + cw_ = mw("31 > 12", DATA) + 32 + g.frame(mid - cw_ / 2, y + 10, cw_, 46, DIM, 2) + g.t(mid, base(y + 10, 46, DATA), "31 > 12", DATA, VELLUM, "mono", "middle") + g.t(mid + cw_ / 2 + 16, base(y + 10, 46, 24), "so they trade places", 24, DIM, "sans") + + # the swap, in flight: one value over, one under + def fly(p0, p1, peak, t, label): + (ax, ay), (bx_, by_) = p0, p1 + mx_, my_ = (ax + bx_) / 2, (ay + by_) / 2 + 2 * peak + g.path(f"M{ax},{ay} Q{mx_},{my_} {bx_},{by_}", DIM, 3) + dl = math.hypot(bx_ - mx_, by_ - my_) + head_tri(g, bx_, by_, (bx_ - mx_) / dl, (by_ - my_) / dl, DIM, 16, 14) + px_ = (1 - t) ** 2 * ax + 2 * (1 - t) * t * mx_ + t * t * bx_ + py_ = (1 - t) ** 2 * ay + 2 * (1 - t) * t * my_ + t * t * by_ + g.rect(px_ - 50, py_ - 30, 100, 60, PAGE) + g.frame(px_ - 50, py_ - 30, 100, 60, BRIGHT, 3) + g.t(px_, py_ + 0.36 * 45, label, 45, BRIGHT, "monob", "middle") + fly((xa, cy - 4), (xb, cy - 4), -46, 0.36, "31") + fly((xb, cy + CH + 4), (xa, cy + CH + 4), 46, 0.36, "12") + + by0 = STAGE_Y + AH + VGAP + bh0 = STAGE_H - AH - VGAP + sx, sy, sw_, sh = panel(g, colx(0), by0, span(7), bh0, "sort.c") + code(g, sx + 2, sy + 16, sw_ - 4, [ + (3, [("for", K), (" (", N), ("int", K), (" i = ", N), ("1", L), ("; i < n; i++) {", N)]), + (4, [(" ", N), ("int", K), (" j = i;", N)]), + (5, [(" ", N), ("while", K), (" (j > ", N), ("0", L), (" && a[j-1] > a[j]) {", N)]), + (6, [(" swap(&a[j-1], &a[j]);", N)]), + (7, [(" j--;", N)]), + ], cur=6, trail=(5, 7)) + + lx, ly, lw, lh = panel(g, colx(7), by0, span(5), bh0, "locals", right="of sort()") + for k, (name, typ, val) in enumerate((("i", "int", "5"), ("j", "int", "4"), ("n", "int", "8"), ("a", "int *", None))): + yy = ly + 12 + k * 56 + b = base(yy, 46, DATA) + g.t(lx + 24, b, name, DATA, VELLUM, "mono") + g.t(lx + 84, base(yy, 46, SM), typ, SM, FAINT, "mono") + if val: + if name == "j": + g.rect(lx + 196, yy, 76, 46, EMBER[VERM]) + g.rect(lx + 196, yy + 40, 76, 6, VERM) + g.t(lx + 212, b, val, DATA, VELLUM, "mono") + else: + hexgroups(g, lx + 212, b, "7ffd3a2c1e20") + g.t(lx + 212 + hexw(12) + 20, base(yy, 46, 24), "where a[0] is", 24, DIM, "sans") + caption(g, [[("While the one on the left is larger, they trade places,",)], + [("and ",), ("j", "mono"), (" follows the smaller value down.",)]]) + g.save("07-sort-swap") + + +# ---- frame 8: the far view: pages and system calls ------------------------ +def frame8(): + g = Svg() + head(g, "A process, from far away", lit=("memory", "kernel"), focus="memory", where="hello") + PH = 480 + x, y, w, h = panel(g, colx(0), STAGE_Y, span(8), PH, "address space", focus=True, right="one square a page of 4096 bytes · low addresses on top") + gx = x + 24 + px_ = gx + hexw(12, SM) + 24 # permissions + nx = px_ + 3 * 30 + 16 # name + zx_ = nx + 150 + 80 # size, ranged right on this + cx = zx_ + 24 # pages + P = 24 # page pitch; drawn 22 + maps = [ + (0x55d4a1c01000, "r-x", "hello", "C", "4K"), + (0x55d4a1c02000, "r--", "hello", "R", "4K"), + (0x55d4a1c03000, "rw-", "hello", "ph", "8K"), + (0x55d4a2e5f000, "rw-", "heap", "pp" + "." * 14, "132K"), + (0x7f3c5e200000, "r-x", "libc.so.6", "pp.p..ppp.p....p", "2.1M"), + (0x7f3c5e5c2000, "r-x", "ld.so", "ppp.pp.p..p.pppp", "216K"), + (0x7ffd3a2a2000, "rw-", "stack", "." * 13 + "pWp", "132K"), + (0x7ffd3a3d1000, "r-x", "vdso", "p.", "8K"), + ] + ry = {} + for i, (addr, perm, name, pages, size) in enumerate(maps): + yy = y + 16 + i * 42 + ry[name + str(i)] = yy + address(g, gx, yy, addr, h=38) + for k, ch in enumerate("rwx"): + bx_ = px_ + k * 30 + if perm[k] != "-": + g.rect(bx_, yy + 4, 26, 30, RAISED) + g.t(bx_ + 13, base(yy, 38, SM), ch, SM, VELLUM, "mono", "middle") + else: + g.rect(bx_ + 10, yy + 16, 6, 6, RULE) + g.t(nx, base(yy, 38, SM), name, SM, VELLUM, "mono") + g.t(zx_, base(yy, 38, SM), size, SM, DIM, "mono", "end") + lead = 44 if name == "stack" else 0 # the stack's used end is its high end + for k, ch in enumerate(pages): + qx = cx + lead + k * P + if ch == ".": + g.frame(qx, yy + 8, P - 2, P - 2, RULE, 2) + else: + g.rect(qx, yy + 8, P - 2, P - 2, {"p": RULE, "C": GOLD, "R": READ, "W": VERM, "h": EMBER[VERM]}[ch]) + if ch == "h": + g.rect(qx, yy + 8 + P - 8, P - 2, 6, VERM) + if len(pages) == 16: + for d in range(3): + g.rect(cx + (0 if lead else 16 * P + 10) + d * 12, yy + 16, 6, 6, FAINT) + # the kernel's half, below everything + ky = y + 16 + len(maps) * 42 + 10 + g.rect(x + 2, ky, w - 4, h - (ky - y) - 2, KERNEL) + km = ky + (h - (ky - y)) / 2 + g.t(gx, km + 0.36 * SM, "ffff 8000 0000", SM, PAGE, "mono") + g.t(nx, km + 0.36 * 28, "kernel", 28, PAGE, "sansm") + g.t(nx + 130, km + 0.36 * 24, "the upper half of every address space", 24, KERNEL_DIM, "sans") + + # one page, magnified + zx, zy, zw, zh = panel(g, colx(8), STAGE_Y, span(4), PH, "one page of the stack", right="4096 bytes") + sgx = zx + 20 + scx = sgx + hexw(8, SM) + 28 + rows = [(0x7ffd3a2c1e38, [None] * 8, "plain"), + (0x7ffd3a2c1e40, "48 65 6c 6c 6f 2c 20 77".split(), "plain"), (0x7ffd3a2c1e48, "6f 72 6c 64 21 0a 00 00".split(), "plain"), + (0x7ffd3a2c1e50, "00 3f 9a c1 77 d2 8e 5b".split(), "plain"), (0x7ffd3a2c1e58, "40 1e 2c 3a fd 7f 00 00".split(), "write")] + elide(g, scx, zy + 18, "3640 bytes above") + for i, (addr, bs, st) in enumerate(rows): + yy = zy + 58 + i * ROW + address(g, sgx, yy, addr, digits=8) + for j, v in enumerate(bs): + byte(g, scx + j * CELL, yy, v, st) + elide(g, scx, zy + 58 + 5 * ROW + 2, "416 below") + wy = ry["stack6"] + 8 + wx = cx + 44 + 14 * P + g.frame(wx - 5, wy - 5, P + 8, P + 8, BRIGHT, 3) + wedge(g, wx + P + 3, wy - 5, wy + P + 3, zx, zy - TAG_H, zy + zh) + + # system calls: the boundary seen from far away + sy0 = STAGE_Y + PH + VGAP + sx, sy, sw_, sh = panel(g, colx(0), sy0, span(12), STAGE_H - PH - VGAP, "system calls", right="time runs right · width is time spent in the kernel") + bl = sy + 78 + g.line(sx + 2, bl, sx + sw_ - 2, bl, VELLUM, 3) + g.t(sx + 24, bl - 14, "user", 22, DIM, "sansm") + g.t(sx + 24, bl + 30, "kernel", 22, DIM, "sansm") + calls = [("execve", 150, 1), ("brk", 18, 0), ("mmap", 26, 0), ("openat", 64, 1), ("read", 40, 0), ("mmap", 30, 0), ("mmap", 22, 0), + ("close", 16, 0), ("mprotect", 70, 1), ("mmap", 22, 0), ("arch_prctl", 16, 0), ("munmap", 44, 0), ("write", 110, 2), ("exit_group", 120, 3)] + gaps = [40, 26, 22, 30, 24, 20, 22, 26, 34, 22, 28, 140, 150, 60] + xx = sx + 130 + now = main_x = None + for (name, wd, kind), gap in zip(calls, gaps): + xx += gap + if name == "write": + main_x = xx - 120 + if kind == 3: # not yet run + g.frame(xx, bl + 2, wd, 44, DIM, 2) + g.t(xx + wd / 2, bl + 80, name, SM, FAINT, "mono", "middle") + else: + g.rect(xx, bl + 2, wd, 44, KERNEL) + if kind == 2: + now = xx + wd * 0.55 + pw = mw(name, SM) + 24 + g.rect(xx + wd / 2 - pw / 2, bl + 58, pw, 40, GOLD) + g.t(xx + wd / 2, base(bl + 58, 40, SM), name, SM, INK, "monob", "middle") + elif kind == 1: + g.t(xx + wd / 2, bl + 80, name, SM, DIM, "mono", "middle") + xx += wd + for label, xa, xb in (("the dynamic loader", sx + 320, main_x - 20), ("main", main_x, sx + sw_ - 60)): + g.path(f"M{xa},{bl - 28} v-10 H{xb} v10", FAINT, 3, join="miter") + if " " in label: + g.t((xa + xb) / 2, bl - 50, label, 24, DIM, "sans", "middle") + else: + g.t((xa + xb) / 2, bl - 50, label, SM, DIM, "mono", "middle") + g.line(now, sy + 8, now, bl + 54, GOLD, 4) + + caption(g, [[("Before ",), ("main", "mono"), (" runs a single line, the loader has already",)], + [("asked the kernel for memory a dozen times.",)]]) + g.save("08-far-view") + + +if __name__ == "__main__": + import sys + frames = {k: v for k, v in globals().items() if k.startswith("frame") and callable(v)} + for k in sys.argv[1:] or sorted(frames): + frames[k if k.startswith("frame") else "frame" + k]() -- cgit v1.3