appendix.tex

\appendix
\section{Appendix}
% \label{sec:impl}

\jinghao{\S\ref{sec:impl}: How to make it work}

% \subsection{Design goal}

%\begin{itemize}
%     \item Safety
%         \begin{itemize}
%             \item Same level of safety as eBPF
%             \item Memory safety
%             \item Control-flow soundness
%             \item Resource management
%             \item Program termination
%         \end{itemize}
%     \item Expressiveness
%         \begin{itemize}
%             \item Support more complicated/advanced programs
%             \item Longer programs
%             \item Unbounded loops
%         \end{itemize}
%     \item An important note: we want expressiveness w/o impairing safety (e.g.
%         allow unbounded loop while ensuring termination)
% \end{itemize}

% \subsection{Overview}
% \begin{itemize}
%     \item Brings out the Rust based approach (use Jiyuan's property-oriented
%         argument: We want these properties, and Rust happens to provide these)
%     \item Infrastructure (Need a figure similar to Fig. 5 from HotOS paper)
% \end{itemize}

We now discuss the high-level mechanisms that we use to build various features in
    \projname{} and make it a practical kernel extension framework.
These include the following:
\begin{itemize}
    \item How the \projname{} kernel crate bridges programs and the kernel.
    \item How \projname{} programs are loaded and attached.
    \item How eBPF maps are supported in \projname{}.
    \item How is the entry of \projname{} implemented that allows kernel to
        execute them directly.
\end{itemize}

\subsection{\projname{} kernel crate}
% \begin{itemize}
%     \item overall structure: program type, kernel binding generation, wrapper
%         interface around binding.
%     \item context conversion
%     \item kernel helper and symbol bindings (dynamic linking scheme)
%     \item kconfig-based conditional compilation
%     \item Map support
% \end{itemize}

The \projname{} kernel crate is responsible for supporting interactions between
    kernel and \projname{} programs and contains interfaces facing both sides.
% It contains support for different program types with
%     interfaces facing the kernel and the \projname{} program.
\projname{} support the same set of program types as eBPF.
Each program type is defined as a Rust struct and with allowed helpers defined
    as its methods.
This effectively implements access control on helper functions with respect to
    program types (e.g., a tracing program should not modify socket buffers
    through networking helper functions), which is also present in eBPF.
The user defines a program object of one of the program struct types and
    assoociates it with a Rust function as the extension program.
The extension function takes in the associated program object and the
    program-type-specific context from the kernel as arguments
    (\S\ref{impl:ctx-converison}).
Inside the extension, developers can use Rust kernel bindings generated by the
    crate to access kernel structures (\S\ref{impl:crate:binding}).
At the same time, helper functions allowed for the program type can be
    invoked through the program object, which are backed by eBPF kernel helpers.
    (\S\ref{impl:crate:symbol-resolv}).

% The crate also has support for maps (\S\ref{impl:map}) and other
%     miscellaneous utilities for the ease of programming (e.g. wrapping return
%     code in \texttt{Result} to support monadic operations in Rust).

\subsubsection{Supplying program context}
\label{impl:ctx-converison}
% Like eBPF, \projname{}
Extension programs take in a kernel-provided ``context'' as input argument.
The context is a pointer to a struct that contains information the program may
    need.
The current eBPF keeps a pair of context struct definitions for certain program
    types, where one of them is exposed to extension programs and the other one
    is the internal data structure in the kernel.
The extension-facing definition is generally a subset of the associated kernel
    internal definition.
This is done for the reason of keeping a stable interface and hidding unneeded
    kernel data from the extension programs.
When a eBPF program is loaded into the kernel, the verifier rewrites accesses
    into the corresponding field in the kernel context
    through the verifier hook specific to the program type.
Rewriting the access also avoids the need for copying data and contructing an
    extension-facing context.

% In \projname{}, the Rust compiler takes the place of the eBPF verifier and as
%     a result there is no way to rewrite the access to the context the same
%     way eBPF does.
In \projname{} the removal of the verifier means it cannot rewrite the access
    to the context the same way eBPF does.
