[PATCH] net: add seq_before/seq_after functions

[PATCH] net: add seq_before/seq_after functions

[Antonio Quartulli]

Introduce two operations to handle comparison between packet sequence
numbers taking into account overflow/wraparound. Batman-adv uses
these functions already to check for successor packet even in case of
overflow.
---

I added this two functions in net.h because I didn't really know where
best placement is. I saw several modules that redefine their own functions
for the same purpose.

 include/linux/net.h |   17 +++++++++++++++++
 1 files changed, 17 insertions(+), 0 deletions(-)

diff --git a/include/linux/net.h b/include/linux/net.h
index 94de83c..c7bc9bf 100644
--- a/include/linux/net.h
+++ b/include/linux/net.h
@@ -295,4 +295,21 @@ extern struct ratelimit_state net_ratelimit_state;
 #endif
 
 #endif /* __KERNEL__ */
+
+/* Returns the smallest signed integer in two's complement with the sizeof x */
+#define smallest_signed_int(x) (1u << (7u + 8u * (sizeof(x) - 1u)))
+
+/* Checks if a sequence number x is a predecessor/successor of y.
+ * they handle overflows/underflows and can correctly check for a
+ * predecessor/successor unless the variable sequence number has grown by
+ * more then 2**(bitwidth(x)-1)-1.
+ * This means that for a uint8_t with the maximum value 255, it would think:
+ *  - when adding nothing - it is neither a predecessor nor a successor
+ *  - before adding more than 127 to the starting value - it is a predecessor,
+ *  - when adding 128 - it is neither a predecessor nor a successor,
+ *  - after adding more than 127 to the starting value - it is a successor */
+#define seq_before(x, y) ({typeof(x) _dummy = (x - y); \
+			_dummy > smallest_signed_int(_dummy); })
+#define seq_after(x, y) seq_before(y, x)
+
 #endif	/* _LINUX_NET_H */
-- 
1.7.3.4

Re: net: add seq_before/seq_after functions

[Sven Eckelmann]

[-- Attachment #1: Type: Text/Plain, Size: 4595 bytes --]

On Wednesday 18 May 2011 14:38:39 Antonio Quartulli wrote:
> Introduce two operations to handle comparison between packet sequence
> numbers taking into account overflow/wraparound. Batman-adv uses
> these functions already to check for successor packet even in case of
> overflow.

Thanks for your efforts to bring that to the kernel. But when you prepare a 
patch then you have to add a signoff. And also David S. Miller is the 
maintainer for this header - it would be interesting to ask him first when we 
want to change that file.

> ---
> I added this two functions in net.h because I didn't really know where
> best placement is. I saw several modules that redefine their own functions
> for the same purpose.
> 
>  include/linux/net.h |   17 +++++++++++++++++
>  1 files changed, 17 insertions(+), 0 deletions(-)
> 
> diff --git a/include/linux/net.h b/include/linux/net.h
> index 94de83c..c7bc9bf 100644
> --- a/include/linux/net.h
> +++ b/include/linux/net.h
> @@ -295,4 +295,21 @@ extern struct ratelimit_state net_ratelimit_state;
>  #endif
> 
>  #endif /* __KERNEL__ */
> +
> +/* Returns the smallest signed integer in two's complement with the sizeof
> x */ +#define smallest_signed_int(x) (1u << (7u + 8u * (sizeof(x) - 1u)))
> +
> +/* Checks if a sequence number x is a predecessor/successor of y.
> + * they handle overflows/underflows and can correctly check for a
> + * predecessor/successor unless the variable sequence number has grown by
> + * more then 2**(bitwidth(x)-1)-1.
> + * This means that for a uint8_t with the maximum value 255, it would
> think: + *  - when adding nothing - it is neither a predecessor nor a
> successor + *  - before adding more than 127 to the starting value - it is
> a predecessor, + *  - when adding 128 - it is neither a predecessor nor a
> successor, + *  - after adding more than 127 to the starting value - it is
> a successor */ +#define seq_before(x, y) ({typeof(x) _dummy = (x - y); \
> +			_dummy > smallest_signed_int(_dummy); })
> +#define seq_after(x, y) seq_before(y, x)
> +
>  #endif	/* _LINUX_NET_H */

I suggested yesterday (probably too late) that it would be good to check the
type of both parameters (similar to the min and max functions in
include/linux/kernel.h

#define seq_before(x, y) ({typeof(x) _d1 = (x); \
			  typeof(y) _d2 = (y); \
			  (void) (&_d1 == &_d2); \
			  typeof(x) _dummy = (_d1 - _d2); \
			  _dummy > smallest_signed_int(_dummy); })


And your seq_before/after conflicts with the one defined in ppp_generic.c

drivers/net/ppp_generic.c:232:0: warning: "seq_before" redefined [enabled by 
default]
include/linux/net.h:312:0: note: this is the location of the previous 
definition
drivers/net/ppp_generic.c:233:0: warning: "seq_after" redefined [enabled by 
default]
include/linux/net.h:314:0: note: this is the location of the previous 
definition

The definition there is only for u32 - thus you would have to remove it and 
check that it always gives the same result:
#define seq_before(a, b)        ((s32)((a) - (b)) < 0)
#define seq_after(a, b)         ((s32)((a) - (b)) > 0)

