Commit | Line | Data |
---|---|---|
317a76f9 | 1 | /* |
b92022f3 | 2 | * Pluggable TCP congestion control support and newReno |
317a76f9 | 3 | * congestion control. |
02582e9b | 4 | * Based on ideas from I/O scheduler support and Web100. |
317a76f9 SH |
5 | * |
6 | * Copyright (C) 2005 Stephen Hemminger <shemminger@osdl.org> | |
7 | */ | |
8 | ||
afd46503 JP |
9 | #define pr_fmt(fmt) "TCP: " fmt |
10 | ||
317a76f9 SH |
11 | #include <linux/module.h> |
12 | #include <linux/mm.h> | |
13 | #include <linux/types.h> | |
14 | #include <linux/list.h> | |
5a0e3ad6 | 15 | #include <linux/gfp.h> |
317a76f9 SH |
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 | ||
5f8ef48d | 26 | list_for_each_entry_rcu(e, &tcp_cong_list, list) { |
317a76f9 SH |
27 | if (strcmp(e->name, name) == 0) |
28 | return e; | |
29 | } | |
30 | ||
31 | return NULL; | |
32 | } | |
33 | ||
34 | /* | |
d08df601 | 35 | * Attach new congestion control algorithm to the list |
317a76f9 SH |
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 */ | |
72dc5b92 | 43 | if (!ca->ssthresh || !ca->cong_avoid) { |
afd46503 | 44 | pr_err("%s does not implement required ops\n", ca->name); |
317a76f9 SH |
45 | return -EINVAL; |
46 | } | |
47 | ||
48 | spin_lock(&tcp_cong_list_lock); | |
49 | if (tcp_ca_find(ca->name)) { | |
afd46503 | 50 | pr_notice("%s already registered\n", ca->name); |
317a76f9 SH |
51 | ret = -EEXIST; |
52 | } else { | |
3d2573f7 | 53 | list_add_tail_rcu(&ca->list, &tcp_cong_list); |
afd46503 | 54 | pr_info("%s registered\n", ca->name); |
317a76f9 SH |
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. */ | |
55d8694f | 77 | void tcp_assign_congestion_control(struct sock *sk) |
317a76f9 | 78 | { |
6687e988 | 79 | struct inet_connection_sock *icsk = inet_csk(sk); |
317a76f9 SH |
80 | struct tcp_congestion_ops *ca; |
81 | ||
55d8694f FW |
82 | rcu_read_lock(); |
83 | list_for_each_entry_rcu(ca, &tcp_cong_list, list) { | |
84 | if (likely(try_module_get(ca->owner))) { | |
85 | icsk->icsk_ca_ops = ca; | |
86 | goto out; | |
317a76f9 | 87 | } |
55d8694f FW |
88 | /* Fallback to next available. The last really |
89 | * guaranteed fallback is Reno from this list. | |
90 | */ | |
317a76f9 | 91 | } |
55d8694f FW |
92 | out: |
93 | rcu_read_unlock(); | |
94 | ||
95 | /* Clear out private data before diag gets it and | |
96 | * the ca has not been initialized. | |
97 | */ | |
98 | if (ca->get_info) | |
99 | memset(icsk->icsk_ca_priv, 0, sizeof(icsk->icsk_ca_priv)); | |
100 | } | |
101 | ||
102 | void tcp_init_congestion_control(struct sock *sk) | |
103 | { | |
104 | const struct inet_connection_sock *icsk = inet_csk(sk); | |
317a76f9 | 105 | |
6687e988 ACM |
106 | if (icsk->icsk_ca_ops->init) |
107 | icsk->icsk_ca_ops->init(sk); | |
317a76f9 SH |
108 | } |
109 | ||
29ba4fff DB |
110 | static void tcp_reinit_congestion_control(struct sock *sk, |
111 | const struct tcp_congestion_ops *ca) | |
112 | { | |
113 | struct inet_connection_sock *icsk = inet_csk(sk); | |
114 | ||
115 | tcp_cleanup_congestion_control(sk); | |
116 | icsk->icsk_ca_ops = ca; | |
117 | ||
118 | if (sk->sk_state != TCP_CLOSE && icsk->icsk_ca_ops->init) | |
119 | icsk->icsk_ca_ops->init(sk); | |
120 | } | |
121 | ||
317a76f9 | 122 | /* Manage refcounts on socket close. */ |
6687e988 | 123 | void tcp_cleanup_congestion_control(struct sock *sk) |
317a76f9 | 124 | { |
6687e988 ACM |
125 | struct inet_connection_sock *icsk = inet_csk(sk); |
126 | ||
127 | if (icsk->icsk_ca_ops->release) | |
128 | icsk->icsk_ca_ops->release(sk); | |
129 | module_put(icsk->icsk_ca_ops->owner); | |
317a76f9 SH |
130 | } |
131 | ||
132 | /* Used by sysctl to change default congestion control */ | |
133 | int tcp_set_default_congestion_control(const char *name) | |
134 | { | |
135 | struct tcp_congestion_ops *ca; | |
136 | int ret = -ENOENT; | |
137 | ||
138 | spin_lock(&tcp_cong_list_lock); | |
139 | ca = tcp_ca_find(name); | |
95a5afca | 140 | #ifdef CONFIG_MODULES |
a8f80e8f | 141 | if (!ca && capable(CAP_NET_ADMIN)) { |
317a76f9 SH |
142 | spin_unlock(&tcp_cong_list_lock); |
143 | ||
144 | request_module("tcp_%s", name); | |
145 | spin_lock(&tcp_cong_list_lock); | |
146 | ca = tcp_ca_find(name); | |
147 | } | |
148 | #endif | |
149 | ||
150 | if (ca) { | |
164891aa | 151 | ca->flags |= TCP_CONG_NON_RESTRICTED; /* default is always allowed */ |
317a76f9 SH |
152 | list_move(&ca->list, &tcp_cong_list); |
153 | ret = 0; | |
154 | } | |
155 | spin_unlock(&tcp_cong_list_lock); | |
156 | ||
157 | return ret; | |
158 | } | |
159 | ||
b1736a71 SH |
160 | /* Set default value from kernel configuration at bootup */ |
161 | static int __init tcp_congestion_default(void) | |
162 | { | |
163 | return tcp_set_default_congestion_control(CONFIG_DEFAULT_TCP_CONG); | |
164 | } | |
165 | late_initcall(tcp_congestion_default); | |
166 | ||
3ff825b2 SH |
167 | /* Build string with list of available congestion control values */ |
168 | void tcp_get_available_congestion_control(char *buf, size_t maxlen) | |
169 | { | |
170 | struct tcp_congestion_ops *ca; | |
171 | size_t offs = 0; | |
172 | ||
173 | rcu_read_lock(); | |
174 | list_for_each_entry_rcu(ca, &tcp_cong_list, list) { | |
175 | offs += snprintf(buf + offs, maxlen - offs, | |
176 | "%s%s", | |
177 | offs == 0 ? "" : " ", ca->name); | |
3ff825b2 SH |
178 | } |
179 | rcu_read_unlock(); | |
180 | } | |
181 | ||
317a76f9 SH |
182 | /* Get current default congestion control */ |
183 | void tcp_get_default_congestion_control(char *name) | |
184 | { | |
185 | struct tcp_congestion_ops *ca; | |
186 | /* We will always have reno... */ | |
187 | BUG_ON(list_empty(&tcp_cong_list)); | |
188 | ||
189 | rcu_read_lock(); | |
190 | ca = list_entry(tcp_cong_list.next, struct tcp_congestion_ops, list); | |
191 | strncpy(name, ca->name, TCP_CA_NAME_MAX); | |
192 | rcu_read_unlock(); | |
193 | } | |
194 | ||
ce7bc3bf SH |
195 | /* Built list of non-restricted congestion control values */ |
196 | void tcp_get_allowed_congestion_control(char *buf, size_t maxlen) | |
197 | { | |
198 | struct tcp_congestion_ops *ca; | |
199 | size_t offs = 0; | |
200 | ||
201 | *buf = '\0'; | |
202 | rcu_read_lock(); | |
203 | list_for_each_entry_rcu(ca, &tcp_cong_list, list) { | |
164891aa | 204 | if (!(ca->flags & TCP_CONG_NON_RESTRICTED)) |
ce7bc3bf SH |
205 | continue; |
206 | offs += snprintf(buf + offs, maxlen - offs, | |
207 | "%s%s", | |
208 | offs == 0 ? "" : " ", ca->name); | |
ce7bc3bf SH |
209 | } |
210 | rcu_read_unlock(); | |
211 | } | |
212 | ||
213 | /* Change list of non-restricted congestion control */ | |
214 | int tcp_set_allowed_congestion_control(char *val) | |
215 | { | |
216 | struct tcp_congestion_ops *ca; | |
c34186ed | 217 | char *saved_clone, *clone, *name; |
ce7bc3bf SH |
218 | int ret = 0; |
219 | ||
c34186ed | 220 | saved_clone = clone = kstrdup(val, GFP_USER); |
ce7bc3bf SH |
221 | if (!clone) |
222 | return -ENOMEM; | |
223 | ||
224 | spin_lock(&tcp_cong_list_lock); | |
225 | /* pass 1 check for bad entries */ | |
226 | while ((name = strsep(&clone, " ")) && *name) { | |
227 | ca = tcp_ca_find(name); | |
228 | if (!ca) { | |
229 | ret = -ENOENT; | |
230 | goto out; | |
231 | } | |
232 | } | |
233 | ||
164891aa | 234 | /* pass 2 clear old values */ |
ce7bc3bf | 235 | list_for_each_entry_rcu(ca, &tcp_cong_list, list) |
164891aa | 236 | ca->flags &= ~TCP_CONG_NON_RESTRICTED; |
ce7bc3bf SH |
237 | |
238 | /* pass 3 mark as allowed */ | |
239 | while ((name = strsep(&val, " ")) && *name) { | |
240 | ca = tcp_ca_find(name); | |
241 | WARN_ON(!ca); | |
242 | if (ca) | |
164891aa | 243 | ca->flags |= TCP_CONG_NON_RESTRICTED; |
ce7bc3bf SH |
244 | } |
245 | out: | |
246 | spin_unlock(&tcp_cong_list_lock); | |
c34186ed | 247 | kfree(saved_clone); |
ce7bc3bf SH |
248 | |
249 | return ret; | |
250 | } | |
251 | ||
5f8ef48d | 252 | /* Change congestion control for socket */ |
6687e988 | 253 | int tcp_set_congestion_control(struct sock *sk, const char *name) |
5f8ef48d | 254 | { |
6687e988 | 255 | struct inet_connection_sock *icsk = inet_csk(sk); |
5f8ef48d SH |
256 | struct tcp_congestion_ops *ca; |
257 | int err = 0; | |
258 | ||
259 | rcu_read_lock(); | |
260 | ca = tcp_ca_find(name); | |
4d4d3d1e | 261 | |
35bfbc94 | 262 | /* no change asking for existing value */ |
6687e988 | 263 | if (ca == icsk->icsk_ca_ops) |
5f8ef48d SH |
264 | goto out; |
265 | ||
95a5afca | 266 | #ifdef CONFIG_MODULES |
35bfbc94 | 267 | /* not found attempt to autoload module */ |
a8f80e8f | 268 | if (!ca && capable(CAP_NET_ADMIN)) { |
35bfbc94 SH |
269 | rcu_read_unlock(); |
270 | request_module("tcp_%s", name); | |
271 | rcu_read_lock(); | |
272 | ca = tcp_ca_find(name); | |
273 | } | |
274 | #endif | |
5f8ef48d SH |
275 | if (!ca) |
276 | err = -ENOENT; | |
52e804c6 EB |
277 | else if (!((ca->flags & TCP_CONG_NON_RESTRICTED) || |
278 | ns_capable(sock_net(sk)->user_ns, CAP_NET_ADMIN))) | |
ce7bc3bf | 279 | err = -EPERM; |
5f8ef48d SH |
280 | else if (!try_module_get(ca->owner)) |
281 | err = -EBUSY; | |
29ba4fff DB |
282 | else |
283 | tcp_reinit_congestion_control(sk, ca); | |
5f8ef48d SH |
284 | out: |
285 | rcu_read_unlock(); | |
286 | return err; | |
287 | } | |
288 | ||
9f9843a7 YC |
289 | /* Slow start is used when congestion window is no greater than the slow start |
290 | * threshold. We base on RFC2581 and also handle stretch ACKs properly. | |
291 | * We do not implement RFC3465 Appropriate Byte Counting (ABC) per se but | |
292 | * something better;) a packet is only considered (s)acked in its entirety to | |
293 | * defend the ACK attacks described in the RFC. Slow start processes a stretch | |
294 | * ACK of degree N as if N acks of degree 1 are received back to back except | |
295 | * ABC caps N to 2. Slow start exits when cwnd grows over ssthresh and | |
296 | * returns the leftover acks to adjust cwnd in congestion avoidance mode. | |
40efc6fa | 297 | */ |
a12a601e | 298 | void tcp_slow_start(struct tcp_sock *tp, u32 acked) |
40efc6fa | 299 | { |
9f9843a7 | 300 | u32 cwnd = tp->snd_cwnd + acked; |
a02ba041 | 301 | |
9f9843a7 YC |
302 | if (cwnd > tp->snd_ssthresh) |
303 | cwnd = tp->snd_ssthresh + 1; | |
9f9843a7 | 304 | tp->snd_cwnd = min(cwnd, tp->snd_cwnd_clamp); |
40efc6fa SH |
305 | } |
306 | EXPORT_SYMBOL_GPL(tcp_slow_start); | |
307 | ||
758ce5c8 IJ |
308 | /* In theory this is tp->snd_cwnd += 1 / tp->snd_cwnd (or alternative w) */ |
309 | void tcp_cong_avoid_ai(struct tcp_sock *tp, u32 w) | |
310 | { | |
311 | if (tp->snd_cwnd_cnt >= w) { | |
312 | if (tp->snd_cwnd < tp->snd_cwnd_clamp) | |
313 | tp->snd_cwnd++; | |
314 | tp->snd_cwnd_cnt = 0; | |
315 | } else { | |
316 | tp->snd_cwnd_cnt++; | |
317 | } | |
318 | } | |
319 | EXPORT_SYMBOL_GPL(tcp_cong_avoid_ai); | |
320 | ||
317a76f9 SH |
321 | /* |
322 | * TCP Reno congestion control | |
323 | * This is special case used for fallback as well. | |
324 | */ | |
325 | /* This is Jacobson's slow start and congestion avoidance. | |
326 | * SIGCOMM '88, p. 328. | |
327 | */ | |
24901551 | 328 | void tcp_reno_cong_avoid(struct sock *sk, u32 ack, u32 acked) |
317a76f9 | 329 | { |
6687e988 ACM |
330 | struct tcp_sock *tp = tcp_sk(sk); |
331 | ||
24901551 | 332 | if (!tcp_is_cwnd_limited(sk)) |
317a76f9 SH |
333 | return; |
334 | ||
7faffa1c | 335 | /* In "safe" area, increase. */ |
e905a9ed | 336 | if (tp->snd_cwnd <= tp->snd_ssthresh) |
9f9843a7 | 337 | tcp_slow_start(tp, acked); |
e905a9ed | 338 | /* In dangerous area, increase slowly. */ |
ca2eb567 | 339 | else |
758ce5c8 | 340 | tcp_cong_avoid_ai(tp, tp->snd_cwnd); |
317a76f9 SH |
341 | } |
342 | EXPORT_SYMBOL_GPL(tcp_reno_cong_avoid); | |
343 | ||
344 | /* Slow start threshold is half the congestion window (min 2) */ | |
6687e988 | 345 | u32 tcp_reno_ssthresh(struct sock *sk) |
317a76f9 | 346 | { |
6687e988 | 347 | const struct tcp_sock *tp = tcp_sk(sk); |
688d1945 | 348 | |
317a76f9 SH |
349 | return max(tp->snd_cwnd >> 1U, 2U); |
350 | } | |
351 | EXPORT_SYMBOL_GPL(tcp_reno_ssthresh); | |
352 | ||
317a76f9 | 353 | struct tcp_congestion_ops tcp_reno = { |
164891aa | 354 | .flags = TCP_CONG_NON_RESTRICTED, |
317a76f9 SH |
355 | .name = "reno", |
356 | .owner = THIS_MODULE, | |
357 | .ssthresh = tcp_reno_ssthresh, | |
358 | .cong_avoid = tcp_reno_cong_avoid, | |
317a76f9 | 359 | }; |