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