[RFC PATCH v3 bpf-next 1/5] bpf/verifier: store subprog info in struct bpf_subprog_info

Edward Cree
2018-04-06T17:14:21Z

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) {