ProHoster > Blog > Administration > A Brief Introduction to BPF and eBPF

A Brief Introduction to BPF and eBPF

Hello, Habr! We are pleased to announce that our book "Linux Observability with BPF".

A Brief Introduction to BPF and eBPF
As the BPF virtual machine continues to evolve and is actively applied in practice, we have translated an article for you that describes its main features and current state.

In recent years, programming tools and techniques aimed at overcoming the limitations of the Linux kernel have gained popularity, especially when high-performance packet processing is required. One of the most popular techniques of this kind is called kernel bypass (kernel bypass), which allows all packet processing to be performed from user space, bypassing the network layer of the kernel. Kernel bypass also involves managing the network card from user space. In other words, when working with the network card, we rely on the driver. user space.

By giving full control of the network card to a user-space program, we reduce the overhead associated with kernel operations (context switching, network level processing, interrupts, etc.), which is quite important when operating at speeds of 10Gb/s or higher. Kernel bypass combined with other capabilities (batch processing) and careful performance tuning (NUMA awareness, CPU isolation, etc.) corresponds to the foundations of high-performance network processing in user space. A prime example of this new approach to packet processing is the DPDK from Intel (Data Plane Development Kit), although there are other well-known tools and techniques, including Cisco's VPP (Vector Packet Processing), Netmap, and of course, Snabb.

There are several drawbacks to organizing network interactions in user space:

  • The OS kernel is an abstraction layer for hardware resources. Since user space programs have to manage their resources directly, they also have to handle their own hardware. Often, this means the need to program their own drivers.
  • Since we completely abandon kernel space, we also forgo all the networking functionality provided by the kernel. User-space programs have to re-implement the functions that may already be provided by the kernel or the operating system.
  • Programs operate in a sandbox mode, which significantly restricts their ability to interact and hinders their integration with other parts of the operating system.

Essentially, in organizing network interactions in user space, performance is enhanced by moving packet processing out of the kernel and into user space. XDP does the opposite: it moves network programs (filters, transformers, routing, etc.) into the kernel space. XDP allows us to perform networking functions as soon as a packet hits the network interface and before it starts moving up into the kernel's network subsystem. As a result, packet processing speed increases significantly. However, how does the kernel allow the user to run their programs in kernel space? Before answering this question, let's look at what BPF is.

BPF and eBPF

Despite its somewhat obscure name, BPF (Berkeley Packet Filtering) is essentially a virtual machine model. This virtual machine was originally designed for packet filtering, hence the name.

One of the most well-known tools that use BPF is tcpdump. When capturing packets using tcpdump , the user can specify an expression for filtering packets. Only packets matching this expression will be captured. For example, the expression "tcp dst port 80" pertains to all TCP packets arriving at port 80. The compiler can optimize this expression by transforming it into BPF bytecode.

$ sudo tcpdump -d "tcp dst port 80"
(000) ldh [12]
(001) jeq #0x86dd jt 2 jf 6
(002) ldb [20]
(003) jeq #0x6 jt 4 jf 15
(004) ldh [56]
(005) jeq #0x50 jt 14 jf 15
(006) jeq #0x800 jt 7 jf 15
(007) ldb [23]
(008) jeq #0x6 jt 9 jf 15
(009) ldh [20]
(010) jset #0x1fff jt 15 jf 11
(011) ldxb 4*([14]&0xf)
(012) ldh [x + 16]
(013) jeq #0x50 jt 14 jf 15
(014) ret #262144
(015) ret #0

This is essentially what the program above does:

  • Instruction (000): loads the packet at offset 12, as a 16-bit word into the accumulator. Offset 12 corresponds to the ethertype of the packet.
  • Instruction (001): compares the value in the accumulator with 0x86dd, that is, with the ethertype value for IPv6. If the result is true, the program counter moves to instruction (002), otherwise it goes to (006).
  • Instruction (006): compares the value with 0x800 (ethertype value for IPv4). If the answer is true, the program moves to (007); if not, it goes to (015).

And so on, until the packet filtering program returns a result. Usually, this is a boolean. Returning a non-zero value (instruction (014)) means that the packet matched, while returning zero (instruction (015)) means that the packet did not match.

The BPF virtual machine and its bytecode were introduced by Steve McCanne and Van Jacobson in late 1992, when their paper was published. BSD Packet Filter: A New Architecture for User-Level Packet Capture, this technology was first presented at the Usenix conference in the winter of 1993.

