A microcontroller Macintosh This all started from a conversation about the RP2040 MCU, and building a simple desktop/GUI for it. I’d made a comment along the lines of “or, just run some old OS”, and it got me thinking about the original Macintosh. The original Macintosh was released 40.5 years before this post, and is a pretty cool machine especially considering that the hardware is very simple. Insanely Great and folklore.org are fun reads, and give a glimpse into the Macintosh’s development. Memory was a squeeze; the original 128KB version was underpowered and only sold for a few months before being replaced by the Macintosh 512K, arguably a more appropriate amount of memory. But, the 128 still runs some real applications and, though it pre-dates MultiFinder/actual multitasking, I found it pretty charming. As a tourist. In 1984 the Mac cost roughly 1/3 as much as a VW Golf and, as someone who’s into old computers and old cars, it’s hard to decide which is more frustrating to use. So back to this £3.80 RPi Pico microcontroller board: The RP2040’s 264KB of RAM gives a lot to play with after carving out the Mac’s 128KB – how cool would it be to do a quick hack, and play with a Mac on it? Time passes. A lot of time. But I totally delivered on the janky hack front: You won’t believe that this quality item didn’t take that long to build. So the software was obviously the involved part, and turned into work on 3 distinct projects. This post is going to be a “development journey” story, as a kind of code/design/venting narrative. If you’re just here for the pictures, scroll along! What is pico-mac? A Raspberry Pi RP2040 microcontroller (on a Pico board), driving monochrome VGA video and taking USB keyboard/mouse input, emulating a Macintosh 128K computer and disc storage. The RP2040 has easily enough RAM to house the Mac’s memory, plus that of the emulator; it’s fast enough (with some tricks) to meet the performance of the real machine, has USB host capability, and the PIO department makes driving VGA video fairly uneventful (with some tricks). The basic Pico board’s 2MB of flash is plenty for a disc image with OS and software. Here’s the Pico MicroMac in action, ready for the paperless office of the future: The Pico MicroMac RISC CISC workstation of the future I hadn’t really used a Mac 128K much before; a few clicks on a museum machine once. But I knew they ran MacDraw, and MacWrite, and MacPaint. All three of these applications are pretty cool for a 128K machine; a largely WYSIWYG word processor with multiple fonts, and a vector drawing package. A great way of playing with early Macintosh system software, and applications of these wonderful machines is via https://infinitemac.org, which has shrinkwrapped running the Mini vMac emulator by emscriptening it to run in the browser. Highly recommended, lots to play with. As a spoiler, MicroMac does run MacDraw, and it was great to play with it on “real fake hardware”: (Do you find “Pico Micro Mac” doesn’t really scan? I didn’t think this taxonomy through, did I?) GitHub links are at the bottom of this page: the pico-mac repo has construction directions if you want to build your own! The journey Back up a bit. I wasn’t committed to building a Pico thing, but was vaguely interested in whether it was feasible, so started tinkering with building a Mac 128K emulator on my normal computer first. The three rules I had a few simple rules for this project: It had to be fun. It’s OK to hack stuff to get it working, it’s not as though I’m being paid for this. I like writing emulation stuff, but I really don’t want to learn 68K assembler, or much about the 68K. There’s a lot of love for 68K out there and that’s cool, but meh I don’t adore it as a CPU. So, right from the outset I wanted to use someone else’s 68K interpreter – I knew there were loads around. Similarly, there are a load of OSes whose innards I’d like to learn more about, but the shittiest early Mac System software isn’t high on the list. Get in there, emulate the hardware, boot the OS as a black box, done. I ended up breaking 2 of and sometimes all 3 of these rules during this project. The Mac 128K The machines are generally pretty simple, and of their time. I started with schematics and Inside Macintosh, PDFs of which covered various details of the original Mac hardware, memory map, mouse/keyboard, etc. https://tinkerdifferent.com/resources/macintosh-128k-512k-schematics.79/ https://vintageapple.org/inside_o/ Inside Macintosh Volumes I-III are particularly useful for hardware information; also Guide to Macintosh Family Hardware 2nd Edition. The Macintosh has: A Motorola 68000 CPU running at 7.whatever MHz roughly 8MHz Flat memory, decoded into regions for memory-mapped IO going to the 6522 VIA, the 8530 SCC, and the IWM floppy controller. (Some of the address decoding is a little funky, though.) Keyboard and mouse hang off the VIA/SCC chips. No external interrupt controller: the 68K has 3 IRQ lines, and there are 3 IRQ sources (VIA, SCC, programmer switch/NMI). “No slots” or expansion cards. No DMA controller: a simple autonomous PAL state machine scans video (and audio samples) out of DRAM. Video is fixed at 512x342 1BPP. The only storage is an internal FDD (plus an external drive), driven by the IWM chip. The first three Mac models are extremely similar: The Mac 128K and Mac 512K are the same machine, except for RAM. The Mac Plus added SCSI to a convenient space in the memory map and an 800K floppy drive, which is double-sided whereas the original was a single 400K side. The Mac Plus ROM also supports the 128K/512K, and was an upgrade to create the Macintosh 512Ke. ‘e’ for Extra ROM Goodness. The Mac Plus ROM supports the HD20 external hard disc, and HFS, and Steve Chamberlin has annotated a disassembly of it. This was the ROM to use: I was making a Macintosh 128Ke. Mac emulator: umac After about 8 minutes of research, I chose the Musashi 68K interpreter. It’s C, simple to interface to, and had a simple out-of-box example of a 68K system with RAM, ROM, and some IO. Musashi is structured to be embedded in bigger projects: wire in memory read/write callbacks, a function to raise an IRQ, call execute in a loop, done. I started building an emulator around it, which ultimately became the umac project. The first half (of, say, five halves) went pretty well: A simple commandline app loading the ROM image, allocating RAM, providing debug messages/assertions/logging, and configuring Musashi. Add address decoding: CPU reads/writes are steered to RAM, or ROM. The “overlay” register lets the ROM boot at 0x00000000 and then trampoline up to a high ROM mirror after setting up CPU exception vectors – this affects the address decoding. This is done by poking a VIA register, so decoded just that bit of that register for now. At this point, the ROM starts running and accessing more non-existent VIA and SCC registers. Added more decoding and a skeleton for emulating these devices elsewhere – the MMIO read/writes are just stubbed out. There are some magic addresses that the ROM accesses that “miss” documented devices: there’s a manufacturing test option that probes for a plugin (just thunk it), and then we witness the RAM size probing. The Mac Plus ROM is looking for up to 4MB of RAM. In the large region devoted to RAM, the smaller amount of actual RAM is mirrored over and over, so the probe writes a magic value at high addresses and spots where it starts to wrap around. RAM is then initialised and filled with a known pattern. This was an exciting point to get to because I could dump the RAM, convert the region used for the video framebuffer into an image, and see the “diagonal stripe” pattern used for RAM testing! “She’s alive!” Not all of the device code enjoyed reading all zeroes, so there was a certain amount of referring to the disassembly and returning, uh, 0xffffffff sometimes to push it further. The goal was to get it as far as accessing the IWM chip, i.e. trying to load the OS. After seeing some IWM accesses there and returning random rubbish values, the first wonderful moment was getting the “Unknown Disc” icon with the question mark – real graphics! The ROM was REALLY DOING SOMETHING! I think I hadn’t implemented any IRQs at this point, and found the ROM in an infinite loop: it was counting a few Vsyncs to delay the flashing question mark. Diversion into a better VIA, with callbacks for GPIO register read/write, and IRQ handling. This also needed to wire into Musashi’s IRQ functions. This was motivating to get to – remembering rule #1 – and “graphics”, even though via a manual memory dump/ImageMagick conversion, was great. I knew the IWM was an “interesting” chip, but didn’t know details. I planned to figure it out when I got there (rule #1). IWM, 68K, and disc drivers My god, I’m glad I put IWM off until this point. If I’d read the “datasheet” (vague register documentation) first, I’d’ve just gone to the pub instead of writing this shitty emulator. IWM is very clever, but very very low-level. The disc controllers in other contemporary machines, e.g. WD1770, abstract the disc physics. At one level, you can poke regs to step to track 17 and then ask the controller to grab sector 3. Not so with IWM: first, the discs are Constant Linear Velocity, meaning the angular rotation needs to change appropriate to whichever track you’re on, and second the IWM just gives the CPU a firehose of crap from the disc head (with minimal decoding). I spent a while reading through the disassembly of the ROM’s IWM driver (breaking rule #2 and rule #1): there’s some kind of servo control loop where the driver twiddles PWM values sent to a DAC to control the disc motor, measured against a VIA timer reference to do some sort of dynamic rate-matching to get the correct bitrate from the disc sectors. I think once it finds the track start it then streams the track into memory, and the driver decodes the symbols (more clever encoding) and selects the sector of interest. I was sad. Surely Basilisk II and Mini vMac etc. had solved this in some clever way – they emulated floppy discs. I learned they do not, and do the smart engineering thing instead: avoid the problem. The other emulators do quite a lot of ROM patching: the ROM isn’t run unmodified. You can argue that this then isn’t a perfect hardware emulation if you’re patching out inconvenient parts of the ROM, but so what. I suspect they were also abiding by a rule #1 too. I was going to do the same: I figured out a bit of how the Mac driver interface works (gah, rule #3!) and understood how the other emulators patched this. They use a custom paravirtualised 68K driver which is copied over the ROM’s IWM driver, servicing .Sony requests from the block layer and routing them to more convenient host-side code to manage the requests. Basilisk II uses some custom 68K opcodes and a simple driver, and Mini vMac a complex driver with trappy accesses to a custom region of memory. I reused the Basilisk II driver but converted to access a trappy region (easier to route: just emulate another device). The driver callbacks land in the host/C side and some cut-down Basilisk II code interprets the requests and copies data to/from the OS-provided buffers. Right now, all I needed was to read blocks from one disc: I didn’t need different formats (or even write support), or multiple drives, or ejecting/changing images. Getting the first block loaded from disc took waaaayyy longer than the first part. And, I’d had to learn a bit of 68K (gah), but just in the nick of time I got a Happy Mac icon as the System software started to load. This was still a simple Linux commandline application, with zero UI. No keyboard or mouse, no video. Time to wrap it in an SDL2 frontend (the unix_main test build in the umac project), and I could watch the screen redraw live. I hadn’t coded the 1Hz timer interrupt into the VIA, and after adding that it booted to a desktop! The first boot As an aside, I try to create a dual-target build for all my embedded projects, with a native host build for rapid prototyping/debugging; libSDL instead of an LCD. It means I don’t need to code at the MCU, so I can code in the garden. :) Next was mouse support. Inside Macintosh and the schematics show how it’s wired, to the VIA (good) and the SCC (a beast). The SCC is my second least-favourite chip in this machine; it’s complex and the datasheet/manual seems to be intentionally written to hide information, piss off readers, get one back at the world. (I didn’t go near the serial side, its main purpose, just external IRQ management. But, it’ll do all kinds of exciting 1980s line coding schemes, offloading bitty work from the CPU. It was key for supporting things like AppleTalk.) Life was almost complete at this point; with a working mouse I could build a new disc image (using Mini vMac, an exercise in itself) with Missile Command. This game is pretty fun for under 10KB on disc. So: Video works Boots from disc Mouse works, Missile Command I had no keyboard, but it’s largely working now. Time to start on sub-project numero due: Hardware and RP2040 Completely unrelated to umac, I built up a circuit and firmare with two goals: Display 512x342x1 video to VGA with minimal components, Get the TinyUSB HID example working and integrated. This would just display a test image copied to a framebuffer, and printf() keyboard/mouse events, as a PoC. The video portion was fun: I’d done some I2S audio PIO work before, but here I wanted to scan out video and arbitrarily control Vsync/Hsync. Well, to test I needed a circuit. VGA wants 0.7V max on the video R,G,B signals and (mumble, some volts) on the syncs. The R,G,B signals are 75Ω to ground: with some maths, a 3.3V GPIO driving all three through a 100Ω resistor is roughly right. The day I started soldering it together I needed a VGA connector. I had a DB15 but wanted it for another project, and felt bad about cutting up a VGA cable. But when I took a walk at lunchtime, no shitting you, I passed some street cables. I had a VGA cable – the rust helps with the janky aesthetic. Free VGA cable The VGA PIO side was pretty fun. It ended up as PIO reading config info dynamically to control Hsync width, display position, and so on, and then some tricks with DMA to scan out the config info interleaved with framebuffer data. By shifting the bits in the right direction and by using the byteswap option on the RP2040 DMA, the big-endian Mac framebuffer can be output directly without CPU-side copies or format conversion. Cool. This can be fairly easily re-used in other projects: see video.c. But. I ended up (re)writing the video side three times in total: First version had two DMA channels writing to the PIO TX FIFO. The first would transfer the config info, then trigger the second to transfer video data, then raise an IRQ. The IRQ handler would then have a short time (the FIFO depth!) to choose a new framebuffer address to read from, and reprogram DMA. It worked OK, but was highly sensitive to other activity in the system. First and most obvious fix is that any latency-sensitive IRQ handler must have the __not_in_flash_func() attribute so as to run out of RAM. But even with that, the design didn’t give much time to reconfigure the DMA: random glitches and blanks occurred when moving the mouse rapidly. Second version did double-buffering with the goal of making the IRQ handler’s job trivial: poke in a pre-prepared DMA config quickly, then after the critical rush calculate the buffer to use for next time. Lots better, but still some glitches under some high load. Even weirder, it’d sometimes just blank out completely, requiring a reset. This was puzzling for a while; I ended up printing out the PIO FIFO’s FDEBUG register to try to catch the bug in the act. I saw that the TXOVER overflow flag was set, and this should be impossible: the FIFOs pull data from DMA on demand with DMA requests and a credited flow-contr…OH WAIT. If credits get messed up or duplicated, too many transfers can happen, leading to an overflow at the receiver side. Well, I’d missed a subtle rule in the RP2040 DMA docs: Another caveat is that multiple channels should not be connected to the same DREQ. So the third version…… doesn’t break this rule, and is more complicated as a result: One DMA channel transfers to the PIO TX FIFO Another channel programs the first channel to send from the config data buffer A third channel programs the first to send the video data The programming of the first triggers the corresponding “next reprogram me” channel The nice thing – aside from no lock-ups or video corruption – is that this now triggers a Hsync IRQ during the video line scan-out, greatly relaxing the deadline of reconfiguring the DMA. I’d like to further improve this (with yet another DMA channel) to transfer without an IRQ per line, as the current IRQ overhead of about 1% of CPU time can be avoided. (It would’ve been simpler to just hardwire the VGA display timing in the PIO code, but I like (for future projects) being able to dynamically-reconfigure the video mode.) So now we have a platform and firmware framework to embed umac into, HID in and video out. The hardware’s done, fuggitthat’lldo, let’s throw it over to the software team: How it all works Back to emulating things A glance at the native umac binary showed a few things to fix before it could run on the Pico: Musashi constructed a huge opcode decode jumptable at runtime, in RAM. It’s never built differently, and never changes at runtime. I added a Musashi build-time generator so that this table could be const (and therefore live in flash). The disassembler was large, and not going to be used on the Pico, so another option to build without. Musashi tries to accurately count execution cycles for each instruction, with more large lookup tables. Maybe useful for console games, but the Mac doesn’t have the same degree of timing sensitivity. REMOVED. (This work is in my small-build branch.) pico-mac takes shape, with the ROM and disc image in flash, and enjoyably it now builds and runs on the Pico! With some careful attention to not shoving stuff in RAM, the RAM use is looking pretty good. The emulator plus HID code is using about 35-40KB on top of the Mac’s 128KB RAM area – there’s 95+KB of RAM still free. This was a good time to finish off adding the keyboard support to umac. The Mac keyboard is interfaced serially through the VIA ‘shift register’, a basic synchronous serial interface. This was logically simple, but frustrating because early attempts at replying to the ROM’s “init” command just were persistently ignored. The ROM disassembly was super-useful again: reading the keyboard init code, it looked like a race condition in interrupt acknowledgement if the response byte appears too soon after the request is sent. Shoved in a delay to hold off a reply until a later poll, and then it was just a matter of mapping keycodes (boooooorrrriiiiing). With a keyboard, the end-of-level MacWrite boss is reached: One problem though: it totally sucked. It was suuuuper slow. I added a 1Hz dump of instruction count, and it was doing about 300 KIPS. The 68000 isn’t an amazing CPU in terms of IPC. Okay, there are some instructions that execute in 4 cycles. But you want to use those extravagant addressing modes don’t you, and touching memory is spending those cycles all over the place. Not an expert, but targeting about 1 MIPS for an about 8MHz 68000 seems right. Only 3x improvement needed. Performance I didn’t say I wasn’t gonna cheat: let’s run that Pico at 250MHz instead of 125MHz. Okay better, but not 2x better. From memory, only about 30% better. Damn, no free lunch today. Musashi has a lot of configurable options. My first goal was to get its main loop (as seen from disassembly/post-compile end!) small: the Mac doesn’t report Bus Errors, so the registers don’t need copies for unwinding. The opcodes are always fetched from a 16b boundary, so don’t need alignment checking, and can use halfword loads (instead of two byte loads munged into a halfword!). For the Cortex-M0+/armv6m ISA, reordering some of the CPU context structure fields enabled immediate-offset access and better code. The CPU type, mysteriously, was dynamically-changeable and led to a bunch of runtime indirection. Looking better, maybe 2x improvement, but not enough. Missile Command was still janky and the mouse wasn’t smooth! Next, some naughty/dangerous optimisations: remove address alignment checking, because unaligned accesses don’t happen in this constrained environment. (Then, this work is in my umac-hacks branch.) But the real perf came from a different trick. First, a diversion! RP2040 memory access The RP2040 has fast RAM, which is multi-banked so as to allow generally single-cycle access to multiple users (2 CPUs, DMA, etc.). Out of the box, most code runs via XIP from external QSPI flash. The QSPI usually runs at the core clock (125MHz default), but has a latency of ~20 cycles for a random word read. The RP2040 uses a relatively simple 16KB cache in front of the flash to protect you from horrible access latency, but the more code you have the more likely you are to call a function and have to crank up QSPI. When overclocking to 250MHz, the QSPI can’t go that fast so stays at 125MHz (I think). Bear in mind, then, that your 20ish QSPI cycles on a miss become 40ish CPU cycles. The particular rock-and-a-hard-place here is that Musashi build-time generates a ton of code, a function for each of its 1968 opcodes, plus that 256KB opcode jumptable. Even if we make the inner execution loop completely free, the opcode dispatch might miss in the flash cache, and the opcode function itself too. (If we want to get 1 MIPS out of about 200 MIPS, a few of these delays are going to really add up.) The __not_in_flash_func() attribute can be used to copy a given function into RAM, guaranteeing fast execution. At the very minimum, the main loop and memory accessors are decorated: every instruction is going to access an opcode and most likely read or write RAM. This improves performance a few percent. Then, I tried decorating whole classes of opcodes: move is frequent, as are branches, so put ‘em in RAM. This helped a lot, but the remaining free RAM was used up very quickly, and I wasn’t at my goal of much above 1 MIPS. Remember that RISC architecture is gonna change everything? We want to put some of those 1968 68K opcodes into RAM to make them fast. What are the top 10 most often-used instructions? Top 100? By adding a 64K table of counters to umac, booting the Mac and running key applications (okay, playing Missile Command for a bit), we get a profile of dynamic instruction counts. It turns out that the 100 hottest opcodes (5% of the total) account for 89% of the execution. And the top 200 account for a whopping 98% of execution. Armed with this profile, the umac build post-processes the Musashi auto-generated code and decorates the top 200 functions with __not_in_flash_func(). This adds only 17KB of extra RAM usage (leaving 95KB spare), and hits about 1.4 MIPS! Party on! At last, the world can enjoy Missile Command’s dark subject matter in performant comfort: Missile Command on pico-mac What about MacPaint? Everyone loves MacPaint. Maybe you love MacPaint, and have noticed I’ve deftly avoided mentioning it. Okay, FINE: It doesn’t run on a Mac 128Ke, because the Mac Plus ROM uses more RAM than the original. :sad-face: I’d seen this thread on 68kMLA about a “Mac 256K”: https://68kmla.org/bb/index.php?threads/the-mythical-mac-256k.46149/ Chances are that the Mac 128K was really a Mac 256K in the lab (or maybe even intended to have 256K and cost-cut before release), as the OS functions fine with 256KB. I wondered, does the Mac ROM/OS need a power-of-two amount of RAM? If not, I have that 95K going spare. Could I make a “Mac 200K”, and then run precious MacPaint? Well, I tried a local hack that patches the ROM to update its global memTop variable based on a given memory size, and yes, System 3.2 is happy with non-power-of-2 sizes. I booted with 256K, 208K, and 192K. However, there were some additional problems to solve: the ROM memtest craps itself without a power-of-2 size (totally fair), and NOPping that out leads to other issues. These can be fixed, though also some parts of boot access off the end of RAM. A power-of-2 size means a cheap address mask wraps RAM accesses to the valid buffer, and that can’t be done with 192K. Unfortunately, when I then tested MacPaint it still wouldn’t run because it wanted to write a scratch file to the read-only boot volume. This is totally breaking rule #1 by this point, so we are staying with 128KB for now. However, a 256K MicroMac is extremely possible. We just need an MCU with, say, 300KB of RAM… Then we’d be cooking on gas. Goodbye, friend Well, dear reader, this has been a blast. I hope there’s been something fun here for ya. Ring off now, caller! The MicroMac! HDMI monitor, using a VGA-to-HDMI box umac screenshot System 3.2, Finder 5.3 Performance tuning Random disc image working OK Resources https://github.com/evansm7/umac https://github.com/evansm7/pico-mac https://www.macintoshrepository.org/7038-all-macintosh-roms-68k-ppc- https://winworldpc.com/product/mac-os-0-6/system-3x https://68kmla.org/bb/index.php?threads/macintosh-128k-mac-plus-roms.4006/ https://docs.google.com/spreadsheets/d/1wB2HnysPp63fezUzfgpk0JX_b7bXvmAg6-Dk7QDyKPY/edit#gid=840977089

