eBPF string matching on steroids

String comparison is a fundamental programming paradigm, and various methods exist to compare the equality of two strings, such as memcmp, or comparing each character by hand if you want to go all in. This introduces a conditional branch for every character that we are trying to match.

For eBPF programs, in particular, this branching can result in our program being rejected by the verifier for long strings. We also need to keep the 1M instruction limit in check when comparing very long strings or checking strings inside a long running loop, hinting at the need for something more clever than comparison at a single-byte granularity.

Let’s first compare how existing string comparison methods hold up inside a long running bounded loop in an eBPF program, and dissect the generated bytecode for each method.

Naive char-by-char matching

This is a comparison at the most granular level; we compare each character from the two candidate strings one-by-one. This introduces a branch for every character, and for eBPF programs the verifier has to simulate every branch since buf is unknown during verification.

if (buf[0] == 'P' && buf[1] == 'O' &&
    buf[2] == 'S' && buf[3] == 'T') { ... }

Inspecting the generated bytecode using llvm-objdump reveals the guts of our branching; we have a memory load and then a conditional branch for each of our 4 characters, resulting in 8 instructions with 4 branches.

 6: r2 = *(u8 *)(r1 + 0x0)    ; load byte 0
 7: if r2 != 0x50 goto <FAIL> ; byte != 'P'
 8: r2 = *(u8 *)(r1 + 0x1)    ; load byte 1
 9: if r2 != 0x4f goto <FAIL> ; byte != 'O'
10: r2 = *(u8 *)(r1 + 0x2)    ; load byte 2
11: if r2 != 0x53 goto <FAIL> ; byte != 'S'
12: ...
13: r1 = *(u8 *)(r1 + 0x3)    ; load byte 3
14: if r1 == 0x54 goto <PASS> ; byte == 'T'

bpf_strncmp helper

The kernel provides the bpf_strncmp helper function, which is just a thin wrapper around the standard strncmp C library function. Digging into the kernel source tree reveals more details about this helper.

BPF_CALL_3(bpf_strncmp, const char *, s1, u32, s1_sz, const char *, s2)
{
    return strncmp(s1, s2, s1_sz);
}

static const struct bpf_func_proto bpf_strncmp_proto = {
	.func		= bpf_strncmp,
	.gpl_only	= false,
	.ret_type	= RET_INTEGER,
	.arg1_type	= ARG_PTR_TO_MEM | MEM_RDONLY,
	.arg2_type	= ARG_MEM_SIZE,
	.arg3_type	= ARG_PTR_TO_CONST_STR,
};

Notice the arg1_type field. It does not accept PTR_TO_PACKET as the first argument, rendering this helper function useless for string comparison on network data without explicitly copying the packet data to the stack.

In a nutshell, the bpf_strncmp cannot be used inside XDP, TC or SK_SKB programs where we need to perform comparisons directly on the packet data without performing a copy.

if (bpf_strncmp(buf, 4, "POST") == 0) { ... }

Anyway, let’s inspect the bytecode that it generates.

 6: r2 = 0x4                 ; arg2: size
 7: r3 = 0x0 ll              ; arg3: pointer to "POST"
 9: call 0xb6                ; call strncmp helper
10: r1 = r0                  ; copy ret val
11: ...
12: if r1 == 0x0 goto <PASS> ; check ret val

The generated bytecode reveals the overhead of a kernel helper call.

Using __builtin_memcmp

This is a Clang compiler builtin to compare two strings, and its semantics are similar to memcmp from the standard C library.

On older LLVM versions, using this helper left us at the mercy of LLVM to ensure it never generated an external call to memcmp, and instead it inlines this helper into byte-by-byte comparisons; failing to do so would otherwise result in the program being rejected by the verifier. The actual fix for this landed in LLVM 15, which expands memcmp calls into individual loads and comparisons when compiling for eBPF targets.

if (__builtin_memcmp(buf, "POST", 4) == 0) { ... }

This generates the following bytecode:

 6: r2 = *(u8 *)(r1 + 0x1)          ; load byte 1
 7: r2 <<= 0x8                      ; lshift by 8
 8: r3 = *(u8 *)(r1 + 0x0)          ; load byte 0
 9: r2 |= r3                        ; merge
10: r3 = *(u8 *)(r1 + 0x2)          ; load byte 2
11: r3 <<= 0x10                     ; lshift by 16
12: r1 = *(u8 *)(r1 + 0x3)          ; load byte 3
13: r1 <<= 0x18                     ; lshift by 24
14: r1 |= r3                        ; merge
15: r1 |= r2                        ; merge
16: if r1 != 0x54534f50 goto <FAIL> ; matches POST

At first glance the generated bytecode might look similar to our naive char-by-char matching, but something more interesting is happening here. LLVM expands the __builtin_memcmp into individual byte loads, followed by left shifts.

Essentially, LLVM generates bytecode to load 4 individual bytes and cleverly merge them into a single 32-bit value using bit-shifts. This results in a single branch where we compare the merged 4-byte value with our POST string literal (converted to 0x54534f50 by LLVM).

This LLVM optimization hints us toward a better approach to compare fixed size strings with minimal branching and fewer instructions.

Integer-based comparison

What if we load multi-byte data from the packet and compare it with compile-time strings cast as multi-byte integers?

// "POST" in little-endian
#define TAG_POST 0x54534f50

if (*(__u32 *)buf == TAG_POST) { ... }

Let’s analyze the bytecode generated:

6: r1 = *(u32 *)(r1 + 0x0)         ; load 4 bytes
7: ...
8: if r1 == 0x54534f50 goto <PASS> ; matches POST

Looks familiar? Yes, this is just a shrunk-down logic of our __builtin_memcmp approach. Instead of loading bytes at a single-byte granularity and stitching them into a 32-bit value using multiple shift instructions, we now just load 4 bytes from the packet in a single instruction.

The size of the value that we need to load depends on the tag that we are matching. For a 4-byte tag such as POST, we can perform a 32-bit load from the packet data in a single instruction. Similarly, for CAPYBARA, we can perform a single 64-bit load from the packet data or two individual 32-bit loads.

This is theoretically as few instructions as it can get: a single 32-bit load and a single branch comparing the loaded value with our compile-time tag constant.

Enough talking, let’s see the numbers.

Evaluation

I ran a benchmark for each of the methods discussed above inside a loop trying to find a 4-byte needle in a haystack, aiming to find the maximum iterations of the loop possible.

__builtin_memcmp is almost on par with our integer tag approach, but notice how it processed around 36% more instructions than our integer tag matching, which is expected, as we saw from the generated bytecode earlier.

What this means is that our integer tag approach is superior to __builtin_memcmp in scenarios where multiple large loops are present, which would cause us to hit the 1M instruction ceiling of eBPF programs because __builtin_memcmp generates more instructions.

These benchmarks were performed on kernel 6.8.0-139-generic (aarch64). You can find the source for these benchmarks at https://github.com/zignis/bpf-strcmp-bench.