1 // SPDX-License-Identifier: GPL-2.0-only 2 /* Copyright (c) 2026 Meta Platforms, Inc. and affiliates. */ 3 #include <linux/bpf.h> 4 #include <linux/bpf_verifier.h> 5 #include <linux/filter.h> 6 #include <linux/sort.h> 7 8 #include "diagnostics.h" 9 10 #define verbose(env, fmt, args...) bpf_verifier_log_write(env, fmt, ##args) 11 12 #define BPF_MAX_GOTOX_EDGES BPF_COMPLEXITY_LIMIT_INSNS 13 14 /* non-recursive DFS pseudo code 15 * 1 procedure DFS-iterative(G,v): 16 * 2 label v as discovered 17 * 3 let S be a stack 18 * 4 S.push(v) 19 * 5 while S is not empty 20 * 6 t <- S.peek() 21 * 7 if t is what we're looking for: 22 * 8 return t 23 * 9 for all edges e in G.adjacentEdges(t) do 24 * 10 if edge e is already labelled 25 * 11 continue with the next edge 26 * 12 w <- G.adjacentVertex(t,e) 27 * 13 if vertex w is not discovered and not explored 28 * 14 label e as tree-edge 29 * 15 label w as discovered 30 * 16 S.push(w) 31 * 17 continue at 5 32 * 18 else if vertex w is discovered 33 * 19 label e as back-edge 34 * 20 else 35 * 21 // vertex w is explored 36 * 22 label e as forward- or cross-edge 37 * 23 label t as explored 38 * 24 S.pop() 39 * 40 * convention: 41 * 0x10 - discovered 42 * 0x11 - discovered and fall-through edge labelled 43 * 0x12 - discovered and fall-through and branch edges labelled 44 * 0x20 - explored 45 */ 46 47 enum { 48 DISCOVERED = 0x10, 49 EXPLORED = 0x20, 50 FALLTHROUGH = 1, 51 BRANCH = 2, 52 }; 53 54 static void mark_subprog_changes_pkt_data(struct bpf_verifier_env *env, int off) 55 { 56 struct bpf_subprog_info *subprog; 57 58 subprog = bpf_find_containing_subprog(env, off); 59 subprog->changes_pkt_data = true; 60 } 61 62 static void mark_subprog_might_sleep(struct bpf_verifier_env *env, int off) 63 { 64 struct bpf_subprog_info *subprog; 65 66 subprog = bpf_find_containing_subprog(env, off); 67 subprog->might_sleep = true; 68 } 69 70 static void mark_subprog_might_throw(struct bpf_verifier_env *env, int off) 71 { 72 struct bpf_subprog_info *subprog; 73 74 subprog = bpf_find_containing_subprog(env, off); 75 subprog->might_throw = true; 76 } 77 78 /* 't' is an index of a call-site. 79 * 'w' is a callee entry point. 80 * Eventually this function would be called when env->cfg.insn_state[w] == EXPLORED. 81 * Rely on DFS traversal order and absence of recursive calls to guarantee that 82 * callee's effect marks would be correct at that moment. 83 */ 84 static void merge_callee_effects(struct bpf_verifier_env *env, int t, int w) 85 { 86 struct bpf_subprog_info *caller, *callee; 87 88 caller = bpf_find_containing_subprog(env, t); 89 callee = bpf_find_containing_subprog(env, w); 90 caller->changes_pkt_data |= callee->changes_pkt_data; 91 caller->might_sleep |= callee->might_sleep; 92 caller->might_throw |= callee->might_throw; 93 } 94 95 enum { 96 DONE_EXPLORING = 0, 97 KEEP_EXPLORING = 1, 98 }; 99 100 /* t, w, e - match pseudo-code above: 101 * t - index of current instruction 102 * w - next instruction 103 * e - edge 104 */ 105 static int push_insn(int t, int w, int e, struct bpf_verifier_env *env) 106 { 107 int *insn_stack = env->cfg.insn_stack; 108 int *insn_state = env->cfg.insn_state; 109 110 if (e == FALLTHROUGH && insn_state[t] >= (DISCOVERED | FALLTHROUGH)) 111 return DONE_EXPLORING; 112 113 if (e == BRANCH && insn_state[t] >= (DISCOVERED | BRANCH)) 114 return DONE_EXPLORING; 115 116 if (w < 0 || w >= env->prog->len) { 117 verbose_linfo(env, t, "%d: ", t); 118 verbose(env, "jump out of range from insn %d to %d\n", t, w); 119 bpf_diag_program_structure( 120 env, t, "jump out of range", "Keep branch targets inside the program.", 121 "Instruction %d jumps to instruction %d, but the program only contains instructions 0 through %d.", 122 t, w, env->prog->len - 1); 123 return -EINVAL; 124 } 125 126 if (e == BRANCH) { 127 /* mark branch target for state pruning */ 128 mark_prune_point(env, w); 129 mark_jmp_point(env, w); 130 mark_jump_target(env, w); 131 } 132 133 if (insn_state[w] == 0) { 134 /* tree-edge */ 135 insn_state[t] = DISCOVERED | e; 136 insn_state[w] = DISCOVERED; 137 if (env->cfg.cur_stack >= env->prog->len) 138 return -E2BIG; 139 insn_stack[env->cfg.cur_stack++] = w; 140 return KEEP_EXPLORING; 141 } else if ((insn_state[w] & 0xF0) == DISCOVERED) { 142 if (env->bpf_capable) 143 return DONE_EXPLORING; 144 verbose_linfo(env, t, "%d: ", t); 145 verbose_linfo(env, w, "%d: ", w); 146 verbose(env, "back-edge from insn %d to %d\n", t, w); 147 bpf_diag_program_structure( 148 env, t, "back-edge is not allowed", 149 "Load with privileges that allow this back-edge, or rewrite the control flow so it does not branch backward.", 150 "Instruction %d branches back to instruction %d. This program is being rejected without the privilege needed for this back-edge.", 151 t, w); 152 return -EINVAL; 153 } else if (insn_state[w] == EXPLORED) { 154 /* forward- or cross-edge */ 155 insn_state[t] = DISCOVERED | e; 156 } else { 157 verifier_bug(env, "insn state internal bug"); 158 return -EFAULT; 159 } 160 return DONE_EXPLORING; 161 } 162 163 static int visit_func_call_insn(int t, struct bpf_insn *insns, 164 struct bpf_verifier_env *env, 165 bool visit_callee) 166 { 167 int ret, insn_sz; 168 int w; 169 170 insn_sz = bpf_is_ldimm64(&insns[t]) ? 2 : 1; 171 ret = push_insn(t, t + insn_sz, FALLTHROUGH, env); 172 if (ret) 173 return ret; 174 175 mark_prune_point(env, t + insn_sz); 176 /* when we exit from subprog, we need to record non-linear history */ 177 mark_jmp_point(env, t + insn_sz); 178 179 if (visit_callee) { 180 w = t + insns[t].imm + 1; 181 mark_prune_point(env, t); 182 merge_callee_effects(env, t, w); 183 ret = push_insn(t, w, BRANCH, env); 184 } 185 return ret; 186 } 187 188 struct bpf_iarray *bpf_iarray_realloc(struct bpf_iarray *old, size_t n_elem) 189 { 190 size_t new_size = sizeof(struct bpf_iarray) + n_elem * sizeof(old->items[0]); 191 struct bpf_iarray *new; 192 193 new = kvrealloc(old, new_size, GFP_KERNEL_ACCOUNT); 194 if (!new) { 195 /* this is what callers always want, so simplify the call site */ 196 kvfree(old); 197 return NULL; 198 } 199 200 new->cnt = n_elem; 201 return new; 202 } 203 204 static int copy_insn_array(struct bpf_map *map, u32 start, u32 end, u32 *items) 205 { 206 struct bpf_insn_array_value *value; 207 u32 i; 208 209 for (i = start; i <= end; i++) { 210 value = map->ops->map_lookup_elem(map, &i); 211 /* 212 * map_lookup_elem of an array map will never return an error, 213 * but not checking it makes some static analysers to worry 214 */ 215 if (IS_ERR(value)) 216 return PTR_ERR(value); 217 else if (!value) 218 return -EINVAL; 219 items[i - start] = value->xlated_off; 220 } 221 return 0; 222 } 223 224 static int cmp_ptr_to_u32(const void *a, const void *b) 225 { 226 return *(u32 *)a - *(u32 *)b; 227 } 228 229 static int sort_insn_array_uniq(u32 *items, int cnt) 230 { 231 int unique = 1; 232 int i; 233 234 sort(items, cnt, sizeof(items[0]), cmp_ptr_to_u32, NULL); 235 236 for (i = 1; i < cnt; i++) 237 if (items[i] != items[unique - 1]) 238 items[unique++] = items[i]; 239 240 return unique; 241 } 242 243 /* 244 * sort_unique({map[start], ..., map[end]}) into off 245 */ 246 int bpf_copy_insn_array_uniq(struct bpf_map *map, u32 start, u32 end, u32 *off) 247 { 248 u32 n = end - start + 1; 249 int err; 250 251 err = copy_insn_array(map, start, end, off); 252 if (err) 253 return err; 254 255 return sort_insn_array_uniq(off, n); 256 } 257 258 /* 259 * Copy all unique offsets from the map 260 */ 261 static struct bpf_iarray *jt_from_map(struct bpf_map *map) 262 { 263 struct bpf_iarray *jt; 264 int err; 265 int n; 266 267 jt = bpf_iarray_realloc(NULL, map->max_entries); 268 if (!jt) 269 return ERR_PTR(-ENOMEM); 270 271 n = bpf_copy_insn_array_uniq(map, 0, map->max_entries - 1, jt->items); 272 if (n < 0) { 273 err = n; 274 goto err_free; 275 } 276 if (n == 0) { 277 err = -EINVAL; 278 goto err_free; 279 } 280 jt->cnt = n; 281 return jt; 282 283 err_free: 284 kvfree(jt); 285 return ERR_PTR(err); 286 } 287 288 /* 289 * Collect the jump table of every subprogram that has one, as the combined 290 * table of all maps whose targets land inside that subprogram. All gotox 291 * instructions of a subprogram share the same table, so this is done in a 292 * single pass over the maps rather than once per gotox. 293 */ 294 static int __compute_subprog_jts(struct bpf_verifier_env *env) 295 { 296 struct bpf_subprog_info *subprog; 297 struct bpf_iarray *jt, *jt_cur; 298 struct bpf_map *map; 299 u32 old_cnt; 300 int i; 301 302 for (i = 0; i < env->insn_array_map_cnt; i++) { 303 /* 304 * TODO (when needed): collect only jump tables, not static keys 305 * or maps for indirect calls 306 */ 307 map = env->insn_array_maps[i]; 308 309 jt_cur = jt_from_map(map); 310 if (IS_ERR(jt_cur)) 311 return PTR_ERR(jt_cur); 312 313 subprog = bpf_find_containing_subprog(env, jt_cur->items[0]); 314 if (verifier_bug_if(!subprog, env, "no subprog contains insn %u of an insn array map", 315 jt_cur->items[0])) { 316 kvfree(jt_cur); 317 return -EFAULT; 318 } 319 if (jt_cur->items[jt_cur->cnt - 1] >= (subprog + 1)->start) { 320 verbose(env, "jump table of subprog starting at %u spans multiple subprogs, map id=%d\n", 321 subprog->start, map->id); 322 bpf_diag_program_structure( 323 env, subprog->start, "jump table spans subprograms", 324 "Keep every entry of a jump table inside one subprogram.", 325 "The jump table in map id %d for the subprogram that starts at instruction %u reaches past its end at instruction %u.", 326 map->id, subprog->start, (subprog + 1)->start); 327 kvfree(jt_cur); 328 return -EINVAL; 329 } 330 331 old_cnt = subprog->jt ? subprog->jt->cnt : 0; 332 jt = bpf_iarray_realloc(subprog->jt, old_cnt + jt_cur->cnt); 333 if (!jt) { 334 subprog->jt = NULL; 335 kvfree(jt_cur); 336 return -ENOMEM; 337 } 338 memcpy(jt->items + old_cnt, jt_cur->items, jt_cur->cnt << 2); 339 subprog->jt = jt; 340 341 kvfree(jt_cur); 342 } 343 344 for (i = 0; i < env->subprog_cnt; i++) { 345 jt = env->subprog_info[i].jt; 346 if (jt) 347 jt->cnt = sort_insn_array_uniq(jt->items, jt->cnt); 348 } 349 350 env->cfg.subprog_jts_ready = true; 351 return 0; 352 } 353 354 /* Leave nothing behind on failure. */ 355 static int compute_subprog_jts(struct bpf_verifier_env *env) 356 { 357 int err; 358 359 err = __compute_subprog_jts(env); 360 if (err) 361 bpf_free_subprog_jts(env); 362 return err; 363 } 364 365 void bpf_free_subprog_jts(struct bpf_verifier_env *env) 366 { 367 int i; 368 369 for (i = 0; i < ARRAY_SIZE(env->subprog_info); i++) { 370 kvfree(env->subprog_info[i].jt); 371 env->subprog_info[i].jt = NULL; 372 } 373 env->cfg.subprog_jts_ready = false; 374 } 375 376 static struct bpf_iarray * 377 subprog_jt(int t, struct bpf_verifier_env *env) 378 { 379 struct bpf_subprog_info *subprog; 380 int subprog_start, err; 381 382 if (!env->cfg.subprog_jts_ready) { 383 err = compute_subprog_jts(env); 384 if (err) 385 return ERR_PTR(err); 386 } 387 388 subprog = bpf_find_containing_subprog(env, t); 389 if (verifier_bug_if(!subprog, env, "no subprog contains insn %d", t)) 390 return ERR_PTR(-EFAULT); 391 subprog_start = subprog->start; 392 393 if (!subprog->jt) { 394 verbose(env, "no jump tables found for subprog starting at %u\n", subprog_start); 395 bpf_diag_program_structure( 396 env, t, "missing jump table", 397 "Make sure subprograms containing gotox instructions are accompanied by jump tables referencing these subprograms.", 398 "No jump table was found for the subprogram that starts at instruction %u.", 399 subprog_start); 400 return ERR_PTR(-EINVAL); 401 } 402 403 return subprog->jt; 404 } 405 406 /* "conditional jump with N edges" */ 407 static int visit_gotox_insn(int t, struct bpf_verifier_env *env) 408 { 409 int *insn_stack = env->cfg.insn_stack; 410 int *insn_state = env->cfg.insn_state; 411 bool keep_exploring = false; 412 struct bpf_iarray *jt; 413 int i, w; 414 415 /* 416 * The first visit pushes every target that still needs exploring, and 417 * those are all done by the time this insn is revisited, so there is 418 * nothing left to walk the jump table for. 419 */ 420 if (insn_state[t] & BRANCH) 421 return DONE_EXPLORING; 422 423 jt = subprog_jt(t, env); 424 if (IS_ERR(jt)) 425 return PTR_ERR(jt); 426 427 insn_state[t] |= BRANCH; 428 429 if (check_add_overflow(env->cfg.gotox_edges, jt->cnt, 430 &env->cfg.gotox_edges) || 431 env->cfg.gotox_edges > BPF_MAX_GOTOX_EDGES) { 432 verbose(env, "number of indirect jump edges in the program exceeds %u\n", 433 BPF_MAX_GOTOX_EDGES); 434 bpf_diag_program_structure( 435 env, t, "too many indirect jump edges", 436 "Reduce the number of indirect jumps, or the number of distinct targets they can reach.", 437 "The program has more than %u indirect jump edges in total, counted over every gotox instruction.", 438 BPF_MAX_GOTOX_EDGES); 439 return -E2BIG; 440 } 441 442 mark_prune_point(env, t); 443 for (i = 0; i < jt->cnt; i++) { 444 w = jt->items[i]; 445 if (verifier_bug_if(w < 0 || w >= env->prog->len, env, 446 "indirect jump from insn %d to %d out of range", t, w)) 447 return -EFAULT; 448 449 mark_jmp_point(env, w); 450 mark_jump_target(env, w); 451 452 /* EXPLORED || DISCOVERED */ 453 if (insn_state[w]) 454 continue; 455 456 if (env->cfg.cur_stack >= env->prog->len) 457 return -E2BIG; 458 459 insn_stack[env->cfg.cur_stack++] = w; 460 insn_state[w] |= DISCOVERED; 461 keep_exploring = true; 462 } 463 464 return keep_exploring ? KEEP_EXPLORING : DONE_EXPLORING; 465 } 466 467 /* 468 * Return pointers to functions in the read-only map that ld_imm64 instruction 469 * 't' loads the address of, or of its value, if there are any. 470 */ 471 static struct bpf_func_ptr *insn_func_ptrs(struct bpf_verifier_env *env, int t, u32 *cnt) 472 { 473 struct bpf_insn *insn = &env->prog->insnsi[t]; 474 475 *cnt = 0; 476 if (!env->func_ptr_cnt || !bpf_is_ldimm64(insn)) 477 return NULL; 478 if (insn->src_reg != BPF_PSEUDO_MAP_VALUE && 479 insn->src_reg != BPF_PSEUDO_MAP_IDX_VALUE && 480 insn->src_reg != BPF_PSEUDO_MAP_FD && 481 insn->src_reg != BPF_PSEUDO_MAP_IDX) 482 return NULL; 483 484 return bpf_map_func_ptrs(env, env->used_maps[env->insn_aux_data[t].map_index], cnt); 485 } 486 487 /* 488 * ld_imm64 that loads the address of a map that has pointers to functions 489 * is similar to ld_imm64 with BPF_PSEUDO_FUNC that loads the address of one 490 * function: any of them may be read from the map and called via callx later. 491 * Treat it as a call of all of them. 492 */ 493 static int visit_func_ptrs_insn(int t, struct bpf_verifier_env *env, 494 struct bpf_func_ptr *ptrs, u32 cnt) 495 { 496 int *insn_stack = env->cfg.insn_stack; 497 int *insn_state = env->cfg.insn_state; 498 int ret, w; 499 u32 i; 500 501 ret = push_insn(t, t + 2, FALLTHROUGH, env); 502 if (ret) 503 return ret; 504 505 /* 506 * Explore one function at a time like push_insn() does, so that 507 * DISCOVERED function is a caller of 't' and not the one that waits in 508 * insn_stack[], which merge_callee_effects() relies on. 509 */ 510 for (i = 0; i < cnt; i++) { 511 w = ptrs[i].xlated_off; 512 if (insn_state[w]) 513 continue; 514 515 if (env->cfg.cur_stack >= env->prog->len) 516 return -E2BIG; 517 518 insn_stack[env->cfg.cur_stack++] = w; 519 insn_state[w] = DISCOVERED; 520 return KEEP_EXPLORING; 521 } 522 523 /* all functions are explored, their effects are known */ 524 mark_prune_point(env, t); 525 for (i = 0; i < cnt; i++) { 526 w = ptrs[i].xlated_off; 527 merge_callee_effects(env, t, w); 528 529 /* the same marks as push_insn() leaves on a branch target */ 530 mark_prune_point(env, w); 531 mark_jmp_point(env, w); 532 mark_jump_target(env, w); 533 } 534 return DONE_EXPLORING; 535 } 536 537 /* Visits the instruction at index t and returns one of the following: 538 * < 0 - an error occurred 539 * DONE_EXPLORING - the instruction was fully explored 540 * KEEP_EXPLORING - there is still work to be done before it is fully explored 541 */ 542 static int visit_insn(int t, struct bpf_verifier_env *env) 543 { 544 struct bpf_insn *insns = env->prog->insnsi, *insn = &insns[t]; 545 struct bpf_func_ptr *ptrs; 546 int ret, off, insn_sz; 547 u32 cnt; 548 549 if (bpf_pseudo_func(insn)) 550 return visit_func_call_insn(t, insns, env, true); 551 552 ptrs = insn_func_ptrs(env, t, &cnt); 553 if (ptrs) 554 return visit_func_ptrs_insn(t, env, ptrs, cnt); 555 556 /* All non-branch instructions have a single fall-through edge. */ 557 if (BPF_CLASS(insn->code) != BPF_JMP && 558 BPF_CLASS(insn->code) != BPF_JMP32) { 559 insn_sz = bpf_is_ldimm64(insn) ? 2 : 1; 560 return push_insn(t, t + insn_sz, FALLTHROUGH, env); 561 } 562 563 switch (BPF_OP(insn->code)) { 564 case BPF_EXIT: 565 return DONE_EXPLORING; 566 567 case BPF_CALL: 568 if (bpf_is_async_callback_calling_insn(insn)) 569 /* Mark this call insn as a prune point to trigger 570 * is_state_visited() check before call itself is 571 * processed by __check_func_call(). Otherwise new 572 * async state will be pushed for further exploration. 573 */ 574 mark_prune_point(env, t); 575 /* For functions that invoke callbacks it is not known how many times 576 * callback would be called. Verifier models callback calling functions 577 * by repeatedly visiting callback bodies and returning to origin call 578 * instruction. 579 * In order to stop such iteration verifier needs to identify when a 580 * state identical some state from a previous iteration is reached. 581 * Check below forces creation of checkpoint before callback calling 582 * instruction to allow search for such identical states. 583 */ 584 if (bpf_is_sync_callback_calling_insn(insn)) { 585 mark_calls_callback(env, t); 586 mark_force_checkpoint(env, t); 587 mark_prune_point(env, t); 588 mark_jmp_point(env, t); 589 } 590 if (bpf_helper_call(insn)) { 591 const struct bpf_func_proto *fp; 592 593 ret = bpf_get_helper_proto(env, insn->imm, &fp); 594 /* If called in a non-sleepable context program will be 595 * rejected anyway, so we should end up with precise 596 * sleepable marks on subprogs, except for dead code 597 * elimination. 598 */ 599 if (ret == 0 && fp->might_sleep) 600 mark_subprog_might_sleep(env, t); 601 /* nobody knows yet whether the dynptr is that of an skb */ 602 if (bpf_helper_changes_pkt_data(insn->imm) || 603 insn->imm == BPF_FUNC_dynptr_write) 604 mark_subprog_changes_pkt_data(env, t); 605 } else if (insn->src_reg == BPF_PSEUDO_KFUNC_CALL) { 606 struct bpf_call_arg_meta meta; 607 608 ret = bpf_fetch_kfunc_arg_meta(env, insn->imm, insn->off, &meta); 609 if (ret == 0 && bpf_is_iter_next_kfunc(&meta)) { 610 mark_prune_point(env, t); 611 /* Checking and saving state checkpoints at iter_next() call 612 * is crucial for fast convergence of open-coded iterator loop 613 * logic, so we need to force it. If we don't do that, 614 * is_state_visited() might skip saving a checkpoint, causing 615 * unnecessarily long sequence of not checkpointed 616 * instructions and jumps, leading to exhaustion of jump 617 * history buffer, and potentially other undesired outcomes. 618 * It is expected that with correct open-coded iterators 619 * convergence will happen quickly, so we don't run a risk of 620 * exhausting memory. 621 */ 622 mark_force_checkpoint(env, t); 623 } 624 /* Same as helpers, if called in a non-sleepable context 625 * program will be rejected anyway, so we should end up 626 * with precise sleepable marks on subprogs, except for 627 * dead code elimination. 628 */ 629 if (ret == 0 && bpf_is_kfunc_sleepable(&meta)) 630 mark_subprog_might_sleep(env, t); 631 if (ret == 0 && bpf_is_kfunc_pkt_changing(&meta)) 632 mark_subprog_changes_pkt_data(env, t); 633 if (ret == 0 && bpf_is_throw_kfunc(insn)) 634 mark_subprog_might_throw(env, t); 635 } 636 return visit_func_call_insn(t, insns, env, insn->src_reg == BPF_PSEUDO_CALL); 637 638 case BPF_JA: 639 if (BPF_SRC(insn->code) == BPF_X) 640 return visit_gotox_insn(t, env); 641 642 if (BPF_CLASS(insn->code) == BPF_JMP) 643 off = insn->off; 644 else 645 off = insn->imm; 646 647 /* unconditional jump with single edge */ 648 ret = push_insn(t, t + off + 1, FALLTHROUGH, env); 649 if (ret) 650 return ret; 651 652 mark_prune_point(env, t + off + 1); 653 mark_jmp_point(env, t + off + 1); 654 mark_jump_target(env, t + off + 1); 655 656 return ret; 657 658 default: 659 /* conditional jump with two edges */ 660 mark_prune_point(env, t); 661 if (bpf_is_may_goto_insn(insn)) 662 mark_force_checkpoint(env, t); 663 664 ret = push_insn(t, t + 1, FALLTHROUGH, env); 665 if (ret) 666 return ret; 667 668 return push_insn(t, t + insn->off + 1, BRANCH, env); 669 } 670 } 671 672 /* non-recursive depth-first-search to detect loops in BPF program 673 * loop == back-edge in directed graph 674 */ 675 int bpf_check_cfg(struct bpf_verifier_env *env) 676 { 677 int insn_cnt = env->prog->len; 678 int *insn_stack, *insn_state; 679 int ex_insn_beg, i, ret = 0; 680 681 insn_state = env->cfg.insn_state = kvzalloc_objs(int, insn_cnt, 682 GFP_KERNEL_ACCOUNT); 683 if (!insn_state) 684 return -ENOMEM; 685 686 insn_stack = env->cfg.insn_stack = kvzalloc_objs(int, insn_cnt, 687 GFP_KERNEL_ACCOUNT); 688 if (!insn_stack) { 689 kvfree(insn_state); 690 return -ENOMEM; 691 } 692 693 ex_insn_beg = env->exception_callback_subprog 694 ? env->subprog_info[env->exception_callback_subprog].start 695 : 0; 696 697 insn_state[0] = DISCOVERED; /* mark 1st insn as discovered */ 698 insn_stack[0] = 0; /* 0 is the first instruction */ 699 env->cfg.cur_stack = 1; 700 701 walk_cfg: 702 while (env->cfg.cur_stack > 0) { 703 int t = insn_stack[env->cfg.cur_stack - 1]; 704 705 ret = visit_insn(t, env); 706 switch (ret) { 707 case DONE_EXPLORING: 708 insn_state[t] = EXPLORED; 709 env->cfg.cur_stack--; 710 break; 711 case KEEP_EXPLORING: 712 break; 713 default: 714 if (ret > 0) { 715 verifier_bug(env, "visit_insn internal bug"); 716 ret = -EFAULT; 717 } 718 goto err_free; 719 } 720 } 721 722 if (env->cfg.cur_stack < 0) { 723 verifier_bug(env, "pop stack internal bug"); 724 ret = -EFAULT; 725 goto err_free; 726 } 727 728 if (ex_insn_beg && insn_state[ex_insn_beg] != EXPLORED) { 729 insn_state[ex_insn_beg] = DISCOVERED; 730 insn_stack[0] = ex_insn_beg; 731 env->cfg.cur_stack = 1; 732 goto walk_cfg; 733 } 734 735 for (i = 0; i < insn_cnt; i++) { 736 struct bpf_insn *insn = &env->prog->insnsi[i]; 737 738 if (insn_state[i] != EXPLORED) { 739 verbose(env, "unreachable insn %d\n", i); 740 bpf_diag_program_structure( 741 env, i, "unreachable instruction", 742 "Remove the unreachable instruction or add valid control flow that reaches it.", 743 "Instruction %d is not reachable from the program entry point.", i); 744 ret = -EINVAL; 745 goto err_free; 746 } 747 if (bpf_is_ldimm64(insn)) { 748 if (insn_state[i + 1] != 0) { 749 verbose(env, "jump into the middle of ldimm64 insn %d\n", i); 750 bpf_diag_program_structure( 751 env, i, "jump into ldimm64 immediate", 752 "Target the first instruction of the ldimm64 pair, or restructure the jump target.", 753 "Control flow reaches the second half of the ldimm64 instruction pair that starts at instruction %d.", 754 i); 755 ret = -EINVAL; 756 goto err_free; 757 } 758 i++; /* skip second half of ldimm64 */ 759 } 760 } 761 ret = 0; /* cfg looks good */ 762 env->prog->aux->changes_pkt_data = env->subprog_info[0].changes_pkt_data; 763 env->prog->aux->might_sleep = env->subprog_info[0].might_sleep; 764 765 err_free: 766 kvfree(insn_state); 767 kvfree(insn_stack); 768 env->cfg.insn_state = env->cfg.insn_stack = NULL; 769 return ret; 770 } 771 772 struct dfs_state { 773 u32 traversed:1; 774 u32 next_succ:31; 775 }; 776 777 /* 778 * For each subprogram 'i' fill array env->cfg.insn_subprogram sub-range 779 * [env->subprog_info[i].postorder_start, env->subprog_info[i+1].postorder_start) 780 * with indices of 'i' instructions in postorder. 781 */ 782 int bpf_compute_postorder(struct bpf_verifier_env *env) 783 { 784 int *stack = NULL, *postorder = NULL, *postorder_nums = NULL; 785 int subprog_idx, stack_sz, cur, s, cur_postorder, start; 786 struct dfs_state *state = NULL; 787 struct bpf_iarray *succ = NULL; 788 789 postorder_nums = kvzalloc_objs(int, env->prog->len, GFP_KERNEL_ACCOUNT); 790 postorder = kvzalloc_objs(int, env->prog->len, GFP_KERNEL_ACCOUNT); 791 stack = kvzalloc_objs(int, env->prog->len, GFP_KERNEL_ACCOUNT); 792 state = kvzalloc_objs(struct dfs_state, env->prog->len, GFP_KERNEL_ACCOUNT); 793 if (!postorder_nums || !postorder || !stack || !state) { 794 kvfree(postorder_nums); 795 kvfree(postorder); 796 kvfree(stack); 797 kvfree(state); 798 return -ENOMEM; 799 } 800 cur_postorder = 0; 801 for (subprog_idx = 0; subprog_idx < env->subprog_cnt; subprog_idx++) { 802 start = env->subprog_info[subprog_idx].start; 803 env->subprog_info[subprog_idx].postorder_start = cur_postorder; 804 stack[0] = start; 805 stack_sz = 1; 806 state[start].traversed = true; 807 do { 808 cur = stack[stack_sz - 1]; 809 succ = bpf_insn_successors(env, cur); 810 if (state[cur].next_succ == succ->cnt) { 811 postorder_nums[cur] = cur_postorder; 812 postorder[cur_postorder] = cur; 813 cur_postorder++; 814 stack_sz--; 815 continue; 816 } 817 s = succ->items[state[cur].next_succ]; 818 if (!state[s].traversed) { 819 state[s].traversed = true; 820 state[s].next_succ = 0; 821 stack[stack_sz] = s; 822 stack_sz++; 823 continue; 824 } 825 state[cur].next_succ++; 826 } while (stack_sz); 827 } 828 env->subprog_info[subprog_idx].postorder_start = cur_postorder; 829 env->cfg.postorder_nums = postorder_nums; 830 env->cfg.insn_postorder = postorder; 831 env->cfg.cur_postorder = cur_postorder; 832 kvfree(stack); 833 kvfree(state); 834 return 0; 835 } 836 837 /* 838 * Compute strongly connected components (SCCs) on the CFG. 839 * Assign an SCC number to each instruction, recorded in env->insn_aux[*].scc. 840 * If instruction is a sole member of its SCC and there are no self edges, 841 * assign it SCC number of zero. 842 * Uses a non-recursive adaptation of Tarjan's algorithm for SCC computation. 843 */ 844 int bpf_compute_scc(struct bpf_verifier_env *env) 845 { 846 const u32 NOT_ON_STACK = U32_MAX; 847 848 struct bpf_insn_aux_data *aux = env->insn_aux_data; 849 const u32 insn_cnt = env->prog->len; 850 int stack_sz, dfs_sz, err = 0; 851 u32 *stack, *pre, *low, *dfs, *dfs_pos; 852 u32 i, j, t, w; 853 u32 next_preorder_num; 854 u32 next_scc_id; 855 bool assign_scc; 856 struct bpf_iarray *succ; 857 858 next_preorder_num = 1; 859 next_scc_id = 1; 860 /* 861 * - 'stack' accumulates vertices in DFS order, see invariant comment below; 862 * - 'pre[t] == p' => preorder number of vertex 't' is 'p'; 863 * - 'low[t] == n' => smallest preorder number of the vertex reachable from 't' is 'n'; 864 * - 'dfs' DFS traversal stack, used to emulate explicit recursion; 865 * - 'dfs_pos[k] == j' => the frame 'dfs[k]' resumes visiting its 866 * successors at index 'j'. 867 */ 868 stack = kvcalloc(insn_cnt, sizeof(int), GFP_KERNEL_ACCOUNT); 869 pre = kvcalloc(insn_cnt, sizeof(int), GFP_KERNEL_ACCOUNT); 870 low = kvcalloc(insn_cnt, sizeof(int), GFP_KERNEL_ACCOUNT); 871 dfs = kvcalloc(insn_cnt, sizeof(*dfs), GFP_KERNEL_ACCOUNT); 872 dfs_pos = kvcalloc(insn_cnt, sizeof(*dfs_pos), GFP_KERNEL_ACCOUNT); 873 if (!stack || !pre || !low || !dfs || !dfs_pos) { 874 err = -ENOMEM; 875 goto exit; 876 } 877 /* 878 * References: 879 * [1] R. Tarjan "Depth-First Search and Linear Graph Algorithms" 880 * [2] D. J. Pearce "A Space-Efficient Algorithm for Finding Strongly Connected Components" 881 * 882 * The algorithm maintains the following invariant: 883 * - suppose there is a path 'u' ~> 'v', such that 'pre[v] < pre[u]'; 884 * - then, vertex 'u' remains on stack while vertex 'v' is on stack. 885 * 886 * Consequently: 887 * - If 'low[v] < pre[v]', there is a path from 'v' to some vertex 'u', 888 * such that 'pre[u] == low[v]'; vertex 'u' is currently on the stack, 889 * and thus there is an SCC (loop) containing both 'u' and 'v'. 890 * - If 'low[v] == pre[v]', loops containing 'v' have been explored, 891 * and 'v' can be considered the root of some SCC. 892 * 893 * Here is a pseudo-code for an explicitly recursive version of the algorithm: 894 * 895 * NOT_ON_STACK = insn_cnt + 1 896 * pre = [0] * insn_cnt 897 * low = [0] * insn_cnt 898 * scc = [0] * insn_cnt 899 * stack = [] 900 * 901 * next_preorder_num = 1 902 * next_scc_id = 1 903 * 904 * def recur(w): 905 * nonlocal next_preorder_num 906 * nonlocal next_scc_id 907 * 908 * pre[w] = next_preorder_num 909 * low[w] = next_preorder_num 910 * next_preorder_num += 1 911 * stack.append(w) 912 * for s in successors(w): 913 * # Note: for classic algorithm the block below should look as: 914 * # 915 * # if pre[s] == 0: 916 * # recur(s) 917 * # low[w] = min(low[w], low[s]) 918 * # elif low[s] != NOT_ON_STACK: 919 * # low[w] = min(low[w], pre[s]) 920 * # 921 * # But replacing both 'min' instructions with 'low[w] = min(low[w], low[s])' 922 * # does not break the invariant and makes iterative version of the algorithm 923 * # simpler. See 'Algorithm #3' from [2]. 924 * 925 * # 's' not yet visited 926 * if pre[s] == 0: 927 * recur(s) 928 * # if 's' is on stack, pick lowest reachable preorder number from it; 929 * # if 's' is not on stack 'low[s] == NOT_ON_STACK > low[w]', 930 * # so 'min' would be a noop. 931 * low[w] = min(low[w], low[s]) 932 * 933 * if low[w] == pre[w]: 934 * # 'w' is the root of an SCC, pop all vertices 935 * # below 'w' on stack and assign same SCC to them. 936 * while True: 937 * t = stack.pop() 938 * low[t] = NOT_ON_STACK 939 * scc[t] = next_scc_id 940 * if t == w: 941 * break 942 * next_scc_id += 1 943 * 944 * for i in range(0, insn_cnt): 945 * if pre[i] == 0: 946 * recur(i) 947 * 948 * Below implementation replaces explicit recursion with array 'dfs'. 949 */ 950 for (i = 0; i < insn_cnt; i++) { 951 if (pre[i]) 952 continue; 953 stack_sz = 0; 954 dfs_sz = 1; 955 dfs[0] = i; 956 dfs_pos[0] = 0; 957 dfs_continue: 958 while (dfs_sz) { 959 w = dfs[dfs_sz - 1]; 960 if (pre[w] == 0) { 961 low[w] = next_preorder_num; 962 pre[w] = next_preorder_num; 963 next_preorder_num++; 964 stack[stack_sz++] = w; 965 } 966 /* Visit remaining 'w' successors */ 967 succ = bpf_insn_successors(env, w); 968 for (j = dfs_pos[dfs_sz - 1]; j < succ->cnt; ++j) { 969 if (pre[succ->items[j]]) { 970 low[w] = min(low[w], low[succ->items[j]]); 971 } else { 972 /* 973 * Once DFS for succ->items[j] is complete, 974 * pre[succ->items[j]] is non-zero, hence 975 * resuming at 'j' allows to follow the 976 * low[w] = min(...) update branch above. 977 */ 978 dfs_pos[dfs_sz - 1] = j; 979 dfs_pos[dfs_sz] = 0; 980 dfs[dfs_sz] = succ->items[j]; 981 dfs_sz++; 982 goto dfs_continue; 983 } 984 } 985 /* 986 * Preserve the invariant: if some vertex above in the stack 987 * is reachable from 'w', keep 'w' on the stack. 988 */ 989 if (low[w] < pre[w]) { 990 dfs_sz--; 991 goto dfs_continue; 992 } 993 /* 994 * Assign SCC number only if component has two or more elements, 995 * or if component has a self reference, or if instruction is a 996 * callback calling function (implicit loop). 997 */ 998 assign_scc = stack[stack_sz - 1] != w; /* two or more elements? */ 999 for (j = 0; j < succ->cnt; ++j) { /* self reference? */ 1000 if (succ->items[j] == w) { 1001 assign_scc = true; 1002 break; 1003 } 1004 } 1005 if (bpf_calls_callback(env, w)) /* implicit loop? */ 1006 assign_scc = true; 1007 /* Pop component elements from stack */ 1008 do { 1009 t = stack[--stack_sz]; 1010 low[t] = NOT_ON_STACK; 1011 if (assign_scc) 1012 aux[t].scc = next_scc_id; 1013 } while (t != w); 1014 if (assign_scc) 1015 next_scc_id++; 1016 dfs_sz--; 1017 } 1018 } 1019 env->scc_info = kvzalloc_objs(*env->scc_info, next_scc_id, 1020 GFP_KERNEL_ACCOUNT); 1021 if (!env->scc_info) { 1022 err = -ENOMEM; 1023 goto exit; 1024 } 1025 env->scc_cnt = next_scc_id; 1026 exit: 1027 kvfree(stack); 1028 kvfree(pre); 1029 kvfree(low); 1030 kvfree(dfs); 1031 kvfree(dfs_pos); 1032 return err; 1033 } 1034