2 * Plugable TCP congestion control support and newReno
4 * Based on ideas from I/O scheduler support and Web100.
6 * Copyright (C) 2005 Stephen Hemminger <shemminger@osdl.org>
9 #define pr_fmt(fmt) "TCP: " fmt
11 #include <linux/module.h>
13 #include <linux/types.h>
14 #include <linux/list.h>
15 #include <linux/gfp.h>
18 static DEFINE_SPINLOCK(tcp_cong_list_lock
);
19 static LIST_HEAD(tcp_cong_list
);
21 /* Simple linear search, don't expect many entries! */
22 static struct tcp_congestion_ops
*tcp_ca_find(const char *name
)
24 struct tcp_congestion_ops
*e
;
26 list_for_each_entry_rcu(e
, &tcp_cong_list
, list
) {
27 if (strcmp(e
->name
, name
) == 0)
35 * Attach new congestion control algorithm to the list
36 * of available options.
38 int tcp_register_congestion_control(struct tcp_congestion_ops
*ca
)
42 /* all algorithms must implement ssthresh and cong_avoid ops */
43 if (!ca
->ssthresh
|| !ca
->cong_avoid
) {
44 pr_err("%s does not implement required ops\n", ca
->name
);
48 spin_lock(&tcp_cong_list_lock
);
49 if (tcp_ca_find(ca
->name
)) {
50 pr_notice("%s already registered\n", ca
->name
);
53 list_add_tail_rcu(&ca
->list
, &tcp_cong_list
);
54 pr_info("%s registered\n", ca
->name
);
56 spin_unlock(&tcp_cong_list_lock
);
60 EXPORT_SYMBOL_GPL(tcp_register_congestion_control
);
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.
68 void tcp_unregister_congestion_control(struct tcp_congestion_ops
*ca
)
70 spin_lock(&tcp_cong_list_lock
);
71 list_del_rcu(&ca
->list
);
72 spin_unlock(&tcp_cong_list_lock
);
74 EXPORT_SYMBOL_GPL(tcp_unregister_congestion_control
);
76 /* Assign choice of congestion control. */
77 void tcp_init_congestion_control(struct sock
*sk
)
79 struct inet_connection_sock
*icsk
= inet_csk(sk
);
80 struct tcp_congestion_ops
*ca
;
82 /* if no choice made yet assign the current value set as default */
83 if (icsk
->icsk_ca_ops
== &tcp_init_congestion_ops
) {
85 list_for_each_entry_rcu(ca
, &tcp_cong_list
, list
) {
86 if (try_module_get(ca
->owner
)) {
87 icsk
->icsk_ca_ops
= ca
;
91 /* fallback to next available */
96 if (icsk
->icsk_ca_ops
->init
)
97 icsk
->icsk_ca_ops
->init(sk
);
100 /* Manage refcounts on socket close. */
101 void tcp_cleanup_congestion_control(struct sock
*sk
)
103 struct inet_connection_sock
*icsk
= inet_csk(sk
);
105 if (icsk
->icsk_ca_ops
->release
)
106 icsk
->icsk_ca_ops
->release(sk
);
107 module_put(icsk
->icsk_ca_ops
->owner
);
110 /* Used by sysctl to change default congestion control */
111 int tcp_set_default_congestion_control(const char *name
)
113 struct tcp_congestion_ops
*ca
;
116 spin_lock(&tcp_cong_list_lock
);
117 ca
= tcp_ca_find(name
);
118 #ifdef CONFIG_MODULES
119 if (!ca
&& capable(CAP_NET_ADMIN
)) {
120 spin_unlock(&tcp_cong_list_lock
);
122 request_module("tcp_%s", name
);
123 spin_lock(&tcp_cong_list_lock
);
124 ca
= tcp_ca_find(name
);
129 ca
->flags
|= TCP_CONG_NON_RESTRICTED
; /* default is always allowed */
130 list_move(&ca
->list
, &tcp_cong_list
);
133 spin_unlock(&tcp_cong_list_lock
);
138 /* Set default value from kernel configuration at bootup */
139 static int __init
tcp_congestion_default(void)
141 return tcp_set_default_congestion_control(CONFIG_DEFAULT_TCP_CONG
);
143 late_initcall(tcp_congestion_default
);
146 /* Build string with list of available congestion control values */
147 void tcp_get_available_congestion_control(char *buf
, size_t maxlen
)
149 struct tcp_congestion_ops
*ca
;
153 list_for_each_entry_rcu(ca
, &tcp_cong_list
, list
) {
154 offs
+= snprintf(buf
+ offs
, maxlen
- offs
,
156 offs
== 0 ? "" : " ", ca
->name
);
162 /* Get current default congestion control */
163 void tcp_get_default_congestion_control(char *name
)
165 struct tcp_congestion_ops
*ca
;
166 /* We will always have reno... */
167 BUG_ON(list_empty(&tcp_cong_list
));
170 ca
= list_entry(tcp_cong_list
.next
, struct tcp_congestion_ops
, list
);
171 strncpy(name
, ca
->name
, TCP_CA_NAME_MAX
);
175 /* Built list of non-restricted congestion control values */
176 void tcp_get_allowed_congestion_control(char *buf
, size_t maxlen
)
178 struct tcp_congestion_ops
*ca
;
183 list_for_each_entry_rcu(ca
, &tcp_cong_list
, list
) {
184 if (!(ca
->flags
& TCP_CONG_NON_RESTRICTED
))
186 offs
+= snprintf(buf
+ offs
, maxlen
- offs
,
188 offs
== 0 ? "" : " ", ca
->name
);
194 /* Change list of non-restricted congestion control */
195 int tcp_set_allowed_congestion_control(char *val
)
197 struct tcp_congestion_ops
*ca
;
198 char *saved_clone
, *clone
, *name
;
201 saved_clone
= clone
= kstrdup(val
, GFP_USER
);
205 spin_lock(&tcp_cong_list_lock
);
206 /* pass 1 check for bad entries */
207 while ((name
= strsep(&clone
, " ")) && *name
) {
208 ca
= tcp_ca_find(name
);
215 /* pass 2 clear old values */
216 list_for_each_entry_rcu(ca
, &tcp_cong_list
, list
)
217 ca
->flags
&= ~TCP_CONG_NON_RESTRICTED
;
219 /* pass 3 mark as allowed */
220 while ((name
= strsep(&val
, " ")) && *name
) {
221 ca
= tcp_ca_find(name
);
224 ca
->flags
|= TCP_CONG_NON_RESTRICTED
;
227 spin_unlock(&tcp_cong_list_lock
);
234 /* Change congestion control for socket */
235 int tcp_set_congestion_control(struct sock
*sk
, const char *name
)
237 struct inet_connection_sock
*icsk
= inet_csk(sk
);
238 struct tcp_congestion_ops
*ca
;
242 ca
= tcp_ca_find(name
);
244 /* no change asking for existing value */
245 if (ca
== icsk
->icsk_ca_ops
)
248 #ifdef CONFIG_MODULES
249 /* not found attempt to autoload module */
250 if (!ca
&& capable(CAP_NET_ADMIN
)) {
252 request_module("tcp_%s", name
);
254 ca
= tcp_ca_find(name
);
260 else if (!((ca
->flags
& TCP_CONG_NON_RESTRICTED
) ||
261 ns_capable(sock_net(sk
)->user_ns
, CAP_NET_ADMIN
)))
264 else if (!try_module_get(ca
->owner
))
268 tcp_cleanup_congestion_control(sk
);
269 icsk
->icsk_ca_ops
= ca
;
271 if (sk
->sk_state
!= TCP_CLOSE
&& icsk
->icsk_ca_ops
->init
)
272 icsk
->icsk_ca_ops
->init(sk
);
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
282 bool tcp_is_cwnd_limited(const struct sock
*sk
, u32 in_flight
)
284 const struct tcp_sock
*tp
= tcp_sk(sk
);
287 if (in_flight
>= tp
->snd_cwnd
)
290 left
= tp
->snd_cwnd
- in_flight
;
291 if (sk_can_gso(sk
) &&
292 left
* sysctl_tcp_tso_win_divisor
< tp
->snd_cwnd
&&
293 left
* tp
->mss_cache
< sk
->sk_gso_max_size
&&
294 left
< sk
->sk_gso_max_segs
)
296 return left
<= tcp_max_tso_deferred_mss(tp
);
298 EXPORT_SYMBOL_GPL(tcp_is_cwnd_limited
);
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.
309 int tcp_slow_start(struct tcp_sock
*tp
, u32 acked
)
311 u32 cwnd
= tp
->snd_cwnd
+ acked
;
313 if (cwnd
> tp
->snd_ssthresh
)
314 cwnd
= tp
->snd_ssthresh
+ 1;
315 acked
-= cwnd
- tp
->snd_cwnd
;
316 tp
->snd_cwnd
= min(cwnd
, tp
->snd_cwnd_clamp
);
319 EXPORT_SYMBOL_GPL(tcp_slow_start
);
321 /* In theory this is tp->snd_cwnd += 1 / tp->snd_cwnd (or alternative w) */
322 void tcp_cong_avoid_ai(struct tcp_sock
*tp
, u32 w
)
324 if (tp
->snd_cwnd_cnt
>= w
) {
325 if (tp
->snd_cwnd
< tp
->snd_cwnd_clamp
)
327 tp
->snd_cwnd_cnt
= 0;
332 EXPORT_SYMBOL_GPL(tcp_cong_avoid_ai
);
335 * TCP Reno congestion control
336 * This is special case used for fallback as well.
338 /* This is Jacobson's slow start and congestion avoidance.
339 * SIGCOMM '88, p. 328.
341 void tcp_reno_cong_avoid(struct sock
*sk
, u32 ack
, u32 acked
, u32 in_flight
)
343 struct tcp_sock
*tp
= tcp_sk(sk
);
345 if (!tcp_is_cwnd_limited(sk
, in_flight
))
348 /* In "safe" area, increase. */
349 if (tp
->snd_cwnd
<= tp
->snd_ssthresh
)
350 tcp_slow_start(tp
, acked
);
351 /* In dangerous area, increase slowly. */
353 tcp_cong_avoid_ai(tp
, tp
->snd_cwnd
);
355 EXPORT_SYMBOL_GPL(tcp_reno_cong_avoid
);
357 /* Slow start threshold is half the congestion window (min 2) */
358 u32
tcp_reno_ssthresh(struct sock
*sk
)
360 const struct tcp_sock
*tp
= tcp_sk(sk
);
361 return max(tp
->snd_cwnd
>> 1U, 2U);
363 EXPORT_SYMBOL_GPL(tcp_reno_ssthresh
);
365 /* Lower bound on congestion window with halving. */
366 u32
tcp_reno_min_cwnd(const struct sock
*sk
)
368 const struct tcp_sock
*tp
= tcp_sk(sk
);
369 return tp
->snd_ssthresh
/2;
371 EXPORT_SYMBOL_GPL(tcp_reno_min_cwnd
);
373 struct tcp_congestion_ops tcp_reno
= {
374 .flags
= TCP_CONG_NON_RESTRICTED
,
376 .owner
= THIS_MODULE
,
377 .ssthresh
= tcp_reno_ssthresh
,
378 .cong_avoid
= tcp_reno_cong_avoid
,
379 .min_cwnd
= tcp_reno_min_cwnd
,
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
386 struct tcp_congestion_ops tcp_init_congestion_ops
= {
388 .owner
= THIS_MODULE
,
389 .ssthresh
= tcp_reno_ssthresh
,
390 .cong_avoid
= tcp_reno_cong_avoid
,
391 .min_cwnd
= tcp_reno_min_cwnd
,
393 EXPORT_SYMBOL_GPL(tcp_init_congestion_ops
);