[NET]: Wrap netdevice hardware header creation.
[linux-2.6] / net / sched / sch_api.c
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
31 #include <net/net_namespace.h>
32 #include <net/netlink.h>
33 #include <net/pkt_sched.h>
34
35 static int qdisc_notify(struct sk_buff *oskb, struct nlmsghdr *n, u32 clid,
36                         struct Qdisc *old, struct Qdisc *new);
37 static int tclass_notify(struct sk_buff *oskb, struct nlmsghdr *n,
38                          struct Qdisc *q, unsigned long cl, int event);
39
40 /*
41
42    Short review.
43    -------------
44
45    This file consists of two interrelated parts:
46
47    1. queueing disciplines manager frontend.
48    2. traffic classes manager frontend.
49
50    Generally, queueing discipline ("qdisc") is a black box,
51    which is able to enqueue packets and to dequeue them (when
52    device is ready to send something) in order and at times
53    determined by algorithm hidden in it.
54
55    qdisc's are divided to two categories:
56    - "queues", which have no internal structure visible from outside.
57    - "schedulers", which split all the packets to "traffic classes",
58      using "packet classifiers" (look at cls_api.c)
59
60    In turn, classes may have child qdiscs (as rule, queues)
61    attached to them etc. etc. etc.
62
63    The goal of the routines in this file is to translate
64    information supplied by user in the form of handles
65    to more intelligible for kernel form, to make some sanity
66    checks and part of work, which is common to all qdiscs
67    and to provide rtnetlink notifications.
68
69    All real intelligent work is done inside qdisc modules.
70
71
72
73    Every discipline has two major routines: enqueue and dequeue.
74
75    ---dequeue
76
77    dequeue usually returns a skb to send. It is allowed to return NULL,
78    but it does not mean that queue is empty, it just means that
79    discipline does not want to send anything this time.
80    Queue is really empty if q->q.qlen == 0.
81    For complicated disciplines with multiple queues q->q is not
82    real packet queue, but however q->q.qlen must be valid.
83
84    ---enqueue
85
86    enqueue returns 0, if packet was enqueued successfully.
87    If packet (this one or another one) was dropped, it returns
88    not zero error code.
89    NET_XMIT_DROP        - this packet dropped
90      Expected action: do not backoff, but wait until queue will clear.
91    NET_XMIT_CN          - probably this packet enqueued, but another one dropped.
92      Expected action: backoff or ignore
93    NET_XMIT_POLICED     - dropped by police.
94      Expected action: backoff or error to real-time apps.
95
96    Auxiliary routines:
97
98    ---requeue
99
100    requeues once dequeued packet. It is used for non-standard or
101    just buggy devices, which can defer output even if dev->tbusy=0.
102
103    ---reset
104
105    returns qdisc to initial state: purge all buffers, clear all
106    timers, counters (except for statistics) etc.
107
108    ---init
109
110    initializes newly created qdisc.
111
112    ---destroy
113
114    destroys resources allocated by init and during lifetime of qdisc.
115
116    ---change
117
118    changes qdisc parameters.
119  */
120
121 /* Protects list of registered TC modules. It is pure SMP lock. */
122 static DEFINE_RWLOCK(qdisc_mod_lock);
123
124
125 /************************************************
126  *      Queueing disciplines manipulation.      *
127  ************************************************/
128
129
130 /* The list of all installed queueing disciplines. */
131
132 static struct Qdisc_ops *qdisc_base;
133
134 /* Register/uregister queueing discipline */
135
136 int register_qdisc(struct Qdisc_ops *qops)
137 {
138         struct Qdisc_ops *q, **qp;
139         int rc = -EEXIST;
140
141         write_lock(&qdisc_mod_lock);
142         for (qp = &qdisc_base; (q = *qp) != NULL; qp = &q->next)
143                 if (!strcmp(qops->id, q->id))
144                         goto out;
145
146         if (qops->enqueue == NULL)
147                 qops->enqueue = noop_qdisc_ops.enqueue;
148         if (qops->requeue == NULL)
149                 qops->requeue = noop_qdisc_ops.requeue;
150         if (qops->dequeue == NULL)
151                 qops->dequeue = noop_qdisc_ops.dequeue;
152
153         qops->next = NULL;
154         *qp = qops;
155         rc = 0;
156 out:
157         write_unlock(&qdisc_mod_lock);
158         return rc;
159 }
160
161 int unregister_qdisc(struct Qdisc_ops *qops)
162 {
163         struct Qdisc_ops *q, **qp;
164         int err = -ENOENT;
165
166         write_lock(&qdisc_mod_lock);
167         for (qp = &qdisc_base; (q=*qp)!=NULL; qp = &q->next)
168                 if (q == qops)
169                         break;
170         if (q) {
171                 *qp = q->next;
172                 q->next = NULL;
173                 err = 0;
174         }
175         write_unlock(&qdisc_mod_lock);
176         return err;
177 }
178
179 /* We know handle. Find qdisc among all qdisc's attached to device
180    (root qdisc, all its children, children of children etc.)
181  */
182
183 struct Qdisc *qdisc_lookup(struct net_device *dev, u32 handle)
184 {
185         struct Qdisc *q;
186
187         list_for_each_entry(q, &dev->qdisc_list, list) {
188                 if (q->handle == handle)
189                         return q;
190         }
191         return NULL;
192 }
193
194 static struct Qdisc *qdisc_leaf(struct Qdisc *p, u32 classid)
195 {
196         unsigned long cl;
197         struct Qdisc *leaf;
198         struct Qdisc_class_ops *cops = p->ops->cl_ops;
199
200         if (cops == NULL)
201                 return NULL;
202         cl = cops->get(p, classid);
203
204         if (cl == 0)
205                 return NULL;
206         leaf = cops->leaf(p, cl);
207         cops->put(p, cl);
208         return leaf;
209 }
210
211 /* Find queueing discipline by name */
212
213 static struct Qdisc_ops *qdisc_lookup_ops(struct rtattr *kind)
214 {
215         struct Qdisc_ops *q = NULL;
216
217         if (kind) {
218                 read_lock(&qdisc_mod_lock);
219                 for (q = qdisc_base; q; q = q->next) {
220                         if (rtattr_strcmp(kind, q->id) == 0) {
221                                 if (!try_module_get(q->owner))
222                                         q = NULL;
223                                 break;
224                         }
225                 }
226                 read_unlock(&qdisc_mod_lock);
227         }
228         return q;
229 }
230
231 static struct qdisc_rate_table *qdisc_rtab_list;
232
233 struct qdisc_rate_table *qdisc_get_rtab(struct tc_ratespec *r, struct rtattr *tab)
234 {
235         struct qdisc_rate_table *rtab;
236
237         for (rtab = qdisc_rtab_list; rtab; rtab = rtab->next) {
238                 if (memcmp(&rtab->rate, r, sizeof(struct tc_ratespec)) == 0) {
239                         rtab->refcnt++;
240                         return rtab;
241                 }
242         }
243
244         if (tab == NULL || r->rate == 0 || r->cell_log == 0 || RTA_PAYLOAD(tab) != 1024)
245                 return NULL;
246
247         rtab = kmalloc(sizeof(*rtab), GFP_KERNEL);
248         if (rtab) {
249                 rtab->rate = *r;
250                 rtab->refcnt = 1;
251                 memcpy(rtab->data, RTA_DATA(tab), 1024);
252                 rtab->next = qdisc_rtab_list;
253                 qdisc_rtab_list = rtab;
254         }
255         return rtab;
256 }
257
258 void qdisc_put_rtab(struct qdisc_rate_table *tab)
259 {
260         struct qdisc_rate_table *rtab, **rtabp;
261
262         if (!tab || --tab->refcnt)
263                 return;
264
265         for (rtabp = &qdisc_rtab_list; (rtab=*rtabp) != NULL; rtabp = &rtab->next) {
266                 if (rtab == tab) {
267                         *rtabp = rtab->next;
268                         kfree(rtab);
269                         return;
270                 }
271         }
272 }
273
274 static enum hrtimer_restart qdisc_watchdog(struct hrtimer *timer)
275 {
276         struct qdisc_watchdog *wd = container_of(timer, struct qdisc_watchdog,
277                                                  timer);
278         struct net_device *dev = wd->qdisc->dev;
279
280         wd->qdisc->flags &= ~TCQ_F_THROTTLED;
281         smp_wmb();
282         netif_schedule(dev);
283
284         return HRTIMER_NORESTART;
285 }
286
287 void qdisc_watchdog_init(struct qdisc_watchdog *wd, struct Qdisc *qdisc)
288 {
289         hrtimer_init(&wd->timer, CLOCK_MONOTONIC, HRTIMER_MODE_ABS);
290         wd->timer.function = qdisc_watchdog;
291         wd->qdisc = qdisc;
292 }
293 EXPORT_SYMBOL(qdisc_watchdog_init);
294
295 void qdisc_watchdog_schedule(struct qdisc_watchdog *wd, psched_time_t expires)
296 {
297         ktime_t time;
298
299         wd->qdisc->flags |= TCQ_F_THROTTLED;
300         time = ktime_set(0, 0);
301         time = ktime_add_ns(time, PSCHED_US2NS(expires));
302         hrtimer_start(&wd->timer, time, HRTIMER_MODE_ABS);
303 }
304 EXPORT_SYMBOL(qdisc_watchdog_schedule);
305
306 void qdisc_watchdog_cancel(struct qdisc_watchdog *wd)
307 {
308         hrtimer_cancel(&wd->timer);
309         wd->qdisc->flags &= ~TCQ_F_THROTTLED;
310 }
311 EXPORT_SYMBOL(qdisc_watchdog_cancel);
312
313 /* Allocate an unique handle from space managed by kernel */
314
315 static u32 qdisc_alloc_handle(struct net_device *dev)
316 {
317         int i = 0x10000;
318         static u32 autohandle = TC_H_MAKE(0x80000000U, 0);
319
320         do {
321                 autohandle += TC_H_MAKE(0x10000U, 0);
322                 if (autohandle == TC_H_MAKE(TC_H_ROOT, 0))
323                         autohandle = TC_H_MAKE(0x80000000U, 0);
324         } while (qdisc_lookup(dev, autohandle) && --i > 0);
325
326         return i>0 ? autohandle : 0;
327 }
328
329 /* Attach toplevel qdisc to device dev */
330
331 static struct Qdisc *
332 dev_graft_qdisc(struct net_device *dev, struct Qdisc *qdisc)
333 {
334         struct Qdisc *oqdisc;
335
336         if (dev->flags & IFF_UP)
337                 dev_deactivate(dev);
338
339         qdisc_lock_tree(dev);
340         if (qdisc && qdisc->flags&TCQ_F_INGRESS) {
341                 oqdisc = dev->qdisc_ingress;
342                 /* Prune old scheduler */
343                 if (oqdisc && atomic_read(&oqdisc->refcnt) <= 1) {
344                         /* delete */
345                         qdisc_reset(oqdisc);
346                         dev->qdisc_ingress = NULL;
347                 } else {  /* new */
348                         dev->qdisc_ingress = qdisc;
349                 }
350
351         } else {
352
353                 oqdisc = dev->qdisc_sleeping;
354
355                 /* Prune old scheduler */
356                 if (oqdisc && atomic_read(&oqdisc->refcnt) <= 1)
357                         qdisc_reset(oqdisc);
358
359                 /* ... and graft new one */
360                 if (qdisc == NULL)
361                         qdisc = &noop_qdisc;
362                 dev->qdisc_sleeping = qdisc;
363                 dev->qdisc = &noop_qdisc;
364         }
365
366         qdisc_unlock_tree(dev);
367
368         if (dev->flags & IFF_UP)
369                 dev_activate(dev);
370
371         return oqdisc;
372 }
373
374 void qdisc_tree_decrease_qlen(struct Qdisc *sch, unsigned int n)
375 {
376         struct Qdisc_class_ops *cops;
377         unsigned long cl;
378         u32 parentid;
379
380         if (n == 0)
381                 return;
382         while ((parentid = sch->parent)) {
383                 sch = qdisc_lookup(sch->dev, TC_H_MAJ(parentid));
384                 if (sch == NULL) {
385                         WARN_ON(parentid != TC_H_ROOT);
386                         return;
387                 }
388                 cops = sch->ops->cl_ops;
389                 if (cops->qlen_notify) {
390                         cl = cops->get(sch, parentid);
391                         cops->qlen_notify(sch, cl);
392                         cops->put(sch, cl);
393                 }
394                 sch->q.qlen -= n;
395         }
396 }
397 EXPORT_SYMBOL(qdisc_tree_decrease_qlen);
398
399 /* Graft qdisc "new" to class "classid" of qdisc "parent" or
400    to device "dev".
401
402    Old qdisc is not destroyed but returned in *old.
403  */
404
405 static int qdisc_graft(struct net_device *dev, struct Qdisc *parent,
406                        u32 classid,
407                        struct Qdisc *new, struct Qdisc **old)
408 {
409         int err = 0;
410         struct Qdisc *q = *old;
411
412
413         if (parent == NULL) {
414                 if (q && q->flags&TCQ_F_INGRESS) {
415                         *old = dev_graft_qdisc(dev, q);
416                 } else {
417                         *old = dev_graft_qdisc(dev, new);
418                 }
419         } else {
420                 struct Qdisc_class_ops *cops = parent->ops->cl_ops;
421
422                 err = -EINVAL;
423
424                 if (cops) {
425                         unsigned long cl = cops->get(parent, classid);
426                         if (cl) {
427                                 err = cops->graft(parent, cl, new, old);
428                                 cops->put(parent, cl);
429                         }
430                 }
431         }
432         return err;
433 }
434
435 /*
436    Allocate and initialize new qdisc.
437
438    Parameters are passed via opt.
439  */
440
441 static struct Qdisc *
442 qdisc_create(struct net_device *dev, u32 parent, u32 handle,
443            struct rtattr **tca, int *errp)
444 {
445         int err;
446         struct rtattr *kind = tca[TCA_KIND-1];
447         struct Qdisc *sch;
448         struct Qdisc_ops *ops;
449
450         ops = qdisc_lookup_ops(kind);
451 #ifdef CONFIG_KMOD
452         if (ops == NULL && kind != NULL) {
453                 char name[IFNAMSIZ];
454                 if (rtattr_strlcpy(name, kind, IFNAMSIZ) < IFNAMSIZ) {
455                         /* We dropped the RTNL semaphore in order to
456                          * perform the module load.  So, even if we
457                          * succeeded in loading the module we have to
458                          * tell the caller to replay the request.  We
459                          * indicate this using -EAGAIN.
460                          * We replay the request because the device may
461                          * go away in the mean time.
462                          */
463                         rtnl_unlock();
464                         request_module("sch_%s", name);
465                         rtnl_lock();
466                         ops = qdisc_lookup_ops(kind);
467                         if (ops != NULL) {
468                                 /* We will try again qdisc_lookup_ops,
469                                  * so don't keep a reference.
470                                  */
471                                 module_put(ops->owner);
472                                 err = -EAGAIN;
473                                 goto err_out;
474                         }
475                 }
476         }
477 #endif
478
479         err = -ENOENT;
480         if (ops == NULL)
481                 goto err_out;
482
483         sch = qdisc_alloc(dev, ops);
484         if (IS_ERR(sch)) {
485                 err = PTR_ERR(sch);
486                 goto err_out2;
487         }
488
489         sch->parent = parent;
490
491         if (handle == TC_H_INGRESS) {
492                 sch->flags |= TCQ_F_INGRESS;
493                 sch->stats_lock = &dev->ingress_lock;
494                 handle = TC_H_MAKE(TC_H_INGRESS, 0);
495         } else {
496                 sch->stats_lock = &dev->queue_lock;
497                 if (handle == 0) {
498                         handle = qdisc_alloc_handle(dev);
499                         err = -ENOMEM;
500                         if (handle == 0)
501                                 goto err_out3;
502                 }
503         }
504
505         sch->handle = handle;
506
507         if (!ops->init || (err = ops->init(sch, tca[TCA_OPTIONS-1])) == 0) {
508                 if (tca[TCA_RATE-1]) {
509                         err = gen_new_estimator(&sch->bstats, &sch->rate_est,
510                                                 sch->stats_lock,
511                                                 tca[TCA_RATE-1]);
512                         if (err) {
513                                 /*
514                                  * Any broken qdiscs that would require
515                                  * a ops->reset() here? The qdisc was never
516                                  * in action so it shouldn't be necessary.
517                                  */
518                                 if (ops->destroy)
519                                         ops->destroy(sch);
520                                 goto err_out3;
521                         }
522                 }
523                 qdisc_lock_tree(dev);
524                 list_add_tail(&sch->list, &dev->qdisc_list);
525                 qdisc_unlock_tree(dev);
526
527                 return sch;
528         }
529 err_out3:
530         dev_put(dev);
531         kfree((char *) sch - sch->padded);
532 err_out2:
533         module_put(ops->owner);
534 err_out:
535         *errp = err;
536         return NULL;
537 }
538
539 static int qdisc_change(struct Qdisc *sch, struct rtattr **tca)
540 {
541         if (tca[TCA_OPTIONS-1]) {
542                 int err;
543
544                 if (sch->ops->change == NULL)
545                         return -EINVAL;
546                 err = sch->ops->change(sch, tca[TCA_OPTIONS-1]);
547                 if (err)
548                         return err;
549         }
550         if (tca[TCA_RATE-1])
551                 gen_replace_estimator(&sch->bstats, &sch->rate_est,
552                         sch->stats_lock, tca[TCA_RATE-1]);
553         return 0;
554 }
555
556 struct check_loop_arg
557 {
558         struct qdisc_walker     w;
559         struct Qdisc            *p;
560         int                     depth;
561 };
562
563 static int check_loop_fn(struct Qdisc *q, unsigned long cl, struct qdisc_walker *w);
564
565 static int check_loop(struct Qdisc *q, struct Qdisc *p, int depth)
566 {
567         struct check_loop_arg   arg;
568
569         if (q->ops->cl_ops == NULL)
570                 return 0;
571
572         arg.w.stop = arg.w.skip = arg.w.count = 0;
573         arg.w.fn = check_loop_fn;
574         arg.depth = depth;
575         arg.p = p;
576         q->ops->cl_ops->walk(q, &arg.w);
577         return arg.w.stop ? -ELOOP : 0;
578 }
579
580 static int
581 check_loop_fn(struct Qdisc *q, unsigned long cl, struct qdisc_walker *w)
582 {
583         struct Qdisc *leaf;
584         struct Qdisc_class_ops *cops = q->ops->cl_ops;
585         struct check_loop_arg *arg = (struct check_loop_arg *)w;
586
587         leaf = cops->leaf(q, cl);
588         if (leaf) {
589                 if (leaf == arg->p || arg->depth > 7)
590                         return -ELOOP;
591                 return check_loop(leaf, arg->p, arg->depth + 1);
592         }
593         return 0;
594 }
595
596 /*
597  * Delete/get qdisc.
598  */
599
600 static int tc_get_qdisc(struct sk_buff *skb, struct nlmsghdr *n, void *arg)
601 {
602         struct tcmsg *tcm = NLMSG_DATA(n);
603         struct rtattr **tca = arg;
604         struct net_device *dev;
605         u32 clid = tcm->tcm_parent;
606         struct Qdisc *q = NULL;
607         struct Qdisc *p = NULL;
608         int err;
609
610         if ((dev = __dev_get_by_index(&init_net, tcm->tcm_ifindex)) == NULL)
611                 return -ENODEV;
612
613         if (clid) {
614                 if (clid != TC_H_ROOT) {
615                         if (TC_H_MAJ(clid) != TC_H_MAJ(TC_H_INGRESS)) {
616                                 if ((p = qdisc_lookup(dev, TC_H_MAJ(clid))) == NULL)
617                                         return -ENOENT;
618                                 q = qdisc_leaf(p, clid);
619                         } else { /* ingress */
620                                 q = dev->qdisc_ingress;
621                         }
622                 } else {
623                         q = dev->qdisc_sleeping;
624                 }
625                 if (!q)
626                         return -ENOENT;
627
628                 if (tcm->tcm_handle && q->handle != tcm->tcm_handle)
629                         return -EINVAL;
630         } else {
631                 if ((q = qdisc_lookup(dev, tcm->tcm_handle)) == NULL)
632                         return -ENOENT;
633         }
634
635         if (tca[TCA_KIND-1] && rtattr_strcmp(tca[TCA_KIND-1], q->ops->id))
636                 return -EINVAL;
637
638         if (n->nlmsg_type == RTM_DELQDISC) {
639                 if (!clid)
640                         return -EINVAL;
641                 if (q->handle == 0)
642                         return -ENOENT;
643                 if ((err = qdisc_graft(dev, p, clid, NULL, &q)) != 0)
644                         return err;
645                 if (q) {
646                         qdisc_notify(skb, n, clid, q, NULL);
647                         qdisc_lock_tree(dev);
648                         qdisc_destroy(q);
649                         qdisc_unlock_tree(dev);
650                 }
651         } else {
652                 qdisc_notify(skb, n, clid, NULL, q);
653         }
654         return 0;
655 }
656
657 /*
658    Create/change qdisc.
659  */
660
661 static int tc_modify_qdisc(struct sk_buff *skb, struct nlmsghdr *n, void *arg)
662 {
663         struct tcmsg *tcm;
664         struct rtattr **tca;
665         struct net_device *dev;
666         u32 clid;
667         struct Qdisc *q, *p;
668         int err;
669
670 replay:
671         /* Reinit, just in case something touches this. */
672         tcm = NLMSG_DATA(n);
673         tca = arg;
674         clid = tcm->tcm_parent;
675         q = p = NULL;
676
677         if ((dev = __dev_get_by_index(&init_net, tcm->tcm_ifindex)) == NULL)
678                 return -ENODEV;
679
680         if (clid) {
681                 if (clid != TC_H_ROOT) {
682                         if (clid != TC_H_INGRESS) {
683                                 if ((p = qdisc_lookup(dev, TC_H_MAJ(clid))) == NULL)
684                                         return -ENOENT;
685                                 q = qdisc_leaf(p, clid);
686                         } else { /*ingress */
687                                 q = dev->qdisc_ingress;
688                         }
689                 } else {
690                         q = dev->qdisc_sleeping;
691                 }
692
693                 /* It may be default qdisc, ignore it */
694                 if (q && q->handle == 0)
695                         q = NULL;
696
697                 if (!q || !tcm->tcm_handle || q->handle != tcm->tcm_handle) {
698                         if (tcm->tcm_handle) {
699                                 if (q && !(n->nlmsg_flags&NLM_F_REPLACE))
700                                         return -EEXIST;
701                                 if (TC_H_MIN(tcm->tcm_handle))
702                                         return -EINVAL;
703                                 if ((q = qdisc_lookup(dev, tcm->tcm_handle)) == NULL)
704                                         goto create_n_graft;
705                                 if (n->nlmsg_flags&NLM_F_EXCL)
706                                         return -EEXIST;
707                                 if (tca[TCA_KIND-1] && rtattr_strcmp(tca[TCA_KIND-1], q->ops->id))
708                                         return -EINVAL;
709                                 if (q == p ||
710                                     (p && check_loop(q, p, 0)))
711                                         return -ELOOP;
712                                 atomic_inc(&q->refcnt);
713                                 goto graft;
714                         } else {
715                                 if (q == NULL)
716                                         goto create_n_graft;
717
718                                 /* This magic test requires explanation.
719                                  *
720                                  *   We know, that some child q is already
721                                  *   attached to this parent and have choice:
722                                  *   either to change it or to create/graft new one.
723                                  *
724                                  *   1. We are allowed to create/graft only
725                                  *   if CREATE and REPLACE flags are set.
726                                  *
727                                  *   2. If EXCL is set, requestor wanted to say,
728                                  *   that qdisc tcm_handle is not expected
729                                  *   to exist, so that we choose create/graft too.
730                                  *
731                                  *   3. The last case is when no flags are set.
732                                  *   Alas, it is sort of hole in API, we
733                                  *   cannot decide what to do unambiguously.
734                                  *   For now we select create/graft, if
735                                  *   user gave KIND, which does not match existing.
736                                  */
737                                 if ((n->nlmsg_flags&NLM_F_CREATE) &&
738                                     (n->nlmsg_flags&NLM_F_REPLACE) &&
739                                     ((n->nlmsg_flags&NLM_F_EXCL) ||
740                                      (tca[TCA_KIND-1] &&
741                                       rtattr_strcmp(tca[TCA_KIND-1], q->ops->id))))
742                                         goto create_n_graft;
743                         }
744                 }
745         } else {
746                 if (!tcm->tcm_handle)
747                         return -EINVAL;
748                 q = qdisc_lookup(dev, tcm->tcm_handle);
749         }
750
751         /* Change qdisc parameters */
752         if (q == NULL)
753                 return -ENOENT;
754         if (n->nlmsg_flags&NLM_F_EXCL)
755                 return -EEXIST;
756         if (tca[TCA_KIND-1] && rtattr_strcmp(tca[TCA_KIND-1], q->ops->id))
757                 return -EINVAL;
758         err = qdisc_change(q, tca);
759         if (err == 0)
760                 qdisc_notify(skb, n, clid, NULL, q);
761         return err;
762
763 create_n_graft:
764         if (!(n->nlmsg_flags&NLM_F_CREATE))
765                 return -ENOENT;
766         if (clid == TC_H_INGRESS)
767                 q = qdisc_create(dev, tcm->tcm_parent, tcm->tcm_parent,
768                                  tca, &err);
769         else
770                 q = qdisc_create(dev, tcm->tcm_parent, tcm->tcm_handle,
771                                  tca, &err);
772         if (q == NULL) {
773                 if (err == -EAGAIN)
774                         goto replay;
775                 return err;
776         }
777
778 graft:
779         if (1) {
780                 struct Qdisc *old_q = NULL;
781                 err = qdisc_graft(dev, p, clid, q, &old_q);
782                 if (err) {
783                         if (q) {
784                                 qdisc_lock_tree(dev);
785                                 qdisc_destroy(q);
786                                 qdisc_unlock_tree(dev);
787                         }
788                         return err;
789                 }
790                 qdisc_notify(skb, n, clid, old_q, q);
791                 if (old_q) {
792                         qdisc_lock_tree(dev);
793                         qdisc_destroy(old_q);
794                         qdisc_unlock_tree(dev);
795                 }
796         }
797         return 0;
798 }
799
800 static int tc_fill_qdisc(struct sk_buff *skb, struct Qdisc *q, u32 clid,
801                          u32 pid, u32 seq, u16 flags, int event)
802 {
803         struct tcmsg *tcm;
804         struct nlmsghdr  *nlh;
805         unsigned char *b = skb_tail_pointer(skb);
806         struct gnet_dump d;
807
808         nlh = NLMSG_NEW(skb, pid, seq, event, sizeof(*tcm), flags);
809         tcm = NLMSG_DATA(nlh);
810         tcm->tcm_family = AF_UNSPEC;
811         tcm->tcm__pad1 = 0;
812         tcm->tcm__pad2 = 0;
813         tcm->tcm_ifindex = q->dev->ifindex;
814         tcm->tcm_parent = clid;
815         tcm->tcm_handle = q->handle;
816         tcm->tcm_info = atomic_read(&q->refcnt);
817         RTA_PUT(skb, TCA_KIND, IFNAMSIZ, q->ops->id);
818         if (q->ops->dump && q->ops->dump(q, skb) < 0)
819                 goto rtattr_failure;
820         q->qstats.qlen = q->q.qlen;
821
822         if (gnet_stats_start_copy_compat(skb, TCA_STATS2, TCA_STATS,
823                         TCA_XSTATS, q->stats_lock, &d) < 0)
824                 goto rtattr_failure;
825
826         if (q->ops->dump_stats && q->ops->dump_stats(q, &d) < 0)
827                 goto rtattr_failure;
828
829         if (gnet_stats_copy_basic(&d, &q->bstats) < 0 ||
830             gnet_stats_copy_rate_est(&d, &q->rate_est) < 0 ||
831             gnet_stats_copy_queue(&d, &q->qstats) < 0)
832                 goto rtattr_failure;
833
834         if (gnet_stats_finish_copy(&d) < 0)
835                 goto rtattr_failure;
836
837         nlh->nlmsg_len = skb_tail_pointer(skb) - b;
838         return skb->len;
839
840 nlmsg_failure:
841 rtattr_failure:
842         nlmsg_trim(skb, b);
843         return -1;
844 }
845
846 static int qdisc_notify(struct sk_buff *oskb, struct nlmsghdr *n,
847                         u32 clid, struct Qdisc *old, struct Qdisc *new)
848 {
849         struct sk_buff *skb;
850         u32 pid = oskb ? NETLINK_CB(oskb).pid : 0;
851
852         skb = alloc_skb(NLMSG_GOODSIZE, GFP_KERNEL);
853         if (!skb)
854                 return -ENOBUFS;
855
856         if (old && old->handle) {
857                 if (tc_fill_qdisc(skb, old, clid, pid, n->nlmsg_seq, 0, RTM_DELQDISC) < 0)
858                         goto err_out;
859         }
860         if (new) {
861                 if (tc_fill_qdisc(skb, new, clid, pid, n->nlmsg_seq, old ? NLM_F_REPLACE : 0, RTM_NEWQDISC) < 0)
862                         goto err_out;
863         }
864
865         if (skb->len)
866                 return rtnetlink_send(skb, pid, RTNLGRP_TC, n->nlmsg_flags&NLM_F_ECHO);
867
868 err_out:
869         kfree_skb(skb);
870         return -EINVAL;
871 }
872
873 static int tc_dump_qdisc(struct sk_buff *skb, struct netlink_callback *cb)
874 {
875         int idx, q_idx;
876         int s_idx, s_q_idx;
877         struct net_device *dev;
878         struct Qdisc *q;
879
880         s_idx = cb->args[0];
881         s_q_idx = q_idx = cb->args[1];
882         read_lock(&dev_base_lock);
883         idx = 0;
884         for_each_netdev(&init_net, dev) {
885                 if (idx < s_idx)
886                         goto cont;
887                 if (idx > s_idx)
888                         s_q_idx = 0;
889                 q_idx = 0;
890                 list_for_each_entry(q, &dev->qdisc_list, list) {
891                         if (q_idx < s_q_idx) {
892                                 q_idx++;
893                                 continue;
894                         }
895                         if (tc_fill_qdisc(skb, q, q->parent, NETLINK_CB(cb->skb).pid,
896                                           cb->nlh->nlmsg_seq, NLM_F_MULTI, RTM_NEWQDISC) <= 0)
897                                 goto done;
898                         q_idx++;
899                 }
900 cont:
901                 idx++;
902         }
903
904 done:
905         read_unlock(&dev_base_lock);
906
907         cb->args[0] = idx;
908         cb->args[1] = q_idx;
909
910         return skb->len;
911 }
912
913
914
915 /************************************************
916  *      Traffic classes manipulation.           *
917  ************************************************/
918
919
920
921 static int tc_ctl_tclass(struct sk_buff *skb, struct nlmsghdr *n, void *arg)
922 {
923         struct tcmsg *tcm = NLMSG_DATA(n);
924         struct rtattr **tca = arg;
925         struct net_device *dev;
926         struct Qdisc *q = NULL;
927         struct Qdisc_class_ops *cops;
928         unsigned long cl = 0;
929         unsigned long new_cl;
930         u32 pid = tcm->tcm_parent;
931         u32 clid = tcm->tcm_handle;
932         u32 qid = TC_H_MAJ(clid);
933         int err;
934
935         if ((dev = __dev_get_by_index(&init_net, tcm->tcm_ifindex)) == NULL)
936                 return -ENODEV;
937
938         /*
939            parent == TC_H_UNSPEC - unspecified parent.
940            parent == TC_H_ROOT   - class is root, which has no parent.
941            parent == X:0         - parent is root class.
942            parent == X:Y         - parent is a node in hierarchy.
943            parent == 0:Y         - parent is X:Y, where X:0 is qdisc.
944
945            handle == 0:0         - generate handle from kernel pool.
946            handle == 0:Y         - class is X:Y, where X:0 is qdisc.
947            handle == X:Y         - clear.
948            handle == X:0         - root class.
949          */
950
951         /* Step 1. Determine qdisc handle X:0 */
952
953         if (pid != TC_H_ROOT) {
954                 u32 qid1 = TC_H_MAJ(pid);
955
956                 if (qid && qid1) {
957                         /* If both majors are known, they must be identical. */
958                         if (qid != qid1)
959                                 return -EINVAL;
960                 } else if (qid1) {
961                         qid = qid1;
962                 } else if (qid == 0)
963                         qid = dev->qdisc_sleeping->handle;
964
965                 /* Now qid is genuine qdisc handle consistent
966                    both with parent and child.
967
968                    TC_H_MAJ(pid) still may be unspecified, complete it now.
969                  */
970                 if (pid)
971                         pid = TC_H_MAKE(qid, pid);
972         } else {
973                 if (qid == 0)
974                         qid = dev->qdisc_sleeping->handle;
975         }
976
977         /* OK. Locate qdisc */
978         if ((q = qdisc_lookup(dev, qid)) == NULL)
979                 return -ENOENT;
980
981         /* An check that it supports classes */
982         cops = q->ops->cl_ops;
983         if (cops == NULL)
984                 return -EINVAL;
985
986         /* Now try to get class */
987         if (clid == 0) {
988                 if (pid == TC_H_ROOT)
989                         clid = qid;
990         } else
991                 clid = TC_H_MAKE(qid, clid);
992
993         if (clid)
994                 cl = cops->get(q, clid);
995
996         if (cl == 0) {
997                 err = -ENOENT;
998                 if (n->nlmsg_type != RTM_NEWTCLASS || !(n->nlmsg_flags&NLM_F_CREATE))
999                         goto out;
1000         } else {
1001                 switch (n->nlmsg_type) {
1002                 case RTM_NEWTCLASS:
1003                         err = -EEXIST;
1004                         if (n->nlmsg_flags&NLM_F_EXCL)
1005                                 goto out;
1006                         break;
1007                 case RTM_DELTCLASS:
1008                         err = cops->delete(q, cl);
1009                         if (err == 0)
1010                                 tclass_notify(skb, n, q, cl, RTM_DELTCLASS);
1011                         goto out;
1012                 case RTM_GETTCLASS:
1013                         err = tclass_notify(skb, n, q, cl, RTM_NEWTCLASS);
1014                         goto out;
1015                 default:
1016                         err = -EINVAL;
1017                         goto out;
1018                 }
1019         }
1020
1021         new_cl = cl;
1022         err = cops->change(q, clid, pid, tca, &new_cl);
1023         if (err == 0)
1024                 tclass_notify(skb, n, q, new_cl, RTM_NEWTCLASS);
1025
1026 out:
1027         if (cl)
1028                 cops->put(q, cl);
1029
1030         return err;
1031 }
1032
1033
1034 static int tc_fill_tclass(struct sk_buff *skb, struct Qdisc *q,
1035                           unsigned long cl,
1036                           u32 pid, u32 seq, u16 flags, int event)
1037 {
1038         struct tcmsg *tcm;
1039         struct nlmsghdr  *nlh;
1040         unsigned char *b = skb_tail_pointer(skb);
1041         struct gnet_dump d;
1042         struct Qdisc_class_ops *cl_ops = q->ops->cl_ops;
1043
1044         nlh = NLMSG_NEW(skb, pid, seq, event, sizeof(*tcm), flags);
1045         tcm = NLMSG_DATA(nlh);
1046         tcm->tcm_family = AF_UNSPEC;
1047         tcm->tcm_ifindex = q->dev->ifindex;
1048         tcm->tcm_parent = q->handle;
1049         tcm->tcm_handle = q->handle;
1050         tcm->tcm_info = 0;
1051         RTA_PUT(skb, TCA_KIND, IFNAMSIZ, q->ops->id);
1052         if (cl_ops->dump && cl_ops->dump(q, cl, skb, tcm) < 0)
1053                 goto rtattr_failure;
1054
1055         if (gnet_stats_start_copy_compat(skb, TCA_STATS2, TCA_STATS,
1056                         TCA_XSTATS, q->stats_lock, &d) < 0)
1057                 goto rtattr_failure;
1058
1059         if (cl_ops->dump_stats && cl_ops->dump_stats(q, cl, &d) < 0)
1060                 goto rtattr_failure;
1061
1062         if (gnet_stats_finish_copy(&d) < 0)
1063                 goto rtattr_failure;
1064
1065         nlh->nlmsg_len = skb_tail_pointer(skb) - b;
1066         return skb->len;
1067
1068 nlmsg_failure:
1069 rtattr_failure:
1070         nlmsg_trim(skb, b);
1071         return -1;
1072 }
1073
1074 static int tclass_notify(struct sk_buff *oskb, struct nlmsghdr *n,
1075                           struct Qdisc *q, unsigned long cl, int event)
1076 {
1077         struct sk_buff *skb;
1078         u32 pid = oskb ? NETLINK_CB(oskb).pid : 0;
1079
1080         skb = alloc_skb(NLMSG_GOODSIZE, GFP_KERNEL);
1081         if (!skb)
1082                 return -ENOBUFS;
1083
1084         if (tc_fill_tclass(skb, q, cl, pid, n->nlmsg_seq, 0, event) < 0) {
1085                 kfree_skb(skb);
1086                 return -EINVAL;
1087         }
1088
1089         return rtnetlink_send(skb, pid, RTNLGRP_TC, n->nlmsg_flags&NLM_F_ECHO);
1090 }
1091
1092 struct qdisc_dump_args
1093 {
1094         struct qdisc_walker w;
1095         struct sk_buff *skb;
1096         struct netlink_callback *cb;
1097 };
1098
1099 static int qdisc_class_dump(struct Qdisc *q, unsigned long cl, struct qdisc_walker *arg)
1100 {
1101         struct qdisc_dump_args *a = (struct qdisc_dump_args *)arg;
1102
1103         return tc_fill_tclass(a->skb, q, cl, NETLINK_CB(a->cb->skb).pid,
1104                               a->cb->nlh->nlmsg_seq, NLM_F_MULTI, RTM_NEWTCLASS);
1105 }
1106
1107 static int tc_dump_tclass(struct sk_buff *skb, struct netlink_callback *cb)
1108 {
1109         int t;
1110         int s_t;
1111         struct net_device *dev;
1112         struct Qdisc *q;
1113         struct tcmsg *tcm = (struct tcmsg*)NLMSG_DATA(cb->nlh);
1114         struct qdisc_dump_args arg;
1115
1116         if (cb->nlh->nlmsg_len < NLMSG_LENGTH(sizeof(*tcm)))
1117                 return 0;
1118         if ((dev = dev_get_by_index(&init_net, tcm->tcm_ifindex)) == NULL)
1119                 return 0;
1120
1121         s_t = cb->args[0];
1122         t = 0;
1123
1124         list_for_each_entry(q, &dev->qdisc_list, list) {
1125                 if (t < s_t || !q->ops->cl_ops ||
1126                     (tcm->tcm_parent &&
1127                      TC_H_MAJ(tcm->tcm_parent) != q->handle)) {
1128                         t++;
1129                         continue;
1130                 }
1131                 if (t > s_t)
1132                         memset(&cb->args[1], 0, sizeof(cb->args)-sizeof(cb->args[0]));
1133                 arg.w.fn = qdisc_class_dump;
1134                 arg.skb = skb;
1135                 arg.cb = cb;
1136                 arg.w.stop  = 0;
1137                 arg.w.skip = cb->args[1];
1138                 arg.w.count = 0;
1139                 q->ops->cl_ops->walk(q, &arg.w);
1140                 cb->args[1] = arg.w.count;
1141                 if (arg.w.stop)
1142                         break;
1143                 t++;
1144         }
1145
1146         cb->args[0] = t;
1147
1148         dev_put(dev);
1149         return skb->len;
1150 }
1151
1152 /* Main classifier routine: scans classifier chain attached
1153    to this qdisc, (optionally) tests for protocol and asks
1154    specific classifiers.
1155  */
1156 int tc_classify_compat(struct sk_buff *skb, struct tcf_proto *tp,
1157                        struct tcf_result *res)
1158 {
1159         __be16 protocol = skb->protocol;
1160         int err = 0;
1161
1162         for (; tp; tp = tp->next) {
1163                 if ((tp->protocol == protocol ||
1164                      tp->protocol == htons(ETH_P_ALL)) &&
1165                     (err = tp->classify(skb, tp, res)) >= 0) {
1166 #ifdef CONFIG_NET_CLS_ACT
1167                         if (err != TC_ACT_RECLASSIFY && skb->tc_verd)
1168                                 skb->tc_verd = SET_TC_VERD(skb->tc_verd, 0);
1169 #endif
1170                         return err;
1171                 }
1172         }
1173         return -1;
1174 }
1175 EXPORT_SYMBOL(tc_classify_compat);
1176
1177 int tc_classify(struct sk_buff *skb, struct tcf_proto *tp,
1178                 struct tcf_result *res)
1179 {
1180         int err = 0;
1181         __be16 protocol;
1182 #ifdef CONFIG_NET_CLS_ACT
1183         struct tcf_proto *otp = tp;
1184 reclassify:
1185 #endif
1186         protocol = skb->protocol;
1187
1188         err = tc_classify_compat(skb, tp, res);
1189 #ifdef CONFIG_NET_CLS_ACT
1190         if (err == TC_ACT_RECLASSIFY) {
1191                 u32 verd = G_TC_VERD(skb->tc_verd);
1192                 tp = otp;
1193
1194                 if (verd++ >= MAX_REC_LOOP) {
1195                         printk("rule prio %u protocol %02x reclassify loop, "
1196                                "packet dropped\n",
1197                                tp->prio&0xffff, ntohs(tp->protocol));
1198                         return TC_ACT_SHOT;
1199                 }
1200                 skb->tc_verd = SET_TC_VERD(skb->tc_verd, verd);
1201                 goto reclassify;
1202         }
1203 #endif
1204         return err;
1205 }
1206 EXPORT_SYMBOL(tc_classify);
1207
1208 void tcf_destroy(struct tcf_proto *tp)
1209 {
1210         tp->ops->destroy(tp);
1211         module_put(tp->ops->owner);
1212         kfree(tp);
1213 }
1214
1215 void tcf_destroy_chain(struct tcf_proto *fl)
1216 {
1217         struct tcf_proto *tp;
1218
1219         while ((tp = fl) != NULL) {
1220                 fl = tp->next;
1221                 tcf_destroy(tp);
1222         }
1223 }
1224 EXPORT_SYMBOL(tcf_destroy_chain);
1225
1226 #ifdef CONFIG_PROC_FS
1227 static int psched_show(struct seq_file *seq, void *v)
1228 {
1229         seq_printf(seq, "%08x %08x %08x %08x\n",
1230                    (u32)NSEC_PER_USEC, (u32)PSCHED_US2NS(1),
1231                    1000000,
1232                    (u32)NSEC_PER_SEC/(u32)ktime_to_ns(KTIME_MONOTONIC_RES));
1233
1234         return 0;
1235 }
1236
1237 static int psched_open(struct inode *inode, struct file *file)
1238 {
1239         return single_open(file, psched_show, PDE(inode)->data);
1240 }
1241
1242 static const struct file_operations psched_fops = {
1243         .owner = THIS_MODULE,
1244         .open = psched_open,
1245         .read  = seq_read,
1246         .llseek = seq_lseek,
1247         .release = single_release,
1248 };
1249 #endif
1250
1251 static int __init pktsched_init(void)
1252 {
1253         register_qdisc(&pfifo_qdisc_ops);
1254         register_qdisc(&bfifo_qdisc_ops);
1255         proc_net_fops_create(&init_net, "psched", 0, &psched_fops);
1256
1257         rtnl_register(PF_UNSPEC, RTM_NEWQDISC, tc_modify_qdisc, NULL);
1258         rtnl_register(PF_UNSPEC, RTM_DELQDISC, tc_get_qdisc, NULL);
1259         rtnl_register(PF_UNSPEC, RTM_GETQDISC, tc_get_qdisc, tc_dump_qdisc);
1260         rtnl_register(PF_UNSPEC, RTM_NEWTCLASS, tc_ctl_tclass, NULL);
1261         rtnl_register(PF_UNSPEC, RTM_DELTCLASS, tc_ctl_tclass, NULL);
1262         rtnl_register(PF_UNSPEC, RTM_GETTCLASS, tc_ctl_tclass, tc_dump_tclass);
1263
1264         return 0;
1265 }
1266
1267 subsys_initcall(pktsched_init);
1268
1269 EXPORT_SYMBOL(qdisc_get_rtab);
1270 EXPORT_SYMBOL(qdisc_put_rtab);
1271 EXPORT_SYMBOL(register_qdisc);
1272 EXPORT_SYMBOL(unregister_qdisc);