bpf: track find_equal_scalars history on per-instruction level

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 as follows:
- 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 'linked_regs' representing such vector.
- When doing check_cond_jmp_op() 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 a pair {instruction index, equal scalars vector} to bpf_verifier_state->jmp_history.
- When doing backtrack_insn() check if any of recorded linked registers is currently marked precise, if so mark all linked registers as precise.

This also requires fixes for two test_verifier tests:
- precise: test 1
- precise: test 2

Both tests contain the following instruction sequence:

19: (bf) r2 = r9 ; R2=scalar(id=3) R9=scalar(id=3)
20: (a5) if r2 < 0x8 goto pc+1 ; R2=scalar(id=3,umin=8)
21: (95) exit

22: (07) r2 += 1                      ; R2_w=scalar(id=3+1,...)
23: (bf) r1 = r10                     ; R1_w=fp0 R10=fp0
24: (07) r1 += -8                     ; R1_w=fp-8
25: (b7) r3 = 0                       ; R3_w=0

26: (85) call bpf_probe_read_kernel#113

The call to bpf_probe_read_kernel() at (26) forces r2 to be precise. Previously, this forced all registers with same id to become precise immediately when mark_chain_precision() is called.
After this change, the precision is propagated to registers sharing same id only when 'if' instruction is backtracked.
Hence verification log for both tests is changed:
regs=r2,r9 -> regs=r2 for instructions 25..20.

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                  |   4 +
 kernel/bpf/verifier.c                         | 231 ++++++++++++++++--
 .../bpf/progs/verifier_subprog_precision.c    |   2 +-
 .../testing/selftests/bpf/verifier/precise.c  |  20 +-
 4 files changed, 232 insertions(+), 25 deletions(-)

include/linux/bpf_verifier.h +4 -0

index 2b54e25d2364..da450552c278 100644
@@ -371,6 +371,10 @@ struct bpf_jmp_history_entry {
        u32 prev_idx : 22;
        /* special flags, e.g., whether insn is doing register stack spill/load */
        u32 flags : 10;
+       /* additional registers that need precision tracking when this
+        * jump is backtracked, vector of six 10-bit records
+        */
+       u64 linked_regs;
 };
 
 /* Maximum number of register states that can exist at once */

kernel/bpf/verifier.c +0 -0

index e25ad5fb9115..ec493360607e 100644

kernel/bpf/verifier.c +6 -0

+
+struct linked_regs {
+       int cnt;
+       struct reg_or_spill entries[LINKED_REGS_MAX];
+};
+

kernel/bpf/verifier.c +6 -0

@@ -3615,6 +3739,12 @@ static int backtrack_insn(struct bpf_verifier_env *env, int idx, int subseq_idx,
                print_bpf_insn(&cbs, insn, env->allow_ptr_leaks);
        }
 
+       /* If there is a history record that some registers gained range at this insn,
+        * propagate precision marks to those registers, so that bt_is_reg_set()
+        * accounts for these registers.
+        */
+       bt_sync_linked_regs(bt, hist);
+
        if (class == BPF_ALU || class == BPF_ALU64) {
                if (!bt_is_reg_set(bt, dreg))
                        return 0;

kernel/bpf/verifier.c +2 -2

        return 0;
 }
 

@@ -4624,7 +4759,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;
 }
 

@@ -4929,7 +5064,7 @@ static int check_stack_read_fixed_off(struct bpf_verifier_env *env,
                insn_flags = 0; /* we are not restoring spilled register */
        }
        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 +12 -0

+               return;
+
+       e = linked_regs_push(reg_set);
+       if (e) {
+               e->frameno = frameno;
+               e->is_reg = is_reg;
+               e->regno = spi_or_reg;
+       } else {
+               reg->id = 0;
+       }
+}
+

kernel/bpf/verifier.c +0 -0

@@ -15312,6 +15500,21 @@ static int check_cond_jmp_op(struct bpf_verifier_env *env,
                return 0;
        }
 

kernel/bpf/verifier.c +5 -0

+               err = push_jmp_history(env, this_branch, 0, linked_regs_pack(&linked_regs));
+               if (err)
+                       return err;
+       }
+
        other_branch = push_stack(env, *insn_idx + insn->off + 1, *insn_idx,
                                  false);
        if (!other_branch)

