Entering and leaving the kernel

Required reading: Chapter 9, 10, 11, and 12 (until sys1.c)

Overview

Big picture: kernel is trusted-third party. Only kernel can execute priviledge instructions (e.g., on PDP-11 loading segmentation registers). The processor enforces this protection through the user/kernel mode bit. (Where are those in the PDP-11? ans: bits 12-15 in PSW). If a user application needs a priviledged service, it must ask the kernel to perform it on its behalf. How can a user program change to the kernel address space? How can the kernel transfer to a user address space? These questions are the topic of today's lecture.

There are three events at which the processor should switch to the kernel address space: (1) supervisor call (called a trap instruction on the PDP-11); (2) an interrupt; and (3) an illegal instruction. (1) corresponds to the case that user program wants to ask explicitly for a kernel service (e.g., switching address spaces). (2) corresponds to the case when a device asks for attention; since devices are shared, we don't want an arbitrary user program to process the interrupt, so the processor should switch control to the kernel. (3) corresponds to the case that the user program got itself in a bad state; by transfering control to the kernel, the kernel can clean up the user program's mess.

Although these three events are different, they all invoke the same mechanism to transfer control to the kernel. This mechanism consists of three steps: (a) change the processor to kernel mode; (b) save and reload the MMU to switch to the kernel address space; and (c) save the program counter and reload it with the kernel entry point. The exact implementation of this mechanism differs from processor to processor, but it is essential that the 3 steps together are atomic. If not, a user program may run with the kernel mode bit, and thus break the protection.

Example: the PDP-11 implementation of this mechanism has 3 steps: (1) save PSW and PC in internal registers; (2) PC and PSW are reloaded from the vector location for the event that causes the switch; and (3) push the internal registers (the saved PSW and PC) on to the new active stack. Step 2 may switch the processor into kernel mode depending on the bits set in loaded PSW (corresponding to step a) . Step 2 loads the kernel entry point (corresponding to step c). Step 1 and 3 correspond to the saving part of step c. Note that step b is implicit on the PDP-11, because in kernel mode the processor has its own segment address registers and sp, thus the processor doesn't have to save and reload the MMU explicitly.

Conceptually, returning from the kernel to a user address space also has the same 3 steps as before: (a) change mode from kernel to user; (b) reload MMU state; and (c) load PC that was saved on entering. On the PDP-11, these 3 steps are performed by a single instruction, rtt, which reloads the PSW and PC from the current active stack. By reloading the PSW, the processor may switch to user mode and switch to using user segment registers.

Interrupts are a hardware implementation of sequence coordination. Conceptually, an interrupt is the hardware equivalent of wakeup. If the processor doesn't support interrupts, the processor has to periodically check on the devices (which is called polling). The problem with polling is how often should the processor poll; if the processor polls to fast, then it wastes resources; if the processor polls to slow, it may take a long time for a device receives attention. Interrups avoid these problems.

Conceptually interrupts are implemented by adding a wire between device and processor; when the device raises the signal on the wire, it sets the "interrupted" gate on the processor. The processor checks the gate between each instruction, and if the gate is set, it invokes the kernel-entering mechanism described above. (The actual implementation is more complicated: to support critical sections, the processor can disable interrupts temporarily. Furthermore, the processor might have multiple interrups levels, as the PDP-11 does.)

V6 code examples

low.s

low.s. what are location vector entries? (Answer: e.g., 512-518 and 526 through 549). where are they located in physical memory? (Answer: addresses 4, 60, 70, 100, 114, 200, 220, etc.) How do you for which vector is used? (Answer: defined by hardware designers and documented in the appendix of PDP-11 handbook.)

Traps

Lets say user program invokes the trap for a system call (e.g., sys exec in proc[1], which contains icode), which has vector location address 034 (28 decimal). Thus, the processor will load PSW with br7+6 and PC with trap (defined on line 755). Furthermore the active kernel stack contains:

	      | saved PSW |  
	      | saved PC (2) | <- sp

