* [PATCH] kernel:bpf Remove structure passing and assignment to save stack and no coping structures
@ 2018-01-13 22:03 Karim Eshapa
2018-01-14 0:43 ` Alexei Starovoitov
2018-01-16 13:55 ` Edward Cree
0 siblings, 2 replies; 6+ messages in thread
From: Karim Eshapa @ 2018-01-13 22:03 UTC (permalink / raw)
To: ast; +Cc: daniel, ecree, davem, linux-kernel, netdev, Karim Eshapa
Use pointers to structure as arguments to function instead of coping
structures and less stack size. Also transfer TNUM(_v, _m) to
tnum.h file to be used in differnet files for creating anonymous structures
statically.
Signed-off-by: Karim Eshapa <karim.eshapa@gmail.com>
Thanks,
Karim
---
include/linux/tnum.h | 4 +++-
kernel/bpf/tnum.c | 14 +++++++-------
kernel/bpf/verifier.c | 11 ++++++-----
3 files changed, 16 insertions(+), 13 deletions(-)
diff --git a/include/linux/tnum.h b/include/linux/tnum.h
index 0d2d3da..72938a0 100644
--- a/include/linux/tnum.h
+++ b/include/linux/tnum.h
@@ -13,6 +13,8 @@ struct tnum {
};
/* Constructors */
+/* Statically tnum constant */
+#define TNUM(_v, _m) (struct tnum){.value = _v, .mask = _m}
/* Represent a known constant as a tnum. */
struct tnum tnum_const(u64 value);
/* A completely unknown value */
@@ -26,7 +28,7 @@ struct tnum tnum_lshift(struct tnum a, u8 shift);
/* Shift a tnum right (by a fixed shift) */
struct tnum tnum_rshift(struct tnum a, u8 shift);
/* Add two tnums, return @a + @b */
-struct tnum tnum_add(struct tnum a, struct tnum b);
+void tnum_add(struct tnum *res, struct tnum *a, struct tnum *b);
/* Subtract two tnums, return @a - @b */
struct tnum tnum_sub(struct tnum a, struct tnum b);
/* Bitwise-AND, return @a & @b */
diff --git a/kernel/bpf/tnum.c b/kernel/bpf/tnum.c
index 1f4bf68..89e3182 100644
--- a/kernel/bpf/tnum.c
+++ b/kernel/bpf/tnum.c
@@ -8,7 +8,6 @@
#include <linux/kernel.h>
#include <linux/tnum.h>
-#define TNUM(_v, _m) (struct tnum){.value = _v, .mask = _m}
/* A completely unknown value */
const struct tnum tnum_unknown = { .value = 0, .mask = -1 };
@@ -43,16 +42,17 @@ struct tnum tnum_rshift(struct tnum a, u8 shift)
return TNUM(a.value >> shift, a.mask >> shift);
}
-struct tnum tnum_add(struct tnum a, struct tnum b)
+void tnum_add(struct tnum *res, struct tnum *a, struct tnum *b)
{
u64 sm, sv, sigma, chi, mu;
- sm = a.mask + b.mask;
- sv = a.value + b.value;
+ sm = a->mask + b->mask;
+ sv = a->value + b->value;
sigma = sm + sv;
chi = sigma ^ sv;
- mu = chi | a.mask | b.mask;
- return TNUM(sv & ~mu, mu);
+ mu = chi | a->mask | b->mask;
+ res->value = (sv & ~mu);
+ res->mask = mu;
}
struct tnum tnum_sub(struct tnum a, struct tnum b)
@@ -102,7 +102,7 @@ static struct tnum hma(struct tnum acc, u64 value, u64 mask)
{
while (mask) {
if (mask & 1)
- acc = tnum_add(acc, TNUM(0, value));
+ tnum_add(&acc, &acc, &TNUM(0, value));
mask >>= 1;
value <<= 1;
}
diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c
index b414d6b..b31b1c4 100644
--- a/kernel/bpf/verifier.c
+++ b/kernel/bpf/verifier.c
@@ -999,7 +999,7 @@ static int check_pkt_ptr_alignment(struct bpf_verifier_env *env,
*/
ip_align = 2;
- reg_off = tnum_add(reg->var_off, tnum_const(ip_align + reg->off + off));
+ tnum_add(®_off, ®->var_off, &TNUM(ip_align + reg->off + off, 0));
if (!tnum_is_aligned(reg_off, size)) {
char tn_buf[48];
@@ -1023,8 +1023,7 @@ static int check_generic_ptr_alignment(struct bpf_verifier_env *env,
/* Byte size accesses are always allowed. */
if (!strict || size == 1)
return 0;
-
- reg_off = tnum_add(reg->var_off, tnum_const(reg->off + off));
+ tnum_add(®_off, ®->var_off, &TNUM(reg->off + off, 0));
if (!tnum_is_aligned(reg_off, size)) {
char tn_buf[48];
@@ -1971,7 +1970,8 @@ static int adjust_ptr_min_max_vals(struct bpf_verifier_env *env,
dst_reg->umin_value = umin_ptr + umin_val;
dst_reg->umax_value = umax_ptr + umax_val;
}
- dst_reg->var_off = tnum_add(ptr_reg->var_off, off_reg->var_off);
+ tnum_add(&dst_reg->var_off, &ptr_reg->var_off,
+ &off_reg->var_off);
dst_reg->off = ptr_reg->off;
if (reg_is_pkt_pointer(ptr_reg)) {
dst_reg->id = ++env->id_gen;
@@ -2108,7 +2108,8 @@ static int adjust_scalar_min_max_vals(struct bpf_verifier_env *env,
dst_reg->umin_value += umin_val;
dst_reg->umax_value += umax_val;
}
- dst_reg->var_off = tnum_add(dst_reg->var_off, src_reg.var_off);
+ tnum_add(&dst_reg->var_off, &dst_reg->var_off,
+ &src_reg.var_off);
break;
case BPF_SUB:
if (signed_sub_overflows(dst_reg->smin_value, smax_val) ||
--
2.7.4
^ permalink raw reply related [flat|nested] 6+ messages in thread* Re: [PATCH] kernel:bpf Remove structure passing and assignment to save stack and no coping structures
2018-01-13 22:03 [PATCH] kernel:bpf Remove structure passing and assignment to save stack and no coping structures Karim Eshapa
@ 2018-01-14 0:43 ` Alexei Starovoitov
2018-01-16 13:55 ` Edward Cree
1 sibling, 0 replies; 6+ messages in thread
From: Alexei Starovoitov @ 2018-01-14 0:43 UTC (permalink / raw)
To: Karim Eshapa; +Cc: ast, daniel, ecree, davem, linux-kernel, netdev
On Sun, Jan 14, 2018 at 12:03:42AM +0200, Karim Eshapa wrote:
> Use pointers to structure as arguments to function instead of coping
> structures and less stack size. Also transfer TNUM(_v, _m) to
> tnum.h file to be used in differnet files for creating anonymous structures
> statically.
>
> Signed-off-by: Karim Eshapa <karim.eshapa@gmail.com>
...
> +/* Statically tnum constant */
> +#define TNUM(_v, _m) (struct tnum){.value = _v, .mask = _m}
> /* Represent a known constant as a tnum. */
> struct tnum tnum_const(u64 value);
> /* A completely unknown value */
> @@ -26,7 +28,7 @@ struct tnum tnum_lshift(struct tnum a, u8 shift);
> /* Shift a tnum right (by a fixed shift) */
> struct tnum tnum_rshift(struct tnum a, u8 shift);
> /* Add two tnums, return @a + @b */
> -struct tnum tnum_add(struct tnum a, struct tnum b);
> +void tnum_add(struct tnum *res, struct tnum *a, struct tnum *b);
...
> - reg_off = tnum_add(reg->var_off, tnum_const(ip_align + reg->off + off));
> + tnum_add(®_off, ®->var_off, &TNUM(ip_align + reg->off + off, 0));
> if (!tnum_is_aligned(reg_off, size)) {
> char tn_buf[48];
>
> @@ -1023,8 +1023,7 @@ static int check_generic_ptr_alignment(struct bpf_verifier_env *env,
> /* Byte size accesses are always allowed. */
> if (!strict || size == 1)
> return 0;
> -
> - reg_off = tnum_add(reg->var_off, tnum_const(reg->off + off));
> + tnum_add(®_off, ®->var_off, &TNUM(reg->off + off, 0));
...
> - dst_reg->var_off = tnum_add(ptr_reg->var_off, off_reg->var_off);
> + tnum_add(&dst_reg->var_off, &ptr_reg->var_off,
> + &off_reg->var_off);
I think that looks much worse and error prone.
Is it gnu or intel style of argumnets ? where is src or dest ?
Can the same pointer be used as src and as dst ? etc, etc
I don't think it saves stack either.
I'd rather leave things as-is.
^ permalink raw reply [flat|nested] 6+ messages in thread* Re: [PATCH] kernel:bpf Remove structure passing and assignment to save stack and no coping structures
2018-01-13 22:03 [PATCH] kernel:bpf Remove structure passing and assignment to save stack and no coping structures Karim Eshapa
2018-01-14 0:43 ` Alexei Starovoitov
@ 2018-01-16 13:55 ` Edward Cree
1 sibling, 0 replies; 6+ messages in thread
From: Edward Cree @ 2018-01-16 13:55 UTC (permalink / raw)
To: Karim Eshapa, ast; +Cc: daniel, davem, linux-kernel, netdev
On 13/01/18 22:03, Karim Eshapa wrote:
> Use pointers to structure as arguments to function instead of coping
> structures and less stack size. Also transfer TNUM(_v, _m) to
> tnum.h file to be used in differnet files for creating anonymous structures
> statically.
>
> Signed-off-by: Karim Eshapa <karim.eshapa@gmail.com>
NACK (some reasons inline).
> Thanks,
> Karim
> ---
> include/linux/tnum.h | 4 +++-
> kernel/bpf/tnum.c | 14 +++++++-------
> kernel/bpf/verifier.c | 11 ++++++-----
> 3 files changed, 16 insertions(+), 13 deletions(-)
>
> diff --git a/include/linux/tnum.h b/include/linux/tnum.h
> index 0d2d3da..72938a0 100644
> --- a/include/linux/tnum.h
> +++ b/include/linux/tnum.h
> @@ -13,6 +13,8 @@ struct tnum {
> };
>
> /* Constructors */
> +/* Statically tnum constant */
> +#define TNUM(_v, _m) (struct tnum){.value = _v, .mask = _m}
This shouldn't be in the 'public' API, because it's dealing in the internals
of the tnum struct in ways that calling code shouldn't have to worry about.
Instead, callers should use functions like tnum_const() to construct tnums.
> /* Represent a known constant as a tnum. */
> struct tnum tnum_const(u64 value);
> /* A completely unknown value */
> @@ -26,7 +28,7 @@ struct tnum tnum_lshift(struct tnum a, u8 shift);
> /* Shift a tnum right (by a fixed shift) */
> struct tnum tnum_rshift(struct tnum a, u8 shift);
> /* Add two tnums, return @a + @b */
> -struct tnum tnum_add(struct tnum a, struct tnum b);
> +void tnum_add(struct tnum *res, struct tnum *a, struct tnum *b);
I would expect the old tnum_add to be inlined by the compiler. Moreover,
the arguments and return value are clearly separate, whereas in your new
version they could (and often will) alias, thus the function body has to
be careful not to write the result until it has finished reading the args.
I wouldn't be surprised if your versions actually _increased_ total stack
usage by confusing the compiler's inliner and liveness analysis.
> /* Subtract two tnums, return @a - @b */
> struct tnum tnum_sub(struct tnum a, struct tnum b);
> /* Bitwise-AND, return @a & @b */
> diff --git a/kernel/bpf/tnum.c b/kernel/bpf/tnum.c
> index 1f4bf68..89e3182 100644
> --- a/kernel/bpf/tnum.c
> +++ b/kernel/bpf/tnum.c
> @@ -8,7 +8,6 @@
> #include <linux/kernel.h>
> #include <linux/tnum.h>
>
> -#define TNUM(_v, _m) (struct tnum){.value = _v, .mask = _m}
> /* A completely unknown value */
> const struct tnum tnum_unknown = { .value = 0, .mask = -1 };
>
> @@ -43,16 +42,17 @@ struct tnum tnum_rshift(struct tnum a, u8 shift)
> return TNUM(a.value >> shift, a.mask >> shift);
> }
>
> -struct tnum tnum_add(struct tnum a, struct tnum b)
> +void tnum_add(struct tnum *res, struct tnum *a, struct tnum *b)
> {
> u64 sm, sv, sigma, chi, mu;
>
> - sm = a.mask + b.mask;
> - sv = a.value + b.value;
> + sm = a->mask + b->mask;
> + sv = a->value + b->value;
> sigma = sm + sv;
> chi = sigma ^ sv;
> - mu = chi | a.mask | b.mask;
> - return TNUM(sv & ~mu, mu);
> + mu = chi | a->mask | b->mask;
> + res->value = (sv & ~mu);
> + res->mask = mu;
> }
>
> struct tnum tnum_sub(struct tnum a, struct tnum b)
> @@ -102,7 +102,7 @@ static struct tnum hma(struct tnum acc, u64 value, u64 mask)
> {
> while (mask) {
> if (mask & 1)
> - acc = tnum_add(acc, TNUM(0, value));
> + tnum_add(&acc, &acc, &TNUM(0, value));
This is much less readable than the original, since instead of using the
assignment operator, the destination is just the first argument - not
nearly as self-documenting.
-Ed
^ permalink raw reply [flat|nested] 6+ messages in thread
* [PATCH] kernel:bpf Remove structure passing and assignment to save stack and no coping structures
@ 2018-01-14 11:18 Karim Eshapa
2018-01-14 17:31 ` Alexei Starovoitov
0 siblings, 1 reply; 6+ messages in thread
From: Karim Eshapa @ 2018-01-14 11:18 UTC (permalink / raw)
To: ast; +Cc: daniel, ecree, davem, linux-kernel, netdev, Karim Eshapa
>> Use pointers to structure as arguments to function instead of coping
>> structures and less stack size. Also transfer TNUM(_v, _m) to
>> tnum.h file to be used in differnet files for creating anonymous structures
>> statically.
>>
>> Signed-off-by: Karim Eshapa <karim.eshapa@gmail.com>
...
>> +/* Statically tnum constant */
>> +#define TNUM(_v, _m) (struct tnum){.value = _v, .mask = _m}
>> /* Represent a known constant as a tnum. */
>> struct tnum tnum_const(u64 value);
>> /* A completely unknown value */
>> @@ -26,7 +28,7 @@ struct tnum tnum_lshift(struct tnum a, u8 shift);
>> /* Shift a tnum right (by a fixed shift) */
>> struct tnum tnum_rshift(struct tnum a, u8 shift);
>> /* Add two tnums, return @a + @b */
>> -struct tnum tnum_add(struct tnum a, struct tnum b);
>> +void tnum_add(struct tnum *res, struct tnum *a, struct tnum *b);
...
>> - reg_off = tnum_add(reg->var_off, tnum_const(ip_align + reg->off + off));
>> + tnum_add(®_off, ®->var_off, &TNUM(ip_align + reg->off + off, 0));
>> if (!tnum_is_aligned(reg_off, size)) {
>> char tn_buf[48];
>>
>> @@ -1023,8 +1023,7 @@ static int check_generic_ptr_alignment(struct bpf_verifier_env *env,
>> /* Byte size accesses are always allowed. */
>> if (!strict || size == 1)
>> return 0;
>> -
>> - reg_off = tnum_add(reg->var_off, tnum_const(reg->off + off));
>> + tnum_add(®_off, ®->var_off, &TNUM(reg->off + off, 0));
...
>> - dst_reg->var_off = tnum_add(ptr_reg->var_off, off_reg->var_off);
>> + tnum_add(&dst_reg->var_off, &ptr_reg->var_off,
>> + &off_reg->var_off);
>Is it gnu or intel style of argumnets ? where is src or dest ?
>Can the same pointer be used as src and as dst ? etc, etc
>I don't think it saves stack either.
>I'd rather leave things as-is.
It's not specific style but it's recommended when passing structure specially if
the structures have large sizes.
and (dest, src0, src1) respectively.Although tnum structure isn't large but it saves
stack,we have 2 structure passed before calling and 1 returned to receive the return value.
>I think that looks much worse and error prone.
I don't actually see errors unless inentionally passing wrong parameters.
Thanks,
Karim
^ permalink raw reply [flat|nested] 6+ messages in thread* Re: [PATCH] kernel:bpf Remove structure passing and assignment to save stack and no coping structures
2018-01-14 11:18 Karim Eshapa
@ 2018-01-14 17:31 ` Alexei Starovoitov
0 siblings, 0 replies; 6+ messages in thread
From: Alexei Starovoitov @ 2018-01-14 17:31 UTC (permalink / raw)
To: Karim Eshapa; +Cc: ast, daniel, ecree, davem, linux-kernel, netdev
On Sun, Jan 14, 2018 at 01:18:35PM +0200, Karim Eshapa wrote:
> >> Use pointers to structure as arguments to function instead of coping
> >> structures and less stack size. Also transfer TNUM(_v, _m) to
> >> tnum.h file to be used in differnet files for creating anonymous structures
> >> statically.
> >>
> >> Signed-off-by: Karim Eshapa <karim.eshapa@gmail.com>
> ...
> >> +/* Statically tnum constant */
> >> +#define TNUM(_v, _m) (struct tnum){.value = _v, .mask = _m}
> >> /* Represent a known constant as a tnum. */
> >> struct tnum tnum_const(u64 value);
> >> /* A completely unknown value */
> >> @@ -26,7 +28,7 @@ struct tnum tnum_lshift(struct tnum a, u8 shift);
> >> /* Shift a tnum right (by a fixed shift) */
> >> struct tnum tnum_rshift(struct tnum a, u8 shift);
> >> /* Add two tnums, return @a + @b */
> >> -struct tnum tnum_add(struct tnum a, struct tnum b);
> >> +void tnum_add(struct tnum *res, struct tnum *a, struct tnum *b);
> ...
> >> - reg_off = tnum_add(reg->var_off, tnum_const(ip_align + reg->off + off));
> >> + tnum_add(®_off, ®->var_off, &TNUM(ip_align + reg->off + off, 0));
> >> if (!tnum_is_aligned(reg_off, size)) {
> >> char tn_buf[48];
> >>
> >> @@ -1023,8 +1023,7 @@ static int check_generic_ptr_alignment(struct bpf_verifier_env *env,
> >> /* Byte size accesses are always allowed. */
> >> if (!strict || size == 1)
> >> return 0;
> >> -
> >> - reg_off = tnum_add(reg->var_off, tnum_const(reg->off + off));
> >> + tnum_add(®_off, ®->var_off, &TNUM(reg->off + off, 0));
> ...
> >> - dst_reg->var_off = tnum_add(ptr_reg->var_off, off_reg->var_off);
> >> + tnum_add(&dst_reg->var_off, &ptr_reg->var_off,
> >> + &off_reg->var_off);
>
> >Is it gnu or intel style of argumnets ? where is src or dest ?
> >Can the same pointer be used as src and as dst ? etc, etc
> >I don't think it saves stack either.
> >I'd rather leave things as-is.
>
> It's not specific style but it's recommended when passing structure specially if
> the structures have large sizes.
> and (dest, src0, src1) respectively.Although tnum structure isn't large but it saves
> stack,we have 2 structure passed before calling and 1 returned to receive the return value.
1. your patch has compile time warnings
2. it doesn't reduce stack size.
For two functions that use tnum_add:
adjust_ptr_min_max_vals() before and after has exactly the same.
check_ptr_alignment() after your patch _increased_ stack size.
3. text of verifier.o shrank 133 bytes while tnum.o increased 198
Please do your homework next time.
tnum code will stay as-is.
^ permalink raw reply [flat|nested] 6+ messages in thread
[parent not found: <20180114173102.smi6jiwqz66wf7av@ast-mbpfile>]
* [PATCH] kernel:bpf Remove structure passing and assignment to save stack and no coping structures
[not found] <20180114173102.smi6jiwqz66wf7av@ast-mbpfile>
@ 2018-01-17 21:32 ` Karim Eshapa
0 siblings, 0 replies; 6+ messages in thread
From: Karim Eshapa @ 2018-01-17 21:32 UTC (permalink / raw)
To: ast; +Cc: daniel, ecree, davem, linux-kernel, netdev, Karim Eshapa
>On Sun, Jan 14, 2018 at 01:18:35PM +0200, Karim Eshapa wrote:
>> >> Use pointers to structure as arguments to function instead of coping
>> >> structures and less stack size. Also transfer TNUM(_v, _m) to
>> >> tnum.h file to be used in differnet files for creating anonymous structures
>> >> statically.
>> >>
>> >> Signed-off-by: Karim Eshapa <karim.eshapa@gmail.com>
>> ...
>> >> +/* Statically tnum constant */
>> >> +#define TNUM(_v, _m) (struct tnum){.value = _v, .mask = _m}
>> >> /* Represent a known constant as a tnum. */
>> >> struct tnum tnum_const(u64 value);
>> >> /* A completely unknown value */
>> >> @@ -26,7 +28,7 @@ struct tnum tnum_lshift(struct tnum a, u8 shift);
>> >> /* Shift a tnum right (by a fixed shift) */
>> >> struct tnum tnum_rshift(struct tnum a, u8 shift);
>> >> /* Add two tnums, return @a + @b */
>> >> -struct tnum tnum_add(struct tnum a, struct tnum b);
>> >> +void tnum_add(struct tnum *res, struct tnum *a, struct tnum *b);
>> ...
>> >> - reg_off = tnum_add(reg->var_off, tnum_const(ip_align + reg->off + off));
>> >> + tnum_add(®_off, ®->var_off, &TNUM(ip_align + reg->off + off, 0));
>> >> if (!tnum_is_aligned(reg_off, size)) {
>> >> char tn_buf[48];
>> >>
>> >> @@ -1023,8 +1023,7 @@ static int check_generic_ptr_alignment(struct bpf_verifier_env *env,
>> >> /* Byte size accesses are always allowed. */
>> >> if (!strict || size == 1)
>> >> return 0;
>> >> -
>> >> - reg_off = tnum_add(reg->var_off, tnum_const(reg->off + off));
>> >> + tnum_add(®_off, ®->var_off, &TNUM(reg->off + off, 0));
>> ...
> >> - dst_reg->var_off = tnum_add(ptr_reg->var_off, off_reg->var_off);
>> >> + tnum_add(&dst_reg->var_off, &ptr_reg->var_off,
>> >> + &off_reg->var_off);
>>
>> >Is it gnu or intel style of argumnets ? where is src or dest ?
>> >Can the same pointer be used as src and as dst ? etc, etc
>> >I don't think it saves stack either.
>> >I'd rather leave things as-is.
>>
>> It's not specific style but it's recommended when passing structure specially if
>> the structures have large sizes.
> and (dest, src0, src1) respectively.Although tnum structure isn't large but it saves
>> stack,we have 2 structure passed before calling and 1 returned to receive the return value.
>1. your patch has compile time warnings
>2. it doesn't reduce stack size.
> For two functions that use tnum_add:
> adjust_ptr_min_max_vals() before and after has exactly the same.
> check_ptr_alignment() after your patch _increased_ stack size.
>3. text of verifier.o shrank 133 bytes while tnum.o increased 198
>Please do your homework next time.
>tnum code will stay as-is.
Thanks so much for your response,if there is any recommended tools
to test how your patch affect memory, performance and what's
going on because all accepted patches I sumbited was so trivial
I'll be so appreciated.
Karim,
^ permalink raw reply [flat|nested] 6+ messages in thread
end of thread, other threads:[~2018-01-17 21:32 UTC | newest]
Thread overview: 6+ messages (download: mbox.gz follow: Atom feed
-- links below jump to the message on this page --
2018-01-13 22:03 [PATCH] kernel:bpf Remove structure passing and assignment to save stack and no coping structures Karim Eshapa
2018-01-14 0:43 ` Alexei Starovoitov
2018-01-16 13:55 ` Edward Cree
-- strict thread matches above, loose matches on Subject: below --
2018-01-14 11:18 Karim Eshapa
2018-01-14 17:31 ` Alexei Starovoitov
[not found] <20180114173102.smi6jiwqz66wf7av@ast-mbpfile>
2018-01-17 21:32 ` Karim Eshapa
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox