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