Merlin: Multi-tier Optimization of eBPF Code for Performance and Compactness

Linux lets you load your own code into the kernel provided a verifier can prove it safe, which makes every instruction expensive twice over — it runs on a hot path and it must be checked before it runs at all — yet the compiler producing that code knows nothing about the sandbox's peculiar rules and leaves a great deal of redundancy behind; this paper (UMass Amherst) adds eBPF-aware passes at two levels and removes 73 percent of the instructions, where the previous best approach searched for equivalent programs and took two days on a program this one handles in a thirtieth of a second.

The argument in one glance

Problem

Code in the kernel is expensive twice

A mechanism in Linux lets an ordinary program load its own code into the running kernel and attach it to the busiest paths there — every arriving packet, every system call. That is why modern observability, networking, and security tools are built on it. Two costs follow. The code runs on a path where nothing is cheap, so waste shows up directly in system throughput. And before it runs at all, a verifier must statically prove it safe, which it will refuse to attempt if the program is too large.
What people did

Compile it with the general-purpose toolchain

These programs are written in C and compiled by the standard compiler infrastructure, which has a backend for the sandbox's instruction set. That backend applies the usual optimisations — constant folding, dead code removal, register allocation — and produces bytecode the verifier will generally accept.
Why it fell short

The compiler does not know the sandbox's rules

The sandbox has requirements a general compiler has no model of. Values must be aligned in particular ways, arithmetic on narrow types must clear the upper bits of a wider register, and the machine has only ten registers. Meeting these conservatively produces sequences that are correct and much longer than needed — a single sixteen-bit load can become four instructions. Worse, two programs that compute exactly the same thing can differ in whether the verifier accepts them at all.
This paper's idea

Write the passes the sandbox needs, at both levels

This paper (Jinsong Mao, Hailun Ding, Juan Zhai and Shiqing Ma) reads the sandbox's own design documentation for the constraints that create the redundancy, then implements six optimisations — some as passes over the compiler's intermediate form, some as rewrites of the finished bytecode where the intermediate form cannot express the change. Everything happens before the verifier, which is left untouched.

Why this problem is worth solving

The environment imposes a constraint that ordinary compilation never faces.

EBPF is a small virtual machine inside the Linux kernel — register-based, with ten 64-bit registers and its own instruction set — that lets unprivileged code be attached to kernel events and run there. Since a bug in kernel code takes down the machine, nothing is loaded until a VERIFIER has statically proved it safe: that it terminates, that its loops are bounded, that every memory access is in range. The verifier does this by walking every distinct path through the program and tracking what it knows about each register at each point, so its work grows with paths rather than with instructions, and it gives up past a limit — a million processed instructions on current kernels. This makes program size a correctness property rather than a performance one. A program that is a little too long does not run slowly; it is refused. And the number of paths is typically far larger than the number of instructions, so removing one instruction can remove a great deal of verification.

Compactness and speed are the same objective here, which is unusual.

The second thing to understand is why a good compiler still leaves work behind.

THE sandbox has rules that exist for its own safety and are invisible in the source language. Data must be aligned, and if the compiler cannot prove a pointer is aligned it assumes the worst, so a sixteen-bit load becomes a sequence that assembles the value from bytes. There are only 64-bit registers, so operating on a narrower type requires masking away the bits that are not part of it, and the general way of doing that is verbose. These are not compiler bugs; they are a general backend behaving conservatively about a target whose peculiarities it has no model of. There is also a sharper problem underneath. Because the verifier accepts or rejects based on what it can prove rather than on what is true, two programs that compute identical results can differ in whether they load — the paper opens with such a pair. So an optimisation here must be judged not only by whether it preserves semantics but by whether it preserves verifiability.

That is the constraint that makes this a research problem rather than a patch.

What people did before, and where it broke

