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 [ + - ]: 52 : if (icsk->icsk_ca_ops == &tcp_init_congestion_ops) {
84 : : rcu_read_lock();
85 [ + - ]: 52 : list_for_each_entry_rcu(ca, &tcp_cong_list, list) {
86 [ + - ]: 52 : if (try_module_get(ca->owner)) {
87 : 52 : icsk->icsk_ca_ops = ca;
88 : 52 : break;
89 : : }
90 : :
91 : : /* fallback to next available */
92 : : }
93 : : rcu_read_unlock();
94 : : }
95 : :
96 [ + - ]: 52 : if (icsk->icsk_ca_ops->init)
97 : 52 : icsk->icsk_ca_ops->init(sk);
98 : 52 : }
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 [ - + ]: 104 : if (icsk->icsk_ca_ops->release)
106 : 0 : icsk->icsk_ca_ops->release(sk);
107 : 104 : module_put(icsk->icsk_ca_ops->owner);
108 : 104 : }
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 [ + + ]: 21116 : if (in_flight >= tp->snd_cwnd)
288 : : return true;
289 : :
290 : 21066 : left = tp->snd_cwnd - in_flight;
291 [ + + ][ - + ]: 21066 : if (sk_can_gso(sk) &&
292 [ # # ]: 0 : left * sysctl_tcp_tso_win_divisor < tp->snd_cwnd &&
293 : 0 : left < tp->xmit_size_goal_segs)
294 : : return true;
295 : 21066 : return left <= tcp_max_tso_deferred_mss(tp);
296 : : }
297 : : EXPORT_SYMBOL_GPL(tcp_is_cwnd_limited);
298 : :
299 : : /* Slow start is used when congestion window is no greater than the slow start
300 : : * threshold. We base on RFC2581 and also handle stretch ACKs properly.
301 : : * We do not implement RFC3465 Appropriate Byte Counting (ABC) per se but
302 : : * something better;) a packet is only considered (s)acked in its entirety to
303 : : * defend the ACK attacks described in the RFC. Slow start processes a stretch
304 : : * ACK of degree N as if N acks of degree 1 are received back to back except
305 : : * ABC caps N to 2. Slow start exits when cwnd grows over ssthresh and
306 : : * returns the leftover acks to adjust cwnd in congestion avoidance mode.
307 : : */
308 : 0 : int tcp_slow_start(struct tcp_sock *tp, u32 acked)
309 : : {
310 : 35 : u32 cwnd = tp->snd_cwnd + acked;
311 : :
312 [ # # ][ + - ]: 35 : if (cwnd > tp->snd_ssthresh)
313 : 35 : cwnd = tp->snd_ssthresh + 1;
314 : 0 : acked -= cwnd - tp->snd_cwnd;
315 : 0 : tp->snd_cwnd = min(cwnd, tp->snd_cwnd_clamp);
316 : 0 : return acked;
317 : : }
318 : : EXPORT_SYMBOL_GPL(tcp_slow_start);
319 : :
320 : : /* In theory this is tp->snd_cwnd += 1 / tp->snd_cwnd (or alternative w) */
321 : 0 : void tcp_cong_avoid_ai(struct tcp_sock *tp, u32 w)
322 : : {
323 [ # # ][ + + ]: 303 : if (tp->snd_cwnd_cnt >= w) {
324 [ # # ][ + - ]: 85 : if (tp->snd_cwnd < tp->snd_cwnd_clamp)
325 : 85 : tp->snd_cwnd++;
326 : 85 : tp->snd_cwnd_cnt = 0;
327 : : } else {
328 : 218 : tp->snd_cwnd_cnt++;
329 : : }
330 : 303 : }
331 : : EXPORT_SYMBOL_GPL(tcp_cong_avoid_ai);
332 : :
333 : : /*
334 : : * TCP Reno congestion control
335 : : * This is special case used for fallback as well.
336 : : */
337 : : /* This is Jacobson's slow start and congestion avoidance.
338 : : * SIGCOMM '88, p. 328.
339 : : */
340 : 0 : void tcp_reno_cong_avoid(struct sock *sk, u32 ack, u32 acked, u32 in_flight)
341 : : {
342 : : struct tcp_sock *tp = tcp_sk(sk);
343 : :
344 [ # # ]: 0 : if (!tcp_is_cwnd_limited(sk, in_flight))
345 : 0 : return;
346 : :
347 : : /* In "safe" area, increase. */
348 [ # # ]: 0 : if (tp->snd_cwnd <= tp->snd_ssthresh)
349 : : tcp_slow_start(tp, acked);
350 : : /* In dangerous area, increase slowly. */
351 : : else
352 : : tcp_cong_avoid_ai(tp, tp->snd_cwnd);
353 : : }
354 : : EXPORT_SYMBOL_GPL(tcp_reno_cong_avoid);
355 : :
356 : : /* Slow start threshold is half the congestion window (min 2) */
357 : 0 : u32 tcp_reno_ssthresh(struct sock *sk)
358 : : {
359 : : const struct tcp_sock *tp = tcp_sk(sk);
360 : 0 : return max(tp->snd_cwnd >> 1U, 2U);
361 : : }
362 : : EXPORT_SYMBOL_GPL(tcp_reno_ssthresh);
363 : :
364 : : /* Lower bound on congestion window with halving. */
365 : 0 : u32 tcp_reno_min_cwnd(const struct sock *sk)
366 : : {
367 : : const struct tcp_sock *tp = tcp_sk(sk);
368 : 0 : return tp->snd_ssthresh/2;
369 : : }
370 : : EXPORT_SYMBOL_GPL(tcp_reno_min_cwnd);
371 : :
372 : : struct tcp_congestion_ops tcp_reno = {
373 : : .flags = TCP_CONG_NON_RESTRICTED,
374 : : .name = "reno",
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 : :
381 : : /* Initial congestion control used (until SYN)
382 : : * really reno under another name so we can tell difference
383 : : * during tcp_set_default_congestion_control
384 : : */
385 : : struct tcp_congestion_ops tcp_init_congestion_ops = {
386 : : .name = "",
387 : : .owner = THIS_MODULE,
388 : : .ssthresh = tcp_reno_ssthresh,
389 : : .cong_avoid = tcp_reno_cong_avoid,
390 : : .min_cwnd = tcp_reno_min_cwnd,
391 : : };
392 : : EXPORT_SYMBOL_GPL(tcp_init_congestion_ops);
|
