[ << ] [ >> ]           [Top] [Contents] [Index] [ ? ]

3. Project 2: PC Booter

In this assignment you will learn more about the IA32 bootstrap process, and a bit of what it's like to program on top of the "bare metal," as it's called. You will complete a basic framework to boot the computer directly into a C program - with no operating system at all. Using this framework, you will then create a simple game or interactive demo of your own devising, using a limited number of the computer's hardware capabilities.

This project will be completed in the src/booter directory. As with Project 1, you will not need to work in the Pintos codebase itself; it is another stand-alone assignment.

The specs directory contains a significant amount of documentation about various hardware components, as well as other specifications that you will find useful throughout the term. For this week, you should use the IA32 manuals in the specs/ia32 directory, as well as the ELF file documentation in the specs directory. Relevant sections are cited in the comments of the source files you will work in.

3.1 Background

During the 1980s, a surprisingly large number of games followed the approach of creating a special disk that would boot the computer directly into the game. When graphics and sound hardware were very limited, and the OS didn't provide any graphics or sound facilities, so-called "PC booters" were able to squeeze the most out of the limited hardware and offer reasonably compelling gaming experiences. (Now that graphics hardware is extremely advanced and widely varied, games depend heavily on the operating system to provide a unified software interface for interacting with the graphics hardware.)

