~ [ source navigation ] ~ [ diff markup ] ~ [ identifier search ] ~

TOMOYO Linux Cross Reference
Linux/net/ipv4/tcp_cong.c

Version: ~ [ linux-5.8-rc3 ] ~ [ linux-5.7.5 ] ~ [ linux-5.6.19 ] ~ [ linux-5.5.19 ] ~ [ linux-5.4.48 ] ~ [ linux-5.3.18 ] ~ [ linux-5.2.21 ] ~ [ linux-5.1.21 ] ~ [ linux-5.0.21 ] ~ [ linux-4.20.17 ] ~ [ linux-4.19.129 ] ~ [ linux-4.18.20 ] ~ [ linux-4.17.19 ] ~ [ linux-4.16.18 ] ~ [ linux-4.15.18 ] ~ [ linux-4.14.185 ] ~ [ linux-4.13.16 ] ~ [ linux-4.12.14 ] ~ [ linux-4.11.12 ] ~ [ linux-4.10.17 ] ~ [ linux-4.9.228 ] ~ [ linux-4.8.17 ] ~ [ linux-4.7.10 ] ~ [ linux-4.6.7 ] ~ [ linux-4.5.7 ] ~ [ linux-4.4.228 ] ~ [ linux-4.3.6 ] ~ [ linux-4.2.8 ] ~ [ linux-4.1.52 ] ~ [ linux-4.0.9 ] ~ [ linux-3.19.8 ] ~ [ linux-3.18.140 ] ~ [ linux-3.17.8 ] ~ [ linux-3.16.85 ] ~ [ linux-3.15.10 ] ~ [ linux-3.14.79 ] ~ [ linux-3.13.11 ] ~ [ linux-3.12.74 ] ~ [ linux-3.11.10 ] ~ [ linux-3.10.108 ] ~ [ linux-2.6.32.71 ] ~ [ linux-2.6.0 ] ~ [ linux-2.4.37.11 ] ~ [ unix-v6-master ] ~ [ ccs-tools-1.8.5 ] ~ [ policy-sample ] ~
Architecture: ~ [ i386 ] ~ [ alpha ] ~ [ m68k ] ~ [ mips ] ~ [ ppc ] ~ [ sparc ] ~ [ sparc64 ] ~

  1 /*
  2  * Pluggable TCP congestion control support and newReno
  3  * congestion control.
  4  * Based on ideas from I/O scheduler support and Web100.
  5  *
  6  * Copyright (C) 2005 Stephen Hemminger <shemminger@osdl.org>
  7  */
  8 
  9 #define pr_fmt(fmt) "TCP: " fmt
 10 
 11 #include <linux/module.h>
 12 #include <linux/mm.h>
 13 #include <linux/types.h>
 14 #include <linux/list.h>
 15 #include <linux/gfp.h>
 16 #include <linux/jhash.h>
 17 #include <net/tcp.h>
 18 
 19 static DEFINE_SPINLOCK(tcp_cong_list_lock);
 20 static LIST_HEAD(tcp_cong_list);
 21 
 22 /* Simple linear search, don't expect many entries! */
 23 static struct tcp_congestion_ops *tcp_ca_find(const char *name)
 24 {
 25         struct tcp_congestion_ops *e;
 26 
 27         list_for_each_entry_rcu(e, &tcp_cong_list, list) {
 28                 if (strcmp(e->name, name) == 0)
 29                         return e;
 30         }
 31 
 32         return NULL;
 33 }
 34 
 35 /* Must be called with rcu lock held */
 36 static const struct tcp_congestion_ops *__tcp_ca_find_autoload(const char *name)
 37 {
 38         const struct tcp_congestion_ops *ca = tcp_ca_find(name);
 39 #ifdef CONFIG_MODULES
 40         if (!ca && capable(CAP_NET_ADMIN)) {
 41                 rcu_read_unlock();
 42                 request_module("tcp_%s", name);
 43                 rcu_read_lock();
 44                 ca = tcp_ca_find(name);
 45         }
 46 #endif
 47         return ca;
 48 }
 49 
 50 /* Simple linear search, not much in here. */
 51 struct tcp_congestion_ops *tcp_ca_find_key(u32 key)
 52 {
 53         struct tcp_congestion_ops *e;
 54 
 55         list_for_each_entry_rcu(e, &tcp_cong_list, list) {
 56                 if (e->key == key)
 57                         return e;
 58         }
 59 
 60         return NULL;
 61 }
 62 
 63 /*
 64  * Attach new congestion control algorithm to the list
 65  * of available options.
 66  */
 67 int tcp_register_congestion_control(struct tcp_congestion_ops *ca)
 68 {
 69         int ret = 0;
 70 
 71         /* all algorithms must implement ssthresh and cong_avoid ops */
 72         if (!ca->ssthresh || !ca->cong_avoid) {
 73                 pr_err("%s does not implement required ops\n", ca->name);
 74                 return -EINVAL;
 75         }
 76 
 77         ca->key = jhash(ca->name, sizeof(ca->name), strlen(ca->name));
 78 
 79         spin_lock(&tcp_cong_list_lock);
 80         if (ca->key == TCP_CA_UNSPEC || tcp_ca_find_key(ca->key)) {
 81                 pr_notice("%s already registered or non-unique key\n",
 82                           ca->name);
 83                 ret = -EEXIST;
 84         } else {
 85                 list_add_tail_rcu(&ca->list, &tcp_cong_list);
 86                 pr_debug("%s registered\n", ca->name);
 87         }
 88         spin_unlock(&tcp_cong_list_lock);
 89 
 90         return ret;
 91 }
 92 EXPORT_SYMBOL_GPL(tcp_register_congestion_control);
 93 
 94 /*
 95  * Remove congestion control algorithm, called from
 96  * the module's remove function.  Module ref counts are used
 97  * to ensure that this can't be done till all sockets using
 98  * that method are closed.
 99  */
