kernel/bpf/liveness.c

Source file repositories/reference/linux-study-clean/kernel/bpf/liveness.c

File Facts

System
Linux kernel
Corpus path
kernel/bpf/liveness.c
Extension
.c
Size
65342 bytes
Lines
2297
Domain
Core OS
Bucket
Scheduler, Processes, Timers, Sync, And Syscalls
Inferred role
Core OS: implementation source
Status
source implementation candidate

Why This File Exists

Core operating-system implementation surface: boot, tasks, memory, VFS, syscall-facing interfaces, synchronization, credentials, and isolation.

Dependency Surface

Detected Declarations

Annotated Snippet

struct per_frame_masks {
	spis_t may_read;	/* stack slots that may be read by this instruction */
	spis_t must_write;	/* stack slots written by this instruction */
	spis_t live_before;	/* stack slots that may be read by this insn and its successors */
};

/*
 * A function instance keyed by (callsite, depth).
 * Encapsulates read and write marks for each instruction in the function.
 * Marks are tracked for each frame up to @depth.
 */
struct func_instance {
	struct hlist_node hl_node;
	u32 callsite;		/* call insn that invoked this subprog (subprog_start for depth 0) */
	u32 depth;		/* call depth (0 = entry subprog) */
	u32 subprog;		/* subprog index */
	u32 subprog_start;	/* cached env->subprog_info[subprog].start */
	u32 insn_cnt;		/* cached number of insns in the function */
	/* Per frame, per instruction masks, frames allocated lazily. */
	struct per_frame_masks *frames[MAX_CALL_FRAMES];
	bool must_write_initialized;
};

struct live_stack_query {
	struct func_instance *instances[MAX_CALL_FRAMES]; /* valid in range [0..curframe] */
	u32 callsites[MAX_CALL_FRAMES]; /* callsite[i] = insn calling frame i+1 */
	u32 curframe;
	u32 insn_idx;
};

struct bpf_liveness {
	DECLARE_HASHTABLE(func_instances, 8);		/* maps (depth, callsite) to func_instance */
	struct live_stack_query live_stack_query;	/* cache to avoid repetitive ht lookups */
	u32 subprog_calls;				/* analyze_subprog() invocations */
};

/*
 * Hash/compare key for func_instance: (depth, callsite).
 * For depth == 0 (entry subprog), @callsite is the subprog start insn.
 * For depth > 0, @callsite is the call instruction index that invoked the subprog.
 */
static u32 instance_hash(u32 callsite, u32 depth)
{
	u32 key[2] = { depth, callsite };

	return jhash2(key, 2, 0);
}

static struct func_instance *find_instance(struct bpf_verifier_env *env,
					   u32 callsite, u32 depth)
{
	struct bpf_liveness *liveness = env->liveness;
	struct func_instance *f;
	u32 key = instance_hash(callsite, depth);

	hash_for_each_possible(liveness->func_instances, f, hl_node, key)
		if (f->depth == depth && f->callsite == callsite)
			return f;
	return NULL;
}

static struct func_instance *call_instance(struct bpf_verifier_env *env,
					   struct func_instance *caller,
					   u32 callsite, int subprog)
{
	u32 depth = caller ? caller->depth + 1 : 0;
	u32 subprog_start = env->subprog_info[subprog].start;
	u32 lookup_key = depth > 0 ? callsite : subprog_start;
	struct func_instance *f;
	u32 hash;

	f = find_instance(env, lookup_key, depth);
	if (f)
		return f;

	f = kvzalloc(sizeof(*f), GFP_KERNEL_ACCOUNT);
	if (!f)
		return ERR_PTR(-ENOMEM);
	f->callsite = lookup_key;
	f->depth = depth;
	f->subprog = subprog;
	f->subprog_start = subprog_start;
	f->insn_cnt = (env->subprog_info + subprog + 1)->start - subprog_start;
	hash = instance_hash(lookup_key, depth);
	hash_add(env->liveness->func_instances, &f->hl_node, hash);
	return f;
}

static struct func_instance *lookup_instance(struct bpf_verifier_env *env,
					     struct bpf_verifier_state *st,

Annotation

Implementation Notes