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   clib_warning ("sack reneging");
 281
 282   scoreboard_clear (sb);
 283   last_hole = scoreboard_insert_hole (sb, TCP_INVALID_SACK_HOLE_INDEX,
 284                                       start, end);
 285   last_hole->is_lost = 1;
 286   sb->tail = scoreboard_hole_index (sb, last_hole);
 287   sb->high_sacked = start;
 288   scoreboard_init_rxt (sb, start);
 289 }
 290
 291 /**
 292  * Test that scoreboard is sane after recovery
 293  *
 294  * Returns 1 if scoreboard is empty or if first hole beyond
 295  * snd_una.
 296  */
 297 u8
 298 tcp_scoreboard_is_sane_post_recovery (tcp_connection_t * tc)
 299 {
 300   sack_scoreboard_hole_t *hole;
 301   hole = scoreboard_first_hole (&tc->sack_sb);
 302   return (!hole || (seq_geq (hole->start, tc->snd_una)
 303                     && seq_lt (hole->end, tc->snd_nxt)));
 304 }
 305
 306 void
 307 tcp_rcv_sacks (tcp_connection_t * tc, u32 ack)
 308 {
 309   sack_scoreboard_hole_t *hole, *next_hole;
 310   sack_scoreboard_t *sb = &tc->sack_sb;
 311   sack_block_t *blk, *rcv_sacks;
 312   u32 blk_index = 0, i, j;
 313   u8 has_rxt;
 314
 315   sb->last_sacked_bytes = 0;
 316   sb->last_bytes_delivered = 0;
 317   sb->rxt_sacked = 0;
 318
 319   if (!tcp_opts_sack (&tc->rcv_opts) && !sb->sacked_bytes
 320       && sb->head == TCP_INVALID_SACK_HOLE_INDEX)
 321     return;
 322
 323   has_rxt = tcp_in_cong_recovery (tc);
 324
 325   /* Remove invalid blocks */
 326   blk = tc->rcv_opts.sacks;
 327   while (blk < vec_end (tc->rcv_opts.sacks))
 328     {
 329       if (seq_lt (blk->start, blk->end)
 330           && seq_gt (blk->start, tc->snd_una)
 331           && seq_gt (blk->start, ack) && seq_leq (blk->end, tc->snd_nxt))
 332         {
 333           blk++;
 334           continue;
 335         }
 336       vec_del1 (tc->rcv_opts.sacks, blk - tc->rcv_opts.sacks);
 337     }
 338
 339   /* Add block for cumulative ack */
 340   if (seq_gt (ack, tc->snd_una))
 341     {
 342       vec_add2 (tc->rcv_opts.sacks, blk, 1);
 343       blk->start = tc->snd_una;
 344       blk->end = ack;
 345     }
 346
 347   if (vec_len (tc->rcv_opts.sacks) == 0)
 348     return;
 349
 350   tcp_scoreboard_trace_add (tc, ack);
 351
 352   /* Make sure blocks are ordered */
 353   rcv_sacks = tc->rcv_opts.sacks;
 354   for (i = 0; i < vec_len (rcv_sacks); i++)
 355     for (j = i + 1; j < vec_len (rcv_sacks); j++)
 356       if (seq_lt (rcv_sacks[j].start, rcv_sacks[i].start))
 357         {
 358           sack_block_t tmp = rcv_sacks[i];
 359           rcv_sacks[i] = rcv_sacks[j];
 360           rcv_sacks[j] = tmp;
 361         }
 362
 363   if (sb->head == TCP_INVALID_SACK_HOLE_INDEX)
 364     {
 365       /* Handle reneging as a special case */
 366       if (PREDICT_FALSE (sb->is_reneging))
 367         {
 368           /* No holes, only sacked bytes */
 369           if (seq_leq (tc->snd_nxt, sb->high_sacked))
 370             {
 371               /* No progress made so return */
 372               if (seq_leq (ack, tc->snd_una))
 373                 return;
 374
 375               /* Update sacked bytes delivered and return */
 376               sb->last_bytes_delivered = ack - tc->snd_una;
 377               sb->sacked_bytes -= sb->last_bytes_delivered;
 378               sb->is_reneging = seq_lt (ack, sb->high_sacked);
 379               return;
 380             }
 381
 382           /* New hole above high sacked. Add it and process normally */
 383           hole = scoreboard_insert_hole (sb, TCP_INVALID_SACK_HOLE_INDEX,
 384                                          sb->high_sacked, tc->snd_nxt);
 385           sb->tail = scoreboard_hole_index (sb, hole);
 386         }
 387       /* Not reneging and no holes. Insert the first that covers all
 388        * outstanding bytes */
 389       else
 390         {
 391           hole = scoreboard_insert_hole (sb, TCP_INVALID_SACK_HOLE_INDEX,
 392                                          tc->snd_una, tc->snd_nxt);
 393           sb->tail = scoreboard_hole_index (sb, hole);
 394         }
 395       sb->high_sacked = rcv_sacks[vec_len (rcv_sacks) - 1].end;
 396     }
 397   else
 398     {
 399       /* If we have holes but snd_nxt is beyond the last hole, update
 400        * last hole end or add new hole after high sacked */
 401       hole = scoreboard_last_hole (sb);
 402       if (seq_gt (tc->snd_nxt, hole->end))
 403         {
 404           if (seq_geq (hole->start, sb->high_sacked))
 405             {
 406               hole->end = tc->snd_nxt;
 407             }
 408           /* New hole after high sacked block */
 409           else if (seq_lt (sb->high_sacked, tc->snd_nxt))
 410             {
 411               scoreboard_insert_hole (sb, sb->tail, sb->high_sacked,
 412                                       tc->snd_nxt);
 413             }
 414         }
 415
 416       /* Keep track of max byte sacked for when the last hole
 417        * is acked */
 418       sb->high_sacked = seq_max (rcv_sacks[vec_len (rcv_sacks) - 1].end,
 419                                  sb->high_sacked);
 420     }
 421
 422   /* Walk the holes with the SACK blocks */
 423   hole = pool_elt_at_index (sb->holes, sb->head);
 424
 425   if (PREDICT_FALSE (sb->is_reneging))
 426     {
 427       sb->last_bytes_delivered += clib_min (hole->start - tc->snd_una,
 428                                             ack - tc->snd_una);
 429       sb->is_reneging = seq_lt (ack, hole->start);
 430     }
 431
 432   while (hole && blk_index < vec_len (rcv_sacks))
 433     {
 434       blk = &rcv_sacks[blk_index];
 435       if (seq_leq (blk->start, hole->start))
 436         {
 437           /* Block covers hole. Remove hole */
 438           if (seq_geq (blk->end, hole->end))
 439             {
 440               next_hole = scoreboard_next_hole (sb, hole);
 441
 442               /* If covered by ack, compute delivered bytes */
 443               if (blk->end == ack)
 444                 {
 445                   u32 sacked = next_hole ? next_hole->start : sb->high_sacked;
 446                   if (PREDICT_FALSE (seq_lt (ack, sacked)))
 447                     {
 448                       sb->last_bytes_delivered += ack - hole->end;
 449                       sb->is_reneging = 1;
 450                     }
 451                   else
 452                     {
 453                       sb->last_bytes_delivered += sacked - hole->end;
 454                       sb->is_reneging = 0;
 455                     }
 456                 }
 457               scoreboard_update_sacked_rxt (sb, hole->start, hole->end,
 458                                             has_rxt);
 459               scoreboard_remove_hole (sb, hole);
 460               hole = next_hole;
 461             }
 462           /* Partial 'head' overlap */
 463           else
 464             {
 465               if (seq_gt (blk->end, hole->start))
 466                 {
 467                   scoreboard_update_sacked_rxt (sb, hole->start, blk->end,
 468                                                 has_rxt);
 469                   hole->start = blk->end;
 470                 }
 471               blk_index++;
 472             }
 473         }
 474       else
 475         {
 476           /* Hole must be split */
 477           if (seq_lt (blk->end, hole->end))
 478             {
 479               u32 hole_index = scoreboard_hole_index (sb, hole);
 480               next_hole = scoreboard_insert_hole (sb, hole_index, blk->end,
 481                                                   hole->end);
 482               /* Pool might've moved */
 483               hole = scoreboard_get_hole (sb, hole_index);
 484               hole->end = blk->start;
 485
 486               scoreboard_update_sacked_rxt (sb, blk->start, blk->end,
 487                                             has_rxt);
 488
 489               blk_index++;
 490               ASSERT (hole->next == scoreboard_hole_index (sb, next_hole));
 491             }
 492           else if (seq_lt (blk->start, hole->end))
 493             {
 494               scoreboard_update_sacked_rxt (sb, blk->start, hole->end,
 495                                             has_rxt);
 496               hole->end = blk->start;
 497             }
 498           hole = scoreboard_next_hole (sb, hole);
 499         }
 500     }
 501
 502   scoreboard_update_bytes (sb, ack, tc->snd_mss);
 503
 504   ASSERT (sb->last_sacked_bytes <= sb->sacked_bytes || tcp_in_recovery (tc));
 505   ASSERT (sb->sacked_bytes == 0 || tcp_in_recovery (tc)
 506           || sb->sacked_bytes <= tc->snd_nxt - seq_max (tc->snd_una, ack));
 507   ASSERT (sb->last_sacked_bytes + sb->lost_bytes <= tc->snd_nxt
 508           - seq_max (tc->snd_una, ack) || tcp_in_recovery (tc));
 509   ASSERT (sb->head == TCP_INVALID_SACK_HOLE_INDEX || tcp_in_recovery (tc)
 510           || sb->is_reneging || sb->holes[sb->head].start == ack);
 511   ASSERT (sb->last_lost_bytes <= sb->lost_bytes);
 512   ASSERT ((ack - tc->snd_una) + sb->last_sacked_bytes
 513           - sb->last_bytes_delivered >= sb->rxt_sacked);
 514   ASSERT ((ack - tc->snd_una) >= tc->sack_sb.last_bytes_delivered
 515           || (tc->flags & TCP_CONN_FINSNT));
 516
 517   TCP_EVT (TCP_EVT_CC_SCOREBOARD, tc);
 518 }
 519
 520 static u8
 521 tcp_sack_vector_is_sane (sack_block_t * sacks)
 522 {
 523   int i;
 524   for (i = 1; i < vec_len (sacks); i++)
 525     {
 526       if (sacks[i - 1].end == sacks[i].start)
 527         return 0;
 528     }
 529   return 1;
 530 }
 531
 532 /**
 533  * Build SACK list as per RFC2018.
 534  *
 535  * Makes sure the first block contains the segment that generated the current
 536  * ACK and the following ones are the ones most recently reported in SACK
 537  * blocks.
 538  *
 539  * @param tc TCP connection for which the SACK list is updated
 540  * @param start Start sequence number of the newest SACK block
 541  * @param end End sequence of the newest SACK block
 542  */
 543 void
 544 tcp_update_sack_list (tcp_connection_t * tc, u32 start, u32 end)
 545 {
 546   sack_block_t *new_list = tc->snd_sacks_fl, *block = 0;
 547   int i;
 548
 549   /* If the first segment is ooo add it to the list. Last write might've moved
 550    * rcv_nxt over the first segment. */
 551   if (seq_lt (tc->rcv_nxt, start))
 552     {
 553       vec_add2 (new_list, block, 1);
 554       block->start = start;
 555       block->end = end;
 556     }
 557
 558   /* Find the blocks still worth keeping. */
 559   for (i = 0; i < vec_len (tc->snd_sacks); i++)
 560     {
 561       /* Discard if rcv_nxt advanced beyond current block */
 562       if (seq_leq (tc->snd_sacks[i].start, tc->rcv_nxt))
 563         continue;
 564
 565       /* Merge or drop if segment overlapped by the new segment */
 566       if (block && (seq_geq (tc->snd_sacks[i].end, new_list[0].start)
 567                     && seq_leq (tc->snd_sacks[i].start, new_list[0].end)))
 568         {
 569           if (seq_lt (tc->snd_sacks[i].start, new_list[0].start))
 570             new_list[0].start = tc->snd_sacks[i].start;
 571           if (seq_lt (new_list[0].end, tc->snd_sacks[i].end))
 572             new_list[0].end = tc->snd_sacks[i].end;
 573           continue;
 574         }
 575
 576       /* Save to new SACK list if we have space. */
 577       if (vec_len (new_list) < TCP_MAX_SACK_BLOCKS)
 578         vec_add1 (new_list, tc->snd_sacks[i]);
 579     }
 580
 581   ASSERT (vec_len (new_list) <= TCP_MAX_SACK_BLOCKS);
 582
 583   /* Replace old vector with new one */
 584   vec_reset_length (tc->snd_sacks);
 585   tc->snd_sacks_fl = tc->snd_sacks;
 586   tc->snd_sacks = new_list;
 587
 588   /* Segments should not 'touch' */
 589   ASSERT (tcp_sack_vector_is_sane (tc->snd_sacks));
 590 }
 591
 592 u32
 593 tcp_sack_list_bytes (tcp_connection_t * tc)
 594 {
 595   u32 bytes = 0, i;
 596   for (i = 0; i < vec_len (tc->snd_sacks); i++)
 597     bytes += tc->snd_sacks[i].end - tc->snd_sacks[i].start;
 598   return bytes;
 599 }
 600
 601 /*
 602  * fd.io coding-style-patch-verification: ON
 603  *
 604  * Local Variables:
 605  * eval: (c-set-style "gnu")
 606  * End:
 607  */