src/vnet/tcp/tcp_bt.c

   1 /*
   2  * Copyright (c) 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  * TCP byte tracker that can generate delivery rate estimates. Based on
  16  * draft-cheng-iccrg-delivery-rate-estimation-00
  17  */
  18
  19 #include <vnet/tcp/tcp_bt.h>
  20 #include <vnet/tcp/tcp.h>
  21 #include <vnet/tcp/tcp_inlines.h>
  22
  23 static tcp_bt_sample_t *
  24 bt_get_sample (tcp_byte_tracker_t * bt, u32 bts_index)
  25 {
  26   if (pool_is_free_index (bt->samples, bts_index))
  27     return 0;
  28   return pool_elt_at_index (bt->samples, bts_index);
  29 }
  30
  31 static tcp_bt_sample_t *
  32 bt_next_sample (tcp_byte_tracker_t * bt, tcp_bt_sample_t * bts)
  33 {
  34   return bt_get_sample (bt, bts->next);
  35 }
  36
  37 static tcp_bt_sample_t *
  38 bt_prev_sample (tcp_byte_tracker_t * bt, tcp_bt_sample_t * bts)
  39 {
  40   return bt_get_sample (bt, bts->prev);
  41 }
  42
  43 static u32
  44 bt_sample_index (tcp_byte_tracker_t * bt, tcp_bt_sample_t * bts)
  45 {
  46   if (!bts)
  47     return TCP_BTS_INVALID_INDEX;
  48   return bts - bt->samples;
  49 }
  50
  51 static inline int
  52 bt_seq_lt (u32 a, u32 b)
  53 {
  54   return seq_lt (a, b);
  55 }
  56
  57 static tcp_bt_sample_t *
  58 bt_alloc_sample (tcp_byte_tracker_t * bt, u32 min_seq, u32 max_seq)
  59 {
  60   tcp_bt_sample_t *bts;
  61
  62   pool_get_zero (bt->samples, bts);
  63   bts->next = bts->prev = TCP_BTS_INVALID_INDEX;
  64   bts->min_seq = min_seq;
  65   bts->max_seq = max_seq;
  66   rb_tree_add_custom (&bt->sample_lookup, bts->min_seq, bts - bt->samples,
  67                       bt_seq_lt);
  68   return bts;
  69 }
  70
  71 static void
  72 bt_free_sample (tcp_byte_tracker_t * bt, tcp_bt_sample_t * bts)
  73 {
  74   if (bts->prev != TCP_BTS_INVALID_INDEX)
  75     {
  76       tcp_bt_sample_t *prev = bt_prev_sample (bt, bts);
  77       prev->next = bts->next;
  78     }
  79   else
  80     bt->head = bts->next;
  81
  82   if (bts->next != TCP_BTS_INVALID_INDEX)
  83     {
  84       tcp_bt_sample_t *next = bt_next_sample (bt, bts);
  85       next->prev = bts->prev;
  86     }
  87   else
  88     bt->tail = bts->prev;
  89
  90   rb_tree_del_custom (&bt->sample_lookup, bts->min_seq, bt_seq_lt);
  91   if (CLIB_DEBUG)
  92     memset (bts, 0xfc, sizeof (*bts));
  93   pool_put (bt->samples, bts);
  94 }
  95
  96 static tcp_bt_sample_t *
  97 bt_split_sample (tcp_byte_tracker_t * bt, tcp_bt_sample_t * bts, u32 seq)
  98 {
  99   tcp_bt_sample_t *ns, *next;
 100   u32 bts_index;
 101
 102   bts_index = bt_sample_index (bt, bts);
 103
 104   ASSERT (seq_leq (bts->min_seq, seq) && seq_lt (seq, bts->max_seq));
 105
 106   ns = bt_alloc_sample (bt, seq, bts->max_seq);
 107   bts = bt_get_sample (bt, bts_index);
 108
 109   *ns = *bts;
 110   ns->min_seq = seq;
 111   bts->max_seq = seq;
 112
 113   next = bt_next_sample (bt, bts);
 114   if (next)
 115     next->prev = bt_sample_index (bt, ns);
 116   else
 117     bt->tail = bt_sample_index (bt, ns);
 118
 119   bts->next = bt_sample_index (bt, ns);
 120   ns->prev = bt_sample_index (bt, bts);
 121
 122   return ns;
 123 }
 124
 125 static tcp_bt_sample_t *
 126 bt_merge_sample (tcp_byte_tracker_t * bt, tcp_bt_sample_t * prev,
 127                  tcp_bt_sample_t * cur)
 128 {
 129   ASSERT (prev->max_seq == cur->min_seq);
 130   prev->max_seq = cur->max_seq;
 131   if (bt_sample_index (bt, cur) == bt->tail)
 132     bt->tail = bt_sample_index (bt, prev);
 133   bt_free_sample (bt, cur);
 134   return prev;
 135 }
 136
 137 static tcp_bt_sample_t *
 138 bt_lookup_seq (tcp_byte_tracker_t * bt, u32 seq)
 139 {
 140   rb_tree_t *rt = &bt->sample_lookup;
 141   rb_node_t *cur, *prev;
 142   tcp_bt_sample_t *bts;
 143
 144   cur = rb_node (rt, rt->root);
 145   if (rb_node_is_tnil (rt, cur))
 146     return 0;
 147
 148   while (seq != cur->key)
 149     {
 150       prev = cur;
 151       if (seq_lt (seq, cur->key))
 152         cur = rb_node_left (rt, cur);
 153       else
 154         cur = rb_node_right (rt, cur);
 155
 156       if (rb_node_is_tnil (rt, cur))
 157         {
 158           /* Hit tnil as a left child. Find predecessor */
 159           if (seq_lt (seq, prev->key))
 160             {
 161               cur = rb_tree_predecessor (rt, prev);
 162               if (rb_node_is_tnil (rt, cur))
 163                 return 0;
 164               bts = bt_get_sample (bt, cur->opaque);
 165             }
 166           /* Hit tnil as a right child */
 167           else
 168             {
 169               bts = bt_get_sample (bt, prev->opaque);
 170             }
 171
 172           if (seq_geq (seq, bts->min_seq))
 173             return bts;
 174
 175           return 0;
 176         }
 177     }
 178
 179   if (!rb_node_is_tnil (rt, cur))
 180     return bt_get_sample (bt, cur->opaque);
 181
 182   return 0;
 183 }
 184
 185 static void
 186 bt_update_sample (tcp_byte_tracker_t * bt, tcp_bt_sample_t * bts, u32 seq)
 187 {
 188   rb_tree_del_custom (&bt->sample_lookup, bts->min_seq, bt_seq_lt);
 189   bts->min_seq = seq;
 190   rb_tree_add_custom (&bt->sample_lookup, bts->min_seq,
 191                       bt_sample_index (bt, bts), bt_seq_lt);
 192 }
 193
 194 static tcp_bt_sample_t *
 195 bt_fix_overlapped (tcp_byte_tracker_t * bt, tcp_bt_sample_t * start,
 196                    u32 seq, u8 is_end)
 197 {
 198   tcp_bt_sample_t *cur, *next;
 199
 200   cur = start;
 201   while (cur && seq_leq (cur->max_seq, seq))
 202     {
 203       next = bt_next_sample (bt, cur);
 204       bt_free_sample (bt, cur);
 205       cur = next;
 206     }
 207
 208   if (cur && seq_lt (cur->min_seq, seq))
 209     bt_update_sample (bt, cur, seq);
 210
 211   return cur;
 212 }
 213
 214 int
 215 tcp_bt_is_sane (tcp_byte_tracker_t * bt)
 216 {
 217   tcp_bt_sample_t *bts, *tmp;
 218
 219   if (pool_elts (bt->samples) != pool_elts (bt->sample_lookup.nodes) - 1)
 220     return 0;
 221
 222   if (bt->head == TCP_BTS_INVALID_INDEX)
 223     {
 224       if (bt->tail != TCP_BTS_INVALID_INDEX)
 225         return 0;
 226       if (pool_elts (bt->samples) != 0)
 227         return 0;
 228       return 1;
 229     }
 230
 231   bts = bt_get_sample (bt, bt->tail);
 232   if (!bts)
 233     return 0;
 234
 235   bts = bt_get_sample (bt, bt->head);
 236   if (!bts || bts->prev != TCP_BTS_INVALID_INDEX)
 237     return 0;
 238
 239   while (bts)
 240     {
 241       tmp = bt_lookup_seq (bt, bts->min_seq);
 242       if (!tmp)
 243         return 0;
 244       if (tmp != bts)
 245         return 0;
 246       tmp = bt_next_sample (bt, bts);
 247       if (tmp)
 248         {
 249           if (tmp->prev != bt_sample_index (bt, bts))
 250             {
 251               clib_warning ("next %u thinks prev is %u should be %u",
 252                             bts->next, tmp->prev, bt_sample_index (bt, bts));
 253               return 0;
 254             }
 255           if (!seq_lt (bts->min_seq, tmp->min_seq))
 256             return 0;
 257         }
 258       else
 259         {
 260           if (bt->tail != bt_sample_index (bt, bts))
 261             return 0;
 262           if (bts->next != TCP_BTS_INVALID_INDEX)
 263             return 0;
 264         }
 265       bts = tmp;
 266     }
 267   return 1;
 268 }
 269
 270 static tcp_bt_sample_t *
 271 tcp_bt_alloc_tx_sample (tcp_connection_t * tc, u32 min_seq, u32 max_seq)
 272 {
 273   tcp_bt_sample_t *bts;
 274   bts = bt_alloc_sample (tc->bt, min_seq, max_seq);
 275   bts->delivered = tc->delivered;
 276   bts->delivered_time = tc->delivered_time;
 277   bts->tx_time = tcp_time_now_us (tc->c_thread_index);
 278   bts->first_tx_time = tc->first_tx_time;
 279   bts->flags |= tc->app_limited ? TCP_BTS_IS_APP_LIMITED : 0;
 280   bts->tx_in_flight = tcp_flight_size (tc);
 281   bts->tx_lost = tc->lost;
 282   return bts;
 283 }
 284
 285 void
 286 tcp_bt_check_app_limited (tcp_connection_t * tc)
 287 {
 288   u32 available_bytes, flight_size;
 289
 290   available_bytes = transport_max_tx_dequeue (&tc->connection);
 291   flight_size = tcp_flight_size (tc);
 292
 293   /* Not enough bytes to fill the cwnd */
 294   if (available_bytes + flight_size + tc->snd_mss < tc->cwnd
 295       /* Bytes considered lost have been retransmitted */
 296       && tc->sack_sb.lost_bytes <= tc->snd_rxt_bytes)
 297     tc->app_limited = tc->delivered + flight_size ? : 1;
 298 }
 299
 300 void
 301 tcp_bt_track_tx (tcp_connection_t * tc, u32 len)
 302 {
 303   tcp_byte_tracker_t *bt = tc->bt;
 304   tcp_bt_sample_t *bts, *tail;
 305   u32 bts_index;
 306
 307   tail = bt_get_sample (bt, bt->tail);
 308   if (tail && tail->max_seq == tc->snd_nxt
 309       && tail->tx_time == tcp_time_now_us (tc->c_thread_index))
 310     {
 311       tail->max_seq += len;
 312       return;
 313     }
 314
 315   if (tc->snd_una == tc->snd_nxt)
 316     {
 317       tc->delivered_time = tcp_time_now_us (tc->c_thread_index);
 318       tc->first_tx_time = tc->delivered_time;
 319     }
 320
 321   bts = tcp_bt_alloc_tx_sample (tc, tc->snd_nxt, tc->snd_nxt + len);
 322   bts_index = bt_sample_index (bt, bts);
 323   tail = bt_get_sample (bt, bt->tail);
 324   if (tail)
 325     {
 326       tail->next = bts_index;
 327       bts->prev = bt->tail;
 328       bt->tail = bts_index;
 329     }
 330   else
 331     {
 332       bt->tail = bt->head = bts_index;
 333     }
 334 }
 335
 336 void
 337 tcp_bt_track_rxt (tcp_connection_t * tc, u32 start, u32 end)
 338 {
 339   tcp_byte_tracker_t *bt = tc->bt;
 340   tcp_bt_sample_t *bts, *next, *cur, *prev, *nbts;
 341   u32 bts_index, cur_index, next_index, prev_index, max_seq;
 342   u8 is_end = end == tc->snd_nxt;
 343   tcp_bts_flags_t bts_flags;
 344
 345   /* Contiguous blocks retransmitted at the same time */
 346   bts = bt_get_sample (bt, bt->last_ooo);
 347   if (bts && bts->max_seq == start
 348       && bts->tx_time == tcp_time_now_us (tc->c_thread_index))
 349     {
 350       bts->max_seq = end;
 351       next = bt_next_sample (bt, bts);
 352       if (next)
 353         bt_fix_overlapped (bt, next, end, is_end);
 354
 355       return;
 356     }
 357
 358   /* Find original tx sample and cache flags in case the sample
 359    * is freed or the pool moves */
 360   bts = bt_lookup_seq (bt, start);
 361   bts_flags = bts->flags;
 362
 363   ASSERT (bts != 0 && seq_geq (start, bts->min_seq));
 364
 365   /* Head in the past */
 366   if (seq_lt (bts->min_seq, tc->snd_una))
 367     bt_update_sample (bt, bts, tc->snd_una);
 368
 369   /* Head overlap */
 370   if (bts->min_seq == start)
 371     {
 372       prev_index = bts->prev;
 373       next = bt_fix_overlapped (bt, bts, end, is_end);
 374       /* bts might no longer be valid from here */
 375       next_index = bt_sample_index (bt, next);
 376
 377       cur = tcp_bt_alloc_tx_sample (tc, start, end);
 378       cur->flags |= TCP_BTS_IS_RXT;
 379       if (bts_flags & TCP_BTS_IS_RXT)
 380         cur->flags |= TCP_BTS_IS_RXT_LOST;
 381       cur->next = next_index;
 382       cur->prev = prev_index;
 383
 384       cur_index = bt_sample_index (bt, cur);
 385
 386       if (next_index != TCP_BTS_INVALID_INDEX)
 387         {
 388           next = bt_get_sample (bt, next_index);
 389           next->prev = cur_index;
 390         }
 391       else
 392         {
 393           bt->tail = cur_index;
 394         }
 395
 396       if (prev_index != TCP_BTS_INVALID_INDEX)
 397         {
 398           prev = bt_get_sample (bt, prev_index);
 399           prev->next = cur_index;
 400         }
 401       else
 402         {
 403           bt->head = cur_index;
 404         }
 405
 406       bt->last_ooo = cur_index;
 407       return;
 408     }
 409
 410   bts_index = bt_sample_index (bt, bts);
 411   next = bt_next_sample (bt, bts);
 412   if (next)
 413     bt_fix_overlapped (bt, next, end, is_end);
 414
 415   max_seq = bts->max_seq;
 416   ASSERT (seq_lt (start, max_seq));
 417
 418   /* Have to split or tail overlap */
 419   cur = tcp_bt_alloc_tx_sample (tc, start, end);
 420   cur->flags |= TCP_BTS_IS_RXT;
 421   if (bts_flags & TCP_BTS_IS_RXT)
 422     cur->flags |= TCP_BTS_IS_RXT_LOST;
 423   cur->prev = bts_index;
 424   cur_index = bt_sample_index (bt, cur);
 425
 426   /* Split. Allocate another sample */
 427   if (seq_lt (end, max_seq))
 428     {
 429       nbts = tcp_bt_alloc_tx_sample (tc, end, bts->max_seq);
 430       cur = bt_get_sample (bt, cur_index);
 431       bts = bt_get_sample (bt, bts_index);
 432
 433       *nbts = *bts;
 434       nbts->min_seq = end;
 435
 436       if (nbts->next != TCP_BTS_INVALID_INDEX)
 437         {
 438           next = bt_get_sample (bt, nbts->next);
 439           next->prev = bt_sample_index (bt, nbts);
 440         }
 441       else
 442         bt->tail = bt_sample_index (bt, nbts);
 443
 444       bts->next = nbts->prev = cur_index;
 445       cur->next = bt_sample_index (bt, nbts);
 446
 447       bts->max_seq = start;
 448       bt->last_ooo = cur_index;
 449     }
 450   /* Tail completely overlapped */
 451   else
 452     {
 453       bts = bt_get_sample (bt, bts_index);
 454       bts->max_seq = start;
 455
 456       if (bts->next != TCP_BTS_INVALID_INDEX)
 457         {
 458           next = bt_get_sample (bt, bts->next);
 459           next->prev = cur_index;
 460         }
 461       else
 462         bt->tail = cur_index;
 463
 464       cur->next = bts->next;
 465       bts->next = cur_index;
 466
 467       bt->last_ooo = cur_index;
 468     }
 469 }
 470
 471 static void
 472 tcp_bt_sample_to_rate_sample (tcp_connection_t * tc, tcp_bt_sample_t * bts,
 473                               tcp_rate_sample_t * rs)
 474 {
 475   if (bts->flags & TCP_BTS_IS_SACKED)
 476     return;
 477
 478   if (rs->prior_delivered && rs->prior_delivered >= bts->delivered)
 479     return;
 480
 481   rs->prior_delivered = bts->delivered;
 482   rs->prior_time = bts->delivered_time;
 483   rs->interval_time = bts->tx_time - bts->first_tx_time;
 484   rs->rtt_time = tc->delivered_time - bts->tx_time;
 485   rs->flags = bts->flags;
 486   rs->tx_in_flight = bts->tx_in_flight;
 487   rs->tx_lost = bts->tx_lost;
 488   tc->first_tx_time = bts->tx_time;
 489 }
 490
 491 static void
 492 tcp_bt_walk_samples (tcp_connection_t * tc, tcp_rate_sample_t * rs)
 493 {
 494   tcp_byte_tracker_t *bt = tc->bt;
 495   tcp_bt_sample_t *next, *cur;
 496
 497   cur = bt_get_sample (bt, bt->head);
 498   while (cur && seq_leq (cur->max_seq, tc->snd_una))
 499     {
 500       next = bt_next_sample (bt, cur);
 501       tcp_bt_sample_to_rate_sample (tc, cur, rs);
 502       bt_free_sample (bt, cur);
 503       cur = next;
 504     }
 505
 506   if (cur && seq_lt (cur->min_seq, tc->snd_una))
 507     tcp_bt_sample_to_rate_sample (tc, cur, rs);
 508 }
 509
 510 static void
 511 tcp_bt_walk_samples_ooo (tcp_connection_t * tc, tcp_rate_sample_t * rs)
 512 {
 513   sack_block_t *blks = tc->rcv_opts.sacks, *blk;
 514   tcp_byte_tracker_t *bt = tc->bt;
 515   tcp_bt_sample_t *cur, *prev, *next;
 516   int i;
 517
 518   for (i = 0; i < vec_len (blks); i++)
 519     {
 520       blk = &blks[i];
 521
 522       /* Ignore blocks that are already covered by snd_una */
 523       if (seq_lt (blk->end, tc->snd_una))
 524         continue;
 525
 526       cur = bt_lookup_seq (bt, blk->start);
 527       if (!cur)
 528         continue;
 529
 530       ASSERT (seq_geq (blk->start, cur->min_seq)
 531               && seq_lt (blk->start, cur->max_seq));
 532
 533       /* Current should be split. Second part will be consumed */
 534       if (PREDICT_FALSE (cur->min_seq != blk->start))
 535         {
 536           cur = bt_split_sample (bt, cur, blk->start);
 537           prev = bt_prev_sample (bt, cur);
 538         }
 539       else
 540         prev = bt_prev_sample (bt, cur);
 541
 542       while (cur && seq_leq (cur->max_seq, blk->end))
 543         {
 544           if (!(cur->flags & TCP_BTS_IS_SACKED))
 545             {
 546               tcp_bt_sample_to_rate_sample (tc, cur, rs);
 547               cur->flags |= TCP_BTS_IS_SACKED;
 548               if (prev && (prev->flags & TCP_BTS_IS_SACKED))
 549                 {
 550                   cur = bt_merge_sample (bt, prev, cur);
 551                   next = bt_next_sample (bt, cur);
 552                 }
 553               else
 554                 {
 555                   next = bt_next_sample (bt, cur);
 556                   if (next && (next->flags & TCP_BTS_IS_SACKED))
 557                     {
 558                       cur = bt_merge_sample (bt, cur, next);
 559                       next = bt_next_sample (bt, cur);
 560                     }
 561                 }
 562             }
 563           else
 564             next = bt_next_sample (bt, cur);
 565
 566           prev = cur;
 567           cur = next;
 568         }
 569
 570       if (cur && seq_lt (cur->min_seq, blk->end))
 571         {
 572           tcp_bt_sample_to_rate_sample (tc, cur, rs);
 573           prev = bt_prev_sample (bt, cur);
 574           /* Extend previous to include the newly sacked bytes */
 575           if (prev && (prev->flags & TCP_BTS_IS_SACKED))
 576             {
 577               prev->max_seq = blk->end;
 578               bt_update_sample (bt, cur, blk->end);
 579             }
 580           /* Split sample into two. First part is consumed */
 581           else
 582             {
 583               next = bt_split_sample (bt, cur, blk->end);
 584               cur = bt_prev_sample (bt, next);
 585               cur->flags |= TCP_BTS_IS_SACKED;
 586             }
 587         }
 588     }
 589 }
 590
 591 void
 592 tcp_bt_sample_delivery_rate (tcp_connection_t * tc, tcp_rate_sample_t * rs)
 593 {
 594   u32 delivered;
 595
 596   if (PREDICT_FALSE (tc->flags & TCP_CONN_FINSNT))
 597     return;
 598
 599   tc->lost += tc->sack_sb.last_lost_bytes;
 600
 601   delivered = tc->bytes_acked + tc->sack_sb.last_sacked_bytes;
 602   if (!delivered || tc->bt->head == TCP_BTS_INVALID_INDEX)
 603     return;
 604
 605   /* Do not count bytes that were previously sacked again */
 606   tc->delivered += delivered - tc->sack_sb.last_bytes_delivered;
 607   tc->delivered_time = tcp_time_now_us (tc->c_thread_index);
 608
 609   if (tc->app_limited && tc->delivered > tc->app_limited)
 610     tc->app_limited = 0;
 611
 612   if (tc->bytes_acked)
 613     tcp_bt_walk_samples (tc, rs);
 614
 615   if (tc->sack_sb.last_sacked_bytes)
 616     tcp_bt_walk_samples_ooo (tc, rs);
 617
 618   rs->interval_time = clib_max ((tc->delivered_time - rs->prior_time),
 619                                 rs->interval_time);
 620   rs->delivered = tc->delivered - rs->prior_delivered;
 621   rs->acked_and_sacked = delivered;
 622   rs->last_lost = tc->sack_sb.last_lost_bytes;
 623   rs->lost = tc->lost - rs->tx_lost;
 624 }
 625
 626 void
 627 tcp_bt_flush_samples (tcp_connection_t * tc)
 628 {
 629   tcp_byte_tracker_t *bt = tc->bt;
 630   tcp_bt_sample_t *bts;
 631   u32 *samples = 0, *si;
 632
 633   vec_validate (samples, pool_elts (bt->samples) - 1);
 634   vec_reset_length (samples);
 635
 636   /* *INDENT-OFF* */
 637   pool_foreach (bts, bt->samples, ({
 638     vec_add1 (samples, bts - bt->samples);
 639   }));
 640   /* *INDENT-ON* */
 641
 642   vec_foreach (si, samples)
 643   {
 644     bts = bt_get_sample (bt, *si);
 645     bt_free_sample (bt, bts);
 646   }
 647
 648   vec_free (samples);
 649 }
 650
 651 void
 652 tcp_bt_cleanup (tcp_connection_t * tc)
 653 {
 654   tcp_byte_tracker_t *bt = tc->bt;
 655
 656   rb_tree_free_nodes (&bt->sample_lookup);
 657   pool_free (bt->samples);
 658   clib_mem_free (bt);
 659   tc->bt = 0;
 660 }
 661
 662 void
 663 tcp_bt_init (tcp_connection_t * tc)
 664 {
 665   tcp_byte_tracker_t *bt;
 666
 667   bt = clib_mem_alloc (sizeof (tcp_byte_tracker_t));
 668   clib_memset (bt, 0, sizeof (tcp_byte_tracker_t));
 669
 670   rb_tree_init (&bt->sample_lookup);
 671   bt->head = bt->tail = TCP_BTS_INVALID_INDEX;
 672   tc->bt = bt;
 673 }
 674
 675 u8 *
 676 format_tcp_bt_sample (u8 * s, va_list * args)
 677 {
 678   tcp_connection_t *tc = va_arg (*args, tcp_connection_t *);
 679   tcp_bt_sample_t *bts = va_arg (*args, tcp_bt_sample_t *);
 680   f64 now = tcp_time_now_us (tc->c_thread_index);
 681   s = format (s, "[%u, %u] d %u dt %.3f txt %.3f ftxt %.3f flags 0x%x",
 682               bts->min_seq - tc->iss, bts->max_seq - tc->iss, bts->delivered,
 683               now - bts->delivered_time, now - bts->tx_time,
 684               now - bts->first_tx_time, bts->flags);
 685   return s;
 686 }
 687
 688 u8 *
 689 format_tcp_bt (u8 * s, va_list * args)
 690 {
 691   tcp_connection_t *tc = va_arg (*args, tcp_connection_t *);
 692   tcp_byte_tracker_t *bt = tc->bt;
 693   tcp_bt_sample_t *bts;
 694
 695   bts = bt_get_sample (bt, bt->head);
 696   while (bts)
 697     {
 698       s = format (s, "%U\n", format_tcp_bt_sample, tc, bts);
 699       bts = bt_next_sample (bt, bts);
 700     }
 701
 702   return s;
 703 }
 704
 705 /*
 706  * fd.io coding-style-patch-verification: ON
 707  *
 708  * Local Variables:
 709  * eval: (c-set-style "gnu")
 710  * End:
 711  */