Alok Menghrajani

Security engineer at Square. Previously co-author of Hack and put the 's' in https at Facebook. Maker of CTFs.

Home | Contact me | Github | Twitter | Facebook

During my exchange program at Carnegie Mellon University, I took an Operating Systems course where we had to write our own OS from nearly scratch (the OS was divided in 4 parts, and we were working in groups of 2 students). The OS was designed for the x86 architecture. This course was very interesting, and after one semester of hard work, our OS really worked !

My partner for this course was Vikram M. I really enjoyed working together, we had a lot of fun. We followed extreme programming guidelines, which means we were mostly working together, in front of a single computer. This way, while one of us was coding, the other one was checking that the overall design was correct. We would only switch to two seperate computers when we needed to test and debug the code.

tools

Our OS is about 10'000 lines of C code (and a little bit of assembly). The code was compiled with gcc.

We used a x86 emulator called simics to test our system. Simics runs on linux (other versions are also available). The advantage of using this emulator was that we didn't need to reboot the whole machine each time our code crashed.

We also used a set of operating systems components called OSKit, developed at the University of Utah.

sources of information

Our main sources of information were:

part one, 2 weeks

The goal of this part was to write 3 device drivers: a console driver (so that we can display text on the screen), a timer device (so that we can have a basic clock) and a keyboard driver.

The hard part about writing these drivers was that we were writing our first kernel code. That means we had to write bullet proof code, since there are less protections schemes. There are also some basic functionalty missing (like some string manipulation functions).

We had to understand how intel has designed the different privelege levels and segmentation.

The communication with the devices (graphics card, timer chip, keyboard) were done through I/O ports and memory-mapped I/O. The devices communicated back data by using hardware interrupts. These interrupts are caught by our interrupt handlers.

part two, 2 weeks

For the second part, we were given a kernel and we had to write a thread library, concurrency primitives (mutexes and condition variables) and a deadlock detection code for a game that uses our libary.

Our thread libary provides function to create and join threads. It uses sys_minclone (a function that creates a child process that is a copy of the calling process) provided by the kernel.

part three, 4 weeks

This was the most important part, since we wrote the kernel from scratch.

Our goals were to implement context switching (which allows us to switch from one process to another) and preemptive multitasking (which means the context switching can occur at any time since it depends on interrupts generated by the timer). We also had to implement the system calls used in the previous parts. We implemented virtual memory.

Debugging kernels is much harder than other type of code, since virtual memory and interrupts often complicate things.

One of the most exciting moments in this course was when we got our first process running. We are able to load user code in the a.out format. Because we didn't yet have a filesystem, the user code was loaded from large arrays compiled into the kernel. We used a utility called exec2obj to create these arrays.

We designed a structure called PCB (process control block), that is at the hearth of multithreading. These PCB's are stored above the kernel stacks and hold information about processes.

Context switching was mainly written in assembly. It requires us to save the state of the running process and jump back to another process.

Implementing virtual memory required us to manage which pages are allocated and which ones are free. We also need to know which pages are accessible by each process (since we don't want processes accessing each other's memory). We managed these pages by having two levels of indirection. Since each page is 4k, that means our OS can only use 16MB of RAM. We wrote some code at the context switching level in order to setup these pages correctly (the x86 handles virtual memory mapping in hardware, but needs some registers to be setup). We also wrote a page fault handler.

One of the tests we conducted was testing our thread library and game designed previously.

part four, 4 weeks

The goal of this part was to implement the filesystem.

We used our own filesystem format, so the data we write cannot be read by any other OS.

We wrote code to manage the sectors on the disk. We store information as meta data on the first sectors of the disk.

Our filesystem supports files, folders, soft links and hard links. We wrote system calls such as open, read, write and close for the user code. We also had to write code to do parse strings into nodes.

We had a buffer cache to enhance the speed of reading and writing data.

In order to ease development, we designed our entire filesystem independently of the kernel (using normal files under linux). Once we had our code working, we ported it to the kernel.

As a test case, we wrote a vi like text editor.

Prof. Dave Eckhardt