sys/netinet/cc/cc_newreno.c

   1 /*-
   2  * SPDX-License-Identifier: BSD-2-Clause-FreeBSD
   3  *
   4  * Copyright (c) 1982, 1986, 1988, 1990, 1993, 1994, 1995
   5  *      The Regents of the University of California.
   6  * Copyright (c) 2007-2008,2010,2014
   7  *      Swinburne University of Technology, Melbourne, Australia.
   8  * Copyright (c) 2009-2010 Lawrence Stewart <lstewart@freebsd.org>
   9  * Copyright (c) 2010 The FreeBSD Foundation
  10  * All rights reserved.
  11  *
  12  * This software was developed at the Centre for Advanced Internet
  13  * Architectures, Swinburne University of Technology, by Lawrence Stewart, James
  14  * Healy and David Hayes, made possible in part by a grant from the Cisco
  15  * University Research Program Fund at Community Foundation Silicon Valley.
  16  *
  17  * Portions of this software were developed at the Centre for Advanced
  18  * Internet Architectures, Swinburne University of Technology, Melbourne,
  19  * Australia by David Hayes under sponsorship from the FreeBSD Foundation.
  20  *
  21  * Redistribution and use in source and binary forms, with or without
  22  * modification, are permitted provided that the following conditions
  23  * are met:
  24  * 1. Redistributions of source code must retain the above copyright
  25  *    notice, this list of conditions and the following disclaimer.
  26  * 2. Redistributions in binary form must reproduce the above copyright
  27  *    notice, this list of conditions and the following disclaimer in the
  28  *    documentation and/or other materials provided with the distribution.
  29  *
  30  * THIS SOFTWARE IS PROVIDED BY THE AUTHOR AND CONTRIBUTORS ``AS IS'' AND
  31  * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
  32  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
  33  * ARE DISCLAIMED. IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE
  34  * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
  35  * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
  36  * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
  37  * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
  38  * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
  39  * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
  40  * SUCH DAMAGE.
  41  */
  42
  43 /*
  44  * This software was first released in 2007 by James Healy and Lawrence Stewart
  45  * whilst working on the NewTCP research project at Swinburne University of
  46  * Technology's Centre for Advanced Internet Architectures, Melbourne,
  47  * Australia, which was made possible in part by a grant from the Cisco
  48  * University Research Program Fund at Community Foundation Silicon Valley.
  49  * More details are available at:
  50  *   http://caia.swin.edu.au/urp/newtcp/
  51  *
  52  * Dec 2014 garmitage@swin.edu.au
  53  * Borrowed code fragments from cc_cdg.c to add modifiable beta
  54  * via sysctls.
  55  *
  56  */
  57
  58 #include <sys/cdefs.h>
  59 __FBSDID("$FreeBSD$");
  60
  61 #include <sys/param.h>
  62 #include <sys/kernel.h>
  63 #include <sys/malloc.h>
  64 #include <sys/module.h>
  65 #include <sys/socket.h>
  66 #include <sys/socketvar.h>
  67 #include <sys/sysctl.h>
  68 #include <sys/systm.h>
  69
  70 #include <net/vnet.h>
  71
  72 #include <netinet/tcp.h>
  73 #include <netinet/tcp_seq.h>
  74 #include <netinet/tcp_var.h>
  75 #include <netinet/cc/cc.h>
  76 #include <netinet/cc/cc_module.h>
  77 #include <netinet/cc/cc_newreno.h>
  78
  79 static MALLOC_DEFINE(M_NEWRENO, "newreno data",
  80         "newreno beta values");
  81
  82 static void     newreno_cb_destroy(struct cc_var *ccv);
  83 static void     newreno_ack_received(struct cc_var *ccv, uint16_t type);
  84 static void     newreno_after_idle(struct cc_var *ccv);
  85 static void     newreno_cong_signal(struct cc_var *ccv, uint32_t type);
  86 static void     newreno_post_recovery(struct cc_var *ccv);
  87 static int newreno_ctl_output(struct cc_var *ccv, struct sockopt *sopt, void *buf);
  88
  89 VNET_DEFINE_STATIC(uint32_t, newreno_beta) = 50;
  90 VNET_DEFINE_STATIC(uint32_t, newreno_beta_ecn) = 80;
  91 #define V_newreno_beta VNET(newreno_beta)
  92 #define V_newreno_beta_ecn VNET(newreno_beta_ecn)
  93
  94 struct cc_algo newreno_cc_algo = {
  95         .name = "newreno",
  96         .cb_destroy = newreno_cb_destroy,
  97         .ack_received = newreno_ack_received,
  98         .after_idle = newreno_after_idle,
  99         .cong_signal = newreno_cong_signal,
 100         .post_recovery = newreno_post_recovery,
 101         .ctl_output = newreno_ctl_output,
 102 };
 103
 104 struct newreno {
 105         uint32_t beta;
 106         uint32_t beta_ecn;
 107 };
 108
 109 static inline struct newreno *
 110 newreno_malloc(struct cc_var *ccv)
 111 {
 112         struct newreno *nreno;
 113
 114         nreno = malloc(sizeof(struct newreno), M_NEWRENO, M_NOWAIT);
 115         if (nreno != NULL) {
 116                 /* NB: nreno is not zeroed, so initialise all fields. */
 117                 nreno->beta = V_newreno_beta;
 118                 nreno->beta_ecn = V_newreno_beta_ecn;
 119                 ccv->cc_data = nreno;
 120         }
 121
 122         return (nreno);
 123 }
 124
 125 static void
 126 newreno_cb_destroy(struct cc_var *ccv)
 127 {
 128         free(ccv->cc_data, M_NEWRENO);
 129 }
 130
 131 static void
 132 newreno_ack_received(struct cc_var *ccv, uint16_t type)
 133 {
 134         if (type == CC_ACK && !IN_RECOVERY(CCV(ccv, t_flags)) &&
 135             (ccv->flags & CCF_CWND_LIMITED)) {
 136                 u_int cw = CCV(ccv, snd_cwnd);
 137                 u_int incr = CCV(ccv, t_maxseg);
 138
 139                 /*
 140                  * Regular in-order ACK, open the congestion window.
 141                  * Method depends on which congestion control state we're
 142                  * in (slow start or cong avoid) and if ABC (RFC 3465) is
 143                  * enabled.
 144                  *
 145                  * slow start: cwnd <= ssthresh
 146                  * cong avoid: cwnd > ssthresh
 147                  *
 148                  * slow start and ABC (RFC 3465):
 149                  *   Grow cwnd exponentially by the amount of data
 150                  *   ACKed capping the max increment per ACK to
 151                  *   (abc_l_var * maxseg) bytes.
 152                  *
 153                  * slow start without ABC (RFC 5681):
 154                  *   Grow cwnd exponentially by maxseg per ACK.
 155                  *
 156                  * cong avoid and ABC (RFC 3465):
 157                  *   Grow cwnd linearly by maxseg per RTT for each
 158                  *   cwnd worth of ACKed data.
 159                  *
 160                  * cong avoid without ABC (RFC 5681):
 161                  *   Grow cwnd linearly by approximately maxseg per RTT using
 162                  *   maxseg^2 / cwnd per ACK as the increment.
 163                  *   If cwnd > maxseg^2, fix the cwnd increment at 1 byte to
 164                  *   avoid capping cwnd.
 165                  */
 166                 if (cw > CCV(ccv, snd_ssthresh)) {
 167                         if (V_tcp_do_rfc3465) {
 168                                 if (ccv->flags & CCF_ABC_SENTAWND)
 169                                         ccv->flags &= ~CCF_ABC_SENTAWND;
 170                                 else
 171                                         incr = 0;
 172                         } else
 173                                 incr = max((incr * incr / cw), 1);
 174                 } else if (V_tcp_do_rfc3465) {
 175                         /*
 176                          * In slow-start with ABC enabled and no RTO in sight?
 177                          * (Must not use abc_l_var > 1 if slow starting after
 178                          * an RTO. On RTO, snd_nxt = snd_una, so the
 179                          * snd_nxt == snd_max check is sufficient to
 180                          * handle this).
 181                          *
 182                          * XXXLAS: Find a way to signal SS after RTO that
 183                          * doesn't rely on tcpcb vars.
 184                          */
 185                         if (CCV(ccv, snd_nxt) == CCV(ccv, snd_max))
 186                                 incr = min(ccv->bytes_this_ack,
 187                                     ccv->nsegs * V_tcp_abc_l_var *
 188                                     CCV(ccv, t_maxseg));
 189                         else
 190                                 incr = min(ccv->bytes_this_ack, CCV(ccv, t_maxseg));
 191                 }
 192                 /* ABC is on by default, so incr equals 0 frequently. */
 193                 if (incr > 0)
 194                         CCV(ccv, snd_cwnd) = min(cw + incr,
 195                             TCP_MAXWIN << CCV(ccv, snd_scale));
 196         }
 197 }
 198
 199 static void
 200 newreno_after_idle(struct cc_var *ccv)
 201 {
 202         uint32_t rw;
 203
 204         /*
 205          * If we've been idle for more than one retransmit timeout the old
 206          * congestion window is no longer current and we have to reduce it to
 207          * the restart window before we can transmit again.
 208          *
 209          * The restart window is the initial window or the last CWND, whichever
 210          * is smaller.
 211          *
 212          * This is done to prevent us from flooding the path with a full CWND at
 213          * wirespeed, overloading router and switch buffers along the way.
 214          *
 215          * See RFC5681 Section 4.1. "Restarting Idle Connections".
 216          *
 217          * In addition, per RFC2861 Section 2, the ssthresh is set to the
 218          * maximum of the former ssthresh or 3/4 of the old cwnd, to
 219          * not exit slow-start prematurely.
 220          */
 221         rw = tcp_compute_initwnd(tcp_maxseg(ccv->ccvc.tcp));
 222
 223         CCV(ccv, snd_ssthresh) = max(CCV(ccv, snd_ssthresh),
 224             CCV(ccv, snd_cwnd)-(CCV(ccv, snd_cwnd)>>2));
 225
 226         CCV(ccv, snd_cwnd) = min(rw, CCV(ccv, snd_cwnd));
 227 }
 228
 229 /*
 230  * Perform any necessary tasks before we enter congestion recovery.
 231  */
 232 static void
 233 newreno_cong_signal(struct cc_var *ccv, uint32_t type)
 234 {
 235         struct newreno *nreno;
 236         uint32_t beta, beta_ecn, cwin, factor;
 237         u_int mss;
 238
 239         cwin = CCV(ccv, snd_cwnd);
 240         mss = CCV(ccv, t_maxseg);
 241         nreno = ccv->cc_data;
 242         beta = (nreno == NULL) ? V_newreno_beta : nreno->beta;
 243         beta_ecn = (nreno == NULL) ? V_newreno_beta_ecn : nreno->beta_ecn;
 244         if (V_cc_do_abe && type == CC_ECN)
 245                 factor = beta_ecn;
 246         else
 247                 factor = beta;
 248
 249         /* Catch algos which mistakenly leak private signal types. */
 250         KASSERT((type & CC_SIGPRIVMASK) == 0,
 251             ("%s: congestion signal type 0x%08x is private\n", __func__, type));
 252
 253         cwin = max(((uint64_t)cwin * (uint64_t)factor) / (100ULL * (uint64_t)mss),
 254             2) * mss;
 255
 256         switch (type) {
 257         case CC_NDUPACK:
 258                 if (!IN_FASTRECOVERY(CCV(ccv, t_flags))) {
 259                         if (IN_CONGRECOVERY(CCV(ccv, t_flags) &&
 260                             V_cc_do_abe && V_cc_abe_frlossreduce)) {
 261                                 CCV(ccv, snd_ssthresh) =
 262                                     ((uint64_t)CCV(ccv, snd_ssthresh) *
 263                                     (uint64_t)beta) /
 264                                     (100ULL * (uint64_t)beta_ecn);
 265                         }
 266                         if (!IN_CONGRECOVERY(CCV(ccv, t_flags)))
 267                                 CCV(ccv, snd_ssthresh) = cwin;
 268                         ENTER_RECOVERY(CCV(ccv, t_flags));
 269                 }
 270                 break;
 271         case CC_ECN:
 272                 if (!IN_CONGRECOVERY(CCV(ccv, t_flags))) {
 273                         CCV(ccv, snd_ssthresh) = cwin;
 274                         CCV(ccv, snd_cwnd) = cwin;
 275                         ENTER_CONGRECOVERY(CCV(ccv, t_flags));
 276                 }
 277                 break;
 278         }
 279 }
 280
 281 /*
 282  * Perform any necessary tasks before we exit congestion recovery.
 283  */
 284 static void
 285 newreno_post_recovery(struct cc_var *ccv)
 286 {
 287         int pipe;
 288
 289         if (IN_FASTRECOVERY(CCV(ccv, t_flags))) {
 290                 /*
 291                  * Fast recovery will conclude after returning from this
 292                  * function. Window inflation should have left us with
 293                  * approximately snd_ssthresh outstanding data. But in case we
 294                  * would be inclined to send a burst, better to do it via the
 295                  * slow start mechanism.
 296                  *
 297                  * XXXLAS: Find a way to do this without needing curack
 298                  */
 299                 if (V_tcp_do_rfc6675_pipe)
 300                         pipe = tcp_compute_pipe(ccv->ccvc.tcp);
 301                 else
 302                         pipe = CCV(ccv, snd_max) - ccv->curack;
 303
 304                 if (pipe < CCV(ccv, snd_ssthresh))
 305                         /*
 306                          * Ensure that cwnd does not collapse to 1 MSS under
 307                          * adverse conditons. Implements RFC6582
 308                          */
 309                         CCV(ccv, snd_cwnd) = max(pipe, CCV(ccv, t_maxseg)) +
 310                             CCV(ccv, t_maxseg);
 311                 else
 312                         CCV(ccv, snd_cwnd) = CCV(ccv, snd_ssthresh);
 313         }
 314 }
 315
 316 static int
 317 newreno_ctl_output(struct cc_var *ccv, struct sockopt *sopt, void *buf)
 318 {
 319         struct newreno *nreno;
 320         struct cc_newreno_opts *opt;
 321
 322         if (sopt->sopt_valsize != sizeof(struct cc_newreno_opts))
 323                 return (EMSGSIZE);
 324
 325         nreno = ccv->cc_data;
 326         opt = buf;
 327
 328         switch (sopt->sopt_dir) {
 329         case SOPT_SET:
 330                 /* We cannot set without cc_data memory. */
 331                 if (nreno == NULL) {
 332                         nreno = newreno_malloc(ccv);
 333                         if (nreno == NULL)
 334                                 return (ENOMEM);
 335                 }
 336                 switch (opt->name) {
 337                 case CC_NEWRENO_BETA:
 338                         nreno->beta = opt->val;
 339                         break;
 340                 case CC_NEWRENO_BETA_ECN:
 341                         if (!V_cc_do_abe)
 342                                 return (EACCES);
 343                         nreno->beta_ecn = opt->val;
 344                         break;
 345                 default:
 346                         return (ENOPROTOOPT);
 347                 }
 348                 break;
 349         case SOPT_GET:
 350                 switch (opt->name) {
 351                 case CC_NEWRENO_BETA:
 352                         opt->val = (nreno == NULL) ?
 353                             V_newreno_beta : nreno->beta;
 354                         break;
 355                 case CC_NEWRENO_BETA_ECN:
 356                         opt->val = (nreno == NULL) ?
 357                             V_newreno_beta_ecn : nreno->beta_ecn;
 358                         break;
 359                 default:
 360                         return (ENOPROTOOPT);
 361                 }
 362                 break;
 363         default:
 364                 return (EINVAL);
 365         }
 366
 367         return (0);
 368 }
 369
 370 static int
 371 newreno_beta_handler(SYSCTL_HANDLER_ARGS)
 372 {
 373         int error;
 374         uint32_t new;
 375
 376         new = *(uint32_t *)arg1;
 377         error = sysctl_handle_int(oidp, &new, 0, req);
 378         if (error == 0 && req->newptr != NULL ) {
 379                 if (arg1 == &VNET_NAME(newreno_beta_ecn) && !V_cc_do_abe)
 380                         error = EACCES;
 381                 else if (new == 0 || new > 100)
 382                         error = EINVAL;
 383                 else
 384                         *(uint32_t *)arg1 = new;
 385         }
 386
 387         return (error);
 388 }
 389
 390 SYSCTL_DECL(_net_inet_tcp_cc_newreno);
 391 SYSCTL_NODE(_net_inet_tcp_cc, OID_AUTO, newreno,
 392     CTLFLAG_RW | CTLFLAG_MPSAFE, NULL,
 393     "New Reno related settings");
 394
 395 SYSCTL_PROC(_net_inet_tcp_cc_newreno, OID_AUTO, beta,
 396     CTLFLAG_VNET | CTLTYPE_UINT | CTLFLAG_RW | CTLFLAG_NEEDGIANT,
 397     &VNET_NAME(newreno_beta), 3, &newreno_beta_handler, "IU",
 398     "New Reno beta, specified as number between 1 and 100");
 399
 400 SYSCTL_PROC(_net_inet_tcp_cc_newreno, OID_AUTO, beta_ecn,
 401     CTLFLAG_VNET | CTLTYPE_UINT | CTLFLAG_RW | CTLFLAG_NEEDGIANT,
 402     &VNET_NAME(newreno_beta_ecn), 3, &newreno_beta_handler, "IU",
 403     "New Reno beta ecn, specified as number between 1 and 100");
 404
 405 DECLARE_CC_MODULE(newreno, &newreno_cc_algo);
 406 MODULE_VERSION(newreno, 1);