sys/netinet/tcp_stacks/tcp_rack.h

   1 /*-
   2  * Copyright (c) 2016-9 Netflix, Inc.
   3  *
   4  * Redistribution and use in source and binary forms, with or without
   5  * modification, are permitted provided that the following conditions
   6  * are met:
   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.
  12  *
  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
  23  * SUCH DAMAGE.
  24  *
  25  * $FreeBSD$
  26  */
  27
  28 #ifndef _NETINET_TCP_RACK_H_
  29 #define _NETINET_TCP_RACK_H_
  30
  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
  41
  42 #define RACK_INITIAL_RTO 1000 /* 1 second in milli seconds */
  43
  44 struct rack_sendmap {
  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
  51                                  * sent */
  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? */
  57         uint8_t r_resv[49];
  58 };
  59
  60 RB_HEAD(rack_rb_tree_head, rack_sendmap);
  61 TAILQ_HEAD(rack_head, rack_sendmap);
  62
  63 #define RACK_LIMIT_TYPE_SPLIT   1
  64
  65 /*
  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
  70  * b/w estimation.
  71  */
  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 {
  75         uint32_t rs_flags;
  76         uint32_t rs_rtt_lowest;
  77         uint32_t rs_rtt_highest;
  78         uint32_t rs_rtt_cnt;
  79         uint64_t rs_rtt_tot;
  80 };
  81
  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
  87
  88
  89 struct rack_log {
  90         union {
  91                 struct rack_sendmap *rsm;       /* For alloc/free */
  92                 uint64_t sb_acc;/* For out/ack or t-o */
  93         };
  94         uint32_t th_seq;
  95         uint32_t th_ack;
  96         uint32_t snd_una;
  97         uint32_t snd_nxt;       /* th_win for TYPE_ACK */
  98         uint32_t snd_max;
  99         uint32_t blk_start[4];
 100         uint32_t blk_end[4];
 101         uint8_t type;
 102         uint8_t n_sackblks;
 103         uint16_t len;           /* Timeout T3=1, TLP=2, RACK=3 */
 104 };
 105
 106 /*
 107  * Magic numbers for logging timeout events if the
 108  * logging is enabled.
 109  */
 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
 116
 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;
 141 };
 142
 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 */
 146
 147 #ifdef _KERNEL
 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)
 152 #endif
 153 /*
 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.
 157  *
 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
 166  * equal snd_max.
 167  *
 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.
 173  *
 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.
 179  *
 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.
 183  */
 184
 185 #define TT_RACK_FR_TMR  0x2000
 186
 187 /*
 188  * Locking for the rack control block.
 189  * a) Locked by INP_WLOCK
 190  * b) Locked by the hpts-mutex
 191  *
 192  */
 193 #define RACK_GP_HIST 4  /* How much goodput history do we maintain? */
 194
 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
 202                                          * resend */
 203         struct timeval rc_last_time_decay;      /* SAD time decay happened here */
 204         uint32_t input_pkt;
 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) */
 210
 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) */
 216
 217         uint32_t rc_tlp_new_data;       /* we need to send new-data on a TLP
 218                                          * Lock(a) */
 219         uint32_t rc_prr_out;    /* bytes sent during recovery Lock(a) */
 220
 221         uint32_t rc_prr_recovery_fs;    /* recovery fs point Lock(a) */
 222
 223         uint32_t rc_prr_sndcnt; /* Prr sndcnt Lock(a) */
 224
 225         uint32_t rc_sacked;     /* Tot sacked on scoreboard Lock(a) */
 226         uint32_t rc_last_tlp_seq;       /* Last tlp sequence Lock(a) */
 227
 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) */
 233
 234         uint32_t rc_loss_count; /* During recovery how many segments were lost
 235                                  * Lock(a) */
 236         uint32_t rc_reorder_fade;       /* Socket option value Lock(a) */
 237
 238         /* Forth cache line 0xc0  */
 239         /* Times */
 240
 241         uint32_t rc_rack_tmit_time;     /* Rack transmit time Lock(a) */
 242         uint32_t rc_holes_rxt;  /* Tot retraned from scoreboard Lock(a) */
 243
 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) */
 247
 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
 250                                          * have allocated */
 251         uint32_t rc_rcvtime;    /* When we last received data */
 252         uint32_t rc_num_split_allocs;   /* num split map entries allocated */
 253
 254         uint32_t rc_last_output_to;
 255         uint32_t rc_went_idle_time;
 256
 257         struct rack_sendmap *rc_sacklast;       /* sack remembered place
 258                                                  * Lock(a) */
 259
 260         struct rack_sendmap *rc_rsm_at_retran;  /* Debug variable kept for
 261                                                  * cache line alignment
 262                                                  * Lock(a) */
 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;
 271         uint32_t ack_count;
 272         uint32_t sack_count;
 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;
 293
 294 };
 295
 296 #ifdef _KERNEL
 297
 298 struct tcp_rack {
 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
 307                                  * Lock(a) */
 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) */
 313
 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
 318                                  * backoff Lock(a) */
 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)  */
 322                 rc_in_persist : 1,
 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,
 329                 r_rep_attack : 1,
 330                 r_rep_reverse : 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,
 334                 delayed_ack : 1,
 335                 set_pacing_done_a_iw : 1,
 336                 use_rack_cheat : 1,
 337                 alloc_limit_reported : 1,
 338                 sack_attack_disable : 1,
 339                 do_detection : 1,
 340                 rc_avail : 1;
 341         uint16_t rack_per_of_gp;
 342         /* Cache line 2 0x40 */
 343         struct rack_control r_ctl;
 344 }        __aligned(CACHE_LINE_SIZE);
 345
 346 #endif
 347 #endif