tcp: fix sacks lost bytes counting (VPP-1465)

Change-Id: Ie46b3a81de4ed39b7b40e3879436f7e5a2908d98
Signed-off-by: Florin Coras <fcoras@cisco.com>

2 files changed, 118 insertions, 50 deletions

diff --git a/src/plugins/unittest/tcp_test.c b/src/plugins/unittest/tcp_test.c
index 33a7fd6af0c..92bf0ffd9c4 100644
--- a/src/plugins/unittest/tcp_test.c
+++ b/src/plugins/unittest/tcp_test.c
@@ -89,6 +89,7 @@ tcp_test_sack_rx (vlib_main_t * vm, unformat_input_t * input)
   tc->snd_una_max = 1000;
   tc->snd_nxt = 1000;
   tc->rcv_opts.flags |= TCP_OPTS_FLAG_SACK;
+  tc->snd_mss = 150;
   scoreboard_init (&tc->sack_sb);
 
   for (i = 0; i < 1000 / 100; i++)
@@ -110,8 +111,8 @@ tcp_test_sack_rx (vlib_main_t * vm, unformat_input_t * input)
   tcp_rcv_sacks (tc, 0);
 
   if (verbose)
-    vlib_cli_output (vm, "sb after even blocks:\n%U", format_tcp_scoreboard,
-		     sb);
+    vlib_cli_output (vm, "sb after even blocks (mss %u):\n%U",
+		     tc->snd_mss, format_tcp_scoreboard, sb, tc);
 
   TCP_TEST ((pool_elts (sb->holes) == 5),
 	    "scoreboard has %d elements", pool_elts (sb->holes));
@@ -127,7 +128,9 @@ tcp_test_sack_rx (vlib_main_t * vm, unformat_input_t * input)
   TCP_TEST ((sb->snd_una_adv == 0), "snd_una_adv %u", sb->snd_una_adv);
   TCP_TEST ((sb->last_sacked_bytes == 400),
 	    "last sacked bytes %d", sb->last_sacked_bytes);
-  TCP_TEST ((sb->high_sacked == 900), "max byte sacked %u", sb->high_sacked);
+  TCP_TEST ((sb->high_sacked == 900), "high sacked %u", sb->high_sacked);
+  TCP_TEST ((sb->lost_bytes == 200), "lost bytes %u", sb->lost_bytes);
+
   /*
    * Inject odd blocks
    */
@@ -141,8 +144,8 @@ tcp_test_sack_rx (vlib_main_t * vm, unformat_input_t * input)
   tcp_rcv_sacks (tc, 0);
 
   if (verbose)
-    vlib_cli_output (vm, "sb after odd blocks:\n%U", format_tcp_scoreboard,
-		     sb);
+    vlib_cli_output (vm, "\nsb after odd blocks:\n%U", format_tcp_scoreboard,
+		     sb, tc);
 
   hole = scoreboard_first_hole (sb);
   TCP_TEST ((pool_elts (sb->holes) == 1),
@@ -151,17 +154,18 @@ tcp_test_sack_rx (vlib_main_t * vm, unformat_input_t * input)
 	    "first hole start %u end %u", hole->start, hole->end);
   TCP_TEST ((sb->sacked_bytes == 900), "sacked bytes %d", sb->sacked_bytes);
   TCP_TEST ((sb->snd_una_adv == 0), "snd_una_adv %u", sb->snd_una_adv);
-  TCP_TEST ((sb->high_sacked == 1000), "max sacked byte %u", sb->high_sacked);
+  TCP_TEST ((sb->high_sacked == 1000), "high sacked %u", sb->high_sacked);
   TCP_TEST ((sb->last_sacked_bytes == 500),
 	    "last sacked bytes %d", sb->last_sacked_bytes);
+  TCP_TEST ((sb->lost_bytes == 100), "lost bytes %u", sb->lost_bytes);
 
   /*
    *  Ack until byte 100, all bytes are now acked + sacked
    */
   tcp_rcv_sacks (tc, 100);
   if (verbose)
-    vlib_cli_output (vm, "ack until byte 100:\n%U", format_tcp_scoreboard,
-		     sb);
+    vlib_cli_output (vm, "\nack until byte 100:\n%U", format_tcp_scoreboard,
+		     sb, tc);
 
   TCP_TEST ((pool_elts (sb->holes) == 0),
 	    "scoreboard has %d elements", pool_elts (sb->holes));
