]>
Commit | Line | Data |
---|---|---|
60c778b2 | 1 | /* SCTP kernel implementation |
1da177e4 LT |
2 | * (C) Copyright IBM Corp. 2001, 2004 |
3 | * Copyright (c) 1999-2000 Cisco, Inc. | |
4 | * Copyright (c) 1999-2001 Motorola, Inc. | |
5 | * Copyright (c) 2001 Intel Corp. | |
6 | * | |
60c778b2 | 7 | * This file is part of the SCTP kernel implementation |
1da177e4 LT |
8 | * |
9 | * These functions manipulate sctp tsn mapping array. | |
10 | * | |
60c778b2 | 11 | * This SCTP implementation is free software; |
1da177e4 LT |
12 | * you can redistribute it and/or modify it under the terms of |
13 | * the GNU General Public License as published by | |
14 | * the Free Software Foundation; either version 2, or (at your option) | |
15 | * any later version. | |
16 | * | |
60c778b2 | 17 | * This SCTP implementation is distributed in the hope that it |
1da177e4 LT |
18 | * will be useful, but WITHOUT ANY WARRANTY; without even the implied |
19 | * ************************ | |
20 | * warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. | |
21 | * See the GNU General Public License for more details. | |
22 | * | |
23 | * You should have received a copy of the GNU General Public License | |
24 | * along with GNU CC; see the file COPYING. If not, write to | |
25 | * the Free Software Foundation, 59 Temple Place - Suite 330, | |
26 | * Boston, MA 02111-1307, USA. | |
27 | * | |
28 | * Please send any bug reports or fixes you make to the | |
29 | * email address(es): | |
91705c61 | 30 | * lksctp developers <linux-sctp@vger.kernel.org> |
1da177e4 | 31 | * |
1da177e4 LT |
32 | * Written or modified by: |
33 | * La Monte H.P. Yarroll <piggy@acm.org> | |
34 | * Jon Grimm <jgrimm@us.ibm.com> | |
35 | * Karl Knutson <karl@athena.chicago.il.us> | |
36 | * Sridhar Samudrala <sri@us.ibm.com> | |
1da177e4 LT |
37 | */ |
38 | ||
5a0e3ad6 | 39 | #include <linux/slab.h> |
1da177e4 | 40 | #include <linux/types.h> |
8e1ee18c | 41 | #include <linux/bitmap.h> |
1da177e4 LT |
42 | #include <net/sctp/sctp.h> |
43 | #include <net/sctp/sm.h> | |
44 | ||
45 | static void sctp_tsnmap_update(struct sctp_tsnmap *map); | |
8e1ee18c VY |
46 | static void sctp_tsnmap_find_gap_ack(unsigned long *map, __u16 off, |
47 | __u16 len, __u16 *start, __u16 *end); | |
70fc69bc | 48 | static int sctp_tsnmap_grow(struct sctp_tsnmap *map, u16 size); |
1da177e4 LT |
49 | |
50 | /* Initialize a block of memory as a tsnmap. */ | |
51 | struct sctp_tsnmap *sctp_tsnmap_init(struct sctp_tsnmap *map, __u16 len, | |
8e1ee18c | 52 | __u32 initial_tsn, gfp_t gfp) |
1da177e4 | 53 | { |
8e1ee18c VY |
54 | if (!map->tsn_map) { |
55 | map->tsn_map = kzalloc(len>>3, gfp); | |
56 | if (map->tsn_map == NULL) | |
57 | return NULL; | |
58 | ||
59 | map->len = len; | |
60 | } else { | |
61 | bitmap_zero(map->tsn_map, map->len); | |
62 | } | |
1da177e4 LT |
63 | |
64 | /* Keep track of TSNs represented by tsn_map. */ | |
65 | map->base_tsn = initial_tsn; | |
1da177e4 LT |
66 | map->cumulative_tsn_ack_point = initial_tsn - 1; |
67 | map->max_tsn_seen = map->cumulative_tsn_ack_point; | |
1da177e4 LT |
68 | map->num_dup_tsns = 0; |
69 | ||
70 | return map; | |
71 | } | |
72 | ||
8e1ee18c VY |
73 | void sctp_tsnmap_free(struct sctp_tsnmap *map) |
74 | { | |
75 | map->len = 0; | |
76 | kfree(map->tsn_map); | |
77 | } | |
78 | ||
1da177e4 LT |
79 | /* Test the tracking state of this TSN. |
80 | * Returns: | |
81 | * 0 if the TSN has not yet been seen | |
82 | * >0 if the TSN has been seen (duplicate) | |
83 | * <0 if the TSN is invalid (too large to track) | |
84 | */ | |
85 | int sctp_tsnmap_check(const struct sctp_tsnmap *map, __u32 tsn) | |
86 | { | |
8e1ee18c VY |
87 | u32 gap; |
88 | ||
89 | /* Check to see if this is an old TSN */ | |
90 | if (TSN_lte(tsn, map->cumulative_tsn_ack_point)) | |
91 | return 1; | |
92 | ||
93 | /* Verify that we can hold this TSN and that it will not | |
94 | * overlfow our map | |
95 | */ | |
96 | if (!TSN_lt(tsn, map->base_tsn + SCTP_TSN_MAP_SIZE)) | |
97 | return -1; | |
1da177e4 LT |
98 | |
99 | /* Calculate the index into the mapping arrays. */ | |
100 | gap = tsn - map->base_tsn; | |
101 | ||
8e1ee18c VY |
102 | /* Check to see if TSN has already been recorded. */ |
103 | if (gap < map->len && test_bit(gap, map->tsn_map)) | |
104 | return 1; | |
1da177e4 | 105 | else |
8e1ee18c | 106 | return 0; |
1da177e4 LT |
107 | } |
108 | ||
109 | ||
110 | /* Mark this TSN as seen. */ | |
4244854d NH |
111 | int sctp_tsnmap_mark(struct sctp_tsnmap *map, __u32 tsn, |
112 | struct sctp_transport *trans) | |
1da177e4 | 113 | { |
8e1ee18c | 114 | u16 gap; |
1da177e4 | 115 | |
1da177e4 | 116 | if (TSN_lt(tsn, map->base_tsn)) |
8e1ee18c | 117 | return 0; |
1da177e4 | 118 | |
1da177e4 LT |
119 | gap = tsn - map->base_tsn; |
120 | ||
70fc69bc | 121 | if (gap >= map->len && !sctp_tsnmap_grow(map, gap + 1)) |
8e1ee18c | 122 | return -ENOMEM; |
1da177e4 | 123 | |
8e1ee18c VY |
124 | if (!sctp_tsnmap_has_gap(map) && gap == 0) { |
125 | /* In this case the map has no gaps and the tsn we are | |
126 | * recording is the next expected tsn. We don't touch | |
127 | * the map but simply bump the values. | |
128 | */ | |
129 | map->max_tsn_seen++; | |
130 | map->cumulative_tsn_ack_point++; | |
4244854d NH |
131 | if (trans) |
132 | trans->sack_generation = | |
133 | trans->asoc->peer.sack_generation; | |
8e1ee18c VY |
134 | map->base_tsn++; |
135 | } else { | |
136 | /* Either we already have a gap, or about to record a gap, so | |
137 | * have work to do. | |
138 | * | |
139 | * Bump the max. | |
140 | */ | |
141 | if (TSN_lt(map->max_tsn_seen, tsn)) | |
142 | map->max_tsn_seen = tsn; | |
143 | ||
144 | /* Mark the TSN as received. */ | |
145 | set_bit(gap, map->tsn_map); | |
146 | ||
147 | /* Go fixup any internal TSN mapping variables including | |
148 | * cumulative_tsn_ack_point. | |
149 | */ | |
150 | sctp_tsnmap_update(map); | |
151 | } | |
152 | ||
153 | return 0; | |
1da177e4 LT |
154 | } |
155 | ||
156 | ||
157 | /* Initialize a Gap Ack Block iterator from memory being provided. */ | |
dda91928 DB |
158 | static void sctp_tsnmap_iter_init(const struct sctp_tsnmap *map, |
159 | struct sctp_tsnmap_iter *iter) | |
1da177e4 LT |
160 | { |
161 | /* Only start looking one past the Cumulative TSN Ack Point. */ | |
162 | iter->start = map->cumulative_tsn_ack_point + 1; | |
163 | } | |
164 | ||
165 | /* Get the next Gap Ack Blocks. Returns 0 if there was not another block | |
166 | * to get. | |
167 | */ | |
dda91928 DB |
168 | static int sctp_tsnmap_next_gap_ack(const struct sctp_tsnmap *map, |
169 | struct sctp_tsnmap_iter *iter, | |
170 | __u16 *start, __u16 *end) | |
1da177e4 | 171 | { |
8e1ee18c VY |
172 | int ended = 0; |
173 | __u16 start_ = 0, end_ = 0, offset; | |
1da177e4 LT |
174 | |
175 | /* If there are no more gap acks possible, get out fast. */ | |
176 | if (TSN_lte(map->max_tsn_seen, iter->start)) | |
177 | return 0; | |
178 | ||
8e1ee18c VY |
179 | offset = iter->start - map->base_tsn; |
180 | sctp_tsnmap_find_gap_ack(map->tsn_map, offset, map->len, | |
181 | &start_, &end_); | |
1da177e4 | 182 | |
8e1ee18c VY |
183 | /* The Gap Ack Block happens to end at the end of the map. */ |
184 | if (start_ && !end_) | |
185 | end_ = map->len - 1; | |
1da177e4 LT |
186 | |
187 | /* If we found a Gap Ack Block, return the start and end and | |
188 | * bump the iterator forward. | |
189 | */ | |
8e1ee18c | 190 | if (end_) { |
1da177e4 | 191 | /* Fix up the start and end based on the |
8e1ee18c | 192 | * Cumulative TSN Ack which is always 1 behind base. |
1da177e4 | 193 | */ |
8e1ee18c VY |
194 | *start = start_ + 1; |
195 | *end = end_ + 1; | |
1da177e4 LT |
196 | |
197 | /* Move the iterator forward. */ | |
198 | iter->start = map->cumulative_tsn_ack_point + *end + 1; | |
8e1ee18c | 199 | ended = 1; |
1da177e4 LT |
200 | } |
201 | ||
202 | return ended; | |
203 | } | |
204 | ||
205 | /* Mark this and any lower TSN as seen. */ | |
206 | void sctp_tsnmap_skip(struct sctp_tsnmap *map, __u32 tsn) | |
207 | { | |
8e1ee18c | 208 | u32 gap; |
1da177e4 | 209 | |
1da177e4 LT |
210 | if (TSN_lt(tsn, map->base_tsn)) |
211 | return; | |
8e1ee18c | 212 | if (!TSN_lt(tsn, map->base_tsn + SCTP_TSN_MAP_SIZE)) |
1da177e4 LT |
213 | return; |
214 | ||
215 | /* Bump the max. */ | |
216 | if (TSN_lt(map->max_tsn_seen, tsn)) | |
217 | map->max_tsn_seen = tsn; | |
218 | ||
1da177e4 LT |
219 | gap = tsn - map->base_tsn + 1; |
220 | ||
8e1ee18c VY |
221 | map->base_tsn += gap; |
222 | map->cumulative_tsn_ack_point += gap; | |
223 | if (gap >= map->len) { | |
224 | /* If our gap is larger then the map size, just | |
225 | * zero out the map. | |
226 | */ | |
227 | bitmap_zero(map->tsn_map, map->len); | |
228 | } else { | |
025dfdaf | 229 | /* If the gap is smaller than the map size, |
8e1ee18c VY |
230 | * shift the map by 'gap' bits and update further. |
231 | */ | |
232 | bitmap_shift_right(map->tsn_map, map->tsn_map, gap, map->len); | |
233 | sctp_tsnmap_update(map); | |
1da177e4 | 234 | } |
1da177e4 LT |
235 | } |
236 | ||
237 | /******************************************************************** | |
238 | * 2nd Level Abstractions | |
239 | ********************************************************************/ | |
240 | ||
241 | /* This private helper function updates the tsnmap buffers and | |
242 | * the Cumulative TSN Ack Point. | |
243 | */ | |
244 | static void sctp_tsnmap_update(struct sctp_tsnmap *map) | |
245 | { | |
8e1ee18c VY |
246 | u16 len; |
247 | unsigned long zero_bit; | |
248 | ||
249 | ||
250 | len = map->max_tsn_seen - map->cumulative_tsn_ack_point; | |
251 | zero_bit = find_first_zero_bit(map->tsn_map, len); | |
252 | if (!zero_bit) | |
253 | return; /* The first 0-bit is bit 0. nothing to do */ | |
254 | ||
255 | map->base_tsn += zero_bit; | |
256 | map->cumulative_tsn_ack_point += zero_bit; | |
1da177e4 | 257 | |
8e1ee18c | 258 | bitmap_shift_right(map->tsn_map, map->tsn_map, zero_bit, map->len); |
1da177e4 LT |
259 | } |
260 | ||
261 | /* How many data chunks are we missing from our peer? | |
262 | */ | |
263 | __u16 sctp_tsnmap_pending(struct sctp_tsnmap *map) | |
264 | { | |
265 | __u32 cum_tsn = map->cumulative_tsn_ack_point; | |
266 | __u32 max_tsn = map->max_tsn_seen; | |
267 | __u32 base_tsn = map->base_tsn; | |
268 | __u16 pending_data; | |
fc184f08 | 269 | u32 gap; |
1da177e4 LT |
270 | |
271 | pending_data = max_tsn - cum_tsn; | |
272 | gap = max_tsn - base_tsn; | |
273 | ||
8e1ee18c | 274 | if (gap == 0 || gap >= map->len) |
1da177e4 LT |
275 | goto out; |
276 | ||
fc184f08 | 277 | pending_data -= bitmap_weight(map->tsn_map, gap + 1); |
1da177e4 LT |
278 | out: |
279 | return pending_data; | |
280 | } | |
281 | ||
282 | /* This is a private helper for finding Gap Ack Blocks. It searches a | |
283 | * single array for the start and end of a Gap Ack Block. | |
284 | * | |
285 | * The flags "started" and "ended" tell is if we found the beginning | |
286 | * or (respectively) the end of a Gap Ack Block. | |
287 | */ | |
8e1ee18c VY |
288 | static void sctp_tsnmap_find_gap_ack(unsigned long *map, __u16 off, |
289 | __u16 len, __u16 *start, __u16 *end) | |
1da177e4 LT |
290 | { |
291 | int i = off; | |
292 | ||
293 | /* Look through the entire array, but break out | |
294 | * early if we have found the end of the Gap Ack Block. | |
295 | */ | |
296 | ||
297 | /* Also, stop looking past the maximum TSN seen. */ | |
298 | ||
299 | /* Look for the start. */ | |
8e1ee18c VY |
300 | i = find_next_bit(map, len, off); |
301 | if (i < len) | |
302 | *start = i; | |
1da177e4 LT |
303 | |
304 | /* Look for the end. */ | |
8e1ee18c | 305 | if (*start) { |
1da177e4 LT |
306 | /* We have found the start, let's find the |
307 | * end. If we find the end, break out. | |
308 | */ | |
8e1ee18c VY |
309 | i = find_next_zero_bit(map, len, i); |
310 | if (i < len) | |
311 | *end = i - 1; | |
1da177e4 LT |
312 | } |
313 | } | |
314 | ||
315 | /* Renege that we have seen a TSN. */ | |
316 | void sctp_tsnmap_renege(struct sctp_tsnmap *map, __u32 tsn) | |
317 | { | |
8e1ee18c | 318 | u32 gap; |
1da177e4 LT |
319 | |
320 | if (TSN_lt(tsn, map->base_tsn)) | |
321 | return; | |
8e1ee18c VY |
322 | /* Assert: TSN is in range. */ |
323 | if (!TSN_lt(tsn, map->base_tsn + map->len)) | |
1da177e4 LT |
324 | return; |
325 | ||
1da177e4 LT |
326 | gap = tsn - map->base_tsn; |
327 | ||
328 | /* Pretend we never saw the TSN. */ | |
8e1ee18c | 329 | clear_bit(gap, map->tsn_map); |
1da177e4 LT |
330 | } |
331 | ||
332 | /* How many gap ack blocks do we have recorded? */ | |
02015180 VY |
333 | __u16 sctp_tsnmap_num_gabs(struct sctp_tsnmap *map, |
334 | struct sctp_gap_ack_block *gabs) | |
1da177e4 LT |
335 | { |
336 | struct sctp_tsnmap_iter iter; | |
02015180 | 337 | int ngaps = 0; |
1da177e4 LT |
338 | |
339 | /* Refresh the gap ack information. */ | |
340 | if (sctp_tsnmap_has_gap(map)) { | |
59ed5aba | 341 | __u16 start = 0, end = 0; |
1da177e4 LT |
342 | sctp_tsnmap_iter_init(map, &iter); |
343 | while (sctp_tsnmap_next_gap_ack(map, &iter, | |
9f81bcd9 AV |
344 | &start, |
345 | &end)) { | |
1da177e4 | 346 | |
02015180 VY |
347 | gabs[ngaps].start = htons(start); |
348 | gabs[ngaps].end = htons(end); | |
349 | ngaps++; | |
350 | if (ngaps >= SCTP_MAX_GABS) | |
1da177e4 LT |
351 | break; |
352 | } | |
353 | } | |
02015180 | 354 | return ngaps; |
1da177e4 | 355 | } |
8e1ee18c | 356 | |
70fc69bc | 357 | static int sctp_tsnmap_grow(struct sctp_tsnmap *map, u16 size) |
8e1ee18c VY |
358 | { |
359 | unsigned long *new; | |
360 | unsigned long inc; | |
361 | u16 len; | |
362 | ||
70fc69bc | 363 | if (size > SCTP_TSN_MAP_SIZE) |
8e1ee18c VY |
364 | return 0; |
365 | ||
70fc69bc | 366 | inc = ALIGN((size - map->len), BITS_PER_LONG) + SCTP_TSN_MAP_INCREMENT; |
8e1ee18c VY |
367 | len = min_t(u16, map->len + inc, SCTP_TSN_MAP_SIZE); |
368 | ||
369 | new = kzalloc(len>>3, GFP_ATOMIC); | |
370 | if (!new) | |
371 | return 0; | |
372 | ||
70fc69bc LR |
373 | bitmap_copy(new, map->tsn_map, |
374 | map->max_tsn_seen - map->cumulative_tsn_ack_point); | |
8e1ee18c VY |
375 | kfree(map->tsn_map); |
376 | map->tsn_map = new; | |
377 | map->len = len; | |
378 | ||
379 | return 1; | |
380 | } |