Since BPF is a virtual machine, it defines the environment in which programs run. In addition to bytecode, it also defines a packet memory model (load instructions implicitly apply to the packet), registers (A and X; the accumulator and index registers), scratch memory storage, and an implicit program counter. Interestingly, the BPF bytecode was modeled after the Motorola 6502 ISA. As Steve McCanne recalled in his plenary session at Sharkfest '11, he had been familiar with the 6502 assembly since high school when he programmed on the Apple II, and this knowledge influenced his work on designing the BPF bytecode.

BPF support was implemented in the Linux kernel in version v2.5 and later, primarily through the efforts of Jay Shullist. The BPF code remained unchanged until 2011, when Eric Dumazet redesigned the BPF interpreter to work in JIT mode (Source: JIT for packet filters). After this, the kernel could directly convert BPF programs into target architecture code instead of interpreting the BPF bytecode: x86, ARM, MIPS, etc.

Later, in 2014, Alexey Starovoitov proposed a new JIT mechanism for BPF. In fact, this new JIT became a new architecture based on BPF and was named eBPF. I believe that for some time both virtual machines coexisted, but currently, packet filtering is implemented based on eBPF. In fact, in many modern documentation samples, BPF refers to eBPF, while the classic BPF is now known as cBPF.

eBPF extends the classic BPF virtual machine in several ways:

  • Based on modern 64-bit architectures. eBPF uses 64-bit registers and increases the available registers from 2 (accumulator and X) to 10. It also provides additional operation codes (BPF_MOV, BPF_JNE, BPF_CALL...).
  • Detached from the network layer subsystem. BPF was tied to the packet data model. Since it was used for packet filtering, its code resided in the subsystem that ensured network interactions. However, the eBPF virtual machine is no longer bound to a data model and can be used for any purposes. Now, an eBPF program can be attached to a tracepoint or kprobe. This opens the door to eBPF instrumentation, performance analysis, and many other use cases in the context of other kernel subsystems. The eBPF code now follows its own path: kernel/bpf.
  • Global data storage called Maps. Maps are key-value stores that provide data exchange between user space and kernel space. eBPF provides maps of several types.
  • Helper functions. In particular, for rewriting a packet, calculating a checksum, or cloning a packet. These functions are executed within the kernel and do not belong to user-space programs. Additionally, system calls can be made from eBPF programs.
  • Tail calls. The size of a program in eBPF is limited to 4096 bytes. The tail call feature allows an eBPF program to transfer control to a new eBPF program and thus bypass this limitation (allowing up to 32 programs to be linked).

eBPF: example

The Linux kernel sources contain several examples for eBPF. They are available at samples/bpf/. To compile these examples, simply enter:

$ sudo make samples/bpf/

I won't write a new example for eBPF myself, but will use one of the samples available in samples/bpf/. I will look at some sections of the code and explain how it works. For this example, I have chosen the program tracex4.

In general, each of the examples in samples/bpf/ consists of two files. In this case:

  • tracex4_kern.c, contains the source code that should run in the kernel as eBPF bytecode.
  • tracex4_user.c, contains the user-space program.

In this case, we need to compile tracex4_kern.c to bytecode eBPF. Currently, there gcc is no server-side component for eBPF. Fortunately, clang can output eBPF bytecode. Makefile use clang for compilation tracex4_kern.c into an object file.

I mentioned earlier that one of the most interesting features of eBPF is maps. tracex4_kern defines a map:

struct pair {
    u64 val;
    u64 ip;
};  

struct bpf_map_def SEC("maps") my_map = {
    .type = BPF_MAP_TYPE_HASH,
    .key_size = sizeof(long),
    .value_size = sizeof(struct pair),
    .max_entries = 1000000,
};

BPF_MAP_TYPE_HASH is one of the many types of maps offered by eBPF. In this case, it is simply a hash. You may also have noticed the declaration SEC("maps"). SEC is a macro used to create a new section in the binary file. Essentially, in the example, tracex4_kern defines two more sections:

SEC("kprobe/kmem_cache_free")
int bpf_prog1(struct pt_regs *ctx)
{   
    long ptr = PT_REGS_PARM2(ctx);

    bpf_map_delete_elem(&my_map, &ptr); 
    return 0;
}
    
