Out of the Depths of x86

In this project you'll be building your own barebones, 32-bit OS kernel in different stages. This kernel won't do much, but it will take away the magic of the boot process! Your work in this project will be separated into three parts:

• A Tiny Bootloader
• A Tiny Assembly Kernel
• A Tiny C Kernel

Getting Started

Before you begin, you will want to read my article on the boot sequence here.

For this project you'll be writing some x86 32-bit assembly code. In particular, you'll be using AT&T syntax (not Intel syntax). If you're not familiar with this type of assembly, you'll want to first get up to speed by reading through this page.

Building a Dead-Simple Bootloader

Our first job is to write a very tiny bootloader that is not even worthy of its name. All it is going to do is do some minimal setup of the CPU and then print out a message on the console. It will not be actually loading an OS image from disk.

We've given you very little support code in this project, so you'll have to be resourceful. We're mostly giving you the stuff to support building and testing, but no actual code. You'll have to provide that. Your source files will need to match the names we require though, and I'll point that out when necessary.

Writing the code

You'll first want to create a file named bootloader.S in your project directory. This will contain our assembly code. We first have to deal with the fact that since we're writing code that will run when the machine first comes up, the CPU will be in 16-bit mode (real mode). To tell the assembler that we'll be running in this environment we have to put an assembler directive in our code like so:

.section .text
.code16
.globl _start
_start:

The first directive simply says that the code that follows should be assembled into the .text section of the final binary. The .code16 directive tells the assembler that the CPU will be running in 16-bit mode when this code executes. The next two lines create a label called _start and export it (using the .globl directive) so that the assembler can find it. Now we're ready to start writing boot code.

Unfortunately, real-mode on x86 is a pain because it relies on segmentation. If you haven't read the OSTEP chapter on segmentation, go do that now. Now, we know that the BIOS is going to drop us (the bootloader code in the MBR) at address 0x7c00. We need to set up our data and stack segment registers to reflect that, so that memory addresses will be relocated properly:

movw $0x7c0, %ax
addw $0x20, %ax
movw %ax, %ss
movw $0x1000, %sp

This chunk of code is setting up our stack segment register. We're going to assume that our temporary boot-time stack (which we will need later) will be right after that MBR (at address 0x7e00). The first three lines are setting this up. The key in the first three lines is that stack addresses will be generated by taking the value in %ss, left shifting by four, and adding the result to a stack address. Thus %ss gets the value 0x7e0. This represents the base of the stack. For our purposes, the stack will grow down, so we set the stack pointer to point at the base plus a 4KB offset, which is why we put 0x1000 in %sp. Remember, this address will have 0x7e00 added to it, so %sp will contain 0x8e00.

Once this is done, we need to also set up the data segment. This is a bit easier:

movw $0x7c0, %ax
movw %ax, %ds

Now that we have our segments set up, we can start to reference data, specifically a message that we're going to print to the screen. Let's just drop the code here and figure it out:

.set OFFSET, my_msg - _start
movw $OFFSET, %si

movb $0xe, %ah
mov $0, %dx

print_loop:
	lodsb
	cmp $0, %al
	je done
	int $0x10
	jmp print_loop

done:
	hlt
	jmp done

my_msg:
	.asciz "Hello from the bootloader!\n"

At a high-level, this code is printing a message to the screen. Why so cryptic? Well, remember we're just a bootloader. We don't have any device drivers, and we don't really wan't to implement one. What we can do though, is leverage the fact that after the BIOS loaded us, it sticks around and provides some utility routines for us. These are often called BIOS calls. You can think of them like system calls, but there is no privilege change. It turns out the BIOS has just such a call to print a character to the console. The way we invoke one of these calls is by putting the BIOS call identifier (in this case 0xe) in the high portion of the A register (%ah) and then triggering a trap using the int instrcution (also called a software interrupt on x86) at the "BIOS call" trap vector (in this case 0x10). Keep in mind all these instructions fit inside of the MBR in the first sector of the disk! The first four instructions are essentially some hackery to figure out where our message is relative to where our code was loaded. This makes use of the .set assembler directive.

