ulpqueue.c 23 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414415416417418419420421422423424425426427428429430431432433434435436437438439440441442443444445446447448449450451452453454455456457458459460461462463464465466467468469470471472473474475476477478479480481482483484485486487488489490491492493494495496497498499500501502503504505506507508509510511512513514515516517518519520521522523524525526527528529530531532533534535536537538539540541542543544545546547548549550551552553554555556557558559560561562563564565566567568569570571572573574575576577578579580581582583584585586587588589590591592593594595596597598599600601602603604605606607608609610611612613614615616617618619620621622623624625626627628629630631632633634635636637638639640641642643644645646647648649650651652653654655656657658659660661662663664665666667668669670671672673674675676677678679680681682683684685686687688689690691692693694695696697698699700701702703704705706707708709710711712713714715716717718719720721722723724725726727728729730731732733734735736737738739740741742743744745746747748749750751752753754755756757758759760761762763764765766767768769770771772773774775776777778779780781782783784785786787788789790791792793794795796797798799800801802803804805806807808809810811812813814815816817818819820821822823824825826827828829830831832833834835836837838839840841842843844845846847848849850851852853854855856857858859860861862863864865866867868869870871872873874875876877878879880881882883884885886887888889890891892893894895896897898899900901902903904905906907908
  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. * Copyright (c) 2001 Nokia, Inc.
  7. * Copyright (c) 2001 La Monte H.P. Yarroll
  8. *
  9. * This abstraction carries sctp events to the ULP (sockets).
  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. * Jon Grimm <jgrimm@us.ibm.com>
  37. * La Monte H.P. Yarroll <piggy@acm.org>
  38. * Sridhar Samudrala <sri@us.ibm.com>
  39. *
  40. * Any bugs reported given to us we will try to fix... any fixes shared will
  41. * be incorporated into the next SCTP release.
  42. */
  43. #include <linux/types.h>
  44. #include <linux/skbuff.h>
  45. #include <net/sock.h>
  46. #include <net/sctp/structs.h>
  47. #include <net/sctp/sctp.h>
  48. #include <net/sctp/sm.h>
  49. /* Forward declarations for internal helpers. */
  50. static struct sctp_ulpevent * sctp_ulpq_reasm(struct sctp_ulpq *ulpq,
  51. struct sctp_ulpevent *);
  52. static struct sctp_ulpevent * sctp_ulpq_order(struct sctp_ulpq *,
  53. struct sctp_ulpevent *);
  54. /* 1st Level Abstractions */
  55. /* Initialize a ULP queue from a block of memory. */
  56. struct sctp_ulpq *sctp_ulpq_init(struct sctp_ulpq *ulpq,
  57. struct sctp_association *asoc)
  58. {
  59. memset(ulpq, 0, sizeof(struct sctp_ulpq));
  60. ulpq->asoc = asoc;
  61. skb_queue_head_init(&ulpq->reasm);
  62. skb_queue_head_init(&ulpq->lobby);
  63. ulpq->pd_mode = 0;
  64. ulpq->malloced = 0;
  65. return ulpq;
  66. }
  67. /* Flush the reassembly and ordering queues. */
  68. void sctp_ulpq_flush(struct sctp_ulpq *ulpq)
  69. {
  70. struct sk_buff *skb;
  71. struct sctp_ulpevent *event;
  72. while ((skb = __skb_dequeue(&ulpq->lobby)) != NULL) {
  73. event = sctp_skb2event(skb);
  74. sctp_ulpevent_free(event);
  75. }
  76. while ((skb = __skb_dequeue(&ulpq->reasm)) != NULL) {
  77. event = sctp_skb2event(skb);
  78. sctp_ulpevent_free(event);
  79. }
  80. }
  81. /* Dispose of a ulpqueue. */
  82. void sctp_ulpq_free(struct sctp_ulpq *ulpq)
  83. {
  84. sctp_ulpq_flush(ulpq);
  85. if (ulpq->malloced)
  86. kfree(ulpq);
  87. }
  88. /* Process an incoming DATA chunk. */
  89. int sctp_ulpq_tail_data(struct sctp_ulpq *ulpq, struct sctp_chunk *chunk,
  90. gfp_t gfp)
  91. {
  92. struct sk_buff_head temp;
  93. sctp_data_chunk_t *hdr;
  94. struct sctp_ulpevent *event;
  95. hdr = (sctp_data_chunk_t *) chunk->chunk_hdr;
  96. /* Create an event from the incoming chunk. */
  97. event = sctp_ulpevent_make_rcvmsg(chunk->asoc, chunk, gfp);
  98. if (!event)
  99. return -ENOMEM;
  100. /* Do reassembly if needed. */
  101. event = sctp_ulpq_reasm(ulpq, event);
  102. /* Do ordering if needed. */
  103. if ((event) && (event->msg_flags & MSG_EOR)){
  104. /* Create a temporary list to collect chunks on. */
  105. skb_queue_head_init(&temp);
  106. __skb_queue_tail(&temp, sctp_event2skb(event));
  107. event = sctp_ulpq_order(ulpq, event);
  108. }
  109. /* Send event to the ULP. 'event' is the sctp_ulpevent for
  110. * very first SKB on the 'temp' list.
  111. */
  112. if (event)
  113. sctp_ulpq_tail_event(ulpq, event);
  114. return 0;
  115. }
  116. /* Add a new event for propagation to the ULP. */
  117. /* Clear the partial delivery mode for this socket. Note: This
  118. * assumes that no association is currently in partial delivery mode.
  119. */
  120. int sctp_clear_pd(struct sock *sk)
  121. {
  122. struct sctp_sock *sp = sctp_sk(sk);
  123. sp->pd_mode = 0;
  124. if (!skb_queue_empty(&sp->pd_lobby)) {
  125. struct list_head *list;
  126. sctp_skb_list_tail(&sp->pd_lobby, &sk->sk_receive_queue);
  127. list = (struct list_head *)&sctp_sk(sk)->pd_lobby;
  128. INIT_LIST_HEAD(list);
  129. return 1;
  130. }
  131. return 0;
  132. }
  133. /* Clear the pd_mode and restart any pending messages waiting for delivery. */
  134. static int sctp_ulpq_clear_pd(struct sctp_ulpq *ulpq)
  135. {
  136. ulpq->pd_mode = 0;
  137. return sctp_clear_pd(ulpq->asoc->base.sk);
  138. }
  139. /* If the SKB of 'event' is on a list, it is the first such member
  140. * of that list.
  141. */
  142. int sctp_ulpq_tail_event(struct sctp_ulpq *ulpq, struct sctp_ulpevent *event)
  143. {
  144. struct sock *sk = ulpq->asoc->base.sk;
  145. struct sk_buff_head *queue, *skb_list;
  146. struct sk_buff *skb = sctp_event2skb(event);
  147. int clear_pd = 0;
  148. skb_list = (struct sk_buff_head *) skb->prev;
  149. /* If the socket is just going to throw this away, do not
  150. * even try to deliver it.
  151. */
  152. if (sock_flag(sk, SOCK_DEAD) || (sk->sk_shutdown & RCV_SHUTDOWN))
  153. goto out_free;
  154. /* Check if the user wishes to receive this event. */
  155. if (!sctp_ulpevent_is_enabled(event, &sctp_sk(sk)->subscribe))
  156. goto out_free;
  157. /* If we are in partial delivery mode, post to the lobby until
  158. * partial delivery is cleared, unless, of course _this_ is
  159. * the association the cause of the partial delivery.
  160. */
  161. if (!sctp_sk(sk)->pd_mode) {
  162. queue = &sk->sk_receive_queue;
  163. } else if (ulpq->pd_mode) {
  164. /* If the association is in partial delivery, we
  165. * need to finish delivering the partially processed
  166. * packet before passing any other data. This is
  167. * because we don't truly support stream interleaving.
  168. */
  169. if ((event->msg_flags & MSG_NOTIFICATION) ||
  170. (SCTP_DATA_NOT_FRAG ==
  171. (event->msg_flags & SCTP_DATA_FRAG_MASK)))
  172. queue = &sctp_sk(sk)->pd_lobby;
  173. else {
  174. clear_pd = event->msg_flags & MSG_EOR;
  175. queue = &sk->sk_receive_queue;
  176. }
  177. } else
  178. queue = &sctp_sk(sk)->pd_lobby;
  179. /* If we are harvesting multiple skbs they will be
  180. * collected on a list.
  181. */
  182. if (skb_list)
  183. sctp_skb_list_tail(skb_list, queue);
  184. else
  185. __skb_queue_tail(queue, skb);
  186. /* Did we just complete partial delivery and need to get
  187. * rolling again? Move pending data to the receive
  188. * queue.
  189. */
  190. if (clear_pd)
  191. sctp_ulpq_clear_pd(ulpq);
  192. if (queue == &sk->sk_receive_queue)
  193. sk->sk_data_ready(sk, 0);
  194. return 1;
  195. out_free:
  196. if (skb_list)
  197. sctp_queue_purge_ulpevents(skb_list);
  198. else
  199. sctp_ulpevent_free(event);
  200. return 0;
  201. }
  202. /* 2nd Level Abstractions */
  203. /* Helper function to store chunks that need to be reassembled. */
  204. static inline void sctp_ulpq_store_reasm(struct sctp_ulpq *ulpq,
  205. struct sctp_ulpevent *event)
  206. {
  207. struct sk_buff *pos;
  208. struct sctp_ulpevent *cevent;
  209. __u32 tsn, ctsn;
  210. tsn = event->tsn;
  211. /* See if it belongs at the end. */
  212. pos = skb_peek_tail(&ulpq->reasm);
  213. if (!pos) {
  214. __skb_queue_tail(&ulpq->reasm, sctp_event2skb(event));
  215. return;
  216. }
  217. /* Short circuit just dropping it at the end. */
  218. cevent = sctp_skb2event(pos);
  219. ctsn = cevent->tsn;
  220. if (TSN_lt(ctsn, tsn)) {
  221. __skb_queue_tail(&ulpq->reasm, sctp_event2skb(event));
  222. return;
  223. }
  224. /* Find the right place in this list. We store them by TSN. */
  225. skb_queue_walk(&ulpq->reasm, pos) {
  226. cevent = sctp_skb2event(pos);
  227. ctsn = cevent->tsn;
  228. if (TSN_lt(tsn, ctsn))
  229. break;
  230. }
  231. /* Insert before pos. */
  232. __skb_insert(sctp_event2skb(event), pos->prev, pos, &ulpq->reasm);
  233. }
  234. /* Helper function to return an event corresponding to the reassembled
  235. * datagram.
  236. * This routine creates a re-assembled skb given the first and last skb's
  237. * as stored in the reassembly queue. The skb's may be non-linear if the sctp
  238. * payload was fragmented on the way and ip had to reassemble them.
  239. * We add the rest of skb's to the first skb's fraglist.
  240. */
  241. static struct sctp_ulpevent *sctp_make_reassembled_event(struct sk_buff_head *queue, struct sk_buff *f_frag, struct sk_buff *l_frag)
  242. {
  243. struct sk_buff *pos;
  244. struct sk_buff *new = NULL;
  245. struct sctp_ulpevent *event;
  246. struct sk_buff *pnext, *last;
  247. struct sk_buff *list = skb_shinfo(f_frag)->frag_list;
  248. /* Store the pointer to the 2nd skb */
  249. if (f_frag == l_frag)
  250. pos = NULL;
  251. else
  252. pos = f_frag->next;
  253. /* Get the last skb in the f_frag's frag_list if present. */
  254. for (last = list; list; last = list, list = list->next);
  255. /* Add the list of remaining fragments to the first fragments
  256. * frag_list.
  257. */
  258. if (last)
  259. last->next = pos;
  260. else {
  261. if (skb_cloned(f_frag)) {
  262. /* This is a cloned skb, we can't just modify
  263. * the frag_list. We need a new skb to do that.
  264. * Instead of calling skb_unshare(), we'll do it
  265. * ourselves since we need to delay the free.
  266. */
  267. new = skb_copy(f_frag, GFP_ATOMIC);
  268. if (!new)
  269. return NULL; /* try again later */
  270. sctp_skb_set_owner_r(new, f_frag->sk);
  271. skb_shinfo(new)->frag_list = pos;
  272. } else
  273. skb_shinfo(f_frag)->frag_list = pos;
  274. }
  275. /* Remove the first fragment from the reassembly queue. */
  276. __skb_unlink(f_frag, queue);
  277. /* if we did unshare, then free the old skb and re-assign */
  278. if (new) {
  279. kfree_skb(f_frag);
  280. f_frag = new;
  281. }
  282. while (pos) {
  283. pnext = pos->next;
  284. /* Update the len and data_len fields of the first fragment. */
  285. f_frag->len += pos->len;
  286. f_frag->data_len += pos->len;
  287. /* Remove the fragment from the reassembly queue. */
  288. __skb_unlink(pos, queue);
  289. /* Break if we have reached the last fragment. */
  290. if (pos == l_frag)
  291. break;
  292. pos->next = pnext;
  293. pos = pnext;
  294. };
  295. event = sctp_skb2event(f_frag);
  296. SCTP_INC_STATS(SCTP_MIB_REASMUSRMSGS);
  297. return event;
  298. }
  299. /* Helper function to check if an incoming chunk has filled up the last
  300. * missing fragment in a SCTP datagram and return the corresponding event.
  301. */
  302. static inline struct sctp_ulpevent *sctp_ulpq_retrieve_reassembled(struct sctp_ulpq *ulpq)
  303. {
  304. struct sk_buff *pos;
  305. struct sctp_ulpevent *cevent;
  306. struct sk_buff *first_frag = NULL;
  307. __u32 ctsn, next_tsn;
  308. struct sctp_ulpevent *retval = NULL;
  309. /* Initialized to 0 just to avoid compiler warning message. Will
  310. * never be used with this value. It is referenced only after it
  311. * is set when we find the first fragment of a message.
  312. */
  313. next_tsn = 0;
  314. /* The chunks are held in the reasm queue sorted by TSN.
  315. * Walk through the queue sequentially and look for a sequence of
  316. * fragmented chunks that complete a datagram.
  317. * 'first_frag' and next_tsn are reset when we find a chunk which
  318. * is the first fragment of a datagram. Once these 2 fields are set
  319. * we expect to find the remaining middle fragments and the last
  320. * fragment in order. If not, first_frag is reset to NULL and we
  321. * start the next pass when we find another first fragment.
  322. */
  323. skb_queue_walk(&ulpq->reasm, pos) {
  324. cevent = sctp_skb2event(pos);
  325. ctsn = cevent->tsn;
  326. switch (cevent->msg_flags & SCTP_DATA_FRAG_MASK) {
  327. case SCTP_DATA_FIRST_FRAG:
  328. first_frag = pos;
  329. next_tsn = ctsn + 1;
  330. break;
  331. case SCTP_DATA_MIDDLE_FRAG:
  332. if ((first_frag) && (ctsn == next_tsn))
  333. next_tsn++;
  334. else
  335. first_frag = NULL;
  336. break;
  337. case SCTP_DATA_LAST_FRAG:
  338. if (first_frag && (ctsn == next_tsn))
  339. goto found;
  340. else
  341. first_frag = NULL;
  342. break;
  343. };
  344. }
  345. done:
  346. return retval;
  347. found:
  348. retval = sctp_make_reassembled_event(&ulpq->reasm, first_frag, pos);
  349. if (retval)
  350. retval->msg_flags |= MSG_EOR;
  351. goto done;
  352. }
  353. /* Retrieve the next set of fragments of a partial message. */
  354. static inline struct sctp_ulpevent *sctp_ulpq_retrieve_partial(struct sctp_ulpq *ulpq)
  355. {
  356. struct sk_buff *pos, *last_frag, *first_frag;
  357. struct sctp_ulpevent *cevent;
  358. __u32 ctsn, next_tsn;
  359. int is_last;
  360. struct sctp_ulpevent *retval;
  361. /* The chunks are held in the reasm queue sorted by TSN.
  362. * Walk through the queue sequentially and look for the first
  363. * sequence of fragmented chunks.
  364. */
  365. if (skb_queue_empty(&ulpq->reasm))
  366. return NULL;
  367. last_frag = first_frag = NULL;
  368. retval = NULL;
  369. next_tsn = 0;
  370. is_last = 0;
  371. skb_queue_walk(&ulpq->reasm, pos) {
  372. cevent = sctp_skb2event(pos);
  373. ctsn = cevent->tsn;
  374. switch (cevent->msg_flags & SCTP_DATA_FRAG_MASK) {
  375. case SCTP_DATA_MIDDLE_FRAG:
  376. if (!first_frag) {
  377. first_frag = pos;
  378. next_tsn = ctsn + 1;
  379. last_frag = pos;
  380. } else if (next_tsn == ctsn)
  381. next_tsn++;
  382. else
  383. goto done;
  384. break;
  385. case SCTP_DATA_LAST_FRAG:
  386. if (!first_frag)
  387. first_frag = pos;
  388. else if (ctsn != next_tsn)
  389. goto done;
  390. last_frag = pos;
  391. is_last = 1;
  392. goto done;
  393. default:
  394. return NULL;
  395. };
  396. }
  397. /* We have the reassembled event. There is no need to look
  398. * further.
  399. */
  400. done:
  401. retval = sctp_make_reassembled_event(&ulpq->reasm, first_frag, last_frag);
  402. if (retval && is_last)
  403. retval->msg_flags |= MSG_EOR;
  404. return retval;
  405. }
  406. /* Helper function to reassemble chunks. Hold chunks on the reasm queue that
  407. * need reassembling.
  408. */
  409. static struct sctp_ulpevent *sctp_ulpq_reasm(struct sctp_ulpq *ulpq,
  410. struct sctp_ulpevent *event)
  411. {
  412. struct sctp_ulpevent *retval = NULL;
  413. /* Check if this is part of a fragmented message. */
  414. if (SCTP_DATA_NOT_FRAG == (event->msg_flags & SCTP_DATA_FRAG_MASK)) {
  415. event->msg_flags |= MSG_EOR;
  416. return event;
  417. }
  418. sctp_ulpq_store_reasm(ulpq, event);
  419. if (!ulpq->pd_mode)
  420. retval = sctp_ulpq_retrieve_reassembled(ulpq);
  421. else {
  422. __u32 ctsn, ctsnap;
  423. /* Do not even bother unless this is the next tsn to
  424. * be delivered.
  425. */
  426. ctsn = event->tsn;
  427. ctsnap = sctp_tsnmap_get_ctsn(&ulpq->asoc->peer.tsn_map);
  428. if (TSN_lte(ctsn, ctsnap))
  429. retval = sctp_ulpq_retrieve_partial(ulpq);
  430. }
  431. return retval;
  432. }
  433. /* Retrieve the first part (sequential fragments) for partial delivery. */
  434. static inline struct sctp_ulpevent *sctp_ulpq_retrieve_first(struct sctp_ulpq *ulpq)
  435. {
  436. struct sk_buff *pos, *last_frag, *first_frag;
  437. struct sctp_ulpevent *cevent;
  438. __u32 ctsn, next_tsn;
  439. struct sctp_ulpevent *retval;
  440. /* The chunks are held in the reasm queue sorted by TSN.
  441. * Walk through the queue sequentially and look for a sequence of
  442. * fragmented chunks that start a datagram.
  443. */
  444. if (skb_queue_empty(&ulpq->reasm))
  445. return NULL;
  446. last_frag = first_frag = NULL;
  447. retval = NULL;
  448. next_tsn = 0;
  449. skb_queue_walk(&ulpq->reasm, pos) {
  450. cevent = sctp_skb2event(pos);
  451. ctsn = cevent->tsn;
  452. switch (cevent->msg_flags & SCTP_DATA_FRAG_MASK) {
  453. case SCTP_DATA_FIRST_FRAG:
  454. if (!first_frag) {
  455. first_frag = pos;
  456. next_tsn = ctsn + 1;
  457. last_frag = pos;
  458. } else
  459. goto done;
  460. break;
  461. case SCTP_DATA_MIDDLE_FRAG:
  462. if (!first_frag)
  463. return NULL;
  464. if (ctsn == next_tsn) {
  465. next_tsn++;
  466. last_frag = pos;
  467. } else
  468. goto done;
  469. break;
  470. default:
  471. return NULL;
  472. };
  473. }
  474. /* We have the reassembled event. There is no need to look
  475. * further.
  476. */
  477. done:
  478. retval = sctp_make_reassembled_event(&ulpq->reasm, first_frag, last_frag);
  479. return retval;
  480. }
  481. /* Helper function to gather skbs that have possibly become
  482. * ordered by an an incoming chunk.
  483. */
  484. static inline void sctp_ulpq_retrieve_ordered(struct sctp_ulpq *ulpq,
  485. struct sctp_ulpevent *event)
  486. {
  487. struct sk_buff_head *event_list;
  488. struct sk_buff *pos, *tmp;
  489. struct sctp_ulpevent *cevent;
  490. struct sctp_stream *in;
  491. __u16 sid, csid;
  492. __u16 ssn, cssn;
  493. sid = event->stream;
  494. ssn = event->ssn;
  495. in = &ulpq->asoc->ssnmap->in;
  496. event_list = (struct sk_buff_head *) sctp_event2skb(event)->prev;
  497. /* We are holding the chunks by stream, by SSN. */
  498. sctp_skb_for_each(pos, &ulpq->lobby, tmp) {
  499. cevent = (struct sctp_ulpevent *) pos->cb;
  500. csid = cevent->stream;
  501. cssn = cevent->ssn;
  502. /* Have we gone too far? */
  503. if (csid > sid)
  504. break;
  505. /* Have we not gone far enough? */
  506. if (csid < sid)
  507. continue;
  508. if (cssn != sctp_ssn_peek(in, sid))
  509. break;
  510. /* Found it, so mark in the ssnmap. */
  511. sctp_ssn_next(in, sid);
  512. __skb_unlink(pos, &ulpq->lobby);
  513. /* Attach all gathered skbs to the event. */
  514. __skb_queue_tail(event_list, pos);
  515. }
  516. }
  517. /* Helper function to store chunks needing ordering. */
  518. static inline void sctp_ulpq_store_ordered(struct sctp_ulpq *ulpq,
  519. struct sctp_ulpevent *event)
  520. {
  521. struct sk_buff *pos;
  522. struct sctp_ulpevent *cevent;
  523. __u16 sid, csid;
  524. __u16 ssn, cssn;
  525. pos = skb_peek_tail(&ulpq->lobby);
  526. if (!pos) {
  527. __skb_queue_tail(&ulpq->lobby, sctp_event2skb(event));
  528. return;
  529. }
  530. sid = event->stream;
  531. ssn = event->ssn;
  532. cevent = (struct sctp_ulpevent *) pos->cb;
  533. csid = cevent->stream;
  534. cssn = cevent->ssn;
  535. if (sid > csid) {
  536. __skb_queue_tail(&ulpq->lobby, sctp_event2skb(event));
  537. return;
  538. }
  539. if ((sid == csid) && SSN_lt(cssn, ssn)) {
  540. __skb_queue_tail(&ulpq->lobby, sctp_event2skb(event));
  541. return;
  542. }
  543. /* Find the right place in this list. We store them by
  544. * stream ID and then by SSN.
  545. */
  546. skb_queue_walk(&ulpq->lobby, pos) {
  547. cevent = (struct sctp_ulpevent *) pos->cb;
  548. csid = cevent->stream;
  549. cssn = cevent->ssn;
  550. if (csid > sid)
  551. break;
  552. if (csid == sid && SSN_lt(ssn, cssn))
  553. break;
  554. }
  555. /* Insert before pos. */
  556. __skb_insert(sctp_event2skb(event), pos->prev, pos, &ulpq->lobby);
  557. }
  558. static struct sctp_ulpevent *sctp_ulpq_order(struct sctp_ulpq *ulpq,
  559. struct sctp_ulpevent *event)
  560. {
  561. __u16 sid, ssn;
  562. struct sctp_stream *in;
  563. /* Check if this message needs ordering. */
  564. if (SCTP_DATA_UNORDERED & event->msg_flags)
  565. return event;
  566. /* Note: The stream ID must be verified before this routine. */
  567. sid = event->stream;
  568. ssn = event->ssn;
  569. in = &ulpq->asoc->ssnmap->in;
  570. /* Is this the expected SSN for this stream ID? */
  571. if (ssn != sctp_ssn_peek(in, sid)) {
  572. /* We've received something out of order, so find where it
  573. * needs to be placed. We order by stream and then by SSN.
  574. */
  575. sctp_ulpq_store_ordered(ulpq, event);
  576. return NULL;
  577. }
  578. /* Mark that the next chunk has been found. */
  579. sctp_ssn_next(in, sid);
  580. /* Go find any other chunks that were waiting for
  581. * ordering.
  582. */
  583. sctp_ulpq_retrieve_ordered(ulpq, event);
  584. return event;
  585. }
  586. /* Helper function to gather skbs that have possibly become
  587. * ordered by forward tsn skipping their dependencies.
  588. */
  589. static inline void sctp_ulpq_reap_ordered(struct sctp_ulpq *ulpq)
  590. {
  591. struct sk_buff *pos, *tmp;
  592. struct sctp_ulpevent *cevent;
  593. struct sctp_ulpevent *event;
  594. struct sctp_stream *in;
  595. struct sk_buff_head temp;
  596. __u16 csid, cssn;
  597. in = &ulpq->asoc->ssnmap->in;
  598. /* We are holding the chunks by stream, by SSN. */
  599. skb_queue_head_init(&temp);
  600. event = NULL;
  601. sctp_skb_for_each(pos, &ulpq->lobby, tmp) {
  602. cevent = (struct sctp_ulpevent *) pos->cb;
  603. csid = cevent->stream;
  604. cssn = cevent->ssn;
  605. if (cssn != sctp_ssn_peek(in, csid))
  606. break;
  607. /* Found it, so mark in the ssnmap. */
  608. sctp_ssn_next(in, csid);
  609. __skb_unlink(pos, &ulpq->lobby);
  610. if (!event) {
  611. /* Create a temporary list to collect chunks on. */
  612. event = sctp_skb2event(pos);
  613. __skb_queue_tail(&temp, sctp_event2skb(event));
  614. } else {
  615. /* Attach all gathered skbs to the event. */
  616. __skb_queue_tail(&temp, pos);
  617. }
  618. }
  619. /* Send event to the ULP. 'event' is the sctp_ulpevent for
  620. * very first SKB on the 'temp' list.
  621. */
  622. if (event)
  623. sctp_ulpq_tail_event(ulpq, event);
  624. }
  625. /* Skip over an SSN. */
  626. void sctp_ulpq_skip(struct sctp_ulpq *ulpq, __u16 sid, __u16 ssn)
  627. {
  628. struct sctp_stream *in;
  629. /* Note: The stream ID must be verified before this routine. */
  630. in = &ulpq->asoc->ssnmap->in;
  631. /* Is this an old SSN? If so ignore. */
  632. if (SSN_lt(ssn, sctp_ssn_peek(in, sid)))
  633. return;
  634. /* Mark that we are no longer expecting this SSN or lower. */
  635. sctp_ssn_skip(in, sid, ssn);
  636. /* Go find any other chunks that were waiting for
  637. * ordering and deliver them if needed.
  638. */
  639. sctp_ulpq_reap_ordered(ulpq);
  640. return;
  641. }
  642. /* Renege 'needed' bytes from the ordering queue. */
  643. static __u16 sctp_ulpq_renege_order(struct sctp_ulpq *ulpq, __u16 needed)
  644. {
  645. __u16 freed = 0;
  646. __u32 tsn;
  647. struct sk_buff *skb;
  648. struct sctp_ulpevent *event;
  649. struct sctp_tsnmap *tsnmap;
  650. tsnmap = &ulpq->asoc->peer.tsn_map;
  651. while ((skb = __skb_dequeue_tail(&ulpq->lobby)) != NULL) {
  652. freed += skb_headlen(skb);
  653. event = sctp_skb2event(skb);
  654. tsn = event->tsn;
  655. sctp_ulpevent_free(event);
  656. sctp_tsnmap_renege(tsnmap, tsn);
  657. if (freed >= needed)
  658. return freed;
  659. }
  660. return freed;
  661. }
  662. /* Renege 'needed' bytes from the reassembly queue. */
  663. static __u16 sctp_ulpq_renege_frags(struct sctp_ulpq *ulpq, __u16 needed)
  664. {
  665. __u16 freed = 0;
  666. __u32 tsn;
  667. struct sk_buff *skb;
  668. struct sctp_ulpevent *event;
  669. struct sctp_tsnmap *tsnmap;
  670. tsnmap = &ulpq->asoc->peer.tsn_map;
  671. /* Walk backwards through the list, reneges the newest tsns. */
  672. while ((skb = __skb_dequeue_tail(&ulpq->reasm)) != NULL) {
  673. freed += skb_headlen(skb);
  674. event = sctp_skb2event(skb);
  675. tsn = event->tsn;
  676. sctp_ulpevent_free(event);
  677. sctp_tsnmap_renege(tsnmap, tsn);
  678. if (freed >= needed)
  679. return freed;
  680. }
  681. return freed;
  682. }
  683. /* Partial deliver the first message as there is pressure on rwnd. */
  684. void sctp_ulpq_partial_delivery(struct sctp_ulpq *ulpq,
  685. struct sctp_chunk *chunk,
  686. gfp_t gfp)
  687. {
  688. struct sctp_ulpevent *event;
  689. struct sctp_association *asoc;
  690. asoc = ulpq->asoc;
  691. /* Are we already in partial delivery mode? */
  692. if (!sctp_sk(asoc->base.sk)->pd_mode) {
  693. /* Is partial delivery possible? */
  694. event = sctp_ulpq_retrieve_first(ulpq);
  695. /* Send event to the ULP. */
  696. if (event) {
  697. sctp_ulpq_tail_event(ulpq, event);
  698. sctp_sk(asoc->base.sk)->pd_mode = 1;
  699. ulpq->pd_mode = 1;
  700. return;
  701. }
  702. }
  703. }
  704. /* Renege some packets to make room for an incoming chunk. */
  705. void sctp_ulpq_renege(struct sctp_ulpq *ulpq, struct sctp_chunk *chunk,
  706. gfp_t gfp)
  707. {
  708. struct sctp_association *asoc;
  709. __u16 needed, freed;
  710. asoc = ulpq->asoc;
  711. if (chunk) {
  712. needed = ntohs(chunk->chunk_hdr->length);
  713. needed -= sizeof(sctp_data_chunk_t);
  714. } else
  715. needed = SCTP_DEFAULT_MAXWINDOW;
  716. freed = 0;
  717. if (skb_queue_empty(&asoc->base.sk->sk_receive_queue)) {
  718. freed = sctp_ulpq_renege_order(ulpq, needed);
  719. if (freed < needed) {
  720. freed += sctp_ulpq_renege_frags(ulpq, needed - freed);
  721. }
  722. }
  723. /* If able to free enough room, accept this chunk. */
  724. if (chunk && (freed >= needed)) {
  725. __u32 tsn;
  726. tsn = ntohl(chunk->subh.data_hdr->tsn);
  727. sctp_tsnmap_mark(&asoc->peer.tsn_map, tsn);
  728. sctp_ulpq_tail_data(ulpq, chunk, gfp);
  729. sctp_ulpq_partial_delivery(ulpq, chunk, gfp);
  730. }
  731. return;
  732. }
  733. /* Notify the application if an association is aborted and in
  734. * partial delivery mode. Send up any pending received messages.
  735. */
  736. void sctp_ulpq_abort_pd(struct sctp_ulpq *ulpq, gfp_t gfp)
  737. {
  738. struct sctp_ulpevent *ev = NULL;
  739. struct sock *sk;
  740. if (!ulpq->pd_mode)
  741. return;
  742. sk = ulpq->asoc->base.sk;
  743. if (sctp_ulpevent_type_enabled(SCTP_PARTIAL_DELIVERY_EVENT,
  744. &sctp_sk(sk)->subscribe))
  745. ev = sctp_ulpevent_make_pdapi(ulpq->asoc,
  746. SCTP_PARTIAL_DELIVERY_ABORTED,
  747. gfp);
  748. if (ev)
  749. __skb_queue_tail(&sk->sk_receive_queue, sctp_event2skb(ev));
  750. /* If there is data waiting, send it up the socket now. */
  751. if (sctp_ulpq_clear_pd(ulpq) || ev)
  752. sk->sk_data_ready(sk, 0);
  753. }