1 /* SCTP kernel reference Implementation
2 * Copyright (c) 1999-2000 Cisco, Inc.
3 * Copyright (c) 1999-2001 Motorola, Inc.
4 * Copyright (c) 2001-2003 International Business Machines, Corp.
5 * Copyright (c) 2001 Intel Corp.
7 * This file is part of the SCTP kernel reference Implementation
9 * These functions manipulate sctp tsn mapping array.
11 * The SCTP reference 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 * The SCTP reference 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>
40 * Any bugs reported given to us we will try to fix... any fixes shared will
41 * be incorporated into the next SCTP release.
44 #include <linux/types.h>
45 #include <net/sctp/sctp.h>
46 #include <net/sctp/sm.h>
48 static void sctp_tsnmap_update(struct sctp_tsnmap
*map
);
49 static void sctp_tsnmap_find_gap_ack(__u8
*map
, __u16 off
,
50 __u16 len
, __u16 base
,
51 int *started
, __u16
*start
,
52 int *ended
, __u16
*end
);
54 /* Create a new sctp_tsnmap.
55 * Allocate room to store at least 'len' contiguous TSNs.
57 struct sctp_tsnmap
*sctp_tsnmap_new(__u16 len
, __u32 initial_tsn
, int gfp
)
59 struct sctp_tsnmap
*retval
;
61 retval
= kmalloc(sizeof(struct sctp_tsnmap
) +
62 sctp_tsnmap_storage_size(len
), gfp
);
66 if (!sctp_tsnmap_init(retval
, len
, initial_tsn
))
77 /* Initialize a block of memory as a tsnmap. */
78 struct sctp_tsnmap
*sctp_tsnmap_init(struct sctp_tsnmap
*map
, __u16 len
,
81 map
->tsn_map
= map
->raw_map
;
82 map
->overflow_map
= map
->tsn_map
+ len
;
85 /* Clear out a TSN ack status. */
86 memset(map
->tsn_map
, 0x00, map
->len
+ map
->len
);
88 /* Keep track of TSNs represented by tsn_map. */
89 map
->base_tsn
= initial_tsn
;
90 map
->overflow_tsn
= initial_tsn
+ map
->len
;
91 map
->cumulative_tsn_ack_point
= initial_tsn
- 1;
92 map
->max_tsn_seen
= map
->cumulative_tsn_ack_point
;
94 map
->num_dup_tsns
= 0;
99 /* Test the tracking state of this TSN.
101 * 0 if the TSN has not yet been seen
102 * >0 if the TSN has been seen (duplicate)
103 * <0 if the TSN is invalid (too large to track)
105 int sctp_tsnmap_check(const struct sctp_tsnmap
*map
, __u32 tsn
)
110 /* Calculate the index into the mapping arrays. */
111 gap
= tsn
- map
->base_tsn
;
113 /* Verify that we can hold this TSN. */
114 if (gap
>= (/* base */ map
->len
+ /* overflow */ map
->len
)) {
119 /* Honk if we've already seen this TSN.
120 * We have three cases:
121 * 1. The TSN is ancient or belongs to a previous tsn_map.
122 * 2. The TSN is already marked in the tsn_map.
123 * 3. The TSN is already marked in the tsn_map_overflow.
126 (gap
< map
->len
&& map
->tsn_map
[gap
]) ||
127 (gap
>= map
->len
&& map
->overflow_map
[gap
- map
->len
]))
137 /* Mark this TSN as seen. */
138 void sctp_tsnmap_mark(struct sctp_tsnmap
*map
, __u32 tsn
)
142 /* Vacuously mark any TSN which precedes the map base or
143 * exceeds the end of the map.
145 if (TSN_lt(tsn
, map
->base_tsn
))
147 if (!TSN_lt(tsn
, map
->base_tsn
+ map
->len
+ map
->len
))
151 if (TSN_lt(map
->max_tsn_seen
, tsn
))
152 map
->max_tsn_seen
= tsn
;
154 /* Assert: TSN is in range. */
155 gap
= tsn
- map
->base_tsn
;
157 /* Mark the TSN as received. */
161 map
->overflow_map
[gap
- map
->len
]++;
163 /* Go fixup any internal TSN mapping variables including
164 * cumulative_tsn_ack_point.
166 sctp_tsnmap_update(map
);
170 /* Dispose of a tsnmap. */
171 void sctp_tsnmap_free(struct sctp_tsnmap
*map
)
177 /* Initialize a Gap Ack Block iterator from memory being provided. */
178 void sctp_tsnmap_iter_init(const struct sctp_tsnmap
*map
,
179 struct sctp_tsnmap_iter
*iter
)
181 /* Only start looking one past the Cumulative TSN Ack Point. */
182 iter
->start
= map
->cumulative_tsn_ack_point
+ 1;
185 /* Get the next Gap Ack Blocks. Returns 0 if there was not another block
188 int sctp_tsnmap_next_gap_ack(const struct sctp_tsnmap
*map
,
189 struct sctp_tsnmap_iter
*iter
, __u16
*start
, __u16
*end
)
192 __u16 _start
, _end
, offset
;
194 /* We haven't found a gap yet. */
197 /* If there are no more gap acks possible, get out fast. */
198 if (TSN_lte(map
->max_tsn_seen
, iter
->start
))
201 /* Search the first mapping array. */
202 if (iter
->start
- map
->base_tsn
< map
->len
) {
204 offset
= iter
->start
- map
->base_tsn
;
205 sctp_tsnmap_find_gap_ack(map
->tsn_map
, offset
, map
->len
, 0,
206 &started
, &_start
, &ended
, &_end
);
209 /* Do we need to check the overflow map? */
211 /* Fix up where we'd like to start searching in the
214 if (iter
->start
- map
->base_tsn
< map
->len
)
217 offset
= iter
->start
- map
->base_tsn
- map
->len
;
219 /* Search the overflow map. */
220 sctp_tsnmap_find_gap_ack(map
->overflow_map
,
228 /* The Gap Ack Block happens to end at the end of the
231 if (started
&& !ended
) {
233 _end
= map
->len
+ map
->len
- 1;
236 /* If we found a Gap Ack Block, return the start and end and
237 * bump the iterator forward.
240 /* Fix up the start and end based on the
241 * Cumulative TSN Ack offset into the map.
243 int gap
= map
->cumulative_tsn_ack_point
-
246 *start
= _start
- gap
;
249 /* Move the iterator forward. */
250 iter
->start
= map
->cumulative_tsn_ack_point
+ *end
+ 1;
256 /********************************************************************
257 * 2nd Level Abstractions
258 ********************************************************************/
260 /* This private helper function updates the tsnmap buffers and
261 * the Cumulative TSN Ack Point.
263 static void sctp_tsnmap_update(struct sctp_tsnmap
*map
)
267 ctsn
= map
->cumulative_tsn_ack_point
;
270 if (ctsn
== map
->overflow_tsn
) {
271 /* Now tsn_map must have been all '1's,
272 * so we swap the map and check the overflow table
274 __u8
*tmp
= map
->tsn_map
;
275 memset(tmp
, 0, map
->len
);
276 map
->tsn_map
= map
->overflow_map
;
277 map
->overflow_map
= tmp
;
279 /* Update the tsn_map boundaries. */
280 map
->base_tsn
+= map
->len
;
281 map
->overflow_tsn
+= map
->len
;
283 } while (map
->tsn_map
[ctsn
- map
->base_tsn
]);
285 map
->cumulative_tsn_ack_point
= ctsn
- 1; /* Back up one. */
288 /* How many data chunks are we missing from our peer?
290 __u16
sctp_tsnmap_pending(struct sctp_tsnmap
*map
)
292 __u32 cum_tsn
= map
->cumulative_tsn_ack_point
;
293 __u32 max_tsn
= map
->max_tsn_seen
;
294 __u32 base_tsn
= map
->base_tsn
;
296 __s32 gap
, start
, end
, i
;
298 pending_data
= max_tsn
- cum_tsn
;
299 gap
= max_tsn
- base_tsn
;
301 if (gap
<= 0 || gap
>= (map
->len
+ map
->len
))
304 start
= ((cum_tsn
>= base_tsn
) ? (cum_tsn
- base_tsn
+ 1) : 0);
305 end
= ((gap
> map
->len
) ? map
->len
: gap
+ 1);
307 for (i
= start
; i
< end
; i
++) {
312 if (gap
>= map
->len
) {
314 end
= gap
- map
->len
+ 1;
315 for (i
= start
; i
< end
; i
++) {
316 if (map
->overflow_map
[i
])
325 /* This is a private helper for finding Gap Ack Blocks. It searches a
326 * single array for the start and end of a Gap Ack Block.
328 * The flags "started" and "ended" tell is if we found the beginning
329 * or (respectively) the end of a Gap Ack Block.
331 static void sctp_tsnmap_find_gap_ack(__u8
*map
, __u16 off
,
332 __u16 len
, __u16 base
,
333 int *started
, __u16
*start
,
334 int *ended
, __u16
*end
)
338 /* Look through the entire array, but break out
339 * early if we have found the end of the Gap Ack Block.
342 /* Also, stop looking past the maximum TSN seen. */
344 /* Look for the start. */
346 for (; i
< len
; i
++) {
355 /* Look for the end. */
357 /* We have found the start, let's find the
358 * end. If we find the end, break out.
360 for (; i
< len
; i
++) {
370 /* Renege that we have seen a TSN. */
371 void sctp_tsnmap_renege(struct sctp_tsnmap
*map
, __u32 tsn
)
375 if (TSN_lt(tsn
, map
->base_tsn
))
377 if (!TSN_lt(tsn
, map
->base_tsn
+ map
->len
+ map
->len
))
380 /* Assert: TSN is in range. */
381 gap
= tsn
- map
->base_tsn
;
383 /* Pretend we never saw the TSN. */
385 map
->tsn_map
[gap
] = 0;
387 map
->overflow_map
[gap
- map
->len
] = 0;
390 /* How many gap ack blocks do we have recorded? */
391 __u16
sctp_tsnmap_num_gabs(struct sctp_tsnmap
*map
)
393 struct sctp_tsnmap_iter iter
;
396 /* Refresh the gap ack information. */
397 if (sctp_tsnmap_has_gap(map
)) {
398 sctp_tsnmap_iter_init(map
, &iter
);
399 while (sctp_tsnmap_next_gap_ack(map
, &iter
,
400 &map
->gabs
[gabs
].start
,
401 &map
->gabs
[gabs
].end
)) {
403 map
->gabs
[gabs
].start
= htons(map
->gabs
[gabs
].start
);
404 map
->gabs
[gabs
].end
= htons(map
->gabs
[gabs
].end
);
406 if (gabs
>= SCTP_MAX_GABS
)