2 * Copyright (c) 2016-9 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_NUM_OF_RETRANS 3
42 #define RACK_INITIAL_RTO 1000 /* 1 second in milli seconds */
45 uint32_t r_start; /* Sequence number of the segment */
46 uint32_t r_end; /* End seq, this is 1 beyond actually */
47 TAILQ_ENTRY(rack_sendmap) r_tnext; /* Time of transmit based next */
48 RB_ENTRY(rack_sendmap) r_next; /* RB Tree next */
49 uint32_t r_rtr_bytes; /* How many bytes have been retransmitted */
50 uint16_t r_rtr_cnt; /* Retran count, index this -1 to get time
52 uint16_t r_flags; /* Flags as defined above */
53 uint32_t r_tim_lastsent[RACK_NUM_OF_RETRANS];
54 uint8_t r_dupack; /* Dup ack count */
55 uint8_t r_in_tmap; /* Flag to see if its in the r_tnext array */
56 uint8_t r_limit_type; /* is this entry counted against a limit? */
60 RB_HEAD(rack_rb_tree_head, rack_sendmap);
61 TAILQ_HEAD(rack_head, rack_sendmap);
63 #define RACK_LIMIT_TYPE_SPLIT 1
66 * We use the rate sample structure to
67 * assist in single sack/ack rate and rtt
68 * calculation. In the future we will expand
69 * this in BBR to do forward rate sample
72 #define RACK_RTT_EMPTY 0x00000001 /* Nothing yet stored in RTT's */
73 #define RACK_RTT_VALID 0x00000002 /* We have at least one valid RTT */
74 struct rack_rtt_sample {
76 uint32_t rs_rtt_lowest;
77 uint32_t rs_rtt_highest;
82 #define RACK_LOG_TYPE_ACK 0x01
83 #define RACK_LOG_TYPE_OUT 0x02
84 #define RACK_LOG_TYPE_TO 0x03
85 #define RACK_LOG_TYPE_ALLOC 0x04
86 #define RACK_LOG_TYPE_FREE 0x05
91 struct rack_sendmap *rsm; /* For alloc/free */
92 uint64_t sb_acc;/* For out/ack or t-o */
97 uint32_t snd_nxt; /* th_win for TYPE_ACK */
99 uint32_t blk_start[4];
103 uint16_t len; /* Timeout T3=1, TLP=2, RACK=3 */
107 * Magic numbers for logging timeout events if the
108 * logging is enabled.
110 #define RACK_TO_FRM_TMR 1
111 #define RACK_TO_FRM_TLP 2
112 #define RACK_TO_FRM_RACK 3
113 #define RACK_TO_FRM_KEEP 4
114 #define RACK_TO_FRM_PERSIST 5
115 #define RACK_TO_FRM_DELACK 6
117 struct rack_opts_stats {
118 uint64_t tcp_rack_prop_rate;
119 uint64_t tcp_rack_prop;
120 uint64_t tcp_rack_tlp_reduce;
121 uint64_t tcp_rack_early_recov;
122 uint64_t tcp_rack_pace_always;
123 uint64_t tcp_rack_pace_reduce;
124 uint64_t tcp_rack_max_seg;
125 uint64_t tcp_rack_prr_sendalot;
126 uint64_t tcp_rack_min_to;
127 uint64_t tcp_rack_early_seg;
128 uint64_t tcp_rack_reord_thresh;
129 uint64_t tcp_rack_reord_fade;
130 uint64_t tcp_rack_tlp_thresh;
131 uint64_t tcp_rack_pkt_delay;
132 uint64_t tcp_rack_tlp_inc_var;
133 uint64_t tcp_tlp_use;
134 uint64_t tcp_rack_idle_reduce;
135 uint64_t tcp_rack_idle_reduce_high;
136 uint64_t rack_no_timer_in_hpts;
137 uint64_t tcp_rack_min_pace_seg;
138 uint64_t tcp_rack_min_pace;
139 uint64_t tcp_rack_cheat;
140 uint64_t tcp_rack_do_detection;
143 #define TLP_USE_ID 1 /* Internet draft behavior */
144 #define TLP_USE_TWO_ONE 2 /* Use 2.1 behavior */
145 #define TLP_USE_TWO_TWO 3 /* Use 2.2 behavior */
148 #define RACK_OPTS_SIZE (sizeof(struct rack_opts_stats)/sizeof(uint64_t))
149 extern counter_u64_t rack_opts_arry[RACK_OPTS_SIZE];
150 #define RACK_OPTS_ADD(name, amm) counter_u64_add(rack_opts_arry[(offsetof(struct rack_opts_stats, name)/sizeof(uint64_t))], (amm))
151 #define RACK_OPTS_INC(name) RACK_OPTS_ADD(name, 1)
154 * As we get each SACK we wade through the
155 * rc_map and mark off what is acked.
156 * We also increment rc_sacked as well.
158 * We also pay attention to missing entries
159 * based on the time and possibly mark them
160 * for retransmit. If we do and we are not already
161 * in recovery we enter recovery. In doing
162 * so we claer prr_delivered/holes_rxt and prr_sent_dur_rec.
163 * We also setup rc_next/rc_snd_nxt/rc_send_end so
164 * we will know where to send from. When not in
165 * recovery rc_next will be NULL and rc_snd_nxt should
168 * Whenever we retransmit from recovery we increment
169 * rc_holes_rxt as we retran a block and mark it as retransmitted
170 * with the time it was sent. During non-recovery sending we
171 * add to our map and note the time down of any send expanding
172 * the rc_map at the tail and moving rc_snd_nxt up with snd_max.
174 * In recovery during SACK/ACK processing if a chunk has
175 * been retransmitted and it is now acked, we decrement rc_holes_rxt.
176 * When we retransmit from the scoreboard we use
177 * rc_next and rc_snd_nxt/rc_send_end to help us
178 * find what needs to be retran.
180 * To calculate pipe we simply take (snd_max - snd_una) + rc_holes_rxt
181 * This gets us the effect of RFC6675 pipe, counting twice for
182 * bytes retransmitted.
185 #define TT_RACK_FR_TMR 0x2000
188 * Locking for the rack control block.
189 * a) Locked by INP_WLOCK
190 * b) Locked by the hpts-mutex
193 #define RACK_GP_HIST 4 /* How much goodput history do we maintain? */
195 struct rack_control {
196 /* Second cache line 0x40 from tcp_rack */
197 struct rack_rb_tree_head rc_mtree; /* Tree of all segments Lock(a) */
198 struct rack_head rc_tmap; /* List in transmit order Lock(a) */
199 struct rack_sendmap *rc_tlpsend; /* Remembered place for
200 * tlp_sending Lock(a) */
201 struct rack_sendmap *rc_resend; /* something we have been asked to
203 struct timeval rc_last_time_decay; /* SAD time decay happened here */
205 uint32_t saved_input_pkt;
206 uint32_t rc_hpts_flags;
207 uint32_t rc_timer_exp; /* If a timer ticks of expiry */
208 uint32_t rc_rack_min_rtt; /* lowest RTT seen Lock(a) */
209 uint32_t rc_rack_largest_cwnd; /* Largest CWND we have seen Lock(a) */
211 /* Third Cache line 0x80 */
212 struct rack_head rc_free; /* Allocation array */
213 uint32_t rc_time_last_sent; /* Time we last sent some data and
214 * logged it Lock(a). */
215 uint32_t rc_reorder_ts; /* Last time we saw reordering Lock(a) */
217 uint32_t rc_tlp_new_data; /* we need to send new-data on a TLP
219 uint32_t rc_prr_out; /* bytes sent during recovery Lock(a) */
221 uint32_t rc_prr_recovery_fs; /* recovery fs point Lock(a) */
223 uint32_t rc_prr_sndcnt; /* Prr sndcnt Lock(a) */
225 uint32_t rc_sacked; /* Tot sacked on scoreboard Lock(a) */
226 uint32_t rc_last_tlp_seq; /* Last tlp sequence Lock(a) */
228 uint32_t rc_prr_delivered; /* during recovery prr var Lock(a) */
229 uint16_t rc_tlp_send_cnt; /* Number of TLP sends we have done
230 * since peer spoke to us Lock(a) */
231 uint16_t rc_tlp_seg_send_cnt; /* Number of times we have TLP sent
232 * rc_last_tlp_seq Lock(a) */
234 uint32_t rc_loss_count; /* During recovery how many segments were lost
236 uint32_t rc_reorder_fade; /* Socket option value Lock(a) */
238 /* Forth cache line 0xc0 */
241 uint32_t rc_rack_tmit_time; /* Rack transmit time Lock(a) */
242 uint32_t rc_holes_rxt; /* Tot retraned from scoreboard Lock(a) */
244 /* Variables to track bad retransmits and recover */
245 uint32_t rc_rsm_start; /* RSM seq number we retransmitted Lock(a) */
246 uint32_t rc_cwnd_at; /* cwnd at the retransmit Lock(a) */
248 uint32_t rc_ssthresh_at;/* ssthresh at the retransmit Lock(a) */
249 uint32_t rc_num_maps_alloced; /* Number of map blocks (sacks) we
251 uint32_t rc_rcvtime; /* When we last received data */
252 uint32_t rc_num_split_allocs; /* num split map entries allocated */
254 uint32_t rc_last_output_to;
255 uint32_t rc_went_idle_time;
257 struct rack_sendmap *rc_sacklast; /* sack remembered place
260 struct rack_sendmap *rc_rsm_at_retran; /* Debug variable kept for
261 * cache line alignment
263 struct timeval rc_last_ack;
264 /* Cache line split 0x100 */
265 struct sack_filter rack_sf;
266 /* Cache line split 0x140 */
267 /* Flags for various things */
268 uint32_t rc_pace_max_segs;
269 uint32_t rc_pace_min_segs;
270 uint32_t rc_high_rwnd;
273 uint32_t sack_noextra_move;
274 uint32_t sack_moved_extra;
275 struct rack_rtt_sample rack_rs;
276 uint32_t rc_tlp_rxt_last_time;
277 uint32_t rc_saved_cwnd;
278 uint32_t rc_gp_history[RACK_GP_HIST];
279 uint32_t rc_tlp_threshold; /* Socket option value Lock(a) */
280 uint16_t rc_early_recovery_segs; /* Socket option value Lock(a) */
281 uint16_t rc_reorder_shift; /* Socket option value Lock(a) */
282 uint16_t rc_pkt_delay; /* Socket option value Lock(a) */
283 uint8_t rc_prop_rate; /* Socket option value Lock(a) */
284 uint8_t rc_prop_reduce; /* Socket option value Lock(a) */
285 uint8_t rc_tlp_cwnd_reduce; /* Socket option value Lock(a) */
286 uint8_t rc_early_recovery; /* Socket option value Lock(a) */
287 uint8_t rc_prr_sendalot;/* Socket option value Lock(a) */
288 uint8_t rc_min_to; /* Socket option value Lock(a) */
289 uint8_t rc_tlp_rtx_out; /* This is TLPRtxOut in the draft */
290 uint8_t rc_rate_sample_method;
291 uint8_t rc_gp_hist_idx: 7,
292 rc_gp_hist_filled: 1;
299 /* First cache line 0x00 */
300 TAILQ_ENTRY(tcp_rack) r_hpts; /* hptsi queue next Lock(b) */
301 int32_t(*r_substate) (struct mbuf *, struct tcphdr *,
302 struct socket *, struct tcpcb *, struct tcpopt *,
303 int32_t, int32_t, uint32_t, int, int, uint8_t); /* Lock(a) */
304 struct tcpcb *rc_tp; /* The tcpcb Lock(a) */
305 struct inpcb *rc_inp; /* The inpcb Lock(a) */
306 uint32_t rc_free_cnt; /* Number of free entries on the rc_free list
308 uint32_t rc_rack_rtt; /* RACK-RTT Lock(a) */
309 uint16_t r_wanted_output; /* Output routine wanted to be called */
310 uint16_t r_cpu; /* CPU that the INP is running on Lock(a) */
311 uint16_t rc_pace_max_segs; /* Socket option value Lock(a) */
312 uint16_t rc_pace_reduce;/* Socket option value Lock(a) */
314 uint8_t r_state; /* Current rack state Lock(a) */
315 uint8_t rc_tmr_stopped : 7,
316 t_timers_stopped : 1;
317 uint8_t rc_enobuf; /* count of enobufs on connection provides
319 uint8_t r_timer_override : 1, /* hpts override Lock(a) */
320 r_tlp_running : 1, /* Running from a TLP timeout Lock(a) */
321 r_is_v6 : 1, /* V6 pcb Lock(a) */
323 rc_last_pto_set : 1, /* XXX not used */
324 rc_tlp_in_progress : 1,
325 rc_always_pace : 1, /* Socket option value Lock(a) */
326 tlp_timer_up : 1; /* The tlp timer is up flag Lock(a) */
327 uint8_t r_enforce_min_pace : 2,
328 rc_has_collapsed : 1,
331 r_xxx_min_pace_seg_thresh : 3;
332 uint8_t rack_tlp_threshold_use;
333 uint8_t rc_allow_data_af_clo: 1,
335 set_pacing_done_a_iw : 1,
337 alloc_limit_reported : 1,
338 sack_attack_disable : 1,
341 uint16_t rack_per_of_gp;
342 /* Cache line 2 0x40 */
343 struct rack_control r_ctl;
344 } __aligned(CACHE_LINE_SIZE);