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 /* returns true if the corresponding bit in the given seq_bits indicates true
28 * and curr_seqno is within range of last_seqno */
get_bit_status(const unsigned long * seq_bits,uint32_t last_seqno,uint32_t curr_seqno)29 int get_bit_status(const unsigned long *seq_bits, uint32_t last_seqno,
30 uint32_t curr_seqno)
31 {
32 int32_t diff, word_offset, word_num;
33
34 diff = last_seqno - curr_seqno;
35 if (diff < 0 || diff >= TQ_LOCAL_WINDOW_SIZE) {
36 return 0;
37 } else {
38 /* which word */
39 word_num = (last_seqno - curr_seqno) / WORD_BIT_SIZE;
40 /* which position in the selected word */
41 word_offset = (last_seqno - curr_seqno) % WORD_BIT_SIZE;
42
43 if (test_bit(word_offset, &seq_bits[word_num]))
44 return 1;
45 else
46 return 0;
47 }
48 }
49
50 /* turn corresponding bit on, so we can remember that we got the packet */
bit_mark(unsigned long * seq_bits,int32_t n)51 void bit_mark(unsigned long *seq_bits, int32_t n)
52 {
53 int32_t word_offset, word_num;
54
55 /* if too old, just drop it */
56 if (n < 0 || n >= TQ_LOCAL_WINDOW_SIZE)
57 return;
58
59 /* which word */
60 word_num = n / WORD_BIT_SIZE;
61 /* which position in the selected word */
62 word_offset = n % WORD_BIT_SIZE;
63
64 set_bit(word_offset, &seq_bits[word_num]); /* turn the position on */
65 }
66
67 /* shift the packet array by n places. */
bit_shift(unsigned long * seq_bits,int32_t n)68 static void bit_shift(unsigned long *seq_bits, int32_t n)
69 {
70 int32_t word_offset, word_num;
71 int32_t i;
72
73 if (n <= 0 || n >= TQ_LOCAL_WINDOW_SIZE)
74 return;
75
76 word_offset = n % WORD_BIT_SIZE;/* shift how much inside each word */
77 word_num = n / WORD_BIT_SIZE; /* shift over how much (full) words */
78
79 for (i = NUM_WORDS - 1; i > word_num; i--) {
80 /* going from old to new, so we don't overwrite the data we copy
81 * from.
82 *
83 * left is high, right is low: FEDC BA98 7654 3210
84 * ^^ ^^
85 * vvvv
86 * ^^^^ = from, vvvvv =to, we'd have word_num==1 and
87 * word_offset==WORD_BIT_SIZE/2 ????? in this example.
88 * (=24 bits)
89 *
90 * our desired output would be: 9876 5432 1000 0000
91 * */
92
93 seq_bits[i] =
94 (seq_bits[i - word_num] << word_offset) +
95 /* take the lower port from the left half, shift it left
96 * to its final position */
97 (seq_bits[i - word_num - 1] >>
98 (WORD_BIT_SIZE-word_offset));
99 /* and the upper part of the right half and shift it left to
100 * its position */
101 /* for our example that would be: word[0] = 9800 + 0076 =
102 * 9876 */
103 }
104 /* now for our last word, i==word_num, we only have its "left" half.
105 * that's the 1000 word in our example.*/
106
107 seq_bits[i] = (seq_bits[i - word_num] << word_offset);
108
109 /* pad the rest with 0, if there is anything */
110 i--;
111
112 for (; i >= 0; i--)
113 seq_bits[i] = 0;
114 }
115
bit_reset_window(unsigned long * seq_bits)116 static void bit_reset_window(unsigned long *seq_bits)
117 {
118 int i;
119 for (i = 0; i < NUM_WORDS; i++)
120 seq_bits[i] = 0;
121 }
122
123
124 /* receive and process one packet within the sequence number window.
125 *
126 * returns:
127 * 1 if the window was moved (either new or very old)
128 * 0 if the window was not moved/shifted.
129 */
bit_get_packet(void * priv,unsigned long * seq_bits,int32_t seq_num_diff,int set_mark)130 int bit_get_packet(void *priv, unsigned long *seq_bits,
131 int32_t seq_num_diff, int set_mark)
132 {
133 struct bat_priv *bat_priv = priv;
134
135 /* sequence number is slightly older. We already got a sequence number
136 * higher than this one, so we just mark it. */
137
138 if ((seq_num_diff <= 0) && (seq_num_diff > -TQ_LOCAL_WINDOW_SIZE)) {
139 if (set_mark)
140 bit_mark(seq_bits, -seq_num_diff);
141 return 0;
142 }
143
144 /* sequence number is slightly newer, so we shift the window and
145 * set the mark if required */
146
147 if ((seq_num_diff > 0) && (seq_num_diff < TQ_LOCAL_WINDOW_SIZE)) {
148 bit_shift(seq_bits, seq_num_diff);
149
150 if (set_mark)
151 bit_mark(seq_bits, 0);
152 return 1;
153 }
154
155 /* sequence number is much newer, probably missed a lot of packets */
156
157 if ((seq_num_diff >= TQ_LOCAL_WINDOW_SIZE) &&
158 (seq_num_diff < EXPECTED_SEQNO_RANGE)) {
159 bat_dbg(DBG_BATMAN, bat_priv,
160 "We missed a lot of packets (%i) !\n",
161 seq_num_diff - 1);
162 bit_reset_window(seq_bits);
163 if (set_mark)
164 bit_mark(seq_bits, 0);
165 return 1;
166 }
167
168 /* received a much older packet. The other host either restarted
169 * or the old packet got delayed somewhere in the network. The
170 * packet should be dropped without calling this function if the
171 * seqno window is protected. */
172
173 if ((seq_num_diff <= -TQ_LOCAL_WINDOW_SIZE) ||
174 (seq_num_diff >= EXPECTED_SEQNO_RANGE)) {
175
176 bat_dbg(DBG_BATMAN, bat_priv,
177 "Other host probably restarted!\n");
178
179 bit_reset_window(seq_bits);
180 if (set_mark)
181 bit_mark(seq_bits, 0);
182
183 return 1;
184 }
185
186 /* never reached */
187 return 0;
188 }
189
190 /* count the hamming weight, how many good packets did we receive? just count
191 * the 1's.
192 */
bit_packet_count(const unsigned long * seq_bits)193 int bit_packet_count(const unsigned long *seq_bits)
194 {
195 int i, hamming = 0;
196
197 for (i = 0; i < NUM_WORDS; i++)
198 hamming += hweight_long(seq_bits[i]);
199
200 return hamming;
201 }
202