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