The third line sets the BIOS call number, and the fourth clears out %dx, which we'll be using for our print routine. Now, this BIOS call will only print one character to the screen, so we have to write a loop to print out an entire string. This is the purpose of print_loop. The first instruction (lodsb) loads a character to %al from memory at an address derived by adding the contents of the %si register to an offset held in an index register (%dx). It also automatically increments the contents of that index register after the load. So our loop copies a character to %al, and checks if it is the null terminator (the value 0). If it is non-zero, it calls the BIOS to print that character. Otherwise, it jumps to the done label, which executes the halt instruction in a loop.

That's all the code we need, but we're not done yet! We have to remember that this code lives within the MBR, which has a well-defined format. Namely, the first 446 bytes contain bootloader code (the code we've been writing), those are followed by a partition table (which we don't care about now), and then 2 very special bytes. In particular, in order to make sure the BIOS sees this as a valid MBR, we have to put a magic "cookie" in the last 2 bytes. This is just a special value, or a signature if you like. The value we need is 0xaa55. So we add some code to fill out the final bytes of our MBR:

remainder:
	.set MBR_REMAINDER, 510 - (remainder - _start)
	.fill MBR_REMAINDER, 1, 0x0
	.word 0xaa55

These are all assembly directives. The first sets a variable containing the number of bytes we need to fill up the partition table segment of the MBR. Since we don't know exactly how many bytes the code we wrote takes up, we play some label arithmetic trickery to get that number indirectly. The whole MBR is 512 bytes, we reserve two for the last 2 cookie bytes, and then we subtract out the code size (remainder - _start). The .fill command then sets that many bytes to zero. Finally, we place the two-byte MBR magic cookie with the .word directive.

That's it! You should now try to build and run this code. We need to send this through our assembler and linker first (using the GNU as assembler and ld linker) to generate a fake disk image with our code in the first 512 bytes:

[you@fusion] as --32 -o bootloader.o bootloader.S
[you@fusion] ld -m elf_i386 -Ttext 0x7c00 --oformat binary -o bootloader.bin bootloader.o

We can then boot using QEMU with our disk image:

[you@fusion] qemu-system-i386 -nographic -drive file=bootloader.bin,index=0,media=disk,format=raw

You can also carry out these steps by using the Makefile, specifically by using make bootloader.bin and make run-bl, respectively.

If everything went right, you should see your string printed to the console.

You're done with the first part; congratulations on your first bootloader! Now if this were a real bootloader, we'd have to have some code that read either a kernel or a second-stage bootloader from disk (using more BIOS calls to grab sectors from the drive). This is more tedious than it is interesting, so we'll reuse an existing bootloader in the next part to do that for us to get us on our way to a kernel.

Building a Kernel

Now that we know how to initiate the bootup sequence, we'll assume that our bootloader has loaded our kernel into memory, and we need to execute some assembly. What we'll end up with is the same (something printing to the console), but it will be in an OS kernel instead of the bootloader. The biggest part that will change is the build process.

GRUB

In the old days, when you wrote an operating system, you'd also have to write your own bootloader as well. These days, things are a bit easier due to efforts to make flexible and free bootloaders. By far the most notable is GRUB (GRand Unified Bootloader). These days GRUB will not only load your kernel into memory, but will also set up the machine for you (e.g. by bringing the machine into protected (32-bit) mode and doing all the nasty segmentation setup) to some extent. In order for it to be able to do this, however, your kernel image must be formatted in a very particular way, much like the MBR before.

Multiboot

Enter the Multiboot standard. This is a booting interface. It is essentially a contract between OS kernels and bootloaders that, when met, will allow the above process to occur without a hitch. For the bootloader (GRUB) it means loading the kernel in a particular way, setting up the CPU to be in an agreed-upon state, and loading registers with very particular information before jumping to the kernel. For the kernel, it means that your kernel image must have a special Multiboot header in a special place.