@@ -171,6 +175,7 @@ tcp_test_sack_rx (vlib_main_t * vm, unformat_input_t * input)
   TCP_TEST ((sb->sacked_bytes == 0), "sacked bytes %d", sb->sacked_bytes);
   TCP_TEST ((sb->last_sacked_bytes == 0),
 	    "last sacked bytes %d", sb->last_sacked_bytes);
+  TCP_TEST ((sb->lost_bytes == 0), "lost bytes %u", sb->lost_bytes);
 
   /*
    * Add new block
@@ -182,16 +187,14 @@ tcp_test_sack_rx (vlib_main_t * vm, unformat_input_t * input)
   block.end = 1300;
   vec_add1 (tc->rcv_opts.sacks, block);
 
-  if (verbose)
-    vlib_cli_output (vm, "add [1200, 1300]:\n%U", format_tcp_scoreboard, sb);
   tc->snd_una_max = 1500;
   tc->snd_una = 1000;
   tc->snd_nxt = 1500;
   tcp_rcv_sacks (tc, 1000);
 
   if (verbose)
-    vlib_cli_output (vm, "sb snd_una_max 1500, snd_una 1000:\n%U",
-		     format_tcp_scoreboard, sb);
+    vlib_cli_output (vm, "\nadd [1200, 1300] snd_una_max 1500, snd_una 1000:"
+		     " \n%U", format_tcp_scoreboard, sb, tc);
 
   TCP_TEST ((sb->snd_una_adv == 0),
 	    "snd_una_adv after ack %u", sb->snd_una_adv);
@@ -207,6 +210,7 @@ tcp_test_sack_rx (vlib_main_t * vm, unformat_input_t * input)
   TCP_TEST ((hole->start == 1300 && hole->end == 1500),
 	    "last hole start %u end %u", hole->start, hole->end);
   TCP_TEST ((sb->sacked_bytes == 100), "sacked bytes %d", sb->sacked_bytes);
+  TCP_TEST ((sb->lost_bytes == 0), "lost bytes %u", sb->lost_bytes);
 
   /*
    * Ack first hole
@@ -216,19 +220,19 @@ tcp_test_sack_rx (vlib_main_t * vm, unformat_input_t * input)
   tcp_rcv_sacks (tc, 1200);
 
   if (verbose)
-    vlib_cli_output (vm, "sb ack up to byte 1200:\n%U", format_tcp_scoreboard,
-		     sb);
+    vlib_cli_output (vm, "\nsb ack up to byte 1200:\n%U",
+		     format_tcp_scoreboard, sb, tc);
 
   TCP_TEST ((sb->snd_una_adv == 100),
 	    "snd_una_adv after ack %u", sb->snd_una_adv);
   TCP_TEST ((sb->sacked_bytes == 0), "sacked bytes %d", sb->sacked_bytes);
-  TCP_TEST ((pool_elts (sb->holes) == 1),
+  TCP_TEST ((pool_elts (sb->holes) == 0),
 	    "scoreboard has %d elements", pool_elts (sb->holes));
-  hole = scoreboard_first_hole (sb);
-  TCP_TEST ((hole->prev == TCP_INVALID_SACK_HOLE_INDEX
-	     && hole->next == TCP_INVALID_SACK_HOLE_INDEX), "hole is valid");
   TCP_TEST ((sb->last_bytes_delivered == 100), "last bytes delivered %d",
 	    sb->last_bytes_delivered);
+  TCP_TEST ((sb->lost_bytes == 0), "lost bytes %u", sb->lost_bytes);
+  TCP_TEST ((sb->head == TCP_INVALID_SACK_HOLE_INDEX), "head %u", sb->head);
+  TCP_TEST ((sb->tail == TCP_INVALID_SACK_HOLE_INDEX), "tail %u", sb->tail);
 
   /*
    * Add some more blocks and then remove all
@@ -246,7 +250,8 @@ tcp_test_sack_rx (vlib_main_t * vm, unformat_input_t * input)
 
   scoreboard_clear (sb);
   if (verbose)
-    vlib_cli_output (vm, "sb cleared all:\n%U", format_tcp_scoreboard, sb);
+    vlib_cli_output (vm, "\nsb cleared all:\n%U", format_tcp_scoreboard, sb,
+		     tc);
 
   TCP_TEST ((pool_elts (sb->holes) == 0),
 	    "number of holes %d", pool_elts (sb->holes));
@@ -267,14 +272,17 @@ tcp_test_sack_rx (vlib_main_t * vm, unformat_input_t * input)
   tc->rcv_opts.n_sack_blocks = vec_len (tc->rcv_opts.sacks);
   tcp_rcv_sacks (tc, 0);
   if (verbose)
-    vlib_cli_output (vm, "sb added odd blocks and ack [0, 950]:\n%U",
-		     format_tcp_scoreboard, sb);
+    vlib_cli_output (vm, "\nsb added odd blocks snd_una 0 snd_una_max 1500:"
+		     "\n%U", format_tcp_scoreboard, sb, tc);
+  TCP_TEST ((pool_elts (sb->holes) == 5),
+	    "scoreboard has %d elements", pool_elts (sb->holes));
+  TCP_TEST ((sb->lost_bytes == 200), "lost bytes %u", sb->lost_bytes);
 
   tcp_rcv_sacks (tc, 950);
 
   if (verbose)
-    vlib_cli_output (vm, "sb added odd blocks and ack [0, 950]:\n%U",
-		     format_tcp_scoreboard, sb);
+    vlib_cli_output (vm, "\nack [0, 950]:\n%U", format_tcp_scoreboard, sb,
+		     tc);
 
   TCP_TEST ((pool_elts (sb->holes) == 0),
 	    "scoreboard has %d elements", pool_elts (sb->holes));
@@ -282,6 +290,7 @@ tcp_test_sack_rx (vlib_main_t * vm, unformat_input_t * input)
   TCP_TEST ((sb->sacked_bytes == 0), "sacked bytes %d", sb->sacked_bytes);
   TCP_TEST ((sb->last_sacked_bytes == 0),
 	    "last sacked bytes %d", sb->last_sacked_bytes);
+  TCP_TEST ((sb->lost_bytes == 0), "lost bytes %u", sb->lost_bytes);
 
   /*
    * Inject one block, ack it and overlap hole
@@ -299,22 +308,26 @@ tcp_test_sack_rx (vlib_main_t * vm, unformat_input_t * input)
   tcp_rcv_sacks (tc, 0);
 
   if (verbose)
-    vlib_cli_output (vm, "sb added [100, 500]:\n%U",
-		     format_tcp_scoreboard, sb);
+    vlib_cli_output (vm, "\nsb added [100, 500] snd_una 0 snd_una_max 1000:"
+		     "\n%U", format_tcp_scoreboard, sb, tc);
 
   tcp_rcv_sacks (tc, 800);
 
   if (verbose)
-    vlib_cli_output (vm, "sb ack [0, 800]:\n%U", format_tcp_scoreboard, sb);
+    vlib_cli_output (vm, "\nsb ack [0, 800]:\n%U", format_tcp_scoreboard, sb,
+		     tc);
 
-  TCP_TEST ((pool_elts (sb->holes) == 1),
+  TCP_TEST ((pool_elts (sb->holes) == 0),
 	    "scoreboard has %d elements", pool_elts (sb->holes));
   TCP_TEST ((sb->snd_una_adv == 0), "snd_una_adv %u", sb->snd_una_adv);
   TCP_TEST ((sb->sacked_bytes == 0), "sacked bytes %d", sb->sacked_bytes);
-  TCP_TEST ((sb->last_sacked_bytes == 0),
-	    "last sacked bytes %d", sb->last_sacked_bytes);
+  TCP_TEST ((sb->last_sacked_bytes == 0), "last sacked bytes %d",
+	    sb->last_sacked_bytes);
   TCP_TEST ((sb->last_bytes_delivered == 400),
 	    "last bytes delivered %d", sb->last_bytes_delivered);
+  TCP_TEST ((sb->lost_bytes == 0), "lost bytes %u", sb->lost_bytes);
+  TCP_TEST ((sb->head == TCP_INVALID_SACK_HOLE_INDEX), "head %u", sb->head);
+  TCP_TEST ((sb->tail == TCP_INVALID_SACK_HOLE_INDEX), "tail %u", sb->tail);
 
   /*
    * One hole close to head, patch head, split in two and start acking
@@ -332,8 +345,12 @@ tcp_test_sack_rx (vlib_main_t * vm, unformat_input_t * input)
 
   tcp_rcv_sacks (tc, 0);
   if (verbose)
-    vlib_cli_output (vm, "sb added [500, 1000]:\n%U",
-		     format_tcp_scoreboard, sb);
+    vlib_cli_output (vm, "\nsb added [500, 1000]:\n%U",
+		     format_tcp_scoreboard, sb, tc);
+  TCP_TEST ((sb->sacked_bytes == 500), "sacked bytes %d", sb->sacked_bytes);
+  TCP_TEST ((sb->last_sacked_bytes == 500), "last sacked bytes %d",
+	    sb->last_sacked_bytes);
+  TCP_TEST ((sb->lost_bytes == 500), "lost bytes %u", sb->lost_bytes);
 
   vec_reset_length (tc->rcv_opts.sacks);
   block.start = 300;
@@ -342,18 +359,57 @@ tcp_test_sack_rx (vlib_main_t * vm, unformat_input_t * input)
   tc->rcv_opts.n_sack_blocks = vec_len (tc->rcv_opts.sacks);
   tcp_rcv_sacks (tc, 100);
   if (verbose)
-    vlib_cli_output (vm, "sb added [0, 100] [300, 400]:\n%U",
-		     format_tcp_scoreboard, sb);
+    vlib_cli_output (vm, "\nsb added [0, 100] [300, 400]:\n%U",
+		     format_tcp_scoreboard, sb, tc);
   TCP_TEST ((pool_elts (sb->holes) == 2),
 	    "scoreboard has %d elements", pool_elts (sb->holes));
+  TCP_TEST ((sb->sacked_bytes == 600), "sacked bytes %d", sb->sacked_bytes);
+  TCP_TEST ((sb->last_sacked_bytes == 100), "last sacked bytes %d",
+	    sb->last_sacked_bytes);
+  TCP_TEST ((sb->last_bytes_delivered == 0), "last bytes delivered %d",
+	    sb->last_bytes_delivered);
+  TCP_TEST ((sb->lost_bytes == 200), "lost bytes %u", sb->lost_bytes);
 
   tc->snd_una = 100;
   tcp_rcv_sacks (tc, 200);
+  tc->snd_una = 200;
   tcp_rcv_sacks (tc, 300);
   if (verbose)
-    vlib_cli_output (vm, "sb added [0, 300]:\n%U", format_tcp_scoreboard, sb);
+    vlib_cli_output (vm, "\nacked [0, 300] in two steps:\n%U",
+		     format_tcp_scoreboard, sb, tc);
   TCP_TEST ((sb->sacked_bytes == 500), "sacked bytes %d", sb->sacked_bytes);
+  TCP_TEST ((sb->lost_bytes == 100), "lost bytes %u", sb->lost_bytes);
+  TCP_TEST ((sb->last_bytes_delivered == 100), "last bytes delivered %d",
+	    sb->last_bytes_delivered);
 
+  tc->snd_una = 400;
+  tcp_rcv_sacks (tc, 500);
+  if (verbose)
+    vlib_cli_output (vm, "\nacked [400, 500]:\n%U", format_tcp_scoreboard, sb,
+		     tc);
+  TCP_TEST ((pool_elts (sb->holes) == 0),
+	    "scoreboard has %d elements", pool_elts (sb->holes));
+  TCP_TEST ((sb->sacked_bytes == 0), "sacked bytes %d", sb->sacked_bytes);
+  TCP_TEST ((sb->last_sacked_bytes == 0), "last sacked bytes %d",
+	    sb->last_sacked_bytes);
+  TCP_TEST ((sb->last_bytes_delivered == 500), "last bytes delivered %d",
+	    sb->last_bytes_delivered);
+  TCP_TEST ((sb->lost_bytes == 0), "lost bytes %u", sb->lost_bytes);
+  TCP_TEST ((sb->snd_una_adv == 500), "snd_una_adv %u", sb->snd_una_adv);
+  TCP_TEST ((sb->head == TCP_INVALID_SACK_HOLE_INDEX), "head %u", sb->head);
+  TCP_TEST ((sb->tail == TCP_INVALID_SACK_HOLE_INDEX), "tail %u", sb->tail);
+
+  /*
+   * Re-ack high sacked, to make sure last_bytes_delivered and
+   * snd_una_adv are 0-ed
+   */
+  tcp_rcv_sacks (tc, 1000);
+  if (verbose)
+    vlib_cli_output (vm, "\nAck high sacked:\n%U", format_tcp_scoreboard, sb,
+		     tc);
+  TCP_TEST ((sb->last_bytes_delivered == 0), "last bytes delivered %d",
+	    sb->last_bytes_delivered);
+  TCP_TEST ((sb->snd_una_adv == 0), "snd_una_adv %u", sb->snd_una_adv);
   return 0;
 }
 
