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