Subversion Repositories or1k

/* SCTP kernel reference Implementation

 * Copyright (c) 1999-2000 Cisco, Inc.

 * Copyright (c) 1999-2001 Motorola, Inc.

 * Copyright (c) 2001-2003 International Business Machines, Corp.

 * Copyright (c) 2001 Intel Corp.

 *

 * This file is part of the SCTP kernel reference Implementation

 *

 * These functions manipulate sctp tsn mapping array.

 *

 * The SCTP reference implementation is free software;

 * you can redistribute it and/or modify it under the terms of

 * the GNU General Public License as published by

 * the Free Software Foundation; either version 2, or (at your option)

 * any later version.

 *

 * The SCTP reference implementation is distributed in the hope that it

 * will be useful, but WITHOUT ANY WARRANTY; without even the implied

 *                 ************************

 * warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.

 * See the GNU General Public License for more details.

 *

 * You should have received a copy of the GNU General Public License

 * along with GNU CC; see the file COPYING.  If not, write to

 * the Free Software Foundation, 59 Temple Place - Suite 330,

 * Boston, MA 02111-1307, USA.

 *

 * Please send any bug reports or fixes you make to the

 * email address(es):

 *    lksctp developers <lksctp-developers@lists.sourceforge.net>

 *

 * Or submit a bug report through the following website:

 *    http://www.sf.net/projects/lksctp

 *

 * Written or modified by:

 *    La Monte H.P. Yarroll <piggy@acm.org>

 *    Jon Grimm             <jgrimm@us.ibm.com>

 *    Karl Knutson          <karl@athena.chicago.il.us>

 *

 * Any bugs reported given to us we will try to fix... any fixes shared will

 * be incorporated into the next SCTP release.

 */

#include <linux/types.h>

#include <net/sctp/sctp.h>

#include <net/sctp/sm.h>

static void sctp_tsnmap_update(struct sctp_tsnmap *map);

static void sctp_tsnmap_find_gap_ack(__u8 *map, __u16 off,

                                     __u16 len, __u16 base,

                                     int *started, __u16 *start,

                                     int *ended, __u16 *end);

/* Create a new sctp_tsnmap.

 * Allocate room to store at least 'len' contiguous TSNs.

 */

struct sctp_tsnmap *sctp_tsnmap_new(__u16 len, __u32 initial_tsn, int gfp)

{

        struct sctp_tsnmap *retval;

        retval = kmalloc(sizeof(struct sctp_tsnmap) +

                         sctp_tsnmap_storage_size(len), gfp);

        if (!retval)

                goto fail;

        if (!sctp_tsnmap_init(retval, len, initial_tsn))

                goto fail_map;

        retval->malloced = 1;

        return retval;

fail_map:

        kfree(retval);

fail:

        return NULL;

}

/* Initialize a block of memory as a tsnmap.  */

struct sctp_tsnmap *sctp_tsnmap_init(struct sctp_tsnmap *map, __u16 len,

                                     __u32 initial_tsn)

{

        map->tsn_map = map->raw_map;

        map->overflow_map = map->tsn_map + len;

        map->len = len;

        /* Clear out a TSN ack status.  */

        memset(map->tsn_map, 0x00, map->len + map->len);

        /* Keep track of TSNs represented by tsn_map.  */

        map->base_tsn = initial_tsn;

        map->overflow_tsn = initial_tsn + map->len;

        map->cumulative_tsn_ack_point = initial_tsn - 1;

        map->max_tsn_seen = map->cumulative_tsn_ack_point;

        map->malloced = 0;

        map->num_dup_tsns = 0;

        return map;

}

/* Test the tracking state of this TSN.

 * Returns:

 *   0 if the TSN has not yet been seen

 *  >0 if the TSN has been seen (duplicate)

 *  <0 if the TSN is invalid (too large to track)

 */

int sctp_tsnmap_check(const struct sctp_tsnmap *map, __u32 tsn)

