src/vnet/tcp/tcp_sack.c

   1 /*
   2  * Copyright (c) 2020 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
  16 #include <vnet/tcp/tcp_sack.h>
  17
  18 static void
  19 scoreboard_remove_hole (sack_scoreboard_t * sb, sack_scoreboard_hole_t * hole)
  20 {
  21   sack_scoreboard_hole_t *next, *prev;
  22
  23   if (hole->next != TCP_INVALID_SACK_HOLE_INDEX)
  24     {
  25       next = pool_elt_at_index (sb->holes, hole->next);
  26       next->prev = hole->prev;
  27     }
  28   else
  29     {
  30       sb->tail = hole->prev;
  31     }
  32
  33   if (hole->prev != TCP_INVALID_SACK_HOLE_INDEX)
  34     {
  35       prev = pool_elt_at_index (sb->holes, hole->prev);
  36       prev->next = hole->next;
  37     }
  38   else
  39     {
  40       sb->head = hole->next;
  41     }
  42
  43   if (scoreboard_hole_index (sb, hole) == sb->cur_rxt_hole)
  44     sb->cur_rxt_hole = TCP_INVALID_SACK_HOLE_INDEX;
  45
  46   /* Poison the entry */
  47   if (CLIB_DEBUG > 0)
  48     clib_memset (hole, 0xfe, sizeof (*hole));
  49
  50   pool_put (sb->holes, hole);
  51 }
  52
  53 static sack_scoreboard_hole_t *
  54 scoreboard_insert_hole (sack_scoreboard_t * sb, u32 prev_index,
  55                         u32 start, u32 end)
  56 {
  57   sack_scoreboard_hole_t *hole, *next, *prev;
  58   u32 hole_index;
  59
  60   pool_get (sb->holes, hole);
  61   clib_memset (hole, 0, sizeof (*hole));
  62
  63   hole->start = start;
  64   hole->end = end;
  65   hole_index = scoreboard_hole_index (sb, hole);
  66
  67   prev = scoreboard_get_hole (sb, prev_index);
  68   if (prev)
  69     {
  70       hole->prev = prev_index;
  71       hole->next = prev->next;
  72
  73       if ((next = scoreboard_next_hole (sb, hole)))
  74         next->prev = hole_index;
  75       else
  76         sb->tail = hole_index;
  77
  78       prev->next = hole_index;
  79     }
  80   else
  81     {
  82       sb->head = hole_index;
  83       hole->prev = TCP_INVALID_SACK_HOLE_INDEX;
  84       hole->next = TCP_INVALID_SACK_HOLE_INDEX;
  85     }
  86
  87   return hole;
  88 }
  89
  90 always_inline void
  91 scoreboard_update_sacked_rxt (sack_scoreboard_t * sb, u32 start, u32 end,
  92                               u8 has_rxt)
  93 {
  94   if (!has_rxt || seq_geq (start, sb->high_rxt))
  95     return;
  96
  97   sb->rxt_sacked +=
  98     seq_lt (end, sb->high_rxt) ? (end - start) : (sb->high_rxt - start);
  99 }
 100
 101 always_inline void
 102 scoreboard_update_bytes (sack_scoreboard_t * sb, u32 ack, u32 snd_mss)
 103 {
 104   sack_scoreboard_hole_t *left, *right;
 105   u32 sacked = 0, blks = 0, old_sacked;
 106
 107   old_sacked = sb->sacked_bytes;
 108
 109   sb->last_lost_bytes = 0;
 110   sb->lost_bytes = 0;
 111   sb->sacked_bytes = 0;
 112
 113   right = scoreboard_last_hole (sb);
 114   if (!right)
 115     {
 116       sb->sacked_bytes = sb->high_sacked - ack;
 117       sb->last_sacked_bytes = sb->sacked_bytes
 118         - (old_sacked - sb->last_bytes_delivered);
 119       return;
 120     }
 121
 122   if (seq_gt (sb->high_sacked, right->end))
 123     {
 124       sacked = sb->high_sacked - right->end;
 125       blks = 1;
 126     }
 127
 128   while (sacked < (TCP_DUPACK_THRESHOLD - 1) * snd_mss
 129          && blks < TCP_DUPACK_THRESHOLD)
 130     {
 131       if (right->is_lost)
 132         sb->lost_bytes += scoreboard_hole_bytes (right);
 133
 134       left = scoreboard_prev_hole (sb, right);
 135       if (!left)
 136         {
 137           ASSERT (right->start == ack || sb->is_reneging);
 138           sacked += right->start - ack;
 139           right = 0;
 140           break;
 141         }
 142
 143       sacked += right->start - left->end;
 144       blks++;
 145       right = left;
 146     }
 147
 148   /* right is first lost */
 149   while (right)
 150     {
 151       sb->lost_bytes += scoreboard_hole_bytes (right);
 152       sb->last_lost_bytes += right->is_lost ? 0 : (right->end - right->start);
 153       right->is_lost = 1;
 154       left = scoreboard_prev_hole (sb, right);
 155       if (!left)
 156         {
 157           ASSERT (right->start == ack || sb->is_reneging);
 158           sacked += right->start - ack;
 159           break;
 160         }
 161       sacked += right->start - left->end;
 162       right = left;
 163     }
 164
 165   sb->sacked_bytes = sacked;
 166   sb->last_sacked_bytes = sacked - (old_sacked - sb->last_bytes_delivered);
 167 }
 168
 169 /**
 170  * Figure out the next hole to retransmit
 171  *
 172  * Follows logic proposed in RFC6675 Sec. 4, NextSeg()
 173  */
 174 sack_scoreboard_hole_t *
 175 scoreboard_next_rxt_hole (sack_scoreboard_t * sb,
 176                           sack_scoreboard_hole_t * start,
 177                           u8 have_unsent, u8 * can_rescue, u8 * snd_limited)
 178 {
 179   sack_scoreboard_hole_t *hole = 0;
 180
 181   hole = start ? start : scoreboard_first_hole (sb);
 182   while (hole && seq_leq (hole->end, sb->high_rxt) && hole->is_lost)
 183     hole = scoreboard_next_hole (sb, hole);
 184
 185   /* Nothing, return */
 186   if (!hole)
 187     {
 188       sb->cur_rxt_hole = TCP_INVALID_SACK_HOLE_INDEX;
 189       return 0;
 190     }
 191
 192   /* Rule (1): if higher than rxt, less than high_sacked and lost */
 193   if (hole->is_lost && seq_lt (hole->start, sb->high_sacked))
 194     {
 195       sb->cur_rxt_hole = scoreboard_hole_index (sb, hole);
 196     }
 197   else
 198     {
 199       /* Rule (2): available unsent data */
 200       if (have_unsent)
 201         {
 202           sb->cur_rxt_hole = TCP_INVALID_SACK_HOLE_INDEX;
 203           return 0;
 204         }
 205       /* Rule (3): if hole not lost */
 206       else if (seq_lt (hole->start, sb->high_sacked))
 207         {
 208           /* And we didn't already retransmit it */
 209           if (seq_leq (hole->end, sb->high_rxt))
 210             {
 211               sb->cur_rxt_hole = TCP_INVALID_SACK_HOLE_INDEX;
 212               return 0;
 213             }
 214           *snd_limited = 0;
 215           sb->cur_rxt_hole = scoreboard_hole_index (sb, hole);
 216         }
 217       /* Rule (4): if hole beyond high_sacked */
 218       else
 219         {
 220           ASSERT (seq_geq (hole->start, sb->high_sacked));
 221           *snd_limited = 1;
 222           *can_rescue = 1;
 223           /* HighRxt MUST NOT be updated */
 224           return 0;
 225         }
 226     }
 227
 228   if (hole && seq_lt (sb->high_rxt, hole->start))
 229     sb->high_rxt = hole->start;
 230
 231   return hole;
 232 }
 233
 234 void
 235 scoreboard_init_rxt (sack_scoreboard_t * sb, u32 snd_una)
 236 {
 237   sack_scoreboard_hole_t *hole;
 238   hole = scoreboard_first_hole (sb);
 239   if (hole)
 240     {
 241       snd_una = seq_gt (snd_una, hole->start) ? snd_una : hole->start;
 242       sb->cur_rxt_hole = sb->head;
 243     }
 244   sb->high_rxt = snd_una;
 245   sb->rescue_rxt = snd_una - 1;
 246 }
 247
 248 void
 249 scoreboard_init (sack_scoreboard_t * sb)
 250 {
 251   sb->head = TCP_INVALID_SACK_HOLE_INDEX;
 252   sb->tail = TCP_INVALID_SACK_HOLE_INDEX;
 253   sb->cur_rxt_hole = TCP_INVALID_SACK_HOLE_INDEX;
 254 }
 255
 256 void
 257 scoreboard_clear (sack_scoreboard_t * sb)
 258 {
 259   sack_scoreboard_hole_t *hole;
 260   while ((hole = scoreboard_first_hole (sb)))
 261     {
 262       scoreboard_remove_hole (sb, hole);
 263     }
 264   ASSERT (sb->head == sb->tail && sb->head == TCP_INVALID_SACK_HOLE_INDEX);
 265   ASSERT (pool_elts (sb->holes) == 0);
 266   sb->sacked_bytes = 0;
 267   sb->last_sacked_bytes = 0;
 268   sb->last_bytes_delivered = 0;
 269   sb->lost_bytes = 0;
 270   sb->last_lost_bytes = 0;
 271   sb->cur_rxt_hole = TCP_INVALID_SACK_HOLE_INDEX;
 272   sb->is_reneging = 0;
 273 }
 274
 275 void
 276 scoreboard_clear_reneging (sack_scoreboard_t * sb, u32 start, u32 end)
 277 {
 278   sack_scoreboard_hole_t *last_hole;
 279
 280   scoreboard_clear (sb);
 281   last_hole = scoreboard_insert_hole (sb, TCP_INVALID_SACK_HOLE_INDEX,
 282                                       start, end);
 283   last_hole->is_lost = 1;
 284   sb->tail = scoreboard_hole_index (sb, last_hole);
 285   sb->high_sacked = start;
 286   scoreboard_init_rxt (sb, start);
 287 }
 288
 289 /**
 290  * Test that scoreboard is sane after recovery
 291  *
 292  * Returns 1 if scoreboard is empty or if first hole beyond
 293  * snd_una.
 294  */
 295 u8
 296 tcp_scoreboard_is_sane_post_recovery (tcp_connection_t * tc)
 297 {
 298   sack_scoreboard_hole_t *hole;
 299   hole = scoreboard_first_hole (&tc->sack_sb);
 300   return (!hole || (seq_geq (hole->start, tc->snd_una)
 301                     && seq_lt (hole->end, tc->snd_nxt)));
 302 }
 303
 304 void
 305 tcp_rcv_sacks (tcp_connection_t * tc, u32 ack)
 306 {
 307   sack_scoreboard_hole_t *hole, *next_hole;
 308   sack_scoreboard_t *sb = &tc->sack_sb;
 309   sack_block_t *blk, *rcv_sacks;
 310   u32 blk_index = 0, i, j;
 311   u8 has_rxt;
 312
 313   sb->last_sacked_bytes = 0;
 314   sb->last_bytes_delivered = 0;
 315   sb->rxt_sacked = 0;
 316
 317   if (!tcp_opts_sack (&tc->rcv_opts) && !sb->sacked_bytes
 318       && sb->head == TCP_INVALID_SACK_HOLE_INDEX)
 319     return;
 320
 321   has_rxt = tcp_in_cong_recovery (tc);
 322
 323   /* Remove invalid blocks */
 324   blk = tc->rcv_opts.sacks;
 325   while (blk < vec_end (tc->rcv_opts.sacks))
 326     {
 327       if (seq_lt (blk->start, blk->end)
 328           && seq_gt (blk->start, tc->snd_una)
 329           && seq_gt (blk->start, ack) && seq_leq (blk->end, tc->snd_nxt))
 330         {
 331           blk++;
 332           continue;
 333         }
 334       vec_del1 (tc->rcv_opts.sacks, blk - tc->rcv_opts.sacks);
 335     }
 336
 337   /* Add block for cumulative ack */
 338   if (seq_gt (ack, tc->snd_una))
 339     {
 340       vec_add2 (tc->rcv_opts.sacks, blk, 1);
 341       blk->start = tc->snd_una;
 342       blk->end = ack;
 343     }
 344
 345   if (vec_len (tc->rcv_opts.sacks) == 0)
 346     return;
 347
 348   tcp_scoreboard_trace_add (tc, ack);
 349
 350   /* Make sure blocks are ordered */
 351   rcv_sacks = tc->rcv_opts.sacks;
 352   for (i = 0; i < vec_len (rcv_sacks); i++)
 353     for (j = i + 1; j < vec_len (rcv_sacks); j++)
 354       if (seq_lt (rcv_sacks[j].start, rcv_sacks[i].start))
 355         {
 356           sack_block_t tmp = rcv_sacks[i];
 357           rcv_sacks[i] = rcv_sacks[j];
 358           rcv_sacks[j] = tmp;
 359         }
 360
 361   if (sb->head == TCP_INVALID_SACK_HOLE_INDEX)
 362     {
 363       /* Handle reneging as a special case */
 364       if (PREDICT_FALSE (sb->is_reneging))
 365         {
 366           /* No holes, only sacked bytes */
 367           if (seq_leq (tc->snd_nxt, sb->high_sacked))
 368             {
 369               /* No progress made so return */
 370               if (seq_leq (ack, tc->snd_una))
 371                 return;
 372
 373               /* Update sacked bytes delivered and return */
 374               sb->last_bytes_delivered = ack - tc->snd_una;
 375               sb->sacked_bytes -= sb->last_bytes_delivered;
 376               sb->is_reneging = seq_lt (ack, sb->high_sacked);
 377               return;
 378             }
 379
 380           /* New hole above high sacked. Add it and process normally */
 381           hole = scoreboard_insert_hole (sb, TCP_INVALID_SACK_HOLE_INDEX,
 382                                          sb->high_sacked, tc->snd_nxt);
 383           sb->tail = scoreboard_hole_index (sb, hole);
 384         }
 385       /* Not reneging and no holes. Insert the first that covers all
 386        * outstanding bytes */
 387       else
 388         {
 389           hole = scoreboard_insert_hole (sb, TCP_INVALID_SACK_HOLE_INDEX,
 390                                          tc->snd_una, tc->snd_nxt);
 391           sb->tail = scoreboard_hole_index (sb, hole);
 392         }
 393       sb->high_sacked = rcv_sacks[vec_len (rcv_sacks) - 1].end;
 394     }
 395   else
 396     {
 397       /* If we have holes but snd_nxt is beyond the last hole, update
 398        * last hole end or add new hole after high sacked */
 399       hole = scoreboard_last_hole (sb);
 400       if (seq_gt (tc->snd_nxt, hole->end))
 401         {
 402           if (seq_geq (hole->start, sb->high_sacked))
 403             {
 404               hole->end = tc->snd_nxt;
 405             }
 406           /* New hole after high sacked block */
 407           else if (seq_lt (sb->high_sacked, tc->snd_nxt))
 408             {
 409               scoreboard_insert_hole (sb, sb->tail, sb->high_sacked,
 410                                       tc->snd_nxt);
 411             }
 412         }
 413
 414       /* Keep track of max byte sacked for when the last hole
 415        * is acked */
 416       sb->high_sacked = seq_max (rcv_sacks[vec_len (rcv_sacks) - 1].end,
 417                                  sb->high_sacked);
 418     }
 419
 420   /* Walk the holes with the SACK blocks */
 421   hole = pool_elt_at_index (sb->holes, sb->head);
 422
 423   if (PREDICT_FALSE (sb->is_reneging))
 424     {
 425       sb->last_bytes_delivered += clib_min (hole->start - tc->snd_una,
 426                                             ack - tc->snd_una);
 427       sb->is_reneging = seq_lt (ack, hole->start);
 428     }
 429
 430   while (hole && blk_index < vec_len (rcv_sacks))
 431     {
 432       blk = &rcv_sacks[blk_index];
 433       if (seq_leq (blk->start, hole->start))
 434         {
 435           /* Block covers hole. Remove hole */
 436           if (seq_geq (blk->end, hole->end))
 437             {
 438               next_hole = scoreboard_next_hole (sb, hole);
 439
 440               /* If covered by ack, compute delivered bytes */
 441               if (blk->end == ack)
 442                 {
 443                   u32 sacked = next_hole ? next_hole->start : sb->high_sacked;
 444                   if (PREDICT_FALSE (seq_lt (ack, sacked)))
 445                     {
 446                       sb->last_bytes_delivered += ack - hole->end;
 447                       sb->is_reneging = 1;
 448                     }
 449                   else
 450                     {
 451                       sb->last_bytes_delivered += sacked - hole->end;
 452                       sb->is_reneging = 0;
 453                     }
 454                 }
 455               scoreboard_update_sacked_rxt (sb, hole->start, hole->end,
 456                                             has_rxt);
 457               scoreboard_remove_hole (sb, hole);
 458               hole = next_hole;
 459             }
 460           /* Partial 'head' overlap */
 461           else
 462             {
 463               if (seq_gt (blk->end, hole->start))
 464                 {
 465                   scoreboard_update_sacked_rxt (sb, hole->start, blk->end,
 466                                                 has_rxt);
 467                   hole->start = blk->end;
 468                 }
 469               blk_index++;
 470             }
 471         }
 472       else
 473         {
 474           /* Hole must be split */
 475           if (seq_lt (blk->end, hole->end))
 476             {
 477               u32 hole_index = scoreboard_hole_index (sb, hole);
 478               next_hole = scoreboard_insert_hole (sb, hole_index, blk->end,
 479                                                   hole->end);
 480               /* Pool might've moved */
 481               hole = scoreboard_get_hole (sb, hole_index);
 482               hole->end = blk->start;
 483
 484               scoreboard_update_sacked_rxt (sb, blk->start, blk->end,
 485                                             has_rxt);
 486
 487               blk_index++;
 488               ASSERT (hole->next == scoreboard_hole_index (sb, next_hole));
 489             }
 490           else if (seq_lt (blk->start, hole->end))
 491             {
 492               scoreboard_update_sacked_rxt (sb, blk->start, hole->end,
 493                                             has_rxt);
 494               hole->end = blk->start;
 495             }
 496           hole = scoreboard_next_hole (sb, hole);
 497         }
 498     }
 499
 500   scoreboard_update_bytes (sb, ack, tc->snd_mss);
 501
 502   ASSERT (sb->last_sacked_bytes <= sb->sacked_bytes || tcp_in_recovery (tc));
 503   ASSERT (sb->sacked_bytes == 0 || tcp_in_recovery (tc)
 504           || sb->sacked_bytes <= tc->snd_nxt - seq_max (tc->snd_una, ack));
 505   ASSERT (sb->last_sacked_bytes + sb->lost_bytes <= tc->snd_nxt
 506           - seq_max (tc->snd_una, ack) || tcp_in_recovery (tc));
 507   ASSERT (sb->head == TCP_INVALID_SACK_HOLE_INDEX || tcp_in_recovery (tc)
 508           || sb->is_reneging || sb->holes[sb->head].start == ack);
 509   ASSERT (sb->last_lost_bytes <= sb->lost_bytes);
 510   ASSERT ((ack - tc->snd_una) + sb->last_sacked_bytes
 511           - sb->last_bytes_delivered >= sb->rxt_sacked);
 512   ASSERT ((ack - tc->snd_una) >= tc->sack_sb.last_bytes_delivered
 513           || (tc->flags & TCP_CONN_FINSNT));
 514
 515   TCP_EVT (TCP_EVT_CC_SCOREBOARD, tc);
 516 }
 517
 518 static u8
 519 tcp_sack_vector_is_sane (sack_block_t * sacks)
 520 {
 521   int i;
 522   for (i = 1; i < vec_len (sacks); i++)
 523     {
 524       if (sacks[i - 1].end == sacks[i].start)
 525         return 0;
 526     }
 527   return 1;
 528 }
 529
 530 /**
 531  * Build SACK list as per RFC2018.
 532  *
 533  * Makes sure the first block contains the segment that generated the current
 534  * ACK and the following ones are the ones most recently reported in SACK
 535  * blocks.
 536  *
 537  * @param tc TCP connection for which the SACK list is updated
 538  * @param start Start sequence number of the newest SACK block
 539  * @param end End sequence of the newest SACK block
 540  */
 541 void
 542 tcp_update_sack_list (tcp_connection_t * tc, u32 start, u32 end)
 543 {
 544   sack_block_t *new_list = tc->snd_sacks_fl, *block = 0;
 545   int i;
 546
 547   /* If the first segment is ooo add it to the list. Last write might've moved
 548    * rcv_nxt over the first segment. */
 549   if (seq_lt (tc->rcv_nxt, start))
 550     {
 551       vec_add2 (new_list, block, 1);
 552       block->start = start;
 553       block->end = end;
 554     }
 555
 556   /* Find the blocks still worth keeping. */
 557   for (i = 0; i < vec_len (tc->snd_sacks); i++)
 558     {
 559       /* Discard if rcv_nxt advanced beyond current block */
 560       if (seq_leq (tc->snd_sacks[i].start, tc->rcv_nxt))
 561         continue;
 562
 563       /* Merge or drop if segment overlapped by the new segment */
 564       if (block && (seq_geq (tc->snd_sacks[i].end, new_list[0].start)
 565                     && seq_leq (tc->snd_sacks[i].start, new_list[0].end)))
 566         {
 567           if (seq_lt (tc->snd_sacks[i].start, new_list[0].start))
 568             new_list[0].start = tc->snd_sacks[i].start;
 569           if (seq_lt (new_list[0].end, tc->snd_sacks[i].end))
 570             new_list[0].end = tc->snd_sacks[i].end;
 571           continue;
 572         }
 573
 574       /* Save to new SACK list if we have space. */
 575       if (vec_len (new_list) < TCP_MAX_SACK_BLOCKS)
 576         vec_add1 (new_list, tc->snd_sacks[i]);
 577     }
 578
 579   ASSERT (vec_len (new_list) <= TCP_MAX_SACK_BLOCKS);
 580
 581   /* Replace old vector with new one */
 582   vec_reset_length (tc->snd_sacks);
 583   tc->snd_sacks_fl = tc->snd_sacks;
 584   tc->snd_sacks = new_list;
 585
 586   /* Segments should not 'touch' */
 587   ASSERT (tcp_sack_vector_is_sane (tc->snd_sacks));
 588 }
 589
 590 u32
 591 tcp_sack_list_bytes (tcp_connection_t * tc)
 592 {
 593   u32 bytes = 0, i;
 594   for (i = 0; i < vec_len (tc->snd_sacks); i++)
 595     bytes += tc->snd_sacks[i].end - tc->snd_sacks[i].start;
 596   return bytes;
 597 }
 598
 599 /*
 600  * fd.io coding-style-patch-verification: ON
 601  *
 602  * Local Variables:
 603  * eval: (c-set-style "gnu")
 604  * End:
 605  */