Lines Matching +full:1 +full:w
13 * 1 procedure DFS-iterative(G,v):
24 * 12 w <- G.adjacentVertex(t,e)
25 * 13 if vertex w is not discovered and not explored
27 * 15 label w as discovered
28 * 16 S.push(w)
30 * 18 else if vertex w is discovered
33 * 21 // vertex w is explored
48 FALLTHROUGH = 1,
77 * 'w' is a callee entry point.
78 * Eventually this function would be called when env->cfg.insn_state[w] == EXPLORED.
82 static void merge_callee_effects(struct bpf_verifier_env *env, int t, int w) in merge_callee_effects() argument
87 callee = bpf_find_containing_subprog(env, w); in merge_callee_effects()
95 KEEP_EXPLORING = 1,
98 /* t, w, e - match pseudo-code above:
100 * w - next instruction
103 static int push_insn(int t, int w, int e, struct bpf_verifier_env *env) in push_insn() argument
114 if (w < 0 || w >= env->prog->len) { in push_insn()
116 verbose(env, "jump out of range from insn %d to %d\n", t, w); in push_insn()
120 t, w, env->prog->len - 1); in push_insn()
126 mark_prune_point(env, w); in push_insn()
127 mark_jmp_point(env, w); in push_insn()
130 if (insn_state[w] == 0) { in push_insn()
133 insn_state[w] = DISCOVERED; in push_insn()
136 insn_stack[env->cfg.cur_stack++] = w; in push_insn()
138 } else if ((insn_state[w] & 0xF0) == DISCOVERED) { in push_insn()
142 verbose_linfo(env, w, "%d: ", w); in push_insn()
143 verbose(env, "back-edge from insn %d to %d\n", t, w); in push_insn()
148 t, w); in push_insn()
150 } else if (insn_state[w] == EXPLORED) { in push_insn()
165 int w; in visit_func_call_insn() local
167 insn_sz = bpf_is_ldimm64(&insns[t]) ? 2 : 1; in visit_func_call_insn()
177 w = t + insns[t].imm + 1; in visit_func_call_insn()
179 merge_callee_effects(env, t, w); in visit_func_call_insn()
180 ret = push_insn(t, w, BRANCH, env); in visit_func_call_insn()
228 int unique = 1; in sort_insn_array_uniq()
233 for (i = 1; i < cnt; i++) in sort_insn_array_uniq()
234 if (items[i] != items[unique - 1]) in sort_insn_array_uniq()
245 u32 n = end - start + 1; in bpf_copy_insn_array_uniq()
268 n = bpf_copy_insn_array_uniq(map, 0, map->max_entries - 1, jt->items); in jt_from_map()
351 subprog_end = (subprog + 1)->start; in create_jt()
381 int i, w; in visit_gotox_insn() local
394 w = jt->items[i]; in visit_gotox_insn()
395 if (w < 0 || w >= env->prog->len) { in visit_gotox_insn()
396 verbose(env, "indirect jump out of range from insn %d to %d\n", t, w); in visit_gotox_insn()
401 t, w, env->prog->len - 1); in visit_gotox_insn()
405 mark_jmp_point(env, w); in visit_gotox_insn()
408 if (insn_state[w]) in visit_gotox_insn()
414 insn_stack[env->cfg.cur_stack++] = w; in visit_gotox_insn()
415 insn_state[w] |= DISCOVERED; in visit_gotox_insn()
440 jt->items[0] = t + 1; in visit_abnormal_return_insn()
441 jt->items[1] = subprog->exit_idx; in visit_abnormal_return_insn()
469 insn_sz = bpf_is_ldimm64(insn) ? 2 : 1; in visit_insn()
561 ret = push_insn(t, t + off + 1, FALLTHROUGH, env); in visit_insn()
565 mark_prune_point(env, t + off + 1); in visit_insn()
566 mark_jmp_point(env, t + off + 1); in visit_insn()
576 ret = push_insn(t, t + 1, FALLTHROUGH, env); in visit_insn()
580 return push_insn(t, t + insn->off + 1, BRANCH, env); in visit_insn()
609 insn_state[0] = DISCOVERED; /* mark 1st insn as discovered */ in bpf_check_cfg()
611 env->cfg.cur_stack = 1; in bpf_check_cfg()
615 int t = insn_stack[env->cfg.cur_stack - 1]; in bpf_check_cfg()
643 env->cfg.cur_stack = 1; in bpf_check_cfg()
660 if (insn_state[i + 1] != 0) { in bpf_check_cfg()
686 * [env->subprog_info[i].postorder_start, env->subprog_info[i+1].postorder_start)
708 stack_sz = 1; in bpf_compute_postorder()
710 top = stack[stack_sz - 1]; in bpf_compute_postorder()
750 u32 i, j, t, w; in bpf_compute_scc() local
756 next_preorder_num = 1; in bpf_compute_scc()
757 next_scc_id = 1; in bpf_compute_scc()
774 * [1] R. Tarjan "Depth-First Search and Linear Graph Algorithms" in bpf_compute_scc()
790 * NOT_ON_STACK = insn_cnt + 1 in bpf_compute_scc()
796 * next_preorder_num = 1 in bpf_compute_scc()
797 * next_scc_id = 1 in bpf_compute_scc()
799 * def recur(w): in bpf_compute_scc()
803 * pre[w] = next_preorder_num in bpf_compute_scc()
804 * low[w] = next_preorder_num in bpf_compute_scc()
805 * next_preorder_num += 1 in bpf_compute_scc()
806 * stack.append(w) in bpf_compute_scc()
807 * for s in successors(w): in bpf_compute_scc()
812 * # low[w] = min(low[w], low[s]) in bpf_compute_scc()
814 * # low[w] = min(low[w], pre[s]) in bpf_compute_scc()
816 * # But replacing both 'min' instructions with 'low[w] = min(low[w], low[s])' in bpf_compute_scc()
824 * # if 's' is not on stack 'low[s] == NOT_ON_STACK > low[w]', in bpf_compute_scc()
826 * low[w] = min(low[w], low[s]) in bpf_compute_scc()
828 * if low[w] == pre[w]: in bpf_compute_scc()
829 * # 'w' is the root of an SCC, pop all vertices in bpf_compute_scc()
830 * # below 'w' on stack and assign same SCC to them. in bpf_compute_scc()
835 * if t == w: in bpf_compute_scc()
837 * next_scc_id += 1 in bpf_compute_scc()
849 dfs_sz = 1; in bpf_compute_scc()
853 w = dfs[dfs_sz - 1]; in bpf_compute_scc()
854 if (pre[w] == 0) { in bpf_compute_scc()
855 low[w] = next_preorder_num; in bpf_compute_scc()
856 pre[w] = next_preorder_num; in bpf_compute_scc()
858 stack[stack_sz++] = w; in bpf_compute_scc()
860 /* Visit 'w' successors */ in bpf_compute_scc()
861 succ = bpf_insn_successors(env, w); in bpf_compute_scc()
864 low[w] = min(low[w], low[succ->items[j]]); in bpf_compute_scc()
872 * is reachable from 'w', keep 'w' on the stack. in bpf_compute_scc()
874 if (low[w] < pre[w]) { in bpf_compute_scc()
883 assign_scc = stack[stack_sz - 1] != w; /* two or more elements? */ in bpf_compute_scc()
885 if (succ->items[j] == w) { in bpf_compute_scc()
890 if (bpf_calls_callback(env, w)) /* implicit loop? */ in bpf_compute_scc()
898 } while (t != w); in bpf_compute_scc()