In 1974, Gerald Popek and Robert Goldberg published a paper, “Formal Requirements for Virtualizable Third Generation Architectures”, giving a set of characteristics for correct full-machine virtualisation. Today, these characteristics remain very useful. Computer architects will informally cite this paper when debating Instruction Set Architecture (ISA) developments, with arguments like “but that’s not Popek & Goldberg-compliant!” In this post I’m looking at one aspect of computer architecture evolution since 1974, and observing how RISC-style atomic operations provide some potential virtualisation gotchas for both programmers and architects. Principles of virtualisation First, some virtualisation context, because it’s fun! A key P&G requirement is that of equivalence: it’s reasonable to expect software running under virtualisation to have the same behaviour as running it bare-metal! This property is otherwise known as correctness. :-) P&G classify instructions as being sensitive if they behave differently when running at a lower privilege level (i.e. the program can detect that it is being run in a different manner). An ISA is said to be classically virtualisable if: Sensitive instructions are privileged, and Privileged instructions executed at a lower privilege level can be trapped to a higher level of privilege. For a classically-virtualisable system, perfect equivalence can then be achieved by running software at a lower than usual level of privilege, trapping all privileged/sensitive instructions, and emulating their behaviour in a VMM. That is, if the design of the ISA ensures that all “sensitive” instructions can be trapped, it’s possible to ensure the logical execution of the software cannot be different to running bare-metal. This virtualisation technique is called “privilege compression”. Note: This applies recursively, running OS-level software with user privilege, or hypervisor-level software at OS/user privilege. Popek & Goldberg formalise this too, giving properties required for correct nested virtualisation. System/360 and PowerPC are both classically virtualisable, almost as though IBM thought about this. ;-) Equivalent virtualisation can be achieved by: Running an OS in user mode (privilege compression, for CPU virtualisation), Catching traps (to supervisor mode/HV) when the guest OS performs a privileged operation, In the hypervisor, operating on a software-maintained “shadow” of what would have been the guest OS’s privileged CPU state were it running bare-metal. Constructing shadow address translations (for memory virtualisation). Linux’s KVM support on PowerPC includes a “PR” feature, which does just this: for CPUs without hardware virtualisation, guests are run in user mode (or “PRoblem state” in IBM lingo). Note: It is key that the hypervisor can observe and control all of the guest’s state. Today, most systems address the performance impact of all of this trap-and-emulate by providing hardware CPU and memory virtualisation (e.g. user, OS and hypervisor execution privilege levels, with nested page tables). But, classically virtualisable ISA design remains important for clear reasoning about isolation between privilege levels and composability of behaviours. Computers in 1974 were ~all CISC All computers in 1974 were available in corduroy with a selection of Liberty-print input devices. All consoles had ashtrays (not even joking tbh). Architecture-wise, IBM was working on early RISC concepts leading to the 701, but most of the industry was on a full-steam trajectory to peak CISC (VAX) in the late 1970s. It’s fair to say that “CISC” wasn’t even a thing yet; instruction sets were just complex. P&G’s paper considered three contemporary computers: IBM System/360 Honeywell 6000 DEC PDP-10 CISC atomic operations and synchronisation primitives These machines had composite/”read-modify-write” atomic operations, similar to those in today’s x86 architectures. System/360 had compare-and-swap, locked operations (read-operate-write), test-and-set, and PDP-10 had EXCHange/swap. These kinds of instructions are not sensitive so, unless the addressed memory is privileged, atomic operations can be performed inside virtual machines without the hypervisor needing to know. Atomic operations in RISC machines Many RISC machines support multi-instruction synchronisation sequences built up around two instruction primitives: Load-and-set-reservation Store-conditional MIPS called these load-linked (LL) and store-conditional (SC), and I’ll use these terms. ARMv8 has LDXR/STXR. PowerPC has LWARX/STWCX. RISC-V has LR/SC. Many machines (such as ARMv8-LSE) also add composite operations such as CAS or atomic addition but still retain the base LL/SC mechanism, and sizes/acquire/release variants are often provided. The concept is that the LL simultaneously loads a value and sets a “reservation” covering the address in question, and a subsequent SC succeeds only if the reservation is still present. A conflicting write to the location (e.g. a store on another CPU) clears the reservation and the SC returns a failure value without modifying memory; LL/SC are performed in a loop to retry until the update succeeds. An LL/SC sequence can typically be arbitrarily complex – a lock routine might test a location is cleared and store a non-zero value if so, whereas an update might increment a counter or calculate a “next” value, and so on. Typically an ISA does not restrict what lies between LL and SC. Coming back to virtualisation requirements, the definition of a reservation is interesting because it’s effectively “hidden state” that the hypervisor cannot manage. Typically, a hypervisor cannot easily read whether a reservation exists, and it can’t be saved/restored1. CISC-like RmW atomic operations do not exhibit this property. Problem seen, problem felt Shall I get to the point? I saw an odd but legal guest code sequence that can be difficult to virtualise. I’ve been trying to run MacOS 9.2 in KVM-PR on a PowerPC G4, and observed the NanoKernel acquire-lock routine happens to use a sensitive instruction (mfsprg) between a lwarx and stwcx. This is strange, and guarantees a trap to the host between the LL and SC operations. Though the guest should not be doing weird stuff when acquiring a lock, it’s still an architecturally-correct program. This means that if the reservation isn’t preserved across the trap, the lock is never taken. Forward progress is never achieved and virtualisation equivalence is not maintained (because the guest livelocks). Specifically, if the reservation is always cleared on the trap, we have a problem. If it is sometimes kept, the guest program can progress. Since the state is hidden (the hypervisor can’t save/restore/re-create), correctness depends on two things: The hypervisor’s exception-emulation-return path not itself clearing the reservation every time for any possible trap The ISA and hardware implementation guaranteeing the reservation is not always cleared by hardware This potential issue isn’t limited to PPC or the MacOS guest. Software guarantees The hypervisor must guarantee two things: It must not intentionally clear reservations on all traps. It must not accidentally do so as a side-effect of a chosen activity: For example, using its own synchronisation primitives elsewhere, or by writing memory that would conflict with the guest’s reservation. This can be challenging: context switching must be avoided in the T&E handler (no sleep or pre-emption), and it can’t take locks. In my MacOS guest experiment, KVM-PR does not happen to currently use any synchronisation primitives on its emulation path, ew delicate – but I had tracing on, which does. The guest locked up. Hardware guarantees But does your CPU guarantee that reservations aren’t always cleared?2 That seems to depend. This morning’s light reading gives: PowerPC architecture PowerISA is comparatively clear on the behaviour (which isn’t surprising, as PowerISA is generally very clearly-specified). PowerISA v3.1 section 1.7.2.1 describes reservations, listing specific reasons for reservation loss. Some are the expected “lose the reservation if someone else hits the memory” reasons, but previous PowerISAs (e.g. 2.06) permitted embedded implementations to clear the reservation on all exceptions. This permission was removed by 3.1; in my opinion a good move. (I did just this, for reasons, in my homebrew PowerPC CPU, oops!) PowerISA does permit spontaneous reservation loss due to speculative behaviour, but is careful to require that forward progress is guaranteed (i.e. that an implementation doesn’t happen to clear the reservation every time for a given piece of code). Finally, it includes a virtualisation-related programming note stating a reservation may be lost if software executes a privileged instruction or utilizes a privileged facility (i.e. sensitive instructions). This expresses intent, but isn’t specification: it doesn’t criminalise a guest doing wrong things unless it’s a rule that was there from the dawn of time. At any rate, this post is going to be old news to the PowerISA authors. Nice doc, 8/10, good jokes, would read again. RISC-V architecture The lack of any guest legacy permits the problem to be solved from the other direction. Interestingly, the RISC-V ISA explicitly constrains the instruction sequences between LR/SC: "The dynamic code executed between the LR and SC instructions can only contain instructions from the base “I” instruction set, excluding loads, stores, backward jumps, taken backward branches, JALR, FENCE, FENCE.I, and SYSTEM instructions.“ This is a good move. Tacitly, this bans sensitive instructions in the critical region, and permits an absence of progress if the guest breaks the rules. Ruling out memory accesses is interesting too, because it can be useful for a hypervisor to be able to T&E any given page in the guest address space without repercussions. Reservation granule size An LL operation is usually architecturally permitted to set an address-based reservation with a size larger than the original access, called the “reservation granule”. A larger granule reduces tracking requirements but increases the risk of a kind of false sharing between locks where an unrelated CPU taking an unrelated lock could clear your CPU’s reservation. This is important to our hypervisor, because of guarantee #2 above: when emulating a sensitive instruction it must not access anything that always causes the reservation to clear. You would hope the guest doesn’t soil itself by executing an instruction against its interests, so we can assume the guest won’t intentionally direct the hypervisor to hit on shared addresses, but if hypervisor and guest memory could ever coexist within a reservation granule there is scope for conflict. PowerPC defines the largest granule as, effectively, the (small) page size. ARM defines it as 4KB (effectively, the same). It’s a reasonable architectural assumption that guest and host memory is disjoint at page size granularity. RISC-V permits the reservation granule to be unlimited, which isn’t great3 – but later notes that “a platform specification may constrain the size and shape of the reservation set. For example, the Unix platform is expected to require of main memory that the reservation set be of fixed size, contiguous, naturally aligned, and no greater than the virtual memory page size.” Conclusion An ISA cannot be classically virtualised if it permits some aspect of trapping or emulation (such as the exception itself) to always cause a reservation to be cleared, unless sensitive instructions are prohibited from any region dependent on a reservation. In terms of computer science, it’s quite unsatisfying if it were possible to have a sequence of RISC instructions that cannot be classically virtualised due to hidden state. In practical terms, trap-and-emulate is alive and well in systems supporting nested virtualisation. Although some ISAs provide a level of hardware support for NV, it tends to be assists to speed up use of privilege compression rather than more exception levels and more translation stages (which, to be fair, would be awful). Consequently there is always something hypervisor-privileged being trapped to the real hypervisor, i.e. T&E is used in anger. So, there are some hardware behaviours which must (continue to be) guaranteed and, unfortunately, some constraints on already-complex software which must be observed. I thought this small computer architecture safari might be interesting to others, and hope you enjoyed the read! Footnotes In theory an ISA could provide the hypervisor with a previous reservation’s address, but re-creating it with a later LL raises ordering model questions! ↩ Sorry for the double-negative, but this alludes to the possibility of architecture permissions (for example, statements like “X is permitted to spontaneously happen at any time”) leading to implementations taking convenient liberties such as “always do X when any cache line is fetched”. If these decisions were to exist, they would be impossible to avoid stepping on, even with a carefully-written hypervisor. ↩ It would be terrible to permit an implementation to allow all hypervisor memory accesses to clear the reservation! ↩