Instead, \projname{} take the advantage of the expressive Rust language
    features.
In particular, \projname{} exports to the extension programs a struct that just
    wraps around the pointer to kernel context.
It implements accesses to the needed fields in the kernel context as safe Rust
    methods of this struct, which accesses the kernel struct internally via
    generated bindings (\S\ref{impl:crate:binding}).
% Doing so effectively re-route accesses to the kernel struct.
At the same time, it also allows controlled access to the kernel context and
    prevents unwanted writes to the context, which may corrupt kernel data
    accidentally.

\subsubsection{Creating Rust bindings of kernel structs}
\label{impl:crate:binding}
Extension programs rely heavily on the kernel data structure definitions.
A tracing program may want to obtain information from the kernel
    \texttt{task\_struct}, while a networking program needs to know the layout
    of protocol headers.
In eBPF, the need can be easily full-filled by including the corresponding
    kernel header files, as most of the time the program is implemented in C
    and compiled to eBPF bytecode.

The problem becomes more involved in \projname{}, as it uses Rust as the
    programming language, which cannot directly work with kernel C headers.
% As a solution, \projname{} creates Rust bindings for the needed kernel
%     definitions.
As a solution, \projname{} uses Rust-bindgen~\cite{bindgen} to create Rust
    bindings for kernel structure definitions and constants from kernel header
    files.
\projname{} integrates the binding generation into program compilation so that
    the bindings are automatically generated for the target kernel during
    build.
The generated Rust binding forms part of the kernel crate and can be imported
    into \projname{} programs like other contents of the kernel crate.

\subsubsection{Supporting kernel helper functions}
\label{impl:crate:symbol-resolv}
Kernel extensions utilizes kernel helper functions for perform more advanced
    operations.
eBPF uses kernel helpers as both a way to interact with the kernel and to
    complement its limitation on expressiveness.
\projname{}, on the other hand, only uses helpers for kernel interaction, since
    Rust is expressive enough that it does not need additional helper functions.

\projname{} uses the existing eBPF helper interface and implements on top of
    it a Rust wrapping layer.
This wrapping layer serves to hide the unsafe kernel C helper interface and
    provides a new interface that \projname{} programs can safely use.
The implementation of eBPF map lookup helper is shown in
    Figure~\ref{fig:map-helper}.
On L30, the kernel helper function returns a pointer to the map value
    (\texttt{*mut V}), the \projname{} wrapping layer converts the pointer
    into a Rust option type~\cite{rust-option} (\texttt{Option<\&mut V>}) on
    L33-L37, which allows \projname{} programs to access the object through a
    safe Rust reference without worrying about deferencing a null pointer.

\begin{figure}[t]
    \lstinputlisting[language=Rust]{./snippets/s5-map.rs}
    \vspace{-10pt}
    \caption{Implementation of eBPF map support in \projname{}}
    \vspace{-10pt}
    \label{fig:map-helper}
\end{figure}

In eBPF, most of the helper calls are direct function calls, however, a few of
    them are further optimized during verification and JITing.
Helper functions in \projname{} do not have the same load time optimization,
    and at the same time the kernel crate wraps the unsafe kernel helpers with
    a safe Rust interface, which could incur further overhead.
We further evaluate the impact in \S\ref{eval:inline}.

% For required kernel symbols (e.g., kernel helper functions), the kernel crate
%     creates a stub declaration for each symbol without using Rust-bindgen.
% This is because certain kernel symbols -- especially all eBPF helper
%     functions --  do not have a declaration in kernel header files.
% The actual definition of the kernel symbols will be resolved when the program
%     is loaded into the kernel (\S\ref{impl:crate:symbol-resolv}).

% The \projname{} kernel crate serves as an interface for the extension programs
%     to interact with the kernel.
% To accomplish this, the crate will need to access kernel symbols.
To reuse the existing kernel helper interface, the crate will need to access
    kernel symbols.
