aboutsummaryrefslogtreecommitdiffstats
path: root/src/vnet/tcp/tcp_output.c
diff options
context:
space:
mode:
authorFlorin Coras <fcoras@cisco.com>2017-05-24 18:03:56 -0700
committerDave Barach <openvpp@barachs.net>2017-06-09 16:47:19 +0000
commit93992a9048cb6e5dcd22de5091e72de778122627 (patch)
treef295bb870ad1614d9327828dd036fb03f60e455e /src/vnet/tcp/tcp_output.c
parent583dc8d3e23a780c85ebe48ea59f0338aad4df17 (diff)
Implement sack based tcp loss recovery (RFC 6675)
- refactor existing congestion control code (RFC 6582/5681). Handling of ack feedback now consists of: ack parsing, cc event detection, event handling, congestion control update - extend sack scoreboard to support sack based retransmissions - basic implementation of Eifel detection algorithm (RFC 3522) for detecting spurious retransmissions - actually initialize the per-thread frame freelist hash tables - increase worker stack size to 2mb - fix session queue node out-of-buffer handling - ensure that the local buffer cache vec_len matches reality - avoid 2x spurious event requeues when short of buffers - count out-of-buffer events - make the builtin server thread-safe - fix bihash template threading issue: need to paint -1 across uninitialized working_copy_length vector elements (via rebase from master) Change-Id: I646cb9f1add9a67d08f4a87badbcb117980ebfc4 Signed-off-by: Florin Coras <fcoras@cisco.com> Signed-off-by: Dave Barach <dbarach@cisco.com>
Diffstat (limited to 'src/vnet/tcp/tcp_output.c')
-rw-r--r--src/vnet/tcp/tcp_output.c287
1 files changed, 189 insertions, 98 deletions
diff --git a/src/vnet/tcp/tcp_output.c b/src/vnet/tcp/tcp_output.c
index 49fd6beffa3..47c94e6daca 100644
--- a/src/vnet/tcp/tcp_output.c
+++ b/src/vnet/tcp/tcp_output.c
@@ -136,10 +136,10 @@ tcp_update_rcv_wnd (tcp_connection_t * tc)
* Figure out how much space we have available
*/
available_space = stream_session_max_rx_enqueue (&tc->connection);
- max_fifo = stream_session_fifo_size (&tc->connection);
+ max_fifo = stream_session_rx_fifo_size (&tc->connection);
- ASSERT (tc->opt.mss < max_fifo);
- if (available_space < tc->opt.mss && available_space < max_fifo >> 3)
+ ASSERT (tc->rcv_opts.mss < max_fifo);
+ if (available_space < tc->rcv_opts.mss && available_space < max_fifo >> 3)
available_space = 0;
/*
@@ -276,8 +276,11 @@ tcp_make_syn_options (tcp_options_t * opts, u8 wnd_scale)
opts->tsecr = 0;
len += TCP_OPTION_LEN_TIMESTAMP;
- opts->flags |= TCP_OPTS_FLAG_SACK_PERMITTED;
- len += TCP_OPTION_LEN_SACK_PERMITTED;
+ if (TCP_USE_SACKS)
+ {
+ opts->flags |= TCP_OPTS_FLAG_SACK_PERMITTED;
+ len += TCP_OPTION_LEN_SACK_PERMITTED;
+ }
/* Align to needed boundary */
len += (TCP_OPTS_ALIGN - len % TCP_OPTS_ALIGN) % TCP_OPTS_ALIGN;
@@ -293,14 +296,14 @@ tcp_make_synack_options (tcp_connection_t * tc, tcp_options_t * opts)
opts->mss = tc->mss;
len += TCP_OPTION_LEN_MSS;
- if (tcp_opts_wscale (&tc->opt))
+ if (tcp_opts_wscale (&tc->rcv_opts))
{
opts->flags |= TCP_OPTS_FLAG_WSCALE;
opts->wscale = tc->rcv_wscale;
len += TCP_OPTION_LEN_WINDOW_SCALE;
}
- if (tcp_opts_tstamp (&tc->opt))
+ if (tcp_opts_tstamp (&tc->rcv_opts))
{
opts->flags |= TCP_OPTS_FLAG_TSTAMP;
opts->tsval = tcp_time_now ();
@@ -308,7 +311,7 @@ tcp_make_synack_options (tcp_connection_t * tc, tcp_options_t * opts)
len += TCP_OPTION_LEN_TIMESTAMP;
}
- if (tcp_opts_sack_permitted (&tc->opt))
+ if (tcp_opts_sack_permitted (&tc->rcv_opts))
{
opts->flags |= TCP_OPTS_FLAG_SACK_PERMITTED;
len += TCP_OPTION_LEN_SACK_PERMITTED;
@@ -326,14 +329,14 @@ tcp_make_established_options (tcp_connection_t * tc, tcp_options_t * opts)
opts->flags = 0;
- if (tcp_opts_tstamp (&tc->opt))
+ if (tcp_opts_tstamp (&tc->rcv_opts))
{
opts->flags |= TCP_OPTS_FLAG_TSTAMP;
opts->tsval = tcp_time_now ();
opts->tsecr = tc->tsval_recent;
len += TCP_OPTION_LEN_TIMESTAMP;
}
- if (tcp_opts_sack_permitted (&tc->opt))
+ if (tcp_opts_sack_permitted (&tc->rcv_opts))
{
if (vec_len (tc->snd_sacks))
{
@@ -395,7 +398,7 @@ tcp_update_snd_mss (tcp_connection_t * tc)
tcp_make_options (tc, &tc->snd_opts, TCP_STATE_ESTABLISHED);
/* XXX check if MTU has been updated */
- tc->snd_mss = clib_min (tc->mss, tc->opt.mss) - tc->snd_opts_len;
+ tc->snd_mss = clib_min (tc->mss, tc->rcv_opts.mss) - tc->snd_opts_len;
ASSERT (tc->snd_mss > 0);
}
@@ -406,21 +409,21 @@ tcp_init_mss (tcp_connection_t * tc)
tcp_update_rcv_mss (tc);
/* TODO cache mss and consider PMTU discovery */
- tc->snd_mss = clib_min (tc->opt.mss, tc->mss);
+ tc->snd_mss = clib_min (tc->rcv_opts.mss, tc->mss);
if (tc->snd_mss < 45)
{
clib_warning ("snd mss is 0");
/* Assume that at least the min default mss works */
tc->snd_mss = default_min_mss;
- tc->opt.mss = default_min_mss;
+ tc->rcv_opts.mss = default_min_mss;
}
/* We should have enough space for 40 bytes of options */
ASSERT (tc->snd_mss > 45);
/* If we use timestamp option, account for it */
- if (tcp_opts_tstamp (&tc->opt))
+ if (tcp_opts_tstamp (&tc->rcv_opts))
tc->snd_mss -= TCP_OPTION_LEN_TIMESTAMP;
}
@@ -879,6 +882,7 @@ tcp_send_fin (tcp_connection_t * tc)
tcp_make_fin (tc, b);
tcp_enqueue_to_output (vm, b, bi, tc->c_is_ip4);
tc->flags |= TCP_CONN_FINSNT;
+ tcp_retransmit_timer_force_update (tc);
TCP_EVT_DBG (TCP_EVT_FIN_SENT, tc);
}
@@ -919,10 +923,7 @@ tcp_push_hdr_i (tcp_connection_t * tc, vlib_buffer_t * b,
if (compute_opts)
tc->snd_opts_len = tcp_make_options (tc, &tc->snd_opts, tc->state);
- /* Write pre-computed options */
tcp_hdr_opts_len = tc->snd_opts_len + sizeof (tcp_header_t);
-
- /* Get rcv window to advertise */
advertise_wnd = tcp_window_to_advertise (tc, next_state);
flags = tcp_make_state_flags (next_state);
@@ -930,26 +931,25 @@ tcp_push_hdr_i (tcp_connection_t * tc, vlib_buffer_t * b,
th = vlib_buffer_push_tcp (b, tc->c_lcl_port, tc->c_rmt_port, tc->snd_nxt,
tc->rcv_nxt, tcp_hdr_opts_len, flags,
advertise_wnd);
-
opts_write_len = tcp_options_write ((u8 *) (th + 1), &tc->snd_opts);
ASSERT (opts_write_len == tc->snd_opts_len);
-
- /* Tag the buffer with the connection index */
vnet_buffer (b)->tcp.connection_index = tc->c_c_index;
+ /*
+ * Update connection variables
+ */
+
tc->snd_nxt += data_len;
tc->rcv_las = tc->rcv_nxt;
/* TODO this is updated in output as well ... */
- if (tc->snd_nxt > tc->snd_una_max)
- tc->snd_una_max = tc->snd_nxt;
-
- if (tc->rtt_ts == 0)
+ if (seq_gt (tc->snd_nxt, tc->snd_una_max))
{
- tc->rtt_ts = tcp_time_now ();
- tc->rtt_seq = tc->snd_nxt;
+ tc->snd_una_max = tc->snd_nxt;
+ tcp_validate_txf_size (tc, tc->snd_una_max - tc->snd_una);
}
+
TCP_EVT_DBG (TCP_EVT_PKTIZE, tc);
}
@@ -987,13 +987,14 @@ tcp_timer_delack_handler (u32 index)
*
* @return the number of bytes in the segment or 0 if there's nothing to
* retransmit
- * */
+ */
u32
tcp_prepare_retransmit_segment (tcp_connection_t * tc, vlib_buffer_t * b,
u32 offset, u32 max_bytes)
{
vlib_main_t *vm = vlib_get_main ();
- u32 n_bytes = 0;
+ int n_bytes = 0;
+ u32 start;
tcp_reuse_buffer (vm, b);
@@ -1001,15 +1002,16 @@ tcp_prepare_retransmit_segment (tcp_connection_t * tc, vlib_buffer_t * b,
ASSERT (max_bytes != 0);
max_bytes = clib_min (tc->snd_mss, max_bytes);
+ start = tc->snd_una + offset;
/* Start is beyond snd_congestion */
- if (seq_geq (tc->snd_una + offset, tc->snd_congestion))
+ if (seq_geq (start, tc->snd_congestion))
goto done;
/* Don't overshoot snd_congestion */
- if (seq_gt (tc->snd_nxt + max_bytes, tc->snd_congestion))
+ if (seq_gt (start + max_bytes, tc->snd_congestion))
{
- max_bytes = tc->snd_congestion - tc->snd_nxt;
+ max_bytes = tc->snd_congestion - start;
if (max_bytes == 0)
goto done;
}
@@ -1021,15 +1023,12 @@ tcp_prepare_retransmit_segment (tcp_connection_t * tc, vlib_buffer_t * b,
n_bytes = stream_session_peek_bytes (&tc->connection,
vlib_buffer_get_current (b), offset,
max_bytes);
- ASSERT (n_bytes != 0);
+ ASSERT (n_bytes > 0);
b->current_length = n_bytes;
tcp_push_hdr_i (tc, b, tc->state, 0);
- /* Don't count multiple retransmits of the same segment */
- if (tc->rto_boff > 1)
- goto done;
-
- tc->rtx_bytes += n_bytes;
+ if (tcp_in_fastrecovery (tc))
+ tc->snd_rxt_bytes += n_bytes;
done:
TCP_EVT_DBG (TCP_EVT_CC_RTX, tc, offset, n_bytes);
@@ -1042,18 +1041,15 @@ done:
static void
tcp_rtx_timeout_cc (tcp_connection_t * tc)
{
+ tc->prev_ssthresh = tc->ssthresh;
+ tc->prev_cwnd = tc->cwnd;
+
/* Cleanly recover cc (also clears up fast retransmit) */
if (tcp_in_fastrecovery (tc))
- {
- tcp_cc_recover (tc);
- }
- else
- {
- tc->ssthresh = clib_max (tcp_flight_size (tc) / 2, 2 * tc->snd_mss);
- }
+ tcp_cc_fastrecovery_exit (tc);
/* Start again from the beginning */
-
+ tc->ssthresh = clib_max (tcp_flight_size (tc) / 2, 2 * tc->snd_mss);
tc->cwnd = tcp_loss_wnd (tc);
tc->snd_congestion = tc->snd_una_max;
tcp_recovery_on (tc);
@@ -1081,18 +1077,31 @@ tcp_timer_retransmit_handler_i (u32 index, u8 is_syn)
/* Make sure timer handle is set to invalid */
tc->timers[TCP_TIMER_RETRANSMIT] = TCP_TIMER_HANDLE_INVALID;
+ if (!tcp_in_recovery (tc) && tc->rto_boff > 0
+ && tc->state >= TCP_STATE_ESTABLISHED)
+ {
+ tc->rto_boff = 0;
+ tcp_update_rto (tc);
+ }
+
/* Increment RTO backoff (also equal to number of retries) */
tc->rto_boff += 1;
/* Go back to first un-acked byte */
tc->snd_nxt = tc->snd_una;
- /* Get buffer */
tcp_get_free_buffer_index (tm, &bi);
b = vlib_get_buffer (vm, bi);
if (tc->state >= TCP_STATE_ESTABLISHED)
{
+ /* Lost FIN, retransmit and return */
+ if (tc->flags & TCP_CONN_FINSNT)
+ {
+ tcp_send_fin (tc);
+ return;
+ }
+
/* First retransmit timeout */
if (tc->rto_boff == 1)
tcp_rtx_timeout_cc (tc);
@@ -1102,24 +1111,30 @@ tcp_timer_retransmit_handler_i (u32 index, u8 is_syn)
TCP_EVT_DBG (TCP_EVT_CC_EVT, tc, 1);
- /* Send one segment. No fancy recovery for now! */
+ /* Send one segment */
n_bytes = tcp_prepare_retransmit_segment (tc, b, 0, tc->snd_mss);
+ /* TODO be less aggressive about this */
scoreboard_clear (&tc->sack_sb);
if (n_bytes == 0)
{
clib_warning ("could not retransmit anything");
+ clib_warning ("%U", format_tcp_connection, tc, 2);
+
/* Try again eventually */
tcp_retransmit_timer_set (tc);
+ ASSERT (0 || (tc->rto_boff > 1
+ && tc->snd_una == tc->snd_congestion));
return;
}
+
+ /* For first retransmit, record timestamp (Eifel detection RFC3522) */
+ if (tc->rto_boff == 1)
+ tc->snd_rxt_ts = tcp_time_now ();
}
- else
+ /* Retransmit for SYN/SYNACK */
+ else if (tc->state == TCP_STATE_SYN_RCVD || tc->state == TCP_STATE_SYN_SENT)
{
- /* Retransmit for SYN/SYNACK */
- ASSERT (tc->state == TCP_STATE_SYN_RCVD
- || tc->state == TCP_STATE_SYN_SENT);
-
/* Try without increasing RTO a number of times. If this fails,
* start growing RTO exponentially */
if (tc->rto_boff > TCP_RTO_SYN_RETRIES)
@@ -1132,6 +1147,12 @@ tcp_timer_retransmit_handler_i (u32 index, u8 is_syn)
/* Account for the SYN */
tc->snd_nxt += 1;
}
+ else
+ {
+ ASSERT (tc->state == TCP_STATE_CLOSED);
+ clib_warning ("connection closed ...");
+ return;
+ }
if (!is_syn)
{
@@ -1180,7 +1201,8 @@ tcp_timer_persist_handler (u32 index)
u32 thread_index = vlib_get_thread_index ();
tcp_connection_t *tc;
vlib_buffer_t *b;
- u32 bi, n_bytes;
+ u32 bi, old_snd_nxt;
+ int n_bytes = 0;
tc = tcp_connection_get_if_valid (index, thread_index);
@@ -1202,13 +1224,15 @@ tcp_timer_persist_handler (u32 index)
/* Try to force the first unsent segment */
tcp_get_free_buffer_index (tm, &bi);
b = vlib_get_buffer (vm, bi);
+
+ tcp_validate_txf_size (tc, tc->snd_una_max - tc->snd_una);
tc->snd_opts_len = tcp_make_options (tc, &tc->snd_opts, tc->state);
n_bytes = stream_session_peek_bytes (&tc->connection,
vlib_buffer_get_current (b),
tc->snd_una_max - tc->snd_una,
tc->snd_mss);
/* Nothing to send */
- if (n_bytes == 0)
+ if (n_bytes <= 0)
{
clib_warning ("persist found nothing to send");
tcp_return_buffer (tm);
@@ -1216,7 +1240,13 @@ tcp_timer_persist_handler (u32 index)
}
b->current_length = n_bytes;
+ ASSERT (tc->snd_nxt == tc->snd_una_max || tc->rto_boff > 1
+ || tcp_timer_is_active (tc, TCP_TIMER_RETRANSMIT));
+
+ /* Allow updating of snd_una_max but don't update snd_nxt */
+ old_snd_nxt = tc->snd_nxt;
tcp_push_hdr_i (tc, b, tc->state, 0);
+ tc->snd_nxt = old_snd_nxt;
tcp_enqueue_to_output (vm, b, bi, tc->c_is_ip4);
/* Re-enable persist timer */
@@ -1232,8 +1262,9 @@ tcp_retransmit_first_unacked (tcp_connection_t * tc)
tcp_main_t *tm = vnet_get_tcp_main ();
vlib_main_t *vm = vlib_get_main ();
vlib_buffer_t *b;
- u32 bi, n_bytes;
+ u32 bi, n_bytes, old_snd_nxt;
+ old_snd_nxt = tc->snd_nxt;
tc->snd_nxt = tc->snd_una;
/* Get buffer */
@@ -1244,75 +1275,117 @@ tcp_retransmit_first_unacked (tcp_connection_t * tc)
n_bytes = tcp_prepare_retransmit_segment (tc, b, 0, tc->snd_mss);
if (n_bytes == 0)
- goto done;
+ {
+ tcp_return_buffer (tm);
+ goto done;
+ }
tcp_enqueue_to_output (vm, b, bi, tc->c_is_ip4);
done:
- tc->snd_nxt = tc->snd_una_max;
+ tc->snd_nxt = old_snd_nxt;
}
-sack_scoreboard_hole_t *
-scoreboard_first_rtx_hole (sack_scoreboard_t * sb)
+/**
+ * Do fast retransmit with SACKs
+ */
+void
+tcp_fast_retransmit_sack (tcp_connection_t * tc)
{
- sack_scoreboard_hole_t *hole = 0;
-
-// hole = scoreboard_first_hole (&tc->sack_sb);
-// if (hole)
-// {
-//
-// offset = hole->start - tc->snd_una;
-// hole_size = hole->end - hole->start;
-//
-// ASSERT(hole_size);
-//
-// if (hole_size < max_bytes)
-// max_bytes = hole_size;
-// }
- return hole;
+ tcp_main_t *tm = vnet_get_tcp_main ();
+ vlib_main_t *vm = vlib_get_main ();
+ u32 n_written = 0, offset = 0, max_bytes;
+ vlib_buffer_t *b;
+ sack_scoreboard_hole_t *hole;
+ sack_scoreboard_t *sb;
+ u32 bi, old_snd_nxt;
+ int snd_space;
+ u8 snd_limited = 0, can_rescue = 0;
+
+ ASSERT (tcp_in_fastrecovery (tc));
+ TCP_EVT_DBG (TCP_EVT_CC_EVT, tc, 0);
+
+ old_snd_nxt = tc->snd_nxt;
+ sb = &tc->sack_sb;
+ snd_space = tcp_available_snd_space (tc);
+
+ hole = scoreboard_get_hole (sb, sb->cur_rxt_hole);
+ while (hole && snd_space > 0)
+ {
+ tcp_get_free_buffer_index (tm, &bi);
+ b = vlib_get_buffer (vm, bi);
+
+ hole = scoreboard_next_rxt_hole (sb, hole,
+ tcp_fastrecovery_sent_1_smss (tc),
+ &can_rescue, &snd_limited);
+ if (!hole)
+ {
+ if (!can_rescue || !(seq_lt (sb->rescue_rxt, tc->snd_una)
+ || seq_gt (sb->rescue_rxt,
+ tc->snd_congestion)))
+ break;
+
+ /* If rescue rxt undefined or less than snd_una then one segment of
+ * up to SMSS octets that MUST include the highest outstanding
+ * unSACKed sequence number SHOULD be returned, and RescueRxt set to
+ * RecoveryPoint. HighRxt MUST NOT be updated.
+ */
+ max_bytes = clib_min (tc->snd_mss, snd_space);
+ offset = tc->snd_congestion - tc->snd_una - max_bytes;
+ sb->rescue_rxt = tc->snd_congestion;
+ tc->snd_nxt = tc->snd_una + offset;
+ tcp_prepare_retransmit_segment (tc, b, offset, max_bytes);
+ tcp_enqueue_to_output (vm, b, bi, tc->c_is_ip4);
+ break;
+ }
+
+ max_bytes = snd_limited ? tc->snd_mss : hole->end - sb->high_rxt;
+ offset = sb->high_rxt - tc->snd_una;
+ tc->snd_nxt = tc->snd_una + offset;
+ n_written = tcp_prepare_retransmit_segment (tc, b, offset, max_bytes);
+
+ /* Nothing left to retransmit */
+ if (n_written == 0)
+ {
+ tcp_return_buffer (tm);
+ break;
+ }
+
+ sb->high_rxt += n_written;
+ tcp_enqueue_to_output (vm, b, bi, tc->c_is_ip4);
+ snd_space -= n_written;
+ }
+
+ /* If window allows, send 1 SMSS of new data */
+ tc->snd_nxt = old_snd_nxt;
}
/**
- * Do fast retransmit.
+ * Fast retransmit without SACK info
*/
void
-tcp_fast_retransmit (tcp_connection_t * tc)
+tcp_fast_retransmit_no_sack (tcp_connection_t * tc)
{
tcp_main_t *tm = vnet_get_tcp_main ();
vlib_main_t *vm = vlib_get_main ();
- u32 bi;
+ u32 n_written = 0, offset = 0, bi, old_snd_nxt;
int snd_space;
- u32 n_written = 0, offset = 0;
vlib_buffer_t *b;
- u8 use_sacks = 0;
ASSERT (tcp_in_fastrecovery (tc));
+ TCP_EVT_DBG (TCP_EVT_CC_EVT, tc, 0);
/* Start resending from first un-acked segment */
+ old_snd_nxt = tc->snd_nxt;
tc->snd_nxt = tc->snd_una;
-
snd_space = tcp_available_snd_space (tc);
- TCP_EVT_DBG (TCP_EVT_CC_EVT, tc, 0);
-
- /* If we have SACKs use them */
- if (tcp_opts_sack_permitted (&tc->opt)
- && scoreboard_first_hole (&tc->sack_sb))
- use_sacks = 0;
while (snd_space > 0)
{
tcp_get_free_buffer_index (tm, &bi);
b = vlib_get_buffer (vm, bi);
- if (use_sacks)
- {
- scoreboard_first_rtx_hole (&tc->sack_sb);
- }
- else
- {
- offset += n_written;
- }
-
+ offset += n_written;
n_written = tcp_prepare_retransmit_segment (tc, b, offset, snd_space);
/* Nothing left to retransmit */
@@ -1326,9 +1399,21 @@ tcp_fast_retransmit (tcp_connection_t * tc)
snd_space -= n_written;
}
- /* If window allows, send 1 SMSS of new data */
- if (seq_lt (tc->snd_nxt, tc->snd_congestion))
- tc->snd_nxt = tc->snd_congestion;
+ /* Restore snd_nxt. If window allows, send 1 SMSS of new data */
+ tc->snd_nxt = old_snd_nxt;
+}
+
+/**
+ * Do fast retransmit
+ */
+void
+tcp_fast_retransmit (tcp_connection_t * tc)
+{
+ if (tcp_opts_sack_permitted (&tc->rcv_opts)
+ && scoreboard_first_hole (&tc->sack_sb))
+ tcp_fast_retransmit_sack (tc);
+ else
+ tcp_fast_retransmit_no_sack (tc);
}
always_inline u32
@@ -1544,6 +1629,12 @@ tcp_push_header (transport_connection_t * tconn, vlib_buffer_t * b)
tc = (tcp_connection_t *) tconn;
tcp_push_hdr_i (tc, b, TCP_STATE_ESTABLISHED, 0);
+
+ if (tc->rtt_ts == 0)
+ {
+ tc->rtt_ts = tcp_time_now ();
+ tc->rtt_seq = tc->snd_nxt;
+ }
return 0;
}