I’ve been working on Otium which is a project of mine to make a little anachronistic retro computer. As part of that, I want to make an operating system which is not Linux or BSD sized or capable but does supply some of the trappings of a modern operating system and computer like multitasking and graphics.

pictured: not this operating system

#Wherein I take a lot for granted

As part of that, I’ve been trying to wrap my head around what it is that an operating system does.

If I were to try to concisely summarize what I’ve learned so far, an operating system lets user programs make simplistic assumptions about how things work that are ultimately not true. For example:

• Resources are infinite
• Code runs sequentially
• Storage devices work like a dictionary with keys and values

One thing that this project has driven home for me is that a lot of work goes into letting programs make those assumptions.

The operating system code doesn’t get to make them; at some point it has to make a judgment call about e.g. how much memory a process can take up (including the overhead of bookkeeping the program’s state within the operating system).

This is a combination of static decisions (what’s the maximum length of a process’s name) and heuristics that need to manage a dynamic system while keeping it healthy: what happens when a process freezes or starts to consume lots of resources, and so on.

#Filesystems in a microkernel

I’ve been trying to approach the problem of adding support for the one of those illusions — files — to the operating system. I say approach because it’s opened a can of worms and I have yet to get to the actual filesystem part.

I’m implementing a microkernel. There’s a lot of good writing about microkernels vs. monolithic ones, but I have two project-specific reasons:

• I’d like it to be possible to develop portions of the operating system on itself, such that e.g. the filesystem driver could be altered on the fly.

• The more pertinent reason right now is that I’m not very good at this and I’m writing code with errors a lot. In a microkernel, I spend more time writing code out of the kernel and the kernel doesn’t crash when my code does.

  Then I have a lot more normal forensic options like printf-debugging and an interactive shell for figuring out what goes wrong.¹

pictured: this operating system

One microkernel-y way of doing files: the filesystem is just a program. Programs that need files send messages to the filesystem, it does the filesystem-y things and responds with the results of file operations.

The kernel and other programs don’t need to know about block storage devices or how they work, the filesystem can crash horribly and the system (except for the parts of it that need files) continues to function.

My starting point has been the lovely OS in 1,000 lines tutorial. After the 15th section, you have a system that can run multiple processes with their own virtual memory, and has one userspace executable written in C linked into the kernel.

So I needed to add a few things to the operating system:

• Multiple user programs with differing behavior
• Programs need to be able to discover each other
• Programs need to be able to send messages to each other

Great, easy.

#Problem 1: Resources are not infinite

I also started tracking the memory usage of the operating system. My goal is to eventually run this on an RP2350 board, so it’ll have on the order of a couple megabytes of memory.

Naively running multiple programs means a lot of duplicated memory. I already had a small but growing library of functions for the userspace supplying functionality like malloc and printf, and loading up multiple copies of it didn’t make sense.

I didn’t want to complicate the build, though, so I stuck with the single separately compiled user program. I still needed to figure out how to share code between multiple instances of that process. My implementation is fairly trivial.

Since I only have one big blob of user code, I was able to punt on a few things.

We just need to make sure that code and read-only data are shared between all user processes. We don’t need to worry about freeing that shared memory through some sort of reference counting scheme because as long as the system is running then it is definitely needed.

Even with that in place, I had to make some random choices about how much memory to give a process. Each process gets its own 32KB user stack, 8KB kernel stack, and a couple pages allocated for various internal purposes. Is that about right? I guess I’ll find out!

I also learned there’s a number of optimizations you can make, like using a shared kernel stack.

#Problem 2: Passing arguments to processes

I needed a way to make the program behave differently in different invocations. The kernel can put whatever it wants into the program’s memory, so that’s not too hard.

I added a page of memory specifically for program arguments, and a syscall for the program to discover it. Now the program gets a list of string arguments just like it would on a POSIX system, and the first one of those is the program name. So we can have a shell program and an fs program.

Except here I got unhappy that I was writing some ad hoc janky binary serialization/deserialization in both my kernel and user program to handle the argument strings.

Pair<uintptr_t *, uintptr_t *> argc_ptrs = allocator.alloc<uintptr_t>();
*argc_ptrs.first = args->argc; // Write to physical

// Allocate argv array - write to physical, get virtual for storage
Pair<char **, char **> argv_ptrs =
    allocator.alloc<char *>(args->argc * sizeof(char *));

