Auto-update from upstream
[linux-2.6] / net / sctp / tsnmap.c
1 /* SCTP kernel reference 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.
6  *
7  * This file is part of the SCTP kernel reference Implementation
8  *
9  * These functions manipulate sctp tsn mapping array.
10  *
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)
15  * any later version.
16  *
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.
22  *
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.
27  *
28  * Please send any bug reports or fixes you make to the
29  * email address(es):
30  *    lksctp developers <lksctp-developers@lists.sourceforge.net>
31  *
32  * Or submit a bug report through the following website:
33  *    http://www.sf.net/projects/lksctp
34  *
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>
40  *
41  * Any bugs reported given to us we will try to fix... any fixes shared will
42  * be incorporated into the next SCTP release.
43  */
44
45 #include <linux/types.h>
46 #include <net/sctp/sctp.h>
47 #include <net/sctp/sm.h>
48
49 static void sctp_tsnmap_update(struct sctp_tsnmap *map);
50 static void sctp_tsnmap_find_gap_ack(__u8 *map, __u16 off,
51                                      __u16 len, __u16 base,
52                                      int *started, __u16 *start,
53                                      int *ended, __u16 *end);
54
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)
58 {
59         map->tsn_map = map->raw_map;
60         map->overflow_map = map->tsn_map + len;
61         map->len = len;
62
63         /* Clear out a TSN ack status.  */
64         memset(map->tsn_map, 0x00, map->len + map->len);
65
66         /* Keep track of TSNs represented by tsn_map.  */
67         map->base_tsn = initial_tsn;
68         map->overflow_tsn = initial_tsn + map->len;
69         map->cumulative_tsn_ack_point = initial_tsn - 1;
70         map->max_tsn_seen = map->cumulative_tsn_ack_point;
71         map->malloced = 0;
72         map->num_dup_tsns = 0;
73
74         return map;
75 }
76
77 /* Test the tracking state of this TSN.
78  * Returns:
79  *   0 if the TSN has not yet been seen
80  *  >0 if the TSN has been seen (duplicate)
81  *  <0 if the TSN is invalid (too large to track)
82  */
83 int sctp_tsnmap_check(const struct sctp_tsnmap *map, __u32 tsn)
84 {
85         __s32 gap;
86         int dup;
87
88         /* Calculate the index into the mapping arrays.  */
89         gap = tsn - map->base_tsn;
90
91         /* Verify that we can hold this TSN.  */
92         if (gap >= (/* base */ map->len + /* overflow */ map->len)) {
93                 dup = -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
108                 dup = 0;
109
110 out:
111         return dup;
112 }
113
114
115 /* Mark this TSN as seen.  */
116 void sctp_tsnmap_mark(struct sctp_tsnmap *map, __u32 tsn)
117 {
118         __s32 gap;
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))
124                 return;
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
132         /* Assert: TSN is in range.  */
133         gap = tsn - map->base_tsn;
134
135         /* Mark the TSN as received.  */
136         if (gap < map->len)
137                 map->tsn_map[gap]++;
138         else
139                 map->overflow_map[gap - map->len]++;
140
141         /* Go fixup any internal TSN mapping variables including
142          * cumulative_tsn_ack_point.
143          */
144         sctp_tsnmap_update(map);
145 }
146
147
148 /* Initialize a Gap Ack Block iterator from memory being provided.  */
149 SCTP_STATIC void sctp_tsnmap_iter_init(const struct sctp_tsnmap *map,
150                                        struct sctp_tsnmap_iter *iter)
151 {
152         /* Only start looking one past the Cumulative TSN Ack Point.  */
153         iter->start = map->cumulative_tsn_ack_point + 1;
154 }
155
156 /* Get the next Gap Ack Blocks. Returns 0 if there was not another block
157  * to get.
158  */
159 SCTP_STATIC int sctp_tsnmap_next_gap_ack(const struct sctp_tsnmap *map,
160                                          struct sctp_tsnmap_iter *iter,
161                                          __u16 *start, __u16 *end)
162 {
163         int started, ended;
164         __u16 _start, _end, offset;
165
166         /* We haven't found a gap yet.  */
167         started = ended = 0;
168
169         /* If there are no more gap acks possible, get out fast.  */
170         if (TSN_lte(map->max_tsn_seen, iter->start))
171                 return 0;
172
173         /* Search the first mapping array.  */
174         if (iter->start - map->base_tsn < map->len) {
175
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
200         /* The Gap Ack Block happens to end at the end of the
201          * overflow map.
202          */
203         if (started && !ended) {
204                 ended++;
205                 _end = map->len + map->len - 1;
206         }
207
208         /* If we found a Gap Ack Block, return the start and end and
209          * bump the iterator forward.
210          */
211         if (ended) {
212                 /* Fix up the start and end based on the
213                  * Cumulative TSN Ack offset into the map.
214                  */
215                 int gap = map->cumulative_tsn_ack_point -
216                         map->base_tsn;
217
218                 *start = _start - gap;
219                 *end = _end - gap;
220
221                 /* Move the iterator forward.  */
222                 iter->start = map->cumulative_tsn_ack_point + *end + 1;
223         }
224
225         return ended;
226 }
227
228 /* Mark this and any lower TSN as seen.  */
229 void sctp_tsnmap_skip(struct sctp_tsnmap *map, __u32 tsn)
230 {
231         __s32 gap;
232
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))
237                 return;
238         if (!TSN_lt(tsn, map->base_tsn + map->len + map->len))
239                 return;
240
241         /* Bump the max.  */
242         if (TSN_lt(map->max_tsn_seen, tsn))
243                 map->max_tsn_seen = tsn;
244
245         /* Assert: TSN is in range.  */
246         gap = tsn - map->base_tsn + 1;
247
248         /* Mark the TSNs as received.  */
249         if (gap <= map->len)
250                 memset(map->tsn_map, 0x01, gap);
251         else {
252                 memset(map->tsn_map, 0x01, map->len);
253                 memset(map->overflow_map, 0x01, (gap - map->len));
254         }
255
256         /* Go fixup any internal TSN mapping variables including
257          * cumulative_tsn_ack_point.
258          */
259         sctp_tsnmap_update(map);
260 }
261
262 /********************************************************************
263  * 2nd Level Abstractions
264  ********************************************************************/
265
266 /* This private helper function updates the tsnmap buffers and
267  * the Cumulative TSN Ack Point.
268  */
269 static void sctp_tsnmap_update(struct sctp_tsnmap *map)
270 {
271         __u32 ctsn;
272
273         ctsn = map->cumulative_tsn_ack_point;
274         do {
275                 ctsn++;
276                 if (ctsn == map->overflow_tsn) {
277                         /* Now tsn_map must have been all '1's,
278                          * so we swap the map and check the overflow table
279                          */
280                         __u8 *tmp = map->tsn_map;
281                         memset(tmp, 0, map->len);
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
291         map->cumulative_tsn_ack_point = ctsn - 1; /* Back up one. */
292 }
293
294 /* How many data chunks  are we missing from our peer?
295  */
296 __u16 sctp_tsnmap_pending(struct sctp_tsnmap *map)
297 {
298         __u32 cum_tsn = map->cumulative_tsn_ack_point;
299         __u32 max_tsn = map->max_tsn_seen;
300         __u32 base_tsn = map->base_tsn;
301         __u16 pending_data;
302         __s32 gap, start, end, i;
303
304         pending_data = max_tsn - cum_tsn;
305         gap = max_tsn - base_tsn;
306
307         if (gap <= 0 || gap >= (map->len + map->len))
308                 goto out;
309
310         start = ((cum_tsn >= base_tsn) ? (cum_tsn - base_tsn + 1) : 0);
311         end = ((gap > map->len ) ? map->len : gap + 1);
312
313         for (i = start; i < end; i++) {
314                 if (map->tsn_map[i])
315                         pending_data--;
316         }
317
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
327 out:
328         return pending_data;
329 }
330
331 /* This is a private helper for finding Gap Ack Blocks.  It searches a
332  * single array for the start and end of a Gap Ack Block.
333  *
334  * The flags "started" and "ended" tell is if we found the beginning
335  * or (respectively) the end of a Gap Ack Block.
336  */
337 static void sctp_tsnmap_find_gap_ack(__u8 *map, __u16 off,
338                                      __u16 len, __u16 base,
339                                      int *started, __u16 *start,
340                                      int *ended, __u16 *end)
341 {
342         int i = off;
343
344         /* Look through the entire array, but break out
345          * early if we have found the end of the Gap Ack Block.
346          */
347
348         /* Also, stop looking past the maximum TSN seen. */
349
350         /* Look for the start. */
351         if (!(*started)) {
352                 for (; i < len; i++) {
353                         if (map[i]) {
354                                 (*started)++;
355                                 *start = base + i;
356                                 break;
357                         }
358                 }
359         }
360
361         /* Look for the end.  */
362         if (*started) {
363                 /* We have found the start, let's find the
364                  * end.  If we find the end, break out.
365                  */
366                 for (; i < len; i++) {
367                         if (!map[i]) {
368                                 (*ended)++;
369                                 *end = base + i - 1;
370                                 break;
371                         }
372                 }
373         }
374 }
375
376 /* Renege that we have seen a TSN.  */
377 void sctp_tsnmap_renege(struct sctp_tsnmap *map, __u32 tsn)
378 {
379         __s32 gap;
380
381         if (TSN_lt(tsn, map->base_tsn))
382                 return;
383         if (!TSN_lt(tsn, map->base_tsn + map->len + map->len))
384                 return;
385
386         /* Assert: TSN is in range.  */
387         gap = tsn - map->base_tsn;
388
389         /* Pretend we never saw the TSN.  */
390         if (gap < map->len)
391                 map->tsn_map[gap] = 0;
392         else
393                 map->overflow_map[gap - map->len] = 0;
394 }
395
396 /* How many gap ack blocks do we have recorded? */
397 __u16 sctp_tsnmap_num_gabs(struct sctp_tsnmap *map)
398 {
399         struct sctp_tsnmap_iter iter;
400         int gabs = 0;
401
402         /* Refresh the gap ack information. */
403         if (sctp_tsnmap_has_gap(map)) {
404                 sctp_tsnmap_iter_init(map, &iter);
405                 while (sctp_tsnmap_next_gap_ack(map, &iter,
406                                                 &map->gabs[gabs].start,
407                                                 &map->gabs[gabs].end)) {
408
409                         map->gabs[gabs].start = htons(map->gabs[gabs].start);
410                         map->gabs[gabs].end = htons(map->gabs[gabs].end);
411                         gabs++;
412                         if (gabs >= SCTP_MAX_GABS)
413                                 break;
414                 }
415         }
416         return gabs;
417 }