// SPDX-License-Identifier: GPL-2.0-only/* Copyright (c) 2026 Meta Platforms, Inc. and affiliates. */#include <linux/bpf.h>#include <linux/bpf_verifier.h>#include <linux/filter.h>#include <linux/sort.h> #define verbose(env, fmt, args...) bpf_verifier_log_write(env, fmt, ##args) /* non-recursive DFS pseudo code * 1 procedure DFS-iterative(G,v): * 2 label v as discovered * 3 let S be a stack * 4 S.push(v) * 5 while S is not empty * 6 t <- S.peek() * 7 if t is what we're looking for: * 8 return t * 9 for all edges e in G.adjacentEdges(t) do * 10 if edge e is already labelled * 11 continue with the next edge * 12 w <- G.adjacentVertex(t,e) * 13 if vertex w is not discovered and not explored * 14 label e as tree-edge * 15 label w as discovered * 16 S.push(w) * 17 continue at 5 * 18 else if vertex w is discovered * 19 label e as back-edge * 20 else * 21 // vertex w is explored * 22 label e as forward- or cross-edge * 23 label t as explored * 24 S.pop() * * convention: * 0x10 - discovered * 0x11 - discovered and fall-through edge labelled * 0x12 - discovered and fall-through and branch edges labelled * 0x20 - explored */ enum { DISCOVERED = 0x10, EXPLORED = 0x20, FALLTHROUGH = 1, BRANCH = 2,}; static void mark_subprog_changes_pkt_data(struct bpf_verifier_env *env, int off){ struct bpf_subprog_info *subprog; subprog = bpf_find_containing_subprog(env, off); subprog->changes_pkt_data = true;} static void mark_subprog_might_sleep(struct bpf_verifier_env *env, int off){ struct bpf_subprog_info *subprog; subprog = bpf_find_containing_subprog(env, off); subprog->might_sleep = true;} static void mark_subprog_might_throw(struct bpf_verifier_env *env, int off){ struct bpf_subprog_info *subprog; subprog = bpf_find_containing_subprog(env, off); subprog->might_throw = true;} /* 't' is an index of a call-site. * 'w' is a callee entry point. * Eventually this function would be called when env->cfg.insn_state[w] == EXPLORED. * Rely on DFS traversal order and absence of recursive calls to guarantee that * callee's effect marks would be correct at that moment. */static void merge_callee_effects(struct bpf_verifier_env *env, int t, int w){ struct bpf_subprog_info *caller, *callee; caller = bpf_find_containing_subprog(env, t); callee = bpf_find_containing_subprog(env, w); caller->changes_pkt_data |= callee->changes_pkt_data; caller->might_sleep |= callee->might_sleep; caller->might_throw |= callee->might_throw;} enum { DONE_EXPLORING = 0, KEEP_EXPLORING = 1,}; /* t, w, e - match pseudo-code above: * t - index of current instruction * w - next instruction * e - edge */static int push_insn(int t, int w, int e, struct bpf_verifier_env *env){ int *insn_stack = env->cfg.insn_stack; int *insn_state = env->cfg.insn_state; if (e == FALLTHROUGH && insn_state[t] >= (DISCOVERED | FALLTHROUGH)) return DONE_EXPLORING; if (e == BRANCH && insn_state[t] >= (DISCOVERED | BRANCH)) return DONE_EXPLORING; if (w < 0 || w >= env->prog->len) { verbose_linfo(env, t, "%d: ", t); verbose(env, "jump out of range from insn %d to %d\n", t, w); return -EINVAL; } if (e == BRANCH) { /* mark branch target for state pruning */ mark_prune_point(env, w); mark_jmp_point(env, w); } if (insn_state[w] == 0) { /* tree-edge */ insn_state[t] = DISCOVERED | e; insn_state[w] = DISCOVERED; if (env->cfg.cur_stack >= env->prog->len) return -E2BIG; insn_stack[env->cfg.cur_stack++] = w; return KEEP_EXPLORING; } else if ((insn_state[w] & 0xF0) == DISCOVERED) { if (env->bpf_capable) return DONE_EXPLORING; verbose_linfo(env, t, "%d: ", t); verbose_linfo(env, w, "%d: ", w); verbose(env, "back-edge from insn %d to %d\n", t, w); return -EINVAL; } else if (insn_state[w] == EXPLORED) { /* forward- or cross-edge */ insn_state[t] = DISCOVERED | e; } else { verifier_bug(env, "insn state internal bug"); return -EFAULT; } return DONE_EXPLORING;} static int visit_func_call_insn(int t, struct bpf_insn *insns, struct bpf_verifier_env *env, bool visit_callee){ int ret, insn_sz; int w; insn_sz = bpf_is_ldimm64(&insns[t]) ? 2 : 1; ret = push_insn(t, t + insn_sz, FALLTHROUGH, env); if (ret) return ret; mark_prune_point(env, t + insn_sz); /* when we exit from subprog, we need to record non-linear history */ mark_jmp_point(env, t + insn_sz); if (visit_callee) { w = t + insns[t].imm + 1; mark_prune_point(env, t); merge_callee_effects(env, t, w); ret = push_insn(t, w, BRANCH, env); } return ret;} struct bpf_iarray *bpf_iarray_realloc(struct bpf_iarray *old, size_t n_elem){ size_t new_size = sizeof(struct bpf_iarray) + n_elem * sizeof(old->items[0]); struct bpf_iarray *new; new = kvrealloc(old, new_size, GFP_KERNEL_ACCOUNT); if (!new) { /* this is what callers always want, so simplify the call site */ kvfree(old); return NULL; } new->cnt = n_elem; return new;} static int copy_insn_array(struct bpf_map *map, u32 start, u32 end, u32 *items){ struct bpf_insn_array_value *value; u32 i; for (i = start; i <= end; i++) { value = map->ops->map_lookup_elem(map, &i); /* * map_lookup_elem of an array map will never return an error, * but not checking it makes some static analysers to worry */ if (IS_ERR(value)) return PTR_ERR(value); else if (!value) return -EINVAL; items[i - start] = value->xlated_off; } return 0;} static int cmp_ptr_to_u32(const void *a, const void *b){ return *(u32 *)a - *(u32 *)b;} static int sort_insn_array_uniq(u32 *items, int cnt){ int unique = 1; int i; sort(items, cnt, sizeof(items[0]), cmp_ptr_to_u32, NULL); for (i = 1; i < cnt; i++) if (items[i] != items[unique - 1]) items[unique++] = items[i]; return unique;} /* * sort_unique({map[start], ..., map[end]}) into off */int bpf_copy_insn_array_uniq(struct bpf_map *map, u32 start, u32 end, u32 *off){ u32 n = end - start + 1; int err; err = copy_insn_array(map, start, end, off); if (err) return err; return sort_insn_array_uniq(off, n);} /* * Copy all unique offsets from the map */static struct bpf_iarray *jt_from_map(struct bpf_map *map){ struct bpf_iarray *jt; int err; int n; jt = bpf_iarray_realloc(NULL, map->max_entries); if (!jt) return ERR_PTR(-ENOMEM); n = bpf_copy_insn_array_uniq(map, 0, map->max_entries - 1, jt->items); if (n < 0) { err = n; goto err_free; } if (n == 0) { err = -EINVAL; goto err_free; } jt->cnt = n; return jt; err_free: kvfree(jt); return ERR_PTR(err);} /* * Find and collect all maps which fit in the subprog. Return the result as one * combined jump table in jt->items (allocated with kvcalloc) */static struct bpf_iarray *jt_from_subprog(struct bpf_verifier_env *env, int subprog_start, int subprog_end){ struct bpf_iarray *jt = NULL; struct bpf_map *map; struct bpf_iarray *jt_cur; int i; for (i = 0; i < env->insn_array_map_cnt; i++) { /* * TODO (when needed): collect only jump tables, not static keys * or maps for indirect calls */ map = env->insn_array_maps[i]; jt_cur = jt_from_map(map); if (IS_ERR(jt_cur)) { kvfree(jt); return jt_cur; } /* * This is enough to check one element. The full table is * checked to fit inside the subprog later in create_jt() */ if (jt_cur->items[0] >= subprog_start && jt_cur->items[0] < subprog_end) { u32 old_cnt = jt ? jt->cnt : 0; jt = bpf_iarray_realloc(jt, old_cnt + jt_cur->cnt); if (!jt) { kvfree(jt_cur); return ERR_PTR(-ENOMEM); } memcpy(jt->items + old_cnt, jt_cur->items, jt_cur->cnt << 2); } kvfree(jt_cur); } if (!jt) { verbose(env, "no jump tables found for subprog starting at %u\n", subprog_start); return ERR_PTR(-EINVAL); } jt->cnt = sort_insn_array_uniq(jt->items, jt->cnt); return jt;} static struct bpf_iarray *create_jt(int t, struct bpf_verifier_env *env){ struct bpf_subprog_info *subprog; int subprog_start, subprog_end; struct bpf_iarray *jt; int i; subprog = bpf_find_containing_subprog(env, t); subprog_start = subprog->start; subprog_end = (subprog + 1)->start; jt = jt_from_subprog(env, subprog_start, subprog_end); if (IS_ERR(jt)) return jt; /* Check that the every element of the jump table fits within the given subprogram */ for (i = 0; i < jt->cnt; i++) { if (jt->items[i] < subprog_start || jt->items[i] >= subprog_end) { verbose(env, "jump table for insn %d points outside of the subprog [%u,%u]\n", t, subprog_start, subprog_end); kvfree(jt); return ERR_PTR(-EINVAL); } } return jt;} /* "conditional jump with N edges" */static int visit_gotox_insn(int t, struct bpf_verifier_env *env){ int *insn_stack = env->cfg.insn_stack; int *insn_state = env->cfg.insn_state; bool keep_exploring = false; struct bpf_iarray *jt; int i, w; jt = env->insn_aux_data[t].jt; if (!jt) { jt = create_jt(t, env); if (IS_ERR(jt)) return PTR_ERR(jt); env->insn_aux_data[t].jt = jt; } mark_prune_point(env, t); for (i = 0; i < jt->cnt; i++) { w = jt->items[i]; if (w < 0 || w >= env->prog->len) { verbose(env, "indirect jump out of range from insn %d to %d\n", t, w); return -EINVAL; } mark_jmp_point(env, w); /* EXPLORED || DISCOVERED */ if (insn_state[w]) continue; if (env->cfg.cur_stack >= env->prog->len) return -E2BIG; insn_stack[env->cfg.cur_stack++] = w; insn_state[w] |= DISCOVERED; keep_exploring = true; } return keep_exploring ? KEEP_EXPLORING : DONE_EXPLORING;} /* * Instructions that can abnormally return from a subprog (tail_call * upon success, ld_{abs,ind} upon load failure) have a hidden exit * that the verifier must account for. */static int visit_abnormal_return_insn(struct bpf_verifier_env *env, int t){ struct bpf_subprog_info *subprog; struct bpf_iarray *jt; if (env->insn_aux_data[t].jt) return 0; jt = bpf_iarray_realloc(NULL, 2); if (!jt) return -ENOMEM; subprog = bpf_find_containing_subprog(env, t); jt->items[0] = t + 1; jt->items[1] = subprog->exit_idx; env->insn_aux_data[t].jt = jt; return 0;} /* Visits the instruction at index t and returns one of the following: * < 0 - an error occurred * DONE_EXPLORING - the instruction was fully explored * KEEP_EXPLORING - there is still work to be done before it is fully explored */static int visit_insn(int t, struct bpf_verifier_env *env){ struct bpf_insn *insns = env->prog->insnsi, *insn = &insns[t]; int ret, off, insn_sz; if (bpf_pseudo_func(insn)) return visit_func_call_insn(t, insns, env, true); /* All non-branch instructions have a single fall-through edge. */ if (BPF_CLASS(insn->code) != BPF_JMP && BPF_CLASS(insn->code) != BPF_JMP32) { if (BPF_CLASS(insn->code) == BPF_LD && (BPF_MODE(insn->code) == BPF_ABS || BPF_MODE(insn->code) == BPF_IND)) { ret = visit_abnormal_return_insn(env, t); if (ret) return ret; } insn_sz = bpf_is_ldimm64(insn) ? 2 : 1; return push_insn(t, t + insn_sz, FALLTHROUGH, env); } switch (BPF_OP(insn->code)) { case BPF_EXIT: return DONE_EXPLORING; case BPF_CALL: if (bpf_is_async_callback_calling_insn(insn)) /* Mark this call insn as a prune point to trigger * is_state_visited() check before call itself is * processed by __check_func_call(). Otherwise new * async state will be pushed for further exploration. */ mark_prune_point(env, t); /* For functions that invoke callbacks it is not known how many times * callback would be called. Verifier models callback calling functions * by repeatedly visiting callback bodies and returning to origin call * instruction. * In order to stop such iteration verifier needs to identify when a * state identical some state from a previous iteration is reached. * Check below forces creation of checkpoint before callback calling * instruction to allow search for such identical states. */ if (bpf_is_sync_callback_calling_insn(insn)) { mark_calls_callback(env, t); mark_force_checkpoint(env, t); mark_prune_point(env, t); mark_jmp_point(env, t); } if (bpf_helper_call(insn)) { const struct bpf_func_proto *fp; ret = bpf_get_helper_proto(env, insn->imm, &fp); /* If called in a non-sleepable context program will be * rejected anyway, so we should end up with precise * sleepable marks on subprogs, except for dead code * elimination. */ if (ret == 0 && fp->might_sleep) mark_subprog_might_sleep(env, t); if (bpf_helper_changes_pkt_data(insn->imm)) mark_subprog_changes_pkt_data(env, t); if (insn->imm == BPF_FUNC_tail_call) { ret = visit_abnormal_return_insn(env, t); if (ret) return ret; } } else if (insn->src_reg == BPF_PSEUDO_KFUNC_CALL) { struct bpf_kfunc_call_arg_meta meta; ret = bpf_fetch_kfunc_arg_meta(env, insn->imm, insn->off, &meta); if (ret == 0 && bpf_is_iter_next_kfunc(&meta)) { mark_prune_point(env, t); /* Checking and saving state checkpoints at iter_next() call * is crucial for fast convergence of open-coded iterator loopLines 1–500 of 883. Load more
// SPDX-License-Identifier: GPL-2.0-only /* Copyright (c) 2026 Meta Platforms, Inc. and affiliates. */ #include <linux/bpf.h> #include <linux/bpf_verifier.h> #include <linux/filter.h> #include <linux/sort.h> #define verbose(env, fmt, args...) bpf_verifier_log_write(env, fmt, ##args) /* non-recursive DFS pseudo code * 1 procedure DFS-iterative(G,v): * 2 label v as discovered * 3 let S be a stack * 4 S.push(v) * 5 while S is not empty * 6 t <- S.peek() * 7 if t is what we're looking for: * 8 return t * 9 for all edges e in G.adjacentEdges(t) do * 10 if edge e is already labelled * 11 continue with the next edge * 12 w <- G.adjacentVertex(t,e) * 13 if vertex w is not discovered and not explored * 14 label e as tree-edge * 15 label w as discovered * 16 S.push(w) * 17 continue at 5 * 18 else if vertex w is discovered * 19 label e as back-edge * 20 else * 21 // vertex w is explored * 22 label e as forward- or cross-edge * 23 label t as explored * 24 S.pop() * * convention: * 0x10 - discovered * 0x11 - discovered and fall-through edge labelled * 0x12 - discovered and fall-through and branch edges labelled * 0x20 - explored */ enum { DISCOVERED = 0x10, EXPLORED = 0x20, FALLTHROUGH = 1, BRANCH = 2, }; static void mark_subprog_changes_pkt_data(struct bpf_verifier_env *env, int off) { struct bpf_subprog_info *subprog; subprog = bpf_find_containing_subprog(env, off); subprog->changes_pkt_data = true; } static void mark_subprog_might_sleep(struct bpf_verifier_env *env, int off) { struct bpf_subprog_info *subprog; subprog = bpf_find_containing_subprog(env, off); subprog->might_sleep = true; } static void mark_subprog_might_throw(struct bpf_verifier_env *env, int off) { struct bpf_subprog_info *subprog; subprog = bpf_find_containing_subprog(env, off); subprog->might_throw = true; } /* 't' is an index of a call-site. * 'w' is a callee entry point. * Eventually this function would be called when env->cfg.insn_state[w] == EXPLORED. * Rely on DFS traversal order and absence of recursive calls to guarantee that * callee's effect marks would be correct at that moment. */ static void merge_callee_effects(struct bpf_verifier_env *env, int t, int w) { struct bpf_subprog_info *caller, *callee; caller = bpf_find_containing_subprog(env, t); callee = bpf_find_containing_subprog(env, w); caller->changes_pkt_data |= callee->changes_pkt_data; caller->might_sleep |= callee->might_sleep; caller->might_throw |= callee->might_throw; } enum { DONE_EXPLORING = 0, KEEP_EXPLORING = 1, }; /* t, w, e - match pseudo-code above: * t - index of current instruction * w - next instruction * e - edge */ static int push_insn(int t, int w, int e, struct bpf_verifier_env *env) { int *insn_stack = env->cfg.insn_stack; int *insn_state = env->cfg.insn_state; if (e == FALLTHROUGH && insn_state[t] >= (DISCOVERED | FALLTHROUGH)) return DONE_EXPLORING; if (e == BRANCH && insn_state[t] >= (DISCOVERED | BRANCH)) return DONE_EXPLORING; if (w < 0 || w >= env->prog->len) { verbose_linfo(env, t, "%d: ", t); verbose(env, "jump out of range from insn %d to %d\n", t, w); return -EINVAL; } if (e == BRANCH) { /* mark branch target for state pruning */ mark_prune_point(env, w); mark_jmp_point(env, w); } if (insn_state[w] == 0) { /* tree-edge */ insn_state[t] = DISCOVERED | e; insn_state[w] = DISCOVERED; if (env->cfg.cur_stack >= env->prog->len) return -E2BIG; insn_stack[env->cfg.cur_stack++] = w; return KEEP_EXPLORING; } else if ((insn_state[w] & 0xF0) == DISCOVERED) { if (env->bpf_capable) return DONE_EXPLORING; verbose_linfo(env, t, "%d: ", t); verbose_linfo(env, w, "%d: ", w); verbose(env, "back-edge from insn %d to %d\n", t, w); return -EINVAL; } else if (insn_state[w] == EXPLORED) { /* forward- or cross-edge */ insn_state[t] = DISCOVERED | e; } else { verifier_bug(env, "insn state internal bug"); return -EFAULT; } return DONE_EXPLORING; } static int visit_func_call_insn(int t, struct bpf_insn *insns, struct bpf_verifier_env *env, bool visit_callee) { int ret, insn_sz; int w; insn_sz = bpf_is_ldimm64(&insns[t]) ? 2 : 1; ret = push_insn(t, t + insn_sz, FALLTHROUGH, env); if (ret) return ret; mark_prune_point(env, t + insn_sz); /* when we exit from subprog, we need to record non-linear history */ mark_jmp_point(env, t + insn_sz); if (visit_callee) { w = t + insns[t].imm + 1; mark_prune_point(env, t); merge_callee_effects(env, t, w); ret = push_insn(t, w, BRANCH, env); } return ret; } struct bpf_iarray *bpf_iarray_realloc(struct bpf_iarray *old, size_t n_elem) { size_t new_size = sizeof(struct bpf_iarray) + n_elem * sizeof(old->items[0]); struct bpf_iarray *new; new = kvrealloc(old, new_size, GFP_KERNEL_ACCOUNT); if (!new) { /* this is what callers always want, so simplify the call site */ kvfree(old); return NULL; } new->cnt = n_elem; return new; } static int copy_insn_array(struct bpf_map *map, u32 start, u32 end, u32 *items) { struct bpf_insn_array_value *value; u32 i; for (i = start; i <= end; i++) { value = map->ops->map_lookup_elem(map, &i); /* * map_lookup_elem of an array map will never return an error, * but not checking it makes some static analysers to worry */ if (IS_ERR(value)) return PTR_ERR(value); else if (!value) return -EINVAL; items[i - start] = value->xlated_off; } return 0; } static int cmp_ptr_to_u32(const void *a, const void *b) { return *(u32 *)a - *(u32 *)b; } static int sort_insn_array_uniq(u32 *items, int cnt) { int unique = 1; int i; sort(items, cnt, sizeof(items[0]), cmp_ptr_to_u32, NULL); for (i = 1; i < cnt; i++) if (items[i] != items[unique - 1]) items[unique++] = items[i]; return unique; } /* * sort_unique({map[start], ..., map[end]}) into off */ int bpf_copy_insn_array_uniq(struct bpf_map *map, u32 start, u32 end, u32 *off) { u32 n = end - start + 1; int err; err = copy_insn_array(map, start, end, off); if (err) return err; return sort_insn_array_uniq(off, n); } /* * Copy all unique offsets from the map */ static struct bpf_iarray *jt_from_map(struct bpf_map *map) { struct bpf_iarray *jt; int err; int n; jt = bpf_iarray_realloc(NULL, map->max_entries); if (!jt) return ERR_PTR(-ENOMEM); n = bpf_copy_insn_array_uniq(map, 0, map->max_entries - 1, jt->items); if (n < 0) { err = n; goto err_free; } if (n == 0) { err = -EINVAL; goto err_free; } jt->cnt = n; return jt; err_free: kvfree(jt); return ERR_PTR(err); } /* * Find and collect all maps which fit in the subprog. Return the result as one * combined jump table in jt->items (allocated with kvcalloc) */ static struct bpf_iarray *jt_from_subprog(struct bpf_verifier_env *env, int subprog_start, int subprog_end) { struct bpf_iarray *jt = NULL; struct bpf_map *map; struct bpf_iarray *jt_cur; int i; for (i = 0; i < env->insn_array_map_cnt; i++) { /* * TODO (when needed): collect only jump tables, not static keys * or maps for indirect calls */ map = env->insn_array_maps[i]; jt_cur = jt_from_map(map); if (IS_ERR(jt_cur)) { kvfree(jt); return jt_cur; } /* * This is enough to check one element. The full table is * checked to fit inside the subprog later in create_jt() */ if (jt_cur->items[0] >= subprog_start && jt_cur->items[0] < subprog_end) { u32 old_cnt = jt ? jt->cnt : 0; jt = bpf_iarray_realloc(jt, old_cnt + jt_cur->cnt); if (!jt) { kvfree(jt_cur); return ERR_PTR(-ENOMEM); } memcpy(jt->items + old_cnt, jt_cur->items, jt_cur->cnt << 2); } kvfree(jt_cur); } if (!jt) { verbose(env, "no jump tables found for subprog starting at %u\n", subprog_start); return ERR_PTR(-EINVAL); } jt->cnt = sort_insn_array_uniq(jt->items, jt->cnt); return jt; } static struct bpf_iarray * create_jt(int t, struct bpf_verifier_env *env) { struct bpf_subprog_info *subprog; int subprog_start, subprog_end; struct bpf_iarray *jt; int i; subprog = bpf_find_containing_subprog(env, t); subprog_start = subprog->start; subprog_end = (subprog + 1)->start; jt = jt_from_subprog(env, subprog_start, subprog_end); if (IS_ERR(jt)) return jt; /* Check that the every element of the jump table fits within the given subprogram */ for (i = 0; i < jt->cnt; i++) { if (jt->items[i] < subprog_start || jt->items[i] >= subprog_end) { verbose(env, "jump table for insn %d points outside of the subprog [%u,%u]\n", t, subprog_start, subprog_end); kvfree(jt); return ERR_PTR(-EINVAL); } } return jt; } /* "conditional jump with N edges" */ static int visit_gotox_insn(int t, struct bpf_verifier_env *env) { int *insn_stack = env->cfg.insn_stack; int *insn_state = env->cfg.insn_state; bool keep_exploring = false; struct bpf_iarray *jt; int i, w; jt = env->insn_aux_data[t].jt; if (!jt) { jt = create_jt(t, env); if (IS_ERR(jt)) return PTR_ERR(jt); env->insn_aux_data[t].jt = jt; } mark_prune_point(env, t); for (i = 0; i < jt->cnt; i++) { w = jt->items[i]; if (w < 0 || w >= env->prog->len) { verbose(env, "indirect jump out of range from insn %d to %d\n", t, w); return -EINVAL; } mark_jmp_point(env, w); /* EXPLORED || DISCOVERED */ if (insn_state[w]) continue; if (env->cfg.cur_stack >= env->prog->len) return -E2BIG; insn_stack[env->cfg.cur_stack++] = w; insn_state[w] |= DISCOVERED; keep_exploring = true; } return keep_exploring ? KEEP_EXPLORING : DONE_EXPLORING; } /* * Instructions that can abnormally return from a subprog (tail_call * upon success, ld_{abs,ind} upon load failure) have a hidden exit * that the verifier must account for. */ static int visit_abnormal_return_insn(struct bpf_verifier_env *env, int t) { struct bpf_subprog_info *subprog; struct bpf_iarray *jt; if (env->insn_aux_data[t].jt) return 0; jt = bpf_iarray_realloc(NULL, 2); if (!jt) return -ENOMEM; subprog = bpf_find_containing_subprog(env, t); jt->items[0] = t + 1; jt->items[1] = subprog->exit_idx; env->insn_aux_data[t].jt = jt; return 0; } /* Visits the instruction at index t and returns one of the following: * < 0 - an error occurred * DONE_EXPLORING - the instruction was fully explored * KEEP_EXPLORING - there is still work to be done before it is fully explored */ static int visit_insn(int t, struct bpf_verifier_env *env) { struct bpf_insn *insns = env->prog->insnsi, *insn = &insns[t]; int ret, off, insn_sz; if (bpf_pseudo_func(insn)) return visit_func_call_insn(t, insns, env, true); /* All non-branch instructions have a single fall-through edge. */ if (BPF_CLASS(insn->code) != BPF_JMP && BPF_CLASS(insn->code) != BPF_JMP32) { if (BPF_CLASS(insn->code) == BPF_LD && (BPF_MODE(insn->code) == BPF_ABS || BPF_MODE(insn->code) == BPF_IND)) { ret = visit_abnormal_return_insn(env, t); if (ret) return ret; } insn_sz = bpf_is_ldimm64(insn) ? 2 : 1; return push_insn(t, t + insn_sz, FALLTHROUGH, env); } switch (BPF_OP(insn->code)) { case BPF_EXIT: return DONE_EXPLORING; case BPF_CALL: if (bpf_is_async_callback_calling_insn(insn)) /* Mark this call insn as a prune point to trigger * is_state_visited() check before call itself is * processed by __check_func_call(). Otherwise new * async state will be pushed for further exploration. */ mark_prune_point(env, t); /* For functions that invoke callbacks it is not known how many times * callback would be called. Verifier models callback calling functions * by repeatedly visiting callback bodies and returning to origin call * instruction. * In order to stop such iteration verifier needs to identify when a * state identical some state from a previous iteration is reached. * Check below forces creation of checkpoint before callback calling * instruction to allow search for such identical states. */ if (bpf_is_sync_callback_calling_insn(insn)) { mark_calls_callback(env, t); mark_force_checkpoint(env, t); mark_prune_point(env, t); mark_jmp_point(env, t); } if (bpf_helper_call(insn)) { const struct bpf_func_proto *fp; ret = bpf_get_helper_proto(env, insn->imm, &fp); /* If called in a non-sleepable context program will be * rejected anyway, so we should end up with precise * sleepable marks on subprogs, except for dead code * elimination. */ if (ret == 0 && fp->might_sleep) mark_subprog_might_sleep(env, t); if (bpf_helper_changes_pkt_data(insn->imm)) mark_subprog_changes_pkt_data(env, t); if (insn->imm == BPF_FUNC_tail_call) { ret = visit_abnormal_return_insn(env, t); if (ret) return ret; } } else if (insn->src_reg == BPF_PSEUDO_KFUNC_CALL) { struct bpf_kfunc_call_arg_meta meta; ret = bpf_fetch_kfunc_arg_meta(env, insn->imm, insn->off, &meta); if (ret == 0 && bpf_is_iter_next_kfunc(&meta)) { mark_prune_point(env, t); /* Checking and saving state checkpoints at iter_next() call * is crucial for fast convergence of open-coded iterator loop