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