Scribe Notes: Lecture 2

CS111: Spring 2014

By: Amy Tsao

Goal of today's lecture: build something with a real application without an operating system

Problems with Computer Systems

1. incommensurate scaling

2. waterbed effect

3. propagation of effects

4. Problem of complexity (the biggest one!)

Problem of Complexity

Computer software and architecture is complicated, moreso than every other field. Before computers were built, the single most complicated object was the aircraft carrier. Nowadays, smartphones are more complex than that. We need a way to manage that complexity.

Moore's Law

The number of transistors that you can put on a chip at a minimum cost doubles every two years. Note that this isn't about how fast the chip is, just the number of transistors.

To put it into scale, the number of transistors on a chip was 2 * 10⁴ in 1970. It has since then grown logarithmically to 4 * 10⁹ transistors in 2014.

Kryder's Law

The number of terabytes you can put on a hard drive at a minimum cost

The ability to build is growing at a growing rate.

We're continuously using our tools to develop a better system.

the rate of growth of technology is proportional to technology

(note that the curve is exponential)

Example

1st Univac was designed very conservatively. It was slow and there was error checking galore because they had no way of testing it since it was designed by hand with paper.

2nd Univac used the first Univac for the design, improving on the old design to make it faster and less conservative.

Conclusion

Both hardware and software have become more powerful and complicated. However, sometimes this gets to be too complicated. We want to learn how to be able to build something without an operating system that is specific to our needs (aka standalone or baremetal).

Building a (not) Operating System

In this section, we want to build something with no operating system. Why? Because sometimes you can't always trust the standard operating systems like Linux or Windows because someone can hack into the operating system and mess everything up. In the example, we are going to build something simple -- counting the number of words in a proposal.

Hardware

· x86 Intel Core i3-2130

· 3 MiB cache, 3.4 GHz

· 4 GiB RAM (dual channel)

o DDR3

o 1600 MHz

o SDRAM3

· 1 TB hard drive, SATA 7200 RPM

· Intel HD integrated graphics

Connections

· no network connection

o air gap security

o no wires into the machine except the power

User Interface

We will have it so that the monitor will display the word count as soon as the machine is plugged in.

A Little Bit More About Hardware

The hard disk tells its three platters to read/write some data. However, they don't talk directly -- there is a disk controller that is connected to the hard drive, with the bus connected to the disk controller. To tell the disk controller a command:

1. Wait for it to become ready (this is busy computer, it has other things to do with its time)

· Say the address you're looking at is 0x1F7. You keep looking at that address until you see a particular pattern in those 8 bits.

2. Store number of sectors you want to read into 0x1F2

· How many sectors you want to read I/O in

3. Store which sector you want and read into 4-byte number (store in 4 adjacent controller vector)

· 0x1F3-0x1F6

· Concatenate them

· Little Endian order

4. Store READ command into 1x1f7

· When you store into the command register computer becomes busy

5. Wait for it to be ready (same as the first step)

6. Slurp data from disk controller cache through CPU into RAM

· If you operate on the data you don't have to pull it out again

Bootstrapping

Bootstrapping is running a program that doesn't require extra input. The problem with this is trying to run a program that isn't in main memory. How do you get memory into RAM when the computer starts without memory in RAM? That's where ROM (read-only memory) comes in.

You could put the program in ROM; however, this is highly impractical. This would require us to change the hardware every time we want a new change, and we can't keep calling up Phoenix Technologies every time we want a new change.

BIOS - Basic Input/Output System

This system is hardwired into ROM. The IP (instruction pointer) initially point to BIOS.

BIOS Procedures

1. Tests itself to make sure it works

2. Looks for devices

· starts sending out requests over the bus, "0x1f7, are you ready?"

· gets a response

3. when it finds a drive that looks like a disk drive, it looks for a special pattern in the first sector indicating that the device is bootable

· Need to make sure this is the right one

· Special pattern (specially hard-coded into the ROM)

How to tell if a device is bootable?

Master Boot Record (MBR)

· Tells you how to boot the system

· You look at the last two bytes, 0x55. If this is right, then we're good to boot

