242 static void print_verifier_state(struct verifier_env *env)  in print_verifier_state()  argument
248 		t = env->cur_state.regs[i].type;  in print_verifier_state()
253 			verbose("%d", env->cur_state.regs[i].imm);  in print_verifier_state()
257 				env->cur_state.regs[i].map_ptr->key_size,  in print_verifier_state()
258 				env->cur_state.regs[i].map_ptr->value_size);  in print_verifier_state()
261 		if (env->cur_state.stack_slot_type[i] == STACK_SPILL)  in print_verifier_state()
263 				reg_type_str[env->cur_state.spilled_regs[i / BPF_REG_SIZE].type]);  in print_verifier_state()
413 static int pop_stack(struct verifier_env *env, int *prev_insn_idx)  in pop_stack()  argument
418 	if (env->head == NULL)  in pop_stack()
421 	memcpy(&env->cur_state, &env->head->st, sizeof(env->cur_state));  in pop_stack()
422 	insn_idx = env->head->insn_idx;  in pop_stack()
424 		*prev_insn_idx = env->head->prev_insn_idx;  in pop_stack()
425 	elem = env->head->next;  in pop_stack()
426 	kfree(env->head);  in pop_stack()
427 	env->head = elem;  in pop_stack()
428 	env->stack_size--;  in pop_stack()
432 static struct verifier_state *push_stack(struct verifier_env *env, int insn_idx,  in push_stack()  argument
441 	memcpy(&elem->st, &env->cur_state, sizeof(env->cur_state));  in push_stack()
444 	elem->next = env->head;  in push_stack()
445 	env->head = elem;  in push_stack()
446 	env->stack_size++;  in push_stack()
447 	if (env->stack_size > 1024) {  in push_stack()
454 	while (pop_stack(env, NULL) >= 0);  in push_stack()
627 static int check_map_access(struct verifier_env *env, u32 regno, int off,  in check_map_access()  argument
630 	struct bpf_map *map = env->cur_state.regs[regno].map_ptr;  in check_map_access()
641 static int check_ctx_access(struct verifier_env *env, int off, int size,  in check_ctx_access()  argument
644 	if (env->prog->aux->ops->is_valid_access &&  in check_ctx_access()
645 	    env->prog->aux->ops->is_valid_access(off, size, t))  in check_ctx_access()
652 static bool is_pointer_value(struct verifier_env *env, int regno)  in is_pointer_value()  argument
654 	if (env->allow_ptr_leaks)  in is_pointer_value()
657 	switch (env->cur_state.regs[regno].type) {  in is_pointer_value()
672 static int check_mem_access(struct verifier_env *env, u32 regno, int off,  in check_mem_access()  argument
676 	struct verifier_state *state = &env->cur_state;  in check_mem_access()
693 		    is_pointer_value(env, value_regno)) {  in check_mem_access()
697 		err = check_map_access(env, regno, off, size);  in check_mem_access()
703 		    is_pointer_value(env, value_regno)) {  in check_mem_access()
707 		err = check_ctx_access(env, off, size, t);  in check_mem_access()
718 			if (!env->allow_ptr_leaks &&  in check_mem_access()
736 static int check_xadd(struct verifier_env *env, struct bpf_insn *insn)  in check_xadd()  argument
738 	struct reg_state *regs = env->cur_state.regs;  in check_xadd()
758 	err = check_mem_access(env, insn->dst_reg, insn->off,  in check_xadd()
764 	return check_mem_access(env, insn->dst_reg, insn->off,  in check_xadd()
772 static int check_stack_boundary(struct verifier_env *env,  in check_stack_boundary()  argument
775 	struct verifier_state *state = &env->cur_state;  in check_stack_boundary()
800 static int check_func_arg(struct verifier_env *env, u32 regno,  in check_func_arg()  argument
803 	struct reg_state *reg = env->cur_state.regs + regno;  in check_func_arg()
816 		if (is_pointer_value(env, regno)) {  in check_func_arg()
861 		err = check_stack_boundary(env, regno, (*mapp)->key_size);  in check_func_arg()
872 		err = check_stack_boundary(env, regno, (*mapp)->value_size);  in check_func_arg()
884 		err = check_stack_boundary(env, regno - 1, reg->imm);  in check_func_arg()
932 static int check_call(struct verifier_env *env, int func_id)  in check_call()  argument
934 	struct verifier_state *state = &env->cur_state;  in check_call()
947 	if (env->prog->aux->ops->get_func_proto)  in check_call()
948 		fn = env->prog->aux->ops->get_func_proto(func_id);  in check_call()
956 	if (!env->prog->gpl_compatible && fn->gpl_only) {  in check_call()
962 	err = check_func_arg(env, BPF_REG_1, fn->arg1_type, &map);  in check_call()
965 	err = check_func_arg(env, BPF_REG_2, fn->arg2_type, &map);  in check_call()
968 	err = check_func_arg(env, BPF_REG_3, fn->arg3_type, &map);  in check_call()
971 	err = check_func_arg(env, BPF_REG_4, fn->arg4_type, &map);  in check_call()
974 	err = check_func_arg(env, BPF_REG_5, fn->arg5_type, &map);  in check_call()
1015 static int check_alu_op(struct verifier_env *env, struct bpf_insn *insn)  in check_alu_op()  argument
1017 	struct reg_state *regs = env->cur_state.regs;  in check_alu_op()
1042 		if (is_pointer_value(env, insn->dst_reg)) {  in check_alu_op()
1084 				if (is_pointer_value(env, insn->src_reg)) {  in check_alu_op()
1150 		} else if (is_pointer_value(env, insn->dst_reg)) {  in check_alu_op()
1155 			   is_pointer_value(env, insn->src_reg)) {  in check_alu_op()
1175 static int check_cond_jmp_op(struct verifier_env *env,  in check_cond_jmp_op()  argument
1178 	struct reg_state *regs = env->cur_state.regs;  in check_cond_jmp_op()
1199 		if (is_pointer_value(env, insn->src_reg)) {  in check_cond_jmp_op()
1236 	other_branch = push_stack(env, *insn_idx + insn->off + 1, *insn_idx);  in check_cond_jmp_op()
1258 	} else if (is_pointer_value(env, insn->dst_reg)) {  in check_cond_jmp_op()
1279 		print_verifier_state(env);  in check_cond_jmp_op()
1292 static int check_ld_imm(struct verifier_env *env, struct bpf_insn *insn)  in check_ld_imm()  argument
1294 	struct reg_state *regs = env->cur_state.regs;  in check_ld_imm()
1349 static int check_ld_abs(struct verifier_env *env, struct bpf_insn *insn)  in check_ld_abs()  argument
1351 	struct reg_state *regs = env->cur_state.regs;  in check_ld_abs()
1356 	if (!may_access_skb(env->prog->type)) {  in check_ld_abs()
1450 static int push_insn(int t, int w, int e, struct verifier_env *env)  in push_insn()  argument
1458 	if (w < 0 || w >= env->prog->len) {  in push_insn()
1465 		env->explored_states[w] = STATE_LIST_MARK;  in push_insn()
1471 		if (cur_stack >= env->prog->len)  in push_insn()
1491 static int check_cfg(struct verifier_env *env)  in check_cfg()  argument
1493 	struct bpf_insn *insns = env->prog->insnsi;  in check_cfg()
1494 	int insn_cnt = env->prog->len;  in check_cfg()
1523 			ret = push_insn(t, t + 1, FALLTHROUGH, env);  in check_cfg()
1535 					FALLTHROUGH, env);  in check_cfg()
1544 				env->explored_states[t + 1] = STATE_LIST_MARK;  in check_cfg()
1547 			ret = push_insn(t, t + 1, FALLTHROUGH, env);  in check_cfg()
1553 			ret = push_insn(t, t + insns[t].off + 1, BRANCH, env);  in check_cfg()
1563 		ret = push_insn(t, t + 1, FALLTHROUGH, env);  in check_cfg()
1668 static int is_state_visited(struct verifier_env *env, int insn_idx)  in is_state_visited()  argument
1673 	sl = env->explored_states[insn_idx];  in is_state_visited()
1681 		if (states_equal(&sl->state, &env->cur_state))  in is_state_visited()
1700 	memcpy(&new_sl->state, &env->cur_state, sizeof(env->cur_state));  in is_state_visited()
1701 	new_sl->next = env->explored_states[insn_idx];  in is_state_visited()
1702 	env->explored_states[insn_idx] = new_sl;  in is_state_visited()
1706 static int do_check(struct verifier_env *env)  in do_check()  argument
1708 	struct verifier_state *state = &env->cur_state;  in do_check()
1709 	struct bpf_insn *insns = env->prog->insnsi;  in do_check()
1711 	int insn_cnt = env->prog->len;  in do_check()
1738 		err = is_state_visited(env, insn_idx);  in do_check()
1755 			print_verifier_state(env);  in do_check()
1765 			err = check_alu_op(env, insn);  in do_check()
1788 			err = check_mem_access(env, insn->src_reg, insn->off,  in do_check()
1824 				err = check_xadd(env, insn);  in do_check()
1843 			err = check_mem_access(env, insn->dst_reg, insn->off,  in do_check()
1870 			err = check_mem_access(env, insn->dst_reg, insn->off,  in do_check()
1888 				err = check_call(env, insn->imm);  in do_check()
1923 				if (is_pointer_value(env, BPF_REG_0)) {  in do_check()
1929 				insn_idx = pop_stack(env, &prev_insn_idx);  in do_check()
1937 				err = check_cond_jmp_op(env, insn, &insn_idx);  in do_check()
1945 				err = check_ld_abs(env, insn);  in do_check()
1950 				err = check_ld_imm(env, insn);  in do_check()
1973 static int replace_map_fd_with_map_ptr(struct verifier_env *env)  in replace_map_fd_with_map_ptr()  argument
1975 	struct bpf_insn *insn = env->prog->insnsi;  in replace_map_fd_with_map_ptr()
1976 	int insn_cnt = env->prog->len;  in replace_map_fd_with_map_ptr()
2026 			for (j = 0; j < env->used_map_cnt; j++)  in replace_map_fd_with_map_ptr()
2027 				if (env->used_maps[j] == map) {  in replace_map_fd_with_map_ptr()
2032 			if (env->used_map_cnt >= MAX_USED_MAPS) {  in replace_map_fd_with_map_ptr()
2047 			env->used_maps[env->used_map_cnt++] = map;  in replace_map_fd_with_map_ptr()
2064 static void release_maps(struct verifier_env *env)  in release_maps()  argument
2068 	for (i = 0; i < env->used_map_cnt; i++)  in release_maps()
2069 		bpf_map_put(env->used_maps[i]);  in release_maps()
2073 static void convert_pseudo_ld_imm64(struct verifier_env *env)  in convert_pseudo_ld_imm64()  argument
2075 	struct bpf_insn *insn = env->prog->insnsi;  in convert_pseudo_ld_imm64()
2076 	int insn_cnt = env->prog->len;  in convert_pseudo_ld_imm64()
2107 static int convert_ctx_accesses(struct verifier_env *env)  in convert_ctx_accesses()  argument
2109 	struct bpf_insn *insn = env->prog->insnsi;  in convert_ctx_accesses()
2110 	int insn_cnt = env->prog->len;  in convert_ctx_accesses()
2117 	if (!env->prog->aux->ops->convert_ctx_access)  in convert_ctx_accesses()
2134 		cnt = env->prog->aux->ops->  in convert_ctx_accesses()
2136 					   insn->off, insn_buf, env->prog);  in convert_ctx_accesses()
2149 		new_prog = bpf_prog_realloc(env->prog,  in convert_ctx_accesses()
2167 		env->prog = new_prog;  in convert_ctx_accesses()
2175 static void free_states(struct verifier_env *env)  in free_states()  argument
2180 	if (!env->explored_states)  in free_states()
2183 	for (i = 0; i < env->prog->len; i++) {  in free_states()
2184 		sl = env->explored_states[i];  in free_states()
2194 	kfree(env->explored_states);  in free_states()
2200 	struct verifier_env *env;  in bpf_check()  local
2209 	env = kzalloc(sizeof(struct verifier_env), GFP_KERNEL);  in bpf_check()
2210 	if (!env)  in bpf_check()
2213 	env->prog = *prog;  in bpf_check()
2241 	ret = replace_map_fd_with_map_ptr(env);  in bpf_check()
2245 	env->explored_states = kcalloc(env->prog->len,  in bpf_check()
2249 	if (!env->explored_states)  in bpf_check()
2252 	ret = check_cfg(env);  in bpf_check()
2256 	env->allow_ptr_leaks = capable(CAP_SYS_ADMIN);  in bpf_check()
2258 	ret = do_check(env);  in bpf_check()
2261 	while (pop_stack(env, NULL) >= 0);  in bpf_check()
2262 	free_states(env);  in bpf_check()
2266 		ret = convert_ctx_accesses(env);  in bpf_check()
2281 	if (ret == 0 && env->used_map_cnt) {  in bpf_check()
2283 		env->prog->aux->used_maps = kmalloc_array(env->used_map_cnt,  in bpf_check()
2284 							  sizeof(env->used_maps[0]),  in bpf_check()
2287 		if (!env->prog->aux->used_maps) {  in bpf_check()
2292 		memcpy(env->prog->aux->used_maps, env->used_maps,  in bpf_check()
2293 		       sizeof(env->used_maps[0]) * env->used_map_cnt);  in bpf_check()
2294 		env->prog->aux->used_map_cnt = env->used_map_cnt;  in bpf_check()
2299 		convert_pseudo_ld_imm64(env);  in bpf_check()
2306 	if (!env->prog->aux->used_maps)  in bpf_check()
2310 		release_maps(env);  in bpf_check()
2311 	*prog = env->prog;  in bpf_check()
2312 	kfree(env);  in bpf_check()