The other major reason why game publishers took this approach was to provide some measure of copy protection. Disks frequently used nonstandard formats (e.g. putting an extra track on floppy disks that operating systems didn't know how to access, or fewer sectors per track than the typical format), so that operating systems would be unable to copy them. Of course, these measures were frequently straightforward to circumvent.

If you want to see a list of PC booter games, check out the list on Wikipedia.

3.1.1 Approach

If you are going to write a PC booter, you will need to write some assembly language. But, you don't want to write an entire game in IA32 assembly, so our goal will be to boot the computer such that it can call into a C program compiled by gcc. The IA32 machine code emitted by gcc is 32-bit code that expects to run against a linear 32-bit address space. However, the bootloader runs in 16-bit real mode. Thus, the bootloader must also transition from 16-bit real mode into 32-bit protected mode.

Fortunately, we can also take a few other shortcuts:

Recall that the bootloader will be loaded into memory by the BIOS, at address 0x0000:0x7C00. The bootloader's primary responsibility is to load the main program into memory, and then prepare the computer such that our program will run properly. The bootloader must be implemented entirely in IA32 assembly language; some of it will be 16-bit real-mode code, and some of it will be 32-bit protected-mode code. Within the 16-bit portion, we can take advantage of BIOS calls, but once we transition into protected mode, we won't be able to use the BIOS anymore. Thus, anything that needs to be done via the BIOS, must be done within the bootloader before the main program executes. (For example, if you wish to change to a graphics display mode instead of the default text-based mode, you need to do this in the bootloader.)

The main program will be written in C, and compiled so that it expects to reside at the address that the bootloader loads it into the computer. The main program can expect that the bootloader has taken care of basic tasks like switching into 32-bit protected mode (otherwise our C program won't run!), but the C program can carry out operations like setting up interrupts, drawing to the screen, and so forth.

These two components are really different programs, so we will build them separately and then stitch them together into a single "floppy disk image." We will generate an image that could be put onto a 1.44MB 3.5" disk. Of course, you probably haven't seen a 3.5" disk drive in quite some time, so we will use the QEMU emulator to boot our disk image and see what happens. (QEMU is one of the two emulators used for the remaining Pintos labs, so you will already have it on your virtual machine. If not, it is very easy to install.) If everything works properly, you should see your program running in the virtual console!

3.1.2 Relevant BIOS Functions

There are really only two BIOS functions that you will need to use in your bootloader. One is used to interact with the computer's video display, and the other is used to interact with the computer's disks.

int $0x10

This interrupt is provided by the BIOS to support interactions with the computer's display. The bootloader currently uses it to print text messages to the screen (AH = 0x0E "Teletype Output"), and to hide the cursor (AH = 0x01 "Set Text-Mode Cursor Shape") so that Donnie doesn't get distracted by "that annoying blinky thing."

You probably won't need to do anything else with this BIOS interrupt, unless you want to pursue some extra credit by creating a graphical game or demo. Switching into the appropriate display mode is complicated without the support of BIOS, so the best option is to use the BIOS in real-mode to switch the video display mode (AH = 0x00 "Set Video Mode"), and then switch to protected mode. (Note that your program will not be able to use the BIOS calls to draw pixels; you will need to write to video memory directly. This is not terribly difficult, though.)

int $0x13

This interrupt is used to access all of the disk-drive related functionality provided by the BIOS. Our bootloader has very simple requirements for interacting with the computer's disks, though: it never needs to write data, only read it, and the BIOS informs the bootloader of what disk it was loaded from by the value in DL. Thus, it should be very straightforward for the bootloader to load the program into memory.

The BIOS provides two functions for reading disk sectors. One is AH = 0x02 "Read Sectors." However, this call uses the Cluster-Head-Sector (CHS) addressing mechanism, which is limited to small disks, and it requires knowing the disk geometry, which we just don't want to mess with. So, we won't use this operation.

The other BIOS int $0x13 function is AH = 0x42 "Extended Read Sectors," and uses the Logical Block Addressing (LBA) mechanism for referring to sectors. The only challenge of this function is that DS:SI must point to a "Disk Address Packet" (abbreviated "DAP") structure that specifies the starting sector and number of sectors to read. This structure is 16 bytes in size, and must be constructed somewhere: the bootloader might use an adjacent area of memory, or it might construct the structure on the stack. Really, the bootloader can do whatever it wants with memory at this point, as long as it doesn't trample bootloader code or try to write to read-only memory regions. That said, it's probably easiest to push the parts of the DAP onto the stack. Most of the arguments to the BIOS call will be constants, since you will know how large the program is that you must load, and where you are going to load it to.

However you decide to do it, once the Disk Address Packet is constructed, it can be passed to the BIOS handler to read the data from the disk. If you use the stack, release the memory when you are done - it's important to practice good coding habits in all situations, even when it isn't strictly necessary.

You should only load as many sectors as your program actually requires; don't just specify "the maximum number of sectors" to the BIOS call. Note that some BIOSes aren't able to load a large number of sectors at once, and you are limited to 64KiB of sector data by the addressing mode anyway. In practice you should be able to load your whole program in one BIOS call. (If this were a problem you could always load it in multiple smaller chunks, but it shouldn't be a problem.)

3.1.3 Hardware Facilities

Once your bootloader has started executing the C program, we have a number of hardware facilities to set up, otherwise our program will be pretty boring. The most obvious of these is video output. By default, the computer will start in a VGA text mode (80x25 characters, with 16 colors to choose from). Since we are in protected mode, we can't call BIOS operations to write to the screen - but we can write directly into the video buffer, which will cause our data to be displayed on the screen immediately. This turns out to be very straightforward. You will want to create a simple API for clearing the screen, changing colors, and drawing text to the screen, so that you can create your program. (What goes in this API will obviously be dictated by what kind of program you wish to create. You might have similar and/or different operations in your video functionality.)

(It is not recommended due to time constraints, but if you wish to change the video display mode, e.g. so that you can create a graphical program, you should perform such configuration operations in your bootloader, before you transition to protected mode. This way you can rely on the BIOS to perform these operations. Note that writing to the display buffer in graphical display modes can be quite complex, so don't pursue this unless you have the rest of the project well in hand!)

Secondly, if we wish to have some kind of animated display, we would like to have a hardware timer facility to leverage. Since its inception, the IBM PC has provided such a feature that is straightforward to configure and use, and because of backward compatibility, this facility is still provided today. The timer can be set up to fire an interrupt on a periodic interval, and then this can be used to drive various aspects of our program. We don't expect to be particularly efficient with how we use the processor, but the timer will at least allow us to do things on a specific time interval.

Third, interactive programs are always far more interesting than passive ones, so we would like to have some kind of basic keyboard facility. Again, this is reasonably straightforward to set up, as long as we have a PS/2 keyboard to use. (USB keyboards are beyond the scope of this project!) Thankfully, this is exactly what most processor emulators include. The PS/2 keyboard controller can be set up fire an interrupt anytime a key is pressed, and anytime a key is released. An interrupt handler can fetch the keyboard data from the PS/2 controller and feed it to the program.

Of course, these two tasks require basic interrupt handling support to be configured and enabled, and since we will be in 32-bit protected mode, our C program is responsible for setting this up. Interrupt handlers also need to be provided for the timer and the keyboard. All of this turns out to be relatively straightforward to complete.

3.2 Requirements

To receive full credit, your submission for Project 2 must include all aspects described in this section.

3.2.1 Design Document

Before you turn in your project, you must copy the project 2 design document template into your source tree under the name pintos/src/booter/DESIGNDOC and fill it in. We recommend that you read the design document template before you start working on the project.

(As before, you don't have to put the commit-hash into the design document that you check into the repository, since that will obviously depend on the rest of the commit. It only needs to be in the one you submit on the course webiste.)

3.2.2 Bootloader

Complete the bootloader in boot.S. This portion is in IA32 assembly language. You will need to fill in three main components:

You will likely need to refer to various specifications to see exactly what to do for each of these steps. These specifications will be provided in the specs subdirectory of the repository. Relevant sections are noted in the bootloader comments.

3.2.3 C Program

The C program should implement a simple game or interesting demo program of your own devising. The program should utilize the video display (text-mode is perfectly fine; we use the term "video" in a general sense), the PC timer, and the keyboard. To support these last subsystems, you will need to configure and enable interrupt handling, and provide interrupt service routines for the timer and the keyboard.

The main requirements of the program's functionality are:

So, it doesn't have to be a game per se, but it is definitely easiest to satisfy these constraints by building a game. Also, don't get carried away - be conservative in your goals, since you only have one week to complete this project.

A simple example would be a 2-person "Pong" game, with keyboard control of both paddles (e.g. "A"/"Z" keys for the left player, and "Up"/"Down" for the right player), and basic score-keeping.

Another example might be a scrolling "racing-type" game, where obstacles scroll from right to left (or from top to bottom), and the player must move a vehicle to avoid impact with an obstacle. Over time, the speed of the scrolling increases such that the game gets harder and harder. On impact, you can make colorful explosions to mock the player for their bad driving.

There are numerous simple games like this - if you get stumped, you can always look at popular games from the 1970s and 1980s for inspiration. The hardware was extremely limited, but the games were surprisingly addictive.

The entry-point for your C program will be in the file game.c, and it is called c_entry(). You can create whatever other source files you want to create, but several files are provided for the video, keyboard, timer and interrupt-handling portions of the code.

Of course, you cannot use libraries in your program, since whatever you do has to run in a very limited environment. Thus, even basic operations like string manipulation or zeroing a memory region will need to be implemented by you. That said, you probably won't run into these kinds of issues very much.

3.2.4 Program Architecture

You should give some careful thought to the architecture of your program. Given the limited amount of time you have, it may be tempting to just put code into whatever file it seems to be needed in, but this can become confusing and difficult to maintain. Implement video functionality in the video source files. Implement keyboard functionality in the keyboard source files. Keep your main game or demo functionality in the main source file, and call out to the other files as needed to implement your program. And so forth.

This is called separation of concerns, and it makes it easier both to understand and to maintain programs. It is a goal you should pursue for virtually all of your programs; only the very smallest ones won't benefit from it - and who knows, those small programs may in fact grow to become big ones.

3.2.5 Global Variables

While we are discussing program architecture, you may also find yourself wanting to use global variables to implement various parts of your PC booter. Given that you have probably been taught to avoid global variables at all costs, you may not have much experience with how to do this properly in a C program.

You haven't been taught wrong; it really is a good idea in general to avoid global variables; but in a program such as this booter, there really aren't better options for managing state in your program. Perhaps there will be some "game state" that would make sense to package into a struct, and then pass a struct-pointer between various components of your system. But, for an interrupt handler updating a keyboard queue or a timer-count, some kind of global variable really is the cleanest thing to do. That said, there are still better and worse ways to construct such a system.

The cleanest approach is to make sure that all global variables in a particular .c file are only visible within that .c file. You can do this by putting the static keyword before the global variable. This will ensure that the variable is not accessible from other .c files in your project, and you won't run into strange linker issues. If the file's global state must be accessed or mutated from outside that file, provide helper functions that perform operations on behalf of the caller. This maximizes encapsulation of the .c file's internal state, and ensures that code outside the .c file cannot access the state directly.

If this doesn't suit your needs (but really, it should), then you can use the extern keyword to declare a global variable without actually defining it. In your .c file, you can put the definitions for your global state, including any required initialization. Don't mark them with the static keyword, because that doesn't make any sense with this technique. Then, in a corresponding .h header file, put a corresponding declaration of the variable (with no initialization!), marked with the extern modifier. Other .c files in your project can then include the header file, and the compiler will understand that the variable is defined elsewhere. Accesses to these kinds of global variables are resolved at link time.

This is an extremely abbreviated description of how to use the extern keyword. If you want to learn more about this technique, and why it is essential for avoiding linker issues, you should read this highly detailed Stack Overflow answer about the topic. It is so complete that there isn't much that can be added to it - except that you really should try to find a way to use static global variables instead of extern ones! Always do everything you can to encapsulate state as much as possible.

3.2.6 Video Output

The files video.h and video.c are where you can put code that interacts with the video display. You can provide whatever kinds of operations that work best for your game. Additional documentation and references are provided in these files.

Note that you are not limited to displaying just the characters you can type on the keyboard! You can leverage any of the Extended ASCII Codes to draw very nice ASCII art. See http://www.asciitable.com/ for more details. Many games from the 80s used these extended ASCII characters to great effect.

3.2.7 Interrupt Handling

The files interrupt.h and interrupt.c contain basic code to support hardware interrupts. You will need to complete the code that sets up the Interrupt Descriptor Table (IDT), and to install an interrupt handler into the IDT. These tasks are very straightforward, and comments are provided to explain the details.

Your game's entry-point will need to call the operations exposed in this code in order to activate interrupt-handling in your game. You will likely want to do this towards the end of your initial setup, since you don't want to actually turn on interrupts until you have installed the handlers for the timer and the keyboard.

Note that interrupt service routines (ISRs) are expected to be put into the file handlers.S. They will need to be written in IA32 assembly code. You can do anything you want in your ISRs, but it is strongly recommended that you simply call a C function to service the interrupt. Details for how to do this are given in handlers.S.

3.2.8 Timer Interrupt

The timer is configured and managed in the files timer.h and timer.c. Code is provided to do the most basic setup of the Programmable Interval Timer, but you will still need to create the ISR for the timer, and also what to do when timer interrupts fire.

A very simple example would be to have a static "timer-count" variable in the timer.c file, that gets incremented when the timer interrupt fires. This would allow you to provide "sleep(int secs)"-type functionality for your game to use. (Perhaps "seconds" is too coarse a granularity, though.)

Another option would be to have your timer interrupt handler call some functions to advance your game state.

There are numerous approaches you could take; these are just two examples. Whatever you decide to do, you will likely want to add other timer-related operations to timer.h for your main program to call.

The timer is initially configured to fire approximately 100 times per second. You can change this configuration to whatever you want. You shouldn't make the timer fire too fast, or you will be very likely to miss timer interrupts.

3.2.9 Keyboard Interrupt

The keyboard follows the same basic pattern as the timer interrupt, but the data it produces is much more interesting. The files to alter are keyboard.h and keyboard.c.

The keyboard initialization code is much shorter than the timer initialization code, because the keyboard was already configured by the BIOS to generate interrupts. You will need to devise some way to manage the data that comes from the keyboard interrupt handler. What makes this more complicated is that the keyboard generates more information than you might expect - it generates a scan-code for every key-press, and one for every key-release. Some of these scan-codes are one byte, and some are two bytes. (Rarely, you will even see three-byte scan-codes.)

Frequently, a "circular queue" data structure is used to buffer keypress data until a program is able to consume it. It is a simple fixed-size buffer with a "head" and a "tail" index. Data is added to the tail, and data is consumed from the head. Of course, when one of these indexes moves past the end of this queue, it wraps back to the start of the queue; hence the name "circular queue."

Of course, you could use some other mechanism to track keyboard state, e.g. only checking if the keys your program requires are pressed or released. This is not very extensible, and likely to be bug-prone, and it will also likely make it extremely difficult to read keys that generate multi-byte scan-codes. So, some kind of queue structure is recommended.

Whether you use a circular queue, or whether you use some other data structure, you should carefully consider potential synchronization issues that can occur. Interrupt handlers can interrupt anything else that runs on the computer - including code that is accessing data structures that the keyboard handler manipulates. To avoid race conditions, you can always disable interrupts while checking the keyboard data structures, and then reenable them when you are finished. Note that the interrupt handler doesn't need to disable interrupts - this already happens automatically - it is only the code that can be interrupted by the handler.

3.3 Suggested Order of Implementation

This project should be easy to divide among team members, since there are several different self-contained parts to complete. There are two things that need to be done quickly - the first is to get the bootloader working so that testing and debugging of the C program can start quickly, and the second is to agree on an idea for a simple game or interactive demo so that the requirements for the various C components can be nailed down quickly.

The bootloader itself should probably be completed by one person who is familiar with IA32 assembly language programming, since it doesn't require a huge amount of programming. Multiple people can work on it together, but probably more as a pair-programming exercise rather than working on different parts of the loader separately. There just isn't a ton of code to write there.

Writing support code for the various subsystems (video, interrupt handling, keyboard, timer) can definitely proceed in parallel, but some consideration should be given to the way that functionality is exposed. This will be driven by the overall program that the team wishes to create.

While developing and testing subsystems, you will likely find it of value to create simple test functions that can be called from the main entry point, to verify that subsystems are working correctly. For example, a simple test that outputs text to various locations on the screen, to ensure that video output is working properly. Similarly, a program that outputs keyboard scan-codes to the screen, or that outputs text based on a timer interrupt, would also be helpful for verifying the corresponding subsystems.

3.4 Testing

3.4.1 Running Your PC Booter

As with Project 1, there is no automated testing for Project 2. Instead, your program can be run in the QEMU emulator to see how it behaves. The Makefile provided with the initial code has several build targets you can use to exercise your program.

make run-qemu
This target will build the file floppy.img and then run it in QEMU. If everything is working properly, you should see your bootloader run, and then your program should start executing. If you have errors, you will need to diagnose them from what you see, or from running the debugger. (See the next item.)

Note that QEMU is configured to enable PC-speaker emulation, but the support for this is very primitive. Don't expect that sound output will necessarily work from within QEMU.

make debug-qemu
This target will carry out the same steps as the previous target, but it will start QEMU with its GDB debugging stubs active. Additionally, QEMU will halt immediately so that you can connect GDB to the emulator. Details on how to do this are given in the next section.

Note that if you click on the QEMU window, it will trap your mouse! Follow the hint in the QEMU window's title bar, and press Ctrl+Alt in order to get QEMU to release your mouse cursor.

3.4.2 Debugging Your PC Booter

Debugging your PC booter is surprisingly easy - well, easy given the fact that it's a bootable program. Just run make debug-qemu as given in the previous section. Then, in a second terminal window, navigate to the directory where your PC booter is located, and type "gdb program.o". This will load the symbols for your program. (It won't load the bootloader symbols; if you need to debug the bootloader, you will have to look at raw assembly code.)

Next, in GDB, run the command "target remote localhost:1234". This will connect to the halted QEMU program. In fact, QEMU is running perfectly fine, but it provides a "GDB hook" that allows GDB to debug the program running inside of QEMU, and the emulator is initially paused until GDB tells it to go.

Once you have connected to the QEMU session, you can set breakpoints (e.g. at c_entry()() or some other location), and debug as usual.

If you need to debug your bootloader, your job is slightly harder, but not much. You need to do these things in order:

Once you have done the above, you can use the stepi (or just si) command to execute each instruction. Note that stepi will step into interrupt calls! The easiest thing to do is to set a breakpoint on the instruction immediately following the int call, so that you can "continue" to execute until the interrupt operation is finished.

3.5 FAQ

Help! I can't get my program to load at all!

The most common issue that students encounter with loading their program is specifying the target address of the BIOS read-sector operation incorrectly. The address must be in segment:offset form (where the actual address is segment << 4 + offset). Furthermore, since the Intel x86 processor family is little-endian, the segment must be the high 2 bytes of the address, and the offset must be the low 2 bytes of the address. Frequently, students either store the segment and offset in the wrong order, or they use a flat address instead of a segmented address.

You should also verify that you are using the appropriate base; don't use decimal if you meant hexadecimal, or vice versa!

Help! My program seems to load fine, but when I debug it, part of it just seems to be missing!

Make sure you are loading as many sectors as your program's binary actually occupies. This kind of issue is commonly caused by loading only a part of the program binary rather than loading all of it.

3.6 Extra Credit

This is a very open-ended project, and there are many opportunities to try out fun and exciting techniques. Be careful about setting your goals too high - it is much better to turn in a complete, working project, even if it doesn't use fancy techniques, rather than trying to use some advanced technique, running into trouble, and having an incomplete project. (Maximum score on this project is 120 points.)

[ << ] [ >> ]           [Top] [Contents] [Index] [ ? ]

This document was generated by Donnie Pinkston on November, 27 2018 using texi2html