| Message ID | 1556880164-10689-5-git-send-email-jiong.wang@netronome.com |
|---|---|
| State | Changes Requested |
| Delegated to: | BPF Maintainers |
| Headers | show |
| Series | bpf: eliminate zero extensions for sub-register writes | expand |
On Fri, May 03, 2019 at 11:42:31AM +0100, Jiong Wang wrote: > This patch introduce new alu32 insn BPF_ZEXT, and allocate the unused > opcode 0xe0 to it. > > Compared with the other alu32 insns, zero extension on low 32-bit is the > only semantics for this instruction. It also allows various JIT back-ends > to do optimal zero extension code-gen. > > BPF_ZEXT is supposed to be encoded with BPF_ALU only, and is supposed to be > generated by the latter 32-bit optimization code inside verifier for those > arches that do not support hardware implicit zero extension only. > > It is not supposed to be used in user's program directly at the moment. > Therefore, no need to recognize it inside generic verification code. It > just need to be supported for execution on interpreter or related JIT > back-ends. uapi and the doc define it, but "it is not supposed to be used" ?! > Signed-off-by: Jiong Wang <jiong.wang@netronome.com> > --- > Documentation/networking/filter.txt | 10 ++++++++++ > include/uapi/linux/bpf.h | 3 +++ > kernel/bpf/core.c | 4 ++++ > tools/include/uapi/linux/bpf.h | 3 +++ > 4 files changed, 20 insertions(+) > > diff --git a/Documentation/networking/filter.txt b/Documentation/networking/filter.txt > index 319e5e0..1cb3e42 100644 > --- a/Documentation/networking/filter.txt > +++ b/Documentation/networking/filter.txt > @@ -903,6 +903,16 @@ If BPF_CLASS(code) == BPF_ALU or BPF_ALU64 [ in eBPF ], BPF_OP(code) is one of: > BPF_MOV 0xb0 /* eBPF only: mov reg to reg */ > BPF_ARSH 0xc0 /* eBPF only: sign extending shift right */ > BPF_END 0xd0 /* eBPF only: endianness conversion */ > + BPF_ZEXT 0xe0 /* eBPF BPF_ALU only: zero-extends low 32-bit */ > + > +Compared with BPF_ALU | BPF_MOV which zero-extends low 32-bit implicitly, > +BPF_ALU | BPF_ZEXT zero-extends low 32-bit explicitly. Such zero extension is wait. that's an excellent observation. alu|mov is exactly it. we do not need another insn. we probably can teach the verifier to recognize <<32, >>32 and replace with mov32
Alexei Starovoitov writes: > On Fri, May 03, 2019 at 11:42:31AM +0100, Jiong Wang wrote: >> This patch introduce new alu32 insn BPF_ZEXT, and allocate the unused >> opcode 0xe0 to it. >> >> Compared with the other alu32 insns, zero extension on low 32-bit is the >> only semantics for this instruction. It also allows various JIT back-ends >> to do optimal zero extension code-gen. >> >> BPF_ZEXT is supposed to be encoded with BPF_ALU only, and is supposed to be >> generated by the latter 32-bit optimization code inside verifier for those >> arches that do not support hardware implicit zero extension only. >> >> It is not supposed to be used in user's program directly at the moment. >> Therefore, no need to recognize it inside generic verification code. It >> just need to be supported for execution on interpreter or related JIT >> back-ends. > > uapi and the doc define it, but "it is not supposed to be used" ?! > >> Signed-off-by: Jiong Wang <jiong.wang@netronome.com> >> --- >> Documentation/networking/filter.txt | 10 ++++++++++ >> include/uapi/linux/bpf.h | 3 +++ >> kernel/bpf/core.c | 4 ++++ >> tools/include/uapi/linux/bpf.h | 3 +++ >> 4 files changed, 20 insertions(+) >> >> diff --git a/Documentation/networking/filter.txt b/Documentation/networking/filter.txt >> index 319e5e0..1cb3e42 100644 >> --- a/Documentation/networking/filter.txt >> +++ b/Documentation/networking/filter.txt >> @@ -903,6 +903,16 @@ If BPF_CLASS(code) == BPF_ALU or BPF_ALU64 [ in eBPF ], BPF_OP(code) is one of: >> BPF_MOV 0xb0 /* eBPF only: mov reg to reg */ >> BPF_ARSH 0xc0 /* eBPF only: sign extending shift right */ >> BPF_END 0xd0 /* eBPF only: endianness conversion */ >> + BPF_ZEXT 0xe0 /* eBPF BPF_ALU only: zero-extends low 32-bit */ >> + >> +Compared with BPF_ALU | BPF_MOV which zero-extends low 32-bit implicitly, >> +BPF_ALU | BPF_ZEXT zero-extends low 32-bit explicitly. Such zero extension is > > wait. that's an excellent observation. alu|mov is exactly it. > we do not need another insn. > we probably can teach the verifier to recognize <<32, >>32 and replace > with mov32 Hmm, I am silly, in v6, patched insn will be conservatively marked as always needing zext, so looks like no problem to just insert mov32 as zext. But some backends needs minor opt, because this will be special mov, with the same src and dst, just need to clear high 32-bit, no need of mov. Regards, Jiong
Jiong Wang writes: > Alexei Starovoitov writes: > >> On Fri, May 03, 2019 at 11:42:31AM +0100, Jiong Wang wrote: >>> This patch introduce new alu32 insn BPF_ZEXT, and allocate the unused >>> opcode 0xe0 to it. >>> >>> Compared with the other alu32 insns, zero extension on low 32-bit is the >>> only semantics for this instruction. It also allows various JIT back-ends >>> to do optimal zero extension code-gen. >>> >>> BPF_ZEXT is supposed to be encoded with BPF_ALU only, and is supposed to be >>> generated by the latter 32-bit optimization code inside verifier for those >>> arches that do not support hardware implicit zero extension only. >>> >>> It is not supposed to be used in user's program directly at the moment. >>> Therefore, no need to recognize it inside generic verification code. It >>> just need to be supported for execution on interpreter or related JIT >>> back-ends. >> >> uapi and the doc define it, but "it is not supposed to be used" ?! >> >>> Signed-off-by: Jiong Wang <jiong.wang@netronome.com> >>> --- >>> Documentation/networking/filter.txt | 10 ++++++++++ >>> include/uapi/linux/bpf.h | 3 +++ >>> kernel/bpf/core.c | 4 ++++ >>> tools/include/uapi/linux/bpf.h | 3 +++ >>> 4 files changed, 20 insertions(+) >>> >>> diff --git a/Documentation/networking/filter.txt b/Documentation/networking/filter.txt >>> index 319e5e0..1cb3e42 100644 >>> --- a/Documentation/networking/filter.txt >>> +++ b/Documentation/networking/filter.txt >>> @@ -903,6 +903,16 @@ If BPF_CLASS(code) == BPF_ALU or BPF_ALU64 [ in eBPF ], BPF_OP(code) is one of: >>> BPF_MOV 0xb0 /* eBPF only: mov reg to reg */ >>> BPF_ARSH 0xc0 /* eBPF only: sign extending shift right */ >>> BPF_END 0xd0 /* eBPF only: endianness conversion */ >>> + BPF_ZEXT 0xe0 /* eBPF BPF_ALU only: zero-extends low 32-bit */ >>> + >>> +Compared with BPF_ALU | BPF_MOV which zero-extends low 32-bit implicitly, >>> +BPF_ALU | BPF_ZEXT zero-extends low 32-bit explicitly. Such zero extension is >> >> wait. that's an excellent observation. alu|mov is exactly it. >> we do not need another insn. >> we probably can teach the verifier to recognize <<32, >>32 and replace >> with mov32 > > Hmm, I am silly, in v6, patched insn will be conservatively marked as > always needing zext, so looks like no problem to just insert mov32 as > zext. But some backends needs minor opt, because this will be special mov, > with the same src and dst, just need to clear high 32-bit, no need of > mov. I take it back. Recalled the reason why new ZEXT was introduced. It was because instruction insertion based approach doesn't push analysis results down to JIT back-ends, instead, it removes the clear-high-32bit semantics from all sub-register write instructions, then insert new explicit ZEXT insn, either by 64bit shifts combination or this new introduced ZEXT, what's important, the inserted "ZEXT" should not be affected by "env->verifier_zext", and be performed unconditionally. That is to say, for the current zero extension insertion based approach, JIT back-ends trust verifier has done full zero extension insertion and rewritten the instruction sequence once the flag env->verifier_zext is set, and then JIT back-end do NOT clear high 32-bit for all existing sub-register write instructions, for example ALU32 and narrowed load, they rely on those new inserted "unconditional ZEXT" to do the job if it is needed. So, if we insert mov32, there actually won't be zero extension insertion performed for it. The inserted "ZEXT" needs to have zero extension semantics that is not affected by env->verifier_zext. BPF_ZEXT was introduced because of this, low32 zext is its only semantics and should be unconditionally done. "mov32" could be used as "ZEXT" only when there is no such removal of zero extension semantics from alu32, or if JIT back-end could have instruction level information, for example the analyzed instruction level zero extension information pushed down to JIT back-ends. The new inserted "mov32" would then has information like "zext_dst" be true, JIT back-end then will generate zero extension for it. Regards, Jiong
On Tue, May 07, 2019 at 05:29:09AM +0100, Jiong Wang wrote: > > Jiong Wang writes: > > > Alexei Starovoitov writes: > > > >> On Fri, May 03, 2019 at 11:42:31AM +0100, Jiong Wang wrote: > >>> This patch introduce new alu32 insn BPF_ZEXT, and allocate the unused > >>> opcode 0xe0 to it. > >>> > >>> Compared with the other alu32 insns, zero extension on low 32-bit is the > >>> only semantics for this instruction. It also allows various JIT back-ends > >>> to do optimal zero extension code-gen. > >>> > >>> BPF_ZEXT is supposed to be encoded with BPF_ALU only, and is supposed to be > >>> generated by the latter 32-bit optimization code inside verifier for those > >>> arches that do not support hardware implicit zero extension only. > >>> > >>> It is not supposed to be used in user's program directly at the moment. > >>> Therefore, no need to recognize it inside generic verification code. It > >>> just need to be supported for execution on interpreter or related JIT > >>> back-ends. > >> > >> uapi and the doc define it, but "it is not supposed to be used" ?! > >> > >>> Signed-off-by: Jiong Wang <jiong.wang@netronome.com> > >>> --- > >>> Documentation/networking/filter.txt | 10 ++++++++++ > >>> include/uapi/linux/bpf.h | 3 +++ > >>> kernel/bpf/core.c | 4 ++++ > >>> tools/include/uapi/linux/bpf.h | 3 +++ > >>> 4 files changed, 20 insertions(+) > >>> > >>> diff --git a/Documentation/networking/filter.txt b/Documentation/networking/filter.txt > >>> index 319e5e0..1cb3e42 100644 > >>> --- a/Documentation/networking/filter.txt > >>> +++ b/Documentation/networking/filter.txt > >>> @@ -903,6 +903,16 @@ If BPF_CLASS(code) == BPF_ALU or BPF_ALU64 [ in eBPF ], BPF_OP(code) is one of: > >>> BPF_MOV 0xb0 /* eBPF only: mov reg to reg */ > >>> BPF_ARSH 0xc0 /* eBPF only: sign extending shift right */ > >>> BPF_END 0xd0 /* eBPF only: endianness conversion */ > >>> + BPF_ZEXT 0xe0 /* eBPF BPF_ALU only: zero-extends low 32-bit */ > >>> + > >>> +Compared with BPF_ALU | BPF_MOV which zero-extends low 32-bit implicitly, > >>> +BPF_ALU | BPF_ZEXT zero-extends low 32-bit explicitly. Such zero extension is > >> > >> wait. that's an excellent observation. alu|mov is exactly it. > >> we do not need another insn. > >> we probably can teach the verifier to recognize <<32, >>32 and replace > >> with mov32 > > > > Hmm, I am silly, in v6, patched insn will be conservatively marked as > > always needing zext, so looks like no problem to just insert mov32 as > > zext. But some backends needs minor opt, because this will be special mov, > > with the same src and dst, just need to clear high 32-bit, no need of > > mov. > > I take it back. > > Recalled the reason why new ZEXT was introduced. It was because instruction > insertion based approach doesn't push analysis results down to JIT > back-ends, instead, it removes the clear-high-32bit semantics from > all sub-register write instructions, then insert new explicit ZEXT insn, > either by 64bit shifts combination or this new introduced ZEXT, what's > important, the inserted "ZEXT" should not be affected by > "env->verifier_zext", and be performed unconditionally. > > That is to say, for the current zero extension insertion based approach, > JIT back-ends trust verifier has done full zero extension insertion and > rewritten the instruction sequence once the flag env->verifier_zext is set, > and then JIT back-end do NOT clear high 32-bit for all existing > sub-register write instructions, for example ALU32 and narrowed load, they > rely on those new inserted "unconditional ZEXT" to do the job if it is > needed. So, if we insert mov32, there actually won't be zero extension > insertion performed for it. > > The inserted "ZEXT" needs to have zero extension semantics that is not > affected by env->verifier_zext. BPF_ZEXT was introduced because of this, > low32 zext is its only semantics and should be unconditionally done. > > "mov32" could be used as "ZEXT" only when there is no such removal of zero > extension semantics from alu32, or if JIT back-end could have instruction > level information, for example the analyzed instruction level zero extension > information pushed down to JIT back-ends. The new inserted "mov32" would > then has information like "zext_dst" be true, JIT back-end then will > generate zero extension for it. JITs could simply always do zext for mov32. No need to for extra flags.
diff --git a/Documentation/networking/filter.txt b/Documentation/networking/filter.txt index 319e5e0..1cb3e42 100644 --- a/Documentation/networking/filter.txt +++ b/Documentation/networking/filter.txt @@ -903,6 +903,16 @@ If BPF_CLASS(code) == BPF_ALU or BPF_ALU64 [ in eBPF ], BPF_OP(code) is one of: BPF_MOV 0xb0 /* eBPF only: mov reg to reg */ BPF_ARSH 0xc0 /* eBPF only: sign extending shift right */ BPF_END 0xd0 /* eBPF only: endianness conversion */ + BPF_ZEXT 0xe0 /* eBPF BPF_ALU only: zero-extends low 32-bit */ + +Compared with BPF_ALU | BPF_MOV which zero-extends low 32-bit implicitly, +BPF_ALU | BPF_ZEXT zero-extends low 32-bit explicitly. Such zero extension is +not the main semantics for the prior, but is for the latter. Therefore, JIT +optimizer could optimize out the zero extension for the prior when it is +concluded safe to do so, but should never do such optimization for the latter. +LLVM compiler won't generate BPF_ZEXT, and hand written assembly is not supposed +to use it. Verifier 32-bit optimization pass, which removes zero extension +semantics from the other BPF_ALU instructions, is the only place generates it. If BPF_CLASS(code) == BPF_JMP or BPF_JMP32 [ in eBPF ], BPF_OP(code) is one of: diff --git a/include/uapi/linux/bpf.h b/include/uapi/linux/bpf.h index 72336ba..22ccdf4 100644 --- a/include/uapi/linux/bpf.h +++ b/include/uapi/linux/bpf.h @@ -32,6 +32,9 @@ #define BPF_FROM_LE BPF_TO_LE #define BPF_FROM_BE BPF_TO_BE +/* zero extend low 32-bit */ +#define BPF_ZEXT 0xe0 + /* jmp encodings */ #define BPF_JNE 0x50 /* jump != */ #define BPF_JLT 0xa0 /* LT is unsigned, '<' */ diff --git a/kernel/bpf/core.c b/kernel/bpf/core.c index 2792eda..ee8703d 100644 --- a/kernel/bpf/core.c +++ b/kernel/bpf/core.c @@ -1152,6 +1152,7 @@ EXPORT_SYMBOL_GPL(__bpf_call_base); INSN_2(ALU, NEG), \ INSN_3(ALU, END, TO_BE), \ INSN_3(ALU, END, TO_LE), \ + INSN_2(ALU, ZEXT), \ /* Immediate based. */ \ INSN_3(ALU, ADD, K), \ INSN_3(ALU, SUB, K), \ @@ -1352,6 +1353,9 @@ static u64 ___bpf_prog_run(u64 *regs, const struct bpf_insn *insn, u64 *stack) ALU64_NEG: DST = -DST; CONT; + ALU_ZEXT: + DST = (u32) DST; + CONT; ALU_MOV_X: DST = (u32) SRC; CONT; diff --git a/tools/include/uapi/linux/bpf.h b/tools/include/uapi/linux/bpf.h index 72336ba..22ccdf4 100644 --- a/tools/include/uapi/linux/bpf.h +++ b/tools/include/uapi/linux/bpf.h @@ -32,6 +32,9 @@ #define BPF_FROM_LE BPF_TO_LE #define BPF_FROM_BE BPF_TO_BE +/* zero extend low 32-bit */ +#define BPF_ZEXT 0xe0 + /* jmp encodings */ #define BPF_JNE 0x50 /* jump != */ #define BPF_JLT 0xa0 /* LT is unsigned, '<' */
This patch introduce new alu32 insn BPF_ZEXT, and allocate the unused opcode 0xe0 to it. Compared with the other alu32 insns, zero extension on low 32-bit is the only semantics for this instruction. It also allows various JIT back-ends to do optimal zero extension code-gen. BPF_ZEXT is supposed to be encoded with BPF_ALU only, and is supposed to be generated by the latter 32-bit optimization code inside verifier for those arches that do not support hardware implicit zero extension only. It is not supposed to be used in user's program directly at the moment. Therefore, no need to recognize it inside generic verification code. It just need to be supported for execution on interpreter or related JIT back-ends. Signed-off-by: Jiong Wang <jiong.wang@netronome.com> --- Documentation/networking/filter.txt | 10 ++++++++++ include/uapi/linux/bpf.h | 3 +++ kernel/bpf/core.c | 4 ++++ tools/include/uapi/linux/bpf.h | 3 +++ 4 files changed, 20 insertions(+)