FD.io VPP  v20.09-64-g4f7b92f0a
Vector Packet Processing
tcp_bt.c
Go to the documentation of this file.
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 *
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 *
33 {
34  return bt_get_sample (bt, bts->next);
35 }
36 
37 static tcp_bt_sample_t *
39 {
40  return bt_get_sample (bt, bts->prev);
41 }
42 
43 static u32
45 {
46  if (!bts)
47  return TCP_BTS_INVALID_INDEX;
48  return bts - bt->samples;
49 }
50 
51 static inline int
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
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 
91  if (CLIB_DEBUG)
92  memset (bts, 0xfc, sizeof (*bts));
93  pool_put (bt->samples, bts);
94 }
95 
96 static tcp_bt_sample_t *
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 *
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 *
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
187 {
189  bts->min_seq = seq;
191  bt_sample_index (bt, bts), bt_seq_lt);
192 }
193 
194 static tcp_bt_sample_t *
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
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 *
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
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
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
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
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
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
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
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
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
653 {
654  tcp_byte_tracker_t *bt = tc->bt;
655 
657  pool_free (bt->samples);
658  clib_mem_free (bt);
659  tc->bt = 0;
660 }
661 
662 void
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 
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  */
#define vec_validate(V, I)
Make sure vector is long enough for given index (no header, unspecified alignment) ...
Definition: vec.h:509
static tcp_bt_sample_t * bt_next_sample(tcp_byte_tracker_t *bt, tcp_bt_sample_t *bts)
Definition: tcp_bt.c:32
#define TCP_BTS_INVALID_INDEX
Definition: tcp_types.h:199
rb_node_t * rb_tree_predecessor(rb_tree_t *rt, rb_node_t *x)
Definition: rbtree.c:287
u64 tx_lost
Lost at tx time.
Definition: tcp_types.h:220
f64 tx_time
Transmit time for the burst.
Definition: tcp_types.h:217
u8 * format_tcp_bt_sample(u8 *s, va_list *args)
Definition: tcp_bt.c:676
struct _sack_block sack_block_t
int tcp_bt_is_sane(tcp_byte_tracker_t *bt)
Check if the byte tracker is in sane state.
Definition: tcp_bt.c:215
a
Definition: bitmap.h:538
u8 * format_tcp_bt(u8 *s, va_list *args)
Definition: tcp_bt.c:689
u32 prev
Previous sample index in list.
Definition: tcp_types.h:212
f64 first_tx_time
Connection first tx time at tx.
Definition: tcp_types.h:218
static tcp_bt_sample_t * bt_split_sample(tcp_byte_tracker_t *bt, tcp_bt_sample_t *bts, u32 seq)
Definition: tcp_bt.c:97
static rb_node_t * rb_node_left(rb_tree_t *rt, rb_node_t *n)
Definition: rbtree.h:94
#define pool_get_zero(P, E)
Allocate an object E from a pool P and zero it.
Definition: pool.h:255
static void bt_free_sample(tcp_byte_tracker_t *bt, tcp_bt_sample_t *bts)
Definition: tcp_bt.c:72
clib_memset(h->entries, 0, sizeof(h->entries[0]) *entries)
static tcp_bt_sample_t * bt_lookup_seq(tcp_byte_tracker_t *bt, u32 seq)
Definition: tcp_bt.c:138
struct _tcp_connection tcp_connection_t
f64 prior_time
Delivered time of sample used for rate.
Definition: tcp_types.h:228
static rb_node_t * rb_node(rb_tree_t *rt, rb_node_index_t ri)
Definition: rbtree.h:82
enum tcp_bts_flags_ tcp_bts_flags_t
u8 * format(u8 *s, const char *fmt,...)
Definition: format.c:424
static rb_node_t * rb_node_right(rb_tree_t *rt, rb_node_t *n)
Definition: rbtree.h:88
u32 head
Head of samples linked list.
Definition: tcp_types.h:244
void rb_tree_free_nodes(rb_tree_t *rt)
Definition: rbtree.c:476
unsigned char u8
Definition: types.h:56
static void tcp_bt_sample_to_rate_sample(tcp_connection_t *tc, tcp_bt_sample_t *bts, tcp_rate_sample_t *rs)
Definition: tcp_bt.c:472
static void tcp_bt_walk_samples(tcp_connection_t *tc, tcp_rate_sample_t *rs)
Definition: tcp_bt.c:492
#define vec_reset_length(v)
Reset vector length to zero NULL-pointer tolerant.
double f64
Definition: types.h:142
static tcp_bt_sample_t * bt_prev_sample(tcp_byte_tracker_t *bt, tcp_bt_sample_t *bts)
Definition: tcp_bt.c:38
#define pool_foreach(VAR, POOL, BODY)
Iterate through pool.
Definition: pool.h:513
void tcp_bt_sample_delivery_rate(tcp_connection_t *tc, tcp_rate_sample_t *rs)
Generate a delivery rate sample from recently acked bytes.
Definition: tcp_bt.c:592
#define seq_leq(_s1, _s2)
Definition: tcp_packet.h:178
static tcp_bt_sample_t * bt_alloc_sample(tcp_byte_tracker_t *bt, u32 min_seq, u32 max_seq)
Definition: tcp_bt.c:58
unsigned int u32
Definition: types.h:88
u32 key
node key
Definition: rbtree.h:38
static tcp_bt_sample_t * bt_get_sample(tcp_byte_tracker_t *bt, u32 bts_index)
Definition: tcp_bt.c:24
u32 max_seq
Max seq number.
Definition: tcp_types.h:214
void tcp_bt_init(tcp_connection_t *tc)
Byte tracker initialize.
Definition: tcp_bt.c:663
u32 lost
Number of bytes lost over interval.
Definition: tcp_types.h:236
#define pool_elt_at_index(p, i)
Returns pointer to element at given index.
Definition: pool.h:534
u32 delivered
Bytes delivered in interval_time.
Definition: tcp_types.h:233
uword opaque
value stored by node
Definition: rbtree.h:39
rb_tree_t sample_lookup
Rbtree for sample lookup by min_seq.
Definition: tcp_types.h:243
tcp_bt_sample_t * samples
Pool of samples.
Definition: tcp_types.h:242
f64 interval_time
Time to ack the bytes delivered.
Definition: tcp_types.h:229
void tcp_bt_cleanup(tcp_connection_t *tc)
Byte tracker cleanup.
Definition: tcp_bt.c:652
#define pool_put(P, E)
Free an object E in pool P.
Definition: pool.h:302
#define PREDICT_FALSE(x)
Definition: clib.h:120
void rb_tree_init(rb_tree_t *rt)
Definition: rbtree.c:483
u32 next
Next sample index in list.
Definition: tcp_types.h:211
tcp_bts_flags_t flags
Sample flag.
Definition: tcp_types.h:221
u8 len
Definition: ip_types.api:92
f64 delivered_time
Delivered time when sample taken.
Definition: tcp_types.h:216
#define pool_free(p)
Free a pool.
Definition: pool.h:427
static u32 tcp_flight_size(const tcp_connection_t *tc)
Our estimate of the number of bytes in flight (pipe size)
Definition: tcp_inlines.h:94
void tcp_bt_track_tx(tcp_connection_t *tc, u32 len)
Track a tcp tx burst.
Definition: tcp_bt.c:301
sll srl srl sll sra u16x4 i
Definition: vector_sse42.h:317
#define vec_free(V)
Free vector&#39;s memory (no header).
Definition: vec.h:380
#define clib_warning(format, args...)
Definition: error.h:59
static u32 bt_sample_index(tcp_byte_tracker_t *bt, tcp_bt_sample_t *bts)
Definition: tcp_bt.c:44
f64 rtt_time
RTT for sample.
Definition: tcp_types.h:230
#define pool_is_free_index(P, I)
Use free bitmap to query whether given index is free.
Definition: pool.h:299
static int bt_seq_lt(u32 a, u32 b)
Definition: tcp_bt.c:52
static u32 transport_max_tx_dequeue(transport_connection_t *tc)
Definition: session.h:503
#define seq_geq(_s1, _s2)
Definition: tcp_packet.h:180
void tcp_bt_check_app_limited(tcp_connection_t *tc)
Check if sample to be generated is app limited.
Definition: tcp_bt.c:286
#define ASSERT(truth)
void tcp_bt_track_rxt(tcp_connection_t *tc, u32 start, u32 end)
Track a tcp retransmission.
Definition: tcp_bt.c:337
static tcp_bt_sample_t * bt_merge_sample(tcp_byte_tracker_t *bt, tcp_bt_sample_t *prev, tcp_bt_sample_t *cur)
Definition: tcp_bt.c:126
void rb_tree_del_custom(rb_tree_t *rt, u32 key, rb_tree_lt_fn ltfn)
Definition: rbtree.c:461
static void clib_mem_free(void *p)
Definition: mem.h:215
u32 last_lost
Bytes lost now.
Definition: tcp_types.h:235
u32 last_ooo
Cached last ooo sample.
Definition: tcp_types.h:246
static void * clib_mem_alloc(uword size)
Definition: mem.h:157
#define clib_max(x, y)
Definition: clib.h:320
u64 tx_lost
Lost over interval.
Definition: tcp_types.h:232
u64 delivered
Total delivered bytes for sample.
Definition: tcp_types.h:215
static u8 rb_node_is_tnil(rb_tree_t *rt, rb_node_t *n)
Definition: rbtree.h:76
u32 tail
Tail of samples linked list.
Definition: tcp_types.h:245
u64 tx_in_flight
In flight at (re)transmit time.
Definition: tcp_types.h:231
#define vec_len(v)
Number of elements in vector (rvalue-only, NULL tolerant)
static void bt_update_sample(tcp_byte_tracker_t *bt, tcp_bt_sample_t *bts, u32 seq)
Definition: tcp_bt.c:186
static f64 tcp_time_now_us(u32 thread_index)
Definition: tcp_inlines.h:213
u32 min_seq
Min seq number in sample.
Definition: tcp_types.h:213
void tcp_bt_flush_samples(tcp_connection_t *tc)
Flush byte tracker samples.
Definition: tcp_bt.c:627
u64 prior_delivered
Delivered of sample used for rate, i.e., total bytes delivered at prior_time.
Definition: tcp_types.h:226
static tcp_bt_sample_t * bt_fix_overlapped(tcp_byte_tracker_t *bt, tcp_bt_sample_t *start, u32 seq, u8 is_end)
Definition: tcp_bt.c:195
#define vec_foreach(var, vec)
Vector iterator.
f64 end
end of the time range
Definition: mactime.api:44
rb_node_t * nodes
pool of nodes
Definition: rbtree.h:44
rb_node_index_t rb_tree_add_custom(rb_tree_t *rt, u32 key, uword opaque, rb_tree_lt_fn ltfn)
Definition: rbtree.c:195
u8 si
Definition: lisp_types.api:47
tcp_bts_flags_t flags
Rate sample flags from bt sample.
Definition: tcp_types.h:237
static tcp_bt_sample_t * tcp_bt_alloc_tx_sample(tcp_connection_t *tc, u32 min_seq, u32 max_seq)
Definition: tcp_bt.c:271
static void tcp_bt_walk_samples_ooo(tcp_connection_t *tc, tcp_rate_sample_t *rs)
Definition: tcp_bt.c:511
rb_node_index_t root
root index
Definition: rbtree.h:45
#define seq_lt(_s1, _s2)
Definition: tcp_packet.h:177
u32 acked_and_sacked
Bytes acked + sacked now.
Definition: tcp_types.h:234
u64 tx_in_flight
In flight at tx time.
Definition: tcp_types.h:219
static uword pool_elts(void *v)
Number of active elements in a pool.
Definition: pool.h:128