At the same time, the crate itself may also need to access certain kernel
    symbols for internal house keeping operations (e.g. resource cleanups as in
    \S\ref{principle:eh})
% For example, invoking kernel helper functions requires knowing the kernel
%     address of the target helper function symbol.
% These kernel symbols includes not only BPF helper functions, but also other
%     global and per-CPU variables.
Because \projname{} programs are compiled in userspace, the compiler does not
    have any knowledge on the required kernel symbols.
% One simple solution is to directly passing kernel symbols and their
%     corresponding addresses to userspace (e.g. through \texttt{/proc/kallsyms})
% However, this is in general considered a dangerous practice as it leaks kernel
%     addresses to userspace.
% At the same time, this solution is not robust against kernel layout changes
%     (e.g. due to kernel rebuild) -- changes of a kernel symbol address requires
%     a recompilation of the \projname{} program that uses it.

\projname{} therefore defers the kernel symbol resolution to program load time,
%     i.e., when the compiled \projname{} program is sent to the kernel.
    the same way dynamic linking works in userspace.
At this point, the booted kernel always knows where the symbols are located.
%     even after layout changes.
% At the same time, the sensitive kernel addresses do not need to be leaked to
%     userspace.
% \projname{} implements this kernel symbol resolution scheme the same way
%     dynamic linking works in userspace.
The \projname{} kernel crate merely creates stub declarations for the required
    kernel symbols.
During compilation, the compiler treats all kernel symbols as external and
    generate relocation entries for the undefined symbols.
At load time, the loader library (\S\ref{impl:load}) parses the executable,
    compiles a list of kernel sybmols that require resolution with their
    corresponding entries in the global offset table (GOT), and sends the
    information to the kernel.
The kernel then resolves the address for each symbol via the kallsyms subsystem
    and patches the GOT entries with the resolved addresses.
This allows programs to access kernel symbols without the need to disable
    kernel address space layout randomization (KASLR).
% and allows programs to correctly referencing these kernel symbols.

\subsubsection{Kconfig-aware conditional compilation}
% kernel uses config-based conditional compilation
% certain functionalities may not be compiled in
% we also use conditional compilation in kernel crate
% read config from build script and pass to the compilation process
The fact that the Linux kernel employs conditional compilation extensively
    based on kernel configuration values implies that certain functionalities
    used by \projname{} programs may not be compiled in.
An example of this is the ability to override the return value of a function in
    Kprobe programs.
This is only available if the \texttt{CONFIG\_BPF\_KPROBE\_OVERRIDE} is
    enabled, which is checked by the verfier in current eBPF.
The \projname{} kernel crate utilizes the conditional compilation counterpart
    in Rust.
The build script~\cite{rust-build-script} of the crate parses the configuration
    of the target kernel and send configuration values of interest to the
    compiler.
The compiler the conditionally compiles the code guarded by the configurations.
If a functionality does not have its associated configuration set, its support
    in the kernel crate will not be present, either.

\subsection{Program load and attachment}
\label{impl:load}
% \begin{itemize}
%     \item kernel loading code and attachment (w/ base program)
%     \item relocation fixups for maps and kernel symbols
%     \item libiu
% \end{itemize}
% Difference between eBPF and Rust programs
% - native code vs. byte code + JIT
% - no verifier to fixup relocations for maps and kernel symbols (e.g helpers)
% Implement kernel side loading logic
% - allocate page and map all LOAD segments in the ELF executable
% - fix all relocations for maps and kernel symbols
% - use the same eBPF insfrastructure
% problem where programs within the same executable share code
% - multiple programs calling the same function
% - one copy per program is ineffcient on memory
% - solution: first load the ELF executable, then associate individual programs
%   with extension entry functions in the code
There are two major differences between eBPF and \projname{} that poses unique
    challenges to the loading of \projname{} programs in the kernel.
Firstly, \projname{} is loaded as native code after compilation, of which the
    kernel does not have control on the layout.
