On 12/4/23 5:32 PM, Andrii Nakryiko wrote:
On Mon, Dec 4, 2023 at 11:26 AM Andrii Nakryiko <andrii@xxxxxxxxxx> wrote:Add support to BPF verifier to track and support register spill/fill to/from stack regardless if it was done through read-only R10 register (which is the only form supported today), or through a general register after copying R10 into it, while also potentially modifying offset. Once we add register this generic spill/fill support to precision backtracking, we can take advantage of it to stop doing eager STACK_ZERO conversion on register spill. Instead we can rely on (im)precision of spilled const zero register to improve verifier state pruning efficiency. This situation of using const zero register to initialize stack slots is very common with __builtin_memset() usage or just zero-initializing variables on the stack, and it causes unnecessary state duplication, as that STACK_ZERO knowledge is often not necessary for correctness, as those zero values are never used in precise context. Thus, relying on register imprecision helps tremendously, especially in real-world BPF programs. To make spilled const zero register behave completely equivalently to STACK_ZERO, we need to improve few other small pieces, which is done in the second part of the patch set. See individual patches for details. There are also two small bug fixes spotted during STACK_ZERO debugging. The patch set consists of logically three changes: - patch #1 (and corresponding tests in patch #2) is fixing/impoving precision propagation for stack spills/fills. This can be landed as a stand-alone improvement; - patches #3 through #9 is improving verification scalability by utilizing register (im)precision instead of eager STACK_ZERO. These changes depend on patch #1. - patch #10 is a memory efficiency improvement to how instruction/jump history is tracked and maintained. It depends on patch #1, but is not strictly speaking required, even though I believe it's a good long-term solution to have a path-dependent per-instruction information. Kind of like a path-dependent counterpart to path-agnostic insn_aux array. v2->v3: - BPF_ST instruction workaround (Eduard);ok, so I fixed this in the main partial_stack_load_preserves_zeros test, but there is at least spill_subregs_preserve_stack_zero that needs fixing as well. I'll audit all the tests thoroughly and will fix all BPF_ST uses. Eduard or Yonghong, what's the Clang version that does support BPF_ST instructions in inline asm? When would we be able to just assume those instructions are supported?
For inline asm, llvm18. For C->asm codegen, llvm18 + cpu=v4. [...]
