projects/linux·blob master · refs

920 lines · 26.1 KiB

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
45enum {
46 DISCOVERED = 0x10,
47 EXPLORED = 0x20,
48 FALLTHROUGH = 1,
49 BRANCH = 2,
50};
51
52static 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
60static 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
68static 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 */
82static 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
93enum {
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 */
103static 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
161static 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
186struct 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
202static 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
222static int cmp_ptr_to_u32(const void *a, const void *b)
223{
224 return *(u32 *)a - *(u32 *)b;
225}
226
227static 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 */
244int 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 */
259static 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
281err_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 */
290static 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
342static struct bpf_iarray *
343create_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" */
376static 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 */
429static 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 */
453static 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 */
590int 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
616walk_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
680err_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 */
692int 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 */
745int 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;
854dfs_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;
914exit:
915 kvfree(stack);
916 kvfree(pre);
917 kvfree(low);
918 kvfree(dfs);
919 return err;
920}