1 /* 2 * Plugable TCP congestion control support and newReno 3 * congestion control. 4 * Based on ideas from I/O scheduler support 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 static DEFINE_SPINLOCK(tcp_cong_list_lock); 19 static LIST_HEAD(tcp_cong_list); 20 21 /* Simple linear search, don't expect many entries! */ 22 static 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 */ 38 int 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("%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("%s already registered\n", ca->name); 51 ret = -EEXIST; 52 } else { 53 list_add_tail_rcu(&ca->list, &tcp_cong_list); 54 pr_info("%s registered\n", ca->name); 55 } 56 spin_unlock(&tcp_cong_list_lock); 57 58 return ret; 59 } 60 EXPORT_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 */ 68 void 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 } 74 EXPORT_SYMBOL_GPL(tcp_unregister_congestion_control); 75 76 /* Assign choice of congestion control. */ 77 void 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. */ 101 void 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 */ 111 int 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 */ 139 static int __init tcp_congestion_default(void) 140 { 141 return tcp_set_default_congestion_control(CONFIG_DEFAULT_TCP_CONG); 142 } 143 late_initcall(tcp_congestion_default); 144 145 /* Build string with list of available congestion control values */ 146 void tcp_get_available_congestion_control(char *buf, size_t maxlen) 147 { 148 struct tcp_congestion_ops *ca; 149 size_t offs = 0; 150 151 rcu_read_lock(); 152 list_for_each_entry_rcu(ca, &tcp_cong_list, list) { 153 offs += snprintf(buf + offs, maxlen - offs, 154 "%s%s", 155 offs == 0 ? "" : " ", ca->name); 156 } 157 rcu_read_unlock(); 158 } 159 160 /* Get current default congestion control */ 161 void tcp_get_default_congestion_control(char *name) 162 { 163 struct tcp_congestion_ops *ca; 164 /* We will always have reno... */ 165 BUG_ON(list_empty(&tcp_cong_list)); 166 167 rcu_read_lock(); 168 ca = list_entry(tcp_cong_list.next, struct tcp_congestion_ops, list); 169 strncpy(name, ca->name, TCP_CA_NAME_MAX); 170 rcu_read_unlock(); 171 } 172 173 /* Built list of non-restricted congestion control values */ 174 void tcp_get_allowed_congestion_control(char *buf, size_t maxlen) 175 { 176 struct tcp_congestion_ops *ca; 177 size_t offs = 0; 178 179 *buf = '\0'; 180 rcu_read_lock(); 181 list_for_each_entry_rcu(ca, &tcp_cong_list, list) { 182 if (!(ca->flags & TCP_CONG_NON_RESTRICTED)) 183 continue; 184 offs += snprintf(buf + offs, maxlen - offs, 185 "%s%s", 186 offs == 0 ? "" : " ", ca->name); 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 *saved_clone, *clone, *name; 196 int ret = 0; 197 198 saved_clone = 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 old values */ 213 list_for_each_entry_rcu(ca, &tcp_cong_list, list) 214 ca->flags &= ~TCP_CONG_NON_RESTRICTED; 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->flags |= TCP_CONG_NON_RESTRICTED; 222 } 223 out: 224 spin_unlock(&tcp_cong_list_lock); 225 kfree(saved_clone); 226 227 return ret; 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 240 /* no change asking for existing value */ 241 if (ca == icsk->icsk_ca_ops) 242 goto out; 243 244 #ifdef CONFIG_MODULES 245 /* not found attempt to autoload module */ 246 if (!ca && capable(CAP_NET_ADMIN)) { 247 rcu_read_unlock(); 248 request_module("tcp_%s", name); 249 rcu_read_lock(); 250 ca = tcp_ca_find(name); 251 } 252 #endif 253 if (!ca) 254 err = -ENOENT; 255 256 else if (!((ca->flags & TCP_CONG_NON_RESTRICTED) || 257 ns_capable(sock_net(sk)->user_ns, CAP_NET_ADMIN))) 258 err = -EPERM; 259 260 else if (!try_module_get(ca->owner)) 261 err = -EBUSY; 262 263 else { 264 tcp_cleanup_congestion_control(sk); 265 icsk->icsk_ca_ops = ca; 266 267 if (sk->sk_state != TCP_CLOSE && icsk->icsk_ca_ops->init) 268 icsk->icsk_ca_ops->init(sk); 269 } 270 out: 271 rcu_read_unlock(); 272 return err; 273 } 274 275 /* Slow start is used when congestion window is no greater than the slow start 276 * threshold. We base on RFC2581 and also handle stretch ACKs properly. 277 * We do not implement RFC3465 Appropriate Byte Counting (ABC) per se but 278 * something better;) a packet is only considered (s)acked in its entirety to 279 * defend the ACK attacks described in the RFC. Slow start processes a stretch 280 * ACK of degree N as if N acks of degree 1 are received back to back except 281 * ABC caps N to 2. Slow start exits when cwnd grows over ssthresh and 282 * returns the leftover acks to adjust cwnd in congestion avoidance mode. 283 */ 284 int tcp_slow_start(struct tcp_sock *tp, u32 acked) 285 { 286 u32 cwnd = tp->snd_cwnd + acked; 287 288 if (cwnd > tp->snd_ssthresh) 289 cwnd = tp->snd_ssthresh + 1; 290 acked -= cwnd - tp->snd_cwnd; 291 tp->snd_cwnd = min(cwnd, tp->snd_cwnd_clamp); 292 return acked; 293 } 294 EXPORT_SYMBOL_GPL(tcp_slow_start); 295 296 /* In theory this is tp->snd_cwnd += 1 / tp->snd_cwnd (or alternative w) */ 297 void tcp_cong_avoid_ai(struct tcp_sock *tp, u32 w) 298 { 299 if (tp->snd_cwnd_cnt >= w) { 300 if (tp->snd_cwnd < tp->snd_cwnd_clamp) 301 tp->snd_cwnd++; 302 tp->snd_cwnd_cnt = 0; 303 } else { 304 tp->snd_cwnd_cnt++; 305 } 306 } 307 EXPORT_SYMBOL_GPL(tcp_cong_avoid_ai); 308 309 /* 310 * TCP Reno congestion control 311 * This is special case used for fallback as well. 312 */ 313 /* This is Jacobson's slow start and congestion avoidance. 314 * SIGCOMM '88, p. 328. 315 */ 316 void tcp_reno_cong_avoid(struct sock *sk, u32 ack, u32 acked) 317 { 318 struct tcp_sock *tp = tcp_sk(sk); 319 320 if (!tcp_is_cwnd_limited(sk)) 321 return; 322 323 /* In "safe" area, increase. */ 324 if (tp->snd_cwnd <= tp->snd_ssthresh) 325 tcp_slow_start(tp, acked); 326 /* In dangerous area, increase slowly. */ 327 else 328 tcp_cong_avoid_ai(tp, tp->snd_cwnd); 329 } 330 EXPORT_SYMBOL_GPL(tcp_reno_cong_avoid); 331 332 /* Slow start threshold is half the congestion window (min 2) */ 333 u32 tcp_reno_ssthresh(struct sock *sk) 334 { 335 const struct tcp_sock *tp = tcp_sk(sk); 336 337 return max(tp->snd_cwnd >> 1U, 2U); 338 } 339 EXPORT_SYMBOL_GPL(tcp_reno_ssthresh); 340 341 struct tcp_congestion_ops tcp_reno = { 342 .flags = TCP_CONG_NON_RESTRICTED, 343 .name = "reno", 344 .owner = THIS_MODULE, 345 .ssthresh = tcp_reno_ssthresh, 346 .cong_avoid = tcp_reno_cong_avoid, 347 }; 348 349 /* Initial congestion control used (until SYN) 350 * really reno under another name so we can tell difference 351 * during tcp_set_default_congestion_control 352 */ 353 struct tcp_congestion_ops tcp_init_congestion_ops = { 354 .name = "", 355 .owner = THIS_MODULE, 356 .ssthresh = tcp_reno_ssthresh, 357 .cong_avoid = tcp_reno_cong_avoid, 358 }; 359 EXPORT_SYMBOL_GPL(tcp_init_congestion_ops); 360