160c778b25972e095df8981dd41e99d161e8738f9Vlad Yasevich/* SCTP kernel implementation 21da177e4c3f41524e886b7f1b8a0c1fc7321cacLinus Torvalds * (C) Copyright IBM Corp. 2001, 2004 31da177e4c3f41524e886b7f1b8a0c1fc7321cacLinus Torvalds * Copyright (c) 1999-2000 Cisco, Inc. 41da177e4c3f41524e886b7f1b8a0c1fc7321cacLinus Torvalds * Copyright (c) 1999-2001 Motorola, Inc. 51da177e4c3f41524e886b7f1b8a0c1fc7321cacLinus Torvalds * Copyright (c) 2001 Intel Corp. 61da177e4c3f41524e886b7f1b8a0c1fc7321cacLinus Torvalds * 760c778b25972e095df8981dd41e99d161e8738f9Vlad Yasevich * This file is part of the SCTP kernel implementation 81da177e4c3f41524e886b7f1b8a0c1fc7321cacLinus Torvalds * 91da177e4c3f41524e886b7f1b8a0c1fc7321cacLinus Torvalds * These functions manipulate sctp tsn mapping array. 101da177e4c3f41524e886b7f1b8a0c1fc7321cacLinus Torvalds * 1160c778b25972e095df8981dd41e99d161e8738f9Vlad Yasevich * This SCTP implementation is free software; 121da177e4c3f41524e886b7f1b8a0c1fc7321cacLinus Torvalds * you can redistribute it and/or modify it under the terms of 131da177e4c3f41524e886b7f1b8a0c1fc7321cacLinus Torvalds * the GNU General Public License as published by 141da177e4c3f41524e886b7f1b8a0c1fc7321cacLinus Torvalds * the Free Software Foundation; either version 2, or (at your option) 151da177e4c3f41524e886b7f1b8a0c1fc7321cacLinus Torvalds * any later version. 161da177e4c3f41524e886b7f1b8a0c1fc7321cacLinus Torvalds * 1760c778b25972e095df8981dd41e99d161e8738f9Vlad Yasevich * This SCTP implementation is distributed in the hope that it 181da177e4c3f41524e886b7f1b8a0c1fc7321cacLinus Torvalds * will be useful, but WITHOUT ANY WARRANTY; without even the implied 191da177e4c3f41524e886b7f1b8a0c1fc7321cacLinus Torvalds * ************************ 201da177e4c3f41524e886b7f1b8a0c1fc7321cacLinus Torvalds * warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. 211da177e4c3f41524e886b7f1b8a0c1fc7321cacLinus Torvalds * See the GNU General Public License for more details. 221da177e4c3f41524e886b7f1b8a0c1fc7321cacLinus Torvalds * 231da177e4c3f41524e886b7f1b8a0c1fc7321cacLinus Torvalds * You should have received a copy of the GNU General Public License 244b2f13a25133b115eb56771bd4a8e71a82aea968Jeff Kirsher * along with GNU CC; see the file COPYING. If not, see 254b2f13a25133b115eb56771bd4a8e71a82aea968Jeff Kirsher * <http://www.gnu.org/licenses/>. 261da177e4c3f41524e886b7f1b8a0c1fc7321cacLinus Torvalds * 271da177e4c3f41524e886b7f1b8a0c1fc7321cacLinus Torvalds * Please send any bug reports or fixes you make to the 281da177e4c3f41524e886b7f1b8a0c1fc7321cacLinus Torvalds * email address(es): 2991705c61b52029ab5da67a15a23eef08667bf40eDaniel Borkmann * lksctp developers <linux-sctp@vger.kernel.org> 301da177e4c3f41524e886b7f1b8a0c1fc7321cacLinus Torvalds * 311da177e4c3f41524e886b7f1b8a0c1fc7321cacLinus Torvalds * Written or modified by: 321da177e4c3f41524e886b7f1b8a0c1fc7321cacLinus Torvalds * La Monte H.P. Yarroll <piggy@acm.org> 331da177e4c3f41524e886b7f1b8a0c1fc7321cacLinus Torvalds * Jon Grimm <jgrimm@us.ibm.com> 341da177e4c3f41524e886b7f1b8a0c1fc7321cacLinus Torvalds * Karl Knutson <karl@athena.chicago.il.us> 351da177e4c3f41524e886b7f1b8a0c1fc7321cacLinus Torvalds * Sridhar Samudrala <sri@us.ibm.com> 361da177e4c3f41524e886b7f1b8a0c1fc7321cacLinus Torvalds */ 371da177e4c3f41524e886b7f1b8a0c1fc7321cacLinus Torvalds 385a0e3ad6af8660be21ca98a971cd00f331318c05Tejun Heo#include <linux/slab.h> 391da177e4c3f41524e886b7f1b8a0c1fc7321cacLinus Torvalds#include <linux/types.h> 408e1ee18c332e08bee9d8bd66e63cd564fbf17fc2Vlad Yasevich#include <linux/bitmap.h> 411da177e4c3f41524e886b7f1b8a0c1fc7321cacLinus Torvalds#include <net/sctp/sctp.h> 421da177e4c3f41524e886b7f1b8a0c1fc7321cacLinus Torvalds#include <net/sctp/sm.h> 431da177e4c3f41524e886b7f1b8a0c1fc7321cacLinus Torvalds 441da177e4c3f41524e886b7f1b8a0c1fc7321cacLinus Torvaldsstatic void sctp_tsnmap_update(struct sctp_tsnmap *map); 458e1ee18c332e08bee9d8bd66e63cd564fbf17fc2Vlad Yasevichstatic void sctp_tsnmap_find_gap_ack(unsigned long *map, __u16 off, 468e1ee18c332e08bee9d8bd66e63cd564fbf17fc2Vlad Yasevich __u16 len, __u16 *start, __u16 *end); 4770fc69bc5a54d9776ace7c99d46eb533f8fb6e89Lee A. Robertsstatic int sctp_tsnmap_grow(struct sctp_tsnmap *map, u16 size); 481da177e4c3f41524e886b7f1b8a0c1fc7321cacLinus Torvalds 491da177e4c3f41524e886b7f1b8a0c1fc7321cacLinus Torvalds/* Initialize a block of memory as a tsnmap. */ 501da177e4c3f41524e886b7f1b8a0c1fc7321cacLinus Torvaldsstruct sctp_tsnmap *sctp_tsnmap_init(struct sctp_tsnmap *map, __u16 len, 518e1ee18c332e08bee9d8bd66e63cd564fbf17fc2Vlad Yasevich __u32 initial_tsn, gfp_t gfp) 521da177e4c3f41524e886b7f1b8a0c1fc7321cacLinus Torvalds{ 538e1ee18c332e08bee9d8bd66e63cd564fbf17fc2Vlad Yasevich if (!map->tsn_map) { 548e1ee18c332e08bee9d8bd66e63cd564fbf17fc2Vlad Yasevich map->tsn_map = kzalloc(len>>3, gfp); 558e1ee18c332e08bee9d8bd66e63cd564fbf17fc2Vlad Yasevich if (map->tsn_map == NULL) 568e1ee18c332e08bee9d8bd66e63cd564fbf17fc2Vlad Yasevich return NULL; 578e1ee18c332e08bee9d8bd66e63cd564fbf17fc2Vlad Yasevich 588e1ee18c332e08bee9d8bd66e63cd564fbf17fc2Vlad Yasevich map->len = len; 598e1ee18c332e08bee9d8bd66e63cd564fbf17fc2Vlad Yasevich } else { 608e1ee18c332e08bee9d8bd66e63cd564fbf17fc2Vlad Yasevich bitmap_zero(map->tsn_map, map->len); 618e1ee18c332e08bee9d8bd66e63cd564fbf17fc2Vlad Yasevich } 621da177e4c3f41524e886b7f1b8a0c1fc7321cacLinus Torvalds 631da177e4c3f41524e886b7f1b8a0c1fc7321cacLinus Torvalds /* Keep track of TSNs represented by tsn_map. */ 641da177e4c3f41524e886b7f1b8a0c1fc7321cacLinus Torvalds map->base_tsn = initial_tsn; 651da177e4c3f41524e886b7f1b8a0c1fc7321cacLinus Torvalds map->cumulative_tsn_ack_point = initial_tsn - 1; 661da177e4c3f41524e886b7f1b8a0c1fc7321cacLinus Torvalds map->max_tsn_seen = map->cumulative_tsn_ack_point; 671da177e4c3f41524e886b7f1b8a0c1fc7321cacLinus Torvalds map->num_dup_tsns = 0; 681da177e4c3f41524e886b7f1b8a0c1fc7321cacLinus Torvalds 691da177e4c3f41524e886b7f1b8a0c1fc7321cacLinus Torvalds return map; 701da177e4c3f41524e886b7f1b8a0c1fc7321cacLinus Torvalds} 711da177e4c3f41524e886b7f1b8a0c1fc7321cacLinus Torvalds 728e1ee18c332e08bee9d8bd66e63cd564fbf17fc2Vlad Yasevichvoid sctp_tsnmap_free(struct sctp_tsnmap *map) 738e1ee18c332e08bee9d8bd66e63cd564fbf17fc2Vlad Yasevich{ 748e1ee18c332e08bee9d8bd66e63cd564fbf17fc2Vlad Yasevich map->len = 0; 758e1ee18c332e08bee9d8bd66e63cd564fbf17fc2Vlad Yasevich kfree(map->tsn_map); 768e1ee18c332e08bee9d8bd66e63cd564fbf17fc2Vlad Yasevich} 778e1ee18c332e08bee9d8bd66e63cd564fbf17fc2Vlad Yasevich 781da177e4c3f41524e886b7f1b8a0c1fc7321cacLinus Torvalds/* Test the tracking state of this TSN. 791da177e4c3f41524e886b7f1b8a0c1fc7321cacLinus Torvalds * Returns: 801da177e4c3f41524e886b7f1b8a0c1fc7321cacLinus Torvalds * 0 if the TSN has not yet been seen 811da177e4c3f41524e886b7f1b8a0c1fc7321cacLinus Torvalds * >0 if the TSN has been seen (duplicate) 821da177e4c3f41524e886b7f1b8a0c1fc7321cacLinus Torvalds * <0 if the TSN is invalid (too large to track) 831da177e4c3f41524e886b7f1b8a0c1fc7321cacLinus Torvalds */ 841da177e4c3f41524e886b7f1b8a0c1fc7321cacLinus Torvaldsint sctp_tsnmap_check(const struct sctp_tsnmap *map, __u32 tsn) 851da177e4c3f41524e886b7f1b8a0c1fc7321cacLinus Torvalds{ 868e1ee18c332e08bee9d8bd66e63cd564fbf17fc2Vlad Yasevich u32 gap; 878e1ee18c332e08bee9d8bd66e63cd564fbf17fc2Vlad Yasevich 888e1ee18c332e08bee9d8bd66e63cd564fbf17fc2Vlad Yasevich /* Check to see if this is an old TSN */ 898e1ee18c332e08bee9d8bd66e63cd564fbf17fc2Vlad Yasevich if (TSN_lte(tsn, map->cumulative_tsn_ack_point)) 908e1ee18c332e08bee9d8bd66e63cd564fbf17fc2Vlad Yasevich return 1; 918e1ee18c332e08bee9d8bd66e63cd564fbf17fc2Vlad Yasevich 928e1ee18c332e08bee9d8bd66e63cd564fbf17fc2Vlad Yasevich /* Verify that we can hold this TSN and that it will not 938e1ee18c332e08bee9d8bd66e63cd564fbf17fc2Vlad Yasevich * overlfow our map 948e1ee18c332e08bee9d8bd66e63cd564fbf17fc2Vlad Yasevich */ 958e1ee18c332e08bee9d8bd66e63cd564fbf17fc2Vlad Yasevich if (!TSN_lt(tsn, map->base_tsn + SCTP_TSN_MAP_SIZE)) 968e1ee18c332e08bee9d8bd66e63cd564fbf17fc2Vlad Yasevich return -1; 971da177e4c3f41524e886b7f1b8a0c1fc7321cacLinus Torvalds 981da177e4c3f41524e886b7f1b8a0c1fc7321cacLinus Torvalds /* Calculate the index into the mapping arrays. */ 991da177e4c3f41524e886b7f1b8a0c1fc7321cacLinus Torvalds gap = tsn - map->base_tsn; 1001da177e4c3f41524e886b7f1b8a0c1fc7321cacLinus Torvalds 1018e1ee18c332e08bee9d8bd66e63cd564fbf17fc2Vlad Yasevich /* Check to see if TSN has already been recorded. */ 1028e1ee18c332e08bee9d8bd66e63cd564fbf17fc2Vlad Yasevich if (gap < map->len && test_bit(gap, map->tsn_map)) 1038e1ee18c332e08bee9d8bd66e63cd564fbf17fc2Vlad Yasevich return 1; 1041da177e4c3f41524e886b7f1b8a0c1fc7321cacLinus Torvalds else 1058e1ee18c332e08bee9d8bd66e63cd564fbf17fc2Vlad Yasevich return 0; 1061da177e4c3f41524e886b7f1b8a0c1fc7321cacLinus Torvalds} 1071da177e4c3f41524e886b7f1b8a0c1fc7321cacLinus Torvalds 1081da177e4c3f41524e886b7f1b8a0c1fc7321cacLinus Torvalds 1091da177e4c3f41524e886b7f1b8a0c1fc7321cacLinus Torvalds/* Mark this TSN as seen. */ 1104244854d22bf8f782698c5224b9191c8d2d42610Neil Hormanint sctp_tsnmap_mark(struct sctp_tsnmap *map, __u32 tsn, 1114244854d22bf8f782698c5224b9191c8d2d42610Neil Horman struct sctp_transport *trans) 1121da177e4c3f41524e886b7f1b8a0c1fc7321cacLinus Torvalds{ 1138e1ee18c332e08bee9d8bd66e63cd564fbf17fc2Vlad Yasevich u16 gap; 1141da177e4c3f41524e886b7f1b8a0c1fc7321cacLinus Torvalds 1151da177e4c3f41524e886b7f1b8a0c1fc7321cacLinus Torvalds if (TSN_lt(tsn, map->base_tsn)) 1168e1ee18c332e08bee9d8bd66e63cd564fbf17fc2Vlad Yasevich return 0; 1171da177e4c3f41524e886b7f1b8a0c1fc7321cacLinus Torvalds 1181da177e4c3f41524e886b7f1b8a0c1fc7321cacLinus Torvalds gap = tsn - map->base_tsn; 1191da177e4c3f41524e886b7f1b8a0c1fc7321cacLinus Torvalds 12070fc69bc5a54d9776ace7c99d46eb533f8fb6e89Lee A. Roberts if (gap >= map->len && !sctp_tsnmap_grow(map, gap + 1)) 1218e1ee18c332e08bee9d8bd66e63cd564fbf17fc2Vlad Yasevich return -ENOMEM; 1221da177e4c3f41524e886b7f1b8a0c1fc7321cacLinus Torvalds 1238e1ee18c332e08bee9d8bd66e63cd564fbf17fc2Vlad Yasevich if (!sctp_tsnmap_has_gap(map) && gap == 0) { 1248e1ee18c332e08bee9d8bd66e63cd564fbf17fc2Vlad Yasevich /* In this case the map has no gaps and the tsn we are 1258e1ee18c332e08bee9d8bd66e63cd564fbf17fc2Vlad Yasevich * recording is the next expected tsn. We don't touch 1268e1ee18c332e08bee9d8bd66e63cd564fbf17fc2Vlad Yasevich * the map but simply bump the values. 1278e1ee18c332e08bee9d8bd66e63cd564fbf17fc2Vlad Yasevich */ 1288e1ee18c332e08bee9d8bd66e63cd564fbf17fc2Vlad Yasevich map->max_tsn_seen++; 1298e1ee18c332e08bee9d8bd66e63cd564fbf17fc2Vlad Yasevich map->cumulative_tsn_ack_point++; 1304244854d22bf8f782698c5224b9191c8d2d42610Neil Horman if (trans) 1314244854d22bf8f782698c5224b9191c8d2d42610Neil Horman trans->sack_generation = 1324244854d22bf8f782698c5224b9191c8d2d42610Neil Horman trans->asoc->peer.sack_generation; 1338e1ee18c332e08bee9d8bd66e63cd564fbf17fc2Vlad Yasevich map->base_tsn++; 1348e1ee18c332e08bee9d8bd66e63cd564fbf17fc2Vlad Yasevich } else { 1358e1ee18c332e08bee9d8bd66e63cd564fbf17fc2Vlad Yasevich /* Either we already have a gap, or about to record a gap, so 1368e1ee18c332e08bee9d8bd66e63cd564fbf17fc2Vlad Yasevich * have work to do. 1378e1ee18c332e08bee9d8bd66e63cd564fbf17fc2Vlad Yasevich * 1388e1ee18c332e08bee9d8bd66e63cd564fbf17fc2Vlad Yasevich * Bump the max. 1398e1ee18c332e08bee9d8bd66e63cd564fbf17fc2Vlad Yasevich */ 1408e1ee18c332e08bee9d8bd66e63cd564fbf17fc2Vlad Yasevich if (TSN_lt(map->max_tsn_seen, tsn)) 1418e1ee18c332e08bee9d8bd66e63cd564fbf17fc2Vlad Yasevich map->max_tsn_seen = tsn; 1428e1ee18c332e08bee9d8bd66e63cd564fbf17fc2Vlad Yasevich 1438e1ee18c332e08bee9d8bd66e63cd564fbf17fc2Vlad Yasevich /* Mark the TSN as received. */ 1448e1ee18c332e08bee9d8bd66e63cd564fbf17fc2Vlad Yasevich set_bit(gap, map->tsn_map); 1458e1ee18c332e08bee9d8bd66e63cd564fbf17fc2Vlad Yasevich 1468e1ee18c332e08bee9d8bd66e63cd564fbf17fc2Vlad Yasevich /* Go fixup any internal TSN mapping variables including 1478e1ee18c332e08bee9d8bd66e63cd564fbf17fc2Vlad Yasevich * cumulative_tsn_ack_point. 1488e1ee18c332e08bee9d8bd66e63cd564fbf17fc2Vlad Yasevich */ 1498e1ee18c332e08bee9d8bd66e63cd564fbf17fc2Vlad Yasevich sctp_tsnmap_update(map); 1508e1ee18c332e08bee9d8bd66e63cd564fbf17fc2Vlad Yasevich } 1518e1ee18c332e08bee9d8bd66e63cd564fbf17fc2Vlad Yasevich 1528e1ee18c332e08bee9d8bd66e63cd564fbf17fc2Vlad Yasevich return 0; 1531da177e4c3f41524e886b7f1b8a0c1fc7321cacLinus Torvalds} 1541da177e4c3f41524e886b7f1b8a0c1fc7321cacLinus Torvalds 1551da177e4c3f41524e886b7f1b8a0c1fc7321cacLinus Torvalds 1561da177e4c3f41524e886b7f1b8a0c1fc7321cacLinus Torvalds/* Initialize a Gap Ack Block iterator from memory being provided. */ 157dda9192851dcf904b4d1095480834f2a4f814ae3Daniel Borkmannstatic void sctp_tsnmap_iter_init(const struct sctp_tsnmap *map, 158dda9192851dcf904b4d1095480834f2a4f814ae3Daniel Borkmann struct sctp_tsnmap_iter *iter) 1591da177e4c3f41524e886b7f1b8a0c1fc7321cacLinus Torvalds{ 1601da177e4c3f41524e886b7f1b8a0c1fc7321cacLinus Torvalds /* Only start looking one past the Cumulative TSN Ack Point. */ 1611da177e4c3f41524e886b7f1b8a0c1fc7321cacLinus Torvalds iter->start = map->cumulative_tsn_ack_point + 1; 1621da177e4c3f41524e886b7f1b8a0c1fc7321cacLinus Torvalds} 1631da177e4c3f41524e886b7f1b8a0c1fc7321cacLinus Torvalds 1641da177e4c3f41524e886b7f1b8a0c1fc7321cacLinus Torvalds/* Get the next Gap Ack Blocks. Returns 0 if there was not another block 1651da177e4c3f41524e886b7f1b8a0c1fc7321cacLinus Torvalds * to get. 1661da177e4c3f41524e886b7f1b8a0c1fc7321cacLinus Torvalds */ 167dda9192851dcf904b4d1095480834f2a4f814ae3Daniel Borkmannstatic int sctp_tsnmap_next_gap_ack(const struct sctp_tsnmap *map, 168dda9192851dcf904b4d1095480834f2a4f814ae3Daniel Borkmann struct sctp_tsnmap_iter *iter, 169dda9192851dcf904b4d1095480834f2a4f814ae3Daniel Borkmann __u16 *start, __u16 *end) 1701da177e4c3f41524e886b7f1b8a0c1fc7321cacLinus Torvalds{ 1718e1ee18c332e08bee9d8bd66e63cd564fbf17fc2Vlad Yasevich int ended = 0; 1728e1ee18c332e08bee9d8bd66e63cd564fbf17fc2Vlad Yasevich __u16 start_ = 0, end_ = 0, offset; 1731da177e4c3f41524e886b7f1b8a0c1fc7321cacLinus Torvalds 1741da177e4c3f41524e886b7f1b8a0c1fc7321cacLinus Torvalds /* If there are no more gap acks possible, get out fast. */ 1751da177e4c3f41524e886b7f1b8a0c1fc7321cacLinus Torvalds if (TSN_lte(map->max_tsn_seen, iter->start)) 1761da177e4c3f41524e886b7f1b8a0c1fc7321cacLinus Torvalds return 0; 1771da177e4c3f41524e886b7f1b8a0c1fc7321cacLinus Torvalds 1788e1ee18c332e08bee9d8bd66e63cd564fbf17fc2Vlad Yasevich offset = iter->start - map->base_tsn; 1798e1ee18c332e08bee9d8bd66e63cd564fbf17fc2Vlad Yasevich sctp_tsnmap_find_gap_ack(map->tsn_map, offset, map->len, 1808e1ee18c332e08bee9d8bd66e63cd564fbf17fc2Vlad Yasevich &start_, &end_); 1811da177e4c3f41524e886b7f1b8a0c1fc7321cacLinus Torvalds 1828e1ee18c332e08bee9d8bd66e63cd564fbf17fc2Vlad Yasevich /* The Gap Ack Block happens to end at the end of the map. */ 1838e1ee18c332e08bee9d8bd66e63cd564fbf17fc2Vlad Yasevich if (start_ && !end_) 1848e1ee18c332e08bee9d8bd66e63cd564fbf17fc2Vlad Yasevich end_ = map->len - 1; 1851da177e4c3f41524e886b7f1b8a0c1fc7321cacLinus Torvalds 1861da177e4c3f41524e886b7f1b8a0c1fc7321cacLinus Torvalds /* If we found a Gap Ack Block, return the start and end and 1871da177e4c3f41524e886b7f1b8a0c1fc7321cacLinus Torvalds * bump the iterator forward. 1881da177e4c3f41524e886b7f1b8a0c1fc7321cacLinus Torvalds */ 1898e1ee18c332e08bee9d8bd66e63cd564fbf17fc2Vlad Yasevich if (end_) { 1901da177e4c3f41524e886b7f1b8a0c1fc7321cacLinus Torvalds /* Fix up the start and end based on the 1918e1ee18c332e08bee9d8bd66e63cd564fbf17fc2Vlad Yasevich * Cumulative TSN Ack which is always 1 behind base. 1921da177e4c3f41524e886b7f1b8a0c1fc7321cacLinus Torvalds */ 1938e1ee18c332e08bee9d8bd66e63cd564fbf17fc2Vlad Yasevich *start = start_ + 1; 1948e1ee18c332e08bee9d8bd66e63cd564fbf17fc2Vlad Yasevich *end = end_ + 1; 1951da177e4c3f41524e886b7f1b8a0c1fc7321cacLinus Torvalds 1961da177e4c3f41524e886b7f1b8a0c1fc7321cacLinus Torvalds /* Move the iterator forward. */ 1971da177e4c3f41524e886b7f1b8a0c1fc7321cacLinus Torvalds iter->start = map->cumulative_tsn_ack_point + *end + 1; 1988e1ee18c332e08bee9d8bd66e63cd564fbf17fc2Vlad Yasevich ended = 1; 1991da177e4c3f41524e886b7f1b8a0c1fc7321cacLinus Torvalds } 2001da177e4c3f41524e886b7f1b8a0c1fc7321cacLinus Torvalds 2011da177e4c3f41524e886b7f1b8a0c1fc7321cacLinus Torvalds return ended; 2021da177e4c3f41524e886b7f1b8a0c1fc7321cacLinus Torvalds} 2031da177e4c3f41524e886b7f1b8a0c1fc7321cacLinus Torvalds 2041da177e4c3f41524e886b7f1b8a0c1fc7321cacLinus Torvalds/* Mark this and any lower TSN as seen. */ 2051da177e4c3f41524e886b7f1b8a0c1fc7321cacLinus Torvaldsvoid sctp_tsnmap_skip(struct sctp_tsnmap *map, __u32 tsn) 2061da177e4c3f41524e886b7f1b8a0c1fc7321cacLinus Torvalds{ 2078e1ee18c332e08bee9d8bd66e63cd564fbf17fc2Vlad Yasevich u32 gap; 2081da177e4c3f41524e886b7f1b8a0c1fc7321cacLinus Torvalds 2091da177e4c3f41524e886b7f1b8a0c1fc7321cacLinus Torvalds if (TSN_lt(tsn, map->base_tsn)) 2101da177e4c3f41524e886b7f1b8a0c1fc7321cacLinus Torvalds return; 2118e1ee18c332e08bee9d8bd66e63cd564fbf17fc2Vlad Yasevich if (!TSN_lt(tsn, map->base_tsn + SCTP_TSN_MAP_SIZE)) 2121da177e4c3f41524e886b7f1b8a0c1fc7321cacLinus Torvalds return; 2131da177e4c3f41524e886b7f1b8a0c1fc7321cacLinus Torvalds 2141da177e4c3f41524e886b7f1b8a0c1fc7321cacLinus Torvalds /* Bump the max. */ 2151da177e4c3f41524e886b7f1b8a0c1fc7321cacLinus Torvalds if (TSN_lt(map->max_tsn_seen, tsn)) 2161da177e4c3f41524e886b7f1b8a0c1fc7321cacLinus Torvalds map->max_tsn_seen = tsn; 2171da177e4c3f41524e886b7f1b8a0c1fc7321cacLinus Torvalds 2181da177e4c3f41524e886b7f1b8a0c1fc7321cacLinus Torvalds gap = tsn - map->base_tsn + 1; 2191da177e4c3f41524e886b7f1b8a0c1fc7321cacLinus Torvalds 2208e1ee18c332e08bee9d8bd66e63cd564fbf17fc2Vlad Yasevich map->base_tsn += gap; 2218e1ee18c332e08bee9d8bd66e63cd564fbf17fc2Vlad Yasevich map->cumulative_tsn_ack_point += gap; 2228e1ee18c332e08bee9d8bd66e63cd564fbf17fc2Vlad Yasevich if (gap >= map->len) { 2238e1ee18c332e08bee9d8bd66e63cd564fbf17fc2Vlad Yasevich /* If our gap is larger then the map size, just 2248e1ee18c332e08bee9d8bd66e63cd564fbf17fc2Vlad Yasevich * zero out the map. 2258e1ee18c332e08bee9d8bd66e63cd564fbf17fc2Vlad Yasevich */ 2268e1ee18c332e08bee9d8bd66e63cd564fbf17fc2Vlad Yasevich bitmap_zero(map->tsn_map, map->len); 2278e1ee18c332e08bee9d8bd66e63cd564fbf17fc2Vlad Yasevich } else { 228025dfdafe77f20b3890981a394774baab7b9c827Frederik Schwarzer /* If the gap is smaller than the map size, 2298e1ee18c332e08bee9d8bd66e63cd564fbf17fc2Vlad Yasevich * shift the map by 'gap' bits and update further. 2308e1ee18c332e08bee9d8bd66e63cd564fbf17fc2Vlad Yasevich */ 2318e1ee18c332e08bee9d8bd66e63cd564fbf17fc2Vlad Yasevich bitmap_shift_right(map->tsn_map, map->tsn_map, gap, map->len); 2328e1ee18c332e08bee9d8bd66e63cd564fbf17fc2Vlad Yasevich sctp_tsnmap_update(map); 2331da177e4c3f41524e886b7f1b8a0c1fc7321cacLinus Torvalds } 2341da177e4c3f41524e886b7f1b8a0c1fc7321cacLinus Torvalds} 2351da177e4c3f41524e886b7f1b8a0c1fc7321cacLinus Torvalds 2361da177e4c3f41524e886b7f1b8a0c1fc7321cacLinus Torvalds/******************************************************************** 2371da177e4c3f41524e886b7f1b8a0c1fc7321cacLinus Torvalds * 2nd Level Abstractions 2381da177e4c3f41524e886b7f1b8a0c1fc7321cacLinus Torvalds ********************************************************************/ 2391da177e4c3f41524e886b7f1b8a0c1fc7321cacLinus Torvalds 2401da177e4c3f41524e886b7f1b8a0c1fc7321cacLinus Torvalds/* This private helper function updates the tsnmap buffers and 2411da177e4c3f41524e886b7f1b8a0c1fc7321cacLinus Torvalds * the Cumulative TSN Ack Point. 2421da177e4c3f41524e886b7f1b8a0c1fc7321cacLinus Torvalds */ 2431da177e4c3f41524e886b7f1b8a0c1fc7321cacLinus Torvaldsstatic void sctp_tsnmap_update(struct sctp_tsnmap *map) 2441da177e4c3f41524e886b7f1b8a0c1fc7321cacLinus Torvalds{ 2458e1ee18c332e08bee9d8bd66e63cd564fbf17fc2Vlad Yasevich u16 len; 2468e1ee18c332e08bee9d8bd66e63cd564fbf17fc2Vlad Yasevich unsigned long zero_bit; 2478e1ee18c332e08bee9d8bd66e63cd564fbf17fc2Vlad Yasevich 2488e1ee18c332e08bee9d8bd66e63cd564fbf17fc2Vlad Yasevich 2498e1ee18c332e08bee9d8bd66e63cd564fbf17fc2Vlad Yasevich len = map->max_tsn_seen - map->cumulative_tsn_ack_point; 2508e1ee18c332e08bee9d8bd66e63cd564fbf17fc2Vlad Yasevich zero_bit = find_first_zero_bit(map->tsn_map, len); 2518e1ee18c332e08bee9d8bd66e63cd564fbf17fc2Vlad Yasevich if (!zero_bit) 2528e1ee18c332e08bee9d8bd66e63cd564fbf17fc2Vlad Yasevich return; /* The first 0-bit is bit 0. nothing to do */ 2538e1ee18c332e08bee9d8bd66e63cd564fbf17fc2Vlad Yasevich 2548e1ee18c332e08bee9d8bd66e63cd564fbf17fc2Vlad Yasevich map->base_tsn += zero_bit; 2558e1ee18c332e08bee9d8bd66e63cd564fbf17fc2Vlad Yasevich map->cumulative_tsn_ack_point += zero_bit; 2561da177e4c3f41524e886b7f1b8a0c1fc7321cacLinus Torvalds 2578e1ee18c332e08bee9d8bd66e63cd564fbf17fc2Vlad Yasevich bitmap_shift_right(map->tsn_map, map->tsn_map, zero_bit, map->len); 2581da177e4c3f41524e886b7f1b8a0c1fc7321cacLinus Torvalds} 2591da177e4c3f41524e886b7f1b8a0c1fc7321cacLinus Torvalds 2601da177e4c3f41524e886b7f1b8a0c1fc7321cacLinus Torvalds/* How many data chunks are we missing from our peer? 2611da177e4c3f41524e886b7f1b8a0c1fc7321cacLinus Torvalds */ 2621da177e4c3f41524e886b7f1b8a0c1fc7321cacLinus Torvalds__u16 sctp_tsnmap_pending(struct sctp_tsnmap *map) 2631da177e4c3f41524e886b7f1b8a0c1fc7321cacLinus Torvalds{ 2641da177e4c3f41524e886b7f1b8a0c1fc7321cacLinus Torvalds __u32 cum_tsn = map->cumulative_tsn_ack_point; 2651da177e4c3f41524e886b7f1b8a0c1fc7321cacLinus Torvalds __u32 max_tsn = map->max_tsn_seen; 2661da177e4c3f41524e886b7f1b8a0c1fc7321cacLinus Torvalds __u32 base_tsn = map->base_tsn; 2671da177e4c3f41524e886b7f1b8a0c1fc7321cacLinus Torvalds __u16 pending_data; 268fc184f089220f7abd604993d7c69218603c2ffb2Akinobu Mita u32 gap; 2691da177e4c3f41524e886b7f1b8a0c1fc7321cacLinus Torvalds 2701da177e4c3f41524e886b7f1b8a0c1fc7321cacLinus Torvalds pending_data = max_tsn - cum_tsn; 2711da177e4c3f41524e886b7f1b8a0c1fc7321cacLinus Torvalds gap = max_tsn - base_tsn; 2721da177e4c3f41524e886b7f1b8a0c1fc7321cacLinus Torvalds 2738e1ee18c332e08bee9d8bd66e63cd564fbf17fc2Vlad Yasevich if (gap == 0 || gap >= map->len) 2741da177e4c3f41524e886b7f1b8a0c1fc7321cacLinus Torvalds goto out; 2751da177e4c3f41524e886b7f1b8a0c1fc7321cacLinus Torvalds 276fc184f089220f7abd604993d7c69218603c2ffb2Akinobu Mita pending_data -= bitmap_weight(map->tsn_map, gap + 1); 2771da177e4c3f41524e886b7f1b8a0c1fc7321cacLinus Torvaldsout: 2781da177e4c3f41524e886b7f1b8a0c1fc7321cacLinus Torvalds return pending_data; 2791da177e4c3f41524e886b7f1b8a0c1fc7321cacLinus Torvalds} 2801da177e4c3f41524e886b7f1b8a0c1fc7321cacLinus Torvalds 2811da177e4c3f41524e886b7f1b8a0c1fc7321cacLinus Torvalds/* This is a private helper for finding Gap Ack Blocks. It searches a 2821da177e4c3f41524e886b7f1b8a0c1fc7321cacLinus Torvalds * single array for the start and end of a Gap Ack Block. 2831da177e4c3f41524e886b7f1b8a0c1fc7321cacLinus Torvalds * 2841da177e4c3f41524e886b7f1b8a0c1fc7321cacLinus Torvalds * The flags "started" and "ended" tell is if we found the beginning 2851da177e4c3f41524e886b7f1b8a0c1fc7321cacLinus Torvalds * or (respectively) the end of a Gap Ack Block. 2861da177e4c3f41524e886b7f1b8a0c1fc7321cacLinus Torvalds */ 2878e1ee18c332e08bee9d8bd66e63cd564fbf17fc2Vlad Yasevichstatic void sctp_tsnmap_find_gap_ack(unsigned long *map, __u16 off, 2888e1ee18c332e08bee9d8bd66e63cd564fbf17fc2Vlad Yasevich __u16 len, __u16 *start, __u16 *end) 2891da177e4c3f41524e886b7f1b8a0c1fc7321cacLinus Torvalds{ 2901da177e4c3f41524e886b7f1b8a0c1fc7321cacLinus Torvalds int i = off; 2911da177e4c3f41524e886b7f1b8a0c1fc7321cacLinus Torvalds 2921da177e4c3f41524e886b7f1b8a0c1fc7321cacLinus Torvalds /* Look through the entire array, but break out 2931da177e4c3f41524e886b7f1b8a0c1fc7321cacLinus Torvalds * early if we have found the end of the Gap Ack Block. 2941da177e4c3f41524e886b7f1b8a0c1fc7321cacLinus Torvalds */ 2951da177e4c3f41524e886b7f1b8a0c1fc7321cacLinus Torvalds 2961da177e4c3f41524e886b7f1b8a0c1fc7321cacLinus Torvalds /* Also, stop looking past the maximum TSN seen. */ 2971da177e4c3f41524e886b7f1b8a0c1fc7321cacLinus Torvalds 2981da177e4c3f41524e886b7f1b8a0c1fc7321cacLinus Torvalds /* Look for the start. */ 2998e1ee18c332e08bee9d8bd66e63cd564fbf17fc2Vlad Yasevich i = find_next_bit(map, len, off); 3008e1ee18c332e08bee9d8bd66e63cd564fbf17fc2Vlad Yasevich if (i < len) 3018e1ee18c332e08bee9d8bd66e63cd564fbf17fc2Vlad Yasevich *start = i; 3021da177e4c3f41524e886b7f1b8a0c1fc7321cacLinus Torvalds 3031da177e4c3f41524e886b7f1b8a0c1fc7321cacLinus Torvalds /* Look for the end. */ 3048e1ee18c332e08bee9d8bd66e63cd564fbf17fc2Vlad Yasevich if (*start) { 3051da177e4c3f41524e886b7f1b8a0c1fc7321cacLinus Torvalds /* We have found the start, let's find the 3061da177e4c3f41524e886b7f1b8a0c1fc7321cacLinus Torvalds * end. If we find the end, break out. 3071da177e4c3f41524e886b7f1b8a0c1fc7321cacLinus Torvalds */ 3088e1ee18c332e08bee9d8bd66e63cd564fbf17fc2Vlad Yasevich i = find_next_zero_bit(map, len, i); 3098e1ee18c332e08bee9d8bd66e63cd564fbf17fc2Vlad Yasevich if (i < len) 3108e1ee18c332e08bee9d8bd66e63cd564fbf17fc2Vlad Yasevich *end = i - 1; 3111da177e4c3f41524e886b7f1b8a0c1fc7321cacLinus Torvalds } 3121da177e4c3f41524e886b7f1b8a0c1fc7321cacLinus Torvalds} 3131da177e4c3f41524e886b7f1b8a0c1fc7321cacLinus Torvalds 3141da177e4c3f41524e886b7f1b8a0c1fc7321cacLinus Torvalds/* Renege that we have seen a TSN. */ 3151da177e4c3f41524e886b7f1b8a0c1fc7321cacLinus Torvaldsvoid sctp_tsnmap_renege(struct sctp_tsnmap *map, __u32 tsn) 3161da177e4c3f41524e886b7f1b8a0c1fc7321cacLinus Torvalds{ 3178e1ee18c332e08bee9d8bd66e63cd564fbf17fc2Vlad Yasevich u32 gap; 3181da177e4c3f41524e886b7f1b8a0c1fc7321cacLinus Torvalds 3191da177e4c3f41524e886b7f1b8a0c1fc7321cacLinus Torvalds if (TSN_lt(tsn, map->base_tsn)) 3201da177e4c3f41524e886b7f1b8a0c1fc7321cacLinus Torvalds return; 3218e1ee18c332e08bee9d8bd66e63cd564fbf17fc2Vlad Yasevich /* Assert: TSN is in range. */ 3228e1ee18c332e08bee9d8bd66e63cd564fbf17fc2Vlad Yasevich if (!TSN_lt(tsn, map->base_tsn + map->len)) 3231da177e4c3f41524e886b7f1b8a0c1fc7321cacLinus Torvalds return; 3241da177e4c3f41524e886b7f1b8a0c1fc7321cacLinus Torvalds 3251da177e4c3f41524e886b7f1b8a0c1fc7321cacLinus Torvalds gap = tsn - map->base_tsn; 3261da177e4c3f41524e886b7f1b8a0c1fc7321cacLinus Torvalds 3271da177e4c3f41524e886b7f1b8a0c1fc7321cacLinus Torvalds /* Pretend we never saw the TSN. */ 3288e1ee18c332e08bee9d8bd66e63cd564fbf17fc2Vlad Yasevich clear_bit(gap, map->tsn_map); 3291da177e4c3f41524e886b7f1b8a0c1fc7321cacLinus Torvalds} 3301da177e4c3f41524e886b7f1b8a0c1fc7321cacLinus Torvalds 3311da177e4c3f41524e886b7f1b8a0c1fc7321cacLinus Torvalds/* How many gap ack blocks do we have recorded? */ 33202015180e2509afd2e3fe3790a333b30708a116bVlad Yasevich__u16 sctp_tsnmap_num_gabs(struct sctp_tsnmap *map, 33302015180e2509afd2e3fe3790a333b30708a116bVlad Yasevich struct sctp_gap_ack_block *gabs) 3341da177e4c3f41524e886b7f1b8a0c1fc7321cacLinus Torvalds{ 3351da177e4c3f41524e886b7f1b8a0c1fc7321cacLinus Torvalds struct sctp_tsnmap_iter iter; 33602015180e2509afd2e3fe3790a333b30708a116bVlad Yasevich int ngaps = 0; 3371da177e4c3f41524e886b7f1b8a0c1fc7321cacLinus Torvalds 3381da177e4c3f41524e886b7f1b8a0c1fc7321cacLinus Torvalds /* Refresh the gap ack information. */ 3391da177e4c3f41524e886b7f1b8a0c1fc7321cacLinus Torvalds if (sctp_tsnmap_has_gap(map)) { 34059ed5aba9ca1c799e272b352d5d2d7fe12bd32e8Shan Wei __u16 start = 0, end = 0; 3411da177e4c3f41524e886b7f1b8a0c1fc7321cacLinus Torvalds sctp_tsnmap_iter_init(map, &iter); 3421da177e4c3f41524e886b7f1b8a0c1fc7321cacLinus Torvalds while (sctp_tsnmap_next_gap_ack(map, &iter, 3439f81bcd9429e9bb4006eb9b7df276706c5df926dAl Viro &start, 3449f81bcd9429e9bb4006eb9b7df276706c5df926dAl Viro &end)) { 3451da177e4c3f41524e886b7f1b8a0c1fc7321cacLinus Torvalds 34602015180e2509afd2e3fe3790a333b30708a116bVlad Yasevich gabs[ngaps].start = htons(start); 34702015180e2509afd2e3fe3790a333b30708a116bVlad Yasevich gabs[ngaps].end = htons(end); 34802015180e2509afd2e3fe3790a333b30708a116bVlad Yasevich ngaps++; 34902015180e2509afd2e3fe3790a333b30708a116bVlad Yasevich if (ngaps >= SCTP_MAX_GABS) 3501da177e4c3f41524e886b7f1b8a0c1fc7321cacLinus Torvalds break; 3511da177e4c3f41524e886b7f1b8a0c1fc7321cacLinus Torvalds } 3521da177e4c3f41524e886b7f1b8a0c1fc7321cacLinus Torvalds } 35302015180e2509afd2e3fe3790a333b30708a116bVlad Yasevich return ngaps; 3541da177e4c3f41524e886b7f1b8a0c1fc7321cacLinus Torvalds} 3558e1ee18c332e08bee9d8bd66e63cd564fbf17fc2Vlad Yasevich 35670fc69bc5a54d9776ace7c99d46eb533f8fb6e89Lee A. Robertsstatic int sctp_tsnmap_grow(struct sctp_tsnmap *map, u16 size) 3578e1ee18c332e08bee9d8bd66e63cd564fbf17fc2Vlad Yasevich{ 3588e1ee18c332e08bee9d8bd66e63cd564fbf17fc2Vlad Yasevich unsigned long *new; 3598e1ee18c332e08bee9d8bd66e63cd564fbf17fc2Vlad Yasevich unsigned long inc; 3608e1ee18c332e08bee9d8bd66e63cd564fbf17fc2Vlad Yasevich u16 len; 3618e1ee18c332e08bee9d8bd66e63cd564fbf17fc2Vlad Yasevich 36270fc69bc5a54d9776ace7c99d46eb533f8fb6e89Lee A. Roberts if (size > SCTP_TSN_MAP_SIZE) 3638e1ee18c332e08bee9d8bd66e63cd564fbf17fc2Vlad Yasevich return 0; 3648e1ee18c332e08bee9d8bd66e63cd564fbf17fc2Vlad Yasevich 36570fc69bc5a54d9776ace7c99d46eb533f8fb6e89Lee A. Roberts inc = ALIGN((size - map->len), BITS_PER_LONG) + SCTP_TSN_MAP_INCREMENT; 3668e1ee18c332e08bee9d8bd66e63cd564fbf17fc2Vlad Yasevich len = min_t(u16, map->len + inc, SCTP_TSN_MAP_SIZE); 3678e1ee18c332e08bee9d8bd66e63cd564fbf17fc2Vlad Yasevich 3688e1ee18c332e08bee9d8bd66e63cd564fbf17fc2Vlad Yasevich new = kzalloc(len>>3, GFP_ATOMIC); 3698e1ee18c332e08bee9d8bd66e63cd564fbf17fc2Vlad Yasevich if (!new) 3708e1ee18c332e08bee9d8bd66e63cd564fbf17fc2Vlad Yasevich return 0; 3718e1ee18c332e08bee9d8bd66e63cd564fbf17fc2Vlad Yasevich 37270fc69bc5a54d9776ace7c99d46eb533f8fb6e89Lee A. Roberts bitmap_copy(new, map->tsn_map, 37370fc69bc5a54d9776ace7c99d46eb533f8fb6e89Lee A. Roberts map->max_tsn_seen - map->cumulative_tsn_ack_point); 3748e1ee18c332e08bee9d8bd66e63cd564fbf17fc2Vlad Yasevich kfree(map->tsn_map); 3758e1ee18c332e08bee9d8bd66e63cd564fbf17fc2Vlad Yasevich map->tsn_map = new; 3768e1ee18c332e08bee9d8bd66e63cd564fbf17fc2Vlad Yasevich map->len = len; 3778e1ee18c332e08bee9d8bd66e63cd564fbf17fc2Vlad Yasevich 3788e1ee18c332e08bee9d8bd66e63cd564fbf17fc2Vlad Yasevich return 1; 3798e1ee18c332e08bee9d8bd66e63cd564fbf17fc2Vlad Yasevich} 380