tsnmap.c 9.76 KB
Newer Older
1
/* SCTP kernel implementation
Linus Torvalds's avatar
Linus Torvalds committed
2
3
4
5
6
 * (C) Copyright IBM Corp. 2001, 2004
 * Copyright (c) 1999-2000 Cisco, Inc.
 * Copyright (c) 1999-2001 Motorola, Inc.
 * Copyright (c) 2001 Intel Corp.
 *
7
 * This file is part of the SCTP kernel implementation
Linus Torvalds's avatar
Linus Torvalds committed
8
9
10
 *
 * These functions manipulate sctp tsn mapping array.
 *
11
 * This SCTP implementation is free software;
Linus Torvalds's avatar
Linus Torvalds committed
12
13
14
15
16
 * you can redistribute it and/or modify it under the terms of
 * the GNU General Public License as published by
 * the Free Software Foundation; either version 2, or (at your option)
 * any later version.
 *
17
 * This SCTP implementation is distributed in the hope that it
Linus Torvalds's avatar
Linus Torvalds committed
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
 * will be useful, but WITHOUT ANY WARRANTY; without even the implied
 *                 ************************
 * warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.
 * See the GNU General Public License for more details.
 *
 * You should have received a copy of the GNU General Public License
 * along with GNU CC; see the file COPYING.  If not, write to
 * the Free Software Foundation, 59 Temple Place - Suite 330,
 * Boston, MA 02111-1307, USA.
 *
 * Please send any bug reports or fixes you make to the
 * email address(es):
 *    lksctp developers <lksctp-developers@lists.sourceforge.net>
 *
 * Or submit a bug report through the following website:
 *    http://www.sf.net/projects/lksctp
 *
 * Written or modified by:
 *    La Monte H.P. Yarroll <piggy@acm.org>
 *    Jon Grimm             <jgrimm@us.ibm.com>
 *    Karl Knutson          <karl@athena.chicago.il.us>
 *    Sridhar Samudrala     <sri@us.ibm.com>
 *
 * Any bugs reported given to us we will try to fix... any fixes shared will
 * be incorporated into the next SCTP release.
 */

45
#include <linux/slab.h>
Linus Torvalds's avatar
Linus Torvalds committed
46
#include <linux/types.h>
47
#include <linux/bitmap.h>
Linus Torvalds's avatar
Linus Torvalds committed
48
49
50
51
#include <net/sctp/sctp.h>
#include <net/sctp/sm.h>

static void sctp_tsnmap_update(struct sctp_tsnmap *map);
52
53
static void sctp_tsnmap_find_gap_ack(unsigned long *map, __u16 off,
				     __u16 len, __u16 *start, __u16 *end);
54
static int sctp_tsnmap_grow(struct sctp_tsnmap *map, u16 size);
Linus Torvalds's avatar
Linus Torvalds committed
55
56
57

/* Initialize a block of memory as a tsnmap.  */
struct sctp_tsnmap *sctp_tsnmap_init(struct sctp_tsnmap *map, __u16 len,
58
				     __u32 initial_tsn, gfp_t gfp)
Linus Torvalds's avatar
Linus Torvalds committed
59
{
60
61
62
63
64
65
66
67
68
	if (!map->tsn_map) {
		map->tsn_map = kzalloc(len>>3, gfp);
		if (map->tsn_map == NULL)
			return NULL;

		map->len = len;
	} else {
		bitmap_zero(map->tsn_map, map->len);
	}
Linus Torvalds's avatar
Linus Torvalds committed
69
70
71
72
73
74
75
76
77
78

	/* Keep track of TSNs represented by tsn_map.  */
	map->base_tsn = initial_tsn;
	map->cumulative_tsn_ack_point = initial_tsn - 1;
	map->max_tsn_seen = map->cumulative_tsn_ack_point;
	map->num_dup_tsns = 0;

	return map;
}

79
80
81
82
83
84
void sctp_tsnmap_free(struct sctp_tsnmap *map)
{
	map->len = 0;
	kfree(map->tsn_map);
}

Linus Torvalds's avatar
Linus Torvalds committed
85
86
87
88
89
90
91
92
/* Test the tracking state of this TSN.
 * Returns:
 *   0 if the TSN has not yet been seen
 *  >0 if the TSN has been seen (duplicate)
 *  <0 if the TSN is invalid (too large to track)
 */