100 void tcp_unregister_congestion_control(struct tcp_congestion_ops *ca)
101 {
102         spin_lock(&tcp_cong_list_lock);
103         list_del_rcu(&ca->list);
104         spin_unlock(&tcp_cong_list_lock);
105 
106         /* Wait for outstanding readers to complete before the
107          * module gets removed entirely.
108          *
109          * A try_module_get() should fail by now as our module is
110          * in "going" state since no refs are held anymore and
111          * module_exit() handler being called.
112          */
113         synchronize_rcu();
114 }
115 EXPORT_SYMBOL_GPL(tcp_unregister_congestion_control);
116 
117 u32 tcp_ca_get_key_by_name(const char *name, bool *ecn_ca)
118 {
119         const struct tcp_congestion_ops *ca;
120         u32 key = TCP_CA_UNSPEC;
121 
122         might_sleep();
123 
124         rcu_read_lock();
125         ca = __tcp_ca_find_autoload(name);
126         if (ca) {
127                 key = ca->key;
128                 *ecn_ca = ca->flags & TCP_CONG_NEEDS_ECN;
129         }
130         rcu_read_unlock();
131 
132         return key;
133 }
134 EXPORT_SYMBOL_GPL(tcp_ca_get_key_by_name);
135 
136 char *tcp_ca_get_name_by_key(u32 key, char *buffer)
137 {
138         const struct tcp_congestion_ops *ca;
139         char *ret = NULL;
140 
141         rcu_read_lock();
142         ca = tcp_ca_find_key(key);
143         if (ca)
144                 ret = strncpy(buffer, ca->name,
145                               TCP_CA_NAME_MAX);
146         rcu_read_unlock();
147 
148         return ret;
149 }
150 EXPORT_SYMBOL_GPL(tcp_ca_get_name_by_key);
151 
152 /* Assign choice of congestion control. */
153 void tcp_assign_congestion_control(struct sock *sk)
154 {
155         struct inet_connection_sock *icsk = inet_csk(sk);
156         struct tcp_congestion_ops *ca;
157 
158         rcu_read_lock();
159         list_for_each_entry_rcu(ca, &tcp_cong_list, list) {
160                 if (likely(try_module_get(ca->owner))) {
161                         icsk->icsk_ca_ops = ca;
162                         goto out;
163                 }
164                 /* Fallback to next available. The last really
165                  * guaranteed fallback is Reno from this list.
166                  */
167         }
168 out:
169         rcu_read_unlock();
170 
171         /* Clear out private data before diag gets it and
172          * the ca has not been initialized.
173          */
174         if (ca->get_info)
175                 memset(icsk->icsk_ca_priv, 0, sizeof(icsk->icsk_ca_priv));
176         if (ca->flags & TCP_CONG_NEEDS_ECN)
177                 INET_ECN_xmit(sk);
178         else
179                 INET_ECN_dontxmit(sk);
180 }
181 
182 void tcp_init_congestion_control(struct sock *sk)
183 {
184         const struct inet_connection_sock *icsk = inet_csk(sk);
185 
186         if (icsk->icsk_ca_ops->init)
187                 icsk->icsk_ca_ops->init(sk);
188         if (tcp_ca_needs_ecn(sk))
189                 INET_ECN_xmit(sk);
190         else
191                 INET_ECN_dontxmit(sk);
192 }
193 
194 static void tcp_reinit_congestion_control(struct sock *sk,
195                                           const struct tcp_congestion_ops *ca)
196 {
197         struct inet_connection_sock *icsk = inet_csk(sk);
198 
199         tcp_cleanup_congestion_control(sk);
200         icsk->icsk_ca_ops = ca;
201         icsk->icsk_ca_setsockopt = 1;
202 
203         if (sk->sk_state != TCP_CLOSE)
204                 tcp_init_congestion_control(sk);
205 }
206 
207 /* Manage refcounts on socket close. */
208 void tcp_cleanup_congestion_control(struct sock *sk)
209 {
210         struct inet_connection_sock *icsk = inet_csk(sk);
211 
212         if (icsk->icsk_ca_ops->release)
213                 icsk->icsk_ca_ops->release(sk);
214         module_put(icsk->icsk_ca_ops->owner);
215 }
216 
217 /* Used by sysctl to change default congestion control */
218 int tcp_set_default_congestion_control(const char *name)
219 {
220         struct tcp_congestion_ops *ca;
221         int ret = -ENOENT;
222 
223         spin_lock(&tcp_cong_list_lock);
224         ca = tcp_ca_find(name);
225 #ifdef CONFIG_MODULES
226         if (!ca && capable(CAP_NET_ADMIN)) {
227                 spin_unlock(&tcp_cong_list_lock);
228 
229                 request_module("tcp_%s", name);
230                 spin_lock(&tcp_cong_list_lock);
231                 ca = tcp_ca_find(name);
232         }
233 #endif
234 
235         if (ca) {
236                 ca->flags |= TCP_CONG_NON_RESTRICTED;   /* default is always allowed */
237                 list_move(&ca->list, &tcp_cong_list);
238                 ret = 0;
239         }
240         spin_unlock(&tcp_cong_list_lock);
241 
242         return ret;
243 }
244 
245 /* Set default value from kernel configuration at bootup */
246 static int __init tcp_congestion_default(void)
247 {
248         return tcp_set_default_congestion_control(CONFIG_DEFAULT_TCP_CONG);
249 }
250 late_initcall(tcp_congestion_default);
251 
252 /* Build string with list of available congestion control values */
253 void tcp_get_available_congestion_control(char *buf, size_t maxlen)
254 {
255         struct tcp_congestion_ops *ca;
256         size_t offs = 0;
257 
258         rcu_read_lock();
259         list_for_each_entry_rcu(ca, &tcp_cong_list, list) {
260                 offs += snprintf(buf + offs, maxlen - offs,
261                                  "%s%s",
262                                  offs == 0 ? "" : " ", ca->name);
263         }
264         rcu_read_unlock();
265 }
266 
267 /* Get current default congestion control */
268 void tcp_get_default_congestion_control(char *name)
269 {
270         struct tcp_congestion_ops *ca;
271         /* We will always have reno... */
272         BUG_ON(list_empty(&tcp_cong_list));
273 
274         rcu_read_lock();
275         ca = list_entry(tcp_cong_list.next, struct tcp_congestion_ops, list);
276         strncpy(name, ca->name, TCP_CA_NAME_MAX);
277         rcu_read_unlock();
278 }
279 
280 /* Built list of non-restricted congestion control values */
281 void tcp_get_allowed_congestion_control(char *buf, size_t maxlen)
282 {
283         struct tcp_congestion_ops *ca;
284         size_t offs = 0;
285 
286         *buf = '\0';
287         rcu_read_lock();
288         list_for_each_entry_rcu(ca, &tcp_cong_list, list) {
289                 if (!(ca->flags & TCP_CONG_NON_RESTRICTED))
290                         continue;
291                 offs += snprintf(buf + offs, maxlen - offs,
292                                  "%s%s",
293                                  offs == 0 ? "" : " ", ca->name);
294         }
295         rcu_read_unlock();
296 }
297 
298 /* Change list of non-restricted congestion control */
299 int tcp_set_allowed_congestion_control(char *val)
300 {
301         struct tcp_congestion_ops *ca;
302         char *saved_clone, *clone, *name;
303         int ret = 0;
304 
305         saved_clone = clone = kstrdup(val, GFP_USER);
306         if (!clone)
307                 return -ENOMEM;
308 
309         spin_lock(&tcp_cong_list_lock);
310         /* pass 1 check for bad entries */
311         while ((name = strsep(&clone, " ")) && *name) {
312                 ca = tcp_ca_find(name);
313                 if (!ca) {
314                         ret = -ENOENT;
315                         goto out;
316                 }
317         }
318 
319         /* pass 2 clear old values */
320         list_for_each_entry_rcu(ca, &tcp_cong_list, list)
321                 ca->flags &= ~TCP_CONG_NON_RESTRICTED;
322 
323         /* pass 3 mark as allowed */
324         while ((name = strsep(&val, " ")) && *name) {
325                 ca = tcp_ca_find(name);
326                 WARN_ON(!ca);
327                 if (ca)
328                         ca->flags |= TCP_CONG_NON_RESTRICTED;
329         }
330 out:
331         spin_unlock(&tcp_cong_list_lock);
332         kfree(saved_clone);
333 
334         return ret;
335 }
336 
337 /* Change congestion control for socket */
338 int tcp_set_congestion_control(struct sock *sk, const char *name)
339 {
340         struct inet_connection_sock *icsk = inet_csk(sk);
341         const struct tcp_congestion_ops *ca;
342         int err = 0;
343 
344         if (icsk->icsk_ca_dst_locked)
345                 return -EPERM;
346 
347         rcu_read_lock();
348         ca = __tcp_ca_find_autoload(name);
349         /* No change asking for existing value */
350         if (ca == icsk->icsk_ca_ops) {
351                 icsk->icsk_ca_setsockopt = 1;
352                 goto out;
353         }
354         if (!ca)
355                 err = -ENOENT;
356         else if (!((ca->flags & TCP_CONG_NON_RESTRICTED) ||
357                    ns_capable(sock_net(sk)->user_ns, CAP_NET_ADMIN)))
358                 err = -EPERM;
359         else if (!try_module_get(ca->owner))
360                 err = -EBUSY;
361         else
362                 tcp_reinit_congestion_control(sk, ca);
363  out:
364         rcu_read_unlock();
365         return err;
366 }
367 
368 /* Slow start is used when congestion window is no greater than the slow start
369  * threshold. We base on RFC2581 and also handle stretch ACKs properly.
370  * We do not implement RFC3465 Appropriate Byte Counting (ABC) per se but
371  * something better;) a packet is only considered (s)acked in its entirety to
372  * defend the ACK attacks described in the RFC. Slow start processes a stretch
373  * ACK of degree N as if N acks of degree 1 are received back to back except
374  * ABC caps N to 2. Slow start exits when cwnd grows over ssthresh and
375  * returns the leftover acks to adjust cwnd in congestion avoidance mode.
376  */
377 u32 tcp_slow_start(struct tcp_sock *tp, u32 acked)
378 {
379         u32 cwnd = min(tp->snd_cwnd + acked, tp->snd_ssthresh);
380 
381         acked -= cwnd - tp->snd_cwnd;
382         tp->snd_cwnd = min(cwnd, tp->snd_cwnd_clamp);
383 
384         return acked;
385 }
386 EXPORT_SYMBOL_GPL(tcp_slow_start);
387 
388 /* In theory this is tp->snd_cwnd += 1 / tp->snd_cwnd (or alternative w),
389  * for every packet that was ACKed.
390  */
391 void tcp_cong_avoid_ai(struct tcp_sock *tp, u32 w, u32 acked)
392 {
393         /* If credits accumulated at a higher w, apply them gently now. */
394         if (tp->snd_cwnd_cnt >= w) {
395                 tp->snd_cwnd_cnt = 0;
396                 tp->snd_cwnd++;
397         }
398 
399         tp->snd_cwnd_cnt += acked;
400         if (tp->snd_cwnd_cnt >= w) {
401                 u32 delta = tp->snd_cwnd_cnt / w;
402 
403                 tp->snd_cwnd_cnt -= delta * w;
404                 tp->snd_cwnd += delta;
405         }
406         tp->snd_cwnd = min(tp->snd_cwnd, tp->snd_cwnd_clamp);
407 }
408 EXPORT_SYMBOL_GPL(tcp_cong_avoid_ai);
409 
410 /*
411  * TCP Reno congestion control
412  * This is special case used for fallback as well.
413  */
414 /* This is Jacobson's slow start and congestion avoidance.
415  * SIGCOMM '88, p. 328.
416  */
417 void tcp_reno_cong_avoid(struct sock *sk, u32 ack, u32 acked)
418 {
419         struct tcp_sock *tp = tcp_sk(sk);
420 
421         if (!tcp_is_cwnd_limited(sk))
422                 return;
423 
424         /* In "safe" area, increase. */
425         if (tcp_in_slow_start(tp)) {
426                 acked = tcp_slow_start(tp, acked);
427                 if (!acked)
428                         return;
429         }
430         /* In dangerous area, increase slowly. */
431         tcp_cong_avoid_ai(tp, tp->snd_cwnd, acked);
432 }
433 EXPORT_SYMBOL_GPL(tcp_reno_cong_avoid);
434 
435 /* Slow start threshold is half the congestion window (min 2) */
436 u32 tcp_reno_ssthresh(struct sock *sk)
437 {
438         const struct tcp_sock *tp = tcp_sk(sk);
439 
440         return max(tp->snd_cwnd >> 1U, 2U);
441 }
442 EXPORT_SYMBOL_GPL(tcp_reno_ssthresh);
443 
444 struct tcp_congestion_ops tcp_reno = {
445         .flags          = TCP_CONG_NON_RESTRICTED,
446         .name           = "reno",
447         .owner          = THIS_MODULE,
448         .ssthresh       = tcp_reno_ssthresh,
449         .cong_avoid     = tcp_reno_cong_avoid,
450 };
451 

~ [ source navigation ] ~ [ diff markup ] ~ [ identifier search ] ~

kernel.org | git.kernel.org | LWN.net | Project Home | Wiki (Japanese) | Wiki (English) | SVN repository | Mail admin

Linux® is a registered trademark of Linus Torvalds in the United States and other countries.
TOMOYO® is a registered trademark of NTT DATA CORPORATION.

osdn.jp