Project 1: Bootloader
The start code is available on both
Blackboard and the fishbowl machines at the directory /u/318/codes/project1/start_code_1.tar.gz.
Overview
In a series of six course projects, you are going to develop a simple
operating system that will cover most of the topics discussed throughout the
course. In this first project, you will build the basic environment that
will be needed to develop the operating system for the rest of the semester:
the bootloader (bootblock).
Specifically, your job is 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 mininal 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 branch to
the kernel. The kernel will then take over.
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.
Said another way, executables that GCC create assume the presence of
a standard library, dynamic linking, and virtual memory, but those
assumptions are invalid for our purposes.
The
createimage tool creates an image (as opposed to an object);
the difference is that an image makes no assumptions about a standard library,
dynamic linking or virtual memory.
To fulfill the requirements of this project, you must learn the:
- IA32 (a.k.a. x86) architecture and assembly language
- boot process of a PC
- BIOS functions to display messages and load data from disc
- ELF format
The
bootblock.s and
createimage.c in this assignment will be used for future projects
throughout the semester.
We have provided start code which contains six
files:
- man/: Manual for createimage. Invoke man -M man createimage
- bochsrc: Config for bochs
- bootblock.s: A template for you to write the bootloader
- bootblock_examples.s: A series of assembly language examples
- createimage.c:
A template for you to write a Linux tool to create a bootable operating system image
- 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.
- Makefile
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 stack and using interrupt calls. This
is more important than getting the two functions to work perfectly.
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 what 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 interrupt 0x13,
which provides low-level access to read or write disk sectors.
This functionality will be necessary for to complete project
one; familiarize yourself early.
Each group must schedule a 10-minute design review slot. The
Review will take place on Monday, Sep 24 between 10:30am and
10:30pm. Additional flexibility will be provided for extreme
circumstances.
To sign up for a design review, use
our signup page. We provide 50 time slots on Sep 24.
Building
A
Makefile is provided for you. Type
make to compile
everything a generate the
image file. Type
make clean to remove the files generated by the last
make. The
Makefile initially uses
createimage
but you may want to change it to
createimage.given in line 54 for the first half
of the project to focus just on the bootloader.
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 it cannot exceed 512 bytes (the size of one disk sector).
Its function will be to:
- 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. In 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 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.
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. An alternative way to use this is to modify the given
Makefile as described above.
See
Testing for information on how to test the
resulting
image.
Reading
Createimage
A linux tool to combine the bootloader and kernel, and any number of
programs in ELF format, into a bootable image file. Additionally, this tool
must somehow let the bootloader know how many sectors to read in order to
fully load the kernel.
When a program is compiled in linux, an ELF executable file is generated (by
default) that 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. Such an executable may contain multiplei
fragments of code, each expecting to be loaded to a particular offset in
memory -- as specified in the ELF header. When the OS loads the executable
file, it will copy each code fragment to the correct offset in memory.
However, when booting a computer, there is no OS to load the bootloader or
kernel. Thus, the bootloader's and kernel's code must be extracted from the
generated ELF executables and carefully laid out in the image file as if it
were memory. There should be no other required resources specified in the
ELF executables because there will be no OS to prepare them when the code
is loaded (this requirement is reflected in the compiler flags:
-nostartfiles, -nostdlib, -fno-builtin, which have been specified in the given
Makefile).
Because the BIOS will load the bootloader to offset 0 (of segment
0x07c0), the compiler must be told that the
starting address is 0 using the
-Ttext flag.
Similarly, the kernel's starting offset is set to
0x1000. Thus, when the BIOS loads the first sector of the image to
offset 0, the bootloader will be ready to run. When the bootloader simply
copies the kernel to
0x1000, it too, will be
ready to run.
Students are also required to implement the --extended
option. 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 image, the segments specified in
the ELF headers, and the kernal size (os size) in the unit of sector so that you can have a sense of whether the bootloader will need to
relocate itself to accomodate a large kernel.
Note:
-
The filesz and
memsz properties of a segment in an
executable may differ. This means that when writing the segment to
memory (or writing to an image), you may have to add padding so that
the segment occupies all of memsz
-
Two adjecent 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.
For specific information on the functionality of
createimage, refer to the
man page
provided in the code template by typing
man -M man
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 so it must work on real
computers.
You must ensure your bootloader works when booted from a USB
flash disk on the lab machines. We will provide you with USB disks.
Booting off a USB disk
One the lab machines, the USB flash disk is accessed at
/dev/sdf. In general, it may be accessible at
/dev/sda,
/dev/sdb,
/dev/sdc, etc.
Make sure you have identified the correct device before writing the
image, otherwise, damage may be done to other devices connected to the
machine.
When you are ready to test your
image:
-
Mark the image so that the BIOS recognizes it as bootable. Write a
signature consisting of two bytes, 0x55
0xaa, to the end of the first sector: address
0x1fe of image. Don't forget to do this in createimage.c
-
Copy it to your USB disk using cat image >
/dev/sdf, assuming /dev/sdf is the
USB disk you intend to boot from. You may also use dd if=image of=/dev/sdf.
-
Next, connect the USB disk to the test computer (which in this case is a machine in fishbowl, you are welcome to try others, e.g. a virtual machine or a simulator), restart, and boot off the
USB disk.
Bochs
Bochs can make debugging your bootloader much easier. If Bochs has been
configured with the
--enable-disasm and
--enable-debugger flags during compilation,
then when it loads your image, it will enter a debug prompt where you can
set breakpoints, step through assembly code, etc. The lab machines have
a debugging version of Bochs in
/u/318/bin/bochsdbg. The Bochs Windows
installer will install both
bochs and
bochsdbg (or
bochs-debugger in the newer version of bochs).
We strongly suggest you use the bochs installed on lab machines. Installing a new one on you own machine may bring you troubles when you use the given code due to version or 32-bit/64-bit issues. The way to login to lab machines is given in:
How to SSH into the Friend Center Lab.
To test
image with Bochs:
- Setup Bochs
-
Run bochs or
bochsdbg from the same directory as the given
bochsrc and the generated image
-
Bochs will stop at a prompti if you run bochsdbg. Type c to
continue execution. You'll probably want to set a breakpoint at your bootloader
using b 0x7c00
before continuing.
Take a look at some other debugger commands.
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.
| 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
|
Extra Credit
You will get 1 point extra credit if your bootloader can load larger kernels which needs to relocate bootloader and/or read kernel data from more than one disk head. In order to do this, 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 either Blackboard or the fishbowl machines at the directory /u/318/codes/project1/extra_credit_1.tar.gz.
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".