This means the kernel need to parse and handle different sections in the
    program differently.
In contrast, eBPF is loaded as eBPF bytecode and contains only executable code.
The kernel has complete control over the generated native through the kernel
    eBPF JIT infrastructure.
Secondly, \projname{} does not have the in-kernel verifier, which is used in
    eBPF to fixup the kernel objects the program references (e.g., maps and
    helpers).
Therefore, the loading logic also needs to perform fixups needed for
    \projname{} on relocations.

The loading of a \projname{} program can be divided into two phases, with the
    first one happening in userspace and the other in kernel space.
The first phase is responsible for parsing the ELF executable into a format the
    kernel can understand as well as performing prerequisite operations (e.g.,
    creation of eBPF maps).
In \projname{} this is done by its userspace loader library \texttt{librex}.
Similar to how \texttt{libbpf} operates on eBPF programs, \texttt{librex}
    provides routines that parses the eBPF maps, kernel symbol relocations,
    and programs from the \projname{} ELF executable.
Once the sections are parsed, it creates the eBPF maps and update the
    corresponding map entries in the ELF (\S\ref{impl:map}), and then load
    the program by sending the ELF binary as well as the map and relocation
    information.
Parsing the ELF sections in usrspace avoids complexity of the loading logic in
    the kernel.

For the second phase, we extend the \texttt{bpf} system call to support loading
    of \projname{} programs.
The system call sends the compiled ELF executable as well as the associated
    relocation information into the kernel.
The kernel first parses the ELF executable and locate all the \texttt{LOAD}
    segments in the executable.
It then allocate new pages and maps the \texttt{LOAD} segments into the
    kernel address space based on the size and permissions of the segments.
With the associated relocation information, the kernel updates the kernel
    symbol relocation entries (\S\ref{impl:crate:symbol-resolv}) and eBPF maps
    (\S\ref{impl:map}) with the corresponding absolute address in the kernel.
% The relocations that need fixup are kernel symbols referenced by the
%     \projname{} program (\S\ref{impl:crate:symbol-resolv}) and eBPF maps
%     (\S\ref{impl:map}).
At this point, the program is considered ``loaded''.
The kernel then wrap the program into a \texttt{bpf\_prog} struct as if it is a
    JIT-ed program -- reusing the existing eBPF infrastructure for program
    management greatly reduces engineering efforts and facilitates easy
    integration with existing eBPF hook points.

Kernel extensions often involves use cases where multiple programs are defined
    together and share common code in the same executable.
% One of the problem \projname{} faces is to deal with multiple programs within
%     the same ELF executable.
% Such programs may share common code in the same executable.
eBPF loads each of the program independently and deplicates the shared code. \jinghao{need check}
% It is obviously not memory efficient if the load of each program requires
%     loading and mapping of the same executable.
This is obviously not memory efficient for \projname{} because duplicating
    shared code means duplicating the \projname{} kernel crate.
The soluation \projname{} uses is that it separates the steps of mapping the
    executable into kernel memory and loading of programs.
The userspace first invokes our extended \texttt{bpf} system call to map the
    whole executable into kernel address space and obtain a reference count to
    the mapped code (behind a file descriptor).
It then can invoke the syscall again to load the program into the kernel.
This later step is simple as it only needs to wrap the function associated with
    the \projname{} program into the \texttt{bpf\_prog} struct.
The newly created \texttt{bpf\_prog} struct takes the reference count of the
    mapped executable code so that the kernel will not clean it up before the
    programs are destroyed.
This allows multiple programs to effectively share the same executable code and
    avoid waste of memeory resources.

