1 | /* |
2 | * Pluggable 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 <linux/jhash.h> |
17 | #include <net/tcp.h> |
18 | |
19 | static DEFINE_SPINLOCK(tcp_cong_list_lock); |
20 | static LIST_HEAD(tcp_cong_list); |
21 | |
22 | /* Simple linear search, don't expect many entries! */ |
23 | static struct tcp_congestion_ops *tcp_ca_find(const char *name) |
24 | { |
25 | struct tcp_congestion_ops *e; |
26 | |
27 | list_for_each_entry_rcu(e, &tcp_cong_list, list) { |
28 | if (strcmp(e->name, name) == 0) |
29 | return e; |
30 | } |
31 | |
32 | return NULL; |
33 | } |
34 | |
35 | /* Must be called with rcu lock held */ |
36 | static struct tcp_congestion_ops *tcp_ca_find_autoload(struct net *net, |
37 | const char *name) |
38 | { |
39 | struct tcp_congestion_ops *ca = tcp_ca_find(name); |
40 | |
41 | #ifdef CONFIG_MODULES |
42 | if (!ca && capable(CAP_NET_ADMIN)) { |
43 | rcu_read_unlock(); |
44 | request_module("tcp_%s" , name); |
45 | rcu_read_lock(); |
46 | ca = tcp_ca_find(name); |
47 | } |
48 | #endif |
49 | return ca; |
50 | } |
51 | |
52 | /* Simple linear search, not much in here. */ |
53 | struct tcp_congestion_ops *tcp_ca_find_key(u32 key) |
54 | { |
55 | struct tcp_congestion_ops *e; |
56 | |
57 | list_for_each_entry_rcu(e, &tcp_cong_list, list) { |
58 | if (e->key == key) |
59 | return e; |
60 | } |
61 | |
62 | return NULL; |
63 | } |
64 | |
65 | /* |
66 | * Attach new congestion control algorithm to the list |
67 | * of available options. |
68 | */ |
69 | int tcp_register_congestion_control(struct tcp_congestion_ops *ca) |
70 | { |
71 | int ret = 0; |
72 | |
73 | /* all algorithms must implement these */ |
74 | if (!ca->ssthresh || !ca->undo_cwnd || |
75 | !(ca->cong_avoid || ca->cong_control)) { |
76 | pr_err("%s does not implement required ops\n" , ca->name); |
77 | return -EINVAL; |
78 | } |
79 | |
80 | ca->key = jhash(ca->name, sizeof(ca->name), strlen(ca->name)); |
81 | |
82 | spin_lock(&tcp_cong_list_lock); |
83 | if (ca->key == TCP_CA_UNSPEC || tcp_ca_find_key(ca->key)) { |
84 | pr_notice("%s already registered or non-unique key\n" , |
85 | ca->name); |
86 | ret = -EEXIST; |
87 | } else { |
88 | list_add_tail_rcu(&ca->list, &tcp_cong_list); |
89 | pr_debug("%s registered\n" , ca->name); |
90 | } |
91 | spin_unlock(&tcp_cong_list_lock); |
92 | |
93 | return ret; |
94 | } |
95 | EXPORT_SYMBOL_GPL(tcp_register_congestion_control); |
96 | |
97 | /* |
98 | * Remove congestion control algorithm, called from |
99 | * the module's remove function. Module ref counts are used |
100 | * to ensure that this can't be done till all sockets using |
101 | * that method are closed. |
102 | */ |
103 | void tcp_unregister_congestion_control(struct tcp_congestion_ops *ca) |
104 | { |
105 | spin_lock(&tcp_cong_list_lock); |
106 | list_del_rcu(&ca->list); |
107 | spin_unlock(&tcp_cong_list_lock); |
108 | |
109 | /* Wait for outstanding readers to complete before the |
110 | * module gets removed entirely. |
111 | * |
112 | * A try_module_get() should fail by now as our module is |
113 | * in "going" state since no refs are held anymore and |
114 | * module_exit() handler being called. |
115 | */ |
116 | synchronize_rcu(); |
117 | } |
118 | EXPORT_SYMBOL_GPL(tcp_unregister_congestion_control); |
119 | |
120 | u32 tcp_ca_get_key_by_name(struct net *net, const char *name, bool *ecn_ca) |
121 | { |
122 | const struct tcp_congestion_ops *ca; |
123 | u32 key = TCP_CA_UNSPEC; |
124 | |
125 | might_sleep(); |
126 | |
127 | rcu_read_lock(); |
128 | ca = tcp_ca_find_autoload(net, name); |
129 | if (ca) { |
130 | key = ca->key; |
131 | *ecn_ca = ca->flags & TCP_CONG_NEEDS_ECN; |
132 | } |
133 | rcu_read_unlock(); |
134 | |
135 | return key; |
136 | } |
137 | EXPORT_SYMBOL_GPL(tcp_ca_get_key_by_name); |
138 | |
139 | char *tcp_ca_get_name_by_key(u32 key, char *buffer) |
140 | { |
141 | const struct tcp_congestion_ops *ca; |
142 | char *ret = NULL; |
143 | |
144 | rcu_read_lock(); |
145 | ca = tcp_ca_find_key(key); |
146 | if (ca) |
147 | ret = strncpy(buffer, ca->name, |
148 | TCP_CA_NAME_MAX); |
149 | rcu_read_unlock(); |
150 | |
151 | return ret; |
152 | } |
153 | EXPORT_SYMBOL_GPL(tcp_ca_get_name_by_key); |
154 | |
155 | /* Assign choice of congestion control. */ |
156 | void tcp_assign_congestion_control(struct sock *sk) |
157 | { |
158 | struct net *net = sock_net(sk); |
159 | struct inet_connection_sock *icsk = inet_csk(sk); |
160 | const struct tcp_congestion_ops *ca; |
161 | |
162 | rcu_read_lock(); |
163 | ca = rcu_dereference(net->ipv4.tcp_congestion_control); |
164 | if (unlikely(!try_module_get(ca->owner))) |
165 | ca = &tcp_reno; |
166 | icsk->icsk_ca_ops = ca; |
167 | rcu_read_unlock(); |
168 | |
169 | memset(icsk->icsk_ca_priv, 0, sizeof(icsk->icsk_ca_priv)); |
170 | if (ca->flags & TCP_CONG_NEEDS_ECN) |
171 | INET_ECN_xmit(sk); |
172 | else |
173 | INET_ECN_dontxmit(sk); |
174 | } |
175 | |
176 | void tcp_init_congestion_control(struct sock *sk) |
177 | { |
178 | const struct inet_connection_sock *icsk = inet_csk(sk); |
179 | |
180 | tcp_sk(sk)->prior_ssthresh = 0; |
181 | if (icsk->icsk_ca_ops->init) |
182 | icsk->icsk_ca_ops->init(sk); |
183 | if (tcp_ca_needs_ecn(sk)) |
184 | INET_ECN_xmit(sk); |
185 | else |
186 | INET_ECN_dontxmit(sk); |
187 | } |
188 | |
189 | static void tcp_reinit_congestion_control(struct sock *sk, |
190 | const struct tcp_congestion_ops *ca) |
191 | { |
192 | struct inet_connection_sock *icsk = inet_csk(sk); |
193 | |
194 | tcp_cleanup_congestion_control(sk); |
195 | icsk->icsk_ca_ops = ca; |
196 | icsk->icsk_ca_setsockopt = 1; |
197 | memset(icsk->icsk_ca_priv, 0, sizeof(icsk->icsk_ca_priv)); |
198 | |
199 | if (sk->sk_state != TCP_CLOSE) |
200 | tcp_init_congestion_control(sk); |
201 | } |
202 | |
203 | /* Manage refcounts on socket close. */ |
204 | void tcp_cleanup_congestion_control(struct sock *sk) |
205 | { |
206 | struct inet_connection_sock *icsk = inet_csk(sk); |
207 | |
208 | if (icsk->icsk_ca_ops->release) |
209 | icsk->icsk_ca_ops->release(sk); |
210 | module_put(icsk->icsk_ca_ops->owner); |
211 | } |
212 | |
213 | /* Used by sysctl to change default congestion control */ |
214 | int tcp_set_default_congestion_control(struct net *net, const char *name) |
215 | { |
216 | struct tcp_congestion_ops *ca; |
217 | const struct tcp_congestion_ops *prev; |
218 | int ret; |
219 | |
220 | rcu_read_lock(); |
221 | ca = tcp_ca_find_autoload(net, name); |
222 | if (!ca) { |
223 | ret = -ENOENT; |
224 | } else if (!try_module_get(ca->owner)) { |
225 | ret = -EBUSY; |
226 | } else { |
227 | prev = xchg(&net->ipv4.tcp_congestion_control, ca); |
228 | if (prev) |
229 | module_put(prev->owner); |
230 | |
231 | ca->flags |= TCP_CONG_NON_RESTRICTED; |
232 | ret = 0; |
233 | } |
234 | rcu_read_unlock(); |
235 | |
236 | return ret; |
237 | } |
238 | |
239 | /* Set default value from kernel configuration at bootup */ |
240 | static int __init tcp_congestion_default(void) |
241 | { |
242 | return tcp_set_default_congestion_control(&init_net, |
243 | CONFIG_DEFAULT_TCP_CONG); |
244 | } |
245 | late_initcall(tcp_congestion_default); |
246 | |
247 | /* Build string with list of available congestion control values */ |
248 | void tcp_get_available_congestion_control(char *buf, size_t maxlen) |
249 | { |
250 | struct tcp_congestion_ops *ca; |
251 | size_t offs = 0; |
252 | |
253 | rcu_read_lock(); |
254 | list_for_each_entry_rcu(ca, &tcp_cong_list, list) { |
255 | offs += snprintf(buf + offs, maxlen - offs, |
256 | "%s%s" , |
257 | offs == 0 ? "" : " " , ca->name); |
258 | } |
259 | rcu_read_unlock(); |
260 | } |
261 | |
262 | /* Get current default congestion control */ |
263 | void tcp_get_default_congestion_control(struct net *net, char *name) |
264 | { |
265 | const struct tcp_congestion_ops *ca; |
266 | |
267 | rcu_read_lock(); |
268 | ca = rcu_dereference(net->ipv4.tcp_congestion_control); |
269 | strncpy(name, ca->name, TCP_CA_NAME_MAX); |
270 | rcu_read_unlock(); |
271 | } |
272 | |
273 | /* Built list of non-restricted congestion control values */ |
274 | void tcp_get_allowed_congestion_control(char *buf, size_t maxlen) |
275 | { |
276 | struct tcp_congestion_ops *ca; |
277 | size_t offs = 0; |
278 | |
279 | *buf = '\0'; |
280 | rcu_read_lock(); |
281 | list_for_each_entry_rcu(ca, &tcp_cong_list, list) { |
282 | if (!(ca->flags & TCP_CONG_NON_RESTRICTED)) |
283 | continue; |
284 | offs += snprintf(buf + offs, maxlen - offs, |
285 | "%s%s" , |
286 | offs == 0 ? "" : " " , ca->name); |
287 | } |
288 | rcu_read_unlock(); |
289 | } |
290 | |
291 | /* Change list of non-restricted congestion control */ |
292 | int tcp_set_allowed_congestion_control(char *val) |
293 | { |
294 | struct tcp_congestion_ops *ca; |
295 | char *saved_clone, *clone, *name; |
296 | int ret = 0; |
297 | |
298 | saved_clone = clone = kstrdup(val, GFP_USER); |
299 | if (!clone) |
300 | return -ENOMEM; |
301 | |
302 | spin_lock(&tcp_cong_list_lock); |
303 | /* pass 1 check for bad entries */ |
304 | while ((name = strsep(&clone, " " )) && *name) { |
305 | ca = tcp_ca_find(name); |
306 | if (!ca) { |
307 | ret = -ENOENT; |
308 | goto out; |
309 | } |
310 | } |
311 | |
312 | /* pass 2 clear old values */ |
313 | list_for_each_entry_rcu(ca, &tcp_cong_list, list) |
314 | ca->flags &= ~TCP_CONG_NON_RESTRICTED; |
315 | |
316 | /* pass 3 mark as allowed */ |
317 | while ((name = strsep(&val, " " )) && *name) { |
318 | ca = tcp_ca_find(name); |
319 | WARN_ON(!ca); |
320 | if (ca) |
321 | ca->flags |= TCP_CONG_NON_RESTRICTED; |
322 | } |
323 | out: |
324 | spin_unlock(&tcp_cong_list_lock); |
325 | kfree(saved_clone); |
326 | |
327 | return ret; |
328 | } |
329 | |
330 | /* Change congestion control for socket. If load is false, then it is the |
331 | * responsibility of the caller to call tcp_init_congestion_control or |
332 | * tcp_reinit_congestion_control (if the current congestion control was |
333 | * already initialized. |
334 | */ |
335 | int tcp_set_congestion_control(struct sock *sk, const char *name, bool load, bool reinit) |
336 | { |
337 | struct inet_connection_sock *icsk = inet_csk(sk); |
338 | const struct tcp_congestion_ops *ca; |
339 | int err = 0; |
340 | |
341 | if (icsk->icsk_ca_dst_locked) |
342 | return -EPERM; |
343 | |
344 | rcu_read_lock(); |
345 | if (!load) |
346 | ca = tcp_ca_find(name); |
347 | else |
348 | ca = tcp_ca_find_autoload(sock_net(sk), name); |
349 | |
350 | /* No change asking for existing value */ |
351 | if (ca == icsk->icsk_ca_ops) { |
352 | icsk->icsk_ca_setsockopt = 1; |
353 | goto out; |
354 | } |
355 | |
356 | if (!ca) { |
357 | err = -ENOENT; |
358 | } else if (!load) { |
359 | const struct tcp_congestion_ops *old_ca = icsk->icsk_ca_ops; |
360 | |
361 | if (try_module_get(ca->owner)) { |
362 | if (reinit) { |
363 | tcp_reinit_congestion_control(sk, ca); |
364 | } else { |
365 | icsk->icsk_ca_ops = ca; |
366 | module_put(old_ca->owner); |
367 | } |
368 | } else { |
369 | err = -EBUSY; |
370 | } |
371 | } else if (!((ca->flags & TCP_CONG_NON_RESTRICTED) || |
372 | ns_capable(sock_net(sk)->user_ns, CAP_NET_ADMIN))) { |
373 | err = -EPERM; |
374 | } else if (!try_module_get(ca->owner)) { |
375 | err = -EBUSY; |
376 | } else { |
377 | tcp_reinit_congestion_control(sk, ca); |
378 | } |
379 | out: |
380 | rcu_read_unlock(); |
381 | return err; |
382 | } |
383 | |
384 | /* Slow start is used when congestion window is no greater than the slow start |
385 | * threshold. We base on RFC2581 and also handle stretch ACKs properly. |
386 | * We do not implement RFC3465 Appropriate Byte Counting (ABC) per se but |
387 | * something better;) a packet is only considered (s)acked in its entirety to |
388 | * defend the ACK attacks described in the RFC. Slow start processes a stretch |
389 | * ACK of degree N as if N acks of degree 1 are received back to back except |
390 | * ABC caps N to 2. Slow start exits when cwnd grows over ssthresh and |
391 | * returns the leftover acks to adjust cwnd in congestion avoidance mode. |
392 | */ |
393 | u32 tcp_slow_start(struct tcp_sock *tp, u32 acked) |
394 | { |
395 | u32 cwnd = min(tp->snd_cwnd + acked, tp->snd_ssthresh); |
396 | |
397 | acked -= cwnd - tp->snd_cwnd; |
398 | tp->snd_cwnd = min(cwnd, tp->snd_cwnd_clamp); |
399 | |
400 | return acked; |
401 | } |
402 | EXPORT_SYMBOL_GPL(tcp_slow_start); |
403 | |
404 | /* In theory this is tp->snd_cwnd += 1 / tp->snd_cwnd (or alternative w), |
405 | * for every packet that was ACKed. |
406 | */ |
407 | void tcp_cong_avoid_ai(struct tcp_sock *tp, u32 w, u32 acked) |
408 | { |
409 | /* If credits accumulated at a higher w, apply them gently now. */ |
410 | if (tp->snd_cwnd_cnt >= w) { |
411 | tp->snd_cwnd_cnt = 0; |
412 | tp->snd_cwnd++; |
413 | } |
414 | |
415 | tp->snd_cwnd_cnt += acked; |
416 | if (tp->snd_cwnd_cnt >= w) { |
417 | u32 delta = tp->snd_cwnd_cnt / w; |
418 | |
419 | tp->snd_cwnd_cnt -= delta * w; |
420 | tp->snd_cwnd += delta; |
421 | } |
422 | tp->snd_cwnd = min(tp->snd_cwnd, tp->snd_cwnd_clamp); |
423 | } |
424 | EXPORT_SYMBOL_GPL(tcp_cong_avoid_ai); |
425 | |
426 | /* |
427 | * TCP Reno congestion control |
428 | * This is special case used for fallback as well. |
429 | */ |
430 | /* This is Jacobson's slow start and congestion avoidance. |
431 | * SIGCOMM '88, p. 328. |
432 | */ |
433 | void tcp_reno_cong_avoid(struct sock *sk, u32 ack, u32 acked) |
434 | { |
435 | struct tcp_sock *tp = tcp_sk(sk); |
436 | |
437 | if (!tcp_is_cwnd_limited(sk)) |
438 | return; |
439 | |
440 | /* In "safe" area, increase. */ |
441 | if (tcp_in_slow_start(tp)) { |
442 | acked = tcp_slow_start(tp, acked); |
443 | if (!acked) |
444 | return; |
445 | } |
446 | /* In dangerous area, increase slowly. */ |
447 | tcp_cong_avoid_ai(tp, tp->snd_cwnd, acked); |
448 | } |
449 | EXPORT_SYMBOL_GPL(tcp_reno_cong_avoid); |
450 | |
451 | /* Slow start threshold is half the congestion window (min 2) */ |
452 | u32 tcp_reno_ssthresh(struct sock *sk) |
453 | { |
454 | const struct tcp_sock *tp = tcp_sk(sk); |
455 | |
456 | return max(tp->snd_cwnd >> 1U, 2U); |
457 | } |
458 | EXPORT_SYMBOL_GPL(tcp_reno_ssthresh); |
459 | |
460 | u32 tcp_reno_undo_cwnd(struct sock *sk) |
461 | { |
462 | const struct tcp_sock *tp = tcp_sk(sk); |
463 | |
464 | return max(tp->snd_cwnd, tp->prior_cwnd); |
465 | } |
466 | EXPORT_SYMBOL_GPL(tcp_reno_undo_cwnd); |
467 | |
468 | struct tcp_congestion_ops tcp_reno = { |
469 | .flags = TCP_CONG_NON_RESTRICTED, |
470 | .name = "reno" , |
471 | .owner = THIS_MODULE, |
472 | .ssthresh = tcp_reno_ssthresh, |
473 | .cong_avoid = tcp_reno_cong_avoid, |
474 | .undo_cwnd = tcp_reno_undo_cwnd, |
475 | }; |
476 | |