Operating Systems 2026F Lecture 14

Video

Video from the lectures given on November 10th and 11th, 2026 are now available:

• Lecture 14A
• Lecture 14B

Notes

Lecture 14A

Lecture 14A
-----------
eBPF

First, how do you know what a process is doing?
 - from the outside?

remember processes are separated from each other
 - separate memory
 - take turns on the CPU

On UNIX-like systems, there is the ptrace system call
 - used by gdb, strace, etc

ptrace is great for development, but not good for production
 - can change how programs behave
 - programs can observe they are being monitored

Better way to monitor processes (and more!) is eBPF
 - direct ancestor is DTrace from Solaris

What is eBPF?
 - "enhanced Berkeley Packet Filter"
 - but the enhanced is doing a lot of work here!


Normal way to monitor network traffic:
 - a process asks for packets
 - the kernel gives the process packets

What if 1) the network is fast, and 2) you only want to look at some of the packets?
 - ideally, the process would only want to get the
   packets it wants rather than all of them
   - otherwise performance could be very very bad

What if the kernel could be given the filter, so it would then know what packets the process was interested in?
 - only the requested data would move out of the kernel
   and into userspace (the requesting process)


But how can we design an API for filtering arbitrary network packets?
 - so, let's let userspace give the kernel a program
 - the program will specify what packets we are and are not interested in

  processes
  --------    <--- kernel/userspace boundary is expensive
  Kernel           to cross
  --------
  Hardware

So how can we pass code to the kernel in a way that the code won't corrupt the kernel?
 - we make a (language) virtual machine!

Initially the language of BPF was a simple bytecode language designed for packet filtering

But then some folks thought, what if we could use this virtual machine for more things?
 - so that's eBPF

eBPF has a number of...quirks...in order to make it safe and secure

For example, you can't do arbitrary loops in eBPF

Randomness
 - how can a computer be random?

Computers can run algorithms that produce pseudo-random number sequences
 - sequences that look "random" according to statistical tests
 - but because they are generated by an algorithm,
   the output is deterministic
 - they can look random by changing their initial state,
   i.e., their seed

So how can a computer get a random number?
 - use the physical world!

The operating system is the part of the system that can observe the physical world in the most direct way
 - network packets arrival
 - keyboard events
 - hard drive access patterns (mainly for spinning metal)
 - CPU random number generators

These are known as "sources of entropy"
 - different sources will have different amounts of unpredictability, e.g. entropy

To convert entropy sources to secure "randomness", we use cryptographically secure pseudo random number generators with the entropy sources as the "seed".

When you access /dev/urandom, you get bits from a cryptographically secure pseudo random number generator that has been seeded with entropy from the physical world (ideally)

mmap
 - just an area of shared memory
 - can be used instead of read/write

Instead of
 - open, read/write, close

We can
 - open, mmap, close

mmap associates part or all of a file with a block of memory
 - so now you can access the file like it was memory!

But also, mmap can be used to allocate memory that can be
shared between processes
 - anonymous mmap

Lecture 14B

Lecture 14B
-----------
eBPF
pseudo randomness
dining philosopher's problem
mmap

eBPF
----

strace, gdb, other debugging tools
 - how can they work in the first place,
   given the restrictions on processes?

They can work because the kernel provides the functionality for one process to monitor and change the behavior of another
 - ptrace!

ptrace is great for debugging, but not great for production
 - very slow
 - intrusive (i.e., the traced program's behavior could change
   due to being monitored)
 - only one process at a time
   - but this can be worked around

Solaris first had dtrace
 - designed to allow very low overhead, robust monitoring of production workloads

So...why eBPF?
 - stands for enhanced Berkeley Packet Filter
 - enhanced is doing a lot of work here!

How can you monitor network traffic efficiently?

You can have a monitoring program just ask for all the packets, and it will get them
 - but for a busy system it will be A LOT (so major performance implications)
 - and most of the time, you only want some of this traffic, potentially very little

So how can we tell the kernel we only want traffic matching certain criteria? How do we define a filter?
 - so a userspace program is going to give the kernel a program to run to analyze network traffic?!
   - which would run IN THE KERNEL?

But it is the best solution because passing data from the kernel to userspace is inherently expensive

So how can we send code to the kernel safely and securely?
 - use a language virtual machine!

so eBPF defines a bytecode virtual machine
 - good for packet filtering
 - but can be used to run almost arbitrary code in the kernel
    - for the purposes of monitoring kernel behavior
      and userspace behavior

eBPF code is limited
 - can only access memory in safe ways
 - no unbounded loops

Concurrency & deadlock

when we deal with concurrency, we have to deal with coordination between executing processes & threads (and other things)

key example here is producer/consumer, but there are MANY patterns

the dining philosopher's problem is an abstraction of the kind of systems that can have deadlock and other concurrency issues
 - involving shared resources

mmap is another way of interacting with files
 - access file contents as memory rather than with read/write
 - e.g.
    open->read/write->close vs.
    open->mmap->mess with memory->close

so with mmap, a range of memory is associated with a range of
bytes in a file
 - potentially at an offset, and a subset

So you can access a data structure directly rather than copying it to memory and then writing it to disk once you're done

mmap is really useful for interacting with large, sparse files
 - don't have to load all of it into memory
 - can access parts randomly without seeks

But mmap has other tricks
 - lets us bypass the copy memory functionality of fork,
   - share memory between processes

Randomness
 - how can a computer be random?


There are algorithms that can produce pseudo-random numbers
 - the numbers look random according to statistical tests
 - but, the algorithms always produce the same values
   given the same initial state (so they aren't random)
   (the seed)

cryptographically secure pseudo random number generator
 - no known way to efficiently predict the next number in the sequence

But we still need a good source of randomness
 - if anything, to seed a cryptographically secure pseudo random number generator

Ultimate source of randomness? the physical world. And the OS can interact with the physical world through devices
 - keyboard events
 - network packet arrival
 - hard drive settling time (for spinning disks)
 - special CPU instructions
   - which they tell us are random!

Feed these inputs into a cryptographically secure pseudo random number generator, and you get something you can rely on for almost any purpose