?  search:
summary | log | graphiclog1 | graphiclog2 | commit | commitdiff | tree | refs | edit | fork
blame | history | raw | HEAD
Linux 2.6.17.7
[linux/fpc-iii.git] / net / sched / sch_cbq.c
blob6cd81708bf710e0c307807bcbffc35176be452a2
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
88 struct cbq_sched_data;
89
90
91 struct 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
163 struct 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
199 static __inline__ unsigned cbq_hash(u32 h)
200 {
201 h ^= h>>8;
202 h ^= h>>4;
203 return h&0xF;
204 }
205
206 static __inline__ struct cbq_class *
207 cbq_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
219 static struct cbq_class *
220 cbq_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
243 static struct cbq_class *
244 cbq_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_BYPASS;
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
310 fallback:
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
330 static __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
354 static 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
382 static void
383 cbq_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
404 static int
405 cbq_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_BYPASS)
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
441 static int
442 cbq_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
477 static 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
531 static 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
550 static 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
586 static 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
602 static 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
611 static 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
619 static 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
654 static 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
690 static 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
732 static __inline__ void
733 cbq_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
754 static void
755 cbq_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
839 static __inline__ struct cbq_class *
840 cbq_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
879 static __inline__ struct sk_buff *
880 cbq_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
940 skip_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
971 next_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
982 static __inline__ struct sk_buff *
983 cbq_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
1000 static struct sk_buff *
1001 cbq_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
1083 static 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
1102 static 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
1127 static 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
1162 static 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
1192 static 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
1226 static 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
1247 static 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
1269 static void
1270 cbq_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
1305 static 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
1326 static 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
1333 static 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
1340 static 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
1359 static 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
1389 static 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
1403 static 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
1409 static 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
1469 static __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
1476 rtattr_failure:
1477 skb_trim(skb, b - skb->data);
1478 return -1;
1479 }
1480
1481 static __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
1501 rtattr_failure:
1502 skb_trim(skb, b - skb->data);
1503 return -1;
1504 }
1505
1506 static __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
1519 rtattr_failure:
1520 skb_trim(skb, b - skb->data);
1521 return -1;
1522 }
1523
1524 static __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.pad = 0;
1532 opt.penalty = (cl->penalty*1000)/HZ;
1533 RTA_PUT(skb, TCA_CBQ_OVL_STRATEGY, sizeof(opt), &opt);
1534 return skb->len;
1535
1536 rtattr_failure:
1537 skb_trim(skb, b - skb->data);
1538 return -1;
1539 }
1540
1541 static __inline__ int cbq_dump_fopt(struct sk_buff *skb, struct cbq_class *cl)
1542 {
1543 unsigned char *b = skb->tail;
1544 struct tc_cbq_fopt opt;
1545
1546 if (cl->split || cl->defmap) {
1547 opt.split = cl->split ? cl->split->classid : 0;
1548 opt.defmap = cl->defmap;
1549 opt.defchange = ~0;
1550 RTA_PUT(skb, TCA_CBQ_FOPT, sizeof(opt), &opt);
1551 }
1552 return skb->len;
1553
1554 rtattr_failure:
1555 skb_trim(skb, b - skb->data);
1556 return -1;
1557 }
1558
1559 #ifdef CONFIG_NET_CLS_POLICE
1560 static __inline__ int cbq_dump_police(struct sk_buff *skb, struct cbq_class *cl)
1561 {
1562 unsigned char *b = skb->tail;
1563 struct tc_cbq_police opt;
1564
1565 if (cl->police) {
1566 opt.police = cl->police;
1567 opt.__res1 = 0;
1568 opt.__res2 = 0;
1569 RTA_PUT(skb, TCA_CBQ_POLICE, sizeof(opt), &opt);
1570 }
1571 return skb->len;
1572
1573 rtattr_failure:
1574 skb_trim(skb, b - skb->data);
1575 return -1;
1576 }
1577 #endif
1578
1579 static int cbq_dump_attr(struct sk_buff *skb, struct cbq_class *cl)
1580 {
1581 if (cbq_dump_lss(skb, cl) < 0 ||
1582 cbq_dump_rate(skb, cl) < 0 ||
1583 cbq_dump_wrr(skb, cl) < 0 ||
1584 cbq_dump_ovl(skb, cl) < 0 ||
1585 #ifdef CONFIG_NET_CLS_POLICE
1586 cbq_dump_police(skb, cl) < 0 ||
1587 #endif
1588 cbq_dump_fopt(skb, cl) < 0)
1589 return -1;
1590 return 0;
1591 }
1592
1593 static int cbq_dump(struct Qdisc *sch, struct sk_buff *skb)
1594 {
1595 struct cbq_sched_data *q = qdisc_priv(sch);
1596 unsigned char *b = skb->tail;
1597 struct rtattr *rta;
1598
1599 rta = (struct rtattr*)b;
1600 RTA_PUT(skb, TCA_OPTIONS, 0, NULL);
1601 if (cbq_dump_attr(skb, &q->link) < 0)
1602 goto rtattr_failure;
1603 rta->rta_len = skb->tail - b;
1604 return skb->len;
1605
1606 rtattr_failure:
1607 skb_trim(skb, b - skb->data);
1608 return -1;
1609 }
1610
1611 static int
1612 cbq_dump_stats(struct Qdisc *sch, struct gnet_dump *d)
1613 {
1614 struct cbq_sched_data *q = qdisc_priv(sch);
1615
1616 q->link.xstats.avgidle = q->link.avgidle;
1617 return gnet_stats_copy_app(d, &q->link.xstats, sizeof(q->link.xstats));
1618 }
1619
1620 static int
1621 cbq_dump_class(struct Qdisc *sch, unsigned long arg,
1622 struct sk_buff *skb, struct tcmsg *tcm)
1623 {
1624 struct cbq_class *cl = (struct cbq_class*)arg;
1625 unsigned char *b = skb->tail;
1626 struct rtattr *rta;
1627
1628 if (cl->tparent)
1629 tcm->tcm_parent = cl->tparent->classid;
1630 else
1631 tcm->tcm_parent = TC_H_ROOT;
1632 tcm->tcm_handle = cl->classid;
1633 tcm->tcm_info = cl->q->handle;
1634
1635 rta = (struct rtattr*)b;
1636 RTA_PUT(skb, TCA_OPTIONS, 0, NULL);
1637 if (cbq_dump_attr(skb, cl) < 0)
1638 goto rtattr_failure;
1639 rta->rta_len = skb->tail - b;
1640 return skb->len;
1641
1642 rtattr_failure:
1643 skb_trim(skb, b - skb->data);
1644 return -1;
1645 }
1646
1647 static int
1648 cbq_dump_class_stats(struct Qdisc *sch, unsigned long arg,
1649 struct gnet_dump *d)
1650 {
1651 struct cbq_sched_data *q = qdisc_priv(sch);
1652 struct cbq_class *cl = (struct cbq_class*)arg;
1653
1654 cl->qstats.qlen = cl->q->q.qlen;
1655 cl->xstats.avgidle = cl->avgidle;
1656 cl->xstats.undertime = 0;
1657
1658 if (!PSCHED_IS_PASTPERFECT(cl->undertime))
1659 cl->xstats.undertime = PSCHED_TDIFF(cl->undertime, q->now);
1660
1661 if (gnet_stats_copy_basic(d, &cl->bstats) < 0 ||
1662 #ifdef CONFIG_NET_ESTIMATOR
1663 gnet_stats_copy_rate_est(d, &cl->rate_est) < 0 ||
1664 #endif
1665 gnet_stats_copy_queue(d, &cl->qstats) < 0)
1666 return -1;
1667
1668 return gnet_stats_copy_app(d, &cl->xstats, sizeof(cl->xstats));
1669 }
1670
1671 static int cbq_graft(struct Qdisc *sch, unsigned long arg, struct Qdisc *new,
1672 struct Qdisc **old)
1673 {
1674 struct cbq_class *cl = (struct cbq_class*)arg;
1675
1676 if (cl) {
1677 if (new == NULL) {
1678 if ((new = qdisc_create_dflt(sch->dev, &pfifo_qdisc_ops)) == NULL)
1679 return -ENOBUFS;
1680 } else {
1681 #ifdef CONFIG_NET_CLS_POLICE
1682 if (cl->police == TC_POLICE_RECLASSIFY)
1683 new->reshape_fail = cbq_reshape_fail;
1684 #endif
1685 }
1686 sch_tree_lock(sch);
1687 *old = cl->q;
1688 cl->q = new;
1689 sch->q.qlen -= (*old)->q.qlen;
1690 qdisc_reset(*old);
1691 sch_tree_unlock(sch);
1692
1693 return 0;
1694 }
1695 return -ENOENT;
1696 }
1697
1698 static struct Qdisc *
1699 cbq_leaf(struct Qdisc *sch, unsigned long arg)
1700 {
1701 struct cbq_class *cl = (struct cbq_class*)arg;
1702
1703 return cl ? cl->q : NULL;
1704 }
1705
1706 static unsigned long cbq_get(struct Qdisc *sch, u32 classid)
1707 {
1708 struct cbq_sched_data *q = qdisc_priv(sch);
1709 struct cbq_class *cl = cbq_class_lookup(q, classid);
1710
1711 if (cl) {
1712 cl->refcnt++;
1713 return (unsigned long)cl;
1714 }
1715 return 0;
1716 }
1717
1718 static void cbq_destroy_filters(struct cbq_class *cl)
1719 {
1720 struct tcf_proto *tp;
1721
1722 while ((tp = cl->filter_list) != NULL) {
1723 cl->filter_list = tp->next;
1724 tcf_destroy(tp);
1725 }
1726 }
1727
1728 static void cbq_destroy_class(struct Qdisc *sch, struct cbq_class *cl)
1729 {
1730 struct cbq_sched_data *q = qdisc_priv(sch);
1731
1732 BUG_TRAP(!cl->filters);
1733
1734 cbq_destroy_filters(cl);
1735 qdisc_destroy(cl->q);
1736 qdisc_put_rtab(cl->R_tab);
1737 #ifdef CONFIG_NET_ESTIMATOR
1738 gen_kill_estimator(&cl->bstats, &cl->rate_est);
1739 #endif
1740 if (cl != &q->link)
1741 kfree(cl);
1742 }
1743
1744 static void
1745 cbq_destroy(struct Qdisc* sch)
1746 {
1747 struct cbq_sched_data *q = qdisc_priv(sch);
1748 struct cbq_class *cl;
1749 unsigned h;
1750
1751 #ifdef CONFIG_NET_CLS_POLICE
1752 q->rx_class = NULL;
1753 #endif
1754 /*
1755 * Filters must be destroyed first because we don't destroy the
1756 * classes from root to leafs which means that filters can still
1757 * be bound to classes which have been destroyed already. --TGR '04
1758 */
1759 for (h = 0; h < 16; h++)
1760 for (cl = q->classes[h]; cl; cl = cl->next)
1761 cbq_destroy_filters(cl);
1762
1763 for (h = 0; h < 16; h++) {
1764 struct cbq_class *next;
1765
1766 for (cl = q->classes[h]; cl; cl = next) {
1767 next = cl->next;
1768 cbq_destroy_class(sch, cl);
1769 }
1770 }
1771 }
1772
1773 static void cbq_put(struct Qdisc *sch, unsigned long arg)
1774 {
1775 struct cbq_class *cl = (struct cbq_class*)arg;
1776
1777 if (--cl->refcnt == 0) {
1778 #ifdef CONFIG_NET_CLS_POLICE
1779 struct cbq_sched_data *q = qdisc_priv(sch);
1780
1781 spin_lock_bh(&sch->dev->queue_lock);
1782 if (q->rx_class == cl)
1783 q->rx_class = NULL;
1784 spin_unlock_bh(&sch->dev->queue_lock);
1785 #endif
1786
1787 cbq_destroy_class(sch, cl);
1788 }
1789 }
1790
1791 static int
1792 cbq_change_class(struct Qdisc *sch, u32 classid, u32 parentid, struct rtattr **tca,
1793 unsigned long *arg)
1794 {
1795 int err;
1796 struct cbq_sched_data *q = qdisc_priv(sch);
1797 struct cbq_class *cl = (struct cbq_class*)*arg;
1798 struct rtattr *opt = tca[TCA_OPTIONS-1];
1799 struct rtattr *tb[TCA_CBQ_MAX];
1800 struct cbq_class *parent;
1801 struct qdisc_rate_table *rtab = NULL;
1802
1803 if (opt==NULL || rtattr_parse_nested(tb, TCA_CBQ_MAX, opt))
1804 return -EINVAL;
1805
1806 if (tb[TCA_CBQ_OVL_STRATEGY-1] &&
1807 RTA_PAYLOAD(tb[TCA_CBQ_OVL_STRATEGY-1]) < sizeof(struct tc_cbq_ovl))
1808 return -EINVAL;
1809
1810 if (tb[TCA_CBQ_FOPT-1] &&
1811 RTA_PAYLOAD(tb[TCA_CBQ_FOPT-1]) < sizeof(struct tc_cbq_fopt))
1812 return -EINVAL;
1813
1814 if (tb[TCA_CBQ_RATE-1] &&
1815 RTA_PAYLOAD(tb[TCA_CBQ_RATE-1]) < sizeof(struct tc_ratespec))
1816 return -EINVAL;
1817
1818 if (tb[TCA_CBQ_LSSOPT-1] &&
1819 RTA_PAYLOAD(tb[TCA_CBQ_LSSOPT-1]) < sizeof(struct tc_cbq_lssopt))
1820 return -EINVAL;
1821
1822 if (tb[TCA_CBQ_WRROPT-1] &&
1823 RTA_PAYLOAD(tb[TCA_CBQ_WRROPT-1]) < sizeof(struct tc_cbq_wrropt))
1824 return -EINVAL;
1825
1826 #ifdef CONFIG_NET_CLS_POLICE
1827 if (tb[TCA_CBQ_POLICE-1] &&
1828 RTA_PAYLOAD(tb[TCA_CBQ_POLICE-1]) < sizeof(struct tc_cbq_police))
1829 return -EINVAL;
1830 #endif
1831
1832 if (cl) {
1833 /* Check parent */
1834 if (parentid) {
1835 if (cl->tparent && cl->tparent->classid != parentid)
1836 return -EINVAL;
1837 if (!cl->tparent && parentid != TC_H_ROOT)
1838 return -EINVAL;
1839 }
1840
1841 if (tb[TCA_CBQ_RATE-1]) {
1842 rtab = qdisc_get_rtab(RTA_DATA(tb[TCA_CBQ_RATE-1]), tb[TCA_CBQ_RTAB-1]);
1843 if (rtab == NULL)
1844 return -EINVAL;
1845 }
1846
1847 /* Change class parameters */
1848 sch_tree_lock(sch);
1849
1850 if (cl->next_alive != NULL)
1851 cbq_deactivate_class(cl);
1852
1853 if (rtab) {
1854 rtab = xchg(&cl->R_tab, rtab);
1855 qdisc_put_rtab(rtab);
1856 }
1857
1858 if (tb[TCA_CBQ_LSSOPT-1])
1859 cbq_set_lss(cl, RTA_DATA(tb[TCA_CBQ_LSSOPT-1]));
1860
1861 if (tb[TCA_CBQ_WRROPT-1]) {
1862 cbq_rmprio(q, cl);
1863 cbq_set_wrr(cl, RTA_DATA(tb[TCA_CBQ_WRROPT-1]));
1864 }
1865
1866 if (tb[TCA_CBQ_OVL_STRATEGY-1])
1867 cbq_set_overlimit(cl, RTA_DATA(tb[TCA_CBQ_OVL_STRATEGY-1]));
1868
1869 #ifdef CONFIG_NET_CLS_POLICE
1870 if (tb[TCA_CBQ_POLICE-1])
1871 cbq_set_police(cl, RTA_DATA(tb[TCA_CBQ_POLICE-1]));
1872 #endif
1873
1874 if (tb[TCA_CBQ_FOPT-1])
1875 cbq_set_fopt(cl, RTA_DATA(tb[TCA_CBQ_FOPT-1]));
1876
1877 if (cl->q->q.qlen)
1878 cbq_activate_class(cl);
1879
1880 sch_tree_unlock(sch);
1881
1882 #ifdef CONFIG_NET_ESTIMATOR
1883 if (tca[TCA_RATE-1])
1884 gen_replace_estimator(&cl->bstats, &cl->rate_est,
1885 cl->stats_lock, tca[TCA_RATE-1]);
1886 #endif
1887 return 0;
1888 }
1889
1890 if (parentid == TC_H_ROOT)
1891 return -EINVAL;
1892
1893 if (tb[TCA_CBQ_WRROPT-1] == NULL || tb[TCA_CBQ_RATE-1] == NULL ||
1894 tb[TCA_CBQ_LSSOPT-1] == NULL)
1895 return -EINVAL;
1896
1897 rtab = qdisc_get_rtab(RTA_DATA(tb[TCA_CBQ_RATE-1]), tb[TCA_CBQ_RTAB-1]);
1898 if (rtab == NULL)
1899 return -EINVAL;
1900
1901 if (classid) {
1902 err = -EINVAL;
1903 if (TC_H_MAJ(classid^sch->handle) || cbq_class_lookup(q, classid))
1904 goto failure;
1905 } else {
1906 int i;
1907 classid = TC_H_MAKE(sch->handle,0x8000);
1908
1909 for (i=0; i<0x8000; i++) {
1910 if (++q->hgenerator >= 0x8000)
1911 q->hgenerator = 1;
1912 if (cbq_class_lookup(q, classid|q->hgenerator) == NULL)
1913 break;
1914 }
1915 err = -ENOSR;
1916 if (i >= 0x8000)
1917 goto failure;
1918 classid = classid|q->hgenerator;
1919 }
1920
1921 parent = &q->link;
1922 if (parentid) {
1923 parent = cbq_class_lookup(q, parentid);
1924 err = -EINVAL;
1925 if (parent == NULL)
1926 goto failure;
1927 }
1928
1929 err = -ENOBUFS;
1930 cl = kmalloc(sizeof(*cl), GFP_KERNEL);
1931 if (cl == NULL)
1932 goto failure;
1933 memset(cl, 0, sizeof(*cl));
1934 cl->R_tab = rtab;
1935 rtab = NULL;
1936 cl->refcnt = 1;
1937 if (!(cl->q = qdisc_create_dflt(sch->dev, &pfifo_qdisc_ops)))
1938 cl->q = &noop_qdisc;
1939 cl->classid = classid;
1940 cl->tparent = parent;
1941 cl->qdisc = sch;
1942 cl->allot = parent->allot;
1943 cl->quantum = cl->allot;
1944 cl->weight = cl->R_tab->rate.rate;
1945 cl->stats_lock = &sch->dev->queue_lock;
1946
1947 sch_tree_lock(sch);
1948 cbq_link_class(cl);
1949 cl->borrow = cl->tparent;
1950 if (cl->tparent != &q->link)
1951 cl->share = cl->tparent;
1952 cbq_adjust_levels(parent);
1953 cl->minidle = -0x7FFFFFFF;
1954 cbq_set_lss(cl, RTA_DATA(tb[TCA_CBQ_LSSOPT-1]));
1955 cbq_set_wrr(cl, RTA_DATA(tb[TCA_CBQ_WRROPT-1]));
1956 if (cl->ewma_log==0)
1957 cl->ewma_log = q->link.ewma_log;
1958 if (cl->maxidle==0)
1959 cl->maxidle = q->link.maxidle;
1960 if (cl->avpkt==0)
1961 cl->avpkt = q->link.avpkt;
1962 cl->overlimit = cbq_ovl_classic;
1963 if (tb[TCA_CBQ_OVL_STRATEGY-1])
1964 cbq_set_overlimit(cl, RTA_DATA(tb[TCA_CBQ_OVL_STRATEGY-1]));
1965 #ifdef CONFIG_NET_CLS_POLICE
1966 if (tb[TCA_CBQ_POLICE-1])
1967 cbq_set_police(cl, RTA_DATA(tb[TCA_CBQ_POLICE-1]));
1968 #endif
1969 if (tb[TCA_CBQ_FOPT-1])
1970 cbq_set_fopt(cl, RTA_DATA(tb[TCA_CBQ_FOPT-1]));
1971 sch_tree_unlock(sch);
1972
1973 #ifdef CONFIG_NET_ESTIMATOR
1974 if (tca[TCA_RATE-1])
1975 gen_new_estimator(&cl->bstats, &cl->rate_est,
1976 cl->stats_lock, tca[TCA_RATE-1]);
1977 #endif
1978
1979 *arg = (unsigned long)cl;
1980 return 0;
1981
1982 failure:
1983 qdisc_put_rtab(rtab);
1984 return err;
1985 }
1986
1987 static int cbq_delete(struct Qdisc *sch, unsigned long arg)
1988 {
1989 struct cbq_sched_data *q = qdisc_priv(sch);
1990 struct cbq_class *cl = (struct cbq_class*)arg;
1991
1992 if (cl->filters || cl->children || cl == &q->link)
1993 return -EBUSY;
1994
1995 sch_tree_lock(sch);
1996
1997 if (cl->next_alive)
1998 cbq_deactivate_class(cl);
1999
2000 if (q->tx_borrowed == cl)
2001 q->tx_borrowed = q->tx_class;
2002 if (q->tx_class == cl) {
2003 q->tx_class = NULL;
2004 q->tx_borrowed = NULL;
2005 }
2006 #ifdef CONFIG_NET_CLS_POLICE
2007 if (q->rx_class == cl)
2008 q->rx_class = NULL;
2009 #endif
2010
2011 cbq_unlink_class(cl);
2012 cbq_adjust_levels(cl->tparent);
2013 cl->defmap = 0;
2014 cbq_sync_defmap(cl);
2015
2016 cbq_rmprio(q, cl);
2017 sch_tree_unlock(sch);
2018
2019 if (--cl->refcnt == 0)
2020 cbq_destroy_class(sch, cl);
2021
2022 return 0;
2023 }
2024
2025 static struct tcf_proto **cbq_find_tcf(struct Qdisc *sch, unsigned long arg)
2026 {
2027 struct cbq_sched_data *q = qdisc_priv(sch);
2028 struct cbq_class *cl = (struct cbq_class *)arg;
2029
2030 if (cl == NULL)
2031 cl = &q->link;
2032
2033 return &cl->filter_list;
2034 }
2035
2036 static unsigned long cbq_bind_filter(struct Qdisc *sch, unsigned long parent,
2037 u32 classid)
2038 {
2039 struct cbq_sched_data *q = qdisc_priv(sch);
2040 struct cbq_class *p = (struct cbq_class*)parent;
2041 struct cbq_class *cl = cbq_class_lookup(q, classid);
2042
2043 if (cl) {
2044 if (p && p->level <= cl->level)
2045 return 0;
2046 cl->filters++;
2047 return (unsigned long)cl;
2048 }
2049 return 0;
2050 }
2051
2052 static void cbq_unbind_filter(struct Qdisc *sch, unsigned long arg)
2053 {
2054 struct cbq_class *cl = (struct cbq_class*)arg;
2055
2056 cl->filters--;
2057 }
2058
2059 static void cbq_walk(struct Qdisc *sch, struct qdisc_walker *arg)
2060 {
2061 struct cbq_sched_data *q = qdisc_priv(sch);
2062 unsigned h;
2063
2064 if (arg->stop)
2065 return;
2066
2067 for (h = 0; h < 16; h++) {
2068 struct cbq_class *cl;
2069
2070 for (cl = q->classes[h]; cl; cl = cl->next) {
2071 if (arg->count < arg->skip) {
2072 arg->count++;
2073 continue;
2074 }
2075 if (arg->fn(sch, (unsigned long)cl, arg) < 0) {
2076 arg->stop = 1;
2077 return;
2078 }
2079 arg->count++;
2080 }
2081 }
2082 }
2083
2084 static struct Qdisc_class_ops cbq_class_ops = {
2085 .graft = cbq_graft,
2086 .leaf = cbq_leaf,
2087 .get = cbq_get,
2088 .put = cbq_put,
2089 .change = cbq_change_class,
2090 .delete = cbq_delete,
2091 .walk = cbq_walk,
2092 .tcf_chain = cbq_find_tcf,
2093 .bind_tcf = cbq_bind_filter,
2094 .unbind_tcf = cbq_unbind_filter,
2095 .dump = cbq_dump_class,
2096 .dump_stats = cbq_dump_class_stats,
2097 };
2098
2099 static struct Qdisc_ops cbq_qdisc_ops = {
2100 .next = NULL,
2101 .cl_ops = &cbq_class_ops,
2102 .id = "cbq",
2103 .priv_size = sizeof(struct cbq_sched_data),
2104 .enqueue = cbq_enqueue,
2105 .dequeue = cbq_dequeue,
2106 .requeue = cbq_requeue,
2107 .drop = cbq_drop,
2108 .init = cbq_init,
2109 .reset = cbq_reset,
2110 .destroy = cbq_destroy,
2111 .change = NULL,
2112 .dump = cbq_dump,
2113 .dump_stats = cbq_dump_stats,
2114 .owner = THIS_MODULE,
2115 };
2116
2117 static int __init cbq_module_init(void)
2118 {
2119 return register_qdisc(&cbq_qdisc_ops);
2120 }
2121 static void __exit cbq_module_exit(void)
2122 {
2123 unregister_qdisc(&cbq_qdisc_ops);
2124 }
2125 module_init(cbq_module_init)
2126 module_exit(cbq_module_exit)
2127 MODULE_LICENSE("GPL");
Linux with added FPC-III support