XANA & iX: A history & post-mortem of two small operating system projects

XANA & iX: A history & post-mortem of two small operating system projects

In 2007, after years of reading about OS development & writing only toy projects in that vein, I wrote my first ‘serious’ small OS — serious in the sense that it used protected mode, had a filesystem, & had a marginally-usable UI. Three years later, I wrote another OS incorporating the lessons I learned from the first. Both of these projects are failures as usable OS projects but successes in other ways.

I’d like to describe them, briefly, in case they might be of interest to other aspiring osdev hobbyists (if only as a warning). I’d also like to describe them in order to indulge in a bit of reminiscence: writing OS experiments is time-consuming, even when they are this small, and while I found the experience enjoyable, I no longer have the spare energy to work on such things — full-time employment has made it impossible.

Both of these projects incorporated Project Xanadu ideas as I understood them at the time. My understanding of these ideas was largely incorrect. For an accurate overview of them from a technical perspective, I recommend reading my essay on the subject. I will not be covering the actual concepts I mis-understood except shallowly (to illuminate the ways in which my implementations differed from them).

The history I sketch is from memory, and I haven’t made an effort to verify beyond looking at commit history. So, circumstances I describe are largely a description of my understanding at the time, filtered through a decade of working on other things — and at the time I worked on these projects, I was both substantially greener as a developer and perpetually sleep-deprived. If there aren’t errors in the chronology of external events, or outright misunderstandings of them, I would be very surprised.

2007: Project XANA

Someone in the freenode #d IRC channel, Alexander Panek, began work on an OS kernel in D some time in 2006 or early 2007, then abandoned it. In early 2007, having been interested in OS development for some time, I read the kernel-in-progress (which consisted of a multiboot header in D, maybe a hundred lines of assembly for getting from the bootloader to an entry point and a small module for VGA text) and ported it from the Digital Mars compiler to GDC (a then-third-party patchset adding D support to GCC).

This was around the time that a major version of the language had been released, and GDC was playing catch-up; I was running a source-based distro, and couldn’t easily get the Digital Mars binaries to run on it. At the same time, as a related but theoretically-separate effort, lots of people were jumping from the default standard library (phobos) to a new replacement standard library (which I believe was called deimos), and I was unable to get deimos to work with my GDC install (although I also didn’t understand why people preferred it — it had features whose use I didn’t comprehend). I had been hanging out in the channel for months but writing only toy programs (and probably not even compiling the ones I wrote). However, I graduated high school in January or February of that year & began taking a handful of classes at a nearby university, and this gave me enough time to dive head-first into the language.

Almost all of the original D code for the kernel ended up being rewritten: the assembly code was rendered unnecessary by GRUB (though I also wrote my own bootloader at some point in the development), and the remaining D code was in VGA module features for things like smooth scrolling that didn’t match my display model or for things like wrapping single GDT/IDT-interface instructions (which might have worked with DMD-generated code but wouldn’t work with GDC-generated code because the registers got filled with unrelated data). However, the brunt of the work actually occurred before getting anything to boot.

It’s unclear to what extent DMD generated code that was actually dependent upon Phobos (or Deimos). However, this version of GDC emitted endless references to Phobos routines, and so D code was used internally even for things you might expect to have no dependencies; furthermore, this D code had dependencies on libc routines, many of which were provided by the OS. For instance, D has optional garbage collection, and all of the garbage collection routines are in D itself — so declaring a variable depended upon malloc, hashing functions, syscalls to get the time, and a variety of other unexpected things. I spent weeks doing nothing but commenting out parts of Phobos and replacing them with mocks that return static values.

Eventually, with the help of a couple math-related routines from a public-domain-licensed all-assembly-language libc implementation & a couple headers taken from GCC itself, I got a kernel that could build & display words on a screen. Mostly, I got a strong lesson in separation of concerns: it is very difficult to extract OS and libc dependencies from a complex high-level library that was never designed to make such an extraction straightforward. The phobos code I could read was deeply entangled with generated code I couldn’t, which had C dependencies I couldn’t predict, and rewriting large portions of the libc was not in the cards. After all, I had taken up the task of writing the first OS in D, and so it simply wouldn’t do to have the codebase be mostly C and assembly, even at an early stage!

