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

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

Version: ~ [ linux-5.10-rc1 ] ~ [ linux-5.9.1 ] ~ [ linux-5.8.16 ] ~ [ linux-5.7.19 ] ~ [ linux-5.6.19 ] ~ [ linux-5.5.19 ] ~ [ linux-5.4.72 ] ~ [ linux-5.3.18 ] ~ [ linux-5.2.21 ] ~ [ linux-5.1.21 ] ~ [ linux-5.0.21 ] ~ [ linux-4.20.17 ] ~ [ linux-4.19.152 ] ~ [ linux-4.18.20 ] ~ [ linux-4.17.19 ] ~ [ linux-4.16.18 ] ~ [ linux-4.15.18 ] ~ [ linux-4.14.202 ] ~ [ linux-4.13.16 ] ~ [ linux-4.12.14 ] ~ [ linux-4.11.12 ] ~ [ linux-4.10.17 ] ~ [ linux-4.9.240 ] ~ [ linux-4.8.17 ] ~ [ linux-4.7.10 ] ~ [ linux-4.6.7 ] ~ [ linux-4.5.7 ] ~ [ linux-4.4.240 ] ~ [ 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  * net/sched/sch_api.c  Packet scheduler API.
  3  *
  4  *              This program is free software; you can redistribute it and/or
  5  *              modify it under the terms of the GNU General Public License
  6  *              as published by the Free Software Foundation; either version
  7  *              2 of the License, or (at your option) any later version.
  8  *
  9  * Authors:     Alexey Kuznetsov, <kuznet@ms2.inr.ac.ru>
 10  *
 11  * Fixes:
 12  *
 13  * Rani Assaf <rani@magic.metawire.com> :980802: JIFFIES and CPU clock sources are repaired.
 14  * Eduardo J. Blanco <ejbs@netlabs.com.uy> :990222: kmod support
 15  * Jamal Hadi Salim <hadi@nortelnetworks.com>: 990601: ingress support
 16  */
 17 
 18 #include <linux/module.h>
 19 #include <linux/types.h>
 20 #include <linux/kernel.h>
 21 #include <linux/string.h>
 22 #include <linux/errno.h>
 23 #include <linux/skbuff.h>
 24 #include <linux/init.h>
 25 #include <linux/proc_fs.h>
 26 #include <linux/seq_file.h>
 27 #include <linux/kmod.h>
 28 #include <linux/list.h>
 29 #include <linux/hrtimer.h>
 30 #include <linux/slab.h>
 31 #include <linux/hashtable.h>
 32 
 33 #include <net/net_namespace.h>
 34 #include <net/sock.h>
 35 #include <net/netlink.h>
 36 #include <net/pkt_sched.h>
 37 #include <net/pkt_cls.h>
 38 
 39 /*
 40 
 41    Short review.
 42    -------------
 43 
 44    This file consists of two interrelated parts:
 45 
 46    1. queueing disciplines manager frontend.
 47    2. traffic classes manager frontend.
 48 
 49    Generally, queueing discipline ("qdisc") is a black box,
 50    which is able to enqueue packets and to dequeue them (when
 51    device is ready to send something) in order and at times
 52    determined by algorithm hidden in it.
 53 
 54    qdisc's are divided to two categories:
 55    - "queues", which have no internal structure visible from outside.
 56    - "schedulers", which split all the packets to "traffic classes",
 57      using "packet classifiers" (look at cls_api.c)
 58 
 59    In turn, classes may have child qdiscs (as rule, queues)
 60    attached to them etc. etc. etc.
 61 
 62    The goal of the routines in this file is to translate
 63    information supplied by user in the form of handles
 64    to more intelligible for kernel form, to make some sanity
 65    checks and part of work, which is common to all qdiscs
 66    and to provide rtnetlink notifications.
 67 
 68    All real intelligent work is done inside qdisc modules.
 69 
 70 
 71 
 72    Every discipline has two major routines: enqueue and dequeue.
 73 
 74    ---dequeue
 75 
 76    dequeue usually returns a skb to send. It is allowed to return NULL,
 77    but it does not mean that queue is empty, it just means that
 78    discipline does not want to send anything this time.
 79    Queue is really empty if q->q.qlen == 0.
 80    For complicated disciplines with multiple queues q->q is not
 81    real packet queue, but however q->q.qlen must be valid.
 82 
 83    ---enqueue
 84 
 85    enqueue returns 0, if packet was enqueued successfully.
 86    If packet (this one or another one) was dropped, it returns
 87    not zero error code.
 88    NET_XMIT_DROP        - this packet dropped
 89      Expected action: do not backoff, but wait until queue will clear.
 90    NET_XMIT_CN          - probably this packet enqueued, but another one dropped.
 91      Expected action: backoff or ignore
 92 
 93    Auxiliary routines:
 94 
 95    ---peek
 96 
 97    like dequeue but without removing a packet from the queue
 98 
 99    ---reset
100 
101    returns qdisc to initial state: purge all buffers, clear all
102    timers, counters (except for statistics) etc.
103 
104    ---init
105 
106    initializes newly created qdisc.
107 
108    ---destroy
109 
110    destroys resources allocated by init and during lifetime of qdisc.
111 
112    ---change
113 
114    changes qdisc parameters.
115  */
116 
117 /* Protects list of registered TC modules. It is pure SMP lock. */
118 static DEFINE_RWLOCK(qdisc_mod_lock);
119 
120 
121 /************************************************
122  *      Queueing disciplines manipulation.      *
123  ************************************************/
124 
125 
126 /* The list of all installed queueing disciplines. */
127 
128 static struct Qdisc_ops *qdisc_base;
129 
130 /* Register/unregister queueing discipline */
131 
132 int register_qdisc(struct Qdisc_ops *qops)
133 {
134         struct Qdisc_ops *q, **qp;
135         int rc = -EEXIST;
136 
137         write_lock(&qdisc_mod_lock);
138         for (qp = &qdisc_base; (q = *qp) != NULL; qp = &q->next)
139                 if (!strcmp(qops->id, q->id))
140                         goto out;
141 
142         if (qops->enqueue == NULL)
143                 qops->enqueue = noop_qdisc_ops.enqueue;
144         if (qops->peek == NULL) {
145                 if (qops->dequeue == NULL)
146                         qops->peek = noop_qdisc_ops.peek;
147                 else
148                         goto out_einval;
149         }
150         if (qops->dequeue == NULL)
151                 qops->dequeue = noop_qdisc_ops.dequeue;
152 
153         if (qops->cl_ops) {
154                 const struct Qdisc_class_ops *cops = qops->cl_ops;
155 
156                 if (!(cops->find && cops->walk && cops->leaf))
157                         goto out_einval;
158 
159                 if (cops->tcf_block && !(cops->bind_tcf && cops->unbind_tcf))
160                         goto out_einval;
161         }
162 
163         qops->next = NULL;
164         *qp = qops;
165         rc = 0;
166 out:
167         write_unlock(&qdisc_mod_lock);
168         return rc;
169 
170 out_einval:
171         rc = -EINVAL;
172         goto out;
173 }
174 EXPORT_SYMBOL(register_qdisc);
175 
176 int unregister_qdisc(struct Qdisc_ops *qops)
177 {
178         struct Qdisc_ops *q, **qp;
179         int err = -ENOENT;
180 
181         write_lock(&qdisc_mod_lock);
182         for (qp = &qdisc_base; (q = *qp) != NULL; qp = &q->next)
183                 if (q == qops)
184                         break;
185         if (q) {
186                 *qp = q->next;
187                 q->next = NULL;
188                 err = 0;
189         }
190         write_unlock(&qdisc_mod_lock);
191         return err;
192 }
193 EXPORT_SYMBOL(unregister_qdisc);
194 
195 /* Get default qdisc if not otherwise specified */
196 void qdisc_get_default(char *name, size_t len)
197 {
198         read_lock(&qdisc_mod_lock);
199         strlcpy(name, default_qdisc_ops->id, len);
200         read_unlock(&qdisc_mod_lock);
201 }
202 
203 static struct Qdisc_ops *qdisc_lookup_default(const char *name)
204 {
205         struct Qdisc_ops *q = NULL;
206 
207         for (q = qdisc_base; q; q = q->next) {
208                 if (!strcmp(name, q->id)) {
209                         if (!try_module_get(q->owner))
210                                 q = NULL;
211                         break;
212                 }
213         }
214 
215         return q;
216 }
217 
218 /* Set new default qdisc to use */
219 int qdisc_set_default(const char *name)
220 {
221         const struct Qdisc_ops *ops;
222 
223         if (!capable(CAP_NET_ADMIN))
224                 return -EPERM;
225 
226         write_lock(&qdisc_mod_lock);
227         ops = qdisc_lookup_default(name);
228         if (!ops) {
229                 /* Not found, drop lock and try to load module */
230                 write_unlock(&qdisc_mod_lock);
231                 request_module("sch_%s", name);
232                 write_lock(&qdisc_mod_lock);
233 
234                 ops = qdisc_lookup_default(name);
235         }
236 
237         if (ops) {
238                 /* Set new default */
239                 module_put(default_qdisc_ops->owner);
240                 default_qdisc_ops = ops;
241         }
242         write_unlock(&qdisc_mod_lock);
243 
244         return ops ? 0 : -ENOENT;
245 }
246 
247 #ifdef CONFIG_NET_SCH_DEFAULT
248 /* Set default value from kernel config */
249 static int __init sch_default_qdisc(void)
250 {
251         return qdisc_set_default(CONFIG_DEFAULT_NET_SCH);
252 }
253 late_initcall(sch_default_qdisc);
254 #endif
255 
256 /* We know handle. Find qdisc among all qdisc's attached to device
257  * (root qdisc, all its children, children of children etc.)
258  * Note: caller either uses rtnl or rcu_read_lock()
259  */
260 
261 static struct Qdisc *qdisc_match_from_root(struct Qdisc *root, u32 handle)
262 {
263         struct Qdisc *q;
264 
265         if (!qdisc_dev(root))
266                 return (root->handle == handle ? root : NULL);
267 
268         if (!(root->flags & TCQ_F_BUILTIN) &&
269             root->handle == handle)
270                 return root;
271 
272         hash_for_each_possible_rcu(qdisc_dev(root)->qdisc_hash, q, hash, handle) {
273                 if (q->handle == handle)
274                         return q;
275         }
276         return NULL;
277 }
278 
279 void qdisc_hash_add(struct Qdisc *q, bool invisible)
280 {
281         if ((q->parent != TC_H_ROOT) && !(q->flags & TCQ_F_INGRESS)) {
282                 ASSERT_RTNL();
283                 hash_add_rcu(qdisc_dev(q)->qdisc_hash, &q->hash, q->handle);
284                 if (invisible)
285                         q->flags |= TCQ_F_INVISIBLE;
286         }
287 }
288 EXPORT_SYMBOL(qdisc_hash_add);
289 
290 void qdisc_hash_del(struct Qdisc *q)
291 {
292         if ((q->parent != TC_H_ROOT) && !(q->flags & TCQ_F_INGRESS)) {
293                 ASSERT_RTNL();
294                 hash_del_rcu(&q->hash);
295         }
296 }
297 EXPORT_SYMBOL(qdisc_hash_del);
298 
299 struct Qdisc *qdisc_lookup(struct net_device *dev, u32 handle)
300 {
301         struct Qdisc *q;
302 
303         if (!handle)
304                 return NULL;
305         q = qdisc_match_from_root(dev->qdisc, handle);
306         if (q)
307                 goto out;
308 
309         if (dev_ingress_queue(dev))
310                 q = qdisc_match_from_root(
311                         dev_ingress_queue(dev)->qdisc_sleeping,
312                         handle);
313 out:
314         return q;
315 }
316 
317 struct Qdisc *qdisc_lookup_rcu(struct net_device *dev, u32 handle)
318 {
319         struct netdev_queue *nq;
320         struct Qdisc *q;
321 
322         if (!handle)
323                 return NULL;
324         q = qdisc_match_from_root(dev->qdisc, handle);
325         if (q)
326                 goto out;
327 
328         nq = dev_ingress_queue_rcu(dev);
329         if (nq)
330                 q = qdisc_match_from_root(nq->qdisc_sleeping, handle);
331 out:
332         return q;
333 }
334 
335 static struct Qdisc *qdisc_leaf(struct Qdisc *p, u32 classid)
336 {
337         unsigned long cl;
338         struct Qdisc *leaf;
339         const struct Qdisc_class_ops *cops = p->ops->cl_ops;
340 
341         if (cops == NULL)
342                 return NULL;
343         cl = cops->find(p, classid);
344 
345         if (cl == 0)
346                 return NULL;
347         leaf = cops->leaf(p, cl);
348         return leaf;
349 }
350 
351 /* Find queueing discipline by name */
352 
353 static struct Qdisc_ops *qdisc_lookup_ops(struct nlattr *kind)
354 {
355         struct Qdisc_ops *q = NULL;
356 
357         if (kind) {
358                 read_lock(&qdisc_mod_lock);
359                 for (q = qdisc_base; q; q = q->next) {
360                         if (nla_strcmp(kind, q->id) == 0) {
361                                 if (!try_module_get(q->owner))
362                                         q = NULL;
363                                 break;
364                         }
365                 }
366                 read_unlock(&qdisc_mod_lock);
367         }
368         return q;
369 }
370 
371 /* The linklayer setting were not transferred from iproute2, in older
372  * versions, and the rate tables lookup systems have been dropped in
373  * the kernel. To keep backward compatible with older iproute2 tc
374  * utils, we detect the linklayer setting by detecting if the rate
375  * table were modified.
376  *
377  * For linklayer ATM table entries, the rate table will be aligned to
378  * 48 bytes, thus some table entries will contain the same value.  The
379  * mpu (min packet unit) is also encoded into the old rate table, thus
380  * starting from the mpu, we find low and high table entries for
381  * mapping this cell.  If these entries contain the same value, when
382  * the rate tables have been modified for linklayer ATM.
383  *
384  * This is done by rounding mpu to the nearest 48 bytes cell/entry,
385  * and then roundup to the next cell, calc the table entry one below,
386  * and compare.
387  */
388 static __u8 __detect_linklayer(struct tc_ratespec *r, __u32 *rtab)
389 {
390         int low       = roundup(r->mpu, 48);
391         int high      = roundup(low+1, 48);
392         int cell_low  = low >> r->cell_log;
393         int cell_high = (high >> r->cell_log) - 1;
394 
395         /* rtab is too inaccurate at rates > 100Mbit/s */
396         if ((r->rate > (100000000/8)) || (rtab[0] == 0)) {
397                 pr_debug("TC linklayer: Giving up ATM detection\n");
398                 return TC_LINKLAYER_ETHERNET;
399         }
400 
401         if ((cell_high > cell_low) && (cell_high < 256)
402             && (rtab[cell_low] == rtab[cell_high])) {
403                 pr_debug("TC linklayer: Detected ATM, low(%d)=high(%d)=%u\n",
404                          cell_low, cell_high, rtab[cell_high]);
405                 return TC_LINKLAYER_ATM;
406         }
407         return TC_LINKLAYER_ETHERNET;
408 }
409 
410 static struct qdisc_rate_table *qdisc_rtab_list;
411 
412 struct qdisc_rate_table *qdisc_get_rtab(struct tc_ratespec *r,
413                                         struct nlattr *tab,
414                                         struct netlink_ext_ack *extack)
415 {
416         struct qdisc_rate_table *rtab;
417 
418         if (tab == NULL || r->rate == 0 || r->cell_log == 0 ||
419             nla_len(tab) != TC_RTAB_SIZE) {
420                 NL_SET_ERR_MSG(extack, "Invalid rate table parameters for searching");
421                 return NULL;
422         }
423 
424         for (rtab = qdisc_rtab_list; rtab; rtab = rtab->next) {
425                 if (!memcmp(&rtab->rate, r, sizeof(struct tc_ratespec)) &&
426                     !memcmp(&rtab->data, nla_data(tab), 1024)) {
427                         rtab->refcnt++;
428                         return rtab;
429                 }
430         }
431 
432         rtab = kmalloc(sizeof(*rtab), GFP_KERNEL);
433         if (rtab) {
434                 rtab->rate = *r;
435                 rtab->refcnt = 1;
436                 memcpy(rtab->data, nla_data(tab), 1024);
437                 if (r->linklayer == TC_LINKLAYER_UNAWARE)
438                         r->linklayer = __detect_linklayer(r, rtab->data);
439                 rtab->next = qdisc_rtab_list;
440                 qdisc_rtab_list = rtab;
441         } else {
442                 NL_SET_ERR_MSG(extack, "Failed to allocate new qdisc rate table");
443         }
444         return rtab;
445 }
446 EXPORT_SYMBOL(qdisc_get_rtab);
447 
448 void qdisc_put_rtab(struct qdisc_rate_table *tab)
449 {
450         struct qdisc_rate_table *rtab, **rtabp;
451 
452         if (!tab || --tab->refcnt)
453                 return;
454 
455         for (rtabp = &qdisc_rtab_list;
456              (rtab = *rtabp) != NULL;
457              rtabp = &rtab->next) {
458                 if (rtab == tab) {
459                         *rtabp = rtab->next;
460                         kfree(rtab);
461                         return;
462                 }
463         }
464 }
465 EXPORT_SYMBOL(qdisc_put_rtab);
466 
467 static LIST_HEAD(qdisc_stab_list);
468 
469 static const struct nla_policy stab_policy[TCA_STAB_MAX + 1] = {
470         [TCA_STAB_BASE] = { .len = sizeof(struct tc_sizespec) },
471         [TCA_STAB_DATA] = { .type = NLA_BINARY },
472 };
473 
474 static struct qdisc_size_table *qdisc_get_stab(struct nlattr *opt,
475                                                struct netlink_ext_ack *extack)
476 {
477         struct nlattr *tb[TCA_STAB_MAX + 1];
478         struct qdisc_size_table *stab;
479         struct tc_sizespec *s;
480         unsigned int tsize = 0;
481         u16 *tab = NULL;
482         int err;
483 
484         err = nla_parse_nested(tb, TCA_STAB_MAX, opt, stab_policy, extack);
485         if (err < 0)
486                 return ERR_PTR(err);
487         if (!tb[TCA_STAB_BASE]) {
488                 NL_SET_ERR_MSG(extack, "Size table base attribute is missing");
489                 return ERR_PTR(-EINVAL);
490         }
491 
492         s = nla_data(tb[TCA_STAB_BASE]);
493 
494         if (s->tsize > 0) {
495                 if (!tb[TCA_STAB_DATA]) {
496                         NL_SET_ERR_MSG(extack, "Size table data attribute is missing");
497                         return ERR_PTR(-EINVAL);
498                 }
499                 tab = nla_data(tb[TCA_STAB_DATA]);
500                 tsize = nla_len(tb[TCA_STAB_DATA]) / sizeof(u16);
501         }
502 
503         if (tsize != s->tsize || (!tab && tsize > 0)) {
504                 NL_SET_ERR_MSG(extack, "Invalid size of size table");
505                 return ERR_PTR(-EINVAL);
506         }
507 
508         list_for_each_entry(stab, &qdisc_stab_list, list) {
509                 if (memcmp(&stab->szopts, s, sizeof(*s)))
510                         continue;
511                 if (tsize > 0 && memcmp(stab->data, tab, tsize * sizeof(u16)))
512                         continue;
513                 stab->refcnt++;
514                 return stab;
515         }
516 
517         stab = kmalloc(sizeof(*stab) + tsize * sizeof(u16), GFP_KERNEL);
518         if (!stab)
519                 return ERR_PTR(-ENOMEM);
520 
521         stab->refcnt = 1;
522         stab->szopts = *s;
523         if (tsize > 0)
524                 memcpy(stab->data, tab, tsize * sizeof(u16));
525 
526         list_add_tail(&stab->list, &qdisc_stab_list);
527 
528         return stab;
529 }
530 
531 static void stab_kfree_rcu(struct rcu_head *head)
532 {
533         kfree(container_of(head, struct qdisc_size_table, rcu));
534 }
535 
536 void qdisc_put_stab(struct qdisc_size_table *tab)
537 {
538         if (!tab)
539                 return;
540 
541         if (--tab->refcnt == 0) {
542                 list_del(&tab->list);
543                 call_rcu_bh(&tab->rcu, stab_kfree_rcu);
544         }
545 }
546 EXPORT_SYMBOL(qdisc_put_stab);
547 
548 static int qdisc_dump_stab(struct sk_buff *skb, struct qdisc_size_table *stab)
549 {
550         struct nlattr *nest;
551 
552         nest = nla_nest_start(skb, TCA_STAB);
553         if (nest == NULL)
554                 goto nla_put_failure;
555         if (nla_put(skb, TCA_STAB_BASE, sizeof(stab->szopts), &stab->szopts))
556                 goto nla_put_failure;
557         nla_nest_end(skb, nest);
558 
559         return skb->len;
560 
561 nla_put_failure:
562         return -1;
563 }
564 
565 void __qdisc_calculate_pkt_len(struct sk_buff *skb,
566                                const struct qdisc_size_table *stab)
567 {
568         int pkt_len, slot;
569 
570         pkt_len = skb->len + stab->szopts.overhead;
571         if (unlikely(!stab->szopts.tsize))
572                 goto out;
573 
574         slot = pkt_len + stab->szopts.cell_align;
575         if (unlikely(slot < 0))
576                 slot = 0;
577 
578         slot >>= stab->szopts.cell_log;
579         if (likely(slot < stab->szopts.tsize))
580                 pkt_len = stab->data[slot];
581         else
582                 pkt_len = stab->data[stab->szopts.tsize - 1] *
583                                 (slot / stab->szopts.tsize) +
584                                 stab->data[slot % stab->szopts.tsize];
585 
586         pkt_len <<= stab->szopts.size_log;
587 out:
588         if (unlikely(pkt_len < 1))
589                 pkt_len = 1;
590         qdisc_skb_cb(skb)->pkt_len = pkt_len;
591 }
592 EXPORT_SYMBOL(__qdisc_calculate_pkt_len);
593 
594 void qdisc_warn_nonwc(const char *txt, struct Qdisc *qdisc)
595 {
596         if (!(qdisc->flags & TCQ_F_WARN_NONWC)) {
597                 pr_warn("%s: %s qdisc %X: is non-work-conserving?\n",
598                         txt, qdisc->ops->id, qdisc->handle >> 16);
599                 qdisc->flags |= TCQ_F_WARN_NONWC;
600         }
601 }
602 EXPORT_SYMBOL(qdisc_warn_nonwc);
603 
604 static enum hrtimer_restart qdisc_watchdog(struct hrtimer *timer)
605 {
606         struct qdisc_watchdog *wd = container_of(timer, struct qdisc_watchdog,
607                                                  timer);
608 
609         rcu_read_lock();
610         __netif_schedule(qdisc_root(wd->qdisc));
611         rcu_read_unlock();
612 
613         return HRTIMER_NORESTART;
614 }
615 
616 void qdisc_watchdog_init_clockid(struct qdisc_watchdog *wd, struct Qdisc *qdisc,
617                                  clockid_t clockid)
618 {
619         hrtimer_init(&wd->timer, clockid, HRTIMER_MODE_ABS_PINNED);
620         wd->timer.function = qdisc_watchdog;
621         wd->qdisc = qdisc;
622 }
623 EXPORT_SYMBOL(qdisc_watchdog_init_clockid);
624 
625 void qdisc_watchdog_init(struct qdisc_watchdog *wd, struct Qdisc *qdisc)
626 {
627         qdisc_watchdog_init_clockid(wd, qdisc, CLOCK_MONOTONIC);
628 }
629 EXPORT_SYMBOL(qdisc_watchdog_init);
630 
631 void qdisc_watchdog_schedule_ns(struct qdisc_watchdog *wd, u64 expires)
632 {
633         if (test_bit(__QDISC_STATE_DEACTIVATED,
634                      &qdisc_root_sleeping(wd->qdisc)->state))
635                 return;
636 
637         if (wd->last_expires == expires)
638                 return;
639 
640         wd->last_expires = expires;
641         hrtimer_start(&wd->timer,
642                       ns_to_ktime(expires),
643                       HRTIMER_MODE_ABS_PINNED);
644 }
645 EXPORT_SYMBOL(qdisc_watchdog_schedule_ns);
646 
647 void qdisc_watchdog_cancel(struct qdisc_watchdog *wd)
648 {
649         hrtimer_cancel(&wd->timer);
650 }
651 EXPORT_SYMBOL(qdisc_watchdog_cancel);
652 
653 static struct hlist_head *qdisc_class_hash_alloc(unsigned int n)
654 {
655         struct hlist_head *h;
656         unsigned int i;
657 
658         h = kvmalloc_array(n, sizeof(struct hlist_head), GFP_KERNEL);
659 
660         if (h != NULL) {
661                 for (i = 0; i < n; i++)
662                         INIT_HLIST_HEAD(&h[i]);
663         }
664         return h;
665 }
666 
667 void qdisc_class_hash_grow(struct Qdisc *sch, struct Qdisc_class_hash *clhash)
668 {
669         struct Qdisc_class_common *cl;
670         struct hlist_node *next;
671         struct hlist_head *nhash, *ohash;
672         unsigned int nsize, nmask, osize;
673         unsigned int i, h;
674 
675         /* Rehash when load factor exceeds 0.75 */
676         if (clhash->hashelems * 4 <= clhash->hashsize * 3)
677                 return;
678         nsize = clhash->hashsize * 2;
679         nmask = nsize - 1;
680         nhash = qdisc_class_hash_alloc(nsize);
681         if (nhash == NULL)
682                 return;
683 
684         ohash = clhash->hash;
685         osize = clhash->hashsize;
686 
687         sch_tree_lock(sch);
688         for (i = 0; i < osize; i++) {
689                 hlist_for_each_entry_safe(cl, next, &ohash[i], hnode) {
690                         h = qdisc_class_hash(cl->classid, nmask);
691                         hlist_add_head(&cl->hnode, &nhash[h]);
692                 }
693         }
694         clhash->hash     = nhash;
695         clhash->hashsize = nsize;
696         clhash->hashmask = nmask;
697         sch_tree_unlock(sch);
698 
699         kvfree(ohash);
700 }
701 EXPORT_SYMBOL(qdisc_class_hash_grow);
702 
703 int qdisc_class_hash_init(struct Qdisc_class_hash *clhash)
704 {
705         unsigned int size = 4;
706 
707         clhash->hash = qdisc_class_hash_alloc(size);
708         if (!clhash->hash)
709                 return -ENOMEM;
710         clhash->hashsize  = size;
711         clhash->hashmask  = size - 1;
712         clhash->hashelems = 0;
713         return 0;
714 }
715 EXPORT_SYMBOL(qdisc_class_hash_init);
716 
717 void qdisc_class_hash_destroy(struct Qdisc_class_hash *clhash)
718 {
719         kvfree(clhash->hash);
720 }
721 EXPORT_SYMBOL(qdisc_class_hash_destroy);
722 
723 void qdisc_class_hash_insert(struct Qdisc_class_hash *clhash,
724                              struct Qdisc_class_common *cl)
725 {
726         unsigned int h;
727 
728         INIT_HLIST_NODE(&cl->hnode);
729         h = qdisc_class_hash(cl->classid, clhash->hashmask);
730         hlist_add_head(&cl->hnode, &clhash->hash[h]);
731         clhash->hashelems++;
732 }
733 EXPORT_SYMBOL(qdisc_class_hash_insert);
734 
735 void qdisc_class_hash_remove(struct Qdisc_class_hash *clhash,
736                              struct Qdisc_class_common *cl)
737 {
738         hlist_del(&cl->hnode);
739         clhash->hashelems--;
740 }
741 EXPORT_SYMBOL(qdisc_class_hash_remove);
742 
743 /* Allocate an unique handle from space managed by kernel
744  * Possible range is [8000-FFFF]:0000 (0x8000 values)
745  */
746 static u32 qdisc_alloc_handle(struct net_device *dev)
747 {
748         int i = 0x8000;
749         static u32 autohandle = TC_H_MAKE(0x80000000U, 0);
750 
751         do {
752                 autohandle += TC_H_MAKE(0x10000U, 0);
753                 if (autohandle == TC_H_MAKE(TC_H_ROOT, 0))
754                         autohandle = TC_H_MAKE(0x80000000U, 0);
755                 if (!qdisc_lookup(dev, autohandle))
756                         return autohandle;
757                 cond_resched();
758         } while (--i > 0);
759 
760         return 0;
761 }
762 
763 void qdisc_tree_reduce_backlog(struct Qdisc *sch, unsigned int n,
764                                unsigned int len)
765 {
766         bool qdisc_is_offloaded = sch->flags & TCQ_F_OFFLOADED;
767         const struct Qdisc_class_ops *cops;
768         unsigned long cl;
769         u32 parentid;
770         bool notify;
771         int drops;
772 
773         if (n == 0 && len == 0)
774                 return;
775         drops = max_t(int, n, 0);
776         rcu_read_lock();
777         while ((parentid = sch->parent)) {
778                 if (TC_H_MAJ(parentid) == TC_H_MAJ(TC_H_INGRESS))
779                         break;
780 
781                 if (sch->flags & TCQ_F_NOPARENT)
782                         break;
783                 /* Notify parent qdisc only if child qdisc becomes empty.
784                  *
785                  * If child was empty even before update then backlog
786                  * counter is screwed and we skip notification because
787                  * parent class is already passive.
788                  *
789                  * If the original child was offloaded then it is allowed
790                  * to be seem as empty, so the parent is notified anyway.
791                  */
792                 notify = !sch->q.qlen && !WARN_ON_ONCE(!n &&
793                                                        !qdisc_is_offloaded);
794                 /* TODO: perform the search on a per txq basis */
795                 sch = qdisc_lookup(qdisc_dev(sch), TC_H_MAJ(parentid));
796                 if (sch == NULL) {
797                         WARN_ON_ONCE(parentid != TC_H_ROOT);
798                         break;
799                 }
800                 cops = sch->ops->cl_ops;
801                 if (notify && cops->qlen_notify) {
802                         cl = cops->find(sch, parentid);
803                         cops->qlen_notify(sch, cl);
804                 }
805                 sch->q.qlen -= n;
806                 sch->qstats.backlog -= len;
807                 __qdisc_qstats_drop(sch, drops);
808         }
809         rcu_read_unlock();
810 }
811 EXPORT_SYMBOL(qdisc_tree_reduce_backlog);
812 
813 static int tc_fill_qdisc(struct sk_buff *skb, struct Qdisc *q, u32 clid,
814                          u32 portid, u32 seq, u16 flags, int event)
815 {
816         struct gnet_stats_basic_cpu __percpu *cpu_bstats = NULL;
817         struct gnet_stats_queue __percpu *cpu_qstats = NULL;
818         struct tcmsg *tcm;
819         struct nlmsghdr  *nlh;
820         unsigned char *b = skb_tail_pointer(skb);
821         struct gnet_dump d;
822         struct qdisc_size_table *stab;
823         u32 block_index;
824         __u32 qlen;
825 
826         cond_resched();
827         nlh = nlmsg_put(skb, portid, seq, event, sizeof(*tcm), flags);
828         if (!nlh)
829                 goto out_nlmsg_trim;
830         tcm = nlmsg_data(nlh);
831         tcm->tcm_family = AF_UNSPEC;
832         tcm->tcm__pad1 = 0;
833         tcm->tcm__pad2 = 0;
834         tcm->tcm_ifindex = qdisc_dev(q)->ifindex;
835         tcm->tcm_parent = clid;
836         tcm->tcm_handle = q->handle;
837         tcm->tcm_info = refcount_read(&q->refcnt);
838         if (nla_put_string(skb, TCA_KIND, q->ops->id))
839                 goto nla_put_failure;
840         if (q->ops->ingress_block_get) {
841                 block_index = q->ops->ingress_block_get(q);
842                 if (block_index &&
843                     nla_put_u32(skb, TCA_INGRESS_BLOCK, block_index))
844                         goto nla_put_failure;
845         }
846         if (q->ops->egress_block_get) {
847                 block_index = q->ops->egress_block_get(q);
848                 if (block_index &&
849                     nla_put_u32(skb, TCA_EGRESS_BLOCK, block_index))
850                         goto nla_put_failure;
851         }
852         if (q->ops->dump && q->ops->dump(q, skb) < 0)
853                 goto nla_put_failure;
854         if (nla_put_u8(skb, TCA_HW_OFFLOAD, !!(q->flags & TCQ_F_OFFLOADED)))
855                 goto nla_put_failure;
856         qlen = qdisc_qlen_sum(q);
857 
858         stab = rtnl_dereference(q->stab);
859         if (stab && qdisc_dump_stab(skb, stab) < 0)
860                 goto nla_put_failure;
861 
862         if (gnet_stats_start_copy_compat(skb, TCA_STATS2, TCA_STATS, TCA_XSTATS,
863                                          NULL, &d, TCA_PAD) < 0)
864                 goto nla_put_failure;
865 
866         if (q->ops->dump_stats && q->ops->dump_stats(q, &d) < 0)
867                 goto nla_put_failure;
868 
869         if (qdisc_is_percpu_stats(q)) {
870                 cpu_bstats = q->cpu_bstats;
871                 cpu_qstats = q->cpu_qstats;
872         }
873 
874         if (gnet_stats_copy_basic(qdisc_root_sleeping_running(q),
875                                   &d, cpu_bstats, &q->bstats) < 0 ||
876             gnet_stats_copy_rate_est(&d, &q->rate_est) < 0 ||
877             gnet_stats_copy_queue(&d, cpu_qstats, &q->qstats, qlen) < 0)
878                 goto nla_put_failure;
879 
880         if (gnet_stats_finish_copy(&d) < 0)
881                 goto nla_put_failure;
882 
883         nlh->nlmsg_len = skb_tail_pointer(skb) - b;
884         return skb->len;
885 
886 out_nlmsg_trim:
887 nla_put_failure:
888         nlmsg_trim(skb, b);
889         return -1;
890 }
891 
892 static bool tc_qdisc_dump_ignore(struct Qdisc *q, bool dump_invisible)
893 {
894         if (q->flags & TCQ_F_BUILTIN)
895                 return true;
896         if ((q->flags & TCQ_F_INVISIBLE) && !dump_invisible)
897                 return true;
898 
899         return false;
900 }
901 
902 static int qdisc_notify(struct net *net, struct sk_buff *oskb,
903                         struct nlmsghdr *n, u32 clid,
904                         struct Qdisc *old, struct Qdisc *new)
905 {
906         struct sk_buff *skb;
907         u32 portid = oskb ? NETLINK_CB(oskb).portid : 0;
908 
909         skb = alloc_skb(NLMSG_GOODSIZE, GFP_KERNEL);
910         if (!skb)
911                 return -ENOBUFS;
912 
913         if (old && !tc_qdisc_dump_ignore(old, false)) {
914                 if (tc_fill_qdisc(skb, old, clid, portid, n->nlmsg_seq,
915                                   0, RTM_DELQDISC) < 0)
916                         goto err_out;
917         }
918         if (new && !tc_qdisc_dump_ignore(new, false)) {
919                 if (tc_fill_qdisc(skb, new, clid, portid, n->nlmsg_seq,
920                                   old ? NLM_F_REPLACE : 0, RTM_NEWQDISC) < 0)
921                         goto err_out;
922         }
923 
924         if (skb->len)
925                 return rtnetlink_send(skb, net, portid, RTNLGRP_TC,
926                                       n->nlmsg_flags & NLM_F_ECHO);
927 
928 err_out:
929         kfree_skb(skb);
930         return -EINVAL;
931 }
932 
933 static void notify_and_destroy(struct net *net, struct sk_buff *skb,
934                                struct nlmsghdr *n, u32 clid,
935                                struct Qdisc *old, struct Qdisc *new)
936 {
937         if (new || old)
938                 qdisc_notify(net, skb, n, clid, old, new);
939 
940         if (old)
941                 qdisc_put(old);
942 }
943 
944 /* Graft qdisc "new" to class "classid" of qdisc "parent" or
945  * to device "dev".
946  *
947  * When appropriate send a netlink notification using 'skb'
948  * and "n".
949  *
950  * On success, destroy old qdisc.
951  */
952 
953 static int qdisc_graft(struct net_device *dev, struct Qdisc *parent,
954                        struct sk_buff *skb, struct nlmsghdr *n, u32 classid,
955                        struct Qdisc *new, struct Qdisc *old,
956                        struct netlink_ext_ack *extack)
957 {
958         struct Qdisc *q = old;
959         struct net *net = dev_net(dev);
960         int err = 0;
961 
962         if (parent == NULL) {
963                 unsigned int i, num_q, ingress;
964 
965                 ingress = 0;
966                 num_q = dev->num_tx_queues;
967                 if ((q && q->flags & TCQ_F_INGRESS) ||
968                     (new && new->flags & TCQ_F_INGRESS)) {
969                         num_q = 1;
970                         ingress = 1;
971                         if (!dev_ingress_queue(dev)) {
972                                 NL_SET_ERR_MSG(extack, "Device does not have an ingress queue");
973                                 return -ENOENT;
974                         }
975                 }
976 
977                 if (dev->flags & IFF_UP)
978                         dev_deactivate(dev);
979 
980                 if (new && new->ops->attach)
981                         goto skip;
982 
983                 for (i = 0; i < num_q; i++) {
984                         struct netdev_queue *dev_queue = dev_ingress_queue(dev);
985 
986                         if (!ingress)
987                                 dev_queue = netdev_get_tx_queue(dev, i);
988 
989                         old = dev_graft_qdisc(dev_queue, new);
990                         if (new && i > 0)
991                                 qdisc_refcount_inc(new);
992 
993                         if (!ingress)
994                                 qdisc_put(old);
995                 }
996 
997 skip:
998                 if (!ingress) {
999                         notify_and_destroy(net, skb, n, classid,
1000                                            dev->qdisc, new);
1001                         if (new && !new->ops->attach)
1002                                 qdisc_refcount_inc(new);
1003                         dev->qdisc = new ? : &noop_qdisc;
1004 
1005                         if (new && new->ops->attach)
1006                                 new->ops->attach(new);
1007                 } else {
1008                         notify_and_destroy(net, skb, n, classid, old, new);
1009                 }
1010 
1011                 if (dev->flags & IFF_UP)
1012                         dev_activate(dev);
1013         } else {
1014                 const struct Qdisc_class_ops *cops = parent->ops->cl_ops;
1015 
1016                 /* Only support running class lockless if parent is lockless */
1017                 if (new && (new->flags & TCQ_F_NOLOCK) &&
1018                     parent && !(parent->flags & TCQ_F_NOLOCK))
1019                         new->flags &= ~TCQ_F_NOLOCK;
1020 
1021                 err = -EOPNOTSUPP;
1022                 if (cops && cops->graft) {
1023                         unsigned long cl = cops->find(parent, classid);
1024 
1025                         if (cl) {
1026                                 err = cops->graft(parent, cl, new, &old,
1027                                                   extack);
1028                         } else {
1029                                 NL_SET_ERR_MSG(extack, "Specified class not found");
1030                                 err = -ENOENT;
1031                         }
1032                 }
1033                 if (!err)
1034                         notify_and_destroy(net, skb, n, classid, old, new);
1035         }
1036         return err;
1037 }
1038 
1039 static int qdisc_block_indexes_set(struct Qdisc *sch, struct nlattr **tca,
1040                                    struct netlink_ext_ack *extack)
1041 {
1042         u32 block_index;
1043 
1044         if (tca[TCA_INGRESS_BLOCK]) {
1045                 block_index = nla_get_u32(tca[TCA_INGRESS_BLOCK]);
1046 
1047                 if (!block_index) {
1048                         NL_SET_ERR_MSG(extack, "Ingress block index cannot be 0");
1049                         return -EINVAL;
1050                 }
1051                 if (!sch->ops->ingress_block_set) {
1052                         NL_SET_ERR_MSG(extack, "Ingress block sharing is not supported");
1053                         return -EOPNOTSUPP;
1054                 }
1055                 sch->ops->ingress_block_set(sch, block_index);
1056         }
1057         if (tca[TCA_EGRESS_BLOCK]) {
1058                 block_index = nla_get_u32(tca[TCA_EGRESS_BLOCK]);
1059 
1060                 if (!block_index) {
1061                         NL_SET_ERR_MSG(extack, "Egress block index cannot be 0");
1062                         return -EINVAL;
1063                 }
1064                 if (!sch->ops->egress_block_set) {
1065                         NL_SET_ERR_MSG(extack, "Egress block sharing is not supported");
1066                         return -EOPNOTSUPP;
1067                 }
1068                 sch->ops->egress_block_set(sch, block_index);
1069         }
1070         return 0;
1071 }
1072 
1073 /*
1074    Allocate and initialize new qdisc.
1075 
1076    Parameters are passed via opt.
1077  */
1078 
1079 static struct Qdisc *qdisc_create(struct net_device *dev,
1080                                   struct netdev_queue *dev_queue,
1081                                   struct Qdisc *p, u32 parent, u32 handle,
1082                                   struct nlattr **tca, int *errp,
1083                                   struct netlink_ext_ack *extack)
1084 {
1085         int err;
1086         struct nlattr *kind = tca[TCA_KIND];
1087         struct Qdisc *sch;
1088         struct Qdisc_ops *ops;
1089         struct qdisc_size_table *stab;
1090 
1091         ops = qdisc_lookup_ops(kind);
1092 #ifdef CONFIG_MODULES
1093         if (ops == NULL && kind != NULL) {
1094                 char name[IFNAMSIZ];
1095                 if (nla_strlcpy(name, kind, IFNAMSIZ) < IFNAMSIZ) {
1096                         /* We dropped the RTNL semaphore in order to
1097                          * perform the module load.  So, even if we
1098                          * succeeded in loading the module we have to
1099                          * tell the caller to replay the request.  We
1100                          * indicate this using -EAGAIN.
1101                          * We replay the request because the device may
1102                          * go away in the mean time.
1103                          */
1104                         rtnl_unlock();
1105                         request_module("sch_%s", name);
1106                         rtnl_lock();
1107                         ops = qdisc_lookup_ops(kind);
1108                         if (ops != NULL) {
1109                                 /* We will try again qdisc_lookup_ops,
1110                                  * so don't keep a reference.
1111                                  */
1112                                 module_put(ops->owner);
1113                                 err = -EAGAIN;
1114                                 goto err_out;
1115                         }
1116                 }
1117         }
1118 #endif
1119 
1120         err = -ENOENT;
1121         if (!ops) {
1122                 NL_SET_ERR_MSG(extack, "Specified qdisc not found");
1123                 goto err_out;
1124         }
1125 
1126         sch = qdisc_alloc(dev_queue, ops, extack);
1127         if (IS_ERR(sch)) {
1128                 err = PTR_ERR(sch);
1129                 goto err_out2;
1130         }
1131 
1132         sch->parent = parent;
1133 
1134         if (handle == TC_H_INGRESS) {
1135                 sch->flags |= TCQ_F_INGRESS;
1136                 handle = TC_H_MAKE(TC_H_INGRESS, 0);
1137         } else {
1138                 if (handle == 0) {
1139                         handle = qdisc_alloc_handle(dev);
1140                         err = -ENOMEM;
1141                         if (handle == 0)
1142                                 goto err_out3;
1143                 }
1144                 if (!netif_is_multiqueue(dev))
1145                         sch->flags |= TCQ_F_ONETXQUEUE;
1146         }
1147 
1148         sch->handle = handle;
1149 
1150         /* This exist to keep backward compatible with a userspace
1151          * loophole, what allowed userspace to get IFF_NO_QUEUE
1152          * facility on older kernels by setting tx_queue_len=0 (prior
1153          * to qdisc init), and then forgot to reinit tx_queue_len
1154          * before again attaching a qdisc.
1155          */
1156         if ((dev->priv_flags & IFF_NO_QUEUE) && (dev->tx_queue_len == 0)) {
1157                 dev->tx_queue_len = DEFAULT_TX_QUEUE_LEN;
1158                 netdev_info(dev, "Caught tx_queue_len zero misconfig\n");
1159         }
1160 
1161         err = qdisc_block_indexes_set(sch, tca, extack);
1162         if (err)
1163                 goto err_out3;
1164 
1165         if (ops->init) {
1166                 err = ops->init(sch, tca[TCA_OPTIONS], extack);
1167                 if (err != 0)
1168                         goto err_out5;
1169         }
1170 
1171         if (tca[TCA_STAB]) {
1172                 stab = qdisc_get_stab(tca[TCA_STAB], extack);
1173                 if (IS_ERR(stab)) {
1174                         err = PTR_ERR(stab);
1175                         goto err_out4;
1176                 }
1177                 rcu_assign_pointer(sch->stab, stab);
1178         }
1179         if (tca[TCA_RATE]) {
1180                 seqcount_t *running;
1181 
1182                 err = -EOPNOTSUPP;
1183                 if (sch->flags & TCQ_F_MQROOT) {
1184                         NL_SET_ERR_MSG(extack, "Cannot attach rate estimator to a multi-queue root qdisc");
1185                         goto err_out4;
1186                 }
1187 
1188                 if (sch->parent != TC_H_ROOT &&
1189                     !(sch->flags & TCQ_F_INGRESS) &&
1190                     (!p || !(p->flags & TCQ_F_MQROOT)))
1191                         running = qdisc_root_sleeping_running(sch);
1192                 else
1193                         running = &sch->running;
1194 
1195                 err = gen_new_estimator(&sch->bstats,
1196                                         sch->cpu_bstats,
1197                                         &sch->rate_est,
1198                                         NULL,
1199                                         running,
1200                                         tca[TCA_RATE]);
1201                 if (err) {
1202                         NL_SET_ERR_MSG(extack, "Failed to generate new estimator");
1203                         goto err_out4;
1204                 }
1205         }
1206 
1207         qdisc_hash_add(sch, false);
1208 
1209         return sch;
1210 
1211 err_out5:
1212         /* ops->init() failed, we call ->destroy() like qdisc_create_dflt() */
1213         if (ops->destroy)
1214                 ops->destroy(sch);
1215 err_out3:
1216         dev_put(dev);
1217         qdisc_free(sch);
1218 err_out2:
1219         module_put(ops->owner);
1220 err_out:
1221         *errp = err;
1222         return NULL;
1223 
1224 err_out4:
1225         /*
1226          * Any broken qdiscs that would require a ops->reset() here?
1227          * The qdisc was never in action so it shouldn't be necessary.
1228          */
1229         qdisc_put_stab(rtnl_dereference(sch->stab));
1230         if (ops->destroy)
1231                 ops->destroy(sch);
1232         goto err_out3;
1233 }
1234 
1235 static int qdisc_change(struct Qdisc *sch, struct nlattr **tca,
1236                         struct netlink_ext_ack *extack)
1237 {
1238         struct qdisc_size_table *ostab, *stab = NULL;
1239         int err = 0;
1240 
1241         if (tca[TCA_OPTIONS]) {
1242                 if (!sch->ops->change) {
1243                         NL_SET_ERR_MSG(extack, "Change operation not supported by specified qdisc");
1244                         return -EINVAL;
1245                 }
1246                 if (tca[TCA_INGRESS_BLOCK] || tca[TCA_EGRESS_BLOCK]) {
1247                         NL_SET_ERR_MSG(extack, "Change of blocks is not supported");
1248                         return -EOPNOTSUPP;
1249                 }
1250                 err = sch->ops->change(sch, tca[TCA_OPTIONS], extack);
1251                 if (err)
1252                         return err;
1253         }
1254 
1255         if (tca[TCA_STAB]) {
1256                 stab = qdisc_get_stab(tca[TCA_STAB], extack);
1257                 if (IS_ERR(stab))
1258                         return PTR_ERR(stab);
1259         }
1260 
1261         ostab = rtnl_dereference(sch->stab);
1262         rcu_assign_pointer(sch->stab, stab);
1263         qdisc_put_stab(ostab);
1264 
1265         if (tca[TCA_RATE]) {
1266                 /* NB: ignores errors from replace_estimator
1267                    because change can't be undone. */
1268                 if (sch->flags & TCQ_F_MQROOT)
1269                         goto out;
1270                 gen_replace_estimator(&sch->bstats,
1271                                       sch->cpu_bstats,
1272                                       &sch->rate_est,
1273                                       NULL,
1274                                       qdisc_root_sleeping_running(sch),
1275                                       tca[TCA_RATE]);
1276         }
1277 out:
1278         return 0;
1279 }
1280 
1281 struct check_loop_arg {
1282         struct qdisc_walker     w;
1283         struct Qdisc            *p;
1284         int                     depth;
1285 };
1286 
1287 static int check_loop_fn(struct Qdisc *q, unsigned long cl,
1288                          struct qdisc_walker *w);
1289 
1290 static int check_loop(struct Qdisc *q, struct Qdisc *p, int depth)
1291 {
1292         struct check_loop_arg   arg;
1293 
1294         if (q->ops->cl_ops == NULL)
1295                 return 0;
1296 
1297         arg.w.stop = arg.w.skip = arg.w.count = 0;
1298         arg.w.fn = check_loop_fn;
1299         arg.depth = depth;
1300         arg.p = p;
1301         q->ops->cl_ops->walk(q, &arg.w);
1302         return arg.w.stop ? -ELOOP : 0;
1303 }
1304 
1305 static int
1306 check_loop_fn(struct Qdisc *q, unsigned long cl, struct qdisc_walker *w)
1307 {
1308         struct Qdisc *leaf;
1309         const struct Qdisc_class_ops *cops = q->ops->cl_ops;
1310         struct check_loop_arg *arg = (struct check_loop_arg *)w;
1311 
1312         leaf = cops->leaf(q, cl);
1313         if (leaf) {
1314                 if (leaf == arg->p || arg->depth > 7)
1315                         return -ELOOP;
1316                 return check_loop(leaf, arg->p, arg->depth + 1);
1317         }
1318         return 0;
1319 }
1320 
1321 const struct nla_policy rtm_tca_policy[TCA_MAX + 1] = {
1322         [TCA_KIND]              = { .type = NLA_STRING },
1323         [TCA_RATE]              = { .type = NLA_BINARY,
1324                                     .len = sizeof(struct tc_estimator) },
1325         [TCA_STAB]              = { .type = NLA_NESTED },
1326         [TCA_DUMP_INVISIBLE]    = { .type = NLA_FLAG },
1327         [TCA_CHAIN]             = { .type = NLA_U32 },
1328         [TCA_INGRESS_BLOCK]     = { .type = NLA_U32 },
1329         [TCA_EGRESS_BLOCK]      = { .type = NLA_U32 },
1330 };
1331 
1332 /*
1333  * Delete/get qdisc.
1334  */
1335 
1336 static int tc_get_qdisc(struct sk_buff *skb, struct nlmsghdr *n,
1337                         struct netlink_ext_ack *extack)
1338 {
1339         struct net *net = sock_net(skb->sk);
1340         struct tcmsg *tcm = nlmsg_data(n);
1341         struct nlattr *tca[TCA_MAX + 1];
1342         struct net_device *dev;
1343         u32 clid;
1344         struct Qdisc *q = NULL;
1345         struct Qdisc *p = NULL;
1346         int err;
1347 
1348         if ((n->nlmsg_type != RTM_GETQDISC) &&
1349             !netlink_ns_capable(skb, net->user_ns, CAP_NET_ADMIN))
1350                 return -EPERM;
1351 
1352         err = nlmsg_parse(n, sizeof(*tcm), tca, TCA_MAX, rtm_tca_policy,
1353                           extack);
1354         if (err < 0)
1355                 return err;
1356 
1357         dev = __dev_get_by_index(net, tcm->tcm_ifindex);
1358         if (!dev)
1359                 return -ENODEV;
1360 
1361         clid = tcm->tcm_parent;
1362         if (clid) {
1363                 if (clid != TC_H_ROOT) {
1364                         if (TC_H_MAJ(clid) != TC_H_MAJ(TC_H_INGRESS)) {
1365                                 p = qdisc_lookup(dev, TC_H_MAJ(clid));
1366                                 if (!p) {
1367                                         NL_SET_ERR_MSG(extack, "Failed to find qdisc with specified classid");
1368                                         return -ENOENT;
1369                                 }
1370                                 q = qdisc_leaf(p, clid);
1371                         } else if (dev_ingress_queue(dev)) {
1372                                 q = dev_ingress_queue(dev)->qdisc_sleeping;
1373                         }
1374                 } else {
1375                         q = dev->qdisc;
1376                 }
1377                 if (!q) {
1378                         NL_SET_ERR_MSG(extack, "Cannot find specified qdisc on specified device");
1379                         return -ENOENT;
1380                 }
1381 
1382                 if (tcm->tcm_handle && q->handle != tcm->tcm_handle) {
1383                         NL_SET_ERR_MSG(extack, "Invalid handle");
1384                         return -EINVAL;
1385                 }
1386         } else {
1387                 q = qdisc_lookup(dev, tcm->tcm_handle);
1388                 if (!q) {
1389                         NL_SET_ERR_MSG(extack, "Failed to find qdisc with specified handle");
1390                         return -ENOENT;
1391                 }
1392         }
1393 
1394         if (tca[TCA_KIND] && nla_strcmp(tca[TCA_KIND], q->ops->id)) {
1395                 NL_SET_ERR_MSG(extack, "Invalid qdisc name");
1396                 return -EINVAL;
1397         }
1398 
1399         if (n->nlmsg_type == RTM_DELQDISC) {
1400                 if (!clid) {
1401                         NL_SET_ERR_MSG(extack, "Classid cannot be zero");
1402                         return -EINVAL;
1403                 }
1404                 if (q->handle == 0) {
1405                         NL_SET_ERR_MSG(extack, "Cannot delete qdisc with handle of zero");
1406                         return -ENOENT;
1407                 }
1408                 err = qdisc_graft(dev, p, skb, n, clid, NULL, q, extack);
1409                 if (err != 0)
1410                         return err;
1411         } else {
1412                 qdisc_notify(net, skb, n, clid, NULL, q);
1413         }
1414         return 0;
1415 }
1416 
1417 /*
1418  * Create/change qdisc.
1419  */
1420 
1421 static int tc_modify_qdisc(struct sk_buff *skb, struct nlmsghdr *n,
1422                            struct netlink_ext_ack *extack)
1423 {
1424         struct net *net = sock_net(skb->sk);
1425         struct tcmsg *tcm;
1426         struct nlattr *tca[TCA_MAX + 1];
1427         struct net_device *dev;
1428         u32 clid;
1429         struct Qdisc *q, *p;
1430         int err;
1431 
1432         if (!netlink_ns_capable(skb, net->user_ns, CAP_NET_ADMIN))
1433                 return -EPERM;
1434 
1435 replay:
1436         /* Reinit, just in case something touches this. */
1437         err = nlmsg_parse(n, sizeof(*tcm), tca, TCA_MAX, rtm_tca_policy,
1438                           extack);
1439         if (err < 0)
1440                 return err;
1441 
1442         tcm = nlmsg_data(n);
1443         clid = tcm->tcm_parent;
1444         q = p = NULL;
1445 
1446         dev = __dev_get_by_index(net, tcm->tcm_ifindex);
1447         if (!dev)
1448                 return -ENODEV;
1449 
1450 
1451         if (clid) {
1452                 if (clid != TC_H_ROOT) {
1453                         if (clid != TC_H_INGRESS) {
1454                                 p = qdisc_lookup(dev, TC_H_MAJ(clid));
1455                                 if (!p) {
1456                                         NL_SET_ERR_MSG(extack, "Failed to find specified qdisc");
1457                                         return -ENOENT;
1458                                 }
1459                                 q = qdisc_leaf(p, clid);
1460                         } else if (dev_ingress_queue_create(dev)) {
1461                                 q = dev_ingress_queue(dev)->qdisc_sleeping;
1462                         }
1463                 } else {
1464                         q = dev->qdisc;
1465                 }
1466 
1467                 /* It may be default qdisc, ignore it */
1468                 if (q && q->handle == 0)
1469                         q = NULL;
1470 
1471                 if (!q || !tcm->tcm_handle || q->handle != tcm->tcm_handle) {
1472                         if (tcm->tcm_handle) {
1473                                 if (q && !(n->nlmsg_flags & NLM_F_REPLACE)) {
1474                                         NL_SET_ERR_MSG(extack, "NLM_F_REPLACE needed to override");
1475                                         return -EEXIST;
1476                                 }
1477                                 if (TC_H_MIN(tcm->tcm_handle)) {
1478                                         NL_SET_ERR_MSG(extack, "Invalid minor handle");
1479                                         return -EINVAL;
1480                                 }
1481                                 q = qdisc_lookup(dev, tcm->tcm_handle);
1482                                 if (!q)
1483                                         goto create_n_graft;
1484                                 if (n->nlmsg_flags & NLM_F_EXCL) {
1485                                         NL_SET_ERR_MSG(extack, "Exclusivity flag on, cannot override");
1486                                         return -EEXIST;
1487                                 }
1488                                 if (tca[TCA_KIND] &&
1489                                     nla_strcmp(tca[TCA_KIND], q->ops->id)) {
1490                                         NL_SET_ERR_MSG(extack, "Invalid qdisc name");
1491                                         return -EINVAL;
1492                                 }
1493                                 if (q == p ||
1494                                     (p && check_loop(q, p, 0))) {
1495                                         NL_SET_ERR_MSG(extack, "Qdisc parent/child loop detected");
1496                                         return -ELOOP;
1497                                 }
1498                                 qdisc_refcount_inc(q);
1499                                 goto graft;
1500                         } else {
1501                                 if (!q)
1502                                         goto create_n_graft;
1503 
1504                                 /* This magic test requires explanation.
1505                                  *
1506                                  *   We know, that some child q is already
1507                                  *   attached to this parent and have choice:
1508                                  *   either to change it or to create/graft new one.
1509                                  *
1510                                  *   1. We are allowed to create/graft only
1511                                  *   if CREATE and REPLACE flags are set.
1512                                  *
1513                                  *   2. If EXCL is set, requestor wanted to say,
1514                                  *   that qdisc tcm_handle is not expected
1515                                  *   to exist, so that we choose create/graft too.
1516                                  *
1517                                  *   3. The last case is when no flags are set.
1518                                  *   Alas, it is sort of hole in API, we
1519                                  *   cannot decide what to do unambiguously.
1520                                  *   For now we select create/graft, if
1521                                  *   user gave KIND, which does not match existing.
1522                                  */
1523                                 if ((n->nlmsg_flags & NLM_F_CREATE) &&
1524                                     (n->nlmsg_flags & NLM_F_REPLACE) &&
1525                                     ((n->nlmsg_flags & NLM_F_EXCL) ||
1526                                      (tca[TCA_KIND] &&
1527                                       nla_strcmp(tca[TCA_KIND], q->ops->id))))
1528                                         goto create_n_graft;
1529                         }
1530                 }
1531         } else {
1532                 if (!tcm->tcm_handle) {
1533                         NL_SET_ERR_MSG(extack, "Handle cannot be zero");
1534                         return -EINVAL;
1535                 }
1536                 q = qdisc_lookup(dev, tcm->tcm_handle);
1537         }
1538 
1539         /* Change qdisc parameters */
1540         if (!q) {
1541                 NL_SET_ERR_MSG(extack, "Specified qdisc not found");
1542                 return -ENOENT;
1543         }
1544         if (n->nlmsg_flags & NLM_F_EXCL) {
1545                 NL_SET_ERR_MSG(extack, "Exclusivity flag on, cannot modify");
1546                 return -EEXIST;
1547         }
1548         if (tca[TCA_KIND] && nla_strcmp(tca[TCA_KIND], q->ops->id)) {
1549                 NL_SET_ERR_MSG(extack, "Invalid qdisc name");
1550                 return -EINVAL;
1551         }
1552         err = qdisc_change(q, tca, extack);
1553         if (err == 0)
1554                 qdisc_notify(net, skb, n, clid, NULL, q);
1555         return err;
1556 
1557 create_n_graft:
1558         if (!(n->nlmsg_flags & NLM_F_CREATE)) {
1559                 NL_SET_ERR_MSG(extack, "Qdisc not found. To create specify NLM_F_CREATE flag");
1560                 return -ENOENT;
1561         }
1562         if (clid == TC_H_INGRESS) {
1563                 if (dev_ingress_queue(dev)) {
1564                         q = qdisc_create(dev, dev_ingress_queue(dev), p,
1565                                          tcm->tcm_parent, tcm->tcm_parent,
1566                                          tca, &err, extack);
1567                 } else {
1568                         NL_SET_ERR_MSG(extack, "Cannot find ingress queue for specified device");
1569                         err = -ENOENT;
1570                 }
1571         } else {
1572                 struct netdev_queue *dev_queue;
1573 
1574                 if (p && p->ops->cl_ops && p->ops->cl_ops->select_queue)
1575                         dev_queue = p->ops->cl_ops->select_queue(p, tcm);
1576                 else if (p)
1577                         dev_queue = p->dev_queue;
1578                 else
1579                         dev_queue = netdev_get_tx_queue(dev, 0);
1580 
1581                 q = qdisc_create(dev, dev_queue, p,
1582                                  tcm->tcm_parent, tcm->tcm_handle,
1583                                  tca, &err, extack);
1584         }
1585         if (q == NULL) {
1586                 if (err == -EAGAIN)
1587                         goto replay;
1588                 return err;
1589         }
1590 
1591 graft:
1592         err = qdisc_graft(dev, p, skb, n, clid, q, NULL, extack);
1593         if (err) {
1594                 if (q)
1595                         qdisc_put(q);
1596                 return err;
1597         }
1598 
1599         return 0;
1600 }
1601 
1602 static int tc_dump_qdisc_root(struct Qdisc *root, struct sk_buff *skb,
1603                               struct netlink_callback *cb,
1604                               int *q_idx_p, int s_q_idx, bool recur,
1605                               bool dump_invisible)
1606 {
1607         int ret = 0, q_idx = *q_idx_p;
1608         struct Qdisc *q;
1609         int b;
1610 
1611         if (!root)
1612                 return 0;
1613 
1614         q = root;
1615         if (q_idx < s_q_idx) {
1616                 q_idx++;
1617         } else {
1618                 if (!tc_qdisc_dump_ignore(q, dump_invisible) &&
1619                     tc_fill_qdisc(skb, q, q->parent, NETLINK_CB(cb->skb).portid,
1620                                   cb->nlh->nlmsg_seq, NLM_F_MULTI,
1621                                   RTM_NEWQDISC) <= 0)
1622                         goto done;
1623                 q_idx++;
1624         }
1625 
1626         /* If dumping singletons, there is no qdisc_dev(root) and the singleton
1627          * itself has already been dumped.
1628          *
1629          * If we've already dumped the top-level (ingress) qdisc above and the global
1630          * qdisc hashtable, we don't want to hit it again
1631          */
1632         if (!qdisc_dev(root) || !recur)
1633                 goto out;
1634 
1635         hash_for_each(qdisc_dev(root)->qdisc_hash, b, q, hash) {
1636                 if (q_idx < s_q_idx) {
1637                         q_idx++;
1638                         continue;
1639                 }
1640                 if (!tc_qdisc_dump_ignore(q, dump_invisible) &&
1641                     tc_fill_qdisc(skb, q, q->parent, NETLINK_CB(cb->skb).portid,
1642                                   cb->nlh->nlmsg_seq, NLM_F_MULTI,
1643                                   RTM_NEWQDISC) <= 0)
1644                         goto done;
1645                 q_idx++;
1646         }
1647 
1648 out:
1649         *q_idx_p = q_idx;
1650         return ret;
1651 done:
1652         ret = -1;
1653         goto out;
1654 }
1655 
1656 static int tc_dump_qdisc(struct sk_buff *skb, struct netlink_callback *cb)
1657 {
1658         struct net *net = sock_net(skb->sk);
1659         int idx, q_idx;
1660         int s_idx, s_q_idx;
1661         struct net_device *dev;
1662         const struct nlmsghdr *nlh = cb->nlh;
1663         struct nlattr *tca[TCA_MAX + 1];
1664         int err;
1665 
1666         s_idx = cb->args[0];
1667         s_q_idx = q_idx = cb->args[1];
1668 
1669         idx = 0;
1670         ASSERT_RTNL();
1671 
1672         err = nlmsg_parse(nlh, sizeof(struct tcmsg), tca, TCA_MAX,
1673                           rtm_tca_policy, cb->extack);
1674         if (err < 0)
1675                 return err;
1676 
1677         for_each_netdev(net, dev) {
1678                 struct netdev_queue *dev_queue;
1679 
1680                 if (idx < s_idx)
1681                         goto cont;
1682                 if (idx > s_idx)
1683                         s_q_idx = 0;
1684                 q_idx = 0;
1685 
1686                 if (tc_dump_qdisc_root(dev->qdisc, skb, cb, &q_idx, s_q_idx,
1687                                        true, tca[TCA_DUMP_INVISIBLE]) < 0)
1688                         goto done;
1689 
1690                 dev_queue = dev_ingress_queue(dev);
1691                 if (dev_queue &&
1692                     tc_dump_qdisc_root(dev_queue->qdisc_sleeping, skb, cb,
1693                                        &q_idx, s_q_idx, false,
1694                                        tca[TCA_DUMP_INVISIBLE]) < 0)
1695                         goto done;
1696 
1697 cont:
1698                 idx++;
1699         }
1700 
1701 done:
1702         cb->args[0] = idx;
1703         cb->args[1] = q_idx;
1704 
1705         return skb->len;
1706 }
1707 
1708 
1709 
1710 /************************************************
1711  *      Traffic classes manipulation.           *
1712  ************************************************/
1713 
1714 static int tc_fill_tclass(struct sk_buff *skb, struct Qdisc *q,
1715                           unsigned long cl,
1716                           u32 portid, u32 seq, u16 flags, int event)
1717 {
1718         struct tcmsg *tcm;
1719         struct nlmsghdr  *nlh;
1720         unsigned char *b = skb_tail_pointer(skb);
1721         struct gnet_dump d;
1722         const struct Qdisc_class_ops *cl_ops = q->ops->cl_ops;
1723 
1724         cond_resched();
1725         nlh = nlmsg_put(skb, portid, seq, event, sizeof(*tcm), flags);
1726         if (!nlh)
1727                 goto out_nlmsg_trim;
1728         tcm = nlmsg_data(nlh);
1729         tcm->tcm_family = AF_UNSPEC;
1730         tcm->tcm__pad1 = 0;
1731         tcm->tcm__pad2 = 0;
1732         tcm->tcm_ifindex = qdisc_dev(q)->ifindex;
1733         tcm->tcm_parent = q->handle;
1734         tcm->tcm_handle = q->handle;
1735         tcm->tcm_info = 0;
1736         if (nla_put_string(skb, TCA_KIND, q->ops->id))
1737                 goto nla_put_failure;
1738         if (cl_ops->dump && cl_ops->dump(q, cl, skb, tcm) < 0)
1739                 goto nla_put_failure;
1740 
1741         if (gnet_stats_start_copy_compat(skb, TCA_STATS2, TCA_STATS, TCA_XSTATS,
1742                                          NULL, &d, TCA_PAD) < 0)
1743                 goto nla_put_failure;
1744 
1745         if (cl_ops->dump_stats && cl_ops->dump_stats(q, cl, &d) < 0)
1746                 goto nla_put_failure;
1747 
1748         if (gnet_stats_finish_copy(&d) < 0)
1749                 goto nla_put_failure;
1750 
1751         nlh->nlmsg_len = skb_tail_pointer(skb) - b;
1752         return skb->len;
1753 
1754 out_nlmsg_trim:
1755 nla_put_failure:
1756         nlmsg_trim(skb, b);
1757         return -1;
1758 }
1759 
1760 static int tclass_notify(struct net *net, struct sk_buff *oskb,
1761                          struct nlmsghdr *n, struct Qdisc *q,
1762                          unsigned long cl, int event)
1763 {
1764         struct sk_buff *skb;
1765         u32 portid = oskb ? NETLINK_CB(oskb).portid : 0;
1766 
1767         skb = alloc_skb(NLMSG_GOODSIZE, GFP_KERNEL);
1768         if (!skb)
1769                 return -ENOBUFS;
1770 
1771         if (tc_fill_tclass(skb, q, cl, portid, n->nlmsg_seq, 0, event) < 0) {
1772                 kfree_skb(skb);
1773                 return -EINVAL;
1774         }
1775 
1776         return rtnetlink_send(skb, net, portid, RTNLGRP_TC,
1777                               n->nlmsg_flags & NLM_F_ECHO);
1778 }
1779 
1780 static int tclass_del_notify(struct net *net,
1781                              const struct Qdisc_class_ops *cops,
1782                              struct sk_buff *oskb, struct nlmsghdr *n,
1783                              struct Qdisc *q, unsigned long cl)
1784 {
1785         u32 portid = oskb ? NETLINK_CB(oskb).portid : 0;
1786         struct sk_buff *skb;
1787         int err = 0;
1788 
1789         if (!cops->delete)
1790                 return -EOPNOTSUPP;
1791 
1792         skb = alloc_skb(NLMSG_GOODSIZE, GFP_KERNEL);
1793         if (!skb)
1794                 return -ENOBUFS;
1795 
1796         if (tc_fill_tclass(skb, q, cl, portid, n->nlmsg_seq, 0,
1797                            RTM_DELTCLASS) < 0) {
1798                 kfree_skb(skb);
1799                 return -EINVAL;
1800         }
1801 
1802         err = cops->delete(q, cl);
1803         if (err) {
1804                 kfree_skb(skb);
1805                 return err;
1806         }
1807 
1808         return rtnetlink_send(skb, net, portid, RTNLGRP_TC,
1809                               n->nlmsg_flags & NLM_F_ECHO);
1810 }
1811 
1812 #ifdef CONFIG_NET_CLS
1813 
1814 struct tcf_bind_args {
1815         struct tcf_walker w;
1816         u32 classid;
1817         unsigned long cl;
1818 };
1819 
1820 static int tcf_node_bind(struct tcf_proto *tp, void *n, struct tcf_walker *arg)
1821 {
1822         struct tcf_bind_args *a = (void *)arg;
1823 
1824         if (tp->ops->bind_class) {
1825                 struct Qdisc *q = tcf_block_q(tp->chain->block);
1826 
1827                 sch_tree_lock(q);
1828                 tp->ops->bind_class(n, a->classid, a->cl);
1829                 sch_tree_unlock(q);
1830         }
1831         return 0;
1832 }
1833 
1834 static void tc_bind_tclass(struct Qdisc *q, u32 portid, u32 clid,
1835                            unsigned long new_cl)
1836 {
1837         const struct Qdisc_class_ops *cops = q->ops->cl_ops;
1838         struct tcf_block *block;
1839         struct tcf_chain *chain;
1840         unsigned long cl;
1841 
1842         cl = cops->find(q, portid);
1843         if (!cl)
1844                 return;
1845         block = cops->tcf_block(q, cl, NULL);
1846         if (!block)
1847                 return;
1848         list_for_each_entry(chain, &block->chain_list, list) {
1849                 struct tcf_proto *tp;
1850 
1851                 for (tp = rtnl_dereference(chain->filter_chain);
1852                      tp; tp = rtnl_dereference(tp->next)) {
1853                         struct tcf_bind_args arg = {};
1854 
1855                         arg.w.fn = tcf_node_bind;
1856                         arg.classid = clid;
1857                         arg.cl = new_cl;
1858                         tp->ops->walk(tp, &arg.w);
1859                 }
1860         }
1861 }
1862 
1863 #else
1864 
1865 static void tc_bind_tclass(struct Qdisc *q, u32 portid, u32 clid,
1866                            unsigned long new_cl)
1867 {
1868 }
1869 
1870 #endif
1871 
1872 static int tc_ctl_tclass(struct sk_buff *skb, struct nlmsghdr *n,
1873                          struct netlink_ext_ack *extack)
1874 {
1875         struct net *net = sock_net(skb->sk);
1876         struct tcmsg *tcm = nlmsg_data(n);
1877         struct nlattr *tca[TCA_MAX + 1];
1878         struct net_device *dev;
1879         struct Qdisc *q = NULL;
1880         const struct Qdisc_class_ops *cops;
1881         unsigned long cl = 0;
1882         unsigned long new_cl;
1883         u32 portid;
1884         u32 clid;
1885         u32 qid;
1886         int err;
1887 
1888         if ((n->nlmsg_type != RTM_GETTCLASS) &&
1889             !netlink_ns_capable(skb, net->user_ns, CAP_NET_ADMIN))
1890                 return -EPERM;
1891 
1892         err = nlmsg_parse(n, sizeof(*tcm), tca, TCA_MAX, rtm_tca_policy,
1893                           extack);
1894         if (err < 0)
1895                 return err;
1896 
1897         dev = __dev_get_by_index(net, tcm->tcm_ifindex);
1898         if (!dev)
1899                 return -ENODEV;
1900 
1901         /*
1902            parent == TC_H_UNSPEC - unspecified parent.
1903            parent == TC_H_ROOT   - class is root, which has no parent.
1904            parent == X:0         - parent is root class.
1905            parent == X:Y         - parent is a node in hierarchy.
1906            parent == 0:Y         - parent is X:Y, where X:0 is qdisc.
1907 
1908            handle == 0:0         - generate handle from kernel pool.
1909            handle == 0:Y         - class is X:Y, where X:0 is qdisc.
1910            handle == X:Y         - clear.
1911            handle == X:0         - root class.
1912          */
1913 
1914         /* Step 1. Determine qdisc handle X:0 */
1915 
1916         portid = tcm->tcm_parent;
1917         clid = tcm->tcm_handle;
1918         qid = TC_H_MAJ(clid);
1919 
1920         if (portid != TC_H_ROOT) {
1921                 u32 qid1 = TC_H_MAJ(portid);
1922 
1923                 if (qid && qid1) {
1924                         /* If both majors are known, they must be identical. */
1925                         if (qid != qid1)
1926                                 return -EINVAL;
1927                 } else if (qid1) {
1928                         qid = qid1;
1929                 } else if (qid == 0)
1930                         qid = dev->qdisc->handle;
1931 
1932                 /* Now qid is genuine qdisc handle consistent
1933                  * both with parent and child.
1934                  *
1935                  * TC_H_MAJ(portid) still may be unspecified, complete it now.
1936                  */
1937                 if (portid)
1938                         portid = TC_H_MAKE(qid, portid);
1939         } else {
1940                 if (qid == 0)
1941                         qid = dev->qdisc->handle;
1942         }
1943 
1944         /* OK. Locate qdisc */
1945         q = qdisc_lookup(dev, qid);
1946         if (!q)
1947                 return -ENOENT;
1948 
1949         /* An check that it supports classes */
1950         cops = q->ops->cl_ops;
1951         if (cops == NULL)
1952                 return -EINVAL;
1953 
1954         /* Now try to get class */
1955         if (clid == 0) {
1956                 if (portid == TC_H_ROOT)
1957                         clid = qid;
1958         } else
1959                 clid = TC_H_MAKE(qid, clid);
1960 
1961         if (clid)
1962                 cl = cops->find(q, clid);
1963 
1964         if (cl == 0) {
1965                 err = -ENOENT;
1966                 if (n->nlmsg_type != RTM_NEWTCLASS ||
1967                     !(n->nlmsg_flags & NLM_F_CREATE))
1968                         goto out;
1969         } else {
1970                 switch (n->nlmsg_type) {
1971                 case RTM_NEWTCLASS:
1972                         err = -EEXIST;
1973                         if (n->nlmsg_flags & NLM_F_EXCL)
1974                                 goto out;
1975                         break;
1976                 case RTM_DELTCLASS:
1977                         err = tclass_del_notify(net, cops, skb, n, q, cl);
1978                         /* Unbind the class with flilters with 0 */
1979                         tc_bind_tclass(q, portid, clid, 0);
1980                         goto out;
1981                 case RTM_GETTCLASS:
1982                         err = tclass_notify(net, skb, n, q, cl, RTM_NEWTCLASS);
1983                         goto out;
1984                 default:
1985                         err = -EINVAL;
1986                         goto out;
1987                 }
1988         }
1989 
1990         if (tca[TCA_INGRESS_BLOCK] || tca[TCA_EGRESS_BLOCK]) {
1991                 NL_SET_ERR_MSG(extack, "Shared blocks are not supported for classes");
1992                 return -EOPNOTSUPP;
1993         }
1994 
1995         new_cl = cl;
1996         err = -EOPNOTSUPP;
1997         if (cops->change)
1998                 err = cops->change(q, clid, portid, tca, &new_cl, extack);
1999         if (err == 0) {
2000                 tclass_notify(net, skb, n, q, new_cl, RTM_NEWTCLASS);
2001                 /* We just create a new class, need to do reverse binding. */
2002                 if (cl != new_cl)
2003                         tc_bind_tclass(q, portid, clid, new_cl);
2004         }
2005 out:
2006         return err;
2007 }
2008 
2009 struct qdisc_dump_args {
2010         struct qdisc_walker     w;
2011         struct sk_buff          *skb;
2012         struct netlink_callback *cb;
2013 };
2014 
2015 static int qdisc_class_dump(struct Qdisc *q, unsigned long cl,
2016                             struct qdisc_walker *arg)
2017 {
2018         struct qdisc_dump_args *a = (struct qdisc_dump_args *)arg;
2019 
2020         return tc_fill_tclass(a->skb, q, cl, NETLINK_CB(a->cb->skb).portid,
2021                               a->cb->nlh->nlmsg_seq, NLM_F_MULTI,
2022                               RTM_NEWTCLASS);
2023 }
2024 
2025 static int tc_dump_tclass_qdisc(struct Qdisc *q, struct sk_buff *skb,
2026                                 struct tcmsg *tcm, struct netlink_callback *cb,
2027                                 int *t_p, int s_t)
2028 {
2029         struct qdisc_dump_args arg;
2030 
2031         if (tc_qdisc_dump_ignore(q, false) ||
2032             *t_p < s_t || !q->ops->cl_ops ||
2033             (tcm->tcm_parent &&
2034              TC_H_MAJ(tcm->tcm_parent) != q->handle)) {
2035                 (*t_p)++;
2036                 return 0;
2037         }
2038         if (*t_p > s_t)
2039                 memset(&cb->args[1], 0, sizeof(cb->args)-sizeof(cb->args[0]));
2040         arg.w.fn = qdisc_class_dump;
2041         arg.skb = skb;
2042         arg.cb = cb;
2043         arg.w.stop  = 0;
2044         arg.w.skip = cb->args[1];
2045         arg.w.count = 0;
2046         q->ops->cl_ops->walk(q, &arg.w);
2047         cb->args[1] = arg.w.count;
2048         if (arg.w.stop)
2049                 return -1;
2050         (*t_p)++;
2051         return 0;
2052 }
2053 
2054 static int tc_dump_tclass_root(struct Qdisc *root, struct sk_buff *skb,
2055                                struct tcmsg *tcm, struct netlink_callback *cb,
2056                                int *t_p, int s_t)
2057 {
2058         struct Qdisc *q;
2059         int b;
2060 
2061         if (!root)
2062                 return 0;
2063 
2064         if (tc_dump_tclass_qdisc(root, skb, tcm, cb, t_p, s_t) < 0)
2065                 return -1;
2066 
2067         if (!qdisc_dev(root))
2068                 return 0;
2069 
2070         if (tcm->tcm_parent) {
2071                 q = qdisc_match_from_root(root, TC_H_MAJ(tcm->tcm_parent));
2072                 if (q && q != root &&
2073                     tc_dump_tclass_qdisc(q, skb, tcm, cb, t_p, s_t) < 0)
2074                         return -1;
2075                 return 0;
2076         }
2077         hash_for_each(qdisc_dev(root)->qdisc_hash, b, q, hash) {
2078                 if (tc_dump_tclass_qdisc(q, skb, tcm, cb, t_p, s_t) < 0)
2079                         return -1;
2080         }
2081 
2082         return 0;
2083 }
2084 
2085 static int tc_dump_tclass(struct sk_buff *skb, struct netlink_callback *cb)
2086 {
2087         struct tcmsg *tcm = nlmsg_data(cb->nlh);
2088         struct net *net = sock_net(skb->sk);
2089         struct netdev_queue *dev_queue;
2090         struct net_device *dev;
2091         int t, s_t;
2092 
2093         if (nlmsg_len(cb->nlh) < sizeof(*tcm))
2094                 return 0;
2095         dev = dev_get_by_index(net, tcm->tcm_ifindex);
2096         if (!dev)
2097                 return 0;
2098 
2099         s_t = cb->args[0];
2100         t = 0;
2101 
2102         if (tc_dump_tclass_root(dev->qdisc, skb, tcm, cb, &t, s_t) < 0)
2103                 goto done;
2104 
2105         dev_queue = dev_ingress_queue(dev);
2106         if (dev_queue &&
2107             tc_dump_tclass_root(dev_queue->qdisc_sleeping, skb, tcm, cb,
2108                                 &t, s_t) < 0)
2109                 goto done;
2110 
2111 done:
2112         cb->args[0] = t;
2113 
2114         dev_put(dev);
2115         return skb->len;
2116 }
2117 
2118 #ifdef CONFIG_PROC_FS
2119 static int psched_show(struct seq_file *seq, void *v)
2120 {
2121         seq_printf(seq, "%08x %08x %08x %08x\n",
2122                    (u32)NSEC_PER_USEC, (u32)PSCHED_TICKS2NS(1),
2123                    1000000,
2124                    (u32)NSEC_PER_SEC / hrtimer_resolution);
2125 
2126         return 0;
2127 }
2128 
2129 static int __net_init psched_net_init(struct net *net)
2130 {
2131         struct proc_dir_entry *e;
2132 
2133         e = proc_create_single("psched", 0, net->proc_net, psched_show);
2134         if (e == NULL)
2135                 return -ENOMEM;
2136 
2137         return 0;
2138 }
2139 
2140 static void __net_exit psched_net_exit(struct net *net)
2141 {
2142         remove_proc_entry("psched", net->proc_net);
2143 }
2144 #else
2145 static int __net_init psched_net_init(struct net *net)
2146 {
2147         return 0;
2148 }
2149 
2150 static void __net_exit psched_net_exit(struct net *net)
2151 {
2152 }
2153 #endif
2154 
2155 static struct pernet_operations psched_net_ops = {
2156         .init = psched_net_init,
2157         .exit = psched_net_exit,
2158 };
2159 
2160 static int __init pktsched_init(void)
2161 {
2162         int err;
2163 
2164         err = register_pernet_subsys(&psched_net_ops);
2165         if (err) {
2166                 pr_err("pktsched_init: "
2167                        "cannot initialize per netns operations\n");
2168                 return err;
2169         }
2170 
2171         register_qdisc(&pfifo_fast_ops);
2172         register_qdisc(&pfifo_qdisc_ops);
2173         register_qdisc(&bfifo_qdisc_ops);
2174         register_qdisc(&pfifo_head_drop_qdisc_ops);
2175         register_qdisc(&mq_qdisc_ops);
2176         register_qdisc(&noqueue_qdisc_ops);
2177 
2178         rtnl_register(PF_UNSPEC, RTM_NEWQDISC, tc_modify_qdisc, NULL, 0);
2179         rtnl_register(PF_UNSPEC, RTM_DELQDISC, tc_get_qdisc, NULL, 0);
2180         rtnl_register(PF_UNSPEC, RTM_GETQDISC, tc_get_qdisc, tc_dump_qdisc,
2181                       0);
2182         rtnl_register(PF_UNSPEC, RTM_NEWTCLASS, tc_ctl_tclass, NULL, 0);
2183         rtnl_register(PF_UNSPEC, RTM_DELTCLASS, tc_ctl_tclass, NULL, 0);
2184         rtnl_register(PF_UNSPEC, RTM_GETTCLASS, tc_ctl_tclass, tc_dump_tclass,
2185                       0);
2186 
2187         return 0;
2188 }
2189 
2190 subsys_initcall(pktsched_init);
2191 

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