outqueue.c 50 KB

12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667686970717273747576777879808182838485868788899091929394959697989910010110210310410510610710810911011111211311411511611711811912012112212312412512612712812913013113213313413513613713813914014114214314414514614714814915015115215315415515615715815916016116216316416516616716816917017117217317417517617717817918018118218318418518618718818919019119219319419519619719819920020120220320420520620720820921021121221321421521621721821922022122222322422522622722822923023123223323423523623723823924024124224324424524624724824925025125225325425525625725825926026126226326426526626726826927027127227327427527627727827928028128228328428528628728828929029129229329429529629729829930030130230330430530630730830931031131231331431531631731831932032132232332432532632732832933033133233333433533633733833934034134234334434534634734834935035135235335435535635735835936036136236336436536636736836937037137237337437537637737837938038138238338438538638738838939039139239339439539639739839940040140240340440540640740840941041141241341441541641741841942042142242342442542642742842943043143243343443543643743843944044144244344444544644744844945045145245345445545645745845946046146246346446546646746846947047147247347447547647747847948048148248348448548648748848949049149249349449549649749849950050150250350450550650750850951051151251351451551651751851952052152252352452552652752852953053153253353453553653753853954054154254354454554654754854955055155255355455555655755855956056156256356456556656756856957057157257357457557657757857958058158258358458558658758858959059159259359459559659759859960060160260360460560660760860961061161261361461561661761861962062162262362462562662762862963063163263363463563663763863964064164264364464564664764864965065165265365465565665765865966066166266366466566666766866967067167267367467567667767867968068168268368468568668768868969069169269369469569669769869970070170270370470570670770870971071171271371471571671771871972072172272372472572672772872973073173273373473573673773873974074174274374474574674774874975075175275375475575675775875976076176276376476576676776876977077177277377477577677777877978078178278378478578678778878979079179279379479579679779879980080180280380480580680780880981081181281381481581681781881982082182282382482582682782882983083183283383483583683783883984084184284384484584684784884985085185285385485585685785885986086186286386486586686786886987087187287387487587687787887988088188288388488588688788888989089189289389489589689789889990090190290390490590690790890991091191291391491591691791891992092192292392492592692792892993093193293393493593693793893994094194294394494594694794894995095195295395495595695795895996096196296396496596696796896997097197297397497597697797897998098198298398498598698798898999099199299399499599699799899910001001100210031004100510061007100810091010101110121013101410151016101710181019102010211022102310241025102610271028102910301031103210331034103510361037103810391040104110421043104410451046104710481049105010511052105310541055105610571058105910601061106210631064106510661067106810691070107110721073107410751076107710781079108010811082108310841085108610871088108910901091109210931094109510961097109810991100110111021103110411051106110711081109111011111112111311141115111611171118111911201121112211231124112511261127112811291130113111321133113411351136113711381139114011411142114311441145114611471148114911501151115211531154115511561157115811591160116111621163116411651166116711681169117011711172117311741175117611771178117911801181118211831184118511861187118811891190119111921193119411951196119711981199120012011202120312041205120612071208120912101211121212131214121512161217121812191220122112221223122412251226122712281229123012311232123312341235123612371238123912401241124212431244124512461247124812491250125112521253125412551256125712581259126012611262126312641265126612671268126912701271127212731274127512761277127812791280128112821283128412851286128712881289129012911292129312941295129612971298129913001301130213031304130513061307130813091310131113121313131413151316131713181319132013211322132313241325132613271328132913301331133213331334133513361337133813391340134113421343134413451346134713481349135013511352135313541355135613571358135913601361136213631364136513661367136813691370137113721373137413751376137713781379138013811382138313841385138613871388138913901391139213931394139513961397139813991400140114021403140414051406140714081409141014111412141314141415141614171418141914201421142214231424142514261427142814291430143114321433143414351436143714381439144014411442144314441445144614471448144914501451145214531454145514561457145814591460146114621463146414651466146714681469147014711472147314741475147614771478147914801481148214831484148514861487148814891490149114921493149414951496149714981499150015011502150315041505150615071508150915101511151215131514151515161517151815191520152115221523152415251526152715281529153015311532153315341535153615371538153915401541154215431544154515461547154815491550155115521553155415551556155715581559156015611562156315641565156615671568156915701571157215731574157515761577157815791580158115821583158415851586158715881589159015911592159315941595159615971598159916001601160216031604160516061607160816091610161116121613161416151616161716181619162016211622162316241625162616271628162916301631163216331634163516361637163816391640164116421643164416451646164716481649165016511652165316541655165616571658165916601661166216631664166516661667166816691670167116721673167416751676167716781679168016811682168316841685168616871688168916901691169216931694169516961697169816991700170117021703170417051706170717081709171017111712171317141715171617171718171917201721172217231724172517261727172817291730173117321733173417351736173717381739174017411742174317441745174617471748174917501751175217531754175517561757175817591760176117621763176417651766176717681769
  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-2003 Intel Corp.
  6. *
  7. * This file is part of the SCTP kernel reference Implementation
  8. *
  9. * These functions implement the sctp_outq class. The outqueue handles
  10. * bundling and queueing of outgoing SCTP chunks.
  11. *
  12. * The SCTP reference implementation is free software;
  13. * you can redistribute it and/or modify it under the terms of
  14. * the GNU General Public License as published by
  15. * the Free Software Foundation; either version 2, or (at your option)
  16. * any later version.
  17. *
  18. * The SCTP reference implementation is distributed in the hope that it
  19. * will be useful, but WITHOUT ANY WARRANTY; without even the implied
  20. * ************************
  21. * warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.
  22. * See the GNU General Public License for more details.
  23. *
  24. * You should have received a copy of the GNU General Public License
  25. * along with GNU CC; see the file COPYING. If not, write to
  26. * the Free Software Foundation, 59 Temple Place - Suite 330,
  27. * Boston, MA 02111-1307, USA.
  28. *
  29. * Please send any bug reports or fixes you make to the
  30. * email address(es):
  31. * lksctp developers <lksctp-developers@lists.sourceforge.net>
  32. *
  33. * Or submit a bug report through the following website:
  34. * http://www.sf.net/projects/lksctp
  35. *
  36. * Written or modified by:
  37. * La Monte H.P. Yarroll <piggy@acm.org>
  38. * Karl Knutson <karl@athena.chicago.il.us>
  39. * Perry Melange <pmelange@null.cc.uic.edu>
  40. * Xingang Guo <xingang.guo@intel.com>
  41. * Hui Huang <hui.huang@nokia.com>
  42. * Sridhar Samudrala <sri@us.ibm.com>
  43. * Jon Grimm <jgrimm@us.ibm.com>
  44. *
  45. * Any bugs reported given to us we will try to fix... any fixes shared will
  46. * be incorporated into the next SCTP release.
  47. */
  48. #include <linux/types.h>
  49. #include <linux/list.h> /* For struct list_head */
  50. #include <linux/socket.h>
  51. #include <linux/ip.h>
  52. #include <net/sock.h> /* For skb_set_owner_w */
  53. #include <net/sctp/sctp.h>
  54. #include <net/sctp/sm.h>
  55. /* Declare internal functions here. */
  56. static int sctp_acked(struct sctp_sackhdr *sack, __u32 tsn);
  57. static void sctp_check_transmitted(struct sctp_outq *q,
  58. struct list_head *transmitted_queue,
  59. struct sctp_transport *transport,
  60. struct sctp_sackhdr *sack,
  61. __u32 highest_new_tsn);
  62. static void sctp_mark_missing(struct sctp_outq *q,
  63. struct list_head *transmitted_queue,
  64. struct sctp_transport *transport,
  65. __u32 highest_new_tsn,
  66. int count_of_newacks);
  67. static void sctp_generate_fwdtsn(struct sctp_outq *q, __u32 sack_ctsn);
  68. /* Add data to the front of the queue. */
  69. static inline void sctp_outq_head_data(struct sctp_outq *q,
  70. struct sctp_chunk *ch)
  71. {
  72. list_add(&ch->list, &q->out_chunk_list);
  73. q->out_qlen += ch->skb->len;
  74. return;
  75. }
  76. /* Take data from the front of the queue. */
  77. static inline struct sctp_chunk *sctp_outq_dequeue_data(struct sctp_outq *q)
  78. {
  79. struct sctp_chunk *ch = NULL;
  80. if (!list_empty(&q->out_chunk_list)) {
  81. struct list_head *entry = q->out_chunk_list.next;
  82. ch = list_entry(entry, struct sctp_chunk, list);
  83. list_del_init(entry);
  84. q->out_qlen -= ch->skb->len;
  85. }
  86. return ch;
  87. }
  88. /* Add data chunk to the end of the queue. */
  89. static inline void sctp_outq_tail_data(struct sctp_outq *q,
  90. struct sctp_chunk *ch)
  91. {
  92. list_add_tail(&ch->list, &q->out_chunk_list);
  93. q->out_qlen += ch->skb->len;
  94. return;
  95. }
  96. /*
  97. * SFR-CACC algorithm:
  98. * D) If count_of_newacks is greater than or equal to 2
  99. * and t was not sent to the current primary then the
  100. * sender MUST NOT increment missing report count for t.
  101. */
  102. static inline int sctp_cacc_skip_3_1_d(struct sctp_transport *primary,
  103. struct sctp_transport *transport,
  104. int count_of_newacks)
  105. {
  106. if (count_of_newacks >=2 && transport != primary)
  107. return 1;
  108. return 0;
  109. }
  110. /*
  111. * SFR-CACC algorithm:
  112. * F) If count_of_newacks is less than 2, let d be the
  113. * destination to which t was sent. If cacc_saw_newack
  114. * is 0 for destination d, then the sender MUST NOT
  115. * increment missing report count for t.
  116. */
  117. static inline int sctp_cacc_skip_3_1_f(struct sctp_transport *transport,
  118. int count_of_newacks)
  119. {
  120. if (count_of_newacks < 2 && !transport->cacc.cacc_saw_newack)
  121. return 1;
  122. return 0;
  123. }
  124. /*
  125. * SFR-CACC algorithm:
  126. * 3.1) If CYCLING_CHANGEOVER is 0, the sender SHOULD
  127. * execute steps C, D, F.
  128. *
  129. * C has been implemented in sctp_outq_sack
  130. */
  131. static inline int sctp_cacc_skip_3_1(struct sctp_transport *primary,
  132. struct sctp_transport *transport,
  133. int count_of_newacks)
  134. {
  135. if (!primary->cacc.cycling_changeover) {
  136. if (sctp_cacc_skip_3_1_d(primary, transport, count_of_newacks))
  137. return 1;
  138. if (sctp_cacc_skip_3_1_f(transport, count_of_newacks))
  139. return 1;
  140. return 0;
  141. }
  142. return 0;
  143. }
  144. /*
  145. * SFR-CACC algorithm:
  146. * 3.2) Else if CYCLING_CHANGEOVER is 1, and t is less
  147. * than next_tsn_at_change of the current primary, then
  148. * the sender MUST NOT increment missing report count
  149. * for t.
  150. */
  151. static inline int sctp_cacc_skip_3_2(struct sctp_transport *primary, __u32 tsn)
  152. {
  153. if (primary->cacc.cycling_changeover &&
  154. TSN_lt(tsn, primary->cacc.next_tsn_at_change))
  155. return 1;
  156. return 0;
  157. }
  158. /*
  159. * SFR-CACC algorithm:
  160. * 3) If the missing report count for TSN t is to be
  161. * incremented according to [RFC2960] and
  162. * [SCTP_STEWART-2002], and CHANGEOVER_ACTIVE is set,
  163. * then the sender MUST futher execute steps 3.1 and
  164. * 3.2 to determine if the missing report count for
  165. * TSN t SHOULD NOT be incremented.
  166. *
  167. * 3.3) If 3.1 and 3.2 do not dictate that the missing
  168. * report count for t should not be incremented, then
  169. * the sender SOULD increment missing report count for
  170. * t (according to [RFC2960] and [SCTP_STEWART_2002]).
  171. */
  172. static inline int sctp_cacc_skip(struct sctp_transport *primary,
  173. struct sctp_transport *transport,
  174. int count_of_newacks,
  175. __u32 tsn)
  176. {
  177. if (primary->cacc.changeover_active &&
  178. (sctp_cacc_skip_3_1(primary, transport, count_of_newacks)
  179. || sctp_cacc_skip_3_2(primary, tsn)))
  180. return 1;
  181. return 0;
  182. }
  183. /* Initialize an existing sctp_outq. This does the boring stuff.
  184. * You still need to define handlers if you really want to DO
  185. * something with this structure...
  186. */
  187. void sctp_outq_init(struct sctp_association *asoc, struct sctp_outq *q)
  188. {
  189. q->asoc = asoc;
  190. INIT_LIST_HEAD(&q->out_chunk_list);
  191. INIT_LIST_HEAD(&q->control_chunk_list);
  192. INIT_LIST_HEAD(&q->retransmit);
  193. INIT_LIST_HEAD(&q->sacked);
  194. INIT_LIST_HEAD(&q->abandoned);
  195. q->outstanding_bytes = 0;
  196. q->empty = 1;
  197. q->cork = 0;
  198. q->malloced = 0;
  199. q->out_qlen = 0;
  200. }
  201. /* Free the outqueue structure and any related pending chunks.
  202. */
  203. void sctp_outq_teardown(struct sctp_outq *q)
  204. {
  205. struct sctp_transport *transport;
  206. struct list_head *lchunk, *pos, *temp;
  207. struct sctp_chunk *chunk, *tmp;
  208. /* Throw away unacknowledged chunks. */
  209. list_for_each(pos, &q->asoc->peer.transport_addr_list) {
  210. transport = list_entry(pos, struct sctp_transport, transports);
  211. while ((lchunk = sctp_list_dequeue(&transport->transmitted)) != NULL) {
  212. chunk = list_entry(lchunk, struct sctp_chunk,
  213. transmitted_list);
  214. /* Mark as part of a failed message. */
  215. sctp_chunk_fail(chunk, q->error);
  216. sctp_chunk_free(chunk);
  217. }
  218. }
  219. /* Throw away chunks that have been gap ACKed. */
  220. list_for_each_safe(lchunk, temp, &q->sacked) {
  221. list_del_init(lchunk);
  222. chunk = list_entry(lchunk, struct sctp_chunk,
  223. transmitted_list);
  224. sctp_chunk_fail(chunk, q->error);
  225. sctp_chunk_free(chunk);
  226. }
  227. /* Throw away any chunks in the retransmit queue. */
  228. list_for_each_safe(lchunk, temp, &q->retransmit) {
  229. list_del_init(lchunk);
  230. chunk = list_entry(lchunk, struct sctp_chunk,
  231. transmitted_list);
  232. sctp_chunk_fail(chunk, q->error);
  233. sctp_chunk_free(chunk);
  234. }
  235. /* Throw away any chunks that are in the abandoned queue. */
  236. list_for_each_safe(lchunk, temp, &q->abandoned) {
  237. list_del_init(lchunk);
  238. chunk = list_entry(lchunk, struct sctp_chunk,
  239. transmitted_list);
  240. sctp_chunk_fail(chunk, q->error);
  241. sctp_chunk_free(chunk);
  242. }
  243. /* Throw away any leftover data chunks. */
  244. while ((chunk = sctp_outq_dequeue_data(q)) != NULL) {
  245. /* Mark as send failure. */
  246. sctp_chunk_fail(chunk, q->error);
  247. sctp_chunk_free(chunk);
  248. }
  249. q->error = 0;
  250. /* Throw away any leftover control chunks. */
  251. list_for_each_entry_safe(chunk, tmp, &q->control_chunk_list, list) {
  252. list_del_init(&chunk->list);
  253. sctp_chunk_free(chunk);
  254. }
  255. }
  256. /* Free the outqueue structure and any related pending chunks. */
  257. void sctp_outq_free(struct sctp_outq *q)
  258. {
  259. /* Throw away leftover chunks. */
  260. sctp_outq_teardown(q);
  261. /* If we were kmalloc()'d, free the memory. */
  262. if (q->malloced)
  263. kfree(q);
  264. }
  265. /* Put a new chunk in an sctp_outq. */
  266. int sctp_outq_tail(struct sctp_outq *q, struct sctp_chunk *chunk)
  267. {
  268. int error = 0;
  269. SCTP_DEBUG_PRINTK("sctp_outq_tail(%p, %p[%s])\n",
  270. q, chunk, chunk && chunk->chunk_hdr ?
  271. sctp_cname(SCTP_ST_CHUNK(chunk->chunk_hdr->type))
  272. : "Illegal Chunk");
  273. /* If it is data, queue it up, otherwise, send it
  274. * immediately.
  275. */
  276. if (SCTP_CID_DATA == chunk->chunk_hdr->type) {
  277. /* Is it OK to queue data chunks? */
  278. /* From 9. Termination of Association
  279. *
  280. * When either endpoint performs a shutdown, the
  281. * association on each peer will stop accepting new
  282. * data from its user and only deliver data in queue
  283. * at the time of sending or receiving the SHUTDOWN
  284. * chunk.
  285. */
  286. switch (q->asoc->state) {
  287. case SCTP_STATE_EMPTY:
  288. case SCTP_STATE_CLOSED:
  289. case SCTP_STATE_SHUTDOWN_PENDING:
  290. case SCTP_STATE_SHUTDOWN_SENT:
  291. case SCTP_STATE_SHUTDOWN_RECEIVED:
  292. case SCTP_STATE_SHUTDOWN_ACK_SENT:
  293. /* Cannot send after transport endpoint shutdown */
  294. error = -ESHUTDOWN;
  295. break;
  296. default:
  297. SCTP_DEBUG_PRINTK("outqueueing (%p, %p[%s])\n",
  298. q, chunk, chunk && chunk->chunk_hdr ?
  299. sctp_cname(SCTP_ST_CHUNK(chunk->chunk_hdr->type))
  300. : "Illegal Chunk");
  301. sctp_outq_tail_data(q, chunk);
  302. if (chunk->chunk_hdr->flags & SCTP_DATA_UNORDERED)
  303. SCTP_INC_STATS(SCTP_MIB_OUTUNORDERCHUNKS);
  304. else
  305. SCTP_INC_STATS(SCTP_MIB_OUTORDERCHUNKS);
  306. q->empty = 0;
  307. break;
  308. };
  309. } else {
  310. list_add_tail(&chunk->list, &q->control_chunk_list);
  311. SCTP_INC_STATS(SCTP_MIB_OUTCTRLCHUNKS);
  312. }
  313. if (error < 0)
  314. return error;
  315. if (!q->cork)
  316. error = sctp_outq_flush(q, 0);
  317. return error;
  318. }
  319. /* Insert a chunk into the sorted list based on the TSNs. The retransmit list
  320. * and the abandoned list are in ascending order.
  321. */
  322. static void sctp_insert_list(struct list_head *head, struct list_head *new)
  323. {
  324. struct list_head *pos;
  325. struct sctp_chunk *nchunk, *lchunk;
  326. __u32 ntsn, ltsn;
  327. int done = 0;
  328. nchunk = list_entry(new, struct sctp_chunk, transmitted_list);
  329. ntsn = ntohl(nchunk->subh.data_hdr->tsn);
  330. list_for_each(pos, head) {
  331. lchunk = list_entry(pos, struct sctp_chunk, transmitted_list);
  332. ltsn = ntohl(lchunk->subh.data_hdr->tsn);
  333. if (TSN_lt(ntsn, ltsn)) {
  334. list_add(new, pos->prev);
  335. done = 1;
  336. break;
  337. }
  338. }
  339. if (!done)
  340. list_add_tail(new, head);
  341. }
  342. /* Mark all the eligible packets on a transport for retransmission. */
  343. void sctp_retransmit_mark(struct sctp_outq *q,
  344. struct sctp_transport *transport,
  345. __u8 fast_retransmit)
  346. {
  347. struct list_head *lchunk, *ltemp;
  348. struct sctp_chunk *chunk;
  349. /* Walk through the specified transmitted queue. */
  350. list_for_each_safe(lchunk, ltemp, &transport->transmitted) {
  351. chunk = list_entry(lchunk, struct sctp_chunk,
  352. transmitted_list);
  353. /* If the chunk is abandoned, move it to abandoned list. */
  354. if (sctp_chunk_abandoned(chunk)) {
  355. list_del_init(lchunk);
  356. sctp_insert_list(&q->abandoned, lchunk);
  357. /* If this chunk has not been previousely acked,
  358. * stop considering it 'outstanding'. Our peer
  359. * will most likely never see it since it will
  360. * not be retransmitted
  361. */
  362. if (!chunk->tsn_gap_acked) {
  363. chunk->transport->flight_size -=
  364. sctp_data_size(chunk);
  365. q->outstanding_bytes -= sctp_data_size(chunk);
  366. q->asoc->peer.rwnd += (sctp_data_size(chunk) +
  367. sizeof(struct sk_buff));
  368. }
  369. continue;
  370. }
  371. /* If we are doing retransmission due to a fast retransmit,
  372. * only the chunk's that are marked for fast retransmit
  373. * should be added to the retransmit queue. If we are doing
  374. * retransmission due to a timeout or pmtu discovery, only the
  375. * chunks that are not yet acked should be added to the
  376. * retransmit queue.
  377. */
  378. if ((fast_retransmit && (chunk->fast_retransmit > 0)) ||
  379. (!fast_retransmit && !chunk->tsn_gap_acked)) {
  380. /* RFC 2960 6.2.1 Processing a Received SACK
  381. *
  382. * C) Any time a DATA chunk is marked for
  383. * retransmission (via either T3-rtx timer expiration
  384. * (Section 6.3.3) or via fast retransmit
  385. * (Section 7.2.4)), add the data size of those
  386. * chunks to the rwnd.
  387. */
  388. q->asoc->peer.rwnd += (sctp_data_size(chunk) +
  389. sizeof(struct sk_buff));
  390. q->outstanding_bytes -= sctp_data_size(chunk);
  391. transport->flight_size -= sctp_data_size(chunk);
  392. /* sctpimpguide-05 Section 2.8.2
  393. * M5) If a T3-rtx timer expires, the
  394. * 'TSN.Missing.Report' of all affected TSNs is set
  395. * to 0.
  396. */
  397. chunk->tsn_missing_report = 0;
  398. /* If a chunk that is being used for RTT measurement
  399. * has to be retransmitted, we cannot use this chunk
  400. * anymore for RTT measurements. Reset rto_pending so
  401. * that a new RTT measurement is started when a new
  402. * data chunk is sent.
  403. */
  404. if (chunk->rtt_in_progress) {
  405. chunk->rtt_in_progress = 0;
  406. transport->rto_pending = 0;
  407. }
  408. /* Move the chunk to the retransmit queue. The chunks
  409. * on the retransmit queue are always kept in order.
  410. */
  411. list_del_init(lchunk);
  412. sctp_insert_list(&q->retransmit, lchunk);
  413. }
  414. }
  415. SCTP_DEBUG_PRINTK("%s: transport: %p, fast_retransmit: %d, "
  416. "cwnd: %d, ssthresh: %d, flight_size: %d, "
  417. "pba: %d\n", __FUNCTION__,
  418. transport, fast_retransmit,
  419. transport->cwnd, transport->ssthresh,
  420. transport->flight_size,
  421. transport->partial_bytes_acked);
  422. }
  423. /* Mark all the eligible packets on a transport for retransmission and force
  424. * one packet out.
  425. */
  426. void sctp_retransmit(struct sctp_outq *q, struct sctp_transport *transport,
  427. sctp_retransmit_reason_t reason)
  428. {
  429. int error = 0;
  430. __u8 fast_retransmit = 0;
  431. switch(reason) {
  432. case SCTP_RTXR_T3_RTX:
  433. SCTP_INC_STATS(SCTP_MIB_T3_RETRANSMITS);
  434. sctp_transport_lower_cwnd(transport, SCTP_LOWER_CWND_T3_RTX);
  435. /* Update the retran path if the T3-rtx timer has expired for
  436. * the current retran path.
  437. */
  438. if (transport == transport->asoc->peer.retran_path)
  439. sctp_assoc_update_retran_path(transport->asoc);
  440. break;
  441. case SCTP_RTXR_FAST_RTX:
  442. SCTP_INC_STATS(SCTP_MIB_FAST_RETRANSMITS);
  443. sctp_transport_lower_cwnd(transport, SCTP_LOWER_CWND_FAST_RTX);
  444. fast_retransmit = 1;
  445. break;
  446. case SCTP_RTXR_PMTUD:
  447. SCTP_INC_STATS(SCTP_MIB_PMTUD_RETRANSMITS);
  448. break;
  449. default:
  450. BUG();
  451. }
  452. sctp_retransmit_mark(q, transport, fast_retransmit);
  453. /* PR-SCTP A5) Any time the T3-rtx timer expires, on any destination,
  454. * the sender SHOULD try to advance the "Advanced.Peer.Ack.Point" by
  455. * following the procedures outlined in C1 - C5.
  456. */
  457. sctp_generate_fwdtsn(q, q->asoc->ctsn_ack_point);
  458. error = sctp_outq_flush(q, /* rtx_timeout */ 1);
  459. if (error)
  460. q->asoc->base.sk->sk_err = -error;
  461. }
  462. /*
  463. * Transmit DATA chunks on the retransmit queue. Upon return from
  464. * sctp_outq_flush_rtx() the packet 'pkt' may contain chunks which
  465. * need to be transmitted by the caller.
  466. * We assume that pkt->transport has already been set.
  467. *
  468. * The return value is a normal kernel error return value.
  469. */
  470. static int sctp_outq_flush_rtx(struct sctp_outq *q, struct sctp_packet *pkt,
  471. int rtx_timeout, int *start_timer)
  472. {
  473. struct list_head *lqueue;
  474. struct list_head *lchunk, *lchunk1;
  475. struct sctp_transport *transport = pkt->transport;
  476. sctp_xmit_t status;
  477. struct sctp_chunk *chunk, *chunk1;
  478. struct sctp_association *asoc;
  479. int error = 0;
  480. asoc = q->asoc;
  481. lqueue = &q->retransmit;
  482. /* RFC 2960 6.3.3 Handle T3-rtx Expiration
  483. *
  484. * E3) Determine how many of the earliest (i.e., lowest TSN)
  485. * outstanding DATA chunks for the address for which the
  486. * T3-rtx has expired will fit into a single packet, subject
  487. * to the MTU constraint for the path corresponding to the
  488. * destination transport address to which the retransmission
  489. * is being sent (this may be different from the address for
  490. * which the timer expires [see Section 6.4]). Call this value
  491. * K. Bundle and retransmit those K DATA chunks in a single
  492. * packet to the destination endpoint.
  493. *
  494. * [Just to be painfully clear, if we are retransmitting
  495. * because a timeout just happened, we should send only ONE
  496. * packet of retransmitted data.]
  497. */
  498. lchunk = sctp_list_dequeue(lqueue);
  499. while (lchunk) {
  500. chunk = list_entry(lchunk, struct sctp_chunk,
  501. transmitted_list);
  502. /* Make sure that Gap Acked TSNs are not retransmitted. A
  503. * simple approach is just to move such TSNs out of the
  504. * way and into a 'transmitted' queue and skip to the
  505. * next chunk.
  506. */
  507. if (chunk->tsn_gap_acked) {
  508. list_add_tail(lchunk, &transport->transmitted);
  509. lchunk = sctp_list_dequeue(lqueue);
  510. continue;
  511. }
  512. /* Attempt to append this chunk to the packet. */
  513. status = sctp_packet_append_chunk(pkt, chunk);
  514. switch (status) {
  515. case SCTP_XMIT_PMTU_FULL:
  516. /* Send this packet. */
  517. if ((error = sctp_packet_transmit(pkt)) == 0)
  518. *start_timer = 1;
  519. /* If we are retransmitting, we should only
  520. * send a single packet.
  521. */
  522. if (rtx_timeout) {
  523. list_add(lchunk, lqueue);
  524. lchunk = NULL;
  525. }
  526. /* Bundle lchunk in the next round. */
  527. break;
  528. case SCTP_XMIT_RWND_FULL:
  529. /* Send this packet. */
  530. if ((error = sctp_packet_transmit(pkt)) == 0)
  531. *start_timer = 1;
  532. /* Stop sending DATA as there is no more room
  533. * at the receiver.
  534. */
  535. list_add(lchunk, lqueue);
  536. lchunk = NULL;
  537. break;
  538. case SCTP_XMIT_NAGLE_DELAY:
  539. /* Send this packet. */
  540. if ((error = sctp_packet_transmit(pkt)) == 0)
  541. *start_timer = 1;
  542. /* Stop sending DATA because of nagle delay. */
  543. list_add(lchunk, lqueue);
  544. lchunk = NULL;
  545. break;
  546. default:
  547. /* The append was successful, so add this chunk to
  548. * the transmitted list.
  549. */
  550. list_add_tail(lchunk, &transport->transmitted);
  551. /* Mark the chunk as ineligible for fast retransmit
  552. * after it is retransmitted.
  553. */
  554. if (chunk->fast_retransmit > 0)
  555. chunk->fast_retransmit = -1;
  556. *start_timer = 1;
  557. q->empty = 0;
  558. /* Retrieve a new chunk to bundle. */
  559. lchunk = sctp_list_dequeue(lqueue);
  560. break;
  561. };
  562. /* If we are here due to a retransmit timeout or a fast
  563. * retransmit and if there are any chunks left in the retransmit
  564. * queue that could not fit in the PMTU sized packet, they need * to be marked as ineligible for a subsequent fast retransmit.
  565. */
  566. if (rtx_timeout && !lchunk) {
  567. list_for_each(lchunk1, lqueue) {
  568. chunk1 = list_entry(lchunk1, struct sctp_chunk,
  569. transmitted_list);
  570. if (chunk1->fast_retransmit > 0)
  571. chunk1->fast_retransmit = -1;
  572. }
  573. }
  574. }
  575. return error;
  576. }
  577. /* Cork the outqueue so queued chunks are really queued. */
  578. int sctp_outq_uncork(struct sctp_outq *q)
  579. {
  580. int error = 0;
  581. if (q->cork) {
  582. q->cork = 0;
  583. error = sctp_outq_flush(q, 0);
  584. }
  585. return error;
  586. }
  587. /*
  588. * Try to flush an outqueue.
  589. *
  590. * Description: Send everything in q which we legally can, subject to
  591. * congestion limitations.
  592. * * Note: This function can be called from multiple contexts so appropriate
  593. * locking concerns must be made. Today we use the sock lock to protect
  594. * this function.
  595. */
  596. int sctp_outq_flush(struct sctp_outq *q, int rtx_timeout)
  597. {
  598. struct sctp_packet *packet;
  599. struct sctp_packet singleton;
  600. struct sctp_association *asoc = q->asoc;
  601. __u16 sport = asoc->base.bind_addr.port;
  602. __u16 dport = asoc->peer.port;
  603. __u32 vtag = asoc->peer.i.init_tag;
  604. struct sctp_transport *transport = NULL;
  605. struct sctp_transport *new_transport;
  606. struct sctp_chunk *chunk, *tmp;
  607. sctp_xmit_t status;
  608. int error = 0;
  609. int start_timer = 0;
  610. /* These transports have chunks to send. */
  611. struct list_head transport_list;
  612. struct list_head *ltransport;
  613. INIT_LIST_HEAD(&transport_list);
  614. packet = NULL;
  615. /*
  616. * 6.10 Bundling
  617. * ...
  618. * When bundling control chunks with DATA chunks, an
  619. * endpoint MUST place control chunks first in the outbound
  620. * SCTP packet. The transmitter MUST transmit DATA chunks
  621. * within a SCTP packet in increasing order of TSN.
  622. * ...
  623. */
  624. list_for_each_entry_safe(chunk, tmp, &q->control_chunk_list, list) {
  625. list_del_init(&chunk->list);
  626. /* Pick the right transport to use. */
  627. new_transport = chunk->transport;
  628. if (!new_transport) {
  629. new_transport = asoc->peer.active_path;
  630. } else if ((new_transport->state == SCTP_INACTIVE) ||
  631. (new_transport->state == SCTP_UNCONFIRMED)) {
  632. /* If the chunk is Heartbeat or Heartbeat Ack,
  633. * send it to chunk->transport, even if it's
  634. * inactive.
  635. *
  636. * 3.3.6 Heartbeat Acknowledgement:
  637. * ...
  638. * A HEARTBEAT ACK is always sent to the source IP
  639. * address of the IP datagram containing the
  640. * HEARTBEAT chunk to which this ack is responding.
  641. * ...
  642. */
  643. if (chunk->chunk_hdr->type != SCTP_CID_HEARTBEAT &&
  644. chunk->chunk_hdr->type != SCTP_CID_HEARTBEAT_ACK)
  645. new_transport = asoc->peer.active_path;
  646. }
  647. /* Are we switching transports?
  648. * Take care of transport locks.
  649. */
  650. if (new_transport != transport) {
  651. transport = new_transport;
  652. if (list_empty(&transport->send_ready)) {
  653. list_add_tail(&transport->send_ready,
  654. &transport_list);
  655. }
  656. packet = &transport->packet;
  657. sctp_packet_config(packet, vtag,
  658. asoc->peer.ecn_capable);
  659. }
  660. switch (chunk->chunk_hdr->type) {
  661. /*
  662. * 6.10 Bundling
  663. * ...
  664. * An endpoint MUST NOT bundle INIT, INIT ACK or SHUTDOWN
  665. * COMPLETE with any other chunks. [Send them immediately.]
  666. */
  667. case SCTP_CID_INIT:
  668. case SCTP_CID_INIT_ACK:
  669. case SCTP_CID_SHUTDOWN_COMPLETE:
  670. sctp_packet_init(&singleton, transport, sport, dport);
  671. sctp_packet_config(&singleton, vtag, 0);
  672. sctp_packet_append_chunk(&singleton, chunk);
  673. error = sctp_packet_transmit(&singleton);
  674. if (error < 0)
  675. return error;
  676. break;
  677. case SCTP_CID_ABORT:
  678. case SCTP_CID_SACK:
  679. case SCTP_CID_HEARTBEAT:
  680. case SCTP_CID_HEARTBEAT_ACK:
  681. case SCTP_CID_SHUTDOWN:
  682. case SCTP_CID_SHUTDOWN_ACK:
  683. case SCTP_CID_ERROR:
  684. case SCTP_CID_COOKIE_ECHO:
  685. case SCTP_CID_COOKIE_ACK:
  686. case SCTP_CID_ECN_ECNE:
  687. case SCTP_CID_ECN_CWR:
  688. case SCTP_CID_ASCONF:
  689. case SCTP_CID_ASCONF_ACK:
  690. case SCTP_CID_FWD_TSN:
  691. sctp_packet_transmit_chunk(packet, chunk);
  692. break;
  693. default:
  694. /* We built a chunk with an illegal type! */
  695. BUG();
  696. };
  697. }
  698. /* Is it OK to send data chunks? */
  699. switch (asoc->state) {
  700. case SCTP_STATE_COOKIE_ECHOED:
  701. /* Only allow bundling when this packet has a COOKIE-ECHO
  702. * chunk.
  703. */
  704. if (!packet || !packet->has_cookie_echo)
  705. break;
  706. /* fallthru */
  707. case SCTP_STATE_ESTABLISHED:
  708. case SCTP_STATE_SHUTDOWN_PENDING:
  709. case SCTP_STATE_SHUTDOWN_RECEIVED:
  710. /*
  711. * RFC 2960 6.1 Transmission of DATA Chunks
  712. *
  713. * C) When the time comes for the sender to transmit,
  714. * before sending new DATA chunks, the sender MUST
  715. * first transmit any outstanding DATA chunks which
  716. * are marked for retransmission (limited by the
  717. * current cwnd).
  718. */
  719. if (!list_empty(&q->retransmit)) {
  720. if (transport == asoc->peer.retran_path)
  721. goto retran;
  722. /* Switch transports & prepare the packet. */
  723. transport = asoc->peer.retran_path;
  724. if (list_empty(&transport->send_ready)) {
  725. list_add_tail(&transport->send_ready,
  726. &transport_list);
  727. }
  728. packet = &transport->packet;
  729. sctp_packet_config(packet, vtag,
  730. asoc->peer.ecn_capable);
  731. retran:
  732. error = sctp_outq_flush_rtx(q, packet,
  733. rtx_timeout, &start_timer);
  734. if (start_timer)
  735. sctp_transport_reset_timers(transport);
  736. /* This can happen on COOKIE-ECHO resend. Only
  737. * one chunk can get bundled with a COOKIE-ECHO.
  738. */
  739. if (packet->has_cookie_echo)
  740. goto sctp_flush_out;
  741. /* Don't send new data if there is still data
  742. * waiting to retransmit.
  743. */
  744. if (!list_empty(&q->retransmit))
  745. goto sctp_flush_out;
  746. }
  747. /* Finally, transmit new packets. */
  748. start_timer = 0;
  749. while ((chunk = sctp_outq_dequeue_data(q)) != NULL) {
  750. /* RFC 2960 6.5 Every DATA chunk MUST carry a valid
  751. * stream identifier.
  752. */
  753. if (chunk->sinfo.sinfo_stream >=
  754. asoc->c.sinit_num_ostreams) {
  755. /* Mark as failed send. */
  756. sctp_chunk_fail(chunk, SCTP_ERROR_INV_STRM);
  757. sctp_chunk_free(chunk);
  758. continue;
  759. }
  760. /* Has this chunk expired? */
  761. if (sctp_chunk_abandoned(chunk)) {
  762. sctp_chunk_fail(chunk, 0);
  763. sctp_chunk_free(chunk);
  764. continue;
  765. }
  766. /* If there is a specified transport, use it.
  767. * Otherwise, we want to use the active path.
  768. */
  769. new_transport = chunk->transport;
  770. if (!new_transport ||
  771. ((new_transport->state == SCTP_INACTIVE) ||
  772. (new_transport->state == SCTP_UNCONFIRMED)))
  773. new_transport = asoc->peer.active_path;
  774. /* Change packets if necessary. */
  775. if (new_transport != transport) {
  776. transport = new_transport;
  777. /* Schedule to have this transport's
  778. * packet flushed.
  779. */
  780. if (list_empty(&transport->send_ready)) {
  781. list_add_tail(&transport->send_ready,
  782. &transport_list);
  783. }
  784. packet = &transport->packet;
  785. sctp_packet_config(packet, vtag,
  786. asoc->peer.ecn_capable);
  787. }
  788. SCTP_DEBUG_PRINTK("sctp_outq_flush(%p, %p[%s]), ",
  789. q, chunk,
  790. chunk && chunk->chunk_hdr ?
  791. sctp_cname(SCTP_ST_CHUNK(
  792. chunk->chunk_hdr->type))
  793. : "Illegal Chunk");
  794. SCTP_DEBUG_PRINTK("TX TSN 0x%x skb->head "
  795. "%p skb->users %d.\n",
  796. ntohl(chunk->subh.data_hdr->tsn),
  797. chunk->skb ?chunk->skb->head : NULL,
  798. chunk->skb ?
  799. atomic_read(&chunk->skb->users) : -1);
  800. /* Add the chunk to the packet. */
  801. status = sctp_packet_transmit_chunk(packet, chunk);
  802. switch (status) {
  803. case SCTP_XMIT_PMTU_FULL:
  804. case SCTP_XMIT_RWND_FULL:
  805. case SCTP_XMIT_NAGLE_DELAY:
  806. /* We could not append this chunk, so put
  807. * the chunk back on the output queue.
  808. */
  809. SCTP_DEBUG_PRINTK("sctp_outq_flush: could "
  810. "not transmit TSN: 0x%x, status: %d\n",
  811. ntohl(chunk->subh.data_hdr->tsn),
  812. status);
  813. sctp_outq_head_data(q, chunk);
  814. goto sctp_flush_out;
  815. break;
  816. case SCTP_XMIT_OK:
  817. break;
  818. default:
  819. BUG();
  820. }
  821. /* BUG: We assume that the sctp_packet_transmit()
  822. * call below will succeed all the time and add the
  823. * chunk to the transmitted list and restart the
  824. * timers.
  825. * It is possible that the call can fail under OOM
  826. * conditions.
  827. *
  828. * Is this really a problem? Won't this behave
  829. * like a lost TSN?
  830. */
  831. list_add_tail(&chunk->transmitted_list,
  832. &transport->transmitted);
  833. sctp_transport_reset_timers(transport);
  834. q->empty = 0;
  835. /* Only let one DATA chunk get bundled with a
  836. * COOKIE-ECHO chunk.
  837. */
  838. if (packet->has_cookie_echo)
  839. goto sctp_flush_out;
  840. }
  841. break;
  842. default:
  843. /* Do nothing. */
  844. break;
  845. }
  846. sctp_flush_out:
  847. /* Before returning, examine all the transports touched in
  848. * this call. Right now, we bluntly force clear all the
  849. * transports. Things might change after we implement Nagle.
  850. * But such an examination is still required.
  851. *
  852. * --xguo
  853. */
  854. while ((ltransport = sctp_list_dequeue(&transport_list)) != NULL ) {
  855. struct sctp_transport *t = list_entry(ltransport,
  856. struct sctp_transport,
  857. send_ready);
  858. packet = &t->packet;
  859. if (!sctp_packet_empty(packet))
  860. error = sctp_packet_transmit(packet);
  861. }
  862. return error;
  863. }
  864. /* Update unack_data based on the incoming SACK chunk */
  865. static void sctp_sack_update_unack_data(struct sctp_association *assoc,
  866. struct sctp_sackhdr *sack)
  867. {
  868. sctp_sack_variable_t *frags;
  869. __u16 unack_data;
  870. int i;
  871. unack_data = assoc->next_tsn - assoc->ctsn_ack_point - 1;
  872. frags = sack->variable;
  873. for (i = 0; i < ntohs(sack->num_gap_ack_blocks); i++) {
  874. unack_data -= ((ntohs(frags[i].gab.end) -
  875. ntohs(frags[i].gab.start) + 1));
  876. }
  877. assoc->unack_data = unack_data;
  878. }
  879. /* Return the highest new tsn that is acknowledged by the given SACK chunk. */
  880. static __u32 sctp_highest_new_tsn(struct sctp_sackhdr *sack,
  881. struct sctp_association *asoc)
  882. {
  883. struct list_head *ltransport, *lchunk;
  884. struct sctp_transport *transport;
  885. struct sctp_chunk *chunk;
  886. __u32 highest_new_tsn, tsn;
  887. struct list_head *transport_list = &asoc->peer.transport_addr_list;
  888. highest_new_tsn = ntohl(sack->cum_tsn_ack);
  889. list_for_each(ltransport, transport_list) {
  890. transport = list_entry(ltransport, struct sctp_transport,
  891. transports);
  892. list_for_each(lchunk, &transport->transmitted) {
  893. chunk = list_entry(lchunk, struct sctp_chunk,
  894. transmitted_list);
  895. tsn = ntohl(chunk->subh.data_hdr->tsn);
  896. if (!chunk->tsn_gap_acked &&
  897. TSN_lt(highest_new_tsn, tsn) &&
  898. sctp_acked(sack, tsn))
  899. highest_new_tsn = tsn;
  900. }
  901. }
  902. return highest_new_tsn;
  903. }
  904. /* This is where we REALLY process a SACK.
  905. *
  906. * Process the SACK against the outqueue. Mostly, this just frees
  907. * things off the transmitted queue.
  908. */
  909. int sctp_outq_sack(struct sctp_outq *q, struct sctp_sackhdr *sack)
  910. {
  911. struct sctp_association *asoc = q->asoc;
  912. struct sctp_transport *transport;
  913. struct sctp_chunk *tchunk = NULL;
  914. struct list_head *lchunk, *transport_list, *pos, *temp;
  915. sctp_sack_variable_t *frags = sack->variable;
  916. __u32 sack_ctsn, ctsn, tsn;
  917. __u32 highest_tsn, highest_new_tsn;
  918. __u32 sack_a_rwnd;
  919. unsigned outstanding;
  920. struct sctp_transport *primary = asoc->peer.primary_path;
  921. int count_of_newacks = 0;
  922. /* Grab the association's destination address list. */
  923. transport_list = &asoc->peer.transport_addr_list;
  924. sack_ctsn = ntohl(sack->cum_tsn_ack);
  925. /*
  926. * SFR-CACC algorithm:
  927. * On receipt of a SACK the sender SHOULD execute the
  928. * following statements.
  929. *
  930. * 1) If the cumulative ack in the SACK passes next tsn_at_change
  931. * on the current primary, the CHANGEOVER_ACTIVE flag SHOULD be
  932. * cleared. The CYCLING_CHANGEOVER flag SHOULD also be cleared for
  933. * all destinations.
  934. */
  935. if (TSN_lte(primary->cacc.next_tsn_at_change, sack_ctsn)) {
  936. primary->cacc.changeover_active = 0;
  937. list_for_each(pos, transport_list) {
  938. transport = list_entry(pos, struct sctp_transport,
  939. transports);
  940. transport->cacc.cycling_changeover = 0;
  941. }
  942. }
  943. /*
  944. * SFR-CACC algorithm:
  945. * 2) If the SACK contains gap acks and the flag CHANGEOVER_ACTIVE
  946. * is set the receiver of the SACK MUST take the following actions:
  947. *
  948. * A) Initialize the cacc_saw_newack to 0 for all destination
  949. * addresses.
  950. */
  951. if (sack->num_gap_ack_blocks &&
  952. primary->cacc.changeover_active) {
  953. list_for_each(pos, transport_list) {
  954. transport = list_entry(pos, struct sctp_transport,
  955. transports);
  956. transport->cacc.cacc_saw_newack = 0;
  957. }
  958. }
  959. /* Get the highest TSN in the sack. */
  960. highest_tsn = sack_ctsn;
  961. if (sack->num_gap_ack_blocks)
  962. highest_tsn +=
  963. ntohs(frags[ntohs(sack->num_gap_ack_blocks) - 1].gab.end);
  964. if (TSN_lt(asoc->highest_sacked, highest_tsn)) {
  965. highest_new_tsn = highest_tsn;
  966. asoc->highest_sacked = highest_tsn;
  967. } else {
  968. highest_new_tsn = sctp_highest_new_tsn(sack, asoc);
  969. }
  970. /* Run through the retransmit queue. Credit bytes received
  971. * and free those chunks that we can.
  972. */
  973. sctp_check_transmitted(q, &q->retransmit, NULL, sack, highest_new_tsn);
  974. sctp_mark_missing(q, &q->retransmit, NULL, highest_new_tsn, 0);
  975. /* Run through the transmitted queue.
  976. * Credit bytes received and free those chunks which we can.
  977. *
  978. * This is a MASSIVE candidate for optimization.
  979. */
  980. list_for_each(pos, transport_list) {
  981. transport = list_entry(pos, struct sctp_transport,
  982. transports);
  983. sctp_check_transmitted(q, &transport->transmitted,
  984. transport, sack, highest_new_tsn);
  985. /*
  986. * SFR-CACC algorithm:
  987. * C) Let count_of_newacks be the number of
  988. * destinations for which cacc_saw_newack is set.
  989. */
  990. if (transport->cacc.cacc_saw_newack)
  991. count_of_newacks ++;
  992. }
  993. list_for_each(pos, transport_list) {
  994. transport = list_entry(pos, struct sctp_transport,
  995. transports);
  996. sctp_mark_missing(q, &transport->transmitted, transport,
  997. highest_new_tsn, count_of_newacks);
  998. }
  999. /* Move the Cumulative TSN Ack Point if appropriate. */
  1000. if (TSN_lt(asoc->ctsn_ack_point, sack_ctsn))
  1001. asoc->ctsn_ack_point = sack_ctsn;
  1002. /* Update unack_data field in the assoc. */
  1003. sctp_sack_update_unack_data(asoc, sack);
  1004. ctsn = asoc->ctsn_ack_point;
  1005. /* Throw away stuff rotting on the sack queue. */
  1006. list_for_each_safe(lchunk, temp, &q->sacked) {
  1007. tchunk = list_entry(lchunk, struct sctp_chunk,
  1008. transmitted_list);
  1009. tsn = ntohl(tchunk->subh.data_hdr->tsn);
  1010. if (TSN_lte(tsn, ctsn))
  1011. sctp_chunk_free(tchunk);
  1012. }
  1013. /* ii) Set rwnd equal to the newly received a_rwnd minus the
  1014. * number of bytes still outstanding after processing the
  1015. * Cumulative TSN Ack and the Gap Ack Blocks.
  1016. */
  1017. sack_a_rwnd = ntohl(sack->a_rwnd);
  1018. outstanding = q->outstanding_bytes;
  1019. if (outstanding < sack_a_rwnd)
  1020. sack_a_rwnd -= outstanding;
  1021. else
  1022. sack_a_rwnd = 0;
  1023. asoc->peer.rwnd = sack_a_rwnd;
  1024. sctp_generate_fwdtsn(q, sack_ctsn);
  1025. SCTP_DEBUG_PRINTK("%s: sack Cumulative TSN Ack is 0x%x.\n",
  1026. __FUNCTION__, sack_ctsn);
  1027. SCTP_DEBUG_PRINTK("%s: Cumulative TSN Ack of association, "
  1028. "%p is 0x%x. Adv peer ack point: 0x%x\n",
  1029. __FUNCTION__, asoc, ctsn, asoc->adv_peer_ack_point);
  1030. /* See if all chunks are acked.
  1031. * Make sure the empty queue handler will get run later.
  1032. */
  1033. q->empty = (list_empty(&q->out_chunk_list) &&
  1034. list_empty(&q->control_chunk_list) &&
  1035. list_empty(&q->retransmit));
  1036. if (!q->empty)
  1037. goto finish;
  1038. list_for_each(pos, transport_list) {
  1039. transport = list_entry(pos, struct sctp_transport,
  1040. transports);
  1041. q->empty = q->empty && list_empty(&transport->transmitted);
  1042. if (!q->empty)
  1043. goto finish;
  1044. }
  1045. SCTP_DEBUG_PRINTK("sack queue is empty.\n");
  1046. finish:
  1047. return q->empty;
  1048. }
  1049. /* Is the outqueue empty? */
  1050. int sctp_outq_is_empty(const struct sctp_outq *q)
  1051. {
  1052. return q->empty;
  1053. }
  1054. /********************************************************************
  1055. * 2nd Level Abstractions
  1056. ********************************************************************/
  1057. /* Go through a transport's transmitted list or the association's retransmit
  1058. * list and move chunks that are acked by the Cumulative TSN Ack to q->sacked.
  1059. * The retransmit list will not have an associated transport.
  1060. *
  1061. * I added coherent debug information output. --xguo
  1062. *
  1063. * Instead of printing 'sacked' or 'kept' for each TSN on the
  1064. * transmitted_queue, we print a range: SACKED: TSN1-TSN2, TSN3, TSN4-TSN5.
  1065. * KEPT TSN6-TSN7, etc.
  1066. */
  1067. static void sctp_check_transmitted(struct sctp_outq *q,
  1068. struct list_head *transmitted_queue,
  1069. struct sctp_transport *transport,
  1070. struct sctp_sackhdr *sack,
  1071. __u32 highest_new_tsn_in_sack)
  1072. {
  1073. struct list_head *lchunk;
  1074. struct sctp_chunk *tchunk;
  1075. struct list_head tlist;
  1076. __u32 tsn;
  1077. __u32 sack_ctsn;
  1078. __u32 rtt;
  1079. __u8 restart_timer = 0;
  1080. int bytes_acked = 0;
  1081. /* These state variables are for coherent debug output. --xguo */
  1082. #if SCTP_DEBUG
  1083. __u32 dbg_ack_tsn = 0; /* An ACKed TSN range starts here... */
  1084. __u32 dbg_last_ack_tsn = 0; /* ...and finishes here. */
  1085. __u32 dbg_kept_tsn = 0; /* An un-ACKed range starts here... */
  1086. __u32 dbg_last_kept_tsn = 0; /* ...and finishes here. */
  1087. /* 0 : The last TSN was ACKed.
  1088. * 1 : The last TSN was NOT ACKed (i.e. KEPT).
  1089. * -1: We need to initialize.
  1090. */
  1091. int dbg_prt_state = -1;
  1092. #endif /* SCTP_DEBUG */
  1093. sack_ctsn = ntohl(sack->cum_tsn_ack);
  1094. INIT_LIST_HEAD(&tlist);
  1095. /* The while loop will skip empty transmitted queues. */
  1096. while (NULL != (lchunk = sctp_list_dequeue(transmitted_queue))) {
  1097. tchunk = list_entry(lchunk, struct sctp_chunk,
  1098. transmitted_list);
  1099. if (sctp_chunk_abandoned(tchunk)) {
  1100. /* Move the chunk to abandoned list. */
  1101. sctp_insert_list(&q->abandoned, lchunk);
  1102. /* If this chunk has not been acked, stop
  1103. * considering it as 'outstanding'.
  1104. */
  1105. if (!tchunk->tsn_gap_acked) {
  1106. tchunk->transport->flight_size -=
  1107. sctp_data_size(tchunk);
  1108. q->outstanding_bytes -= sctp_data_size(tchunk);
  1109. }
  1110. continue;
  1111. }
  1112. tsn = ntohl(tchunk->subh.data_hdr->tsn);
  1113. if (sctp_acked(sack, tsn)) {
  1114. /* If this queue is the retransmit queue, the
  1115. * retransmit timer has already reclaimed
  1116. * the outstanding bytes for this chunk, so only
  1117. * count bytes associated with a transport.
  1118. */
  1119. if (transport) {
  1120. /* If this chunk is being used for RTT
  1121. * measurement, calculate the RTT and update
  1122. * the RTO using this value.
  1123. *
  1124. * 6.3.1 C5) Karn's algorithm: RTT measurements
  1125. * MUST NOT be made using packets that were
  1126. * retransmitted (and thus for which it is
  1127. * ambiguous whether the reply was for the
  1128. * first instance of the packet or a later
  1129. * instance).
  1130. */
  1131. if (!tchunk->tsn_gap_acked &&
  1132. !tchunk->resent &&
  1133. tchunk->rtt_in_progress) {
  1134. tchunk->rtt_in_progress = 0;
  1135. rtt = jiffies - tchunk->sent_at;
  1136. sctp_transport_update_rto(transport,
  1137. rtt);
  1138. }
  1139. }
  1140. if (TSN_lte(tsn, sack_ctsn)) {
  1141. /* RFC 2960 6.3.2 Retransmission Timer Rules
  1142. *
  1143. * R3) Whenever a SACK is received
  1144. * that acknowledges the DATA chunk
  1145. * with the earliest outstanding TSN
  1146. * for that address, restart T3-rtx
  1147. * timer for that address with its
  1148. * current RTO.
  1149. */
  1150. restart_timer = 1;
  1151. if (!tchunk->tsn_gap_acked) {
  1152. tchunk->tsn_gap_acked = 1;
  1153. bytes_acked += sctp_data_size(tchunk);
  1154. /*
  1155. * SFR-CACC algorithm:
  1156. * 2) If the SACK contains gap acks
  1157. * and the flag CHANGEOVER_ACTIVE is
  1158. * set the receiver of the SACK MUST
  1159. * take the following action:
  1160. *
  1161. * B) For each TSN t being acked that
  1162. * has not been acked in any SACK so
  1163. * far, set cacc_saw_newack to 1 for
  1164. * the destination that the TSN was
  1165. * sent to.
  1166. */
  1167. if (transport &&
  1168. sack->num_gap_ack_blocks &&
  1169. q->asoc->peer.primary_path->cacc.
  1170. changeover_active)
  1171. transport->cacc.cacc_saw_newack
  1172. = 1;
  1173. }
  1174. list_add_tail(&tchunk->transmitted_list,
  1175. &q->sacked);
  1176. } else {
  1177. /* RFC2960 7.2.4, sctpimpguide-05 2.8.2
  1178. * M2) Each time a SACK arrives reporting
  1179. * 'Stray DATA chunk(s)' record the highest TSN
  1180. * reported as newly acknowledged, call this
  1181. * value 'HighestTSNinSack'. A newly
  1182. * acknowledged DATA chunk is one not
  1183. * previously acknowledged in a SACK.
  1184. *
  1185. * When the SCTP sender of data receives a SACK
  1186. * chunk that acknowledges, for the first time,
  1187. * the receipt of a DATA chunk, all the still
  1188. * unacknowledged DATA chunks whose TSN is
  1189. * older than that newly acknowledged DATA
  1190. * chunk, are qualified as 'Stray DATA chunks'.
  1191. */
  1192. if (!tchunk->tsn_gap_acked) {
  1193. tchunk->tsn_gap_acked = 1;
  1194. bytes_acked += sctp_data_size(tchunk);
  1195. }
  1196. list_add_tail(lchunk, &tlist);
  1197. }
  1198. #if SCTP_DEBUG
  1199. switch (dbg_prt_state) {
  1200. case 0: /* last TSN was ACKed */
  1201. if (dbg_last_ack_tsn + 1 == tsn) {
  1202. /* This TSN belongs to the
  1203. * current ACK range.
  1204. */
  1205. break;
  1206. }
  1207. if (dbg_last_ack_tsn != dbg_ack_tsn) {
  1208. /* Display the end of the
  1209. * current range.
  1210. */
  1211. SCTP_DEBUG_PRINTK("-%08x",
  1212. dbg_last_ack_tsn);
  1213. }
  1214. /* Start a new range. */
  1215. SCTP_DEBUG_PRINTK(",%08x", tsn);
  1216. dbg_ack_tsn = tsn;
  1217. break;
  1218. case 1: /* The last TSN was NOT ACKed. */
  1219. if (dbg_last_kept_tsn != dbg_kept_tsn) {
  1220. /* Display the end of current range. */
  1221. SCTP_DEBUG_PRINTK("-%08x",
  1222. dbg_last_kept_tsn);
  1223. }
  1224. SCTP_DEBUG_PRINTK("\n");
  1225. /* FALL THROUGH... */
  1226. default:
  1227. /* This is the first-ever TSN we examined. */
  1228. /* Start a new range of ACK-ed TSNs. */
  1229. SCTP_DEBUG_PRINTK("ACKed: %08x", tsn);
  1230. dbg_prt_state = 0;
  1231. dbg_ack_tsn = tsn;
  1232. };
  1233. dbg_last_ack_tsn = tsn;
  1234. #endif /* SCTP_DEBUG */
  1235. } else {
  1236. if (tchunk->tsn_gap_acked) {
  1237. SCTP_DEBUG_PRINTK("%s: Receiver reneged on "
  1238. "data TSN: 0x%x\n",
  1239. __FUNCTION__,
  1240. tsn);
  1241. tchunk->tsn_gap_acked = 0;
  1242. bytes_acked -= sctp_data_size(tchunk);
  1243. /* RFC 2960 6.3.2 Retransmission Timer Rules
  1244. *
  1245. * R4) Whenever a SACK is received missing a
  1246. * TSN that was previously acknowledged via a
  1247. * Gap Ack Block, start T3-rtx for the
  1248. * destination address to which the DATA
  1249. * chunk was originally
  1250. * transmitted if it is not already running.
  1251. */
  1252. restart_timer = 1;
  1253. }
  1254. list_add_tail(lchunk, &tlist);
  1255. #if SCTP_DEBUG
  1256. /* See the above comments on ACK-ed TSNs. */
  1257. switch (dbg_prt_state) {
  1258. case 1:
  1259. if (dbg_last_kept_tsn + 1 == tsn)
  1260. break;
  1261. if (dbg_last_kept_tsn != dbg_kept_tsn)
  1262. SCTP_DEBUG_PRINTK("-%08x",
  1263. dbg_last_kept_tsn);
  1264. SCTP_DEBUG_PRINTK(",%08x", tsn);
  1265. dbg_kept_tsn = tsn;
  1266. break;
  1267. case 0:
  1268. if (dbg_last_ack_tsn != dbg_ack_tsn)
  1269. SCTP_DEBUG_PRINTK("-%08x",
  1270. dbg_last_ack_tsn);
  1271. SCTP_DEBUG_PRINTK("\n");
  1272. /* FALL THROUGH... */
  1273. default:
  1274. SCTP_DEBUG_PRINTK("KEPT: %08x",tsn);
  1275. dbg_prt_state = 1;
  1276. dbg_kept_tsn = tsn;
  1277. };
  1278. dbg_last_kept_tsn = tsn;
  1279. #endif /* SCTP_DEBUG */
  1280. }
  1281. }
  1282. #if SCTP_DEBUG
  1283. /* Finish off the last range, displaying its ending TSN. */
  1284. switch (dbg_prt_state) {
  1285. case 0:
  1286. if (dbg_last_ack_tsn != dbg_ack_tsn) {
  1287. SCTP_DEBUG_PRINTK("-%08x\n", dbg_last_ack_tsn);
  1288. } else {
  1289. SCTP_DEBUG_PRINTK("\n");
  1290. }
  1291. break;
  1292. case 1:
  1293. if (dbg_last_kept_tsn != dbg_kept_tsn) {
  1294. SCTP_DEBUG_PRINTK("-%08x\n", dbg_last_kept_tsn);
  1295. } else {
  1296. SCTP_DEBUG_PRINTK("\n");
  1297. }
  1298. };
  1299. #endif /* SCTP_DEBUG */
  1300. if (transport) {
  1301. if (bytes_acked) {
  1302. /* 8.2. When an outstanding TSN is acknowledged,
  1303. * the endpoint shall clear the error counter of
  1304. * the destination transport address to which the
  1305. * DATA chunk was last sent.
  1306. * The association's overall error counter is
  1307. * also cleared.
  1308. */
  1309. transport->error_count = 0;
  1310. transport->asoc->overall_error_count = 0;
  1311. /* Mark the destination transport address as
  1312. * active if it is not so marked.
  1313. */
  1314. if ((transport->state == SCTP_INACTIVE) ||
  1315. (transport->state == SCTP_UNCONFIRMED)) {
  1316. sctp_assoc_control_transport(
  1317. transport->asoc,
  1318. transport,
  1319. SCTP_TRANSPORT_UP,
  1320. SCTP_RECEIVED_SACK);
  1321. }
  1322. sctp_transport_raise_cwnd(transport, sack_ctsn,
  1323. bytes_acked);
  1324. transport->flight_size -= bytes_acked;
  1325. q->outstanding_bytes -= bytes_acked;
  1326. } else {
  1327. /* RFC 2960 6.1, sctpimpguide-06 2.15.2
  1328. * When a sender is doing zero window probing, it
  1329. * should not timeout the association if it continues
  1330. * to receive new packets from the receiver. The
  1331. * reason is that the receiver MAY keep its window
  1332. * closed for an indefinite time.
  1333. * A sender is doing zero window probing when the
  1334. * receiver's advertised window is zero, and there is
  1335. * only one data chunk in flight to the receiver.
  1336. */
  1337. if (!q->asoc->peer.rwnd &&
  1338. !list_empty(&tlist) &&
  1339. (sack_ctsn+2 == q->asoc->next_tsn)) {
  1340. SCTP_DEBUG_PRINTK("%s: SACK received for zero "
  1341. "window probe: %u\n",
  1342. __FUNCTION__, sack_ctsn);
  1343. q->asoc->overall_error_count = 0;
  1344. transport->error_count = 0;
  1345. }
  1346. }
  1347. /* RFC 2960 6.3.2 Retransmission Timer Rules
  1348. *
  1349. * R2) Whenever all outstanding data sent to an address have
  1350. * been acknowledged, turn off the T3-rtx timer of that
  1351. * address.
  1352. */
  1353. if (!transport->flight_size) {
  1354. if (timer_pending(&transport->T3_rtx_timer) &&
  1355. del_timer(&transport->T3_rtx_timer)) {
  1356. sctp_transport_put(transport);
  1357. }
  1358. } else if (restart_timer) {
  1359. if (!mod_timer(&transport->T3_rtx_timer,
  1360. jiffies + transport->rto))
  1361. sctp_transport_hold(transport);
  1362. }
  1363. }
  1364. list_splice(&tlist, transmitted_queue);
  1365. }
  1366. /* Mark chunks as missing and consequently may get retransmitted. */
  1367. static void sctp_mark_missing(struct sctp_outq *q,
  1368. struct list_head *transmitted_queue,
  1369. struct sctp_transport *transport,
  1370. __u32 highest_new_tsn_in_sack,
  1371. int count_of_newacks)
  1372. {
  1373. struct sctp_chunk *chunk;
  1374. struct list_head *pos;
  1375. __u32 tsn;
  1376. char do_fast_retransmit = 0;
  1377. struct sctp_transport *primary = q->asoc->peer.primary_path;
  1378. list_for_each(pos, transmitted_queue) {
  1379. chunk = list_entry(pos, struct sctp_chunk, transmitted_list);
  1380. tsn = ntohl(chunk->subh.data_hdr->tsn);
  1381. /* RFC 2960 7.2.4, sctpimpguide-05 2.8.2 M3) Examine all
  1382. * 'Unacknowledged TSN's', if the TSN number of an
  1383. * 'Unacknowledged TSN' is smaller than the 'HighestTSNinSack'
  1384. * value, increment the 'TSN.Missing.Report' count on that
  1385. * chunk if it has NOT been fast retransmitted or marked for
  1386. * fast retransmit already.
  1387. */
  1388. if (!chunk->fast_retransmit &&
  1389. !chunk->tsn_gap_acked &&
  1390. TSN_lt(tsn, highest_new_tsn_in_sack)) {
  1391. /* SFR-CACC may require us to skip marking
  1392. * this chunk as missing.
  1393. */
  1394. if (!transport || !sctp_cacc_skip(primary, transport,
  1395. count_of_newacks, tsn)) {
  1396. chunk->tsn_missing_report++;
  1397. SCTP_DEBUG_PRINTK(
  1398. "%s: TSN 0x%x missing counter: %d\n",
  1399. __FUNCTION__, tsn,
  1400. chunk->tsn_missing_report);
  1401. }
  1402. }
  1403. /*
  1404. * M4) If any DATA chunk is found to have a
  1405. * 'TSN.Missing.Report'
  1406. * value larger than or equal to 3, mark that chunk for
  1407. * retransmission and start the fast retransmit procedure.
  1408. */
  1409. if (chunk->tsn_missing_report >= 3) {
  1410. chunk->fast_retransmit = 1;
  1411. do_fast_retransmit = 1;
  1412. }
  1413. }
  1414. if (transport) {
  1415. if (do_fast_retransmit)
  1416. sctp_retransmit(q, transport, SCTP_RTXR_FAST_RTX);
  1417. SCTP_DEBUG_PRINTK("%s: transport: %p, cwnd: %d, "
  1418. "ssthresh: %d, flight_size: %d, pba: %d\n",
  1419. __FUNCTION__, transport, transport->cwnd,
  1420. transport->ssthresh, transport->flight_size,
  1421. transport->partial_bytes_acked);
  1422. }
  1423. }
  1424. /* Is the given TSN acked by this packet? */
  1425. static int sctp_acked(struct sctp_sackhdr *sack, __u32 tsn)
  1426. {
  1427. int i;
  1428. sctp_sack_variable_t *frags;
  1429. __u16 gap;
  1430. __u32 ctsn = ntohl(sack->cum_tsn_ack);
  1431. if (TSN_lte(tsn, ctsn))
  1432. goto pass;
  1433. /* 3.3.4 Selective Acknowledgement (SACK) (3):
  1434. *
  1435. * Gap Ack Blocks:
  1436. * These fields contain the Gap Ack Blocks. They are repeated
  1437. * for each Gap Ack Block up to the number of Gap Ack Blocks
  1438. * defined in the Number of Gap Ack Blocks field. All DATA
  1439. * chunks with TSNs greater than or equal to (Cumulative TSN
  1440. * Ack + Gap Ack Block Start) and less than or equal to
  1441. * (Cumulative TSN Ack + Gap Ack Block End) of each Gap Ack
  1442. * Block are assumed to have been received correctly.
  1443. */
  1444. frags = sack->variable;
  1445. gap = tsn - ctsn;
  1446. for (i = 0; i < ntohs(sack->num_gap_ack_blocks); ++i) {
  1447. if (TSN_lte(ntohs(frags[i].gab.start), gap) &&
  1448. TSN_lte(gap, ntohs(frags[i].gab.end)))
  1449. goto pass;
  1450. }
  1451. return 0;
  1452. pass:
  1453. return 1;
  1454. }
  1455. static inline int sctp_get_skip_pos(struct sctp_fwdtsn_skip *skiplist,
  1456. int nskips, __be16 stream)
  1457. {
  1458. int i;
  1459. for (i = 0; i < nskips; i++) {
  1460. if (skiplist[i].stream == stream)
  1461. return i;
  1462. }
  1463. return i;
  1464. }
  1465. /* Create and add a fwdtsn chunk to the outq's control queue if needed. */
  1466. static void sctp_generate_fwdtsn(struct sctp_outq *q, __u32 ctsn)
  1467. {
  1468. struct sctp_association *asoc = q->asoc;
  1469. struct sctp_chunk *ftsn_chunk = NULL;
  1470. struct sctp_fwdtsn_skip ftsn_skip_arr[10];
  1471. int nskips = 0;
  1472. int skip_pos = 0;
  1473. __u32 tsn;
  1474. struct sctp_chunk *chunk;
  1475. struct list_head *lchunk, *temp;
  1476. /* PR-SCTP C1) Let SackCumAck be the Cumulative TSN ACK carried in the
  1477. * received SACK.
  1478. *
  1479. * If (Advanced.Peer.Ack.Point < SackCumAck), then update
  1480. * Advanced.Peer.Ack.Point to be equal to SackCumAck.
  1481. */
  1482. if (TSN_lt(asoc->adv_peer_ack_point, ctsn))
  1483. asoc->adv_peer_ack_point = ctsn;
  1484. /* PR-SCTP C2) Try to further advance the "Advanced.Peer.Ack.Point"
  1485. * locally, that is, to move "Advanced.Peer.Ack.Point" up as long as
  1486. * the chunk next in the out-queue space is marked as "abandoned" as
  1487. * shown in the following example:
  1488. *
  1489. * Assuming that a SACK arrived with the Cumulative TSN ACK 102
  1490. * and the Advanced.Peer.Ack.Point is updated to this value:
  1491. *
  1492. * out-queue at the end of ==> out-queue after Adv.Ack.Point
  1493. * normal SACK processing local advancement
  1494. * ... ...
  1495. * Adv.Ack.Pt-> 102 acked 102 acked
  1496. * 103 abandoned 103 abandoned
  1497. * 104 abandoned Adv.Ack.P-> 104 abandoned
  1498. * 105 105
  1499. * 106 acked 106 acked
  1500. * ... ...
  1501. *
  1502. * In this example, the data sender successfully advanced the
  1503. * "Advanced.Peer.Ack.Point" from 102 to 104 locally.
  1504. */
  1505. list_for_each_safe(lchunk, temp, &q->abandoned) {
  1506. chunk = list_entry(lchunk, struct sctp_chunk,
  1507. transmitted_list);
  1508. tsn = ntohl(chunk->subh.data_hdr->tsn);
  1509. /* Remove any chunks in the abandoned queue that are acked by
  1510. * the ctsn.
  1511. */
  1512. if (TSN_lte(tsn, ctsn)) {
  1513. list_del_init(lchunk);
  1514. sctp_chunk_free(chunk);
  1515. } else {
  1516. if (TSN_lte(tsn, asoc->adv_peer_ack_point+1)) {
  1517. asoc->adv_peer_ack_point = tsn;
  1518. if (chunk->chunk_hdr->flags &
  1519. SCTP_DATA_UNORDERED)
  1520. continue;
  1521. skip_pos = sctp_get_skip_pos(&ftsn_skip_arr[0],
  1522. nskips,
  1523. chunk->subh.data_hdr->stream);
  1524. ftsn_skip_arr[skip_pos].stream =
  1525. chunk->subh.data_hdr->stream;
  1526. ftsn_skip_arr[skip_pos].ssn =
  1527. chunk->subh.data_hdr->ssn;
  1528. if (skip_pos == nskips)
  1529. nskips++;
  1530. if (nskips == 10)
  1531. break;
  1532. } else
  1533. break;
  1534. }
  1535. }
  1536. /* PR-SCTP C3) If, after step C1 and C2, the "Advanced.Peer.Ack.Point"
  1537. * is greater than the Cumulative TSN ACK carried in the received
  1538. * SACK, the data sender MUST send the data receiver a FORWARD TSN
  1539. * chunk containing the latest value of the
  1540. * "Advanced.Peer.Ack.Point".
  1541. *
  1542. * C4) For each "abandoned" TSN the sender of the FORWARD TSN SHOULD
  1543. * list each stream and sequence number in the forwarded TSN. This
  1544. * information will enable the receiver to easily find any
  1545. * stranded TSN's waiting on stream reorder queues. Each stream
  1546. * SHOULD only be reported once; this means that if multiple
  1547. * abandoned messages occur in the same stream then only the
  1548. * highest abandoned stream sequence number is reported. If the
  1549. * total size of the FORWARD TSN does NOT fit in a single MTU then
  1550. * the sender of the FORWARD TSN SHOULD lower the
  1551. * Advanced.Peer.Ack.Point to the last TSN that will fit in a
  1552. * single MTU.
  1553. */
  1554. if (asoc->adv_peer_ack_point > ctsn)
  1555. ftsn_chunk = sctp_make_fwdtsn(asoc, asoc->adv_peer_ack_point,
  1556. nskips, &ftsn_skip_arr[0]);
  1557. if (ftsn_chunk) {
  1558. list_add_tail(&ftsn_chunk->list, &q->control_chunk_list);
  1559. SCTP_INC_STATS(SCTP_MIB_OUTCTRLCHUNKS);
  1560. }
  1561. }