Post by @thalia@discuss.systems

2026-10-16 04:39 UTC

But why does form/fed implement an allocator? Now, we'd just load all the key/value pairs into memory, process, and dump, especially for a database so small. But memory was expensive and the PDP-11/20 had only 56KB. Instead, it uses a file as the backing store and reads 512-byte blocks on demand, caching up to four of them, and flushing when evicted. It implements a buddy allocator with a full suite of functions, including coalescing and resizing. This was well before the standard library started to take form, so it was all bespoke to form/fed. 4/6

Replies (2)

@thalia@discuss.systems 2026-10-16 04:40

My process of reverse engineering this was quite methodical. Since it is hand-written assembly, it employs numerous clever tricks, global program knowledge, and ad hoc calling conventions for every function. Many functions have straightforward dataflow and a clear calling convention. Some require examining the demanded registers across all callers, to determine whether a register is written or clobbered. But a nightmarish trio of functions are mutually recursive. To correctly analyze these, I annotated points with the register and stack state. Loops merge states on backedges, branches merge states on join. So far so good; this logic remains relatively local. At recursive calls, I'd initially assume the call would update all state and I'd represent this with fresh values for all registers. This lets me do a dataflow analysis as usual. But some of these fresh values were observed, so I couldn't stop yet, as a full fixpoint was required. I repeatedly propagated constraints between the functions until the calling conventions were fully resolved. Yes, I did this by hand. Yes, I'm crazy. I'm working on a decompiler for PDP-11 assembly to period-appropriate C, but I haven't finished it yet, so I instead played as the static analyzer. 5/6 #programminglanguages #reverseengineering

Open ##5259783
@kromione@mastodon.social 2026-10-16 07:11

A buddy allocator over 512-byte blocks with a four-block cache, all to fit in 56 KB, says a lot about that machine. Recovering old versions of the database from the free lists sounds like a great next chapter.

Open ##5366832