(Luckily, Phobos was also public-domain licensed. My changes were ad-hoc but substantial enough that they couldn’t easily be applied at build-time, particularly to a moving target: I essentially had my own broken, gutted phobos fork.)

Being a giant dork, I named my kernel Project XANA — a combination of Project Xanadu (with which I had been obsessed for at least four years already) and XANA, the antagonist of the mediocre french animated children’s television show Code Lyoko (which I didn’t watch, but which I respected on the grounds that shows about virtual reality were relatively thin on the ground).

Once I got the kernel running, I implemented keyboard support, which required modifying the IDT (and thus the GDT). I had switched to GRUB by this point, since my bootloader, which did the switch into protected mode itself, couldn’t read the kernel’s symbol table & therefore couldn’t jump to a non-static address. Since GRUB had set up the IDT and GDT initially during its switch into protected mode, I hadn’t needed to work with them since the switch, and writing a full IDT in D ended up being relatively difficult: the tricks that the author of the original code I was working off of (now mostly rewritten anyhow) didn’t work in GDC (if they ever did in DMD — considering the absence of a similarly gutted Phobos in that project, probably not), and so I had to invent my own. Getting the keyboard working was probably a few weeks’ worth of work on the grounds that, rather than looking things up, I was working by trial and error.

At this point, high on having something working, I started dumping Xanadu concepts into the design.

Since the kernel at the time produced a file named ‘stage2’ (after grub’s stage1 and stage1.5 files), I broke development into stages: the kernel up to this point was ‘stage2’, while the next stage, which implemented a document storage system, was ‘estage’ (‘e’ for ‘enfilade’). I actually didn’t use enfilades — I had tumbler-indexed hash tables, with a custom hashing algorithm that was so slow that it ended up being worse than linear search. I also implemented a document system with span-to-span hyperlinks. I had to reintroduce previously-removed parts of phobos in order to make any of this work.

Then, I implemented an interactive frontend. Keeping with the Code Lyoko theme, I called it Aileta (after one of the protagonists, who was probably named after Alita, Princess of Mars). I took inspiration from ZigZag & from the PlayStation 3’s “cross-bar” menu system, and treated the first character of any document as an icon for that document. (I had set up keyboard input handling so that control+character produced the character with the ASCII code of that character minus 92, and chose to display control codes, so the graphic & line-drawing characters prior to ASCII 65 were easily accessible, though one would need to memorize them.) The first forward- and back-links were used to arrange the document icons into a navigable cross-shaped menu.

After implementing this, I started work on hard disk support, which required writing PIC and IRQ manipulation code. I made the disk map directly to the in-memory structure used for the document storage structure, which ultimately meant making a wrapper for disk routines that, to an outside observer, looked like a byte array or a void pointer. These routines never got a workout on a real disk — only in emulation. I was able to happily trigger formats (which took in excess of half an hour) but I never tested reading from this structure after a reboot. I also brought in a full Lua implementation and removed system & libc dependencies — the idea being that Lua code in documents would be the primary way of developing within the system.

Ultimately, this project was a mess: to the extent that it was functional, it was unusably slow; it suffered from the use of a very high-level language (which needed to be tamed), and while it made use of some of the features provided by that language, it was limited in the use of those features by functionality that needed to be removed. In only a few cases was the use of D beneficial: VGA manipulation was nominally easier than in C because of the module system and because structs act as pseudo-objects with member functions not mapped to allocated memory, and making a hard disk look like a byte array, while it wouldn’t really be possible in C, also isn’t a particularly sensible thing to do.

