sys/netinet/cc/cc_vegas.c

   1 /*-
   2  * SPDX-License-Identifier: BSD-2-Clause-FreeBSD
   3  *
   4  * Copyright (c) 2009-2010
   5  *      Swinburne University of Technology, Melbourne, Australia
   6  * Copyright (c) 2010 Lawrence Stewart <lstewart@freebsd.org>
   7  * Copyright (c) 2010-2011 The FreeBSD Foundation
   8  * All rights reserved.
   9  *
  10  * This software was developed at the Centre for Advanced Internet
  11  * Architectures, Swinburne University of Technology, by David Hayes and
  12  * Lawrence Stewart, made possible in part by a grant from the Cisco University
  13  * Research Program Fund at Community Foundation Silicon Valley.
  14  *
  15  * Portions of this software were developed at the Centre for Advanced Internet
  16  * Architectures, Swinburne University of Technology, Melbourne, Australia by
  17  * David Hayes under sponsorship from the FreeBSD Foundation.
  18  *
  19  * Redistribution and use in source and binary forms, with or without
  20  * modification, are permitted provided that the following conditions
  21  * are met:
  22  * 1. Redistributions of source code must retain the above copyright
  23  *    notice, this list of conditions and the following disclaimer.
  24  * 2. Redistributions in binary form must reproduce the above copyright
  25  *    notice, this list of conditions and the following disclaimer in the
  26  *    documentation and/or other materials provided with the distribution.
  27  *
  28  * THIS SOFTWARE IS PROVIDED BY THE AUTHOR AND CONTRIBUTORS ``AS IS'' AND
  29  * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
  30  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
  31  * ARE DISCLAIMED. IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE
  32  * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
  33  * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
  34  * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
  35  * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
  36  * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
  37  * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
  38  * SUCH DAMAGE.
  39  */
  40
  41 /*
  42  * An implementation of the Vegas congestion control algorithm for FreeBSD,
  43  * based on L. S. Brakmo and L. L. Peterson, "TCP Vegas: end to end congestion
  44  * avoidance on a global internet", IEEE J. Sel. Areas Commun., vol. 13, no. 8,
  45  * pp. 1465-1480, Oct. 1995. The original Vegas duplicate ack policy has not
  46  * been implemented, since clock ticks are not as coarse as they were (i.e.
  47  * 500ms) when Vegas was designed. Also, packets are timed once per RTT as in
  48  * the original paper.
  49  *
  50  * Originally released as part of the NewTCP research project at Swinburne
  51  * University of Technology's Centre for Advanced Internet Architectures,
  52  * Melbourne, Australia, which was made possible in part by a grant from the
  53  * Cisco University Research Program Fund at Community Foundation Silicon
  54  * Valley. More details are available at:
  55  *   http://caia.swin.edu.au/urp/newtcp/
  56  */
  57
  58 #include <sys/cdefs.h>
  59 __FBSDID("$FreeBSD$");
  60
  61 #include <sys/param.h>
  62 #include <sys/kernel.h>
  63 #include <sys/khelp.h>
  64 #include <sys/malloc.h>
  65 #include <sys/module.h>
  66 #include <sys/queue.h>
  67 #include <sys/socket.h>
  68 #include <sys/socketvar.h>
  69 #include <sys/sysctl.h>
  70 #include <sys/systm.h>
  71
  72 #include <net/vnet.h>
  73
  74 #include <net/route.h>
  75 #include <net/route/nhop.h>
  76
  77 #include <netinet/in_pcb.h>
  78 #include <netinet/tcp.h>
  79 #include <netinet/tcp_timer.h>
  80 #include <netinet/tcp_var.h>
  81 #include <netinet/cc/cc.h>
  82 #include <netinet/cc/cc_module.h>
  83
  84 #include <netinet/khelp/h_ertt.h>
  85
  86 /*
  87  * Private signal type for rate based congestion signal.
  88  * See <netinet/cc.h> for appropriate bit-range to use for private signals.
  89  */
  90 #define CC_VEGAS_RATE   0x01000000
  91
  92 static void     vegas_ack_received(struct cc_var *ccv, uint16_t ack_type);
  93 static void     vegas_cb_destroy(struct cc_var *ccv);
  94 static int      vegas_cb_init(struct cc_var *ccv, void *ptr);
  95 static void     vegas_cong_signal(struct cc_var *ccv, uint32_t signal_type);
  96 static void     vegas_conn_init(struct cc_var *ccv);
  97 static int      vegas_mod_init(void);
  98 static size_t   vegas_data_sz(void);
  99
 100 struct vegas {
 101         int slow_start_toggle;
 102 };
 103
 104 static int32_t ertt_id;
 105
 106 VNET_DEFINE_STATIC(uint32_t, vegas_alpha) = 1;
 107 VNET_DEFINE_STATIC(uint32_t, vegas_beta) = 3;
 108 #define V_vegas_alpha   VNET(vegas_alpha)
 109 #define V_vegas_beta    VNET(vegas_beta)
 110
 111 struct cc_algo vegas_cc_algo = {
 112         .name = "vegas",
 113         .ack_received = vegas_ack_received,
 114         .cb_destroy = vegas_cb_destroy,
 115         .cb_init = vegas_cb_init,
 116         .cong_signal = vegas_cong_signal,
 117         .conn_init = vegas_conn_init,
 118         .mod_init = vegas_mod_init,
 119         .cc_data_sz = vegas_data_sz,
 120         .after_idle = newreno_cc_after_idle,
 121         .post_recovery = newreno_cc_post_recovery,
 122 };
 123
 124 /*
 125  * The vegas window adjustment is done once every RTT, as indicated by the
 126  * ERTT_NEW_MEASUREMENT flag. This flag is reset once the new measurement data
 127  * has been used.
 128  */
 129 static void
 130 vegas_ack_received(struct cc_var *ccv, uint16_t ack_type)
 131 {
 132         struct ertt *e_t;
 133         struct vegas *vegas_data;
 134         long actual_tx_rate, expected_tx_rate, ndiff;
 135
 136         e_t = khelp_get_osd(CCV(ccv, osd), ertt_id);
 137         vegas_data = ccv->cc_data;
 138
 139         if (e_t->flags & ERTT_NEW_MEASUREMENT) { /* Once per RTT. */
 140                 if (e_t->minrtt && e_t->markedpkt_rtt) {
 141                         expected_tx_rate = e_t->marked_snd_cwnd / e_t->minrtt;
 142                         actual_tx_rate = e_t->bytes_tx_in_marked_rtt /
 143                             e_t->markedpkt_rtt;
 144                         ndiff = (expected_tx_rate - actual_tx_rate) *
 145                             e_t->minrtt / CCV(ccv, t_maxseg);
 146
 147                         if (ndiff < V_vegas_alpha) {
 148                                 if (CCV(ccv, snd_cwnd) <=
 149                                     CCV(ccv, snd_ssthresh)) {
 150                                         vegas_data->slow_start_toggle =
 151                                             vegas_data->slow_start_toggle ?
 152                                             0 : 1;
 153                                 } else {
 154                                         vegas_data->slow_start_toggle = 0;
 155                                         CCV(ccv, snd_cwnd) =
 156                                             min(CCV(ccv, snd_cwnd) +
 157                                             CCV(ccv, t_maxseg),
 158                                             TCP_MAXWIN << CCV(ccv, snd_scale));
 159                                 }
 160                         } else if (ndiff > V_vegas_beta) {
 161                                 /* Rate-based congestion. */
 162                                 vegas_cong_signal(ccv, CC_VEGAS_RATE);
 163                                 vegas_data->slow_start_toggle = 0;
 164                         }
 165                 }
 166                 e_t->flags &= ~ERTT_NEW_MEASUREMENT;
 167         }
 168
 169         if (vegas_data->slow_start_toggle)
 170                 newreno_cc_ack_received(ccv, ack_type);
 171 }
 172
 173 static void
 174 vegas_cb_destroy(struct cc_var *ccv)
 175 {
 176         free(ccv->cc_data, M_CC_MEM);
 177 }
 178
 179 static size_t
 180 vegas_data_sz(void)
 181 {
 182         return (sizeof(struct vegas));
 183 }
 184
 185 static int
 186 vegas_cb_init(struct cc_var *ccv, void *ptr)
 187 {
 188         struct vegas *vegas_data;
 189
 190         INP_WLOCK_ASSERT(tptoinpcb(ccv->ccvc.tcp));
 191         if (ptr == NULL) {
 192                 vegas_data = malloc(sizeof(struct vegas), M_CC_MEM, M_NOWAIT);
 193                 if (vegas_data == NULL)
 194                         return (ENOMEM);
 195         } else
 196                 vegas_data = ptr;
 197
 198         vegas_data->slow_start_toggle = 1;
 199         ccv->cc_data = vegas_data;
 200
 201         return (0);
 202 }
 203
 204 /*
 205  * If congestion has been triggered triggered by the Vegas measured rates, it is
 206  * handled here, otherwise it falls back to newreno's congestion handling.
 207  */
 208 static void
 209 vegas_cong_signal(struct cc_var *ccv, uint32_t signal_type)
 210 {
 211         struct vegas *vegas_data;
 212         int presignalrecov;
 213
 214         vegas_data = ccv->cc_data;
 215
 216         if (IN_RECOVERY(CCV(ccv, t_flags)))
 217                 presignalrecov = 1;
 218         else
 219                 presignalrecov = 0;
 220
 221         switch(signal_type) {
 222         case CC_VEGAS_RATE:
 223                 if (!IN_RECOVERY(CCV(ccv, t_flags))) {
 224                         CCV(ccv, snd_cwnd) = max(2 * CCV(ccv, t_maxseg),
 225                             CCV(ccv, snd_cwnd) - CCV(ccv, t_maxseg));
 226                         if (CCV(ccv, snd_cwnd) < CCV(ccv, snd_ssthresh))
 227                                 /* Exit slow start. */
 228                                 CCV(ccv, snd_ssthresh) = CCV(ccv, snd_cwnd);
 229                 }
 230                 break;
 231
 232         default:
 233                 newreno_cc_cong_signal(ccv, signal_type);
 234         }
 235
 236         if (IN_RECOVERY(CCV(ccv, t_flags)) && !presignalrecov)
 237                 vegas_data->slow_start_toggle =
 238                     (CCV(ccv, snd_cwnd) < CCV(ccv, snd_ssthresh)) ? 1 : 0;
 239 }
 240
 241 static void
 242 vegas_conn_init(struct cc_var *ccv)
 243 {
 244         struct vegas *vegas_data;
 245
 246         vegas_data = ccv->cc_data;
 247         vegas_data->slow_start_toggle = 1;
 248 }
 249
 250 static int
 251 vegas_mod_init(void)
 252 {
 253         ertt_id = khelp_get_id("ertt");
 254         if (ertt_id <= 0) {
 255                 printf("%s: h_ertt module not found\n", __func__);
 256                 return (ENOENT);
 257         }
 258         return (0);
 259 }
 260
 261 static int
 262 vegas_alpha_handler(SYSCTL_HANDLER_ARGS)
 263 {
 264         int error;
 265         uint32_t new;
 266
 267         new = V_vegas_alpha;
 268         error = sysctl_handle_int(oidp, &new, 0, req);
 269         if (error == 0 && req->newptr != NULL) {
 270                 if (new == 0 || new > V_vegas_beta)
 271                         error = EINVAL;
 272                 else
 273                         V_vegas_alpha = new;
 274         }
 275
 276         return (error);
 277 }
 278
 279 static int
 280 vegas_beta_handler(SYSCTL_HANDLER_ARGS)
 281 {
 282         int error;
 283         uint32_t new;
 284
 285         new = V_vegas_beta;
 286         error = sysctl_handle_int(oidp, &new, 0, req);
 287         if (error == 0 && req->newptr != NULL) {
 288                 if (new == 0 || new < V_vegas_alpha)
 289                          error = EINVAL;
 290                 else
 291                         V_vegas_beta = new;
 292         }
 293
 294         return (error);
 295 }
 296
 297 SYSCTL_DECL(_net_inet_tcp_cc_vegas);
 298 SYSCTL_NODE(_net_inet_tcp_cc, OID_AUTO, vegas,
 299     CTLFLAG_RW | CTLFLAG_MPSAFE, NULL,
 300     "Vegas related settings");
 301
 302 SYSCTL_PROC(_net_inet_tcp_cc_vegas, OID_AUTO, alpha,
 303     CTLFLAG_VNET | CTLTYPE_UINT | CTLFLAG_RW | CTLFLAG_NEEDGIANT,
 304     &VNET_NAME(vegas_alpha), 1, &vegas_alpha_handler, "IU",
 305     "vegas alpha, specified as number of \"buffers\" (0 < alpha < beta)");
 306
 307 SYSCTL_PROC(_net_inet_tcp_cc_vegas, OID_AUTO, beta,
 308     CTLFLAG_VNET | CTLTYPE_UINT | CTLFLAG_RW | CTLFLAG_NEEDGIANT,
 309     &VNET_NAME(vegas_beta), 3, &vegas_beta_handler, "IU",
 310     "vegas beta, specified as number of \"buffers\" (0 < alpha < beta)");
 311
 312 DECLARE_CC_MODULE(vegas, &vegas_cc_algo);
 313 MODULE_VERSION(vegas, 2);
 314 MODULE_DEPEND(vegas, ertt, 1, 1, 1);