Project 1: Bootloader
Overview
In this first project, you will build the basic environment that
is needed to develop the operating system for the rest of the semester:
the bootloader (bootblock).
Specifically, it will be your job to implement
bootblock.s and
createimage.c.
Every operating system is responsible for enabling other programs to be
run. However, who enables the operating system? This function
is performed by a small program known as the bootloader.
Although bootloaders take a different form with each computer
architecture, the core ideas remain the same. In this project,
you will create a bootloader for the x86 architecture.
In the x86 architecture,
the bootup procedure looks for a bootloader on
the first sector of the booting device (a USB flash disk, hard drive, image file, etc.) and is
automatically loaded and executed during the system booting process. It is
responsible for loading the rest of the operating system from the booting device
into memory. The bootloader cannot rely upon any functionality from
the operating system, such as OS calls for disk I/O, or linking an
object file against static libraries. However, the x86 architecture
requires the presence of the Basic Input Output System (BIOS), which
provides minimal terminal, keyboard and disk support. Your
bootloader will use these BIOS calls to load the kernel from
disk into memory, set up a stack space, and then switch control to
the kernel. At this point, the OS begins running.
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 put the bootloader and kernel executables into a bootable OS image file
that can be directly loaded and run on a machine, similar to how Ubuntu LiveCDs work.
To fulfill the requirements of this project, you must learn the:
- IA32 (a.k.a. x86) architecture and assembly language
- boot process of a computer
- BIOS functions to display messages and load data from disk
- ELF format
The
bootblock.s and
createimage.c in this assignment will be used for future projects
throughout the semester.
We have provided starter code which contains eight files:
- bootblock.s: The template for the bootloader.
- createimage.c: The template for the Linux tool to create a
bootable OS image
- assembly_example.s: A series of assembly language examples
- createimage.given:
An executable Linux tool for you to test your bootblock.s code and validate your createimage.c
- kernel.s:
A minimal kernel to test your bootup code and your tool. Larger kernels used for the extra credit will be provided later.
- man/: Manual for createimage.
Invoked by man -M man createimage in the shell, or found
here
- Makefile: Used to compile and create your files
- bochsrc: The configuration file for the Bochs emulator
The start code is available on the lab machines at
/u/318/code/project1/
Design Review
First, take a look at
what we
expect from you in general.
For this project,
at your design review, we want you to write
print_char
and
print_string functions in assembly.
The first outputs a single character to the screen, and the second outputs
a full string to the screen. Both should start printing at the cursor and
advance the cursor as a result. You may implement these using any BIOS
interrupts. Note that these are functions: they will be called with
call and return with
ret, and they should save and restore any modified registers. You may
choose your own calling convention. The goal for this part (what we're
grading) is your understanding of the organization of the stack and the use of interrupt calls. This
is more important than getting the two functions to work perfectly, although getting the functions to
work may help you test your bootloader in its early stages.
Therefore, when implementing these functions, do it in a copy of
bootblock.s
You should be able to describe:
-
How to move the kernel from disk to memory:
- Where to find it on disk.
- Where to copy it in memory.
- How to do the copying in assembly.
- In which case must your bootloader be relocated?
- How to create the disk image:
- Given an executable (ELF), show how to use the header info to find
where the first code segment begins.
- Show how to determine where in the image file this segment must be
placed.
- Where to write padding.
Though not required for the design review, we also encourage
you to investigate BIOS interrupt 0x13,
which provides low-level access to read or write disk sectors.
You will need this functionality to complete project 1; familiarize yourself early.
Each group must schedule a 10-minute design review slot during the allotted times.
Additional flexibility will be provided only for extreme circumstances.
To sign up for a design review, use
our signup page.
Building
A
Makefile is provided for you. To compile all your files and to generate
the
image file, use the
make command
from within the directory that contains your project.
To remove any files generated by the last
make, use the
make clean command.
The
Makefile initially uses
./createimage.given to build
image.
Once you have implemented
createimage.c, you will have to change
line 54 to use your own
createimage.
Do not make this change until you are sure your bootloader is working.
Bootblock
When compiled,
bootblock.s, will be written to the
first sector of your boot device (USB, an image, etc.). You must write it in IA32
assembly language and its assembled machine language representation cannot exceed 512 bytes
(the size of one disk sector).
bootblock.s must:
- Set up the any registers needed to load the kernel.
- Load the kernel.
- Set up the stack for the kernel.
- Invoke the kernel.
You are required to handle kernels of size up to 128 sectors. Reading up to 128 sectors can be done with
one BIOS call, but you must beware that you cannot cross a
physical
segment (every 64K starting at address
0) in
one read. If using Bochs, reading more than 64 sectors will fail if your image is
used as a floppy disk instead of a hard disk.
When a PC boots the image/disk that you have prepared, and the system
has been initialized, the first sector of the boot disk (the bootloader) is
loaded at address
0x07c0:0000
(
0x7c00 in real addressing mode) and control
jumps to that address.
Your bootloader can safely modify memory in the range
[
0x0a00,
0xa0000) without having to worry about
overwriting video memory, the interrupt vector table, or BIOS.
The kernel should be loaded at address
0x0000:1000. You may assume that the entire kernel is no more than
128 sectors long. Notice that a loaded larger kernel may overlap with the
bootloader, so you will have to relocate the bootloader to a higher address
that can't be overwritten before loading the kernel (see
extra credit).
In order to load sectors, you must know the boot device number, which is
stored in
%dl. Common values are
0x0 for a floppy drive,
0x80 for the first hard drive,
0x81 for the
second, etc. You should save this value for later use.
We have provided
createimage.given which is a
linux-compiled binary version of
createimage
so that you may test your bootloader independently of the next half of the
project. You can create an image using:
./createimage.given --extended bootblock
kernel or simply use the
Makefile.
See
Testing for information on how to test the
resulting
image.
Reading
Createimage
This is a linux tool that combines the bootloader and kernel into a bootable image file.
Part of this tool is to tell the bootloader how many disk sectors to read in order to
fully load the kernel.
When a program is compiled in Linux, an ELF executable file is generated. This file contains
the program code and information telling the OS how
to load the code into memory and what resources (dynamically-linked
libraries, etc.) are required.
However, at this stage, you do not have an OS to load any executable files.
Thus, you must extract the bootloader and kernel from the corresponding
generated ELF executables and carefully laid out in the image file as if it
were memory.
In order to write
createimage, you will need to become especially
familiar with the following features of the ELF file format:
-
ELF headers, and their e_phnum and e_phoff
fields.
-
Program headers, and their p_offset and p_filesz
fields. Note that the p_filesz and
p_memsz properties of a segment in an
executable may differ.
We encourage you to read the
Documentation for the ELF file format
as this document contains extensive explanations of the features you will need for this project.
You are also required to implement the --extended
option. This option is supposed to print information for debugging the OS image etc.
In particular, when given this option, create image is expected
to display the number of sectors used by the image, the specific sector numbers on the disk
which will contain the different executables loaded by
createimage, the segments specified in the ELF headers for each executable file loaded, and
the kernal size (os size) in sectors so that you can have a sense of whether the bootloader will need to
relocate itself to accomodate a larger kernel (especially useful for the extra credit).
To complete
createimage, you will need to implement the following
functions in addition to
completing main():
-
read_exec_file(): Reads in an executable file in ELF format.
-
write_bootblock(): Writes the bootblock to the image file.
-
write_kernel(): Writes the kernel to the image file.
-
count_kernel_sectors(): Counts the number of sectors in the kernel.
-
record_kernel_sectors(): Tells the bootloader how many sectors the kernel has.
-
extended_opt(): Prints the information for --extended option.
To help you get started, you should refer to the man page in the code template by typing
man -M man
createimage to get more information on the functionality of
createimage. You should ignore the "
-vm" option for this project.
Testing
While developing your bootloader, we encourage you to test it using the free
Bochs emulator (
bochs.sourceforge.net).
However, you will be developing a real operating system in this course so your project 1 must work
on real computers.
To complete this project, you must ensure your bootloader works when booted
from a USB flash disk on the lab machines. We will provide you with USB disks. If your code is
correct, you should see the following message upon booting:
"Kernel > Running a trivial test... Test passed!"
With the previous caveat in mind, Bochs
can make debugging your bootloader much easier. The
lab machines have a debugging version of Bochs in
/u/318/bin/bochsdbg.
When it loads your image, it will enter a debug prompt where you can set breakpoints, step through
assembly code, etc. You can get familiar with the Bochs testing and debugging workflow using the
Quickstart Tutorial. You can find full documentation of
the Bochs internal debugger
here.
We strongly suggest you use the Bochs installed on lab machines. The way to login to lab
machines is given in:
How to SSH into the Friend Center Lab.
If you do not set up your
bochsrc file as instructed in the Quickstart, Bochs will create a logfile called bochsout [.txt] which may become quite
large (up to 6 GB!). If you are using Lab 010,
make sure you delete
this file when you're done so that you don't use up all the disk space!
. (If the disk fills up, no one will be able to log in to their normal
session). At this point, you can still log in using the "Fail Safe"
session to delete the file.
Booting off a USB disk
When you are ready to test your
image on a real machine,
you should write it to a flash drive to boot from. On the lab machines, the USB flash
disk is accessed at
/dev/sdg. In general, it may be accessible at
/dev/sda,
/dev/sdb,
/dev/sdc, etc.
You can find the specific device name for it by typing the
dmesg command
into the shell right after plugging your USB disk into the machine. Simply
scroll to the bottom and you will see the sd
x for your thumb drive.
Make sure you have identified the correct device before writing the
image, otherwise, damage may be done to other devices connected to the
machine.
You must prepare your image for the flash drive by marking the image so that the BIOS recognizes
it as bootable. In
createimage.c, write a signature consisting of two bytes,
0x550xaa,
to the end of the first sector: address
0x1fe
of
image.
Once you have prepared the
image file, copy it to your USB disk using
sudo dd if=image of=/dev/sdf bs=512.
Next, with the USB disk connected to the test computer in the lab, restart and boot off the USB disk.
| Resources | Tools |
|
|
-
objdump -M i8086,att [-D | -d]
filename: disassembles a program, showing symbols
and offsets.
-
hexdump: dumps file in hex and other
formats
-
od: octal (and other formats) dump of
a file
|
Checklist
Here is a rough checklist to help you complete the two phases of the project:
-
bootblock
- Set disk segment before fetching kernel from disk.
- Transfer kernel data from disk into memory using answers to "from where", "to where", and "how" from Design Review.
- Set up stack for kernel. (COS217 review: what are the pointers defining the stack?)
- Start executing kernel code at the location where you loaded it into memory.
-
createimage
- read executable header and program header
- read from bootfile and then write into image and pad.
- read from kernelfile and then write into image and pad.
- count number of sectors in kernel
- record number of sectors to bootloader into image file at right location
- handle extended option calculation and printing
Extra Credit
You will get 1 point extra credit if your bootloader can load larger kernels and/or read kernel data from more than one disk head. For the first part, your bootloader will need to relocate itself. In order to do some extra credit, you will need to know
BIOS Int 0x13 Function 8
which can help you get disk parameters and a little bit about the cylinder-head-sector (CHS). In brief, successful BIOS Int 0x13 will return
CH = low eight bits of maximum cylinder number
CL = maximum sector number (bits 5-0)
high two bits of maximum cylinder number (bits 7-6)
DH = maximum head number
Notice that 1 cylinder contains maximal head number of heads, 1 head contains maximal sector number of sectors. You will resort to these disk parameters to read kernel sector by sector. More information about CHS will be covered in the later lectures.
We provided two kernels for your extra credit test. You can download the extra_credit.tar.gz from the same code folder as the start code.
There's one 84-sector medium kernel and one 160-sector large kernel. The medium kernel is self-explainatory.
By loading the large kernel correctly, you should see
Passed Test 1
Passed Test 2
Passed Test 3
If you wish to perform a more extensive test on the large kernel, you should use the bochsrc.large file (provided in aforementioned archive), and create an empty file called output. After running bochs, inspect the contents of the file output. If it worked, it will be full of 32 lines of the text "This is sixteen".
Some thoughts to consider for the extra credit:
- Two adjacent segments in the executable file may
not be contiguous when loaded into memory. The simplest method to handle this case
is to add padding between the segments, so that the two segments seem to be one contiguous segment.
-
A segment in a large kernel might occupy offset
0x7c00, which would overlap with the
bootloader. (0x0000:0x7c00 is equivalent to
0x07c0:0x0000). Your bootloader will have
to copy itself to a higher address that cannot be overwritten when
it eventually loads the kernel.
Program Submission
Don't forget to complete the general
requirements for each project! In particular, you need to
submit a README file, which concisely describes your design and
implementation, and what parts work and what parts you didn't get to work.
You don't have to repeat anything you presented in the design review.
Submit via
Dropbox;
only one person per group should submit. When submitting the assignment, please turn in the files specified in the Dropbox, along with your readme (less than 500 words in text format).