\subsection{Supporting eBPF maps}
\label{impl:map}
% maps are important: storage and data sharing
% supporting map is hard:
%   2 step of rewriting for the sake of easy programming and hide kernel
%     pointer
%   Not directly available in Rust
%   need to make map interface safe
%   also need seamless support as eBPF does
%
% Use a loader library:
%   define a ABI of Rust map object in memory (metadata + actual kptr) put in
%     .map section
%   loader library parse elf object and find all maps
%   use the defined ABI to read out metadata and create map via bpf syscall
%   rewrite kptr in each map in the elf object with map fd (safe because
%     kptr is 8 byte and can be treated as an int and map fd is 4 byte)
%   when loading the program, send in the updated elf object and offset of each
%     map kptr within the object
%   kernel will use the previously written fd in the kptr to retrieve the real
%     address of the map and update kptr value.
%   kptr is initialized to null, since compiler does not see the post
%     compilation fixups, it will assume the value never changes and
%     constant-propogate the map kptr, leading to incorrect program behavior
%   e.g. the map helpers always verifies the kptr is not null before invoking
%     actual kernel helper, assuming the kptr to be always null makes the map
%     helper always return error without calling into the kernel
%   solution: treat the kptr as a volatile variable and force a load before
%     each map call
%
The kernel eBPF maps provide a powerful primitive for extension programs to
    store data across program execution and to easily share data with userspace.
Therefore, such a functionality is highly desired in \projname{}.

Current eBPF allows user to define a eBPF map in the program by defining a
    struct instance that contains the map metadata (e.g. key/value type, number
    of entries) in a specific ELF section for maps.
All map operations on this map would be made through this instance.
At program load time, \texttt{libbpf}, the eBPF loader library, parses the map
    metadata from the struct instance.
It then creates the map in the kernel through the \texttt{bpf} system call and
    obtain a file descriptor referring to the map.
\texttt{libbpf} rewrites the eBPF bytecode such that all references to the
    created map are updated to the value of the file descriptor.
When the program is loaded to the kernel, the eBPF verifier performs a second
    round of rewriting -- for each map file descriptor, it obtains the actual
    kernel eBPF map struct the file descriptor refers to and updates the
    references to the address of the kernel internal map struct.
This two-stage rewriting provides two desired properties: it 1) prevents
    leaking of a kernel map address to userspace and 2) allows seamless and
    transparent interaction with the kernel maps from extension programs.
However, supporting eBPF maps in the ways of eBPF is not trivial in
    \projname{}, because the ABI of map metadata struct is eBPF-specific and
    the absence of in-kernel verifier.
% However, for \projname{}, achieving these two properties is not trivial: the
%     Rust compiler cannot provide these since creating maps is out-of-scope for
%     compilation, and at the same time the existing two-stage rewriting is specifically
%     for eBPF and cannot be reused for Rust programs directly.

In order to support a safe and convenient map interface, \projname{} defines
    its own ABI for storing map metadata and implements the rewriting logic in
    its own program loader library and kernel program loading code.
In \projname{} programs, users can define a map by creating a new, static
    \texttt{RexMap} object in the \texttt{.map} section through a convenience
    macro provided by the \projname{} kernel crate.
Part of the implementation of \texttt{RexMap} is shown in
    Figure~\ref{fig:map-helper}.
\texttt{RexMap} is exported by the \projname{} kernel crate, which contains
    various map parameters, and a private pointer to the kernel map struct.
The struct uses generic types to encode the map type, key type, and
    value types.
All map helpers in \projname{} are also generic functions with the same set of
    generic parameters, which take \texttt{RexMap} objects as arguments and
    internally invoke the kernel map helper functions with the kernel map
    pointer.
Doing so ensures safety of map operations -- it prevents mismatches in map
    types and key/value types (\S\ref{principle:memsafety}).
The creation of \texttt{RexMap} is set to be constantly evaluated; in other
    words, this means its fields are initialized at compile time and readily
    available in the executable data.
This is the same as how eBPF initilizes ``legacy'' maps (newer maps are
    initialized via BTF debug information).

The ABI is implemented by forcing the \texttt{RexMap} struct to have
    C-representation~\cite{nomicon-reprc}, i.e., the memory layout
    is the same as a equivalent C structand thereby enforce a stable layout.
Doing so allows \texttt{librex}, the \projname{} loader library to easily parse
    a \texttt{RexMap} struct to obtain the map metadata.
