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 <asm/uaccess.h>
15 #include <asm/system.h>
16 #include <linux/bitops.h>
17 #include <linux/types.h>
18 #include <linux/kernel.h>
19 #include <linux/string.h>
21 #include <linux/socket.h>
22 #include <linux/sockios.h>
24 #include <linux/errno.h>
25 #include <linux/interrupt.h>
26 #include <linux/if_ether.h>
27 #include <linux/inet.h>
28 #include <linux/netdevice.h>
29 #include <linux/etherdevice.h>
30 #include <linux/notifier.h>
32 #include <net/netlink.h>
33 #include <net/route.h>
34 #include <linux/skbuff.h>
36 #include <net/pkt_sched.h>
39 /* Class-Based Queueing (CBQ) algorithm.
40 =======================================
42 Sources: [1] Sally Floyd and Van Jacobson, "Link-sharing and Resource
43 Management Models for Packet Networks",
44 IEEE/ACM Transactions on Networking, Vol.3, No.4, 1995
46 [2] Sally Floyd, "Notes on CBQ and Guaranteed Service", 1995
48 [3] Sally Floyd, "Notes on Class-Based Queueing: Setting
51 [4] Sally Floyd and Michael Speer, "Experimental Results
52 for Class-Based Queueing", 1998, not published.
54 -----------------------------------------------------------------------
56 Algorithm skeleton was taken from NS simulator cbq.cc.
57 If someone wants to check this code against the LBL version,
58 he should take into account that ONLY the skeleton was borrowed,
59 the implementation is different. Particularly:
61 --- The WRR algorithm is different. Our version looks more
62 reasonable (I hope) and works when quanta are allowed to be
63 less than MTU, which is always the case when real time classes
64 have small rates. Note, that the statement of [3] is
65 incomplete, delay may actually be estimated even if class
66 per-round allotment is less than MTU. Namely, if per-round
67 allotment is W*r_i, and r_1+...+r_k = r < 1
69 delay_i <= ([MTU/(W*r_i)]*W*r + W*r + k*MTU)/B
71 In the worst case we have IntServ estimate with D = W*r+k*MTU
72 and C = MTU*r. The proof (if correct at all) is trivial.
75 --- It seems that cbq-2.0 is not very accurate. At least, I cannot
76 interpret some places, which look like wrong translations
77 from NS. Anyone is advised to find these differences
78 and explain to me, why I am wrong 8).
80 --- Linux has no EOI event, so that we cannot estimate true class
81 idle time. Workaround is to consider the next dequeue event
82 as sign that previous packet is finished. This is wrong because of
83 internal device queueing, but on a permanently loaded link it is true.
84 Moreover, combined with clock integrator, this scheme looks
85 very close to an ideal solution. */
87 struct cbq_sched_data;
92 struct cbq_class *next; /* hash table link */
93 struct cbq_class *next_alive; /* next class with backlog in this priority band */
97 unsigned char priority; /* class priority */
98 unsigned char priority2; /* priority to be used after overlimit */
99 unsigned char ewma_log; /* time constant for idle time calculation */
100 unsigned char ovl_strategy;
101 #ifdef CONFIG_NET_CLS_POLICE
102 unsigned char police;
107 /* Link-sharing scheduler parameters */
108 long maxidle; /* Class parameters: see below. */
112 struct qdisc_rate_table *R_tab;
114 /* Overlimit strategy parameters */
115 void (*overlimit)(struct cbq_class *cl);
116 psched_tdiff_t penalty;
118 /* General scheduler (WRR) parameters */
120 long quantum; /* Allotment per WRR round */
121 long weight; /* Relative allotment: see below */
123 struct Qdisc *qdisc; /* Ptr to CBQ discipline */
124 struct cbq_class *split; /* Ptr to split node */
125 struct cbq_class *share; /* Ptr to LS parent in the class tree */
126 struct cbq_class *tparent; /* Ptr to tree parent in the class tree */
127 struct cbq_class *borrow; /* NULL if class is bandwidth limited;
129 struct cbq_class *sibling; /* Sibling chain */
130 struct cbq_class *children; /* Pointer to children chain */
132 struct Qdisc *q; /* Elementary queueing discipline */
136 unsigned char cpriority; /* Effective priority */
137 unsigned char delayed;
138 unsigned char level; /* level of the class in hierarchy:
139 0 for leaf classes, and maximal
140 level of children + 1 for nodes.
143 psched_time_t last; /* Last end of service */
144 psched_time_t undertime;
146 long deficit; /* Saved deficit for WRR */
147 psched_time_t penalized;
148 struct gnet_stats_basic bstats;
149 struct gnet_stats_queue qstats;
150 struct gnet_stats_rate_est rate_est;
151 spinlock_t *stats_lock;
152 struct tc_cbq_xstats xstats;
154 struct tcf_proto *filter_list;
159 struct cbq_class *defaults[TC_PRIO_MAX+1];
162 struct cbq_sched_data
164 struct cbq_class *classes[16]; /* Hash table of all classes */
165 int nclasses[TC_CBQ_MAXPRIO+1];
166 unsigned quanta[TC_CBQ_MAXPRIO+1];
168 struct cbq_class link;
171 struct cbq_class *active[TC_CBQ_MAXPRIO+1]; /* List of all classes
174 #ifdef CONFIG_NET_CLS_POLICE
175 struct cbq_class *rx_class;
177 struct cbq_class *tx_class;
178 struct cbq_class *tx_borrowed;
180 psched_time_t now; /* Cached timestamp */
181 psched_time_t now_rt; /* Cached real time */
184 struct hrtimer delay_timer;
185 struct qdisc_watchdog watchdog; /* Watchdog timer,
189 psched_tdiff_t wd_expires;
195 #define L2T(cl,len) ((cl)->R_tab->data[(len)>>(cl)->R_tab->rate.cell_log])
198 static __inline__ unsigned cbq_hash(u32 h)
205 static __inline__ struct cbq_class *
206 cbq_class_lookup(struct cbq_sched_data *q, u32 classid)
208 struct cbq_class *cl;
210 for (cl = q->classes[cbq_hash(classid)]; cl; cl = cl->next)
211 if (cl->classid == classid)
216 #ifdef CONFIG_NET_CLS_POLICE
218 static struct cbq_class *
219 cbq_reclassify(struct sk_buff *skb, struct cbq_class *this)
221 struct cbq_class *cl, *new;
223 for (cl = this->tparent; cl; cl = cl->tparent)
224 if ((new = cl->defaults[TC_PRIO_BESTEFFORT]) != NULL && new != this)
232 /* Classify packet. The procedure is pretty complicated, but
233 it allows us to combine link sharing and priority scheduling
236 Namely, you can put link sharing rules (f.e. route based) at root of CBQ,
237 so that it resolves to split nodes. Then packets are classified
238 by logical priority, or a more specific classifier may be attached
242 static struct cbq_class *
243 cbq_classify(struct sk_buff *skb, struct Qdisc *sch, int *qerr)
245 struct cbq_sched_data *q = qdisc_priv(sch);
246 struct cbq_class *head = &q->link;
247 struct cbq_class **defmap;
248 struct cbq_class *cl = NULL;
249 u32 prio = skb->priority;
250 struct tcf_result res;
253 * Step 1. If skb->priority points to one of our classes, use it.
255 if (TC_H_MAJ(prio^sch->handle) == 0 &&
256 (cl = cbq_class_lookup(q, prio)) != NULL)
259 *qerr = NET_XMIT_BYPASS;
262 defmap = head->defaults;
265 * Step 2+n. Apply classifier.
267 if (!head->filter_list || (result = tc_classify(skb, head->filter_list, &res)) < 0)
270 if ((cl = (void*)res.class) == NULL) {
271 if (TC_H_MAJ(res.classid))
272 cl = cbq_class_lookup(q, res.classid);
273 else if ((cl = defmap[res.classid&TC_PRIO_MAX]) == NULL)
274 cl = defmap[TC_PRIO_BESTEFFORT];
276 if (cl == NULL || cl->level >= head->level)
280 #ifdef CONFIG_NET_CLS_ACT
284 *qerr = NET_XMIT_SUCCESS;
288 #elif defined(CONFIG_NET_CLS_POLICE)
290 case TC_POLICE_RECLASSIFY:
291 return cbq_reclassify(skb, cl);
302 * Step 3+n. If classifier selected a link sharing class,
303 * apply agency specific classifier.
304 * Repeat this procdure until we hit a leaf node.
313 * Step 4. No success...
315 if (TC_H_MAJ(prio) == 0 &&
316 !(cl = head->defaults[prio&TC_PRIO_MAX]) &&
317 !(cl = head->defaults[TC_PRIO_BESTEFFORT]))
324 A packet has just been enqueued on the empty class.
325 cbq_activate_class adds it to the tail of active class list
326 of its priority band.
329 static __inline__ void cbq_activate_class(struct cbq_class *cl)
331 struct cbq_sched_data *q = qdisc_priv(cl->qdisc);
332 int prio = cl->cpriority;
333 struct cbq_class *cl_tail;
335 cl_tail = q->active[prio];
336 q->active[prio] = cl;
338 if (cl_tail != NULL) {
339 cl->next_alive = cl_tail->next_alive;
340 cl_tail->next_alive = cl;
343 q->activemask |= (1<<prio);
348 Unlink class from active chain.
349 Note that this same procedure is done directly in cbq_dequeue*
350 during round-robin procedure.
353 static void cbq_deactivate_class(struct cbq_class *this)
355 struct cbq_sched_data *q = qdisc_priv(this->qdisc);
356 int prio = this->cpriority;
357 struct cbq_class *cl;
358 struct cbq_class *cl_prev = q->active[prio];
361 cl = cl_prev->next_alive;
363 cl_prev->next_alive = cl->next_alive;
364 cl->next_alive = NULL;
366 if (cl == q->active[prio]) {
367 q->active[prio] = cl_prev;
368 if (cl == q->active[prio]) {
369 q->active[prio] = NULL;
370 q->activemask &= ~(1<<prio);
376 } while ((cl_prev = cl) != q->active[prio]);
380 cbq_mark_toplevel(struct cbq_sched_data *q, struct cbq_class *cl)
382 int toplevel = q->toplevel;
384 if (toplevel > cl->level && !(cl->q->flags&TCQ_F_THROTTLED)) {
388 PSCHED_GET_TIME(now);
389 incr = PSCHED_TDIFF(now, q->now_rt);
393 if (cl->undertime < now) {
394 q->toplevel = cl->level;
397 } while ((cl=cl->borrow) != NULL && toplevel > cl->level);
402 cbq_enqueue(struct sk_buff *skb, struct Qdisc *sch)
404 struct cbq_sched_data *q = qdisc_priv(sch);
407 struct cbq_class *cl = cbq_classify(skb, sch, &ret);
409 #ifdef CONFIG_NET_CLS_POLICE
413 if (ret == NET_XMIT_BYPASS)
419 #ifdef CONFIG_NET_CLS_POLICE
420 cl->q->__parent = sch;
422 if ((ret = cl->q->enqueue(skb, cl->q)) == NET_XMIT_SUCCESS) {
424 sch->bstats.packets++;
425 sch->bstats.bytes+=len;
426 cbq_mark_toplevel(q, cl);
428 cbq_activate_class(cl);
433 cbq_mark_toplevel(q, cl);
439 cbq_requeue(struct sk_buff *skb, struct Qdisc *sch)
441 struct cbq_sched_data *q = qdisc_priv(sch);
442 struct cbq_class *cl;
445 if ((cl = q->tx_class) == NULL) {
452 cbq_mark_toplevel(q, cl);
454 #ifdef CONFIG_NET_CLS_POLICE
456 cl->q->__parent = sch;
458 if ((ret = cl->q->ops->requeue(skb, cl->q)) == 0) {
460 sch->qstats.requeues++;
462 cbq_activate_class(cl);
470 /* Overlimit actions */
472 /* TC_CBQ_OVL_CLASSIC: (default) penalize leaf class by adding offtime */
474 static void cbq_ovl_classic(struct cbq_class *cl)
476 struct cbq_sched_data *q = qdisc_priv(cl->qdisc);
477 psched_tdiff_t delay = PSCHED_TDIFF(cl->undertime, q->now);
480 delay += cl->offtime;
483 Class goes to sleep, so that it will have no
484 chance to work avgidle. Let's forgive it 8)
486 BTW cbq-2.0 has a crap in this
487 place, apparently they forgot to shift it by cl->ewma_log.
490 delay -= (-cl->avgidle) - ((-cl->avgidle) >> cl->ewma_log);
491 if (cl->avgidle < cl->minidle)
492 cl->avgidle = cl->minidle;
495 cl->undertime = q->now + delay;
497 cl->xstats.overactions++;
500 if (q->wd_expires == 0 || q->wd_expires > delay)
501 q->wd_expires = delay;
503 /* Dirty work! We must schedule wakeups based on
504 real available rate, rather than leaf rate,
505 which may be tiny (even zero).
507 if (q->toplevel == TC_CBQ_MAXLEVEL) {
509 psched_tdiff_t base_delay = q->wd_expires;
511 for (b = cl->borrow; b; b = b->borrow) {
512 delay = PSCHED_TDIFF(b->undertime, q->now);
513 if (delay < base_delay) {
520 q->wd_expires = base_delay;
524 /* TC_CBQ_OVL_RCLASSIC: penalize by offtime classes in hierarchy, when
528 static void cbq_ovl_rclassic(struct cbq_class *cl)
530 struct cbq_sched_data *q = qdisc_priv(cl->qdisc);
531 struct cbq_class *this = cl;
534 if (cl->level > q->toplevel) {
538 } while ((cl = cl->borrow) != NULL);
545 /* TC_CBQ_OVL_DELAY: delay until it will go to underlimit */
547 static void cbq_ovl_delay(struct cbq_class *cl)
549 struct cbq_sched_data *q = qdisc_priv(cl->qdisc);
550 psched_tdiff_t delay = PSCHED_TDIFF(cl->undertime, q->now);
553 psched_time_t sched = q->now;
556 delay += cl->offtime;
558 delay -= (-cl->avgidle) - ((-cl->avgidle) >> cl->ewma_log);
559 if (cl->avgidle < cl->minidle)
560 cl->avgidle = cl->minidle;
561 cl->undertime = q->now + delay;
564 sched += delay + cl->penalty;
565 cl->penalized = sched;
566 cl->cpriority = TC_CBQ_MAXPRIO;
567 q->pmask |= (1<<TC_CBQ_MAXPRIO);
569 expires = ktime_set(0, 0);
570 expires = ktime_add_ns(expires, PSCHED_US2NS(sched));
571 if (hrtimer_try_to_cancel(&q->delay_timer) &&
572 ktime_to_ns(ktime_sub(q->delay_timer.expires,
574 q->delay_timer.expires = expires;
575 hrtimer_restart(&q->delay_timer);
577 cl->xstats.overactions++;
582 if (q->wd_expires == 0 || q->wd_expires > delay)
583 q->wd_expires = delay;
586 /* TC_CBQ_OVL_LOWPRIO: penalize class by lowering its priority band */
588 static void cbq_ovl_lowprio(struct cbq_class *cl)
590 struct cbq_sched_data *q = qdisc_priv(cl->qdisc);
592 cl->penalized = q->now + cl->penalty;
594 if (cl->cpriority != cl->priority2) {
595 cl->cpriority = cl->priority2;
596 q->pmask |= (1<<cl->cpriority);
597 cl->xstats.overactions++;
602 /* TC_CBQ_OVL_DROP: penalize class by dropping */
604 static void cbq_ovl_drop(struct cbq_class *cl)
606 if (cl->q->ops->drop)
607 if (cl->q->ops->drop(cl->q))
609 cl->xstats.overactions++;
613 static psched_tdiff_t cbq_undelay_prio(struct cbq_sched_data *q, int prio,
616 struct cbq_class *cl;
617 struct cbq_class *cl_prev = q->active[prio];
618 psched_time_t sched = now;
624 cl = cl_prev->next_alive;
625 if (now - cl->penalized > 0) {
626 cl_prev->next_alive = cl->next_alive;
627 cl->next_alive = NULL;
628 cl->cpriority = cl->priority;
630 cbq_activate_class(cl);
632 if (cl == q->active[prio]) {
633 q->active[prio] = cl_prev;
634 if (cl == q->active[prio]) {
635 q->active[prio] = NULL;
640 cl = cl_prev->next_alive;
641 } else if (sched - cl->penalized > 0)
642 sched = cl->penalized;
643 } while ((cl_prev = cl) != q->active[prio]);
648 static enum hrtimer_restart cbq_undelay(struct hrtimer *timer)
650 struct cbq_sched_data *q = container_of(timer, struct cbq_sched_data,
652 struct Qdisc *sch = q->watchdog.qdisc;
654 psched_tdiff_t delay = 0;
657 PSCHED_GET_TIME(now);
663 int prio = ffz(~pmask);
668 tmp = cbq_undelay_prio(q, prio, now);
671 if (tmp < delay || delay == 0)
679 time = ktime_set(0, 0);
680 time = ktime_add_ns(time, PSCHED_US2NS(now + delay));
681 hrtimer_start(&q->delay_timer, time, HRTIMER_MODE_ABS);
684 sch->flags &= ~TCQ_F_THROTTLED;
685 netif_schedule(sch->dev);
686 return HRTIMER_NORESTART;
690 #ifdef CONFIG_NET_CLS_POLICE
692 static int cbq_reshape_fail(struct sk_buff *skb, struct Qdisc *child)
695 struct Qdisc *sch = child->__parent;
696 struct cbq_sched_data *q = qdisc_priv(sch);
697 struct cbq_class *cl = q->rx_class;
701 if (cl && (cl = cbq_reclassify(skb, cl)) != NULL) {
703 cbq_mark_toplevel(q, cl);
706 cl->q->__parent = sch;
708 if (cl->q->enqueue(skb, cl->q) == 0) {
710 sch->bstats.packets++;
711 sch->bstats.bytes+=len;
713 cbq_activate_class(cl);
726 It is mission critical procedure.
728 We "regenerate" toplevel cutoff, if transmitting class
729 has backlog and it is not regulated. It is not part of
730 original CBQ description, but looks more reasonable.
731 Probably, it is wrong. This question needs further investigation.
734 static __inline__ void
735 cbq_update_toplevel(struct cbq_sched_data *q, struct cbq_class *cl,
736 struct cbq_class *borrowed)
738 if (cl && q->toplevel >= borrowed->level) {
739 if (cl->q->q.qlen > 1) {
741 if (borrowed->undertime == PSCHED_PASTPERFECT) {
742 q->toplevel = borrowed->level;
745 } while ((borrowed=borrowed->borrow) != NULL);
748 /* It is not necessary now. Uncommenting it
749 will save CPU cycles, but decrease fairness.
751 q->toplevel = TC_CBQ_MAXLEVEL;
757 cbq_update(struct cbq_sched_data *q)
759 struct cbq_class *this = q->tx_class;
760 struct cbq_class *cl = this;
765 for ( ; cl; cl = cl->share) {
766 long avgidle = cl->avgidle;
769 cl->bstats.packets++;
770 cl->bstats.bytes += len;
773 (now - last) is total time between packet right edges.
774 (last_pktlen/rate) is "virtual" busy time, so that
776 idle = (now - last) - last_pktlen/rate
779 idle = PSCHED_TDIFF(q->now, cl->last);
780 if ((unsigned long)idle > 128*1024*1024) {
781 avgidle = cl->maxidle;
783 idle -= L2T(cl, len);
785 /* true_avgidle := (1-W)*true_avgidle + W*idle,
786 where W=2^{-ewma_log}. But cl->avgidle is scaled:
787 cl->avgidle == true_avgidle/W,
790 avgidle += idle - (avgidle>>cl->ewma_log);
794 /* Overlimit or at-limit */
796 if (avgidle < cl->minidle)
797 avgidle = cl->minidle;
799 cl->avgidle = avgidle;
801 /* Calculate expected time, when this class
802 will be allowed to send.
804 (1-W)*true_avgidle + W*delay = 0, i.e.
805 idle = (1/W - 1)*(-true_avgidle)
807 idle = (1 - W)*(-cl->avgidle);
809 idle = (-avgidle) - ((-avgidle) >> cl->ewma_log);
813 To maintain the rate allocated to the class,
814 we add to undertime virtual clock,
815 necessary to complete transmitted packet.
816 (len/phys_bandwidth has been already passed
817 to the moment of cbq_update)
820 idle -= L2T(&q->link, len);
821 idle += L2T(cl, len);
823 cl->undertime = q->now + idle;
827 cl->undertime = PSCHED_PASTPERFECT;
828 if (avgidle > cl->maxidle)
829 cl->avgidle = cl->maxidle;
831 cl->avgidle = avgidle;
836 cbq_update_toplevel(q, this, q->tx_borrowed);
839 static __inline__ struct cbq_class *
840 cbq_under_limit(struct cbq_class *cl)
842 struct cbq_sched_data *q = qdisc_priv(cl->qdisc);
843 struct cbq_class *this_cl = cl;
845 if (cl->tparent == NULL)
848 if (cl->undertime == PSCHED_PASTPERFECT || q->now >= cl->undertime) {
854 /* It is very suspicious place. Now overlimit
855 action is generated for not bounded classes
856 only if link is completely congested.
857 Though it is in agree with ancestor-only paradigm,
858 it looks very stupid. Particularly,
859 it means that this chunk of code will either
860 never be called or result in strong amplification
861 of burstiness. Dangerous, silly, and, however,
862 no another solution exists.
864 if ((cl = cl->borrow) == NULL) {
865 this_cl->qstats.overlimits++;
866 this_cl->overlimit(this_cl);
869 if (cl->level > q->toplevel)
871 } while (cl->undertime != PSCHED_PASTPERFECT && q->now < cl->undertime);
877 static __inline__ struct sk_buff *
878 cbq_dequeue_prio(struct Qdisc *sch, int prio)
880 struct cbq_sched_data *q = qdisc_priv(sch);
881 struct cbq_class *cl_tail, *cl_prev, *cl;
885 cl_tail = cl_prev = q->active[prio];
886 cl = cl_prev->next_alive;
893 struct cbq_class *borrow = cl;
896 (borrow = cbq_under_limit(cl)) == NULL)
899 if (cl->deficit <= 0) {
900 /* Class exhausted its allotment per
901 this round. Switch to the next one.
904 cl->deficit += cl->quantum;
908 skb = cl->q->dequeue(cl->q);
910 /* Class did not give us any skb :-(
911 It could occur even if cl->q->q.qlen != 0
912 f.e. if cl->q == "tbf"
917 cl->deficit -= skb->len;
919 q->tx_borrowed = borrow;
921 #ifndef CBQ_XSTATS_BORROWS_BYTES
922 borrow->xstats.borrows++;
923 cl->xstats.borrows++;
925 borrow->xstats.borrows += skb->len;
926 cl->xstats.borrows += skb->len;
929 q->tx_len = skb->len;
931 if (cl->deficit <= 0) {
932 q->active[prio] = cl;
934 cl->deficit += cl->quantum;
939 if (cl->q->q.qlen == 0 || prio != cl->cpriority) {
940 /* Class is empty or penalized.
941 Unlink it from active chain.
943 cl_prev->next_alive = cl->next_alive;
944 cl->next_alive = NULL;
946 /* Did cl_tail point to it? */
951 /* Was it the last class in this band? */
954 q->active[prio] = NULL;
955 q->activemask &= ~(1<<prio);
957 cbq_activate_class(cl);
961 q->active[prio] = cl_tail;
964 cbq_activate_class(cl);
972 } while (cl_prev != cl_tail);
975 q->active[prio] = cl_prev;
980 static __inline__ struct sk_buff *
981 cbq_dequeue_1(struct Qdisc *sch)
983 struct cbq_sched_data *q = qdisc_priv(sch);
987 activemask = q->activemask&0xFF;
989 int prio = ffz(~activemask);
990 activemask &= ~(1<<prio);
991 skb = cbq_dequeue_prio(sch, prio);
998 static struct sk_buff *
999 cbq_dequeue(struct Qdisc *sch)
1001 struct sk_buff *skb;
1002 struct cbq_sched_data *q = qdisc_priv(sch);
1004 psched_tdiff_t incr;
1006 PSCHED_GET_TIME(now);
1007 incr = PSCHED_TDIFF(now, q->now_rt);
1010 psched_tdiff_t incr2;
1011 /* Time integrator. We calculate EOS time
1012 by adding expected packet transmission time.
1013 If real time is greater, we warp artificial clock,
1016 cbq_time = max(real_time, work);
1018 incr2 = L2T(&q->link, q->tx_len);
1021 if ((incr -= incr2) < 0)
1030 skb = cbq_dequeue_1(sch);
1033 sch->flags &= ~TCQ_F_THROTTLED;
1037 /* All the classes are overlimit.
1041 1. Scheduler is empty.
1042 2. Toplevel cutoff inhibited borrowing.
1043 3. Root class is overlimit.
1045 Reset 2d and 3d conditions and retry.
1047 Note, that NS and cbq-2.0 are buggy, peeking
1048 an arbitrary class is appropriate for ancestor-only
1049 sharing, but not for toplevel algorithm.
1051 Our version is better, but slower, because it requires
1052 two passes, but it is unavoidable with top-level sharing.
1055 if (q->toplevel == TC_CBQ_MAXLEVEL &&
1056 q->link.undertime == PSCHED_PASTPERFECT)
1059 q->toplevel = TC_CBQ_MAXLEVEL;
1060 q->link.undertime = PSCHED_PASTPERFECT;
1063 /* No packets in scheduler or nobody wants to give them to us :-(
1064 Sigh... start watchdog timer in the last case. */
1067 sch->qstats.overlimits++;
1069 qdisc_watchdog_schedule(&q->watchdog,
1070 now + q->wd_expires);
1075 /* CBQ class maintanance routines */
1077 static void cbq_adjust_levels(struct cbq_class *this)
1084 struct cbq_class *cl;
1086 if ((cl = this->children) != NULL) {
1088 if (cl->level > level)
1090 } while ((cl = cl->sibling) != this->children);
1092 this->level = level+1;
1093 } while ((this = this->tparent) != NULL);
1096 static void cbq_normalize_quanta(struct cbq_sched_data *q, int prio)
1098 struct cbq_class *cl;
1101 if (q->quanta[prio] == 0)
1104 for (h=0; h<16; h++) {
1105 for (cl = q->classes[h]; cl; cl = cl->next) {
1106 /* BUGGGG... Beware! This expression suffer of
1107 arithmetic overflows!
1109 if (cl->priority == prio) {
1110 cl->quantum = (cl->weight*cl->allot*q->nclasses[prio])/
1113 if (cl->quantum <= 0 || cl->quantum>32*cl->qdisc->dev->mtu) {
1114 printk(KERN_WARNING "CBQ: class %08x has bad quantum==%ld, repaired.\n", cl->classid, cl->quantum);
1115 cl->quantum = cl->qdisc->dev->mtu/2 + 1;
1121 static void cbq_sync_defmap(struct cbq_class *cl)
1123 struct cbq_sched_data *q = qdisc_priv(cl->qdisc);
1124 struct cbq_class *split = cl->split;
1131 for (i=0; i<=TC_PRIO_MAX; i++) {
1132 if (split->defaults[i] == cl && !(cl->defmap&(1<<i)))
1133 split->defaults[i] = NULL;
1136 for (i=0; i<=TC_PRIO_MAX; i++) {
1137 int level = split->level;
1139 if (split->defaults[i])
1142 for (h=0; h<16; h++) {
1143 struct cbq_class *c;
1145 for (c = q->classes[h]; c; c = c->next) {
1146 if (c->split == split && c->level < level &&
1148 split->defaults[i] = c;
1156 static void cbq_change_defmap(struct cbq_class *cl, u32 splitid, u32 def, u32 mask)
1158 struct cbq_class *split = NULL;
1161 if ((split = cl->split) == NULL)
1163 splitid = split->classid;
1166 if (split == NULL || split->classid != splitid) {
1167 for (split = cl->tparent; split; split = split->tparent)
1168 if (split->classid == splitid)
1175 if (cl->split != split) {
1177 cbq_sync_defmap(cl);
1179 cl->defmap = def&mask;
1181 cl->defmap = (cl->defmap&~mask)|(def&mask);
1183 cbq_sync_defmap(cl);
1186 static void cbq_unlink_class(struct cbq_class *this)
1188 struct cbq_class *cl, **clp;
1189 struct cbq_sched_data *q = qdisc_priv(this->qdisc);
1191 for (clp = &q->classes[cbq_hash(this->classid)]; (cl = *clp) != NULL; clp = &cl->next) {
1199 if (this->tparent) {
1208 } while ((cl = *clp) != this->sibling);
1210 if (this->tparent->children == this) {
1211 this->tparent->children = this->sibling;
1212 if (this->sibling == this)
1213 this->tparent->children = NULL;
1216 BUG_TRAP(this->sibling == this);
1220 static void cbq_link_class(struct cbq_class *this)
1222 struct cbq_sched_data *q = qdisc_priv(this->qdisc);
1223 unsigned h = cbq_hash(this->classid);
1224 struct cbq_class *parent = this->tparent;
1226 this->sibling = this;
1227 this->next = q->classes[h];
1228 q->classes[h] = this;
1233 if (parent->children == NULL) {
1234 parent->children = this;
1236 this->sibling = parent->children->sibling;
1237 parent->children->sibling = this;
1241 static unsigned int cbq_drop(struct Qdisc* sch)
1243 struct cbq_sched_data *q = qdisc_priv(sch);
1244 struct cbq_class *cl, *cl_head;
1248 for (prio = TC_CBQ_MAXPRIO; prio >= 0; prio--) {
1249 if ((cl_head = q->active[prio]) == NULL)
1254 if (cl->q->ops->drop && (len = cl->q->ops->drop(cl->q))) {
1257 cbq_deactivate_class(cl);
1260 } while ((cl = cl->next_alive) != cl_head);
1266 cbq_reset(struct Qdisc* sch)
1268 struct cbq_sched_data *q = qdisc_priv(sch);
1269 struct cbq_class *cl;
1276 q->tx_borrowed = NULL;
1277 qdisc_watchdog_cancel(&q->watchdog);
1278 hrtimer_cancel(&q->delay_timer);
1279 q->toplevel = TC_CBQ_MAXLEVEL;
1280 PSCHED_GET_TIME(q->now);
1283 for (prio = 0; prio <= TC_CBQ_MAXPRIO; prio++)
1284 q->active[prio] = NULL;
1286 for (h = 0; h < 16; h++) {
1287 for (cl = q->classes[h]; cl; cl = cl->next) {
1290 cl->next_alive = NULL;
1291 cl->undertime = PSCHED_PASTPERFECT;
1292 cl->avgidle = cl->maxidle;
1293 cl->deficit = cl->quantum;
1294 cl->cpriority = cl->priority;
1301 static int cbq_set_lss(struct cbq_class *cl, struct tc_cbq_lssopt *lss)
1303 if (lss->change&TCF_CBQ_LSS_FLAGS) {
1304 cl->share = (lss->flags&TCF_CBQ_LSS_ISOLATED) ? NULL : cl->tparent;
1305 cl->borrow = (lss->flags&TCF_CBQ_LSS_BOUNDED) ? NULL : cl->tparent;
1307 if (lss->change&TCF_CBQ_LSS_EWMA)
1308 cl->ewma_log = lss->ewma_log;
1309 if (lss->change&TCF_CBQ_LSS_AVPKT)
1310 cl->avpkt = lss->avpkt;
1311 if (lss->change&TCF_CBQ_LSS_MINIDLE)
1312 cl->minidle = -(long)lss->minidle;
1313 if (lss->change&TCF_CBQ_LSS_MAXIDLE) {
1314 cl->maxidle = lss->maxidle;
1315 cl->avgidle = lss->maxidle;
1317 if (lss->change&TCF_CBQ_LSS_OFFTIME)
1318 cl->offtime = lss->offtime;
1322 static void cbq_rmprio(struct cbq_sched_data *q, struct cbq_class *cl)
1324 q->nclasses[cl->priority]--;
1325 q->quanta[cl->priority] -= cl->weight;
1326 cbq_normalize_quanta(q, cl->priority);
1329 static void cbq_addprio(struct cbq_sched_data *q, struct cbq_class *cl)
1331 q->nclasses[cl->priority]++;
1332 q->quanta[cl->priority] += cl->weight;
1333 cbq_normalize_quanta(q, cl->priority);
1336 static int cbq_set_wrr(struct cbq_class *cl, struct tc_cbq_wrropt *wrr)
1338 struct cbq_sched_data *q = qdisc_priv(cl->qdisc);
1341 cl->allot = wrr->allot;
1343 cl->weight = wrr->weight;
1344 if (wrr->priority) {
1345 cl->priority = wrr->priority-1;
1346 cl->cpriority = cl->priority;
1347 if (cl->priority >= cl->priority2)
1348 cl->priority2 = TC_CBQ_MAXPRIO-1;
1355 static int cbq_set_overlimit(struct cbq_class *cl, struct tc_cbq_ovl *ovl)
1357 switch (ovl->strategy) {
1358 case TC_CBQ_OVL_CLASSIC:
1359 cl->overlimit = cbq_ovl_classic;
1361 case TC_CBQ_OVL_DELAY:
1362 cl->overlimit = cbq_ovl_delay;
1364 case TC_CBQ_OVL_LOWPRIO:
1365 if (ovl->priority2-1 >= TC_CBQ_MAXPRIO ||
1366 ovl->priority2-1 <= cl->priority)
1368 cl->priority2 = ovl->priority2-1;
1369 cl->overlimit = cbq_ovl_lowprio;
1371 case TC_CBQ_OVL_DROP:
1372 cl->overlimit = cbq_ovl_drop;
1374 case TC_CBQ_OVL_RCLASSIC:
1375 cl->overlimit = cbq_ovl_rclassic;
1380 cl->penalty = ovl->penalty;
1384 #ifdef CONFIG_NET_CLS_POLICE
1385 static int cbq_set_police(struct cbq_class *cl, struct tc_cbq_police *p)
1387 cl->police = p->police;
1389 if (cl->q->handle) {
1390 if (p->police == TC_POLICE_RECLASSIFY)
1391 cl->q->reshape_fail = cbq_reshape_fail;
1393 cl->q->reshape_fail = NULL;
1399 static int cbq_set_fopt(struct cbq_class *cl, struct tc_cbq_fopt *fopt)
1401 cbq_change_defmap(cl, fopt->split, fopt->defmap, fopt->defchange);
1405 static int cbq_init(struct Qdisc *sch, struct rtattr *opt)
1407 struct cbq_sched_data *q = qdisc_priv(sch);
1408 struct rtattr *tb[TCA_CBQ_MAX];
1409 struct tc_ratespec *r;
1411 if (rtattr_parse_nested(tb, TCA_CBQ_MAX, opt) < 0 ||
1412 tb[TCA_CBQ_RTAB-1] == NULL || tb[TCA_CBQ_RATE-1] == NULL ||
1413 RTA_PAYLOAD(tb[TCA_CBQ_RATE-1]) < sizeof(struct tc_ratespec))
1416 if (tb[TCA_CBQ_LSSOPT-1] &&
1417 RTA_PAYLOAD(tb[TCA_CBQ_LSSOPT-1]) < sizeof(struct tc_cbq_lssopt))
1420 r = RTA_DATA(tb[TCA_CBQ_RATE-1]);
1422 if ((q->link.R_tab = qdisc_get_rtab(r, tb[TCA_CBQ_RTAB-1])) == NULL)
1426 q->link.sibling = &q->link;
1427 q->link.classid = sch->handle;
1428 q->link.qdisc = sch;
1429 if (!(q->link.q = qdisc_create_dflt(sch->dev, &pfifo_qdisc_ops,
1431 q->link.q = &noop_qdisc;
1433 q->link.priority = TC_CBQ_MAXPRIO-1;
1434 q->link.priority2 = TC_CBQ_MAXPRIO-1;
1435 q->link.cpriority = TC_CBQ_MAXPRIO-1;
1436 q->link.ovl_strategy = TC_CBQ_OVL_CLASSIC;
1437 q->link.overlimit = cbq_ovl_classic;
1438 q->link.allot = psched_mtu(sch->dev);
1439 q->link.quantum = q->link.allot;
1440 q->link.weight = q->link.R_tab->rate.rate;
1442 q->link.ewma_log = TC_CBQ_DEF_EWMA;
1443 q->link.avpkt = q->link.allot/2;
1444 q->link.minidle = -0x7FFFFFFF;
1445 q->link.stats_lock = &sch->dev->queue_lock;
1447 qdisc_watchdog_init(&q->watchdog, sch);
1448 hrtimer_init(&q->delay_timer, CLOCK_MONOTONIC, HRTIMER_MODE_ABS);
1449 q->delay_timer.function = cbq_undelay;
1450 q->toplevel = TC_CBQ_MAXLEVEL;
1451 PSCHED_GET_TIME(q->now);
1454 cbq_link_class(&q->link);
1456 if (tb[TCA_CBQ_LSSOPT-1])
1457 cbq_set_lss(&q->link, RTA_DATA(tb[TCA_CBQ_LSSOPT-1]));
1459 cbq_addprio(q, &q->link);
1463 static __inline__ int cbq_dump_rate(struct sk_buff *skb, struct cbq_class *cl)
1465 unsigned char *b = skb_tail_pointer(skb);
1467 RTA_PUT(skb, TCA_CBQ_RATE, sizeof(cl->R_tab->rate), &cl->R_tab->rate);
1475 static __inline__ int cbq_dump_lss(struct sk_buff *skb, struct cbq_class *cl)
1477 unsigned char *b = skb_tail_pointer(skb);
1478 struct tc_cbq_lssopt opt;
1481 if (cl->borrow == NULL)
1482 opt.flags |= TCF_CBQ_LSS_BOUNDED;
1483 if (cl->share == NULL)
1484 opt.flags |= TCF_CBQ_LSS_ISOLATED;
1485 opt.ewma_log = cl->ewma_log;
1486 opt.level = cl->level;
1487 opt.avpkt = cl->avpkt;
1488 opt.maxidle = cl->maxidle;
1489 opt.minidle = (u32)(-cl->minidle);
1490 opt.offtime = cl->offtime;
1492 RTA_PUT(skb, TCA_CBQ_LSSOPT, sizeof(opt), &opt);
1500 static __inline__ int cbq_dump_wrr(struct sk_buff *skb, struct cbq_class *cl)
1502 unsigned char *b = skb_tail_pointer(skb);
1503 struct tc_cbq_wrropt opt;
1506 opt.allot = cl->allot;
1507 opt.priority = cl->priority+1;
1508 opt.cpriority = cl->cpriority+1;
1509 opt.weight = cl->weight;
1510 RTA_PUT(skb, TCA_CBQ_WRROPT, sizeof(opt), &opt);
1518 static __inline__ int cbq_dump_ovl(struct sk_buff *skb, struct cbq_class *cl)
1520 unsigned char *b = skb_tail_pointer(skb);
1521 struct tc_cbq_ovl opt;
1523 opt.strategy = cl->ovl_strategy;
1524 opt.priority2 = cl->priority2+1;
1526 opt.penalty = cl->penalty;
1527 RTA_PUT(skb, TCA_CBQ_OVL_STRATEGY, sizeof(opt), &opt);
1535 static __inline__ int cbq_dump_fopt(struct sk_buff *skb, struct cbq_class *cl)
1537 unsigned char *b = skb_tail_pointer(skb);
1538 struct tc_cbq_fopt opt;
1540 if (cl->split || cl->defmap) {
1541 opt.split = cl->split ? cl->split->classid : 0;
1542 opt.defmap = cl->defmap;
1544 RTA_PUT(skb, TCA_CBQ_FOPT, sizeof(opt), &opt);
1553 #ifdef CONFIG_NET_CLS_POLICE
1554 static __inline__ int cbq_dump_police(struct sk_buff *skb, struct cbq_class *cl)
1556 unsigned char *b = skb_tail_pointer(skb);
1557 struct tc_cbq_police opt;
1560 opt.police = cl->police;
1563 RTA_PUT(skb, TCA_CBQ_POLICE, sizeof(opt), &opt);
1573 static int cbq_dump_attr(struct sk_buff *skb, struct cbq_class *cl)
1575 if (cbq_dump_lss(skb, cl) < 0 ||
1576 cbq_dump_rate(skb, cl) < 0 ||
1577 cbq_dump_wrr(skb, cl) < 0 ||
1578 cbq_dump_ovl(skb, cl) < 0 ||
1579 #ifdef CONFIG_NET_CLS_POLICE
1580 cbq_dump_police(skb, cl) < 0 ||
1582 cbq_dump_fopt(skb, cl) < 0)
1587 static int cbq_dump(struct Qdisc *sch, struct sk_buff *skb)
1589 struct cbq_sched_data *q = qdisc_priv(sch);
1590 unsigned char *b = skb_tail_pointer(skb);
1593 rta = (struct rtattr*)b;
1594 RTA_PUT(skb, TCA_OPTIONS, 0, NULL);
1595 if (cbq_dump_attr(skb, &q->link) < 0)
1596 goto rtattr_failure;
1597 rta->rta_len = skb_tail_pointer(skb) - b;
1606 cbq_dump_stats(struct Qdisc *sch, struct gnet_dump *d)
1608 struct cbq_sched_data *q = qdisc_priv(sch);
1610 q->link.xstats.avgidle = q->link.avgidle;
1611 return gnet_stats_copy_app(d, &q->link.xstats, sizeof(q->link.xstats));
1615 cbq_dump_class(struct Qdisc *sch, unsigned long arg,
1616 struct sk_buff *skb, struct tcmsg *tcm)
1618 struct cbq_class *cl = (struct cbq_class*)arg;
1619 unsigned char *b = skb_tail_pointer(skb);
1623 tcm->tcm_parent = cl->tparent->classid;
1625 tcm->tcm_parent = TC_H_ROOT;
1626 tcm->tcm_handle = cl->classid;
1627 tcm->tcm_info = cl->q->handle;
1629 rta = (struct rtattr*)b;
1630 RTA_PUT(skb, TCA_OPTIONS, 0, NULL);
1631 if (cbq_dump_attr(skb, cl) < 0)
1632 goto rtattr_failure;
1633 rta->rta_len = skb_tail_pointer(skb) - b;
1642 cbq_dump_class_stats(struct Qdisc *sch, unsigned long arg,
1643 struct gnet_dump *d)
1645 struct cbq_sched_data *q = qdisc_priv(sch);
1646 struct cbq_class *cl = (struct cbq_class*)arg;
1648 cl->qstats.qlen = cl->q->q.qlen;
1649 cl->xstats.avgidle = cl->avgidle;
1650 cl->xstats.undertime = 0;
1652 if (cl->undertime != PSCHED_PASTPERFECT)
1653 cl->xstats.undertime = PSCHED_TDIFF(cl->undertime, q->now);
1655 if (gnet_stats_copy_basic(d, &cl->bstats) < 0 ||
1656 #ifdef CONFIG_NET_ESTIMATOR
1657 gnet_stats_copy_rate_est(d, &cl->rate_est) < 0 ||
1659 gnet_stats_copy_queue(d, &cl->qstats) < 0)
1662 return gnet_stats_copy_app(d, &cl->xstats, sizeof(cl->xstats));
1665 static int cbq_graft(struct Qdisc *sch, unsigned long arg, struct Qdisc *new,
1668 struct cbq_class *cl = (struct cbq_class*)arg;
1672 if ((new = qdisc_create_dflt(sch->dev, &pfifo_qdisc_ops,
1673 cl->classid)) == NULL)
1676 #ifdef CONFIG_NET_CLS_POLICE
1677 if (cl->police == TC_POLICE_RECLASSIFY)
1678 new->reshape_fail = cbq_reshape_fail;
1682 *old = xchg(&cl->q, new);
1683 qdisc_tree_decrease_qlen(*old, (*old)->q.qlen);
1685 sch_tree_unlock(sch);
1692 static struct Qdisc *
1693 cbq_leaf(struct Qdisc *sch, unsigned long arg)
1695 struct cbq_class *cl = (struct cbq_class*)arg;
1697 return cl ? cl->q : NULL;
1700 static void cbq_qlen_notify(struct Qdisc *sch, unsigned long arg)
1702 struct cbq_class *cl = (struct cbq_class *)arg;
1704 if (cl->q->q.qlen == 0)
1705 cbq_deactivate_class(cl);
1708 static unsigned long cbq_get(struct Qdisc *sch, u32 classid)
1710 struct cbq_sched_data *q = qdisc_priv(sch);
1711 struct cbq_class *cl = cbq_class_lookup(q, classid);
1715 return (unsigned long)cl;
1720 static void cbq_destroy_filters(struct cbq_class *cl)
1722 struct tcf_proto *tp;
1724 while ((tp = cl->filter_list) != NULL) {
1725 cl->filter_list = tp->next;
1730 static void cbq_destroy_class(struct Qdisc *sch, struct cbq_class *cl)
1732 struct cbq_sched_data *q = qdisc_priv(sch);
1734 BUG_TRAP(!cl->filters);
1736 cbq_destroy_filters(cl);
1737 qdisc_destroy(cl->q);
1738 qdisc_put_rtab(cl->R_tab);
1739 #ifdef CONFIG_NET_ESTIMATOR
1740 gen_kill_estimator(&cl->bstats, &cl->rate_est);
1747 cbq_destroy(struct Qdisc* sch)
1749 struct cbq_sched_data *q = qdisc_priv(sch);
1750 struct cbq_class *cl;
1753 #ifdef CONFIG_NET_CLS_POLICE
1757 * Filters must be destroyed first because we don't destroy the
1758 * classes from root to leafs which means that filters can still
1759 * be bound to classes which have been destroyed already. --TGR '04
1761 for (h = 0; h < 16; h++)
1762 for (cl = q->classes[h]; cl; cl = cl->next)
1763 cbq_destroy_filters(cl);
1765 for (h = 0; h < 16; h++) {
1766 struct cbq_class *next;
1768 for (cl = q->classes[h]; cl; cl = next) {
1770 cbq_destroy_class(sch, cl);
1775 static void cbq_put(struct Qdisc *sch, unsigned long arg)
1777 struct cbq_class *cl = (struct cbq_class*)arg;
1779 if (--cl->refcnt == 0) {
1780 #ifdef CONFIG_NET_CLS_POLICE
1781 struct cbq_sched_data *q = qdisc_priv(sch);
1783 spin_lock_bh(&sch->dev->queue_lock);
1784 if (q->rx_class == cl)
1786 spin_unlock_bh(&sch->dev->queue_lock);
1789 cbq_destroy_class(sch, cl);
1794 cbq_change_class(struct Qdisc *sch, u32 classid, u32 parentid, struct rtattr **tca,
1798 struct cbq_sched_data *q = qdisc_priv(sch);
1799 struct cbq_class *cl = (struct cbq_class*)*arg;
1800 struct rtattr *opt = tca[TCA_OPTIONS-1];
1801 struct rtattr *tb[TCA_CBQ_MAX];
1802 struct cbq_class *parent;
1803 struct qdisc_rate_table *rtab = NULL;
1805 if (opt==NULL || rtattr_parse_nested(tb, TCA_CBQ_MAX, opt))
1808 if (tb[TCA_CBQ_OVL_STRATEGY-1] &&
1809 RTA_PAYLOAD(tb[TCA_CBQ_OVL_STRATEGY-1]) < sizeof(struct tc_cbq_ovl))
1812 if (tb[TCA_CBQ_FOPT-1] &&
1813 RTA_PAYLOAD(tb[TCA_CBQ_FOPT-1]) < sizeof(struct tc_cbq_fopt))
1816 if (tb[TCA_CBQ_RATE-1] &&
1817 RTA_PAYLOAD(tb[TCA_CBQ_RATE-1]) < sizeof(struct tc_ratespec))
1820 if (tb[TCA_CBQ_LSSOPT-1] &&
1821 RTA_PAYLOAD(tb[TCA_CBQ_LSSOPT-1]) < sizeof(struct tc_cbq_lssopt))
1824 if (tb[TCA_CBQ_WRROPT-1] &&
1825 RTA_PAYLOAD(tb[TCA_CBQ_WRROPT-1]) < sizeof(struct tc_cbq_wrropt))
1828 #ifdef CONFIG_NET_CLS_POLICE
1829 if (tb[TCA_CBQ_POLICE-1] &&
1830 RTA_PAYLOAD(tb[TCA_CBQ_POLICE-1]) < sizeof(struct tc_cbq_police))
1837 if (cl->tparent && cl->tparent->classid != parentid)
1839 if (!cl->tparent && parentid != TC_H_ROOT)
1843 if (tb[TCA_CBQ_RATE-1]) {
1844 rtab = qdisc_get_rtab(RTA_DATA(tb[TCA_CBQ_RATE-1]), tb[TCA_CBQ_RTAB-1]);
1849 /* Change class parameters */
1852 if (cl->next_alive != NULL)
1853 cbq_deactivate_class(cl);
1856 rtab = xchg(&cl->R_tab, rtab);
1857 qdisc_put_rtab(rtab);
1860 if (tb[TCA_CBQ_LSSOPT-1])
1861 cbq_set_lss(cl, RTA_DATA(tb[TCA_CBQ_LSSOPT-1]));
1863 if (tb[TCA_CBQ_WRROPT-1]) {
1865 cbq_set_wrr(cl, RTA_DATA(tb[TCA_CBQ_WRROPT-1]));
1868 if (tb[TCA_CBQ_OVL_STRATEGY-1])
1869 cbq_set_overlimit(cl, RTA_DATA(tb[TCA_CBQ_OVL_STRATEGY-1]));
1871 #ifdef CONFIG_NET_CLS_POLICE
1872 if (tb[TCA_CBQ_POLICE-1])
1873 cbq_set_police(cl, RTA_DATA(tb[TCA_CBQ_POLICE-1]));
1876 if (tb[TCA_CBQ_FOPT-1])
1877 cbq_set_fopt(cl, RTA_DATA(tb[TCA_CBQ_FOPT-1]));
1880 cbq_activate_class(cl);
1882 sch_tree_unlock(sch);
1884 #ifdef CONFIG_NET_ESTIMATOR
1885 if (tca[TCA_RATE-1])
1886 gen_replace_estimator(&cl->bstats, &cl->rate_est,
1887 cl->stats_lock, tca[TCA_RATE-1]);
1892 if (parentid == TC_H_ROOT)
1895 if (tb[TCA_CBQ_WRROPT-1] == NULL || tb[TCA_CBQ_RATE-1] == NULL ||
1896 tb[TCA_CBQ_LSSOPT-1] == NULL)
1899 rtab = qdisc_get_rtab(RTA_DATA(tb[TCA_CBQ_RATE-1]), tb[TCA_CBQ_RTAB-1]);
1905 if (TC_H_MAJ(classid^sch->handle) || cbq_class_lookup(q, classid))
1909 classid = TC_H_MAKE(sch->handle,0x8000);
1911 for (i=0; i<0x8000; i++) {
1912 if (++q->hgenerator >= 0x8000)
1914 if (cbq_class_lookup(q, classid|q->hgenerator) == NULL)
1920 classid = classid|q->hgenerator;
1925 parent = cbq_class_lookup(q, parentid);
1932 cl = kzalloc(sizeof(*cl), GFP_KERNEL);
1938 if (!(cl->q = qdisc_create_dflt(sch->dev, &pfifo_qdisc_ops, classid)))
1939 cl->q = &noop_qdisc;
1940 cl->classid = classid;
1941 cl->tparent = parent;
1943 cl->allot = parent->allot;
1944 cl->quantum = cl->allot;
1945 cl->weight = cl->R_tab->rate.rate;
1946 cl->stats_lock = &sch->dev->queue_lock;
1950 cl->borrow = cl->tparent;
1951 if (cl->tparent != &q->link)
1952 cl->share = cl->tparent;
1953 cbq_adjust_levels(parent);
1954 cl->minidle = -0x7FFFFFFF;
1955 cbq_set_lss(cl, RTA_DATA(tb[TCA_CBQ_LSSOPT-1]));
1956 cbq_set_wrr(cl, RTA_DATA(tb[TCA_CBQ_WRROPT-1]));
1957 if (cl->ewma_log==0)
1958 cl->ewma_log = q->link.ewma_log;
1960 cl->maxidle = q->link.maxidle;
1962 cl->avpkt = q->link.avpkt;
1963 cl->overlimit = cbq_ovl_classic;
1964 if (tb[TCA_CBQ_OVL_STRATEGY-1])
1965 cbq_set_overlimit(cl, RTA_DATA(tb[TCA_CBQ_OVL_STRATEGY-1]));
1966 #ifdef CONFIG_NET_CLS_POLICE
1967 if (tb[TCA_CBQ_POLICE-1])
1968 cbq_set_police(cl, RTA_DATA(tb[TCA_CBQ_POLICE-1]));
1970 if (tb[TCA_CBQ_FOPT-1])
1971 cbq_set_fopt(cl, RTA_DATA(tb[TCA_CBQ_FOPT-1]));
1972 sch_tree_unlock(sch);
1974 #ifdef CONFIG_NET_ESTIMATOR
1975 if (tca[TCA_RATE-1])
1976 gen_new_estimator(&cl->bstats, &cl->rate_est,
1977 cl->stats_lock, tca[TCA_RATE-1]);
1980 *arg = (unsigned long)cl;
1984 qdisc_put_rtab(rtab);
1988 static int cbq_delete(struct Qdisc *sch, unsigned long arg)
1990 struct cbq_sched_data *q = qdisc_priv(sch);
1991 struct cbq_class *cl = (struct cbq_class*)arg;
1994 if (cl->filters || cl->children || cl == &q->link)
1999 qlen = cl->q->q.qlen;
2001 qdisc_tree_decrease_qlen(cl->q, qlen);
2004 cbq_deactivate_class(cl);
2006 if (q->tx_borrowed == cl)
2007 q->tx_borrowed = q->tx_class;
2008 if (q->tx_class == cl) {
2010 q->tx_borrowed = NULL;
2012 #ifdef CONFIG_NET_CLS_POLICE
2013 if (q->rx_class == cl)
2017 cbq_unlink_class(cl);
2018 cbq_adjust_levels(cl->tparent);
2020 cbq_sync_defmap(cl);
2023 sch_tree_unlock(sch);
2025 if (--cl->refcnt == 0)
2026 cbq_destroy_class(sch, cl);
2031 static struct tcf_proto **cbq_find_tcf(struct Qdisc *sch, unsigned long arg)
2033 struct cbq_sched_data *q = qdisc_priv(sch);
2034 struct cbq_class *cl = (struct cbq_class *)arg;
2039 return &cl->filter_list;
2042 static unsigned long cbq_bind_filter(struct Qdisc *sch, unsigned long parent,
2045 struct cbq_sched_data *q = qdisc_priv(sch);
2046 struct cbq_class *p = (struct cbq_class*)parent;
2047 struct cbq_class *cl = cbq_class_lookup(q, classid);
2050 if (p && p->level <= cl->level)
2053 return (unsigned long)cl;
2058 static void cbq_unbind_filter(struct Qdisc *sch, unsigned long arg)
2060 struct cbq_class *cl = (struct cbq_class*)arg;
2065 static void cbq_walk(struct Qdisc *sch, struct qdisc_walker *arg)
2067 struct cbq_sched_data *q = qdisc_priv(sch);
2073 for (h = 0; h < 16; h++) {
2074 struct cbq_class *cl;
2076 for (cl = q->classes[h]; cl; cl = cl->next) {
2077 if (arg->count < arg->skip) {
2081 if (arg->fn(sch, (unsigned long)cl, arg) < 0) {
2090 static struct Qdisc_class_ops cbq_class_ops = {
2093 .qlen_notify = cbq_qlen_notify,
2096 .change = cbq_change_class,
2097 .delete = cbq_delete,
2099 .tcf_chain = cbq_find_tcf,
2100 .bind_tcf = cbq_bind_filter,
2101 .unbind_tcf = cbq_unbind_filter,
2102 .dump = cbq_dump_class,
2103 .dump_stats = cbq_dump_class_stats,
2106 static struct Qdisc_ops cbq_qdisc_ops = {
2108 .cl_ops = &cbq_class_ops,
2110 .priv_size = sizeof(struct cbq_sched_data),
2111 .enqueue = cbq_enqueue,
2112 .dequeue = cbq_dequeue,
2113 .requeue = cbq_requeue,
2117 .destroy = cbq_destroy,
2120 .dump_stats = cbq_dump_stats,
2121 .owner = THIS_MODULE,
2124 static int __init cbq_module_init(void)
2126 return register_qdisc(&cbq_qdisc_ops);
2128 static void __exit cbq_module_exit(void)
2130 unregister_qdisc(&cbq_qdisc_ops);
2132 module_init(cbq_module_init)
2133 module_exit(cbq_module_exit)
2134 MODULE_LICENSE("GPL");