kernel/bpf/verifier.c +2 -2

        }
        if (dst_reg->type == SCALAR_VALUE && dst_reg->id &&
            !WARN_ON_ONCE(dst_reg->id != other_branch_regs[insn->dst_reg].id)) {
-               find_equal_scalars(this_branch, dst_reg);
-               find_equal_scalars(other_branch, &other_branch_regs[insn->dst_reg]);
+               copy_known_reg(this_branch, dst_reg, &linked_regs);
+               copy_known_reg(other_branch, &other_branch_regs[insn->dst_reg], &linked_regs);
        }
 

Quoted 7 lines · Eduard Zingerman

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:

Quoted 4 lines

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

linked_scalars? especially now that Alexei added offsets between linked registers

Quoted 10 lines

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

let's reverse the order here so it's linear in how the algorithm actually works (backwards)?

Quoted 3 lines

Technically, achieve this as follows:
- Use 10 bits to identify each register that gains range because of find_equal_scalars():

should this be renamed to find_linked_scalars() nowadays?

Quoted 8 lines

kernel/bpf/verifier.c +0 -0

index e25ad5fb9115..ec493360607e 100644
@@ -3335,9 +3335,87 @@ static bool is_jmp_point(struct bpf_verifier_env *env, int insn_idx)
        return env->insn_aux_data[insn_idx].jmp_point;
 }
 

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

Quoted 7 lines

kernel/bpf/verifier.c +7 -0

+#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)

ull for 32-bit arches?

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

Quoted 3 lines

kernel/bpf/verifier.c +2 -0

+#define ES_SPI_OFF     ES_FRAMENO_BITS
+#define ES_IS_REG_OFF  (ES_SPI_BITS + ES_FRAMENO_BITS)

ES makes no sense now, no? LR or LINKREG or something along those lines?

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

Quoted 3 lines

kernel/bpf/verifier.c +3 -0

+#define LINKED_REGS_MAX        6
+
+struct reg_or_spill {

reg_or_spill -> linked_reg ?

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

Quoted 8 lines

kernel/bpf/verifier.c +7 -0

+       u8 frameno:3;
+       union {
+               u8 spi:6;
+               u8 regno:6;
+       };
+       bool is_reg:1;
+};

Do we need these bitfields for unpacked representation? It's going to use 2 bytes for this struct anyways. If you just use u8 for everything you end up with 3 bytes. Bitfields are a bit slower because the compiler will need to do more bit manipulations, so is it really worth it?

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

Quoted 6 lines

kernel/bpf/verifier.c +1 -0

@@ -3844,6 +3974,7 @@ static int backtrack_insn(struct bpf_verifier_env *env, int idx, int subseq_idx,
                         */
                        bt_set_reg(bt, dreg);
                        bt_set_reg(bt, sreg);
+               } else if (BPF_SRC(insn->code) == BPF_K) {
                         /* else dreg <cond> K

drop "else" from the comment then? I like this change.

Quoted 6 lines

kernel/bpf/verifier.c +0 -0

                          * Only dreg still needs precision before
                          * this insn, so for the K-based conditional

@@ -3862,6 +3993,10 @@ static int backtrack_insn(struct bpf_verifier_env *env, int idx, int subseq_idx,
                        /* to be analyzed */
                        return -ENOTSUPP;
        }

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

Quoted 4 lines

kernel/bpf/verifier.c +4 -0

+       /* Propagate precision marks to linked registers, to account for
+        * registers marked as precise in this function.
+        */
+       bt_sync_linked_regs(bt, hist);

Radical Andrii is fine with this, though I wonder if there is some place outside of backtrack_insn() where the first bt_sync_linked_regs() could be called just once?

But regardless, this is only mildly expensive when we do have linked registers, so unlikely to have any noticeable performance effect.