diff --git a/src/vnet/tcp/tcp_input.c b/src/vnet/tcp/tcp_input.c
index 85aaa16f245..19012578c6b 100644
--- a/src/vnet/tcp/tcp_input.c
+++ b/src/vnet/tcp/tcp_input.c
@@ -667,38 +667,41 @@ scoreboard_insert_hole (sack_scoreboard_t * sb, u32 prev_index,
 static void
 scoreboard_update_bytes (tcp_connection_t * tc, sack_scoreboard_t * sb)
 {
-  sack_scoreboard_hole_t *hole, *prev;
+  sack_scoreboard_hole_t *left, *right;
   u32 bytes = 0, blks = 0;
 
   sb->lost_bytes = 0;
   sb->sacked_bytes = 0;
-  hole = scoreboard_last_hole (sb);
-  if (!hole)
+  left = scoreboard_last_hole (sb);
+  if (!left)
     return;
 
-  if (seq_gt (sb->high_sacked, hole->end))
+  if (seq_gt (sb->high_sacked, left->end))
     {
-      bytes = sb->high_sacked - hole->end;
+      bytes = sb->high_sacked - left->end;
       blks = 1;
+      if (bytes > (TCP_DUPACK_THRESHOLD - 1) * tc->snd_mss
+	  && left->prev == TCP_INVALID_SACK_HOLE_INDEX)
+	sb->lost_bytes += scoreboard_hole_bytes (left);
     }
 
-  while ((prev = scoreboard_prev_hole (sb, hole))
+  right = left;
+  while ((left = scoreboard_prev_hole (sb, right))
 	 && (bytes < (TCP_DUPACK_THRESHOLD - 1) * tc->snd_mss
 	     && blks < TCP_DUPACK_THRESHOLD))
     {
-      bytes += hole->start - prev->end;
+      bytes += right->start - left->end;
       blks++;
-      hole = prev;
+      right = left;
     }
 
-  while (hole)
+  while (left)
     {
-      sb->lost_bytes += scoreboard_hole_bytes (hole);
-      hole->is_lost = 1;
-      prev = hole;
-      hole = scoreboard_prev_hole (sb, hole);
-      if (hole)
-	bytes += prev->start - hole->end;
+      bytes += right->start - left->end;
+      sb->lost_bytes += scoreboard_hole_bytes (left);
+      left->is_lost = 1;
+      right = left;
+      left = scoreboard_prev_hole (sb, left);
     }
   sb->sacked_bytes = bytes;
 }
@@ -815,7 +818,8 @@ tcp_scoreboard_is_sane_post_recovery (tcp_connection_t * tc)
 {
   sack_scoreboard_hole_t *hole;
   hole = scoreboard_first_hole (&tc->sack_sb);
-  return (!hole || seq_geq (hole->start, tc->snd_una));
+  return (!hole || (seq_geq (hole->start, tc->snd_una)
+		    && seq_lt (hole->end, tc->snd_una_max)));
 }
 
 void
@@ -974,6 +978,14 @@ tcp_rcv_sacks (tcp_connection_t * tc, u32 ack)
 	}
     }
 
+  if (pool_elts (sb->holes) == 1)
+    {
+      hole = scoreboard_first_hole (sb);
+      if (hole->start == ack + sb->snd_una_adv
+	  && hole->end == tc->snd_una_max)
+	scoreboard_remove_hole (sb, hole);
+    }
+
   scoreboard_update_bytes (tc, sb);
   sb->last_sacked_bytes = sb->sacked_bytes
     - (old_sacked_bytes - sb->last_bytes_delivered);