bpf: Infer zext_dst based on static register liveness analysis

As reported in the thread [1], the verifier's 32-bit operations zero
extension logic is broken. This logic is responsible for correct
semantics of 32-bit operations on s390 architecture.

According to BPF semantics, operation `w1 += 1` is supposed to zero
extend the upper half of the register `r1`. On s390 the JIT relies on
the verifier emitting explicit zero extension before such operations.

The verifier attempts to minimize the amount of zero extensions
inserted by tracking whether upper halves of the 64-bit registers are
ever used. Previously such tracking worked as follows:

- bpf_reg_state->subreg_def field was set by do_check_insn()
  for each operation defining lower but not the upper halves
  of the register.
- Whenever an operation reading the whole register was verified,
  the verifier checked register's subreg_def and set
  bpf_insn_aux_data->zext_dst flag as true via a call to
  mark_insn_zext() function.
- After the verification was complete, a special pass
  bpf_opt_subreg_zext_lo32_rnd_hi32() extended 32-bit operations
  with bpf_insn_aux_data->zext_dst set as true by adding
  explicit zero extension.

Note that the logic above relies on bpf_reg_state->subreg_def,
which is a property of a current verifier state.
Before the commit [2] two additional steps happened:

- The verifier tracked upper and lower register halves' liveness as
  flags REG_LIVE_READ{32,64} in bpf_reg_state->live.
- The function propagate_liveness() called mark_insn_zext()
  in order to transfer the knowledge about which registers have
  their upper halves alive (and thus might require zero extension).

The commit [2] removed the two steps described above,
hence making possible a situation like below:

- The register's upper half is set and is used on some verification
  path P1 and the register happens not to be marked as precise.
- The checkpoint C is created while processing some instruction
  between register initialization and usage.
- On some other verification path P2 the register's upper half is not
  initialized and that path ends hitting the checkpoint C.
- In such a case the register's initialization on path P2 would lack
  zext_dst mark, making it possible for the program to inject
  an arbitrary value in the register's upper half.

This commit replaces subreg_def based logic with computing zext_dst
statically, as a part of the bpf_compute_live_registers() analysis:

- The analysis now tracks usage of upper and lower halves of the
  registers separately.
- If some instruction defines a 32-bit subregister, but not the whole
  register, *and* the upper half of the register is alive after that
  instruction, the instruction is marked as zext_dst.

There is one notable drop in precision: whenever a BPF subprogram is
called, all 64 bits of parameter registers are presumed to be used.
The assumption is that such a drop in precision would not inflict
a noticeable performance penalty.

[1] https://lore.kernel.org/bpf/CAGKGUv=sOuqQtA1Ub-5JXfA4FPosJFYKAQE4B79cK+P1erxqtg@mail.gmail.com/
[2] commit 107e16979905 ("bpf: disable and remove registers chain based liveness")

Fixes: 107e16979905 ("bpf: disable and remove registers chain based liveness")
Reported-by: Min-gyu Kim <gimm78064@gmail.com>
Reported-by: STAR Labs SG <info@starlabs.sg>
Signed-off-by: Eduard Zingerman <eddyz87@gmail.com>
Signed-off-by: Daniel Borkmann <daniel@iogearbox.net>
Acked-by: Daniel Borkmann <daniel@iogearbox.net>
Link: https://lore.kernel.org/bpf/CAGKGUv=sOuqQtA1Ub-5JXfA4FPosJFYKAQE4B79cK+P1erxqtg@mail.gmail.com/
Link: https://lore.kernel.org/bpf/20260807-static-zext-v4-5-b6c270013c77@gmail.com

1 files changed, 1 insertions, 6 deletions

diff --git a/include/linux/bpf_verifier.h b/include/linux/bpf_verifier.h
index a2a40caca0a0..2c74d676ede9 100644
--- a/include/linux/bpf_verifier.h
+++ b/include/linux/bpf_verifier.h
@@ -162,11 +162,6 @@ struct bpf_reg_state {
 	 * pointing to bpf_func_state.
 	 */
 	u32 frameno;
-	/* Tracks subreg definition. The stored value is the insn_idx of the
-	 * writing insn. This is safe because subreg_def is used before any insn
-	 * patching which only happens after main verification finished.
-	 */
-	s32 subreg_def;
 	/* if (!precise && SCALAR_VALUE) min/max/tnum don't affect safety */
 	bool precise;
 };
@@ -1637,7 +1632,6 @@ struct bpf_kfunc_desc_tab {
 };
 
 /* Functions exported from verifier.c, used by fixups.c */
-bool bpf_is_reg64(struct bpf_insn *insn, u32 regno, struct bpf_reg_state *reg, enum bpf_reg_arg_type t);
 void bpf_clear_insn_aux_data(struct bpf_verifier_env *env, int start, int len);
 void bpf_mark_subprog_exc_cb(struct bpf_verifier_env *env, int subprog);
 bool bpf_allow_tail_call_in_subprogs(struct bpf_verifier_env *env);
@@ -1661,5 +1655,6 @@ int bpf_convert_ctx_accesses(struct bpf_verifier_env *env);
 int bpf_jit_subprogs(struct bpf_verifier_env *env);
 int bpf_fixup_call_args(struct bpf_verifier_env *env);
 int bpf_do_misc_fixups(struct bpf_verifier_env *env);
+int bpf_insn_def32(struct bpf_prog *prog, struct bpf_insn *insn);
 
 #endif /* _LINUX_BPF_VERIFIER_H */