But I would say that they have a different definition of seq_before. Changing 
that behaviour for batman-adv would not be that problematic, but maybe for 
ppp.

A defintion which should fulfil the requirements for ppp could be:

#define seq_after(x, y) ({typeof(x) _d1 = (x); \
			  typeof(y) _d2 = (y); \
			  (void) (&_d1 == &_d2); \
			  typeof(x) _dummy = (_d2 - _d1); \
			  _dummy > smallest_signed_int(_dummy); })
#define seq_before(x, y) ({typeof(x) _d1 = (x); \
			  typeof(y) _d2 = (y); \
			  (void) (&_d1 == &_d2); \
			  typeof(x) _dummy = (_d1 - _d2); \
			  _dummy >= smallest_signed_int(_dummy); })

Of course the comment above the seq_before/seq_after would be wrong.

/* Checks if a sequence number x is a predecessor/successor of y.
 * they handle overflows/underflows and can correctly check for a
 * predecessor/successor unless the variable sequence number has grown by
 * more then 2**(bitwidth(x)-1).
 * This means that for a uint8_t with the maximum value 255, it would think:
 *  - when adding nothing - it is neither a predecessor nor a successor
 *  - before adding more than 128 to the starting value - it is a predecessor,
 *  - after adding more than 127 to the starting value - it is a successor */

I think there could be more candidates which would like to use this abstract 
functionality. Maybe some one else on linux-kernel or netdev has a suggestion.

Kind regards,
	Sven

[-- Attachment #2: This is a digitally signed message part. --]
[-- Type: application/pgp-signature, Size: 836 bytes --]

Re: net: add seq_before/seq_after functions

[David Miller]

From: Sven Eckelmann <sven@narfation.org>
Date: Thu, 19 May 2011 10:54:32 +0200

> On Wednesday 18 May 2011 14:38:39 Antonio Quartulli wrote:
>> Introduce two operations to handle comparison between packet sequence
>> numbers taking into account overflow/wraparound. Batman-adv uses
>> these functions already to check for successor packet even in case of
>> overflow.
> 
> Thanks for your efforts to bring that to the kernel. But when you prepare a 
> patch then you have to add a signoff. And also David S. Miller is the 
> maintainer for this header - it would be interesting to ask him first when we 
> want to change that file.

Well it makes no sense to add these interfaces until we see an
upstream submission of code which will actually use it.

Also I'm skeptical that such generic sounding interfaces make
sense when it appears to me that these are protocol specific
sequence number tests so probably belong in whatever protocol
is upcoming which will use these interfaces.

Again, this is why we want to see the code that's going to use
these new routines before we can seriously consider adding them
at all.

Re: net: add seq_before/seq_after functions

[Sven Eckelmann]

[-- Attachment #1: Type: Text/Plain, Size: 1736 bytes --]

On Thursday 19 May 2011 11:08:24 David Miller wrote:
> From: Sven Eckelmann <sven@narfation.org>
> Date: Thu, 19 May 2011 10:54:32 +0200
> 
> > On Wednesday 18 May 2011 14:38:39 Antonio Quartulli wrote:
> >> Introduce two operations to handle comparison between packet sequence
> >> numbers taking into account overflow/wraparound. Batman-adv uses
> >> these functions already to check for successor packet even in case of
> >> overflow.
> > 
> > Thanks for your efforts to bring that to the kernel. But when you prepare
> > a patch then you have to add a signoff. And also David S. Miller is the
> > maintainer for this header - it would be interesting to ask him first
> > when we want to change that file.
> 
> Well it makes no sense to add these interfaces until we see an
> upstream submission of code which will actually use it.
> 
> Also I'm skeptical that such generic sounding interfaces make
> sense when it appears to me that these are protocol specific
> sequence number tests so probably belong in whatever protocol
> is upcoming which will use these interfaces.
> 
> Again, this is why we want to see the code that's going to use
> these new routines before we can seriously consider adding them
> at all.

This is currently used by vis.c in net/batman-adv and could also be used by 
ppp-generic.c (with my changes of course). And it is planned to be used by 
transtable.c in net/batman-adv. The idea was to propose this to linux-
kernel/netdev before we move it to a place were only batman-adv can use it 
(the current situation is that vis.c in batman-adv can only use it).

It is ok that you say that it should be batman-adv specific - we only wanted 
to ask first.

Thanks,
	Sven

[-- Attachment #2: This is a digitally signed message part. --]
[-- Type: application/pgp-signature, Size: 836 bytes --]

Re: net: add seq_before/seq_after functions

[David Miller]

From: Sven Eckelmann <sven@narfation.org>
Date: Thu, 19 May 2011 11:21:21 +0200

> This is currently used by vis.c in net/batman-adv and could also be used by 
> ppp-generic.c (with my changes of course). And it is planned to be used by 
> transtable.c in net/batman-adv. The idea was to propose this to linux-
> kernel/netdev before we move it to a place were only batman-adv can use it 
> (the current situation is that vis.c in batman-adv can only use it).
> 
> It is ok that you say that it should be batman-adv specific - we only wanted 
> to ask first.

Well, this is a purely networking change, the header you're touching is
networking specific, so really in this case linux-kernel didn't need to
get involved :-)