]>
Commit | Line | Data |
---|---|---|
c6c8fea2 | 1 | /* |
64afe353 | 2 | * Copyright (C) 2006-2011 B.A.T.M.A.N. contributors: |
c6c8fea2 SE |
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 */ | |
b2c44a53 DH |
29 | int get_bit_status(const unsigned long *seq_bits, uint32_t last_seqno, |
30 | uint32_t curr_seqno) | |
c6c8fea2 SE |
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 */ | |
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. */ | |
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 | |
015758d0 | 100 | * its position */ |
c6c8fea2 SE |
101 | /* for our example that would be: word[0] = 9800 + 0076 = |
102 | * 9876 */ | |
103 | } | |
015758d0 AQ |
104 | /* now for our last word, i==word_num, we only have its "left" half. |
105 | * that's the 1000 word in our example.*/ | |
c6c8fea2 SE |
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 | ||
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 | */ | |
b4e17054 SE |
130 | int bit_get_packet(void *priv, unsigned long *seq_bits, |
131 | int32_t seq_num_diff, int set_mark) | |
c6c8fea2 | 132 | { |
5f718c20 | 133 | struct bat_priv *bat_priv = priv; |
c6c8fea2 SE |
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 | */ | |
747e4221 | 193 | int bit_packet_count(const unsigned long *seq_bits) |
c6c8fea2 SE |
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 | } |