CS 111

Scribe Notes for 10/2/08

Creating a proper Operating System:

OS Goals:

• protection
• robustness
• utilization
• performance
• flexibility
• simplicity

What's wrong with our original Word Counting OS from last lecture?

• No flexibility - Too much of a pain to make changes
• Too hard to reuse parts in other programs
• Too hard to run other programs simultaneously
• No robustness - too hard to recover from faults

How to cope with complexity..

MODULARITY - Split the program into pieces

ABSTRACTION - use "nice" boundaries between pieces
Assume N lines of code and K modules

then #Bugs is PROPORTIONAL to N
and the Time to Fix bugs is PROPORTIONAL to N

Without modules: Debug time is proportional to N^2
With modules: Debug time is proportional to (Bugs/K * N/K)K
which is proportional to (N^2)/K

Metrics for "nice" module boundaries

1. Performance - modularity usually hurts performance a bit
2. Robustness - tolerance of faults/errors
3. Flexible/Lack of assumptions/ neutrality - lets the components be used in many different ways
4. Simplicity - easy to learn and use. Has a short manual

Rewriting read_ide_sector

With these metrics in mind, we would want to rewrite our original read_ide_sector function declartion from:

void read_ide_sector(int s, char* addr);

to:

ssize_t read(int diskno, off_t s, char* addr, size_t size);

• bootloader (2)
• word count OS (1)

Properties of our new 'read' function

• Virtualization - pretends to have a 'read' behavior (it is actually built atop inb/insl.. which sends messages to controllers)
• Abstraction - a virtualization that's simpler than the underlying machine

How to implement modularity

1. Don't just create 1 giant function 'main'

   Having one function may be fast, but it is complex and unflexible

2. Function call modularity

   
   

   Since a callee can potentially overwrite the caller's memory, there is a contract between the caller and callee saying that should not happen.

   Take this factorial function for example:

   
   
   int fact (int n){
        if (n == 0)
           return 1;
        else
           return n*fact(n-1);
        }
   

   which in x86 assembly code fact() looks like:

   
   fact: pushl   %ebp
         movl    $1, %eax
         movl    %esp, %ebp
         movl    8(%edp), %edx
         testl   %edx
         jl      .L6
         
   .L5   imull   %edx, %eax
         decl    %edx
         jne     .L5
   
   .L6   popl    %edp
         ret
   

   While the main routine calling fact(5) looks like:

   
         pushl   $5
         call    fact
         addl    $4, %esp
   

   Since the memory for the main routine is located directly above the fact() routine in memory, fact() could potentially overwrite the saved return address of the main routine, or even access beyond the end of the stack.

   This obviously can create dangerous vulnerabilities where the callee could return to an arbitrary peice of code other than the expected main routine.

   This is known as soft modularity. Our goal is to instead achieve hard modularity.

3. Virtualization

   The idea of virtualization is to isolate the OS to a 'sandbox' where everything that happens is contained and will not affect the actual running operating system. Our main operating system will also always be able to take over control when needed.

   Write an x86 emulator

   • checks all memory references
   • times out if the program runs too long (infinite loop)
   • checks all I/O instructions.

   This is a very safe way of running a program, but it also causes it to be very slow.

   Use a virtualizable processor

   • lets us take control whenever a program issues a "bad" instruction e.g. halt, invite.
   • We should also be allowed to gain control periodically even if the program loops infinitely using "timer interrupt"
   • Finally, we should be able to regain control if a program attempts to access memory it shouldn't accessing

   If none of these parameters are violated, the program will run at full speed.

   By combining a virtualizable processor and an operating system, you can run a program in an isolated domain.

How are O.S. primitives invoked?

1. Function calls - Through function calls, an application can do anything without restrictions, which can be potentially dangerous since the O.S. never wants to lose control.
2. Protected Transfer Control - To place restrictions on applications, there is what is called protected transfer control , where the O.S. has a supervisor bit that indicates if an application or O.S. is currently executing instructions.

   '0' indicates an ordinary application so it cannot execute special instructions. If any rules are violated, the application is trapped and control is handed over to the O.S.

   '1' indicates the O.S. is currently in control, and therefore there are no restrictions.

The x86 uses interrupts to make an application HALT when a special instruction is needed. The kernel then takes over and executes the special instructions.

As shown by the figure, applications can perform ordinary instructions directly, whereas special instructions require interfacing with the OS.