xref: /linux/net/batman-adv/bitarray.c (revision 26b0d14106954ae46d2f4f7eec3481828a210f7d)
1 /*
2  * Copyright (C) 2006-2012 B.A.T.M.A.N. contributors:
3  *
4  * Simon Wunderlich, Marek Lindner
5  *
6  * This program is free software; you can redistribute it and/or
7  * modify it under the terms of version 2 of the GNU General Public
8  * License as published by the Free Software Foundation.
9  *
10  * This program is distributed in the hope that it will be useful, but
11  * WITHOUT ANY WARRANTY; without even the implied warranty of
12  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
13  * General Public License for more details.
14  *
15  * You should have received a copy of the GNU General Public License
16  * along with this program; if not, write to the Free Software
17  * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA
18  * 02110-1301, USA
19  *
20  */
21 
22 #include "main.h"
23 #include "bitarray.h"
24 
25 #include <linux/bitops.h>
26 
27 /* shift the packet array by n places. */
28 static void bat_bitmap_shift_left(unsigned long *seq_bits, int32_t n)
29 {
30 	if (n <= 0 || n >= TQ_LOCAL_WINDOW_SIZE)
31 		return;
32 
33 	bitmap_shift_left(seq_bits, seq_bits, n, TQ_LOCAL_WINDOW_SIZE);
34 }
35 
36 
37 /* receive and process one packet within the sequence number window.
38  *
39  * returns:
40  *  1 if the window was moved (either new or very old)
41  *  0 if the window was not moved/shifted.
42  */
43 int bit_get_packet(void *priv, unsigned long *seq_bits,
44 		    int32_t seq_num_diff, int set_mark)
45 {
46 	struct bat_priv *bat_priv = priv;
47 
48 	/* sequence number is slightly older. We already got a sequence number
49 	 * higher than this one, so we just mark it. */
50 
51 	if ((seq_num_diff <= 0) && (seq_num_diff > -TQ_LOCAL_WINDOW_SIZE)) {
52 		if (set_mark)
53 			bat_set_bit(seq_bits, -seq_num_diff);
54 		return 0;
55 	}
56 
57 	/* sequence number is slightly newer, so we shift the window and
58 	 * set the mark if required */
59 
60 	if ((seq_num_diff > 0) && (seq_num_diff < TQ_LOCAL_WINDOW_SIZE)) {
61 		bat_bitmap_shift_left(seq_bits, seq_num_diff);
62 
63 		if (set_mark)
64 			bat_set_bit(seq_bits, 0);
65 		return 1;
66 	}
67 
68 	/* sequence number is much newer, probably missed a lot of packets */
69 
70 	if ((seq_num_diff >= TQ_LOCAL_WINDOW_SIZE) &&
71 	    (seq_num_diff < EXPECTED_SEQNO_RANGE)) {
72 		bat_dbg(DBG_BATMAN, bat_priv,
73 			"We missed a lot of packets (%i) !\n",
74 			seq_num_diff - 1);
75 		bitmap_zero(seq_bits, TQ_LOCAL_WINDOW_SIZE);
76 		if (set_mark)
77 			bat_set_bit(seq_bits, 0);
78 		return 1;
79 	}
80 
81 	/* received a much older packet. The other host either restarted
82 	 * or the old packet got delayed somewhere in the network. The
83 	 * packet should be dropped without calling this function if the
84 	 * seqno window is protected. */
85 
86 	if ((seq_num_diff <= -TQ_LOCAL_WINDOW_SIZE) ||
87 	    (seq_num_diff >= EXPECTED_SEQNO_RANGE)) {
88 
89 		bat_dbg(DBG_BATMAN, bat_priv,
90 			"Other host probably restarted!\n");
91 
92 		bitmap_zero(seq_bits, TQ_LOCAL_WINDOW_SIZE);
93 		if (set_mark)
94 			bat_set_bit(seq_bits, 0);
95 
96 		return 1;
97 	}
98 
99 	/* never reached */
100 	return 0;
101 }
102