xref: /linux/include/linux/bpf_verifier.h (revision c16c6c4683cc57dd2736750da12e04f1f74a45e1)
1 /* SPDX-License-Identifier: GPL-2.0-only */
2 /* Copyright (c) 2011-2014 PLUMgrid, http://plumgrid.com
3  */
4 #ifndef _LINUX_BPF_VERIFIER_H
5 #define _LINUX_BPF_VERIFIER_H 1
6 
7 #include <linux/bpf.h> /* for enum bpf_reg_type */
8 #include <linux/btf.h> /* for struct btf and btf_id() */
9 #include <linux/filter.h> /* for MAX_BPF_STACK */
10 #include <linux/tnum.h>
11 #include <linux/cnum.h>
12 #include <linux/math64.h> /* for div_s64_rem() */
13 
14 /*
15  * Mathematical modulo, the residue of 'v' modulo 'step', normalized to [0, step).
16  * This differs from C's '%' operator, which truncates the quotient toward zero
17  * and so returns a remainder with the sign of the dividend (e.g. -1 % 3 == -1, not 2).
18  */
19 static inline u16 imod(s64 v, u16 step)
20 {
21 	s32 rem;
22 
23 	div_s64_rem(v, step, &rem);
24 	return rem < 0 ? rem + step : rem;
25 }
26 
27 /* Maximum variable offset umax_value permitted when resolving memory accesses.
28  * In practice this is far bigger than any realistic pointer offset; this limit
29  * ensures that umax_value + (int)off + (int)size cannot overflow a u64.
30  */
31 #define BPF_MAX_VAR_OFF	(1 << 29)
32 /* Maximum variable size permitted for ARG_MEM_SIZE[_OR_ZERO].  This ensures
33  * that converting umax_value to int cannot overflow.
34  */
35 #define BPF_MAX_VAR_SIZ	(1 << 29)
36 /*
37  * size of tmp_str_buf in bpf_verifier.
38  * we need at least 1399 bytes to fit full stack mask representation
39  * (in the "-8,-16,...,-2048" form)
40  */
41 #define TMP_STR_BUF_LEN 1408
42 /* Patch buffer size */
43 #define INSN_BUF_SIZE 32
44 
45 #define ITER_PREFIX "bpf_iter_"
46 
47 enum bpf_iter_state {
48 	BPF_ITER_STATE_INVALID, /* for non-first slot */
49 	BPF_ITER_STATE_ACTIVE,
50 	BPF_ITER_STATE_DRAINED,
51 };
52 
53 /* Bytes [off, off + size) of the stack of frame frameno. Nothing when size is 0. */
54 struct bpf_stack_range {
55 	u32 frameno;
56 	s32 off;
57 	u32 size;
58 };
59 
60 struct bpf_reg_state {
61 	/* Ordering of fields matters.  See states_equal() */
62 	enum bpf_reg_type type;
63 	/*
64 	 * Constant delta between "linked" scalars with the same ID.
65 	 */
66 	s32 delta;
67 	union {
68 		/* valid when type == PTR_TO_PACKET */
69 		int range;
70 		/*
71 		 * Valid when type == PTR_TO_STACK. Inside the callee two registers
72 		 * can be both PTR_TO_STACK like R1=fp-8 and R2=fp-8, but one of them
73 		 * points to this function stack while another to the caller's stack.
74 		 * To differentiate them 'frameno' is used which is an index in
75 		 * bpf_verifier_state->frame[] array pointing to bpf_func_state.
76 		 */
77 		u8 frameno;
78 
79 		/*
80 		 * For CONST_PTR_TO_MAP, PTR_TO_MAP_KEY, PTR_TO_MAP_VALUE and
81 		 * PTR_TO_INSN.
82 		 */
83 		struct bpf_map *map_ptr;
84 
85 		/* for PTR_TO_BTF_ID */
86 		struct {
87 			struct btf *btf;
88 			u32 btf_id;
89 		};
90 
91 		struct { /* for PTR_TO_MEM | PTR_TO_MEM_OR_NULL */
92 			u32 mem_size;
93 			/*
94 			 * bpf_dynptr_slice() and bpf_dynptr_slice_rdwr() return the
95 			 * buffer when the data is not contiguous: the register may
96 			 * point to this part of the stack.
97 			 */
98 			struct bpf_stack_range buf;
99 		};
100 
101 		/* For dynptr stack slots */
102 		struct {
103 			enum bpf_dynptr_type type;
104 			/* A dynptr is 16 bytes so it takes up 2 stack slots.
105 			 * We need to track which slot is the first slot
106 			 * to protect against cases where the user may try to
107 			 * pass in an address starting at the second slot of the
108 			 * dynptr.
109 			 */
110 			bool first_slot;
111 		} dynptr;
112 
113 		/* For bpf_iter stack slots */
114 		struct {
115 			/* BTF container and BTF type ID describing
116 			 * struct bpf_iter_<type> of an iterator state
117 			 */
118 			struct btf *btf;
119 			u32 btf_id;
120 			/* packing following two fields to fit iter state into 16 bytes */
121 			enum bpf_iter_state state:2;
122 			int depth:30;
123 		} iter;
124 
125 		/* For irq stack slots */
126 		struct {
127 			enum {
128 				IRQ_NATIVE_KFUNC,
129 				IRQ_LOCK_KFUNC,
130 			} kfunc_class;
131 		} irq;
132 
133 		/* Max size from any of the above. */
134 		struct {
135 			unsigned long raw1;
136 			unsigned long raw2;
137 		} raw;
138 
139 		u32 subprogno; /* for PTR_TO_FUNC */
140 	};
141 	/* For scalar types (SCALAR_VALUE), this represents our knowledge of
142 	 * the actual value.
143 	 * For pointer types, this represents the variable part of the offset
144 	 * from the pointed-to object, and is shared with all bpf_reg_states
145 	 * with the same id as us.
146 	 */
147 	struct tnum var_off;
148 	/* Used to determine if any memory access using this register will
149 	 * result in a bad access.
150 	 * These refer to the same value as var_off, not necessarily the actual
151 	 * contents of the register.
152 	 */
153 	struct cnum64 r64; /* 64-bit range as circular number */
154 	struct cnum32 r32; /* 32-bit range as circular number */
155 	/*
156 	 * The value described by this register, interpreted as s64, lies on
157 	 * a line described by a linear equation base + step * k.
158 	 * Invariant: base < step.
159 	 */
160 	u16 base;
161 	u16 step;
162 	/* For PTR_TO_PACKET, used to find other pointers with the same variable
163 	 * offset, so they can share range knowledge.
164 	 * For PTR_TO_MAP_VALUE_OR_NULL this is used to share which map value we
165 	 * came from, when one is tested for != NULL.
166 	 * For PTR_TO_MEM_OR_NULL this is used to identify memory allocation
167 	 * for the purpose of tracking that it's freed.
168 	 * For PTR_TO_SOCKET this is used to share which pointers retain the
169 	 * same reference to the socket, to determine proper reference freeing.
170 	 * For stack slots that are dynptrs, this is used to track references to
171 	 * the dynptr to determine proper reference freeing.
172 	 * Similarly to dynptrs, we use ID to track "belonging" of a reference
173 	 * to a specific instance of bpf_iter.
174 	 */
175 	/*
176 	 * Upper bit of ID is used to remember relationship between "linked"
177 	 * registers. Example:
178 	 * r1 = r2;    both will have r1->id == r2->id == N
179 	 * r1 += 10;   r1->id == N | BPF_ADD_CONST and r1->delta == 10
180 	 * r3 = r2;    both will have r3->id == r2->id == N
181 	 * w3 += 10;   r3->id == N | BPF_ADD_CONST32 and r3->delta == 10
182 	 */
183 #define BPF_ADD_CONST64 (1U << 31)
184 #define BPF_ADD_CONST32 (1U << 30)
185 #define BPF_ADD_CONST (BPF_ADD_CONST64 | BPF_ADD_CONST32)
186 	u32 id;
187 	/*
188 	 * Tracks the parent object this register was derived from.
189 	 * Used for cascading invalidation: when the parent object is
190 	 * released or invalidated, all registers with matching parent_id
191 	 * are also invalidated. For example, a slice from bpf_dynptr_data()
192 	 * gets parent_id set to the dynptr's id.
193 	 */
194 	u32 parent_id;
195 	/*
196 	 * Distinguishes inner-map lookups and their keys and values. Zero for
197 	 * other registers. Kept outside the metadata union for ID remapping
198 	 * during state comparisons.
199 	 */
200 	u32 map_uid:31;
201 	/* if (!precise && SCALAR_VALUE) min/max/tnum don't affect safety */
202 	u32 precise:1;
203 };
204 
205 static inline s64 reg_smin(const struct bpf_reg_state *reg)
206 {
207 	return cnum64_smin(reg->r64);
208 }
209 
210 static inline s64 reg_smax(const struct bpf_reg_state *reg)
211 {
212 	return cnum64_smax(reg->r64);
213 }
214 
215 static inline u64 reg_umin(const struct bpf_reg_state *reg)
216 {
217 	return cnum64_umin(reg->r64);
218 }
219 
220 static inline u64 reg_umax(const struct bpf_reg_state *reg)
221 {
222 	return cnum64_umax(reg->r64);
223 }
224 
225 static inline s32 reg_s32_min(const struct bpf_reg_state *reg)
226 {
227 	return cnum32_smin(reg->r32);
228 }
229 
230 static inline s32 reg_s32_max(const struct bpf_reg_state *reg)
231 {
232 	return cnum32_smax(reg->r32);
233 }
234 
235 static inline u32 reg_u32_min(const struct bpf_reg_state *reg)
236 {
237 	return cnum32_umin(reg->r32);
238 }
239 
240 static inline u32 reg_u32_max(const struct bpf_reg_state *reg)
241 {
242 	return cnum32_umax(reg->r32);
243 }
244 
245 static inline void reg_set_srange32(struct bpf_reg_state *reg, s32 smin, s32 smax)
246 {
247 	reg->r32 = cnum32_from_srange(smin, smax);
248 }
249 
250 static inline void reg_set_urange32(struct bpf_reg_state *reg, u32 umin, u32 umax)
251 {
252 	reg->r32 = cnum32_from_urange(umin, umax);
253 }
254 
255 static inline void reg_set_srange64(struct bpf_reg_state *reg, s64 smin, s64 smax)
256 {
257 	reg->r64 = cnum64_from_srange(smin, smax);
258 }
259 
260 static inline void reg_set_urange64(struct bpf_reg_state *reg, u64 umin, u64 umax)
261 {
262 	reg->r64 = cnum64_from_urange(umin, umax);
263 }
264 
265 enum bpf_stack_slot_type {
266 	STACK_INVALID,    /* nothing was stored in this stack slot */
267 	STACK_SPILL,      /* register spilled into stack */
268 	STACK_MISC,	  /* BPF program wrote some data into this slot */
269 	STACK_ZERO,	  /* BPF program wrote constant zero */
270 	/* A dynptr is stored in this stack slot. The type of dynptr
271 	 * is stored in bpf_stack_state->spilled_ptr.dynptr.type
272 	 */
273 	STACK_DYNPTR,
274 	STACK_ITER,
275 	STACK_IRQ_FLAG,
276 	STACK_POISON,
277 };
278 
279 #define BPF_REG_SIZE 8	/* size of eBPF register in bytes */
280 
281 /*
282  * Largest number of BPF_REG_SIZE stack slots a single frame can have, sized
283  * for the largest stack budget any JIT supports. A frame may use any part of
284  * its program's budget; check_max_stack_depth() enforces the budget on the
285  * combined depth of frames sharing the kernel stack and on each frame using
286  * a private stack.
287  */
288 #define MAX_BPF_STACK_SLOTS	(MAX_BPF_STACK_JIT / BPF_REG_SIZE)
289 
290 /* 4-byte stack slot granularity for liveness analysis */
291 #define BPF_HALF_REG_SIZE	4
292 #define STACK_SLOT_SZ		4
293 
294 #define BPF_REGMASK_ARGS ((1 << BPF_REG_1) | (1 << BPF_REG_2) | \
295 			  (1 << BPF_REG_3) | (1 << BPF_REG_4) | \
296 			  (1 << BPF_REG_5))
297 
298 #define BPF_MAIN_FUNC (-1)
299 
300 #define BPF_DYNPTR_SIZE		sizeof(struct bpf_dynptr_kern)
301 #define BPF_DYNPTR_NR_SLOTS		(BPF_DYNPTR_SIZE / BPF_REG_SIZE)
302 
303 struct bpf_stack_state {
304 	struct bpf_reg_state spilled_ptr;
305 	u8 slot_type[BPF_REG_SIZE];
306 };
307 
308 struct bpf_reference_state {
309 	/* Each reference object has a type. Ensure REF_TYPE_PTR is zero to
310 	 * default to pointer reference on zero initialization of a state.
311 	 */
312 	enum ref_state_type {
313 		REF_TYPE_PTR		= (1 << 1),
314 		REF_TYPE_IRQ		= (1 << 2),
315 		REF_TYPE_LOCK		= (1 << 3),
316 		REF_TYPE_RES_LOCK 	= (1 << 4),
317 		REF_TYPE_RES_LOCK_IRQ	= (1 << 5),
318 		REF_TYPE_LOCK_MASK	= REF_TYPE_LOCK | REF_TYPE_RES_LOCK | REF_TYPE_RES_LOCK_IRQ,
319 	} type;
320 	/* Track each reference created with a unique id, even if the same
321 	 * instruction creates the reference multiple times (eg, via CALL).
322 	 */
323 	int id;
324 	/* Instruction where the allocation of this reference occurred. This
325 	 * is used purely to inform the user of a reference leak.
326 	 */
327 	int insn_idx;
328 	union {
329 		/* For REF_TYPE_PTR */
330 		int parent_id;
331 		/* Use to keep track of the source object of a lock, to ensure
332 		 * it matches on unlock.
333 		 */
334 		void *ptr;
335 	};
336 };
337 
338 struct bpf_retval_range {
339 	s32 minval;
340 	s32 maxval;
341 	bool return_32bit;
342 };
343 
344 /* SCEV/widening register space: r0..r10 plus every stack slot of a frame. */
345 #define BPF_SCEV_REGS_NUM (MAX_BPF_REG + MAX_BPF_STACK_SLOTS)
346 
347 struct bpf_loop_iters {
348 	u32 min_header_count;   /* min number of times header is executed */
349 	u32 max_header_count;   /* max number of times header is executed */
350 	unsigned long precise_regs[BITS_TO_LONGS(BPF_SCEV_REGS_NUM)];
351 };
352 
353 struct loop_stack_entry {
354 	struct bpf_verifier_state *entry_state;
355 	u32 min_header_count;
356 	u32 max_header_count;
357 	u32 loop_id:31;
358 	u32 terminates:1;
359 };
360 
361 #define LOOP_STACK_SIZE 16
362 
363 /* state of the program:
364  * type of all registers and stack info
365  */
366 struct bpf_func_state {
367 	struct bpf_reg_state regs[MAX_BPF_REG];
368 	/* index of call instruction that called into this func */
369 	int callsite;
370 	/* stack frame number of this function state from pov of
371 	 * enclosing bpf_verifier_state.
372 	 * 0 = main function, 1 = first callee.
373 	 */
374 	u32 frameno;
375 	/*
376 	 * Unique diagnostic identity for this function invocation. Frame depth is
377 	 * reused after returns, while this ID is preserved across state clones.
378 	 */
379 	u32 diag_frame_id;
380 	/* subprog number == index within subprog_info
381 	 * zero == main subprog
382 	 */
383 	u32 subprogno;
384 	/* Every bpf_timer_start will increment async_entry_cnt.
385 	 * It's used to distinguish:
386 	 * void foo(void) { for(;;); }
387 	 * void foo(void) { bpf_timer_set_callback(,foo); }
388 	 */
389 	u32 async_entry_cnt;
390 	struct bpf_retval_range callback_ret_range;
391 	bool in_callback_fn;
392 	bool in_async_callback_fn;
393 	bool in_exception_callback_fn;
394 	bool no_stack_arg_load;
395 	/*
396 	 * The helper invokes this callback under rcu_read_lock(), so the
397 	 * callback and its callees run in an RCU read-side critical section.
398 	 */
399 	bool in_rcu_callback_fn;
400 	/* For callback calling functions that limit number of possible
401 	 * callback executions (e.g. bpf_loop) keeps track of current
402 	 * simulated iteration number.
403 	 * Value in frame N refers to number of times callback with frame
404 	 * N+1 was simulated, e.g. for the following call:
405 	 *
406 	 *   bpf_loop(..., fn, ...); | suppose current frame is N
407 	 *                           | fn would be simulated in frame N+1
408 	 *                           | number of simulations is tracked in frame N
409 	 */
410 	u32 callback_depth;
411 	/* Instructions processed in this frame and callees on the current path. */
412 	u32 insns_subtotal;
413 	/*
414 	 * Control-flow loop nesting at the current insn within this frame's
415 	 * subprogram (loops never cross subprogram boundaries).
416 	 */
417 	u32 loop_stack_cnt;
418 
419 	/* The following fields should be last. See copy_func_state() */
420 	/* The state of the stack. Each element of the array describes BPF_REG_SIZE
421 	 * (i.e. 8) bytes worth of stack memory.
422 	 * stack[0] represents bytes [*(r10-8)..*(r10-1)]
423 	 * stack[1] represents bytes [*(r10-16)..*(r10-9)]
424 	 * ...
425 	 * stack[allocated_stack/8 - 1] represents [*(r10-allocated_stack)..*(r10-allocated_stack+7)]
426 	 */
427 	struct bpf_stack_state *stack;
428 	/* Size of the current stack, in bytes. The stack state is tracked below, in
429 	 * `stack`. allocated_stack is always a multiple of BPF_REG_SIZE.
430 	 */
431 	int allocated_stack;
432 
433 	u16 out_stack_arg_cnt; /* Number of outgoing on-stack argument slots */
434 	struct bpf_reg_state *stack_arg_regs; /* Outgoing on-stack arguments */
435 	struct loop_stack_entry *loop_stack;
436 };
437 
438 #define MAX_CALL_FRAMES 16
439 
440 /* instruction history flags, used in bpf_jmp_history_entry.flags field.
441  * Frame number and SPI are stored in dedicated fields of bpf_jmp_history_entry.
442  */
443 enum {
444 	INSN_F_STACK_ACCESS = BIT(0),
445 
446 	INSN_F_DST_REG_STACK = BIT(1), /* dst_reg is PTR_TO_STACK */
447 	INSN_F_SRC_REG_STACK = BIT(2), /* src_reg is PTR_TO_STACK */
448 
449 	INSN_F_STACK_ARG_ACCESS = BIT(3),
450 };
451 
452 /* Registers linked to one jump condition that a history entry can record */
453 #define BPF_LINKED_REGS_MAX	5
454 
455 struct bpf_jmp_history_entry {
456 	/* insn idx can't be bigger than 1 million */
457 	u32 idx : 20;
458 	u32 frame : 4;	/* stack access frame number */
459 	/* special INSN_F_xxx flags */
460 	u32 flags : 4;
461 	u32 : 4;
462 	u32 prev_idx : 20;
463 	u32 spi : 12;	/* stack slot index */
464 	/*
465 	 * Scalar registers and spilled scalars linked to the condition of
466 	 * this jump, which need precision tracking together when the jump is
467 	 * backtracked. Each is packed as 4 bits of frame number, one bit
468 	 * telling a register from a stack slot and 11 bits of register or
469 	 * slot index, see linked_regs_pack().
470 	 */
471 	u16 linked_regs[BPF_LINKED_REGS_MAX];
472 	u8 linked_regs_cnt;
473 };
474 
475 static_assert(MAX_CALL_FRAMES <= (1 << 4));
476 static_assert(MAX_BPF_STACK_SLOTS <= (1 << 12));
477 
478 /* Maximum number of bpf_reg_state objects that can exist at once */
479 #define MAX_STACK_ARG_SLOTS (MAX_BPF_FUNC_ARGS - MAX_BPF_FUNC_REG_ARGS)
480 #define BPF_ID_MAP_SIZE ((MAX_BPF_REG + MAX_BPF_STACK_SLOTS + MAX_STACK_ARG_SLOTS) * \
481 			 MAX_CALL_FRAMES)
482 
483 struct bpf_verifier_state {
484 	/* call stack tracking */
485 	struct bpf_func_state *frame[MAX_CALL_FRAMES];
486 	struct bpf_verifier_state *parent;
487 	/* Acquired reference states */
488 	struct bpf_reference_state *refs;
489 	/*
490 	 * 'branches' field is the number of branches left to explore:
491 	 * 0 - all possible paths from this state reached bpf_exit or
492 	 * were safely pruned
493 	 * 1 - at least one path is being explored.
494 	 * This state hasn't reached bpf_exit
495 	 * 2 - at least two paths are being explored.
496 	 * This state is an immediate parent of two children.
497 	 * One is fallthrough branch with branches==1 and another
498 	 * state is pushed into stack (to be explored later) also with
499 	 * branches==1. The parent of this state has branches==1.
500 	 * The verifier state tree connected via 'parent' pointer looks like:
501 	 * 1
502 	 * 1
503 	 * 2 -> 1 (first 'if' pushed into stack)
504 	 * 1
505 	 * 2 -> 1 (second 'if' pushed into stack)
506 	 * 1
507 	 * 1
508 	 * 1 bpf_exit.
509 	 *
510 	 * Once do_check() reaches bpf_exit, it calls update_branch_counts()
511 	 * and the verifier state tree will look:
512 	 * 1
513 	 * 1
514 	 * 2 -> 1 (first 'if' pushed into stack)
515 	 * 1
516 	 * 1 -> 1 (second 'if' pushed into stack)
517 	 * 0
518 	 * 0
519 	 * 0 bpf_exit.
520 	 * After pop_stack() the do_check() will resume at second 'if'.
521 	 *
522 	 * If is_state_visited() sees a state with branches > 0 it means
523 	 * there is a loop. If such state is exactly equal to the current state
524 	 * it's an infinite loop. Note states_equal() checks for states
525 	 * equivalency, so two states being 'states_equal' does not mean
526 	 * infinite loop. The exact comparison is provided by
527 	 * states_maybe_looping() function. It's a stronger pre-check and
528 	 * much faster than states_equal().
529 	 *
530 	 * This algorithm may not find all possible infinite loops or
531 	 * loop iteration count may be too high.
532 	 * In such cases BPF_COMPLEXITY_LIMIT_INSNS limit kicks in.
533 	 */
534 	u32 branches;
535 	u32 insn_idx;
536 	u32 curframe;
537 
538 	u32 acquired_refs;
539 	u32 active_locks;
540 	u32 active_preempt_locks;
541 	u32 active_irq_id;
542 	u32 active_lock_id;
543 	void *active_lock_ptr;
544 	u32 active_rcu_locks;
545 
546 	bool speculative;
547 	bool in_sleepable;
548 	/* The callee left with unwind_exit. Next insn is unwind_goto. */
549 	bool unwound;
550 
551 	/*
552 	 * First and last insn idx of this verifier state.
553 	 * last_insn_idx is -1 if no instructions have been executed yet.
554 	 */
555 	u32 first_insn_idx;
556 	u32 last_insn_idx;
557 	/* if this state is a backedge state then equal_state
558 	 * records cached state to which this state is equal.
559 	 */
560 	struct bpf_verifier_state *equal_state;
561 	/* jmp history recorded from first to last.
562 	 * backtracking is using it to go from last to first.
563 	 * For most states jmp_history_cnt is [0-3].
564 	 * For loops can go up to ~40.
565 	 */
566 	struct bpf_jmp_history_entry *jmp_history;
567 	u32 jmp_history_cnt;
568 	u32 dfs_depth;
569 	u32 callback_unroll_depth;
570 	u32 may_goto_depth;
571 };
572 
573 /* Number of BPF_REG_SIZE stack slots tracked for the frame so far. */
574 static inline u32 bpf_stack_nr_slots(const struct bpf_func_state *frame)
575 {
576 	return frame->allocated_stack / BPF_REG_SIZE;
577 }
578 
579 /*
580  * Stack slot @spi of @frame, covering bytes [fp - (spi + 1) * 8, fp - spi * 8).
581  * The caller must ensure spi < bpf_stack_nr_slots(frame), see bpf_grow_stack_state().
582  */
583 static inline struct bpf_stack_state *bpf_stack_slot(const struct bpf_func_state *frame, u32 spi)
584 {
585 	return &frame->stack[spi];
586 }
587 
588 static inline struct bpf_reg_state *
589 bpf_get_spilled_reg(int slot, struct bpf_func_state *frame, u32 mask)
590 {
591 	struct bpf_stack_state *ss;
592 
593 	if (slot >= bpf_stack_nr_slots(frame))
594 		return NULL;
595 	ss = bpf_stack_slot(frame, slot);
596 	if ((1 << ss->slot_type[BPF_REG_SIZE - 1]) & mask)
597 		return &ss->spilled_ptr;
598 	return NULL;
599 }
600 
601 static inline struct bpf_reg_state *
602 bpf_get_spilled_stack_arg(int slot, struct bpf_func_state *frame)
603 {
604 	if (slot < frame->out_stack_arg_cnt &&
605 	    frame->stack_arg_regs[slot].type != NOT_INIT)
606 		return &frame->stack_arg_regs[slot];
607 	return NULL;
608 }
609 
610 /* Iterate over 'frame', setting 'reg' to either NULL or a spilled register. */
611 #define bpf_for_each_spilled_reg(iter, frame, reg, mask)			\
612 	for (iter = 0, reg = bpf_get_spilled_reg(iter, frame, mask);		\
613 	     iter < bpf_stack_nr_slots(frame);				\
614 	     iter++, reg = bpf_get_spilled_reg(iter, frame, mask))
615 
616 /* Iterate over 'frame', setting 'reg' to either NULL or a spilled stack arg. */
617 #define bpf_for_each_spilled_stack_arg(iter, frame, reg)               \
618 	for (iter = 0, reg = bpf_get_spilled_stack_arg(iter, frame);   \
619 	     iter < frame->out_stack_arg_cnt;                          \
620 	     iter++, reg = bpf_get_spilled_stack_arg(iter, frame))
621 
622 #define bpf_for_each_reg_in_vstate_mask(__vst, __state, __reg, __stack, __mask, __expr)   \
623 	({                                                               \
624 		struct bpf_verifier_state *___vstate = __vst;            \
625 		int ___i, ___j;                                          \
626 		for (___i = 0; ___i <= ___vstate->curframe; ___i++) {    \
627 			struct bpf_reg_state *___regs;                   \
628 			__state = ___vstate->frame[___i];                \
629 			___regs = __state->regs;                         \
630 			__stack = NULL;                                  \
631 			for (___j = 0; ___j < MAX_BPF_REG; ___j++) {     \
632 				__reg = &___regs[___j];                  \
633 				(void)(__expr);                          \
634 			}                                                \
635 			bpf_for_each_spilled_reg(___j, __state, __reg, __mask) { \
636 				if (!__reg)                              \
637 					continue;                        \
638 				__stack = bpf_stack_slot(__state, ___j); \
639 				(void)(__expr);                          \
640 			}                                                \
641 			__stack = NULL;                                  \
642 			bpf_for_each_spilled_stack_arg(___j, __state, __reg) { \
643 				if (!__reg)                              \
644 					continue;                        \
645 				(void)(__expr);                          \
646 			}						 \
647 		}                                                        \
648 		(void)__stack;                                           \
649 	})
650 
651 /* Invoke __expr over regsiters in __vst, setting __state and __reg */
652 #define bpf_for_each_reg_in_vstate(__vst, __state, __reg, __expr)		\
653 	({									\
654 		struct bpf_stack_state * ___stack;                        	\
655 		(void)___stack;							\
656 		bpf_for_each_reg_in_vstate_mask(__vst, __state, __reg, ___stack,\
657 						1 << STACK_SPILL, __expr);	\
658 	})
659 
660 /* linked list of verifier states used to prune search */
661 struct bpf_verifier_state_list {
662 	struct bpf_verifier_state state;
663 	struct list_head node;
664 	u32 miss_cnt;
665 	u32 hit_cnt:31;
666 	u32 in_free_list:1;
667 };
668 
669 struct bpf_loop_inline_state {
670 	unsigned int initialized:1; /* set to true upon first entry */
671 	unsigned int fit_for_inline:1; /* true if callback function is the same
672 					* at each call and flags are always zero
673 					*/
674 	u32 callback_subprogno; /* valid when fit_for_inline is true */
675 };
676 
677 /* pointer and state for maps */
678 struct bpf_map_ptr_state {
679 	struct bpf_map *map_ptr;
680 	bool poison;
681 	bool unpriv;
682 };
683 
684 /* Possible states for alu_state member. */
685 #define BPF_ALU_SANITIZE_SRC		(1U << 0)
686 #define BPF_ALU_SANITIZE_DST		(1U << 1)
687 #define BPF_ALU_NEG_VALUE		(1U << 2)
688 #define BPF_ALU_NON_POINTER		(1U << 3)
689 #define BPF_ALU_IMMEDIATE		(1U << 4)
690 #define BPF_ALU_SANITIZE		(BPF_ALU_SANITIZE_SRC | \
691 					 BPF_ALU_SANITIZE_DST)
692 
693 /*
694  * An array of BPF instructions.
695  * Primary usage: return value of bpf_insn_successors.
696  */
697 struct bpf_iarray {
698 	int cnt;
699 	u32 items[];
700 };
701 
702 #define iarray_for_each(item, arr)						\
703 	for (int ___idx = 0;							\
704 	     ___idx < (arr)->cnt && ({ item = (arr)->items[___idx]; 1; });	\
705 	     ___idx++)
706 
707 #define MAX_BACKEDGES 16
708 #define MAX_LOOP_EXITS 256
709 
710 /* Number of exit conditions dominating a backedge. */
711 #define MAX_LATCHES 4
712 
713 struct bpf_backedge {
714 	int from;
715 	/*
716 	 * Conditional jumps within the loop that dominate 'from' and have
717 	 * a successor outside the loop, nearest first. latches[0] is the
718 	 * latch; the remaining entries are additional exit conditions.
719 	 * Each usable condition gives an upper bound on the iteration count,
720 	 * so keeping only a subset is sound.
721 	 */
722 	int latches[MAX_LATCHES];
723 	u8 latches_cnt;
724 };
725 
726 struct bpf_loop_exit {
727 	int from; /* instruction inside the loop */
728 	int to; /* instruction outside the loop */
729 };
730 
731 struct bpf_loop {
732 	struct bpf_backedge backedges[MAX_BACKEDGES];
733 	/* edges exiting from this loop, includes edges from nested loops */
734 	struct bpf_loop_exit *exits;
735 	int backedges_cnt;
736 	int exits_cnt;
737 	bool irreducible;
738 	bool backedges_overflow;
739 	bool exits_overflow;
740 	/*
741 	 * Loop-entry registers used to compute stack addresses for loads,
742 	 * stores and calls requiring fixed stack offsets, in this and nested
743 	 * loops.
744 	 */
745 	unsigned long store_base_regs[BITS_TO_LONGS(BPF_SCEV_REGS_NUM)];
746 };
747 
748 struct bpf_insn_aux_data {
749 	union {
750 		enum bpf_reg_type ptr_type;	/* pointer type for load/store insns */
751 		struct bpf_map_ptr_state map_ptr_state;
752 		s32 call_imm;			/* saved imm field of call insn */
753 		u32 alu_limit;			/* limit for add/sub register with pointer */
754 		struct {
755 			u32 map_index;		/* index into used_maps[] */
756 			u32 map_off;		/* offset from value base address */
757 		};
758 		struct {
759 			enum bpf_reg_type reg_type;	/* type of pseudo_btf_id */
760 			union {
761 				struct {
762 					struct btf *btf;
763 					u32 btf_id;	/* btf_id for struct typed var */
764 				};
765 				u32 mem_size;	/* mem_size for non-struct typed var */
766 			};
767 		} btf_var;
768 		/* if instruction is a call to bpf_loop this field tracks
769 		 * the state of the relevant registers to make decision about inlining
770 		 */
771 		struct bpf_loop_inline_state loop_inline_state;
772 	};
773 	union {
774 		/* remember the size of type passed to bpf_obj_new to rewrite R1 */
775 		u64 obj_new_size;
776 		/* remember the offset of node field within type to rewrite */
777 		u64 insert_off;
778 	};
779 	struct btf_struct_meta *kptr_struct_meta;
780 	u64 map_key_state; /* constant (32 bit) key tracking for maps */
781 	/*
782 	 * Per-instruction summary of stack slots in the current frame
783 	 * that this instruction may write to.
784 	 */
785 	DECLARE_BITMAP(may_write_mask, MAX_BPF_STACK_SLOTS);
786 	DECLARE_BITMAP(live_stack_before, MAX_BPF_STACK_SLOTS);
787 	u16 stack_ptrs; /* bitmask of regs that may hold a frame pointer here (arg_track) */
788 	int ctx_field_size; /* the ctx field size for load insn, maybe 0 */
789 	u32 seen; /* this insn was processed by the verifier at env->pass_cnt */
790 	u64 nospec:1; /* do not execute this instruction speculatively */
791 	u64 nospec_result:1; /* result is unsafe under speculation, nospec must follow */
792 	u64 zext_dst:1; /* this insn zero extends dst reg */
793 	u64 needs_zext:1; /* alu op needs to clear upper bits */
794 	u64 prevent_zext:1; /* alu op cannot be zext (already used with 64-bit scalars) */
795 	u64 non_sleepable:1; /* helper/kfunc may be called from non-sleepable context */
796 	u64 is_iter_next:1; /* bpf_iter_<type>_next() kfunc call */
797 	u64 call_with_percpu_alloc_ptr:1; /* {this,per}_cpu_ptr() with prog percpu alloc */
798 	u64 bb_end:1; /* last instruction of a basic block */
799 	u64 need_scev:1;
800 	u64 alu_state:5; /* used in combination with alu_limit */
801 	/* true if STX or LDX instruction is a part of a spill/fill
802 	 * pattern for a bpf_fastcall call.
803 	 */
804 	u64 fastcall_pattern:1;
805 	/* for CALL instructions, a number of spill/fill pairs in the
806 	 * bpf_fastcall pattern.
807 	 */
808 	u64 fastcall_spills_num:3;
809 	u64 arg_prog:4;
810 	/*
811 	 * What a load found, on any path: an __arena pointer member of a
812 	 * kernel struct, which arena_member_fixup() rewrites, one that is
813 	 * __nullable as well, or anything else through any pointer.
814 	 */
815 	u64 arena_member:1;
816 	u64 arena_member_nullable:1;
817 	u64 non_arena_load:1;
818 
819 	/* below flags are initialized once */
820 	u64 jmp_point:1;
821 	u64 prune_point:1;
822 	/* ensure we check state equivalence and save state checkpoint and
823 	 * this instruction, regardless of any heuristics
824 	 */
825 	u64 force_checkpoint:1;
826 	/* true if instruction is a call to a helper function that
827 	 * accepts callback function as a parameter.
828 	 */
829 	u64 calls_callback:1;
830 	u64 indirect_target:1; /* if it is an indirect jump target */
831 	u64 non_stack_access:1; /* instruction can access non-stack memory */
832 	/* true if some jump or call instruction targets this instruction */
833 	u64 jump_target:1;
834 
835 	unsigned int orig_idx; /* original instruction index, initialized once */
836 	/*
837 	 * CFG strongly connected component this instruction belongs to,
838 	 * zero if it is a singleton SCC.
839 	 */
840 	u32 scc;
841 	/* registers alive before this instruction. */
842 	u16 live_regs_before;
843 	/*
844 	 * Bitmask of R0-R9 that hold known values at this instruction.
845 	 * const_reg_mask: scalar constants that fit in 32 bits.
846 	 * const_reg_map_mask: map pointers, val is map_index into used_maps[].
847 	 * const_reg_subprog_mask: subprog pointers, val is subprog number.
848 	 * const_reg_vals[i] holds the 32-bit value for register i.
849 	 * Populated by compute_const_regs() pre-pass.
850 	 */
851 	u16 const_reg_mask;
852 	u16 const_reg_map_mask;
853 	u16 const_reg_subprog_mask;
854 	u32 const_reg_vals[10];
855 	/*
856 	 * Header index of the innermost loop containing this instruction, -1 if none.
857 	 * For a loop header, identifies the parent loop instead.
858 	 */
859 	s32 loop_header;
860 	/* additional information about the loop if this instruction is a loop header */
861 	struct bpf_loop *loop;
862 };
863 
864 #define MAX_USED_MAPS 64 /* max number of maps accessed by one eBPF program */
865 #define MAX_USED_BTFS 64 /* max number of BTFs accessed by one BPF program */
866 
867 /*
868  * Longest line the verifier log can carry: a full stack mask of
869  * MAX_BPF_STACK_SLOTS slots, see TMP_STR_BUF_LEN, plus its prefix.
870  */
871 #define BPF_VERIFIER_TMP_LOG_SIZE	2048
872 
873 struct bpf_verifier_log {
874 	/* Logical start and end positions of a "log window" of the verifier log.
875 	 * start_pos == 0 means we haven't truncated anything.
876 	 * Once truncation starts to happen, start_pos + len_total == end_pos,
877 	 * except during log reset situations, in which (end_pos - start_pos)
878 	 * might get smaller than len_total (see bpf_vlog_reset()).
879 	 * Generally, (end_pos - start_pos) gives number of useful data in
880 	 * user log buffer.
881 	 */
882 	u64 start_pos;
883 	u64 end_pos;
884 	char __user *ubuf;
885 	u32 level;
886 	u32 len_total;
887 	u32 len_max;
888 	char kbuf[BPF_VERIFIER_TMP_LOG_SIZE];
889 };
890 
891 #define BPF_LOG_LEVEL1	1
892 #define BPF_LOG_LEVEL2	2
893 #define BPF_LOG_STATS	4
894 #define BPF_LOG_FIXED	8
895 #define BPF_LOG_LEVEL	(BPF_LOG_LEVEL1 | BPF_LOG_LEVEL2)
896 #define BPF_LOG_MASK	(BPF_LOG_LEVEL | BPF_LOG_STATS | BPF_LOG_FIXED)
897 #define BPF_LOG_KERNEL	(BPF_LOG_MASK + 1) /* kernel internal flag */
898 #define BPF_LOG_MIN_ALIGNMENT 8U
899 #define BPF_LOG_ALIGNMENT 40U
900 
901 static inline bool bpf_verifier_log_needed(const struct bpf_verifier_log *log)
902 {
903 	return log && log->level;
904 }
905 
906 struct bpf_log_attr {
907 	char __user *ubuf;
908 	u32 size;
909 	u32 level;
910 	u32 offsetof_true_size;
911 	bpfptr_t uattr;
912 };
913 
914 int bpf_log_attr_init(struct bpf_log_attr *log, u64 log_buf, u32 log_size, u32 log_level,
915 		      u32 offsetof_log_true_size, bpfptr_t uattr, struct bpf_common_attr *common,
916 		      bpfptr_t uattr_common, u32 size_common);
917 struct bpf_verifier_log *bpf_log_attr_create_vlog(struct bpf_log_attr *attr_log,
918 						  struct bpf_common_attr *common, bpfptr_t uattr,
919 						  u32 size);
920 int bpf_log_attr_finalize(struct bpf_log_attr *attr, struct bpf_verifier_log *log);
921 
922 #define BPF_MAX_SUBPROGS 256
923 
924 /*
925  * A pointer to a static subprog in the value of a frozen read-only array map:
926  * a 64-bit value that is the offset in bytes of the first instruction of
927  * the subprog in the program.
928  */
929 struct bpf_func_ptr {
930 	struct bpf_map *map;
931 	u32 map_off;		/* offset of the pointer in the value of the map */
932 	u32 orig_off;		/* what the map has: the first instruction of the subprog */
933 	u32 xlated_off;		/* the same after instructions were patched and removed */
934 };
935 
936 /* the subprog that a bpf_func_ptr pointed to was removed as dead code */
937 #define BPF_FUNC_PTR_DELETED ((u32)-1)
938 
939 enum priv_stack_mode {
940 	PRIV_STACK_UNKNOWN,
941 	NO_PRIV_STACK,
942 	PRIV_STACK_ADAPTIVE,
943 };
944 
945 struct bpf_subprog_info {
946 	const char *name; /* name extracted from BTF */
947 	u32 start; /* insn idx of function entry point */
948 	u32 linfo_idx; /* The idx to the main_prog->aux->linfo */
949 	u32 postorder_start; /* The idx to the env->cfg.insn_postorder */
950 	/*
951 	 * Index of one of the BPF_EXIT instructions in this subprogram, or
952 	 * U32_MAX when it has none.
953 	 */
954 	u32 exit_idx;
955 	struct bpf_iarray *jt; /* jump table shared by all gotox of this subprogram */
956 	u16 stack_depth; /* max. stack depth used by this function */
957 	u16 stack_extra;
958 	u32 insns_total;
959 	u32 insns_self;
960 	/* offsets in range [stack_depth .. fastcall_stack_off)
961 	 * are used for bpf_fastcall spills and fills.
962 	 */
963 	s16 fastcall_stack_off;
964 	bool has_tail_call: 1;
965 	bool might_throw: 1;
966 	bool can_unwind: 1; /* has unwind_exit */
967 	bool tail_call_reachable: 1;
968 	bool has_ld_abs: 1;
969 	bool is_cb: 1;
970 	bool is_async_cb: 1;
971 	bool is_exception_cb: 1;
972 	/* bpf_loop() or bpf_for_each_map_elem() call it in a loop */
973 	bool is_loop_cb: 1;
974 	/* BPF code, another helper or a kfunc call it */
975 	bool is_called: 1;
976 	bool args_cached: 1;
977 	/* true if the return value is passed in the R0:R2 register pair */
978 	bool ret_reg_pair: 1;
979 	/* true if bpf_fastcall stack region is used by functions that can't be inlined */
980 	bool keep_fastcall_stack: 1;
981 	bool changes_pkt_data: 1;
982 	bool might_sleep: 1;
983 	u8 arg_slot_cnt:4;
984 
985 	enum priv_stack_mode priv_stack_mode;
986 	struct bpf_subprog_arg_info args[MAX_BPF_FUNC_ARGS];
987 	u16 stack_arg_cnt; /* incoming + max outgoing */
988 	u16 max_out_stack_arg_cnt;
989 };
990 
991 static inline u16 bpf_in_stack_arg_cnt(const struct bpf_subprog_info *sub)
992 {
993 	if (sub->arg_slot_cnt > MAX_BPF_FUNC_REG_ARGS)
994 		return sub->arg_slot_cnt - MAX_BPF_FUNC_REG_ARGS;
995 	return 0;
996 }
997 
998 struct bpf_diag;
999 struct bpf_verifier_env;
1000 
1001 struct backtrack_state {
1002 	struct bpf_verifier_env *env;
1003 	u32 frame;
1004 	u32 reg_masks[MAX_CALL_FRAMES];
1005 	unsigned long stack_masks[MAX_CALL_FRAMES][BITS_TO_LONGS(MAX_BPF_STACK_SLOTS)];
1006 	u8 stack_arg_masks[MAX_CALL_FRAMES];
1007 };
1008 
1009 struct bpf_id_pair {
1010 	u32 old;
1011 	u32 cur;
1012 };
1013 
1014 struct bpf_idmap {
1015 	u32 tmp_id_gen;
1016 	u32 cnt;
1017 	struct bpf_id_pair map[BPF_ID_MAP_SIZE];
1018 };
1019 
1020 struct bpf_idset {
1021 	u32 num_ids;
1022 	struct {
1023 		u32 id;
1024 		u32 cnt;
1025 	} entries[BPF_ID_MAP_SIZE];
1026 };
1027 
1028 /* see verifier.c:compute_scc_callchain() */
1029 struct bpf_scc_callchain {
1030 	/* call sites from bpf_verifier_state->frame[*]->callsite leading to this SCC */
1031 	u32 callsites[MAX_CALL_FRAMES - 1];
1032 	/* last frame in a chain is identified by SCC id */
1033 	u32 scc;
1034 };
1035 
1036 /* verifier state waiting for propagate_backedges() */
1037 struct bpf_scc_backedge {
1038 	struct bpf_scc_backedge *next;
1039 	struct bpf_verifier_state state;
1040 };
1041 
1042 struct bpf_scc_visit {
1043 	struct bpf_scc_callchain callchain;
1044 	/* first state in current verification path that entered SCC
1045 	 * identified by the callchain
1046 	 */
1047 	struct bpf_verifier_state *entry_state;
1048 	struct bpf_scc_backedge *backedges; /* list of backedges */
1049 	u32 num_backedges;
1050 };
1051 
1052 /* An array of bpf_scc_visit structs sharing tht same bpf_scc_callchain->scc
1053  * but having different bpf_scc_callchain->callsites.
1054  */
1055 struct bpf_scc_info {
1056 	u32 num_visits;
1057 	struct bpf_scc_visit visits[];
1058 };
1059 
1060 struct bpf_liveness;
1061 struct scev;
1062 
1063 struct bpf_fd_array {
1064 	union {
1065 		struct bpf_map *map;
1066 		struct btf *btf;
1067 		unsigned long val;
1068 	};
1069 };
1070 
1071 /* single container for all structs
1072  * one verifier_env per bpf_check() call
1073  */
1074 struct bpf_verifier_env {
1075 	u32 insn_idx;
1076 	u32 prev_insn_idx;
1077 	struct bpf_prog *prog;		/* eBPF program being verified */
1078 	const struct bpf_verifier_ops *ops;
1079 	struct module *attach_btf_mod;	/* The owner module of prog->aux->attach_btf */
1080 	struct bpf_verifier_stack_elem *head; /* stack of verifier states to be processed */
1081 	int stack_size;			/* number of states to be processed */
1082 	bool strict_alignment;		/* perform strict pointer alignment checks */
1083 	bool test_state_freq;		/* test verifier with different pruning frequency */
1084 	bool test_reg_invariants;	/* fail verification on register invariants violations */
1085 	struct bpf_verifier_state *cur_state; /* current verifier state */
1086 	/* Search pruning optimization, array of list_heads for
1087 	 * lists of struct bpf_verifier_state_list.
1088 	 */
1089 	struct list_head *explored_states;
1090 	struct list_head free_list;	/* list of struct bpf_verifier_state_list */
1091 	struct bpf_map *used_maps[MAX_USED_MAPS]; /* array of map's used by eBPF program */
1092 	struct btf_mod_pair used_btfs[MAX_USED_BTFS]; /* array of BTF's used by BPF program */
1093 	struct bpf_map *insn_array_maps[MAX_USED_MAPS]; /* array of INSN_ARRAY map's to be relocated */
1094 	u32 used_map_cnt;		/* number of used maps */
1095 	u32 used_btf_cnt;		/* number of used BTF objects */
1096 	u32 insn_array_map_cnt;		/* number of used maps of type BPF_MAP_TYPE_INSN_ARRAY */
1097 	u32 id_gen;			/* used to generate unique reg IDs */
1098 	u32 hidden_subprog_cnt;		/* number of hidden subprogs */
1099 	int exception_callback_subprog;
1100 	bool explore_alu_limits;
1101 	bool allow_ptr_leaks;
1102 	/* Allow access to uninitialized stack memory. Writes with fixed offset are
1103 	 * always allowed, so this refers to reads (with fixed or variable offset),
1104 	 * to writes with variable offset and to indirect (helper) accesses.
1105 	 */
1106 	bool allow_uninit_stack;
1107 	bool bpf_capable;
1108 	bool bypass_spec_v1;
1109 	bool bypass_spec_v4;
1110 	bool seen_direct_write;
1111 	/* a register may point to the stack and is not PTR_TO_STACK, see bpf_reg_state::buf */
1112 	bool seen_stack_slice;
1113 	/* a global function is verified for BPF_FUNC_CTX_NO_RCU_LOCK */
1114 	bool no_rcu_read_lock;
1115 	bool seen_exception;
1116 	bool signature;
1117 	u32 insn_aux_data_len;
1118 	struct bpf_insn_aux_data *insn_aux_data; /* array of per-insn state */
1119 	const struct bpf_line_info *prev_linfo;
1120 	struct bpf_verifier_log log;
1121 	struct bpf_diag *diag;
1122 	struct bpf_func_proto bpf_subprog_scratch;
1123 	struct bpf_subprog_info subprog_info[BPF_MAX_SUBPROGS + 2]; /* max + 2 for the fake and exception subprogs */
1124 	/* subprog indices sorted in topological order: leaves first, callers last */
1125 	int subprog_topo_order[BPF_MAX_SUBPROGS + 2];
1126 	/*
1127 	 * Pointers to static subprogs found in frozen read-only maps of the
1128 	 * program, see resolve_func_ptrs(). Sorted by map and map_off.
1129 	 */
1130 	struct bpf_func_ptr *func_ptrs;
1131 	u32 func_ptr_cnt;
1132 	bool has_callx;
1133 	/*
1134 	 * Call graph edges created by callx instructions. A bitmap of
1135 	 * subprog_cnt * subprog_cnt bits, where bit (caller * subprog_cnt + callee)
1136 	 * is set when the main verification pass sees 'caller' calling 'callee'
1137 	 * via callx. Allocated when the first such edge is recorded.
1138 	 */
1139 	unsigned long *callx_edges;
1140 	union {
1141 		struct bpf_idmap idmap_scratch;
1142 		struct bpf_idset idset_scratch;
1143 	};
1144 	struct {
1145 		int *insn_state;
1146 		int *insn_stack;
1147 		/*
1148 		 * vector of instruction indexes sorted in post-order, grouped by subprogram,
1149 		 * see bpf_subprog_info->postorder_start.
1150 		 */
1151 		int *insn_postorder;
1152 		int *postorder_nums;
1153 		int cur_stack;
1154 		/* current position in the insn_postorder vector */
1155 		int cur_postorder;
1156 		u32 gotox_edges;
1157 		bool subprog_jts_ready;
1158 	} cfg;
1159 	struct backtrack_state bt;
1160 	struct bpf_jmp_history_entry *cur_hist_ent;
1161 	/* Per-callsite snapshot of the parent's tracked spill slots for cross-frame fills. */
1162 	struct spill_snapshot **callsite_at_stack;
1163 	u32 pass_cnt; /* number of times do_check() was called */
1164 	u32 subprog_cnt;
1165 	/* number of instructions analyzed by the verifier */
1166 	u32 prev_insn_processed, insn_processed;
1167 	/* number of jmps, calls, exits analyzed so far */
1168 	u32 prev_jmps_processed, jmps_processed;
1169 	/* maximum combined stack depth */
1170 	u32 max_stack_depth;
1171 	/* stack budget of the program, see bpf_prog_stack_limit() */
1172 	u32 stack_limit;
1173 	/* total verification time */
1174 	u64 verification_time;
1175 	/* maximum number of verifier states kept in 'branching' instructions */
1176 	u32 max_states_per_insn;
1177 	/* total number of allocated verifier states */
1178 	u32 total_states;
1179 	/* some states are freed during program analysis.
1180 	 * this is peak number of states. this number dominates kernel
1181 	 * memory consumption during verification
1182 	 */
1183 	u32 peak_states;
1184 	/* longest register parentage chain walked for liveness marking */
1185 	u32 longest_mark_read_walk;
1186 	u32 free_list_size;
1187 	u32 explored_states_size;
1188 	u32 num_backedges;
1189 	/*
1190 	 * The program's fd_array comes in two shapes, told apart by whether
1191 	 * the caller passed fd_array_cnt. They are mutually exclusive:
1192 	 *  - continuous (fd_array_cnt given): ->fd_array holds every entry
1193 	 *    resolved to its object up front, indexed by fd_array position,
1194 	 *    with ->fd_array_cnt slots; ->fd_array_raw is unused.
1195 	 *  - sparse (no fd_array_cnt): ->fd_array is NULL, and entries are
1196 	 *    read from ->fd_array_raw (the caller's fd_array) and resolved
1197 	 *    on the spot at each reference.
1198 	 */
1199 	struct bpf_fd_array *fd_array;
1200 	u32 fd_array_cnt;
1201 	bpfptr_t fd_array_raw;
1202 
1203 	/* bit mask to keep track of whether a register has been accessed
1204 	 * since the last time the function state was printed
1205 	 */
1206 	u32 scratched_regs;
1207 	/* Same as scratched_regs but for stack slots */
1208 	DECLARE_BITMAP(scratched_stack_slots, MAX_BPF_STACK_SLOTS);
1209 	u64 prev_log_pos, prev_insn_print_pos;
1210 	/* buffer used to temporary hold constants as scalar registers */
1211 	struct bpf_reg_state fake_reg[1];
1212 	/* buffers used to save updated reg states while simulating branches */
1213 	struct bpf_reg_state true_reg1, true_reg2, false_reg1, false_reg2;
1214 	/* buffer used to generate temporary string representations,
1215 	 * e.g., in reg_type_str() to generate reg_type string
1216 	 */
1217 	char tmp_str_buf[TMP_STR_BUF_LEN];
1218 	char tmp_arg_name[32];
1219 	struct bpf_insn insn_buf[INSN_BUF_SIZE];
1220 	struct bpf_insn epilogue_buf[INSN_BUF_SIZE];
1221 	struct bpf_scc_callchain callchain_buf;
1222 	struct bpf_liveness *liveness;
1223 	/* array of pointers to bpf_scc_info indexed by SCC id */
1224 	struct bpf_scc_info **scc_info;
1225 	u32 scc_cnt;
1226 	struct bpf_iarray *succ;
1227 	struct bpf_iarray *gotox_tmp_buf;
1228 	int *idoms;
1229 	struct scev *scev;
1230 };
1231 
1232 static inline struct bpf_func_info_aux *subprog_aux(struct bpf_verifier_env *env, int subprog)
1233 {
1234 	return &env->prog->aux->func_info_aux[subprog];
1235 }
1236 
1237 static inline struct bpf_subprog_info *subprog_info(struct bpf_verifier_env *env, int subprog)
1238 {
1239 	return &env->subprog_info[subprog];
1240 }
1241 
1242 static inline bool bpf_ret_reg_pair(struct bpf_verifier_env *env, int subprog)
1243 {
1244 	return subprog_info(env, subprog)->ret_reg_pair;
1245 }
1246 
1247 struct bpf_call_summary {
1248 	u8 arg_slot_cnt;
1249 	bool is_void;
1250 	bool fastcall;
1251 };
1252 
1253 static inline bool bpf_helper_call(const struct bpf_insn *insn)
1254 {
1255 	return insn->code == (BPF_JMP | BPF_CALL) &&
1256 	       insn->src_reg == 0;
1257 }
1258 
1259 static inline bool bpf_pseudo_call(const struct bpf_insn *insn)
1260 {
1261 	return insn->code == (BPF_JMP | BPF_CALL) &&
1262 	       insn->src_reg == BPF_PSEUDO_CALL;
1263 }
1264 
1265 static inline bool bpf_pseudo_kfunc_call(const struct bpf_insn *insn)
1266 {
1267 	return insn->code == (BPF_JMP | BPF_CALL) &&
1268 	       insn->src_reg == BPF_PSEUDO_KFUNC_CALL;
1269 }
1270 
1271 /* callx: indirect call of a bpf subprog whose address is in insn->dst_reg */
1272 static inline bool bpf_is_callx(const struct bpf_insn *insn)
1273 {
1274 	return insn->code == (BPF_JMP | BPF_CALL | BPF_X);
1275 }
1276 
1277 __printf(2, 0) void bpf_verifier_vlog(struct bpf_verifier_log *log,
1278 				      const char *fmt, va_list args);
1279 __printf(2, 3) void bpf_verifier_log_write(struct bpf_verifier_env *env,
1280 					   const char *fmt, ...);
1281 __printf(2, 3) void bpf_log(struct bpf_verifier_log *log,
1282 			    const char *fmt, ...);
1283 int bpf_vlog_init(struct bpf_verifier_log *log, u32 log_level,
1284 		  char __user *log_buf, u32 log_size);
1285 void bpf_vlog_reset(struct bpf_verifier_log *log, u64 new_pos);
1286 int bpf_vlog_finalize(struct bpf_verifier_log *log, u32 *log_size_actual);
1287 
1288 __printf(3, 4) void verbose_linfo(struct bpf_verifier_env *env,
1289 				  u32 insn_off,
1290 				  const char *prefix_fmt, ...);
1291 void bpf_verbose_snum(struct bpf_verifier_env *env, s64 num);
1292 void bpf_verbose_snum32(struct bpf_verifier_env *env, s32 num);
1293 
1294 #define verifier_bug_if(cond, env, fmt, args...)						\
1295 	({											\
1296 		bool __cond = (cond);								\
1297 		if (unlikely(__cond))								\
1298 			verifier_bug(env, fmt " (" #cond ")", ##args);				\
1299 		(__cond);									\
1300 	})
1301 #define verifier_bug(env, fmt, args...)								\
1302 	({											\
1303 		BPF_WARN_ONCE(1, "verifier bug: " fmt "\n", ##args);				\
1304 		bpf_log(&env->log, "verifier bug: " fmt "\n", ##args);				\
1305 	})
1306 
1307 static inline void mark_prune_point(struct bpf_verifier_env *env, int idx)
1308 {
1309 	env->insn_aux_data[idx].prune_point = true;
1310 }
1311 
1312 static inline bool bpf_is_prune_point(struct bpf_verifier_env *env, int insn_idx)
1313 {
1314 	return env->insn_aux_data[insn_idx].prune_point;
1315 }
1316 
1317 static inline void mark_force_checkpoint(struct bpf_verifier_env *env, int idx)
1318 {
1319 	env->insn_aux_data[idx].force_checkpoint = true;
1320 }
1321 
1322 static inline bool bpf_is_force_checkpoint(struct bpf_verifier_env *env, int insn_idx)
1323 {
1324 	return env->insn_aux_data[insn_idx].force_checkpoint;
1325 }
1326 
1327 static inline void clear_scalar_id(struct bpf_reg_state *reg)
1328 {
1329 	reg->id = 0;
1330 	reg->delta = 0;
1331 }
1332 
1333 static inline void mark_calls_callback(struct bpf_verifier_env *env, int idx)
1334 {
1335 	env->insn_aux_data[idx].calls_callback = true;
1336 }
1337 
1338 static inline bool bpf_calls_callback(struct bpf_verifier_env *env, int insn_idx)
1339 {
1340 	return env->insn_aux_data[insn_idx].calls_callback;
1341 }
1342 
1343 static inline void mark_jmp_point(struct bpf_verifier_env *env, int idx)
1344 {
1345 	env->insn_aux_data[idx].jmp_point = true;
1346 }
1347 
1348 static inline void mark_jump_target(struct bpf_verifier_env *env, int idx)
1349 {
1350 	env->insn_aux_data[idx].jump_target = true;
1351 }
1352 
1353 static inline bool bpf_is_jump_target(struct bpf_verifier_env *env, int insn_idx)
1354 {
1355 	return env->insn_aux_data[insn_idx].jump_target;
1356 }
1357 
1358 static inline struct bpf_func_state *cur_func(struct bpf_verifier_env *env)
1359 {
1360 	struct bpf_verifier_state *cur = env->cur_state;
1361 
1362 	return cur->frame[cur->curframe];
1363 }
1364 
1365 static inline struct bpf_reg_state *cur_regs(struct bpf_verifier_env *env)
1366 {
1367 	return cur_func(env)->regs;
1368 }
1369 
1370 int bpf_prog_offload_verifier_prep(struct bpf_prog *prog);
1371 int bpf_prog_offload_verify_insn(struct bpf_verifier_env *env,
1372 				 int insn_idx, int prev_insn_idx);
1373 int bpf_prog_offload_finalize(struct bpf_verifier_env *env);
1374 void
1375 bpf_prog_offload_replace_insn(struct bpf_verifier_env *env, u32 off,
1376 			      struct bpf_insn *insn);
1377 void
1378 bpf_prog_offload_remove_insns(struct bpf_verifier_env *env, u32 off, u32 cnt);
1379 
1380 /* this lives here instead of in bpf.h because it needs to dereference tgt_prog */
1381 static inline u64 bpf_trampoline_compute_key(const struct bpf_prog *tgt_prog,
1382 					     struct btf *btf, u32 btf_id)
1383 {
1384 	if (tgt_prog)
1385 		return ((u64)tgt_prog->aux->id << 32) | btf_id;
1386 	else
1387 		return ((u64)btf_obj_id(btf) << 32) | 0x80000000 | btf_id;
1388 }
1389 
1390 /* unpack the IDs from the key as constructed above */
1391 static inline void bpf_trampoline_unpack_key(u64 key, u32 *obj_id, u32 *btf_id)
1392 {
1393 	if (obj_id)
1394 		*obj_id = key >> 32;
1395 	if (btf_id)
1396 		*btf_id = key & 0x7FFFFFFF;
1397 }
1398 
1399 int bpf_prepare_btf_info(struct bpf_verifier_env *env,
1400 			 const union bpf_attr *attr, bpfptr_t uattr);
1401 int bpf_check_core_relo(struct bpf_verifier_env *env,
1402 			const union bpf_attr *attr, bpfptr_t uattr);
1403 int bpf_check_btf_info(struct bpf_verifier_env *env,
1404 		       const union bpf_attr *attr, bpfptr_t uattr);
1405 
1406 int bpf_check_attach_target(struct bpf_verifier_log *log,
1407 			    const struct bpf_prog *prog,
1408 			    const struct bpf_prog *tgt_prog,
1409 			    u32 btf_id,
1410 			    struct bpf_attach_target_info *tgt_info);
1411 int bpf_check_ext_prologue(struct bpf_verifier_log *log,
1412 			   const struct bpf_prog *tgt_prog, u32 btf_id);
1413 void bpf_free_kfunc_btf_tab(struct bpf_kfunc_btf_tab *tab);
1414 
1415 int mark_chain_precision(struct bpf_verifier_env *env, int regno);
1416 
1417 int bpf_is_state_visited(struct bpf_verifier_env *env, int insn_idx);
1418 int bpf_split_cur_state(struct bpf_verifier_env *env);
1419 int bpf_update_branch_counts(struct bpf_verifier_env *env, struct bpf_verifier_state *st);
1420 
1421 void bpf_clear_jmp_history(struct bpf_verifier_state *state);
1422 int bpf_copy_verifier_state(struct bpf_verifier_state *dst_state,
1423 			    const struct bpf_verifier_state *src);
1424 struct list_head *bpf_explored_state(struct bpf_verifier_env *env, int idx);
1425 void bpf_free_verifier_state(struct bpf_verifier_state *state, bool free_self);
1426 void bpf_free_backedges(struct bpf_scc_visit *visit);
1427 int bpf_push_jmp_history(struct bpf_verifier_env *env, struct bpf_verifier_state *cur,
1428 			 int insn_flags, int spi, int frame, const u16 *linked_regs,
1429 			 u8 linked_regs_cnt);
1430 void bpf_bt_sync_linked_regs(struct backtrack_state *bt, struct bpf_jmp_history_entry *hist);
1431 void bpf_mark_reg_not_init(const struct bpf_verifier_env *env,
1432 			   struct bpf_reg_state *reg);
1433 void bpf_mark_reg_known_scalar(struct bpf_reg_state *reg, u64 imm);
1434 void bpf_mark_reg_unknown_imprecise(struct bpf_reg_state *reg);
1435 int bpf_grow_stack_state(struct bpf_verifier_env *env, struct bpf_func_state *state, int size);
1436 void bpf_mark_all_scalars_precise(struct bpf_verifier_env *env,
1437 				  struct bpf_verifier_state *st);
1438 void bpf_clear_singular_ids(struct bpf_verifier_env *env, struct bpf_verifier_state *st);
1439 int bpf_mark_chain_precision(struct bpf_verifier_env *env,
1440 			     struct bpf_verifier_state *starting_state,
1441 			     int regno, bool *changed);
1442 
1443 static inline int bpf_get_spi(s32 off)
1444 {
1445 	return (-off - 1) / BPF_REG_SIZE;
1446 }
1447 
1448 /*
1449  * Stack a program may use in total: combined over the frames of a call
1450  * chain on the kernel stack, or per frame on a private stack. Any single
1451  * frame may reach that deep. Only a JIT that lays out such frames may go
1452  * beyond MAX_BPF_STACK, the interpreter's frame size, and only one whose
1453  * tail calls let the target set up its own frame: without subprogram
1454  * tail calls, do_misc_fixups() gives every program with tail calls a
1455  * MAX_BPF_STACK frame, which a deeper frame would overrun.
1456  */
1457 static inline u32 bpf_prog_stack_limit(const struct bpf_prog *prog)
1458 {
1459 	/* an offloaded program never runs on the host JIT, whatever it supports */
1460 	if (prog->jit_requested && !bpf_prog_is_offloaded(prog->aux) &&
1461 	    bpf_jit_supports_large_stack() && bpf_jit_supports_subprog_tailcalls())
1462 		return MAX_BPF_STACK_JIT;
1463 	return MAX_BPF_STACK;
1464 }
1465 
1466 /*
1467  * Return the function state a stack pointer register refers to. frameno
1468  * shares storage with other pointer metadata, so return NULL for any
1469  * other register type instead of indexing frame[] with aliased bytes.
1470  */
1471 static inline struct bpf_func_state *bpf_func(struct bpf_verifier_env *env,
1472 					      const struct bpf_reg_state *reg)
1473 {
1474 	struct bpf_verifier_state *cur = env->cur_state;
1475 
1476 	if (reg->type != PTR_TO_STACK)
1477 		return NULL;
1478 	return cur->frame[reg->frameno];
1479 }
1480 
1481 /* Return IP for a given frame in a call stack */
1482 static inline u32 bpf_frame_insn_idx(struct bpf_verifier_state *st, u32 frame)
1483 {
1484 	return frame == st->curframe
1485 	       ? st->insn_idx
1486 	       : st->frame[frame + 1]->callsite;
1487 }
1488 
1489 static inline bool bpf_is_jmp_point(struct bpf_verifier_env *env, int insn_idx)
1490 {
1491 	return env->insn_aux_data[insn_idx].jmp_point;
1492 }
1493 
1494 static inline bool bpf_is_spilled_reg(const struct bpf_stack_state *stack)
1495 {
1496 	return stack->slot_type[BPF_REG_SIZE - 1] == STACK_SPILL;
1497 }
1498 
1499 static inline int bpf_spill_size(const struct bpf_stack_state *stack)
1500 {
1501 	int i, spill_size = 0;
1502 
1503 	for (i = BPF_REG_SIZE - 1; i >= 0 && stack->slot_type[i] == STACK_SPILL; i--)
1504 		spill_size++;
1505 	return spill_size;
1506 }
1507 
1508 static inline bool bpf_is_spilled_scalar_reg(const struct bpf_stack_state *stack)
1509 {
1510 	return bpf_is_spilled_reg(stack) && stack->spilled_ptr.type == SCALAR_VALUE;
1511 }
1512 
1513 static inline bool bpf_register_is_null(struct bpf_reg_state *reg)
1514 {
1515 	return reg->type == SCALAR_VALUE && tnum_equals_const(reg->var_off, 0);
1516 }
1517 
1518 static inline void bpf_bt_set_frame_reg(struct backtrack_state *bt, u32 frame, u32 reg)
1519 {
1520 	bt->reg_masks[frame] |= 1 << reg;
1521 }
1522 
1523 static inline void bpf_bt_set_frame_slot(struct backtrack_state *bt, u32 frame, u32 slot)
1524 {
1525 	__set_bit(slot, bt->stack_masks[frame]);
1526 }
1527 
1528 static inline void bt_set_frame_stack_arg_slot(struct backtrack_state *bt, u32 frame, u32 slot)
1529 {
1530 	bt->stack_arg_masks[frame] |= 1 << slot;
1531 }
1532 
1533 static inline bool bt_is_frame_reg_set(struct backtrack_state *bt, u32 frame, u32 reg)
1534 {
1535 	return bt->reg_masks[frame] & (1 << reg);
1536 }
1537 
1538 static inline bool bt_is_frame_slot_set(struct backtrack_state *bt, u32 frame, u32 slot)
1539 {
1540 	return test_bit(slot, bt->stack_masks[frame]);
1541 }
1542 
1543 bool bpf_map_is_rdonly(const struct bpf_map *map);
1544 struct bpf_func_ptr *bpf_map_func_ptrs(struct bpf_verifier_env *env,
1545 				       const struct bpf_map *map, u32 *cnt);
1546 struct bpf_func_ptr *bpf_map_range_func_ptrs(struct bpf_verifier_env *env,
1547 					     const struct bpf_map *map,
1548 					     u64 off, u64 size, u32 *cnt);
1549 void bpf_adjust_func_ptrs(struct bpf_verifier_env *env, u32 off, u32 len);
1550 void bpf_adjust_func_ptrs_after_remove(struct bpf_verifier_env *env, u32 off, u32 len);
1551 int bpf_map_direct_read(struct bpf_map *map, int off, int size, u64 *val,
1552 			bool is_ldsx);
1553 
1554 #define BPF_BASE_TYPE_MASK	GENMASK(BPF_BASE_TYPE_BITS - 1, 0)
1555 
1556 /* extract base type from bpf_{arg, return, reg}_type. */
1557 static inline u32 base_type(u32 type)
1558 {
1559 	return type & BPF_BASE_TYPE_MASK;
1560 }
1561 
1562 /* extract flags from an extended type. See bpf_type_flag in bpf.h. */
1563 static inline u32 type_flag(u32 type)
1564 {
1565 	return type & ~BPF_BASE_TYPE_MASK;
1566 }
1567 
1568 static inline bool bpf_is_ptr_to_mem_or_btf_id(enum bpf_reg_type type)
1569 {
1570 	switch (base_type(type)) {
1571 	case PTR_TO_MEM:
1572 	case PTR_TO_BTF_ID:
1573 		return true;
1574 	default:
1575 		return false;
1576 	}
1577 }
1578 
1579 static inline bool bpf_may_fault_on_deref(enum bpf_reg_type type)
1580 {
1581 	/*
1582 	 * The pointer types which must not be dereferenced without fault
1583 	 * protection, that is, the ones bpf_convert_ctx_accesses() has to
1584 	 * turn a BPF_LDX into a BPF_PROBE_MEM one for.
1585 	 */
1586 	return type == PTR_TO_BTF_ID || (type_flag(type) & PTR_UNTRUSTED);
1587 }
1588 
1589 static inline bool bpf_prog_has_arena_ctx_arg(const struct bpf_prog *prog)
1590 {
1591 	int i;
1592 
1593 	for (i = 0; i < prog->aux->ctx_arg_info_size; i++)
1594 		if (base_type(prog->aux->ctx_arg_info[i].reg_type) == PTR_TO_ARENA)
1595 			return true;
1596 	return false;
1597 }
1598 
1599 static inline enum bpf_prog_type resolve_prog_type(const struct bpf_prog *prog)
1600 {
1601 	return (prog->type == BPF_PROG_TYPE_EXT && prog->aux->saved_dst_prog_type) ?
1602 		prog->aux->saved_dst_prog_type : prog->type;
1603 }
1604 
1605 static inline bool bpf_prog_check_recur(const struct bpf_prog *prog)
1606 {
1607 	switch (resolve_prog_type(prog)) {
1608 	case BPF_PROG_TYPE_TRACING:
1609 		return prog->expected_attach_type != BPF_TRACE_ITER;
1610 	case BPF_PROG_TYPE_STRUCT_OPS:
1611 		return prog->aux->jits_use_priv_stack;
1612 	case BPF_PROG_TYPE_LSM:
1613 	case BPF_PROG_TYPE_SYSCALL:
1614 		return false;
1615 	default:
1616 		return true;
1617 	}
1618 }
1619 
1620 #define BPF_REG_TRUSTED_MODIFIERS (MEM_ALLOC | PTR_TRUSTED | NON_OWN_REF)
1621 
1622 static inline bool bpf_type_has_unsafe_modifiers(u32 type)
1623 {
1624 	return type_flag(type) & ~BPF_REG_TRUSTED_MODIFIERS;
1625 }
1626 
1627 static inline bool type_is_ptr_alloc_obj(u32 type)
1628 {
1629 	return base_type(type) == PTR_TO_BTF_ID &&
1630 	       type_flag(type) & MEM_ALLOC &&
1631 	       !(type_flag(type) & PTR_UNTRUSTED);
1632 }
1633 
1634 static inline bool type_is_non_owning_ref(u32 type)
1635 {
1636 	return type_is_ptr_alloc_obj(type) && type_flag(type) & NON_OWN_REF;
1637 }
1638 
1639 static inline bool type_is_map_ptr(enum bpf_reg_type type)
1640 {
1641 	switch (base_type(type)) {
1642 	case CONST_PTR_TO_MAP:
1643 	case PTR_TO_MAP_KEY:
1644 	case PTR_TO_MAP_VALUE:
1645 		return true;
1646 	default:
1647 		return false;
1648 	}
1649 }
1650 
1651 static inline bool type_is_pkt_pointer(enum bpf_reg_type type)
1652 {
1653 	type = base_type(type);
1654 	return type == PTR_TO_PACKET ||
1655 	       type == PTR_TO_PACKET_META;
1656 }
1657 
1658 static inline bool type_is_sk_pointer(enum bpf_reg_type type)
1659 {
1660 	return type == PTR_TO_SOCKET ||
1661 		type == PTR_TO_SOCK_COMMON ||
1662 		type == PTR_TO_TCP_SOCK ||
1663 		type == PTR_TO_XDP_SOCK;
1664 }
1665 
1666 static inline bool type_may_be_null(u32 type)
1667 {
1668 	return type & PTR_MAYBE_NULL;
1669 }
1670 
1671 static inline void mark_reg_scratched(struct bpf_verifier_env *env, u32 regno)
1672 {
1673 	env->scratched_regs |= 1U << regno;
1674 }
1675 
1676 static inline void mark_stack_slot_scratched(struct bpf_verifier_env *env, u32 spi)
1677 {
1678 	__set_bit(spi, env->scratched_stack_slots);
1679 }
1680 
1681 static inline bool reg_scratched(const struct bpf_verifier_env *env, u32 regno)
1682 {
1683 	return (env->scratched_regs >> regno) & 1;
1684 }
1685 
1686 static inline bool stack_slot_scratched(const struct bpf_verifier_env *env, u32 spi)
1687 {
1688 	return test_bit(spi, env->scratched_stack_slots);
1689 }
1690 
1691 static inline bool verifier_state_scratched(const struct bpf_verifier_env *env)
1692 {
1693 	return env->scratched_regs ||
1694 	       !bitmap_empty(env->scratched_stack_slots, MAX_BPF_STACK_SLOTS);
1695 }
1696 
1697 static inline void mark_verifier_state_clean(struct bpf_verifier_env *env)
1698 {
1699 	env->scratched_regs = 0U;
1700 	bitmap_zero(env->scratched_stack_slots, MAX_BPF_STACK_SLOTS);
1701 }
1702 
1703 /* Used for printing the entire verifier state. */
1704 static inline void mark_verifier_state_scratched(struct bpf_verifier_env *env)
1705 {
1706 	env->scratched_regs = ~0U;
1707 	bitmap_fill(env->scratched_stack_slots, MAX_BPF_STACK_SLOTS);
1708 }
1709 
1710 static inline bool bpf_stack_narrow_access_ok(int off, int fill_size, int spill_size)
1711 {
1712 #ifdef __BIG_ENDIAN
1713 	off -= spill_size - fill_size;
1714 #endif
1715 
1716 	return !(off % BPF_REG_SIZE);
1717 }
1718 
1719 static inline bool insn_is_gotox(struct bpf_insn *insn)
1720 {
1721 	return BPF_CLASS(insn->code) == BPF_JMP &&
1722 	       BPF_OP(insn->code) == BPF_JA &&
1723 	       BPF_SRC(insn->code) == BPF_X;
1724 }
1725 
1726 const char *reg_type_str(struct bpf_verifier_env *env, enum bpf_reg_type type);
1727 const char *dynptr_type_str(enum bpf_dynptr_type type);
1728 const char *iter_type_str(const struct btf *btf, u32 btf_id);
1729 const char *iter_state_str(enum bpf_iter_state state);
1730 
1731 void print_verifier_state(struct bpf_verifier_env *env, const struct bpf_verifier_state *vstate,
1732 			  u32 frameno, bool print_all);
1733 void print_insn_state(struct bpf_verifier_env *env, const struct bpf_verifier_state *vstate,
1734 		      u32 frameno);
1735 u32 bpf_vlog_alignment(u32 pos);
1736 const char *bpf_disasm_kfunc_name(void *data, const struct bpf_insn *insn);
1737 
1738 struct bpf_subprog_info *bpf_find_containing_subprog(struct bpf_verifier_env *env, int off);
1739 const char *bpf_subprog_name(const struct bpf_verifier_env *env, int subprog);
1740 int bpf_jmp_offset(struct bpf_insn *insn);
1741 struct bpf_iarray *bpf_insn_successors(struct bpf_verifier_env *env, u32 idx);
1742 void bpf_fmt_stack_mask(char *buf, ssize_t buf_sz, const unsigned long *stack_mask);
1743 bool bpf_subprog_is_global(const struct bpf_verifier_env *env, int subprog);
1744 
1745 /* Kinds of member a by-value struct or union may be composed of. */
1746 enum btf_member_kind {
1747 	BTF_MEMBER_SCALAR	= BIT(0), /* an int or an enum */
1748 	BTF_MEMBER_ARENA_PTR	= BIT(1), /* a pointer carrying the "arena" type tag */
1749 };
1750 
1751 bool btf_struct_is_composed_of(struct bpf_verifier_env *env, const struct btf *btf,
1752 			       const struct btf_type *t, u32 member_kinds);
1753 u32 btf_func_arg_align(const struct btf *btf, const struct btf_type *t);
1754 
1755 int bpf_find_subprog(struct bpf_verifier_env *env, int off);
1756 bool bpf_is_throw_kfunc(struct bpf_insn *insn);
1757 int bpf_compute_const_regs(struct bpf_verifier_env *env);
1758 int bpf_prune_dead_branches(struct bpf_verifier_env *env);
1759 int bpf_check_cfg(struct bpf_verifier_env *env);
1760 void bpf_free_subprog_jts(struct bpf_verifier_env *env);
1761 int bpf_compute_postorder(struct bpf_verifier_env *env);
1762 int bpf_compute_scc(struct bpf_verifier_env *env);
1763 
1764 struct bpf_map_desc {
1765 	struct bpf_map *ptr;
1766 	int uid;
1767 };
1768 
1769 /* The last initialized dynptr; Populated by process_dynptr_func() */
1770 struct bpf_dynptr_desc {
1771 	enum bpf_dynptr_type type;
1772 	u32 id;
1773 	u32 parent_id;
1774 };
1775 
1776 /*
1777  * The last seen rereferenced object; Updated by update_ref_obj() when a register refers to a
1778  * referenced object. Used when the helper or kfunc is casting a referenced object, returning
1779  * allocated memory derived from referenced object or creating a dynptr with a referenced
1780  * object as parent.
1781  */
1782 struct ref_obj_desc {
1783 	u32 id;
1784 	u32 parent_id;
1785 	u8 cnt;
1786 };
1787 
1788 /*
1789  * Generic MEM_UNINIT arguments, indexed by ABI slot. var_size_mask excludes
1790  * variable-sized buffers from raw mode without losing the output annotation.
1791  * size records constant ranges to mark initialized after checking all arguments,
1792  * only when the caller is allowed to read uninitialized stack memory.
1793  */
1794 struct arg_raw_mem_desc {
1795 	u16 mask;
1796 	u16 var_size_mask;
1797 	int size[MAX_BPF_FUNC_ARGS];
1798 };
1799 
1800 /* Size of PTR_TO_MEM returned, taken from a constant allocation-size argument */
1801 struct ret_mem_desc {
1802 	u32 size;
1803 	bool found;
1804 };
1805 
1806 /* A constant scalar argument; Populated by process_const_arg() */
1807 struct arg_constant_desc {
1808 	u64 value;
1809 	bool found;
1810 };
1811 
1812 struct bpf_call_arg_meta {
1813 	/* Common */
1814 	struct btf *btf;
1815 	u32 func_id;
1816 	const struct bpf_func_proto *fn;
1817 	const struct btf_type *func_proto;
1818 	u8 release_regno;
1819 	u32 ret_btf_id;
1820 	u32 subprogno;
1821 	struct bpf_map_desc map;
1822 	struct bpf_dynptr_desc dynptr;
1823 	struct ref_obj_desc ref_obj;
1824 	struct ret_mem_desc ret_mem;
1825 	struct arg_raw_mem_desc arg_raw_mem;
1826 
1827 	/* Only set by subprog */
1828 	bool subprog_may_change_pkt;
1829 
1830 	/* Only set by kfunc */
1831 	bool r0_rdonly;
1832 	u32 kfunc_flags;
1833 	const char *func_name;
1834 	struct arg_constant_desc arg_constant;
1835 	/* The type of the dynptr that the kfunc writes through */
1836 	enum bpf_dynptr_type dynptr_write_type;
1837 	/* The buffer of bpf_dynptr_slice() or bpf_dynptr_slice_rdwr() */
1838 	struct bpf_stack_range slice_buf;
1839 
1840 	/* arg_{btf,btf_id,owning_ref} are used by kfunc-specific handling,
1841 	 * generally to pass info about user-defined local kptr types to later
1842 	 * verification logic
1843 	 *   bpf_obj_drop/bpf_percpu_obj_drop
1844 	 *     Record the local kptr type to be drop'd
1845 	 *   bpf_refcount_acquire (via ARG_PTR_TO_REFCOUNTED_KPTR arg type)
1846 	 *     Record the local kptr type to be refcount_incr'd and use
1847 	 *     arg_owning_ref to determine whether refcount_acquire should be
1848 	 *     fallible
1849 	 */
1850 	struct btf *arg_btf;
1851 	u32 arg_btf_id;
1852 	bool arg_owning_ref;
1853 
1854 	struct {
1855 		struct btf_field *field;
1856 	} arg_list_head;
1857 	struct {
1858 		struct btf_field *field;
1859 	} arg_rbtree_root;
1860 	struct {
1861 		u8 spi;
1862 		u8 frameno;
1863 	} iter;
1864 
1865 	/* Only set by helper */
1866 	u64 msize_max_value;
1867 	s64 const_map_key;
1868 	struct btf *ret_btf;
1869 	struct btf_field *kptr_field;
1870 };
1871 
1872 int bpf_get_helper_proto(struct bpf_verifier_env *env, int func_id,
1873 			 const struct bpf_func_proto **ptr);
1874 int bpf_fetch_kfunc_arg_meta(struct bpf_verifier_env *env, s32 func_id,
1875 			     s16 offset, struct bpf_call_arg_meta *meta);
1876 bool bpf_is_async_callback_calling_insn(struct bpf_insn *insn);
1877 bool bpf_is_sync_callback_calling_insn(struct bpf_insn *insn);
1878 static inline bool bpf_is_iter_next_kfunc(struct bpf_call_arg_meta *meta)
1879 {
1880 	return meta->kfunc_flags & KF_ITER_NEXT;
1881 }
1882 
1883 static inline bool bpf_is_kfunc_sleepable(struct bpf_call_arg_meta *meta)
1884 {
1885 	return meta->kfunc_flags & KF_SLEEPABLE;
1886 }
1887 bool bpf_is_kfunc_pkt_changing(struct bpf_call_arg_meta *meta);
1888 struct bpf_iarray *bpf_iarray_realloc(struct bpf_iarray *old, size_t n_elem);
1889 int bpf_copy_insn_array_uniq(struct bpf_map *map, u32 start, u32 end, u32 *off);
1890 bool bpf_insn_is_cond_jump(u8 code);
1891 bool bpf_is_may_goto_insn(struct bpf_insn *insn);
1892 
1893 void bpf_verbose_insn(struct bpf_verifier_env *env, struct bpf_insn *insn);
1894 bool bpf_get_call_summary(struct bpf_verifier_env *env, struct bpf_insn *call,
1895 			  struct bpf_call_summary *cs);
1896 /* Stack effects used for state pruning; must_write implies may_write. */
1897 struct arg_access_info {
1898 	u32 size;		/* Maximum extent; U32_MAX if unknown. */
1899 	u8 may_read:1;		/* Incoming contents or initialization may be needed. */
1900 	u8 may_write:1;
1901 	u8 must_write:1;	/* Prior verifier state is destroyed throughout size. */
1902 };
1903 
1904 struct arg_access_info
1905 bpf_helper_stack_access_bytes(struct bpf_verifier_env *env,
1906 			      struct bpf_insn *insn, int arg, int insn_idx);
1907 struct arg_access_info
1908 bpf_kfunc_stack_access_bytes(struct bpf_verifier_env *env,
1909 			     struct bpf_insn *insn, int arg, int insn_idx);
1910 struct arg_access_info
1911 bpf_global_subprog_stack_access_bytes(struct bpf_verifier_env *env,
1912 				      struct bpf_insn *insn, int arg, int insn_idx);
1913 int bpf_compute_subprog_arg_access(struct bpf_verifier_env *env);
1914 bool bpf_same_memory_origin(const struct bpf_reg_state *reg_a,
1915 			    const struct bpf_reg_state *reg_b);
1916 void bpf_trim_pkt_range(struct bpf_reg_state *reg, s64 smax);
1917 int bpf_set_reg_range(struct bpf_verifier_env *env, struct bpf_reg_state *reg,
1918 		      struct cnum64 r64, struct cnum32 r32, u16 base, u16 step);
1919 bool bpf_reg_union_compatible(const struct bpf_reg_state *a, const struct bpf_reg_state *b);
1920 int bpf_reg_union(struct bpf_verifier_env *env, struct bpf_reg_state *acc,
1921 		  const struct bpf_reg_state *src);
1922 
1923 int bpf_stack_liveness_init(struct bpf_verifier_env *env);
1924 void bpf_stack_liveness_free(struct bpf_verifier_env *env);
1925 int bpf_live_stack_query_init(struct bpf_verifier_env *env, struct bpf_verifier_state *st);
1926 const unsigned long *bpf_may_write_mask(struct bpf_verifier_env *env, u32 insn_idx);
1927 bool bpf_needs_fixed_stack_off(struct bpf_verifier_env *env, int insn_idx);
1928 bool bpf_stack_slot_alive(struct bpf_verifier_env *env, u32 frameno, u32 spi);
1929 int bpf_compute_live_registers(struct bpf_verifier_env *env);
1930 
1931 #define BPF_MAP_KEY_POISON	(1ULL << 63)
1932 #define BPF_MAP_KEY_SEEN	(1ULL << 62)
1933 
1934 static inline bool bpf_map_ptr_poisoned(const struct bpf_insn_aux_data *aux)
1935 {
1936 	return aux->map_ptr_state.poison;
1937 }
1938 
1939 static inline bool bpf_map_ptr_unpriv(const struct bpf_insn_aux_data *aux)
1940 {
1941 	return aux->map_ptr_state.unpriv;
1942 }
1943 
1944 static inline bool bpf_map_key_poisoned(const struct bpf_insn_aux_data *aux)
1945 {
1946 	return aux->map_key_state & BPF_MAP_KEY_POISON;
1947 }
1948 
1949 static inline bool bpf_map_key_unseen(const struct bpf_insn_aux_data *aux)
1950 {
1951 	return !(aux->map_key_state & BPF_MAP_KEY_SEEN);
1952 }
1953 
1954 static inline u64 bpf_map_key_immediate(const struct bpf_insn_aux_data *aux)
1955 {
1956 	return aux->map_key_state & ~(BPF_MAP_KEY_SEEN | BPF_MAP_KEY_POISON);
1957 }
1958 
1959 static inline bool bpf_is_mem_insn(struct bpf_insn *insn)
1960 {
1961 	if (BPF_CLASS(insn->code) != BPF_ST &&
1962 	    BPF_CLASS(insn->code) != BPF_STX &&
1963 	    BPF_CLASS(insn->code) != BPF_LDX)
1964 		return false;
1965 
1966 	if (insn->code == (BPF_ST | BPF_NOSPEC))
1967 		return false;
1968 
1969 	return (BPF_MODE(insn->code) == BPF_MEM ||
1970 		BPF_MODE(insn->code) == BPF_MEMSX ||
1971 		BPF_MODE(insn->code) == BPF_ATOMIC);
1972 }
1973 
1974 #define MAX_PACKET_OFF 0xffff
1975 #define CALLER_SAVED_REGS 6
1976 
1977 enum bpf_reg_arg_type {
1978 	SRC_OP,		/* register is used as source operand */
1979 	DST_OP,		/* register is used as destination operand */
1980 	DST_OP_NO_MARK	/* same as above, check only, don't mark */
1981 };
1982 
1983 #define MAX_KFUNC_DESCS 256
1984 /* Each kfunc can have its canonical and one specialized call target. */
1985 #define MAX_KFUNC_CALL_DESCS (MAX_KFUNC_DESCS * 2)
1986 static_assert(MAX_KFUNC_CALL_DESCS <= S16_MAX + 1);
1987 
1988 struct bpf_kfunc_desc {
1989 	struct btf_func_model func_model;
1990 	struct bpf_func_proto proto;
1991 	u32 func_id;
1992 	u16 offset;
1993 	unsigned long addr;
1994 };
1995 
1996 struct bpf_kfunc_desc_tab {
1997 	u32 nr_descs;
1998 	u32 nr_base_descs;
1999 	/* Sorted by func_id (BTF ID) and offset (fd_array offset) during
2000 	 * verification. JITs use the descriptor index stored in the finalized
2001 	 * call's off field. The first nr_base_descs entries are the canonical
2002 	 * descriptors used for verifier lookups. Call specialization may append
2003 	 * immutable descriptors for additional targets.
2004 	 *
2005 	 * Grown one entry at a time by bpf_add_kfunc_call() and during
2006 	 * call specialization.
2007 	 */
2008 	struct bpf_kfunc_desc descs[];
2009 };
2010 
2011 /* Functions exported from verifier.c, used by fixups.c */
2012 void bpf_mark_subprog_exc_cb(struct bpf_verifier_env *env, int subprog);
2013 bool bpf_allow_tail_call_in_subprogs(struct bpf_verifier_env *env);
2014 bool bpf_verifier_inlines_helper_call(struct bpf_verifier_env *env, s32 imm);
2015 int bpf_add_kfunc_call(struct bpf_verifier_env *env, u32 func_id, u16 offset);
2016 int bpf_fixup_kfunc_call(struct bpf_verifier_env *env, struct bpf_insn *insn,
2017 			 struct bpf_insn *insn_buf, int insn_idx, int *cnt);
2018 
2019 /* Functions exported from verifier.c, used by trampoline.c */
2020 int bpf_check_attach_btf_id_multi(struct btf *btf, struct bpf_prog *prog, u32 btf_id,
2021 				  struct bpf_attach_target_info *tgt_info);
2022 
2023 /* Functions in fixups.c, called from bpf_check() */
2024 void bpf_clear_insn_aux_data(struct bpf_verifier_env *env, int start, int len);
2025 int bpf_remove_fastcall_spills_fills(struct bpf_verifier_env *env);
2026 int bpf_optimize_bpf_loop(struct bpf_verifier_env *env);
2027 void bpf_opt_hard_wire_dead_code_branches(struct bpf_verifier_env *env);
2028 int bpf_opt_remove_dead_code(struct bpf_verifier_env *env);
2029 int bpf_opt_remove_nops(struct bpf_verifier_env *env);
2030 int bpf_opt_subreg_zext_lo32_rnd_hi32(struct bpf_verifier_env *env, const union bpf_attr *attr);
2031 int bpf_convert_ctx_accesses(struct bpf_verifier_env *env);
2032 int bpf_jit_subprogs(struct bpf_verifier_env *env);
2033 int bpf_fixup_call_args(struct bpf_verifier_env *env);
2034 int bpf_do_misc_fixups(struct bpf_verifier_env *env);
2035 int bpf_insn_def32(struct bpf_prog *prog, struct bpf_insn *insn);
2036 
2037 int bpf_flip_opcode(u32 opcode);
2038 u8 bpf_rev_opcode(u8 opcode);
2039 
2040 int bpf_compute_idoms(struct bpf_verifier_env *env);
2041 int bpf_compute_loops(struct bpf_verifier_env *env);
2042 int bpf_loop_at_index(struct bpf_verifier_env *env, u32 idx);
2043 bool bpf_is_nested_loop(struct bpf_verifier_env *env, int inner_header, int outer_header);
2044 
2045 int bpf_init_scev(struct bpf_verifier_env *env);
2046 void bpf_free_scev(struct bpf_verifier_env *env);
2047 int bpf_compute_scev(struct bpf_verifier_env *env);
2048 
2049 int bpf_compute_loop_iters(struct bpf_verifier_env *env, struct bpf_verifier_state *st,
2050 			   struct bpf_loop_iters *iters);
2051 int bpf_widen_scev_regs(struct bpf_verifier_env *env, struct bpf_verifier_state *st,
2052 			struct bpf_verifier_state *loop_entry, struct bpf_loop_iters *iters);
2053 int bpf_clamp_scev_regs(struct bpf_verifier_env *env, struct bpf_func_state *st, u32 insn_idx,
2054 			struct bpf_verifier_state *entry_state, u32 max_header_count);
2055 
2056 #endif /* _LINUX_BPF_VERIFIER_H */
2057