2 * Copyright (c) 2016-2020 Netflix, Inc.
4 * Redistribution and use in source and binary forms, with or without
5 * modification, are permitted provided that the following conditions
7 * 1. Redistributions of source code must retain the above copyright
8 * notice, this list of conditions and the following disclaimer.
9 * 2. Redistributions in binary form must reproduce the above copyright
10 * notice, this list of conditions and the following disclaimer in the
11 * documentation and/or other materials provided with the distribution.
13 * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
14 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
15 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
16 * ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
17 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
18 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
19 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
20 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
21 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
22 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
28 #ifndef _NETINET_TCP_RACK_H_
29 #define _NETINET_TCP_RACK_H_
31 #define RACK_ACKED 0x0001/* The remote endpoint acked this */
32 #define RACK_TO_MIXED 0x0002/* A timeout occured that mixed the send order - not used */
33 #define RACK_DEFERRED 0x0004/* We can't use this for RTT calc - not used */
34 #define RACK_OVERMAX 0x0008/* We have more retran's then we can fit */
35 #define RACK_SACK_PASSED 0x0010/* A sack was done above this block */
36 #define RACK_WAS_SACKPASS 0x0020/* We retransmitted due to SACK pass */
37 #define RACK_HAS_FIN 0x0040/* segment is sent with fin */
38 #define RACK_TLP 0x0080/* segment sent as tail-loss-probe */
39 #define RACK_RWND_COLLAPSED 0x0100/* The peer collapsed the rwnd on the segment */
40 #define RACK_APP_LIMITED 0x0200/* We went app limited after this send */
41 #define RACK_WAS_ACKED 0x0400/* a RTO undid the ack, but it already had a rtt calc done */
42 #define RACK_HAS_SIN 0x0800/* SIN is on this guy */
43 #define RACK_NUM_OF_RETRANS 3
45 #define RACK_INITIAL_RTO 1000 /* 1 second in milli seconds */
47 #define RACK_REQ_AVG 4 /* Must be less than 256 */
50 uint32_t r_start; /* Sequence number of the segment */
51 uint32_t r_end; /* End seq, this is 1 beyond actually */
52 TAILQ_ENTRY(rack_sendmap) r_tnext; /* Time of transmit based next */
53 RB_ENTRY(rack_sendmap) r_next; /* RB Tree next */
54 uint32_t r_rtr_bytes; /* How many bytes have been retransmitted */
55 uint16_t r_rtr_cnt; /* Retran count, index this -1 to get time
57 uint16_t r_flags; /* Flags as defined above */
58 uint32_t r_tim_lastsent[RACK_NUM_OF_RETRANS];
59 uint32_t usec_orig_send; /* time of orginal send in useconds */
60 uint32_t r_nseq_appl; /* If this one is app limited, this is the nxt seq limited */
61 uint32_t r_ack_arrival; /* This is the time of ack-arrival (if SACK'd) */
62 uint8_t r_dupack; /* Dup ack count */
63 uint8_t r_in_tmap; /* Flag to see if its in the r_tnext array */
64 uint8_t r_limit_type; /* is this entry counted against a limit? */
65 uint8_t r_just_ret : 1, /* After sending, the next pkt was just returned, i.e. limited */
66 r_one_out_nr : 1, /* Special case 1 outstanding and not in recovery */
71 RB_HEAD(rack_rb_tree_head, rack_sendmap);
72 TAILQ_HEAD(rack_head, rack_sendmap);
74 #define RACK_LIMIT_TYPE_SPLIT 1
77 * We use the rate sample structure to
78 * assist in single sack/ack rate and rtt
79 * calculation. In the future we will expand
80 * this in BBR to do forward rate sample
83 #define RACK_RTT_EMPTY 0x00000001 /* Nothing yet stored in RTT's */
84 #define RACK_RTT_VALID 0x00000002 /* We have at least one valid RTT */
85 struct rack_rtt_sample {
87 uint32_t rs_rtt_lowest;
88 uint32_t rs_rtt_highest;
93 uint16_t rs_us_rtrcnt;
96 #define RACK_LOG_TYPE_ACK 0x01
97 #define RACK_LOG_TYPE_OUT 0x02
98 #define RACK_LOG_TYPE_TO 0x03
99 #define RACK_LOG_TYPE_ALLOC 0x04
100 #define RACK_LOG_TYPE_FREE 0x05
105 struct rack_sendmap *rsm; /* For alloc/free */
106 uint64_t sb_acc;/* For out/ack or t-o */
111 uint32_t snd_nxt; /* th_win for TYPE_ACK */
113 uint32_t blk_start[4];
117 uint16_t len; /* Timeout T3=1, TLP=2, RACK=3 */
121 * Magic numbers for logging timeout events if the
122 * logging is enabled.
124 #define RACK_TO_FRM_TMR 1
125 #define RACK_TO_FRM_TLP 2
126 #define RACK_TO_FRM_RACK 3
127 #define RACK_TO_FRM_KEEP 4
128 #define RACK_TO_FRM_PERSIST 5
129 #define RACK_TO_FRM_DELACK 6
131 struct rack_opts_stats {
132 uint64_t tcp_rack_prop_rate;
133 uint64_t tcp_rack_prop;
134 uint64_t tcp_rack_tlp_reduce;
135 uint64_t tcp_rack_early_recov;
136 uint64_t tcp_rack_pace_always;
137 uint64_t tcp_rack_pace_reduce;
138 uint64_t tcp_rack_max_seg;
139 uint64_t tcp_rack_prr_sendalot;
140 uint64_t tcp_rack_min_to;
141 uint64_t tcp_rack_early_seg;
142 uint64_t tcp_rack_reord_thresh;
143 uint64_t tcp_rack_reord_fade;
144 uint64_t tcp_rack_tlp_thresh;
145 uint64_t tcp_rack_pkt_delay;
146 uint64_t tcp_rack_tlp_inc_var;
147 uint64_t tcp_tlp_use;
148 uint64_t tcp_rack_idle_reduce;
149 uint64_t tcp_rack_idle_reduce_high;
150 uint64_t rack_no_timer_in_hpts;
151 uint64_t tcp_rack_min_pace_seg;
152 uint64_t tcp_rack_pace_rate_ca;
153 uint64_t tcp_rack_rr;
154 uint64_t tcp_rack_do_detection;
155 uint64_t tcp_rack_rrr_no_conf_rate;
156 uint64_t tcp_initial_rate;
157 uint64_t tcp_initial_win;
158 uint64_t tcp_hdwr_pacing;
159 uint64_t tcp_gp_inc_ss;
160 uint64_t tcp_gp_inc_ca;
161 uint64_t tcp_gp_inc_rec;
162 uint64_t tcp_rack_force_max_seg;
163 uint64_t tcp_rack_pace_rate_ss;
164 uint64_t tcp_rack_pace_rate_rec;
165 /* Temp counters for dsack */
166 uint64_t tcp_sack_path_1;
167 uint64_t tcp_sack_path_2a;
168 uint64_t tcp_sack_path_2b;
169 uint64_t tcp_sack_path_3;
170 uint64_t tcp_sack_path_4;
171 /* non temp counters */
172 uint64_t tcp_rack_scwnd;
173 uint64_t tcp_rack_noprr;
174 uint64_t tcp_rack_cfg_rate;
175 uint64_t tcp_timely_dyn;
176 uint64_t tcp_rack_mbufq;
180 uint64_t tcp_profile;
183 /* RTT shrink reasons */
184 #define RACK_RTTS_INIT 0
185 #define RACK_RTTS_NEWRTT 1
186 #define RACK_RTTS_EXITPROBE 2
187 #define RACK_RTTS_ENTERPROBE 3
188 #define RACK_RTTS_REACHTARGET 4
189 #define RACK_RTTS_SEEHBP 5
190 #define RACK_RTTS_NOBACKOFF 6
191 #define RACK_RTTS_SAFETY 7
193 #define RACK_USE_BEG 1
194 #define RACK_USE_END 2
195 #define RACK_USE_END_OR_THACK 3
197 #define TLP_USE_ID 1 /* Internet draft behavior */
198 #define TLP_USE_TWO_ONE 2 /* Use 2.1 behavior */
199 #define TLP_USE_TWO_TWO 3 /* Use 2.2 behavior */
200 #define RACK_MIN_BW 8000 /* 64kbps in Bps */
202 #define MIN_GP_WIN 6 /* We need at least 6 MSS in a GP measurement */
204 #define RACK_OPTS_SIZE (sizeof(struct rack_opts_stats)/sizeof(uint64_t))
205 extern counter_u64_t rack_opts_arry[RACK_OPTS_SIZE];
206 #define RACK_OPTS_ADD(name, amm) counter_u64_add(rack_opts_arry[(offsetof(struct rack_opts_stats, name)/sizeof(uint64_t))], (amm))
207 #define RACK_OPTS_INC(name) RACK_OPTS_ADD(name, 1)
210 * As we get each SACK we wade through the
211 * rc_map and mark off what is acked.
212 * We also increment rc_sacked as well.
214 * We also pay attention to missing entries
215 * based on the time and possibly mark them
216 * for retransmit. If we do and we are not already
217 * in recovery we enter recovery. In doing
218 * so we claer prr_delivered/holes_rxt and prr_sent_dur_rec.
219 * We also setup rc_next/rc_snd_nxt/rc_send_end so
220 * we will know where to send from. When not in
221 * recovery rc_next will be NULL and rc_snd_nxt should
224 * Whenever we retransmit from recovery we increment
225 * rc_holes_rxt as we retran a block and mark it as retransmitted
226 * with the time it was sent. During non-recovery sending we
227 * add to our map and note the time down of any send expanding
228 * the rc_map at the tail and moving rc_snd_nxt up with snd_max.
230 * In recovery during SACK/ACK processing if a chunk has
231 * been retransmitted and it is now acked, we decrement rc_holes_rxt.
232 * When we retransmit from the scoreboard we use
233 * rc_next and rc_snd_nxt/rc_send_end to help us
234 * find what needs to be retran.
236 * To calculate pipe we simply take (snd_max - snd_una) + rc_holes_rxt
237 * This gets us the effect of RFC6675 pipe, counting twice for
238 * bytes retransmitted.
241 #define TT_RACK_FR_TMR 0x2000
244 * Locking for the rack control block.
245 * a) Locked by INP_WLOCK
246 * b) Locked by the hpts-mutex
249 #define RACK_GP_HIST 4 /* How much goodput history do we maintain? */
251 struct rack_control {
252 /* Second cache line 0x40 from tcp_rack */
253 struct rack_rb_tree_head rc_mtree; /* Tree of all segments Lock(a) */
254 struct rack_head rc_tmap; /* List in transmit order Lock(a) */
255 struct rack_sendmap *rc_tlpsend; /* Remembered place for
256 * tlp_sending Lock(a) */
257 struct rack_sendmap *rc_resend; /* something we have been asked to
260 uint32_t saved_input_pkt;
261 uint32_t rc_hpts_flags;
262 uint32_t rc_fixed_pacing_rate_ca;
263 uint32_t rc_fixed_pacing_rate_rec;
264 uint32_t rc_fixed_pacing_rate_ss;
265 uint32_t cwnd_to_use; /* The cwnd in use */
266 uint32_t rc_timer_exp; /* If a timer ticks of expiry */
267 uint32_t rc_rack_min_rtt; /* lowest RTT seen Lock(a) */
268 uint32_t rc_rack_largest_cwnd; /* Largest CWND we have seen Lock(a) */
270 /* Third Cache line 0x80 */
271 struct rack_head rc_free; /* Allocation array */
272 uint32_t rc_time_last_sent; /* Time we last sent some data and
273 * logged it Lock(a). */
274 uint32_t rc_reorder_ts; /* Last time we saw reordering Lock(a) */
276 uint32_t rc_tlp_new_data; /* we need to send new-data on a TLP
278 uint32_t rc_prr_out; /* bytes sent during recovery Lock(a) */
280 uint32_t rc_prr_recovery_fs; /* recovery fs point Lock(a) */
282 uint32_t rc_prr_sndcnt; /* Prr sndcnt Lock(a) */
284 uint32_t rc_sacked; /* Tot sacked on scoreboard Lock(a) */
285 uint32_t xxx_rc_last_tlp_seq; /* Last tlp sequence Lock(a) */
287 uint32_t rc_prr_delivered; /* during recovery prr var Lock(a) */
288 uint16_t rc_tlp_cnt_out; /* count of times we have sent a TLP without new data */
289 uint16_t xxx_rc_tlp_seg_send_cnt; /* Number of times we have TLP sent
290 * rc_last_tlp_seq Lock(a) */
292 uint32_t rc_loss_count; /* How many bytes have been retransmitted
294 uint32_t rc_reorder_fade; /* Socket option value Lock(a) */
296 /* Forth cache line 0xc0 */
299 uint32_t rc_rack_tmit_time; /* Rack transmit time Lock(a) */
300 uint32_t rc_holes_rxt; /* Tot retraned from scoreboard Lock(a) */
302 /* Variables to track bad retransmits and recover */
303 uint32_t rc_rsm_start; /* RSM seq number we retransmitted Lock(a) */
304 uint32_t rc_cwnd_at; /* cwnd at the retransmit Lock(a) */
306 uint32_t rc_ssthresh_at;/* ssthresh at the retransmit Lock(a) */
307 uint32_t rc_num_maps_alloced; /* Number of map blocks (sacks) we
309 uint32_t rc_rcvtime; /* When we last received data */
310 uint32_t rc_num_split_allocs; /* num split map entries allocated */
312 uint32_t rc_last_output_to;
313 uint32_t rc_went_idle_time;
315 struct rack_sendmap *rc_sacklast; /* sack remembered place
318 struct rack_sendmap *rc_rsm_at_retran; /* Debug variable kept for
319 * cache line alignment
321 struct rack_sendmap *rc_first_appl; /* Pointer to first app limited */
322 struct rack_sendmap *rc_end_appl; /* Pointer to last app limited */
323 /* Cache line split 0x100 */
324 struct sack_filter rack_sf;
325 /* Cache line split 0x140 */
326 /* Flags for various things */
327 uint32_t last_pacing_time;
328 uint32_t rc_pace_max_segs;
329 uint32_t rc_pace_min_segs;
330 uint32_t rc_app_limited_cnt;
331 uint16_t rack_per_of_gp_ss; /* 100 = 100%, so from 65536 = 655 x bw */
332 uint16_t rack_per_of_gp_ca; /* 100 = 100%, so from 65536 = 655 x bw */
333 uint16_t rack_per_of_gp_rec; /* 100 = 100%, so from 65536 = 655 x bw, 0=off */
334 uint16_t rack_per_of_gp_probertt; /* 100 = 100%, so from 65536 = 655 x bw, 0=off */
335 uint32_t rc_high_rwnd;
338 uint32_t sack_noextra_move;
339 uint32_t sack_moved_extra;
340 struct rack_rtt_sample rack_rs;
341 const struct tcp_hwrate_limit_table *crte;
342 uint32_t rc_agg_early;
343 uint32_t rc_agg_delayed;
344 uint32_t rc_tlp_rxt_last_time;
345 uint32_t rc_saved_cwnd;
346 uint32_t rc_gp_output_ts;
347 uint32_t rc_gp_cumack_ts;
348 struct timeval act_rcv_time;
349 struct timeval rc_last_time_decay; /* SAD time decay happened here */
352 #ifdef NETFLIX_SHARED_CWND
353 struct shared_cwnd *rc_scw;
355 uint64_t last_gp_comp_bw;
356 uint64_t last_max_bw; /* Our calculated max b/w last */
357 struct time_filter_small rc_gp_min_rtt;
358 int32_t rc_rtt_diff; /* Timely style rtt diff of our gp_srtt */
359 uint32_t rc_gp_srtt; /* Current GP srtt */
360 uint32_t rc_prev_gp_srtt; /* Previous RTT */
361 uint32_t rc_entry_gp_rtt; /* Entry to PRTT gp-rtt */
362 uint32_t rc_loss_at_start; /* At measurement window where was our lost value */
364 uint32_t forced_ack_ts;
365 uint32_t rc_lower_rtt_us_cts; /* Time our GP rtt was last lowered */
366 uint32_t rc_time_probertt_entered;
367 uint32_t rc_time_probertt_starts;
368 uint32_t rc_lowest_us_rtt;
369 uint32_t rc_highest_us_rtt;
370 uint32_t rc_last_us_rtt;
371 uint32_t rc_time_of_last_probertt;
372 uint32_t rc_target_probertt_flight;
373 uint32_t rc_probertt_sndmax_atexit; /* Highest sent to in probe-rtt */
374 uint32_t rc_gp_lowrtt; /* Lowest rtt seen during GPUT measurement */
375 uint32_t rc_gp_high_rwnd; /* Highest rwnd seen during GPUT measurement */
376 int32_t rc_scw_index;
377 uint32_t rc_tlp_threshold; /* Socket option value Lock(a) */
378 uint16_t rc_early_recovery_segs; /* Socket option value Lock(a) */
379 uint16_t rc_reorder_shift; /* Socket option value Lock(a) */
380 uint16_t rc_pkt_delay; /* Socket option value Lock(a) */
381 uint8_t rc_no_push_at_mrtt; /* No push when we exceed max rtt */
382 uint8_t num_avg; /* average count before we go to normal decay */
383 uint8_t rc_prop_rate; /* Socket option value Lock(a) */
384 uint8_t rc_prop_reduce; /* Socket option value Lock(a) */
385 uint8_t rc_tlp_cwnd_reduce; /* Socket option value Lock(a) */
386 uint8_t rc_early_recovery; /* Socket option value Lock(a) */
387 uint8_t rc_prr_sendalot;/* Socket option value Lock(a) */
388 uint8_t rc_min_to; /* Socket option value Lock(a) */
389 uint8_t rc_rate_sample_method;
390 uint8_t rc_gp_hist_idx;
393 #define RACK_TIMELY_CNT_BOOST 5 /* At 5th increase boost */
394 #define RACK_MINRTT_FILTER_TIM 10 /* Seconds */
399 /* First cache line 0x00 */
400 TAILQ_ENTRY(tcp_rack) r_hpts; /* hptsi queue next Lock(b) */
401 int32_t(*r_substate) (struct mbuf *, struct tcphdr *,
402 struct socket *, struct tcpcb *, struct tcpopt *,
403 int32_t, int32_t, uint32_t, int, int, uint8_t); /* Lock(a) */
404 struct tcpcb *rc_tp; /* The tcpcb Lock(a) */
405 struct inpcb *rc_inp; /* The inpcb Lock(a) */
406 uint32_t rc_free_cnt; /* Number of free entries on the rc_free list
408 uint32_t rc_rack_rtt; /* RACK-RTT Lock(a) */
409 uint16_t r_mbuf_queue : 1, /* Do we do mbuf queue for non-paced */
410 rtt_limit_mul : 4, /* muliply this by low rtt */
412 r_avail_bits : 10; /* Available */
414 uint16_t rc_user_set_max_segs; /* Socket option value Lock(a) */
415 uint16_t forced_ack : 1,
418 rc_gp_timely_inc_cnt : 3,
419 rc_gp_timely_dec_cnt : 3,
420 rc_not_backing_off: 1,
421 rc_highly_buffered: 1, /* The path is highly buffered */
422 rc_dragged_bottom: 1,
423 rc_dack_mode : 1, /* Mac O/S emulation of d-ack */
424 rc_dack_toggle : 1, /* For Mac O/S emulation of d-ack */
425 pacing_longer_than_rtt : 1,
427 uint8_t r_state; /* Current rack state Lock(a) */
428 uint8_t rc_tmr_stopped : 7,
429 t_timers_stopped : 1;
430 uint8_t rc_enobuf : 7, /* count of enobufs on connection provides */
432 uint8_t r_timer_override : 1, /* hpts override Lock(a) */
433 r_is_v6 : 1, /* V6 pcb Lock(a) */
435 rc_tlp_in_progress : 1,
436 rc_always_pace : 1, /* Socket option value Lock(a) */
438 rc_pace_fill_if_rttin_range : 1,
440 uint8_t app_limited_needs_set : 1,
442 rc_has_collapsed : 1,
445 rack_hdrw_pacing : 1, /* We are doing Hardware pacing */
446 rack_hdw_pace_ena : 1, /* Is hardware pacing enabled? */
447 rack_attempt_hdwr_pace : 1; /* Did we attempt hdwr pacing (if allowed) */
448 uint8_t rack_tlp_threshold_use : 3, /* only 1, 2 and 3 used so far */
449 rack_rec_nonrxt_use_cr : 1,
450 rack_enable_scwnd : 1,
451 rack_attempted_scwnd : 1,
453 rack_scwnd_is_idle : 1;
454 uint8_t rc_allow_data_af_clo: 1,
456 set_pacing_done_a_iw : 1,
458 alloc_limit_reported : 1,
459 sack_attack_disable : 1,
461 rc_force_max_seg : 1;
462 uint8_t rack_cwnd_limited : 1,
469 uint16_t rc_init_win : 8,
475 rc_gp_no_rec_chg : 1,
477 measure_saw_probe_rtt : 1;
478 /* Cache line 2 0x40 */
479 struct rack_control r_ctl;
480 } __aligned(CACHE_LINE_SIZE);