week 11 cs4973/cs6640 03/17 2025 https://naizhengtan.github.io/25spring/ OSI exam review: 1. OS basics and C 2. RISC-V 3. egos 4. context and scheduling 5. trap to kernel 6. isolation and protection 7. device drivers --- 1. OS basics and C - everything is 0s and 1s * bits and bytes * instructions are 0s and 1s * data: char, int, long long * unsigned vs. signed types - little endian * what is little endian * how 0xdeadbeef looks like in little endian? * configurable in RISC-V machines * we (egos) assume little endian - a program's memory layout * text segment * data segment * stack * heap * Which RISC-V registers point to them? - C pointers * a pointer = a memory address * pointer arithmetic * a pointer of a pointer? -- "void **old_sp" in context switch - common knowledge of C * uninitialized local variables on stack * two ways to access arrays * keywords: * union * static variable * bit field * bit manipulation 10001 & 10000 = 10000 // bit-wise and 10001 | 10000 = 10001 // bit-wise or 10001 ^ 10000 = 00001 // bit-wise xor ~1000 = 0111 // bit-wise not 2. RISC-V - asm(Template : OutputOperands : InputOperands) * Template: a string that is the template for the assembler code. * OutputOperands: the C variables modified by the instructions in the Template. * InputOperands: C expressions read by the instructions in the Template. * for example, int mie asm("csrr %0, mie" : "=r"(mie)); asm("csrw mie, %0" ::"r"(mie | 0x80)); - common RISC-V registers * execution: pc, sp, ra * exceptions: mepc, mtvec, mcause * timer interrupt: mtime, mtimcmp, mstatus, mie - common RISC-V assembly instructions * execution: addi, sw, lw, mv * function calls: call, ret * syscalls: ecall, mret * CSRs: csrr, csrw - calling convention * caller-saved registers: ra, ... * callee-saved registers: sp, ... 3. egos - OS organizations: * monolithic OS * microkernel OS (egos) * exokernel (LibOS) * multikernel - a bird view of egos * three layers: earth, grass, and apps * earth/grass/user apps run in M/S/U-Mode * earth abstracts HW * grass provides scheduling, IPC, and syscalls - earth and grass interfaces * a list of function pointers in a well-known memory location - system apps (part of OS) * sys_proc (GPID_PROC) * sys_file (GPID_FILE) * sys_dir (GPID_DIR) * sys_shell (GPID_SHELL) - OS booting * CPU jmps to 0x20400000 +-> earth.S:_enter +-> earth.c:main +-> grass.S:_enter +-> grass.c:main +-> app.S:_enter +-> sys_proc.c:main | ... | +-> sys_shell.c:main - kernel ~= 3 handlers * handling interrupts (scheduling) * handling exceptions (killing apps) * handling syscalls (run syscalls) - egos exception handler: trap_entry (cpu_intr.c) +-> trap_handler (kernel.c) (ctx_start) +-> ctx_entry() +-> excp_entry(id) +->[your code] +-> ctx_switch() // back to user stack +-> [end of trap_handler] +-> [end of trap_entry] +-> [user space] - handling syscalls: * see "syscall workflow" on reference page 4. Context and scheduling (a) user-level threading - TCB: thread control block * thread id * status * "main" function pointer * function arguments * context (stack pointer, program counter, general purposed registers) - ULT tasks * manages TCBs * make a new stack for each new thread * scheduling * context switch! (in user-space) - context switch in user space * how it works in egos? ctx_start()/ctx_switch() - cooperative scheduling vs. preemptive scheduling * lab2 ULT is cooperative * one can implement a preemptive ULT by using signals (b) kernel schedulers - PCB: process control block * process id * status * context (sp and mepc) * IPC (sender & receiver) * scheduling attributes - process status * Unused, Ready, Runnable, Running, "Waiting" * transition diagram -- definition: preemptive scheduler and nonpreemptive scheduler - scheduling metrics * turnaround time * response time * CPU time * yield numbers - scheduling algorithm * round robin (~= original scheduler) * MLFQ (lab3) -- expectation: since you implemented this, you should be able to remember the details. - "loop &; ls" * the performance difference in the above two algorithms, * and why? 5. trap to kernel---interrupts, exceptions, and syscalls (a) timer interrupt - the backbone of handling timer interrupts void handler() { CRITICAL("Got a timer interrupt!"); // (4) reset timer } int main() { CRITICAL("This is a simple timer example"); // (1) register handler() as interrupt handler // (2) set a timer // (3) enable timer interrupt while(1); } - register timer handler * mtvec - set/reset CPU timer * mtime, mtimecmp - enable timer interrupt * mstatus, mie - how to trigger a timer interrupt? * set mtimecmp accordingly * set the MSIP bit of mip // how we initially implement syscall (b) exceptions - CPU: "I don't know how to progress". - Exceptions are synchronized traps. - RISC-V exception reason table Examples: * read/write invalid memory * run invalid instructions * run privileged instructions in unprivileged mode - handling exceptions: Similar to interrupts. Again, mtvec, mcause, mepc, (c) syscalls - Interfaces for user applications to "talk" to kernel. - Three design questions for kernel developers Q1: how to trap to kernel? Q2: what information is transferred between apps and kernel? Q3: how to transfer the information? - how to trap to kernel * interrupt (skeleton code) * ecall (your lab4) 6. isolation and protection (a) privilege levels - defined by CPU * two bits, may or may not be visible * in RISC-V, it is invisible (MPP hints the privilege level after mret) [updated 03/18:] * M-mode: 3; S-mode: 1; U-mode: 0 - can be a "virtualization hole" * implementing a hypervisor-egos would be a cool final project. * trap-and-emulate hypervisor * VM: simulation of a computer, accurate enough to run an O/S * running the VM's kernel in U-Mode * ordinary instructions work fine * privileged RISC-V instructions are illegal in U-Mode will cause a trap, to the hypervisor * hypervisor trap handler emulates privileged instruction - a program running in the "high" privilege level can * execute privileged instructions, * touch privileged registers (CSRs), * access memory marked as privileged - how to switch privilege levels * low-to-high: interrupts, exceptions, and ecall * high-to-low: set MPP, then mret (b) memory protection - protection = isolation + access control - the access control problem subj --[access]--> obj * for us subj: instructions + context (privilege levels and others) op: r/w/x obj: memory address - solutions: ACL * segmentation (x86-32) * PMP (RISC-V) * paging - segmentation (x86-32) * protecting granularity: a segment, defined by "base" and "limit" * segments are defined in descriptor tables in memory * access right bits are in descriptors - PMP (RISC-V) * protecting granularity: memory regions and privilege levels * regions are defined by pmpcfg and pmpaddr CSRs * access right bits are in pmpcfg registers * limitation: cannot tell different processes ("crash3 proc") - paging * isolation: different roots of page tables provide different address spaces * access control: -- protecting granularity: pages -- access right bits are in page tables, in particular, page table enries (c) virtual memory - virtual memory translation: VA --[translation]--> PA - virtual memory translation: * paging * page table * RV-32 2-level page table (lab5) - page table walk * split the VA to 10:10:12 * walk from the root of the page table (satp) * find the L1 page table page * locate the page table entry (PTE) for L2 page table page * find the L2 page table page * locate the page table entry (PTE) for data page * find the PA in the data page - page faults * invalid PTE * violating the permission bits on PTEs 7. device driver - four ways of communicating with a device * port-IO * memory mapped IO * interrupt * shared memory (e.g., DMA) - combination of mechanism: {polling, interrupt} X {Programmed IO, DMA} - SPI and SD card * exchanging bits and bytes * cmds to SD card * single-block reads/writes * multi-block reads/writes