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