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
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
From: Sven Eckelmann <[email protected]>
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.
On Thursday 19 May 2011 11:08:24 David Miller wrote:
> From: Sven Eckelmann <[email protected]>
> 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
From: Sven Eckelmann <[email protected]>
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 :-)