no_caller_saved_registers attribute for helper calls

Extract the part of check_helper_call() as a utility function allowing to query 'struct bpf_func_proto' for a specific helper function id.

Signed-off-by Eduard Zingerman <[email protected]>

---
 kernel/bpf/verifier.c | 30 +++++++++++++++++++++++-------
 1 file changed, 23 insertions(+), 7 deletions(-)

kernel/bpf/verifier.c +3 -0

index d3927d819465..4869f1fb0a42 100644
@@ -10261,6 +10261,24 @@ static void update_loop_inline_state(struct bpf_verifier_env *env, u32 subprogno
                                 state->callback_subprogno == subprogno);
 }
 
+static int get_helper_proto(struct bpf_verifier_env *env, int func_id,
+                           const struct bpf_func_proto **ptr)
+{

kernel/bpf/verifier.c +5 -3

+
+       *ptr = result;
+       return 0;
+}
+
 static int check_helper_call(struct bpf_verifier_env *env, struct bpf_insn *insn,
                             int *insn_idx_p)
 {

@@ -10277,18 +10295,16 @@ static int check_helper_call(struct bpf_verifier_env *env, struct bpf_insn *insn
 
        /* find function prototype */
        func_id = insn->imm;
-       if (func_id < 0 || func_id >= __BPF_FUNC_MAX_ID) {
-               verbose(env, "invalid func %s#%d\n", func_id_name(func_id),
-                       func_id);

kernel/bpf/verifier.c +1 -2

                verbose(env, "program of this type cannot use helper %s#%d\n",
                        func_id_name(func_id), func_id);
-               return -EINVAL;
+               return err;
        }
 
        /* eBPF programs must be GPL compatible to use GPL-ed functions */
--

2.45.2

Quoted 7 lines

kernel/bpf/verifier.c +3 -0

@@ -10261,6 +10261,24 @@ static void update_loop_inline_state(struct bpf_verifier_env *env, u32 subprogno
                                 state->callback_subprogno == subprogno);
 }
 
+static int get_helper_proto(struct bpf_verifier_env *env, int func_id,
+                           const struct bpf_func_proto **ptr)
+{

kernel/bpf/verifier.c static void update_loop_inline_state(struct bpf_verifier_env *env, u32 subprogno · line 10276

Quoted 10 lines

kernel/bpf/verifier.c +10 -0

+       const struct bpf_func_proto *result = NULL;
+
+       if (func_id < 0 || func_id >= __BPF_FUNC_MAX_ID)
+               return -ERANGE;
+
+       if (env->ops->get_func_proto)
+               result = env->ops->get_func_proto(func_id, env->prog);
+
+       if (!result)
+               return -EINVAL;

result is a bit unnecessary. We could do either

*ptr = NULL;
if (env->ops->get_func_proto)

    *ptr = env->ops->get_func_proto(func_id, env->prog);

return *ptr ? 0 : -EINVAL;

or just

if (!env->ops->get_func_proto)

    return -EINVAL;

*ptr = env->ops->get_func_proto(func_id, env->prog);

return *ptr ? 0 : -EINVAL;

GCC and LLVM define a no_caller_saved_registers function attribute. This attribute means that function scratches only some of the caller saved registers defined by ABI.
For BPF the set of such registers could be defined as follows:
- R0 is scratched only if function is non-void;
- R1-R5 are scratched only if corresponding parameter type is defined in the function prototype.

This commit introduces flag bpf_func_prot->allow_nocsr. If this flag is set for some helper function, verifier assumes that it follows no_caller_saved_registers calling convention.

The contract between kernel and clang allows to simultaneously use such functions and maintain backwards compatibility with old kernels that don't understand no_caller_saved_registers calls (nocsr for short):

- clang generates a simple pattern for nocsr calls, e.g.:

    r1 = 1;
    r2 = 2;
    *(u64 *)(r10 - 8)  = r1;
    *(u64 *)(r10 - 16) = r2;
    call %[to_be_inlined]
    r2 = *(u64 *)(r10 - 16);
    r1 = *(u64 *)(r10 - 8);
    r0 = r1;
    r0 += r2;
    exit;

- kernel removes unnecessary spills and fills, if called function is inlined by verifier or current JIT (with assumption that patch inserted by verifier or JIT honors nocsr contract, e.g. does not scratch r3-r5 for the example above), e.g. the code above would be transformed to:

    r1 = 1;
    r2 = 2;
    call %[to_be_inlined]
    r0 = r1;
    r0 += r2;
    exit;

Technically, the transformation is split into the following phases:
- function mark_nocsr_pattern_patterns(), called from bpf_check() searches and marks potential patterns in instruction auxiliary data;
- upon stack read or write access,
function check_nocsr_stack_contract() is used to verify if stack offsets, presumably reserved for nocsr patterns, are used only from those patterns;
- function do_misc_fixups(), called from bpf_check(), applies the rewrite for valid patterns.

See comment in mark_nocsr_pattern_for_call() for more details.

Suggested-by Alexei Starovoitov <[email protected]>

Signed-off-by Eduard Zingerman <[email protected]>

---
 include/linux/bpf.h          |   6 +
 include/linux/bpf_verifier.h |  14 ++
 kernel/bpf/verifier.c        | 300 ++++++++++++++++++++++++++++++++++-
 3 files changed, 314 insertions(+), 6 deletions(-)

include/linux/bpf.h +6 -0

index 960780ef04e1..391e19c5cd68 100644
@@ -807,6 +807,12 @@ struct bpf_func_proto {
        bool gpl_only;
        bool pkt_access;
        bool might_sleep;
+       /* set to true if helper follows contract for gcc/llvm
+        * attribute no_caller_saved_registers:
+        * - void functions do not scratch r0
+        * - functions taking N arguments scratch only registers r1-rN
+        */
+       bool allow_nocsr;
        enum bpf_return_type ret_type;
        union {
                struct {

include/linux/bpf_verifier.h +0 -0

index 2b54e25d2364..735ae0901b3d 100644
@@ -585,6 +585,15 @@ struct bpf_insn_aux_data {
         * accepts callback function as a parameter.

include/linux/bpf_verifier.h +2 -0

+        */
+       s16 nocsr_stack_off;
        bool has_tail_call: 1;
        bool tail_call_reachable: 1;
        bool has_ld_abs: 1;

kernel/bpf/verifier.c +4 -2

index 4869f1fb0a42..d16a249b59ad 100644
@@ -2471,16 +2471,37 @@ static int cmp_subprogs(const void *a, const void *b)
               ((struct bpf_subprog_info *)b)->start;
 }
 
-static int find_subprog(struct bpf_verifier_env *env, int off)
+/* Find subprogram that contains instruction at 'off' */
+static int find_containing_subprog(struct bpf_verifier_env *env, int off)
 {
-       struct bpf_subprog_info *p;
+       struct bpf_subprog_info *vals = env->subprog_info;
+       int l, r, m;

kernel/bpf/verifier.c +10 -0

+
+/* Find subprogram that starts exactly at 'off' */
+static int find_subprog(struct bpf_verifier_env *env, int off)
+{
+       int idx;
+
+       idx = find_containing_subprog(env, off);
+       if (idx < 0 || env->subprog_info[idx].start != off)
+               return -ENOENT;
+       return idx;
 }
 
 static int add_subprog(struct bpf_verifier_env *env, int off)

@@ -4501,6 +4522,23 @@ static int get_reg_width(struct bpf_reg_state *reg)
        return fls64(reg->umax_value);
 }

kernel/bpf/verifier.c +15 -0

+        * from something that is not a part of the nocsr pattern,
+        * disable nocsr rewrites for current subprogram by setting
+        * nocsr_stack_off to a value smaller than any possible offset.
+        */
+       subprog->nocsr_stack_off = S16_MIN;
+}
+
 /* check_stack_{read,write}_fixed_off functions track spill/fill of registers,
  * stack boundary and alignment are checked in check_mem_access()
  */

@@ -4549,6 +4587,7 @@ static int check_stack_write_fixed_off(struct bpf_verifier_env *env,
        if (err)
                return err;
 
+       check_nocsr_stack_contract(env, state, insn_idx, off);
        mark_stack_slot_scratched(env, spi);
        if (reg && !(off % BPF_REG_SIZE) && reg->type == SCALAR_VALUE && env->bpf_capable) {
                bool reg_value_fits;

@@ -4682,6 +4721,7 @@ static int check_stack_write_var_off(struct bpf_verifier_env *env,
                        return err;
        }
 
+       check_nocsr_stack_contract(env, state, insn_idx, min_off);
        /* Variable offset writes destroy any spilled pointers in range. */
        for (i = min_off; i < max_off; i++) {
                u8 new_type, *stype;

@@ -4820,6 +4860,7 @@ static int check_stack_read_fixed_off(struct bpf_verifier_env *env,
        reg = &reg_state->stack[spi].spilled_ptr;
 
        mark_stack_slot_scratched(env, spi);
+       check_nocsr_stack_contract(env, state, env->insn_idx, off);
 
        if (is_spilled_reg(&reg_state->stack[spi])) {
                u8 spill_size = 1;

@@ -4980,6 +5021,7 @@ static int check_stack_read_var_off(struct bpf_verifier_env *env,
        min_off = reg->smin_value + off;
        max_off = reg->smax_value + off;
        mark_reg_stack_read(env, ptr_state, min_off, max_off + size, dst_regno);
+       check_nocsr_stack_contract(env, ptr_state, env->insn_idx, min_off);
        return 0;
 }
 

@@ -15951,6 +15993,206 @@ static int visit_func_call_insn(int t, struct bpf_insn *insns,
        return ret;
 }
 
+/* Bitmask with 1s for all caller saved registers */
+#define ALL_CALLER_SAVED_REGS ((1u << CALLER_SAVED_REGS) - 1)
+
+/* Return a bitmask specifying which caller saved registers are

kernel/bpf/verifier.c +19 -0

+{
+       u8 mask;
+       int i;
+
+       if (!fn->allow_nocsr)
+               return ALL_CALLER_SAVED_REGS;
+
+       mask = 0;
+       if (fn->ret_type != RET_VOID)
+               mask |= BIT(BPF_REG_0);
+       for (i = 0; i < ARRAY_SIZE(fn->arg_type); ++i)
+               if (fn->arg_type[i] != ARG_DONTCARE)
+                       mask |= BIT(BPF_REG_1 + i);
+       return mask;
+}
+
+/* True if do_misc_fixups() replaces calls to helper number 'imm',
+ * replacement patch is presumed to follow no_caller_saved_registers contract
+ * (see mark_nocsr_pattern_for_call() below).

kernel/bpf/verifier.c +69 -0

+
+       return ALL_CALLER_SAVED_REGS;
+}
+
+/* GCC and LLVM define a no_caller_saved_registers function attribute.
+ * This attribute means that function scratches only some of
+ * the caller saved registers defined by ABI.
+ * For BPF the set of such registers could be defined as follows:
+ * - R0 is scratched only if function is non-void;
+ * - R1-R5 are scratched only if corresponding parameter type is defined
+ *   in the function prototype.
+ *
+ * The contract between kernel and clang allows to simultaneously use
+ * such functions and maintain backwards compatibility with old
+ * kernels that don't understand no_caller_saved_registers calls
+ * (nocsr for short):
+ *
+ * - for nocsr calls clang allocates registers as-if relevant r0-r5
+ *   registers are not scratched by the call;
+ *
+ * - as a post-processing step, clang visits each nocsr call and adds
+ *   spill/fill for every live r0-r5;
+ *
+ * - stack offsets used for the spill/fill are allocated as minimal
+ *   stack offsets in whole function and are not used for any other
+ *   purposes;
+ *
+ * - when kernel loads a program, it looks for such patterns
+ *   (nocsr function surrounded by spills/fills) and checks if
+ *   spill/fill stack offsets are used exclusively in nocsr patterns;
+ *
+ * - if so, and if verifier or current JIT inlines the call to the
+ *   nocsr function (e.g. a helper call), kernel removes unnecessary
+ *   spill/fill pairs;
+ *
+ * - when old kernel loads a program, presence of spill/fill pairs
+ *   keeps BPF program valid, albeit slightly less efficient.
+ *
+ * For example:
+ *
+ *   r1 = 1;
+ *   r2 = 2;
+ *   *(u64 *)(r10 - 8)  = r1;            r1 = 1;
+ *   *(u64 *)(r10 - 16) = r2;            r2 = 2;
+ *   call %[to_be_inlined]         -->   call %[to_be_inlined]
+ *   r2 = *(u64 *)(r10 - 16);            r0 = r1;
+ *   r1 = *(u64 *)(r10 - 8);             r0 += r2;
+ *   r0 = r1;                            exit;
+ *   r0 += r2;
+ *   exit;
+ *
+ * The purpose of mark_nocsr_pattern_for_call is to:
+ * - look for such patterns;
+ * - mark spill and fill instructions in env->insn_aux_data[*].nocsr_pattern;
+ * - mark set env->insn_aux_data[*].nocsr_spills_num for call instruction;
+ * - update env->subprog_info[*]->nocsr_stack_off to find an offset
+ *   at which nocsr spill/fill stack slots start.
+ *
+ * The .nocsr_pattern and .nocsr_stack_off are used by
+ * check_nocsr_stack_contract() to check if every stack access to
+ * nocsr spill/fill stack slot originates from spill/fill
+ * instructions, members of nocsr patterns.
+ *
+ * If such condition holds true for a subprogram, nocsr patterns could
+ * be rewritten by do_misc_fixups().
+ * Otherwise nocsr patterns are not changed in the subprogram
+ * (code, presumably, generated by an older clang version).
+ *
+ * For example, it is *not* safe to remove spill/fill below:

kernel/bpf/verifier.c +5 -0

+       int s, i;
+       s16 off;
+
+       if (csr_mask == ALL_CALLER_SAVED_REGS)
+               return;

kernel/bpf/verifier.c +30 -0

+}
+
+/* Update the following fields when appropriate:
+ * - env->insn_aux_data[*].nocsr_pattern
+ * - env->insn_aux_data[*].spills_num and
+ * - env->subprog_info[*].nocsr_stack_off
+ * See mark_nocsr_pattern_for_call().
+ */
+static int mark_nocsr_patterns(struct bpf_verifier_env *env)
+{
+       struct bpf_insn *insn = env->prog->insnsi;
+       int i, insn_cnt = env->prog->len;
+
+       for (i = 0; i < insn_cnt; i++, insn++)
+               /* might be extended to handle kfuncs as well */
+               if (bpf_helper_call(insn))
+                       mark_nocsr_pattern_for_call(env, i);
+       return 0;
+}
+
 /* Visits the instruction at index t and returns one of the following:
  *  < 0 - an error occurred
  *  DONE_EXPLORING - the instruction was fully explored

@@ -20119,6 +20361,48 @@ static int do_misc_fixups(struct bpf_verifier_env *env)
                        goto next_insn;
                if (insn->src_reg == BPF_PSEUDO_CALL)
                        goto next_insn;
+               /* Remove unnecessary spill/fill pairs, members of nocsr pattern */
+               if (env->insn_aux_data[i + delta].nocsr_spills_num > 0) {
+                       u32 j, spills_num = env->insn_aux_data[i + delta].nocsr_spills_num;
+                       int err;
+
+                       /* don't apply this on a second visit */
+                       env->insn_aux_data[i + delta].nocsr_spills_num = 0;
+
+                       /* check if spill/fill stack access is in expected offset range */
+                       for (j = 1; j <= spills_num; ++j) {

kernel/bpf/verifier.c +5 -1

+               }
                if (insn->src_reg == BPF_PSEUDO_KFUNC_CALL) {
                        ret = fixup_kfunc_call(env, insn, insn_buf, i + delta, &cnt);
                        if (ret)

@@ -21704,6 +21988,10 @@ int bpf_check(struct bpf_prog **prog, union bpf_attr *attr, bpfptr_t uattr, __u3
        if (ret < 0)
                goto skip_full_check;
 
+       ret = mark_nocsr_patterns(env);
+       if (ret < 0)
+               goto skip_full_check;
+
        ret = do_check_main(env);
        ret = ret ?: do_check_subprogs(env);
 
--

2.45.2

Quoted 6 lines

include/linux/bpf_verifier.h +0 -0

index 2b54e25d2364..735ae0901b3d 100644
@@ -585,6 +585,15 @@ struct bpf_insn_aux_data {
         * accepts callback function as a parameter.

include/linux/bpf_verifier.h struct bpf_insn_aux_data { · line 595

Quoted 10 lines

include/linux/bpf_verifier.h +8 -0

         */
        bool calls_callback;
+       /* true if STX or LDX instruction is a part of a spill/fill
+        * pattern for a no_caller_saved_registers call.
+        */
+       u8 nocsr_pattern:1;
+       /* for CALL instructions, a number of spill/fill pairs in the
+        * no_caller_saved_registers pattern.
+        */
+       u8 nocsr_spills_num:3;

despite bitfields this will extend bpf_insn_aux_data by 8 bytes. there are 2 bytes of padding after alu_state, let's put this there.

And let's not add bitfields unless absolutely necessary (this can be always done later).

Quoted 4 lines

include/linux/bpf_verifier.h +1 -0

+
 };
 

include/linux/bpf_verifier.h struct bpf_subprog_info { · line 655

Quoted 8 lines

include/linux/bpf_verifier.h +3 -0

 #define MAX_USED_MAPS 64 /* max number of maps accessed by one eBPF program */

@@ -641,6 +650,11 @@ struct bpf_subprog_info {
        u32 linfo_idx; /* The idx to the main_prog->aux->linfo */
        u16 stack_depth; /* max. stack depth used by this function */
        u16 stack_extra;
+       /* stack depth after which slots reserved for
+        * no_caller_saved_registers spills/fills start,
+        * value <= nocsr_stack_off belongs to the spill/fill area.

are you sure about <= (not <), it seems like nocsr_stack_off is exclusive right bound for nocsr stack region (it would be good to call this out explicitly here)

Quoted 29 lines

include/linux/bpf_verifier.h +2 -0

+        */
+       s16 nocsr_stack_off;
        bool has_tail_call: 1;
        bool tail_call_reachable: 1;
        bool has_ld_abs: 1;

kernel/bpf/verifier.c +5 -6

index 4869f1fb0a42..d16a249b59ad 100644
@@ -2471,16 +2471,37 @@ static int cmp_subprogs(const void *a, const void *b)
               ((struct bpf_subprog_info *)b)->start;
 }
 
-static int find_subprog(struct bpf_verifier_env *env, int off)
+/* Find subprogram that contains instruction at 'off' */
+static int find_containing_subprog(struct bpf_verifier_env *env, int off)
 {
-       struct bpf_subprog_info *p;
+       struct bpf_subprog_info *vals = env->subprog_info;
+       int l, r, m;
 
-       p = bsearch(&off, env->subprog_info, env->subprog_cnt,
-                   sizeof(env->subprog_info[0]), cmp_subprogs);
-       if (!p)
+       if (off >= env->prog->len || off < 0 || env->subprog_cnt == 0)
                return -ENOENT;
-       return p - env->subprog_info;
 

kernel/bpf/verifier.c static int cmp_subprogs(const void *a, const void *b) · line 2484

Quoted 2 lines

kernel/bpf/verifier.c +2 -0

+       l = 0;
+       m = 0;

no need to initialize m

kernel/bpf/verifier.c static int cmp_subprogs(const void *a, const void *b) · line 2494

Quoted 11 lines

kernel/bpf/verifier.c +10 -0

+       r = env->subprog_cnt - 1;
+       while (l < r) {
+               m = l + (r - l + 1) / 2;
+               if (vals[m].start <= off)
+                       l = m;
+               else
+                       r = m - 1;
+       }
+       return l;
+}

I love it, looks great :)

Quoted 4 lines

kernel/bpf/verifier.c +0 -0

@@ -4501,6 +4522,23 @@ static int get_reg_width(struct bpf_reg_state *reg)
        return fls64(reg->umax_value);
 }
 

kernel/bpf/verifier.c static int get_reg_width(struct bpf_reg_state *reg) · line 4533

Quoted 9 lines

kernel/bpf/verifier.c +9 -0

+/* See comment for mark_nocsr_pattern_for_call() */
+static void check_nocsr_stack_contract(struct bpf_verifier_env *env, struct bpf_func_state *state,
+                                      int insn_idx, int off)
+{
+       struct bpf_subprog_info *subprog = &env->subprog_info[state->subprogno];
+       struct bpf_insn_aux_data *aux = &env->insn_aux_data[insn_idx];
+
+       if (subprog->nocsr_stack_off <= off || aux->nocsr_pattern)
+               return;

can helper call instruction go through this check? E.g., if we do bpf_probe_read_kernel() into stack slot, where do we check that that slot is not overlapping with nocsr spill/fill region?

Quoted 14 lines

kernel/bpf/verifier.c +10 -0

@@ -15951,6 +15993,206 @@ static int visit_func_call_insn(int t, struct bpf_insn *insns,
        return ret;
 }
 
+/* Bitmask with 1s for all caller saved registers */
+#define ALL_CALLER_SAVED_REGS ((1u << CALLER_SAVED_REGS) - 1)
+
+/* Return a bitmask specifying which caller saved registers are
+ * modified by a call to a helper.
+ * (Either as a return value or as scratch registers).
+ *
+ * For normal helpers registers R0-R5 are scratched.
+ * For helpers marked as no_csr:
+ * - scratch R0 if function is non-void;

kernel/bpf/verifier.c static int visit_func_call_insn(int t, struct bpf_insn *insns, · line 16009

Quoted 4 lines

kernel/bpf/verifier.c +4 -0

+ * - scratch R1-R5 if corresponding parameter type is set
+ *   in the function prototype.
+ */
+static u8 get_helper_reg_mask(const struct bpf_func_proto *fn)

suggestion: to make this less confusing, here we are returning a mask of registers that are clobbered by the helper, is that right? so get_helper_clobber_mask() maybe?

kernel/bpf/verifier.c static int visit_func_call_insn(int t, struct bpf_insn *insns, · line 16038

Quoted 4 lines

kernel/bpf/verifier.c +4 -0

+/* If 'insn' is a call that follows no_caller_saved_registers contract
+ * and called function is inlined by current jit or verifier,
+ * return a mask with 1s corresponding to registers that are scratched
+ * by this call (depends on return type and number of return parameters).

return parameters? was it supposed to be "function parameters/arguments"?

kernel/bpf/verifier.c static int visit_func_call_insn(int t, struct bpf_insn *insns, · line 16041

Quoted 4 lines

kernel/bpf/verifier.c +3 -0

+ * Otherwise return ALL_CALLER_SAVED_REGS mask.
+ */
+static u32 call_csr_mask(struct bpf_verifier_env *env, struct bpf_insn *insn)

you use u8 for get_helper_reg_mask() and u32 here, why not keep them consistent?

similar to the naming nit above, I think we should be a bit more explicit with what "mask" actually means. Is this also clobber mask?

kernel/bpf/verifier.c static int visit_func_call_insn(int t, struct bpf_insn *insns, · line 16049

Quoted 9 lines

kernel/bpf/verifier.c +8 -0

+{
+       const struct bpf_func_proto *fn;
+
+       if (bpf_helper_call(insn) &&
+           (verifier_inlines_helper_call(env, insn->imm) || bpf_jit_inlines_helper_call(insn->imm)) &&
+           get_helper_proto(env, insn->imm, &fn) == 0 &&
+           fn->allow_nocsr)
+               return ~get_helper_reg_mask(fn);

hm... I'm a bit confused why we do a negation here? aren't we working with clobbering mask... I'll keep reading for now.

Quoted 4 lines

kernel/bpf/verifier.c +3 -0

+
+       return ALL_CALLER_SAVED_REGS;
+}

Quoted 1 line

+static void mark_nocsr_pattern_for_call(struct bpf_verifier_env *env, int t)

t is insn_idx, let's not carry over old crufty check_cfg naming

kernel/bpf/verifier.c static int visit_func_call_insn(int t, struct bpf_insn *insns, · line 16133

Quoted 6 lines

kernel/bpf/verifier.c +5 -0

+{
+       struct bpf_insn *insns = env->prog->insnsi, *stx, *ldx;
+       struct bpf_subprog_info *subprog;
+       u32 csr_mask = call_csr_mask(env, &insns[t]);
+       u32 reg_mask = ~csr_mask | ~ALL_CALLER_SAVED_REGS;

tbh, I'm lost with all these bitmask and their inversions... call_csr_mask()'s result is basically always used inverted, so why not return inverted mask in the first place?

Quoted 12 lines

kernel/bpf/verifier.c +11 -0

+       int s, i;
+       s16 off;
+
+       if (csr_mask == ALL_CALLER_SAVED_REGS)
+               return;
+
+       for (i = 1, off = 0; i <= ARRAY_SIZE(caller_saved); ++i, off += BPF_REG_SIZE) {
+               if (t - i < 0 || t + i >= env->prog->len)
+                       break;
+               stx = &insns[t - i];
+               ldx = &insns[t + i];

kernel/bpf/verifier.c static int visit_func_call_insn(int t, struct bpf_insn *insns, · line 16148

Quoted 4 lines

kernel/bpf/verifier.c +4 -0

+               if (off == 0) {
+                       off = stx->off;
+                       if (off % BPF_REG_SIZE != 0)
+                               break;

kind of ugly that we assume stx before we actually checked that it's STX?... maybe split humongous if below into instruction checking (with code and src_reg) and then off checking separately?

Quoted 4 lines

kernel/bpf/verifier.c +3 -0

+               }
+               if (/* *(u64 *)(r10 - off) = r[0-5]? */
+                   stx->code != (BPF_STX | BPF_MEM | BPF_DW) ||

kernel/bpf/verifier.c static int visit_func_call_insn(int t, struct bpf_insn *insns, · line 16161

Quoted 10 lines

kernel/bpf/verifier.c +10 -0

+                   stx->dst_reg != BPF_REG_10 ||
+                   /* r[0-5] = *(u64 *)(r10 - off)? */
+                   ldx->code != (BPF_LDX | BPF_MEM | BPF_DW) ||
+                   ldx->src_reg != BPF_REG_10 ||
+                   /* check spill/fill for the same reg and offset */
+                   stx->src_reg != ldx->dst_reg ||
+                   stx->off != ldx->off ||
+                   stx->off != off ||
+                   /* this should be a previously unseen register */
+                   BIT(stx->src_reg) & reg_mask)

() around & operation?

kernel/bpf/verifier.c static int visit_func_call_insn(int t, struct bpf_insn *insns, · line 16171

Quoted 11 lines

kernel/bpf/verifier.c +10 -0

+                       break;
+               reg_mask |= BIT(stx->src_reg);
+               env->insn_aux_data[t - i].nocsr_pattern = 1;
+               env->insn_aux_data[t + i].nocsr_pattern = 1;
+       }
+       if (i == 1)
+               return;
+       env->insn_aux_data[t].nocsr_spills_num = i - 1;
+       s = find_containing_subprog(env, t);
+       /* can't happen */

then don't check ;) we leave the state partially set for CSR but not quite. We either should error out completely or just assume correctness of find_containing_subprog, IMO

kernel/bpf/verifier.c static int visit_func_call_insn(int t, struct bpf_insn *insns, · line 16175

Quoted 5 lines

kernel/bpf/verifier.c +4 -0

+       if (WARN_ON_ONCE(s < 0))
+               return;
+       subprog = &env->subprog_info[s];
+       subprog->nocsr_stack_off = min(subprog->nocsr_stack_off, off);

should this be max()? offsets are negative, right? so if nocsr uses -8 and -16 as in the example, entire [-16, 0) region is nocsr region

Quoted 2 lines

+}

Quoted 19 lines

kernel/bpf/verifier.c +15 -0

@@ -20119,6 +20361,48 @@ static int do_misc_fixups(struct bpf_verifier_env *env)
                        goto next_insn;
                if (insn->src_reg == BPF_PSEUDO_CALL)
                        goto next_insn;
+               /* Remove unnecessary spill/fill pairs, members of nocsr pattern */
+               if (env->insn_aux_data[i + delta].nocsr_spills_num > 0) {
+                       u32 j, spills_num = env->insn_aux_data[i + delta].nocsr_spills_num;
+                       int err;
+
+                       /* don't apply this on a second visit */
+                       env->insn_aux_data[i + delta].nocsr_spills_num = 0;
+
+                       /* check if spill/fill stack access is in expected offset range */
+                       for (j = 1; j <= spills_num; ++j) {
+                               if ((insn - j)->off >= subprogs[cur_subprog].nocsr_stack_off ||
+                                   (insn + j)->off >= subprogs[cur_subprog].nocsr_stack_off) {
+                                       /* do a second visit of this instruction,
+                                        * so that verifier can inline it
+                                        */

kernel/bpf/verifier.c static int do_misc_fixups(struct bpf_verifier_env *env) · line 20383

Quoted 5 lines

kernel/bpf/verifier.c +5 -0

+                                       i -= 1;
+                                       insn -= 1;
+                                       goto next_insn;
+                               }
+                       }

I don't get this loop, can you elaborate? Why are we double-checking anything here, didn't we do this already?

kernel/bpf/verifier.c static int do_misc_fixups(struct bpf_verifier_env *env) · line 20395

Quoted 13 lines

kernel/bpf/verifier.c +12 -0

+
+                       /* apply the rewrite:
+                        *   *(u64 *)(r10 - X) = rY ; num-times
+                        *   call()                               -> call()
+                        *   rY = *(u64 *)(r10 - X) ; num-times
+                        */
+                       err = verifier_remove_insns(env, i + delta - spills_num, spills_num);
+                       if (err)
+                               return err;
+                       err = verifier_remove_insns(env, i + delta - spills_num + 1, spills_num);
+                       if (err)
+                               return err;

why not a single bpf_patch_insn_data()?

kernel/bpf/verifier.c static int do_misc_fixups(struct bpf_verifier_env *env) · line 20404

Quoted 9 lines

kernel/bpf/verifier.c +9 -0

+
+                       i += spills_num - 1;
+                       /*   ^            ^   do a second visit of this instruction,
+                        *   |            '-- so that verifier can inline it
+                        *   '--------------- jump over deleted fills
+                        */
+                       delta -= 2 * spills_num;
+                       insn = env->prog->insnsi + i + delta;
+                       goto next_insn;

why not adjust the state and just fall through, what goto next_insn does that we can't (and next instruction is misleading, so I'd rather fix up and move forward)

Quoted 5 lines

kernel/bpf/verifier.c +1 -0

+               }
                if (insn->src_reg == BPF_PSEUDO_KFUNC_CALL) {
                        ret = fixup_kfunc_call(env, insn, insn_buf, i + delta, &cnt);
                        if (ret)

On Tue, 2024-07-09 at 16:42 -0700, Andrii Nakryiko wrote:

[...]

Quoted 4 lines

Quoted 4 lines

+
};

Quoted 12 lines

include/linux/bpf_verifier.h struct bpf_subprog_info { · line 655

Quoted 8 lines

#define MAX_USED_MAPS 64 /* max number of maps accessed by one eBPF program */

include/linux/bpf_verifier.h +3 -0

@@ -641,6 +650,11 @@ struct bpf_subprog_info {
        u32 linfo_idx; /* The idx to the main_prog->aux->linfo */
        u16 stack_depth; /* max. stack depth used by this function */
        u16 stack_extra;
+       /* stack depth after which slots reserved for
+        * no_caller_saved_registers spills/fills start,
+        * value <= nocsr_stack_off belongs to the spill/fill area.

are you sure about <= (not <), it seems like nocsr_stack_off is exclusive right bound for nocsr stack region (it would be good to call this out explicitly here)

Right, it should be '<', my bad, will update the comment.

Quoted 5 lines

Quoted 5 lines

kernel/bpf/verifier.c +0 -0

@@ -4501,6 +4522,23 @@ static int get_reg_width(struct bpf_reg_state *reg)
        return fls64(reg->umax_value);
 }
 

Quoted 13 lines

kernel/bpf/verifier.c static int get_reg_width(struct bpf_reg_state *reg) · line 4533

Quoted 9 lines

kernel/bpf/verifier.c +9 -0

+/* See comment for mark_nocsr_pattern_for_call() */
+static void check_nocsr_stack_contract(struct bpf_verifier_env *env, struct bpf_func_state *state,
+                                      int insn_idx, int off)
+{
+       struct bpf_subprog_info *subprog = &env->subprog_info[state->subprogno];
+       struct bpf_insn_aux_data *aux = &env->insn_aux_data[insn_idx];
+
+       if (subprog->nocsr_stack_off <= off || aux->nocsr_pattern)
+               return;

can helper call instruction go through this check? E.g., if we do bpf_probe_read_kernel() into stack slot, where do we check that that slot is not overlapping with nocsr spill/fill region?

In check_helper_call() we do check_mem_access() that eventually calls one of the check_stack_{read,write}_{fixed,varying}_off(). The .access_size should be set for bpf_probe_read_kernel() because it's argument base type is ARG_PTR_TO_MEM.
I will add a test case to double-check this.

[...]

Quoted 14 lines

Quoted 14 lines

kernel/bpf/verifier.c +10 -0

@@ -15951,6 +15993,206 @@ static int visit_func_call_insn(int t, struct bpf_insn *insns,
        return ret;
 }
 
+/* Bitmask with 1s for all caller saved registers */
+#define ALL_CALLER_SAVED_REGS ((1u << CALLER_SAVED_REGS) - 1)
+
+/* Return a bitmask specifying which caller saved registers are
+ * modified by a call to a helper.
+ * (Either as a return value or as scratch registers).
+ *
+ * For normal helpers registers R0-R5 are scratched.
+ * For helpers marked as no_csr:
+ * - scratch R0 if function is non-void;

Quoted 8 lines

kernel/bpf/verifier.c static int visit_func_call_insn(int t, struct bpf_insn *insns, · line 16009

Quoted 4 lines

kernel/bpf/verifier.c +4 -0

+ * - scratch R1-R5 if corresponding parameter type is set
+ *   in the function prototype.
+ */
+static u8 get_helper_reg_mask(const struct bpf_func_proto *fn)

suggestion: to make this less confusing, here we are returning a mask of registers that are clobbered by the helper, is that right? so get_helper_clobber_mask() maybe?

get_helper_clobber_mask() is a good name, will change.

[...]

Quoted 6 lines

kernel/bpf/verifier.c static int visit_func_call_insn(int t, struct bpf_insn *insns, · line 16038

Quoted 4 lines

kernel/bpf/verifier.c +4 -0

+/* If 'insn' is a call that follows no_caller_saved_registers contract
+ * and called function is inlined by current jit or verifier,
+ * return a mask with 1s corresponding to registers that are scratched
+ * by this call (depends on return type and number of return parameters).

return parameters? was it supposed to be "function parameters/arguments"?

My bad.

Quoted 6 lines

kernel/bpf/verifier.c static int visit_func_call_insn(int t, struct bpf_insn *insns, · line 16041

Quoted 4 lines

kernel/bpf/verifier.c +3 -0

+ * Otherwise return ALL_CALLER_SAVED_REGS mask.
+ */
+static u32 call_csr_mask(struct bpf_verifier_env *env, struct bpf_insn *insn)

you use u8 for get_helper_reg_mask() and u32 here, why not keep them consistent?

Ok

Quoted 2 lines

similar to the naming nit above, I think we should be a bit more explicit with what "mask" actually means. Is this also clobber mask?

I mean, there is a comment right above the function. This function returns a mask of caller saved registers (csr). I'll make the name more explicit.

Quoted 12 lines

kernel/bpf/verifier.c static int visit_func_call_insn(int t, struct bpf_insn *insns, · line 16049

Quoted 9 lines

kernel/bpf/verifier.c +8 -0

+{
+       const struct bpf_func_proto *fn;
+
+       if (bpf_helper_call(insn) &&
+           (verifier_inlines_helper_call(env, insn->imm) || bpf_jit_inlines_helper_call(insn->imm)) &&
+           get_helper_proto(env, insn->imm, &fn) == 0 &&
+           fn->allow_nocsr)
+               return ~get_helper_reg_mask(fn);

hm... I'm a bit confused why we do a negation here? aren't we working with clobbering mask... I'll keep reading for now.

Please read the comment before the function.

Quoted 4 lines

Quoted 4 lines

kernel/bpf/verifier.c +3 -0

+
+       return ALL_CALLER_SAVED_REGS;
+}

[...]

Quoted 3 lines

Quoted 1 line

+static void mark_nocsr_pattern_for_call(struct bpf_verifier_env *env, int t)

t is insn_idx, let's not carry over old crufty check_cfg naming

Ok

Quoted 7 lines

Quoted 6 lines

kernel/bpf/verifier.c +5 -0

+{
+       struct bpf_insn *insns = env->prog->insnsi, *stx, *ldx;
+       struct bpf_subprog_info *subprog;
+       u32 csr_mask = call_csr_mask(env, &insns[t]);
+       u32 reg_mask = ~csr_mask | ~ALL_CALLER_SAVED_REGS;

Quoted 3 lines

tbh, I'm lost with all these bitmask and their inversions... call_csr_mask()'s result is basically always used inverted, so why not return inverted mask in the first place?

The mask is initialized as a set of all registers preserved by this call.

Those that are not in mask need a spill/fill pair.
I'll toss things around to make this more clear.
(naming, comments, maybe move the '| ~ALL_CALLER_SAVED_REGS' to the call_csr_mask()).

Quoted 12 lines

Quoted 12 lines

kernel/bpf/verifier.c +11 -0

+       int s, i;
+       s16 off;
+
+       if (csr_mask == ALL_CALLER_SAVED_REGS)
+               return;
+
+       for (i = 1, off = 0; i <= ARRAY_SIZE(caller_saved); ++i, off += BPF_REG_SIZE) {
+               if (t - i < 0 || t + i >= env->prog->len)
+                       break;
+               stx = &insns[t - i];
+               ldx = &insns[t + i];

Quoted 8 lines

kernel/bpf/verifier.c static int visit_func_call_insn(int t, struct bpf_insn *insns, · line 16148

Quoted 4 lines

kernel/bpf/verifier.c +4 -0

+               if (off == 0) {
+                       off = stx->off;
+                       if (off % BPF_REG_SIZE != 0)
+                               break;

kind of ugly that we assume stx before we actually checked that it's STX?... maybe split humongous if below into instruction checking (with code and src_reg) and then off checking separately?

Don't see anything ugly about this, tbh.

Can split the 'if' statement, if you think it's hard to read.

Quoted 16 lines

Quoted 15 lines

kernel/bpf/verifier.c +13 -0

+               }
+               if (/* *(u64 *)(r10 - off) = r[0-5]? */
+                   stx->code != (BPF_STX | BPF_MEM | BPF_DW) ||
+                   stx->dst_reg != BPF_REG_10 ||
+                   /* r[0-5] = *(u64 *)(r10 - off)? */
+                   ldx->code != (BPF_LDX | BPF_MEM | BPF_DW) ||
+                   ldx->src_reg != BPF_REG_10 ||
+                   /* check spill/fill for the same reg and offset */
+                   stx->src_reg != ldx->dst_reg ||
+                   stx->off != ldx->off ||
+                   stx->off != off ||
+                   /* this should be a previously unseen register */
+                   BIT(stx->src_reg) & reg_mask)

Quoted 1 line

() around & operation?

No need, & has higher priority over ||.
You can check the AST using
https://tree-sitter.github.io/tree-sitter/playground .

Quoted 13 lines

kernel/bpf/verifier.c static int visit_func_call_insn(int t, struct bpf_insn *insns, · line 16171

Quoted 12 lines

kernel/bpf/verifier.c +10 -0

+                       break;
+               reg_mask |= BIT(stx->src_reg);
+               env->insn_aux_data[t - i].nocsr_pattern = 1;
+               env->insn_aux_data[t + i].nocsr_pattern = 1;
+       }
+       if (i == 1)
+               return;
+       env->insn_aux_data[t].nocsr_spills_num = i - 1;
+       s = find_containing_subprog(env, t);
+       /* can't happen */

Quoted 3 lines

then don't check ;) we leave the state partially set for CSR but not quite. We either should error out completely or just assume correctness of find_containing_subprog, IMO

Ok

Quoted 6 lines

Quoted 5 lines

kernel/bpf/verifier.c +4 -0

+       if (WARN_ON_ONCE(s < 0))
+               return;
+       subprog = &env->subprog_info[s];
+       subprog->nocsr_stack_off = min(subprog->nocsr_stack_off, off);

Quoted 2 lines

should this be max()? offsets are negative, right? so if nocsr uses -8 and -16 as in the example, entire [-16, 0) region is nocsr region

This should be min exactly because stack offsets are negative. For the example above the 'off' is initialized as -16 and then is incremented by +8 giving final value of -8.
And I need to select the minimal value used between several patterns.

Quoted 3 lines

Quoted 3 lines

+}

[...]

Quoted 19 lines

Quoted 19 lines

kernel/bpf/verifier.c +15 -0

@@ -20119,6 +20361,48 @@ static int do_misc_fixups(struct bpf_verifier_env *env)
                        goto next_insn;
                if (insn->src_reg == BPF_PSEUDO_CALL)
                        goto next_insn;
+               /* Remove unnecessary spill/fill pairs, members of nocsr pattern */
+               if (env->insn_aux_data[i + delta].nocsr_spills_num > 0) {
+                       u32 j, spills_num = env->insn_aux_data[i + delta].nocsr_spills_num;
+                       int err;
+
+                       /* don't apply this on a second visit */
+                       env->insn_aux_data[i + delta].nocsr_spills_num = 0;
+
+                       /* check if spill/fill stack access is in expected offset range */
+                       for (j = 1; j <= spills_num; ++j) {
+                               if ((insn - j)->off >= subprogs[cur_subprog].nocsr_stack_off ||
+                                   (insn + j)->off >= subprogs[cur_subprog].nocsr_stack_off) {
+                                       /* do a second visit of this instruction,
+                                        * so that verifier can inline it
+                                        */

Quoted 8 lines

kernel/bpf/verifier.c static int do_misc_fixups(struct bpf_verifier_env *env) · line 20383

Quoted 5 lines

kernel/bpf/verifier.c +5 -0

+                                       i -= 1;
+                                       insn -= 1;
+                                       goto next_insn;
+                               }
+                       }

I don't get this loop, can you elaborate? Why are we double-checking anything here, didn't we do this already?

We established probable patterns and probable minimal offset. Over the course of program verification we might have invalidated the .nocsr_stack_off for a particular subprogram => hence a need for this check.

Quoted 15 lines

Quoted 14 lines

kernel/bpf/verifier.c +12 -0

+
+                       /* apply the rewrite:
+                        *   *(u64 *)(r10 - X) = rY ; num-times
+                        *   call()                               -> call()
+                        *   rY = *(u64 *)(r10 - X) ; num-times
+                        */
+                       err = verifier_remove_insns(env, i + delta - spills_num, spills_num);
+                       if (err)
+                               return err;
+                       err = verifier_remove_insns(env, i + delta - spills_num + 1, spills_num);
+                       if (err)
+                               return err;

Quoted 1 line

why not a single bpf_patch_insn_data()?

bpf_patch_insn_data() assumes that one instruction has to be replaced with many. Here I need to replace many instructions with a single instruction. I'd prefer not to tweak bpf_patch_insn_data() for this patch-set.

On the other hand, the do_jit() for x86 removes NOPs (BPF_JA +0), so I can probably replace spills/fills with NOPs here instead of calling bpf_patch_insn_data() or bpf_remove_insns().

Quoted 11 lines

kernel/bpf/verifier.c static int do_misc_fixups(struct bpf_verifier_env *env) · line 20404

Quoted 10 lines

kernel/bpf/verifier.c +9 -0

+
+                       i += spills_num - 1;
+                       /*   ^            ^   do a second visit of this instruction,
+                        *   |            '-- so that verifier can inline it
+                        *   '--------------- jump over deleted fills
+                        */
+                       delta -= 2 * spills_num;
+                       insn = env->prog->insnsi + i + delta;
+                       goto next_insn;

Quoted 3 lines

why not adjust the state and just fall through, what goto next_insn does that we can't (and next instruction is misleading, so I'd rather fix up and move forward)

I don't like this. The fall-through makes control flow more convoluted. To understand what would happen next:
- with goto next_insn we just start over;
- with fall-through we need to think about position of this particular 'if' statement within the loop.

Quoted 5 lines

Quoted 5 lines

kernel/bpf/verifier.c +1 -0

+               }
                if (insn->src_reg == BPF_PSEUDO_KFUNC_CALL) {
                        ret = fixup_kfunc_call(env, insn, insn_buf, i + delta, &cnt);
                        if (ret)

[...]

Quoted 1 line

Right, it should be '<', my bad, will update the comment.

See, I do read comments ;)

Quoted 14 lines

Quoted 5 lines

Quoted 5 lines

kernel/bpf/verifier.c +5 -0

+/* See comment for mark_nocsr_pattern_for_call() */
+static void check_nocsr_stack_contract(struct bpf_verifier_env *env, struct bpf_func_state *state,
+                                      int insn_idx, int off)
+{
+       struct bpf_subprog_info *subprog = &env->subprog_info[state->subprogno];

Quoted 8 lines

kernel/bpf/verifier.c static int get_reg_width(struct bpf_reg_state *reg) · line 4533

Quoted 4 lines

kernel/bpf/verifier.c +4 -0

+       struct bpf_insn_aux_data *aux = &env->insn_aux_data[insn_idx];
+
+       if (subprog->nocsr_stack_off <= off || aux->nocsr_pattern)
+               return;

can helper call instruction go through this check? E.g., if we do bpf_probe_read_kernel() into stack slot, where do we check that that slot is not overlapping with nocsr spill/fill region?

Quoted 5 lines

In check_helper_call() we do check_mem_access() that eventually calls one of the check_stack_{read,write}_{fixed,varying}_off(). The .access_size should be set for bpf_probe_read_kernel() because it's argument base type is ARG_PTR_TO_MEM.
I will add a test case to double-check this.

Ok. Also as I was reading this I didn't yet realize that aux->nocsr_pattern is not set for call instruction itself, so I was worried that we might accidentally skip the check. But we don't set nocsr_pattern for call, so we should be good (but the test never hurts)

Quoted 26 lines

Quoted 3 lines

Quoted 1 line

+static u32 call_csr_mask(struct bpf_verifier_env *env, struct bpf_insn *insn)

you use u8 for get_helper_reg_mask() and u32 here, why not keep them consistent?

Ok

Quoted 2 lines

similar to the naming nit above, I think we should be a bit more explicit with what "mask" actually means. Is this also clobber mask?

I mean, there is a comment right above the function. This function returns a mask of caller saved registers (csr). I'll make the name more explicit.

Quoted 12 lines

kernel/bpf/verifier.c static int visit_func_call_insn(int t, struct bpf_insn *insns, · line 16049

Quoted 9 lines

kernel/bpf/verifier.c +8 -0

+{
+       const struct bpf_func_proto *fn;
+
+       if (bpf_helper_call(insn) &&
+           (verifier_inlines_helper_call(env, insn->imm) || bpf_jit_inlines_helper_call(insn->imm)) &&
+           get_helper_proto(env, insn->imm, &fn) == 0 &&
+           fn->allow_nocsr)
+               return ~get_helper_reg_mask(fn);

hm... I'm a bit confused why we do a negation here? aren't we working with clobbering mask... I'll keep reading for now.

Quoted 2 lines

Please read the comment before the function.

Believe it or not, but I read it like 10 times and that didn't help me much.

+/* If 'insn' is a call that follows no_caller_saved_registers contract
+ * and called function is inlined by current jit or verifier,
+ * return a mask with 1s corresponding to registers that are scratched
+ * by this call (depends on return type and number of return parameters).
+ * Otherwise return ALL_CALLER_SAVED_REGS mask.

"registers that are scratched by this call" would be what get_helper_reg_mask() returns for the function (at least that's my reading of the above), and yet you return inverted mask. It doesn't really help that we return ALL_CALLER_SAVED_REGS as "nope, it's not nocsr call".

Maybe it would be a bit easier to follow if call_csr_mask() returned bool and mask as an out parameter in case it's nocsr call. So instead of special casing ALL_CALLER_SAVED_REGS there would be a nice "not a nocsr, never mind" and early exit.

Anyways, perhaps I'm just being very dense here, I just found this particular piece extremely hard to follow intuitively.

Quoted 18 lines

Quoted 4 lines

Quoted 4 lines

kernel/bpf/verifier.c +3 -0

+
+       return ALL_CALLER_SAVED_REGS;
+}

[...]

Quoted 10 lines

kernel/bpf/verifier.c static int visit_func_call_insn(int t, struct bpf_insn *insns, · line 16133

Quoted 6 lines

kernel/bpf/verifier.c +6 -0

+static void mark_nocsr_pattern_for_call(struct bpf_verifier_env *env, int t)
+{
+       struct bpf_insn *insns = env->prog->insnsi, *stx, *ldx;
+       struct bpf_subprog_info *subprog;
+       u32 csr_mask = call_csr_mask(env, &insns[t]);
+       u32 reg_mask = ~csr_mask | ~ALL_CALLER_SAVED_REGS;

tbh, I'm lost with all these bitmask and their inversions... call_csr_mask()'s result is basically always used inverted, so why not return inverted mask in the first place?

Quoted 1 line

The mask is initialized as a set of all registers preserved by this call.

ok, maybe it's just a mix of "no csr" and "csr" that confuses me. How about we call call_csr_mask as get_helper_preserved_mask() or something like that to "match" get_helper_clobber_mask()?

Quoted 25 lines

Those that are not in mask need a spill/fill pair.
I'll toss things around to make this more clear.
(naming, comments, maybe move the '| ~ALL_CALLER_SAVED_REGS' to the call_csr_mask()).

Quoted 20 lines

Quoted 6 lines

kernel/bpf/verifier.c +5 -0

+       int s, i;
+       s16 off;
+
+       if (csr_mask == ALL_CALLER_SAVED_REGS)
+               return;

kernel/bpf/verifier.c static int visit_func_call_insn(int t, struct bpf_insn *insns, · line 16148

Quoted 10 lines

kernel/bpf/verifier.c +10 -0

+
+       for (i = 1, off = 0; i <= ARRAY_SIZE(caller_saved); ++i, off += BPF_REG_SIZE) {
+               if (t - i < 0 || t + i >= env->prog->len)
+                       break;
+               stx = &insns[t - i];
+               ldx = &insns[t + i];
+               if (off == 0) {
+                       off = stx->off;
+                       if (off % BPF_REG_SIZE != 0)
+                               break;

kind of ugly that we assume stx before we actually checked that it's STX?... maybe split humongous if below into instruction checking (with code and src_reg) and then off checking separately?

Quoted 1 line

Don't see anything ugly about this, tbh.

you are using stx->off and do % BPF_REG_SIZE check on it while that stx->off field might be meaningless for the instruction (because we are not yet sure it's STX instruction), that's a bit ugly, IMO

Quoted 2 lines

Can split the 'if' statement, if you think it's hard to read.

it's not about readability for me

Quoted 16 lines

Quoted 16 lines

Quoted 15 lines

kernel/bpf/verifier.c +13 -0

+               }
+               if (/* *(u64 *)(r10 - off) = r[0-5]? */
+                   stx->code != (BPF_STX | BPF_MEM | BPF_DW) ||
+                   stx->dst_reg != BPF_REG_10 ||
+                   /* r[0-5] = *(u64 *)(r10 - off)? */
+                   ldx->code != (BPF_LDX | BPF_MEM | BPF_DW) ||
+                   ldx->src_reg != BPF_REG_10 ||
+                   /* check spill/fill for the same reg and offset */
+                   stx->src_reg != ldx->dst_reg ||
+                   stx->off != ldx->off ||
+                   stx->off != off ||
+                   /* this should be a previously unseen register */
+                   BIT(stx->src_reg) & reg_mask)

Quoted 5 lines

Quoted 1 line

() around & operation?

No need, & has higher priority over ||.
You can check the AST using
https://tree-sitter.github.io/tree-sitter/playground .

Oh, I have no doubt you checked that it works correctly. It's just not a really good habit to rely on C's obscure operation ordering rules beyond A && B || C (and even then it is arguable). I think the rule of thumb to not mix bitwise and logic operators without explicit parenthesis makes sense.

But never mind, I already feel weird complaining about !strcmp(), every real kernel engineer should memorize operator precedence by heart.

Quoted 10 lines

Quoted 10 lines

Quoted 10 lines

kernel/bpf/verifier.c +10 -0

+                       break;
+               reg_mask |= BIT(stx->src_reg);
+               env->insn_aux_data[t - i].nocsr_pattern = 1;
+               env->insn_aux_data[t + i].nocsr_pattern = 1;
+       }
+       if (i == 1)
+               return;
+       env->insn_aux_data[t].nocsr_spills_num = i - 1;
+       s = find_containing_subprog(env, t);
+       /* can't happen */

Quoted 5 lines

Quoted 5 lines

Quoted 4 lines

kernel/bpf/verifier.c +4 -0

+       if (WARN_ON_ONCE(s < 0))
+               return;
+       subprog = &env->subprog_info[s];
+       subprog->nocsr_stack_off = min(subprog->nocsr_stack_off, off);

Quoted 7 lines

Quoted 2 lines

should this be max()? offsets are negative, right? so if nocsr uses -8 and -16 as in the example, entire [-16, 0) region is nocsr region

This should be min exactly because stack offsets are negative. For the example above the 'off' is initialized as -16 and then is incremented by +8 giving final value of -8.
And I need to select the minimal value used between several patterns.

so let's say I have two nocsr calls in the same subprog

    *(u64 *)(r10 - 8)  = r1;
    *(u64 *)(r10 - 16) = r2;
    call %[to_be_inlined]
    r2 = *(u64 *)(r10 - 16);
    r1 = *(u64 *)(r10 - 8);

and then a bit later

    *(u64 *)(r10 - 16)  = r1;
    *(u64 *)(r10 - 24) = r2;
    call %[to_be_inlined]
    r2 = *(u64 *)(r10 - 24);
    r1 = *(u64 *)(r10 - 16);

For the first chunk nocsr range is [-16, 0). For the second it's [-24, -8), right?
Should *(u64 *)(r10 - 8) = 123 somewhere in that subprog (not for nocsr calls) invalidate this whole nocsr thing? With min you'll basically have [-24, -8) as nocsr-reserved region, but shouldn't it be whole [-24, 0)?

Clang shouldn't generate such inconsistent offset, right? But it's legal, no? And if not, then all the calls should use the same upper stack boundary and we shouldn't be doing min/max, but rather checking that they are all consistent.

Or what am I missing again?

Quoted 15 lines

Quoted 14 lines

kernel/bpf/verifier.c static int do_misc_fixups(struct bpf_verifier_env *env) · line 20395

Quoted 12 lines

kernel/bpf/verifier.c +12 -0

+
+                       /* apply the rewrite:
+                        *   *(u64 *)(r10 - X) = rY ; num-times
+                        *   call()                               -> call()
+                        *   rY = *(u64 *)(r10 - X) ; num-times
+                        */
+                       err = verifier_remove_insns(env, i + delta - spills_num, spills_num);
+                       if (err)
+                               return err;
+                       err = verifier_remove_insns(env, i + delta - spills_num + 1, spills_num);
+                       if (err)
+                               return err;

why not a single bpf_patch_insn_data()?

Quoted 3 lines

bpf_patch_insn_data() assumes that one instruction has to be replaced with many. Here I need to replace many instructions with a single instruction. I'd prefer not to tweak bpf_patch_insn_data() for this patch-set.

ah, bpf_patch_insn_data just does bpf_patch_insn_single, somehow I thought that it does range for range replacement of instructions. Never mind then (it's a bit sad that we don't have a proper flexible and powerful patching primitive, though, but oh well).

Quoted 14 lines

Quoted 10 lines

kernel/bpf/verifier.c static int do_misc_fixups(struct bpf_verifier_env *env) · line 20404

Quoted 9 lines

kernel/bpf/verifier.c +9 -0

+
+                       i += spills_num - 1;
+                       /*   ^            ^   do a second visit of this instruction,
+                        *   |            '-- so that verifier can inline it
+                        *   '--------------- jump over deleted fills
+                        */
+                       delta -= 2 * spills_num;
+                       insn = env->prog->insnsi + i + delta;
+                       goto next_insn;

Quoted 3 lines

why not adjust the state and just fall through, what goto next_insn does that we can't (and next instruction is misleading, so I'd rather fix up and move forward)

Quoted 6 lines

I don't like this. The fall-through makes control flow more convoluted. To understand what would happen next:
- with goto next_insn we just start over;
- with fall-through we need to think about position of this particular 'if' statement within the loop.

Alright, it's fine. Though I don't see anything wrong with knowing that we patch up nocsr pattern before we do inlining of calls. And yes, order is important, so what? I always assumed that the order of operations in do_misc_fixups() is not arbitrary.

On Tue, 2024-07-09 at 23:01 -0700, Andrii Nakryiko wrote:

[...]

Quoted 3 lines

Quoted 1 line

Right, it should be '<', my bad, will update the comment.

See, I do read comments ;)

Yes, sorry about that remark.

[...]

Quoted 20 lines

Quoted 14 lines

Quoted 5 lines

Quoted 5 lines

kernel/bpf/verifier.c +5 -0

+/* See comment for mark_nocsr_pattern_for_call() */
+static void check_nocsr_stack_contract(struct bpf_verifier_env *env, struct bpf_func_state *state,
+                                      int insn_idx, int off)
+{
+       struct bpf_subprog_info *subprog = &env->subprog_info[state->subprogno];

Quoted 8 lines

kernel/bpf/verifier.c static int get_reg_width(struct bpf_reg_state *reg) · line 4533

Quoted 4 lines

kernel/bpf/verifier.c +4 -0

+       struct bpf_insn_aux_data *aux = &env->insn_aux_data[insn_idx];
+
+       if (subprog->nocsr_stack_off <= off || aux->nocsr_pattern)
+               return;

can helper call instruction go through this check? E.g., if we do bpf_probe_read_kernel() into stack slot, where do we check that that slot is not overlapping with nocsr spill/fill region?

Quoted 5 lines

In check_helper_call() we do check_mem_access() that eventually calls one of the check_stack_{read,write}_{fixed,varying}_off(). The .access_size should be set for bpf_probe_read_kernel() because it's argument base type is ARG_PTR_TO_MEM.
I will add a test case to double-check this.

Quoted 5 lines

Ok. Also as I was reading this I didn't yet realize that aux->nocsr_pattern is not set for call instruction itself, so I was worried that we might accidentally skip the check. But we don't set nocsr_pattern for call, so we should be good (but the test never hurts)

Well yes, there is a flag check, but call to bpf_probe_read_kernel() touching candidate nocsr stack address should disable nocsr rewrites for current subprogram.

[...]

Quoted 37 lines

Quoted 26 lines

Quoted 3 lines

Quoted 1 line

+static u32 call_csr_mask(struct bpf_verifier_env *env, struct bpf_insn *insn)

you use u8 for get_helper_reg_mask() and u32 here, why not keep them consistent?

Ok

Quoted 2 lines

similar to the naming nit above, I think we should be a bit more explicit with what "mask" actually means. Is this also clobber mask?

I mean, there is a comment right above the function. This function returns a mask of caller saved registers (csr). I'll make the name more explicit.

Quoted 12 lines

kernel/bpf/verifier.c static int visit_func_call_insn(int t, struct bpf_insn *insns, · line 16049

Quoted 9 lines

kernel/bpf/verifier.c +8 -0

+{
+       const struct bpf_func_proto *fn;
+
+       if (bpf_helper_call(insn) &&
+           (verifier_inlines_helper_call(env, insn->imm) || bpf_jit_inlines_helper_call(insn->imm)) &&
+           get_helper_proto(env, insn->imm, &fn) == 0 &&
+           fn->allow_nocsr)
+               return ~get_helper_reg_mask(fn);

hm... I'm a bit confused why we do a negation here? aren't we working with clobbering mask... I'll keep reading for now.

Quoted 2 lines

Please read the comment before the function.

Believe it or not, but I read it like 10 times and that didn't help me much.

+/* If 'insn' is a call that follows no_caller_saved_registers contract
+ * and called function is inlined by current jit or verifier,
+ * return a mask with 1s corresponding to registers that are scratched
+ * by this call (depends on return type and number of return parameters).
+ * Otherwise return ALL_CALLER_SAVED_REGS mask.

Quoted 5 lines

"registers that are scratched by this call" would be what get_helper_reg_mask() returns for the function (at least that's my reading of the above), and yet you return inverted mask. It doesn't really help that we return ALL_CALLER_SAVED_REGS as "nope, it's not nocsr call".

I see, I messed up the comment...

Quoted 4 lines

Maybe it would be a bit easier to follow if call_csr_mask() returned bool and mask as an out parameter in case it's nocsr call. So instead of special casing ALL_CALLER_SAVED_REGS there would be a nice "not a nocsr, never mind" and early exit.

Out parameter seems to be an overkill. I'll change names a little bit to make it easier to follow. If for v3 you'd still think that out parameter is better I'll switch then.

Quoted 24 lines

Anyways, perhaps I'm just being very dense here, I just found this particular piece extremely hard to follow intuitively.

Quoted 19 lines

Quoted 4 lines

Quoted 4 lines

kernel/bpf/verifier.c +3 -0

+
+       return ALL_CALLER_SAVED_REGS;
+}

[...]

Quoted 10 lines

kernel/bpf/verifier.c static int visit_func_call_insn(int t, struct bpf_insn *insns, · line 16133

Quoted 6 lines

kernel/bpf/verifier.c +6 -0

+static void mark_nocsr_pattern_for_call(struct bpf_verifier_env *env, int t)
+{
+       struct bpf_insn *insns = env->prog->insnsi, *stx, *ldx;
+       struct bpf_subprog_info *subprog;
+       u32 csr_mask = call_csr_mask(env, &insns[t]);
+       u32 reg_mask = ~csr_mask | ~ALL_CALLER_SAVED_REGS;

tbh, I'm lost with all these bitmask and their inversions... call_csr_mask()'s result is basically always used inverted, so why not return inverted mask in the first place?

The mask is initialized as a set of all registers preserved by this call.

Quoted 3 lines

ok, maybe it's just a mix of "no csr" and "csr" that confuses me. How about we call call_csr_mask as get_helper_preserved_mask() or something like that to "match" get_helper_clobber_mask()?

Yes, these two names are good, thank you.
I'd still call it get_call_preserved_mask() as kfuncs might be added at some point.

Quoted 28 lines

Quoted 27 lines

Those that are not in mask need a spill/fill pair.
I'll toss things around to make this more clear.
(naming, comments, maybe move the '| ~ALL_CALLER_SAVED_REGS' to the call_csr_mask()).

Quoted 12 lines

Quoted 12 lines

kernel/bpf/verifier.c +11 -0

+       int s, i;
+       s16 off;
+
+       if (csr_mask == ALL_CALLER_SAVED_REGS)
+               return;
+
+       for (i = 1, off = 0; i <= ARRAY_SIZE(caller_saved); ++i, off += BPF_REG_SIZE) {
+               if (t - i < 0 || t + i >= env->prog->len)
+                       break;
+               stx = &insns[t - i];
+               ldx = &insns[t + i];

Quoted 8 lines

kernel/bpf/verifier.c static int visit_func_call_insn(int t, struct bpf_insn *insns, · line 16148

Quoted 4 lines

kernel/bpf/verifier.c +4 -0

+               if (off == 0) {
+                       off = stx->off;
+                       if (off % BPF_REG_SIZE != 0)
+                               break;

kind of ugly that we assume stx before we actually checked that it's STX?... maybe split humongous if below into instruction checking (with code and src_reg) and then off checking separately?

Don't see anything ugly about this, tbh.

Quoted 3 lines

you are using stx->off and do % BPF_REG_SIZE check on it while that stx->off field might be meaningless for the instruction (because we are not yet sure it's STX instruction), that's a bit ugly, IMO

I can rewrite it like below:

                if (stx->code != (BPF_STX | BPF_MEM | BPF_DW) ||
                    ldx->code != (BPF_LDX | BPF_MEM | BPF_DW))

                        break;
                off = off != 0 ?: stx->off; // or use full 'if' block from the old version
                if (stx->dst_reg != BPF_REG_10 ||
                    ldx->src_reg != BPF_REG_10 ||
                    /* check spill/fill for the same reg and offset */
                    stx->src_reg != ldx->dst_reg ||
                    stx->off != ldx->off ||
                    stx->off != off ||
                    (off % BPF_REG_SIZE) != 0 ||
                    /* this should be a previously unseen register */
                    (BIT(stx->src_reg) & reg_mask))

                        break;

But I'm not sure this adds any actual clarity.

Quoted 34 lines

Quoted 3 lines

Can split the 'if' statement, if you think it's hard to read.

it's not about readability for me

Quoted 16 lines

Quoted 16 lines

Quoted 15 lines

kernel/bpf/verifier.c +13 -0

+               }
+               if (/* *(u64 *)(r10 - off) = r[0-5]? */
+                   stx->code != (BPF_STX | BPF_MEM | BPF_DW) ||
+                   stx->dst_reg != BPF_REG_10 ||
+                   /* r[0-5] = *(u64 *)(r10 - off)? */
+                   ldx->code != (BPF_LDX | BPF_MEM | BPF_DW) ||
+                   ldx->src_reg != BPF_REG_10 ||
+                   /* check spill/fill for the same reg and offset */
+                   stx->src_reg != ldx->dst_reg ||
+                   stx->off != ldx->off ||
+                   stx->off != off ||
+                   /* this should be a previously unseen register */
+                   BIT(stx->src_reg) & reg_mask)

Quoted 5 lines

Quoted 1 line

() around & operation?

No need, & has higher priority over ||.
You can check the AST using
https://tree-sitter.github.io/tree-sitter/playground .

Oh, I have no doubt you checked that it works correctly. It's just not a really good habit to rely on C's obscure operation ordering rules beyond A && B || C (and even then it is arguable). I think the rule of thumb to not mix bitwise and logic operators without explicit parenthesis makes sense.

Quoted 3 lines

But never mind, I already feel weird complaining about !strcmp(), every real kernel engineer should memorize operator precedence by heart.

I assumed you implied incorrect evaluation order.
Will add parenthesis.

Quoted 10 lines

Quoted 10 lines

Quoted 10 lines

Quoted 10 lines

kernel/bpf/verifier.c +10 -0

+                       break;
+               reg_mask |= BIT(stx->src_reg);
+               env->insn_aux_data[t - i].nocsr_pattern = 1;
+               env->insn_aux_data[t + i].nocsr_pattern = 1;
+       }
+       if (i == 1)
+               return;
+       env->insn_aux_data[t].nocsr_spills_num = i - 1;
+       s = find_containing_subprog(env, t);
+       /* can't happen */

[...]

Quoted 39 lines

Quoted 5 lines

Quoted 5 lines

Quoted 4 lines

kernel/bpf/verifier.c +4 -0

+       if (WARN_ON_ONCE(s < 0))
+               return;
+       subprog = &env->subprog_info[s];
+       subprog->nocsr_stack_off = min(subprog->nocsr_stack_off, off);

Quoted 7 lines

Quoted 2 lines

should this be max()? offsets are negative, right? so if nocsr uses -8 and -16 as in the example, entire [-16, 0) region is nocsr region

This should be min exactly because stack offsets are negative. For the example above the 'off' is initialized as -16 and then is incremented by +8 giving final value of -8.
And I need to select the minimal value used between several patterns.

so let's say I have two nocsr calls in the same subprog

    *(u64 *)(r10 - 8)  = r1;
    *(u64 *)(r10 - 16) = r2;
    call %[to_be_inlined]
    r2 = *(u64 *)(r10 - 16);
    r1 = *(u64 *)(r10 - 8);

and then a bit later

    *(u64 *)(r10 - 16)  = r1;
    *(u64 *)(r10 - 24) = r2;
    call %[to_be_inlined]
    r2 = *(u64 *)(r10 - 24);
    r1 = *(u64 *)(r10 - 16);

For the first chunk nocsr range is [-16, 0). For the second it's [-24, -8), right?
Should *(u64 *)(r10 - 8) = 123 somewhere in that subprog (not for nocsr calls) invalidate this whole nocsr thing? With min you'll basically have [-24, -8) as nocsr-reserved region, but shouldn't it be whole [-24, 0)?

Quoted 6 lines

Clang shouldn't generate such inconsistent offset, right? But it's legal, no? And if not, then all the calls should use the same upper stack boundary and we shouldn't be doing min/max, but rather checking that they are all consistent.

Or what am I missing again?

You don't miss anything.

With the current algorithm first call will not be rewritten because of the offset check in do_misc_fixups().
The second call would be rewritten and this is safe to do, because verifier knows that range [-24,-8) is only used by nocsr patterns. What you suggest is slightly more pessimistic, compared to current algorithm.

[...]

Quoted 19 lines

Quoted 18 lines

Quoted 13 lines

kernel/bpf/verifier.c static int do_misc_fixups(struct bpf_verifier_env *env) · line 20395

Quoted 12 lines

kernel/bpf/verifier.c +12 -0

+
+                       /* apply the rewrite:
+                        *   *(u64 *)(r10 - X) = rY ; num-times
+                        *   call()                               -> call()
+                        *   rY = *(u64 *)(r10 - X) ; num-times
+                        */
+                       err = verifier_remove_insns(env, i + delta - spills_num, spills_num);
+                       if (err)
+                               return err;
+                       err = verifier_remove_insns(env, i + delta - spills_num + 1, spills_num);
+                       if (err)
+                               return err;

Quoted 1 line

why not a single bpf_patch_insn_data()?

bpf_patch_insn_data() assumes that one instruction has to be replaced with many. Here I need to replace many instructions with a single instruction. I'd prefer not to tweak bpf_patch_insn_data() for this patch-set.

Quoted 4 lines

ah, bpf_patch_insn_data just does bpf_patch_insn_single, somehow I thought that it does range for range replacement of instructions. Never mind then (it's a bit sad that we don't have a proper flexible and powerful patching primitive, though, but oh well).

That is true.
I'll think about it once other issues with this patch-set are resolved.

[...]

Quoted 21 lines

Quoted 14 lines

Quoted 10 lines

kernel/bpf/verifier.c static int do_misc_fixups(struct bpf_verifier_env *env) · line 20404

Quoted 9 lines

kernel/bpf/verifier.c +9 -0

+
+                       i += spills_num - 1;
+                       /*   ^            ^   do a second visit of this instruction,
+                        *   |            '-- so that verifier can inline it
+                        *   '--------------- jump over deleted fills
+                        */
+                       delta -= 2 * spills_num;
+                       insn = env->prog->insnsi + i + delta;
+                       goto next_insn;

Quoted 3 lines

why not adjust the state and just fall through, what goto next_insn does that we can't (and next instruction is misleading, so I'd rather fix up and move forward)

Quoted 6 lines

I don't like this. The fall-through makes control flow more convoluted. To understand what would happen next:
- with goto next_insn we just start over;
- with fall-through we need to think about position of this particular 'if' statement within the loop.

Quoted 4 lines

Alright, it's fine. Though I don't see anything wrong with knowing that we patch up nocsr pattern before we do inlining of calls. And yes, order is important, so what? I always assumed that the order of operations in do_misc_fixups() is not arbitrary.

On a second thought maybe fall-through is not that bad.

[...]

Quoted 4 lines

I can rewrite it like below:

                if (stx->code != (BPF_STX | BPF_MEM | BPF_DW) ||
                    ldx->code != (BPF_LDX | BPF_MEM | BPF_DW))

I'd add stx->dst_reg != BPF_REG_10 and ldx->src_reg != BPF_REG_10 checks here and preserve original comments with instruction assembly form.

(think about this as establishing that we are looking at the correct shapes of instructions)

Quoted 11 lines

                        break;
                off = off != 0 ?: stx->off; // or use full 'if' block from the old version
                if (stx->dst_reg != BPF_REG_10 ||
                    ldx->src_reg != BPF_REG_10 ||
                    /* check spill/fill for the same reg and offset */
                    stx->src_reg != ldx->dst_reg ||
                    stx->off != ldx->off ||
                    stx->off != off ||
                    (off % BPF_REG_SIZE) != 0 ||
                    /* this should be a previously unseen register */
                    (BIT(stx->src_reg) & reg_mask))

and here we are checking all the correctness and additional imposed semantical invariants knowing full well that we are dealing with correct STX/LDX shapes

Quoted 3 lines

                        break;

But I'm not sure this adds any actual clarity.

I think it makes sense.

Ok, I see, this wasn't obvious that you want this behavior. I actually find it surprising (and so at least let's call this possibility out).

But, tbh, I'd make this stricter. I'd dictate that within a subprogram all no_csr patterns *should* end with the same stack offset and I would check for that (so what I mentioned before that instead of min or max we need assignment and check for equality if we already assigned it once).

Also, instead of doing that extra nocsr offset check in do_misc_fixups(), why don't we just reset all no_csr patterns within a subprogram *if we find a single violation*. Compiler shouldn't ever emit such code, right? So let's be strict and fallback to not recognizing nocsr.

And then we won't need that extra check in do_misc_fixups() because we eagerly unset no_csr flag and will never hit that piece of logic in patching.

I'd go even further and say that on any nocsr invariant violation, we just go and reset all nocsr pattern flags across entire BPF program (all subprogs including). In check_nocsr_stack_contract() I mean. Just have a loop over all instructions and set that flag to false.

Why not? What realistic application would need to violate nocsr in some subprogs but not in others?

KISS or it's too simplistic for some reason?

Quoted 11 lines

Quoted 8 lines

Quoted 3 lines

bpf_patch_insn_data() assumes that one instruction has to be replaced with many. Here I need to replace many instructions with a single instruction. I'd prefer not to tweak bpf_patch_insn_data() for this patch-set.

ah, bpf_patch_insn_data just does bpf_patch_insn_single, somehow I thought that it does range for range replacement of instructions. Never mind then (it's a bit sad that we don't have a proper flexible and powerful patching primitive, though, but oh well).

That is true.
I'll think about it once other issues with this patch-set are resolved.

yeah, it's completely unrelated, but having a bpf_patch_insns that takes input instruction range to be replaced and replacing it with another set of instructions would cover all existing use cases and some more. We wouldn't need verifier_remove_insns(), because that's just replacing existing instructions with empty new set of instructions. We would now have "insert instructions" primitive if we specify empty input range of instructions. If we add a flag whether to adjust jump offsets and make it configurable, we'd need the thing that Alexei needed for may_goto without any extra hacks.

Furthermore, I find it wrong and silly that we keep having manual delta+insn adjustments in every single piece of patching logic. I think this should be done by bpf_patch_insns(). We need to have a small "insn_patcher" struct that we use during instruction patching, and a small instruction iterator on top that would keep returning next instruction to process (and its index, probably). This will allow us to optimize patching and instead of doing O(N) we can have something faster and smarter (if we hide direct insn array accesses during patching).

But this is all a completely separate story from all of this.

On Wed, 2024-07-10 at 08:36 -0700, Andrii Nakryiko wrote:

[...]

Quoted 28 lines

Quoted 4 lines

I can rewrite it like below:

                if (stx->code != (BPF_STX | BPF_MEM | BPF_DW) ||
                    ldx->code != (BPF_LDX | BPF_MEM | BPF_DW))

I'd add stx->dst_reg != BPF_REG_10 and ldx->src_reg != BPF_REG_10 checks here and preserve original comments with instruction assembly form.

(think about this as establishing that we are looking at the correct shapes of instructions)

Quoted 11 lines

                        break;
                off = off != 0 ?: stx->off; // or use full 'if' block from the old version
                if (stx->dst_reg != BPF_REG_10 ||
                    ldx->src_reg != BPF_REG_10 ||
                    /* check spill/fill for the same reg and offset */
                    stx->src_reg != ldx->dst_reg ||
                    stx->off != ldx->off ||
                    stx->off != off ||
                    (off % BPF_REG_SIZE) != 0 ||
                    /* this should be a previously unseen register */
                    (BIT(stx->src_reg) & reg_mask))

and here we are checking all the correctness and additional imposed semantical invariants knowing full well that we are dealing with correct STX/LDX shapes

Quoted 5 lines

Quoted 3 lines

                        break;

But I'm not sure this adds any actual clarity.

I think it makes sense.

Ok, will change.

[...]

Quoted 8 lines

Ok, I see, this wasn't obvious that you want this behavior. I actually find it surprising (and so at least let's call this possibility out).

But, tbh, I'd make this stricter. I'd dictate that within a subprogram all no_csr patterns *should* end with the same stack offset and I would check for that (so what I mentioned before that instead of min or max we need assignment and check for equality if we already assigned it once).

This makes sense, but does not cover a theoretical corner case:
- suppose there are two nocsr functions A and B on the kernel side, but only was A marked as nocsr during program compilation;
- the spill/fill "bracket" was generated for a call to function B by the compiler (because this is just a valid codegen).

So I wanted to keep the nocsr check a little bit more permissive.

Quoted 6 lines

Also, instead of doing that extra nocsr offset check in do_misc_fixups(), why don't we just reset all no_csr patterns within a subprogram *if we find a single violation*. Compiler shouldn't ever emit such code, right? So let's be strict and fallback to not recognizing nocsr.

Quoted 3 lines

And then we won't need that extra check in do_misc_fixups() because we eagerly unset no_csr flag and will never hit that piece of logic in patching.

I can do that, but the detector pass would have to be two pass:
- on the first pass, find the nocsr_stack_off, add candidate insn marks;
- on the second pass, remove marks from insns with wrong stack access offset.

Otherwise I can't discern true patterns from false positives in situation described above.

Quoted 6 lines

I'd go even further and say that on any nocsr invariant violation, we just go and reset all nocsr pattern flags across entire BPF program (all subprogs including). In check_nocsr_stack_contract() I mean. Just have a loop over all instructions and set that flag to false.

Quoted 4 lines

Why not? What realistic application would need to violate nocsr in some subprogs but not in others?

KISS or it's too simplistic for some reason?

I can invalidate nocsr per-program.
If so, I would use an "allow_nocsr" flag in program aux to avoid additional passes over instructions.

[...]

Quoted 32 lines

Quoted 11 lines

Quoted 8 lines

Quoted 3 lines

bpf_patch_insn_data() assumes that one instruction has to be replaced with many. Here I need to replace many instructions with a single instruction. I'd prefer not to tweak bpf_patch_insn_data() for this patch-set.

ah, bpf_patch_insn_data just does bpf_patch_insn_single, somehow I thought that it does range for range replacement of instructions. Never mind then (it's a bit sad that we don't have a proper flexible and powerful patching primitive, though, but oh well).

That is true.
I'll think about it once other issues with this patch-set are resolved.

yeah, it's completely unrelated, but having a bpf_patch_insns that takes input instruction range to be replaced and replacing it with another set of instructions would cover all existing use cases and some more. We wouldn't need verifier_remove_insns(), because that's just replacing existing instructions with empty new set of instructions. We would now have "insert instructions" primitive if we specify empty input range of instructions. If we add a flag whether to adjust jump offsets and make it configurable, we'd need the thing that Alexei needed for may_goto without any extra hacks.

Furthermore, I find it wrong and silly that we keep having manual delta+insn adjustments in every single piece of patching logic. I think this should be done by bpf_patch_insns(). We need to have a small "insn_patcher" struct that we use during instruction patching, and a small instruction iterator on top that would keep returning next instruction to process (and its index, probably). This will allow us to optimize patching and instead of doing O(N) we can have something faster and smarter (if we hide direct insn array accesses during patching).

Quoted 1 line

But this is all a completely separate story from all of this.

I actually suggested something along these lines very long time ago:
https://lore.kernel.org/bpf/[email protected]/

Quoted 9 lines

Quoted 8 lines

Ok, I see, this wasn't obvious that you want this behavior. I actually find it surprising (and so at least let's call this possibility out).

But, tbh, I'd make this stricter. I'd dictate that within a subprogram all no_csr patterns *should* end with the same stack offset and I would check for that (so what I mentioned before that instead of min or max we need assignment and check for equality if we already assigned it once).

Quoted 5 lines

This makes sense, but does not cover a theoretical corner case:
- suppose there are two nocsr functions A and B on the kernel side, but only was A marked as nocsr during program compilation;
- the spill/fill "bracket" was generated for a call to function B by the compiler (because this is just a valid codegen).

In this case the call to A shouldn't be changing nocsr_offset at all, though? You should find no spill/fill and thus even though A is *allowed* to use no_csr, it doesn't, so it should have no effect on nocsr offsets, no?

But your example actually made me think about another (not theoretical at all) case. What if we have calls to A and B, the kernel is slightly old and knows that B is nocsr, but A is not. But the BPF program was compiled with the latest helper/kfunc definitions marking A as no_csr eligible (as well as B). (btw, THAT'S THE WORD for allow_csr -- ELIGIBLE. csr_eligible FTW! but I digress...)

With the case above we'll disable nocsr for both A and B, right? That sucks, but not sure if we can do anything about that. (We can probably assume no_csr pattern and thus allow spill/fill and not disable nocsr in general, but not remove spill/fills... a bit more complication upfront for longer term extensibility.. not sure, maybe performance regression is a fine price, hmm)

So I take it back about unmarking csr in the *entire BPF program*, let's just limit it to the subprog scope. But I still think we should do it eagerly, rather than double checking in do_misc_followups(). WDYT?

Quoted 12 lines

So I wanted to keep the nocsr check a little bit more permissive.

Quoted 9 lines

Also, instead of doing that extra nocsr offset check in do_misc_fixups(), why don't we just reset all no_csr patterns within a subprogram *if we find a single violation*. Compiler shouldn't ever emit such code, right? So let's be strict and fallback to not recognizing nocsr.

And then we won't need that extra check in do_misc_fixups() because we eagerly unset no_csr flag and will never hit that piece of logic in patching.

Quoted 3 lines

I can do that, but the detector pass would have to be two pass:
- on the first pass, find the nocsr_stack_off, add candidate insn marks;
- on the second pass, remove marks from insns with wrong stack access offset.

It's not really a second pass, it's part of normal validation. check_nocsr_stack_contract() will detect this and will do, yes, pass over all instructions of a subprogram to unmark them.

Quoted 2 lines

Otherwise I can't discern true patterns from false positives in situation described above.

See above, I might be missing what your "theoretical" example changes.

Quoted 9 lines

Quoted 9 lines

I'd go even further and say that on any nocsr invariant violation, we just go and reset all nocsr pattern flags across entire BPF program (all subprogs including). In check_nocsr_stack_contract() I mean. Just have a loop over all instructions and set that flag to false.

Why not? What realistic application would need to violate nocsr in some subprogs but not in others?

Quoted 5 lines

Quoted 1 line

KISS or it's too simplistic for some reason?

I can invalidate nocsr per-program.
If so, I would use an "allow_nocsr" flag in program aux to avoid additional passes over instructions.

yep, see above (but let's keep it per-subprog for now)

Quoted 34 lines

Quoted 33 lines

Quoted 11 lines

Quoted 8 lines

Quoted 3 lines

bpf_patch_insn_data() assumes that one instruction has to be replaced with many. Here I need to replace many instructions with a single instruction. I'd prefer not to tweak bpf_patch_insn_data() for this patch-set.

ah, bpf_patch_insn_data just does bpf_patch_insn_single, somehow I thought that it does range for range replacement of instructions. Never mind then (it's a bit sad that we don't have a proper flexible and powerful patching primitive, though, but oh well).

That is true.
I'll think about it once other issues with this patch-set are resolved.

yeah, it's completely unrelated, but having a bpf_patch_insns that takes input instruction range to be replaced and replacing it with another set of instructions would cover all existing use cases and some more. We wouldn't need verifier_remove_insns(), because that's just replacing existing instructions with empty new set of instructions. We would now have "insert instructions" primitive if we specify empty input range of instructions. If we add a flag whether to adjust jump offsets and make it configurable, we'd need the thing that Alexei needed for may_goto without any extra hacks.

Furthermore, I find it wrong and silly that we keep having manual delta+insn adjustments in every single piece of patching logic. I think this should be done by bpf_patch_insns(). We need to have a small "insn_patcher" struct that we use during instruction patching, and a small instruction iterator on top that would keep returning next instruction to process (and its index, probably). This will allow us to optimize patching and instead of doing O(N) we can have something faster and smarter (if we hide direct insn array accesses during patching).

But this is all a completely separate story from all of this.

Quoted 2 lines

I actually suggested something along these lines very long time ago:
https://lore.kernel.org/bpf/[email protected]/

We had a few discussions around patching improvements (you can see I mentioned that in that thread as well). We all like to talk about improving this, but not really doing anything about this. :) Tech debt at its best.

On Wed, 2024-07-10 at 10:50 -0700, Andrii Nakryiko wrote:

[...]

Quoted 15 lines

Quoted 9 lines

Quoted 8 lines

Ok, I see, this wasn't obvious that you want this behavior. I actually find it surprising (and so at least let's call this possibility out).

But, tbh, I'd make this stricter. I'd dictate that within a subprogram all no_csr patterns *should* end with the same stack offset and I would check for that (so what I mentioned before that instead of min or max we need assignment and check for equality if we already assigned it once).

Quoted 5 lines

This makes sense, but does not cover a theoretical corner case:
- suppose there are two nocsr functions A and B on the kernel side, but only was A marked as nocsr during program compilation;
- the spill/fill "bracket" was generated for a call to function B by the compiler (because this is just a valid codegen).

Quoted 4 lines

In this case the call to A shouldn't be changing nocsr_offset at all, though? You should find no spill/fill and thus even though A is *allowed* to use no_csr, it doesn't, so it should have no effect on nocsr offsets, no?

Consider the following code:

    *(u64 *)(r10 - 24) = r1;
    call A                     // kernel and clang know that A is nocsr
    r1 = *(u64 *)(r10 - 24);   // kernel assumes .nocsr_stack_offset -24
    ...
    *(u64 *)(r10 - 16) = r1;
    call B                     // only kernel knows that B is nocsr
    r1 = *(u64 *)(r10 - 16);   // with stricter logic this would disable
                               // nocsr for the whole sub-probram

Quoted 15 lines

But your example actually made me think about another (not theoretical at all) case. What if we have calls to A and B, the kernel is slightly old and knows that B is nocsr, but A is not. But the BPF program was compiled with the latest helper/kfunc definitions marking A as no_csr eligible (as well as B). (btw, THAT'S THE WORD for allow_csr -- ELIGIBLE. csr_eligible FTW! but I digress...)

With the case above we'll disable nocsr for both A and B, right? That sucks, but not sure if we can do anything about that. (We can probably assume no_csr pattern and thus allow spill/fill and not disable nocsr in general, but not remove spill/fills... a bit more complication upfront for longer term extensibility.. not sure, maybe performance regression is a fine price, hmm)

Quoted 4 lines

So I take it back about unmarking csr in the *entire BPF program*, let's just limit it to the subprog scope. But I still think we should do it eagerly, rather than double checking in do_misc_followups(). WDYT?

With current algo this situation would disable nocsr indeed. The problem is that checks for spilled stack slots usage is too simplistic. However, it could be covered if the check is performed using e.g. process I described earlier:
- for spill, remember the defining instruction in the stack slot structure;
- for fill, "merge" the defining instruction index;
- for other stack access mark defining instruction as escaping.

Quoted 13 lines

Quoted 13 lines

So I wanted to keep the nocsr check a little bit more permissive.

Quoted 9 lines

Also, instead of doing that extra nocsr offset check in do_misc_fixups(), why don't we just reset all no_csr patterns within a subprogram *if we find a single violation*. Compiler shouldn't ever emit such code, right? So let's be strict and fallback to not recognizing nocsr.

And then we won't need that extra check in do_misc_fixups() because we eagerly unset no_csr flag and will never hit that piece of logic in patching.

Quoted 7 lines

Quoted 3 lines

I can do that, but the detector pass would have to be two pass:
- on the first pass, find the nocsr_stack_off, add candidate insn marks;
- on the second pass, remove marks from insns with wrong stack access offset.

It's not really a second pass, it's part of normal validation. check_nocsr_stack_contract() will detect this and will do, yes, pass over all instructions of a subprogram to unmark them.

- on the first pass true .nocsr_stack_off is not yet known,
so .nocsr_pattern is set optimistically;
- on the second pass .nocsr_stack_off is already known,
so .nocsr_pattern can be removed from spills/fills outside the range;
- check_nocsr_stack_contract() does not need to scan full sub-program on each violation, it can set a flag disabling nocsr in subprogram info.

Quoted 15 lines

Quoted 3 lines

Otherwise I can't discern true patterns from false positives in situation described above.

See above, I might be missing what your "theoretical" example changes.

Quoted 9 lines

Quoted 9 lines

I'd go even further and say that on any nocsr invariant violation, we just go and reset all nocsr pattern flags across entire BPF program (all subprogs including). In check_nocsr_stack_contract() I mean. Just have a loop over all instructions and set that flag to false.

Why not? What realistic application would need to violate nocsr in some subprogs but not in others?

Quoted 7 lines

Quoted 5 lines

Quoted 1 line

KISS or it's too simplistic for some reason?

I can invalidate nocsr per-program.
If so, I would use an "allow_nocsr" flag in program aux to avoid additional passes over instructions.

yep, see above (but let's keep it per-subprog for now)

Ok

Quoted 37 lines

Quoted 36 lines

Quoted 32 lines

Quoted 11 lines

Quoted 8 lines

Quoted 3 lines

bpf_patch_insn_data() assumes that one instruction has to be replaced with many. Here I need to replace many instructions with a single instruction. I'd prefer not to tweak bpf_patch_insn_data() for this patch-set.

ah, bpf_patch_insn_data just does bpf_patch_insn_single, somehow I thought that it does range for range replacement of instructions. Never mind then (it's a bit sad that we don't have a proper flexible and powerful patching primitive, though, but oh well).

That is true.
I'll think about it once other issues with this patch-set are resolved.

yeah, it's completely unrelated, but having a bpf_patch_insns that takes input instruction range to be replaced and replacing it with another set of instructions would cover all existing use cases and some more. We wouldn't need verifier_remove_insns(), because that's just replacing existing instructions with empty new set of instructions. We would now have "insert instructions" primitive if we specify empty input range of instructions. If we add a flag whether to adjust jump offsets and make it configurable, we'd need the thing that Alexei needed for may_goto without any extra hacks.

Furthermore, I find it wrong and silly that we keep having manual delta+insn adjustments in every single piece of patching logic. I think this should be done by bpf_patch_insns(). We need to have a small "insn_patcher" struct that we use during instruction patching, and a small instruction iterator on top that would keep returning next instruction to process (and its index, probably). This will allow us to optimize patching and instead of doing O(N) we can have something faster and smarter (if we hide direct insn array accesses during patching).

Quoted 1 line

But this is all a completely separate story from all of this.

I actually suggested something along these lines very long time ago:
https://lore.kernel.org/bpf/[email protected]/

Quoted 4 lines

We had a few discussions around patching improvements (you can see I mentioned that in that thread as well). We all like to talk about improving this, but not really doing anything about this. :) Tech debt at its best.

If you are not completely opposed to that idea I can follow-up with a complete version as an RFC.

Quoted 27 lines · Eduard Zingerman

On Wed, 2024-07-10 at 10:50 -0700, Andrii Nakryiko wrote:

[...]

Quoted 15 lines

Quoted 9 lines

Quoted 8 lines

Ok, I see, this wasn't obvious that you want this behavior. I actually find it surprising (and so at least let's call this possibility out).

But, tbh, I'd make this stricter. I'd dictate that within a subprogram all no_csr patterns *should* end with the same stack offset and I would check for that (so what I mentioned before that instead of min or max we need assignment and check for equality if we already assigned it once).

Quoted 5 lines

This makes sense, but does not cover a theoretical corner case:
- suppose there are two nocsr functions A and B on the kernel side, but only was A marked as nocsr during program compilation;
- the spill/fill "bracket" was generated for a call to function B by the compiler (because this is just a valid codegen).

Quoted 4 lines

In this case the call to A shouldn't be changing nocsr_offset at all, though? You should find no spill/fill and thus even though A is *allowed* to use no_csr, it doesn't, so it should have no effect on nocsr offsets, no?

Consider the following code:

Quoted 8 lines

    *(u64 *)(r10 - 24) = r1;
    call A                     // kernel and clang know that A is nocsr
    r1 = *(u64 *)(r10 - 24);   // kernel assumes .nocsr_stack_offset -24
    ...
    *(u64 *)(r10 - 16) = r1;
    call B                     // only kernel knows that B is nocsr
    r1 = *(u64 *)(r10 - 16);   // with stricter logic this would disable
                               // nocsr for the whole sub-probram

oh, you mean that r10-16 accesses are valid instructions emitted by the compiler but not due to nocsr? I mean, tough luck?... We shouldn't reject this, but nocsr is ultimately a performance optimization, so not critical if it doesn't work within some subprogram.

Quoted 19 lines

Quoted 14 lines

But your example actually made me think about another (not theoretical at all) case. What if we have calls to A and B, the kernel is slightly old and knows that B is nocsr, but A is not. But the BPF program was compiled with the latest helper/kfunc definitions marking A as no_csr eligible (as well as B). (btw, THAT'S THE WORD for allow_csr -- ELIGIBLE. csr_eligible FTW! but I digress...)

With the case above we'll disable nocsr for both A and B, right? That sucks, but not sure if we can do anything about that. (We can probably assume no_csr pattern and thus allow spill/fill and not disable nocsr in general, but not remove spill/fills... a bit more complication upfront for longer term extensibility.. not sure, maybe performance regression is a fine price, hmm)

Quoted 4 lines

So I take it back about unmarking csr in the *entire BPF program*, let's just limit it to the subprog scope. But I still think we should do it eagerly, rather than double checking in do_misc_followups(). WDYT?

Quoted 7 lines

With current algo this situation would disable nocsr indeed. The problem is that checks for spilled stack slots usage is too simplistic. However, it could be covered if the check is performed using e.g. process I described earlier:
- for spill, remember the defining instruction in the stack slot structure;
- for fill, "merge" the defining instruction index;
- for other stack access mark defining instruction as escaping.

Sorry, I have no idea what the above means and implies. "defining instruction", "merge", "escaping"

As I mentioned above, I'd keep it as simple as reasonably possible.

Quoted 7 lines

Quoted 1 line

- on the first pass true .nocsr_stack_off is not yet known,
so .nocsr_pattern is set optimistically;
- on the second pass .nocsr_stack_off is already known,
so .nocsr_pattern can be removed from spills/fills outside the range;
- check_nocsr_stack_contract() does not need to scan full sub-program on each violation, it can set a flag disabling nocsr in subprogram info.

I'm not even sure anymore if we are agreeing or disagreeing, let's just look at the next revision or something, I'm getting lost.

I was saying that as soon as check_nocsr_stack_contract() detects that contract is breached, we eagerly set nocsr_pattern and nocsr_spills_num to 0 for all instructions within the current subprog and setting nocsr_stack_off for subprog info to 0 (there is no more csr). There will be no other violations after that within that subprog. Maybe that's what you mean as well and I just can't read.

Quoted 37 lines · Andrii Nakryiko

Quoted 35 lines · Eduard Zingerman

On Wed, 2024-07-10 at 10:50 -0700, Andrii Nakryiko wrote:

[...]

Quoted 15 lines

Quoted 9 lines

Quoted 8 lines

Ok, I see, this wasn't obvious that you want this behavior. I actually find it surprising (and so at least let's call this possibility out).

But, tbh, I'd make this stricter. I'd dictate that within a subprogram all no_csr patterns *should* end with the same stack offset and I would check for that (so what I mentioned before that instead of min or max we need assignment and check for equality if we already assigned it once).

Quoted 5 lines

This makes sense, but does not cover a theoretical corner case:
- suppose there are two nocsr functions A and B on the kernel side, but only was A marked as nocsr during program compilation;
- the spill/fill "bracket" was generated for a call to function B by the compiler (because this is just a valid codegen).

Quoted 4 lines

In this case the call to A shouldn't be changing nocsr_offset at all, though? You should find no spill/fill and thus even though A is *allowed* to use no_csr, it doesn't, so it should have no effect on nocsr offsets, no?

Consider the following code:

    *(u64 *)(r10 - 24) = r1;
    call A                     // kernel and clang know that A is nocsr
    r1 = *(u64 *)(r10 - 24);   // kernel assumes .nocsr_stack_offset -24
    ...
    *(u64 *)(r10 - 16) = r1;
    call B                     // only kernel knows that B is nocsr
    r1 = *(u64 *)(r10 - 16);   // with stricter logic this would disable
                               // nocsr for the whole sub-probram

Quoted 4 lines

oh, you mean that r10-16 accesses are valid instructions emitted by the compiler but not due to nocsr? I mean, tough luck?... We shouldn't reject this, but nocsr is ultimately a performance optimization, so not critical if it doesn't work within some subprogram.

Not critical, but the difference between allowing and disallowing nocsr for this case is '<' (current) vs '==' (suggested) check for .nocsr_stack_offset. I think that current algo should not be made more strict.

Quoted 27 lines

Quoted 19 lines

Quoted 14 lines

But your example actually made me think about another (not theoretical at all) case. What if we have calls to A and B, the kernel is slightly old and knows that B is nocsr, but A is not. But the BPF program was compiled with the latest helper/kfunc definitions marking A as no_csr eligible (as well as B). (btw, THAT'S THE WORD for allow_csr -- ELIGIBLE. csr_eligible FTW! but I digress...)

With the case above we'll disable nocsr for both A and B, right? That sucks, but not sure if we can do anything about that. (We can probably assume no_csr pattern and thus allow spill/fill and not disable nocsr in general, but not remove spill/fills... a bit more complication upfront for longer term extensibility.. not sure, maybe performance regression is a fine price, hmm)

Quoted 4 lines

So I take it back about unmarking csr in the *entire BPF program*, let's just limit it to the subprog scope. But I still think we should do it eagerly, rather than double checking in do_misc_followups(). WDYT?

Quoted 7 lines

With current algo this situation would disable nocsr indeed. The problem is that checks for spilled stack slots usage is too simplistic. However, it could be covered if the check is performed using e.g. process I described earlier:
- for spill, remember the defining instruction in the stack slot structure;
- for fill, "merge" the defining instruction index;
- for other stack access mark defining instruction as escaping.

Quoted 4 lines

Sorry, I have no idea what the above means and implies. "defining instruction", "merge", "escaping"

As I mentioned above, I'd keep it as simple as reasonably possible.

It should not be much more complex compared to current implementation.

    1: *(u64 *)(r10 - 16) = r1; // for stack slot -16 remember that
                                // it is defined at insn (1)
    2: call %[nocsr_func]
    3: r1 = *(u64 *)(r10 - 16); // the value read from stack is defined
                                // at (1), so remember this in insn aux

If (1) is the only defining instruction for (3) and value written at (1) is not used by other instructions (e.g. not passed as function argument, "escapes"), the pair (1) and (3) could be removed.

Quoted 14 lines

As I mentioned above, I'd keep it as simple as reasonably possible.

Quoted 7 lines

Quoted 1 line

- on the first pass true .nocsr_stack_off is not yet known,
so .nocsr_pattern is set optimistically;
- on the second pass .nocsr_stack_off is already known,
so .nocsr_pattern can be removed from spills/fills outside the range;
- check_nocsr_stack_contract() does not need to scan full sub-program on each violation, it can set a flag disabling nocsr in subprogram info.

I'm not even sure anymore if we are agreeing or disagreeing, let's just look at the next revision or something, I'm getting lost.

Quoted 6 lines

I was saying that as soon as check_nocsr_stack_contract() detects that contract is breached, we eagerly set nocsr_pattern and nocsr_spills_num to 0 for all instructions within the current subprog and setting nocsr_stack_off for subprog info to 0 (there is no more csr). There will be no other violations after that within that subprog. Maybe that's what you mean as well and I just can't read.

Ok, I'll send v3, let's proceed from there.

[...]

Quoted 8 lines

Quoted 8 lines

So I wanted to keep the nocsr check a little bit more permissive.

Quoted 5 lines

Also, instead of doing that extra nocsr offset check in do_misc_fixups(), why don't we just reset all no_csr patterns within a subprogram *if we find a single violation*. Compiler shouldn't ever emit such code, right? So let's be strict and fallback to not recognizing nocsr.

Quoted 11 lines

Quoted 7 lines

Quoted 3 lines

And then we won't need that extra check in do_misc_fixups() because we eagerly unset no_csr flag and will never hit that piece of logic in patching.

I can do that, but the detector pass would have to be two pass:
- on the first pass, find the nocsr_stack_off, add candidate insn marks;
- on the second pass, remove marks from insns with wrong stack access offset.

It's not really a second pass, it's part of normal validation. check_nocsr_stack_contract() will detect this and will do, yes, pass over all instructions of a subprogram to unmark them.

- on the first pass true .nocsr_stack_off is not yet known,
so .nocsr_pattern is set optimistically;
- on the second pass .nocsr_stack_off is already known,
so .nocsr_pattern can be removed from spills/fills outside the range;
- check_nocsr_stack_contract() does not need to scan full sub-program on each violation, it can set a flag disabling nocsr in subprogram info.

Quoted 3 lines · Eduard Zingerman

Quoted 3 lines

Quoted 3 lines

So I wanted to keep the nocsr check a little bit more permissive.

Quoted 5 lines

Quoted 5 lines

Quoted 5 lines

Quoted 5 lines

Also, instead of doing that extra nocsr offset check in do_misc_fixups(), why don't we just reset all no_csr patterns within a subprogram *if we find a single violation*. Compiler shouldn't ever emit such code, right? So let's be strict and fallback to not recognizing nocsr.

no.

Quoted 13 lines

Quoted 5 lines

Quoted 5 lines

Quoted 4 lines

And then we won't need that extra check in do_misc_fixups() because we eagerly unset no_csr flag and will never hit that piece of logic in patching.

Quoted 7 lines

Quoted 3 lines

I can do that, but the detector pass would have to be two pass:
- on the first pass, find the nocsr_stack_off, add candidate insn marks;
- on the second pass, remove marks from insns with wrong stack access offset.

It's not really a second pass, it's part of normal validation. check_nocsr_stack_contract() will detect this and will do, yes, pass over all instructions of a subprogram to unmark them.

Quoted 6 lines

- on the first pass true .nocsr_stack_off is not yet known,
so .nocsr_pattern is set optimistically;
- on the second pass .nocsr_stack_off is already known,
so .nocsr_pattern can be removed from spills/fills outside the range;
- check_nocsr_stack_contract() does not need to scan full sub-program on each violation, it can set a flag disabling nocsr in subprogram info.

I really don't like where this discussion is going.
Keep the current algo it's simple enough and matches what the compiler will generate. Obscure cases of users manually writing such patterns in asm are out of scope. Do not complicate the verifier for them.

But, tbh, I'd make this stricter. I'd dictate that within a subprogram all no_csr patterns *should* end with the same stack offset and I would check for that (so what I mentioned before that instead of min or max we need assignment and check for equality if we already assigned it once).

Quoted 6 lines

include/linux/bpf_verifier.h +0 -0

index 2b54e25d2364..735ae0901b3d 100644
@@ -585,6 +585,15 @@ struct bpf_insn_aux_data {
         * accepts callback function as a parameter.

include/linux/bpf_verifier.h struct bpf_insn_aux_data { · line 595

Quoted 10 lines

include/linux/bpf_verifier.h +8 -0

         */
        bool calls_callback;
+       /* true if STX or LDX instruction is a part of a spill/fill
+        * pattern for a no_caller_saved_registers call.
+        */
+       u8 nocsr_pattern:1;
+       /* for CALL instructions, a number of spill/fill pairs in the
+        * no_caller_saved_registers pattern.
+        */
+       u8 nocsr_spills_num:3;

despite bitfields this will extend bpf_insn_aux_data by 8 bytes. there are 2 bytes of padding after alu_state, let's put this there.

And let's not add bitfields unless absolutely necessary (this can be always done later).

On Tue, 2024-07-09 at 16:42 -0700, Andrii Nakryiko wrote:

[...]

Quoted 20 lines

Quoted 6 lines

include/linux/bpf_verifier.h +0 -0

index 2b54e25d2364..735ae0901b3d 100644
@@ -585,6 +585,15 @@ struct bpf_insn_aux_data {
         * accepts callback function as a parameter.

include/linux/bpf_verifier.h struct bpf_insn_aux_data { · line 595

Quoted 10 lines

include/linux/bpf_verifier.h +8 -0

         */
        bool calls_callback;
+       /* true if STX or LDX instruction is a part of a spill/fill
+        * pattern for a no_caller_saved_registers call.
+        */
+       u8 nocsr_pattern:1;
+       /* for CALL instructions, a number of spill/fill pairs in the
+        * no_caller_saved_registers pattern.
+        */
+       u8 nocsr_spills_num:3;

despite bitfields this will extend bpf_insn_aux_data by 8 bytes. there are 2 bytes of padding after alu_state, let's put this there.

Quoted 2 lines

And let's not add bitfields unless absolutely necessary (this can be always done later).

Unfortunately the bitfields are still necessary, here is pahole output after moving fields and removing bitfields:

struct bpf_insn_aux_data {
        ...
        u8                         alu_state;            /*    62     1 */
        u8                         nocsr_pattern;        /*    63     1 */
        /* --- cacheline 1 boundary (64 bytes) --- */
        u8                         nocsr_spills_num;     /*    64     1 */

        /* XXX 3 bytes hole, try to pack */

        unsigned int               orig_idx;             /*    68     4 */
        ...

        /* size: 80, cachelines: 2, members: 20 */
        /* sum members: 73, holes: 1, sum holes: 3 */
        /* padding: 4 */
        /* last cacheline: 16 bytes */
};

While with bitfields:

        /* size: 72, cachelines: 2, members: 20 */

[...]

kernel/bpf/verifier.c +23 -0

+                       for (j = 1; j <= spills_num; ++j) {
+                               if ((insn - j)->off >= subprogs[cur_subprog].nocsr_stack_off ||
+                                   (insn + j)->off >= subprogs[cur_subprog].nocsr_stack_off) {
+                                       /* do a second visit of this instruction,
+                                        * so that verifier can inline it
+                                        */
+                                       i -= 1;
+                                       insn -= 1;
+                                       goto next_insn;
+                               }
+                       }
+
+                       /* apply the rewrite:
+                        *   *(u64 *)(r10 - X) = rY ; num-times
+                        *   call()                               -> call()
+                        *   rY = *(u64 *)(r10 - X) ; num-times
+                        */
+                       err = verifier_remove_insns(env, i + delta - spills_num, spills_num);
+                       if (err)
+                               return err;
+                       err = verifier_remove_insns(env, i + delta - spills_num + 1, spills_num);
+                       if (err)
+                               return err;

somewhere after spill/fill removal subprog->stack_depth needs to be adjust to nocsr_stack_off, otherwise extra stack space is wasted.
I couldn't find this logic in the patch.

Once the adjustment logic is done, pls add a selftest with nocsr and may_goto, since may_goto processing is in the same do_misc_fixups() loop and it needs to grow the stack while spill/fill removal will shrink the stack.

struct bpf_insn *disasm_insn(struct bpf_insn *insn, char *buf, size_t buf_sz);

Disassembles instruction 'insn' to a text buffer 'buf'. Removes insn->code hex prefix added by kernel disassembly routine. Returns a pointer to the next instruction
(increments insn by either 1 or 2).

Signed-off-by Eduard Zingerman <[email protected]>

---
 tools/testing/selftests/bpf/Makefile          |  1 +
 tools/testing/selftests/bpf/disasm_helpers.c  | 51 +++++++++++++
 tools/testing/selftests/bpf/disasm_helpers.h  | 12 +++
 .../selftests/bpf/prog_tests/ctx_rewrite.c    | 74 +++----------------
 tools/testing/selftests/bpf/testing_helpers.c |  1 +
 5 files changed, 75 insertions(+), 64 deletions(-)
 create mode 100644 tools/testing/selftests/bpf/disasm_helpers.c
 create mode 100644 tools/testing/selftests/bpf/disasm_helpers.h

Add annotations __arch_x86_64, __arch_arm64, __arch_riscv64 to specify on which architecture the test case should be tested. Several __arch_* annotations could be specified at once. When test case is not run on current arch it is marked as skipped.

For example, the following would be tested only on arm64 and riscv64:

  SEC("raw_tp")
  __arch_arm64
  __arch_riscv64
  __xlated("1: *(u64 *)(r10 - 16) = r1")
  __xlated("2: call")
  __xlated("3: r1 = *(u64 *)(r10 - 16);")
  __success
  __naked void canary_arm64_riscv64(void)
  {
        asm volatile (
        "r1 = 1;"
        "*(u64 *)(r10 - 16) = r1;"
        "call %[bpf_get_smp_processor_id];"
        "r1 = *(u64 *)(r10 - 16);"
        "exit;"
        :
        : __imm(bpf_get_smp_processor_id)
        : __clobber_all);
  }

On x86 it would be skipped:

#467/2 verifier_nocsr/canary_arm64_riscv64:SKIP

Signed-off-by Eduard Zingerman <[email protected]>

---
 tools/testing/selftests/bpf/progs/bpf_misc.h |  8 ++++
 tools/testing/selftests/bpf/test_loader.c    | 43 ++++++++++++++++++++
 2 files changed, 51 insertions(+)

tools/testing/selftests/bpf/test_loader.c +2 -0

+       spec->arch_mask = arch_mask;
+
        if (spec->mode_mask == 0)
                spec->mode_mask = PRIV;