Hacking it up

Back to assembly. You should create a file called lowkern.S. We can now write some more unconstrained assembly code (though we won't need to here) since we won't be confined to a few hundred bytes of MBR space. Our kernel can be pretty much as big as we want, but we must meet the Multiboot specification. In particular, we'll be meeting the version 2 spec, and version 2 of GRUB (which implements the bootloader half of the spec).

The main thing the spec tells us is that we must have a special header. We'll create a special section just for it:

.section .multiboot_hdr
.set MULTIBOOT_MAGIC, 0xe85250d6
.set ARCH, 0x0

multiboot_hdr:
	.long MULTIBOOT_MAGIC
	.long ARCH
	.long hdr_end - multiboot_hdr
	.long -(MULTIBOOT_MAGIC + (hdr_end - multiboot_hdr))

	/* no special tags */
	.word 0, 0
	.long 8

hdr_end:

The first line creates a special section in the program binary that we will make appear at the beginning of the binary (more on that soon). The .long directives place 4-byte values. As you might have already guessed, MULTIBOOT_MAGIC is a special cookie telling the bootloader that this is a Multiboot-compliant kernel. The ARCH value is used to tell the bootloader what architecture the kernel is compiled for, but this isn't strictly necessary, so we just put 0 there. The next value is the length of the Multiboot header, which we again calculate using some label arithmetic. The next value is a checksum which ensures that the header has not been corrupted. The next two directives tell the bootloader that we're not requesting any special information from it. So much for the header. Now we can start writing kernel code!

We must tell the linker that everything now will go in the normal code section:

.section .text

.code32

.globl kernel_entry
kernel_entry:
	movb $'O',  0xb8000
	movb $0x0f, 0xb8001
	movb $'K',  0xb8002
	movb $0x0f, 0xb8003

end:
	hlt
	jmp end

Note that since GRUB will bring the machine out of real mode and into 32-bit mode for us, by the time it jumps to us we should be using 32-bit instructions! We tell the assembler that this is the case using the .code32 directive. Now we start writing our kernel code. Here we're printing out characters to the screen, but we're doing it in a different way. We're actually painting characters to the screen by copying bytes to a framebuffer. This is a basic mode of operation that every graphics device must support. This framebuffer happens to always be mapped at physical address 0xb8000 on PC hardware. Remember, the memory controller makes sure that our stores to this address don't go to RAM address 0xb8000, but rather to somewhere in graphics memory. The graphics card then converts these bytes into pixels and sends them out to the display. Why do we have more than just 2 writes? Well, the framebuffer isn't just single bytes, but rather pairs of bytes. The first of the pair indicates the symbol to appear, and the second byte determines its attributes. The attribute I'm providing here (0x0f) means "white on a black background."

Linking and Loading

Now that we've written the code for our kernel, we have to generate an image from it. We can't just run this through our assembler, because we need the sections we made to appear in the write place. Normally when you compile code (e.g. a simple C program using gcc), the binary executable is generated in a default way. The linker is in charge of generating this image, and it follows a well-defined format on UNIX systems called ELF. Windows systems use a different format. The ELF format is what determines how different code and data sections are laid out on a binary file after code is compiled and linked. The details aren't too important to us, but we need to make sure that that special section we created appears at the very beginning of our ELF binary for our kernel. To do that, we'll need to create a linker script.

The linker script tells the linker how to place executable code in the binary file it generates. It's very useful when building code for embedded microcontrollers or writing operating systems. Create a file called kernel.ld. We'll need to add a few things:

ENTRY(kernel_entry)

SECTIONS {
	. = 1M;
	
	.boot :
	{
		*(.multiboot_hdr)
		boot_stack_start = .;
		. += 0x1000;
		boot_stack_end = .;
	}

	.text :
	{
		*(.text)
	}
}

The ENTRY() directive tells the linker where the entry point of our code is. This is the first instruction in the code that will execute. This tells whoever is loading the binary (the bootloader for our purposes) where they should jmp after loading. The SECTIONS directive tells the linker how to lay out the various sections. We first set the loading point to 1MB in the first line. We do this because a Multiboot bootloader will always load the kernel at 1MB. The next part creates a section called .boot and puts the contents of our header into it. We then tell the linker to lay out some space (exactly one page) for our boot-time stack, and create symbols which point to its beginning and end so that we can reference it in our code later on. We then tell the linker to lay out the code segment after that.

Hello Kernel

We should now be able to build our little 32-bit assembly kernel:

[you@fusion] gcc -ffreestanding -nostdlib -m32 -o lowkern.o -c lowkern.S
[you@fusion] ld -T kernel.ld -m elf_i386 -o lowkern.bin lowkern.o

The -ffreestanding and -nostdlib flags tell the compiler that it shouldn't assume a C runtime is available, and shouldn't assume access to the C standard libraries. The -m32 flag indicates that we're compiling 32-bit code. We then invoke the linker (ld), and tell it to use our special linker script with the -T flag, and again specify 32-bit. We now have a kernel image. We've provided a shorthand for these steps for you in the Makefile as well (make lowkern.bin).

You can verify that our special boot section has been created by running:

[you@fusion] readelf -SW lowkern.bin

We can't boot this binary directly, however. We need to generate a little root filesystem that GRUB can load the kernel from. Luckily, GRUB includes a utility to do just that, called grub-mkrescue. You don't need to invoke it directly. You can just run make iso. This should create an ISO CD-ROM image called p2kern.iso which we can use to boot:

[you@fusion] qemu-system-i386 -cdrom p2kern.iso

This will boot up a virtual machine, and you'll see a menu to boot your asm kernel or another kernel (which we'll build in the next part). Select the first, and if everything went well, you should see "OK" printed to the screen. Note that if you're running QEMU with the -nographic flag, you won't see this, so you'll want to ssh to fusion using X forwarding (with the -X flag) so you can see a QEMU window.

