net/ipv4/tcp_cong.c

   1 /*
   2  * Plugable TCP congestion control support and newReno
   3  * congestion control.
   4  * Based on ideas from I/O scheduler suport and Web100.
   5  *
   6  * Copyright (C) 2005 Stephen Hemminger <shemminger@osdl.org>
   7  */
   8
   9 #define pr_fmt(fmt) "TCP: " fmt
  10
  11 #include <linux/module.h>
  12 #include <linux/mm.h>
  13 #include <linux/types.h>
  14 #include <linux/list.h>
  15 #include <linux/gfp.h>
  16 #include <net/tcp.h>
  17
  18 int sysctl_tcp_max_ssthresh = 0;
  19
  20 static DEFINE_SPINLOCK(tcp_cong_list_lock);
  21 static LIST_HEAD(tcp_cong_list);
  22
  23 /* Simple linear search, don't expect many entries! */
  24 static struct tcp_congestion_ops *tcp_ca_find(const char *name)
  25 {
  26         struct tcp_congestion_ops *e;
  27
  28         list_for_each_entry_rcu(e, &tcp_cong_list, list) {
  29                 if (strcmp(e->name, name) == 0)
  30                         return e;
  31         }
  32
  33         return NULL;
  34 }
  35
  36 /*
  37  * Attach new congestion control algorithm to the list
  38  * of available options.
  39  */
  40 int tcp_register_congestion_control(struct tcp_congestion_ops *ca)
  41 {
  42         int ret = 0;
  43
  44         /* all algorithms must implement ssthresh and cong_avoid ops */
  45         if (!ca->ssthresh || !ca->cong_avoid) {
  46                 pr_err("%s does not implement required ops\n", ca->name);
  47                 return -EINVAL;
  48         }
  49
  50         spin_lock(&tcp_cong_list_lock);
  51         if (tcp_ca_find(ca->name)) {
  52                 pr_notice("%s already registered\n", ca->name);
  53                 ret = -EEXIST;
  54         } else {
  55                 list_add_tail_rcu(&ca->list, &tcp_cong_list);
  56                 pr_info("%s registered\n", ca->name);
  57         }
  58         spin_unlock(&tcp_cong_list_lock);
  59
  60         return ret;
  61 }
  62 EXPORT_SYMBOL_GPL(tcp_register_congestion_control);
  63
  64 /*
  65  * Remove congestion control algorithm, called from
  66  * the module's remove function.  Module ref counts are used
  67  * to ensure that this can't be done till all sockets using
  68  * that method are closed.
  69  */
  70 void tcp_unregister_congestion_control(struct tcp_congestion_ops *ca)
  71 {
  72         spin_lock(&tcp_cong_list_lock);
  73         list_del_rcu(&ca->list);
  74         spin_unlock(&tcp_cong_list_lock);
  75 }
  76 EXPORT_SYMBOL_GPL(tcp_unregister_congestion_control);
  77
  78 /* Assign choice of congestion control. */
  79 void tcp_init_congestion_control(struct sock *sk)
  80 {
  81         struct inet_connection_sock *icsk = inet_csk(sk);
  82         struct tcp_congestion_ops *ca;
  83
  84         /* if no choice made yet assign the current value set as default */
  85         if (icsk->icsk_ca_ops == &tcp_init_congestion_ops) {
  86                 rcu_read_lock();
  87                 list_for_each_entry_rcu(ca, &tcp_cong_list, list) {
  88                         if (try_module_get(ca->owner)) {
  89                                 icsk->icsk_ca_ops = ca;
  90                                 break;
  91                         }
  92
  93                         /* fallback to next available */
  94                 }
  95                 rcu_read_unlock();
  96         }
  97
  98         if (icsk->icsk_ca_ops->init)
  99                 icsk->icsk_ca_ops->init(sk);
 100 }
 101
 102 /* Manage refcounts on socket close. */
 103 void tcp_cleanup_congestion_control(struct sock *sk)
 104 {
 105         struct inet_connection_sock *icsk = inet_csk(sk);
 106
 107         if (icsk->icsk_ca_ops->release)
 108                 icsk->icsk_ca_ops->release(sk);
 109         module_put(icsk->icsk_ca_ops->owner);
 110 }
 111
 112 /* Used by sysctl to change default congestion control */
 113 int tcp_set_default_congestion_control(const char *name)
 114 {
 115         struct tcp_congestion_ops *ca;
 116         int ret = -ENOENT;
 117
 118         spin_lock(&tcp_cong_list_lock);
 119         ca = tcp_ca_find(name);
 120 #ifdef CONFIG_MODULES
 121         if (!ca && capable(CAP_NET_ADMIN)) {
 122                 spin_unlock(&tcp_cong_list_lock);
 123
 124                 request_module("tcp_%s", name);
 125                 spin_lock(&tcp_cong_list_lock);
 126                 ca = tcp_ca_find(name);
 127         }
 128 #endif
 129
 130         if (ca) {
 131                 ca->flags |= TCP_CONG_NON_RESTRICTED;   /* default is always allowed */
 132                 list_move(&ca->list, &tcp_cong_list);
 133                 ret = 0;
 134         }
 135         spin_unlock(&tcp_cong_list_lock);
 136
 137         return ret;
 138 }
 139
 140 /* Set default value from kernel configuration at bootup */
 141 static int __init tcp_congestion_default(void)
 142 {
 143         return tcp_set_default_congestion_control(CONFIG_DEFAULT_TCP_CONG);
 144 }
 145 late_initcall(tcp_congestion_default);
 146
 147
 148 /* Build string with list of available congestion control values */
 149 void tcp_get_available_congestion_control(char *buf, size_t maxlen)
 150 {
 151         struct tcp_congestion_ops *ca;
 152         size_t offs = 0;
 153
 154         rcu_read_lock();
 155         list_for_each_entry_rcu(ca, &tcp_cong_list, list) {
 156                 offs += snprintf(buf + offs, maxlen - offs,
 157                                  "%s%s",
 158                                  offs == 0 ? "" : " ", ca->name);
 159
 160         }
 161         rcu_read_unlock();
 162 }
 163
 164 /* Get current default congestion control */
 165 void tcp_get_default_congestion_control(char *name)
 166 {
 167         struct tcp_congestion_ops *ca;
 168         /* We will always have reno... */
 169         BUG_ON(list_empty(&tcp_cong_list));
 170
 171         rcu_read_lock();
 172         ca = list_entry(tcp_cong_list.next, struct tcp_congestion_ops, list);
 173         strncpy(name, ca->name, TCP_CA_NAME_MAX);
 174         rcu_read_unlock();
 175 }
 176
 177 /* Built list of non-restricted congestion control values */
 178 void tcp_get_allowed_congestion_control(char *buf, size_t maxlen)
 179 {
 180         struct tcp_congestion_ops *ca;
 181         size_t offs = 0;
 182
 183         *buf = '\0';
 184         rcu_read_lock();
 185         list_for_each_entry_rcu(ca, &tcp_cong_list, list) {
 186                 if (!(ca->flags & TCP_CONG_NON_RESTRICTED))
 187                         continue;
 188                 offs += snprintf(buf + offs, maxlen - offs,
 189                                  "%s%s",
 190                                  offs == 0 ? "" : " ", ca->name);
 191
 192         }
 193         rcu_read_unlock();
 194 }
 195
 196 /* Change list of non-restricted congestion control */
 197 int tcp_set_allowed_congestion_control(char *val)
 198 {
 199         struct tcp_congestion_ops *ca;
 200         char *saved_clone, *clone, *name;
 201         int ret = 0;
 202
 203         saved_clone = clone = kstrdup(val, GFP_USER);
 204         if (!clone)
 205                 return -ENOMEM;
 206
 207         spin_lock(&tcp_cong_list_lock);
 208         /* pass 1 check for bad entries */
 209         while ((name = strsep(&clone, " ")) && *name) {
 210                 ca = tcp_ca_find(name);
 211                 if (!ca) {
 212                         ret = -ENOENT;
 213                         goto out;
 214                 }
 215         }
 216
 217         /* pass 2 clear old values */
 218         list_for_each_entry_rcu(ca, &tcp_cong_list, list)
 219                 ca->flags &= ~TCP_CONG_NON_RESTRICTED;
 220
 221         /* pass 3 mark as allowed */
 222         while ((name = strsep(&val, " ")) && *name) {
 223                 ca = tcp_ca_find(name);
 224                 WARN_ON(!ca);
 225                 if (ca)
 226                         ca->flags |= TCP_CONG_NON_RESTRICTED;
 227         }
 228 out:
 229         spin_unlock(&tcp_cong_list_lock);
 230         kfree(saved_clone);
 231
 232         return ret;
 233 }
 234
 235
 236 /* Change congestion control for socket */
 237 int tcp_set_congestion_control(struct sock *sk, const char *name)
 238 {
 239         struct inet_connection_sock *icsk = inet_csk(sk);
 240         struct tcp_congestion_ops *ca;
 241         int err = 0;
 242
 243         rcu_read_lock();
 244         ca = tcp_ca_find(name);
 245
 246         /* no change asking for existing value */
 247         if (ca == icsk->icsk_ca_ops)
 248                 goto out;
 249
 250 #ifdef CONFIG_MODULES
 251         /* not found attempt to autoload module */
 252         if (!ca && capable(CAP_NET_ADMIN)) {
 253                 rcu_read_unlock();
 254                 request_module("tcp_%s", name);
 255                 rcu_read_lock();
 256                 ca = tcp_ca_find(name);
 257         }
 258 #endif
 259         if (!ca)
 260                 err = -ENOENT;
 261
 262         else if (!((ca->flags & TCP_CONG_NON_RESTRICTED) || capable(CAP_NET_ADMIN)))
 263                 err = -EPERM;
 264
 265         else if (!try_module_get(ca->owner))
 266                 err = -EBUSY;
 267
 268         else {
 269                 tcp_cleanup_congestion_control(sk);
 270                 icsk->icsk_ca_ops = ca;
 271
 272                 if (sk->sk_state != TCP_CLOSE && icsk->icsk_ca_ops->init)
 273                         icsk->icsk_ca_ops->init(sk);
 274         }
 275  out:
 276         rcu_read_unlock();
 277         return err;
 278 }
 279
 280 /* RFC2861 Check whether we are limited by application or congestion window
 281  * This is the inverse of cwnd check in tcp_tso_should_defer
 282  */
 283 bool tcp_is_cwnd_limited(const struct sock *sk, u32 in_flight)
 284 {
 285         const struct tcp_sock *tp = tcp_sk(sk);
 286         u32 left;
 287
 288         if (in_flight >= tp->snd_cwnd)
 289                 return true;
 290
 291         left = tp->snd_cwnd - in_flight;
 292         if (sk_can_gso(sk) &&
 293             left * sysctl_tcp_tso_win_divisor < tp->snd_cwnd &&
 294             left * tp->mss_cache < sk->sk_gso_max_size &&
 295             left < sk->sk_gso_max_segs)
 296                 return true;
 297         return left <= tcp_max_tso_deferred_mss(tp);
 298 }
 299 EXPORT_SYMBOL_GPL(tcp_is_cwnd_limited);
 300
 301 /*
 302  * Slow start is used when congestion window is less than slow start
 303  * threshold. This version implements the basic RFC2581 version
 304  * and optionally supports:
 305  *      RFC3742 Limited Slow Start        - growth limited to max_ssthresh
 306  *      RFC3465 Appropriate Byte Counting - growth limited by bytes acknowledged
 307  */
 308 void tcp_slow_start(struct tcp_sock *tp)
 309 {
 310         int cnt; /* increase in packets */
 311         unsigned int delta = 0;
 312
 313         /* RFC3465: ABC Slow start
 314          * Increase only after a full MSS of bytes is acked
 315          *
 316          * TCP sender SHOULD increase cwnd by the number of
 317          * previously unacknowledged bytes ACKed by each incoming
 318          * acknowledgment, provided the increase is not more than L
 319          */
 320         if (sysctl_tcp_abc && tp->bytes_acked < tp->mss_cache)
 321                 return;
 322
 323         if (sysctl_tcp_max_ssthresh > 0 && tp->snd_cwnd > sysctl_tcp_max_ssthresh)
 324                 cnt = sysctl_tcp_max_ssthresh >> 1;     /* limited slow start */
 325         else
 326                 cnt = tp->snd_cwnd;                     /* exponential increase */
 327
 328         /* RFC3465: ABC
 329          * We MAY increase by 2 if discovered delayed ack
 330          */
 331         if (sysctl_tcp_abc > 1 && tp->bytes_acked >= 2*tp->mss_cache)
 332                 cnt <<= 1;
 333         tp->bytes_acked = 0;
 334
 335         tp->snd_cwnd_cnt += cnt;
 336         while (tp->snd_cwnd_cnt >= tp->snd_cwnd) {
 337                 tp->snd_cwnd_cnt -= tp->snd_cwnd;
 338                 delta++;
 339         }
 340         tp->snd_cwnd = min(tp->snd_cwnd + delta, tp->snd_cwnd_clamp);
 341 }
 342 EXPORT_SYMBOL_GPL(tcp_slow_start);
 343
 344 /* In theory this is tp->snd_cwnd += 1 / tp->snd_cwnd (or alternative w) */
 345 void tcp_cong_avoid_ai(struct tcp_sock *tp, u32 w)
 346 {
 347         if (tp->snd_cwnd_cnt >= w) {
 348                 if (tp->snd_cwnd < tp->snd_cwnd_clamp)
 349                         tp->snd_cwnd++;
 350                 tp->snd_cwnd_cnt = 0;
 351         } else {
 352                 tp->snd_cwnd_cnt++;
 353         }
 354 }
 355 EXPORT_SYMBOL_GPL(tcp_cong_avoid_ai);
 356
 357 /*
 358  * TCP Reno congestion control
 359  * This is special case used for fallback as well.
 360  */
 361 /* This is Jacobson's slow start and congestion avoidance.
 362  * SIGCOMM '88, p. 328.
 363  */
 364 void tcp_reno_cong_avoid(struct sock *sk, u32 ack, u32 in_flight)
 365 {
 366         struct tcp_sock *tp = tcp_sk(sk);
 367
 368         if (!tcp_is_cwnd_limited(sk, in_flight))
 369                 return;
 370
 371         /* In "safe" area, increase. */
 372         if (tp->snd_cwnd <= tp->snd_ssthresh)
 373                 tcp_slow_start(tp);
 374
 375         /* In dangerous area, increase slowly. */
 376         else if (sysctl_tcp_abc) {
 377                 /* RFC3465: Appropriate Byte Count
 378                  * increase once for each full cwnd acked
 379                  */
 380                 if (tp->bytes_acked >= tp->snd_cwnd*tp->mss_cache) {
 381                         tp->bytes_acked -= tp->snd_cwnd*tp->mss_cache;
 382                         if (tp->snd_cwnd < tp->snd_cwnd_clamp)
 383                                 tp->snd_cwnd++;
 384                 }
 385         } else {
 386                 tcp_cong_avoid_ai(tp, tp->snd_cwnd);
 387         }
 388 }
 389 EXPORT_SYMBOL_GPL(tcp_reno_cong_avoid);
 390
 391 /* Slow start threshold is half the congestion window (min 2) */
 392 u32 tcp_reno_ssthresh(struct sock *sk)
 393 {
 394         const struct tcp_sock *tp = tcp_sk(sk);
 395         return max(tp->snd_cwnd >> 1U, 2U);
 396 }
 397 EXPORT_SYMBOL_GPL(tcp_reno_ssthresh);
 398
 399 /* Lower bound on congestion window with halving. */
 400 u32 tcp_reno_min_cwnd(const struct sock *sk)
 401 {
 402         const struct tcp_sock *tp = tcp_sk(sk);
 403         return tp->snd_ssthresh/2;
 404 }
 405 EXPORT_SYMBOL_GPL(tcp_reno_min_cwnd);
 406
 407 struct tcp_congestion_ops tcp_reno = {
 408         .flags          = TCP_CONG_NON_RESTRICTED,
 409         .name           = "reno",
 410         .owner          = THIS_MODULE,
 411         .ssthresh       = tcp_reno_ssthresh,
 412         .cong_avoid     = tcp_reno_cong_avoid,
 413         .min_cwnd       = tcp_reno_min_cwnd,
 414 };
 415
 416 /* Initial congestion control used (until SYN)
 417  * really reno under another name so we can tell difference
 418  * during tcp_set_default_congestion_control
 419  */
 420 struct tcp_congestion_ops tcp_init_congestion_ops  = {
 421         .name           = "",
 422         .owner          = THIS_MODULE,
 423         .ssthresh       = tcp_reno_ssthresh,
 424         .cong_avoid     = tcp_reno_cong_avoid,
 425         .min_cwnd       = tcp_reno_min_cwnd,
 426 };
 427 EXPORT_SYMBOL_GPL(tcp_init_congestion_ops);