// SPDX-License-Identifier: GPL-2.0-only/* Copyright (c) 2011-2014 PLUMgrid, http://plumgrid.com * Copyright (c) 2016 Facebook * Copyright (c) 2018 Covalent IO, Inc. http://covalent.io */#include <uapi/linux/btf.h>#include <linux/bpf-cgroup.h>#include <linux/kernel.h>#include <linux/types.h>#include <linux/slab.h>#include <linux/bpf.h>#include <linux/btf.h>#include <linux/bpf_verifier.h>#include <linux/filter.h>#include <net/netlink.h>#include <linux/file.h>#include <linux/vmalloc.h>#include <linux/stringify.h>#include <linux/bsearch.h>#include <linux/sort.h>#include <linux/perf_event.h>#include <linux/ctype.h>#include <linux/error-injection.h>#include <linux/bpf_lsm.h>#include <linux/btf_ids.h>#include <linux/poison.h>#include <linux/module.h>#include <linux/cpumask.h>#include <linux/cnum.h>#include <linux/bpf_mem_alloc.h>#include <net/xdp.h>#include <linux/trace_events.h>#include <linux/kallsyms.h> #include "disasm.h" static const struct bpf_verifier_ops * const bpf_verifier_ops[] = {#define BPF_PROG_TYPE(_id, _name, prog_ctx_type, kern_ctx_type) \ [_id] = & _name ## _verifier_ops,#define BPF_MAP_TYPE(_id, _ops)#define BPF_LINK_TYPE(_id, _name)#include <linux/bpf_types.h>#undef BPF_PROG_TYPE#undef BPF_MAP_TYPE#undef BPF_LINK_TYPE}; enum bpf_features { BPF_FEAT_RDONLY_CAST_TO_VOID = 0, BPF_FEAT_STREAMS = 1, __MAX_BPF_FEAT,}; struct bpf_mem_alloc bpf_global_percpu_ma;static bool bpf_global_percpu_ma_set; /* bpf_check() is a static code analyzer that walks eBPF program * instruction by instruction and updates register/stack state. * All paths of conditional branches are analyzed until 'bpf_exit' insn. * * The first pass is depth-first-search to check that the program is a DAG. * It rejects the following programs: * - larger than BPF_MAXINSNS insns * - if loop is present (detected via back-edge) * - unreachable insns exist (shouldn't be a forest. program = one function) * - out of bounds or malformed jumps * The second pass is all possible path descent from the 1st insn. * Since it's analyzing all paths through the program, the length of the * analysis is limited to 64k insn, which may be hit even if total number of * insn is less then 4K, but there are too many branches that change stack/regs. * Number of 'branches to be analyzed' is limited to 1k * * On entry to each instruction, each register has a type, and the instruction * changes the types of the registers depending on instruction semantics. * If instruction is BPF_MOV64_REG(BPF_REG_1, BPF_REG_5), then type of R5 is * copied to R1. * * All registers are 64-bit. * R0 - return register * R1-R5 argument passing registers * R6-R9 callee saved registers * R10 - frame pointer read-only * * At the start of BPF program the register R1 contains a pointer to bpf_context * and has type PTR_TO_CTX. * * Verifier tracks arithmetic operations on pointers in case: * BPF_MOV64_REG(BPF_REG_1, BPF_REG_10), * BPF_ALU64_IMM(BPF_ADD, BPF_REG_1, -20), * 1st insn copies R10 (which has FRAME_PTR) type into R1 * and 2nd arithmetic instruction is pattern matched to recognize * that it wants to construct a pointer to some element within stack. * So after 2nd insn, the register R1 has type PTR_TO_STACK * (and -20 constant is saved for further stack bounds checking). * Meaning that this reg is a pointer to stack plus known immediate constant. * * Most of the time the registers have SCALAR_VALUE type, which * means the register has some value, but it's not a valid pointer. * (like pointer plus pointer becomes SCALAR_VALUE type) * * When verifier sees load or store instructions the type of base register * can be: PTR_TO_MAP_VALUE, PTR_TO_CTX, PTR_TO_STACK, PTR_TO_SOCKET. These are * four pointer types recognized by check_mem_access() function. * * PTR_TO_MAP_VALUE means that this register is pointing to 'map element value' * and the range of [ptr, ptr + map's value_size) is accessible. * * registers used to pass values to function calls are checked against * function argument constraints. * * ARG_PTR_TO_MAP_KEY is one of such argument constraints. * It means that the register type passed to this function must be * PTR_TO_STACK and it will be used inside the function as * 'pointer to map element key' * * For example the argument constraints for bpf_map_lookup_elem(): * .ret_type = RET_PTR_TO_MAP_VALUE_OR_NULL, * .arg1_type = ARG_CONST_MAP_PTR, * .arg2_type = ARG_PTR_TO_MAP_KEY, * * ret_type says that this function returns 'pointer to map elem value or null' * function expects 1st argument to be a const pointer to 'struct bpf_map' and * 2nd argument should be a pointer to stack, which will be used inside * the helper function as a pointer to map element key. * * On the kernel side the helper function looks like: * u64 bpf_map_lookup_elem(u64 r1, u64 r2, u64 r3, u64 r4, u64 r5) * { * struct bpf_map *map = (struct bpf_map *) (unsigned long) r1; * void *key = (void *) (unsigned long) r2; * void *value; * * here kernel can access 'key' and 'map' pointers safely, knowing that * [key, key + map->key_size) bytes are valid and were initialized on * the stack of eBPF program. * } * * Corresponding eBPF program may look like: * BPF_MOV64_REG(BPF_REG_2, BPF_REG_10), // after this insn R2 type is FRAME_PTR * BPF_ALU64_IMM(BPF_ADD, BPF_REG_2, -4), // after this insn R2 type is PTR_TO_STACK * BPF_LD_MAP_FD(BPF_REG_1, map_fd), // after this insn R1 type is CONST_PTR_TO_MAP * BPF_RAW_INSN(BPF_JMP | BPF_CALL, 0, 0, 0, BPF_FUNC_map_lookup_elem), * here verifier looks at prototype of map_lookup_elem() and sees: * .arg1_type == ARG_CONST_MAP_PTR and R1->type == CONST_PTR_TO_MAP, which is ok, * Now verifier knows that this map has key of R1->map_ptr->key_size bytes * * Then .arg2_type == ARG_PTR_TO_MAP_KEY and R2->type == PTR_TO_STACK, ok so far, * Now verifier checks that [R2, R2 + map's key_size) are within stack limits * and were initialized prior to this call. * If it's ok, then verifier allows this BPF_CALL insn and looks at * .ret_type which is RET_PTR_TO_MAP_VALUE_OR_NULL, so it sets * R0->type = PTR_TO_MAP_VALUE_OR_NULL which means bpf_map_lookup_elem() function * returns either pointer to map value or NULL. * * When type PTR_TO_MAP_VALUE_OR_NULL passes through 'if (reg != 0) goto +off' * insn, the register holding that pointer in the true branch changes state to * PTR_TO_MAP_VALUE and the same register changes state to CONST_IMM in the false * branch. See check_cond_jmp_op(). * * After the call R0 is set to return type of the function and registers R1-R5 * are set to NOT_INIT to indicate that they are no longer readable. * * The following reference types represent a potential reference to a kernel * resource which, after first being allocated, must be checked and freed by * the BPF program: * - PTR_TO_SOCKET_OR_NULL, PTR_TO_SOCKET * * When the verifier sees a helper call return a reference type, it allocates a * pointer id for the reference and stores it in the current function state. * Similar to the way that PTR_TO_MAP_VALUE_OR_NULL is converted into * PTR_TO_MAP_VALUE, PTR_TO_SOCKET_OR_NULL becomes PTR_TO_SOCKET when the type * passes through a NULL-check conditional. For the branch wherein the state is * changed to CONST_IMM, the verifier releases the reference. * * For each helper function that allocates a reference, such as * bpf_sk_lookup_tcp(), there is a corresponding release function, such as * bpf_sk_release(). When a reference type passes into the release function, * the verifier also releases the reference. If any unchecked or unreleased * reference remains at the end of the program, the verifier rejects it. */ /* verifier_state + insn_idx are pushed to stack when branch is encountered */struct bpf_verifier_stack_elem { /* verifier state is 'st' * before processing instruction 'insn_idx' * and after processing instruction 'prev_insn_idx' */ struct bpf_verifier_state st; int insn_idx; int prev_insn_idx; struct bpf_verifier_stack_elem *next; /* length of verifier log at the time this state was pushed on stack */ u32 log_pos;}; #define BPF_COMPLEXITY_LIMIT_JMP_SEQ 8192#define BPF_COMPLEXITY_LIMIT_STATES 64 #define BPF_GLOBAL_PERCPU_MA_MAX_SIZE 512 #define BPF_PRIV_STACK_MIN_SIZE 64 static int acquire_reference(struct bpf_verifier_env *env, int insn_idx, int parent_id);static int release_reference_nomark(struct bpf_verifier_state *state, int id);static int release_reference(struct bpf_verifier_env *env, int id);static void invalidate_non_owning_refs(struct bpf_verifier_env *env);static bool in_rbtree_lock_required_cb(struct bpf_verifier_env *env);static bool is_tracing_prog_type(enum bpf_prog_type type);static int ref_set_non_owning(struct bpf_verifier_env *env, struct bpf_reg_state *reg);static bool is_trusted_reg(struct bpf_verifier_env *env, const struct bpf_reg_state *reg);static inline bool in_sleepable_context(struct bpf_verifier_env *env);static const char *non_sleepable_context_description(struct bpf_verifier_env *env);static void scalar32_min_max_add(struct bpf_reg_state *dst_reg, struct bpf_reg_state *src_reg);static void scalar_min_max_add(struct bpf_reg_state *dst_reg, struct bpf_reg_state *src_reg); static void bpf_map_ptr_store(struct bpf_insn_aux_data *aux, struct bpf_map *map, bool unpriv, bool poison){ unpriv |= bpf_map_ptr_unpriv(aux); aux->map_ptr_state.unpriv = unpriv; aux->map_ptr_state.poison = poison; aux->map_ptr_state.map_ptr = map;} static void bpf_map_key_store(struct bpf_insn_aux_data *aux, u64 state){ bool poisoned = bpf_map_key_poisoned(aux); aux->map_key_state = state | BPF_MAP_KEY_SEEN | (poisoned ? BPF_MAP_KEY_POISON : 0ULL);} static void update_ref_obj(struct ref_obj_desc *ref_obj, struct bpf_reg_state *reg){ ref_obj->id = reg->id; ref_obj->parent_id = reg->parent_id; ref_obj->cnt++;} static int validate_ref_obj(struct bpf_verifier_env *env, struct ref_obj_desc *ref_obj){ if (ref_obj->cnt > 1) { verifier_bug(env, "function expects only one referenced object but got %d\n", ref_obj->cnt); return -EFAULT; } return 0;} struct bpf_call_arg_meta { struct bpf_map_desc map; struct bpf_dynptr_desc dynptr; struct ref_obj_desc ref_obj; bool raw_mode; bool pkt_access; u8 release_regno; int regno; int access_size; int mem_size; u64 msize_max_value; int func_id; struct btf *btf; u32 btf_id; struct btf *ret_btf; u32 ret_btf_id; u32 subprogno; struct btf_field *kptr_field; s64 const_map_key;}; struct bpf_kfunc_meta { struct btf *btf; const struct btf_type *proto; const char *name; const u32 *flags; s32 id;}; struct btf *btf_vmlinux; typedef struct argno { int argno;} argno_t; static argno_t argno_from_reg(u32 regno){ return (argno_t){ .argno = regno };} static argno_t argno_from_arg(u32 arg){ return (argno_t){ .argno = -arg };} static int reg_from_argno(argno_t a){ if (a.argno >= 0) return a.argno; if (a.argno >= -MAX_BPF_FUNC_REG_ARGS) return -a.argno; return -1;} static int arg_from_argno(argno_t a){ if (a.argno < 0) return -a.argno; return -1;} static int arg_idx_from_argno(argno_t a){ return arg_from_argno(a) - 1;} static const char *btf_type_name(const struct btf *btf, u32 id){ return btf_name_by_offset(btf, btf_type_by_id(btf, id)->name_off);} static DEFINE_MUTEX(bpf_verifier_lock);static DEFINE_MUTEX(bpf_percpu_ma_lock); __printf(2, 3) static void verbose(void *private_data, const char *fmt, ...){ struct bpf_verifier_env *env = private_data; va_list args; if (!bpf_verifier_log_needed(&env->log)) return; va_start(args, fmt); bpf_verifier_vlog(&env->log, fmt, args); va_end(args);} static void verbose_invalid_scalar(struct bpf_verifier_env *env, struct bpf_reg_state *reg, struct bpf_retval_range range, const char *ctx, const char *reg_name){ bool unknown = true; verbose(env, "%s the register %s has", ctx, reg_name); if (reg_smin(reg) > S64_MIN) { verbose(env, " smin=%lld", reg_smin(reg)); unknown = false; } if (reg_smax(reg) < S64_MAX) { verbose(env, " smax=%lld", reg_smax(reg)); unknown = false; } if (unknown) verbose(env, " unknown scalar value"); verbose(env, " should have been in [%d, %d]\n", range.minval, range.maxval);} static bool reg_not_null(struct bpf_verifier_env *env, const struct bpf_reg_state *reg){ enum bpf_reg_type type; type = reg->type; if (type_may_be_null(type)) return false; type = base_type(type); return type == PTR_TO_SOCKET || type == PTR_TO_TCP_SOCK || type == PTR_TO_MAP_VALUE || type == PTR_TO_MAP_KEY || type == PTR_TO_SOCK_COMMON || (type == PTR_TO_BTF_ID && is_trusted_reg(env, reg)) || (type == PTR_TO_MEM && !(reg->type & PTR_UNTRUSTED)) || type == CONST_PTR_TO_MAP;} static struct btf_record *reg_btf_record(const struct bpf_reg_state *reg){ struct btf_record *rec = NULL; struct btf_struct_meta *meta; if (reg->type == PTR_TO_MAP_VALUE) { rec = reg->map_ptr->record; } else if (type_is_ptr_alloc_obj(reg->type)) { meta = btf_find_struct_meta(reg->btf, reg->btf_id); if (meta) rec = meta->record; } return rec;} bool bpf_subprog_is_global(const struct bpf_verifier_env *env, int subprog){ struct bpf_func_info_aux *aux = env->prog->aux->func_info_aux; return aux && aux[subprog].linkage == BTF_FUNC_GLOBAL;} static bool subprog_returns_void(struct bpf_verifier_env *env, int subprog){ const struct btf_type *type, *func, *func_proto; const struct btf *btf = env->prog->aux->btf; u32 btf_id; btf_id = env->prog->aux->func_info[subprog].type_id; func = btf_type_by_id(btf, btf_id); if (verifier_bug_if(!func, env, "btf_id %u not found", btf_id)) return false; func_proto = btf_type_by_id(btf, func->type); if (!func_proto) return false; type = btf_type_skip_modifiers(btf, func_proto->type, NULL); if (!type) return false; return btf_type_is_void(type);} static const char *subprog_name(const struct bpf_verifier_env *env, int subprog){ struct bpf_func_info *info; if (!env->prog->aux->func_info) return ""; info = &env->prog->aux->func_info[subprog]; return btf_type_name(env->prog->aux->btf, info->type_id);} void bpf_mark_subprog_exc_cb(struct bpf_verifier_env *env, int subprog){ struct bpf_subprog_info *info = subprog_info(env, subprog); info->is_cb = true; info->is_async_cb = true; info->is_exception_cb = true;} static bool subprog_is_exc_cb(struct bpf_verifier_env *env, int subprog){ return subprog_info(env, subprog)->is_exception_cb;} static bool reg_may_point_to_spin_lock(const struct bpf_reg_state *reg){ return btf_record_has_field(reg_btf_record(reg), BPF_SPIN_LOCK | BPF_RES_SPIN_LOCK);} static bool type_is_rdonly_mem(u32 type){ return type & MEM_RDONLY;} static bool is_acquire_function(enum bpf_func_id func_id, const struct bpf_map *map){ enum bpf_map_type map_type = map ? map->map_type : BPF_MAP_TYPE_UNSPEC; if (func_id == BPF_FUNC_sk_lookup_tcp || func_id == BPF_FUNC_sk_lookup_udp || func_id == BPF_FUNC_skc_lookup_tcp || func_id == BPF_FUNC_ringbuf_reserve || func_id == BPF_FUNC_kptr_xchg) return true; if (func_id == BPF_FUNC_map_lookup_elem && (map_type == BPF_MAP_TYPE_SOCKMAP || map_type == BPF_MAP_TYPE_SOCKHASH)) return true; return false;} static bool is_ptr_cast_function(enum bpf_func_id func_id){ return func_id == BPF_FUNC_tcp_sock || func_id == BPF_FUNC_sk_fullsock || func_id == BPF_FUNC_skc_to_tcp_sock || func_id == BPF_FUNC_skc_to_tcp6_sock || func_id == BPF_FUNC_skc_to_udp6_sock || func_id == BPF_FUNC_skc_to_mptcp_sock || func_id == BPF_FUNC_skc_to_tcp_timewait_sock || func_id == BPF_FUNC_skc_to_tcp_request_sock;} static bool is_sync_callback_calling_kfunc(u32 btf_id);static bool is_async_callback_calling_kfunc(u32 btf_id);static bool is_callback_calling_kfunc(u32 btf_id); static bool is_bpf_wq_set_callback_kfunc(u32 btf_id);static bool is_task_work_add_kfunc(u32 func_id); static bool is_sync_callback_calling_function(enum bpf_func_id func_id){Lines 1–500 of 20066. Load more
// SPDX-License-Identifier: GPL-2.0-only /* Copyright (c) 2011-2014 PLUMgrid, http://plumgrid.com * Copyright (c) 2016 Facebook * Copyright (c) 2018 Covalent IO, Inc. http://covalent.io */ #include <uapi/linux/btf.h> #include <linux/bpf-cgroup.h> #include <linux/kernel.h> #include <linux/types.h> #include <linux/slab.h> #include <linux/bpf.h> #include <linux/btf.h> #include <linux/bpf_verifier.h> #include <linux/filter.h> #include <net/netlink.h> #include <linux/file.h> #include <linux/vmalloc.h> #include <linux/stringify.h> #include <linux/bsearch.h> #include <linux/sort.h> #include <linux/perf_event.h> #include <linux/ctype.h> #include <linux/error-injection.h> #include <linux/bpf_lsm.h> #include <linux/btf_ids.h> #include <linux/poison.h> #include <linux/module.h> #include <linux/cpumask.h> #include <linux/cnum.h> #include <linux/bpf_mem_alloc.h> #include <net/xdp.h> #include <linux/trace_events.h> #include <linux/kallsyms.h> #include "disasm.h" static const struct bpf_verifier_ops * const bpf_verifier_ops[] = { #define BPF_PROG_TYPE(_id, _name, prog_ctx_type, kern_ctx_type) \ [_id] = & _name ## _verifier_ops, #define BPF_MAP_TYPE(_id, _ops) #define BPF_LINK_TYPE(_id, _name) #include <linux/bpf_types.h> #undef BPF_PROG_TYPE #undef BPF_MAP_TYPE #undef BPF_LINK_TYPE }; enum bpf_features { BPF_FEAT_RDONLY_CAST_TO_VOID = 0, BPF_FEAT_STREAMS = 1, __MAX_BPF_FEAT, }; struct bpf_mem_alloc bpf_global_percpu_ma; static bool bpf_global_percpu_ma_set; /* bpf_check() is a static code analyzer that walks eBPF program * instruction by instruction and updates register/stack state. * All paths of conditional branches are analyzed until 'bpf_exit' insn. * * The first pass is depth-first-search to check that the program is a DAG. * It rejects the following programs: * - larger than BPF_MAXINSNS insns * - if loop is present (detected via back-edge) * - unreachable insns exist (shouldn't be a forest. program = one function) * - out of bounds or malformed jumps * The second pass is all possible path descent from the 1st insn. * Since it's analyzing all paths through the program, the length of the * analysis is limited to 64k insn, which may be hit even if total number of * insn is less then 4K, but there are too many branches that change stack/regs. * Number of 'branches to be analyzed' is limited to 1k * * On entry to each instruction, each register has a type, and the instruction * changes the types of the registers depending on instruction semantics. * If instruction is BPF_MOV64_REG(BPF_REG_1, BPF_REG_5), then type of R5 is * copied to R1. * * All registers are 64-bit. * R0 - return register * R1-R5 argument passing registers * R6-R9 callee saved registers * R10 - frame pointer read-only * * At the start of BPF program the register R1 contains a pointer to bpf_context * and has type PTR_TO_CTX. * * Verifier tracks arithmetic operations on pointers in case: * BPF_MOV64_REG(BPF_REG_1, BPF_REG_10), * BPF_ALU64_IMM(BPF_ADD, BPF_REG_1, -20), * 1st insn copies R10 (which has FRAME_PTR) type into R1 * and 2nd arithmetic instruction is pattern matched to recognize * that it wants to construct a pointer to some element within stack. * So after 2nd insn, the register R1 has type PTR_TO_STACK * (and -20 constant is saved for further stack bounds checking). * Meaning that this reg is a pointer to stack plus known immediate constant. * * Most of the time the registers have SCALAR_VALUE type, which * means the register has some value, but it's not a valid pointer. * (like pointer plus pointer becomes SCALAR_VALUE type) * * When verifier sees load or store instructions the type of base register * can be: PTR_TO_MAP_VALUE, PTR_TO_CTX, PTR_TO_STACK, PTR_TO_SOCKET. These are * four pointer types recognized by check_mem_access() function. * * PTR_TO_MAP_VALUE means that this register is pointing to 'map element value' * and the range of [ptr, ptr + map's value_size) is accessible. * * registers used to pass values to function calls are checked against * function argument constraints. * * ARG_PTR_TO_MAP_KEY is one of such argument constraints. * It means that the register type passed to this function must be * PTR_TO_STACK and it will be used inside the function as * 'pointer to map element key' * * For example the argument constraints for bpf_map_lookup_elem(): * .ret_type = RET_PTR_TO_MAP_VALUE_OR_NULL, * .arg1_type = ARG_CONST_MAP_PTR, * .arg2_type = ARG_PTR_TO_MAP_KEY, * * ret_type says that this function returns 'pointer to map elem value or null' * function expects 1st argument to be a const pointer to 'struct bpf_map' and * 2nd argument should be a pointer to stack, which will be used inside * the helper function as a pointer to map element key. * * On the kernel side the helper function looks like: * u64 bpf_map_lookup_elem(u64 r1, u64 r2, u64 r3, u64 r4, u64 r5) * { * struct bpf_map *map = (struct bpf_map *) (unsigned long) r1; * void *key = (void *) (unsigned long) r2; * void *value; * * here kernel can access 'key' and 'map' pointers safely, knowing that * [key, key + map->key_size) bytes are valid and were initialized on * the stack of eBPF program. * } * * Corresponding eBPF program may look like: * BPF_MOV64_REG(BPF_REG_2, BPF_REG_10), // after this insn R2 type is FRAME_PTR * BPF_ALU64_IMM(BPF_ADD, BPF_REG_2, -4), // after this insn R2 type is PTR_TO_STACK * BPF_LD_MAP_FD(BPF_REG_1, map_fd), // after this insn R1 type is CONST_PTR_TO_MAP * BPF_RAW_INSN(BPF_JMP | BPF_CALL, 0, 0, 0, BPF_FUNC_map_lookup_elem), * here verifier looks at prototype of map_lookup_elem() and sees: * .arg1_type == ARG_CONST_MAP_PTR and R1->type == CONST_PTR_TO_MAP, which is ok, * Now verifier knows that this map has key of R1->map_ptr->key_size bytes * * Then .arg2_type == ARG_PTR_TO_MAP_KEY and R2->type == PTR_TO_STACK, ok so far, * Now verifier checks that [R2, R2 + map's key_size) are within stack limits * and were initialized prior to this call. * If it's ok, then verifier allows this BPF_CALL insn and looks at * .ret_type which is RET_PTR_TO_MAP_VALUE_OR_NULL, so it sets * R0->type = PTR_TO_MAP_VALUE_OR_NULL which means bpf_map_lookup_elem() function * returns either pointer to map value or NULL. * * When type PTR_TO_MAP_VALUE_OR_NULL passes through 'if (reg != 0) goto +off' * insn, the register holding that pointer in the true branch changes state to * PTR_TO_MAP_VALUE and the same register changes state to CONST_IMM in the false * branch. See check_cond_jmp_op(). * * After the call R0 is set to return type of the function and registers R1-R5 * are set to NOT_INIT to indicate that they are no longer readable. * * The following reference types represent a potential reference to a kernel * resource which, after first being allocated, must be checked and freed by * the BPF program: * - PTR_TO_SOCKET_OR_NULL, PTR_TO_SOCKET * * When the verifier sees a helper call return a reference type, it allocates a * pointer id for the reference and stores it in the current function state. * Similar to the way that PTR_TO_MAP_VALUE_OR_NULL is converted into * PTR_TO_MAP_VALUE, PTR_TO_SOCKET_OR_NULL becomes PTR_TO_SOCKET when the type * passes through a NULL-check conditional. For the branch wherein the state is * changed to CONST_IMM, the verifier releases the reference. * * For each helper function that allocates a reference, such as * bpf_sk_lookup_tcp(), there is a corresponding release function, such as * bpf_sk_release(). When a reference type passes into the release function, * the verifier also releases the reference. If any unchecked or unreleased * reference remains at the end of the program, the verifier rejects it. */ /* verifier_state + insn_idx are pushed to stack when branch is encountered */ struct bpf_verifier_stack_elem { /* verifier state is 'st' * before processing instruction 'insn_idx' * and after processing instruction 'prev_insn_idx' */ struct bpf_verifier_state st; int insn_idx; int prev_insn_idx; struct bpf_verifier_stack_elem *next; /* length of verifier log at the time this state was pushed on stack */ u32 log_pos; }; #define BPF_COMPLEXITY_LIMIT_JMP_SEQ 8192 #define BPF_COMPLEXITY_LIMIT_STATES 64 #define BPF_GLOBAL_PERCPU_MA_MAX_SIZE 512 #define BPF_PRIV_STACK_MIN_SIZE 64 static int acquire_reference(struct bpf_verifier_env *env, int insn_idx, int parent_id); static int release_reference_nomark(struct bpf_verifier_state *state, int id); static int release_reference(struct bpf_verifier_env *env, int id); static void invalidate_non_owning_refs(struct bpf_verifier_env *env); static bool in_rbtree_lock_required_cb(struct bpf_verifier_env *env); static bool is_tracing_prog_type(enum bpf_prog_type type); static int ref_set_non_owning(struct bpf_verifier_env *env, struct bpf_reg_state *reg); static bool is_trusted_reg(struct bpf_verifier_env *env, const struct bpf_reg_state *reg); static inline bool in_sleepable_context(struct bpf_verifier_env *env); static const char *non_sleepable_context_description(struct bpf_verifier_env *env); static void scalar32_min_max_add(struct bpf_reg_state *dst_reg, struct bpf_reg_state *src_reg); static void scalar_min_max_add(struct bpf_reg_state *dst_reg, struct bpf_reg_state *src_reg); static void bpf_map_ptr_store(struct bpf_insn_aux_data *aux, struct bpf_map *map, bool unpriv, bool poison) { unpriv |= bpf_map_ptr_unpriv(aux); aux->map_ptr_state.unpriv = unpriv; aux->map_ptr_state.poison = poison; aux->map_ptr_state.map_ptr = map; } static void bpf_map_key_store(struct bpf_insn_aux_data *aux, u64 state) { bool poisoned = bpf_map_key_poisoned(aux); aux->map_key_state = state | BPF_MAP_KEY_SEEN | (poisoned ? BPF_MAP_KEY_POISON : 0ULL); } static void update_ref_obj(struct ref_obj_desc *ref_obj, struct bpf_reg_state *reg) { ref_obj->id = reg->id; ref_obj->parent_id = reg->parent_id; ref_obj->cnt++; } static int validate_ref_obj(struct bpf_verifier_env *env, struct ref_obj_desc *ref_obj) { if (ref_obj->cnt > 1) { verifier_bug(env, "function expects only one referenced object but got %d\n", ref_obj->cnt); return -EFAULT; } return 0; } struct bpf_call_arg_meta { struct bpf_map_desc map; struct bpf_dynptr_desc dynptr; struct ref_obj_desc ref_obj; bool raw_mode; bool pkt_access; u8 release_regno; int regno; int access_size; int mem_size; u64 msize_max_value; int func_id; struct btf *btf; u32 btf_id; struct btf *ret_btf; u32 ret_btf_id; u32 subprogno; struct btf_field *kptr_field; s64 const_map_key; }; struct bpf_kfunc_meta { struct btf *btf; const struct btf_type *proto; const char *name; const u32 *flags; s32 id; }; struct btf *btf_vmlinux; typedef struct argno { int argno; } argno_t; static argno_t argno_from_reg(u32 regno) { return (argno_t){ .argno = regno }; } static argno_t argno_from_arg(u32 arg) { return (argno_t){ .argno = -arg }; } static int reg_from_argno(argno_t a) { if (a.argno >= 0) return a.argno; if (a.argno >= -MAX_BPF_FUNC_REG_ARGS) return -a.argno; return -1; } static int arg_from_argno(argno_t a) { if (a.argno < 0) return -a.argno; return -1; } static int arg_idx_from_argno(argno_t a) { return arg_from_argno(a) - 1; } static const char *btf_type_name(const struct btf *btf, u32 id) { return btf_name_by_offset(btf, btf_type_by_id(btf, id)->name_off); } static DEFINE_MUTEX(bpf_verifier_lock); static DEFINE_MUTEX(bpf_percpu_ma_lock); __printf(2, 3) static void verbose(void *private_data, const char *fmt, ...) { struct bpf_verifier_env *env = private_data; va_list args; if (!bpf_verifier_log_needed(&env->log)) return; va_start(args, fmt); bpf_verifier_vlog(&env->log, fmt, args); va_end(args); } static void verbose_invalid_scalar(struct bpf_verifier_env *env, struct bpf_reg_state *reg, struct bpf_retval_range range, const char *ctx, const char *reg_name) { bool unknown = true; verbose(env, "%s the register %s has", ctx, reg_name); if (reg_smin(reg) > S64_MIN) { verbose(env, " smin=%lld", reg_smin(reg)); unknown = false; } if (reg_smax(reg) < S64_MAX) { verbose(env, " smax=%lld", reg_smax(reg)); unknown = false; } if (unknown) verbose(env, " unknown scalar value"); verbose(env, " should have been in [%d, %d]\n", range.minval, range.maxval); } static bool reg_not_null(struct bpf_verifier_env *env, const struct bpf_reg_state *reg) { enum bpf_reg_type type; type = reg->type; if (type_may_be_null(type)) return false; type = base_type(type); return type == PTR_TO_SOCKET || type == PTR_TO_TCP_SOCK || type == PTR_TO_MAP_VALUE || type == PTR_TO_MAP_KEY || type == PTR_TO_SOCK_COMMON || (type == PTR_TO_BTF_ID && is_trusted_reg(env, reg)) || (type == PTR_TO_MEM && !(reg->type & PTR_UNTRUSTED)) || type == CONST_PTR_TO_MAP; } static struct btf_record *reg_btf_record(const struct bpf_reg_state *reg) { struct btf_record *rec = NULL; struct btf_struct_meta *meta; if (reg->type == PTR_TO_MAP_VALUE) { rec = reg->map_ptr->record; } else if (type_is_ptr_alloc_obj(reg->type)) { meta = btf_find_struct_meta(reg->btf, reg->btf_id); if (meta) rec = meta->record; } return rec; } bool bpf_subprog_is_global(const struct bpf_verifier_env *env, int subprog) { struct bpf_func_info_aux *aux = env->prog->aux->func_info_aux; return aux && aux[subprog].linkage == BTF_FUNC_GLOBAL; } static bool subprog_returns_void(struct bpf_verifier_env *env, int subprog) { const struct btf_type *type, *func, *func_proto; const struct btf *btf = env->prog->aux->btf; u32 btf_id; btf_id = env->prog->aux->func_info[subprog].type_id; func = btf_type_by_id(btf, btf_id); if (verifier_bug_if(!func, env, "btf_id %u not found", btf_id)) return false; func_proto = btf_type_by_id(btf, func->type); if (!func_proto) return false; type = btf_type_skip_modifiers(btf, func_proto->type, NULL); if (!type) return false; return btf_type_is_void(type); } static const char *subprog_name(const struct bpf_verifier_env *env, int subprog) { struct bpf_func_info *info; if (!env->prog->aux->func_info) return ""; info = &env->prog->aux->func_info[subprog]; return btf_type_name(env->prog->aux->btf, info->type_id); } void bpf_mark_subprog_exc_cb(struct bpf_verifier_env *env, int subprog) { struct bpf_subprog_info *info = subprog_info(env, subprog); info->is_cb = true; info->is_async_cb = true; info->is_exception_cb = true; } static bool subprog_is_exc_cb(struct bpf_verifier_env *env, int subprog) { return subprog_info(env, subprog)->is_exception_cb; } static bool reg_may_point_to_spin_lock(const struct bpf_reg_state *reg) { return btf_record_has_field(reg_btf_record(reg), BPF_SPIN_LOCK | BPF_RES_SPIN_LOCK); } static bool type_is_rdonly_mem(u32 type) { return type & MEM_RDONLY; } static bool is_acquire_function(enum bpf_func_id func_id, const struct bpf_map *map) { enum bpf_map_type map_type = map ? map->map_type : BPF_MAP_TYPE_UNSPEC; if (func_id == BPF_FUNC_sk_lookup_tcp || func_id == BPF_FUNC_sk_lookup_udp || func_id == BPF_FUNC_skc_lookup_tcp || func_id == BPF_FUNC_ringbuf_reserve || func_id == BPF_FUNC_kptr_xchg) return true; if (func_id == BPF_FUNC_map_lookup_elem && (map_type == BPF_MAP_TYPE_SOCKMAP || map_type == BPF_MAP_TYPE_SOCKHASH)) return true; return false; } static bool is_ptr_cast_function(enum bpf_func_id func_id) { return func_id == BPF_FUNC_tcp_sock || func_id == BPF_FUNC_sk_fullsock || func_id == BPF_FUNC_skc_to_tcp_sock || func_id == BPF_FUNC_skc_to_tcp6_sock || func_id == BPF_FUNC_skc_to_udp6_sock || func_id == BPF_FUNC_skc_to_mptcp_sock || func_id == BPF_FUNC_skc_to_tcp_timewait_sock || func_id == BPF_FUNC_skc_to_tcp_request_sock; } static bool is_sync_callback_calling_kfunc(u32 btf_id); static bool is_async_callback_calling_kfunc(u32 btf_id); static bool is_callback_calling_kfunc(u32 btf_id); static bool is_bpf_wq_set_callback_kfunc(u32 btf_id); static bool is_task_work_add_kfunc(u32 func_id); static bool is_sync_callback_calling_function(enum bpf_func_id func_id) {