2 * Plugable TCP congestion control support and newReno
4 * Based on ideas from I/O scheduler suport and Web100.
6 * Copyright (C) 2005 Stephen Hemminger <shemminger@osdl.org>
9 #include <linux/module.h>
11 #include <linux/types.h>
12 #include <linux/list.h>
13 #include <linux/gfp.h>
16 int sysctl_tcp_max_ssthresh
= 0;
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("TCP %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("TCP %s already registered\n", ca
->name
);
53 list_add_tail_rcu(&ca
->list
, &tcp_cong_list
);
54 pr_info("TCP %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
) || capable(CAP_NET_ADMIN
)))
263 else if (!try_module_get(ca
->owner
))
267 tcp_cleanup_congestion_control(sk
);
268 icsk
->icsk_ca_ops
= ca
;
270 if (sk
->sk_state
!= TCP_CLOSE
&& icsk
->icsk_ca_ops
->init
)
271 icsk
->icsk_ca_ops
->init(sk
);
278 /* RFC2861 Check whether we are limited by application or congestion window
279 * This is the inverse of cwnd check in tcp_tso_should_defer
281 int tcp_is_cwnd_limited(const struct sock
*sk
, u32 in_flight
)
283 const struct tcp_sock
*tp
= tcp_sk(sk
);
286 if (in_flight
>= tp
->snd_cwnd
)
289 left
= tp
->snd_cwnd
- in_flight
;
290 if (sk_can_gso(sk
) &&
291 left
* sysctl_tcp_tso_win_divisor
< tp
->snd_cwnd
&&
292 left
* tp
->mss_cache
< sk
->sk_gso_max_size
)
294 return left
<= tcp_max_tso_deferred_mss(tp
);
296 EXPORT_SYMBOL_GPL(tcp_is_cwnd_limited
);
299 * Slow start is used when congestion window is less than slow start
300 * threshold. This version implements the basic RFC2581 version
301 * and optionally supports:
302 * RFC3742 Limited Slow Start - growth limited to max_ssthresh
303 * RFC3465 Appropriate Byte Counting - growth limited by bytes acknowledged
305 void tcp_slow_start(struct tcp_sock
*tp
)
307 int cnt
; /* increase in packets */
309 /* RFC3465: ABC Slow start
310 * Increase only after a full MSS of bytes is acked
312 * TCP sender SHOULD increase cwnd by the number of
313 * previously unacknowledged bytes ACKed by each incoming
314 * acknowledgment, provided the increase is not more than L
316 if (sysctl_tcp_abc
&& tp
->bytes_acked
< tp
->mss_cache
)
319 if (sysctl_tcp_max_ssthresh
> 0 && tp
->snd_cwnd
> sysctl_tcp_max_ssthresh
)
320 cnt
= sysctl_tcp_max_ssthresh
>> 1; /* limited slow start */
322 cnt
= tp
->snd_cwnd
; /* exponential increase */
325 * We MAY increase by 2 if discovered delayed ack
327 if (sysctl_tcp_abc
> 1 && tp
->bytes_acked
>= 2*tp
->mss_cache
)
331 tp
->snd_cwnd_cnt
+= cnt
;
332 while (tp
->snd_cwnd_cnt
>= tp
->snd_cwnd
) {
333 tp
->snd_cwnd_cnt
-= tp
->snd_cwnd
;
334 if (tp
->snd_cwnd
< tp
->snd_cwnd_clamp
)
338 EXPORT_SYMBOL_GPL(tcp_slow_start
);
340 /* In theory this is tp->snd_cwnd += 1 / tp->snd_cwnd (or alternative w) */
341 void tcp_cong_avoid_ai(struct tcp_sock
*tp
, u32 w
)
343 if (tp
->snd_cwnd_cnt
>= w
) {
344 if (tp
->snd_cwnd
< tp
->snd_cwnd_clamp
)
346 tp
->snd_cwnd_cnt
= 0;
351 EXPORT_SYMBOL_GPL(tcp_cong_avoid_ai
);
354 * TCP Reno congestion control
355 * This is special case used for fallback as well.
357 /* This is Jacobson's slow start and congestion avoidance.
358 * SIGCOMM '88, p. 328.
360 void tcp_reno_cong_avoid(struct sock
*sk
, u32 ack
, u32 in_flight
)
362 struct tcp_sock
*tp
= tcp_sk(sk
);
364 if (!tcp_is_cwnd_limited(sk
, in_flight
))
367 /* In "safe" area, increase. */
368 if (tp
->snd_cwnd
<= tp
->snd_ssthresh
)
371 /* In dangerous area, increase slowly. */
372 else if (sysctl_tcp_abc
) {
373 /* RFC3465: Appropriate Byte Count
374 * increase once for each full cwnd acked
376 if (tp
->bytes_acked
>= tp
->snd_cwnd
*tp
->mss_cache
) {
377 tp
->bytes_acked
-= tp
->snd_cwnd
*tp
->mss_cache
;
378 if (tp
->snd_cwnd
< tp
->snd_cwnd_clamp
)
382 tcp_cong_avoid_ai(tp
, tp
->snd_cwnd
);
385 EXPORT_SYMBOL_GPL(tcp_reno_cong_avoid
);
387 /* Slow start threshold is half the congestion window (min 2) */
388 u32
tcp_reno_ssthresh(struct sock
*sk
)
390 const struct tcp_sock
*tp
= tcp_sk(sk
);
391 return max(tp
->snd_cwnd
>> 1U, 2U);
393 EXPORT_SYMBOL_GPL(tcp_reno_ssthresh
);
395 /* Lower bound on congestion window with halving. */
396 u32
tcp_reno_min_cwnd(const struct sock
*sk
)
398 const struct tcp_sock
*tp
= tcp_sk(sk
);
399 return tp
->snd_ssthresh
/2;
401 EXPORT_SYMBOL_GPL(tcp_reno_min_cwnd
);
403 struct tcp_congestion_ops tcp_reno
= {
404 .flags
= TCP_CONG_NON_RESTRICTED
,
406 .owner
= THIS_MODULE
,
407 .ssthresh
= tcp_reno_ssthresh
,
408 .cong_avoid
= tcp_reno_cong_avoid
,
409 .min_cwnd
= tcp_reno_min_cwnd
,
412 /* Initial congestion control used (until SYN)
413 * really reno under another name so we can tell difference
414 * during tcp_set_default_congestion_control
416 struct tcp_congestion_ops tcp_init_congestion_ops
= {
418 .owner
= THIS_MODULE
,
419 .ssthresh
= tcp_reno_ssthresh
,
420 .cong_avoid
= tcp_reno_cong_avoid
,
421 .min_cwnd
= tcp_reno_min_cwnd
,
423 EXPORT_SYMBOL_GPL(tcp_init_congestion_ops
);