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>
24 /* Class-Based Queueing (CBQ) algorithm.
25 =======================================
27 Sources: [1] Sally Floyd and Van Jacobson, "Link-sharing and Resource
28 Management Models for Packet Networks",
29 IEEE/ACM Transactions on Networking, Vol.3, No.4, 1995
31 [2] Sally Floyd, "Notes on CBQ and Guaranteed Service", 1995
33 [3] Sally Floyd, "Notes on Class-Based Queueing: Setting
36 [4] Sally Floyd and Michael Speer, "Experimental Results
37 for Class-Based Queueing", 1998, not published.
39 -----------------------------------------------------------------------
41 Algorithm skeleton was taken from NS simulator cbq.cc.
42 If someone wants to check this code against the LBL version,
43 he should take into account that ONLY the skeleton was borrowed,
44 the implementation is different. Particularly:
46 --- The WRR algorithm is different. Our version looks more
47 reasonable (I hope) and works when quanta are allowed to be
48 less than MTU, which is always the case when real time classes
49 have small rates. Note, that the statement of [3] is
50 incomplete, delay may actually be estimated even if class
51 per-round allotment is less than MTU. Namely, if per-round
52 allotment is W*r_i, and r_1+...+r_k = r < 1
54 delay_i <= ([MTU/(W*r_i)]*W*r + W*r + k*MTU)/B
56 In the worst case we have IntServ estimate with D = W*r+k*MTU
57 and C = MTU*r. The proof (if correct at all) is trivial.
60 --- It seems that cbq-2.0 is not very accurate. At least, I cannot
61 interpret some places, which look like wrong translations
62 from NS. Anyone is advised to find these differences
63 and explain to me, why I am wrong 8).
65 --- Linux has no EOI event, so that we cannot estimate true class
66 idle time. Workaround is to consider the next dequeue event
67 as sign that previous packet is finished. This is wrong because of
68 internal device queueing, but on a permanently loaded link it is true.
69 Moreover, combined with clock integrator, this scheme looks
70 very close to an ideal solution. */
72 struct cbq_sched_data
;
76 struct Qdisc_class_common common
;
77 struct cbq_class
*next_alive
; /* next class with backlog in this priority band */
80 unsigned char priority
; /* class priority */
81 unsigned char priority2
; /* priority to be used after overlimit */
82 unsigned char ewma_log
; /* time constant for idle time calculation */
83 unsigned char ovl_strategy
;
84 #ifdef CONFIG_NET_CLS_ACT
90 /* Link-sharing scheduler parameters */
91 long maxidle
; /* Class parameters: see below. */
95 struct qdisc_rate_table
*R_tab
;
97 /* Overlimit strategy parameters */
98 void (*overlimit
)(struct cbq_class
*cl
);
99 psched_tdiff_t penalty
;
101 /* General scheduler (WRR) parameters */
103 long quantum
; /* Allotment per WRR round */
104 long weight
; /* Relative allotment: see below */
106 struct Qdisc
*qdisc
; /* Ptr to CBQ discipline */
107 struct cbq_class
*split
; /* Ptr to split node */
108 struct cbq_class
*share
; /* Ptr to LS parent in the class tree */
109 struct cbq_class
*tparent
; /* Ptr to tree parent in the class tree */
110 struct cbq_class
*borrow
; /* NULL if class is bandwidth limited;
112 struct cbq_class
*sibling
; /* Sibling chain */
113 struct cbq_class
*children
; /* Pointer to children chain */
115 struct Qdisc
*q
; /* Elementary queueing discipline */
119 unsigned char cpriority
; /* Effective priority */
120 unsigned char delayed
;
121 unsigned char level
; /* level of the class in hierarchy:
122 0 for leaf classes, and maximal
123 level of children + 1 for nodes.
126 psched_time_t last
; /* Last end of service */
127 psched_time_t undertime
;
129 long deficit
; /* Saved deficit for WRR */
130 psched_time_t penalized
;
131 struct gnet_stats_basic_packed bstats
;
132 struct gnet_stats_queue qstats
;
133 struct gnet_stats_rate_est rate_est
;
134 struct tc_cbq_xstats xstats
;
136 struct tcf_proto
*filter_list
;
141 struct cbq_class
*defaults
[TC_PRIO_MAX
+ 1];
144 struct cbq_sched_data
{
145 struct Qdisc_class_hash clhash
; /* Hash table of all classes */
146 int nclasses
[TC_CBQ_MAXPRIO
+ 1];
147 unsigned int quanta
[TC_CBQ_MAXPRIO
+ 1];
149 struct cbq_class link
;
151 unsigned int activemask
;
152 struct cbq_class
*active
[TC_CBQ_MAXPRIO
+ 1]; /* List of all classes
155 #ifdef CONFIG_NET_CLS_ACT
156 struct cbq_class
*rx_class
;
158 struct cbq_class
*tx_class
;
159 struct cbq_class
*tx_borrowed
;
161 psched_time_t now
; /* Cached timestamp */
162 psched_time_t now_rt
; /* Cached real time */
165 struct hrtimer delay_timer
;
166 struct qdisc_watchdog watchdog
; /* Watchdog timer,
170 psched_tdiff_t wd_expires
;
176 #define L2T(cl, len) qdisc_l2t((cl)->R_tab, len)
178 static inline struct cbq_class
*
179 cbq_class_lookup(struct cbq_sched_data
*q
, u32 classid
)
181 struct Qdisc_class_common
*clc
;
183 clc
= qdisc_class_find(&q
->clhash
, classid
);
186 return container_of(clc
, struct cbq_class
, common
);
189 #ifdef CONFIG_NET_CLS_ACT
191 static struct cbq_class
*
192 cbq_reclassify(struct sk_buff
*skb
, struct cbq_class
*this)
194 struct cbq_class
*cl
;
196 for (cl
= this->tparent
; cl
; cl
= cl
->tparent
) {
197 struct cbq_class
*new = cl
->defaults
[TC_PRIO_BESTEFFORT
];
199 if (new != NULL
&& new != this)
207 /* Classify packet. The procedure is pretty complicated, but
208 * it allows us to combine link sharing and priority scheduling
211 * Namely, you can put link sharing rules (f.e. route based) at root of CBQ,
212 * so that it resolves to split nodes. Then packets are classified
213 * by logical priority, or a more specific classifier may be attached
217 static struct cbq_class
*
218 cbq_classify(struct sk_buff
*skb
, struct Qdisc
*sch
, int *qerr
)
220 struct cbq_sched_data
*q
= qdisc_priv(sch
);
221 struct cbq_class
*head
= &q
->link
;
222 struct cbq_class
**defmap
;
223 struct cbq_class
*cl
= NULL
;
224 u32 prio
= skb
->priority
;
225 struct tcf_result res
;
228 * Step 1. If skb->priority points to one of our classes, use it.
230 if (TC_H_MAJ(prio
^ sch
->handle
) == 0 &&
231 (cl
= cbq_class_lookup(q
, prio
)) != NULL
)
234 *qerr
= NET_XMIT_SUCCESS
| __NET_XMIT_BYPASS
;
237 defmap
= head
->defaults
;
240 * Step 2+n. Apply classifier.
242 if (!head
->filter_list
||
243 (result
= tc_classify_compat(skb
, head
->filter_list
, &res
)) < 0)
246 cl
= (void *)res
.class;
248 if (TC_H_MAJ(res
.classid
))
249 cl
= cbq_class_lookup(q
, res
.classid
);
250 else if ((cl
= defmap
[res
.classid
& TC_PRIO_MAX
]) == NULL
)
251 cl
= defmap
[TC_PRIO_BESTEFFORT
];
253 if (cl
== NULL
|| cl
->level
>= head
->level
)
257 #ifdef CONFIG_NET_CLS_ACT
261 *qerr
= NET_XMIT_SUCCESS
| __NET_XMIT_STOLEN
;
264 case TC_ACT_RECLASSIFY
:
265 return cbq_reclassify(skb
, cl
);
272 * Step 3+n. If classifier selected a link sharing class,
273 * apply agency specific classifier.
274 * Repeat this procdure until we hit a leaf node.
283 * Step 4. No success...
285 if (TC_H_MAJ(prio
) == 0 &&
286 !(cl
= head
->defaults
[prio
& TC_PRIO_MAX
]) &&
287 !(cl
= head
->defaults
[TC_PRIO_BESTEFFORT
]))
294 * A packet has just been enqueued on the empty class.
295 * cbq_activate_class adds it to the tail of active class list
296 * of its priority band.
299 static inline void cbq_activate_class(struct cbq_class
*cl
)
301 struct cbq_sched_data
*q
= qdisc_priv(cl
->qdisc
);
302 int prio
= cl
->cpriority
;
303 struct cbq_class
*cl_tail
;
305 cl_tail
= q
->active
[prio
];
306 q
->active
[prio
] = cl
;
308 if (cl_tail
!= NULL
) {
309 cl
->next_alive
= cl_tail
->next_alive
;
310 cl_tail
->next_alive
= cl
;
313 q
->activemask
|= (1<<prio
);
318 * Unlink class from active chain.
319 * Note that this same procedure is done directly in cbq_dequeue*
320 * during round-robin procedure.
323 static void cbq_deactivate_class(struct cbq_class
*this)
325 struct cbq_sched_data
*q
= qdisc_priv(this->qdisc
);
326 int prio
= this->cpriority
;
327 struct cbq_class
*cl
;
328 struct cbq_class
*cl_prev
= q
->active
[prio
];
331 cl
= cl_prev
->next_alive
;
333 cl_prev
->next_alive
= cl
->next_alive
;
334 cl
->next_alive
= NULL
;
336 if (cl
== q
->active
[prio
]) {
337 q
->active
[prio
] = cl_prev
;
338 if (cl
== q
->active
[prio
]) {
339 q
->active
[prio
] = NULL
;
340 q
->activemask
&= ~(1<<prio
);
346 } while ((cl_prev
= cl
) != q
->active
[prio
]);
350 cbq_mark_toplevel(struct cbq_sched_data
*q
, struct cbq_class
*cl
)
352 int toplevel
= q
->toplevel
;
354 if (toplevel
> cl
->level
&& !(qdisc_is_throttled(cl
->q
))) {
358 now
= psched_get_time();
359 incr
= now
- q
->now_rt
;
363 if (cl
->undertime
< now
) {
364 q
->toplevel
= cl
->level
;
367 } while ((cl
= cl
->borrow
) != NULL
&& toplevel
> cl
->level
);
372 cbq_enqueue(struct sk_buff
*skb
, struct Qdisc
*sch
)
374 struct cbq_sched_data
*q
= qdisc_priv(sch
);
375 int uninitialized_var(ret
);
376 struct cbq_class
*cl
= cbq_classify(skb
, sch
, &ret
);
378 #ifdef CONFIG_NET_CLS_ACT
382 if (ret
& __NET_XMIT_BYPASS
)
388 #ifdef CONFIG_NET_CLS_ACT
389 cl
->q
->__parent
= sch
;
391 ret
= qdisc_enqueue(skb
, cl
->q
);
392 if (ret
== NET_XMIT_SUCCESS
) {
394 qdisc_bstats_update(sch
, skb
);
395 cbq_mark_toplevel(q
, cl
);
397 cbq_activate_class(cl
);
401 if (net_xmit_drop_count(ret
)) {
403 cbq_mark_toplevel(q
, cl
);
409 /* Overlimit actions */
411 /* TC_CBQ_OVL_CLASSIC: (default) penalize leaf class by adding offtime */
413 static void cbq_ovl_classic(struct cbq_class
*cl
)
415 struct cbq_sched_data
*q
= qdisc_priv(cl
->qdisc
);
416 psched_tdiff_t delay
= cl
->undertime
- q
->now
;
419 delay
+= cl
->offtime
;
422 * Class goes to sleep, so that it will have no
423 * chance to work avgidle. Let's forgive it 8)
425 * BTW cbq-2.0 has a crap in this
426 * place, apparently they forgot to shift it by cl->ewma_log.
429 delay
-= (-cl
->avgidle
) - ((-cl
->avgidle
) >> cl
->ewma_log
);
430 if (cl
->avgidle
< cl
->minidle
)
431 cl
->avgidle
= cl
->minidle
;
434 cl
->undertime
= q
->now
+ delay
;
436 cl
->xstats
.overactions
++;
439 if (q
->wd_expires
== 0 || q
->wd_expires
> delay
)
440 q
->wd_expires
= delay
;
442 /* Dirty work! We must schedule wakeups based on
443 * real available rate, rather than leaf rate,
444 * which may be tiny (even zero).
446 if (q
->toplevel
== TC_CBQ_MAXLEVEL
) {
448 psched_tdiff_t base_delay
= q
->wd_expires
;
450 for (b
= cl
->borrow
; b
; b
= b
->borrow
) {
451 delay
= b
->undertime
- q
->now
;
452 if (delay
< base_delay
) {
459 q
->wd_expires
= base_delay
;
463 /* TC_CBQ_OVL_RCLASSIC: penalize by offtime classes in hierarchy, when
467 static void cbq_ovl_rclassic(struct cbq_class
*cl
)
469 struct cbq_sched_data
*q
= qdisc_priv(cl
->qdisc
);
470 struct cbq_class
*this = cl
;
473 if (cl
->level
> q
->toplevel
) {
477 } while ((cl
= cl
->borrow
) != NULL
);
484 /* TC_CBQ_OVL_DELAY: delay until it will go to underlimit */
486 static void cbq_ovl_delay(struct cbq_class
*cl
)
488 struct cbq_sched_data
*q
= qdisc_priv(cl
->qdisc
);
489 psched_tdiff_t delay
= cl
->undertime
- q
->now
;
491 if (test_bit(__QDISC_STATE_DEACTIVATED
,
492 &qdisc_root_sleeping(cl
->qdisc
)->state
))
496 psched_time_t sched
= q
->now
;
499 delay
+= cl
->offtime
;
501 delay
-= (-cl
->avgidle
) - ((-cl
->avgidle
) >> cl
->ewma_log
);
502 if (cl
->avgidle
< cl
->minidle
)
503 cl
->avgidle
= cl
->minidle
;
504 cl
->undertime
= q
->now
+ delay
;
507 sched
+= delay
+ cl
->penalty
;
508 cl
->penalized
= sched
;
509 cl
->cpriority
= TC_CBQ_MAXPRIO
;
510 q
->pmask
|= (1<<TC_CBQ_MAXPRIO
);
512 expires
= ktime_set(0, 0);
513 expires
= ktime_add_ns(expires
, PSCHED_TICKS2NS(sched
));
514 if (hrtimer_try_to_cancel(&q
->delay_timer
) &&
515 ktime_to_ns(ktime_sub(
516 hrtimer_get_expires(&q
->delay_timer
),
518 hrtimer_set_expires(&q
->delay_timer
, expires
);
519 hrtimer_restart(&q
->delay_timer
);
521 cl
->xstats
.overactions
++;
526 if (q
->wd_expires
== 0 || q
->wd_expires
> delay
)
527 q
->wd_expires
= delay
;
530 /* TC_CBQ_OVL_LOWPRIO: penalize class by lowering its priority band */
532 static void cbq_ovl_lowprio(struct cbq_class
*cl
)
534 struct cbq_sched_data
*q
= qdisc_priv(cl
->qdisc
);
536 cl
->penalized
= q
->now
+ cl
->penalty
;
538 if (cl
->cpriority
!= cl
->priority2
) {
539 cl
->cpriority
= cl
->priority2
;
540 q
->pmask
|= (1<<cl
->cpriority
);
541 cl
->xstats
.overactions
++;
546 /* TC_CBQ_OVL_DROP: penalize class by dropping */
548 static void cbq_ovl_drop(struct cbq_class
*cl
)
550 if (cl
->q
->ops
->drop
)
551 if (cl
->q
->ops
->drop(cl
->q
))
553 cl
->xstats
.overactions
++;
557 static psched_tdiff_t
cbq_undelay_prio(struct cbq_sched_data
*q
, int prio
,
560 struct cbq_class
*cl
;
561 struct cbq_class
*cl_prev
= q
->active
[prio
];
562 psched_time_t sched
= now
;
568 cl
= cl_prev
->next_alive
;
569 if (now
- cl
->penalized
> 0) {
570 cl_prev
->next_alive
= cl
->next_alive
;
571 cl
->next_alive
= NULL
;
572 cl
->cpriority
= cl
->priority
;
574 cbq_activate_class(cl
);
576 if (cl
== q
->active
[prio
]) {
577 q
->active
[prio
] = cl_prev
;
578 if (cl
== q
->active
[prio
]) {
579 q
->active
[prio
] = NULL
;
584 cl
= cl_prev
->next_alive
;
585 } else if (sched
- cl
->penalized
> 0)
586 sched
= cl
->penalized
;
587 } while ((cl_prev
= cl
) != q
->active
[prio
]);
592 static enum hrtimer_restart
cbq_undelay(struct hrtimer
*timer
)
594 struct cbq_sched_data
*q
= container_of(timer
, struct cbq_sched_data
,
596 struct Qdisc
*sch
= q
->watchdog
.qdisc
;
598 psched_tdiff_t delay
= 0;
601 now
= psched_get_time();
607 int prio
= ffz(~pmask
);
612 tmp
= cbq_undelay_prio(q
, prio
, now
);
615 if (tmp
< delay
|| delay
== 0)
623 time
= ktime_set(0, 0);
624 time
= ktime_add_ns(time
, PSCHED_TICKS2NS(now
+ delay
));
625 hrtimer_start(&q
->delay_timer
, time
, HRTIMER_MODE_ABS
);
628 qdisc_unthrottled(sch
);
629 __netif_schedule(qdisc_root(sch
));
630 return HRTIMER_NORESTART
;
633 #ifdef CONFIG_NET_CLS_ACT
634 static int cbq_reshape_fail(struct sk_buff
*skb
, struct Qdisc
*child
)
636 struct Qdisc
*sch
= child
->__parent
;
637 struct cbq_sched_data
*q
= qdisc_priv(sch
);
638 struct cbq_class
*cl
= q
->rx_class
;
642 if (cl
&& (cl
= cbq_reclassify(skb
, cl
)) != NULL
) {
645 cbq_mark_toplevel(q
, cl
);
648 cl
->q
->__parent
= sch
;
650 ret
= qdisc_enqueue(skb
, cl
->q
);
651 if (ret
== NET_XMIT_SUCCESS
) {
653 qdisc_bstats_update(sch
, skb
);
655 cbq_activate_class(cl
);
658 if (net_xmit_drop_count(ret
))
669 * It is mission critical procedure.
671 * We "regenerate" toplevel cutoff, if transmitting class
672 * has backlog and it is not regulated. It is not part of
673 * original CBQ description, but looks more reasonable.
674 * Probably, it is wrong. This question needs further investigation.
678 cbq_update_toplevel(struct cbq_sched_data
*q
, struct cbq_class
*cl
,
679 struct cbq_class
*borrowed
)
681 if (cl
&& q
->toplevel
>= borrowed
->level
) {
682 if (cl
->q
->q
.qlen
> 1) {
684 if (borrowed
->undertime
== PSCHED_PASTPERFECT
) {
685 q
->toplevel
= borrowed
->level
;
688 } while ((borrowed
= borrowed
->borrow
) != NULL
);
691 /* It is not necessary now. Uncommenting it
692 will save CPU cycles, but decrease fairness.
694 q
->toplevel
= TC_CBQ_MAXLEVEL
;
700 cbq_update(struct cbq_sched_data
*q
)
702 struct cbq_class
*this = q
->tx_class
;
703 struct cbq_class
*cl
= this;
708 for ( ; cl
; cl
= cl
->share
) {
709 long avgidle
= cl
->avgidle
;
712 cl
->bstats
.packets
++;
713 cl
->bstats
.bytes
+= len
;
716 * (now - last) is total time between packet right edges.
717 * (last_pktlen/rate) is "virtual" busy time, so that
719 * idle = (now - last) - last_pktlen/rate
722 idle
= q
->now
- cl
->last
;
723 if ((unsigned long)idle
> 128*1024*1024) {
724 avgidle
= cl
->maxidle
;
726 idle
-= L2T(cl
, len
);
728 /* true_avgidle := (1-W)*true_avgidle + W*idle,
729 * where W=2^{-ewma_log}. But cl->avgidle is scaled:
730 * cl->avgidle == true_avgidle/W,
733 avgidle
+= idle
- (avgidle
>>cl
->ewma_log
);
737 /* Overlimit or at-limit */
739 if (avgidle
< cl
->minidle
)
740 avgidle
= cl
->minidle
;
742 cl
->avgidle
= avgidle
;
744 /* Calculate expected time, when this class
745 * will be allowed to send.
746 * It will occur, when:
747 * (1-W)*true_avgidle + W*delay = 0, i.e.
748 * idle = (1/W - 1)*(-true_avgidle)
750 * idle = (1 - W)*(-cl->avgidle);
752 idle
= (-avgidle
) - ((-avgidle
) >> cl
->ewma_log
);
756 * To maintain the rate allocated to the class,
757 * we add to undertime virtual clock,
758 * necessary to complete transmitted packet.
759 * (len/phys_bandwidth has been already passed
760 * to the moment of cbq_update)
763 idle
-= L2T(&q
->link
, len
);
764 idle
+= L2T(cl
, len
);
766 cl
->undertime
= q
->now
+ idle
;
770 cl
->undertime
= PSCHED_PASTPERFECT
;
771 if (avgidle
> cl
->maxidle
)
772 cl
->avgidle
= cl
->maxidle
;
774 cl
->avgidle
= avgidle
;
779 cbq_update_toplevel(q
, this, q
->tx_borrowed
);
782 static inline struct cbq_class
*
783 cbq_under_limit(struct cbq_class
*cl
)
785 struct cbq_sched_data
*q
= qdisc_priv(cl
->qdisc
);
786 struct cbq_class
*this_cl
= cl
;
788 if (cl
->tparent
== NULL
)
791 if (cl
->undertime
== PSCHED_PASTPERFECT
|| q
->now
>= cl
->undertime
) {
797 /* It is very suspicious place. Now overlimit
798 * action is generated for not bounded classes
799 * only if link is completely congested.
800 * Though it is in agree with ancestor-only paradigm,
801 * it looks very stupid. Particularly,
802 * it means that this chunk of code will either
803 * never be called or result in strong amplification
804 * of burstiness. Dangerous, silly, and, however,
805 * no another solution exists.
809 this_cl
->qstats
.overlimits
++;
810 this_cl
->overlimit(this_cl
);
813 if (cl
->level
> q
->toplevel
)
815 } while (cl
->undertime
!= PSCHED_PASTPERFECT
&& q
->now
< cl
->undertime
);
821 static inline struct sk_buff
*
822 cbq_dequeue_prio(struct Qdisc
*sch
, int prio
)
824 struct cbq_sched_data
*q
= qdisc_priv(sch
);
825 struct cbq_class
*cl_tail
, *cl_prev
, *cl
;
829 cl_tail
= cl_prev
= q
->active
[prio
];
830 cl
= cl_prev
->next_alive
;
837 struct cbq_class
*borrow
= cl
;
840 (borrow
= cbq_under_limit(cl
)) == NULL
)
843 if (cl
->deficit
<= 0) {
844 /* Class exhausted its allotment per
845 * this round. Switch to the next one.
848 cl
->deficit
+= cl
->quantum
;
852 skb
= cl
->q
->dequeue(cl
->q
);
854 /* Class did not give us any skb :-(
855 * It could occur even if cl->q->q.qlen != 0
856 * f.e. if cl->q == "tbf"
861 cl
->deficit
-= qdisc_pkt_len(skb
);
863 q
->tx_borrowed
= borrow
;
865 #ifndef CBQ_XSTATS_BORROWS_BYTES
866 borrow
->xstats
.borrows
++;
867 cl
->xstats
.borrows
++;
869 borrow
->xstats
.borrows
+= qdisc_pkt_len(skb
);
870 cl
->xstats
.borrows
+= qdisc_pkt_len(skb
);
873 q
->tx_len
= qdisc_pkt_len(skb
);
875 if (cl
->deficit
<= 0) {
876 q
->active
[prio
] = cl
;
878 cl
->deficit
+= cl
->quantum
;
883 if (cl
->q
->q
.qlen
== 0 || prio
!= cl
->cpriority
) {
884 /* Class is empty or penalized.
885 * Unlink it from active chain.
887 cl_prev
->next_alive
= cl
->next_alive
;
888 cl
->next_alive
= NULL
;
890 /* Did cl_tail point to it? */
895 /* Was it the last class in this band? */
898 q
->active
[prio
] = NULL
;
899 q
->activemask
&= ~(1<<prio
);
901 cbq_activate_class(cl
);
905 q
->active
[prio
] = cl_tail
;
908 cbq_activate_class(cl
);
916 } while (cl_prev
!= cl_tail
);
919 q
->active
[prio
] = cl_prev
;
924 static inline struct sk_buff
*
925 cbq_dequeue_1(struct Qdisc
*sch
)
927 struct cbq_sched_data
*q
= qdisc_priv(sch
);
929 unsigned int activemask
;
931 activemask
= q
->activemask
& 0xFF;
933 int prio
= ffz(~activemask
);
934 activemask
&= ~(1<<prio
);
935 skb
= cbq_dequeue_prio(sch
, prio
);
942 static struct sk_buff
*
943 cbq_dequeue(struct Qdisc
*sch
)
946 struct cbq_sched_data
*q
= qdisc_priv(sch
);
950 now
= psched_get_time();
951 incr
= now
- q
->now_rt
;
954 psched_tdiff_t incr2
;
955 /* Time integrator. We calculate EOS time
956 * by adding expected packet transmission time.
957 * If real time is greater, we warp artificial clock,
960 * cbq_time = max(real_time, work);
962 incr2
= L2T(&q
->link
, q
->tx_len
);
965 if ((incr
-= incr2
) < 0)
974 skb
= cbq_dequeue_1(sch
);
977 qdisc_unthrottled(sch
);
981 /* All the classes are overlimit.
983 * It is possible, if:
985 * 1. Scheduler is empty.
986 * 2. Toplevel cutoff inhibited borrowing.
987 * 3. Root class is overlimit.
989 * Reset 2d and 3d conditions and retry.
991 * Note, that NS and cbq-2.0 are buggy, peeking
992 * an arbitrary class is appropriate for ancestor-only
993 * sharing, but not for toplevel algorithm.
995 * Our version is better, but slower, because it requires
996 * two passes, but it is unavoidable with top-level sharing.
999 if (q
->toplevel
== TC_CBQ_MAXLEVEL
&&
1000 q
->link
.undertime
== PSCHED_PASTPERFECT
)
1003 q
->toplevel
= TC_CBQ_MAXLEVEL
;
1004 q
->link
.undertime
= PSCHED_PASTPERFECT
;
1007 /* No packets in scheduler or nobody wants to give them to us :-(
1008 * Sigh... start watchdog timer in the last case.
1012 sch
->qstats
.overlimits
++;
1014 qdisc_watchdog_schedule(&q
->watchdog
,
1015 now
+ q
->wd_expires
);
1020 /* CBQ class maintanance routines */
1022 static void cbq_adjust_levels(struct cbq_class
*this)
1029 struct cbq_class
*cl
;
1031 cl
= this->children
;
1034 if (cl
->level
> level
)
1036 } while ((cl
= cl
->sibling
) != this->children
);
1038 this->level
= level
+ 1;
1039 } while ((this = this->tparent
) != NULL
);
1042 static void cbq_normalize_quanta(struct cbq_sched_data
*q
, int prio
)
1044 struct cbq_class
*cl
;
1045 struct hlist_node
*n
;
1048 if (q
->quanta
[prio
] == 0)
1051 for (h
= 0; h
< q
->clhash
.hashsize
; h
++) {
1052 hlist_for_each_entry(cl
, n
, &q
->clhash
.hash
[h
], common
.hnode
) {
1053 /* BUGGGG... Beware! This expression suffer of
1054 * arithmetic overflows!
1056 if (cl
->priority
== prio
) {
1057 cl
->quantum
= (cl
->weight
*cl
->allot
*q
->nclasses
[prio
])/
1060 if (cl
->quantum
<= 0 || cl
->quantum
>32*qdisc_dev(cl
->qdisc
)->mtu
) {
1061 pr_warning("CBQ: class %08x has bad quantum==%ld, repaired.\n",
1062 cl
->common
.classid
, cl
->quantum
);
1063 cl
->quantum
= qdisc_dev(cl
->qdisc
)->mtu
/2 + 1;
1069 static void cbq_sync_defmap(struct cbq_class
*cl
)
1071 struct cbq_sched_data
*q
= qdisc_priv(cl
->qdisc
);
1072 struct cbq_class
*split
= cl
->split
;
1079 for (i
= 0; i
<= TC_PRIO_MAX
; i
++) {
1080 if (split
->defaults
[i
] == cl
&& !(cl
->defmap
& (1<<i
)))
1081 split
->defaults
[i
] = NULL
;
1084 for (i
= 0; i
<= TC_PRIO_MAX
; i
++) {
1085 int level
= split
->level
;
1087 if (split
->defaults
[i
])
1090 for (h
= 0; h
< q
->clhash
.hashsize
; h
++) {
1091 struct hlist_node
*n
;
1092 struct cbq_class
*c
;
1094 hlist_for_each_entry(c
, n
, &q
->clhash
.hash
[h
],
1096 if (c
->split
== split
&& c
->level
< level
&&
1097 c
->defmap
& (1<<i
)) {
1098 split
->defaults
[i
] = c
;
1106 static void cbq_change_defmap(struct cbq_class
*cl
, u32 splitid
, u32 def
, u32 mask
)
1108 struct cbq_class
*split
= NULL
;
1114 splitid
= split
->common
.classid
;
1117 if (split
== NULL
|| split
->common
.classid
!= splitid
) {
1118 for (split
= cl
->tparent
; split
; split
= split
->tparent
)
1119 if (split
->common
.classid
== splitid
)
1126 if (cl
->split
!= split
) {
1128 cbq_sync_defmap(cl
);
1130 cl
->defmap
= def
& mask
;
1132 cl
->defmap
= (cl
->defmap
& ~mask
) | (def
& mask
);
1134 cbq_sync_defmap(cl
);
1137 static void cbq_unlink_class(struct cbq_class
*this)
1139 struct cbq_class
*cl
, **clp
;
1140 struct cbq_sched_data
*q
= qdisc_priv(this->qdisc
);
1142 qdisc_class_hash_remove(&q
->clhash
, &this->common
);
1144 if (this->tparent
) {
1145 clp
= &this->sibling
;
1153 } while ((cl
= *clp
) != this->sibling
);
1155 if (this->tparent
->children
== this) {
1156 this->tparent
->children
= this->sibling
;
1157 if (this->sibling
== this)
1158 this->tparent
->children
= NULL
;
1161 WARN_ON(this->sibling
!= this);
1165 static void cbq_link_class(struct cbq_class
*this)
1167 struct cbq_sched_data
*q
= qdisc_priv(this->qdisc
);
1168 struct cbq_class
*parent
= this->tparent
;
1170 this->sibling
= this;
1171 qdisc_class_hash_insert(&q
->clhash
, &this->common
);
1176 if (parent
->children
== NULL
) {
1177 parent
->children
= this;
1179 this->sibling
= parent
->children
->sibling
;
1180 parent
->children
->sibling
= this;
1184 static unsigned int cbq_drop(struct Qdisc
*sch
)
1186 struct cbq_sched_data
*q
= qdisc_priv(sch
);
1187 struct cbq_class
*cl
, *cl_head
;
1191 for (prio
= TC_CBQ_MAXPRIO
; prio
>= 0; prio
--) {
1192 cl_head
= q
->active
[prio
];
1198 if (cl
->q
->ops
->drop
&& (len
= cl
->q
->ops
->drop(cl
->q
))) {
1201 cbq_deactivate_class(cl
);
1204 } while ((cl
= cl
->next_alive
) != cl_head
);
1210 cbq_reset(struct Qdisc
*sch
)
1212 struct cbq_sched_data
*q
= qdisc_priv(sch
);
1213 struct cbq_class
*cl
;
1214 struct hlist_node
*n
;
1221 q
->tx_borrowed
= NULL
;
1222 qdisc_watchdog_cancel(&q
->watchdog
);
1223 hrtimer_cancel(&q
->delay_timer
);
1224 q
->toplevel
= TC_CBQ_MAXLEVEL
;
1225 q
->now
= psched_get_time();
1228 for (prio
= 0; prio
<= TC_CBQ_MAXPRIO
; prio
++)
1229 q
->active
[prio
] = NULL
;
1231 for (h
= 0; h
< q
->clhash
.hashsize
; h
++) {
1232 hlist_for_each_entry(cl
, n
, &q
->clhash
.hash
[h
], common
.hnode
) {
1235 cl
->next_alive
= NULL
;
1236 cl
->undertime
= PSCHED_PASTPERFECT
;
1237 cl
->avgidle
= cl
->maxidle
;
1238 cl
->deficit
= cl
->quantum
;
1239 cl
->cpriority
= cl
->priority
;
1246 static int cbq_set_lss(struct cbq_class
*cl
, struct tc_cbq_lssopt
*lss
)
1248 if (lss
->change
& TCF_CBQ_LSS_FLAGS
) {
1249 cl
->share
= (lss
->flags
& TCF_CBQ_LSS_ISOLATED
) ? NULL
: cl
->tparent
;
1250 cl
->borrow
= (lss
->flags
& TCF_CBQ_LSS_BOUNDED
) ? NULL
: cl
->tparent
;
1252 if (lss
->change
& TCF_CBQ_LSS_EWMA
)
1253 cl
->ewma_log
= lss
->ewma_log
;
1254 if (lss
->change
& TCF_CBQ_LSS_AVPKT
)
1255 cl
->avpkt
= lss
->avpkt
;
1256 if (lss
->change
& TCF_CBQ_LSS_MINIDLE
)
1257 cl
->minidle
= -(long)lss
->minidle
;
1258 if (lss
->change
& TCF_CBQ_LSS_MAXIDLE
) {
1259 cl
->maxidle
= lss
->maxidle
;
1260 cl
->avgidle
= lss
->maxidle
;
1262 if (lss
->change
& TCF_CBQ_LSS_OFFTIME
)
1263 cl
->offtime
= lss
->offtime
;
1267 static void cbq_rmprio(struct cbq_sched_data
*q
, struct cbq_class
*cl
)
1269 q
->nclasses
[cl
->priority
]--;
1270 q
->quanta
[cl
->priority
] -= cl
->weight
;
1271 cbq_normalize_quanta(q
, cl
->priority
);
1274 static void cbq_addprio(struct cbq_sched_data
*q
, struct cbq_class
*cl
)
1276 q
->nclasses
[cl
->priority
]++;
1277 q
->quanta
[cl
->priority
] += cl
->weight
;
1278 cbq_normalize_quanta(q
, cl
->priority
);
1281 static int cbq_set_wrr(struct cbq_class
*cl
, struct tc_cbq_wrropt
*wrr
)
1283 struct cbq_sched_data
*q
= qdisc_priv(cl
->qdisc
);
1286 cl
->allot
= wrr
->allot
;
1288 cl
->weight
= wrr
->weight
;
1289 if (wrr
->priority
) {
1290 cl
->priority
= wrr
->priority
- 1;
1291 cl
->cpriority
= cl
->priority
;
1292 if (cl
->priority
>= cl
->priority2
)
1293 cl
->priority2
= TC_CBQ_MAXPRIO
- 1;
1300 static int cbq_set_overlimit(struct cbq_class
*cl
, struct tc_cbq_ovl
*ovl
)
1302 switch (ovl
->strategy
) {
1303 case TC_CBQ_OVL_CLASSIC
:
1304 cl
->overlimit
= cbq_ovl_classic
;
1306 case TC_CBQ_OVL_DELAY
:
1307 cl
->overlimit
= cbq_ovl_delay
;
1309 case TC_CBQ_OVL_LOWPRIO
:
1310 if (ovl
->priority2
- 1 >= TC_CBQ_MAXPRIO
||
1311 ovl
->priority2
- 1 <= cl
->priority
)
1313 cl
->priority2
= ovl
->priority2
- 1;
1314 cl
->overlimit
= cbq_ovl_lowprio
;
1316 case TC_CBQ_OVL_DROP
:
1317 cl
->overlimit
= cbq_ovl_drop
;
1319 case TC_CBQ_OVL_RCLASSIC
:
1320 cl
->overlimit
= cbq_ovl_rclassic
;
1325 cl
->penalty
= ovl
->penalty
;
1329 #ifdef CONFIG_NET_CLS_ACT
1330 static int cbq_set_police(struct cbq_class
*cl
, struct tc_cbq_police
*p
)
1332 cl
->police
= p
->police
;
1334 if (cl
->q
->handle
) {
1335 if (p
->police
== TC_POLICE_RECLASSIFY
)
1336 cl
->q
->reshape_fail
= cbq_reshape_fail
;
1338 cl
->q
->reshape_fail
= NULL
;
1344 static int cbq_set_fopt(struct cbq_class
*cl
, struct tc_cbq_fopt
*fopt
)
1346 cbq_change_defmap(cl
, fopt
->split
, fopt
->defmap
, fopt
->defchange
);
1350 static const struct nla_policy cbq_policy
[TCA_CBQ_MAX
+ 1] = {
1351 [TCA_CBQ_LSSOPT
] = { .len
= sizeof(struct tc_cbq_lssopt
) },
1352 [TCA_CBQ_WRROPT
] = { .len
= sizeof(struct tc_cbq_wrropt
) },
1353 [TCA_CBQ_FOPT
] = { .len
= sizeof(struct tc_cbq_fopt
) },
1354 [TCA_CBQ_OVL_STRATEGY
] = { .len
= sizeof(struct tc_cbq_ovl
) },
1355 [TCA_CBQ_RATE
] = { .len
= sizeof(struct tc_ratespec
) },
1356 [TCA_CBQ_RTAB
] = { .type
= NLA_BINARY
, .len
= TC_RTAB_SIZE
},
1357 [TCA_CBQ_POLICE
] = { .len
= sizeof(struct tc_cbq_police
) },
1360 static int cbq_init(struct Qdisc
*sch
, struct nlattr
*opt
)
1362 struct cbq_sched_data
*q
= qdisc_priv(sch
);
1363 struct nlattr
*tb
[TCA_CBQ_MAX
+ 1];
1364 struct tc_ratespec
*r
;
1367 err
= nla_parse_nested(tb
, TCA_CBQ_MAX
, opt
, cbq_policy
);
1371 if (tb
[TCA_CBQ_RTAB
] == NULL
|| tb
[TCA_CBQ_RATE
] == NULL
)
1374 r
= nla_data(tb
[TCA_CBQ_RATE
]);
1376 if ((q
->link
.R_tab
= qdisc_get_rtab(r
, tb
[TCA_CBQ_RTAB
])) == NULL
)
1379 err
= qdisc_class_hash_init(&q
->clhash
);
1384 q
->link
.sibling
= &q
->link
;
1385 q
->link
.common
.classid
= sch
->handle
;
1386 q
->link
.qdisc
= sch
;
1387 q
->link
.q
= qdisc_create_dflt(sch
->dev_queue
, &pfifo_qdisc_ops
,
1390 q
->link
.q
= &noop_qdisc
;
1392 q
->link
.priority
= TC_CBQ_MAXPRIO
- 1;
1393 q
->link
.priority2
= TC_CBQ_MAXPRIO
- 1;
1394 q
->link
.cpriority
= TC_CBQ_MAXPRIO
- 1;
1395 q
->link
.ovl_strategy
= TC_CBQ_OVL_CLASSIC
;
1396 q
->link
.overlimit
= cbq_ovl_classic
;
1397 q
->link
.allot
= psched_mtu(qdisc_dev(sch
));
1398 q
->link
.quantum
= q
->link
.allot
;
1399 q
->link
.weight
= q
->link
.R_tab
->rate
.rate
;
1401 q
->link
.ewma_log
= TC_CBQ_DEF_EWMA
;
1402 q
->link
.avpkt
= q
->link
.allot
/2;
1403 q
->link
.minidle
= -0x7FFFFFFF;
1405 qdisc_watchdog_init(&q
->watchdog
, sch
);
1406 hrtimer_init(&q
->delay_timer
, CLOCK_MONOTONIC
, HRTIMER_MODE_ABS
);
1407 q
->delay_timer
.function
= cbq_undelay
;
1408 q
->toplevel
= TC_CBQ_MAXLEVEL
;
1409 q
->now
= psched_get_time();
1412 cbq_link_class(&q
->link
);
1414 if (tb
[TCA_CBQ_LSSOPT
])
1415 cbq_set_lss(&q
->link
, nla_data(tb
[TCA_CBQ_LSSOPT
]));
1417 cbq_addprio(q
, &q
->link
);
1421 qdisc_put_rtab(q
->link
.R_tab
);
1425 static int cbq_dump_rate(struct sk_buff
*skb
, struct cbq_class
*cl
)
1427 unsigned char *b
= skb_tail_pointer(skb
);
1429 NLA_PUT(skb
, TCA_CBQ_RATE
, sizeof(cl
->R_tab
->rate
), &cl
->R_tab
->rate
);
1437 static int cbq_dump_lss(struct sk_buff
*skb
, struct cbq_class
*cl
)
1439 unsigned char *b
= skb_tail_pointer(skb
);
1440 struct tc_cbq_lssopt opt
;
1443 if (cl
->borrow
== NULL
)
1444 opt
.flags
|= TCF_CBQ_LSS_BOUNDED
;
1445 if (cl
->share
== NULL
)
1446 opt
.flags
|= TCF_CBQ_LSS_ISOLATED
;
1447 opt
.ewma_log
= cl
->ewma_log
;
1448 opt
.level
= cl
->level
;
1449 opt
.avpkt
= cl
->avpkt
;
1450 opt
.maxidle
= cl
->maxidle
;
1451 opt
.minidle
= (u32
)(-cl
->minidle
);
1452 opt
.offtime
= cl
->offtime
;
1454 NLA_PUT(skb
, TCA_CBQ_LSSOPT
, sizeof(opt
), &opt
);
1462 static int cbq_dump_wrr(struct sk_buff
*skb
, struct cbq_class
*cl
)
1464 unsigned char *b
= skb_tail_pointer(skb
);
1465 struct tc_cbq_wrropt opt
;
1468 opt
.allot
= cl
->allot
;
1469 opt
.priority
= cl
->priority
+ 1;
1470 opt
.cpriority
= cl
->cpriority
+ 1;
1471 opt
.weight
= cl
->weight
;
1472 NLA_PUT(skb
, TCA_CBQ_WRROPT
, sizeof(opt
), &opt
);
1480 static int cbq_dump_ovl(struct sk_buff
*skb
, struct cbq_class
*cl
)
1482 unsigned char *b
= skb_tail_pointer(skb
);
1483 struct tc_cbq_ovl opt
;
1485 opt
.strategy
= cl
->ovl_strategy
;
1486 opt
.priority2
= cl
->priority2
+ 1;
1488 opt
.penalty
= cl
->penalty
;
1489 NLA_PUT(skb
, TCA_CBQ_OVL_STRATEGY
, sizeof(opt
), &opt
);
1497 static int cbq_dump_fopt(struct sk_buff
*skb
, struct cbq_class
*cl
)
1499 unsigned char *b
= skb_tail_pointer(skb
);
1500 struct tc_cbq_fopt opt
;
1502 if (cl
->split
|| cl
->defmap
) {
1503 opt
.split
= cl
->split
? cl
->split
->common
.classid
: 0;
1504 opt
.defmap
= cl
->defmap
;
1506 NLA_PUT(skb
, TCA_CBQ_FOPT
, sizeof(opt
), &opt
);
1515 #ifdef CONFIG_NET_CLS_ACT
1516 static int cbq_dump_police(struct sk_buff
*skb
, struct cbq_class
*cl
)
1518 unsigned char *b
= skb_tail_pointer(skb
);
1519 struct tc_cbq_police opt
;
1522 opt
.police
= cl
->police
;
1525 NLA_PUT(skb
, TCA_CBQ_POLICE
, sizeof(opt
), &opt
);
1535 static int cbq_dump_attr(struct sk_buff
*skb
, struct cbq_class
*cl
)
1537 if (cbq_dump_lss(skb
, cl
) < 0 ||
1538 cbq_dump_rate(skb
, cl
) < 0 ||
1539 cbq_dump_wrr(skb
, cl
) < 0 ||
1540 cbq_dump_ovl(skb
, cl
) < 0 ||
1541 #ifdef CONFIG_NET_CLS_ACT
1542 cbq_dump_police(skb
, cl
) < 0 ||
1544 cbq_dump_fopt(skb
, cl
) < 0)
1549 static int cbq_dump(struct Qdisc
*sch
, struct sk_buff
*skb
)
1551 struct cbq_sched_data
*q
= qdisc_priv(sch
);
1552 struct nlattr
*nest
;
1554 nest
= nla_nest_start(skb
, TCA_OPTIONS
);
1556 goto nla_put_failure
;
1557 if (cbq_dump_attr(skb
, &q
->link
) < 0)
1558 goto nla_put_failure
;
1559 nla_nest_end(skb
, nest
);
1563 nla_nest_cancel(skb
, nest
);
1568 cbq_dump_stats(struct Qdisc
*sch
, struct gnet_dump
*d
)
1570 struct cbq_sched_data
*q
= qdisc_priv(sch
);
1572 q
->link
.xstats
.avgidle
= q
->link
.avgidle
;
1573 return gnet_stats_copy_app(d
, &q
->link
.xstats
, sizeof(q
->link
.xstats
));
1577 cbq_dump_class(struct Qdisc
*sch
, unsigned long arg
,
1578 struct sk_buff
*skb
, struct tcmsg
*tcm
)
1580 struct cbq_class
*cl
= (struct cbq_class
*)arg
;
1581 struct nlattr
*nest
;
1584 tcm
->tcm_parent
= cl
->tparent
->common
.classid
;
1586 tcm
->tcm_parent
= TC_H_ROOT
;
1587 tcm
->tcm_handle
= cl
->common
.classid
;
1588 tcm
->tcm_info
= cl
->q
->handle
;
1590 nest
= nla_nest_start(skb
, TCA_OPTIONS
);
1592 goto nla_put_failure
;
1593 if (cbq_dump_attr(skb
, cl
) < 0)
1594 goto nla_put_failure
;
1595 nla_nest_end(skb
, nest
);
1599 nla_nest_cancel(skb
, nest
);
1604 cbq_dump_class_stats(struct Qdisc
*sch
, unsigned long arg
,
1605 struct gnet_dump
*d
)
1607 struct cbq_sched_data
*q
= qdisc_priv(sch
);
1608 struct cbq_class
*cl
= (struct cbq_class
*)arg
;
1610 cl
->qstats
.qlen
= cl
->q
->q
.qlen
;
1611 cl
->xstats
.avgidle
= cl
->avgidle
;
1612 cl
->xstats
.undertime
= 0;
1614 if (cl
->undertime
!= PSCHED_PASTPERFECT
)
1615 cl
->xstats
.undertime
= cl
->undertime
- q
->now
;
1617 if (gnet_stats_copy_basic(d
, &cl
->bstats
) < 0 ||
1618 gnet_stats_copy_rate_est(d
, &cl
->bstats
, &cl
->rate_est
) < 0 ||
1619 gnet_stats_copy_queue(d
, &cl
->qstats
) < 0)
1622 return gnet_stats_copy_app(d
, &cl
->xstats
, sizeof(cl
->xstats
));
1625 static int cbq_graft(struct Qdisc
*sch
, unsigned long arg
, struct Qdisc
*new,
1628 struct cbq_class
*cl
= (struct cbq_class
*)arg
;
1631 new = qdisc_create_dflt(sch
->dev_queue
,
1632 &pfifo_qdisc_ops
, cl
->common
.classid
);
1636 #ifdef CONFIG_NET_CLS_ACT
1637 if (cl
->police
== TC_POLICE_RECLASSIFY
)
1638 new->reshape_fail
= cbq_reshape_fail
;
1644 qdisc_tree_decrease_qlen(*old
, (*old
)->q
.qlen
);
1646 sch_tree_unlock(sch
);
1651 static struct Qdisc
*cbq_leaf(struct Qdisc
*sch
, unsigned long arg
)
1653 struct cbq_class
*cl
= (struct cbq_class
*)arg
;
1658 static void cbq_qlen_notify(struct Qdisc
*sch
, unsigned long arg
)
1660 struct cbq_class
*cl
= (struct cbq_class
*)arg
;
1662 if (cl
->q
->q
.qlen
== 0)
1663 cbq_deactivate_class(cl
);
1666 static unsigned long cbq_get(struct Qdisc
*sch
, u32 classid
)
1668 struct cbq_sched_data
*q
= qdisc_priv(sch
);
1669 struct cbq_class
*cl
= cbq_class_lookup(q
, classid
);
1673 return (unsigned long)cl
;
1678 static void cbq_destroy_class(struct Qdisc
*sch
, struct cbq_class
*cl
)
1680 struct cbq_sched_data
*q
= qdisc_priv(sch
);
1682 WARN_ON(cl
->filters
);
1684 tcf_destroy_chain(&cl
->filter_list
);
1685 qdisc_destroy(cl
->q
);
1686 qdisc_put_rtab(cl
->R_tab
);
1687 gen_kill_estimator(&cl
->bstats
, &cl
->rate_est
);
1692 static void cbq_destroy(struct Qdisc
*sch
)
1694 struct cbq_sched_data
*q
= qdisc_priv(sch
);
1695 struct hlist_node
*n
, *next
;
1696 struct cbq_class
*cl
;
1699 #ifdef CONFIG_NET_CLS_ACT
1703 * Filters must be destroyed first because we don't destroy the
1704 * classes from root to leafs which means that filters can still
1705 * be bound to classes which have been destroyed already. --TGR '04
1707 for (h
= 0; h
< q
->clhash
.hashsize
; h
++) {
1708 hlist_for_each_entry(cl
, n
, &q
->clhash
.hash
[h
], common
.hnode
)
1709 tcf_destroy_chain(&cl
->filter_list
);
1711 for (h
= 0; h
< q
->clhash
.hashsize
; h
++) {
1712 hlist_for_each_entry_safe(cl
, n
, next
, &q
->clhash
.hash
[h
],
1714 cbq_destroy_class(sch
, cl
);
1716 qdisc_class_hash_destroy(&q
->clhash
);
1719 static void cbq_put(struct Qdisc
*sch
, unsigned long arg
)
1721 struct cbq_class
*cl
= (struct cbq_class
*)arg
;
1723 if (--cl
->refcnt
== 0) {
1724 #ifdef CONFIG_NET_CLS_ACT
1725 spinlock_t
*root_lock
= qdisc_root_sleeping_lock(sch
);
1726 struct cbq_sched_data
*q
= qdisc_priv(sch
);
1728 spin_lock_bh(root_lock
);
1729 if (q
->rx_class
== cl
)
1731 spin_unlock_bh(root_lock
);
1734 cbq_destroy_class(sch
, cl
);
1739 cbq_change_class(struct Qdisc
*sch
, u32 classid
, u32 parentid
, struct nlattr
**tca
,
1743 struct cbq_sched_data
*q
= qdisc_priv(sch
);
1744 struct cbq_class
*cl
= (struct cbq_class
*)*arg
;
1745 struct nlattr
*opt
= tca
[TCA_OPTIONS
];
1746 struct nlattr
*tb
[TCA_CBQ_MAX
+ 1];
1747 struct cbq_class
*parent
;
1748 struct qdisc_rate_table
*rtab
= NULL
;
1753 err
= nla_parse_nested(tb
, TCA_CBQ_MAX
, opt
, cbq_policy
);
1761 cl
->tparent
->common
.classid
!= parentid
)
1763 if (!cl
->tparent
&& parentid
!= TC_H_ROOT
)
1767 if (tb
[TCA_CBQ_RATE
]) {
1768 rtab
= qdisc_get_rtab(nla_data(tb
[TCA_CBQ_RATE
]),
1774 if (tca
[TCA_RATE
]) {
1775 err
= gen_replace_estimator(&cl
->bstats
, &cl
->rate_est
,
1776 qdisc_root_sleeping_lock(sch
),
1780 qdisc_put_rtab(rtab
);
1785 /* Change class parameters */
1788 if (cl
->next_alive
!= NULL
)
1789 cbq_deactivate_class(cl
);
1792 qdisc_put_rtab(cl
->R_tab
);
1796 if (tb
[TCA_CBQ_LSSOPT
])
1797 cbq_set_lss(cl
, nla_data(tb
[TCA_CBQ_LSSOPT
]));
1799 if (tb
[TCA_CBQ_WRROPT
]) {
1801 cbq_set_wrr(cl
, nla_data(tb
[TCA_CBQ_WRROPT
]));
1804 if (tb
[TCA_CBQ_OVL_STRATEGY
])
1805 cbq_set_overlimit(cl
, nla_data(tb
[TCA_CBQ_OVL_STRATEGY
]));
1807 #ifdef CONFIG_NET_CLS_ACT
1808 if (tb
[TCA_CBQ_POLICE
])
1809 cbq_set_police(cl
, nla_data(tb
[TCA_CBQ_POLICE
]));
1812 if (tb
[TCA_CBQ_FOPT
])
1813 cbq_set_fopt(cl
, nla_data(tb
[TCA_CBQ_FOPT
]));
1816 cbq_activate_class(cl
);
1818 sch_tree_unlock(sch
);
1823 if (parentid
== TC_H_ROOT
)
1826 if (tb
[TCA_CBQ_WRROPT
] == NULL
|| tb
[TCA_CBQ_RATE
] == NULL
||
1827 tb
[TCA_CBQ_LSSOPT
] == NULL
)
1830 rtab
= qdisc_get_rtab(nla_data(tb
[TCA_CBQ_RATE
]), tb
[TCA_CBQ_RTAB
]);
1836 if (TC_H_MAJ(classid
^ sch
->handle
) ||
1837 cbq_class_lookup(q
, classid
))
1841 classid
= TC_H_MAKE(sch
->handle
, 0x8000);
1843 for (i
= 0; i
< 0x8000; i
++) {
1844 if (++q
->hgenerator
>= 0x8000)
1846 if (cbq_class_lookup(q
, classid
|q
->hgenerator
) == NULL
)
1852 classid
= classid
|q
->hgenerator
;
1857 parent
= cbq_class_lookup(q
, parentid
);
1864 cl
= kzalloc(sizeof(*cl
), GFP_KERNEL
);
1868 if (tca
[TCA_RATE
]) {
1869 err
= gen_new_estimator(&cl
->bstats
, &cl
->rate_est
,
1870 qdisc_root_sleeping_lock(sch
),
1881 cl
->q
= qdisc_create_dflt(sch
->dev_queue
, &pfifo_qdisc_ops
, classid
);
1883 cl
->q
= &noop_qdisc
;
1884 cl
->common
.classid
= classid
;
1885 cl
->tparent
= parent
;
1887 cl
->allot
= parent
->allot
;
1888 cl
->quantum
= cl
->allot
;
1889 cl
->weight
= cl
->R_tab
->rate
.rate
;
1893 cl
->borrow
= cl
->tparent
;
1894 if (cl
->tparent
!= &q
->link
)
1895 cl
->share
= cl
->tparent
;
1896 cbq_adjust_levels(parent
);
1897 cl
->minidle
= -0x7FFFFFFF;
1898 cbq_set_lss(cl
, nla_data(tb
[TCA_CBQ_LSSOPT
]));
1899 cbq_set_wrr(cl
, nla_data(tb
[TCA_CBQ_WRROPT
]));
1900 if (cl
->ewma_log
== 0)
1901 cl
->ewma_log
= q
->link
.ewma_log
;
1902 if (cl
->maxidle
== 0)
1903 cl
->maxidle
= q
->link
.maxidle
;
1905 cl
->avpkt
= q
->link
.avpkt
;
1906 cl
->overlimit
= cbq_ovl_classic
;
1907 if (tb
[TCA_CBQ_OVL_STRATEGY
])
1908 cbq_set_overlimit(cl
, nla_data(tb
[TCA_CBQ_OVL_STRATEGY
]));
1909 #ifdef CONFIG_NET_CLS_ACT
1910 if (tb
[TCA_CBQ_POLICE
])
1911 cbq_set_police(cl
, nla_data(tb
[TCA_CBQ_POLICE
]));
1913 if (tb
[TCA_CBQ_FOPT
])
1914 cbq_set_fopt(cl
, nla_data(tb
[TCA_CBQ_FOPT
]));
1915 sch_tree_unlock(sch
);
1917 qdisc_class_hash_grow(sch
, &q
->clhash
);
1919 *arg
= (unsigned long)cl
;
1923 qdisc_put_rtab(rtab
);
1927 static int cbq_delete(struct Qdisc
*sch
, unsigned long arg
)
1929 struct cbq_sched_data
*q
= qdisc_priv(sch
);
1930 struct cbq_class
*cl
= (struct cbq_class
*)arg
;
1933 if (cl
->filters
|| cl
->children
|| cl
== &q
->link
)
1938 qlen
= cl
->q
->q
.qlen
;
1940 qdisc_tree_decrease_qlen(cl
->q
, qlen
);
1943 cbq_deactivate_class(cl
);
1945 if (q
->tx_borrowed
== cl
)
1946 q
->tx_borrowed
= q
->tx_class
;
1947 if (q
->tx_class
== cl
) {
1949 q
->tx_borrowed
= NULL
;
1951 #ifdef CONFIG_NET_CLS_ACT
1952 if (q
->rx_class
== cl
)
1956 cbq_unlink_class(cl
);
1957 cbq_adjust_levels(cl
->tparent
);
1959 cbq_sync_defmap(cl
);
1962 sch_tree_unlock(sch
);
1964 BUG_ON(--cl
->refcnt
== 0);
1966 * This shouldn't happen: we "hold" one cops->get() when called
1967 * from tc_ctl_tclass; the destroy method is done from cops->put().
1973 static struct tcf_proto
**cbq_find_tcf(struct Qdisc
*sch
, unsigned long arg
)
1975 struct cbq_sched_data
*q
= qdisc_priv(sch
);
1976 struct cbq_class
*cl
= (struct cbq_class
*)arg
;
1981 return &cl
->filter_list
;
1984 static unsigned long cbq_bind_filter(struct Qdisc
*sch
, unsigned long parent
,
1987 struct cbq_sched_data
*q
= qdisc_priv(sch
);
1988 struct cbq_class
*p
= (struct cbq_class
*)parent
;
1989 struct cbq_class
*cl
= cbq_class_lookup(q
, classid
);
1992 if (p
&& p
->level
<= cl
->level
)
1995 return (unsigned long)cl
;
2000 static void cbq_unbind_filter(struct Qdisc
*sch
, unsigned long arg
)
2002 struct cbq_class
*cl
= (struct cbq_class
*)arg
;
2007 static void cbq_walk(struct Qdisc
*sch
, struct qdisc_walker
*arg
)
2009 struct cbq_sched_data
*q
= qdisc_priv(sch
);
2010 struct cbq_class
*cl
;
2011 struct hlist_node
*n
;
2017 for (h
= 0; h
< q
->clhash
.hashsize
; h
++) {
2018 hlist_for_each_entry(cl
, n
, &q
->clhash
.hash
[h
], common
.hnode
) {
2019 if (arg
->count
< arg
->skip
) {
2023 if (arg
->fn(sch
, (unsigned long)cl
, arg
) < 0) {
2032 static const struct Qdisc_class_ops cbq_class_ops
= {
2035 .qlen_notify
= cbq_qlen_notify
,
2038 .change
= cbq_change_class
,
2039 .delete = cbq_delete
,
2041 .tcf_chain
= cbq_find_tcf
,
2042 .bind_tcf
= cbq_bind_filter
,
2043 .unbind_tcf
= cbq_unbind_filter
,
2044 .dump
= cbq_dump_class
,
2045 .dump_stats
= cbq_dump_class_stats
,
2048 static struct Qdisc_ops cbq_qdisc_ops __read_mostly
= {
2050 .cl_ops
= &cbq_class_ops
,
2052 .priv_size
= sizeof(struct cbq_sched_data
),
2053 .enqueue
= cbq_enqueue
,
2054 .dequeue
= cbq_dequeue
,
2055 .peek
= qdisc_peek_dequeued
,
2059 .destroy
= cbq_destroy
,
2062 .dump_stats
= cbq_dump_stats
,
2063 .owner
= THIS_MODULE
,
2066 static int __init
cbq_module_init(void)
2068 return register_qdisc(&cbq_qdisc_ops
);
2070 static void __exit
cbq_module_exit(void)
2072 unregister_qdisc(&cbq_qdisc_ops
);
2074 module_init(cbq_module_init
)
2075 module_exit(cbq_module_exit
)
2076 MODULE_LICENSE("GPL");