26 next->prev = hole->prev;
30 sb->tail = hole->prev;
36 prev->next = hole->next;
40 sb->head = hole->next;
70 hole->prev = prev_index;
71 hole->next = prev->next;
74 next->prev = hole_index;
76 sb->tail = hole_index;
78 prev->next = hole_index;
82 sb->head = hole_index;
92 u8 has_rxt,
u16 snd_mss)
98 if (
seq_lt (start, sb->high_sacked))
100 u32 reord = (sb->high_sacked - start + snd_mss - 1) / snd_mss;
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);
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;
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;
148 while (sacked <= (sb->reorder - 1) * snd_mss && blks < sb->reorder)
156 ASSERT (right->start == ack || sb->is_reneging);
157 sacked += right->start - ack;
162 sacked += right->start - left->end;
171 sb->last_lost_bytes += right->is_lost ? 0 : (right->end - right->start);
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);
196 u8 have_unsent,
u8 * can_rescue,
u8 * snd_limited)
201 while (hole &&
seq_leq (hole->end, sb->high_rxt) && hole->is_lost)
212 if (hole->is_lost &&
seq_lt (hole->start, sb->high_sacked))
225 else if (
seq_lt (hole->start, sb->high_sacked))
228 if (
seq_leq (hole->end, sb->high_rxt))
247 if (hole &&
seq_lt (sb->high_rxt, hole->start))
248 sb->high_rxt = hole->start;
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;
286 sb->sacked_bytes = 0;
287 sb->last_sacked_bytes = 0;
288 sb->last_bytes_delivered = 0;
290 sb->last_lost_bytes = 0;
304 last_hole->is_lost = 1;
306 sb->high_sacked = start;
321 return (!hole || (
seq_geq (hole->start, tc->snd_una)
322 &&
seq_lt (hole->end, tc->snd_nxt)));
331 u32 blk_index = 0,
i, j, high_sacked;
334 sb->last_sacked_bytes = 0;
335 sb->last_bytes_delivered = 0;
345 blk = tc->rcv_opts.sacks;
346 while (blk <
vec_end (tc->rcv_opts.sacks))
348 if (
seq_lt (blk->start, blk->end)
349 &&
seq_gt (blk->start, tc->snd_una)
350 &&
seq_gt (blk->start, ack)
351 &&
seq_lt (blk->start, tc->snd_nxt)
352 &&
seq_leq (blk->end, tc->snd_nxt))
357 vec_del1 (tc->rcv_opts.sacks, blk - tc->rcv_opts.sacks);
361 if (
seq_gt (ack, tc->snd_una))
363 vec_add2 (tc->rcv_opts.sacks, blk, 1);
364 blk->start = tc->snd_una;
368 if (
vec_len (tc->rcv_opts.sacks) == 0)
374 rcv_sacks = tc->rcv_opts.sacks;
376 for (j =
i + 1; j <
vec_len (rcv_sacks); j++)
377 if (
seq_lt (rcv_sacks[j].start, rcv_sacks[
i].start))
380 rcv_sacks[
i] = rcv_sacks[j];
390 if (
seq_leq (tc->snd_nxt, sb->high_sacked))
393 if (
seq_leq (ack, tc->snd_una))
397 sb->last_bytes_delivered = ack - tc->snd_una;
398 sb->sacked_bytes -= sb->last_bytes_delivered;
399 sb->is_reneging =
seq_lt (ack, sb->high_sacked);
405 sb->high_sacked, tc->snd_nxt);
413 tc->snd_una, tc->snd_nxt);
415 sb->high_sacked = tc->snd_una;
417 high_sacked = rcv_sacks[
vec_len (rcv_sacks) - 1].end;
424 if (
seq_gt (tc->snd_nxt, hole->end))
426 if (
seq_geq (hole->start, sb->high_sacked))
428 hole->end = tc->snd_nxt;
431 else if (
seq_lt (sb->high_sacked, tc->snd_nxt))
439 high_sacked =
seq_max (rcv_sacks[vec_len (rcv_sacks) - 1].
end,
448 sb->last_bytes_delivered +=
clib_min (hole->start - tc->snd_una,
450 sb->is_reneging =
seq_lt (ack, hole->start);
453 while (hole && blk_index < vec_len (rcv_sacks))
455 blk = &rcv_sacks[blk_index];
456 if (
seq_leq (blk->start, hole->start))
459 if (
seq_geq (blk->end, hole->end))
466 u32 sacked = next_hole ? next_hole->start :
467 seq_max (sb->high_sacked, hole->end);
470 sb->last_bytes_delivered += ack - hole->end;
475 sb->last_bytes_delivered += sacked - hole->end;
480 has_rxt, tc->snd_mss);
487 if (
seq_gt (blk->end, hole->start))
490 has_rxt, tc->snd_mss);
491 hole->start = blk->end;
499 if (
seq_lt (blk->end, hole->end))
506 hole->end = blk->start;
507 next_hole->is_lost = hole->is_lost;
510 has_rxt, tc->snd_mss);
515 else if (
seq_lt (blk->start, hole->end))
518 has_rxt, tc->snd_mss);
519 hole->end = blk->start;
525 sb->high_sacked = high_sacked;
530 || sb->sacked_bytes <= tc->snd_nxt -
seq_max (tc->snd_una, ack));
531 ASSERT (sb->last_sacked_bytes + sb->lost_bytes <= tc->snd_nxt
534 || sb->is_reneging || sb->holes[sb->head].start == ack);
535 ASSERT (sb->last_lost_bytes <= sb->lost_bytes);
536 ASSERT ((ack - tc->snd_una) + sb->last_sacked_bytes
537 - sb->last_bytes_delivered >= sb->rxt_sacked);
538 ASSERT ((ack - tc->snd_una) >= tc->sack_sb.last_bytes_delivered
539 || (tc->flags & TCP_CONN_FINSNT));
541 TCP_EVT (TCP_EVT_CC_SCOREBOARD, tc);
548 for (i = 1; i <
vec_len (sacks); i++)
550 if (sacks[i - 1].
end == sacks[i].start)
575 if (
seq_lt (tc->rcv_nxt, start))
578 block->start = start;
583 for (i = 0; i <
vec_len (tc->snd_sacks); i++)
586 if (
seq_leq (tc->snd_sacks[i].start, tc->rcv_nxt))
590 if (block && (
seq_geq (tc->snd_sacks[i].end, new_list[0].start)
591 &&
seq_leq (tc->snd_sacks[i].start, new_list[0].end)))
593 if (
seq_lt (tc->snd_sacks[i].start, new_list[0].start))
594 new_list[0].start = tc->snd_sacks[i].start;
595 if (
seq_lt (new_list[0].end, tc->snd_sacks[i].end))
596 new_list[0].end = tc->snd_sacks[i].end;
602 vec_add1 (new_list, tc->snd_sacks[i]);
609 tc->snd_sacks_fl = tc->snd_sacks;
610 tc->snd_sacks = new_list;
621 bytes += tc->snd_sacks[
i].end - tc->snd_sacks[
i].start;
#define TCP_MAX_SACK_REORDER
struct _sack_block sack_block_t
static u32 scoreboard_hole_bytes(sack_scoreboard_hole_t *hole)
#define TCP_INVALID_SACK_HOLE_INDEX
clib_memset(h->entries, 0, sizeof(h->entries[0]) *entries)
static sack_scoreboard_hole_t * scoreboard_get_hole(sack_scoreboard_t *sb, u32 index)
struct _tcp_connection tcp_connection_t
#define vec_add1(V, E)
Add 1 element to end of vector (unspecified alignment).
#define vec_add2(V, P, N)
Add N elements to end of vector V, return pointer to new elements in P.
#define tcp_opts_sack(_to)
static void scoreboard_update_sacked(sack_scoreboard_t *sb, u32 start, u32 end, u8 has_rxt, u16 snd_mss)
#define pool_get(P, E)
Allocate an object E from a pool P (unspecified alignment).
struct _sack_scoreboard sack_scoreboard_t
#define tcp_in_cong_recovery(tc)
#define vec_reset_length(v)
Reset vector length to zero NULL-pointer tolerant.
u32 tcp_sack_list_bytes(tcp_connection_t *tc)
#define seq_leq(_s1, _s2)
#define vec_end(v)
End (last data address) of vector.
static sack_scoreboard_hole_t * scoreboard_first_hole(sack_scoreboard_t *sb)
static sack_scoreboard_hole_t * scoreboard_prev_hole(sack_scoreboard_t *sb, sack_scoreboard_hole_t *hole)
static void scoreboard_update_bytes(sack_scoreboard_t *sb, u32 ack, u32 snd_mss)
void scoreboard_clear_reneging(sack_scoreboard_t *sb, u32 start, u32 end)
static sack_scoreboard_hole_t * scoreboard_next_hole(sack_scoreboard_t *sb, sack_scoreboard_hole_t *hole)
void tcp_update_sack_list(tcp_connection_t *tc, u32 start, u32 end)
Build SACK list as per RFC2018.
#define pool_elt_at_index(p, i)
Returns pointer to element at given index.
static u8 tcp_sack_vector_is_sane(sack_block_t *sacks)
#define TCP_DUPACK_THRESHOLD
static void scoreboard_remove_hole(sack_scoreboard_t *sb, sack_scoreboard_hole_t *hole)
#define pool_put(P, E)
Free an object E in pool P.
#define vec_del1(v, i)
Delete the element at index I.
static u32 scoreboard_hole_index(sack_scoreboard_t *sb, sack_scoreboard_hole_t *hole)
static sack_scoreboard_hole_t * scoreboard_last_hole(sack_scoreboard_t *sb)
#define seq_max(_s1, _s2)
void scoreboard_init(sack_scoreboard_t *sb)
sll srl srl sll sra u16x4 i
#define tcp_scoreboard_trace_add(_tc, _ack)
#define TCP_MAX_SACK_BLOCKS
Max number of SACK blocks stored.
#define tcp_in_recovery(tc)
#define seq_geq(_s1, _s2)
struct _sack_scoreboard_hole sack_scoreboard_hole_t
u8 tcp_scoreboard_is_sane_post_recovery(tcp_connection_t *tc)
Test that scoreboard is sane after recovery.
void scoreboard_clear(sack_scoreboard_t *sb)
#define vec_len(v)
Number of elements in vector (rvalue-only, NULL tolerant)
static sack_scoreboard_hole_t * scoreboard_insert_hole(sack_scoreboard_t *sb, u32 prev_index, u32 start, u32 end)
sack_scoreboard_hole_t * scoreboard_next_rxt_hole(sack_scoreboard_t *sb, sack_scoreboard_hole_t *start, u8 have_unsent, u8 *can_rescue, u8 *snd_limited)
Figure out the next hole to retransmit.
void scoreboard_init_rxt(sack_scoreboard_t *sb, u32 snd_una)
f64 end
end of the time range
void tcp_rcv_sacks(tcp_connection_t *tc, u32 ack)
#define TCP_EVT(_evt, _args...)
static uword pool_elts(void *v)
Number of active elements in a pool.