Root/
1 | /* |
2 | * Copyright (C) 2006-2011 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 */ |
29 | uint8_t get_bit_status(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 */ |
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 |
100 | * it's 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 the it's "left" |
105 | * half. 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 | |
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 | */ |
130 | char bit_get_packet(void *priv, unsigned long *seq_bits, |
131 | int32_t seq_num_diff, int8_t set_mark) |
132 | { |
133 | struct bat_priv *bat_priv = (struct 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 | */ |
193 | int bit_packet_count(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 |
Branches:
ben-wpan
ben-wpan-stefan
javiroman/ks7010
jz-2.6.34
jz-2.6.34-rc5
jz-2.6.34-rc6
jz-2.6.34-rc7
jz-2.6.35
jz-2.6.36
jz-2.6.37
jz-2.6.38
jz-2.6.39
jz-3.0
jz-3.1
jz-3.11
jz-3.12
jz-3.13
jz-3.15
jz-3.16
jz-3.18-dt
jz-3.2
jz-3.3
jz-3.4
jz-3.5
jz-3.6
jz-3.6-rc2-pwm
jz-3.9
jz-3.9-clk
jz-3.9-rc8
jz47xx
jz47xx-2.6.38
master
Tags:
od-2011-09-04
od-2011-09-18
v2.6.34-rc5
v2.6.34-rc6
v2.6.34-rc7
v3.9