Built October 2018 I used to hate Cathode Ray Tubes. As a kid in Europe, everything flickered at 50Hz, or made a loud whistle at 15.625KHz (back when I could still hear it). CRTs just seemed crude, “electro-brutalist” contraptions from the valve era. They were heavy, and delicate, and distorted, and blurry, and whistled, and gave people electric shocks when they weren’t busy imploding and spreading glass shards around the place. When I saw the film Brazil, I remember getting anxious about exposed CRTs all over the place — seems I was the kind of kid who was more worried about someone touching the anode or electron gun than the totalitarian bureaucratic world they lived in. 🤷🏻‍♂️ As ever, I digress. Now in the 2020s, the CRT is pretty much gone. We have astonishing flat-panel LCD and OLED screens. Nothing flickers, everything’s pin-sharp, multi-megapixel resolutions, nothing whines (except me), and display life is pretty incredible for those of us old enough to remember green-screen computing (but young enough to still see the details). But, the march to betterness marches away from accessible: if you take apart a phone, the LCD is a magic glass rectangle, and that’s it. Maybe you can see some LEDs if you tear it apart, but it’s really not obvious how it works. CRTs are also magic, but in a pleasing 19th century top-hat-and-cane science kind of way. Invisible beams trace out images through a foot of empty space. They respond colourfully to magnets (also magic) held to their screens by curious children whose glee rapidly decays into panic, and trying to undo the effect using the other pole before their mother looks around and discovers what they’ve done (allegedly). The magnet-game is a clue: (most) CRTs use electromagnets that scans the invisible electron beam to light an image at the front. There’s something enjoyable about moving the beam yourself, with a magnet in hand, and you can kind of intuitively figure out how it works from doing this. (Remember the Left-hand Rule?) I started to warm to CRTs, maybe a fondness when I realised I hadn’t had to seriously use one for over a decade. I wanted to build something. I also like smol displays, and found an excellent source for a small CRT — a video camera viewfinder. Home cameras had tiny CRTs, roughly 1cm picture size, but I looked to find a higher-end professional viewfinder because they tended to have larger tubes for a higher-quality image. Eventually I found a Sony HVF-2000 viewfinder, from ca. 1980. This viewfinder contained a monochrome 1.5” CRT, and its drive circuitry on stinky 1970s phenolic resin PCBs. All it needs are two turntables and an 8V DC power supply and composite video input. It displays nice, sharp images on a cool white phosphor. I built this from it: Small CRT floating in a box I wanted to show the CRT from all angles, without hiding any of it, in the trusty “desktop curiosity” style. The idea was to show off this beautiful little obsolete glass thingy, in a way that you could sorta guess how it worked. Switching it on with a pleasing clack, it starts silently playing a selection of 1980s TV shows, over and over and over: I had this on my desk at work, and a Young PersonTM came into my office one day to ask about it. He hadn’t really seen a CRT close-up before, and we had a fun chat about how it worked (including waving a magnet at it – everyone has a spare magnet on their desk for these moments, don’t they? Hello…?). Yay! If you’re unfamiliar with CRTs, they work roughly like this: The glass envelope contains a vacuum. The neck contains a heating filament (like a lightbulb) which gives off electrons into the void. This “electron gun” is near some metal plates (with variously high positive and negative voltages), which act to focus the fizz of electrons into a narrow beam, directing it forward. The inside of the front face of the tube is covered by a phosphorescent material which lights up when hit with electrons. The front face is connected to the anode terminal, a high positive voltage. This attracts the beam of electrons, which accelerate to the front. The beam hits the front and creates light in a small spot. To create the picture, the beam is steered in rasters/lines using horizontal and vertical electromagnets wrapped around the neck of the tube. (The magnets are called the “yoke”.) For PAL at 50Hz, lines are drawn 15625 times a second. Relying on the principle of persistence of vision, this creates the illusion of a steady image. The tube is sealed and electron gun inside is largely invisible, but here you can see the malicious-looking thick anode wire, and how dainty the tube really is with the yoke removed: Note: the anode voltage for this tube is, from memory, about 2.5 kilovolts, so not particularly spicy. A large computer monitor will give you 25KV! Did I mention the X-rays? Circuit The original viewfinder was a two-board affair, fitting in a strange transverse shape for the viewfinder case. I removed a couple of controls and indicators unrelated to the CRT operation, and extended the wires slightly so they could be stacked. The viewfinder’s eyepiece looks onto a mirror, turning 90º to the CRT face — so the image is horizontally flipped. This was undone by swapping the horizontal deflection coil wires, reversing the field direction. The circuit’s pretty trivial. It just takes a DC input (9-12V) and uses two DC-DC converter modules to create an 8V supply for the CRT board and a 5V supply for a Raspberry Pi Zero layered at the bottom. The whole thing uses under 2W. The Pi’s composite output drops straight into the CRT board. The Pi starts up a simple shell script that picks a file to play. There’s a rotary encoder on the back, to change channel, but I haven’t wired it up yet. Case For me, the case was the best bit. I had just got (and since lost :((( ) access to a decent laser cutter, and wanted to make a dovetailed transparent case for the parts. It’s made from 3mm colourless and sky-blue acrylic. Rubber bands make the world go round The CRT is supported from two “hangers”, and two trays below hold the circuitry. These are fixed to the sides using a slot/tab approach, with captive nuts. In the close-up pictures you can see there are some hairline stress fractures around the corners of some of the tab cut-outs: they could evidently do with being a few hundred µm wider! The front/top/back/bottom faces are glued together, then the left/right sides are screwed into the shelves/hangers with captive M3 nuts. This sandwiches it all together. The back holds a barrel-style DC jack, power switch, and (as-yet unused) rotary encoder. The encoder was intended to eventually be a kind of “channel select”: The acrylic is a total magnet for fingerprints and dust, which is excellent if you’re into that kind of thing. There seems to also be little flecks filling the case, probably some aquadag flaking off the CRT. This technology just keeps on giving. OpenSCAD The case is designed in OpenSCAD, and is somewhat parameterised: the XYZ dimensions, dovetailing, spacing of shelves and so forth can be tweaked till it looks good. One nice OpenSCAD laser-cutting trick I saw is that 2D parts can be rendered into a “preview” 3D view, tweaked and fettled, and then re-rendered flat on a 2D plane to create a template for cutting. So, make a 3D prototype, change the parameters until it looks good (maybe printing stuff out to see whether the physical items actually fit!)… …then change the mode variable, and the same parts are laid out in 2D for cutting: Feel free to hack on and re-use this template. Resources OpenSCAD box sources Pics Tiny dmesg! Edmund Esq

Built in November 2015 (now-traditional multi-year writeup delay applied) A hat, bejewelled with 38 RGB LEDs Is this thing on..? It’s been a while since I’ve written one of these. So, the hat. It’s been on the writeup pile for almost 6 years, nagging away. Finally it’s its time to shine! NO PUN ESCAPES Anyway, the hat. It seemed like a good idea, and I even wore it out dancing. I know, so cool. This hat had been through at least two fancy-dress events, and had a natty band aftermarket mod even before the LEDs. Long story short, got a hat, put a battery, ARM Cortex-M0 microcontroller, accelerometer in it and a strip of full-colour RGB LEDs around it. The LEDs then react to movement, with an effect similar to a spirit level: as it tilts, a spark travels to the highest point. The spark rolls around, fading out nicely. Hardware Pretty much full bodge-city, and made in a real rush before a party. Parts: Charity shop Trilby (someone’s going to correct me that this is not an ISO standard Trilby and is in fact a Westcountry Colonel Chap Trilby, or something). Bugger it – a hat. A WS2812B strip of 38 LEDs. 38 is what would fit around the hat. Cheapo ADXL345 board. Cheapo STM32F030 board (I <3 these boards! So power, such price wow). Cheapo Li-Ion charging board and 5V step-up module all-in-one (AKA “powerbank board”). Li-Ion flat/pouch-style battery. Obviously some hot glue in there somewhere too. No schematic, sorry, it was quite freeform. The battery is attached to charging board. That connects to the rest of the system via a 0.1” header/disconnectable “power switch” cable. The 5V power then directly feeds the LED strip, from Cortex-M0 board (which then generates 3.3V itself). The ADXL345 accelerometer is joined directly to the the STM32 board at what was the UART header, which is configured for I2C: The STM32 board is also stripped of any unnecessary or especially pointy parts, such as jumpers/pin headers, to make it as flat and pain-free as possible. The LED strip is bent into a ring and soldered back onto itself. 5V and ground are linked at the join, whereas DI enters at the join and DO is left hanging. This is done for mechanical stability, and can’t hurt for power distribution too. Here’s the ring in testing: The electronics are mounted in an antistatic bag (with a hole for the power “switch” header pins, wires, etc.), and the bag sewn into the top of the hat: The LED ring is attached via a small hole, and sewn on with periodic thread loops: Software The firmware goes through an initial “which way is up?” calibration phase for the first few seconds, where it: Lights a simple red dotted pattern to warn the user it’s about to sample which way is up, so put it on quick and stand as naturally as you can with such exciting technology on your head, Lights a simple white dotted pattern, as it measures the “resting vector”, i.e. which way is up. This “resting vector” is thereafter used as the reference for determining whether the hat is tilted, and in which direction. Tilt direction vectors The main loop’s job is to regulate the rate of LED updates, read the accelerometer, calculate a position to draw a bright spark “blob”, and update the LEDs. The accelerometer returns a 3D vector of a force; when not being externally accelerated, the vector represents the direction of Earth’s gravity, i.e. ‘down’. Trigonometry is both fun and useful Roughly, the calculations that are performed are: Relative to “vertical” (approximated by the resting vector), calculate the hat’s tilt in terms of angle of the measured vector to vertical, and its bearing to “12 o’clock” in the horizontal (XY) plane. Convert the bearing of the vector into a position in the LED hoop. Use the radius of the vector in the XY plane as a crude magnitude, scaling up the spark intensity for a larger tilt. All this talk of tilt and gravity vectors assumes the hat isn’t being moved (i.e. worn by a human). It doesn’t correct for the fact that the hat is likely actually accelerating, rather than sitting static at a tilt but, hey, this is a hat with LEDs and not a rocket. It is incorrect and looks good. Floating-point I never use floating point in any of my embedded projects. I’m a die-hard fixed-point kind of guy. You know where you are with fixed point. Sooo anyway, the firmware uses the excellent Qfplib, from https://www.quinapalus.com/qfplib-m0-tiny.html. This provides tiny single-precision floating point routines, including the trigonometric routines I needed for the angle calculations. Bizarrely, with an embedded hat on, it was way easier using gosh-darnit real FP than it was to do the trigonometry in fixed point. Framebuffer The framebuffer is only one dimensional :) It’s a line of pixels representing the LEDs. Blobs are drawn into the framebuffer at given position, and start off “bright”. Every frame, the brightness of all pixels is decremented, giving a fade-out effect. The code drawing blobs uses a pre-calculated colour look-up table, to give a cool white-blue-purple transition to the spark. Driving the WS2812B RGB LEDs The WS2812B LEDs take a 1-bit stream of data encoding 24b of RGB data, in a fixed-time frame using relative timing of rising/falling edges to give a 0 or 1 bit. The code uses a timer in PWM mode to output a 1/0 data bit, refilled from a neat little DMA routine. Once a framebuffer has been drawn, the LEDs are refreshed. For each pixel in the line, the brightness bits are converted into an array of timer values each representing a PWM period (therefore a 0-time or a 1-time). A double-buffered DMA scheme is used to stream these values into the timer PWM register. This costs a few bytes of memory for the intermediate buffers, and is complicated, but has several advantages: It’s completely flicker-free and largely immune to any other interrupt/DMA activity compared to bitbanging approaches. It goes on in the background, freeing up CPU time to calculate the next frame. Though the CPU is pretty fast, this allows LEDHat to update at over 100Hz, giving incredibly fluid motion. Resources Firmware sourcecode: https://github.com/evansm7/LEDHat