2 * Pluggable 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>
16 #include <linux/jhash.h>
19 static DEFINE_SPINLOCK(tcp_cong_list_lock
);
20 static LIST_HEAD(tcp_cong_list
);
22 /* Simple linear search, don't expect many entries! */
23 static struct tcp_congestion_ops
*tcp_ca_find(const char *name
)
25 struct tcp_congestion_ops
*e
;
27 list_for_each_entry_rcu(e
, &tcp_cong_list
, list
) {
28 if (strcmp(e
->name
, name
) == 0)
35 /* Must be called with rcu lock held */
36 static const struct tcp_congestion_ops
*__tcp_ca_find_autoload(const char *name
)
38 const struct tcp_congestion_ops
*ca
= tcp_ca_find(name
);
40 if (!ca
&& capable(CAP_NET_ADMIN
)) {
42 request_module("tcp_%s", name
);
44 ca
= tcp_ca_find(name
);
50 /* Simple linear search, not much in here. */
51 struct tcp_congestion_ops
*tcp_ca_find_key(u32 key
)
53 struct tcp_congestion_ops
*e
;
55 list_for_each_entry_rcu(e
, &tcp_cong_list
, list
) {
64 * Attach new congestion control algorithm to the list
65 * of available options.
67 int tcp_register_congestion_control(struct tcp_congestion_ops
*ca
)
71 /* all algorithms must implement these */
72 if (!ca
->ssthresh
|| !ca
->undo_cwnd
||
73 !(ca
->cong_avoid
|| ca
->cong_control
)) {
74 pr_err("%s does not implement required ops\n", ca
->name
);
78 ca
->key
= jhash(ca
->name
, sizeof(ca
->name
), strlen(ca
->name
));
80 spin_lock(&tcp_cong_list_lock
);
81 if (ca
->key
== TCP_CA_UNSPEC
|| tcp_ca_find_key(ca
->key
)) {
82 pr_notice("%s already registered or non-unique key\n",
86 list_add_tail_rcu(&ca
->list
, &tcp_cong_list
);
87 pr_debug("%s registered\n", ca
->name
);
89 spin_unlock(&tcp_cong_list_lock
);
93 EXPORT_SYMBOL_GPL(tcp_register_congestion_control
);
96 * Remove congestion control algorithm, called from
97 * the module's remove function. Module ref counts are used
98 * to ensure that this can't be done till all sockets using
99 * that method are closed.
101 void tcp_unregister_congestion_control(struct tcp_congestion_ops
*ca
)
103 spin_lock(&tcp_cong_list_lock
);
104 list_del_rcu(&ca
->list
);
105 spin_unlock(&tcp_cong_list_lock
);
107 /* Wait for outstanding readers to complete before the
108 * module gets removed entirely.
110 * A try_module_get() should fail by now as our module is
111 * in "going" state since no refs are held anymore and
112 * module_exit() handler being called.
116 EXPORT_SYMBOL_GPL(tcp_unregister_congestion_control
);
118 u32
tcp_ca_get_key_by_name(const char *name
, bool *ecn_ca
)
120 const struct tcp_congestion_ops
*ca
;
121 u32 key
= TCP_CA_UNSPEC
;
126 ca
= __tcp_ca_find_autoload(name
);
129 *ecn_ca
= ca
->flags
& TCP_CONG_NEEDS_ECN
;
135 EXPORT_SYMBOL_GPL(tcp_ca_get_key_by_name
);
137 char *tcp_ca_get_name_by_key(u32 key
, char *buffer
)
139 const struct tcp_congestion_ops
*ca
;
143 ca
= tcp_ca_find_key(key
);
145 ret
= strncpy(buffer
, ca
->name
,
151 EXPORT_SYMBOL_GPL(tcp_ca_get_name_by_key
);
153 /* Assign choice of congestion control. */
154 void tcp_assign_congestion_control(struct sock
*sk
)
156 struct inet_connection_sock
*icsk
= inet_csk(sk
);
157 struct tcp_congestion_ops
*ca
;
160 list_for_each_entry_rcu(ca
, &tcp_cong_list
, list
) {
161 if (likely(try_module_get(ca
->owner
))) {
162 icsk
->icsk_ca_ops
= ca
;
165 /* Fallback to next available. The last really
166 * guaranteed fallback is Reno from this list.
171 memset(icsk
->icsk_ca_priv
, 0, sizeof(icsk
->icsk_ca_priv
));
173 if (ca
->flags
& TCP_CONG_NEEDS_ECN
)
176 INET_ECN_dontxmit(sk
);
179 void tcp_init_congestion_control(struct sock
*sk
)
181 const struct inet_connection_sock
*icsk
= inet_csk(sk
);
183 tcp_sk(sk
)->prior_ssthresh
= 0;
184 if (icsk
->icsk_ca_ops
->init
)
185 icsk
->icsk_ca_ops
->init(sk
);
186 if (tcp_ca_needs_ecn(sk
))
189 INET_ECN_dontxmit(sk
);
192 static void tcp_reinit_congestion_control(struct sock
*sk
,
193 const struct tcp_congestion_ops
*ca
)
195 struct inet_connection_sock
*icsk
= inet_csk(sk
);
197 tcp_cleanup_congestion_control(sk
);
198 icsk
->icsk_ca_ops
= ca
;
199 icsk
->icsk_ca_setsockopt
= 1;
200 memset(icsk
->icsk_ca_priv
, 0, sizeof(icsk
->icsk_ca_priv
));
202 if (sk
->sk_state
!= TCP_CLOSE
)
203 tcp_init_congestion_control(sk
);
206 /* Manage refcounts on socket close. */
207 void tcp_cleanup_congestion_control(struct sock
*sk
)
209 struct inet_connection_sock
*icsk
= inet_csk(sk
);
211 if (icsk
->icsk_ca_ops
->release
)
212 icsk
->icsk_ca_ops
->release(sk
);
213 module_put(icsk
->icsk_ca_ops
->owner
);
216 /* Used by sysctl to change default congestion control */
217 int tcp_set_default_congestion_control(const char *name
)
219 struct tcp_congestion_ops
*ca
;
222 spin_lock(&tcp_cong_list_lock
);
223 ca
= tcp_ca_find(name
);
224 #ifdef CONFIG_MODULES
225 if (!ca
&& capable(CAP_NET_ADMIN
)) {
226 spin_unlock(&tcp_cong_list_lock
);
228 request_module("tcp_%s", name
);
229 spin_lock(&tcp_cong_list_lock
);
230 ca
= tcp_ca_find(name
);
235 ca
->flags
|= TCP_CONG_NON_RESTRICTED
; /* default is always allowed */
236 list_move(&ca
->list
, &tcp_cong_list
);
239 spin_unlock(&tcp_cong_list_lock
);
244 /* Set default value from kernel configuration at bootup */
245 static int __init
tcp_congestion_default(void)
247 return tcp_set_default_congestion_control(CONFIG_DEFAULT_TCP_CONG
);
249 late_initcall(tcp_congestion_default
);
251 /* Build string with list of available congestion control values */
252 void tcp_get_available_congestion_control(char *buf
, size_t maxlen
)
254 struct tcp_congestion_ops
*ca
;
258 list_for_each_entry_rcu(ca
, &tcp_cong_list
, list
) {
259 offs
+= snprintf(buf
+ offs
, maxlen
- offs
,
261 offs
== 0 ? "" : " ", ca
->name
);
266 /* Get current default congestion control */
267 void tcp_get_default_congestion_control(char *name
)
269 struct tcp_congestion_ops
*ca
;
270 /* We will always have reno... */
271 BUG_ON(list_empty(&tcp_cong_list
));
274 ca
= list_entry(tcp_cong_list
.next
, struct tcp_congestion_ops
, list
);
275 strncpy(name
, ca
->name
, TCP_CA_NAME_MAX
);
279 /* Built list of non-restricted congestion control values */
280 void tcp_get_allowed_congestion_control(char *buf
, size_t maxlen
)
282 struct tcp_congestion_ops
*ca
;
287 list_for_each_entry_rcu(ca
, &tcp_cong_list
, list
) {
288 if (!(ca
->flags
& TCP_CONG_NON_RESTRICTED
))
290 offs
+= snprintf(buf
+ offs
, maxlen
- offs
,
292 offs
== 0 ? "" : " ", ca
->name
);
297 /* Change list of non-restricted congestion control */
298 int tcp_set_allowed_congestion_control(char *val
)
300 struct tcp_congestion_ops
*ca
;
301 char *saved_clone
, *clone
, *name
;
304 saved_clone
= clone
= kstrdup(val
, GFP_USER
);
308 spin_lock(&tcp_cong_list_lock
);
309 /* pass 1 check for bad entries */
310 while ((name
= strsep(&clone
, " ")) && *name
) {
311 ca
= tcp_ca_find(name
);
318 /* pass 2 clear old values */
319 list_for_each_entry_rcu(ca
, &tcp_cong_list
, list
)
320 ca
->flags
&= ~TCP_CONG_NON_RESTRICTED
;
322 /* pass 3 mark as allowed */
323 while ((name
= strsep(&val
, " ")) && *name
) {
324 ca
= tcp_ca_find(name
);
327 ca
->flags
|= TCP_CONG_NON_RESTRICTED
;
330 spin_unlock(&tcp_cong_list_lock
);
336 /* Change congestion control for socket */
337 int tcp_set_congestion_control(struct sock
*sk
, const char *name
)
339 struct inet_connection_sock
*icsk
= inet_csk(sk
);
340 const struct tcp_congestion_ops
*ca
;
343 if (icsk
->icsk_ca_dst_locked
)
347 ca
= __tcp_ca_find_autoload(name
);
348 /* No change asking for existing value */
349 if (ca
== icsk
->icsk_ca_ops
) {
350 icsk
->icsk_ca_setsockopt
= 1;
355 else if (!((ca
->flags
& TCP_CONG_NON_RESTRICTED
) ||
356 ns_capable(sock_net(sk
)->user_ns
, CAP_NET_ADMIN
)))
358 else if (!try_module_get(ca
->owner
))
361 tcp_reinit_congestion_control(sk
, ca
);
367 /* Slow start is used when congestion window is no greater than the slow start
368 * threshold. We base on RFC2581 and also handle stretch ACKs properly.
369 * We do not implement RFC3465 Appropriate Byte Counting (ABC) per se but
370 * something better;) a packet is only considered (s)acked in its entirety to
371 * defend the ACK attacks described in the RFC. Slow start processes a stretch
372 * ACK of degree N as if N acks of degree 1 are received back to back except
373 * ABC caps N to 2. Slow start exits when cwnd grows over ssthresh and
374 * returns the leftover acks to adjust cwnd in congestion avoidance mode.
376 u32
tcp_slow_start(struct tcp_sock
*tp
, u32 acked
)
378 u32 cwnd
= min(tp
->snd_cwnd
+ acked
, tp
->snd_ssthresh
);
380 acked
-= cwnd
- tp
->snd_cwnd
;
381 tp
->snd_cwnd
= min(cwnd
, tp
->snd_cwnd_clamp
);
385 EXPORT_SYMBOL_GPL(tcp_slow_start
);
387 /* In theory this is tp->snd_cwnd += 1 / tp->snd_cwnd (or alternative w),
388 * for every packet that was ACKed.
390 void tcp_cong_avoid_ai(struct tcp_sock
*tp
, u32 w
, u32 acked
)
392 /* If credits accumulated at a higher w, apply them gently now. */
393 if (tp
->snd_cwnd_cnt
>= w
) {
394 tp
->snd_cwnd_cnt
= 0;
398 tp
->snd_cwnd_cnt
+= acked
;
399 if (tp
->snd_cwnd_cnt
>= w
) {
400 u32 delta
= tp
->snd_cwnd_cnt
/ w
;
402 tp
->snd_cwnd_cnt
-= delta
* w
;
403 tp
->snd_cwnd
+= delta
;
405 tp
->snd_cwnd
= min(tp
->snd_cwnd
, tp
->snd_cwnd_clamp
);
407 EXPORT_SYMBOL_GPL(tcp_cong_avoid_ai
);
410 * TCP Reno congestion control
411 * This is special case used for fallback as well.
413 /* This is Jacobson's slow start and congestion avoidance.
414 * SIGCOMM '88, p. 328.
416 void tcp_reno_cong_avoid(struct sock
*sk
, u32 ack
, u32 acked
)
418 struct tcp_sock
*tp
= tcp_sk(sk
);
420 if (!tcp_is_cwnd_limited(sk
))
423 /* In "safe" area, increase. */
424 if (tcp_in_slow_start(tp
)) {
425 acked
= tcp_slow_start(tp
, acked
);
429 /* In dangerous area, increase slowly. */
430 tcp_cong_avoid_ai(tp
, tp
->snd_cwnd
, acked
);
432 EXPORT_SYMBOL_GPL(tcp_reno_cong_avoid
);
434 /* Slow start threshold is half the congestion window (min 2) */
435 u32
tcp_reno_ssthresh(struct sock
*sk
)
437 const struct tcp_sock
*tp
= tcp_sk(sk
);
439 return max(tp
->snd_cwnd
>> 1U, 2U);
441 EXPORT_SYMBOL_GPL(tcp_reno_ssthresh
);
443 u32
tcp_reno_undo_cwnd(struct sock
*sk
)
445 const struct tcp_sock
*tp
= tcp_sk(sk
);
447 return max(tp
->snd_cwnd
, tp
->snd_ssthresh
<< 1);
449 EXPORT_SYMBOL_GPL(tcp_reno_undo_cwnd
);
451 struct tcp_congestion_ops tcp_reno
= {
452 .flags
= TCP_CONG_NON_RESTRICTED
,
454 .owner
= THIS_MODULE
,
455 .ssthresh
= tcp_reno_ssthresh
,
456 .cong_avoid
= tcp_reno_cong_avoid
,
457 .undo_cwnd
= tcp_reno_undo_cwnd
,