COS 318: Operating systems  

Fall 2006, Princeton University

Project 1: Bootup Mechanism

Important Dates:
Precept I: 8:30-9:30pm Wed. Sept. 20
Design Review: 6:00-9:00pm Mon. Sept. 25
Precept II: 8:30-9:30pm Wed. Sept. 27
Project Due: 11:59pm Mon. Oct. 2
Wei is in charge of this project.
Something about design review: the goal of design review is to help the TA track what you are doing and point out the potential mistakes as early as possible.  We want to make sure that you can finish the project before it's due, so that you won't have to start all over again in the middle of the second week because either of a major design defect, or you haven't started to do it at all.  We don't mind how many mistakes you make at that stage.  In fact we encourage students to make mistakes.  At the stage of design review, the two of you should have seriously thought about the project and discussed in detail so that you have a clear idea of what you are going to do.  In other words, you have started to do the coding, or right about to.  You are expected to show something in material besides speaking to the TA.  It can be step by step pseudocode, code framework, flowchart, or something you think appropriate.  Depending on specific projects, we might also want you to show some running code, or answer certain questions.
To sign up for the design review, please use online signup here.
Overview

In the series of six course projects, you are going to develop a simple operating system, which will cover most of the topics discussed throughout the course.  In this first project, your will build the basic environment that will be needed to develop the operating system for the rest of the semester.  Specifically, your job is to implement two programs: bootblock.s and createimage.c. The bootblock resides on the first sector of the booting device (USB flash disk for this project) and is automatically loaded and executed at system booting process.  It is responsible for loading the rest of the operating system from the booting device into memory.  Because GCC, the compiler used to compile the bootblock and kernel source, generates executable files in a specific format which needs operating system support (of course not available before the operating system itself is loaded) to run, we need the createimage tool to transform and pack them up into an image file that can be directly loaded and run on a bare machine.  This file is called an image because it is loaded into the memory exactly as what it is like on a disc.

To fulfill the requirements of this project, you will need to learn the following knowledge:
The "bootblock" and "createimage" from this assignment will be used throughout the semester.

