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

TOMOYO Linux Cross Reference
Linux/net/sched/sch_red.c

Version: ~ [ linux-5.15-rc7 ] ~ [ linux-5.14.14 ] ~ [ linux-5.13.19 ] ~ [ linux-5.12.19 ] ~ [ linux-5.11.22 ] ~ [ linux-5.10.75 ] ~ [ linux-5.9.16 ] ~ [ linux-5.8.18 ] ~ [ linux-5.7.19 ] ~ [ linux-5.6.19 ] ~ [ linux-5.5.19 ] ~ [ linux-5.4.155 ] ~ [ linux-5.3.18 ] ~ [ linux-5.2.21 ] ~ [ linux-5.1.21 ] ~ [ linux-5.0.21 ] ~ [ linux-4.20.17 ] ~ [ linux-4.19.213 ] ~ [ linux-4.18.20 ] ~ [ linux-4.17.19 ] ~ [ linux-4.16.18 ] ~ [ linux-4.15.18 ] ~ [ linux-4.14.252 ] ~ [ linux-4.13.16 ] ~ [ linux-4.12.14 ] ~ [ linux-4.11.12 ] ~ [ linux-4.10.17 ] ~ [ linux-4.9.287 ] ~ [ linux-4.8.17 ] ~ [ linux-4.7.10 ] ~ [ linux-4.6.7 ] ~ [ linux-4.5.7 ] ~ [ linux-4.4.289 ] ~ [ linux-4.3.6 ] ~ [ linux-4.2.8 ] ~ [ linux-4.1.52 ] ~ [ linux-4.0.9 ] ~ [ linux-3.18.140 ] ~ [ linux-3.16.85 ] ~ [ linux-3.14.79 ] ~ [ linux-3.12.74 ] ~ [ 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 // SPDX-License-Identifier: GPL-2.0-or-later
  2 /*
  3  * net/sched/sch_red.c  Random Early Detection queue.
  4  *
  5  * Authors:     Alexey Kuznetsov, <kuznet@ms2.inr.ac.ru>
  6  *
  7  * Changes:
  8  * J Hadi Salim 980914: computation fixes
  9  * Alexey Makarenko <makar@phoenix.kharkov.ua> 990814: qave on idle link was calculated incorrectly.
 10  * J Hadi Salim 980816:  ECN support
 11  */
 12 
 13 #include <linux/module.h>
 14 #include <linux/types.h>
 15 #include <linux/kernel.h>
 16 #include <linux/skbuff.h>
 17 #include <net/pkt_sched.h>
 18 #include <net/pkt_cls.h>
 19 #include <net/inet_ecn.h>
 20 #include <net/red.h>
 21 
 22 
 23 /*      Parameters, settable by user:
 24         -----------------------------
 25 
 26         limit           - bytes (must be > qth_max + burst)
 27 
 28         Hard limit on queue length, should be chosen >qth_max
 29         to allow packet bursts. This parameter does not
 30         affect the algorithms behaviour and can be chosen
 31         arbitrarily high (well, less than ram size)
 32         Really, this limit will never be reached
 33         if RED works correctly.
 34  */
 35 
 36 struct red_sched_data {
 37         u32                     limit;          /* HARD maximal queue length */
 38         unsigned char           flags;
 39         struct timer_list       adapt_timer;
 40         struct Qdisc            *sch;
 41         struct red_parms        parms;
 42         struct red_vars         vars;
 43         struct red_stats        stats;
 44         struct Qdisc            *qdisc;
 45 };
 46 
 47 static inline int red_use_ecn(struct red_sched_data *q)
 48 {
 49         return q->flags & TC_RED_ECN;
 50 }
 51 
 52 static inline int red_use_harddrop(struct red_sched_data *q)
 53 {
 54         return q->flags & TC_RED_HARDDROP;
 55 }
 56 
 57 static int red_enqueue(struct sk_buff *skb, struct Qdisc *sch,
 58                        struct sk_buff **to_free)
 59 {
 60         struct red_sched_data *q = qdisc_priv(sch);
 61         struct Qdisc *child = q->qdisc;
 62         int ret;
 63 
 64         q->vars.qavg = red_calc_qavg(&q->parms,
 65                                      &q->vars,
 66                                      child->qstats.backlog);
 67 
 68         if (red_is_idling(&q->vars))
 69                 red_end_of_idle_period(&q->vars);
 70 
 71         switch (red_action(&q->parms, &q->vars, q->vars.qavg)) {
 72         case RED_DONT_MARK:
 73                 break;
 74 
 75         case RED_PROB_MARK:
 76                 qdisc_qstats_overlimit(sch);
 77                 if (!red_use_ecn(q) || !INET_ECN_set_ce(skb)) {
 78                         q->stats.prob_drop++;
 79                         goto congestion_drop;
 80                 }
 81 
 82                 q->stats.prob_mark++;
 83                 break;
 84 
 85         case RED_HARD_MARK:
 86                 qdisc_qstats_overlimit(sch);
 87                 if (red_use_harddrop(q) || !red_use_ecn(q) ||
 88                     !INET_ECN_set_ce(skb)) {
 89                         q->stats.forced_drop++;
 90                         goto congestion_drop;
 91                 }
 92 
 93                 q->stats.forced_mark++;
 94                 break;
 95         }
 96 
 97         ret = qdisc_enqueue(skb, child, to_free);
 98         if (likely(ret == NET_XMIT_SUCCESS)) {
 99                 qdisc_qstats_backlog_inc(sch, skb);
100                 sch->q.qlen++;
101         } else if (net_xmit_drop_count(ret)) {
102                 q->stats.pdrop++;
103                 qdisc_qstats_drop(sch);
104         }
105         return ret;
106 
107 congestion_drop:
108         qdisc_drop(skb, sch, to_free);
109         return NET_XMIT_CN;
110 }
111 
112 static struct sk_buff *red_dequeue(struct Qdisc *sch)
113 {
114         struct sk_buff *skb;
115         struct red_sched_data *q = qdisc_priv(sch);
116         struct Qdisc *child = q->qdisc;
117 
118         skb = child->dequeue(child);
119         if (skb) {
120                 qdisc_bstats_update(sch, skb);
121                 qdisc_qstats_backlog_dec(sch, skb);
122                 sch->q.qlen--;
123         } else {
124                 if (!red_is_idling(&q->vars))
125                         red_start_of_idle_period(&q->vars);
126         }
127         return skb;
128 }
129 
130 static struct sk_buff *red_peek(struct Qdisc *sch)
131 {
132         struct red_sched_data *q = qdisc_priv(sch);
133         struct Qdisc *child = q->qdisc;
134 
135         return child->ops->peek(child);
136 }
137 
138 static void red_reset(struct Qdisc *sch)
139 {
140         struct red_sched_data *q = qdisc_priv(sch);
141 
142         qdisc_reset(q->qdisc);
143         sch->qstats.backlog = 0;
144         sch->q.qlen = 0;
145         red_restart(&q->vars);
146 }
147 
148 static int red_offload(struct Qdisc *sch, bool enable)
149 {
150         struct red_sched_data *q = qdisc_priv(sch);
151         struct net_device *dev = qdisc_dev(sch);
152         struct tc_red_qopt_offload opt = {
153                 .handle = sch->handle,
154                 .parent = sch->parent,
155         };
156 
157         if (!tc_can_offload(dev) || !dev->netdev_ops->ndo_setup_tc)
158                 return -EOPNOTSUPP;
159 
160         if (enable) {
161                 opt.command = TC_RED_REPLACE;
162                 opt.set.min = q->parms.qth_min >> q->parms.Wlog;
163                 opt.set.max = q->parms.qth_max >> q->parms.Wlog;
164                 opt.set.probability = q->parms.max_P;
165                 opt.set.limit = q->limit;
166                 opt.set.is_ecn = red_use_ecn(q);
167                 opt.set.is_harddrop = red_use_harddrop(q);
168                 opt.set.qstats = &sch->qstats;
169         } else {
170                 opt.command = TC_RED_DESTROY;
171         }
172 
173         return dev->netdev_ops->ndo_setup_tc(dev, TC_SETUP_QDISC_RED, &opt);
174 }
175 
176 static void red_destroy(struct Qdisc *sch)
177 {
178         struct red_sched_data *q = qdisc_priv(sch);
179 
180         del_timer_sync(&q->adapt_timer);
181         red_offload(sch, false);
182         qdisc_put(q->qdisc);
183 }
184 
185 static const struct nla_policy red_policy[TCA_RED_MAX + 1] = {
186         [TCA_RED_PARMS] = { .len = sizeof(struct tc_red_qopt) },
187         [TCA_RED_STAB]  = { .len = RED_STAB_SIZE },
188         [TCA_RED_MAX_P] = { .type = NLA_U32 },
189 };
190 
191 static int red_change(struct Qdisc *sch, struct nlattr *opt,
192                       struct netlink_ext_ack *extack)
193 {
194         struct Qdisc *old_child = NULL, *child = NULL;
195         struct red_sched_data *q = qdisc_priv(sch);
196         struct nlattr *tb[TCA_RED_MAX + 1];
197         struct tc_red_qopt *ctl;
198         int err;
199         u32 max_P;
200 
201         if (opt == NULL)
202                 return -EINVAL;
203 
204         err = nla_parse_nested_deprecated(tb, TCA_RED_MAX, opt, red_policy,
205                                           NULL);
206         if (err < 0)
207                 return err;
208 
209         if (tb[TCA_RED_PARMS] == NULL ||
210             tb[TCA_RED_STAB] == NULL)
211                 return -EINVAL;
212 
213         max_P = tb[TCA_RED_MAX_P] ? nla_get_u32(tb[TCA_RED_MAX_P]) : 0;
214 
215         ctl = nla_data(tb[TCA_RED_PARMS]);
216         if (!red_check_params(ctl->qth_min, ctl->qth_max, ctl->Wlog))
217                 return -EINVAL;
218 
219         if (ctl->limit > 0) {
220                 child = fifo_create_dflt(sch, &bfifo_qdisc_ops, ctl->limit,
221                                          extack);
222                 if (IS_ERR(child))
223                         return PTR_ERR(child);
224 
225                 /* child is fifo, no need to check for noop_qdisc */
226                 qdisc_hash_add(child, true);
227         }
228 
229         sch_tree_lock(sch);
230         q->flags = ctl->flags;
231         q->limit = ctl->limit;
232         if (child) {
233                 qdisc_tree_flush_backlog(q->qdisc);
234                 old_child = q->qdisc;
235                 q->qdisc = child;
236         }
237 
238         red_set_parms(&q->parms,
239                       ctl->qth_min, ctl->qth_max, ctl->Wlog,
240                       ctl->Plog, ctl->Scell_log,
241                       nla_data(tb[TCA_RED_STAB]),
242                       max_P);
243         red_set_vars(&q->vars);
244 
245         del_timer(&q->adapt_timer);
246         if (ctl->flags & TC_RED_ADAPTATIVE)
247                 mod_timer(&q->adapt_timer, jiffies + HZ/2);
248 
249         if (!q->qdisc->q.qlen)
250                 red_start_of_idle_period(&q->vars);
251 
252         sch_tree_unlock(sch);
253 
254         red_offload(sch, true);
255 
256         if (old_child)
257                 qdisc_put(old_child);
258         return 0;
259 }
260 
261 static inline void red_adaptative_timer(struct timer_list *t)
262 {
263         struct red_sched_data *q = from_timer(q, t, adapt_timer);
264         struct Qdisc *sch = q->sch;
265         spinlock_t *root_lock = qdisc_lock(qdisc_root_sleeping(sch));
266 
267         spin_lock(root_lock);
268         red_adaptative_algo(&q->parms, &q->vars);
269         mod_timer(&q->adapt_timer, jiffies + HZ/2);
270         spin_unlock(root_lock);
271 }
272 
273 static int red_init(struct Qdisc *sch, struct nlattr *opt,
274                     struct netlink_ext_ack *extack)
275 {
276         struct red_sched_data *q = qdisc_priv(sch);
277 
278         q->qdisc = &noop_qdisc;
279         q->sch = sch;
280         timer_setup(&q->adapt_timer, red_adaptative_timer, 0);
281         return red_change(sch, opt, extack);
282 }
283 
284 static int red_dump_offload_stats(struct Qdisc *sch)
285 {
286         struct tc_red_qopt_offload hw_stats = {
287                 .command = TC_RED_STATS,
288                 .handle = sch->handle,
289                 .parent = sch->parent,
290                 {
291                         .stats.bstats = &sch->bstats,
292                         .stats.qstats = &sch->qstats,
293                 },
294         };
295 
296         return qdisc_offload_dump_helper(sch, TC_SETUP_QDISC_RED, &hw_stats);
297 }
298 
299 static int red_dump(struct Qdisc *sch, struct sk_buff *skb)
300 {
301         struct red_sched_data *q = qdisc_priv(sch);
302         struct nlattr *opts = NULL;
303         struct tc_red_qopt opt = {
304                 .limit          = q->limit,
305                 .flags          = q->flags,
306                 .qth_min        = q->parms.qth_min >> q->parms.Wlog,
307                 .qth_max        = q->parms.qth_max >> q->parms.Wlog,
308                 .Wlog           = q->parms.Wlog,
309                 .Plog           = q->parms.Plog,
310                 .Scell_log      = q->parms.Scell_log,
311         };
312         int err;
313 
314         err = red_dump_offload_stats(sch);
315         if (err)
316                 goto nla_put_failure;
317 
318         opts = nla_nest_start_noflag(skb, TCA_OPTIONS);
319         if (opts == NULL)
320                 goto nla_put_failure;
321         if (nla_put(skb, TCA_RED_PARMS, sizeof(opt), &opt) ||
322             nla_put_u32(skb, TCA_RED_MAX_P, q->parms.max_P))
323                 goto nla_put_failure;
324         return nla_nest_end(skb, opts);
325 
326 nla_put_failure:
327         nla_nest_cancel(skb, opts);
328         return -EMSGSIZE;
329 }
330 
331 static int red_dump_stats(struct Qdisc *sch, struct gnet_dump *d)
332 {
333         struct red_sched_data *q = qdisc_priv(sch);
334         struct net_device *dev = qdisc_dev(sch);
335         struct tc_red_xstats st = {0};
336 
337         if (sch->flags & TCQ_F_OFFLOADED) {
338                 struct tc_red_qopt_offload hw_stats_request = {
339                         .command = TC_RED_XSTATS,
340                         .handle = sch->handle,
341                         .parent = sch->parent,
342                         {
343                                 .xstats = &q->stats,
344                         },
345                 };
346                 dev->netdev_ops->ndo_setup_tc(dev, TC_SETUP_QDISC_RED,
347                                               &hw_stats_request);
348         }
349         st.early = q->stats.prob_drop + q->stats.forced_drop;
350         st.pdrop = q->stats.pdrop;
351         st.other = q->stats.other;
352         st.marked = q->stats.prob_mark + q->stats.forced_mark;
353 
354         return gnet_stats_copy_app(d, &st, sizeof(st));
355 }
356 
357 static int red_dump_class(struct Qdisc *sch, unsigned long cl,
358                           struct sk_buff *skb, struct tcmsg *tcm)
359 {
360         struct red_sched_data *q = qdisc_priv(sch);
361 
362         tcm->tcm_handle |= TC_H_MIN(1);
363         tcm->tcm_info = q->qdisc->handle;
364         return 0;
365 }
366 
367 static void red_graft_offload(struct Qdisc *sch,
368                               struct Qdisc *new, struct Qdisc *old,
369                               struct netlink_ext_ack *extack)
370 {
371         struct tc_red_qopt_offload graft_offload = {
372                 .handle         = sch->handle,
373                 .parent         = sch->parent,
374                 .child_handle   = new->handle,
375                 .command        = TC_RED_GRAFT,
376         };
377 
378         qdisc_offload_graft_helper(qdisc_dev(sch), sch, new, old,
379                                    TC_SETUP_QDISC_RED, &graft_offload, extack);
380 }
381 
382 static int red_graft(struct Qdisc *sch, unsigned long arg, struct Qdisc *new,
383                      struct Qdisc **old, struct netlink_ext_ack *extack)
384 {
385         struct red_sched_data *q = qdisc_priv(sch);
386 
387         if (new == NULL)
388                 new = &noop_qdisc;
389 
390         *old = qdisc_replace(sch, new, &q->qdisc);
391 
392         red_graft_offload(sch, new, *old, extack);
393         return 0;
394 }
395 
396 static struct Qdisc *red_leaf(struct Qdisc *sch, unsigned long arg)
397 {
398         struct red_sched_data *q = qdisc_priv(sch);
399         return q->qdisc;
400 }
401 
402 static unsigned long red_find(struct Qdisc *sch, u32 classid)
403 {
404         return 1;
405 }
406 
407 static void red_walk(struct Qdisc *sch, struct qdisc_walker *walker)
408 {
409         if (!walker->stop) {
410                 if (walker->count >= walker->skip)
411                         if (walker->fn(sch, 1, walker) < 0) {
412                                 walker->stop = 1;
413                                 return;
414                         }
415                 walker->count++;
416         }
417 }
418 
419 static const struct Qdisc_class_ops red_class_ops = {
420         .graft          =       red_graft,
421         .leaf           =       red_leaf,
422         .find           =       red_find,
423         .walk           =       red_walk,
424         .dump           =       red_dump_class,
425 };
426 
427 static struct Qdisc_ops red_qdisc_ops __read_mostly = {
428         .id             =       "red",
429         .priv_size      =       sizeof(struct red_sched_data),
430         .cl_ops         =       &red_class_ops,
431         .enqueue        =       red_enqueue,
432         .dequeue        =       red_dequeue,
433         .peek           =       red_peek,
434         .init           =       red_init,
435         .reset          =       red_reset,
436         .destroy        =       red_destroy,
437         .change         =       red_change,
438         .dump           =       red_dump,
439         .dump_stats     =       red_dump_stats,
440         .owner          =       THIS_MODULE,
441 };
442 
443 static int __init red_module_init(void)
444 {
445         return register_qdisc(&red_qdisc_ops);
446 }
447 
448 static void __exit red_module_exit(void)
449 {
450         unregister_qdisc(&red_qdisc_ops);
451 }
452 
453 module_init(red_module_init)
454 module_exit(red_module_exit)
455 
456 MODULE_LICENSE("GPL");
457 

~ [ 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