kernel/bpf/verifier.c static bool try_match_pkt_pointers(const struct bpf_insn *insn, · line 15293

Quoted 8 lines

kernel/bpf/verifier.c +2 -2

@@ -15154,14 +15289,66 @@ static bool try_match_pkt_pointers(const struct bpf_insn *insn,
        return true;
 }
 
-static void find_equal_scalars(struct bpf_verifier_state *vstate,
-                              struct bpf_reg_state *known_reg)
+static void __find_equal_scalars(struct linked_regs *reg_set, struct bpf_reg_state *reg,
+                                u32 id, u32 frameno, u32 spi_or_reg, bool is_reg)

we should abandon "equal scalars" terminology, they don't have to be equal, they are just linked together (potentially with a fixed difference between them)

how about "collect_linked_regs"?

Quoted 4 lines

kernel/bpf/verifier.c +0 -0

@@ -15312,6 +15500,21 @@ static int check_cond_jmp_op(struct bpf_verifier_env *env,
                return 0;
        }
 

kernel/bpf/verifier.c static int check_cond_jmp_op(struct bpf_verifier_env *env, · line 15512

Quoted 10 lines

kernel/bpf/verifier.c +10 -0

+       /* Push scalar registers sharing same ID to jump history,
+        * do this before creating 'other_branch', so that both
+        * 'this_branch' and 'other_branch' share this history
+        * if parent state is created.
+        */
+       if (BPF_SRC(insn->code) == BPF_X && src_reg->type == SCALAR_VALUE && src_reg->id)
+               find_equal_scalars(this_branch, src_reg->id, &linked_regs);
+       if (dst_reg->type == SCALAR_VALUE && dst_reg->id)
+               find_equal_scalars(this_branch, dst_reg->id, &linked_regs);
+       if (linked_regs.cnt > 1) {

if we have just one, should it be even marked as linked?

Quoted 12 lines

kernel/bpf/verifier.c +5 -0

+               err = push_jmp_history(env, this_branch, 0, linked_regs_pack(&linked_regs));
+               if (err)
+                       return err;
+       }
+
        other_branch = push_stack(env, *insn_idx + insn->off + 1, *insn_idx,
                                  false);
        if (!other_branch)

@@ -15336,13 +15539,13 @@ static int check_cond_jmp_op(struct bpf_verifier_env *env,
        if (BPF_SRC(insn->code) == BPF_X &&
            src_reg->type == SCALAR_VALUE && src_reg->id &&

kernel/bpf/verifier.c static int check_cond_jmp_op(struct bpf_verifier_env *env, · line 15543

Quoted 5 lines

kernel/bpf/verifier.c +2 -2

            !WARN_ON_ONCE(src_reg->id != other_branch_regs[insn->src_reg].id)) {
-               find_equal_scalars(this_branch, src_reg);
-               find_equal_scalars(other_branch, &other_branch_regs[insn->src_reg]);
+               copy_known_reg(this_branch, src_reg, &linked_regs);
+               copy_known_reg(other_branch, &other_branch_regs[insn->src_reg], &linked_regs);

I liked the "sync" terminology you used for bt, so why not call this "sync_linked_regs" ?

Quoted 8 lines · Andrii Nakryiko

Quoted 7 lines · Eduard Zingerman

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:

Quoted 7 lines

Quoted 4 lines

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

linked_scalars? especially now that Alexei added offsets between linked registers

Missed this, will update.

Quoted 11 lines

Quoted 10 lines

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

Quoted 2 lines

let's reverse the order here so it's linear in how the algorithm actually works (backwards)?

I thought the arrow would be enough. Ok, can reverse.

Quoted 8 lines

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

Quoted 6 lines

kernel/bpf/verifier.c +1 -0

@@ -3844,6 +3974,7 @@ static int backtrack_insn(struct bpf_verifier_env *env, int idx, int subseq_idx,
                         */
                        bt_set_reg(bt, dreg);
                        bt_set_reg(bt, sreg);
+               } else if (BPF_SRC(insn->code) == BPF_K) {
                         /* else dreg <cond> K

drop "else" from the comment then? I like this change.

This is actually a leftover from v1. I can drop "else" from the comment or drop this hunk as it is not necessary for the series.

Quoted 15 lines

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

Quoted 11 lines

kernel/bpf/verifier.c +4 -0

                          * Only dreg still needs precision before
                          * this insn, so for the K-based conditional

@@ -3862,6 +3993,10 @@ static int backtrack_insn(struct bpf_verifier_env *env, int idx, int subseq_idx,
                        /* to be analyzed */
                        return -ENOTSUPP;
        }
+       /* Propagate precision marks to linked registers, to account for
+        * registers marked as precise in this function.
+        */
+       bt_sync_linked_regs(bt, hist);

Radical Andrii is fine with this, though I wonder if there is some place outside of backtrack_insn() where the first bt_sync_linked_regs() could be called just once?

The problem here is that:
- in theory linked_regs could be present for any instruction, thus sync() is needed after get_jmp_hist_entry call in __mark_chain_precision();
- backtrack_insn() might both remove and add some registers in bt, hence, to correctly handle bt_empty() call in __mark_chain_precision the sync() is also needed after backtrack_insn().

So, current placement is the simplest I could come up with.

Quoted 4 lines

Quoted 4 lines

kernel/bpf/verifier.c +0 -0

@@ -15312,6 +15500,21 @@ static int check_cond_jmp_op(struct bpf_verifier_env *env,
                return 0;
        }
 

Quoted 12 lines

kernel/bpf/verifier.c static int check_cond_jmp_op(struct bpf_verifier_env *env, · line 15512

Quoted 10 lines

kernel/bpf/verifier.c +10 -0

+       /* Push scalar registers sharing same ID to jump history,
+        * do this before creating 'other_branch', so that both
+        * 'this_branch' and 'other_branch' share this history
+        * if parent state is created.
+        */
+       if (BPF_SRC(insn->code) == BPF_X && src_reg->type == SCALAR_VALUE && src_reg->id)
+               find_equal_scalars(this_branch, src_reg->id, &linked_regs);
+       if (dst_reg->type == SCALAR_VALUE && dst_reg->id)
+               find_equal_scalars(this_branch, dst_reg->id, &linked_regs);
+       if (linked_regs.cnt > 1) {

if we have just one, should it be even marked as linked?

Sorry, I don't understand. Do you suggest to add an additional check in find_equal_scalars/collect_linked_regs and reset it if 'cnt' equals 1?

[...]

Quoted 12 lines

Quoted 12 lines

kernel/bpf/verifier.c +5 -0

+               err = push_jmp_history(env, this_branch, 0, linked_regs_pack(&linked_regs));
+               if (err)
+                       return err;
+       }
+
        other_branch = push_stack(env, *insn_idx + insn->off + 1, *insn_idx,
                                  false);
        if (!other_branch)

@@ -15336,13 +15539,13 @@ static int check_cond_jmp_op(struct bpf_verifier_env *env,
        if (BPF_SRC(insn->code) == BPF_X &&
            src_reg->type == SCALAR_VALUE && src_reg->id &&

Quoted 8 lines

kernel/bpf/verifier.c static int check_cond_jmp_op(struct bpf_verifier_env *env, · line 15543

Quoted 5 lines

kernel/bpf/verifier.c +2 -2

            !WARN_ON_ONCE(src_reg->id != other_branch_regs[insn->src_reg].id)) {
-               find_equal_scalars(this_branch, src_reg);
-               find_equal_scalars(other_branch, &other_branch_regs[insn->src_reg]);
+               copy_known_reg(this_branch, src_reg, &linked_regs);
+               copy_known_reg(other_branch, &other_branch_regs[insn->src_reg], &linked_regs);

I liked the "sync" terminology you used for bt, so why not call this "sync_linked_regs" ?

I kept the current name for the function.
Suggested name makes sense, though.

[...]

Quoted 13 lines

Quoted 12 lines

Quoted 9 lines

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

let's reverse the order here so it's linear in how the algorithm actually works (backwards)?

Quoted 1 line

I thought the arrow would be enough. Ok, can reverse.

it's the reverse order compared to what you'd see in the verifier log. I did see the arrow (though it wasn't all that clear on the first reading), but still feels like it would be better to have consistent order with verifier log

[...]

Quoted 9 lines

Quoted 8 lines

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

Quoted 6 lines

kernel/bpf/verifier.c +1 -0

@@ -3844,6 +3974,7 @@ static int backtrack_insn(struct bpf_verifier_env *env, int idx, int subseq_idx,
                         */
                        bt_set_reg(bt, dreg);
                        bt_set_reg(bt, sreg);
+               } else if (BPF_SRC(insn->code) == BPF_K) {
                         /* else dreg <cond> K

drop "else" from the comment then? I like this change.

Quoted 2 lines

This is actually a leftover from v1. I can drop "else" from the comment or drop this hunk as it is not necessary for the series.

I'd keep explicit else if

Quoted 17 lines

Quoted 4 lines

Quoted 4 lines

kernel/bpf/verifier.c +0 -0

@@ -15312,6 +15500,21 @@ static int check_cond_jmp_op(struct bpf_verifier_env *env,
                return 0;
        }
 

Quoted 12 lines

kernel/bpf/verifier.c static int check_cond_jmp_op(struct bpf_verifier_env *env, · line 15512

Quoted 10 lines

kernel/bpf/verifier.c +10 -0

+       /* Push scalar registers sharing same ID to jump history,
+        * do this before creating 'other_branch', so that both
+        * 'this_branch' and 'other_branch' share this history
+        * if parent state is created.
+        */
+       if (BPF_SRC(insn->code) == BPF_X && src_reg->type == SCALAR_VALUE && src_reg->id)
+               find_equal_scalars(this_branch, src_reg->id, &linked_regs);
+       if (dst_reg->type == SCALAR_VALUE && dst_reg->id)
+               find_equal_scalars(this_branch, dst_reg->id, &linked_regs);
+       if (linked_regs.cnt > 1) {

if we have just one, should it be even marked as linked?

Quoted 2 lines

Sorry, I don't understand. Do you suggest to add an additional check in find_equal_scalars/collect_linked_regs and reset it if 'cnt' equals 1?

I find if (linked_regs.cnt > 1) check a bit weird and it feels like it should be unnecessary. As soon as we are left with just one "linked" register (linked with what? with itself?) it shouldn't be linked anymore. Is there a point where we break the link between registers where we can/should drop ID from the singularly linked register? Why keep that scalar register ID set?

On Tue, 2024-07-09 at 22:28 -0700, Andrii Nakryiko wrote:

[...]

Quoted 13 lines

Quoted 13 lines

Quoted 12 lines

Quoted 9 lines

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

let's reverse the order here so it's linear in how the algorithm actually works (backwards)?

Quoted 6 lines

Quoted 1 line

I thought the arrow would be enough. Ok, can reverse.

it's the reverse order compared to what you'd see in the verifier log. I did see the arrow (though it wasn't all that clear on the first reading), but still feels like it would be better to have consistent order with verifier log

Ok, no problem

Quoted 12 lines

[...]

Quoted 9 lines

Quoted 8 lines

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

Quoted 6 lines

kernel/bpf/verifier.c +1 -0

@@ -3844,6 +3974,7 @@ static int backtrack_insn(struct bpf_verifier_env *env, int idx, int subseq_idx,
                         */
                        bt_set_reg(bt, dreg);
                        bt_set_reg(bt, sreg);
+               } else if (BPF_SRC(insn->code) == BPF_K) {
                         /* else dreg <cond> K

drop "else" from the comment then? I like this change.

Quoted 4 lines

Quoted 2 lines

This is actually a leftover from v1. I can drop "else" from the comment or drop this hunk as it is not necessary for the series.

I'd keep explicit else if

Ok, will do

[...]

Quoted 20 lines

Quoted 17 lines

Quoted 4 lines

Quoted 4 lines

kernel/bpf/verifier.c +0 -0

@@ -15312,6 +15500,21 @@ static int check_cond_jmp_op(struct bpf_verifier_env *env,
                return 0;
        }
 

Quoted 12 lines

kernel/bpf/verifier.c static int check_cond_jmp_op(struct bpf_verifier_env *env, · line 15512

Quoted 10 lines

kernel/bpf/verifier.c +10 -0

+       /* Push scalar registers sharing same ID to jump history,
+        * do this before creating 'other_branch', so that both
+        * 'this_branch' and 'other_branch' share this history
+        * if parent state is created.
+        */
+       if (BPF_SRC(insn->code) == BPF_X && src_reg->type == SCALAR_VALUE && src_reg->id)
+               find_equal_scalars(this_branch, src_reg->id, &linked_regs);
+       if (dst_reg->type == SCALAR_VALUE && dst_reg->id)
+               find_equal_scalars(this_branch, dst_reg->id, &linked_regs);
+       if (linked_regs.cnt > 1) {

if we have just one, should it be even marked as linked?

Quoted 2 lines

Sorry, I don't understand. Do you suggest to add an additional check in find_equal_scalars/collect_linked_regs and reset it if 'cnt' equals 1?

Quoted 6 lines

I find if (linked_regs.cnt > 1) check a bit weird and it feels like it should be unnecessary. As soon as we are left with just one "linked" register (linked with what? with itself?) it shouldn't be linked anymore. Is there a point where we break the link between registers where we can/should drop ID from the singularly linked register? Why keep that scalar register ID set?

I can push this check inside find_equal_scalars/collect_linked_regs, e.g.:

collect_linked_regs(... linked_regs ...)

{
        ...
        if (linked_regs.cnt == 1)
                linked_regs.cnt = 0;

        ...
}

But then this particular place would have to be modified as follows:

        if (linked_regs.cnt > 0) {

                err = push_jmp_history(env, this_branch, 0, linked_regs_pack(&linked_regs));
                if (err)
                        return err;
        }

Or something similar has to be done inside push_jmp_history().

[...]