int sctp_tsnmap_check(const struct sctp_tsnmap *map, __u32 tsn)
{
93
94
95
96
97
98
99
100
101
102
103
	u32 gap;

	/* Check to see if this is an old TSN */
	if (TSN_lte(tsn, map->cumulative_tsn_ack_point))
		return 1;

	/* Verify that we can hold this TSN and that it will not
	 * overlfow our map
	 */
	if (!TSN_lt(tsn, map->base_tsn + SCTP_TSN_MAP_SIZE))
		return -1;
Linus Torvalds's avatar
Linus Torvalds committed
104
105
106
107

	/* Calculate the index into the mapping arrays.  */
	gap = tsn - map->base_tsn;

108
109
110
	/* Check to see if TSN has already been recorded.  */
	if (gap < map->len && test_bit(gap, map->tsn_map))
		return 1;
Linus Torvalds's avatar
Linus Torvalds committed
111
	else
112
		return 0;
Linus Torvalds's avatar
Linus Torvalds committed
113
114
115
116
}


/* Mark this TSN as seen.  */
117
118
int sctp_tsnmap_mark(struct sctp_tsnmap *map, __u32 tsn,
		     struct sctp_transport *trans)
Linus Torvalds's avatar
Linus Torvalds committed
119
{
120
	u16 gap;
Linus Torvalds's avatar
Linus Torvalds committed
121
122

	if (TSN_lt(tsn, map->base_tsn))
123
		return 0;
Linus Torvalds's avatar
Linus Torvalds committed
124
125
126

	gap = tsn - map->base_tsn;

127
	if (gap >= map->len && !sctp_tsnmap_grow(map, gap + 1))
128
		return -ENOMEM;
Linus Torvalds's avatar
Linus Torvalds committed
129

130
131
132
133
134
135
136
	if (!sctp_tsnmap_has_gap(map) && gap == 0) {
		/* In this case the map has no gaps and the tsn we are
		 * recording is the next expected tsn.  We don't touch
		 * the map but simply bump the values.
		 */
		map->max_tsn_seen++;
		map->cumulative_tsn_ack_point++;
137
138
139
		if (trans)
			trans->sack_generation =
				trans->asoc->peer.sack_generation;
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
		map->base_tsn++;
	} else {
		/* Either we already have a gap, or about to record a gap, so
		 * have work to do.
		 *
		 * Bump the max.
		 */
		if (TSN_lt(map->max_tsn_seen, tsn))
			map->max_tsn_seen = tsn;

		/* Mark the TSN as received.  */
		set_bit(gap, map->tsn_map);

		/* Go fixup any internal TSN mapping variables including
		 * cumulative_tsn_ack_point.
		 */
		sctp_tsnmap_update(map);
	}

	return 0;
Linus Torvalds's avatar
Linus Torvalds committed
160
161
162
163
}


/* Initialize a Gap Ack Block iterator from memory being provided.  */
164
165
static void sctp_tsnmap_iter_init(const struct sctp_tsnmap *map,
				  struct sctp_tsnmap_iter *iter)
Linus Torvalds's avatar
Linus Torvalds committed
166
167
168
169
170
171
172
173
{
	/* Only start looking one past the Cumulative TSN Ack Point.  */
	iter->start = map->cumulative_tsn_ack_point + 1;
}

/* Get the next Gap Ack Blocks. Returns 0 if there was not another block
 * to get.
 */
174
175
176
static int sctp_tsnmap_next_gap_ack(const struct sctp_tsnmap *map,
				    struct sctp_tsnmap_iter *iter,
				    __u16 *start, __u16 *end)
