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 | /* | |
32 | * Attach new congestion control algorthim 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 */ | |
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 | ||
6687e988 | 80 | if (icsk->icsk_ca_ops != &tcp_init_congestion_ops) |
5f8ef48d SH |
81 | return; |
82 | ||
317a76f9 SH |
83 | rcu_read_lock(); |
84 | list_for_each_entry_rcu(ca, &tcp_cong_list, list) { | |
85 | if (try_module_get(ca->owner)) { | |
6687e988 | 86 | icsk->icsk_ca_ops = ca; |
317a76f9 SH |
87 | break; |
88 | } | |
89 | ||
90 | } | |
91 | rcu_read_unlock(); | |
92 | ||
6687e988 ACM |
93 | if (icsk->icsk_ca_ops->init) |
94 | icsk->icsk_ca_ops->init(sk); | |
317a76f9 SH |
95 | } |
96 | ||
97 | /* Manage refcounts on socket close. */ | |
6687e988 | 98 | void tcp_cleanup_congestion_control(struct sock *sk) |
317a76f9 | 99 | { |
6687e988 ACM |
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); | |
317a76f9 SH |
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 | |
35bfbc94 | 116 | if (!ca && capable(CAP_SYS_MODULE)) { |
317a76f9 SH |
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) { | |
ce7bc3bf | 126 | ca->non_restricted = 1; /* default is always allowed */ |
317a76f9 SH |
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 | ||
b1736a71 SH |
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 | ||
3ff825b2 SH |
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 | ||
317a76f9 SH |
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 | ||
ce7bc3bf SH |
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 | ||
5f8ef48d | 230 | /* Change congestion control for socket */ |
6687e988 | 231 | int tcp_set_congestion_control(struct sock *sk, const char *name) |
5f8ef48d | 232 | { |
6687e988 | 233 | struct inet_connection_sock *icsk = inet_csk(sk); |
5f8ef48d SH |
234 | struct tcp_congestion_ops *ca; |
235 | int err = 0; | |
236 | ||
237 | rcu_read_lock(); | |
238 | ca = tcp_ca_find(name); | |
35bfbc94 | 239 | /* no change asking for existing value */ |
6687e988 | 240 | if (ca == icsk->icsk_ca_ops) |
5f8ef48d SH |
241 | goto out; |
242 | ||
35bfbc94 SH |
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 | |
5f8ef48d SH |
252 | if (!ca) |
253 | err = -ENOENT; | |
254 | ||
ce7bc3bf SH |
255 | else if (!(ca->non_restricted || capable(CAP_NET_ADMIN))) |
256 | err = -EPERM; | |
257 | ||
5f8ef48d SH |
258 | else if (!try_module_get(ca->owner)) |
259 | err = -EBUSY; | |
260 | ||
261 | else { | |
6687e988 ACM |
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); | |
5f8ef48d SH |
266 | } |
267 | out: | |
268 | rcu_read_unlock(); | |
269 | return err; | |
270 | } | |
271 | ||
40efc6fa SH |
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 */ | |
3fdf3f0c | 288 | if (sysctl_tcp_abc > 1 && tp->bytes_acked >= 2*tp->mss_cache) { |
40efc6fa SH |
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 | ||
317a76f9 SH |
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 | */ | |
6687e988 | 307 | void tcp_reno_cong_avoid(struct sock *sk, u32 ack, u32 rtt, u32 in_flight, |
317a76f9 SH |
308 | int flag) |
309 | { | |
6687e988 ACM |
310 | struct tcp_sock *tp = tcp_sk(sk); |
311 | ||
f4805ede | 312 | if (!tcp_is_cwnd_limited(sk, in_flight)) |
317a76f9 SH |
313 | return; |
314 | ||
7faffa1c | 315 | /* In "safe" area, increase. */ |
e905a9ed | 316 | if (tp->snd_cwnd <= tp->snd_ssthresh) |
7faffa1c | 317 | tcp_slow_start(tp); |
9772efb9 | 318 | |
e905a9ed | 319 | /* In dangerous area, increase slowly. */ |
9772efb9 | 320 | else if (sysctl_tcp_abc) { |
e905a9ed YH |
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 | } | |
317a76f9 SH |
338 | } |
339 | EXPORT_SYMBOL_GPL(tcp_reno_cong_avoid); | |
340 | ||
341 | /* Slow start threshold is half the congestion window (min 2) */ | |
6687e988 | 342 | u32 tcp_reno_ssthresh(struct sock *sk) |
317a76f9 | 343 | { |
6687e988 | 344 | const struct tcp_sock *tp = tcp_sk(sk); |
317a76f9 SH |
345 | return max(tp->snd_cwnd >> 1U, 2U); |
346 | } | |
347 | EXPORT_SYMBOL_GPL(tcp_reno_ssthresh); | |
348 | ||
72dc5b92 SH |
349 | /* Lower bound on congestion window with halving. */ |
350 | u32 tcp_reno_min_cwnd(const struct sock *sk) | |
317a76f9 | 351 | { |
6687e988 | 352 | const struct tcp_sock *tp = tcp_sk(sk); |
317a76f9 SH |
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", | |
ce7bc3bf | 359 | .non_restricted = 1, |
317a76f9 SH |
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 | ||
5f8ef48d SH |
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); |