[B.A.T.M.A.N.] vis: (sometimes) missing entries

[B.A.T.M.A.N.] vis: (sometimes) missing entries

[Linus Lüssing]

[-- Attachment #1.1: Type: text/plain, Size: 4914 bytes --]

Hi guys,

Ok, and the second bug, which has been there even before the 0.2
release if I remember right, is, that seemingly random entries in
the vis-servers output are missing, even when having a setup with
single-interface nodes only. The probability seems to increase the
more nodes are in the mesh network. For instance, I'm right now
running a setup of 4 wifi routers + my laptop with the current
batman-adv maintenance version with my last vis patch. They are
all right next to each other and connected over wifi, therefore
they're all in the same neighbourhood. No downloads or any other
highly disturbing wifi traffic around.

With just 3 routers, there are only missing entries from time to
time, but with 5 devices, there is usually always at least one
entry missing. For example:

-----------------------------------------------------------------
sh-4.1# ./batctl vd dot && ./batctl o
digraph {
        "06:22:b0:98:94:0b" -> "06:22:b0:98:87:f9" [label="1.20"]
        "06:22:b0:98:94:0b" -> "06:22:b0:44:c6:59" [label="1.0"]
        "06:22:b0:98:94:0b" -> "00:13:e8:50:c0:ff" [label="1.0"]
        "06:22:b0:98:94:0b" -> "06:22:b0:44:94:5d" [label="1.20"]
        "06:22:b0:98:94:0b" -> "00:22:b0:98:94:0b" [label="HNA"]
        "06:22:b0:98:94:0b" -> "02:c7:5f:09:af:0f" [label="HNA"]
        subgraph "cluster_06:22:b0:98:94:0b" {
                "06:22:b0:98:94:0b" [peripheries=2]
        }
        "06:22:b0:98:87:f9" -> "06:22:b0:98:94:0b" [label="1.20"]
        "06:22:b0:98:87:f9" -> "06:22:b0:44:c6:59" [label="1.71"]
        "06:22:b0:98:87:f9" -> "00:13:e8:50:c0:ff" [label="1.32"]
        "06:22:b0:98:87:f9" -> "00:22:b0:98:87:f9" [label="HNA"]
        "06:22:b0:98:87:f9" -> "9e:03:d3:3e:3e:15" [label="HNA"]
        subgraph "cluster_06:22:b0:98:87:f9" {
                "06:22:b0:98:87:f9" [peripheries=2]
        }
        "06:22:b0:44:c6:59" -> "06:22:b0:98:87:f9" [label="1.15"]
        "06:22:b0:44:c6:59" -> "00:13:e8:50:c0:ff" [label="1.28"]
        "06:22:b0:44:c6:59" -> "06:22:b0:44:94:5d" [label="1.80"]
        "06:22:b0:44:c6:59" -> "46:b4:01:60:f6:57" [label="HNA"]
        "06:22:b0:44:c6:59" -> "00:22:b0:44:c6:59" [label="HNA"]
        subgraph "cluster_06:22:b0:44:c6:59" {
                "06:22:b0:44:c6:59" [peripheries=2]
        }
        "00:13:e8:50:c0:ff" -> "06:22:b0:98:87:f9" [label="1.3"]
        "00:13:e8:50:c0:ff" -> "06:22:b0:98:94:0b" [label="1.28"]
        "00:13:e8:50:c0:ff" -> "06:22:b0:44:c6:59" [label="1.36"]
        "00:13:e8:50:c0:ff" -> "06:22:b0:44:94:5d" [label="1.53"]
        "00:13:e8:50:c0:ff" -> "2e:bb:47:5b:b1:5e" [label="HNA"]
        subgraph "cluster_00:13:e8:50:c0:ff" {
                "00:13:e8:50:c0:ff" [peripheries=2]
        }
        "06:22:b0:44:94:5d" -> "06:22:b0:98:87:f9" [label="1.0"]
        "06:22:b0:44:94:5d" -> "06:22:b0:98:94:0b" [label="1.89"]
        "06:22:b0:44:94:5d" -> "06:22:b0:44:c6:59" [label="1.28"]
        "06:22:b0:44:94:5d" -> "00:13:e8:50:c0:ff" [label="1.49"]
        "06:22:b0:44:94:5d" -> "00:22:b0:44:94:5d" [label="HNA"]
        "06:22:b0:44:94:5d" -> "da:ef:64:a7:33:a7" [label="HNA"]
        subgraph "cluster_06:22:b0:44:94:5d" {
                "06:22:b0:44:94:5d" [peripheries=2]
        }
}
  Originator     (#/255)           Nexthop [outgoingIF]:   Potential nexthops ... [B.A.T.M.A.N. adv 0.2.1-beta, MainIF/MAC: wlan0/00:13:e8:50:c0:ff]
06:22:b0:98:87:f9  (252) 06:22:b0:98:87:f9 [     wlan0]: 06:22:b0:98:87:f9 (252) 06:22:b0:98:94:0b (232) 06:22:b0:44:94:5d (232) 06:22:b0:44:c6:59 (229)
06:22:b0:98:94:0b  (249) 06:22:b0:98:94:0b [     wlan0]: 06:22:b0:98:94:0b (249) 06:22:b0:44:94:5d (217) 06:22:b0:98:87:f9 (235) 06:22:b0:44:c6:59 (234)
06:22:b0:44:c6:59  (246) 06:22:b0:44:c6:59 [     wlan0]: 06:22:b0:44:c6:59 (246) 06:22:b0:44:94:5d (221) 06:22:b0:98:94:0b (229) 06:22:b0:98:87:f9 (225)
06:22:b0:44:94:5d  (242) 06:22:b0:44:94:5d [     wlan0]: 06:22:b0:44:94:5d (242) 06:22:b0:98:94:0b (225) 06:22:b0:98:87:f9 (212) 06:22:b0:44:c6:59 (227)
sh-4.1#
-----------------------------------------------------------------

I'd expect all 5 nodes to have a direct connection to all other 4
nodes. However, for instance 06:22:b0:98:87:f9 is just having
three. A couple of seconds later, the missing entry is there
again, but other ones can be missing.

What I also just noticed is, that when I refresh the vis-output
every second only the TQ values of _2_ entries at a time  get updated,
the other ones are static for quite a while. However, looking at
wireshark tells me, that I'm still getting a vis-packet of all other 4 nodes
every second. So it looks like the vis-server might not be always
updating its vis_hash to me, but not sure about that.

I'm also attaching a capture on the laptop's wifi interface while
I had been sending ping-floods to ensure that the tq-values should be
changing frequently (which is not the case according to the
vis-server-output).

Cheers, Linus

[-- Attachment #1.2: vis-series2.cap --]
[-- Type: application/cap, Size: 27431 bytes --]

[-- Attachment #2: Digital signature --]
[-- Type: application/pgp-signature, Size: 836 bytes --]

[B.A.T.M.A.N.] [PATCH] batman-adv: Fixing wrap-around bug in vis

[Linus Lüssing]

When the seqno for a vis packet had a wrap around from i.e. 255 to 0,
add_packet() would falsely claim the older packet with the seqno 255 as
newer as the one with the seqno of 0 and would therefore ignore the new
packet. This happens with all following vis packets until the old vis
packet expires after 180 seconds timeout. This patch fixes this issue
and gets rid of these highly undesired 3min. breaks for the vis-server.

Signed-off-by: Linus Lüssing <linus.luessing@web.de>
---
 batman-adv-kernelland/packet.h |    3 ++-
 batman-adv-kernelland/vis.c    |    3 ++-
 2 files changed, 4 insertions(+), 2 deletions(-)

diff --git a/batman-adv-kernelland/packet.h b/batman-adv-kernelland/packet.h
index c8b973f..df38883 100644
--- a/batman-adv-kernelland/packet.h
+++ b/batman-adv-kernelland/packet.h
@@ -106,7 +106,8 @@ struct vis_packet {
 	uint8_t  packet_type;
 	uint8_t  version;        /* batman version field */
 	uint8_t  vis_type;	 /* which type of vis-participant sent this? */
-	uint8_t  seqno;		 /* sequence number */
+	uint8_t  seqno;		 /* sequence number
+				  * (add_packet() expects uint8_t) */
 	uint8_t  entries;	 /* number of entries behind this struct */
 	uint8_t  ttl;		 /* TTL */
 	uint8_t  vis_orig[6];	 /* originator that informs about its
diff --git a/batman-adv-kernelland/vis.c b/batman-adv-kernelland/vis.c
index fa8a487..6cab4ba 100644
--- a/batman-adv-kernelland/vis.c
+++ b/batman-adv-kernelland/vis.c
@@ -213,7 +213,8 @@ static struct vis_info *add_packet(struct vis_packet *vis_packet,
 	old_info = hash_find(vis_hash, &search_elem);
 
 	if (old_info != NULL) {
-		if (vis_packet->seqno - old_info->packet.seqno <= 0) {
+		/* seqno is uint8_t, therefore checking for 127 */
+		if ((vis_packet->seqno - old_info->packet.seqno) > 127) {
 			if (old_info->packet.seqno == vis_packet->seqno) {
 				recv_list_add(&old_info->recv_list,
 					      vis_packet->sender_orig);
-- 
1.7.0

Re: [B.A.T.M.A.N.] [PATCH] batman-adv: Fixing wrap-around bug in vis

[Linus Lüssing]

[-- Attachment #1: Type: text/plain, Size: 2072 bytes --]

> +		if ((vis_packet->seqno - old_info->packet.seqno) > 127) {
If anyone might have a more generic solution instead of using the
fixed of 127 without having to utilise math.h, that'd be great.

Ok, and no some more words to the tests and discussions with Marek
yesterday and their results.

> What I also just noticed is, that when I refresh the vis-output
> every second only the TQ values of _2_ entries at a time  get updated,
> the other ones are static for quite a while. However, looking at
> wireshark tells me, that I'm still getting a vis-packet of all
> other 4 nodes                                                                                 
> every second. So it looks like the vis-server might not be always
> updating its vis_hash to me, but not sure about that.
The issue seemed to be the thing I just sent a patch for. Pfeh,
then I didn't see any ghost bug which was sometimes there and
sometimes not. I started to doubt about the setup a lot first :).

> I'd expect all 5 nodes to have a direct connection to all other 4
> nodes. However, for instance 06:22:b0:98:87:f9 is just having
> three. A couple of seconds later, the missing entry is there
> again, but other ones can be missing.
The line which is causing this behavior is in generate_vis_packet():
------
398                 if (orig_node->router != NULL
399                         && compare_orig(orig_node->router->addr,
400                                         orig_node->orig)
------
It turned out that this is not a bug and that it was intended to
leave out those vis entries. Looks like I had slightly different
expectations at the vis-server. I wanted to see all possible links
and alternative next-hops in the vis-graph while Marek enlightened
me, that this would increase the throughput usage a lot as for
instance a far distant node, from which we'd receive a batman-ogm
up to every 120 seconds would result into a vis-entry then.
So including alternative/non-used next-hops in the vis-output
might need a new discussion.

Cheers, Linus

[-- Attachment #2: Digital signature --]
[-- Type: application/pgp-signature, Size: 836 bytes --]

[B.A.T.M.A.N.] [PATCH] batman-adv: Fixing wrap-around bug in vis

[Linus Lüssing]

When the seqno for a vis packet had a wrap around from i.e. 255 to 0,
add_packet() would falsely claim the older packet with the seqno 255 as
newer as the one with the seqno of 0 and would therefore ignore the new
packet. This happens with all following vis packets until the old vis
packet expires after 180 seconds timeout. This patch fixes this issue
and gets rid of these highly undesired 3min. breaks for the vis-server.

Signed-off-by: Linus Lüssing <linus.luessing@web.de>
---
 batman-adv-kernelland/vis.c |    3 ++-
 1 files changed, 2 insertions(+), 1 deletions(-)

diff --git a/batman-adv-kernelland/vis.c b/batman-adv-kernelland/vis.c
index fa8a487..5735a6a 100644
--- a/batman-adv-kernelland/vis.c
+++ b/batman-adv-kernelland/vis.c
@@ -213,7 +213,8 @@ static struct vis_info *add_packet(struct vis_packet *vis_packet,
 	old_info = hash_find(vis_hash, &search_elem);
 
 	if (old_info != NULL) {
-		if (vis_packet->seqno - old_info->packet.seqno <= 0) {
+		if (vis_packet->seqno - old_info->packet.seqno
+		    <= 1 << 7 * sizeof(vis_packet->seqno)) {
 			if (old_info->packet.seqno == vis_packet->seqno) {
 				recv_list_add(&old_info->recv_list,
 					      vis_packet->sender_orig);
-- 
1.7.0

Re: [B.A.T.M.A.N.] [PATCH] batman-adv: Fixing wrap-around bug in vis

[Linus Lüssing]

[-- Attachment #1: Type: text/plain, Size: 1432 bytes --]

Sorry, typo there, has to be ">=" and not "<=" of coures. My
fault.

On Thu, Mar 11, 2010 at 10:19:06PM +0100, Linus Lüssing wrote:
> When the seqno for a vis packet had a wrap around from i.e. 255 to 0,
> add_packet() would falsely claim the older packet with the seqno 255 as
> newer as the one with the seqno of 0 and would therefore ignore the new
> packet. This happens with all following vis packets until the old vis
> packet expires after 180 seconds timeout. This patch fixes this issue
> and gets rid of these highly undesired 3min. breaks for the vis-server.
> 
> Signed-off-by: Linus Lüssing <linus.luessing@web.de>
> ---
>  batman-adv-kernelland/vis.c |    3 ++-
>  1 files changed, 2 insertions(+), 1 deletions(-)
> 
> diff --git a/batman-adv-kernelland/vis.c b/batman-adv-kernelland/vis.c
> index fa8a487..5735a6a 100644
> --- a/batman-adv-kernelland/vis.c
> +++ b/batman-adv-kernelland/vis.c
> @@ -213,7 +213,8 @@ static struct vis_info *add_packet(struct vis_packet *vis_packet,
>  	old_info = hash_find(vis_hash, &search_elem);
>  
>  	if (old_info != NULL) {
> -		if (vis_packet->seqno - old_info->packet.seqno <= 0) {
> +		if (vis_packet->seqno - old_info->packet.seqno
> +		    <= 1 << 7 * sizeof(vis_packet->seqno)) {
>  			if (old_info->packet.seqno == vis_packet->seqno) {
>  				recv_list_add(&old_info->recv_list,
>  					      vis_packet->sender_orig);
> -- 
> 1.7.0
> 

[-- Attachment #2: Digital signature --]
[-- Type: application/pgp-signature, Size: 836 bytes --]

Re: [B.A.T.M.A.N.] [PATCH] batman-adv: Fixing wrap-around bug in vis

[Sven Eckelmann]

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

Linus Lüssing wrote:
> -               if (vis_packet->seqno - old_info->packet.seqno <= 0) {
> +               if (vis_packet->seqno - old_info->packet.seqno
> +                   <= 1 << 7 * sizeof(vis_packet->seqno)) {

Shouldn't that be 
 1 << 7 + 8 * (sizeof(vis_packet->seqno) - 1))?

Otherwise you would have left the the sizeof(vis_packet->seqno) most 
significant bits 0 and the rest one. And maybe a seq_before/seq_after static 
inline function could be created to make this thing a lot more readable. You 
could also do that in a macro if you don't want to assume the type of 
vis_packet->seqno... which is probably what you tried by using sizeof

#define seq_before(x,y) ((x - y) >= 1 << 7 + 8 * (sizeof(x) - 1))
#define seq_after(x,y) ((y - x) >= 1 << 7 + 8 * (sizeof(x) - 1))
....

And maybe you see here that the equal part which is needed bellow that line 
isn't possible. So it must be changed to 

if (!seq_after(vis_packet->seqno, old_info->packet.seqno))

I hope that this is right - please check twice.


Best regards,
	Sven

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

Re: [B.A.T.M.A.N.] [PATCH] batman-adv: Fixing wrap-around bug in vis

[Sven Eckelmann]

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

Sven Eckelmann wrote:
> #define seq_before(x,y) ((x - y) >= 1 << 7 + 8 * (sizeof(x) - 1))
> #define seq_after(x,y) ((y - x) >= 1 << 7 + 8 * (sizeof(x) - 1))
> ....

That must be 
#define seq_before(x,y) ((x - y) > 1 << 7 + 8 * (sizeof(x) - 1))
#define seq_after(x,y) ((y - x) > 1 << 7 + 8 * (sizeof(x) - 1))

Or otherwise it would be wrong balanced between equal, after and before. In 
other words: For every x in N0 and y in N0 is only one true of (x == y) or 
seq_before(x, y) or seq_after(x, y) after the change of >= to >

Best regards,
	Sven

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

Re: [B.A.T.M.A.N.] [PATCH] batman-adv: Fixing wrap-around bug in vis

[Sven Eckelmann]

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

Sven Eckelmann wrote:
> That must be
> #define seq_before(x,y) ((x - y) > 1 << 7 + 8 * (sizeof(x) - 1))
> #define seq_after(x,y) ((y - x) > 1 << 7 + 8 * (sizeof(x) - 1))

Nearly correct but accidentally  deleted a =

#define seq_before(x,y) ((x - y) > 1 << 7 + 8 * (sizeof(x) - 1))
#define seq_after(x,y) ((y - x) >= 1 << 7 + 8 * (sizeof(x) - 1))

Best regards,
	Sven

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

Re: [B.A.T.M.A.N.] [PATCH] batman-adv: Fixing wrap-around bug in vis

[Linus Lüssing]

[-- Attachment #1: Type: text/plain, Size: 1018 bytes --]

Sorry still does not seem to work :). Despite testing it on a
setup in batman itself I also tested it with a small c program
(which does not work as expected either):
-----
#include <stdio.h>
#include <stdint.h>

#define seq_before(x,y) ((x - y) > 1 << 7 + 8 * (sizeof(x) - 1))
#define seq_after(x,y) ((y - x) >= 1 << 7 + 8 * (sizeof(x) - 1))

int main() {
        uint8_t old = 0;
        uint8_t new = 1;
        if (!seq_after(new,old))
                printf("foobar\n");

        return 0;
}
-----
$ ./test
foobar
$

On Fri, Mar 12, 2010 at 12:04:47AM +0100, Sven Eckelmann wrote:
> Sven Eckelmann wrote:
> > That must be
> > #define seq_before(x,y) ((x - y) > 1 << 7 + 8 * (sizeof(x) - 1))
> > #define seq_after(x,y) ((y - x) > 1 << 7 + 8 * (sizeof(x) - 1))
> 
> Nearly correct but accidentally  deleted a =
> 
> #define seq_before(x,y) ((x - y) > 1 << 7 + 8 * (sizeof(x) - 1))
> #define seq_after(x,y) ((y - x) >= 1 << 7 + 8 * (sizeof(x) - 1))
> 
> Best regards,
> 	Sven



[-- Attachment #2: Digital signature --]
[-- Type: application/pgp-signature, Size: 836 bytes --]

Re: [B.A.T.M.A.N.] [PATCH] batman-adv: Fixing wrap-around bug in vis

[Andrew Lunn]

On Fri, Mar 12, 2010 at 01:09:31AM +0100, Linus L??ssing wrote:
> Sorry still does not seem to work :). Despite testing it on a
> setup in batman itself I also tested it with a small c program
> (which does not work as expected either):
> -----
> #include <stdio.h>
> #include <stdint.h>
> 
> #define seq_before(x,y) ((x - y) > 1 << 7 + 8 * (sizeof(x) - 1))
> #define seq_after(x,y) ((y - x) >= 1 << 7 + 8 * (sizeof(x) - 1))
> 
> int main() {
>         uint8_t old = 0;
>         uint8_t new = 1;
>         if (!seq_after(new,old))
>                 printf("foobar\n");
> 
>         return 0;
> }

It is worth taking a look at include/linux/jiffies.h. The macros
time_after(), time_after_eq() etc.

	      Andrew

Re: [B.A.T.M.A.N.] [PATCH] batman-adv: Fixing wrap-around bug in vis

[Sven Eckelmann]

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

Linus Lüssing wrote:
> Sorry still does not seem to work :). Despite testing it on a
> setup in batman itself I also tested it with a small c program
> (which does not work as expected either):

But your version works? I would really doubt that when we do the same. The
macro will only replace the thing and we would have the same formular in that
situation.

> -----
> #include <stdio.h>
> #include <stdint.h>
> 
> #define seq_before(x,y) ((x - y) > 1 << 7 + 8 * (sizeof(x) - 1))
> #define seq_after(x,y) ((y - x) >= 1 << 7 + 8 * (sizeof(x) - 1))
> 
> int main() {
>         uint8_t old = 0;
>         uint8_t new = 1;
>         if (!seq_after(new,old))
>                 printf("foobar\n");
> 
>         return 0;
> }
> -----
> $ ./test
> foobar
> $

Now it gets real cruel, but who cares... C++ wasn't accept in the kernel, so we have
to deal with it using some GNUish stuff.

#define seq_before(x,y) ({typeof(x) _dummy = (x - y); \
                          _dummy > 1u << (7u + 8u * (sizeof(_dummy) - 1u));})
#define seq_after(x,y) ({typeof(x) _dummy = (y - x); \
                         _dummy >= 1u << (7u + 8u * (sizeof(_dummy) - 1u));})

Thanks for testing (I never did it :) ) and please test that one.

Best regards,
	Sven

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

Re: [B.A.T.M.A.N.] [PATCH] batman-adv: Fixing wrap-around bug in vis

[Sven Eckelmann]

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

Sven Eckelmann wrote:
> Now it gets real cruel, but who cares... C++ wasn't accept in the kernel,
>  so we have to deal with it using some GNUish stuff.
> 
> #define seq_before(x,y) ({typeof(x) _dummy = (x - y); \
>                           _dummy > 1u << (7u + 8u * (sizeof(_dummy) -
>  1u));}) #define seq_after(x,y) ({typeof(x) _dummy = (y - x); \
>                          _dummy >= 1u << (7u + 8u * (sizeof(_dummy) -
>  1u));})

After a small discussion with Marek I would like to suggest a easier readable 
and symmetric definition

/* 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 an 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)

Best regards,
	Sven

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

Re: [B.A.T.M.A.N.] [PATCH] batman-adv: Fixing wrap-around bug in vis

[Sven Eckelmann]

[-- Attachment #1.1: Type: Text/Plain, Size: 1670 bytes --]

Sven Eckelmann wrote:
> Sven Eckelmann wrote:
> > Now it gets real cruel, but who cares... C++ wasn't accept in the kernel,
> >  so we have to deal with it using some GNUish stuff.
> >
> > #define seq_before(x,y) ({typeof(x) _dummy = (x - y); \
> >                           _dummy > 1u << (7u + 8u * (sizeof(_dummy) -
> >  1u));}) #define seq_after(x,y) ({typeof(x) _dummy = (y - x); \
> >                          _dummy >= 1u << (7u + 8u * (sizeof(_dummy) -
> >  1u));})
> 
> After a small discussion with Marek I would like to suggest a easier
>  readable and symmetric definition
> 
> /* 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 an 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)

@Linus: Here a small testcase - just as prove that I tested it this time :D

Best regards,
	Sven

[-- Attachment #1.2: seq_before_test.c --]
[-- Type: text/x-csrc, Size: 3082 bytes --]

#include <stdio.h>
#include <stdint.h>
#include <stdlib.h>


/* 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 an 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)

#define type uint8_t

int main(void) {
	int first_round = 1;
	type x, y, i;
	type parts = ((type)~0u >> 1); /* 2**(bitwidth(type)-1)-1 */
	int error = 0;

	for (x = 0; first_round || x != 0; x++) {
		first_round = 0;

		y = x;

		/* Equal */
		{
			if (seq_before(x, y)) {
				printf("Wrong seq_before(%u, %u) == true\n", x, y);
				error = 1;
			}
			if (seq_after(x, y)) {
				printf("Wrong seq_after(%u, %u) == true\n", x, y);
				error = 1;
			}
			y++;
		}

		/* Successor */
		for (i = 0; i < parts; i++) {
			if (!seq_before(x, y)) {
				printf("Wrong seq_before(%u, %u) == true\n", x, y);
				error = 1;
			}
			if (seq_after(x, y)) {
				printf("Wrong seq_after(%u, %u) == true\n", x, y);
				error = 1;
			}
			y++;
		}

		/* Undefined */
		{
			if (seq_before(x, y)) {
				printf("Wrong seq_before(%u, %u) == true\n", x, y);
				error = 1;
			}
			if (seq_after(x, y)) {
				printf("Wrong seq_after(%u, %u) == true\n", x, y);
				error = 1;
			}
			y++;
		}

		/* Predecessor */
		for (i = 0; i < parts; i++) {
			if (seq_before(x, y)) {
				printf("Wrong seq_before(%u, %u) == true\n", x, y);
				error = 1;
			}
			if (!seq_after(x, y)) {
				printf("Wrong seq_after(%u, %u) == false\n", x, y);
				error = 1;
			}
			y++;
		}
		
		if (x != y) {
			printf("In round %u only tested till %u\n", x, y);
			error = 1;
		}

	}

	if (first_round) {
		printf("Not done a single test\n");
		error = 1;
	}
	

	/* 0 is successor of 0-1 */
	{
		x = (type)~0u;
		y = 0;
		if (!seq_before(x, y)) {
			printf("Wrong seq_before(%u, %u) == false\n", x, y);
			error = 1;
		}
		if (seq_after(x, y)) {
			printf("Wrong seq_after(%u, %u) == true\n", x, y);
			error = 1;
		}
		y++;
	}
	
	
	/* 0 is predecessor of 1 */
	{
		x = 1;
		y = 0;
		if (seq_before(x, y)) {
			printf("Wrong seq_before(%u, %u) == true\n", x, y);
			error = 1;
		}
		if (!seq_after(x, y)) {
			printf("Wrong seq_after(%u, %u) == false\n", x, y);
			error = 1;
		}
		y++;
	}

	return error;
}

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

Re: [B.A.T.M.A.N.] [PATCH] batman-adv: Fixing wrap-around bug in vis

[Simon Wunderlich]

[-- Attachment #1: Type: text/plain, Size: 1963 bytes --]

Hey,

nice catch!

I'd like to join the party and propose this version:

#define seq_before(x,y) ((int8_t) (x - y) < 0)
#define seq_after(x,y) seq_before(y,x)

Not so much bitshifting and may a little bit easier to 
understand, but also not general and does not pass Svens regression test ... :(

Wrong seq_before(0, 128) == true
Wrong seq_after(0, 128) == true
Wrong seq_before(1, 129) == true
Wrong seq_after(1, 129) == true
Wrong seq_before(2, 130) == true
Wrong seq_after(2, 130) == true
Wrong seq_before(3, 131) == true
Wrong seq_after(3, 131) == true
Wrong seq_before(4, 132) == true
Wrong seq_after(4, 132) == true
Wrong seq_before(5, 133) == true
Wrong seq_after(5, 133) == true

What do you think?  ;)

best regards
	Simon

On Thu, Mar 11, 2010 at 11:06:42PM +0100, Sven Eckelmann wrote:
> Linus Lüssing wrote:
> > -               if (vis_packet->seqno - old_info->packet.seqno <= 0) {
> > +               if (vis_packet->seqno - old_info->packet.seqno
> > +                   <= 1 << 7 * sizeof(vis_packet->seqno)) {
> 
> Shouldn't that be 
>  1 << 7 + 8 * (sizeof(vis_packet->seqno) - 1))?
> 
> Otherwise you would have left the the sizeof(vis_packet->seqno) most 
> significant bits 0 and the rest one. And maybe a seq_before/seq_after static 
> inline function could be created to make this thing a lot more readable. You 
> could also do that in a macro if you don't want to assume the type of 
> vis_packet->seqno... which is probably what you tried by using sizeof
> 
> #define seq_before(x,y) ((x - y) >= 1 << 7 + 8 * (sizeof(x) - 1))
> #define seq_after(x,y) ((y - x) >= 1 << 7 + 8 * (sizeof(x) - 1))
> ....
> 
> And maybe you see here that the equal part which is needed bellow that line 
> isn't possible. So it must be changed to 
> 
> if (!seq_after(vis_packet->seqno, old_info->packet.seqno))
> 
> I hope that this is right - please check twice.
> 
> 
> Best regards,
> 	Sven



[-- Attachment #2: Digital signature --]
[-- Type: application/pgp-signature, Size: 197 bytes --]

Re: [B.A.T.M.A.N.] [PATCH] batman-adv: Fixing wrap-around bug in vis

[Sven Eckelmann]

[-- Attachment #1: Type: text/plain, Size: 1305 bytes --]

On Fri, Mar 12, 2010 at 09:57:40PM +0100, Simon Wunderlich wrote:
> #define seq_before(x,y) ((int8_t) (x - y) < 0)
> #define seq_after(x,y) seq_before(y,x)
> 
> Not so much bitshifting and may a little bit easier to 
> understand, but also not general and does not pass Svens regression test ... :(
> 
> Wrong seq_before(0, 128) == true
> Wrong seq_after(0, 128) == true
> Wrong seq_before(1, 129) == true
> Wrong seq_after(1, 129) == true
> Wrong seq_before(2, 130) == true
> Wrong seq_after(2, 130) == true
> Wrong seq_before(3, 131) == true
> Wrong seq_after(3, 131) == true
> Wrong seq_before(4, 132) == true
> Wrong seq_after(4, 132) == true
> Wrong seq_before(5, 133) == true
> Wrong seq_after(5, 133) == true
> 
> What do you think?  ;)

This is the version which also was mentioned by andrew - which has the
advantage that it doesn't have "complicated" code, but isn't general purpose
for unsigned ints. The only reason I started with the more complicated stuff
was that Linus tried to make it easier to change the packet definition
without ruining the code at different places.

That it doesn't pass the test is only the due to my symmetric definition of the
operation. I am not really intrested in changing that code, but to support
Linus.

Best regards,
	Sven

[-- Attachment #2: Digital signature --]
[-- Type: application/pgp-signature, Size: 836 bytes --]

[B.A.T.M.A.N.] [PATCH] batman-adv: Fixing wrap-around bug in vis

[Linus Lüssing]

When the seqno for a vis packet had a wrap around from i.e. 255 to 0,
add_packet() would falsely claim the older packet with the seqno 255 as
newer as the one with the seqno of 0 and would therefore ignore the new
packet. This happens with all following vis packets until the old vis
packet expires after 180 seconds timeout. This patch fixes this issue
and gets rid of these highly undesired 3min. breaks for the vis-server.

Signed-off-by: Linus Lüssing <linus.luessing@web.de>
Signed-off-by: Sven Eckelmann <sven.eckelmann@gmx.de>
---
 batman-adv-kernelland/vis.c |   18 +++++++++++++++++-
 1 files changed, 17 insertions(+), 1 deletions(-)

diff --git a/batman-adv-kernelland/vis.c b/batman-adv-kernelland/vis.c
index fa8a487..5fd8710 100644
--- a/batman-adv-kernelland/vis.c
+++ b/batman-adv-kernelland/vis.c
@@ -28,6 +28,22 @@
 #include "hash.h"
 #include "compat.h"
 
+/* 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)
+
 struct hashtable_t *vis_hash;
 DEFINE_SPINLOCK(vis_hash_lock);
 static DEFINE_SPINLOCK(recv_list_lock);
@@ -213,7 +229,7 @@ static struct vis_info *add_packet(struct vis_packet *vis_packet,
 	old_info = hash_find(vis_hash, &search_elem);
 
 	if (old_info != NULL) {
-		if (vis_packet->seqno - old_info->packet.seqno <= 0) {
+		if (!seq_after(vis_packet->seqno, old_info->packet.seqno)) {
 			if (old_info->packet.seqno == vis_packet->seqno) {
 				recv_list_add(&old_info->recv_list,
 					      vis_packet->sender_orig);
-- 
1.7.0

Re: [B.A.T.M.A.N.] [PATCH] batman-adv: Fixing wrap-around bug in vis

[Marek Lindner]

On Sunday 14 March 2010 23:46:28 Linus Lüssing wrote:
> When the seqno for a vis packet had a wrap around from i.e. 255 to 0,
> add_packet() would falsely claim the older packet with the seqno 255 as
> newer as the one with the seqno of 0 and would therefore ignore the new
> packet. This happens with all following vis packets until the old vis
> packet expires after 180 seconds timeout. This patch fixes this issue
> and gets rid of these highly undesired 3min. breaks for the vis-server.

Applied in rev 1597.

Thanks,
Marek