Hacking eBPF & LLVM for Fun and Profit

Introduction

Recently, we have been commissioned to complete several tasks related to developing eBPF-powered applications. As part of the development process, we encountered some limitations imposed by eBPF on developers, which led to the creation of this blog post.

eBPF is a widely used technology, used by many software companies on the market to deliver monitoring and security software. It allows one to trace, and sometimes modify, the Linux runtime behaviour. For example, one might monitor the creation of each process in the system, get notified about incoming network connections, and many more. This blogpost series will assume some basic familiarity with eBPF basic concepts - if you need a quick intro, you might want to check out ebpf.io.

While one can certainly write eBPF code manually (by using the macros that are defined in the bpf_insn header), this is most certainly not the common way to write modern maintainable eBPF code. One of the most used approaches is to write C/Rust code, and use clang - a compiler front-end that utilizes llvm behind the scenes, and using libbpf.

Anyone who has dabbled a bit in writing eBPF code has encountered the verifier - the kernel component that ensures that the bytecode we are trying to load into the kernel is valid and doesn’t compromise the eBPF program’s constraints. Upholding these constraints makes sure that no rouge eBPF program can crash the kernel, and contributes to the stability of the system. For example, at least as of today, no unbounded loops are allowed, one can’t use uninitialized registers and many more integrity checks.

Instruction count limit

One of the checks relates to the size of the loaded eBPF program - One can look at the source code to see there is a limit imposed on the number of instructions an eBPF program can have (note that there are different limits whether you are loading an unprivileged eBPF program or not, but the concept remains the same). Complex logic would often require larger eBPF programs, so bypassing this limit is of the essence in these cases.

In this blog series, we will attempt to hack our way in llvm code to use some features of eBPF programs in order to at least partially circumvent these constraints.

Anatomy of a simple eBPF program

For this blog post we will focus on eBPF programs that are written in C.

Let’s take a look at this short eBPF program:

#include <linux/bpf.h>
#include <bpf/bpf_helpers.h>

char LICENSE[] SEC("license") = "GPL";

struct sys_enter_execve {
    __u64 unused;
    __u32 nr;
    __u32 pad;
    const char *filename;
    const char *const *argv;
    const char *const *envp;
};

SEC("tracepoint/syscalls/sys_enter_execve")
int hello_world(struct sys_enter_execve *ctx) {
    __u32 pid = (__u32)(bpf_get_current_pid_tgid() >> 32);
    char comm[128];

    if (0 == bpf_get_current_comm(comm, sizeof(comm))) {
            /* We are reading the execed parameter from user space */
            char execed[128];
            if (0 < bpf_probe_read_user_str(execed, sizeof(execed), ctx->filename)) {
                bpf_printk("%s just execed, with pid %d the program %s\n", comm, pid, execed);
            }
    }

    return 0;
}

Besides the GPL license declaration (which is required to use some “GPL only” functions, as described in the licensing requirements), the program is quite simple.

You can compile the program to an object file using our supplied bash script.

The directive SEC("tracepoint/syscalls/sys_enter_execve") instructs the compiler to place our generated program in an elf section that is named, you guessed it, tracepoint/syscalls/sys_enter_execve .

libbpf boot-strapping code later examines the generated sections, and knows how to load each program and attach it to the correct location. The program hello_world will attempt to print out the command line and pid of each program, and the path to the exec-ed executable.

The loading script will load the program into the kernel and attach it to the relevant tracepoint (you can later remove it by running the detach script). To view the output from the tracing pipe, you can use this script.

Putting it all together, we get the following output:

From C code to eBPF bytecode

Now, let’s start to dissect a bit the compilation command that we used:clang -O2 -target bpf -c bpf.c -o bpf.o

Behind the scenes, clang performs several transformations on the code before emitting the final object file. We can do a rough distinction between two phases: IR generation, and native target machine code generation.

