[PATCH net-next] filter: add bpf_optimize_div()

[PATCH net-next] filter: add bpf_optimize_div()

[Denis Kirjanov]

optimize_div() found in  mips bpf jit is really usefull
for other arches. So let's put it in filter.h

CC: Alexei Starovoitov <ast@plumgrid.com>
Signed-off-by: Denis Kirjanov <kda@linux-powerpc.org>
---
 include/linux/filter.h | 11 +++++++++++
 1 file changed, 11 insertions(+)

diff --git a/include/linux/filter.h b/include/linux/filter.h
index ca95abd..b385637 100644
--- a/include/linux/filter.h
+++ b/include/linux/filter.h
@@ -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)
 {
-- 
2.1.0

Re: [PATCH net-next] filter: add bpf_optimize_div()

[Alexei Starovoitov]

On Thu, Nov 20, 2014 at 11:42 AM, Denis Kirjanov <kda@linux-powerpc.org> wrote:
> optimize_div() found in  mips bpf jit is really usefull
> for other arches. So let's put it in filter.h
>
> CC: Alexei Starovoitov <ast@plumgrid.com>
> Signed-off-by: Denis Kirjanov <kda@linux-powerpc.org>
> ---
>  include/linux/filter.h | 11 +++++++++++
>  1 file changed, 11 insertions(+)
>
> diff --git a/include/linux/filter.h b/include/linux/filter.h
> index ca95abd..b385637 100644
> --- a/include/linux/filter.h
> +++ b/include/linux/filter.h
> +
> +static inline int bpf_optimize_div(u32 *k)

'inline' is unnecessary

> +{
> +       /* 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.

Re: [PATCH net-next] filter: add bpf_optimize_div()

[Daniel Borkmann]

On 11/20/2014 10:07 PM, Alexei Starovoitov wrote:
> On Thu, Nov 20, 2014 at 11:42 AM, Denis Kirjanov <kda@linux-powerpc.org> wrote:
...
>> diff --git a/include/linux/filter.h b/include/linux/filter.h
>> index ca95abd..b385637 100644
>> --- a/include/linux/filter.h
>> +++ b/include/linux/filter.h
>> +
>> +static inline int bpf_optimize_div(u32 *k)
>
> 'inline' is unnecessary

Btw, it's a header file here, so it's necessary here.

...
> In general I don't think such optimizations
> belong in kernel at all. User space should be doing this.

+1

Re: [PATCH net-next] filter: add bpf_optimize_div()

[Denis Kirjanov]

On 11/21/14, Alexei Starovoitov <ast@plumgrid.com> wrote:
> On Thu, Nov 20, 2014 at 11:42 AM, Denis Kirjanov <kda@linux-powerpc.org>
> wrote:
>> optimize_div() found in  mips bpf jit is really usefull
>> for other arches. So let's put it in filter.h
>>
>> CC: Alexei Starovoitov <ast@plumgrid.com>
>> Signed-off-by: Denis Kirjanov <kda@linux-powerpc.org>
>> ---
>>  include/linux/filter.h | 11 +++++++++++
>>  1 file changed, 11 insertions(+)
>>
>> diff --git a/include/linux/filter.h b/include/linux/filter.h
>> index ca95abd..b385637 100644
>> --- a/include/linux/filter.h
>> +++ b/include/linux/filter.h
>> +
>> +static inline int bpf_optimize_div(u32 *k)
>
> 'inline' is unnecessary
>
>> +{
>> +       /* 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()

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

> 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.
>

Re: [PATCH net-next] filter: add bpf_optimize_div()

[Daniel Borkmann]

On 11/20/2014 08:42 PM, Denis Kirjanov wrote:
> optimize_div() found in  mips bpf jit is really usefull
> for other arches. So let's put it in filter.h
>
> CC: Alexei Starovoitov <ast@plumgrid.com>
> Signed-off-by: Denis Kirjanov <kda@linux-powerpc.org>

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.

> ---
>   include/linux/filter.h | 11 +++++++++++
>   1 file changed, 11 insertions(+)
>
> diff --git a/include/linux/filter.h b/include/linux/filter.h
> index ca95abd..b385637 100644
> --- a/include/linux/filter.h
> +++ b/include/linux/filter.h
> @@ -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)
>   {
>

Re: [PATCH net-next] filter: add bpf_optimize_div()

[Denis Kirjanov]

On 11/21/14, Daniel Borkmann <dborkman@redhat.com> wrote:
> On 11/20/2014 08:42 PM, Denis Kirjanov wrote:
>> optimize_div() found in  mips bpf jit is really usefull
>> for other arches. So let's put it in filter.h
>>
>> CC: Alexei Starovoitov <ast@plumgrid.com>
>> Signed-off-by: Denis Kirjanov <kda@linux-powerpc.org>
>
> 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.

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

>
>> ---
>>   include/linux/filter.h | 11 +++++++++++
>>   1 file changed, 11 insertions(+)
>>
>> diff --git a/include/linux/filter.h b/include/linux/filter.h
>> index ca95abd..b385637 100644
>> --- a/include/linux/filter.h
>> +++ b/include/linux/filter.h
>> @@ -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)
>>   {
>>
>

RE: [PATCH net-next] filter: add bpf_optimize_div()

[David Laight]

From: Denis Kirjanov
> optimize_div() found in  mips bpf jit is really usefull
> for other arches. So let's put it in filter.h
...
> +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