Booting into C

This assignment will teach you to build a minimal bootable code that boots on real hardware into C. Technically, you can do this assignment on any operating system that supports the Unix API and can run Qemu (Linux Openlab machines, your laptop that runs Linux or Linux VM, and even MacOS, etc.). You don't need to set up xv6 for this assignment, but if you're running on Openlab you'll have to install QEMU, see QEMU setup instructions.

For Mac / OSX users: the support of 32 bit applications is deprecated in the latest version of your system. So if you already updated your system to MacOS Catalina or have updated your XCode then we recommend you to do the homework at the Openlab machines.

This assignment explains how to create a minimal x86 operating system kernel using the Multiboot standard. In fact, it will just boot and print "Hello, world!" on the screen, and then print "Hello from C!" on the serial line from the C main() function.

Most of this assignment is based on intermezzOS project.

When you turn on a computer, it loads the BIOS from some special flash memory. The BIOS runs self test and initialization routines of the hardware, then it looks for bootable devices. If it finds one, the control is transferred to its bootloader, which is a small portion of executable code stored at the device's beginning. The bootloader has to determine the location of the kernel image on the device and load it into memory. It also needs to switch the CPU to the so-called protected mode because x86 CPUs start in the very limited real mode by default (to be compatible to programs from 1978).

We won't write a bootloader because that would be a complex project on its own (we partially covered this in class since xv6 implements a simple boot loader with two files: bootasm.S and bootmain.c). Instead we will use one of the many well-tested bootloaders out there to boot our kernel from a CD-ROM or USB drive

Let's get going! The very first thing we're going to do is create a 'multiboot header'. What's that, you ask? Well, to explain it, let's take a small step back and talk about how a computer boots up.

One of the amazing and terrible things about the x86 architecture is that it's maintained backwards compatibility throughout the years. This has been a competitive advantage, but it's also meant that the boot process is largely a pile of hacks. Each time a new iteration comes out, a new step gets added to the process. That's right, when your fancy new computer starts up, it thinks it's an 8086 from 1976. And then, through a succession of steps, we transition through more and more modern architectures until we end at the latest and greatest.

The first mode is called 'real mode'. This is a 16 bit mode that the original x86 chips used. The second is 'protected mode'. This 32 bit mode adds new things on top of real mode. It's called 'protected' because real mode sort of let you do whatever you wanted, even if it was a bad idea. Protected mode was the first time that the hardware enabled certain kinds of protections that allow us to exercise more control around such things as RAM. We'll talk more about those details later.

The final mode is called 'long mode', and it's 64 bits. Since our OS will only enter 32bit mode we'll not touch 64bit 'long mode'.

So that's the task ahead of us: make the jump up the ladder and get to 32bit mode. We can do it! Let's talk more details.

So let's begin by turning the power to our computer on. When we press the power button, a bunch of low-level initialization protocols are executed: Management Engine, BIOS, etc.

With the BIOS we're already in the land of software, but unlike software that you may be used to writing, the BIOS comes bundled with its computer and is located in Read-Only Memory (ROM).

One of the first things the BIOS does is run a 'POST' or Power-On Self-Test which checks for the availability and integrity of all the pieces of hardware that the computer needs including the BIOS itself, CPU registers, RAM, etc. If you've ever heard a computer beeping at you as it boots up, that's the POST reporting its findings.

Assuming no problems are found, the BIOS starts the real booting process.

The BIOS automatically finds a 'bootable drive' by looking in certain pre-determined places like the computer's hard drive and CD-DVD drives, and USB sticks. A drive is 'bootable' if it contains software that can finish the booting process. In the BIOS menu you can usually change in what order the BIOS looks for bootable drives or tell it to boot from a specific drive.

The BIOS knows it's found a bootable drive by looking at the first few kilobytes of the drive and looking for some magical numbers set in that drive's memory. This won't be the last time some magical numbers or hacky sounding things are used on our way to building an OS. Such is life at such a low level...

When the BIOS has found its bootable drive, it loads part of the drive into memory and transfers execution to it. With this process, we move away from what comes dictated by the computer manufacturer and move ever closer to getting our OS running.

The part of our bootable drive that gets executed is called a bootloader, since it loads things at boot time. The bootloader's job is to take our kernel, put it into memory, and then transition control to it.

Some people start their operating systems journey by writing a bootloader. For example, in class we started by looking at the xv6 bootloader that is loaded by the BIOS at the 0x7c00 address. In this assignment we will not be doing that.

In the interest of actually getting around to implementing a kernel, instead, we'll use an existing bootloader: GRUB.

GRUB and Multiboot

GRUB stands for 'GRand Unified Bootloader', and it's a common one for GNU/Linux systems. GRUB implements a specification called Multiboot, which is a set of conventions for how a kernel should get loaded into memory. By following the Multiboot specification, we can let GRUB load our kernel.

The way that we do this is through a 'header'. We'll put some information in a format that multiboot specifies right at the start of our kernel. GRUB will read this information, and follow it to do the right thing.

One other advantage of using GRUB: it will handle the transition from real mode to protected mode for us, skipping the first step. We don't even need to know anything about all of that old stuff. If you're curious about the kinds of things you would have needed to know, put "A20 line" into your favorite search engine, and get ready to cry yourself to sleep.

Writing our own Multiboot header

