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{
 119        u16 gap;
 120
 121        if (TSN_lt(tsn, map->base_tsn))
 122                return 0;
 123
 124        gap = tsn - map->base_tsn;
 125
 126        if (gap >= map->len && !sctp_tsnmap_grow(map, gap))
 127                return -ENOMEM;
 128
 129        if (!sctp_tsnmap_has_gap(map) && gap == 0) {
 130                /* In this case the map has no gaps and the tsn we are
 131                 * recording is the next expected tsn.  We don't touch
 132                 * the map but simply bump the values.
 133                 */
 134                map->max_tsn_seen++;
 135                map->cumulative_tsn_ack_point++;
 136                map->base_tsn++;
 137        } else {
 138                /* Either we already have a gap, or about to record a gap, so
 139                 * have work to do.
 140                 *
 141                 * Bump the max.
 142                 */
 143                if (TSN_lt(map->max_tsn_seen, tsn))
 144                        map->max_tsn_seen = tsn;
 145
 146                /* Mark the TSN as received.  */
 147                set_bit(gap, map->tsn_map);
 148
 149                /* Go fixup any internal TSN mapping variables including
 150                 * cumulative_tsn_ack_point.
 151                 */
 152                sctp_tsnmap_update(map);
 153        }
 154
 155        return 0;
 156}
 157
 158
 159/* Initialize a Gap Ack Block iterator from memory being provided.  */
 160SCTP_STATIC void sctp_tsnmap_iter_init(const struct sctp_tsnmap *map,
 161                                       struct sctp_tsnmap_iter *iter)
 162{
 163        /* Only start looking one past the Cumulative TSN Ack Point.  */
 164        iter->start = map->cumulative_tsn_ack_point + 1;
 165}
 166
 167/* Get the next Gap Ack Blocks. Returns 0 if there was not another block
 168 * to get.
 169 */
 170SCTP_STATIC int sctp_tsnmap_next_gap_ack(const struct sctp_tsnmap *map,
 171                                         struct sctp_tsnmap_iter *iter,
 172                                         __u16 *start, __u16 *end)
 173{
 174        int ended = 0;
 175        __u16 start_ = 0, end_ = 0, offset;
 176
 177        /* If there are no more gap acks possible, get out fast.  */
 178        if (TSN_lte(map->max_tsn_seen, iter->start))
 179                return 0;
 180
 181        offset = iter->start - map->base_tsn;
 182        sctp_tsnmap_find_gap_ack(map->tsn_map, offset, map->len,
 183                                 &start_, &end_);
 184
 185        /* The Gap Ack Block happens to end at the end of the map. */
 186        if (start_ && !end_)
 187                end_ = map->len - 1;
 188
 189        /* If we found a Gap Ack Block, return the start and end and
 190         * bump the iterator forward.
 191         */
 192        if (end_) {
 193                /* Fix up the start and end based on the
 194                 * Cumulative TSN Ack which is always 1 behind base.
 195                 */
 196                *start = start_ + 1;
 197                *end = end_ + 1;
 198
 199                /* Move the iterator forward.  */
 200                iter->start = map->cumulative_tsn_ack_point + *end + 1;
 201                ended = 1;
 202        }
 203
 204        return ended;
 205}
 206
 207/* Mark this and any lower TSN as seen.  */
 208void sctp_tsnmap_skip(struct sctp_tsnmap *map, __u32 tsn)
 209{
 210        u32 gap;
 211
 212        if (TSN_lt(tsn, map->base_tsn))
 213                return;
 214        if (!TSN_lt(tsn, map->base_tsn + SCTP_TSN_MAP_SIZE))
 215                return;
 216
 217        /* Bump the max.  */
 218        if (TSN_lt(map->max_tsn_seen, tsn))
 219                map->max_tsn_seen = tsn;
 220
 221        gap = tsn - map->base_tsn + 1;
 222
 223        map->base_tsn += gap;
 224        map->cumulative_tsn_ack_point += gap;
 225        if (gap >= map->len) {
 226                /* If our gap is larger then the map size, just
 227                 * zero out the map.
 228                 */
 229                bitmap_zero(map->tsn_map, map->len);
 230        } else {
 231                /* If the gap is smaller than the map size,
 232                 * shift the map by 'gap' bits and update further.
 233                 */
 234                bitmap_shift_right(map->tsn_map, map->tsn_map, gap, map->len);
 235                sctp_tsnmap_update(map);
 236        }
 237}
 238
 239/********************************************************************
 240 * 2nd Level Abstractions
 241 ********************************************************************/
 242
 243/* This private helper function updates the tsnmap buffers and
 244 * the Cumulative TSN Ack Point.
 245 */
 246static void sctp_tsnmap_update(struct sctp_tsnmap *map)
 247{
 248        u16 len;
 249        unsigned long zero_bit;
 250
 251
 252        len = map->max_tsn_seen - map->cumulative_tsn_ack_point;
 253        zero_bit = find_first_zero_bit(map->tsn_map, len);
 254        if (!zero_bit)
 255                return;         /* The first 0-bit is bit 0.  nothing to do */
 256
 257        map->base_tsn += zero_bit;
 258        map->cumulative_tsn_ack_point += zero_bit;
 259
 260        bitmap_shift_right(map->tsn_map, map->tsn_map, zero_bit, map->len);
 261}
 262
 263/* How many data chunks  are we missing from our peer?
 264 */
 265__u16 sctp_tsnmap_pending(struct sctp_tsnmap *map)
 266{
 267        __u32 cum_tsn = map->cumulative_tsn_ack_point;
 268        __u32 max_tsn = map->max_tsn_seen;
 269        __u32 base_tsn = map->base_tsn;
 270        __u16 pending_data;
 271        u32 gap, i;
 272
 273        pending_data = max_tsn - cum_tsn;
 274        gap = max_tsn - base_tsn;
 275
 276        if (gap == 0 || gap >= map->len)
 277                goto out;
 278
 279        for (i = 0; i < gap+1; i++) {
 280                if (test_bit(i, map->tsn_map))
 281                        pending_data--;
 282        }
 283
 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, end;
 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