x86 Kernel

During my Junior Spring semester (s24), I decided to take CMU’s Operating System Design and Implementation course. To quote the syllabus:

Operating System Design and Implementation is a rigorous hands-on introduction to the principles and practice of operating systems. The core experience is writing a small Unix-inspired OS kernel, in C with some x86 assembly language, which runs on a PC hardware simulator (and on actual PC hardware if you wish). Work is done in two-person teams, and team programming skills (source control, modularity, documentation) are emphasized.

The course was definitely an eye-opener in terms of how much effort goes into designing & building an operating system, and taught me a lot in the process of building my own kernel. But this post will focus more on the project, than the course.

Overview

The project itself entails building a Unix-like operating system, with various system calls to manage both tasks & threads, a scheduler, a virtual memory manager, and various internal tools to help manage the status of threads.

To simplify things, I’ve decided to split the project into 4 main components:

1. Device Drivers
2. User Thread Library
3. the Kernel itself
4. Paravirtualization

Device Drivers

Part of the project entailed building drivers to manage the console, keyboard & timer. Although interfacing with these components required relatively small amounts of code, you learned a lot of about navigating the intel documentation along with the required steps needed to communicate with them.

When it came to the keyboard interrupt, you also had to ensure it was quick to complete, making use of the top-half/bottom-half abstraction. If the function wasn’t quick to send an acknowledgement, you could have problems when it comes to missing interrupts, or deadlocks, to name a few.

User Thread Library

This component of the project entailed implementing 1:1 threads (or kernel threads). We made use of system calls to create and manage threads, which involved implementing functions like:

• thr_fork
• join
• exit
• yield

One of the challenges of this component was ensuring certain interactions resulted in sane results, for example, what if a thread is exiting as someone is trying to join on it? If these situations aren’t properly accounted for, you can have outcomes which don’t really make sense, or having resources leak.

As such, part of this component was implementing synchronization objects, like:

• mutexes
• conditional variables
• semaphores
• read/writer locks

Although these tools can easily (albeit poorly) be implemented, if you want to ensure certain properties (like avoiding starvation), you’ll have to put more effort into their design. Similar to before, you also have certain interactions which you have to be careful with, and properly defend against.

Kernel

The kernel makes up the vast majority of the project, with a deadline that lasts approximately 6 weeks. It involves implementing system calls, like:

• fork
• thread_fork
• join
• exit
• yield
• make_runnable/deschedule
• new_pages/remove_pages

With an increased variety of system calls to implement, the number of “harmful” interactions increased, which meant more thought had to be put into how functions/systems were designed in order to avoid these pitfalls. To make things even more complicated, there are things which can silently fail as we are now the most privileged entity running, meaning things that should fail, might not. For example, the following would normal fail:

int main() {
    int *addr = (int *)0x0;
    *addr = 42;

    return 0;
}

However, when you are running within the kernel, this might work - after all, the kernel has full access to the entire address space.

Another large sub-component of the kernel project was the design & implementation of Virtual Memory (VM). There are only so many physical pages which can be allocated to processes, so one of the responsibilities of the kernel is the proper management of the physical frames, and how they are allocated & mapped when creating a new thread, or swapping between then. This also entailed setting the correct permissions on pages, to ensure that areas marked as “read-only” are actually read-only, or making sure that a user process can’t mess around with the kernel code/data.

An optimization we implemented here was the introduction of Zero-Fill On Demand (ZFOD) - you have one global page filled with 0s (marked as read-only), which can be used to quickly “allocate” new pages filled with 0s (make reads free). Then, when a thread tries to write, the page can actually be allocated and given to the thread.

Finally, as we were working on a uni-processor machine, we had to ensure that there was no busy-waiting. If the world isn’t ready for us to run, then we should take the necessary steps to deschedule ourselves, and let someone else run while waiting for the world to be ready.

Paravirtualization

The final component of the project involved supporting virtualization. This was done via the use of paravirtualization which made porting kernels easier.

This involved modifying the kernel to support the use of multiple segments, and to be able to differentiate between a guest kernel and a regular thread. Apart from that, new system calls had to be added to support running a guest kernel which included giving them the ability to disable virtual interrupts, and I/O wrappers.

We also had to add support for passing virtual interrupts, so that the guest kernel could receive timer interrupts and keyboard input. This let us play a game which ran under a guest kernel, that could keep track of how much time passed and could accept user-input.