Skip to contentSkip to conversation

bpf: use common instruction history across all states

PATCH Superseded Andrii Nakryiko 3 participants 6 messages Oct 30, 2024 – Nov 11, 2024

Subsystems (2)

v1 of 3 Superseded Latest is v3 →

lore
Share & tools
lore

Andrii Nakryiko

author maintainer
#0 lore raw

PATCH 1/1 bpf: use common instruction history across all states

Instead of allocating and copying instruction history each time we enqueue child verifier state, switch to a model where we use one common dynamically sized array of instruction history entries across all states.

The key observation for proving this is correct is that instruction history is only relevant while state is active, which means it either is a current state (and thus we are actively modifying instruction history and no other state can interfere with us) or we are checkpointed state with some children still active (either enqueued or being current).

In the latter case our portion of instruction history is finalized and won't change or grow, so as long as we keep it immutable until the state is finalized, we are good.

Now, when state is finalized and is put into state hash for potentially future pruning lookups, instruction history is not used anymore. This is because instruction history is only used by precision marking logic, and we never modify precision markings for finalized states.

So, instead of each state having its own small instruction history, we keep a global dynamically-sized instruction history, where each state in current DFS path from root to active state remembers its portion of instruction history. Current state can append to this history, but cannot modify any of its parent histories.

Async callback state enqueing, while logically detached from parent state, still is part of verification backtracking tree, so has to follow the same schema as normal state checkpoints.

Because the insn_hist array can be grown through realloc, states don't keep pointers, they instead maintain two indices, [start, end), into global instruction history array. End is exclusive index, so start == end means there is no relevant instruction history.

This eliminates a lot of allocations and minimizes overall memory usage.

For instance, running a worst-case test from [0] (but without the heuristics-based fix [1]), it took 12.5 minutes until we get -ENOMEM. With the changes in this patch the whole test succeeds in 10 minutes (very slow, so heuristics from [1] is important, of course).

To further validate correctness, veristat-based comparison was performed for Meta production BPF objects and BPF selftests objects. In both cases there were no differences *at all* in terms of verdict or instruction and state counts, providing a good confidence in the change.

Having this low-memory-overhead solution of keeping dynamic per-instruction history cheaply opens up some new possibilities, like keeping extra information for literally every single validated instruction. This will be used for simplifying precision backpropagation logic in follow up patches.

[0] https://lore.kernel.org/bpf/[email protected]/
[1] https://lore.kernel.org/bpf/[email protected]/

---
 include/linux/bpf_verifier.h |  19 ++++---
 kernel/bpf/verifier.c        | 105 +++++++++++++++++------------------
 2 files changed, 62 insertions(+), 62 deletions(-)
