sys/netinet/tcp_stacks/sack_filter.c

   1 /*-
   2  * Copyright (c) 2017-9 Netflix, Inc.
   3  *
   4  * Redistribution and use in source and binary forms, with or without
   5  * modification, are permitted provided that the following conditions
   6  * are met:
   7  * 1. Redistributions of source code must retain the above copyright
   8  *    notice, this list of conditions and the following disclaimer.
   9  * 2. Redistributions in binary form must reproduce the above copyright
  10  *    notice, this list of conditions and the following disclaimer in the
  11  *    documentation and/or other materials provided with the distribution.
  12  *
  13  * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
  14  * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
  15  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
  16  * ARE DISCLAIMED.  IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
  17  * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
  18  * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
  19  * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
  20  * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
  21  * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
  22  * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
  23  * SUCH DAMAGE.
  24  *
  25  */
  26 #include <sys/cdefs.h>
  27 __FBSDID("$FreeBSD$");
  28 #include <sys/types.h>
  29 #include <sys/queue.h>
  30 #include <sys/socket.h>
  31 #include <sys/mbuf.h>
  32 #include <sys/sockopt.h>
  33 #include <netinet/tcp.h>
  34 #include <netinet/tcp_var.h>
  35 #include <netinet/tcp_seq.h>
  36 #ifndef _KERNEL
  37 #include <stdio.h>
  38 #include <unistd.h>
  39 #include <string.h>
  40 #include <strings.h>
  41 #include <stdlib.h>
  42 #include <limits.h>
  43 #include <getopt.h>
  44 #endif
  45 #include "sack_filter.h"
  46
  47 /*
  48  * Sack filter is used to filter out sacks
  49  * that have already been processed. The idea
  50  * is pretty simple really, consider two sacks
  51  *
  52  * SACK 1
  53  *   cum-ack A
  54  *     sack B - C
  55  * SACK 2
  56  *   cum-ack A
  57  *     sack D - E
  58  *     sack B - C
  59  *
  60  * The previous sack information (B-C) is repeated
  61  * in SACK 2. If the receiver gets SACK 1 and then
  62  * SACK 2 then any work associated with B-C as already
  63  * been completed. This only effects where we may have
  64  * (as in bbr or rack) cases where we walk a linked list.
  65  *
  66  * Now the utility trys to keep everything in a single
  67  * cache line. This means that its not perfect and
  68  * it could be that so big of sack's come that a
  69  * "remembered" processed sack falls off the list and
  70  * so gets re-processed. Thats ok, it just means we
  71  * did some extra work. We could of course take more
  72  * cache line hits by expanding the size of this
  73  * structure, but then that would cost more.
  74  */
  75
  76 #ifndef _KERNEL
  77 int detailed_dump = 0;
  78 uint64_t cnt_skipped_oldsack = 0;
  79 uint64_t cnt_used_oldsack = 0;
  80 int highest_used=0;
  81 int over_written=0;
  82 int empty_avail=0;
  83 int no_collapse = 0;
  84 FILE *out = NULL;
  85 FILE *in = NULL;
  86 #endif
  87
  88 #define sack_blk_used(sf, i) ((1 << i) & sf->sf_bits)
  89 #define sack_blk_set(sf, i) ((1 << i) | sf->sf_bits)
  90 #define sack_blk_clr(sf, i) (~(1 << i) & sf->sf_bits)
  91
  92 #ifndef _KERNEL
  93 static
  94 #endif
  95 void
  96 sack_filter_clear(struct sack_filter *sf, tcp_seq seq)
  97 {
  98         sf->sf_ack = seq;
  99         sf->sf_bits = 0;
 100         sf->sf_cur = 0;
 101         sf->sf_used = 0;
 102 }
 103 /*
 104  * Given a previous sack filter block, filter out
 105  * any entries where the cum-ack moves over them
 106  * fully or partially.
 107  */
 108 static void
 109 sack_filter_prune(struct sack_filter *sf, tcp_seq th_ack)
 110 {
 111         int32_t i;
 112         /* start with the oldest */
 113         for (i = 0; i < SACK_FILTER_BLOCKS; i++) {
 114                 if (sack_blk_used(sf, i)) {
 115                         if (SEQ_GT(th_ack, sf->sf_blks[i].end)) {
 116                                 /* This block is consumed */
 117                                 sf->sf_bits = sack_blk_clr(sf, i);
 118                                 sf->sf_used--;
 119                         } else if (SEQ_GT(th_ack, sf->sf_blks[i].start)) {
 120                                 /* Some of it is acked */
 121                                 sf->sf_blks[i].start = th_ack;
 122                                 /* We could in theory break here, but
 123                                  * there are some broken implementations
 124                                  * that send multiple blocks. We want
 125                                  * to catch them all with similar seq's.
 126                                  */
 127                         }
 128                 }
 129         }
 130         sf->sf_ack = th_ack;
 131 }
 132
 133 /*
 134  * Return true if you find that
 135  * the sackblock b is on the score
 136  * board. Update it along the way
 137  * if part of it is on the board.
 138  */
 139 static int32_t
 140 is_sack_on_board(struct sack_filter *sf, struct sackblk *b)
 141 {
 142         int32_t i, cnt;
 143
 144         for (i = sf->sf_cur, cnt=0; cnt < SACK_FILTER_BLOCKS; cnt++) {
 145                 if (sack_blk_used(sf, i)) {
 146                         if (SEQ_LT(b->start, sf->sf_ack)) {
 147                                 /* Behind cum-ack update */
 148                                 b->start = sf->sf_ack;
 149                         }
 150                         if (SEQ_LT(b->end, sf->sf_ack)) {
 151                                 /* End back behind too */
 152                                 b->end = sf->sf_ack;
 153                         }
 154                         if (b->start == b->end) {
 155                                 return(1);
 156                         }
 157                         /* Jonathans Rule 1 */
 158                         if (SEQ_LEQ(sf->sf_blks[i].start, b->start) &&
 159                             SEQ_GEQ(sf->sf_blks[i].end, b->end)) {
 160                                 /**
 161                                  * Our board has this entirely in
 162                                  * whole or in part:
 163                                  *
 164                                  * board  |-------------|
 165                                  * sack   |-------------|
 166                                  * <or>
 167                                  * board  |-------------|
 168                                  * sack       |----|
 169                                  *
 170                                  */
 171                                 return(1);
 172                         }
 173                         /* Jonathans Rule 2 */
 174                         if(SEQ_LT(sf->sf_blks[i].end, b->start)) {
 175                                 /**
 176                                  * Not near each other:
 177                                  *
 178                                  * board   |---|
 179                                  * sack           |---|
 180                                  */
 181                                 goto nxt_blk;
 182                         }
 183                         /* Jonathans Rule 3 */
 184                         if (SEQ_GT(sf->sf_blks[i].start, b->end)) {
 185                                 /**
 186                                  * Not near each other:
 187                                  *
 188                                  * board         |---|
 189                                  * sack  |---|
 190                                  */
 191                                 goto nxt_blk;
 192                         }
 193                         if (SEQ_LEQ(sf->sf_blks[i].start, b->start)) {
 194                                 /**
 195                                  * The board block partial meets:
 196                                  *
 197                                  *  board   |--------|
 198                                  *  sack        |----------|
 199                                  *    <or>
 200                                  *  board   |--------|
 201                                  *  sack    |--------------|
 202                                  *
 203                                  * up with this one (we have part of it).
 204                                  * 1) Update the board block to the new end
 205                                  *      and
 206                                  * 2) Update the start of this block to my end.
 207                                  */
 208                                 b->start = sf->sf_blks[i].end;
 209                                 sf->sf_blks[i].end = b->end;
 210                                 goto nxt_blk;
 211                         }
 212                         if (SEQ_GEQ(sf->sf_blks[i].end, b->end)) {
 213                                 /**
 214                                  * The board block partial meets:
 215                                  *
 216                                  *  board       |--------|
 217                                  *  sack  |----------|
 218                                  *     <or>
 219                                  *  board       |----|
 220                                  *  sack  |----------|
 221                                  * 1) Update the board block to the new start
 222                                  *      and
 223                                  * 2) Update the start of this block to my end.
 224                                  */
 225                                 b->end = sf->sf_blks[i].start;
 226                                 sf->sf_blks[i].start = b->start;
 227                                 goto nxt_blk;
 228                         }
 229                 }
 230         nxt_blk:
 231                 i++;
 232                 i %= SACK_FILTER_BLOCKS;
 233         }
 234         /* Did we totally consume it in pieces? */
 235         if (b->start != b->end)
 236                 return(0);
 237         else
 238                 return(1);
 239 }
 240
 241 static int32_t
 242 sack_filter_old(struct sack_filter *sf, struct sackblk *in, int  numblks)
 243 {
 244         int32_t num, i;
 245         struct sackblk blkboard[TCP_MAX_SACK];
 246         /*
 247          * An old sack has arrived. It may contain data
 248          * we do not have. We might not have it since
 249          * we could have had a lost ack <or> we might have the
 250          * entire thing on our current board. We want to prune
 251          * off anything we have. With this function though we
 252          * won't add to the board.
 253          */
 254         for( i = 0, num = 0; i<numblks; i++ ) {
 255                 if (is_sack_on_board(sf, &in[i])) {
 256 #ifndef _KERNEL
 257                         cnt_skipped_oldsack++;
 258 #endif
 259                         continue;
 260                 }
 261                 /* Did not find it (or found only
 262                  * a piece of it). Copy it to
 263                  * our outgoing board.
 264                  */
 265                 memcpy(&blkboard[num], &in[i], sizeof(struct sackblk));
 266 #ifndef _KERNEL
 267                 cnt_used_oldsack++;
 268 #endif
 269                 num++;
 270         }
 271         if (num) {
 272                 memcpy(in, blkboard, (num * sizeof(struct sackblk)));
 273         }
 274         return (num);
 275 }
 276
 277 /*
 278  * Given idx its used but there is space available
 279  * move the entry to the next free slot
 280  */
 281 static void
 282 sack_move_to_empty(struct sack_filter *sf, uint32_t idx)
 283 {
 284         int32_t i, cnt;
 285
 286         i = (idx + 1) % SACK_FILTER_BLOCKS;
 287         for (cnt=0; cnt <(SACK_FILTER_BLOCKS-1); cnt++) {
 288                 if (sack_blk_used(sf, i) == 0) {
 289                         memcpy(&sf->sf_blks[i], &sf->sf_blks[idx], sizeof(struct sackblk));
 290                         sf->sf_bits = sack_blk_clr(sf, idx);
 291                         sf->sf_bits = sack_blk_set(sf, i);
 292                         return;
 293                 }
 294                 i++;
 295                 i %= SACK_FILTER_BLOCKS;
 296         }
 297 }
 298
 299 static int32_t
 300 sack_filter_new(struct sack_filter *sf, struct sackblk *in, int numblks, tcp_seq th_ack)
 301 {
 302         struct sackblk blkboard[TCP_MAX_SACK];
 303         int32_t num, i;
 304         /*
 305          * First lets trim the old and possibly
 306          * throw any away we have.
 307          */
 308         for(i=0, num=0; i<numblks; i++) {
 309                 if (is_sack_on_board(sf, &in[i]))
 310                         continue;
 311                 memcpy(&blkboard[num], &in[i], sizeof(struct sackblk));
 312                 num++;
 313         }
 314         if (num == 0)
 315                 return(num);
 316
 317         /* Now what we are left with is either
 318          * completely merged on to the board
 319          * from the above steps, or is new
 320          * and need to be added to the board
 321          * with the last one updated to current.
 322          *
 323          * First copy it out, we want to return that
 324          * to our caller for processing.
 325          */
 326         memcpy(in, blkboard, (num * sizeof(struct sackblk)));
 327         numblks = num;
 328         /* Now go through and add to our board as needed */
 329         for(i=(num-1); i>=0; i--) {
 330                 if (is_sack_on_board(sf, &blkboard[i])) {
 331                         continue;
 332                 }
 333                 /* Add this guy its not listed */
 334                 sf->sf_cur++;
 335                 sf->sf_cur %= SACK_FILTER_BLOCKS;
 336                 if ((sack_blk_used(sf, sf->sf_cur)) &&
 337                     (sf->sf_used < SACK_FILTER_BLOCKS)) {
 338                         sack_move_to_empty(sf, sf->sf_cur);
 339                 }
 340 #ifndef _KERNEL
 341                 if (sack_blk_used(sf, sf->sf_cur)) {
 342                         over_written++;
 343                         if (sf->sf_used < SACK_FILTER_BLOCKS)
 344                                 empty_avail++;
 345                 }
 346 #endif
 347                 memcpy(&sf->sf_blks[sf->sf_cur], &in[i], sizeof(struct sackblk));
 348                 if (sack_blk_used(sf, sf->sf_cur) == 0) {
 349                         sf->sf_used++;
 350 #ifndef _KERNEL
 351                         if (sf->sf_used > highest_used)
 352                                 highest_used = sf->sf_used;
 353 #endif
 354                         sf->sf_bits = sack_blk_set(sf, sf->sf_cur);
 355                 }
 356         }
 357         return(numblks);
 358 }
 359
 360 /*
 361  * Given a sack block on the board (the skip index) see if
 362  * any other used entries overlap or meet, if so return the index.
 363  */
 364 static int32_t
 365 sack_blocks_overlap_or_meet(struct sack_filter *sf, struct sackblk *sb, uint32_t skip)
 366 {
 367         int32_t i;
 368
 369         for(i=0; i<SACK_FILTER_BLOCKS; i++) {
 370                 if (sack_blk_used(sf, i) == 0)
 371                         continue;
 372                 if (i == skip)
 373                         continue;
 374                 if (SEQ_GEQ(sf->sf_blks[i].end, sb->start) &&
 375                     SEQ_LEQ(sf->sf_blks[i].end, sb->end) &&
 376                     SEQ_LEQ(sf->sf_blks[i].start, sb->start)) {
 377                         /**
 378                          * The two board blocks meet:
 379                          *
 380                          *  board1   |--------|
 381                          *  board2       |----------|
 382                          *    <or>
 383                          *  board1   |--------|
 384                          *  board2   |--------------|
 385                          *    <or>
 386                          *  board1   |--------|
 387                          *  board2   |--------|
 388                          */
 389                         return(i);
 390                 }
 391                 if (SEQ_LEQ(sf->sf_blks[i].start, sb->end) &&
 392                     SEQ_GEQ(sf->sf_blks[i].start, sb->start) &&
 393                     SEQ_GEQ(sf->sf_blks[i].end, sb->end)) {
 394                         /**
 395                          * The board block partial meets:
 396                          *
 397                          *  board       |--------|
 398                          *  sack  |----------|
 399                          *     <or>
 400                          *  board       |----|
 401                          *  sack  |----------|
 402                          * 1) Update the board block to the new start
 403                          *      and
 404                          * 2) Update the start of this block to my end.
 405                          */
 406                         return(i);
 407                 }
 408         }
 409         return (-1);
 410 }
 411
 412 /*
 413  * Collapse entry src into entry into
 414  * and free up the src entry afterwards.
 415  */
 416 static void
 417 sack_collapse(struct sack_filter *sf, int32_t src, int32_t into)
 418 {
 419         if (SEQ_LT(sf->sf_blks[src].start, sf->sf_blks[into].start)) {
 420                 /* src has a lower starting point */
 421                 sf->sf_blks[into].start = sf->sf_blks[src].start;
 422         }
 423         if (SEQ_GT(sf->sf_blks[src].end, sf->sf_blks[into].end)) {
 424                 /* src has a higher ending point */
 425                 sf->sf_blks[into].end = sf->sf_blks[src].end;
 426         }
 427         sf->sf_bits = sack_blk_clr(sf, src);
 428         sf->sf_used--;
 429 }
 430
 431 static void
 432 sack_board_collapse(struct sack_filter *sf)
 433 {
 434         int32_t i, j, i_d, j_d;
 435
 436         for(i=0; i<SACK_FILTER_BLOCKS; i++) {
 437                 if (sack_blk_used(sf, i) == 0)
 438                         continue;
 439                 /*
 440                  * Look at all other blocks but this guy
 441                  * to see if they overlap. If so we collapse
 442                  * the two blocks together.
 443                  */
 444                 j = sack_blocks_overlap_or_meet(sf, &sf->sf_blks[i], i);
 445                 if (j == -1) {
 446                         /* No overlap */
 447                         continue;
 448                 }
 449                 /*
 450                  * Ok j and i overlap with each other, collapse the
 451                  * one out furthest away from the current position.
 452                  */
 453                 if (sf->sf_cur > i)
 454                         i_d = sf->sf_cur - i;
 455                 else
 456                         i_d = i - sf->sf_cur;
 457                 if (sf->sf_cur > j)
 458                         j_d = sf->sf_cur - j;
 459                 else
 460                         j_d = j - sf->sf_cur;
 461                 if (j_d > i_d) {
 462                         sack_collapse(sf, j, i);
 463                 } else
 464                         sack_collapse(sf, i, j);
 465         }
 466 }
 467
 468 #ifndef _KERNEL
 469 uint64_t saved=0;
 470 uint64_t tot_sack_blks=0;
 471
 472 static void
 473 sack_filter_dump(FILE *out, struct sack_filter *sf)
 474 {
 475         int i;
 476         fprintf(out, "  sf_ack:%u sf_bits:0x%x c:%d used:%d\n",
 477                 sf->sf_ack, sf->sf_bits,
 478                 sf->sf_cur, sf->sf_used);
 479
 480         for(i=0; i<SACK_FILTER_BLOCKS; i++) {
 481                 if (sack_blk_used(sf, i)) {
 482                         fprintf(out, "Entry:%d start:%u end:%u\n", i,
 483                                sf->sf_blks[i].start,
 484                                sf->sf_blks[i].end);
 485                 }
 486         }
 487 }
 488 #endif
 489
 490 #ifndef _KERNEL
 491 static
 492 #endif
 493 int
 494 sack_filter_blks(struct sack_filter *sf, struct sackblk *in, int numblks,
 495                  tcp_seq th_ack)
 496 {
 497         int32_t i, ret;
 498
 499         if (numblks > TCP_MAX_SACK) {
 500 #ifdef _KERNEL
 501                 panic("sf:%p sb:%p Impossible number of sack blocks %d > 4\n",
 502                       sf, in,
 503                       numblks);
 504 #endif
 505                 return(numblks);
 506         }
 507 #ifndef _KERNEL
 508         if ((sf->sf_used > 1) && (no_collapse == 0))
 509                 sack_board_collapse(sf);
 510
 511 #else
 512         if (sf->sf_used > 1)
 513                 sack_board_collapse(sf);
 514 #endif
 515         if ((sf->sf_used == 0) && numblks) {
 516                 /*
 517                  * We are brand new add the blocks in
 518                  * reverse order. Note we can see more
 519                  * than one in new, since ack's could be lost.
 520                  */
 521                 int cnt_added = 0;
 522
 523                 sf->sf_ack = th_ack;
 524                 for(i=(numblks-1), sf->sf_cur=0; i >= 0; i--) {
 525                         memcpy(&sf->sf_blks[sf->sf_cur], &in[i], sizeof(struct sackblk));
 526                         sf->sf_bits = sack_blk_set(sf, sf->sf_cur);
 527                         sf->sf_cur++;
 528                         sf->sf_cur %= SACK_FILTER_BLOCKS;
 529                         sf->sf_used++;
 530                         cnt_added++;
 531 #ifndef _KERNEL
 532                         if (sf->sf_used > highest_used)
 533                                 highest_used = sf->sf_used;
 534 #endif
 535                 }
 536                 if (sf->sf_cur)
 537                         sf->sf_cur--;
 538
 539                 return (cnt_added);
 540         }
 541         if (SEQ_GT(th_ack, sf->sf_ack)) {
 542                 sack_filter_prune(sf, th_ack);
 543         }
 544         if (numblks) {
 545                 if (SEQ_GEQ(th_ack, sf->sf_ack)) {
 546                         ret = sack_filter_new(sf, in, numblks, th_ack);
 547                 } else {
 548                         ret = sack_filter_old(sf, in, numblks);
 549                 }
 550         } else
 551                 ret = 0;
 552         return (ret);
 553 }
 554
 555 void
 556 sack_filter_reject(struct sack_filter *sf, struct sackblk *in)
 557 {
 558         /*
 559          * Given a specified block (that had made
 560          * it past the sack filter). Reject that
 561          * block triming it off any sack-filter block
 562          * that has it. Usually because the block was
 563          * too small and did not cover a whole send.
 564          *
 565          * This function will only "undo" sack-blocks
 566          * that are fresh and touch the edges of
 567          * blocks in our filter.
 568          */
 569         int i;
 570
 571         for(i=0; i<SACK_FILTER_BLOCKS; i++) {
 572                 if (sack_blk_used(sf, i) == 0)
 573                         continue;
 574                 /*
 575                  * Now given the sack-filter block does it touch
 576                  * with one of the ends
 577                  */
 578                 if (sf->sf_blks[i].end == in->end) {
 579                         /* The end moves back to start */
 580                         if (SEQ_GT(in->start, sf->sf_blks[i].start))
 581                                 /* in-blk       |----| */
 582                                 /* sf-blk  |---------| */
 583                                 sf->sf_blks[i].end = in->start;
 584                         else {
 585                                 /* It consumes this block */
 586                                 /* in-blk  |---------| */
 587                                 /* sf-blk     |------| */
 588                                 /* <or> */
 589                                 /* sf-blk  |---------| */
 590                                 sf->sf_bits = sack_blk_clr(sf, i);
 591                                 sf->sf_used--;
 592                         }
 593                         continue;
 594                 }
 595                 if (sf->sf_blks[i].start == in->start) {
 596                         if (SEQ_LT(in->end, sf->sf_blks[i].end)) {
 597                                 /* in-blk  |----|      */
 598                                 /* sf-blk  |---------| */
 599                                 sf->sf_blks[i].start = in->end;
 600                         } else {
 601                                 /* It consumes this block */
 602                                 /* in-blk  |----------|  */
 603                                 /* sf-blk  |-------|     */
 604                                 /* <or> */
 605                                 /* sf-blk  |----------|  */
 606                                 sf->sf_bits = sack_blk_clr(sf, i);
 607                                 sf->sf_used--;
 608                         }
 609                         continue;
 610                 }
 611         }
 612 }
 613
 614 #ifndef _KERNEL
 615
 616 int
 617 main(int argc, char **argv)
 618 {
 619         char buffer[512];
 620         struct sackblk blks[TCP_MAX_SACK];
 621         FILE *err;
 622         tcp_seq th_ack, snd_una, snd_max = 0;
 623         struct sack_filter sf;
 624         int32_t numblks,i;
 625         int snd_una_set=0;
 626         double a, b, c;
 627         int invalid_sack_print = 0;
 628         uint32_t chg_remembered=0;
 629         uint32_t sack_chg=0;
 630         char line_buf[10][256];
 631         int line_buf_at=0;
 632
 633         in = stdin;
 634         out = stdout;
 635         while ((i = getopt(argc, argv, "ndIi:o:?h")) != -1) {
 636                 switch (i) {
 637                 case 'n':
 638                         no_collapse = 1;
 639                         break;
 640                 case 'd':
 641                         detailed_dump = 1;
 642                         break;
 643                 case'I':
 644                         invalid_sack_print = 1;
 645                         break;
 646                 case 'i':
 647                         in = fopen(optarg, "r");
 648                         if (in == NULL) {
 649                                 fprintf(stderr, "Fatal error can't open %s for input\n", optarg);
 650                                 exit(-1);
 651                         }
 652                         break;
 653                 case 'o':
 654                         out = fopen(optarg, "w");
 655                         if (out == NULL) {
 656                                 fprintf(stderr, "Fatal error can't open %s for output\n", optarg);
 657                                 exit(-1);
 658                         }
 659                         break;
 660                 default:
 661                 case '?':
 662                 case 'h':
 663                         fprintf(stderr, "Use %s [ -i infile -o outfile -I]\n", argv[0]);
 664                         return(0);
 665                         break;
 666                 };
 667         }
 668         sack_filter_clear(&sf, 0);
 669         memset(buffer, 0, sizeof(buffer));
 670         memset(blks, 0, sizeof(blks));
 671         numblks = 0;
 672         fprintf(out, "************************************\n");
 673         while (fgets(buffer, sizeof(buffer), in) != NULL) {
 674                 sprintf(line_buf[line_buf_at], "%s", buffer);
 675                 line_buf_at++;
 676                 if (strncmp(buffer, "QUIT", 4) == 0) {
 677                         break;
 678                 } else if (strncmp(buffer, "DUMP", 4) == 0) {
 679                         sack_filter_dump(out, &sf);
 680                 } else if (strncmp(buffer, "MAX:", 4) == 0) {
 681                         snd_max = strtoul(&buffer[4], NULL, 0);
 682                 } else if (strncmp(buffer, "COMMIT", 6) == 0) {
 683                         int nn, ii;
 684                         if (numblks) {
 685                                 uint32_t szof, tot_chg;
 686                                 for(ii=0; ii<line_buf_at; ii++) {
 687                                         fprintf(out, "%s", line_buf[ii]);
 688                                 }
 689                                 fprintf(out, "------------------------------------\n");
 690                                 nn = sack_filter_blks(&sf, blks, numblks, th_ack);
 691                                 saved += numblks - nn;
 692                                 tot_sack_blks += numblks;
 693                                 fprintf(out, "ACK:%u\n", sf.sf_ack);
 694                                 for(ii=0, tot_chg=0; ii<nn; ii++) {
 695                                         szof = blks[ii].end - blks[ii].start;
 696                                         tot_chg += szof;
 697                                         fprintf(out, "SACK:%u:%u [%u]\n",
 698                                                blks[ii].start,
 699                                                 blks[ii].end, szof);
 700                                 }
 701                                 fprintf(out,"************************************\n");
 702                                 chg_remembered = tot_chg;
 703                                 if (detailed_dump) {
 704                                         sack_filter_dump(out, &sf);
 705                                         fprintf(out,"************************************\n");
 706                                 }
 707                         }
 708                         memset(blks, 0, sizeof(blks));
 709                         memset(line_buf, 0, sizeof(line_buf));
 710                         line_buf_at=0;
 711                         numblks = 0;
 712                 } else if (strncmp(buffer, "CHG:", 4) == 0) {
 713                         sack_chg = strtoul(&buffer[4], NULL, 0);
 714                         if ((sack_chg != chg_remembered) &&
 715                             (sack_chg > chg_remembered)){
 716                                 fprintf(out,"***WARNING WILL RODGERS DANGER!! sack_chg:%u last:%u\n",
 717                                         sack_chg, chg_remembered
 718                                         );
 719                         }
 720                         sack_chg = chg_remembered = 0;
 721                 } else if (strncmp(buffer, "RXT", 3) == 0) {
 722                         sack_filter_clear(&sf, snd_una);
 723                 } else if (strncmp(buffer, "ACK:", 4) == 0) {
 724                         th_ack = strtoul(&buffer[4], NULL, 0);
 725                         if (snd_una_set == 0) {
 726                                 snd_una = th_ack;
 727                                 snd_una_set = 1;
 728                         } else if (SEQ_GT(th_ack, snd_una)) {
 729                                 snd_una = th_ack;
 730                         }
 731                 } else if (strncmp(buffer, "EXIT", 4) == 0) {
 732                         sack_filter_clear(&sf, snd_una);
 733                         sack_chg = chg_remembered = 0;
 734                 } else if (strncmp(buffer, "SACK:", 5) == 0) {
 735                         char *end=NULL;
 736                         uint32_t start;
 737                         uint32_t endv;
 738
 739                         start = strtoul(&buffer[5], &end, 0);
 740                         if (end) {
 741                                 endv = strtoul(&end[1], NULL, 0);
 742                         } else {
 743                                 fprintf(out, "--Sack invalid skip 0 start:%u : ??\n", start);
 744                                 continue;
 745                         }
 746                         if (SEQ_GT(endv, snd_max))
 747                                 snd_max = endv;
 748                         if (SEQ_LT(endv, start)) {
 749                                 fprintf(out, "--Sack invalid skip 1 endv:%u < start:%u\n", endv, start);
 750                                 continue;
 751                         }
 752                         if (numblks == TCP_MAX_SACK) {
 753                                 fprintf(out, "--Exceeded max %d\n", numblks);
 754                                 exit(0);
 755                         }
 756                         blks[numblks].start = start;
 757                         blks[numblks].end = endv;
 758                         numblks++;
 759                 } else if (strncmp(buffer, "REJ:n:n", 4) == 0) {
 760                         struct sackblk in;
 761                         char *end=NULL;
 762
 763                         in.start = strtoul(&buffer[4], &end, 0);
 764                         if (end) {
 765                                 in.end = strtoul(&end[1], NULL, 0);
 766                                 sack_filter_reject(&sf, &in);
 767                         } else
 768                                 fprintf(out, "Invalid input END:A:B\n");
 769                 } else if (strncmp(buffer, "HELP", 4) == 0) {
 770                         fprintf(out, "You can input:\n");
 771                         fprintf(out, "SACK:S:E -- to define a sack block\n");
 772                         fprintf(out, "RXT -- to clear the filter without changing the remembered\n");
 773                         fprintf(out, "EXIT -- To clear the sack filter and start all fresh\n");
 774                         fprintf(out, "ACK:N -- To advance the cum-ack to N\n");
 775                         fprintf(out, "MAX:N -- To set send-max to N\n");
 776                         fprintf(out, "COMMIT -- To apply the sack you built to the filter and dump the filter\n");
 777                         fprintf(out, "DUMP -- To display the current contents of the sack filter\n");
 778                         fprintf(out, "QUIT -- To exit this program\n");
 779                 } else {
 780                         fprintf(out, "Command %s unknown\n", buffer);
 781                 }
 782                 memset(buffer, 0, sizeof(buffer));
 783         }
 784         if (in != stdin) {
 785                 fclose(in);
 786         }
 787         if (out != stdout) {
 788                 fclose(out);
 789         }
 790         a = saved * 100.0;
 791         b = tot_sack_blks * 1.0;
 792         if (b > 0.0)
 793                 c = a/b;
 794         else
 795                 c = 0.0;
 796         if (out != stdout)
 797                 err = stdout;
 798         else
 799                 err = stderr;
 800         fprintf(err, "Saved %lu sack blocks out of %lu (%2.3f%%) old_skip:%lu old_usd:%lu high_cnt:%d ow:%d ea:%d\n",
 801                 saved, tot_sack_blks, c, cnt_skipped_oldsack, cnt_used_oldsack, highest_used, over_written, empty_avail);
 802         return(0);
 803 }
 804 #endif