• What stack is the active kernel stack? (Answer: the stack of the kernel thread that swtch last switched to; i.e., the user process's kernel stack.)
• After 756 the active stack contains:

  	      | saved old PSW |  
  	      | saved PC  (2) | <- sp
  	      |		      |
  	      | saved new PSW |
  

  
  This code fixes the stack layout so that traps and interrupts can use the same code path. The fixup continues at call1. We save PSW immediately, because tst instruction will set the condition bits, overriding the bottom bits of the PSW that came from the vector table.
• Line 762: save r0, set pc to call1, and store the address of the memory location that contains "_trap" into r0.
• After 771 the active stack contains:

  	      | saved old PSW |  
  	      | saved PC      |
  	      |	saved r0      |  <- sp
  	      | saved new PSW |
  	      
  

  
  R0 is loaded with _trap.
• 772 moves sp down, pointing it to the "saved new PSW" entry.
• 773 set priority to zero; kernel takes interrupts again; end of critical section.
• 774 jump to the code that is shared with interrupt processing.
• Just before 785 the active stack contains:

  	| saved old PSW |  
  	| saved PC      |
  	| saved r0      | 
  	| saved new PSW |
  	| saved r1 |
  	| SP from previous mode |
  	| saved new PSW & !037 | <- sp
  

  
  In the case of proc[1] executing, SP from previous mode will be zero. (Icode hasn't touched it yet.)
• At line 2693 the active stack contains:

  	| saved old PSW |  
  	| saved PC      |
  	| saved r0      | 
  	| saved new PSW |
  	| saved r1 |
  	| SP from previous mode |
  	| saved new PSW & !037 |
  	| return address pc (787) |   // trap came from user space
  	| saved r5 |  <- r5
  	| saved r4 |
  	| saved r3 |
  	| saved r2 |  
  	| cret     | <- sp
  

  
  The compiler inserts at the beginning of the C function "jsr r5 .csv", which implements the function prologue, saving a bunch of registers. 4(r5) will point to first argument of trap, etc.
• 2754: what is fuiword(pc-2)&077? (Answer: kernel will retrieve bottom 6 bits of the word that contains the user trap instruction that caused the processor to get to here. The kernel use the 6 bits as an index into systent.) For example, check icode (the first user-level program on line 1518); the bottom 6 bits (013 = 11 decimal) will correspond to the entry of exec in systent (on line 2910).
• When trap returns, the kernel will return to line 787. Kernel checks whether some other other thread should run. The active kernel stacks is:

  	| saved old PSW |  
  	| saved PC      |
  	| saved r0      | 
  	| saved new PSW |
  	| saved r1 |
  	| SP from previous mode |
  	| saved new PSW & !037 | <- sp
  

  
  line 794: remove saved new PSW & !0x37 from stack.
• Start return to user space. Reload sp register from previous mode with SP on stack (which is the saved SP from previous mode!), and bump saved SP from stack. Thus, active stacks is:

  	| saved old PSW |  
  	| saved PC      |
  	| saved r0      | 
  	| saved new PSW |
  	| saved r1 | <- sp
  

• Line 802: restore r1; bump "new PSW" from stack; restore r0, and return with rtt, which restores PSW and PC. The kernel stack that we trapped into is now exactly as before the trap.

Interrupts

The location vector for clock interrupt is at address 100. Thus a clock interrupt will set PC to kwlp; and PSW to br6. Furthermore the active kernel stack contains:

	      | saved PSW |  
	      | saved PC | <- sp

• line 570: save r0, set r0 to the address "_clock" on line 570, and jump to call.
• line 777: make a copy of current PSW and put it on the stack:

  	      | saved old PSW |  
  	      | saved PC      |
  	      |	saved r0      |
  	      | saved new PSW | <- sp
  

  
  Now we enter the same path as the trap followed. The stack is "identical" to the stack when entering trap, except now we will enter clock. (The only other differences are that kernel still runs at priority level 6, instead of 0 and that the return address may return to line 800 (as opposed to 787), if the clock interrup interrupted the kernel.
• Line 3734, the active kernel stack contains:

  	| saved old PSW |  // previous mode was either kernel or user
  	| saved PC      |  // address to resume execution of interrupted program
  	| saved r0      |  
  	| saved new PSW |  // the one from the location vector (br6)
  	| saved r1 |
  	| SP from previous mode |  // kernel or user stack pointer
  	| saved new PSW & !037 |   // = 0, unused in clock
  	| return address pc (787 or 800) |  // depending on previous mode
  	| saved r5 |  <- r5
  	| saved r4 |
  	| saved r3 |
  	| saved r2 |  
  	| cret     | <- sp
  

• Line 3759: kernel makes sure it wasn't interrupted in callout (because just before callout kernel lowered priority level to 5.) Why lower interrupt level to 5?
• Line 3798: if a second has elapsed and the priority level was non-zero, do book keeping.
• Line 3818: setpri may cause runrun to be set, indicating that the current thread should release processor so that another thread can run. This flag is tested just before the current thread returns to user space (line 788). (This code maintains the rule that threads switch only at well defined points: before returning to user space and in sleep. Interrupts in kernel mode always return to the kernel thread that was interrupted.)

Traps and interrupts

• What does the stack contain if trap() is interrupted by a clock interrupt? How about if trap() is interrupted and then clock() is interrupted (after clock() lowers priority)? Why do recursive traps/interrupts work out correctly?
• Why does timeout() set priority to 7 (line 3854)?
• Line 1564: How does fuibyte work? (Answer: see Lion's beginning of Chapter 10.)