2 * net/sched/sch_cbq.c Class-Based Queueing discipline.
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.
9 * Authors: Alexey Kuznetsov, <kuznet@ms2.inr.ac.ru>
13 #include <linux/module.h>
14 #include <linux/slab.h>
15 #include <linux/types.h>
16 #include <linux/kernel.h>
17 #include <linux/string.h>
18 #include <linux/errno.h>
19 #include <linux/skbuff.h>
20 #include <net/netlink.h>
21 #include <net/pkt_sched.h>
22 #include <net/pkt_cls.h>
25 /* Class-Based Queueing (CBQ) algorithm.
26 =======================================
28 Sources: [1] Sally Floyd and Van Jacobson, "Link-sharing and Resource
29 Management Models for Packet Networks",
30 IEEE/ACM Transactions on Networking, Vol.3, No.4, 1995
32 [2] Sally Floyd, "Notes on CBQ and Guaranteed Service", 1995
34 [3] Sally Floyd, "Notes on Class-Based Queueing: Setting
37 [4] Sally Floyd and Michael Speer, "Experimental Results
38 for Class-Based Queueing", 1998, not published.
40 -----------------------------------------------------------------------
42 Algorithm skeleton was taken from NS simulator cbq.cc.
43 If someone wants to check this code against the LBL version,
44 he should take into account that ONLY the skeleton was borrowed,
45 the implementation is different. Particularly:
47 --- The WRR algorithm is different. Our version looks more
48 reasonable (I hope) and works when quanta are allowed to be
49 less than MTU, which is always the case when real time classes
50 have small rates. Note, that the statement of [3] is
51 incomplete, delay may actually be estimated even if class
52 per-round allotment is less than MTU. Namely, if per-round
53 allotment is W*r_i, and r_1+...+r_k = r < 1
55 delay_i <= ([MTU/(W*r_i)]*W*r + W*r + k*MTU)/B
57 In the worst case we have IntServ estimate with D = W*r+k*MTU
58 and C = MTU*r. The proof (if correct at all) is trivial.
61 --- It seems that cbq-2.0 is not very accurate. At least, I cannot
62 interpret some places, which look like wrong translations
63 from NS. Anyone is advised to find these differences
64 and explain to me, why I am wrong 8).
66 --- Linux has no EOI event, so that we cannot estimate true class
67 idle time. Workaround is to consider the next dequeue event
68 as sign that previous packet is finished. This is wrong because of
69 internal device queueing, but on a permanently loaded link it is true.
70 Moreover, combined with clock integrator, this scheme looks
71 very close to an ideal solution. */
73 struct cbq_sched_data
;
77 struct Qdisc_class_common common
;
78 struct cbq_class
*next_alive
; /* next class with backlog in this priority band */
81 unsigned char priority
; /* class priority */
82 unsigned char priority2
; /* priority to be used after overlimit */
83 unsigned char ewma_log
; /* time constant for idle time calculation */
87 /* Link-sharing scheduler parameters */
88 long maxidle
; /* Class parameters: see below. */
92 struct qdisc_rate_table
*R_tab
;
94 /* General scheduler (WRR) parameters */
96 long quantum
; /* Allotment per WRR round */
97 long weight
; /* Relative allotment: see below */
99 struct Qdisc
*qdisc
; /* Ptr to CBQ discipline */
100 struct cbq_class
*split
; /* Ptr to split node */
101 struct cbq_class
*share
; /* Ptr to LS parent in the class tree */
102 struct cbq_class
*tparent
; /* Ptr to tree parent in the class tree */
103 struct cbq_class
*borrow
; /* NULL if class is bandwidth limited;
105 struct cbq_class
*sibling
; /* Sibling chain */
106 struct cbq_class
*children
; /* Pointer to children chain */
108 struct Qdisc
*q
; /* Elementary queueing discipline */
112 unsigned char cpriority
; /* Effective priority */
113 unsigned char delayed
;
114 unsigned char level
; /* level of the class in hierarchy:
115 0 for leaf classes, and maximal
116 level of children + 1 for nodes.
119 psched_time_t last
; /* Last end of service */
120 psched_time_t undertime
;
122 long deficit
; /* Saved deficit for WRR */
123 psched_time_t penalized
;
124 struct gnet_stats_basic_packed bstats
;
125 struct gnet_stats_queue qstats
;
126 struct net_rate_estimator __rcu
*rate_est
;
127 struct tc_cbq_xstats xstats
;
129 struct tcf_proto __rcu
*filter_list
;
134 struct cbq_class
*defaults
[TC_PRIO_MAX
+ 1];
137 struct cbq_sched_data
{
138 struct Qdisc_class_hash clhash
; /* Hash table of all classes */
139 int nclasses
[TC_CBQ_MAXPRIO
+ 1];
140 unsigned int quanta
[TC_CBQ_MAXPRIO
+ 1];
142 struct cbq_class link
;
144 unsigned int activemask
;
145 struct cbq_class
*active
[TC_CBQ_MAXPRIO
+ 1]; /* List of all classes
148 #ifdef CONFIG_NET_CLS_ACT
149 struct cbq_class
*rx_class
;
151 struct cbq_class
*tx_class
;
152 struct cbq_class
*tx_borrowed
;
154 psched_time_t now
; /* Cached timestamp */
157 struct hrtimer delay_timer
;
158 struct qdisc_watchdog watchdog
; /* Watchdog timer,
162 psched_tdiff_t wd_expires
;
168 #define L2T(cl, len) qdisc_l2t((cl)->R_tab, len)
170 static inline struct cbq_class
*
171 cbq_class_lookup(struct cbq_sched_data
*q
, u32 classid
)
173 struct Qdisc_class_common
*clc
;
175 clc
= qdisc_class_find(&q
->clhash
, classid
);
178 return container_of(clc
, struct cbq_class
, common
);
181 #ifdef CONFIG_NET_CLS_ACT
183 static struct cbq_class
*
184 cbq_reclassify(struct sk_buff
*skb
, struct cbq_class
*this)
186 struct cbq_class
*cl
;
188 for (cl
= this->tparent
; cl
; cl
= cl
->tparent
) {
189 struct cbq_class
*new = cl
->defaults
[TC_PRIO_BESTEFFORT
];
191 if (new != NULL
&& new != this)
199 /* Classify packet. The procedure is pretty complicated, but
200 * it allows us to combine link sharing and priority scheduling
203 * Namely, you can put link sharing rules (f.e. route based) at root of CBQ,
204 * so that it resolves to split nodes. Then packets are classified
205 * by logical priority, or a more specific classifier may be attached
209 static struct cbq_class
*
210 cbq_classify(struct sk_buff
*skb
, struct Qdisc
*sch
, int *qerr
)
212 struct cbq_sched_data
*q
= qdisc_priv(sch
);
213 struct cbq_class
*head
= &q
->link
;
214 struct cbq_class
**defmap
;
215 struct cbq_class
*cl
= NULL
;
216 u32 prio
= skb
->priority
;
217 struct tcf_proto
*fl
;
218 struct tcf_result res
;
221 * Step 1. If skb->priority points to one of our classes, use it.
223 if (TC_H_MAJ(prio
^ sch
->handle
) == 0 &&
224 (cl
= cbq_class_lookup(q
, prio
)) != NULL
)
227 *qerr
= NET_XMIT_SUCCESS
| __NET_XMIT_BYPASS
;
230 defmap
= head
->defaults
;
232 fl
= rcu_dereference_bh(head
->filter_list
);
234 * Step 2+n. Apply classifier.
236 result
= tc_classify(skb
, fl
, &res
, true);
237 if (!fl
|| result
< 0)
240 cl
= (void *)res
.class;
242 if (TC_H_MAJ(res
.classid
))
243 cl
= cbq_class_lookup(q
, res
.classid
);
244 else if ((cl
= defmap
[res
.classid
& TC_PRIO_MAX
]) == NULL
)
245 cl
= defmap
[TC_PRIO_BESTEFFORT
];
250 if (cl
->level
>= head
->level
)
252 #ifdef CONFIG_NET_CLS_ACT
256 *qerr
= NET_XMIT_SUCCESS
| __NET_XMIT_STOLEN
;
259 case TC_ACT_RECLASSIFY
:
260 return cbq_reclassify(skb
, cl
);
267 * Step 3+n. If classifier selected a link sharing class,
268 * apply agency specific classifier.
269 * Repeat this procdure until we hit a leaf node.
278 * Step 4. No success...
280 if (TC_H_MAJ(prio
) == 0 &&
281 !(cl
= head
->defaults
[prio
& TC_PRIO_MAX
]) &&
282 !(cl
= head
->defaults
[TC_PRIO_BESTEFFORT
]))
289 * A packet has just been enqueued on the empty class.
290 * cbq_activate_class adds it to the tail of active class list
291 * of its priority band.
294 static inline void cbq_activate_class(struct cbq_class
*cl
)
296 struct cbq_sched_data
*q
= qdisc_priv(cl
->qdisc
);
297 int prio
= cl
->cpriority
;
298 struct cbq_class
*cl_tail
;
300 cl_tail
= q
->active
[prio
];
301 q
->active
[prio
] = cl
;
303 if (cl_tail
!= NULL
) {
304 cl
->next_alive
= cl_tail
->next_alive
;
305 cl_tail
->next_alive
= cl
;
308 q
->activemask
|= (1<<prio
);
313 * Unlink class from active chain.
314 * Note that this same procedure is done directly in cbq_dequeue*
315 * during round-robin procedure.
318 static void cbq_deactivate_class(struct cbq_class
*this)
320 struct cbq_sched_data
*q
= qdisc_priv(this->qdisc
);
321 int prio
= this->cpriority
;
322 struct cbq_class
*cl
;
323 struct cbq_class
*cl_prev
= q
->active
[prio
];
326 cl
= cl_prev
->next_alive
;
328 cl_prev
->next_alive
= cl
->next_alive
;
329 cl
->next_alive
= NULL
;
331 if (cl
== q
->active
[prio
]) {
332 q
->active
[prio
] = cl_prev
;
333 if (cl
== q
->active
[prio
]) {
334 q
->active
[prio
] = NULL
;
335 q
->activemask
&= ~(1<<prio
);
341 } while ((cl_prev
= cl
) != q
->active
[prio
]);
345 cbq_mark_toplevel(struct cbq_sched_data
*q
, struct cbq_class
*cl
)
347 int toplevel
= q
->toplevel
;
349 if (toplevel
> cl
->level
) {
350 psched_time_t now
= psched_get_time();
353 if (cl
->undertime
< now
) {
354 q
->toplevel
= cl
->level
;
357 } while ((cl
= cl
->borrow
) != NULL
&& toplevel
> cl
->level
);
362 cbq_enqueue(struct sk_buff
*skb
, struct Qdisc
*sch
,
363 struct sk_buff
**to_free
)
365 struct cbq_sched_data
*q
= qdisc_priv(sch
);
366 int uninitialized_var(ret
);
367 struct cbq_class
*cl
= cbq_classify(skb
, sch
, &ret
);
369 #ifdef CONFIG_NET_CLS_ACT
373 if (ret
& __NET_XMIT_BYPASS
)
374 qdisc_qstats_drop(sch
);
375 __qdisc_drop(skb
, to_free
);
379 ret
= qdisc_enqueue(skb
, cl
->q
, to_free
);
380 if (ret
== NET_XMIT_SUCCESS
) {
382 cbq_mark_toplevel(q
, cl
);
384 cbq_activate_class(cl
);
388 if (net_xmit_drop_count(ret
)) {
389 qdisc_qstats_drop(sch
);
390 cbq_mark_toplevel(q
, cl
);
396 /* Overlimit action: penalize leaf class by adding offtime */
397 static void cbq_overlimit(struct cbq_class
*cl
)
399 struct cbq_sched_data
*q
= qdisc_priv(cl
->qdisc
);
400 psched_tdiff_t delay
= cl
->undertime
- q
->now
;
403 delay
+= cl
->offtime
;
406 * Class goes to sleep, so that it will have no
407 * chance to work avgidle. Let's forgive it 8)
409 * BTW cbq-2.0 has a crap in this
410 * place, apparently they forgot to shift it by cl->ewma_log.
413 delay
-= (-cl
->avgidle
) - ((-cl
->avgidle
) >> cl
->ewma_log
);
414 if (cl
->avgidle
< cl
->minidle
)
415 cl
->avgidle
= cl
->minidle
;
418 cl
->undertime
= q
->now
+ delay
;
420 cl
->xstats
.overactions
++;
423 if (q
->wd_expires
== 0 || q
->wd_expires
> delay
)
424 q
->wd_expires
= delay
;
426 /* Dirty work! We must schedule wakeups based on
427 * real available rate, rather than leaf rate,
428 * which may be tiny (even zero).
430 if (q
->toplevel
== TC_CBQ_MAXLEVEL
) {
432 psched_tdiff_t base_delay
= q
->wd_expires
;
434 for (b
= cl
->borrow
; b
; b
= b
->borrow
) {
435 delay
= b
->undertime
- q
->now
;
436 if (delay
< base_delay
) {
443 q
->wd_expires
= base_delay
;
447 static psched_tdiff_t
cbq_undelay_prio(struct cbq_sched_data
*q
, int prio
,
450 struct cbq_class
*cl
;
451 struct cbq_class
*cl_prev
= q
->active
[prio
];
452 psched_time_t sched
= now
;
458 cl
= cl_prev
->next_alive
;
459 if (now
- cl
->penalized
> 0) {
460 cl_prev
->next_alive
= cl
->next_alive
;
461 cl
->next_alive
= NULL
;
462 cl
->cpriority
= cl
->priority
;
464 cbq_activate_class(cl
);
466 if (cl
== q
->active
[prio
]) {
467 q
->active
[prio
] = cl_prev
;
468 if (cl
== q
->active
[prio
]) {
469 q
->active
[prio
] = NULL
;
474 cl
= cl_prev
->next_alive
;
475 } else if (sched
- cl
->penalized
> 0)
476 sched
= cl
->penalized
;
477 } while ((cl_prev
= cl
) != q
->active
[prio
]);
482 static enum hrtimer_restart
cbq_undelay(struct hrtimer
*timer
)
484 struct cbq_sched_data
*q
= container_of(timer
, struct cbq_sched_data
,
486 struct Qdisc
*sch
= q
->watchdog
.qdisc
;
488 psched_tdiff_t delay
= 0;
491 now
= psched_get_time();
497 int prio
= ffz(~pmask
);
502 tmp
= cbq_undelay_prio(q
, prio
, now
);
505 if (tmp
< delay
|| delay
== 0)
514 time
= ktime_add_ns(time
, PSCHED_TICKS2NS(now
+ delay
));
515 hrtimer_start(&q
->delay_timer
, time
, HRTIMER_MODE_ABS_PINNED
);
518 __netif_schedule(qdisc_root(sch
));
519 return HRTIMER_NORESTART
;
523 * It is mission critical procedure.
525 * We "regenerate" toplevel cutoff, if transmitting class
526 * has backlog and it is not regulated. It is not part of
527 * original CBQ description, but looks more reasonable.
528 * Probably, it is wrong. This question needs further investigation.
532 cbq_update_toplevel(struct cbq_sched_data
*q
, struct cbq_class
*cl
,
533 struct cbq_class
*borrowed
)
535 if (cl
&& q
->toplevel
>= borrowed
->level
) {
536 if (cl
->q
->q
.qlen
> 1) {
538 if (borrowed
->undertime
== PSCHED_PASTPERFECT
) {
539 q
->toplevel
= borrowed
->level
;
542 } while ((borrowed
= borrowed
->borrow
) != NULL
);
545 /* It is not necessary now. Uncommenting it
546 will save CPU cycles, but decrease fairness.
548 q
->toplevel
= TC_CBQ_MAXLEVEL
;
554 cbq_update(struct cbq_sched_data
*q
)
556 struct cbq_class
*this = q
->tx_class
;
557 struct cbq_class
*cl
= this;
562 /* Time integrator. We calculate EOS time
563 * by adding expected packet transmission time.
565 now
= q
->now
+ L2T(&q
->link
, len
);
567 for ( ; cl
; cl
= cl
->share
) {
568 long avgidle
= cl
->avgidle
;
571 cl
->bstats
.packets
++;
572 cl
->bstats
.bytes
+= len
;
575 * (now - last) is total time between packet right edges.
576 * (last_pktlen/rate) is "virtual" busy time, so that
578 * idle = (now - last) - last_pktlen/rate
581 idle
= now
- cl
->last
;
582 if ((unsigned long)idle
> 128*1024*1024) {
583 avgidle
= cl
->maxidle
;
585 idle
-= L2T(cl
, len
);
587 /* true_avgidle := (1-W)*true_avgidle + W*idle,
588 * where W=2^{-ewma_log}. But cl->avgidle is scaled:
589 * cl->avgidle == true_avgidle/W,
592 avgidle
+= idle
- (avgidle
>>cl
->ewma_log
);
596 /* Overlimit or at-limit */
598 if (avgidle
< cl
->minidle
)
599 avgidle
= cl
->minidle
;
601 cl
->avgidle
= avgidle
;
603 /* Calculate expected time, when this class
604 * will be allowed to send.
605 * It will occur, when:
606 * (1-W)*true_avgidle + W*delay = 0, i.e.
607 * idle = (1/W - 1)*(-true_avgidle)
609 * idle = (1 - W)*(-cl->avgidle);
611 idle
= (-avgidle
) - ((-avgidle
) >> cl
->ewma_log
);
615 * To maintain the rate allocated to the class,
616 * we add to undertime virtual clock,
617 * necessary to complete transmitted packet.
618 * (len/phys_bandwidth has been already passed
619 * to the moment of cbq_update)
622 idle
-= L2T(&q
->link
, len
);
623 idle
+= L2T(cl
, len
);
625 cl
->undertime
= now
+ idle
;
629 cl
->undertime
= PSCHED_PASTPERFECT
;
630 if (avgidle
> cl
->maxidle
)
631 cl
->avgidle
= cl
->maxidle
;
633 cl
->avgidle
= avgidle
;
635 if ((s64
)(now
- cl
->last
) > 0)
639 cbq_update_toplevel(q
, this, q
->tx_borrowed
);
642 static inline struct cbq_class
*
643 cbq_under_limit(struct cbq_class
*cl
)
645 struct cbq_sched_data
*q
= qdisc_priv(cl
->qdisc
);
646 struct cbq_class
*this_cl
= cl
;
648 if (cl
->tparent
== NULL
)
651 if (cl
->undertime
== PSCHED_PASTPERFECT
|| q
->now
>= cl
->undertime
) {
657 /* It is very suspicious place. Now overlimit
658 * action is generated for not bounded classes
659 * only if link is completely congested.
660 * Though it is in agree with ancestor-only paradigm,
661 * it looks very stupid. Particularly,
662 * it means that this chunk of code will either
663 * never be called or result in strong amplification
664 * of burstiness. Dangerous, silly, and, however,
665 * no another solution exists.
669 this_cl
->qstats
.overlimits
++;
670 cbq_overlimit(this_cl
);
673 if (cl
->level
> q
->toplevel
)
675 } while (cl
->undertime
!= PSCHED_PASTPERFECT
&& q
->now
< cl
->undertime
);
681 static inline struct sk_buff
*
682 cbq_dequeue_prio(struct Qdisc
*sch
, int prio
)
684 struct cbq_sched_data
*q
= qdisc_priv(sch
);
685 struct cbq_class
*cl_tail
, *cl_prev
, *cl
;
689 cl_tail
= cl_prev
= q
->active
[prio
];
690 cl
= cl_prev
->next_alive
;
697 struct cbq_class
*borrow
= cl
;
700 (borrow
= cbq_under_limit(cl
)) == NULL
)
703 if (cl
->deficit
<= 0) {
704 /* Class exhausted its allotment per
705 * this round. Switch to the next one.
708 cl
->deficit
+= cl
->quantum
;
712 skb
= cl
->q
->dequeue(cl
->q
);
714 /* Class did not give us any skb :-(
715 * It could occur even if cl->q->q.qlen != 0
716 * f.e. if cl->q == "tbf"
721 cl
->deficit
-= qdisc_pkt_len(skb
);
723 q
->tx_borrowed
= borrow
;
725 #ifndef CBQ_XSTATS_BORROWS_BYTES
726 borrow
->xstats
.borrows
++;
727 cl
->xstats
.borrows
++;
729 borrow
->xstats
.borrows
+= qdisc_pkt_len(skb
);
730 cl
->xstats
.borrows
+= qdisc_pkt_len(skb
);
733 q
->tx_len
= qdisc_pkt_len(skb
);
735 if (cl
->deficit
<= 0) {
736 q
->active
[prio
] = cl
;
738 cl
->deficit
+= cl
->quantum
;
743 if (cl
->q
->q
.qlen
== 0 || prio
!= cl
->cpriority
) {
744 /* Class is empty or penalized.
745 * Unlink it from active chain.
747 cl_prev
->next_alive
= cl
->next_alive
;
748 cl
->next_alive
= NULL
;
750 /* Did cl_tail point to it? */
755 /* Was it the last class in this band? */
758 q
->active
[prio
] = NULL
;
759 q
->activemask
&= ~(1<<prio
);
761 cbq_activate_class(cl
);
765 q
->active
[prio
] = cl_tail
;
768 cbq_activate_class(cl
);
776 } while (cl_prev
!= cl_tail
);
779 q
->active
[prio
] = cl_prev
;
784 static inline struct sk_buff
*
785 cbq_dequeue_1(struct Qdisc
*sch
)
787 struct cbq_sched_data
*q
= qdisc_priv(sch
);
789 unsigned int activemask
;
791 activemask
= q
->activemask
& 0xFF;
793 int prio
= ffz(~activemask
);
794 activemask
&= ~(1<<prio
);
795 skb
= cbq_dequeue_prio(sch
, prio
);
802 static struct sk_buff
*
803 cbq_dequeue(struct Qdisc
*sch
)
806 struct cbq_sched_data
*q
= qdisc_priv(sch
);
809 now
= psched_get_time();
819 skb
= cbq_dequeue_1(sch
);
821 qdisc_bstats_update(sch
, skb
);
826 /* All the classes are overlimit.
828 * It is possible, if:
830 * 1. Scheduler is empty.
831 * 2. Toplevel cutoff inhibited borrowing.
832 * 3. Root class is overlimit.
834 * Reset 2d and 3d conditions and retry.
836 * Note, that NS and cbq-2.0 are buggy, peeking
837 * an arbitrary class is appropriate for ancestor-only
838 * sharing, but not for toplevel algorithm.
840 * Our version is better, but slower, because it requires
841 * two passes, but it is unavoidable with top-level sharing.
844 if (q
->toplevel
== TC_CBQ_MAXLEVEL
&&
845 q
->link
.undertime
== PSCHED_PASTPERFECT
)
848 q
->toplevel
= TC_CBQ_MAXLEVEL
;
849 q
->link
.undertime
= PSCHED_PASTPERFECT
;
852 /* No packets in scheduler or nobody wants to give them to us :-(
853 * Sigh... start watchdog timer in the last case.
857 qdisc_qstats_overlimit(sch
);
859 qdisc_watchdog_schedule(&q
->watchdog
,
860 now
+ q
->wd_expires
);
865 /* CBQ class maintanance routines */
867 static void cbq_adjust_levels(struct cbq_class
*this)
874 struct cbq_class
*cl
;
879 if (cl
->level
> level
)
881 } while ((cl
= cl
->sibling
) != this->children
);
883 this->level
= level
+ 1;
884 } while ((this = this->tparent
) != NULL
);
887 static void cbq_normalize_quanta(struct cbq_sched_data
*q
, int prio
)
889 struct cbq_class
*cl
;
892 if (q
->quanta
[prio
] == 0)
895 for (h
= 0; h
< q
->clhash
.hashsize
; h
++) {
896 hlist_for_each_entry(cl
, &q
->clhash
.hash
[h
], common
.hnode
) {
897 /* BUGGGG... Beware! This expression suffer of
898 * arithmetic overflows!
900 if (cl
->priority
== prio
) {
901 cl
->quantum
= (cl
->weight
*cl
->allot
*q
->nclasses
[prio
])/
904 if (cl
->quantum
<= 0 ||
905 cl
->quantum
> 32*qdisc_dev(cl
->qdisc
)->mtu
) {
906 pr_warn("CBQ: class %08x has bad quantum==%ld, repaired.\n",
907 cl
->common
.classid
, cl
->quantum
);
908 cl
->quantum
= qdisc_dev(cl
->qdisc
)->mtu
/2 + 1;
914 static void cbq_sync_defmap(struct cbq_class
*cl
)
916 struct cbq_sched_data
*q
= qdisc_priv(cl
->qdisc
);
917 struct cbq_class
*split
= cl
->split
;
924 for (i
= 0; i
<= TC_PRIO_MAX
; i
++) {
925 if (split
->defaults
[i
] == cl
&& !(cl
->defmap
& (1<<i
)))
926 split
->defaults
[i
] = NULL
;
929 for (i
= 0; i
<= TC_PRIO_MAX
; i
++) {
930 int level
= split
->level
;
932 if (split
->defaults
[i
])
935 for (h
= 0; h
< q
->clhash
.hashsize
; h
++) {
938 hlist_for_each_entry(c
, &q
->clhash
.hash
[h
],
940 if (c
->split
== split
&& c
->level
< level
&&
941 c
->defmap
& (1<<i
)) {
942 split
->defaults
[i
] = c
;
950 static void cbq_change_defmap(struct cbq_class
*cl
, u32 splitid
, u32 def
, u32 mask
)
952 struct cbq_class
*split
= NULL
;
958 splitid
= split
->common
.classid
;
961 if (split
== NULL
|| split
->common
.classid
!= splitid
) {
962 for (split
= cl
->tparent
; split
; split
= split
->tparent
)
963 if (split
->common
.classid
== splitid
)
970 if (cl
->split
!= split
) {
974 cl
->defmap
= def
& mask
;
976 cl
->defmap
= (cl
->defmap
& ~mask
) | (def
& mask
);
981 static void cbq_unlink_class(struct cbq_class
*this)
983 struct cbq_class
*cl
, **clp
;
984 struct cbq_sched_data
*q
= qdisc_priv(this->qdisc
);
986 qdisc_class_hash_remove(&q
->clhash
, &this->common
);
989 clp
= &this->sibling
;
997 } while ((cl
= *clp
) != this->sibling
);
999 if (this->tparent
->children
== this) {
1000 this->tparent
->children
= this->sibling
;
1001 if (this->sibling
== this)
1002 this->tparent
->children
= NULL
;
1005 WARN_ON(this->sibling
!= this);
1009 static void cbq_link_class(struct cbq_class
*this)
1011 struct cbq_sched_data
*q
= qdisc_priv(this->qdisc
);
1012 struct cbq_class
*parent
= this->tparent
;
1014 this->sibling
= this;
1015 qdisc_class_hash_insert(&q
->clhash
, &this->common
);
1020 if (parent
->children
== NULL
) {
1021 parent
->children
= this;
1023 this->sibling
= parent
->children
->sibling
;
1024 parent
->children
->sibling
= this;
1029 cbq_reset(struct Qdisc
*sch
)
1031 struct cbq_sched_data
*q
= qdisc_priv(sch
);
1032 struct cbq_class
*cl
;
1039 q
->tx_borrowed
= NULL
;
1040 qdisc_watchdog_cancel(&q
->watchdog
);
1041 hrtimer_cancel(&q
->delay_timer
);
1042 q
->toplevel
= TC_CBQ_MAXLEVEL
;
1043 q
->now
= psched_get_time();
1045 for (prio
= 0; prio
<= TC_CBQ_MAXPRIO
; prio
++)
1046 q
->active
[prio
] = NULL
;
1048 for (h
= 0; h
< q
->clhash
.hashsize
; h
++) {
1049 hlist_for_each_entry(cl
, &q
->clhash
.hash
[h
], common
.hnode
) {
1052 cl
->next_alive
= NULL
;
1053 cl
->undertime
= PSCHED_PASTPERFECT
;
1054 cl
->avgidle
= cl
->maxidle
;
1055 cl
->deficit
= cl
->quantum
;
1056 cl
->cpriority
= cl
->priority
;
1063 static int cbq_set_lss(struct cbq_class
*cl
, struct tc_cbq_lssopt
*lss
)
1065 if (lss
->change
& TCF_CBQ_LSS_FLAGS
) {
1066 cl
->share
= (lss
->flags
& TCF_CBQ_LSS_ISOLATED
) ? NULL
: cl
->tparent
;
1067 cl
->borrow
= (lss
->flags
& TCF_CBQ_LSS_BOUNDED
) ? NULL
: cl
->tparent
;
1069 if (lss
->change
& TCF_CBQ_LSS_EWMA
)
1070 cl
->ewma_log
= lss
->ewma_log
;
1071 if (lss
->change
& TCF_CBQ_LSS_AVPKT
)
1072 cl
->avpkt
= lss
->avpkt
;
1073 if (lss
->change
& TCF_CBQ_LSS_MINIDLE
)
1074 cl
->minidle
= -(long)lss
->minidle
;
1075 if (lss
->change
& TCF_CBQ_LSS_MAXIDLE
) {
1076 cl
->maxidle
= lss
->maxidle
;
1077 cl
->avgidle
= lss
->maxidle
;
1079 if (lss
->change
& TCF_CBQ_LSS_OFFTIME
)
1080 cl
->offtime
= lss
->offtime
;
1084 static void cbq_rmprio(struct cbq_sched_data
*q
, struct cbq_class
*cl
)
1086 q
->nclasses
[cl
->priority
]--;
1087 q
->quanta
[cl
->priority
] -= cl
->weight
;
1088 cbq_normalize_quanta(q
, cl
->priority
);
1091 static void cbq_addprio(struct cbq_sched_data
*q
, struct cbq_class
*cl
)
1093 q
->nclasses
[cl
->priority
]++;
1094 q
->quanta
[cl
->priority
] += cl
->weight
;
1095 cbq_normalize_quanta(q
, cl
->priority
);
1098 static int cbq_set_wrr(struct cbq_class
*cl
, struct tc_cbq_wrropt
*wrr
)
1100 struct cbq_sched_data
*q
= qdisc_priv(cl
->qdisc
);
1103 cl
->allot
= wrr
->allot
;
1105 cl
->weight
= wrr
->weight
;
1106 if (wrr
->priority
) {
1107 cl
->priority
= wrr
->priority
- 1;
1108 cl
->cpriority
= cl
->priority
;
1109 if (cl
->priority
>= cl
->priority2
)
1110 cl
->priority2
= TC_CBQ_MAXPRIO
- 1;
1117 static int cbq_set_fopt(struct cbq_class
*cl
, struct tc_cbq_fopt
*fopt
)
1119 cbq_change_defmap(cl
, fopt
->split
, fopt
->defmap
, fopt
->defchange
);
1123 static const struct nla_policy cbq_policy
[TCA_CBQ_MAX
+ 1] = {
1124 [TCA_CBQ_LSSOPT
] = { .len
= sizeof(struct tc_cbq_lssopt
) },
1125 [TCA_CBQ_WRROPT
] = { .len
= sizeof(struct tc_cbq_wrropt
) },
1126 [TCA_CBQ_FOPT
] = { .len
= sizeof(struct tc_cbq_fopt
) },
1127 [TCA_CBQ_OVL_STRATEGY
] = { .len
= sizeof(struct tc_cbq_ovl
) },
1128 [TCA_CBQ_RATE
] = { .len
= sizeof(struct tc_ratespec
) },
1129 [TCA_CBQ_RTAB
] = { .type
= NLA_BINARY
, .len
= TC_RTAB_SIZE
},
1130 [TCA_CBQ_POLICE
] = { .len
= sizeof(struct tc_cbq_police
) },
1133 static int cbq_init(struct Qdisc
*sch
, struct nlattr
*opt
)
1135 struct cbq_sched_data
*q
= qdisc_priv(sch
);
1136 struct nlattr
*tb
[TCA_CBQ_MAX
+ 1];
1137 struct tc_ratespec
*r
;
1140 err
= nla_parse_nested(tb
, TCA_CBQ_MAX
, opt
, cbq_policy
);
1144 if (tb
[TCA_CBQ_RTAB
] == NULL
|| tb
[TCA_CBQ_RATE
] == NULL
)
1147 r
= nla_data(tb
[TCA_CBQ_RATE
]);
1149 if ((q
->link
.R_tab
= qdisc_get_rtab(r
, tb
[TCA_CBQ_RTAB
])) == NULL
)
1152 err
= qdisc_class_hash_init(&q
->clhash
);
1157 q
->link
.sibling
= &q
->link
;
1158 q
->link
.common
.classid
= sch
->handle
;
1159 q
->link
.qdisc
= sch
;
1160 q
->link
.q
= qdisc_create_dflt(sch
->dev_queue
, &pfifo_qdisc_ops
,
1163 q
->link
.q
= &noop_qdisc
;
1165 q
->link
.priority
= TC_CBQ_MAXPRIO
- 1;
1166 q
->link
.priority2
= TC_CBQ_MAXPRIO
- 1;
1167 q
->link
.cpriority
= TC_CBQ_MAXPRIO
- 1;
1168 q
->link
.allot
= psched_mtu(qdisc_dev(sch
));
1169 q
->link
.quantum
= q
->link
.allot
;
1170 q
->link
.weight
= q
->link
.R_tab
->rate
.rate
;
1172 q
->link
.ewma_log
= TC_CBQ_DEF_EWMA
;
1173 q
->link
.avpkt
= q
->link
.allot
/2;
1174 q
->link
.minidle
= -0x7FFFFFFF;
1176 qdisc_watchdog_init(&q
->watchdog
, sch
);
1177 hrtimer_init(&q
->delay_timer
, CLOCK_MONOTONIC
, HRTIMER_MODE_ABS_PINNED
);
1178 q
->delay_timer
.function
= cbq_undelay
;
1179 q
->toplevel
= TC_CBQ_MAXLEVEL
;
1180 q
->now
= psched_get_time();
1182 cbq_link_class(&q
->link
);
1184 if (tb
[TCA_CBQ_LSSOPT
])
1185 cbq_set_lss(&q
->link
, nla_data(tb
[TCA_CBQ_LSSOPT
]));
1187 cbq_addprio(q
, &q
->link
);
1191 qdisc_put_rtab(q
->link
.R_tab
);
1195 static int cbq_dump_rate(struct sk_buff
*skb
, struct cbq_class
*cl
)
1197 unsigned char *b
= skb_tail_pointer(skb
);
1199 if (nla_put(skb
, TCA_CBQ_RATE
, sizeof(cl
->R_tab
->rate
), &cl
->R_tab
->rate
))
1200 goto nla_put_failure
;
1208 static int cbq_dump_lss(struct sk_buff
*skb
, struct cbq_class
*cl
)
1210 unsigned char *b
= skb_tail_pointer(skb
);
1211 struct tc_cbq_lssopt opt
;
1214 if (cl
->borrow
== NULL
)
1215 opt
.flags
|= TCF_CBQ_LSS_BOUNDED
;
1216 if (cl
->share
== NULL
)
1217 opt
.flags
|= TCF_CBQ_LSS_ISOLATED
;
1218 opt
.ewma_log
= cl
->ewma_log
;
1219 opt
.level
= cl
->level
;
1220 opt
.avpkt
= cl
->avpkt
;
1221 opt
.maxidle
= cl
->maxidle
;
1222 opt
.minidle
= (u32
)(-cl
->minidle
);
1223 opt
.offtime
= cl
->offtime
;
1225 if (nla_put(skb
, TCA_CBQ_LSSOPT
, sizeof(opt
), &opt
))
1226 goto nla_put_failure
;
1234 static int cbq_dump_wrr(struct sk_buff
*skb
, struct cbq_class
*cl
)
1236 unsigned char *b
= skb_tail_pointer(skb
);
1237 struct tc_cbq_wrropt opt
;
1239 memset(&opt
, 0, sizeof(opt
));
1241 opt
.allot
= cl
->allot
;
1242 opt
.priority
= cl
->priority
+ 1;
1243 opt
.cpriority
= cl
->cpriority
+ 1;
1244 opt
.weight
= cl
->weight
;
1245 if (nla_put(skb
, TCA_CBQ_WRROPT
, sizeof(opt
), &opt
))
1246 goto nla_put_failure
;
1254 static int cbq_dump_fopt(struct sk_buff
*skb
, struct cbq_class
*cl
)
1256 unsigned char *b
= skb_tail_pointer(skb
);
1257 struct tc_cbq_fopt opt
;
1259 if (cl
->split
|| cl
->defmap
) {
1260 opt
.split
= cl
->split
? cl
->split
->common
.classid
: 0;
1261 opt
.defmap
= cl
->defmap
;
1263 if (nla_put(skb
, TCA_CBQ_FOPT
, sizeof(opt
), &opt
))
1264 goto nla_put_failure
;
1273 static int cbq_dump_attr(struct sk_buff
*skb
, struct cbq_class
*cl
)
1275 if (cbq_dump_lss(skb
, cl
) < 0 ||
1276 cbq_dump_rate(skb
, cl
) < 0 ||
1277 cbq_dump_wrr(skb
, cl
) < 0 ||
1278 cbq_dump_fopt(skb
, cl
) < 0)
1283 static int cbq_dump(struct Qdisc
*sch
, struct sk_buff
*skb
)
1285 struct cbq_sched_data
*q
= qdisc_priv(sch
);
1286 struct nlattr
*nest
;
1288 nest
= nla_nest_start(skb
, TCA_OPTIONS
);
1290 goto nla_put_failure
;
1291 if (cbq_dump_attr(skb
, &q
->link
) < 0)
1292 goto nla_put_failure
;
1293 return nla_nest_end(skb
, nest
);
1296 nla_nest_cancel(skb
, nest
);
1301 cbq_dump_stats(struct Qdisc
*sch
, struct gnet_dump
*d
)
1303 struct cbq_sched_data
*q
= qdisc_priv(sch
);
1305 q
->link
.xstats
.avgidle
= q
->link
.avgidle
;
1306 return gnet_stats_copy_app(d
, &q
->link
.xstats
, sizeof(q
->link
.xstats
));
1310 cbq_dump_class(struct Qdisc
*sch
, unsigned long arg
,
1311 struct sk_buff
*skb
, struct tcmsg
*tcm
)
1313 struct cbq_class
*cl
= (struct cbq_class
*)arg
;
1314 struct nlattr
*nest
;
1317 tcm
->tcm_parent
= cl
->tparent
->common
.classid
;
1319 tcm
->tcm_parent
= TC_H_ROOT
;
1320 tcm
->tcm_handle
= cl
->common
.classid
;
1321 tcm
->tcm_info
= cl
->q
->handle
;
1323 nest
= nla_nest_start(skb
, TCA_OPTIONS
);
1325 goto nla_put_failure
;
1326 if (cbq_dump_attr(skb
, cl
) < 0)
1327 goto nla_put_failure
;
1328 return nla_nest_end(skb
, nest
);
1331 nla_nest_cancel(skb
, nest
);
1336 cbq_dump_class_stats(struct Qdisc
*sch
, unsigned long arg
,
1337 struct gnet_dump
*d
)
1339 struct cbq_sched_data
*q
= qdisc_priv(sch
);
1340 struct cbq_class
*cl
= (struct cbq_class
*)arg
;
1342 cl
->xstats
.avgidle
= cl
->avgidle
;
1343 cl
->xstats
.undertime
= 0;
1345 if (cl
->undertime
!= PSCHED_PASTPERFECT
)
1346 cl
->xstats
.undertime
= cl
->undertime
- q
->now
;
1348 if (gnet_stats_copy_basic(qdisc_root_sleeping_running(sch
),
1349 d
, NULL
, &cl
->bstats
) < 0 ||
1350 gnet_stats_copy_rate_est(d
, &cl
->rate_est
) < 0 ||
1351 gnet_stats_copy_queue(d
, NULL
, &cl
->qstats
, cl
->q
->q
.qlen
) < 0)
1354 return gnet_stats_copy_app(d
, &cl
->xstats
, sizeof(cl
->xstats
));
1357 static int cbq_graft(struct Qdisc
*sch
, unsigned long arg
, struct Qdisc
*new,
1360 struct cbq_class
*cl
= (struct cbq_class
*)arg
;
1363 new = qdisc_create_dflt(sch
->dev_queue
,
1364 &pfifo_qdisc_ops
, cl
->common
.classid
);
1369 *old
= qdisc_replace(sch
, new, &cl
->q
);
1373 static struct Qdisc
*cbq_leaf(struct Qdisc
*sch
, unsigned long arg
)
1375 struct cbq_class
*cl
= (struct cbq_class
*)arg
;
1380 static void cbq_qlen_notify(struct Qdisc
*sch
, unsigned long arg
)
1382 struct cbq_class
*cl
= (struct cbq_class
*)arg
;
1384 if (cl
->q
->q
.qlen
== 0)
1385 cbq_deactivate_class(cl
);
1388 static unsigned long cbq_get(struct Qdisc
*sch
, u32 classid
)
1390 struct cbq_sched_data
*q
= qdisc_priv(sch
);
1391 struct cbq_class
*cl
= cbq_class_lookup(q
, classid
);
1395 return (unsigned long)cl
;
1400 static void cbq_destroy_class(struct Qdisc
*sch
, struct cbq_class
*cl
)
1402 struct cbq_sched_data
*q
= qdisc_priv(sch
);
1404 WARN_ON(cl
->filters
);
1406 tcf_destroy_chain(&cl
->filter_list
);
1407 qdisc_destroy(cl
->q
);
1408 qdisc_put_rtab(cl
->R_tab
);
1409 gen_kill_estimator(&cl
->rate_est
);
1414 static void cbq_destroy(struct Qdisc
*sch
)
1416 struct cbq_sched_data
*q
= qdisc_priv(sch
);
1417 struct hlist_node
*next
;
1418 struct cbq_class
*cl
;
1421 #ifdef CONFIG_NET_CLS_ACT
1425 * Filters must be destroyed first because we don't destroy the
1426 * classes from root to leafs which means that filters can still
1427 * be bound to classes which have been destroyed already. --TGR '04
1429 for (h
= 0; h
< q
->clhash
.hashsize
; h
++) {
1430 hlist_for_each_entry(cl
, &q
->clhash
.hash
[h
], common
.hnode
)
1431 tcf_destroy_chain(&cl
->filter_list
);
1433 for (h
= 0; h
< q
->clhash
.hashsize
; h
++) {
1434 hlist_for_each_entry_safe(cl
, next
, &q
->clhash
.hash
[h
],
1436 cbq_destroy_class(sch
, cl
);
1438 qdisc_class_hash_destroy(&q
->clhash
);
1441 static void cbq_put(struct Qdisc
*sch
, unsigned long arg
)
1443 struct cbq_class
*cl
= (struct cbq_class
*)arg
;
1445 if (--cl
->refcnt
== 0) {
1446 #ifdef CONFIG_NET_CLS_ACT
1447 spinlock_t
*root_lock
= qdisc_root_sleeping_lock(sch
);
1448 struct cbq_sched_data
*q
= qdisc_priv(sch
);
1450 spin_lock_bh(root_lock
);
1451 if (q
->rx_class
== cl
)
1453 spin_unlock_bh(root_lock
);
1456 cbq_destroy_class(sch
, cl
);
1461 cbq_change_class(struct Qdisc
*sch
, u32 classid
, u32 parentid
, struct nlattr
**tca
,
1465 struct cbq_sched_data
*q
= qdisc_priv(sch
);
1466 struct cbq_class
*cl
= (struct cbq_class
*)*arg
;
1467 struct nlattr
*opt
= tca
[TCA_OPTIONS
];
1468 struct nlattr
*tb
[TCA_CBQ_MAX
+ 1];
1469 struct cbq_class
*parent
;
1470 struct qdisc_rate_table
*rtab
= NULL
;
1475 err
= nla_parse_nested(tb
, TCA_CBQ_MAX
, opt
, cbq_policy
);
1479 if (tb
[TCA_CBQ_OVL_STRATEGY
] || tb
[TCA_CBQ_POLICE
])
1486 cl
->tparent
->common
.classid
!= parentid
)
1488 if (!cl
->tparent
&& parentid
!= TC_H_ROOT
)
1492 if (tb
[TCA_CBQ_RATE
]) {
1493 rtab
= qdisc_get_rtab(nla_data(tb
[TCA_CBQ_RATE
]),
1499 if (tca
[TCA_RATE
]) {
1500 err
= gen_replace_estimator(&cl
->bstats
, NULL
,
1503 qdisc_root_sleeping_running(sch
),
1506 qdisc_put_rtab(rtab
);
1511 /* Change class parameters */
1514 if (cl
->next_alive
!= NULL
)
1515 cbq_deactivate_class(cl
);
1518 qdisc_put_rtab(cl
->R_tab
);
1522 if (tb
[TCA_CBQ_LSSOPT
])
1523 cbq_set_lss(cl
, nla_data(tb
[TCA_CBQ_LSSOPT
]));
1525 if (tb
[TCA_CBQ_WRROPT
]) {
1527 cbq_set_wrr(cl
, nla_data(tb
[TCA_CBQ_WRROPT
]));
1530 if (tb
[TCA_CBQ_FOPT
])
1531 cbq_set_fopt(cl
, nla_data(tb
[TCA_CBQ_FOPT
]));
1534 cbq_activate_class(cl
);
1536 sch_tree_unlock(sch
);
1541 if (parentid
== TC_H_ROOT
)
1544 if (tb
[TCA_CBQ_WRROPT
] == NULL
|| tb
[TCA_CBQ_RATE
] == NULL
||
1545 tb
[TCA_CBQ_LSSOPT
] == NULL
)
1548 rtab
= qdisc_get_rtab(nla_data(tb
[TCA_CBQ_RATE
]), tb
[TCA_CBQ_RTAB
]);
1554 if (TC_H_MAJ(classid
^ sch
->handle
) ||
1555 cbq_class_lookup(q
, classid
))
1559 classid
= TC_H_MAKE(sch
->handle
, 0x8000);
1561 for (i
= 0; i
< 0x8000; i
++) {
1562 if (++q
->hgenerator
>= 0x8000)
1564 if (cbq_class_lookup(q
, classid
|q
->hgenerator
) == NULL
)
1570 classid
= classid
|q
->hgenerator
;
1575 parent
= cbq_class_lookup(q
, parentid
);
1582 cl
= kzalloc(sizeof(*cl
), GFP_KERNEL
);
1586 if (tca
[TCA_RATE
]) {
1587 err
= gen_new_estimator(&cl
->bstats
, NULL
, &cl
->rate_est
,
1589 qdisc_root_sleeping_running(sch
),
1600 cl
->q
= qdisc_create_dflt(sch
->dev_queue
, &pfifo_qdisc_ops
, classid
);
1602 cl
->q
= &noop_qdisc
;
1603 cl
->common
.classid
= classid
;
1604 cl
->tparent
= parent
;
1606 cl
->allot
= parent
->allot
;
1607 cl
->quantum
= cl
->allot
;
1608 cl
->weight
= cl
->R_tab
->rate
.rate
;
1612 cl
->borrow
= cl
->tparent
;
1613 if (cl
->tparent
!= &q
->link
)
1614 cl
->share
= cl
->tparent
;
1615 cbq_adjust_levels(parent
);
1616 cl
->minidle
= -0x7FFFFFFF;
1617 cbq_set_lss(cl
, nla_data(tb
[TCA_CBQ_LSSOPT
]));
1618 cbq_set_wrr(cl
, nla_data(tb
[TCA_CBQ_WRROPT
]));
1619 if (cl
->ewma_log
== 0)
1620 cl
->ewma_log
= q
->link
.ewma_log
;
1621 if (cl
->maxidle
== 0)
1622 cl
->maxidle
= q
->link
.maxidle
;
1624 cl
->avpkt
= q
->link
.avpkt
;
1625 if (tb
[TCA_CBQ_FOPT
])
1626 cbq_set_fopt(cl
, nla_data(tb
[TCA_CBQ_FOPT
]));
1627 sch_tree_unlock(sch
);
1629 qdisc_class_hash_grow(sch
, &q
->clhash
);
1631 *arg
= (unsigned long)cl
;
1635 qdisc_put_rtab(rtab
);
1639 static int cbq_delete(struct Qdisc
*sch
, unsigned long arg
)
1641 struct cbq_sched_data
*q
= qdisc_priv(sch
);
1642 struct cbq_class
*cl
= (struct cbq_class
*)arg
;
1643 unsigned int qlen
, backlog
;
1645 if (cl
->filters
|| cl
->children
|| cl
== &q
->link
)
1650 qlen
= cl
->q
->q
.qlen
;
1651 backlog
= cl
->q
->qstats
.backlog
;
1653 qdisc_tree_reduce_backlog(cl
->q
, qlen
, backlog
);
1656 cbq_deactivate_class(cl
);
1658 if (q
->tx_borrowed
== cl
)
1659 q
->tx_borrowed
= q
->tx_class
;
1660 if (q
->tx_class
== cl
) {
1662 q
->tx_borrowed
= NULL
;
1664 #ifdef CONFIG_NET_CLS_ACT
1665 if (q
->rx_class
== cl
)
1669 cbq_unlink_class(cl
);
1670 cbq_adjust_levels(cl
->tparent
);
1672 cbq_sync_defmap(cl
);
1675 sch_tree_unlock(sch
);
1677 BUG_ON(--cl
->refcnt
== 0);
1679 * This shouldn't happen: we "hold" one cops->get() when called
1680 * from tc_ctl_tclass; the destroy method is done from cops->put().
1686 static struct tcf_proto __rcu
**cbq_find_tcf(struct Qdisc
*sch
,
1689 struct cbq_sched_data
*q
= qdisc_priv(sch
);
1690 struct cbq_class
*cl
= (struct cbq_class
*)arg
;
1695 return &cl
->filter_list
;
1698 static unsigned long cbq_bind_filter(struct Qdisc
*sch
, unsigned long parent
,
1701 struct cbq_sched_data
*q
= qdisc_priv(sch
);
1702 struct cbq_class
*p
= (struct cbq_class
*)parent
;
1703 struct cbq_class
*cl
= cbq_class_lookup(q
, classid
);
1706 if (p
&& p
->level
<= cl
->level
)
1709 return (unsigned long)cl
;
1714 static void cbq_unbind_filter(struct Qdisc
*sch
, unsigned long arg
)
1716 struct cbq_class
*cl
= (struct cbq_class
*)arg
;
1721 static void cbq_walk(struct Qdisc
*sch
, struct qdisc_walker
*arg
)
1723 struct cbq_sched_data
*q
= qdisc_priv(sch
);
1724 struct cbq_class
*cl
;
1730 for (h
= 0; h
< q
->clhash
.hashsize
; h
++) {
1731 hlist_for_each_entry(cl
, &q
->clhash
.hash
[h
], common
.hnode
) {
1732 if (arg
->count
< arg
->skip
) {
1736 if (arg
->fn(sch
, (unsigned long)cl
, arg
) < 0) {
1745 static const struct Qdisc_class_ops cbq_class_ops
= {
1748 .qlen_notify
= cbq_qlen_notify
,
1751 .change
= cbq_change_class
,
1752 .delete = cbq_delete
,
1754 .tcf_chain
= cbq_find_tcf
,
1755 .bind_tcf
= cbq_bind_filter
,
1756 .unbind_tcf
= cbq_unbind_filter
,
1757 .dump
= cbq_dump_class
,
1758 .dump_stats
= cbq_dump_class_stats
,
1761 static struct Qdisc_ops cbq_qdisc_ops __read_mostly
= {
1763 .cl_ops
= &cbq_class_ops
,
1765 .priv_size
= sizeof(struct cbq_sched_data
),
1766 .enqueue
= cbq_enqueue
,
1767 .dequeue
= cbq_dequeue
,
1768 .peek
= qdisc_peek_dequeued
,
1771 .destroy
= cbq_destroy
,
1774 .dump_stats
= cbq_dump_stats
,
1775 .owner
= THIS_MODULE
,
1778 static int __init
cbq_module_init(void)
1780 return register_qdisc(&cbq_qdisc_ops
);
1782 static void __exit
cbq_module_exit(void)
1784 unregister_qdisc(&cbq_qdisc_ops
);
1786 module_init(cbq_module_init
)
1787 module_exit(cbq_module_exit
)
1788 MODULE_LICENSE("GPL");