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, see 25 * <http://www.gnu.org/licenses/>. 26 * 27 * Please send any bug reports or fixes you make to the 28 * email address(es): 29 * lksctp developers <linux-sctp@vger.kernel.org> 30 * 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> 36 */ 37 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> 43 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); 48 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) 52 { 53 if (!map->tsn_map) { 54 map->tsn_map = kzalloc(len>>3, gfp); 55 if (map->tsn_map == NULL) 56 return NULL; 57 58 map->len = len; 59 } else { 60 bitmap_zero(map->tsn_map, map->len); 61 } 62 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; 68 69 return map; 70 } 71 72 void sctp_tsnmap_free(struct sctp_tsnmap *map) 73 { 74 map->len = 0; 75 kfree(map->tsn_map); 76 } 77 78 /* Test the tracking state of this TSN. 79 * Returns: 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) 83 */ 84 int sctp_tsnmap_check(const struct sctp_tsnmap *map, __u32 tsn) 85 { 86 u32 gap; 87 88 /* Check to see if this is an old TSN */ 89 if (TSN_lte(tsn, map->cumulative_tsn_ack_point)) 90 return 1; 91 92 /* Verify that we can hold this TSN and that it will not 93 * overlfow our map 94 */ 95 if (!TSN_lt(tsn, map->base_tsn + SCTP_TSN_MAP_SIZE)) 96 return -1; 97 98 /* Calculate the index into the mapping arrays. */ 99 gap = tsn - map->base_tsn; 100 101 /* Check to see if TSN has already been recorded. */ 102 if (gap < map->len && test_bit(gap, map->tsn_map)) 103 return 1; 104 else 105 return 0; 106 } 107 108 109 /* Mark this TSN as seen. */ 110 int sctp_tsnmap_mark(struct sctp_tsnmap *map, __u32 tsn, 111 struct sctp_transport *trans) 112 { 113 u16 gap; 114 115 if (TSN_lt(tsn, map->base_tsn)) 116 return 0; 117 118 gap = tsn - map->base_tsn; 119 120 if (gap >= map->len && !sctp_tsnmap_grow(map, gap + 1)) 121 return -ENOMEM; 122 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. 127 */ 128 map->max_tsn_seen++; 129 map->cumulative_tsn_ack_point++; 130 if (trans) 131 trans->sack_generation = 132 trans->asoc->peer.sack_generation; 133 map->base_tsn++; 134 } else { 135 /* Either we already have a gap, or about to record a gap, so 136 * have work to do. 137 * 138 * Bump the max. 139 */ 140 if (TSN_lt(map->max_tsn_seen, tsn)) 141 map->max_tsn_seen = tsn; 142 143 /* Mark the TSN as received. */ 144 set_bit(gap, map->tsn_map); 145 146 /* Go fixup any internal TSN mapping variables including 147 * cumulative_tsn_ack_point. 148 */ 149 sctp_tsnmap_update(map); 150 } 151 152 return 0; 153 } 154 155 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) 159 { 160 /* Only start looking one past the Cumulative TSN Ack Point. */ 161 iter->start = map->cumulative_tsn_ack_point + 1; 162 } 163 164 /* Get the next Gap Ack Blocks. Returns 0 if there was not another block 165 * to get. 166 */ 167 static int sctp_tsnmap_next_gap_ack(const struct sctp_tsnmap *map, 168 struct sctp_tsnmap_iter *iter, 169 __u16 *start, __u16 *end) 170 { 171 int ended = 0; 172 __u16 start_ = 0, end_ = 0, offset; 173 174 /* If there are no more gap acks possible, get out fast. */ 175 if (TSN_lte(map->max_tsn_seen, iter->start)) 176 return 0; 177 178 offset = iter->start - map->base_tsn; 179 sctp_tsnmap_find_gap_ack(map->tsn_map, offset, map->len, 180 &start_, &end_); 181 182 /* The Gap Ack Block happens to end at the end of the map. */ 183 if (start_ && !end_) 184 end_ = map->len - 1; 185 186 /* If we found a Gap Ack Block, return the start and end and 187 * bump the iterator forward. 188 */ 189 if (end_) { 190 /* Fix up the start and end based on the 191 * Cumulative TSN Ack which is always 1 behind base. 192 */ 193 *start = start_ + 1; 194 *end = end_ + 1; 195 196 /* Move the iterator forward. */ 197 iter->start = map->cumulative_tsn_ack_point + *end + 1; 198 ended = 1; 199 } 200 201 return ended; 202 } 203 204 /* Mark this and any lower TSN as seen. */ 205 void sctp_tsnmap_skip(struct sctp_tsnmap *map, __u32 tsn) 206 { 207 u32 gap; 208 209 if (TSN_lt(tsn, map->base_tsn)) 210 return; 211 if (!TSN_lt(tsn, map->base_tsn + SCTP_TSN_MAP_SIZE)) 212 return; 213 214 /* Bump the max. */ 215 if (TSN_lt(map->max_tsn_seen, tsn)) 216 map->max_tsn_seen = tsn; 217 218 gap = tsn - map->base_tsn + 1; 219 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 224 * zero out the map. 225 */ 226 bitmap_zero(map->tsn_map, map->len); 227 } else { 228 /* If the gap is smaller than the map size, 229 * shift the map by 'gap' bits and update further. 230 */ 231 bitmap_shift_right(map->tsn_map, map->tsn_map, gap, map->len); 232 sctp_tsnmap_update(map); 233 } 234 } 235 236 /******************************************************************** 237 * 2nd Level Abstractions 238 ********************************************************************/ 239 240 /* This private helper function updates the tsnmap buffers and 241 * the Cumulative TSN Ack Point. 242 */ 243 static void sctp_tsnmap_update(struct sctp_tsnmap *map) 244 { 245 u16 len; 246 unsigned long zero_bit; 247 248 249 len = map->max_tsn_seen - map->cumulative_tsn_ack_point; 250 zero_bit = find_first_zero_bit(map->tsn_map, len); 251 if (!zero_bit) 252 return; /* The first 0-bit is bit 0. nothing to do */ 253 254 map->base_tsn += zero_bit; 255 map->cumulative_tsn_ack_point += zero_bit; 256 257 bitmap_shift_right(map->tsn_map, map->tsn_map, zero_bit, map->len); 258 } 259 260 /* How many data chunks are we missing from our peer? 261 */ 262 __u16 sctp_tsnmap_pending(struct sctp_tsnmap *map) 263 { 264 __u32 cum_tsn = map->cumulative_tsn_ack_point; 265 __u32 max_tsn = map->max_tsn_seen; 266 __u32 base_tsn = map->base_tsn; 267 __u16 pending_data; 268 u32 gap; 269 270 pending_data = max_tsn - cum_tsn; 271 gap = max_tsn - base_tsn; 272 273 if (gap == 0 || gap >= map->len) 274 goto out; 275 276 pending_data -= bitmap_weight(map->tsn_map, gap + 1); 277 out: 278 return pending_data; 279 } 280 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. 283 * 284 * The flags "started" and "ended" tell is if we found the beginning 285 * or (respectively) the end of a Gap Ack Block. 286 */ 287 static void sctp_tsnmap_find_gap_ack(unsigned long *map, __u16 off, 288 __u16 len, __u16 *start, __u16 *end) 289 { 290 int i = off; 291 292 /* Look through the entire array, but break out 293 * early if we have found the end of the Gap Ack Block. 294 */ 295 296 /* Also, stop looking past the maximum TSN seen. */ 297 298 /* Look for the start. */ 299 i = find_next_bit(map, len, off); 300 if (i < len) 301 *start = i; 302 303 /* Look for the end. */ 304 if (*start) { 305 /* We have found the start, let's find the 306 * end. If we find the end, break out. 307 */ 308 i = find_next_zero_bit(map, len, i); 309 if (i < len) 310 *end = i - 1; 311 } 312 } 313 314 /* Renege that we have seen a TSN. */ 315 void sctp_tsnmap_renege(struct sctp_tsnmap *map, __u32 tsn) 316 { 317 u32 gap; 318 319 if (TSN_lt(tsn, map->base_tsn)) 320 return; 321 /* Assert: TSN is in range. */ 322 if (!TSN_lt(tsn, map->base_tsn + map->len)) 323 return; 324 325 gap = tsn - map->base_tsn; 326 327 /* Pretend we never saw the TSN. */ 328 clear_bit(gap, map->tsn_map); 329 } 330 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) 334 { 335 struct sctp_tsnmap_iter iter; 336 int ngaps = 0; 337 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, 343 &start, 344 &end)) { 345 346 gabs[ngaps].start = htons(start); 347 gabs[ngaps].end = htons(end); 348 ngaps++; 349 if (ngaps >= SCTP_MAX_GABS) 350 break; 351 } 352 } 353 return ngaps; 354 } 355 356 static int sctp_tsnmap_grow(struct sctp_tsnmap *map, u16 size) 357 { 358 unsigned long *new; 359 unsigned long inc; 360 u16 len; 361 362 if (size > SCTP_TSN_MAP_SIZE) 363 return 0; 364 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); 367 368 new = kzalloc(len>>3, GFP_ATOMIC); 369 if (!new) 370 return 0; 371 372 bitmap_copy(new, map->tsn_map, 373 map->max_tsn_seen - map->cumulative_tsn_ack_point); 374 kfree(map->tsn_map); 375 map->tsn_map = new; 376 map->len = len; 377 378 return 1; 379 } 380