1 /* $NetBSD: tcp_sack.c,v 1.10.2.4 2006/11/11 20:48:34 bouyer Exp $ */
2
3 /*
4 * Copyright (c) 2005 The NetBSD Foundation, Inc.
5 * All rights reserved.
6 *
7 * This code is derived from software contributed to The NetBSD Foundation
8 * by Kentaro A. Kurahone.
9 *
10 * Redistribution and use in source and binary forms, with or without
11 * modification, are permitted provided that the following conditions
12 * are met:
13 * 1. Redistributions of source code must retain the above copyright
14 * notice, this list of conditions and the following disclaimer.
15 * 2. Redistributions in binary form must reproduce the above copyright
16 * notice, this list of conditions and the following disclaimer in the
17 * documentation and/or other materials provided with the distribution.
18 * 3. All advertising materials mentioning features or use of this software
19 * must display the following acknowledgement:
20 * This product includes software developed by the NetBSD
21 * Foundation, Inc. and its contributors.
22 * 4. Neither the name of The NetBSD Foundation nor the names of its
23 * contributors may be used to endorse or promote products derived
24 * from this software without specific prior written permission.
25 *
26 * THIS SOFTWARE IS PROVIDED BY THE NETBSD FOUNDATION, INC. AND CONTRIBUTORS
27 * ``AS IS'' AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED
28 * TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
29 * PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE FOUNDATION OR CONTRIBUTORS
30 * BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
31 * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
32 * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
33 * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
34 * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
35 * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
36 * POSSIBILITY OF SUCH DAMAGE.
37 */
38
39 /*
40 * Copyright (c) 1982, 1986, 1988, 1990, 1993, 1994, 1995
41 * The Regents of the University of California. All rights reserved.
42 *
43 * Redistribution and use in source and binary forms, with or without
44 * modification, are permitted provided that the following conditions
45 * are met:
46 * 1. Redistributions of source code must retain the above copyright
47 * notice, this list of conditions and the following disclaimer.
48 * 2. Redistributions in binary form must reproduce the above copyright
49 * notice, this list of conditions and the following disclaimer in the
50 * documentation and/or other materials provided with the distribution.
51 * 4. Neither the name of the University nor the names of its contributors
52 * may be used to endorse or promote products derived from this software
53 * without specific prior written permission.
54 *
55 * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
56 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
57 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
58 * ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
59 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
60 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
61 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
62 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
63 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
64 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
65 * SUCH DAMAGE.
66 *
67 * @(#)tcp_sack.c 8.12 (Berkeley) 5/24/95
68 * $FreeBSD: src/sys/netinet/tcp_sack.c,v 1.3.2.2 2004/12/25 23:02:57 rwatson Exp $
69 */
70
71 /*
72 * @@(#)COPYRIGHT 1.1 (NRL) 17 January 1995
73 *
74 * NRL grants permission for redistribution and use in source and binary
75 * forms, with or without modification, of the software and documentation
76 * created at NRL provided that the following conditions are met:
77 *
78 * 1. Redistributions of source code must retain the above copyright
79 * notice, this list of conditions and the following disclaimer.
80 * 2. Redistributions in binary form must reproduce the above copyright
81 * notice, this list of conditions and the following disclaimer in the
82 * documentation and/or other materials provided with the distribution.
83 * 3. All advertising materials mentioning features or use of this software
84 * must display the following acknowledgements:
85 * This product includes software developed by the University of
86 * California, Berkeley and its contributors.
87 * This product includes software developed at the Information
88 * Technology Division, US Naval Research Laboratory.
89 * 4. Neither the name of the NRL nor the names of its contributors
90 * may be used to endorse or promote products derived from this software
91 * without specific prior written permission.
92 *
93 * THE SOFTWARE PROVIDED BY NRL IS PROVIDED BY NRL AND CONTRIBUTORS ``AS
94 * IS'' AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED
95 * TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A
96 * PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL NRL OR
97 * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
98 * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
99 * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
100 * PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF
101 * LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING
102 * NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
103 * SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
104 *
105 * The views and conclusions contained in the software and documentation
106 * are those of the authors and should not be interpreted as representing
107 * official policies, either expressed or implied, of the US Naval
108 * Research Laboratory (NRL).
109 */
110
111 #include <sys/cdefs.h>
112 __KERNEL_RCSID(0, "$NetBSD: tcp_sack.c,v 1.10.2.4 2006/11/11 20:48:34 bouyer Exp $");
113
114 #include "opt_inet.h"
115 #include "opt_ipsec.h"
116 #include "opt_inet_csum.h"
117 #include "opt_tcp_debug.h"
118
119 #include <sys/param.h>
120 #include <sys/systm.h>
121 #include <sys/malloc.h>
122 #include <sys/mbuf.h>
123 #include <sys/protosw.h>
124 #include <sys/socket.h>
125 #include <sys/socketvar.h>
126 #include <sys/errno.h>
127 #include <sys/syslog.h>
128 #include <sys/pool.h>
129 #include <sys/domain.h>
130 #include <sys/kernel.h>
131
132 #include <net/if.h>
133 #include <net/route.h>
134 #include <net/if_types.h>
135
136 #include <netinet/in.h>
137 #include <netinet/in_systm.h>
138 #include <netinet/ip.h>
139 #include <netinet/in_pcb.h>
140 #include <netinet/in_var.h>
141 #include <netinet/ip_var.h>
142
143 #ifdef INET6
144 #ifndef INET
145 #include <netinet/in.h>
146 #endif
147 #include <netinet/ip6.h>
148 #include <netinet6/ip6_var.h>
149 #include <netinet6/in6_pcb.h>
150 #include <netinet6/ip6_var.h>
151 #include <netinet6/in6_var.h>
152 #include <netinet/icmp6.h>
153 #include <netinet6/nd6.h>
154 #endif
155
156 #ifndef INET6
157 /* always need ip6.h for IP6_EXTHDR_GET */
158 #include <netinet/ip6.h>
159 #endif
160
161 #include <netinet/tcp.h>
162 #include <netinet/tcp_fsm.h>
163 #include <netinet/tcp_seq.h>
164 #include <netinet/tcp_timer.h>
165 #include <netinet/tcp_var.h>
166 #include <netinet/tcpip.h>
167 #include <netinet/tcp_debug.h>
168
169 #include <machine/stdarg.h>
170
171 /* SACK block pool. */
172 POOL_INIT(sackhole_pool, sizeof(struct sackhole), 0, 0, 0, "sackholepl", NULL);
173
174 void
175 tcp_new_dsack(struct tcpcb *tp, tcp_seq seq, u_int32_t len)
176 {
177 if (TCP_SACK_ENABLED(tp)) {
178 tp->rcv_dsack_block.left = seq;
179 tp->rcv_dsack_block.right = seq + len;
180 tp->rcv_sack_flags |= TCPSACK_HAVED;
181 }
182 }
183
184 void
185 tcp_sack_option(struct tcpcb *tp, struct tcphdr *th, u_char *cp, int optlen)
186 {
187 struct sackblk
188 t_sack_block[(MAX_TCPOPTLEN - 2) / (sizeof(u_int32_t) * 2)];
189 struct sackblk *sack = NULL;
190 struct sackhole *cur = NULL;
191 struct sackhole *tmp = NULL;
192 char *lp = cp + 2;
193 int i, j, num_sack_blks;
194 tcp_seq left, right, acked;
195
196 /*
197 * If we aren't processing SACK responses, this is not an ACK
198 * or the peer sends us a sack option with invalid length, don't
199 * update the scoreboard.
200 */
201 if (!TCP_SACK_ENABLED(tp) || ((th->th_flags & TH_ACK) == 0) ||
202 (optlen % 8 != 2 || optlen < 10)) {
203 return;
204 }
205
206 /*
207 * If we don't want any SACK holes to be allocated, just return.
208 */
209 if (tcp_sack_globalmaxholes == 0 || tcp_sack_tp_maxholes == 0) {
210 return;
211 }
212
213 /* If the ACK is outside [snd_una, snd_max], ignore the SACK options. */
214 if (SEQ_LT(th->th_ack, tp->snd_una) || SEQ_GT(th->th_ack, tp->snd_max))
215 return;
216
217 /*
218 * Extract SACK blocks.
219 *
220 * Note that t_sack_block is sorted so that we only need to do
221 * one pass over the sequence number space. (SACK "fast-path")
222 */
223 num_sack_blks = optlen / 8;
224 acked = (SEQ_GT(th->th_ack, tp->snd_una)) ? th->th_ack : tp->snd_una;
225 for (i = 0; i < num_sack_blks; i++, lp += sizeof(uint32_t) * 2) {
226 memcpy(&left, lp, sizeof(uint32_t));
227 memcpy(&right, lp + sizeof(uint32_t), sizeof(uint32_t));
228 left = ntohl(left);
229 right = ntohl(right);
230
231 if (SEQ_LEQ(right, acked) || SEQ_GT(right, tp->snd_max) ||
232 SEQ_GEQ(left, right)) {
233 /* SACK entry that's old, or invalid. */
234 i--;
235 num_sack_blks--;
236 continue;
237 }
238
239 /* Insertion sort. */
240 for (j = i; (j > 0) && SEQ_LT(left, t_sack_block[j - 1].left);
241 j--) {
242 t_sack_block[j].left = t_sack_block[j - 1].left;
243 t_sack_block[j].right = t_sack_block[j - 1].right;
244 }
245 t_sack_block[j].left = left;
246 t_sack_block[j].right = right;
247 }
248
249 /* Update the scoreboard. */
250 cur = TAILQ_FIRST(&tp->snd_holes);
251 for (i = 0; i < num_sack_blks; i++) {
252 sack = &t_sack_block[i];
253 /*
254 * FACK TCP. Update snd_fack so we can enter Fast
255 * Recovery early.
256 */
257 if (SEQ_GEQ(sack->right, tp->snd_fack))
258 tp->snd_fack = sack->right;
259
260 if (TAILQ_EMPTY(&tp->snd_holes)) {
261 /* First hole. */
262 if (tcp_sack_globalholes >= tcp_sack_globalmaxholes) {
263 return;
264 }
265 cur = (struct sackhole *)
266 pool_get(&sackhole_pool, PR_NOWAIT);
267 if (cur == NULL) {
268 /* ENOBUFS, bail out*/
269 return;
270 }
271 cur->start = th->th_ack;
272 cur->end = sack->left;
273 cur->rxmit = cur->start;
274 tp->rcv_lastsack = sack->right;
275 tp->snd_numholes++;
276 tcp_sack_globalholes++;
277 TAILQ_INSERT_HEAD(&tp->snd_holes, cur, sackhole_q);
278 continue; /* With next sack block */
279 }
280
281 /* Go through the list of holes. */
282 while (cur) {
283 if (SEQ_LEQ(sack->right, cur->start))
284 /* SACKs data before the current hole */
285 break; /* No use going through more holes */
286
287 if (SEQ_GEQ(sack->left, cur->end)) {
288 /* SACKs data beyond the current hole */
289 cur = TAILQ_NEXT(cur, sackhole_q);
290 continue;
291 }
292
293 if (SEQ_LEQ(sack->left, cur->start)) {
294 /* Data acks at least the beginning of hole */
295 if (SEQ_GEQ(sack->right, cur->end)) {
296 /* Acks entire hole, so delete hole */
297 tmp = cur;
298 cur = TAILQ_NEXT(cur, sackhole_q);
299 tp->snd_numholes--;
300 tcp_sack_globalholes--;
301 TAILQ_REMOVE(&tp->snd_holes, tmp,
302 sackhole_q);
303 pool_put(&sackhole_pool, tmp);
304 break;
305 }
306
307 /* Otherwise, move start of hole forward */
308 cur->start = sack->right;
309 cur->rxmit = SEQ_MAX(cur->rxmit, cur->start);
310 break;
311 }
312
313 if (SEQ_GEQ(sack->right, cur->end)) {
314 /* Move end of hole backward. */
315 cur->end = sack->left;
316 cur->rxmit = SEQ_MIN(cur->rxmit, cur->end);
317 cur = TAILQ_NEXT(cur, sackhole_q);
318 break;
319 }
320
321 if (SEQ_LT(cur->start, sack->left) &&
322 SEQ_GT(cur->end, sack->right)) {
323 /*
324 * ACKs some data in middle of a hole; need to
325 * split current hole
326 */
327 if (tcp_sack_globalholes >=
328 tcp_sack_globalmaxholes ||
329 tp->snd_numholes >=
330 tcp_sack_tp_maxholes) {
331 return;
332 }
333 tmp = (struct sackhole *)
334 pool_get(&sackhole_pool, PR_NOWAIT);
335 if (tmp == NULL) {
336 /* ENOBUFS, bail out. */
337 return;
338 }
339 tmp->start = sack->right;
340 tmp->end = cur->end;
341 tmp->rxmit = SEQ_MAX(cur->rxmit, tmp->start);
342 cur->end = sack->left;
343 cur->rxmit = SEQ_MIN(cur->rxmit, cur->end);
344 tp->snd_numholes++;
345 tcp_sack_globalholes++;
346 TAILQ_INSERT_AFTER(&tp->snd_holes, cur, tmp,
347 sackhole_q);
348 cur = tmp;
349 break;
350 }
351 }
352
353 /* At this point, we have reached the tail of the list. */
354 if (SEQ_LT(tp->rcv_lastsack, sack->left)) {
355 /*
356 * Need to append new hole at end.
357 */
358 if (tcp_sack_globalholes >=
359 tcp_sack_globalmaxholes ||
360 tp->snd_numholes >=
361 tcp_sack_tp_maxholes) {
362 return;
363 }
364 tmp = (struct sackhole *)
365 pool_get(&sackhole_pool, PR_NOWAIT);
366 if (tmp == NULL)
367 continue; /* ENOBUFS */
368 tmp->start = tp->rcv_lastsack;
369 tmp->end = sack->left;
370 tmp->rxmit = tmp->start;
371 tp->snd_numholes++;
372 tcp_sack_globalholes++;
373 TAILQ_INSERT_TAIL(&tp->snd_holes, tmp, sackhole_q);
374 cur = tmp;
375 }
376 if (SEQ_LT(tp->rcv_lastsack, sack->right)) {
377 tp->rcv_lastsack = sack->right;
378 }
379 }
380 }
381
382 void
383 tcp_del_sackholes(struct tcpcb *tp, struct tcphdr *th)
384 {
385 /* Max because this could be an older ack that just arrived. */
386 tcp_seq lastack = SEQ_GT(th->th_ack, tp->snd_una) ?
387 th->th_ack : tp->snd_una;
388 struct sackhole *cur = TAILQ_FIRST(&tp->snd_holes);
389 struct sackhole *tmp;
390
391 while (cur) {
392 if (SEQ_LEQ(cur->end, lastack)) {
393 tmp = cur;
394 cur = TAILQ_NEXT(cur, sackhole_q);
395 tp->snd_numholes--;
396 tcp_sack_globalholes--;
397 TAILQ_REMOVE(&tp->snd_holes, tmp, sackhole_q);
398 pool_put(&sackhole_pool, tmp);
399 } else if (SEQ_LT(cur->start, lastack)) {
400 cur->start = lastack;
401 if (SEQ_LT(cur->rxmit, cur->start))
402 cur->rxmit = cur->start;
403 break;
404 } else
405 break;
406
407 }
408 }
409
410 void
411 tcp_free_sackholes(struct tcpcb *tp)
412 {
413 struct sackhole *sack;
414
415 /* Free up the SACK hole list. */
416 while (!TAILQ_EMPTY(&tp->snd_holes)) {
417 sack = TAILQ_FIRST(&tp->snd_holes);
418 tcp_sack_globalholes--;
419 TAILQ_REMOVE(&tp->snd_holes, sack, sackhole_q);
420 pool_put(&sackhole_pool, sack);
421 }
422
423 tp->snd_numholes = 0;
424 }
425
426 /*
427 * Implements the SACK response to a new ack, checking for partial acks
428 * in fast recovery.
429 */
430 void
431 tcp_sack_newack(struct tcpcb *tp, struct tcphdr *th)
432 {
433 if (tp->t_partialacks < 0) {
434 /*
435 * Not in fast recovery. Reset the duplicate ack
436 * counter.
437 */
438 tp->t_dupacks = 0;
439 } else if (SEQ_LT(th->th_ack, tp->snd_recover)) {
440 /*
441 * Partial ack handling within a sack recovery episode.
442 * Keeping this very simple for now. When a partial ack
443 * is received, force snd_cwnd to a value that will allow
444 * the sender to transmit no more than 2 segments.
445 * If necessary, a fancier scheme can be adopted at a
446 * later point, but for now, the goal is to prevent the
447 * sender from bursting a large amount of data in the midst
448 * of sack recovery.
449 */
450 int num_segs = 1;
451 int sack_bytes_rxmt = 0;
452
453 tp->t_partialacks++;
454 TCP_TIMER_DISARM(tp, TCPT_REXMT);
455 tp->t_rtttime = 0;
456
457 /*
458 * send one or 2 segments based on how much new data was acked
459 */
460 if (((th->th_ack - tp->snd_una) / tp->t_segsz) > 2)
461 num_segs = 2;
462 (void)tcp_sack_output(tp, &sack_bytes_rxmt);
463 tp->snd_cwnd = sack_bytes_rxmt +
464 (tp->snd_nxt - tp->sack_newdata) + num_segs * tp->t_segsz;
465 tp->t_flags |= TF_ACKNOW;
466 (void) tcp_output(tp);
467 } else {
468 /*
469 * Complete ack, inflate the congestion window to
470 * ssthresh and exit fast recovery.
471 *
472 * Window inflation should have left us with approx.
473 * snd_ssthresh outstanding data. But in case we
474 * would be inclined to send a burst, better to do
475 * it via the slow start mechanism.
476 */
477 if (SEQ_SUB(tp->snd_max, th->th_ack) < tp->snd_ssthresh)
478 tp->snd_cwnd = SEQ_SUB(tp->snd_max, th->th_ack)
479 + tp->t_segsz;
480 else
481 tp->snd_cwnd = tp->snd_ssthresh;
482 tp->t_partialacks = -1;
483 tp->t_dupacks = 0;
484 if (SEQ_GT(th->th_ack, tp->snd_fack))
485 tp->snd_fack = th->th_ack;
486 }
487 }
488
489 /*
490 * Returns pointer to a sackhole if there are any pending retransmissions;
491 * NULL otherwise.
492 */
493 struct sackhole *
494 tcp_sack_output(struct tcpcb *tp, int *sack_bytes_rexmt)
495 {
496 struct sackhole *cur = NULL;
497
498 if(!TCP_SACK_ENABLED(tp))
499 return (NULL);
500
501 *sack_bytes_rexmt = 0;
502 TAILQ_FOREACH(cur, &tp->snd_holes, sackhole_q) {
503 if (SEQ_LT(cur->rxmit, cur->end)) {
504 if (SEQ_LT(cur->rxmit, tp->snd_una)) {
505 /* old SACK hole */
506 continue;
507 }
508 *sack_bytes_rexmt += (cur->rxmit - cur->start);
509 break;
510 }
511 *sack_bytes_rexmt += (cur->rxmit - cur->start);
512 }
513
514 return (cur);
515 }
516
517 /*
518 * After a timeout, the SACK list may be rebuilt. This SACK information
519 * should be used to avoid retransmitting SACKed data. This function
520 * traverses the SACK list to see if snd_nxt should be moved forward.
521 */
522 void
523 tcp_sack_adjust(struct tcpcb *tp)
524 {
525 struct sackhole *cur = TAILQ_FIRST(&tp->snd_holes);
526 struct sackhole *n = NULL;
527
528 if (TAILQ_EMPTY(&tp->snd_holes))
529 return; /* No holes */
530 if (SEQ_GEQ(tp->snd_nxt, tp->rcv_lastsack))
531 return; /* We're already beyond any SACKed blocks */
532
533 /*
534 * Two cases for which we want to advance snd_nxt:
535 * i) snd_nxt lies between end of one hole and beginning of another
536 * ii) snd_nxt lies between end of last hole and rcv_lastsack
537 */
538 while ((n = TAILQ_NEXT(cur, sackhole_q)) != NULL) {
539 if (SEQ_LT(tp->snd_nxt, cur->end))
540 return;
541 if (SEQ_GEQ(tp->snd_nxt, n->start))
542 cur = n;
543 else {
544 tp->snd_nxt = n->start;
545 return;
546 }
547 }
548 if (SEQ_LT(tp->snd_nxt, cur->end))
549 return;
550 tp->snd_nxt = tp->rcv_lastsack;
551
552 return;
553 }
554
555 int
556 tcp_sack_numblks(const struct tcpcb *tp)
557 {
558 int numblks;
559
560 if (!TCP_SACK_ENABLED(tp)) {
561 return 0;
562 }
563
564 numblks = (((tp->rcv_sack_flags & TCPSACK_HAVED) != 0) ? 1 : 0) +
565 tp->t_segqlen;
566
567 if (numblks == 0) {
568 return 0;
569 }
570
571 if (numblks > TCP_SACK_MAX) {
572 numblks = TCP_SACK_MAX;
573 }
574
575 return numblks;
576 }
Cache object: 3a279828867f4c509f045c4634a8a60f
|