* [RFC PATCH v3 bpf-next 1/5] bpf/verifier: store subprog info in struct bpf_subprog_info
2018-04-06 17:11 [RFC PATCH v3 bpf-next 0/5] bpf/verifier: subprog/func_call simplifications Edward Cree
@ 2018-04-06 17:13 ` Edward Cree
2018-04-06 17:13 ` [RFC PATCH v3 bpf-next 2/5] bpf/verifier: rewrite subprog boundary detection Edward Cree
` (4 subsequent siblings)
5 siblings, 0 replies; 10+ messages in thread
From: Edward Cree @ 2018-04-06 17:13 UTC (permalink / raw)
To: Alexei Starovoitov, Daniel Borkmann; +Cc: netdev
Per-subprog info is stored in env->subprog_info, an array of structs,
rather than multiple arrays with a common index.
Signed-off-by: Edward Cree <ecree@solarflare.com>
---
include/linux/bpf_verifier.h | 9 +++++---
kernel/bpf/verifier.c | 49 +++++++++++++++++++++++---------------------
2 files changed, 32 insertions(+), 26 deletions(-)
diff --git a/include/linux/bpf_verifier.h b/include/linux/bpf_verifier.h
index 7e61c395fddf..8f70dc181e23 100644
--- a/include/linux/bpf_verifier.h
+++ b/include/linux/bpf_verifier.h
@@ -173,6 +173,11 @@ static inline bool bpf_verifier_log_needed(const struct bpf_verifier_log *log)
#define BPF_MAX_SUBPROGS 256
+struct bpf_subprog_info {
+ u32 start; /* insn idx of function entry point */
+ u16 stack_depth; /* max. stack depth used by this function */
+};
+
/* single container for all structs
* one verifier_env per bpf_check() call
*/
@@ -191,9 +196,7 @@ struct bpf_verifier_env {
bool seen_direct_write;
struct bpf_insn_aux_data *insn_aux_data; /* array of per-insn state */
struct bpf_verifier_log log;
- u32 subprog_starts[BPF_MAX_SUBPROGS];
- /* computes the stack depth of each bpf function */
- u16 subprog_stack_depth[BPF_MAX_SUBPROGS + 1];
+ struct bpf_subprog_info subprog_info[BPF_MAX_SUBPROGS + 1];
u32 subprog_cnt;
};
diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c
index 5dd1dcb902bf..df4d742360d9 100644
--- a/kernel/bpf/verifier.c
+++ b/kernel/bpf/verifier.c
@@ -738,18 +738,19 @@ enum reg_arg_type {
static int cmp_subprogs(const void *a, const void *b)
{
- return *(int *)a - *(int *)b;
+ return ((struct bpf_subprog_info *)a)->start -
+ ((struct bpf_subprog_info *)b)->start;
}
static int find_subprog(struct bpf_verifier_env *env, int off)
{
- u32 *p;
+ struct bpf_subprog_info *p;
- p = bsearch(&off, env->subprog_starts, env->subprog_cnt,
- sizeof(env->subprog_starts[0]), cmp_subprogs);
+ p = bsearch(&off, env->subprog_info, env->subprog_cnt,
+ sizeof(env->subprog_info[0]), cmp_subprogs);
if (!p)
return -ENOENT;
- return p - env->subprog_starts;
+ return p - env->subprog_info;
}
@@ -769,9 +770,9 @@ static int add_subprog(struct bpf_verifier_env *env, int off)
verbose(env, "too many subprograms\n");
return -E2BIG;
}
- env->subprog_starts[env->subprog_cnt++] = off;
- sort(env->subprog_starts, env->subprog_cnt,
- sizeof(env->subprog_starts[0]), cmp_subprogs, NULL);
+ env->subprog_info[env->subprog_cnt++].start = off;
+ sort(env->subprog_info, env->subprog_cnt,
+ sizeof(env->subprog_info[0]), cmp_subprogs, NULL);
return 0;
}
@@ -802,14 +803,14 @@ static int check_subprogs(struct bpf_verifier_env *env)
if (env->log.level > 1)
for (i = 0; i < env->subprog_cnt; i++)
- verbose(env, "func#%d @%d\n", i, env->subprog_starts[i]);
+ verbose(env, "func#%d @%d\n", i, env->subprog_info[i].start);
/* now check that all jumps are within the same subprog */
subprog_start = 0;
if (env->subprog_cnt == cur_subprog)
subprog_end = insn_cnt;
else
- subprog_end = env->subprog_starts[cur_subprog++];
+ subprog_end = env->subprog_info[cur_subprog++].start;
for (i = 0; i < insn_cnt; i++) {
u8 code = insn[i].code;
@@ -837,7 +838,7 @@ static int check_subprogs(struct bpf_verifier_env *env)
if (env->subprog_cnt == cur_subprog)
subprog_end = insn_cnt;
else
- subprog_end = env->subprog_starts[cur_subprog++];
+ subprog_end = env->subprog_info[cur_subprog++].start;
}
}
return 0;
@@ -1470,13 +1471,13 @@ static int update_stack_depth(struct bpf_verifier_env *env,
const struct bpf_func_state *func,
int off)
{
- u16 stack = env->subprog_stack_depth[func->subprogno];
+ u16 stack = env->subprog_info[func->subprogno].stack_depth;
if (stack >= -off)
return 0;
/* update known max for given subprogram */
- env->subprog_stack_depth[func->subprogno] = -off;
+ env->subprog_info[func->subprogno].stack_depth = -off;
return 0;
}
@@ -1498,7 +1499,8 @@ static int check_max_stack_depth(struct bpf_verifier_env *env)
/* round up to 32-bytes, since this is granularity
* of interpreter stack size
*/
- depth += round_up(max_t(u32, env->subprog_stack_depth[subprog], 1), 32);
+ depth += round_up(max_t(u32, env->subprog_info[subprog].stack_depth, 1),
+ 32);
if (depth > MAX_BPF_STACK) {
verbose(env, "combined stack size of %d calls is %d. Too large\n",
frame + 1, depth);
@@ -1508,7 +1510,7 @@ static int check_max_stack_depth(struct bpf_verifier_env *env)
if (env->subprog_cnt == subprog)
subprog_end = insn_cnt;
else
- subprog_end = env->subprog_starts[subprog];
+ subprog_end = env->subprog_info[subprog].start;
for (; i < subprog_end; i++) {
if (insn[i].code != (BPF_JMP | BPF_CALL))
continue;
@@ -1539,7 +1541,8 @@ static int check_max_stack_depth(struct bpf_verifier_env *env)
*/
if (frame == 0)
return 0;
- depth -= round_up(max_t(u32, env->subprog_stack_depth[subprog], 1), 32);
+ depth -= round_up(max_t(u32, env->subprog_info[subprog].stack_depth, 1),
+ 32);
frame--;
i = ret_insn[frame];
subprog = ret_prog[frame];
@@ -1559,7 +1562,7 @@ static int get_callee_stack_depth(struct bpf_verifier_env *env,
return -EFAULT;
}
subprog++;
- return env->subprog_stack_depth[subprog];
+ return env->subprog_info[subprog].stack_depth;
}
#endif
@@ -4860,14 +4863,14 @@ static int do_check(struct bpf_verifier_env *env)
verbose(env, "processed %d insns (limit %d), stack depth ",
insn_processed, BPF_COMPLEXITY_LIMIT_INSNS);
for (i = 0; i < env->subprog_cnt + 1; i++) {
- u32 depth = env->subprog_stack_depth[i];
+ u32 depth = env->subprog_info[i].stack_depth;
verbose(env, "%d", depth);
if (i + 1 < env->subprog_cnt + 1)
verbose(env, "+");
}
verbose(env, "\n");
- env->prog->aux->stack_depth = env->subprog_stack_depth[0];
+ env->prog->aux->stack_depth = env->subprog_info[0].stack_depth;
return 0;
}
@@ -5074,9 +5077,9 @@ static void adjust_subprog_starts(struct bpf_verifier_env *env, u32 off, u32 len
if (len == 1)
return;
for (i = 0; i < env->subprog_cnt; i++) {
- if (env->subprog_starts[i] < off)
+ if (env->subprog_info[i].start < off)
continue;
- env->subprog_starts[i] += len - 1;
+ env->subprog_info[i].start += len - 1;
}
}
@@ -5274,7 +5277,7 @@ static int jit_subprogs(struct bpf_verifier_env *env)
if (env->subprog_cnt == i)
subprog_end = prog->len;
else
- subprog_end = env->subprog_starts[i];
+ subprog_end = env->subprog_info[i].start;
len = subprog_end - subprog_start;
func[i] = bpf_prog_alloc(bpf_prog_size(len), GFP_USER);
@@ -5291,7 +5294,7 @@ static int jit_subprogs(struct bpf_verifier_env *env)
* Long term would need debug info to populate names
*/
func[i]->aux->name[0] = 'F';
- func[i]->aux->stack_depth = env->subprog_stack_depth[i];
+ func[i]->aux->stack_depth = env->subprog_info[i].stack_depth;
func[i]->jit_requested = 1;
func[i] = bpf_int_jit_compile(func[i]);
if (!func[i]->jited) {
^ permalink raw reply related [flat|nested] 10+ messages in thread* [RFC PATCH v3 bpf-next 2/5] bpf/verifier: rewrite subprog boundary detection
2018-04-06 17:11 [RFC PATCH v3 bpf-next 0/5] bpf/verifier: subprog/func_call simplifications Edward Cree
2018-04-06 17:13 ` [RFC PATCH v3 bpf-next 1/5] bpf/verifier: store subprog info in struct bpf_subprog_info Edward Cree
@ 2018-04-06 17:13 ` Edward Cree
2018-04-17 23:48 ` Alexei Starovoitov
2018-04-06 17:14 ` [RFC PATCH v3 bpf-next 3/5] bpf/verifier: update selftests Edward Cree
` (3 subsequent siblings)
5 siblings, 1 reply; 10+ messages in thread
From: Edward Cree @ 2018-04-06 17:13 UTC (permalink / raw)
To: Alexei Starovoitov, Daniel Borkmann; +Cc: netdev
By storing a subprogno in each insn's aux data, we avoid the need to keep
the list of subprog starts sorted or bsearch() it in find_subprog().
Also, get rid of the weird one-based indexing of subprog numbers.
Signed-off-by: Edward Cree <ecree@solarflare.com>
---
include/linux/bpf_verifier.h | 3 +-
kernel/bpf/verifier.c | 284 ++++++++++++++++++++++++++-----------------
2 files changed, 177 insertions(+), 110 deletions(-)
diff --git a/include/linux/bpf_verifier.h b/include/linux/bpf_verifier.h
index 8f70dc181e23..17990dd56e65 100644
--- a/include/linux/bpf_verifier.h
+++ b/include/linux/bpf_verifier.h
@@ -146,6 +146,7 @@ struct bpf_insn_aux_data {
s32 call_imm; /* saved imm field of call insn */
};
int ctx_field_size; /* the ctx field size for load insn, maybe 0 */
+ u16 subprogno; /* subprog in which this insn resides */
bool seen; /* this insn was processed by the verifier */
};
@@ -196,7 +197,7 @@ struct bpf_verifier_env {
bool seen_direct_write;
struct bpf_insn_aux_data *insn_aux_data; /* array of per-insn state */
struct bpf_verifier_log log;
- struct bpf_subprog_info subprog_info[BPF_MAX_SUBPROGS + 1];
+ struct bpf_subprog_info subprog_info[BPF_MAX_SUBPROGS];
u32 subprog_cnt;
};
diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c
index df4d742360d9..587eb445bfa2 100644
--- a/kernel/bpf/verifier.c
+++ b/kernel/bpf/verifier.c
@@ -736,109 +736,171 @@ enum reg_arg_type {
DST_OP_NO_MARK /* same as above, check only, don't mark */
};
-static int cmp_subprogs(const void *a, const void *b)
+static int find_subprog(struct bpf_verifier_env *env, int insn_idx)
{
- return ((struct bpf_subprog_info *)a)->start -
- ((struct bpf_subprog_info *)b)->start;
-}
-
-static int find_subprog(struct bpf_verifier_env *env, int off)
-{
- struct bpf_subprog_info *p;
-
- p = bsearch(&off, env->subprog_info, env->subprog_cnt,
- sizeof(env->subprog_info[0]), cmp_subprogs);
- if (!p)
- return -ENOENT;
- return p - env->subprog_info;
+ int insn_cnt = env->prog->len;
+ u32 subprogno;
+ if (insn_idx >= insn_cnt || insn_idx < 0) {
+ verbose(env, "find_subprog of invalid insn_idx %d\n", insn_idx);
+ return -EINVAL;
+ }
+ subprogno = env->insn_aux_data[insn_idx].subprogno;
+ /* validate that we are at start of subprog */
+ if (env->subprog_info[subprogno].start != insn_idx) {
+ verbose(env, "insn_idx %d is in subprog %u but that starts at %d\n",
+ insn_idx, subprogno, env->subprog_info[subprogno].start);
+ return -EINVAL;
+ }
+ return subprogno;
}
static int add_subprog(struct bpf_verifier_env *env, int off)
{
int insn_cnt = env->prog->len;
+ struct bpf_subprog_info *info;
int ret;
if (off >= insn_cnt || off < 0) {
verbose(env, "call to invalid destination\n");
return -EINVAL;
}
- ret = find_subprog(env, off);
- if (ret >= 0)
- return 0;
- if (env->subprog_cnt >= BPF_MAX_SUBPROGS) {
- verbose(env, "too many subprograms\n");
- return -E2BIG;
+ ret = env->insn_aux_data[off].subprogno;
+ /* At the time add_subprog is called, only (some) entry points are
+ * marked with an aux->subprogno; 'body' insns aren't. Thus, a
+ * subprogno of 0 means either "not yet marked as an entry point" or
+ * "entry point of main(), i.e. insn 0".
+ * However, a call to insn 0 is never legal (it would necessarily imply
+ * recursion, which check_cfg will catch), therefore we can assume that
+ * we will only be called with off == 0 once, and in that case we
+ * should go ahead and add the subprog entry.
+ */
+ if (!ret) {
+ if (env->subprog_cnt >= BPF_MAX_SUBPROGS) {
+ verbose(env, "too many subprograms\n");
+ return -E2BIG;
+ }
+ ret = env->subprog_cnt++;
+ info = &env->subprog_info[ret];
+ info->start = off;
+ info->stack_depth = 0;
+ env->insn_aux_data[off].subprogno = ret;
}
- env->subprog_info[env->subprog_cnt++].start = off;
- sort(env->subprog_info, env->subprog_cnt,
- sizeof(env->subprog_info[0]), cmp_subprogs, NULL);
- return 0;
+ return ret;
}
static int check_subprogs(struct bpf_verifier_env *env)
{
- int i, ret, subprog_start, subprog_end, off, cur_subprog = 0;
- struct bpf_insn *insn = env->prog->insnsi;
- int insn_cnt = env->prog->len;
+ struct bpf_insn_aux_data *aux = env->insn_aux_data;
+ struct bpf_insn *insns = env->prog->insnsi;
+ int insn_cnt = env->prog->len, i, err;
+ int cur_subprog;
- /* determine subprog starts. The end is one before the next starts */
- for (i = 0; i < insn_cnt; i++) {
- if (insn[i].code != (BPF_JMP | BPF_CALL))
- continue;
- if (insn[i].src_reg != BPF_PSEUDO_CALL)
- continue;
- if (!env->allow_ptr_leaks) {
- verbose(env, "function calls to other bpf functions are allowed for root only\n");
- return -EPERM;
- }
- if (bpf_prog_is_dev_bound(env->prog->aux)) {
- verbose(env, "function calls in offloaded programs are not supported yet\n");
- return -EINVAL;
+ /* Find subprog starts */
+ err = add_subprog(env, 0); /* subprog 0, main(), starts at insn 0 */
+ if (err < 0)
+ return err;
+ for (i = 0; i < insn_cnt; i++)
+ if (insns[i].code == (BPF_JMP | BPF_CALL) &&
+ insns[i].src_reg == BPF_PSEUDO_CALL) {
+ if (!env->allow_ptr_leaks) {
+ verbose(env, "function calls to other bpf functions are allowed for root only\n");
+ return -EPERM;
+ }
+ if (bpf_prog_is_dev_bound(env->prog->aux)) {
+ verbose(env, "function calls in offloaded programs are not supported yet\n");
+ return -EINVAL;
+ }
+ /* add_subprog marks the callee entry point with the
+ * new subprogno.
+ */
+ err = add_subprog(env, i + insns[i].imm + 1);
+ if (err < 0)
+ return err;
}
- ret = add_subprog(env, i + insn[i].imm + 1);
- if (ret < 0)
- return ret;
- }
if (env->log.level > 1)
for (i = 0; i < env->subprog_cnt; i++)
verbose(env, "func#%d @%d\n", i, env->subprog_info[i].start);
- /* now check that all jumps are within the same subprog */
- subprog_start = 0;
- if (env->subprog_cnt == cur_subprog)
- subprog_end = insn_cnt;
- else
- subprog_end = env->subprog_info[cur_subprog++].start;
+ /* Fill in subprogno on each insn of function body, on the assumption
+ * that each subprog is a contiguous block of insns. This will be
+ * validated by the next step
+ */
+ cur_subprog = 0;
+ for (i = 0; i < insn_cnt; i++)
+ if (aux[i].subprogno)
+ cur_subprog = aux[i].subprogno;
+ else
+ aux[i].subprogno = cur_subprog;
+
+ /* Check that control never flows from one subprog to another except by
+ * a pseudo-call insn.
+ */
for (i = 0; i < insn_cnt; i++) {
- u8 code = insn[i].code;
-
- if (BPF_CLASS(code) != BPF_JMP)
- goto next;
- if (BPF_OP(code) == BPF_EXIT || BPF_OP(code) == BPF_CALL)
- goto next;
- off = i + insn[i].off + 1;
- if (off < subprog_start || off >= subprog_end) {
- verbose(env, "jump out of range from insn %d to %d\n", i, off);
- return -EINVAL;
+ bool fallthrough = false, jump = false;
+ u8 opcode = BPF_OP(insns[i].code);
+ int target;
+
+ /* Determine where control flow from this insn goes */
+ if (BPF_CLASS(insns[i].code) != BPF_JMP) {
+ fallthrough = true;
+ } else {
+ switch (opcode) {
+ case BPF_EXIT:
+ /* This insn doesn't go anywhere. If we're in
+ * a subprog, then the return target is handled
+ * as a fallthrough on the call insn, so no need
+ * to worry about it here.
+ */
+ continue;
+ case BPF_CALL:
+ /* If pseudo-call, already handled marking the
+ * callee. Both kinds of call will eventually
+ * return and pass to the following insn.
+ */
+ fallthrough = true;
+ break;
+ case BPF_JA:
+ /* unconditional jump; mark target */
+ jump = true;
+ target = i + insns[i].off + 1;
+ break;
+ default:
+ /* conditional jump; branch both ways */
+ fallthrough = true;
+ jump = true;
+ target = i + insns[i].off + 1;
+ break;
+ }
}
-next:
- if (i == subprog_end - 1) {
- /* to avoid fall-through from one subprog into another
- * the last insn of the subprog should be either exit
- * or unconditional jump back
- */
- if (code != (BPF_JMP | BPF_EXIT) &&
- code != (BPF_JMP | BPF_JA)) {
- verbose(env, "last insn is not an exit or jmp\n");
+
+ /* Check that that control flow doesn't leave the subprog */
+ cur_subprog = aux[i].subprogno;
+ if (fallthrough) {
+ if (i + 1 >= insn_cnt) {
+ verbose(env, "no exit/jump at end of program (insn %d)\n",
+ i);
+ return -EINVAL;
+ }
+ if (aux[i + 1].subprogno != cur_subprog) {
+ verbose(env, "no exit/jump at end of subprog %d (insn %d)\n",
+ cur_subprog, i);
+ return -EINVAL;
+ }
+ }
+ if (jump) {
+ if (target < 0 || target >= insn_cnt) {
+ verbose(env, "jump out of range from insn %d to %d\n",
+ i, target);
+ return -EINVAL;
+ }
+ if (aux[target].subprogno != cur_subprog) {
+ verbose(env, "jump from insn %d to %d crosses from subprog %d to %d\n",
+ i, target, cur_subprog,
+ aux[target].subprogno);
return -EINVAL;
}
- subprog_start = subprog_end;
- if (env->subprog_cnt == cur_subprog)
- subprog_end = insn_cnt;
- else
- subprog_end = env->subprog_info[cur_subprog++].start;
}
}
return 0;
@@ -1489,7 +1551,8 @@ static int update_stack_depth(struct bpf_verifier_env *env,
*/
static int check_max_stack_depth(struct bpf_verifier_env *env)
{
- int depth = 0, frame = 0, subprog = 0, i = 0, subprog_end;
+ int depth = 0, frame = 0, subprog = 0, i = 0;
+ struct bpf_insn_aux_data *aux = env->insn_aux_data;
struct bpf_insn *insn = env->prog->insnsi;
int insn_cnt = env->prog->len;
int ret_insn[MAX_CALL_FRAMES];
@@ -1507,11 +1570,7 @@ static int check_max_stack_depth(struct bpf_verifier_env *env)
return -EACCES;
}
continue_func:
- if (env->subprog_cnt == subprog)
- subprog_end = insn_cnt;
- else
- subprog_end = env->subprog_info[subprog].start;
- for (; i < subprog_end; i++) {
+ for (; i < insn_cnt && aux[i].subprogno == subprog; i++) {
if (insn[i].code != (BPF_JMP | BPF_CALL))
continue;
if (insn[i].src_reg != BPF_PSEUDO_CALL)
@@ -1528,7 +1587,6 @@ static int check_max_stack_depth(struct bpf_verifier_env *env)
i);
return -EFAULT;
}
- subprog++;
frame++;
if (frame >= MAX_CALL_FRAMES) {
WARN_ONCE(1, "verifier bug. Call stack is too deep\n");
@@ -1561,7 +1619,6 @@ static int get_callee_stack_depth(struct bpf_verifier_env *env,
start);
return -EFAULT;
}
- subprog++;
return env->subprog_info[subprog].stack_depth;
}
#endif
@@ -2100,7 +2157,7 @@ static int check_map_func_compatibility(struct bpf_verifier_env *env,
case BPF_FUNC_tail_call:
if (map->map_type != BPF_MAP_TYPE_PROG_ARRAY)
goto error;
- if (env->subprog_cnt) {
+ if (env->subprog_cnt > 1) {
verbose(env, "tail_calls are not allowed in programs with bpf-to-bpf calls\n");
return -EINVAL;
}
@@ -2245,6 +2302,9 @@ static int check_func_call(struct bpf_verifier_env *env, struct bpf_insn *insn,
}
target_insn = *insn_idx + insn->imm;
+ /* We will increment insn_idx (PC) in do_check() after handling this
+ * call insn, so the actual start of the function is target + 1.
+ */
subprog = find_subprog(env, target_insn + 1);
if (subprog < 0) {
verbose(env, "verifier bug. No program starts at insn %d\n",
@@ -2272,7 +2332,7 @@ static int check_func_call(struct bpf_verifier_env *env, struct bpf_insn *insn,
/* remember the callsite, it will be used by bpf_exit */
*insn_idx /* callsite */,
state->curframe + 1 /* frameno within this callchain */,
- subprog + 1 /* subprog number within this prog */);
+ subprog /* subprog number within this prog */);
/* copy r1 - r5 args that callee can access */
for (i = BPF_REG_1; i <= BPF_REG_5; i++)
@@ -3831,7 +3891,7 @@ static int check_ld_abs(struct bpf_verifier_env *env, struct bpf_insn *insn)
return -EINVAL;
}
- if (env->subprog_cnt) {
+ if (env->subprog_cnt > 1) {
/* when program has LD_ABS insn JITs and interpreter assume
* that r1 == ctx == skb which is not the case for callees
* that can have arbitrary arguments. It's problematic
@@ -4020,10 +4080,6 @@ static int check_cfg(struct bpf_verifier_env *env)
int ret = 0;
int i, t;
- ret = check_subprogs(env);
- if (ret < 0)
- return ret;
-
insn_state = kcalloc(insn_cnt, sizeof(int), GFP_KERNEL);
if (!insn_state)
return -ENOMEM;
@@ -4862,11 +4918,11 @@ static int do_check(struct bpf_verifier_env *env)
verbose(env, "processed %d insns (limit %d), stack depth ",
insn_processed, BPF_COMPLEXITY_LIMIT_INSNS);
- for (i = 0; i < env->subprog_cnt + 1; i++) {
+ for (i = 0; i < env->subprog_cnt; i++) {
u32 depth = env->subprog_info[i].stack_depth;
verbose(env, "%d", depth);
- if (i + 1 < env->subprog_cnt + 1)
+ if (i + 1 < env->subprog_cnt)
verbose(env, "+");
}
verbose(env, "\n");
@@ -5238,12 +5294,12 @@ static int convert_ctx_accesses(struct bpf_verifier_env *env)
static int jit_subprogs(struct bpf_verifier_env *env)
{
struct bpf_prog *prog = env->prog, **func, *tmp;
- int i, j, subprog_start, subprog_end = 0, len, subprog;
struct bpf_insn *insn;
void *old_bpf_func;
+ int i, j, subprog;
int err = -ENOMEM;
- if (env->subprog_cnt == 0)
+ if (env->subprog_cnt <= 1)
return 0;
for (i = 0, insn = prog->insnsi; i < prog->len; i++, insn++) {
@@ -5259,7 +5315,7 @@ static int jit_subprogs(struct bpf_verifier_env *env)
/* temporarily remember subprog id inside insn instead of
* aux_data, since next loop will split up all insns into funcs
*/
- insn->off = subprog + 1;
+ insn->off = subprog;
/* remember original imm in case JIT fails and fallback
* to interpreter will be needed
*/
@@ -5268,23 +5324,24 @@ static int jit_subprogs(struct bpf_verifier_env *env)
insn->imm = 1;
}
- func = kzalloc(sizeof(prog) * (env->subprog_cnt + 1), GFP_KERNEL);
+ func = kzalloc(sizeof(prog) * env->subprog_cnt, GFP_KERNEL);
if (!func)
return -ENOMEM;
- for (i = 0; i <= env->subprog_cnt; i++) {
- subprog_start = subprog_end;
- if (env->subprog_cnt == i)
- subprog_end = prog->len;
- else
- subprog_end = env->subprog_info[i].start;
+ for (i = 0; i < env->subprog_cnt; i++) {
+ struct bpf_subprog_info *info = &env->subprog_info[i];
+ int len, end = prog->len;
+
+ if (i + 1 < env->subprog_cnt)
+ end = info[1].start;
+ len = end - info->start;
- len = subprog_end - subprog_start;
func[i] = bpf_prog_alloc(bpf_prog_size(len), GFP_USER);
if (!func[i])
goto out_free;
- memcpy(func[i]->insnsi, &prog->insnsi[subprog_start],
+ memcpy(func[i]->insnsi, prog->insnsi + info->start,
len * sizeof(struct bpf_insn));
+
func[i]->type = prog->type;
func[i]->len = len;
if (bpf_prog_calc_tag(func[i]))
@@ -5307,7 +5364,7 @@ static int jit_subprogs(struct bpf_verifier_env *env)
* now populate all bpf_calls with correct addresses and
* run last pass of JIT
*/
- for (i = 0; i <= env->subprog_cnt; i++) {
+ for (i = 0; i < env->subprog_cnt; i++) {
insn = func[i]->insnsi;
for (j = 0; j < func[i]->len; j++, insn++) {
if (insn->code != (BPF_JMP | BPF_CALL) ||
@@ -5315,12 +5372,16 @@ static int jit_subprogs(struct bpf_verifier_env *env)
continue;
subprog = insn->off;
insn->off = 0;
+ if (subprog < 0 || subprog >= env->subprog_cnt) {
+ err = -EFAULT;
+ goto out_free;
+ }
insn->imm = (u64 (*)(u64, u64, u64, u64, u64))
func[subprog]->bpf_func -
__bpf_call_base;
}
}
- for (i = 0; i <= env->subprog_cnt; i++) {
+ for (i = 0; i < env->subprog_cnt; i++) {
old_bpf_func = func[i]->bpf_func;
tmp = bpf_int_jit_compile(func[i]);
if (tmp != func[i] || func[i]->bpf_func != old_bpf_func) {
@@ -5334,7 +5395,7 @@ static int jit_subprogs(struct bpf_verifier_env *env)
/* finally lock prog and jit images for all functions and
* populate kallsysm
*/
- for (i = 0; i <= env->subprog_cnt; i++) {
+ for (i = 0; i < env->subprog_cnt; i++) {
bpf_prog_lock_ro(func[i]);
bpf_prog_kallsyms_add(func[i]);
}
@@ -5351,7 +5412,7 @@ static int jit_subprogs(struct bpf_verifier_env *env)
continue;
insn->off = env->insn_aux_data[i].call_imm;
subprog = find_subprog(env, i + insn->off + 1);
- addr = (unsigned long)func[subprog + 1]->bpf_func;
+ addr = (unsigned long)func[subprog]->bpf_func;
addr &= PAGE_MASK;
insn->imm = (u64 (*)(u64, u64, u64, u64, u64))
addr - __bpf_call_base;
@@ -5360,10 +5421,10 @@ static int jit_subprogs(struct bpf_verifier_env *env)
prog->jited = 1;
prog->bpf_func = func[0]->bpf_func;
prog->aux->func = func;
- prog->aux->func_cnt = env->subprog_cnt + 1;
+ prog->aux->func_cnt = env->subprog_cnt;
return 0;
out_free:
- for (i = 0; i <= env->subprog_cnt; i++)
+ for (i = 0; i < env->subprog_cnt; i++)
if (func[i])
bpf_jit_free(func[i]);
kfree(func);
@@ -5393,6 +5454,7 @@ static int fixup_call_args(struct bpf_verifier_env *env)
err = jit_subprogs(env);
if (err == 0)
return 0;
+ verbose(env, "failed to jit_subprogs %d\n", err);
}
#ifndef CONFIG_BPF_JIT_ALWAYS_ON
for (i = 0; i < prog->len; i++, insn++) {
@@ -5682,6 +5744,10 @@ int bpf_check(struct bpf_prog **prog, union bpf_attr *attr)
env->allow_ptr_leaks = capable(CAP_SYS_ADMIN);
+ ret = check_subprogs(env);
+ if (ret < 0)
+ goto skip_full_check;
+
ret = check_cfg(env);
if (ret < 0)
goto skip_full_check;
^ permalink raw reply related [flat|nested] 10+ messages in thread* Re: [RFC PATCH v3 bpf-next 2/5] bpf/verifier: rewrite subprog boundary detection
2018-04-06 17:13 ` [RFC PATCH v3 bpf-next 2/5] bpf/verifier: rewrite subprog boundary detection Edward Cree
@ 2018-04-17 23:48 ` Alexei Starovoitov
2018-05-01 20:40 ` Edward Cree
0 siblings, 1 reply; 10+ messages in thread
From: Alexei Starovoitov @ 2018-04-17 23:48 UTC (permalink / raw)
To: Edward Cree; +Cc: Daniel Borkmann, netdev
On Fri, Apr 06, 2018 at 06:13:59PM +0100, Edward Cree wrote:
> By storing a subprogno in each insn's aux data, we avoid the need to keep
> the list of subprog starts sorted or bsearch() it in find_subprog().
> Also, get rid of the weird one-based indexing of subprog numbers.
>
> Signed-off-by: Edward Cree <ecree@solarflare.com>
> ---
> include/linux/bpf_verifier.h | 3 +-
> kernel/bpf/verifier.c | 284 ++++++++++++++++++++++++++-----------------
> 2 files changed, 177 insertions(+), 110 deletions(-)
>
> diff --git a/include/linux/bpf_verifier.h b/include/linux/bpf_verifier.h
> index 8f70dc181e23..17990dd56e65 100644
> --- a/include/linux/bpf_verifier.h
> +++ b/include/linux/bpf_verifier.h
> @@ -146,6 +146,7 @@ struct bpf_insn_aux_data {
> s32 call_imm; /* saved imm field of call insn */
> };
> int ctx_field_size; /* the ctx field size for load insn, maybe 0 */
> + u16 subprogno; /* subprog in which this insn resides */
> bool seen; /* this insn was processed by the verifier */
> };
as I was saying before this is no go.
subprogno is meaningless in the hierarchy of: prog -> func -> bb -> insn
Soon bpf will have libraries and this field would need to become
a pointer back to bb or func structure creating unnecessary circular dependency.
^ permalink raw reply [flat|nested] 10+ messages in thread* Re: [RFC PATCH v3 bpf-next 2/5] bpf/verifier: rewrite subprog boundary detection
2018-04-17 23:48 ` Alexei Starovoitov
@ 2018-05-01 20:40 ` Edward Cree
0 siblings, 0 replies; 10+ messages in thread
From: Edward Cree @ 2018-05-01 20:40 UTC (permalink / raw)
To: Alexei Starovoitov; +Cc: Daniel Borkmann, netdev
On 18/04/18 00:48, Alexei Starovoitov wrote:
> as I was saying before this is no go.
> subprogno is meaningless in the hierarchy of: prog -> func -> bb -> insn
> Soon bpf will have libraries and this field would need to become
> a pointer back to bb or func structure creating unnecessary circular dependency.
I'm afraid I don't follow. Why can't func numbers (and later, bb numbers)
be per-prog? When verifier is linking multiple progs together it will
necessarily have the subprog-info for each prog, and when making cross-
prog calls it'll have to already know which prog it's calling into; I
don't see any reason why the index into a prog's subprog_info array
should become "meaningless" in such a setup.
Besides, subprogno is how the rest of the verifier currently identifies a
func, and in the absence of any indication of how anything different
will be implemented, that's what an incremental patch has to work with.
If you're worried about the SPOT violation from having both
aux->subprogno and subprog_info->start... well, we could actually get
rid of the latter! Uses of it are:
* carving up insn arrays in jit_subprogs(). Could be done based on
aux->subprogno instead (v1 of this series did that)
* checking CALL destination is at start of function. That could be done
by putting a flag in the aux_data to mark "this insn is at the start of
its subprog". Doesn't even need to increase memory usage: it could be
done by ORing a flag (0x8000, say) into aux->subprogno; or we could
replace 'bool seen;' with 'u8 flags;' again with no extra memory used.
* a few verbose() messages.
That would have another nice consequence, in that adjust_subprog_starts()
could go away - another code simplification resulting from use of the
right data structures.
Btw, sorry for delay in responding; got bogged down in some sfc driver
work.
-Ed
^ permalink raw reply [flat|nested] 10+ messages in thread
* [RFC PATCH v3 bpf-next 3/5] bpf/verifier: update selftests
2018-04-06 17:11 [RFC PATCH v3 bpf-next 0/5] bpf/verifier: subprog/func_call simplifications Edward Cree
2018-04-06 17:13 ` [RFC PATCH v3 bpf-next 1/5] bpf/verifier: store subprog info in struct bpf_subprog_info Edward Cree
2018-04-06 17:13 ` [RFC PATCH v3 bpf-next 2/5] bpf/verifier: rewrite subprog boundary detection Edward Cree
@ 2018-04-06 17:14 ` Edward Cree
2018-04-06 17:14 ` [RFC PATCH v3 bpf-next 4/5] bpf/verifier: use call graph to efficiently check max stack depth Edward Cree
` (2 subsequent siblings)
5 siblings, 0 replies; 10+ messages in thread
From: Edward Cree @ 2018-04-06 17:14 UTC (permalink / raw)
To: Alexei Starovoitov, Daniel Borkmann; +Cc: netdev
Error messages for some bad programs have changed.
Also added a test ("calls: interleaved functions") to ensure that subprogs
are required to be contiguous.
It wasn't entirely clear to me what "calls: wrong recursive calls" was
meant to test for, since all of the JMP|CALL insns are unreachable. I've
changed it so that they are now reachable, which causes static back-edges
to be detected (since that, like insn reachability, is now tested before
subprog boundaries are determined).
Signed-off-by: Edward Cree <ecree@solarflare.com>
---
tools/testing/selftests/bpf/test_verifier.c | 51 ++++++++++++++++++-----------
1 file changed, 32 insertions(+), 19 deletions(-)
diff --git a/tools/testing/selftests/bpf/test_verifier.c b/tools/testing/selftests/bpf/test_verifier.c
index 3e7718b1a9ae..d53522d20072 100644
--- a/tools/testing/selftests/bpf/test_verifier.c
+++ b/tools/testing/selftests/bpf/test_verifier.c
@@ -646,7 +646,7 @@ static struct bpf_test tests[] = {
.insns = {
BPF_ALU64_REG(BPF_MOV, BPF_REG_0, BPF_REG_2),
},
- .errstr = "not an exit",
+ .errstr = "no exit/jump at end of program",
.result = REJECT,
},
{
@@ -9442,13 +9442,13 @@ static struct bpf_test tests[] = {
BPF_EXIT_INSN(),
},
.prog_type = BPF_PROG_TYPE_TRACEPOINT,
- .errstr = "last insn is not an exit or jmp",
+ .errstr = "no exit/jump at end of subprog 0 (insn 0)",
.result = REJECT,
},
{
"calls: wrong recursive calls",
.insns = {
- BPF_JMP_IMM(BPF_JA, 0, 0, 4),
+ BPF_JMP_IMM(BPF_JA, 0, 0, 3),
BPF_JMP_IMM(BPF_JA, 0, 0, 4),
BPF_RAW_INSN(BPF_JMP | BPF_CALL, 0, 1, 0, -2),
BPF_RAW_INSN(BPF_JMP | BPF_CALL, 0, 1, 0, -2),
@@ -9457,7 +9457,7 @@ static struct bpf_test tests[] = {
BPF_EXIT_INSN(),
},
.prog_type = BPF_PROG_TYPE_TRACEPOINT,
- .errstr = "jump out of range",
+ .errstr = "jump from insn 0 to 4 crosses",
.result = REJECT,
},
{
@@ -9508,7 +9508,7 @@ static struct bpf_test tests[] = {
BPF_EXIT_INSN(),
},
.prog_type = BPF_PROG_TYPE_TRACEPOINT,
- .errstr = "jump out of range",
+ .errstr = "jump from insn 1 to 5 crosses",
.result = REJECT,
},
{
@@ -9787,7 +9787,7 @@ static struct bpf_test tests[] = {
BPF_EXIT_INSN(),
},
.prog_type = BPF_PROG_TYPE_SCHED_CLS,
- .errstr = "jump out of range from insn 1 to 4",
+ .errstr = "jump from insn 1 to 4 crosses",
.result = REJECT,
},
{
@@ -9803,13 +9803,12 @@ static struct bpf_test tests[] = {
BPF_ALU64_REG(BPF_ADD, BPF_REG_7, BPF_REG_0),
BPF_MOV64_REG(BPF_REG_0, BPF_REG_7),
BPF_EXIT_INSN(),
- BPF_LDX_MEM(BPF_W, BPF_REG_0, BPF_REG_1,
- offsetof(struct __sk_buff, len)),
+ BPF_LDX_MEM(BPF_DW, BPF_REG_0, BPF_REG_1, 8),
BPF_JMP_IMM(BPF_JEQ, BPF_REG_0, 0, -3),
BPF_EXIT_INSN(),
},
.prog_type = BPF_PROG_TYPE_TRACEPOINT,
- .errstr = "jump out of range from insn 11 to 9",
+ .errstr = "jump from insn 11 to 9 crosses",
.result = REJECT,
},
{
@@ -9861,7 +9860,7 @@ static struct bpf_test tests[] = {
BPF_EXIT_INSN(),
},
.prog_type = BPF_PROG_TYPE_TRACEPOINT,
- .errstr = "invalid destination",
+ .errstr = "call to invalid destination",
.result = REJECT,
},
{
@@ -9873,7 +9872,7 @@ static struct bpf_test tests[] = {
BPF_EXIT_INSN(),
},
.prog_type = BPF_PROG_TYPE_TRACEPOINT,
- .errstr = "invalid destination",
+ .errstr = "call to invalid destination",
.result = REJECT,
},
{
@@ -9886,7 +9885,7 @@ static struct bpf_test tests[] = {
BPF_EXIT_INSN(),
},
.prog_type = BPF_PROG_TYPE_TRACEPOINT,
- .errstr = "jump out of range",
+ .errstr = "jump from insn 3 to 1 crosses",
.result = REJECT,
},
{
@@ -9899,7 +9898,7 @@ static struct bpf_test tests[] = {
BPF_EXIT_INSN(),
},
.prog_type = BPF_PROG_TYPE_TRACEPOINT,
- .errstr = "jump out of range",
+ .errstr = "jump from insn 0 to 4 crosses",
.result = REJECT,
},
{
@@ -9913,7 +9912,7 @@ static struct bpf_test tests[] = {
BPF_JMP_IMM(BPF_JEQ, BPF_REG_1, 0, -2),
},
.prog_type = BPF_PROG_TYPE_TRACEPOINT,
- .errstr = "not an exit",
+ .errstr = "no exit/jump at end of program",
.result = REJECT,
},
{
@@ -9927,7 +9926,7 @@ static struct bpf_test tests[] = {
BPF_EXIT_INSN(),
},
.prog_type = BPF_PROG_TYPE_TRACEPOINT,
- .errstr = "last insn",
+ .errstr = "no exit/jump at end of subprog",
.result = REJECT,
},
{
@@ -9942,7 +9941,7 @@ static struct bpf_test tests[] = {
BPF_EXIT_INSN(),
},
.prog_type = BPF_PROG_TYPE_TRACEPOINT,
- .errstr = "last insn",
+ .errstr = "no exit/jump at end of subprog",
.result = REJECT,
},
{
@@ -9982,12 +9981,11 @@ static struct bpf_test tests[] = {
BPF_ALU64_REG(BPF_ADD, BPF_REG_7, BPF_REG_0),
BPF_MOV64_REG(BPF_REG_0, BPF_REG_7),
BPF_MOV64_REG(BPF_REG_0, BPF_REG_0),
- BPF_LDX_MEM(BPF_W, BPF_REG_0, BPF_REG_1,
- offsetof(struct __sk_buff, len)),
+ BPF_LDX_MEM(BPF_DW, BPF_REG_0, BPF_REG_1, 8),
BPF_EXIT_INSN(),
},
.prog_type = BPF_PROG_TYPE_TRACEPOINT,
- .errstr = "not an exit",
+ .errstr = "no exit/jump at end of subprog",
.result = REJECT,
},
{
@@ -11423,6 +11421,21 @@ static struct bpf_test tests[] = {
.errstr = "BPF_XADD stores into R2 packet",
.prog_type = BPF_PROG_TYPE_XDP,
},
+ {
+ "calls: interleaved functions",
+ .insns = {
+ BPF_RAW_INSN(BPF_JMP | BPF_CALL, 0, 1, 0, 2),
+ BPF_MOV64_IMM(BPF_REG_0, 1),
+ BPF_JMP_IMM(BPF_JA, 0, 0, 2),
+ BPF_MOV64_IMM(BPF_REG_0, 2),
+ BPF_JMP_IMM(BPF_JA, 0, 0, 1),
+ BPF_EXIT_INSN(),
+ BPF_EXIT_INSN(),
+ },
+ .prog_type = BPF_PROG_TYPE_TRACEPOINT,
+ .errstr = "jump from insn 2 to 5 crosses",
+ .result = REJECT,
+ },
};
static int probe_filter_length(const struct bpf_insn *fp)
^ permalink raw reply related [flat|nested] 10+ messages in thread* [RFC PATCH v3 bpf-next 4/5] bpf/verifier: use call graph to efficiently check max stack depth
2018-04-06 17:11 [RFC PATCH v3 bpf-next 0/5] bpf/verifier: subprog/func_call simplifications Edward Cree
` (2 preceding siblings ...)
2018-04-06 17:14 ` [RFC PATCH v3 bpf-next 3/5] bpf/verifier: update selftests Edward Cree
@ 2018-04-06 17:14 ` Edward Cree
2018-04-10 12:54 ` Jiong Wang
2018-04-06 17:15 ` [RFC PATCH v3 bpf-next 5/5] bpf/verifier: per-register parent pointers Edward Cree
2018-04-10 12:54 ` [RFC PATCH v3 bpf-next 0/5] bpf/verifier: subprog/func_call simplifications Jiong Wang
5 siblings, 1 reply; 10+ messages in thread
From: Edward Cree @ 2018-04-06 17:14 UTC (permalink / raw)
To: Alexei Starovoitov, Daniel Borkmann; +Cc: netdev
Instead of recursively walking every possible call chain,
check_max_stack_depth() now uses an explicit call graph (recorded in
subprog_info.callees) which it topologically sorts, allowing it to find
for each subprog the maximum stack depth of all call chains, and then
use that depth in calculating the stack depth it implies for the
subprog's callees. This is O(number of subprogs).
The call graph is populated as part of the check_subprogs() pass.
Signed-off-by: Edward Cree <ecree@solarflare.com>
---
include/linux/bpf_verifier.h | 3 +
kernel/bpf/verifier.c | 168 +++++++++++++++++++++++++------------------
2 files changed, 101 insertions(+), 70 deletions(-)
diff --git a/include/linux/bpf_verifier.h b/include/linux/bpf_verifier.h
index 17990dd56e65..32f27cbe721b 100644
--- a/include/linux/bpf_verifier.h
+++ b/include/linux/bpf_verifier.h
@@ -175,8 +175,11 @@ static inline bool bpf_verifier_log_needed(const struct bpf_verifier_log *log)
#define BPF_MAX_SUBPROGS 256
struct bpf_subprog_info {
+ /* which other subprogs does this one directly call? */
+ DECLARE_BITMAP(callees, BPF_MAX_SUBPROGS);
u32 start; /* insn idx of function entry point */
u16 stack_depth; /* max. stack depth used by this function */
+ u16 total_stack_depth; /* max. stack depth used by entire call chain */
};
/* single container for all structs
diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c
index 587eb445bfa2..45f530e4a65e 100644
--- a/kernel/bpf/verifier.c
+++ b/kernel/bpf/verifier.c
@@ -784,6 +784,7 @@ static int add_subprog(struct bpf_verifier_env *env, int off)
info = &env->subprog_info[ret];
info->start = off;
info->stack_depth = 0;
+ memset(info->callees, 0, sizeof(info->callees));
env->insn_aux_data[off].subprogno = ret;
}
return ret;
@@ -793,13 +794,13 @@ static int check_subprogs(struct bpf_verifier_env *env)
{
struct bpf_insn_aux_data *aux = env->insn_aux_data;
struct bpf_insn *insns = env->prog->insnsi;
- int insn_cnt = env->prog->len, i, err;
+ int insn_cnt = env->prog->len, i, subprog;
int cur_subprog;
/* Find subprog starts */
- err = add_subprog(env, 0); /* subprog 0, main(), starts at insn 0 */
- if (err < 0)
- return err;
+ subprog = add_subprog(env, 0); /* subprog 0, main(), starts at insn 0 */
+ if (subprog < 0)
+ return subprog;
for (i = 0; i < insn_cnt; i++)
if (insns[i].code == (BPF_JMP | BPF_CALL) &&
insns[i].src_reg == BPF_PSEUDO_CALL) {
@@ -814,9 +815,9 @@ static int check_subprogs(struct bpf_verifier_env *env)
/* add_subprog marks the callee entry point with the
* new subprogno.
*/
- err = add_subprog(env, i + insns[i].imm + 1);
- if (err < 0)
- return err;
+ subprog = add_subprog(env, i + insns[i].imm + 1);
+ if (subprog < 0)
+ return subprog;
}
if (env->log.level > 1)
@@ -842,6 +843,7 @@ static int check_subprogs(struct bpf_verifier_env *env)
u8 opcode = BPF_OP(insns[i].code);
int target;
+ cur_subprog = aux[i].subprogno;
/* Determine where control flow from this insn goes */
if (BPF_CLASS(insns[i].code) != BPF_JMP) {
fallthrough = true;
@@ -855,9 +857,18 @@ static int check_subprogs(struct bpf_verifier_env *env)
*/
continue;
case BPF_CALL:
- /* If pseudo-call, already handled marking the
- * callee. Both kinds of call will eventually
- * return and pass to the following insn.
+ if (insns[i].src_reg == BPF_PSEUDO_CALL) {
+ /* record edge in call graph */
+ subprog = find_subprog(env, i + insns[i].imm + 1);
+ if (subprog < 0)
+ return subprog;
+ __set_bit(subprog, env->subprog_info[cur_subprog].callees);
+ /* already handled marking the callee
+ * back in add_subprog, so jump is false
+ */
+ }
+ /* Call will eventually return and pass control
+ * to the following insn.
*/
fallthrough = true;
break;
@@ -876,7 +887,6 @@ static int check_subprogs(struct bpf_verifier_env *env)
}
/* Check that that control flow doesn't leave the subprog */
- cur_subprog = aux[i].subprogno;
if (fallthrough) {
if (i + 1 >= insn_cnt) {
verbose(env, "no exit/jump at end of program (insn %d)\n",
@@ -1533,78 +1543,96 @@ static int update_stack_depth(struct bpf_verifier_env *env,
const struct bpf_func_state *func,
int off)
{
- u16 stack = env->subprog_info[func->subprogno].stack_depth;
+ struct bpf_subprog_info *info;
- if (stack >= -off)
- return 0;
+ if (!func)
+ return -EFAULT;
+ if (func->subprogno >= BPF_MAX_SUBPROGS)
+ return -E2BIG;
+ info = &env->subprog_info[func->subprogno];
/* update known max for given subprogram */
- env->subprog_info[func->subprogno].stack_depth = -off;
+ info->stack_depth = max_t(u16, info->stack_depth, -off);
return 0;
}
-/* starting from main bpf function walk all instructions of the function
- * and recursively walk all callees that given function can call.
- * Ignore jump and exit insns.
- * Since recursion is prevented by check_cfg() this algorithm
- * only needs a local stack of MAX_CALL_FRAMES to remember callsites
+/* Topologically sort the call graph, and thereby determine the maximum stack
+ * depth of each subprog's worst-case call chain. Store in total_stack_depth.
+ * The tsort is performed using Kahn's algorithm. Since that algorithm selects
+ * nodes in the order of the sorted output, we can do our processing in the loop
+ * that does the tsort, rather than storing the sorted list and then having a
+ * second loop to iterate over it and compute the total_stack_depth values.
*/
static int check_max_stack_depth(struct bpf_verifier_env *env)
{
- int depth = 0, frame = 0, subprog = 0, i = 0;
- struct bpf_insn_aux_data *aux = env->insn_aux_data;
- struct bpf_insn *insn = env->prog->insnsi;
- int insn_cnt = env->prog->len;
- int ret_insn[MAX_CALL_FRAMES];
- int ret_prog[MAX_CALL_FRAMES];
+ DECLARE_BITMAP(frontier, BPF_MAX_SUBPROGS) = {0};
+ DECLARE_BITMAP(visited, BPF_MAX_SUBPROGS) = {0};
+ int subprog, i, j;
+
+ /* subprog 0 has no incoming edges, and should be the only such */
+ __set_bit(0, frontier);
+ env->subprog_info[0].total_stack_depth = env->subprog_info[0].stack_depth;
+
+ while (true) {
+ /* select a frontier node */
+ subprog = find_first_bit(frontier, BPF_MAX_SUBPROGS);
+ if (subprog >= BPF_MAX_SUBPROGS) /* frontier is empty, done */
+ break;
+ /* remove it from the frontier */
+ __clear_bit(subprog, frontier);
+ /* validate its total stack depth. Since all callers of this
+ * function have already been processed, the value now in
+ * info->total_stack_depth reflects the deepest call chain of
+ * this function.
+ */
+ if (env->subprog_info[subprog].total_stack_depth > MAX_BPF_STACK) {
+ verbose(env, "combined stack size of calls to %d (at insn %d) is %d. Too large\n",
+ subprog, env->subprog_info[subprog].start,
+ env->subprog_info[subprog].total_stack_depth);
+ return -EACCES;
+ }
+ if (env->log.level > 1) {
+ verbose(env, "combined stack size of calls to %d (at insn %d) is %d\n",
+ subprog, env->subprog_info[subprog].start,
+ env->subprog_info[subprog].total_stack_depth);
+ }
+ __set_bit(subprog, visited);
+ /* for each callee */
+ for_each_set_bit(i, env->subprog_info[subprog].callees,
+ BPF_MAX_SUBPROGS) {
+ /* round up to 32-bytes, since this is granularity of
+ * interpreter stack size
+ */
+ u16 stack_depth = round_up(max_t(u16, env->subprog_info[i].stack_depth, 1), 32);
-process_func:
- /* round up to 32-bytes, since this is granularity
- * of interpreter stack size
- */
- depth += round_up(max_t(u32, env->subprog_info[subprog].stack_depth, 1),
- 32);
- if (depth > MAX_BPF_STACK) {
- verbose(env, "combined stack size of %d calls is %d. Too large\n",
- frame + 1, depth);
- return -EACCES;
+ /* Update callee total stack depth. Since our own
+ * max total_stack_depth is known, the callee tsd is
+ * at least that plus the callee's stack frame size.
+ */
+ env->subprog_info[i].total_stack_depth = max_t(u16,
+ env->subprog_info[i].total_stack_depth,
+ env->subprog_info[subprog].total_stack_depth +
+ stack_depth);
+ /* does it have unvisited callers? */
+ for_each_clear_bit(j, visited, env->subprog_cnt) {
+ if (test_bit(i, env->subprog_info[j].callees))
+ break;
+ }
+ /* if not, add it to the frontier */
+ if (j >= env->subprog_cnt)
+ __set_bit(i, frontier);
+ }
}
-continue_func:
- for (; i < insn_cnt && aux[i].subprogno == subprog; i++) {
- if (insn[i].code != (BPF_JMP | BPF_CALL))
- continue;
- if (insn[i].src_reg != BPF_PSEUDO_CALL)
- continue;
- /* remember insn and function to return to */
- ret_insn[frame] = i + 1;
- ret_prog[frame] = subprog;
- /* find the callee */
- i = i + insn[i].imm + 1;
- subprog = find_subprog(env, i);
- if (subprog < 0) {
- WARN_ONCE(1, "verifier bug. No program starts at insn %d\n",
- i);
- return -EFAULT;
- }
- frame++;
- if (frame >= MAX_CALL_FRAMES) {
- WARN_ONCE(1, "verifier bug. Call stack is too deep\n");
- return -EFAULT;
- }
- goto process_func;
+ /* are any nodes left unvisited? */
+ subprog = find_first_zero_bit(visited, env->subprog_cnt);
+ if (subprog < env->subprog_cnt) {
+ /* then call graph is not acyclic, which shouldn't happen */
+ verbose(env, "verifier bug. Call graph has a cycle including subprog %d (at insn %d)\n",
+ subprog, env->subprog_info[subprog].start);
+ return -EFAULT;
}
- /* end of for() loop means the last insn of the 'subprog'
- * was reached. Doesn't matter whether it was JA or EXIT
- */
- if (frame == 0)
- return 0;
- depth -= round_up(max_t(u32, env->subprog_info[subprog].stack_depth, 1),
- 32);
- frame--;
- i = ret_insn[frame];
- subprog = ret_prog[frame];
- goto continue_func;
+ return 0;
}
#ifndef CONFIG_BPF_JIT_ALWAYS_ON
^ permalink raw reply related [flat|nested] 10+ messages in thread* [RFC PATCH v3 bpf-next 5/5] bpf/verifier: per-register parent pointers
2018-04-06 17:11 [RFC PATCH v3 bpf-next 0/5] bpf/verifier: subprog/func_call simplifications Edward Cree
` (3 preceding siblings ...)
2018-04-06 17:14 ` [RFC PATCH v3 bpf-next 4/5] bpf/verifier: use call graph to efficiently check max stack depth Edward Cree
@ 2018-04-06 17:15 ` Edward Cree
2018-04-10 12:54 ` [RFC PATCH v3 bpf-next 0/5] bpf/verifier: subprog/func_call simplifications Jiong Wang
5 siblings, 0 replies; 10+ messages in thread
From: Edward Cree @ 2018-04-06 17:15 UTC (permalink / raw)
To: Alexei Starovoitov, Daniel Borkmann; +Cc: netdev
By giving each register its own liveness chain, we elide the skip_callee()
logic. Instead, each register's parent is the state it inherits from;
both check_func_call() and prepare_func_exit() automatically connect
reg states to the correct chain since when they copy the reg state across
(r1-r5 into the callee as args, and r0 out as the return value) they also
copy the parent pointer.
Signed-off-by: Edward Cree <ecree@solarflare.com>
---
include/linux/bpf_verifier.h | 8 +-
kernel/bpf/verifier.c | 180 ++++++++++---------------------------------
2 files changed, 45 insertions(+), 143 deletions(-)
diff --git a/include/linux/bpf_verifier.h b/include/linux/bpf_verifier.h
index 32f27cbe721b..81b627dbda32 100644
--- a/include/linux/bpf_verifier.h
+++ b/include/linux/bpf_verifier.h
@@ -41,6 +41,7 @@ enum bpf_reg_liveness {
};
struct bpf_reg_state {
+ /* Ordering of fields matters. See states_equal() */
enum bpf_reg_type type;
union {
/* valid when type == PTR_TO_PACKET */
@@ -59,7 +60,6 @@ struct bpf_reg_state {
* came from, when one is tested for != NULL.
*/
u32 id;
- /* Ordering of fields matters. See states_equal() */
/* For scalar types (SCALAR_VALUE), this represents our knowledge of
* the actual value.
* For pointer types, this represents the variable part of the offset
@@ -76,15 +76,15 @@ struct bpf_reg_state {
s64 smax_value; /* maximum possible (s64)value */
u64 umin_value; /* minimum possible (u64)value */
u64 umax_value; /* maximum possible (u64)value */
+ /* parentage chain for liveness checking */
+ struct bpf_reg_state *parent;
/* Inside the callee two registers can be both PTR_TO_STACK like
* R1=fp-8 and R2=fp-8, but one of them points to this function stack
* while another to the caller's stack. To differentiate them 'frameno'
* is used which is an index in bpf_verifier_state->frame[] array
* pointing to bpf_func_state.
- * This field must be second to last, for states_equal() reasons.
*/
u32 frameno;
- /* This field must be last, for states_equal() reasons. */
enum bpf_reg_liveness live;
};
@@ -107,7 +107,6 @@ struct bpf_stack_state {
*/
struct bpf_func_state {
struct bpf_reg_state regs[MAX_BPF_REG];
- struct bpf_verifier_state *parent;
/* index of call instruction that called into this func */
int callsite;
/* stack frame number of this function state from pov of
@@ -129,7 +128,6 @@ struct bpf_func_state {
struct bpf_verifier_state {
/* call stack tracking */
struct bpf_func_state *frame[MAX_CALL_FRAMES];
- struct bpf_verifier_state *parent;
u32 curframe;
};
diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c
index 45f530e4a65e..4b37cd6fa181 100644
--- a/kernel/bpf/verifier.c
+++ b/kernel/bpf/verifier.c
@@ -355,9 +355,9 @@ static int copy_stack_state(struct bpf_func_state *dst,
/* do_check() starts with zero-sized stack in struct bpf_verifier_state to
* make it consume minimal amount of memory. check_stack_write() access from
* the program calls into realloc_func_state() to grow the stack size.
- * Note there is a non-zero 'parent' pointer inside bpf_verifier_state
- * which this function copies over. It points to previous bpf_verifier_state
- * which is never reallocated
+ * Note there is a non-zero parent pointer inside each reg of bpf_verifier_state
+ * which this function copies over. It points to corresponding reg in previous
+ * bpf_verifier_state which is never reallocated
*/
static int realloc_func_state(struct bpf_func_state *state, int size,
bool copy_old)
@@ -441,7 +441,6 @@ static int copy_verifier_state(struct bpf_verifier_state *dst_state,
dst_state->frame[i] = NULL;
}
dst_state->curframe = src->curframe;
- dst_state->parent = src->parent;
for (i = 0; i <= src->curframe; i++) {
dst = dst_state->frame[i];
if (!dst) {
@@ -707,6 +706,7 @@ static void init_reg_state(struct bpf_verifier_env *env,
for (i = 0; i < MAX_BPF_REG; i++) {
mark_reg_not_init(env, regs, i);
regs[i].live = REG_LIVE_NONE;
+ regs[i].parent = NULL;
}
/* frame pointer */
@@ -916,74 +916,21 @@ static int check_subprogs(struct bpf_verifier_env *env)
return 0;
}
-static
-struct bpf_verifier_state *skip_callee(struct bpf_verifier_env *env,
- const struct bpf_verifier_state *state,
- struct bpf_verifier_state *parent,
- u32 regno)
-{
- struct bpf_verifier_state *tmp = NULL;
-
- /* 'parent' could be a state of caller and
- * 'state' could be a state of callee. In such case
- * parent->curframe < state->curframe
- * and it's ok for r1 - r5 registers
- *
- * 'parent' could be a callee's state after it bpf_exit-ed.
- * In such case parent->curframe > state->curframe
- * and it's ok for r0 only
- */
- if (parent->curframe == state->curframe ||
- (parent->curframe < state->curframe &&
- regno >= BPF_REG_1 && regno <= BPF_REG_5) ||
- (parent->curframe > state->curframe &&
- regno == BPF_REG_0))
- return parent;
-
- if (parent->curframe > state->curframe &&
- regno >= BPF_REG_6) {
- /* for callee saved regs we have to skip the whole chain
- * of states that belong to callee and mark as LIVE_READ
- * the registers before the call
- */
- tmp = parent;
- while (tmp && tmp->curframe != state->curframe) {
- tmp = tmp->parent;
- }
- if (!tmp)
- goto bug;
- parent = tmp;
- } else {
- goto bug;
- }
- return parent;
-bug:
- verbose(env, "verifier bug regno %d tmp %p\n", regno, tmp);
- verbose(env, "regno %d parent frame %d current frame %d\n",
- regno, parent->curframe, state->curframe);
- return NULL;
-}
-
+/* Parentage chain of this register (or stack slot) should take care of all
+ * issues like callee-saved registers, stack slot allocation time, etc.
+ */
static int mark_reg_read(struct bpf_verifier_env *env,
- const struct bpf_verifier_state *state,
- struct bpf_verifier_state *parent,
- u32 regno)
+ const struct bpf_reg_state *state,
+ struct bpf_reg_state *parent)
{
bool writes = parent == state->parent; /* Observe write marks */
- if (regno == BPF_REG_FP)
- /* We don't need to worry about FP liveness because it's read-only */
- return 0;
-
while (parent) {
/* if read wasn't screened by an earlier write ... */
- if (writes && state->frame[state->curframe]->regs[regno].live & REG_LIVE_WRITTEN)
+ if (writes && state->live & REG_LIVE_WRITTEN)
break;
- parent = skip_callee(env, state, parent, regno);
- if (!parent)
- return -EFAULT;
/* ... then we depend on parent's value */
- parent->frame[parent->curframe]->regs[regno].live |= REG_LIVE_READ;
+ parent->live |= REG_LIVE_READ;
state = parent;
parent = state->parent;
writes = true;
@@ -1009,7 +956,10 @@ static int check_reg_arg(struct bpf_verifier_env *env, u32 regno,
verbose(env, "R%d !read_ok\n", regno);
return -EACCES;
}
- return mark_reg_read(env, vstate, vstate->parent, regno);
+ /* We don't need to worry about FP liveness because it's read-only */
+ if (regno != BPF_REG_FP)
+ return mark_reg_read(env, ®s[regno],
+ regs[regno].parent);
} else {
/* check whether register used as dest operand can be written to */
if (regno == BPF_REG_FP) {
@@ -1121,61 +1071,6 @@ static int check_stack_write(struct bpf_verifier_env *env,
return 0;
}
-/* registers of every function are unique and mark_reg_read() propagates
- * the liveness in the following cases:
- * - from callee into caller for R1 - R5 that were used as arguments
- * - from caller into callee for R0 that used as result of the call
- * - from caller to the same caller skipping states of the callee for R6 - R9,
- * since R6 - R9 are callee saved by implicit function prologue and
- * caller's R6 != callee's R6, so when we propagate liveness up to
- * parent states we need to skip callee states for R6 - R9.
- *
- * stack slot marking is different, since stacks of caller and callee are
- * accessible in both (since caller can pass a pointer to caller's stack to
- * callee which can pass it to another function), hence mark_stack_slot_read()
- * has to propagate the stack liveness to all parent states at given frame number.
- * Consider code:
- * f1() {
- * ptr = fp - 8;
- * *ptr = ctx;
- * call f2 {
- * .. = *ptr;
- * }
- * .. = *ptr;
- * }
- * First *ptr is reading from f1's stack and mark_stack_slot_read() has
- * to mark liveness at the f1's frame and not f2's frame.
- * Second *ptr is also reading from f1's stack and mark_stack_slot_read() has
- * to propagate liveness to f2 states at f1's frame level and further into
- * f1 states at f1's frame level until write into that stack slot
- */
-static void mark_stack_slot_read(struct bpf_verifier_env *env,
- const struct bpf_verifier_state *state,
- struct bpf_verifier_state *parent,
- int slot, int frameno)
-{
- bool writes = parent == state->parent; /* Observe write marks */
-
- while (parent) {
- if (parent->frame[frameno]->allocated_stack <= slot * BPF_REG_SIZE)
- /* since LIVE_WRITTEN mark is only done for full 8-byte
- * write the read marks are conservative and parent
- * state may not even have the stack allocated. In such case
- * end the propagation, since the loop reached beginning
- * of the function
- */
- break;
- /* if read wasn't screened by an earlier write ... */
- if (writes && state->frame[frameno]->stack[slot].spilled_ptr.live & REG_LIVE_WRITTEN)
- break;
- /* ... then we depend on parent's value */
- parent->frame[frameno]->stack[slot].spilled_ptr.live |= REG_LIVE_READ;
- state = parent;
- parent = state->parent;
- writes = true;
- }
-}
-
static int check_stack_read(struct bpf_verifier_env *env,
struct bpf_func_state *reg_state /* func where register points to */,
int off, int size, int value_regno)
@@ -1213,8 +1108,8 @@ static int check_stack_read(struct bpf_verifier_env *env,
*/
state->regs[value_regno].live |= REG_LIVE_WRITTEN;
}
- mark_stack_slot_read(env, vstate, vstate->parent, spi,
- reg_state->frameno);
+ mark_reg_read(env, ®_state->stack[spi].spilled_ptr,
+ reg_state->stack[spi].spilled_ptr.parent);
return 0;
} else {
int zeros = 0;
@@ -1230,8 +1125,8 @@ static int check_stack_read(struct bpf_verifier_env *env,
off, i, size);
return -EACCES;
}
- mark_stack_slot_read(env, vstate, vstate->parent, spi,
- reg_state->frameno);
+ mark_reg_read(env, ®_state->stack[spi].spilled_ptr,
+ reg_state->stack[spi].spilled_ptr.parent);
if (value_regno >= 0) {
if (zeros == size) {
/* any size read into register is zero extended,
@@ -1930,8 +1825,8 @@ static int check_stack_boundary(struct bpf_verifier_env *env, int regno,
/* reading any byte out of 8-byte 'spill_slot' will cause
* the whole slot to be marked as 'read'
*/
- mark_stack_slot_read(env, env->cur_state, env->cur_state->parent,
- spi, state->frameno);
+ mark_reg_read(env, &state->stack[spi].spilled_ptr,
+ state->stack[spi].spilled_ptr.parent);
}
return update_stack_depth(env, state, off);
}
@@ -2362,11 +2257,13 @@ static int check_func_call(struct bpf_verifier_env *env, struct bpf_insn *insn,
state->curframe + 1 /* frameno within this callchain */,
subprog /* subprog number within this prog */);
- /* copy r1 - r5 args that callee can access */
+ /* copy r1 - r5 args that callee can access. The copy includes parent
+ * pointers, which connects us up to the liveness chain
+ */
for (i = BPF_REG_1; i <= BPF_REG_5; i++)
callee->regs[i] = caller->regs[i];
- /* after the call regsiters r0 - r5 were scratched */
+ /* after the call registers r0 - r5 were scratched */
for (i = 0; i < CALLER_SAVED_REGS; i++) {
mark_reg_not_init(env, caller->regs, caller_saved[i]);
check_reg_arg(env, caller_saved[i], DST_OP_NO_MARK);
@@ -4272,7 +4169,7 @@ static bool regsafe(struct bpf_reg_state *rold, struct bpf_reg_state *rcur,
/* explored state didn't use this */
return true;
- equal = memcmp(rold, rcur, offsetof(struct bpf_reg_state, frameno)) == 0;
+ equal = memcmp(rold, rcur, offsetof(struct bpf_reg_state, parent)) == 0;
if (rold->type == PTR_TO_STACK)
/* two stack pointers are equal only if they're pointing to
@@ -4505,7 +4402,7 @@ static bool states_equal(struct bpf_verifier_env *env,
* equivalent state (jump target or such) we didn't arrive by the straight-line
* code, so read marks in the state must propagate to the parent regardless
* of the state's write marks. That's what 'parent == state->parent' comparison
- * in mark_reg_read() and mark_stack_slot_read() is for.
+ * in mark_reg_read() is for.
*/
static int propagate_liveness(struct bpf_verifier_env *env,
const struct bpf_verifier_state *vstate,
@@ -4526,7 +4423,8 @@ static int propagate_liveness(struct bpf_verifier_env *env,
if (vparent->frame[vparent->curframe]->regs[i].live & REG_LIVE_READ)
continue;
if (vstate->frame[vstate->curframe]->regs[i].live & REG_LIVE_READ) {
- err = mark_reg_read(env, vstate, vparent, i);
+ err = mark_reg_read(env, &vstate->frame[vstate->curframe]->regs[i],
+ &vparent->frame[vstate->curframe]->regs[i]);
if (err)
return err;
}
@@ -4541,7 +4439,8 @@ static int propagate_liveness(struct bpf_verifier_env *env,
if (parent->stack[i].spilled_ptr.live & REG_LIVE_READ)
continue;
if (state->stack[i].spilled_ptr.live & REG_LIVE_READ)
- mark_stack_slot_read(env, vstate, vparent, i, frame);
+ mark_reg_read(env, &state->stack[i].spilled_ptr,
+ &parent->stack[i].spilled_ptr);
}
}
return err;
@@ -4551,7 +4450,7 @@ static int is_state_visited(struct bpf_verifier_env *env, int insn_idx)
{
struct bpf_verifier_state_list *new_sl;
struct bpf_verifier_state_list *sl;
- struct bpf_verifier_state *cur = env->cur_state;
+ struct bpf_verifier_state *cur = env->cur_state, *new;
int i, j, err;
sl = env->explored_states[insn_idx];
@@ -4593,16 +4492,18 @@ static int is_state_visited(struct bpf_verifier_env *env, int insn_idx)
return -ENOMEM;
/* add new state to the head of linked list */
- err = copy_verifier_state(&new_sl->state, cur);
+ new = &new_sl->state;
+ err = copy_verifier_state(new, cur);
if (err) {
- free_verifier_state(&new_sl->state, false);
+ free_verifier_state(new, false);
kfree(new_sl);
return err;
}
new_sl->next = env->explored_states[insn_idx];
env->explored_states[insn_idx] = new_sl;
/* connect new state to parentage chain */
- cur->parent = &new_sl->state;
+ for (i = 0; i < BPF_REG_FP; i++)
+ cur_regs(env)[i].parent = &new->frame[new->curframe]->regs[i];
/* clear write marks in current state: the writes we did are not writes
* our child did, so they don't screen off its reads from us.
* (There are no read marks in current state, because reads always mark
@@ -4615,9 +4516,13 @@ static int is_state_visited(struct bpf_verifier_env *env, int insn_idx)
/* all stack frames are accessible from callee, clear them all */
for (j = 0; j <= cur->curframe; j++) {
struct bpf_func_state *frame = cur->frame[j];
+ struct bpf_func_state *newframe = new->frame[j];
- for (i = 0; i < frame->allocated_stack / BPF_REG_SIZE; i++)
+ for (i = 0; i < frame->allocated_stack / BPF_REG_SIZE; i++) {
frame->stack[i].spilled_ptr.live = REG_LIVE_NONE;
+ frame->stack[i].spilled_ptr.parent =
+ &newframe->stack[i].spilled_ptr;
+ }
}
return 0;
}
@@ -4636,7 +4541,6 @@ static int do_check(struct bpf_verifier_env *env)
if (!state)
return -ENOMEM;
state->curframe = 0;
- state->parent = NULL;
state->frame[0] = kzalloc(sizeof(struct bpf_func_state), GFP_KERNEL);
if (!state->frame[0]) {
kfree(state);
^ permalink raw reply related [flat|nested] 10+ messages in thread* Re: [RFC PATCH v3 bpf-next 0/5] bpf/verifier: subprog/func_call simplifications
2018-04-06 17:11 [RFC PATCH v3 bpf-next 0/5] bpf/verifier: subprog/func_call simplifications Edward Cree
` (4 preceding siblings ...)
2018-04-06 17:15 ` [RFC PATCH v3 bpf-next 5/5] bpf/verifier: per-register parent pointers Edward Cree
@ 2018-04-10 12:54 ` Jiong Wang
5 siblings, 0 replies; 10+ messages in thread
From: Jiong Wang @ 2018-04-10 12:54 UTC (permalink / raw)
To: Edward Cree, Alexei Starovoitov, Daniel Borkmann; +Cc: netdev
On 06/04/2018 18:11, Edward Cree wrote:
> By storing subprog boundaries as a subprogno mark on each insn, rather than
> a start (and implicit end) for each subprog, the code handling subprogs can
> in various places be made simpler, more explicit, and more efficient (i.e.
> better asymptotic complexity).
IMHO, the subprog number might be much smaller than insn number, so just
keeping sorted subprog information in env->subprog_info and do bsearch
looks reasonable to me.
While the new added "subprogno" field is only used round find_subprog, so
I feel it is a little bit heavy to allocate a delicated field that wouldn't
be used broadly for each instruction.
> This also lays the ground for possible
> future work in which an extension of the check_subprogs() code to cover
> basic blocks could replace check_cfg(), which currently largely duplicates
> the insn-walking part.
I was thinking to remove the insn-walk duplication in the other way by
center them in the DFS insn-walk in check_cfg, as we can't remove that one
before we migrate to other loop detection method. This approach is
questionable though.
> Some other changes were also included to support this:
> * Per-subprog info is stored in env->subprog_info, an array of structs,
> rather than several arrays with a common index.
> * Subprog numbers and corresponding subprog_info index are now 0-based;
> subprog 0 is the main()-function of the program, starting at insn 0.
> * Call graph is now stored in the new bpf_subprog_info struct; used here
> for check_max_stack_depth() but may have other uses too.
Ack above changes which center all subprog related info into
env->subprog_info and the new addition of callee field.
^ permalink raw reply [flat|nested] 10+ messages in thread