Nevertheless, being able to prototype low-level structures in D made certain things easier, on a conceptual level. Many of the ideas that eventually made their way into iX were prototyped in XANA, because structures that were unthinkable to me in C were idiomatic in D, and it turned out that those structures ported back into C nicely.

XANA cannot build on modern versions of GDC or DMD. As far as I know, nobody else has attempted to write an OS mostly or primarily in D, although people write OSes in C++ all the time & would have similar problems. (I suspect that an OS written in Rust or Go would also run into these issues — whereas, with C++, there are well-understood best-practices and minimal standard libraries specifically to minimize the impact of these problems.)

2010: iX

In 2010 I took an operating systems class & remembered how much (masochistic) fun writing XANA was. So, I started writing a new OS in C, cribbing some ideas from XANA. Specifically, I translated XANA’s multiboot header back into C, copied the linker script, and did another ZigZag variation for the front-end.

Since I was writing C, I had the ability to control precisely which standard library features I wanted to use, and (in fact) to break compatibility in some cases. So, I implemented only a handful of them.

Rather than port back the IDT routines I had written for XANA, I worked off of a tutorial for OSdev in C — bkerndev. The IDT, GDT, and IRQ files are the only code in this project that I didn’t write. (Had I written them myself I would have written them in assembly. I still don’t have 100% understanding of what Bran is doing in this code or why, even though I’ve written equivalent code in assembly and in D. Replacing them while keeping compatibility was deemed low-priority.) I backported some ideas from my XANA keyboard handling code and combined them with ideas from bkerndev to produce a fairly small keyboard handler.

Once again, I made the on-disk format mimic the in-memory structure for user data, which itself was informed by the UI. However, since this was a design decision from the outset, I made sure to make the formats straightforward to implement, resistant to serialization problems. This meant having a static-length preallocated memory structure with static-length fields. (We never make new cells or new dimensions; instead, we fill in connections, or fill in pre-allocated cells. All cell content is also of a fixed maximum length, with zero termination truncating it.)

Unlike XANA’s interface, I had functional dimension-switching in iX. However, the dimensions were not named (only numbered), and I didn’t have clones, so iX is not a proper ZigZag implementation.

Rather than trying to import a conventional language, I started work on an early version of kaukactr, which was to be the internal language for development on this system. I didn’t get as far as to even write function decoding in this implementation, but the original plans would have already been mapped out by the time I wrote this code. I also integrated it into the task-switching code, which switched between tasks every jiffy and used the normal timer interrupt.

ZigZag and Kaukatcr were a good fit for an OS written in a low-level language like C: they don’t require complicated structures that benefit significantly from abstraction layers, and serialization can be made straightforward. I could have supported named dimensions, clones, and a proper/full kaukactr implementation without much effort.

iX has fairly clean code (particularly compared to XANA), although when drawing boxes and graphical structures it tends to get long & hard to read — it would benefit from refactoring, specifically with the introduction of dedicated drawing routines. I avoided using unusual C features (even if such features might be fairly common in OS dev) & tried to make the code small and clear. I didn’t implement anything unnecessary — iX is minimalist where XANA is maximalist.

Conclusion

Neither of these projects is going to storm the world. In fact, neither is even going to have the kind of small-but-enthusiastic user base that Menuet has. However, I think they demonstrate some useful ideas, some of which are at odds with recieved wisdom in OS development:

1. It’s possible and potentially rewarding to make use of high-level language features in an OS development context, provided you can minimize the runtime dependencies of those features.
2. It’s possible and potentially rewarding to write an OS as a standalone experiment in UI design, and to make the structure of the OS mirror your UI design. This is easier in minimalist systems, where irrelevant features that might make the OS usable are eliminated in favor of conceptual simplicity. The OS becomes an art project.
3. If you avoid the goals of compatibility, usability, and widespread adoption, difficult problems (task switching, filesystem design, interfacing with storage media) become straightforward.
4. There’s room for thousands of art-project OSes, in a way that there isn’t for even hundreds of UNIX clones.