CS 111: Operating Systems - Lecture 2

Jan 9, 2013

Scribe notes by Siu Ching Kwan, John Jang, Xiaodong Sun, Komei Nakamoto

One more problem in building OS

Complexity Continued:

arises because of Moore's Law.
# of transistors on an I.C. at min cost doubles every 2 years
d(technology)/dt = K * technology

How the complexity of OS can cause choke

- Example1:

For the very first successful computer UNIVACI, almost all circutits were error-correcting because no simulators. Here the complexity is the problem for efficient development.
However, for further development, we can use existing computer to simulate circuits, which makes it more efficient.

- Example2: trouble with complexities

Virtual servers are common in many scenes such as in business. Consider a case using tar to back up the several virtual servers built on a single physical server.
We are using the 'tar' utility to back up the servers.

    $cd /or

    tar -cf /backup/1

while tar is running,

    $ echo ordinary > foo

    (tar sees what's in "foo",
    tar: opendir(","), read dir(...), (stat("foo"))

The trouble here is that, attacker can retrieve file stored in other virtual servers
To break into the server by virtual server, attacker can replace his directory or file with a symbolic link pointed to victim file (by guessing the path).
When the system administrator uses the tar utility to restore the file, the tar utility will follow the link and restore the file pointed by the link.

    $ ln -sf /path/to/victim  foo //create a symbolic link to victim file

How to fix this problem?
Use the flag O_NOFOLLOW when opening the file, so that the tar utility will not follow symbolic links.

    [tar open ("foo", ...)

Sample Problem - if without Operation System

Suppose we want a very secure word counter program for a paranoid professor who wrote a proposal but doesn't trust anyone except you to write all the code

Requirements and Specifications

- Machine Specs:

• i3-2130
• 1TB 7200rpm SATA hard drive.
• Intel HD integrated graphics
• 4 GiB dual channel DDR3 SDRAM 1600

- I/O:

• Input: ASCII text file on hard drive
• Output: a number in the center of screen indicating the number of words counted
• Definition of words: [a-zA-Z]+

- Issues:

• How to boot? (power on - bootstrapping)
• How to read input from disk?
• How to output to screen?

The BIOS performs the following tasks:

• Tests the system. (eg. Memory test)
• Looks for devices connected to bus.
• Finds a device that has MBR (Master Boot Record), which means it's bootable.
  BIOS finds MBR by identifying if its last two bytes are 0x55 and 0xAA (little endian). This is called "MBR signature".
• When found the MBR, it loads MBR to 0x7c00 of RAM, and set the instruction pointer to 0x7c00.

MBR

MBR is a 512 byte record that located in the beginning of a disk. The first 446 bytes are x86 code that MBR runs. The next 64 bytes are partition table describing 4 partitions (status/type, start address, size). We only have 4 partitions because of the room limit.

what does MBR do?

• checks the partition table and looks for a bootable disk partition.
• when found bootable partition, loads first sector of the partition, VBR (Volume Boot Record), into RAM.

Finally VBR can read any program we want into memory. Normally, it loads boot program of particular OS.
(e.g. VBR runs GRUB, and GRUB runs Linux kernel.)
The difference between MBR and VBR is that MBR is OS agnostic, meaning it's independent of OS that is booting.

"Chain Loading": in summary, the boot process is in a chain. BIOS loads MBR, MBR loads VBR, and VBR loads boot program of OS.

Read from Disk

CPU, RAM, disk are all connected to data bus and communicate with each other through data bus. Disk is connected to disk controller, which communicates with data bus to perform reads and seeks on disk.

Programmed I/O: a method of transferring data between CPU and other I/O devices by accessing I/O address (bus address).

CPU can load and store from:

• 0x1f7: 8 bits register that stores status and data read from disk.
• 0x1f2: 8 bits register that stores number of sectors.
• 0x1f3~0x1f6: 32 bits sector offset.

How the whole machine and our program works

The big picture:

Semi-complete code:

Put hard disk code into RAM:

Assume Our word counter code has 45 sectos in hard disk, starts from 1200 sector. Also, starts from address 0x7c00 in RAM is where our code will be.

for (i = 0; i < 45; i++) {

  read_sector (i + 1200, (char *)0x150000+i*512;

}

goto 0x150000;

Now define read_sector:

// s is the sector number, and a is the memory address we want to write

void read_sector(int s, char *a)

{

// wait until device is ready

  while ( (inb(0x1f7)&0xc0) != 0x40)  // inb instruction reads address 0x1f7 in bus

    continue;

  outb(0x1f2, 1);  // set the number of sectors to read to 1

  outb(0x1f3, s&0xff);	// put sector number into disk controller register.

  outb(0x1f4, (s>>8)&0xff);

  outb(0x1f5, (s>>16)&0xff);

  outb(0x1f6, (s>>24)&0xff);

  outb(0x1f7, 0x20);  // read sector inscturction is given here "0x20"

  while ( (inb(0x1f7)&0xc0) != 0x40)  // wait until the disk is ready to issue command again

    continue;

  // sends data out of disk cache into RAM, in size of 4-byte words for 128 times

  insl(0x1f0, a, 128);

}

Word Counter Program:

#define isalpha(x) sa[x]

static const char sa[256] = {0,0,0,...1,1,1,...0,0,0};

void main (void)

{
  int nwords = 0;

  bool inword = false;

  for (;;) {

    char buf[512];

    read-sector(1000000, buf);  //1,000,000 is the address where our words are

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

      if (!buf[i]) {

      report_answer(nword);

      return;

      }

      bool thisalpha = isalpha( (unsigned char) buf[j]);

      nwords += thisalpha & ~inword;

      inword = thisalpha;

    }

  }

}

Print out our answer:

void report_answer (int n) {

  uint16_t p = (uint16_t *)0x68014;

  do {

    //print words in backward order

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

    n/=10;

  } while(n);

}