tsnmap.c 10 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414415416417418
  1. /* SCTP kernel reference 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 reference Implementation
  8. *
  9. * These functions manipulate sctp tsn mapping array.
  10. *
  11. * The SCTP reference 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. * The SCTP reference 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. #include <linux/types.h>
  45. #include <net/sctp/sctp.h>
  46. #include <net/sctp/sm.h>
  47. static void sctp_tsnmap_update(struct sctp_tsnmap *map);
  48. static void sctp_tsnmap_find_gap_ack(__u8 *map, __u16 off,
  49. __u16 len, __u16 base,
  50. int *started, __u16 *start,
  51. int *ended, __u16 *end);
  52. /* Initialize a block of memory as a tsnmap. */
  53. struct sctp_tsnmap *sctp_tsnmap_init(struct sctp_tsnmap *map, __u16 len,
  54. __u32 initial_tsn)
  55. {
  56. map->tsn_map = map->raw_map;
  57. map->overflow_map = map->tsn_map + len;
  58. map->len = len;
  59. /* Clear out a TSN ack status. */
  60. memset(map->tsn_map, 0x00, map->len + map->len);
  61. /* Keep track of TSNs represented by tsn_map. */
  62. map->base_tsn = initial_tsn;
  63. map->overflow_tsn = initial_tsn + map->len;
  64. map->cumulative_tsn_ack_point = initial_tsn - 1;
  65. map->max_tsn_seen = map->cumulative_tsn_ack_point;
  66. map->malloced = 0;
  67. map->num_dup_tsns = 0;
  68. return map;
  69. }
  70. /* Test the tracking state of this TSN.
  71. * Returns:
  72. * 0 if the TSN has not yet been seen
  73. * >0 if the TSN has been seen (duplicate)
  74. * <0 if the TSN is invalid (too large to track)
  75. */
  76. int sctp_tsnmap_check(const struct sctp_tsnmap *map, __u32 tsn)
  77. {
  78. __s32 gap;
  79. int dup;
  80. /* Calculate the index into the mapping arrays. */
  81. gap = tsn - map->base_tsn;
  82. /* Verify that we can hold this TSN. */
  83. if (gap >= (/* base */ map->len + /* overflow */ map->len)) {
  84. dup = -1;
  85. goto out;
  86. }
  87. /* Honk if we've already seen this TSN.
  88. * We have three cases:
  89. * 1. The TSN is ancient or belongs to a previous tsn_map.
  90. * 2. The TSN is already marked in the tsn_map.
  91. * 3. The TSN is already marked in the tsn_map_overflow.
  92. */
  93. if (gap < 0 ||
  94. (gap < map->len && map->tsn_map[gap]) ||
  95. (gap >= map->len && map->overflow_map[gap - map->len]))
  96. dup = 1;
  97. else
  98. dup = 0;
  99. out:
  100. return dup;
  101. }
  102. /* Mark this TSN as seen. */
  103. void sctp_tsnmap_mark(struct sctp_tsnmap *map, __u32 tsn)
  104. {
  105. __s32 gap;
  106. /* Vacuously mark any TSN which precedes the map base or
  107. * exceeds the end of the map.
  108. */
  109. if (TSN_lt(tsn, map->base_tsn))
  110. return;
  111. if (!TSN_lt(tsn, map->base_tsn + map->len + map->len))
  112. return;
  113. /* Bump the max. */
  114. if (TSN_lt(map->max_tsn_seen, tsn))
  115. map->max_tsn_seen = tsn;
  116. /* Assert: TSN is in range. */
  117. gap = tsn - map->base_tsn;
  118. /* Mark the TSN as received. */
  119. if (gap < map->len)
  120. map->tsn_map[gap]++;
  121. else
  122. map->overflow_map[gap - map->len]++;
  123. /* Go fixup any internal TSN mapping variables including
  124. * cumulative_tsn_ack_point.
  125. */
  126. sctp_tsnmap_update(map);
  127. }
  128. /* Initialize a Gap Ack Block iterator from memory being provided. */
  129. SCTP_STATIC void sctp_tsnmap_iter_init(const struct sctp_tsnmap *map,
  130. struct sctp_tsnmap_iter *iter)
  131. {
  132. /* Only start looking one past the Cumulative TSN Ack Point. */
  133. iter->start = map->cumulative_tsn_ack_point + 1;
  134. }
  135. /* Get the next Gap Ack Blocks. Returns 0 if there was not another block
  136. * to get.
  137. */
  138. SCTP_STATIC int sctp_tsnmap_next_gap_ack(const struct sctp_tsnmap *map,
  139. struct sctp_tsnmap_iter *iter,
  140. __u16 *start, __u16 *end)
  141. {
  142. int started, ended;
  143. __u16 _start, _end, offset;
  144. /* We haven't found a gap yet. */
  145. started = ended = 0;
  146. /* If there are no more gap acks possible, get out fast. */
  147. if (TSN_lte(map->max_tsn_seen, iter->start))
  148. return 0;
  149. /* Search the first mapping array. */
  150. if (iter->start - map->base_tsn < map->len) {
  151. offset = iter->start - map->base_tsn;
  152. sctp_tsnmap_find_gap_ack(map->tsn_map, offset, map->len, 0,
  153. &started, &_start, &ended, &_end);
  154. }
  155. /* Do we need to check the overflow map? */
  156. if (!ended) {
  157. /* Fix up where we'd like to start searching in the
  158. * overflow map.
  159. */
  160. if (iter->start - map->base_tsn < map->len)
  161. offset = 0;
  162. else
  163. offset = iter->start - map->base_tsn - map->len;
  164. /* Search the overflow map. */
  165. sctp_tsnmap_find_gap_ack(map->overflow_map,
  166. offset,
  167. map->len,
  168. map->len,
  169. &started, &_start,
  170. &ended, &_end);
  171. }
  172. /* The Gap Ack Block happens to end at the end of the
  173. * overflow map.
  174. */
  175. if (started && !ended) {
  176. ended++;
  177. _end = map->len + map->len - 1;
  178. }
  179. /* If we found a Gap Ack Block, return the start and end and
  180. * bump the iterator forward.
  181. */
  182. if (ended) {
  183. /* Fix up the start and end based on the
  184. * Cumulative TSN Ack offset into the map.
  185. */
  186. int gap = map->cumulative_tsn_ack_point -
  187. map->base_tsn;
  188. *start = _start - gap;
  189. *end = _end - gap;
  190. /* Move the iterator forward. */
  191. iter->start = map->cumulative_tsn_ack_point + *end + 1;
  192. }
  193. return ended;
  194. }
  195. /* Mark this and any lower TSN as seen. */
  196. void sctp_tsnmap_skip(struct sctp_tsnmap *map, __u32 tsn)
  197. {
  198. __s32 gap;
  199. /* Vacuously mark any TSN which precedes the map base or
  200. * exceeds the end of the map.
  201. */
  202. if (TSN_lt(tsn, map->base_tsn))
  203. return;
  204. if (!TSN_lt(tsn, map->base_tsn + map->len + map->len))
  205. return;
  206. /* Bump the max. */
  207. if (TSN_lt(map->max_tsn_seen, tsn))
  208. map->max_tsn_seen = tsn;
  209. /* Assert: TSN is in range. */
  210. gap = tsn - map->base_tsn + 1;
  211. /* Mark the TSNs as received. */
  212. if (gap <= map->len)
  213. memset(map->tsn_map, 0x01, gap);
  214. else {
  215. memset(map->tsn_map, 0x01, map->len);
  216. memset(map->overflow_map, 0x01, (gap - map->len));
  217. }
  218. /* Go fixup any internal TSN mapping variables including
  219. * cumulative_tsn_ack_point.
  220. */
  221. sctp_tsnmap_update(map);
  222. }
  223. /********************************************************************
  224. * 2nd Level Abstractions
  225. ********************************************************************/
  226. /* This private helper function updates the tsnmap buffers and
  227. * the Cumulative TSN Ack Point.
  228. */
  229. static void sctp_tsnmap_update(struct sctp_tsnmap *map)
  230. {
  231. __u32 ctsn;
  232. ctsn = map->cumulative_tsn_ack_point;
  233. do {
  234. ctsn++;
  235. if (ctsn == map->overflow_tsn) {
  236. /* Now tsn_map must have been all '1's,
  237. * so we swap the map and check the overflow table
  238. */
  239. __u8 *tmp = map->tsn_map;
  240. memset(tmp, 0, map->len);
  241. map->tsn_map = map->overflow_map;
  242. map->overflow_map = tmp;
  243. /* Update the tsn_map boundaries. */
  244. map->base_tsn += map->len;
  245. map->overflow_tsn += map->len;
  246. }
  247. } while (map->tsn_map[ctsn - map->base_tsn]);
  248. map->cumulative_tsn_ack_point = ctsn - 1; /* Back up one. */
  249. }
  250. /* How many data chunks are we missing from our peer?
  251. */
  252. __u16 sctp_tsnmap_pending(struct sctp_tsnmap *map)
  253. {
  254. __u32 cum_tsn = map->cumulative_tsn_ack_point;
  255. __u32 max_tsn = map->max_tsn_seen;
  256. __u32 base_tsn = map->base_tsn;
  257. __u16 pending_data;
  258. __s32 gap, start, end, i;
  259. pending_data = max_tsn - cum_tsn;
  260. gap = max_tsn - base_tsn;
  261. if (gap <= 0 || gap >= (map->len + map->len))
  262. goto out;
  263. start = ((cum_tsn >= base_tsn) ? (cum_tsn - base_tsn + 1) : 0);
  264. end = ((gap > map->len ) ? map->len : gap + 1);
  265. for (i = start; i < end; i++) {
  266. if (map->tsn_map[i])
  267. pending_data--;
  268. }
  269. if (gap >= map->len) {
  270. start = 0;
  271. end = gap - map->len + 1;
  272. for (i = start; i < end; i++) {
  273. if (map->overflow_map[i])
  274. pending_data--;
  275. }
  276. }
  277. out:
  278. return pending_data;
  279. }
  280. /* This is a private helper for finding Gap Ack Blocks. It searches a
  281. * single array for the start and end of a Gap Ack Block.
  282. *
  283. * The flags "started" and "ended" tell is if we found the beginning
  284. * or (respectively) the end of a Gap Ack Block.
  285. */
  286. static void sctp_tsnmap_find_gap_ack(__u8 *map, __u16 off,
  287. __u16 len, __u16 base,
  288. int *started, __u16 *start,
  289. int *ended, __u16 *end)
  290. {
  291. int i = off;
  292. /* Look through the entire array, but break out
  293. * early if we have found the end of the Gap Ack Block.
  294. */
  295. /* Also, stop looking past the maximum TSN seen. */
  296. /* Look for the start. */
  297. if (!(*started)) {
  298. for (; i < len; i++) {
  299. if (map[i]) {
  300. (*started)++;
  301. *start = base + i;
  302. break;
  303. }
  304. }
  305. }
  306. /* Look for the end. */
  307. if (*started) {
  308. /* We have found the start, let's find the
  309. * end. If we find the end, break out.
  310. */
  311. for (; i < len; i++) {
  312. if (!map[i]) {
  313. (*ended)++;
  314. *end = base + i - 1;
  315. break;
  316. }
  317. }
  318. }
  319. }
  320. /* Renege that we have seen a TSN. */
  321. void sctp_tsnmap_renege(struct sctp_tsnmap *map, __u32 tsn)
  322. {
  323. __s32 gap;
  324. if (TSN_lt(tsn, map->base_tsn))
  325. return;
  326. if (!TSN_lt(tsn, map->base_tsn + map->len + map->len))
  327. return;
  328. /* Assert: TSN is in range. */
  329. gap = tsn - map->base_tsn;
  330. /* Pretend we never saw the TSN. */
  331. if (gap < map->len)
  332. map->tsn_map[gap] = 0;
  333. else
  334. map->overflow_map[gap - map->len] = 0;
  335. }
  336. /* How many gap ack blocks do we have recorded? */
  337. __u16 sctp_tsnmap_num_gabs(struct sctp_tsnmap *map)
  338. {
  339. struct sctp_tsnmap_iter iter;
  340. int gabs = 0;
  341. /* Refresh the gap ack information. */
  342. if (sctp_tsnmap_has_gap(map)) {
  343. __u16 start, end;
  344. sctp_tsnmap_iter_init(map, &iter);
  345. while (sctp_tsnmap_next_gap_ack(map, &iter,
  346. &start,
  347. &end)) {
  348. map->gabs[gabs].start = htons(start);
  349. map->gabs[gabs].end = htons(end);
  350. gabs++;
  351. if (gabs >= SCTP_MAX_GABS)
  352. break;
  353. }
  354. }
  355. return gabs;
  356. }