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 if (bpf_helper_changes_pkt_data(insn->imm)) 602 mark_subprog_changes_pkt_data(env, t); 603 } else if (insn->src_reg == BPF_PSEUDO_KFUNC_CALL) { 604 struct bpf_call_arg_meta meta; 605 606 ret = bpf_fetch_kfunc_arg_meta(env, insn->imm, insn->off, &meta); 607 if (ret == 0 && bpf_is_iter_next_kfunc(&meta)) { 608 mark_prune_point(env, t); 609 /* Checking and saving state checkpoints at iter_next() call 610 * is crucial for fast convergence of open-coded iterator loop 611 * logic, so we need to force it. If we don't do that, 612 * is_state_visited() might skip saving a checkpoint, causing 613 * unnecessarily long sequence of not checkpointed 614 * instructions and jumps, leading to exhaustion of jump 615 * history buffer, and potentially other undesired outcomes. 616 * It is expected that with correct open-coded iterators 617 * convergence will happen quickly, so we don't run a risk of 618 * exhausting memory. 619 */ 620 mark_force_checkpoint(env, t); 621 } 622 /* Same as helpers, if called in a non-sleepable context 623 * program will be rejected anyway, so we should end up 624 * with precise sleepable marks on subprogs, except for 625 * dead code elimination. 626 */ 627 if (ret == 0 && bpf_is_kfunc_sleepable(&meta)) 628 mark_subprog_might_sleep(env, t); 629 if (ret == 0 && bpf_is_kfunc_pkt_changing(&meta)) 630 mark_subprog_changes_pkt_data(env, t); 631 if (ret == 0 && bpf_is_throw_kfunc(insn)) 632 mark_subprog_might_throw(env, t); 633 } 634 return visit_func_call_insn(t, insns, env, insn->src_reg == BPF_PSEUDO_CALL); 635 636 case BPF_JA: 637 if (BPF_SRC(insn->code) == BPF_X) 638 return visit_gotox_insn(t, env); 639 640 if (BPF_CLASS(insn->code) == BPF_JMP) 641 off = insn->off; 642 else 643 off = insn->imm; 644 645 /* unconditional jump with single edge */ 646 ret = push_insn(t, t + off + 1, FALLTHROUGH, env); 647 if (ret) 648 return ret; 649 650 mark_prune_point(env, t + off + 1); 651 mark_jmp_point(env, t + off + 1); 652 mark_jump_target(env, t + off + 1); 653 654 return ret; 655 656 default: 657 /* conditional jump with two edges */ 658 mark_prune_point(env, t); 659 if (bpf_is_may_goto_insn(insn)) 660 mark_force_checkpoint(env, t); 661 662 ret = push_insn(t, t + 1, FALLTHROUGH, env); 663 if (ret) 664 return ret; 665 666 return push_insn(t, t + insn->off + 1, BRANCH, env); 667 } 668 } 669 670 /* non-recursive depth-first-search to detect loops in BPF program 671 * loop == back-edge in directed graph 672 */ 673 int bpf_check_cfg(struct bpf_verifier_env *env) 674 { 675 int insn_cnt = env->prog->len; 676 int *insn_stack, *insn_state; 677 int ex_insn_beg, i, ret = 0; 678 679 insn_state = env->cfg.insn_state = kvzalloc_objs(int, insn_cnt, 680 GFP_KERNEL_ACCOUNT); 681 if (!insn_state) 682 return -ENOMEM; 683 684 insn_stack = env->cfg.insn_stack = kvzalloc_objs(int, insn_cnt, 685 GFP_KERNEL_ACCOUNT); 686 if (!insn_stack) { 687 kvfree(insn_state); 688 return -ENOMEM; 689 } 690 691 ex_insn_beg = env->exception_callback_subprog 692 ? env->subprog_info[env->exception_callback_subprog].start 693 : 0; 694 695 insn_state[0] = DISCOVERED; /* mark 1st insn as discovered */ 696 insn_stack[0] = 0; /* 0 is the first instruction */ 697 env->cfg.cur_stack = 1; 698 699 walk_cfg: 700 while (env->cfg.cur_stack > 0) { 701 int t = insn_stack[env->cfg.cur_stack - 1]; 702 703 ret = visit_insn(t, env); 704 switch (ret) { 705 case DONE_EXPLORING: 706 insn_state[t] = EXPLORED; 707 env->cfg.cur_stack--; 708 break; 709 case KEEP_EXPLORING: 710 break; 711 default: 712 if (ret > 0) { 713 verifier_bug(env, "visit_insn internal bug"); 714 ret = -EFAULT; 715 } 716 goto err_free; 717 } 718 } 719 720 if (env->cfg.cur_stack < 0) { 721 verifier_bug(env, "pop stack internal bug"); 722 ret = -EFAULT; 723 goto err_free; 724 } 725 726 if (ex_insn_beg && insn_state[ex_insn_beg] != EXPLORED) { 727 insn_state[ex_insn_beg] = DISCOVERED; 728 insn_stack[0] = ex_insn_beg; 729 env->cfg.cur_stack = 1; 730 goto walk_cfg; 731 } 732 733 for (i = 0; i < insn_cnt; i++) { 734 struct bpf_insn *insn = &env->prog->insnsi[i]; 735 736 if (insn_state[i] != EXPLORED) { 737 verbose(env, "unreachable insn %d\n", i); 738 bpf_diag_program_structure( 739 env, i, "unreachable instruction", 740 "Remove the unreachable instruction or add valid control flow that reaches it.", 741 "Instruction %d is not reachable from the program entry point.", i); 742 ret = -EINVAL; 743 goto err_free; 744 } 745 if (bpf_is_ldimm64(insn)) { 746 if (insn_state[i + 1] != 0) { 747 verbose(env, "jump into the middle of ldimm64 insn %d\n", i); 748 bpf_diag_program_structure( 749 env, i, "jump into ldimm64 immediate", 750 "Target the first instruction of the ldimm64 pair, or restructure the jump target.", 751 "Control flow reaches the second half of the ldimm64 instruction pair that starts at instruction %d.", 752 i); 753 ret = -EINVAL; 754 goto err_free; 755 } 756 i++; /* skip second half of ldimm64 */ 757 } 758 } 759 ret = 0; /* cfg looks good */ 760 env->prog->aux->changes_pkt_data = env->subprog_info[0].changes_pkt_data; 761 env->prog->aux->might_sleep = env->subprog_info[0].might_sleep; 762 763 err_free: 764 kvfree(insn_state); 765 kvfree(insn_stack); 766 env->cfg.insn_state = env->cfg.insn_stack = NULL; 767 return ret; 768 } 769 770 struct dfs_state { 771 u32 traversed:1; 772 u32 next_succ:31; 773 }; 774 775 /* 776 * For each subprogram 'i' fill array env->cfg.insn_subprogram sub-range 777 * [env->subprog_info[i].postorder_start, env->subprog_info[i+1].postorder_start) 778 * with indices of 'i' instructions in postorder. 779 */ 780 int bpf_compute_postorder(struct bpf_verifier_env *env) 781 { 782 int *stack = NULL, *postorder = NULL, *postorder_nums = NULL; 783 int subprog_idx, stack_sz, cur, s, cur_postorder, start; 784 struct dfs_state *state = NULL; 785 struct bpf_iarray *succ = NULL; 786 787 postorder_nums = kvzalloc_objs(int, env->prog->len, GFP_KERNEL_ACCOUNT); 788 postorder = kvzalloc_objs(int, env->prog->len, GFP_KERNEL_ACCOUNT); 789 stack = kvzalloc_objs(int, env->prog->len, GFP_KERNEL_ACCOUNT); 790 state = kvzalloc_objs(struct dfs_state, env->prog->len, GFP_KERNEL_ACCOUNT); 791 if (!postorder_nums || !postorder || !stack || !state) { 792 kvfree(postorder_nums); 793 kvfree(postorder); 794 kvfree(stack); 795 kvfree(state); 796 return -ENOMEM; 797 } 798 cur_postorder = 0; 799 for (subprog_idx = 0; subprog_idx < env->subprog_cnt; subprog_idx++) { 800 start = env->subprog_info[subprog_idx].start; 801 env->subprog_info[subprog_idx].postorder_start = cur_postorder; 802 stack[0] = start; 803 stack_sz = 1; 804 state[start].traversed = true; 805 do { 806 cur = stack[stack_sz - 1]; 807 succ = bpf_insn_successors(env, cur); 808 if (state[cur].next_succ == succ->cnt) { 809 postorder_nums[cur] = cur_postorder; 810 postorder[cur_postorder] = cur; 811 cur_postorder++; 812 stack_sz--; 813 continue; 814 } 815 s = succ->items[state[cur].next_succ]; 816 if (!state[s].traversed) { 817 state[s].traversed = true; 818 state[s].next_succ = 0; 819 stack[stack_sz] = s; 820 stack_sz++; 821 continue; 822 } 823 state[cur].next_succ++; 824 } while (stack_sz); 825 } 826 env->subprog_info[subprog_idx].postorder_start = cur_postorder; 827 env->cfg.postorder_nums = postorder_nums; 828 env->cfg.insn_postorder = postorder; 829 env->cfg.cur_postorder = cur_postorder; 830 kvfree(stack); 831 kvfree(state); 832 return 0; 833 } 834 835 /* 836 * Compute strongly connected components (SCCs) on the CFG. 837 * Assign an SCC number to each instruction, recorded in env->insn_aux[*].scc. 838 * If instruction is a sole member of its SCC and there are no self edges, 839 * assign it SCC number of zero. 840 * Uses a non-recursive adaptation of Tarjan's algorithm for SCC computation. 841 */ 842 int bpf_compute_scc(struct bpf_verifier_env *env) 843 { 844 const u32 NOT_ON_STACK = U32_MAX; 845 846 struct bpf_insn_aux_data *aux = env->insn_aux_data; 847 const u32 insn_cnt = env->prog->len; 848 int stack_sz, dfs_sz, err = 0; 849 u32 *stack, *pre, *low, *dfs, *dfs_pos; 850 u32 i, j, t, w; 851 u32 next_preorder_num; 852 u32 next_scc_id; 853 bool assign_scc; 854 struct bpf_iarray *succ; 855 856 next_preorder_num = 1; 857 next_scc_id = 1; 858 /* 859 * - 'stack' accumulates vertices in DFS order, see invariant comment below; 860 * - 'pre[t] == p' => preorder number of vertex 't' is 'p'; 861 * - 'low[t] == n' => smallest preorder number of the vertex reachable from 't' is 'n'; 862 * - 'dfs' DFS traversal stack, used to emulate explicit recursion; 863 * - 'dfs_pos[k] == j' => the frame 'dfs[k]' resumes visiting its 864 * successors at index 'j'. 865 */ 866 stack = kvcalloc(insn_cnt, sizeof(int), GFP_KERNEL_ACCOUNT); 867 pre = kvcalloc(insn_cnt, sizeof(int), GFP_KERNEL_ACCOUNT); 868 low = kvcalloc(insn_cnt, sizeof(int), GFP_KERNEL_ACCOUNT); 869 dfs = kvcalloc(insn_cnt, sizeof(*dfs), GFP_KERNEL_ACCOUNT); 870 dfs_pos = kvcalloc(insn_cnt, sizeof(*dfs_pos), GFP_KERNEL_ACCOUNT); 871 if (!stack || !pre || !low || !dfs || !dfs_pos) { 872 err = -ENOMEM; 873 goto exit; 874 } 875 /* 876 * References: 877 * [1] R. Tarjan "Depth-First Search and Linear Graph Algorithms" 878 * [2] D. J. Pearce "A Space-Efficient Algorithm for Finding Strongly Connected Components" 879 * 880 * The algorithm maintains the following invariant: 881 * - suppose there is a path 'u' ~> 'v', such that 'pre[v] < pre[u]'; 882 * - then, vertex 'u' remains on stack while vertex 'v' is on stack. 883 * 884 * Consequently: 885 * - If 'low[v] < pre[v]', there is a path from 'v' to some vertex 'u', 886 * such that 'pre[u] == low[v]'; vertex 'u' is currently on the stack, 887 * and thus there is an SCC (loop) containing both 'u' and 'v'. 888 * - If 'low[v] == pre[v]', loops containing 'v' have been explored, 889 * and 'v' can be considered the root of some SCC. 890 * 891 * Here is a pseudo-code for an explicitly recursive version of the algorithm: 892 * 893 * NOT_ON_STACK = insn_cnt + 1 894 * pre = [0] * insn_cnt 895 * low = [0] * insn_cnt 896 * scc = [0] * insn_cnt 897 * stack = [] 898 * 899 * next_preorder_num = 1 900 * next_scc_id = 1 901 * 902 * def recur(w): 903 * nonlocal next_preorder_num 904 * nonlocal next_scc_id 905 * 906 * pre[w] = next_preorder_num 907 * low[w] = next_preorder_num 908 * next_preorder_num += 1 909 * stack.append(w) 910 * for s in successors(w): 911 * # Note: for classic algorithm the block below should look as: 912 * # 913 * # if pre[s] == 0: 914 * # recur(s) 915 * # low[w] = min(low[w], low[s]) 916 * # elif low[s] != NOT_ON_STACK: 917 * # low[w] = min(low[w], pre[s]) 918 * # 919 * # But replacing both 'min' instructions with 'low[w] = min(low[w], low[s])' 920 * # does not break the invariant and makes iterative version of the algorithm 921 * # simpler. See 'Algorithm #3' from [2]. 922 * 923 * # 's' not yet visited 924 * if pre[s] == 0: 925 * recur(s) 926 * # if 's' is on stack, pick lowest reachable preorder number from it; 927 * # if 's' is not on stack 'low[s] == NOT_ON_STACK > low[w]', 928 * # so 'min' would be a noop. 929 * low[w] = min(low[w], low[s]) 930 * 931 * if low[w] == pre[w]: 932 * # 'w' is the root of an SCC, pop all vertices 933 * # below 'w' on stack and assign same SCC to them. 934 * while True: 935 * t = stack.pop() 936 * low[t] = NOT_ON_STACK 937 * scc[t] = next_scc_id 938 * if t == w: 939 * break 940 * next_scc_id += 1 941 * 942 * for i in range(0, insn_cnt): 943 * if pre[i] == 0: 944 * recur(i) 945 * 946 * Below implementation replaces explicit recursion with array 'dfs'. 947 */ 948 for (i = 0; i < insn_cnt; i++) { 949 if (pre[i]) 950 continue; 951 stack_sz = 0; 952 dfs_sz = 1; 953 dfs[0] = i; 954 dfs_pos[0] = 0; 955 dfs_continue: 956 while (dfs_sz) { 957 w = dfs[dfs_sz - 1]; 958 if (pre[w] == 0) { 959 low[w] = next_preorder_num; 960 pre[w] = next_preorder_num; 961 next_preorder_num++; 962 stack[stack_sz++] = w; 963 } 964 /* Visit remaining 'w' successors */ 965 succ = bpf_insn_successors(env, w); 966 for (j = dfs_pos[dfs_sz - 1]; j < succ->cnt; ++j) { 967 if (pre[succ->items[j]]) { 968 low[w] = min(low[w], low[succ->items[j]]); 969 } else { 970 /* 971 * Once DFS for succ->items[j] is complete, 972 * pre[succ->items[j]] is non-zero, hence 973 * resuming at 'j' allows to follow the 974 * low[w] = min(...) update branch above. 975 */ 976 dfs_pos[dfs_sz - 1] = j; 977 dfs_pos[dfs_sz] = 0; 978 dfs[dfs_sz] = succ->items[j]; 979 dfs_sz++; 980 goto dfs_continue; 981 } 982 } 983 /* 984 * Preserve the invariant: if some vertex above in the stack 985 * is reachable from 'w', keep 'w' on the stack. 986 */ 987 if (low[w] < pre[w]) { 988 dfs_sz--; 989 goto dfs_continue; 990 } 991 /* 992 * Assign SCC number only if component has two or more elements, 993 * or if component has a self reference, or if instruction is a 994 * callback calling function (implicit loop). 995 */ 996 assign_scc = stack[stack_sz - 1] != w; /* two or more elements? */ 997 for (j = 0; j < succ->cnt; ++j) { /* self reference? */ 998 if (succ->items[j] == w) { 999 assign_scc = true; 1000 break; 1001 } 1002 } 1003 if (bpf_calls_callback(env, w)) /* implicit loop? */ 1004 assign_scc = true; 1005 /* Pop component elements from stack */ 1006 do { 1007 t = stack[--stack_sz]; 1008 low[t] = NOT_ON_STACK; 1009 if (assign_scc) 1010 aux[t].scc = next_scc_id; 1011 } while (t != w); 1012 if (assign_scc) 1013 next_scc_id++; 1014 dfs_sz--; 1015 } 1016 } 1017 env->scc_info = kvzalloc_objs(*env->scc_info, next_scc_id, 1018 GFP_KERNEL_ACCOUNT); 1019 if (!env->scc_info) { 1020 err = -ENOMEM; 1021 goto exit; 1022 } 1023 env->scc_cnt = next_scc_id; 1024 exit: 1025 kvfree(stack); 1026 kvfree(pre); 1027 kvfree(low); 1028 kvfree(dfs); 1029 kvfree(dfs_pos); 1030 return err; 1031 } 1032