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