Similar to \texttt{libbpf}, \texttt{librex} finds and parses all maps in the
    \texttt{.map} section.
% This is possible because the constructor of \texttt{RexMap} is defined as
%     a constant expression and therefore the \texttt{RexMap} objects are
%     initialized at compile time.
With the metadata for each map, the library creates the requested eBPF maps in
    the kernel using the \texttt{bpf} system call and rewrites the kernel
    pointer field of each \texttt{RexMap} object to the file descriptor value.
When loading the program, the loader library sends both the updated ELF
    executable and a list of offsets of the kernel map pointer field within the
    executable to the kernel.
The kernel reads the file descriptor at each offset and update it with the real
    map address referred by the file descriptor to make all map operations
    work.

During compile-time initialization, the kernel pointer field in
    \texttt{RexMap} is set to a null pointer.
Since the \texttt{RexMap} objects are defined as read-only and rewriting
    happens after compilation, this makes the Rust compiler incorrectly assume
    the kernel map pointer always stays \texttt{NULL}.
This in turn causes the compiler to perform constant propagation on the kernel
    pointer field when optimizations are enabled, leading to incorrect program
    behavior.
For example, the \projname{} map helpers in the \projname{} kernel crate always
    verifies that the kernel pointer is not null before invoking the kernel map
    helper functions.
By constant-propagating the \texttt{NULL} pointer value, the compiler believes
    the check always fails and makes the map helper always to return error
    without calling into the kernel helper function.
In order to solve this problem, the \projname{} kernel crate treats the kernel
    pointer as volatile and forces a load of the pointer value from memory
    every time it is used by the map helpers.
\jinghao{Feels this paragraph does not add much, shall we remove it}

\subsection{Safe guarding program entry}
% \begin{itemize}
%     \item LLVM pass
% \end{itemize}
To allow \projname{} extension code in Rust to be called from the kernel C
    code, an FFI entry-point function is needed to wrap around the user-defined
    extension function.
This wrapper function needs to handle certain unsafe operations, including
    interpreting the context argument supplied by the kernel as a Rust
    reference and performing context conversion for selected program types.
Because of this, this entry function should not be implemented by the user.
For example, interpreting an XDP context as a kernel perf-event context and
    perform the context conversion specific to perf-event would violate memory
    and type safety and result in undefined behavior.
Therefore, \projname{} chooses to automatically generate the entry point code
    during compilation of the Rust extension programs.

We implement the generation of entry code as an compiler pass, taking the
    advantage of Rust's use of LLVM as its code generation backend.
At the LLVM-IR stage, the entry code generation pass reads out the information
    related to the program from the program object the user defines.
This is achieved by implementing a similar ABI to \texttt{RexMap}s
    (\S\ref{impl:map}) on program objects, which creates a fixed memory layout
    of the program object
% This is achieved by enforcing a specific memory layout of the program object
%     struct (e.g., always store the program type in the first integer field) and
%     then constant-initializing the program object, which effectively implements
%     an ABI between the Rust compiler front end and the LLVM middle/back end.
The pass generates a new entry function for the program.
%     with the
%     user-supplied program name.
The function has the same prototype as the in-kernel hook point, and therefore,
    the kernel can directly invoke the function from the place the program is
    attached.
Inside the entry function, depending on the type of the program, the pass
    generates code that invokes the program-type-specific code from the
    \projname{} kernel crate that dispatches the program.
The code reinterprets the context argument supplied by the kernel into a Rust
    object, performs context conversion if needed
    (\S\ref{impl:ctx-converison}), and eventually call into the
    user-defined extension function that is associated with the \projname{}
    program object.

% \subsection{Handle exceptional control flow}
% \begin{itemize}
%     \item kernel trampoline
% \end{itemize}

% \subsection{Stack overflow protection}
% \begin{itemize}
%     \item kernel vmapped, dedicated stack
%     \item LLVM instrumentation
% \end{itemize}