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 #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 int sysctl_tcp_max_ssthresh
= 0;
20 static DEFINE_SPINLOCK(tcp_cong_list_lock
);
21 static LIST_HEAD(tcp_cong_list
);
23 /* Simple linear search, don't expect many entries! */
24 static struct tcp_congestion_ops
*tcp_ca_find(const char *name
)
26 struct tcp_congestion_ops
*e
;
28 list_for_each_entry_rcu(e
, &tcp_cong_list
, list
) {
29 if (strcmp(e
->name
, name
) == 0)
37 * Attach new congestion control algorithm to the list
38 * of available options.
40 int tcp_register_congestion_control(struct tcp_congestion_ops
*ca
)
44 /* all algorithms must implement ssthresh and cong_avoid ops */
45 if (!ca
->ssthresh
|| !ca
->cong_avoid
) {
46 pr_err("%s does not implement required ops\n", ca
->name
);
50 spin_lock(&tcp_cong_list_lock
);
51 if (tcp_ca_find(ca
->name
)) {
52 pr_notice("%s already registered\n", ca
->name
);
55 list_add_tail_rcu(&ca
->list
, &tcp_cong_list
);
56 pr_info("%s registered\n", ca
->name
);
58 spin_unlock(&tcp_cong_list_lock
);
62 EXPORT_SYMBOL_GPL(tcp_register_congestion_control
);
65 * Remove congestion control algorithm, called from
66 * the module's remove function. Module ref counts are used
67 * to ensure that this can't be done till all sockets using
68 * that method are closed.
70 void tcp_unregister_congestion_control(struct tcp_congestion_ops
*ca
)
72 spin_lock(&tcp_cong_list_lock
);
73 list_del_rcu(&ca
->list
);
74 spin_unlock(&tcp_cong_list_lock
);
76 EXPORT_SYMBOL_GPL(tcp_unregister_congestion_control
);
78 /* Assign choice of congestion control. */
79 void tcp_init_congestion_control(struct sock
*sk
)
81 struct inet_connection_sock
*icsk
= inet_csk(sk
);
82 struct tcp_congestion_ops
*ca
;
84 /* if no choice made yet assign the current value set as default */
85 if (icsk
->icsk_ca_ops
== &tcp_init_congestion_ops
) {
87 list_for_each_entry_rcu(ca
, &tcp_cong_list
, list
) {
88 if (try_module_get(ca
->owner
)) {
89 icsk
->icsk_ca_ops
= ca
;
93 /* fallback to next available */
98 if (icsk
->icsk_ca_ops
->init
)
99 icsk
->icsk_ca_ops
->init(sk
);
102 /* Manage refcounts on socket close. */
103 void tcp_cleanup_congestion_control(struct sock
*sk
)
105 struct inet_connection_sock
*icsk
= inet_csk(sk
);
107 if (icsk
->icsk_ca_ops
->release
)
108 icsk
->icsk_ca_ops
->release(sk
);
109 module_put(icsk
->icsk_ca_ops
->owner
);
112 /* Used by sysctl to change default congestion control */
113 int tcp_set_default_congestion_control(const char *name
)
115 struct tcp_congestion_ops
*ca
;
118 spin_lock(&tcp_cong_list_lock
);
119 ca
= tcp_ca_find(name
);
120 #ifdef CONFIG_MODULES
121 if (!ca
&& capable(CAP_NET_ADMIN
)) {
122 spin_unlock(&tcp_cong_list_lock
);
124 request_module("tcp_%s", name
);
125 spin_lock(&tcp_cong_list_lock
);
126 ca
= tcp_ca_find(name
);
131 ca
->flags
|= TCP_CONG_NON_RESTRICTED
; /* default is always allowed */
132 list_move(&ca
->list
, &tcp_cong_list
);
135 spin_unlock(&tcp_cong_list_lock
);
140 /* Set default value from kernel configuration at bootup */
141 static int __init
tcp_congestion_default(void)
143 return tcp_set_default_congestion_control(CONFIG_DEFAULT_TCP_CONG
);
145 late_initcall(tcp_congestion_default
);
148 /* Build string with list of available congestion control values */
149 void tcp_get_available_congestion_control(char *buf
, size_t maxlen
)
151 struct tcp_congestion_ops
*ca
;
155 list_for_each_entry_rcu(ca
, &tcp_cong_list
, list
) {
156 offs
+= snprintf(buf
+ offs
, maxlen
- offs
,
158 offs
== 0 ? "" : " ", ca
->name
);
164 /* Get current default congestion control */
165 void tcp_get_default_congestion_control(char *name
)
167 struct tcp_congestion_ops
*ca
;
168 /* We will always have reno... */
169 BUG_ON(list_empty(&tcp_cong_list
));
172 ca
= list_entry(tcp_cong_list
.next
, struct tcp_congestion_ops
, list
);
173 strncpy(name
, ca
->name
, TCP_CA_NAME_MAX
);
177 /* Built list of non-restricted congestion control values */
178 void tcp_get_allowed_congestion_control(char *buf
, size_t maxlen
)
180 struct tcp_congestion_ops
*ca
;
185 list_for_each_entry_rcu(ca
, &tcp_cong_list
, list
) {
186 if (!(ca
->flags
& TCP_CONG_NON_RESTRICTED
))
188 offs
+= snprintf(buf
+ offs
, maxlen
- offs
,
190 offs
== 0 ? "" : " ", ca
->name
);
196 /* Change list of non-restricted congestion control */
197 int tcp_set_allowed_congestion_control(char *val
)
199 struct tcp_congestion_ops
*ca
;
200 char *saved_clone
, *clone
, *name
;
203 saved_clone
= clone
= kstrdup(val
, GFP_USER
);
207 spin_lock(&tcp_cong_list_lock
);
208 /* pass 1 check for bad entries */
209 while ((name
= strsep(&clone
, " ")) && *name
) {
210 ca
= tcp_ca_find(name
);
217 /* pass 2 clear old values */
218 list_for_each_entry_rcu(ca
, &tcp_cong_list
, list
)
219 ca
->flags
&= ~TCP_CONG_NON_RESTRICTED
;
221 /* pass 3 mark as allowed */
222 while ((name
= strsep(&val
, " ")) && *name
) {
223 ca
= tcp_ca_find(name
);
226 ca
->flags
|= TCP_CONG_NON_RESTRICTED
;
229 spin_unlock(&tcp_cong_list_lock
);
236 /* Change congestion control for socket */
237 int tcp_set_congestion_control(struct sock
*sk
, const char *name
)
239 struct inet_connection_sock
*icsk
= inet_csk(sk
);
240 struct tcp_congestion_ops
*ca
;
244 ca
= tcp_ca_find(name
);
246 /* no change asking for existing value */
247 if (ca
== icsk
->icsk_ca_ops
)
250 #ifdef CONFIG_MODULES
251 /* not found attempt to autoload module */
252 if (!ca
&& capable(CAP_NET_ADMIN
)) {
254 request_module("tcp_%s", name
);
256 ca
= tcp_ca_find(name
);
262 else if (!((ca
->flags
& TCP_CONG_NON_RESTRICTED
) || capable(CAP_NET_ADMIN
)))
265 else if (!try_module_get(ca
->owner
))
269 tcp_cleanup_congestion_control(sk
);
270 icsk
->icsk_ca_ops
= ca
;
272 if (sk
->sk_state
!= TCP_CLOSE
&& icsk
->icsk_ca_ops
->init
)
273 icsk
->icsk_ca_ops
->init(sk
);
280 /* RFC2861 Check whether we are limited by application or congestion window
281 * This is the inverse of cwnd check in tcp_tso_should_defer
283 bool tcp_is_cwnd_limited(const struct sock
*sk
, u32 in_flight
)
285 const struct tcp_sock
*tp
= tcp_sk(sk
);
288 if (in_flight
>= tp
->snd_cwnd
)
291 left
= tp
->snd_cwnd
- in_flight
;
292 if (sk_can_gso(sk
) &&
293 left
* sysctl_tcp_tso_win_divisor
< tp
->snd_cwnd
&&
294 left
* tp
->mss_cache
< sk
->sk_gso_max_size
&&
295 left
< sk
->sk_gso_max_segs
)
297 return left
<= tcp_max_tso_deferred_mss(tp
);
299 EXPORT_SYMBOL_GPL(tcp_is_cwnd_limited
);
302 * Slow start is used when congestion window is less than slow start
303 * threshold. This version implements the basic RFC2581 version
304 * and optionally supports:
305 * RFC3742 Limited Slow Start - growth limited to max_ssthresh
306 * RFC3465 Appropriate Byte Counting - growth limited by bytes acknowledged
308 void tcp_slow_start(struct tcp_sock
*tp
)
310 int cnt
; /* increase in packets */
311 unsigned int delta
= 0;
313 /* RFC3465: ABC Slow start
314 * Increase only after a full MSS of bytes is acked
316 * TCP sender SHOULD increase cwnd by the number of
317 * previously unacknowledged bytes ACKed by each incoming
318 * acknowledgment, provided the increase is not more than L
320 if (sysctl_tcp_abc
&& tp
->bytes_acked
< tp
->mss_cache
)
323 if (sysctl_tcp_max_ssthresh
> 0 && tp
->snd_cwnd
> sysctl_tcp_max_ssthresh
)
324 cnt
= sysctl_tcp_max_ssthresh
>> 1; /* limited slow start */
326 cnt
= tp
->snd_cwnd
; /* exponential increase */
329 * We MAY increase by 2 if discovered delayed ack
331 if (sysctl_tcp_abc
> 1 && tp
->bytes_acked
>= 2*tp
->mss_cache
)
335 tp
->snd_cwnd_cnt
+= cnt
;
336 while (tp
->snd_cwnd_cnt
>= tp
->snd_cwnd
) {
337 tp
->snd_cwnd_cnt
-= tp
->snd_cwnd
;
340 tp
->snd_cwnd
= min(tp
->snd_cwnd
+ delta
, tp
->snd_cwnd_clamp
);
342 EXPORT_SYMBOL_GPL(tcp_slow_start
);
344 /* In theory this is tp->snd_cwnd += 1 / tp->snd_cwnd (or alternative w) */
345 void tcp_cong_avoid_ai(struct tcp_sock
*tp
, u32 w
)
347 if (tp
->snd_cwnd_cnt
>= w
) {
348 if (tp
->snd_cwnd
< tp
->snd_cwnd_clamp
)
350 tp
->snd_cwnd_cnt
= 0;
355 EXPORT_SYMBOL_GPL(tcp_cong_avoid_ai
);
358 * TCP Reno congestion control
359 * This is special case used for fallback as well.
361 /* This is Jacobson's slow start and congestion avoidance.
362 * SIGCOMM '88, p. 328.
364 void tcp_reno_cong_avoid(struct sock
*sk
, u32 ack
, u32 in_flight
)
366 struct tcp_sock
*tp
= tcp_sk(sk
);
368 if (!tcp_is_cwnd_limited(sk
, in_flight
))
371 /* In "safe" area, increase. */
372 if (tp
->snd_cwnd
<= tp
->snd_ssthresh
)
375 /* In dangerous area, increase slowly. */
376 else if (sysctl_tcp_abc
) {
377 /* RFC3465: Appropriate Byte Count
378 * increase once for each full cwnd acked
380 if (tp
->bytes_acked
>= tp
->snd_cwnd
*tp
->mss_cache
) {
381 tp
->bytes_acked
-= tp
->snd_cwnd
*tp
->mss_cache
;
382 if (tp
->snd_cwnd
< tp
->snd_cwnd_clamp
)
386 tcp_cong_avoid_ai(tp
, tp
->snd_cwnd
);
389 EXPORT_SYMBOL_GPL(tcp_reno_cong_avoid
);
391 /* Slow start threshold is half the congestion window (min 2) */
392 u32
tcp_reno_ssthresh(struct sock
*sk
)
394 const struct tcp_sock
*tp
= tcp_sk(sk
);
395 return max(tp
->snd_cwnd
>> 1U, 2U);
397 EXPORT_SYMBOL_GPL(tcp_reno_ssthresh
);
399 /* Lower bound on congestion window with halving. */
400 u32
tcp_reno_min_cwnd(const struct sock
*sk
)
402 const struct tcp_sock
*tp
= tcp_sk(sk
);
403 return tp
->snd_ssthresh
/2;
405 EXPORT_SYMBOL_GPL(tcp_reno_min_cwnd
);
407 struct tcp_congestion_ops tcp_reno
= {
408 .flags
= TCP_CONG_NON_RESTRICTED
,
410 .owner
= THIS_MODULE
,
411 .ssthresh
= tcp_reno_ssthresh
,
412 .cong_avoid
= tcp_reno_cong_avoid
,
413 .min_cwnd
= tcp_reno_min_cwnd
,
416 /* Initial congestion control used (until SYN)
417 * really reno under another name so we can tell difference
418 * during tcp_set_default_congestion_control
420 struct tcp_congestion_ops tcp_init_congestion_ops
= {
422 .owner
= THIS_MODULE
,
423 .ssthresh
= tcp_reno_ssthresh
,
424 .cong_avoid
= tcp_reno_cong_avoid
,
425 .min_cwnd
= tcp_reno_min_cwnd
,
427 EXPORT_SYMBOL_GPL(tcp_init_congestion_ops
);