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_est64 rate_est;
134 struct tc_cbq_xstats xstats;
136 struct tcf_proto __rcu *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 */
164 struct hrtimer delay_timer;
165 struct qdisc_watchdog watchdog; /* Watchdog timer,
169 psched_tdiff_t wd_expires;
175 #define L2T(cl, len) qdisc_l2t((cl)->R_tab, len)
177 static inline struct cbq_class *
178 cbq_class_lookup(struct cbq_sched_data *q, u32 classid)
180 struct Qdisc_class_common *clc;
182 clc = qdisc_class_find(&q->clhash, classid);
185 return container_of(clc, struct cbq_class, common);
188 #ifdef CONFIG_NET_CLS_ACT
190 static struct cbq_class *
191 cbq_reclassify(struct sk_buff *skb, struct cbq_class *this)
193 struct cbq_class *cl;
195 for (cl = this->tparent; cl; cl = cl->tparent) {
196 struct cbq_class *new = cl->defaults[TC_PRIO_BESTEFFORT];
198 if (new != NULL && new != this)
206 /* Classify packet. The procedure is pretty complicated, but
207 * it allows us to combine link sharing and priority scheduling
210 * Namely, you can put link sharing rules (f.e. route based) at root of CBQ,
211 * so that it resolves to split nodes. Then packets are classified
212 * by logical priority, or a more specific classifier may be attached
216 static struct cbq_class *
217 cbq_classify(struct sk_buff *skb, struct Qdisc *sch, int *qerr)
219 struct cbq_sched_data *q = qdisc_priv(sch);
220 struct cbq_class *head = &q->link;
221 struct cbq_class **defmap;
222 struct cbq_class *cl = NULL;
223 u32 prio = skb->priority;
224 struct tcf_proto *fl;
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;
239 fl = rcu_dereference_bh(head->filter_list);
241 * Step 2+n. Apply classifier.
243 result = tc_classify(skb, fl, &res, true);
244 if (!fl || result < 0)
247 cl = (void *)res.class;
249 if (TC_H_MAJ(res.classid))
250 cl = cbq_class_lookup(q, res.classid);
251 else if ((cl = defmap[res.classid & TC_PRIO_MAX]) == NULL)
252 cl = defmap[TC_PRIO_BESTEFFORT];
257 if (cl->level >= head->level)
259 #ifdef CONFIG_NET_CLS_ACT
263 *qerr = NET_XMIT_SUCCESS | __NET_XMIT_STOLEN;
266 case TC_ACT_RECLASSIFY:
267 return cbq_reclassify(skb, cl);
274 * Step 3+n. If classifier selected a link sharing class,
275 * apply agency specific classifier.
276 * Repeat this procdure until we hit a leaf node.
285 * Step 4. No success...
287 if (TC_H_MAJ(prio) == 0 &&
288 !(cl = head->defaults[prio & TC_PRIO_MAX]) &&
289 !(cl = head->defaults[TC_PRIO_BESTEFFORT]))
296 * A packet has just been enqueued on the empty class.
297 * cbq_activate_class adds it to the tail of active class list
298 * of its priority band.
301 static inline void cbq_activate_class(struct cbq_class *cl)
303 struct cbq_sched_data *q = qdisc_priv(cl->qdisc);
304 int prio = cl->cpriority;
305 struct cbq_class *cl_tail;
307 cl_tail = q->active[prio];
308 q->active[prio] = cl;
310 if (cl_tail != NULL) {
311 cl->next_alive = cl_tail->next_alive;
312 cl_tail->next_alive = cl;
315 q->activemask |= (1<<prio);
320 * Unlink class from active chain.
321 * Note that this same procedure is done directly in cbq_dequeue*
322 * during round-robin procedure.
325 static void cbq_deactivate_class(struct cbq_class *this)
327 struct cbq_sched_data *q = qdisc_priv(this->qdisc);
328 int prio = this->cpriority;
329 struct cbq_class *cl;
330 struct cbq_class *cl_prev = q->active[prio];
333 cl = cl_prev->next_alive;
335 cl_prev->next_alive = cl->next_alive;
336 cl->next_alive = NULL;
338 if (cl == q->active[prio]) {
339 q->active[prio] = cl_prev;
340 if (cl == q->active[prio]) {
341 q->active[prio] = NULL;
342 q->activemask &= ~(1<<prio);
348 } while ((cl_prev = cl) != q->active[prio]);
352 cbq_mark_toplevel(struct cbq_sched_data *q, struct cbq_class *cl)
354 int toplevel = q->toplevel;
356 if (toplevel > cl->level && !(qdisc_is_throttled(cl->q))) {
357 psched_time_t now = psched_get_time();
360 if (cl->undertime < now) {
361 q->toplevel = cl->level;
364 } while ((cl = cl->borrow) != NULL && toplevel > cl->level);
369 cbq_enqueue(struct sk_buff *skb, struct Qdisc *sch)
371 struct cbq_sched_data *q = qdisc_priv(sch);
372 int uninitialized_var(ret);
373 struct cbq_class *cl = cbq_classify(skb, sch, &ret);
375 #ifdef CONFIG_NET_CLS_ACT
379 if (ret & __NET_XMIT_BYPASS)
380 qdisc_qstats_drop(sch);
385 #ifdef CONFIG_NET_CLS_ACT
386 cl->q->__parent = sch;
388 ret = qdisc_enqueue(skb, cl->q);
389 if (ret == NET_XMIT_SUCCESS) {
391 cbq_mark_toplevel(q, cl);
393 cbq_activate_class(cl);
397 if (net_xmit_drop_count(ret)) {
398 qdisc_qstats_drop(sch);
399 cbq_mark_toplevel(q, cl);
405 /* Overlimit actions */
407 /* TC_CBQ_OVL_CLASSIC: (default) penalize leaf class by adding offtime */
409 static void cbq_ovl_classic(struct cbq_class *cl)
411 struct cbq_sched_data *q = qdisc_priv(cl->qdisc);
412 psched_tdiff_t delay = cl->undertime - q->now;
415 delay += cl->offtime;
418 * Class goes to sleep, so that it will have no
419 * chance to work avgidle. Let's forgive it 8)
421 * BTW cbq-2.0 has a crap in this
422 * place, apparently they forgot to shift it by cl->ewma_log.
425 delay -= (-cl->avgidle) - ((-cl->avgidle) >> cl->ewma_log);
426 if (cl->avgidle < cl->minidle)
427 cl->avgidle = cl->minidle;
430 cl->undertime = q->now + delay;
432 cl->xstats.overactions++;
435 if (q->wd_expires == 0 || q->wd_expires > delay)
436 q->wd_expires = delay;
438 /* Dirty work! We must schedule wakeups based on
439 * real available rate, rather than leaf rate,
440 * which may be tiny (even zero).
442 if (q->toplevel == TC_CBQ_MAXLEVEL) {
444 psched_tdiff_t base_delay = q->wd_expires;
446 for (b = cl->borrow; b; b = b->borrow) {
447 delay = b->undertime - q->now;
448 if (delay < base_delay) {
455 q->wd_expires = base_delay;
459 /* TC_CBQ_OVL_RCLASSIC: penalize by offtime classes in hierarchy, when
463 static void cbq_ovl_rclassic(struct cbq_class *cl)
465 struct cbq_sched_data *q = qdisc_priv(cl->qdisc);
466 struct cbq_class *this = cl;
469 if (cl->level > q->toplevel) {
473 } while ((cl = cl->borrow) != NULL);
480 /* TC_CBQ_OVL_DELAY: delay until it will go to underlimit */
482 static void cbq_ovl_delay(struct cbq_class *cl)
484 struct cbq_sched_data *q = qdisc_priv(cl->qdisc);
485 psched_tdiff_t delay = cl->undertime - q->now;
487 if (test_bit(__QDISC_STATE_DEACTIVATED,
488 &qdisc_root_sleeping(cl->qdisc)->state))
492 psched_time_t sched = q->now;
495 delay += cl->offtime;
497 delay -= (-cl->avgidle) - ((-cl->avgidle) >> cl->ewma_log);
498 if (cl->avgidle < cl->minidle)
499 cl->avgidle = cl->minidle;
500 cl->undertime = q->now + delay;
503 sched += delay + cl->penalty;
504 cl->penalized = sched;
505 cl->cpriority = TC_CBQ_MAXPRIO;
506 q->pmask |= (1<<TC_CBQ_MAXPRIO);
508 expires = ns_to_ktime(PSCHED_TICKS2NS(sched));
509 if (hrtimer_try_to_cancel(&q->delay_timer) &&
510 ktime_to_ns(ktime_sub(
511 hrtimer_get_expires(&q->delay_timer),
513 hrtimer_set_expires(&q->delay_timer, expires);
514 hrtimer_restart(&q->delay_timer);
516 cl->xstats.overactions++;
521 if (q->wd_expires == 0 || q->wd_expires > delay)
522 q->wd_expires = delay;
525 /* TC_CBQ_OVL_LOWPRIO: penalize class by lowering its priority band */
527 static void cbq_ovl_lowprio(struct cbq_class *cl)
529 struct cbq_sched_data *q = qdisc_priv(cl->qdisc);
531 cl->penalized = q->now + cl->penalty;
533 if (cl->cpriority != cl->priority2) {
534 cl->cpriority = cl->priority2;
535 q->pmask |= (1<<cl->cpriority);
536 cl->xstats.overactions++;
541 /* TC_CBQ_OVL_DROP: penalize class by dropping */
543 static void cbq_ovl_drop(struct cbq_class *cl)
545 if (cl->q->ops->drop)
546 if (cl->q->ops->drop(cl->q))
548 cl->xstats.overactions++;
552 static psched_tdiff_t cbq_undelay_prio(struct cbq_sched_data *q, int prio,
555 struct cbq_class *cl;
556 struct cbq_class *cl_prev = q->active[prio];
557 psched_time_t sched = now;
563 cl = cl_prev->next_alive;
564 if (now - cl->penalized > 0) {
565 cl_prev->next_alive = cl->next_alive;
566 cl->next_alive = NULL;
567 cl->cpriority = cl->priority;
569 cbq_activate_class(cl);
571 if (cl == q->active[prio]) {
572 q->active[prio] = cl_prev;
573 if (cl == q->active[prio]) {
574 q->active[prio] = NULL;
579 cl = cl_prev->next_alive;
580 } else if (sched - cl->penalized > 0)
581 sched = cl->penalized;
582 } while ((cl_prev = cl) != q->active[prio]);
587 static enum hrtimer_restart cbq_undelay(struct hrtimer *timer)
589 struct cbq_sched_data *q = container_of(timer, struct cbq_sched_data,
591 struct Qdisc *sch = q->watchdog.qdisc;
593 psched_tdiff_t delay = 0;
596 now = psched_get_time();
602 int prio = ffz(~pmask);
607 tmp = cbq_undelay_prio(q, prio, now);
610 if (tmp < delay || delay == 0)
618 time = ktime_set(0, 0);
619 time = ktime_add_ns(time, PSCHED_TICKS2NS(now + delay));
620 hrtimer_start(&q->delay_timer, time, HRTIMER_MODE_ABS_PINNED);
623 qdisc_unthrottled(sch);
624 __netif_schedule(qdisc_root(sch));
625 return HRTIMER_NORESTART;
628 #ifdef CONFIG_NET_CLS_ACT
629 static int cbq_reshape_fail(struct sk_buff *skb, struct Qdisc *child)
631 struct Qdisc *sch = child->__parent;
632 struct cbq_sched_data *q = qdisc_priv(sch);
633 struct cbq_class *cl = q->rx_class;
637 if (cl && (cl = cbq_reclassify(skb, cl)) != NULL) {
640 cbq_mark_toplevel(q, cl);
643 cl->q->__parent = sch;
645 ret = qdisc_enqueue(skb, cl->q);
646 if (ret == NET_XMIT_SUCCESS) {
649 cbq_activate_class(cl);
652 if (net_xmit_drop_count(ret))
653 qdisc_qstats_drop(sch);
657 qdisc_qstats_drop(sch);
663 * It is mission critical procedure.
665 * We "regenerate" toplevel cutoff, if transmitting class
666 * has backlog and it is not regulated. It is not part of
667 * original CBQ description, but looks more reasonable.
668 * Probably, it is wrong. This question needs further investigation.
672 cbq_update_toplevel(struct cbq_sched_data *q, struct cbq_class *cl,
673 struct cbq_class *borrowed)
675 if (cl && q->toplevel >= borrowed->level) {
676 if (cl->q->q.qlen > 1) {
678 if (borrowed->undertime == PSCHED_PASTPERFECT) {
679 q->toplevel = borrowed->level;
682 } while ((borrowed = borrowed->borrow) != NULL);
685 /* It is not necessary now. Uncommenting it
686 will save CPU cycles, but decrease fairness.
688 q->toplevel = TC_CBQ_MAXLEVEL;
694 cbq_update(struct cbq_sched_data *q)
696 struct cbq_class *this = q->tx_class;
697 struct cbq_class *cl = this;
702 /* Time integrator. We calculate EOS time
703 * by adding expected packet transmission time.
705 now = q->now + L2T(&q->link, len);
707 for ( ; cl; cl = cl->share) {
708 long avgidle = cl->avgidle;
711 cl->bstats.packets++;
712 cl->bstats.bytes += len;
715 * (now - last) is total time between packet right edges.
716 * (last_pktlen/rate) is "virtual" busy time, so that
718 * idle = (now - last) - last_pktlen/rate
721 idle = now - cl->last;
722 if ((unsigned long)idle > 128*1024*1024) {
723 avgidle = cl->maxidle;
725 idle -= L2T(cl, len);
727 /* true_avgidle := (1-W)*true_avgidle + W*idle,
728 * where W=2^{-ewma_log}. But cl->avgidle is scaled:
729 * cl->avgidle == true_avgidle/W,
732 avgidle += idle - (avgidle>>cl->ewma_log);
736 /* Overlimit or at-limit */
738 if (avgidle < cl->minidle)
739 avgidle = cl->minidle;
741 cl->avgidle = avgidle;
743 /* Calculate expected time, when this class
744 * will be allowed to send.
745 * It will occur, when:
746 * (1-W)*true_avgidle + W*delay = 0, i.e.
747 * idle = (1/W - 1)*(-true_avgidle)
749 * idle = (1 - W)*(-cl->avgidle);
751 idle = (-avgidle) - ((-avgidle) >> cl->ewma_log);
755 * To maintain the rate allocated to the class,
756 * we add to undertime virtual clock,
757 * necessary to complete transmitted packet.
758 * (len/phys_bandwidth has been already passed
759 * to the moment of cbq_update)
762 idle -= L2T(&q->link, len);
763 idle += L2T(cl, len);
765 cl->undertime = now + idle;
769 cl->undertime = PSCHED_PASTPERFECT;
770 if (avgidle > cl->maxidle)
771 cl->avgidle = cl->maxidle;
773 cl->avgidle = avgidle;
775 if ((s64)(now - cl->last) > 0)
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);
949 now = psched_get_time();
959 skb = cbq_dequeue_1(sch);
961 qdisc_bstats_update(sch, skb);
963 qdisc_unthrottled(sch);
967 /* All the classes are overlimit.
969 * It is possible, if:
971 * 1. Scheduler is empty.
972 * 2. Toplevel cutoff inhibited borrowing.
973 * 3. Root class is overlimit.
975 * Reset 2d and 3d conditions and retry.
977 * Note, that NS and cbq-2.0 are buggy, peeking
978 * an arbitrary class is appropriate for ancestor-only
979 * sharing, but not for toplevel algorithm.
981 * Our version is better, but slower, because it requires
982 * two passes, but it is unavoidable with top-level sharing.
985 if (q->toplevel == TC_CBQ_MAXLEVEL &&
986 q->link.undertime == PSCHED_PASTPERFECT)
989 q->toplevel = TC_CBQ_MAXLEVEL;
990 q->link.undertime = PSCHED_PASTPERFECT;
993 /* No packets in scheduler or nobody wants to give them to us :-(
994 * Sigh... start watchdog timer in the last case.
998 qdisc_qstats_overlimit(sch);
1000 qdisc_watchdog_schedule(&q->watchdog,
1001 now + q->wd_expires);
1006 /* CBQ class maintanance routines */
1008 static void cbq_adjust_levels(struct cbq_class *this)
1015 struct cbq_class *cl;
1017 cl = this->children;
1020 if (cl->level > level)
1022 } while ((cl = cl->sibling) != this->children);
1024 this->level = level + 1;
1025 } while ((this = this->tparent) != NULL);
1028 static void cbq_normalize_quanta(struct cbq_sched_data *q, int prio)
1030 struct cbq_class *cl;
1033 if (q->quanta[prio] == 0)
1036 for (h = 0; h < q->clhash.hashsize; h++) {
1037 hlist_for_each_entry(cl, &q->clhash.hash[h], common.hnode) {
1038 /* BUGGGG... Beware! This expression suffer of
1039 * arithmetic overflows!
1041 if (cl->priority == prio) {
1042 cl->quantum = (cl->weight*cl->allot*q->nclasses[prio])/
1045 if (cl->quantum <= 0 ||
1046 cl->quantum > 32*qdisc_dev(cl->qdisc)->mtu) {
1047 pr_warn("CBQ: class %08x has bad quantum==%ld, repaired.\n",
1048 cl->common.classid, cl->quantum);
1049 cl->quantum = qdisc_dev(cl->qdisc)->mtu/2 + 1;
1055 static void cbq_sync_defmap(struct cbq_class *cl)
1057 struct cbq_sched_data *q = qdisc_priv(cl->qdisc);
1058 struct cbq_class *split = cl->split;
1065 for (i = 0; i <= TC_PRIO_MAX; i++) {
1066 if (split->defaults[i] == cl && !(cl->defmap & (1<<i)))
1067 split->defaults[i] = NULL;
1070 for (i = 0; i <= TC_PRIO_MAX; i++) {
1071 int level = split->level;
1073 if (split->defaults[i])
1076 for (h = 0; h < q->clhash.hashsize; h++) {
1077 struct cbq_class *c;
1079 hlist_for_each_entry(c, &q->clhash.hash[h],
1081 if (c->split == split && c->level < level &&
1082 c->defmap & (1<<i)) {
1083 split->defaults[i] = c;
1091 static void cbq_change_defmap(struct cbq_class *cl, u32 splitid, u32 def, u32 mask)
1093 struct cbq_class *split = NULL;
1099 splitid = split->common.classid;
1102 if (split == NULL || split->common.classid != splitid) {
1103 for (split = cl->tparent; split; split = split->tparent)
1104 if (split->common.classid == splitid)
1111 if (cl->split != split) {
1113 cbq_sync_defmap(cl);
1115 cl->defmap = def & mask;
1117 cl->defmap = (cl->defmap & ~mask) | (def & mask);
1119 cbq_sync_defmap(cl);
1122 static void cbq_unlink_class(struct cbq_class *this)
1124 struct cbq_class *cl, **clp;
1125 struct cbq_sched_data *q = qdisc_priv(this->qdisc);
1127 qdisc_class_hash_remove(&q->clhash, &this->common);
1129 if (this->tparent) {
1130 clp = &this->sibling;
1138 } while ((cl = *clp) != this->sibling);
1140 if (this->tparent->children == this) {
1141 this->tparent->children = this->sibling;
1142 if (this->sibling == this)
1143 this->tparent->children = NULL;
1146 WARN_ON(this->sibling != this);
1150 static void cbq_link_class(struct cbq_class *this)
1152 struct cbq_sched_data *q = qdisc_priv(this->qdisc);
1153 struct cbq_class *parent = this->tparent;
1155 this->sibling = this;
1156 qdisc_class_hash_insert(&q->clhash, &this->common);
1161 if (parent->children == NULL) {
1162 parent->children = this;
1164 this->sibling = parent->children->sibling;
1165 parent->children->sibling = this;
1169 static unsigned int cbq_drop(struct Qdisc *sch)
1171 struct cbq_sched_data *q = qdisc_priv(sch);
1172 struct cbq_class *cl, *cl_head;
1176 for (prio = TC_CBQ_MAXPRIO; prio >= 0; prio--) {
1177 cl_head = q->active[prio];
1183 if (cl->q->ops->drop && (len = cl->q->ops->drop(cl->q))) {
1186 cbq_deactivate_class(cl);
1189 } while ((cl = cl->next_alive) != cl_head);
1195 cbq_reset(struct Qdisc *sch)
1197 struct cbq_sched_data *q = qdisc_priv(sch);
1198 struct cbq_class *cl;
1205 q->tx_borrowed = NULL;
1206 qdisc_watchdog_cancel(&q->watchdog);
1207 hrtimer_cancel(&q->delay_timer);
1208 q->toplevel = TC_CBQ_MAXLEVEL;
1209 q->now = psched_get_time();
1211 for (prio = 0; prio <= TC_CBQ_MAXPRIO; prio++)
1212 q->active[prio] = NULL;
1214 for (h = 0; h < q->clhash.hashsize; h++) {
1215 hlist_for_each_entry(cl, &q->clhash.hash[h], common.hnode) {
1218 cl->next_alive = NULL;
1219 cl->undertime = PSCHED_PASTPERFECT;
1220 cl->avgidle = cl->maxidle;
1221 cl->deficit = cl->quantum;
1222 cl->cpriority = cl->priority;
1229 static int cbq_set_lss(struct cbq_class *cl, struct tc_cbq_lssopt *lss)
1231 if (lss->change & TCF_CBQ_LSS_FLAGS) {
1232 cl->share = (lss->flags & TCF_CBQ_LSS_ISOLATED) ? NULL : cl->tparent;
1233 cl->borrow = (lss->flags & TCF_CBQ_LSS_BOUNDED) ? NULL : cl->tparent;
1235 if (lss->change & TCF_CBQ_LSS_EWMA)
1236 cl->ewma_log = lss->ewma_log;
1237 if (lss->change & TCF_CBQ_LSS_AVPKT)
1238 cl->avpkt = lss->avpkt;
1239 if (lss->change & TCF_CBQ_LSS_MINIDLE)
1240 cl->minidle = -(long)lss->minidle;
1241 if (lss->change & TCF_CBQ_LSS_MAXIDLE) {
1242 cl->maxidle = lss->maxidle;
1243 cl->avgidle = lss->maxidle;
1245 if (lss->change & TCF_CBQ_LSS_OFFTIME)
1246 cl->offtime = lss->offtime;
1250 static void cbq_rmprio(struct cbq_sched_data *q, struct cbq_class *cl)
1252 q->nclasses[cl->priority]--;
1253 q->quanta[cl->priority] -= cl->weight;
1254 cbq_normalize_quanta(q, cl->priority);
1257 static void cbq_addprio(struct cbq_sched_data *q, struct cbq_class *cl)
1259 q->nclasses[cl->priority]++;
1260 q->quanta[cl->priority] += cl->weight;
1261 cbq_normalize_quanta(q, cl->priority);
1264 static int cbq_set_wrr(struct cbq_class *cl, struct tc_cbq_wrropt *wrr)
1266 struct cbq_sched_data *q = qdisc_priv(cl->qdisc);
1269 cl->allot = wrr->allot;
1271 cl->weight = wrr->weight;
1272 if (wrr->priority) {
1273 cl->priority = wrr->priority - 1;
1274 cl->cpriority = cl->priority;
1275 if (cl->priority >= cl->priority2)
1276 cl->priority2 = TC_CBQ_MAXPRIO - 1;
1283 static int cbq_set_overlimit(struct cbq_class *cl, struct tc_cbq_ovl *ovl)
1285 switch (ovl->strategy) {
1286 case TC_CBQ_OVL_CLASSIC:
1287 cl->overlimit = cbq_ovl_classic;
1289 case TC_CBQ_OVL_DELAY:
1290 cl->overlimit = cbq_ovl_delay;
1292 case TC_CBQ_OVL_LOWPRIO:
1293 if (ovl->priority2 - 1 >= TC_CBQ_MAXPRIO ||
1294 ovl->priority2 - 1 <= cl->priority)
1296 cl->priority2 = ovl->priority2 - 1;
1297 cl->overlimit = cbq_ovl_lowprio;
1299 case TC_CBQ_OVL_DROP:
1300 cl->overlimit = cbq_ovl_drop;
1302 case TC_CBQ_OVL_RCLASSIC:
1303 cl->overlimit = cbq_ovl_rclassic;
1308 cl->penalty = ovl->penalty;
1312 #ifdef CONFIG_NET_CLS_ACT
1313 static int cbq_set_police(struct cbq_class *cl, struct tc_cbq_police *p)
1315 cl->police = p->police;
1317 if (cl->q->handle) {
1318 if (p->police == TC_POLICE_RECLASSIFY)
1319 cl->q->reshape_fail = cbq_reshape_fail;
1321 cl->q->reshape_fail = NULL;
1327 static int cbq_set_fopt(struct cbq_class *cl, struct tc_cbq_fopt *fopt)
1329 cbq_change_defmap(cl, fopt->split, fopt->defmap, fopt->defchange);
1333 static const struct nla_policy cbq_policy[TCA_CBQ_MAX + 1] = {
1334 [TCA_CBQ_LSSOPT] = { .len = sizeof(struct tc_cbq_lssopt) },
1335 [TCA_CBQ_WRROPT] = { .len = sizeof(struct tc_cbq_wrropt) },
1336 [TCA_CBQ_FOPT] = { .len = sizeof(struct tc_cbq_fopt) },
1337 [TCA_CBQ_OVL_STRATEGY] = { .len = sizeof(struct tc_cbq_ovl) },
1338 [TCA_CBQ_RATE] = { .len = sizeof(struct tc_ratespec) },
1339 [TCA_CBQ_RTAB] = { .type = NLA_BINARY, .len = TC_RTAB_SIZE },
1340 [TCA_CBQ_POLICE] = { .len = sizeof(struct tc_cbq_police) },
1343 static int cbq_opt_parse(struct nlattr *tb[TCA_CBQ_MAX + 1], struct nlattr *opt)
1350 err = nla_parse_nested(tb, TCA_CBQ_MAX, opt, cbq_policy);
1354 if (tb[TCA_CBQ_WRROPT]) {
1355 const struct tc_cbq_wrropt *wrr = nla_data(tb[TCA_CBQ_WRROPT]);
1357 if (wrr->priority > TC_CBQ_MAXPRIO)
1363 static int cbq_init(struct Qdisc *sch, struct nlattr *opt)
1365 struct cbq_sched_data *q = qdisc_priv(sch);
1366 struct nlattr *tb[TCA_CBQ_MAX + 1];
1367 struct tc_ratespec *r;
1370 err = cbq_opt_parse(tb, opt);
1374 if (tb[TCA_CBQ_RTAB] == NULL || tb[TCA_CBQ_RATE] == NULL)
1377 r = nla_data(tb[TCA_CBQ_RATE]);
1379 if ((q->link.R_tab = qdisc_get_rtab(r, tb[TCA_CBQ_RTAB])) == NULL)
1382 err = qdisc_class_hash_init(&q->clhash);
1387 q->link.sibling = &q->link;
1388 q->link.common.classid = sch->handle;
1389 q->link.qdisc = sch;
1390 q->link.q = qdisc_create_dflt(sch->dev_queue, &pfifo_qdisc_ops,
1393 q->link.q = &noop_qdisc;
1395 q->link.priority = TC_CBQ_MAXPRIO - 1;
1396 q->link.priority2 = TC_CBQ_MAXPRIO - 1;
1397 q->link.cpriority = TC_CBQ_MAXPRIO - 1;
1398 q->link.ovl_strategy = TC_CBQ_OVL_CLASSIC;
1399 q->link.overlimit = cbq_ovl_classic;
1400 q->link.allot = psched_mtu(qdisc_dev(sch));
1401 q->link.quantum = q->link.allot;
1402 q->link.weight = q->link.R_tab->rate.rate;
1404 q->link.ewma_log = TC_CBQ_DEF_EWMA;
1405 q->link.avpkt = q->link.allot/2;
1406 q->link.minidle = -0x7FFFFFFF;
1408 qdisc_watchdog_init(&q->watchdog, sch);
1409 hrtimer_init(&q->delay_timer, CLOCK_MONOTONIC, HRTIMER_MODE_ABS_PINNED);
1410 q->delay_timer.function = cbq_undelay;
1411 q->toplevel = TC_CBQ_MAXLEVEL;
1412 q->now = psched_get_time();
1414 cbq_link_class(&q->link);
1416 if (tb[TCA_CBQ_LSSOPT])
1417 cbq_set_lss(&q->link, nla_data(tb[TCA_CBQ_LSSOPT]));
1419 cbq_addprio(q, &q->link);
1423 qdisc_put_rtab(q->link.R_tab);
1427 static int cbq_dump_rate(struct sk_buff *skb, struct cbq_class *cl)
1429 unsigned char *b = skb_tail_pointer(skb);
1431 if (nla_put(skb, TCA_CBQ_RATE, sizeof(cl->R_tab->rate), &cl->R_tab->rate))
1432 goto nla_put_failure;
1440 static int cbq_dump_lss(struct sk_buff *skb, struct cbq_class *cl)
1442 unsigned char *b = skb_tail_pointer(skb);
1443 struct tc_cbq_lssopt opt;
1446 if (cl->borrow == NULL)
1447 opt.flags |= TCF_CBQ_LSS_BOUNDED;
1448 if (cl->share == NULL)
1449 opt.flags |= TCF_CBQ_LSS_ISOLATED;
1450 opt.ewma_log = cl->ewma_log;
1451 opt.level = cl->level;
1452 opt.avpkt = cl->avpkt;
1453 opt.maxidle = cl->maxidle;
1454 opt.minidle = (u32)(-cl->minidle);
1455 opt.offtime = cl->offtime;
1457 if (nla_put(skb, TCA_CBQ_LSSOPT, sizeof(opt), &opt))
1458 goto nla_put_failure;
1466 static int cbq_dump_wrr(struct sk_buff *skb, struct cbq_class *cl)
1468 unsigned char *b = skb_tail_pointer(skb);
1469 struct tc_cbq_wrropt opt;
1471 memset(&opt, 0, sizeof(opt));
1473 opt.allot = cl->allot;
1474 opt.priority = cl->priority + 1;
1475 opt.cpriority = cl->cpriority + 1;
1476 opt.weight = cl->weight;
1477 if (nla_put(skb, TCA_CBQ_WRROPT, sizeof(opt), &opt))
1478 goto nla_put_failure;
1486 static int cbq_dump_ovl(struct sk_buff *skb, struct cbq_class *cl)
1488 unsigned char *b = skb_tail_pointer(skb);
1489 struct tc_cbq_ovl opt;
1491 opt.strategy = cl->ovl_strategy;
1492 opt.priority2 = cl->priority2 + 1;
1494 opt.penalty = cl->penalty;
1495 if (nla_put(skb, TCA_CBQ_OVL_STRATEGY, sizeof(opt), &opt))
1496 goto nla_put_failure;
1504 static int cbq_dump_fopt(struct sk_buff *skb, struct cbq_class *cl)
1506 unsigned char *b = skb_tail_pointer(skb);
1507 struct tc_cbq_fopt opt;
1509 if (cl->split || cl->defmap) {
1510 opt.split = cl->split ? cl->split->common.classid : 0;
1511 opt.defmap = cl->defmap;
1513 if (nla_put(skb, TCA_CBQ_FOPT, sizeof(opt), &opt))
1514 goto nla_put_failure;
1523 #ifdef CONFIG_NET_CLS_ACT
1524 static int cbq_dump_police(struct sk_buff *skb, struct cbq_class *cl)
1526 unsigned char *b = skb_tail_pointer(skb);
1527 struct tc_cbq_police opt;
1530 opt.police = cl->police;
1533 if (nla_put(skb, TCA_CBQ_POLICE, sizeof(opt), &opt))
1534 goto nla_put_failure;
1544 static int cbq_dump_attr(struct sk_buff *skb, struct cbq_class *cl)
1546 if (cbq_dump_lss(skb, cl) < 0 ||
1547 cbq_dump_rate(skb, cl) < 0 ||
1548 cbq_dump_wrr(skb, cl) < 0 ||
1549 cbq_dump_ovl(skb, cl) < 0 ||
1550 #ifdef CONFIG_NET_CLS_ACT
1551 cbq_dump_police(skb, cl) < 0 ||
1553 cbq_dump_fopt(skb, cl) < 0)
1558 static int cbq_dump(struct Qdisc *sch, struct sk_buff *skb)
1560 struct cbq_sched_data *q = qdisc_priv(sch);
1561 struct nlattr *nest;
1563 nest = nla_nest_start(skb, TCA_OPTIONS);
1565 goto nla_put_failure;
1566 if (cbq_dump_attr(skb, &q->link) < 0)
1567 goto nla_put_failure;
1568 return nla_nest_end(skb, nest);
1571 nla_nest_cancel(skb, nest);
1576 cbq_dump_stats(struct Qdisc *sch, struct gnet_dump *d)
1578 struct cbq_sched_data *q = qdisc_priv(sch);
1580 q->link.xstats.avgidle = q->link.avgidle;
1581 return gnet_stats_copy_app(d, &q->link.xstats, sizeof(q->link.xstats));
1585 cbq_dump_class(struct Qdisc *sch, unsigned long arg,
1586 struct sk_buff *skb, struct tcmsg *tcm)
1588 struct cbq_class *cl = (struct cbq_class *)arg;
1589 struct nlattr *nest;
1592 tcm->tcm_parent = cl->tparent->common.classid;
1594 tcm->tcm_parent = TC_H_ROOT;
1595 tcm->tcm_handle = cl->common.classid;
1596 tcm->tcm_info = cl->q->handle;
1598 nest = nla_nest_start(skb, TCA_OPTIONS);
1600 goto nla_put_failure;
1601 if (cbq_dump_attr(skb, cl) < 0)
1602 goto nla_put_failure;
1603 return nla_nest_end(skb, nest);
1606 nla_nest_cancel(skb, nest);
1611 cbq_dump_class_stats(struct Qdisc *sch, unsigned long arg,
1612 struct gnet_dump *d)
1614 struct cbq_sched_data *q = qdisc_priv(sch);
1615 struct cbq_class *cl = (struct cbq_class *)arg;
1617 cl->xstats.avgidle = cl->avgidle;
1618 cl->xstats.undertime = 0;
1620 if (cl->undertime != PSCHED_PASTPERFECT)
1621 cl->xstats.undertime = cl->undertime - q->now;
1623 if (gnet_stats_copy_basic(d, NULL, &cl->bstats) < 0 ||
1624 gnet_stats_copy_rate_est(d, &cl->bstats, &cl->rate_est) < 0 ||
1625 gnet_stats_copy_queue(d, NULL, &cl->qstats, cl->q->q.qlen) < 0)
1628 return gnet_stats_copy_app(d, &cl->xstats, sizeof(cl->xstats));
1631 static int cbq_graft(struct Qdisc *sch, unsigned long arg, struct Qdisc *new,
1634 struct cbq_class *cl = (struct cbq_class *)arg;
1637 new = qdisc_create_dflt(sch->dev_queue,
1638 &pfifo_qdisc_ops, cl->common.classid);
1642 #ifdef CONFIG_NET_CLS_ACT
1643 if (cl->police == TC_POLICE_RECLASSIFY)
1644 new->reshape_fail = cbq_reshape_fail;
1648 *old = qdisc_replace(sch, new, &cl->q);
1652 static struct Qdisc *cbq_leaf(struct Qdisc *sch, unsigned long arg)
1654 struct cbq_class *cl = (struct cbq_class *)arg;
1659 static void cbq_qlen_notify(struct Qdisc *sch, unsigned long arg)
1661 struct cbq_class *cl = (struct cbq_class *)arg;
1663 if (cl->q->q.qlen == 0)
1664 cbq_deactivate_class(cl);
1667 static unsigned long cbq_get(struct Qdisc *sch, u32 classid)
1669 struct cbq_sched_data *q = qdisc_priv(sch);
1670 struct cbq_class *cl = cbq_class_lookup(q, classid);
1674 return (unsigned long)cl;
1679 static void cbq_destroy_class(struct Qdisc *sch, struct cbq_class *cl)
1681 struct cbq_sched_data *q = qdisc_priv(sch);
1683 WARN_ON(cl->filters);
1685 tcf_destroy_chain(&cl->filter_list);
1686 qdisc_destroy(cl->q);
1687 qdisc_put_rtab(cl->R_tab);
1688 gen_kill_estimator(&cl->bstats, &cl->rate_est);
1693 static void cbq_destroy(struct Qdisc *sch)
1695 struct cbq_sched_data *q = qdisc_priv(sch);
1696 struct hlist_node *next;
1697 struct cbq_class *cl;
1700 #ifdef CONFIG_NET_CLS_ACT
1704 * Filters must be destroyed first because we don't destroy the
1705 * classes from root to leafs which means that filters can still
1706 * be bound to classes which have been destroyed already. --TGR '04
1708 for (h = 0; h < q->clhash.hashsize; h++) {
1709 hlist_for_each_entry(cl, &q->clhash.hash[h], common.hnode)
1710 tcf_destroy_chain(&cl->filter_list);
1712 for (h = 0; h < q->clhash.hashsize; h++) {
1713 hlist_for_each_entry_safe(cl, next, &q->clhash.hash[h],
1715 cbq_destroy_class(sch, cl);
1717 qdisc_class_hash_destroy(&q->clhash);
1720 static void cbq_put(struct Qdisc *sch, unsigned long arg)
1722 struct cbq_class *cl = (struct cbq_class *)arg;
1724 if (--cl->refcnt == 0) {
1725 #ifdef CONFIG_NET_CLS_ACT
1726 spinlock_t *root_lock = qdisc_root_sleeping_lock(sch);
1727 struct cbq_sched_data *q = qdisc_priv(sch);
1729 spin_lock_bh(root_lock);
1730 if (q->rx_class == cl)
1732 spin_unlock_bh(root_lock);
1735 cbq_destroy_class(sch, cl);
1740 cbq_change_class(struct Qdisc *sch, u32 classid, u32 parentid, struct nlattr **tca,
1744 struct cbq_sched_data *q = qdisc_priv(sch);
1745 struct cbq_class *cl = (struct cbq_class *)*arg;
1746 struct nlattr *opt = tca[TCA_OPTIONS];
1747 struct nlattr *tb[TCA_CBQ_MAX + 1];
1748 struct cbq_class *parent;
1749 struct qdisc_rate_table *rtab = NULL;
1751 err = cbq_opt_parse(tb, opt);
1759 cl->tparent->common.classid != parentid)
1761 if (!cl->tparent && parentid != TC_H_ROOT)
1765 if (tb[TCA_CBQ_RATE]) {
1766 rtab = qdisc_get_rtab(nla_data(tb[TCA_CBQ_RATE]),
1772 if (tca[TCA_RATE]) {
1773 err = gen_replace_estimator(&cl->bstats, NULL,
1775 qdisc_root_sleeping_lock(sch),
1778 qdisc_put_rtab(rtab);
1783 /* Change class parameters */
1786 if (cl->next_alive != NULL)
1787 cbq_deactivate_class(cl);
1790 qdisc_put_rtab(cl->R_tab);
1794 if (tb[TCA_CBQ_LSSOPT])
1795 cbq_set_lss(cl, nla_data(tb[TCA_CBQ_LSSOPT]));
1797 if (tb[TCA_CBQ_WRROPT]) {
1799 cbq_set_wrr(cl, nla_data(tb[TCA_CBQ_WRROPT]));
1802 if (tb[TCA_CBQ_OVL_STRATEGY])
1803 cbq_set_overlimit(cl, nla_data(tb[TCA_CBQ_OVL_STRATEGY]));
1805 #ifdef CONFIG_NET_CLS_ACT
1806 if (tb[TCA_CBQ_POLICE])
1807 cbq_set_police(cl, nla_data(tb[TCA_CBQ_POLICE]));
1810 if (tb[TCA_CBQ_FOPT])
1811 cbq_set_fopt(cl, nla_data(tb[TCA_CBQ_FOPT]));
1814 cbq_activate_class(cl);
1816 sch_tree_unlock(sch);
1821 if (parentid == TC_H_ROOT)
1824 if (tb[TCA_CBQ_WRROPT] == NULL || tb[TCA_CBQ_RATE] == NULL ||
1825 tb[TCA_CBQ_LSSOPT] == NULL)
1828 rtab = qdisc_get_rtab(nla_data(tb[TCA_CBQ_RATE]), tb[TCA_CBQ_RTAB]);
1834 if (TC_H_MAJ(classid ^ sch->handle) ||
1835 cbq_class_lookup(q, classid))
1839 classid = TC_H_MAKE(sch->handle, 0x8000);
1841 for (i = 0; i < 0x8000; i++) {
1842 if (++q->hgenerator >= 0x8000)
1844 if (cbq_class_lookup(q, classid|q->hgenerator) == NULL)
1850 classid = classid|q->hgenerator;
1855 parent = cbq_class_lookup(q, parentid);
1862 cl = kzalloc(sizeof(*cl), GFP_KERNEL);
1866 if (tca[TCA_RATE]) {
1867 err = gen_new_estimator(&cl->bstats, NULL, &cl->rate_est,
1868 qdisc_root_sleeping_lock(sch),
1879 cl->q = qdisc_create_dflt(sch->dev_queue, &pfifo_qdisc_ops, classid);
1881 cl->q = &noop_qdisc;
1882 cl->common.classid = classid;
1883 cl->tparent = parent;
1885 cl->allot = parent->allot;
1886 cl->quantum = cl->allot;
1887 cl->weight = cl->R_tab->rate.rate;
1891 cl->borrow = cl->tparent;
1892 if (cl->tparent != &q->link)
1893 cl->share = cl->tparent;
1894 cbq_adjust_levels(parent);
1895 cl->minidle = -0x7FFFFFFF;
1896 cbq_set_lss(cl, nla_data(tb[TCA_CBQ_LSSOPT]));
1897 cbq_set_wrr(cl, nla_data(tb[TCA_CBQ_WRROPT]));
1898 if (cl->ewma_log == 0)
1899 cl->ewma_log = q->link.ewma_log;
1900 if (cl->maxidle == 0)
1901 cl->maxidle = q->link.maxidle;
1903 cl->avpkt = q->link.avpkt;
1904 cl->overlimit = cbq_ovl_classic;
1905 if (tb[TCA_CBQ_OVL_STRATEGY])
1906 cbq_set_overlimit(cl, nla_data(tb[TCA_CBQ_OVL_STRATEGY]));
1907 #ifdef CONFIG_NET_CLS_ACT
1908 if (tb[TCA_CBQ_POLICE])
1909 cbq_set_police(cl, nla_data(tb[TCA_CBQ_POLICE]));
1911 if (tb[TCA_CBQ_FOPT])
1912 cbq_set_fopt(cl, nla_data(tb[TCA_CBQ_FOPT]));
1913 sch_tree_unlock(sch);
1915 qdisc_class_hash_grow(sch, &q->clhash);
1917 *arg = (unsigned long)cl;
1921 qdisc_put_rtab(rtab);
1925 static int cbq_delete(struct Qdisc *sch, unsigned long arg)
1927 struct cbq_sched_data *q = qdisc_priv(sch);
1928 struct cbq_class *cl = (struct cbq_class *)arg;
1929 unsigned int qlen, backlog;
1931 if (cl->filters || cl->children || cl == &q->link)
1936 qlen = cl->q->q.qlen;
1937 backlog = cl->q->qstats.backlog;
1939 qdisc_tree_reduce_backlog(cl->q, qlen, backlog);
1942 cbq_deactivate_class(cl);
1944 if (q->tx_borrowed == cl)
1945 q->tx_borrowed = q->tx_class;
1946 if (q->tx_class == cl) {
1948 q->tx_borrowed = NULL;
1950 #ifdef CONFIG_NET_CLS_ACT
1951 if (q->rx_class == cl)
1955 cbq_unlink_class(cl);
1956 cbq_adjust_levels(cl->tparent);
1958 cbq_sync_defmap(cl);
1961 sch_tree_unlock(sch);
1963 BUG_ON(--cl->refcnt == 0);
1965 * This shouldn't happen: we "hold" one cops->get() when called
1966 * from tc_ctl_tclass; the destroy method is done from cops->put().
1972 static struct tcf_proto __rcu **cbq_find_tcf(struct Qdisc *sch,
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;
2016 for (h = 0; h < q->clhash.hashsize; h++) {
2017 hlist_for_each_entry(cl, &q->clhash.hash[h], common.hnode) {
2018 if (arg->count < arg->skip) {
2022 if (arg->fn(sch, (unsigned long)cl, arg) < 0) {
2031 static const struct Qdisc_class_ops cbq_class_ops = {
2034 .qlen_notify = cbq_qlen_notify,
2037 .change = cbq_change_class,
2038 .delete = cbq_delete,
2040 .tcf_chain = cbq_find_tcf,
2041 .bind_tcf = cbq_bind_filter,
2042 .unbind_tcf = cbq_unbind_filter,
2043 .dump = cbq_dump_class,
2044 .dump_stats = cbq_dump_class_stats,
2047 static struct Qdisc_ops cbq_qdisc_ops __read_mostly = {
2049 .cl_ops = &cbq_class_ops,
2051 .priv_size = sizeof(struct cbq_sched_data),
2052 .enqueue = cbq_enqueue,
2053 .dequeue = cbq_dequeue,
2054 .peek = qdisc_peek_dequeued,
2058 .destroy = cbq_destroy,
2061 .dump_stats = cbq_dump_stats,
2062 .owner = THIS_MODULE,
2065 static int __init cbq_module_init(void)
2067 return register_qdisc(&cbq_qdisc_ops);
2069 static void __exit cbq_module_exit(void)
2071 unregister_qdisc(&cbq_qdisc_ops);
2073 module_init(cbq_module_init)
2074 module_exit(cbq_module_exit)
2075 MODULE_LICENSE("GPL");