Linus Torvalds's avatar
Linus Torvalds committed
177
{
178
179
	int ended = 0;
	__u16 start_ = 0, end_ = 0, offset;
Linus Torvalds's avatar
Linus Torvalds committed
180
181
182
183
184

	/* If there are no more gap acks possible, get out fast.  */
	if (TSN_lte(map->max_tsn_seen, iter->start))
		return 0;

185
186
187
	offset = iter->start - map->base_tsn;
	sctp_tsnmap_find_gap_ack(map->tsn_map, offset, map->len,
				 &start_, &end_);
Linus Torvalds's avatar
Linus Torvalds committed
188

189
190
191
	/* The Gap Ack Block happens to end at the end of the map. */
	if (start_ && !end_)
		end_ = map->len - 1;
Linus Torvalds's avatar
Linus Torvalds committed
192
193
194
195

	/* If we found a Gap Ack Block, return the start and end and
	 * bump the iterator forward.
	 */
196
	if (end_) {
Linus Torvalds's avatar
Linus Torvalds committed
197
		/* Fix up the start and end based on the
198
		 * Cumulative TSN Ack which is always 1 behind base.
Linus Torvalds's avatar
Linus Torvalds committed
199
		 */
200
201
		*start = start_ + 1;
		*end = end_ + 1;
Linus Torvalds's avatar
Linus Torvalds committed
202
203
204

		/* Move the iterator forward.  */
		iter->start = map->cumulative_tsn_ack_point + *end + 1;
205
		ended = 1;
Linus Torvalds's avatar
Linus Torvalds committed
206
207
208
209
210
211
212
213
	}

	return ended;
}

/* Mark this and any lower TSN as seen.  */
void sctp_tsnmap_skip(struct sctp_tsnmap *map, __u32 tsn)
{
214
	u32 gap;
Linus Torvalds's avatar
Linus Torvalds committed
215
216
217

	if (TSN_lt(tsn, map->base_tsn))
		return;
218
	if (!TSN_lt(tsn, map->base_tsn + SCTP_TSN_MAP_SIZE))
Linus Torvalds's avatar
Linus Torvalds committed
219
220
221
222
223
224
225
226
		return;

	/* Bump the max.  */
	if (TSN_lt(map->max_tsn_seen, tsn))
		map->max_tsn_seen = tsn;

	gap = tsn - map->base_tsn + 1;

227
228
229
230
231
232
233
234
	map->base_tsn += gap;
	map->cumulative_tsn_ack_point += gap;
	if (gap >= map->len) {
		/* If our gap is larger then the map size, just
		 * zero out the map.
		 */
		bitmap_zero(map->tsn_map, map->len);
	} else {
235
		/* If the gap is smaller than the map size,
236
237
238
239
		 * shift the map by 'gap' bits and update further.
		 */
		bitmap_shift_right(map->tsn_map, map->tsn_map, gap, map->len);
		sctp_tsnmap_update(map);
Linus Torvalds's avatar
Linus Torvalds committed
240
241
242
243
244
245
246
247
248
249
250
251
	}
}

/********************************************************************
 * 2nd Level Abstractions
 ********************************************************************/

/* This private helper function updates the tsnmap buffers and
 * the Cumulative TSN Ack Point.
 */
static void sctp_tsnmap_update(struct sctp_tsnmap *map)
{
252
253
254
255
256
257
258
259
260
261
262
	u16 len;
	unsigned long zero_bit;


	len = map->max_tsn_seen - map->cumulative_tsn_ack_point;
	zero_bit = find_first_zero_bit(map->tsn_map, len);
	if (!zero_bit)
		return;		/* The first 0-bit is bit 0.  nothing to do */

	map->base_tsn += zero_bit;
	map->cumulative_tsn_ack_point += zero_bit;
Linus Torvalds's avatar
Linus Torvalds committed
263

264
	bitmap_shift_right(map->tsn_map, map->tsn_map, zero_bit, map->len);
Linus Torvalds's avatar
Linus Torvalds committed
265
266
267
268
269
270
271
272
273
274
}

/* How many data chunks  are we missing from our peer?
 */
__u16 sctp_tsnmap_pending(struct sctp_tsnmap *map)
{
	__u32 cum_tsn = map->cumulative_tsn_ack_point;
	__u32 max_tsn = map->max_tsn_seen;
	__u32 base_tsn = map->base_tsn;
	__u16 pending_data;
Akinobu Mita's avatar
Akinobu Mita committed
275
	u32 gap;
Linus Torvalds's avatar
Linus Torvalds committed
276
277
278
279

	pending_data = max_tsn - cum_tsn;
	gap = max_tsn - base_tsn;

280
	if (gap == 0 || gap >= map->len)
Linus Torvalds's avatar
Linus Torvalds committed
281
282
		goto out;

Akinobu Mita's avatar
Akinobu Mita committed
283
	pending_data -= bitmap_weight(map->tsn_map, gap + 1);
Linus Torvalds's avatar
Linus Torvalds committed
284
285
286
287
288
289
290
291
292
293
out:
	return pending_data;
}

