?  search:
summary | log | graphiclog1 | graphiclog2 | commit | commitdiff | tree | refs | edit | fork
blame | history | raw | HEAD
[PATCH] trivial s2io annotations
[linux-2.6.22.y-op.git] / net / sched / sch_cbq.c
blobf79a4f3d0a9584db88107acd901347c96a110087
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 return;
375 }
376 } while ((cl_prev = cl) != q->active[prio]);
377 }
378
379 static void
380 cbq_mark_toplevel(struct cbq_sched_data *q, struct cbq_class *cl)
381 {
382 int toplevel = q->toplevel;
383
384 if (toplevel > cl->level && !(cl->q->flags&TCQ_F_THROTTLED)) {
385 psched_time_t now;
386 psched_tdiff_t incr;
387
388 PSCHED_GET_TIME(now);
389 incr = PSCHED_TDIFF(now, q->now_rt);
390 PSCHED_TADD2(q->now, incr, now);
391
392 do {
393 if (PSCHED_TLESS(cl->undertime, now)) {
394 q->toplevel = cl->level;
395 return;
396 }
397 } while ((cl=cl->borrow) != NULL && toplevel > cl->level);
398 }
399 }
400
401 static int
402 cbq_enqueue(struct sk_buff *skb, struct Qdisc *sch)
403 {
404 struct cbq_sched_data *q = qdisc_priv(sch);
405 int len = skb->len;
406 int ret;
407 struct cbq_class *cl = cbq_classify(skb, sch, &ret);
408
409 #ifdef CONFIG_NET_CLS_POLICE
410 q->rx_class = cl;
411 #endif
412 if (cl == NULL) {
413 if (ret == NET_XMIT_BYPASS)
414 sch->qstats.drops++;
415 kfree_skb(skb);
416 return ret;
417 }
418
419 #ifdef CONFIG_NET_CLS_POLICE
420 cl->q->__parent = sch;
421 #endif
422 if ((ret = cl->q->enqueue(skb, cl->q)) == NET_XMIT_SUCCESS) {
423 sch->q.qlen++;
424 sch->bstats.packets++;
425 sch->bstats.bytes+=len;
426 cbq_mark_toplevel(q, cl);
427 if (!cl->next_alive)
428 cbq_activate_class(cl);
429 return ret;
430 }
431
432 sch->qstats.drops++;
433 cbq_mark_toplevel(q, cl);
434 cl->qstats.drops++;
435 return ret;
436 }
437
438 static int
439 cbq_requeue(struct sk_buff *skb, struct Qdisc *sch)
440 {
441 struct cbq_sched_data *q = qdisc_priv(sch);
442 struct cbq_class *cl;
443 int ret;
444
445 if ((cl = q->tx_class) == NULL) {
446 kfree_skb(skb);
447 sch->qstats.drops++;
448 return NET_XMIT_CN;
449 }
450 q->tx_class = NULL;
451
452 cbq_mark_toplevel(q, cl);
453
454 #ifdef CONFIG_NET_CLS_POLICE
455 q->rx_class = cl;
456 cl->q->__parent = sch;
457 #endif
458 if ((ret = cl->q->ops->requeue(skb, cl->q)) == 0) {
459 sch->q.qlen++;
460 sch->qstats.requeues++;
461 if (!cl->next_alive)
462 cbq_activate_class(cl);
463 return 0;
464 }
465 sch->qstats.drops++;
466 cl->qstats.drops++;
467 return ret;
468 }
469
470 /* Overlimit actions */
471
472 /* TC_CBQ_OVL_CLASSIC: (default) penalize leaf class by adding offtime */
473
474 static void cbq_ovl_classic(struct cbq_class *cl)
475 {
476 struct cbq_sched_data *q = qdisc_priv(cl->qdisc);
477 psched_tdiff_t delay = PSCHED_TDIFF(cl->undertime, q->now);
478
479 if (!cl->delayed) {
480 delay += cl->offtime;
481
482 /*
483 Class goes to sleep, so that it will have no
484 chance to work avgidle. Let's forgive it 8)
485
486 BTW cbq-2.0 has a crap in this
487 place, apparently they forgot to shift it by cl->ewma_log.
488 */
489 if (cl->avgidle < 0)
490 delay -= (-cl->avgidle) - ((-cl->avgidle) >> cl->ewma_log);
491 if (cl->avgidle < cl->minidle)
492 cl->avgidle = cl->minidle;
493 if (delay <= 0)
494 delay = 1;
495 PSCHED_TADD2(q->now, delay, cl->undertime);
496
497 cl->xstats.overactions++;
498 cl->delayed = 1;
499 }
500 if (q->wd_expires == 0 || q->wd_expires > delay)
501 q->wd_expires = delay;
502
503 /* Dirty work! We must schedule wakeups based on
504 real available rate, rather than leaf rate,
505 which may be tiny (even zero).
506 */
507 if (q->toplevel == TC_CBQ_MAXLEVEL) {
508 struct cbq_class *b;
509 psched_tdiff_t base_delay = q->wd_expires;
510
511 for (b = cl->borrow; b; b = b->borrow) {
512 delay = PSCHED_TDIFF(b->undertime, q->now);
513 if (delay < base_delay) {
514 if (delay <= 0)
515 delay = 1;
516 base_delay = delay;
517 }
518 }
519
520 q->wd_expires = base_delay;
521 }
522 }
523
524 /* TC_CBQ_OVL_RCLASSIC: penalize by offtime classes in hierarchy, when
525 they go overlimit
526 */
527
528 static void cbq_ovl_rclassic(struct cbq_class *cl)
529 {
530 struct cbq_sched_data *q = qdisc_priv(cl->qdisc);
531 struct cbq_class *this = cl;
532
533 do {
534 if (cl->level > q->toplevel) {
535 cl = NULL;
536 break;
537 }
538 } while ((cl = cl->borrow) != NULL);
539
540 if (cl == NULL)
541 cl = this;
542 cbq_ovl_classic(cl);
543 }
544
545 /* TC_CBQ_OVL_DELAY: delay until it will go to underlimit */
546
547 static void cbq_ovl_delay(struct cbq_class *cl)
548 {
549 struct cbq_sched_data *q = qdisc_priv(cl->qdisc);
550 psched_tdiff_t delay = PSCHED_TDIFF(cl->undertime, q->now);
551
552 if (!cl->delayed) {
553 unsigned long sched = jiffies;
554
555 delay += cl->offtime;
556 if (cl->avgidle < 0)
557 delay -= (-cl->avgidle) - ((-cl->avgidle) >> cl->ewma_log);
558 if (cl->avgidle < cl->minidle)
559 cl->avgidle = cl->minidle;
560 PSCHED_TADD2(q->now, delay, cl->undertime);
561
562 if (delay > 0) {
563 sched += PSCHED_US2JIFFIE(delay) + cl->penalty;
564 cl->penalized = sched;
565 cl->cpriority = TC_CBQ_MAXPRIO;
566 q->pmask |= (1<<TC_CBQ_MAXPRIO);
567 if (del_timer(&q->delay_timer) &&
568 (long)(q->delay_timer.expires - sched) > 0)
569 q->delay_timer.expires = sched;
570 add_timer(&q->delay_timer);
571 cl->delayed = 1;
572 cl->xstats.overactions++;
573 return;
574 }
575 delay = 1;
576 }
577 if (q->wd_expires == 0 || q->wd_expires > delay)
578 q->wd_expires = delay;
579 }
580
581 /* TC_CBQ_OVL_LOWPRIO: penalize class by lowering its priority band */
582
583 static void cbq_ovl_lowprio(struct cbq_class *cl)
584 {
585 struct cbq_sched_data *q = qdisc_priv(cl->qdisc);
586
587 cl->penalized = jiffies + cl->penalty;
588
589 if (cl->cpriority != cl->priority2) {
590 cl->cpriority = cl->priority2;
591 q->pmask |= (1<<cl->cpriority);
592 cl->xstats.overactions++;
593 }
594 cbq_ovl_classic(cl);
595 }
596
597 /* TC_CBQ_OVL_DROP: penalize class by dropping */
598
599 static void cbq_ovl_drop(struct cbq_class *cl)
600 {
601 if (cl->q->ops->drop)
602 if (cl->q->ops->drop(cl->q))
603 cl->qdisc->q.qlen--;
604 cl->xstats.overactions++;
605 cbq_ovl_classic(cl);
606 }
607
608 static void cbq_watchdog(unsigned long arg)
609 {
610 struct Qdisc *sch = (struct Qdisc*)arg;
611
612 sch->flags &= ~TCQ_F_THROTTLED;
613 netif_schedule(sch->dev);
614 }
615
616 static unsigned long cbq_undelay_prio(struct cbq_sched_data *q, int prio)
617 {
618 struct cbq_class *cl;
619 struct cbq_class *cl_prev = q->active[prio];
620 unsigned long now = jiffies;
621 unsigned long sched = now;
622
623 if (cl_prev == NULL)
624 return now;
625
626 do {
627 cl = cl_prev->next_alive;
628 if ((long)(now - cl->penalized) > 0) {
629 cl_prev->next_alive = cl->next_alive;
630 cl->next_alive = NULL;
631 cl->cpriority = cl->priority;
632 cl->delayed = 0;
633 cbq_activate_class(cl);
634
635 if (cl == q->active[prio]) {
636 q->active[prio] = cl_prev;
637 if (cl == q->active[prio]) {
638 q->active[prio] = NULL;
639 return 0;
640 }
641 }
642
643 cl = cl_prev->next_alive;
644 } else if ((long)(sched - cl->penalized) > 0)
645 sched = cl->penalized;
646 } while ((cl_prev = cl) != q->active[prio]);
647
648 return (long)(sched - now);
649 }
650
651 static void cbq_undelay(unsigned long arg)
652 {
653 struct Qdisc *sch = (struct Qdisc*)arg;
654 struct cbq_sched_data *q = qdisc_priv(sch);
655 long delay = 0;
656 unsigned pmask;
657
658 pmask = q->pmask;
659 q->pmask = 0;
660
661 while (pmask) {
662 int prio = ffz(~pmask);
663 long tmp;
664
665 pmask &= ~(1<<prio);
666
667 tmp = cbq_undelay_prio(q, prio);
668 if (tmp > 0) {
669 q->pmask |= 1<<prio;
670 if (tmp < delay || delay == 0)
671 delay = tmp;
672 }
673 }
674
675 if (delay) {
676 q->delay_timer.expires = jiffies + delay;
677 add_timer(&q->delay_timer);
678 }
679
680 sch->flags &= ~TCQ_F_THROTTLED;
681 netif_schedule(sch->dev);
682 }
683
684
685 #ifdef CONFIG_NET_CLS_POLICE
686
687 static int cbq_reshape_fail(struct sk_buff *skb, struct Qdisc *child)
688 {
689 int len = skb->len;
690 struct Qdisc *sch = child->__parent;
691 struct cbq_sched_data *q = qdisc_priv(sch);
692 struct cbq_class *cl = q->rx_class;
693
694 q->rx_class = NULL;
695
696 if (cl && (cl = cbq_reclassify(skb, cl)) != NULL) {
697
698 cbq_mark_toplevel(q, cl);
699
700 q->rx_class = cl;
701 cl->q->__parent = sch;
702
703 if (cl->q->enqueue(skb, cl->q) == 0) {
704 sch->q.qlen++;
705 sch->bstats.packets++;
706 sch->bstats.bytes+=len;
707 if (!cl->next_alive)
708 cbq_activate_class(cl);
709 return 0;
710 }
711 sch->qstats.drops++;
712 return 0;
713 }
714
715 sch->qstats.drops++;
716 return -1;
717 }
718 #endif
719
720 /*
721 It is mission critical procedure.
722
723 We "regenerate" toplevel cutoff, if transmitting class
724 has backlog and it is not regulated. It is not part of
725 original CBQ description, but looks more reasonable.
726 Probably, it is wrong. This question needs further investigation.
727 */
728
729 static __inline__ void
730 cbq_update_toplevel(struct cbq_sched_data *q, struct cbq_class *cl,
731 struct cbq_class *borrowed)
732 {
733 if (cl && q->toplevel >= borrowed->level) {
734 if (cl->q->q.qlen > 1) {
735 do {
736 if (PSCHED_IS_PASTPERFECT(borrowed->undertime)) {
737 q->toplevel = borrowed->level;
738 return;
739 }
740 } while ((borrowed=borrowed->borrow) != NULL);
741 }
742 #if 0
743 /* It is not necessary now. Uncommenting it
744 will save CPU cycles, but decrease fairness.
745 */
746 q->toplevel = TC_CBQ_MAXLEVEL;
747 #endif
748 }
749 }
750
751 static void
752 cbq_update(struct cbq_sched_data *q)
753 {
754 struct cbq_class *this = q->tx_class;
755 struct cbq_class *cl = this;
756 int len = q->tx_len;
757
758 q->tx_class = NULL;
759
760 for ( ; cl; cl = cl->share) {
761 long avgidle = cl->avgidle;
762 long idle;
763
764 cl->bstats.packets++;
765 cl->bstats.bytes += len;
766
767 /*
768 (now - last) is total time between packet right edges.
769 (last_pktlen/rate) is "virtual" busy time, so that
770
771 idle = (now - last) - last_pktlen/rate
772 */
773
774 idle = PSCHED_TDIFF(q->now, cl->last);
775 if ((unsigned long)idle > 128*1024*1024) {
776 avgidle = cl->maxidle;
777 } else {
778 idle -= L2T(cl, len);
779
780 /* true_avgidle := (1-W)*true_avgidle + W*idle,
781 where W=2^{-ewma_log}. But cl->avgidle is scaled:
782 cl->avgidle == true_avgidle/W,
783 hence:
784 */
785 avgidle += idle - (avgidle>>cl->ewma_log);
786 }
787
788 if (avgidle <= 0) {
789 /* Overlimit or at-limit */
790
791 if (avgidle < cl->minidle)
792 avgidle = cl->minidle;
793
794 cl->avgidle = avgidle;
795
796 /* Calculate expected time, when this class
797 will be allowed to send.
798 It will occur, when:
799 (1-W)*true_avgidle + W*delay = 0, i.e.
800 idle = (1/W - 1)*(-true_avgidle)
801 or
802 idle = (1 - W)*(-cl->avgidle);
803 */
804 idle = (-avgidle) - ((-avgidle) >> cl->ewma_log);
805
806 /*
807 That is not all.
808 To maintain the rate allocated to the class,
809 we add to undertime virtual clock,
810 necessary to complete transmitted packet.
811 (len/phys_bandwidth has been already passed
812 to the moment of cbq_update)
813 */
814
815 idle -= L2T(&q->link, len);
816 idle += L2T(cl, len);
817
818 PSCHED_AUDIT_TDIFF(idle);
819
820 PSCHED_TADD2(q->now, idle, cl->undertime);
821 } else {
822 /* Underlimit */
823
824 PSCHED_SET_PASTPERFECT(cl->undertime);
825 if (avgidle > cl->maxidle)
826 cl->avgidle = cl->maxidle;
827 else
828 cl->avgidle = avgidle;
829 }
830 cl->last = q->now;
831 }
832
833 cbq_update_toplevel(q, this, q->tx_borrowed);
834 }
835
836 static __inline__ struct cbq_class *
837 cbq_under_limit(struct cbq_class *cl)
838 {
839 struct cbq_sched_data *q = qdisc_priv(cl->qdisc);
840 struct cbq_class *this_cl = cl;
841
842 if (cl->tparent == NULL)
843 return cl;
844
845 if (PSCHED_IS_PASTPERFECT(cl->undertime) ||
846 !PSCHED_TLESS(q->now, cl->undertime)) {
847 cl->delayed = 0;
848 return cl;
849 }
850
851 do {
852 /* It is very suspicious place. Now overlimit
853 action is generated for not bounded classes
854 only if link is completely congested.
855 Though it is in agree with ancestor-only paradigm,
856 it looks very stupid. Particularly,
857 it means that this chunk of code will either
858 never be called or result in strong amplification
859 of burstiness. Dangerous, silly, and, however,
860 no another solution exists.
861 */
862 if ((cl = cl->borrow) == NULL) {
863 this_cl->qstats.overlimits++;
864 this_cl->overlimit(this_cl);
865 return NULL;
866 }
867 if (cl->level > q->toplevel)
868 return NULL;
869 } while (!PSCHED_IS_PASTPERFECT(cl->undertime) &&
870 PSCHED_TLESS(q->now, cl->undertime));
871
872 cl->delayed = 0;
873 return cl;
874 }
875
876 static __inline__ struct sk_buff *
877 cbq_dequeue_prio(struct Qdisc *sch, int prio)
878 {
879 struct cbq_sched_data *q = qdisc_priv(sch);
880 struct cbq_class *cl_tail, *cl_prev, *cl;
881 struct sk_buff *skb;
882 int deficit;
883
884 cl_tail = cl_prev = q->active[prio];
885 cl = cl_prev->next_alive;
886
887 do {
888 deficit = 0;
889
890 /* Start round */
891 do {
892 struct cbq_class *borrow = cl;
893
894 if (cl->q->q.qlen &&
895 (borrow = cbq_under_limit(cl)) == NULL)
896 goto skip_class;
897
898 if (cl->deficit <= 0) {
899 /* Class exhausted its allotment per
900 this round. Switch to the next one.
901 */
902 deficit = 1;
903 cl->deficit += cl->quantum;
904 goto next_class;
905 }
906
907 skb = cl->q->dequeue(cl->q);
908
909 /* Class did not give us any skb :-(
910 It could occur even if cl->q->q.qlen != 0
911 f.e. if cl->q == "tbf"
912 */
913 if (skb == NULL)
914 goto skip_class;
915
916 cl->deficit -= skb->len;
917 q->tx_class = cl;
918 q->tx_borrowed = borrow;
919 if (borrow != cl) {
920 #ifndef CBQ_XSTATS_BORROWS_BYTES
921 borrow->xstats.borrows++;
922 cl->xstats.borrows++;
923 #else
924 borrow->xstats.borrows += skb->len;
925 cl->xstats.borrows += skb->len;
926 #endif
927 }
928 q->tx_len = skb->len;
929
930 if (cl->deficit <= 0) {
931 q->active[prio] = cl;
932 cl = cl->next_alive;
933 cl->deficit += cl->quantum;
934 }
935 return skb;
936
937 skip_class:
938 if (cl->q->q.qlen == 0 || prio != cl->cpriority) {
939 /* Class is empty or penalized.
940 Unlink it from active chain.
941 */
942 cl_prev->next_alive = cl->next_alive;
943 cl->next_alive = NULL;
944
945 /* Did cl_tail point to it? */
946 if (cl == cl_tail) {
947 /* Repair it! */
948 cl_tail = cl_prev;
949
950 /* Was it the last class in this band? */
951 if (cl == cl_tail) {
952 /* Kill the band! */
953 q->active[prio] = NULL;
954 q->activemask &= ~(1<<prio);
955 if (cl->q->q.qlen)
956 cbq_activate_class(cl);
957 return NULL;
958 }
959
960 q->active[prio] = cl_tail;
961 }
962 if (cl->q->q.qlen)
963 cbq_activate_class(cl);
964
965 cl = cl_prev;
966 }
967
968 next_class:
969 cl_prev = cl;
970 cl = cl->next_alive;
971 } while (cl_prev != cl_tail);
972 } while (deficit);
973
974 q->active[prio] = cl_prev;
975
976 return NULL;
977 }
978
979 static __inline__ struct sk_buff *
980 cbq_dequeue_1(struct Qdisc *sch)
981 {
982 struct cbq_sched_data *q = qdisc_priv(sch);
983 struct sk_buff *skb;
984 unsigned activemask;
985
986 activemask = q->activemask&0xFF;
987 while (activemask) {
988 int prio = ffz(~activemask);
989 activemask &= ~(1<<prio);
990 skb = cbq_dequeue_prio(sch, prio);
991 if (skb)
992 return skb;
993 }
994 return NULL;
995 }
996
997 static struct sk_buff *
998 cbq_dequeue(struct Qdisc *sch)
999 {
1000 struct sk_buff *skb;
1001 struct cbq_sched_data *q = qdisc_priv(sch);
1002 psched_time_t now;
1003 psched_tdiff_t incr;
1004
1005 PSCHED_GET_TIME(now);
1006 incr = PSCHED_TDIFF(now, q->now_rt);
1007
1008 if (q->tx_class) {
1009 psched_tdiff_t incr2;
1010 /* Time integrator. We calculate EOS time
1011 by adding expected packet transmission time.
1012 If real time is greater, we warp artificial clock,
1013 so that:
1014
1015 cbq_time = max(real_time, work);
1016 */
1017 incr2 = L2T(&q->link, q->tx_len);
1018 PSCHED_TADD(q->now, incr2);
1019 cbq_update(q);
1020 if ((incr -= incr2) < 0)
1021 incr = 0;
1022 }
1023 PSCHED_TADD(q->now, incr);
1024 q->now_rt = now;
1025
1026 for (;;) {
1027 q->wd_expires = 0;
1028
1029 skb = cbq_dequeue_1(sch);
1030 if (skb) {
1031 sch->q.qlen--;
1032 sch->flags &= ~TCQ_F_THROTTLED;
1033 return skb;
1034 }
1035
1036 /* All the classes are overlimit.
1037
1038 It is possible, if:
1039
1040 1. Scheduler is empty.
1041 2. Toplevel cutoff inhibited borrowing.
1042 3. Root class is overlimit.
1043
1044 Reset 2d and 3d conditions and retry.
1045
1046 Note, that NS and cbq-2.0 are buggy, peeking
1047 an arbitrary class is appropriate for ancestor-only
1048 sharing, but not for toplevel algorithm.
1049
1050 Our version is better, but slower, because it requires
1051 two passes, but it is unavoidable with top-level sharing.
1052 */
1053
1054 if (q->toplevel == TC_CBQ_MAXLEVEL &&
1055 PSCHED_IS_PASTPERFECT(q->link.undertime))
1056 break;
1057
1058 q->toplevel = TC_CBQ_MAXLEVEL;
1059 PSCHED_SET_PASTPERFECT(q->link.undertime);
1060 }
1061
1062 /* No packets in scheduler or nobody wants to give them to us :-(
1063 Sigh... start watchdog timer in the last case. */
1064
1065 if (sch->q.qlen) {
1066 sch->qstats.overlimits++;
1067 if (q->wd_expires) {
1068 long delay = PSCHED_US2JIFFIE(q->wd_expires);
1069 if (delay <= 0)
1070 delay = 1;
1071 mod_timer(&q->wd_timer, jiffies + delay);
1072 sch->flags |= TCQ_F_THROTTLED;
1073 }
1074 }
1075 return NULL;
1076 }
1077
1078 /* CBQ class maintanance routines */
1079
1080 static void cbq_adjust_levels(struct cbq_class *this)
1081 {
1082 if (this == NULL)
1083 return;
1084
1085 do {
1086 int level = 0;
1087 struct cbq_class *cl;
1088
1089 if ((cl = this->children) != NULL) {
1090 do {
1091 if (cl->level > level)
1092 level = cl->level;
1093 } while ((cl = cl->sibling) != this->children);
1094 }
1095 this->level = level+1;
1096 } while ((this = this->tparent) != NULL);
1097 }
1098
1099 static void cbq_normalize_quanta(struct cbq_sched_data *q, int prio)
1100 {
1101 struct cbq_class *cl;
1102 unsigned h;
1103
1104 if (q->quanta[prio] == 0)
1105 return;
1106
1107 for (h=0; h<16; h++) {
1108 for (cl = q->classes[h]; cl; cl = cl->next) {
1109 /* BUGGGG... Beware! This expression suffer of
1110 arithmetic overflows!
1111 */
1112 if (cl->priority == prio) {
1113 cl->quantum = (cl->weight*cl->allot*q->nclasses[prio])/
1114 q->quanta[prio];
1115 }
1116 if (cl->quantum <= 0 || cl->quantum>32*cl->qdisc->dev->mtu) {
1117 printk(KERN_WARNING "CBQ: class %08x has bad quantum==%ld, repaired.\n", cl->classid, cl->quantum);
1118 cl->quantum = cl->qdisc->dev->mtu/2 + 1;
1119 }
1120 }
1121 }
1122 }
1123
1124 static void cbq_sync_defmap(struct cbq_class *cl)
1125 {
1126 struct cbq_sched_data *q = qdisc_priv(cl->qdisc);
1127 struct cbq_class *split = cl->split;
1128 unsigned h;
1129 int i;
1130
1131 if (split == NULL)
1132 return;
1133
1134 for (i=0; i<=TC_PRIO_MAX; i++) {
1135 if (split->defaults[i] == cl && !(cl->defmap&(1<<i)))
1136 split->defaults[i] = NULL;
1137 }
1138
1139 for (i=0; i<=TC_PRIO_MAX; i++) {
1140 int level = split->level;
1141
1142 if (split->defaults[i])
1143 continue;
1144
1145 for (h=0; h<16; h++) {
1146 struct cbq_class *c;
1147
1148 for (c = q->classes[h]; c; c = c->next) {
1149 if (c->split == split && c->level < level &&
1150 c->defmap&(1<<i)) {
1151 split->defaults[i] = c;
1152 level = c->level;
1153 }
1154 }
1155 }
1156 }
1157 }
1158
1159 static void cbq_change_defmap(struct cbq_class *cl, u32 splitid, u32 def, u32 mask)
1160 {
1161 struct cbq_class *split = NULL;
1162
1163 if (splitid == 0) {
1164 if ((split = cl->split) == NULL)
1165 return;
1166 splitid = split->classid;
1167 }
1168
1169 if (split == NULL || split->classid != splitid) {
1170 for (split = cl->tparent; split; split = split->tparent)
1171 if (split->classid == splitid)
1172 break;
1173 }
1174
1175 if (split == NULL)
1176 return;
1177
1178 if (cl->split != split) {
1179 cl->defmap = 0;
1180 cbq_sync_defmap(cl);
1181 cl->split = split;
1182 cl->defmap = def&mask;
1183 } else
1184 cl->defmap = (cl->defmap&~mask)|(def&mask);
1185
1186 cbq_sync_defmap(cl);
1187 }
1188
1189 static void cbq_unlink_class(struct cbq_class *this)
1190 {
1191 struct cbq_class *cl, **clp;
1192 struct cbq_sched_data *q = qdisc_priv(this->qdisc);
1193
1194 for (clp = &q->classes[cbq_hash(this->classid)]; (cl = *clp) != NULL; clp = &cl->next) {
1195 if (cl == this) {
1196 *clp = cl->next;
1197 cl->next = NULL;
1198 break;
1199 }
1200 }
1201
1202 if (this->tparent) {
1203 clp=&this->sibling;
1204 cl = *clp;
1205 do {
1206 if (cl == this) {
1207 *clp = cl->sibling;
1208 break;
1209 }
1210 clp = &cl->sibling;
1211 } while ((cl = *clp) != this->sibling);
1212
1213 if (this->tparent->children == this) {
1214 this->tparent->children = this->sibling;
1215 if (this->sibling == this)
1216 this->tparent->children = NULL;
1217 }
1218 } else {
1219 BUG_TRAP(this->sibling == this);
1220 }
1221 }
1222
1223 static void cbq_link_class(struct cbq_class *this)
1224 {
1225 struct cbq_sched_data *q = qdisc_priv(this->qdisc);
1226 unsigned h = cbq_hash(this->classid);
1227 struct cbq_class *parent = this->tparent;
1228
1229 this->sibling = this;
1230 this->next = q->classes[h];
1231 q->classes[h] = this;
1232
1233 if (parent == NULL)
1234 return;
1235
1236 if (parent->children == NULL) {
1237 parent->children = this;
1238 } else {
1239 this->sibling = parent->children->sibling;
1240 parent->children->sibling = this;
1241 }
1242 }
1243
1244 static unsigned int cbq_drop(struct Qdisc* sch)
1245 {
1246 struct cbq_sched_data *q = qdisc_priv(sch);
1247 struct cbq_class *cl, *cl_head;
1248 int prio;
1249 unsigned int len;
1250
1251 for (prio = TC_CBQ_MAXPRIO; prio >= 0; prio--) {
1252 if ((cl_head = q->active[prio]) == NULL)
1253 continue;
1254
1255 cl = cl_head;
1256 do {
1257 if (cl->q->ops->drop && (len = cl->q->ops->drop(cl->q))) {
1258 sch->q.qlen--;
1259 if (!cl->q->q.qlen)
1260 cbq_deactivate_class(cl);
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 sch->handle)))
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,
1679 cl->classid)) == NULL)
1680 return -ENOBUFS;
1681 } else {
1682 #ifdef CONFIG_NET_CLS_POLICE
1683 if (cl->police == TC_POLICE_RECLASSIFY)
1684 new->reshape_fail = cbq_reshape_fail;
1685 #endif
1686 }
1687 sch_tree_lock(sch);
1688 *old = xchg(&cl->q, new);
1689 qdisc_tree_decrease_qlen(*old, (*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 void cbq_qlen_notify(struct Qdisc *sch, unsigned long arg)
1707 {
1708 struct cbq_class *cl = (struct cbq_class *)arg;
1709
1710 if (cl->q->q.qlen == 0)
1711 cbq_deactivate_class(cl);
1712 }
1713
1714 static unsigned long cbq_get(struct Qdisc *sch, u32 classid)
1715 {
1716 struct cbq_sched_data *q = qdisc_priv(sch);
1717 struct cbq_class *cl = cbq_class_lookup(q, classid);
1718
1719 if (cl) {
1720 cl->refcnt++;
1721 return (unsigned long)cl;
1722 }
1723 return 0;
1724 }
1725
1726 static void cbq_destroy_filters(struct cbq_class *cl)
1727 {
1728 struct tcf_proto *tp;
1729
1730 while ((tp = cl->filter_list) != NULL) {
1731 cl->filter_list = tp->next;
1732 tcf_destroy(tp);
1733 }
1734 }
1735
1736 static void cbq_destroy_class(struct Qdisc *sch, struct cbq_class *cl)
1737 {
1738 struct cbq_sched_data *q = qdisc_priv(sch);
1739
1740 BUG_TRAP(!cl->filters);
1741
1742 cbq_destroy_filters(cl);
1743 qdisc_destroy(cl->q);
1744 qdisc_put_rtab(cl->R_tab);
1745 #ifdef CONFIG_NET_ESTIMATOR
1746 gen_kill_estimator(&cl->bstats, &cl->rate_est);
1747 #endif
1748 if (cl != &q->link)
1749 kfree(cl);
1750 }
1751
1752 static void
1753 cbq_destroy(struct Qdisc* sch)
1754 {
1755 struct cbq_sched_data *q = qdisc_priv(sch);
1756 struct cbq_class *cl;
1757 unsigned h;
1758
1759 #ifdef CONFIG_NET_CLS_POLICE
1760 q->rx_class = NULL;
1761 #endif
1762 /*
1763 * Filters must be destroyed first because we don't destroy the
1764 * classes from root to leafs which means that filters can still
1765 * be bound to classes which have been destroyed already. --TGR '04
1766 */
1767 for (h = 0; h < 16; h++)
1768 for (cl = q->classes[h]; cl; cl = cl->next)
1769 cbq_destroy_filters(cl);
1770
1771 for (h = 0; h < 16; h++) {
1772 struct cbq_class *next;
1773
1774 for (cl = q->classes[h]; cl; cl = next) {
1775 next = cl->next;
1776 cbq_destroy_class(sch, cl);
1777 }
1778 }
1779 }
1780
1781 static void cbq_put(struct Qdisc *sch, unsigned long arg)
1782 {
1783 struct cbq_class *cl = (struct cbq_class*)arg;
1784
1785 if (--cl->refcnt == 0) {
1786 #ifdef CONFIG_NET_CLS_POLICE
1787 struct cbq_sched_data *q = qdisc_priv(sch);
1788
1789 spin_lock_bh(&sch->dev->queue_lock);
1790 if (q->rx_class == cl)
1791 q->rx_class = NULL;
1792 spin_unlock_bh(&sch->dev->queue_lock);
1793 #endif
1794
1795 cbq_destroy_class(sch, cl);
1796 }
1797 }
1798
1799 static int
1800 cbq_change_class(struct Qdisc *sch, u32 classid, u32 parentid, struct rtattr **tca,
1801 unsigned long *arg)
1802 {
1803 int err;
1804 struct cbq_sched_data *q = qdisc_priv(sch);
1805 struct cbq_class *cl = (struct cbq_class*)*arg;
1806 struct rtattr *opt = tca[TCA_OPTIONS-1];
1807 struct rtattr *tb[TCA_CBQ_MAX];
1808 struct cbq_class *parent;
1809 struct qdisc_rate_table *rtab = NULL;
1810
1811 if (opt==NULL || rtattr_parse_nested(tb, TCA_CBQ_MAX, opt))
1812 return -EINVAL;
1813
1814 if (tb[TCA_CBQ_OVL_STRATEGY-1] &&
1815 RTA_PAYLOAD(tb[TCA_CBQ_OVL_STRATEGY-1]) < sizeof(struct tc_cbq_ovl))
1816 return -EINVAL;
1817
1818 if (tb[TCA_CBQ_FOPT-1] &&
1819 RTA_PAYLOAD(tb[TCA_CBQ_FOPT-1]) < sizeof(struct tc_cbq_fopt))
1820 return -EINVAL;
1821
1822 if (tb[TCA_CBQ_RATE-1] &&
1823 RTA_PAYLOAD(tb[TCA_CBQ_RATE-1]) < sizeof(struct tc_ratespec))
1824 return -EINVAL;
1825
1826 if (tb[TCA_CBQ_LSSOPT-1] &&
1827 RTA_PAYLOAD(tb[TCA_CBQ_LSSOPT-1]) < sizeof(struct tc_cbq_lssopt))
1828 return -EINVAL;
1829
1830 if (tb[TCA_CBQ_WRROPT-1] &&
1831 RTA_PAYLOAD(tb[TCA_CBQ_WRROPT-1]) < sizeof(struct tc_cbq_wrropt))
1832 return -EINVAL;
1833
1834 #ifdef CONFIG_NET_CLS_POLICE
1835 if (tb[TCA_CBQ_POLICE-1] &&
1836 RTA_PAYLOAD(tb[TCA_CBQ_POLICE-1]) < sizeof(struct tc_cbq_police))
1837 return -EINVAL;
1838 #endif
1839
1840 if (cl) {
1841 /* Check parent */
1842 if (parentid) {
1843 if (cl->tparent && cl->tparent->classid != parentid)
1844 return -EINVAL;
1845 if (!cl->tparent && parentid != TC_H_ROOT)
1846 return -EINVAL;
1847 }
1848
1849 if (tb[TCA_CBQ_RATE-1]) {
1850 rtab = qdisc_get_rtab(RTA_DATA(tb[TCA_CBQ_RATE-1]), tb[TCA_CBQ_RTAB-1]);
1851 if (rtab == NULL)
1852 return -EINVAL;
1853 }
1854
1855 /* Change class parameters */
1856 sch_tree_lock(sch);
1857
1858 if (cl->next_alive != NULL)
1859 cbq_deactivate_class(cl);
1860
1861 if (rtab) {
1862 rtab = xchg(&cl->R_tab, rtab);
1863 qdisc_put_rtab(rtab);
1864 }
1865
1866 if (tb[TCA_CBQ_LSSOPT-1])
1867 cbq_set_lss(cl, RTA_DATA(tb[TCA_CBQ_LSSOPT-1]));
1868
1869 if (tb[TCA_CBQ_WRROPT-1]) {
1870 cbq_rmprio(q, cl);
1871 cbq_set_wrr(cl, RTA_DATA(tb[TCA_CBQ_WRROPT-1]));
1872 }
1873
1874 if (tb[TCA_CBQ_OVL_STRATEGY-1])
1875 cbq_set_overlimit(cl, RTA_DATA(tb[TCA_CBQ_OVL_STRATEGY-1]));
1876
1877 #ifdef CONFIG_NET_CLS_POLICE
1878 if (tb[TCA_CBQ_POLICE-1])
1879 cbq_set_police(cl, RTA_DATA(tb[TCA_CBQ_POLICE-1]));
1880 #endif
1881
1882 if (tb[TCA_CBQ_FOPT-1])
1883 cbq_set_fopt(cl, RTA_DATA(tb[TCA_CBQ_FOPT-1]));
1884
1885 if (cl->q->q.qlen)
1886 cbq_activate_class(cl);
1887
1888 sch_tree_unlock(sch);
1889
1890 #ifdef CONFIG_NET_ESTIMATOR
1891 if (tca[TCA_RATE-1])
1892 gen_replace_estimator(&cl->bstats, &cl->rate_est,
1893 cl->stats_lock, tca[TCA_RATE-1]);
1894 #endif
1895 return 0;
1896 }
1897
1898 if (parentid == TC_H_ROOT)
1899 return -EINVAL;
1900
1901 if (tb[TCA_CBQ_WRROPT-1] == NULL || tb[TCA_CBQ_RATE-1] == NULL ||
1902 tb[TCA_CBQ_LSSOPT-1] == NULL)
1903 return -EINVAL;
1904
1905 rtab = qdisc_get_rtab(RTA_DATA(tb[TCA_CBQ_RATE-1]), tb[TCA_CBQ_RTAB-1]);
1906 if (rtab == NULL)
1907 return -EINVAL;
1908
1909 if (classid) {
1910 err = -EINVAL;
1911 if (TC_H_MAJ(classid^sch->handle) || cbq_class_lookup(q, classid))
1912 goto failure;
1913 } else {
1914 int i;
1915 classid = TC_H_MAKE(sch->handle,0x8000);
1916
1917 for (i=0; i<0x8000; i++) {
1918 if (++q->hgenerator >= 0x8000)
1919 q->hgenerator = 1;
1920 if (cbq_class_lookup(q, classid|q->hgenerator) == NULL)
1921 break;
1922 }
1923 err = -ENOSR;
1924 if (i >= 0x8000)
1925 goto failure;
1926 classid = classid|q->hgenerator;
1927 }
1928
1929 parent = &q->link;
1930 if (parentid) {
1931 parent = cbq_class_lookup(q, parentid);
1932 err = -EINVAL;
1933 if (parent == NULL)
1934 goto failure;
1935 }
1936
1937 err = -ENOBUFS;
1938 cl = kzalloc(sizeof(*cl), GFP_KERNEL);
1939 if (cl == NULL)
1940 goto failure;
1941 cl->R_tab = rtab;
1942 rtab = NULL;
1943 cl->refcnt = 1;
1944 if (!(cl->q = qdisc_create_dflt(sch->dev, &pfifo_qdisc_ops, classid)))
1945 cl->q = &noop_qdisc;
1946 cl->classid = classid;
1947 cl->tparent = parent;
1948 cl->qdisc = sch;
1949 cl->allot = parent->allot;
1950 cl->quantum = cl->allot;
1951 cl->weight = cl->R_tab->rate.rate;
1952 cl->stats_lock = &sch->dev->queue_lock;
1953
1954 sch_tree_lock(sch);
1955 cbq_link_class(cl);
1956 cl->borrow = cl->tparent;
1957 if (cl->tparent != &q->link)
1958 cl->share = cl->tparent;
1959 cbq_adjust_levels(parent);
1960 cl->minidle = -0x7FFFFFFF;
1961 cbq_set_lss(cl, RTA_DATA(tb[TCA_CBQ_LSSOPT-1]));
1962 cbq_set_wrr(cl, RTA_DATA(tb[TCA_CBQ_WRROPT-1]));
1963 if (cl->ewma_log==0)
1964 cl->ewma_log = q->link.ewma_log;
1965 if (cl->maxidle==0)
1966 cl->maxidle = q->link.maxidle;
1967 if (cl->avpkt==0)
1968 cl->avpkt = q->link.avpkt;
1969 cl->overlimit = cbq_ovl_classic;
1970 if (tb[TCA_CBQ_OVL_STRATEGY-1])
1971 cbq_set_overlimit(cl, RTA_DATA(tb[TCA_CBQ_OVL_STRATEGY-1]));
1972 #ifdef CONFIG_NET_CLS_POLICE
1973 if (tb[TCA_CBQ_POLICE-1])
1974 cbq_set_police(cl, RTA_DATA(tb[TCA_CBQ_POLICE-1]));
1975 #endif
1976 if (tb[TCA_CBQ_FOPT-1])
1977 cbq_set_fopt(cl, RTA_DATA(tb[TCA_CBQ_FOPT-1]));
1978 sch_tree_unlock(sch);
1979
1980 #ifdef CONFIG_NET_ESTIMATOR
1981 if (tca[TCA_RATE-1])
1982 gen_new_estimator(&cl->bstats, &cl->rate_est,
1983 cl->stats_lock, tca[TCA_RATE-1]);
1984 #endif
1985
1986 *arg = (unsigned long)cl;
1987 return 0;
1988
1989 failure:
1990 qdisc_put_rtab(rtab);
1991 return err;
1992 }
1993
1994 static int cbq_delete(struct Qdisc *sch, unsigned long arg)
1995 {
1996 struct cbq_sched_data *q = qdisc_priv(sch);
1997 struct cbq_class *cl = (struct cbq_class*)arg;
1998 unsigned int qlen;
1999
2000 if (cl->filters || cl->children || cl == &q->link)
2001 return -EBUSY;
2002
2003 sch_tree_lock(sch);
2004
2005 qlen = cl->q->q.qlen;
2006 qdisc_reset(cl->q);
2007 qdisc_tree_decrease_qlen(cl->q, qlen);
2008
2009 if (cl->next_alive)
2010 cbq_deactivate_class(cl);
2011
2012 if (q->tx_borrowed == cl)
2013 q->tx_borrowed = q->tx_class;
2014 if (q->tx_class == cl) {
2015 q->tx_class = NULL;
2016 q->tx_borrowed = NULL;
2017 }
2018 #ifdef CONFIG_NET_CLS_POLICE
2019 if (q->rx_class == cl)
2020 q->rx_class = NULL;
2021 #endif
2022
2023 cbq_unlink_class(cl);
2024 cbq_adjust_levels(cl->tparent);
2025 cl->defmap = 0;
2026 cbq_sync_defmap(cl);
2027
2028 cbq_rmprio(q, cl);
2029 sch_tree_unlock(sch);
2030
2031 if (--cl->refcnt == 0)
2032 cbq_destroy_class(sch, cl);
2033
2034 return 0;
2035 }
2036
2037 static struct tcf_proto **cbq_find_tcf(struct Qdisc *sch, unsigned long arg)
2038 {
2039 struct cbq_sched_data *q = qdisc_priv(sch);
2040 struct cbq_class *cl = (struct cbq_class *)arg;
2041
2042 if (cl == NULL)
2043 cl = &q->link;
2044
2045 return &cl->filter_list;
2046 }
2047
2048 static unsigned long cbq_bind_filter(struct Qdisc *sch, unsigned long parent,
2049 u32 classid)
2050 {
2051 struct cbq_sched_data *q = qdisc_priv(sch);
2052 struct cbq_class *p = (struct cbq_class*)parent;
2053 struct cbq_class *cl = cbq_class_lookup(q, classid);
2054
2055 if (cl) {
2056 if (p && p->level <= cl->level)
2057 return 0;
2058 cl->filters++;
2059 return (unsigned long)cl;
2060 }
2061 return 0;
2062 }
2063
2064 static void cbq_unbind_filter(struct Qdisc *sch, unsigned long arg)
2065 {
2066 struct cbq_class *cl = (struct cbq_class*)arg;
2067
2068 cl->filters--;
2069 }
2070
2071 static void cbq_walk(struct Qdisc *sch, struct qdisc_walker *arg)
2072 {
2073 struct cbq_sched_data *q = qdisc_priv(sch);
2074 unsigned h;
2075
2076 if (arg->stop)
2077 return;
2078
2079 for (h = 0; h < 16; h++) {
2080 struct cbq_class *cl;
2081
2082 for (cl = q->classes[h]; cl; cl = cl->next) {
2083 if (arg->count < arg->skip) {
2084 arg->count++;
2085 continue;
2086 }
2087 if (arg->fn(sch, (unsigned long)cl, arg) < 0) {
2088 arg->stop = 1;
2089 return;
2090 }
2091 arg->count++;
2092 }
2093 }
2094 }
2095
2096 static struct Qdisc_class_ops cbq_class_ops = {
2097 .graft = cbq_graft,
2098 .leaf = cbq_leaf,
2099 .qlen_notify = cbq_qlen_notify,
2100 .get = cbq_get,
2101 .put = cbq_put,
2102 .change = cbq_change_class,
2103 .delete = cbq_delete,
2104 .walk = cbq_walk,
2105 .tcf_chain = cbq_find_tcf,
2106 .bind_tcf = cbq_bind_filter,
2107 .unbind_tcf = cbq_unbind_filter,
2108 .dump = cbq_dump_class,
2109 .dump_stats = cbq_dump_class_stats,
2110 };
2111
2112 static struct Qdisc_ops cbq_qdisc_ops = {
2113 .next = NULL,
2114 .cl_ops = &cbq_class_ops,
2115 .id = "cbq",
2116 .priv_size = sizeof(struct cbq_sched_data),
2117 .enqueue = cbq_enqueue,
2118 .dequeue = cbq_dequeue,
2119 .requeue = cbq_requeue,
2120 .drop = cbq_drop,
2121 .init = cbq_init,
2122 .reset = cbq_reset,
2123 .destroy = cbq_destroy,
2124 .change = NULL,
2125 .dump = cbq_dump,
2126 .dump_stats = cbq_dump_stats,
2127 .owner = THIS_MODULE,
2128 };
2129
2130 static int __init cbq_module_init(void)
2131 {
2132 return register_qdisc(&cbq_qdisc_ops);
2133 }
2134 static void __exit cbq_module_exit(void)
2135 {
2136 unregister_qdisc(&cbq_qdisc_ops);
2137 }
2138 module_init(cbq_module_init)
2139 module_exit(cbq_module_exit)
2140 MODULE_LICENSE("GPL");
linux v2.6.22.y-op