bpf: track find_equal_scalars history on per-instruction level

Let push_jmp_history() peek current jump history entry basing on the passed bpf_verifier_state. This replaces a "global" variable in bpf_verifier_env allowing to use push_jmp_history() for states other than env->cur_state.

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

---
 include/linux/bpf_verifier.h |  1 -
 kernel/bpf/verifier.c        | 34 ++++++++++++++++------------------
 2 files changed, 16 insertions(+), 19 deletions(-)

include/linux/bpf_verifier.h +0 -1

index 84365e6dd85d..cbfb235984c8 100644
@@ -705,7 +705,6 @@ struct bpf_verifier_env {
                int cur_stack;
        } cfg;
        struct backtrack_state bt;
-       struct bpf_jmp_history_entry *cur_hist_ent;
        u32 pass_cnt; /* number of times do_check() was called */
        u32 subprog_cnt;
        /* number of instructions analyzed by the verifier */

kernel/bpf/verifier.c +8 -0

index 011d54a1dc53..759ef089b33c 100644
@@ -3304,24 +3304,34 @@ static bool is_jmp_point(struct bpf_verifier_env *env, int insn_idx)
        return env->insn_aux_data[insn_idx].jmp_point;
 }
 
+static struct bpf_jmp_history_entry *get_jmp_hist_entry(struct bpf_verifier_state *st,
+                                                       u32 hist_end, int insn_idx)
+{
+       if (hist_end > 0 && st->jmp_history[hist_end - 1].idx == insn_idx)
+               return &st->jmp_history[hist_end - 1];
+       return NULL;
+}
+
 /* for any branch, call, exit record the history of jmps in the given state */

kernel/bpf/verifier.c +5 -18

        /* combine instruction flags if we already recorded this instruction */
