Hardware Support: Privilege Levels and Interrupts

About:

• hardware support for virtualization
  • Privilege levels
  • Interrupts, traps, faults

Interested in making a user process abstraction that prevents user programs from accessing resources they have not been granted access to.

Hardware Features

Hardware features supporting OS functionality

• CPU privilege levels
  • fundamental hardware architecture support feature that is needed to allow isolated running programs
  • what operations are allowed should be integrated in the privilege levels
• MMU (virtual memory)
  • each running program should access independent memory areas
• Exceptions (hardware interrupts, traps / system calls, faults)
  • allows the system to gain control of the CPU at points where it is necessary to do so
  • hardware interrupts: peripheral devices may require attention from the OS kernel, so this is the way they let the kernel know. For certain devices, interrupt is the only way to gain the OS's attention, e.g., timer.
  • system call is one of the most important traps. It tells the OS kernel, "hey there's something i need to do that i can't do on my own" like writing to I/O.
  • software errors also evoke a trap, like division by zero.
  • example of fault: page fault- user program accesses a memory that doesn't exist, then the kernel is called to provide a page of virtual memory.
• Interval timer
  • assume that ordinary software programs will not relinquish control, so the timer is implemented to make sure that the OS gets control at certain points to make scheduling decision.
• I/O devices (disk controllers, network controllers, etc)
  • not exactly fundamental to what the OS does, but a computer system wouldn't be useful if it didn't have some I/O device. E.g., ability for user to interact like a keyboard, hardware storage mechanisms for persistent data, network access (OS needs to mediate access to data transfer over the network on behalf of the running programs).
• Hardware support for synchronization

Architectural support

Two general types of architectural support needed to support OS functionality:

• manipulating privileged state
• handling and generating events

Privileged state:

• OS kernel should create a "sandbox" for user processes. Within the sandbox, the running program can only access granted resources. On the other hand, the kernel should have access to everything without restriction.
• a higher privilege level gives you access to more resources
  • resources/operations that kernel can use vs users need selective granting
• user processes should not be allowed to access these resources outside the sandbox:
  • kernel memory. or else they could edit data structures that grant itself access to everything
  • memory belonging to other processes. (unless agreed upon)
    • e.g., you type a password on a web browser, another application should not be able to see what you typed.
  • hardware device.

How are these privilege levels enforced?

• Example of why you need to restrict: if you allowed an ordinary user program (on x86) to put a new value into the CR3 register (points to the top level page table that defines the address space), then it implies that you are allowing a program to make changes to its own address space meaning that it can access any memory system. Therefore, a move instruction to CR3 is clearly a kernel privilege
• TODO
• One way is to interpret: Instead of directly executing user programs on the CPU, instead the kernel implements a software interpreter, where it would interpret in software the program execution one by one.
  • If the interpret sees them execute a privileged instruction (like move instruction to CR3), then it won't execute it
  • problem: speed penalty of 10-100x compared to native execution in the CPU (or a complexity penalty).
• A better solution is to use CPU privilege levels
  • CPU checks the privilege level of the one trying to executed and checks against the privilege level required to execute it. If a user mode attempts to execute a privileged instruction, it causes an exception
  • all modern CPUs support at least two privilege levels. (two is sufficient and you can't assume you would need more)
    • 32-bit x86 supported 4 privilege levels. "Gates" (interrupt vectors) could specify a minimum privilege level required to use them.
    • When you need a more detailed privilege level, you can always do it in software. This is why two is always sufficient

Basic operation of CPU:

1. fetch instruction
2. decode and execute instruction
3. Either
   1. exception - if instruction is privileged and the current mode is user mode. Store the star address of exception handler in program counter (PC). Any time an exception is raised, then it it switches to kernel mode (exception are always handled in kernel mode) and executes the exception handler.
   2. branch taken. the program counter is loaded with the address of the target instruction (branch = any instruction that involves flow). If reti, return to previous mode. If there is an exception in the stack frame, then that means the code that is executing was reached as a result of a interrupt, the stack frame will tell you what instruction had an exception, which is used to know where to return to in order to continue execution.
   3. otherwise TODO

Privilege instruction: any instruction outside of that sandbox. e..g, mov to a control register like CR3.

• there are other registers that are privilege because they have access to things like interrupt handlers / tables.
• TODO

How to restrict memory access?

• Again, you could implement it with software, but it would be slow
• A hardware solution is hardware enforced memory management. How do you implement that?
  • segmentation: when the kernel returns control to a user process, it sets up hardware registers (base, which specifies the first register the program may access, and limit, which specifies the last address the program may access, registers), and when the user process tries to access a memory address, it compares it to these base and limit registers.
    • E.g., in user mode, any memory reference to address A such that A < base or A >= limit causes an exception.
    • pros: simple to implement (hardware, software)
    • cons: 1) process memory must be contiguous, meaning that it would be difficult to have expandable memory areas (heap or stack data structure, dynamic memory allocation is not efficient) so then you would need the program to request a large memory allotment. but then you would have a fragmentation problem. you would need to move stuff around to make enough space and that would be expensive. 2) poor utilization of system memory. Memory references are not uniformly distributed over the address space (some locations are used more or less frequently).
  • paging virtual memory: a process address space is a sequence of virtual pages (4kb chunk is the standard size for x86) and then there's a data structure that the kernel sets up for a particular process and virtual space. It tells the MMU which pages of the process maps to the physical address. Some pages of the virtual pages can be mapped to nothing at all which.
    • solves the two problems 1) no requirement for contiguous because each physical page is generic (you can assign any virtual page to any physical page). 2) the mapping (virtual <-> physical page) is dynamic and changes as the program runs.
    • the OS kernel has two responsibilities: 1) setting up the virtual address space 2) allocating space. the OS kernel could look at the program and determine what memory it needs in advanced, but it doesn't. It knows where the program wants to load things, but I'm not going to map anything yet. Relies on the fact that when the program tries to access data (like global variables or heap) but it hasn't mapped yet, a page fault would occur. Then this fault would be handled by the kernel and they can make a decision on what to do, and that might be to allocate a physical page, load data, and then map that virtual to physical page. This concept is called demand paging.
    • Uses hierarchical page tables. CR3 points to top level page table. The address first part describes which level 1 entry it is, and then the second part tells you which part of the level 2 entry, which does describe which part of physical memory it points to. These two parts together is the virtual page number.
    • pros: 1) memory can be allocated or deallocated on demand (good for high demand, they can steal memory from pages that are not "hot"). 2) os kernel's page fault handler (software) can implement arbitrary semantics when a page is needed, which enables things like memory-mapped file TODO I/O 3) and address space can be sparse
    • cons: 1) software complexity like the page fault handler. 2) hardware complexity. TLB needed to get good performance for translation between virtual and physical address

