filter: add bpf_optimize_div()
Subsystems (4)
PATCH 1/1 filter: add bpf_optimize_div()
optimize_div() found in mips bpf jit is really usefull for other arches. So let's put it in filter.h
--- include/linux/filter.h | 11 +++++++++++ 1 file changed, 11 insertions(+)
include/linux/filter.h +11 -0
@@ -414,6 +414,17 @@ static inline void bpf_jit_dump(unsigned int flen, unsigned int proglen,print_hex_dump (KERN_ERR ,"JIT code: " ,DUMP_PREFIX_OFFSET , 16, 1, image, proglen, false); } + +static inline int bpf_optimize_div (u32 *k) +{ +/* power of 2 divides can be implemented with right shift */ +if (!(*k & (*k-1 ))) { + *k =ilog2 (*k); +return 1 ; + } + +return 0 ; +}#else static inline void bpf_jit_compile (struct bpf_prog *fp) {
Signature · 1 line
2.1.0
Quoted 13 lines · Denis Kirjanov
optimize_div()found in mips bpf jit is really usefull for other arches. So let's put it infilter.hCC Alexei Starovoitov <[email protected]>Signed-off-by Denis Kirjanov <[email protected]>--- include/linux/filter.h | 11 +++++++++++ 1 file changed, 11 insertions(+)include/linux/filter.h +0
-0
include/linux/filter.h static inline void bpf_jit_dump(unsigned int flen, unsigned int proglen, · line 418
Quoted 2 lines
include/linux/filter.h +2
-0+ +static inline int bpf_optimize_div (u32 *k)
'inline' is unnecessary
include/linux/filter.h static inline void bpf_jit_dump(unsigned int flen, unsigned int proglen, · line 427
Quoted 9 lines
include/linux/filter.h +9
-0+{ +/* power of 2 divides can be implemented with right shift */ +if (!(*k & (*k-1 ))) { + *k =ilog2 (*k); +return 1 ; + } + +return 0 ; +}
I don't think it makes sense to add a helper function without first user. If you really want to use it in ppc, make this change as part of the series. In the 1st patch move it out of mips and use it in mips jit and 2nd patch use it in ppc.
Also since you mentioned mips...
if (k == 1 || optimize_div(&k)) {
ctx->flags |= SEEN_A;
emit_jit_reg_move(r_A, r_zero, ctx);
this is definitely wrong in there.
Also with such helper function we'd need to be careful not to modify 'k' in place, otherwise multi-pass jit algorithm would be broken.
In general I don't think such optimizations belong in kernel at all. User space should be doing this.
Quoted 1 line · Alexei Starovoitov
On Thu, Nov 20, 2014 at 11:42 AM, Denis Kirjanov <[email protected]> wrote:
...
Quoted 8 lines
include/linux/filter.h static inline void bpf_jit_dump(unsigned int flen, unsigned int proglen, · line 418
Quoted 6 lines
include/linux/filter.h +2
-0+ +static inline int bpf_optimize_div (u32 *k)'inline' is unnecessary
Btw, it's a header file here, so it's necessary here.
...
Quoted 2 lines
In general I don't think such optimizations belong in kernel at all. User space should be doing this.
+1
Quoted 20 lines · Alexei Starovoitov
Quoted 13 lines · Denis Kirjanov
optimize_div()found in mips bpf jit is really usefull for other arches. So let's put it infilter.hCC Alexei Starovoitov <[email protected]>Signed-off-by Denis Kirjanov <[email protected]>--- include/linux/filter.h | 11 +++++++++++ 1 file changed, 11 insertions(+)include/linux/filter.h +0
-0include/linux/filter.h static inline void bpf_jit_dump(unsigned int flen, unsigned int proglen, · line 418
Quoted 2 lines
include/linux/filter.h +2
-0+ +static inline int bpf_optimize_div (u32 *k)'inline' is unnecessary
Quoted 15 lines
include/linux/filter.h static inline void bpf_jit_dump(unsigned int flen, unsigned int proglen, · line 427
Quoted 9 lines
include/linux/filter.h +9
-0+{ +/* power of 2 divides can be implemented with right shift */ +if (!(*k & (*k-1 ))) { + *k =ilog2 (*k); +return 1 ; + } + +return 0 ; +}I don't think it makes sense to add a helper function without first user. If you really want to use it in ppc, make this change as part of the series. In the 1st patch move it out of mips and use it in mips jit and 2nd patch use it in ppc.
Heh, actually we already have it: is_power_of_2()
Quoted 7 lines
Also since you mentioned mips...
if (k == 1 ||optimize_div(&k)) {
ctx->flags|=SEEN_A;
emit_jit_reg_move(r_A, r_zero, ctx);
this is definitely wrong in there.
I'll check it
Quoted 7 lines
Also with such helper function we'd need to be careful not to modify 'k' in place, otherwise multi-pass jit algorithm would be broken.
In general I don't think such optimizations belong in kernel at all. User space should be doing this.
Daniel Borkmann
NAKQuoted 5 lines · Denis Kirjanov
optimize_div()found in mips bpf jit is really usefull for other arches. So let's put it infilter.hCC Alexei Starovoitov <[email protected]>Signed-off-by Denis Kirjanov <[email protected]>
NAK
1) There's no user of this function (you name MIPS JIT, but don't remove it from there) ...
2) It's not really specific or tied to the BPF API in particular, so doesn't really belong here, rather some more generic kernel header, iff anything.
Quoted 27 lines
--- include/linux/filter.h | 11 +++++++++++ 1 file changed, 11 insertions(+)include/linux/filter.h +11
-0@@ -414,6 +414,17 @@ static inline void bpf_jit_dump(unsigned int flen, unsigned int proglen,print_hex_dump (KERN_ERR ,"JIT code: " ,DUMP_PREFIX_OFFSET , 16, 1, image, proglen, false); } + +static inline int bpf_optimize_div (u32 *k) +{ +/* power of 2 divides can be implemented with right shift */ +if (!(*k & (*k-1 ))) { + *k =ilog2 (*k); +return 1 ; + } + +return 0 ; +}#else static inline void bpf_jit_compile (struct bpf_prog *fp) {
Quoted 11 lines · Daniel Borkmann
Quoted 5 lines · Denis Kirjanov
optimize_div()found in mips bpf jit is really usefull for other arches. So let's put it infilter.hCC Alexei Starovoitov <[email protected]>Signed-off-by Denis Kirjanov <[email protected]>NAK
1) There's no user of this function (you name MIPS JIT, but don't remove it from there) ...
Right, I wanted to get some feedback before removing/adding it to the other places.
Quoted 4 lines
2) It's not really specific or tied to the BPF API in particular, so doesn't really belong here, rather some more generic kernel header, iff anything.
I was thinking about the best place to put this helper since this looks more or less generic...
Actually I had to put the RFC tag to the patch
Quoted 30 lines
Quoted 29 lines
--- include/linux/filter.h | 11 +++++++++++ 1 file changed, 11 insertions(+)include/linux/filter.h +11
-0@@ -414,6 +414,17 @@ static inline void bpf_jit_dump(unsigned int flen,unsigned int proglen, print_hex_dump(KERN_ERR, "JIT code: ", DUMP_PREFIX_OFFSET, 16, 1, image, proglen, false); } + +static inline int bpf_optimize_div (u32 *k) +{ +/* power of 2 divides can be implemented with right shift */ +if (!(*k & (*k-1 ))) { + *k =ilog2 (*k); +return 1 ; + } + +return 0 ; +}#else static inline void bpf_jit_compile (struct bpf_prog *fp){
From: Denis Kirjanov
Quoted 2 lines
optimize_div()found in mips bpf jit is really usefull for other arches. So let's put it infilter.h
...
include/linux/filter.h static inline void bpf_jit_dump(unsigned int flen, unsigned int proglen, · line 427
Quoted 10 lines
include/linux/filter.h +10
-0+static inline int bpf_optimize_div (u32 *k) +{ +/* power of 2 divides can be implemented with right shift */ +if (!(*k & (*k-1 ))) { + *k =ilog2 (*k); +return 1 ; + } + +return 0 ; +}
If 'k' is a constant then a 'multiply by reciprocal' is likely to be as fast as the shift - and works for a wider range of values.
On some architectures the ilog2() may itself be expensive.
On x86 the divide might even be faster than the conditional mess the above generates.
David