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>
15 int sysctl_tcp_max_ssthresh
= 0;
17 static DEFINE_SPINLOCK(tcp_cong_list_lock
);
18 static LIST_HEAD(tcp_cong_list
);
20 /* Simple linear search, don't expect many entries! */
21 static struct tcp_congestion_ops
*tcp_ca_find(const char *name
)
23 struct tcp_congestion_ops
*e
;
25 list_for_each_entry_rcu(e
, &tcp_cong_list
, list
) {
26 if (strcmp(e
->name
, name
) == 0)
34 * Attach new congestion control algorithm to the list
35 * of available options.
37 int tcp_register_congestion_control(struct tcp_congestion_ops
*ca
)
41 /* all algorithms must implement ssthresh and cong_avoid ops */
42 if (!ca
->ssthresh
|| !ca
->cong_avoid
) {
43 printk(KERN_ERR
"TCP %s does not implement required ops\n",
48 spin_lock(&tcp_cong_list_lock
);
49 if (tcp_ca_find(ca
->name
)) {
50 printk(KERN_NOTICE
"TCP %s already registered\n", ca
->name
);
53 list_add_tail_rcu(&ca
->list
, &tcp_cong_list
);
54 printk(KERN_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
);
119 if (!ca
&& capable(CAP_SYS_MODULE
)) {
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
)
249 /* not found attempt to autoload module */
250 if (!ca
&& capable(CAP_SYS_MODULE
)) {
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
);
280 * Slow start is used when congestion window is less than slow start
281 * threshold. This version implements the basic RFC2581 version
282 * and optionally supports:
283 * RFC3742 Limited Slow Start - growth limited to max_ssthresh
284 * RFC3465 Appropriate Byte Counting - growth limited by bytes acknowledged
286 void tcp_slow_start(struct tcp_sock
*tp
)
288 int cnt
; /* increase in packets */
290 /* RFC3465: ABC Slow start
291 * Increase only after a full MSS of bytes is acked
293 * TCP sender SHOULD increase cwnd by the number of
294 * previously unacknowledged bytes ACKed by each incoming
295 * acknowledgment, provided the increase is not more than L
297 if (sysctl_tcp_abc
&& tp
->bytes_acked
< tp
->mss_cache
)
300 if (sysctl_tcp_max_ssthresh
> 0 && tp
->snd_cwnd
> sysctl_tcp_max_ssthresh
)
301 cnt
= sysctl_tcp_max_ssthresh
>> 1; /* limited slow start */
303 cnt
= tp
->snd_cwnd
; /* exponential increase */
306 * We MAY increase by 2 if discovered delayed ack
308 if (sysctl_tcp_abc
> 1 && tp
->bytes_acked
>= 2*tp
->mss_cache
)
312 tp
->snd_cwnd_cnt
+= cnt
;
313 while (tp
->snd_cwnd_cnt
>= tp
->snd_cwnd
) {
314 tp
->snd_cwnd_cnt
-= tp
->snd_cwnd
;
315 if (tp
->snd_cwnd
< tp
->snd_cwnd_clamp
)
319 EXPORT_SYMBOL_GPL(tcp_slow_start
);
322 * TCP Reno congestion control
323 * This is special case used for fallback as well.
325 /* This is Jacobson's slow start and congestion avoidance.
326 * SIGCOMM '88, p. 328.
328 void tcp_reno_cong_avoid(struct sock
*sk
, u32 ack
, u32 rtt
, u32 in_flight
,
331 struct tcp_sock
*tp
= tcp_sk(sk
);
333 if (!tcp_is_cwnd_limited(sk
, in_flight
))
336 /* In "safe" area, increase. */
337 if (tp
->snd_cwnd
<= tp
->snd_ssthresh
)
340 /* In dangerous area, increase slowly. */
341 else if (sysctl_tcp_abc
) {
342 /* RFC3465: Appropriate Byte Count
343 * increase once for each full cwnd acked
345 if (tp
->bytes_acked
>= tp
->snd_cwnd
*tp
->mss_cache
) {
346 tp
->bytes_acked
-= tp
->snd_cwnd
*tp
->mss_cache
;
347 if (tp
->snd_cwnd
< tp
->snd_cwnd_clamp
)
351 /* In theory this is tp->snd_cwnd += 1 / tp->snd_cwnd */
352 if (tp
->snd_cwnd_cnt
>= tp
->snd_cwnd
) {
353 if (tp
->snd_cwnd
< tp
->snd_cwnd_clamp
)
355 tp
->snd_cwnd_cnt
= 0;
360 EXPORT_SYMBOL_GPL(tcp_reno_cong_avoid
);
362 /* Slow start threshold is half the congestion window (min 2) */
363 u32
tcp_reno_ssthresh(struct sock
*sk
)
365 const struct tcp_sock
*tp
= tcp_sk(sk
);
366 return max(tp
->snd_cwnd
>> 1U, 2U);
368 EXPORT_SYMBOL_GPL(tcp_reno_ssthresh
);
370 /* Lower bound on congestion window with halving. */
371 u32
tcp_reno_min_cwnd(const struct sock
*sk
)
373 const struct tcp_sock
*tp
= tcp_sk(sk
);
374 return tp
->snd_ssthresh
/2;
376 EXPORT_SYMBOL_GPL(tcp_reno_min_cwnd
);
378 struct tcp_congestion_ops tcp_reno
= {
379 .flags
= TCP_CONG_NON_RESTRICTED
,
381 .owner
= THIS_MODULE
,
382 .ssthresh
= tcp_reno_ssthresh
,
383 .cong_avoid
= tcp_reno_cong_avoid
,
384 .min_cwnd
= tcp_reno_min_cwnd
,
387 /* Initial congestion control used (until SYN)
388 * really reno under another name so we can tell difference
389 * during tcp_set_default_congestion_control
391 struct tcp_congestion_ops tcp_init_congestion_ops
= {
393 .owner
= THIS_MODULE
,
394 .ssthresh
= tcp_reno_ssthresh
,
395 .cong_avoid
= tcp_reno_cong_avoid
,
396 .min_cwnd
= tcp_reno_min_cwnd
,
398 EXPORT_SYMBOL_GPL(tcp_init_congestion_ops
);