23  * - As the verifier accumulates a set of visited states, the analysis instance
72  *     read and write marks are already recorded by the analysis instance.
78  * - Function instance: for a given call chain, for each instruction in
103  * A function instance created for a specific callchain.
128 	/* Cached instance corresponding to env->cur_state, avoids per-instruction ht lookup */
173  * Find existing or allocate new function instance corresponding to @callchain.
229 	struct func_instance *instance;  in bpf_stack_liveness_free()  local
235 	hash_for_each_safe(env->liveness->func_instances, bkt, tmp, instance, hl_node) {  in bpf_stack_liveness_free()
236 		for (i = 0; i <= instance->callchain.curframe; i++)  in bpf_stack_liveness_free()
237 			kvfree(instance->frames[i]);  in bpf_stack_liveness_free()
238 		kvfree(instance->must_write_set);  in bpf_stack_liveness_free()
239 		kvfree(instance);  in bpf_stack_liveness_free()
246  * to start of the function corresponding to @instance.
248 static int relative_idx(struct func_instance *instance, u32 insn_idx)  in relative_idx()  argument
250 	return insn_idx - instance->callchain.sp_starts[instance->callchain.curframe];  in relative_idx()
253 static struct per_frame_masks *get_frame_masks(struct func_instance *instance,  in get_frame_masks()  argument
256 	if (!instance->frames[frame])  in get_frame_masks()
259 	return &instance->frames[frame][relative_idx(instance, insn_idx)];  in get_frame_masks()
263 						 struct func_instance *instance,  in alloc_frame_masks()  argument
268 	if (!instance->frames[frame]) {  in alloc_frame_masks()
269 		arr = kvcalloc(instance->insn_cnt, sizeof(*arr), GFP_KERNEL_ACCOUNT);  in alloc_frame_masks()
270 		instance->frames[frame] = arr;  in alloc_frame_masks()
274 	return get_frame_masks(instance, frame, insn_idx);  in alloc_frame_masks()
282 /* If @env->liveness->cur_instance is null, set it to instance corresponding to @env->cur_state. */
286 	struct func_instance *instance;  in ensure_cur_instance()  local
291 	instance = lookup_instance(env, env->cur_state, env->cur_state->curframe);  in ensure_cur_instance()
292 	if (IS_ERR(instance))  in ensure_cur_instance()
293 		return PTR_ERR(instance);  in ensure_cur_instance()
295 	liveness->cur_instance = instance;  in ensure_cur_instance()
301 			   struct func_instance *instance, u32 frame, u32 insn_idx, u64 mask)  in mark_stack_read()  argument
306 	masks = alloc_frame_masks(env, instance, frame, insn_idx);  in mark_stack_read()
312 		instance->updated = true;  in mark_stack_read()
327 				    struct func_instance *instance, u32 insn_idx)  in reset_stack_write_marks()  argument
333 	for (i = 0; i <= instance->callchain.curframe; i++)  in reset_stack_write_marks()
356 				    struct func_instance *instance)  in commit_stack_write_marks()  argument
363 	if (!instance)  in commit_stack_write_marks()
366 	curframe = instance->callchain.curframe;  in commit_stack_write_marks()
367 	idx = relative_idx(instance, liveness->write_insn_idx);  in commit_stack_write_marks()
371 		if (mask == 0 && !instance->must_write_set[idx])  in commit_stack_write_marks()
373 		masks = alloc_frame_masks(env, instance, frame, liveness->write_insn_idx);  in commit_stack_write_marks()
381 		if (instance->must_write_set[idx])  in commit_stack_write_marks()
385 			instance->updated = true;  in commit_stack_write_marks()
388 			instance->must_write_dropped = true;  in commit_stack_write_marks()
390 	instance->must_write_set[idx] = true;  in commit_stack_write_marks()
495 						struct func_instance *instance)  in get_outer_instance()  argument
497 	struct callchain callchain = instance->callchain;  in get_outer_instance()
513  * Transfer @may_read and @must_write_acc marks from the first instruction of @instance,
514  * to the call instruction in function instance calling @instance.
517 				       struct func_instance *instance)  in propagate_to_outer_instance()  argument
519 	struct callchain *callchain = &instance->callchain;  in propagate_to_outer_instance()
526 	outer_instance = get_outer_instance(env, instance);  in propagate_to_outer_instance()
531 		insn = get_frame_masks(instance, frame, this_subprog_start);  in propagate_to_outer_instance()
544 			       struct func_instance *instance, u32 frame, u32 insn_idx)  in update_insn()  argument
557 	insn = get_frame_masks(instance, frame, insn_idx);  in update_insn()
566 		succ_insn = get_frame_masks(instance, frame, succ[s]);  in update_insn()
580 	     insn_idx == callchain_subprog_start(&instance->callchain) ||  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
596 	struct callchain *callchain = &instance->callchain;  in update_instance()
608 	if (instance->must_write_dropped) {  in update_instance()
610 			if (!instance->frames[frame])  in update_instance()
613 			for (i = 0; i < instance->insn_cnt; i++) {  in update_instance()
614 				insn = get_frame_masks(instance, frame, this_subprog_start + i);  in update_instance()
628 		for (frame = 0; frame <= instance->callchain.curframe; frame++) {  in update_instance()
629 			if (!instance->frames[frame])  in update_instance()
633 				changed |= update_insn(env, instance, frame, insn_postorder[i]);  in update_instance()
641 	/* transfer marks accumulated for outer frames to outer func instance (caller) */  in update_instance()
643 		err = propagate_to_outer_instance(env, instance);  in update_instance()
661 	struct func_instance *instance;  in bpf_update_live_stack()  local
666 		instance = lookup_instance(env, env->cur_state, frame);  in bpf_update_live_stack()
667 		if (IS_ERR(instance))  in bpf_update_live_stack()
668 			return PTR_ERR(instance);  in bpf_update_live_stack()
670 		if (instance->updated) {  in bpf_update_live_stack()
671 			err = update_instance(env, instance);  in bpf_update_live_stack()
674 			instance->updated = false;  in bpf_update_live_stack()
675 			instance->must_write_dropped = false;  in bpf_update_live_stack()
681 static bool is_live_before(struct func_instance *instance, u32 insn_idx, u32 frameno, u32 spi)  in is_live_before()  argument
685 	masks = get_frame_masks(instance, frameno, insn_idx);  in is_live_before()
692 	struct func_instance *instance;  in bpf_live_stack_query_init()  local
697 		instance = lookup_instance(env, st, frame);  in bpf_live_stack_query_init()
698 		if (IS_ERR(instance))  in bpf_live_stack_query_init()
699 			return PTR_ERR(instance);  in bpf_live_stack_query_init()
700 		q->instances[frame] = instance;  in bpf_live_stack_query_init()
710 	 * Slot is alive if it is read before q->st->insn_idx in current func instance,  in bpf_stack_slot_alive()
711 	 * or if for some outer func instance:  in bpf_stack_slot_alive()
716 	struct func_instance *instance, *curframe_instance;  in bpf_stack_slot_alive()  local
726 		instance = q->instances[i];  in bpf_stack_slot_alive()
728 			? is_live_before(instance, callsite, frameno, spi)  in bpf_stack_slot_alive()
729 			: is_live_before(instance, callsite + 1, frameno, spi);  in bpf_stack_slot_alive()