net/ipv4/tcp_nv.c

   1 /*
   2  * TCP NV: TCP with Congestion Avoidance
   3  *
   4  * TCP-NV is a successor of TCP-Vegas that has been developed to
   5  * deal with the issues that occur in modern networks.
   6  * Like TCP-Vegas, TCP-NV supports true congestion avoidance,
   7  * the ability to detect congestion before packet losses occur.
   8  * When congestion (queue buildup) starts to occur, TCP-NV
   9  * predicts what the cwnd size should be for the current
  10  * throughput and it reduces the cwnd proportionally to
  11  * the difference between the current cwnd and the predicted cwnd.
  12  *
  13  * NV is only recommeneded for traffic within a data center, and when
  14  * all the flows are NV (at least those within the data center). This
  15  * is due to the inherent unfairness between flows using losses to
  16  * detect congestion (congestion control) and those that use queue
  17  * buildup to detect congestion (congestion avoidance).
  18  *
  19  * Note: High NIC coalescence values may lower the performance of NV
  20  * due to the increased noise in RTT values. In particular, we have
  21  * seen issues with rx-frames values greater than 8.
  22  *
  23  * TODO:
  24  * 1) Add mechanism to deal with reverse congestion.
  25  */
  26
  27 #include <linux/mm.h>
  28 #include <linux/module.h>
  29 #include <linux/math64.h>
  30 #include <net/tcp.h>
  31 #include <linux/inet_diag.h>
  32
  33 /* TCP NV parameters
  34  *
  35  * nv_pad               Max number of queued packets allowed in network
  36  * nv_pad_buffer        Do not grow cwnd if this closed to nv_pad
  37  * nv_reset_period      How often (in) seconds)to reset min_rtt
  38  * nv_min_cwnd          Don't decrease cwnd below this if there are no losses
  39  * nv_cong_dec_mult     Decrease cwnd by X% (30%) of congestion when detected
  40  * nv_ssthresh_factor   On congestion set ssthresh to this * <desired cwnd> / 8
  41  * nv_rtt_factor        RTT averaging factor
  42  * nv_loss_dec_factor   Decrease cwnd to this (80%) when losses occur
  43  * nv_dec_eval_min_calls        Wait this many RTT measurements before dec cwnd
  44  * nv_inc_eval_min_calls        Wait this many RTT measurements before inc cwnd
  45  * nv_ssthresh_eval_min_calls   Wait this many RTT measurements before stopping
  46  *                              slow-start due to congestion
  47  * nv_stop_rtt_cnt      Only grow cwnd for this many RTTs after non-congestion
  48  * nv_rtt_min_cnt       Wait these many RTTs before making congesion decision
  49  * nv_cwnd_growth_rate_neg
  50  * nv_cwnd_growth_rate_pos
  51  *      How quickly to double growth rate (not rate) of cwnd when not
  52  *      congested. One value (nv_cwnd_growth_rate_neg) for when
  53  *      rate < 1 pkt/RTT (after losses). The other (nv_cwnd_growth_rate_pos)
  54  *      otherwise.
  55  */
  56
  57 static int nv_pad __read_mostly = 10;
  58 static int nv_pad_buffer __read_mostly = 2;
  59 static int nv_reset_period __read_mostly = 5; /* in seconds */
  60 static int nv_min_cwnd __read_mostly = 2;
  61 static int nv_cong_dec_mult __read_mostly = 30 * 128 / 100; /* = 30% */
  62 static int nv_ssthresh_factor __read_mostly = 8; /* = 1 */
  63 static int nv_rtt_factor __read_mostly = 128; /* = 1/2*old + 1/2*new */
  64 static int nv_loss_dec_factor __read_mostly = 819; /* => 80% */
  65 static int nv_cwnd_growth_rate_neg __read_mostly = 8;
  66 static int nv_cwnd_growth_rate_pos __read_mostly; /* 0 => fixed like Reno */
  67 static int nv_dec_eval_min_calls __read_mostly = 60;
  68 static int nv_inc_eval_min_calls __read_mostly = 20;
  69 static int nv_ssthresh_eval_min_calls __read_mostly = 30;
  70 static int nv_stop_rtt_cnt __read_mostly = 10;
  71 static int nv_rtt_min_cnt __read_mostly = 2;
  72
  73 module_param(nv_pad, int, 0644);
  74 MODULE_PARM_DESC(nv_pad, "max queued packets allowed in network");
  75 module_param(nv_reset_period, int, 0644);
  76 MODULE_PARM_DESC(nv_reset_period, "nv_min_rtt reset period (secs)");
  77 module_param(nv_min_cwnd, int, 0644);
  78 MODULE_PARM_DESC(nv_min_cwnd, "NV will not decrease cwnd below this value"
  79                  " without losses");
  80
  81 /* TCP NV Parameters */
  82 struct tcpnv {
  83         unsigned long nv_min_rtt_reset_jiffies;  /* when to switch to
  84                                                   * nv_min_rtt_new */
  85         s8  cwnd_growth_factor; /* Current cwnd growth factor,
  86                                  * < 0 => less than 1 packet/RTT */
  87         u8  available8;
  88         u16 available16;
  89         u8  nv_allow_cwnd_growth:1, /* whether cwnd can grow */
  90                 nv_reset:1,         /* whether to reset values */
  91                 nv_catchup:1;       /* whether we are growing because
  92                                      * of temporary cwnd decrease */
  93         u8  nv_eval_call_cnt;   /* call count since last eval */
  94         u8  nv_min_cwnd;        /* nv won't make a ca decision if cwnd is
  95                                  * smaller than this. It may grow to handle
  96                                  * TSO, LRO and interrupt coalescence because
  97                                  * with these a small cwnd cannot saturate
  98                                  * the link. Note that this is different from
  99                                  * the file local nv_min_cwnd */
 100         u8  nv_rtt_cnt;         /* RTTs without making ca decision */;
 101         u32 nv_last_rtt;        /* last rtt */
 102         u32 nv_min_rtt;         /* active min rtt. Used to determine slope */
 103         u32 nv_min_rtt_new;     /* min rtt for future use */
 104         u32 nv_base_rtt;        /* If non-zero it represents the threshold for
 105                                  * congestion */
 106         u32 nv_lower_bound_rtt; /* Used in conjunction with nv_base_rtt. It is
 107                                  * set to 80% of nv_base_rtt. It helps reduce
 108                                  * unfairness between flows */
 109         u32 nv_rtt_max_rate;    /* max rate seen during current RTT */
 110         u32 nv_rtt_start_seq;   /* current RTT ends when packet arrives
 111                                  * acking beyond nv_rtt_start_seq */
 112         u32 nv_last_snd_una;    /* Previous value of tp->snd_una. It is
 113                                  * used to determine bytes acked since last
 114                                  * call to bictcp_acked */
 115         u32 nv_no_cong_cnt;     /* Consecutive no congestion decisions */
 116 };
 117
 118 #define NV_INIT_RTT       U32_MAX
 119 #define NV_MIN_CWND       4
 120 #define NV_MIN_CWND_GROW  2
 121 #define NV_TSO_CWND_BOUND 80
 122
 123 static inline void tcpnv_reset(struct tcpnv *ca, struct sock *sk)
 124 {
 125         struct tcp_sock *tp = tcp_sk(sk);
 126
 127         ca->nv_reset = 0;
 128         ca->nv_no_cong_cnt = 0;
 129         ca->nv_rtt_cnt = 0;
 130         ca->nv_last_rtt = 0;
 131         ca->nv_rtt_max_rate = 0;
 132         ca->nv_rtt_start_seq = tp->snd_una;
 133         ca->nv_eval_call_cnt = 0;
 134         ca->nv_last_snd_una = tp->snd_una;
 135 }
 136
 137 static void tcpnv_init(struct sock *sk)
 138 {
 139         struct tcpnv *ca = inet_csk_ca(sk);
 140         int base_rtt;
 141
 142         tcpnv_reset(ca, sk);
 143
 144         /* See if base_rtt is available from socket_ops bpf program.
 145          * It is meant to be used in environments, such as communication
 146          * within a datacenter, where we have reasonable estimates of
 147          * RTTs
 148          */
 149         base_rtt = tcp_call_bpf(sk, BPF_SOCK_OPS_BASE_RTT, 0, NULL);
 150         if (base_rtt > 0) {
 151                 ca->nv_base_rtt = base_rtt;
 152                 ca->nv_lower_bound_rtt = (base_rtt * 205) >> 8; /* 80% */
 153         } else {
 154                 ca->nv_base_rtt = 0;
 155                 ca->nv_lower_bound_rtt = 0;
 156         }
 157
 158         ca->nv_allow_cwnd_growth = 1;
 159         ca->nv_min_rtt_reset_jiffies = jiffies + 2 * HZ;
 160         ca->nv_min_rtt = NV_INIT_RTT;
 161         ca->nv_min_rtt_new = NV_INIT_RTT;
 162         ca->nv_min_cwnd = NV_MIN_CWND;
 163         ca->nv_catchup = 0;
 164         ca->cwnd_growth_factor = 0;
 165 }
 166
 167 /* If provided, apply upper (base_rtt) and lower (lower_bound_rtt)
 168  * bounds to RTT.
 169  */
 170 inline u32 nv_get_bounded_rtt(struct tcpnv *ca, u32 val)
 171 {
 172         if (ca->nv_lower_bound_rtt > 0 && val < ca->nv_lower_bound_rtt)
 173                 return ca->nv_lower_bound_rtt;
 174         else if (ca->nv_base_rtt > 0 && val > ca->nv_base_rtt)
 175                 return ca->nv_base_rtt;
 176         else
 177                 return val;
 178 }
 179
 180 static void tcpnv_cong_avoid(struct sock *sk, u32 ack, u32 acked)
 181 {
 182         struct tcp_sock *tp = tcp_sk(sk);
 183         struct tcpnv *ca = inet_csk_ca(sk);
 184         u32 cnt;
 185
 186         if (!tcp_is_cwnd_limited(sk))
 187                 return;
 188
 189         /* Only grow cwnd if NV has not detected congestion */
 190         if (!ca->nv_allow_cwnd_growth)
 191                 return;
 192
 193         if (tcp_in_slow_start(tp)) {
 194                 acked = tcp_slow_start(tp, acked);
 195                 if (!acked)
 196                         return;
 197         }
 198
 199         if (ca->cwnd_growth_factor < 0) {
 200                 cnt = tp->snd_cwnd << -ca->cwnd_growth_factor;
 201                 tcp_cong_avoid_ai(tp, cnt, acked);
 202         } else {
 203                 cnt = max(4U, tp->snd_cwnd >> ca->cwnd_growth_factor);
 204                 tcp_cong_avoid_ai(tp, cnt, acked);
 205         }
 206 }
 207
 208 static u32 tcpnv_recalc_ssthresh(struct sock *sk)
 209 {
 210         const struct tcp_sock *tp = tcp_sk(sk);
 211
 212         return max((tp->snd_cwnd * nv_loss_dec_factor) >> 10, 2U);
 213 }
 214
 215 static void tcpnv_state(struct sock *sk, u8 new_state)
 216 {
 217         struct tcpnv *ca = inet_csk_ca(sk);
 218
 219         if (new_state == TCP_CA_Open && ca->nv_reset) {
 220                 tcpnv_reset(ca, sk);
 221         } else if (new_state == TCP_CA_Loss || new_state == TCP_CA_CWR ||
 222                 new_state == TCP_CA_Recovery) {
 223                 ca->nv_reset = 1;
 224                 ca->nv_allow_cwnd_growth = 0;
 225                 if (new_state == TCP_CA_Loss) {
 226                         /* Reset cwnd growth factor to Reno value */
 227                         if (ca->cwnd_growth_factor > 0)
 228                                 ca->cwnd_growth_factor = 0;
 229                         /* Decrease growth rate if allowed */
 230                         if (nv_cwnd_growth_rate_neg > 0 &&
 231                             ca->cwnd_growth_factor > -8)
 232                                 ca->cwnd_growth_factor--;
 233                 }
 234         }
 235 }
 236
 237 /* Do congestion avoidance calculations for TCP-NV
 238  */
 239 static void tcpnv_acked(struct sock *sk, const struct ack_sample *sample)
 240 {
 241         const struct inet_connection_sock *icsk = inet_csk(sk);
 242         struct tcp_sock *tp = tcp_sk(sk);
 243         struct tcpnv *ca = inet_csk_ca(sk);
 244         unsigned long now = jiffies;
 245         u64 rate64;
 246         u32 rate, max_win, cwnd_by_slope;
 247         u32 avg_rtt;
 248         u32 bytes_acked = 0;
 249
 250         /* Some calls are for duplicates without timetamps */
 251         if (sample->rtt_us < 0)
 252                 return;
 253
 254         /* If not in TCP_CA_Open or TCP_CA_Disorder states, skip. */
 255         if (icsk->icsk_ca_state != TCP_CA_Open &&
 256             icsk->icsk_ca_state != TCP_CA_Disorder)
 257                 return;
 258
 259         /* Stop cwnd growth if we were in catch up mode */
 260         if (ca->nv_catchup && tp->snd_cwnd >= nv_min_cwnd) {
 261                 ca->nv_catchup = 0;
 262                 ca->nv_allow_cwnd_growth = 0;
 263         }
 264
 265         bytes_acked = tp->snd_una - ca->nv_last_snd_una;
 266         ca->nv_last_snd_una = tp->snd_una;
 267
 268         if (sample->in_flight == 0)
 269                 return;
 270
 271         /* Calculate moving average of RTT */
 272         if (nv_rtt_factor > 0) {
 273                 if (ca->nv_last_rtt > 0) {
 274                         avg_rtt = (((u64)sample->rtt_us) * nv_rtt_factor +
 275                                    ((u64)ca->nv_last_rtt)
 276                                    * (256 - nv_rtt_factor)) >> 8;
 277                 } else {
 278                         avg_rtt = sample->rtt_us;
 279                         ca->nv_min_rtt = avg_rtt << 1;
 280                 }
 281                 ca->nv_last_rtt = avg_rtt;
 282         } else {
 283                 avg_rtt = sample->rtt_us;
 284         }
 285
 286         /* rate in 100's bits per second */
 287         rate64 = ((u64)sample->in_flight) * 80000;
 288         do_div(rate64, avg_rtt ?: 1);
 289         rate = (u32)rate64;
 290
 291         /* Remember the maximum rate seen during this RTT
 292          * Note: It may be more than one RTT. This function should be
 293          *       called at least nv_dec_eval_min_calls times.
 294          */
 295         if (ca->nv_rtt_max_rate < rate)
 296                 ca->nv_rtt_max_rate = rate;
 297
 298         /* We have valid information, increment counter */
 299         if (ca->nv_eval_call_cnt < 255)
 300                 ca->nv_eval_call_cnt++;
 301
 302         /* Apply bounds to rtt. Only used to update min_rtt */
 303         avg_rtt = nv_get_bounded_rtt(ca, avg_rtt);
 304
 305         /* update min rtt if necessary */
 306         if (avg_rtt < ca->nv_min_rtt)
 307                 ca->nv_min_rtt = avg_rtt;
 308
 309         /* update future min_rtt if necessary */
 310         if (avg_rtt < ca->nv_min_rtt_new)
 311                 ca->nv_min_rtt_new = avg_rtt;
 312
 313         /* nv_min_rtt is updated with the minimum (possibley averaged) rtt
 314          * seen in the last sysctl_tcp_nv_reset_period seconds (i.e. a
 315          * warm reset). This new nv_min_rtt will be continued to be updated
 316          * and be used for another sysctl_tcp_nv_reset_period seconds,
 317          * when it will be updated again.
 318          * In practice we introduce some randomness, so the actual period used
 319          * is chosen randomly from the range:
 320          *   [sysctl_tcp_nv_reset_period*3/4, sysctl_tcp_nv_reset_period*5/4)
 321          */
 322         if (time_after_eq(now, ca->nv_min_rtt_reset_jiffies)) {
 323                 unsigned char rand;
 324
 325                 ca->nv_min_rtt = ca->nv_min_rtt_new;
 326                 ca->nv_min_rtt_new = NV_INIT_RTT;
 327                 get_random_bytes(&rand, 1);
 328                 ca->nv_min_rtt_reset_jiffies =
 329                         now + ((nv_reset_period * (384 + rand) * HZ) >> 9);
 330                 /* Every so often we decrease ca->nv_min_cwnd in case previous
 331                  *  value is no longer accurate.
 332                  */
 333                 ca->nv_min_cwnd = max(ca->nv_min_cwnd / 2, NV_MIN_CWND);
 334         }
 335
 336         /* Once per RTT check if we need to do congestion avoidance */
 337         if (before(ca->nv_rtt_start_seq, tp->snd_una)) {
 338                 ca->nv_rtt_start_seq = tp->snd_nxt;
 339                 if (ca->nv_rtt_cnt < 0xff)
 340                         /* Increase counter for RTTs without CA decision */
 341                         ca->nv_rtt_cnt++;
 342
 343                 /* If this function is only called once within an RTT
 344                  * the cwnd is probably too small (in some cases due to
 345                  * tso, lro or interrupt coalescence), so we increase
 346                  * ca->nv_min_cwnd.
 347                  */
 348                 if (ca->nv_eval_call_cnt == 1 &&
 349                     bytes_acked >= (ca->nv_min_cwnd - 1) * tp->mss_cache &&
 350                     ca->nv_min_cwnd < (NV_TSO_CWND_BOUND + 1)) {
 351                         ca->nv_min_cwnd = min(ca->nv_min_cwnd
 352                                               + NV_MIN_CWND_GROW,
 353                                               NV_TSO_CWND_BOUND + 1);
 354                         ca->nv_rtt_start_seq = tp->snd_nxt +
 355                                 ca->nv_min_cwnd * tp->mss_cache;
 356                         ca->nv_eval_call_cnt = 0;
 357                         ca->nv_allow_cwnd_growth = 1;
 358                         return;
 359                 }
 360
 361                 /* Find the ideal cwnd for current rate from slope
 362                  * slope = 80000.0 * mss / nv_min_rtt
 363                  * cwnd_by_slope = nv_rtt_max_rate / slope
 364                  */
 365                 cwnd_by_slope = (u32)
 366                         div64_u64(((u64)ca->nv_rtt_max_rate) * ca->nv_min_rtt,
 367                                   80000ULL * tp->mss_cache);
 368                 max_win = cwnd_by_slope + nv_pad;
 369
 370                 /* If cwnd > max_win, decrease cwnd
 371                  * if cwnd < max_win, grow cwnd
 372                  * else leave the same
 373                  */
 374                 if (tp->snd_cwnd > max_win) {
 375                         /* there is congestion, check that it is ok
 376                          * to make a CA decision
 377                          * 1. We should have at least nv_dec_eval_min_calls
 378                          *    data points before making a CA  decision
 379                          * 2. We only make a congesion decision after
 380                          *    nv_rtt_min_cnt RTTs
 381                          */
 382                         if (ca->nv_rtt_cnt < nv_rtt_min_cnt) {
 383                                 return;
 384                         } else if (tp->snd_ssthresh == TCP_INFINITE_SSTHRESH) {
 385                                 if (ca->nv_eval_call_cnt <
 386                                     nv_ssthresh_eval_min_calls)
 387                                         return;
 388                                 /* otherwise we will decrease cwnd */
 389                         } else if (ca->nv_eval_call_cnt <
 390                                    nv_dec_eval_min_calls) {
 391                                 if (ca->nv_allow_cwnd_growth &&
 392                                     ca->nv_rtt_cnt > nv_stop_rtt_cnt)
 393                                         ca->nv_allow_cwnd_growth = 0;
 394                                 return;
 395                         }
 396
 397                         /* We have enough data to determine we are congested */
 398                         ca->nv_allow_cwnd_growth = 0;
 399                         tp->snd_ssthresh =
 400                                 (nv_ssthresh_factor * max_win) >> 3;
 401                         if (tp->snd_cwnd - max_win > 2) {
 402                                 /* gap > 2, we do exponential cwnd decrease */
 403                                 int dec;
 404
 405                                 dec = max(2U, ((tp->snd_cwnd - max_win) *
 406                                                nv_cong_dec_mult) >> 7);
 407                                 tp->snd_cwnd -= dec;
 408                         } else if (nv_cong_dec_mult > 0) {
 409                                 tp->snd_cwnd = max_win;
 410                         }
 411                         if (ca->cwnd_growth_factor > 0)
 412                                 ca->cwnd_growth_factor = 0;
 413                         ca->nv_no_cong_cnt = 0;
 414                 } else if (tp->snd_cwnd <= max_win - nv_pad_buffer) {
 415                         /* There is no congestion, grow cwnd if allowed*/
 416                         if (ca->nv_eval_call_cnt < nv_inc_eval_min_calls)
 417                                 return;
 418
 419                         ca->nv_allow_cwnd_growth = 1;
 420                         ca->nv_no_cong_cnt++;
 421                         if (ca->cwnd_growth_factor < 0 &&
 422                             nv_cwnd_growth_rate_neg > 0 &&
 423                             ca->nv_no_cong_cnt > nv_cwnd_growth_rate_neg) {
 424                                 ca->cwnd_growth_factor++;
 425                                 ca->nv_no_cong_cnt = 0;
 426                         } else if (ca->cwnd_growth_factor >= 0 &&
 427                                    nv_cwnd_growth_rate_pos > 0 &&
 428                                    ca->nv_no_cong_cnt >
 429                                    nv_cwnd_growth_rate_pos) {
 430                                 ca->cwnd_growth_factor++;
 431                                 ca->nv_no_cong_cnt = 0;
 432                         }
 433                 } else {
 434                         /* cwnd is in-between, so do nothing */
 435                         return;
 436                 }
 437
 438                 /* update state */
 439                 ca->nv_eval_call_cnt = 0;
 440                 ca->nv_rtt_cnt = 0;
 441                 ca->nv_rtt_max_rate = 0;
 442
 443                 /* Don't want to make cwnd < nv_min_cwnd
 444                  * (it wasn't before, if it is now is because nv
 445                  *  decreased it).
 446                  */
 447                 if (tp->snd_cwnd < nv_min_cwnd)
 448                         tp->snd_cwnd = nv_min_cwnd;
 449         }
 450 }
 451
 452 /* Extract info for Tcp socket info provided via netlink */
 453 static size_t tcpnv_get_info(struct sock *sk, u32 ext, int *attr,
 454                              union tcp_cc_info *info)
 455 {
 456         const struct tcpnv *ca = inet_csk_ca(sk);
 457
 458         if (ext & (1 << (INET_DIAG_VEGASINFO - 1))) {
 459                 info->vegas.tcpv_enabled = 1;
 460                 info->vegas.tcpv_rttcnt = ca->nv_rtt_cnt;
 461                 info->vegas.tcpv_rtt = ca->nv_last_rtt;
 462                 info->vegas.tcpv_minrtt = ca->nv_min_rtt;
 463
 464                 *attr = INET_DIAG_VEGASINFO;
 465                 return sizeof(struct tcpvegas_info);
 466         }
 467         return 0;
 468 }
 469
 470 static struct tcp_congestion_ops tcpnv __read_mostly = {
 471         .init           = tcpnv_init,
 472         .ssthresh       = tcpnv_recalc_ssthresh,
 473         .cong_avoid     = tcpnv_cong_avoid,
 474         .set_state      = tcpnv_state,
 475         .undo_cwnd      = tcp_reno_undo_cwnd,
 476         .pkts_acked     = tcpnv_acked,
 477         .get_info       = tcpnv_get_info,
 478
 479         .owner          = THIS_MODULE,
 480         .name           = "nv",
 481 };
 482
 483 static int __init tcpnv_register(void)
 484 {
 485         BUILD_BUG_ON(sizeof(struct tcpnv) > ICSK_CA_PRIV_SIZE);
 486
 487         return tcp_register_congestion_control(&tcpnv);
 488 }
 489
 490 static void __exit tcpnv_unregister(void)
 491 {
 492         tcp_unregister_congestion_control(&tcpnv);
 493 }
 494
 495 module_init(tcpnv_register);
 496 module_exit(tcpnv_unregister);
 497
 498 MODULE_AUTHOR("Lawrence Brakmo");
 499 MODULE_LICENSE("GPL");
 500 MODULE_DESCRIPTION("TCP NV");
 501 MODULE_VERSION("1.0");