aboutsummaryrefslogtreecommitdiffstats
path: root/net/sched/sch_cbq.c
diff options
context:
space:
mode:
authorLinus Torvalds <torvalds@ppc970.osdl.org>2005-04-16 18:20:36 -0400
committerLinus Torvalds <torvalds@ppc970.osdl.org>2005-04-16 18:20:36 -0400
commit1da177e4c3f41524e886b7f1b8a0c1fc7321cac2 (patch)
tree0bba044c4ce775e45a88a51686b5d9f90697ea9d /net/sched/sch_cbq.c
Linux-2.6.12-rc2v2.6.12-rc2
Initial git repository build. I'm not bothering with the full history, even though we have it. We can create a separate "historical" git archive of that later if we want to, and in the meantime it's about 3.2GB when imported into git - space that would just make the early git days unnecessarily complicated, when we don't have a lot of good infrastructure for it. Let it rip!
Diffstat (limited to 'net/sched/sch_cbq.c')
-rw-r--r--net/sched/sch_cbq.c2124
1 files changed, 2124 insertions, 0 deletions
diff --git a/net/sched/sch_cbq.c b/net/sched/sch_cbq.c
new file mode 100644
index 000000000000..d43e3b8cbf6a
--- /dev/null
+++ b/net/sched/sch_cbq.c
@@ -0,0 +1,2124 @@
1/*
2 * net/sched/sch_cbq.c Class-Based Queueing discipline.
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 */
12
13#include <linux/config.h>
14#include <linux/module.h>
15#include <asm/uaccess.h>
16#include <asm/system.h>
17#include <linux/bitops.h>
18#include <linux/types.h>
19#include <linux/kernel.h>
20#include <linux/sched.h>
21#include <linux/string.h>
22#include <linux/mm.h>
23#include <linux/socket.h>
24#include <linux/sockios.h>
25#include <linux/in.h>
26#include <linux/errno.h>
27#include <linux/interrupt.h>
28#include <linux/if_ether.h>
29#include <linux/inet.h>
30#include <linux/netdevice.h>
31#include <linux/etherdevice.h>
32#include <linux/notifier.h>
33#include <net/ip.h>
34#include <net/route.h>
35#include <linux/skbuff.h>
36#include <net/sock.h>
37#include <net/pkt_sched.h>
38
39
40/* Class-Based Queueing (CBQ) algorithm.
41 =======================================
42
43 Sources: [1] Sally Floyd and Van Jacobson, "Link-sharing and Resource
44 Management Models for Packet Networks",
45 IEEE/ACM Transactions on Networking, Vol.3, No.4, 1995
46
47 [2] Sally Floyd, "Notes on CBQ and Guaranteed Service", 1995
48
49 [3] Sally Floyd, "Notes on Class-Based Queueing: Setting
50 Parameters", 1996
51
52 [4] Sally Floyd and Michael Speer, "Experimental Results
53 for Class-Based Queueing", 1998, not published.
54
55 -----------------------------------------------------------------------
56
57 Algorithm skeleton was taken from NS simulator cbq.cc.
58 If someone wants to check this code against the LBL version,
59 he should take into account that ONLY the skeleton was borrowed,
60 the implementation is different. Particularly:
61
62 --- The WRR algorithm is different. Our version looks more
63 reasonable (I hope) and works when quanta are allowed to be
64 less than MTU, which is always the case when real time classes
65 have small rates. Note, that the statement of [3] is
66 incomplete, delay may actually be estimated even if class
67 per-round allotment is less than MTU. Namely, if per-round
68 allotment is W*r_i, and r_1+...+r_k = r < 1
69
70 delay_i <= ([MTU/(W*r_i)]*W*r + W*r + k*MTU)/B
71
72 In the worst case we have IntServ estimate with D = W*r+k*MTU
73 and C = MTU*r. The proof (if correct at all) is trivial.
74
75
76 --- It seems that cbq-2.0 is not very accurate. At least, I cannot
77 interpret some places, which look like wrong translations
78 from NS. Anyone is advised to find these differences
79 and explain to me, why I am wrong 8).
80
81 --- Linux has no EOI event, so that we cannot estimate true class
82 idle time. Workaround is to consider the next dequeue event
83 as sign that previous packet is finished. This is wrong because of
84 internal device queueing, but on a permanently loaded link it is true.
85 Moreover, combined with clock integrator, this scheme looks
86 very close to an ideal solution. */
87
88struct cbq_sched_data;
89
90
91struct cbq_class
92{
93 struct cbq_class *next; /* hash table link */
94 struct cbq_class *next_alive; /* next class with backlog in this priority band */
95
96/* Parameters */
97 u32 classid;
98 unsigned char priority; /* class priority */
99 unsigned char priority2; /* priority to be used after overlimit */
100 unsigned char ewma_log; /* time constant for idle time calculation */
101 unsigned char ovl_strategy;
102#ifdef CONFIG_NET_CLS_POLICE
103 unsigned char police;
104#endif
105
106 u32 defmap;
107
108 /* Link-sharing scheduler parameters */
109 long maxidle; /* Class parameters: see below. */
110 long offtime;
111 long minidle;
112 u32 avpkt;
113 struct qdisc_rate_table *R_tab;
114
115 /* Overlimit strategy parameters */
116 void (*overlimit)(struct cbq_class *cl);
117 long penalty;
118
119 /* General scheduler (WRR) parameters */
120 long allot;
121 long quantum; /* Allotment per WRR round */
122 long weight; /* Relative allotment: see below */
123
124 struct Qdisc *qdisc; /* Ptr to CBQ discipline */
125 struct cbq_class *split; /* Ptr to split node */
126 struct cbq_class *share; /* Ptr to LS parent in the class tree */
127 struct cbq_class *tparent; /* Ptr to tree parent in the class tree */
128 struct cbq_class *borrow; /* NULL if class is bandwidth limited;
129 parent otherwise */
130 struct cbq_class *sibling; /* Sibling chain */
131 struct cbq_class *children; /* Pointer to children chain */
132
133 struct Qdisc *q; /* Elementary queueing discipline */
134
135
136/* Variables */
137 unsigned char cpriority; /* Effective priority */
138 unsigned char delayed;
139 unsigned char level; /* level of the class in hierarchy:
140 0 for leaf classes, and maximal
141 level of children + 1 for nodes.
142 */
143
144 psched_time_t last; /* Last end of service */
145 psched_time_t undertime;
146 long avgidle;
147 long deficit; /* Saved deficit for WRR */
148 unsigned long penalized;
149 struct gnet_stats_basic bstats;
150 struct gnet_stats_queue qstats;
151 struct gnet_stats_rate_est rate_est;
152 spinlock_t *stats_lock;
153 struct tc_cbq_xstats xstats;
154
155 struct tcf_proto *filter_list;
156
157 int refcnt;
158 int filters;
159
160 struct cbq_class *defaults[TC_PRIO_MAX+1];
161};
162
163struct cbq_sched_data
164{
165 struct cbq_class *classes[16]; /* Hash table of all classes */
166 int nclasses[TC_CBQ_MAXPRIO+1];
167 unsigned quanta[TC_CBQ_MAXPRIO+1];
168
169 struct cbq_class link;
170
171 unsigned activemask;
172 struct cbq_class *active[TC_CBQ_MAXPRIO+1]; /* List of all classes
173 with backlog */
174
175#ifdef CONFIG_NET_CLS_POLICE
176 struct cbq_class *rx_class;
177#endif
178 struct cbq_class *tx_class;
179 struct cbq_class *tx_borrowed;
180 int tx_len;
181 psched_time_t now; /* Cached timestamp */
182 psched_time_t now_rt; /* Cached real time */
183 unsigned pmask;
184
185 struct timer_list delay_timer;
186 struct timer_list wd_timer; /* Watchdog timer,
187 started when CBQ has
188 backlog, but cannot
189 transmit just now */
190 long wd_expires;
191 int toplevel;
192 u32 hgenerator;
193};
194
195
196#define L2T(cl,len) ((cl)->R_tab->data[(len)>>(cl)->R_tab->rate.cell_log])
197
198
199static __inline__ unsigned cbq_hash(u32 h)
200{
201 h ^= h>>8;
202 h ^= h>>4;
203 return h&0xF;
204}
205
206static __inline__ struct cbq_class *
207cbq_class_lookup(struct cbq_sched_data *q, u32 classid)
208{
209 struct cbq_class *cl;
210
211 for (cl = q->classes[cbq_hash(classid)]; cl; cl = cl->next)
212 if (cl->classid == classid)
213 return cl;
214 return NULL;
215}
216
217#ifdef CONFIG_NET_CLS_POLICE
218
219static struct cbq_class *
220cbq_reclassify(struct sk_buff *skb, struct cbq_class *this)
221{
222 struct cbq_class *cl, *new;
223
224 for (cl = this->tparent; cl; cl = cl->tparent)
225 if ((new = cl->defaults[TC_PRIO_BESTEFFORT]) != NULL && new != this)
226 return new;
227
228 return NULL;
229}
230
231#endif
232
233/* Classify packet. The procedure is pretty complicated, but
234 it allows us to combine link sharing and priority scheduling
235 transparently.
236
237 Namely, you can put link sharing rules (f.e. route based) at root of CBQ,
238 so that it resolves to split nodes. Then packets are classified
239 by logical priority, or a more specific classifier may be attached
240 to the split node.
241 */
242
243static struct cbq_class *
244cbq_classify(struct sk_buff *skb, struct Qdisc *sch, int *qerr)
245{
246 struct cbq_sched_data *q = qdisc_priv(sch);
247 struct cbq_class *head = &q->link;
248 struct cbq_class **defmap;
249 struct cbq_class *cl = NULL;
250 u32 prio = skb->priority;
251 struct tcf_result res;
252
253 /*
254 * Step 1. If skb->priority points to one of our classes, use it.
255 */
256 if (TC_H_MAJ(prio^sch->handle) == 0 &&
257 (cl = cbq_class_lookup(q, prio)) != NULL)
258 return cl;
259
260 *qerr = NET_XMIT_DROP;
261 for (;;) {
262 int result = 0;
263 defmap = head->defaults;
264
265 /*
266 * Step 2+n. Apply classifier.
267 */
268 if (!head->filter_list || (result = tc_classify(skb, head->filter_list, &res)) < 0)
269 goto fallback;
270
271 if ((cl = (void*)res.class) == NULL) {
272 if (TC_H_MAJ(res.classid))
273 cl = cbq_class_lookup(q, res.classid);
274 else if ((cl = defmap[res.classid&TC_PRIO_MAX]) == NULL)
275 cl = defmap[TC_PRIO_BESTEFFORT];
276
277 if (cl == NULL || cl->level >= head->level)
278 goto fallback;
279 }
280
281#ifdef CONFIG_NET_CLS_ACT
282 switch (result) {
283 case TC_ACT_QUEUED:
284 case TC_ACT_STOLEN:
285 *qerr = NET_XMIT_SUCCESS;
286 case TC_ACT_SHOT:
287 return NULL;
288 }
289#elif defined(CONFIG_NET_CLS_POLICE)
290 switch (result) {
291 case TC_POLICE_RECLASSIFY:
292 return cbq_reclassify(skb, cl);
293 case TC_POLICE_SHOT:
294 return NULL;
295 default:
296 break;
297 }
298#endif
299 if (cl->level == 0)
300 return cl;
301
302 /*
303 * Step 3+n. If classifier selected a link sharing class,
304 * apply agency specific classifier.
305 * Repeat this procdure until we hit a leaf node.
306 */
307 head = cl;
308 }
309
310fallback:
311 cl = head;
312
313 /*
314 * Step 4. No success...
315 */
316 if (TC_H_MAJ(prio) == 0 &&
317 !(cl = head->defaults[prio&TC_PRIO_MAX]) &&
318 !(cl = head->defaults[TC_PRIO_BESTEFFORT]))
319 return head;
320
321 return cl;
322}
323
324/*
325 A packet has just been enqueued on the empty class.
326 cbq_activate_class adds it to the tail of active class list
327 of its priority band.
328 */
329
330static __inline__ void cbq_activate_class(struct cbq_class *cl)
331{
332 struct cbq_sched_data *q = qdisc_priv(cl->qdisc);
333 int prio = cl->cpriority;
334 struct cbq_class *cl_tail;
335
336 cl_tail = q->active[prio];
337 q->active[prio] = cl;
338
339 if (cl_tail != NULL) {
340 cl->next_alive = cl_tail->next_alive;
341 cl_tail->next_alive = cl;
342 } else {
343 cl->next_alive = cl;
344 q->activemask |= (1<<prio);
345 }
346}
347
348/*
349 Unlink class from active chain.
350 Note that this same procedure is done directly in cbq_dequeue*
351 during round-robin procedure.
352 */
353
354static void cbq_deactivate_class(struct cbq_class *this)
355{
356 struct cbq_sched_data *q = qdisc_priv(this->qdisc);
357 int prio = this->cpriority;
358 struct cbq_class *cl;
359 struct cbq_class *cl_prev = q->active[prio];
360
361 do {
362 cl = cl_prev->next_alive;
363 if (cl == this) {
364 cl_prev->next_alive = cl->next_alive;
365 cl->next_alive = NULL;
366
367 if (cl == q->active[prio]) {
368 q->active[prio] = cl_prev;
369 if (cl == q->active[prio]) {
370 q->active[prio] = NULL;
371 q->activemask &= ~(1<<prio);
372 return;
373 }
374 }
375
376 cl = cl_prev->next_alive;
377 return;
378 }
379 } while ((cl_prev = cl) != q->active[prio]);
380}
381
382static void
383cbq_mark_toplevel(struct cbq_sched_data *q, struct cbq_class *cl)
384{
385 int toplevel = q->toplevel;
386
387 if (toplevel > cl->level && !(cl->q->flags&TCQ_F_THROTTLED)) {
388 psched_time_t now;
389 psched_tdiff_t incr;
390
391 PSCHED_GET_TIME(now);
392 incr = PSCHED_TDIFF(now, q->now_rt);
393 PSCHED_TADD2(q->now, incr, now);
394
395 do {
396 if (PSCHED_TLESS(cl->undertime, now)) {
397 q->toplevel = cl->level;
398 return;
399 }
400 } while ((cl=cl->borrow) != NULL && toplevel > cl->level);
401 }
402}
403
404static int
405cbq_enqueue(struct sk_buff *skb, struct Qdisc *sch)
406{
407 struct cbq_sched_data *q = qdisc_priv(sch);
408 int len = skb->len;
409 int ret;
410 struct cbq_class *cl = cbq_classify(skb, sch, &ret);
411
412#ifdef CONFIG_NET_CLS_POLICE
413 q->rx_class = cl;
414#endif
415 if (cl == NULL) {
416 if (ret == NET_XMIT_DROP)
417 sch->qstats.drops++;
418 kfree_skb(skb);
419 return ret;
420 }
421
422#ifdef CONFIG_NET_CLS_POLICE
423 cl->q->__parent = sch;
424#endif
425 if ((ret = cl->q->enqueue(skb, cl->q)) == NET_XMIT_SUCCESS) {
426 sch->q.qlen++;
427 sch->bstats.packets++;
428 sch->bstats.bytes+=len;
429 cbq_mark_toplevel(q, cl);
430 if (!cl->next_alive)
431 cbq_activate_class(cl);
432 return ret;
433 }
434
435 sch->qstats.drops++;
436 cbq_mark_toplevel(q, cl);
437 cl->qstats.drops++;
438 return ret;
439}
440
441static int
442cbq_requeue(struct sk_buff *skb, struct Qdisc *sch)
443{
444 struct cbq_sched_data *q = qdisc_priv(sch);
445 struct cbq_class *cl;
446 int ret;
447
448 if ((cl = q->tx_class) == NULL) {
449 kfree_skb(skb);
450 sch->qstats.drops++;
451 return NET_XMIT_CN;
452 }
453 q->tx_class = NULL;
454
455 cbq_mark_toplevel(q, cl);
456
457#ifdef CONFIG_NET_CLS_POLICE
458 q->rx_class = cl;
459 cl->q->__parent = sch;
460#endif
461 if ((ret = cl->q->ops->requeue(skb, cl->q)) == 0) {
462 sch->q.qlen++;
463 sch->qstats.requeues++;
464 if (!cl->next_alive)
465 cbq_activate_class(cl);
466 return 0;
467 }
468 sch->qstats.drops++;
469 cl->qstats.drops++;
470 return ret;
471}
472
473/* Overlimit actions */
474
475/* TC_CBQ_OVL_CLASSIC: (default) penalize leaf class by adding offtime */
476
477static void cbq_ovl_classic(struct cbq_class *cl)
478{
479 struct cbq_sched_data *q = qdisc_priv(cl->qdisc);
480 psched_tdiff_t delay = PSCHED_TDIFF(cl->undertime, q->now);
481
482 if (!cl->delayed) {
483 delay += cl->offtime;
484
485 /*
486 Class goes to sleep, so that it will have no
487 chance to work avgidle. Let's forgive it 8)
488
489 BTW cbq-2.0 has a crap in this
490 place, apparently they forgot to shift it by cl->ewma_log.
491 */
492 if (cl->avgidle < 0)
493 delay -= (-cl->avgidle) - ((-cl->avgidle) >> cl->ewma_log);
494 if (cl->avgidle < cl->minidle)
495 cl->avgidle = cl->minidle;
496 if (delay <= 0)
497 delay = 1;
498 PSCHED_TADD2(q->now, delay, cl->undertime);
499
500 cl->xstats.overactions++;
501 cl->delayed = 1;
502 }
503 if (q->wd_expires == 0 || q->wd_expires > delay)
504 q->wd_expires = delay;
505
506 /* Dirty work! We must schedule wakeups based on
507 real available rate, rather than leaf rate,
508 which may be tiny (even zero).
509 */
510 if (q->toplevel == TC_CBQ_MAXLEVEL) {
511 struct cbq_class *b;
512 psched_tdiff_t base_delay = q->wd_expires;
513
514 for (b = cl->borrow; b; b = b->borrow) {
515 delay = PSCHED_TDIFF(b->undertime, q->now);
516 if (delay < base_delay) {
517 if (delay <= 0)
518 delay = 1;
519 base_delay = delay;
520 }
521 }
522
523 q->wd_expires = base_delay;
524 }
525}
526
527/* TC_CBQ_OVL_RCLASSIC: penalize by offtime classes in hierarchy, when
528 they go overlimit
529 */
530
531static void cbq_ovl_rclassic(struct cbq_class *cl)
532{
533 struct cbq_sched_data *q = qdisc_priv(cl->qdisc);
534 struct cbq_class *this = cl;
535
536 do {
537 if (cl->level > q->toplevel) {
538 cl = NULL;
539 break;
540 }
541 } while ((cl = cl->borrow) != NULL);
542
543 if (cl == NULL)
544 cl = this;
545 cbq_ovl_classic(cl);
546}
547
548/* TC_CBQ_OVL_DELAY: delay until it will go to underlimit */
549
550static void cbq_ovl_delay(struct cbq_class *cl)
551{
552 struct cbq_sched_data *q = qdisc_priv(cl->qdisc);
553 psched_tdiff_t delay = PSCHED_TDIFF(cl->undertime, q->now);
554
555 if (!cl->delayed) {
556 unsigned long sched = jiffies;
557
558 delay += cl->offtime;
559 if (cl->avgidle < 0)
560 delay -= (-cl->avgidle) - ((-cl->avgidle) >> cl->ewma_log);
561 if (cl->avgidle < cl->minidle)
562 cl->avgidle = cl->minidle;
563 PSCHED_TADD2(q->now, delay, cl->undertime);
564
565 if (delay > 0) {
566 sched += PSCHED_US2JIFFIE(delay) + cl->penalty;
567 cl->penalized = sched;
568 cl->cpriority = TC_CBQ_MAXPRIO;
569 q->pmask |= (1<<TC_CBQ_MAXPRIO);
570 if (del_timer(&q->delay_timer) &&
571 (long)(q->delay_timer.expires - sched) > 0)
572 q->delay_timer.expires = sched;
573 add_timer(&q->delay_timer);
574 cl->delayed = 1;
575 cl->xstats.overactions++;
576 return;
577 }
578 delay = 1;
579 }
580 if (q->wd_expires == 0 || q->wd_expires > delay)
581 q->wd_expires = delay;
582}
583
584/* TC_CBQ_OVL_LOWPRIO: penalize class by lowering its priority band */
585
586static void cbq_ovl_lowprio(struct cbq_class *cl)
587{
588 struct cbq_sched_data *q = qdisc_priv(cl->qdisc);
589
590 cl->penalized = jiffies + cl->penalty;
591
592 if (cl->cpriority != cl->priority2) {
593 cl->cpriority = cl->priority2;
594 q->pmask |= (1<<cl->cpriority);
595 cl->xstats.overactions++;
596 }
597 cbq_ovl_classic(cl);
598}
599
600/* TC_CBQ_OVL_DROP: penalize class by dropping */
601
602static void cbq_ovl_drop(struct cbq_class *cl)
603{
604 if (cl->q->ops->drop)
605 if (cl->q->ops->drop(cl->q))
606 cl->qdisc->q.qlen--;
607 cl->xstats.overactions++;
608 cbq_ovl_classic(cl);
609}
610
611static void cbq_watchdog(unsigned long arg)
612{
613 struct Qdisc *sch = (struct Qdisc*)arg;
614
615 sch->flags &= ~TCQ_F_THROTTLED;
616 netif_schedule(sch->dev);
617}
618
619static unsigned long cbq_undelay_prio(struct cbq_sched_data *q, int prio)
620{
621 struct cbq_class *cl;
622 struct cbq_class *cl_prev = q->active[prio];
623 unsigned long now = jiffies;
624 unsigned long sched = now;
625
626 if (cl_prev == NULL)
627 return now;
628
629 do {
630 cl = cl_prev->next_alive;
631 if ((long)(now - cl->penalized) > 0) {
632 cl_prev->next_alive = cl->next_alive;
633 cl->next_alive = NULL;
634 cl->cpriority = cl->priority;
635 cl->delayed = 0;
636 cbq_activate_class(cl);
637
638 if (cl == q->active[prio]) {
639 q->active[prio] = cl_prev;
640 if (cl == q->active[prio]) {
641 q->active[prio] = NULL;
642 return 0;
643 }
644 }
645
646 cl = cl_prev->next_alive;
647 } else if ((long)(sched - cl->penalized) > 0)
648 sched = cl->penalized;
649 } while ((cl_prev = cl) != q->active[prio]);
650
651 return (long)(sched - now);
652}
653
654static void cbq_undelay(unsigned long arg)
655{
656 struct Qdisc *sch = (struct Qdisc*)arg;
657 struct cbq_sched_data *q = qdisc_priv(sch);
658 long delay = 0;
659 unsigned pmask;
660
661 pmask = q->pmask;
662 q->pmask = 0;
663
664 while (pmask) {
665 int prio = ffz(~pmask);
666 long tmp;
667
668 pmask &= ~(1<<prio);
669
670 tmp = cbq_undelay_prio(q, prio);
671 if (tmp > 0) {
672 q->pmask |= 1<<prio;
673 if (tmp < delay || delay == 0)
674 delay = tmp;
675 }
676 }
677
678 if (delay) {
679 q->delay_timer.expires = jiffies + delay;
680 add_timer(&q->delay_timer);
681 }
682
683 sch->flags &= ~TCQ_F_THROTTLED;
684 netif_schedule(sch->dev);
685}
686
687
688#ifdef CONFIG_NET_CLS_POLICE
689
690static int cbq_reshape_fail(struct sk_buff *skb, struct Qdisc *child)
691{
692 int len = skb->len;
693 struct Qdisc *sch = child->__parent;
694 struct cbq_sched_data *q = qdisc_priv(sch);
695 struct cbq_class *cl = q->rx_class;
696
697 q->rx_class = NULL;
698
699 if (cl && (cl = cbq_reclassify(skb, cl)) != NULL) {
700
701 cbq_mark_toplevel(q, cl);
702
703 q->rx_class = cl;
704 cl->q->__parent = sch;
705
706 if (cl->q->enqueue(skb, cl->q) == 0) {
707 sch->q.qlen++;
708 sch->bstats.packets++;
709 sch->bstats.bytes+=len;
710 if (!cl->next_alive)
711 cbq_activate_class(cl);
712 return 0;
713 }
714 sch->qstats.drops++;
715 return 0;
716 }
717
718 sch->qstats.drops++;
719 return -1;
720}
721#endif
722
723/*
724 It is mission critical procedure.
725
726 We "regenerate" toplevel cutoff, if transmitting class
727 has backlog and it is not regulated. It is not part of
728 original CBQ description, but looks more reasonable.
729 Probably, it is wrong. This question needs further investigation.
730*/
731
732static __inline__ void
733cbq_update_toplevel(struct cbq_sched_data *q, struct cbq_class *cl,
734 struct cbq_class *borrowed)
735{
736 if (cl && q->toplevel >= borrowed->level) {
737 if (cl->q->q.qlen > 1) {
738 do {
739 if (PSCHED_IS_PASTPERFECT(borrowed->undertime)) {
740 q->toplevel = borrowed->level;
741 return;
742 }
743 } while ((borrowed=borrowed->borrow) != NULL);
744 }
745#if 0
746 /* It is not necessary now. Uncommenting it
747 will save CPU cycles, but decrease fairness.
748 */
749 q->toplevel = TC_CBQ_MAXLEVEL;
750#endif
751 }
752}
753
754static void
755cbq_update(struct cbq_sched_data *q)
756{
757 struct cbq_class *this = q->tx_class;
758 struct cbq_class *cl = this;
759 int len = q->tx_len;
760
761 q->tx_class = NULL;
762
763 for ( ; cl; cl = cl->share) {
764 long avgidle = cl->avgidle;
765 long idle;
766
767 cl->bstats.packets++;
768 cl->bstats.bytes += len;
769
770 /*
771 (now - last) is total time between packet right edges.
772 (last_pktlen/rate) is "virtual" busy time, so that
773
774 idle = (now - last) - last_pktlen/rate
775 */
776
777 idle = PSCHED_TDIFF(q->now, cl->last);
778 if ((unsigned long)idle > 128*1024*1024) {
779 avgidle = cl->maxidle;
780 } else {
781 idle -= L2T(cl, len);
782
783 /* true_avgidle := (1-W)*true_avgidle + W*idle,
784 where W=2^{-ewma_log}. But cl->avgidle is scaled:
785 cl->avgidle == true_avgidle/W,
786 hence:
787 */
788 avgidle += idle - (avgidle>>cl->ewma_log);
789 }
790
791 if (avgidle <= 0) {
792 /* Overlimit or at-limit */
793
794 if (avgidle < cl->minidle)
795 avgidle = cl->minidle;
796
797 cl->avgidle = avgidle;
798
799 /* Calculate expected time, when this class
800 will be allowed to send.
801 It will occur, when:
802 (1-W)*true_avgidle + W*delay = 0, i.e.
803 idle = (1/W - 1)*(-true_avgidle)
804 or
805 idle = (1 - W)*(-cl->avgidle);
806 */
807 idle = (-avgidle) - ((-avgidle) >> cl->ewma_log);
808
809 /*
810 That is not all.
811 To maintain the rate allocated to the class,
812 we add to undertime virtual clock,
813 necessary to complete transmitted packet.
814 (len/phys_bandwidth has been already passed
815 to the moment of cbq_update)
816 */
817
818 idle -= L2T(&q->link, len);
819 idle += L2T(cl, len);
820
821 PSCHED_AUDIT_TDIFF(idle);
822
823 PSCHED_TADD2(q->now, idle, cl->undertime);
824 } else {
825 /* Underlimit */
826
827 PSCHED_SET_PASTPERFECT(cl->undertime);
828 if (avgidle > cl->maxidle)
829 cl->avgidle = cl->maxidle;
830 else
831 cl->avgidle = avgidle;
832 }
833 cl->last = q->now;
834 }
835
836 cbq_update_toplevel(q, this, q->tx_borrowed);
837}
838
839static __inline__ struct cbq_class *
840cbq_under_limit(struct cbq_class *cl)
841{
842 struct cbq_sched_data *q = qdisc_priv(cl->qdisc);
843 struct cbq_class *this_cl = cl;
844
845 if (cl->tparent == NULL)
846 return cl;
847
848 if (PSCHED_IS_PASTPERFECT(cl->undertime) ||
849 !PSCHED_TLESS(q->now, cl->undertime)) {
850 cl->delayed = 0;
851 return cl;
852 }
853
854 do {
855 /* It is very suspicious place. Now overlimit
856 action is generated for not bounded classes
857 only if link is completely congested.
858 Though it is in agree with ancestor-only paradigm,
859 it looks very stupid. Particularly,
860 it means that this chunk of code will either
861 never be called or result in strong amplification
862 of burstiness. Dangerous, silly, and, however,
863 no another solution exists.
864 */
865 if ((cl = cl->borrow) == NULL) {
866 this_cl->qstats.overlimits++;
867 this_cl->overlimit(this_cl);
868 return NULL;
869 }
870 if (cl->level > q->toplevel)
871 return NULL;
872 } while (!PSCHED_IS_PASTPERFECT(cl->undertime) &&
873 PSCHED_TLESS(q->now, cl->undertime));
874
875 cl->delayed = 0;
876 return cl;
877}
878
879static __inline__ struct sk_buff *
880cbq_dequeue_prio(struct Qdisc *sch, int prio)
881{
882 struct cbq_sched_data *q = qdisc_priv(sch);
883 struct cbq_class *cl_tail, *cl_prev, *cl;
884 struct sk_buff *skb;
885 int deficit;
886
887 cl_tail = cl_prev = q->active[prio];
888 cl = cl_prev->next_alive;
889
890 do {
891 deficit = 0;
892
893 /* Start round */
894 do {
895 struct cbq_class *borrow = cl;
896
897 if (cl->q->q.qlen &&
898 (borrow = cbq_under_limit(cl)) == NULL)
899 goto skip_class;
900
901 if (cl->deficit <= 0) {
902 /* Class exhausted its allotment per
903 this round. Switch to the next one.
904 */
905 deficit = 1;
906 cl->deficit += cl->quantum;
907 goto next_class;
908 }
909
910 skb = cl->q->dequeue(cl->q);
911
912 /* Class did not give us any skb :-(
913 It could occur even if cl->q->q.qlen != 0
914 f.e. if cl->q == "tbf"
915 */
916 if (skb == NULL)
917 goto skip_class;
918
919 cl->deficit -= skb->len;
920 q->tx_class = cl;
921 q->tx_borrowed = borrow;
922 if (borrow != cl) {
923#ifndef CBQ_XSTATS_BORROWS_BYTES
924 borrow->xstats.borrows++;
925 cl->xstats.borrows++;
926#else
927 borrow->xstats.borrows += skb->len;
928 cl->xstats.borrows += skb->len;
929#endif
930 }
931 q->tx_len = skb->len;
932
933 if (cl->deficit <= 0) {
934 q->active[prio] = cl;
935 cl = cl->next_alive;
936 cl->deficit += cl->quantum;
937 }
938 return skb;
939
940skip_class:
941 if (cl->q->q.qlen == 0 || prio != cl->cpriority) {
942 /* Class is empty or penalized.
943 Unlink it from active chain.
944 */
945 cl_prev->next_alive = cl->next_alive;
946 cl->next_alive = NULL;
947
948 /* Did cl_tail point to it? */
949 if (cl == cl_tail) {
950 /* Repair it! */
951 cl_tail = cl_prev;
952
953 /* Was it the last class in this band? */
954 if (cl == cl_tail) {
955 /* Kill the band! */
956 q->active[prio] = NULL;
957 q->activemask &= ~(1<<prio);
958 if (cl->q->q.qlen)
959 cbq_activate_class(cl);
960 return NULL;
961 }
962
963 q->active[prio] = cl_tail;
964 }
965 if (cl->q->q.qlen)
966 cbq_activate_class(cl);
967
968 cl = cl_prev;
969 }
970
971next_class:
972 cl_prev = cl;
973 cl = cl->next_alive;
974 } while (cl_prev != cl_tail);
975 } while (deficit);
976
977 q->active[prio] = cl_prev;
978
979 return NULL;
980}
981
982static __inline__ struct sk_buff *
983cbq_dequeue_1(struct Qdisc *sch)
984{
985 struct cbq_sched_data *q = qdisc_priv(sch);
986 struct sk_buff *skb;
987 unsigned activemask;
988
989 activemask = q->activemask&0xFF;
990 while (activemask) {
991 int prio = ffz(~activemask);
992 activemask &= ~(1<<prio);
993 skb = cbq_dequeue_prio(sch, prio);
994 if (skb)
995 return skb;
996 }
997 return NULL;
998}
999
1000static struct sk_buff *
1001cbq_dequeue(struct Qdisc *sch)
1002{
1003 struct sk_buff *skb;
1004 struct cbq_sched_data *q = qdisc_priv(sch);
1005 psched_time_t now;
1006 psched_tdiff_t incr;
1007
1008 PSCHED_GET_TIME(now);
1009 incr = PSCHED_TDIFF(now, q->now_rt);
1010
1011 if (q->tx_class) {
1012 psched_tdiff_t incr2;
1013 /* Time integrator. We calculate EOS time
1014 by adding expected packet transmission time.
1015 If real time is greater, we warp artificial clock,
1016 so that:
1017
1018 cbq_time = max(real_time, work);
1019 */
1020 incr2 = L2T(&q->link, q->tx_len);
1021 PSCHED_TADD(q->now, incr2);
1022 cbq_update(q);
1023 if ((incr -= incr2) < 0)
1024 incr = 0;
1025 }
1026 PSCHED_TADD(q->now, incr);
1027 q->now_rt = now;
1028
1029 for (;;) {
1030 q->wd_expires = 0;
1031
1032 skb = cbq_dequeue_1(sch);
1033 if (skb) {
1034 sch->q.qlen--;
1035 sch->flags &= ~TCQ_F_THROTTLED;
1036 return skb;
1037 }
1038
1039 /* All the classes are overlimit.
1040
1041 It is possible, if:
1042
1043 1. Scheduler is empty.
1044 2. Toplevel cutoff inhibited borrowing.
1045 3. Root class is overlimit.
1046
1047 Reset 2d and 3d conditions and retry.
1048
1049 Note, that NS and cbq-2.0 are buggy, peeking
1050 an arbitrary class is appropriate for ancestor-only
1051 sharing, but not for toplevel algorithm.
1052
1053 Our version is better, but slower, because it requires
1054 two passes, but it is unavoidable with top-level sharing.
1055 */
1056
1057 if (q->toplevel == TC_CBQ_MAXLEVEL &&
1058 PSCHED_IS_PASTPERFECT(q->link.undertime))
1059 break;
1060
1061 q->toplevel = TC_CBQ_MAXLEVEL;
1062 PSCHED_SET_PASTPERFECT(q->link.undertime);
1063 }
1064
1065 /* No packets in scheduler or nobody wants to give them to us :-(
1066 Sigh... start watchdog timer in the last case. */
1067
1068 if (sch->q.qlen) {
1069 sch->qstats.overlimits++;
1070 if (q->wd_expires) {
1071 long delay = PSCHED_US2JIFFIE(q->wd_expires);
1072 if (delay <= 0)
1073 delay = 1;
1074 mod_timer(&q->wd_timer, jiffies + delay);
1075 sch->flags |= TCQ_F_THROTTLED;
1076 }
1077 }
1078 return NULL;
1079}
1080
1081/* CBQ class maintanance routines */
1082
1083static void cbq_adjust_levels(struct cbq_class *this)
1084{
1085 if (this == NULL)
1086 return;
1087
1088 do {
1089 int level = 0;
1090 struct cbq_class *cl;
1091
1092 if ((cl = this->children) != NULL) {
1093 do {
1094 if (cl->level > level)
1095 level = cl->level;
1096 } while ((cl = cl->sibling) != this->children);
1097 }
1098 this->level = level+1;
1099 } while ((this = this->tparent) != NULL);
1100}
1101
1102static void cbq_normalize_quanta(struct cbq_sched_data *q, int prio)
1103{
1104 struct cbq_class *cl;
1105 unsigned h;
1106
1107 if (q->quanta[prio] == 0)
1108 return;
1109
1110 for (h=0; h<16; h++) {
1111 for (cl = q->classes[h]; cl; cl = cl->next) {
1112 /* BUGGGG... Beware! This expression suffer of
1113 arithmetic overflows!
1114 */
1115 if (cl->priority == prio) {
1116 cl->quantum = (cl->weight*cl->allot*q->nclasses[prio])/
1117 q->quanta[prio];
1118 }
1119 if (cl->quantum <= 0 || cl->quantum>32*cl->qdisc->dev->mtu) {
1120 printk(KERN_WARNING "CBQ: class %08x has bad quantum==%ld, repaired.\n", cl->classid, cl->quantum);
1121 cl->quantum = cl->qdisc->dev->mtu/2 + 1;
1122 }
1123 }
1124 }
1125}
1126
1127static void cbq_sync_defmap(struct cbq_class *cl)
1128{
1129 struct cbq_sched_data *q = qdisc_priv(cl->qdisc);
1130 struct cbq_class *split = cl->split;
1131 unsigned h;
1132 int i;
1133
1134 if (split == NULL)
1135 return;
1136
1137 for (i=0; i<=TC_PRIO_MAX; i++) {
1138 if (split->defaults[i] == cl && !(cl->defmap&(1<<i)))
1139 split->defaults[i] = NULL;
1140 }
1141
1142 for (i=0; i<=TC_PRIO_MAX; i++) {
1143 int level = split->level;
1144
1145 if (split->defaults[i])
1146 continue;
1147
1148 for (h=0; h<16; h++) {
1149 struct cbq_class *c;
1150
1151 for (c = q->classes[h]; c; c = c->next) {
1152 if (c->split == split && c->level < level &&
1153 c->defmap&(1<<i)) {
1154 split->defaults[i] = c;
1155 level = c->level;
1156 }
1157 }
1158 }
1159 }
1160}
1161
1162static void cbq_change_defmap(struct cbq_class *cl, u32 splitid, u32 def, u32 mask)
1163{
1164 struct cbq_class *split = NULL;
1165
1166 if (splitid == 0) {
1167 if ((split = cl->split) == NULL)
1168 return;
1169 splitid = split->classid;
1170 }
1171
1172 if (split == NULL || split->classid != splitid) {
1173 for (split = cl->tparent; split; split = split->tparent)
1174 if (split->classid == splitid)
1175 break;
1176 }
1177
1178 if (split == NULL)
1179 return;
1180
1181 if (cl->split != split) {
1182 cl->defmap = 0;
1183 cbq_sync_defmap(cl);
1184 cl->split = split;
1185 cl->defmap = def&mask;
1186 } else
1187 cl->defmap = (cl->defmap&~mask)|(def&mask);
1188
1189 cbq_sync_defmap(cl);
1190}
1191
1192static void cbq_unlink_class(struct cbq_class *this)
1193{
1194 struct cbq_class *cl, **clp;
1195 struct cbq_sched_data *q = qdisc_priv(this->qdisc);
1196
1197 for (clp = &q->classes[cbq_hash(this->classid)]; (cl = *clp) != NULL; clp = &cl->next) {
1198 if (cl == this) {
1199 *clp = cl->next;
1200 cl->next = NULL;
1201 break;
1202 }
1203 }
1204
1205 if (this->tparent) {
1206 clp=&this->sibling;
1207 cl = *clp;
1208 do {
1209 if (cl == this) {
1210 *clp = cl->sibling;
1211 break;
1212 }
1213 clp = &cl->sibling;
1214 } while ((cl = *clp) != this->sibling);
1215
1216 if (this->tparent->children == this) {
1217 this->tparent->children = this->sibling;
1218 if (this->sibling == this)
1219 this->tparent->children = NULL;
1220 }
1221 } else {
1222 BUG_TRAP(this->sibling == this);
1223 }
1224}
1225
1226static void cbq_link_class(struct cbq_class *this)
1227{
1228 struct cbq_sched_data *q = qdisc_priv(this->qdisc);
1229 unsigned h = cbq_hash(this->classid);
1230 struct cbq_class *parent = this->tparent;
1231
1232 this->sibling = this;
1233 this->next = q->classes[h];
1234 q->classes[h] = this;
1235
1236 if (parent == NULL)
1237 return;
1238
1239 if (parent->children == NULL) {
1240 parent->children = this;
1241 } else {
1242 this->sibling = parent->children->sibling;
1243 parent->children->sibling = this;
1244 }
1245}
1246
1247static unsigned int cbq_drop(struct Qdisc* sch)
1248{
1249 struct cbq_sched_data *q = qdisc_priv(sch);
1250 struct cbq_class *cl, *cl_head;
1251 int prio;
1252 unsigned int len;
1253
1254 for (prio = TC_CBQ_MAXPRIO; prio >= 0; prio--) {
1255 if ((cl_head = q->active[prio]) == NULL)
1256 continue;
1257
1258 cl = cl_head;
1259 do {
1260 if (cl->q->ops->drop && (len = cl->q->ops->drop(cl->q))) {
1261 sch->q.qlen--;
1262 return len;
1263 }
1264 } while ((cl = cl->next_alive) != cl_head);
1265 }
1266 return 0;
1267}
1268
1269static void
1270cbq_reset(struct Qdisc* sch)
1271{
1272 struct cbq_sched_data *q = qdisc_priv(sch);
1273 struct cbq_class *cl;
1274 int prio;
1275 unsigned h;
1276
1277 q->activemask = 0;
1278 q->pmask = 0;
1279 q->tx_class = NULL;
1280 q->tx_borrowed = NULL;
1281 del_timer(&q->wd_timer);
1282 del_timer(&q->delay_timer);
1283 q->toplevel = TC_CBQ_MAXLEVEL;
1284 PSCHED_GET_TIME(q->now);
1285 q->now_rt = q->now;
1286
1287 for (prio = 0; prio <= TC_CBQ_MAXPRIO; prio++)
1288 q->active[prio] = NULL;
1289
1290 for (h = 0; h < 16; h++) {
1291 for (cl = q->classes[h]; cl; cl = cl->next) {
1292 qdisc_reset(cl->q);
1293
1294 cl->next_alive = NULL;
1295 PSCHED_SET_PASTPERFECT(cl->undertime);
1296 cl->avgidle = cl->maxidle;
1297 cl->deficit = cl->quantum;
1298 cl->cpriority = cl->priority;
1299 }
1300 }
1301 sch->q.qlen = 0;
1302}
1303
1304
1305static int cbq_set_lss(struct cbq_class *cl, struct tc_cbq_lssopt *lss)
1306{
1307 if (lss->change&TCF_CBQ_LSS_FLAGS) {
1308 cl->share = (lss->flags&TCF_CBQ_LSS_ISOLATED) ? NULL : cl->tparent;
1309 cl->borrow = (lss->flags&TCF_CBQ_LSS_BOUNDED) ? NULL : cl->tparent;
1310 }
1311 if (lss->change&TCF_CBQ_LSS_EWMA)
1312 cl->ewma_log = lss->ewma_log;
1313 if (lss->change&TCF_CBQ_LSS_AVPKT)
1314 cl->avpkt = lss->avpkt;
1315 if (lss->change&TCF_CBQ_LSS_MINIDLE)
1316 cl->minidle = -(long)lss->minidle;
1317 if (lss->change&TCF_CBQ_LSS_MAXIDLE) {
1318 cl->maxidle = lss->maxidle;
1319 cl->avgidle = lss->maxidle;
1320 }
1321 if (lss->change&TCF_CBQ_LSS_OFFTIME)
1322 cl->offtime = lss->offtime;
1323 return 0;
1324}
1325
1326static void cbq_rmprio(struct cbq_sched_data *q, struct cbq_class *cl)
1327{
1328 q->nclasses[cl->priority]--;
1329 q->quanta[cl->priority] -= cl->weight;
1330 cbq_normalize_quanta(q, cl->priority);
1331}
1332
1333static void cbq_addprio(struct cbq_sched_data *q, struct cbq_class *cl)
1334{
1335 q->nclasses[cl->priority]++;
1336 q->quanta[cl->priority] += cl->weight;
1337 cbq_normalize_quanta(q, cl->priority);
1338}
1339
1340static int cbq_set_wrr(struct cbq_class *cl, struct tc_cbq_wrropt *wrr)
1341{
1342 struct cbq_sched_data *q = qdisc_priv(cl->qdisc);
1343
1344 if (wrr->allot)
1345 cl->allot = wrr->allot;
1346 if (wrr->weight)
1347 cl->weight = wrr->weight;
1348 if (wrr->priority) {
1349 cl->priority = wrr->priority-1;
1350 cl->cpriority = cl->priority;
1351 if (cl->priority >= cl->priority2)
1352 cl->priority2 = TC_CBQ_MAXPRIO-1;
1353 }
1354
1355 cbq_addprio(q, cl);
1356 return 0;
1357}
1358
1359static int cbq_set_overlimit(struct cbq_class *cl, struct tc_cbq_ovl *ovl)
1360{
1361 switch (ovl->strategy) {
1362 case TC_CBQ_OVL_CLASSIC:
1363 cl->overlimit = cbq_ovl_classic;
1364 break;
1365 case TC_CBQ_OVL_DELAY:
1366 cl->overlimit = cbq_ovl_delay;
1367 break;
1368 case TC_CBQ_OVL_LOWPRIO:
1369 if (ovl->priority2-1 >= TC_CBQ_MAXPRIO ||
1370 ovl->priority2-1 <= cl->priority)
1371 return -EINVAL;
1372 cl->priority2 = ovl->priority2-1;
1373 cl->overlimit = cbq_ovl_lowprio;
1374 break;
1375 case TC_CBQ_OVL_DROP:
1376 cl->overlimit = cbq_ovl_drop;
1377 break;
1378 case TC_CBQ_OVL_RCLASSIC:
1379 cl->overlimit = cbq_ovl_rclassic;
1380 break;
1381 default:
1382 return -EINVAL;
1383 }
1384 cl->penalty = (ovl->penalty*HZ)/1000;
1385 return 0;
1386}
1387
1388#ifdef CONFIG_NET_CLS_POLICE
1389static int cbq_set_police(struct cbq_class *cl, struct tc_cbq_police *p)
1390{
1391 cl->police = p->police;
1392
1393 if (cl->q->handle) {
1394 if (p->police == TC_POLICE_RECLASSIFY)
1395 cl->q->reshape_fail = cbq_reshape_fail;
1396 else
1397 cl->q->reshape_fail = NULL;
1398 }
1399 return 0;
1400}
1401#endif
1402
1403static int cbq_set_fopt(struct cbq_class *cl, struct tc_cbq_fopt *fopt)
1404{
1405 cbq_change_defmap(cl, fopt->split, fopt->defmap, fopt->defchange);
1406 return 0;
1407}
1408
1409static int cbq_init(struct Qdisc *sch, struct rtattr *opt)
1410{
1411 struct cbq_sched_data *q = qdisc_priv(sch);
1412 struct rtattr *tb[TCA_CBQ_MAX];
1413 struct tc_ratespec *r;
1414
1415 if (rtattr_parse_nested(tb, TCA_CBQ_MAX, opt) < 0 ||
1416 tb[TCA_CBQ_RTAB-1] == NULL || tb[TCA_CBQ_RATE-1] == NULL ||
1417 RTA_PAYLOAD(tb[TCA_CBQ_RATE-1]) < sizeof(struct tc_ratespec))
1418 return -EINVAL;
1419
1420 if (tb[TCA_CBQ_LSSOPT-1] &&
1421 RTA_PAYLOAD(tb[TCA_CBQ_LSSOPT-1]) < sizeof(struct tc_cbq_lssopt))
1422 return -EINVAL;
1423
1424 r = RTA_DATA(tb[TCA_CBQ_RATE-1]);
1425
1426 if ((q->link.R_tab = qdisc_get_rtab(r, tb[TCA_CBQ_RTAB-1])) == NULL)
1427 return -EINVAL;
1428
1429 q->link.refcnt = 1;
1430 q->link.sibling = &q->link;
1431 q->link.classid = sch->handle;
1432 q->link.qdisc = sch;
1433 if (!(q->link.q = qdisc_create_dflt(sch->dev, &pfifo_qdisc_ops)))
1434 q->link.q = &noop_qdisc;
1435
1436 q->link.priority = TC_CBQ_MAXPRIO-1;
1437 q->link.priority2 = TC_CBQ_MAXPRIO-1;
1438 q->link.cpriority = TC_CBQ_MAXPRIO-1;
1439 q->link.ovl_strategy = TC_CBQ_OVL_CLASSIC;
1440 q->link.overlimit = cbq_ovl_classic;
1441 q->link.allot = psched_mtu(sch->dev);
1442 q->link.quantum = q->link.allot;
1443 q->link.weight = q->link.R_tab->rate.rate;
1444
1445 q->link.ewma_log = TC_CBQ_DEF_EWMA;
1446 q->link.avpkt = q->link.allot/2;
1447 q->link.minidle = -0x7FFFFFFF;
1448 q->link.stats_lock = &sch->dev->queue_lock;
1449
1450 init_timer(&q->wd_timer);
1451 q->wd_timer.data = (unsigned long)sch;
1452 q->wd_timer.function = cbq_watchdog;
1453 init_timer(&q->delay_timer);
1454 q->delay_timer.data = (unsigned long)sch;
1455 q->delay_timer.function = cbq_undelay;
1456 q->toplevel = TC_CBQ_MAXLEVEL;
1457 PSCHED_GET_TIME(q->now);
1458 q->now_rt = q->now;
1459
1460 cbq_link_class(&q->link);
1461
1462 if (tb[TCA_CBQ_LSSOPT-1])
1463 cbq_set_lss(&q->link, RTA_DATA(tb[TCA_CBQ_LSSOPT-1]));
1464
1465 cbq_addprio(q, &q->link);
1466 return 0;
1467}
1468
1469static __inline__ int cbq_dump_rate(struct sk_buff *skb, struct cbq_class *cl)
1470{
1471 unsigned char *b = skb->tail;
1472
1473 RTA_PUT(skb, TCA_CBQ_RATE, sizeof(cl->R_tab->rate), &cl->R_tab->rate);
1474 return skb->len;
1475
1476rtattr_failure:
1477 skb_trim(skb, b - skb->data);
1478 return -1;
1479}
1480
1481static __inline__ int cbq_dump_lss(struct sk_buff *skb, struct cbq_class *cl)
1482{
1483 unsigned char *b = skb->tail;
1484 struct tc_cbq_lssopt opt;
1485
1486 opt.flags = 0;
1487 if (cl->borrow == NULL)
1488 opt.flags |= TCF_CBQ_LSS_BOUNDED;
1489 if (cl->share == NULL)
1490 opt.flags |= TCF_CBQ_LSS_ISOLATED;
1491 opt.ewma_log = cl->ewma_log;
1492 opt.level = cl->level;
1493 opt.avpkt = cl->avpkt;
1494 opt.maxidle = cl->maxidle;
1495 opt.minidle = (u32)(-cl->minidle);
1496 opt.offtime = cl->offtime;
1497 opt.change = ~0;
1498 RTA_PUT(skb, TCA_CBQ_LSSOPT, sizeof(opt), &opt);
1499 return skb->len;
1500
1501rtattr_failure:
1502 skb_trim(skb, b - skb->data);
1503 return -1;
1504}
1505
1506static __inline__ int cbq_dump_wrr(struct sk_buff *skb, struct cbq_class *cl)
1507{
1508 unsigned char *b = skb->tail;
1509 struct tc_cbq_wrropt opt;
1510
1511 opt.flags = 0;
1512 opt.allot = cl->allot;
1513 opt.priority = cl->priority+1;
1514 opt.cpriority = cl->cpriority+1;
1515 opt.weight = cl->weight;
1516 RTA_PUT(skb, TCA_CBQ_WRROPT, sizeof(opt), &opt);
1517 return skb->len;
1518
1519rtattr_failure:
1520 skb_trim(skb, b - skb->data);
1521 return -1;
1522}
1523
1524static __inline__ int cbq_dump_ovl(struct sk_buff *skb, struct cbq_class *cl)
1525{
1526 unsigned char *b = skb->tail;
1527 struct tc_cbq_ovl opt;
1528
1529 opt.strategy = cl->ovl_strategy;
1530 opt.priority2 = cl->priority2+1;
1531 opt.penalty = (cl->penalty*1000)/HZ;
1532 RTA_PUT(skb, TCA_CBQ_OVL_STRATEGY, sizeof(opt), &opt);
1533 return skb->len;
1534
1535rtattr_failure:
1536 skb_trim(skb, b - skb->data);
1537 return -1;
1538}
1539
1540static __inline__ int cbq_dump_fopt(struct sk_buff *skb, struct cbq_class *cl)
1541{
1542 unsigned char *b = skb->tail;
1543 struct tc_cbq_fopt opt;
1544
1545 if (cl->split || cl->defmap) {
1546 opt.split = cl->split ? cl->split->classid : 0;
1547 opt.defmap = cl->defmap;
1548 opt.defchange = ~0;
1549 RTA_PUT(skb, TCA_CBQ_FOPT, sizeof(opt), &opt);
1550 }
1551 return skb->len;
1552
1553rtattr_failure:
1554 skb_trim(skb, b - skb->data);
1555 return -1;
1556}
1557
1558#ifdef CONFIG_NET_CLS_POLICE
1559static __inline__ int cbq_dump_police(struct sk_buff *skb, struct cbq_class *cl)
1560{
1561 unsigned char *b = skb->tail;
1562 struct tc_cbq_police opt;
1563
1564 if (cl->police) {
1565 opt.police = cl->police;
1566 RTA_PUT(skb, TCA_CBQ_POLICE, sizeof(opt), &opt);
1567 }
1568 return skb->len;
1569
1570rtattr_failure:
1571 skb_trim(skb, b - skb->data);
1572 return -1;
1573}
1574#endif
1575
1576static int cbq_dump_attr(struct sk_buff *skb, struct cbq_class *cl)
1577{
1578 if (cbq_dump_lss(skb, cl) < 0 ||
1579 cbq_dump_rate(skb, cl) < 0 ||
1580 cbq_dump_wrr(skb, cl) < 0 ||
1581 cbq_dump_ovl(skb, cl) < 0 ||
1582#ifdef CONFIG_NET_CLS_POLICE
1583 cbq_dump_police(skb, cl) < 0 ||
1584#endif
1585 cbq_dump_fopt(skb, cl) < 0)
1586 return -1;
1587 return 0;
1588}
1589
1590static int cbq_dump(struct Qdisc *sch, struct sk_buff *skb)
1591{
1592 struct cbq_sched_data *q = qdisc_priv(sch);
1593 unsigned char *b = skb->tail;
1594 struct rtattr *rta;
1595
1596 rta = (struct rtattr*)b;
1597 RTA_PUT(skb, TCA_OPTIONS, 0, NULL);
1598 if (cbq_dump_attr(skb, &q->link) < 0)
1599 goto rtattr_failure;
1600 rta->rta_len = skb->tail - b;
1601 return skb->len;
1602
1603rtattr_failure:
1604 skb_trim(skb, b - skb->data);
1605 return -1;
1606}
1607
1608static int
1609cbq_dump_stats(struct Qdisc *sch, struct gnet_dump *d)
1610{
1611 struct cbq_sched_data *q = qdisc_priv(sch);
1612
1613 q->link.xstats.avgidle = q->link.avgidle;
1614 return gnet_stats_copy_app(d, &q->link.xstats, sizeof(q->link.xstats));
1615}
1616
1617static int
1618cbq_dump_class(struct Qdisc *sch, unsigned long arg,
1619 struct sk_buff *skb, struct tcmsg *tcm)
1620{
1621 struct cbq_class *cl = (struct cbq_class*)arg;
1622 unsigned char *b = skb->tail;
1623 struct rtattr *rta;
1624
1625 if (cl->tparent)
1626 tcm->tcm_parent = cl->tparent->classid;
1627 else
1628 tcm->tcm_parent = TC_H_ROOT;
1629 tcm->tcm_handle = cl->classid;
1630 tcm->tcm_info = cl->q->handle;
1631
1632 rta = (struct rtattr*)b;
1633 RTA_PUT(skb, TCA_OPTIONS, 0, NULL);
1634 if (cbq_dump_attr(skb, cl) < 0)
1635 goto rtattr_failure;
1636 rta->rta_len = skb->tail - b;
1637 return skb->len;
1638
1639rtattr_failure:
1640 skb_trim(skb, b - skb->data);
1641 return -1;
1642}
1643
1644static int
1645cbq_dump_class_stats(struct Qdisc *sch, unsigned long arg,
1646 struct gnet_dump *d)
1647{
1648 struct cbq_sched_data *q = qdisc_priv(sch);
1649 struct cbq_class *cl = (struct cbq_class*)arg;
1650
1651 cl->qstats.qlen = cl->q->q.qlen;
1652 cl->xstats.avgidle = cl->avgidle;
1653 cl->xstats.undertime = 0;
1654
1655 if (!PSCHED_IS_PASTPERFECT(cl->undertime))
1656 cl->xstats.undertime = PSCHED_TDIFF(cl->undertime, q->now);
1657
1658 if (gnet_stats_copy_basic(d, &cl->bstats) < 0 ||
1659#ifdef CONFIG_NET_ESTIMATOR
1660 gnet_stats_copy_rate_est(d, &cl->rate_est) < 0 ||
1661#endif
1662 gnet_stats_copy_queue(d, &cl->qstats) < 0)
1663 return -1;
1664
1665 return gnet_stats_copy_app(d, &cl->xstats, sizeof(cl->xstats));
1666}
1667
1668static int cbq_graft(struct Qdisc *sch, unsigned long arg, struct Qdisc *new,
1669 struct Qdisc **old)
1670{
1671 struct cbq_class *cl = (struct cbq_class*)arg;
1672
1673 if (cl) {
1674 if (new == NULL) {
1675 if ((new = qdisc_create_dflt(sch->dev, &pfifo_qdisc_ops)) == NULL)
1676 return -ENOBUFS;
1677 } else {
1678#ifdef CONFIG_NET_CLS_POLICE
1679 if (cl->police == TC_POLICE_RECLASSIFY)
1680 new->reshape_fail = cbq_reshape_fail;
1681#endif
1682 }
1683 sch_tree_lock(sch);
1684 *old = cl->q;
1685 cl->q = new;
1686 sch->q.qlen -= (*old)->q.qlen;
1687 qdisc_reset(*old);
1688 sch_tree_unlock(sch);
1689
1690 return 0;
1691 }
1692 return -ENOENT;
1693}
1694
1695static struct Qdisc *
1696cbq_leaf(struct Qdisc *sch, unsigned long arg)
1697{
1698 struct cbq_class *cl = (struct cbq_class*)arg;
1699
1700 return cl ? cl->q : NULL;
1701}
1702
1703static unsigned long cbq_get(struct Qdisc *sch, u32 classid)
1704{
1705 struct cbq_sched_data *q = qdisc_priv(sch);
1706 struct cbq_class *cl = cbq_class_lookup(q, classid);
1707
1708 if (cl) {
1709 cl->refcnt++;
1710 return (unsigned long)cl;
1711 }
1712 return 0;
1713}
1714
1715static void cbq_destroy_filters(struct cbq_class *cl)
1716{
1717 struct tcf_proto *tp;
1718
1719 while ((tp = cl->filter_list) != NULL) {
1720 cl->filter_list = tp->next;
1721 tcf_destroy(tp);
1722 }
1723}
1724
1725static void cbq_destroy_class(struct Qdisc *sch, struct cbq_class *cl)
1726{
1727 struct cbq_sched_data *q = qdisc_priv(sch);
1728
1729 BUG_TRAP(!cl->filters);
1730
1731 cbq_destroy_filters(cl);
1732 qdisc_destroy(cl->q);
1733 qdisc_put_rtab(cl->R_tab);
1734#ifdef CONFIG_NET_ESTIMATOR
1735 gen_kill_estimator(&cl->bstats, &cl->rate_est);
1736#endif
1737 if (cl != &q->link)
1738 kfree(cl);
1739}
1740
1741static void
1742cbq_destroy(struct Qdisc* sch)
1743{
1744 struct cbq_sched_data *q = qdisc_priv(sch);
1745 struct cbq_class *cl;
1746 unsigned h;
1747
1748#ifdef CONFIG_NET_CLS_POLICE
1749 q->rx_class = NULL;
1750#endif
1751 /*
1752 * Filters must be destroyed first because we don't destroy the
1753 * classes from root to leafs which means that filters can still
1754 * be bound to classes which have been destroyed already. --TGR '04
1755 */
1756 for (h = 0; h < 16; h++)
1757 for (cl = q->classes[h]; cl; cl = cl->next)
1758 cbq_destroy_filters(cl);
1759
1760 for (h = 0; h < 16; h++) {
1761 struct cbq_class *next;
1762
1763 for (cl = q->classes[h]; cl; cl = next) {
1764 next = cl->next;
1765 cbq_destroy_class(sch, cl);
1766 }
1767 }
1768}
1769
1770static void cbq_put(struct Qdisc *sch, unsigned long arg)
1771{
1772 struct cbq_class *cl = (struct cbq_class*)arg;
1773
1774 if (--cl->refcnt == 0) {
1775#ifdef CONFIG_NET_CLS_POLICE
1776 struct cbq_sched_data *q = qdisc_priv(sch);
1777
1778 spin_lock_bh(&sch->dev->queue_lock);
1779 if (q->rx_class == cl)
1780 q->rx_class = NULL;
1781 spin_unlock_bh(&sch->dev->queue_lock);
1782#endif
1783
1784 cbq_destroy_class(sch, cl);
1785 }
1786}
1787
1788static int
1789cbq_change_class(struct Qdisc *sch, u32 classid, u32 parentid, struct rtattr **tca,
1790 unsigned long *arg)
1791{
1792 int err;
1793 struct cbq_sched_data *q = qdisc_priv(sch);
1794 struct cbq_class *cl = (struct cbq_class*)*arg;
1795 struct rtattr *opt = tca[TCA_OPTIONS-1];
1796 struct rtattr *tb[TCA_CBQ_MAX];
1797 struct cbq_class *parent;
1798 struct qdisc_rate_table *rtab = NULL;
1799
1800 if (opt==NULL || rtattr_parse_nested(tb, TCA_CBQ_MAX, opt))
1801 return -EINVAL;
1802
1803 if (tb[TCA_CBQ_OVL_STRATEGY-1] &&
1804 RTA_PAYLOAD(tb[TCA_CBQ_OVL_STRATEGY-1]) < sizeof(struct tc_cbq_ovl))
1805 return -EINVAL;
1806
1807 if (tb[TCA_CBQ_FOPT-1] &&
1808 RTA_PAYLOAD(tb[TCA_CBQ_FOPT-1]) < sizeof(struct tc_cbq_fopt))
1809 return -EINVAL;
1810
1811 if (tb[TCA_CBQ_RATE-1] &&
1812 RTA_PAYLOAD(tb[TCA_CBQ_RATE-1]) < sizeof(struct tc_ratespec))
1813 return -EINVAL;
1814
1815 if (tb[TCA_CBQ_LSSOPT-1] &&
1816 RTA_PAYLOAD(tb[TCA_CBQ_LSSOPT-1]) < sizeof(struct tc_cbq_lssopt))
1817 return -EINVAL;
1818
1819 if (tb[TCA_CBQ_WRROPT-1] &&
1820 RTA_PAYLOAD(tb[TCA_CBQ_WRROPT-1]) < sizeof(struct tc_cbq_wrropt))
1821 return -EINVAL;
1822
1823#ifdef CONFIG_NET_CLS_POLICE
1824 if (tb[TCA_CBQ_POLICE-1] &&
1825 RTA_PAYLOAD(tb[TCA_CBQ_POLICE-1]) < sizeof(struct tc_cbq_police))
1826 return -EINVAL;
1827#endif
1828
1829 if (cl) {
1830 /* Check parent */
1831 if (parentid) {
1832 if (cl->tparent && cl->tparent->classid != parentid)
1833 return -EINVAL;
1834 if (!cl->tparent && parentid != TC_H_ROOT)
1835 return -EINVAL;
1836 }
1837
1838 if (tb[TCA_CBQ_RATE-1]) {
1839 rtab = qdisc_get_rtab(RTA_DATA(tb[TCA_CBQ_RATE-1]), tb[TCA_CBQ_RTAB-1]);
1840 if (rtab == NULL)
1841 return -EINVAL;
1842 }
1843
1844 /* Change class parameters */
1845 sch_tree_lock(sch);
1846
1847 if (cl->next_alive != NULL)
1848 cbq_deactivate_class(cl);
1849
1850 if (rtab) {
1851 rtab = xchg(&cl->R_tab, rtab);
1852 qdisc_put_rtab(rtab);
1853 }
1854
1855 if (tb[TCA_CBQ_LSSOPT-1])
1856 cbq_set_lss(cl, RTA_DATA(tb[TCA_CBQ_LSSOPT-1]));
1857
1858 if (tb[TCA_CBQ_WRROPT-1]) {
1859 cbq_rmprio(q, cl);
1860 cbq_set_wrr(cl, RTA_DATA(tb[TCA_CBQ_WRROPT-1]));
1861 }
1862
1863 if (tb[TCA_CBQ_OVL_STRATEGY-1])
1864 cbq_set_overlimit(cl, RTA_DATA(tb[TCA_CBQ_OVL_STRATEGY-1]));
1865
1866#ifdef CONFIG_NET_CLS_POLICE
1867 if (tb[TCA_CBQ_POLICE-1])
1868 cbq_set_police(cl, RTA_DATA(tb[TCA_CBQ_POLICE-1]));
1869#endif
1870
1871 if (tb[TCA_CBQ_FOPT-1])
1872 cbq_set_fopt(cl, RTA_DATA(tb[TCA_CBQ_FOPT-1]));
1873
1874 if (cl->q->q.qlen)
1875 cbq_activate_class(cl);
1876
1877 sch_tree_unlock(sch);
1878
1879#ifdef CONFIG_NET_ESTIMATOR
1880 if (tca[TCA_RATE-1])
1881 gen_replace_estimator(&cl->bstats, &cl->rate_est,
1882 cl->stats_lock, tca[TCA_RATE-1]);
1883#endif
1884 return 0;
1885 }
1886
1887 if (parentid == TC_H_ROOT)
1888 return -EINVAL;
1889
1890 if (tb[TCA_CBQ_WRROPT-1] == NULL || tb[TCA_CBQ_RATE-1] == NULL ||
1891 tb[TCA_CBQ_LSSOPT-1] == NULL)
1892 return -EINVAL;
1893
1894 rtab = qdisc_get_rtab(RTA_DATA(tb[TCA_CBQ_RATE-1]), tb[TCA_CBQ_RTAB-1]);
1895 if (rtab == NULL)
1896 return -EINVAL;
1897
1898 if (classid) {
1899 err = -EINVAL;
1900 if (TC_H_MAJ(classid^sch->handle) || cbq_class_lookup(q, classid))
1901 goto failure;
1902 } else {
1903 int i;
1904 classid = TC_H_MAKE(sch->handle,0x8000);
1905
1906 for (i=0; i<0x8000; i++) {
1907 if (++q->hgenerator >= 0x8000)
1908 q->hgenerator = 1;
1909 if (cbq_class_lookup(q, classid|q->hgenerator) == NULL)
1910 break;
1911 }
1912 err = -ENOSR;
1913 if (i >= 0x8000)
1914 goto failure;
1915 classid = classid|q->hgenerator;
1916 }
1917
1918 parent = &q->link;
1919 if (parentid) {
1920 parent = cbq_class_lookup(q, parentid);
1921 err = -EINVAL;
1922 if (parent == NULL)
1923 goto failure;
1924 }
1925
1926 err = -ENOBUFS;
1927 cl = kmalloc(sizeof(*cl), GFP_KERNEL);
1928 if (cl == NULL)
1929 goto failure;
1930 memset(cl, 0, sizeof(*cl));
1931 cl->R_tab = rtab;
1932 rtab = NULL;
1933 cl->refcnt = 1;
1934 if (!(cl->q = qdisc_create_dflt(sch->dev, &pfifo_qdisc_ops)))
1935 cl->q = &noop_qdisc;
1936 cl->classid = classid;
1937 cl->tparent = parent;
1938 cl->qdisc = sch;
1939 cl->allot = parent->allot;
1940 cl->quantum = cl->allot;
1941 cl->weight = cl->R_tab->rate.rate;
1942 cl->stats_lock = &sch->dev->queue_lock;
1943
1944 sch_tree_lock(sch);
1945 cbq_link_class(cl);
1946 cl->borrow = cl->tparent;
1947 if (cl->tparent != &q->link)
1948 cl->share = cl->tparent;
1949 cbq_adjust_levels(parent);
1950 cl->minidle = -0x7FFFFFFF;
1951 cbq_set_lss(cl, RTA_DATA(tb[TCA_CBQ_LSSOPT-1]));
1952 cbq_set_wrr(cl, RTA_DATA(tb[TCA_CBQ_WRROPT-1]));
1953 if (cl->ewma_log==0)
1954 cl->ewma_log = q->link.ewma_log;
1955 if (cl->maxidle==0)
1956 cl->maxidle = q->link.maxidle;
1957 if (cl->avpkt==0)
1958 cl->avpkt = q->link.avpkt;
1959 cl->overlimit = cbq_ovl_classic;
1960 if (tb[TCA_CBQ_OVL_STRATEGY-1])
1961 cbq_set_overlimit(cl, RTA_DATA(tb[TCA_CBQ_OVL_STRATEGY-1]));
1962#ifdef CONFIG_NET_CLS_POLICE
1963 if (tb[TCA_CBQ_POLICE-1])
1964 cbq_set_police(cl, RTA_DATA(tb[TCA_CBQ_POLICE-1]));
1965#endif
1966 if (tb[TCA_CBQ_FOPT-1])
1967 cbq_set_fopt(cl, RTA_DATA(tb[TCA_CBQ_FOPT-1]));
1968 sch_tree_unlock(sch);
1969
1970#ifdef CONFIG_NET_ESTIMATOR
1971 if (tca[TCA_RATE-1])
1972 gen_new_estimator(&cl->bstats, &cl->rate_est,
1973 cl->stats_lock, tca[TCA_RATE-1]);
1974#endif
1975
1976 *arg = (unsigned long)cl;
1977 return 0;
1978
1979failure:
1980 qdisc_put_rtab(rtab);
1981 return err;
1982}
1983
1984static int cbq_delete(struct Qdisc *sch, unsigned long arg)
1985{
1986 struct cbq_sched_data *q = qdisc_priv(sch);
1987 struct cbq_class *cl = (struct cbq_class*)arg;
1988
1989 if (cl->filters || cl->children || cl == &q->link)
1990 return -EBUSY;
1991
1992 sch_tree_lock(sch);
1993
1994 if (cl->next_alive)
1995 cbq_deactivate_class(cl);
1996
1997 if (q->tx_borrowed == cl)
1998 q->tx_borrowed = q->tx_class;
1999 if (q->tx_class == cl) {
2000 q->tx_class = NULL;
2001 q->tx_borrowed = NULL;
2002 }
2003#ifdef CONFIG_NET_CLS_POLICE
2004 if (q->rx_class == cl)
2005 q->rx_class = NULL;
2006#endif
2007
2008 cbq_unlink_class(cl);
2009 cbq_adjust_levels(cl->tparent);
2010 cl->defmap = 0;
2011 cbq_sync_defmap(cl);
2012
2013 cbq_rmprio(q, cl);
2014 sch_tree_unlock(sch);
2015
2016 if (--cl->refcnt == 0)
2017 cbq_destroy_class(sch, cl);
2018
2019 return 0;
2020}
2021
2022static struct tcf_proto **cbq_find_tcf(struct Qdisc *sch, unsigned long arg)
2023{
2024 struct cbq_sched_data *q = qdisc_priv(sch);
2025 struct cbq_class *cl = (struct cbq_class *)arg;
2026
2027 if (cl == NULL)
2028 cl = &q->link;
2029
2030 return &cl->filter_list;
2031}
2032
2033static unsigned long cbq_bind_filter(struct Qdisc *sch, unsigned long parent,
2034 u32 classid)
2035{
2036 struct cbq_sched_data *q = qdisc_priv(sch);
2037 struct cbq_class *p = (struct cbq_class*)parent;
2038 struct cbq_class *cl = cbq_class_lookup(q, classid);
2039
2040 if (cl) {
2041 if (p && p->level <= cl->level)
2042 return 0;
2043 cl->filters++;
2044 return (unsigned long)cl;
2045 }
2046 return 0;
2047}
2048
2049static void cbq_unbind_filter(struct Qdisc *sch, unsigned long arg)
2050{
2051 struct cbq_class *cl = (struct cbq_class*)arg;
2052
2053 cl->filters--;
2054}
2055
2056static void cbq_walk(struct Qdisc *sch, struct qdisc_walker *arg)
2057{
2058 struct cbq_sched_data *q = qdisc_priv(sch);
2059 unsigned h;
2060
2061 if (arg->stop)
2062 return;
2063
2064 for (h = 0; h < 16; h++) {
2065 struct cbq_class *cl;
2066
2067 for (cl = q->classes[h]; cl; cl = cl->next) {
2068 if (arg->count < arg->skip) {
2069 arg->count++;
2070 continue;
2071 }
2072 if (arg->fn(sch, (unsigned long)cl, arg) < 0) {
2073 arg->stop = 1;
2074 return;
2075 }
2076 arg->count++;
2077 }
2078 }
2079}
2080
2081static struct Qdisc_class_ops cbq_class_ops = {
2082 .graft = cbq_graft,
2083 .leaf = cbq_leaf,
2084 .get = cbq_get,
2085 .put = cbq_put,
2086 .change = cbq_change_class,
2087 .delete = cbq_delete,
2088 .walk = cbq_walk,
2089 .tcf_chain = cbq_find_tcf,
2090 .bind_tcf = cbq_bind_filter,
2091 .unbind_tcf = cbq_unbind_filter,
2092 .dump = cbq_dump_class,
2093 .dump_stats = cbq_dump_class_stats,
2094};
2095
2096static struct Qdisc_ops cbq_qdisc_ops = {
2097 .next = NULL,
2098 .cl_ops = &cbq_class_ops,
2099 .id = "cbq",
2100 .priv_size = sizeof(struct cbq_sched_data),
2101 .enqueue = cbq_enqueue,
2102 .dequeue = cbq_dequeue,
2103 .requeue = cbq_requeue,
2104 .drop = cbq_drop,
2105 .init = cbq_init,
2106 .reset = cbq_reset,
2107 .destroy = cbq_destroy,
2108 .change = NULL,
2109 .dump = cbq_dump,
2110 .dump_stats = cbq_dump_stats,
2111 .owner = THIS_MODULE,
2112};
2113
2114static int __init cbq_module_init(void)
2115{
2116 return register_qdisc(&cbq_qdisc_ops);
2117}
2118static void __exit cbq_module_exit(void)
2119{
2120 unregister_qdisc(&cbq_qdisc_ops);
2121}
2122module_init(cbq_module_init)
2123module_exit(cbq_module_exit)
2124MODULE_LICENSE("GPL");