* [PATCH bpf-next 1/4] bpf: replace env->cur_hist_ent with a getter function
2024-02-22 0:50 [PATCH bpf-next 0/4] bpf: track find_equal_scalars history on per-instruction level Eduard Zingerman
@ 2024-02-22 0:50 ` Eduard Zingerman
2024-02-28 19:46 ` Andrii Nakryiko
2024-02-22 0:50 ` [PATCH bpf-next 2/4] bpf: track find_equal_scalars history on per-instruction level Eduard Zingerman
` (2 subsequent siblings)
3 siblings, 1 reply; 17+ messages in thread
From: Eduard Zingerman @ 2024-02-22 0:50 UTC (permalink / raw)
To: bpf, ast
Cc: andrii, daniel, martin.lau, kernel-team, yonghong.song,
sunhao.th, Eduard Zingerman
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 <eddyz87@gmail.com>
---
include/linux/bpf_verifier.h | 1 -
kernel/bpf/verifier.c | 34 ++++++++++++++++------------------
2 files changed, 16 insertions(+), 19 deletions(-)
diff --git a/include/linux/bpf_verifier.h b/include/linux/bpf_verifier.h
index 84365e6dd85d..cbfb235984c8 100644
--- a/include/linux/bpf_verifier.h
+++ b/include/linux/bpf_verifier.h
@@ -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 */
diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c
index 011d54a1dc53..759ef089b33c 100644
--- a/kernel/bpf/verifier.c
+++ b/kernel/bpf/verifier.c
@@ -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;
+ cur_hist_ent = get_jmp_hist_entry(cur, cnt, env->insn_idx);
+
/* 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
^ permalink raw reply related [flat|nested] 17+ messages in thread
* Re: [PATCH bpf-next 1/4] bpf: replace env->cur_hist_ent with a getter function
2024-02-22 0:50 ` [PATCH bpf-next 1/4] bpf: replace env->cur_hist_ent with a getter function Eduard Zingerman
@ 2024-02-28 19:46 ` Andrii Nakryiko
2024-02-28 21:23 ` Eduard Zingerman
0 siblings, 1 reply; 17+ messages in thread
From: Andrii Nakryiko @ 2024-02-28 19:46 UTC (permalink / raw)
To: Eduard Zingerman
Cc: bpf, ast, andrii, daniel, martin.lau, kernel-team, yonghong.song,
sunhao.th
On Wed, Feb 21, 2024 at 4:50 PM Eduard Zingerman <eddyz87@gmail.com> wrote:
>
> 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 <eddyz87@gmail.com>
> ---
> include/linux/bpf_verifier.h | 1 -
> kernel/bpf/verifier.c | 34 ++++++++++++++++------------------
> 2 files changed, 16 insertions(+), 19 deletions(-)
>
> diff --git a/include/linux/bpf_verifier.h b/include/linux/bpf_verifier.h
> index 84365e6dd85d..cbfb235984c8 100644
> --- a/include/linux/bpf_verifier.h
> +++ b/include/linux/bpf_verifier.h
> @@ -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 */
> diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c
> index 011d54a1dc53..759ef089b33c 100644
> --- a/kernel/bpf/verifier.c
> +++ b/kernel/bpf/verifier.c
> @@ -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;
>
> + 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.
> /* 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
>
^ permalink raw reply [flat|nested] 17+ messages in thread
* Re: [PATCH bpf-next 1/4] bpf: replace env->cur_hist_ent with a getter function
2024-02-28 19:46 ` Andrii Nakryiko
@ 2024-02-28 21:23 ` Eduard Zingerman
0 siblings, 0 replies; 17+ messages in thread
From: Eduard Zingerman @ 2024-02-28 21:23 UTC (permalink / raw)
To: Andrii Nakryiko
Cc: bpf, ast, andrii, daniel, martin.lau, kernel-team, yonghong.song,
sunhao.th
On Wed, 2024-02-28 at 11:46 -0800, Andrii Nakryiko wrote:
[...]
> > diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c
> > index 011d54a1dc53..759ef089b33c 100644
> > --- a/kernel/bpf/verifier.c
> > +++ b/kernel/bpf/verifier.c
> > @@ -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;
> >
> > + 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.
You are correct.
> 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.
No need, the patch-set does not rely on capability to push entry for
several states simultaneously. I'll just drop this patch from v2.
[...]
^ permalink raw reply [flat|nested] 17+ messages in thread
* [PATCH bpf-next 2/4] bpf: track find_equal_scalars history on per-instruction level
2024-02-22 0:50 [PATCH bpf-next 0/4] bpf: track find_equal_scalars history on per-instruction level Eduard Zingerman
2024-02-22 0:50 ` [PATCH bpf-next 1/4] bpf: replace env->cur_hist_ent with a getter function Eduard Zingerman
@ 2024-02-22 0:50 ` Eduard Zingerman
2024-02-28 19:58 ` Andrii Nakryiko
2024-02-28 23:01 ` Andrii Nakryiko
2024-02-22 0:50 ` [PATCH bpf-next 3/4] bpf: remove mark_precise_scalar_ids() Eduard Zingerman
2024-02-22 0:50 ` [PATCH bpf-next 4/4] selftests/bpf: tests for per-insn find_equal_scalars() precision tracking Eduard Zingerman
3 siblings, 2 replies; 17+ messages in thread
From: Eduard Zingerman @ 2024-02-22 0:50 UTC (permalink / raw)
To: bpf, ast
Cc: andrii, daniel, martin.lau, kernel-team, yonghong.song,
sunhao.th, 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:
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 <sunhao.th@gmail.com>
Closes: https://lore.kernel.org/bpf/CAEf4BzZ0xidVCqB47XnkXcNhkPWF6_nTV7yt+_Lf0kcFEut2Mg@mail.gmail.com/
Suggested-by: Andrii Nakryiko <andrii@kernel.org>
Signed-off-by: Eduard Zingerman <eddyz87@gmail.com>
---
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(-)
diff --git a/include/linux/bpf_verifier.h b/include/linux/bpf_verifier.h
index cbfb235984c8..26e32555711c 100644
--- a/include/linux/bpf_verifier.h
+++ b/include/linux/bpf_verifier.h
@@ -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;
};
/* Maximum number of register states that can exist at once */
diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c
index 759ef089b33c..b95b6842703c 100644
--- a/kernel/bpf/verifier.c
+++ b/kernel/bpf/verifier.c
@@ -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);
+ if (num == 0)
+ return false;
+ *equal_scalars >>= ES_SIZE_BITS;
+ equal_scalars_unpack(*equal_scalars, frameno, spi_or_reg, is_reg);
+ *equal_scalars >>= ES_ENTRY_BITS;
+ *equal_scalars <<= ES_SIZE_BITS;
+ *equal_scalars |= num - 1;
+ return true;
+}
+
static struct bpf_jmp_history_entry *get_jmp_hist_entry(struct bpf_verifier_state *st,
u32 hist_end, int insn_idx)
{
@@ -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;
@@ -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;
+ }
+ 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;
@@ -3502,6 +3579,11 @@ static inline bool bt_is_reg_set(struct backtrack_state *bt, u32 reg)
return bt->reg_masks[bt->frame] & (1 << reg);
}
+static inline bool bt_is_frame_reg_set(struct backtrack_state *bt, u32 frame, u32 reg)
+{
+ return bt->reg_masks[frame] & (1 << reg);
+}
+
static inline bool bt_is_frame_slot_set(struct backtrack_state *bt, u32 frame, u32 slot)
{
return bt->stack_masks[frame] & (1ull << slot);
@@ -3546,6 +3628,39 @@ static void fmt_stack_mask(char *buf, ssize_t buf_sz, u64 stack_mask)
}
}
+/* If any register R in hist->equal_scalars is marked as precise in bt,
+ * do bt_set_frame_{reg,slot}(bt, R) for all registers in hist->equal_scalars.
+ */
+static void bt_set_equal_scalars(struct backtrack_state *bt, struct bpf_jmp_history_entry *hist)
+{
+ bool is_reg, some_precise = false;
+ u64 equal_scalars;
+ u32 fr, spi;
+
+ if (!hist || hist->equal_scalars == 0)
+ return;
+
+ equal_scalars = hist->equal_scalars;
+ 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))) {
+ some_precise = true;
+ break;
+ }
+ }
+
+ if (!some_precise)
+ return;
+
+ equal_scalars = hist->equal_scalars;
+ while (equal_scalars_pop(&equal_scalars, &fr, &spi, &is_reg)) {
+ if (is_reg)
+ bt_set_frame_reg(bt, fr, spi);
+ else
+ bt_set_frame_slot(bt, fr, spi);
+ }
+}
+
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
@@ -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);
+ bt_set_equal_scalars(bt, hist);
+ } else if (BPF_SRC(insn->code) == BPF_K) {
+ bt_set_equal_scalars(bt, hist);
/* 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;
}
@@ -4884,7 +5003,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;
}
@@ -14835,16 +14954,58 @@ 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(u64 *equal_scalars,
+ struct bpf_reg_state *reg,
+ u32 id, u32 frameno, u32 spi_or_reg, bool is_reg)
{
- struct bpf_func_state *state;
+ if (reg->type != SCALAR_VALUE || reg->id != id)
+ return;
+
+ if (!equal_scalars_push(equal_scalars, frameno, spi_or_reg, is_reg))
+ reg->id = 0;
+}
+
+/* For all R being scalar registers or spilled scalar registers
+ * in verifier state, save R in equal_scalars if R->id == id.
+ * If there are too many Rs sharing same id, reset id for leftover Rs.
+ */
+static void find_equal_scalars(struct bpf_verifier_state *vstate, u32 id, u64 *equal_scalars)
+{
+ struct bpf_func_state *func;
struct bpf_reg_state *reg;
+ int i, j;
- bpf_for_each_reg_in_vstate(vstate, state, reg, ({
- if (reg->type == SCALAR_VALUE && reg->id == known_reg->id)
+ for (i = vstate->curframe; i >= 0; i--) {
+ func = vstate->frame[i];
+ for (j = 0; j < BPF_REG_FP; j++) {
+ reg = &func->regs[j];
+ __find_equal_scalars(equal_scalars, reg, id, i, j, true);
+ }
+ for (j = 0; j < func->allocated_stack / BPF_REG_SIZE; j++) {
+ if (!is_spilled_reg(&func->stack[j]))
+ continue;
+ reg = &func->stack[j].spilled_ptr;
+ __find_equal_scalars(equal_scalars, reg, id, i, j, false);
+ }
+ }
+}
+
+/* For all R in equal_scalars, copy known_reg range into R
+ * if R->id == known_reg->id.
+ */
+static void copy_known_reg(struct bpf_verifier_state *vstate,
+ struct bpf_reg_state *known_reg, u64 equal_scalars)
+{
+ struct bpf_reg_state *reg;
+ u32 fr, spi;
+ bool is_reg;
+
+ while (equal_scalars_pop(&equal_scalars, &fr, &spi, &is_reg)) {
+ reg = is_reg ? &vstate->frame[fr]->regs[spi]
+ : &vstate->frame[fr]->stack[spi].spilled_ptr;
+ if (reg->id == known_reg->id)
copy_register_state(reg, known_reg);
- }));
+ }
}
static int check_cond_jmp_op(struct bpf_verifier_env *env,
@@ -14857,6 +15018,7 @@ static int check_cond_jmp_op(struct bpf_verifier_env *env,
struct bpf_reg_state *eq_branch_regs;
struct bpf_reg_state fake_reg = {};
u8 opcode = BPF_OP(insn->code);
+ u64 equal_scalars = 0;
bool is_jmp32;
int pred = -1;
int err;
@@ -14944,6 +15106,21 @@ static int check_cond_jmp_op(struct bpf_verifier_env *env,
return 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, &equal_scalars);
+ if (dst_reg->type == SCALAR_VALUE && dst_reg->id)
+ find_equal_scalars(this_branch, dst_reg->id, &equal_scalars);
+ if (equal_scalars_size(equal_scalars) > 1) {
+ err = push_jmp_history(env, this_branch, 0, equal_scalars);
+ if (err)
+ return err;
+ }
+
other_branch = push_stack(env, *insn_idx + insn->off + 1, *insn_idx,
false);
if (!other_branch)
@@ -14968,13 +15145,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 &&
!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, equal_scalars);
+ copy_known_reg(other_branch, &other_branch_regs[insn->src_reg], equal_scalars);
}
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, equal_scalars);
+ copy_known_reg(other_branch, &other_branch_regs[insn->dst_reg], equal_scalars);
}
/* if one pointer register is compared to another pointer
@@ -17213,7 +17390,7 @@ static int is_state_visited(struct bpf_verifier_env *env, int insn_idx)
* the current state.
*/
if (is_jmp_point(env, env->insn_idx))
- err = err ? : push_jmp_history(env, cur, 0);
+ err = err ? : push_jmp_history(env, cur, 0, 0);
err = err ? : propagate_precision(env, &sl->state);
if (err)
return err;
@@ -17477,7 +17654,7 @@ static int do_check(struct bpf_verifier_env *env)
}
if (is_jmp_point(env, env->insn_idx)) {
- err = push_jmp_history(env, state, 0);
+ err = push_jmp_history(env, state, 0, 0);
if (err)
return err;
}
diff --git a/tools/testing/selftests/bpf/progs/verifier_subprog_precision.c b/tools/testing/selftests/bpf/progs/verifier_subprog_precision.c
index 6f5d19665cf6..2c7261834149 100644
--- a/tools/testing/selftests/bpf/progs/verifier_subprog_precision.c
+++ b/tools/testing/selftests/bpf/progs/verifier_subprog_precision.c
@@ -191,7 +191,7 @@ __msg("mark_precise: frame0: last_idx 14 first_idx 9")
__msg("mark_precise: frame0: regs=r6 stack= before 13: (bf) r1 = r7")
__msg("mark_precise: frame0: regs=r6 stack= before 12: (27) r6 *= 4")
__msg("mark_precise: frame0: regs=r6 stack= before 11: (25) if r6 > 0x3 goto pc+4")
-__msg("mark_precise: frame0: regs=r6 stack= before 10: (bf) r6 = r0")
+__msg("mark_precise: frame0: regs=r0,r6 stack= before 10: (bf) r6 = r0")
__msg("mark_precise: frame0: regs=r0 stack= before 9: (85) call bpf_loop")
/* State entering callback body popped from states stack */
__msg("from 9 to 17: frame1:")
diff --git a/tools/testing/selftests/bpf/verifier/precise.c b/tools/testing/selftests/bpf/verifier/precise.c
index 0a9293a57211..64d722199e8f 100644
--- a/tools/testing/selftests/bpf/verifier/precise.c
+++ b/tools/testing/selftests/bpf/verifier/precise.c
@@ -44,7 +44,7 @@
mark_precise: frame0: regs=r2 stack= before 23\
mark_precise: frame0: regs=r2 stack= before 22\
mark_precise: frame0: regs=r2 stack= before 20\
- mark_precise: frame0: parent state regs=r2 stack=:\
+ mark_precise: frame0: parent state regs=r2,r9 stack=:\
mark_precise: frame0: last_idx 19 first_idx 10\
mark_precise: frame0: regs=r2,r9 stack= before 19\
mark_precise: frame0: regs=r9 stack= before 18\
--
2.43.0
^ permalink raw reply related [flat|nested] 17+ messages in thread
* Re: [PATCH bpf-next 2/4] bpf: track find_equal_scalars history on per-instruction level
2024-02-22 0:50 ` [PATCH bpf-next 2/4] bpf: track find_equal_scalars history on per-instruction level Eduard Zingerman
@ 2024-02-28 19:58 ` Andrii Nakryiko
2024-02-28 21:16 ` Eduard Zingerman
2024-02-28 23:01 ` Andrii Nakryiko
1 sibling, 1 reply; 17+ messages in thread
From: Andrii Nakryiko @ 2024-02-28 19:58 UTC (permalink / raw)
To: Eduard Zingerman
Cc: bpf, ast, andrii, daniel, martin.lau, kernel-team, yonghong.song,
sunhao.th
On Wed, Feb 21, 2024 at 4:50 PM Eduard Zingerman <eddyz87@gmail.com> wrote:
>
> 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 <sunhao.th@gmail.com>
> Closes: https://lore.kernel.org/bpf/CAEf4BzZ0xidVCqB47XnkXcNhkPWF6_nTV7yt+_Lf0kcFEut2Mg@mail.gmail.com/
> Suggested-by: Andrii Nakryiko <andrii@kernel.org>
> Signed-off-by: Eduard Zingerman <eddyz87@gmail.com>
> ---
> 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(-)
>
> diff --git a/include/linux/bpf_verifier.h b/include/linux/bpf_verifier.h
> index cbfb235984c8..26e32555711c 100644
> --- a/include/linux/bpf_verifier.h
> +++ b/include/linux/bpf_verifier.h
> @@ -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"?
> };
>
> /* Maximum number of register states that can exist at once */
> diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c
> index 759ef089b33c..b95b6842703c 100644
> --- a/kernel/bpf/verifier.c
> +++ b/kernel/bpf/verifier.c
> @@ -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);
> + if (num == 0)
> + return false;
> + *equal_scalars >>= ES_SIZE_BITS;
> + equal_scalars_unpack(*equal_scalars, frameno, spi_or_reg, is_reg);
> + *equal_scalars >>= ES_ENTRY_BITS;
> + *equal_scalars <<= ES_SIZE_BITS;
> + *equal_scalars |= num - 1;
> + return true;
> +}
> +
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?
> static struct bpf_jmp_history_entry *get_jmp_hist_entry(struct bpf_verifier_state *st,
> u32 hist_end, int insn_idx)
> {
[...]
^ permalink raw reply [flat|nested] 17+ messages in thread
* Re: [PATCH bpf-next 2/4] bpf: track find_equal_scalars history on per-instruction level
2024-02-28 19:58 ` Andrii Nakryiko
@ 2024-02-28 21:16 ` Eduard Zingerman
2024-02-28 21:36 ` Andrii Nakryiko
2024-02-28 21:40 ` Andrii Nakryiko
0 siblings, 2 replies; 17+ messages in thread
From: Eduard Zingerman @ 2024-02-28 21:16 UTC (permalink / raw)
To: Andrii Nakryiko
Cc: bpf, ast, andrii, daniel, martin.lau, kernel-team, yonghong.song,
sunhao.th
On Wed, 2024-02-28 at 11:58 -0800, Andrii Nakryiko wrote:
[...]
> > diff --git a/include/linux/bpf_verifier.h b/include/linux/bpf_verifier.h
> > index cbfb235984c8..26e32555711c 100644
> > --- a/include/linux/bpf_verifier.h
> > +++ b/include/linux/bpf_verifier.h
> > @@ -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.
[...]
> I'm wondering if this pop/push set of primitives is the best approach?
I kinda like it :)
> 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'.
> 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().
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.
> 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 ---
^ permalink raw reply [flat|nested] 17+ messages in thread
* Re: [PATCH bpf-next 2/4] bpf: track find_equal_scalars history on per-instruction level
2024-02-28 21:16 ` Eduard Zingerman
@ 2024-02-28 21:36 ` Andrii Nakryiko
2024-02-28 22:39 ` Eduard Zingerman
2024-02-28 21:40 ` Andrii Nakryiko
1 sibling, 1 reply; 17+ messages in thread
From: Andrii Nakryiko @ 2024-02-28 21:36 UTC (permalink / raw)
To: Eduard Zingerman
Cc: bpf, ast, andrii, daniel, martin.lau, kernel-team, yonghong.song,
sunhao.th
On Wed, Feb 28, 2024 at 1:16 PM Eduard Zingerman <eddyz87@gmail.com> wrote:
>
> On Wed, 2024-02-28 at 11:58 -0800, Andrii Nakryiko wrote:
> [...]
>
> > > diff --git a/include/linux/bpf_verifier.h b/include/linux/bpf_verifier.h
> > > index cbfb235984c8..26e32555711c 100644
> > > --- a/include/linux/bpf_verifier.h
> > > +++ b/include/linux/bpf_verifier.h
> > > @@ -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.
>
> [...]
>
> > I'm wondering if this pop/push set of primitives is the best approach?
>
> I kinda like it :)
>
> > 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'.
>
> > 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().
>
> 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.
Can I disagree? I find the second to be much better. There is no
in-place modification of a mask, no out parameters, we have a clean
record r with a few fields. We also know the count upfront, though we
maintain a simple rule (mask == 0 => cnt == 0), so not really a big
deal either way.
>
> > 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.
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.
>
> --- 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;
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
> tmp |= (r->is_reg ? 1 : 0) << ES_IS_REG_OFF;
>
> val <<= ES_ENTRY_BITS;
> val |= tmp;
val <<= ES_ENTRY_BITS;
val |= r->frameno | (r->spi << ES_SPI_OFF) | ((r->is_reg ? 1 : 0) <<
ES_IS_REG_OFF);
or you can do it as three assignment, but there is no need for 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;
> }
> }
>
I do think that the above is much easier to read and follow.
> ---------------------------------------------------------------- >8 ---
^ permalink raw reply [flat|nested] 17+ messages in thread
* Re: [PATCH bpf-next 2/4] bpf: track find_equal_scalars history on per-instruction level
2024-02-28 21:36 ` Andrii Nakryiko
@ 2024-02-28 22:39 ` Eduard Zingerman
0 siblings, 0 replies; 17+ messages in thread
From: Eduard Zingerman @ 2024-02-28 22:39 UTC (permalink / raw)
To: Andrii Nakryiko
Cc: bpf, ast, andrii, daniel, martin.lau, kernel-team, yonghong.song,
sunhao.th
On Wed, 2024-02-28 at 13:36 -0800, Andrii Nakryiko wrote:
[...]
> 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.
Ok, code is meant to be read, so I'll switch to below in v2.
[...]
> > 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;
>
> 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
Ok, I'll add bitmasks to field definitions and remove masks here.
[...]
^ permalink raw reply [flat|nested] 17+ messages in thread
* Re: [PATCH bpf-next 2/4] bpf: track find_equal_scalars history on per-instruction level
2024-02-28 21:16 ` Eduard Zingerman
2024-02-28 21:36 ` Andrii Nakryiko
@ 2024-02-28 21:40 ` Andrii Nakryiko
1 sibling, 0 replies; 17+ messages in thread
From: Andrii Nakryiko @ 2024-02-28 21:40 UTC (permalink / raw)
To: Eduard Zingerman
Cc: bpf, ast, andrii, daniel, martin.lau, kernel-team, yonghong.song,
sunhao.th
On Wed, Feb 28, 2024 at 1:16 PM Eduard Zingerman <eddyz87@gmail.com> wrote:
>
> On Wed, 2024-02-28 at 11:58 -0800, Andrii Nakryiko wrote:
> [...]
>
> > > diff --git a/include/linux/bpf_verifier.h b/include/linux/bpf_verifier.h
> > > index cbfb235984c8..26e32555711c 100644
> > > --- a/include/linux/bpf_verifier.h
> > > +++ b/include/linux/bpf_verifier.h
> > > @@ -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.
I'd start with calling this specific field either "linked_regs" or
"linked_set". It's a superset of "equal scalars", so we don't strictly
need to rename all the existing mentions of "equal_scalars" in
existing code.
>
> [...]
>
[...]
^ permalink raw reply [flat|nested] 17+ messages in thread
* Re: [PATCH bpf-next 2/4] bpf: track find_equal_scalars history on per-instruction level
2024-02-22 0:50 ` [PATCH bpf-next 2/4] bpf: track find_equal_scalars history on per-instruction level Eduard Zingerman
2024-02-28 19:58 ` Andrii Nakryiko
@ 2024-02-28 23:01 ` Andrii Nakryiko
2024-02-28 23:29 ` Eduard Zingerman
1 sibling, 1 reply; 17+ messages in thread
From: Andrii Nakryiko @ 2024-02-28 23:01 UTC (permalink / raw)
To: Eduard Zingerman
Cc: bpf, ast, andrii, daniel, martin.lau, kernel-team, yonghong.song,
sunhao.th
On Wed, Feb 21, 2024 at 4:50 PM Eduard Zingerman <eddyz87@gmail.com> wrote:
>
> 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 <sunhao.th@gmail.com>
> Closes: https://lore.kernel.org/bpf/CAEf4BzZ0xidVCqB47XnkXcNhkPWF6_nTV7yt+_Lf0kcFEut2Mg@mail.gmail.com/
> Suggested-by: Andrii Nakryiko <andrii@kernel.org>
> Signed-off-by: Eduard Zingerman <eddyz87@gmail.com>
> ---
> 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(-)
>
> diff --git a/include/linux/bpf_verifier.h b/include/linux/bpf_verifier.h
> index cbfb235984c8..26e32555711c 100644
> --- a/include/linux/bpf_verifier.h
> +++ b/include/linux/bpf_verifier.h
> @@ -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;
> };
>
[...]
> @@ -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;
> @@ -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?
> + 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
> @@ -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);
> + 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...
> /* 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;
> }
>
[...]
^ permalink raw reply [flat|nested] 17+ messages in thread
* Re: [PATCH bpf-next 2/4] bpf: track find_equal_scalars history on per-instruction level
2024-02-28 23:01 ` Andrii Nakryiko
@ 2024-02-28 23:29 ` Eduard Zingerman
2024-03-01 17:34 ` Andrii Nakryiko
0 siblings, 1 reply; 17+ messages in thread
From: Eduard Zingerman @ 2024-02-28 23:29 UTC (permalink / raw)
To: Andrii Nakryiko
Cc: bpf, ast, andrii, daniel, martin.lau, kernel-team, yonghong.song,
sunhao.th
On Wed, 2024-02-28 at 15:01 -0800, Andrii Nakryiko wrote:
[...]
> > @@ -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
[...]
> > /* 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);
> > + 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.
>
> > /* else dreg <cond> K
> > * Only dreg still needs precision before
> > * this insn, so for the K-based conditional
[...]
^ permalink raw reply [flat|nested] 17+ messages in thread
* Re: [PATCH bpf-next 2/4] bpf: track find_equal_scalars history on per-instruction level
2024-02-28 23:29 ` Eduard Zingerman
@ 2024-03-01 17:34 ` Andrii Nakryiko
2024-03-01 17:44 ` Eduard Zingerman
0 siblings, 1 reply; 17+ messages in thread
From: Andrii Nakryiko @ 2024-03-01 17:34 UTC (permalink / raw)
To: Eduard Zingerman
Cc: bpf, ast, andrii, daniel, martin.lau, kernel-team, yonghong.song,
sunhao.th
On Wed, Feb 28, 2024 at 3:29 PM Eduard Zingerman <eddyz87@gmail.com> wrote:
>
> On Wed, 2024-02-28 at 15:01 -0800, Andrii Nakryiko wrote:
> [...]
>
> > > @@ -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
>
> [...]
>
> > > /* 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);
> > > + 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.
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?
>
> >
> > > /* else dreg <cond> K
> > > * Only dreg still needs precision before
> > > * this insn, so for the K-based conditional
>
> [...]
^ permalink raw reply [flat|nested] 17+ messages in thread
* Re: [PATCH bpf-next 2/4] bpf: track find_equal_scalars history on per-instruction level
2024-03-01 17:34 ` Andrii Nakryiko
@ 2024-03-01 17:44 ` Eduard Zingerman
2024-03-04 23:37 ` Andrii Nakryiko
0 siblings, 1 reply; 17+ messages in thread
From: Eduard Zingerman @ 2024-03-01 17:44 UTC (permalink / raw)
To: Andrii Nakryiko
Cc: bpf, ast, andrii, daniel, martin.lau, kernel-team, yonghong.song,
sunhao.th
On Fri, 2024-03-01 at 09:34 -0800, Andrii Nakryiko wrote:
[...]
> 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 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?
> 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.
^ permalink raw reply [flat|nested] 17+ messages in thread
* Re: [PATCH bpf-next 2/4] bpf: track find_equal_scalars history on per-instruction level
2024-03-01 17:44 ` Eduard Zingerman
@ 2024-03-04 23:37 ` Andrii Nakryiko
0 siblings, 0 replies; 17+ messages in thread
From: Andrii Nakryiko @ 2024-03-04 23:37 UTC (permalink / raw)
To: Eduard Zingerman
Cc: bpf, ast, andrii, daniel, martin.lau, kernel-team, yonghong.song,
sunhao.th
On Fri, Mar 1, 2024 at 9:44 AM Eduard Zingerman <eddyz87@gmail.com> wrote:
>
> On Fri, 2024-03-01 at 09:34 -0800, Andrii Nakryiko wrote:
> [...]
>
> > 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 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?
Not exactly. It was more a proposal to change the current use of
bt_set_reg() with bt_set_linked_regs(), which would take into account
linked registers. And do it throughout the entire backtrack_insn(),
regardless of specific instruction being backtracked. I think that
would eliminate the need to have bt_set_equal_scalars() before
instruction as well.
>
> > 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.
^ permalink raw reply [flat|nested] 17+ messages in thread
* [PATCH bpf-next 3/4] bpf: remove mark_precise_scalar_ids()
2024-02-22 0:50 [PATCH bpf-next 0/4] bpf: track find_equal_scalars history on per-instruction level Eduard Zingerman
2024-02-22 0:50 ` [PATCH bpf-next 1/4] bpf: replace env->cur_hist_ent with a getter function Eduard Zingerman
2024-02-22 0:50 ` [PATCH bpf-next 2/4] bpf: track find_equal_scalars history on per-instruction level Eduard Zingerman
@ 2024-02-22 0:50 ` Eduard Zingerman
2024-02-22 0:50 ` [PATCH bpf-next 4/4] selftests/bpf: tests for per-insn find_equal_scalars() precision tracking Eduard Zingerman
3 siblings, 0 replies; 17+ messages in thread
From: Eduard Zingerman @ 2024-02-22 0:50 UTC (permalink / raw)
To: bpf, ast
Cc: andrii, daniel, martin.lau, kernel-team, yonghong.song,
sunhao.th, Eduard Zingerman
Function mark_precise_scalar_ids() is superseded by
bt_set_equal_scalars() and equal scalars tracking in jump history.
mark_precise_scalar_ids() propagates precision over registers sharing
same ID on parent/child state boundaries, while jump history records
allow bt_set_equal_scalars() to propagate same information with
instruction level granularity, which is strictly more precise.
This commit removes mark_precise_scalar_ids() and updates test cases
in progs/verifier_scalar_ids to reflect new verifier behavior.
The tests are updated in the following manner:
- mark_precise_scalar_ids() propagated precision regardless of
presence of conditional jumps, while new jump history bases logic
only kicks in when conditional jumps are present.
Hence test cases are augmented with conditional jumps to still
trigger precision propagation.
- As equal scalars tracking no longer relies on parent/child state
boundaries some test cases are no longer interesting,
such test cases are removed, namely:
- precision_same_state and precision_cross_state are superseded by
equal_scalars_bpf_k;
- precision_same_state_broken_link and equal_scalars_broken_link
are superseded by equal_scalars_broken_link.
Signed-off-by: Eduard Zingerman <eddyz87@gmail.com>
---
kernel/bpf/verifier.c | 115 ------------
.../selftests/bpf/progs/verifier_scalar_ids.c | 171 ++++++------------
.../testing/selftests/bpf/verifier/precise.c | 8 +-
3 files changed, 59 insertions(+), 235 deletions(-)
diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c
index b95b6842703c..921aee8b12f6 100644
--- a/kernel/bpf/verifier.c
+++ b/kernel/bpf/verifier.c
@@ -4076,96 +4076,6 @@ static void mark_all_scalars_imprecise(struct bpf_verifier_env *env, struct bpf_
}
}
-static bool idset_contains(struct bpf_idset *s, u32 id)
-{
- u32 i;
-
- for (i = 0; i < s->count; ++i)
- if (s->ids[i] == id)
- return true;
-
- return false;
-}
-
-static int idset_push(struct bpf_idset *s, u32 id)
-{
- if (WARN_ON_ONCE(s->count >= ARRAY_SIZE(s->ids)))
- return -EFAULT;
- s->ids[s->count++] = id;
- return 0;
-}
-
-static void idset_reset(struct bpf_idset *s)
-{
- s->count = 0;
-}
-
-/* Collect a set of IDs for all registers currently marked as precise in env->bt.
- * Mark all registers with these IDs as precise.
- */
-static int mark_precise_scalar_ids(struct bpf_verifier_env *env, struct bpf_verifier_state *st)
-{
- struct bpf_idset *precise_ids = &env->idset_scratch;
- struct backtrack_state *bt = &env->bt;
- struct bpf_func_state *func;
- struct bpf_reg_state *reg;
- DECLARE_BITMAP(mask, 64);
- int i, fr;
-
- idset_reset(precise_ids);
-
- for (fr = bt->frame; fr >= 0; fr--) {
- func = st->frame[fr];
-
- bitmap_from_u64(mask, bt_frame_reg_mask(bt, fr));
- for_each_set_bit(i, mask, 32) {
- reg = &func->regs[i];
- if (!reg->id || reg->type != SCALAR_VALUE)
- continue;
- if (idset_push(precise_ids, reg->id))
- return -EFAULT;
- }
-
- bitmap_from_u64(mask, bt_frame_stack_mask(bt, fr));
- for_each_set_bit(i, mask, 64) {
- if (i >= func->allocated_stack / BPF_REG_SIZE)
- break;
- if (!is_spilled_scalar_reg(&func->stack[i]))
- continue;
- reg = &func->stack[i].spilled_ptr;
- if (!reg->id)
- continue;
- if (idset_push(precise_ids, reg->id))
- return -EFAULT;
- }
- }
-
- for (fr = 0; fr <= st->curframe; ++fr) {
- func = st->frame[fr];
-
- for (i = BPF_REG_0; i < BPF_REG_10; ++i) {
- reg = &func->regs[i];
- if (!reg->id)
- continue;
- if (!idset_contains(precise_ids, reg->id))
- continue;
- bt_set_frame_reg(bt, fr, i);
- }
- for (i = 0; i < func->allocated_stack / BPF_REG_SIZE; ++i) {
- if (!is_spilled_scalar_reg(&func->stack[i]))
- continue;
- reg = &func->stack[i].spilled_ptr;
- if (!reg->id)
- continue;
- if (!idset_contains(precise_ids, reg->id))
- continue;
- bt_set_frame_slot(bt, fr, i);
- }
- }
-
- return 0;
-}
-
/*
* __mark_chain_precision() backtracks BPF program instruction sequence and
* chain of verifier states making sure that register *regno* (if regno >= 0)
@@ -4298,31 +4208,6 @@ static int __mark_chain_precision(struct bpf_verifier_env *env, int regno)
bt->frame, last_idx, first_idx, subseq_idx);
}
- /* If some register with scalar ID is marked as precise,
- * make sure that all registers sharing this ID are also precise.
- * This is needed to estimate effect of find_equal_scalars().
- * Do this at the last instruction of each state,
- * bpf_reg_state::id fields are valid for these instructions.
- *
- * Allows to track precision in situation like below:
- *
- * r2 = unknown value
- * ...
- * --- state #0 ---
- * ...
- * r1 = r2 // r1 and r2 now share the same ID
- * ...
- * --- state #1 {r1.id = A, r2.id = A} ---
- * ...
- * if (r2 > 10) goto exit; // find_equal_scalars() assigns range to r1
- * ...
- * --- state #2 {r1.id = A, r2.id = A} ---
- * r3 = r10
- * r3 += r1 // need to mark both r1 and r2
- */
- if (mark_precise_scalar_ids(env, st))
- return -EFAULT;
-
if (last_idx < 0) {
/* we are at the entry into subprog, which
* is expected for global funcs, but only if
diff --git a/tools/testing/selftests/bpf/progs/verifier_scalar_ids.c b/tools/testing/selftests/bpf/progs/verifier_scalar_ids.c
index 13b29a7faa71..639db72b1c55 100644
--- a/tools/testing/selftests/bpf/progs/verifier_scalar_ids.c
+++ b/tools/testing/selftests/bpf/progs/verifier_scalar_ids.c
@@ -5,54 +5,27 @@
#include "bpf_misc.h"
/* Check that precision marks propagate through scalar IDs.
- * Registers r{0,1,2} have the same scalar ID at the moment when r0 is
- * marked to be precise, this mark is immediately propagated to r{1,2}.
+ * Registers r{0,1,2} have the same scalar ID.
+ * Range information is propagated for scalars sharing same ID.
+ * Check that precision mark for r0 causes precision marks for r{1,2}
+ * when range information is propagated for 'if <reg> <op> <const>' insn.
*/
SEC("socket")
__success __log_level(2)
-__msg("frame0: regs=r0,r1,r2 stack= before 4: (bf) r3 = r10")
-__msg("frame0: regs=r0,r1,r2 stack= before 3: (bf) r2 = r0")
-__msg("frame0: regs=r0,r1 stack= before 2: (bf) r1 = r0")
-__msg("frame0: regs=r0 stack= before 1: (57) r0 &= 255")
-__msg("frame0: regs=r0 stack= before 0: (85) call bpf_ktime_get_ns")
-__flag(BPF_F_TEST_STATE_FREQ)
-__naked void precision_same_state(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;"
- /* force r0 to be precise, this immediately marks r1 and r2 as
- * precise as well because of shared IDs
- */
- "r3 = r10;"
- "r3 += r0;"
- "r0 = 0;"
- "exit;"
- :
- : __imm(bpf_ktime_get_ns)
- : __clobber_all);
-}
-
-/* Same as precision_same_state, but mark propagates through state /
- * parent state boundary.
- */
-SEC("socket")
-__success __log_level(2)
-__msg("frame0: last_idx 6 first_idx 5 subseq_idx -1")
-__msg("frame0: regs=r0,r1,r2 stack= before 5: (bf) r3 = r10")
+/* first 'if' branch */
+__msg("6: (0f) r3 += r0")
+__msg("frame0: regs=r0 stack= before 4: (25) if r1 > 0x7 goto pc+0")
__msg("frame0: parent state regs=r0,r1,r2 stack=:")
-__msg("frame0: regs=r0,r1,r2 stack= before 4: (05) goto pc+0")
__msg("frame0: regs=r0,r1,r2 stack= before 3: (bf) r2 = r0")
-__msg("frame0: regs=r0,r1 stack= before 2: (bf) r1 = r0")
-__msg("frame0: regs=r0 stack= before 1: (57) r0 &= 255")
-__msg("frame0: parent state regs=r0 stack=:")
-__msg("frame0: regs=r0 stack= before 0: (85) call bpf_ktime_get_ns")
+/* second 'if' branch */
+__msg("from 4 to 5: ")
+__msg("6: (0f) r3 += r0")
+__msg("frame0: regs=r0 stack= before 5: (bf) r3 = r10")
+__msg("frame0: regs=r0 stack= before 4: (25) if r1 > 0x7 goto pc+0")
+/* parent state already has r{0,1,2} as precise */
+__msg("frame0: parent state regs= stack=:")
__flag(BPF_F_TEST_STATE_FREQ)
-__naked void precision_cross_state(void)
+__naked void equal_scalars_bpf_k(void)
{
asm volatile (
/* r0 = random number up to 0xff */
@@ -61,9 +34,8 @@ __naked void precision_cross_state(void)
/* tie r0.id == r1.id == r2.id */
"r1 = r0;"
"r2 = r0;"
- /* force checkpoint */
- "goto +0;"
- /* force r0 to be precise, this immediately marks r1 and r2 as
+ "if r1 > 7 goto +0;"
+ /* force r0 to be precise, this eventually marks r1 and r2 as
* precise as well because of shared IDs
*/
"r3 = r10;"
@@ -75,59 +47,18 @@ __naked void precision_cross_state(void)
: __clobber_all);
}
-/* Same as precision_same_state, but break one of the
+/* Same as equal_scalars_bpf_k, but break one of the
* links, note that r1 is absent from regs=... in __msg below.
*/
SEC("socket")
__success __log_level(2)
-__msg("frame0: regs=r0,r2 stack= before 5: (bf) r3 = r10")
-__msg("frame0: regs=r0,r2 stack= before 4: (b7) r1 = 0")
-__msg("frame0: regs=r0,r2 stack= before 3: (bf) r2 = r0")
-__msg("frame0: regs=r0 stack= before 2: (bf) r1 = r0")
-__msg("frame0: regs=r0 stack= before 1: (57) r0 &= 255")
-__msg("frame0: regs=r0 stack= before 0: (85) call bpf_ktime_get_ns")
-__flag(BPF_F_TEST_STATE_FREQ)
-__naked void precision_same_state_broken_link(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;"
- /* break link for r1, this is the only line that differs
- * compared to the previous test
- */
- "r1 = 0;"
- /* force r0 to be precise, this immediately marks r1 and r2 as
- * precise as well because of shared IDs
- */
- "r3 = r10;"
- "r3 += r0;"
- "r0 = 0;"
- "exit;"
- :
- : __imm(bpf_ktime_get_ns)
- : __clobber_all);
-}
-
-/* Same as precision_same_state_broken_link, but with state /
- * parent state boundary.
- */
-SEC("socket")
-__success __log_level(2)
-__msg("frame0: regs=r0,r2 stack= before 6: (bf) r3 = r10")
-__msg("frame0: regs=r0,r2 stack= before 5: (b7) r1 = 0")
-__msg("frame0: parent state regs=r0,r2 stack=:")
-__msg("frame0: regs=r0,r1,r2 stack= before 4: (05) goto pc+0")
-__msg("frame0: regs=r0,r1,r2 stack= before 3: (bf) r2 = r0")
-__msg("frame0: regs=r0,r1 stack= before 2: (bf) r1 = r0")
-__msg("frame0: regs=r0 stack= before 1: (57) r0 &= 255")
+__msg("7: (0f) r3 += r0")
+__msg("frame0: regs=r0 stack= before 6: (bf) r3 = r10")
__msg("frame0: parent state regs=r0 stack=:")
-__msg("frame0: regs=r0 stack= before 0: (85) call bpf_ktime_get_ns")
+__msg("frame0: regs=r0 stack= before 5: (25) if r0 > 0x7 goto pc+0")
+__msg("frame0: parent state regs=r0,r2 stack=:")
__flag(BPF_F_TEST_STATE_FREQ)
-__naked void precision_cross_state_broken_link(void)
+__naked void equal_scalars_broken_link(void)
{
asm volatile (
/* r0 = random number up to 0xff */
@@ -136,18 +67,13 @@ __naked void precision_cross_state_broken_link(void)
/* tie r0.id == r1.id == r2.id */
"r1 = r0;"
"r2 = r0;"
- /* force checkpoint, although link between r1 and r{0,2} is
- * broken by the next statement current precision tracking
- * algorithm can't react to it and propagates mark for r1 to
- * the parent state.
- */
- "goto +0;"
/* break link for r1, this is the only line that differs
- * compared to precision_cross_state()
+ * compared to the previous test
*/
"r1 = 0;"
- /* force r0 to be precise, this immediately marks r1 and r2 as
- * precise as well because of shared IDs
+ "if r0 > 7 goto +0;"
+ /* force r0 to be precise,
+ * this eventually marks r2 as precise because of shared IDs
*/
"r3 = r10;"
"r3 += r0;"
@@ -164,10 +90,16 @@ __naked void precision_cross_state_broken_link(void)
*/
SEC("socket")
__success __log_level(2)
-__msg("11: (0f) r2 += r1")
+__msg("12: (0f) r2 += r1")
/* Current state */
-__msg("frame2: last_idx 11 first_idx 10 subseq_idx -1")
-__msg("frame2: regs=r1 stack= before 10: (bf) r2 = r10")
+__msg("frame2: last_idx 12 first_idx 11 subseq_idx -1 ")
+__msg("frame2: regs=r1 stack= before 11: (bf) r2 = r10")
+__msg("frame2: parent state regs=r1 stack=")
+__msg("frame1: parent state regs= stack=")
+__msg("frame0: parent state regs= stack=")
+/* Parent state */
+__msg("frame2: last_idx 10 first_idx 10 subseq_idx 11 ")
+__msg("frame2: regs=r1 stack= before 10: (25) if r1 > 0x7 goto pc+0")
__msg("frame2: parent state regs=r1 stack=")
/* frame1.r{6,7} are marked because mark_precise_scalar_ids()
* looks for all registers with frame2.r1.id in the current state
@@ -192,7 +124,7 @@ __msg("frame1: regs=r1 stack= before 4: (85) call pc+1")
__msg("frame0: parent state regs=r1,r6 stack=")
/* Parent state */
__msg("frame0: last_idx 3 first_idx 1 subseq_idx 4")
-__msg("frame0: regs=r0,r1,r6 stack= before 3: (bf) r6 = r0")
+__msg("frame0: regs=r1,r6 stack= before 3: (bf) r6 = r0")
__msg("frame0: regs=r0,r1 stack= before 2: (bf) r1 = r0")
__msg("frame0: regs=r0 stack= before 1: (57) r0 &= 255")
__flag(BPF_F_TEST_STATE_FREQ)
@@ -230,7 +162,8 @@ static __naked __noinline __used
void precision_many_frames__bar(void)
{
asm volatile (
- /* force r1 to be precise, this immediately marks:
+ "if r1 > 7 goto +0;"
+ /* force r1 to be precise, this eventually marks:
* - bar frame r1
* - foo frame r{1,6,7}
* - main frame r{1,6}
@@ -247,14 +180,16 @@ void precision_many_frames__bar(void)
*/
SEC("socket")
__success __log_level(2)
+__msg("11: (0f) r2 += r1")
/* foo frame */
-__msg("frame1: regs=r1 stack=-8,-16 before 9: (bf) r2 = r10")
+__msg("frame1: regs=r1 stack= before 10: (bf) r2 = r10")
+__msg("frame1: regs=r1 stack= before 9: (25) if r1 > 0x7 goto pc+0")
__msg("frame1: regs=r1 stack=-8,-16 before 8: (7b) *(u64 *)(r10 -16) = r1")
__msg("frame1: regs=r1 stack=-8 before 7: (7b) *(u64 *)(r10 -8) = r1")
__msg("frame1: regs=r1 stack= before 4: (85) call pc+2")
/* main frame */
-__msg("frame0: regs=r0,r1 stack=-8 before 3: (7b) *(u64 *)(r10 -8) = r1")
-__msg("frame0: regs=r0,r1 stack= before 2: (bf) r1 = r0")
+__msg("frame0: regs=r1 stack=-8 before 3: (7b) *(u64 *)(r10 -8) = r1")
+__msg("frame0: regs=r1 stack= before 2: (bf) r1 = r0")
__msg("frame0: regs=r0 stack= before 1: (57) r0 &= 255")
__flag(BPF_F_TEST_STATE_FREQ)
__naked void precision_stack(void)
@@ -283,7 +218,8 @@ void precision_stack__foo(void)
*/
"*(u64*)(r10 - 8) = r1;"
"*(u64*)(r10 - 16) = r1;"
- /* force r1 to be precise, this immediately marks:
+ "if r1 > 7 goto +0;"
+ /* force r1 to be precise, this eventually marks:
* - foo frame r1,fp{-8,-16}
* - main frame r1,fp{-8}
*/
@@ -299,15 +235,17 @@ void precision_stack__foo(void)
SEC("socket")
__success __log_level(2)
/* r{6,7} */
-__msg("11: (0f) r3 += r7")
-__msg("frame0: regs=r6,r7 stack= before 10: (bf) r3 = r10")
+__msg("12: (0f) r3 += r7")
+__msg("frame0: regs=r7 stack= before 11: (bf) r3 = r10")
+__msg("frame0: regs=r7 stack= before 9: (25) if r7 > 0x7 goto pc+0")
/* ... skip some insns ... */
__msg("frame0: regs=r6,r7 stack= before 3: (bf) r7 = r0")
__msg("frame0: regs=r0,r6 stack= before 2: (bf) r6 = r0")
/* r{8,9} */
-__msg("12: (0f) r3 += r9")
-__msg("frame0: regs=r8,r9 stack= before 11: (0f) r3 += r7")
+__msg("13: (0f) r3 += r9")
+__msg("frame0: regs=r9 stack= before 12: (0f) r3 += r7")
/* ... skip some insns ... */
+__msg("frame0: regs=r9 stack= before 10: (25) if r9 > 0x7 goto pc+0")
__msg("frame0: regs=r8,r9 stack= before 7: (bf) r9 = r0")
__msg("frame0: regs=r0,r8 stack= before 6: (bf) r8 = r0")
__flag(BPF_F_TEST_STATE_FREQ)
@@ -328,8 +266,9 @@ __naked void precision_two_ids(void)
"r9 = r0;"
/* clear r0 id */
"r0 = 0;"
- /* force checkpoint */
- "goto +0;"
+ /* propagate equal scalars precision */
+ "if r7 > 7 goto +0;"
+ "if r9 > 7 goto +0;"
"r3 = r10;"
/* force r7 to be precise, this also marks r6 */
"r3 += r7;"
diff --git a/tools/testing/selftests/bpf/verifier/precise.c b/tools/testing/selftests/bpf/verifier/precise.c
index 64d722199e8f..59a020c35647 100644
--- a/tools/testing/selftests/bpf/verifier/precise.c
+++ b/tools/testing/selftests/bpf/verifier/precise.c
@@ -106,7 +106,7 @@
mark_precise: frame0: regs=r2 stack= before 22\
mark_precise: frame0: parent state regs=r2 stack=:\
mark_precise: frame0: last_idx 20 first_idx 20\
- mark_precise: frame0: regs=r2,r9 stack= before 20\
+ mark_precise: frame0: regs=r2 stack= before 20\
mark_precise: frame0: parent state regs=r2,r9 stack=:\
mark_precise: frame0: last_idx 19 first_idx 17\
mark_precise: frame0: regs=r2,r9 stack= before 19\
@@ -183,10 +183,10 @@
.prog_type = BPF_PROG_TYPE_XDP,
.flags = BPF_F_TEST_STATE_FREQ,
.errstr = "mark_precise: frame0: last_idx 7 first_idx 7\
- mark_precise: frame0: parent state regs=r4 stack=-8:\
+ mark_precise: frame0: parent state regs=r4 stack=:\
mark_precise: frame0: last_idx 6 first_idx 4\
- mark_precise: frame0: regs=r4 stack=-8 before 6: (b7) r0 = -1\
- mark_precise: frame0: regs=r4 stack=-8 before 5: (79) r4 = *(u64 *)(r10 -8)\
+ mark_precise: frame0: regs=r4 stack= before 6: (b7) r0 = -1\
+ mark_precise: frame0: regs=r4 stack= before 5: (79) r4 = *(u64 *)(r10 -8)\
mark_precise: frame0: regs= stack=-8 before 4: (7b) *(u64 *)(r3 -8) = r0\
mark_precise: frame0: parent state regs=r0 stack=:\
mark_precise: frame0: last_idx 3 first_idx 3\
--
2.43.0
^ permalink raw reply related [flat|nested] 17+ messages in thread
* [PATCH bpf-next 4/4] selftests/bpf: tests for per-insn find_equal_scalars() precision tracking
2024-02-22 0:50 [PATCH bpf-next 0/4] bpf: track find_equal_scalars history on per-instruction level Eduard Zingerman
` (2 preceding siblings ...)
2024-02-22 0:50 ` [PATCH bpf-next 3/4] bpf: remove mark_precise_scalar_ids() Eduard Zingerman
@ 2024-02-22 0:50 ` Eduard Zingerman
3 siblings, 0 replies; 17+ messages in thread
From: Eduard Zingerman @ 2024-02-22 0:50 UTC (permalink / raw)
To: bpf, ast
Cc: andrii, daniel, martin.lau, kernel-team, yonghong.song,
sunhao.th, Eduard Zingerman
Add a few test cases to verify precision tracking for scalars gaining
range because of find_equal_scalars():
- check what happens when more than 6 registers might gain range in
find_equal_scalars();
- check if precision is propagated correctly when operand of
conditional jump gained range in find_equal_scalars() and one of
linked registers is marked precise;
- check if precision is propagated correctly when operand of
conditional jump gained range in find_equal_scalars() and a
other-linked operand of the conditional jump is marked precise;
- add a minimized reproducer for precision tracking bug reported in [0];
- Check that mark_chain_precision() for one of the conditional jump
operands does not trigger equal scalars precision propagation.
[0] https://lore.kernel.org/bpf/CAEf4BzZ0xidVCqB47XnkXcNhkPWF6_nTV7yt+_Lf0kcFEut2Mg@mail.gmail.com/
Signed-off-by: Eduard Zingerman <eddyz87@gmail.com>
---
.../selftests/bpf/progs/verifier_scalar_ids.c | 165 ++++++++++++++++++
1 file changed, 165 insertions(+)
diff --git a/tools/testing/selftests/bpf/progs/verifier_scalar_ids.c b/tools/testing/selftests/bpf/progs/verifier_scalar_ids.c
index 639db72b1c55..993c5affb3d7 100644
--- a/tools/testing/selftests/bpf/progs/verifier_scalar_ids.c
+++ b/tools/testing/selftests/bpf/progs/verifier_scalar_ids.c
@@ -47,6 +47,72 @@ __naked void equal_scalars_bpf_k(void)
: __clobber_all);
}
+/* Registers r{0,1,2} share same ID when 'if r1 > ...' insn is processed,
+ * check that verifier marks r{1,2} as precise while backtracking
+ * 'if r1 > ...' with r0 already marked.
+ */
+SEC("socket")
+__success __log_level(2)
+__flag(BPF_F_TEST_STATE_FREQ)
+__msg("frame0: regs=r0 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_src(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 += r0;"
+ "r0 = 0;"
+ "exit;"
+ :
+ : __imm(bpf_ktime_get_ns)
+ : __clobber_all);
+}
+
+/* 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);
+}
+
/* Same as equal_scalars_bpf_k, but break one of the
* links, note that r1 is absent from regs=... in __msg below.
*/
@@ -280,6 +346,105 @@ __naked void precision_two_ids(void)
: __clobber_all);
}
+SEC("socket")
+__success __log_level(2)
+__flag(BPF_F_TEST_STATE_FREQ)
+/* check thar r0 and r6 have different IDs after 'if',
+ * find_equal_scalars() can't tie more than 6 registers for a single insn.
+ */
+__msg("8: (25) if r0 > 0x7 goto pc+0 ; R0=scalar(id=1")
+__msg("9: (bf) r6 = r6 ; R6_w=scalar(id=2")
+/* check that r{0-5} are marked precise after 'if' */
+__msg("frame0: regs=r0 stack= before 8: (25) if r0 > 0x7 goto pc+0")
+__msg("frame0: parent state regs=r0,r1,r2,r3,r4,r5 stack=:")
+__naked void equal_scalars_too_many_regs(void)
+{
+ asm volatile (
+ /* r0 = random number up to 0xff */
+ "call %[bpf_ktime_get_ns];"
+ "r0 &= 0xff;"
+ /* tie r{0-6} IDs */
+ "r1 = r0;"
+ "r2 = r0;"
+ "r3 = r0;"
+ "r4 = r0;"
+ "r5 = r0;"
+ "r6 = r0;"
+ /* propagate range for r{0-6} */
+ "if r0 > 7 goto +0;"
+ /* make r6 appear in the log */
+ "r6 = r6;"
+ /* force r0 to be precise,
+ * this would cause r{0-4} to be precise because of shared IDs
+ */
+ "r7 = r10;"
+ "r7 += r0;"
+ "r0 = 0;"
+ "exit;"
+ :
+ : __imm(bpf_ktime_get_ns)
+ : __clobber_all);
+}
+
+SEC("socket")
+__failure __log_level(2)
+__flag(BPF_F_TEST_STATE_FREQ)
+__msg("regs=r7 stack= before 5: (3d) if r8 >= r0")
+__msg("parent state regs=r0,r7,r8")
+__msg("regs=r0,r7,r8 stack= before 4: (25) if r0 > 0x1")
+__msg("div by zero")
+__naked void equal_scalars_broken_link_2(void)
+{
+ asm volatile (
+ "call %[bpf_get_prandom_u32];"
+ "r7 = r0;"
+ "r8 = r0;"
+ "call %[bpf_get_prandom_u32];"
+ "if r0 > 1 goto +0;"
+ /* r7.id == r8.id,
+ * thus r7 precision implies r8 precision,
+ * which implies r0 precision because of the conditional below.
+ */
+ "if r8 >= r0 goto 1f;"
+ /* break id relation between r7 and r8 */
+ "r8 += r8;"
+ /* make r7 precise */
+ "if r7 == 0 goto 1f;"
+ "r0 /= 0;"
+"1:"
+ "r0 = 42;"
+ "exit;"
+ :
+ : __imm(bpf_get_prandom_u32)
+ : __clobber_all);
+}
+
+/* Check that mark_chain_precision() for one of the conditional jump
+ * operands does not trigger equal scalars precision propagation.
+ */
+SEC("socket")
+__success __log_level(2)
+__msg("3: (25) if r1 > 0x100 goto pc+0")
+__msg("frame0: regs=r1 stack= before 2: (bf) r1 = r0")
+__naked void cjmp_no_equal_scalars_trigger(void)
+{
+ asm volatile (
+ /* r0 = random number up to 0xff */
+ "call %[bpf_ktime_get_ns];"
+ "r0 &= 0xff;"
+ /* tie r0.id == r1.id */
+ "r1 = r0;"
+ /* the jump below would be predicted, thus r1 would be marked precise,
+ * this should not imply precision mark for r0
+ */
+ "if r1 > 256 goto +0;"
+ "r0 = 0;"
+ "exit;"
+ :
+ : __imm(bpf_ktime_get_ns)
+ : __clobber_all);
+}
+
/* Verify that check_ids() is used by regsafe() for scalars.
*
* r9 = ... some pointer with range X ...
--
2.43.0
^ permalink raw reply related [flat|nested] 17+ messages in thread