Commit | Line | Data |
---|---|---|
317a76f9 SH |
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 | ||
317a76f9 SH |
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 | ||
5f8ef48d | 23 | list_for_each_entry_rcu(e, &tcp_cong_list, list) { |
317a76f9 SH |
24 | if (strcmp(e->name, name) == 0) |
25 | return e; | |
26 | } | |
27 | ||
28 | return NULL; | |
29 | } | |
30 | ||
31 | /* | |
d08df601 | 32 | * Attach new congestion control algorithm to the list |
317a76f9 SH |
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 */ | |
72dc5b92 | 40 | if (!ca->ssthresh || !ca->cong_avoid) { |
317a76f9 SH |
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 { | |
3d2573f7 | 51 | list_add_tail_rcu(&ca->list, &tcp_cong_list); |
317a76f9 SH |
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. */ | |
6687e988 | 75 | void tcp_init_congestion_control(struct sock *sk) |
317a76f9 | 76 | { |
6687e988 | 77 | struct inet_connection_sock *icsk = inet_csk(sk); |
317a76f9 SH |
78 | struct tcp_congestion_ops *ca; |
79 | ||
4d4d3d1e SH |
80 | /* if no choice made yet assign the current value set as default */ |
81 | if (icsk->icsk_ca_ops == &tcp_init_congestion_ops) { | |
82 | rcu_read_lock(); | |
83 | list_for_each_entry_rcu(ca, &tcp_cong_list, list) { | |
84 | if (try_module_get(ca->owner)) { | |
85 | icsk->icsk_ca_ops = ca; | |
86 | break; | |
87 | } | |
5f8ef48d | 88 | |
4d4d3d1e | 89 | /* fallback to next available */ |
317a76f9 | 90 | } |
4d4d3d1e | 91 | rcu_read_unlock(); |
317a76f9 | 92 | } |
317a76f9 | 93 | |
6687e988 ACM |
94 | if (icsk->icsk_ca_ops->init) |
95 | icsk->icsk_ca_ops->init(sk); | |
317a76f9 SH |
96 | } |
97 | ||
98 | /* Manage refcounts on socket close. */ | |
6687e988 | 99 | void tcp_cleanup_congestion_control(struct sock *sk) |
317a76f9 | 100 | { |
6687e988 ACM |
101 | struct inet_connection_sock *icsk = inet_csk(sk); |
102 | ||
103 | if (icsk->icsk_ca_ops->release) | |
104 | icsk->icsk_ca_ops->release(sk); | |
105 | module_put(icsk->icsk_ca_ops->owner); | |
317a76f9 SH |
106 | } |
107 | ||
108 | /* Used by sysctl to change default congestion control */ | |
109 | int tcp_set_default_congestion_control(const char *name) | |
110 | { | |
111 | struct tcp_congestion_ops *ca; | |
112 | int ret = -ENOENT; | |
113 | ||
114 | spin_lock(&tcp_cong_list_lock); | |
115 | ca = tcp_ca_find(name); | |
116 | #ifdef CONFIG_KMOD | |
35bfbc94 | 117 | if (!ca && capable(CAP_SYS_MODULE)) { |
317a76f9 SH |
118 | spin_unlock(&tcp_cong_list_lock); |
119 | ||
120 | request_module("tcp_%s", name); | |
121 | spin_lock(&tcp_cong_list_lock); | |
122 | ca = tcp_ca_find(name); | |
123 | } | |
124 | #endif | |
125 | ||
126 | if (ca) { | |
ce7bc3bf | 127 | ca->non_restricted = 1; /* default is always allowed */ |
317a76f9 SH |
128 | list_move(&ca->list, &tcp_cong_list); |
129 | ret = 0; | |
130 | } | |
131 | spin_unlock(&tcp_cong_list_lock); | |
132 | ||
133 | return ret; | |
134 | } | |
135 | ||
b1736a71 SH |
136 | /* Set default value from kernel configuration at bootup */ |
137 | static int __init tcp_congestion_default(void) | |
138 | { | |
139 | return tcp_set_default_congestion_control(CONFIG_DEFAULT_TCP_CONG); | |
140 | } | |
141 | late_initcall(tcp_congestion_default); | |
142 | ||
143 | ||
3ff825b2 SH |
144 | /* Build string with list of available congestion control values */ |
145 | void tcp_get_available_congestion_control(char *buf, size_t maxlen) | |
146 | { | |
147 | struct tcp_congestion_ops *ca; | |
148 | size_t offs = 0; | |
149 | ||
150 | rcu_read_lock(); | |
151 | list_for_each_entry_rcu(ca, &tcp_cong_list, list) { | |
152 | offs += snprintf(buf + offs, maxlen - offs, | |
153 | "%s%s", | |
154 | offs == 0 ? "" : " ", ca->name); | |
155 | ||
156 | } | |
157 | rcu_read_unlock(); | |
158 | } | |
159 | ||
317a76f9 SH |
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 | ||
ce7bc3bf SH |
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->non_restricted) | |
183 | continue; | |
184 | offs += snprintf(buf + offs, maxlen - offs, | |
185 | "%s%s", | |
186 | offs == 0 ? "" : " ", ca->name); | |
187 | ||
188 | } | |
189 | rcu_read_unlock(); | |
190 | } | |
191 | ||
192 | /* Change list of non-restricted congestion control */ | |
193 | int tcp_set_allowed_congestion_control(char *val) | |
194 | { | |
195 | struct tcp_congestion_ops *ca; | |
196 | char *clone, *name; | |
197 | int ret = 0; | |
198 | ||
199 | clone = kstrdup(val, GFP_USER); | |
200 | if (!clone) | |
201 | return -ENOMEM; | |
202 | ||
203 | spin_lock(&tcp_cong_list_lock); | |
204 | /* pass 1 check for bad entries */ | |
205 | while ((name = strsep(&clone, " ")) && *name) { | |
206 | ca = tcp_ca_find(name); | |
207 | if (!ca) { | |
208 | ret = -ENOENT; | |
209 | goto out; | |
210 | } | |
211 | } | |
212 | ||
213 | /* pass 2 clear */ | |
214 | list_for_each_entry_rcu(ca, &tcp_cong_list, list) | |
215 | ca->non_restricted = 0; | |
216 | ||
217 | /* pass 3 mark as allowed */ | |
218 | while ((name = strsep(&val, " ")) && *name) { | |
219 | ca = tcp_ca_find(name); | |
220 | WARN_ON(!ca); | |
221 | if (ca) | |
222 | ca->non_restricted = 1; | |
223 | } | |
224 | out: | |
225 | spin_unlock(&tcp_cong_list_lock); | |
226 | ||
227 | return ret; | |
228 | } | |
229 | ||
230 | ||
5f8ef48d | 231 | /* Change congestion control for socket */ |
6687e988 | 232 | int tcp_set_congestion_control(struct sock *sk, const char *name) |
5f8ef48d | 233 | { |
6687e988 | 234 | struct inet_connection_sock *icsk = inet_csk(sk); |
5f8ef48d SH |
235 | struct tcp_congestion_ops *ca; |
236 | int err = 0; | |
237 | ||
238 | rcu_read_lock(); | |
239 | ca = tcp_ca_find(name); | |
4d4d3d1e | 240 | |
35bfbc94 | 241 | /* no change asking for existing value */ |
6687e988 | 242 | if (ca == icsk->icsk_ca_ops) |
5f8ef48d SH |
243 | goto out; |
244 | ||
35bfbc94 SH |
245 | #ifdef CONFIG_KMOD |
246 | /* not found attempt to autoload module */ | |
247 | if (!ca && capable(CAP_SYS_MODULE)) { | |
248 | rcu_read_unlock(); | |
249 | request_module("tcp_%s", name); | |
250 | rcu_read_lock(); | |
251 | ca = tcp_ca_find(name); | |
252 | } | |
253 | #endif | |
5f8ef48d SH |
254 | if (!ca) |
255 | err = -ENOENT; | |
256 | ||
ce7bc3bf SH |
257 | else if (!(ca->non_restricted || capable(CAP_NET_ADMIN))) |
258 | err = -EPERM; | |
259 | ||
5f8ef48d SH |
260 | else if (!try_module_get(ca->owner)) |
261 | err = -EBUSY; | |
262 | ||
263 | else { | |
6687e988 ACM |
264 | tcp_cleanup_congestion_control(sk); |
265 | icsk->icsk_ca_ops = ca; | |
4d4d3d1e SH |
266 | |
267 | if (sk->sk_state != TCP_CLOSE && icsk->icsk_ca_ops->init) | |
6687e988 | 268 | icsk->icsk_ca_ops->init(sk); |
5f8ef48d SH |
269 | } |
270 | out: | |
271 | rcu_read_unlock(); | |
272 | return err; | |
273 | } | |
274 | ||
40efc6fa SH |
275 | |
276 | /* | |
277 | * Linear increase during slow start | |
278 | */ | |
279 | void tcp_slow_start(struct tcp_sock *tp) | |
280 | { | |
281 | if (sysctl_tcp_abc) { | |
282 | /* RFC3465: Slow Start | |
283 | * TCP sender SHOULD increase cwnd by the number of | |
284 | * previously unacknowledged bytes ACKed by each incoming | |
285 | * acknowledgment, provided the increase is not more than L | |
286 | */ | |
287 | if (tp->bytes_acked < tp->mss_cache) | |
288 | return; | |
289 | ||
290 | /* We MAY increase by 2 if discovered delayed ack */ | |
3fdf3f0c | 291 | if (sysctl_tcp_abc > 1 && tp->bytes_acked >= 2*tp->mss_cache) { |
40efc6fa SH |
292 | if (tp->snd_cwnd < tp->snd_cwnd_clamp) |
293 | tp->snd_cwnd++; | |
294 | } | |
295 | } | |
296 | tp->bytes_acked = 0; | |
297 | ||
298 | if (tp->snd_cwnd < tp->snd_cwnd_clamp) | |
299 | tp->snd_cwnd++; | |
300 | } | |
301 | EXPORT_SYMBOL_GPL(tcp_slow_start); | |
302 | ||
317a76f9 SH |
303 | /* |
304 | * TCP Reno congestion control | |
305 | * This is special case used for fallback as well. | |
306 | */ | |
307 | /* This is Jacobson's slow start and congestion avoidance. | |
308 | * SIGCOMM '88, p. 328. | |
309 | */ | |
6687e988 | 310 | void tcp_reno_cong_avoid(struct sock *sk, u32 ack, u32 rtt, u32 in_flight, |
317a76f9 SH |
311 | int flag) |
312 | { | |
6687e988 ACM |
313 | struct tcp_sock *tp = tcp_sk(sk); |
314 | ||
f4805ede | 315 | if (!tcp_is_cwnd_limited(sk, in_flight)) |
317a76f9 SH |
316 | return; |
317 | ||
7faffa1c | 318 | /* In "safe" area, increase. */ |
e905a9ed | 319 | if (tp->snd_cwnd <= tp->snd_ssthresh) |
7faffa1c | 320 | tcp_slow_start(tp); |
9772efb9 | 321 | |
e905a9ed | 322 | /* In dangerous area, increase slowly. */ |
9772efb9 | 323 | else if (sysctl_tcp_abc) { |
e905a9ed YH |
324 | /* RFC3465: Appropriate Byte Count |
325 | * increase once for each full cwnd acked | |
326 | */ | |
327 | if (tp->bytes_acked >= tp->snd_cwnd*tp->mss_cache) { | |
328 | tp->bytes_acked -= tp->snd_cwnd*tp->mss_cache; | |
329 | if (tp->snd_cwnd < tp->snd_cwnd_clamp) | |
330 | tp->snd_cwnd++; | |
331 | } | |
332 | } else { | |
333 | /* In theory this is tp->snd_cwnd += 1 / tp->snd_cwnd */ | |
334 | if (tp->snd_cwnd_cnt >= tp->snd_cwnd) { | |
335 | if (tp->snd_cwnd < tp->snd_cwnd_clamp) | |
336 | tp->snd_cwnd++; | |
337 | tp->snd_cwnd_cnt = 0; | |
338 | } else | |
339 | tp->snd_cwnd_cnt++; | |
340 | } | |
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); |
317a76f9 SH |
348 | return max(tp->snd_cwnd >> 1U, 2U); |
349 | } | |
350 | EXPORT_SYMBOL_GPL(tcp_reno_ssthresh); | |
351 | ||
72dc5b92 SH |
352 | /* Lower bound on congestion window with halving. */ |
353 | u32 tcp_reno_min_cwnd(const struct sock *sk) | |
317a76f9 | 354 | { |
6687e988 | 355 | const struct tcp_sock *tp = tcp_sk(sk); |
317a76f9 SH |
356 | return tp->snd_ssthresh/2; |
357 | } | |
358 | EXPORT_SYMBOL_GPL(tcp_reno_min_cwnd); | |
359 | ||
360 | struct tcp_congestion_ops tcp_reno = { | |
361 | .name = "reno", | |
ce7bc3bf | 362 | .non_restricted = 1, |
317a76f9 SH |
363 | .owner = THIS_MODULE, |
364 | .ssthresh = tcp_reno_ssthresh, | |
365 | .cong_avoid = tcp_reno_cong_avoid, | |
366 | .min_cwnd = tcp_reno_min_cwnd, | |
367 | }; | |
368 | ||
5f8ef48d SH |
369 | /* Initial congestion control used (until SYN) |
370 | * really reno under another name so we can tell difference | |
371 | * during tcp_set_default_congestion_control | |
372 | */ | |
373 | struct tcp_congestion_ops tcp_init_congestion_ops = { | |
374 | .name = "", | |
375 | .owner = THIS_MODULE, | |
376 | .ssthresh = tcp_reno_ssthresh, | |
377 | .cong_avoid = tcp_reno_cong_avoid, | |
378 | .min_cwnd = tcp_reno_min_cwnd, | |
379 | }; | |
380 | EXPORT_SYMBOL_GPL(tcp_init_congestion_ops); |