Luke Nelson
Ryan Benmalek
Lab X Writeup

December 14 2015

We decicded to implement an interpreter and JIT compiler for bpf in JOS to use
for filtering system calls similar to Linux's seccomp. We chose it because
creating JIT implementations is an interesting area of work because it
has the capability to eliminate costly upcalls, but needs to be secure enough
that user space programs cannot gain control of the kernel.

Creating an interpreter for bpf was fairly straightforward, but creating a
bpf to x86 compiler has many challenges. The largest challenge is one of
security. When interpreting bpf, we can check at every instruction that
a memory access is legal or division isn't by zero. When compiling to x86,
the kernel has no way to gain control back except by the compiled bpf program
returning. This means we have to statically verify that memory accesses are
legal and that every compiled program returns. Additionally, x86 instructions,
unlike bpf ones, do not have a fixed length. This means that jump offsets
are not known during the first pass over the bpf. To solve this, we padded all
x86 instructions to 10 bytes with nops. For bpf instructions that compile to
multiple x86 instructions, we packed the instructions inside the 10 bytes so
that there is a direct mapping from bpf jump offset to x86 jump offset. Doing
so restricts the maximum jump length because an instruction that makes a jump
decision off of an immediate must be compiled to a cmp instruction followed by
two jump instructions, which must be stored in a minimum of 10 bytes.
Alternatively, one could pad to more than 10 bytes and use 4-byte jump
offsets instead of 1-byte ones. We could also eliminate nop padding in a
second pass if the padding was determined to be a problem. Additionally,
the registers allocated to the bpf program must not overwrite registers needed
by gcc. To solve this we very carefully created a stub in x86 that handles the
exchange from gcc generated code to the JIT code, and vice versa.

One interesting thing we noticed is that compiling bpf to x86 did not seem to
have a significant performance impact on small programs. We think that that
is a combination of gcc's effectiveness at optimizing the interpreter
combined with the fact that the programs being tested were small.