/* This is a private helper for finding Gap Ack Blocks.  It searches a
 * single array for the start and end of a Gap Ack Block.
 *
 * The flags "started" and "ended" tell is if we found the beginning
 * or (respectively) the end of a Gap Ack Block.
 */
294
295
static void sctp_tsnmap_find_gap_ack(unsigned long *map, __u16 off,
				     __u16 len, __u16 *start, __u16 *end)
Linus Torvalds's avatar
Linus Torvalds committed
296
297
298
299
300
301
302
303
304
305
{
	int i = off;

	/* Look through the entire array, but break out
	 * early if we have found the end of the Gap Ack Block.
	 */

	/* Also, stop looking past the maximum TSN seen. */

	/* Look for the start. */
306
307
308
	i = find_next_bit(map, len, off);
	if (i < len)
		*start = i;
Linus Torvalds's avatar
Linus Torvalds committed
309
310

	/* Look for the end.  */
311
	if (*start) {
Linus Torvalds's avatar
Linus Torvalds committed
312
313
314
		/* We have found the start, let's find the
		 * end.  If we find the end, break out.
		 */
315
316
317
		i = find_next_zero_bit(map, len, i);
		if (i < len)
			*end = i - 1;
Linus Torvalds's avatar
Linus Torvalds committed
318
319
320
321
322
323
	}
}

/* Renege that we have seen a TSN.  */
void sctp_tsnmap_renege(struct sctp_tsnmap *map, __u32 tsn)
{
324
	u32 gap;
Linus Torvalds's avatar
Linus Torvalds committed
325
326
327

	if (TSN_lt(tsn, map->base_tsn))
		return;
328
329
	/* Assert: TSN is in range.  */
	if (!TSN_lt(tsn, map->base_tsn + map->len))
Linus Torvalds's avatar
Linus Torvalds committed
330
331
332
333
334
		return;

	gap = tsn - map->base_tsn;

	/* Pretend we never saw the TSN.  */
335
	clear_bit(gap, map->tsn_map);
Linus Torvalds's avatar
Linus Torvalds committed
336
337
338
}

/* How many gap ack blocks do we have recorded? */
339
340
__u16 sctp_tsnmap_num_gabs(struct sctp_tsnmap *map,
			   struct sctp_gap_ack_block *gabs)
Linus Torvalds's avatar
Linus Torvalds committed
341
342
{
	struct sctp_tsnmap_iter iter;
343
	int ngaps = 0;
Linus Torvalds's avatar
Linus Torvalds committed
344
345
346

	/* Refresh the gap ack information. */
	if (sctp_tsnmap_has_gap(map)) {
347
		__u16 start = 0, end = 0;
Linus Torvalds's avatar
Linus Torvalds committed
348
349
		sctp_tsnmap_iter_init(map, &iter);
		while (sctp_tsnmap_next_gap_ack(map, &iter,
350
351
						&start,
						&end)) {
Linus Torvalds's avatar
Linus Torvalds committed
352

353
354
355
356
			gabs[ngaps].start = htons(start);
			gabs[ngaps].end = htons(end);
			ngaps++;
			if (ngaps >= SCTP_MAX_GABS)
Linus Torvalds's avatar
Linus Torvalds committed
357
358
359
				break;
		}
	}
360
	return ngaps;
Linus Torvalds's avatar
Linus Torvalds committed
361
}
362

363
static int sctp_tsnmap_grow(struct sctp_tsnmap *map, u16 size)
364
365
366
367
368
{
	unsigned long *new;
	unsigned long inc;
	u16  len;

369
	if (size > SCTP_TSN_MAP_SIZE)
370
371
		return 0;

372
	inc = ALIGN((size - map->len), BITS_PER_LONG) + SCTP_TSN_MAP_INCREMENT;
373
374
375
376
377
378
	len = min_t(u16, map->len + inc, SCTP_TSN_MAP_SIZE);

	new = kzalloc(len>>3, GFP_ATOMIC);
	if (!new)
		return 0;

379
380
	bitmap_copy(new, map->tsn_map,
		map->max_tsn_seen - map->cumulative_tsn_ack_point);
381
382
383
384
385
386
	kfree(map->tsn_map);
	map->tsn_map = new;
	map->len = len;

	return 1;
}