include/linux/bpf_verifier.h +11 -8
index 4513372c5bc8..497be9829a5f 100644
@@ -349,7 +349,7 @@ struct bpf_func_state {
 
 #define MAX_CALL_FRAMES 8
 
-/* instruction history flags, used in bpf_jmp_history_entry.flags field */
+/* instruction history flags, used in bpf_insn_hist_entry.flags field */
 enum {
 	/* instruction references stack slot through PTR_TO_STACK register;
 	 * we also store stack's frame number in lower 3 bits (MAX_CALL_FRAMES is 8)
@@ -367,7 +367,7 @@ enum {
 static_assert(INSN_F_FRAMENO_MASK + 1 >= MAX_CALL_FRAMES);
 static_assert(INSN_F_SPI_MASK + 1 >= MAX_BPF_STACK / 8);
 
-struct bpf_jmp_history_entry {
+struct bpf_insn_hist_entry {
 	u32 idx;
 	/* insn idx can't be bigger than 1 million */
 	u32 prev_idx : 22;
@@ -458,13 +458,14 @@ struct bpf_verifier_state {
 	 * See get_loop_entry() for more information.
 	 */
 	struct bpf_verifier_state *loop_entry;
-	/* jmp history recorded from first to last.
-	 * backtracking is using it to go from last to first.
-	 * For most states jmp_history_cnt is [0-3].
+	/* Sub-range of env->insn_hist[] corresponding to this state's
+	 * instruction history.
+	 * Backtracking is using it to go from last to first.
+	 * For most states instruction history is short, 0-3 instructions.
 	 * For loops can go up to ~40.
 	 */
-	struct bpf_jmp_history_entry *jmp_history;
-	u32 jmp_history_cnt;
+	u32 insn_hist_start;
+	u32 insn_hist_end;
 	u32 dfs_depth;
 	u32 callback_unroll_depth;
 	u32 may_goto_depth;
@@ -747,7 +748,9 @@ struct bpf_verifier_env {
 		int cur_stack;
 	} cfg;
 	struct backtrack_state bt;
-	struct bpf_jmp_history_entry *cur_hist_ent;
+	struct bpf_insn_hist_entry *insn_hist;
+	struct bpf_insn_hist_entry *cur_hist_ent;
+	u32 insn_hist_cap;
 	u32 pass_cnt; /* number of times do_check() was called */
 	u32 subprog_cnt;
 	/* number of instructions analyzed by the verifier */
kernel/bpf/verifier.c +51 -54

256 lines not on this page · raw message

Signature · 1 line
2.43.5
#1 lore raw
Quoted 2 lines · Andrii Nakryiko

Async callback state enqueing, while logically detached from parent

typo. enqueuing

Quoted 8 lines
kernel/bpf/verifier.c +4 -3
-static int get_prev_insn_idx(struct bpf_verifier_state *st, int i,
-                            u32 *history)
+static int get_prev_insn_idx(const struct bpf_verifier_env *env,
+                            struct bpf_verifier_state *st,
+                            int insn_idx, u32 hist_start, u32 *hist_endp)
 {
-       u32 cnt = *history;
+       u32 hist_end = *hist_endp;

kernel/bpf/verifier.c static struct bpf_jmp_history_entry *get_jmp_hist_entry(struct bpf_verifier_stat · line 3546

Quoted 10 lines
kernel/bpf/verifier.c +3 -2
+       u32 cnt = hist_end - hist_start;
 
-       if (i == st->first_insn_idx) {
+       if (insn_idx == st->first_insn_idx) {
                if (cnt == 0)
                        return -ENOENT;
-               if (cnt == 1 && st->jmp_history[0].idx == i)
+               if (cnt == 1 && env->insn_hist[hist_end - 1].idx == insn_idx)
                        return -ENOENT;
        }

I think the above bit would be easier to understand if it was env->insn_hist[hist_start].

When cnt==1 it's the same as hist_end-1, but it took me more time to grok that part. With [hist_start] would have been easier. Not a big deal.

Another minor suggestion...
wouldn't it be cleaner to take hist_start/end from 'st' both in get_prev_insn_idx() and in get_insn_hist_entry() ?

So that __mark_chain_precision() doesn't need to reach out into details of 'st' just to pass hist_start/end values into other helpers.

#2 lore raw
Quoted 6 lines · Alexei Starovoitov
Quoted 2 lines · Andrii Nakryiko

Async callback state enqueing, while logically detached from parent

typo. enqueuing

yep, tricky word :) should be "enqueueing", fixed

Quoted 23 lines
Quoted 9 lines
(quoted diff) +4 -3
-static int get_prev_insn_idx(struct bpf_verifier_state *st, int i,
-                            u32 *history)
+static int get_prev_insn_idx(const struct bpf_verifier_env *env,
+                            struct bpf_verifier_state *st,
+                            int insn_idx, u32 hist_start, u32 *hist_endp)
 {
-       u32 cnt = *history;
+       u32 hist_end = *hist_endp;

Review

Quoted 10 lines
(quoted diff) +3 -2
+       u32 cnt = hist_end - hist_start;
 
-       if (i == st->first_insn_idx) {
+       if (insn_idx == st->first_insn_idx) {
                if (cnt == 0)
                        return -ENOENT;
-               if (cnt == 1 && st->jmp_history[0].idx == i)
+               if (cnt == 1 && env->insn_hist[hist_end - 1].idx == insn_idx)
                        return -ENOENT;
        }

I think the above bit would be easier to understand if it was env->insn_hist[hist_start].

Quoted 3 lines

When cnt==1 it's the same as hist_end-1, but it took me more time to grok that part. With [hist_start] would have been easier. Not a big deal.

yep, I agree. Originally I didn't pass hist_start directly, so I would have to use st->insn_hist_start, and it felt too verbose. But now that's not a problem, I'll use hist_start everywhere.

Quoted 7 lines

Another minor suggestion...
wouldn't it be cleaner to take hist_start/end from 'st' both in get_prev_insn_idx() and in get_insn_hist_entry() ?

So that __mark_chain_precision() doesn't need to reach out into details of 'st' just to pass hist_start/end values into other helpers.

Note that for get_prev_insn_idx() we modify (but only locally!) hist_end, as we process instruction history for the currently processed state (we do a virtual stack pop for each entry). So we can't just use st->insn_hist_end, we need a local copy for hist_end that will be updated without touching the actual insn_hist_end. That's the reason I have u32 hist_end = st->insn_hist_end;, to pass &hist_end into get_prev_insn_idx().

Having said that, if you prefer, I can fetch insn_hist_{start, end} from st, always, but then maintain local hist_cnt as input argument for get_insn_hist_enrty() and in/out argument for get_prev_insn_idx(). Would you prefer that? something like below:

kernel/bpf/verifier.c +0 -0
index 15245206d883..34bed6be7449 100644
@@ -3586,10 +3586,14 @@ static int push_insn_history(struct

bpf_verifier_env *env, struct bpf_verifier_s
}

static struct bpf_insn_hist_entry *get_insn_hist_entry(struct
bpf_verifier_env *env,
- u32 hist_start,
u32 hist_end, int insn_idx)
+ struct
bpf_verifier_state *st,
+ u32 hist_cnt,
int insn_idx)
{
- if (hist_end > hist_start && env->insn_hist[hist_end - 1].idx
== insn_idx)
- return &env->insn_hist[hist_end - 1];
+ u32 hist_idx = st->insn_hist_start + hist_cnt - 1;
+
+ if (hist_cnt > 0 && env->insn_hist[hist_idx].idx == insn_idx)
+ return &env->insn_hist[hist_idx];
+

        return NULL;

}

@@ -3608,21 +3612,20 @@ static struct bpf_insn_hist_entry *get_insn_hist_entry(struct bpf_verifier_env *
*/
static int get_prev_insn_idx(const struct bpf_verifier_env *env,
struct bpf_verifier_state *st,
- int insn_idx, u32 hist_start, u32 *hist_endp)
+ int insn_idx, u32 *hist_cntp)
{

-       u32 hist_end = *hist_endp;
-       u32 cnt = hist_end - hist_start;
+       u32 cnt = *hist_cntp;
        if (insn_idx == st->first_insn_idx) {
                if (cnt == 0)
                        return -ENOENT;
-               if (cnt == 1 && env->insn_hist[hist_start].idx == insn_idx)
+               if (cnt == 1 &&
env->insn_hist[st->insn_hist_start].idx == insn_idx)
                        return -ENOENT;
        }

- if (cnt && env->insn_hist[hist_start].idx == insn_idx) {
- (*hist_endp)--;
- return env->insn_hist[hist_start].prev_idx;
+ if (cnt && env->insn_hist[st->insn_hist_start].idx == insn_idx) {
+ *hist_cntp = cnt - 1;

+               return env->insn_hist[st->insn_hist_start].prev_idx;
        } else {
                return insn_idx - 1;
        }

@@ -4378,8 +4381,7 @@ static int __mark_chain_precision(struct bpf_verifier_env *env, int regno)

        for (;;) {
                DECLARE_BITMAP(mask, 64);
-               u32 hist_start = st->insn_hist_start;
-               u32 hist_end = st->insn_hist_end;
+               u32 hist_cnt = st->insn_hist_end - st->insn_hist_start;
                struct bpf_insn_hist_entry *hist;

                if (env->log.level & BPF_LOG_LEVEL2) {
@@ -4419,7 +4421,7 @@ static int __mark_chain_precision(struct
bpf_verifier_env *env, int regno)
                                err = 0;
                                skip_first = false;
                        } else {

- hist = get_insn_hist_entry(env,
hist_start, hist_end, i);
+ hist = get_insn_hist_entry(env, st,
hist_cnt, i);
err = backtrack_insn(env, i,

subseq_idx, hist, bt);
                        }
                        if (err == -ENOTSUPP) {
@@ -4436,7 +4438,7 @@ static int __mark_chain_precision(struct
bpf_verifier_env *env, int regno)
                                 */
                                return 0;
                        subseq_idx = i;
-                       i = get_prev_insn_idx(env, st, i, hist_start,
&hist_end);
+                       i = get_prev_insn_idx(env, st, i, &hist_cnt);
                        if (i == -ENOENT)
                                break;
                        if (i >= env->prog->len) {
#3 lore raw
Quoted 59 lines · Andrii Nakryiko
Quoted 6 lines · Alexei Starovoitov
Quoted 2 lines · Andrii Nakryiko

Async callback state enqueing, while logically detached from parent

typo. enqueuing

yep, tricky word :) should be "enqueueing", fixed

Quoted 23 lines
Quoted 9 lines
(quoted diff) +4 -3
-static int get_prev_insn_idx(struct bpf_verifier_state *st, int i,
-                            u32 *history)
+static int get_prev_insn_idx(const struct bpf_verifier_env *env,
+                            struct bpf_verifier_state *st,
+                            int insn_idx, u32 hist_start, u32 *hist_endp)
 {
-       u32 cnt = *history;
+       u32 hist_end = *hist_endp;

Review

Quoted 10 lines
(quoted diff) +3 -2
+       u32 cnt = hist_end - hist_start;
 
-       if (i == st->first_insn_idx) {
+       if (insn_idx == st->first_insn_idx) {
                if (cnt == 0)
                        return -ENOENT;
-               if (cnt == 1 && st->jmp_history[0].idx == i)
+               if (cnt == 1 && env->insn_hist[hist_end - 1].idx == insn_idx)
                        return -ENOENT;
        }

I think the above bit would be easier to understand if it was env->insn_hist[hist_start].

Quoted 3 lines

When cnt==1 it's the same as hist_end-1, but it took me more time to grok that part. With [hist_start] would have been easier. Not a big deal.

yep, I agree. Originally I didn't pass hist_start directly, so I would have to use st->insn_hist_start, and it felt too verbose. But now that's not a problem, I'll use hist_start everywhere.

Quoted 7 lines

Another minor suggestion...
wouldn't it be cleaner to take hist_start/end from 'st' both in get_prev_insn_idx() and in get_insn_hist_entry() ?

So that __mark_chain_precision() doesn't need to reach out into details of 'st' just to pass hist_start/end values into other helpers.

Note that for get_prev_insn_idx() we modify (but only locally!) hist_end, as we process instruction history for the currently processed state (we do a virtual stack pop for each entry). So we can't just use st->insn_hist_end, we need a local copy for hist_end that will be updated without touching the actual insn_hist_end. That's the reason I have u32 hist_end = st->insn_hist_end;, to pass &hist_end into get_prev_insn_idx().

Quoted 5 lines

Having said that, if you prefer, I can fetch insn_hist_{start, end} from st, always, but then maintain local hist_cnt as input argument for get_insn_hist_enrty() and in/out argument for get_prev_insn_idx(). Would you prefer that? something like below:

Argh, gmail messed this up. See [0] for better formatting.

[0] https://gist.github.com/anakryiko/25228b0ae2760f78b7ae7f0160faa5c1

#4 lore raw
Quoted 68 lines · Andrii Nakryiko
Quoted 59 lines · Andrii Nakryiko
Quoted 6 lines · Alexei Starovoitov
Quoted 2 lines · Andrii Nakryiko

Async callback state enqueing, while logically detached from parent

typo. enqueuing

yep, tricky word :) should be "enqueueing", fixed

Quoted 23 lines
Quoted 9 lines
(quoted diff) +4 -3
-static int get_prev_insn_idx(struct bpf_verifier_state *st, int i,
-                            u32 *history)
+static int get_prev_insn_idx(const struct bpf_verifier_env *env,
+                            struct bpf_verifier_state *st,
+                            int insn_idx, u32 hist_start, u32 *hist_endp)
 {
-       u32 cnt = *history;
+       u32 hist_end = *hist_endp;

Review

Quoted 10 lines
(quoted diff) +3 -2
+       u32 cnt = hist_end - hist_start;
 
-       if (i == st->first_insn_idx) {
+       if (insn_idx == st->first_insn_idx) {
                if (cnt == 0)
                        return -ENOENT;
-               if (cnt == 1 && st->jmp_history[0].idx == i)
+               if (cnt == 1 && env->insn_hist[hist_end - 1].idx == insn_idx)
                        return -ENOENT;
        }

I think the above bit would be easier to understand if it was env->insn_hist[hist_start].

Quoted 3 lines

When cnt==1 it's the same as hist_end-1, but it took me more time to grok that part. With [hist_start] would have been easier. Not a big deal.

yep, I agree. Originally I didn't pass hist_start directly, so I would have to use st->insn_hist_start, and it felt too verbose. But now that's not a problem, I'll use hist_start everywhere.

Quoted 7 lines

Another minor suggestion...
wouldn't it be cleaner to take hist_start/end from 'st' both in get_prev_insn_idx() and in get_insn_hist_entry() ?

So that __mark_chain_precision() doesn't need to reach out into details of 'st' just to pass hist_start/end values into other helpers.

Note that for get_prev_insn_idx() we modify (but only locally!) hist_end, as we process instruction history for the currently processed state (we do a virtual stack pop for each entry). So we can't just use st->insn_hist_end, we need a local copy for hist_end that will be updated without touching the actual insn_hist_end. That's the reason I have u32 hist_end = st->insn_hist_end;, to pass &hist_end into get_prev_insn_idx().

Quoted 5 lines

Having said that, if you prefer, I can fetch insn_hist_{start, end} from st, always, but then maintain local hist_cnt as input argument for get_insn_hist_enrty() and in/out argument for get_prev_insn_idx(). Would you prefer that? something like below:

Quoted 3 lines

Argh, gmail messed this up. See [0] for better formatting.

[0] https://gist.github.com/anakryiko/25228b0ae2760f78b7ae7f0160faa5c1

I had a tiny bug in get_prev_insns_idx(), fixing which makes get_prev_insn_idx() a bit verbose if using this hist_cnt approach:

static int get_prev_insn_idx(const struct bpf_verifier_env *env,
struct bpf_verifier_state *st, int insn_idx, u32 *hist_cntp)
{
u32 cnt = *hist_cntp;

  if (insn_idx == st->first_insn_idx) {
    if (cnt == 0)
      return -ENOENT;
      if (cnt == 1 && env->insn_hist[st->insn_hist_start].idx == insn_idx)
        return -ENOENT;
  }

if (cnt && env->insn_hist[st->insn_hist_start + hist_cnt - 1].idx ==

insn_idx) {
    *hist_cntp = cnt - 1;
    return env->insn_hist[st->insn_hist_start + hist_cnt - 1].prev_idx;
  } else {
    return insn_idx - 1;

}
}

I mean that env->insn_hist[st->insn_hist_start + hist_cnt - 1] in last if/else. But let me know which way you prefer it anyways.

#5 lore raw
Quoted 97 lines · Andrii Nakryiko
Quoted 68 lines · Andrii Nakryiko
Quoted 59 lines · Andrii Nakryiko
Quoted 6 lines · Alexei Starovoitov
Quoted 2 lines · Andrii Nakryiko

Async callback state enqueing, while logically detached from parent

typo. enqueuing

yep, tricky word :) should be "enqueueing", fixed

Quoted 23 lines
Quoted 9 lines
(quoted diff) +4 -3
-static int get_prev_insn_idx(struct bpf_verifier_state *st, int i,
-                            u32 *history)
+static int get_prev_insn_idx(const struct bpf_verifier_env *env,
+                            struct bpf_verifier_state *st,
+                            int insn_idx, u32 hist_start, u32 *hist_endp)
 {
-       u32 cnt = *history;
+       u32 hist_end = *hist_endp;

Review

Quoted 10 lines
(quoted diff) +3 -2
+       u32 cnt = hist_end - hist_start;
 
-       if (i == st->first_insn_idx) {
+       if (insn_idx == st->first_insn_idx) {
                if (cnt == 0)
                        return -ENOENT;
-               if (cnt == 1 && st->jmp_history[0].idx == i)
+               if (cnt == 1 && env->insn_hist[hist_end - 1].idx == insn_idx)
                        return -ENOENT;
        }

I think the above bit would be easier to understand if it was env->insn_hist[hist_start].

Quoted 3 lines

When cnt==1 it's the same as hist_end-1, but it took me more time to grok that part. With [hist_start] would have been easier. Not a big deal.

yep, I agree. Originally I didn't pass hist_start directly, so I would have to use st->insn_hist_start, and it felt too verbose. But now that's not a problem, I'll use hist_start everywhere.

Quoted 7 lines

Another minor suggestion...
wouldn't it be cleaner to take hist_start/end from 'st' both in get_prev_insn_idx() and in get_insn_hist_entry() ?

So that __mark_chain_precision() doesn't need to reach out into details of 'st' just to pass hist_start/end values into other helpers.

Note that for get_prev_insn_idx() we modify (but only locally!) hist_end, as we process instruction history for the currently processed state (we do a virtual stack pop for each entry). So we can't just use st->insn_hist_end, we need a local copy for hist_end that will be updated without touching the actual insn_hist_end. That's the reason I have u32 hist_end = st->insn_hist_end;, to pass &hist_end into get_prev_insn_idx().

Quoted 5 lines

Having said that, if you prefer, I can fetch insn_hist_{start, end} from st, always, but then maintain local hist_cnt as input argument for get_insn_hist_enrty() and in/out argument for get_prev_insn_idx(). Would you prefer that? something like below:

Quoted 3 lines

Argh, gmail messed this up. See [0] for better formatting.

[0] https://gist.github.com/anakryiko/25228b0ae2760f78b7ae7f0160faa5c1

I had a tiny bug in get_prev_insns_idx(), fixing which makes get_prev_insn_idx() a bit verbose if using this hist_cnt approach:

static int get_prev_insn_idx(const struct bpf_verifier_env *env,
struct bpf_verifier_state *st, int insn_idx, u32 *hist_cntp)
{
u32 cnt = *hist_cntp;

  if (insn_idx == st->first_insn_idx) {
    if (cnt == 0)
      return -ENOENT;
      if (cnt == 1 && env->insn_hist[st->insn_hist_start].idx == insn_idx)
        return -ENOENT;
  }

if (cnt && env->insn_hist[st->insn_hist_start + hist_cnt - 1].idx ==

insn_idx) {
    *hist_cntp = cnt - 1;
    return env->insn_hist[st->insn_hist_start + hist_cnt - 1].prev_idx;
  } else {
    return insn_idx - 1;
Quoted 6 lines

}
}

I mean that env->insn_hist[st->insn_hist_start + hist_cnt - 1] in last if/else. But let me know which way you prefer it anyways.

Ohh. I missed that decrement is local to __mark_chain_precision(). Original version is probably better than when it passes start/end around. This hist_cnt approach is harder to read.

So pls resend with typo fixed.