xref: /freebsd/sys/netinet/tcp_sack.c (revision acd3428b7d3e94cef0e1881c868cb4b131d4ff41)
1 /*-
2  * Copyright (c) 1982, 1986, 1988, 1990, 1993, 1994, 1995
3  *	The Regents of the University of California.  All rights reserved.
4  *
5  * Redistribution and use in source and binary forms, with or without
6  * modification, are permitted provided that the following conditions
7  * are met:
8  * 1. Redistributions of source code must retain the above copyright
9  *    notice, this list of conditions and the following disclaimer.
10  * 2. Redistributions in binary form must reproduce the above copyright
11  *    notice, this list of conditions and the following disclaimer in the
12  *    documentation and/or other materials provided with the distribution.
13  * 4. Neither the name of the University nor the names of its contributors
14  *    may be used to endorse or promote products derived from this software
15  *    without specific prior written permission.
16  *
17  * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
18  * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
19  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
20  * ARE DISCLAIMED.  IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
21  * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
22  * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
23  * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
24  * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
25  * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
26  * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
27  * SUCH DAMAGE.
28  *
29  *	@(#)tcp_sack.c	8.12 (Berkeley) 5/24/95
30  * $FreeBSD$
31  */
32 
33 /*-
34  * Copyright (c) 1982, 1986, 1988, 1990, 1993, 1994
35  *	The Regents of the University of California.  All rights reserved.
36  *
37  * Redistribution and use in source and binary forms, with or without
38  * modification, are permitted provided that the following conditions
39  * are met:
40  * 1. Redistributions of source code must retain the above copyright
41  *    notice, this list of conditions and the following disclaimer.
42  * 2. Redistributions in binary form must reproduce the above copyright
43  *    notice, this list of conditions and the following disclaimer in the
44  *    documentation and/or other materials provided with the distribution.
45  * 3. Neither the name of the University nor the names of its contributors
46  *    may be used to endorse or promote products derived from this software
47  *    without specific prior written permission.
48  *
49  * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
50  * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
51  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
52  * ARE DISCLAIMED.  IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
53  * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
54  * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
55  * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
56  * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
57  * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
58  * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
59  * SUCH DAMAGE.
60  *
61  *	@@(#)COPYRIGHT	1.1 (NRL) 17 January 1995
62  *
63  * NRL grants permission for redistribution and use in source and binary
64  * forms, with or without modification, of the software and documentation
65  * created at NRL provided that the following conditions are met:
66  *
67  * 1. Redistributions of source code must retain the above copyright
68  *    notice, this list of conditions and the following disclaimer.
69  * 2. Redistributions in binary form must reproduce the above copyright
70  *    notice, this list of conditions and the following disclaimer in the
71  *    documentation and/or other materials provided with the distribution.
72  * 3. All advertising materials mentioning features or use of this software
73  *    must display the following acknowledgements:
74  *	This product includes software developed by the University of
75  *	California, Berkeley and its contributors.
76  *	This product includes software developed at the Information
77  *	Technology Division, US Naval Research Laboratory.
78  * 4. Neither the name of the NRL nor the names of its contributors
79  *    may be used to endorse or promote products derived from this software
80  *    without specific prior written permission.
81  *
82  * THE SOFTWARE PROVIDED BY NRL IS PROVIDED BY NRL AND CONTRIBUTORS ``AS
83  * IS'' AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED
84  * TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A
85  * PARTICULAR PURPOSE ARE DISCLAIMED.  IN NO EVENT SHALL NRL OR
86  * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
87  * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
88  * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
89  * PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF
90  * LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING
91  * NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
92  * SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
93  *
94  * The views and conclusions contained in the software and documentation
95  * are those of the authors and should not be interpreted as representing
96  * official policies, either expressed or implied, of the US Naval
97  * Research Laboratory (NRL).
98  */
99 #include "opt_inet.h"
100 #include "opt_inet6.h"
101 #include "opt_tcpdebug.h"
102 #include "opt_tcp_input.h"
103 #include "opt_tcp_sack.h"
104 
105 #include <sys/param.h>
106 #include <sys/systm.h>
107 #include <sys/kernel.h>
108 #include <sys/sysctl.h>
109 #include <sys/malloc.h>
110 #include <sys/mbuf.h>
111 #include <sys/proc.h>		/* for proc0 declaration */
112 #include <sys/protosw.h>
113 #include <sys/socket.h>
114 #include <sys/socketvar.h>
115 #include <sys/syslog.h>
116 #include <sys/systm.h>
117 
118 #include <machine/cpu.h>	/* before tcp_seq.h, for tcp_random18() */
119 
120 #include <vm/uma.h>
121 
122 #include <net/if.h>
123 #include <net/route.h>
124 
125 #include <netinet/in.h>
126 #include <netinet/in_systm.h>
127 #include <netinet/ip.h>
128 #include <netinet/in_var.h>
129 #include <netinet/in_pcb.h>
130 #include <netinet/ip_var.h>
131 #include <netinet/ip6.h>
132 #include <netinet/icmp6.h>
133 #include <netinet6/nd6.h>
134 #include <netinet6/ip6_var.h>
135 #include <netinet6/in6_pcb.h>
136 #include <netinet/tcp.h>
137 #include <netinet/tcp_fsm.h>
138 #include <netinet/tcp_seq.h>
139 #include <netinet/tcp_timer.h>
140 #include <netinet/tcp_var.h>
141 #include <netinet6/tcp6_var.h>
142 #include <netinet/tcpip.h>
143 #ifdef TCPDEBUG
144 #include <netinet/tcp_debug.h>
145 #endif /* TCPDEBUG */
146 
147 #include <machine/in_cksum.h>
148 
149 extern struct uma_zone *sack_hole_zone;
150 
151 SYSCTL_NODE(_net_inet_tcp, OID_AUTO, sack, CTLFLAG_RW, 0, "TCP SACK");
152 int tcp_do_sack = 1;
153 SYSCTL_INT(_net_inet_tcp_sack, OID_AUTO, enable, CTLFLAG_RW,
154 	&tcp_do_sack, 0, "Enable/Disable TCP SACK support");
155 TUNABLE_INT("net.inet.tcp.sack.enable", &tcp_do_sack);
156 
157 static int tcp_sack_maxholes = 128;
158 SYSCTL_INT(_net_inet_tcp_sack, OID_AUTO, maxholes, CTLFLAG_RW,
159 	&tcp_sack_maxholes, 0,
160     "Maximum number of TCP SACK holes allowed per connection");
161 
162 static int tcp_sack_globalmaxholes = 65536;
163 SYSCTL_INT(_net_inet_tcp_sack, OID_AUTO, globalmaxholes, CTLFLAG_RW,
164 	&tcp_sack_globalmaxholes, 0,
165     "Global maximum number of TCP SACK holes");
166 
167 static int tcp_sack_globalholes = 0;
168 SYSCTL_INT(_net_inet_tcp_sack, OID_AUTO, globalholes, CTLFLAG_RD,
169     &tcp_sack_globalholes, 0,
170     "Global number of TCP SACK holes currently allocated");
171 
172 /*
173  * This function is called upon receipt of new valid data (while not in header
174  * prediction mode), and it updates the ordered list of sacks.
175  */
176 void
177 tcp_update_sack_list(struct tcpcb *tp, tcp_seq rcv_start, tcp_seq rcv_end)
178 {
179 	/*
180 	 * First reported block MUST be the most recent one.  Subsequent
181 	 * blocks SHOULD be in the order in which they arrived at the
182 	 * receiver.  These two conditions make the implementation fully
183 	 * compliant with RFC 2018.
184 	 */
185 	struct sackblk head_blk, saved_blks[MAX_SACK_BLKS];
186 	int num_head, num_saved, i;
187 
188 	INP_LOCK_ASSERT(tp->t_inpcb);
189 
190 	/* Check arguments */
191 	KASSERT(SEQ_LT(rcv_start, rcv_end), ("rcv_start < rcv_end"));
192 
193 	/* SACK block for the received segment. */
194 	head_blk.start = rcv_start;
195 	head_blk.end = rcv_end;
196 
197 	/*
198 	 * Merge updated SACK blocks into head_blk, and
199 	 * save unchanged SACK blocks into saved_blks[].
200 	 * num_saved will have the number of the saved SACK blocks.
201 	 */
202 	num_saved = 0;
203 	for (i = 0; i < tp->rcv_numsacks; i++) {
204 		tcp_seq start = tp->sackblks[i].start;
205 		tcp_seq end = tp->sackblks[i].end;
206 		if (SEQ_GEQ(start, end) || SEQ_LEQ(start, tp->rcv_nxt)) {
207 			/*
208 			 * Discard this SACK block.
209 			 */
210 		} else if (SEQ_LEQ(head_blk.start, end) &&
211 			   SEQ_GEQ(head_blk.end, start)) {
212 			/*
213 			 * Merge this SACK block into head_blk.
214 			 * This SACK block itself will be discarded.
215 			 */
216 			if (SEQ_GT(head_blk.start, start))
217 				head_blk.start = start;
218 			if (SEQ_LT(head_blk.end, end))
219 				head_blk.end = end;
220 		} else {
221 			/*
222 			 * Save this SACK block.
223 			 */
224 			saved_blks[num_saved].start = start;
225 			saved_blks[num_saved].end = end;
226 			num_saved++;
227 		}
228 	}
229 
230 	/*
231 	 * Update SACK list in tp->sackblks[].
232 	 */
233 	num_head = 0;
234 	if (SEQ_GT(head_blk.start, tp->rcv_nxt)) {
235 		/*
236 		 * The received data segment is an out-of-order segment.
237 		 * Put head_blk at the top of SACK list.
238 		 */
239 		tp->sackblks[0] = head_blk;
240 		num_head = 1;
241 		/*
242 		 * If the number of saved SACK blocks exceeds its limit,
243 		 * discard the last SACK block.
244 		 */
245 		if (num_saved >= MAX_SACK_BLKS)
246 			num_saved--;
247 	}
248 	if (num_saved > 0) {
249 		/*
250 		 * Copy the saved SACK blocks back.
251 		 */
252 		bcopy(saved_blks, &tp->sackblks[num_head],
253 		      sizeof(struct sackblk) * num_saved);
254 	}
255 
256 	/* Save the number of SACK blocks. */
257 	tp->rcv_numsacks = num_head + num_saved;
258 }
259 
260 /*
261  * Delete all receiver-side SACK information.
262  */
263 void
264 tcp_clean_sackreport(tp)
265 	struct tcpcb *tp;
266 {
267 	int i;
268 
269 	INP_LOCK_ASSERT(tp->t_inpcb);
270 	tp->rcv_numsacks = 0;
271 	for (i = 0; i < MAX_SACK_BLKS; i++)
272 		tp->sackblks[i].start = tp->sackblks[i].end=0;
273 }
274 
275 /*
276  * Allocate struct sackhole.
277  */
278 static struct sackhole *
279 tcp_sackhole_alloc(struct tcpcb *tp, tcp_seq start, tcp_seq end)
280 {
281 	struct sackhole *hole;
282 
283 	if (tp->snd_numholes >= tcp_sack_maxholes ||
284 	    tcp_sack_globalholes >= tcp_sack_globalmaxholes) {
285 		tcpstat.tcps_sack_sboverflow++;
286 		return NULL;
287 	}
288 
289 	hole = (struct sackhole *)uma_zalloc(sack_hole_zone, M_NOWAIT);
290 	if (hole == NULL)
291 		return NULL;
292 
293 	hole->start = start;
294 	hole->end = end;
295 	hole->rxmit = start;
296 
297 	tp->snd_numholes++;
298 	tcp_sack_globalholes++;
299 
300 	return hole;
301 }
302 
303 /*
304  * Free struct sackhole.
305  */
306 static void
307 tcp_sackhole_free(struct tcpcb *tp, struct sackhole *hole)
308 {
309 	uma_zfree(sack_hole_zone, hole);
310 
311 	tp->snd_numholes--;
312 	tcp_sack_globalholes--;
313 
314 	KASSERT(tp->snd_numholes >= 0, ("tp->snd_numholes >= 0"));
315 	KASSERT(tcp_sack_globalholes >= 0, ("tcp_sack_globalholes >= 0"));
316 }
317 
318 /*
319  * Insert new SACK hole into scoreboard.
320  */
321 static struct sackhole *
322 tcp_sackhole_insert(struct tcpcb *tp, tcp_seq start, tcp_seq end,
323 		    struct sackhole *after)
324 {
325 	struct sackhole *hole;
326 
327 	/* Allocate a new SACK hole. */
328 	hole = tcp_sackhole_alloc(tp, start, end);
329 	if (hole == NULL)
330 		return NULL;
331 
332 	/* Insert the new SACK hole into scoreboard */
333 	if (after != NULL)
334 		TAILQ_INSERT_AFTER(&tp->snd_holes, after, hole, scblink);
335 	else
336 		TAILQ_INSERT_TAIL(&tp->snd_holes, hole, scblink);
337 
338 	/* Update SACK hint. */
339 	if (tp->sackhint.nexthole == NULL)
340 		tp->sackhint.nexthole = hole;
341 
342 	return hole;
343 }
344 
345 /*
346  * Remove SACK hole from scoreboard.
347  */
348 static void
349 tcp_sackhole_remove(struct tcpcb *tp, struct sackhole *hole)
350 {
351 	/* Update SACK hint. */
352 	if (tp->sackhint.nexthole == hole)
353 		tp->sackhint.nexthole = TAILQ_NEXT(hole, scblink);
354 
355 	/* Remove this SACK hole. */
356 	TAILQ_REMOVE(&tp->snd_holes, hole, scblink);
357 
358 	/* Free this SACK hole. */
359 	tcp_sackhole_free(tp, hole);
360 }
361 
362 /*
363  * Process cumulative ACK and the TCP SACK option to update the scoreboard.
364  * tp->snd_holes is an ordered list of holes (oldest to newest, in terms of
365  * the sequence space).
366  */
367 void
368 tcp_sack_doack(struct tcpcb *tp, struct tcpopt *to, tcp_seq th_ack)
369 {
370 	struct sackhole *cur, *temp;
371 	struct sackblk sack, sack_blocks[TCP_MAX_SACK + 1], *sblkp;
372 	int i, j, num_sack_blks;
373 
374 	INP_LOCK_ASSERT(tp->t_inpcb);
375 
376 	num_sack_blks = 0;
377 	/*
378 	 * If SND.UNA will be advanced by SEG.ACK, and if SACK holes exist,
379 	 * treat [SND.UNA, SEG.ACK) as if it is a SACK block.
380 	 */
381 	if (SEQ_LT(tp->snd_una, th_ack) && !TAILQ_EMPTY(&tp->snd_holes)) {
382 		sack_blocks[num_sack_blks].start = tp->snd_una;
383 		sack_blocks[num_sack_blks++].end = th_ack;
384 	}
385 	/*
386 	 * Append received valid SACK blocks to sack_blocks[].
387 	 */
388 	for (i = 0; i < to->to_nsacks; i++) {
389 		bcopy((to->to_sacks + i * TCPOLEN_SACK), &sack, sizeof(sack));
390 		sack.start = ntohl(sack.start);
391 		sack.end = ntohl(sack.end);
392 		if (SEQ_GT(sack.end, sack.start) &&
393 		    SEQ_GT(sack.start, tp->snd_una) &&
394 		    SEQ_GT(sack.start, th_ack) &&
395 		    SEQ_LT(sack.start, tp->snd_max) &&
396 		    SEQ_GT(sack.end, tp->snd_una) &&
397 		    SEQ_LEQ(sack.end, tp->snd_max))
398 			sack_blocks[num_sack_blks++] = sack;
399 	}
400 
401 	/*
402 	 * Return if SND.UNA is not advanced and no valid SACK block
403 	 * is received.
404 	 */
405 	if (num_sack_blks == 0)
406 		return;
407 
408 	/*
409 	 * Sort the SACK blocks so we can update the scoreboard
410 	 * with just one pass. The overhead of sorting upto 4+1 elements
411 	 * is less than making upto 4+1 passes over the scoreboard.
412 	 */
413 	for (i = 0; i < num_sack_blks; i++) {
414 		for (j = i + 1; j < num_sack_blks; j++) {
415 			if (SEQ_GT(sack_blocks[i].end, sack_blocks[j].end)) {
416 				sack = sack_blocks[i];
417 				sack_blocks[i] = sack_blocks[j];
418 				sack_blocks[j] = sack;
419 			}
420 		}
421 	}
422 	if (TAILQ_EMPTY(&tp->snd_holes))
423 		/*
424 		 * Empty scoreboard. Need to initialize snd_fack (it may be
425 		 * uninitialized or have a bogus value). Scoreboard holes
426 		 * (from the sack blocks received) are created later below (in
427 		 * the logic that adds holes to the tail of the scoreboard).
428 		 */
429 		tp->snd_fack = SEQ_MAX(tp->snd_una, th_ack);
430 	/*
431 	 * In the while-loop below, incoming SACK blocks (sack_blocks[])
432 	 * and SACK holes (snd_holes) are traversed from their tails with
433 	 * just one pass in order to reduce the number of compares especially
434 	 * when the bandwidth-delay product is large.
435 	 * Note: Typically, in the first RTT of SACK recovery, the highest
436 	 * three or four SACK blocks with the same ack number are received.
437 	 * In the second RTT, if retransmitted data segments are not lost,
438 	 * the highest three or four SACK blocks with ack number advancing
439 	 * are received.
440 	 */
441 	sblkp = &sack_blocks[num_sack_blks - 1];	/* Last SACK block */
442 	if (SEQ_LT(tp->snd_fack, sblkp->start)) {
443 		/*
444 		 * The highest SACK block is beyond fack.
445 		 * Append new SACK hole at the tail.
446 		 * If the second or later highest SACK blocks are also
447 		 * beyond the current fack, they will be inserted by
448 		 * way of hole splitting in the while-loop below.
449 		 */
450 		temp = tcp_sackhole_insert(tp, tp->snd_fack,sblkp->start,NULL);
451 		if (temp != NULL) {
452 			tp->snd_fack = sblkp->end;
453 			/* Go to the previous sack block. */
454 			sblkp--;
455 		} else {
456 			/*
457 			 * We failed to add a new hole based on the current
458 			 * sack block.  Skip over all the sack blocks that
459 			 * fall completely to the right of snd_fack and proceed
460 			 * to trim the scoreboard based on the remaining sack
461 			 * blocks. This also trims the scoreboard for th_ack
462 			 * (which is sack_blocks[0]).
463 			 */
464 			while (sblkp >= sack_blocks &&
465 			       SEQ_LT(tp->snd_fack, sblkp->start))
466 				sblkp--;
467 			if (sblkp >= sack_blocks &&
468 			    SEQ_LT(tp->snd_fack, sblkp->end))
469 				tp->snd_fack = sblkp->end;
470 		}
471 	} else if (SEQ_LT(tp->snd_fack, sblkp->end))
472 		/* fack is advanced. */
473 		tp->snd_fack = sblkp->end;
474 	/* We must have at least one SACK hole in scoreboard */
475 	KASSERT(!TAILQ_EMPTY(&tp->snd_holes), ("SACK scoreboard must not be empty"));
476 	cur = TAILQ_LAST(&tp->snd_holes, sackhole_head); /* Last SACK hole */
477 	/*
478 	 * Since the incoming sack blocks are sorted, we can process them
479 	 * making one sweep of the scoreboard.
480 	 */
481 	while (sblkp >= sack_blocks  && cur != NULL) {
482 		if (SEQ_GEQ(sblkp->start, cur->end)) {
483 			/*
484 			 * SACKs data beyond the current hole.
485 			 * Go to the previous sack block.
486 			 */
487 			sblkp--;
488 			continue;
489 		}
490 		if (SEQ_LEQ(sblkp->end, cur->start)) {
491 			/*
492 			 * SACKs data before the current hole.
493 			 * Go to the previous hole.
494 			 */
495 			cur = TAILQ_PREV(cur, sackhole_head, scblink);
496 			continue;
497 		}
498 		tp->sackhint.sack_bytes_rexmit -= (cur->rxmit - cur->start);
499 		KASSERT(tp->sackhint.sack_bytes_rexmit >= 0,
500 			("sackhint bytes rtx >= 0"));
501 		if (SEQ_LEQ(sblkp->start, cur->start)) {
502 			/* Data acks at least the beginning of hole */
503 			if (SEQ_GEQ(sblkp->end, cur->end)) {
504 				/* Acks entire hole, so delete hole */
505 				temp = cur;
506 				cur = TAILQ_PREV(cur, sackhole_head, scblink);
507 				tcp_sackhole_remove(tp, temp);
508 				/*
509 				 * The sack block may ack all or part of the next
510 				 * hole too, so continue onto the next hole.
511 				 */
512 				continue;
513 			} else {
514 				/* Move start of hole forward */
515 				cur->start = sblkp->end;
516 				cur->rxmit = SEQ_MAX(cur->rxmit, cur->start);
517 			}
518 		} else {
519 			/* Data acks at least the end of hole */
520 			if (SEQ_GEQ(sblkp->end, cur->end)) {
521 				/* Move end of hole backward */
522 				cur->end = sblkp->start;
523 				cur->rxmit = SEQ_MIN(cur->rxmit, cur->end);
524 			} else {
525 				/*
526 				 * ACKs some data in middle of a hole; need to
527 				 * split current hole
528 				 */
529 				temp = tcp_sackhole_insert(tp, sblkp->end,
530 							   cur->end, cur);
531 				if (temp != NULL) {
532 					if (SEQ_GT(cur->rxmit, temp->rxmit)) {
533 						temp->rxmit = cur->rxmit;
534 						tp->sackhint.sack_bytes_rexmit
535 							+= (temp->rxmit
536 							    - temp->start);
537 					}
538 					cur->end = sblkp->start;
539 					cur->rxmit = SEQ_MIN(cur->rxmit,
540 							     cur->end);
541 				}
542 			}
543 		}
544 		tp->sackhint.sack_bytes_rexmit += (cur->rxmit - cur->start);
545 		/*
546 		 * Testing sblkp->start against cur->start tells us whether
547 		 * we're done with the sack block or the sack hole.
548 		 * Accordingly, we advance one or the other.
549 		 */
550 		if (SEQ_LEQ(sblkp->start, cur->start))
551 			cur = TAILQ_PREV(cur, sackhole_head, scblink);
552 		else
553 			sblkp--;
554 	}
555 }
556 
557 /*
558  * Free all SACK holes to clear the scoreboard.
559  */
560 void
561 tcp_free_sackholes(struct tcpcb *tp)
562 {
563 	struct sackhole *q;
564 
565 	INP_LOCK_ASSERT(tp->t_inpcb);
566 	while ((q = TAILQ_FIRST(&tp->snd_holes)) != NULL)
567 		tcp_sackhole_remove(tp, q);
568 	tp->sackhint.sack_bytes_rexmit = 0;
569 
570 	KASSERT(tp->snd_numholes == 0, ("tp->snd_numholes == 0"));
571 	KASSERT(tp->sackhint.nexthole == NULL,
572 		("tp->sackhint.nexthole == NULL"));
573 }
574 
575 /*
576  * Partial ack handling within a sack recovery episode.
577  * Keeping this very simple for now. When a partial ack
578  * is received, force snd_cwnd to a value that will allow
579  * the sender to transmit no more than 2 segments.
580  * If necessary, a better scheme can be adopted at a
581  * later point, but for now, the goal is to prevent the
582  * sender from bursting a large amount of data in the midst
583  * of sack recovery.
584  */
585 void
586 tcp_sack_partialack(tp, th)
587 	struct tcpcb *tp;
588 	struct tcphdr *th;
589 {
590 	int num_segs = 1;
591 
592 	INP_LOCK_ASSERT(tp->t_inpcb);
593 	callout_stop(tp->tt_rexmt);
594 	tp->t_rtttime = 0;
595 	/* send one or 2 segments based on how much new data was acked */
596 	if (((th->th_ack - tp->snd_una) / tp->t_maxseg) > 2)
597 		num_segs = 2;
598 	tp->snd_cwnd = (tp->sackhint.sack_bytes_rexmit +
599 		(tp->snd_nxt - tp->sack_newdata) +
600 		num_segs * tp->t_maxseg);
601 	if (tp->snd_cwnd > tp->snd_ssthresh)
602 		tp->snd_cwnd = tp->snd_ssthresh;
603 	tp->t_flags |= TF_ACKNOW;
604 	(void) tcp_output(tp);
605 }
606 
607 #if 0
608 /*
609  * Debug version of tcp_sack_output() that walks the scoreboard. Used for
610  * now to sanity check the hint.
611  */
612 static struct sackhole *
613 tcp_sack_output_debug(struct tcpcb *tp, int *sack_bytes_rexmt)
614 {
615 	struct sackhole *p;
616 
617 	INP_LOCK_ASSERT(tp->t_inpcb);
618 	*sack_bytes_rexmt = 0;
619 	TAILQ_FOREACH(p, &tp->snd_holes, scblink) {
620 		if (SEQ_LT(p->rxmit, p->end)) {
621 			if (SEQ_LT(p->rxmit, tp->snd_una)) {/* old SACK hole */
622 				continue;
623 			}
624 			*sack_bytes_rexmt += (p->rxmit - p->start);
625 			break;
626 		}
627 		*sack_bytes_rexmt += (p->rxmit - p->start);
628 	}
629 	return (p);
630 }
631 #endif
632 
633 /*
634  * Returns the next hole to retransmit and the number of retransmitted bytes
635  * from the scoreboard. We store both the next hole and the number of
636  * retransmitted bytes as hints (and recompute these on the fly upon SACK/ACK
637  * reception). This avoids scoreboard traversals completely.
638  *
639  * The loop here will traverse *at most* one link. Here's the argument.
640  * For the loop to traverse more than 1 link before finding the next hole to
641  * retransmit, we would need to have at least 1 node following the current hint
642  * with (rxmit == end). But, for all holes following the current hint,
643  * (start == rxmit), since we have not yet retransmitted from them. Therefore,
644  * in order to traverse more 1 link in the loop below, we need to have at least
645  * one node following the current hint with (start == rxmit == end).
646  * But that can't happen, (start == end) means that all the data in that hole
647  * has been sacked, in which case, the hole would have been removed from the
648  * scoreboard.
649  */
650 struct sackhole *
651 tcp_sack_output(struct tcpcb *tp, int *sack_bytes_rexmt)
652 {
653 	struct sackhole *hole = NULL;
654 
655 	INP_LOCK_ASSERT(tp->t_inpcb);
656 	*sack_bytes_rexmt = tp->sackhint.sack_bytes_rexmit;
657 	hole = tp->sackhint.nexthole;
658 	if (hole == NULL || SEQ_LT(hole->rxmit, hole->end))
659 		goto out;
660 	while ((hole = TAILQ_NEXT(hole, scblink)) != NULL) {
661 		if (SEQ_LT(hole->rxmit, hole->end)) {
662 			tp->sackhint.nexthole = hole;
663 			break;
664 		}
665 	}
666 out:
667 	return (hole);
668 }
669 
670 /*
671  * After a timeout, the SACK list may be rebuilt.  This SACK information
672  * should be used to avoid retransmitting SACKed data.  This function
673  * traverses the SACK list to see if snd_nxt should be moved forward.
674  */
675 void
676 tcp_sack_adjust(struct tcpcb *tp)
677 {
678 	struct sackhole *p, *cur = TAILQ_FIRST(&tp->snd_holes);
679 
680 	INP_LOCK_ASSERT(tp->t_inpcb);
681 	if (cur == NULL)
682 		return; /* No holes */
683 	if (SEQ_GEQ(tp->snd_nxt, tp->snd_fack))
684 		return; /* We're already beyond any SACKed blocks */
685 	/*
686 	 * Two cases for which we want to advance snd_nxt:
687 	 * i) snd_nxt lies between end of one hole and beginning of another
688 	 * ii) snd_nxt lies between end of last hole and snd_fack
689 	 */
690 	while ((p = TAILQ_NEXT(cur, scblink)) != NULL) {
691 		if (SEQ_LT(tp->snd_nxt, cur->end))
692 			return;
693 		if (SEQ_GEQ(tp->snd_nxt, p->start))
694 			cur = p;
695 		else {
696 			tp->snd_nxt = p->start;
697 			return;
698 		}
699 	}
700 	if (SEQ_LT(tp->snd_nxt, cur->end))
701 		return;
702 	tp->snd_nxt = tp->snd_fack;
703 	return;
704 }
705