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