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:
7 * http://www.apache.org/licenses/LICENSE-2.0
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.
16 #include <vnet/tcp/tcp_sack.h>
19 scoreboard_remove_hole (sack_scoreboard_t * sb, sack_scoreboard_hole_t * hole)
21 sack_scoreboard_hole_t *next, *prev;
23 if (hole->next != TCP_INVALID_SACK_HOLE_INDEX)
25 next = pool_elt_at_index (sb->holes, hole->next);
26 next->prev = hole->prev;
30 sb->tail = hole->prev;
33 if (hole->prev != TCP_INVALID_SACK_HOLE_INDEX)
35 prev = pool_elt_at_index (sb->holes, hole->prev);
36 prev->next = hole->next;
40 sb->head = hole->next;
43 if (scoreboard_hole_index (sb, hole) == sb->cur_rxt_hole)
44 sb->cur_rxt_hole = TCP_INVALID_SACK_HOLE_INDEX;
46 /* Poison the entry */
48 clib_memset (hole, 0xfe, sizeof (*hole));
50 pool_put (sb->holes, hole);
53 static sack_scoreboard_hole_t *
54 scoreboard_insert_hole (sack_scoreboard_t * sb, u32 prev_index,
57 sack_scoreboard_hole_t *hole, *next, *prev;
60 pool_get (sb->holes, hole);
61 clib_memset (hole, 0, sizeof (*hole));
65 hole_index = scoreboard_hole_index (sb, hole);
67 prev = scoreboard_get_hole (sb, prev_index);
70 hole->prev = prev_index;
71 hole->next = prev->next;
73 if ((next = scoreboard_next_hole (sb, hole)))
74 next->prev = hole_index;
76 sb->tail = hole_index;
78 prev->next = hole_index;
82 sb->head = hole_index;
83 hole->prev = TCP_INVALID_SACK_HOLE_INDEX;
84 hole->next = TCP_INVALID_SACK_HOLE_INDEX;
91 scoreboard_update_sacked (sack_scoreboard_t * sb, u32 start, u32 end,
92 u8 has_rxt, u16 snd_mss)
96 /* Sequence was not retransmitted but it was sacked. Estimate reorder
97 * only if not in congestion recovery */
98 if (seq_lt (start, sb->high_sacked))
100 u32 reord = (sb->high_sacked - start + snd_mss - 1) / snd_mss;
101 reord = clib_min (reord, TCP_MAX_SACK_REORDER);
102 sb->reorder = clib_max (sb->reorder, reord);
107 if (seq_geq (start, sb->high_rxt))
111 seq_lt (end, sb->high_rxt) ? (end - start) : (sb->high_rxt - start);
115 scoreboard_update_bytes (sack_scoreboard_t * sb, u32 ack, u32 snd_mss)
117 sack_scoreboard_hole_t *left, *right;
118 u32 sacked = 0, blks = 0, old_sacked;
120 old_sacked = sb->sacked_bytes;
122 sb->last_lost_bytes = 0;
124 sb->sacked_bytes = 0;
126 right = scoreboard_last_hole (sb);
129 sb->sacked_bytes = sb->high_sacked - ack;
130 sb->last_sacked_bytes = sb->sacked_bytes
131 - (old_sacked - sb->last_bytes_delivered);
135 if (seq_gt (sb->high_sacked, right->end))
137 sacked = sb->high_sacked - right->end;
141 /* As per RFC 6675 a sequence number is lost if:
142 * DupThresh discontiguous SACKed sequences have arrived above
143 * 'SeqNum' or more than (DupThresh - 1) * SMSS bytes with sequence
144 * numbers greater than 'SeqNum' have been SACKed.
145 * To avoid spurious retransmits, use reordering estimate instead of
146 * DupThresh to detect loss.
148 while (sacked <= (sb->reorder - 1) * snd_mss && blks < sb->reorder)
151 sb->lost_bytes += scoreboard_hole_bytes (right);
153 left = scoreboard_prev_hole (sb, right);
156 ASSERT (right->start == ack || sb->is_reneging);
157 sacked += right->start - ack;
162 sacked += right->start - left->end;
167 /* right is first lost */
170 sb->lost_bytes += scoreboard_hole_bytes (right);
171 sb->last_lost_bytes += right->is_lost ? 0 : (right->end - right->start);
173 left = scoreboard_prev_hole (sb, right);
176 ASSERT (right->start == ack || sb->is_reneging);
177 sacked += right->start - ack;
180 sacked += right->start - left->end;
184 sb->sacked_bytes = sacked;
185 sb->last_sacked_bytes = sacked - (old_sacked - sb->last_bytes_delivered);
189 * Figure out the next hole to retransmit
191 * Follows logic proposed in RFC6675 Sec. 4, NextSeg()
193 sack_scoreboard_hole_t *
194 scoreboard_next_rxt_hole (sack_scoreboard_t * sb,
195 sack_scoreboard_hole_t * start,
196 u8 have_unsent, u8 * can_rescue, u8 * snd_limited)
198 sack_scoreboard_hole_t *hole = 0;
200 hole = start ? start : scoreboard_first_hole (sb);
201 while (hole && seq_leq (hole->end, sb->high_rxt) && hole->is_lost)
202 hole = scoreboard_next_hole (sb, hole);
204 /* Nothing, return */
207 sb->cur_rxt_hole = TCP_INVALID_SACK_HOLE_INDEX;
211 /* Rule (1): if higher than rxt, less than high_sacked and lost */
212 if (hole->is_lost && seq_lt (hole->start, sb->high_sacked))
214 sb->cur_rxt_hole = scoreboard_hole_index (sb, hole);
218 /* Rule (2): available unsent data */
221 sb->cur_rxt_hole = TCP_INVALID_SACK_HOLE_INDEX;
224 /* Rule (3): if hole not lost */
225 else if (seq_lt (hole->start, sb->high_sacked))
227 /* And we didn't already retransmit it */
228 if (seq_leq (hole->end, sb->high_rxt))
230 sb->cur_rxt_hole = TCP_INVALID_SACK_HOLE_INDEX;
234 sb->cur_rxt_hole = scoreboard_hole_index (sb, hole);
236 /* Rule (4): if hole beyond high_sacked */
239 ASSERT (seq_geq (hole->start, sb->high_sacked));
242 /* HighRxt MUST NOT be updated */
247 if (hole && seq_lt (sb->high_rxt, hole->start))
248 sb->high_rxt = hole->start;
254 scoreboard_init_rxt (sack_scoreboard_t * sb, u32 snd_una)
256 sack_scoreboard_hole_t *hole;
257 hole = scoreboard_first_hole (sb);
260 snd_una = seq_gt (snd_una, hole->start) ? snd_una : hole->start;
261 sb->cur_rxt_hole = sb->head;
263 sb->high_rxt = snd_una;
264 sb->rescue_rxt = snd_una - 1;
268 scoreboard_rxt_mark_lost (sack_scoreboard_t *sb, u32 snd_una, u32 snd_nxt)
270 sack_scoreboard_hole_t *hole;
272 hole = scoreboard_first_hole (sb);
275 hole = scoreboard_insert_hole (sb, TCP_INVALID_SACK_HOLE_INDEX, snd_una,
277 sb->tail = scoreboard_hole_index (sb, hole);
278 sb->high_sacked = snd_una;
285 sb->lost_bytes += scoreboard_hole_bytes (hole);
289 scoreboard_init (sack_scoreboard_t * sb)
291 sb->head = TCP_INVALID_SACK_HOLE_INDEX;
292 sb->tail = TCP_INVALID_SACK_HOLE_INDEX;
293 sb->cur_rxt_hole = TCP_INVALID_SACK_HOLE_INDEX;
294 sb->reorder = TCP_DUPACK_THRESHOLD;
298 scoreboard_clear (sack_scoreboard_t * sb)
300 sack_scoreboard_hole_t *hole;
301 while ((hole = scoreboard_first_hole (sb)))
303 scoreboard_remove_hole (sb, hole);
305 ASSERT (sb->head == sb->tail && sb->head == TCP_INVALID_SACK_HOLE_INDEX);
306 ASSERT (pool_elts (sb->holes) == 0);
307 sb->sacked_bytes = 0;
308 sb->last_sacked_bytes = 0;
309 sb->last_bytes_delivered = 0;
311 sb->last_lost_bytes = 0;
312 sb->cur_rxt_hole = TCP_INVALID_SACK_HOLE_INDEX;
314 sb->reorder = TCP_DUPACK_THRESHOLD;
318 scoreboard_clear_reneging (sack_scoreboard_t * sb, u32 start, u32 end)
320 sack_scoreboard_hole_t *last_hole;
322 scoreboard_clear (sb);
323 last_hole = scoreboard_insert_hole (sb, TCP_INVALID_SACK_HOLE_INDEX,
325 last_hole->is_lost = 1;
326 sb->tail = scoreboard_hole_index (sb, last_hole);
327 sb->high_sacked = start;
328 scoreboard_init_rxt (sb, start);
332 * Test that scoreboard is sane after recovery
334 * Returns 1 if scoreboard is empty or if first hole beyond
338 tcp_scoreboard_is_sane_post_recovery (tcp_connection_t * tc)
340 sack_scoreboard_hole_t *hole;
341 hole = scoreboard_first_hole (&tc->sack_sb);
342 return (!hole || (seq_geq (hole->start, tc->snd_una)
343 && seq_lt (hole->end, tc->snd_nxt)));
347 tcp_rcv_sacks (tcp_connection_t * tc, u32 ack)
349 sack_scoreboard_hole_t *hole, *next_hole;
350 sack_scoreboard_t *sb = &tc->sack_sb;
351 sack_block_t *blk, *rcv_sacks;
352 u32 blk_index = 0, i, j, high_sacked;
355 sb->last_sacked_bytes = 0;
356 sb->last_bytes_delivered = 0;
359 if (!tcp_opts_sack (&tc->rcv_opts) && !sb->sacked_bytes
360 && sb->head == TCP_INVALID_SACK_HOLE_INDEX)
363 has_rxt = tcp_in_cong_recovery (tc);
365 /* Remove invalid blocks */
366 blk = tc->rcv_opts.sacks;
367 while (blk < vec_end (tc->rcv_opts.sacks))
369 if (seq_lt (blk->start, blk->end)
370 && seq_gt (blk->start, tc->snd_una)
371 && seq_gt (blk->start, ack)
372 && seq_lt (blk->start, tc->snd_nxt)
373 && seq_leq (blk->end, tc->snd_nxt))
378 vec_del1 (tc->rcv_opts.sacks, blk - tc->rcv_opts.sacks);
381 /* Add block for cumulative ack */
382 if (seq_gt (ack, tc->snd_una))
384 vec_add2 (tc->rcv_opts.sacks, blk, 1);
385 blk->start = tc->snd_una;
389 if (vec_len (tc->rcv_opts.sacks) == 0)
392 tcp_scoreboard_trace_add (tc, ack);
394 /* Make sure blocks are ordered */
395 rcv_sacks = tc->rcv_opts.sacks;
396 for (i = 0; i < vec_len (rcv_sacks); i++)
397 for (j = i + 1; j < vec_len (rcv_sacks); j++)
398 if (seq_lt (rcv_sacks[j].start, rcv_sacks[i].start))
400 sack_block_t tmp = rcv_sacks[i];
401 rcv_sacks[i] = rcv_sacks[j];
405 if (sb->head == TCP_INVALID_SACK_HOLE_INDEX)
407 /* Handle reneging as a special case */
408 if (PREDICT_FALSE (sb->is_reneging))
410 /* No holes, only sacked bytes */
411 if (seq_leq (tc->snd_nxt, sb->high_sacked))
413 /* No progress made so return */
414 if (seq_leq (ack, tc->snd_una))
417 /* Update sacked bytes delivered and return */
418 sb->last_bytes_delivered = ack - tc->snd_una;
419 sb->sacked_bytes -= sb->last_bytes_delivered;
420 sb->is_reneging = seq_lt (ack, sb->high_sacked);
424 /* New hole above high sacked. Add it and process normally */
425 hole = scoreboard_insert_hole (sb, TCP_INVALID_SACK_HOLE_INDEX,
426 sb->high_sacked, tc->snd_nxt);
427 sb->tail = scoreboard_hole_index (sb, hole);
429 /* Not reneging and no holes. Insert the first that covers all
430 * outstanding bytes */
433 hole = scoreboard_insert_hole (sb, TCP_INVALID_SACK_HOLE_INDEX,
434 tc->snd_una, tc->snd_nxt);
435 sb->tail = scoreboard_hole_index (sb, hole);
436 sb->high_sacked = tc->snd_una;
438 high_sacked = rcv_sacks[vec_len (rcv_sacks) - 1].end;
442 /* If we have holes but snd_nxt is beyond the last hole, update
443 * last hole end or add new hole after high sacked */
444 hole = scoreboard_last_hole (sb);
445 if (seq_gt (tc->snd_nxt, hole->end))
447 if (seq_geq (hole->start, sb->high_sacked))
449 hole->end = tc->snd_nxt;
451 /* New hole after high sacked block */
452 else if (seq_lt (sb->high_sacked, tc->snd_nxt))
454 scoreboard_insert_hole (sb, sb->tail, sb->high_sacked,
458 /* Keep track of max byte sacked for when the last hole
460 high_sacked = seq_max (rcv_sacks[vec_len (rcv_sacks) - 1].end,
464 /* Walk the holes with the SACK blocks */
465 hole = pool_elt_at_index (sb->holes, sb->head);
467 if (PREDICT_FALSE (sb->is_reneging))
469 sb->last_bytes_delivered += clib_min (hole->start - tc->snd_una,
471 sb->is_reneging = seq_lt (ack, hole->start);
474 while (hole && blk_index < vec_len (rcv_sacks))
476 blk = &rcv_sacks[blk_index];
477 if (seq_leq (blk->start, hole->start))
479 /* Block covers hole. Remove hole */
480 if (seq_geq (blk->end, hole->end))
482 next_hole = scoreboard_next_hole (sb, hole);
484 /* If covered by ack, compute delivered bytes */
487 u32 sacked = next_hole ? next_hole->start :
488 seq_max (sb->high_sacked, hole->end);
489 if (PREDICT_FALSE (seq_lt (ack, sacked)))
491 sb->last_bytes_delivered += ack - hole->end;
496 sb->last_bytes_delivered += sacked - hole->end;
500 scoreboard_update_sacked (sb, hole->start, hole->end,
501 has_rxt, tc->snd_mss);
502 scoreboard_remove_hole (sb, hole);
505 /* Partial 'head' overlap */
508 if (seq_gt (blk->end, hole->start))
510 scoreboard_update_sacked (sb, hole->start, blk->end,
511 has_rxt, tc->snd_mss);
512 hole->start = blk->end;
519 /* Hole must be split */
520 if (seq_lt (blk->end, hole->end))
522 u32 hole_index = scoreboard_hole_index (sb, hole);
523 next_hole = scoreboard_insert_hole (sb, hole_index, blk->end,
525 /* Pool might've moved */
526 hole = scoreboard_get_hole (sb, hole_index);
527 hole->end = blk->start;
528 next_hole->is_lost = hole->is_lost;
530 scoreboard_update_sacked (sb, blk->start, blk->end,
531 has_rxt, tc->snd_mss);
534 ASSERT (hole->next == scoreboard_hole_index (sb, next_hole));
536 else if (seq_lt (blk->start, hole->end))
538 scoreboard_update_sacked (sb, blk->start, hole->end,
539 has_rxt, tc->snd_mss);
540 hole->end = blk->start;
542 hole = scoreboard_next_hole (sb, hole);
546 sb->high_sacked = high_sacked;
547 scoreboard_update_bytes (sb, ack, tc->snd_mss);
549 ASSERT (sb->last_sacked_bytes <= sb->sacked_bytes || tcp_in_recovery (tc));
550 ASSERT (sb->sacked_bytes == 0 || tcp_in_recovery (tc)
551 || sb->sacked_bytes <= tc->snd_nxt - seq_max (tc->snd_una, ack));
552 ASSERT (sb->last_sacked_bytes + sb->lost_bytes <= tc->snd_nxt
553 - seq_max (tc->snd_una, ack) || tcp_in_recovery (tc));
554 ASSERT (sb->head == TCP_INVALID_SACK_HOLE_INDEX || tcp_in_recovery (tc)
555 || sb->is_reneging || sb->holes[sb->head].start == ack);
556 ASSERT (sb->last_lost_bytes <= sb->lost_bytes);
557 ASSERT ((ack - tc->snd_una) + sb->last_sacked_bytes
558 - sb->last_bytes_delivered >= sb->rxt_sacked);
559 ASSERT ((ack - tc->snd_una) >= tc->sack_sb.last_bytes_delivered
560 || (tc->flags & TCP_CONN_FINSNT));
562 TCP_EVT (TCP_EVT_CC_SCOREBOARD, tc);
566 tcp_sack_vector_is_sane (sack_block_t * sacks)
569 for (i = 1; i < vec_len (sacks); i++)
571 if (sacks[i - 1].end == sacks[i].start)
578 * Build SACK list as per RFC2018.
580 * Makes sure the first block contains the segment that generated the current
581 * ACK and the following ones are the ones most recently reported in SACK
584 * @param tc TCP connection for which the SACK list is updated
585 * @param start Start sequence number of the newest SACK block
586 * @param end End sequence of the newest SACK block
589 tcp_update_sack_list (tcp_connection_t * tc, u32 start, u32 end)
591 sack_block_t *new_list = tc->snd_sacks_fl, *block = 0;
594 /* If the first segment is ooo add it to the list. Last write might've moved
595 * rcv_nxt over the first segment. */
596 if (seq_lt (tc->rcv_nxt, start))
598 vec_add2 (new_list, block, 1);
599 block->start = start;
603 /* Find the blocks still worth keeping. */
604 for (i = 0; i < vec_len (tc->snd_sacks); i++)
606 /* Discard if rcv_nxt advanced beyond current block */
607 if (seq_leq (tc->snd_sacks[i].start, tc->rcv_nxt))
610 /* Merge or drop if segment overlapped by the new segment */
611 if (block && (seq_geq (tc->snd_sacks[i].end, new_list[0].start)
612 && seq_leq (tc->snd_sacks[i].start, new_list[0].end)))
614 if (seq_lt (tc->snd_sacks[i].start, new_list[0].start))
615 new_list[0].start = tc->snd_sacks[i].start;
616 if (seq_lt (new_list[0].end, tc->snd_sacks[i].end))
617 new_list[0].end = tc->snd_sacks[i].end;
621 /* Save to new SACK list if we have space. */
622 if (vec_len (new_list) < TCP_MAX_SACK_BLOCKS)
623 vec_add1 (new_list, tc->snd_sacks[i]);
626 ASSERT (vec_len (new_list) <= TCP_MAX_SACK_BLOCKS);
628 /* Replace old vector with new one */
629 vec_reset_length (tc->snd_sacks);
630 tc->snd_sacks_fl = tc->snd_sacks;
631 tc->snd_sacks = new_list;
633 /* Segments should not 'touch' */
634 ASSERT (tcp_sack_vector_is_sane (tc->snd_sacks));
638 tcp_sack_list_bytes (tcp_connection_t * tc)
641 for (i = 0; i < vec_len (tc->snd_sacks); i++)
642 bytes += tc->snd_sacks[i].end - tc->snd_sacks[i].start;
647 * fd.io coding-style-patch-verification: ON
650 * eval: (c-set-style "gnu")