| lists.openwall.net | lists / announce owl-users owl-dev john-users john-dev passwdqc-users yescrypt popa3d-users / oss-security kernel-hardening musl sabotage tlsify passwords / crypt-dev xvendor / Bugtraq Full-Disclosure linux-kernel linux-netdev linux-ext4 linux-hardening linux-cve-announce PHC | |
|
Open Source and information security mailing list archives
| ||
|
Date: Mon, 8 Oct 2018 21:18:41 +0100
From: Jiong Wang <jiong.wang@...ronome.com>
To: Alexei Starovoitov <alexei.starovoitov@...il.com>
Cc: Edward Cree <ecree@...arflare.com>, ast@...nel.org,
daniel@...earbox.net, netdev@...r.kernel.org
Subject: Re: [RFC PATCH v2 bpf-next 0/2] verifier liveness simplification
On 03/10/2018 17:53, Jiong Wang wrote:
> On 03/10/2018 16:59, Alexei Starovoitov wrote:
>> On Wed, Oct 03, 2018 at 04:36:31PM +0100, Jiong Wang wrote:
> <snip...>
>>> Now this hasn't happened. I am still debugging the root cause, but kind of
>>> feel
>>> "64-bit" attribute propagation is the issue, it seems to me it can't be
>>> nicely
>>> integrated into the existing register read/write propagation infrastructure.
>>
>> may be share your patches that modify the liveness propagation?
>
> OK, I will share it after some clean up.
Have done more experiments on the algo, and finally got something passed my
local tests. bpf selftest passed as well except several test_verifier failures
due to some corner cases I guess, will have a look later.
In these test, x86-64 is using the 32-bit information. In the insn loop inside
sanitize_dead_code, once an insn is not marked as 64-bit and if it is ALU64, it
will then be changed to ALU32. When enable tracking using printk, I could see
quite a few ALU64 instructions really are rewritten into ALU32, so tests like
test_l4lb runs OK looks like a positive signal of the correctness.
The algo separates the problem into two steps.
- First, assume there is no code path prune and all code paths will be walked
through. In this case, if we could propagate 64-bit info backward along the
use-def chains for all paths walked, one insn must will be marked as 64-bit
correctly. Finish this step requires building use-def chain, and it is done
in the following way:
1. each insn could have two explicit uses, so add two chain fields in
bpf_insn_aux_data.
2. we need finer enum to describe register use, so split SRC_OP into
SRC_OP_0, SRC_OP64_0, SRC_OP_1, SRC_OP64_1 to indicate the source
is the first/second source and whether it is a 64-bit source.
3. create the chain at check_reg_arg which is exactly covering all
register use sites. The function to create the chain is link_reg_to_def.
4. when creating the chain, if a source is a 64-bit source, also
propagating the information backward along use-def chain straight away.
This is done in mark_reg_read which further calls the new function
"mark_insn_64bit" which is doing the real job. "mark_insn_64bit" fetches
the def insn for the 64-bit source, and further marks the def insns of
its sources as 64-bit. This will be repeated until the whole use-def
chain consumed.
5. by use-def chain described above, if there is no code path prune, one
insn must have been marked as 64-bit when it's result has 64-bit use.
6. helper call causing implicit reg use and must be conservative treated
as 64-bit use, bpf-to-bpf function call has insn connected by use-def
so doesn't need to make that conservative assumption.
- Second, to handle code path prune, define new liveness enum
REG_LIVE_READ64 and REG_LIVE_UNIQUE_WRITTEN. The latter will only be
set if reg_arg_type is the new U_DST_OP or U_DST_OP_NO_MARK, and
REG_LIVE_READ64 will be set if one 64-bit read is not screened off by
REG_LIVE_UNIQUE_WRITTEN.
The thought is 64-bit use info will only be screened off if the dst register
is unique in all register operands, meaning not the same as any source. For
example, insn 18 below will screen off r4 64-bit propagation.
17: r3 += r7
18: r4 = 1
19: *(u64 *)(r10 - 32) = r3
20: *(u64 *)(r10 - 40) = r4
So, U_DST_OP/U_DST_OP_NO_MARK have been introduced to differentiate with
DST_OP/DST_OP_NO_MARK. Inside check_reg_arg, checks are done on dst_reg,
and would pass U_DST_* as reg_arg_type when it is unique. U_DST_* then
will set liveness to REG_LIVE_UNIQUE_WRITTEN. In side mark_reg_read, if
one 64-bit read is not screened off by REG_LIVE_UNIQUE_WRITTEN, then
REG_LIVE_READ64 will be set in the reg_state. REG_LIVE_READ64 further
triggers propagating downstream 64-bit uses from the pruned paths into the
current path inside propagate_liveness when path prune happened.
Compared with propagating REG_LIVE_READ, propagating REG_LIVE_READ64 needs
more work. Because one 64-bit read could indicating more than one registers
are 64-bit. For example, insn 19 above shows r3 is 64-bit source, so its
define at insn 17 are 64-bit, then all sources of insn 17 must be 64-bit,
meaning both r3 and r7 are 64-bit. Therefore, REG_LIVE_READ64 needs to be
propagated on both r3 and r7 upward along the register parentage chain.
During walking def-use chain, we record all such affected reg_state, and
propagate REG_LIVE_READ64 for all of them. This logic is done inside
mark_insn_64bit as well.
- For short, the implementation treating the new 64-bit info (REG_LIVE_READ64)
propagation the same as REG_LIVE_READ propagation.
REG_LIVE_READ triggers more path prune during state equal comparison, while
REG_LIVE_READ64 triggers 64-bit insn marking during def-use chain walking.
Use-def chain is separate from reg state parentage chain chain, the prior is
helping the later, reg states that needs REG_LIVE_READ64 propagation are
collected during use-def chain walking.
Please review the following implementation.
Thanks.
Regards,
Jiong
diff --git a/include/linux/bpf_verifier.h b/include/linux/bpf_verifier.h
index b42b60a..ea22f43 100644
--- a/include/linux/bpf_verifier.h
+++ b/include/linux/bpf_verifier.h
@@ -34,11 +34,15 @@
* but of the link between it and its parent. See mark_reg_read() and
* mark_stack_slot_read() in kernel/bpf/verifier.c.
*/
-enum bpf_reg_liveness {
- REG_LIVE_NONE = 0, /* reg hasn't been read or written this branch */
- REG_LIVE_READ, /* reg was read, so we're sensitive to initial value */
- REG_LIVE_WRITTEN, /* reg was written first, screening off later reads */
-};
+/* Reg hasn't been read or written this branch. */
+#define REG_LIVE_NONE 0
+/* Reg was read, so we're sensitive to initial value. */
+#define REG_LIVE_READ 0x1
+/* The read is also 64-bit. */
+#define REG_LIVE_READ64 0x2
+#define REG_LIVE_WRITTEN 0x4
+/* The write also should screen off 64-bit backward propagation. */
+#define REG_LIVE_UNIQUE_WRITTEN 0x8
struct bpf_reg_state {
/* Ordering of fields matters. See states_equal() */
@@ -85,7 +89,11 @@ struct bpf_reg_state {
* pointing to bpf_func_state.
*/
u32 frameno;
- enum bpf_reg_liveness live;
+ u32 live;
+ struct {
+ s16 active_def;
+ bool full_ref;
+ };
};
enum bpf_stack_slot_type {
@@ -145,6 +153,11 @@ struct bpf_insn_aux_data {
};
int ctx_field_size; /* the ctx field size for load insn, maybe 0 */
int sanitize_stack_off; /* stack slot to be cleared */
+ struct {
+ s16 def[2]; /* The insns defining the uses of this insn. */
+ bool full_ref; /* This insn should operate on full 64-bit. */
+ };
+ struct bpf_reg_state *reg_state;
bool seen; /* this insn was processed by the verifier */
};
diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c
index 8ccbff4..061345d 100644
--- a/kernel/bpf/verifier.c
+++ b/kernel/bpf/verifier.c
@@ -271,8 +271,7 @@ static char slot_type_char[] = {
[STACK_ZERO] = '0',
};
-static void print_liveness(struct bpf_verifier_env *env,
- enum bpf_reg_liveness live)
+static void print_liveness(struct bpf_verifier_env *env, u32 live)
{
if (live & (REG_LIVE_READ | REG_LIVE_WRITTEN))
verbose(env, "_");
@@ -755,6 +754,7 @@ static void init_reg_state(struct bpf_verifier_env *env,
mark_reg_not_init(env, regs, i);
regs[i].live = REG_LIVE_NONE;
regs[i].parent = NULL;
+ regs[i].active_def = -1;
}
/* frame pointer */
@@ -779,9 +779,16 @@ static void init_func_state(struct bpf_verifier_env *env,
}
enum reg_arg_type {
- SRC_OP, /* register is used as source operand */
+ SRC_OP_0, /* register is used as source operand */
+ SRC_OP64_0, /* likewise, and all 64 bits of the source matter */
+ SRC_OP_1, /* the second source */
+ SRC_OP64_1, /* likewise */
+ SRC_OP64_IMP, /* implicit source, always 64-bit */
+ SRC_OP_SPILL, /* stack spill */
DST_OP, /* register is used as destination operand */
- DST_OP_NO_MARK /* same as above, check only, don't mark */
+ U_DST_OP, /* likewise, and no overlap with any source */
+ DST_OP_NO_MARK, /* same as above, check only, don't mark */
+ U_DST_OP_NO_MARK/* likewise */
};
static int cmp_subprogs(const void *a, const void *b)
@@ -899,14 +906,101 @@ static int check_subprogs(struct bpf_verifier_env *env)
return 0;
}
+static void
+link_reg_to_def(struct bpf_verifier_env *env, const struct bpf_reg_state *rstate,
+ enum reg_arg_type read_t, s16 insn_idx)
+{
+ s16 slot_idx, def_idx;
+
+ if (insn_idx == -1)
+ return;
+
+ slot_idx = (read_t - SRC_OP_0) % 2;
+ def_idx = rstate->active_def;
+ env->insn_aux_data[insn_idx].def[slot_idx] = def_idx + 1;
+}
+
+/* Stack of insns to process, this is also used by check_cfg. */
+static int *insn_stack;
+
+struct prop_pair {
+ struct bpf_reg_state *reg_state;
+ u8 regno;
+};
+
+/* Mark insn upward along the chain, also propagate READ64 liveness. */
+static int mark_insn_64bit(struct bpf_verifier_env *env, int insn_idx)
+{
+ struct bpf_insn_aux_data *aux = env->insn_aux_data;
+ u16 u2d0, u2d1, stack_idx = 0, prop_idx = 0;
+ struct prop_pair *prop_stack;
+
+ prop_stack = kcalloc(1024, sizeof(struct prop_pair), GFP_KERNEL);
+ if (!prop_stack)
+ return -ENOMEM;
+
+ insn_stack[stack_idx++] = insn_idx;
+
+ while (stack_idx) {
+ u16 def_idx = insn_stack[--stack_idx];
+
+ if (!def_idx)
+ continue;
+
+ def_idx--;
+
+ aux[def_idx].full_ref = true;
+ u2d0 = aux[def_idx].def[0];
+ if (u2d0) {
+ insn_stack[stack_idx++] = u2d0;
+ prop_stack[prop_idx].reg_state = aux[def_idx].reg_state;
+ prop_stack[prop_idx++].regno =
+ env->prog->insnsi[u2d0 - 1].dst_reg;
+ }
+ u2d1 = aux[def_idx].def[1];
+ if (u2d1) {
+ insn_stack[stack_idx++] = u2d1;
+ prop_stack[prop_idx].reg_state = aux[def_idx].reg_state;
+ prop_stack[prop_idx++].regno =
+ env->prog->insnsi[u2d1 - 1].dst_reg;
+ }
+ }
+
+ while (prop_idx) {
+ struct prop_pair pair = prop_stack[--prop_idx];
+ struct bpf_reg_state *state, *parent;
+ u8 regno = pair.regno;
+
+ state = pair.reg_state + regno;
+ parent = state->parent;
+
+ while (parent) {
+ if (state->live & REG_LIVE_UNIQUE_WRITTEN)
+ break;
+
+ parent->live |= REG_LIVE_READ64;
+ state = parent;
+ parent = state->parent;
+ }
+ }
+
+ kfree(prop_stack);
+
+ return 0;
+}
+
/* 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_reg_state *state,
- struct bpf_reg_state *parent)
+ struct bpf_reg_state *parent, bool full_reg_read)
{
bool writes = parent == state->parent; /* Observe write marks */
+ const struct bpf_reg_state *orig_state = state;
+ struct bpf_reg_state *orig_parent = parent;
+ bool orig_writes = writes;
+ int def_idx;
while (parent) {
/* if read wasn't screened by an earlier write ... */
@@ -918,11 +1012,20 @@ static int mark_reg_read(struct bpf_verifier_env *env,
parent = state->parent;
writes = true;
}
- return 0;
+
+ writes = orig_writes;
+ parent = orig_parent;
+ state = orig_state;
+
+ def_idx = writes ? state->active_def : parent->active_def;
+ if (!full_reg_read || def_idx == -1)
+ return 0;
+
+ return mark_insn_64bit(env, def_idx + 1);
}
static int check_reg_arg(struct bpf_verifier_env *env, u32 regno,
- enum reg_arg_type t)
+ enum reg_arg_type t, s16 insn_idx)
{
struct bpf_verifier_state *vstate = env->cur_state;
struct bpf_func_state *state = vstate->frame[vstate->curframe];
@@ -933,16 +1036,24 @@ static int check_reg_arg(struct bpf_verifier_env *env, u32 regno,
return -EINVAL;
}
- if (t == SRC_OP) {
+ if (t == SRC_OP_0 || t == SRC_OP_1 ||
+ t == SRC_OP64_0 || t == SRC_OP64_1 || t == SRC_OP64_IMP) {
+ struct bpf_reg_state *rstate = regs + regno;
+
/* check whether register used as source operand can be read */
- if (regs[regno].type == NOT_INIT) {
+ if (rstate->type == NOT_INIT) {
verbose(env, "R%d !read_ok\n", regno);
return -EACCES;
}
+
+ link_reg_to_def(env, rstate, t, insn_idx);
+
/* 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);
+ return mark_reg_read(env, rstate, rstate->parent,
+ t == SRC_OP64_0 ||
+ t == SRC_OP64_1 ||
+ t == SRC_OP64_IMP);
} else {
/* check whether register used as dest operand can be written to */
if (regno == BPF_REG_FP) {
@@ -950,8 +1061,14 @@ static int check_reg_arg(struct bpf_verifier_env *env, u32 regno,
return -EACCES;
}
regs[regno].live |= REG_LIVE_WRITTEN;
- if (t == DST_OP)
+ if (t == U_DST_OP || t == U_DST_OP_NO_MARK)
+ regs[regno].live |= REG_LIVE_UNIQUE_WRITTEN;
+ if (t == DST_OP || t == U_DST_OP)
mark_reg_unknown(env, regs, regno);
+ regs[regno].active_def = insn_idx;
+ if (insn_idx != -1) {
+ env->insn_aux_data[insn_idx].reg_state = regs;
+ }
}
return 0;
}
@@ -1118,7 +1235,8 @@ static int check_stack_read(struct bpf_verifier_env *env,
state->regs[value_regno].live |= REG_LIVE_WRITTEN;
}
mark_reg_read(env, ®_state->stack[spi].spilled_ptr,
- reg_state->stack[spi].spilled_ptr.parent);
+ reg_state->stack[spi].spilled_ptr.parent,
+ SRC_OP_SPILL);
return 0;
} else {
int zeros = 0;
@@ -1135,7 +1253,8 @@ static int check_stack_read(struct bpf_verifier_env *env,
return -EACCES;
}
mark_reg_read(env, ®_state->stack[spi].spilled_ptr,
- reg_state->stack[spi].spilled_ptr.parent);
+ reg_state->stack[spi].spilled_ptr.parent,
+ SRC_OP_SPILL);
if (value_regno >= 0) {
if (zeros == size) {
/* any size read into register is zero extended,
@@ -1735,23 +1854,26 @@ static int check_mem_access(struct bpf_verifier_env *env, int insn_idx, u32 regn
return err;
}
-static int check_xadd(struct bpf_verifier_env *env, int insn_idx, struct bpf_insn *insn)
+static int
+check_xadd(struct bpf_verifier_env *env, int insn_idx, struct bpf_insn *insn)
{
+ bool is_xadd_64 = BPF_SIZE(insn->code) == BPF_DW;
+ bool is_xadd_32 = BPF_SIZE(insn->code) == BPF_W;
int err;
- if ((BPF_SIZE(insn->code) != BPF_W && BPF_SIZE(insn->code) != BPF_DW) ||
- insn->imm != 0) {
+ if (!(is_xadd_32 || is_xadd_64) || insn->imm != 0) {
verbose(env, "BPF_XADD uses reserved fields\n");
return -EINVAL;
}
/* check src1 operand */
- err = check_reg_arg(env, insn->src_reg, SRC_OP);
+ err = check_reg_arg(env, insn->src_reg,
+ is_xadd_32 ? SRC_OP_0 : SRC_OP64_0, insn_idx);
if (err)
return err;
/* check src2 operand */
- err = check_reg_arg(env, insn->dst_reg, SRC_OP);
+ err = check_reg_arg(env, insn->dst_reg, SRC_OP64_1, insn_idx);
if (err)
return err;
@@ -1852,7 +1974,8 @@ static int check_stack_boundary(struct bpf_verifier_env *env, int regno,
* the whole slot to be marked as 'read'
*/
mark_reg_read(env, &state->stack[spi].spilled_ptr,
- state->stack[spi].spilled_ptr.parent);
+ state->stack[spi].spilled_ptr.parent,
+ SRC_OP_SPILL);
}
return update_stack_depth(env, state, off);
}
@@ -1903,7 +2026,7 @@ static int check_func_arg(struct bpf_verifier_env *env, u32 regno,
if (arg_type == ARG_DONTCARE)
return 0;
- err = check_reg_arg(env, regno, SRC_OP);
+ err = check_reg_arg(env, regno, SRC_OP64_IMP, -1);
if (err)
return err;
@@ -2320,7 +2443,7 @@ static int check_func_call(struct bpf_verifier_env *env, struct bpf_insn *insn,
/* 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);
+ check_reg_arg(env, caller_saved[i], DST_OP_NO_MARK, -1);
}
/* only increment it after check_reg_arg() finished */
@@ -2510,7 +2633,7 @@ static int check_helper_call(struct bpf_verifier_env *env, int func_id, int insn
/* reset caller saved regs */
for (i = 0; i < CALLER_SAVED_REGS; i++) {
mark_reg_not_init(env, regs, caller_saved[i]);
- check_reg_arg(env, caller_saved[i], DST_OP_NO_MARK);
+ check_reg_arg(env, caller_saved[i], DST_OP_NO_MARK, -1);
}
/* update return register (already marked as written above) */
@@ -3161,7 +3284,10 @@ static int check_alu_op(struct bpf_verifier_env *env, struct bpf_insn *insn)
{
struct bpf_reg_state *regs = cur_regs(env);
u8 opcode = BPF_OP(insn->code);
- int err;
+ enum reg_arg_type dst_type;
+ int err, insn_idx;
+
+ insn_idx = insn - env->prog->insnsi;
if (opcode == BPF_END || opcode == BPF_NEG) {
if (opcode == BPF_NEG) {
@@ -3181,7 +3307,7 @@ static int check_alu_op(struct bpf_verifier_env *env, struct bpf_insn *insn)
}
/* check src operand */
- err = check_reg_arg(env, insn->dst_reg, SRC_OP);
+ err = check_reg_arg(env, insn->dst_reg, SRC_OP_0, insn_idx);
if (err)
return err;
@@ -3191,8 +3317,9 @@ static int check_alu_op(struct bpf_verifier_env *env, struct bpf_insn *insn)
return -EACCES;
}
+ dst_type = insn->dst_reg != insn->src_reg ? U_DST_OP : DST_OP;
/* check dest operand */
- err = check_reg_arg(env, insn->dst_reg, DST_OP);
+ err = check_reg_arg(env, insn->dst_reg, dst_type, insn_idx);
if (err)
return err;
@@ -3205,18 +3332,24 @@ static int check_alu_op(struct bpf_verifier_env *env, struct bpf_insn *insn)
}
/* check src operand */
- err = check_reg_arg(env, insn->src_reg, SRC_OP);
+ err = check_reg_arg(env, insn->src_reg, SRC_OP_0,
+ insn_idx);
if (err)
return err;
+
+ dst_type = insn->dst_reg != insn->src_reg ?
+ U_DST_OP_NO_MARK : DST_OP_NO_MARK;
} else {
if (insn->src_reg != BPF_REG_0 || insn->off != 0) {
verbose(env, "BPF_MOV uses reserved fields\n");
return -EINVAL;
}
+
+ dst_type = U_DST_OP_NO_MARK;
}
/* check dest operand, mark as required later */
- err = check_reg_arg(env, insn->dst_reg, DST_OP_NO_MARK);
+ err = check_reg_arg(env, insn->dst_reg, dst_type, insn_idx);
if (err)
return err;
@@ -3225,8 +3358,12 @@ static int check_alu_op(struct bpf_verifier_env *env, struct bpf_insn *insn)
/* case: R1 = R2
* copy register state to dest reg
*/
+ u32 live_old = regs[insn->dst_reg].live;
+ s16 def_old = regs[insn->dst_reg].active_def;
+
regs[insn->dst_reg] = regs[insn->src_reg];
- regs[insn->dst_reg].live |= REG_LIVE_WRITTEN;
+ regs[insn->dst_reg].live |= live_old;
+ regs[insn->dst_reg].active_def = def_old;
} else {
/* R1 = (u32) R2 */
if (is_pointer_value(env, insn->src_reg)) {
@@ -3266,18 +3403,23 @@ static int check_alu_op(struct bpf_verifier_env *env, struct bpf_insn *insn)
return -EINVAL;
}
/* check src1 operand */
- err = check_reg_arg(env, insn->src_reg, SRC_OP);
+ err = check_reg_arg(env, insn->src_reg, SRC_OP_0,
+ insn_idx);
if (err)
return err;
+ dst_type = insn->dst_reg != insn->src_reg ?
+ U_DST_OP_NO_MARK : DST_OP_NO_MARK;
} else {
if (insn->src_reg != BPF_REG_0 || insn->off != 0) {
verbose(env, "BPF_ALU uses reserved fields\n");
return -EINVAL;
}
+
+ dst_type = DST_OP_NO_MARK;
}
/* check src2 operand */
- err = check_reg_arg(env, insn->dst_reg, SRC_OP);
+ err = check_reg_arg(env, insn->dst_reg, SRC_OP_1, insn_idx);
if (err)
return err;
@@ -3303,7 +3445,7 @@ static int check_alu_op(struct bpf_verifier_env *env, struct bpf_insn *insn)
}
/* check dest operand */
- err = check_reg_arg(env, insn->dst_reg, DST_OP_NO_MARK);
+ err = check_reg_arg(env, insn->dst_reg, dst_type, insn_idx);
if (err)
return err;
@@ -3759,6 +3901,7 @@ static int check_cond_jmp_op(struct bpf_verifier_env *env,
struct bpf_reg_state *regs = this_branch->frame[this_branch->curframe]->regs;
struct bpf_reg_state *dst_reg, *other_branch_regs;
u8 opcode = BPF_OP(insn->code);
+ int old_insn_idx = *insn_idx;
int err;
if (opcode > BPF_JSLE) {
@@ -3773,7 +3916,8 @@ static int check_cond_jmp_op(struct bpf_verifier_env *env,
}
/* check src1 operand */
- err = check_reg_arg(env, insn->src_reg, SRC_OP);
+ err = check_reg_arg(env, insn->src_reg, SRC_OP64_0,
+ old_insn_idx);
if (err)
return err;
@@ -3790,7 +3934,7 @@ static int check_cond_jmp_op(struct bpf_verifier_env *env,
}
/* check src2 operand */
- err = check_reg_arg(env, insn->dst_reg, SRC_OP);
+ err = check_reg_arg(env, insn->dst_reg, SRC_OP64_1, old_insn_idx);
if (err)
return err;
@@ -3896,7 +4040,8 @@ static int check_ld_imm(struct bpf_verifier_env *env, struct bpf_insn *insn)
return -EINVAL;
}
- err = check_reg_arg(env, insn->dst_reg, DST_OP);
+ err = check_reg_arg(env, insn->dst_reg, U_DST_OP,
+ insn - env->prog->insnsi);
if (err)
return err;
@@ -3945,9 +4090,9 @@ static bool may_access_skb(enum bpf_prog_type type)
*/
static int check_ld_abs(struct bpf_verifier_env *env, struct bpf_insn *insn)
{
+ int i, err, insn_idx = insn - env->prog->insnsi;
struct bpf_reg_state *regs = cur_regs(env);
u8 mode = BPF_MODE(insn->code);
- int i, err;
if (!may_access_skb(env->prog->type)) {
verbose(env, "BPF_LD_[ABS|IND] instructions not allowed for this program type\n");
@@ -3979,7 +4124,7 @@ static int check_ld_abs(struct bpf_verifier_env *env, struct bpf_insn *insn)
}
/* check whether implicit source operand (register R6) is readable */
- err = check_reg_arg(env, BPF_REG_6, SRC_OP);
+ err = check_reg_arg(env, BPF_REG_6, SRC_OP64_1, insn_idx);
if (err)
return err;
@@ -3991,7 +4136,7 @@ static int check_ld_abs(struct bpf_verifier_env *env, struct bpf_insn *insn)
if (mode == BPF_IND) {
/* check explicit source operand */
- err = check_reg_arg(env, insn->src_reg, SRC_OP);
+ err = check_reg_arg(env, insn->src_reg, SRC_OP_0, insn_idx);
if (err)
return err;
}
@@ -3999,7 +4144,7 @@ static int check_ld_abs(struct bpf_verifier_env *env, struct bpf_insn *insn)
/* reset caller saved regs to unreadable */
for (i = 0; i < CALLER_SAVED_REGS; i++) {
mark_reg_not_init(env, regs, caller_saved[i]);
- check_reg_arg(env, caller_saved[i], DST_OP_NO_MARK);
+ check_reg_arg(env, caller_saved[i], DST_OP_NO_MARK, -1);
}
/* mark destination R0 register as readable, since it contains
@@ -4091,7 +4236,6 @@ enum {
#define STATE_LIST_MARK ((struct bpf_verifier_state_list *) -1L)
-static int *insn_stack; /* stack of insns to process */
static int cur_stack; /* current stack index */
static int *insn_state;
@@ -4554,10 +4698,11 @@ static bool states_equal(struct bpf_verifier_env *env,
*/
static int propagate_liveness(struct bpf_verifier_env *env,
const struct bpf_verifier_state *vstate,
- struct bpf_verifier_state *vparent)
+ struct bpf_verifier_state *vparent, int insn_idx)
{
- int i, frame, err = 0;
+ struct bpf_reg_state *regs, *parent_regs;
struct bpf_func_state *state, *parent;
+ int i, frame, err = 0;
if (vparent->curframe != vstate->curframe) {
WARN(1, "propagate_live: parent frame %d current frame %d\n",
@@ -4566,13 +4711,24 @@ static int propagate_liveness(struct bpf_verifier_env *env,
}
/* Propagate read liveness of registers... */
BUILD_BUG_ON(BPF_REG_FP + 1 != MAX_BPF_REG);
+ parent_regs = vparent->frame[vparent->curframe]->regs;
+ regs = vstate->frame[vparent->curframe]->regs;
/* We don't need to worry about FP liveness because it's read-only */
for (i = 0; i < BPF_REG_FP; i++) {
- if (vparent->frame[vparent->curframe]->regs[i].live & REG_LIVE_READ)
+ if (!(parent_regs[i].live & REG_LIVE_READ64) &&
+ regs[i].live & REG_LIVE_READ64) {
+ err = mark_reg_read(env, ®s[i], &parent_regs[i],
+ true);
+ if (err)
+ return err;
continue;
- if (vstate->frame[vstate->curframe]->regs[i].live & REG_LIVE_READ) {
- err = mark_reg_read(env, &vstate->frame[vstate->curframe]->regs[i],
- &vparent->frame[vstate->curframe]->regs[i]);
+ }
+
+ if (parent_regs[i].live & REG_LIVE_READ)
+ continue;
+ if (regs[i].live & REG_LIVE_READ) {
+ err = mark_reg_read(env, ®s[i], &parent_regs[i],
+ false);
if (err)
return err;
}
@@ -4588,7 +4744,8 @@ static int propagate_liveness(struct bpf_verifier_env *env,
continue;
if (state->stack[i].spilled_ptr.live & REG_LIVE_READ)
mark_reg_read(env, &state->stack[i].spilled_ptr,
- &parent->stack[i].spilled_ptr);
+ &parent->stack[i].spilled_ptr,
+ false);
}
}
return err;
@@ -4620,7 +4777,7 @@ static int is_state_visited(struct bpf_verifier_env *env, int insn_idx)
* they'll be immediately forgotten as we're pruning
* this state and will pop a new one.
*/
- err = propagate_liveness(env, &sl->state, cur);
+ err = propagate_liveness(env, &sl->state, cur, insn_idx);
if (err)
return err;
return 1;
@@ -4699,6 +4856,12 @@ static int do_check(struct bpf_verifier_env *env)
BPF_MAIN_FUNC /* callsite */,
0 /* frameno */,
0 /* subprogno, zero == main subprog */);
+
+ /* insn_stack will be used by propagate_64bit_usage. */
+ insn_stack = kcalloc(insn_cnt * 2, sizeof(int), GFP_KERNEL);
+ if (!insn_stack)
+ return -ENOMEM;
+
insn_idx = 0;
for (;;) {
struct bpf_insn *insn;
@@ -4779,11 +4942,13 @@ static int do_check(struct bpf_verifier_env *env)
/* check for reserved fields is already done */
/* check src operand */
- err = check_reg_arg(env, insn->src_reg, SRC_OP);
+ err = check_reg_arg(env, insn->src_reg, SRC_OP64_0,
+ insn_idx);
if (err)
return err;
- err = check_reg_arg(env, insn->dst_reg, DST_OP_NO_MARK);
+ err = check_reg_arg(env, insn->dst_reg,
+ U_DST_OP_NO_MARK, insn_idx);
if (err)
return err;
@@ -4823,6 +4988,12 @@ static int do_check(struct bpf_verifier_env *env)
} else if (class == BPF_STX) {
enum bpf_reg_type *prev_dst_type, dst_reg_type;
+ enum reg_arg_type source_type;
+
+ /* Let the back-end decide which insn to use according
+ * to store width.
+ */
+ env->insn_aux_data[insn_idx].full_ref = true;
if (BPF_MODE(insn->code) == BPF_XADD) {
err = check_xadd(env, insn_idx, insn);
@@ -4832,12 +5003,17 @@ static int do_check(struct bpf_verifier_env *env)
continue;
}
+ source_type = BPF_SIZE(insn->code) == BPF_DW ?
+ SRC_OP64_0 : SRC_OP_0;
+
/* check src1 operand */
- err = check_reg_arg(env, insn->src_reg, SRC_OP);
+ err = check_reg_arg(env, insn->src_reg, source_type,
+ insn_idx);
if (err)
return err;
/* check src2 operand */
- err = check_reg_arg(env, insn->dst_reg, SRC_OP);
+ err = check_reg_arg(env, insn->dst_reg, SRC_OP64_1,
+ insn_idx);
if (err)
return err;
@@ -4867,8 +5043,12 @@ static int do_check(struct bpf_verifier_env *env)
verbose(env, "BPF_ST uses reserved fields\n");
return -EINVAL;
}
+
+ env->insn_aux_data[insn_idx].full_ref = true;
+
/* check src operand */
- err = check_reg_arg(env, insn->dst_reg, SRC_OP);
+ err = check_reg_arg(env, insn->dst_reg, SRC_OP64_0,
+ insn_idx);
if (err)
return err;
@@ -4888,6 +5068,12 @@ static int do_check(struct bpf_verifier_env *env)
} else if (class == BPF_JMP) {
u8 opcode = BPF_OP(insn->code);
+ /* TODO: could potentially use range info to check if
+ * the comparison setting condition could be done on
+ * 32-bit sub-register.
+ */
+ env->insn_aux_data[insn_idx].full_ref = true;
+
if (opcode == BPF_CALL) {
if (BPF_SRC(insn->code) != BPF_K ||
insn->off != 0 ||
@@ -4918,6 +5104,9 @@ static int do_check(struct bpf_verifier_env *env)
continue;
} else if (opcode == BPF_EXIT) {
+ bool is_main_exit;
+ u32 frame_idx;
+
if (BPF_SRC(insn->code) != BPF_K ||
insn->imm != 0 ||
insn->src_reg != BPF_REG_0 ||
@@ -4926,7 +5115,8 @@ static int do_check(struct bpf_verifier_env *env)
return -EINVAL;
}
- if (state->curframe) {
+ frame_idx = state->curframe;
+ if (frame_idx) {
/* exit from nested function */
prev_insn_idx = insn_idx;
err = prepare_func_exit(env, &insn_idx);
@@ -4942,7 +5132,12 @@ static int do_check(struct bpf_verifier_env *env)
* of bpf_exit, which means that program wrote
* something into it earlier
*/
- err = check_reg_arg(env, BPF_REG_0, SRC_OP);
+ is_main_exit =
+ !state->frame[frame_idx]->subprogno;
+ err = check_reg_arg(env, BPF_REG_0,
+ is_main_exit ?
+ SRC_OP64_0 :SRC_OP_0,
+ insn_idx);
if (err)
return err;
@@ -5267,6 +5462,13 @@ static void sanitize_dead_code(struct bpf_verifier_env *env)
int i;
for (i = 0; i < insn_cnt; i++) {
+ /* Demonstration the usage of "full_ref" info. We could rewrite
+ * BPF_ALU64 into BPF_ALU. 64-bit architecture could
+ * then automatically get more 32-bit sub-register.
+ */
+ if (!aux_data[i].full_ref &&
+ BPF_CLASS(insn[i].code) == BPF_ALU64)
+ insn[i].code = (insn[i].code & ~0x7) | BPF_ALU;
if (aux_data[i].seen)
continue;
memcpy(insn + i, &trap, sizeof(trap));
@@ -5910,11 +6112,13 @@ int bpf_check(struct bpf_prog **prog, union bpf_attr *attr)
if (ret < 0)
goto skip_full_check;
+ insn_stack = NULL;
ret = do_check(env);
if (env->cur_state) {
free_verifier_state(env->cur_state, true);
env->cur_state = NULL;
}
+ kfree(insn_stack);
skip_full_check:
while (!pop_stack(env, NULL, NULL));
Powered by blists - more mailing lists