aboutsummaryrefslogtreecommitdiffstats
path: root/net/sctp/tsnmap.c
diff options
context:
space:
mode:
authorVlad Yasevich <vladislav.yasevich@hp.com>2008-10-08 17:18:39 -0400
committerDavid S. Miller <davem@davemloft.net>2008-10-08 17:18:39 -0400
commit8e1ee18c332e08bee9d8bd66e63cd564fbf17fc2 (patch)
tree8dace1db660d555eb6e020f301fdfe6cf6c05b80 /net/sctp/tsnmap.c
parent3c689b7320ae6f20dba6a8b71806a6c6fd604ee8 (diff)
sctp: Rework the tsn map to use generic bitmap.
The tsn map currently use is 4K large and is stuck inside the sctp_association structure making memory references REALLY expensive. What we really need is at most 4K worth of bits so the biggest map we would have is 512 bytes. Also, the map is only really usefull when we have gaps to store and report. As such, starting with minimal map of say 32 TSNs (bits) should be enough for normal low-loss operations. We can grow the map by some multiple of 32 along with some extra room any time we receive the TSN which would put us outside of the map boundry. As we close gaps, we can shift the map to rebase it on the latest TSN we've seen. This saves 4088 bytes per association just in the map alone along savings from the now unnecessary structure members. Signed-off-by: Vlad Yasevich <vladislav.yasevich@hp.com> Signed-off-by: David S. Miller <davem@davemloft.net>
Diffstat (limited to 'net/sctp/tsnmap.c')
-rw-r--r--net/sctp/tsnmap.c331
1 files changed, 148 insertions, 183 deletions
diff --git a/net/sctp/tsnmap.c b/net/sctp/tsnmap.c
index f3e58b275905..142ed7ca424d 100644
--- a/net/sctp/tsnmap.c
+++ b/net/sctp/tsnmap.c
@@ -43,37 +43,44 @@
43 */ 43 */
44 44
45#include <linux/types.h> 45#include <linux/types.h>
46#include <linux/bitmap.h>
46#include <net/sctp/sctp.h> 47#include <net/sctp/sctp.h>
47#include <net/sctp/sm.h> 48#include <net/sctp/sm.h>
48 49
49static void sctp_tsnmap_update(struct sctp_tsnmap *map); 50static void sctp_tsnmap_update(struct sctp_tsnmap *map);
50static void sctp_tsnmap_find_gap_ack(__u8 *map, __u16 off, 51static void sctp_tsnmap_find_gap_ack(unsigned long *map, __u16 off,
51 __u16 len, __u16 base, 52 __u16 len, __u16 *start, __u16 *end);
52 int *started, __u16 *start, 53static int sctp_tsnmap_grow(struct sctp_tsnmap *map, u16 gap);
53 int *ended, __u16 *end);
54 54
55/* Initialize a block of memory as a tsnmap. */ 55/* Initialize a block of memory as a tsnmap. */
56struct sctp_tsnmap *sctp_tsnmap_init(struct sctp_tsnmap *map, __u16 len, 56struct sctp_tsnmap *sctp_tsnmap_init(struct sctp_tsnmap *map, __u16 len,
57 __u32 initial_tsn) 57 __u32 initial_tsn, gfp_t gfp)
58{ 58{
59 map->tsn_map = map->raw_map; 59 if (!map->tsn_map) {
60 map->overflow_map = map->tsn_map + len; 60 map->tsn_map = kzalloc(len>>3, gfp);
61 map->len = len; 61 if (map->tsn_map == NULL)
62 62 return NULL;
63 /* Clear out a TSN ack status. */ 63
64 memset(map->tsn_map, 0x00, map->len + map->len); 64 map->len = len;
65 } else {
66 bitmap_zero(map->tsn_map, map->len);
67 }
65 68
66 /* Keep track of TSNs represented by tsn_map. */ 69 /* Keep track of TSNs represented by tsn_map. */
67 map->base_tsn = initial_tsn; 70 map->base_tsn = initial_tsn;
68 map->overflow_tsn = initial_tsn + map->len;
69 map->cumulative_tsn_ack_point = initial_tsn - 1; 71 map->cumulative_tsn_ack_point = initial_tsn - 1;
70 map->max_tsn_seen = map->cumulative_tsn_ack_point; 72 map->max_tsn_seen = map->cumulative_tsn_ack_point;
71 map->malloced = 0;
72 map->num_dup_tsns = 0; 73 map->num_dup_tsns = 0;
73 74
74 return map; 75 return map;
75} 76}
76 77
78void sctp_tsnmap_free(struct sctp_tsnmap *map)
79{
80 map->len = 0;
81 kfree(map->tsn_map);
82}
83
77/* Test the tracking state of this TSN. 84/* Test the tracking state of this TSN.
78 * Returns: 85 * Returns:
79 * 0 if the TSN has not yet been seen 86 * 0 if the TSN has not yet been seen
@@ -82,66 +89,69 @@ struct sctp_tsnmap *sctp_tsnmap_init(struct sctp_tsnmap *map, __u16 len,
82 */ 89 */
83int sctp_tsnmap_check(const struct sctp_tsnmap *map, __u32 tsn) 90int sctp_tsnmap_check(const struct sctp_tsnmap *map, __u32 tsn)
84{ 91{
85 __s32 gap; 92 u32 gap;
86 int dup; 93
94 /* Check to see if this is an old TSN */
95 if (TSN_lte(tsn, map->cumulative_tsn_ack_point))
96 return 1;
97
98 /* Verify that we can hold this TSN and that it will not
99 * overlfow our map
100 */
101 if (!TSN_lt(tsn, map->base_tsn + SCTP_TSN_MAP_SIZE))
102 return -1;
87 103
88 /* Calculate the index into the mapping arrays. */ 104 /* Calculate the index into the mapping arrays. */
89 gap = tsn - map->base_tsn; 105 gap = tsn - map->base_tsn;
90 106
91 /* Verify that we can hold this TSN. */ 107 /* Check to see if TSN has already been recorded. */
92 if (gap >= (/* base */ map->len + /* overflow */ map->len)) { 108 if (gap < map->len && test_bit(gap, map->tsn_map))
93 dup = -1; 109 return 1;
94 goto out;
95 }
96
97 /* Honk if we've already seen this TSN.
98 * We have three cases:
99 * 1. The TSN is ancient or belongs to a previous tsn_map.
100 * 2. The TSN is already marked in the tsn_map.
101 * 3. The TSN is already marked in the tsn_map_overflow.
102 */
103 if (gap < 0 ||
104 (gap < map->len && map->tsn_map[gap]) ||
105 (gap >= map->len && map->overflow_map[gap - map->len]))
106 dup = 1;
107 else 110 else
108 dup = 0; 111 return 0;
109
110out:
111 return dup;
112} 112}
113 113
114 114
115/* Mark this TSN as seen. */ 115/* Mark this TSN as seen. */
116void sctp_tsnmap_mark(struct sctp_tsnmap *map, __u32 tsn) 116int sctp_tsnmap_mark(struct sctp_tsnmap *map, __u32 tsn)
117{ 117{
118 __s32 gap; 118 u16 gap;
119 119
120 /* Vacuously mark any TSN which precedes the map base or
121 * exceeds the end of the map.
122 */
123 if (TSN_lt(tsn, map->base_tsn)) 120 if (TSN_lt(tsn, map->base_tsn))
124 return; 121 return 0;
125 if (!TSN_lt(tsn, map->base_tsn + map->len + map->len))
126 return;
127
128 /* Bump the max. */
129 if (TSN_lt(map->max_tsn_seen, tsn))
130 map->max_tsn_seen = tsn;
131 122
132 /* Assert: TSN is in range. */
133 gap = tsn - map->base_tsn; 123 gap = tsn - map->base_tsn;
134 124
135 /* Mark the TSN as received. */ 125 if (gap >= map->len && !sctp_tsnmap_grow(map, gap))
136 if (gap < map->len) 126 return -ENOMEM;
137 map->tsn_map[gap]++;
138 else
139 map->overflow_map[gap - map->len]++;
140 127
141 /* Go fixup any internal TSN mapping variables including 128 if (!sctp_tsnmap_has_gap(map) && gap == 0) {
142 * cumulative_tsn_ack_point. 129 /* In this case the map has no gaps and the tsn we are
143 */ 130 * recording is the next expected tsn. We don't touch
144 sctp_tsnmap_update(map); 131 * the map but simply bump the values.
132 */
133 map->max_tsn_seen++;
134 map->cumulative_tsn_ack_point++;
135 map->base_tsn++;
136 } else {
137 /* Either we already have a gap, or about to record a gap, so
138 * have work to do.
139 *
140 * Bump the max.
141 */
142 if (TSN_lt(map->max_tsn_seen, tsn))
143 map->max_tsn_seen = tsn;
144
145 /* Mark the TSN as received. */
146 set_bit(gap, map->tsn_map);
147
148 /* Go fixup any internal TSN mapping variables including
149 * cumulative_tsn_ack_point.
150 */
151 sctp_tsnmap_update(map);
152 }
153
154 return 0;
145} 155}
146 156
147 157
@@ -160,66 +170,34 @@ SCTP_STATIC int sctp_tsnmap_next_gap_ack(const struct sctp_tsnmap *map,
160 struct sctp_tsnmap_iter *iter, 170 struct sctp_tsnmap_iter *iter,
161 __u16 *start, __u16 *end) 171 __u16 *start, __u16 *end)
162{ 172{
163 int started, ended; 173 int ended = 0;
164 __u16 start_, end_, offset; 174 __u16 start_ = 0, end_ = 0, offset;
165
166 /* We haven't found a gap yet. */
167 started = ended = 0;
168 175
169 /* If there are no more gap acks possible, get out fast. */ 176 /* If there are no more gap acks possible, get out fast. */
170 if (TSN_lte(map->max_tsn_seen, iter->start)) 177 if (TSN_lte(map->max_tsn_seen, iter->start))
171 return 0; 178 return 0;
172 179
173 /* Search the first mapping array. */ 180 offset = iter->start - map->base_tsn;
174 if (iter->start - map->base_tsn < map->len) { 181 sctp_tsnmap_find_gap_ack(map->tsn_map, offset, map->len,
175 182 &start_, &end_);
176 offset = iter->start - map->base_tsn;
177 sctp_tsnmap_find_gap_ack(map->tsn_map, offset, map->len, 0,
178 &started, &start_, &ended, &end_);
179 }
180
181 /* Do we need to check the overflow map? */
182 if (!ended) {
183 /* Fix up where we'd like to start searching in the
184 * overflow map.
185 */
186 if (iter->start - map->base_tsn < map->len)
187 offset = 0;
188 else
189 offset = iter->start - map->base_tsn - map->len;
190
191 /* Search the overflow map. */
192 sctp_tsnmap_find_gap_ack(map->overflow_map,
193 offset,
194 map->len,
195 map->len,
196 &started, &start_,
197 &ended, &end_);
198 }
199 183
200 /* The Gap Ack Block happens to end at the end of the 184 /* The Gap Ack Block happens to end at the end of the map. */
201 * overflow map. 185 if (start_ && !end_)
202 */ 186 end_ = map->len - 1;
203 if (started && !ended) {
204 ended++;
205 end_ = map->len + map->len - 1;
206 }
207 187
208 /* If we found a Gap Ack Block, return the start and end and 188 /* If we found a Gap Ack Block, return the start and end and
209 * bump the iterator forward. 189 * bump the iterator forward.
210 */ 190 */
211 if (ended) { 191 if (end_) {
212 /* Fix up the start and end based on the 192 /* Fix up the start and end based on the
213 * Cumulative TSN Ack offset into the map. 193 * Cumulative TSN Ack which is always 1 behind base.
214 */ 194 */
215 int gap = map->cumulative_tsn_ack_point - 195 *start = start_ + 1;
216 map->base_tsn; 196 *end = end_ + 1;
217
218 *start = start_ - gap;
219 *end = end_ - gap;
220 197
221 /* Move the iterator forward. */ 198 /* Move the iterator forward. */
222 iter->start = map->cumulative_tsn_ack_point + *end + 1; 199 iter->start = map->cumulative_tsn_ack_point + *end + 1;
200 ended = 1;
223 } 201 }
224 202
225 return ended; 203 return ended;
@@ -228,35 +206,33 @@ SCTP_STATIC int sctp_tsnmap_next_gap_ack(const struct sctp_tsnmap *map,
228/* Mark this and any lower TSN as seen. */ 206/* Mark this and any lower TSN as seen. */
229void sctp_tsnmap_skip(struct sctp_tsnmap *map, __u32 tsn) 207void sctp_tsnmap_skip(struct sctp_tsnmap *map, __u32 tsn)
230{ 208{
231 __s32 gap; 209 u32 gap;
232 210
233 /* Vacuously mark any TSN which precedes the map base or
234 * exceeds the end of the map.
235 */
236 if (TSN_lt(tsn, map->base_tsn)) 211 if (TSN_lt(tsn, map->base_tsn))
237 return; 212 return;
238 if (!TSN_lt(tsn, map->base_tsn + map->len + map->len)) 213 if (!TSN_lt(tsn, map->base_tsn + SCTP_TSN_MAP_SIZE))
239 return; 214 return;
240 215
241 /* Bump the max. */ 216 /* Bump the max. */
242 if (TSN_lt(map->max_tsn_seen, tsn)) 217 if (TSN_lt(map->max_tsn_seen, tsn))
243 map->max_tsn_seen = tsn; 218 map->max_tsn_seen = tsn;
244 219
245 /* Assert: TSN is in range. */
246 gap = tsn - map->base_tsn + 1; 220 gap = tsn - map->base_tsn + 1;
247 221
248 /* Mark the TSNs as received. */ 222 map->base_tsn += gap;
249 if (gap <= map->len) 223 map->cumulative_tsn_ack_point += gap;
250 memset(map->tsn_map, 0x01, gap); 224 if (gap >= map->len) {
251 else { 225 /* If our gap is larger then the map size, just
252 memset(map->tsn_map, 0x01, map->len); 226 * zero out the map.
253 memset(map->overflow_map, 0x01, (gap - map->len)); 227 */
228 bitmap_zero(map->tsn_map, map->len);
229 } else {
230 /* If the gap is smaller then the map size,
231 * shift the map by 'gap' bits and update further.
232 */
233 bitmap_shift_right(map->tsn_map, map->tsn_map, gap, map->len);
234 sctp_tsnmap_update(map);
254 } 235 }
255
256 /* Go fixup any internal TSN mapping variables including
257 * cumulative_tsn_ack_point.
258 */
259 sctp_tsnmap_update(map);
260} 236}
261 237
262/******************************************************************** 238/********************************************************************
@@ -268,27 +244,19 @@ void sctp_tsnmap_skip(struct sctp_tsnmap *map, __u32 tsn)
268 */ 244 */
269static void sctp_tsnmap_update(struct sctp_tsnmap *map) 245static void sctp_tsnmap_update(struct sctp_tsnmap *map)
270{ 246{
271 __u32 ctsn; 247 u16 len;
272 248 unsigned long zero_bit;
273 ctsn = map->cumulative_tsn_ack_point; 249
274 do { 250
275 ctsn++; 251 len = map->max_tsn_seen - map->cumulative_tsn_ack_point;
276 if (ctsn == map->overflow_tsn) { 252 zero_bit = find_first_zero_bit(map->tsn_map, len);
277 /* Now tsn_map must have been all '1's, 253 if (!zero_bit)
278 * so we swap the map and check the overflow table 254 return; /* The first 0-bit is bit 0. nothing to do */
279 */ 255
280 __u8 *tmp = map->tsn_map; 256 map->base_tsn += zero_bit;
281 memset(tmp, 0, map->len); 257 map->cumulative_tsn_ack_point += zero_bit;
282 map->tsn_map = map->overflow_map;
283 map->overflow_map = tmp;
284
285 /* Update the tsn_map boundaries. */
286 map->base_tsn += map->len;
287 map->overflow_tsn += map->len;
288 }
289 } while (map->tsn_map[ctsn - map->base_tsn]);
290 258
291 map->cumulative_tsn_ack_point = ctsn - 1; /* Back up one. */ 259 bitmap_shift_right(map->tsn_map, map->tsn_map, zero_bit, map->len);
292} 260}
293 261
294/* How many data chunks are we missing from our peer? 262/* How many data chunks are we missing from our peer?
@@ -299,31 +267,19 @@ __u16 sctp_tsnmap_pending(struct sctp_tsnmap *map)
299 __u32 max_tsn = map->max_tsn_seen; 267 __u32 max_tsn = map->max_tsn_seen;
300 __u32 base_tsn = map->base_tsn; 268 __u32 base_tsn = map->base_tsn;
301 __u16 pending_data; 269 __u16 pending_data;
302 __s32 gap, start, end, i; 270 u32 gap, i;
303 271
304 pending_data = max_tsn - cum_tsn; 272 pending_data = max_tsn - cum_tsn;
305 gap = max_tsn - base_tsn; 273 gap = max_tsn - base_tsn;
306 274
307 if (gap <= 0 || gap >= (map->len + map->len)) 275 if (gap == 0 || gap >= map->len)
308 goto out; 276 goto out;
309 277
310 start = ((cum_tsn >= base_tsn) ? (cum_tsn - base_tsn + 1) : 0); 278 for (i = 0; i < gap+1; i++) {
311 end = ((gap > map->len ) ? map->len : gap + 1); 279 if (test_bit(i, map->tsn_map))
312
313 for (i = start; i < end; i++) {
314 if (map->tsn_map[i])
315 pending_data--; 280 pending_data--;
316 } 281 }
317 282
318 if (gap >= map->len) {
319 start = 0;
320 end = gap - map->len + 1;
321 for (i = start; i < end; i++) {
322 if (map->overflow_map[i])
323 pending_data--;
324 }
325 }
326
327out: 283out:
328 return pending_data; 284 return pending_data;
329} 285}
@@ -334,10 +290,8 @@ out:
334 * The flags "started" and "ended" tell is if we found the beginning 290 * The flags "started" and "ended" tell is if we found the beginning
335 * or (respectively) the end of a Gap Ack Block. 291 * or (respectively) the end of a Gap Ack Block.
336 */ 292 */
337static void sctp_tsnmap_find_gap_ack(__u8 *map, __u16 off, 293static void sctp_tsnmap_find_gap_ack(unsigned long *map, __u16 off,
338 __u16 len, __u16 base, 294 __u16 len, __u16 *start, __u16 *end)
339 int *started, __u16 *start,
340 int *ended, __u16 *end)
341{ 295{
342 int i = off; 296 int i = off;
343 297
@@ -348,49 +302,36 @@ static void sctp_tsnmap_find_gap_ack(__u8 *map, __u16 off,
348 /* Also, stop looking past the maximum TSN seen. */ 302 /* Also, stop looking past the maximum TSN seen. */
349 303
350 /* Look for the start. */ 304 /* Look for the start. */
351 if (!(*started)) { 305 i = find_next_bit(map, len, off);
352 for (; i < len; i++) { 306 if (i < len)
353 if (map[i]) { 307 *start = i;
354 (*started)++;
355 *start = base + i;
356 break;
357 }
358 }
359 }
360 308
361 /* Look for the end. */ 309 /* Look for the end. */
362 if (*started) { 310 if (*start) {
363 /* We have found the start, let's find the 311 /* We have found the start, let's find the
364 * end. If we find the end, break out. 312 * end. If we find the end, break out.
365 */ 313 */
366 for (; i < len; i++) { 314 i = find_next_zero_bit(map, len, i);
367 if (!map[i]) { 315 if (i < len)
368 (*ended)++; 316 *end = i - 1;
369 *end = base + i - 1;
370 break;
371 }
372 }
373 } 317 }
374} 318}
375 319
376/* Renege that we have seen a TSN. */ 320/* Renege that we have seen a TSN. */
377void sctp_tsnmap_renege(struct sctp_tsnmap *map, __u32 tsn) 321void sctp_tsnmap_renege(struct sctp_tsnmap *map, __u32 tsn)
378{ 322{
379 __s32 gap; 323 u32 gap;
380 324
381 if (TSN_lt(tsn, map->base_tsn)) 325 if (TSN_lt(tsn, map->base_tsn))
382 return; 326 return;
383 if (!TSN_lt(tsn, map->base_tsn + map->len + map->len)) 327 /* Assert: TSN is in range. */
328 if (!TSN_lt(tsn, map->base_tsn + map->len))
384 return; 329 return;
385 330
386 /* Assert: TSN is in range. */
387 gap = tsn - map->base_tsn; 331 gap = tsn - map->base_tsn;
388 332
389 /* Pretend we never saw the TSN. */ 333 /* Pretend we never saw the TSN. */
390 if (gap < map->len) 334 clear_bit(gap, map->tsn_map);
391 map->tsn_map[gap] = 0;
392 else
393 map->overflow_map[gap - map->len] = 0;
394} 335}
395 336
396/* How many gap ack blocks do we have recorded? */ 337/* How many gap ack blocks do we have recorded? */
@@ -416,3 +357,27 @@ __u16 sctp_tsnmap_num_gabs(struct sctp_tsnmap *map)
416 } 357 }
417 return gabs; 358 return gabs;
418} 359}
360
361static int sctp_tsnmap_grow(struct sctp_tsnmap *map, u16 gap)
362{
363 unsigned long *new;
364 unsigned long inc;
365 u16 len;
366
367 if (gap >= SCTP_TSN_MAP_SIZE)
368 return 0;
369
370 inc = ALIGN((gap - map->len),BITS_PER_LONG) + SCTP_TSN_MAP_INCREMENT;
371 len = min_t(u16, map->len + inc, SCTP_TSN_MAP_SIZE);
372
373 new = kzalloc(len>>3, GFP_ATOMIC);
374 if (!new)
375 return 0;
376
377 bitmap_copy(new, map->tsn_map, map->max_tsn_seen - map->base_tsn);
378 kfree(map->tsn_map);
379 map->tsn_map = new;
380 map->len = len;
381
382 return 1;
383}