LWN: Comments on "Writing network flow dissectors in BPF"

Writing network flow dissectors in BPF

nix — Thu, 13 Sep 2018 11:45:28 +0000

Are loops permitted in eBPF now? I mean, there's no reason loops that the verifier can prove terminate might not exist in eBPF, but last I knew they were still prohibited (in check_cfg()). (... I just checked, and that's still true in master, and in -next.)

In the absence of loops I don't see that target-dependent loop optimizations are going to be particularly relevant (except, I suppose, for complete unrolling.)

Writing network flow dissectors in BPF

dbkm11 — Wed, 12 Sep 2018 11:27:11 +0000

"Linux currently includes one built-in flow dissector; the flower classifier [PDF] is the main user." It's one user but /not/ the main one. Calculating the skb->hash is done using the flow dissector and this is done for every packet in the stack, and its something that cannot be compiled out, hence the target to reduce attack surface there.

Writing network flow dissectors in BPF

jezuch — Tue, 11 Sep 2018 17:14:13 +0000

Java, a JITted runtime, actually is pretty fast. What drags it down in real world workloads is garbage collection pauses. There are techniques that avoid allocation, and thus the GC, but barely anyone uses them.

And the Graal compiler available in newer OpenJDK promises to show what a JIT is really capable of, because the current compiler is so old and complex that progress in it ceased a long time ago. Early adopters of Graal report even 20% improvements, if I remember correctly.

Writing network flow dissectors in BPF

jezuch — Tue, 11 Sep 2018 17:06:43 +0000

> Years of work on C compilers makes them pretty good both at higher level transformations and low level machine specific optimisation.

A C compiler is like a cow. It's big and complex (how many stomachs?) because it has to be if it wants to stand a chance extracting anything of value from the extremely low quality food it takes.

Assembler, on the other hand, is like a dog. It's much simpler because transition from meat to meat is kind of easy.

But C? Nope. It has to work *hard*.

Writing network flow dissectors in BPF

miquels — Tue, 11 Sep 2018 09:09:25 +0000

> [1] For example, using fixed-sized arrays...
> [2] ...and passing them in a way that access bounds remain easily statically provable despite C's pointer decay semantics.

Found this posting by Walter Bright from 2009. Too bad no C compiler has implemented something like it (AFAIK): C's Biggest Mistake.

Writing network flow dissectors in BPF

mtaht — Sat, 08 Sep 2018 15:08:04 +0000

I've heard these sorts of defenses of jitted code over and over again for 30 years. Please forgive me for being dubious as to any advantages in real world applications on anything other than toy benchmarks.

Writing network flow dissectors in BPF

pbonzini — Sat, 08 Sep 2018 15:03:34 +0000

Higher level transformations can still be done when compiling to eBPF, since they are done before instruction selection. So LLVM does the first round of optimization and emits eBPF, while the kernel does bytecode verification and x86 instruction selection. Where a regular compiler has an edge is in register allocation and target-dependent loop optimizations (optimizing induction variables, choosing addressing modes, etc.).

Writing network flow dissectors in BPF

mm7323 — Fri, 07 Sep 2018 22:25:01 +0000

Indeed, it has often been said, and it is logically true, that higher level languages with stronger typing and more descriptive constructs should allow for better compiler optimisation and faster execution.

Often that's not the case as code can be a mess in any language- and though this may also be a situation where the C is aged and not well optimised.

The security benefits of eBPF make this initiative a good thing though. And if anything, further use of eBPF should help drive optimisation efforts in the compiler/assembler.

Writing network flow dissectors in BPF

Paf — Fri, 07 Sep 2018 20:32:15 +0000

I don't know BPF at all, but I can support the idea that it is remarkably difficult to prove constraints in C.

In general, in high performance computing situations, one reason Fortran is sometimes preferred is that it does not have pointers (in practical terms - they do exist but are very little used). A pointer in C can point *anywhere*, so unless the compiler can trace its entire lifecycle, they can make lots of otherwise relatively straightforward optimizations very hard. Pointers can also point in to the middle of what you'd like to have as unitary data types, again preventing certain optimizations. So in general, Fortran code is more easily optimized than C. (There are modified dialects of C that implement some additional constraints for this same reason (C11 has some effort in this direction, I believe).)

That specific example might not apply here, but is hopefully interesting.

Writing network flow dissectors in BPF

wahern — Fri, 07 Sep 2018 19:11:45 +0000

The nature of the BPF instruction set and virtual machine also makes it easier for a compiler to elide rote conditionals and branches, such as related to bounds checking, regardless of the scope and SLoC of the policy logic. This can be accomplished in C, but the language and environment have many more degrees of freedom so it requires careful and deliberate use of data structures[1] and composition[2] such that the compiler can readily ascertain and prove the variants through complex conditionals, type conversions, and deep call chains. Such careful design is normally lacking in typical C software stacks, including Linux kernel networking code, and its one of those aspects of programming (like good error handling, OOM recovery, or concurrency modeling) that demands strict discipline across the code base from the very outset.

A BPF compiler should have an easier time optimizing data access because of the stricter invariants baked into the design; and because these invariants demand greater discipline from the outset. C compilers are super sophisticated and the eBPF compiler quite naive, but we overestimate the ease of proving constraints in general purpose code and underestimate the dividends from code underpinned by strong, natural invariants.

I think this is one aspect of BPF that indisputably gives it a leg up, notwithstanding the abusive use of BPF. I've been critical of the shift to using BPF and eBPF as a green field for reinventing subsystems that are more maintainable and transparent using the normal C kernel interfaces and architecture. From a functional perspective I'm suspicious of heavy BPF usage, but I can't deny the technical potential.

[1] For example, using fixed-sized arrays...
[2] ...and passing them in a way that access bounds remain easily statically provable despite C's pointer decay semantics. (E.g. keep pointer derivations in lexically close proximity to parameter declarations and variable definitions containing the array.) Relying on the compiler to hoist bounds checking out of loops has proven spotty at best. Like JIT optimizations and performance claims, it's theoretically workable but difficult for compilers to resolve consistently. Plus, such hoisting can be done more reliably in something like BPF because there are more invariants enforced from the outset.

Writing network flow dissectors in BPF

mm7323 — Fri, 07 Sep 2018 17:45:54 +0000

Years of work on C compilers makes them pretty good both at higher level transformations and low level machine specific optimisation.

I'd be surprised if this could easily be beaten or quickly replicated by the eBPF compiler.

The only case I see BPF winning is if the BPF program is produced and compiled specifically for the task in hand and thus omits a lot of option checking and branches that are not used in the specific dissector. This could well be what's happening here.

Writing network flow dissectors in BPF

grawity — Fri, 07 Sep 2018 09:26:25 +0000

As long as it's compiled to similar machine code (iirc, ebpf is compiled on load) then there's no reason it shouldn't run at a similar speed, is there?

Writing network flow dissectors in BPF

mtaht — Thu, 06 Sep 2018 22:15:36 +0000

The flow dissector is also heavily used by the various fq based qdiscs.

I still have a hard time believing an ebpf version would be even close in speed to the C version... but... cool.