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 bool is_ctx_reg(struct bpf_verifier_env *env, int regno) 982 { 983 const struct bpf_reg_state *reg = cur_regs(env) + regno; 984 985 return reg->type == PTR_TO_CTX; 986 } 987 988 static int check_pkt_ptr_alignment(struct bpf_verifier_env *env, 989 const struct bpf_reg_state *reg, 990 int off, int size, bool strict) 991 { 992 struct tnum reg_off; 993 int ip_align; 994 995 /* Byte size accesses are always allowed. */ 996 if (!strict || size == 1) 997 return 0; 998 999 /* For platforms that do not have a Kconfig enabling 1000 * CONFIG_HAVE_EFFICIENT_UNALIGNED_ACCESS the value of 1001 * NET_IP_ALIGN is universally set to '2'. And on platforms 1002 * that do set CONFIG_HAVE_EFFICIENT_UNALIGNED_ACCESS, we get 1003 * to this code only in strict mode where we want to emulate 1004 * the NET_IP_ALIGN==2 checking. Therefore use an 1005 * unconditional IP align value of '2'. 1006 */ 1007 ip_align = 2; 1008 1009 reg_off = tnum_add(reg->var_off, tnum_const(ip_align + reg->off + off)); 1010 if (!tnum_is_aligned(reg_off, size)) { 1011 char tn_buf[48]; 1012 1013 tnum_strn(tn_buf, sizeof(tn_buf), reg->var_off); 1014 verbose(env, 1015 "misaligned packet access off %d+%s+%d+%d size %d\n", 1016 ip_align, tn_buf, reg->off, off, size); 1017 return -EACCES; 1018 } 1019 1020 return 0; 1021 } 1022 1023 static int check_generic_ptr_alignment(struct bpf_verifier_env *env, 1024 const struct bpf_reg_state *reg, 1025 const char *pointer_desc, 1026 int off, int size, bool strict) 1027 { 1028 struct tnum reg_off; 1029 1030 /* Byte size accesses are always allowed. */ 1031 if (!strict || size == 1) 1032 return 0; 1033 1034 reg_off = tnum_add(reg->var_off, tnum_const(reg->off + off)); 1035 if (!tnum_is_aligned(reg_off, size)) { 1036 char tn_buf[48]; 1037 1038 tnum_strn(tn_buf, sizeof(tn_buf), reg->var_off); 1039 verbose(env, "misaligned %saccess off %s+%d+%d size %d\n", 1040 pointer_desc, tn_buf, reg->off, off, size); 1041 return -EACCES; 1042 } 1043 1044 return 0; 1045 } 1046 1047 static int check_ptr_alignment(struct bpf_verifier_env *env, 1048 const struct bpf_reg_state *reg, 1049 int off, int size) 1050 { 1051 bool strict = env->strict_alignment; 1052 const char *pointer_desc = ""; 1053 1054 switch (reg->type) { 1055 case PTR_TO_PACKET: 1056 case PTR_TO_PACKET_META: 1057 /* Special case, because of NET_IP_ALIGN. Given metadata sits 1058 * right in front, treat it the very same way. 1059 */ 1060 return check_pkt_ptr_alignment(env, reg, off, size, strict); 1061 case PTR_TO_MAP_VALUE: 1062 pointer_desc = "value "; 1063 break; 1064 case PTR_TO_CTX: 1065 pointer_desc = "context "; 1066 break; 1067 case PTR_TO_STACK: 1068 pointer_desc = "stack "; 1069 /* The stack spill tracking logic in check_stack_write() 1070 * and check_stack_read() relies on stack accesses being 1071 * aligned. 1072 */ 1073 strict = true; 1074 break; 1075 default: 1076 break; 1077 } 1078 return check_generic_ptr_alignment(env, reg, pointer_desc, off, size, 1079 strict); 1080 } 1081 1082 /* truncate register to smaller size (in bytes) 1083 * must be called with size < BPF_REG_SIZE 1084 */ 1085 static void coerce_reg_to_size(struct bpf_reg_state *reg, int size) 1086 { 1087 u64 mask; 1088 1089 /* clear high bits in bit representation */ 1090 reg->var_off = tnum_cast(reg->var_off, size); 1091 1092 /* fix arithmetic bounds */ 1093 mask = ((u64)1 << (size * 8)) - 1; 1094 if ((reg->umin_value & ~mask) == (reg->umax_value & ~mask)) { 1095 reg->umin_value &= mask; 1096 reg->umax_value &= mask; 1097 } else { 1098 reg->umin_value = 0; 1099 reg->umax_value = mask; 1100 } 1101 reg->smin_value = reg->umin_value; 1102 reg->smax_value = reg->umax_value; 1103 } 1104 1105 /* check whether memory at (regno + off) is accessible for t = (read | write) 1106 * if t==write, value_regno is a register which value is stored into memory 1107 * if t==read, value_regno is a register which will receive the value from memory 1108 * if t==write && value_regno==-1, some unknown value is stored into memory 1109 * if t==read && value_regno==-1, don't care what we read from memory 1110 */ 1111 static int check_mem_access(struct bpf_verifier_env *env, int insn_idx, u32 regno, int off, 1112 int bpf_size, enum bpf_access_type t, 1113 int value_regno) 1114 { 1115 struct bpf_verifier_state *state = env->cur_state; 1116 struct bpf_reg_state *regs = cur_regs(env); 1117 struct bpf_reg_state *reg = regs + regno; 1118 int size, err = 0; 1119 1120 size = bpf_size_to_bytes(bpf_size); 1121 if (size < 0) 1122 return size; 1123 1124 /* alignment checks will add in reg->off themselves */ 1125 err = check_ptr_alignment(env, reg, off, size); 1126 if (err) 1127 return err; 1128 1129 /* for access checks, reg->off is just part of off */ 1130 off += reg->off; 1131 1132 if (reg->type == PTR_TO_MAP_VALUE) { 1133 if (t == BPF_WRITE && value_regno >= 0 && 1134 is_pointer_value(env, value_regno)) { 1135 verbose(env, "R%d leaks addr into map\n", value_regno); 1136 return -EACCES; 1137 } 1138 1139 err = check_map_access(env, regno, off, size, false); 1140 if (!err && t == BPF_READ && value_regno >= 0) 1141 mark_reg_unknown(env, regs, value_regno); 1142 1143 } else if (reg->type == PTR_TO_CTX) { 1144 enum bpf_reg_type reg_type = SCALAR_VALUE; 1145 1146 if (t == BPF_WRITE && value_regno >= 0 && 1147 is_pointer_value(env, value_regno)) { 1148 verbose(env, "R%d leaks addr into ctx\n", value_regno); 1149 return -EACCES; 1150 } 1151 /* ctx accesses must be at a fixed offset, so that we can 1152 * determine what type of data were returned. 1153 */ 1154 if (reg->off) { 1155 verbose(env, 1156 "dereference of modified ctx ptr R%d off=%d+%d, ctx+const is allowed, ctx+const+const is not\n", 1157 regno, reg->off, off - reg->off); 1158 return -EACCES; 1159 } 1160 if (!tnum_is_const(reg->var_off) || reg->var_off.value) { 1161 char tn_buf[48]; 1162 1163 tnum_strn(tn_buf, sizeof(tn_buf), reg->var_off); 1164 verbose(env, 1165 "variable ctx access var_off=%s off=%d size=%d", 1166 tn_buf, off, size); 1167 return -EACCES; 1168 } 1169 err = check_ctx_access(env, insn_idx, off, size, t, ®_type); 1170 if (!err && t == BPF_READ && value_regno >= 0) { 1171 /* ctx access returns either a scalar, or a 1172 * PTR_TO_PACKET[_META,_END]. In the latter 1173 * case, we know the offset is zero. 1174 */ 1175 if (reg_type == SCALAR_VALUE) 1176 mark_reg_unknown(env, regs, value_regno); 1177 else 1178 mark_reg_known_zero(env, regs, 1179 value_regno); 1180 regs[value_regno].id = 0; 1181 regs[value_regno].off = 0; 1182 regs[value_regno].range = 0; 1183 regs[value_regno].type = reg_type; 1184 } 1185 1186 } else if (reg->type == PTR_TO_STACK) { 1187 /* stack accesses must be at a fixed offset, so that we can 1188 * determine what type of data were returned. 1189 * See check_stack_read(). 1190 */ 1191 if (!tnum_is_const(reg->var_off)) { 1192 char tn_buf[48]; 1193 1194 tnum_strn(tn_buf, sizeof(tn_buf), reg->var_off); 1195 verbose(env, "variable stack access var_off=%s off=%d size=%d", 1196 tn_buf, off, size); 1197 return -EACCES; 1198 } 1199 off += reg->var_off.value; 1200 if (off >= 0 || off < -MAX_BPF_STACK) { 1201 verbose(env, "invalid stack off=%d size=%d\n", off, 1202 size); 1203 return -EACCES; 1204 } 1205 1206 if (env->prog->aux->stack_depth < -off) 1207 env->prog->aux->stack_depth = -off; 1208 1209 if (t == BPF_WRITE) 1210 err = check_stack_write(env, state, off, size, 1211 value_regno); 1212 else 1213 err = check_stack_read(env, state, off, size, 1214 value_regno); 1215 } else if (reg_is_pkt_pointer(reg)) { 1216 if (t == BPF_WRITE && !may_access_direct_pkt_data(env, NULL, t)) { 1217 verbose(env, "cannot write into packet\n"); 1218 return -EACCES; 1219 } 1220 if (t == BPF_WRITE && value_regno >= 0 && 1221 is_pointer_value(env, value_regno)) { 1222 verbose(env, "R%d leaks addr into packet\n", 1223 value_regno); 1224 return -EACCES; 1225 } 1226 err = check_packet_access(env, regno, off, size, false); 1227 if (!err && t == BPF_READ && value_regno >= 0) 1228 mark_reg_unknown(env, regs, value_regno); 1229 } else { 1230 verbose(env, "R%d invalid mem access '%s'\n", regno, 1231 reg_type_str[reg->type]); 1232 return -EACCES; 1233 } 1234 1235 if (!err && size < BPF_REG_SIZE && value_regno >= 0 && t == BPF_READ && 1236 regs[value_regno].type == SCALAR_VALUE) { 1237 /* b/h/w load zero-extends, mark upper bits as known 0 */ 1238 coerce_reg_to_size(®s[value_regno], size); 1239 } 1240 return err; 1241 } 1242 1243 static int check_xadd(struct bpf_verifier_env *env, int insn_idx, struct bpf_insn *insn) 1244 { 1245 int err; 1246 1247 if ((BPF_SIZE(insn->code) != BPF_W && BPF_SIZE(insn->code) != BPF_DW) || 1248 insn->imm != 0) { 1249 verbose(env, "BPF_XADD uses reserved fields\n"); 1250 return -EINVAL; 1251 } 1252 1253 /* check src1 operand */ 1254 err = check_reg_arg(env, insn->src_reg, SRC_OP); 1255 if (err) 1256 return err; 1257 1258 /* check src2 operand */ 1259 err = check_reg_arg(env, insn->dst_reg, SRC_OP); 1260 if (err) 1261 return err; 1262 1263 if (is_pointer_value(env, insn->src_reg)) { 1264 verbose(env, "R%d leaks addr into mem\n", insn->src_reg); 1265 return -EACCES; 1266 } 1267 1268 if (is_ctx_reg(env, insn->dst_reg)) { 1269 verbose(env, "BPF_XADD stores into R%d context is not allowed\n", 1270 insn->dst_reg); 1271 return -EACCES; 1272 } 1273 1274 /* check whether atomic_add can read the memory */ 1275 err = check_mem_access(env, insn_idx, insn->dst_reg, insn->off, 1276 BPF_SIZE(insn->code), BPF_READ, -1); 1277 if (err) 1278 return err; 1279 1280 /* check whether atomic_add can write into the same memory */ 1281 return check_mem_access(env, insn_idx, insn->dst_reg, insn->off, 1282 BPF_SIZE(insn->code), BPF_WRITE, -1); 1283 } 1284 1285 /* Does this register contain a constant zero? */ 1286 static bool register_is_null(struct bpf_reg_state reg) 1287 { 1288 return reg.type == SCALAR_VALUE && tnum_equals_const(reg.var_off, 0); 1289 } 1290 1291 /* when register 'regno' is passed into function that will read 'access_size' 1292 * bytes from that pointer, make sure that it's within stack boundary 1293 * and all elements of stack are initialized. 1294 * Unlike most pointer bounds-checking functions, this one doesn't take an 1295 * 'off' argument, so it has to add in reg->off itself. 1296 */ 1297 static int check_stack_boundary(struct bpf_verifier_env *env, int regno, 1298 int access_size, bool zero_size_allowed, 1299 struct bpf_call_arg_meta *meta) 1300 { 1301 struct bpf_verifier_state *state = env->cur_state; 1302 struct bpf_reg_state *regs = state->regs; 1303 int off, i, slot, spi; 1304 1305 if (regs[regno].type != PTR_TO_STACK) { 1306 /* Allow zero-byte read from NULL, regardless of pointer type */ 1307 if (zero_size_allowed && access_size == 0 && 1308 register_is_null(regs[regno])) 1309 return 0; 1310 1311 verbose(env, "R%d type=%s expected=%s\n", regno, 1312 reg_type_str[regs[regno].type], 1313 reg_type_str[PTR_TO_STACK]); 1314 return -EACCES; 1315 } 1316 1317 /* Only allow fixed-offset stack reads */ 1318 if (!tnum_is_const(regs[regno].var_off)) { 1319 char tn_buf[48]; 1320 1321 tnum_strn(tn_buf, sizeof(tn_buf), regs[regno].var_off); 1322 verbose(env, "invalid variable stack read R%d var_off=%s\n", 1323 regno, tn_buf); 1324 return -EACCES; 1325 } 1326 off = regs[regno].off + regs[regno].var_off.value; 1327 if (off >= 0 || off < -MAX_BPF_STACK || off + access_size > 0 || 1328 access_size < 0 || (access_size == 0 && !zero_size_allowed)) { 1329 verbose(env, "invalid stack type R%d off=%d access_size=%d\n", 1330 regno, off, access_size); 1331 return -EACCES; 1332 } 1333 1334 if (env->prog->aux->stack_depth < -off) 1335 env->prog->aux->stack_depth = -off; 1336 1337 if (meta && meta->raw_mode) { 1338 meta->access_size = access_size; 1339 meta->regno = regno; 1340 return 0; 1341 } 1342 1343 for (i = 0; i < access_size; i++) { 1344 slot = -(off + i) - 1; 1345 spi = slot / BPF_REG_SIZE; 1346 if (state->allocated_stack <= slot || 1347 state->stack[spi].slot_type[slot % BPF_REG_SIZE] != 1348 STACK_MISC) { 1349 verbose(env, "invalid indirect read from stack off %d+%d size %d\n", 1350 off, i, access_size); 1351 return -EACCES; 1352 } 1353 } 1354 return 0; 1355 } 1356 1357 static int check_helper_mem_access(struct bpf_verifier_env *env, int regno, 1358 int access_size, bool zero_size_allowed, 1359 struct bpf_call_arg_meta *meta) 1360 { 1361 struct bpf_reg_state *regs = cur_regs(env), *reg = ®s[regno]; 1362 1363 switch (reg->type) { 1364 case PTR_TO_PACKET: 1365 case PTR_TO_PACKET_META: 1366 return check_packet_access(env, regno, reg->off, access_size, 1367 zero_size_allowed); 1368 case PTR_TO_MAP_VALUE: 1369 return check_map_access(env, regno, reg->off, access_size, 1370 zero_size_allowed); 1371 default: /* scalar_value|ptr_to_stack or invalid ptr */ 1372 return check_stack_boundary(env, regno, access_size, 1373 zero_size_allowed, meta); 1374 } 1375 } 1376 1377 static int check_func_arg(struct bpf_verifier_env *env, u32 regno, 1378 enum bpf_arg_type arg_type, 1379 struct bpf_call_arg_meta *meta) 1380 { 1381 struct bpf_reg_state *regs = cur_regs(env), *reg = ®s[regno]; 1382 enum bpf_reg_type expected_type, type = reg->type; 1383 int err = 0; 1384 1385 if (arg_type == ARG_DONTCARE) 1386 return 0; 1387 1388 err = check_reg_arg(env, regno, SRC_OP); 1389 if (err) 1390 return err; 1391 1392 if (arg_type == ARG_ANYTHING) { 1393 if (is_pointer_value(env, regno)) { 1394 verbose(env, "R%d leaks addr into helper function\n", 1395 regno); 1396 return -EACCES; 1397 } 1398 return 0; 1399 } 1400 1401 if (type_is_pkt_pointer(type) && 1402 !may_access_direct_pkt_data(env, meta, BPF_READ)) { 1403 verbose(env, "helper access to the packet is not allowed\n"); 1404 return -EACCES; 1405 } 1406 1407 if (arg_type == ARG_PTR_TO_MAP_KEY || 1408 arg_type == ARG_PTR_TO_MAP_VALUE) { 1409 expected_type = PTR_TO_STACK; 1410 if (!type_is_pkt_pointer(type) && 1411 type != expected_type) 1412 goto err_type; 1413 } else if (arg_type == ARG_CONST_SIZE || 1414 arg_type == ARG_CONST_SIZE_OR_ZERO) { 1415 expected_type = SCALAR_VALUE; 1416 if (type != expected_type) 1417 goto err_type; 1418 } else if (arg_type == ARG_CONST_MAP_PTR) { 1419 expected_type = CONST_PTR_TO_MAP; 1420 if (type != expected_type) 1421 goto err_type; 1422 } else if (arg_type == ARG_PTR_TO_CTX) { 1423 expected_type = PTR_TO_CTX; 1424 if (type != expected_type) 1425 goto err_type; 1426 } else if (arg_type == ARG_PTR_TO_MEM || 1427 arg_type == ARG_PTR_TO_MEM_OR_NULL || 1428 arg_type == ARG_PTR_TO_UNINIT_MEM) { 1429 expected_type = PTR_TO_STACK; 1430 /* One exception here. In case function allows for NULL to be 1431 * passed in as argument, it's a SCALAR_VALUE type. Final test 1432 * happens during stack boundary checking. 1433 */ 1434 if (register_is_null(*reg) && 1435 arg_type == ARG_PTR_TO_MEM_OR_NULL) 1436 /* final test in check_stack_boundary() */; 1437 else if (!type_is_pkt_pointer(type) && 1438 type != PTR_TO_MAP_VALUE && 1439 type != expected_type) 1440 goto err_type; 1441 meta->raw_mode = arg_type == ARG_PTR_TO_UNINIT_MEM; 1442 } else { 1443 verbose(env, "unsupported arg_type %d\n", arg_type); 1444 return -EFAULT; 1445 } 1446 1447 if (arg_type == ARG_CONST_MAP_PTR) { 1448 /* bpf_map_xxx(map_ptr) call: remember that map_ptr */ 1449 meta->map_ptr = reg->map_ptr; 1450 } else if (arg_type == ARG_PTR_TO_MAP_KEY) { 1451 /* bpf_map_xxx(..., map_ptr, ..., key) call: 1452 * check that [key, key + map->key_size) are within 1453 * stack limits and initialized 1454 */ 1455 if (!meta->map_ptr) { 1456 /* in function declaration map_ptr must come before 1457 * map_key, so that it's verified and known before 1458 * we have to check map_key here. Otherwise it means 1459 * that kernel subsystem misconfigured verifier 1460 */ 1461 verbose(env, "invalid map_ptr to access map->key\n"); 1462 return -EACCES; 1463 } 1464 if (type_is_pkt_pointer(type)) 1465 err = check_packet_access(env, regno, reg->off, 1466 meta->map_ptr->key_size, 1467 false); 1468 else 1469 err = check_stack_boundary(env, regno, 1470 meta->map_ptr->key_size, 1471 false, NULL); 1472 } else if (arg_type == ARG_PTR_TO_MAP_VALUE) { 1473 /* bpf_map_xxx(..., map_ptr, ..., value) call: 1474 * check [value, value + map->value_size) validity 1475 */ 1476 if (!meta->map_ptr) { 1477 /* kernel subsystem misconfigured verifier */ 1478 verbose(env, "invalid map_ptr to access map->value\n"); 1479 return -EACCES; 1480 } 1481 if (type_is_pkt_pointer(type)) 1482 err = check_packet_access(env, regno, reg->off, 1483 meta->map_ptr->value_size, 1484 false); 1485 else 1486 err = check_stack_boundary(env, regno, 1487 meta->map_ptr->value_size, 1488 false, NULL); 1489 } else if (arg_type == ARG_CONST_SIZE || 1490 arg_type == ARG_CONST_SIZE_OR_ZERO) { 1491 bool zero_size_allowed = (arg_type == ARG_CONST_SIZE_OR_ZERO); 1492 1493 /* bpf_xxx(..., buf, len) call will access 'len' bytes 1494 * from stack pointer 'buf'. Check it 1495 * note: regno == len, regno - 1 == buf 1496 */ 1497 if (regno == 0) { 1498 /* kernel subsystem misconfigured verifier */ 1499 verbose(env, 1500 "ARG_CONST_SIZE cannot be first argument\n"); 1501 return -EACCES; 1502 } 1503 1504 /* The register is SCALAR_VALUE; the access check 1505 * happens using its boundaries. 1506 */ 1507 1508 if (!tnum_is_const(reg->var_off)) 1509 /* For unprivileged variable accesses, disable raw 1510 * mode so that the program is required to 1511 * initialize all the memory that the helper could 1512 * just partially fill up. 1513 */ 1514 meta = NULL; 1515 1516 if (reg->smin_value < 0) { 1517 verbose(env, "R%d min value is negative, either use unsigned or 'var &= const'\n", 1518 regno); 1519 return -EACCES; 1520 } 1521 1522 if (reg->umin_value == 0) { 1523 err = check_helper_mem_access(env, regno - 1, 0, 1524 zero_size_allowed, 1525 meta); 1526 if (err) 1527 return err; 1528 } 1529 1530 if (reg->umax_value >= BPF_MAX_VAR_SIZ) { 1531 verbose(env, "R%d unbounded memory access, use 'var &= const' or 'if (var < const)'\n", 1532 regno); 1533 return -EACCES; 1534 } 1535 err = check_helper_mem_access(env, regno - 1, 1536 reg->umax_value, 1537 zero_size_allowed, meta); 1538 } 1539 1540 return err; 1541 err_type: 1542 verbose(env, "R%d type=%s expected=%s\n", regno, 1543 reg_type_str[type], reg_type_str[expected_type]); 1544 return -EACCES; 1545 } 1546 1547 static int check_map_func_compatibility(struct bpf_verifier_env *env, 1548 struct bpf_map *map, int func_id) 1549 { 1550 if (!map) 1551 return 0; 1552 1553 /* We need a two way check, first is from map perspective ... */ 1554 switch (map->map_type) { 1555 case BPF_MAP_TYPE_PROG_ARRAY: 1556 if (func_id != BPF_FUNC_tail_call) 1557 goto error; 1558 break; 1559 case BPF_MAP_TYPE_PERF_EVENT_ARRAY: 1560 if (func_id != BPF_FUNC_perf_event_read && 1561 func_id != BPF_FUNC_perf_event_output && 1562 func_id != BPF_FUNC_perf_event_read_value) 1563 goto error; 1564 break; 1565 case BPF_MAP_TYPE_STACK_TRACE: 1566 if (func_id != BPF_FUNC_get_stackid) 1567 goto error; 1568 break; 1569 case BPF_MAP_TYPE_CGROUP_ARRAY: 1570 if (func_id != BPF_FUNC_skb_under_cgroup && 1571 func_id != BPF_FUNC_current_task_under_cgroup) 1572 goto error; 1573 break; 1574 /* devmap returns a pointer to a live net_device ifindex that we cannot 1575 * allow to be modified from bpf side. So do not allow lookup elements 1576 * for now. 1577 */ 1578 case BPF_MAP_TYPE_DEVMAP: 1579 if (func_id != BPF_FUNC_redirect_map) 1580 goto error; 1581 break; 1582 /* Restrict bpf side of cpumap, open when use-cases appear */ 1583 case BPF_MAP_TYPE_CPUMAP: 1584 if (func_id != BPF_FUNC_redirect_map) 1585 goto error; 1586 break; 1587 case BPF_MAP_TYPE_ARRAY_OF_MAPS: 1588 case BPF_MAP_TYPE_HASH_OF_MAPS: 1589 if (func_id != BPF_FUNC_map_lookup_elem) 1590 goto error; 1591 break; 1592 case BPF_MAP_TYPE_SOCKMAP: 1593 if (func_id != BPF_FUNC_sk_redirect_map && 1594 func_id != BPF_FUNC_sock_map_update && 1595 func_id != BPF_FUNC_map_delete_elem) 1596 goto error; 1597 break; 1598 default: 1599 break; 1600 } 1601 1602 /* ... and second from the function itself. */ 1603 switch (func_id) { 1604 case BPF_FUNC_tail_call: 1605 if (map->map_type != BPF_MAP_TYPE_PROG_ARRAY) 1606 goto error; 1607 break; 1608 case BPF_FUNC_perf_event_read: 1609 case BPF_FUNC_perf_event_output: 1610 case BPF_FUNC_perf_event_read_value: 1611 if (map->map_type != BPF_MAP_TYPE_PERF_EVENT_ARRAY) 1612 goto error; 1613 break; 1614 case BPF_FUNC_get_stackid: 1615 if (map->map_type != BPF_MAP_TYPE_STACK_TRACE) 1616 goto error; 1617 break; 1618 case BPF_FUNC_current_task_under_cgroup: 1619 case BPF_FUNC_skb_under_cgroup: 1620 if (map->map_type != BPF_MAP_TYPE_CGROUP_ARRAY) 1621 goto error; 1622 break; 1623 case BPF_FUNC_redirect_map: 1624 if (map->map_type != BPF_MAP_TYPE_DEVMAP && 1625 map->map_type != BPF_MAP_TYPE_CPUMAP) 1626 goto error; 1627 break; 1628 case BPF_FUNC_sk_redirect_map: 1629 if (map->map_type != BPF_MAP_TYPE_SOCKMAP) 1630 goto error; 1631 break; 1632 case BPF_FUNC_sock_map_update: 1633 if (map->map_type != BPF_MAP_TYPE_SOCKMAP) 1634 goto error; 1635 break; 1636 default: 1637 break; 1638 } 1639 1640 return 0; 1641 error: 1642 verbose(env, "cannot pass map_type %d into func %s#%d\n", 1643 map->map_type, func_id_name(func_id), func_id); 1644 return -EINVAL; 1645 } 1646 1647 static int check_raw_mode(const struct bpf_func_proto *fn) 1648 { 1649 int count = 0; 1650 1651 if (fn->arg1_type == ARG_PTR_TO_UNINIT_MEM) 1652 count++; 1653 if (fn->arg2_type == ARG_PTR_TO_UNINIT_MEM) 1654 count++; 1655 if (fn->arg3_type == ARG_PTR_TO_UNINIT_MEM) 1656 count++; 1657 if (fn->arg4_type == ARG_PTR_TO_UNINIT_MEM) 1658 count++; 1659 if (fn->arg5_type == ARG_PTR_TO_UNINIT_MEM) 1660 count++; 1661 1662 return count > 1 ? -EINVAL : 0; 1663 } 1664 1665 /* Packet data might have moved, any old PTR_TO_PACKET[_META,_END] 1666 * are now invalid, so turn them into unknown SCALAR_VALUE. 1667 */ 1668 static void clear_all_pkt_pointers(struct bpf_verifier_env *env) 1669 { 1670 struct bpf_verifier_state *state = env->cur_state; 1671 struct bpf_reg_state *regs = state->regs, *reg; 1672 int i; 1673 1674 for (i = 0; i < MAX_BPF_REG; i++) 1675 if (reg_is_pkt_pointer_any(®s[i])) 1676 mark_reg_unknown(env, regs, i); 1677 1678 for (i = 0; i < state->allocated_stack / BPF_REG_SIZE; i++) { 1679 if (state->stack[i].slot_type[0] != STACK_SPILL) 1680 continue; 1681 reg = &state->stack[i].spilled_ptr; 1682 if (reg_is_pkt_pointer_any(reg)) 1683 __mark_reg_unknown(reg); 1684 } 1685 } 1686 1687 static int check_call(struct bpf_verifier_env *env, int func_id, int insn_idx) 1688 { 1689 const struct bpf_func_proto *fn = NULL; 1690 struct bpf_reg_state *regs; 1691 struct bpf_call_arg_meta meta; 1692 bool changes_data; 1693 int i, err; 1694 1695 /* find function prototype */ 1696 if (func_id < 0 || func_id >= __BPF_FUNC_MAX_ID) { 1697 verbose(env, "invalid func %s#%d\n", func_id_name(func_id), 1698 func_id); 1699 return -EINVAL; 1700 } 1701 1702 if (env->ops->get_func_proto) 1703 fn = env->ops->get_func_proto(func_id); 1704 1705 if (!fn) { 1706 verbose(env, "unknown func %s#%d\n", func_id_name(func_id), 1707 func_id); 1708 return -EINVAL; 1709 } 1710 1711 /* eBPF programs must be GPL compatible to use GPL-ed functions */ 1712 if (!env->prog->gpl_compatible && fn->gpl_only) { 1713 verbose(env, "cannot call GPL only function from proprietary program\n"); 1714 return -EINVAL; 1715 } 1716 1717 /* With LD_ABS/IND some JITs save/restore skb from r1. */ 1718 changes_data = bpf_helper_changes_pkt_data(fn->func); 1719 if (changes_data && fn->arg1_type != ARG_PTR_TO_CTX) { 1720 verbose(env, "kernel subsystem misconfigured func %s#%d: r1 != ctx\n", 1721 func_id_name(func_id), func_id); 1722 return -EINVAL; 1723 } 1724 1725 memset(&meta, 0, sizeof(meta)); 1726 meta.pkt_access = fn->pkt_access; 1727 1728 /* We only support one arg being in raw mode at the moment, which 1729 * is sufficient for the helper functions we have right now. 1730 */ 1731 err = check_raw_mode(fn); 1732 if (err) { 1733 verbose(env, "kernel subsystem misconfigured func %s#%d\n", 1734 func_id_name(func_id), func_id); 1735 return err; 1736 } 1737 1738 /* check args */ 1739 err = check_func_arg(env, BPF_REG_1, fn->arg1_type, &meta); 1740 if (err) 1741 return err; 1742 err = check_func_arg(env, BPF_REG_2, fn->arg2_type, &meta); 1743 if (err) 1744 return err; 1745 if (func_id == BPF_FUNC_tail_call) { 1746 if (meta.map_ptr == NULL) { 1747 verbose(env, "verifier bug\n"); 1748 return -EINVAL; 1749 } 1750 env->insn_aux_data[insn_idx].map_ptr = meta.map_ptr; 1751 } 1752 err = check_func_arg(env, BPF_REG_3, fn->arg3_type, &meta); 1753 if (err) 1754 return err; 1755 err = check_func_arg(env, BPF_REG_4, fn->arg4_type, &meta); 1756 if (err) 1757 return err; 1758 err = check_func_arg(env, BPF_REG_5, fn->arg5_type, &meta); 1759 if (err) 1760 return err; 1761 1762 /* Mark slots with STACK_MISC in case of raw mode, stack offset 1763 * is inferred from register state. 1764 */ 1765 for (i = 0; i < meta.access_size; i++) { 1766 err = check_mem_access(env, insn_idx, meta.regno, i, BPF_B, BPF_WRITE, -1); 1767 if (err) 1768 return err; 1769 } 1770 1771 regs = cur_regs(env); 1772 /* reset caller saved regs */ 1773 for (i = 0; i < CALLER_SAVED_REGS; i++) { 1774 mark_reg_not_init(env, regs, caller_saved[i]); 1775 check_reg_arg(env, caller_saved[i], DST_OP_NO_MARK); 1776 } 1777 1778 /* update return register (already marked as written above) */ 1779 if (fn->ret_type == RET_INTEGER) { 1780 /* sets type to SCALAR_VALUE */ 1781 mark_reg_unknown(env, regs, BPF_REG_0); 1782 } else if (fn->ret_type == RET_VOID) { 1783 regs[BPF_REG_0].type = NOT_INIT; 1784 } else if (fn->ret_type == RET_PTR_TO_MAP_VALUE_OR_NULL) { 1785 struct bpf_insn_aux_data *insn_aux; 1786 1787 regs[BPF_REG_0].type = PTR_TO_MAP_VALUE_OR_NULL; 1788 /* There is no offset yet applied, variable or fixed */ 1789 mark_reg_known_zero(env, regs, BPF_REG_0); 1790 regs[BPF_REG_0].off = 0; 1791 /* remember map_ptr, so that check_map_access() 1792 * can check 'value_size' boundary of memory access 1793 * to map element returned from bpf_map_lookup_elem() 1794 */ 1795 if (meta.map_ptr == NULL) { 1796 verbose(env, 1797 "kernel subsystem misconfigured verifier\n"); 1798 return -EINVAL; 1799 } 1800 regs[BPF_REG_0].map_ptr = meta.map_ptr; 1801 regs[BPF_REG_0].id = ++env->id_gen; 1802 insn_aux = &env->insn_aux_data[insn_idx]; 1803 if (!insn_aux->map_ptr) 1804 insn_aux->map_ptr = meta.map_ptr; 1805 else if (insn_aux->map_ptr != meta.map_ptr) 1806 insn_aux->map_ptr = BPF_MAP_PTR_POISON; 1807 } else { 1808 verbose(env, "unknown return type %d of func %s#%d\n", 1809 fn->ret_type, func_id_name(func_id), func_id); 1810 return -EINVAL; 1811 } 1812 1813 err = check_map_func_compatibility(env, meta.map_ptr, func_id); 1814 if (err) 1815 return err; 1816 1817 if (changes_data) 1818 clear_all_pkt_pointers(env); 1819 return 0; 1820 } 1821 1822 static bool signed_add_overflows(s64 a, s64 b) 1823 { 1824 /* Do the add in u64, where overflow is well-defined */ 1825 s64 res = (s64)((u64)a + (u64)b); 1826 1827 if (b < 0) 1828 return res > a; 1829 return res < a; 1830 } 1831 1832 static bool signed_sub_overflows(s64 a, s64 b) 1833 { 1834 /* Do the sub in u64, where overflow is well-defined */ 1835 s64 res = (s64)((u64)a - (u64)b); 1836 1837 if (b < 0) 1838 return res < a; 1839 return res > a; 1840 } 1841 1842 static bool check_reg_sane_offset(struct bpf_verifier_env *env, 1843 const struct bpf_reg_state *reg, 1844 enum bpf_reg_type type) 1845 { 1846 bool known = tnum_is_const(reg->var_off); 1847 s64 val = reg->var_off.value; 1848 s64 smin = reg->smin_value; 1849 1850 if (known && (val >= BPF_MAX_VAR_OFF || val <= -BPF_MAX_VAR_OFF)) { 1851 verbose(env, "math between %s pointer and %lld is not allowed\n", 1852 reg_type_str[type], val); 1853 return false; 1854 } 1855 1856 if (reg->off >= BPF_MAX_VAR_OFF || reg->off <= -BPF_MAX_VAR_OFF) { 1857 verbose(env, "%s pointer offset %d is not allowed\n", 1858 reg_type_str[type], reg->off); 1859 return false; 1860 } 1861 1862 if (smin == S64_MIN) { 1863 verbose(env, "math between %s pointer and register with unbounded min value is not allowed\n", 1864 reg_type_str[type]); 1865 return false; 1866 } 1867 1868 if (smin >= BPF_MAX_VAR_OFF || smin <= -BPF_MAX_VAR_OFF) { 1869 verbose(env, "value %lld makes %s pointer be out of bounds\n", 1870 smin, reg_type_str[type]); 1871 return false; 1872 } 1873 1874 return true; 1875 } 1876 1877 /* Handles arithmetic on a pointer and a scalar: computes new min/max and var_off. 1878 * Caller should also handle BPF_MOV case separately. 1879 * If we return -EACCES, caller may want to try again treating pointer as a 1880 * scalar. So we only emit a diagnostic if !env->allow_ptr_leaks. 1881 */ 1882 static int adjust_ptr_min_max_vals(struct bpf_verifier_env *env, 1883 struct bpf_insn *insn, 1884 const struct bpf_reg_state *ptr_reg, 1885 const struct bpf_reg_state *off_reg) 1886 { 1887 struct bpf_reg_state *regs = cur_regs(env), *dst_reg; 1888 bool known = tnum_is_const(off_reg->var_off); 1889 s64 smin_val = off_reg->smin_value, smax_val = off_reg->smax_value, 1890 smin_ptr = ptr_reg->smin_value, smax_ptr = ptr_reg->smax_value; 1891 u64 umin_val = off_reg->umin_value, umax_val = off_reg->umax_value, 1892 umin_ptr = ptr_reg->umin_value, umax_ptr = ptr_reg->umax_value; 1893 u8 opcode = BPF_OP(insn->code); 1894 u32 dst = insn->dst_reg; 1895 1896 dst_reg = ®s[dst]; 1897 1898 if ((known && (smin_val != smax_val || umin_val != umax_val)) || 1899 smin_val > smax_val || umin_val > umax_val) { 1900 /* Taint dst register if offset had invalid bounds derived from 1901 * e.g. dead branches. 1902 */ 1903 __mark_reg_unknown(dst_reg); 1904 return 0; 1905 } 1906 1907 if (BPF_CLASS(insn->code) != BPF_ALU64) { 1908 /* 32-bit ALU ops on pointers produce (meaningless) scalars */ 1909 verbose(env, 1910 "R%d 32-bit pointer arithmetic prohibited\n", 1911 dst); 1912 return -EACCES; 1913 } 1914 1915 if (ptr_reg->type == PTR_TO_MAP_VALUE_OR_NULL) { 1916 verbose(env, "R%d pointer arithmetic on PTR_TO_MAP_VALUE_OR_NULL prohibited, null-check it first\n", 1917 dst); 1918 return -EACCES; 1919 } 1920 if (ptr_reg->type == CONST_PTR_TO_MAP) { 1921 verbose(env, "R%d pointer arithmetic on CONST_PTR_TO_MAP prohibited\n", 1922 dst); 1923 return -EACCES; 1924 } 1925 if (ptr_reg->type == PTR_TO_PACKET_END) { 1926 verbose(env, "R%d pointer arithmetic on PTR_TO_PACKET_END prohibited\n", 1927 dst); 1928 return -EACCES; 1929 } 1930 1931 /* In case of 'scalar += pointer', dst_reg inherits pointer type and id. 1932 * The id may be overwritten later if we create a new variable offset. 1933 */ 1934 dst_reg->type = ptr_reg->type; 1935 dst_reg->id = ptr_reg->id; 1936 1937 if (!check_reg_sane_offset(env, off_reg, ptr_reg->type) || 1938 !check_reg_sane_offset(env, ptr_reg, ptr_reg->type)) 1939 return -EINVAL; 1940 1941 switch (opcode) { 1942 case BPF_ADD: 1943 /* We can take a fixed offset as long as it doesn't overflow 1944 * the s32 'off' field 1945 */ 1946 if (known && (ptr_reg->off + smin_val == 1947 (s64)(s32)(ptr_reg->off + smin_val))) { 1948 /* pointer += K. Accumulate it into fixed offset */ 1949 dst_reg->smin_value = smin_ptr; 1950 dst_reg->smax_value = smax_ptr; 1951 dst_reg->umin_value = umin_ptr; 1952 dst_reg->umax_value = umax_ptr; 1953 dst_reg->var_off = ptr_reg->var_off; 1954 dst_reg->off = ptr_reg->off + smin_val; 1955 dst_reg->range = ptr_reg->range; 1956 break; 1957 } 1958 /* A new variable offset is created. Note that off_reg->off 1959 * == 0, since it's a scalar. 1960 * dst_reg gets the pointer type and since some positive 1961 * integer value was added to the pointer, give it a new 'id' 1962 * if it's a PTR_TO_PACKET. 1963 * this creates a new 'base' pointer, off_reg (variable) gets 1964 * added into the variable offset, and we copy the fixed offset 1965 * from ptr_reg. 1966 */ 1967 if (signed_add_overflows(smin_ptr, smin_val) || 1968 signed_add_overflows(smax_ptr, smax_val)) { 1969 dst_reg->smin_value = S64_MIN; 1970 dst_reg->smax_value = S64_MAX; 1971 } else { 1972 dst_reg->smin_value = smin_ptr + smin_val; 1973 dst_reg->smax_value = smax_ptr + smax_val; 1974 } 1975 if (umin_ptr + umin_val < umin_ptr || 1976 umax_ptr + umax_val < umax_ptr) { 1977 dst_reg->umin_value = 0; 1978 dst_reg->umax_value = U64_MAX; 1979 } else { 1980 dst_reg->umin_value = umin_ptr + umin_val; 1981 dst_reg->umax_value = umax_ptr + umax_val; 1982 } 1983 dst_reg->var_off = tnum_add(ptr_reg->var_off, off_reg->var_off); 1984 dst_reg->off = ptr_reg->off; 1985 if (reg_is_pkt_pointer(ptr_reg)) { 1986 dst_reg->id = ++env->id_gen; 1987 /* something was added to pkt_ptr, set range to zero */ 1988 dst_reg->range = 0; 1989 } 1990 break; 1991 case BPF_SUB: 1992 if (dst_reg == off_reg) { 1993 /* scalar -= pointer. Creates an unknown scalar */ 1994 verbose(env, "R%d tried to subtract pointer from scalar\n", 1995 dst); 1996 return -EACCES; 1997 } 1998 /* We don't allow subtraction from FP, because (according to 1999 * test_verifier.c test "invalid fp arithmetic", JITs might not 2000 * be able to deal with it. 2001 */ 2002 if (ptr_reg->type == PTR_TO_STACK) { 2003 verbose(env, "R%d subtraction from stack pointer prohibited\n", 2004 dst); 2005 return -EACCES; 2006 } 2007 if (known && (ptr_reg->off - smin_val == 2008 (s64)(s32)(ptr_reg->off - smin_val))) { 2009 /* pointer -= K. Subtract it from fixed offset */ 2010 dst_reg->smin_value = smin_ptr; 2011 dst_reg->smax_value = smax_ptr; 2012 dst_reg->umin_value = umin_ptr; 2013 dst_reg->umax_value = umax_ptr; 2014 dst_reg->var_off = ptr_reg->var_off; 2015 dst_reg->id = ptr_reg->id; 2016 dst_reg->off = ptr_reg->off - smin_val; 2017 dst_reg->range = ptr_reg->range; 2018 break; 2019 } 2020 /* A new variable offset is created. If the subtrahend is known 2021 * nonnegative, then any reg->range we had before is still good. 2022 */ 2023 if (signed_sub_overflows(smin_ptr, smax_val) || 2024 signed_sub_overflows(smax_ptr, smin_val)) { 2025 /* Overflow possible, we know nothing */ 2026 dst_reg->smin_value = S64_MIN; 2027 dst_reg->smax_value = S64_MAX; 2028 } else { 2029 dst_reg->smin_value = smin_ptr - smax_val; 2030 dst_reg->smax_value = smax_ptr - smin_val; 2031 } 2032 if (umin_ptr < umax_val) { 2033 /* Overflow possible, we know nothing */ 2034 dst_reg->umin_value = 0; 2035 dst_reg->umax_value = U64_MAX; 2036 } else { 2037 /* Cannot overflow (as long as bounds are consistent) */ 2038 dst_reg->umin_value = umin_ptr - umax_val; 2039 dst_reg->umax_value = umax_ptr - umin_val; 2040 } 2041 dst_reg->var_off = tnum_sub(ptr_reg->var_off, off_reg->var_off); 2042 dst_reg->off = ptr_reg->off; 2043 if (reg_is_pkt_pointer(ptr_reg)) { 2044 dst_reg->id = ++env->id_gen; 2045 /* something was added to pkt_ptr, set range to zero */ 2046 if (smin_val < 0) 2047 dst_reg->range = 0; 2048 } 2049 break; 2050 case BPF_AND: 2051 case BPF_OR: 2052 case BPF_XOR: 2053 /* bitwise ops on pointers are troublesome, prohibit. */ 2054 verbose(env, "R%d bitwise operator %s on pointer prohibited\n", 2055 dst, bpf_alu_string[opcode >> 4]); 2056 return -EACCES; 2057 default: 2058 /* other operators (e.g. MUL,LSH) produce non-pointer results */ 2059 verbose(env, "R%d pointer arithmetic with %s operator prohibited\n", 2060 dst, bpf_alu_string[opcode >> 4]); 2061 return -EACCES; 2062 } 2063 2064 if (!check_reg_sane_offset(env, dst_reg, ptr_reg->type)) 2065 return -EINVAL; 2066 2067 __update_reg_bounds(dst_reg); 2068 __reg_deduce_bounds(dst_reg); 2069 __reg_bound_offset(dst_reg); 2070 return 0; 2071 } 2072 2073 /* WARNING: This function does calculations on 64-bit values, but the actual 2074 * execution may occur on 32-bit values. Therefore, things like bitshifts 2075 * need extra checks in the 32-bit case. 2076 */ 2077 static int adjust_scalar_min_max_vals(struct bpf_verifier_env *env, 2078 struct bpf_insn *insn, 2079 struct bpf_reg_state *dst_reg, 2080 struct bpf_reg_state src_reg) 2081 { 2082 struct bpf_reg_state *regs = cur_regs(env); 2083 u8 opcode = BPF_OP(insn->code); 2084 bool src_known, dst_known; 2085 s64 smin_val, smax_val; 2086 u64 umin_val, umax_val; 2087 u64 insn_bitness = (BPF_CLASS(insn->code) == BPF_ALU64) ? 64 : 32; 2088 2089 smin_val = src_reg.smin_value; 2090 smax_val = src_reg.smax_value; 2091 umin_val = src_reg.umin_value; 2092 umax_val = src_reg.umax_value; 2093 src_known = tnum_is_const(src_reg.var_off); 2094 dst_known = tnum_is_const(dst_reg->var_off); 2095 2096 if ((src_known && (smin_val != smax_val || umin_val != umax_val)) || 2097 smin_val > smax_val || umin_val > umax_val) { 2098 /* Taint dst register if offset had invalid bounds derived from 2099 * e.g. dead branches. 2100 */ 2101 __mark_reg_unknown(dst_reg); 2102 return 0; 2103 } 2104 2105 if (!src_known && 2106 opcode != BPF_ADD && opcode != BPF_SUB && opcode != BPF_AND) { 2107 __mark_reg_unknown(dst_reg); 2108 return 0; 2109 } 2110 2111 switch (opcode) { 2112 case BPF_ADD: 2113 if (signed_add_overflows(dst_reg->smin_value, smin_val) || 2114 signed_add_overflows(dst_reg->smax_value, smax_val)) { 2115 dst_reg->smin_value = S64_MIN; 2116 dst_reg->smax_value = S64_MAX; 2117 } else { 2118 dst_reg->smin_value += smin_val; 2119 dst_reg->smax_value += smax_val; 2120 } 2121 if (dst_reg->umin_value + umin_val < umin_val || 2122 dst_reg->umax_value + umax_val < umax_val) { 2123 dst_reg->umin_value = 0; 2124 dst_reg->umax_value = U64_MAX; 2125 } else { 2126 dst_reg->umin_value += umin_val; 2127 dst_reg->umax_value += umax_val; 2128 } 2129 dst_reg->var_off = tnum_add(dst_reg->var_off, src_reg.var_off); 2130 break; 2131 case BPF_SUB: 2132 if (signed_sub_overflows(dst_reg->smin_value, smax_val) || 2133 signed_sub_overflows(dst_reg->smax_value, smin_val)) { 2134 /* Overflow possible, we know nothing */ 2135 dst_reg->smin_value = S64_MIN; 2136 dst_reg->smax_value = S64_MAX; 2137 } else { 2138 dst_reg->smin_value -= smax_val; 2139 dst_reg->smax_value -= smin_val; 2140 } 2141 if (dst_reg->umin_value < umax_val) { 2142 /* Overflow possible, we know nothing */ 2143 dst_reg->umin_value = 0; 2144 dst_reg->umax_value = U64_MAX; 2145 } else { 2146 /* Cannot overflow (as long as bounds are consistent) */ 2147 dst_reg->umin_value -= umax_val; 2148 dst_reg->umax_value -= umin_val; 2149 } 2150 dst_reg->var_off = tnum_sub(dst_reg->var_off, src_reg.var_off); 2151 break; 2152 case BPF_MUL: 2153 dst_reg->var_off = tnum_mul(dst_reg->var_off, src_reg.var_off); 2154 if (smin_val < 0 || dst_reg->smin_value < 0) { 2155 /* Ain't nobody got time to multiply that sign */ 2156 __mark_reg_unbounded(dst_reg); 2157 __update_reg_bounds(dst_reg); 2158 break; 2159 } 2160 /* Both values are positive, so we can work with unsigned and 2161 * copy the result to signed (unless it exceeds S64_MAX). 2162 */ 2163 if (umax_val > U32_MAX || dst_reg->umax_value > U32_MAX) { 2164 /* Potential overflow, we know nothing */ 2165 __mark_reg_unbounded(dst_reg); 2166 /* (except what we can learn from the var_off) */ 2167 __update_reg_bounds(dst_reg); 2168 break; 2169 } 2170 dst_reg->umin_value *= umin_val; 2171 dst_reg->umax_value *= umax_val; 2172 if (dst_reg->umax_value > S64_MAX) { 2173 /* Overflow possible, we know nothing */ 2174 dst_reg->smin_value = S64_MIN; 2175 dst_reg->smax_value = S64_MAX; 2176 } else { 2177 dst_reg->smin_value = dst_reg->umin_value; 2178 dst_reg->smax_value = dst_reg->umax_value; 2179 } 2180 break; 2181 case BPF_AND: 2182 if (src_known && dst_known) { 2183 __mark_reg_known(dst_reg, dst_reg->var_off.value & 2184 src_reg.var_off.value); 2185 break; 2186 } 2187 /* We get our minimum from the var_off, since that's inherently 2188 * bitwise. Our maximum is the minimum of the operands' maxima. 2189 */ 2190 dst_reg->var_off = tnum_and(dst_reg->var_off, src_reg.var_off); 2191 dst_reg->umin_value = dst_reg->var_off.value; 2192 dst_reg->umax_value = min(dst_reg->umax_value, umax_val); 2193 if (dst_reg->smin_value < 0 || smin_val < 0) { 2194 /* Lose signed bounds when ANDing negative numbers, 2195 * ain't nobody got time for that. 2196 */ 2197 dst_reg->smin_value = S64_MIN; 2198 dst_reg->smax_value = S64_MAX; 2199 } else { 2200 /* ANDing two positives gives a positive, so safe to 2201 * cast result into s64. 2202 */ 2203 dst_reg->smin_value = dst_reg->umin_value; 2204 dst_reg->smax_value = dst_reg->umax_value; 2205 } 2206 /* We may learn something more from the var_off */ 2207 __update_reg_bounds(dst_reg); 2208 break; 2209 case BPF_OR: 2210 if (src_known && dst_known) { 2211 __mark_reg_known(dst_reg, dst_reg->var_off.value | 2212 src_reg.var_off.value); 2213 break; 2214 } 2215 /* We get our maximum from the var_off, and our minimum is the 2216 * maximum of the operands' minima 2217 */ 2218 dst_reg->var_off = tnum_or(dst_reg->var_off, src_reg.var_off); 2219 dst_reg->umin_value = max(dst_reg->umin_value, umin_val); 2220 dst_reg->umax_value = dst_reg->var_off.value | 2221 dst_reg->var_off.mask; 2222 if (dst_reg->smin_value < 0 || smin_val < 0) { 2223 /* Lose signed bounds when ORing negative numbers, 2224 * ain't nobody got time for that. 2225 */ 2226 dst_reg->smin_value = S64_MIN; 2227 dst_reg->smax_value = S64_MAX; 2228 } else { 2229 /* ORing two positives gives a positive, so safe to 2230 * cast result into s64. 2231 */ 2232 dst_reg->smin_value = dst_reg->umin_value; 2233 dst_reg->smax_value = dst_reg->umax_value; 2234 } 2235 /* We may learn something more from the var_off */ 2236 __update_reg_bounds(dst_reg); 2237 break; 2238 case BPF_LSH: 2239 if (umax_val >= insn_bitness) { 2240 /* Shifts greater than 31 or 63 are undefined. 2241 * This includes shifts by a negative number. 2242 */ 2243 mark_reg_unknown(env, regs, insn->dst_reg); 2244 break; 2245 } 2246 /* We lose all sign bit information (except what we can pick 2247 * up from var_off) 2248 */ 2249 dst_reg->smin_value = S64_MIN; 2250 dst_reg->smax_value = S64_MAX; 2251 /* If we might shift our top bit out, then we know nothing */ 2252 if (dst_reg->umax_value > 1ULL << (63 - umax_val)) { 2253 dst_reg->umin_value = 0; 2254 dst_reg->umax_value = U64_MAX; 2255 } else { 2256 dst_reg->umin_value <<= umin_val; 2257 dst_reg->umax_value <<= umax_val; 2258 } 2259 if (src_known) 2260 dst_reg->var_off = tnum_lshift(dst_reg->var_off, umin_val); 2261 else 2262 dst_reg->var_off = tnum_lshift(tnum_unknown, umin_val); 2263 /* We may learn something more from the var_off */ 2264 __update_reg_bounds(dst_reg); 2265 break; 2266 case BPF_RSH: 2267 if (umax_val >= insn_bitness) { 2268 /* Shifts greater than 31 or 63 are undefined. 2269 * This includes shifts by a negative number. 2270 */ 2271 mark_reg_unknown(env, regs, insn->dst_reg); 2272 break; 2273 } 2274 /* BPF_RSH is an unsigned shift. If the value in dst_reg might 2275 * be negative, then either: 2276 * 1) src_reg might be zero, so the sign bit of the result is 2277 * unknown, so we lose our signed bounds 2278 * 2) it's known negative, thus the unsigned bounds capture the 2279 * signed bounds 2280 * 3) the signed bounds cross zero, so they tell us nothing 2281 * about the result 2282 * If the value in dst_reg is known nonnegative, then again the 2283 * unsigned bounts capture the signed bounds. 2284 * Thus, in all cases it suffices to blow away our signed bounds 2285 * and rely on inferring new ones from the unsigned bounds and 2286 * var_off of the result. 2287 */ 2288 dst_reg->smin_value = S64_MIN; 2289 dst_reg->smax_value = S64_MAX; 2290 if (src_known) 2291 dst_reg->var_off = tnum_rshift(dst_reg->var_off, 2292 umin_val); 2293 else 2294 dst_reg->var_off = tnum_rshift(tnum_unknown, umin_val); 2295 dst_reg->umin_value >>= umax_val; 2296 dst_reg->umax_value >>= umin_val; 2297 /* We may learn something more from the var_off */ 2298 __update_reg_bounds(dst_reg); 2299 break; 2300 default: 2301 mark_reg_unknown(env, regs, insn->dst_reg); 2302 break; 2303 } 2304 2305 if (BPF_CLASS(insn->code) != BPF_ALU64) { 2306 /* 32-bit ALU ops are (32,32)->32 */ 2307 coerce_reg_to_size(dst_reg, 4); 2308 coerce_reg_to_size(&src_reg, 4); 2309 } 2310 2311 __reg_deduce_bounds(dst_reg); 2312 __reg_bound_offset(dst_reg); 2313 return 0; 2314 } 2315 2316 /* Handles ALU ops other than BPF_END, BPF_NEG and BPF_MOV: computes new min/max 2317 * and var_off. 2318 */ 2319 static int adjust_reg_min_max_vals(struct bpf_verifier_env *env, 2320 struct bpf_insn *insn) 2321 { 2322 struct bpf_reg_state *regs = cur_regs(env), *dst_reg, *src_reg; 2323 struct bpf_reg_state *ptr_reg = NULL, off_reg = {0}; 2324 u8 opcode = BPF_OP(insn->code); 2325 2326 dst_reg = ®s[insn->dst_reg]; 2327 src_reg = NULL; 2328 if (dst_reg->type != SCALAR_VALUE) 2329 ptr_reg = dst_reg; 2330 if (BPF_SRC(insn->code) == BPF_X) { 2331 src_reg = ®s[insn->src_reg]; 2332 if (src_reg->type != SCALAR_VALUE) { 2333 if (dst_reg->type != SCALAR_VALUE) { 2334 /* Combining two pointers by any ALU op yields 2335 * an arbitrary scalar. Disallow all math except 2336 * pointer subtraction 2337 */ 2338 if (opcode == BPF_SUB){ 2339 mark_reg_unknown(env, regs, insn->dst_reg); 2340 return 0; 2341 } 2342 verbose(env, "R%d pointer %s pointer prohibited\n", 2343 insn->dst_reg, 2344 bpf_alu_string[opcode >> 4]); 2345 return -EACCES; 2346 } else { 2347 /* scalar += pointer 2348 * This is legal, but we have to reverse our 2349 * src/dest handling in computing the range 2350 */ 2351 return adjust_ptr_min_max_vals(env, insn, 2352 src_reg, dst_reg); 2353 } 2354 } else if (ptr_reg) { 2355 /* pointer += scalar */ 2356 return adjust_ptr_min_max_vals(env, insn, 2357 dst_reg, src_reg); 2358 } 2359 } else { 2360 /* Pretend the src is a reg with a known value, since we only 2361 * need to be able to read from this state. 2362 */ 2363 off_reg.type = SCALAR_VALUE; 2364 __mark_reg_known(&off_reg, insn->imm); 2365 src_reg = &off_reg; 2366 if (ptr_reg) /* pointer += K */ 2367 return adjust_ptr_min_max_vals(env, insn, 2368 ptr_reg, src_reg); 2369 } 2370 2371 /* Got here implies adding two SCALAR_VALUEs */ 2372 if (WARN_ON_ONCE(ptr_reg)) { 2373 print_verifier_state(env, env->cur_state); 2374 verbose(env, "verifier internal error: unexpected ptr_reg\n"); 2375 return -EINVAL; 2376 } 2377 if (WARN_ON(!src_reg)) { 2378 print_verifier_state(env, env->cur_state); 2379 verbose(env, "verifier internal error: no src_reg\n"); 2380 return -EINVAL; 2381 } 2382 return adjust_scalar_min_max_vals(env, insn, dst_reg, *src_reg); 2383 } 2384 2385 /* check validity of 32-bit and 64-bit arithmetic operations */ 2386 static int check_alu_op(struct bpf_verifier_env *env, struct bpf_insn *insn) 2387 { 2388 struct bpf_reg_state *regs = cur_regs(env); 2389 u8 opcode = BPF_OP(insn->code); 2390 int err; 2391 2392 if (opcode == BPF_END || opcode == BPF_NEG) { 2393 if (opcode == BPF_NEG) { 2394 if (BPF_SRC(insn->code) != 0 || 2395 insn->src_reg != BPF_REG_0 || 2396 insn->off != 0 || insn->imm != 0) { 2397 verbose(env, "BPF_NEG uses reserved fields\n"); 2398 return -EINVAL; 2399 } 2400 } else { 2401 if (insn->src_reg != BPF_REG_0 || insn->off != 0 || 2402 (insn->imm != 16 && insn->imm != 32 && insn->imm != 64) || 2403 BPF_CLASS(insn->code) == BPF_ALU64) { 2404 verbose(env, "BPF_END uses reserved fields\n"); 2405 return -EINVAL; 2406 } 2407 } 2408 2409 /* check src operand */ 2410 err = check_reg_arg(env, insn->dst_reg, SRC_OP); 2411 if (err) 2412 return err; 2413 2414 if (is_pointer_value(env, insn->dst_reg)) { 2415 verbose(env, "R%d pointer arithmetic prohibited\n", 2416 insn->dst_reg); 2417 return -EACCES; 2418 } 2419 2420 /* check dest operand */ 2421 err = check_reg_arg(env, insn->dst_reg, DST_OP); 2422 if (err) 2423 return err; 2424 2425 } else if (opcode == BPF_MOV) { 2426 2427 if (BPF_SRC(insn->code) == BPF_X) { 2428 if (insn->imm != 0 || insn->off != 0) { 2429 verbose(env, "BPF_MOV uses reserved fields\n"); 2430 return -EINVAL; 2431 } 2432 2433 /* check src operand */ 2434 err = check_reg_arg(env, insn->src_reg, SRC_OP); 2435 if (err) 2436 return err; 2437 } else { 2438 if (insn->src_reg != BPF_REG_0 || insn->off != 0) { 2439 verbose(env, "BPF_MOV uses reserved fields\n"); 2440 return -EINVAL; 2441 } 2442 } 2443 2444 /* check dest operand */ 2445 err = check_reg_arg(env, insn->dst_reg, DST_OP); 2446 if (err) 2447 return err; 2448 2449 if (BPF_SRC(insn->code) == BPF_X) { 2450 if (BPF_CLASS(insn->code) == BPF_ALU64) { 2451 /* case: R1 = R2 2452 * copy register state to dest reg 2453 */ 2454 regs[insn->dst_reg] = regs[insn->src_reg]; 2455 regs[insn->dst_reg].live |= REG_LIVE_WRITTEN; 2456 } else { 2457 /* R1 = (u32) R2 */ 2458 if (is_pointer_value(env, insn->src_reg)) { 2459 verbose(env, 2460 "R%d partial copy of pointer\n", 2461 insn->src_reg); 2462 return -EACCES; 2463 } 2464 mark_reg_unknown(env, regs, insn->dst_reg); 2465 coerce_reg_to_size(®s[insn->dst_reg], 4); 2466 } 2467 } else { 2468 /* case: R = imm 2469 * remember the value we stored into this reg 2470 */ 2471 regs[insn->dst_reg].type = SCALAR_VALUE; 2472 if (BPF_CLASS(insn->code) == BPF_ALU64) { 2473 __mark_reg_known(regs + insn->dst_reg, 2474 insn->imm); 2475 } else { 2476 __mark_reg_known(regs + insn->dst_reg, 2477 (u32)insn->imm); 2478 } 2479 } 2480 2481 } else if (opcode > BPF_END) { 2482 verbose(env, "invalid BPF_ALU opcode %x\n", opcode); 2483 return -EINVAL; 2484 2485 } else { /* all other ALU ops: and, sub, xor, add, ... */ 2486 2487 if (BPF_SRC(insn->code) == BPF_X) { 2488 if (insn->imm != 0 || insn->off != 0) { 2489 verbose(env, "BPF_ALU uses reserved fields\n"); 2490 return -EINVAL; 2491 } 2492 /* check src1 operand */ 2493 err = check_reg_arg(env, insn->src_reg, SRC_OP); 2494 if (err) 2495 return err; 2496 } else { 2497 if (insn->src_reg != BPF_REG_0 || insn->off != 0) { 2498 verbose(env, "BPF_ALU uses reserved fields\n"); 2499 return -EINVAL; 2500 } 2501 } 2502 2503 /* check src2 operand */ 2504 err = check_reg_arg(env, insn->dst_reg, SRC_OP); 2505 if (err) 2506 return err; 2507 2508 if ((opcode == BPF_MOD || opcode == BPF_DIV) && 2509 BPF_SRC(insn->code) == BPF_K && insn->imm == 0) { 2510 verbose(env, "div by zero\n"); 2511 return -EINVAL; 2512 } 2513 2514 if (opcode == BPF_ARSH && BPF_CLASS(insn->code) != BPF_ALU64) { 2515 verbose(env, "BPF_ARSH not supported for 32 bit ALU\n"); 2516 return -EINVAL; 2517 } 2518 2519 if ((opcode == BPF_LSH || opcode == BPF_RSH || 2520 opcode == BPF_ARSH) && BPF_SRC(insn->code) == BPF_K) { 2521 int size = BPF_CLASS(insn->code) == BPF_ALU64 ? 64 : 32; 2522 2523 if (insn->imm < 0 || insn->imm >= size) { 2524 verbose(env, "invalid shift %d\n", insn->imm); 2525 return -EINVAL; 2526 } 2527 } 2528 2529 /* check dest operand */ 2530 err = check_reg_arg(env, insn->dst_reg, DST_OP_NO_MARK); 2531 if (err) 2532 return err; 2533 2534 return adjust_reg_min_max_vals(env, insn); 2535 } 2536 2537 return 0; 2538 } 2539 2540 static void find_good_pkt_pointers(struct bpf_verifier_state *state, 2541 struct bpf_reg_state *dst_reg, 2542 enum bpf_reg_type type, 2543 bool range_right_open) 2544 { 2545 struct bpf_reg_state *regs = state->regs, *reg; 2546 u16 new_range; 2547 int i; 2548 2549 if (dst_reg->off < 0 || 2550 (dst_reg->off == 0 && range_right_open)) 2551 /* This doesn't give us any range */ 2552 return; 2553 2554 if (dst_reg->umax_value > MAX_PACKET_OFF || 2555 dst_reg->umax_value + dst_reg->off > MAX_PACKET_OFF) 2556 /* Risk of overflow. For instance, ptr + (1<<63) may be less 2557 * than pkt_end, but that's because it's also less than pkt. 2558 */ 2559 return; 2560 2561 new_range = dst_reg->off; 2562 if (range_right_open) 2563 new_range--; 2564 2565 /* Examples for register markings: 2566 * 2567 * pkt_data in dst register: 2568 * 2569 * r2 = r3; 2570 * r2 += 8; 2571 * if (r2 > pkt_end) goto <handle exception> 2572 * <access okay> 2573 * 2574 * r2 = r3; 2575 * r2 += 8; 2576 * if (r2 < pkt_end) goto <access okay> 2577 * <handle exception> 2578 * 2579 * Where: 2580 * r2 == dst_reg, pkt_end == src_reg 2581 * r2=pkt(id=n,off=8,r=0) 2582 * r3=pkt(id=n,off=0,r=0) 2583 * 2584 * pkt_data in src register: 2585 * 2586 * r2 = r3; 2587 * r2 += 8; 2588 * if (pkt_end >= r2) goto <access okay> 2589 * <handle exception> 2590 * 2591 * r2 = r3; 2592 * r2 += 8; 2593 * if (pkt_end <= r2) goto <handle exception> 2594 * <access okay> 2595 * 2596 * Where: 2597 * pkt_end == dst_reg, r2 == src_reg 2598 * r2=pkt(id=n,off=8,r=0) 2599 * r3=pkt(id=n,off=0,r=0) 2600 * 2601 * Find register r3 and mark its range as r3=pkt(id=n,off=0,r=8) 2602 * or r3=pkt(id=n,off=0,r=8-1), so that range of bytes [r3, r3 + 8) 2603 * and [r3, r3 + 8-1) respectively is safe to access depending on 2604 * the check. 2605 */ 2606 2607 /* If our ids match, then we must have the same max_value. And we 2608 * don't care about the other reg's fixed offset, since if it's too big 2609 * the range won't allow anything. 2610 * dst_reg->off is known < MAX_PACKET_OFF, therefore it fits in a u16. 2611 */ 2612 for (i = 0; i < MAX_BPF_REG; i++) 2613 if (regs[i].type == type && regs[i].id == dst_reg->id) 2614 /* keep the maximum range already checked */ 2615 regs[i].range = max(regs[i].range, new_range); 2616 2617 for (i = 0; i < state->allocated_stack / BPF_REG_SIZE; i++) { 2618 if (state->stack[i].slot_type[0] != STACK_SPILL) 2619 continue; 2620 reg = &state->stack[i].spilled_ptr; 2621 if (reg->type == type && reg->id == dst_reg->id) 2622 reg->range = max(reg->range, new_range); 2623 } 2624 } 2625 2626 /* Adjusts the register min/max values in the case that the dst_reg is the 2627 * variable register that we are working on, and src_reg is a constant or we're 2628 * simply doing a BPF_K check. 2629 * In JEQ/JNE cases we also adjust the var_off values. 2630 */ 2631 static void reg_set_min_max(struct bpf_reg_state *true_reg, 2632 struct bpf_reg_state *false_reg, u64 val, 2633 u8 opcode) 2634 { 2635 /* If the dst_reg is a pointer, we can't learn anything about its 2636 * variable offset from the compare (unless src_reg were a pointer into 2637 * the same object, but we don't bother with that. 2638 * Since false_reg and true_reg have the same type by construction, we 2639 * only need to check one of them for pointerness. 2640 */ 2641 if (__is_pointer_value(false, false_reg)) 2642 return; 2643 2644 switch (opcode) { 2645 case BPF_JEQ: 2646 /* If this is false then we know nothing Jon Snow, but if it is 2647 * true then we know for sure. 2648 */ 2649 __mark_reg_known(true_reg, val); 2650 break; 2651 case BPF_JNE: 2652 /* If this is true we know nothing Jon Snow, but if it is false 2653 * we know the value for sure; 2654 */ 2655 __mark_reg_known(false_reg, val); 2656 break; 2657 case BPF_JGT: 2658 false_reg->umax_value = min(false_reg->umax_value, val); 2659 true_reg->umin_value = max(true_reg->umin_value, val + 1); 2660 break; 2661 case BPF_JSGT: 2662 false_reg->smax_value = min_t(s64, false_reg->smax_value, val); 2663 true_reg->smin_value = max_t(s64, true_reg->smin_value, val + 1); 2664 break; 2665 case BPF_JLT: 2666 false_reg->umin_value = max(false_reg->umin_value, val); 2667 true_reg->umax_value = min(true_reg->umax_value, val - 1); 2668 break; 2669 case BPF_JSLT: 2670 false_reg->smin_value = max_t(s64, false_reg->smin_value, val); 2671 true_reg->smax_value = min_t(s64, true_reg->smax_value, val - 1); 2672 break; 2673 case BPF_JGE: 2674 false_reg->umax_value = min(false_reg->umax_value, val - 1); 2675 true_reg->umin_value = max(true_reg->umin_value, val); 2676 break; 2677 case BPF_JSGE: 2678 false_reg->smax_value = min_t(s64, false_reg->smax_value, val - 1); 2679 true_reg->smin_value = max_t(s64, true_reg->smin_value, val); 2680 break; 2681 case BPF_JLE: 2682 false_reg->umin_value = max(false_reg->umin_value, val + 1); 2683 true_reg->umax_value = min(true_reg->umax_value, val); 2684 break; 2685 case BPF_JSLE: 2686 false_reg->smin_value = max_t(s64, false_reg->smin_value, val + 1); 2687 true_reg->smax_value = min_t(s64, true_reg->smax_value, val); 2688 break; 2689 default: 2690 break; 2691 } 2692 2693 __reg_deduce_bounds(false_reg); 2694 __reg_deduce_bounds(true_reg); 2695 /* We might have learned some bits from the bounds. */ 2696 __reg_bound_offset(false_reg); 2697 __reg_bound_offset(true_reg); 2698 /* Intersecting with the old var_off might have improved our bounds 2699 * slightly. e.g. if umax was 0x7f...f and var_off was (0; 0xf...fc), 2700 * then new var_off is (0; 0x7f...fc) which improves our umax. 2701 */ 2702 __update_reg_bounds(false_reg); 2703 __update_reg_bounds(true_reg); 2704 } 2705 2706 /* Same as above, but for the case that dst_reg holds a constant and src_reg is 2707 * the variable reg. 2708 */ 2709 static void reg_set_min_max_inv(struct bpf_reg_state *true_reg, 2710 struct bpf_reg_state *false_reg, u64 val, 2711 u8 opcode) 2712 { 2713 if (__is_pointer_value(false, false_reg)) 2714 return; 2715 2716 switch (opcode) { 2717 case BPF_JEQ: 2718 /* If this is false then we know nothing Jon Snow, but if it is 2719 * true then we know for sure. 2720 */ 2721 __mark_reg_known(true_reg, val); 2722 break; 2723 case BPF_JNE: 2724 /* If this is true we know nothing Jon Snow, but if it is false 2725 * we know the value for sure; 2726 */ 2727 __mark_reg_known(false_reg, val); 2728 break; 2729 case BPF_JGT: 2730 true_reg->umax_value = min(true_reg->umax_value, val - 1); 2731 false_reg->umin_value = max(false_reg->umin_value, val); 2732 break; 2733 case BPF_JSGT: 2734 true_reg->smax_value = min_t(s64, true_reg->smax_value, val - 1); 2735 false_reg->smin_value = max_t(s64, false_reg->smin_value, val); 2736 break; 2737 case BPF_JLT: 2738 true_reg->umin_value = max(true_reg->umin_value, val + 1); 2739 false_reg->umax_value = min(false_reg->umax_value, val); 2740 break; 2741 case BPF_JSLT: 2742 true_reg->smin_value = max_t(s64, true_reg->smin_value, val + 1); 2743 false_reg->smax_value = min_t(s64, false_reg->smax_value, val); 2744 break; 2745 case BPF_JGE: 2746 true_reg->umax_value = min(true_reg->umax_value, val); 2747 false_reg->umin_value = max(false_reg->umin_value, val + 1); 2748 break; 2749 case BPF_JSGE: 2750 true_reg->smax_value = min_t(s64, true_reg->smax_value, val); 2751 false_reg->smin_value = max_t(s64, false_reg->smin_value, val + 1); 2752 break; 2753 case BPF_JLE: 2754 true_reg->umin_value = max(true_reg->umin_value, val); 2755 false_reg->umax_value = min(false_reg->umax_value, val - 1); 2756 break; 2757 case BPF_JSLE: 2758 true_reg->smin_value = max_t(s64, true_reg->smin_value, val); 2759 false_reg->smax_value = min_t(s64, false_reg->smax_value, val - 1); 2760 break; 2761 default: 2762 break; 2763 } 2764 2765 __reg_deduce_bounds(false_reg); 2766 __reg_deduce_bounds(true_reg); 2767 /* We might have learned some bits from the bounds. */ 2768 __reg_bound_offset(false_reg); 2769 __reg_bound_offset(true_reg); 2770 /* Intersecting with the old var_off might have improved our bounds 2771 * slightly. e.g. if umax was 0x7f...f and var_off was (0; 0xf...fc), 2772 * then new var_off is (0; 0x7f...fc) which improves our umax. 2773 */ 2774 __update_reg_bounds(false_reg); 2775 __update_reg_bounds(true_reg); 2776 } 2777 2778 /* Regs are known to be equal, so intersect their min/max/var_off */ 2779 static void __reg_combine_min_max(struct bpf_reg_state *src_reg, 2780 struct bpf_reg_state *dst_reg) 2781 { 2782 src_reg->umin_value = dst_reg->umin_value = max(src_reg->umin_value, 2783 dst_reg->umin_value); 2784 src_reg->umax_value = dst_reg->umax_value = min(src_reg->umax_value, 2785 dst_reg->umax_value); 2786 src_reg->smin_value = dst_reg->smin_value = max(src_reg->smin_value, 2787 dst_reg->smin_value); 2788 src_reg->smax_value = dst_reg->smax_value = min(src_reg->smax_value, 2789 dst_reg->smax_value); 2790 src_reg->var_off = dst_reg->var_off = tnum_intersect(src_reg->var_off, 2791 dst_reg->var_off); 2792 /* We might have learned new bounds from the var_off. */ 2793 __update_reg_bounds(src_reg); 2794 __update_reg_bounds(dst_reg); 2795 /* We might have learned something about the sign bit. */ 2796 __reg_deduce_bounds(src_reg); 2797 __reg_deduce_bounds(dst_reg); 2798 /* We might have learned some bits from the bounds. */ 2799 __reg_bound_offset(src_reg); 2800 __reg_bound_offset(dst_reg); 2801 /* Intersecting with the old var_off might have improved our bounds 2802 * slightly. e.g. if umax was 0x7f...f and var_off was (0; 0xf...fc), 2803 * then new var_off is (0; 0x7f...fc) which improves our umax. 2804 */ 2805 __update_reg_bounds(src_reg); 2806 __update_reg_bounds(dst_reg); 2807 } 2808 2809 static void reg_combine_min_max(struct bpf_reg_state *true_src, 2810 struct bpf_reg_state *true_dst, 2811 struct bpf_reg_state *false_src, 2812 struct bpf_reg_state *false_dst, 2813 u8 opcode) 2814 { 2815 switch (opcode) { 2816 case BPF_JEQ: 2817 __reg_combine_min_max(true_src, true_dst); 2818 break; 2819 case BPF_JNE: 2820 __reg_combine_min_max(false_src, false_dst); 2821 break; 2822 } 2823 } 2824 2825 static void mark_map_reg(struct bpf_reg_state *regs, u32 regno, u32 id, 2826 bool is_null) 2827 { 2828 struct bpf_reg_state *reg = ®s[regno]; 2829 2830 if (reg->type == PTR_TO_MAP_VALUE_OR_NULL && reg->id == id) { 2831 /* Old offset (both fixed and variable parts) should 2832 * have been known-zero, because we don't allow pointer 2833 * arithmetic on pointers that might be NULL. 2834 */ 2835 if (WARN_ON_ONCE(reg->smin_value || reg->smax_value || 2836 !tnum_equals_const(reg->var_off, 0) || 2837 reg->off)) { 2838 __mark_reg_known_zero(reg); 2839 reg->off = 0; 2840 } 2841 if (is_null) { 2842 reg->type = SCALAR_VALUE; 2843 } else if (reg->map_ptr->inner_map_meta) { 2844 reg->type = CONST_PTR_TO_MAP; 2845 reg->map_ptr = reg->map_ptr->inner_map_meta; 2846 } else { 2847 reg->type = PTR_TO_MAP_VALUE; 2848 } 2849 /* We don't need id from this point onwards anymore, thus we 2850 * should better reset it, so that state pruning has chances 2851 * to take effect. 2852 */ 2853 reg->id = 0; 2854 } 2855 } 2856 2857 /* The logic is similar to find_good_pkt_pointers(), both could eventually 2858 * be folded together at some point. 2859 */ 2860 static void mark_map_regs(struct bpf_verifier_state *state, u32 regno, 2861 bool is_null) 2862 { 2863 struct bpf_reg_state *regs = state->regs; 2864 u32 id = regs[regno].id; 2865 int i; 2866 2867 for (i = 0; i < MAX_BPF_REG; i++) 2868 mark_map_reg(regs, i, id, is_null); 2869 2870 for (i = 0; i < state->allocated_stack / BPF_REG_SIZE; i++) { 2871 if (state->stack[i].slot_type[0] != STACK_SPILL) 2872 continue; 2873 mark_map_reg(&state->stack[i].spilled_ptr, 0, id, is_null); 2874 } 2875 } 2876 2877 static bool try_match_pkt_pointers(const struct bpf_insn *insn, 2878 struct bpf_reg_state *dst_reg, 2879 struct bpf_reg_state *src_reg, 2880 struct bpf_verifier_state *this_branch, 2881 struct bpf_verifier_state *other_branch) 2882 { 2883 if (BPF_SRC(insn->code) != BPF_X) 2884 return false; 2885 2886 switch (BPF_OP(insn->code)) { 2887 case BPF_JGT: 2888 if ((dst_reg->type == PTR_TO_PACKET && 2889 src_reg->type == PTR_TO_PACKET_END) || 2890 (dst_reg->type == PTR_TO_PACKET_META && 2891 reg_is_init_pkt_pointer(src_reg, PTR_TO_PACKET))) { 2892 /* pkt_data' > pkt_end, pkt_meta' > pkt_data */ 2893 find_good_pkt_pointers(this_branch, dst_reg, 2894 dst_reg->type, false); 2895 } else if ((dst_reg->type == PTR_TO_PACKET_END && 2896 src_reg->type == PTR_TO_PACKET) || 2897 (reg_is_init_pkt_pointer(dst_reg, PTR_TO_PACKET) && 2898 src_reg->type == PTR_TO_PACKET_META)) { 2899 /* pkt_end > pkt_data', pkt_data > pkt_meta' */ 2900 find_good_pkt_pointers(other_branch, src_reg, 2901 src_reg->type, true); 2902 } else { 2903 return false; 2904 } 2905 break; 2906 case BPF_JLT: 2907 if ((dst_reg->type == PTR_TO_PACKET && 2908 src_reg->type == PTR_TO_PACKET_END) || 2909 (dst_reg->type == PTR_TO_PACKET_META && 2910 reg_is_init_pkt_pointer(src_reg, PTR_TO_PACKET))) { 2911 /* pkt_data' < pkt_end, pkt_meta' < pkt_data */ 2912 find_good_pkt_pointers(other_branch, dst_reg, 2913 dst_reg->type, true); 2914 } else if ((dst_reg->type == PTR_TO_PACKET_END && 2915 src_reg->type == PTR_TO_PACKET) || 2916 (reg_is_init_pkt_pointer(dst_reg, PTR_TO_PACKET) && 2917 src_reg->type == PTR_TO_PACKET_META)) { 2918 /* pkt_end < pkt_data', pkt_data > pkt_meta' */ 2919 find_good_pkt_pointers(this_branch, src_reg, 2920 src_reg->type, false); 2921 } else { 2922 return false; 2923 } 2924 break; 2925 case BPF_JGE: 2926 if ((dst_reg->type == PTR_TO_PACKET && 2927 src_reg->type == PTR_TO_PACKET_END) || 2928 (dst_reg->type == PTR_TO_PACKET_META && 2929 reg_is_init_pkt_pointer(src_reg, PTR_TO_PACKET))) { 2930 /* pkt_data' >= pkt_end, pkt_meta' >= pkt_data */ 2931 find_good_pkt_pointers(this_branch, dst_reg, 2932 dst_reg->type, true); 2933 } else if ((dst_reg->type == PTR_TO_PACKET_END && 2934 src_reg->type == PTR_TO_PACKET) || 2935 (reg_is_init_pkt_pointer(dst_reg, PTR_TO_PACKET) && 2936 src_reg->type == PTR_TO_PACKET_META)) { 2937 /* pkt_end >= pkt_data', pkt_data >= pkt_meta' */ 2938 find_good_pkt_pointers(other_branch, src_reg, 2939 src_reg->type, false); 2940 } else { 2941 return false; 2942 } 2943 break; 2944 case BPF_JLE: 2945 if ((dst_reg->type == PTR_TO_PACKET && 2946 src_reg->type == PTR_TO_PACKET_END) || 2947 (dst_reg->type == PTR_TO_PACKET_META && 2948 reg_is_init_pkt_pointer(src_reg, PTR_TO_PACKET))) { 2949 /* pkt_data' <= pkt_end, pkt_meta' <= pkt_data */ 2950 find_good_pkt_pointers(other_branch, dst_reg, 2951 dst_reg->type, false); 2952 } else if ((dst_reg->type == PTR_TO_PACKET_END && 2953 src_reg->type == PTR_TO_PACKET) || 2954 (reg_is_init_pkt_pointer(dst_reg, PTR_TO_PACKET) && 2955 src_reg->type == PTR_TO_PACKET_META)) { 2956 /* pkt_end <= pkt_data', pkt_data <= pkt_meta' */ 2957 find_good_pkt_pointers(this_branch, src_reg, 2958 src_reg->type, true); 2959 } else { 2960 return false; 2961 } 2962 break; 2963 default: 2964 return false; 2965 } 2966 2967 return true; 2968 } 2969 2970 static int check_cond_jmp_op(struct bpf_verifier_env *env, 2971 struct bpf_insn *insn, int *insn_idx) 2972 { 2973 struct bpf_verifier_state *other_branch, *this_branch = env->cur_state; 2974 struct bpf_reg_state *regs = this_branch->regs, *dst_reg; 2975 u8 opcode = BPF_OP(insn->code); 2976 int err; 2977 2978 if (opcode > BPF_JSLE) { 2979 verbose(env, "invalid BPF_JMP opcode %x\n", opcode); 2980 return -EINVAL; 2981 } 2982 2983 if (BPF_SRC(insn->code) == BPF_X) { 2984 if (insn->imm != 0) { 2985 verbose(env, "BPF_JMP uses reserved fields\n"); 2986 return -EINVAL; 2987 } 2988 2989 /* check src1 operand */ 2990 err = check_reg_arg(env, insn->src_reg, SRC_OP); 2991 if (err) 2992 return err; 2993 2994 if (is_pointer_value(env, insn->src_reg)) { 2995 verbose(env, "R%d pointer comparison prohibited\n", 2996 insn->src_reg); 2997 return -EACCES; 2998 } 2999 } else { 3000 if (insn->src_reg != BPF_REG_0) { 3001 verbose(env, "BPF_JMP uses reserved fields\n"); 3002 return -EINVAL; 3003 } 3004 } 3005 3006 /* check src2 operand */ 3007 err = check_reg_arg(env, insn->dst_reg, SRC_OP); 3008 if (err) 3009 return err; 3010 3011 dst_reg = ®s[insn->dst_reg]; 3012 3013 /* detect if R == 0 where R was initialized to zero earlier */ 3014 if (BPF_SRC(insn->code) == BPF_K && 3015 (opcode == BPF_JEQ || opcode == BPF_JNE) && 3016 dst_reg->type == SCALAR_VALUE && 3017 tnum_equals_const(dst_reg->var_off, insn->imm)) { 3018 if (opcode == BPF_JEQ) { 3019 /* if (imm == imm) goto pc+off; 3020 * only follow the goto, ignore fall-through 3021 */ 3022 *insn_idx += insn->off; 3023 return 0; 3024 } else { 3025 /* if (imm != imm) goto pc+off; 3026 * only follow fall-through branch, since 3027 * that's where the program will go 3028 */ 3029 return 0; 3030 } 3031 } 3032 3033 other_branch = push_stack(env, *insn_idx + insn->off + 1, *insn_idx); 3034 if (!other_branch) 3035 return -EFAULT; 3036 3037 /* detect if we are comparing against a constant value so we can adjust 3038 * our min/max values for our dst register. 3039 * this is only legit if both are scalars (or pointers to the same 3040 * object, I suppose, but we don't support that right now), because 3041 * otherwise the different base pointers mean the offsets aren't 3042 * comparable. 3043 */ 3044 if (BPF_SRC(insn->code) == BPF_X) { 3045 if (dst_reg->type == SCALAR_VALUE && 3046 regs[insn->src_reg].type == SCALAR_VALUE) { 3047 if (tnum_is_const(regs[insn->src_reg].var_off)) 3048 reg_set_min_max(&other_branch->regs[insn->dst_reg], 3049 dst_reg, regs[insn->src_reg].var_off.value, 3050 opcode); 3051 else if (tnum_is_const(dst_reg->var_off)) 3052 reg_set_min_max_inv(&other_branch->regs[insn->src_reg], 3053 ®s[insn->src_reg], 3054 dst_reg->var_off.value, opcode); 3055 else if (opcode == BPF_JEQ || opcode == BPF_JNE) 3056 /* Comparing for equality, we can combine knowledge */ 3057 reg_combine_min_max(&other_branch->regs[insn->src_reg], 3058 &other_branch->regs[insn->dst_reg], 3059 ®s[insn->src_reg], 3060 ®s[insn->dst_reg], opcode); 3061 } 3062 } else if (dst_reg->type == SCALAR_VALUE) { 3063 reg_set_min_max(&other_branch->regs[insn->dst_reg], 3064 dst_reg, insn->imm, opcode); 3065 } 3066 3067 /* detect if R == 0 where R is returned from bpf_map_lookup_elem() */ 3068 if (BPF_SRC(insn->code) == BPF_K && 3069 insn->imm == 0 && (opcode == BPF_JEQ || opcode == BPF_JNE) && 3070 dst_reg->type == PTR_TO_MAP_VALUE_OR_NULL) { 3071 /* Mark all identical map registers in each branch as either 3072 * safe or unknown depending R == 0 or R != 0 conditional. 3073 */ 3074 mark_map_regs(this_branch, insn->dst_reg, opcode == BPF_JNE); 3075 mark_map_regs(other_branch, insn->dst_reg, opcode == BPF_JEQ); 3076 } else if (!try_match_pkt_pointers(insn, dst_reg, ®s[insn->src_reg], 3077 this_branch, other_branch) && 3078 is_pointer_value(env, insn->dst_reg)) { 3079 verbose(env, "R%d pointer comparison prohibited\n", 3080 insn->dst_reg); 3081 return -EACCES; 3082 } 3083 if (env->log.level) 3084 print_verifier_state(env, this_branch); 3085 return 0; 3086 } 3087 3088 /* return the map pointer stored inside BPF_LD_IMM64 instruction */ 3089 static struct bpf_map *ld_imm64_to_map_ptr(struct bpf_insn *insn) 3090 { 3091 u64 imm64 = ((u64) (u32) insn[0].imm) | ((u64) (u32) insn[1].imm) << 32; 3092 3093 return (struct bpf_map *) (unsigned long) imm64; 3094 } 3095 3096 /* verify BPF_LD_IMM64 instruction */ 3097 static int check_ld_imm(struct bpf_verifier_env *env, struct bpf_insn *insn) 3098 { 3099 struct bpf_reg_state *regs = cur_regs(env); 3100 int err; 3101 3102 if (BPF_SIZE(insn->code) != BPF_DW) { 3103 verbose(env, "invalid BPF_LD_IMM insn\n"); 3104 return -EINVAL; 3105 } 3106 if (insn->off != 0) { 3107 verbose(env, "BPF_LD_IMM64 uses reserved fields\n"); 3108 return -EINVAL; 3109 } 3110 3111 err = check_reg_arg(env, insn->dst_reg, DST_OP); 3112 if (err) 3113 return err; 3114 3115 if (insn->src_reg == 0) { 3116 u64 imm = ((u64)(insn + 1)->imm << 32) | (u32)insn->imm; 3117 3118 regs[insn->dst_reg].type = SCALAR_VALUE; 3119 __mark_reg_known(®s[insn->dst_reg], imm); 3120 return 0; 3121 } 3122 3123 /* replace_map_fd_with_map_ptr() should have caught bad ld_imm64 */ 3124 BUG_ON(insn->src_reg != BPF_PSEUDO_MAP_FD); 3125 3126 regs[insn->dst_reg].type = CONST_PTR_TO_MAP; 3127 regs[insn->dst_reg].map_ptr = ld_imm64_to_map_ptr(insn); 3128 return 0; 3129 } 3130 3131 static bool may_access_skb(enum bpf_prog_type type) 3132 { 3133 switch (type) { 3134 case BPF_PROG_TYPE_SOCKET_FILTER: 3135 case BPF_PROG_TYPE_SCHED_CLS: 3136 case BPF_PROG_TYPE_SCHED_ACT: 3137 return true; 3138 default: 3139 return false; 3140 } 3141 } 3142 3143 /* verify safety of LD_ABS|LD_IND instructions: 3144 * - they can only appear in the programs where ctx == skb 3145 * - since they are wrappers of function calls, they scratch R1-R5 registers, 3146 * preserve R6-R9, and store return value into R0 3147 * 3148 * Implicit input: 3149 * ctx == skb == R6 == CTX 3150 * 3151 * Explicit input: 3152 * SRC == any register 3153 * IMM == 32-bit immediate 3154 * 3155 * Output: 3156 * R0 - 8/16/32-bit skb data converted to cpu endianness 3157 */ 3158 static int check_ld_abs(struct bpf_verifier_env *env, struct bpf_insn *insn) 3159 { 3160 struct bpf_reg_state *regs = cur_regs(env); 3161 u8 mode = BPF_MODE(insn->code); 3162 int i, err; 3163 3164 if (!may_access_skb(env->prog->type)) { 3165 verbose(env, "BPF_LD_[ABS|IND] instructions not allowed for this program type\n"); 3166 return -EINVAL; 3167 } 3168 3169 if (insn->dst_reg != BPF_REG_0 || insn->off != 0 || 3170 BPF_SIZE(insn->code) == BPF_DW || 3171 (mode == BPF_ABS && insn->src_reg != BPF_REG_0)) { 3172 verbose(env, "BPF_LD_[ABS|IND] uses reserved fields\n"); 3173 return -EINVAL; 3174 } 3175 3176 /* check whether implicit source operand (register R6) is readable */ 3177 err = check_reg_arg(env, BPF_REG_6, SRC_OP); 3178 if (err) 3179 return err; 3180 3181 if (regs[BPF_REG_6].type != PTR_TO_CTX) { 3182 verbose(env, 3183 "at the time of BPF_LD_ABS|IND R6 != pointer to skb\n"); 3184 return -EINVAL; 3185 } 3186 3187 if (mode == BPF_IND) { 3188 /* check explicit source operand */ 3189 err = check_reg_arg(env, insn->src_reg, SRC_OP); 3190 if (err) 3191 return err; 3192 } 3193 3194 /* reset caller saved regs to unreadable */ 3195 for (i = 0; i < CALLER_SAVED_REGS; i++) { 3196 mark_reg_not_init(env, regs, caller_saved[i]); 3197 check_reg_arg(env, caller_saved[i], DST_OP_NO_MARK); 3198 } 3199 3200 /* mark destination R0 register as readable, since it contains 3201 * the value fetched from the packet. 3202 * Already marked as written above. 3203 */ 3204 mark_reg_unknown(env, regs, BPF_REG_0); 3205 return 0; 3206 } 3207 3208 static int check_return_code(struct bpf_verifier_env *env) 3209 { 3210 struct bpf_reg_state *reg; 3211 struct tnum range = tnum_range(0, 1); 3212 3213 switch (env->prog->type) { 3214 case BPF_PROG_TYPE_CGROUP_SKB: 3215 case BPF_PROG_TYPE_CGROUP_SOCK: 3216 case BPF_PROG_TYPE_SOCK_OPS: 3217 case BPF_PROG_TYPE_CGROUP_DEVICE: 3218 break; 3219 default: 3220 return 0; 3221 } 3222 3223 reg = cur_regs(env) + BPF_REG_0; 3224 if (reg->type != SCALAR_VALUE) { 3225 verbose(env, "At program exit the register R0 is not a known value (%s)\n", 3226 reg_type_str[reg->type]); 3227 return -EINVAL; 3228 } 3229 3230 if (!tnum_in(range, reg->var_off)) { 3231 verbose(env, "At program exit the register R0 "); 3232 if (!tnum_is_unknown(reg->var_off)) { 3233 char tn_buf[48]; 3234 3235 tnum_strn(tn_buf, sizeof(tn_buf), reg->var_off); 3236 verbose(env, "has value %s", tn_buf); 3237 } else { 3238 verbose(env, "has unknown scalar value"); 3239 } 3240 verbose(env, " should have been 0 or 1\n"); 3241 return -EINVAL; 3242 } 3243 return 0; 3244 } 3245 3246 /* non-recursive DFS pseudo code 3247 * 1 procedure DFS-iterative(G,v): 3248 * 2 label v as discovered 3249 * 3 let S be a stack 3250 * 4 S.push(v) 3251 * 5 while S is not empty 3252 * 6 t <- S.pop() 3253 * 7 if t is what we're looking for: 3254 * 8 return t 3255 * 9 for all edges e in G.adjacentEdges(t) do 3256 * 10 if edge e is already labelled 3257 * 11 continue with the next edge 3258 * 12 w <- G.adjacentVertex(t,e) 3259 * 13 if vertex w is not discovered and not explored 3260 * 14 label e as tree-edge 3261 * 15 label w as discovered 3262 * 16 S.push(w) 3263 * 17 continue at 5 3264 * 18 else if vertex w is discovered 3265 * 19 label e as back-edge 3266 * 20 else 3267 * 21 // vertex w is explored 3268 * 22 label e as forward- or cross-edge 3269 * 23 label t as explored 3270 * 24 S.pop() 3271 * 3272 * convention: 3273 * 0x10 - discovered 3274 * 0x11 - discovered and fall-through edge labelled 3275 * 0x12 - discovered and fall-through and branch edges labelled 3276 * 0x20 - explored 3277 */ 3278 3279 enum { 3280 DISCOVERED = 0x10, 3281 EXPLORED = 0x20, 3282 FALLTHROUGH = 1, 3283 BRANCH = 2, 3284 }; 3285 3286 #define STATE_LIST_MARK ((struct bpf_verifier_state_list *) -1L) 3287 3288 static int *insn_stack; /* stack of insns to process */ 3289 static int cur_stack; /* current stack index */ 3290 static int *insn_state; 3291 3292 /* t, w, e - match pseudo-code above: 3293 * t - index of current instruction 3294 * w - next instruction 3295 * e - edge 3296 */ 3297 static int push_insn(int t, int w, int e, struct bpf_verifier_env *env) 3298 { 3299 if (e == FALLTHROUGH && insn_state[t] >= (DISCOVERED | FALLTHROUGH)) 3300 return 0; 3301 3302 if (e == BRANCH && insn_state[t] >= (DISCOVERED | BRANCH)) 3303 return 0; 3304 3305 if (w < 0 || w >= env->prog->len) { 3306 verbose(env, "jump out of range from insn %d to %d\n", t, w); 3307 return -EINVAL; 3308 } 3309 3310 if (e == BRANCH) 3311 /* mark branch target for state pruning */ 3312 env->explored_states[w] = STATE_LIST_MARK; 3313 3314 if (insn_state[w] == 0) { 3315 /* tree-edge */ 3316 insn_state[t] = DISCOVERED | e; 3317 insn_state[w] = DISCOVERED; 3318 if (cur_stack >= env->prog->len) 3319 return -E2BIG; 3320 insn_stack[cur_stack++] = w; 3321 return 1; 3322 } else if ((insn_state[w] & 0xF0) == DISCOVERED) { 3323 verbose(env, "back-edge from insn %d to %d\n", t, w); 3324 return -EINVAL; 3325 } else if (insn_state[w] == EXPLORED) { 3326 /* forward- or cross-edge */ 3327 insn_state[t] = DISCOVERED | e; 3328 } else { 3329 verbose(env, "insn state internal bug\n"); 3330 return -EFAULT; 3331 } 3332 return 0; 3333 } 3334 3335 /* non-recursive depth-first-search to detect loops in BPF program 3336 * loop == back-edge in directed graph 3337 */ 3338 static int check_cfg(struct bpf_verifier_env *env) 3339 { 3340 struct bpf_insn *insns = env->prog->insnsi; 3341 int insn_cnt = env->prog->len; 3342 int ret = 0; 3343 int i, t; 3344 3345 insn_state = kcalloc(insn_cnt, sizeof(int), GFP_KERNEL); 3346 if (!insn_state) 3347 return -ENOMEM; 3348 3349 insn_stack = kcalloc(insn_cnt, sizeof(int), GFP_KERNEL); 3350 if (!insn_stack) { 3351 kfree(insn_state); 3352 return -ENOMEM; 3353 } 3354 3355 insn_state[0] = DISCOVERED; /* mark 1st insn as discovered */ 3356 insn_stack[0] = 0; /* 0 is the first instruction */ 3357 cur_stack = 1; 3358 3359 peek_stack: 3360 if (cur_stack == 0) 3361 goto check_state; 3362 t = insn_stack[cur_stack - 1]; 3363 3364 if (BPF_CLASS(insns[t].code) == BPF_JMP) { 3365 u8 opcode = BPF_OP(insns[t].code); 3366 3367 if (opcode == BPF_EXIT) { 3368 goto mark_explored; 3369 } else if (opcode == BPF_CALL) { 3370 ret = push_insn(t, t + 1, FALLTHROUGH, env); 3371 if (ret == 1) 3372 goto peek_stack; 3373 else if (ret < 0) 3374 goto err_free; 3375 if (t + 1 < insn_cnt) 3376 env->explored_states[t + 1] = STATE_LIST_MARK; 3377 } else if (opcode == BPF_JA) { 3378 if (BPF_SRC(insns[t].code) != BPF_K) { 3379 ret = -EINVAL; 3380 goto err_free; 3381 } 3382 /* unconditional jump with single edge */ 3383 ret = push_insn(t, t + insns[t].off + 1, 3384 FALLTHROUGH, env); 3385 if (ret == 1) 3386 goto peek_stack; 3387 else if (ret < 0) 3388 goto err_free; 3389 /* tell verifier to check for equivalent states 3390 * after every call and jump 3391 */ 3392 if (t + 1 < insn_cnt) 3393 env->explored_states[t + 1] = STATE_LIST_MARK; 3394 } else { 3395 /* conditional jump with two edges */ 3396 env->explored_states[t] = STATE_LIST_MARK; 3397 ret = push_insn(t, t + 1, FALLTHROUGH, env); 3398 if (ret == 1) 3399 goto peek_stack; 3400 else if (ret < 0) 3401 goto err_free; 3402 3403 ret = push_insn(t, t + insns[t].off + 1, BRANCH, env); 3404 if (ret == 1) 3405 goto peek_stack; 3406 else if (ret < 0) 3407 goto err_free; 3408 } 3409 } else { 3410 /* all other non-branch instructions with single 3411 * fall-through edge 3412 */ 3413 ret = push_insn(t, t + 1, FALLTHROUGH, env); 3414 if (ret == 1) 3415 goto peek_stack; 3416 else if (ret < 0) 3417 goto err_free; 3418 } 3419 3420 mark_explored: 3421 insn_state[t] = EXPLORED; 3422 if (cur_stack-- <= 0) { 3423 verbose(env, "pop stack internal bug\n"); 3424 ret = -EFAULT; 3425 goto err_free; 3426 } 3427 goto peek_stack; 3428 3429 check_state: 3430 for (i = 0; i < insn_cnt; i++) { 3431 if (insn_state[i] != EXPLORED) { 3432 verbose(env, "unreachable insn %d\n", i); 3433 ret = -EINVAL; 3434 goto err_free; 3435 } 3436 } 3437 ret = 0; /* cfg looks good */ 3438 3439 err_free: 3440 kfree(insn_state); 3441 kfree(insn_stack); 3442 return ret; 3443 } 3444 3445 /* check %cur's range satisfies %old's */ 3446 static bool range_within(struct bpf_reg_state *old, 3447 struct bpf_reg_state *cur) 3448 { 3449 return old->umin_value <= cur->umin_value && 3450 old->umax_value >= cur->umax_value && 3451 old->smin_value <= cur->smin_value && 3452 old->smax_value >= cur->smax_value; 3453 } 3454 3455 /* Maximum number of register states that can exist at once */ 3456 #define ID_MAP_SIZE (MAX_BPF_REG + MAX_BPF_STACK / BPF_REG_SIZE) 3457 struct idpair { 3458 u32 old; 3459 u32 cur; 3460 }; 3461 3462 /* If in the old state two registers had the same id, then they need to have 3463 * the same id in the new state as well. But that id could be different from 3464 * the old state, so we need to track the mapping from old to new ids. 3465 * Once we have seen that, say, a reg with old id 5 had new id 9, any subsequent 3466 * regs with old id 5 must also have new id 9 for the new state to be safe. But 3467 * regs with a different old id could still have new id 9, we don't care about 3468 * that. 3469 * So we look through our idmap to see if this old id has been seen before. If 3470 * so, we require the new id to match; otherwise, we add the id pair to the map. 3471 */ 3472 static bool check_ids(u32 old_id, u32 cur_id, struct idpair *idmap) 3473 { 3474 unsigned int i; 3475 3476 for (i = 0; i < ID_MAP_SIZE; i++) { 3477 if (!idmap[i].old) { 3478 /* Reached an empty slot; haven't seen this id before */ 3479 idmap[i].old = old_id; 3480 idmap[i].cur = cur_id; 3481 return true; 3482 } 3483 if (idmap[i].old == old_id) 3484 return idmap[i].cur == cur_id; 3485 } 3486 /* We ran out of idmap slots, which should be impossible */ 3487 WARN_ON_ONCE(1); 3488 return false; 3489 } 3490 3491 /* Returns true if (rold safe implies rcur safe) */ 3492 static bool regsafe(struct bpf_reg_state *rold, struct bpf_reg_state *rcur, 3493 struct idpair *idmap) 3494 { 3495 if (!(rold->live & REG_LIVE_READ)) 3496 /* explored state didn't use this */ 3497 return true; 3498 3499 if (memcmp(rold, rcur, offsetof(struct bpf_reg_state, live)) == 0) 3500 return true; 3501 3502 if (rold->type == NOT_INIT) 3503 /* explored state can't have used this */ 3504 return true; 3505 if (rcur->type == NOT_INIT) 3506 return false; 3507 switch (rold->type) { 3508 case SCALAR_VALUE: 3509 if (rcur->type == SCALAR_VALUE) { 3510 /* new val must satisfy old val knowledge */ 3511 return range_within(rold, rcur) && 3512 tnum_in(rold->var_off, rcur->var_off); 3513 } else { 3514 /* We're trying to use a pointer in place of a scalar. 3515 * Even if the scalar was unbounded, this could lead to 3516 * pointer leaks because scalars are allowed to leak 3517 * while pointers are not. We could make this safe in 3518 * special cases if root is calling us, but it's 3519 * probably not worth the hassle. 3520 */ 3521 return false; 3522 } 3523 case PTR_TO_MAP_VALUE: 3524 /* If the new min/max/var_off satisfy the old ones and 3525 * everything else matches, we are OK. 3526 * We don't care about the 'id' value, because nothing 3527 * uses it for PTR_TO_MAP_VALUE (only for ..._OR_NULL) 3528 */ 3529 return memcmp(rold, rcur, offsetof(struct bpf_reg_state, id)) == 0 && 3530 range_within(rold, rcur) && 3531 tnum_in(rold->var_off, rcur->var_off); 3532 case PTR_TO_MAP_VALUE_OR_NULL: 3533 /* a PTR_TO_MAP_VALUE could be safe to use as a 3534 * PTR_TO_MAP_VALUE_OR_NULL into the same map. 3535 * However, if the old PTR_TO_MAP_VALUE_OR_NULL then got NULL- 3536 * checked, doing so could have affected others with the same 3537 * id, and we can't check for that because we lost the id when 3538 * we converted to a PTR_TO_MAP_VALUE. 3539 */ 3540 if (rcur->type != PTR_TO_MAP_VALUE_OR_NULL) 3541 return false; 3542 if (memcmp(rold, rcur, offsetof(struct bpf_reg_state, id))) 3543 return false; 3544 /* Check our ids match any regs they're supposed to */ 3545 return check_ids(rold->id, rcur->id, idmap); 3546 case PTR_TO_PACKET_META: 3547 case PTR_TO_PACKET: 3548 if (rcur->type != rold->type) 3549 return false; 3550 /* We must have at least as much range as the old ptr 3551 * did, so that any accesses which were safe before are 3552 * still safe. This is true even if old range < old off, 3553 * since someone could have accessed through (ptr - k), or 3554 * even done ptr -= k in a register, to get a safe access. 3555 */ 3556 if (rold->range > rcur->range) 3557 return false; 3558 /* If the offsets don't match, we can't trust our alignment; 3559 * nor can we be sure that we won't fall out of range. 3560 */ 3561 if (rold->off != rcur->off) 3562 return false; 3563 /* id relations must be preserved */ 3564 if (rold->id && !check_ids(rold->id, rcur->id, idmap)) 3565 return false; 3566 /* new val must satisfy old val knowledge */ 3567 return range_within(rold, rcur) && 3568 tnum_in(rold->var_off, rcur->var_off); 3569 case PTR_TO_CTX: 3570 case CONST_PTR_TO_MAP: 3571 case PTR_TO_STACK: 3572 case PTR_TO_PACKET_END: 3573 /* Only valid matches are exact, which memcmp() above 3574 * would have accepted 3575 */ 3576 default: 3577 /* Don't know what's going on, just say it's not safe */ 3578 return false; 3579 } 3580 3581 /* Shouldn't get here; if we do, say it's not safe */ 3582 WARN_ON_ONCE(1); 3583 return false; 3584 } 3585 3586 static bool stacksafe(struct bpf_verifier_state *old, 3587 struct bpf_verifier_state *cur, 3588 struct idpair *idmap) 3589 { 3590 int i, spi; 3591 3592 /* if explored stack has more populated slots than current stack 3593 * such stacks are not equivalent 3594 */ 3595 if (old->allocated_stack > cur->allocated_stack) 3596 return false; 3597 3598 /* walk slots of the explored stack and ignore any additional 3599 * slots in the current stack, since explored(safe) state 3600 * didn't use them 3601 */ 3602 for (i = 0; i < old->allocated_stack; i++) { 3603 spi = i / BPF_REG_SIZE; 3604 3605 if (old->stack[spi].slot_type[i % BPF_REG_SIZE] == STACK_INVALID) 3606 continue; 3607 if (old->stack[spi].slot_type[i % BPF_REG_SIZE] != 3608 cur->stack[spi].slot_type[i % BPF_REG_SIZE]) 3609 /* Ex: old explored (safe) state has STACK_SPILL in 3610 * this stack slot, but current has has STACK_MISC -> 3611 * this verifier states are not equivalent, 3612 * return false to continue verification of this path 3613 */ 3614 return false; 3615 if (i % BPF_REG_SIZE) 3616 continue; 3617 if (old->stack[spi].slot_type[0] != STACK_SPILL) 3618 continue; 3619 if (!regsafe(&old->stack[spi].spilled_ptr, 3620 &cur->stack[spi].spilled_ptr, 3621 idmap)) 3622 /* when explored and current stack slot are both storing 3623 * spilled registers, check that stored pointers types 3624 * are the same as well. 3625 * Ex: explored safe path could have stored 3626 * (bpf_reg_state) {.type = PTR_TO_STACK, .off = -8} 3627 * but current path has stored: 3628 * (bpf_reg_state) {.type = PTR_TO_STACK, .off = -16} 3629 * such verifier states are not equivalent. 3630 * return false to continue verification of this path 3631 */ 3632 return false; 3633 } 3634 return true; 3635 } 3636 3637 /* compare two verifier states 3638 * 3639 * all states stored in state_list are known to be valid, since 3640 * verifier reached 'bpf_exit' instruction through them 3641 * 3642 * this function is called when verifier exploring different branches of 3643 * execution popped from the state stack. If it sees an old state that has 3644 * more strict register state and more strict stack state then this execution 3645 * branch doesn't need to be explored further, since verifier already 3646 * concluded that more strict state leads to valid finish. 3647 * 3648 * Therefore two states are equivalent if register state is more conservative 3649 * and explored stack state is more conservative than the current one. 3650 * Example: 3651 * explored current 3652 * (slot1=INV slot2=MISC) == (slot1=MISC slot2=MISC) 3653 * (slot1=MISC slot2=MISC) != (slot1=INV slot2=MISC) 3654 * 3655 * In other words if current stack state (one being explored) has more 3656 * valid slots than old one that already passed validation, it means 3657 * the verifier can stop exploring and conclude that current state is valid too 3658 * 3659 * Similarly with registers. If explored state has register type as invalid 3660 * whereas register type in current state is meaningful, it means that 3661 * the current state will reach 'bpf_exit' instruction safely 3662 */ 3663 static bool states_equal(struct bpf_verifier_env *env, 3664 struct bpf_verifier_state *old, 3665 struct bpf_verifier_state *cur) 3666 { 3667 struct idpair *idmap; 3668 bool ret = false; 3669 int i; 3670 3671 idmap = kcalloc(ID_MAP_SIZE, sizeof(struct idpair), GFP_KERNEL); 3672 /* If we failed to allocate the idmap, just say it's not safe */ 3673 if (!idmap) 3674 return false; 3675 3676 for (i = 0; i < MAX_BPF_REG; i++) { 3677 if (!regsafe(&old->regs[i], &cur->regs[i], idmap)) 3678 goto out_free; 3679 } 3680 3681 if (!stacksafe(old, cur, idmap)) 3682 goto out_free; 3683 ret = true; 3684 out_free: 3685 kfree(idmap); 3686 return ret; 3687 } 3688 3689 /* A write screens off any subsequent reads; but write marks come from the 3690 * straight-line code between a state and its parent. When we arrive at a 3691 * jump target (in the first iteration of the propagate_liveness() loop), 3692 * we didn't arrive by the straight-line code, so read marks in state must 3693 * propagate to parent regardless of state's write marks. 3694 */ 3695 static bool do_propagate_liveness(const struct bpf_verifier_state *state, 3696 struct bpf_verifier_state *parent) 3697 { 3698 bool writes = parent == state->parent; /* Observe write marks */ 3699 bool touched = false; /* any changes made? */ 3700 int i; 3701 3702 if (!parent) 3703 return touched; 3704 /* Propagate read liveness of registers... */ 3705 BUILD_BUG_ON(BPF_REG_FP + 1 != MAX_BPF_REG); 3706 /* We don't need to worry about FP liveness because it's read-only */ 3707 for (i = 0; i < BPF_REG_FP; i++) { 3708 if (parent->regs[i].live & REG_LIVE_READ) 3709 continue; 3710 if (writes && (state->regs[i].live & REG_LIVE_WRITTEN)) 3711 continue; 3712 if (state->regs[i].live & REG_LIVE_READ) { 3713 parent->regs[i].live |= REG_LIVE_READ; 3714 touched = true; 3715 } 3716 } 3717 /* ... and stack slots */ 3718 for (i = 0; i < state->allocated_stack / BPF_REG_SIZE && 3719 i < parent->allocated_stack / BPF_REG_SIZE; i++) { 3720 if (parent->stack[i].slot_type[0] != STACK_SPILL) 3721 continue; 3722 if (state->stack[i].slot_type[0] != STACK_SPILL) 3723 continue; 3724 if (parent->stack[i].spilled_ptr.live & REG_LIVE_READ) 3725 continue; 3726 if (writes && 3727 (state->stack[i].spilled_ptr.live & REG_LIVE_WRITTEN)) 3728 continue; 3729 if (state->stack[i].spilled_ptr.live & REG_LIVE_READ) { 3730 parent->stack[i].spilled_ptr.live |= REG_LIVE_READ; 3731 touched = true; 3732 } 3733 } 3734 return touched; 3735 } 3736 3737 /* "parent" is "a state from which we reach the current state", but initially 3738 * it is not the state->parent (i.e. "the state whose straight-line code leads 3739 * to the current state"), instead it is the state that happened to arrive at 3740 * a (prunable) equivalent of the current state. See comment above 3741 * do_propagate_liveness() for consequences of this. 3742 * This function is just a more efficient way of calling mark_reg_read() or 3743 * mark_stack_slot_read() on each reg in "parent" that is read in "state", 3744 * though it requires that parent != state->parent in the call arguments. 3745 */ 3746 static void propagate_liveness(const struct bpf_verifier_state *state, 3747 struct bpf_verifier_state *parent) 3748 { 3749 while (do_propagate_liveness(state, parent)) { 3750 /* Something changed, so we need to feed those changes onward */ 3751 state = parent; 3752 parent = state->parent; 3753 } 3754 } 3755 3756 static int is_state_visited(struct bpf_verifier_env *env, int insn_idx) 3757 { 3758 struct bpf_verifier_state_list *new_sl; 3759 struct bpf_verifier_state_list *sl; 3760 struct bpf_verifier_state *cur = env->cur_state; 3761 int i, err; 3762 3763 sl = env->explored_states[insn_idx]; 3764 if (!sl) 3765 /* this 'insn_idx' instruction wasn't marked, so we will not 3766 * be doing state search here 3767 */ 3768 return 0; 3769 3770 while (sl != STATE_LIST_MARK) { 3771 if (states_equal(env, &sl->state, cur)) { 3772 /* reached equivalent register/stack state, 3773 * prune the search. 3774 * Registers read by the continuation are read by us. 3775 * If we have any write marks in env->cur_state, they 3776 * will prevent corresponding reads in the continuation 3777 * from reaching our parent (an explored_state). Our 3778 * own state will get the read marks recorded, but 3779 * they'll be immediately forgotten as we're pruning 3780 * this state and will pop a new one. 3781 */ 3782 propagate_liveness(&sl->state, cur); 3783 return 1; 3784 } 3785 sl = sl->next; 3786 } 3787 3788 /* there were no equivalent states, remember current one. 3789 * technically the current state is not proven to be safe yet, 3790 * but it will either reach bpf_exit (which means it's safe) or 3791 * it will be rejected. Since there are no loops, we won't be 3792 * seeing this 'insn_idx' instruction again on the way to bpf_exit 3793 */ 3794 new_sl = kzalloc(sizeof(struct bpf_verifier_state_list), GFP_KERNEL); 3795 if (!new_sl) 3796 return -ENOMEM; 3797 3798 /* add new state to the head of linked list */ 3799 err = copy_verifier_state(&new_sl->state, cur); 3800 if (err) { 3801 free_verifier_state(&new_sl->state, false); 3802 kfree(new_sl); 3803 return err; 3804 } 3805 new_sl->next = env->explored_states[insn_idx]; 3806 env->explored_states[insn_idx] = new_sl; 3807 /* connect new state to parentage chain */ 3808 cur->parent = &new_sl->state; 3809 /* clear write marks in current state: the writes we did are not writes 3810 * our child did, so they don't screen off its reads from us. 3811 * (There are no read marks in current state, because reads always mark 3812 * their parent and current state never has children yet. Only 3813 * explored_states can get read marks.) 3814 */ 3815 for (i = 0; i < BPF_REG_FP; i++) 3816 cur->regs[i].live = REG_LIVE_NONE; 3817 for (i = 0; i < cur->allocated_stack / BPF_REG_SIZE; i++) 3818 if (cur->stack[i].slot_type[0] == STACK_SPILL) 3819 cur->stack[i].spilled_ptr.live = REG_LIVE_NONE; 3820 return 0; 3821 } 3822 3823 static int ext_analyzer_insn_hook(struct bpf_verifier_env *env, 3824 int insn_idx, int prev_insn_idx) 3825 { 3826 if (env->dev_ops && env->dev_ops->insn_hook) 3827 return env->dev_ops->insn_hook(env, insn_idx, prev_insn_idx); 3828 3829 return 0; 3830 } 3831 3832 static int do_check(struct bpf_verifier_env *env) 3833 { 3834 struct bpf_verifier_state *state; 3835 struct bpf_insn *insns = env->prog->insnsi; 3836 struct bpf_reg_state *regs; 3837 int insn_cnt = env->prog->len; 3838 int insn_idx, prev_insn_idx = 0; 3839 int insn_processed = 0; 3840 bool do_print_state = false; 3841 3842 state = kzalloc(sizeof(struct bpf_verifier_state), GFP_KERNEL); 3843 if (!state) 3844 return -ENOMEM; 3845 env->cur_state = state; 3846 init_reg_state(env, state->regs); 3847 state->parent = NULL; 3848 insn_idx = 0; 3849 for (;;) { 3850 struct bpf_insn *insn; 3851 u8 class; 3852 int err; 3853 3854 if (insn_idx >= insn_cnt) { 3855 verbose(env, "invalid insn idx %d insn_cnt %d\n", 3856 insn_idx, insn_cnt); 3857 return -EFAULT; 3858 } 3859 3860 insn = &insns[insn_idx]; 3861 class = BPF_CLASS(insn->code); 3862 3863 if (++insn_processed > BPF_COMPLEXITY_LIMIT_INSNS) { 3864 verbose(env, 3865 "BPF program is too large. Processed %d insn\n", 3866 insn_processed); 3867 return -E2BIG; 3868 } 3869 3870 err = is_state_visited(env, insn_idx); 3871 if (err < 0) 3872 return err; 3873 if (err == 1) { 3874 /* found equivalent state, can prune the search */ 3875 if (env->log.level) { 3876 if (do_print_state) 3877 verbose(env, "\nfrom %d to %d: safe\n", 3878 prev_insn_idx, insn_idx); 3879 else 3880 verbose(env, "%d: safe\n", insn_idx); 3881 } 3882 goto process_bpf_exit; 3883 } 3884 3885 if (need_resched()) 3886 cond_resched(); 3887 3888 if (env->log.level > 1 || (env->log.level && do_print_state)) { 3889 if (env->log.level > 1) 3890 verbose(env, "%d:", insn_idx); 3891 else 3892 verbose(env, "\nfrom %d to %d:", 3893 prev_insn_idx, insn_idx); 3894 print_verifier_state(env, state); 3895 do_print_state = false; 3896 } 3897 3898 if (env->log.level) { 3899 verbose(env, "%d: ", insn_idx); 3900 print_bpf_insn(verbose, env, insn, 3901 env->allow_ptr_leaks); 3902 } 3903 3904 err = ext_analyzer_insn_hook(env, insn_idx, prev_insn_idx); 3905 if (err) 3906 return err; 3907 3908 regs = cur_regs(env); 3909 env->insn_aux_data[insn_idx].seen = true; 3910 if (class == BPF_ALU || class == BPF_ALU64) { 3911 err = check_alu_op(env, insn); 3912 if (err) 3913 return err; 3914 3915 } else if (class == BPF_LDX) { 3916 enum bpf_reg_type *prev_src_type, src_reg_type; 3917 3918 /* check for reserved fields is already done */ 3919 3920 /* check src operand */ 3921 err = check_reg_arg(env, insn->src_reg, SRC_OP); 3922 if (err) 3923 return err; 3924 3925 err = check_reg_arg(env, insn->dst_reg, DST_OP_NO_MARK); 3926 if (err) 3927 return err; 3928 3929 src_reg_type = regs[insn->src_reg].type; 3930 3931 /* check that memory (src_reg + off) is readable, 3932 * the state of dst_reg will be updated by this func 3933 */ 3934 err = check_mem_access(env, insn_idx, insn->src_reg, insn->off, 3935 BPF_SIZE(insn->code), BPF_READ, 3936 insn->dst_reg); 3937 if (err) 3938 return err; 3939 3940 prev_src_type = &env->insn_aux_data[insn_idx].ptr_type; 3941 3942 if (*prev_src_type == NOT_INIT) { 3943 /* saw a valid insn 3944 * dst_reg = *(u32 *)(src_reg + off) 3945 * save type to validate intersecting paths 3946 */ 3947 *prev_src_type = src_reg_type; 3948 3949 } else if (src_reg_type != *prev_src_type && 3950 (src_reg_type == PTR_TO_CTX || 3951 *prev_src_type == PTR_TO_CTX)) { 3952 /* ABuser program is trying to use the same insn 3953 * dst_reg = *(u32*) (src_reg + off) 3954 * with different pointer types: 3955 * src_reg == ctx in one branch and 3956 * src_reg == stack|map in some other branch. 3957 * Reject it. 3958 */ 3959 verbose(env, "same insn cannot be used with different pointers\n"); 3960 return -EINVAL; 3961 } 3962 3963 } else if (class == BPF_STX) { 3964 enum bpf_reg_type *prev_dst_type, dst_reg_type; 3965 3966 if (BPF_MODE(insn->code) == BPF_XADD) { 3967 err = check_xadd(env, insn_idx, insn); 3968 if (err) 3969 return err; 3970 insn_idx++; 3971 continue; 3972 } 3973 3974 /* check src1 operand */ 3975 err = check_reg_arg(env, insn->src_reg, SRC_OP); 3976 if (err) 3977 return err; 3978 /* check src2 operand */ 3979 err = check_reg_arg(env, insn->dst_reg, SRC_OP); 3980 if (err) 3981 return err; 3982 3983 dst_reg_type = regs[insn->dst_reg].type; 3984 3985 /* check that memory (dst_reg + off) is writeable */ 3986 err = check_mem_access(env, insn_idx, insn->dst_reg, insn->off, 3987 BPF_SIZE(insn->code), BPF_WRITE, 3988 insn->src_reg); 3989 if (err) 3990 return err; 3991 3992 prev_dst_type = &env->insn_aux_data[insn_idx].ptr_type; 3993 3994 if (*prev_dst_type == NOT_INIT) { 3995 *prev_dst_type = dst_reg_type; 3996 } else if (dst_reg_type != *prev_dst_type && 3997 (dst_reg_type == PTR_TO_CTX || 3998 *prev_dst_type == PTR_TO_CTX)) { 3999 verbose(env, "same insn cannot be used with different pointers\n"); 4000 return -EINVAL; 4001 } 4002 4003 } else if (class == BPF_ST) { 4004 if (BPF_MODE(insn->code) != BPF_MEM || 4005 insn->src_reg != BPF_REG_0) { 4006 verbose(env, "BPF_ST uses reserved fields\n"); 4007 return -EINVAL; 4008 } 4009 /* check src operand */ 4010 err = check_reg_arg(env, insn->dst_reg, SRC_OP); 4011 if (err) 4012 return err; 4013 4014 if (is_ctx_reg(env, insn->dst_reg)) { 4015 verbose(env, "BPF_ST stores into R%d context is not allowed\n", 4016 insn->dst_reg); 4017 return -EACCES; 4018 } 4019 4020 /* check that memory (dst_reg + off) is writeable */ 4021 err = check_mem_access(env, insn_idx, insn->dst_reg, insn->off, 4022 BPF_SIZE(insn->code), BPF_WRITE, 4023 -1); 4024 if (err) 4025 return err; 4026 4027 } else if (class == BPF_JMP) { 4028 u8 opcode = BPF_OP(insn->code); 4029 4030 if (opcode == BPF_CALL) { 4031 if (BPF_SRC(insn->code) != BPF_K || 4032 insn->off != 0 || 4033 insn->src_reg != BPF_REG_0 || 4034 insn->dst_reg != BPF_REG_0) { 4035 verbose(env, "BPF_CALL uses reserved fields\n"); 4036 return -EINVAL; 4037 } 4038 4039 err = check_call(env, insn->imm, insn_idx); 4040 if (err) 4041 return err; 4042 4043 } else if (opcode == BPF_JA) { 4044 if (BPF_SRC(insn->code) != BPF_K || 4045 insn->imm != 0 || 4046 insn->src_reg != BPF_REG_0 || 4047 insn->dst_reg != BPF_REG_0) { 4048 verbose(env, "BPF_JA uses reserved fields\n"); 4049 return -EINVAL; 4050 } 4051 4052 insn_idx += insn->off + 1; 4053 continue; 4054 4055 } else if (opcode == BPF_EXIT) { 4056 if (BPF_SRC(insn->code) != BPF_K || 4057 insn->imm != 0 || 4058 insn->src_reg != BPF_REG_0 || 4059 insn->dst_reg != BPF_REG_0) { 4060 verbose(env, "BPF_EXIT uses reserved fields\n"); 4061 return -EINVAL; 4062 } 4063 4064 /* eBPF calling convetion is such that R0 is used 4065 * to return the value from eBPF program. 4066 * Make sure that it's readable at this time 4067 * of bpf_exit, which means that program wrote 4068 * something into it earlier 4069 */ 4070 err = check_reg_arg(env, BPF_REG_0, SRC_OP); 4071 if (err) 4072 return err; 4073 4074 if (is_pointer_value(env, BPF_REG_0)) { 4075 verbose(env, "R0 leaks addr as return value\n"); 4076 return -EACCES; 4077 } 4078 4079 err = check_return_code(env); 4080 if (err) 4081 return err; 4082 process_bpf_exit: 4083 err = pop_stack(env, &prev_insn_idx, &insn_idx); 4084 if (err < 0) { 4085 if (err != -ENOENT) 4086 return err; 4087 break; 4088 } else { 4089 do_print_state = true; 4090 continue; 4091 } 4092 } else { 4093 err = check_cond_jmp_op(env, insn, &insn_idx); 4094 if (err) 4095 return err; 4096 } 4097 } else if (class == BPF_LD) { 4098 u8 mode = BPF_MODE(insn->code); 4099 4100 if (mode == BPF_ABS || mode == BPF_IND) { 4101 err = check_ld_abs(env, insn); 4102 if (err) 4103 return err; 4104 4105 } else if (mode == BPF_IMM) { 4106 err = check_ld_imm(env, insn); 4107 if (err) 4108 return err; 4109 4110 insn_idx++; 4111 env->insn_aux_data[insn_idx].seen = true; 4112 } else { 4113 verbose(env, "invalid BPF_LD mode\n"); 4114 return -EINVAL; 4115 } 4116 } else { 4117 verbose(env, "unknown insn class %d\n", class); 4118 return -EINVAL; 4119 } 4120 4121 insn_idx++; 4122 } 4123 4124 verbose(env, "processed %d insns, stack depth %d\n", insn_processed, 4125 env->prog->aux->stack_depth); 4126 return 0; 4127 } 4128 4129 static int check_map_prealloc(struct bpf_map *map) 4130 { 4131 return (map->map_type != BPF_MAP_TYPE_HASH && 4132 map->map_type != BPF_MAP_TYPE_PERCPU_HASH && 4133 map->map_type != BPF_MAP_TYPE_HASH_OF_MAPS) || 4134 !(map->map_flags & BPF_F_NO_PREALLOC); 4135 } 4136 4137 static int check_map_prog_compatibility(struct bpf_verifier_env *env, 4138 struct bpf_map *map, 4139 struct bpf_prog *prog) 4140 4141 { 4142 /* Make sure that BPF_PROG_TYPE_PERF_EVENT programs only use 4143 * preallocated hash maps, since doing memory allocation 4144 * in overflow_handler can crash depending on where nmi got 4145 * triggered. 4146 */ 4147 if (prog->type == BPF_PROG_TYPE_PERF_EVENT) { 4148 if (!check_map_prealloc(map)) { 4149 verbose(env, "perf_event programs can only use preallocated hash map\n"); 4150 return -EINVAL; 4151 } 4152 if (map->inner_map_meta && 4153 !check_map_prealloc(map->inner_map_meta)) { 4154 verbose(env, "perf_event programs can only use preallocated inner hash map\n"); 4155 return -EINVAL; 4156 } 4157 } 4158 return 0; 4159 } 4160 4161 /* look for pseudo eBPF instructions that access map FDs and 4162 * replace them with actual map pointers 4163 */ 4164 static int replace_map_fd_with_map_ptr(struct bpf_verifier_env *env) 4165 { 4166 struct bpf_insn *insn = env->prog->insnsi; 4167 int insn_cnt = env->prog->len; 4168 int i, j, err; 4169 4170 err = bpf_prog_calc_tag(env->prog); 4171 if (err) 4172 return err; 4173 4174 for (i = 0; i < insn_cnt; i++, insn++) { 4175 if (BPF_CLASS(insn->code) == BPF_LDX && 4176 (BPF_MODE(insn->code) != BPF_MEM || insn->imm != 0)) { 4177 verbose(env, "BPF_LDX uses reserved fields\n"); 4178 return -EINVAL; 4179 } 4180 4181 if (BPF_CLASS(insn->code) == BPF_STX && 4182 ((BPF_MODE(insn->code) != BPF_MEM && 4183 BPF_MODE(insn->code) != BPF_XADD) || insn->imm != 0)) { 4184 verbose(env, "BPF_STX uses reserved fields\n"); 4185 return -EINVAL; 4186 } 4187 4188 if (insn[0].code == (BPF_LD | BPF_IMM | BPF_DW)) { 4189 struct bpf_map *map; 4190 struct fd f; 4191 4192 if (i == insn_cnt - 1 || insn[1].code != 0 || 4193 insn[1].dst_reg != 0 || insn[1].src_reg != 0 || 4194 insn[1].off != 0) { 4195 verbose(env, "invalid bpf_ld_imm64 insn\n"); 4196 return -EINVAL; 4197 } 4198 4199 if (insn->src_reg == 0) 4200 /* valid generic load 64-bit imm */ 4201 goto next_insn; 4202 4203 if (insn->src_reg != BPF_PSEUDO_MAP_FD) { 4204 verbose(env, 4205 "unrecognized bpf_ld_imm64 insn\n"); 4206 return -EINVAL; 4207 } 4208 4209 f = fdget(insn->imm); 4210 map = __bpf_map_get(f); 4211 if (IS_ERR(map)) { 4212 verbose(env, "fd %d is not pointing to valid bpf_map\n", 4213 insn->imm); 4214 return PTR_ERR(map); 4215 } 4216 4217 err = check_map_prog_compatibility(env, map, env->prog); 4218 if (err) { 4219 fdput(f); 4220 return err; 4221 } 4222 4223 /* store map pointer inside BPF_LD_IMM64 instruction */ 4224 insn[0].imm = (u32) (unsigned long) map; 4225 insn[1].imm = ((u64) (unsigned long) map) >> 32; 4226 4227 /* check whether we recorded this map already */ 4228 for (j = 0; j < env->used_map_cnt; j++) 4229 if (env->used_maps[j] == map) { 4230 fdput(f); 4231 goto next_insn; 4232 } 4233 4234 if (env->used_map_cnt >= MAX_USED_MAPS) { 4235 fdput(f); 4236 return -E2BIG; 4237 } 4238 4239 /* hold the map. If the program is rejected by verifier, 4240 * the map will be released by release_maps() or it 4241 * will be used by the valid program until it's unloaded 4242 * and all maps are released in free_bpf_prog_info() 4243 */ 4244 map = bpf_map_inc(map, false); 4245 if (IS_ERR(map)) { 4246 fdput(f); 4247 return PTR_ERR(map); 4248 } 4249 env->used_maps[env->used_map_cnt++] = map; 4250 4251 fdput(f); 4252 next_insn: 4253 insn++; 4254 i++; 4255 } 4256 } 4257 4258 /* now all pseudo BPF_LD_IMM64 instructions load valid 4259 * 'struct bpf_map *' into a register instead of user map_fd. 4260 * These pointers will be used later by verifier to validate map access. 4261 */ 4262 return 0; 4263 } 4264 4265 /* drop refcnt of maps used by the rejected program */ 4266 static void release_maps(struct bpf_verifier_env *env) 4267 { 4268 int i; 4269 4270 for (i = 0; i < env->used_map_cnt; i++) 4271 bpf_map_put(env->used_maps[i]); 4272 } 4273 4274 /* convert pseudo BPF_LD_IMM64 into generic BPF_LD_IMM64 */ 4275 static void convert_pseudo_ld_imm64(struct bpf_verifier_env *env) 4276 { 4277 struct bpf_insn *insn = env->prog->insnsi; 4278 int insn_cnt = env->prog->len; 4279 int i; 4280 4281 for (i = 0; i < insn_cnt; i++, insn++) 4282 if (insn->code == (BPF_LD | BPF_IMM | BPF_DW)) 4283 insn->src_reg = 0; 4284 } 4285 4286 /* single env->prog->insni[off] instruction was replaced with the range 4287 * insni[off, off + cnt). Adjust corresponding insn_aux_data by copying 4288 * [0, off) and [off, end) to new locations, so the patched range stays zero 4289 */ 4290 static int adjust_insn_aux_data(struct bpf_verifier_env *env, u32 prog_len, 4291 u32 off, u32 cnt) 4292 { 4293 struct bpf_insn_aux_data *new_data, *old_data = env->insn_aux_data; 4294 int i; 4295 4296 if (cnt == 1) 4297 return 0; 4298 new_data = vzalloc(sizeof(struct bpf_insn_aux_data) * prog_len); 4299 if (!new_data) 4300 return -ENOMEM; 4301 memcpy(new_data, old_data, sizeof(struct bpf_insn_aux_data) * off); 4302 memcpy(new_data + off + cnt - 1, old_data + off, 4303 sizeof(struct bpf_insn_aux_data) * (prog_len - off - cnt + 1)); 4304 for (i = off; i < off + cnt - 1; i++) 4305 new_data[i].seen = true; 4306 env->insn_aux_data = new_data; 4307 vfree(old_data); 4308 return 0; 4309 } 4310 4311 static struct bpf_prog *bpf_patch_insn_data(struct bpf_verifier_env *env, u32 off, 4312 const struct bpf_insn *patch, u32 len) 4313 { 4314 struct bpf_prog *new_prog; 4315 4316 new_prog = bpf_patch_insn_single(env->prog, off, patch, len); 4317 if (!new_prog) 4318 return NULL; 4319 if (adjust_insn_aux_data(env, new_prog->len, off, len)) 4320 return NULL; 4321 return new_prog; 4322 } 4323 4324 /* The verifier does more data flow analysis than llvm and will not explore 4325 * branches that are dead at run time. Malicious programs can have dead code 4326 * too. Therefore replace all dead at-run-time code with nops. 4327 */ 4328 static void sanitize_dead_code(struct bpf_verifier_env *env) 4329 { 4330 struct bpf_insn_aux_data *aux_data = env->insn_aux_data; 4331 struct bpf_insn nop = BPF_MOV64_REG(BPF_REG_0, BPF_REG_0); 4332 struct bpf_insn *insn = env->prog->insnsi; 4333 const int insn_cnt = env->prog->len; 4334 int i; 4335 4336 for (i = 0; i < insn_cnt; i++) { 4337 if (aux_data[i].seen) 4338 continue; 4339 memcpy(insn + i, &nop, sizeof(nop)); 4340 } 4341 } 4342 4343 /* convert load instructions that access fields of 'struct __sk_buff' 4344 * into sequence of instructions that access fields of 'struct sk_buff' 4345 */ 4346 static int convert_ctx_accesses(struct bpf_verifier_env *env) 4347 { 4348 const struct bpf_verifier_ops *ops = env->ops; 4349 int i, cnt, size, ctx_field_size, delta = 0; 4350 const int insn_cnt = env->prog->len; 4351 struct bpf_insn insn_buf[16], *insn; 4352 struct bpf_prog *new_prog; 4353 enum bpf_access_type type; 4354 bool is_narrower_load; 4355 u32 target_size; 4356 4357 if (ops->gen_prologue) { 4358 cnt = ops->gen_prologue(insn_buf, env->seen_direct_write, 4359 env->prog); 4360 if (cnt >= ARRAY_SIZE(insn_buf)) { 4361 verbose(env, "bpf verifier is misconfigured\n"); 4362 return -EINVAL; 4363 } else if (cnt) { 4364 new_prog = bpf_patch_insn_data(env, 0, insn_buf, cnt); 4365 if (!new_prog) 4366 return -ENOMEM; 4367 4368 env->prog = new_prog; 4369 delta += cnt - 1; 4370 } 4371 } 4372 4373 if (!ops->convert_ctx_access) 4374 return 0; 4375 4376 insn = env->prog->insnsi + delta; 4377 4378 for (i = 0; i < insn_cnt; i++, insn++) { 4379 if (insn->code == (BPF_LDX | BPF_MEM | BPF_B) || 4380 insn->code == (BPF_LDX | BPF_MEM | BPF_H) || 4381 insn->code == (BPF_LDX | BPF_MEM | BPF_W) || 4382 insn->code == (BPF_LDX | BPF_MEM | BPF_DW)) 4383 type = BPF_READ; 4384 else if (insn->code == (BPF_STX | BPF_MEM | BPF_B) || 4385 insn->code == (BPF_STX | BPF_MEM | BPF_H) || 4386 insn->code == (BPF_STX | BPF_MEM | BPF_W) || 4387 insn->code == (BPF_STX | BPF_MEM | BPF_DW)) 4388 type = BPF_WRITE; 4389 else 4390 continue; 4391 4392 if (env->insn_aux_data[i + delta].ptr_type != PTR_TO_CTX) 4393 continue; 4394 4395 ctx_field_size = env->insn_aux_data[i + delta].ctx_field_size; 4396 size = BPF_LDST_BYTES(insn); 4397 4398 /* If the read access is a narrower load of the field, 4399 * convert to a 4/8-byte load, to minimum program type specific 4400 * convert_ctx_access changes. If conversion is successful, 4401 * we will apply proper mask to the result. 4402 */ 4403 is_narrower_load = size < ctx_field_size; 4404 if (is_narrower_load) { 4405 u32 off = insn->off; 4406 u8 size_code; 4407 4408 if (type == BPF_WRITE) { 4409 verbose(env, "bpf verifier narrow ctx access misconfigured\n"); 4410 return -EINVAL; 4411 } 4412 4413 size_code = BPF_H; 4414 if (ctx_field_size == 4) 4415 size_code = BPF_W; 4416 else if (ctx_field_size == 8) 4417 size_code = BPF_DW; 4418 4419 insn->off = off & ~(ctx_field_size - 1); 4420 insn->code = BPF_LDX | BPF_MEM | size_code; 4421 } 4422 4423 target_size = 0; 4424 cnt = ops->convert_ctx_access(type, insn, insn_buf, env->prog, 4425 &target_size); 4426 if (cnt == 0 || cnt >= ARRAY_SIZE(insn_buf) || 4427 (ctx_field_size && !target_size)) { 4428 verbose(env, "bpf verifier is misconfigured\n"); 4429 return -EINVAL; 4430 } 4431 4432 if (is_narrower_load && size < target_size) { 4433 if (ctx_field_size <= 4) 4434 insn_buf[cnt++] = BPF_ALU32_IMM(BPF_AND, insn->dst_reg, 4435 (1 << size * 8) - 1); 4436 else 4437 insn_buf[cnt++] = BPF_ALU64_IMM(BPF_AND, insn->dst_reg, 4438 (1 << size * 8) - 1); 4439 } 4440 4441 new_prog = bpf_patch_insn_data(env, i + delta, insn_buf, cnt); 4442 if (!new_prog) 4443 return -ENOMEM; 4444 4445 delta += cnt - 1; 4446 4447 /* keep walking new program and skip insns we just inserted */ 4448 env->prog = new_prog; 4449 insn = new_prog->insnsi + i + delta; 4450 } 4451 4452 return 0; 4453 } 4454 4455 /* fixup insn->imm field of bpf_call instructions 4456 * and inline eligible helpers as explicit sequence of BPF instructions 4457 * 4458 * this function is called after eBPF program passed verification 4459 */ 4460 static int fixup_bpf_calls(struct bpf_verifier_env *env) 4461 { 4462 struct bpf_prog *prog = env->prog; 4463 struct bpf_insn *insn = prog->insnsi; 4464 const struct bpf_func_proto *fn; 4465 const int insn_cnt = prog->len; 4466 struct bpf_insn insn_buf[16]; 4467 struct bpf_prog *new_prog; 4468 struct bpf_map *map_ptr; 4469 int i, cnt, delta = 0; 4470 4471 for (i = 0; i < insn_cnt; i++, insn++) { 4472 if (insn->code == (BPF_ALU | BPF_MOD | BPF_X) || 4473 insn->code == (BPF_ALU | BPF_DIV | BPF_X)) { 4474 /* due to JIT bugs clear upper 32-bits of src register 4475 * before div/mod operation 4476 */ 4477 insn_buf[0] = BPF_MOV32_REG(insn->src_reg, insn->src_reg); 4478 insn_buf[1] = *insn; 4479 cnt = 2; 4480 new_prog = bpf_patch_insn_data(env, i + delta, insn_buf, cnt); 4481 if (!new_prog) 4482 return -ENOMEM; 4483 4484 delta += cnt - 1; 4485 env->prog = prog = new_prog; 4486 insn = new_prog->insnsi + i + delta; 4487 continue; 4488 } 4489 4490 if (insn->code != (BPF_JMP | BPF_CALL)) 4491 continue; 4492 4493 if (insn->imm == BPF_FUNC_get_route_realm) 4494 prog->dst_needed = 1; 4495 if (insn->imm == BPF_FUNC_get_prandom_u32) 4496 bpf_user_rnd_init_once(); 4497 if (insn->imm == BPF_FUNC_tail_call) { 4498 /* If we tail call into other programs, we 4499 * cannot make any assumptions since they can 4500 * be replaced dynamically during runtime in 4501 * the program array. 4502 */ 4503 prog->cb_access = 1; 4504 env->prog->aux->stack_depth = MAX_BPF_STACK; 4505 4506 /* mark bpf_tail_call as different opcode to avoid 4507 * conditional branch in the interpeter for every normal 4508 * call and to prevent accidental JITing by JIT compiler 4509 * that doesn't support bpf_tail_call yet 4510 */ 4511 insn->imm = 0; 4512 insn->code = BPF_JMP | BPF_TAIL_CALL; 4513 4514 /* instead of changing every JIT dealing with tail_call 4515 * emit two extra insns: 4516 * if (index >= max_entries) goto out; 4517 * index &= array->index_mask; 4518 * to avoid out-of-bounds cpu speculation 4519 */ 4520 map_ptr = env->insn_aux_data[i + delta].map_ptr; 4521 if (map_ptr == BPF_MAP_PTR_POISON) { 4522 verbose(env, "tail_call abusing map_ptr\n"); 4523 return -EINVAL; 4524 } 4525 if (!map_ptr->unpriv_array) 4526 continue; 4527 insn_buf[0] = BPF_JMP_IMM(BPF_JGE, BPF_REG_3, 4528 map_ptr->max_entries, 2); 4529 insn_buf[1] = BPF_ALU32_IMM(BPF_AND, BPF_REG_3, 4530 container_of(map_ptr, 4531 struct bpf_array, 4532 map)->index_mask); 4533 insn_buf[2] = *insn; 4534 cnt = 3; 4535 new_prog = bpf_patch_insn_data(env, i + delta, insn_buf, cnt); 4536 if (!new_prog) 4537 return -ENOMEM; 4538 4539 delta += cnt - 1; 4540 env->prog = prog = new_prog; 4541 insn = new_prog->insnsi + i + delta; 4542 continue; 4543 } 4544 4545 /* BPF_EMIT_CALL() assumptions in some of the map_gen_lookup 4546 * handlers are currently limited to 64 bit only. 4547 */ 4548 if (ebpf_jit_enabled() && BITS_PER_LONG == 64 && 4549 insn->imm == BPF_FUNC_map_lookup_elem) { 4550 map_ptr = env->insn_aux_data[i + delta].map_ptr; 4551 if (map_ptr == BPF_MAP_PTR_POISON || 4552 !map_ptr->ops->map_gen_lookup) 4553 goto patch_call_imm; 4554 4555 cnt = map_ptr->ops->map_gen_lookup(map_ptr, insn_buf); 4556 if (cnt == 0 || cnt >= ARRAY_SIZE(insn_buf)) { 4557 verbose(env, "bpf verifier is misconfigured\n"); 4558 return -EINVAL; 4559 } 4560 4561 new_prog = bpf_patch_insn_data(env, i + delta, insn_buf, 4562 cnt); 4563 if (!new_prog) 4564 return -ENOMEM; 4565 4566 delta += cnt - 1; 4567 4568 /* keep walking new program and skip insns we just inserted */ 4569 env->prog = prog = new_prog; 4570 insn = new_prog->insnsi + i + delta; 4571 continue; 4572 } 4573 4574 if (insn->imm == BPF_FUNC_redirect_map) { 4575 /* Note, we cannot use prog directly as imm as subsequent 4576 * rewrites would still change the prog pointer. The only 4577 * stable address we can use is aux, which also works with 4578 * prog clones during blinding. 4579 */ 4580 u64 addr = (unsigned long)prog->aux; 4581 struct bpf_insn r4_ld[] = { 4582 BPF_LD_IMM64(BPF_REG_4, addr), 4583 *insn, 4584 }; 4585 cnt = ARRAY_SIZE(r4_ld); 4586 4587 new_prog = bpf_patch_insn_data(env, i + delta, r4_ld, cnt); 4588 if (!new_prog) 4589 return -ENOMEM; 4590 4591 delta += cnt - 1; 4592 env->prog = prog = new_prog; 4593 insn = new_prog->insnsi + i + delta; 4594 } 4595 patch_call_imm: 4596 fn = env->ops->get_func_proto(insn->imm); 4597 /* all functions that have prototype and verifier allowed 4598 * programs to call them, must be real in-kernel functions 4599 */ 4600 if (!fn->func) { 4601 verbose(env, 4602 "kernel subsystem misconfigured func %s#%d\n", 4603 func_id_name(insn->imm), insn->imm); 4604 return -EFAULT; 4605 } 4606 insn->imm = fn->func - __bpf_call_base; 4607 } 4608 4609 return 0; 4610 } 4611 4612 static void free_states(struct bpf_verifier_env *env) 4613 { 4614 struct bpf_verifier_state_list *sl, *sln; 4615 int i; 4616 4617 if (!env->explored_states) 4618 return; 4619 4620 for (i = 0; i < env->prog->len; i++) { 4621 sl = env->explored_states[i]; 4622 4623 if (sl) 4624 while (sl != STATE_LIST_MARK) { 4625 sln = sl->next; 4626 free_verifier_state(&sl->state, false); 4627 kfree(sl); 4628 sl = sln; 4629 } 4630 } 4631 4632 kfree(env->explored_states); 4633 } 4634 4635 int bpf_check(struct bpf_prog **prog, union bpf_attr *attr) 4636 { 4637 struct bpf_verifier_env *env; 4638 struct bpf_verifer_log *log; 4639 int ret = -EINVAL; 4640 4641 /* no program is valid */ 4642 if (ARRAY_SIZE(bpf_verifier_ops) == 0) 4643 return -EINVAL; 4644 4645 /* 'struct bpf_verifier_env' can be global, but since it's not small, 4646 * allocate/free it every time bpf_check() is called 4647 */ 4648 env = kzalloc(sizeof(struct bpf_verifier_env), GFP_KERNEL); 4649 if (!env) 4650 return -ENOMEM; 4651 log = &env->log; 4652 4653 env->insn_aux_data = vzalloc(sizeof(struct bpf_insn_aux_data) * 4654 (*prog)->len); 4655 ret = -ENOMEM; 4656 if (!env->insn_aux_data) 4657 goto err_free_env; 4658 env->prog = *prog; 4659 env->ops = bpf_verifier_ops[env->prog->type]; 4660 4661 /* grab the mutex to protect few globals used by verifier */ 4662 mutex_lock(&bpf_verifier_lock); 4663 4664 if (attr->log_level || attr->log_buf || attr->log_size) { 4665 /* user requested verbose verifier output 4666 * and supplied buffer to store the verification trace 4667 */ 4668 log->level = attr->log_level; 4669 log->ubuf = (char __user *) (unsigned long) attr->log_buf; 4670 log->len_total = attr->log_size; 4671 4672 ret = -EINVAL; 4673 /* log attributes have to be sane */ 4674 if (log->len_total < 128 || log->len_total > UINT_MAX >> 8 || 4675 !log->level || !log->ubuf) 4676 goto err_unlock; 4677 } 4678 4679 env->strict_alignment = !!(attr->prog_flags & BPF_F_STRICT_ALIGNMENT); 4680 if (!IS_ENABLED(CONFIG_HAVE_EFFICIENT_UNALIGNED_ACCESS)) 4681 env->strict_alignment = true; 4682 4683 if (env->prog->aux->offload) { 4684 ret = bpf_prog_offload_verifier_prep(env); 4685 if (ret) 4686 goto err_unlock; 4687 } 4688 4689 ret = replace_map_fd_with_map_ptr(env); 4690 if (ret < 0) 4691 goto skip_full_check; 4692 4693 env->explored_states = kcalloc(env->prog->len, 4694 sizeof(struct bpf_verifier_state_list *), 4695 GFP_USER); 4696 ret = -ENOMEM; 4697 if (!env->explored_states) 4698 goto skip_full_check; 4699 4700 ret = check_cfg(env); 4701 if (ret < 0) 4702 goto skip_full_check; 4703 4704 env->allow_ptr_leaks = capable(CAP_SYS_ADMIN); 4705 4706 ret = do_check(env); 4707 if (env->cur_state) { 4708 free_verifier_state(env->cur_state, true); 4709 env->cur_state = NULL; 4710 } 4711 4712 skip_full_check: 4713 while (!pop_stack(env, NULL, NULL)); 4714 free_states(env); 4715 4716 if (ret == 0) 4717 sanitize_dead_code(env); 4718 4719 if (ret == 0) 4720 /* program is valid, convert *(u32*)(ctx + off) accesses */ 4721 ret = convert_ctx_accesses(env); 4722 4723 if (ret == 0) 4724 ret = fixup_bpf_calls(env); 4725 4726 if (log->level && bpf_verifier_log_full(log)) 4727 ret = -ENOSPC; 4728 if (log->level && !log->ubuf) { 4729 ret = -EFAULT; 4730 goto err_release_maps; 4731 } 4732 4733 if (ret == 0 && env->used_map_cnt) { 4734 /* if program passed verifier, update used_maps in bpf_prog_info */ 4735 env->prog->aux->used_maps = kmalloc_array(env->used_map_cnt, 4736 sizeof(env->used_maps[0]), 4737 GFP_KERNEL); 4738 4739 if (!env->prog->aux->used_maps) { 4740 ret = -ENOMEM; 4741 goto err_release_maps; 4742 } 4743 4744 memcpy(env->prog->aux->used_maps, env->used_maps, 4745 sizeof(env->used_maps[0]) * env->used_map_cnt); 4746 env->prog->aux->used_map_cnt = env->used_map_cnt; 4747 4748 /* program is valid. Convert pseudo bpf_ld_imm64 into generic 4749 * bpf_ld_imm64 instructions 4750 */ 4751 convert_pseudo_ld_imm64(env); 4752 } 4753 4754 err_release_maps: 4755 if (!env->prog->aux->used_maps) 4756 /* if we didn't copy map pointers into bpf_prog_info, release 4757 * them now. Otherwise free_bpf_prog_info() will release them. 4758 */ 4759 release_maps(env); 4760 *prog = env->prog; 4761 err_unlock: 4762 mutex_unlock(&bpf_verifier_lock); 4763 vfree(env->insn_aux_data); 4764 err_free_env: 4765 kfree(env); 4766 return ret; 4767 } 4768