1 /*- 2 * Copyright (c) 2016 3 * Netflix Inc. All rights reserved. 4 * 5 * Redistribution and use in source and binary forms, with or without 6 * modification, are permitted provided that the following conditions 7 * are met: 8 * 1. Redistributions of source code must retain the above copyright 9 * notice, this list of conditions and the following disclaimer. 10 * 2. Redistributions in binary form must reproduce the above copyright 11 * notice, this list of conditions and the following disclaimer in the 12 * documentation and/or other materials provided with the distribution. 13 * 14 * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND 15 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE 16 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE 17 * ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE 18 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL 19 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS 20 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) 21 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT 22 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY 23 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF 24 * SUCH DAMAGE. 25 * 26 * $FreeBSD$ 27 */ 28 29 #ifndef _NETINET_TCP_RACK_H_ 30 #define _NETINET_TCP_RACK_H_ 31 32 #define RACK_ACKED 0x0001/* The remote endpoint acked this */ 33 #define RACK_TO_MIXED 0x0002/* A timeout occured that mixed the send order */ 34 #define RACK_DEFERRED 0x0004/* We can't use this for RTT calc */ 35 #define RACK_OVERMAX 0x0008/* We have more retran's then we can fit */ 36 #define RACK_SACK_PASSED 0x0010/* A sack was done above this block */ 37 #define RACK_WAS_SACKPASS 0x0020/* We retransmitted due to SACK pass */ 38 #define RACK_HAS_FIN 0x0040/* segment is sent with fin */ 39 #define RACK_TLP 0x0080/* segment sent as tail-loss-probe */ 40 41 #define RACK_NUM_OF_RETRANS 3 42 43 #define RACK_INITIAL_RTO 1000 /* 1 second in milli seconds */ 44 45 struct rack_sendmap { 46 TAILQ_ENTRY(rack_sendmap) r_next; /* seq number arrayed next */ 47 TAILQ_ENTRY(rack_sendmap) r_tnext; /* Time of transmit based next */ 48 uint32_t r_tim_lastsent[RACK_NUM_OF_RETRANS]; 49 uint32_t r_start; /* Sequence number of the segment */ 50 uint32_t r_end; /* End seq, this is 1 beyond actually */ 51 uint32_t r_rtr_bytes; /* How many bytes have been retransmitted */ 52 uint16_t r_rtr_cnt; /* Retran count, index this -1 to get time 53 * sent */ 54 uint8_t r_flags; /* Flags as defined above */ 55 uint8_t r_sndcnt; /* Retran count, not limited by 56 * RACK_NUM_OF_RETRANS */ 57 uint8_t r_in_tmap; /* Flag to see if its in the r_tnext array */ 58 uint8_t r_resv[3]; 59 }; 60 61 TAILQ_HEAD(rack_head, rack_sendmap); 62 63 64 /* 65 * We use the rate sample structure to 66 * assist in single sack/ack rate and rtt 67 * calculation. In the future we will expand 68 * this in BBR to do forward rate sample 69 * b/w estimation. 70 */ 71 #define RACK_RTT_EMPTY 0x00000001 /* Nothing yet stored in RTT's */ 72 #define RACK_RTT_VALID 0x00000002 /* We have at least one valid RTT */ 73 struct rack_rtt_sample { 74 uint32_t rs_flags; 75 uint32_t rs_rtt_lowest; 76 uint32_t rs_rtt_highest; 77 uint32_t rs_rtt_cnt; 78 uint64_t rs_rtt_tot; 79 }; 80 81 #define RACK_LOG_TYPE_ACK 0x01 82 #define RACK_LOG_TYPE_OUT 0x02 83 #define RACK_LOG_TYPE_TO 0x03 84 #define RACK_LOG_TYPE_ALLOC 0x04 85 #define RACK_LOG_TYPE_FREE 0x05 86 87 88 struct rack_log { 89 union { 90 struct rack_sendmap *rsm; /* For alloc/free */ 91 uint64_t sb_acc;/* For out/ack or t-o */ 92 }; 93 uint32_t th_seq; 94 uint32_t th_ack; 95 uint32_t snd_una; 96 uint32_t snd_nxt; /* th_win for TYPE_ACK */ 97 uint32_t snd_max; 98 uint32_t blk_start[4]; 99 uint32_t blk_end[4]; 100 uint8_t type; 101 uint8_t n_sackblks; 102 uint16_t len; /* Timeout T3=1, TLP=2, RACK=3 */ 103 }; 104 105 /* 106 * Magic numbers for logging timeout events if the 107 * logging is enabled. 108 */ 109 #define RACK_TO_FRM_TMR 1 110 #define RACK_TO_FRM_TLP 2 111 #define RACK_TO_FRM_RACK 3 112 #define RACK_TO_FRM_KEEP 4 113 #define RACK_TO_FRM_PERSIST 5 114 #define RACK_TO_FRM_DELACK 6 115 116 struct rack_opts_stats { 117 uint64_t tcp_rack_prop_rate; 118 uint64_t tcp_rack_prop; 119 uint64_t tcp_rack_tlp_reduce; 120 uint64_t tcp_rack_early_recov; 121 uint64_t tcp_rack_pace_always; 122 uint64_t tcp_rack_pace_reduce; 123 uint64_t tcp_rack_max_seg; 124 uint64_t tcp_rack_prr_sendalot; 125 uint64_t tcp_rack_min_to; 126 uint64_t tcp_rack_early_seg; 127 uint64_t tcp_rack_reord_thresh; 128 uint64_t tcp_rack_reord_fade; 129 uint64_t tcp_rack_tlp_thresh; 130 uint64_t tcp_rack_pkt_delay; 131 uint64_t tcp_rack_tlp_inc_var; 132 uint64_t tcp_tlp_use; 133 uint64_t tcp_rack_idle_reduce; 134 uint64_t tcp_rack_idle_reduce_high; 135 uint64_t rack_no_timer_in_hpts; 136 uint64_t tcp_rack_min_pace_seg; 137 uint64_t tcp_rack_min_pace; 138 }; 139 140 #define TLP_USE_ID 1 /* Internet draft behavior */ 141 #define TLP_USE_TWO_ONE 2 /* Use 2.1 behavior */ 142 #define TLP_USE_TWO_TWO 3 /* Use 2.2 behavior */ 143 144 #ifdef _KERNEL 145 #define RACK_OPTS_SIZE (sizeof(struct rack_opts_stats)/sizeof(uint64_t)) 146 extern counter_u64_t rack_opts_arry[RACK_OPTS_SIZE]; 147 #define RACK_OPTS_ADD(name, amm) counter_u64_add(rack_opts_arry[(offsetof(struct rack_opts_stats, name)/sizeof(uint64_t))], (amm)) 148 #define RACK_OPTS_INC(name) RACK_OPTS_ADD(name, 1) 149 #endif 150 /* 151 * As we get each SACK we wade through the 152 * rc_map and mark off what is acked. 153 * We also increment rc_sacked as well. 154 * 155 * We also pay attention to missing entries 156 * based on the time and possibly mark them 157 * for retransmit. If we do and we are not already 158 * in recovery we enter recovery. In doing 159 * so we claer prr_delivered/holes_rxt and prr_sent_dur_rec. 160 * We also setup rc_next/rc_snd_nxt/rc_send_end so 161 * we will know where to send from. When not in 162 * recovery rc_next will be NULL and rc_snd_nxt should 163 * equal snd_max. 164 * 165 * Whenever we retransmit from recovery we increment 166 * rc_holes_rxt as we retran a block and mark it as retransmitted 167 * with the time it was sent. During non-recovery sending we 168 * add to our map and note the time down of any send expanding 169 * the rc_map at the tail and moving rc_snd_nxt up with snd_max. 170 * 171 * In recovery during SACK/ACK processing if a chunk has 172 * been retransmitted and it is now acked, we decrement rc_holes_rxt. 173 * When we retransmit from the scoreboard we use 174 * rc_next and rc_snd_nxt/rc_send_end to help us 175 * find what needs to be retran. 176 * 177 * To calculate pipe we simply take (snd_max - snd_una) + rc_holes_rxt 178 * This gets us the effect of RFC6675 pipe, counting twice for 179 * bytes retransmitted. 180 */ 181 182 #define TT_RACK_FR_TMR 0x2000 183 184 /* 185 * Locking for the rack control block. 186 * a) Locked by INP_WLOCK 187 * b) Locked by the hpts-mutex 188 * 189 */ 190 191 struct rack_control { 192 /* Second cache line 0x40 from tcp_rack */ 193 struct rack_head rc_map;/* List of all segments Lock(a) */ 194 struct rack_head rc_tmap; /* List in transmit order Lock(a) */ 195 struct rack_sendmap *rc_tlpsend; /* Remembered place for 196 * tlp_sending Lock(a) */ 197 struct rack_sendmap *rc_resend; /* something we have been asked to 198 * resend */ 199 uint32_t rc_hpts_flags; 200 uint32_t rc_timer_exp; /* If a timer ticks of expiry */ 201 uint32_t rc_rack_min_rtt; /* lowest RTT seen Lock(a) */ 202 uint32_t rc_rack_largest_cwnd; /* Largest CWND we have seen Lock(a) */ 203 204 /* Third Cache line 0x80 */ 205 struct rack_head rc_free; /* Allocation array */ 206 uint32_t rc_time_last_sent; /* Time we last sent some data and 207 * logged it Lock(a). */ 208 uint32_t rc_reorder_ts; /* Last time we saw reordering Lock(a) */ 209 210 uint32_t rc_tlp_new_data; /* we need to send new-data on a TLP 211 * Lock(a) */ 212 uint32_t rc_prr_out; /* bytes sent during recovery Lock(a) */ 213 214 uint32_t rc_prr_recovery_fs; /* recovery fs point Lock(a) */ 215 216 uint32_t rc_prr_sndcnt; /* Prr sndcnt Lock(a) */ 217 218 uint32_t rc_sacked; /* Tot sacked on scoreboard Lock(a) */ 219 uint32_t rc_last_tlp_seq; /* Last tlp sequence Lock(a) */ 220 221 uint32_t rc_prr_delivered; /* during recovery prr var Lock(a) */ 222 uint16_t rc_tlp_send_cnt; /* Number of TLP sends we have done 223 * since peer spoke to us Lock(a) */ 224 uint16_t rc_tlp_seg_send_cnt; /* Number of times we have TLP sent 225 * rc_last_tlp_seq Lock(a) */ 226 227 uint32_t rc_loss_count; /* During recovery how many segments were lost 228 * Lock(a) */ 229 uint32_t rc_reorder_fade; /* Socket option value Lock(a) */ 230 231 /* Forth cache line 0xc0 */ 232 /* Times */ 233 234 uint32_t rc_rack_tmit_time; /* Rack transmit time Lock(a) */ 235 uint32_t rc_holes_rxt; /* Tot retraned from scoreboard Lock(a) */ 236 237 /* Variables to track bad retransmits and recover */ 238 uint32_t rc_rsm_start; /* RSM seq number we retransmitted Lock(a) */ 239 uint32_t rc_cwnd_at; /* cwnd at the retransmit Lock(a) */ 240 241 uint32_t rc_ssthresh_at;/* ssthresh at the retransmit Lock(a) */ 242 uint32_t rc_num_maps_alloced; /* Number of map blocks (sacks) we 243 * have allocated */ 244 uint32_t rc_rcvtime; /* When we last received data */ 245 uint32_t rc_notused; 246 uint32_t rc_last_output_to; 247 uint32_t rc_went_idle_time; 248 249 struct rack_sendmap *rc_sacklast; /* sack remembered place 250 * Lock(a) */ 251 252 struct rack_sendmap *rc_next; /* remembered place where we next 253 * retransmit at Lock(a) */ 254 struct rack_sendmap *rc_rsm_at_retran; /* Debug variable kept for 255 * cache line alignment 256 * Lock(a) */ 257 /* Cache line split 0x100 */ 258 struct sack_filter rack_sf; 259 /* Cache line split 0x140 */ 260 /* Flags for various things */ 261 struct rack_rtt_sample rack_rs; 262 uint32_t rc_tlp_threshold; /* Socket option value Lock(a) */ 263 uint16_t rc_early_recovery_segs; /* Socket option value Lock(a) */ 264 uint16_t rc_reorder_shift; /* Socket option value Lock(a) */ 265 uint16_t rc_pkt_delay; /* Socket option value Lock(a) */ 266 uint8_t rc_prop_rate; /* Socket option value Lock(a) */ 267 uint8_t rc_prop_reduce; /* Socket option value Lock(a) */ 268 uint8_t rc_tlp_cwnd_reduce; /* Socket option value Lock(a) */ 269 uint8_t rc_early_recovery; /* Socket option value Lock(a) */ 270 uint8_t rc_prr_sendalot;/* Socket option value Lock(a) */ 271 uint8_t rc_min_to; /* Socket option value Lock(a) */ 272 uint8_t rc_prr_inc_var; /* Socket option value Lock(a) */ 273 uint8_t rc_tlp_rtx_out; /* This is TLPRtxOut in the draft */ 274 uint8_t rc_rate_sample_method; 275 }; 276 277 #ifdef _KERNEL 278 279 struct tcp_rack { 280 /* First cache line 0x00 */ 281 TAILQ_ENTRY(tcp_rack) r_hpts; /* hptsi queue next Lock(b) */ 282 int32_t(*r_substate) (struct mbuf *, struct tcphdr *, 283 struct socket *, struct tcpcb *, struct tcpopt *, 284 int32_t, int32_t, int32_t *, uint32_t, int, int); /* Lock(a) */ 285 struct tcpcb *rc_tp; /* The tcpcb Lock(a) */ 286 struct inpcb *rc_inp; /* The inpcb Lock(a) */ 287 uint32_t rc_free_cnt; /* Number of free entries on the rc_free list 288 * Lock(a) */ 289 uint32_t rc_rack_rtt; /* RACK-RTT Lock(a) */ 290 uint16_t r_wanted_output; /* Output routine wanted to be called */ 291 uint16_t r_cpu; /* CPU that the INP is running on Lock(a) */ 292 uint16_t rc_pace_max_segs; /* Socket option value Lock(a) */ 293 uint16_t rc_pace_reduce;/* Socket option value Lock(a) */ 294 295 uint8_t r_state; /* Current rack state Lock(a) */ 296 uint8_t rc_tmr_stopped : 7, 297 t_timers_stopped : 1; 298 uint8_t rc_enobuf; /* count of enobufs on connection provides 299 * backoff Lock(a) */ 300 uint8_t r_timer_override : 1, /* hpts override Lock(a) */ 301 r_tlp_running : 1, /* Running from a TLP timeout Lock(a) */ 302 r_is_v6 : 1, /* V6 pcb Lock(a) */ 303 rc_in_persist : 1, 304 rc_last_pto_set : 1, /* XXX not used */ 305 rc_tlp_in_progress : 1, 306 rc_always_pace : 1, /* Socket option value Lock(a) */ 307 rc_timer_up : 1; /* The rack timer is up flag Lock(a) */ 308 uint8_t r_idle_reduce_largest : 1, 309 r_enforce_min_pace : 2, 310 r_min_pace_seg_thresh : 5; 311 uint8_t rack_tlp_threshold_use; 312 uint8_t rc_allow_data_af_clo: 1, 313 delayed_ack : 1, 314 rc_avail : 6; 315 uint8_t r_resv[2]; /* Fill to cache line boundary */ 316 /* Cache line 2 0x40 */ 317 struct rack_control r_ctl; 318 } __aligned(CACHE_LINE_SIZE); 319 320 #endif 321 #endif 322