ECS 150 – The Kernel Abstraction
Prof. Joël Porquet-Lupine
UC Davis – 2020/2021
Copyright © 2017-2021 Joël Porquet-Lupine – CC BY-NC-SA 4.0 International License /
1 / 26
Process abstraction
Process definition
A process is a program in execution
Disk Source
int x;
…
x = 42;
compile
Executable
.text .data 1011 … 0101
Processor
load+run
Memory
Stack
Heap Data
Instructions
Stack
Heap Data
Instructions
OS kernel
SP
PC
2 / 26
/
Process abstraction
Lack of protection
Multiple processes can be loaded in memory and run concurrently
Issues
Buggy process
Crash other processes Crash the OS
Hog all the resources
Malicious process
Solution
Redefine process abstraction Include notion of protection
Memory
Stack
Heap
Data
Instructions
Stack
Heap
Data
Instructions
Stack
Heap
Data
Instructions
3 / 26
/
Military defense Buggy C software program
OS kernel
Process abstraction
Process RE-definition
A process is a program in execution, running with limited rights
Protected execution
Memory segments process can access Other permissions process has
E.g., what files it can access
Based on process’ user ID, group ID
But efficient
Restricting rights must not hinder functionality
Efficient use of hardware
Communication with OS and between processes is safe
Process 1
Process 2
Process 3
PCB PCB PCB
User Kernel
PID=1
mem uid gid …
PID=2
mem uid gid …
PID=3
mem uid gid …
4 / 26
/
Process abstraction
Limited privilege execution Interpreted execution
Basic model in interpreted languages
Javascript, Python, etc. Emulate each program instruction
If instruction is permitted, then perform it
Otherwise, stop process But execution quite slow…
Native execution
Run unprivileged code directly on the CPU
Very fast execution
But safe execution needs specific hardware support…
Application
Interpreter
Hardware
Application
Hardware
5 / 26
/
Dual-mode operation
Concept
Distinct execution modes supported directly in hardware
Indicated by a bit in processor status register (e.g., 0 or 1)
Can be more than one mode on some processor architectures
Kernel mode
Execution with full privileges on the hardware
Read/write to any memory location Access to any I/O device Read/write to any disk sector Send/receive any packet
Etc.
User mode
Limited privileges on the hardware
As granted by the operating system
User Mode
Kernel Mode
6 / 26
/
Dual-mode operation
Hardware support
Privileged instructions
Potentially unsafe instructions prohibited when in user mode Only available in kernel mode
Memory protection
Memory accesses outside of process’ memory limits prohibited Prevent process from overwriting kernel’s or other processes’ memory
Timer interrupts
Kernel periodically regains control on CPU Prevent running process from hogging hardware
Mode switch
Safe and efficient way to switch mode
From user mode to kernel mode, and vice-versa
7 / 26
/
Dual-mode operation
Typical 5-stage pipeline
Instruction Decode Register Fetch
Execute Address Calc.
Memory Access
Write Back
Instruction Fetch
IF ID EX MEM WB
Next PC
PC
IR
Next SEQ PC RS1
RS2
Next SEQ PC
Branch taken
Register File
Zero?
Memory
Imm Extend
Sign
ALU
Memory
WB Data
8 / 26
/
Adder
MUX
MUX MEM / WB
EX / MEM
ID / EX
IF / ID
MUX MUX
Dual-mode operation
“Dual-mode” 5-stage pipeline
Instruction Decode Register Fetch
Execute Address Calc.
Memory Access
Write Back
Instruction Fetch
IF ID EX MEM WB
Next PC
PC
IR
Next SEQ PC RS1
RS2
Next SEQ PC
Branch taken
Register File
Zero?
Memory
Imm Extend
Sign
ALU
Memory
Exception handler
WB Data
Status Register
Mode
9 / 26
/
Adder
MUX
MUX MEM / WB
EX / MEM
ID / EX
IF / ID
MUX MUX
ECS 150 – The Kernel Abstraction
Prof. Joël Porquet-Lupine
UC Davis – 2020/2021
Copyright © 2017-2021 Joël Porquet-Lupine – CC BY-NC-SA 4.0 International License /
10 / 26
Recap
Process abstraction, v2.0 Protected execution
Native execution
Application
Hardware
Process 1
Process 2
Process 3
PCB PCB PCB
User Kernel
PID=1 mem uid gid
…
Dual-mode operation User mode vs kernel mode
User Mode
Kernel Mode
Hardware support
Privileged instructions Memory protection Timer interrupts Mode switch
PID=2 mem uid gid
…
PID=3 mem uid gid
…
11 / 26
/
Privileged instructions
Definition
Instructions only available to code running in kernel mode
Processor exception if user code tries to execute privileged instruction
Example
And more…
Toggle processor mode Modify memory protection Flush/invalidate caches/TLBs Halt or reset processor
Etc.
int main(void)
{
printf(“Hello!\n”);
/* Try deactivating
* hardware interrupts */ asm (“cli” ::: “memory”);
while (1)
printf(“I win?\n”);
return 0; }
x86_cli.c
$ ./x86_cli
Hello!
Segmentation fault (core dumped)
Illegal instructions are reported as segmentation faults on x86/Linux
12 / 26
/
Memory protection
Concept
Enforce memory boundaries to processes
Processor exception if code tries to access unauthorized memory
Virtual memory
Runtime translation between virtual and physical address spaces
Basic segmentation
Memory area defined by base and bound pair
Process
Memory
Base+ Bound
Base
Raise exception
>
CPU
Process
Memory
Physical address
Base
<
Bound
Translation
Virtual address
Physical address
@virt
@phys
CPU
Raise exception
13 / 26
/
Timer interrupts
Boot sequence
Upon powering on the computer
Privilege mode set to kernel mode
PC set to address of boot code (e.g., BIOS) Boot code runs
Loads kernel image into memory Jumps to kernel's entry point
Kernel code runs
Machine setup (devices, virtual memory, interrupt vector table, etc.) Chooses the first user process to run, loads it, and jumps to it
Privilege bit set to user mode PC set to process' entry point
First process runs
Need a way for kernel to re-take control...
14 / 26
/
Timer interrupts
Hardware timer
Periodically interrupts the processor
Frequency of interruption set by the kernel
Returns control to the kernel exception handler
Also used to maintain accurate and precise time of day
jiffy
tick
tick
P1
P1
P2
P3
P2
15 / 26
/
Mode switching
User mode to kernel mode Exceptions
Triggered by program behavior Intentional or unintentional Synchronous events
Interrupts
Triggered by I/O devices (Better) alternative to polling Asynchronous events
System calls
Request from process for kernel to perform operation on its behalf
Intentional, synchronous events
asm ("cli" ::: "memory");
int *a = NULL; *a = 42;
User code
instruction #n
instruction #n+1
...
Kernel code
Interrupt ...
Interrupt before current instruction
Interrupt
Service
Routine
read:
movq $SYS_read, rax movq $fd, rdi
movq $buf, rsi
...
syscall
16 / 26
/
Return to instruction
Mode switching
Kernel mode to user mode Return from interrupt or system call
Resume suspended execution
Process context switch
Resume some other process
New process start
Jump to first instruction in program
Signal
Asynchronous notification If signal handler defined
P1
P1
P1
P2
P2
P1
P1
(signal handler)
P1
17 / 26
/
ECS 150 - The Kernel Abstraction
Prof. Joël Porquet-Lupine
UC Davis - 2020/2021
Copyright © 2017-2021 Joël Porquet-Lupine - CC BY-NC-SA 4.0 International License /
18 / 26
Recap
Mode switching
User to kernel
Exceptions
Caused by program behavior
Synchronous Interrupts
Trigged by I/O devices
Asynchronous System calls
Service request to kernel Synchronous
Kernel to user
Return from interrupt or system call
Context switch between processes
New process start
Signal handler
P1
P1
P1
P2
P2
P1
P1
(signal handler)
P1
19 / 26
/
Mode switching
Safe and efficient switching
Protect from corrupting the kernel
Entry door to the kernel for processes Reduce overhead of kernel
Maximize CPU cycles for processes
Requirements
1. Atomic transfer of control
2. Exception vector
3. Transparent, restartable execution
20 / 26
/
Mode switching
Atomic transfer of control
Safe transition between modes must be atomic
I.e., in one unbreakable, logical step
CPU mode, PC, stack, memory protection, etc. changed at the same time
User to kernel switch
Save cause for jump
Interrupt, Exception, Syscall? Save current PC
Jump to kernel entry point(s) Switch from user to kernel mode Change memory protection Disable interrupts
Process
Kernel
Kernel to user switch
Jump to process (restore PC) Switch from kernel to user mode Change memory protection Restore interrupts
Process
Kernel
21 / 26
/
Mode switching
Exception vector
Provide limited number of entry points into the kernel
Table set up by kernel: function pointers to exception handlers
Software-managed
Single kernel entry point for CPU
Fixed or configurable address
Software dispatch based on exception cause
Example MIPS processor
/* Exception handler init */
exception_handlers[0] = handle_int;
exception_handlers[8] = handle_sys;
exception_handlers[10] = handle_ri;
...
Hardware-managed
CPU aware of vector Automatic hardware dispatch
Processor Memory
Exception vector
...
handle_int() {
...
handle_sys() {
}
...
}
handle_ri() {
}
...
exception_vector: # Kernel entry point # Retrieve cause from system register mfc0 k1, CP0_CAUSE
# Extract exception code
andi k1, k1, 0x7c
# Use code as index in array
lw k0, exception_handlers(k1) # Jump to proper handler
jr k0
Example MIPS processor
Exception vector
register
22 / 26
/
Mode switching
Transparent, restartable execution
Processes should never know when they are interrupted Save/restore execution context (processor registers)
Software-managed
Hardware-managed
Processor saves all the registers in a provided memory region
Task state segment (TSS) on x86 processors
Rarely used in practice
E.g., not used by Linux or Windows
handle_int:
# Save all registers
sw $1, 4(sp) sw $2, 8(sp) sw $3, 12(sp)
...
...
lw $3, 12(sp)
lw $2, 8(sp) lw $1, 4(sp)
# Jump back to process
eret
# Jump to C function
# that processes interrupt requests jal do_irq
# Restore all registers
Example MIPS processor
23 / 26
/
Kernel stack
Definition
Kernel has its own stack, located in kernel memory Different from process' stack
User process
main() {
scanf(); }
scanf() {
read(0, ...);
}
read() {
asm("syscall");
}
Kernel
handle_sys:
SAVE_ALL
jal do_sys
RESTORE_ALL
do_sys() {
read_sys();
}
read_sys() {
...
}
PC SP
Processor
(user)
main
scanf
read
User stack
Kernel stack
Register File
24 / 26
/
Kernel stack
Context saving
Kernel stack is used to save associated process context
User process
main() {
scanf(); }
scanf() {
read(0, ...);
}
read() {
asm("syscall");
}
Kernel
handle_sys:
SAVE_ALL
jal do_sys
RESTORE_ALL
do_sys() {
read_sys();
}
read_sys() {
...
}
PC SP
Processor
(kernel)
main
scanf
read
Process ctx:
CPU registers
PC, SP
do_sys
read_sys
User stack
Not a good idea to reuse process's stack pointer
Reliability: no guarantee user stack is valid Security: kernel data shouldn't leak to user space
Kernel stack
Register File
25 / 26
/
Kernel stack
One kernel stack per process
Kernel saves its own state when switching between two processes
P1 user stack
main
scanf
read
P2 user stack
user kernel
P2 user stack
main
main
tick
syscall
context switch
context switch
P1 user ctx
read_sys
ctx switch
P1 kernel ctx
P2 user ctx
timer INT
ctx switch
P2 kernel ctx
P2 user ctx
timer INT
ctx switch
P2 kernel ctx
P1 user ctx
timer INT
ctx switch
P1 kernel ctx
P2 kernel stack
P1 kernel stack
P1 kernel stack
P2 kernel stack
26 / 26
/