{

        __s32 gap;

        int dup;

        /* Calculate the index into the mapping arrays.  */

        gap = tsn - map->base_tsn;

        /* Verify that we can hold this TSN.  */

        if (gap >= (/* base */ map->len + /* overflow */ map->len)) {

                dup = -1;

                goto out;

        }

        /* Honk if we've already seen this TSN.

         * We have three cases:

         *      1. The TSN is ancient or belongs to a previous tsn_map.

         *      2. The TSN is already marked in the tsn_map.

         *      3. The TSN is already marked in the tsn_map_overflow.

         */

        if (gap < 0 ||

            (gap < map->len && map->tsn_map[gap]) ||

            (gap >= map->len && map->overflow_map[gap - map->len]))

                dup = 1;

        else

                dup = 0;

out:

        return dup;

}

/* Mark this TSN as seen.  */

void sctp_tsnmap_mark(struct sctp_tsnmap *map, __u32 tsn)

{

        __s32 gap;

        /* Vacuously mark any TSN which precedes the map base or

         * exceeds the end of the map.

         */

        if (TSN_lt(tsn, map->base_tsn))

                return;

        if (!TSN_lt(tsn, map->base_tsn + map->len + map->len))

                return;

        /* Bump the max.  */

        if (TSN_lt(map->max_tsn_seen, tsn))

                map->max_tsn_seen = tsn;

        /* Assert: TSN is in range.  */

        gap = tsn - map->base_tsn;

        /* Mark the TSN as received.  */

        if (gap < map->len)

                map->tsn_map[gap]++;

        else

                map->overflow_map[gap - map->len]++;

        /* Go fixup any internal TSN mapping variables including

         * cumulative_tsn_ack_point.

         */

        sctp_tsnmap_update(map);

}

/* Dispose of a tsnmap.  */

void sctp_tsnmap_free(struct sctp_tsnmap *map)

{

        if (map->malloced)

                kfree(map);

}

/* Initialize a Gap Ack Block iterator from memory being provided.  */

void sctp_tsnmap_iter_init(const struct sctp_tsnmap *map,

                           struct sctp_tsnmap_iter *iter)

{

        /* Only start looking one past the Cumulative TSN Ack Point.  */

        iter->start = map->cumulative_tsn_ack_point + 1;

}

/* Get the next Gap Ack Blocks. Returns 0 if there was not another block

 * to get.

 */

int sctp_tsnmap_next_gap_ack(const struct sctp_tsnmap *map,

        struct sctp_tsnmap_iter *iter, __u16 *start, __u16 *end)

{

        int started, ended;

        __u16 _start, _end, offset;

        /* We haven't found a gap yet.  */

        started = ended = 0;

        /* If there are no more gap acks possible, get out fast.  */

        if (TSN_lte(map->max_tsn_seen, iter->start))

                return 0;

        /* Search the first mapping array.  */

        if (iter->start - map->base_tsn < map->len) {

                offset = iter->start - map->base_tsn;

                sctp_tsnmap_find_gap_ack(map->tsn_map, offset, map->len, 0,

                                         &started, &_start, &ended, &_end);

        }

        /* Do we need to check the overflow map? */

        if (!ended) {

                /* Fix up where we'd like to start searching in the

                 * overflow map.

                 */

                if (iter->start - map->base_tsn < map->len)

                        offset = 0;

                else

                        offset = iter->start - map->base_tsn - map->len;

                /* Search the overflow map.  */

                sctp_tsnmap_find_gap_ack(map->overflow_map,

                                         offset,

                                         map->len,

                                         map->len,

                                         &started, &_start,

                                         &ended, &_end);

        }

        /* The Gap Ack Block happens to end at the end of the

         * overflow map.

         */

        if (started && !ended) {

                ended++;

                _end = map->len + map->len - 1;

        }

        /* If we found a Gap Ack Block, return the start and end and

         * bump the iterator forward.

         */

        if (ended) {

                /* Fix up the start and end based on the

                 * Cumulative TSN Ack offset into the map.

                 */

                int gap = map->cumulative_tsn_ack_point -

                        map->base_tsn;

                *start = _start - gap;

                *end = _end - gap;

                /* Move the iterator forward.  */

                iter->start = map->cumulative_tsn_ack_point + *end + 1;

        }

        return ended;

}

/********************************************************************

 * 2nd Level Abstractions

 ********************************************************************/

/* This private helper function updates the tsnmap buffers and

 * the Cumulative TSN Ack Point.

 */

static void sctp_tsnmap_update(struct sctp_tsnmap *map)

