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