8 #define verbose(env, fmt, args...) bpf_verifier_log_write(env, fmt, ##args)  argument
12 static bool is_may_goto_insn_at(struct bpf_verifier_env *env, int insn_idx)  in is_may_goto_insn_at()  argument
14 	return bpf_is_may_goto_insn(&env->prog->insnsi[insn_idx]);  in is_may_goto_insn_at()
17 static bool is_iter_next_insn(struct bpf_verifier_env *env, int insn_idx)  in is_iter_next_insn()  argument
19 	return env->insn_aux_data[insn_idx].is_iter_next;  in is_iter_next_insn()
22 static void update_peak_states(struct bpf_verifier_env *env)  in update_peak_states()  argument
26 	cur_states = env->explored_states_size + env->free_list_size + env->num_backedges;  in update_peak_states()
27 	env->peak_states = max(env->peak_states, cur_states);  in update_peak_states()
41 static bool incomplete_read_marks(struct bpf_verifier_env *env,
48 static void maybe_free_verifier_state(struct bpf_verifier_env *env,  in maybe_free_verifier_state()  argument
53 	    || incomplete_read_marks(env, &sl->state))  in maybe_free_verifier_state()
58 	env->free_list_size--;  in maybe_free_verifier_state()
74 static bool compute_scc_callchain(struct bpf_verifier_env *env,  in compute_scc_callchain()  argument
83 		scc = env->insn_aux_data[insn_idx].scc;  in compute_scc_callchain()
97 static struct bpf_scc_visit *scc_visit_lookup(struct bpf_verifier_env *env,  in scc_visit_lookup()  argument
100 	struct bpf_scc_info *info = env->scc_info[callchain->scc];  in scc_visit_lookup()
116 static struct bpf_scc_visit *scc_visit_alloc(struct bpf_verifier_env *env,  in scc_visit_alloc()  argument
125 	info = env->scc_info[scc];  in scc_visit_alloc()
128 	info = kvrealloc(env->scc_info[scc], new_sz, GFP_KERNEL_ACCOUNT);  in scc_visit_alloc()
131 	env->scc_info[scc] = info;  in scc_visit_alloc()
140 static char *format_callchain(struct bpf_verifier_env *env, struct bpf_scc_callchain *callchain)  in format_callchain()  argument
142 	char *buf = env->tmp_str_buf;  in format_callchain()
153 	return env->tmp_str_buf;  in format_callchain()
160 static int maybe_enter_scc(struct bpf_verifier_env *env, struct bpf_verifier_state *st)  in maybe_enter_scc()  argument
162 	struct bpf_scc_callchain *callchain = &env->callchain_buf;  in maybe_enter_scc()
165 	if (!compute_scc_callchain(env, st, callchain))  in maybe_enter_scc()
167 	visit = scc_visit_lookup(env, callchain);  in maybe_enter_scc()
168 	visit = visit ?: scc_visit_alloc(env, callchain);  in maybe_enter_scc()
173 		if (env->log.level & BPF_LOG_LEVEL2)  in maybe_enter_scc()
174 			verbose(env, "SCC enter %s\n", format_callchain(env, callchain));  in maybe_enter_scc()
179 static int propagate_backedges(struct bpf_verifier_env *env, struct bpf_scc_visit *visit);
185 static int maybe_exit_scc(struct bpf_verifier_env *env, struct bpf_verifier_state *st)  in maybe_exit_scc()  argument
187 	struct bpf_scc_callchain *callchain = &env->callchain_buf;  in maybe_exit_scc()
190 	if (!compute_scc_callchain(env, st, callchain))  in maybe_exit_scc()
192 	visit = scc_visit_lookup(env, callchain);  in maybe_exit_scc()
207 			verifier_bug(env, "scc exit: no visit info for call chain %s",  in maybe_exit_scc()
208 				     format_callchain(env, callchain));  in maybe_exit_scc()
215 	if (env->log.level & BPF_LOG_LEVEL2)  in maybe_exit_scc()
216 		verbose(env, "SCC exit %s\n", format_callchain(env, callchain));  in maybe_exit_scc()
218 	env->num_backedges -= visit->num_backedges;  in maybe_exit_scc()
220 	update_peak_states(env);  in maybe_exit_scc()
221 	return propagate_backedges(env, visit);  in maybe_exit_scc()
227 static int add_scc_backedge(struct bpf_verifier_env *env,  in add_scc_backedge()  argument
231 	struct bpf_scc_callchain *callchain = &env->callchain_buf;  in add_scc_backedge()
234 	if (!compute_scc_callchain(env, st, callchain)) {  in add_scc_backedge()
235 		verifier_bug(env, "add backedge: no SCC in verification path, insn_idx %d",  in add_scc_backedge()
239 	visit = scc_visit_lookup(env, callchain);  in add_scc_backedge()
241 		verifier_bug(env, "add backedge: no visit info for call chain %s",  in add_scc_backedge()
242 			     format_callchain(env, callchain));  in add_scc_backedge()
245 	if (env->log.level & BPF_LOG_LEVEL2)  in add_scc_backedge()
246 		verbose(env, "SCC backedge %s\n", format_callchain(env, callchain));  in add_scc_backedge()
250 	env->num_backedges++;  in add_scc_backedge()
251 	update_peak_states(env);  in add_scc_backedge()
259 static bool incomplete_read_marks(struct bpf_verifier_env *env,  in incomplete_read_marks()  argument
262 	struct bpf_scc_callchain *callchain = &env->callchain_buf;  in incomplete_read_marks()
265 	if (!compute_scc_callchain(env, st, callchain))  in incomplete_read_marks()
267 	visit = scc_visit_lookup(env, callchain);  in incomplete_read_marks()
273 int bpf_update_branch_counts(struct bpf_verifier_env *env, struct bpf_verifier_state *st)  in bpf_update_branch_counts()  argument
285 		verifier_bug_if((int)br < 0, env, "%s:branches_to_explore=%d", __func__, br);  in bpf_update_branch_counts()
288 		err = maybe_exit_scc(env, st);  in bpf_update_branch_counts()
294 			maybe_free_verifier_state(env, sl);  in bpf_update_branch_counts()
398 static void __clean_func_state(struct bpf_verifier_env *env,  in __clean_func_state()  argument
410 			bpf_mark_reg_not_init(env, &st->regs[i]);  in __clean_func_state()
419 		bool lo_live = bpf_stack_slot_alive(env, frame, i * 2);  in __clean_func_state()
420 		bool hi_live = bpf_stack_slot_alive(env, frame, i * 2 + 1);  in __clean_func_state()
463 				bpf_mark_reg_not_init(env, spill);  in __clean_func_state()
471 static int clean_verifier_state(struct bpf_verifier_env *env,  in clean_verifier_state()  argument
476 	err = bpf_live_stack_query_init(env, st);  in clean_verifier_state()
481 		u16 live_regs = env->insn_aux_data[ip].live_regs_before;  in clean_verifier_state()
483 		__clean_func_state(env, st->frame[i], live_regs, i);  in clean_verifier_state()
505 static bool regsafe(struct bpf_verifier_env *env, struct bpf_reg_state *rold,  in regsafe()  argument
542 		if (env->explore_alu_limits) {  in regsafe()
673 static bool is_stack_misc_after(struct bpf_verifier_env *env,  in is_stack_misc_after()  argument
681 		     env->allow_uninit_stack))  in is_stack_misc_after()
689 static struct bpf_reg_state *scalar_reg_for_stack(struct bpf_verifier_env *env,  in scalar_reg_for_stack()  argument
695 	if (is_stack_misc_after(env, stack, im))  in scalar_reg_for_stack()
701 static bool stacksafe(struct bpf_verifier_env *env, struct bpf_func_state *old,  in stacksafe()  argument
735 		if (env->allow_uninit_stack &&  in stacksafe()
752 			old_reg = scalar_reg_for_stack(env, &old->stack[spi], im);  in stacksafe()
753 			cur_reg = scalar_reg_for_stack(env, &cur->stack[spi], im);  in stacksafe()
755 				if (!regsafe(env, old_reg, cur_reg, idmap, exact))  in stacksafe()
792 			if (!regsafe(env, &old->stack[spi].spilled_ptr,  in stacksafe()
846 static bool stack_arg_safe(struct bpf_verifier_env *env, struct bpf_func_state *old,  in stack_arg_safe()  argument
861 		if (!regsafe(env, old_arg, cur_arg, idmap, exact))  in stack_arg_safe()
944 static bool func_states_equal(struct bpf_verifier_env *env, struct bpf_func_state *old,  in func_states_equal()  argument
947 	u16 live_regs = env->insn_aux_data[insn_idx].live_regs_before;  in func_states_equal()
958 		    !regsafe(env, &old->regs[i], &cur->regs[i],  in func_states_equal()
959 			     &env->idmap_scratch, exact))  in func_states_equal()
962 	if (!stacksafe(env, old, cur, &env->idmap_scratch, exact))  in func_states_equal()
965 	if (!stack_arg_safe(env, old, cur, &env->idmap_scratch, exact))  in func_states_equal()
971 static void reset_idmap_scratch(struct bpf_verifier_env *env)  in reset_idmap_scratch()  argument
973 	struct bpf_idmap *idmap = &env->idmap_scratch;  in reset_idmap_scratch()
975 	idmap->tmp_id_gen = env->id_gen;  in reset_idmap_scratch()
979 static bool states_equal(struct bpf_verifier_env *env,  in states_equal()  argument
990 	reset_idmap_scratch(env);  in states_equal()
1001 	if (!refsafe(old, cur, &env->idmap_scratch))  in states_equal()
1011 		if (!func_states_equal(env, old->frame[i], cur->frame[i], insn_idx, exact))  in states_equal()
1020 static int propagate_precision(struct bpf_verifier_env *env,  in propagate_precision()  argument
1038 			if (env->log.level & BPF_LOG_LEVEL2) {  in propagate_precision()
1040 					verbose(env, "frame %d: propagating r%d", fr, i);  in propagate_precision()
1042 					verbose(env, ",r%d", i);  in propagate_precision()
1044 			bpf_bt_set_frame_reg(&env->bt, fr, i);  in propagate_precision()
1055 			if (env->log.level & BPF_LOG_LEVEL2) {  in propagate_precision()
1057 					verbose(env, "frame %d: propagating fp%d",  in propagate_precision()
1060 					verbose(env, ",fp%d", (-i - 1) * BPF_REG_SIZE);  in propagate_precision()
1062 			bpf_bt_set_frame_slot(&env->bt, fr, i);  in propagate_precision()
1065 		if (!first && (env->log.level & BPF_LOG_LEVEL2))  in propagate_precision()
1066 			verbose(env, "\n");  in propagate_precision()
1069 	err = bpf_mark_chain_precision(env, cur, -1, changed);  in propagate_precision()
1084 static int propagate_backedges(struct bpf_verifier_env *env, struct bpf_scc_visit *visit)  in propagate_backedges()  argument
1094 			if (env->log.level & BPF_LOG_LEVEL2)  in propagate_backedges()
1095 				verbose(env, "%s: too many iterations\n", __func__);  in propagate_backedges()
1097 				bpf_mark_all_scalars_precise(env, &backedge->state);  in propagate_backedges()
1103 			err = propagate_precision(env, st->equal_state, st, &changed);  in propagate_backedges()
1213 static void mark_all_scalars_imprecise(struct bpf_verifier_env *env, struct bpf_verifier_state *st)  in mark_all_scalars_imprecise()  argument
1238 int bpf_is_state_visited(struct bpf_verifier_env *env, int insn_idx)  in bpf_is_state_visited()  argument
1242 	struct bpf_verifier_state *cur = env->cur_state, *new;  in bpf_is_state_visited()
1247 	force_new_state = env->test_state_freq || bpf_is_force_checkpoint(env, insn_idx) ||  in bpf_is_state_visited()
1260 	if (env->jmps_processed - env->prev_jmps_processed >= 2 &&  in bpf_is_state_visited()
1261 	    env->insn_processed - env->prev_insn_processed >= 8)  in bpf_is_state_visited()
1265 	err = clean_verifier_state(env, cur);  in bpf_is_state_visited()
1270 	head = bpf_explored_state(env, insn_idx);  in bpf_is_state_visited()
1331 			if (is_iter_next_insn(env, insn_idx)) {  in bpf_is_state_visited()
1332 				if (states_equal(env, &sl->state, cur, RANGE_WITHIN)) {  in bpf_is_state_visited()
1347 					iter_state = &bpf_func(env, iter_reg)->stack[spi].spilled_ptr;  in bpf_is_state_visited()
1355 			if (is_may_goto_insn_at(env, insn_idx)) {  in bpf_is_state_visited()
1357 				    states_equal(env, &sl->state, cur, RANGE_WITHIN)) {  in bpf_is_state_visited()
1362 			if (bpf_calls_callback(env, insn_idx)) {  in bpf_is_state_visited()
1363 				if (states_equal(env, &sl->state, cur, RANGE_WITHIN)) {  in bpf_is_state_visited()
1371 			    states_equal(env, &sl->state, cur, EXACT) &&  in bpf_is_state_visited()
1375 				verbose_linfo(env, insn_idx, "; ");  in bpf_is_state_visited()
1376 				verbose(env, "infinite loop detected at insn %d\n", insn_idx);  in bpf_is_state_visited()
1377 				verbose(env, "cur state:");  in bpf_is_state_visited()
1378 				print_verifier_state(env, cur, cur->curframe, true);  in bpf_is_state_visited()
1379 				verbose(env, "old state:");  in bpf_is_state_visited()
1380 				print_verifier_state(env, &sl->state, cur->curframe, true);  in bpf_is_state_visited()
1397 			    env->jmps_processed - env->prev_jmps_processed < 20 &&  in bpf_is_state_visited()
1398 			    env->insn_processed - env->prev_insn_processed < 100)  in bpf_is_state_visited()
1403 		loop = incomplete_read_marks(env, &sl->state);  in bpf_is_state_visited()
1404 		if (states_equal(env, &sl->state, cur, loop ? RANGE_WITHIN : NOT_EXACT)) {  in bpf_is_state_visited()
1414 			if (bpf_is_jmp_point(env, env->insn_idx))  in bpf_is_state_visited()
1415 				err = bpf_push_jmp_history(env, cur, 0, 0, 0, 0);  in bpf_is_state_visited()
1416 			err = err ? : propagate_precision(env, &sl->state, cur, NULL);  in bpf_is_state_visited()
1501 				err = err ?: add_scc_backedge(env, &sl->state, backedge);  in bpf_is_state_visited()
1527 		n = bpf_is_force_checkpoint(env, insn_idx) && sl->state.branches > 0 ? 64 : 3;  in bpf_is_state_visited()
1534 			list_add(&sl->node, &env->free_list);  in bpf_is_state_visited()
1535 			env->free_list_size++;  in bpf_is_state_visited()
1536 			env->explored_states_size--;  in bpf_is_state_visited()
1537 			maybe_free_verifier_state(env, sl);  in bpf_is_state_visited()
1541 	if (env->max_states_per_insn < states_cnt)  in bpf_is_state_visited()
1542 		env->max_states_per_insn = states_cnt;  in bpf_is_state_visited()
1544 	if (!env->bpf_capable && states_cnt > BPF_COMPLEXITY_LIMIT_STATES)  in bpf_is_state_visited()
1562 	env->total_states++;  in bpf_is_state_visited()
1563 	env->explored_states_size++;  in bpf_is_state_visited()
1564 	update_peak_states(env);  in bpf_is_state_visited()
1565 	env->prev_jmps_processed = env->jmps_processed;  in bpf_is_state_visited()
1566 	env->prev_insn_processed = env->insn_processed;  in bpf_is_state_visited()
1569 	if (env->bpf_capable)  in bpf_is_state_visited()
1570 		mark_all_scalars_imprecise(env, cur);  in bpf_is_state_visited()
1572 	bpf_clear_singular_ids(env, cur);  in bpf_is_state_visited()
1583 	verifier_bug_if(new->branches != 1, env,  in bpf_is_state_visited()
1586 	err = maybe_enter_scc(env, new);  in bpf_is_state_visited()