I said we were gonna get to the code, and then I went on about more history. Sorry about that! It's code time for real! You can download a zipped folder that contains skeletons for the homework files boot-into-c-src.zip.

Inside your homework folder there is a file called multiboot_header.asm. Open it in your favorite editor. I use vim, but you should feel free to use any great editor like eamcs.

This is a .asm file, which is short for 'assembly'. That's right, we're going to write some assembly code here. Don't worry! It's not super hard.

The Magic Number

Our first assembly file will be almost entirely data, not code. Here's the first line:

Ugh! Gibberish! Let's start with the semicolon (;). It's a comment, that lasts until the end of the line. This particular comment says 'magic number'. As we said, you'll be seeing a lot of magic numbers in your operating system work. The idea of a magic number is that it's completely and utterly arbitrary. It doesn't mean anything. It's just magic. The very first thing that the multiboot specification requires is that we have the magic number 0xe85250d6 right at the start.

What's the value in having an arbitrary number there? Well, it's a kind of safeguard against bad things happening. This is one of the ways in which we can check that we actually have a real multiboot header. If it doesn't have the magic number, something has gone wrong, and we can throw an error.

I have no idea why it's 0xe85250d6, and I don't need to care. It just is.

Finally, the dd. It's short for 'define double word'. It declares that we're going to stick some 32-bit data at this location. Remember, when x86 first started, it was a 16-bit architecture set. That meant that the amount of data that could be held in a CPU register (or one 'word' as it's commonly known) was 16 bits. To transition to a 32-bit architecture without losing backwards compatibility, x86 got the concept of a 'double word' or double 16 bits.

The mode code

Okay, time to add a second line:

This is another form of magic number. We want to boot into protected mode, and so we put a zero here, using dd again. If we wanted GRUB to do something else, we could look up another code, but this is the one that we want.

Header length

The next thing that's required is a header length. We could use dd and count out exactly how many bytes that our header is, but there's two reasons why we're not doing that:

1. Computers should do math, not people.
2. We're going to add more stuff, and we'd have to recalculate this number each time. Or wait until the end and come back. See #1.

Here's what this looks like:

You don't have to align the comments if you don't want to. I usually don't, but it looks nice and after we're done with this file, we're not going to mess with it again, so we won't be constantly re-aligning them in the future.

The header_start: and header_end: things are called labels. Labels let us use a name to refer to a particular part of our code. Labels also refer to the memory occupied by the data and code which directly follows it. So in our code above the label header_start points directly to the memory at the very beginning of our magic number and thus to the very beginning of our header.

Our third dd line uses those two labels to do some math: the header length is the value of header_end minus the value of header_start. Because header_start and header_end are just the addresses of places in memory, we can simply subtract to get the distance between those two addresses. When we compile this assembly code, the assembler will do this calculation for us (so at runtime there is only a number in there). No need to figure out how many bytes there are by hand. Awesome.

You'll also notice that I indented the dd statements. Usually, labels go in the first column, and you indent actual instructions. How much you indent is up to you; it's a pretty flexible format.

The Checksum

The fourth field multiboot requires is a 'checksum'. The idea is that we sum up some numbers, and then use that number to check that they're all what we expected things to be. It's similar to a (very simple) hash, in this sense: it lets GRUB double-check that everything is accurate. Here's the checksum:

Again, we'll use math to let the computer calculate the sum for us at compile time. We add up the magic number, the mode code, and the header length, and then subtract it from a big number. dd then puts that value into this spot in our file.

Ending tag

After the checksum you can list a series of "tags", which is a way for the OS to tell the bootloader to do some extra things before handing control over to the OS, or to give the OS some extra information once started. We don't need any of that yet, though, so we just need to include the required "end tag", which looks like this:

Here we use dw to define a 'word' instead of just data. Remember a 'word' is 16 bits or 2 bytes on the x86_64 architecture. The multiboot specification demands that this be exactly a word. You'll find that this is super common in operating systems: the exact size and amount of everything matters. It's just a side-effect of working at a low level.

The Section

We have one last thing to do: add a 'section' annotation. We'll talk more about sections later, so for now, just put what I tell you at the top of the file. Here's the final file:

We have just written a multiboot compliant header. It's a lot of esoterica, but it's pretty straightforward once you've seen it a few times.

Assembling with nasm

We can't use this file directly, we need to turn it into binary. We can use a program called an 'assembler' to 'assemble' our assembly code into binary code. It's very similar to using a 'compiler' to 'compile' our source code into binary. But when it's assembly, people often use the more specific name.

We will be using an assembler called nasm to do this. You should invoke nasm like this:

The -f elf32 says that we want to output a file as 32bit ELF. The -g -F dwarf flag says that we want to include debugging information in dwarf format. After you run this command, you should see a multiboot_header.o file in the same directory. This is our 'object file', hence the .o. Don't let the word 'object' confuse you. It has nothing to do with anything object oriented. 'Object files' are just binary code with some metadata in a particular format, in our case ELF. Later, we'll take this file and use it to build our OS.

You can inspect the bytes of the header with hexdump:

Summary

Congratulations! This is the first step towards building an operating system. We learned about the boot process, the GRUB bootloader, and the Multiboot specification. We wrote a Multiboot-compliant header file in assembly code, and used nasm to create an object file from it.

Next, we'll write the actual code that prints "Hello world" to the screen. Let's go!

Now that we've got the headers out of the way, let's do the traditional first program: Hello, world!

The smallest kernel

Our hello world will be just 20 lines of assembly code. But let's begin with something even shorter. Open a file called boot.asm and put this in it:

As you know already, start: is a label. GRUB uses this conventional label to know where to begin.

The hlt statement is our first bit of 'real' assembly. So far, we had just been declaring data. This is actual, executable code. It's short for 'halt'. In other words, it ends the program.

By giving this line a label, we can call it, sort of like a function. That's what GRUB does: "Call the function named start." This function has just one line: stop.

Unlike many other languages, you'll notice that there's no way to say if this 'function' takes any arguments or not. We'll talk more about that later.

This code won't quite work on its own though. We need to do a little bit more bookkeeping first. Here's the next few lines:

Three new bits of information. The first, global start, says "I'm going to define a label start, and I want it to be available outside of this file." If we don't say this, GRUB won't know where to find its definition. You can kind of think of it like a 'public' annotation in other languages.

Then we have section .text. We saw section briefly, but I told you we'd get to it later. The place where we get to it is at the end of this chapter. For the moment, all you need to know is this: code goes into a section named .text. Everything that comes after the section line is "inside that section", until another section line appears.

Following, we have bits 32. GRUB will boot us into protected mode, aka 32-bit mode (similar to how xv6 bootloader starts in 16-bit real mode GRUB will be loaded by the BIOS and will switch into protected 32-bit mode for us). But we have to specify directly that assembler has to generate 32bit code. Our Hello World will only be in 32 bits.

Finally Printing

We could theoretically stop here, but instead, let's actually print the "Hello world" text to the screen. We'll start off with an 'H':

This new line is the most complicated bit of assembly we've seen yet. There's a lot packed into this little line.

The first important bit is mov. This is short for move, and it sorta looks like this:

Oh, and ; starts a comment, remember? So the ; H is just for us. I put this comment here because this line prints an H to the screen!

Yup, it does. Okay, so here's why: mov copies thing into place. The amount of stuff it copies is determined by size.

Then, the previous instruction is saying: "Copy one word: the number 0x0248 to some place".

The place looks like a number just like 0x0248, but it has square brackets [] around it. Those brackets are special. They mean "the address in memory located by this number." In other words, we're copying the number 0x0248 into the specific memory location 0xb8000. That's what this line does.

Why? Well, we're using the screen as a "memory mapped" device. Specific positions in memory correspond to certain positions on the screen. And the position 0xb8000 is one of those positions: the upper-left corner of the screen.

Now, we are copying 0x0248. Why this number? Well, it's in three parts:

Let's start at the right. The last, two numbers are the letter, in ASCII. H is 72 in ASCII, and 48 is 72 in hexadecimal: (4 * 16) + 8 = 72. So this will write H.

The other two numbers are colors. There are 16 colors available, each with a number. Here's the table:

So, 02 is a black background with a green foreground. Classic. Feel free to change this up, use whatever combination of colors you want!

So this gives us a H in green, over black. Next letter: e.

Lower case e is 65 in ASCII, at least, in hexadecimal. And 02 is our same color code. But you'll notice that the memory location is different.

Okay, so we copied four hexadecimal digits into memory, right? For our H. 0248. A hexadecimal digit has sixteen values, which is 4 bits (for example, 0xf would be represented in bits as 1111). Two of them make 8 bits, i.e. one byte. Since we need half a word for the colors (02), and half a word for the H (48), that's one word in total (or two bytes). Each place that the memory address points to can hold one byte (a.k.a. 8 bits or half a word). Hence, if our first memory position is at 0, the second letter will start at 2.

This math gets easier the more often you do it. And we won't be doing that much more of it. There is a lot of working with hex numbers in operating systems work, so you'll get better as we practice.

With this, you should be able to get the rest of Hello, World. Go ahead and try if you want: each letter needs to bump the location twice, and you need to look up the letter's number in hex.

If you don't want to bother with all that, here's the final code:

Finally, now that we've got all of the code working, we can assemble our boot.asm file with nasm, just like we did with the multiboot_header.asm file:

This will produce a boot.o file. We're almost ready to go!

Okay! So we have two different .o files: multiboot_header.o and boot.o. But what we need is one file with both of them. Our OS doesn't have the ability to do anything yet, let alone load itself in two parts somehow. We just want one big binary file. Linking is how we'll turn these two files into a single output: by linking them together.

Open up a file called linker.ldand put this in it:

This is a 'linker script'. It controls how our linker will combine these files into the final output. Let's take it bit-by-bit:

This line sets the 'entry point' for this executable. In our case, we called our entry point by the name people use: start. Remember? In boot.asm? Same name here.

Okay! I've been promising you that we'd talk about sections. Everything inside of these curly braces is a section. We annotated parts of our code with sections earlier, and here, in this part of the linker script, we will describe each section by name and where it goes in the resulting output.

This line means that we will start putting sections at the one megabyte mark. This is the conventional place to put a kernel, at least to start. Below one megabyte is all kinds of memory-mapped stuff. Remember the VGA stuff? It wouldn't work if we mapped our kernel's code to that part of memory... garbage on the screen!

This will create a "read only" section named rodata. And inside of it...

... goes every section named multiboot_header. Remember how we defined that section in multiboot_header.asm? It'll be here, at the start of the rodata section. That's what we need for GRUB to see it.

Next, we define a text section. The text section is where you put code. And inside of it...

... goes every section named text. See how this is working? The syntax is a bit weird, but it's not too bad. We do the same for the code and bss section. That's it for our script! We can then use the tool ld to link all of this stuff together:

By running this command, we do a few things: -m elf_i386 ask the linker to generate the 32bit. -T linker.ld tells the linker to use the script we just made. -o kernel.bin sets the name of our output file. In our case, that's kernel.bin. We'll be using this file in the next step. It's our whole kernel!. Finally, multiboot_header.o boot.o are the object files that we want to link together.

That's it! We've now got our kernel in the kernel.bin file. Next, we're going to make an ISO out of it, so that we can load it up in QEMU.

Now that we have our kernel.bin, the next step is to make an ISO. Remember compact discs? Well, by making an ISO file, we can both test our Hello World kernel in QEMU, as well as running it on actual hardware!

To do this, we're going to use a GRUB tool called grub2-mkrescue. We have to create a certain structure of files on disk, run the tool, and we'll get an hello.iso file at the end.

Doing so is not very much work, but we need to put the files in the right places. First, we need to make several directories and copy the provided grub.cfg file:

The -p flag to mkdir will make the directory we specify, as well as any 'parent' directories, hence the p. In other words, this will make an build directory with a isofiles directory inside that has boot inside, and finally the grub directory inside of that. Then we copy the grub.cfg file. It should look like this:

This file configures GRUB. Let's talk about the menuentry block first. GRUB lets us load up multiple different operating systems, and it usually does this by displaying a menu of OS choices to the user when the machine boots. Each menuentry section corresponds to one of these. We give it a name, in this case, cs238pOS, and then a little script to tell it what to do. First, we use the multiboot2 command to point at our kernel file. In this case, that location is /boot/kernel.bin. Remember how we made a boot directory inside of isofiles? Since we're making the ISO out of the isofiles directory, everything inside of it is at the root of our ISO. Hence /boot.

Let's copy our kernel.bin file there now:

Finally, the boot command says "that's all the configuration we need to do, boot it up."

But what about those timeout and default settings? Well, the default setting controls which menuentry we want to be the default. The numbers start at zero, and since we only have that one, we set it as the default. When GRUB starts, it will wait for timeout seconds, and then choose the default option if the user didn't pick a different one. Since we only have one option here, we just set it to zero, so it will start up right away.

The final layout should look like this:

Using grub2-mkrescue is easy. We run this command:

The -o flag controls the output filename, which we choose to be hello.iso. And then we pass it the directory to make the ISO out of, which is the build/isofiles directory we just set up. If you get an error like grub2-mkrescue: error: xorriso not found., that means your system does not have the package xorriso installed.

After this, if everything went well, we will have a hello.iso file with our teeny kernel on it. You could put this on a USB stick, or burn it on a CD and run it on an actual computer if you wanted to! But doing so would be really annoying during development. So in the next section, we'll use an emulator, QEMU, to run the ISO file on our development machine.

Let's actually run our kernel! To do this, we'll use QEMU, a full-system emulator. Using QEMU is fairly straightfoward. If you're running on openlab you can't really connect to the GUI application, so we'll use -curses:

To exit, type Alt + 2 (or Esc + 2), type q (or quit) in the console; and then Enter

If you're running on your own machine you can simply run:

To exit in Linux (maybe Windows too); type Ctrl + Alt + q in the window that popped out.

If everything went well, congrats! you should see Hello, world!. If not, something may have gone wrong. Double check that you followed the examples exactly. Maybe you missed something, or made a mistake while copying things down.

Note that you may see other stuff behind the Hello World message, this part may vary based on your version of GRUB, and also since we didn't clear the screen, everything from GRUB just stays as it is. We'll write a function to do that eventually...

Let's talk about the command qemu-system-x86_64 before we move on. We're running the x86_64 variant of QEMU. While we have a 32-bit kernel the QEMU emulates x86 64bit architecture. And since 32bit code is part of it everything works. We're going to start QEMU with a CD-ROM drive, -cdrom, and its contents are the hello.iso file we made.

That's it! Here's the thing, though: while that wasn't too complicated, it was a lot of steps. Each time we make a change, we have to go through all these steps over again. In the next section, we'll use Make to do all these steps for us.

Typing all of these commands out every time we want to build the project is tiring and error-prone. It's nice to be able to have a single command that builds our entire project. To do this, we'll use the tool make and our downloaded Makefile.

To make this Makefile working move create boot folder in the same directory as Makefile and put previously created grub.cfg into boot folder.

The makefile starts by defining several variables kernel, iso, linker_script, and grub_cfg that define names of the output files we want to make. CFLAGS is a variable that defines all flags to the GCC compiler. QEMU_... are variables that define different flags passed to calls to qemu.

We then create two lists: a list of assembly files in the variable assembly_source_files and a list of C source files, c_source_files. We then use the patsubst command to generate another two lists that are the same file names but in the folder build, and with .o as extension:

Then whe add all the targets:

First, the notation $(var) expands to the content of the variable var. For example, in our Makefile, $(iso) expands to build/hello.iso.

Makefiles are mainly a collection of rules to "make a target" or to "do an action". When we call make we either specify a target, an action, or just take the default one (which is the first defined in the file).

Targets are files that we want to create, the name of the target is the actual name of the file. Actions are things that we want to do that doesn't necesarely produce a file. The "rules" I just mentioned have the following shape (note that before each command there must be a tab \t character):

At the right side of the : symbol, we have the dependencies of this target, they are "what has to be present and updated" before running the commands associated with the rule. If a dependency is not updated, then make searches for some other rule in the Makefile that could create/update the outdated dependency. Only when all dependencies are updated, make runs the commands associated with the rule. For example, in our Makefile, the action iso requires the file build/hello.iso to be presest and updated.

This "search and update the dependency" behavior is recursive, so if a dependency has a rule with an outdated dependency, make will go deeper and deeper until it gets to the source files that you are editing. Therefore, if you make a change in a source file, make detects it, and when called, it will update all the dependencies that were affected by your editions. Neat!

On the other hand, if nothing has changed in the dependencies since the last time make ran, make knows that there is nothing new to do and does not run the commands because everythitg is up to date. That is great, because we will not recompile code that did not change. On big projects that can save many hours!.

It's convenient to define actions to automatize some tasks: to run our kernel in qemu, we added the rules qemu and qemu-gdb. To clean all the "compile-time-generated" files, we added the rule clean. This is useful when you want to prepare to make a full re-build from scratch, what we will do when grading your work.

One last thing, given the smart "run-the-rule-only-when-needed" behavior of make, there is one little problem: there are some actions that we want to perform every time we request it to make, no matter if files have changed or not. You can list those "always-run" targets/actions on the special target .PHONY.

Up until now we did a lot of work that wasn't actually writing kernel code. So let's review what we're up to:

1. GRUB loaded our kernel, and started running it.
2. We're currently running in 'protected mode', a 32-bit environment.
3. We want to enable paging.
4. We want to create a stack and jump into main.

We're on step three. More specifically, here's what we have to do:

1. Set up something called 'paging'.
2. Set up something called a 'GDT'.
3. Call into main.

Paging is actually implemented by a part of the CPU called an 'MMU', for 'memory management unit'. The MMU will translate virtual addresses into their respective physical addresses automatically; we can write all of our software with virtual addresses only. The MMU does this with a data structure called a 'page table'. As an operating system, we load up the page table with a certain data structure, and then tell the CPU to enable paging. This is the task ahead of us; it's required to set up paging before we transition to long mode.

How should we do our mapping of physical to virtual addresses? You can make this easy, or complex, and it depends on exactly what you want your OS to be good at. Some strategies are better than others, depending on the kinds of programs you expect to be running. We're going to keep it simple, and use a strategy called 'identity mapping'. This means that every virtual address will map to a physical address of the same number. Nothing fancy.

Let's talk more about the page table. In 32bit mode, the page table is two levels deep, and each page is 4096 bytes in size. What do I mean by levels? Here are the official names:

• Page-Directory Table (PD)
• Page Table (PT)

So here's the strategy to accomplish that: create a single entry of each of these tables, then point them at each other in the correct way, then tell the CPU that paging should be enabled.

Creating the page table entries

To create space for these page table entries, open up boot.asm and add these lines at the bottom:

We introduce a new section, 'bss'. It stands for 'block started by symbol', and was introduced in the 1950s. The name doesn't make much sense anymore, but the reason we use it is because of its behavior: entries in the bss section are automatically set to zero by the linker. This is useful, as we only want certain bits set to 1, and most of them set to zero.

The resb directive reserves bytes; we want to reserve space for each entry.

The align directive makes sure that we've aligned our tables properly. We haven't talked much about alignment yet: the idea is that the addresses here will be set to a multiple of 4096, hence 'aligned' to 4096 byte chunks. We'll eventually talk more about alignment and why it's important, but it doesn't matter a ton right now.

After this has been added, we have a single valid entry for each level. However, because they are all zeroes, we have no valid pages. That's not super useful. Let's set things up properly.

Pointing the entries at each other

In order to do this setup, we need to write some more assembly code! Open up boot.asm. You can either leave in printing code, or remove it. If you do leave it in, add this code before it: that way, if you see your message print out, you know it ran successfully.

If you recall, ; are comments. Leaving yourself excessive comments in assembly files is a good idea. Let's go over each of these lines:

This copies the contents of the first page table entry into the eax register. We need to do this because of the next line:

We take the contents of eax and or it with the number 0b11, the result is written in eax. Each entry in a page table contains an address, but it also contains metadata about that page. The first two bits are the 'present bit' and the 'writable bit'. By setting the first bit, we say "this page is currently in memory," and by setting the second, we say "this page is allowed to be written to." There are a number of other settings we can change this way, but they're not important for now.

Now that we have an entry set up properly, the next line is of interest:

Another mov instruction, but this time, copying eax, where we've been setting things up, into... something in brackets. [] means, "I will be giving you an address between the brackets. Please do something at the place this address points." In other words, [] is like a dereference operator.

Now, the address we've put is kind of funny looking: ptd_table + 0. What's up with that + 0? It's not strictly needed: adding zero to something keeps it the same. However, it's intended to convey to the reader that we're accessing the zeroth entry in the page table. We're about to see some more code later where we will do something other than add zero, and so putting it here makes our code look more symmetric overall. If you don't like this style, you don't have to put the zero.

These few lines form the core of how we're setting up these page tables. We're going to do the same thing over again, with slight variations.

Here's the full thing again:

We have one last thing to do: set up the level two page table to have valid references to pages. We're going to do something we haven't done yet in assembly: write a loop!

Here's the basic outline of loop in assembly:

• Create a counter variable to track how many times we've looped
• make a label to define where the loop starts
• do the body of the loop
• add one to our counter
• check to see if our counter is equal to the number of times we want to loop
• if it's not, jump back to the top of the loop
• if it is, we're done

It's a little more detail-oriented than loops in other languages. Usually, you have curly braces or indentation to indicate that the body of the loop is separate, but we don't have any of those things here. We also have to write the code to increment the counter, and check if we're done. Lots of little fiddly bits. But that's the nature of what we're doing! Let's get to it!

In order to write a loop, we need a counter. ecx is the usual loop counter register, that's what the c stands for: counter. We also have a comment indicating what we're doing in this part of the code.

Next, we need to make a new label:

As we mentioned above, this is where we will loop back to when the loop continues.

We're going to store 0x1000 in eax, or 4096 which is 4KB. Here's the reason: each page is 4KB in size. So in order to get the right memory location, we will multiply the number of the loop counter by 0x1000

Here's that multiplication! mul takes just one argument, which in this case is our ecx counter, and multiplies that by eax, storing the result in eax. This will be the location of the next page.

Next up, our friend or. Here, we again set present and writable bits 0b11.

Just like before, we are now writing the value in eax to a location. But instead of it being just pt_table + 0, we're adding ecx * 4. Remember, ecx is our loop counter. Each entry is four bytes in size, so we need to multiply the counter by four, and then add it to pt_table.

That's the body of the loop! Now we need to see if we need to keep looping or not:

The inc instruction increments the register it's given by one. ecx is our loop counter, so we're adding to it. Then, we 'compare' with cmp. We're comparing ecx with 1024: we want to map 1024 page entries overall. The page table is 4096 bytes, each entry is 4 bytes, so that means there are 1024 entries. This will give us 1024 * 4KB: four megabytes of memory. It's also why we wrote the loop: writing out 1024 entries by hand is possible, theoretically, but is not fun. Let's make the computer do the math for us.

The jne instruction is short for 'jump if not equal'. It checks the result of the cmp, and if the comparison says 'not equal', it will jump to the label we've defined. map_pt_table points to the top of the loop.

That's it! We've written our loop and mapped our second-level page table. Here's the full code, all in one place:

Now that we've done this, we have a valid initial page table. Time to enable paging!

Enable paging

Now that we have a valid page table, we need to inform the hardware about it. Here's the steps we need to take:

• We have to put the address of the page table directory in a special register
• enable paging

These steps are not particularly interesting, but we have to do them. First, let's do the first step:

So, this might seem a bit redundant: if we put ptd_table into eax, and then put eax into cr3, why not just put ptd_table into cr3? As it turns out, cr3 is a special register, called a 'control register', hence the cr. The cr registers are special: they control how the CPU actually works. In our case, the cr3 register needs to hold the location of the page table.

Because it's a special register, it has some restrictions, and one of those is that when you mov to cr3, it has to be from another register. So we need the first mov to set p4_table in a register before we can set cr3.

Step one: done!

Finally we are all ready to enable paging!

cr0 is the register we need to modify. We do the usual "move to eax, set some bits, move back to the register" pattern. In this case, we set bit 31.

Once we've set these bits, we're done! Here's the full code listing:

The GDT is used for a style of memory handling called 'segmentation', which is in contrast to the paging model that we just set up. Even though we're not using segmentation, however, we're still required to have a valid GDT. Such is life.

So let's set up a minimal GDT. Our GDT will have three entries:

• a 'zero entry'
• a 'code segment'
• a 'data segment'

If we were going to be using the GDT for real stuff, it could have a number of code and data segment entries. But we need at least one of each to have a minimum viable table, so let's get to it!

The Zero entry

The first entry in the GDT is special: it needs to be a zero value. Add this to the bottom of boot.asm:

We have a new section: rodata. This stands for 'read only data', and since we're not going to modify our GDT, having it be read-only is a good idea.

Next, we have a label: gdt_start. We'll use this label later, to tell the hardware where our GDT is located.

Finally, dd 0. This defines a 'doubleword' value, in other words, a 32-bit value. Given that it's a zero entry, it shouldn't be too surprising that the value of this entry is zero!

That's all there is to it.

Setting up code and data segments

Next, we need a code segment. Add this below the zero entry that you created above.

Here we carefully follow the layout of the segment descriptor to make sure that all flags are set correctly (the exact layout can be found in the Intel Developer's Manual, 3.4.5). It would be nice to use a human-friendly macro like xv6 does, but I'm not good with macros in NASM.

Similar, we define the data segment.

Finally, we have to define the GDT descriptor, the special data structure that defines the size of the GDT and has a pointer to it in memory. We compute the size as the difference between two labels: gdt_end and gdt_start. The pointer itself is the value of the label where GDT starts, i.e., gdt_start.

Finally, lets define two constants for the code and data segments that we can load in registers

Note that here since each descriptor was 8 bytes long the code segment is defined as 0x8 and the data segment is 0x16. This is exactly what we want since the first 3 bits of the segment selector (3.4.2 in the Intel SDM) are used for flags.

Now we can add this code somewhere at the top to make sure that all segment registers are initialized correctly.

Load the GDT

So! We're finally ready to tell the hardware about our GDT. Add this line right above the code that initializes the data segment registers:

We pass lgdt the value of our gdt_descriptor label. lgdt stands for 'load global descriptor table'. That's it!

We have all of the prerequisites done! In the next section, we will complete our boot sequence by entering main().

Now we're one step away from calling the main function. We need to set up the stack. First, lets reserve 4096 bytes (one page) for the stack in the BSS section of the boot.asm file:

Now we can load the address of the stack into the esp register and call the main function:

We need to let the assembler know that main will be defined in a different object file (we'll compile it from main.c). For that we need to add this line right at the top of boot.asm

Compiling main()

Use the skeletons that you already downloaded: main.c, console.c, and console.h. A minimal main() function can look something like this:

It calls the uartinit() function to initialize the serial line and then prints "Hello from C" on the serial line. Serial ports are a legacy communications port common on IBM-PC compatible computers. Use of serial ports for connecting peripherals has largely been deprecated in favor of USB and other modern peripheral interfaces, however it is still commonly used in certain industries for interfacing with industrial hardware such as CNC machines or commercial devices such as POS terminals. Historically it was common for many dial-up modems to be connected via a computer's serial port, and the design of the underlying UART hardware itself reflects this.

Serial ports are typically controlled by UART hardware. This is the hardware chip responsible for encoding and decoding the data sent over the serial interface. Modern serial ports typically implement the RS-232 standard, and can use a variety of different connector interfaces. The DE-9 interface is the one most commonly used connector for serial ports in modern systems.

Serial ports are of particular interest to operating-system developers since they are much easier to implement drivers for than USB, and are still commonly found in many x86 systems. It is common for operating-system developers to use a system's serial ports for debugging purposes, since they do not require sophisticated hardware setups and are useful for transmitting information in the early stages of an operating-system's initialization. Many emulators such as QEMU and Bochs allow the redirection of serial output to either stdio or a file on the host computer.

To print something on the serial line we need to implement a minimal serial line driver. In this homework assignment we provide you a simple serial driver in console.c. It still makes sense for you to look over the page that describes the details of the serial line protocol in osdev.org.

At a high level we define which I/O port serial line is connected to:

We then use a couple of helper functions that provide the interface to assembly in and out instructions.

We then use the uartinit() function to initialize the serial line interface

The uartputc() displays an individual character on the screen

And finally the printk() function prints a string on the screen

Now we're finally ready to boot into C. There are three outputs produced by qemu that we care about:

1. The serial line output
2. The VGA output
3. The qemu debugging console (do not confuse with the gdb console)

The first one is already setup in the makefile to be written in the serial.log file. The second one is a bit more complex, you see, this is a graphical output; there is a couple of alternatives that we can control with the qemu flags -curses and -nographic. Let's review these two lines of our Makefile:

By un-commenting these variables, you will be activating that flag for qemu (check the rules that use these variables). So, activating:

1. none In your machine, it will pop out a window with the VGA output. In an environment without GUI (such as openlab) you will get an error.
2. only curses The default config in the Makefile. The VGA output is simulated using the curses interface, and printed in the screen.
3. curses and nox The screen will only show the qemu debugging console. The curses-simulated output will be written in the serial.log file, along with the serial line output.
4. only nox Exactly the same as curses and nox.

So, comment/uncomment these variables to your preferences, and if you put all the files in the correct places, you can run make qemu and get "Hello from C" in the serial.log file.

Another intersting skill to learn while working on this homework is debugging kernels with GDB. To do this we will be using GDB's remote debugging feature and QEMU's remote GDB debugging stub. Remote debugging is a very important technique for kernel development in general: the basic idea is that the main debugger (GDB in this case) runs separately from the program being debugged (the xv6 kernel atop QEMU) - they could be on completely separate machines, in fact.

Finding and breaking at an address

In this case, the entry point is 0x1010f0. Now we can start QEMU with GDB and break at this address. Open two terminals, either using a terminal multiplexer like tmux or logging in to openlab in another teminal. Run make qemu-gdb in the first terminal. This will run the qemu-gdb target in the Makefile:

In the other terminal, change directory, and start gdb.

What you see on the screen is the assembly code of the BIOS that QEMU executes as part of the platform initialization. The BIOS starts at address 0xfff0 (you can read more about it in the How Does an Intel Processor Boot? blog post. You can single step through the BIOS machine code with the si (single instruction) GDB command if you like, but it's hard to make sense of what is going on so lets skip it for now and get to the point when QEMU starts executing our kernel.

Set a breakpoint at the address of the entry point, e.g.

The details of what you see may differ slightly from the above output.

Troubleshooting GDB issues

It might be possible that you get the following error on gdb.

GDB uses a file called .gdbinit to initialize things. We provide you with a .gdbinit file with the required setup. However, to allow this local .gdbinit file to be used, we have to add the a line to the global .gdbinit file. Add this line to /home/<username>/.gdbinit.

Try to examine the .gdbinit file that we provide you (in unix systems files starting with . are hidden, you can list them with ls -a).

It tells gdb that the file to read symbols from while debugging is in build/kernel.bin. Since we are using remote-debugging, gdb and the target environment communicate through a network socket (this matches with what is setup in the QEMU_GDB variable in the Makefile). The other lines in the .gdbinit file setup the communication.

Making yourself familiar with GDB

This part of the homework teaches you how to use GDB. If your OS and GDB are still running exit them.

To exit gdb, just type Ctrl + C, and type quit. Depending on how you started qemu, you can exit with different commands:

• If using -curses, type Alt + 2 (or Esc + 2), type q (or quit) in the console; and then Enter
• If using -nographic, and see something like this in the first terminal:
  ... XMM02=00000000000000000000000000000000 XMM03=00000000000000000000000000000000 XMM04=00000000000000000000000000000000 XMM05=00000000000000000000000000000000 XMM06=00000000000000000000000000000000 XMM07=00000000000000000000000000000000 _
  Then just press Enter to reveal the qemu console, type quit, and Enter again.
• You can also exit QEMU by it with Ctrl + A, X.

Start your OS and gdb again as you did before. Use two terminals: one to start the OS in QEMU (make qemu-gdb) and one to start GDB (gdb)

Now we explore the other ways of setting breakpoints. Instead of br *0x001010f0 , you can use the name of the function or an assembly label, e.g., to set the breakpoint at the beginning of the start label you can use:

BTW, autocomplete works inside GDB, so you can just type "s" and hit Tab. Similarly, you can set the breakpoint on the main() function.

If you need help with GDB commands, GDB can show you a list of all commands with:

Now since you set two breakpoints you can continue execution of the system until one of them gets hit. In gdb enter the "c" (continue) command to run xv6 until it hits the first breakpoint (_start).

Just in case it is disabled, you can instruct gdb to, after advancing a single machine instruction, print the next one. You can also switch between ATT and Intel disassembly syntax. Now use the si (step instruction) command to single step your execution (execute one machine instruction at a time). Remember that the _start label is defined in the assembly file, entry.S to be the entry point for the kernel. Enter si a couple of times. Note, you don't have to enter si every time, if you just press "enter" the GDB will execute the last command.

You can either continue single stepping until you reach your code or the main() function, or you can enter "c" to continue execution until the next breakpoint.

The moment you reach the C code, you should be able to view the C source alongside using the l (list) command. Since we compiled the kernel with the "-g" flag that includes the symbol information into the ELF file we can see the C source code that we're executing.

Remember that when you hit the main breakpoint GDB showed you that you're at line 14 in the main.c file (main.c:14). You can either step into the functions with the s (step) command (note, in contrast to the si step instruction command, this one will execute one C line at a time), or step over the functions with the n (next) command which will not enter the function, but instead will execute it till completion.

Try stepping into one of the functions you built. Once gdb has stopped at the line where you invoke a function, type s for step.

The whole listing of the source code seems a bit inconvenient (entering l every time you want to see the source line is a bit annoying). GDB provides a more conventional way of following the program execution with the TUI mechanism. Enable it with the following GDB command

Now you see the source code window and the machine instructions at the bottom. You can use the same commands to walk through your program. You can scroll the source with arrow keys, PgUp, and PgDown.

TUI can show you the state of the registers and how they are changing as you execute your code

TUI is a very cute part of GDB and hence it makes sense to read more about its various capabilities: TUI Commands.

For example, you can specify the assembly layout to single step through machine instructions similar to source code:

Or you can use them both (try it)

Or you can look at the registers too:

Beej's Quick Guide to GDB is a wonderful introduction to GDB using TUI.

QEMU has a built-in monitor that can inspect and modify the machine state. To enter the monitor press Alt + 2 . Some of the following commands should be helpful in the monitor:

This displays mapped virtual memory and permissions. The above example tells us that 0x0000000000400000 bytes of memory from 0x0000000000000000 to 0x0000000000400000 are mapped read/write.

This displays a full dump of the machine's internal register state.

Finally, your assignment is to implement page table that maps the first 8MB of virtual addresses to the first 8MB of physical memory. At the moment we have a page table that maps first 4MB, you need to define and construct a new page table once you boot into main().

Once your page table is constructed use the provided lcr3() function to load it into the CR3 register. Note, you have to load the physical address of the page table.

Extra credit 1: (10% bonus)

Implement support for mapping 256MBs of physical memory with 4KB pages.

Extra credit 2: (10% bonus)

Implement a simple CGA driver, i.e., when you use the printk() it should print on both serial line like now and on the display.

Extra credit 3: (5% bonus)

Boot on real hardware. I.e., try booting your code on a real desktop or laptop by either burning a CD-ROM or a USB flash drive. Record a video of your code booting.

Extra credit 4: (5% bonus)

Change the descriptor privilege level in the GDT to 3. Analyse (understand and explain) what happens.

Submit your solution (the zip archive) through Gradescope in the assignment called HW4 - Booting into C. Please zip all of your files and submit them. If you have done extra credit then place all the required files in a new folder extra1, extra2, etc.

You can resubmit as many times as you wish. If you have any problems with the structure the autograder will tell you. The structure of the zip file should be the following:

The file video_link.txt will only contain one line, with a single link to the video:

1. You will first show a white sheet of paper with your name and UCI email address.
2. Then you will show the physical machine booting. Make sure that the paper and screen are readable.
3. The video cannot have cuts. It has to be taken in one single shot.