1 of 16

CSE 451

Operating Systems

L2 - The Kernel Abstraction

Slides by: Tom Anderson

Baris Kasikci

2 of 16

Device I/O

OS kernel needs to communicate with physical devices

Network, disk, video, USB, keyboard, mouse, …

Devices operate asynchronously from the CPU

Each with their own microprocessor controller

How does the OS communicate with the controller?

I/O devices assigned a range of memory addresses, separate from main DRAM
CPU read/write memory locations to issue commands/read results

How does CPU make use of the time while waiting for I/O to finish?

3 of 16

Synchronous vs. Asynchronous I/O

Synchronous I/O: Polling

OS pokes I/O memory on device to issue request
While device is working, kernel polls I/O memory to wait until I/O is done
Device completes, stores data in its buffers
Kernel copies data from device into memory

Asynchronous: Interrupts

OS issues request to device via I/O memory
CPU goes back to work on some other task
Device completes, stores data in its buffers
Triggers CPU interrupt to signal I/O completion
OS runs device specific handler; when done, resume previous work

4 of 16

Faster I/O: DMA and Buffer Descriptors

Direct memory access (DMA)

I/O device directly reads/writes computer’s memory (ex: incoming network packet stored directly in DRAM)

Buffer descriptor: data structure to specify where to find the I/O request

E.g., packet header and packet body
Buffer descriptor itself is DMA’ed!

CPU and device I/O share a queue of buffer descriptors

I/O device reads from front
CPU fills at tail

Interrupt only if buffer empties/fills

5 of 16

Physical Address Layout - Reminder

What happens when computer powers up?

How does OS kernel get loaded into memory?
BIOS contains CPU instructions

OS kernel and applications share memory

how do we prevent apps from modifying

kernel data (or data in other apps)

I/O device controllers addressed as memory

CPU sends commands to I/O device through memory reads/writes
how do we prevent apps from issuing commands to read or modify disk blocks owned by other apps/users?

load r1, <address>

bootloader

OS

6 of 16

Buffer Descriptors Illustrated

Buffer descriptor has two pieces of information, one is what operation should be carried out and 2 is where to find the data on which a specific operation will be carried out (read or write).

It is a buffer descriptor in the sense that it describes the buffer of data that I might have. This data may already be in memory. There will also be a valid bit which is set when the I/O is ready, completed.

On the hardware side, everything is a DMA. I’d go and take the head and look for the specific buffer descriptor for it. The I/O device will copy the buffer descriptor to its own memory, using DMA (there is a block of data that I am supposed to read). Then it’ll copy the data over using another DMA. When it is done, it’ll copy the buffer descriptor back in there with the done bit set. Then software can come and read the buffer descriptor, reclaim it to use it for some other descriptor for another I/O.

You can run this super fast on the order of GB/s. One consequence of this is that by just writing to memory, you can cause the I/O device to overwrite anything. The OS has that power. For example the code of the OS itself. I can similarly cause the I’O device to copy anything into memory. If you allowed apps to DMA into memory that’d defeat isolation.

7 of 16

Device Interrupts

How do device interrupts work?

What instruction does the CPU run after an interrupt?
What is the interrupt handler written in? C? Java?
What stack does it use?
Is the work the CPU had been doing before the interrupt lost forever?
If not, how does the CPU know how to resume that work?

8 of 16

Interrupt Vector

Table set up by OS kernel; points to code to run on different events

9 of 16

Interrupt Vector on x86

The thing that we handed you code is different. You can look in xk, there is this file called vectros.s, which is assembly code where the interrupt vectors are.

This code pushes some arguments onto the stack, and sometimes it’s two things because of the way certain interrupts work, which is something we’ll discuss I a couple of lectures. Then it jumps to some code that pertains to all the interrupts. If some have only one argument, I’ll push another one just to make this common code work.

So what does trap.asm do? This will help handle this with C code. So what it’ll do is it’ll save all the current sate of the registers by pushing them onto the stack. mov %rsp, %rdi copies the current stack pointer into register %rdi. The function trap is being called with a pointer to the current stack (trap frame) %rdi holds that pointer → passed as argument 1.

I can now run the C code without worrying that it’d overwrite the prior state.

10 of 16

Interrupt Masking

Interrupt handler runs with interrupts off

Re-enabled when interrupt completes

OS kernel can also turn interrupts off

Eg., when determining the next process/thread to run
On x86

CLI: disable interrrupts
STI: enable interrupts
Only applies to the current CPU (on a multicore)

We’ll need this to implement context switching

11 of 16

Challenge: Saving/Restoring State

Efficient I/O requires us to be able to run something else while the I/O operation is ongoing

Device copies its data directly into/out of memory (DMA, buffer descriptors)
Hardware CPU interrupt signals completion

Thus, we need to be able to interrupt and transparently resume execution of the background task

Code must be unaware it has been interrupted!
Need to restore the program counter
And also all other parts of the CPU state - condition codes, registers, …

12 of 16

Main Points

Process concept

A process is the OS abstraction for executing a program with limited privileges

Dual-mode operation: user vs. kernel

Kernel-mode: execute with complete privileges
User-mode: execute with fewer privileges

Safe control transfer

How do we switch from one mode to the other?

- Interrupts are one way

13 of 16

Physical Memory

14 of 16

Challenge: Protection

How do we execute code with restricted privileges?

Either because the code is buggy or if it might be malicious

Some examples:

A script running in a web browser
A program you just downloaded off the Internet
A program you just wrote that you haven’t tested yet

15 of 16

Process Abstraction

Process: an instance of a program, with limited rights

Cannot modify or read operating system kernel code or data
Cannot modify or read I/O controller memory
Cannot modify its own rights without asking the kernel
Cannot overwrite BIOS or bootloader code
…

Process contains one or more threads and an address space

Thread: a sequence of instructions within a process

Potentially many threads per process

Address space: set of rights of a process

Memory regions that the process can access
Other permissions (e.g., which system calls it can make, what files it can access)

16 of 16

Options for execution with limited privilege?

Execute each program instruction in a simulator?

If the instruction is permitted, do the instruction; otherwise stop
Used in Javascript and other interpreted languages
Logically correct, but kind of slow

Use compiler to prove code safe? Software “sandbox” for untrusted code

Just-in-time compilation of safe code snippets (used in QEMU)
Or add extra checks whenever just when using pointers or indirect jumps
Still somewhat slow

Rely on type safety?

Run unprivileged code directly on the CPU at full speed
Generality? Even Java isn’t type safe with concurrent code