CS 111 - Fall 2010

David Yang and Kina Winoto

Hard Modularity

"How can we implement hard modularity?"

• Client-Server Organization - We can take each module and place each a seperate computer, this way we obtain parallelism for free if done properly. (e.g. this approach is used by QNX) With this approach, we achieve parallelism if properly set up. We also limit the propagation of errors because the approach lacks shared states (both the client and server can run independently of whether or not the other crashes). Downsides to this approach include slow speed due to high latency between modules, security problems due to authentication issues, higher resource usage, potential transmission errors, and greater complexity.

  On a small scale, this method is inefficient on a small scale because of the amount complexity and resources required.

  	// Client-server factorial call example code
  
  	// Client module
  	// We can package this into a subroutine fact(int) that the client can call
  	// Server waits for subroutine, this implementation has no parallelism
  
  	send (fact, {"!",5} }; 		// second argument = { cmd, arg }, computer 5!
  	receive (fact, response); 	// add timeout
  	if (response.opcode == "ok")
  		print (response, val);
  	else
  		print ("error");
  
  	// Server
  	while (1) {
  		receive (fact, request);
  		if (request.opcode == "!") {
  			n = request.val;
  			int p = 1;
  			for (int i = 1, i <= n, i++)
  				p *= i;
  			response = {"ok", p};
  		} else
  			response = {"no good"};
  		send (fact, response);
  	}
  				

• Instruction Set Expansion - We can extend the machine and expand instruction set so that it can contain new instructions for each server operation. This method protects the server and not the client. This method is not practical because it would require the hardware to be constantly modified to contain these instructions. (e.g. incl, movl, add "factl" %eax, %ebx)
• Virtualization - We can build a virtual machine via an x86 emulator (in C, for example) on top of another machine (e.g. Intel, AMD with factl instruction built on top). We can add the factl instruction to the emulator and run the desired program in this environment. The client would never be in control while the server will be the emulator in control of all emulated processes. This method combines both method 1 and method 2. This method is relatively slow by a factor of 10 compared to the previous approach. Portability was an issue before in the early days of computing because of the limited memory available but this is not as issue anymore. (e.g. emulate instruction count)
• Virtualizable Processor - We can build off the third approach to implement better hard modularity. Taking the emulation of a machine on top of another machine from the last approach (as long as it is virtualizable), we can control what instructions the emulated programs generally execute and still maintain full speed of the program. This approach is faster than pure virtualization. We can separate hardware instructions into two categories - privileged and unprivileged. Privileged instructions have the hardware pass control to the emulator (e.g. the kernel) to decide whether the emulated program is allowed to execute the instructions (e.g. halt). Unprivileged instructions can be run by the emulated program freely (e.g. add, mult). Under this approach, we make the assumption that the vast majority of instructions executed are unprivileged.

  

• Several cons to this approach along with their appropriate fixes:
  • Denial of service attacks, infinite loops of halt - To prevent this, we can tell the emulator to count the number of system calls made. If the counter gets too high, we can stop the emulated process that is calling the system calls.
  • Infinite unprivileged instructions - This would give the emulated program control. An effective counter for this would be to use a timeout from the processor to give control to the emulator in a small interval (e.g. 10 ms).
  • Use store instruction to modify emulator - To fix this con, we partition memory just like we partitioned our instructions, between unprivileged and privileged.
  • Interrupts - We immediately give control to emulator when there is an interrupt.
  • Instructions that interface directly with the hardware (e.g. inb, insl) - All these instructions that talk straight to device will be emulated in the environment.

Hardware Traps

"How is control transferred?"

The hardware traps when a privileged instruction is run and passes control to the kernel (emulator). This can be due to hardware device interrupts, the CPU timer, or invalid instructions as well. Every privileged instruction has an instruction variable and a byte variable. The instruction variable generates an interrupts based on its value. The Linux convention has the byte set to 0x80 for system calls. The kernel maintains an interrupt table (0-255), with each entry a pointer to a privileged instruction that it can execute. When the hardware trap is executed, the stack segment (ss), stack pointer (esp), flags, code segment (cs), instruction pointer (eip), and error code are pushed onto the stack. The instruction reti returns from interrupt and does inverse by restoring stuff off stack. It also sets the a "privileged" bit to 1 during the interrupt routine. After the eip, the kernel (emulator) can execute privileged instructions. This method of hardware traps gives us a protected transfer of control in exchange for some loss in speed.

Potential bugs and their fixes:

• An attacker can try to modify interrupt address table - We can put the interrupt address table in inaccessible memory.
• Infinite loop - We can have a register that denotes a privileged user and an unprivileged user.

(QNX uses a virtualizable processor + client/server message passing)

(Linux uses a virtualizable processor + extended instruction sets)

Layering

We have these ideas of seperate processes on different hardware, virtualization, virtualizable processors, etc. which all boils down to layering , which is formally: building a more useful abstraction from a lower level abstraction. So we are building more and more abstractions on top of other, lower, abstractions. Here's how we're building it:

Layering within a computer system

This layering can also nest. For example on an x86, we have up to 4 levels:

Nested layers with the x86. In Linux, however, we don't have all of these layers.

In order to implement this layering we have to restrict access between the layers:

First, we must restrict access to instructions; we want to be able to stop unauthorized apps from executing certain instructions since we obviously don't want apps to suddenly talk to devices and say take over your keyboard. This gives us two types of code:

1. Priviledged code, which will be able to execute all instructions.
2. Unpriviledged code, which will only by able to execute unpriviledged instructions.

Secondly, we must restrict access to registers: we restrict access to registers depending on the code since we don't want an app overwriting the kernel's stack pointer or something. This also gives us two general types of registers::

1. Obviously, we have priviledged registers. However these are rarely used, but controls access.
2. And we have normal registers, in which the code accesses these at full speed ahead.
But wait. If we just have these normal registers for all processes, what if we have something like cat | dog! Won't cat's registers stomp all over dog's?! So we need to virtualize the registers! Thus this is what happens in memory:

What happens in memory to ensure virtualized registers.

Things to note:
1. The more registers we have, the longer it will take to context-switch.
2. The kernel needs to save and restore only the registers it uses.
3. We don't need to save/restore floating point registers.

Back to what we were saying before, with restriction. Next, we need to restrict access to primary memory. We don't want to give up access to primary memory to processes we aren't in charge of. Thus, each process has its own chunk of memory.

Each process gets its own chunk of virtual memory that has essentially identical addresses. This works via virtual memory that looks much different in physical memory. It's complicated in actual physical memory, but we don't care since we have this level of abstraction!

And lastly, we need to restrict access to devices since as we mentioned earlier, we don't want our processes to randomly be able to take over the keyboard. Or screen. Or send messages to bad people via a device.
We don't have any hardware support for this unlike the above restrictions -- there is no special device like there is special memory. We don't have this support because it's so rare. So it's usually only syscalls typically and those are priviledged.

Interestingly though, there are two different kinds of devices:
1. Request/Response Devices: These types of devices do whatever you tell it to do. This type includes things such as disk drives and graphics cards.
2. Spontaneous Data Generation: These types just give you stuff and include things such as keyboards or network cards.
So how do we give a level of abstraction to these devices? Unix's big idea was to give one single abstraction for all devices! Thus, open, write, read, close, etc are all modeled as devices. Every single device is treated as a file. For example, if we were to type cat /proc/cpuinfo into a Linux terminal, all we would get is the cpu info. This shows that all devices are just treated as files.