tcp: byte tracker fix

Type: fix

Signed-off-by: Ryujiro Shibuya <ryujiro.shibuya@owmobility.com>
Change-Id: If7e22978a6b65f5b68ccb2bd97b5e0fba167b3bf

2 files changed, 220 insertions, 1 deletions

diff --git a/src/plugins/unittest/tcp_test.c b/src/plugins/unittest/tcp_test.c
index 0d854084339..eb2b6b68072 100644
--- a/src/plugins/unittest/tcp_test.c
+++ b/src/plugins/unittest/tcp_test.c
@@ -1329,6 +1329,217 @@ tcp_test_delivery (vlib_main_t * vm, unformat_input_t * input)
   return 0;
 }
 
+static int
+tcp_test_bt (vlib_main_t * vm, unformat_input_t * input)
+{
+  u32 thread_index = 0;
+  tcp_rate_sample_t _rs = { 0 }, *rs = &_rs;
+  tcp_connection_t _tc, *tc = &_tc;
+  int __clib_unused verbose = 0, i;
+  tcp_byte_tracker_t *bt;
+  tcp_bt_sample_t *bts;
+  u32 head;
+  sack_block_t *blk;
+
+  /* Init data structures */
+  memset (tc, 0, sizeof (*tc));
+  tcp_bt_init (tc);
+  bt = tc->bt;
+
+  /* 1) track first burst at time 1 */
+  /* [] --> [0:100] */
+  session_main.wrk[thread_index].last_vlib_time = 1;
+  tcp_bt_track_tx (tc, 100);
+  tc->snd_nxt += 100;
+
+  TCP_TEST (tcp_bt_is_sane (bt), "tracker should be sane");
+  TCP_TEST (pool_elts (bt->samples) == 1, "should have 1 sample");
+  bts = pool_elt_at_index (bt->samples, bt->head);
+  head = bt->head;
+  TCP_TEST (bts->min_seq == tc->snd_una, "min seq should be snd_una");
+  TCP_TEST (bts->next == TCP_BTS_INVALID_INDEX, "next should be invalid");
+  TCP_TEST (bts->prev == TCP_BTS_INVALID_INDEX, "prev should be invalid");
+  TCP_TEST (bts->tx_time == 1, "tx time should be 1");
+  TCP_TEST (!(bts->flags & TCP_BTS_IS_RXT), "not retransmitted");
+  TCP_TEST (!(bts->flags & TCP_BTS_IS_SACKED), "not sacked");
+
+  /* 2) track second butst at time 2 */
+  /* --> [0:100][100:200] */
+  session_main.wrk[thread_index].last_vlib_time = 2;
+  tcp_bt_track_tx (tc, 100);
+  tc->snd_nxt += 100;
+
+  TCP_TEST (tcp_bt_is_sane (bt), "tracker should be sane");
+  TCP_TEST (pool_elts (bt->samples) == 2, "should have 2 samples");
+  bts = pool_elt_at_index (bt->samples, bt->head);
+  TCP_TEST (head == bt->head, "head is not updated");
+  TCP_TEST (bts->min_seq == tc->snd_una, "min seq should be snd_una");
+  TCP_TEST (bts->tx_time == 1, "tx time of head should be 1");
+
+  /* 3) acked partially at time 3 */
+  /* ACK:150 */
+  /* --> [150:200] */
+  session_main.wrk[thread_index].last_vlib_time = 3;
+  tc->snd_una = 150;
+  tc->bytes_acked = 150;
+  tc->sack_sb.last_sacked_bytes = 0;
+  tcp_bt_sample_delivery_rate (tc, rs);
+
+  TCP_TEST (tcp_bt_is_sane (bt), "tracker should be sane");
+  TCP_TEST (pool_elts (bt->samples) == 1, "should have 1 sample");
+  TCP_TEST (head != bt->head, "head is updated");
+  head = bt->head;
+  bts = pool_elt_at_index (bt->samples, bt->head);
+  TCP_TEST (bts->min_seq == tc->snd_una, "min seq should be snd_una");
+  TCP_TEST (bts->tx_time == 2, "tx time should be 2");
+
+  /* 4) track another burst at time 4 */
+  /* --> [150:200][200:300] */
+  session_main.wrk[thread_index].last_vlib_time = 4;
+  tcp_bt_track_tx (tc, 100);
+  tc->snd_nxt += 100;
+
+  TCP_TEST (tcp_bt_is_sane (bt), "tracker should be sane");
+  TCP_TEST (pool_elts (bt->samples) == 2, "should have 2 samples");
+  bts = pool_elt_at_index (bt->samples, bt->head);
+  TCP_TEST (head == bt->head, "head is not updated");
+  TCP_TEST (bts->min_seq == tc->snd_una, "min seq should be snd_una");
+  TCP_TEST (bts->tx_time == 2, "tx time of head should be 2");
+
+  /* 5) track another burst at time 5 */
+  /* --> [150:200][200:300][300:400] */
+  session_main.wrk[thread_index].last_vlib_time = 5;
+  tcp_bt_track_tx (tc, 100);
+  tc->snd_nxt += 100;
+
+  TCP_TEST (tcp_bt_is_sane (bt), "tracker should be sane");
+  TCP_TEST (pool_elts (bt->samples) == 3, "should have 3 samples");
+  bts = pool_elt_at_index (bt->samples, bt->head);
+  TCP_TEST (head == bt->head, "head is not updated");
+  TCP_TEST (bts->min_seq == tc->snd_una, "min seq should be snd_una");
+  TCP_TEST (bts->tx_time == 2, "tx time of head should be 2");
+
+  /* 6) acked with SACK option at time 6 */
+  /* ACK:250 + SACK[350:400] */
+  /* --> [250:300][300:350][350:400/sacked] */
+  session_main.wrk[thread_index].last_vlib_time = 6;
+  tc->snd_una = 250;
+  tc->bytes_acked = 100;
+  tc->sack_sb.last_sacked_bytes = 50;
+  vec_add2 (tc->rcv_opts.sacks, blk, 1);
+  blk->start = 350;
+  blk->end = 400;
+  tcp_bt_sample_delivery_rate (tc, rs);
+
+  TCP_TEST (tcp_bt_is_sane (bt), "tracker should be sane");
+  TCP_TEST (pool_elts (bt->samples) == 3, "should have 3 samples");
+  TCP_TEST (head != bt->head, "head is updated");
+  head = bt->head;
+  bts = pool_elt_at_index (bt->samples, bt->head);
+  TCP_TEST (bts->min_seq == tc->snd_una, "min seq should be snd_una");
+  TCP_TEST (bts->tx_time == 4, "tx time of head should be 4");
+  TCP_TEST (!(bts->flags & TCP_BTS_IS_SACKED), "not sacked");
+  bts = pool_elt_at_index (bt->samples, bts->next);
+  TCP_TEST (bts->tx_time == 5, "tx time of next should be 5");
+  TCP_TEST (!(bts->flags & TCP_BTS_IS_SACKED), "not sacked");
+  bts = pool_elt_at_index (bt->samples, bt->tail);
+  TCP_TEST (bts->tx_time == 5, "tx time of tail should be 5");
+  TCP_TEST ((bts->flags & TCP_BTS_IS_SACKED), "sacked");
+
+  /* 7) track another burst at time 7 */
+  /* --> [250:300][300:350][350:400/sacked][400-500] */
+  session_main.wrk[thread_index].last_vlib_time = 7;
+  tcp_bt_track_tx (tc, 100);
+  tc->snd_nxt += 100;
+
+  TCP_TEST (tcp_bt_is_sane (bt), "tracker should be sane");
+  TCP_TEST (pool_elts (bt->samples) == 4, "should have 4 samples");
+  bts = pool_elt_at_index (bt->samples, bt->head);
+  TCP_TEST (head == bt->head, "head is not updated");
+  bts = pool_elt_at_index (bt->samples, bt->head);
+  TCP_TEST (bts->min_seq == tc->snd_una, "min seq should be snd_una");
+  TCP_TEST (bts->tx_time == 4, "tx time of head should be 4");
+  TCP_TEST (!(bts->flags & TCP_BTS_IS_SACKED), "not sacked");
+  bts = pool_elt_at_index (bt->samples, bts->next);
+  TCP_TEST (bts->tx_time == 5, "tx time of next should be 5");
+  TCP_TEST (!(bts->flags & TCP_BTS_IS_SACKED), "not sacked");
+  bts = pool_elt_at_index (bt->samples, bts->next);
+  TCP_TEST (bts->tx_time == 5, "tx time of next should be 5");
+  TCP_TEST ((bts->flags & TCP_BTS_IS_SACKED), "sacked");
+  bts = pool_elt_at_index (bt->samples, bt->tail);
+  TCP_TEST (bts->tx_time == 7, "tx time of tail should be 7");
+  TCP_TEST (!(bts->flags & TCP_BTS_IS_SACKED), "not sacked");
+
+  /* 8) retransmit lost one at time 8 */
+  /* retransmit [250:300] */
+  /* --> [250:300][300:350][350:400/sacked][400-500] */
+  session_main.wrk[thread_index].last_vlib_time = 8;
+  tcp_bt_track_rxt (tc, 250, 300);
+  tcp_bt_sample_delivery_rate (tc, rs);
+
+  TCP_TEST (tcp_bt_is_sane (bt), "tracker should be sane");
+  TCP_TEST (pool_elts (bt->samples) == 4, "should have 4 samples");
+  TCP_TEST (head == bt->head, "head is not updated");
+  bts = pool_elt_at_index (bt->samples, bt->head);
+  TCP_TEST (bts->min_seq == tc->snd_una, "min seq should be snd_una");
+  TCP_TEST (bts->tx_time == 8, "tx time of head should be 8");
+  bts = pool_elt_at_index (bt->samples, bts->next);
+  TCP_TEST (bts->tx_time == 5, "tx time of next should be 5");
+  TCP_TEST (!(bts->flags & TCP_BTS_IS_SACKED), "not sacked");
+  bts = pool_elt_at_index (bt->samples, bts->next);
+  TCP_TEST (bts->tx_time == 5, "tx time of next should be 5");
+  TCP_TEST ((bts->flags & TCP_BTS_IS_SACKED), "sacked");
+  bts = pool_elt_at_index (bt->samples, bt->tail);
+  TCP_TEST (bts->tx_time == 7, "tx time of tail should be 7");
+  TCP_TEST (!(bts->flags & TCP_BTS_IS_SACKED), "not sacked");
+
+  /* 9) acked with SACK option at time 9 */
+  /* ACK:350 + SACK[420:450] */
+  /* --> [400:420][420:450/sacked][450:400] */
+  session_main.wrk[thread_index].last_vlib_time = 6;
+  tc->snd_una = 400;
+  tc->bytes_acked = 150;
+  tc->sack_sb.last_sacked_bytes = 30;
+  vec_add2 (tc->rcv_opts.sacks, blk, 1);
+  blk->start = 420;
+  blk->end = 450;
+  tcp_bt_sample_delivery_rate (tc, rs);
+
+  TCP_TEST (tcp_bt_is_sane (bt), "tracker should be sane");
+  TCP_TEST (pool_elts (bt->samples) == 3, "should have 3 samples");
+  TCP_TEST (head != bt->head, "head is updated");
+  head = bt->head;
+  bts = pool_elt_at_index (bt->samples, bt->head);
+  TCP_TEST (bts->min_seq == tc->snd_una, "min seq should be snd_una");
+  TCP_TEST (bts->min_seq == 400 && bts->max_seq == 420, "bts [400:420]");
+  TCP_TEST (bts->tx_time == 7, "tx time of head should be 7");
+  TCP_TEST (!(bts->flags & TCP_BTS_IS_SACKED), "not sacked");
+  bts = pool_elt_at_index (bt->samples, bts->next);
+  TCP_TEST (bts->min_seq == 420 && bts->max_seq == 450, "bts [420:450]");
+  TCP_TEST (bts->tx_time == 7, "tx time of head should be 7");
+  TCP_TEST ((bts->flags & TCP_BTS_IS_SACKED), "sacked");
+  bts = pool_elt_at_index (bt->samples, bts->next);
+  TCP_TEST (bts->min_seq == 450 && bts->max_seq == 500, "bts [450:500]");
+  TCP_TEST (bts->tx_time == 7, "tx time of head should be 7");
+  TCP_TEST (!(bts->flags & TCP_BTS_IS_SACKED), "not sacked");
+
+  /* 10) acked partially at time 10 */
+  /* ACK:500 */
+  /* --> [] */
+  session_main.wrk[thread_index].last_vlib_time = 3;
+  tc->snd_una = 500;
+  tc->bytes_acked = 100;
+  tc->sack_sb.last_sacked_bytes = 0;
+  tcp_bt_sample_delivery_rate (tc, rs);
+
+  TCP_TEST (tcp_bt_is_sane (bt), "tracker should be sane");
+  TCP_TEST (pool_elts (bt->samples) == 0, "should have 0 samples");
+  TCP_TEST (bt->head == TCP_BTS_INVALID_INDEX, "bt->head is invalidated");
+  TCP_TEST (tc->snd_una == tc->snd_nxt, "snd_una == snd_nxt");
+
+  return 0;
+}
+
 static clib_error_t *
 tcp_test (vlib_main_t * vm,
 	  unformat_input_t * input, vlib_cli_command_t * cmd_arg)
