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. 6 * 7 * This file is part of the SCTP kernel implementation 8 * 9 * These functions manipulate sctp tsn mapping array. 10 * 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) 15 * any later version. 16 * 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. 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 <linux-sctp@vger.kernel.org> 31 * 32 * Written or modified by: 33 * La Monte H.P. Yarroll <piggy@acm.org> 34 * Jon Grimm <jgrimm@us.ibm.com> 35 * Karl Knutson <karl@athena.chicago.il.us> 36 * Sridhar Samudrala <sri@us.ibm.com> 37 */ 38 39 #include <linux/slab.h> 40 #include <linux/types.h> 41 #include <linux/bitmap.h> 42 #include <net/sctp/sctp.h> 43 #include <net/sctp/sm.h> 44 45 static void sctp_tsnmap_update(struct sctp_tsnmap *map); 46 static void sctp_tsnmap_find_gap_ack(unsigned long *map, __u16 off, 47 __u16 len, __u16 *start, __u16 *end); 48 static int sctp_tsnmap_grow(struct sctp_tsnmap *map, u16 size); 49 50 /* Initialize a block of memory as a tsnmap. */ 51 struct sctp_tsnmap *sctp_tsnmap_init(struct sctp_tsnmap *map, __u16 len, 52 __u32 initial_tsn, gfp_t gfp) 53 { 54 if (!map->tsn_map) { 55 map->tsn_map = kzalloc(len>>3, gfp); 56 if (map->tsn_map == NULL) 57 return NULL; 58 59 map->len = len; 60 } else { 61 bitmap_zero(map->tsn_map, map->len); 62 } 63 64 /* Keep track of TSNs represented by tsn_map. */ 65 map->base_tsn = initial_tsn; 66 map->cumulative_tsn_ack_point = initial_tsn - 1; 67 map->max_tsn_seen = map->cumulative_tsn_ack_point; 68 map->num_dup_tsns = 0; 69 70 return map; 71 } 72 73 void sctp_tsnmap_free(struct sctp_tsnmap *map) 74 { 75 map->len = 0; 76 kfree(map->tsn_map); 77 } 78 79 /* Test the tracking state of this TSN. 80 * Returns: 81 * 0 if the TSN has not yet been seen 82 * >0 if the TSN has been seen (duplicate) 83 * <0 if the TSN is invalid (too large to track) 84 */ 85 int sctp_tsnmap_check(const struct sctp_tsnmap *map, __u32 tsn) 86 { 87 u32 gap; 88 89 /* Check to see if this is an old TSN */ 90 if (TSN_lte(tsn, map->cumulative_tsn_ack_point)) 91 return 1; 92 93 /* Verify that we can hold this TSN and that it will not 94 * overlfow our map 95 */ 96 if (!TSN_lt(tsn, map->base_tsn + SCTP_TSN_MAP_SIZE)) 97 return -1; 98 99 /* Calculate the index into the mapping arrays. */ 100 gap = tsn - map->base_tsn; 101 102 /* Check to see if TSN has already been recorded. */ 103 if (gap < map->len && test_bit(gap, map->tsn_map)) 104 return 1; 105 else 106 return 0; 107 } 108 109 110 /* Mark this TSN as seen. */ 111 int sctp_tsnmap_mark(struct sctp_tsnmap *map, __u32 tsn, 112 struct sctp_transport *trans) 113 { 114 u16 gap; 115 116 if (TSN_lt(tsn, map->base_tsn)) 117 return 0; 118 119 gap = tsn - map->base_tsn; 120 121 if (gap >= map->len && !sctp_tsnmap_grow(map, gap + 1)) 122 return -ENOMEM; 123 124 if (!sctp_tsnmap_has_gap(map) && gap == 0) { 125 /* In this case the map has no gaps and the tsn we are 126 * recording is the next expected tsn. We don't touch 127 * the map but simply bump the values. 128 */ 129 map->max_tsn_seen++; 130 map->cumulative_tsn_ack_point++; 131 if (trans) 132 trans->sack_generation = 133 trans->asoc->peer.sack_generation; 134 map->base_tsn++; 135 } else { 136 /* Either we already have a gap, or about to record a gap, so 137 * have work to do. 138 * 139 * Bump the max. 140 */ 141 if (TSN_lt(map->max_tsn_seen, tsn)) 142 map->max_tsn_seen = tsn; 143 144 /* Mark the TSN as received. */ 145 set_bit(gap, map->tsn_map); 146 147 /* Go fixup any internal TSN mapping variables including 148 * cumulative_tsn_ack_point. 149 */ 150 sctp_tsnmap_update(map); 151 } 152 153 return 0; 154 } 155 156 157 /* Initialize a Gap Ack Block iterator from memory being provided. */ 158 static void sctp_tsnmap_iter_init(const struct sctp_tsnmap *map, 159 struct sctp_tsnmap_iter *iter) 160 { 161 /* Only start looking one past the Cumulative TSN Ack Point. */ 162 iter->start = map->cumulative_tsn_ack_point + 1; 163 } 164 165 /* Get the next Gap Ack Blocks. Returns 0 if there was not another block 166 * to get. 167 */ 168 static int sctp_tsnmap_next_gap_ack(const struct sctp_tsnmap *map, 169 struct sctp_tsnmap_iter *iter, 170 __u16 *start, __u16 *end) 171 { 172 int ended = 0; 173 __u16 start_ = 0, end_ = 0, offset; 174 175 /* If there are no more gap acks possible, get out fast. */ 176 if (TSN_lte(map->max_tsn_seen, iter->start)) 177 return 0; 178 179 offset = iter->start - map->base_tsn; 180 sctp_tsnmap_find_gap_ack(map->tsn_map, offset, map->len, 181 &start_, &end_); 182 183 /* The Gap Ack Block happens to end at the end of the map. */ 184 if (start_ && !end_) 185 end_ = map->len - 1; 186 187 /* If we found a Gap Ack Block, return the start and end and 188 * bump the iterator forward. 189 */ 190 if (end_) { 191 /* Fix up the start and end based on the 192 * Cumulative TSN Ack which is always 1 behind base. 193 */ 194 *start = start_ + 1; 195 *end = end_ + 1; 196 197 /* Move the iterator forward. */ 198 iter->start = map->cumulative_tsn_ack_point + *end + 1; 199 ended = 1; 200 } 201 202 return ended; 203 } 204 205 /* Mark this and any lower TSN as seen. */ 206 void sctp_tsnmap_skip(struct sctp_tsnmap *map, __u32 tsn) 207 { 208 u32 gap; 209 210 if (TSN_lt(tsn, map->base_tsn)) 211 return; 212 if (!TSN_lt(tsn, map->base_tsn + SCTP_TSN_MAP_SIZE)) 213 return; 214 215 /* Bump the max. */ 216 if (TSN_lt(map->max_tsn_seen, tsn)) 217 map->max_tsn_seen = tsn; 218 219 gap = tsn - map->base_tsn + 1; 220 221 map->base_tsn += gap; 222 map->cumulative_tsn_ack_point += gap; 223 if (gap >= map->len) { 224 /* If our gap is larger then the map size, just 225 * zero out the map. 226 */ 227 bitmap_zero(map->tsn_map, map->len); 228 } else { 229 /* If the gap is smaller than the map size, 230 * shift the map by 'gap' bits and update further. 231 */ 232 bitmap_shift_right(map->tsn_map, map->tsn_map, gap, map->len); 233 sctp_tsnmap_update(map); 234 } 235 } 236 237 /******************************************************************** 238 * 2nd Level Abstractions 239 ********************************************************************/ 240 241 /* This private helper function updates the tsnmap buffers and 242 * the Cumulative TSN Ack Point. 243 */ 244 static void sctp_tsnmap_update(struct sctp_tsnmap *map) 245 { 246 u16 len; 247 unsigned long zero_bit; 248 249 250 len = map->max_tsn_seen - map->cumulative_tsn_ack_point; 251 zero_bit = find_first_zero_bit(map->tsn_map, len); 252 if (!zero_bit) 253 return; /* The first 0-bit is bit 0. nothing to do */ 254 255 map->base_tsn += zero_bit; 256 map->cumulative_tsn_ack_point += zero_bit; 257 258 bitmap_shift_right(map->tsn_map, map->tsn_map, zero_bit, map->len); 259 } 260 261 /* How many data chunks are we missing from our peer? 262 */ 263 __u16 sctp_tsnmap_pending(struct sctp_tsnmap *map) 264 { 265 __u32 cum_tsn = map->cumulative_tsn_ack_point; 266 __u32 max_tsn = map->max_tsn_seen; 267 __u32 base_tsn = map->base_tsn; 268 __u16 pending_data; 269 u32 gap; 270 271 pending_data = max_tsn - cum_tsn; 272 gap = max_tsn - base_tsn; 273 274 if (gap == 0 || gap >= map->len) 275 goto out; 276 277 pending_data -= bitmap_weight(map->tsn_map, gap + 1); 278 out: 279 return pending_data; 280 } 281 282 /* This is a private helper for finding Gap Ack Blocks. It searches a 283 * single array for the start and end of a Gap Ack Block. 284 * 285 * The flags "started" and "ended" tell is if we found the beginning 286 * or (respectively) the end of a Gap Ack Block. 287 */ 288 static void sctp_tsnmap_find_gap_ack(unsigned long *map, __u16 off, 289 __u16 len, __u16 *start, __u16 *end) 290 { 291 int i = off; 292 293 /* Look through the entire array, but break out 294 * early if we have found the end of the Gap Ack Block. 295 */ 296 297 /* Also, stop looking past the maximum TSN seen. */ 298 299 /* Look for the start. */ 300 i = find_next_bit(map, len, off); 301 if (i < len) 302 *start = i; 303 304 /* Look for the end. */ 305 if (*start) { 306 /* We have found the start, let's find the 307 * end. If we find the end, break out. 308 */ 309 i = find_next_zero_bit(map, len, i); 310 if (i < len) 311 *end = i - 1; 312 } 313 } 314 315 /* Renege that we have seen a TSN. */ 316 void sctp_tsnmap_renege(struct sctp_tsnmap *map, __u32 tsn) 317 { 318 u32 gap; 319 320 if (TSN_lt(tsn, map->base_tsn)) 321 return; 322 /* Assert: TSN is in range. */ 323 if (!TSN_lt(tsn, map->base_tsn + map->len)) 324 return; 325 326 gap = tsn - map->base_tsn; 327 328 /* Pretend we never saw the TSN. */ 329 clear_bit(gap, map->tsn_map); 330 } 331 332 /* How many gap ack blocks do we have recorded? */ 333 __u16 sctp_tsnmap_num_gabs(struct sctp_tsnmap *map, 334 struct sctp_gap_ack_block *gabs) 335 { 336 struct sctp_tsnmap_iter iter; 337 int ngaps = 0; 338 339 /* Refresh the gap ack information. */ 340 if (sctp_tsnmap_has_gap(map)) { 341 __u16 start = 0, end = 0; 342 sctp_tsnmap_iter_init(map, &iter); 343 while (sctp_tsnmap_next_gap_ack(map, &iter, 344 &start, 345 &end)) { 346 347 gabs[ngaps].start = htons(start); 348 gabs[ngaps].end = htons(end); 349 ngaps++; 350 if (ngaps >= SCTP_MAX_GABS) 351 break; 352 } 353 } 354 return ngaps; 355 } 356 357 static int sctp_tsnmap_grow(struct sctp_tsnmap *map, u16 size) 358 { 359 unsigned long *new; 360 unsigned long inc; 361 u16 len; 362 363 if (size > SCTP_TSN_MAP_SIZE) 364 return 0; 365 366 inc = ALIGN((size - map->len), BITS_PER_LONG) + SCTP_TSN_MAP_INCREMENT; 367 len = min_t(u16, map->len + inc, SCTP_TSN_MAP_SIZE); 368 369 new = kzalloc(len>>3, GFP_ATOMIC); 370 if (!new) 371 return 0; 372 373 bitmap_copy(new, map->tsn_map, 374 map->max_tsn_seen - map->cumulative_tsn_ack_point); 375 kfree(map->tsn_map); 376 map->tsn_map = new; 377 map->len = len; 378 379 return 1; 380 } 381