· OS-agnostic

Word Count

MBR

|

v

=========================================

|boot | /usr | swap | /home |

=========================================

Partition Descriptor

16 bytes that include:

status (e.g. bootable?)

start sector 4 bytes

size (in sectors) 4 bytes

type (DOS, Linux, etc.)

Last thing that BIO does is jump to the boot program, which lets the boot program gain control of your system. The boot program will read the actual program and run it.

BUT

· Even this doesn't give us enough flexibility

· Could be that some partitions are Windows, and some are Linux (completely different ways of starting up programs)

· What can we do instead?

Volume Boot Record (VBR)

This can be OS-specific. VBR is essentially two programs: boot program and our program (word count).

Part 2: Translating Everything into C

mbr.c --> cc --> mbro --> Id --> mbr executable

The executable should be exactly 512 bytes long (can check with old if=mbr of=/dev/dsk/0 count=1 size=512)

We assume the size of the word count program is about 10 KiB, which means we will have to read 20 sectors. We will also assume that the program resides at 0x8000.

for(int i = 0; i < 20; i++)

//subroutine: what sector we're reading from and where we're reading to

//read_sector(from, sector_number, to memory location)

read_sector(1+i, , 0x10000 + i*512) <-- can't put it in 0x8000, need to put it somewhere else

goto 0x10000; //need to put * in front of address if in gcc

Problem?

· we don't have the read_sector function

//two parameters: sector number and address

//As long as we do the right thing so it doesn't really matter if int a or char *a

static void read_sector(int s, char *a) {

wait_for_ready();

outb(0x1F2, 1); //only want to read one sector

//and then read 4 sectors

for(int i = 0x1f6; i >= 0x1f3; i--) {

outb(i, s & 0xff); <-- & 0xff is actually optional, computer is smart enough to ignore the top bytes

s >>= 8;

}

outb(0x1f, 0x20);

wait_for_ready();

//data is sitting in disk controller cache, pull it out and put into RAM

//insert long (long=32bits)

//want 128 words out of memory and into a[0] ... a[128]

insl(0x1f0, (int*)a, 128);

//we make this a function because we do this twice: once for step 1 and another time for step 4

//param: none

static void wait_for_ready(void) {

//read the bytes from controller 0x1F7

//inb: give it address, tells the bytes in that address

//only care about the top 2 bytes because that tells us if it's ready or not

while(inb(0x1F7) & 0xc0) != 0x40) {

continue;
}

//needs to get data out of the device and into the return register

static unsigned char inb(int a) {

//use actual assembly language

asm(" inb ... ");

}

Random tidbit that you can look up on your own for fun: PIO (programmed I/O)

Now we can do word count!

We assume we've read the word count program:

void main(void) {

unsigned long nw = 0; //number of words)

bool inw = false; //true if in a word, false if not

int s = 21; //start at s=21 because wc = 20

for(;i) {

//local buffer we're reading into

char buf[512];

read_sector(s, buf);

}

for(int i = 0; i < 512; i++) {

if(buf[i] == '\0') { //assume end of file = '\0'

finish(nw);

return; //OR for(;i) and put it into an infinite loop

}

//if the current character is a letter and the previous character was not, then you add 1

//if it's lowercase, it will stay lowercase; if it is uppercase, it will go lowercase

bool mw1 = 'A' || 'a' <= buf[i] && buf[i] >= 'z' || 'Z';

OR

//lowers it if it's uppercase should be between 0 and 26

bool inw1 = (buf[i] | 'a' - 'A') - 'a' < 26u;

nw += inw1 & ~inw;

mw = inw1;

}

}

memory_mapped_output;

This assumes your screen is 24 x 80.

[ 80] [80 ] ... [ 80] (24 of these)

16 bits: half tells what character it is, half is what color to use

memory mapped to: 0xb8014

You start in the middle of the array and write it backwards. This is because it's easier to compute lower digit and harder to compute the higher number.

void finish(n) {

short *p = (short*) 0xb8014;

do {

*p --= '0' + n%10;

n /= 10;

} while (n);

}

End product: stores a neutral black and white number on the screen.