BPF verifier drops fixed caps that rejected large programs
Alexei Starovoitov proposes growing tables for maps, subprograms and kfuncs, and faster checks so safe programs are no longer turned away for size.
Alexei Starovoitov has proposed removing most of the fixed ceilings the Linux BPF verifier uses when it loads a program, so a program that is otherwise safe is no longer rejected for needing one more map, subprogram or kernel function.
Those ceilings do not protect the kernel once a program is running. They are the size of an array, or they hide an algorithm that does not scale, and they have been raised only after a real program hit them. Starovoitov wrote that Rust crates have already done that to two of the numbers. "None of these numbers protects the kernel at run time."
Today a program may use at most 64 maps, 256 kernel functions, 1,024 subprograms and a 4,096-entry file-descriptor array, among other caps. Under the proposal those tables grow with the program. Kernel functions would still stop at 65,536, and a few smaller ceilings remain, including the length of a BTF name. Work that was quadratic, or worse, below the old limits becomes linear or n log n. Outside the tools tree the kernel shrinks by a few hundred lines.
The change also replaces a dominance calculation that bogged down when many branches met at one instruction: 30,000 such edges took 13 seconds, and 100,000 did not finish. Starovoitov switches that walk to the Lengauer-Tarjan algorithm. Loading a program under memory pressure would return an out-of-memory error instead of invoking the OOM killer, and a load stopped by a fatal signal or by the freezer is meant to restart without the caller seeing the interruption.
Automated review on the BPF list did not sign off cleanly. One report says the restart logic misses commands that set the common-attributes flag, so a frozen load can return EINTR, which existing retry loops do not treat as a reason to try again. Another says binding another map to an already huge program can trip a kernel warning, impractical without enormous memory and file descriptors but inconsistent with the no-warn allocations used elsewhere. Reviewers also flagged a pre-existing leak in which resolved kernel map pointers can be hashed into a subprogram tag and exposed to user space, plus selftest failures on architectures without private stacks. Starovoitov had not replied in the material posted with the series.