src/plugins/unittest/tcp_test.c

   1 /*
   2  * Copyright (c) 2017-2019 Cisco and/or its affiliates.
   3  * Licensed under the Apache License, Version 2.0 (the "License");
   4  * you may not use this file except in compliance with the License.
   5  * You may obtain a copy of the License at:
   6  *
   7  *     http://www.apache.org/licenses/LICENSE-2.0
   8  *
   9  * Unless required by applicable law or agreed to in writing, software
  10  * distributed under the License is distributed on an "AS IS" BASIS,
  11  * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
  12  * See the License for the specific language governing permissions and
  13  * limitations under the License.
  14  */
  15 #include <vnet/tcp/tcp.h>
  16 #include <vnet/tcp/tcp_inlines.h>
  17
  18 #define TCP_TEST_I(_cond, _comment, _args...)                   \
  19 ({                                                              \
  20   int _evald = (_cond);                                         \
  21   if (!(_evald)) {                                              \
  22     fformat(stderr, "FAIL:%d: " _comment "\n",                  \
  23             __LINE__, ##_args);                                 \
  24   } else {                                                      \
  25     fformat(stderr, "PASS:%d: " _comment "\n",                  \
  26             __LINE__, ##_args);                                 \
  27   }                                                             \
  28   _evald;                                                       \
  29 })
  30
  31 #define TCP_TEST(_cond, _comment, _args...)                     \
  32 {                                                               \
  33     if (!TCP_TEST_I(_cond, _comment, ##_args)) {                \
  34         return 1;                                               \
  35     }                                                           \
  36 }
  37
  38 /* *INDENT-OFF* */
  39 scoreboard_trace_elt_t sb_trace[] = {};
  40 /* *INDENT-ON* */
  41
  42 static int
  43 tcp_test_scoreboard_replay (vlib_main_t * vm, unformat_input_t * input)
  44 {
  45   int verbose = 0;
  46   tcp_connection_t _tc, *tc = &_tc;
  47   u8 *s = 0;
  48
  49   while (unformat_check_input (input) != UNFORMAT_END_OF_INPUT)
  50     {
  51       if (unformat (input, "detail"))
  52         verbose = 1;
  53       else
  54         {
  55           clib_error_t *e = clib_error_return
  56             (0, "unknown input `%U'", format_unformat_error, input);
  57           clib_error_report (e);
  58           return -1;
  59         }
  60     }
  61
  62 #if TCP_SCOREBOARD_TRACE
  63   tc->sack_sb.trace = sb_trace;
  64 #endif
  65   s = tcp_scoreboard_replay (s, tc, verbose);
  66   vlib_cli_output (vm, "%v", s);
  67   return 0;
  68 }
  69
  70 static int
  71 tcp_test_sack_rx (vlib_main_t * vm, unformat_input_t * input)
  72 {
  73   tcp_connection_t _tc, *tc = &_tc;
  74   sack_scoreboard_t *sb = &tc->sack_sb;
  75   sack_block_t *sacks = 0, block;
  76   sack_scoreboard_hole_t *hole;
  77   int i, verbose = 0;
  78
  79   while (unformat_check_input (input) != UNFORMAT_END_OF_INPUT)
  80     {
  81       if (unformat (input, "verbose"))
  82         verbose = 1;
  83       else if (unformat (input, "replay"))
  84         return tcp_test_scoreboard_replay (vm, input);
  85     }
  86
  87   clib_memset (tc, 0, sizeof (*tc));
  88
  89   tc->flags |= TCP_CONN_FAST_RECOVERY | TCP_CONN_RECOVERY;
  90   tc->snd_una = 0;
  91   tc->snd_una_max = 1000;
  92   tc->snd_nxt = 1000;
  93   tc->rcv_opts.flags |= TCP_OPTS_FLAG_SACK;
  94   tc->snd_mss = 150;
  95   scoreboard_init (&tc->sack_sb);
  96
  97   for (i = 0; i < 1000 / 100; i++)
  98     {
  99       block.start = i * 100;
 100       block.end = (i + 1) * 100;
 101       vec_add1 (sacks, block);
 102     }
 103
 104   /*
 105    * Inject even blocks
 106    */
 107
 108   for (i = 0; i < 1000 / 200; i++)
 109     {
 110       vec_add1 (tc->rcv_opts.sacks, sacks[i * 2]);
 111     }
 112   tc->rcv_opts.n_sack_blocks = vec_len (tc->rcv_opts.sacks);
 113   tcp_rcv_sacks (tc, 0);
 114
 115   if (verbose)
 116     vlib_cli_output (vm, "sb after even blocks (mss %u):\n%U",
 117                      tc->snd_mss, format_tcp_scoreboard, sb, tc);
 118
 119   TCP_TEST ((pool_elts (sb->holes) == 5),
 120             "scoreboard has %d elements", pool_elts (sb->holes));
 121
 122   /* First SACK block should be rejected */
 123   hole = scoreboard_first_hole (sb);
 124   TCP_TEST ((hole->start == 0 && hole->end == 200),
 125             "first hole start %u end %u", hole->start, hole->end);
 126   hole = scoreboard_last_hole (sb);
 127   TCP_TEST ((hole->start == 900 && hole->end == 1000),
 128             "last hole start %u end %u", hole->start, hole->end);
 129   TCP_TEST ((sb->sacked_bytes == 400), "sacked bytes %d", sb->sacked_bytes);
 130   TCP_TEST ((!sb->is_reneging), "is not reneging");
 131   TCP_TEST ((sb->last_sacked_bytes == 400),
 132             "last sacked bytes %d", sb->last_sacked_bytes);
 133   TCP_TEST ((sb->high_sacked == 900), "high sacked %u", sb->high_sacked);
 134   TCP_TEST ((sb->lost_bytes == 300), "lost bytes %u", sb->lost_bytes);
 135
 136   /*
 137    * Inject odd blocks except the last
 138    *
 139    */
 140
 141   vec_reset_length (tc->rcv_opts.sacks);
 142   for (i = 0; i < 800 / 200; i++)
 143     {
 144       vec_add1 (tc->rcv_opts.sacks, sacks[i * 2 + 1]);
 145     }
 146   tc->rcv_opts.n_sack_blocks = vec_len (tc->rcv_opts.sacks);
 147   tcp_rcv_sacks (tc, 0);
 148
 149   if (verbose)
 150     vlib_cli_output (vm, "\nsb after odd blocks:\n%U", format_tcp_scoreboard,
 151                      sb, tc);
 152
 153   hole = scoreboard_first_hole (sb);
 154   TCP_TEST ((pool_elts (sb->holes) == 2),
 155             "scoreboard has %d holes", pool_elts (sb->holes));
 156   TCP_TEST ((hole->start == 0 && hole->end == 100),
 157             "first hole start %u end %u", hole->start, hole->end);
 158   TCP_TEST ((sb->sacked_bytes == 800), "sacked bytes %d", sb->sacked_bytes);
 159   TCP_TEST ((!sb->is_reneging), "is not reneging");
 160   TCP_TEST ((sb->high_sacked == 900), "high sacked %u", sb->high_sacked);
 161   TCP_TEST ((sb->last_sacked_bytes == 400),
 162             "last sacked bytes %d", sb->last_sacked_bytes);
 163   TCP_TEST ((sb->lost_bytes == 100), "lost bytes %u", sb->lost_bytes);
 164
 165   /*
 166    *  Ack until byte 100 - this is reneging because we should ack until 900
 167    */
 168   tcp_rcv_sacks (tc, 100);
 169   if (verbose)
 170     vlib_cli_output (vm, "\nack until byte 100:\n%U", format_tcp_scoreboard,
 171                      sb, tc);
 172
 173   TCP_TEST ((pool_elts (sb->holes) == 1), "scoreboard has %d elements",
 174             pool_elts (sb->holes));
 175   TCP_TEST ((sb->is_reneging), "is reneging");
 176
 177   /*
 178    * Make sure we accept duplicate acks while reneging.
 179    */
 180   tc->snd_una = 100;
 181   sb->high_rxt = 950;
 182
 183   block.start = 900;
 184   block.end = 950;
 185   vec_add1 (tc->rcv_opts.sacks, block);
 186
 187   tcp_rcv_sacks (tc, 100);
 188   TCP_TEST ((pool_elts (sb->holes) == 1), "scoreboard has %d elements",
 189             pool_elts (sb->holes));
 190   TCP_TEST ((sb->is_reneging), "is reneging");
 191   TCP_TEST ((sb->last_sacked_bytes == 50), "last sacked bytes %d",
 192             sb->last_sacked_bytes);
 193   TCP_TEST ((sb->rxt_sacked == 50), "last rxt sacked bytes %d",
 194             sb->rxt_sacked);
 195
 196   /*
 197    * Sack all up to 950
 198    */
 199   tcp_rcv_sacks (tc, 950);
 200   TCP_TEST ((sb->high_sacked == 950), "max sacked byte %u", sb->high_sacked);
 201   TCP_TEST ((sb->sacked_bytes == 0), "sacked bytes %d", sb->sacked_bytes);
 202   TCP_TEST ((sb->last_sacked_bytes == 0),
 203             "last sacked bytes %d", sb->last_sacked_bytes);
 204   TCP_TEST ((sb->lost_bytes == 0), "lost bytes %u", sb->lost_bytes);
 205   TCP_TEST ((!sb->is_reneging), "is not reneging");
 206
 207   /*
 208    * Sack [960 970] [980 990]
 209    */
 210   sb->high_rxt = 985;
 211
 212   tc->snd_una = 950;
 213   vec_reset_length (tc->rcv_opts.sacks);
 214   block.start = 960;
 215   block.end = 970;
 216   vec_add1 (tc->rcv_opts.sacks, block);
 217
 218   block.start = 980;
 219   block.end = 990;
 220   vec_add1 (tc->rcv_opts.sacks, block);
 221
 222   tcp_rcv_sacks (tc, 950);
 223   TCP_TEST ((sb->high_sacked == 990), "max sacked byte %u", sb->high_sacked);
 224   TCP_TEST ((sb->sacked_bytes == 20), "sacked bytes %d", sb->sacked_bytes);
 225   TCP_TEST ((sb->last_sacked_bytes == 20),
 226             "last sacked bytes %d", sb->last_sacked_bytes);
 227   TCP_TEST ((sb->lost_bytes == 0), "lost bytes %u", sb->lost_bytes);
 228   TCP_TEST ((!sb->is_reneging), "is not reneging");
 229   TCP_TEST ((sb->rxt_sacked == 15), "last rxt sacked bytes %d",
 230             sb->rxt_sacked);
 231
 232   /*
 233    * Ack up to 960 (reneging) + [961 971]
 234    */
 235   tc->rcv_opts.sacks[0].start = 961;
 236   tc->rcv_opts.sacks[0].end = 971;
 237
 238   tcp_rcv_sacks (tc, 960);
 239
 240   TCP_TEST ((sb->is_reneging), "is reneging");
 241   TCP_TEST ((sb->sacked_bytes == 21), "sacked bytes %d", sb->sacked_bytes);
 242   TCP_TEST ((sb->last_sacked_bytes == 1),
 243             "last sacked bytes %d", sb->last_sacked_bytes);
 244   TCP_TEST ((sb->rxt_sacked == 11), "last rxt sacked bytes %d",
 245             sb->rxt_sacked);
 246   TCP_TEST ((sb->last_bytes_delivered == 0), "last bytes delivered %d",
 247             sb->last_bytes_delivered);
 248
 249   /*
 250    * Ack up to 960 (reneging) + [961 990]
 251    */
 252   tc->snd_una = 960;
 253   tc->rcv_opts.sacks[0].start = 961;
 254   tc->rcv_opts.sacks[0].end = 990;
 255
 256   tcp_rcv_sacks (tc, 960);
 257
 258   TCP_TEST ((sb->is_reneging), "is reneging");
 259   TCP_TEST ((sb->sacked_bytes == 30), "sacked bytes %d", sb->sacked_bytes);
 260   TCP_TEST ((sb->last_sacked_bytes == 9),
 261             "last sacked bytes %d", sb->last_sacked_bytes);
 262   TCP_TEST ((sb->rxt_sacked == 9), "last rxt sacked bytes %d",
 263             sb->rxt_sacked);
 264
 265   /*
 266    * Sack remaining bytes [990 1000]
 267    */
 268   tc->rcv_opts.sacks[0].start = 990;
 269   tc->rcv_opts.sacks[0].end = 1000;
 270
 271   tcp_rcv_sacks (tc, 960);
 272
 273   TCP_TEST ((sb->is_reneging), "is reneging");
 274   TCP_TEST ((sb->sacked_bytes == 40), "sacked bytes %d", sb->sacked_bytes);
 275   TCP_TEST ((sb->last_sacked_bytes == 10),
 276             "last sacked bytes %d", sb->last_sacked_bytes);
 277   TCP_TEST ((sb->rxt_sacked == 0), "last rxt sacked bytes %d",
 278             sb->rxt_sacked);
 279   TCP_TEST (pool_elts (sb->holes) == 0, "no holes left");
 280
 281   /*
 282    * Ack up to 970 no sack blocks
 283    */
 284   vec_reset_length (tc->rcv_opts.sacks);
 285   tc->rcv_opts.flags &= ~TCP_OPTS_FLAG_SACK;
 286   tcp_rcv_sacks (tc, 970);
 287
 288   TCP_TEST ((sb->is_reneging), "is reneging");
 289   TCP_TEST ((sb->sacked_bytes == 30), "sacked bytes %d", sb->sacked_bytes);
 290   TCP_TEST ((sb->last_sacked_bytes == 0),
 291             "last sacked bytes %d", sb->last_sacked_bytes);
 292   TCP_TEST ((sb->rxt_sacked == 0), "last rxt sacked bytes %d",
 293             sb->rxt_sacked);
 294
 295   /*
 296    * Ack all up to 1000
 297    */
 298   tc->snd_una = 970;
 299   tcp_rcv_sacks (tc, 1000);
 300   TCP_TEST ((sb->high_sacked == 1000), "max sacked byte %u", sb->high_sacked);
 301   TCP_TEST ((sb->sacked_bytes == 0), "sacked bytes %d", sb->sacked_bytes);
 302   TCP_TEST (sb->last_bytes_delivered == 30, "last bytes delivered %d",
 303             sb->last_bytes_delivered);
 304   TCP_TEST ((sb->last_sacked_bytes == 0),
 305             "last sacked bytes %d", sb->last_sacked_bytes);
 306   TCP_TEST ((sb->lost_bytes == 0), "lost bytes %u", sb->lost_bytes);
 307   TCP_TEST ((!sb->is_reneging), "is not reneging");
 308
 309   /*
 310    * Add new block
 311    */
 312   tc->flags = 0;
 313   tc->rcv_opts.flags |= TCP_OPTS_FLAG_SACK;
 314   vec_reset_length (tc->rcv_opts.sacks);
 315
 316   block.start = 1200;
 317   block.end = 1300;
 318   vec_add1 (tc->rcv_opts.sacks, block);
 319
 320   tc->snd_una_max = 1500;
 321   tc->snd_una = 1000;
 322   tc->snd_nxt = 1500;
 323   tcp_rcv_sacks (tc, 1000);
 324
 325   if (verbose)
 326     vlib_cli_output (vm, "\nadd [1200, 1300] snd_una_max 1500, snd_una 1000:"
 327                      " \n%U", format_tcp_scoreboard, sb, tc);
 328
 329   TCP_TEST ((!sb->is_reneging), "is not reneging");
 330   TCP_TEST ((pool_elts (sb->holes) == 2),
 331             "scoreboard has %d holes", pool_elts (sb->holes));
 332   hole = scoreboard_first_hole (sb);
 333   TCP_TEST ((hole->start == 1000 && hole->end == 1200),
 334             "first hole start %u end %u", hole->start, hole->end);
 335   TCP_TEST ((sb->high_sacked == 1300), "max sacked byte %u", sb->high_sacked);
 336   hole = scoreboard_last_hole (sb);
 337   TCP_TEST ((hole->start == 1300 && hole->end == 1500),
 338             "last hole start %u end %u", hole->start, hole->end);
 339   TCP_TEST ((sb->sacked_bytes == 100), "sacked bytes %d", sb->sacked_bytes);
 340   TCP_TEST ((sb->lost_bytes == 0), "lost bytes %u", sb->lost_bytes);
 341
 342   /*
 343    * Ack first hole
 344    */
 345
 346   vec_reset_length (tc->rcv_opts.sacks);
 347   /* Ack up to 1300 to avoid reneging */
 348   tcp_rcv_sacks (tc, 1300);
 349
 350   if (verbose)
 351     vlib_cli_output (vm, "\nsb ack up to byte 1300:\n%U",
 352                      format_tcp_scoreboard, sb, tc);
 353
 354   TCP_TEST ((sb->sacked_bytes == 0), "sacked bytes %d", sb->sacked_bytes);
 355   TCP_TEST ((pool_elts (sb->holes) == 1),
 356             "scoreboard has %d elements", pool_elts (sb->holes));
 357   TCP_TEST ((sb->last_bytes_delivered == 100), "last bytes delivered %d",
 358             sb->last_bytes_delivered);
 359   TCP_TEST ((sb->lost_bytes == 0), "lost bytes %u", sb->lost_bytes);
 360   TCP_TEST ((sb->head != TCP_INVALID_SACK_HOLE_INDEX), "head %u", sb->head);
 361   TCP_TEST ((sb->tail != TCP_INVALID_SACK_HOLE_INDEX), "tail %u", sb->tail);
 362   TCP_TEST ((!sb->is_reneging), "is not reneging");
 363
 364   /*
 365    * Add some more blocks and then remove all
 366    */
 367   vec_reset_length (tc->rcv_opts.sacks);
 368   tc->snd_una = 1300;
 369   tc->snd_nxt = tc->snd_una_max = 1900;
 370   for (i = 0; i < 5; i++)
 371     {
 372       block.start = i * 100 + 1200;
 373       block.end = (i + 1) * 100 + 1200;
 374       vec_add1 (tc->rcv_opts.sacks, block);
 375     }
 376   tcp_rcv_sacks (tc, 1900);
 377
 378   scoreboard_clear (sb);
 379   if (verbose)
 380     vlib_cli_output (vm, "\nsb cleared all:\n%U", format_tcp_scoreboard, sb,
 381                      tc);
 382
 383   TCP_TEST ((pool_elts (sb->holes) == 0),
 384             "number of holes %d", pool_elts (sb->holes));
 385   TCP_TEST ((sb->head == TCP_INVALID_SACK_HOLE_INDEX), "head %u", sb->head);
 386   TCP_TEST ((sb->tail == TCP_INVALID_SACK_HOLE_INDEX), "tail %u", sb->tail);
 387
 388   /*
 389    * Re-inject odd blocks and ack them all
 390    */
 391
 392   tc->snd_una = 0;
 393   tc->snd_una_max = 1000;
 394   tc->snd_nxt = 1000;
 395   vec_reset_length (tc->rcv_opts.sacks);
 396   for (i = 0; i < 5; i++)
 397     {
 398       vec_add1 (tc->rcv_opts.sacks, sacks[i * 2 + 1]);
 399     }
 400   tc->rcv_opts.n_sack_blocks = vec_len (tc->rcv_opts.sacks);
 401   tcp_rcv_sacks (tc, 0);
 402   if (verbose)
 403     vlib_cli_output (vm, "\nsb added odd blocks snd_una 0 snd_una_max 1000:"
 404                      "\n%U", format_tcp_scoreboard, sb, tc);
 405   TCP_TEST ((pool_elts (sb->holes) == 5),
 406             "scoreboard has %d elements", pool_elts (sb->holes));
 407   TCP_TEST ((sb->lost_bytes == 300), "lost bytes %u", sb->lost_bytes);
 408   hole = scoreboard_last_hole (sb);
 409   TCP_TEST ((hole->end == 900), "last hole end %u", hole->end);
 410   TCP_TEST ((sb->high_sacked == 1000), "high sacked %u", sb->high_sacked);
 411
 412   /*
 413    * Renege bytes from 950 to 1000
 414    */
 415   tcp_rcv_sacks (tc, 950);
 416
 417   if (verbose)
 418     vlib_cli_output (vm, "\nack [0, 950]:\n%U", format_tcp_scoreboard, sb,
 419                      tc);
 420
 421   TCP_TEST ((pool_elts (sb->holes) == 0), "scoreboard has %d elements",
 422             pool_elts (sb->holes));
 423   TCP_TEST ((sb->is_reneging), "is reneging");
 424   TCP_TEST ((sb->sacked_bytes == 50), "sacked bytes %d", sb->sacked_bytes);
 425   TCP_TEST ((sb->last_sacked_bytes == 0), "last sacked bytes %d",
 426             sb->last_sacked_bytes);
 427   TCP_TEST ((sb->lost_bytes == 0), "lost bytes %u", sb->lost_bytes);
 428   TCP_TEST ((sb->high_sacked == 1000), "high sacked %u", sb->high_sacked);
 429
 430   scoreboard_clear (sb);
 431
 432   /*
 433    * Inject one block, ack it and overlap hole
 434    */
 435
 436   tc->snd_una = 0;
 437   tc->snd_una_max = 1000;
 438   tc->snd_nxt = 1000;
 439
 440   block.start = 100;
 441   block.end = 500;
 442   vec_add1 (tc->rcv_opts.sacks, block);
 443   tc->rcv_opts.n_sack_blocks = vec_len (tc->rcv_opts.sacks);
 444
 445   tcp_rcv_sacks (tc, 0);
 446
 447   if (verbose)
 448     vlib_cli_output (vm, "\nsb added [100, 500] snd_una 0 snd_una_max 1000:"
 449                      "\n%U", format_tcp_scoreboard, sb, tc);
 450
 451   tcp_rcv_sacks (tc, 800);
 452
 453   if (verbose)
 454     vlib_cli_output (vm, "\nsb ack [0, 800]:\n%U", format_tcp_scoreboard, sb,
 455                      tc);
 456
 457   TCP_TEST ((pool_elts (sb->holes) == 1),
 458             "scoreboard has %d elements", pool_elts (sb->holes));
 459   TCP_TEST ((!sb->is_reneging), "is not reneging");
 460   TCP_TEST ((sb->sacked_bytes == 0), "sacked bytes %d", sb->sacked_bytes);
 461   TCP_TEST ((sb->last_sacked_bytes == 0), "last sacked bytes %d",
 462             sb->last_sacked_bytes);
 463   TCP_TEST ((sb->last_bytes_delivered == 400),
 464             "last bytes delivered %d", sb->last_bytes_delivered);
 465   TCP_TEST ((sb->lost_bytes == 0), "lost bytes %u", sb->lost_bytes);
 466   TCP_TEST ((sb->head != TCP_INVALID_SACK_HOLE_INDEX), "head %u", sb->head);
 467   TCP_TEST ((sb->tail != TCP_INVALID_SACK_HOLE_INDEX), "tail %u", sb->tail);
 468
 469   /*
 470    * One hole close to head, patch head, split in two and start acking
 471    * the lowest part
 472    */
 473   scoreboard_clear (sb);
 474   tc->snd_una = 0;
 475   tc->snd_una_max = 1000;
 476   tc->snd_nxt = 1000;
 477
 478   block.start = 500;
 479   block.end = 1000;
 480   vec_add1 (tc->rcv_opts.sacks, block);
 481   tc->rcv_opts.n_sack_blocks = vec_len (tc->rcv_opts.sacks);
 482
 483   tcp_rcv_sacks (tc, 0);
 484   if (verbose)
 485     vlib_cli_output (vm, "\nsb added [500, 1000]:\n%U",
 486                      format_tcp_scoreboard, sb, tc);
 487   TCP_TEST ((sb->sacked_bytes == 500), "sacked bytes %d", sb->sacked_bytes);
 488   TCP_TEST ((sb->last_sacked_bytes == 500), "last sacked bytes %d",
 489             sb->last_sacked_bytes);
 490   TCP_TEST ((sb->lost_bytes == 500), "lost bytes %u", sb->lost_bytes);
 491
 492   vec_reset_length (tc->rcv_opts.sacks);
 493   block.start = 300;
 494   block.end = 400;
 495   vec_add1 (tc->rcv_opts.sacks, block);
 496   tc->rcv_opts.n_sack_blocks = vec_len (tc->rcv_opts.sacks);
 497   tcp_rcv_sacks (tc, 100);
 498   if (verbose)
 499     vlib_cli_output (vm, "\nsb added [0, 100] [300, 400]:\n%U",
 500                      format_tcp_scoreboard, sb, tc);
 501   TCP_TEST ((pool_elts (sb->holes) == 2),
 502             "scoreboard has %d elements", pool_elts (sb->holes));
 503   TCP_TEST ((sb->sacked_bytes == 600), "sacked bytes %d", sb->sacked_bytes);
 504   TCP_TEST ((sb->last_sacked_bytes == 100), "last sacked bytes %d",
 505             sb->last_sacked_bytes);
 506   TCP_TEST ((sb->last_bytes_delivered == 0), "last bytes delivered %d",
 507             sb->last_bytes_delivered);
 508   TCP_TEST ((sb->lost_bytes == 300), "lost bytes %u", sb->lost_bytes);
 509
 510   /*
 511    * Ack [100 300] in two steps
 512    *
 513    * Step 1. Ack [100 200] which delivers 100 of the bytes lost
 514    */
 515   tc->snd_una = 100;
 516   tcp_rcv_sacks (tc, 200);
 517   TCP_TEST ((sb->sacked_bytes == 600), "sacked bytes %d", sb->sacked_bytes);
 518   TCP_TEST ((sb->last_bytes_delivered == 0), "last bytes delivered %d",
 519             sb->last_bytes_delivered);
 520   TCP_TEST ((sb->lost_bytes == 200), "lost bytes %u", sb->lost_bytes);
 521
 522   /*
 523    * Step 2. Ack up to 300, although 300 400 is sacked, so this is interpreted
 524    * as reneging.
 525    */
 526   tc->snd_una = 200;
 527   tcp_rcv_sacks (tc, 300);
 528   if (verbose)
 529     vlib_cli_output (vm, "\nacked [100, 300] in two steps:\n%U",
 530                      format_tcp_scoreboard, sb, tc);
 531   TCP_TEST ((sb->sacked_bytes == 600), "sacked bytes %d", sb->sacked_bytes);
 532   TCP_TEST ((sb->lost_bytes == 100), "lost bytes %u", sb->lost_bytes);
 533   TCP_TEST ((sb->last_bytes_delivered == 0), "last bytes delivered %d",
 534             sb->last_bytes_delivered);
 535   TCP_TEST ((sb->is_reneging), "is reneging");
 536
 537   /*
 538    * Ack [300 500]. Delivers reneged segment [300 400] and reneges bytes
 539    * above 500
 540    */
 541   tc->snd_una = 300;
 542   tcp_rcv_sacks (tc, 500);
 543   if (verbose)
 544     vlib_cli_output (vm, "\nacked [400, 500]:\n%U", format_tcp_scoreboard, sb,
 545                      tc);
 546   TCP_TEST ((pool_elts (sb->holes) == 0),
 547             "scoreboard has %d elements", pool_elts (sb->holes));
 548   TCP_TEST ((sb->sacked_bytes == 500), "sacked bytes %d", sb->sacked_bytes);
 549   TCP_TEST ((sb->last_sacked_bytes == 0), "last sacked bytes %d",
 550             sb->last_sacked_bytes);
 551   TCP_TEST ((sb->last_bytes_delivered == 100), "last bytes delivered %d",
 552             sb->last_bytes_delivered);
 553   TCP_TEST ((sb->is_reneging), "is reneging");
 554   TCP_TEST ((sb->head == TCP_INVALID_SACK_HOLE_INDEX), "head %u", sb->head);
 555   TCP_TEST ((sb->tail == TCP_INVALID_SACK_HOLE_INDEX), "tail %u", sb->tail);
 556
 557   /*
 558    * Ack up to 1000 to deliver all bytes
 559    */
 560   tc->snd_una = 500;
 561   tcp_rcv_sacks (tc, 1000);
 562   if (verbose)
 563     vlib_cli_output (vm, "\nAck high sacked:\n%U", format_tcp_scoreboard, sb,
 564                      tc);
 565   TCP_TEST ((sb->last_sacked_bytes == 0), "last sacked bytes %d",
 566             sb->last_sacked_bytes);
 567   TCP_TEST ((sb->last_bytes_delivered == 500), "last bytes delivered %d",
 568             sb->last_bytes_delivered);
 569   TCP_TEST ((!sb->is_reneging), "is not reneging");
 570
 571   /*
 572    * Add [1200, 1500] and test that [1000, 1200] is lost (bytes condition)
 573    * snd_una = 1000 and snd_una_max = 1600
 574    */
 575   tc->snd_una = 1000;
 576   tc->snd_nxt = tc->snd_una_max = 1600;
 577   vec_reset_length (tc->rcv_opts.sacks);
 578   block.start = 1200;
 579   block.end = 1500;
 580   vec_add1 (tc->rcv_opts.sacks, block);
 581   tc->rcv_opts.n_sack_blocks = vec_len (tc->rcv_opts.sacks);
 582   tcp_rcv_sacks (tc, 1000);
 583   if (verbose)
 584     vlib_cli_output (vm, "\nacked [1200, 1500] test first hole is lost:\n%U",
 585                      format_tcp_scoreboard, sb, tc);
 586   TCP_TEST ((pool_elts (sb->holes) == 2), "scoreboard has %d elements",
 587             pool_elts (sb->holes));
 588   TCP_TEST ((sb->sacked_bytes == 300), "sacked bytes %d", sb->sacked_bytes);
 589   TCP_TEST ((sb->last_sacked_bytes == 300), "last sacked bytes %d",
 590             sb->last_sacked_bytes);
 591   TCP_TEST ((sb->last_bytes_delivered == 0), "last bytes delivered %d",
 592             sb->last_bytes_delivered);
 593   TCP_TEST ((sb->lost_bytes == 200), "lost bytes %u", sb->lost_bytes);
 594   TCP_TEST ((!sb->is_reneging), "is not reneging");
 595
 596   /*
 597    * Restart
 598    */
 599   scoreboard_clear (sb);
 600   vec_reset_length (tc->rcv_opts.sacks);
 601
 602   /*
 603    * Inject [100 500]
 604    */
 605
 606   tc->flags |= TCP_CONN_FAST_RECOVERY | TCP_CONN_RECOVERY;
 607   tc->snd_una = 0;
 608   tc->snd_una_max = 1000;
 609   tc->snd_nxt = 1000;
 610   sb->high_rxt = 0;
 611
 612   block.start = 100;
 613   block.end = 500;
 614   vec_add1 (tc->rcv_opts.sacks, block);
 615   tc->rcv_opts.n_sack_blocks = vec_len (tc->rcv_opts.sacks);
 616
 617   tcp_rcv_sacks (tc, 0);
 618
 619   TCP_TEST ((sb->sacked_bytes == 400), "sacked bytes %d", sb->sacked_bytes);
 620   TCP_TEST ((sb->last_sacked_bytes == 400), "last sacked bytes %d",
 621             sb->last_sacked_bytes);
 622   TCP_TEST ((!sb->is_reneging), "is not reneging");
 623
 624   /*
 625    * Renege, sack all of the remaining bytes and cover some rxt bytes
 626    */
 627   sb->high_rxt = 700;
 628   tc->rcv_opts.sacks[0].start = 500;
 629   tc->rcv_opts.sacks[0].end = 1000;
 630
 631   tcp_rcv_sacks (tc, 100);
 632
 633   TCP_TEST ((sb->sacked_bytes == 900), "sacked bytes %d", sb->sacked_bytes);
 634   TCP_TEST ((sb->last_sacked_bytes == 500), "last sacked bytes %d",
 635             sb->last_sacked_bytes);
 636   TCP_TEST (sb->is_reneging, "is reneging");
 637   TCP_TEST ((sb->rxt_sacked == 300), "last rxt sacked bytes %d",
 638             sb->rxt_sacked);
 639
 640   /*
 641    * Restart
 642    */
 643   scoreboard_clear (sb);
 644   vec_reset_length (tc->rcv_opts.sacks);
 645
 646   /*
 647    * Broken sacks:
 648    * block.start > snd_nxt
 649    * && block.start < blk.end
 650    * && block.end <= snd_nxt
 651    */
 652   tc->flags = 0;
 653   block.start = 2147483647;
 654   block.end = 4294967295;
 655   vec_add1 (tc->rcv_opts.sacks, block);
 656   tc->snd_una = tc->snd_nxt = 1969067947;
 657
 658   tcp_rcv_sacks (tc, tc->snd_una);
 659
 660   /*
 661    * Clear
 662    */
 663   scoreboard_clear (sb);
 664   vec_reset_length (tc->rcv_opts.sacks);
 665
 666   return 0;
 667 }
 668
 669 static int
 670 tcp_test_sack_tx (vlib_main_t * vm, unformat_input_t * input)
 671 {
 672   tcp_connection_t _tc, *tc = &_tc;
 673   sack_block_t *sacks;
 674   int i, verbose = 0, expected;
 675
 676   while (unformat_check_input (input) != UNFORMAT_END_OF_INPUT)
 677     {
 678       if (unformat (input, "verbose"))
 679         verbose = 1;
 680       else
 681         {
 682           vlib_cli_output (vm, "parse error: '%U'", format_unformat_error,
 683                            input);
 684           return -1;
 685         }
 686     }
 687
 688   clib_memset (tc, 0, sizeof (*tc));
 689
 690   /*
 691    * Add odd sack block pairs
 692    */
 693   for (i = 1; i < 10; i += 2)
 694     {
 695       tcp_update_sack_list (tc, i * 100, (i + 1) * 100);
 696     }
 697
 698   TCP_TEST ((vec_len (tc->snd_sacks) == 5), "sack blocks %d expected %d",
 699             vec_len (tc->snd_sacks), 5);
 700   TCP_TEST ((tc->snd_sacks[0].start = 900),
 701             "first sack block start %u expected %u", tc->snd_sacks[0].start,
 702             900);
 703
 704   /*
 705    * Try to add one extra
 706    */
 707   sacks = vec_dup (tc->snd_sacks);
 708
 709   tcp_update_sack_list (tc, 1100, 1200);
 710   if (verbose)
 711     vlib_cli_output (vm, "add new segment [1100, 1200]\n%U",
 712                      format_tcp_sacks, tc);
 713   expected = 5 < TCP_MAX_SACK_BLOCKS ? 6 : 5;
 714   TCP_TEST ((vec_len (tc->snd_sacks) == expected),
 715             "sack blocks %d expected %d", vec_len (tc->snd_sacks), expected);
 716   TCP_TEST ((tc->snd_sacks[0].start == 1100),
 717             "first sack block start %u expected %u", tc->snd_sacks[0].start,
 718             1100);
 719
 720   /* restore */
 721   vec_free (tc->snd_sacks);
 722   tc->snd_sacks = sacks;
 723
 724   /*
 725    * Overlap first 2 segment
 726    */
 727   tc->rcv_nxt = 300;
 728   tcp_update_sack_list (tc, 300, 300);
 729   if (verbose)
 730     vlib_cli_output (vm, "overlap first 2 segments:\n%U",
 731                      format_tcp_sacks, tc);
 732   TCP_TEST ((vec_len (tc->snd_sacks) == 3), "sack blocks %d expected %d",
 733             vec_len (tc->snd_sacks), 3);
 734   TCP_TEST ((tc->snd_sacks[0].start == 900),
 735             "first sack block start %u expected %u", tc->snd_sacks[0].start,
 736             500);
 737
 738   /*
 739    * Add a new segment
 740    */
 741   tcp_update_sack_list (tc, 1100, 1200);
 742   if (verbose)
 743     vlib_cli_output (vm, "add new segment [1100, 1200]\n%U",
 744                      format_tcp_sacks, tc);
 745   TCP_TEST ((vec_len (tc->snd_sacks) == 4), "sack blocks %d expected %d",
 746             vec_len (tc->snd_sacks), 4);
 747   TCP_TEST ((tc->snd_sacks[0].start == 1100),
 748             "first sack block start %u expected %u", tc->snd_sacks[0].start,
 749             1100);
 750
 751   /*
 752    * Join middle segments
 753    */
 754   tcp_update_sack_list (tc, 800, 900);
 755   if (verbose)
 756     vlib_cli_output (vm, "join middle segments [800, 900]\n%U",
 757                      format_tcp_sacks, tc);
 758
 759   TCP_TEST ((vec_len (tc->snd_sacks) == 3), "sack blocks %d expected %d",
 760             vec_len (tc->snd_sacks), 3);
 761   TCP_TEST ((tc->snd_sacks[0].start == 700),
 762             "first sack block start %u expected %u", tc->snd_sacks[0].start,
 763             1100);
 764
 765   /*
 766    * Advance rcv_nxt to overlap all
 767    */
 768   tc->rcv_nxt = 1200;
 769   tcp_update_sack_list (tc, 1200, 1200);
 770   if (verbose)
 771     vlib_cli_output (vm, "advance rcv_nxt to 1200\n%U", format_tcp_sacks, tc);
 772   TCP_TEST ((vec_len (tc->snd_sacks) == 0), "sack blocks %d expected %d",
 773             vec_len (tc->snd_sacks), 0);
 774
 775
 776   /*
 777    * Add 2 blocks, overwrite first and update rcv_nxt to also remove it
 778    */
 779
 780   vec_reset_length (tc->snd_sacks);
 781   tc->rcv_nxt = 0;
 782
 783   tcp_update_sack_list (tc, 100, 200);
 784   tcp_update_sack_list (tc, 300, 400);
 785
 786   if (verbose)
 787     vlib_cli_output (vm, "add [100, 200] [300, 400]\n%U",
 788                      format_tcp_sacks, tc);
 789   TCP_TEST ((vec_len (tc->snd_sacks) == 2),
 790             "sack blocks %d expected %d", vec_len (tc->snd_sacks), 2);
 791   TCP_TEST ((tc->snd_sacks[0].start == 300),
 792             "first sack block start %u expected %u", tc->snd_sacks[0].start,
 793             300);
 794
 795   tc->rcv_nxt = 100;
 796   tcp_update_sack_list (tc, 100, 100);
 797   if (verbose)
 798     vlib_cli_output (vm, "add [100, 200] rcv_nxt = 100\n%U",
 799                      format_tcp_sacks, tc);
 800   TCP_TEST ((vec_len (tc->snd_sacks) == 1),
 801             "sack blocks %d expected %d", vec_len (tc->snd_sacks), 1);
 802   TCP_TEST ((tc->snd_sacks[0].start == 300),
 803             "first sack block start %u expected %u", tc->snd_sacks[0].start,
 804             300);
 805   return 0;
 806 }
 807
 808 static int
 809 tcp_test_sack (vlib_main_t * vm, unformat_input_t * input)
 810 {
 811   int res = 0;
 812
 813   /* Run all tests */
 814   if (unformat_check_input (input) == UNFORMAT_END_OF_INPUT)
 815     {
 816       if (tcp_test_sack_tx (vm, input))
 817         {
 818           return -1;
 819         }
 820
 821       if (tcp_test_sack_rx (vm, input))
 822         {
 823           return -1;
 824         }
 825     }
 826   else
 827     {
 828       if (unformat (input, "tx"))
 829         {
 830           res = tcp_test_sack_tx (vm, input);
 831         }
 832       else if (unformat (input, "rx"))
 833         {
 834           res = tcp_test_sack_rx (vm, input);
 835         }
 836     }
 837
 838   return res;
 839 }
 840
 841 static int
 842 tcp_test_lookup (vlib_main_t * vm, unformat_input_t * input)
 843 {
 844   session_main_t *smm = &session_main;
 845   transport_connection_t _tc1, *tc1 = &_tc1, _tc2, *tc2 = &_tc2, *tconn;
 846   tcp_connection_t *tc;
 847   session_t *s, *s1;
 848   u8 cmp = 0, is_filtered = 0;
 849   u32 sidx;
 850
 851   /*
 852    * Allocate fake session and connection 1
 853    */
 854   pool_get (smm->wrk[0].sessions, s);
 855   clib_memset (s, 0, sizeof (*s));
 856   s->session_index = sidx = s - smm->wrk[0].sessions;
 857
 858   tc = tcp_connection_alloc (0);
 859   tc->connection.s_index = s->session_index;
 860   s->connection_index = tc->connection.c_index;
 861
 862   tc->connection.lcl_ip.ip4.as_u32 = clib_host_to_net_u32 (0x06000101);
 863   tc->connection.rmt_ip.ip4.as_u32 = clib_host_to_net_u32 (0x06000103);
 864   tc->connection.lcl_port = 35051;
 865   tc->connection.rmt_port = 53764;
 866   tc->connection.proto = TRANSPORT_PROTO_TCP;
 867   tc->connection.is_ip4 = 1;
 868   clib_memcpy_fast (tc1, &tc->connection, sizeof (*tc1));
 869
 870   /*
 871    * Allocate fake session and connection 2
 872    */
 873   pool_get (smm->wrk[0].sessions, s);
 874   clib_memset (s, 0, sizeof (*s));
 875   s->session_index = s - smm->wrk[0].sessions;
 876
 877   tc = tcp_connection_alloc (0);
 878   tc->connection.s_index = s->session_index;
 879   s->connection_index = tc->connection.c_index;
 880
 881   tc->connection.lcl_ip.ip4.as_u32 = clib_host_to_net_u32 (0x06000101);
 882   tc->connection.rmt_ip.ip4.as_u32 = clib_host_to_net_u32 (0x06000102);
 883   tc->connection.lcl_port = 38225;
 884   tc->connection.rmt_port = 53764;
 885   tc->connection.proto = TRANSPORT_PROTO_TCP;
 886   tc->connection.is_ip4 = 1;
 887   clib_memcpy_fast (tc2, &tc->connection, sizeof (*tc2));
 888
 889   /*
 890    * Confirm that connection lookup works
 891    */
 892
 893   s1 = pool_elt_at_index (smm->wrk[0].sessions, sidx);
 894   session_lookup_add_connection (tc1, session_handle (s1));
 895   tconn = session_lookup_connection_wt4 (0, &tc1->lcl_ip.ip4,
 896                                          &tc1->rmt_ip.ip4,
 897                                          tc1->lcl_port, tc1->rmt_port,
 898                                          tc1->proto, 0, &is_filtered);
 899
 900   TCP_TEST ((tconn != 0), "connection exists");
 901   cmp = (memcmp (&tconn->rmt_ip, &tc1->rmt_ip, sizeof (tc1->rmt_ip)) == 0);
 902   TCP_TEST ((cmp), "rmt ip is identical %d", cmp);
 903   TCP_TEST ((tconn->lcl_port == tc1->lcl_port),
 904             "rmt port is identical %d", tconn->lcl_port == tc1->lcl_port);
 905
 906   /*
 907    * Non-existing connection lookup should not work
 908    */
 909
 910   tconn = session_lookup_connection_wt4 (0, &tc2->lcl_ip.ip4,
 911                                          &tc2->rmt_ip.ip4,
 912                                          tc2->lcl_port, tc2->rmt_port,
 913                                          tc2->proto, 0, &is_filtered);
 914   TCP_TEST ((tconn == 0), "lookup result should be null");
 915
 916   /*
 917    * Delete and lookup again
 918    */
 919   session_lookup_del_connection (tc1);
 920   tconn = session_lookup_connection_wt4 (0, &tc1->lcl_ip.ip4,
 921                                          &tc1->rmt_ip.ip4,
 922                                          tc1->lcl_port, tc1->rmt_port,
 923                                          tc1->proto, 0, &is_filtered);
 924   TCP_TEST ((tconn == 0), "lookup result should be null");
 925   tconn = session_lookup_connection_wt4 (0, &tc2->lcl_ip.ip4,
 926                                          &tc2->rmt_ip.ip4,
 927                                          tc2->lcl_port, tc2->rmt_port,
 928                                          tc2->proto, 0, &is_filtered);
 929   TCP_TEST ((tconn == 0), "lookup result should be null");
 930
 931   /*
 932    * Re-add and lookup tc2
 933    */
 934   session_lookup_add_connection (tc1, tc1->s_index);
 935   tconn = session_lookup_connection_wt4 (0, &tc2->lcl_ip.ip4,
 936                                          &tc2->rmt_ip.ip4,
 937                                          tc2->lcl_port, tc2->rmt_port,
 938                                          tc2->proto, 0, &is_filtered);
 939   TCP_TEST ((tconn == 0), "lookup result should be null");
 940
 941   return 0;
 942 }
 943
 944 static int
 945 tcp_test_session (vlib_main_t * vm, unformat_input_t * input)
 946 {
 947   int rv = 0;
 948   tcp_connection_t *tc0;
 949   ip4_address_t local, remote;
 950   u16 local_port, remote_port;
 951   int is_add = 1;
 952
 953
 954   while (unformat_check_input (input) != UNFORMAT_END_OF_INPUT)
 955     {
 956       if (unformat (input, "del"))
 957         is_add = 0;
 958       else if (unformat (input, "add"))
 959         is_add = 1;
 960       else
 961         break;
 962     }
 963
 964   if (is_add)
 965     {
 966       local.as_u32 = clib_host_to_net_u32 (0x06000101);
 967       remote.as_u32 = clib_host_to_net_u32 (0x06000102);
 968       local_port = clib_host_to_net_u16 (1234);
 969       remote_port = clib_host_to_net_u16 (11234);
 970
 971       tc0 = tcp_connection_alloc (0);
 972
 973       tc0->state = TCP_STATE_ESTABLISHED;
 974       tc0->rcv_las = 1;
 975       tc0->c_lcl_port = local_port;
 976       tc0->c_rmt_port = remote_port;
 977       tc0->c_is_ip4 = 1;
 978       tc0->c_thread_index = 0;
 979       tc0->c_lcl_ip4.as_u32 = local.as_u32;
 980       tc0->c_rmt_ip4.as_u32 = remote.as_u32;
 981       tc0->rcv_opts.mss = 1450;
 982       tcp_connection_init_vars (tc0);
 983
 984       TCP_EVT (TCP_EVT_OPEN, tc0);
 985
 986       if (session_stream_accept (&tc0->connection, 0 /* listener index */ ,
 987                                  0 /* thread index */ , 0 /* notify */ ))
 988         clib_warning ("stream_session_accept failed");
 989
 990       session_stream_accept_notify (&tc0->connection);
 991     }
 992   else
 993     {
 994       tc0 = tcp_connection_get (0 /* connection index */ , 0 /* thread */ );
 995       tc0->state = TCP_STATE_CLOSED;
 996       session_transport_closing_notify (&tc0->connection);
 997     }
 998
 999   return rv;
1000 }
1001
1002 static inline int
1003 tbt_seq_lt (u32 a, u32 b)
1004 {
1005   return seq_lt (a, b);
1006 }
1007
1008 static int
1009 tcp_test_delivery (vlib_main_t * vm, unformat_input_t * input)
1010 {
1011   u32 thread_index = 0, snd_una, *min_seqs = 0;
1012   tcp_rate_sample_t _rs = { 0 }, *rs = &_rs;
1013   tcp_connection_t _tc, *tc = &_tc;
1014   sack_scoreboard_t *sb = &tc->sack_sb;
1015   int __clib_unused verbose = 0, i;
1016   u64 rate = 1000, burst = 100;
1017   sack_block_t *sacks = 0;
1018   tcp_byte_tracker_t *bt;
1019   rb_node_t *root, *rbn;
1020   tcp_bt_sample_t *bts;
1021
1022   while (unformat_check_input (input) != UNFORMAT_END_OF_INPUT)
1023     {
1024       if (unformat (input, "verbose"))
1025         verbose = 1;
1026       else
1027         {
1028           vlib_cli_output (vm, "parse error: '%U'", format_unformat_error,
1029                            input);
1030           return -1;
1031         }
1032     }
1033
1034   /* Init data structures */
1035   memset (tc, 0, sizeof (*tc));
1036   session_main.wrk[thread_index].last_vlib_time = 1;
1037   transport_connection_tx_pacer_update (&tc->connection, rate, 1e6);
1038
1039   tcp_bt_init (tc);
1040   bt = tc->bt;
1041
1042   /*
1043    * Track simple bursts without rxt
1044    */
1045
1046   /* 1) track first burst a time 1 */
1047   tcp_bt_track_tx (tc, burst);
1048
1049   TCP_TEST (tcp_bt_is_sane (bt), "tracker should be sane");
1050   TCP_TEST (pool_elts (bt->samples) == 1, "should have 1 sample");
1051   bts = pool_elt_at_index (bt->samples, bt->head);
1052   TCP_TEST (bts->min_seq == tc->snd_una, "min seq should be snd_una");
1053   TCP_TEST (bts->next == TCP_BTS_INVALID_INDEX, "next should be invalid");
1054   TCP_TEST (bts->prev == TCP_BTS_INVALID_INDEX, "prev should be invalid");
1055   TCP_TEST (bts->delivered_time == 1, "delivered time should be 1");
1056   TCP_TEST (bts->delivered == 0, "delivered should be 0");
1057   TCP_TEST (!(bts->flags & TCP_BTS_IS_RXT), "not retransmitted");
1058   TCP_TEST (!(bts->flags & TCP_BTS_IS_APP_LIMITED), "not app limited");
1059
1060   /* 2) check delivery rate at time 2 */
1061   session_main.wrk[thread_index].last_vlib_time = 2;
1062   tc->snd_una = tc->snd_nxt = burst;
1063   tc->bytes_acked = burst;
1064
1065   tcp_bt_sample_delivery_rate (tc, rs);
1066
1067   TCP_TEST (tcp_bt_is_sane (bt), "tracker should be sane");
1068   TCP_TEST (pool_elts (bt->samples) == 0, "sample should've been consumed");
1069   TCP_TEST (tc->delivered_time == 2, "delivered time should be 2");
1070   TCP_TEST (tc->delivered == burst, "delivered should be 100");
1071   TCP_TEST (rs->interval_time == 1, "ack time should be 1");
1072   TCP_TEST (rs->delivered == burst, "delivered should be 100");
1073   TCP_TEST (rs->prior_delivered == 0, "sample delivered should be 0");
1074   TCP_TEST (!(rs->flags & TCP_BTS_IS_RXT), "not retransmitted");
1075   TCP_TEST (tc->first_tx_time == 1, "first_tx_time %u", tc->first_tx_time);
1076
1077   /* 3) track second burst at time 2 */
1078   tcp_bt_track_tx (tc, burst);
1079   tc->snd_nxt += burst;
1080
1081   /* 4) track second burst at time 3 */
1082   session_main.wrk[thread_index].last_vlib_time = 3;
1083   tcp_bt_track_tx (tc, burst);
1084   tc->snd_nxt += burst;
1085
1086   TCP_TEST (pool_elts (bt->samples) == 2, "should have 2 samples");
1087
1088   TCP_TEST (tcp_bt_is_sane (bt), "tracker should be sane");
1089   bts = pool_elt_at_index (bt->samples, bt->head);
1090   TCP_TEST (bts->min_seq == tc->snd_una, "min seq should be snd_una");
1091   TCP_TEST (bts->next == bt->tail, "next should tail");
1092
1093   bts = pool_elt_at_index (bt->samples, bt->tail);
1094   TCP_TEST (bts->min_seq == tc->snd_nxt - burst,
1095             "min seq should be snd_nxt prior to burst");
1096   TCP_TEST (bts->prev == bt->head, "prev should be head");
1097
1098   /* 5) check delivery rate at time 4 */
1099   session_main.wrk[thread_index].last_vlib_time = 4;
1100   tc->snd_una = tc->snd_nxt;
1101   tc->bytes_acked = 2 * burst;
1102
1103   tcp_bt_sample_delivery_rate (tc, rs);
1104
1105   TCP_TEST (tcp_bt_is_sane (bt), "tracker should be sane");
1106   TCP_TEST (pool_elts (bt->samples) == 0, "sample should've been consumed");
1107   TCP_TEST (tc->delivered_time == 4, "delivered time should be 4");
1108   TCP_TEST (tc->delivered == 3 * burst, "delivered should be 300 is %u",
1109             tc->delivered);
1110   TCP_TEST (rs->interval_time == 2, "ack time should be 2");
1111   TCP_TEST (rs->delivered == 2 * burst, "delivered should be 200");
1112   TCP_TEST (rs->prior_delivered == burst, "delivered should be 100");
1113   TCP_TEST (!(rs->flags & TCP_BTS_IS_RXT), "not retransmitted");
1114   TCP_TEST (tc->first_tx_time == 2, "first_tx_time %u", tc->first_tx_time);
1115
1116   /*
1117    * Track retransmissions
1118    *
1119    * snd_una should be 300 at this point
1120    */
1121
1122   snd_una = tc->snd_una;
1123
1124   /* 1) track first burst at time 4 */
1125   tcp_bt_track_tx (tc, burst);
1126   tc->snd_nxt += burst;
1127
1128   /* 2) track second burst at time 5 */
1129   session_main.wrk[thread_index].last_vlib_time = 5;
1130   tcp_bt_track_tx (tc, burst);
1131   tc->snd_nxt += burst;
1132
1133   /* 3) track third burst at time 6 */
1134   session_main.wrk[thread_index].last_vlib_time = 6;
1135   tcp_bt_track_tx (tc, burst);
1136   tc->snd_nxt += burst;
1137
1138   /* 4) track fourth burst at time 7 */
1139   session_main.wrk[thread_index].last_vlib_time = 7;
1140   /* Limited until last burst is acked */
1141   tc->app_limited = snd_una + 4 * burst - 1;
1142   tcp_bt_track_tx (tc, burst);
1143   tc->snd_nxt += burst;
1144
1145   /* 5) check delivery rate at time 8
1146    *
1147    * tc->snd_una = snd_una + 10
1148    * sacks:
1149    * [snd_una + burst, snd_una + burst + 10]
1150    * [snd_una + 2 * burst + 10, snd_una + 2 * burst + 20]
1151    */
1152   session_main.wrk[thread_index].last_vlib_time = 8;
1153   tc->snd_una += 10;
1154   tc->bytes_acked = 10;
1155   sb->last_sacked_bytes = 20;
1156
1157   TCP_TEST (pool_elts (bt->samples) == 4, "there should be 4 samples");
1158
1159   vec_validate (sacks, 1);
1160   sacks[0].start = snd_una + burst;
1161   sacks[0].end = snd_una + burst + 10;
1162   sacks[1].start = snd_una + 2 * burst + 10;
1163   sacks[1].end = snd_una + 2 * burst + 20;
1164   tc->rcv_opts.sacks = sacks;
1165
1166   tcp_bt_sample_delivery_rate (tc, rs);
1167
1168   TCP_TEST (tcp_bt_is_sane (bt), "tracker should be sane");
1169   TCP_TEST (pool_elts (bt->samples) == 7, "there should be 7 samples %u",
1170             pool_elts (bt->samples));
1171   TCP_TEST (tc->delivered_time == 8, "delivered time should be 8");
1172   TCP_TEST (tc->delivered == 3 * burst + 30, "delivered should be %u is %u",
1173             3 * burst + 30, tc->delivered);
1174   /* All 3 samples have the same delivered number of bytes. So the first is
1175    * the reference for delivery estimate. */
1176   TCP_TEST (rs->interval_time == 4, "ack time should be 4 is %.2f",
1177             rs->interval_time);
1178   TCP_TEST (rs->delivered == 30, "delivered should be 30");
1179   TCP_TEST (rs->prior_delivered == 3 * burst,
1180             "sample delivered should be %u", 3 * burst);
1181   TCP_TEST (!(rs->flags & TCP_BTS_IS_RXT), "not retransmitted");
1182   TCP_TEST (!(rs->flags & TCP_BTS_IS_APP_LIMITED), "not app limited");
1183   /* All 3 samples have the same delivered number of bytes. The first
1184    * sets the first tx time */
1185   TCP_TEST (tc->first_tx_time == 4, "first_tx_time %u", tc->first_tx_time);
1186
1187   /* 6) Retransmit and track at time 9
1188    *
1189    * delivered = 3 * burst + 30
1190    * delivered_time = 8 (last ack)
1191    *
1192    * segments:
1193    * [snd_una + 10, snd_una + burst]
1194    * [snd_una + burst + 10, snd_una + 2 * burst + 10]
1195    * [snd_una + 2 * burst + 20, snd_una + 4 * burst]
1196    */
1197   session_main.wrk[thread_index].last_vlib_time = 9;
1198
1199   tcp_bt_track_rxt (tc, snd_una + 10, snd_una + burst);
1200   TCP_TEST (tcp_bt_is_sane (bt), "tracker should be sane");
1201   /* The retransmit covers everything left from first burst */
1202   TCP_TEST (pool_elts (bt->samples) == 7, "there should be 7 samples %u",
1203             pool_elts (bt->samples));
1204
1205   tcp_bt_track_rxt (tc, snd_una + burst + 10, snd_una + 2 * burst + 10);
1206   TCP_TEST (tcp_bt_is_sane (bt), "tracker should be sane");
1207   TCP_TEST (pool_elts (bt->samples) == 6, "there should be 6 samples %u",
1208             pool_elts (bt->samples));
1209
1210   /* Retransmit covers last sample entirely so it should be removed */
1211   tcp_bt_track_rxt (tc, snd_una + 2 * burst + 20, snd_una + 4 * burst);
1212   TCP_TEST (tcp_bt_is_sane (bt), "tracker should be sane");
1213   TCP_TEST (pool_elts (bt->samples) == 5, "there should be 5 samples %u",
1214             pool_elts (bt->samples));
1215
1216   vec_validate (min_seqs, 4);
1217   min_seqs[0] = snd_una + 10;
1218   min_seqs[1] = snd_una + burst;
1219   min_seqs[2] = snd_una + burst + 10;
1220   min_seqs[3] = snd_una + 2 * burst + 10;
1221   min_seqs[4] = snd_una + 2 * burst + 20;
1222
1223   root = bt->sample_lookup.nodes + bt->sample_lookup.root;
1224   bts = bt->samples + bt->head;
1225   for (i = 0; i < vec_len (min_seqs); i++)
1226     {
1227       if (bts->min_seq != min_seqs[i])
1228         TCP_TEST (0, "should be %u is %u", min_seqs[i], bts->min_seq);
1229       rbn = rb_tree_search_subtree_custom (&bt->sample_lookup, root,
1230                                            bts->min_seq, tbt_seq_lt);
1231       if (rbn->opaque != bts - bt->samples)
1232         TCP_TEST (0, "lookup should work");
1233       bts = bt->samples + bts->next;
1234     }
1235
1236   /* 7) check delivery rate at time 10
1237    *
1238    * tc->snd_una = snd_una + 2 * burst
1239    * sacks:
1240    * [snd_una + 2 * burst + 20, snd_una + 2 * burst + 30]
1241    * [snd_una + 2 * burst + 50, snd_una + 2 * burst + 60]
1242    */
1243   session_main.wrk[thread_index].last_vlib_time = 10;
1244   tc->snd_una = snd_una + 2 * burst;
1245   tc->bytes_acked = 2 * burst - 10;
1246   sb->last_sacked_bytes = 20;
1247
1248   sacks[0].start = snd_una + 2 * burst + 20;
1249   sacks[0].end = snd_una + 2 * burst + 30;
1250   sacks[1].start = snd_una + 2 * burst + 50;
1251   sacks[1].end = snd_una + 2 * burst + 60;
1252
1253   tcp_bt_sample_delivery_rate (tc, rs);
1254
1255   TCP_TEST (tcp_bt_is_sane (bt), "tracker should be sane");
1256   TCP_TEST (pool_elts (bt->samples) == 5, "num samples should be 5 is %u",
1257             pool_elts (bt->samples));
1258   TCP_TEST (tc->delivered_time == 10, "delivered time should be 10");
1259   TCP_TEST (tc->delivered == 5 * burst + 40, "delivered should be %u is %u",
1260             5 * burst + 40, tc->delivered);
1261   /* A rxt was acked and delivered time for it is 8 (last ack time) so
1262    * ack_time is 2 (8 - 10). However, first_tx_time for rxt was 4 and rxt
1263    * time 9. Therefore snd_time is 5 (9 - 4)*/
1264   TCP_TEST (rs->interval_time == 5, "ack time should be 5 is %.2f",
1265             rs->interval_time);
1266   /* delivered_now - delivered_rxt ~ 5 * burst + 40 - 3 * burst - 30 */
1267   TCP_TEST (rs->delivered == 2 * burst + 10, "delivered should be 210 is %u",
1268             rs->delivered);
1269   TCP_TEST (rs->prior_delivered == 3 * burst + 30,
1270             "sample delivered should be %u", 3 * burst + 30);
1271   TCP_TEST (rs->flags & TCP_BTS_IS_RXT, "is retransmitted");
1272   /* Sample is app limited because of the retransmits */
1273   TCP_TEST (rs->flags & TCP_BTS_IS_APP_LIMITED, "is app limited");
1274   TCP_TEST (tc->app_limited, "app limited should be set");
1275   TCP_TEST (tc->first_tx_time == 9, "first_tx_time %u", tc->first_tx_time);
1276
1277
1278   /*
1279    * 8) check delivery rate at time 11
1280    */
1281   session_main.wrk[thread_index].last_vlib_time = 11;
1282   tc->snd_una = tc->snd_nxt;
1283   tc->bytes_acked = 2 * burst;
1284   sb->last_sacked_bytes = 0;
1285   sb->last_bytes_delivered = 40;
1286
1287   memset (rs, 0, sizeof (*rs));
1288   tcp_bt_sample_delivery_rate (tc, rs);
1289
1290   TCP_TEST (tcp_bt_is_sane (bt), "tracker should be sane");
1291   TCP_TEST (pool_elts (bt->samples) == 0, "num samples should be 0 is %u",
1292             pool_elts (bt->samples));
1293   TCP_TEST (tc->delivered_time == 11, "delivered time should be 11");
1294   TCP_TEST (tc->delivered == 7 * burst, "delivered should be %u is %u",
1295             7 * burst, tc->delivered);
1296   /* Delivered time at retransmit was 8 so ack_time is 11 - 8 = 3. However,
1297    * first_tx_time for rxt was 4 and rxt time was 9. Therefore snd_time
1298    * is 9 - 4 = 5 */
1299   TCP_TEST (rs->interval_time == 5, "ack time should be 5 is %.2f",
1300             rs->interval_time);
1301   /* delivered_now - delivered_rxt ~ 7 * burst - 3 * burst - 30.
1302    * That's because we didn't retransmit any new segment. */
1303   TCP_TEST (rs->delivered == 4 * burst - 30, "delivered should be 160 is %u",
1304             rs->delivered);
1305   TCP_TEST (rs->prior_delivered == 3 * burst + 30,
1306             "sample delivered should be %u", 3 * burst + 30);
1307   TCP_TEST (rs->flags & TCP_BTS_IS_RXT, "is retransmitted");
1308   TCP_TEST (rs->flags & TCP_BTS_IS_APP_LIMITED, "is app limited");
1309   TCP_TEST (tc->app_limited == 0, "app limited should be cleared");
1310   TCP_TEST (tc->first_tx_time == 9, "first_tx_time %u", tc->first_tx_time);
1311
1312   /*
1313    * 9) test flush
1314    */
1315
1316   tcp_bt_track_tx (tc, burst);
1317   tc->snd_nxt += burst;
1318
1319   session_main.wrk[thread_index].last_vlib_time = 12;
1320   tcp_bt_track_tx (tc, burst);
1321   tc->snd_nxt += burst;
1322
1323   tcp_bt_flush_samples (tc);
1324
1325   /*
1326    * Cleanup
1327    */
1328   vec_free (sacks);
1329   vec_free (min_seqs);
1330   tcp_bt_cleanup (tc);
1331   return 0;
1332 }
1333
1334 static clib_error_t *
1335 tcp_test (vlib_main_t * vm,
1336           unformat_input_t * input, vlib_cli_command_t * cmd_arg)
1337 {
1338   int res = 0;
1339
1340   while (unformat_check_input (input) != UNFORMAT_END_OF_INPUT)
1341     {
1342       if (unformat (input, "sack"))
1343         {
1344           res = tcp_test_sack (vm, input);
1345         }
1346       else if (unformat (input, "session"))
1347         {
1348           res = tcp_test_session (vm, input);
1349         }
1350       else if (unformat (input, "lookup"))
1351         {
1352           res = tcp_test_lookup (vm, input);
1353         }
1354       else if (unformat (input, "delivery"))
1355         {
1356           res = tcp_test_delivery (vm, input);
1357         }
1358       else if (unformat (input, "all"))
1359         {
1360           if ((res = tcp_test_sack (vm, input)))
1361             goto done;
1362           if ((res = tcp_test_lookup (vm, input)))
1363             goto done;
1364           if ((res = tcp_test_delivery (vm, input)))
1365             goto done;
1366         }
1367       else
1368         break;
1369     }
1370
1371 done:
1372   if (res)
1373     return clib_error_return (0, "TCP unit test failed");
1374   return 0;
1375 }
1376
1377 /* *INDENT-OFF* */
1378 VLIB_CLI_COMMAND (tcp_test_command, static) =
1379 {
1380   .path = "test tcp",
1381   .short_help = "internal tcp unit tests",
1382   .function = tcp_test,
1383 };
1384 /* *INDENT-ON* */
1385
1386 /*
1387  * fd.io coding-style-patch-verification: ON
1388  *
1389  * Local Variables:
1390  * eval: (c-set-style "gnu")
1391  * End:
1392  */