| Message ID | 1553623539-15474-4-git-send-email-jiong.wang@netronome.com |
|---|---|
| State | RFC |
| Delegated to: | BPF Maintainers |
| Headers | show |
| Series | bpf: eliminate zero extensions for sub-register writes | expand |
On Tue, Mar 26, 2019 at 7:06 PM Jiong Wang <jiong.wang@netronome.com> wrote: > > In previous patch, we have split register arg type for sub-register read, > but haven't touch read liveness. > > This patch further split read liveness into REG_LIVE_READ64 and > REG_LIVE_READ32. Liveness propagation code are updated accordingly. > > After this split, customized actions could be defined when propagating full > register read (REG_LIVE_READ64) or sub-register read (REG_LIVE_READ32). > > Signed-off-by: Jiong Wang <jiong.wang@netronome.com> [...] > @@ -1374,7 +1374,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, > + size == BPF_REG_SIZE); Isn't it possible to use a 4-byte read on the upper half of an 8-byte stack slot? > if (value_regno >= 0) { > if (zeros == size) { > /* any size read into register is zero extended, > @@ -2220,7 +2221,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, > + access_size == BPF_REG_SIZE); Same thing as above. > } > return update_stack_depth(env, state, off); > } [...]
Jann Horn writes: > On Tue, Mar 26, 2019 at 7:06 PM Jiong Wang <jiong.wang@netronome.com> wrote: >> >> In previous patch, we have split register arg type for sub-register read, >> but haven't touch read liveness. >> >> This patch further split read liveness into REG_LIVE_READ64 and >> REG_LIVE_READ32. Liveness propagation code are updated accordingly. >> >> After this split, customized actions could be defined when propagating full >> register read (REG_LIVE_READ64) or sub-register read (REG_LIVE_READ32). >> >> Signed-off-by: Jiong Wang <jiong.wang@netronome.com> > [...] >> @@ -1374,7 +1374,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, >> + size == BPF_REG_SIZE); > > Isn't it possible to use a 4-byte read on the upper half of an 8-byte > stack slot? I think that's fine, and is irrelevant with zero-extension on register. If it is a 8-byte stack slot comes from spill of register, then the definition of the register should have been marked as needing zero-extension if that register was generated by sub-register write. Regards, Jiong > >> if (value_regno >= 0) { >> if (zeros == size) { >> /* any size read into register is zero extended, >> @@ -2220,7 +2221,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, >> + access_size == BPF_REG_SIZE); > > Same thing as above. > >> } >> return update_stack_depth(env, state, off); >> } > [...]
On Tue, Mar 26, 2019 at 06:05:26PM +0000, Jiong Wang wrote: > In previous patch, we have split register arg type for sub-register read, > but haven't touch read liveness. > > This patch further split read liveness into REG_LIVE_READ64 and > REG_LIVE_READ32. Liveness propagation code are updated accordingly. > > After this split, customized actions could be defined when propagating full > register read (REG_LIVE_READ64) or sub-register read (REG_LIVE_READ32). > > Signed-off-by: Jiong Wang <jiong.wang@netronome.com> > --- > include/linux/bpf_verifier.h | 9 ++++++--- > kernel/bpf/verifier.c | 30 +++++++++++++++++++++--------- > 2 files changed, 27 insertions(+), 12 deletions(-) > > diff --git a/include/linux/bpf_verifier.h b/include/linux/bpf_verifier.h > index f03c86a..27761ab 100644 > --- a/include/linux/bpf_verifier.h > +++ b/include/linux/bpf_verifier.h > @@ -37,11 +37,14 @@ > /* Reg hasn't been read or written this branch. */ > #define REG_LIVE_NONE 0x0 > /* Reg was read, so we're sensitive to initial value. */ > -#define REG_LIVE_READ 0x1 > +#define REG_LIVE_READ32 0x1 > +/* Likewise, but full 64-bit content matters. */ > +#define REG_LIVE_READ64 0x2 > +#define REG_LIVE_READ (REG_LIVE_READ32 | REG_LIVE_READ64) > /* Reg was written first, screening off later reads. */ > -#define REG_LIVE_WRITTEN 0x2 > +#define REG_LIVE_WRITTEN 0x4 > /* Liveness won't be updating this register anymore. */ > -#define REG_LIVE_DONE 0x4 > +#define REG_LIVE_DONE 0x8 > > struct bpf_reg_state { > /* Ordering of fields matters. See states_equal() */ > diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c > index 245bb3c..b95c438 100644 > --- a/kernel/bpf/verifier.c > +++ b/kernel/bpf/verifier.c > @@ -1126,7 +1126,7 @@ static int check_subprogs(struct bpf_verifier_env *env) > */ > 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 dw_read) > { > bool writes = parent == state->parent; /* Observe write marks */ > > @@ -1141,7 +1141,7 @@ static int mark_reg_read(struct bpf_verifier_env *env, > return -EFAULT; > } > /* ... then we depend on parent's value */ > - parent->live |= REG_LIVE_READ; > + parent->live |= dw_read ? REG_LIVE_READ64 : REG_LIVE_READ32; > state = parent; > parent = state->parent; > writes = true; > @@ -1170,7 +1170,7 @@ static int check_reg_arg(struct bpf_verifier_env *env, u32 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); > + regs[regno].parent, true); > } else { > /* check whether register used as dest operand can be written to */ > if (regno == BPF_REG_FP) { > @@ -1357,7 +1357,7 @@ 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, true); > return 0; > } else { > int zeros = 0; > @@ -1374,7 +1374,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, > + size == BPF_REG_SIZE); > if (value_regno >= 0) { > if (zeros == size) { > /* any size read into register is zero extended, > @@ -2220,7 +2221,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, > + access_size == BPF_REG_SIZE); > } > return update_stack_depth(env, state, off); > } > @@ -6059,7 +6061,7 @@ static int propagate_liveness_reg(struct bpf_verifier_env *env, > if (parent_reg->live & flag || !(reg->live & flag)) > return 0; > > - err = mark_reg_read(env, reg, parent_reg); > + err = mark_reg_read(env, reg, parent_reg, flag == REG_LIVE_READ64); > if (err) > return err; > > @@ -6092,7 +6094,12 @@ static int propagate_liveness(struct bpf_verifier_env *env, > regs = vstate->frame[vstate->curframe]->regs; > /* We don't need to worry about FP liveness because it's read-only */ > for (i = 0; i < BPF_REG_FP; i++) { > - err = propagate_liveness_reg(env, ®s[i], &parent_regs[i]); > + err = propagate_liveness_reg(env, ®s[i], &parent_regs[i], > + REG_LIVE_READ64); > + if (err < 0) > + return err; > + err = propagate_liveness_reg(env, ®s[i], &parent_regs[i], > + REG_LIVE_READ32); so the parentage chain will be walked twice. Please do it in one loop. It's already slow. I'm working on patches that speed up this walk, but doing it twice is wasteful regardless.
diff --git a/include/linux/bpf_verifier.h b/include/linux/bpf_verifier.h index f03c86a..27761ab 100644 --- a/include/linux/bpf_verifier.h +++ b/include/linux/bpf_verifier.h @@ -37,11 +37,14 @@ /* Reg hasn't been read or written this branch. */ #define REG_LIVE_NONE 0x0 /* Reg was read, so we're sensitive to initial value. */ -#define REG_LIVE_READ 0x1 +#define REG_LIVE_READ32 0x1 +/* Likewise, but full 64-bit content matters. */ +#define REG_LIVE_READ64 0x2 +#define REG_LIVE_READ (REG_LIVE_READ32 | REG_LIVE_READ64) /* Reg was written first, screening off later reads. */ -#define REG_LIVE_WRITTEN 0x2 +#define REG_LIVE_WRITTEN 0x4 /* Liveness won't be updating this register anymore. */ -#define REG_LIVE_DONE 0x4 +#define REG_LIVE_DONE 0x8 struct bpf_reg_state { /* Ordering of fields matters. See states_equal() */ diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c index 245bb3c..b95c438 100644 --- a/kernel/bpf/verifier.c +++ b/kernel/bpf/verifier.c @@ -1126,7 +1126,7 @@ static int check_subprogs(struct bpf_verifier_env *env) */ 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 dw_read) { bool writes = parent == state->parent; /* Observe write marks */ @@ -1141,7 +1141,7 @@ static int mark_reg_read(struct bpf_verifier_env *env, return -EFAULT; } /* ... then we depend on parent's value */ - parent->live |= REG_LIVE_READ; + parent->live |= dw_read ? REG_LIVE_READ64 : REG_LIVE_READ32; state = parent; parent = state->parent; writes = true; @@ -1170,7 +1170,7 @@ static int check_reg_arg(struct bpf_verifier_env *env, u32 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); + regs[regno].parent, true); } else { /* check whether register used as dest operand can be written to */ if (regno == BPF_REG_FP) { @@ -1357,7 +1357,7 @@ 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, true); return 0; } else { int zeros = 0; @@ -1374,7 +1374,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, + size == BPF_REG_SIZE); if (value_regno >= 0) { if (zeros == size) { /* any size read into register is zero extended, @@ -2220,7 +2221,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, + access_size == BPF_REG_SIZE); } return update_stack_depth(env, state, off); } @@ -6059,7 +6061,7 @@ static int propagate_liveness_reg(struct bpf_verifier_env *env, if (parent_reg->live & flag || !(reg->live & flag)) return 0; - err = mark_reg_read(env, reg, parent_reg); + err = mark_reg_read(env, reg, parent_reg, flag == REG_LIVE_READ64); if (err) return err; @@ -6092,7 +6094,12 @@ static int propagate_liveness(struct bpf_verifier_env *env, regs = vstate->frame[vstate->curframe]->regs; /* We don't need to worry about FP liveness because it's read-only */ for (i = 0; i < BPF_REG_FP; i++) { - err = propagate_liveness_reg(env, ®s[i], &parent_regs[i]); + err = propagate_liveness_reg(env, ®s[i], &parent_regs[i], + REG_LIVE_READ64); + if (err < 0) + return err; + err = propagate_liveness_reg(env, ®s[i], &parent_regs[i], + REG_LIVE_READ32); if (err < 0) return err; } @@ -6107,7 +6114,12 @@ static int propagate_liveness(struct bpf_verifier_env *env, parent_reg = &parent->stack[i].spilled_ptr; reg = &state->stack[i].spilled_ptr; - err = propagate_liveness_reg(env, reg, parent_reg); + err = propagate_liveness_reg(env, reg, parent_reg, + REG_LIVE_READ64); + if (err < 0) + return err; + err = propagate_liveness_reg(env, reg, parent_reg, + REG_LIVE_READ32); if (err < 0) return err; }
In previous patch, we have split register arg type for sub-register read, but haven't touch read liveness. This patch further split read liveness into REG_LIVE_READ64 and REG_LIVE_READ32. Liveness propagation code are updated accordingly. After this split, customized actions could be defined when propagating full register read (REG_LIVE_READ64) or sub-register read (REG_LIVE_READ32). Signed-off-by: Jiong Wang <jiong.wang@netronome.com> --- include/linux/bpf_verifier.h | 9 ++++++--- kernel/bpf/verifier.c | 30 +++++++++++++++++++++--------- 2 files changed, 27 insertions(+), 12 deletions(-)