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