1 /* SCTP kernel implementation
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.
7 * This file is part of the SCTP kernel implementation
9 * These functions manipulate sctp tsn mapping array.
11 * This SCTP implementation is free software;
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)
17 * This SCTP implementation is distributed in the hope that it
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.
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.
28 * Please send any bug reports or fixes you make to the
30 * lksctp developers <lksctp-developers@lists.sourceforge.net>
32 * Or submit a bug report through the following website:
33 * http://www.sf.net/projects/lksctp
35 * Written or modified by:
36 * La Monte H.P. Yarroll <piggy@acm.org>
37 * Jon Grimm <jgrimm@us.ibm.com>
38 * Karl Knutson <karl@athena.chicago.il.us>
39 * Sridhar Samudrala <sri@us.ibm.com>
41 * Any bugs reported given to us we will try to fix... any fixes shared will
42 * be incorporated into the next SCTP release.
45 #include <linux/types.h>
46 #include <linux/bitmap.h>
47 #include <net/sctp/sctp.h>
48 #include <net/sctp/sm.h>
50 static void sctp_tsnmap_update(struct sctp_tsnmap
*map
);
51 static void sctp_tsnmap_find_gap_ack(unsigned long *map
, __u16 off
,
52 __u16 len
, __u16
*start
, __u16
*end
);
53 static int sctp_tsnmap_grow(struct sctp_tsnmap
*map
, u16 gap
);
55 /* Initialize a block of memory as a tsnmap. */
56 struct sctp_tsnmap
*sctp_tsnmap_init(struct sctp_tsnmap
*map
, __u16 len
,
57 __u32 initial_tsn
, gfp_t gfp
)
60 map
->tsn_map
= kzalloc(len
>>3, gfp
);
61 if (map
->tsn_map
== NULL
)
66 bitmap_zero(map
->tsn_map
, map
->len
);
69 /* Keep track of TSNs represented by tsn_map. */
70 map
->base_tsn
= initial_tsn
;
71 map
->cumulative_tsn_ack_point
= initial_tsn
- 1;
72 map
->max_tsn_seen
= map
->cumulative_tsn_ack_point
;
73 map
->num_dup_tsns
= 0;
78 void sctp_tsnmap_free(struct sctp_tsnmap
*map
)
84 /* Test the tracking state of this TSN.
86 * 0 if the TSN has not yet been seen
87 * >0 if the TSN has been seen (duplicate)
88 * <0 if the TSN is invalid (too large to track)
90 int sctp_tsnmap_check(const struct sctp_tsnmap
*map
, __u32 tsn
)
94 /* Check to see if this is an old TSN */
95 if (TSN_lte(tsn
, map
->cumulative_tsn_ack_point
))
98 /* Verify that we can hold this TSN and that it will not
101 if (!TSN_lt(tsn
, map
->base_tsn
+ SCTP_TSN_MAP_SIZE
))
104 /* Calculate the index into the mapping arrays. */
105 gap
= tsn
- map
->base_tsn
;
107 /* Check to see if TSN has already been recorded. */
108 if (gap
< map
->len
&& test_bit(gap
, map
->tsn_map
))
115 /* Mark this TSN as seen. */
116 int sctp_tsnmap_mark(struct sctp_tsnmap
*map
, __u32 tsn
)
120 if (TSN_lt(tsn
, map
->base_tsn
))
123 gap
= tsn
- map
->base_tsn
;
125 if (gap
>= map
->len
&& !sctp_tsnmap_grow(map
, gap
))
128 if (!sctp_tsnmap_has_gap(map
) && gap
== 0) {
129 /* In this case the map has no gaps and the tsn we are
130 * recording is the next expected tsn. We don't touch
131 * the map but simply bump the values.
134 map
->cumulative_tsn_ack_point
++;
137 /* Either we already have a gap, or about to record a gap, so
142 if (TSN_lt(map
->max_tsn_seen
, tsn
))
143 map
->max_tsn_seen
= tsn
;
145 /* Mark the TSN as received. */
146 set_bit(gap
, map
->tsn_map
);
148 /* Go fixup any internal TSN mapping variables including
149 * cumulative_tsn_ack_point.
151 sctp_tsnmap_update(map
);
158 /* Initialize a Gap Ack Block iterator from memory being provided. */
159 SCTP_STATIC
void sctp_tsnmap_iter_init(const struct sctp_tsnmap
*map
,
160 struct sctp_tsnmap_iter
*iter
)
162 /* Only start looking one past the Cumulative TSN Ack Point. */
163 iter
->start
= map
->cumulative_tsn_ack_point
+ 1;
166 /* Get the next Gap Ack Blocks. Returns 0 if there was not another block
169 SCTP_STATIC
int sctp_tsnmap_next_gap_ack(const struct sctp_tsnmap
*map
,
170 struct sctp_tsnmap_iter
*iter
,
171 __u16
*start
, __u16
*end
)
174 __u16 start_
= 0, end_
= 0, offset
;
176 /* If there are no more gap acks possible, get out fast. */
177 if (TSN_lte(map
->max_tsn_seen
, iter
->start
))
180 offset
= iter
->start
- map
->base_tsn
;
181 sctp_tsnmap_find_gap_ack(map
->tsn_map
, offset
, map
->len
,
184 /* The Gap Ack Block happens to end at the end of the map. */
188 /* If we found a Gap Ack Block, return the start and end and
189 * bump the iterator forward.
192 /* Fix up the start and end based on the
193 * Cumulative TSN Ack which is always 1 behind base.
198 /* Move the iterator forward. */
199 iter
->start
= map
->cumulative_tsn_ack_point
+ *end
+ 1;
206 /* Mark this and any lower TSN as seen. */
207 void sctp_tsnmap_skip(struct sctp_tsnmap
*map
, __u32 tsn
)
211 if (TSN_lt(tsn
, map
->base_tsn
))
213 if (!TSN_lt(tsn
, map
->base_tsn
+ SCTP_TSN_MAP_SIZE
))
217 if (TSN_lt(map
->max_tsn_seen
, tsn
))
218 map
->max_tsn_seen
= tsn
;
220 gap
= tsn
- map
->base_tsn
+ 1;
222 map
->base_tsn
+= gap
;
223 map
->cumulative_tsn_ack_point
+= gap
;
224 if (gap
>= map
->len
) {
225 /* If our gap is larger then the map size, just
228 bitmap_zero(map
->tsn_map
, map
->len
);
230 /* If the gap is smaller than the map size,
231 * shift the map by 'gap' bits and update further.
233 bitmap_shift_right(map
->tsn_map
, map
->tsn_map
, gap
, map
->len
);
234 sctp_tsnmap_update(map
);
238 /********************************************************************
239 * 2nd Level Abstractions
240 ********************************************************************/
242 /* This private helper function updates the tsnmap buffers and
243 * the Cumulative TSN Ack Point.
245 static void sctp_tsnmap_update(struct sctp_tsnmap
*map
)
248 unsigned long zero_bit
;
251 len
= map
->max_tsn_seen
- map
->cumulative_tsn_ack_point
;
252 zero_bit
= find_first_zero_bit(map
->tsn_map
, len
);
254 return; /* The first 0-bit is bit 0. nothing to do */
256 map
->base_tsn
+= zero_bit
;
257 map
->cumulative_tsn_ack_point
+= zero_bit
;
259 bitmap_shift_right(map
->tsn_map
, map
->tsn_map
, zero_bit
, map
->len
);
262 /* How many data chunks are we missing from our peer?
264 __u16
sctp_tsnmap_pending(struct sctp_tsnmap
*map
)
266 __u32 cum_tsn
= map
->cumulative_tsn_ack_point
;
267 __u32 max_tsn
= map
->max_tsn_seen
;
268 __u32 base_tsn
= map
->base_tsn
;
272 pending_data
= max_tsn
- cum_tsn
;
273 gap
= max_tsn
- base_tsn
;
275 if (gap
== 0 || gap
>= map
->len
)
278 for (i
= 0; i
< gap
+1; i
++) {
279 if (test_bit(i
, map
->tsn_map
))
287 /* This is a private helper for finding Gap Ack Blocks. It searches a
288 * single array for the start and end of a Gap Ack Block.
290 * The flags "started" and "ended" tell is if we found the beginning
291 * or (respectively) the end of a Gap Ack Block.
293 static void sctp_tsnmap_find_gap_ack(unsigned long *map
, __u16 off
,
294 __u16 len
, __u16
*start
, __u16
*end
)
298 /* Look through the entire array, but break out
299 * early if we have found the end of the Gap Ack Block.
302 /* Also, stop looking past the maximum TSN seen. */
304 /* Look for the start. */
305 i
= find_next_bit(map
, len
, off
);
309 /* Look for the end. */
311 /* We have found the start, let's find the
312 * end. If we find the end, break out.
314 i
= find_next_zero_bit(map
, len
, i
);
320 /* Renege that we have seen a TSN. */
321 void sctp_tsnmap_renege(struct sctp_tsnmap
*map
, __u32 tsn
)
325 if (TSN_lt(tsn
, map
->base_tsn
))
327 /* Assert: TSN is in range. */
328 if (!TSN_lt(tsn
, map
->base_tsn
+ map
->len
))
331 gap
= tsn
- map
->base_tsn
;
333 /* Pretend we never saw the TSN. */
334 clear_bit(gap
, map
->tsn_map
);
337 /* How many gap ack blocks do we have recorded? */
338 __u16
sctp_tsnmap_num_gabs(struct sctp_tsnmap
*map
,
339 struct sctp_gap_ack_block
*gabs
)
341 struct sctp_tsnmap_iter iter
;
344 /* Refresh the gap ack information. */
345 if (sctp_tsnmap_has_gap(map
)) {
347 sctp_tsnmap_iter_init(map
, &iter
);
348 while (sctp_tsnmap_next_gap_ack(map
, &iter
,
352 gabs
[ngaps
].start
= htons(start
);
353 gabs
[ngaps
].end
= htons(end
);
355 if (ngaps
>= SCTP_MAX_GABS
)
362 static int sctp_tsnmap_grow(struct sctp_tsnmap
*map
, u16 gap
)
368 if (gap
>= SCTP_TSN_MAP_SIZE
)
371 inc
= ALIGN((gap
- map
->len
),BITS_PER_LONG
) + SCTP_TSN_MAP_INCREMENT
;
372 len
= min_t(u16
, map
->len
+ inc
, SCTP_TSN_MAP_SIZE
);
374 new = kzalloc(len
>>3, GFP_ATOMIC
);
378 bitmap_copy(new, map
->tsn_map
, map
->max_tsn_seen
- map
->base_tsn
);
This page took 0.037692 seconds and 5 git commands to generate.