bpf: use common instruction history across all states
Andrii Nakryiko
maintainerPATCH 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
@@ -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
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.
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 inget_prev_insn_idx()and inget_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
@@ -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(structbpf_verifier_env *env,
- u32 hist_start,
u32 hist_end, int insn_idx)
+ structbpf_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) {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_startdirectly, so I would have to usest->insn_hist_start, and it felt too verbose. But now that's not a problem, I'll usehist_starteverywhere.Quoted 7 lines
Another minor suggestion...
wouldn't it be cleaner to take hist_start/end from 'st' both inget_prev_insn_idx()and inget_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 usest->insn_hist_end, we need a local copy forhist_endthat will be updated without touching the actualinsn_hist_end. That's the reason I haveu32 hist_end = st->insn_hist_end;, to pass&hist_endintoget_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_cntas input argument forget_insn_hist_enrty()and in/out argument forget_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
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_startdirectly, so I would have to usest->insn_hist_start, and it felt too verbose. But now that's not a problem, I'll usehist_starteverywhere.Quoted 7 lines
Another minor suggestion...
wouldn't it be cleaner to take hist_start/end from 'st' both inget_prev_insn_idx()and inget_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 usest->insn_hist_end, we need a local copy forhist_endthat will be updated without touching the actualinsn_hist_end. That's the reason I haveu32 hist_end = st->insn_hist_end;, to pass&hist_endintoget_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_cntas input argument forget_insn_hist_enrty()and in/out argument forget_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.
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_startdirectly, so I would have to usest->insn_hist_start, and it felt too verbose. But now that's not a problem, I'll usehist_starteverywhere.Quoted 7 lines
Another minor suggestion...
wouldn't it be cleaner to take hist_start/end from 'st' both inget_prev_insn_idx()and inget_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 usest->insn_hist_end, we need a local copy forhist_endthat will be updated without touching the actualinsn_hist_end. That's the reason I haveu32 hist_end = st->insn_hist_end;, to pass&hist_endintoget_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_cntas input argument forget_insn_hist_enrty()and in/out argument forget_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 makesget_prev_insn_idx()a bit verbose if using thishist_cntapproach:static int get_prev_insn_idx(const struct
bpf_verifier_env*env,
structbpf_verifier_state*st, intinsn_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.