Rely on the standard compiler backend. Write the program in C, compile with optimisation enabled, load the result. This is what essentially everyone does.
The gap. The backend is conservative about the sandbox’s constraints because it has no model of them. Measured here, three quarters of the instructions in real programs turn out to be removable, most of them from a single conservative assumption about alignment.
Optimise by searching for an equivalent program. The prior state of the art formalises the instruction set, uses stochastic search to propose semantically equivalent programs, and checks candidates against hand-written safety models.
The gap. Cost and coverage. Optimising one 1,771-instruction program took two days, with time growing exponentially in program size, and the safety models are manual work that must be maintained as the sandbox evolves.
The same approach, applied more broadly. In principle a search-based optimiser could cover every kind of program that uses this mechanism.
The gap. It does not, because the helper functions the kernel exposes were never all formalised. In practice the prior system handles only packet-processing programs, which leaves the observability and security tools — the bulk of real deployments — untouched.
Hand-optimise the source. Developers do tune these programs, since they know the constraints the compiler does not.
The gap. It requires deep kernel expertise, it has to be redone as programs change, and the redundancy being removed is introduced during code generation, below the level the developer is writing at.

How the redundancy gets removed

From C source to smaller bytecode, without touching the kernel

↓ →
new
↓ →
new
↓ →
new
↓ →
new
↓ →
new

The two tiers exist because the two kinds of redundancy live at different levels: one comes from information the intermediate form is missing, the other from how that form is lowered.

The idea

Read the specification for the constraints, then encode them as passes. The method is less glamorous than the alternative and that is the point. Rather than searching for a better program, the authors went to the sandbox’s design documentation, extracted the rules that constrain how data may be manipulated, and asked which of them cause a general compiler to emit more instructions than necessary. That yields six optimisations in two families — merging instructions that can be combined, and replacing expensive operations with cheaper equivalents. None is novel as a compiler technique; constant propagation, dead code elimination, superword merging, macro-op fusion, code compaction and peephole rewriting are all textbook. What is new is knowing where they apply in this target, which is precisely the knowledge a general backend lacks. Turning a search into a directed construction by exploiting domain structure is the same move as the accelerator design-space work covered elsewhere on this site, and it produces the same shape of result — minutes or seconds where the search took hours or days.

One conservative assumption accounts for most of the waste. The optimisations are not equal, and the breakdown is instructive. Alignment alone provides 17.85 percent of the instruction reduction, against 1.59, 1.44, 0.61, 0.17 and 0.13 percent for the other five. The reason is that the compiler, unable to prove what alignment a pointer has, assumes the worst and emits code that assembles a value byte by byte. A pass that computes the actual offsets of every pointer and infers the strongest alignment that is genuinely safe collapses those sequences into single loads. Memory access is the most common thing these programs do, so the saving is everywhere. It is worth noticing what this implies about the others — five of the six optimisations together contribute under four percent, so this is one large win with a supporting cast rather than six comparable ideas. That these programs are overwhelmingly made of field reads is also the structural fact exploited by the work on compiling the same packet programs into hardware covered elsewhere on this site, which arrives at it from the opposite direction.

Optimising for the verifier is a distinct goal that happens to align. The unusual feature of this target is that the code is analysed before it runs, by something that gives up if the analysis is too large. Every removed instruction removes register states the verifier must track along every path that reaches it, and since the verifier explores paths rather than instructions, the effect is amplified — the paper measures up to 89.6 percent fewer processed instructions and up to 85.2 percent less verification time, averaging 17.1 and 25.4 percent. That matters beyond speed, because a program that exceeds the verifier’s budget cannot be loaded, so this is the difference between a tool working and not existing. Careful attention to what the kernel will actually permit, rather than to what would be fastest in principle, is the same discipline as the machine-learning-in-the-kernel work covered elsewhere on this site, which spends most of its effort on what the environment allows.

Four instructions that should have been one

How a conservative alignment assumption becomes a fourfold expansion

Following a two-byte load from source through code generation and back to a single instruction.

Step 1 of 5

The source loads a sixteen-bit value