@@ -1355,6 +1566,10 @@ tcp_test (vlib_main_t * vm,
 	{
 	  res = tcp_test_delivery (vm, input);
 	}
+      else if (unformat (input, "bt"))
+	{
+	  res = tcp_test_bt (vm, input);
+	}
       else if (unformat (input, "all"))
 	{
 	  if ((res = tcp_test_sack (vm, input)))
diff --git a/src/vnet/tcp/tcp_bt.c b/src/vnet/tcp/tcp_bt.c
index de2e7ad7f8e..07f86789945 100644
--- a/src/vnet/tcp/tcp_bt.c
+++ b/src/vnet/tcp/tcp_bt.c
@@ -306,6 +306,7 @@ tcp_bt_track_tx (tcp_connection_t * tc, u32 len)
 
   tail = bt_get_sample (bt, bt->tail);
   if (tail && tail->max_seq == tc->snd_nxt
+      && !(tail->flags & TCP_BTS_IS_SACKED)
       && tail->tx_time == tcp_time_now_us (tc->c_thread_index))
     {
       tail->max_seq += len;
@@ -504,7 +505,10 @@ tcp_bt_walk_samples (tcp_connection_t * tc, tcp_rate_sample_t * rs)
     }
 
   if (cur && seq_lt (cur->min_seq, tc->snd_una))
-    tcp_bt_sample_to_rate_sample (tc, cur, rs);
+    {
+      bt_update_sample (bt, cur, tc->snd_una);
+      tcp_bt_sample_to_rate_sample (tc, cur, rs);
+    }
 }
 
 static void