blob: ace6770e9048a69fb613e16b04e601f5ff5e2d0b [file] [log] [blame]
Vlad Yasevich60c778b2008-01-11 09:57:09 -05001/* SCTP kernel implementation
Linus Torvalds1da177e2005-04-16 15:20:36 -07002 * (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 *
Vlad Yasevich60c778b2008-01-11 09:57:09 -05007 * This file is part of the SCTP kernel implementation
Linus Torvalds1da177e2005-04-16 15:20:36 -07008 *
9 * These functions implement the sctp_outq class. The outqueue handles
10 * bundling and queueing of outgoing SCTP chunks.
11 *
Vlad Yasevich60c778b2008-01-11 09:57:09 -050012 * This SCTP implementation is free software;
Linus Torvalds1da177e2005-04-16 15:20:36 -070013 * 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 *
Vlad Yasevich60c778b2008-01-11 09:57:09 -050018 * This SCTP implementation is distributed in the hope that it
Linus Torvalds1da177e2005-04-16 15:20:36 -070019 * 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{
David S. Miller79af02c2005-07-08 21:47:49 -070078 list_add(&ch->list, &q->out_chunk_list);
Linus Torvalds1da177e2005-04-16 15:20:36 -070079 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{
David S. Miller79af02c2005-07-08 21:47:49 -070086 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);
Linus Torvalds1da177e2005-04-16 15:20:36 -070093 q->out_qlen -= ch->skb->len;
David S. Miller79af02c2005-07-08 21:47:49 -070094 }
Linus Torvalds1da177e2005-04-16 15:20:36 -070095 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{
David S. Miller79af02c2005-07-08 21:47:49 -0700101 list_add_tail(&ch->list, &q->out_chunk_list);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700102 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;
David S. Miller79af02c2005-07-08 21:47:49 -0700205 INIT_LIST_HEAD(&q->out_chunk_list);
206 INIT_LIST_HEAD(&q->control_chunk_list);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700207 INIT_LIST_HEAD(&q->retransmit);
208 INIT_LIST_HEAD(&q->sacked);
209 INIT_LIST_HEAD(&q->abandoned);
210
Vlad Yasevich62aeaff2008-06-04 12:39:11 -0700211 q->fast_rtx = 0;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700212 q->outstanding_bytes = 0;
213 q->empty = 1;
214 q->cork = 0;
215
216 q->malloced = 0;
217 q->out_qlen = 0;
218}
219
220/* Free the outqueue structure and any related pending chunks.
221 */
222void sctp_outq_teardown(struct sctp_outq *q)
223{
224 struct sctp_transport *transport;
Robert P. J. Day9dbc15f2008-04-12 18:54:24 -0700225 struct list_head *lchunk, *temp;
David S. Miller79af02c2005-07-08 21:47:49 -0700226 struct sctp_chunk *chunk, *tmp;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700227
228 /* Throw away unacknowledged chunks. */
Robert P. J. Day9dbc15f2008-04-12 18:54:24 -0700229 list_for_each_entry(transport, &q->asoc->peer.transport_addr_list,
230 transports) {
Linus Torvalds1da177e2005-04-16 15:20:36 -0700231 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
270 /* Mark as send failure. */
271 sctp_chunk_fail(chunk, q->error);
272 sctp_chunk_free(chunk);
273 }
274
275 q->error = 0;
276
277 /* Throw away any leftover control chunks. */
David S. Miller79af02c2005-07-08 21:47:49 -0700278 list_for_each_entry_safe(chunk, tmp, &q->control_chunk_list, list) {
279 list_del_init(&chunk->list);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700280 sctp_chunk_free(chunk);
David S. Miller79af02c2005-07-08 21:47:49 -0700281 }
Linus Torvalds1da177e2005-04-16 15:20:36 -0700282}
283
284/* Free the outqueue structure and any related pending chunks. */
285void sctp_outq_free(struct sctp_outq *q)
286{
287 /* Throw away leftover chunks. */
288 sctp_outq_teardown(q);
289
290 /* If we were kmalloc()'d, free the memory. */
291 if (q->malloced)
292 kfree(q);
293}
294
295/* Put a new chunk in an sctp_outq. */
296int sctp_outq_tail(struct sctp_outq *q, struct sctp_chunk *chunk)
297{
298 int error = 0;
299
300 SCTP_DEBUG_PRINTK("sctp_outq_tail(%p, %p[%s])\n",
301 q, chunk, chunk && chunk->chunk_hdr ?
302 sctp_cname(SCTP_ST_CHUNK(chunk->chunk_hdr->type))
303 : "Illegal Chunk");
304
305 /* If it is data, queue it up, otherwise, send it
306 * immediately.
307 */
308 if (SCTP_CID_DATA == chunk->chunk_hdr->type) {
309 /* Is it OK to queue data chunks? */
310 /* From 9. Termination of Association
311 *
312 * When either endpoint performs a shutdown, the
313 * association on each peer will stop accepting new
314 * data from its user and only deliver data in queue
315 * at the time of sending or receiving the SHUTDOWN
316 * chunk.
317 */
318 switch (q->asoc->state) {
319 case SCTP_STATE_EMPTY:
320 case SCTP_STATE_CLOSED:
321 case SCTP_STATE_SHUTDOWN_PENDING:
322 case SCTP_STATE_SHUTDOWN_SENT:
323 case SCTP_STATE_SHUTDOWN_RECEIVED:
324 case SCTP_STATE_SHUTDOWN_ACK_SENT:
325 /* Cannot send after transport endpoint shutdown */
326 error = -ESHUTDOWN;
327 break;
328
329 default:
330 SCTP_DEBUG_PRINTK("outqueueing (%p, %p[%s])\n",
331 q, chunk, chunk && chunk->chunk_hdr ?
332 sctp_cname(SCTP_ST_CHUNK(chunk->chunk_hdr->type))
333 : "Illegal Chunk");
334
335 sctp_outq_tail_data(q, chunk);
336 if (chunk->chunk_hdr->flags & SCTP_DATA_UNORDERED)
337 SCTP_INC_STATS(SCTP_MIB_OUTUNORDERCHUNKS);
338 else
339 SCTP_INC_STATS(SCTP_MIB_OUTORDERCHUNKS);
340 q->empty = 0;
341 break;
Stephen Hemminger3ff50b72007-04-20 17:09:22 -0700342 }
Linus Torvalds1da177e2005-04-16 15:20:36 -0700343 } else {
David S. Miller79af02c2005-07-08 21:47:49 -0700344 list_add_tail(&chunk->list, &q->control_chunk_list);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700345 SCTP_INC_STATS(SCTP_MIB_OUTCTRLCHUNKS);
346 }
347
348 if (error < 0)
349 return error;
350
351 if (!q->cork)
352 error = sctp_outq_flush(q, 0);
353
354 return error;
355}
356
357/* Insert a chunk into the sorted list based on the TSNs. The retransmit list
358 * and the abandoned list are in ascending order.
359 */
360static void sctp_insert_list(struct list_head *head, struct list_head *new)
361{
362 struct list_head *pos;
363 struct sctp_chunk *nchunk, *lchunk;
364 __u32 ntsn, ltsn;
365 int done = 0;
366
367 nchunk = list_entry(new, struct sctp_chunk, transmitted_list);
368 ntsn = ntohl(nchunk->subh.data_hdr->tsn);
369
370 list_for_each(pos, head) {
371 lchunk = list_entry(pos, struct sctp_chunk, transmitted_list);
372 ltsn = ntohl(lchunk->subh.data_hdr->tsn);
373 if (TSN_lt(ntsn, ltsn)) {
374 list_add(new, pos->prev);
375 done = 1;
376 break;
377 }
378 }
379 if (!done)
YOSHIFUJI Hideakid808ad92007-02-09 23:25:18 +0900380 list_add_tail(new, head);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700381}
382
383/* Mark all the eligible packets on a transport for retransmission. */
384void sctp_retransmit_mark(struct sctp_outq *q,
385 struct sctp_transport *transport,
Vlad Yasevichb6157d82007-10-24 15:59:16 -0400386 __u8 reason)
Linus Torvalds1da177e2005-04-16 15:20:36 -0700387{
388 struct list_head *lchunk, *ltemp;
389 struct sctp_chunk *chunk;
390
391 /* Walk through the specified transmitted queue. */
392 list_for_each_safe(lchunk, ltemp, &transport->transmitted) {
393 chunk = list_entry(lchunk, struct sctp_chunk,
394 transmitted_list);
395
396 /* If the chunk is abandoned, move it to abandoned list. */
397 if (sctp_chunk_abandoned(chunk)) {
398 list_del_init(lchunk);
399 sctp_insert_list(&q->abandoned, lchunk);
Vlad Yasevich8c4a2d42007-02-21 02:06:04 -0800400
401 /* If this chunk has not been previousely acked,
402 * stop considering it 'outstanding'. Our peer
403 * will most likely never see it since it will
404 * not be retransmitted
405 */
406 if (!chunk->tsn_gap_acked) {
407 chunk->transport->flight_size -=
408 sctp_data_size(chunk);
409 q->outstanding_bytes -= sctp_data_size(chunk);
410 q->asoc->peer.rwnd += (sctp_data_size(chunk) +
411 sizeof(struct sk_buff));
412 }
Linus Torvalds1da177e2005-04-16 15:20:36 -0700413 continue;
414 }
415
Vlad Yasevichb6157d82007-10-24 15:59:16 -0400416 /* If we are doing retransmission due to a timeout or pmtu
417 * discovery, only the chunks that are not yet acked should
418 * be added to the retransmit queue.
Linus Torvalds1da177e2005-04-16 15:20:36 -0700419 */
Vlad Yasevichb6157d82007-10-24 15:59:16 -0400420 if ((reason == SCTP_RTXR_FAST_RTX &&
421 (chunk->fast_retransmit > 0)) ||
422 (reason != SCTP_RTXR_FAST_RTX && !chunk->tsn_gap_acked)) {
Vlad Yasevichd0ce9292007-08-24 19:37:46 +0900423 /* If this chunk was sent less then 1 rto ago, do not
424 * retransmit this chunk, but give the peer time
Vlad Yasevichb6157d82007-10-24 15:59:16 -0400425 * to acknowlege it. Do this only when
426 * retransmitting due to T3 timeout.
Vlad Yasevichd0ce9292007-08-24 19:37:46 +0900427 */
Vlad Yasevichb6157d82007-10-24 15:59:16 -0400428 if (reason == SCTP_RTXR_T3_RTX &&
429 (jiffies - chunk->sent_at) < transport->last_rto)
Vlad Yasevichd0ce9292007-08-24 19:37:46 +0900430 continue;
431
Linus Torvalds1da177e2005-04-16 15:20:36 -0700432 /* RFC 2960 6.2.1 Processing a Received SACK
433 *
434 * C) Any time a DATA chunk is marked for
435 * retransmission (via either T3-rtx timer expiration
436 * (Section 6.3.3) or via fast retransmit
437 * (Section 7.2.4)), add the data size of those
438 * chunks to the rwnd.
439 */
Sridhar Samudralacd497882006-09-29 17:09:05 -0700440 q->asoc->peer.rwnd += (sctp_data_size(chunk) +
441 sizeof(struct sk_buff));
Linus Torvalds1da177e2005-04-16 15:20:36 -0700442 q->outstanding_bytes -= sctp_data_size(chunk);
443 transport->flight_size -= sctp_data_size(chunk);
444
445 /* sctpimpguide-05 Section 2.8.2
446 * M5) If a T3-rtx timer expires, the
447 * 'TSN.Missing.Report' of all affected TSNs is set
448 * to 0.
449 */
450 chunk->tsn_missing_report = 0;
451
452 /* If a chunk that is being used for RTT measurement
453 * has to be retransmitted, we cannot use this chunk
454 * anymore for RTT measurements. Reset rto_pending so
455 * that a new RTT measurement is started when a new
456 * data chunk is sent.
457 */
458 if (chunk->rtt_in_progress) {
459 chunk->rtt_in_progress = 0;
460 transport->rto_pending = 0;
461 }
462
463 /* Move the chunk to the retransmit queue. The chunks
464 * on the retransmit queue are always kept in order.
465 */
466 list_del_init(lchunk);
467 sctp_insert_list(&q->retransmit, lchunk);
468 }
469 }
470
Vlad Yasevichb6157d82007-10-24 15:59:16 -0400471 SCTP_DEBUG_PRINTK("%s: transport: %p, reason: %d, "
Linus Torvalds1da177e2005-04-16 15:20:36 -0700472 "cwnd: %d, ssthresh: %d, flight_size: %d, "
Harvey Harrison0dc47872008-03-05 20:47:47 -0800473 "pba: %d\n", __func__,
Vlad Yasevichb6157d82007-10-24 15:59:16 -0400474 transport, reason,
Linus Torvalds1da177e2005-04-16 15:20:36 -0700475 transport->cwnd, transport->ssthresh,
476 transport->flight_size,
477 transport->partial_bytes_acked);
478
479}
480
481/* Mark all the eligible packets on a transport for retransmission and force
482 * one packet out.
483 */
484void sctp_retransmit(struct sctp_outq *q, struct sctp_transport *transport,
485 sctp_retransmit_reason_t reason)
486{
487 int error = 0;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700488
489 switch(reason) {
490 case SCTP_RTXR_T3_RTX:
Sridhar Samudralaac0b0462006-08-22 00:15:33 -0700491 SCTP_INC_STATS(SCTP_MIB_T3_RETRANSMITS);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700492 sctp_transport_lower_cwnd(transport, SCTP_LOWER_CWND_T3_RTX);
493 /* Update the retran path if the T3-rtx timer has expired for
494 * the current retran path.
495 */
496 if (transport == transport->asoc->peer.retran_path)
497 sctp_assoc_update_retran_path(transport->asoc);
Neil Horman58fbbed2008-02-29 11:40:56 -0800498 transport->asoc->rtx_data_chunks +=
499 transport->asoc->unack_data;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700500 break;
501 case SCTP_RTXR_FAST_RTX:
Sridhar Samudralaac0b0462006-08-22 00:15:33 -0700502 SCTP_INC_STATS(SCTP_MIB_FAST_RETRANSMITS);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700503 sctp_transport_lower_cwnd(transport, SCTP_LOWER_CWND_FAST_RTX);
Vlad Yasevich62aeaff2008-06-04 12:39:11 -0700504 q->fast_rtx = 1;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700505 break;
506 case SCTP_RTXR_PMTUD:
Sridhar Samudralaac0b0462006-08-22 00:15:33 -0700507 SCTP_INC_STATS(SCTP_MIB_PMTUD_RETRANSMITS);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700508 break;
Vlad Yasevichb6157d82007-10-24 15:59:16 -0400509 case SCTP_RTXR_T1_RTX:
510 SCTP_INC_STATS(SCTP_MIB_T1_RETRANSMITS);
Neil Horman58fbbed2008-02-29 11:40:56 -0800511 transport->asoc->init_retries++;
Vlad Yasevichb6157d82007-10-24 15:59:16 -0400512 break;
Sridhar Samudralaac0b0462006-08-22 00:15:33 -0700513 default:
514 BUG();
Linus Torvalds1da177e2005-04-16 15:20:36 -0700515 }
516
Vlad Yasevichb6157d82007-10-24 15:59:16 -0400517 sctp_retransmit_mark(q, transport, reason);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700518
519 /* PR-SCTP A5) Any time the T3-rtx timer expires, on any destination,
520 * the sender SHOULD try to advance the "Advanced.Peer.Ack.Point" by
521 * following the procedures outlined in C1 - C5.
522 */
Vlad Yasevich8b750ce2008-06-04 12:39:36 -0700523 if (reason == SCTP_RTXR_T3_RTX)
524 sctp_generate_fwdtsn(q, q->asoc->ctsn_ack_point);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700525
Vlad Yasevich8b750ce2008-06-04 12:39:36 -0700526 /* Flush the queues only on timeout, since fast_rtx is only
527 * triggered during sack processing and the queue
528 * will be flushed at the end.
529 */
530 if (reason != SCTP_RTXR_FAST_RTX)
531 error = sctp_outq_flush(q, /* rtx_timeout */ 1);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700532
533 if (error)
534 q->asoc->base.sk->sk_err = -error;
535}
536
537/*
538 * Transmit DATA chunks on the retransmit queue. Upon return from
539 * sctp_outq_flush_rtx() the packet 'pkt' may contain chunks which
540 * need to be transmitted by the caller.
541 * We assume that pkt->transport has already been set.
542 *
543 * The return value is a normal kernel error return value.
544 */
545static int sctp_outq_flush_rtx(struct sctp_outq *q, struct sctp_packet *pkt,
546 int rtx_timeout, int *start_timer)
547{
548 struct list_head *lqueue;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700549 struct sctp_transport *transport = pkt->transport;
550 sctp_xmit_t status;
551 struct sctp_chunk *chunk, *chunk1;
552 struct sctp_association *asoc;
Vlad Yasevich62aeaff2008-06-04 12:39:11 -0700553 int fast_rtx;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700554 int error = 0;
Vlad Yasevich62aeaff2008-06-04 12:39:11 -0700555 int timer = 0;
Vlad Yasevich8b750ce2008-06-04 12:39:36 -0700556 int done = 0;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700557
558 asoc = q->asoc;
559 lqueue = &q->retransmit;
Vlad Yasevich62aeaff2008-06-04 12:39:11 -0700560 fast_rtx = q->fast_rtx;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700561
Vlad Yasevich8b750ce2008-06-04 12:39:36 -0700562 /* This loop handles time-out retransmissions, fast retransmissions,
563 * and retransmissions due to opening of whindow.
564 *
565 * RFC 2960 6.3.3 Handle T3-rtx Expiration
Linus Torvalds1da177e2005-04-16 15:20:36 -0700566 *
567 * E3) Determine how many of the earliest (i.e., lowest TSN)
568 * outstanding DATA chunks for the address for which the
569 * T3-rtx has expired will fit into a single packet, subject
570 * to the MTU constraint for the path corresponding to the
571 * destination transport address to which the retransmission
572 * is being sent (this may be different from the address for
573 * which the timer expires [see Section 6.4]). Call this value
574 * K. Bundle and retransmit those K DATA chunks in a single
575 * packet to the destination endpoint.
576 *
577 * [Just to be painfully clear, if we are retransmitting
578 * because a timeout just happened, we should send only ONE
579 * packet of retransmitted data.]
Vlad Yasevich8b750ce2008-06-04 12:39:36 -0700580 *
581 * For fast retransmissions we also send only ONE packet. However,
582 * if we are just flushing the queue due to open window, we'll
583 * try to send as much as possible.
Linus Torvalds1da177e2005-04-16 15:20:36 -0700584 */
Vlad Yasevich8b750ce2008-06-04 12:39:36 -0700585 list_for_each_entry_safe(chunk, chunk1, lqueue, transmitted_list) {
Linus Torvalds1da177e2005-04-16 15:20:36 -0700586
587 /* Make sure that Gap Acked TSNs are not retransmitted. A
588 * simple approach is just to move such TSNs out of the
589 * way and into a 'transmitted' queue and skip to the
590 * next chunk.
591 */
592 if (chunk->tsn_gap_acked) {
Vlad Yasevich8b750ce2008-06-04 12:39:36 -0700593 list_del(&chunk->transmitted_list);
594 list_add_tail(&chunk->transmitted_list,
595 &transport->transmitted);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700596 continue;
597 }
598
Vlad Yasevich8b750ce2008-06-04 12:39:36 -0700599 /* If we are doing fast retransmit, ignore non-fast_rtransmit
600 * chunks
601 */
602 if (fast_rtx && !chunk->fast_retransmit)
603 continue;
604
Linus Torvalds1da177e2005-04-16 15:20:36 -0700605 /* Attempt to append this chunk to the packet. */
606 status = sctp_packet_append_chunk(pkt, chunk);
607
608 switch (status) {
609 case SCTP_XMIT_PMTU_FULL:
610 /* Send this packet. */
Vlad Yasevich62aeaff2008-06-04 12:39:11 -0700611 error = sctp_packet_transmit(pkt);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700612
613 /* If we are retransmitting, we should only
614 * send a single packet.
615 */
Vlad Yasevich8b750ce2008-06-04 12:39:36 -0700616 if (rtx_timeout || fast_rtx)
617 done = 1;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700618
Vlad Yasevich8b750ce2008-06-04 12:39:36 -0700619 /* Bundle next chunk in the next round. */
Linus Torvalds1da177e2005-04-16 15:20:36 -0700620 break;
621
622 case SCTP_XMIT_RWND_FULL:
YOSHIFUJI Hideakid808ad92007-02-09 23:25:18 +0900623 /* Send this packet. */
Vlad Yasevich62aeaff2008-06-04 12:39:11 -0700624 error = sctp_packet_transmit(pkt);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700625
626 /* Stop sending DATA as there is no more room
627 * at the receiver.
628 */
Vlad Yasevich8b750ce2008-06-04 12:39:36 -0700629 done = 1;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700630 break;
631
632 case SCTP_XMIT_NAGLE_DELAY:
YOSHIFUJI Hideakid808ad92007-02-09 23:25:18 +0900633 /* Send this packet. */
Vlad Yasevich62aeaff2008-06-04 12:39:11 -0700634 error = sctp_packet_transmit(pkt);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700635
636 /* Stop sending DATA because of nagle delay. */
Vlad Yasevich8b750ce2008-06-04 12:39:36 -0700637 done = 1;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700638 break;
639
640 default:
641 /* The append was successful, so add this chunk to
642 * the transmitted list.
643 */
Vlad Yasevich8b750ce2008-06-04 12:39:36 -0700644 list_del(&chunk->transmitted_list);
645 list_add_tail(&chunk->transmitted_list,
646 &transport->transmitted);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700647
YOSHIFUJI Hideakid808ad92007-02-09 23:25:18 +0900648 /* Mark the chunk as ineligible for fast retransmit
Linus Torvalds1da177e2005-04-16 15:20:36 -0700649 * after it is retransmitted.
650 */
Vlad Yasevich27852c22006-02-02 16:57:31 -0800651 if (chunk->fast_retransmit > 0)
652 chunk->fast_retransmit = -1;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700653
Vlad Yasevich62aeaff2008-06-04 12:39:11 -0700654 /* Force start T3-rtx timer when fast retransmitting
655 * the earliest outstanding TSN
656 */
657 if (!timer && fast_rtx &&
658 ntohl(chunk->subh.data_hdr->tsn) ==
659 asoc->ctsn_ack_point + 1)
660 timer = 2;
661
Linus Torvalds1da177e2005-04-16 15:20:36 -0700662 q->empty = 0;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700663 break;
Stephen Hemminger3ff50b72007-04-20 17:09:22 -0700664 }
Linus Torvalds1da177e2005-04-16 15:20:36 -0700665
Vlad Yasevich62aeaff2008-06-04 12:39:11 -0700666 /* Set the timer if there were no errors */
667 if (!error && !timer)
668 timer = 1;
669
Vlad Yasevich8b750ce2008-06-04 12:39:36 -0700670 if (done)
671 break;
672 }
673
674 /* If we are here due to a retransmit timeout or a fast
675 * retransmit and if there are any chunks left in the retransmit
676 * queue that could not fit in the PMTU sized packet, they need
677 * to be marked as ineligible for a subsequent fast retransmit.
678 */
679 if (rtx_timeout || fast_rtx) {
680 list_for_each_entry(chunk1, lqueue, transmitted_list) {
681 if (chunk1->fast_retransmit > 0)
682 chunk1->fast_retransmit = -1;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700683 }
684 }
685
Vlad Yasevich62aeaff2008-06-04 12:39:11 -0700686 *start_timer = timer;
687
688 /* Clear fast retransmit hint */
689 if (fast_rtx)
690 q->fast_rtx = 0;
691
Linus Torvalds1da177e2005-04-16 15:20:36 -0700692 return error;
693}
694
695/* Cork the outqueue so queued chunks are really queued. */
696int sctp_outq_uncork(struct sctp_outq *q)
697{
698 int error = 0;
Vlad Yasevich7d54dc62007-11-09 11:43:41 -0500699 if (q->cork)
Linus Torvalds1da177e2005-04-16 15:20:36 -0700700 q->cork = 0;
Vlad Yasevich7d54dc62007-11-09 11:43:41 -0500701 error = sctp_outq_flush(q, 0);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700702 return error;
703}
704
705/*
706 * Try to flush an outqueue.
707 *
708 * Description: Send everything in q which we legally can, subject to
709 * congestion limitations.
710 * * Note: This function can be called from multiple contexts so appropriate
711 * locking concerns must be made. Today we use the sock lock to protect
712 * this function.
713 */
714int sctp_outq_flush(struct sctp_outq *q, int rtx_timeout)
715{
716 struct sctp_packet *packet;
717 struct sctp_packet singleton;
718 struct sctp_association *asoc = q->asoc;
719 __u16 sport = asoc->base.bind_addr.port;
720 __u16 dport = asoc->peer.port;
721 __u32 vtag = asoc->peer.i.init_tag;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700722 struct sctp_transport *transport = NULL;
723 struct sctp_transport *new_transport;
David S. Miller79af02c2005-07-08 21:47:49 -0700724 struct sctp_chunk *chunk, *tmp;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700725 sctp_xmit_t status;
726 int error = 0;
727 int start_timer = 0;
728
729 /* These transports have chunks to send. */
730 struct list_head transport_list;
731 struct list_head *ltransport;
732
733 INIT_LIST_HEAD(&transport_list);
734 packet = NULL;
735
736 /*
737 * 6.10 Bundling
738 * ...
739 * When bundling control chunks with DATA chunks, an
740 * endpoint MUST place control chunks first in the outbound
741 * SCTP packet. The transmitter MUST transmit DATA chunks
742 * within a SCTP packet in increasing order of TSN.
743 * ...
744 */
745
David S. Miller79af02c2005-07-08 21:47:49 -0700746 list_for_each_entry_safe(chunk, tmp, &q->control_chunk_list, list) {
747 list_del_init(&chunk->list);
748
Linus Torvalds1da177e2005-04-16 15:20:36 -0700749 /* Pick the right transport to use. */
750 new_transport = chunk->transport;
751
752 if (!new_transport) {
Vlad Yasevicha08de642007-12-20 14:11:47 -0800753 /*
754 * If we have a prior transport pointer, see if
755 * the destination address of the chunk
756 * matches the destination address of the
757 * current transport. If not a match, then
758 * try to look up the transport with a given
759 * destination address. We do this because
760 * after processing ASCONFs, we may have new
761 * transports created.
762 */
763 if (transport &&
764 sctp_cmp_addr_exact(&chunk->dest,
765 &transport->ipaddr))
766 new_transport = transport;
767 else
768 new_transport = sctp_assoc_lookup_paddr(asoc,
769 &chunk->dest);
770
771 /* if we still don't have a new transport, then
772 * use the current active path.
773 */
774 if (!new_transport)
775 new_transport = asoc->peer.active_path;
Sridhar Samudralaad8fec12006-07-21 14:48:50 -0700776 } else if ((new_transport->state == SCTP_INACTIVE) ||
777 (new_transport->state == SCTP_UNCONFIRMED)) {
Frank Filz3f7a87d2005-06-20 13:14:57 -0700778 /* If the chunk is Heartbeat or Heartbeat Ack,
779 * send it to chunk->transport, even if it's
Linus Torvalds1da177e2005-04-16 15:20:36 -0700780 * inactive.
781 *
782 * 3.3.6 Heartbeat Acknowledgement:
YOSHIFUJI Hideakid808ad92007-02-09 23:25:18 +0900783 * ...
Linus Torvalds1da177e2005-04-16 15:20:36 -0700784 * A HEARTBEAT ACK is always sent to the source IP
785 * address of the IP datagram containing the
786 * HEARTBEAT chunk to which this ack is responding.
YOSHIFUJI Hideakid808ad92007-02-09 23:25:18 +0900787 * ...
Vlad Yasevicha08de642007-12-20 14:11:47 -0800788 *
789 * ASCONF_ACKs also must be sent to the source.
Linus Torvalds1da177e2005-04-16 15:20:36 -0700790 */
791 if (chunk->chunk_hdr->type != SCTP_CID_HEARTBEAT &&
Vlad Yasevicha08de642007-12-20 14:11:47 -0800792 chunk->chunk_hdr->type != SCTP_CID_HEARTBEAT_ACK &&
793 chunk->chunk_hdr->type != SCTP_CID_ASCONF_ACK)
Linus Torvalds1da177e2005-04-16 15:20:36 -0700794 new_transport = asoc->peer.active_path;
795 }
796
797 /* Are we switching transports?
798 * Take care of transport locks.
799 */
800 if (new_transport != transport) {
801 transport = new_transport;
802 if (list_empty(&transport->send_ready)) {
803 list_add_tail(&transport->send_ready,
804 &transport_list);
805 }
806 packet = &transport->packet;
807 sctp_packet_config(packet, vtag,
808 asoc->peer.ecn_capable);
809 }
810
811 switch (chunk->chunk_hdr->type) {
812 /*
813 * 6.10 Bundling
814 * ...
815 * An endpoint MUST NOT bundle INIT, INIT ACK or SHUTDOWN
816 * COMPLETE with any other chunks. [Send them immediately.]
817 */
818 case SCTP_CID_INIT:
819 case SCTP_CID_INIT_ACK:
820 case SCTP_CID_SHUTDOWN_COMPLETE:
821 sctp_packet_init(&singleton, transport, sport, dport);
822 sctp_packet_config(&singleton, vtag, 0);
823 sctp_packet_append_chunk(&singleton, chunk);
824 error = sctp_packet_transmit(&singleton);
825 if (error < 0)
826 return error;
827 break;
828
829 case SCTP_CID_ABORT:
Gui Jianfengf4ad85c2008-04-12 18:39:34 -0700830 if (sctp_test_T_bit(chunk)) {
831 packet->vtag = asoc->c.my_vtag;
832 }
Linus Torvalds1da177e2005-04-16 15:20:36 -0700833 case SCTP_CID_SACK:
834 case SCTP_CID_HEARTBEAT:
835 case SCTP_CID_HEARTBEAT_ACK:
836 case SCTP_CID_SHUTDOWN:
837 case SCTP_CID_SHUTDOWN_ACK:
838 case SCTP_CID_ERROR:
839 case SCTP_CID_COOKIE_ECHO:
840 case SCTP_CID_COOKIE_ACK:
841 case SCTP_CID_ECN_ECNE:
842 case SCTP_CID_ECN_CWR:
843 case SCTP_CID_ASCONF:
844 case SCTP_CID_ASCONF_ACK:
845 case SCTP_CID_FWD_TSN:
846 sctp_packet_transmit_chunk(packet, chunk);
847 break;
848
849 default:
850 /* We built a chunk with an illegal type! */
851 BUG();
Stephen Hemminger3ff50b72007-04-20 17:09:22 -0700852 }
Linus Torvalds1da177e2005-04-16 15:20:36 -0700853 }
854
855 /* Is it OK to send data chunks? */
856 switch (asoc->state) {
857 case SCTP_STATE_COOKIE_ECHOED:
858 /* Only allow bundling when this packet has a COOKIE-ECHO
859 * chunk.
860 */
861 if (!packet || !packet->has_cookie_echo)
862 break;
863
864 /* fallthru */
865 case SCTP_STATE_ESTABLISHED:
866 case SCTP_STATE_SHUTDOWN_PENDING:
867 case SCTP_STATE_SHUTDOWN_RECEIVED:
868 /*
869 * RFC 2960 6.1 Transmission of DATA Chunks
870 *
871 * C) When the time comes for the sender to transmit,
872 * before sending new DATA chunks, the sender MUST
873 * first transmit any outstanding DATA chunks which
874 * are marked for retransmission (limited by the
875 * current cwnd).
876 */
877 if (!list_empty(&q->retransmit)) {
878 if (transport == asoc->peer.retran_path)
879 goto retran;
880
881 /* Switch transports & prepare the packet. */
882
883 transport = asoc->peer.retran_path;
884
885 if (list_empty(&transport->send_ready)) {
886 list_add_tail(&transport->send_ready,
887 &transport_list);
888 }
889
890 packet = &transport->packet;
891 sctp_packet_config(packet, vtag,
892 asoc->peer.ecn_capable);
893 retran:
894 error = sctp_outq_flush_rtx(q, packet,
895 rtx_timeout, &start_timer);
896
897 if (start_timer)
Vlad Yasevich62aeaff2008-06-04 12:39:11 -0700898 sctp_transport_reset_timers(transport,
899 start_timer-1);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700900
901 /* This can happen on COOKIE-ECHO resend. Only
902 * one chunk can get bundled with a COOKIE-ECHO.
903 */
904 if (packet->has_cookie_echo)
905 goto sctp_flush_out;
906
907 /* Don't send new data if there is still data
908 * waiting to retransmit.
909 */
910 if (!list_empty(&q->retransmit))
911 goto sctp_flush_out;
912 }
913
914 /* Finally, transmit new packets. */
915 start_timer = 0;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700916 while ((chunk = sctp_outq_dequeue_data(q)) != NULL) {
917 /* RFC 2960 6.5 Every DATA chunk MUST carry a valid
918 * stream identifier.
919 */
920 if (chunk->sinfo.sinfo_stream >=
921 asoc->c.sinit_num_ostreams) {
922
923 /* Mark as failed send. */
924 sctp_chunk_fail(chunk, SCTP_ERROR_INV_STRM);
925 sctp_chunk_free(chunk);
926 continue;
927 }
928
929 /* Has this chunk expired? */
930 if (sctp_chunk_abandoned(chunk)) {
931 sctp_chunk_fail(chunk, 0);
932 sctp_chunk_free(chunk);
933 continue;
934 }
935
936 /* If there is a specified transport, use it.
937 * Otherwise, we want to use the active path.
938 */
939 new_transport = chunk->transport;
Frank Filz3f7a87d2005-06-20 13:14:57 -0700940 if (!new_transport ||
Sridhar Samudralaad8fec12006-07-21 14:48:50 -0700941 ((new_transport->state == SCTP_INACTIVE) ||
942 (new_transport->state == SCTP_UNCONFIRMED)))
Linus Torvalds1da177e2005-04-16 15:20:36 -0700943 new_transport = asoc->peer.active_path;
944
945 /* Change packets if necessary. */
946 if (new_transport != transport) {
947 transport = new_transport;
948
949 /* Schedule to have this transport's
950 * packet flushed.
951 */
952 if (list_empty(&transport->send_ready)) {
953 list_add_tail(&transport->send_ready,
954 &transport_list);
955 }
956
957 packet = &transport->packet;
958 sctp_packet_config(packet, vtag,
959 asoc->peer.ecn_capable);
960 }
961
962 SCTP_DEBUG_PRINTK("sctp_outq_flush(%p, %p[%s]), ",
963 q, chunk,
964 chunk && chunk->chunk_hdr ?
965 sctp_cname(SCTP_ST_CHUNK(
966 chunk->chunk_hdr->type))
967 : "Illegal Chunk");
968
969 SCTP_DEBUG_PRINTK("TX TSN 0x%x skb->head "
970 "%p skb->users %d.\n",
971 ntohl(chunk->subh.data_hdr->tsn),
972 chunk->skb ?chunk->skb->head : NULL,
973 chunk->skb ?
974 atomic_read(&chunk->skb->users) : -1);
975
976 /* Add the chunk to the packet. */
977 status = sctp_packet_transmit_chunk(packet, chunk);
978
979 switch (status) {
980 case SCTP_XMIT_PMTU_FULL:
981 case SCTP_XMIT_RWND_FULL:
982 case SCTP_XMIT_NAGLE_DELAY:
983 /* We could not append this chunk, so put
984 * the chunk back on the output queue.
985 */
986 SCTP_DEBUG_PRINTK("sctp_outq_flush: could "
987 "not transmit TSN: 0x%x, status: %d\n",
988 ntohl(chunk->subh.data_hdr->tsn),
989 status);
990 sctp_outq_head_data(q, chunk);
991 goto sctp_flush_out;
992 break;
993
994 case SCTP_XMIT_OK:
995 break;
996
997 default:
998 BUG();
999 }
1000
YOSHIFUJI Hideakid808ad92007-02-09 23:25:18 +09001001 /* BUG: We assume that the sctp_packet_transmit()
Linus Torvalds1da177e2005-04-16 15:20:36 -07001002 * call below will succeed all the time and add the
1003 * chunk to the transmitted list and restart the
1004 * timers.
1005 * It is possible that the call can fail under OOM
1006 * conditions.
1007 *
1008 * Is this really a problem? Won't this behave
1009 * like a lost TSN?
1010 */
1011 list_add_tail(&chunk->transmitted_list,
1012 &transport->transmitted);
1013
Vlad Yasevich62aeaff2008-06-04 12:39:11 -07001014 sctp_transport_reset_timers(transport, start_timer-1);
Linus Torvalds1da177e2005-04-16 15:20:36 -07001015
1016 q->empty = 0;
1017
1018 /* Only let one DATA chunk get bundled with a
1019 * COOKIE-ECHO chunk.
1020 */
1021 if (packet->has_cookie_echo)
1022 goto sctp_flush_out;
1023 }
1024 break;
1025
1026 default:
1027 /* Do nothing. */
1028 break;
1029 }
1030
1031sctp_flush_out:
1032
1033 /* Before returning, examine all the transports touched in
1034 * this call. Right now, we bluntly force clear all the
1035 * transports. Things might change after we implement Nagle.
1036 * But such an examination is still required.
1037 *
1038 * --xguo
1039 */
1040 while ((ltransport = sctp_list_dequeue(&transport_list)) != NULL ) {
1041 struct sctp_transport *t = list_entry(ltransport,
1042 struct sctp_transport,
1043 send_ready);
1044 packet = &t->packet;
1045 if (!sctp_packet_empty(packet))
1046 error = sctp_packet_transmit(packet);
1047 }
1048
1049 return error;
1050}
1051
1052/* Update unack_data based on the incoming SACK chunk */
1053static void sctp_sack_update_unack_data(struct sctp_association *assoc,
1054 struct sctp_sackhdr *sack)
1055{
1056 sctp_sack_variable_t *frags;
1057 __u16 unack_data;
1058 int i;
1059
1060 unack_data = assoc->next_tsn - assoc->ctsn_ack_point - 1;
1061
1062 frags = sack->variable;
1063 for (i = 0; i < ntohs(sack->num_gap_ack_blocks); i++) {
1064 unack_data -= ((ntohs(frags[i].gab.end) -
1065 ntohs(frags[i].gab.start) + 1));
1066 }
1067
1068 assoc->unack_data = unack_data;
1069}
1070
1071/* Return the highest new tsn that is acknowledged by the given SACK chunk. */
1072static __u32 sctp_highest_new_tsn(struct sctp_sackhdr *sack,
1073 struct sctp_association *asoc)
1074{
Linus Torvalds1da177e2005-04-16 15:20:36 -07001075 struct sctp_transport *transport;
1076 struct sctp_chunk *chunk;
1077 __u32 highest_new_tsn, tsn;
1078 struct list_head *transport_list = &asoc->peer.transport_addr_list;
1079
1080 highest_new_tsn = ntohl(sack->cum_tsn_ack);
1081
Robert P. J. Day9dbc15f2008-04-12 18:54:24 -07001082 list_for_each_entry(transport, transport_list, transports) {
1083 list_for_each_entry(chunk, &transport->transmitted,
1084 transmitted_list) {
Linus Torvalds1da177e2005-04-16 15:20:36 -07001085 tsn = ntohl(chunk->subh.data_hdr->tsn);
1086
1087 if (!chunk->tsn_gap_acked &&
1088 TSN_lt(highest_new_tsn, tsn) &&
1089 sctp_acked(sack, tsn))
1090 highest_new_tsn = tsn;
1091 }
1092 }
1093
1094 return highest_new_tsn;
1095}
1096
1097/* This is where we REALLY process a SACK.
1098 *
1099 * Process the SACK against the outqueue. Mostly, this just frees
1100 * things off the transmitted queue.
1101 */
1102int sctp_outq_sack(struct sctp_outq *q, struct sctp_sackhdr *sack)
1103{
1104 struct sctp_association *asoc = q->asoc;
1105 struct sctp_transport *transport;
1106 struct sctp_chunk *tchunk = NULL;
Robert P. J. Day9dbc15f2008-04-12 18:54:24 -07001107 struct list_head *lchunk, *transport_list, *temp;
Linus Torvalds1da177e2005-04-16 15:20:36 -07001108 sctp_sack_variable_t *frags = sack->variable;
1109 __u32 sack_ctsn, ctsn, tsn;
1110 __u32 highest_tsn, highest_new_tsn;
1111 __u32 sack_a_rwnd;
1112 unsigned outstanding;
1113 struct sctp_transport *primary = asoc->peer.primary_path;
1114 int count_of_newacks = 0;
1115
1116 /* Grab the association's destination address list. */
1117 transport_list = &asoc->peer.transport_addr_list;
1118
1119 sack_ctsn = ntohl(sack->cum_tsn_ack);
1120
1121 /*
1122 * SFR-CACC algorithm:
1123 * On receipt of a SACK the sender SHOULD execute the
1124 * following statements.
1125 *
1126 * 1) If the cumulative ack in the SACK passes next tsn_at_change
1127 * on the current primary, the CHANGEOVER_ACTIVE flag SHOULD be
1128 * cleared. The CYCLING_CHANGEOVER flag SHOULD also be cleared for
1129 * all destinations.
1130 */
1131 if (TSN_lte(primary->cacc.next_tsn_at_change, sack_ctsn)) {
1132 primary->cacc.changeover_active = 0;
Robert P. J. Day9dbc15f2008-04-12 18:54:24 -07001133 list_for_each_entry(transport, transport_list,
1134 transports) {
Linus Torvalds1da177e2005-04-16 15:20:36 -07001135 transport->cacc.cycling_changeover = 0;
1136 }
1137 }
1138
1139 /*
1140 * SFR-CACC algorithm:
1141 * 2) If the SACK contains gap acks and the flag CHANGEOVER_ACTIVE
1142 * is set the receiver of the SACK MUST take the following actions:
1143 *
1144 * A) Initialize the cacc_saw_newack to 0 for all destination
1145 * addresses.
1146 */
Al Viro34bcca22006-11-20 17:27:15 -08001147 if (sack->num_gap_ack_blocks &&
Linus Torvalds1da177e2005-04-16 15:20:36 -07001148 primary->cacc.changeover_active) {
Robert P. J. Day9dbc15f2008-04-12 18:54:24 -07001149 list_for_each_entry(transport, transport_list, transports) {
Linus Torvalds1da177e2005-04-16 15:20:36 -07001150 transport->cacc.cacc_saw_newack = 0;
1151 }
1152 }
1153
1154 /* Get the highest TSN in the sack. */
1155 highest_tsn = sack_ctsn;
1156 if (sack->num_gap_ack_blocks)
1157 highest_tsn +=
1158 ntohs(frags[ntohs(sack->num_gap_ack_blocks) - 1].gab.end);
1159
1160 if (TSN_lt(asoc->highest_sacked, highest_tsn)) {
1161 highest_new_tsn = highest_tsn;
1162 asoc->highest_sacked = highest_tsn;
1163 } else {
1164 highest_new_tsn = sctp_highest_new_tsn(sack, asoc);
1165 }
1166
1167 /* Run through the retransmit queue. Credit bytes received
1168 * and free those chunks that we can.
1169 */
1170 sctp_check_transmitted(q, &q->retransmit, NULL, sack, highest_new_tsn);
1171 sctp_mark_missing(q, &q->retransmit, NULL, highest_new_tsn, 0);
1172
1173 /* Run through the transmitted queue.
1174 * Credit bytes received and free those chunks which we can.
1175 *
1176 * This is a MASSIVE candidate for optimization.
1177 */
Robert P. J. Day9dbc15f2008-04-12 18:54:24 -07001178 list_for_each_entry(transport, transport_list, transports) {
Linus Torvalds1da177e2005-04-16 15:20:36 -07001179 sctp_check_transmitted(q, &transport->transmitted,
1180 transport, sack, highest_new_tsn);
1181 /*
1182 * SFR-CACC algorithm:
1183 * C) Let count_of_newacks be the number of
1184 * destinations for which cacc_saw_newack is set.
1185 */
1186 if (transport->cacc.cacc_saw_newack)
1187 count_of_newacks ++;
1188 }
1189
Robert P. J. Day9dbc15f2008-04-12 18:54:24 -07001190 list_for_each_entry(transport, transport_list, transports) {
Linus Torvalds1da177e2005-04-16 15:20:36 -07001191 sctp_mark_missing(q, &transport->transmitted, transport,
1192 highest_new_tsn, count_of_newacks);
1193 }
1194
1195 /* Move the Cumulative TSN Ack Point if appropriate. */
1196 if (TSN_lt(asoc->ctsn_ack_point, sack_ctsn))
1197 asoc->ctsn_ack_point = sack_ctsn;
1198
1199 /* Update unack_data field in the assoc. */
1200 sctp_sack_update_unack_data(asoc, sack);
1201
1202 ctsn = asoc->ctsn_ack_point;
1203
1204 /* Throw away stuff rotting on the sack queue. */
1205 list_for_each_safe(lchunk, temp, &q->sacked) {
1206 tchunk = list_entry(lchunk, struct sctp_chunk,
1207 transmitted_list);
1208 tsn = ntohl(tchunk->subh.data_hdr->tsn);
Vlad Yasevich5f9646c2008-02-05 14:23:44 -05001209 if (TSN_lte(tsn, ctsn)) {
1210 list_del_init(&tchunk->transmitted_list);
Linus Torvalds1da177e2005-04-16 15:20:36 -07001211 sctp_chunk_free(tchunk);
Vlad Yasevich5f9646c2008-02-05 14:23:44 -05001212 }
Linus Torvalds1da177e2005-04-16 15:20:36 -07001213 }
1214
1215 /* ii) Set rwnd equal to the newly received a_rwnd minus the
1216 * number of bytes still outstanding after processing the
1217 * Cumulative TSN Ack and the Gap Ack Blocks.
1218 */
1219
1220 sack_a_rwnd = ntohl(sack->a_rwnd);
1221 outstanding = q->outstanding_bytes;
1222
1223 if (outstanding < sack_a_rwnd)
1224 sack_a_rwnd -= outstanding;
1225 else
1226 sack_a_rwnd = 0;
1227
1228 asoc->peer.rwnd = sack_a_rwnd;
1229
1230 sctp_generate_fwdtsn(q, sack_ctsn);
1231
1232 SCTP_DEBUG_PRINTK("%s: sack Cumulative TSN Ack is 0x%x.\n",
Harvey Harrison0dc47872008-03-05 20:47:47 -08001233 __func__, sack_ctsn);
Linus Torvalds1da177e2005-04-16 15:20:36 -07001234 SCTP_DEBUG_PRINTK("%s: Cumulative TSN Ack of association, "
1235 "%p is 0x%x. Adv peer ack point: 0x%x\n",
Harvey Harrison0dc47872008-03-05 20:47:47 -08001236 __func__, asoc, ctsn, asoc->adv_peer_ack_point);
Linus Torvalds1da177e2005-04-16 15:20:36 -07001237
1238 /* See if all chunks are acked.
1239 * Make sure the empty queue handler will get run later.
1240 */
David S. Miller79af02c2005-07-08 21:47:49 -07001241 q->empty = (list_empty(&q->out_chunk_list) &&
1242 list_empty(&q->control_chunk_list) &&
1243 list_empty(&q->retransmit));
Linus Torvalds1da177e2005-04-16 15:20:36 -07001244 if (!q->empty)
1245 goto finish;
1246
Robert P. J. Day9dbc15f2008-04-12 18:54:24 -07001247 list_for_each_entry(transport, transport_list, transports) {
Linus Torvalds1da177e2005-04-16 15:20:36 -07001248 q->empty = q->empty && list_empty(&transport->transmitted);
1249 if (!q->empty)
1250 goto finish;
1251 }
1252
1253 SCTP_DEBUG_PRINTK("sack queue is empty.\n");
1254finish:
1255 return q->empty;
1256}
1257
1258/* Is the outqueue empty? */
1259int sctp_outq_is_empty(const struct sctp_outq *q)
1260{
1261 return q->empty;
1262}
1263
1264/********************************************************************
1265 * 2nd Level Abstractions
1266 ********************************************************************/
1267
1268/* Go through a transport's transmitted list or the association's retransmit
1269 * list and move chunks that are acked by the Cumulative TSN Ack to q->sacked.
1270 * The retransmit list will not have an associated transport.
1271 *
1272 * I added coherent debug information output. --xguo
1273 *
1274 * Instead of printing 'sacked' or 'kept' for each TSN on the
1275 * transmitted_queue, we print a range: SACKED: TSN1-TSN2, TSN3, TSN4-TSN5.
1276 * KEPT TSN6-TSN7, etc.
1277 */
1278static void sctp_check_transmitted(struct sctp_outq *q,
1279 struct list_head *transmitted_queue,
1280 struct sctp_transport *transport,
1281 struct sctp_sackhdr *sack,
1282 __u32 highest_new_tsn_in_sack)
1283{
1284 struct list_head *lchunk;
1285 struct sctp_chunk *tchunk;
1286 struct list_head tlist;
1287 __u32 tsn;
1288 __u32 sack_ctsn;
1289 __u32 rtt;
1290 __u8 restart_timer = 0;
1291 int bytes_acked = 0;
1292
1293 /* These state variables are for coherent debug output. --xguo */
1294
1295#if SCTP_DEBUG
1296 __u32 dbg_ack_tsn = 0; /* An ACKed TSN range starts here... */
1297 __u32 dbg_last_ack_tsn = 0; /* ...and finishes here. */
1298 __u32 dbg_kept_tsn = 0; /* An un-ACKed range starts here... */
1299 __u32 dbg_last_kept_tsn = 0; /* ...and finishes here. */
1300
1301 /* 0 : The last TSN was ACKed.
1302 * 1 : The last TSN was NOT ACKed (i.e. KEPT).
1303 * -1: We need to initialize.
1304 */
1305 int dbg_prt_state = -1;
1306#endif /* SCTP_DEBUG */
1307
1308 sack_ctsn = ntohl(sack->cum_tsn_ack);
1309
1310 INIT_LIST_HEAD(&tlist);
1311
1312 /* The while loop will skip empty transmitted queues. */
1313 while (NULL != (lchunk = sctp_list_dequeue(transmitted_queue))) {
1314 tchunk = list_entry(lchunk, struct sctp_chunk,
1315 transmitted_list);
1316
1317 if (sctp_chunk_abandoned(tchunk)) {
1318 /* Move the chunk to abandoned list. */
1319 sctp_insert_list(&q->abandoned, lchunk);
Vlad Yasevich8c4a2d42007-02-21 02:06:04 -08001320
1321 /* If this chunk has not been acked, stop
1322 * considering it as 'outstanding'.
1323 */
1324 if (!tchunk->tsn_gap_acked) {
1325 tchunk->transport->flight_size -=
1326 sctp_data_size(tchunk);
1327 q->outstanding_bytes -= sctp_data_size(tchunk);
1328 }
Linus Torvalds1da177e2005-04-16 15:20:36 -07001329 continue;
1330 }
1331
1332 tsn = ntohl(tchunk->subh.data_hdr->tsn);
1333 if (sctp_acked(sack, tsn)) {
1334 /* If this queue is the retransmit queue, the
1335 * retransmit timer has already reclaimed
1336 * the outstanding bytes for this chunk, so only
1337 * count bytes associated with a transport.
1338 */
1339 if (transport) {
1340 /* If this chunk is being used for RTT
1341 * measurement, calculate the RTT and update
1342 * the RTO using this value.
1343 *
1344 * 6.3.1 C5) Karn's algorithm: RTT measurements
1345 * MUST NOT be made using packets that were
1346 * retransmitted (and thus for which it is
1347 * ambiguous whether the reply was for the
1348 * first instance of the packet or a later
1349 * instance).
1350 */
YOSHIFUJI Hideakid808ad92007-02-09 23:25:18 +09001351 if (!tchunk->tsn_gap_acked &&
Linus Torvalds1da177e2005-04-16 15:20:36 -07001352 !tchunk->resent &&
1353 tchunk->rtt_in_progress) {
Vlad Yasevich4c9f5d52006-06-17 22:56:08 -07001354 tchunk->rtt_in_progress = 0;
Linus Torvalds1da177e2005-04-16 15:20:36 -07001355 rtt = jiffies - tchunk->sent_at;
1356 sctp_transport_update_rto(transport,
1357 rtt);
1358 }
1359 }
YOSHIFUJI Hideakid808ad92007-02-09 23:25:18 +09001360 if (TSN_lte(tsn, sack_ctsn)) {
Linus Torvalds1da177e2005-04-16 15:20:36 -07001361 /* RFC 2960 6.3.2 Retransmission Timer Rules
1362 *
1363 * R3) Whenever a SACK is received
1364 * that acknowledges the DATA chunk
1365 * with the earliest outstanding TSN
1366 * for that address, restart T3-rtx
1367 * timer for that address with its
1368 * current RTO.
1369 */
1370 restart_timer = 1;
1371
1372 if (!tchunk->tsn_gap_acked) {
1373 tchunk->tsn_gap_acked = 1;
1374 bytes_acked += sctp_data_size(tchunk);
1375 /*
1376 * SFR-CACC algorithm:
1377 * 2) If the SACK contains gap acks
1378 * and the flag CHANGEOVER_ACTIVE is
1379 * set the receiver of the SACK MUST
1380 * take the following action:
1381 *
1382 * B) For each TSN t being acked that
1383 * has not been acked in any SACK so
1384 * far, set cacc_saw_newack to 1 for
1385 * the destination that the TSN was
1386 * sent to.
1387 */
1388 if (transport &&
1389 sack->num_gap_ack_blocks &&
1390 q->asoc->peer.primary_path->cacc.
1391 changeover_active)
1392 transport->cacc.cacc_saw_newack
1393 = 1;
1394 }
1395
1396 list_add_tail(&tchunk->transmitted_list,
1397 &q->sacked);
1398 } else {
1399 /* RFC2960 7.2.4, sctpimpguide-05 2.8.2
1400 * M2) Each time a SACK arrives reporting
1401 * 'Stray DATA chunk(s)' record the highest TSN
1402 * reported as newly acknowledged, call this
1403 * value 'HighestTSNinSack'. A newly
1404 * acknowledged DATA chunk is one not
1405 * previously acknowledged in a SACK.
1406 *
1407 * When the SCTP sender of data receives a SACK
1408 * chunk that acknowledges, for the first time,
1409 * the receipt of a DATA chunk, all the still
1410 * unacknowledged DATA chunks whose TSN is
1411 * older than that newly acknowledged DATA
1412 * chunk, are qualified as 'Stray DATA chunks'.
1413 */
1414 if (!tchunk->tsn_gap_acked) {
1415 tchunk->tsn_gap_acked = 1;
1416 bytes_acked += sctp_data_size(tchunk);
1417 }
1418 list_add_tail(lchunk, &tlist);
1419 }
1420
1421#if SCTP_DEBUG
1422 switch (dbg_prt_state) {
1423 case 0: /* last TSN was ACKed */
1424 if (dbg_last_ack_tsn + 1 == tsn) {
1425 /* This TSN belongs to the
1426 * current ACK range.
1427 */
1428 break;
1429 }
1430
1431 if (dbg_last_ack_tsn != dbg_ack_tsn) {
1432 /* Display the end of the
1433 * current range.
1434 */
1435 SCTP_DEBUG_PRINTK("-%08x",
1436 dbg_last_ack_tsn);
1437 }
1438
1439 /* Start a new range. */
1440 SCTP_DEBUG_PRINTK(",%08x", tsn);
1441 dbg_ack_tsn = tsn;
1442 break;
1443
1444 case 1: /* The last TSN was NOT ACKed. */
1445 if (dbg_last_kept_tsn != dbg_kept_tsn) {
1446 /* Display the end of current range. */
1447 SCTP_DEBUG_PRINTK("-%08x",
1448 dbg_last_kept_tsn);
1449 }
1450
1451 SCTP_DEBUG_PRINTK("\n");
1452
1453 /* FALL THROUGH... */
1454 default:
1455 /* This is the first-ever TSN we examined. */
1456 /* Start a new range of ACK-ed TSNs. */
1457 SCTP_DEBUG_PRINTK("ACKed: %08x", tsn);
1458 dbg_prt_state = 0;
1459 dbg_ack_tsn = tsn;
Stephen Hemminger3ff50b72007-04-20 17:09:22 -07001460 }
Linus Torvalds1da177e2005-04-16 15:20:36 -07001461
1462 dbg_last_ack_tsn = tsn;
1463#endif /* SCTP_DEBUG */
1464
1465 } else {
1466 if (tchunk->tsn_gap_acked) {
1467 SCTP_DEBUG_PRINTK("%s: Receiver reneged on "
1468 "data TSN: 0x%x\n",
Harvey Harrison0dc47872008-03-05 20:47:47 -08001469 __func__,
Linus Torvalds1da177e2005-04-16 15:20:36 -07001470 tsn);
1471 tchunk->tsn_gap_acked = 0;
1472
1473 bytes_acked -= sctp_data_size(tchunk);
1474
1475 /* RFC 2960 6.3.2 Retransmission Timer Rules
1476 *
1477 * R4) Whenever a SACK is received missing a
1478 * TSN that was previously acknowledged via a
1479 * Gap Ack Block, start T3-rtx for the
1480 * destination address to which the DATA
1481 * chunk was originally
1482 * transmitted if it is not already running.
1483 */
1484 restart_timer = 1;
1485 }
1486
1487 list_add_tail(lchunk, &tlist);
1488
1489#if SCTP_DEBUG
1490 /* See the above comments on ACK-ed TSNs. */
1491 switch (dbg_prt_state) {
1492 case 1:
1493 if (dbg_last_kept_tsn + 1 == tsn)
1494 break;
1495
1496 if (dbg_last_kept_tsn != dbg_kept_tsn)
1497 SCTP_DEBUG_PRINTK("-%08x",
1498 dbg_last_kept_tsn);
1499
1500 SCTP_DEBUG_PRINTK(",%08x", tsn);
1501 dbg_kept_tsn = tsn;
1502 break;
1503
1504 case 0:
1505 if (dbg_last_ack_tsn != dbg_ack_tsn)
1506 SCTP_DEBUG_PRINTK("-%08x",
1507 dbg_last_ack_tsn);
1508 SCTP_DEBUG_PRINTK("\n");
1509
1510 /* FALL THROUGH... */
1511 default:
1512 SCTP_DEBUG_PRINTK("KEPT: %08x",tsn);
1513 dbg_prt_state = 1;
1514 dbg_kept_tsn = tsn;
Stephen Hemminger3ff50b72007-04-20 17:09:22 -07001515 }
Linus Torvalds1da177e2005-04-16 15:20:36 -07001516
1517 dbg_last_kept_tsn = tsn;
1518#endif /* SCTP_DEBUG */
1519 }
1520 }
1521
1522#if SCTP_DEBUG
1523 /* Finish off the last range, displaying its ending TSN. */
1524 switch (dbg_prt_state) {
1525 case 0:
1526 if (dbg_last_ack_tsn != dbg_ack_tsn) {
1527 SCTP_DEBUG_PRINTK("-%08x\n", dbg_last_ack_tsn);
1528 } else {
1529 SCTP_DEBUG_PRINTK("\n");
1530 }
1531 break;
1532
1533 case 1:
1534 if (dbg_last_kept_tsn != dbg_kept_tsn) {
1535 SCTP_DEBUG_PRINTK("-%08x\n", dbg_last_kept_tsn);
1536 } else {
1537 SCTP_DEBUG_PRINTK("\n");
1538 }
Stephen Hemminger3ff50b72007-04-20 17:09:22 -07001539 }
Linus Torvalds1da177e2005-04-16 15:20:36 -07001540#endif /* SCTP_DEBUG */
1541 if (transport) {
1542 if (bytes_acked) {
1543 /* 8.2. When an outstanding TSN is acknowledged,
1544 * the endpoint shall clear the error counter of
1545 * the destination transport address to which the
1546 * DATA chunk was last sent.
1547 * The association's overall error counter is
1548 * also cleared.
1549 */
1550 transport->error_count = 0;
1551 transport->asoc->overall_error_count = 0;
1552
1553 /* Mark the destination transport address as
1554 * active if it is not so marked.
1555 */
Sridhar Samudralaad8fec12006-07-21 14:48:50 -07001556 if ((transport->state == SCTP_INACTIVE) ||
1557 (transport->state == SCTP_UNCONFIRMED)) {
Linus Torvalds1da177e2005-04-16 15:20:36 -07001558 sctp_assoc_control_transport(
1559 transport->asoc,
1560 transport,
1561 SCTP_TRANSPORT_UP,
1562 SCTP_RECEIVED_SACK);
1563 }
1564
1565 sctp_transport_raise_cwnd(transport, sack_ctsn,
1566 bytes_acked);
1567
1568 transport->flight_size -= bytes_acked;
Gui Jianfeng8b73a072008-04-17 14:22:18 -07001569 if (transport->flight_size == 0)
1570 transport->partial_bytes_acked = 0;
Linus Torvalds1da177e2005-04-16 15:20:36 -07001571 q->outstanding_bytes -= bytes_acked;
1572 } else {
1573 /* RFC 2960 6.1, sctpimpguide-06 2.15.2
1574 * When a sender is doing zero window probing, it
1575 * should not timeout the association if it continues
1576 * to receive new packets from the receiver. The
1577 * reason is that the receiver MAY keep its window
1578 * closed for an indefinite time.
1579 * A sender is doing zero window probing when the
1580 * receiver's advertised window is zero, and there is
1581 * only one data chunk in flight to the receiver.
1582 */
1583 if (!q->asoc->peer.rwnd &&
1584 !list_empty(&tlist) &&
1585 (sack_ctsn+2 == q->asoc->next_tsn)) {
1586 SCTP_DEBUG_PRINTK("%s: SACK received for zero "
1587 "window probe: %u\n",
Harvey Harrison0dc47872008-03-05 20:47:47 -08001588 __func__, sack_ctsn);
Linus Torvalds1da177e2005-04-16 15:20:36 -07001589 q->asoc->overall_error_count = 0;
1590 transport->error_count = 0;
1591 }
1592 }
1593
1594 /* RFC 2960 6.3.2 Retransmission Timer Rules
1595 *
1596 * R2) Whenever all outstanding data sent to an address have
1597 * been acknowledged, turn off the T3-rtx timer of that
1598 * address.
1599 */
1600 if (!transport->flight_size) {
1601 if (timer_pending(&transport->T3_rtx_timer) &&
1602 del_timer(&transport->T3_rtx_timer)) {
1603 sctp_transport_put(transport);
1604 }
1605 } else if (restart_timer) {
1606 if (!mod_timer(&transport->T3_rtx_timer,
1607 jiffies + transport->rto))
1608 sctp_transport_hold(transport);
1609 }
1610 }
1611
1612 list_splice(&tlist, transmitted_queue);
1613}
1614
1615/* Mark chunks as missing and consequently may get retransmitted. */
1616static void sctp_mark_missing(struct sctp_outq *q,
1617 struct list_head *transmitted_queue,
1618 struct sctp_transport *transport,
1619 __u32 highest_new_tsn_in_sack,
1620 int count_of_newacks)
1621{
1622 struct sctp_chunk *chunk;
Linus Torvalds1da177e2005-04-16 15:20:36 -07001623 __u32 tsn;
1624 char do_fast_retransmit = 0;
1625 struct sctp_transport *primary = q->asoc->peer.primary_path;
1626
Robert P. J. Day9dbc15f2008-04-12 18:54:24 -07001627 list_for_each_entry(chunk, transmitted_queue, transmitted_list) {
Linus Torvalds1da177e2005-04-16 15:20:36 -07001628
Linus Torvalds1da177e2005-04-16 15:20:36 -07001629 tsn = ntohl(chunk->subh.data_hdr->tsn);
1630
1631 /* RFC 2960 7.2.4, sctpimpguide-05 2.8.2 M3) Examine all
1632 * 'Unacknowledged TSN's', if the TSN number of an
1633 * 'Unacknowledged TSN' is smaller than the 'HighestTSNinSack'
1634 * value, increment the 'TSN.Missing.Report' count on that
1635 * chunk if it has NOT been fast retransmitted or marked for
1636 * fast retransmit already.
1637 */
1638 if (!chunk->fast_retransmit &&
1639 !chunk->tsn_gap_acked &&
1640 TSN_lt(tsn, highest_new_tsn_in_sack)) {
1641
1642 /* SFR-CACC may require us to skip marking
1643 * this chunk as missing.
1644 */
1645 if (!transport || !sctp_cacc_skip(primary, transport,
1646 count_of_newacks, tsn)) {
1647 chunk->tsn_missing_report++;
1648
1649 SCTP_DEBUG_PRINTK(
1650 "%s: TSN 0x%x missing counter: %d\n",
Harvey Harrison0dc47872008-03-05 20:47:47 -08001651 __func__, tsn,
Linus Torvalds1da177e2005-04-16 15:20:36 -07001652 chunk->tsn_missing_report);
1653 }
1654 }
1655 /*
1656 * M4) If any DATA chunk is found to have a
1657 * 'TSN.Missing.Report'
Vlad Yasevich27852c22006-02-02 16:57:31 -08001658 * value larger than or equal to 3, mark that chunk for
Linus Torvalds1da177e2005-04-16 15:20:36 -07001659 * retransmission and start the fast retransmit procedure.
1660 */
1661
Vlad Yasevich27852c22006-02-02 16:57:31 -08001662 if (chunk->tsn_missing_report >= 3) {
Linus Torvalds1da177e2005-04-16 15:20:36 -07001663 chunk->fast_retransmit = 1;
1664 do_fast_retransmit = 1;
1665 }
1666 }
1667
1668 if (transport) {
1669 if (do_fast_retransmit)
1670 sctp_retransmit(q, transport, SCTP_RTXR_FAST_RTX);
1671
1672 SCTP_DEBUG_PRINTK("%s: transport: %p, cwnd: %d, "
1673 "ssthresh: %d, flight_size: %d, pba: %d\n",
Harvey Harrison0dc47872008-03-05 20:47:47 -08001674 __func__, transport, transport->cwnd,
YOSHIFUJI Hideakid808ad92007-02-09 23:25:18 +09001675 transport->ssthresh, transport->flight_size,
Linus Torvalds1da177e2005-04-16 15:20:36 -07001676 transport->partial_bytes_acked);
1677 }
1678}
1679
1680/* Is the given TSN acked by this packet? */
1681static int sctp_acked(struct sctp_sackhdr *sack, __u32 tsn)
1682{
1683 int i;
1684 sctp_sack_variable_t *frags;
1685 __u16 gap;
1686 __u32 ctsn = ntohl(sack->cum_tsn_ack);
1687
YOSHIFUJI Hideakid808ad92007-02-09 23:25:18 +09001688 if (TSN_lte(tsn, ctsn))
Linus Torvalds1da177e2005-04-16 15:20:36 -07001689 goto pass;
1690
1691 /* 3.3.4 Selective Acknowledgement (SACK) (3):
1692 *
1693 * Gap Ack Blocks:
1694 * These fields contain the Gap Ack Blocks. They are repeated
1695 * for each Gap Ack Block up to the number of Gap Ack Blocks
1696 * defined in the Number of Gap Ack Blocks field. All DATA
1697 * chunks with TSNs greater than or equal to (Cumulative TSN
1698 * Ack + Gap Ack Block Start) and less than or equal to
1699 * (Cumulative TSN Ack + Gap Ack Block End) of each Gap Ack
1700 * Block are assumed to have been received correctly.
1701 */
1702
1703 frags = sack->variable;
1704 gap = tsn - ctsn;
1705 for (i = 0; i < ntohs(sack->num_gap_ack_blocks); ++i) {
1706 if (TSN_lte(ntohs(frags[i].gab.start), gap) &&
1707 TSN_lte(gap, ntohs(frags[i].gab.end)))
1708 goto pass;
1709 }
1710
1711 return 0;
1712pass:
1713 return 1;
1714}
1715
1716static inline int sctp_get_skip_pos(struct sctp_fwdtsn_skip *skiplist,
Al Viro9f81bcd2006-11-20 17:26:34 -08001717 int nskips, __be16 stream)
Linus Torvalds1da177e2005-04-16 15:20:36 -07001718{
1719 int i;
1720
1721 for (i = 0; i < nskips; i++) {
1722 if (skiplist[i].stream == stream)
1723 return i;
1724 }
1725 return i;
1726}
1727
1728/* Create and add a fwdtsn chunk to the outq's control queue if needed. */
1729static void sctp_generate_fwdtsn(struct sctp_outq *q, __u32 ctsn)
1730{
1731 struct sctp_association *asoc = q->asoc;
1732 struct sctp_chunk *ftsn_chunk = NULL;
1733 struct sctp_fwdtsn_skip ftsn_skip_arr[10];
1734 int nskips = 0;
1735 int skip_pos = 0;
1736 __u32 tsn;
1737 struct sctp_chunk *chunk;
1738 struct list_head *lchunk, *temp;
1739
1740 /* PR-SCTP C1) Let SackCumAck be the Cumulative TSN ACK carried in the
1741 * received SACK.
YOSHIFUJI Hideakid808ad92007-02-09 23:25:18 +09001742 *
Linus Torvalds1da177e2005-04-16 15:20:36 -07001743 * If (Advanced.Peer.Ack.Point < SackCumAck), then update
1744 * Advanced.Peer.Ack.Point to be equal to SackCumAck.
1745 */
1746 if (TSN_lt(asoc->adv_peer_ack_point, ctsn))
1747 asoc->adv_peer_ack_point = ctsn;
1748
1749 /* PR-SCTP C2) Try to further advance the "Advanced.Peer.Ack.Point"
1750 * locally, that is, to move "Advanced.Peer.Ack.Point" up as long as
1751 * the chunk next in the out-queue space is marked as "abandoned" as
1752 * shown in the following example:
1753 *
1754 * Assuming that a SACK arrived with the Cumulative TSN ACK 102
1755 * and the Advanced.Peer.Ack.Point is updated to this value:
YOSHIFUJI Hideakid808ad92007-02-09 23:25:18 +09001756 *
Linus Torvalds1da177e2005-04-16 15:20:36 -07001757 * out-queue at the end of ==> out-queue after Adv.Ack.Point
1758 * normal SACK processing local advancement
1759 * ... ...
1760 * Adv.Ack.Pt-> 102 acked 102 acked
1761 * 103 abandoned 103 abandoned
1762 * 104 abandoned Adv.Ack.P-> 104 abandoned
1763 * 105 105
1764 * 106 acked 106 acked
1765 * ... ...
1766 *
1767 * In this example, the data sender successfully advanced the
1768 * "Advanced.Peer.Ack.Point" from 102 to 104 locally.
1769 */
1770 list_for_each_safe(lchunk, temp, &q->abandoned) {
1771 chunk = list_entry(lchunk, struct sctp_chunk,
1772 transmitted_list);
1773 tsn = ntohl(chunk->subh.data_hdr->tsn);
1774
1775 /* Remove any chunks in the abandoned queue that are acked by
1776 * the ctsn.
YOSHIFUJI Hideakid808ad92007-02-09 23:25:18 +09001777 */
Linus Torvalds1da177e2005-04-16 15:20:36 -07001778 if (TSN_lte(tsn, ctsn)) {
1779 list_del_init(lchunk);
Linus Torvalds1da177e2005-04-16 15:20:36 -07001780 sctp_chunk_free(chunk);
1781 } else {
1782 if (TSN_lte(tsn, asoc->adv_peer_ack_point+1)) {
1783 asoc->adv_peer_ack_point = tsn;
1784 if (chunk->chunk_hdr->flags &
1785 SCTP_DATA_UNORDERED)
1786 continue;
1787 skip_pos = sctp_get_skip_pos(&ftsn_skip_arr[0],
1788 nskips,
1789 chunk->subh.data_hdr->stream);
1790 ftsn_skip_arr[skip_pos].stream =
1791 chunk->subh.data_hdr->stream;
1792 ftsn_skip_arr[skip_pos].ssn =
1793 chunk->subh.data_hdr->ssn;
1794 if (skip_pos == nskips)
1795 nskips++;
1796 if (nskips == 10)
1797 break;
1798 } else
1799 break;
1800 }
1801 }
1802
1803 /* PR-SCTP C3) If, after step C1 and C2, the "Advanced.Peer.Ack.Point"
1804 * is greater than the Cumulative TSN ACK carried in the received
1805 * SACK, the data sender MUST send the data receiver a FORWARD TSN
1806 * chunk containing the latest value of the
1807 * "Advanced.Peer.Ack.Point".
1808 *
1809 * C4) For each "abandoned" TSN the sender of the FORWARD TSN SHOULD
1810 * list each stream and sequence number in the forwarded TSN. This
1811 * information will enable the receiver to easily find any
1812 * stranded TSN's waiting on stream reorder queues. Each stream
1813 * SHOULD only be reported once; this means that if multiple
1814 * abandoned messages occur in the same stream then only the
1815 * highest abandoned stream sequence number is reported. If the
1816 * total size of the FORWARD TSN does NOT fit in a single MTU then
1817 * the sender of the FORWARD TSN SHOULD lower the
1818 * Advanced.Peer.Ack.Point to the last TSN that will fit in a
1819 * single MTU.
1820 */
1821 if (asoc->adv_peer_ack_point > ctsn)
1822 ftsn_chunk = sctp_make_fwdtsn(asoc, asoc->adv_peer_ack_point,
YOSHIFUJI Hideakid808ad92007-02-09 23:25:18 +09001823 nskips, &ftsn_skip_arr[0]);
Linus Torvalds1da177e2005-04-16 15:20:36 -07001824
1825 if (ftsn_chunk) {
David S. Miller79af02c2005-07-08 21:47:49 -07001826 list_add_tail(&ftsn_chunk->list, &q->control_chunk_list);
Linus Torvalds1da177e2005-04-16 15:20:36 -07001827 SCTP_INC_STATS(SCTP_MIB_OUTCTRLCHUNKS);
1828 }
1829}