Branch data Line data Source code
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 : 0 : static struct tcp_congestion_ops *tcp_ca_find(const char *name)
23 : : {
24 : : struct tcp_congestion_ops *e;
25 : :
26 [ # # ]: 0 : list_for_each_entry_rcu(e, &tcp_cong_list, list) {
27 [ # # ]: 0 : 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 : 0 : 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 [ # # ][ # # ]: 0 : if (!ca->ssthresh || !ca->cong_avoid) {
44 : 0 : pr_err("%s does not implement required ops\n", ca->name);
45 : 0 : return -EINVAL;
46 : : }
47 : :
48 : : spin_lock(&tcp_cong_list_lock);
49 [ # # ]: 0 : if (tcp_ca_find(ca->name)) {
50 : 0 : pr_notice("%s already registered\n", ca->name);
51 : : ret = -EEXIST;
52 : : } else {
53 : 0 : list_add_tail_rcu(&ca->list, &tcp_cong_list);
54 : 0 : pr_info("%s registered\n", ca->name);
55 : : }
56 : : spin_unlock(&tcp_cong_list_lock);
57 : :
58 : 0 : 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 : 0 : 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 : 0 : }
74 : : EXPORT_SYMBOL_GPL(tcp_unregister_congestion_control);
75 : :
76 : : /* Assign choice of congestion control. */
77 : 0 : 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 [ + - ]: 57 : if (icsk->icsk_ca_ops == &tcp_init_congestion_ops) {
84 : : rcu_read_lock();
85 [ + - ]: 57 : list_for_each_entry_rcu(ca, &tcp_cong_list, list) {
86 [ + - ]: 57 : if (try_module_get(ca->owner)) {
87 : 57 : icsk->icsk_ca_ops = ca;
88 : 57 : break;
89 : : }
90 : :
91 : : /* fallback to next available */
92 : : }
93 : : rcu_read_unlock();
94 : : }
95 : :
96 [ + - ]: 57 : if (icsk->icsk_ca_ops->init)
97 : 57 : icsk->icsk_ca_ops->init(sk);
98 : 57 : }
99 : :
100 : : /* Manage refcounts on socket close. */
101 : 0 : void tcp_cleanup_congestion_control(struct sock *sk)
102 : : {
103 : : struct inet_connection_sock *icsk = inet_csk(sk);
104 : :
105 [ - + ]: 109 : if (icsk->icsk_ca_ops->release)
106 : 0 : icsk->icsk_ca_ops->release(sk);
107 : 109 : module_put(icsk->icsk_ca_ops->owner);
108 : 109 : }
109 : :
110 : : /* Used by sysctl to change default congestion control */
111 : 0 : 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 : 0 : ca = tcp_ca_find(name);
118 : : #ifdef CONFIG_MODULES
119 [ # # ][ # # ]: 0 : if (!ca && capable(CAP_NET_ADMIN)) {
120 : : spin_unlock(&tcp_cong_list_lock);
121 : :
122 : 0 : request_module("tcp_%s", name);
123 : : spin_lock(&tcp_cong_list_lock);
124 : 0 : ca = tcp_ca_find(name);
125 : : }
126 : : #endif
127 : :
128 [ # # ]: 0 : if (ca) {
129 : 0 : ca->flags |= TCP_CONG_NON_RESTRICTED; /* default is always allowed */
130 : 0 : list_move(&ca->list, &tcp_cong_list);
131 : : ret = 0;
132 : : }
133 : : spin_unlock(&tcp_cong_list_lock);
134 : :
135 : 0 : return ret;
136 : : }
137 : :
138 : : /* Set default value from kernel configuration at bootup */
139 : 0 : static int __init tcp_congestion_default(void)
140 : : {
141 : 0 : return tcp_set_default_congestion_control(CONFIG_DEFAULT_TCP_CONG);
142 : : }
143 : : late_initcall(tcp_congestion_default);
144 : :
145 : :
146 : : /* Build string with list of available congestion control values */
147 : 0 : void tcp_get_available_congestion_control(char *buf, size_t maxlen)
148 : : {
149 : : struct tcp_congestion_ops *ca;
150 : : size_t offs = 0;
151 : :
152 : : rcu_read_lock();
153 [ + + ]: 8 : list_for_each_entry_rcu(ca, &tcp_cong_list, list) {
154 [ + + ]: 4 : offs += snprintf(buf + offs, maxlen - offs,
155 : : "%s%s",
156 : 4 : offs == 0 ? "" : " ", ca->name);
157 : :
158 : : }
159 : : rcu_read_unlock();
160 : 2 : }
161 : :
162 : : /* Get current default congestion control */
163 : 0 : void tcp_get_default_congestion_control(char *name)
164 : : {
165 : : struct tcp_congestion_ops *ca;
166 : : /* We will always have reno... */
167 [ - + ]: 2 : BUG_ON(list_empty(&tcp_cong_list));
168 : :
169 : : rcu_read_lock();
170 : 2 : ca = list_entry(tcp_cong_list.next, struct tcp_congestion_ops, list);
171 : 2 : strncpy(name, ca->name, TCP_CA_NAME_MAX);
172 : : rcu_read_unlock();
173 : 2 : }
174 : :
175 : : /* Built list of non-restricted congestion control values */
176 : 0 : void tcp_get_allowed_congestion_control(char *buf, size_t maxlen)
177 : : {
178 : : struct tcp_congestion_ops *ca;
179 : : size_t offs = 0;
180 : :
181 : 2 : *buf = '\0';
182 : : rcu_read_lock();
183 [ + + ]: 8 : list_for_each_entry_rcu(ca, &tcp_cong_list, list) {
184 [ - + ]: 4 : if (!(ca->flags & TCP_CONG_NON_RESTRICTED))
185 : 0 : continue;
186 [ + + ]: 4 : offs += snprintf(buf + offs, maxlen - offs,
187 : : "%s%s",
188 : 4 : offs == 0 ? "" : " ", ca->name);
189 : :
190 : : }
191 : : rcu_read_unlock();
192 : 2 : }
193 : :
194 : : /* Change list of non-restricted congestion control */
195 : 0 : int tcp_set_allowed_congestion_control(char *val)
196 : : {
197 : : struct tcp_congestion_ops *ca;
198 : : char *saved_clone, *clone, *name;
199 : : int ret = 0;
200 : :
201 : 0 : saved_clone = clone = kstrdup(val, GFP_USER);
202 [ # # ]: 0 : if (!clone)
203 : : return -ENOMEM;
204 : :
205 : : spin_lock(&tcp_cong_list_lock);
206 : : /* pass 1 check for bad entries */
207 [ # # ][ # # ]: 0 : while ((name = strsep(&clone, " ")) && *name) {
208 : 0 : ca = tcp_ca_find(name);
209 [ # # ]: 0 : if (!ca) {
210 : : ret = -ENOENT;
211 : : goto out;
212 : : }
213 : : }
214 : :
215 : : /* pass 2 clear old values */
216 [ # # ]: 0 : list_for_each_entry_rcu(ca, &tcp_cong_list, list)
217 : 0 : ca->flags &= ~TCP_CONG_NON_RESTRICTED;
218 : :
219 : : /* pass 3 mark as allowed */
220 [ # # ][ # # ]: 0 : while ((name = strsep(&val, " ")) && *name) {
221 : 0 : ca = tcp_ca_find(name);
222 [ # # ]: 0 : WARN_ON(!ca);
223 [ # # ]: 0 : if (ca)
224 : 0 : ca->flags |= TCP_CONG_NON_RESTRICTED;
225 : : }
226 : : out:
227 : : spin_unlock(&tcp_cong_list_lock);
228 : 0 : kfree(saved_clone);
229 : :
230 : 0 : return ret;
231 : : }
232 : :
233 : :
234 : : /* Change congestion control for socket */
235 : 0 : int tcp_set_congestion_control(struct sock *sk, const char *name)
236 : : {
237 : : struct inet_connection_sock *icsk = inet_csk(sk);
238 : : struct tcp_congestion_ops *ca;
239 : : int err = 0;
240 : :
241 : : rcu_read_lock();
242 : 0 : ca = tcp_ca_find(name);
243 : :
244 : : /* no change asking for existing value */
245 [ # # ]: 0 : if (ca == icsk->icsk_ca_ops)
246 : : goto out;
247 : :
248 : : #ifdef CONFIG_MODULES
249 : : /* not found attempt to autoload module */
250 [ # # ][ # # ]: 0 : if (!ca && capable(CAP_NET_ADMIN)) {
251 : : rcu_read_unlock();
252 : 0 : request_module("tcp_%s", name);
253 : : rcu_read_lock();
254 : 0 : ca = tcp_ca_find(name);
255 : : }
256 : : #endif
257 [ # # ]: 0 : if (!ca)
258 : : err = -ENOENT;
259 : :
260 [ # # # # ]: 0 : else if (!((ca->flags & TCP_CONG_NON_RESTRICTED) ||
261 : 0 : ns_capable(sock_net(sk)->user_ns, CAP_NET_ADMIN)))
262 : : err = -EPERM;
263 : :
264 [ # # ]: 0 : else if (!try_module_get(ca->owner))
265 : : err = -EBUSY;
266 : :
267 : : else {
268 : 0 : tcp_cleanup_congestion_control(sk);
269 : 0 : icsk->icsk_ca_ops = ca;
270 : :
271 [ # # ][ # # ]: 0 : if (sk->sk_state != TCP_CLOSE && icsk->icsk_ca_ops->init)
272 : 0 : icsk->icsk_ca_ops->init(sk);
273 : : }
274 : : out:
275 : : rcu_read_unlock();
276 : 0 : return err;
277 : : }
278 : :
279 : : /* RFC2861 Check whether we are limited by application or congestion window
280 : : * This is the inverse of cwnd check in tcp_tso_should_defer
281 : : */
282 : 0 : bool tcp_is_cwnd_limited(const struct sock *sk, u32 in_flight)
283 : : {
284 : : const struct tcp_sock *tp = tcp_sk(sk);
285 : : u32 left;
286 : :
287 [ + + ]: 38477 : if (in_flight >= tp->snd_cwnd)
288 : : return true;
289 : :
290 : 38428 : left = tp->snd_cwnd - in_flight;
291 [ + + ][ - + ]: 38428 : if (sk_can_gso(sk) &&
292 [ # # ]: 0 : left * sysctl_tcp_tso_win_divisor < tp->snd_cwnd &&
293 [ # # ]: 0 : left * tp->mss_cache < sk->sk_gso_max_size &&
294 : 0 : left < sk->sk_gso_max_segs)
295 : : return true;
296 : 38428 : return left <= tcp_max_tso_deferred_mss(tp);
297 : : }
298 : : EXPORT_SYMBOL_GPL(tcp_is_cwnd_limited);
299 : :
300 : : /* Slow start is used when congestion window is no greater than the slow start
301 : : * threshold. We base on RFC2581 and also handle stretch ACKs properly.
302 : : * We do not implement RFC3465 Appropriate Byte Counting (ABC) per se but
303 : : * something better;) a packet is only considered (s)acked in its entirety to
304 : : * defend the ACK attacks described in the RFC. Slow start processes a stretch
305 : : * ACK of degree N as if N acks of degree 1 are received back to back except
306 : : * ABC caps N to 2. Slow start exits when cwnd grows over ssthresh and
307 : : * returns the leftover acks to adjust cwnd in congestion avoidance mode.
308 : : */
309 : 0 : int tcp_slow_start(struct tcp_sock *tp, u32 acked)
310 : : {
311 : 28 : u32 cwnd = tp->snd_cwnd + acked;
312 : :
313 [ # # ][ + + ]: 28 : if (cwnd > tp->snd_ssthresh)
314 : 11 : cwnd = tp->snd_ssthresh + 1;
315 : 0 : acked -= cwnd - tp->snd_cwnd;
316 : 0 : tp->snd_cwnd = min(cwnd, tp->snd_cwnd_clamp);
317 : 0 : return acked;
318 : : }
319 : : EXPORT_SYMBOL_GPL(tcp_slow_start);
320 : :
321 : : /* In theory this is tp->snd_cwnd += 1 / tp->snd_cwnd (or alternative w) */
322 : 0 : void tcp_cong_avoid_ai(struct tcp_sock *tp, u32 w)
323 : : {
324 [ # # ][ + + ]: 188 : if (tp->snd_cwnd_cnt >= w) {
325 [ # # ][ + - ]: 82 : if (tp->snd_cwnd < tp->snd_cwnd_clamp)
326 : 82 : tp->snd_cwnd++;
327 : 82 : tp->snd_cwnd_cnt = 0;
328 : : } else {
329 : 106 : tp->snd_cwnd_cnt++;
330 : : }
331 : 188 : }
332 : : EXPORT_SYMBOL_GPL(tcp_cong_avoid_ai);
333 : :
334 : : /*
335 : : * TCP Reno congestion control
336 : : * This is special case used for fallback as well.
337 : : */
338 : : /* This is Jacobson's slow start and congestion avoidance.
339 : : * SIGCOMM '88, p. 328.
340 : : */
341 : 0 : void tcp_reno_cong_avoid(struct sock *sk, u32 ack, u32 acked, u32 in_flight)
342 : : {
343 : : struct tcp_sock *tp = tcp_sk(sk);
344 : :
345 [ # # ]: 0 : if (!tcp_is_cwnd_limited(sk, in_flight))
346 : 0 : return;
347 : :
348 : : /* In "safe" area, increase. */
349 [ # # ]: 0 : if (tp->snd_cwnd <= tp->snd_ssthresh)
350 : : tcp_slow_start(tp, acked);
351 : : /* In dangerous area, increase slowly. */
352 : : else
353 : : tcp_cong_avoid_ai(tp, tp->snd_cwnd);
354 : : }
355 : : EXPORT_SYMBOL_GPL(tcp_reno_cong_avoid);
356 : :
357 : : /* Slow start threshold is half the congestion window (min 2) */
358 : 0 : u32 tcp_reno_ssthresh(struct sock *sk)
359 : : {
360 : : const struct tcp_sock *tp = tcp_sk(sk);
361 : 0 : return max(tp->snd_cwnd >> 1U, 2U);
362 : : }
363 : : EXPORT_SYMBOL_GPL(tcp_reno_ssthresh);
364 : :
365 : : /* Lower bound on congestion window with halving. */
366 : 0 : u32 tcp_reno_min_cwnd(const struct sock *sk)
367 : : {
368 : : const struct tcp_sock *tp = tcp_sk(sk);
369 : 0 : return tp->snd_ssthresh/2;
370 : : }
371 : : EXPORT_SYMBOL_GPL(tcp_reno_min_cwnd);
372 : :
373 : : struct tcp_congestion_ops tcp_reno = {
374 : : .flags = TCP_CONG_NON_RESTRICTED,
375 : : .name = "reno",
376 : : .owner = THIS_MODULE,
377 : : .ssthresh = tcp_reno_ssthresh,
378 : : .cong_avoid = tcp_reno_cong_avoid,
379 : : .min_cwnd = tcp_reno_min_cwnd,
380 : : };
381 : :
382 : : /* Initial congestion control used (until SYN)
383 : : * really reno under another name so we can tell difference
384 : : * during tcp_set_default_congestion_control
385 : : */
386 : : struct tcp_congestion_ops tcp_init_congestion_ops = {
387 : : .name = "",
388 : : .owner = THIS_MODULE,
389 : : .ssthresh = tcp_reno_ssthresh,
390 : : .cong_avoid = tcp_reno_cong_avoid,
391 : : .min_cwnd = tcp_reno_min_cwnd,
392 : : };
393 : : EXPORT_SYMBOL_GPL(tcp_init_congestion_ops);
|