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