Post by @thalia@discuss.systems

Most notably, the oldest list of UNIX licensees was produced from a form letter database.

Ken Thompson used form/fed to simplify mailing to early users: rather than hand- or typewriting messages, this fancy tool would substitute each recipient and the date. In 1975, when UNIX News was starting up, he used this form letter database to dump the list of contacts that served as the initial subscriber list.

The circumstances of the UNIX V4 tape found at the University of Utah are still somewhat unclear, as it was apparently not used for research and only sparse traces of its acquisition survived. But some letters to Martin Newell are in that form letter database and I hope to recover more information through forensic analysis.

2/6

#unix #retrocomputing #vintagecomputing

#unix #vintagecomputing #retrocomputing

0 Boosts

1 Like

Thalia Archibald

@thalia@discuss.systems last wk.

Now that I understand it fully, I'll build a forensic analysis tool in Rust to recover prior versions of the database by reversing allocator operations.

Much information is leaked through the slack data in freed blocks, the string copying patterns, and the ordering of the free lists. I hope to be able to construct a tree of possible operations that could have produced a form letter database.

With this, I may be able to refine my estimate of when UNIX was requested by the U.

3/6

Thalia Archibald

@thalia@discuss.systems last wk.

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

Thalia Archibald

@thalia@discuss.systems last wk.

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

Thalia Archibald

@thalia@discuss.systems last wk.

Throughout this process, I fixed about a dozen bugs in the original assembly program and many other small issues. It seems it was less tested than the assembler, my last porting project, which had impressively few bugs in its 3,583 lines of assembly.

6/6