net/sctp/tsnmap.c

0001 // SPDX-License-Identifier: GPL-2.0-or-later
0002 /* SCTP kernel implementation
0003  * (C) Copyright IBM Corp. 2001, 2004
0004  * Copyright (c) 1999-2000 Cisco, Inc.
0005  * Copyright (c) 1999-2001 Motorola, Inc.
0006  * Copyright (c) 2001 Intel Corp.
0007  *
0008  * This file is part of the SCTP kernel implementation
0009  *
0010  * These functions manipulate sctp tsn mapping array.
0011  *
0012  * Please send any bug reports or fixes you make to the
0013  * email address(es):
0014  *    lksctp developers <linux-sctp@vger.kernel.org>
0015  *
0016  * Written or modified by:
0017  *    La Monte H.P. Yarroll <piggy@acm.org>
0018  *    Jon Grimm             <jgrimm@us.ibm.com>
0019  *    Karl Knutson          <karl@athena.chicago.il.us>
0020  *    Sridhar Samudrala     <sri@us.ibm.com>
0021  */
0022
0023 #include <linux/slab.h>
0024 #include <linux/types.h>
0025 #include <linux/bitmap.h>
0026 #include <net/sctp/sctp.h>
0027 #include <net/sctp/sm.h>
0028
0029 static void sctp_tsnmap_update(struct sctp_tsnmap *map);
0030 static void sctp_tsnmap_find_gap_ack(unsigned long *map, __u16 off,
0031                      __u16 len, __u16 *start, __u16 *end);
0032 static int sctp_tsnmap_grow(struct sctp_tsnmap *map, u16 size);
0033
0034 /* Initialize a block of memory as a tsnmap.  */
0035 struct sctp_tsnmap *sctp_tsnmap_init(struct sctp_tsnmap *map, __u16 len,
0036                      __u32 initial_tsn, gfp_t gfp)
0037 {
0038     if (!map->tsn_map) {
0039         map->tsn_map = kzalloc(len>>3, gfp);
0040         if (map->tsn_map == NULL)
0041             return NULL;
0042
0043         map->len = len;
0044     } else {
0045         bitmap_zero(map->tsn_map, map->len);
0046     }
0047
0048     /* Keep track of TSNs represented by tsn_map.  */
0049     map->base_tsn = initial_tsn;
0050     map->cumulative_tsn_ack_point = initial_tsn - 1;
0051     map->max_tsn_seen = map->cumulative_tsn_ack_point;
0052     map->num_dup_tsns = 0;
0053
0054     return map;
0055 }
0056
0057 void sctp_tsnmap_free(struct sctp_tsnmap *map)
0058 {
0059     map->len = 0;
0060     kfree(map->tsn_map);
0061 }
0062
0063 /* Test the tracking state of this TSN.
0064  * Returns:
0065  *   0 if the TSN has not yet been seen
0066  *  >0 if the TSN has been seen (duplicate)
0067  *  <0 if the TSN is invalid (too large to track)
0068  */
0069 int sctp_tsnmap_check(const struct sctp_tsnmap *map, __u32 tsn)
0070 {
0071     u32 gap;
0072
0073     /* Check to see if this is an old TSN */
0074     if (TSN_lte(tsn, map->cumulative_tsn_ack_point))
0075         return 1;
0076
0077     /* Verify that we can hold this TSN and that it will not
0078      * overflow our map
0079      */
0080     if (!TSN_lt(tsn, map->base_tsn + SCTP_TSN_MAP_SIZE))
0081         return -1;
0082
0083     /* Calculate the index into the mapping arrays.  */
0084     gap = tsn - map->base_tsn;
0085
0086     /* Check to see if TSN has already been recorded.  */
0087     if (gap < map->len && test_bit(gap, map->tsn_map))
0088         return 1;
0089     else
0090         return 0;
0091 }
0092
0093
0094 /* Mark this TSN as seen.  */
0095 int sctp_tsnmap_mark(struct sctp_tsnmap *map, __u32 tsn,
0096              struct sctp_transport *trans)
0097 {
0098     u16 gap;
0099
0100     if (TSN_lt(tsn, map->base_tsn))
0101         return 0;
0102
0103     gap = tsn - map->base_tsn;
0104
0105     if (gap >= map->len && !sctp_tsnmap_grow(map, gap + 1))
0106         return -ENOMEM;
0107
0108     if (!sctp_tsnmap_has_gap(map) && gap == 0) {
0109         /* In this case the map has no gaps and the tsn we are
0110          * recording is the next expected tsn.  We don't touch
0111          * the map but simply bump the values.
0112          */
0113         map->max_tsn_seen++;
0114         map->cumulative_tsn_ack_point++;
0115         if (trans)
0116             trans->sack_generation =
0117                 trans->asoc->peer.sack_generation;
0118         map->base_tsn++;
0119     } else {
0120         /* Either we already have a gap, or about to record a gap, so
0121          * have work to do.
0122          *
0123          * Bump the max.
0124          */
0125         if (TSN_lt(map->max_tsn_seen, tsn))
0126             map->max_tsn_seen = tsn;
0127
0128         /* Mark the TSN as received.  */
0129         set_bit(gap, map->tsn_map);
0130
0131         /* Go fixup any internal TSN mapping variables including
0132          * cumulative_tsn_ack_point.
0133          */
0134         sctp_tsnmap_update(map);
0135     }
0136
0137     return 0;
0138 }
0139
0140
0141 /* Initialize a Gap Ack Block iterator from memory being provided.  */
0142 static void sctp_tsnmap_iter_init(const struct sctp_tsnmap *map,
0143                   struct sctp_tsnmap_iter *iter)
0144 {
0145     /* Only start looking one past the Cumulative TSN Ack Point.  */
0146     iter->start = map->cumulative_tsn_ack_point + 1;
0147 }
0148
0149 /* Get the next Gap Ack Blocks. Returns 0 if there was not another block
0150  * to get.
0151  */
0152 static int sctp_tsnmap_next_gap_ack(const struct sctp_tsnmap *map,
0153                     struct sctp_tsnmap_iter *iter,
0154                     __u16 *start, __u16 *end)
0155 {
0156     int ended = 0;
0157     __u16 start_ = 0, end_ = 0, offset;
0158
0159     /* If there are no more gap acks possible, get out fast.  */
0160     if (TSN_lte(map->max_tsn_seen, iter->start))
0161         return 0;
0162
0163     offset = iter->start - map->base_tsn;
0164     sctp_tsnmap_find_gap_ack(map->tsn_map, offset, map->len,
0165                  &start_, &end_);
0166
0167     /* The Gap Ack Block happens to end at the end of the map. */
0168     if (start_ && !end_)
0169         end_ = map->len - 1;
0170
0171     /* If we found a Gap Ack Block, return the start and end and
0172      * bump the iterator forward.
0173      */
0174     if (end_) {
0175         /* Fix up the start and end based on the
0176          * Cumulative TSN Ack which is always 1 behind base.
0177          */
0178         *start = start_ + 1;
0179         *end = end_ + 1;
0180
0181         /* Move the iterator forward.  */
0182         iter->start = map->cumulative_tsn_ack_point + *end + 1;
0183         ended = 1;
0184     }
0185
0186     return ended;
0187 }
0188
0189 /* Mark this and any lower TSN as seen.  */
0190 void sctp_tsnmap_skip(struct sctp_tsnmap *map, __u32 tsn)
0191 {
0192     u32 gap;
0193
0194     if (TSN_lt(tsn, map->base_tsn))
0195         return;
0196     if (!TSN_lt(tsn, map->base_tsn + SCTP_TSN_MAP_SIZE))
0197         return;
0198
0199     /* Bump the max.  */
0200     if (TSN_lt(map->max_tsn_seen, tsn))
0201         map->max_tsn_seen = tsn;
0202
0203     gap = tsn - map->base_tsn + 1;
0204
0205     map->base_tsn += gap;
0206     map->cumulative_tsn_ack_point += gap;
0207     if (gap >= map->len) {
0208         /* If our gap is larger then the map size, just
0209          * zero out the map.
0210          */
0211         bitmap_zero(map->tsn_map, map->len);
0212     } else {
0213         /* If the gap is smaller than the map size,
0214          * shift the map by 'gap' bits and update further.
0215          */
0216         bitmap_shift_right(map->tsn_map, map->tsn_map, gap, map->len);
0217         sctp_tsnmap_update(map);
0218     }
0219 }
0220
0221 /********************************************************************
0222  * 2nd Level Abstractions
0223  ********************************************************************/
0224
0225 /* This private helper function updates the tsnmap buffers and
0226  * the Cumulative TSN Ack Point.
0227  */
0228 static void sctp_tsnmap_update(struct sctp_tsnmap *map)
0229 {
0230     u16 len;
0231     unsigned long zero_bit;
0232
0233
0234     len = map->max_tsn_seen - map->cumulative_tsn_ack_point;
0235     zero_bit = find_first_zero_bit(map->tsn_map, len);
0236     if (!zero_bit)
0237         return;     /* The first 0-bit is bit 0.  nothing to do */
0238
0239     map->base_tsn += zero_bit;
0240     map->cumulative_tsn_ack_point += zero_bit;
0241
0242     bitmap_shift_right(map->tsn_map, map->tsn_map, zero_bit, map->len);
0243 }
0244
0245 /* How many data chunks  are we missing from our peer?
0246  */
0247 __u16 sctp_tsnmap_pending(struct sctp_tsnmap *map)
0248 {
0249     __u32 cum_tsn = map->cumulative_tsn_ack_point;
0250     __u32 max_tsn = map->max_tsn_seen;
0251     __u32 base_tsn = map->base_tsn;
0252     __u16 pending_data;
0253     u32 gap;
0254
0255     pending_data = max_tsn - cum_tsn;
0256     gap = max_tsn - base_tsn;
0257
0258     if (gap == 0 || gap >= map->len)
0259         goto out;
0260
0261     pending_data -= bitmap_weight(map->tsn_map, gap + 1);
0262 out:
0263     return pending_data;
0264 }
0265
0266 /* This is a private helper for finding Gap Ack Blocks.  It searches a
0267  * single array for the start and end of a Gap Ack Block.
0268  *
0269  * The flags "started" and "ended" tell is if we found the beginning
0270  * or (respectively) the end of a Gap Ack Block.
0271  */
0272 static void sctp_tsnmap_find_gap_ack(unsigned long *map, __u16 off,
0273                      __u16 len, __u16 *start, __u16 *end)
0274 {
0275     int i = off;
0276
0277     /* Look through the entire array, but break out
0278      * early if we have found the end of the Gap Ack Block.
0279      */
0280
0281     /* Also, stop looking past the maximum TSN seen. */
0282
0283     /* Look for the start. */
0284     i = find_next_bit(map, len, off);
0285     if (i < len)
0286         *start = i;
0287
0288     /* Look for the end.  */
0289     if (*start) {
0290         /* We have found the start, let's find the
0291          * end.  If we find the end, break out.
0292          */
0293         i = find_next_zero_bit(map, len, i);
0294         if (i < len)
0295             *end = i - 1;
0296     }
0297 }
0298
0299 /* Renege that we have seen a TSN.  */
0300 void sctp_tsnmap_renege(struct sctp_tsnmap *map, __u32 tsn)
0301 {
0302     u32 gap;
0303
0304     if (TSN_lt(tsn, map->base_tsn))
0305         return;
0306     /* Assert: TSN is in range.  */
0307     if (!TSN_lt(tsn, map->base_tsn + map->len))
0308         return;
0309
0310     gap = tsn - map->base_tsn;
0311
0312     /* Pretend we never saw the TSN.  */
0313     clear_bit(gap, map->tsn_map);
0314 }
0315
0316 /* How many gap ack blocks do we have recorded? */
0317 __u16 sctp_tsnmap_num_gabs(struct sctp_tsnmap *map,
0318                struct sctp_gap_ack_block *gabs)
0319 {
0320     struct sctp_tsnmap_iter iter;
0321     int ngaps = 0;
0322
0323     /* Refresh the gap ack information. */
0324     if (sctp_tsnmap_has_gap(map)) {
0325         __u16 start = 0, end = 0;
0326         sctp_tsnmap_iter_init(map, &iter);
0327         while (sctp_tsnmap_next_gap_ack(map, &iter,
0328                         &start,
0329                         &end)) {
0330
0331             gabs[ngaps].start = htons(start);
0332             gabs[ngaps].end = htons(end);
0333             ngaps++;
0334             if (ngaps >= SCTP_MAX_GABS)
0335                 break;
0336         }
0337     }
0338     return ngaps;
0339 }
0340
0341 static int sctp_tsnmap_grow(struct sctp_tsnmap *map, u16 size)
0342 {
0343     unsigned long *new;
0344     unsigned long inc;
0345     u16  len;
0346
0347     if (size > SCTP_TSN_MAP_SIZE)
0348         return 0;
0349
0350     inc = ALIGN((size - map->len), BITS_PER_LONG) + SCTP_TSN_MAP_INCREMENT;
0351     len = min_t(u16, map->len + inc, SCTP_TSN_MAP_SIZE);
0352
0353     new = kzalloc(len>>3, GFP_ATOMIC);
0354     if (!new)
0355         return 0;
0356
0357     bitmap_copy(new, map->tsn_map,
0358         map->max_tsn_seen - map->cumulative_tsn_ack_point);
0359     kfree(map->tsn_map);
0360     map->tsn_map = new;
0361     map->len = len;
0362
0363     return 1;
0364 }