It was 4:00 in the afternoon, and time to walk to the dump, out past the sewage plant, and talk about hard problems.
I’ve had some of my best ideas while out walking. I’m 6’4″ with long legs, and I walk fast. I find when my legs are occupied I can let stuff sift through my head and sort of bounce around until they fall into place. One must leave the cell phone and music player and other distractions behind or you won’t get work done; just get out there and let the ground travel past your feet, and things get solved.
That, or just go out for a walk with cow-orkers and enjoy the day, and bullshit about stuff.
The latest problem I was working out was how to run Unix on the Atari ST. The Tramiels had somehow wrangled a license for AT&T’s SVR-something-or-other version of Unix (might have been SVR3, but this was in the bad old days when AT&T was actively fucking up Unix, and it could have been just about any version, including SVR666). The license was for a mind boggling, nay, jaw-dropping ten bucks a seat. The problem was that the ST didn’t have any kind of memory management hardware, just a raw CPU flinging real addresses at naked DRAM, and the machine’s cheap-ass vanilla 68000 was incapable of recovering from a fault unless you cheated.
[What's that about Linux? Dear child, Linus was probably not out of whatever they use for high school in Finland. All we had in the market was 4.2bsd running on Vaxen, 68K-based Suns with a ton of hardware to work around the 68000 limitation re faulting, and a whole running field of wannabes that would sink without a trace in five years. Oh, and some screwed up AT&T workstations with monochrome graphics and UIs that curdled your eyeballs and left you wishing AT&T had simply stuck with making phones.]
The hardware folks were convinced that grafting an MMU into the ST was impossible; in theory you could still run something like Unix, but with no memory protection and no way to easily grow and shrink a process’s address space a straight-forward port of Unix would be glacial and prone to crashing really badly. The hardware guys were mostly right; the 68000 wasn’t capable of handling a page fault (it didn’t save enough information on its exception frames to restart all cases of a faulted instruction). Motorola didn’t offer an MMU chip anyway (the 68020 didn’t exist yet, and the sticker shock of its optional external MMU meant that only Apple folks could afford it, and it was still optional on most Macs for several years). Furthermore, the memory system of the ST wouldn’t tolerate the delays that a traditional MMU would incur; the ST’s DRAMs were being thrashed ten or fifteeen nanoseconds under spec (“You have to understand,” said our hardware guys, “DRAMs are really analog devices,” and I’m sure a DRAM designer somewhere felt cold and shivery all of a sudden, and didn’t know why).
To run Unix effectively we needed some hardware that was very fast, that was simple enough to put into a minor spin of the ST’s memory controller with little project risk, and that would still provide some kind of memory relocation and protection. The ability to have separate address spaces to isolate processes would be good, too.
“If you can come up with something that takes about a gate delay, I’ll put it in,” said John, the memory controller guy. He seemed dubious, but willing to listen.
I went for a bunch of walks.
- – - -
In the early 80s, eastern Sunnyvale bordered southern San Fransisco Bay with a landfill hill (a large, long mound maybe a hundred feet high), and a sewage treatment plant just beyond. Beyond these were settling ponds for the sewage, separated by a large number of wandering dikes upon which were set miles upon miles of paths for walking. I never exhausted the paths. It was easy to get your heart pumping and your legs swinging and let your head fly off into some tough technical nut. I never really noticed any smell; maybe once or twice. The winter rains washed the stink out of the air.
There were birds out there by the thousands, and any number of rodents. I saw an enormous heron once and realized why my parents had been so excited to see them nest in a marsh we’d lived near in Ohio.
We could also get a good view of planes at Moffet Field. Occasionally a U2 would take off, shaking the ground slightly as it roared into the stratosphere to look (we were told) for pot fields in northern California, saving the world for democracy.
Then the path would loop back, and I’d bounce some ideas off of people. Eventually we got it.
- – - -
The MMUs I knew about did page table walks of a multi-level tree; those multiple indirections implied complex, stateful and slow machinery. There was no room in the ST’s memory controller for the caches required to make a table-based system perform reasonably, even if the gate count of table-lookup hardware had been possible. The ST was no VAX. We had to pay dearly for chip area, schedules were tight, and DRAM timing was even tighter. Nobody wanted to pay for a feature they’d never use.
Non-MMU-based systems used base-and-bounds; a favorite technique in mainframes and minis from the 60s and 70s. We could get protection by checking user accesses against limit registers, a pretty cheap operation, but that wouldn’t get you relocation. To do that you had to muck with the address bits, and do an addition.
The problem was, there wasn’t time to do an addition with the necessary carry-propagation on every single address issue, not to mention the gate count.
So how does a typical Unix process grow? The text and data are at the bottom of the address space and don’t move; the bss follows those, and grows up via the “brk.” The stack grows down. That’s it. Very simple, very hippy 70s.
So imagine something really minimal, like replacing a bunch of address lines with a chosen constant value for user-mode accesses. Leave everything untouched for supervisor accesses. That’s it, that’s your total relocation. It’s really simple to implement in hardware, just a latch and some muxes to choose which address lines go through and which get replaced.
For address space growth you have another register, a mask or a bit count, that checks to see if some number of the issued upper address bits are either all zero or all one. You start the stack at 0xfffffffe and grow down. You start the bss low and grow up. A variable number of bits in the middle of each address are simply substituted. If the upper N bits aren’t all 0000…00 or 11111…11 then you generate a fault.
Now you have a system that both relocates addresses and handles growth in two directions in powers of two. You use throwaway instructions to do stack growth probing (dud sequences that don’t need to be restarted if they fault), and that needs a little compiler work, but it’s not too bad. Processes are tiled in memory at power-of-two addresses, so there’s more physical copying going on than you probably like when stuff grows, but again, it’s not too bad. Welcome to the world of doesn’t-totally-suck, and probably runs rings around a PDP-11 despite its limitations. AT&T SVR-N didn’t have paging anyway (like I said, they should have stuck with phones).
- – - -
John Horton, the memory chip guy, actually did this hardware for the Mega ST; I don’t know if it’s documented, or if he had to sneak it in or not. I do know that it was not used for Unix in my time at Atari; the deal with AT&T expired before the hardware existed, and frankly, supporting Unix probably would have been a massive effort, and one that the Atari software group would have been unable to adequately support. I vaguely recall some Unix-a-like environments for the ST, but I pretty much lost interest in the ST after I left Atari in 1987.
I recall talking about this scheme with John Gilmore, who took a kind interest and asked some good probing questions. We had some great conversations at some otherwise strained hacker dinners in Berkeley. (I’ll talk about South Bay versus North Bay geeks some other time…).