8 #define verbose(env, fmt, args...) bpf_verifier_log_write(env, fmt, ##args)  argument
51 static void mark_subprog_changes_pkt_data(struct bpf_verifier_env *env, int off)  in mark_subprog_changes_pkt_data()  argument
55 	subprog = bpf_find_containing_subprog(env, off);  in mark_subprog_changes_pkt_data()
59 static void mark_subprog_might_sleep(struct bpf_verifier_env *env, int off)  in mark_subprog_might_sleep()  argument
63 	subprog = bpf_find_containing_subprog(env, off);  in mark_subprog_might_sleep()
67 static void mark_subprog_might_throw(struct bpf_verifier_env *env, int off)  in mark_subprog_might_throw()  argument
71 	subprog = bpf_find_containing_subprog(env, off);  in mark_subprog_might_throw()
81 static void merge_callee_effects(struct bpf_verifier_env *env, int t, int w)  in merge_callee_effects()  argument
85 	caller = bpf_find_containing_subprog(env, t);  in merge_callee_effects()
86 	callee = bpf_find_containing_subprog(env, w);  in merge_callee_effects()
102 static int push_insn(int t, int w, int e, struct bpf_verifier_env *env)  in push_insn()  argument
104 	int *insn_stack = env->cfg.insn_stack;  in push_insn()
105 	int *insn_state = env->cfg.insn_state;  in push_insn()
113 	if (w < 0 || w >= env->prog->len) {  in push_insn()
114 		verbose_linfo(env, t, "%d: ", t);  in push_insn()
115 		verbose(env, "jump out of range from insn %d to %d\n", t, w);  in push_insn()
121 		mark_prune_point(env, w);  in push_insn()
122 		mark_jmp_point(env, w);  in push_insn()
129 		if (env->cfg.cur_stack >= env->prog->len)  in push_insn()
131 		insn_stack[env->cfg.cur_stack++] = w;  in push_insn()
134 		if (env->bpf_capable)  in push_insn()
136 		verbose_linfo(env, t, "%d: ", t);  in push_insn()
137 		verbose_linfo(env, w, "%d: ", w);  in push_insn()
138 		verbose(env, "back-edge from insn %d to %d\n", t, w);  in push_insn()
144 		verifier_bug(env, "insn state internal bug");  in push_insn()
151 				struct bpf_verifier_env *env,  in visit_func_call_insn()  argument
158 	ret = push_insn(t, t + insn_sz, FALLTHROUGH, env);  in visit_func_call_insn()
162 	mark_prune_point(env, t + insn_sz);  in visit_func_call_insn()
164 	mark_jmp_point(env, t + insn_sz);  in visit_func_call_insn()
168 		mark_prune_point(env, t);  in visit_func_call_insn()
169 		merge_callee_effects(env, t, w);  in visit_func_call_insn()
170 		ret = push_insn(t, w, BRANCH, env);  in visit_func_call_insn()
279 static struct bpf_iarray *jt_from_subprog(struct bpf_verifier_env *env,  in jt_from_subprog()  argument
287 	for (i = 0; i < env->insn_array_map_cnt; i++) {  in jt_from_subprog()
292 		map = env->insn_array_maps[i];  in jt_from_subprog()
318 		verbose(env, "no jump tables found for subprog starting at %u\n", subprog_start);  in jt_from_subprog()
327 create_jt(int t, struct bpf_verifier_env *env)  in create_jt()  argument
334 	subprog = bpf_find_containing_subprog(env, t);  in create_jt()
337 	jt = jt_from_subprog(env, subprog_start, subprog_end);  in create_jt()
344 			verbose(env, "jump table for insn %d points outside of the subprog [%u,%u]\n",  in create_jt()
355 static int visit_gotox_insn(int t, struct bpf_verifier_env *env)  in visit_gotox_insn()  argument
357 	int *insn_stack = env->cfg.insn_stack;  in visit_gotox_insn()
358 	int *insn_state = env->cfg.insn_state;  in visit_gotox_insn()
363 	jt = env->insn_aux_data[t].jt;  in visit_gotox_insn()
365 		jt = create_jt(t, env);  in visit_gotox_insn()
369 		env->insn_aux_data[t].jt = jt;  in visit_gotox_insn()
372 	mark_prune_point(env, t);  in visit_gotox_insn()
375 		if (w < 0 || w >= env->prog->len) {  in visit_gotox_insn()
376 			verbose(env, "indirect jump out of range from insn %d to %d\n", t, w);  in visit_gotox_insn()
380 		mark_jmp_point(env, w);  in visit_gotox_insn()
386 		if (env->cfg.cur_stack >= env->prog->len)  in visit_gotox_insn()
389 		insn_stack[env->cfg.cur_stack++] = w;  in visit_gotox_insn()
402 static int visit_abnormal_return_insn(struct bpf_verifier_env *env, int t)  in visit_abnormal_return_insn()  argument
407 	if (env->insn_aux_data[t].jt)  in visit_abnormal_return_insn()
414 	subprog = bpf_find_containing_subprog(env, t);  in visit_abnormal_return_insn()
417 	env->insn_aux_data[t].jt = jt;  in visit_abnormal_return_insn()
426 static int visit_insn(int t, struct bpf_verifier_env *env)  in visit_insn()  argument
428 	struct bpf_insn *insns = env->prog->insnsi, *insn = &insns[t];  in visit_insn()
432 		return visit_func_call_insn(t, insns, env, true);  in visit_insn()
440 			ret = visit_abnormal_return_insn(env, t);  in visit_insn()
445 		return push_insn(t, t + insn_sz, FALLTHROUGH, env);  in visit_insn()
459 			mark_prune_point(env, t);  in visit_insn()
470 			mark_calls_callback(env, t);  in visit_insn()
471 			mark_force_checkpoint(env, t);  in visit_insn()
472 			mark_prune_point(env, t);  in visit_insn()
473 			mark_jmp_point(env, t);  in visit_insn()
478 			ret = bpf_get_helper_proto(env, insn->imm, &fp);  in visit_insn()
485 				mark_subprog_might_sleep(env, t);  in visit_insn()
487 				mark_subprog_changes_pkt_data(env, t);  in visit_insn()
489 				ret = visit_abnormal_return_insn(env, t);  in visit_insn()
496 			ret = bpf_fetch_kfunc_arg_meta(env, insn->imm, insn->off, &meta);  in visit_insn()
498 				mark_prune_point(env, t);  in visit_insn()
510 				mark_force_checkpoint(env, t);  in visit_insn()
518 				mark_subprog_might_sleep(env, t);  in visit_insn()
520 				mark_subprog_changes_pkt_data(env, t);  in visit_insn()
522 				mark_subprog_might_throw(env, t);  in visit_insn()
524 		return visit_func_call_insn(t, insns, env, insn->src_reg == BPF_PSEUDO_CALL);  in visit_insn()
528 			return visit_gotox_insn(t, env);  in visit_insn()
536 		ret = push_insn(t, t + off + 1, FALLTHROUGH, env);  in visit_insn()
540 		mark_prune_point(env, t + off + 1);  in visit_insn()
541 		mark_jmp_point(env, t + off + 1);  in visit_insn()
547 		mark_prune_point(env, t);  in visit_insn()
549 			mark_force_checkpoint(env, t);  in visit_insn()
551 		ret = push_insn(t, t + 1, FALLTHROUGH, env);  in visit_insn()
555 		return push_insn(t, t + insn->off + 1, BRANCH, env);  in visit_insn()
562 int bpf_check_cfg(struct bpf_verifier_env *env)  in bpf_check_cfg()  argument
564 	int insn_cnt = env->prog->len;  in bpf_check_cfg()
568 	insn_state = env->cfg.insn_state = kvzalloc_objs(int, insn_cnt,  in bpf_check_cfg()
573 	insn_stack = env->cfg.insn_stack = kvzalloc_objs(int, insn_cnt,  in bpf_check_cfg()
580 	ex_insn_beg = env->exception_callback_subprog  in bpf_check_cfg()
581 		      ? env->subprog_info[env->exception_callback_subprog].start  in bpf_check_cfg()
586 	env->cfg.cur_stack = 1;  in bpf_check_cfg()
589 	while (env->cfg.cur_stack > 0) {  in bpf_check_cfg()
590 		int t = insn_stack[env->cfg.cur_stack - 1];  in bpf_check_cfg()
592 		ret = visit_insn(t, env);  in bpf_check_cfg()
596 			env->cfg.cur_stack--;  in bpf_check_cfg()
602 				verifier_bug(env, "visit_insn internal bug");  in bpf_check_cfg()
609 	if (env->cfg.cur_stack < 0) {  in bpf_check_cfg()
610 		verifier_bug(env, "pop stack internal bug");  in bpf_check_cfg()
618 		env->cfg.cur_stack = 1;  in bpf_check_cfg()
623 		struct bpf_insn *insn = &env->prog->insnsi[i];  in bpf_check_cfg()
626 			verbose(env, "unreachable insn %d\n", i);  in bpf_check_cfg()
632 				verbose(env, "jump into the middle of ldimm64 insn %d\n", i);  in bpf_check_cfg()
640 	env->prog->aux->changes_pkt_data = env->subprog_info[0].changes_pkt_data;  in bpf_check_cfg()
641 	env->prog->aux->might_sleep = env->subprog_info[0].might_sleep;  in bpf_check_cfg()
646 	env->cfg.insn_state = env->cfg.insn_stack = NULL;  in bpf_check_cfg()
655 int bpf_compute_postorder(struct bpf_verifier_env *env)  in bpf_compute_postorder()  argument
661 	postorder = kvzalloc_objs(int, env->prog->len, GFP_KERNEL_ACCOUNT);  in bpf_compute_postorder()
662 	state = kvzalloc_objs(int, env->prog->len, GFP_KERNEL_ACCOUNT);  in bpf_compute_postorder()
663 	stack = kvzalloc_objs(int, env->prog->len, GFP_KERNEL_ACCOUNT);  in bpf_compute_postorder()
671 	for (i = 0; i < env->subprog_cnt; i++) {  in bpf_compute_postorder()
672 		env->subprog_info[i].postorder_start = cur_postorder;  in bpf_compute_postorder()
673 		stack[0] = env->subprog_info[i].start;  in bpf_compute_postorder()
683 			succ = bpf_insn_successors(env, top);  in bpf_compute_postorder()
693 	env->subprog_info[i].postorder_start = cur_postorder;  in bpf_compute_postorder()
694 	env->cfg.insn_postorder = postorder;  in bpf_compute_postorder()
695 	env->cfg.cur_postorder = cur_postorder;  in bpf_compute_postorder()
708 int bpf_compute_scc(struct bpf_verifier_env *env)  in bpf_compute_scc()  argument
712 	struct bpf_insn_aux_data *aux = env->insn_aux_data;  in bpf_compute_scc()
713 	const u32 insn_cnt = env->prog->len;  in bpf_compute_scc()
827 			succ = bpf_insn_successors(env, w);  in bpf_compute_scc()
856 			if (bpf_calls_callback(env, w)) /* implicit loop? */  in bpf_compute_scc()
870 	env->scc_info = kvzalloc_objs(*env->scc_info, next_scc_id,  in bpf_compute_scc()
872 	if (!env->scc_info) {  in bpf_compute_scc()
876 	env->scc_cnt = next_scc_id;  in bpf_compute_scc()