Staging: batman-adv: Reorganize sequence number handling
authorSimon Wunderlich <siwu@hrz.tu-chemnitz.de>
Fri, 7 May 2010 19:47:24 +0000 (21:47 +0200)
committerGreg Kroah-Hartman <gregkh@suse.de>
Tue, 11 May 2010 20:42:39 +0000 (13:42 -0700)
commitf94cee241099b31732460c255c6af24979ec778e
treeeb1ec752a24ef310b7db71ede0ee9bf9dcbe9c2a
parentb7bce588b3a6a058e00d9629c25cf170dede63fc
Staging: batman-adv: Reorganize sequence number handling

BATMAN and broadcast packets are tracked with a sequence number window of
currently 64 entries to measure and avoid duplicates. Packets which have a
sequence number smaller than the newest received packet minus 64 are not
within this sequence number window anymore and are called "old packets"
from now on.

When old packets are received, the routing code assumes that the host of the
originator has been restarted. This assumption however might be wrong as
packets can also be delayed by NIC drivers, e.g. because of long queues or
collision detection in dense WiFi? environments. This behaviour can be
reproduced by doing a broadcast ping flood in a dense node environment.

The effect is that the sequence number window is jumping forth and back,
accepting and forwarding any packet (because packets are assumed to be "new")
and causing loops.

To overcome this problem, the sequence number handling has been reorganized.
When an old packet is received, the window is reset back only once. Other old
packets are dropped for (currently) 30 seconds to "protect" the new sequence
number and avoid the hopping as described above.

The reorganization brings some code cleanups (at least i hope you feel the
same) and also fixes a bug in count_real_packets() which falsely updated
the last_real_seqno for slightly older packets within the seqno window
if they are no duplicates.

This second version of the patch also fixes a problem where for seq_diff==64
bit_shift() reads from outside of the seqno window, and removes the loop
for seq_diff == -64 which was present in the first patch.

The third iteration also adds a window for the next expected sequence numbers.
This minimizes sequence number flapping for packets with very big differences
(e.g. 3 packets with seqno 0, 25000 and 50000 might still cause problems
without this window).

Signed-off-by: Simon Wunderlich <siwu@hrz.tu-chemnitz.de>
Signed-off-by: Andrew Lunn <andrew@lunn.ch>
Signed-off-by: Greg Kroah-Hartman <gregkh@suse.de>
drivers/staging/batman-adv/bitarray.c
drivers/staging/batman-adv/main.h
drivers/staging/batman-adv/originator.c
drivers/staging/batman-adv/routing.c
drivers/staging/batman-adv/types.h