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