A program reads a two-byte field from a packet or a kernel structure through a pointer. In C this is unremarkable and in the intermediate form it is a single load.

This is the single most common shape of operation in these programs. They exist to inspect data at kernel hot paths, so most of what they do is read fields out of structures somebody else laid out.

Why it works

The compiler was being conservative, not wrong. Recovering the true alignment of each pointer by analysis → the backend can emit a wide load instead of a byte-assembly sequence → four instructions collapse to one wherever a field is read, which is most of what these programs do.
Size is a correctness property here, not just a cost. Removing instructions → the program falls further below the verifier’s budget → programs that would have been refused can now be loaded, which is a different kind of benefit from running faster.
The verifier explores paths, so savings amplify. Each removed instruction removes register states along every path reaching it → verification cost falls faster than instruction count → up to 89.6 percent fewer processed instructions and 85.2 percent less verification time.
Two tiers because redundancy lives at two levels. Passes over the intermediate form fix what is missing information, and bytecode rewrites fix what code generation introduces → patterns that cannot be expressed at one level are still reachable at the other → masking sequences for narrow types are removed even though the intermediate form has no way to say so.
A directed construction scales where a search does not. Applying known transformations at known opportunities → cost is roughly linear in program size instead of exponential → about a thirtieth of a second per program against two days, and coverage of every program type rather than only packet processing.

The evaluation

Property	What was measured	The result	What it tells you
How much code disappears
Effect on verification
Runtime effect on deployed tools
Against the search-based optimiser
Cost of optimising

The prior system took two days to optimise a single 1,771-instruction program, which is the comparison the compilation-time numbers should be read against.Underlined values explain themselves when clicked.

Where this stops working

What to keep in mind

The headline 73 percent reduction is dominated by one optimisation — recovering pointer alignment — with the other five contributing under four percent between them, so this is one strong result with a supporting cast rather than six comparable ideas. The performance comparison against the search-based alternative is also narrow: 0.59 percent throughput and 5.31 percent latency on the programs where both apply, which says the two reach similar code quality and that the real advantages are compilation cost and coverage. The latency results vary sharply with offered load, from about 30 percent at medium load down to 2.54 percent when the link is saturated, so a single average would mislead. And the whole approach is tied to the current sandbox and its documented constraints; a change to the instruction set or the verifier means revisiting which optimisations still apply and still preserve acceptance.

Background

Where this sits among kernel-extension papers

The work on running user code inside the kernel covered elsewhere on this site keeps arriving at the same tension. The sandbox exists because kernel code that misbehaves takes the machine with it, so the rules are strict and the verifier is conservative — and every one of those rules costs something at the level below, in instructions the compiler must emit to satisfy a constraint the source never mentioned. What this paper does is unusual only in how ordinary its method is. It reads the specification, finds where the constraints create redundancy, and writes the passes. The interesting comparison is with the alternative of searching for a better program, which is more general in principle and in practice both far slower and far narrower, because a search needs a formal model of everything it might encounter and nobody had finished writing one.

Check yourself

Check your understanding

1. Why is instruction count more than a performance concern for programs loaded into the kernel this way?
2. Why does a general compiler expand a single sixteen-bit load into four instructions?
3. Why does verification cost fall faster than instruction count?
4. The prior state of the art searches for semantically equivalent programs. Predict its two main limitations relative to writing targeted passes.

Sources

Merlin: Multi-tier Optimization of eBPF Code for Performance and Compactness. Jinsong Mao, Hailun Ding, Juan Zhai, Shiqing Ma. ASPLOS 2024, Volume 3, pages 639 to 653. DOI 10.1145/3620666.3651387. Full text read from the authors’ copy hosted at the University of Massachusetts Amherst. Note that the abstract states the compilation speedup as 106 times, while the evaluation reports six orders of magnitude on average, ranging from about 4,900 to over three million; the abstract figure appears to be a rendering of ten to the sixth.