Courtesy of Saltzer et al., Principles of Computer System Design (2009)
Thursday, April 5, 2012
Instructor: Professor Paul Eggert
UCLA
Scribe Notes by James Hung
Imagine a world without operating systems. Now why would we not want an operating system, especially in this day and age? Well, we might be paranoid and therefore not trust any operating system written by a third party. However, we still want to get work done. In this case, we want to count words in a text file. To accomplish this, we will write a standalone program that does not require an operating system at all. Here are some requirements and design considerations for this program:
'\0') represents End of File (EOF).We now face a few problems. How are we going to load our program into RAM in the first place, since RAM is always initialized to all zeros upon powering on the PC? How are we going to get bytes off the disk into RAM? How are we going to output to the screen? To answer these questions, we must first understand the boot process of a typical x86 PC.
A special read-only region of the RAM is reserved for the BIOS (Basic Input Output System). When a PC is powered on, the BIOS is loaded from non-volatile memory such as flash or EEPROM to this RAM region. The instruction pointer will point to this region, enabling the CPU to begin executing instructions and therefore begin the boot process. The BIOS performs a Power On Self Test (POST) and detects devices on the bus by probing addresses. The figure below shows an example of a basic computer system with several modules connected by a shared bus:
Courtesy of Saltzer et al., Principles of Computer System Design (2009)
Finally, the BIOS searches for a bootable device. This leads us to the discussion of the PC's storage subsystem.
A hard drive physically consists of one or more magnetic platters that spin at a constant speed, typically 7200 RPM nowadays. Each recordable platter surface is logically divided into rings called tracks, and each track is divided into equal sized blocks. For each recordable platter surface, a read/write head mounted on a seek arm flies a few nanometers above the rotating surface. See figure below for illustrations:
Courtesy of Saltzer et al., Principles of Computer System Design (2009)
Traditional hard drives have 512-byte sectors, but in the recent years hard drive manufacturers have been moving to 4K sectors ("Advanced Format") in order to accommodate larger storage capacities.
The hard drive is the slowest component of a computer system. In order to read data from random locations on the disk, the hard drive must position the head to the track containing the desired data. This seek process on average takes several milliseconds on a modern hard drive. Since the platters are constantly rotating, the drive then must wait for the data arrive under the head, which takes a few more milliseconds. This can add up to more than ten milliseconds. Relatively speaking, a processor can execute millions of instructions in that short period of time. In order to compensate for this latency, disk controllers have small RAM as cache.
The disk controller exposes to the bus a small number of registers that the CPU can load or store from:
| Bus Address | Description | Length |
|---|---|---|
| 0x1f7 | Control / status | 8 bits |
| 0x1f2 | Number of sectors | 8 bits |
| 0x1f3 - 0x1f6 | Sector offset | 32 bits |
The BIOS manipulates the disk controller's registers to load sector 0 of the hard drive into RAM address 0x7c00 (recall that a sector is 512 bytes). Sector 0 is where the Master Boot Record (MBR) is located. The BIOS verifies that an MBR exists by checking if the last two bytes of the sector is 0x55 and 0xAA (or, written as a little-endian 16-bit word, 0xAA55). The layout of the MBR is shown below (not drawn to scale):
| x86 code 446 bytes | Partition table entry 16 bytes | Partition table entry 16 bytes | Partition table entry 16 bytes | Partition table entry 16 bytes | MBR signature (0x55, 0xAA) 2 bytes |
Each partition table entry has the following fields:
At this point, the BIOS has loaded sector 0 and verified that it is indeed an MBR. It will thus proceed to execute the x86 code in the MBR by jumping to address 0x7c00. Since you can't write much code given a 446-byte constraint, MBR code typically does the following:
Note that while the MBR is OS-agnostic, the VBR is OS-specific. For example, in Linux, the VBR loads the GRand Unified Bootloader (GRUB), which in turn loads the Linux kernel. Once the kernel is loaded, GRUB is no longer needed.
In our toy example, the VBR will load our word count program.
The following is the conceptual C code for our word count program. The comments in the code contain some additional useful information, so please do take a look at them.
/*
* inb stands for the inb x86 instruction, which reads a bus register.
*/
char inb(int addr)
{
asm("inb", ... addr);
}
/*
* This function lets us read a disk sector into RAM. It does this by talking
* the disk controller via its registers.
*/
void read_ide_sector(int s, char *a)
{
// Wait until disk is ready.
while ((inb(0x1f7) & 0xc0) != 0x40)
continue;
// Read only 1 sector.
outb(0x1f2, 1);
// 32-bit sector offset represented by four 8-bit registers.
outb(0x1f3, s & 0xff);
outb(0x1f4, (s >> 8) & 0xff);
outb(0x1f5, (s >> 16) & 0xff);
outb(0x1f6, (s >> 24) & 0xff);
// Tell disk controller to READ_SECTORS.
outb(0x1f7, 0x20);
// Wait until disk is ready.
while ((inb(0x1f7) & 0xc0) != 0x40)
continue;
// Store sector to a. The following instruction means, do the following
// 128 times: Get 32-bit (4-byte) data from register 0x1f0 and store to a.
// 128 * 4 bytes = 512 bytes, which is an entire sector.
insl(0x1f0, a, 128);
}
/*
* This function outputs a number to the screen.
*
* How does screen output work? There is a special memory region beginning at
* address 0xb8000. Whatever you write to this special memory region will
* appear on the screen. Since we are in text mode, the screen is a 80x25 grid
* (80 cols, 25 rows). Each character is represented by 2 bytes:
*
* - Low order byte: ASCII character to be printed.
* - High order byte: Attributes of the character (color, blink).
*/
void write_out(unsigned long long n)
{
// Print the word count at approximately the center of the screen.
char *p = (char *)(0xb8000 + 80*25*2/2 - 20);
do {
// Least significant digit.
int lsd = n % 10;
*--p = 7;
*--p = lsd + '0';
n /= 10;
} while (n);
}
/*
* Actual word count program.
*/
void main(void)
{
unsigned long long words = 0;
bool in_word = false;
// Start at the following sector.
int s = 100000;
for (; ; s++) {
char buf[512];
read_ide_sector(s, buf);
for (int j = 0; j < sizeof(buf); j++) {
if (!buf[j]) {
// EOF
write_out(words);
return;
}
bool this_alpha = isalpha(buf[j]);
words += (this_alpha & !in_word);
in_word = this_alpha;
}
}
}
We have now satisfied the paranoia requirement. However, there are still other issues to consider.
While our program is fast, we can further improve performance. Right now, our program reads one sector, performs computations, and repeats until it reaches the end of the file. Instead, we could have done one or more of the following:
While standalone programs are great for paranoid developers, they suffer from several disadvantages:
Consider the first two points. Since the MBR, VBR, and our word count program each needs to read sectors, each requires a separate copy of read_ide_sector. Any changes made to read_ide_sector has to be applied to all three copies of the code, which is bad.
One solution would be to place common code in the BIOS. While this was really the case back in the days, it has proved to be too inflexible. For example, one would have to go through the hassle of flashing the BIOS (and risk bricking their computer in the event of a power failure in the middle of flashing) in order to update the software. Modern OSes do not make use of such BIOS routines, even though they may still be there for backwards compatibility reasons.
Instead, we should have an OS-specific reader that provides functionality similar to read_ide_sector. We can make the reading function more generalized so that it becomes something like ssize_t read_file(int file_descriptor, off_t byte_offset, size_t buffer_size). As you can see, the function has been generalized to work with files instead of drives directly, and the caller does not need to work at such a low level as sectors (abstraction). This generalization and abstraction enables the function to be reusable by others as a module (modularity). We can then go on and get rid of the byte offset so that each call to the function automatically reads the next byte. This would mean we would need a function like off_t lseek(int file_descriptor, off_t new_byte_offset, int flag) to move the read pointer around in the file when needed.
Did we just make our API too complex, or did we make our lives easier? It really depends on your perspective. There are always tradeoffs.
This document is fully HTML 4.01 compliant: