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, see
25 * <http://www.gnu.org/licenses/>.
27 * Please send any bug reports or fixes you make to the
29 * lksctp developers <linux-sctp@vger.kernel.org>
31 * Written or modified by:
32 * La Monte H.P. Yarroll <piggy@acm.org>
33 * Jon Grimm <jgrimm@us.ibm.com>
34 * Karl Knutson <karl@athena.chicago.il.us>
35 * Sridhar Samudrala <sri@us.ibm.com>
38 #include <linux/slab.h>
39 #include <linux/types.h>
40 #include <linux/bitmap.h>
41 #include <net/sctp/sctp.h>
42 #include <net/sctp/sm.h>
44 static void sctp_tsnmap_update(struct sctp_tsnmap
*map
);
45 static void sctp_tsnmap_find_gap_ack(unsigned long *map
, __u16 off
,
46 __u16 len
, __u16
*start
, __u16
*end
);
47 static int sctp_tsnmap_grow(struct sctp_tsnmap
*map
, u16 size
);
49 /* Initialize a block of memory as a tsnmap. */
50 struct sctp_tsnmap
*sctp_tsnmap_init(struct sctp_tsnmap
*map
, __u16 len
,
51 __u32 initial_tsn
, gfp_t gfp
)
54 map
->tsn_map
= kzalloc(len
>>3, gfp
);
55 if (map
->tsn_map
== NULL
)
60 bitmap_zero(map
->tsn_map
, map
->len
);
63 /* Keep track of TSNs represented by tsn_map. */
64 map
->base_tsn
= initial_tsn
;
65 map
->cumulative_tsn_ack_point
= initial_tsn
- 1;
66 map
->max_tsn_seen
= map
->cumulative_tsn_ack_point
;
67 map
->num_dup_tsns
= 0;
72 void sctp_tsnmap_free(struct sctp_tsnmap
*map
)
78 /* Test the tracking state of this TSN.
80 * 0 if the TSN has not yet been seen
81 * >0 if the TSN has been seen (duplicate)
82 * <0 if the TSN is invalid (too large to track)
84 int sctp_tsnmap_check(const struct sctp_tsnmap
*map
, __u32 tsn
)
88 /* Check to see if this is an old TSN */
89 if (TSN_lte(tsn
, map
->cumulative_tsn_ack_point
))
92 /* Verify that we can hold this TSN and that it will not
95 if (!TSN_lt(tsn
, map
->base_tsn
+ SCTP_TSN_MAP_SIZE
))
98 /* Calculate the index into the mapping arrays. */
99 gap
= tsn
- map
->base_tsn
;
101 /* Check to see if TSN has already been recorded. */
102 if (gap
< map
->len
&& test_bit(gap
, map
->tsn_map
))
109 /* Mark this TSN as seen. */
110 int sctp_tsnmap_mark(struct sctp_tsnmap
*map
, __u32 tsn
,
111 struct sctp_transport
*trans
)
115 if (TSN_lt(tsn
, map
->base_tsn
))
118 gap
= tsn
- map
->base_tsn
;
120 if (gap
>= map
->len
&& !sctp_tsnmap_grow(map
, gap
+ 1))
123 if (!sctp_tsnmap_has_gap(map
) && gap
== 0) {
124 /* In this case the map has no gaps and the tsn we are
125 * recording is the next expected tsn. We don't touch
126 * the map but simply bump the values.
129 map
->cumulative_tsn_ack_point
++;
131 trans
->sack_generation
=
132 trans
->asoc
->peer
.sack_generation
;
135 /* Either we already have a gap, or about to record a gap, so
140 if (TSN_lt(map
->max_tsn_seen
, tsn
))
141 map
->max_tsn_seen
= tsn
;
143 /* Mark the TSN as received. */
144 set_bit(gap
, map
->tsn_map
);
146 /* Go fixup any internal TSN mapping variables including
147 * cumulative_tsn_ack_point.
149 sctp_tsnmap_update(map
);
156 /* Initialize a Gap Ack Block iterator from memory being provided. */
157 static void sctp_tsnmap_iter_init(const struct sctp_tsnmap
*map
,
158 struct sctp_tsnmap_iter
*iter
)
160 /* Only start looking one past the Cumulative TSN Ack Point. */
161 iter
->start
= map
->cumulative_tsn_ack_point
+ 1;
164 /* Get the next Gap Ack Blocks. Returns 0 if there was not another block
167 static int sctp_tsnmap_next_gap_ack(const struct sctp_tsnmap
*map
,
168 struct sctp_tsnmap_iter
*iter
,
169 __u16
*start
, __u16
*end
)
172 __u16 start_
= 0, end_
= 0, offset
;
174 /* If there are no more gap acks possible, get out fast. */
175 if (TSN_lte(map
->max_tsn_seen
, iter
->start
))
178 offset
= iter
->start
- map
->base_tsn
;
179 sctp_tsnmap_find_gap_ack(map
->tsn_map
, offset
, map
->len
,
182 /* The Gap Ack Block happens to end at the end of the map. */
186 /* If we found a Gap Ack Block, return the start and end and
187 * bump the iterator forward.
190 /* Fix up the start and end based on the
191 * Cumulative TSN Ack which is always 1 behind base.
196 /* Move the iterator forward. */
197 iter
->start
= map
->cumulative_tsn_ack_point
+ *end
+ 1;
204 /* Mark this and any lower TSN as seen. */
205 void sctp_tsnmap_skip(struct sctp_tsnmap
*map
, __u32 tsn
)
209 if (TSN_lt(tsn
, map
->base_tsn
))
211 if (!TSN_lt(tsn
, map
->base_tsn
+ SCTP_TSN_MAP_SIZE
))
215 if (TSN_lt(map
->max_tsn_seen
, tsn
))
216 map
->max_tsn_seen
= tsn
;
218 gap
= tsn
- map
->base_tsn
+ 1;
220 map
->base_tsn
+= gap
;
221 map
->cumulative_tsn_ack_point
+= gap
;
222 if (gap
>= map
->len
) {
223 /* If our gap is larger then the map size, just
226 bitmap_zero(map
->tsn_map
, map
->len
);
228 /* If the gap is smaller than the map size,
229 * shift the map by 'gap' bits and update further.
231 bitmap_shift_right(map
->tsn_map
, map
->tsn_map
, gap
, map
->len
);
232 sctp_tsnmap_update(map
);
236 /********************************************************************
237 * 2nd Level Abstractions
238 ********************************************************************/
240 /* This private helper function updates the tsnmap buffers and
241 * the Cumulative TSN Ack Point.
243 static void sctp_tsnmap_update(struct sctp_tsnmap
*map
)
246 unsigned long zero_bit
;
249 len
= map
->max_tsn_seen
- map
->cumulative_tsn_ack_point
;
250 zero_bit
= find_first_zero_bit(map
->tsn_map
, len
);
252 return; /* The first 0-bit is bit 0. nothing to do */
254 map
->base_tsn
+= zero_bit
;
255 map
->cumulative_tsn_ack_point
+= zero_bit
;
257 bitmap_shift_right(map
->tsn_map
, map
->tsn_map
, zero_bit
, map
->len
);
260 /* How many data chunks are we missing from our peer?
262 __u16
sctp_tsnmap_pending(struct sctp_tsnmap
*map
)
264 __u32 cum_tsn
= map
->cumulative_tsn_ack_point
;
265 __u32 max_tsn
= map
->max_tsn_seen
;
266 __u32 base_tsn
= map
->base_tsn
;
270 pending_data
= max_tsn
- cum_tsn
;
271 gap
= max_tsn
- base_tsn
;
273 if (gap
== 0 || gap
>= map
->len
)
276 pending_data
-= bitmap_weight(map
->tsn_map
, gap
+ 1);
281 /* This is a private helper for finding Gap Ack Blocks. It searches a
282 * single array for the start and end of a Gap Ack Block.
284 * The flags "started" and "ended" tell is if we found the beginning
285 * or (respectively) the end of a Gap Ack Block.
287 static void sctp_tsnmap_find_gap_ack(unsigned long *map
, __u16 off
,
288 __u16 len
, __u16
*start
, __u16
*end
)
292 /* Look through the entire array, but break out
293 * early if we have found the end of the Gap Ack Block.
296 /* Also, stop looking past the maximum TSN seen. */
298 /* Look for the start. */
299 i
= find_next_bit(map
, len
, off
);
303 /* Look for the end. */
305 /* We have found the start, let's find the
306 * end. If we find the end, break out.
308 i
= find_next_zero_bit(map
, len
, i
);
314 /* Renege that we have seen a TSN. */
315 void sctp_tsnmap_renege(struct sctp_tsnmap
*map
, __u32 tsn
)
319 if (TSN_lt(tsn
, map
->base_tsn
))
321 /* Assert: TSN is in range. */
322 if (!TSN_lt(tsn
, map
->base_tsn
+ map
->len
))
325 gap
= tsn
- map
->base_tsn
;
327 /* Pretend we never saw the TSN. */
328 clear_bit(gap
, map
->tsn_map
);
331 /* How many gap ack blocks do we have recorded? */
332 __u16
sctp_tsnmap_num_gabs(struct sctp_tsnmap
*map
,
333 struct sctp_gap_ack_block
*gabs
)
335 struct sctp_tsnmap_iter iter
;
338 /* Refresh the gap ack information. */
339 if (sctp_tsnmap_has_gap(map
)) {
340 __u16 start
= 0, end
= 0;
341 sctp_tsnmap_iter_init(map
, &iter
);
342 while (sctp_tsnmap_next_gap_ack(map
, &iter
,
346 gabs
[ngaps
].start
= htons(start
);
347 gabs
[ngaps
].end
= htons(end
);
349 if (ngaps
>= SCTP_MAX_GABS
)
356 static int sctp_tsnmap_grow(struct sctp_tsnmap
*map
, u16 size
)
362 if (size
> SCTP_TSN_MAP_SIZE
)
365 inc
= ALIGN((size
- map
->len
), BITS_PER_LONG
) + SCTP_TSN_MAP_INCREMENT
;
366 len
= min_t(u16
, map
->len
+ inc
, SCTP_TSN_MAP_SIZE
);
368 new = kzalloc(len
>>3, GFP_ATOMIC
);
372 bitmap_copy(new, map
->tsn_map
,
373 map
->max_tsn_seen
- map
->cumulative_tsn_ack_point
);
This page took 0.039255 seconds and 5 git commands to generate.