liveness.c

  1// SPDX-License-Identifier: GPL-2.0-only
  2/* Copyright (c) 2025 Meta Platforms, Inc. and affiliates. */
  3
  4#include <linux/bpf_verifier.h>
  5#include <linux/hashtable.h>
  6#include <linux/jhash.h>
  7#include <linux/slab.h>
  8
  9/*
 10 * This file implements live stack slots analysis. After accumulating
 11 * stack usage data, the analysis answers queries about whether a
 12 * particular stack slot may be read by an instruction or any of it's
 13 * successors.  This data is consumed by the verifier states caching
 14 * mechanism to decide which stack slots are important when looking for a
 15 * visited state corresponding to the current state.
 16 *
 17 * The analysis is call chain sensitive, meaning that data is collected
 18 * and queried for tuples (call chain, subprogram instruction index).
 19 * Such sensitivity allows identifying if some subprogram call always
 20 * leads to writes in the caller's stack.
 21 *
 22 * The basic idea is as follows:
 23 * - As the verifier accumulates a set of visited states, the analysis instance
 24 *   accumulates a conservative estimate of stack slots that can be read
 25 *   or must be written for each visited tuple (call chain, instruction index).
 26 * - If several states happen to visit the same instruction with the same
 27 *   call chain, stack usage information for the corresponding tuple is joined:
 28 *   - "may_read" set represents a union of all possibly read slots
 29 *     (any slot in "may_read" set might be read at or after the instruction);
 30 *   - "must_write" set represents an intersection of all possibly written slots
 31 *     (any slot in "must_write" set is guaranteed to be written by the instruction).
 32 * - The analysis is split into two phases:
 33 *   - read and write marks accumulation;
 34 *   - read and write marks propagation.
 35 * - The propagation phase is a textbook live variable data flow analysis:
 36 *
 37 *     state[cc, i].live_after = U [state[cc, s].live_before for s in bpf_insn_successors(i)]
 38 *     state[cc, i].live_before =
 39 *       (state[cc, i].live_after / state[cc, i].must_write) U state[i].may_read
 40 *
 41 *   Where:
 42 *   - `U`  stands for set union
 43 *   - `/`  stands for set difference;
 44 *   - `cc` stands for a call chain;
 45 *   - `i` and `s` are instruction indexes;
 46 *
 47 *   The above equations are computed for each call chain and instruction
 48 *   index until state stops changing.
 49 * - Additionally, in order to transfer "must_write" information from a
 50 *   subprogram to call instructions invoking this subprogram,
 51 *   the "must_write_acc" set is tracked for each (cc, i) tuple.
 52 *   A set of stack slots that are guaranteed to be written by this
 53 *   instruction or any of its successors (within the subprogram).
 54 *   The equation for "must_write_acc" propagation looks as follows:
 55 *
 56 *     state[cc, i].must_write_acc =
 57 *       ∩ [state[cc, s].must_write_acc for s in bpf_insn_successors(i)]
 58 *       U state[cc, i].must_write
 59 *
 60 *   (An intersection of all "must_write_acc" for instruction successors
 61 *    plus all "must_write" slots for the instruction itself).
 62 * - After the propagation phase completes for a subprogram, information from
 63 *   (cc, 0) tuple (subprogram entry) is transferred to the caller's call chain:
 64 *   - "must_write_acc" set is intersected with the call site's "must_write" set;
 65 *   - "may_read" set is added to the call site's "may_read" set.
 66 * - Any live stack queries must be taken after the propagation phase.
 67 * - Accumulation and propagation phases can be entered multiple times,
 68 *   at any point in time:
 69 *   - "may_read" set only grows;
 70 *   - "must_write" set only shrinks;
 71 *   - for each visited verifier state with zero branches, all relevant
 72 *     read and write marks are already recorded by the analysis instance.
 73 *
 74 * Technically, the analysis is facilitated by the following data structures:
 75 * - Call chain: for given verifier state, the call chain is a tuple of call
 76 *   instruction indexes leading to the current subprogram plus the subprogram
 77 *   entry point index.
 78 * - Function instance: for a given call chain, for each instruction in
 79 *   the current subprogram, a mapping between instruction index and a
 80 *   set of "may_read", "must_write" and other marks accumulated for this
 81 *   instruction.
 82 * - A hash table mapping call chains to function instances.
 83 */
 84
 85struct callchain {
 86	u32 callsites[MAX_CALL_FRAMES];	/* instruction pointer for each frame */
 87	/* cached subprog_info[*].start for functions owning the frames:
 88	 * - sp_starts[curframe] used to get insn relative index within current function;
 89	 * - sp_starts[0..current-1] used for fast callchain_frame_up().
 90	 */
 91	u32 sp_starts[MAX_CALL_FRAMES];
 92	u32 curframe;			/* depth of callsites and sp_starts arrays */
 93};
 94
 95struct per_frame_masks {
 96	u64 may_read;		/* stack slots that may be read by this instruction */
 97	u64 must_write;		/* stack slots written by this instruction */
 98	u64 must_write_acc;	/* stack slots written by this instruction and its successors */
 99	u64 live_before;	/* stack slots that may be read by this insn and its successors */
100};
101
102/*
103 * A function instance created for a specific callchain.
104 * Encapsulates read and write marks for each instruction in the function.
105 * Marks are tracked for each frame in the callchain.
106 */
107struct func_instance {
108	struct hlist_node hl_node;
109	struct callchain callchain;
110	u32 insn_cnt;		/* cached number of insns in the function */
111	bool updated;
112	bool must_write_dropped;
113	/* Per frame, per instruction masks, frames allocated lazily. */
114	struct per_frame_masks *frames[MAX_CALL_FRAMES];
115	/* For each instruction a flag telling if "must_write" had been initialized for it. */
116	bool *must_write_set;
117};
118
119struct live_stack_query {
120	struct func_instance *instances[MAX_CALL_FRAMES]; /* valid in range [0..curframe] */
121	u32 curframe;
122	u32 insn_idx;
123};
124
125struct bpf_liveness {
126	DECLARE_HASHTABLE(func_instances, 8);		/* maps callchain to func_instance */
127	struct live_stack_query live_stack_query;	/* cache to avoid repetitive ht lookups */
128	/* Cached instance corresponding to env->cur_state, avoids per-instruction ht lookup */
129	struct func_instance *cur_instance;
130	/*
131	 * Below fields are used to accumulate stack write marks for instruction at
132	 * @write_insn_idx before submitting the marks to @cur_instance.
133	 */
134	u64 write_masks_acc[MAX_CALL_FRAMES];
135	u32 write_insn_idx;
136};
137
138/* Compute callchain corresponding to state @st at depth @frameno */
139static void compute_callchain(struct bpf_verifier_env *env, struct bpf_verifier_state *st,
140			      struct callchain *callchain, u32 frameno)
141{
142	struct bpf_subprog_info *subprog_info = env->subprog_info;
143	u32 i;
144
145	memset(callchain, 0, sizeof(*callchain));
146	for (i = 0; i <= frameno; i++) {
147		callchain->sp_starts[i] = subprog_info[st->frame[i]->subprogno].start;
148		if (i < st->curframe)
149			callchain->callsites[i] = st->frame[i + 1]->callsite;
150	}
151	callchain->curframe = frameno;
152	callchain->callsites[callchain->curframe] = callchain->sp_starts[callchain->curframe];
153}
154
155static u32 hash_callchain(struct callchain *callchain)
156{
157	return jhash2(callchain->callsites, callchain->curframe, 0);
158}
159
160static bool same_callsites(struct callchain *a, struct callchain *b)
161{
162	int i;
163
164	if (a->curframe != b->curframe)
165		return false;
166	for (i = a->curframe; i >= 0; i--)
167		if (a->callsites[i] != b->callsites[i])
168			return false;
169	return true;
170}
171
172/*
173 * Find existing or allocate new function instance corresponding to @callchain.
174 * Instances are accumulated in env->liveness->func_instances and persist
175 * until the end of the verification process.
176 */
177static struct func_instance *__lookup_instance(struct bpf_verifier_env *env,
178					       struct callchain *callchain)
179{
180	struct bpf_liveness *liveness = env->liveness;
181	struct bpf_subprog_info *subprog;
182	struct func_instance *result;
183	u32 subprog_sz, size, key;
184
185	key = hash_callchain(callchain);
186	hash_for_each_possible(liveness->func_instances, result, hl_node, key)
187		if (same_callsites(&result->callchain, callchain))
188			return result;
189
190	subprog = bpf_find_containing_subprog(env, callchain->sp_starts[callchain->curframe]);
191	subprog_sz = (subprog + 1)->start - subprog->start;
192	size = sizeof(struct func_instance);
193	result = kvzalloc(size, GFP_KERNEL_ACCOUNT);
194	if (!result)
195		return ERR_PTR(-ENOMEM);
196	result->must_write_set = kvcalloc(subprog_sz, sizeof(*result->must_write_set),
197					  GFP_KERNEL_ACCOUNT);
198	if (!result->must_write_set) {
199		kvfree(result);
200		return ERR_PTR(-ENOMEM);
201	}
202	memcpy(&result->callchain, callchain, sizeof(*callchain));
203	result->insn_cnt = subprog_sz;
204	hash_add(liveness->func_instances, &result->hl_node, key);
205	return result;
206}
207
208static struct func_instance *lookup_instance(struct bpf_verifier_env *env,
209					     struct bpf_verifier_state *st,
210					     u32 frameno)
211{
212	struct callchain callchain;
213
214	compute_callchain(env, st, &callchain, frameno);
215	return __lookup_instance(env, &callchain);
216}
217
218int bpf_stack_liveness_init(struct bpf_verifier_env *env)
219{
220	env->liveness = kvzalloc(sizeof(*env->liveness), GFP_KERNEL_ACCOUNT);
221	if (!env->liveness)
222		return -ENOMEM;
223	hash_init(env->liveness->func_instances);
224	return 0;
225}
226
227void bpf_stack_liveness_free(struct bpf_verifier_env *env)
228{
229	struct func_instance *instance;
230	struct hlist_node *tmp;
231	int bkt, i;
232
233	if (!env->liveness)
234		return;
235	hash_for_each_safe(env->liveness->func_instances, bkt, tmp, instance, hl_node) {
236		for (i = 0; i <= instance->callchain.curframe; i++)
237			kvfree(instance->frames[i]);
238		kvfree(instance->must_write_set);
239		kvfree(instance);
240	}
241	kvfree(env->liveness);
242}
243
244/*
245 * Convert absolute instruction index @insn_idx to an index relative
246 * to start of the function corresponding to @instance.
247 */
248static int relative_idx(struct func_instance *instance, u32 insn_idx)
249{
250	return insn_idx - instance->callchain.sp_starts[instance->callchain.curframe];
251}
252
253static struct per_frame_masks *get_frame_masks(struct func_instance *instance,
254					       u32 frame, u32 insn_idx)
255{
256	if (!instance->frames[frame])
257		return NULL;
258
259	return &instance->frames[frame][relative_idx(instance, insn_idx)];
260}
261
262static struct per_frame_masks *alloc_frame_masks(struct bpf_verifier_env *env,
263						 struct func_instance *instance,
264						 u32 frame, u32 insn_idx)
265{
266	struct per_frame_masks *arr;
267
268	if (!instance->frames[frame]) {
269		arr = kvcalloc(instance->insn_cnt, sizeof(*arr), GFP_KERNEL_ACCOUNT);
270		instance->frames[frame] = arr;
271		if (!arr)
272			return ERR_PTR(-ENOMEM);
273	}
274	return get_frame_masks(instance, frame, insn_idx);
275}
276
277void bpf_reset_live_stack_callchain(struct bpf_verifier_env *env)
278{
279	env->liveness->cur_instance = NULL;
280}
281
282/* If @env->liveness->cur_instance is null, set it to instance corresponding to @env->cur_state. */
283static int ensure_cur_instance(struct bpf_verifier_env *env)
284{
285	struct bpf_liveness *liveness = env->liveness;
286	struct func_instance *instance;
287
288	if (liveness->cur_instance)
289		return 0;
290
291	instance = lookup_instance(env, env->cur_state, env->cur_state->curframe);
292	if (IS_ERR(instance))
293		return PTR_ERR(instance);
294
295	liveness->cur_instance = instance;
296	return 0;
297}
298
299/* Accumulate may_read masks for @frame at @insn_idx */
300static int mark_stack_read(struct bpf_verifier_env *env,
301			   struct func_instance *instance, u32 frame, u32 insn_idx, u64 mask)
302{
303	struct per_frame_masks *masks;
304	u64 new_may_read;
305
306	masks = alloc_frame_masks(env, instance, frame, insn_idx);
307	if (IS_ERR(masks))
308		return PTR_ERR(masks);
309	new_may_read = masks->may_read | mask;
310	if (new_may_read != masks->may_read &&
311	    ((new_may_read | masks->live_before) != masks->live_before))
312		instance->updated = true;
313	masks->may_read |= mask;
314	return 0;
315}
316
317int bpf_mark_stack_read(struct bpf_verifier_env *env, u32 frame, u32 insn_idx, u64 mask)
318{
319	int err;
320
321	err = ensure_cur_instance(env);
322	err = err ?: mark_stack_read(env, env->liveness->cur_instance, frame, insn_idx, mask);
323	return err;
324}
325
326static void reset_stack_write_marks(struct bpf_verifier_env *env,
327				    struct func_instance *instance, u32 insn_idx)
328{
329	struct bpf_liveness *liveness = env->liveness;
330	int i;
331
332	liveness->write_insn_idx = insn_idx;
333	for (i = 0; i <= instance->callchain.curframe; i++)
334		liveness->write_masks_acc[i] = 0;
335}
336
337int bpf_reset_stack_write_marks(struct bpf_verifier_env *env, u32 insn_idx)
338{
339	struct bpf_liveness *liveness = env->liveness;
340	int err;
341
342	err = ensure_cur_instance(env);
343	if (err)
344		return err;
345
346	reset_stack_write_marks(env, liveness->cur_instance, insn_idx);
347	return 0;
348}
349
350void bpf_mark_stack_write(struct bpf_verifier_env *env, u32 frame, u64 mask)
351{
352	env->liveness->write_masks_acc[frame] |= mask;
353}
354
355static int commit_stack_write_marks(struct bpf_verifier_env *env,
356				    struct func_instance *instance)
357{
358	struct bpf_liveness *liveness = env->liveness;
359	u32 idx, frame, curframe, old_must_write;
360	struct per_frame_masks *masks;
361	u64 mask;
362
363	if (!instance)
364		return 0;
365
366	curframe = instance->callchain.curframe;
367	idx = relative_idx(instance, liveness->write_insn_idx);
368	for (frame = 0; frame <= curframe; frame++) {
369		mask = liveness->write_masks_acc[frame];
370		/* avoid allocating frames for zero masks */
371		if (mask == 0 && !instance->must_write_set[idx])
372			continue;
373		masks = alloc_frame_masks(env, instance, frame, liveness->write_insn_idx);
374		if (IS_ERR(masks))
375			return PTR_ERR(masks);
376		old_must_write = masks->must_write;
377		/*
378		 * If instruction at this callchain is seen for a first time, set must_write equal
379		 * to @mask. Otherwise take intersection with the previous value.
380		 */
381		if (instance->must_write_set[idx])
382			mask &= old_must_write;
383		if (old_must_write != mask) {
384			masks->must_write = mask;
385			instance->updated = true;
386		}
387		if (old_must_write & ~mask)
388			instance->must_write_dropped = true;
389	}
390	instance->must_write_set[idx] = true;
391	liveness->write_insn_idx = 0;
392	return 0;
393}
394
395/*
396 * Merge stack writes marks in @env->liveness->write_masks_acc
397 * with information already in @env->liveness->cur_instance.
398 */
399int bpf_commit_stack_write_marks(struct bpf_verifier_env *env)
400{
401	return commit_stack_write_marks(env, env->liveness->cur_instance);
402}
403
404static char *fmt_callchain(struct bpf_verifier_env *env, struct callchain *callchain)
405{
406	char *buf_end = env->tmp_str_buf + sizeof(env->tmp_str_buf);
407	char *buf = env->tmp_str_buf;
408	int i;
409
410	buf += snprintf(buf, buf_end - buf, "(");
411	for (i = 0; i <= callchain->curframe; i++)
412		buf += snprintf(buf, buf_end - buf, "%s%d", i ? "," : "", callchain->callsites[i]);
413	snprintf(buf, buf_end - buf, ")");
414	return env->tmp_str_buf;
415}
416
417static void log_mask_change(struct bpf_verifier_env *env, struct callchain *callchain,
418			    char *pfx, u32 frame, u32 insn_idx, u64 old, u64 new)
419{
420	u64 changed_bits = old ^ new;
421	u64 new_ones = new & changed_bits;
422	u64 new_zeros = ~new & changed_bits;
423
424	if (!changed_bits)
425		return;
426	bpf_log(&env->log, "%s frame %d insn %d ", fmt_callchain(env, callchain), frame, insn_idx);
427	if (new_ones) {
428		bpf_fmt_stack_mask(env->tmp_str_buf, sizeof(env->tmp_str_buf), new_ones);
429		bpf_log(&env->log, "+%s %s ", pfx, env->tmp_str_buf);
430	}
431	if (new_zeros) {
432		bpf_fmt_stack_mask(env->tmp_str_buf, sizeof(env->tmp_str_buf), new_zeros);
433		bpf_log(&env->log, "-%s %s", pfx, env->tmp_str_buf);
434	}
435	bpf_log(&env->log, "\n");
436}
437
438int bpf_jmp_offset(struct bpf_insn *insn)
439{
440	u8 code = insn->code;
441
442	if (code == (BPF_JMP32 | BPF_JA))
443		return insn->imm;
444	return insn->off;
445}
446
447__diag_push();
448__diag_ignore_all("-Woverride-init", "Allow field initialization overrides for opcode_info_tbl");
449
450/*
451 * Returns an array of instructions succ, with succ->items[0], ...,
452 * succ->items[n-1] with successor instructions, where n=succ->cnt
453 */
454inline struct bpf_iarray *
455bpf_insn_successors(struct bpf_verifier_env *env, u32 idx)
456{
457	static const struct opcode_info {
458		bool can_jump;
459		bool can_fallthrough;
460	} opcode_info_tbl[256] = {
461		[0 ... 255] = {.can_jump = false, .can_fallthrough = true},
462	#define _J(code, ...) \
463		[BPF_JMP   | code] = __VA_ARGS__, \
464		[BPF_JMP32 | code] = __VA_ARGS__
465
466		_J(BPF_EXIT,  {.can_jump = false, .can_fallthrough = false}),
467		_J(BPF_JA,    {.can_jump = true,  .can_fallthrough = false}),
468		_J(BPF_JEQ,   {.can_jump = true,  .can_fallthrough = true}),
469		_J(BPF_JNE,   {.can_jump = true,  .can_fallthrough = true}),
470		_J(BPF_JLT,   {.can_jump = true,  .can_fallthrough = true}),
471		_J(BPF_JLE,   {.can_jump = true,  .can_fallthrough = true}),
472		_J(BPF_JGT,   {.can_jump = true,  .can_fallthrough = true}),
473		_J(BPF_JGE,   {.can_jump = true,  .can_fallthrough = true}),
474		_J(BPF_JSGT,  {.can_jump = true,  .can_fallthrough = true}),
475		_J(BPF_JSGE,  {.can_jump = true,  .can_fallthrough = true}),
476		_J(BPF_JSLT,  {.can_jump = true,  .can_fallthrough = true}),
477		_J(BPF_JSLE,  {.can_jump = true,  .can_fallthrough = true}),
478		_J(BPF_JCOND, {.can_jump = true,  .can_fallthrough = true}),
479		_J(BPF_JSET,  {.can_jump = true,  .can_fallthrough = true}),
480	#undef _J
481	};
482	struct bpf_prog *prog = env->prog;
483	struct bpf_insn *insn = &prog->insnsi[idx];
484	const struct opcode_info *opcode_info;
485	struct bpf_iarray *succ, *jt;
486	int insn_sz;
487
488	jt = env->insn_aux_data[idx].jt;
489	if (unlikely(jt))
490		return jt;
491
492	/* pre-allocated array of size up to 2; reset cnt, as it may have been used already */
493	succ = env->succ;
494	succ->cnt = 0;
495
496	opcode_info = &opcode_info_tbl[BPF_CLASS(insn->code) | BPF_OP(insn->code)];
497	insn_sz = bpf_is_ldimm64(insn) ? 2 : 1;
498	if (opcode_info->can_fallthrough)
499		succ->items[succ->cnt++] = idx + insn_sz;
500
501	if (opcode_info->can_jump)
502		succ->items[succ->cnt++] = idx + bpf_jmp_offset(insn) + 1;
503
504	return succ;
505}
506
507__diag_pop();
508
509static struct func_instance *get_outer_instance(struct bpf_verifier_env *env,
510						struct func_instance *instance)
511{
512	struct callchain callchain = instance->callchain;
513
514	/* Adjust @callchain to represent callchain one frame up */
515	callchain.callsites[callchain.curframe] = 0;
516	callchain.sp_starts[callchain.curframe] = 0;
517	callchain.curframe--;
518	callchain.callsites[callchain.curframe] = callchain.sp_starts[callchain.curframe];
519	return __lookup_instance(env, &callchain);
520}
521
522static u32 callchain_subprog_start(struct callchain *callchain)
523{
524	return callchain->sp_starts[callchain->curframe];
525}
526
527/*
528 * Transfer @may_read and @must_write_acc marks from the first instruction of @instance,
529 * to the call instruction in function instance calling @instance.
530 */
531static int propagate_to_outer_instance(struct bpf_verifier_env *env,
532				       struct func_instance *instance)
533{
534	struct callchain *callchain = &instance->callchain;
535	u32 this_subprog_start, callsite, frame;
536	struct func_instance *outer_instance;
537	struct per_frame_masks *insn;
538	int err;
539
540	this_subprog_start = callchain_subprog_start(callchain);
541	outer_instance = get_outer_instance(env, instance);
542	if (IS_ERR(outer_instance))
543		return PTR_ERR(outer_instance);
544	callsite = callchain->callsites[callchain->curframe - 1];
545
546	reset_stack_write_marks(env, outer_instance, callsite);
547	for (frame = 0; frame < callchain->curframe; frame++) {
548		insn = get_frame_masks(instance, frame, this_subprog_start);
549		if (!insn)
550			continue;
551		bpf_mark_stack_write(env, frame, insn->must_write_acc);
552		err = mark_stack_read(env, outer_instance, frame, callsite, insn->live_before);
553		if (err)
554			return err;
555	}
556	commit_stack_write_marks(env, outer_instance);
557	return 0;
558}
559
560static inline bool update_insn(struct bpf_verifier_env *env,
561			       struct func_instance *instance, u32 frame, u32 insn_idx)
562{
563	struct bpf_insn_aux_data *aux = env->insn_aux_data;
564	u64 new_before, new_after, must_write_acc;
565	struct per_frame_masks *insn, *succ_insn;
566	struct bpf_iarray *succ;
567	u32 s;
568	bool changed;
569
570	succ = bpf_insn_successors(env, insn_idx);
571	if (succ->cnt == 0)
572		return false;
573
574	changed = false;
575	insn = get_frame_masks(instance, frame, insn_idx);
576	new_before = 0;
577	new_after = 0;
578	/*
579	 * New "must_write_acc" is an intersection of all "must_write_acc"
580	 * of successors plus all "must_write" slots of instruction itself.
581	 */
582	must_write_acc = U64_MAX;
583	for (s = 0; s < succ->cnt; ++s) {
584		succ_insn = get_frame_masks(instance, frame, succ->items[s]);
585		new_after |= succ_insn->live_before;
586		must_write_acc &= succ_insn->must_write_acc;
587	}
588	must_write_acc |= insn->must_write;
589	/*
590	 * New "live_before" is a union of all "live_before" of successors
591	 * minus slots written by instruction plus slots read by instruction.
592	 */
593	new_before = (new_after & ~insn->must_write) | insn->may_read;
594	changed |= new_before != insn->live_before;
595	changed |= must_write_acc != insn->must_write_acc;
596	if (unlikely(env->log.level & BPF_LOG_LEVEL2) &&
597	    (insn->may_read || insn->must_write ||
598	     insn_idx == callchain_subprog_start(&instance->callchain) ||
599	     aux[insn_idx].prune_point)) {
600		log_mask_change(env, &instance->callchain, "live",
601				frame, insn_idx, insn->live_before, new_before);
602		log_mask_change(env, &instance->callchain, "written",
603				frame, insn_idx, insn->must_write_acc, must_write_acc);
604	}
605	insn->live_before = new_before;
606	insn->must_write_acc = must_write_acc;
607	return changed;
608}
609
610/* Fixed-point computation of @live_before and @must_write_acc marks */
611static int update_instance(struct bpf_verifier_env *env, struct func_instance *instance)
612{
613	u32 i, frame, po_start, po_end, cnt, this_subprog_start;
614	struct callchain *callchain = &instance->callchain;
615	int *insn_postorder = env->cfg.insn_postorder;
616	struct bpf_subprog_info *subprog;
617	struct per_frame_masks *insn;
618	bool changed;
619	int err;
620
621	this_subprog_start = callchain_subprog_start(callchain);
622	/*
623	 * If must_write marks were updated must_write_acc needs to be reset
624	 * (to account for the case when new must_write sets became smaller).
625	 */
626	if (instance->must_write_dropped) {
627		for (frame = 0; frame <= callchain->curframe; frame++) {
628			if (!instance->frames[frame])
629				continue;
630
631			for (i = 0; i < instance->insn_cnt; i++) {
632				insn = get_frame_masks(instance, frame, this_subprog_start + i);
633				insn->must_write_acc = 0;
634			}
635		}
636	}
637
638	subprog = bpf_find_containing_subprog(env, this_subprog_start);
639	po_start = subprog->postorder_start;
640	po_end = (subprog + 1)->postorder_start;
641	cnt = 0;
642	/* repeat until fixed point is reached */
643	do {
644		cnt++;
645		changed = false;
646		for (frame = 0; frame <= instance->callchain.curframe; frame++) {
647			if (!instance->frames[frame])
648				continue;
649
650			for (i = po_start; i < po_end; i++)
651				changed |= update_insn(env, instance, frame, insn_postorder[i]);
652		}
653	} while (changed);
654
655	if (env->log.level & BPF_LOG_LEVEL2)
656		bpf_log(&env->log, "%s live stack update done in %d iterations\n",
657			fmt_callchain(env, callchain), cnt);
658
659	/* transfer marks accumulated for outer frames to outer func instance (caller) */
660	if (callchain->curframe > 0) {
661		err = propagate_to_outer_instance(env, instance);
662		if (err)
663			return err;
664	}
665
666	return 0;
667}
668
669/*
670 * Prepare all callchains within @env->cur_state for querying.
671 * This function should be called after each verifier.c:pop_stack()
672 * and whenever verifier.c:do_check_insn() processes subprogram exit.
673 * This would guarantee that visited verifier states with zero branches
674 * have their bpf_mark_stack_{read,write}() effects propagated in
675 * @env->liveness.
676 */
677int bpf_update_live_stack(struct bpf_verifier_env *env)
678{
679	struct func_instance *instance;
680	int err, frame;
681
682	bpf_reset_live_stack_callchain(env);
683	for (frame = env->cur_state->curframe; frame >= 0; --frame) {
684		instance = lookup_instance(env, env->cur_state, frame);
685		if (IS_ERR(instance))
686			return PTR_ERR(instance);
687
688		if (instance->updated) {
689			err = update_instance(env, instance);
690			if (err)
691				return err;
692			instance->updated = false;
693			instance->must_write_dropped = false;
694		}
695	}
696	return 0;
697}
698
699static bool is_live_before(struct func_instance *instance, u32 insn_idx, u32 frameno, u32 spi)
700{
701	struct per_frame_masks *masks;
702
703	masks = get_frame_masks(instance, frameno, insn_idx);
704	return masks && (masks->live_before & BIT(spi));
705}
706
707int bpf_live_stack_query_init(struct bpf_verifier_env *env, struct bpf_verifier_state *st)
708{
709	struct live_stack_query *q = &env->liveness->live_stack_query;
710	struct func_instance *instance;
711	u32 frame;
712
713	memset(q, 0, sizeof(*q));
714	for (frame = 0; frame <= st->curframe; frame++) {
715		instance = lookup_instance(env, st, frame);
716		if (IS_ERR(instance))
717			return PTR_ERR(instance);
718		q->instances[frame] = instance;
719	}
720	q->curframe = st->curframe;
721	q->insn_idx = st->insn_idx;
722	return 0;
723}
724
725bool bpf_stack_slot_alive(struct bpf_verifier_env *env, u32 frameno, u32 spi)
726{
727	/*
728	 * Slot is alive if it is read before q->st->insn_idx in current func instance,
729	 * or if for some outer func instance:
730	 * - alive before callsite if callsite calls callback, otherwise
731	 * - alive after callsite
732	 */
733	struct live_stack_query *q = &env->liveness->live_stack_query;
734	struct func_instance *instance, *curframe_instance;
735	u32 i, callsite;
736	bool alive;
737
738	curframe_instance = q->instances[q->curframe];
739	if (is_live_before(curframe_instance, q->insn_idx, frameno, spi))
740		return true;
741
742	for (i = frameno; i < q->curframe; i++) {
743		callsite = curframe_instance->callchain.callsites[i];
744		instance = q->instances[i];
745		alive = bpf_calls_callback(env, callsite)
746			? is_live_before(instance, callsite, frameno, spi)
747			: is_live_before(instance, callsite + 1, frameno, spi);
748		if (alive)
749			return true;
750	}
751
752	return false;
753}