Sunday, July 17, 2011

Build your own operating system

Ten years ago (around the year 2001) I wrote a simple x86 protected-mode OS just to find out how operating systems work. That was really great fun and I learned very much about OS concepts and paradigms (and also a lot of stuff about computer hardware, programming, software architecture, data structures etc.). Ever since the gathered experience and knowledge by building my own operating system has been extremely valuable.

I began by reading Andrew Tanenbaum's book "Operating Systems: Design and Implementation" during which I studied a lot of Minix source code. Later I also read his other books about modern operating systems and structured computer organization.
To get started with this challenging task, one needs some profound knowledge of the memory-management-unit (MMU) of the x86 CPU and its protected mode. To me, the best known tutorial on the web is the "Protected Mode Tutorial" by Jens Hohmuth of the Westsächsische Hochschule Zwickau. Sadly, this tutorial is only available in german. If you do not speak german you may try to translate it with Google Translate. The best parts of the tutorial are its great assembly language examples for Borland's TASM and Microsoft's MASM. I typed in all the examples by hand and played with them until I understood every single line of code :-). What is also helpful to understand the MMU and protected-mode of the x86 CPU is Intels Architecture Software Developer’s Manual and Hans-Peter Messmer's book The Indispensable PC Hardware Book.

The protected-mode tutorial starts by explaining how virtual addresses are mapped to physical addresses using the x86 MMU's two-level page table. Thus one will understand how a modern OS implements the process address spaces and how it protects processes from each other. You should also get the idea about how the OS lays out executables and shared libraries within the process address space and how it creates shared memory regions.
Two core abstractions of every modern OS are processes and threads. The multitasking chapter of the tutorial will give you some insights on how an OS may implement them for the x86 CPU. Therefor, the examples of the tutorial use segment descriptors and task state segments. The Global Descriptor Table (GDT) contains segment descriptors for the code, data and stack segments of a process. A Task State Segment (TSS) is used by the examples to implement a process (with one thread) on the x86 CPU. Each process or thread has a context which includes the code, data and stack segments, its program counter, a reference to its page table, etc.
Be aware, that modern OSes do not use disjoint segments anymore. They use a flat memory model where all x86 segments refer to the same virtual address space. The virtual address space is build using the MMU's two-level page table as explained above. Also be aware that e.g. Linux or Windows do not do hardware context switches using different task state segments. Instead they just create one TSS per CPU and do the switching stuff by themselves (see [1] and [2]). But if you understand the tutorial examples you will also get what Linux and Windows are doing and how they are doing it.
A modern OS kernel securely offers its features to user space programs via the system call interface. Since the system calls are the only valid entry points into the kernel for user space programs it is only possible to call them using special CPU features. Depending on the CPU architecture this may be done by call gates, special assembler instructions like syscall, or software interrupts.
Monolithic operating systems usually have a lot of system calls to offer a bunch of features to user mode programs while microkernel operating systems normally only have a minimal set of system calls. Hence, microkernel operating systems implement a lot of features by supplementary user mode OS services and provide them to user mode programs using inter-process communication (IPC) mechanisms.
Interrupts and exceptions are managed and handled on the x86 CPU using the Interrupt Descriptor Table (IDT). E.g. the timer interrupt triggers the scheduler from time to time to switch from one process to another to achieve true multitasking. Another example is the page-fault exception which is the starting point for the paging mechanism available in every modern desktop or server OS. This exception is risen every time a program tries to access a memory page that is currently swapped out to disk. The OS handles it by mapping the missing memory page back into the process address space before it executes the process again.

The protected-mode tutorial closes with a really great multitasking example where four processes draw pretty cool animations onto the display in VGA graphics mode (click here for the source code). Here is how this example x86 protected-mode OS looks like by running it from the MS-DOS mode of Windows 98 SE:

With the profound knowledge about the x86 protected-mode you should be able to start writing your own hobby OS or to understand what is going on under the hood of a Linux, Mac OS X, Windows or QNX Neutrino operating system.
I have put all the source code from the protected-mode tutorial and a simple boot sector (bootloader) program into my blog repository.
Modern operating systems offer lots of other features we haven't touched yet like dynamic memory management, dynamic linking, file systems, networking protocol stacks, etc. But once you have understood and implemented the core OS concepts you could evolve your OS step by step or you may start developing code for one of the well-known operating systems.

To dig deep into modern OS design and architecture I suggest the QNX Neutrino OS Architecture Guide. It provides a lot of insights into microkernel operating systems, IPC, the process manager, dynamic linking, resource managers and device drivers, networking, priority inheritance and much more interesting stuff. You may also take a look at Microsoft's Singularity research OS.
If you want to get familiar with the Linux operating system I recommend the books Professional Linux Kernel Architecture by Wolfgang Mauerer and Linux Kernel Development by Robert Love.
For Mac OS X enthusiasts I would suggest Mac OS X Internals by Amit Singh. People who are interested in Windows might like Windows Internals from Mark Russinovich and David A. Solomon.
You should also take a look at Google's Android operating system. It has a neat and scalable architecture where a monolithic Linux kernel is extended by a really nice inter-process communication (Binder IPC) and software component framework. Above the Linux kernel Google's Android looks very much like a microkernel OS that is similar to the QNX Neutrino RTOS. Another microkernel OS that is very interesting is Miray's Symobi. I worked at Miray Software on the Symobi project some years ago where I build the networking protocol stacks and the USB device management OS services from scratch. So I really like the Symobi OS which is similar to the QNX Neutrino RTOS.

Oh, by the way you now also know how the two OS security concepts Data Execution Prevention (DEP) and Address Space Layout Randomization (ASLR) work. The DEP is a feature of the x86 MMU where each page table entry has an additional NX bit, e.g. to mark stack and data pages as not executable.
The ASLR feature affects the layout of executable programs and shared libraries within the process address space.

Some more links about operating systems and related topics:
My Blog Repository
Assembler Programming Topics
"Get into protected mode, enable paging, do something useful, get out again" by David Lindauer
Protected Mode Basics by Robert Collins
The LOADALL Instruction by Robert Collins
A Memory Allocator by Doug Lea
Doing a Kernel in C++
Making plain binary files using a C compiler (i386+)
Skelix OS Tutorial (Protected Mode)
Intel Architecture Software Developer’s Manual
i386 Atomic Operations
Mixing Assembly and C
Writing a Kernel in C
Writing Your Own Toy OS (Part I)
Writing Your Own Toy OS (Part II)
Writing Your Own Toy OS (Part III)
BareMetal OS
MMURTL aka Developing Your own 32-Bit Operating System by Richard A. Burgess
Miray Symobi
Can We Make Operating Systems Reliable and Secure? by Andrew S. Tanenbaum
Executable and Linkable (ELF) File Format
Portable Executable (PE) File Format
ARM Architecture Reference Manual
ARM Processor MMU

Friday, July 1, 2011