| 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.8 2008/08/15 21:37:16 nth Exp $ |
| 34 | */ |
| 35 | |
| 36 | #include <sys/param.h> |
| 37 | #include <sys/systm.h> |
| 38 | #include <sys/kernel.h> |
| 39 | #include <sys/malloc.h> |
| 40 | #include <sys/queue.h> |
| 41 | #include <sys/thread.h> |
| 42 | #include <sys/types.h> |
| 43 | #include <sys/socket.h> |
| 44 | #include <sys/socketvar.h> |
| 45 | |
| 46 | #include <net/if.h> |
| 47 | |
| 48 | #include <netinet/in.h> |
| 49 | #include <netinet/in_systm.h> |
| 50 | #include <netinet/ip.h> |
| 51 | #include <netinet/in_var.h> |
| 52 | #include <netinet/in_pcb.h> |
| 53 | #include <netinet/ip_var.h> |
| 54 | #include <netinet/tcp.h> |
| 55 | #include <netinet/tcp_seq.h> |
| 56 | #include <netinet/tcp_var.h> |
| 57 | |
| 58 | /* |
| 59 | * Implemented: |
| 60 | * |
| 61 | * RFC 2018 |
| 62 | * RFC 2883 |
| 63 | * RFC 3517 |
| 64 | */ |
| 65 | |
| 66 | struct sackblock { |
| 67 | tcp_seq sblk_start; |
| 68 | tcp_seq sblk_end; |
| 69 | TAILQ_ENTRY(sackblock) sblk_list; |
| 70 | }; |
| 71 | |
| 72 | #define MAXSAVEDBLOCKS 8 /* per connection limit */ |
| 73 | |
| 74 | static void insert_block(struct scoreboard *scb, struct sackblock *newblock); |
| 75 | static void update_lostseq(struct scoreboard *scb, tcp_seq snd_una, |
| 76 | u_int maxseg); |
| 77 | |
| 78 | static MALLOC_DEFINE(M_SACKBLOCK, "sblk", "sackblock struct"); |
| 79 | |
| 80 | /* |
| 81 | * Per-tcpcb initialization. |
| 82 | */ |
| 83 | void |
| 84 | tcp_sack_tcpcb_init(struct tcpcb *tp) |
| 85 | { |
| 86 | struct scoreboard *scb = &tp->scb; |
| 87 | |
| 88 | scb->nblocks = 0; |
| 89 | TAILQ_INIT(&scb->sackblocks); |
| 90 | scb->lastfound = NULL; |
| 91 | } |
| 92 | |
| 93 | /* |
| 94 | * Find the SACK block containing or immediately preceding "seq". |
| 95 | * The boolean result indicates whether the sequence is actually |
| 96 | * contained in the SACK block. |
| 97 | */ |
| 98 | static boolean_t |
| 99 | sack_block_lookup(struct scoreboard *scb, tcp_seq seq, struct sackblock **sb) |
| 100 | { |
| 101 | struct sackblock *hint = scb->lastfound; |
| 102 | struct sackblock *cur, *last, *prev; |
| 103 | |
| 104 | if (TAILQ_EMPTY(&scb->sackblocks)) { |
| 105 | *sb = NULL; |
| 106 | return FALSE; |
| 107 | } |
| 108 | |
| 109 | if (hint == NULL) { |
| 110 | /* No hint. Search from start to end. */ |
| 111 | cur = TAILQ_FIRST(&scb->sackblocks); |
| 112 | last = NULL; |
| 113 | prev = TAILQ_LAST(&scb->sackblocks, sackblock_list); |
| 114 | } else { |
| 115 | if (SEQ_GEQ(seq, hint->sblk_start)) { |
| 116 | /* Search from hint to end of list. */ |
| 117 | cur = hint; |
| 118 | last = NULL; |
| 119 | prev = TAILQ_LAST(&scb->sackblocks, sackblock_list); |
| 120 | } else { |
| 121 | /* Search from front of list to hint. */ |
| 122 | cur = TAILQ_FIRST(&scb->sackblocks); |
| 123 | last = hint; |
| 124 | prev = TAILQ_PREV(hint, sackblock_list, sblk_list); |
| 125 | } |
| 126 | } |
| 127 | |
| 128 | do { |
| 129 | if (SEQ_GT(cur->sblk_end, seq)) { |
| 130 | if (SEQ_GEQ(seq, cur->sblk_start)) { |
| 131 | *sb = scb->lastfound = cur; |
| 132 | return TRUE; |
| 133 | } else { |
| 134 | *sb = scb->lastfound = |
| 135 | TAILQ_PREV(cur, sackblock_list, sblk_list); |
| 136 | return FALSE; |
| 137 | } |
| 138 | } |
| 139 | cur = TAILQ_NEXT(cur, sblk_list); |
| 140 | } while (cur != last); |
| 141 | |
| 142 | *sb = scb->lastfound = prev; |
| 143 | return FALSE; |
| 144 | } |
| 145 | |
| 146 | /* |
| 147 | * Allocate a SACK block. |
| 148 | */ |
| 149 | static __inline struct sackblock * |
| 150 | alloc_sackblock(void) |
| 151 | { |
| 152 | return (kmalloc(sizeof(struct sackblock), M_SACKBLOCK, M_NOWAIT)); |
| 153 | } |
| 154 | |
| 155 | /* |
| 156 | * Free a SACK block. |
| 157 | */ |
| 158 | static __inline void |
| 159 | free_sackblock(struct sackblock *s) |
| 160 | { |
| 161 | kfree(s, M_SACKBLOCK); |
| 162 | } |
| 163 | |
| 164 | /* |
| 165 | * Free up SACK blocks for data that's been acked. |
| 166 | */ |
| 167 | static void |
| 168 | tcp_sack_ack_blocks(struct scoreboard *scb, tcp_seq th_ack) |
| 169 | { |
| 170 | struct sackblock *sb, *nb; |
| 171 | |
| 172 | sb = TAILQ_FIRST(&scb->sackblocks); |
| 173 | while (sb && SEQ_LEQ(sb->sblk_end, th_ack)) { |
| 174 | nb = TAILQ_NEXT(sb, sblk_list); |
| 175 | if (scb->lastfound == sb) |
| 176 | scb->lastfound = NULL; |
| 177 | TAILQ_REMOVE(&scb->sackblocks, sb, sblk_list); |
| 178 | free_sackblock(sb); |
| 179 | --scb->nblocks; |
| 180 | KASSERT(scb->nblocks >= 0, |
| 181 | ("SACK block count underflow: %d < 0", scb->nblocks)); |
| 182 | sb = nb; |
| 183 | } |
| 184 | if (sb && SEQ_GT(th_ack, sb->sblk_start)) |
| 185 | sb->sblk_start = th_ack; /* other side reneged? XXX */ |
| 186 | } |
| 187 | |
| 188 | /* |
| 189 | * Delete and free SACK blocks saved in scoreboard. |
| 190 | */ |
| 191 | void |
| 192 | tcp_sack_cleanup(struct scoreboard *scb) |
| 193 | { |
| 194 | struct sackblock *sb, *nb; |
| 195 | |
| 196 | TAILQ_FOREACH_MUTABLE(sb, &scb->sackblocks, sblk_list, nb) { |
| 197 | free_sackblock(sb); |
| 198 | --scb->nblocks; |
| 199 | } |
| 200 | KASSERT(scb->nblocks == 0, |
| 201 | ("SACK block %d count not zero", scb->nblocks)); |
| 202 | TAILQ_INIT(&scb->sackblocks); |
| 203 | scb->lastfound = NULL; |
| 204 | } |
| 205 | |
| 206 | /* |
| 207 | * Cleanup the reported SACK block information |
| 208 | */ |
| 209 | void |
| 210 | tcp_sack_report_cleanup(struct tcpcb *tp) |
| 211 | { |
| 212 | tp->t_flags &= ~(TF_DUPSEG | TF_ENCLOSESEG | TF_SACKLEFT); |
| 213 | tp->reportblk.rblk_start = tp->reportblk.rblk_end; |
| 214 | } |
| 215 | |
| 216 | /* |
| 217 | * Returns 0 if not D-SACK block, |
| 218 | * 1 if D-SACK, |
| 219 | * 2 if duplicate of out-of-order D-SACK block. |
| 220 | */ |
| 221 | int |
| 222 | tcp_sack_ndsack_blocks(struct raw_sackblock *blocks, const int numblocks, |
| 223 | tcp_seq snd_una) |
| 224 | { |
| 225 | if (numblocks == 0) |
| 226 | return 0; |
| 227 | |
| 228 | if (SEQ_LT(blocks[0].rblk_start, snd_una)) |
| 229 | return 1; |
| 230 | |
| 231 | /* block 0 inside block 1 */ |
| 232 | if (numblocks > 1 && |
| 233 | SEQ_GEQ(blocks[0].rblk_start, blocks[1].rblk_start) && |
| 234 | SEQ_LEQ(blocks[0].rblk_end, blocks[1].rblk_end)) |
| 235 | return 2; |
| 236 | |
| 237 | return 0; |
| 238 | } |
| 239 | |
| 240 | /* |
| 241 | * Update scoreboard on new incoming ACK. |
| 242 | */ |
| 243 | static void |
| 244 | tcp_sack_add_blocks(struct tcpcb *tp, struct tcpopt *to) |
| 245 | { |
| 246 | const int numblocks = to->to_nsackblocks; |
| 247 | struct raw_sackblock *blocks = to->to_sackblocks; |
| 248 | struct scoreboard *scb = &tp->scb; |
| 249 | struct sackblock *sb; |
| 250 | int startblock; |
| 251 | int i; |
| 252 | |
| 253 | if (tcp_sack_ndsack_blocks(blocks, numblocks, tp->snd_una) > 0) |
| 254 | startblock = 1; |
| 255 | else |
| 256 | startblock = 0; |
| 257 | |
| 258 | for (i = startblock; i < numblocks; i++) { |
| 259 | struct raw_sackblock *newsackblock = &blocks[i]; |
| 260 | |
| 261 | /* don't accept bad SACK blocks */ |
| 262 | if (SEQ_GT(newsackblock->rblk_end, tp->snd_max)) { |
| 263 | tcpstat.tcps_rcvbadsackopt++; |
| 264 | break; /* skip all other blocks */ |
| 265 | } |
| 266 | tcpstat.tcps_sacksbupdate++; |
| 267 | |
| 268 | sb = alloc_sackblock(); |
| 269 | if (sb == NULL) { /* do some sort of cleanup? XXX */ |
| 270 | tcpstat.tcps_sacksbfailed++; |
| 271 | break; /* just skip rest of blocks */ |
| 272 | } |
| 273 | sb->sblk_start = newsackblock->rblk_start; |
| 274 | sb->sblk_end = newsackblock->rblk_end; |
| 275 | if (TAILQ_EMPTY(&scb->sackblocks)) { |
| 276 | KASSERT(scb->nblocks == 0, ("emply scb w/ blocks")); |
| 277 | scb->nblocks = 1; |
| 278 | TAILQ_INSERT_HEAD(&scb->sackblocks, sb, sblk_list); |
| 279 | } else { |
| 280 | insert_block(scb, sb); |
| 281 | } |
| 282 | } |
| 283 | } |
| 284 | |
| 285 | void |
| 286 | tcp_sack_update_scoreboard(struct tcpcb *tp, struct tcpopt *to) |
| 287 | { |
| 288 | struct scoreboard *scb = &tp->scb; |
| 289 | |
| 290 | tcp_sack_ack_blocks(scb, tp->snd_una); |
| 291 | tcp_sack_add_blocks(tp, to); |
| 292 | update_lostseq(scb, tp->snd_una, tp->t_maxseg); |
| 293 | if (SEQ_LT(tp->rexmt_high, tp->snd_una)) |
| 294 | tp->rexmt_high = tp->snd_una; |
| 295 | } |
| 296 | |
| 297 | /* |
| 298 | * Insert SACK block into sender's scoreboard. |
| 299 | */ |
| 300 | static void |
| 301 | insert_block(struct scoreboard *scb, struct sackblock *newblock) |
| 302 | { |
| 303 | struct sackblock *sb, *workingblock; |
| 304 | boolean_t overlap_front; |
| 305 | |
| 306 | KASSERT(scb->nblocks > 0, ("insert_block() called w/ no blocks")); |
| 307 | |
| 308 | if (scb->nblocks == MAXSAVEDBLOCKS) { |
| 309 | /* |
| 310 | * Should try to kick out older blocks XXX JH |
| 311 | * May be able to coalesce with existing block. |
| 312 | * Or, go other way and free all blocks if we hit this limit. |
| 313 | */ |
| 314 | free_sackblock(newblock); |
| 315 | tcpstat.tcps_sacksboverflow++; |
| 316 | return; |
| 317 | } |
| 318 | KASSERT(scb->nblocks < MAXSAVEDBLOCKS, |
| 319 | ("too many SACK blocks %d", scb->nblocks)); |
| 320 | |
| 321 | overlap_front = sack_block_lookup(scb, newblock->sblk_start, &sb); |
| 322 | |
| 323 | if (sb == NULL) { |
| 324 | workingblock = newblock; |
| 325 | TAILQ_INSERT_HEAD(&scb->sackblocks, newblock, sblk_list); |
| 326 | ++scb->nblocks; |
| 327 | } else { |
| 328 | if (overlap_front || sb->sblk_end == newblock->sblk_start) { |
| 329 | /* extend old block and discard new one */ |
| 330 | workingblock = sb; |
| 331 | if (SEQ_GT(newblock->sblk_end, sb->sblk_end)) |
| 332 | sb->sblk_end = newblock->sblk_end; |
| 333 | free_sackblock(newblock); |
| 334 | tcpstat.tcps_sacksbreused++; |
| 335 | } else { |
| 336 | workingblock = newblock; |
| 337 | TAILQ_INSERT_AFTER(&scb->sackblocks, sb, newblock, |
| 338 | sblk_list); |
| 339 | ++scb->nblocks; |
| 340 | } |
| 341 | } |
| 342 | |
| 343 | /* Consolidate right-hand side. */ |
| 344 | sb = TAILQ_NEXT(workingblock, sblk_list); |
| 345 | while (sb != NULL && |
| 346 | SEQ_GEQ(workingblock->sblk_end, sb->sblk_end)) { |
| 347 | struct sackblock *nextblock; |
| 348 | |
| 349 | nextblock = TAILQ_NEXT(sb, sblk_list); |
| 350 | if (scb->lastfound == sb) |
| 351 | scb->lastfound = NULL; |
| 352 | /* Remove completely overlapped block */ |
| 353 | TAILQ_REMOVE(&scb->sackblocks, sb, sblk_list); |
| 354 | free_sackblock(sb); |
| 355 | --scb->nblocks; |
| 356 | KASSERT(scb->nblocks > 0, |
| 357 | ("removed overlapped block: %d blocks left", scb->nblocks)); |
| 358 | sb = nextblock; |
| 359 | } |
| 360 | if (sb != NULL && |
| 361 | SEQ_GEQ(workingblock->sblk_end, sb->sblk_start)) { |
| 362 | /* Extend new block to cover partially overlapped old block. */ |
| 363 | workingblock->sblk_end = sb->sblk_end; |
| 364 | if (scb->lastfound == sb) |
| 365 | scb->lastfound = NULL; |
| 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 | kprintf("%d blocks:", scb->nblocks); |
| 381 | TAILQ_FOREACH(sb, &scb->sackblocks, sblk_list) |
| 382 | kprintf(" [%u, %u)", sb->sblk_start, sb->sblk_end); |
| 383 | kprintf("\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 | * Number of bytes SACKed below seq. |
| 444 | */ |
| 445 | int |
| 446 | tcp_sack_bytes_below(struct scoreboard *scb, tcp_seq seq) |
| 447 | { |
| 448 | struct sackblock *sb; |
| 449 | int bytes_sacked = 0; |
| 450 | |
| 451 | sb = TAILQ_FIRST(&scb->sackblocks); |
| 452 | while (sb && SEQ_GT(seq, sb->sblk_start)) { |
| 453 | bytes_sacked += seq_min(seq, sb->sblk_end) - sb->sblk_start; |
| 454 | sb = TAILQ_NEXT(sb, sblk_list); |
| 455 | } |
| 456 | return bytes_sacked; |
| 457 | } |
| 458 | |
| 459 | /* |
| 460 | * Return estimate of the number of bytes outstanding in the network. |
| 461 | */ |
| 462 | uint32_t |
| 463 | tcp_sack_compute_pipe(struct tcpcb *tp) |
| 464 | { |
| 465 | struct scoreboard *scb = &tp->scb; |
| 466 | struct sackblock *sb; |
| 467 | int nlost, nretransmitted; |
| 468 | tcp_seq end; |
| 469 | |
| 470 | nlost = tp->snd_max - scb->lostseq; |
| 471 | nretransmitted = tp->rexmt_high - tp->snd_una; |
| 472 | |
| 473 | TAILQ_FOREACH(sb, &scb->sackblocks, sblk_list) { |
| 474 | if (SEQ_LT(sb->sblk_start, tp->rexmt_high)) { |
| 475 | end = seq_min(sb->sblk_end, tp->rexmt_high); |
| 476 | nretransmitted -= end - sb->sblk_start; |
| 477 | } |
| 478 | if (SEQ_GEQ(sb->sblk_start, scb->lostseq)) |
| 479 | nlost -= sb->sblk_end - sb->sblk_start; |
| 480 | } |
| 481 | |
| 482 | return (nlost + nretransmitted); |
| 483 | } |
| 484 | |
| 485 | /* |
| 486 | * Return the sequence number and length of the next segment to transmit |
| 487 | * when in Fast Recovery. |
| 488 | */ |
| 489 | boolean_t |
| 490 | tcp_sack_nextseg(struct tcpcb *tp, tcp_seq *nextrexmt, uint32_t *plen, |
| 491 | boolean_t *lostdup) |
| 492 | { |
| 493 | struct scoreboard *scb = &tp->scb; |
| 494 | struct socket *so = tp->t_inpcb->inp_socket; |
| 495 | struct sackblock *sb; |
| 496 | const struct sackblock *lastblock = |
| 497 | TAILQ_LAST(&scb->sackblocks, sackblock_list); |
| 498 | tcp_seq torexmt; |
| 499 | long len, off; |
| 500 | |
| 501 | /* skip SACKed data */ |
| 502 | tcp_sack_skip_sacked(scb, &tp->rexmt_high); |
| 503 | |
| 504 | /* Look for lost data. */ |
| 505 | torexmt = tp->rexmt_high; |
| 506 | *lostdup = FALSE; |
| 507 | if (lastblock != NULL) { |
| 508 | if (SEQ_LT(torexmt, lastblock->sblk_end) && |
| 509 | scb_islost(scb, torexmt)) { |
| 510 | sendunsacked: |
| 511 | *nextrexmt = torexmt; |
| 512 | /* If the left-hand edge has been SACKed, pull it in. */ |
| 513 | if (sack_block_lookup(scb, torexmt + tp->t_maxseg, &sb)) |
| 514 | *plen = sb->sblk_start - torexmt; |
| 515 | else |
| 516 | *plen = tp->t_maxseg; |
| 517 | return TRUE; |
| 518 | } |
| 519 | } |
| 520 | |
| 521 | /* See if unsent data available within send window. */ |
| 522 | off = tp->snd_max - tp->snd_una; |
| 523 | len = (long) ulmin(so->so_snd.ssb_cc, tp->snd_wnd) - off; |
| 524 | if (len > 0) { |
| 525 | *nextrexmt = tp->snd_max; /* Send new data. */ |
| 526 | *plen = tp->t_maxseg; |
| 527 | return TRUE; |
| 528 | } |
| 529 | |
| 530 | /* We're less certain this data has been lost. */ |
| 531 | if (lastblock == NULL || SEQ_LT(torexmt, lastblock->sblk_end)) |
| 532 | goto sendunsacked; |
| 533 | |
| 534 | return FALSE; |
| 535 | } |
| 536 | |
| 537 | /* |
| 538 | * Return the next sequence number higher than "*prexmt" that has |
| 539 | * not been SACKed. |
| 540 | */ |
| 541 | void |
| 542 | tcp_sack_skip_sacked(struct scoreboard *scb, tcp_seq *prexmt) |
| 543 | { |
| 544 | struct sackblock *sb; |
| 545 | |
| 546 | /* skip SACKed data */ |
| 547 | if (sack_block_lookup(scb, *prexmt, &sb)) |
| 548 | *prexmt = sb->sblk_end; |
| 549 | } |
| 550 | |
| 551 | #ifdef later |
| 552 | void |
| 553 | tcp_sack_save_scoreboard(struct scoreboard *scb) |
| 554 | { |
| 555 | struct scoreboard *scb = &tp->scb; |
| 556 | |
| 557 | scb->sackblocks_prev = scb->sackblocks; |
| 558 | TAILQ_INIT(&scb->sackblocks); |
| 559 | } |
| 560 | |
| 561 | void |
| 562 | tcp_sack_revert_scoreboard(struct scoreboard *scb, tcp_seq snd_una, |
| 563 | u_int maxseg) |
| 564 | { |
| 565 | struct sackblock *sb; |
| 566 | |
| 567 | scb->sackblocks = scb->sackblocks_prev; |
| 568 | scb->nblocks = 0; |
| 569 | TAILQ_FOREACH(sb, &scb->sackblocks, sblk_list) |
| 570 | ++scb->nblocks; |
| 571 | tcp_sack_ack_blocks(scb, snd_una); |
| 572 | scb->lastfound = NULL; |
| 573 | } |
| 574 | #endif |
| 575 | |
| 576 | #ifdef DEBUG_SACK_HISTORY |
| 577 | static void |
| 578 | tcp_sack_dump_history(char *msg, struct tcpcb *tp) |
| 579 | { |
| 580 | int i; |
| 581 | static int ndumped; |
| 582 | |
| 583 | /* only need a couple of these to debug most problems */ |
| 584 | if (++ndumped > 900) |
| 585 | return; |
| 586 | |
| 587 | kprintf("%s:\tnsackhistory %d: ", msg, tp->nsackhistory); |
| 588 | for (i = 0; i < tp->nsackhistory; ++i) |
| 589 | kprintf("[%u, %u) ", tp->sackhistory[i].rblk_start, |
| 590 | tp->sackhistory[i].rblk_end); |
| 591 | kprintf("\n"); |
| 592 | } |
| 593 | #else |
| 594 | static __inline void |
| 595 | tcp_sack_dump_history(char *msg, struct tcpcb *tp) |
| 596 | { |
| 597 | } |
| 598 | #endif |
| 599 | |
| 600 | /* |
| 601 | * Remove old SACK blocks from the SACK history that have already been ACKed. |
| 602 | */ |
| 603 | static void |
| 604 | tcp_sack_ack_history(struct tcpcb *tp) |
| 605 | { |
| 606 | int i, nblocks, openslot; |
| 607 | |
| 608 | tcp_sack_dump_history("before tcp_sack_ack_history", tp); |
| 609 | nblocks = tp->nsackhistory; |
| 610 | for (i = openslot = 0; i < nblocks; ++i) { |
| 611 | if (SEQ_LEQ(tp->sackhistory[i].rblk_end, tp->rcv_nxt)) { |
| 612 | --tp->nsackhistory; |
| 613 | continue; |
| 614 | } |
| 615 | if (SEQ_LT(tp->sackhistory[i].rblk_start, tp->rcv_nxt)) |
| 616 | tp->sackhistory[i].rblk_start = tp->rcv_nxt; |
| 617 | if (i == openslot) |
| 618 | ++openslot; |
| 619 | else |
| 620 | tp->sackhistory[openslot++] = tp->sackhistory[i]; |
| 621 | } |
| 622 | tcp_sack_dump_history("after tcp_sack_ack_history", tp); |
| 623 | KASSERT(openslot == tp->nsackhistory, |
| 624 | ("tcp_sack_ack_history miscounted: %d != %d", |
| 625 | openslot, tp->nsackhistory)); |
| 626 | } |
| 627 | |
| 628 | /* |
| 629 | * Add or merge newblock into reported history. |
| 630 | * Also remove or update SACK blocks that will be acked. |
| 631 | */ |
| 632 | static void |
| 633 | tcp_sack_update_reported_history(struct tcpcb *tp, tcp_seq start, tcp_seq end) |
| 634 | { |
| 635 | struct raw_sackblock copy[MAX_SACK_REPORT_BLOCKS]; |
| 636 | int i, cindex; |
| 637 | |
| 638 | tcp_sack_dump_history("before tcp_sack_update_reported_history", tp); |
| 639 | /* |
| 640 | * Six cases: |
| 641 | * 0) no overlap |
| 642 | * 1) newblock == oldblock |
| 643 | * 2) oldblock contains newblock |
| 644 | * 3) newblock contains oldblock |
| 645 | * 4) tail of oldblock overlaps or abuts start of newblock |
| 646 | * 5) tail of newblock overlaps or abuts head of oldblock |
| 647 | */ |
| 648 | for (i = cindex = 0; i < tp->nsackhistory; ++i) { |
| 649 | struct raw_sackblock *oldblock = &tp->sackhistory[i]; |
| 650 | tcp_seq old_start = oldblock->rblk_start; |
| 651 | tcp_seq old_end = oldblock->rblk_end; |
| 652 | |
| 653 | if (SEQ_LT(end, old_start) || SEQ_GT(start, old_end)) { |
| 654 | /* Case 0: no overlap. Copy old block. */ |
| 655 | copy[cindex++] = *oldblock; |
| 656 | continue; |
| 657 | } |
| 658 | |
| 659 | if (SEQ_GEQ(start, old_start) && SEQ_LEQ(end, old_end)) { |
| 660 | /* Cases 1 & 2. Move block to front of history. */ |
| 661 | int j; |
| 662 | |
| 663 | start = old_start; |
| 664 | end = old_end; |
| 665 | /* no need to check rest of blocks */ |
| 666 | for (j = i + 1; j < tp->nsackhistory; ++j) |
| 667 | copy[cindex++] = tp->sackhistory[j]; |
| 668 | break; |
| 669 | } |
| 670 | |
| 671 | if (SEQ_GEQ(old_end, start) && SEQ_LT(old_start, start)) { |
| 672 | /* Case 4: extend start of new block. */ |
| 673 | start = old_start; |
| 674 | } else if (SEQ_GEQ(end, old_start) && SEQ_GT(old_end, end)) { |
| 675 | /* Case 5: extend end of new block */ |
| 676 | end = old_end; |
| 677 | } else { |
| 678 | /* Case 3. Delete old block by not copying it. */ |
| 679 | KASSERT(SEQ_LEQ(start, old_start) && |
| 680 | SEQ_GEQ(end, old_end), |
| 681 | ("bad logic: old [%u, %u), new [%u, %u)", |
| 682 | old_start, old_end, start, end)); |
| 683 | } |
| 684 | } |
| 685 | |
| 686 | /* insert new block */ |
| 687 | tp->sackhistory[0].rblk_start = start; |
| 688 | tp->sackhistory[0].rblk_end = end; |
| 689 | cindex = min(cindex, MAX_SACK_REPORT_BLOCKS - 1); |
| 690 | for (i = 0; i < cindex; ++i) |
| 691 | tp->sackhistory[i + 1] = copy[i]; |
| 692 | tp->nsackhistory = cindex + 1; |
| 693 | tcp_sack_dump_history("after tcp_sack_update_reported_history", tp); |
| 694 | } |
| 695 | |
| 696 | /* |
| 697 | * Fill in SACK report to return to data sender. |
| 698 | */ |
| 699 | void |
| 700 | tcp_sack_fill_report(struct tcpcb *tp, u_char *opt, u_int *plen) |
| 701 | { |
| 702 | u_int optlen = *plen; |
| 703 | uint32_t *lp = (uint32_t *)(opt + optlen); |
| 704 | uint32_t *olp; |
| 705 | tcp_seq hstart = tp->rcv_nxt, hend; |
| 706 | int nblocks; |
| 707 | |
| 708 | KASSERT(TCP_MAXOLEN - optlen >= |
| 709 | TCPOLEN_SACK_ALIGNED + TCPOLEN_SACK_BLOCK, |
| 710 | ("no room for SACK header and one block: optlen %d", optlen)); |
| 711 | |
| 712 | if (tp->t_flags & TF_DUPSEG) |
| 713 | tcpstat.tcps_snddsackopt++; |
| 714 | else |
| 715 | tcpstat.tcps_sndsackopt++; |
| 716 | |
| 717 | olp = lp++; |
| 718 | optlen += TCPOLEN_SACK_ALIGNED; |
| 719 | |
| 720 | tcp_sack_ack_history(tp); |
| 721 | if (tp->reportblk.rblk_start != tp->reportblk.rblk_end) { |
| 722 | *lp++ = htonl(tp->reportblk.rblk_start); |
| 723 | *lp++ = htonl(tp->reportblk.rblk_end); |
| 724 | optlen += TCPOLEN_SACK_BLOCK; |
| 725 | hstart = tp->reportblk.rblk_start; |
| 726 | hend = tp->reportblk.rblk_end; |
| 727 | if (tp->t_flags & TF_ENCLOSESEG) { |
| 728 | KASSERT(TCP_MAXOLEN - optlen >= TCPOLEN_SACK_BLOCK, |
| 729 | ("no room for enclosing SACK block: oplen %d", |
| 730 | optlen)); |
| 731 | *lp++ = htonl(tp->encloseblk.rblk_start); |
| 732 | *lp++ = htonl(tp->encloseblk.rblk_end); |
| 733 | optlen += TCPOLEN_SACK_BLOCK; |
| 734 | hstart = tp->encloseblk.rblk_start; |
| 735 | hend = tp->encloseblk.rblk_end; |
| 736 | } |
| 737 | if (SEQ_GT(hstart, tp->rcv_nxt)) |
| 738 | tcp_sack_update_reported_history(tp, hstart, hend); |
| 739 | } |
| 740 | if (tcp_do_smartsack && (tp->t_flags & TF_SACKLEFT)) { |
| 741 | /* Fill in from left! Walk re-assembly queue. */ |
| 742 | struct tseg_qent *q; |
| 743 | |
| 744 | q = LIST_FIRST(&tp->t_segq); |
| 745 | while (q != NULL && |
| 746 | TCP_MAXOLEN - optlen >= TCPOLEN_SACK_BLOCK) { |
| 747 | *lp++ = htonl(q->tqe_th->th_seq); |
| 748 | *lp++ = htonl(TCP_SACK_BLKEND( |
| 749 | q->tqe_th->th_seq + q->tqe_len, |
| 750 | q->tqe_th->th_flags)); |
| 751 | optlen += TCPOLEN_SACK_BLOCK; |
| 752 | q = LIST_NEXT(q, tqe_q); |
| 753 | } |
| 754 | } else { |
| 755 | int n = 0; |
| 756 | |
| 757 | /* Fill in SACK blocks from right side. */ |
| 758 | while (n < tp->nsackhistory && |
| 759 | TCP_MAXOLEN - optlen >= TCPOLEN_SACK_BLOCK) { |
| 760 | if (tp->sackhistory[n].rblk_start != hstart) { |
| 761 | *lp++ = htonl(tp->sackhistory[n].rblk_start); |
| 762 | *lp++ = htonl(tp->sackhistory[n].rblk_end); |
| 763 | optlen += TCPOLEN_SACK_BLOCK; |
| 764 | } |
| 765 | ++n; |
| 766 | } |
| 767 | } |
| 768 | tp->reportblk.rblk_start = tp->reportblk.rblk_end; |
| 769 | tp->t_flags &= ~(TF_DUPSEG | TF_ENCLOSESEG | TF_SACKLEFT); |
| 770 | nblocks = (lp - olp - 1) / 2; |
| 771 | *olp = htonl(TCPOPT_SACK_ALIGNED | |
| 772 | (TCPOLEN_SACK + nblocks * TCPOLEN_SACK_BLOCK)); |
| 773 | *plen = optlen; |
| 774 | } |