That's it for this part; congrats on your first kernel!

Goodbye Assembly

Since we're lazy and spoiled by high-level languages (think of the UNIX team writing the entire OS in assembly!), we want to get to the point where we can start writing our kernel in C code. To do that, we're going to have to get the environment set up for it. Namely, we're going to have to make use of that stack we setup in our linker script before. This time I'm not giving you the code, but I'll give you some hints:

• There are two files you need to fill in, boot.S and kernel.c
• boot.S is going to look a lot like lowkern.S, but it needs to jump to a C function at some point
• In your boot.S you're going to have to set up the stack putting a pointer to the stack we reserved in the stack pointer register (%esp)
• Your C kernel should be implemented in kernel.c and should do the same thing as lowkern.S did (with the framebuffer and printing to the screen) but in C. It should then go into an infinite halt loop and never return.
• You'll need the call instruction to get into C code.
• Once you've finished writing the code, you'll want to use the make ckern.bin command and make iso again

To run this kernel, you should be able to run the same QEMU command as in the last part, only this time you'll select the second option in the GRUB menu.

If you got that working, congratulations! You're well on your way to implementing your own OS. There are plenty of resources out there that will guide you from this point, xv6 being a great example. You should be able to look at the xv6 build and boot process and have a much better idea of what is going on now!

Testing Your Code

Testing code at this low level is a challenge. Since we haven't fully booted the machine (and we don't have a working OS yet), we don't have a debugger, or fancy memory leak detection tools like Valgrind. We hardly even have a screen we can print to! Really your only options are to try to debug in the dark (painful, but really stretches your mind) or to do register-level debugging with QEMU. You can single step QEMU and dump out machine registers by using its "monitor." To get QEMU to put its montior on stdio, you can provide the -monitor stdio flag to your QEMU invocation. This will drop you into a gdb-like debugging environment where you can see the register values on the machine, e.g. by running info registers.

Acknowledgements

This project was inspired by Johan Montelius's excellent set of OS experiments.

Other Resources

• Nice blog post on how computers boot up
• The Linux Boot Protocol