{

        __u32 ctsn;

        ctsn = map->cumulative_tsn_ack_point;

        do {

                ctsn++;

                if (ctsn == map->overflow_tsn) {

                        /* Now tsn_map must have been all '1's,

                         * so we swap the map and check the overflow table

                         */

                        __u8 *tmp = map->tsn_map;

                        memset(tmp, 0, map->len);

                        map->tsn_map = map->overflow_map;

                        map->overflow_map = tmp;

                        /* Update the tsn_map boundaries.  */

                        map->base_tsn += map->len;

                        map->overflow_tsn += map->len;

                }

        } while (map->tsn_map[ctsn - map->base_tsn]);

        map->cumulative_tsn_ack_point = ctsn - 1; /* Back up one. */

}

/* How many data chunks  are we missing from our peer?

 */

__u16 sctp_tsnmap_pending(struct sctp_tsnmap *map)

{

        __u32 cum_tsn = map->cumulative_tsn_ack_point;

        __u32 max_tsn = map->max_tsn_seen;

        __u32 base_tsn = map->base_tsn;

        __u16 pending_data;

        __s32 gap, start, end, i;

        pending_data = max_tsn - cum_tsn;

        gap = max_tsn - base_tsn;

        if (gap <= 0 || gap >= (map->len + map->len))

                goto out;

        start = ((cum_tsn >= base_tsn) ? (cum_tsn - base_tsn + 1) : 0);

        end = ((gap > map->len ) ? map->len : gap + 1);

        for (i = start; i < end; i++) {

                if (map->tsn_map[i])

                        pending_data--;

        }

        if (gap >= map->len) {

                start = 0;

                end = gap - map->len + 1;

                for (i = start; i < end; i++) {

                        if (map->overflow_map[i])

                                pending_data--;

                }

        }

out:

        return pending_data;

}

/* This is a private helper for finding Gap Ack Blocks.  It searches a

 * single array for the start and end of a Gap Ack Block.

 *

 * The flags "started" and "ended" tell is if we found the beginning

 * or (respectively) the end of a Gap Ack Block.

 */

static void sctp_tsnmap_find_gap_ack(__u8 *map, __u16 off,

                                     __u16 len, __u16 base,

                                     int *started, __u16 *start,

                                     int *ended, __u16 *end)

{

        int i = off;

        /* Look through the entire array, but break out

         * early if we have found the end of the Gap Ack Block.

         */

        /* Also, stop looking past the maximum TSN seen. */

        /* Look for the start. */

        if (!(*started)) {

                for (; i < len; i++) {

                        if (map[i]) {

                                (*started)++;

                                *start = base + i;

                                break;

                        }

                }

        }

        /* Look for the end.  */

        if (*started) {

                /* We have found the start, let's find the

                 * end.  If we find the end, break out.

                 */

                for (; i < len; i++) {

                        if (!map[i]) {

                                (*ended)++;

                                *end = base + i - 1;

                                break;

                        }

                }

        }

}

/* Renege that we have seen a TSN.  */

void sctp_tsnmap_renege(struct sctp_tsnmap *map, __u32 tsn)

{

        __s32 gap;

        if (TSN_lt(tsn, map->base_tsn))

                return;

        if (!TSN_lt(tsn, map->base_tsn + map->len + map->len))

                return;

        /* Assert: TSN is in range.  */

        gap = tsn - map->base_tsn;

        /* Pretend we never saw the TSN.  */

        if (gap < map->len)

                map->tsn_map[gap] = 0;

        else

                map->overflow_map[gap - map->len] = 0;

}

/* How many gap ack blocks do we have recorded? */

__u16 sctp_tsnmap_num_gabs(struct sctp_tsnmap *map)

{

        struct sctp_tsnmap_iter iter;

        int gabs = 0;

        /* Refresh the gap ack information. */

        if (sctp_tsnmap_has_gap(map)) {

                sctp_tsnmap_iter_init(map, &iter);

                while (sctp_tsnmap_next_gap_ack(map, &iter,

                                                &map->gabs[gabs].start,

                                                &map->gabs[gabs].end)) {

                        map->gabs[gabs].start = htons(map->gabs[gabs].start);

                        map->gabs[gabs].end = htons(map->gabs[gabs].end);

                        gabs++;

                        if (gabs >= SCTP_MAX_GABS)

                                break;

                }

        }

        return gabs;

}