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