SEC("kretprobe/kmem_cache_alloc_node") 
int bpf_prog2(struct pt_regs *ctx)
{
    long ptr = PT_REGS_RC(ctx);
    long ip = 0;

    // get the IP address of the caller kmem_cache_alloc_node() 
    BPF_KRETPROBE_READ_RET_IP(ip, ctx);

    struct pair v = {
        .val = bpf_ktime_get_ns(),
        .ip = ip,
    };
    
    bpf_map_update_elem(&my_map, &ptr, &v, BPF_ANY);
    return 0;
}

These two functions allow you to remove an entry from the map (kprobe/kmem_cache_free) and add a new entry to the map (kretprobe/kmem_cache_alloc_node). All function names written in uppercase correspond to macros defined in bpf_helpers.h.

If I dump the sections of the object file, I should see that these new sections are already defined:

$ objdump -h tracex4_kern.o

tracex4_kern.o: file format elf64-little

Sections:
Idx Name Size VMA LMA File off Algn
0 .text 00000000 0000000000000000 0000000000000000 00000040 2**2
CONTENTS, ALLOC, LOAD, READONLY, CODE
1 kprobe/kmem_cache_free 00000048 0000000000000000 0000000000000000 00000040 2**3
CONTENTS, ALLOC, LOAD, RELOC, READONLY, CODE
2 kretprobe/kmem_cache_alloc_node 000000c0 0000000000000000 0000000000000000 00000088 2**3
CONTENTS, ALLOC, LOAD, RELOC, READONLY, CODE
3 maps 0000001c 0000000000000000 0000000000000000 00000148 2**2
CONTENTS, ALLOC, LOAD, DATA
4 license 00000004 0000000000000000 0000000000000000 00000164 2**0
CONTENTS, ALLOC, LOAD, DATA
5 version 00000004 0000000000000000 0000000000000000 00000168 2**2
CONTENTS, ALLOC, LOAD, DATA
6 .eh_frame 00000050 0000000000000000 0000000000000000 00000170 2**3
CONTENTS, ALLOC, LOAD, RELOC, READONLY, DATA

There is also tracex4_user.c, the main program. Essentially, this program listens for events kmem_cache_alloc_node. When such an event occurs, the corresponding eBPF code is executed. The code saves the object's IP attribute into the map, and then this object is cyclically output in the main program. For example:

$ sudo ./tracex4
obj 0xffff8d6430f60a00 is 2sec old was allocated at ip ffffffff9891ad90
obj 0xffff8d6062ca5e00 is 23sec old was allocated at ip ffffffff98090e8f
obj 0xffff8d5f80161780 is 6sec old was allocated at ip ffffffff98090e8f

How are the user-space program and the eBPF program related? During initialization, tracex4_user.c loads the object file tracex4_kern.o using the function load_bpf_file.

int main(int ac, char **argv)
{
    struct rlimit r = {RLIM_INFINITY, RLIM_INFINITY};
    char filename[256];
    int i;

    snprintf(filename, sizeof(filename), "%s_kern.o", argv[0]);

    if (setrlimit(RLIMIT_MEMLOCK, &r)) {
        perror("setrlimit(RLIMIT_MEMLOCK, RLIM_INFINITY)");
        return 1;
    }

    if (load_bpf_file(filename)) {
        printf("%s", bpf_log_buf);
        return 1;
    }

    for (i = 0; ; i++) {
        print_old_objects(map_fd[1]);
        sleep(1);
    }

    return 0;
}

During execution load_bpf_file the probes defined in the eBPF file are added to /sys/kernel/debug/tracing/kprobe_events. Now we are listening to these events, and our program can perform actions when they occur.

$ sudo cat /sys/kernel/debug/tracing/kprobe_events
p:kprobes/kmem_cache_free kmem_cache_free
r:kprobes/kmem_cache_alloc_node kmem_cache_alloc_node

All other programs in sample/bpf/ are structured similarly. They always consist of two files:

  • XXX_kern.c: eBPF program.
  • XXX_user.c: main program.

The eBPF program defines maps and functions bound to the section. When the kernel issues an event of a certain type (for example, tracepoint), the bound functions are executed. Maps facilitate data exchange between the kernel program and the user-space program.

Conclusion

This article has briefly covered BPF and eBPF. I know there is a lot of information and resources about eBPF today, so I will recommend a few more materials for further study.

I recommend reading:

Source: habr.com

Buy reliable website hosting with DDoS protection, VPS VDS servers 🔥 Buy reliable website hosting with DDoS protection, VPS VDS servers | ProHoster