Operating Systems 2020W Final Exam Review
Video
Video from the exam review on April 9, 2020 is now available.
Notes
Final Exam Review
-----------------
A3 topics
- equivalence between named pipes and (unnamed) pipes from pipe()
- general understanding of pipes
- what you can and can't do with them
- specifically, you can't seek on pipes (go backwards, forwards)
- can only read or write (depending on which side of the pipe you have)
- so can only substitute for regular files in these limited contexts
(no seeking, only reading or only writing linearly)
- understanding conditional variables and semaphores
- why they require special implementations
- the basic logic of them
- how poor implementations can lead to deadlock
- processes versus threads
- how to create a process vs how to create a thread
- how making a thread shares memory while a process copies memory
- note how we had to create special shared memory with two
processes but didn't have to with threads, because all is shared
- character devices, block devices
- how to create from scratch
- significance of major/minor numbers
- difference between uid and euid
- how uid is used to indicate process ownership, while
euid indicates process privileges
- if you own a process, you can send signals to it (i.e., you can
kill it)
- basic understanding of what the kernel tracks (in the task_struct)
versus what users see, what is in kernel space and what isn't
- specifically, uid/gid vs usernames and groups
A4/T8 topics
- difference between virtual and physical memory
- file mmap'd into two processes: could have same virtual addresses
but do not have to. Will have same physical addresses
(because same file, loaded only once and shared)
- processes can control layout of virtual memory
- if you coded everything, could control where mmap puts things (mostly),
ask for areas of virtual address space to be made valid or invalid,
change binary so code and data are loaded in different places
- processes can't directly control physical memory
- kernel does what it wants with it
- kernel vfs
- how modules can define file operations for devices by specifying function
pointers in a struct
- can choose functions for read, write, lseek, ioctl, etc
- if you don't define, userspace gets error when trying
to do that system call on your character device
- ioctl
- how it only applies to devices, not regular files
- how tty's are character devices, and how ioctl's allow
us to control tty's
- page sizes in the Linux kernel
- how they are architecture dependent, but the kernel source
abstracts them so most of the kernel doesn't care
- page sizes are determined by the CPU
- page offsets versus page numbers
- how lower bits of virtual address encodes an offset in a page
- walking a page table
- how you do lookups at each level which give the physical address
of the page containing the next level, until we get to the data page
- physical address is really a "page number", i.e. pointer with lower
PAGE_SIZE bits set to 0
A4/T9 topics
- you can use -D on command line to define things in a C program, like #define
- how this can be used to change how programs are compiled
- how with eBPF (as implemented in bcc) the python code runs in userspace, but
compiles and loads C programs into kernel space (the actual eBPF code)
- eBPF programs can watch every system call and arbitrary numbers of
kernel functions and functions in processes (specified by PID or by
library or executable) - crazy powerful
- how eBPF can do much more than ptrace-based programs (strace, gdb)
- ptrace only allows for monitoring one process at a time
- eBPF can watch everything in kernel and userspace
- how eBPF can do powerful things so has to be restricted to root
- what kind of things can it do that regular processes can't do,
even ones running as root?
- how ridiclously often filter() was called in 3000shellwatch.py/bpfprogram.c
- probes can run on function/system call start or exit
- signals (like users) are represented as numbers, not strings, in
the kernel (although signals are encoded using #define's in the
kernel source)
- permissions
- symbolic versus octal
rwxrwxrwx vs 0777
- only care about read, write, execute permissions
(other things are encoded in these bits like setuid, not on exam)
- safety of eBPF versus regular kernel modules
Midterm topics
- see the midterm review
- see the midterm questions
------------------------------------------
BELOW IS EXTRA MATERIAL
Topics to discuss
- mmap
- page table lookups
eBPF safety
- clear termination (can calculate when loops terminate)
- safe memory access (no dangerous pointer arithmetic)
- ?
Page tables are simple data structures
- have to be, are traversed by hardware, and need to be done quickly
What it is doing is splitting up the bits of a virtual address into
offsets into lookup pages
- each lookup page is an array of "pointers",
really page numbers (i.e., lower PAGE_SIZE bits are ignored)
- in a 4K page, we can fit 2^9 64 bit pointers
- we need 9 bits to specify each location in a page
- so page table lookups are literally
- use pointer P to find page of physical memory M
64 bit virtual addresses, 57 bit physical addresses with 5-level page tables
9-bits 9-bits 9-bits 9-bits 9-bits 12-bits = 57 bits
pgd p4d pud pmd pte
start with pointer to page table (which is a pointer to a page)
- this is the pgd page
- in that page, use pgd bits in the virtual addess to get a 9-bit number
- that 9 bit number (0-511) is an offset into the page
- (the page is a 512 element array, with each element
consisting of an 8-byte pointer)
- use this pointer to get the p4d page
Do the same thing for the p4d page, pud page, pmd page, and pte page
- 5 levels
when you do the lookup in the PTE page, you get a pointer to the data page
- where the actual process data is
- last 12 bits of virtual address is an offset into this page
All these calculations ARE NOT ON THE FINAL
- just the idea of 5-level page tables
- difference between virtual and physical addresses