We have provided a code template for you to use as a starting point.  It can be found on the Princeton machines (arizona.princeton.edu) in either /u/cos318/1_pre/* (or the file /u/cos318/1_pre.tar.  To unpack the tar file type 'tar -xvf 1_pre.tar').  The 1_pre directory should contain six files:
Since our entire project will be using the USB flash disk, please do not read/modify the hard disk.


Bootblock Overview

The file bootblock.s should contain the code that will be written on the boot sector of USB flash disk. This has to be written in IA32 assembly language and should not exceed 512 bytes (1 sector). This code will be responsible for loading in the rest of the operating system, setting up a stack for the kernel and then invoking the kernel.  You are required to handle kernels of size up to 127 sectors.  You will get extra credit if your bootblock can handle sizes greater than 128 sectors.

You can start a PC by pressing the power button, or reboot it by press <Ctrl+Alt+Del> (you may also find a reset button on some models).  After the BIOS has initialized the system, the bootblock gets loaded at memory address 0x07c0:0000 and the control is jumped to that address. Your bootblock should load the OS starting at 0x0000:1000. In real mode, you have 640 KBytes starting at 0x0000:0000. The low memory area has some system data like the interrupt vectors and BIOS data. To avoid overwriting them, you should only use memory above 0x0000:1000 for this assignment.  You can assume that the entire OS is less or equal to 127 sectors for this project.  Remember that the loaded OS image might cover some part of the address space where the bootblock originally resides.  If you are working on your home macines rather than the lab machines, please make sure your program also run on lab machine before submit it because your TA will be testing your program on lab machine. 

Note:
We have provided you with a working binary version of createimage so you don’t have to get your own version done before you test the bootblock.  To test your bootblock you can use the createimage.given file.  Type './createimage.given --extended ./bootblock ./kernel' then 'cat image > /dev/sda' to copy the image onto the USB flash disk.

The links on the main page provide assistance in understanding x86 assembly language and architecture.  The precept will also give assistance in understanding these topics. Unless you are already familiar with assembly programming, you may find debugging low-level boot code more difficult at first. We will cover some general strategies for debugging the boot strap in section, but you may also find it useful to use a PC simulator such as Bochs or Qemu. More information on Bochs may be found at the end of this page.

Note: On the lab machines, the USB flash disk will be detected as /dev/sda. But on other linux machines you might have, USB flash disk could be detected as /dev/sdb or even sd? depending on whether other SCSI devices are present in the system. Please be careful and make sure your USB flash disk is mounted on /dev/sda before saving the image to /dev/sda. Otherwise, you risk ruin your file system on your exististing hard disk.

For the design review you are expected to have working print_char and print_string methods written in assembly. 

Createimage Overview

This program is a Linux tool to create a bootable kernel image.  To make your life a bit easier, we have provided you with a man page in the man directory included in the project directory. You can view the man page by typing

man -M man createimage

Please ignore the "-vm" option for this project.

Essentially, createimage takes a bootloader and several executables and places them all into one image file.  The bootloader must be placed in the first sector, while all other executables should be placed at offset specified in the ELF header.  To read an ELF file use fopen, fread, and fseek.  The program header (figure 2-1 of the ELF Documentation) contains information about each segment in the ELF and should be used to determine the address at which to place the segment.  Be aware of the following:
One more thing you will have to do is to mark the USB flash disk as "bootable device". You will have to put a signature in the boot sector (first sector) of the USB flash disk so that the BIOS will recognize this device as bootable. The signature consists of two bytes: "0x55 0xaa", and you will need to put this signature at the end of the boot sector at offset 0x1fe.  You will also have to figure out a way to inform the bootloader how many sectors to read.

You should read:
Program Submission

Submit your final solution electronically on arizona.princeton.edu using the following command:

/u/cos318/bin/318submit 1 README Makefile bootblock.s createimage.c

The submit command copies your files to the directory /u/cos318/submit/UserLogin/number and lists all the files that you have submitted for assignment number. UserLogin is your user account name. If you execute submit after the project deadline, your files are placed in directory number_late. You can run submit more than once, and you can submit partial lists of files.

Each group needs to submit only one copy.  This means that only one of you needs to submit.

Assembly Language Examples

Please read the assembly language provided before reading this section.  The file bootblock_examples.s also contains several x86 assembly language examples.

Loading an segment:offset
The project will require you to load a number into a segment register to setup the stack and data segments.  The code segment register (CS) cannot be loaded directly, but instead only indirectly through a JMP type instruction.  When loading a value into the stack segment register (SS), interrupts are disabled for the next instruction, thus allowing you to set the stack pointer (SP).  As an example of setting up the segment registers for data, consider the following string copy:

# Setup the registers - see chapter 3 of Intel ISA reference volume 2
movw DATA_SEGMENT, %ax
movw %ax, %ds
movw OTHER_DATA_SEGMENT, %ax
movw %ax, %es
movw STRING_FROM_ADDRESS, %si
movw STRING_TO_ADDRESS, %di

# Move a byte from one string to the other - implictly DS:SI to ES:DI
movsb

# The values in %si and %di are automatically incremented/decremented based on the DF flag.

 

Display memory

For your design review you are required to implement routines that print to the screen.  During booting, you can write directly to the screen by writing to the display RAM which is mapped starting at 0xb800:0000. Each location on the screen requires two bytes---one to specify the attribute (Use 0x07) and the second for the character itself. The text screen is 80x25 characters. So, to write to i-th row and j-th column, you write the 2 bytes starting at offset ((i-1)*80+(j-1))*2.

So, the following code sequence writes the character 'K' (ascii 0x4b) to the top left corner of the screen.
movw 0xb800,%bx

movw %bx,%es

movw $0x074b,%es:(0x0)

This code sequence is very useful for debugging.

Useful BIOS Features

You are allowed to use these BIOS functions to complete this assignment.

BIOS Int 0x13 Function 2 (From Undocumented PC)

Reads a number of 512 bytes diskette sectors starting from a specified location. The data read is placed into RAM at the location specified by ES:BX. The buffer must be sufficiently large to hold the data AND must not cross a 64K linear address boundary. (For our project, for simplicity, you can assume cylinder number bits 8&9, i.e. bits 6&7 of cl is zero).

Called with:
ah = 2

al = number of sectors to read,

ch = cylinder number,  (lowest 8 bits of the 10-bit cylinder number, 0 based)

cl, bits 6&7 = cylinder number bits 8 and 9.

    bits 0-5   = starting sector number, 1 to 63

dh = starting head number, 0 to 255

dl = drive number, (0x80 + zero based hard driver number)  (Note: use dl = 0x80 for the first hard disk. For this project, if you want to boot USB flash disk on the lab machines, you can set dl to be 0x80 because on our lab machines, the USB flash disk will be treated as the first bootable hard disk with dl=0x80. On other machines, this might not be true since different BIOS could treat the USB flash disk as different devices like floppy disk, see note below for more information.)

es:bx = pointer where to place information read from diskette

Returns:
ah = return status (0 if successful)

al = burst error length if ah = 11; undefined on most BIOSes for other ah return status values.

carry = 0 successful, = 1 if error occurred

Note: If you want to make your USB flash disk to boot on machines other than the lab machines, you may also need to save the register %dl at the begining of your bootloader code. The register %dl will contain the correct driver number corresponding to this USB boot device. (Because on different computer, the USB flash disk could be treated differently. We have seen on one computer with AMIBIOS, the USB boot device is being recognized as driver 0x0 rather than 0x80 on the lab machines.) So you can use the right dl value when you call the BIOS function calls.

BIOS Int 0x10 Function 0x0e (From Undocumented PC)

This function sends a character to the display at the current cursor position on the active display page. As necessary, it automatically wraps lines, scrolls and interprets some control characters for specific actions. Note : Linefeed is 0x0a and carriage return is 0x0d.

Called with:
ah = 0x0e

al = character to write

bh = active page number (Use 0x00)

bl = foreground color (graphics mode only) (Use 0x02)

Returns:
character displayed

Extra credits

In order to get extra credits, your bootloader will need to be able to load more than 128 sectors. In order to do that, you will need to use another BIOS call listed below. With that BIOS call, you will be able to get the disk parameter and then read sector by sector to load more than 128 sectors.

 

BIOS Int 0x13 Function 8 (From Undocumented PC)

This function gets the drive parameters for the specified driver.
Called with:

ah = 8
dl = driver number (0x80 + zero based hard driver number)

returns:
if successful:

ah = 0

al = undefined
carry = 0
ch = maximum cylinder number (lowest 8 bits of the 10-bits cylinder number, 0 based)

cl, bits 6&7 = cylinder number bits 8 and 9.

    bits 0-5   = maximum sector number, 1 to 63

dh = maximum head number, 0 to 255

dl = number of drives

if failed (but at least one drive is active)

ah = 7
carry = 1
al = cx = dx = 0

if failed (because no hard disk exists)
ah = 1
carry = 1
al = bx = cx = dx = es = 0

Useful Resources

Besides the tutorial and documentation given on the main page, you might find the following links useful.