| 1 | /* |
| 2 | * Copyright (c) 2003, 2004 Jeffrey M. Hsu. All rights reserved. |
| 3 | * Copyright (c) 2003, 2004 The DragonFly Project. All rights reserved. |
| 4 | * |
| 5 | * This code is derived from software contributed to The DragonFly Project |
| 6 | * by Jeffrey M. Hsu. |
| 7 | * |
| 8 | * Redistribution and use in source and binary forms, with or without |
| 9 | * modification, are permitted provided that the following conditions |
| 10 | * are met: |
| 11 | * 1. Redistributions of source code must retain the above copyright |
| 12 | * notice, this list of conditions and the following disclaimer. |
| 13 | * 2. Redistributions in binary form must reproduce the above copyright |
| 14 | * notice, this list of conditions and the following disclaimer in the |
| 15 | * documentation and/or other materials provided with the distribution. |
| 16 | * 3. Neither the name of The DragonFly Project nor the names of its |
| 17 | * contributors may be used to endorse or promote products derived |
| 18 | * from this software without specific, prior written permission. |
| 19 | * |
| 20 | * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS |
| 21 | * ``AS IS'' AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT |
| 22 | * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS |
| 23 | * FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE |
| 24 | * COPYRIGHT HOLDERS OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, |
| 25 | * INCIDENTAL, SPECIAL, EXEMPLARY OR CONSEQUENTIAL DAMAGES (INCLUDING, |
| 26 | * BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; |
| 27 | * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED |
| 28 | * AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, |
| 29 | * OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT |
| 30 | * OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF |
| 31 | * SUCH DAMAGE. |
| 32 | * |
| 33 | * $DragonFly: src/sys/netinet/tcp_sack.c,v 1.1 2004/11/14 00:49:08 hsu Exp $ |
| 34 | */ |
| 35 | |
| 36 | /* |
| 37 | * Copyright (c) 2003, 2004 Jeffrey M. Hsu. All rights reserved. |
| 38 | * |
| 39 | * License terms: all terms for the DragonFly license above plus the following: |
| 40 | * |
| 41 | * 4. All advertising materials mentioning features or use of this software |
| 42 | * must display the following acknowledgement: |
| 43 | * |
| 44 | * This product includes software developed by Jeffrey M. Hsu |
| 45 | * for the DragonFly Project. |
| 46 | * |
| 47 | * This requirement may be waived with permission from Jeffrey Hsu. |
| 48 | * This requirement will sunset and may be removed on November 13, 2005, |
| 49 | * after which the standard DragonFly license (as shown above) will |
| 50 | * apply. |
| 51 | */ |
| 52 | |
| 53 | #include <sys/param.h> |
| 54 | #include <sys/systm.h> |
| 55 | #include <sys/kernel.h> |
| 56 | #include <sys/malloc.h> |
| 57 | #include <sys/queue.h> |
| 58 | #include <sys/thread.h> |
| 59 | #include <sys/types.h> |
| 60 | #include <sys/socket.h> |
| 61 | #include <sys/socketvar.h> |
| 62 | |
| 63 | #include <net/if.h> |
| 64 | |
| 65 | #include <netinet/in.h> |
| 66 | #include <netinet/in_systm.h> |
| 67 | #include <netinet/ip.h> |
| 68 | #include <netinet/in_var.h> |
| 69 | #include <netinet/in_pcb.h> |
| 70 | #include <netinet/ip_var.h> |
| 71 | #include <netinet/tcp.h> |
| 72 | #include <netinet/tcp_seq.h> |
| 73 | #include <netinet/tcp_var.h> |
| 74 | |
| 75 | #include <vm/vm_zone.h> |
| 76 | |
| 77 | struct sackblock { |
| 78 | tcp_seq sblk_start; |
| 79 | tcp_seq sblk_end; |
| 80 | TAILQ_ENTRY(sackblock) sblk_list; |
| 81 | }; |
| 82 | |
| 83 | #define MAXSAVEDBLOCKS 8 /* per connection limit */ |
| 84 | |
| 85 | static void insert_block(struct scoreboard *scb, struct sackblock *newblock); |
| 86 | static void update_lostseq(struct scoreboard *scb, tcp_seq snd_una, |
| 87 | u_int maxseg); |
| 88 | |
| 89 | static vm_zone_t sackblock_zone; |
| 90 | |
| 91 | /* |
| 92 | * Initialize SACK module. |
| 93 | */ |
| 94 | void |
| 95 | tcp_sack_init() |
| 96 | { |
| 97 | sackblock_zone = zinit("sack blocks", sizeof(struct sackblock), |
| 98 | maxsockets, ZONE_INTERRUPT, 0); |
| 99 | } |
| 100 | |
| 101 | /* |
| 102 | * Per-tcpcb initialization. |
| 103 | */ |
| 104 | void |
| 105 | tcp_sack_tcpcb_init(struct tcpcb *tp) |
| 106 | { |
| 107 | struct scoreboard *scb = &tp->scb; |
| 108 | |
| 109 | scb->nblocks = 0; |
| 110 | TAILQ_INIT(&scb->sackblocks); |
| 111 | scb->lastfound = NULL; |
| 112 | } |
| 113 | |
| 114 | /* |
| 115 | * Find the SACK block containing or immediately preceding "seq". |
| 116 | * The boolean result indicates whether the sequence is actually |
| 117 | * contained in the SACK block. |
| 118 | */ |
| 119 | static boolean_t |
| 120 | sack_block_lookup(struct scoreboard *scb, tcp_seq seq, struct sackblock **sb) |
| 121 | { |
| 122 | struct sackblock *hint = scb->lastfound; |
| 123 | struct sackblock *cur, *last, *prev; |
| 124 | |
| 125 | if (TAILQ_EMPTY(&scb->sackblocks)) { |
| 126 | *sb = NULL; |
| 127 | return FALSE; |
| 128 | } |
| 129 | |
| 130 | if (hint == NULL) { |
| 131 | /* No hint. Search from start to end. */ |
| 132 | cur = TAILQ_FIRST(&scb->sackblocks); |
| 133 | last = NULL; |
| 134 | prev = TAILQ_LAST(&scb->sackblocks, sackblock_list); |
| 135 | } else { |
| 136 | if (SEQ_GEQ(seq, hint->sblk_start)) { |
| 137 | /* Search from hint to end of list. */ |
| 138 | cur = hint; |
| 139 | last = NULL; |
| 140 | prev = TAILQ_LAST(&scb->sackblocks, sackblock_list); |
| 141 | } else { |
| 142 | /* Search from front of list to hint. */ |
| 143 | cur = TAILQ_FIRST(&scb->sackblocks); |
| 144 | last = hint; |
| 145 | prev = TAILQ_PREV(hint, sackblock_list, sblk_list); |
| 146 | } |
| 147 | } |
| 148 | |
| 149 | do { |
| 150 | if (SEQ_GT(cur->sblk_end, seq)) { |
| 151 | if (SEQ_GEQ(seq, cur->sblk_start)) { |
| 152 | *sb = scb->lastfound = cur; |
| 153 | return TRUE; |
| 154 | } else { |
| 155 | *sb = scb->lastfound = |
| 156 | TAILQ_PREV(cur, sackblock_list, sblk_list); |
| 157 | return FALSE; |
| 158 | } |
| 159 | } |
| 160 | cur = TAILQ_NEXT(cur, sblk_list); |
| 161 | } while (cur != last); |
| 162 | |
| 163 | *sb = scb->lastfound = prev; |
| 164 | return FALSE; |
| 165 | } |
| 166 | |
| 167 | /* |
| 168 | * Allocate a SACK block. |
| 169 | */ |
| 170 | static __inline struct sackblock * |
| 171 | alloc_sackblock(void) |
| 172 | { |
| 173 | return zalloc(sackblock_zone); |
| 174 | } |
| 175 | |
| 176 | /* |
| 177 | * Free a SACK block. |
| 178 | */ |
| 179 | static __inline void |
| 180 | free_sackblock(struct sackblock *s) |
| 181 | { |
| 182 | zfree(sackblock_zone, s); |
| 183 | } |
| 184 | |
| 185 | /* |
| 186 | * Free up SACK blocks for data that's been acked. |
| 187 | */ |
| 188 | static void |
| 189 | tcp_sack_ack_blocks(struct scoreboard *scb, tcp_seq th_ack) |
| 190 | { |
| 191 | struct sackblock *sb, *nb; |
| 192 | |
| 193 | sb = TAILQ_FIRST(&scb->sackblocks); |
| 194 | while (sb && SEQ_LEQ(sb->sblk_end, th_ack)) { |
| 195 | nb = TAILQ_NEXT(sb, sblk_list); |
| 196 | if (sb == scb->lastfound) |
| 197 | scb->lastfound = NULL; |
| 198 | TAILQ_REMOVE(&scb->sackblocks, sb, sblk_list); |
| 199 | free_sackblock(sb); |
| 200 | --scb->nblocks; |
| 201 | KASSERT(scb->nblocks >= 0, |
| 202 | ("SACK block count underflow: %d < 0", scb->nblocks)); |
| 203 | sb = nb; |
| 204 | } |
| 205 | if (sb && SEQ_GT(th_ack, sb->sblk_start)) |
| 206 | sb->sblk_start = th_ack; /* other side reneged? XXX */ |
| 207 | } |
| 208 | |
| 209 | /* |
| 210 | * Delete and free SACK blocks saved in scoreboard. |
| 211 | */ |
| 212 | void |
| 213 | tcp_sack_cleanup(struct scoreboard *scb) |
| 214 | { |
| 215 | struct sackblock *sb, *nb; |
| 216 | |
| 217 | TAILQ_FOREACH_MUTABLE(sb, &scb->sackblocks, sblk_list, nb) { |
| 218 | free_sackblock(sb); |
| 219 | --scb->nblocks; |
| 220 | } |
| 221 | KASSERT(scb->nblocks == 0, |
| 222 | ("SACK block %d count not zero", scb->nblocks)); |
| 223 | TAILQ_INIT(&scb->sackblocks); |
| 224 | scb->lastfound = NULL; |
| 225 | } |
| 226 | |
| 227 | /* |
| 228 | * Returns 0 if not D-SACK block, |
| 229 | * 1 if D-SACK, |
| 230 | * 2 if duplicate of out-of-order D-SACK block. |
| 231 | */ |
| 232 | int |
| 233 | tcp_sack_ndsack_blocks(struct raw_sackblock *blocks, const int numblocks, |
| 234 | tcp_seq snd_una) |
| 235 | { |
| 236 | if (numblocks == 0) |
| 237 | return 0; |
| 238 | |
| 239 | if (SEQ_LT(blocks[0].rblk_start, snd_una)) |
| 240 | return 1; |
| 241 | |
| 242 | /* block 0 inside block 1 */ |
| 243 | if (numblocks > 1 && |
| 244 | SEQ_GEQ(blocks[0].rblk_start, blocks[1].rblk_start) && |
| 245 | SEQ_LEQ(blocks[0].rblk_end, blocks[1].rblk_end)) |
| 246 | return 2; |
| 247 | |
| 248 | return 0; |
| 249 | } |
| 250 | |
| 251 | /* |
| 252 | * Update scoreboard on new incoming ACK. |
| 253 | */ |
| 254 | static void |
| 255 | tcp_sack_add_blocks(struct tcpcb *tp, struct tcpopt *to) |
| 256 | { |
| 257 | const int numblocks = to->to_nsackblocks; |
| 258 | struct raw_sackblock *blocks = to->to_sackblocks; |
| 259 | struct scoreboard *scb = &tp->scb; |
| 260 | struct sackblock *sb; |
| 261 | int startblock; |
| 262 | int i; |
| 263 | |
| 264 | if (tcp_sack_ndsack_blocks(blocks, numblocks, tp->snd_una) > 0) |
| 265 | startblock = 1; |
| 266 | else |
| 267 | startblock = 0; |
| 268 | |
| 269 | for (i = startblock; i < numblocks; i++) { |
| 270 | struct raw_sackblock *newsackblock = &blocks[i]; |
| 271 | |
| 272 | /* don't accept bad SACK blocks */ |
| 273 | if (SEQ_GT(newsackblock->rblk_end, tp->snd_max)) |
| 274 | break; /* skip all other blocks */ |
| 275 | |
| 276 | sb = alloc_sackblock(); |
| 277 | if (sb == NULL) /* do some sort of cleanup? XXX */ |
| 278 | break; /* just skip rest of blocks */ |
| 279 | sb->sblk_start = newsackblock->rblk_start; |
| 280 | sb->sblk_end = newsackblock->rblk_end; |
| 281 | if (TAILQ_EMPTY(&scb->sackblocks)) { |
| 282 | KASSERT(scb->nblocks == 0, ("emply scb w/ blocks")); |
| 283 | scb->nblocks = 1; |
| 284 | TAILQ_INSERT_HEAD(&scb->sackblocks, sb, sblk_list); |
| 285 | } else { |
| 286 | insert_block(scb, sb); |
| 287 | } |
| 288 | } |
| 289 | } |
| 290 | |
| 291 | void |
| 292 | tcp_sack_update_scoreboard(struct tcpcb *tp, struct tcpopt *to) |
| 293 | { |
| 294 | struct scoreboard *scb = &tp->scb; |
| 295 | |
| 296 | tcp_sack_ack_blocks(scb, tp->snd_una); |
| 297 | tcp_sack_add_blocks(tp, to); |
| 298 | update_lostseq(scb, tp->snd_una, tp->t_maxseg); |
| 299 | if (SEQ_LT(tp->rexmt_high, tp->snd_una)) |
| 300 | tp->rexmt_high = tp->snd_una; |
| 301 | } |
| 302 | |
| 303 | /* |
| 304 | * Insert SACK block into sender's scoreboard. |
| 305 | */ |
| 306 | static void |
| 307 | insert_block(struct scoreboard *scb, struct sackblock *newblock) |
| 308 | { |
| 309 | struct sackblock *sb, *workingblock; |
| 310 | boolean_t overlap_front; |
| 311 | |
| 312 | KASSERT(scb->nblocks > 0, ("insert_block() called w/ no blocks")); |
| 313 | |
| 314 | if (scb->nblocks == MAXSAVEDBLOCKS) { |
| 315 | /* |
| 316 | * Should try to kick out older blocks XXX JH |
| 317 | * May be able to coalesce with existing block. |
| 318 | * Or, go other way and free all blocks if we hit this limit. |
| 319 | */ |
| 320 | free_sackblock(newblock); |
| 321 | return; |
| 322 | } |
| 323 | KASSERT(scb->nblocks < MAXSAVEDBLOCKS, |
| 324 | ("too many SACK blocks %d", scb->nblocks)); |
| 325 | |
| 326 | overlap_front = sack_block_lookup(scb, newblock->sblk_start, &sb); |
| 327 | |
| 328 | if (sb == NULL) { |
| 329 | workingblock = newblock; |
| 330 | TAILQ_INSERT_HEAD(&scb->sackblocks, newblock, sblk_list); |
| 331 | ++scb->nblocks; |
| 332 | } else { |
| 333 | if (overlap_front || sb->sblk_end == newblock->sblk_start) { |
| 334 | /* extend old block and discard new one */ |
| 335 | workingblock = sb; |
| 336 | if (SEQ_GT(newblock->sblk_end, sb->sblk_end)) |
| 337 | sb->sblk_end = newblock->sblk_end; |
| 338 | free_sackblock(newblock); |
| 339 | } else { |
| 340 | workingblock = newblock; |
| 341 | TAILQ_INSERT_AFTER(&scb->sackblocks, sb, newblock, |
| 342 | sblk_list); |
| 343 | ++scb->nblocks; |
| 344 | } |
| 345 | } |
| 346 | |
| 347 | /* Consolidate right-hand side. */ |
| 348 | sb = TAILQ_NEXT(workingblock, sblk_list); |
| 349 | while (sb != NULL && |
| 350 | SEQ_GEQ(workingblock->sblk_end, sb->sblk_end)) { |
| 351 | struct sackblock *nextblock; |
| 352 | |
| 353 | nextblock = TAILQ_NEXT(sb, sblk_list); |
| 354 | /* Remove completely overlapped block */ |
| 355 | TAILQ_REMOVE(&scb->sackblocks, sb, sblk_list); |
| 356 | free_sackblock(sb); |
| 357 | --scb->nblocks; |
| 358 | KASSERT(scb->nblocks > 0, |
| 359 | ("removed overlapped block: %d blocks left", scb->nblocks)); |
| 360 | sb = nextblock; |
| 361 | } |
| 362 | if (sb != NULL && |
| 363 | SEQ_GEQ(workingblock->sblk_end, sb->sblk_start)) { |
| 364 | /* Extend new block to cover partially overlapped old block. */ |
| 365 | workingblock->sblk_end = sb->sblk_end; |
| 366 | TAILQ_REMOVE(&scb->sackblocks, sb, sblk_list); |
| 367 | free_sackblock(sb); |
| 368 | --scb->nblocks; |
| 369 | KASSERT(scb->nblocks > 0, |
| 370 | ("removed partial right: %d blocks left", scb->nblocks)); |
| 371 | } |
| 372 | } |
| 373 | |
| 374 | #ifdef DEBUG_SACK_BLOCKS |
| 375 | static void |
| 376 | tcp_sack_dump_blocks(struct scoreboard *scb) |
| 377 | { |
| 378 | struct sackblock *sb; |
| 379 | |
| 380 | printf("%d blocks:", scb->nblocks); |
| 381 | TAILQ_FOREACH(sb, &scb->sackblocks, sblk_list) |
| 382 | printf(" [%u, %u)", sb->sblk_start, sb->sblk_end); |
| 383 | printf("\n"); |
| 384 | } |
| 385 | #else |
| 386 | static __inline void |
| 387 | tcp_sack_dump_blocks(struct scoreboard *scb) |
| 388 | { |
| 389 | } |
| 390 | #endif |
| 391 | |
| 392 | /* |
| 393 | * Optimization to quickly determine which packets are lost. |
| 394 | */ |
| 395 | static void |
| 396 | update_lostseq(struct scoreboard *scb, tcp_seq snd_una, u_int maxseg) |
| 397 | { |
| 398 | struct sackblock *sb; |
| 399 | int nsackblocks = 0; |
| 400 | int bytes_sacked = 0; |
| 401 | |
| 402 | sb = TAILQ_LAST(&scb->sackblocks, sackblock_list); |
| 403 | while (sb != NULL) { |
| 404 | ++nsackblocks; |
| 405 | bytes_sacked += sb->sblk_end - sb->sblk_start; |
| 406 | if (nsackblocks == tcprexmtthresh || |
| 407 | bytes_sacked >= tcprexmtthresh * maxseg) { |
| 408 | scb->lostseq = sb->sblk_start; |
| 409 | return; |
| 410 | } |
| 411 | sb = TAILQ_PREV(sb, sackblock_list, sblk_list); |
| 412 | } |
| 413 | scb->lostseq = snd_una; |
| 414 | } |
| 415 | |
| 416 | /* |
| 417 | * Return whether the given sequence number is considered lost. |
| 418 | */ |
| 419 | static boolean_t |
| 420 | scb_islost(struct scoreboard *scb, tcp_seq seqnum) |
| 421 | { |
| 422 | return SEQ_LT(seqnum, scb->lostseq); |
| 423 | } |
| 424 | |
| 425 | /* |
| 426 | * True if at least "amount" has been SACKed. Used by Early Retransmit. |
| 427 | */ |
| 428 | boolean_t |
| 429 | tcp_sack_has_sacked(struct scoreboard *scb, u_int amount) |
| 430 | { |
| 431 | struct sackblock *sb; |
| 432 | int bytes_sacked = 0; |
| 433 | |
| 434 | TAILQ_FOREACH(sb, &scb->sackblocks, sblk_list) { |
| 435 | bytes_sacked += sb->sblk_end - sb->sblk_start; |
| 436 | if (bytes_sacked >= amount) |
| 437 | return TRUE; |
| 438 | } |
| 439 | return FALSE; |
| 440 | } |
| 441 | |
| 442 | /* |
| 443 | * Return estimate of the number of bytes outstanding in the network. |
| 444 | */ |
| 445 | uint32_t |
| 446 | tcp_sack_compute_pipe(struct tcpcb *tp) |
| 447 | { |
| 448 | struct scoreboard *scb = &tp->scb; |
| 449 | struct sackblock *sb; |
| 450 | int nlost, nretransmitted; |
| 451 | tcp_seq end; |
| 452 | |
| 453 | nlost = tp->snd_max - scb->lostseq; |
| 454 | nretransmitted = tp->rexmt_high - tp->snd_una; |
| 455 | |
| 456 | TAILQ_FOREACH(sb, &scb->sackblocks, sblk_list) { |
| 457 | if (SEQ_LT(sb->sblk_start, tp->rexmt_high)) { |
| 458 | end = seq_min(sb->sblk_end, tp->rexmt_high); |
| 459 | nretransmitted -= end - sb->sblk_start; |
| 460 | } |
| 461 | if (SEQ_GEQ(sb->sblk_start, scb->lostseq)) |
| 462 | nlost -= sb->sblk_end - sb->sblk_start; |
| 463 | } |
| 464 | |
| 465 | return (nlost + nretransmitted); |
| 466 | } |
| 467 | |
| 468 | /* |
| 469 | * Return the sequence number and length of the next segment to transmit |
| 470 | * when in Fast Recovery. |
| 471 | */ |
| 472 | boolean_t |
| 473 | tcp_sack_nextseg(struct tcpcb *tp, tcp_seq *nextrexmt, uint32_t *plen, |
| 474 | boolean_t *lostdup) |
| 475 | { |
| 476 | struct scoreboard *scb = &tp->scb; |
| 477 | struct socket *so = tp->t_inpcb->inp_socket; |
| 478 | struct sackblock *sb; |
| 479 | const struct sackblock *lastblock = |
| 480 | TAILQ_LAST(&scb->sackblocks, sackblock_list); |
| 481 | tcp_seq torexmt; |
| 482 | long len, off; |
| 483 | |
| 484 | /* skip SACKed data */ |
| 485 | tcp_sack_skip_sacked(scb, &tp->rexmt_high); |
| 486 | |
| 487 | /* Look for lost data. */ |
| 488 | torexmt = tp->rexmt_high; |
| 489 | *lostdup = FALSE; |
| 490 | if (lastblock != NULL) { |
| 491 | if (SEQ_LT(torexmt, lastblock->sblk_end) && |
| 492 | scb_islost(scb, torexmt)) { |
| 493 | sendunsacked: |
| 494 | *nextrexmt = torexmt; |
| 495 | /* If the left-hand edge has been SACKed, pull it in. */ |
| 496 | if (sack_block_lookup(scb, torexmt + tp->t_maxseg, &sb)) |
| 497 | *plen = sb->sblk_start - torexmt; |
| 498 | else |
| 499 | *plen = tp->t_maxseg; |
| 500 | return TRUE; |
| 501 | } |
| 502 | } |
| 503 | |
| 504 | /* See if unsent data available within send window. */ |
| 505 | off = tp->snd_max - tp->snd_una; |
| 506 | len = (long) ulmin(so->so_snd.sb_cc, tp->snd_wnd) - off; |
| 507 | if (len > 0) { |
| 508 | *nextrexmt = tp->snd_max; /* Send new data. */ |
| 509 | *plen = tp->t_maxseg; |
| 510 | return TRUE; |
| 511 | } |
| 512 | |
| 513 | /* We're less certain this data has been lost. */ |
| 514 | if (lastblock == NULL || SEQ_LT(torexmt, lastblock->sblk_end)) |
| 515 | goto sendunsacked; |
| 516 | |
| 517 | return FALSE; |
| 518 | } |
| 519 | |
| 520 | /* |
| 521 | * Return the next sequence number higher than "*prexmt" that has |
| 522 | * not been SACKed. |
| 523 | */ |
| 524 | void |
| 525 | tcp_sack_skip_sacked(struct scoreboard *scb, tcp_seq *prexmt) |
| 526 | { |
| 527 | struct sackblock *sb; |
| 528 | |
| 529 | /* skip SACKed data */ |
| 530 | if (sack_block_lookup(scb, *prexmt, &sb)) |
| 531 | *prexmt = sb->sblk_end; |
| 532 | } |
| 533 | |
| 534 | #ifdef later |
| 535 | void |
| 536 | tcp_sack_save_scoreboard(struct scoreboard *scb) |
| 537 | { |
| 538 | struct scoreboard *scb = &tp->scb; |
| 539 | |
| 540 | scb->sackblocks_prev = scb->sackblocks; |
| 541 | TAILQ_INIT(&scb->sackblocks); |
| 542 | } |
| 543 | |
| 544 | void |
| 545 | tcp_sack_revert_scoreboard(struct scoreboard *scb, tcp_seq snd_una, |
| 546 | u_int maxseg) |
| 547 | { |
| 548 | struct sackblock *sb; |
| 549 | |
| 550 | scb->sackblocks = scb->sackblocks_prev; |
| 551 | scb->nblocks = 0; |
| 552 | TAILQ_FOREACH(sb, &scb->sackblocks, sblk_list) |
| 553 | ++scb->nblocks; |
| 554 | tcp_sack_ack_blocks(scb, snd_una); |
| 555 | scb->lastfound = NULL; |
| 556 | } |
| 557 | #endif |
| 558 | |
| 559 | #ifdef DEBUG_SACK_HISTORY |
| 560 | static void |
| 561 | tcp_sack_dump_history(char *msg, struct tcpcb *tp) |
| 562 | { |
| 563 | int i; |
| 564 | static int ndumped; |
| 565 | |
| 566 | /* only need a couple of these to debug most problems */ |
| 567 | if (++ndumped > 900) |
| 568 | return; |
| 569 | |
| 570 | printf("%s:\tnsackhistory %d: ", msg, tp->nsackhistory); |
| 571 | for (i = 0; i < tp->nsackhistory; ++i) |
| 572 | printf("[%u, %u) ", tp->sackhistory[i].rblk_start, |
| 573 | tp->sackhistory[i].rblk_end); |
| 574 | printf("\n"); |
| 575 | } |
| 576 | #else |
| 577 | static __inline void |
| 578 | tcp_sack_dump_history(char *msg, struct tcpcb *tp) |
| 579 | { |
| 580 | } |
| 581 | #endif |
| 582 | |
| 583 | /* |
| 584 | * Remove old SACK blocks from the SACK history that have already been ACKed. |
| 585 | */ |
| 586 | static void |
| 587 | tcp_sack_ack_history(struct tcpcb *tp) |
| 588 | { |
| 589 | int i, nblocks, openslot; |
| 590 | |
| 591 | tcp_sack_dump_history("before tcp_sack_ack_history", tp); |
| 592 | nblocks = tp->nsackhistory; |
| 593 | for (i = openslot = 0; i < nblocks; ++i) { |
| 594 | if (SEQ_LEQ(tp->sackhistory[i].rblk_end, tp->rcv_nxt)) { |
| 595 | --tp->nsackhistory; |
| 596 | continue; |
| 597 | } |
| 598 | if (SEQ_LT(tp->sackhistory[i].rblk_start, tp->rcv_nxt)) |
| 599 | tp->sackhistory[i].rblk_start = tp->rcv_nxt; |
| 600 | if (i == openslot) |
| 601 | ++openslot; |
| 602 | else |
| 603 | tp->sackhistory[openslot++] = tp->sackhistory[i]; |
| 604 | } |
| 605 | tcp_sack_dump_history("after tcp_sack_ack_history", tp); |
| 606 | KASSERT(openslot == tp->nsackhistory, |
| 607 | ("tcp_sack_ack_history miscounted: %d != %d", |
| 608 | openslot, tp->nsackhistory)); |
| 609 | } |
| 610 | |
| 611 | /* |
| 612 | * Add or merge newblock into reported history. |
| 613 | * Also remove or update SACK blocks that will be acked. |
| 614 | */ |
| 615 | static void |
| 616 | tcp_sack_update_reported_history(struct tcpcb *tp, tcp_seq start, tcp_seq end) |
| 617 | { |
| 618 | struct raw_sackblock copy[MAX_SACK_REPORT_BLOCKS]; |
| 619 | int i, cindex; |
| 620 | |
| 621 | tcp_sack_dump_history("before tcp_sack_update_reported_history", tp); |
| 622 | /* |
| 623 | * Six cases: |
| 624 | * 0) no overlap |
| 625 | * 1) newblock == oldblock |
| 626 | * 2) oldblock contains newblock |
| 627 | * 3) newblock contains oldblock |
| 628 | * 4) tail of oldblock overlaps or abuts start of newblock |
| 629 | * 5) tail of newblock overlaps or abuts head of oldblock |
| 630 | */ |
| 631 | for (i = cindex = 0; i < tp->nsackhistory; ++i) { |
| 632 | struct raw_sackblock *oldblock = &tp->sackhistory[i]; |
| 633 | tcp_seq old_start = oldblock->rblk_start; |
| 634 | tcp_seq old_end = oldblock->rblk_end; |
| 635 | |
| 636 | if (SEQ_LT(end, old_start) || SEQ_GT(start, old_end)) { |
| 637 | /* Case 0: no overlap. Copy old block. */ |
| 638 | copy[cindex++] = *oldblock; |
| 639 | continue; |
| 640 | } |
| 641 | |
| 642 | if (SEQ_GEQ(start, old_start) && SEQ_LEQ(end, old_end)) { |
| 643 | /* Cases 1 & 2. Move block to front of history. */ |
| 644 | int j; |
| 645 | |
| 646 | start = old_start; |
| 647 | end = old_end; |
| 648 | /* no need to check rest of blocks */ |
| 649 | for (j = i + 1; j < tp->nsackhistory; ++j) |
| 650 | copy[cindex++] = tp->sackhistory[j]; |
| 651 | break; |
| 652 | } |
| 653 | |
| 654 | if (SEQ_GEQ(old_end, start) && SEQ_LT(old_start, start)) { |
| 655 | /* Case 4: extend start of new block. */ |
| 656 | start = old_start; |
| 657 | } else if (SEQ_GEQ(end, old_start) && SEQ_GT(old_end, end)) { |
| 658 | /* Case 5: extend end of new block */ |
| 659 | end = old_end; |
| 660 | } else { |
| 661 | /* Case 3. Delete old block by not copying it. */ |
| 662 | KASSERT(SEQ_LEQ(start, old_start) && |
| 663 | SEQ_GEQ(end, old_end), |
| 664 | ("bad logic: old [%u, %u), new [%u, %u)", |
| 665 | old_start, old_end, start, end)); |
| 666 | } |
| 667 | } |
| 668 | |
| 669 | /* insert new block */ |
| 670 | tp->sackhistory[0].rblk_start = start; |
| 671 | tp->sackhistory[0].rblk_end = end; |
| 672 | cindex = min(cindex, MAX_SACK_REPORT_BLOCKS - 1); |
| 673 | for (i = 0; i < cindex; ++i) |
| 674 | tp->sackhistory[i + 1] = copy[i]; |
| 675 | tp->nsackhistory = cindex + 1; |
| 676 | tcp_sack_dump_history("after tcp_sack_update_reported_history", tp); |
| 677 | } |
| 678 | |
| 679 | /* |
| 680 | * Fill in SACK report to return to data sender. |
| 681 | */ |
| 682 | void |
| 683 | tcp_sack_fill_report(struct tcpcb *tp, u_char *opt, u_int *plen) |
| 684 | { |
| 685 | u_int optlen = *plen; |
| 686 | uint32_t *lp = (uint32_t *)(opt + optlen); |
| 687 | uint32_t *olp; |
| 688 | tcp_seq hstart = tp->rcv_nxt, hend; |
| 689 | int nblocks; |
| 690 | |
| 691 | KASSERT(TCP_MAXOLEN - optlen >= |
| 692 | TCPOLEN_SACK_ALIGNED + TCPOLEN_SACK_BLOCK, |
| 693 | ("no room for SACK header and one block: optlen %d", optlen)); |
| 694 | |
| 695 | olp = lp++; |
| 696 | optlen += TCPOLEN_SACK_ALIGNED; |
| 697 | |
| 698 | tcp_sack_ack_history(tp); |
| 699 | if (tp->reportblk.rblk_start != tp->reportblk.rblk_end) { |
| 700 | *lp++ = htonl(tp->reportblk.rblk_start); |
| 701 | *lp++ = htonl(tp->reportblk.rblk_end); |
| 702 | optlen += TCPOLEN_SACK_BLOCK; |
| 703 | hstart = tp->reportblk.rblk_start; |
| 704 | hend = tp->reportblk.rblk_end; |
| 705 | if (tp->t_flags & TF_ENCLOSESEG) { |
| 706 | KASSERT(TCP_MAXOLEN - optlen >= TCPOLEN_SACK_BLOCK, |
| 707 | ("no room for enclosing SACK block: oplen %d", |
| 708 | optlen)); |
| 709 | *lp++ = htonl(tp->encloseblk.rblk_start); |
| 710 | *lp++ = htonl(tp->encloseblk.rblk_end); |
| 711 | optlen += TCPOLEN_SACK_BLOCK; |
| 712 | hstart = tp->encloseblk.rblk_start; |
| 713 | hend = tp->encloseblk.rblk_end; |
| 714 | } |
| 715 | if (SEQ_GT(hstart, tp->rcv_nxt)) |
| 716 | tcp_sack_update_reported_history(tp, hstart, hend); |
| 717 | } |
| 718 | if (tcp_do_smartsack && (tp->t_flags & TF_SACKLEFT)) { |
| 719 | /* Fill in from left! Walk re-assembly queue. */ |
| 720 | struct tseg_qent *q; |
| 721 | |
| 722 | q = LIST_FIRST(&tp->t_segq); |
| 723 | while (q != NULL && |
| 724 | TCP_MAXOLEN - optlen >= TCPOLEN_SACK_BLOCK) { |
| 725 | *lp++ = htonl(q->tqe_th->th_seq); |
| 726 | *lp++ = htonl(q->tqe_th->th_seq + q->tqe_len); |
| 727 | optlen += TCPOLEN_SACK_BLOCK; |
| 728 | q = LIST_NEXT(q, tqe_q); |
| 729 | } |
| 730 | } else { |
| 731 | int n = 0; |
| 732 | |
| 733 | /* Fill in SACK blocks from right side. */ |
| 734 | while (n < tp->nsackhistory && |
| 735 | TCP_MAXOLEN - optlen >= TCPOLEN_SACK_BLOCK) { |
| 736 | if (tp->sackhistory[n].rblk_start != hstart) { |
| 737 | *lp++ = htonl(tp->sackhistory[n].rblk_start); |
| 738 | *lp++ = htonl(tp->sackhistory[n].rblk_end); |
| 739 | optlen += TCPOLEN_SACK_BLOCK; |
| 740 | } |
| 741 | ++n; |
| 742 | } |
| 743 | } |
| 744 | tp->reportblk.rblk_start = tp->reportblk.rblk_end; |
| 745 | tp->t_flags &= ~(TF_DUPSEG | TF_ENCLOSESEG | TF_SACKLEFT); |
| 746 | nblocks = (lp - olp - 1) / 2; |
| 747 | *olp = htonl(TCPOPT_SACK_ALIGNED | |
| 748 | (TCPOLEN_SACK + nblocks * TCPOLEN_SACK_BLOCK)); |
| 749 | *plen = optlen; |
| 750 | } |