Lecture 2: Abstractions and Bootstrapping

CS111: Operating Systems
Scribes: Joon Lee and John Lee

Secure Word Count Program

Let's suppose that you are designing a word count program for paranoid users who don't trust their computer's word count program, the shell, and even the kernel to manage processing their secret data. But they trust you, so you must design a secure word count program based on the customer's configuration.

Customer Configuration:

• White Box Desktop x86 (32-bit)
• Intel Core i3-4160 3 MiB L3 Cache 3.6 GHz
• 4 GiB dual channel DDR3 SDRAM 1600 MHz
• 1 TB Hard drive SATA 7200 rpm
• Intel HD Integrated Graphics
• Disk Controller

When the user presses the power button the computer should:

1. Boot up
2. Run the word count program
3. Display the word count on the screen

Input:

• ASCII text file less than 1 TB on disk
• Definition of word: [A-Za-z]⁺

Output:

• Number of words in file

The UI consists of just the power button and the screen.



So how does the booting process work?
To answer this question we take a look at the next section, Bootstrapping

Bootstrapping

1. Perform hardware self-tests
2. Scan for devices
3. If device has MBR
   (identified by the signature 0xAA55) it is bootable
4. Loads MBR into RAM at 0x7c00 and the instruction pointer jumps to 0x7c00

RAM (Random Access Memory)

Master Boot Record Layout (MBR)

MBR

#/bin/sh
foo=bar
exec sed "s/foo/$foo/g"

//MBR Code
for (int i = 0; i < 80; i++)  //40 KiB = 80 sectors 
	read_ide_sector(i + 100,0x20000 + i * 512);  //(sector number, memory address) 
goto *0x20000;


void read_ide_sector(int s, int a) {  //read disk sector to the RAM 
	wait_for_ready();
	outb(0x1f2, 1);  //0x1f2 - number of sectors 
	for (int i = 0; i < 4; i++)  //0x1f3 to 0x1f6 - sector offsets 
		outb(0x1f3 + i, (s >> (8 * i)) & 0xff);
	outb(0x1f7, 0x20);  //read sectors
	wait_for_ready();
	
	/*
	When the disk is ready to be read, the results 
	which are stored in the disk controller's cache 
	goes to the CPU first then gets loaded into the RAM.
	insl() copies 128 words (512 bytes) into RAM.
	*/
	insl(0x1f0, a, 128); 
}

void wait_for_ready(void) {  //wait until it's ready
	while ((inb(0x1f7) & 0xc0) != 0x40)  //0x1f7 - status register
		continue;
	/*
	Our disk speed is: 7200 RPM ==> 120 Hz ==> 8.333 ms/rotation. 
	The average time for the read head of the disk to move to the correct track is 10 ms. 
	The average rotational latency is 4.166 ms. 
	Then our average delay is around ~15 ms. 
	*/
}

 //WC Program
void main(void) {
	long long int nwords = 0; 
	int s = 50000; 
	bool inword = false;
	int len;
	do {
		char buf[513];
		buf[512] = 0;  //end of the buffer
		read_ide_sector(s++, (int)buf);
		len = strlen(buf);
		nwords += cws(buf, len, &inword); 
	} while (len == 512);
	display_cws(nwords);
}

int cws(char *buf, int bufsize, bool *inword) {  //cws - count words in sector
	int w = 0;
	for (int i = 0; i < bufsize; i++) {
		bool alpha = isalpha((unsigned char)buf[i]);
		w += alpha & !*inword;
		*inword = alpha;
	}
}

void display_cws(int nwords) {  //displaying on the screen
	char *screen = 0xB8000 + 200;
	do {
		screen[0] = (nwords % 10) + '0';
		screen[1] = 7;  //grey on black
		screen -= 2;
	} while (nwords /= 10 != 0);
}