128 	/* Cached instance corresponding to env->cur_state, avoids per-instruction ht lookup */
139 static void compute_callchain(struct bpf_verifier_env *env, struct bpf_verifier_state *st,  in compute_callchain()  argument
142 	struct bpf_subprog_info *subprog_info = env->subprog_info;  in compute_callchain()
174  * Instances are accumulated in env->liveness->func_instances and persist
177 static struct func_instance *__lookup_instance(struct bpf_verifier_env *env,  in __lookup_instance()  argument
180 	struct bpf_liveness *liveness = env->liveness;  in __lookup_instance()
190 	subprog = bpf_find_containing_subprog(env, callchain->sp_starts[callchain->curframe]);  in __lookup_instance()
208 static struct func_instance *lookup_instance(struct bpf_verifier_env *env,  in lookup_instance()  argument
214 	compute_callchain(env, st, &callchain, frameno);  in lookup_instance()
215 	return __lookup_instance(env, &callchain);  in lookup_instance()
218 int bpf_stack_liveness_init(struct bpf_verifier_env *env)  in bpf_stack_liveness_init()  argument
220 	env->liveness = kvzalloc(sizeof(*env->liveness), GFP_KERNEL_ACCOUNT);  in bpf_stack_liveness_init()
221 	if (!env->liveness)  in bpf_stack_liveness_init()
223 	hash_init(env->liveness->func_instances);  in bpf_stack_liveness_init()
227 void bpf_stack_liveness_free(struct bpf_verifier_env *env)  in bpf_stack_liveness_free()  argument
233 	if (!env->liveness)  in bpf_stack_liveness_free()
235 	hash_for_each_safe(env->liveness->func_instances, bkt, tmp, instance, hl_node) {  in bpf_stack_liveness_free()
241 	kvfree(env->liveness);  in bpf_stack_liveness_free()
262 static struct per_frame_masks *alloc_frame_masks(struct bpf_verifier_env *env,  in alloc_frame_masks()  argument
277 void bpf_reset_live_stack_callchain(struct bpf_verifier_env *env)  in bpf_reset_live_stack_callchain()  argument
279 	env->liveness->cur_instance = NULL;  in bpf_reset_live_stack_callchain()
282 /* If @env->liveness->cur_instance is null, set it to instance corresponding to @env->cur_state. */
283 static int ensure_cur_instance(struct bpf_verifier_env *env)  in ensure_cur_instance()  argument
285 	struct bpf_liveness *liveness = env->liveness;  in ensure_cur_instance()
291 	instance = lookup_instance(env, env->cur_state, env->cur_state->curframe);  in ensure_cur_instance()
300 static int mark_stack_read(struct bpf_verifier_env *env,  in mark_stack_read()  argument
306 	masks = alloc_frame_masks(env, instance, frame, insn_idx);  in mark_stack_read()
317 int bpf_mark_stack_read(struct bpf_verifier_env *env, u32 frame, u32 insn_idx, u64 mask)  in bpf_mark_stack_read()  argument
321 	err = ensure_cur_instance(env);  in bpf_mark_stack_read()
322 	err = err ?: mark_stack_read(env, env->liveness->cur_instance, frame, insn_idx, mask);  in bpf_mark_stack_read()
326 static void reset_stack_write_marks(struct bpf_verifier_env *env,  in reset_stack_write_marks()  argument
329 	struct bpf_liveness *liveness = env->liveness;  in reset_stack_write_marks()
337 int bpf_reset_stack_write_marks(struct bpf_verifier_env *env, u32 insn_idx)  in bpf_reset_stack_write_marks()  argument
339 	struct bpf_liveness *liveness = env->liveness;  in bpf_reset_stack_write_marks()
342 	err = ensure_cur_instance(env);  in bpf_reset_stack_write_marks()
346 	reset_stack_write_marks(env, liveness->cur_instance, insn_idx);  in bpf_reset_stack_write_marks()
350 void bpf_mark_stack_write(struct bpf_verifier_env *env, u32 frame, u64 mask)  in bpf_mark_stack_write()  argument
352 	env->liveness->write_masks_acc[frame] |= mask;  in bpf_mark_stack_write()
355 static int commit_stack_write_marks(struct bpf_verifier_env *env,  in commit_stack_write_marks()  argument
358 	struct bpf_liveness *liveness = env->liveness;  in commit_stack_write_marks()
373 		masks = alloc_frame_masks(env, instance, frame, liveness->write_insn_idx);  in commit_stack_write_marks()
396  * Merge stack writes marks in @env->liveness->write_masks_acc
397  * with information already in @env->liveness->cur_instance.
399 int bpf_commit_stack_write_marks(struct bpf_verifier_env *env)  in bpf_commit_stack_write_marks()  argument
401 	return commit_stack_write_marks(env, env->liveness->cur_instance);  in bpf_commit_stack_write_marks()
404 static char *fmt_callchain(struct bpf_verifier_env *env, struct callchain *callchain)  in fmt_callchain()  argument
406 	char *buf_end = env->tmp_str_buf + sizeof(env->tmp_str_buf);  in fmt_callchain()
407 	char *buf = env->tmp_str_buf;  in fmt_callchain()
414 	return env->tmp_str_buf;  in fmt_callchain()
417 static void log_mask_change(struct bpf_verifier_env *env, struct callchain *callchain,  in log_mask_change()  argument
426 	bpf_log(&env->log, "%s frame %d insn %d ", fmt_callchain(env, callchain), frame, insn_idx);  in log_mask_change()
428 		bpf_fmt_stack_mask(env->tmp_str_buf, sizeof(env->tmp_str_buf), new_ones);  in log_mask_change()
429 		bpf_log(&env->log, "+%s %s ", pfx, env->tmp_str_buf);  in log_mask_change()
432 		bpf_fmt_stack_mask(env->tmp_str_buf, sizeof(env->tmp_str_buf), new_zeros);  in log_mask_change()
433 		bpf_log(&env->log, "-%s %s", pfx, env->tmp_str_buf);  in log_mask_change()
435 	bpf_log(&env->log, "\n");  in log_mask_change()
494 static struct func_instance *get_outer_instance(struct bpf_verifier_env *env,  in get_outer_instance()  argument
504 	return __lookup_instance(env, &callchain);  in get_outer_instance()
516 static int propagate_to_outer_instance(struct bpf_verifier_env *env,  in propagate_to_outer_instance()  argument
526 	outer_instance = get_outer_instance(env, instance);  in propagate_to_outer_instance()
529 	reset_stack_write_marks(env, outer_instance, callsite);  in propagate_to_outer_instance()
534 		bpf_mark_stack_write(env, frame, insn->must_write_acc);  in propagate_to_outer_instance()
535 		err = mark_stack_read(env, outer_instance, frame, callsite, insn->live_before);  in propagate_to_outer_instance()
539 	commit_stack_write_marks(env, outer_instance);  in propagate_to_outer_instance()
543 static inline bool update_insn(struct bpf_verifier_env *env,  in update_insn()  argument
546 	struct bpf_insn_aux_data *aux = env->insn_aux_data;  in update_insn()
552 	succ_num = bpf_insn_successors(env->prog, insn_idx, succ);  in update_insn()
578 	if (unlikely(env->log.level & BPF_LOG_LEVEL2) &&  in update_insn()
582 		log_mask_change(env, &instance->callchain, "live",  in update_insn()
584 		log_mask_change(env, &instance->callchain, "written",  in update_insn()
593 static int update_instance(struct bpf_verifier_env *env, struct func_instance *instance)  in update_instance()  argument
597 	int *insn_postorder = env->cfg.insn_postorder;  in update_instance()
620 	subprog = bpf_find_containing_subprog(env, this_subprog_start);  in update_instance()
633 				changed |= update_insn(env, instance, frame, insn_postorder[i]);  in update_instance()
637 	if (env->log.level & BPF_LOG_LEVEL2)  in update_instance()
638 		bpf_log(&env->log, "%s live stack update done in %d iterations\n",  in update_instance()
639 			fmt_callchain(env, callchain), cnt);  in update_instance()
643 		err = propagate_to_outer_instance(env, instance);  in update_instance()
652  * Prepare all callchains within @env->cur_state for querying.
657  * @env->liveness.
659 int bpf_update_live_stack(struct bpf_verifier_env *env)  in bpf_update_live_stack()  argument
664 	bpf_reset_live_stack_callchain(env);  in bpf_update_live_stack()
665 	for (frame = env->cur_state->curframe; frame >= 0; --frame) {  in bpf_update_live_stack()
666 		instance = lookup_instance(env, env->cur_state, frame);  in bpf_update_live_stack()
671 			err = update_instance(env, instance);  in bpf_update_live_stack()
689 int bpf_live_stack_query_init(struct bpf_verifier_env *env, struct bpf_verifier_state *st)  in bpf_live_stack_query_init()  argument
691 	struct live_stack_query *q = &env->liveness->live_stack_query;  in bpf_live_stack_query_init()
697 		instance = lookup_instance(env, st, frame);  in bpf_live_stack_query_init()
707 bool bpf_stack_slot_alive(struct bpf_verifier_env *env, u32 frameno, u32 spi)  in bpf_stack_slot_alive()  argument
715 	struct live_stack_query *q = &env->liveness->live_stack_query;  in bpf_stack_slot_alive()
727 		alive = bpf_calls_callback(env, callsite)  in bpf_stack_slot_alive()