diff options
| author | Eduard Zingerman <eddyz87@gmail.com> | 2025-02-15 03:03:57 -0800 |
|---|---|---|
| committer | Alexei Starovoitov <ast@kernel.org> | 2025-02-18 19:22:59 -0800 |
| commit | bb7abf3049025f7e4ad91cff2d9fe8381a9278af (patch) | |
| tree | 69e00fb0be6e806656e9463cb72051bf794bf223 /kernel/bpf/verifier.c | |
| parent | bpf: detect infinite loop in get_loop_entry() (diff) | |
| download | linux-bb7abf3049025f7e4ad91cff2d9fe8381a9278af.tar.gz linux-bb7abf3049025f7e4ad91cff2d9fe8381a9278af.zip | |
bpf: make state->dfs_depth < state->loop_entry->dfs_depth an invariant
For a generic loop detection algorithm a graph node can be a loop
header for itself. However, state loop entries are computed for use in
is_state_visited(), where get_loop_entry(state)->branches is checked.
is_state_visited() also checks state->branches, thus the case when
state == state->loop_entry is not interesting for is_state_visited().
This change does not affect correctness, but simplifies
get_loop_entry() a bit and also simplifies change to
update_loop_entry() in patch 9.
Signed-off-by: Eduard Zingerman <eddyz87@gmail.com>
Link: https://lore.kernel.org/r/20250215110411.3236773-7-eddyz87@gmail.com
Signed-off-by: Alexei Starovoitov <ast@kernel.org>
Diffstat (limited to 'kernel/bpf/verifier.c')
| -rw-r--r-- | kernel/bpf/verifier.c | 6 |
1 files changed, 3 insertions, 3 deletions
diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c index ddf6ed9f3482..cb5ae7dc6488 100644 --- a/kernel/bpf/verifier.c +++ b/kernel/bpf/verifier.c @@ -1799,7 +1799,7 @@ static bool same_callsites(struct bpf_verifier_state *a, struct bpf_verifier_sta * # Find outermost loop entry known for n * def get_loop_entry(n): * h = entries.get(n, None) - * while h in entries and entries[h] != h: + * while h in entries: * h = entries[h] * return h * @@ -1838,7 +1838,7 @@ static struct bpf_verifier_state *get_loop_entry(struct bpf_verifier_env *env, struct bpf_verifier_state *topmost = st->loop_entry, *old; u32 steps = 0; - while (topmost && topmost->loop_entry && topmost != topmost->loop_entry) { + while (topmost && topmost->loop_entry) { if (steps++ > st->dfs_depth) { WARN_ONCE(true, "verifier bug: infinite loop in get_loop_entry\n"); verbose(env, "verifier bug: infinite loop in get_loop_entry()\n"); @@ -1865,7 +1865,7 @@ static void update_loop_entry(struct bpf_verifier_state *cur, struct bpf_verifie * hence 'cur' and 'hdr' are not in the same loop and there is * no need to update cur->loop_entry. */ - if (hdr->branches && hdr->dfs_depth <= (cur->loop_entry ?: cur)->dfs_depth) { + if (hdr->branches && hdr->dfs_depth < (cur->loop_entry ?: cur)->dfs_depth) { cur->loop_entry = hdr; hdr->used_as_loop_entry = true; } |