[$] A look inside the BPF verifier

LWN has covered BPFsince its initial introduction to Linux, usually through the lens of the newestdevelopments; this can make it hard to view the whole picture. BPF providesa way to extend a running kernel, without having to recompile and reboot.It does this in a safe way, so that malicious BPFprograms cannot crash a running kernel, thanks to the BPF verifier. So how doesthe verifier actually work, what are its limits, and how has it changed sincethe early days of BPF?