1 /* Copyright (c) 2011-2014 PLUMgrid, http://plumgrid.com 2 * Copyright (c) 2016 Facebook 3 * 4 * This program is free software; you can redistribute it and/or 5 * modify it under the terms of version 2 of the GNU General Public 6 * License as published by the Free Software Foundation. 7 * 8 * This program is distributed in the hope that it will be useful, but 9 * WITHOUT ANY WARRANTY; without even the implied warranty of 10 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU 11 * General Public License for more details. 12 */ 13 #include <linux/kernel.h> 14 #include <linux/types.h> 15 #include <linux/slab.h> 16 #include <linux/bpf.h> 17 #include <linux/bpf_verifier.h> 18 #include <linux/filter.h> 19 #include <net/netlink.h> 20 #include <linux/file.h> 21 #include <linux/vmalloc.h> 22 #include <linux/stringify.h> 23 24 #include "disasm.h" 25 26 static const struct bpf_verifier_ops * const bpf_verifier_ops[] = { 27 #define BPF_PROG_TYPE(_id, _name) \ 28 [_id] = & _name ## _verifier_ops, 29 #define BPF_MAP_TYPE(_id, _ops) 30 #include <linux/bpf_types.h> 31 #undef BPF_PROG_TYPE 32 #undef BPF_MAP_TYPE 33 }; 34 35 /* bpf_check() is a static code analyzer that walks eBPF program 36 * instruction by instruction and updates register/stack state. 37 * All paths of conditional branches are analyzed until 'bpf_exit' insn. 38 * 39 * The first pass is depth-first-search to check that the program is a DAG. 40 * It rejects the following programs: 41 * - larger than BPF_MAXINSNS insns 42 * - if loop is present (detected via back-edge) 43 * - unreachable insns exist (shouldn't be a forest. program = one function) 44 * - out of bounds or malformed jumps 45 * The second pass is all possible path descent from the 1st insn. 46 * Since it's analyzing all pathes through the program, the length of the 47 * analysis is limited to 64k insn, which may be hit even if total number of 48 * insn is less then 4K, but there are too many branches that change stack/regs. 49 * Number of 'branches to be analyzed' is limited to 1k 50 * 51 * On entry to each instruction, each register has a type, and the instruction 52 * changes the types of the registers depending on instruction semantics. 53 * If instruction is BPF_MOV64_REG(BPF_REG_1, BPF_REG_5), then type of R5 is 54 * copied to R1. 55 * 56 * All registers are 64-bit. 57 * R0 - return register 58 * R1-R5 argument passing registers 59 * R6-R9 callee saved registers 60 * R10 - frame pointer read-only 61 * 62 * At the start of BPF program the register R1 contains a pointer to bpf_context 63 * and has type PTR_TO_CTX. 64 * 65 * Verifier tracks arithmetic operations on pointers in case: 66 * BPF_MOV64_REG(BPF_REG_1, BPF_REG_10), 67 * BPF_ALU64_IMM(BPF_ADD, BPF_REG_1, -20), 68 * 1st insn copies R10 (which has FRAME_PTR) type into R1 69 * and 2nd arithmetic instruction is pattern matched to recognize 70 * that it wants to construct a pointer to some element within stack. 71 * So after 2nd insn, the register R1 has type PTR_TO_STACK 72 * (and -20 constant is saved for further stack bounds checking). 73 * Meaning that this reg is a pointer to stack plus known immediate constant. 74 * 75 * Most of the time the registers have SCALAR_VALUE type, which 76 * means the register has some value, but it's not a valid pointer. 77 * (like pointer plus pointer becomes SCALAR_VALUE type) 78 * 79 * When verifier sees load or store instructions the type of base register 80 * can be: PTR_TO_MAP_VALUE, PTR_TO_CTX, PTR_TO_STACK. These are three pointer 81 * types recognized by check_mem_access() function. 82 * 83 * PTR_TO_MAP_VALUE means that this register is pointing to 'map element value' 84 * and the range of [ptr, ptr + map's value_size) is accessible. 85 * 86 * registers used to pass values to function calls are checked against 87 * function argument constraints. 88 * 89 * ARG_PTR_TO_MAP_KEY is one of such argument constraints. 90 * It means that the register type passed to this function must be 91 * PTR_TO_STACK and it will be used inside the function as 92 * 'pointer to map element key' 93 * 94 * For example the argument constraints for bpf_map_lookup_elem(): 95 * .ret_type = RET_PTR_TO_MAP_VALUE_OR_NULL, 96 * .arg1_type = ARG_CONST_MAP_PTR, 97 * .arg2_type = ARG_PTR_TO_MAP_KEY, 98 * 99 * ret_type says that this function returns 'pointer to map elem value or null' 100 * function expects 1st argument to be a const pointer to 'struct bpf_map' and 101 * 2nd argument should be a pointer to stack, which will be used inside 102 * the helper function as a pointer to map element key. 103 * 104 * On the kernel side the helper function looks like: 105 * u64 bpf_map_lookup_elem(u64 r1, u64 r2, u64 r3, u64 r4, u64 r5) 106 * { 107 * struct bpf_map *map = (struct bpf_map *) (unsigned long) r1; 108 * void *key = (void *) (unsigned long) r2; 109 * void *value; 110 * 111 * here kernel can access 'key' and 'map' pointers safely, knowing that 112 * [key, key + map->key_size) bytes are valid and were initialized on 113 * the stack of eBPF program. 114 * } 115 * 116 * Corresponding eBPF program may look like: 117 * BPF_MOV64_REG(BPF_REG_2, BPF_REG_10), // after this insn R2 type is FRAME_PTR 118 * BPF_ALU64_IMM(BPF_ADD, BPF_REG_2, -4), // after this insn R2 type is PTR_TO_STACK 119 * BPF_LD_MAP_FD(BPF_REG_1, map_fd), // after this insn R1 type is CONST_PTR_TO_MAP 120 * BPF_RAW_INSN(BPF_JMP | BPF_CALL, 0, 0, 0, BPF_FUNC_map_lookup_elem), 121 * here verifier looks at prototype of map_lookup_elem() and sees: 122 * .arg1_type == ARG_CONST_MAP_PTR and R1->type == CONST_PTR_TO_MAP, which is ok, 123 * Now verifier knows that this map has key of R1->map_ptr->key_size bytes 124 * 125 * Then .arg2_type == ARG_PTR_TO_MAP_KEY and R2->type == PTR_TO_STACK, ok so far, 126 * Now verifier checks that [R2, R2 + map's key_size) are within stack limits 127 * and were initialized prior to this call. 128 * If it's ok, then verifier allows this BPF_CALL insn and looks at 129 * .ret_type which is RET_PTR_TO_MAP_VALUE_OR_NULL, so it sets 130 * R0->type = PTR_TO_MAP_VALUE_OR_NULL which means bpf_map_lookup_elem() function 131 * returns ether pointer to map value or NULL. 132 * 133 * When type PTR_TO_MAP_VALUE_OR_NULL passes through 'if (reg != 0) goto +off' 134 * insn, the register holding that pointer in the true branch changes state to 135 * PTR_TO_MAP_VALUE and the same register changes state to CONST_IMM in the false 136 * branch. See check_cond_jmp_op(). 137 * 138 * After the call R0 is set to return type of the function and registers R1-R5 139 * are set to NOT_INIT to indicate that they are no longer readable. 140 */ 141 142 /* verifier_state + insn_idx are pushed to stack when branch is encountered */ 143 struct bpf_verifier_stack_elem { 144 /* verifer state is 'st' 145 * before processing instruction 'insn_idx' 146 * and after processing instruction 'prev_insn_idx' 147 */ 148 struct bpf_verifier_state st; 149 int insn_idx; 150 int prev_insn_idx; 151 struct bpf_verifier_stack_elem *next; 152 }; 153 154 #define BPF_COMPLEXITY_LIMIT_INSNS 131072 155 #define BPF_COMPLEXITY_LIMIT_STACK 1024 156 157 #define BPF_MAP_PTR_POISON ((void *)0xeB9F + POISON_POINTER_DELTA) 158 159 struct bpf_call_arg_meta { 160 struct bpf_map *map_ptr; 161 bool raw_mode; 162 bool pkt_access; 163 int regno; 164 int access_size; 165 }; 166 167 static DEFINE_MUTEX(bpf_verifier_lock); 168 169 /* log_level controls verbosity level of eBPF verifier. 170 * verbose() is used to dump the verification trace to the log, so the user 171 * can figure out what's wrong with the program 172 */ 173 static __printf(2, 3) void verbose(struct bpf_verifier_env *env, 174 const char *fmt, ...) 175 { 176 struct bpf_verifer_log *log = &env->log; 177 unsigned int n; 178 va_list args; 179 180 if (!log->level || !log->ubuf || bpf_verifier_log_full(log)) 181 return; 182 183 va_start(args, fmt); 184 n = vscnprintf(log->kbuf, BPF_VERIFIER_TMP_LOG_SIZE, fmt, args); 185 va_end(args); 186 187 WARN_ONCE(n >= BPF_VERIFIER_TMP_LOG_SIZE - 1, 188 "verifier log line truncated - local buffer too short\n"); 189 190 n = min(log->len_total - log->len_used - 1, n); 191 log->kbuf[n] = '\0'; 192 193 if (!copy_to_user(log->ubuf + log->len_used, log->kbuf, n + 1)) 194 log->len_used += n; 195 else 196 log->ubuf = NULL; 197 } 198 199 static bool type_is_pkt_pointer(enum bpf_reg_type type) 200 { 201 return type == PTR_TO_PACKET || 202 type == PTR_TO_PACKET_META; 203 } 204 205 /* string representation of 'enum bpf_reg_type' */ 206 static const char * const reg_type_str[] = { 207 [NOT_INIT] = "?", 208 [SCALAR_VALUE] = "inv", 209 [PTR_TO_CTX] = "ctx", 210 [CONST_PTR_TO_MAP] = "map_ptr", 211 [PTR_TO_MAP_VALUE] = "map_value", 212 [PTR_TO_MAP_VALUE_OR_NULL] = "map_value_or_null", 213 [PTR_TO_STACK] = "fp", 214 [PTR_TO_PACKET] = "pkt", 215 [PTR_TO_PACKET_META] = "pkt_meta", 216 [PTR_TO_PACKET_END] = "pkt_end", 217 }; 218 219 static void print_verifier_state(struct bpf_verifier_env *env, 220 struct bpf_verifier_state *state) 221 { 222 struct bpf_reg_state *reg; 223 enum bpf_reg_type t; 224 int i; 225 226 for (i = 0; i < MAX_BPF_REG; i++) { 227 reg = &state->regs[i]; 228 t = reg->type; 229 if (t == NOT_INIT) 230 continue; 231 verbose(env, " R%d=%s", i, reg_type_str[t]); 232 if ((t == SCALAR_VALUE || t == PTR_TO_STACK) && 233 tnum_is_const(reg->var_off)) { 234 /* reg->off should be 0 for SCALAR_VALUE */ 235 verbose(env, "%lld", reg->var_off.value + reg->off); 236 } else { 237 verbose(env, "(id=%d", reg->id); 238 if (t != SCALAR_VALUE) 239 verbose(env, ",off=%d", reg->off); 240 if (type_is_pkt_pointer(t)) 241 verbose(env, ",r=%d", reg->range); 242 else if (t == CONST_PTR_TO_MAP || 243 t == PTR_TO_MAP_VALUE || 244 t == PTR_TO_MAP_VALUE_OR_NULL) 245 verbose(env, ",ks=%d,vs=%d", 246 reg->map_ptr->key_size, 247 reg->map_ptr->value_size); 248 if (tnum_is_const(reg->var_off)) { 249 /* Typically an immediate SCALAR_VALUE, but 250 * could be a pointer whose offset is too big 251 * for reg->off 252 */ 253 verbose(env, ",imm=%llx", reg->var_off.value); 254 } else { 255 if (reg->smin_value != reg->umin_value && 256 reg->smin_value != S64_MIN) 257 verbose(env, ",smin_value=%lld", 258 (long long)reg->smin_value); 259 if (reg->smax_value != reg->umax_value && 260 reg->smax_value != S64_MAX) 261 verbose(env, ",smax_value=%lld", 262 (long long)reg->smax_value); 263 if (reg->umin_value != 0) 264 verbose(env, ",umin_value=%llu", 265 (unsigned long long)reg->umin_value); 266 if (reg->umax_value != U64_MAX) 267 verbose(env, ",umax_value=%llu", 268 (unsigned long long)reg->umax_value); 269 if (!tnum_is_unknown(reg->var_off)) { 270 char tn_buf[48]; 271 272 tnum_strn(tn_buf, sizeof(tn_buf), reg->var_off); 273 verbose(env, ",var_off=%s", tn_buf); 274 } 275 } 276 verbose(env, ")"); 277 } 278 } 279 for (i = 0; i < state->allocated_stack / BPF_REG_SIZE; i++) { 280 if (state->stack[i].slot_type[0] == STACK_SPILL) 281 verbose(env, " fp%d=%s", 282 -MAX_BPF_STACK + i * BPF_REG_SIZE, 283 reg_type_str[state->stack[i].spilled_ptr.type]); 284 } 285 verbose(env, "\n"); 286 } 287 288 static int copy_stack_state(struct bpf_verifier_state *dst, 289 const struct bpf_verifier_state *src) 290 { 291 if (!src->stack) 292 return 0; 293 if (WARN_ON_ONCE(dst->allocated_stack < src->allocated_stack)) { 294 /* internal bug, make state invalid to reject the program */ 295 memset(dst, 0, sizeof(*dst)); 296 return -EFAULT; 297 } 298 memcpy(dst->stack, src->stack, 299 sizeof(*src->stack) * (src->allocated_stack / BPF_REG_SIZE)); 300 return 0; 301 } 302 303 /* do_check() starts with zero-sized stack in struct bpf_verifier_state to 304 * make it consume minimal amount of memory. check_stack_write() access from 305 * the program calls into realloc_verifier_state() to grow the stack size. 306 * Note there is a non-zero 'parent' pointer inside bpf_verifier_state 307 * which this function copies over. It points to previous bpf_verifier_state 308 * which is never reallocated 309 */ 310 static int realloc_verifier_state(struct bpf_verifier_state *state, int size, 311 bool copy_old) 312 { 313 u32 old_size = state->allocated_stack; 314 struct bpf_stack_state *new_stack; 315 int slot = size / BPF_REG_SIZE; 316 317 if (size <= old_size || !size) { 318 if (copy_old) 319 return 0; 320 state->allocated_stack = slot * BPF_REG_SIZE; 321 if (!size && old_size) { 322 kfree(state->stack); 323 state->stack = NULL; 324 } 325 return 0; 326 } 327 new_stack = kmalloc_array(slot, sizeof(struct bpf_stack_state), 328 GFP_KERNEL); 329 if (!new_stack) 330 return -ENOMEM; 331 if (copy_old) { 332 if (state->stack) 333 memcpy(new_stack, state->stack, 334 sizeof(*new_stack) * (old_size / BPF_REG_SIZE)); 335 memset(new_stack + old_size / BPF_REG_SIZE, 0, 336 sizeof(*new_stack) * (size - old_size) / BPF_REG_SIZE); 337 } 338 state->allocated_stack = slot * BPF_REG_SIZE; 339 kfree(state->stack); 340 state->stack = new_stack; 341 return 0; 342 } 343 344 static void free_verifier_state(struct bpf_verifier_state *state, 345 bool free_self) 346 { 347 kfree(state->stack); 348 if (free_self) 349 kfree(state); 350 } 351 352 /* copy verifier state from src to dst growing dst stack space 353 * when necessary to accommodate larger src stack 354 */ 355 static int copy_verifier_state(struct bpf_verifier_state *dst, 356 const struct bpf_verifier_state *src) 357 { 358 int err; 359 360 err = realloc_verifier_state(dst, src->allocated_stack, false); 361 if (err) 362 return err; 363 memcpy(dst, src, offsetof(struct bpf_verifier_state, allocated_stack)); 364 return copy_stack_state(dst, src); 365 } 366 367 static int pop_stack(struct bpf_verifier_env *env, int *prev_insn_idx, 368 int *insn_idx) 369 { 370 struct bpf_verifier_state *cur = env->cur_state; 371 struct bpf_verifier_stack_elem *elem, *head = env->head; 372 int err; 373 374 if (env->head == NULL) 375 return -ENOENT; 376 377 if (cur) { 378 err = copy_verifier_state(cur, &head->st); 379 if (err) 380 return err; 381 } 382 if (insn_idx) 383 *insn_idx = head->insn_idx; 384 if (prev_insn_idx) 385 *prev_insn_idx = head->prev_insn_idx; 386 elem = head->next; 387 free_verifier_state(&head->st, false); 388 kfree(head); 389 env->head = elem; 390 env->stack_size--; 391 return 0; 392 } 393 394 static struct bpf_verifier_state *push_stack(struct bpf_verifier_env *env, 395 int insn_idx, int prev_insn_idx) 396 { 397 struct bpf_verifier_state *cur = env->cur_state; 398 struct bpf_verifier_stack_elem *elem; 399 int err; 400 401 elem = kzalloc(sizeof(struct bpf_verifier_stack_elem), GFP_KERNEL); 402 if (!elem) 403 goto err; 404 405 elem->insn_idx = insn_idx; 406 elem->prev_insn_idx = prev_insn_idx; 407 elem->next = env->head; 408 env->head = elem; 409 env->stack_size++; 410 err = copy_verifier_state(&elem->st, cur); 411 if (err) 412 goto err; 413 if (env->stack_size > BPF_COMPLEXITY_LIMIT_STACK) { 414 verbose(env, "BPF program is too complex\n"); 415 goto err; 416 } 417 return &elem->st; 418 err: 419 /* pop all elements and return */ 420 while (!pop_stack(env, NULL, NULL)); 421 return NULL; 422 } 423 424 #define CALLER_SAVED_REGS 6 425 static const int caller_saved[CALLER_SAVED_REGS] = { 426 BPF_REG_0, BPF_REG_1, BPF_REG_2, BPF_REG_3, BPF_REG_4, BPF_REG_5 427 }; 428 429 static void __mark_reg_not_init(struct bpf_reg_state *reg); 430 431 /* Mark the unknown part of a register (variable offset or scalar value) as 432 * known to have the value @imm. 433 */ 434 static void __mark_reg_known(struct bpf_reg_state *reg, u64 imm) 435 { 436 reg->id = 0; 437 reg->var_off = tnum_const(imm); 438 reg->smin_value = (s64)imm; 439 reg->smax_value = (s64)imm; 440 reg->umin_value = imm; 441 reg->umax_value = imm; 442 } 443 444 /* Mark the 'variable offset' part of a register as zero. This should be 445 * used only on registers holding a pointer type. 446 */ 447 static void __mark_reg_known_zero(struct bpf_reg_state *reg) 448 { 449 __mark_reg_known(reg, 0); 450 } 451 452 static void mark_reg_known_zero(struct bpf_verifier_env *env, 453 struct bpf_reg_state *regs, u32 regno) 454 { 455 if (WARN_ON(regno >= MAX_BPF_REG)) { 456 verbose(env, "mark_reg_known_zero(regs, %u)\n", regno); 457 /* Something bad happened, let's kill all regs */ 458 for (regno = 0; regno < MAX_BPF_REG; regno++) 459 __mark_reg_not_init(regs + regno); 460 return; 461 } 462 __mark_reg_known_zero(regs + regno); 463 } 464 465 static bool reg_is_pkt_pointer(const struct bpf_reg_state *reg) 466 { 467 return type_is_pkt_pointer(reg->type); 468 } 469 470 static bool reg_is_pkt_pointer_any(const struct bpf_reg_state *reg) 471 { 472 return reg_is_pkt_pointer(reg) || 473 reg->type == PTR_TO_PACKET_END; 474 } 475 476 /* Unmodified PTR_TO_PACKET[_META,_END] register from ctx access. */ 477 static bool reg_is_init_pkt_pointer(const struct bpf_reg_state *reg, 478 enum bpf_reg_type which) 479 { 480 /* The register can already have a range from prior markings. 481 * This is fine as long as it hasn't been advanced from its 482 * origin. 483 */ 484 return reg->type == which && 485 reg->id == 0 && 486 reg->off == 0 && 487 tnum_equals_const(reg->var_off, 0); 488 } 489 490 /* Attempts to improve min/max values based on var_off information */ 491 static void __update_reg_bounds(struct bpf_reg_state *reg) 492 { 493 /* min signed is max(sign bit) | min(other bits) */ 494 reg->smin_value = max_t(s64, reg->smin_value, 495 reg->var_off.value | (reg->var_off.mask & S64_MIN)); 496 /* max signed is min(sign bit) | max(other bits) */ 497 reg->smax_value = min_t(s64, reg->smax_value, 498 reg->var_off.value | (reg->var_off.mask & S64_MAX)); 499 reg->umin_value = max(reg->umin_value, reg->var_off.value); 500 reg->umax_value = min(reg->umax_value, 501 reg->var_off.value | reg->var_off.mask); 502 } 503 504 /* Uses signed min/max values to inform unsigned, and vice-versa */ 505 static void __reg_deduce_bounds(struct bpf_reg_state *reg) 506 { 507 /* Learn sign from signed bounds. 508 * If we cannot cross the sign boundary, then signed and unsigned bounds 509 * are the same, so combine. This works even in the negative case, e.g. 510 * -3 s<= x s<= -1 implies 0xf...fd u<= x u<= 0xf...ff. 511 */ 512 if (reg->smin_value >= 0 || reg->smax_value < 0) { 513 reg->smin_value = reg->umin_value = max_t(u64, reg->smin_value, 514 reg->umin_value); 515 reg->smax_value = reg->umax_value = min_t(u64, reg->smax_value, 516 reg->umax_value); 517 return; 518 } 519 /* Learn sign from unsigned bounds. Signed bounds cross the sign 520 * boundary, so we must be careful. 521 */ 522 if ((s64)reg->umax_value >= 0) { 523 /* Positive. We can't learn anything from the smin, but smax 524 * is positive, hence safe. 525 */ 526 reg->smin_value = reg->umin_value; 527 reg->smax_value = reg->umax_value = min_t(u64, reg->smax_value, 528 reg->umax_value); 529 } else if ((s64)reg->umin_value < 0) { 530 /* Negative. We can't learn anything from the smax, but smin 531 * is negative, hence safe. 532 */ 533 reg->smin_value = reg->umin_value = max_t(u64, reg->smin_value, 534 reg->umin_value); 535 reg->smax_value = reg->umax_value; 536 } 537 } 538 539 /* Attempts to improve var_off based on unsigned min/max information */ 540 static void __reg_bound_offset(struct bpf_reg_state *reg) 541 { 542 reg->var_off = tnum_intersect(reg->var_off, 543 tnum_range(reg->umin_value, 544 reg->umax_value)); 545 } 546 547 /* Reset the min/max bounds of a register */ 548 static void __mark_reg_unbounded(struct bpf_reg_state *reg) 549 { 550 reg->smin_value = S64_MIN; 551 reg->smax_value = S64_MAX; 552 reg->umin_value = 0; 553 reg->umax_value = U64_MAX; 554 } 555 556 /* Mark a register as having a completely unknown (scalar) value. */ 557 static void __mark_reg_unknown(struct bpf_reg_state *reg) 558 { 559 reg->type = SCALAR_VALUE; 560 reg->id = 0; 561 reg->off = 0; 562 reg->var_off = tnum_unknown; 563 __mark_reg_unbounded(reg); 564 } 565 566 static void mark_reg_unknown(struct bpf_verifier_env *env, 567 struct bpf_reg_state *regs, u32 regno) 568 { 569 if (WARN_ON(regno >= MAX_BPF_REG)) { 570 verbose(env, "mark_reg_unknown(regs, %u)\n", regno); 571 /* Something bad happened, let's kill all regs */ 572 for (regno = 0; regno < MAX_BPF_REG; regno++) 573 __mark_reg_not_init(regs + regno); 574 return; 575 } 576 __mark_reg_unknown(regs + regno); 577 } 578 579 static void __mark_reg_not_init(struct bpf_reg_state *reg) 580 { 581 __mark_reg_unknown(reg); 582 reg->type = NOT_INIT; 583 } 584 585 static void mark_reg_not_init(struct bpf_verifier_env *env, 586 struct bpf_reg_state *regs, u32 regno) 587 { 588 if (WARN_ON(regno >= MAX_BPF_REG)) { 589 verbose(env, "mark_reg_not_init(regs, %u)\n", regno); 590 /* Something bad happened, let's kill all regs */ 591 for (regno = 0; regno < MAX_BPF_REG; regno++) 592 __mark_reg_not_init(regs + regno); 593 return; 594 } 595 __mark_reg_not_init(regs + regno); 596 } 597 598 static void init_reg_state(struct bpf_verifier_env *env, 599 struct bpf_reg_state *regs) 600 { 601 int i; 602 603 for (i = 0; i < MAX_BPF_REG; i++) { 604 mark_reg_not_init(env, regs, i); 605 regs[i].live = REG_LIVE_NONE; 606 } 607 608 /* frame pointer */ 609 regs[BPF_REG_FP].type = PTR_TO_STACK; 610 mark_reg_known_zero(env, regs, BPF_REG_FP); 611 612 /* 1st arg to a function */ 613 regs[BPF_REG_1].type = PTR_TO_CTX; 614 mark_reg_known_zero(env, regs, BPF_REG_1); 615 } 616 617 enum reg_arg_type { 618 SRC_OP, /* register is used as source operand */ 619 DST_OP, /* register is used as destination operand */ 620 DST_OP_NO_MARK /* same as above, check only, don't mark */ 621 }; 622 623 static void mark_reg_read(const struct bpf_verifier_state *state, u32 regno) 624 { 625 struct bpf_verifier_state *parent = state->parent; 626 627 if (regno == BPF_REG_FP) 628 /* We don't need to worry about FP liveness because it's read-only */ 629 return; 630 631 while (parent) { 632 /* if read wasn't screened by an earlier write ... */ 633 if (state->regs[regno].live & REG_LIVE_WRITTEN) 634 break; 635 /* ... then we depend on parent's value */ 636 parent->regs[regno].live |= REG_LIVE_READ; 637 state = parent; 638 parent = state->parent; 639 } 640 } 641 642 static int check_reg_arg(struct bpf_verifier_env *env, u32 regno, 643 enum reg_arg_type t) 644 { 645 struct bpf_reg_state *regs = env->cur_state->regs; 646 647 if (regno >= MAX_BPF_REG) { 648 verbose(env, "R%d is invalid\n", regno); 649 return -EINVAL; 650 } 651 652 if (t == SRC_OP) { 653 /* check whether register used as source operand can be read */ 654 if (regs[regno].type == NOT_INIT) { 655 verbose(env, "R%d !read_ok\n", regno); 656 return -EACCES; 657 } 658 mark_reg_read(env->cur_state, regno); 659 } else { 660 /* check whether register used as dest operand can be written to */ 661 if (regno == BPF_REG_FP) { 662 verbose(env, "frame pointer is read only\n"); 663 return -EACCES; 664 } 665 regs[regno].live |= REG_LIVE_WRITTEN; 666 if (t == DST_OP) 667 mark_reg_unknown(env, regs, regno); 668 } 669 return 0; 670 } 671 672 static bool is_spillable_regtype(enum bpf_reg_type type) 673 { 674 switch (type) { 675 case PTR_TO_MAP_VALUE: 676 case PTR_TO_MAP_VALUE_OR_NULL: 677 case PTR_TO_STACK: 678 case PTR_TO_CTX: 679 case PTR_TO_PACKET: 680 case PTR_TO_PACKET_META: 681 case PTR_TO_PACKET_END: 682 case CONST_PTR_TO_MAP: 683 return true; 684 default: 685 return false; 686 } 687 } 688 689 /* check_stack_read/write functions track spill/fill of registers, 690 * stack boundary and alignment are checked in check_mem_access() 691 */ 692 static int check_stack_write(struct bpf_verifier_env *env, 693 struct bpf_verifier_state *state, int off, 694 int size, int value_regno) 695 { 696 int i, slot = -off - 1, spi = slot / BPF_REG_SIZE, err; 697 698 err = realloc_verifier_state(state, round_up(slot + 1, BPF_REG_SIZE), 699 true); 700 if (err) 701 return err; 702 /* caller checked that off % size == 0 and -MAX_BPF_STACK <= off < 0, 703 * so it's aligned access and [off, off + size) are within stack limits 704 */ 705 if (!env->allow_ptr_leaks && 706 state->stack[spi].slot_type[0] == STACK_SPILL && 707 size != BPF_REG_SIZE) { 708 verbose(env, "attempt to corrupt spilled pointer on stack\n"); 709 return -EACCES; 710 } 711 712 if (value_regno >= 0 && 713 is_spillable_regtype(state->regs[value_regno].type)) { 714 715 /* register containing pointer is being spilled into stack */ 716 if (size != BPF_REG_SIZE) { 717 verbose(env, "invalid size of register spill\n"); 718 return -EACCES; 719 } 720 721 /* save register state */ 722 state->stack[spi].spilled_ptr = state->regs[value_regno]; 723 state->stack[spi].spilled_ptr.live |= REG_LIVE_WRITTEN; 724 725 for (i = 0; i < BPF_REG_SIZE; i++) 726 state->stack[spi].slot_type[i] = STACK_SPILL; 727 } else { 728 /* regular write of data into stack */ 729 state->stack[spi].spilled_ptr = (struct bpf_reg_state) {}; 730 731 for (i = 0; i < size; i++) 732 state->stack[spi].slot_type[(slot - i) % BPF_REG_SIZE] = 733 STACK_MISC; 734 } 735 return 0; 736 } 737 738 static void mark_stack_slot_read(const struct bpf_verifier_state *state, int slot) 739 { 740 struct bpf_verifier_state *parent = state->parent; 741 742 while (parent) { 743 /* if read wasn't screened by an earlier write ... */ 744 if (state->stack[slot].spilled_ptr.live & REG_LIVE_WRITTEN) 745 break; 746 /* ... then we depend on parent's value */ 747 parent->stack[slot].spilled_ptr.live |= REG_LIVE_READ; 748 state = parent; 749 parent = state->parent; 750 } 751 } 752 753 static int check_stack_read(struct bpf_verifier_env *env, 754 struct bpf_verifier_state *state, int off, int size, 755 int value_regno) 756 { 757 int i, slot = -off - 1, spi = slot / BPF_REG_SIZE; 758 u8 *stype; 759 760 if (state->allocated_stack <= slot) { 761 verbose(env, "invalid read from stack off %d+0 size %d\n", 762 off, size); 763 return -EACCES; 764 } 765 stype = state->stack[spi].slot_type; 766 767 if (stype[0] == STACK_SPILL) { 768 if (size != BPF_REG_SIZE) { 769 verbose(env, "invalid size of register spill\n"); 770 return -EACCES; 771 } 772 for (i = 1; i < BPF_REG_SIZE; i++) { 773 if (stype[(slot - i) % BPF_REG_SIZE] != STACK_SPILL) { 774 verbose(env, "corrupted spill memory\n"); 775 return -EACCES; 776 } 777 } 778 779 if (value_regno >= 0) { 780 /* restore register state from stack */ 781 state->regs[value_regno] = state->stack[spi].spilled_ptr; 782 mark_stack_slot_read(state, spi); 783 } 784 return 0; 785 } else { 786 for (i = 0; i < size; i++) { 787 if (stype[(slot - i) % BPF_REG_SIZE] != STACK_MISC) { 788 verbose(env, "invalid read from stack off %d+%d size %d\n", 789 off, i, size); 790 return -EACCES; 791 } 792 } 793 if (value_regno >= 0) 794 /* have read misc data from the stack */ 795 mark_reg_unknown(env, state->regs, value_regno); 796 return 0; 797 } 798 } 799 800 /* check read/write into map element returned by bpf_map_lookup_elem() */ 801 static int __check_map_access(struct bpf_verifier_env *env, u32 regno, int off, 802 int size, bool zero_size_allowed) 803 { 804 struct bpf_reg_state *regs = cur_regs(env); 805 struct bpf_map *map = regs[regno].map_ptr; 806 807 if (off < 0 || size < 0 || (size == 0 && !zero_size_allowed) || 808 off + size > map->value_size) { 809 verbose(env, "invalid access to map value, value_size=%d off=%d size=%d\n", 810 map->value_size, off, size); 811 return -EACCES; 812 } 813 return 0; 814 } 815 816 /* check read/write into a map element with possible variable offset */ 817 static int check_map_access(struct bpf_verifier_env *env, u32 regno, 818 int off, int size, bool zero_size_allowed) 819 { 820 struct bpf_verifier_state *state = env->cur_state; 821 struct bpf_reg_state *reg = &state->regs[regno]; 822 int err; 823 824 /* We may have adjusted the register to this map value, so we 825 * need to try adding each of min_value and max_value to off 826 * to make sure our theoretical access will be safe. 827 */ 828 if (env->log.level) 829 print_verifier_state(env, state); 830 /* The minimum value is only important with signed 831 * comparisons where we can't assume the floor of a 832 * value is 0. If we are using signed variables for our 833 * index'es we need to make sure that whatever we use 834 * will have a set floor within our range. 835 */ 836 if (reg->smin_value < 0) { 837 verbose(env, "R%d min value is negative, either use unsigned index or do a if (index >=0) check.\n", 838 regno); 839 return -EACCES; 840 } 841 err = __check_map_access(env, regno, reg->smin_value + off, size, 842 zero_size_allowed); 843 if (err) { 844 verbose(env, "R%d min value is outside of the array range\n", 845 regno); 846 return err; 847 } 848 849 /* If we haven't set a max value then we need to bail since we can't be 850 * sure we won't do bad things. 851 * If reg->umax_value + off could overflow, treat that as unbounded too. 852 */ 853 if (reg->umax_value >= BPF_MAX_VAR_OFF) { 854 verbose(env, "R%d unbounded memory access, make sure to bounds check any array access into a map\n", 855 regno); 856 return -EACCES; 857 } 858 err = __check_map_access(env, regno, reg->umax_value + off, size, 859 zero_size_allowed); 860 if (err) 861 verbose(env, "R%d max value is outside of the array range\n", 862 regno); 863 return err; 864 } 865 866 #define MAX_PACKET_OFF 0xffff 867 868 static bool may_access_direct_pkt_data(struct bpf_verifier_env *env, 869 const struct bpf_call_arg_meta *meta, 870 enum bpf_access_type t) 871 { 872 switch (env->prog->type) { 873 case BPF_PROG_TYPE_LWT_IN: 874 case BPF_PROG_TYPE_LWT_OUT: 875 /* dst_input() and dst_output() can't write for now */ 876 if (t == BPF_WRITE) 877 return false; 878 /* fallthrough */ 879 case BPF_PROG_TYPE_SCHED_CLS: 880 case BPF_PROG_TYPE_SCHED_ACT: 881 case BPF_PROG_TYPE_XDP: 882 case BPF_PROG_TYPE_LWT_XMIT: 883 case BPF_PROG_TYPE_SK_SKB: 884 if (meta) 885 return meta->pkt_access; 886 887 env->seen_direct_write = true; 888 return true; 889 default: 890 return false; 891 } 892 } 893 894 static int __check_packet_access(struct bpf_verifier_env *env, u32 regno, 895 int off, int size, bool zero_size_allowed) 896 { 897 struct bpf_reg_state *regs = cur_regs(env); 898 struct bpf_reg_state *reg = ®s[regno]; 899 900 if (off < 0 || size < 0 || (size == 0 && !zero_size_allowed) || 901 (u64)off + size > reg->range) { 902 verbose(env, "invalid access to packet, off=%d size=%d, R%d(id=%d,off=%d,r=%d)\n", 903 off, size, regno, reg->id, reg->off, reg->range); 904 return -EACCES; 905 } 906 return 0; 907 } 908 909 static int check_packet_access(struct bpf_verifier_env *env, u32 regno, int off, 910 int size, bool zero_size_allowed) 911 { 912 struct bpf_reg_state *regs = cur_regs(env); 913 struct bpf_reg_state *reg = ®s[regno]; 914 int err; 915 916 /* We may have added a variable offset to the packet pointer; but any 917 * reg->range we have comes after that. We are only checking the fixed 918 * offset. 919 */ 920 921 /* We don't allow negative numbers, because we aren't tracking enough 922 * detail to prove they're safe. 923 */ 924 if (reg->smin_value < 0) { 925 verbose(env, "R%d min value is negative, either use unsigned index or do a if (index >=0) check.\n", 926 regno); 927 return -EACCES; 928 } 929 err = __check_packet_access(env, regno, off, size, zero_size_allowed); 930 if (err) { 931 verbose(env, "R%d offset is outside of the packet\n", regno); 932 return err; 933 } 934 return err; 935 } 936 937 /* check access to 'struct bpf_context' fields. Supports fixed offsets only */ 938 static int check_ctx_access(struct bpf_verifier_env *env, int insn_idx, int off, int size, 939 enum bpf_access_type t, enum bpf_reg_type *reg_type) 940 { 941 struct bpf_insn_access_aux info = { 942 .reg_type = *reg_type, 943 }; 944 945 if (env->ops->is_valid_access && 946 env->ops->is_valid_access(off, size, t, &info)) { 947 /* A non zero info.ctx_field_size indicates that this field is a 948 * candidate for later verifier transformation to load the whole 949 * field and then apply a mask when accessed with a narrower 950 * access than actual ctx access size. A zero info.ctx_field_size 951 * will only allow for whole field access and rejects any other 952 * type of narrower access. 953 */ 954 *reg_type = info.reg_type; 955 956 env->insn_aux_data[insn_idx].ctx_field_size = info.ctx_field_size; 957 /* remember the offset of last byte accessed in ctx */ 958 if (env->prog->aux->max_ctx_offset < off + size) 959 env->prog->aux->max_ctx_offset = off + size; 960 return 0; 961 } 962 963 verbose(env, "invalid bpf_context access off=%d size=%d\n", off, size); 964 return -EACCES; 965 } 966 967 static bool __is_pointer_value(bool allow_ptr_leaks, 968 const struct bpf_reg_state *reg) 969 { 970 if (allow_ptr_leaks) 971 return false; 972 973 return reg->type != SCALAR_VALUE; 974 } 975 976 static bool is_pointer_value(struct bpf_verifier_env *env, int regno) 977 { 978 return __is_pointer_value(env->allow_ptr_leaks, cur_regs(env) + regno); 979 } 980 981 static int check_pkt_ptr_alignment(struct bpf_verifier_env *env, 982 const struct bpf_reg_state *reg, 983 int off, int size, bool strict) 984 { 985 struct tnum reg_off; 986 int ip_align; 987 988 /* Byte size accesses are always allowed. */ 989 if (!strict || size == 1) 990 return 0; 991 992 /* For platforms that do not have a Kconfig enabling 993 * CONFIG_HAVE_EFFICIENT_UNALIGNED_ACCESS the value of 994 * NET_IP_ALIGN is universally set to '2'. And on platforms 995 * that do set CONFIG_HAVE_EFFICIENT_UNALIGNED_ACCESS, we get 996 * to this code only in strict mode where we want to emulate 997 * the NET_IP_ALIGN==2 checking. Therefore use an 998 * unconditional IP align value of '2'. 999 */ 1000 ip_align = 2; 1001 1002 reg_off = tnum_add(reg->var_off, tnum_const(ip_align + reg->off + off)); 1003 if (!tnum_is_aligned(reg_off, size)) { 1004 char tn_buf[48]; 1005 1006 tnum_strn(tn_buf, sizeof(tn_buf), reg->var_off); 1007 verbose(env, 1008 "misaligned packet access off %d+%s+%d+%d size %d\n", 1009 ip_align, tn_buf, reg->off, off, size); 1010 return -EACCES; 1011 } 1012 1013 return 0; 1014 } 1015 1016 static int check_generic_ptr_alignment(struct bpf_verifier_env *env, 1017 const struct bpf_reg_state *reg, 1018 const char *pointer_desc, 1019 int off, int size, bool strict) 1020 { 1021 struct tnum reg_off; 1022 1023 /* Byte size accesses are always allowed. */ 1024 if (!strict || size == 1) 1025 return 0; 1026 1027 reg_off = tnum_add(reg->var_off, tnum_const(reg->off + off)); 1028 if (!tnum_is_aligned(reg_off, size)) { 1029 char tn_buf[48]; 1030 1031 tnum_strn(tn_buf, sizeof(tn_buf), reg->var_off); 1032 verbose(env, "misaligned %saccess off %s+%d+%d size %d\n", 1033 pointer_desc, tn_buf, reg->off, off, size); 1034 return -EACCES; 1035 } 1036 1037 return 0; 1038 } 1039 1040 static int check_ptr_alignment(struct bpf_verifier_env *env, 1041 const struct bpf_reg_state *reg, 1042 int off, int size) 1043 { 1044 bool strict = env->strict_alignment; 1045 const char *pointer_desc = ""; 1046 1047 switch (reg->type) { 1048 case PTR_TO_PACKET: 1049 case PTR_TO_PACKET_META: 1050 /* Special case, because of NET_IP_ALIGN. Given metadata sits 1051 * right in front, treat it the very same way. 1052 */ 1053 return check_pkt_ptr_alignment(env, reg, off, size, strict); 1054 case PTR_TO_MAP_VALUE: 1055 pointer_desc = "value "; 1056 break; 1057 case PTR_TO_CTX: 1058 pointer_desc = "context "; 1059 break; 1060 case PTR_TO_STACK: 1061 pointer_desc = "stack "; 1062 break; 1063 default: 1064 break; 1065 } 1066 return check_generic_ptr_alignment(env, reg, pointer_desc, off, size, 1067 strict); 1068 } 1069 1070 /* check whether memory at (regno + off) is accessible for t = (read | write) 1071 * if t==write, value_regno is a register which value is stored into memory 1072 * if t==read, value_regno is a register which will receive the value from memory 1073 * if t==write && value_regno==-1, some unknown value is stored into memory 1074 * if t==read && value_regno==-1, don't care what we read from memory 1075 */ 1076 static int check_mem_access(struct bpf_verifier_env *env, int insn_idx, u32 regno, int off, 1077 int bpf_size, enum bpf_access_type t, 1078 int value_regno) 1079 { 1080 struct bpf_verifier_state *state = env->cur_state; 1081 struct bpf_reg_state *regs = cur_regs(env); 1082 struct bpf_reg_state *reg = regs + regno; 1083 int size, err = 0; 1084 1085 size = bpf_size_to_bytes(bpf_size); 1086 if (size < 0) 1087 return size; 1088 1089 /* alignment checks will add in reg->off themselves */ 1090 err = check_ptr_alignment(env, reg, off, size); 1091 if (err) 1092 return err; 1093 1094 /* for access checks, reg->off is just part of off */ 1095 off += reg->off; 1096 1097 if (reg->type == PTR_TO_MAP_VALUE) { 1098 if (t == BPF_WRITE && value_regno >= 0 && 1099 is_pointer_value(env, value_regno)) { 1100 verbose(env, "R%d leaks addr into map\n", value_regno); 1101 return -EACCES; 1102 } 1103 1104 err = check_map_access(env, regno, off, size, false); 1105 if (!err && t == BPF_READ && value_regno >= 0) 1106 mark_reg_unknown(env, regs, value_regno); 1107 1108 } else if (reg->type == PTR_TO_CTX) { 1109 enum bpf_reg_type reg_type = SCALAR_VALUE; 1110 1111 if (t == BPF_WRITE && value_regno >= 0 && 1112 is_pointer_value(env, value_regno)) { 1113 verbose(env, "R%d leaks addr into ctx\n", value_regno); 1114 return -EACCES; 1115 } 1116 /* ctx accesses must be at a fixed offset, so that we can 1117 * determine what type of data were returned. 1118 */ 1119 if (reg->off) { 1120 verbose(env, 1121 "dereference of modified ctx ptr R%d off=%d+%d, ctx+const is allowed, ctx+const+const is not\n", 1122 regno, reg->off, off - reg->off); 1123 return -EACCES; 1124 } 1125 if (!tnum_is_const(reg->var_off) || reg->var_off.value) { 1126 char tn_buf[48]; 1127 1128 tnum_strn(tn_buf, sizeof(tn_buf), reg->var_off); 1129 verbose(env, 1130 "variable ctx access var_off=%s off=%d size=%d", 1131 tn_buf, off, size); 1132 return -EACCES; 1133 } 1134 err = check_ctx_access(env, insn_idx, off, size, t, ®_type); 1135 if (!err && t == BPF_READ && value_regno >= 0) { 1136 /* ctx access returns either a scalar, or a 1137 * PTR_TO_PACKET[_META,_END]. In the latter 1138 * case, we know the offset is zero. 1139 */ 1140 if (reg_type == SCALAR_VALUE) 1141 mark_reg_unknown(env, regs, value_regno); 1142 else 1143 mark_reg_known_zero(env, regs, 1144 value_regno); 1145 regs[value_regno].id = 0; 1146 regs[value_regno].off = 0; 1147 regs[value_regno].range = 0; 1148 regs[value_regno].type = reg_type; 1149 } 1150 1151 } else if (reg->type == PTR_TO_STACK) { 1152 /* stack accesses must be at a fixed offset, so that we can 1153 * determine what type of data were returned. 1154 * See check_stack_read(). 1155 */ 1156 if (!tnum_is_const(reg->var_off)) { 1157 char tn_buf[48]; 1158 1159 tnum_strn(tn_buf, sizeof(tn_buf), reg->var_off); 1160 verbose(env, "variable stack access var_off=%s off=%d size=%d", 1161 tn_buf, off, size); 1162 return -EACCES; 1163 } 1164 off += reg->var_off.value; 1165 if (off >= 0 || off < -MAX_BPF_STACK) { 1166 verbose(env, "invalid stack off=%d size=%d\n", off, 1167 size); 1168 return -EACCES; 1169 } 1170 1171 if (env->prog->aux->stack_depth < -off) 1172 env->prog->aux->stack_depth = -off; 1173 1174 if (t == BPF_WRITE) 1175 err = check_stack_write(env, state, off, size, 1176 value_regno); 1177 else 1178 err = check_stack_read(env, state, off, size, 1179 value_regno); 1180 } else if (reg_is_pkt_pointer(reg)) { 1181 if (t == BPF_WRITE && !may_access_direct_pkt_data(env, NULL, t)) { 1182 verbose(env, "cannot write into packet\n"); 1183 return -EACCES; 1184 } 1185 if (t == BPF_WRITE && value_regno >= 0 && 1186 is_pointer_value(env, value_regno)) { 1187 verbose(env, "R%d leaks addr into packet\n", 1188 value_regno); 1189 return -EACCES; 1190 } 1191 err = check_packet_access(env, regno, off, size, false); 1192 if (!err && t == BPF_READ && value_regno >= 0) 1193 mark_reg_unknown(env, regs, value_regno); 1194 } else { 1195 verbose(env, "R%d invalid mem access '%s'\n", regno, 1196 reg_type_str[reg->type]); 1197 return -EACCES; 1198 } 1199 1200 if (!err && size < BPF_REG_SIZE && value_regno >= 0 && t == BPF_READ && 1201 regs[value_regno].type == SCALAR_VALUE) { 1202 /* b/h/w load zero-extends, mark upper bits as known 0 */ 1203 regs[value_regno].var_off = 1204 tnum_cast(regs[value_regno].var_off, size); 1205 __update_reg_bounds(®s[value_regno]); 1206 } 1207 return err; 1208 } 1209 1210 static int check_xadd(struct bpf_verifier_env *env, int insn_idx, struct bpf_insn *insn) 1211 { 1212 int err; 1213 1214 if ((BPF_SIZE(insn->code) != BPF_W && BPF_SIZE(insn->code) != BPF_DW) || 1215 insn->imm != 0) { 1216 verbose(env, "BPF_XADD uses reserved fields\n"); 1217 return -EINVAL; 1218 } 1219 1220 /* check src1 operand */ 1221 err = check_reg_arg(env, insn->src_reg, SRC_OP); 1222 if (err) 1223 return err; 1224 1225 /* check src2 operand */ 1226 err = check_reg_arg(env, insn->dst_reg, SRC_OP); 1227 if (err) 1228 return err; 1229 1230 if (is_pointer_value(env, insn->src_reg)) { 1231 verbose(env, "R%d leaks addr into mem\n", insn->src_reg); 1232 return -EACCES; 1233 } 1234 1235 /* check whether atomic_add can read the memory */ 1236 err = check_mem_access(env, insn_idx, insn->dst_reg, insn->off, 1237 BPF_SIZE(insn->code), BPF_READ, -1); 1238 if (err) 1239 return err; 1240 1241 /* check whether atomic_add can write into the same memory */ 1242 return check_mem_access(env, insn_idx, insn->dst_reg, insn->off, 1243 BPF_SIZE(insn->code), BPF_WRITE, -1); 1244 } 1245 1246 /* Does this register contain a constant zero? */ 1247 static bool register_is_null(struct bpf_reg_state reg) 1248 { 1249 return reg.type == SCALAR_VALUE && tnum_equals_const(reg.var_off, 0); 1250 } 1251 1252 /* when register 'regno' is passed into function that will read 'access_size' 1253 * bytes from that pointer, make sure that it's within stack boundary 1254 * and all elements of stack are initialized. 1255 * Unlike most pointer bounds-checking functions, this one doesn't take an 1256 * 'off' argument, so it has to add in reg->off itself. 1257 */ 1258 static int check_stack_boundary(struct bpf_verifier_env *env, int regno, 1259 int access_size, bool zero_size_allowed, 1260 struct bpf_call_arg_meta *meta) 1261 { 1262 struct bpf_verifier_state *state = env->cur_state; 1263 struct bpf_reg_state *regs = state->regs; 1264 int off, i, slot, spi; 1265 1266 if (regs[regno].type != PTR_TO_STACK) { 1267 /* Allow zero-byte read from NULL, regardless of pointer type */ 1268 if (zero_size_allowed && access_size == 0 && 1269 register_is_null(regs[regno])) 1270 return 0; 1271 1272 verbose(env, "R%d type=%s expected=%s\n", regno, 1273 reg_type_str[regs[regno].type], 1274 reg_type_str[PTR_TO_STACK]); 1275 return -EACCES; 1276 } 1277 1278 /* Only allow fixed-offset stack reads */ 1279 if (!tnum_is_const(regs[regno].var_off)) { 1280 char tn_buf[48]; 1281 1282 tnum_strn(tn_buf, sizeof(tn_buf), regs[regno].var_off); 1283 verbose(env, "invalid variable stack read R%d var_off=%s\n", 1284 regno, tn_buf); 1285 } 1286 off = regs[regno].off + regs[regno].var_off.value; 1287 if (off >= 0 || off < -MAX_BPF_STACK || off + access_size > 0 || 1288 access_size < 0 || (access_size == 0 && !zero_size_allowed)) { 1289 verbose(env, "invalid stack type R%d off=%d access_size=%d\n", 1290 regno, off, access_size); 1291 return -EACCES; 1292 } 1293 1294 if (env->prog->aux->stack_depth < -off) 1295 env->prog->aux->stack_depth = -off; 1296 1297 if (meta && meta->raw_mode) { 1298 meta->access_size = access_size; 1299 meta->regno = regno; 1300 return 0; 1301 } 1302 1303 for (i = 0; i < access_size; i++) { 1304 slot = -(off + i) - 1; 1305 spi = slot / BPF_REG_SIZE; 1306 if (state->allocated_stack <= slot || 1307 state->stack[spi].slot_type[slot % BPF_REG_SIZE] != 1308 STACK_MISC) { 1309 verbose(env, "invalid indirect read from stack off %d+%d size %d\n", 1310 off, i, access_size); 1311 return -EACCES; 1312 } 1313 } 1314 return 0; 1315 } 1316 1317 static int check_helper_mem_access(struct bpf_verifier_env *env, int regno, 1318 int access_size, bool zero_size_allowed, 1319 struct bpf_call_arg_meta *meta) 1320 { 1321 struct bpf_reg_state *regs = cur_regs(env), *reg = ®s[regno]; 1322 1323 switch (reg->type) { 1324 case PTR_TO_PACKET: 1325 case PTR_TO_PACKET_META: 1326 return check_packet_access(env, regno, reg->off, access_size, 1327 zero_size_allowed); 1328 case PTR_TO_MAP_VALUE: 1329 return check_map_access(env, regno, reg->off, access_size, 1330 zero_size_allowed); 1331 default: /* scalar_value|ptr_to_stack or invalid ptr */ 1332 return check_stack_boundary(env, regno, access_size, 1333 zero_size_allowed, meta); 1334 } 1335 } 1336 1337 static int check_func_arg(struct bpf_verifier_env *env, u32 regno, 1338 enum bpf_arg_type arg_type, 1339 struct bpf_call_arg_meta *meta) 1340 { 1341 struct bpf_reg_state *regs = cur_regs(env), *reg = ®s[regno]; 1342 enum bpf_reg_type expected_type, type = reg->type; 1343 int err = 0; 1344 1345 if (arg_type == ARG_DONTCARE) 1346 return 0; 1347 1348 err = check_reg_arg(env, regno, SRC_OP); 1349 if (err) 1350 return err; 1351 1352 if (arg_type == ARG_ANYTHING) { 1353 if (is_pointer_value(env, regno)) { 1354 verbose(env, "R%d leaks addr into helper function\n", 1355 regno); 1356 return -EACCES; 1357 } 1358 return 0; 1359 } 1360 1361 if (type_is_pkt_pointer(type) && 1362 !may_access_direct_pkt_data(env, meta, BPF_READ)) { 1363 verbose(env, "helper access to the packet is not allowed\n"); 1364 return -EACCES; 1365 } 1366 1367 if (arg_type == ARG_PTR_TO_MAP_KEY || 1368 arg_type == ARG_PTR_TO_MAP_VALUE) { 1369 expected_type = PTR_TO_STACK; 1370 if (!type_is_pkt_pointer(type) && 1371 type != expected_type) 1372 goto err_type; 1373 } else if (arg_type == ARG_CONST_SIZE || 1374 arg_type == ARG_CONST_SIZE_OR_ZERO) { 1375 expected_type = SCALAR_VALUE; 1376 if (type != expected_type) 1377 goto err_type; 1378 } else if (arg_type == ARG_CONST_MAP_PTR) { 1379 expected_type = CONST_PTR_TO_MAP; 1380 if (type != expected_type) 1381 goto err_type; 1382 } else if (arg_type == ARG_PTR_TO_CTX) { 1383 expected_type = PTR_TO_CTX; 1384 if (type != expected_type) 1385 goto err_type; 1386 } else if (arg_type == ARG_PTR_TO_MEM || 1387 arg_type == ARG_PTR_TO_UNINIT_MEM) { 1388 expected_type = PTR_TO_STACK; 1389 /* One exception here. In case function allows for NULL to be 1390 * passed in as argument, it's a SCALAR_VALUE type. Final test 1391 * happens during stack boundary checking. 1392 */ 1393 if (register_is_null(*reg)) 1394 /* final test in check_stack_boundary() */; 1395 else if (!type_is_pkt_pointer(type) && 1396 type != PTR_TO_MAP_VALUE && 1397 type != expected_type) 1398 goto err_type; 1399 meta->raw_mode = arg_type == ARG_PTR_TO_UNINIT_MEM; 1400 } else { 1401 verbose(env, "unsupported arg_type %d\n", arg_type); 1402 return -EFAULT; 1403 } 1404 1405 if (arg_type == ARG_CONST_MAP_PTR) { 1406 /* bpf_map_xxx(map_ptr) call: remember that map_ptr */ 1407 meta->map_ptr = reg->map_ptr; 1408 } else if (arg_type == ARG_PTR_TO_MAP_KEY) { 1409 /* bpf_map_xxx(..., map_ptr, ..., key) call: 1410 * check that [key, key + map->key_size) are within 1411 * stack limits and initialized 1412 */ 1413 if (!meta->map_ptr) { 1414 /* in function declaration map_ptr must come before 1415 * map_key, so that it's verified and known before 1416 * we have to check map_key here. Otherwise it means 1417 * that kernel subsystem misconfigured verifier 1418 */ 1419 verbose(env, "invalid map_ptr to access map->key\n"); 1420 return -EACCES; 1421 } 1422 if (type_is_pkt_pointer(type)) 1423 err = check_packet_access(env, regno, reg->off, 1424 meta->map_ptr->key_size, 1425 false); 1426 else 1427 err = check_stack_boundary(env, regno, 1428 meta->map_ptr->key_size, 1429 false, NULL); 1430 } else if (arg_type == ARG_PTR_TO_MAP_VALUE) { 1431 /* bpf_map_xxx(..., map_ptr, ..., value) call: 1432 * check [value, value + map->value_size) validity 1433 */ 1434 if (!meta->map_ptr) { 1435 /* kernel subsystem misconfigured verifier */ 1436 verbose(env, "invalid map_ptr to access map->value\n"); 1437 return -EACCES; 1438 } 1439 if (type_is_pkt_pointer(type)) 1440 err = check_packet_access(env, regno, reg->off, 1441 meta->map_ptr->value_size, 1442 false); 1443 else 1444 err = check_stack_boundary(env, regno, 1445 meta->map_ptr->value_size, 1446 false, NULL); 1447 } else if (arg_type == ARG_CONST_SIZE || 1448 arg_type == ARG_CONST_SIZE_OR_ZERO) { 1449 bool zero_size_allowed = (arg_type == ARG_CONST_SIZE_OR_ZERO); 1450 1451 /* bpf_xxx(..., buf, len) call will access 'len' bytes 1452 * from stack pointer 'buf'. Check it 1453 * note: regno == len, regno - 1 == buf 1454 */ 1455 if (regno == 0) { 1456 /* kernel subsystem misconfigured verifier */ 1457 verbose(env, 1458 "ARG_CONST_SIZE cannot be first argument\n"); 1459 return -EACCES; 1460 } 1461 1462 /* The register is SCALAR_VALUE; the access check 1463 * happens using its boundaries. 1464 */ 1465 1466 if (!tnum_is_const(reg->var_off)) 1467 /* For unprivileged variable accesses, disable raw 1468 * mode so that the program is required to 1469 * initialize all the memory that the helper could 1470 * just partially fill up. 1471 */ 1472 meta = NULL; 1473 1474 if (reg->smin_value < 0) { 1475 verbose(env, "R%d min value is negative, either use unsigned or 'var &= const'\n", 1476 regno); 1477 return -EACCES; 1478 } 1479 1480 if (reg->umin_value == 0) { 1481 err = check_helper_mem_access(env, regno - 1, 0, 1482 zero_size_allowed, 1483 meta); 1484 if (err) 1485 return err; 1486 } 1487 1488 if (reg->umax_value >= BPF_MAX_VAR_SIZ) { 1489 verbose(env, "R%d unbounded memory access, use 'var &= const' or 'if (var < const)'\n", 1490 regno); 1491 return -EACCES; 1492 } 1493 err = check_helper_mem_access(env, regno - 1, 1494 reg->umax_value, 1495 zero_size_allowed, meta); 1496 } 1497 1498 return err; 1499 err_type: 1500 verbose(env, "R%d type=%s expected=%s\n", regno, 1501 reg_type_str[type], reg_type_str[expected_type]); 1502 return -EACCES; 1503 } 1504 1505 static int check_map_func_compatibility(struct bpf_verifier_env *env, 1506 struct bpf_map *map, int func_id) 1507 { 1508 if (!map) 1509 return 0; 1510 1511 /* We need a two way check, first is from map perspective ... */ 1512 switch (map->map_type) { 1513 case BPF_MAP_TYPE_PROG_ARRAY: 1514 if (func_id != BPF_FUNC_tail_call) 1515 goto error; 1516 break; 1517 case BPF_MAP_TYPE_PERF_EVENT_ARRAY: 1518 if (func_id != BPF_FUNC_perf_event_read && 1519 func_id != BPF_FUNC_perf_event_output && 1520 func_id != BPF_FUNC_perf_event_read_value) 1521 goto error; 1522 break; 1523 case BPF_MAP_TYPE_STACK_TRACE: 1524 if (func_id != BPF_FUNC_get_stackid) 1525 goto error; 1526 break; 1527 case BPF_MAP_TYPE_CGROUP_ARRAY: 1528 if (func_id != BPF_FUNC_skb_under_cgroup && 1529 func_id != BPF_FUNC_current_task_under_cgroup) 1530 goto error; 1531 break; 1532 /* devmap returns a pointer to a live net_device ifindex that we cannot 1533 * allow to be modified from bpf side. So do not allow lookup elements 1534 * for now. 1535 */ 1536 case BPF_MAP_TYPE_DEVMAP: 1537 if (func_id != BPF_FUNC_redirect_map) 1538 goto error; 1539 break; 1540 /* Restrict bpf side of cpumap, open when use-cases appear */ 1541 case BPF_MAP_TYPE_CPUMAP: 1542 if (func_id != BPF_FUNC_redirect_map) 1543 goto error; 1544 break; 1545 case BPF_MAP_TYPE_ARRAY_OF_MAPS: 1546 case BPF_MAP_TYPE_HASH_OF_MAPS: 1547 if (func_id != BPF_FUNC_map_lookup_elem) 1548 goto error; 1549 break; 1550 case BPF_MAP_TYPE_SOCKMAP: 1551 if (func_id != BPF_FUNC_sk_redirect_map && 1552 func_id != BPF_FUNC_sock_map_update && 1553 func_id != BPF_FUNC_map_delete_elem) 1554 goto error; 1555 break; 1556 default: 1557 break; 1558 } 1559 1560 /* ... and second from the function itself. */ 1561 switch (func_id) { 1562 case BPF_FUNC_tail_call: 1563 if (map->map_type != BPF_MAP_TYPE_PROG_ARRAY) 1564 goto error; 1565 break; 1566 case BPF_FUNC_perf_event_read: 1567 case BPF_FUNC_perf_event_output: 1568 case BPF_FUNC_perf_event_read_value: 1569 if (map->map_type != BPF_MAP_TYPE_PERF_EVENT_ARRAY) 1570 goto error; 1571 break; 1572 case BPF_FUNC_get_stackid: 1573 if (map->map_type != BPF_MAP_TYPE_STACK_TRACE) 1574 goto error; 1575 break; 1576 case BPF_FUNC_current_task_under_cgroup: 1577 case BPF_FUNC_skb_under_cgroup: 1578 if (map->map_type != BPF_MAP_TYPE_CGROUP_ARRAY) 1579 goto error; 1580 break; 1581 case BPF_FUNC_redirect_map: 1582 if (map->map_type != BPF_MAP_TYPE_DEVMAP && 1583 map->map_type != BPF_MAP_TYPE_CPUMAP) 1584 goto error; 1585 break; 1586 case BPF_FUNC_sk_redirect_map: 1587 if (map->map_type != BPF_MAP_TYPE_SOCKMAP) 1588 goto error; 1589 break; 1590 case BPF_FUNC_sock_map_update: 1591 if (map->map_type != BPF_MAP_TYPE_SOCKMAP) 1592 goto error; 1593 break; 1594 default: 1595 break; 1596 } 1597 1598 return 0; 1599 error: 1600 verbose(env, "cannot pass map_type %d into func %s#%d\n", 1601 map->map_type, func_id_name(func_id), func_id); 1602 return -EINVAL; 1603 } 1604 1605 static int check_raw_mode(const struct bpf_func_proto *fn) 1606 { 1607 int count = 0; 1608 1609 if (fn->arg1_type == ARG_PTR_TO_UNINIT_MEM) 1610 count++; 1611 if (fn->arg2_type == ARG_PTR_TO_UNINIT_MEM) 1612 count++; 1613 if (fn->arg3_type == ARG_PTR_TO_UNINIT_MEM) 1614 count++; 1615 if (fn->arg4_type == ARG_PTR_TO_UNINIT_MEM) 1616 count++; 1617 if (fn->arg5_type == ARG_PTR_TO_UNINIT_MEM) 1618 count++; 1619 1620 return count > 1 ? -EINVAL : 0; 1621 } 1622 1623 /* Packet data might have moved, any old PTR_TO_PACKET[_META,_END] 1624 * are now invalid, so turn them into unknown SCALAR_VALUE. 1625 */ 1626 static void clear_all_pkt_pointers(struct bpf_verifier_env *env) 1627 { 1628 struct bpf_verifier_state *state = env->cur_state; 1629 struct bpf_reg_state *regs = state->regs, *reg; 1630 int i; 1631 1632 for (i = 0; i < MAX_BPF_REG; i++) 1633 if (reg_is_pkt_pointer_any(®s[i])) 1634 mark_reg_unknown(env, regs, i); 1635 1636 for (i = 0; i < state->allocated_stack / BPF_REG_SIZE; i++) { 1637 if (state->stack[i].slot_type[0] != STACK_SPILL) 1638 continue; 1639 reg = &state->stack[i].spilled_ptr; 1640 if (reg_is_pkt_pointer_any(reg)) 1641 __mark_reg_unknown(reg); 1642 } 1643 } 1644 1645 static int check_call(struct bpf_verifier_env *env, int func_id, int insn_idx) 1646 { 1647 const struct bpf_func_proto *fn = NULL; 1648 struct bpf_reg_state *regs; 1649 struct bpf_call_arg_meta meta; 1650 bool changes_data; 1651 int i, err; 1652 1653 /* find function prototype */ 1654 if (func_id < 0 || func_id >= __BPF_FUNC_MAX_ID) { 1655 verbose(env, "invalid func %s#%d\n", func_id_name(func_id), 1656 func_id); 1657 return -EINVAL; 1658 } 1659 1660 if (env->ops->get_func_proto) 1661 fn = env->ops->get_func_proto(func_id); 1662 1663 if (!fn) { 1664 verbose(env, "unknown func %s#%d\n", func_id_name(func_id), 1665 func_id); 1666 return -EINVAL; 1667 } 1668 1669 /* eBPF programs must be GPL compatible to use GPL-ed functions */ 1670 if (!env->prog->gpl_compatible && fn->gpl_only) { 1671 verbose(env, "cannot call GPL only function from proprietary program\n"); 1672 return -EINVAL; 1673 } 1674 1675 changes_data = bpf_helper_changes_pkt_data(fn->func); 1676 1677 memset(&meta, 0, sizeof(meta)); 1678 meta.pkt_access = fn->pkt_access; 1679 1680 /* We only support one arg being in raw mode at the moment, which 1681 * is sufficient for the helper functions we have right now. 1682 */ 1683 err = check_raw_mode(fn); 1684 if (err) { 1685 verbose(env, "kernel subsystem misconfigured func %s#%d\n", 1686 func_id_name(func_id), func_id); 1687 return err; 1688 } 1689 1690 /* check args */ 1691 err = check_func_arg(env, BPF_REG_1, fn->arg1_type, &meta); 1692 if (err) 1693 return err; 1694 err = check_func_arg(env, BPF_REG_2, fn->arg2_type, &meta); 1695 if (err) 1696 return err; 1697 err = check_func_arg(env, BPF_REG_3, fn->arg3_type, &meta); 1698 if (err) 1699 return err; 1700 err = check_func_arg(env, BPF_REG_4, fn->arg4_type, &meta); 1701 if (err) 1702 return err; 1703 err = check_func_arg(env, BPF_REG_5, fn->arg5_type, &meta); 1704 if (err) 1705 return err; 1706 1707 /* Mark slots with STACK_MISC in case of raw mode, stack offset 1708 * is inferred from register state. 1709 */ 1710 for (i = 0; i < meta.access_size; i++) { 1711 err = check_mem_access(env, insn_idx, meta.regno, i, BPF_B, BPF_WRITE, -1); 1712 if (err) 1713 return err; 1714 } 1715 1716 regs = cur_regs(env); 1717 /* reset caller saved regs */ 1718 for (i = 0; i < CALLER_SAVED_REGS; i++) { 1719 mark_reg_not_init(env, regs, caller_saved[i]); 1720 check_reg_arg(env, caller_saved[i], DST_OP_NO_MARK); 1721 } 1722 1723 /* update return register (already marked as written above) */ 1724 if (fn->ret_type == RET_INTEGER) { 1725 /* sets type to SCALAR_VALUE */ 1726 mark_reg_unknown(env, regs, BPF_REG_0); 1727 } else if (fn->ret_type == RET_VOID) { 1728 regs[BPF_REG_0].type = NOT_INIT; 1729 } else if (fn->ret_type == RET_PTR_TO_MAP_VALUE_OR_NULL) { 1730 struct bpf_insn_aux_data *insn_aux; 1731 1732 regs[BPF_REG_0].type = PTR_TO_MAP_VALUE_OR_NULL; 1733 /* There is no offset yet applied, variable or fixed */ 1734 mark_reg_known_zero(env, regs, BPF_REG_0); 1735 regs[BPF_REG_0].off = 0; 1736 /* remember map_ptr, so that check_map_access() 1737 * can check 'value_size' boundary of memory access 1738 * to map element returned from bpf_map_lookup_elem() 1739 */ 1740 if (meta.map_ptr == NULL) { 1741 verbose(env, 1742 "kernel subsystem misconfigured verifier\n"); 1743 return -EINVAL; 1744 } 1745 regs[BPF_REG_0].map_ptr = meta.map_ptr; 1746 regs[BPF_REG_0].id = ++env->id_gen; 1747 insn_aux = &env->insn_aux_data[insn_idx]; 1748 if (!insn_aux->map_ptr) 1749 insn_aux->map_ptr = meta.map_ptr; 1750 else if (insn_aux->map_ptr != meta.map_ptr) 1751 insn_aux->map_ptr = BPF_MAP_PTR_POISON; 1752 } else { 1753 verbose(env, "unknown return type %d of func %s#%d\n", 1754 fn->ret_type, func_id_name(func_id), func_id); 1755 return -EINVAL; 1756 } 1757 1758 err = check_map_func_compatibility(env, meta.map_ptr, func_id); 1759 if (err) 1760 return err; 1761 1762 if (changes_data) 1763 clear_all_pkt_pointers(env); 1764 return 0; 1765 } 1766 1767 static void coerce_reg_to_32(struct bpf_reg_state *reg) 1768 { 1769 /* clear high 32 bits */ 1770 reg->var_off = tnum_cast(reg->var_off, 4); 1771 /* Update bounds */ 1772 __update_reg_bounds(reg); 1773 } 1774 1775 static bool signed_add_overflows(s64 a, s64 b) 1776 { 1777 /* Do the add in u64, where overflow is well-defined */ 1778 s64 res = (s64)((u64)a + (u64)b); 1779 1780 if (b < 0) 1781 return res > a; 1782 return res < a; 1783 } 1784 1785 static bool signed_sub_overflows(s64 a, s64 b) 1786 { 1787 /* Do the sub in u64, where overflow is well-defined */ 1788 s64 res = (s64)((u64)a - (u64)b); 1789 1790 if (b < 0) 1791 return res < a; 1792 return res > a; 1793 } 1794 1795 /* Handles arithmetic on a pointer and a scalar: computes new min/max and var_off. 1796 * Caller should also handle BPF_MOV case separately. 1797 * If we return -EACCES, caller may want to try again treating pointer as a 1798 * scalar. So we only emit a diagnostic if !env->allow_ptr_leaks. 1799 */ 1800 static int adjust_ptr_min_max_vals(struct bpf_verifier_env *env, 1801 struct bpf_insn *insn, 1802 const struct bpf_reg_state *ptr_reg, 1803 const struct bpf_reg_state *off_reg) 1804 { 1805 struct bpf_reg_state *regs = cur_regs(env), *dst_reg; 1806 bool known = tnum_is_const(off_reg->var_off); 1807 s64 smin_val = off_reg->smin_value, smax_val = off_reg->smax_value, 1808 smin_ptr = ptr_reg->smin_value, smax_ptr = ptr_reg->smax_value; 1809 u64 umin_val = off_reg->umin_value, umax_val = off_reg->umax_value, 1810 umin_ptr = ptr_reg->umin_value, umax_ptr = ptr_reg->umax_value; 1811 u8 opcode = BPF_OP(insn->code); 1812 u32 dst = insn->dst_reg; 1813 1814 dst_reg = ®s[dst]; 1815 1816 if (WARN_ON_ONCE(known && (smin_val != smax_val))) { 1817 print_verifier_state(env, env->cur_state); 1818 verbose(env, 1819 "verifier internal error: known but bad sbounds\n"); 1820 return -EINVAL; 1821 } 1822 if (WARN_ON_ONCE(known && (umin_val != umax_val))) { 1823 print_verifier_state(env, env->cur_state); 1824 verbose(env, 1825 "verifier internal error: known but bad ubounds\n"); 1826 return -EINVAL; 1827 } 1828 1829 if (BPF_CLASS(insn->code) != BPF_ALU64) { 1830 /* 32-bit ALU ops on pointers produce (meaningless) scalars */ 1831 if (!env->allow_ptr_leaks) 1832 verbose(env, 1833 "R%d 32-bit pointer arithmetic prohibited\n", 1834 dst); 1835 return -EACCES; 1836 } 1837 1838 if (ptr_reg->type == PTR_TO_MAP_VALUE_OR_NULL) { 1839 if (!env->allow_ptr_leaks) 1840 verbose(env, "R%d pointer arithmetic on PTR_TO_MAP_VALUE_OR_NULL prohibited, null-check it first\n", 1841 dst); 1842 return -EACCES; 1843 } 1844 if (ptr_reg->type == CONST_PTR_TO_MAP) { 1845 if (!env->allow_ptr_leaks) 1846 verbose(env, "R%d pointer arithmetic on CONST_PTR_TO_MAP prohibited\n", 1847 dst); 1848 return -EACCES; 1849 } 1850 if (ptr_reg->type == PTR_TO_PACKET_END) { 1851 if (!env->allow_ptr_leaks) 1852 verbose(env, "R%d pointer arithmetic on PTR_TO_PACKET_END prohibited\n", 1853 dst); 1854 return -EACCES; 1855 } 1856 1857 /* In case of 'scalar += pointer', dst_reg inherits pointer type and id. 1858 * The id may be overwritten later if we create a new variable offset. 1859 */ 1860 dst_reg->type = ptr_reg->type; 1861 dst_reg->id = ptr_reg->id; 1862 1863 switch (opcode) { 1864 case BPF_ADD: 1865 /* We can take a fixed offset as long as it doesn't overflow 1866 * the s32 'off' field 1867 */ 1868 if (known && (ptr_reg->off + smin_val == 1869 (s64)(s32)(ptr_reg->off + smin_val))) { 1870 /* pointer += K. Accumulate it into fixed offset */ 1871 dst_reg->smin_value = smin_ptr; 1872 dst_reg->smax_value = smax_ptr; 1873 dst_reg->umin_value = umin_ptr; 1874 dst_reg->umax_value = umax_ptr; 1875 dst_reg->var_off = ptr_reg->var_off; 1876 dst_reg->off = ptr_reg->off + smin_val; 1877 dst_reg->range = ptr_reg->range; 1878 break; 1879 } 1880 /* A new variable offset is created. Note that off_reg->off 1881 * == 0, since it's a scalar. 1882 * dst_reg gets the pointer type and since some positive 1883 * integer value was added to the pointer, give it a new 'id' 1884 * if it's a PTR_TO_PACKET. 1885 * this creates a new 'base' pointer, off_reg (variable) gets 1886 * added into the variable offset, and we copy the fixed offset 1887 * from ptr_reg. 1888 */ 1889 if (signed_add_overflows(smin_ptr, smin_val) || 1890 signed_add_overflows(smax_ptr, smax_val)) { 1891 dst_reg->smin_value = S64_MIN; 1892 dst_reg->smax_value = S64_MAX; 1893 } else { 1894 dst_reg->smin_value = smin_ptr + smin_val; 1895 dst_reg->smax_value = smax_ptr + smax_val; 1896 } 1897 if (umin_ptr + umin_val < umin_ptr || 1898 umax_ptr + umax_val < umax_ptr) { 1899 dst_reg->umin_value = 0; 1900 dst_reg->umax_value = U64_MAX; 1901 } else { 1902 dst_reg->umin_value = umin_ptr + umin_val; 1903 dst_reg->umax_value = umax_ptr + umax_val; 1904 } 1905 dst_reg->var_off = tnum_add(ptr_reg->var_off, off_reg->var_off); 1906 dst_reg->off = ptr_reg->off; 1907 if (reg_is_pkt_pointer(ptr_reg)) { 1908 dst_reg->id = ++env->id_gen; 1909 /* something was added to pkt_ptr, set range to zero */ 1910 dst_reg->range = 0; 1911 } 1912 break; 1913 case BPF_SUB: 1914 if (dst_reg == off_reg) { 1915 /* scalar -= pointer. Creates an unknown scalar */ 1916 if (!env->allow_ptr_leaks) 1917 verbose(env, "R%d tried to subtract pointer from scalar\n", 1918 dst); 1919 return -EACCES; 1920 } 1921 /* We don't allow subtraction from FP, because (according to 1922 * test_verifier.c test "invalid fp arithmetic", JITs might not 1923 * be able to deal with it. 1924 */ 1925 if (ptr_reg->type == PTR_TO_STACK) { 1926 if (!env->allow_ptr_leaks) 1927 verbose(env, "R%d subtraction from stack pointer prohibited\n", 1928 dst); 1929 return -EACCES; 1930 } 1931 if (known && (ptr_reg->off - smin_val == 1932 (s64)(s32)(ptr_reg->off - smin_val))) { 1933 /* pointer -= K. Subtract it from fixed offset */ 1934 dst_reg->smin_value = smin_ptr; 1935 dst_reg->smax_value = smax_ptr; 1936 dst_reg->umin_value = umin_ptr; 1937 dst_reg->umax_value = umax_ptr; 1938 dst_reg->var_off = ptr_reg->var_off; 1939 dst_reg->id = ptr_reg->id; 1940 dst_reg->off = ptr_reg->off - smin_val; 1941 dst_reg->range = ptr_reg->range; 1942 break; 1943 } 1944 /* A new variable offset is created. If the subtrahend is known 1945 * nonnegative, then any reg->range we had before is still good. 1946 */ 1947 if (signed_sub_overflows(smin_ptr, smax_val) || 1948 signed_sub_overflows(smax_ptr, smin_val)) { 1949 /* Overflow possible, we know nothing */ 1950 dst_reg->smin_value = S64_MIN; 1951 dst_reg->smax_value = S64_MAX; 1952 } else { 1953 dst_reg->smin_value = smin_ptr - smax_val; 1954 dst_reg->smax_value = smax_ptr - smin_val; 1955 } 1956 if (umin_ptr < umax_val) { 1957 /* Overflow possible, we know nothing */ 1958 dst_reg->umin_value = 0; 1959 dst_reg->umax_value = U64_MAX; 1960 } else { 1961 /* Cannot overflow (as long as bounds are consistent) */ 1962 dst_reg->umin_value = umin_ptr - umax_val; 1963 dst_reg->umax_value = umax_ptr - umin_val; 1964 } 1965 dst_reg->var_off = tnum_sub(ptr_reg->var_off, off_reg->var_off); 1966 dst_reg->off = ptr_reg->off; 1967 if (reg_is_pkt_pointer(ptr_reg)) { 1968 dst_reg->id = ++env->id_gen; 1969 /* something was added to pkt_ptr, set range to zero */ 1970 if (smin_val < 0) 1971 dst_reg->range = 0; 1972 } 1973 break; 1974 case BPF_AND: 1975 case BPF_OR: 1976 case BPF_XOR: 1977 /* bitwise ops on pointers are troublesome, prohibit for now. 1978 * (However, in principle we could allow some cases, e.g. 1979 * ptr &= ~3 which would reduce min_value by 3.) 1980 */ 1981 if (!env->allow_ptr_leaks) 1982 verbose(env, "R%d bitwise operator %s on pointer prohibited\n", 1983 dst, bpf_alu_string[opcode >> 4]); 1984 return -EACCES; 1985 default: 1986 /* other operators (e.g. MUL,LSH) produce non-pointer results */ 1987 if (!env->allow_ptr_leaks) 1988 verbose(env, "R%d pointer arithmetic with %s operator prohibited\n", 1989 dst, bpf_alu_string[opcode >> 4]); 1990 return -EACCES; 1991 } 1992 1993 __update_reg_bounds(dst_reg); 1994 __reg_deduce_bounds(dst_reg); 1995 __reg_bound_offset(dst_reg); 1996 return 0; 1997 } 1998 1999 static int adjust_scalar_min_max_vals(struct bpf_verifier_env *env, 2000 struct bpf_insn *insn, 2001 struct bpf_reg_state *dst_reg, 2002 struct bpf_reg_state src_reg) 2003 { 2004 struct bpf_reg_state *regs = cur_regs(env); 2005 u8 opcode = BPF_OP(insn->code); 2006 bool src_known, dst_known; 2007 s64 smin_val, smax_val; 2008 u64 umin_val, umax_val; 2009 2010 if (BPF_CLASS(insn->code) != BPF_ALU64) { 2011 /* 32-bit ALU ops are (32,32)->64 */ 2012 coerce_reg_to_32(dst_reg); 2013 coerce_reg_to_32(&src_reg); 2014 } 2015 smin_val = src_reg.smin_value; 2016 smax_val = src_reg.smax_value; 2017 umin_val = src_reg.umin_value; 2018 umax_val = src_reg.umax_value; 2019 src_known = tnum_is_const(src_reg.var_off); 2020 dst_known = tnum_is_const(dst_reg->var_off); 2021 2022 switch (opcode) { 2023 case BPF_ADD: 2024 if (signed_add_overflows(dst_reg->smin_value, smin_val) || 2025 signed_add_overflows(dst_reg->smax_value, smax_val)) { 2026 dst_reg->smin_value = S64_MIN; 2027 dst_reg->smax_value = S64_MAX; 2028 } else { 2029 dst_reg->smin_value += smin_val; 2030 dst_reg->smax_value += smax_val; 2031 } 2032 if (dst_reg->umin_value + umin_val < umin_val || 2033 dst_reg->umax_value + umax_val < umax_val) { 2034 dst_reg->umin_value = 0; 2035 dst_reg->umax_value = U64_MAX; 2036 } else { 2037 dst_reg->umin_value += umin_val; 2038 dst_reg->umax_value += umax_val; 2039 } 2040 dst_reg->var_off = tnum_add(dst_reg->var_off, src_reg.var_off); 2041 break; 2042 case BPF_SUB: 2043 if (signed_sub_overflows(dst_reg->smin_value, smax_val) || 2044 signed_sub_overflows(dst_reg->smax_value, smin_val)) { 2045 /* Overflow possible, we know nothing */ 2046 dst_reg->smin_value = S64_MIN; 2047 dst_reg->smax_value = S64_MAX; 2048 } else { 2049 dst_reg->smin_value -= smax_val; 2050 dst_reg->smax_value -= smin_val; 2051 } 2052 if (dst_reg->umin_value < umax_val) { 2053 /* Overflow possible, we know nothing */ 2054 dst_reg->umin_value = 0; 2055 dst_reg->umax_value = U64_MAX; 2056 } else { 2057 /* Cannot overflow (as long as bounds are consistent) */ 2058 dst_reg->umin_value -= umax_val; 2059 dst_reg->umax_value -= umin_val; 2060 } 2061 dst_reg->var_off = tnum_sub(dst_reg->var_off, src_reg.var_off); 2062 break; 2063 case BPF_MUL: 2064 dst_reg->var_off = tnum_mul(dst_reg->var_off, src_reg.var_off); 2065 if (smin_val < 0 || dst_reg->smin_value < 0) { 2066 /* Ain't nobody got time to multiply that sign */ 2067 __mark_reg_unbounded(dst_reg); 2068 __update_reg_bounds(dst_reg); 2069 break; 2070 } 2071 /* Both values are positive, so we can work with unsigned and 2072 * copy the result to signed (unless it exceeds S64_MAX). 2073 */ 2074 if (umax_val > U32_MAX || dst_reg->umax_value > U32_MAX) { 2075 /* Potential overflow, we know nothing */ 2076 __mark_reg_unbounded(dst_reg); 2077 /* (except what we can learn from the var_off) */ 2078 __update_reg_bounds(dst_reg); 2079 break; 2080 } 2081 dst_reg->umin_value *= umin_val; 2082 dst_reg->umax_value *= umax_val; 2083 if (dst_reg->umax_value > S64_MAX) { 2084 /* Overflow possible, we know nothing */ 2085 dst_reg->smin_value = S64_MIN; 2086 dst_reg->smax_value = S64_MAX; 2087 } else { 2088 dst_reg->smin_value = dst_reg->umin_value; 2089 dst_reg->smax_value = dst_reg->umax_value; 2090 } 2091 break; 2092 case BPF_AND: 2093 if (src_known && dst_known) { 2094 __mark_reg_known(dst_reg, dst_reg->var_off.value & 2095 src_reg.var_off.value); 2096 break; 2097 } 2098 /* We get our minimum from the var_off, since that's inherently 2099 * bitwise. Our maximum is the minimum of the operands' maxima. 2100 */ 2101 dst_reg->var_off = tnum_and(dst_reg->var_off, src_reg.var_off); 2102 dst_reg->umin_value = dst_reg->var_off.value; 2103 dst_reg->umax_value = min(dst_reg->umax_value, umax_val); 2104 if (dst_reg->smin_value < 0 || smin_val < 0) { 2105 /* Lose signed bounds when ANDing negative numbers, 2106 * ain't nobody got time for that. 2107 */ 2108 dst_reg->smin_value = S64_MIN; 2109 dst_reg->smax_value = S64_MAX; 2110 } else { 2111 /* ANDing two positives gives a positive, so safe to 2112 * cast result into s64. 2113 */ 2114 dst_reg->smin_value = dst_reg->umin_value; 2115 dst_reg->smax_value = dst_reg->umax_value; 2116 } 2117 /* We may learn something more from the var_off */ 2118 __update_reg_bounds(dst_reg); 2119 break; 2120 case BPF_OR: 2121 if (src_known && dst_known) { 2122 __mark_reg_known(dst_reg, dst_reg->var_off.value | 2123 src_reg.var_off.value); 2124 break; 2125 } 2126 /* We get our maximum from the var_off, and our minimum is the 2127 * maximum of the operands' minima 2128 */ 2129 dst_reg->var_off = tnum_or(dst_reg->var_off, src_reg.var_off); 2130 dst_reg->umin_value = max(dst_reg->umin_value, umin_val); 2131 dst_reg->umax_value = dst_reg->var_off.value | 2132 dst_reg->var_off.mask; 2133 if (dst_reg->smin_value < 0 || smin_val < 0) { 2134 /* Lose signed bounds when ORing negative numbers, 2135 * ain't nobody got time for that. 2136 */ 2137 dst_reg->smin_value = S64_MIN; 2138 dst_reg->smax_value = S64_MAX; 2139 } else { 2140 /* ORing two positives gives a positive, so safe to 2141 * cast result into s64. 2142 */ 2143 dst_reg->smin_value = dst_reg->umin_value; 2144 dst_reg->smax_value = dst_reg->umax_value; 2145 } 2146 /* We may learn something more from the var_off */ 2147 __update_reg_bounds(dst_reg); 2148 break; 2149 case BPF_LSH: 2150 if (umax_val > 63) { 2151 /* Shifts greater than 63 are undefined. This includes 2152 * shifts by a negative number. 2153 */ 2154 mark_reg_unknown(env, regs, insn->dst_reg); 2155 break; 2156 } 2157 /* We lose all sign bit information (except what we can pick 2158 * up from var_off) 2159 */ 2160 dst_reg->smin_value = S64_MIN; 2161 dst_reg->smax_value = S64_MAX; 2162 /* If we might shift our top bit out, then we know nothing */ 2163 if (dst_reg->umax_value > 1ULL << (63 - umax_val)) { 2164 dst_reg->umin_value = 0; 2165 dst_reg->umax_value = U64_MAX; 2166 } else { 2167 dst_reg->umin_value <<= umin_val; 2168 dst_reg->umax_value <<= umax_val; 2169 } 2170 if (src_known) 2171 dst_reg->var_off = tnum_lshift(dst_reg->var_off, umin_val); 2172 else 2173 dst_reg->var_off = tnum_lshift(tnum_unknown, umin_val); 2174 /* We may learn something more from the var_off */ 2175 __update_reg_bounds(dst_reg); 2176 break; 2177 case BPF_RSH: 2178 if (umax_val > 63) { 2179 /* Shifts greater than 63 are undefined. This includes 2180 * shifts by a negative number. 2181 */ 2182 mark_reg_unknown(env, regs, insn->dst_reg); 2183 break; 2184 } 2185 /* BPF_RSH is an unsigned shift, so make the appropriate casts */ 2186 if (dst_reg->smin_value < 0) { 2187 if (umin_val) { 2188 /* Sign bit will be cleared */ 2189 dst_reg->smin_value = 0; 2190 } else { 2191 /* Lost sign bit information */ 2192 dst_reg->smin_value = S64_MIN; 2193 dst_reg->smax_value = S64_MAX; 2194 } 2195 } else { 2196 dst_reg->smin_value = 2197 (u64)(dst_reg->smin_value) >> umax_val; 2198 } 2199 if (src_known) 2200 dst_reg->var_off = tnum_rshift(dst_reg->var_off, 2201 umin_val); 2202 else 2203 dst_reg->var_off = tnum_rshift(tnum_unknown, umin_val); 2204 dst_reg->umin_value >>= umax_val; 2205 dst_reg->umax_value >>= umin_val; 2206 /* We may learn something more from the var_off */ 2207 __update_reg_bounds(dst_reg); 2208 break; 2209 default: 2210 mark_reg_unknown(env, regs, insn->dst_reg); 2211 break; 2212 } 2213 2214 __reg_deduce_bounds(dst_reg); 2215 __reg_bound_offset(dst_reg); 2216 return 0; 2217 } 2218 2219 /* Handles ALU ops other than BPF_END, BPF_NEG and BPF_MOV: computes new min/max 2220 * and var_off. 2221 */ 2222 static int adjust_reg_min_max_vals(struct bpf_verifier_env *env, 2223 struct bpf_insn *insn) 2224 { 2225 struct bpf_reg_state *regs = cur_regs(env), *dst_reg, *src_reg; 2226 struct bpf_reg_state *ptr_reg = NULL, off_reg = {0}; 2227 u8 opcode = BPF_OP(insn->code); 2228 int rc; 2229 2230 dst_reg = ®s[insn->dst_reg]; 2231 src_reg = NULL; 2232 if (dst_reg->type != SCALAR_VALUE) 2233 ptr_reg = dst_reg; 2234 if (BPF_SRC(insn->code) == BPF_X) { 2235 src_reg = ®s[insn->src_reg]; 2236 if (src_reg->type != SCALAR_VALUE) { 2237 if (dst_reg->type != SCALAR_VALUE) { 2238 /* Combining two pointers by any ALU op yields 2239 * an arbitrary scalar. 2240 */ 2241 if (!env->allow_ptr_leaks) { 2242 verbose(env, "R%d pointer %s pointer prohibited\n", 2243 insn->dst_reg, 2244 bpf_alu_string[opcode >> 4]); 2245 return -EACCES; 2246 } 2247 mark_reg_unknown(env, regs, insn->dst_reg); 2248 return 0; 2249 } else { 2250 /* scalar += pointer 2251 * This is legal, but we have to reverse our 2252 * src/dest handling in computing the range 2253 */ 2254 rc = adjust_ptr_min_max_vals(env, insn, 2255 src_reg, dst_reg); 2256 if (rc == -EACCES && env->allow_ptr_leaks) { 2257 /* scalar += unknown scalar */ 2258 __mark_reg_unknown(&off_reg); 2259 return adjust_scalar_min_max_vals( 2260 env, insn, 2261 dst_reg, off_reg); 2262 } 2263 return rc; 2264 } 2265 } else if (ptr_reg) { 2266 /* pointer += scalar */ 2267 rc = adjust_ptr_min_max_vals(env, insn, 2268 dst_reg, src_reg); 2269 if (rc == -EACCES && env->allow_ptr_leaks) { 2270 /* unknown scalar += scalar */ 2271 __mark_reg_unknown(dst_reg); 2272 return adjust_scalar_min_max_vals( 2273 env, insn, dst_reg, *src_reg); 2274 } 2275 return rc; 2276 } 2277 } else { 2278 /* Pretend the src is a reg with a known value, since we only 2279 * need to be able to read from this state. 2280 */ 2281 off_reg.type = SCALAR_VALUE; 2282 __mark_reg_known(&off_reg, insn->imm); 2283 src_reg = &off_reg; 2284 if (ptr_reg) { /* pointer += K */ 2285 rc = adjust_ptr_min_max_vals(env, insn, 2286 ptr_reg, src_reg); 2287 if (rc == -EACCES && env->allow_ptr_leaks) { 2288 /* unknown scalar += K */ 2289 __mark_reg_unknown(dst_reg); 2290 return adjust_scalar_min_max_vals( 2291 env, insn, dst_reg, off_reg); 2292 } 2293 return rc; 2294 } 2295 } 2296 2297 /* Got here implies adding two SCALAR_VALUEs */ 2298 if (WARN_ON_ONCE(ptr_reg)) { 2299 print_verifier_state(env, env->cur_state); 2300 verbose(env, "verifier internal error: unexpected ptr_reg\n"); 2301 return -EINVAL; 2302 } 2303 if (WARN_ON(!src_reg)) { 2304 print_verifier_state(env, env->cur_state); 2305 verbose(env, "verifier internal error: no src_reg\n"); 2306 return -EINVAL; 2307 } 2308 return adjust_scalar_min_max_vals(env, insn, dst_reg, *src_reg); 2309 } 2310 2311 /* check validity of 32-bit and 64-bit arithmetic operations */ 2312 static int check_alu_op(struct bpf_verifier_env *env, struct bpf_insn *insn) 2313 { 2314 struct bpf_reg_state *regs = cur_regs(env); 2315 u8 opcode = BPF_OP(insn->code); 2316 int err; 2317 2318 if (opcode == BPF_END || opcode == BPF_NEG) { 2319 if (opcode == BPF_NEG) { 2320 if (BPF_SRC(insn->code) != 0 || 2321 insn->src_reg != BPF_REG_0 || 2322 insn->off != 0 || insn->imm != 0) { 2323 verbose(env, "BPF_NEG uses reserved fields\n"); 2324 return -EINVAL; 2325 } 2326 } else { 2327 if (insn->src_reg != BPF_REG_0 || insn->off != 0 || 2328 (insn->imm != 16 && insn->imm != 32 && insn->imm != 64) || 2329 BPF_CLASS(insn->code) == BPF_ALU64) { 2330 verbose(env, "BPF_END uses reserved fields\n"); 2331 return -EINVAL; 2332 } 2333 } 2334 2335 /* check src operand */ 2336 err = check_reg_arg(env, insn->dst_reg, SRC_OP); 2337 if (err) 2338 return err; 2339 2340 if (is_pointer_value(env, insn->dst_reg)) { 2341 verbose(env, "R%d pointer arithmetic prohibited\n", 2342 insn->dst_reg); 2343 return -EACCES; 2344 } 2345 2346 /* check dest operand */ 2347 err = check_reg_arg(env, insn->dst_reg, DST_OP); 2348 if (err) 2349 return err; 2350 2351 } else if (opcode == BPF_MOV) { 2352 2353 if (BPF_SRC(insn->code) == BPF_X) { 2354 if (insn->imm != 0 || insn->off != 0) { 2355 verbose(env, "BPF_MOV uses reserved fields\n"); 2356 return -EINVAL; 2357 } 2358 2359 /* check src operand */ 2360 err = check_reg_arg(env, insn->src_reg, SRC_OP); 2361 if (err) 2362 return err; 2363 } else { 2364 if (insn->src_reg != BPF_REG_0 || insn->off != 0) { 2365 verbose(env, "BPF_MOV uses reserved fields\n"); 2366 return -EINVAL; 2367 } 2368 } 2369 2370 /* check dest operand */ 2371 err = check_reg_arg(env, insn->dst_reg, DST_OP); 2372 if (err) 2373 return err; 2374 2375 if (BPF_SRC(insn->code) == BPF_X) { 2376 if (BPF_CLASS(insn->code) == BPF_ALU64) { 2377 /* case: R1 = R2 2378 * copy register state to dest reg 2379 */ 2380 regs[insn->dst_reg] = regs[insn->src_reg]; 2381 regs[insn->dst_reg].live |= REG_LIVE_WRITTEN; 2382 } else { 2383 /* R1 = (u32) R2 */ 2384 if (is_pointer_value(env, insn->src_reg)) { 2385 verbose(env, 2386 "R%d partial copy of pointer\n", 2387 insn->src_reg); 2388 return -EACCES; 2389 } 2390 mark_reg_unknown(env, regs, insn->dst_reg); 2391 /* high 32 bits are known zero. */ 2392 regs[insn->dst_reg].var_off = tnum_cast( 2393 regs[insn->dst_reg].var_off, 4); 2394 __update_reg_bounds(®s[insn->dst_reg]); 2395 } 2396 } else { 2397 /* case: R = imm 2398 * remember the value we stored into this reg 2399 */ 2400 regs[insn->dst_reg].type = SCALAR_VALUE; 2401 __mark_reg_known(regs + insn->dst_reg, insn->imm); 2402 } 2403 2404 } else if (opcode > BPF_END) { 2405 verbose(env, "invalid BPF_ALU opcode %x\n", opcode); 2406 return -EINVAL; 2407 2408 } else { /* all other ALU ops: and, sub, xor, add, ... */ 2409 2410 if (BPF_SRC(insn->code) == BPF_X) { 2411 if (insn->imm != 0 || insn->off != 0) { 2412 verbose(env, "BPF_ALU uses reserved fields\n"); 2413 return -EINVAL; 2414 } 2415 /* check src1 operand */ 2416 err = check_reg_arg(env, insn->src_reg, SRC_OP); 2417 if (err) 2418 return err; 2419 } else { 2420 if (insn->src_reg != BPF_REG_0 || insn->off != 0) { 2421 verbose(env, "BPF_ALU uses reserved fields\n"); 2422 return -EINVAL; 2423 } 2424 } 2425 2426 /* check src2 operand */ 2427 err = check_reg_arg(env, insn->dst_reg, SRC_OP); 2428 if (err) 2429 return err; 2430 2431 if ((opcode == BPF_MOD || opcode == BPF_DIV) && 2432 BPF_SRC(insn->code) == BPF_K && insn->imm == 0) { 2433 verbose(env, "div by zero\n"); 2434 return -EINVAL; 2435 } 2436 2437 if ((opcode == BPF_LSH || opcode == BPF_RSH || 2438 opcode == BPF_ARSH) && BPF_SRC(insn->code) == BPF_K) { 2439 int size = BPF_CLASS(insn->code) == BPF_ALU64 ? 64 : 32; 2440 2441 if (insn->imm < 0 || insn->imm >= size) { 2442 verbose(env, "invalid shift %d\n", insn->imm); 2443 return -EINVAL; 2444 } 2445 } 2446 2447 /* check dest operand */ 2448 err = check_reg_arg(env, insn->dst_reg, DST_OP_NO_MARK); 2449 if (err) 2450 return err; 2451 2452 return adjust_reg_min_max_vals(env, insn); 2453 } 2454 2455 return 0; 2456 } 2457 2458 static void find_good_pkt_pointers(struct bpf_verifier_state *state, 2459 struct bpf_reg_state *dst_reg, 2460 enum bpf_reg_type type, 2461 bool range_right_open) 2462 { 2463 struct bpf_reg_state *regs = state->regs, *reg; 2464 u16 new_range; 2465 int i; 2466 2467 if (dst_reg->off < 0 || 2468 (dst_reg->off == 0 && range_right_open)) 2469 /* This doesn't give us any range */ 2470 return; 2471 2472 if (dst_reg->umax_value > MAX_PACKET_OFF || 2473 dst_reg->umax_value + dst_reg->off > MAX_PACKET_OFF) 2474 /* Risk of overflow. For instance, ptr + (1<<63) may be less 2475 * than pkt_end, but that's because it's also less than pkt. 2476 */ 2477 return; 2478 2479 new_range = dst_reg->off; 2480 if (range_right_open) 2481 new_range--; 2482 2483 /* Examples for register markings: 2484 * 2485 * pkt_data in dst register: 2486 * 2487 * r2 = r3; 2488 * r2 += 8; 2489 * if (r2 > pkt_end) goto <handle exception> 2490 * <access okay> 2491 * 2492 * r2 = r3; 2493 * r2 += 8; 2494 * if (r2 < pkt_end) goto <access okay> 2495 * <handle exception> 2496 * 2497 * Where: 2498 * r2 == dst_reg, pkt_end == src_reg 2499 * r2=pkt(id=n,off=8,r=0) 2500 * r3=pkt(id=n,off=0,r=0) 2501 * 2502 * pkt_data in src register: 2503 * 2504 * r2 = r3; 2505 * r2 += 8; 2506 * if (pkt_end >= r2) goto <access okay> 2507 * <handle exception> 2508 * 2509 * r2 = r3; 2510 * r2 += 8; 2511 * if (pkt_end <= r2) goto <handle exception> 2512 * <access okay> 2513 * 2514 * Where: 2515 * pkt_end == dst_reg, r2 == src_reg 2516 * r2=pkt(id=n,off=8,r=0) 2517 * r3=pkt(id=n,off=0,r=0) 2518 * 2519 * Find register r3 and mark its range as r3=pkt(id=n,off=0,r=8) 2520 * or r3=pkt(id=n,off=0,r=8-1), so that range of bytes [r3, r3 + 8) 2521 * and [r3, r3 + 8-1) respectively is safe to access depending on 2522 * the check. 2523 */ 2524 2525 /* If our ids match, then we must have the same max_value. And we 2526 * don't care about the other reg's fixed offset, since if it's too big 2527 * the range won't allow anything. 2528 * dst_reg->off is known < MAX_PACKET_OFF, therefore it fits in a u16. 2529 */ 2530 for (i = 0; i < MAX_BPF_REG; i++) 2531 if (regs[i].type == type && regs[i].id == dst_reg->id) 2532 /* keep the maximum range already checked */ 2533 regs[i].range = max(regs[i].range, new_range); 2534 2535 for (i = 0; i < state->allocated_stack / BPF_REG_SIZE; i++) { 2536 if (state->stack[i].slot_type[0] != STACK_SPILL) 2537 continue; 2538 reg = &state->stack[i].spilled_ptr; 2539 if (reg->type == type && reg->id == dst_reg->id) 2540 reg->range = max(reg->range, new_range); 2541 } 2542 } 2543 2544 /* Adjusts the register min/max values in the case that the dst_reg is the 2545 * variable register that we are working on, and src_reg is a constant or we're 2546 * simply doing a BPF_K check. 2547 * In JEQ/JNE cases we also adjust the var_off values. 2548 */ 2549 static void reg_set_min_max(struct bpf_reg_state *true_reg, 2550 struct bpf_reg_state *false_reg, u64 val, 2551 u8 opcode) 2552 { 2553 /* If the dst_reg is a pointer, we can't learn anything about its 2554 * variable offset from the compare (unless src_reg were a pointer into 2555 * the same object, but we don't bother with that. 2556 * Since false_reg and true_reg have the same type by construction, we 2557 * only need to check one of them for pointerness. 2558 */ 2559 if (__is_pointer_value(false, false_reg)) 2560 return; 2561 2562 switch (opcode) { 2563 case BPF_JEQ: 2564 /* If this is false then we know nothing Jon Snow, but if it is 2565 * true then we know for sure. 2566 */ 2567 __mark_reg_known(true_reg, val); 2568 break; 2569 case BPF_JNE: 2570 /* If this is true we know nothing Jon Snow, but if it is false 2571 * we know the value for sure; 2572 */ 2573 __mark_reg_known(false_reg, val); 2574 break; 2575 case BPF_JGT: 2576 false_reg->umax_value = min(false_reg->umax_value, val); 2577 true_reg->umin_value = max(true_reg->umin_value, val + 1); 2578 break; 2579 case BPF_JSGT: 2580 false_reg->smax_value = min_t(s64, false_reg->smax_value, val); 2581 true_reg->smin_value = max_t(s64, true_reg->smin_value, val + 1); 2582 break; 2583 case BPF_JLT: 2584 false_reg->umin_value = max(false_reg->umin_value, val); 2585 true_reg->umax_value = min(true_reg->umax_value, val - 1); 2586 break; 2587 case BPF_JSLT: 2588 false_reg->smin_value = max_t(s64, false_reg->smin_value, val); 2589 true_reg->smax_value = min_t(s64, true_reg->smax_value, val - 1); 2590 break; 2591 case BPF_JGE: 2592 false_reg->umax_value = min(false_reg->umax_value, val - 1); 2593 true_reg->umin_value = max(true_reg->umin_value, val); 2594 break; 2595 case BPF_JSGE: 2596 false_reg->smax_value = min_t(s64, false_reg->smax_value, val - 1); 2597 true_reg->smin_value = max_t(s64, true_reg->smin_value, val); 2598 break; 2599 case BPF_JLE: 2600 false_reg->umin_value = max(false_reg->umin_value, val + 1); 2601 true_reg->umax_value = min(true_reg->umax_value, val); 2602 break; 2603 case BPF_JSLE: 2604 false_reg->smin_value = max_t(s64, false_reg->smin_value, val + 1); 2605 true_reg->smax_value = min_t(s64, true_reg->smax_value, val); 2606 break; 2607 default: 2608 break; 2609 } 2610 2611 __reg_deduce_bounds(false_reg); 2612 __reg_deduce_bounds(true_reg); 2613 /* We might have learned some bits from the bounds. */ 2614 __reg_bound_offset(false_reg); 2615 __reg_bound_offset(true_reg); 2616 /* Intersecting with the old var_off might have improved our bounds 2617 * slightly. e.g. if umax was 0x7f...f and var_off was (0; 0xf...fc), 2618 * then new var_off is (0; 0x7f...fc) which improves our umax. 2619 */ 2620 __update_reg_bounds(false_reg); 2621 __update_reg_bounds(true_reg); 2622 } 2623 2624 /* Same as above, but for the case that dst_reg holds a constant and src_reg is 2625 * the variable reg. 2626 */ 2627 static void reg_set_min_max_inv(struct bpf_reg_state *true_reg, 2628 struct bpf_reg_state *false_reg, u64 val, 2629 u8 opcode) 2630 { 2631 if (__is_pointer_value(false, false_reg)) 2632 return; 2633 2634 switch (opcode) { 2635 case BPF_JEQ: 2636 /* If this is false then we know nothing Jon Snow, but if it is 2637 * true then we know for sure. 2638 */ 2639 __mark_reg_known(true_reg, val); 2640 break; 2641 case BPF_JNE: 2642 /* If this is true we know nothing Jon Snow, but if it is false 2643 * we know the value for sure; 2644 */ 2645 __mark_reg_known(false_reg, val); 2646 break; 2647 case BPF_JGT: 2648 true_reg->umax_value = min(true_reg->umax_value, val - 1); 2649 false_reg->umin_value = max(false_reg->umin_value, val); 2650 break; 2651 case BPF_JSGT: 2652 true_reg->smax_value = min_t(s64, true_reg->smax_value, val - 1); 2653 false_reg->smin_value = max_t(s64, false_reg->smin_value, val); 2654 break; 2655 case BPF_JLT: 2656 true_reg->umin_value = max(true_reg->umin_value, val + 1); 2657 false_reg->umax_value = min(false_reg->umax_value, val); 2658 break; 2659 case BPF_JSLT: 2660 true_reg->smin_value = max_t(s64, true_reg->smin_value, val + 1); 2661 false_reg->smax_value = min_t(s64, false_reg->smax_value, val); 2662 break; 2663 case BPF_JGE: 2664 true_reg->umax_value = min(true_reg->umax_value, val); 2665 false_reg->umin_value = max(false_reg->umin_value, val + 1); 2666 break; 2667 case BPF_JSGE: 2668 true_reg->smax_value = min_t(s64, true_reg->smax_value, val); 2669 false_reg->smin_value = max_t(s64, false_reg->smin_value, val + 1); 2670 break; 2671 case BPF_JLE: 2672 true_reg->umin_value = max(true_reg->umin_value, val); 2673 false_reg->umax_value = min(false_reg->umax_value, val - 1); 2674 break; 2675 case BPF_JSLE: 2676 true_reg->smin_value = max_t(s64, true_reg->smin_value, val); 2677 false_reg->smax_value = min_t(s64, false_reg->smax_value, val - 1); 2678 break; 2679 default: 2680 break; 2681 } 2682 2683 __reg_deduce_bounds(false_reg); 2684 __reg_deduce_bounds(true_reg); 2685 /* We might have learned some bits from the bounds. */ 2686 __reg_bound_offset(false_reg); 2687 __reg_bound_offset(true_reg); 2688 /* Intersecting with the old var_off might have improved our bounds 2689 * slightly. e.g. if umax was 0x7f...f and var_off was (0; 0xf...fc), 2690 * then new var_off is (0; 0x7f...fc) which improves our umax. 2691 */ 2692 __update_reg_bounds(false_reg); 2693 __update_reg_bounds(true_reg); 2694 } 2695 2696 /* Regs are known to be equal, so intersect their min/max/var_off */ 2697 static void __reg_combine_min_max(struct bpf_reg_state *src_reg, 2698 struct bpf_reg_state *dst_reg) 2699 { 2700 src_reg->umin_value = dst_reg->umin_value = max(src_reg->umin_value, 2701 dst_reg->umin_value); 2702 src_reg->umax_value = dst_reg->umax_value = min(src_reg->umax_value, 2703 dst_reg->umax_value); 2704 src_reg->smin_value = dst_reg->smin_value = max(src_reg->smin_value, 2705 dst_reg->smin_value); 2706 src_reg->smax_value = dst_reg->smax_value = min(src_reg->smax_value, 2707 dst_reg->smax_value); 2708 src_reg->var_off = dst_reg->var_off = tnum_intersect(src_reg->var_off, 2709 dst_reg->var_off); 2710 /* We might have learned new bounds from the var_off. */ 2711 __update_reg_bounds(src_reg); 2712 __update_reg_bounds(dst_reg); 2713 /* We might have learned something about the sign bit. */ 2714 __reg_deduce_bounds(src_reg); 2715 __reg_deduce_bounds(dst_reg); 2716 /* We might have learned some bits from the bounds. */ 2717 __reg_bound_offset(src_reg); 2718 __reg_bound_offset(dst_reg); 2719 /* Intersecting with the old var_off might have improved our bounds 2720 * slightly. e.g. if umax was 0x7f...f and var_off was (0; 0xf...fc), 2721 * then new var_off is (0; 0x7f...fc) which improves our umax. 2722 */ 2723 __update_reg_bounds(src_reg); 2724 __update_reg_bounds(dst_reg); 2725 } 2726 2727 static void reg_combine_min_max(struct bpf_reg_state *true_src, 2728 struct bpf_reg_state *true_dst, 2729 struct bpf_reg_state *false_src, 2730 struct bpf_reg_state *false_dst, 2731 u8 opcode) 2732 { 2733 switch (opcode) { 2734 case BPF_JEQ: 2735 __reg_combine_min_max(true_src, true_dst); 2736 break; 2737 case BPF_JNE: 2738 __reg_combine_min_max(false_src, false_dst); 2739 break; 2740 } 2741 } 2742 2743 static void mark_map_reg(struct bpf_reg_state *regs, u32 regno, u32 id, 2744 bool is_null) 2745 { 2746 struct bpf_reg_state *reg = ®s[regno]; 2747 2748 if (reg->type == PTR_TO_MAP_VALUE_OR_NULL && reg->id == id) { 2749 /* Old offset (both fixed and variable parts) should 2750 * have been known-zero, because we don't allow pointer 2751 * arithmetic on pointers that might be NULL. 2752 */ 2753 if (WARN_ON_ONCE(reg->smin_value || reg->smax_value || 2754 !tnum_equals_const(reg->var_off, 0) || 2755 reg->off)) { 2756 __mark_reg_known_zero(reg); 2757 reg->off = 0; 2758 } 2759 if (is_null) { 2760 reg->type = SCALAR_VALUE; 2761 } else if (reg->map_ptr->inner_map_meta) { 2762 reg->type = CONST_PTR_TO_MAP; 2763 reg->map_ptr = reg->map_ptr->inner_map_meta; 2764 } else { 2765 reg->type = PTR_TO_MAP_VALUE; 2766 } 2767 /* We don't need id from this point onwards anymore, thus we 2768 * should better reset it, so that state pruning has chances 2769 * to take effect. 2770 */ 2771 reg->id = 0; 2772 } 2773 } 2774 2775 /* The logic is similar to find_good_pkt_pointers(), both could eventually 2776 * be folded together at some point. 2777 */ 2778 static void mark_map_regs(struct bpf_verifier_state *state, u32 regno, 2779 bool is_null) 2780 { 2781 struct bpf_reg_state *regs = state->regs; 2782 u32 id = regs[regno].id; 2783 int i; 2784 2785 for (i = 0; i < MAX_BPF_REG; i++) 2786 mark_map_reg(regs, i, id, is_null); 2787 2788 for (i = 0; i < state->allocated_stack / BPF_REG_SIZE; i++) { 2789 if (state->stack[i].slot_type[0] != STACK_SPILL) 2790 continue; 2791 mark_map_reg(&state->stack[i].spilled_ptr, 0, id, is_null); 2792 } 2793 } 2794 2795 static bool try_match_pkt_pointers(const struct bpf_insn *insn, 2796 struct bpf_reg_state *dst_reg, 2797 struct bpf_reg_state *src_reg, 2798 struct bpf_verifier_state *this_branch, 2799 struct bpf_verifier_state *other_branch) 2800 { 2801 if (BPF_SRC(insn->code) != BPF_X) 2802 return false; 2803 2804 switch (BPF_OP(insn->code)) { 2805 case BPF_JGT: 2806 if ((dst_reg->type == PTR_TO_PACKET && 2807 src_reg->type == PTR_TO_PACKET_END) || 2808 (dst_reg->type == PTR_TO_PACKET_META && 2809 reg_is_init_pkt_pointer(src_reg, PTR_TO_PACKET))) { 2810 /* pkt_data' > pkt_end, pkt_meta' > pkt_data */ 2811 find_good_pkt_pointers(this_branch, dst_reg, 2812 dst_reg->type, false); 2813 } else if ((dst_reg->type == PTR_TO_PACKET_END && 2814 src_reg->type == PTR_TO_PACKET) || 2815 (reg_is_init_pkt_pointer(dst_reg, PTR_TO_PACKET) && 2816 src_reg->type == PTR_TO_PACKET_META)) { 2817 /* pkt_end > pkt_data', pkt_data > pkt_meta' */ 2818 find_good_pkt_pointers(other_branch, src_reg, 2819 src_reg->type, true); 2820 } else { 2821 return false; 2822 } 2823 break; 2824 case BPF_JLT: 2825 if ((dst_reg->type == PTR_TO_PACKET && 2826 src_reg->type == PTR_TO_PACKET_END) || 2827 (dst_reg->type == PTR_TO_PACKET_META && 2828 reg_is_init_pkt_pointer(src_reg, PTR_TO_PACKET))) { 2829 /* pkt_data' < pkt_end, pkt_meta' < pkt_data */ 2830 find_good_pkt_pointers(other_branch, dst_reg, 2831 dst_reg->type, true); 2832 } else if ((dst_reg->type == PTR_TO_PACKET_END && 2833 src_reg->type == PTR_TO_PACKET) || 2834 (reg_is_init_pkt_pointer(dst_reg, PTR_TO_PACKET) && 2835 src_reg->type == PTR_TO_PACKET_META)) { 2836 /* pkt_end < pkt_data', pkt_data > pkt_meta' */ 2837 find_good_pkt_pointers(this_branch, src_reg, 2838 src_reg->type, false); 2839 } else { 2840 return false; 2841 } 2842 break; 2843 case BPF_JGE: 2844 if ((dst_reg->type == PTR_TO_PACKET && 2845 src_reg->type == PTR_TO_PACKET_END) || 2846 (dst_reg->type == PTR_TO_PACKET_META && 2847 reg_is_init_pkt_pointer(src_reg, PTR_TO_PACKET))) { 2848 /* pkt_data' >= pkt_end, pkt_meta' >= pkt_data */ 2849 find_good_pkt_pointers(this_branch, dst_reg, 2850 dst_reg->type, true); 2851 } else if ((dst_reg->type == PTR_TO_PACKET_END && 2852 src_reg->type == PTR_TO_PACKET) || 2853 (reg_is_init_pkt_pointer(dst_reg, PTR_TO_PACKET) && 2854 src_reg->type == PTR_TO_PACKET_META)) { 2855 /* pkt_end >= pkt_data', pkt_data >= pkt_meta' */ 2856 find_good_pkt_pointers(other_branch, src_reg, 2857 src_reg->type, false); 2858 } else { 2859 return false; 2860 } 2861 break; 2862 case BPF_JLE: 2863 if ((dst_reg->type == PTR_TO_PACKET && 2864 src_reg->type == PTR_TO_PACKET_END) || 2865 (dst_reg->type == PTR_TO_PACKET_META && 2866 reg_is_init_pkt_pointer(src_reg, PTR_TO_PACKET))) { 2867 /* pkt_data' <= pkt_end, pkt_meta' <= pkt_data */ 2868 find_good_pkt_pointers(other_branch, dst_reg, 2869 dst_reg->type, false); 2870 } else if ((dst_reg->type == PTR_TO_PACKET_END && 2871 src_reg->type == PTR_TO_PACKET) || 2872 (reg_is_init_pkt_pointer(dst_reg, PTR_TO_PACKET) && 2873 src_reg->type == PTR_TO_PACKET_META)) { 2874 /* pkt_end <= pkt_data', pkt_data <= pkt_meta' */ 2875 find_good_pkt_pointers(this_branch, src_reg, 2876 src_reg->type, true); 2877 } else { 2878 return false; 2879 } 2880 break; 2881 default: 2882 return false; 2883 } 2884 2885 return true; 2886 } 2887 2888 static int check_cond_jmp_op(struct bpf_verifier_env *env, 2889 struct bpf_insn *insn, int *insn_idx) 2890 { 2891 struct bpf_verifier_state *other_branch, *this_branch = env->cur_state; 2892 struct bpf_reg_state *regs = this_branch->regs, *dst_reg; 2893 u8 opcode = BPF_OP(insn->code); 2894 int err; 2895 2896 if (opcode > BPF_JSLE) { 2897 verbose(env, "invalid BPF_JMP opcode %x\n", opcode); 2898 return -EINVAL; 2899 } 2900 2901 if (BPF_SRC(insn->code) == BPF_X) { 2902 if (insn->imm != 0) { 2903 verbose(env, "BPF_JMP uses reserved fields\n"); 2904 return -EINVAL; 2905 } 2906 2907 /* check src1 operand */ 2908 err = check_reg_arg(env, insn->src_reg, SRC_OP); 2909 if (err) 2910 return err; 2911 2912 if (is_pointer_value(env, insn->src_reg)) { 2913 verbose(env, "R%d pointer comparison prohibited\n", 2914 insn->src_reg); 2915 return -EACCES; 2916 } 2917 } else { 2918 if (insn->src_reg != BPF_REG_0) { 2919 verbose(env, "BPF_JMP uses reserved fields\n"); 2920 return -EINVAL; 2921 } 2922 } 2923 2924 /* check src2 operand */ 2925 err = check_reg_arg(env, insn->dst_reg, SRC_OP); 2926 if (err) 2927 return err; 2928 2929 dst_reg = ®s[insn->dst_reg]; 2930 2931 /* detect if R == 0 where R was initialized to zero earlier */ 2932 if (BPF_SRC(insn->code) == BPF_K && 2933 (opcode == BPF_JEQ || opcode == BPF_JNE) && 2934 dst_reg->type == SCALAR_VALUE && 2935 tnum_equals_const(dst_reg->var_off, insn->imm)) { 2936 if (opcode == BPF_JEQ) { 2937 /* if (imm == imm) goto pc+off; 2938 * only follow the goto, ignore fall-through 2939 */ 2940 *insn_idx += insn->off; 2941 return 0; 2942 } else { 2943 /* if (imm != imm) goto pc+off; 2944 * only follow fall-through branch, since 2945 * that's where the program will go 2946 */ 2947 return 0; 2948 } 2949 } 2950 2951 other_branch = push_stack(env, *insn_idx + insn->off + 1, *insn_idx); 2952 if (!other_branch) 2953 return -EFAULT; 2954 2955 /* detect if we are comparing against a constant value so we can adjust 2956 * our min/max values for our dst register. 2957 * this is only legit if both are scalars (or pointers to the same 2958 * object, I suppose, but we don't support that right now), because 2959 * otherwise the different base pointers mean the offsets aren't 2960 * comparable. 2961 */ 2962 if (BPF_SRC(insn->code) == BPF_X) { 2963 if (dst_reg->type == SCALAR_VALUE && 2964 regs[insn->src_reg].type == SCALAR_VALUE) { 2965 if (tnum_is_const(regs[insn->src_reg].var_off)) 2966 reg_set_min_max(&other_branch->regs[insn->dst_reg], 2967 dst_reg, regs[insn->src_reg].var_off.value, 2968 opcode); 2969 else if (tnum_is_const(dst_reg->var_off)) 2970 reg_set_min_max_inv(&other_branch->regs[insn->src_reg], 2971 ®s[insn->src_reg], 2972 dst_reg->var_off.value, opcode); 2973 else if (opcode == BPF_JEQ || opcode == BPF_JNE) 2974 /* Comparing for equality, we can combine knowledge */ 2975 reg_combine_min_max(&other_branch->regs[insn->src_reg], 2976 &other_branch->regs[insn->dst_reg], 2977 ®s[insn->src_reg], 2978 ®s[insn->dst_reg], opcode); 2979 } 2980 } else if (dst_reg->type == SCALAR_VALUE) { 2981 reg_set_min_max(&other_branch->regs[insn->dst_reg], 2982 dst_reg, insn->imm, opcode); 2983 } 2984 2985 /* detect if R == 0 where R is returned from bpf_map_lookup_elem() */ 2986 if (BPF_SRC(insn->code) == BPF_K && 2987 insn->imm == 0 && (opcode == BPF_JEQ || opcode == BPF_JNE) && 2988 dst_reg->type == PTR_TO_MAP_VALUE_OR_NULL) { 2989 /* Mark all identical map registers in each branch as either 2990 * safe or unknown depending R == 0 or R != 0 conditional. 2991 */ 2992 mark_map_regs(this_branch, insn->dst_reg, opcode == BPF_JNE); 2993 mark_map_regs(other_branch, insn->dst_reg, opcode == BPF_JEQ); 2994 } else if (!try_match_pkt_pointers(insn, dst_reg, ®s[insn->src_reg], 2995 this_branch, other_branch) && 2996 is_pointer_value(env, insn->dst_reg)) { 2997 verbose(env, "R%d pointer comparison prohibited\n", 2998 insn->dst_reg); 2999 return -EACCES; 3000 } 3001 if (env->log.level) 3002 print_verifier_state(env, this_branch); 3003 return 0; 3004 } 3005 3006 /* return the map pointer stored inside BPF_LD_IMM64 instruction */ 3007 static struct bpf_map *ld_imm64_to_map_ptr(struct bpf_insn *insn) 3008 { 3009 u64 imm64 = ((u64) (u32) insn[0].imm) | ((u64) (u32) insn[1].imm) << 32; 3010 3011 return (struct bpf_map *) (unsigned long) imm64; 3012 } 3013 3014 /* verify BPF_LD_IMM64 instruction */ 3015 static int check_ld_imm(struct bpf_verifier_env *env, struct bpf_insn *insn) 3016 { 3017 struct bpf_reg_state *regs = cur_regs(env); 3018 int err; 3019 3020 if (BPF_SIZE(insn->code) != BPF_DW) { 3021 verbose(env, "invalid BPF_LD_IMM insn\n"); 3022 return -EINVAL; 3023 } 3024 if (insn->off != 0) { 3025 verbose(env, "BPF_LD_IMM64 uses reserved fields\n"); 3026 return -EINVAL; 3027 } 3028 3029 err = check_reg_arg(env, insn->dst_reg, DST_OP); 3030 if (err) 3031 return err; 3032 3033 if (insn->src_reg == 0) { 3034 u64 imm = ((u64)(insn + 1)->imm << 32) | (u32)insn->imm; 3035 3036 regs[insn->dst_reg].type = SCALAR_VALUE; 3037 __mark_reg_known(®s[insn->dst_reg], imm); 3038 return 0; 3039 } 3040 3041 /* replace_map_fd_with_map_ptr() should have caught bad ld_imm64 */ 3042 BUG_ON(insn->src_reg != BPF_PSEUDO_MAP_FD); 3043 3044 regs[insn->dst_reg].type = CONST_PTR_TO_MAP; 3045 regs[insn->dst_reg].map_ptr = ld_imm64_to_map_ptr(insn); 3046 return 0; 3047 } 3048 3049 static bool may_access_skb(enum bpf_prog_type type) 3050 { 3051 switch (type) { 3052 case BPF_PROG_TYPE_SOCKET_FILTER: 3053 case BPF_PROG_TYPE_SCHED_CLS: 3054 case BPF_PROG_TYPE_SCHED_ACT: 3055 return true; 3056 default: 3057 return false; 3058 } 3059 } 3060 3061 /* verify safety of LD_ABS|LD_IND instructions: 3062 * - they can only appear in the programs where ctx == skb 3063 * - since they are wrappers of function calls, they scratch R1-R5 registers, 3064 * preserve R6-R9, and store return value into R0 3065 * 3066 * Implicit input: 3067 * ctx == skb == R6 == CTX 3068 * 3069 * Explicit input: 3070 * SRC == any register 3071 * IMM == 32-bit immediate 3072 * 3073 * Output: 3074 * R0 - 8/16/32-bit skb data converted to cpu endianness 3075 */ 3076 static int check_ld_abs(struct bpf_verifier_env *env, struct bpf_insn *insn) 3077 { 3078 struct bpf_reg_state *regs = cur_regs(env); 3079 u8 mode = BPF_MODE(insn->code); 3080 int i, err; 3081 3082 if (!may_access_skb(env->prog->type)) { 3083 verbose(env, "BPF_LD_[ABS|IND] instructions not allowed for this program type\n"); 3084 return -EINVAL; 3085 } 3086 3087 if (insn->dst_reg != BPF_REG_0 || insn->off != 0 || 3088 BPF_SIZE(insn->code) == BPF_DW || 3089 (mode == BPF_ABS && insn->src_reg != BPF_REG_0)) { 3090 verbose(env, "BPF_LD_[ABS|IND] uses reserved fields\n"); 3091 return -EINVAL; 3092 } 3093 3094 /* check whether implicit source operand (register R6) is readable */ 3095 err = check_reg_arg(env, BPF_REG_6, SRC_OP); 3096 if (err) 3097 return err; 3098 3099 if (regs[BPF_REG_6].type != PTR_TO_CTX) { 3100 verbose(env, 3101 "at the time of BPF_LD_ABS|IND R6 != pointer to skb\n"); 3102 return -EINVAL; 3103 } 3104 3105 if (mode == BPF_IND) { 3106 /* check explicit source operand */ 3107 err = check_reg_arg(env, insn->src_reg, SRC_OP); 3108 if (err) 3109 return err; 3110 } 3111 3112 /* reset caller saved regs to unreadable */ 3113 for (i = 0; i < CALLER_SAVED_REGS; i++) { 3114 mark_reg_not_init(env, regs, caller_saved[i]); 3115 check_reg_arg(env, caller_saved[i], DST_OP_NO_MARK); 3116 } 3117 3118 /* mark destination R0 register as readable, since it contains 3119 * the value fetched from the packet. 3120 * Already marked as written above. 3121 */ 3122 mark_reg_unknown(env, regs, BPF_REG_0); 3123 return 0; 3124 } 3125 3126 static int check_return_code(struct bpf_verifier_env *env) 3127 { 3128 struct bpf_reg_state *reg; 3129 struct tnum range = tnum_range(0, 1); 3130 3131 switch (env->prog->type) { 3132 case BPF_PROG_TYPE_CGROUP_SKB: 3133 case BPF_PROG_TYPE_CGROUP_SOCK: 3134 case BPF_PROG_TYPE_SOCK_OPS: 3135 case BPF_PROG_TYPE_CGROUP_DEVICE: 3136 break; 3137 default: 3138 return 0; 3139 } 3140 3141 reg = cur_regs(env) + BPF_REG_0; 3142 if (reg->type != SCALAR_VALUE) { 3143 verbose(env, "At program exit the register R0 is not a known value (%s)\n", 3144 reg_type_str[reg->type]); 3145 return -EINVAL; 3146 } 3147 3148 if (!tnum_in(range, reg->var_off)) { 3149 verbose(env, "At program exit the register R0 "); 3150 if (!tnum_is_unknown(reg->var_off)) { 3151 char tn_buf[48]; 3152 3153 tnum_strn(tn_buf, sizeof(tn_buf), reg->var_off); 3154 verbose(env, "has value %s", tn_buf); 3155 } else { 3156 verbose(env, "has unknown scalar value"); 3157 } 3158 verbose(env, " should have been 0 or 1\n"); 3159 return -EINVAL; 3160 } 3161 return 0; 3162 } 3163 3164 /* non-recursive DFS pseudo code 3165 * 1 procedure DFS-iterative(G,v): 3166 * 2 label v as discovered 3167 * 3 let S be a stack 3168 * 4 S.push(v) 3169 * 5 while S is not empty 3170 * 6 t <- S.pop() 3171 * 7 if t is what we're looking for: 3172 * 8 return t 3173 * 9 for all edges e in G.adjacentEdges(t) do 3174 * 10 if edge e is already labelled 3175 * 11 continue with the next edge 3176 * 12 w <- G.adjacentVertex(t,e) 3177 * 13 if vertex w is not discovered and not explored 3178 * 14 label e as tree-edge 3179 * 15 label w as discovered 3180 * 16 S.push(w) 3181 * 17 continue at 5 3182 * 18 else if vertex w is discovered 3183 * 19 label e as back-edge 3184 * 20 else 3185 * 21 // vertex w is explored 3186 * 22 label e as forward- or cross-edge 3187 * 23 label t as explored 3188 * 24 S.pop() 3189 * 3190 * convention: 3191 * 0x10 - discovered 3192 * 0x11 - discovered and fall-through edge labelled 3193 * 0x12 - discovered and fall-through and branch edges labelled 3194 * 0x20 - explored 3195 */ 3196 3197 enum { 3198 DISCOVERED = 0x10, 3199 EXPLORED = 0x20, 3200 FALLTHROUGH = 1, 3201 BRANCH = 2, 3202 }; 3203 3204 #define STATE_LIST_MARK ((struct bpf_verifier_state_list *) -1L) 3205 3206 static int *insn_stack; /* stack of insns to process */ 3207 static int cur_stack; /* current stack index */ 3208 static int *insn_state; 3209 3210 /* t, w, e - match pseudo-code above: 3211 * t - index of current instruction 3212 * w - next instruction 3213 * e - edge 3214 */ 3215 static int push_insn(int t, int w, int e, struct bpf_verifier_env *env) 3216 { 3217 if (e == FALLTHROUGH && insn_state[t] >= (DISCOVERED | FALLTHROUGH)) 3218 return 0; 3219 3220 if (e == BRANCH && insn_state[t] >= (DISCOVERED | BRANCH)) 3221 return 0; 3222 3223 if (w < 0 || w >= env->prog->len) { 3224 verbose(env, "jump out of range from insn %d to %d\n", t, w); 3225 return -EINVAL; 3226 } 3227 3228 if (e == BRANCH) 3229 /* mark branch target for state pruning */ 3230 env->explored_states[w] = STATE_LIST_MARK; 3231 3232 if (insn_state[w] == 0) { 3233 /* tree-edge */ 3234 insn_state[t] = DISCOVERED | e; 3235 insn_state[w] = DISCOVERED; 3236 if (cur_stack >= env->prog->len) 3237 return -E2BIG; 3238 insn_stack[cur_stack++] = w; 3239 return 1; 3240 } else if ((insn_state[w] & 0xF0) == DISCOVERED) { 3241 verbose(env, "back-edge from insn %d to %d\n", t, w); 3242 return -EINVAL; 3243 } else if (insn_state[w] == EXPLORED) { 3244 /* forward- or cross-edge */ 3245 insn_state[t] = DISCOVERED | e; 3246 } else { 3247 verbose(env, "insn state internal bug\n"); 3248 return -EFAULT; 3249 } 3250 return 0; 3251 } 3252 3253 /* non-recursive depth-first-search to detect loops in BPF program 3254 * loop == back-edge in directed graph 3255 */ 3256 static int check_cfg(struct bpf_verifier_env *env) 3257 { 3258 struct bpf_insn *insns = env->prog->insnsi; 3259 int insn_cnt = env->prog->len; 3260 int ret = 0; 3261 int i, t; 3262 3263 insn_state = kcalloc(insn_cnt, sizeof(int), GFP_KERNEL); 3264 if (!insn_state) 3265 return -ENOMEM; 3266 3267 insn_stack = kcalloc(insn_cnt, sizeof(int), GFP_KERNEL); 3268 if (!insn_stack) { 3269 kfree(insn_state); 3270 return -ENOMEM; 3271 } 3272 3273 insn_state[0] = DISCOVERED; /* mark 1st insn as discovered */ 3274 insn_stack[0] = 0; /* 0 is the first instruction */ 3275 cur_stack = 1; 3276 3277 peek_stack: 3278 if (cur_stack == 0) 3279 goto check_state; 3280 t = insn_stack[cur_stack - 1]; 3281 3282 if (BPF_CLASS(insns[t].code) == BPF_JMP) { 3283 u8 opcode = BPF_OP(insns[t].code); 3284 3285 if (opcode == BPF_EXIT) { 3286 goto mark_explored; 3287 } else if (opcode == BPF_CALL) { 3288 ret = push_insn(t, t + 1, FALLTHROUGH, env); 3289 if (ret == 1) 3290 goto peek_stack; 3291 else if (ret < 0) 3292 goto err_free; 3293 if (t + 1 < insn_cnt) 3294 env->explored_states[t + 1] = STATE_LIST_MARK; 3295 } else if (opcode == BPF_JA) { 3296 if (BPF_SRC(insns[t].code) != BPF_K) { 3297 ret = -EINVAL; 3298 goto err_free; 3299 } 3300 /* unconditional jump with single edge */ 3301 ret = push_insn(t, t + insns[t].off + 1, 3302 FALLTHROUGH, env); 3303 if (ret == 1) 3304 goto peek_stack; 3305 else if (ret < 0) 3306 goto err_free; 3307 /* tell verifier to check for equivalent states 3308 * after every call and jump 3309 */ 3310 if (t + 1 < insn_cnt) 3311 env->explored_states[t + 1] = STATE_LIST_MARK; 3312 } else { 3313 /* conditional jump with two edges */ 3314 env->explored_states[t] = STATE_LIST_MARK; 3315 ret = push_insn(t, t + 1, FALLTHROUGH, env); 3316 if (ret == 1) 3317 goto peek_stack; 3318 else if (ret < 0) 3319 goto err_free; 3320 3321 ret = push_insn(t, t + insns[t].off + 1, BRANCH, env); 3322 if (ret == 1) 3323 goto peek_stack; 3324 else if (ret < 0) 3325 goto err_free; 3326 } 3327 } else { 3328 /* all other non-branch instructions with single 3329 * fall-through edge 3330 */ 3331 ret = push_insn(t, t + 1, FALLTHROUGH, env); 3332 if (ret == 1) 3333 goto peek_stack; 3334 else if (ret < 0) 3335 goto err_free; 3336 } 3337 3338 mark_explored: 3339 insn_state[t] = EXPLORED; 3340 if (cur_stack-- <= 0) { 3341 verbose(env, "pop stack internal bug\n"); 3342 ret = -EFAULT; 3343 goto err_free; 3344 } 3345 goto peek_stack; 3346 3347 check_state: 3348 for (i = 0; i < insn_cnt; i++) { 3349 if (insn_state[i] != EXPLORED) { 3350 verbose(env, "unreachable insn %d\n", i); 3351 ret = -EINVAL; 3352 goto err_free; 3353 } 3354 } 3355 ret = 0; /* cfg looks good */ 3356 3357 err_free: 3358 kfree(insn_state); 3359 kfree(insn_stack); 3360 return ret; 3361 } 3362 3363 /* check %cur's range satisfies %old's */ 3364 static bool range_within(struct bpf_reg_state *old, 3365 struct bpf_reg_state *cur) 3366 { 3367 return old->umin_value <= cur->umin_value && 3368 old->umax_value >= cur->umax_value && 3369 old->smin_value <= cur->smin_value && 3370 old->smax_value >= cur->smax_value; 3371 } 3372 3373 /* Maximum number of register states that can exist at once */ 3374 #define ID_MAP_SIZE (MAX_BPF_REG + MAX_BPF_STACK / BPF_REG_SIZE) 3375 struct idpair { 3376 u32 old; 3377 u32 cur; 3378 }; 3379 3380 /* If in the old state two registers had the same id, then they need to have 3381 * the same id in the new state as well. But that id could be different from 3382 * the old state, so we need to track the mapping from old to new ids. 3383 * Once we have seen that, say, a reg with old id 5 had new id 9, any subsequent 3384 * regs with old id 5 must also have new id 9 for the new state to be safe. But 3385 * regs with a different old id could still have new id 9, we don't care about 3386 * that. 3387 * So we look through our idmap to see if this old id has been seen before. If 3388 * so, we require the new id to match; otherwise, we add the id pair to the map. 3389 */ 3390 static bool check_ids(u32 old_id, u32 cur_id, struct idpair *idmap) 3391 { 3392 unsigned int i; 3393 3394 for (i = 0; i < ID_MAP_SIZE; i++) { 3395 if (!idmap[i].old) { 3396 /* Reached an empty slot; haven't seen this id before */ 3397 idmap[i].old = old_id; 3398 idmap[i].cur = cur_id; 3399 return true; 3400 } 3401 if (idmap[i].old == old_id) 3402 return idmap[i].cur == cur_id; 3403 } 3404 /* We ran out of idmap slots, which should be impossible */ 3405 WARN_ON_ONCE(1); 3406 return false; 3407 } 3408 3409 /* Returns true if (rold safe implies rcur safe) */ 3410 static bool regsafe(struct bpf_reg_state *rold, struct bpf_reg_state *rcur, 3411 struct idpair *idmap) 3412 { 3413 if (!(rold->live & REG_LIVE_READ)) 3414 /* explored state didn't use this */ 3415 return true; 3416 3417 if (memcmp(rold, rcur, offsetof(struct bpf_reg_state, live)) == 0) 3418 return true; 3419 3420 if (rold->type == NOT_INIT) 3421 /* explored state can't have used this */ 3422 return true; 3423 if (rcur->type == NOT_INIT) 3424 return false; 3425 switch (rold->type) { 3426 case SCALAR_VALUE: 3427 if (rcur->type == SCALAR_VALUE) { 3428 /* new val must satisfy old val knowledge */ 3429 return range_within(rold, rcur) && 3430 tnum_in(rold->var_off, rcur->var_off); 3431 } else { 3432 /* if we knew anything about the old value, we're not 3433 * equal, because we can't know anything about the 3434 * scalar value of the pointer in the new value. 3435 */ 3436 return rold->umin_value == 0 && 3437 rold->umax_value == U64_MAX && 3438 rold->smin_value == S64_MIN && 3439 rold->smax_value == S64_MAX && 3440 tnum_is_unknown(rold->var_off); 3441 } 3442 case PTR_TO_MAP_VALUE: 3443 /* If the new min/max/var_off satisfy the old ones and 3444 * everything else matches, we are OK. 3445 * We don't care about the 'id' value, because nothing 3446 * uses it for PTR_TO_MAP_VALUE (only for ..._OR_NULL) 3447 */ 3448 return memcmp(rold, rcur, offsetof(struct bpf_reg_state, id)) == 0 && 3449 range_within(rold, rcur) && 3450 tnum_in(rold->var_off, rcur->var_off); 3451 case PTR_TO_MAP_VALUE_OR_NULL: 3452 /* a PTR_TO_MAP_VALUE could be safe to use as a 3453 * PTR_TO_MAP_VALUE_OR_NULL into the same map. 3454 * However, if the old PTR_TO_MAP_VALUE_OR_NULL then got NULL- 3455 * checked, doing so could have affected others with the same 3456 * id, and we can't check for that because we lost the id when 3457 * we converted to a PTR_TO_MAP_VALUE. 3458 */ 3459 if (rcur->type != PTR_TO_MAP_VALUE_OR_NULL) 3460 return false; 3461 if (memcmp(rold, rcur, offsetof(struct bpf_reg_state, id))) 3462 return false; 3463 /* Check our ids match any regs they're supposed to */ 3464 return check_ids(rold->id, rcur->id, idmap); 3465 case PTR_TO_PACKET_META: 3466 case PTR_TO_PACKET: 3467 if (rcur->type != rold->type) 3468 return false; 3469 /* We must have at least as much range as the old ptr 3470 * did, so that any accesses which were safe before are 3471 * still safe. This is true even if old range < old off, 3472 * since someone could have accessed through (ptr - k), or 3473 * even done ptr -= k in a register, to get a safe access. 3474 */ 3475 if (rold->range > rcur->range) 3476 return false; 3477 /* If the offsets don't match, we can't trust our alignment; 3478 * nor can we be sure that we won't fall out of range. 3479 */ 3480 if (rold->off != rcur->off) 3481 return false; 3482 /* id relations must be preserved */ 3483 if (rold->id && !check_ids(rold->id, rcur->id, idmap)) 3484 return false; 3485 /* new val must satisfy old val knowledge */ 3486 return range_within(rold, rcur) && 3487 tnum_in(rold->var_off, rcur->var_off); 3488 case PTR_TO_CTX: 3489 case CONST_PTR_TO_MAP: 3490 case PTR_TO_STACK: 3491 case PTR_TO_PACKET_END: 3492 /* Only valid matches are exact, which memcmp() above 3493 * would have accepted 3494 */ 3495 default: 3496 /* Don't know what's going on, just say it's not safe */ 3497 return false; 3498 } 3499 3500 /* Shouldn't get here; if we do, say it's not safe */ 3501 WARN_ON_ONCE(1); 3502 return false; 3503 } 3504 3505 static bool stacksafe(struct bpf_verifier_state *old, 3506 struct bpf_verifier_state *cur, 3507 struct idpair *idmap) 3508 { 3509 int i, spi; 3510 3511 /* if explored stack has more populated slots than current stack 3512 * such stacks are not equivalent 3513 */ 3514 if (old->allocated_stack > cur->allocated_stack) 3515 return false; 3516 3517 /* walk slots of the explored stack and ignore any additional 3518 * slots in the current stack, since explored(safe) state 3519 * didn't use them 3520 */ 3521 for (i = 0; i < old->allocated_stack; i++) { 3522 spi = i / BPF_REG_SIZE; 3523 3524 if (old->stack[spi].slot_type[i % BPF_REG_SIZE] == STACK_INVALID) 3525 continue; 3526 if (old->stack[spi].slot_type[i % BPF_REG_SIZE] != 3527 cur->stack[spi].slot_type[i % BPF_REG_SIZE]) 3528 /* Ex: old explored (safe) state has STACK_SPILL in 3529 * this stack slot, but current has has STACK_MISC -> 3530 * this verifier states are not equivalent, 3531 * return false to continue verification of this path 3532 */ 3533 return false; 3534 if (i % BPF_REG_SIZE) 3535 continue; 3536 if (old->stack[spi].slot_type[0] != STACK_SPILL) 3537 continue; 3538 if (!regsafe(&old->stack[spi].spilled_ptr, 3539 &cur->stack[spi].spilled_ptr, 3540 idmap)) 3541 /* when explored and current stack slot are both storing 3542 * spilled registers, check that stored pointers types 3543 * are the same as well. 3544 * Ex: explored safe path could have stored 3545 * (bpf_reg_state) {.type = PTR_TO_STACK, .off = -8} 3546 * but current path has stored: 3547 * (bpf_reg_state) {.type = PTR_TO_STACK, .off = -16} 3548 * such verifier states are not equivalent. 3549 * return false to continue verification of this path 3550 */ 3551 return false; 3552 } 3553 return true; 3554 } 3555 3556 /* compare two verifier states 3557 * 3558 * all states stored in state_list are known to be valid, since 3559 * verifier reached 'bpf_exit' instruction through them 3560 * 3561 * this function is called when verifier exploring different branches of 3562 * execution popped from the state stack. If it sees an old state that has 3563 * more strict register state and more strict stack state then this execution 3564 * branch doesn't need to be explored further, since verifier already 3565 * concluded that more strict state leads to valid finish. 3566 * 3567 * Therefore two states are equivalent if register state is more conservative 3568 * and explored stack state is more conservative than the current one. 3569 * Example: 3570 * explored current 3571 * (slot1=INV slot2=MISC) == (slot1=MISC slot2=MISC) 3572 * (slot1=MISC slot2=MISC) != (slot1=INV slot2=MISC) 3573 * 3574 * In other words if current stack state (one being explored) has more 3575 * valid slots than old one that already passed validation, it means 3576 * the verifier can stop exploring and conclude that current state is valid too 3577 * 3578 * Similarly with registers. If explored state has register type as invalid 3579 * whereas register type in current state is meaningful, it means that 3580 * the current state will reach 'bpf_exit' instruction safely 3581 */ 3582 static bool states_equal(struct bpf_verifier_env *env, 3583 struct bpf_verifier_state *old, 3584 struct bpf_verifier_state *cur) 3585 { 3586 struct idpair *idmap; 3587 bool ret = false; 3588 int i; 3589 3590 idmap = kcalloc(ID_MAP_SIZE, sizeof(struct idpair), GFP_KERNEL); 3591 /* If we failed to allocate the idmap, just say it's not safe */ 3592 if (!idmap) 3593 return false; 3594 3595 for (i = 0; i < MAX_BPF_REG; i++) { 3596 if (!regsafe(&old->regs[i], &cur->regs[i], idmap)) 3597 goto out_free; 3598 } 3599 3600 if (!stacksafe(old, cur, idmap)) 3601 goto out_free; 3602 ret = true; 3603 out_free: 3604 kfree(idmap); 3605 return ret; 3606 } 3607 3608 /* A write screens off any subsequent reads; but write marks come from the 3609 * straight-line code between a state and its parent. When we arrive at a 3610 * jump target (in the first iteration of the propagate_liveness() loop), 3611 * we didn't arrive by the straight-line code, so read marks in state must 3612 * propagate to parent regardless of state's write marks. 3613 */ 3614 static bool do_propagate_liveness(const struct bpf_verifier_state *state, 3615 struct bpf_verifier_state *parent) 3616 { 3617 bool writes = parent == state->parent; /* Observe write marks */ 3618 bool touched = false; /* any changes made? */ 3619 int i; 3620 3621 if (!parent) 3622 return touched; 3623 /* Propagate read liveness of registers... */ 3624 BUILD_BUG_ON(BPF_REG_FP + 1 != MAX_BPF_REG); 3625 /* We don't need to worry about FP liveness because it's read-only */ 3626 for (i = 0; i < BPF_REG_FP; i++) { 3627 if (parent->regs[i].live & REG_LIVE_READ) 3628 continue; 3629 if (writes && (state->regs[i].live & REG_LIVE_WRITTEN)) 3630 continue; 3631 if (state->regs[i].live & REG_LIVE_READ) { 3632 parent->regs[i].live |= REG_LIVE_READ; 3633 touched = true; 3634 } 3635 } 3636 /* ... and stack slots */ 3637 for (i = 0; i < state->allocated_stack / BPF_REG_SIZE && 3638 i < parent->allocated_stack / BPF_REG_SIZE; i++) { 3639 if (parent->stack[i].slot_type[0] != STACK_SPILL) 3640 continue; 3641 if (state->stack[i].slot_type[0] != STACK_SPILL) 3642 continue; 3643 if (parent->stack[i].spilled_ptr.live & REG_LIVE_READ) 3644 continue; 3645 if (writes && 3646 (state->stack[i].spilled_ptr.live & REG_LIVE_WRITTEN)) 3647 continue; 3648 if (state->stack[i].spilled_ptr.live & REG_LIVE_READ) { 3649 parent->stack[i].spilled_ptr.live |= REG_LIVE_READ; 3650 touched = true; 3651 } 3652 } 3653 return touched; 3654 } 3655 3656 /* "parent" is "a state from which we reach the current state", but initially 3657 * it is not the state->parent (i.e. "the state whose straight-line code leads 3658 * to the current state"), instead it is the state that happened to arrive at 3659 * a (prunable) equivalent of the current state. See comment above 3660 * do_propagate_liveness() for consequences of this. 3661 * This function is just a more efficient way of calling mark_reg_read() or 3662 * mark_stack_slot_read() on each reg in "parent" that is read in "state", 3663 * though it requires that parent != state->parent in the call arguments. 3664 */ 3665 static void propagate_liveness(const struct bpf_verifier_state *state, 3666 struct bpf_verifier_state *parent) 3667 { 3668 while (do_propagate_liveness(state, parent)) { 3669 /* Something changed, so we need to feed those changes onward */ 3670 state = parent; 3671 parent = state->parent; 3672 } 3673 } 3674 3675 static int is_state_visited(struct bpf_verifier_env *env, int insn_idx) 3676 { 3677 struct bpf_verifier_state_list *new_sl; 3678 struct bpf_verifier_state_list *sl; 3679 struct bpf_verifier_state *cur = env->cur_state; 3680 int i, err; 3681 3682 sl = env->explored_states[insn_idx]; 3683 if (!sl) 3684 /* this 'insn_idx' instruction wasn't marked, so we will not 3685 * be doing state search here 3686 */ 3687 return 0; 3688 3689 while (sl != STATE_LIST_MARK) { 3690 if (states_equal(env, &sl->state, cur)) { 3691 /* reached equivalent register/stack state, 3692 * prune the search. 3693 * Registers read by the continuation are read by us. 3694 * If we have any write marks in env->cur_state, they 3695 * will prevent corresponding reads in the continuation 3696 * from reaching our parent (an explored_state). Our 3697 * own state will get the read marks recorded, but 3698 * they'll be immediately forgotten as we're pruning 3699 * this state and will pop a new one. 3700 */ 3701 propagate_liveness(&sl->state, cur); 3702 return 1; 3703 } 3704 sl = sl->next; 3705 } 3706 3707 /* there were no equivalent states, remember current one. 3708 * technically the current state is not proven to be safe yet, 3709 * but it will either reach bpf_exit (which means it's safe) or 3710 * it will be rejected. Since there are no loops, we won't be 3711 * seeing this 'insn_idx' instruction again on the way to bpf_exit 3712 */ 3713 new_sl = kzalloc(sizeof(struct bpf_verifier_state_list), GFP_KERNEL); 3714 if (!new_sl) 3715 return -ENOMEM; 3716 3717 /* add new state to the head of linked list */ 3718 err = copy_verifier_state(&new_sl->state, cur); 3719 if (err) { 3720 free_verifier_state(&new_sl->state, false); 3721 kfree(new_sl); 3722 return err; 3723 } 3724 new_sl->next = env->explored_states[insn_idx]; 3725 env->explored_states[insn_idx] = new_sl; 3726 /* connect new state to parentage chain */ 3727 cur->parent = &new_sl->state; 3728 /* clear write marks in current state: the writes we did are not writes 3729 * our child did, so they don't screen off its reads from us. 3730 * (There are no read marks in current state, because reads always mark 3731 * their parent and current state never has children yet. Only 3732 * explored_states can get read marks.) 3733 */ 3734 for (i = 0; i < BPF_REG_FP; i++) 3735 cur->regs[i].live = REG_LIVE_NONE; 3736 for (i = 0; i < cur->allocated_stack / BPF_REG_SIZE; i++) 3737 if (cur->stack[i].slot_type[0] == STACK_SPILL) 3738 cur->stack[i].spilled_ptr.live = REG_LIVE_NONE; 3739 return 0; 3740 } 3741 3742 static int ext_analyzer_insn_hook(struct bpf_verifier_env *env, 3743 int insn_idx, int prev_insn_idx) 3744 { 3745 if (env->dev_ops && env->dev_ops->insn_hook) 3746 return env->dev_ops->insn_hook(env, insn_idx, prev_insn_idx); 3747 3748 return 0; 3749 } 3750 3751 static int do_check(struct bpf_verifier_env *env) 3752 { 3753 struct bpf_verifier_state *state; 3754 struct bpf_insn *insns = env->prog->insnsi; 3755 struct bpf_reg_state *regs; 3756 int insn_cnt = env->prog->len; 3757 int insn_idx, prev_insn_idx = 0; 3758 int insn_processed = 0; 3759 bool do_print_state = false; 3760 3761 state = kzalloc(sizeof(struct bpf_verifier_state), GFP_KERNEL); 3762 if (!state) 3763 return -ENOMEM; 3764 env->cur_state = state; 3765 init_reg_state(env, state->regs); 3766 state->parent = NULL; 3767 insn_idx = 0; 3768 for (;;) { 3769 struct bpf_insn *insn; 3770 u8 class; 3771 int err; 3772 3773 if (insn_idx >= insn_cnt) { 3774 verbose(env, "invalid insn idx %d insn_cnt %d\n", 3775 insn_idx, insn_cnt); 3776 return -EFAULT; 3777 } 3778 3779 insn = &insns[insn_idx]; 3780 class = BPF_CLASS(insn->code); 3781 3782 if (++insn_processed > BPF_COMPLEXITY_LIMIT_INSNS) { 3783 verbose(env, 3784 "BPF program is too large. Processed %d insn\n", 3785 insn_processed); 3786 return -E2BIG; 3787 } 3788 3789 err = is_state_visited(env, insn_idx); 3790 if (err < 0) 3791 return err; 3792 if (err == 1) { 3793 /* found equivalent state, can prune the search */ 3794 if (env->log.level) { 3795 if (do_print_state) 3796 verbose(env, "\nfrom %d to %d: safe\n", 3797 prev_insn_idx, insn_idx); 3798 else 3799 verbose(env, "%d: safe\n", insn_idx); 3800 } 3801 goto process_bpf_exit; 3802 } 3803 3804 if (need_resched()) 3805 cond_resched(); 3806 3807 if (env->log.level > 1 || (env->log.level && do_print_state)) { 3808 if (env->log.level > 1) 3809 verbose(env, "%d:", insn_idx); 3810 else 3811 verbose(env, "\nfrom %d to %d:", 3812 prev_insn_idx, insn_idx); 3813 print_verifier_state(env, state); 3814 do_print_state = false; 3815 } 3816 3817 if (env->log.level) { 3818 verbose(env, "%d: ", insn_idx); 3819 print_bpf_insn(verbose, env, insn, 3820 env->allow_ptr_leaks); 3821 } 3822 3823 err = ext_analyzer_insn_hook(env, insn_idx, prev_insn_idx); 3824 if (err) 3825 return err; 3826 3827 regs = cur_regs(env); 3828 if (class == BPF_ALU || class == BPF_ALU64) { 3829 err = check_alu_op(env, insn); 3830 if (err) 3831 return err; 3832 3833 } else if (class == BPF_LDX) { 3834 enum bpf_reg_type *prev_src_type, src_reg_type; 3835 3836 /* check for reserved fields is already done */ 3837 3838 /* check src operand */ 3839 err = check_reg_arg(env, insn->src_reg, SRC_OP); 3840 if (err) 3841 return err; 3842 3843 err = check_reg_arg(env, insn->dst_reg, DST_OP_NO_MARK); 3844 if (err) 3845 return err; 3846 3847 src_reg_type = regs[insn->src_reg].type; 3848 3849 /* check that memory (src_reg + off) is readable, 3850 * the state of dst_reg will be updated by this func 3851 */ 3852 err = check_mem_access(env, insn_idx, insn->src_reg, insn->off, 3853 BPF_SIZE(insn->code), BPF_READ, 3854 insn->dst_reg); 3855 if (err) 3856 return err; 3857 3858 prev_src_type = &env->insn_aux_data[insn_idx].ptr_type; 3859 3860 if (*prev_src_type == NOT_INIT) { 3861 /* saw a valid insn 3862 * dst_reg = *(u32 *)(src_reg + off) 3863 * save type to validate intersecting paths 3864 */ 3865 *prev_src_type = src_reg_type; 3866 3867 } else if (src_reg_type != *prev_src_type && 3868 (src_reg_type == PTR_TO_CTX || 3869 *prev_src_type == PTR_TO_CTX)) { 3870 /* ABuser program is trying to use the same insn 3871 * dst_reg = *(u32*) (src_reg + off) 3872 * with different pointer types: 3873 * src_reg == ctx in one branch and 3874 * src_reg == stack|map in some other branch. 3875 * Reject it. 3876 */ 3877 verbose(env, "same insn cannot be used with different pointers\n"); 3878 return -EINVAL; 3879 } 3880 3881 } else if (class == BPF_STX) { 3882 enum bpf_reg_type *prev_dst_type, dst_reg_type; 3883 3884 if (BPF_MODE(insn->code) == BPF_XADD) { 3885 err = check_xadd(env, insn_idx, insn); 3886 if (err) 3887 return err; 3888 insn_idx++; 3889 continue; 3890 } 3891 3892 /* check src1 operand */ 3893 err = check_reg_arg(env, insn->src_reg, SRC_OP); 3894 if (err) 3895 return err; 3896 /* check src2 operand */ 3897 err = check_reg_arg(env, insn->dst_reg, SRC_OP); 3898 if (err) 3899 return err; 3900 3901 dst_reg_type = regs[insn->dst_reg].type; 3902 3903 /* check that memory (dst_reg + off) is writeable */ 3904 err = check_mem_access(env, insn_idx, insn->dst_reg, insn->off, 3905 BPF_SIZE(insn->code), BPF_WRITE, 3906 insn->src_reg); 3907 if (err) 3908 return err; 3909 3910 prev_dst_type = &env->insn_aux_data[insn_idx].ptr_type; 3911 3912 if (*prev_dst_type == NOT_INIT) { 3913 *prev_dst_type = dst_reg_type; 3914 } else if (dst_reg_type != *prev_dst_type && 3915 (dst_reg_type == PTR_TO_CTX || 3916 *prev_dst_type == PTR_TO_CTX)) { 3917 verbose(env, "same insn cannot be used with different pointers\n"); 3918 return -EINVAL; 3919 } 3920 3921 } else if (class == BPF_ST) { 3922 if (BPF_MODE(insn->code) != BPF_MEM || 3923 insn->src_reg != BPF_REG_0) { 3924 verbose(env, "BPF_ST uses reserved fields\n"); 3925 return -EINVAL; 3926 } 3927 /* check src operand */ 3928 err = check_reg_arg(env, insn->dst_reg, SRC_OP); 3929 if (err) 3930 return err; 3931 3932 /* check that memory (dst_reg + off) is writeable */ 3933 err = check_mem_access(env, insn_idx, insn->dst_reg, insn->off, 3934 BPF_SIZE(insn->code), BPF_WRITE, 3935 -1); 3936 if (err) 3937 return err; 3938 3939 } else if (class == BPF_JMP) { 3940 u8 opcode = BPF_OP(insn->code); 3941 3942 if (opcode == BPF_CALL) { 3943 if (BPF_SRC(insn->code) != BPF_K || 3944 insn->off != 0 || 3945 insn->src_reg != BPF_REG_0 || 3946 insn->dst_reg != BPF_REG_0) { 3947 verbose(env, "BPF_CALL uses reserved fields\n"); 3948 return -EINVAL; 3949 } 3950 3951 err = check_call(env, insn->imm, insn_idx); 3952 if (err) 3953 return err; 3954 3955 } else if (opcode == BPF_JA) { 3956 if (BPF_SRC(insn->code) != BPF_K || 3957 insn->imm != 0 || 3958 insn->src_reg != BPF_REG_0 || 3959 insn->dst_reg != BPF_REG_0) { 3960 verbose(env, "BPF_JA uses reserved fields\n"); 3961 return -EINVAL; 3962 } 3963 3964 insn_idx += insn->off + 1; 3965 continue; 3966 3967 } else if (opcode == BPF_EXIT) { 3968 if (BPF_SRC(insn->code) != BPF_K || 3969 insn->imm != 0 || 3970 insn->src_reg != BPF_REG_0 || 3971 insn->dst_reg != BPF_REG_0) { 3972 verbose(env, "BPF_EXIT uses reserved fields\n"); 3973 return -EINVAL; 3974 } 3975 3976 /* eBPF calling convetion is such that R0 is used 3977 * to return the value from eBPF program. 3978 * Make sure that it's readable at this time 3979 * of bpf_exit, which means that program wrote 3980 * something into it earlier 3981 */ 3982 err = check_reg_arg(env, BPF_REG_0, SRC_OP); 3983 if (err) 3984 return err; 3985 3986 if (is_pointer_value(env, BPF_REG_0)) { 3987 verbose(env, "R0 leaks addr as return value\n"); 3988 return -EACCES; 3989 } 3990 3991 err = check_return_code(env); 3992 if (err) 3993 return err; 3994 process_bpf_exit: 3995 err = pop_stack(env, &prev_insn_idx, &insn_idx); 3996 if (err < 0) { 3997 if (err != -ENOENT) 3998 return err; 3999 break; 4000 } else { 4001 do_print_state = true; 4002 continue; 4003 } 4004 } else { 4005 err = check_cond_jmp_op(env, insn, &insn_idx); 4006 if (err) 4007 return err; 4008 } 4009 } else if (class == BPF_LD) { 4010 u8 mode = BPF_MODE(insn->code); 4011 4012 if (mode == BPF_ABS || mode == BPF_IND) { 4013 err = check_ld_abs(env, insn); 4014 if (err) 4015 return err; 4016 4017 } else if (mode == BPF_IMM) { 4018 err = check_ld_imm(env, insn); 4019 if (err) 4020 return err; 4021 4022 insn_idx++; 4023 } else { 4024 verbose(env, "invalid BPF_LD mode\n"); 4025 return -EINVAL; 4026 } 4027 } else { 4028 verbose(env, "unknown insn class %d\n", class); 4029 return -EINVAL; 4030 } 4031 4032 insn_idx++; 4033 } 4034 4035 verbose(env, "processed %d insns, stack depth %d\n", insn_processed, 4036 env->prog->aux->stack_depth); 4037 return 0; 4038 } 4039 4040 static int check_map_prealloc(struct bpf_map *map) 4041 { 4042 return (map->map_type != BPF_MAP_TYPE_HASH && 4043 map->map_type != BPF_MAP_TYPE_PERCPU_HASH && 4044 map->map_type != BPF_MAP_TYPE_HASH_OF_MAPS) || 4045 !(map->map_flags & BPF_F_NO_PREALLOC); 4046 } 4047 4048 static int check_map_prog_compatibility(struct bpf_verifier_env *env, 4049 struct bpf_map *map, 4050 struct bpf_prog *prog) 4051 4052 { 4053 /* Make sure that BPF_PROG_TYPE_PERF_EVENT programs only use 4054 * preallocated hash maps, since doing memory allocation 4055 * in overflow_handler can crash depending on where nmi got 4056 * triggered. 4057 */ 4058 if (prog->type == BPF_PROG_TYPE_PERF_EVENT) { 4059 if (!check_map_prealloc(map)) { 4060 verbose(env, "perf_event programs can only use preallocated hash map\n"); 4061 return -EINVAL; 4062 } 4063 if (map->inner_map_meta && 4064 !check_map_prealloc(map->inner_map_meta)) { 4065 verbose(env, "perf_event programs can only use preallocated inner hash map\n"); 4066 return -EINVAL; 4067 } 4068 } 4069 return 0; 4070 } 4071 4072 /* look for pseudo eBPF instructions that access map FDs and 4073 * replace them with actual map pointers 4074 */ 4075 static int replace_map_fd_with_map_ptr(struct bpf_verifier_env *env) 4076 { 4077 struct bpf_insn *insn = env->prog->insnsi; 4078 int insn_cnt = env->prog->len; 4079 int i, j, err; 4080 4081 err = bpf_prog_calc_tag(env->prog); 4082 if (err) 4083 return err; 4084 4085 for (i = 0; i < insn_cnt; i++, insn++) { 4086 if (BPF_CLASS(insn->code) == BPF_LDX && 4087 (BPF_MODE(insn->code) != BPF_MEM || insn->imm != 0)) { 4088 verbose(env, "BPF_LDX uses reserved fields\n"); 4089 return -EINVAL; 4090 } 4091 4092 if (BPF_CLASS(insn->code) == BPF_STX && 4093 ((BPF_MODE(insn->code) != BPF_MEM && 4094 BPF_MODE(insn->code) != BPF_XADD) || insn->imm != 0)) { 4095 verbose(env, "BPF_STX uses reserved fields\n"); 4096 return -EINVAL; 4097 } 4098 4099 if (insn[0].code == (BPF_LD | BPF_IMM | BPF_DW)) { 4100 struct bpf_map *map; 4101 struct fd f; 4102 4103 if (i == insn_cnt - 1 || insn[1].code != 0 || 4104 insn[1].dst_reg != 0 || insn[1].src_reg != 0 || 4105 insn[1].off != 0) { 4106 verbose(env, "invalid bpf_ld_imm64 insn\n"); 4107 return -EINVAL; 4108 } 4109 4110 if (insn->src_reg == 0) 4111 /* valid generic load 64-bit imm */ 4112 goto next_insn; 4113 4114 if (insn->src_reg != BPF_PSEUDO_MAP_FD) { 4115 verbose(env, 4116 "unrecognized bpf_ld_imm64 insn\n"); 4117 return -EINVAL; 4118 } 4119 4120 f = fdget(insn->imm); 4121 map = __bpf_map_get(f); 4122 if (IS_ERR(map)) { 4123 verbose(env, "fd %d is not pointing to valid bpf_map\n", 4124 insn->imm); 4125 return PTR_ERR(map); 4126 } 4127 4128 err = check_map_prog_compatibility(env, map, env->prog); 4129 if (err) { 4130 fdput(f); 4131 return err; 4132 } 4133 4134 /* store map pointer inside BPF_LD_IMM64 instruction */ 4135 insn[0].imm = (u32) (unsigned long) map; 4136 insn[1].imm = ((u64) (unsigned long) map) >> 32; 4137 4138 /* check whether we recorded this map already */ 4139 for (j = 0; j < env->used_map_cnt; j++) 4140 if (env->used_maps[j] == map) { 4141 fdput(f); 4142 goto next_insn; 4143 } 4144 4145 if (env->used_map_cnt >= MAX_USED_MAPS) { 4146 fdput(f); 4147 return -E2BIG; 4148 } 4149 4150 /* hold the map. If the program is rejected by verifier, 4151 * the map will be released by release_maps() or it 4152 * will be used by the valid program until it's unloaded 4153 * and all maps are released in free_bpf_prog_info() 4154 */ 4155 map = bpf_map_inc(map, false); 4156 if (IS_ERR(map)) { 4157 fdput(f); 4158 return PTR_ERR(map); 4159 } 4160 env->used_maps[env->used_map_cnt++] = map; 4161 4162 fdput(f); 4163 next_insn: 4164 insn++; 4165 i++; 4166 } 4167 } 4168 4169 /* now all pseudo BPF_LD_IMM64 instructions load valid 4170 * 'struct bpf_map *' into a register instead of user map_fd. 4171 * These pointers will be used later by verifier to validate map access. 4172 */ 4173 return 0; 4174 } 4175 4176 /* drop refcnt of maps used by the rejected program */ 4177 static void release_maps(struct bpf_verifier_env *env) 4178 { 4179 int i; 4180 4181 for (i = 0; i < env->used_map_cnt; i++) 4182 bpf_map_put(env->used_maps[i]); 4183 } 4184 4185 /* convert pseudo BPF_LD_IMM64 into generic BPF_LD_IMM64 */ 4186 static void convert_pseudo_ld_imm64(struct bpf_verifier_env *env) 4187 { 4188 struct bpf_insn *insn = env->prog->insnsi; 4189 int insn_cnt = env->prog->len; 4190 int i; 4191 4192 for (i = 0; i < insn_cnt; i++, insn++) 4193 if (insn->code == (BPF_LD | BPF_IMM | BPF_DW)) 4194 insn->src_reg = 0; 4195 } 4196 4197 /* single env->prog->insni[off] instruction was replaced with the range 4198 * insni[off, off + cnt). Adjust corresponding insn_aux_data by copying 4199 * [0, off) and [off, end) to new locations, so the patched range stays zero 4200 */ 4201 static int adjust_insn_aux_data(struct bpf_verifier_env *env, u32 prog_len, 4202 u32 off, u32 cnt) 4203 { 4204 struct bpf_insn_aux_data *new_data, *old_data = env->insn_aux_data; 4205 4206 if (cnt == 1) 4207 return 0; 4208 new_data = vzalloc(sizeof(struct bpf_insn_aux_data) * prog_len); 4209 if (!new_data) 4210 return -ENOMEM; 4211 memcpy(new_data, old_data, sizeof(struct bpf_insn_aux_data) * off); 4212 memcpy(new_data + off + cnt - 1, old_data + off, 4213 sizeof(struct bpf_insn_aux_data) * (prog_len - off - cnt + 1)); 4214 env->insn_aux_data = new_data; 4215 vfree(old_data); 4216 return 0; 4217 } 4218 4219 static struct bpf_prog *bpf_patch_insn_data(struct bpf_verifier_env *env, u32 off, 4220 const struct bpf_insn *patch, u32 len) 4221 { 4222 struct bpf_prog *new_prog; 4223 4224 new_prog = bpf_patch_insn_single(env->prog, off, patch, len); 4225 if (!new_prog) 4226 return NULL; 4227 if (adjust_insn_aux_data(env, new_prog->len, off, len)) 4228 return NULL; 4229 return new_prog; 4230 } 4231 4232 /* convert load instructions that access fields of 'struct __sk_buff' 4233 * into sequence of instructions that access fields of 'struct sk_buff' 4234 */ 4235 static int convert_ctx_accesses(struct bpf_verifier_env *env) 4236 { 4237 const struct bpf_verifier_ops *ops = env->ops; 4238 int i, cnt, size, ctx_field_size, delta = 0; 4239 const int insn_cnt = env->prog->len; 4240 struct bpf_insn insn_buf[16], *insn; 4241 struct bpf_prog *new_prog; 4242 enum bpf_access_type type; 4243 bool is_narrower_load; 4244 u32 target_size; 4245 4246 if (ops->gen_prologue) { 4247 cnt = ops->gen_prologue(insn_buf, env->seen_direct_write, 4248 env->prog); 4249 if (cnt >= ARRAY_SIZE(insn_buf)) { 4250 verbose(env, "bpf verifier is misconfigured\n"); 4251 return -EINVAL; 4252 } else if (cnt) { 4253 new_prog = bpf_patch_insn_data(env, 0, insn_buf, cnt); 4254 if (!new_prog) 4255 return -ENOMEM; 4256 4257 env->prog = new_prog; 4258 delta += cnt - 1; 4259 } 4260 } 4261 4262 if (!ops->convert_ctx_access) 4263 return 0; 4264 4265 insn = env->prog->insnsi + delta; 4266 4267 for (i = 0; i < insn_cnt; i++, insn++) { 4268 if (insn->code == (BPF_LDX | BPF_MEM | BPF_B) || 4269 insn->code == (BPF_LDX | BPF_MEM | BPF_H) || 4270 insn->code == (BPF_LDX | BPF_MEM | BPF_W) || 4271 insn->code == (BPF_LDX | BPF_MEM | BPF_DW)) 4272 type = BPF_READ; 4273 else if (insn->code == (BPF_STX | BPF_MEM | BPF_B) || 4274 insn->code == (BPF_STX | BPF_MEM | BPF_H) || 4275 insn->code == (BPF_STX | BPF_MEM | BPF_W) || 4276 insn->code == (BPF_STX | BPF_MEM | BPF_DW)) 4277 type = BPF_WRITE; 4278 else 4279 continue; 4280 4281 if (env->insn_aux_data[i + delta].ptr_type != PTR_TO_CTX) 4282 continue; 4283 4284 ctx_field_size = env->insn_aux_data[i + delta].ctx_field_size; 4285 size = BPF_LDST_BYTES(insn); 4286 4287 /* If the read access is a narrower load of the field, 4288 * convert to a 4/8-byte load, to minimum program type specific 4289 * convert_ctx_access changes. If conversion is successful, 4290 * we will apply proper mask to the result. 4291 */ 4292 is_narrower_load = size < ctx_field_size; 4293 if (is_narrower_load) { 4294 u32 off = insn->off; 4295 u8 size_code; 4296 4297 if (type == BPF_WRITE) { 4298 verbose(env, "bpf verifier narrow ctx access misconfigured\n"); 4299 return -EINVAL; 4300 } 4301 4302 size_code = BPF_H; 4303 if (ctx_field_size == 4) 4304 size_code = BPF_W; 4305 else if (ctx_field_size == 8) 4306 size_code = BPF_DW; 4307 4308 insn->off = off & ~(ctx_field_size - 1); 4309 insn->code = BPF_LDX | BPF_MEM | size_code; 4310 } 4311 4312 target_size = 0; 4313 cnt = ops->convert_ctx_access(type, insn, insn_buf, env->prog, 4314 &target_size); 4315 if (cnt == 0 || cnt >= ARRAY_SIZE(insn_buf) || 4316 (ctx_field_size && !target_size)) { 4317 verbose(env, "bpf verifier is misconfigured\n"); 4318 return -EINVAL; 4319 } 4320 4321 if (is_narrower_load && size < target_size) { 4322 if (ctx_field_size <= 4) 4323 insn_buf[cnt++] = BPF_ALU32_IMM(BPF_AND, insn->dst_reg, 4324 (1 << size * 8) - 1); 4325 else 4326 insn_buf[cnt++] = BPF_ALU64_IMM(BPF_AND, insn->dst_reg, 4327 (1 << size * 8) - 1); 4328 } 4329 4330 new_prog = bpf_patch_insn_data(env, i + delta, insn_buf, cnt); 4331 if (!new_prog) 4332 return -ENOMEM; 4333 4334 delta += cnt - 1; 4335 4336 /* keep walking new program and skip insns we just inserted */ 4337 env->prog = new_prog; 4338 insn = new_prog->insnsi + i + delta; 4339 } 4340 4341 return 0; 4342 } 4343 4344 /* fixup insn->imm field of bpf_call instructions 4345 * and inline eligible helpers as explicit sequence of BPF instructions 4346 * 4347 * this function is called after eBPF program passed verification 4348 */ 4349 static int fixup_bpf_calls(struct bpf_verifier_env *env) 4350 { 4351 struct bpf_prog *prog = env->prog; 4352 struct bpf_insn *insn = prog->insnsi; 4353 const struct bpf_func_proto *fn; 4354 const int insn_cnt = prog->len; 4355 struct bpf_insn insn_buf[16]; 4356 struct bpf_prog *new_prog; 4357 struct bpf_map *map_ptr; 4358 int i, cnt, delta = 0; 4359 4360 for (i = 0; i < insn_cnt; i++, insn++) { 4361 if (insn->code != (BPF_JMP | BPF_CALL)) 4362 continue; 4363 4364 if (insn->imm == BPF_FUNC_get_route_realm) 4365 prog->dst_needed = 1; 4366 if (insn->imm == BPF_FUNC_get_prandom_u32) 4367 bpf_user_rnd_init_once(); 4368 if (insn->imm == BPF_FUNC_tail_call) { 4369 /* If we tail call into other programs, we 4370 * cannot make any assumptions since they can 4371 * be replaced dynamically during runtime in 4372 * the program array. 4373 */ 4374 prog->cb_access = 1; 4375 env->prog->aux->stack_depth = MAX_BPF_STACK; 4376 4377 /* mark bpf_tail_call as different opcode to avoid 4378 * conditional branch in the interpeter for every normal 4379 * call and to prevent accidental JITing by JIT compiler 4380 * that doesn't support bpf_tail_call yet 4381 */ 4382 insn->imm = 0; 4383 insn->code = BPF_JMP | BPF_TAIL_CALL; 4384 continue; 4385 } 4386 4387 /* BPF_EMIT_CALL() assumptions in some of the map_gen_lookup 4388 * handlers are currently limited to 64 bit only. 4389 */ 4390 if (ebpf_jit_enabled() && BITS_PER_LONG == 64 && 4391 insn->imm == BPF_FUNC_map_lookup_elem) { 4392 map_ptr = env->insn_aux_data[i + delta].map_ptr; 4393 if (map_ptr == BPF_MAP_PTR_POISON || 4394 !map_ptr->ops->map_gen_lookup) 4395 goto patch_call_imm; 4396 4397 cnt = map_ptr->ops->map_gen_lookup(map_ptr, insn_buf); 4398 if (cnt == 0 || cnt >= ARRAY_SIZE(insn_buf)) { 4399 verbose(env, "bpf verifier is misconfigured\n"); 4400 return -EINVAL; 4401 } 4402 4403 new_prog = bpf_patch_insn_data(env, i + delta, insn_buf, 4404 cnt); 4405 if (!new_prog) 4406 return -ENOMEM; 4407 4408 delta += cnt - 1; 4409 4410 /* keep walking new program and skip insns we just inserted */ 4411 env->prog = prog = new_prog; 4412 insn = new_prog->insnsi + i + delta; 4413 continue; 4414 } 4415 4416 if (insn->imm == BPF_FUNC_redirect_map) { 4417 /* Note, we cannot use prog directly as imm as subsequent 4418 * rewrites would still change the prog pointer. The only 4419 * stable address we can use is aux, which also works with 4420 * prog clones during blinding. 4421 */ 4422 u64 addr = (unsigned long)prog->aux; 4423 struct bpf_insn r4_ld[] = { 4424 BPF_LD_IMM64(BPF_REG_4, addr), 4425 *insn, 4426 }; 4427 cnt = ARRAY_SIZE(r4_ld); 4428 4429 new_prog = bpf_patch_insn_data(env, i + delta, r4_ld, cnt); 4430 if (!new_prog) 4431 return -ENOMEM; 4432 4433 delta += cnt - 1; 4434 env->prog = prog = new_prog; 4435 insn = new_prog->insnsi + i + delta; 4436 } 4437 patch_call_imm: 4438 fn = env->ops->get_func_proto(insn->imm); 4439 /* all functions that have prototype and verifier allowed 4440 * programs to call them, must be real in-kernel functions 4441 */ 4442 if (!fn->func) { 4443 verbose(env, 4444 "kernel subsystem misconfigured func %s#%d\n", 4445 func_id_name(insn->imm), insn->imm); 4446 return -EFAULT; 4447 } 4448 insn->imm = fn->func - __bpf_call_base; 4449 } 4450 4451 return 0; 4452 } 4453 4454 static void free_states(struct bpf_verifier_env *env) 4455 { 4456 struct bpf_verifier_state_list *sl, *sln; 4457 int i; 4458 4459 if (!env->explored_states) 4460 return; 4461 4462 for (i = 0; i < env->prog->len; i++) { 4463 sl = env->explored_states[i]; 4464 4465 if (sl) 4466 while (sl != STATE_LIST_MARK) { 4467 sln = sl->next; 4468 free_verifier_state(&sl->state, false); 4469 kfree(sl); 4470 sl = sln; 4471 } 4472 } 4473 4474 kfree(env->explored_states); 4475 } 4476 4477 int bpf_check(struct bpf_prog **prog, union bpf_attr *attr) 4478 { 4479 struct bpf_verifier_env *env; 4480 struct bpf_verifer_log *log; 4481 int ret = -EINVAL; 4482 4483 /* no program is valid */ 4484 if (ARRAY_SIZE(bpf_verifier_ops) == 0) 4485 return -EINVAL; 4486 4487 /* 'struct bpf_verifier_env' can be global, but since it's not small, 4488 * allocate/free it every time bpf_check() is called 4489 */ 4490 env = kzalloc(sizeof(struct bpf_verifier_env), GFP_KERNEL); 4491 if (!env) 4492 return -ENOMEM; 4493 log = &env->log; 4494 4495 env->insn_aux_data = vzalloc(sizeof(struct bpf_insn_aux_data) * 4496 (*prog)->len); 4497 ret = -ENOMEM; 4498 if (!env->insn_aux_data) 4499 goto err_free_env; 4500 env->prog = *prog; 4501 env->ops = bpf_verifier_ops[env->prog->type]; 4502 4503 /* grab the mutex to protect few globals used by verifier */ 4504 mutex_lock(&bpf_verifier_lock); 4505 4506 if (attr->log_level || attr->log_buf || attr->log_size) { 4507 /* user requested verbose verifier output 4508 * and supplied buffer to store the verification trace 4509 */ 4510 log->level = attr->log_level; 4511 log->ubuf = (char __user *) (unsigned long) attr->log_buf; 4512 log->len_total = attr->log_size; 4513 4514 ret = -EINVAL; 4515 /* log attributes have to be sane */ 4516 if (log->len_total < 128 || log->len_total > UINT_MAX >> 8 || 4517 !log->level || !log->ubuf) 4518 goto err_unlock; 4519 } 4520 4521 env->strict_alignment = !!(attr->prog_flags & BPF_F_STRICT_ALIGNMENT); 4522 if (!IS_ENABLED(CONFIG_HAVE_EFFICIENT_UNALIGNED_ACCESS)) 4523 env->strict_alignment = true; 4524 4525 if (env->prog->aux->offload) { 4526 ret = bpf_prog_offload_verifier_prep(env); 4527 if (ret) 4528 goto err_unlock; 4529 } 4530 4531 ret = replace_map_fd_with_map_ptr(env); 4532 if (ret < 0) 4533 goto skip_full_check; 4534 4535 env->explored_states = kcalloc(env->prog->len, 4536 sizeof(struct bpf_verifier_state_list *), 4537 GFP_USER); 4538 ret = -ENOMEM; 4539 if (!env->explored_states) 4540 goto skip_full_check; 4541 4542 ret = check_cfg(env); 4543 if (ret < 0) 4544 goto skip_full_check; 4545 4546 env->allow_ptr_leaks = capable(CAP_SYS_ADMIN); 4547 4548 ret = do_check(env); 4549 if (env->cur_state) { 4550 free_verifier_state(env->cur_state, true); 4551 env->cur_state = NULL; 4552 } 4553 4554 skip_full_check: 4555 while (!pop_stack(env, NULL, NULL)); 4556 free_states(env); 4557 4558 if (ret == 0) 4559 /* program is valid, convert *(u32*)(ctx + off) accesses */ 4560 ret = convert_ctx_accesses(env); 4561 4562 if (ret == 0) 4563 ret = fixup_bpf_calls(env); 4564 4565 if (log->level && bpf_verifier_log_full(log)) 4566 ret = -ENOSPC; 4567 if (log->level && !log->ubuf) { 4568 ret = -EFAULT; 4569 goto err_release_maps; 4570 } 4571 4572 if (ret == 0 && env->used_map_cnt) { 4573 /* if program passed verifier, update used_maps in bpf_prog_info */ 4574 env->prog->aux->used_maps = kmalloc_array(env->used_map_cnt, 4575 sizeof(env->used_maps[0]), 4576 GFP_KERNEL); 4577 4578 if (!env->prog->aux->used_maps) { 4579 ret = -ENOMEM; 4580 goto err_release_maps; 4581 } 4582 4583 memcpy(env->prog->aux->used_maps, env->used_maps, 4584 sizeof(env->used_maps[0]) * env->used_map_cnt); 4585 env->prog->aux->used_map_cnt = env->used_map_cnt; 4586 4587 /* program is valid. Convert pseudo bpf_ld_imm64 into generic 4588 * bpf_ld_imm64 instructions 4589 */ 4590 convert_pseudo_ld_imm64(env); 4591 } 4592 4593 err_release_maps: 4594 if (!env->prog->aux->used_maps) 4595 /* if we didn't copy map pointers into bpf_prog_info, release 4596 * them now. Otherwise free_bpf_prog_info() will release them. 4597 */ 4598 release_maps(env); 4599 *prog = env->prog; 4600 err_unlock: 4601 mutex_unlock(&bpf_verifier_lock); 4602 vfree(env->insn_aux_data); 4603 err_free_env: 4604 kfree(env); 4605 return ret; 4606 } 4607