What is the kernel? The OS kernel is basically an event handler. Events can be traps, faults, and exceptions. Code execution is the result of the occurrence of these events.

• the kernel doesn't have a main. TODO
• what is an event? An interrupt, which is the way the CPU knows that things need to be handled.
  • The CPU vectors to the handler routines (including switching to kernel mode). In pintos OS, the event handlers are literally c files that are executed.
  • Handler routine saves context (values in CPU registers) so that it knows where to continue execution.
  • Flow: 1) (user mode) user code executes 2) there is an event like an interrupt 3) (switches to kernel mode) save the context 4) handle the event 5) restore the context 6) (switches to user mode) then the user code execution. Between 1 to 6 it seems flawless.
  • asynchronous event vs synchronous event
    • asynchronous can occur at any time like a hardware interrupt
    • synchronous events happen as a direct result of the code that is executed like a system call trap when the user program executes a system call.
  • hardware events (like an interval timer or i/o controller interrupts the cpu to let them know that an I/O operation has finished)
    • these happen at unpredictable times
    • tough problem. Imagine you are modifying a kernel data structure, and then the interrupt happens at the same time and it happens to access that kernel data structure, then it causes a race condition that results in undesirable outcomes.
    • when a hardware event happens the OS kernel needs to execute a handler routine too deal with it.

TODO

Interrupt controller: have a dedicated device to monitor IRQs.

• notifies CPU when device(s) require attention
• supports “masking” (temporarily deferring the handling a subset of IRQs. If a hardware device does assert its IRQ while it is masked, the handling of the interrupt is deferred until the OS kernel unmasks the IRQ) and priorities (if multiple interrupts are active, priorities to determine which gets sent to CPU next). They can also disable processing of all external interrupts.
• 32-bit x86 PCs use two 8529A Peripheral Interrupt Controller (PIC) chips
  • One can be cascaded to the input of the another. The first PIC notifies the second PIC and tells them which IRQ# was triggered (3 bit) and then the second PIC is connected to the CPU and notifies along with the IRQ#.
• In Pintos, IRQs 0-15 are mapped to CPU interrupt vectors 32-47 in src/threads/interrupt.c.
  • Pintos cannot mask individual hardware interrupts.
  • Pintos does use the intr_get_level() and intr_set_level() functions

Interrupt vector

The x86 interrupt vector table is called the interrupt disrupter table (IDT).

• It is an array of “interrupt gates”
• Has a special CPU register (IDTR) that points to the start of this tale
• In pintos: `make_intr_gate

Side note: the scheduler is tied closely to the timer interrupt. If your code looks at the data structures that tracks what processes are runnable. Be aware they don’t overlap with…

Preemption: any thread can only use it for a certain amount of time

This is how a CPU responds to a software interrupt:

• TODO

In the system call API design, it was important to think about how to provide resources to processes in an abstract way so that they have limited access but then they aren’t allowed to specify it themselves.

• File descriptors describe many resources.
• checking system call arguments to verify whether a process is allowed to access a specific resource is very important.

Faults…

Synchronization and interrupts: