mirrors/linux
0
0 Fork 0
mirror of https://git.kernel.org/pub/scm/linux/kernel/git/torvalds/linux.git synced 2026-10-26 10:57:38 +08:00
Code Activity
Files
master
linux/kernel/bpf/const_fold.c
T
Alexei Starovoitov a2d2747713 bpf: Add unwind_goto and unwind_exit insns 
Rust Drop, C++ destructors and __attribute__((cleanup)) in C have to run
when a panic or an exception passes through a frame.

v1 [1] did it with a flag in r3 and 'if r3 != 0 goto pad' after the call.
Three bugs that the bots found there had the same cause: r3 is an ordinary
register, and JITs guessed the meaning from the shape of the code.
Kumar suggested new insns instead [2]:

  unwind_goto pad    BPF_JMP | BPF_JCOND, src_reg = BPF_UNWIND_GOTO
  unwind_exit        BPF_JMP | BPF_EXIT,  src_reg = BPF_UNWIND_EXIT

'call foo; unwind_goto pad' goes to the pad when foo left with unwind_exit
and falls through when it left with exit. No register says which one it
was. In everything else unwind_exit is exit.

llvm lowers unwinding to them [3]:

  ret                            exit
  invoke foo unwind pad          call foo; unwind_goto pad
  resume                         r0 = 0; unwind_exit
  call _Unwind_RaiseException    r0 = 0; unwind_exit
  invoke _Unwind_RaiseException  goto pad

In a function that returns 16 bytes it's 'r0 = 0; r2 = 0; unwind_exit'.

Landing pads are ordinary blocks, so the verifier checks them like any
other code. A pad that forgets to drop a lock or a reference is a leak on
that path. There are no tables, no stack walk, no kfuncs, no BTF and
nothing to do for libbpf and other loaders.

In the verifier:
- unwind_goto has to follow a call or callx of a subprog and cannot be
  a jump target. For cfg, liveness and the rest it's one more conditional
  jump, like may_goto.
- How the callee left is one bit of the verifier state. It lives from
  the exit of the callee to the next insn. states_equal() looks at it,
  since the registers can be the same either way.
- unwind_exit is rejected when unwind_goto doesn't follow the call.
- A global subprog that has unwind_exit can leave either way. Both are
  explored after the call, like it's done for might_throw.
- A sync callback cannot unwind. The helper that calls it doesn't expect
  that: bpf_loop() would go on.
- unwind_exit of the main prog is exit, unless it's an extension. So it is
  in async and exception callbacks. The kernel calls them, and there is no
  frame to unwind to.
- An extension leaves either way, like the subprog that it replaced.
  freplace is a jump, so the extension returns to the caller of
  the subprog. An extension that has unwind_exit can replace only a subprog
  that has it too. Otherwise there is no unwind_goto after the calls.
- Of tracing progs only fentry can attach to a subprog or an extension
  that has unwind_exit. It would return to the trampoline that called it.
- unwind_exit changes its return address, so the cpu mispredicts
  the return and runs what follows unwind_goto speculatively. Without
  CAP_PERFMON the verifier looks at that path too.
- unwind_goto goes away together with a pad that turned out to be dead
  code. It stays when what follows it is dead code. The cpu predicts that
  the callee returns there, so 'goto pc-1' takes the place of the dead
  code. Otherwise its removal would move other code there.

JITs don't emit a branch:

  unwind_goto:
	extable[n++] = { ret_addr - 1 -> pad }
  unwind_exit:
	my_ret_addr = bpf_unwind_target(my_ret_addr)
	epilogue

So exit and the normal path after the call cost nothing. Every frame fixes
only its own return address. There is no stack walk. The lookup is what
the page fault handler does for bpf progs.
The interpreter cannot do that, so the prog has to be JITed, and JITs opt
in with bpf_jit_supports_unwind(). x86-64 and arm64 are in the next
patches.

BPF_JCOND is the same opcode as BPF_CALL_ARGS of the interpreter, and
BPF_UNWIND_GOTO is the same number as BPF_PSEUDO_CALL. may_goto is gone by
the time a prog is dumped, unwind_goto is not. bpf_insn_prepare_dump()
tells them apart: a prog with unwind_goto is always JITed.

Compared to v1 there is no BTF decl_tag and no 'r3 = 0' before every exit.
Tail call and ld_abs are fine in a subprog that can unwind, since they
leave it like exit does.

unwind_exit doesn't set r0. An implicit definition of r0 would need
special cases in backtracking, in liveness and in the check of the return
value of the main prog. A plain 'r0 = 0' in front of it needs none.

Rust

rust-bpf [4] builds with that llvm as it is. The programs are built with
-C panic=unwind. The panic handler prints the message and calls
_Unwind_RaiseException().
exc_cleanup.rs panics three frames deep, with preemption disabled in one
frame and rcu_read_lock held in another. All Drop impls run and the prog
returns 0.
scx_simple.rs is 2195 insns with 48 unwind_goto, 20 of them after callx,
and 16 unwind_exit. With r3 it was 2216 insns. scx_cosmos.rs is 3694 insns
with 68 and 18. It was 3716.

C++

Exceptions work too. This compiles, loads and runs:

  struct rcu_guard {
          rcu_guard() { bpf_rcu_read_lock(); }
          ~rcu_guard() { bpf_rcu_read_unlock(); }
  };

  static __noinline int inner(int len)
  {
          rcu_guard guard;

          if (len > 100)
                  throw 1;
          return len;
  }

  SEC("tc") int prog(struct __sk_buff *skb)
  {
          try {
                  return inner(skb->len);
          } catch (...) {
                  return 42;
          }
  }

It returns 64 for a packet of 64 bytes and 42 for a packet of 200 bytes.
The destructor runs in both cases, otherwise the verifier would reject
the prog. 'throw' is a jump to the pad with the destructor. 'catch' is
unwind_goto:

  inner:
    w6 = w1
    call bpf_rcu_read_lock
    if w6 s< 101 goto ret
    r1 = exc_obj ll
    *(u32 *)(r1 + 0) = 1
    goto pad
  ret:
    call bpf_rcu_read_unlock
    w0 = w6
    exit
  pad:
    call bpf_rcu_read_unlock
    r0 = 0
    unwind_exit

  prog:
    w6 = *(u32 *)(r1 + 0)
    w1 = w6
    call inner
    unwind_goto catch
  out:
    w0 = w6
    exit
  catch:
    w6 = 42
    goto out

It needs -fexceptions -funwind-tables and four one line __cxa_*()
functions, where __cxa_throw() calls _Unwind_RaiseException().
Every pad is entered whatever was thrown, so llvm takes catch (...) only.
It's a selftest in patch 5.

[1] https://lore.kernel.org/bpf/20261018010246.1643877-1-alexei.starovoitov@gmail.com/
[2] https://lore.kernel.org/bpf/DM7KR7J8VY2T.1CZIRUF6QRCWG@gmail.com/
[3] https://github.com/llvm/llvm-project/pull/233649
[4] https://github.com/4ast/rust-bpf

Suggested-by: Kumar Kartikeya Dwivedi <memxor@gmail.com>
Signed-off-by: Alexei Starovoitov <ast@kernel.org>
Link: https://patch.msgid.link/20261020181320.1284798-2-alexei.starovoitov@gmail.com
2026-10-20 20:54:25 +00:00

405 lines
11 KiB
C
Raw Permalink Blame History

// SPDX-License-Identifier: GPL-2.0-only
/* Copyright (c) 2026 Meta Platforms, Inc. and affiliates. */
#include <linux/bpf_verifier.h>
/*
* Forward dataflow analysis to determine constant register values at every
* instruction. Tracks 64-bit constant values in R0-R9 through the program,
* using a fixed-point iteration in reverse postorder. Records which registers
* hold known constants and their values in
* env->insn_aux_data[].{const_reg_mask, const_reg_vals}.
*/
enum const_arg_state {
CONST_ARG_UNVISITED, /* instruction not yet reached */
CONST_ARG_UNKNOWN, /* register value not a known constant */
CONST_ARG_CONST, /* register holds a known 64-bit constant */
CONST_ARG_MAP_PTR, /* register holds a map pointer, map_index is set */
CONST_ARG_MAP_VALUE, /* register points to map value data, val is offset */
CONST_ARG_SUBPROG, /* register holds a subprog pointer, val is subprog number */
};
struct const_arg_info {
enum const_arg_state state;
u32 map_index;
u64 val;
};
static bool ci_is_unvisited(const struct const_arg_info *ci)
{
return ci->state == CONST_ARG_UNVISITED;
}
static bool ci_is_unknown(const struct const_arg_info *ci)
{
return ci->state == CONST_ARG_UNKNOWN;
}
static bool ci_is_const(const struct const_arg_info *ci)
{
return ci->state == CONST_ARG_CONST;
}
static bool ci_is_map_value(const struct const_arg_info *ci)
{
return ci->state == CONST_ARG_MAP_VALUE;
}
/* Transfer function: compute output register state from instruction. */
static void const_reg_xfer(struct bpf_verifier_env *env, struct const_arg_info *ci_out,
struct bpf_insn *insn, struct bpf_insn *insns, int idx)
{
struct const_arg_info unknown = { .state = CONST_ARG_UNKNOWN, .val = 0 };
struct const_arg_info *dst = &ci_out[insn->dst_reg];
struct const_arg_info *src = &ci_out[insn->src_reg];
u8 class = BPF_CLASS(insn->code);
u8 mode = BPF_MODE(insn->code);
u8 opcode = BPF_OP(insn->code) | BPF_SRC(insn->code);
int r;
/* Stack arg stores (r11-based) are outside the tracked register set. */
if (is_stack_arg_st(insn) || is_stack_arg_stx(insn))
return;
if (is_stack_arg_ldx(insn)) {
ci_out[insn->dst_reg] = unknown;
return;
}
switch (class) {
case BPF_ALU:
case BPF_ALU64:
switch (opcode) {
case BPF_MOV | BPF_K:
dst->state = CONST_ARG_CONST;
dst->val = (s64)insn->imm;
break;
case BPF_MOV | BPF_X:
*dst = *src;
if (!insn->off)
break;
if (!ci_is_const(dst)) {
*dst = unknown;
break;
}
switch (insn->off) {
case 8: dst->val = (s8)dst->val; break;
case 16: dst->val = (s16)dst->val; break;
case 32: dst->val = (s32)dst->val; break;
default: *dst = unknown; break;
}
break;
case BPF_ADD | BPF_K:
if (!ci_is_const(dst) && !ci_is_map_value(dst)) {
*dst = unknown;
break;
}
dst->val += insn->imm;
break;
case BPF_SUB | BPF_K:
if (!ci_is_const(dst) && !ci_is_map_value(dst)) {
*dst = unknown;
break;
}
dst->val -= insn->imm;
break;
case BPF_AND | BPF_K:
if (!ci_is_const(dst)) {
if (!insn->imm) {
dst->state = CONST_ARG_CONST;
dst->val = 0;
} else {
*dst = unknown;
}
break;
}
dst->val &= (s64)insn->imm;
break;
case BPF_AND | BPF_X:
if (ci_is_const(dst) && dst->val == 0)
break; /* 0 & x == 0 */
if (ci_is_const(src) && src->val == 0) {
dst->state = CONST_ARG_CONST;
dst->val = 0;
break;
}
if (!ci_is_const(dst) || !ci_is_const(src)) {
*dst = unknown;
break;
}
dst->val &= src->val;
break;
default:
*dst = unknown;
break;
}
if (class == BPF_ALU) {
if (ci_is_const(dst))
dst->val = (u32)dst->val;
else if (!ci_is_unknown(dst))
*dst = unknown;
}
break;
case BPF_LD:
if (mode == BPF_ABS || mode == BPF_IND)
goto process_call;
if (mode != BPF_IMM || BPF_SIZE(insn->code) != BPF_DW)
break;
if (insn->src_reg == BPF_PSEUDO_FUNC) {
int subprog = bpf_find_subprog(env, idx + insn->imm + 1);
if (subprog >= 0) {
dst->state = CONST_ARG_SUBPROG;
dst->val = subprog;
} else {
*dst = unknown;
}
} else if (insn->src_reg == BPF_PSEUDO_MAP_VALUE ||
insn->src_reg == BPF_PSEUDO_MAP_IDX_VALUE) {
dst->state = CONST_ARG_MAP_VALUE;
dst->map_index = env->insn_aux_data[idx].map_index;
dst->val = env->insn_aux_data[idx].map_off;
} else if (insn->src_reg == BPF_PSEUDO_MAP_FD ||
insn->src_reg == BPF_PSEUDO_MAP_IDX) {
dst->state = CONST_ARG_MAP_PTR;
dst->map_index = env->insn_aux_data[idx].map_index;
} else if (insn->src_reg == 0) {
dst->state = CONST_ARG_CONST;
dst->val = (u64)(u32)insn->imm | ((u64)(u32)insns[idx + 1].imm << 32);
} else {
*dst = unknown;
}
break;
case BPF_LDX:
if (!ci_is_map_value(src)) {
*dst = unknown;
break;
}
struct bpf_map *map = env->used_maps[src->map_index];
int size = bpf_size_to_bytes(BPF_SIZE(insn->code));
bool is_ldsx = mode == BPF_MEMSX;
int off = src->val + insn->off;
u64 val = 0;
u32 cnt;
if (!bpf_map_is_rdonly(map) || !map->ops->map_direct_value_addr ||
off < 0 || off + size > map->value_size ||
/* so are the addresses of functions that the map points to */
bpf_map_range_func_ptrs(env, map, off, size, &cnt) ||
bpf_map_direct_read(map, off, size, &val, is_ldsx)) {
*dst = unknown;
break;
}
dst->state = CONST_ARG_CONST;
dst->val = val;
break;
case BPF_JMP:
/* both 'call imm' and 'callx reg' clobber caller saved registers */
if (BPF_OP(insn->code) != BPF_CALL)
break;
process_call:
for (r = BPF_REG_0; r <= BPF_REG_5; r++)
ci_out[r] = unknown;
break;
case BPF_STX:
r = bpf_atomic_load_reg(insn);
if (r >= 0)
ci_out[r] = unknown;
break;
}
}
/* Join function: merge output state into a successor's input state. */
static bool const_reg_join(struct const_arg_info *ci_target,
struct const_arg_info *ci_out)
{
bool changed = false;
int r;
for (r = 0; r < MAX_BPF_REG; r++) {
struct const_arg_info *old = &ci_target[r];
struct const_arg_info *new = &ci_out[r];
if (ci_is_unvisited(old) && !ci_is_unvisited(new)) {
ci_target[r] = *new;
changed = true;
} else if (!ci_is_unknown(old) && !ci_is_unvisited(old) &&
(new->state != old->state || new->val != old->val ||
new->map_index != old->map_index)) {
old->state = CONST_ARG_UNKNOWN;
changed = true;
}
}
return changed;
}
int bpf_compute_const_regs(struct bpf_verifier_env *env)
{
struct const_arg_info unknown = { .state = CONST_ARG_UNKNOWN, .val = 0 };
struct bpf_insn_aux_data *insn_aux = env->insn_aux_data;
struct bpf_insn *insns = env->prog->insnsi;
int insn_cnt = env->prog->len;
struct const_arg_info (*ci_in)[MAX_BPF_REG];
struct const_arg_info ci_out[MAX_BPF_REG];
struct bpf_iarray *succ;
bool changed;
int i, r;
/* kvzalloc zeroes memory, so all entries start as CONST_ARG_UNVISITED (0) */
ci_in = kvzalloc_objs(*ci_in, insn_cnt, GFP_KERNEL_ACCOUNT);
if (!ci_in)
return -ENOMEM;
/* Subprogram entries (including main at subprog 0): all registers unknown */
for (i = 0; i < env->subprog_cnt; i++) {
int start = env->subprog_info[i].start;
for (r = 0; r < MAX_BPF_REG; r++)
ci_in[start][r] = unknown;
}
redo:
changed = false;
for (i = env->cfg.cur_postorder - 1; i >= 0; i--) {
int idx = env->cfg.insn_postorder[i];
struct bpf_insn *insn = &insns[idx];
struct const_arg_info *ci = ci_in[idx];
memcpy(ci_out, ci, sizeof(ci_out));
const_reg_xfer(env, ci_out, insn, insns, idx);
succ = bpf_insn_successors(env, idx);
for (int s = 0; s < succ->cnt; s++)
changed |= const_reg_join(ci_in[succ->items[s]], ci_out);
}
if (changed)
goto redo;
/* Save computed constants into insn_aux[] if they fit into 32-bit */
for (i = 0; i < insn_cnt; i++) {
u16 mask = 0, map_mask = 0, subprog_mask = 0;
struct bpf_insn_aux_data *aux = &insn_aux[i];
struct const_arg_info *ci = ci_in[i];
for (r = BPF_REG_0; r < ARRAY_SIZE(aux->const_reg_vals); r++) {
struct const_arg_info *c = &ci[r];
switch (c->state) {
case CONST_ARG_CONST: {
u64 val = c->val;
if (val != (u32)val)
break;
mask |= BIT(r);
aux->const_reg_vals[r] = val;
break;
}
case CONST_ARG_MAP_PTR:
map_mask |= BIT(r);
aux->const_reg_vals[r] = c->map_index;
break;
case CONST_ARG_SUBPROG:
subprog_mask |= BIT(r);
aux->const_reg_vals[r] = c->val;
break;
default:
break;
}
}
aux->const_reg_mask = mask;
aux->const_reg_map_mask = map_mask;
aux->const_reg_subprog_mask = subprog_mask;
}
kvfree(ci_in);
return 0;
}
static int eval_const_branch(u8 opcode, u64 dst_val, u64 src_val)
{
switch (BPF_OP(opcode)) {
case BPF_JEQ: return dst_val == src_val;
case BPF_JNE: return dst_val != src_val;
case BPF_JGT: return dst_val > src_val;
case BPF_JGE: return dst_val >= src_val;
case BPF_JLT: return dst_val < src_val;
case BPF_JLE: return dst_val <= src_val;
case BPF_JSGT: return (s64)dst_val > (s64)src_val;
case BPF_JSGE: return (s64)dst_val >= (s64)src_val;
case BPF_JSLT: return (s64)dst_val < (s64)src_val;
case BPF_JSLE: return (s64)dst_val <= (s64)src_val;
case BPF_JSET: return (bool)(dst_val & src_val);
default: return -1;
}
}
/*
* Rewrite conditional branches with constant outcomes into unconditional
* jumps using register values resolved by bpf_compute_const_regs() pass.
* This eliminates dead edges from the CFG so that compute_live_registers()
* doesn't propagate liveness through dead code.
*/
int bpf_prune_dead_branches(struct bpf_verifier_env *env)
{
struct bpf_insn_aux_data *insn_aux = env->insn_aux_data;
struct bpf_insn *insns = env->prog->insnsi;
int insn_cnt = env->prog->len;
bool changed = false;
int i;
for (i = 0; i < insn_cnt; i++) {
struct bpf_insn_aux_data *aux = &insn_aux[i];
struct bpf_insn *insn = &insns[i];
u8 class = BPF_CLASS(insn->code);
u64 dst_val, src_val;
int taken;
if (!bpf_insn_is_cond_jump(insn->code))
continue;
if (BPF_OP(insn->code) == BPF_JCOND)
continue;
if (!(aux->const_reg_mask & BIT(insn->dst_reg)))
continue;
dst_val = aux->const_reg_vals[insn->dst_reg];
if (BPF_SRC(insn->code) == BPF_K) {
src_val = insn->imm;
} else {
if (!(aux->const_reg_mask & BIT(insn->src_reg)))
continue;
src_val = aux->const_reg_vals[insn->src_reg];
}
if (class == BPF_JMP32) {
/*
* The (s32) cast maps the 32-bit range into two u64 sub-ranges:
* [0x00000000, 0x7FFFFFFF] -> [0x0000000000000000, 0x000000007FFFFFFF]
* [0x80000000, 0xFFFFFFFF] -> [0xFFFFFFFF80000000, 0xFFFFFFFFFFFFFFFF]
* The ordering is preserved within each sub-range, and
* the second sub-range is above the first as u64.
*/
dst_val = (s32)dst_val;
src_val = (s32)src_val;
}
taken = eval_const_branch(insn->code, dst_val, src_val);
if (taken < 0) {
bpf_log(&env->log, "Unknown conditional jump %x\n", insn->code);
return -EFAULT;
}
*insn = BPF_JMP_A(taken ? insn->off : 0);
changed = true;
}
if (!changed)
return 0;
/* recompute postorder, since CFG has changed */
kvfree(env->cfg.insn_postorder);
env->cfg.insn_postorder = NULL;
kvfree(env->cfg.postorder_nums);
env->cfg.postorder_nums = NULL;
return bpf_compute_postorder(env);
}
View Git Blame Copy Permalink