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