-       if (env->cur_hist_ent) {
+       if (cur_hist_ent) {
                /* atomic instructions push insn_flags twice, for READ and
                 * WRITE sides, but they should agree on stack slot
                 */
-               WARN_ONCE((env->cur_hist_ent->flags & insn_flags) &&
-                         (env->cur_hist_ent->flags & insn_flags) != insn_flags,
+               WARN_ONCE((cur_hist_ent->flags & insn_flags) &&
+                         (cur_hist_ent->flags & insn_flags) != insn_flags,
                          "verifier insn history bug: insn_idx %d cur flags %x new flags %x\n",
-                         env->insn_idx, env->cur_hist_ent->flags, insn_flags);
-               env->cur_hist_ent->flags |= insn_flags;
+                         env->insn_idx, cur_hist_ent->flags, insn_flags);
+               cur_hist_ent->flags |= insn_flags;
                return 0;
        }
 

@@ -3337,19 +3347,10 @@ static int push_jmp_history(struct bpf_verifier_env *env, struct bpf_verifier_st
        p->prev_idx = env->prev_insn_idx;
        p->flags = insn_flags;
        cur->jmp_history_cnt = cnt;
-       env->cur_hist_ent = p;
 
        return 0;
 }
 
-static struct bpf_jmp_history_entry *get_jmp_hist_entry(struct bpf_verifier_state *st,
-                                                       u32 hist_end, int insn_idx)
-{
-       if (hist_end > 0 && st->jmp_history[hist_end - 1].idx == insn_idx)
-               return &st->jmp_history[hist_end - 1];
-       return NULL;
-}
-
 /* Backtrack one insn at a time. If idx is not at the top of recorded
  * history then previous instruction came from straight line execution.
  * Return -ENOENT if we exhausted all instructions within given state.

@@ -17437,9 +17438,6 @@ static int do_check(struct bpf_verifier_env *env)
                u8 class;
                int err;
 
-               /* reset current history entry on each new instruction */
-               env->cur_hist_ent = NULL;
-
                env->prev_insn_idx = prev_insn_idx;
                if (env->insn_idx >= insn_cnt) {
                        verbose(env, "invalid insn idx %d insn_cnt %d\n",
--

2.43.0

Quoted 25 lines

kernel/bpf/verifier.c +9 -1

index 011d54a1dc53..759ef089b33c 100644
@@ -3304,24 +3304,34 @@ static bool is_jmp_point(struct bpf_verifier_env *env, int insn_idx)
        return env->insn_aux_data[insn_idx].jmp_point;
 }
 
+static struct bpf_jmp_history_entry *get_jmp_hist_entry(struct bpf_verifier_state *st,
+                                                       u32 hist_end, int insn_idx)
+{
+       if (hist_end > 0 && st->jmp_history[hist_end - 1].idx == insn_idx)
+               return &st->jmp_history[hist_end - 1];
+       return NULL;
+}
+
 /* for any branch, call, exit record the history of jmps in the given state */
 static int push_jmp_history(struct bpf_verifier_env *env, struct bpf_verifier_state *cur,
                            int insn_flags)
 {
+       struct bpf_jmp_history_entry *p, *cur_hist_ent;
        u32 cnt = cur->jmp_history_cnt;
-       struct bpf_jmp_history_entry *p;
        size_t alloc_size;
 

kernel/bpf/verifier.c static bool is_jmp_point(struct bpf_verifier_env *env, int insn_idx) · line 3324

Quoted 2 lines

kernel/bpf/verifier.c +2 -0

+       cur_hist_ent = get_jmp_hist_entry(cur, cnt, env->insn_idx);
+

This is, generally speaking, not correct to do. You can have a tight loop where the instruction with the same insn_idx is executed multiple times and so we'll get multiple consecutive entries in jmp_history with the same insn_idx. We shouldn't reuse hist_ent for all of them, each simulated instruction execution should have its own entry in jump history.

It's fine to use get_jmp_hist_entry() in backtracking, though.

I'll look through the rest of patches more closely first before suggesting any alternatives. But what you do in this patch is not 100% correct.

Use bpf_verifier_state->jmp_history to track which registers were updated by find_equal_scalars() when conditional jump was verified. Use recorded information in backtrack_insn() to propagate precision.

E.g. for the following program:

while verifying instructions

  r1 = r0              |
  if r1 < 8  goto ...  | push r0,r1 as equal_scalars in jmp_history
  if r0 > 16 goto ...  | push r0,r1 as equal_scalars in jmp_history
  r2 = r10             |
  r2 += r0             v mark_chain_precision(r0)

while doing mark_chain_precision(r0)

  r1 = r0              ^
  if r1 < 8  goto ...  | mark r0,r1 as precise
  if r0 > 16 goto ...  | mark r0,r1 as precise
  r2 = r10             |
  r2 += r0             | mark r0 precise

Technically achieve this in following steps:
- Use 10 bits to identify each register that gains range because of find_equal_scalars():
- 3 bits for frame number;
- 6 bits for register or stack slot number;
- 1 bit to indicate if register is spilled.
- Use u64 as a vector of 6 such records + 4 bits for vector length.
- Augment struct bpf_jmp_history_entry with field 'equal_scalars' representing such vector.
- When doing check_cond_jmp_op() for remember up to 6 registers that gain range because of find_equal_scalars() in such a vector.
- Don't propagate range information and reset IDs for registers that don't fit in 6-value vector.
- Push collected vector to bpf_verifier_state->jmp_history for instruction index of conditional jump.
- When doing backtrack_insn() for conditional jumps
check if any of recorded equal scalars is currently marked precise, if so mark all equal recorded scalars as precise.

Fixes 904e6ddf4133 ("bpf: Use scalar ids in mark_chain_precision()")

Reported-by Hao Sun <[email protected]>

Closes https://lore.kernel.org/bpf/CAEf4BzZ0xidVCqB47XnkXcNhkPWF6_nTV7yt+_Lf0kcFEut2Mg@mail.gmail.com/ open here

Suggested-by Andrii Nakryiko <[email protected]>

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

---
 include/linux/bpf_verifier.h                  |   1 +
 kernel/bpf/verifier.c                         | 207 ++++++++++++++++--
 .../bpf/progs/verifier_subprog_precision.c    |   2 +-
 .../testing/selftests/bpf/verifier/precise.c  |   2 +-
 4 files changed, 195 insertions(+), 17 deletions(-)

include/linux/bpf_verifier.h +0 -0

index cbfb235984c8..26e32555711c 100644

include/linux/bpf_verifier.h +0 -0

 };
 
 /* Maximum number of register states that can exist at once */

kernel/bpf/verifier.c +60 -0

index 759ef089b33c..b95b6842703c 100644
@@ -3304,6 +3304,76 @@ static bool is_jmp_point(struct bpf_verifier_env *env, int insn_idx)
        return env->insn_aux_data[insn_idx].jmp_point;
 }
 
+#define ES_FRAMENO_BITS        3
+#define ES_SPI_BITS    6
+#define ES_ENTRY_BITS  (ES_SPI_BITS + ES_FRAMENO_BITS + 1)
+#define ES_SIZE_BITS   4
+#define ES_FRAMENO_MASK        ((1ul << ES_FRAMENO_BITS) - 1)
+#define ES_SPI_MASK    ((1ul << ES_SPI_BITS)     - 1)
+#define ES_SIZE_MASK   ((1ul << ES_SIZE_BITS)    - 1)
+#define ES_SPI_OFF     ES_FRAMENO_BITS
+#define ES_IS_REG_OFF  (ES_SPI_BITS + ES_FRAMENO_BITS)
+
+/* Pack one history entry for equal scalars as 10 bits in the following format:
+ * - 3-bits frameno
+ * - 6-bits spi_or_reg
+ * - 1-bit  is_reg
+ */
+static u64 equal_scalars_pack(u32 frameno, u32 spi_or_reg, bool is_reg)
+{
+       u64 val = 0;
+
+       val |= frameno & ES_FRAMENO_MASK;
+       val |= (spi_or_reg & ES_SPI_MASK) << ES_SPI_OFF;
+       val |= (is_reg ? 1 : 0) << ES_IS_REG_OFF;
+       return val;
+}
+
+static void equal_scalars_unpack(u64 val, u32 *frameno, u32 *spi_or_reg, bool *is_reg)
+{
+       *frameno    =  val & ES_FRAMENO_MASK;
+       *spi_or_reg = (val >> ES_SPI_OFF) & ES_SPI_MASK;
+       *is_reg     = (val >> ES_IS_REG_OFF) & 0x1;
+}
+
+static u32 equal_scalars_size(u64 equal_scalars)
+{
+       return equal_scalars & ES_SIZE_MASK;
+}
+
+/* Use u64 as a stack of 6 10-bit values, use first 4-bits to track
+ * number of elements currently in stack.
+ */
+static bool equal_scalars_push(u64 *equal_scalars, u32 frameno, u32 spi_or_reg, bool is_reg)
+{
+       u32 num;
+
+       num = equal_scalars_size(*equal_scalars);
+       if (num == 6)
+               return false;
+       *equal_scalars >>= ES_SIZE_BITS;
+       *equal_scalars <<= ES_ENTRY_BITS;
+       *equal_scalars |= equal_scalars_pack(frameno, spi_or_reg, is_reg);
+       *equal_scalars <<= ES_SIZE_BITS;
+       *equal_scalars |= num + 1;
+       return true;
+}
+
+static bool equal_scalars_pop(u64 *equal_scalars, u32 *frameno, u32 *spi_or_reg, bool *is_reg)
+{
+       u32 num;
+
+       num = equal_scalars_size(*equal_scalars);

kernel/bpf/verifier.c +0 -0

 static struct bpf_jmp_history_entry *get_jmp_hist_entry(struct bpf_verifier_state *st,
                                                        u32 hist_end, int insn_idx)
 {

Quoted 4 lines

include/linux/bpf_verifier.h +0 -0

index cbfb235984c8..26e32555711c 100644

include/linux/bpf_verifier.h struct bpf_jmp_history_entry { · line 364

Quoted 5 lines

include/linux/bpf_verifier.h +1 -0

@@ -361,6 +361,7 @@ struct bpf_jmp_history_entry {
        u32 prev_idx : 22;
        /* special flags, e.g., whether insn is doing register stack spill/load */
        u32 flags : 10;
+       u64 equal_scalars;

nit: should we call this concept as a bit more generic "linked registers" instead of "equal scalars"?

I'm wondering if this pop/push set of primitives is the best approach?

What if we had pack/unpack operations, where for various checking logic we'd be working with "unpacked" representation, e.g., something like this:

struct linked_reg_set {
    int cnt;
    struct {

        int frameno;
        union {
            int spi;
            int regno;
        };
        bool is_set;
        bool is_reg;
    } reg_set[6];
};

bt_set_equal_scalars() could accept struct linked_reg_set* instead of bitmask itself. Same for find_equal_scalars().

I think even implementation of packing/unpacking would be more straightforward and we won't even need all those ES_xxx consts (or at least fewer of them).

WDYT?

On Wed, 2024-02-28 at 11:58 -0800, Andrii Nakryiko wrote:
[...]

Quoted 4 lines

Quoted 4 lines

include/linux/bpf_verifier.h +0 -0

index cbfb235984c8..26e32555711c 100644

Quoted 8 lines

include/linux/bpf_verifier.h struct bpf_jmp_history_entry { · line 364

Quoted 5 lines

include/linux/bpf_verifier.h +1 -0

@@ -361,6 +361,7 @@ struct bpf_jmp_history_entry {
        u32 prev_idx : 22;
        /* special flags, e.g., whether insn is doing register stack spill/load */
        u32 flags : 10;
+       u64 equal_scalars;

nit: should we call this concept as a bit more generic "linked registers" instead of "equal scalars"?

It's a historical name for the feature and it is present in a few commit and tests. Agree that "linked_registers" is better in current context.
A bit reluctant but can change it here.

[...]

Quoted 1 line

I'm wondering if this pop/push set of primitives is the best approach?

I kinda like it :)

Quoted 7 lines

What if we had pack/unpack operations, where for various checking logic we'd be working with "unpacked" representation, e.g., something like this:

struct linked_reg_set {
    int cnt;
    struct {

Will need a name here, otherwise iteration would be somewhat inconvenient. Suppose 'struct reg_or_spill'.

Quoted 10 lines

        int frameno;
        union {
            int spi;
            int regno;
        };
        bool is_set;
        bool is_reg;
    } reg_set[6];
};

Quoted 2 lines

bt_set_equal_scalars() could accept struct linked_reg_set* instead of bitmask itself. Same for find_equal_scalars().

For clients it would be

        while (equal_scalars_pop(&equal_scalars, &fr, &spi, &is_reg)) {
                if ((is_reg && bt_is_frame_reg_set(bt, fr, spi)) ||
                    (!is_reg && bt_is_frame_slot_set(bt, fr, spi)))
                    ...
        }

    --- vs ---

        for (i = 0; i < equal_scalars->cnt; ++i) {
                struct reg_or_spill *r = equal_scalars->reg_set[i];

                if ((r->is_reg && bt_is_frame_reg_set(bt, r->frameno, r->regno)) ||
                    (!r->is_reg && bt_is_frame_slot_set(bt, r->frameno, r->spi)))
                    ...
        }

I'd say, no significant difference.

Quoted 6 lines

I think even implementation of packing/unpacking would be more straightforward and we won't even need all those ES_xxx consts (or at least fewer of them).

WDYT?

I wouldn't say it simplifies packing/unpacking much. Below is the code using new data structure and it's like 59 lines old version vs 56 lines new version.

--- 8< ----------------------------------------------------------------

struct reg_or_spill {
        int frameno;
        union {
                int spi;
                int regno;
        };
        bool is_reg;
};

struct linked_reg_set {
        int cnt;
        struct reg_or_spill reg_set[6];
};

/* Pack one history entry for equal scalars as 10 bits in the following format:
* - 3-bits frameno
* - 6-bits spi_or_reg
* - 1-bit is_reg
*/
static u64 linked_reg_set_pack(struct linked_reg_set *s)

{
        u64 val = 0;
        int i;

        for (i = 0; i < s->cnt; ++i) {
                struct reg_or_spill *r = &s->reg_set[i];
                u64 tmp = 0;

                tmp |= r->frameno & ES_FRAMENO_MASK;
                tmp |= (r->spi & ES_SPI_MASK) << ES_SPI_OFF;

                tmp |= (r->is_reg ? 1 : 0) << ES_IS_REG_OFF;

                val <<= ES_ENTRY_BITS;
                val |= tmp;

        }
        val <<= ES_SIZE_BITS;
        val |= s->cnt;
        return val;
}

static void linked_reg_set_unpack(u64 val, struct linked_reg_set *s)

{
        int i;

        s->cnt = val & ES_SIZE_MASK;
        val >>= ES_SIZE_BITS;

        for (i = 0; i < s->cnt; ++i) {
                struct reg_or_spill *r = &s->reg_set[i];

                r->frameno =  val & ES_FRAMENO_MASK;
                r->spi     = (val >> ES_SPI_OFF) & ES_SPI_MASK;
                r->is_reg  = (val >> ES_IS_REG_OFF) & 0x1;
                val >>= ES_ENTRY_BITS;
        }
}

---------------------------------------------------------------- >8 ---

I'd say it's not about a number of lines, it's about ease of understanding, reasoning, and using these helpers.

I do prefer the code you wrote below, but I'm not going to die on this hill if you insist. I'll go think about the rest of the logic.

Quoted 9 lines

static u64 linked_reg_set_pack(struct linked_reg_set *s)

{
        u64 val = 0;
        int i;

        for (i = 0; i < s->cnt; ++i) {
                struct reg_or_spill *r = &s->reg_set[i];
                u64 tmp = 0;

Quoted 2 lines

                tmp |= r->frameno & ES_FRAMENO_MASK;
                tmp |= (r->spi & ES_SPI_MASK) << ES_SPI_OFF;

nit: we shouldn't mask anything here, it just makes an impression that r->frameno can be bigger than we have bits for it in a bitmask

On Wed, 2024-02-28 at 11:58 -0800, Andrii Nakryiko wrote:
[...]

Quoted 4 lines

Quoted 4 lines

include/linux/bpf_verifier.h +0 -0

index cbfb235984c8..26e32555711c 100644

Quoted 8 lines

include/linux/bpf_verifier.h struct bpf_jmp_history_entry { · line 364

Quoted 5 lines

include/linux/bpf_verifier.h +1 -0

@@ -361,6 +361,7 @@ struct bpf_jmp_history_entry {
        u32 prev_idx : 22;
        /* special flags, e.g., whether insn is doing register stack spill/load */
        u32 flags : 10;
+       u64 equal_scalars;

nit: should we call this concept as a bit more generic "linked registers" instead of "equal scalars"?

It's a historical name for the feature and it is present in a few commit and tests. Agree that "linked_registers" is better in current context.
A bit reluctant but can change it here.

[...]

Use bpf_verifier_state->jmp_history to track which registers were updated by find_equal_scalars() when conditional jump was verified. Use recorded information in backtrack_insn() to propagate precision.

E.g. for the following program:

while verifying instructions

  r1 = r0              |
  if r1 < 8  goto ...  | push r0,r1 as equal_scalars in jmp_history
  if r0 > 16 goto ...  | push r0,r1 as equal_scalars in jmp_history
  r2 = r10             |
  r2 += r0             v mark_chain_precision(r0)

while doing mark_chain_precision(r0)

  r1 = r0              ^
  if r1 < 8  goto ...  | mark r0,r1 as precise
  if r0 > 16 goto ...  | mark r0,r1 as precise
  r2 = r10             |
  r2 += r0             | mark r0 precise

Technically achieve this in following steps:
- Use 10 bits to identify each register that gains range because of find_equal_scalars():
- 3 bits for frame number;
- 6 bits for register or stack slot number;
- 1 bit to indicate if register is spilled.
- Use u64 as a vector of 6 such records + 4 bits for vector length.
- Augment struct bpf_jmp_history_entry with field 'equal_scalars' representing such vector.
- When doing check_cond_jmp_op() for remember up to 6 registers that gain range because of find_equal_scalars() in such a vector.
- Don't propagate range information and reset IDs for registers that don't fit in 6-value vector.
- Push collected vector to bpf_verifier_state->jmp_history for instruction index of conditional jump.
- When doing backtrack_insn() for conditional jumps
check if any of recorded equal scalars is currently marked precise, if so mark all equal recorded scalars as precise.

Fixes 904e6ddf4133 ("bpf: Use scalar ids in mark_chain_precision()")

Reported-by Hao Sun <[email protected]>

Closes https://lore.kernel.org/bpf/CAEf4BzZ0xidVCqB47XnkXcNhkPWF6_nTV7yt+_Lf0kcFEut2Mg@mail.gmail.com/ open here

Suggested-by Andrii Nakryiko <[email protected]>

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

---
 include/linux/bpf_verifier.h                  |   1 +
 kernel/bpf/verifier.c                         | 207 ++++++++++++++++--
 .../bpf/progs/verifier_subprog_precision.c    |   2 +-
 .../testing/selftests/bpf/verifier/precise.c  |   2 +-
 4 files changed, 195 insertions(+), 17 deletions(-)

include/linux/bpf_verifier.h +1 -0

index cbfb235984c8..26e32555711c 100644
@@ -361,6 +361,7 @@ struct bpf_jmp_history_entry {
        u32 prev_idx : 22;
        /* special flags, e.g., whether insn is doing register stack spill/load */
        u32 flags : 10;
+       u64 equal_scalars;
 };
 

include/linux/bpf_verifier.h +1 -1

@@ -3314,7 +3384,7 @@ static struct bpf_jmp_history_entry *get_jmp_hist_entry(struct bpf_verifier_stat
 
 /* for any branch, call, exit record the history of jmps in the given state */
 static int push_jmp_history(struct bpf_verifier_env *env, struct bpf_verifier_state *cur,
-                           int insn_flags)
+                           int insn_flags, u64 equal_scalars)
 {
        struct bpf_jmp_history_entry *p, *cur_hist_ent;
        u32 cnt = cur->jmp_history_cnt;

include/linux/bpf_verifier.h +2 -0

+               cur_hist_ent->equal_scalars = equal_scalars;
                return 0;
        }
 

@@ -3346,6 +3422,7 @@ static int push_jmp_history(struct bpf_verifier_env *env, struct bpf_verifier_st
        p->idx = env->insn_idx;
        p->prev_idx = env->prev_insn_idx;
        p->flags = insn_flags;
+       p->equal_scalars = equal_scalars;
        cur->jmp_history_cnt = cnt;
 
        return 0;

static bool calls_callback(struct bpf_verifier_env *env, int insn_idx);

/* For given verifier state backtrack_insn() is called from the last insn to

include/linux/bpf_verifier.h +1 -0

@@ -3802,6 +3917,7 @@ static int backtrack_insn(struct bpf_verifier_env *env, int idx, int subseq_idx,
                         */
                        return 0;
                } else if (BPF_SRC(insn->code) == BPF_X) {
+                       bt_set_equal_scalars(bt, hist);
                        if (!bt_is_reg_set(bt, dreg) && !bt_is_reg_set(bt, sreg))
                                return 0;
                        /* dreg <cond> sreg

include/linux/bpf_verifier.h +1 -1

                         /* else dreg <cond> K
                          * Only dreg still needs precision before
                          * this insn, so for the K-based conditional

@@ -4579,7 +4698,7 @@ static int check_stack_write_fixed_off(struct bpf_verifier_env *env,
        }
 
        if (insn_flags)
-               return push_jmp_history(env, env->cur_state, insn_flags);
+               return push_jmp_history(env, env->cur_state, insn_flags, 0);
        return 0;
 }
 

kernel/bpf/verifier.c static int push_jmp_history(struct bpf_verifier_env *env, struct bpf_verifier_st · line 3409

Quoted 9 lines

kernel/bpf/verifier.c +5 -0

@@ -3332,6 +3402,12 @@ static int push_jmp_history(struct bpf_verifier_env *env, struct bpf_verifier_st
                          "verifier insn history bug: insn_idx %d cur flags %x new flags %x\n",
                          env->insn_idx, cur_hist_ent->flags, insn_flags);
                cur_hist_ent->flags |= insn_flags;
+               if (cur_hist_ent->equal_scalars != 0) {
+                       verbose(env, "verifier bug: insn_idx %d equal_scalars != 0: %#llx\n",
+                               env->insn_idx, cur_hist_ent->equal_scalars);
+                       return -EFAULT;
+               }

let's do WARN_ONCE() just like we do for flags? why deviating?

Quoted 13 lines

kernel/bpf/verifier.c +1 -0

 /* For given verifier state backtrack_insn() is called from the last insn to

@@ -3802,6 +3917,7 @@ static int backtrack_insn(struct bpf_verifier_env *env, int idx, int subseq_idx,
                         */
                        return 0;
                } else if (BPF_SRC(insn->code) == BPF_X) {
+                       bt_set_equal_scalars(bt, hist);
                        if (!bt_is_reg_set(bt, dreg) && !bt_is_reg_set(bt, sreg))
                                return 0;
                        /* dreg <cond> sreg

@@ -3812,6 +3928,9 @@ static int backtrack_insn(struct bpf_verifier_env *env, int idx, int subseq_idx,
                         */
                        bt_set_reg(bt, dreg);
                        bt_set_reg(bt, sreg);

kernel/bpf/verifier.c static int backtrack_insn(struct bpf_verifier_env *env, int idx, int subseq_idx, · line 3933

Quoted 3 lines

kernel/bpf/verifier.c +3 -0

+                       bt_set_equal_scalars(bt, hist);
+               } else if (BPF_SRC(insn->code) == BPF_K) {
+                       bt_set_equal_scalars(bt, hist);

Can you please elaborate why we are doing bt_set_equal_scalars() in these three places and not everywhere else? I'm trying to understand whether we should do it more generically for any instruction either before or after all the bt_set_xxx() calls...

Quoted 4 lines

kernel/bpf/verifier.c +0 -0

                         /* else dreg <cond> K
                          * Only dreg still needs precision before
                          * this insn, so for the K-based conditional

On Wed, 2024-02-28 at 15:01 -0800, Andrii Nakryiko wrote:
[...]

Quoted 11 lines

kernel/bpf/verifier.c static int push_jmp_history(struct bpf_verifier_env *env, struct bpf_verifier_st · line 3409

Quoted 9 lines

kernel/bpf/verifier.c +5 -0

@@ -3332,6 +3402,12 @@ static int push_jmp_history(struct bpf_verifier_env *env, struct bpf_verifier_st
                          "verifier insn history bug: insn_idx %d cur flags %x new flags %x\n",
                          env->insn_idx, cur_hist_ent->flags, insn_flags);
                cur_hist_ent->flags |= insn_flags;
+               if (cur_hist_ent->equal_scalars != 0) {
+                       verbose(env, "verifier bug: insn_idx %d equal_scalars != 0: %#llx\n",
+                               env->insn_idx, cur_hist_ent->equal_scalars);
+                       return -EFAULT;
+               }

let's do WARN_ONCE() just like we do for flags? why deviating?

Ok

[...]

Quoted 13 lines

Quoted 13 lines

kernel/bpf/verifier.c +1 -0

 /* For given verifier state backtrack_insn() is called from the last insn to

@@ -3802,6 +3917,7 @@ static int backtrack_insn(struct bpf_verifier_env *env, int idx, int subseq_idx,
                         */
                        return 0;
                } else if (BPF_SRC(insn->code) == BPF_X) {
+                       bt_set_equal_scalars(bt, hist);
                        if (!bt_is_reg_set(bt, dreg) && !bt_is_reg_set(bt, sreg))
                                return 0;
                        /* dreg <cond> sreg

@@ -3812,6 +3928,9 @@ static int backtrack_insn(struct bpf_verifier_env *env, int idx, int subseq_idx,
                         */
                        bt_set_reg(bt, dreg);
                        bt_set_reg(bt, sreg);

Quoted 8 lines

kernel/bpf/verifier.c static int backtrack_insn(struct bpf_verifier_env *env, int idx, int subseq_idx, · line 3933

Quoted 3 lines

kernel/bpf/verifier.c +3 -0

+                       bt_set_equal_scalars(bt, hist);
+               } else if (BPF_SRC(insn->code) == BPF_K) {
+                       bt_set_equal_scalars(bt, hist);

Can you please elaborate why we are doing bt_set_equal_scalars() in these three places and not everywhere else? I'm trying to understand whether we should do it more generically for any instruction either before or after all the bt_set_xxx() calls...

The before call for BPF_X is for situation when dreg/sreg are not yet tracked precise but one of the registers that gained range because of this 'if' is already tracked.

The after call for BPF_X is for situation when say dreg is already tracked precise but sreg is not and there are some registers had same id as sreg, that gained range when this 'if' was processed. The equal_scalars_bpf_x_dst() test case covers this situation. Here it is for your convenience:

    /* Registers r{0,1,2} share same ID when 'if r1 > r3' insn is processed,
     * check that verifier marks r{0,1,2} as precise while backtracking
     * 'if r1 > r3' with r3 already marked.
     */
    SEC("socket")
    __success __log_level(2)
    __flag(BPF_F_TEST_STATE_FREQ)
    __msg("frame0: regs=r3 stack= before 5: (2d) if r1 > r3 goto pc+0")
    __msg("frame0: parent state regs=r0,r1,r2,r3 stack=:")
    __msg("frame0: regs=r0,r1,r2,r3 stack= before 4: (b7) r3 = 7")
    __naked void equal_scalars_bpf_x_dst(void)
    {
        asm volatile (
        /* r0 = random number up to 0xff */
        "call %[bpf_ktime_get_ns];"
        "r0 &= 0xff;"
        /* tie r0.id == r1.id == r2.id */
        "r1 = r0;"
        "r2 = r0;"
        "r3 = 7;"
        "if r1 > r3 goto +0;"
        /* force r0 to be precise, this eventually marks r1 and r2 as
         * precise as well because of shared IDs
         */
        "r4 = r10;"
        "r4 += r3;"
        "r0 = 0;"
        "exit;"
        :
        : __imm(bpf_ktime_get_ns)
        : __clobber_all);
    }

The before call for BPF_K is the same as before call for BPF_X: for situation when dreg is not yet tracked precise, but one of the registers that gained range because of this 'if' is already tracked.

The calls are placed at point where conditional jumps are processed because 'equal_scalars' are only recorded for conditional jumps.

Quoted 5 lines

Quoted 5 lines

kernel/bpf/verifier.c +0 -0

                         /* else dreg <cond> K
                          * Only dreg still needs precision before
                          * this insn, so for the K-based conditional

[...]

As I mentioned in offline conversation, I wonder if it's better and less error-prone to do linked register processing in backtrack_insn() not just for conditional jumps, for all instructions? Whenever we currently do bpf_set_reg(), we can first check if there are linked registers and they contain a register we are about to set precise. If that's the case, set all of them precise.

That would make it unnecessary to have this "before BPF_X|BPF_K" checks, I think.

It might be sufficient to process just conditional jumps given today's use of linked registers, but is there any downside to doing it across all instructions? Are you worried about regression in number of states due to precision? Or performance?

On Fri, 2024-03-01 at 09:34 -0800, Andrii Nakryiko wrote:
[...]

Quoted 7 lines

As I mentioned in offline conversation, I wonder if it's better and less error-prone to do linked register processing in backtrack_insn() not just for conditional jumps, for all instructions? Whenever we currently do bpf_set_reg(), we can first check if there are linked registers and they contain a register we are about to set precise. If that's the case, set all of them precise.

Quoted 2 lines

That would make it unnecessary to have this "before BPF_X|BPF_K" checks, I think.

It should not be a problem to do bt_set_equal_scalars() at the beginning of backtrack_insn().
Same way, I can put the after call at the end of backtrack_insn(). Is this what you have in mind?

Quoted 5 lines

It might be sufficient to process just conditional jumps given today's use of linked registers, but is there any downside to doing it across all instructions? Are you worried about regression in number of states due to precision? Or performance?

Changing position for bt_set_equal_scalars() calls should not affect anything semantically at the moment. Changes to backtracking state would be done only if some linked registers are present in 'hist' and that would be true only for conditional jumps.
Maybe some more CPU cycles but I don't think that would be noticeable.