for (size_t i = 0; i != args->argc; i++) {
    size_t len = strlen(args->argv[i]);
    // Allocate string - write to physical, store virtual in argv
    Pair<char *, char *> arg_ptrs = allocator.alloc<char>(len + 1);
    arg_ptrs.first[len] = '\0';

    memcpy(arg_ptrs.first, args->argv[i], len); // Write to physical
    argv_ptrs.first[i] = arg_ptrs.second;       // Store virtual in argv
    oprintf("arg %d %s (paddr %x, vaddr %x)\n",
     i,
     arg_ptrs.first,
     arg_ptrs.first,
     arg_ptrs.second
   );
}

Ick. You can see the printf-debugging I was doing because it took me a couple tries to get it to work. Plus you can imagine this startup page gaining more functionality over time, like environment variables.

So I stopped to add msgpack, a sort of JSON-esque binary serialization format to the kernel. Now the arguments page is a msgpack message:

MPackWriter msg(buffer, OT_PAGE_SIZE);

msg.map(1).str("args").stringarray(args->argc, args->argv);

Aside from making the immediate code better, this also feels like a pragmatic choice because it makes it easy to pretty-print the contents of this and other communications between the kernel and userspace at any point. Even more, even easier printf debugging of what’s going on.

#Problem 3: What even is message passing

After dealing with this I was ready to add message passing. It was then that I remembered I don’t actually know how to do that.

Turns out there’s quite a few decisions you need to make at this point:

• Are the APIs synchronous or asynchronous? Does a process totally block while waiting for messages?

• What format do the messages have?

• Is there a fast path for smaller messages that can fit into a couple of machine registers?

• In the case of large messages, how do they get shared around? Is there a shared memory mechanism for processes to talk to each other, or does the kernel copy things around?

• The code for types, encoding and decoding of messages. Is it all written by hand, do you use a code generator?

Fortunately there’s a number of good small microkernels that can be studied; Resea is a cool one from the author of the OS1K tutorial. L4 has produced a lot of research and descendants. After reading some of these I felt I at least had a handle on the problem.

Making things up as I went along, I ended up with the following API:

/** Look up a process's PID by its name.
    Returns zero in case of failure. */
int ou_proc_lookup(const char *name);

/** Given a message index, get the address
  * of the page where the message can be read. 
  * Returns null in case of failure. */
PageAddr ou_get_msg_page(int msg_idx);

/** Return the count of messages waiting
  * for a process. */
int ou_ipc_check_message(void);

/** Send a msgpack message in the 
  * communication page to the given process PID.
  * Returns zero in case of failure;
  * an extended error message will
  * be available in the communication page. */
int ou_ipc_send_message(int pid);

/** Pop the most recent message off the stack */
int ou_ipc_pop_message(void);

So we have a basic asynchronous design. Sending a message causes the kernel to copy the communication page (essentially a scratch buffer for communications between the kernel and user program) to the memory of the receiving process. The communication page is assumed to have a valid msgpack message.

The receiving process needs to poll ou_ipc_check_message inbetween doing other work to check for messages and then deal with them, then pop those messages.

There’s a couple of decisions here that may or may not pan out:

• There is no fast path for small messages and using msgpack for the messages might add quite a bit of overhead.

• Currently we hard cap the number of messages that a process can have waiting for it at 16, because it requires allocating memory dynamically for that process.

  This means if a process does not clear its queue while messages accumulating, message sending will start to fail. For core functionality like filesystems and graphics this would make the system unusable even if not technically crashed.

• Right now each of those messages gets a page, so we use up to 16*4KB of memory for messages that are in practice much smaller than that.

• Writing asynchronous code by hand like this correctly is hard.

I’ll likely have to revisit all of these pretty shortly. Some are just placeholders, but others like synchronous v. asynchronous and how to format messages are core design decisions that will require all user code to be updated should they change.

#The black triangle moment

At the end of all this though, I was able to make a black triangle; a separate program that responds to all messages by printing them to the console. The shell of the operating system can be used to send any message:

print-server ready
tcl shell ready
> set pspid [proc/lookup print-server]
result: 2
> mp/string "Hello, world"
result:
> mp/send $pspid
result:
print-server: got message, msg count: 1
> printing message received
"Hello, world"

This looks up the process ID of the print-server, constructs a messagepack message in memory (in this case just the “Hello world!”) string and then sends it, resulting in a separate process printing it out.

This works on the web demo at the moment.

#Maybe now we can add a filesystem

It is hoped that after all this I can write an actual filesystem driver and have code read/write files. Which is probably super easy, right? Wish me luck.