|[ << ]||[ >> ]||[Top]||[Contents]||[Index]||[ ? ]|
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.
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.
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.
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
gcc. The IA32 machine code emitted by
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!
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.
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.)
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.)
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.
To receive full credit, your submission for Project 2 must include all aspects described in this section.
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
(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.)
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.
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
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.
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.
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
.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
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
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
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
variables instead of
extern ones! Always do everything you can to
encapsulate state as much as possible.
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.
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
The timer is configured and managed in the files
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
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.
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
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.
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.
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.
floppy.imgand 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.
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.
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:
set architecture i8086" so that the debugger will show you 16-bit x86 assembly code
break *0x7c00" so that the debugger will stop at the first instruction of your bootloader
c" (or "
continue") so that the debugger will resume executing, until it hits the breakpoint you just set
display/5i $pc" will cause GDB to always show you the next five instructions to be executed, so that you can see what is going on
Once you have done the above, you can use the
stepi (or just
si) command to execute each instruction. Note that
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
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
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!
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.
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.)
As mentioned earlier, the easiest way to change the display mode is to do it in your bootloader, and then implement your video drawing code in your C program.
You will probably want to read this page to get started: http://wiki.osdev.org/Drawing_In_Protected_Mode. Then, you will need to find documentation on the graphics mode you decide to use. CGA is relatively simple, but you will only have 4 colors and 320x200 pixel resolution. EGA and VGA give you many more colors, but the various display modes can require complicated interactions with video memory in order to draw pixels.
Finally, once you switch to a graphical mode, you will have to draw text on the screen all by yourself! Most graphics code includes font tables for drawing characters on the screen in graphical display modes.
To get these points, you will need to demo this to Donnie. You can use
dd utility to dump your disk image to a physical device;
there are numerous tutorials for
dd on the Internet.
NOTE 1: This will not work on a Mac, since Macs use UEFI rather than BIOS for bootstrapping the computer. You will need to have a reasonably modern PC computer.
NOTE 2: Do not reboot the CS lab computers to test your program on the lab hardware! If you are discovered doing this, you will receive a substantial point deduction on this assignment.
The Programmable Interval Timer (PIT) has three different channels for generating timer events. We already use Channel 0 to generate timer interrupts, but Channel 2 can be routed to the PC speaker to generate tones of varying frequencies. (Channel 1 hasn't been used much since the original PC computers, so not all emulators support it.)
The only problem with trying to get PC speaker audio working is that both
QEMU and Bochs have very limited support for PC speaker emulation. Thus,
you will probably need to try PC speaker output on a real computer.
Another option is to try running your bootable image in QEMU directly on
your computer; i.e. not within a virtual machine on yoru computer. (You
will also need to specify a command-line like
qemu-system-i386 -soundhw pcspk ..." to enable PC speaker
You can read more about PC speaker output at this URL: http://wiki.osdev.org/PC_Speaker. You should find that this is not particularly difficult to program, but it is more difficult to actually test, since you will probably need a physical computer to do so.
|[ << ]||[ >> ]||[Top]||[Contents]||[Index]||[ ? ]|