llvm can perform various optimizations that aren’t machine dependent - loop unrolling, dead code elimination, and many more - all these optimizations operate on llvm IR code. The specs for this intermediate representation language can be found in llvm’s website.

We can instruct clang to emit for us a file containing these intermediate representation instructions for inspection in assembly format.

Using the command clang -O2 -target bpf -emit-llvm -S -c bpf.c -o bpf.ll we get the file bpf.ll that should contain something like the following:

(rest of the image was truncated for the sake of brevity).

This llvm bitcode file can be transformed to our target eBPF bytecode, by using the following command:

llc -filetype=obj bpf.ll -o bpf.o

(llc is the llvm static compiler)

The resulting object file can be loaded just like before (you can try it!), and we can see our eBPF bytecode instructions inside it by using llvm-objdump -d:

LLVM Machine passes

The way that llvm operates behind the scenes when generating code is using the concept of a pass. In short, there are different types of passes (passes that operate on a whole module, passes that operate on a function, and so on) - and each pass can either do some useful transformation on the code, or perform some analysis to be used by other passes in the pipeline. Some examples would be dead code elimination, loop analysis, inlining and many more.

Note that there are passes that operate in the IR level, and there are passes that operate in the machine code level.

For our project, we would be interested in operating on the generated machine code - we would want to split large native eBPF functions based on their physical instruction count, not the size of their intermediate representation.

So, we would want to implement a pass that operates in the machine level. Unfortunately for us, this is a bit harder than creating an IR level pass. The reason being, is while there are options to load dynamic plugins with passes for opt (a tool that can allow us running various optimizations on .ll files), there is no such option for machine code level passes, as llc has no such plugin interface.

So - our workplan would be to implement our pass inside the source tree of llvm (specifically, llvm/lib/Target/BPF), and do all our modifications from within llc.More specifically - we’ll be implementing a MachineFunctionPass.

A toy MachineFunctionPass

To start us off - lets implement a very simple MachineFunctionPass which simply counts the number of instruction in a function.Our MachineFunctionPass will look something like this (the full code is in the patch file):

#include <llvm/CodeGen/MachineFunctionPass.h>
#include <llvm/CodeGen/MachineFunction.h>
...
class BPFMachineInstructionCountPass: public MachineFunctionPass {  
public:  
    BPFMachineInstructionCountPass(): MachineFunctionPass(ID) {}  
    static char ID;  
    bool runOnMachineFunction(MachineFunction& MF) override {  
        dbgs() << "The machine function " << MF.getName() << " has " << MF.getInstructionCount() << " instructions.\n";  
        // We didn't change any analysis.  
        return false;  
    }  
};

As you can see, this simply retrieves the MachineFunction name and instruction count and prints them to the error stream (dbgs()).

Integrating this into the llvm codebase is fairly straightforward:

1. Clone the llvm project
2. Checkout the tag llvmorg-16.0.6
3. Apply the provided patch on top of this tag
4. Follow the instructions in llvms website in order to generate the ninja files from cmake
5. run ninja llc in order to build llc (we don’t need the other components for now, since we will be dealing only with machine functions for now)

Voila! You should now have your own version of llc, that prints the number of physical instructions in each function. You can see this pretty easily from the source code:Using our custom generated llc, we now get the following output when we compile our bpf.ll file:

The intended solution - tail calls

Recalling our use case - we want to be able to automatically detect large eBPF functions and automatically split them to smaller ones.The plan is to glue these split functions together with the aid of bpf tail calls.

Tail calls allow one eBPF program to invoke another, and since each program gets its own quota of max number of instructions - we can use this mechanism to raise the limit of instructions.

Obviously, the reality of this is much more complex - we will progressively confront the various challenges in implementing this solution, tracking our progress in this series of blog posts.

Summary

In this blog post we demonstrated the initial step towards the intended solution, and laid out our plan. In the next blog post we will look at a case study in splitting a toy program, by implementing another toy MachineFunctionPass, and on the way explore the structure of an eBPF object with multiple programs, and the behaviour of tail calls in that context.