Loading...
1// SPDX-License-Identifier: GPL-2.0-or-later
2/*
3 * net/sched/sch_cbq.c Class-Based Queueing discipline.
4 *
5 * Authors: Alexey Kuznetsov, <kuznet@ms2.inr.ac.ru>
6 */
7
8#include <linux/module.h>
9#include <linux/slab.h>
10#include <linux/types.h>
11#include <linux/kernel.h>
12#include <linux/string.h>
13#include <linux/errno.h>
14#include <linux/skbuff.h>
15#include <net/netlink.h>
16#include <net/pkt_sched.h>
17#include <net/pkt_cls.h>
18
19
20/* Class-Based Queueing (CBQ) algorithm.
21 =======================================
22
23 Sources: [1] Sally Floyd and Van Jacobson, "Link-sharing and Resource
24 Management Models for Packet Networks",
25 IEEE/ACM Transactions on Networking, Vol.3, No.4, 1995
26
27 [2] Sally Floyd, "Notes on CBQ and Guaranteed Service", 1995
28
29 [3] Sally Floyd, "Notes on Class-Based Queueing: Setting
30 Parameters", 1996
31
32 [4] Sally Floyd and Michael Speer, "Experimental Results
33 for Class-Based Queueing", 1998, not published.
34
35 -----------------------------------------------------------------------
36
37 Algorithm skeleton was taken from NS simulator cbq.cc.
38 If someone wants to check this code against the LBL version,
39 he should take into account that ONLY the skeleton was borrowed,
40 the implementation is different. Particularly:
41
42 --- The WRR algorithm is different. Our version looks more
43 reasonable (I hope) and works when quanta are allowed to be
44 less than MTU, which is always the case when real time classes
45 have small rates. Note, that the statement of [3] is
46 incomplete, delay may actually be estimated even if class
47 per-round allotment is less than MTU. Namely, if per-round
48 allotment is W*r_i, and r_1+...+r_k = r < 1
49
50 delay_i <= ([MTU/(W*r_i)]*W*r + W*r + k*MTU)/B
51
52 In the worst case we have IntServ estimate with D = W*r+k*MTU
53 and C = MTU*r. The proof (if correct at all) is trivial.
54
55
56 --- It seems that cbq-2.0 is not very accurate. At least, I cannot
57 interpret some places, which look like wrong translations
58 from NS. Anyone is advised to find these differences
59 and explain to me, why I am wrong 8).
60
61 --- Linux has no EOI event, so that we cannot estimate true class
62 idle time. Workaround is to consider the next dequeue event
63 as sign that previous packet is finished. This is wrong because of
64 internal device queueing, but on a permanently loaded link it is true.
65 Moreover, combined with clock integrator, this scheme looks
66 very close to an ideal solution. */
67
68struct cbq_sched_data;
69
70
71struct cbq_class {
72 struct Qdisc_class_common common;
73 struct cbq_class *next_alive; /* next class with backlog in this priority band */
74
75/* Parameters */
76 unsigned char priority; /* class priority */
77 unsigned char priority2; /* priority to be used after overlimit */
78 unsigned char ewma_log; /* time constant for idle time calculation */
79
80 u32 defmap;
81
82 /* Link-sharing scheduler parameters */
83 long maxidle; /* Class parameters: see below. */
84 long offtime;
85 long minidle;
86 u32 avpkt;
87 struct qdisc_rate_table *R_tab;
88
89 /* General scheduler (WRR) parameters */
90 long allot;
91 long quantum; /* Allotment per WRR round */
92 long weight; /* Relative allotment: see below */
93
94 struct Qdisc *qdisc; /* Ptr to CBQ discipline */
95 struct cbq_class *split; /* Ptr to split node */
96 struct cbq_class *share; /* Ptr to LS parent in the class tree */
97 struct cbq_class *tparent; /* Ptr to tree parent in the class tree */
98 struct cbq_class *borrow; /* NULL if class is bandwidth limited;
99 parent otherwise */
100 struct cbq_class *sibling; /* Sibling chain */
101 struct cbq_class *children; /* Pointer to children chain */
102
103 struct Qdisc *q; /* Elementary queueing discipline */
104
105
106/* Variables */
107 unsigned char cpriority; /* Effective priority */
108 unsigned char delayed;
109 unsigned char level; /* level of the class in hierarchy:
110 0 for leaf classes, and maximal
111 level of children + 1 for nodes.
112 */
113
114 psched_time_t last; /* Last end of service */
115 psched_time_t undertime;
116 long avgidle;
117 long deficit; /* Saved deficit for WRR */
118 psched_time_t penalized;
119 struct gnet_stats_basic_packed bstats;
120 struct gnet_stats_queue qstats;
121 struct net_rate_estimator __rcu *rate_est;
122 struct tc_cbq_xstats xstats;
123
124 struct tcf_proto __rcu *filter_list;
125 struct tcf_block *block;
126
127 int filters;
128
129 struct cbq_class *defaults[TC_PRIO_MAX + 1];
130};
131
132struct cbq_sched_data {
133 struct Qdisc_class_hash clhash; /* Hash table of all classes */
134 int nclasses[TC_CBQ_MAXPRIO + 1];
135 unsigned int quanta[TC_CBQ_MAXPRIO + 1];
136
137 struct cbq_class link;
138
139 unsigned int activemask;
140 struct cbq_class *active[TC_CBQ_MAXPRIO + 1]; /* List of all classes
141 with backlog */
142
143#ifdef CONFIG_NET_CLS_ACT
144 struct cbq_class *rx_class;
145#endif
146 struct cbq_class *tx_class;
147 struct cbq_class *tx_borrowed;
148 int tx_len;
149 psched_time_t now; /* Cached timestamp */
150 unsigned int pmask;
151
152 struct hrtimer delay_timer;
153 struct qdisc_watchdog watchdog; /* Watchdog timer,
154 started when CBQ has
155 backlog, but cannot
156 transmit just now */
157 psched_tdiff_t wd_expires;
158 int toplevel;
159 u32 hgenerator;
160};
161
162
163#define L2T(cl, len) qdisc_l2t((cl)->R_tab, len)
164
165static inline struct cbq_class *
166cbq_class_lookup(struct cbq_sched_data *q, u32 classid)
167{
168 struct Qdisc_class_common *clc;
169
170 clc = qdisc_class_find(&q->clhash, classid);
171 if (clc == NULL)
172 return NULL;
173 return container_of(clc, struct cbq_class, common);
174}
175
176#ifdef CONFIG_NET_CLS_ACT
177
178static struct cbq_class *
179cbq_reclassify(struct sk_buff *skb, struct cbq_class *this)
180{
181 struct cbq_class *cl;
182
183 for (cl = this->tparent; cl; cl = cl->tparent) {
184 struct cbq_class *new = cl->defaults[TC_PRIO_BESTEFFORT];
185
186 if (new != NULL && new != this)
187 return new;
188 }
189 return NULL;
190}
191
192#endif
193
194/* Classify packet. The procedure is pretty complicated, but
195 * it allows us to combine link sharing and priority scheduling
196 * transparently.
197 *
198 * Namely, you can put link sharing rules (f.e. route based) at root of CBQ,
199 * so that it resolves to split nodes. Then packets are classified
200 * by logical priority, or a more specific classifier may be attached
201 * to the split node.
202 */
203
204static struct cbq_class *
205cbq_classify(struct sk_buff *skb, struct Qdisc *sch, int *qerr)
206{
207 struct cbq_sched_data *q = qdisc_priv(sch);
208 struct cbq_class *head = &q->link;
209 struct cbq_class **defmap;
210 struct cbq_class *cl = NULL;
211 u32 prio = skb->priority;
212 struct tcf_proto *fl;
213 struct tcf_result res;
214
215 /*
216 * Step 1. If skb->priority points to one of our classes, use it.
217 */
218 if (TC_H_MAJ(prio ^ sch->handle) == 0 &&
219 (cl = cbq_class_lookup(q, prio)) != NULL)
220 return cl;
221
222 *qerr = NET_XMIT_SUCCESS | __NET_XMIT_BYPASS;
223 for (;;) {
224 int result = 0;
225 defmap = head->defaults;
226
227 fl = rcu_dereference_bh(head->filter_list);
228 /*
229 * Step 2+n. Apply classifier.
230 */
231 result = tcf_classify(skb, fl, &res, true);
232 if (!fl || result < 0)
233 goto fallback;
234
235 cl = (void *)res.class;
236 if (!cl) {
237 if (TC_H_MAJ(res.classid))
238 cl = cbq_class_lookup(q, res.classid);
239 else if ((cl = defmap[res.classid & TC_PRIO_MAX]) == NULL)
240 cl = defmap[TC_PRIO_BESTEFFORT];
241
242 if (cl == NULL)
243 goto fallback;
244 }
245 if (cl->level >= head->level)
246 goto fallback;
247#ifdef CONFIG_NET_CLS_ACT
248 switch (result) {
249 case TC_ACT_QUEUED:
250 case TC_ACT_STOLEN:
251 case TC_ACT_TRAP:
252 *qerr = NET_XMIT_SUCCESS | __NET_XMIT_STOLEN;
253 /* fall through */
254 case TC_ACT_SHOT:
255 return NULL;
256 case TC_ACT_RECLASSIFY:
257 return cbq_reclassify(skb, cl);
258 }
259#endif
260 if (cl->level == 0)
261 return cl;
262
263 /*
264 * Step 3+n. If classifier selected a link sharing class,
265 * apply agency specific classifier.
266 * Repeat this procdure until we hit a leaf node.
267 */
268 head = cl;
269 }
270
271fallback:
272 cl = head;
273
274 /*
275 * Step 4. No success...
276 */
277 if (TC_H_MAJ(prio) == 0 &&
278 !(cl = head->defaults[prio & TC_PRIO_MAX]) &&
279 !(cl = head->defaults[TC_PRIO_BESTEFFORT]))
280 return head;
281
282 return cl;
283}
284
285/*
286 * A packet has just been enqueued on the empty class.
287 * cbq_activate_class adds it to the tail of active class list
288 * of its priority band.
289 */
290
291static inline void cbq_activate_class(struct cbq_class *cl)
292{
293 struct cbq_sched_data *q = qdisc_priv(cl->qdisc);
294 int prio = cl->cpriority;
295 struct cbq_class *cl_tail;
296
297 cl_tail = q->active[prio];
298 q->active[prio] = cl;
299
300 if (cl_tail != NULL) {
301 cl->next_alive = cl_tail->next_alive;
302 cl_tail->next_alive = cl;
303 } else {
304 cl->next_alive = cl;
305 q->activemask |= (1<<prio);
306 }
307}
308
309/*
310 * Unlink class from active chain.
311 * Note that this same procedure is done directly in cbq_dequeue*
312 * during round-robin procedure.
313 */
314
315static void cbq_deactivate_class(struct cbq_class *this)
316{
317 struct cbq_sched_data *q = qdisc_priv(this->qdisc);
318 int prio = this->cpriority;
319 struct cbq_class *cl;
320 struct cbq_class *cl_prev = q->active[prio];
321
322 do {
323 cl = cl_prev->next_alive;
324 if (cl == this) {
325 cl_prev->next_alive = cl->next_alive;
326 cl->next_alive = NULL;
327
328 if (cl == q->active[prio]) {
329 q->active[prio] = cl_prev;
330 if (cl == q->active[prio]) {
331 q->active[prio] = NULL;
332 q->activemask &= ~(1<<prio);
333 return;
334 }
335 }
336 return;
337 }
338 } while ((cl_prev = cl) != q->active[prio]);
339}
340
341static void
342cbq_mark_toplevel(struct cbq_sched_data *q, struct cbq_class *cl)
343{
344 int toplevel = q->toplevel;
345
346 if (toplevel > cl->level) {
347 psched_time_t now = psched_get_time();
348
349 do {
350 if (cl->undertime < now) {
351 q->toplevel = cl->level;
352 return;
353 }
354 } while ((cl = cl->borrow) != NULL && toplevel > cl->level);
355 }
356}
357
358static int
359cbq_enqueue(struct sk_buff *skb, struct Qdisc *sch,
360 struct sk_buff **to_free)
361{
362 struct cbq_sched_data *q = qdisc_priv(sch);
363 int uninitialized_var(ret);
364 struct cbq_class *cl = cbq_classify(skb, sch, &ret);
365
366#ifdef CONFIG_NET_CLS_ACT
367 q->rx_class = cl;
368#endif
369 if (cl == NULL) {
370 if (ret & __NET_XMIT_BYPASS)
371 qdisc_qstats_drop(sch);
372 __qdisc_drop(skb, to_free);
373 return ret;
374 }
375
376 ret = qdisc_enqueue(skb, cl->q, to_free);
377 if (ret == NET_XMIT_SUCCESS) {
378 sch->q.qlen++;
379 cbq_mark_toplevel(q, cl);
380 if (!cl->next_alive)
381 cbq_activate_class(cl);
382 return ret;
383 }
384
385 if (net_xmit_drop_count(ret)) {
386 qdisc_qstats_drop(sch);
387 cbq_mark_toplevel(q, cl);
388 cl->qstats.drops++;
389 }
390 return ret;
391}
392
393/* Overlimit action: penalize leaf class by adding offtime */
394static void cbq_overlimit(struct cbq_class *cl)
395{
396 struct cbq_sched_data *q = qdisc_priv(cl->qdisc);
397 psched_tdiff_t delay = cl->undertime - q->now;
398
399 if (!cl->delayed) {
400 delay += cl->offtime;
401
402 /*
403 * Class goes to sleep, so that it will have no
404 * chance to work avgidle. Let's forgive it 8)
405 *
406 * BTW cbq-2.0 has a crap in this
407 * place, apparently they forgot to shift it by cl->ewma_log.
408 */
409 if (cl->avgidle < 0)
410 delay -= (-cl->avgidle) - ((-cl->avgidle) >> cl->ewma_log);
411 if (cl->avgidle < cl->minidle)
412 cl->avgidle = cl->minidle;
413 if (delay <= 0)
414 delay = 1;
415 cl->undertime = q->now + delay;
416
417 cl->xstats.overactions++;
418 cl->delayed = 1;
419 }
420 if (q->wd_expires == 0 || q->wd_expires > delay)
421 q->wd_expires = delay;
422
423 /* Dirty work! We must schedule wakeups based on
424 * real available rate, rather than leaf rate,
425 * which may be tiny (even zero).
426 */
427 if (q->toplevel == TC_CBQ_MAXLEVEL) {
428 struct cbq_class *b;
429 psched_tdiff_t base_delay = q->wd_expires;
430
431 for (b = cl->borrow; b; b = b->borrow) {
432 delay = b->undertime - q->now;
433 if (delay < base_delay) {
434 if (delay <= 0)
435 delay = 1;
436 base_delay = delay;
437 }
438 }
439
440 q->wd_expires = base_delay;
441 }
442}
443
444static psched_tdiff_t cbq_undelay_prio(struct cbq_sched_data *q, int prio,
445 psched_time_t now)
446{
447 struct cbq_class *cl;
448 struct cbq_class *cl_prev = q->active[prio];
449 psched_time_t sched = now;
450
451 if (cl_prev == NULL)
452 return 0;
453
454 do {
455 cl = cl_prev->next_alive;
456 if (now - cl->penalized > 0) {
457 cl_prev->next_alive = cl->next_alive;
458 cl->next_alive = NULL;
459 cl->cpriority = cl->priority;
460 cl->delayed = 0;
461 cbq_activate_class(cl);
462
463 if (cl == q->active[prio]) {
464 q->active[prio] = cl_prev;
465 if (cl == q->active[prio]) {
466 q->active[prio] = NULL;
467 return 0;
468 }
469 }
470
471 cl = cl_prev->next_alive;
472 } else if (sched - cl->penalized > 0)
473 sched = cl->penalized;
474 } while ((cl_prev = cl) != q->active[prio]);
475
476 return sched - now;
477}
478
479static enum hrtimer_restart cbq_undelay(struct hrtimer *timer)
480{
481 struct cbq_sched_data *q = container_of(timer, struct cbq_sched_data,
482 delay_timer);
483 struct Qdisc *sch = q->watchdog.qdisc;
484 psched_time_t now;
485 psched_tdiff_t delay = 0;
486 unsigned int pmask;
487
488 now = psched_get_time();
489
490 pmask = q->pmask;
491 q->pmask = 0;
492
493 while (pmask) {
494 int prio = ffz(~pmask);
495 psched_tdiff_t tmp;
496
497 pmask &= ~(1<<prio);
498
499 tmp = cbq_undelay_prio(q, prio, now);
500 if (tmp > 0) {
501 q->pmask |= 1<<prio;
502 if (tmp < delay || delay == 0)
503 delay = tmp;
504 }
505 }
506
507 if (delay) {
508 ktime_t time;
509
510 time = 0;
511 time = ktime_add_ns(time, PSCHED_TICKS2NS(now + delay));
512 hrtimer_start(&q->delay_timer, time, HRTIMER_MODE_ABS_PINNED);
513 }
514
515 __netif_schedule(qdisc_root(sch));
516 return HRTIMER_NORESTART;
517}
518
519/*
520 * It is mission critical procedure.
521 *
522 * We "regenerate" toplevel cutoff, if transmitting class
523 * has backlog and it is not regulated. It is not part of
524 * original CBQ description, but looks more reasonable.
525 * Probably, it is wrong. This question needs further investigation.
526 */
527
528static inline void
529cbq_update_toplevel(struct cbq_sched_data *q, struct cbq_class *cl,
530 struct cbq_class *borrowed)
531{
532 if (cl && q->toplevel >= borrowed->level) {
533 if (cl->q->q.qlen > 1) {
534 do {
535 if (borrowed->undertime == PSCHED_PASTPERFECT) {
536 q->toplevel = borrowed->level;
537 return;
538 }
539 } while ((borrowed = borrowed->borrow) != NULL);
540 }
541#if 0
542 /* It is not necessary now. Uncommenting it
543 will save CPU cycles, but decrease fairness.
544 */
545 q->toplevel = TC_CBQ_MAXLEVEL;
546#endif
547 }
548}
549
550static void
551cbq_update(struct cbq_sched_data *q)
552{
553 struct cbq_class *this = q->tx_class;
554 struct cbq_class *cl = this;
555 int len = q->tx_len;
556 psched_time_t now;
557
558 q->tx_class = NULL;
559 /* Time integrator. We calculate EOS time
560 * by adding expected packet transmission time.
561 */
562 now = q->now + L2T(&q->link, len);
563
564 for ( ; cl; cl = cl->share) {
565 long avgidle = cl->avgidle;
566 long idle;
567
568 cl->bstats.packets++;
569 cl->bstats.bytes += len;
570
571 /*
572 * (now - last) is total time between packet right edges.
573 * (last_pktlen/rate) is "virtual" busy time, so that
574 *
575 * idle = (now - last) - last_pktlen/rate
576 */
577
578 idle = now - cl->last;
579 if ((unsigned long)idle > 128*1024*1024) {
580 avgidle = cl->maxidle;
581 } else {
582 idle -= L2T(cl, len);
583
584 /* true_avgidle := (1-W)*true_avgidle + W*idle,
585 * where W=2^{-ewma_log}. But cl->avgidle is scaled:
586 * cl->avgidle == true_avgidle/W,
587 * hence:
588 */
589 avgidle += idle - (avgidle>>cl->ewma_log);
590 }
591
592 if (avgidle <= 0) {
593 /* Overlimit or at-limit */
594
595 if (avgidle < cl->minidle)
596 avgidle = cl->minidle;
597
598 cl->avgidle = avgidle;
599
600 /* Calculate expected time, when this class
601 * will be allowed to send.
602 * It will occur, when:
603 * (1-W)*true_avgidle + W*delay = 0, i.e.
604 * idle = (1/W - 1)*(-true_avgidle)
605 * or
606 * idle = (1 - W)*(-cl->avgidle);
607 */
608 idle = (-avgidle) - ((-avgidle) >> cl->ewma_log);
609
610 /*
611 * That is not all.
612 * To maintain the rate allocated to the class,
613 * we add to undertime virtual clock,
614 * necessary to complete transmitted packet.
615 * (len/phys_bandwidth has been already passed
616 * to the moment of cbq_update)
617 */
618
619 idle -= L2T(&q->link, len);
620 idle += L2T(cl, len);
621
622 cl->undertime = now + idle;
623 } else {
624 /* Underlimit */
625
626 cl->undertime = PSCHED_PASTPERFECT;
627 if (avgidle > cl->maxidle)
628 cl->avgidle = cl->maxidle;
629 else
630 cl->avgidle = avgidle;
631 }
632 if ((s64)(now - cl->last) > 0)
633 cl->last = now;
634 }
635
636 cbq_update_toplevel(q, this, q->tx_borrowed);
637}
638
639static inline struct cbq_class *
640cbq_under_limit(struct cbq_class *cl)
641{
642 struct cbq_sched_data *q = qdisc_priv(cl->qdisc);
643 struct cbq_class *this_cl = cl;
644
645 if (cl->tparent == NULL)
646 return cl;
647
648 if (cl->undertime == PSCHED_PASTPERFECT || q->now >= cl->undertime) {
649 cl->delayed = 0;
650 return cl;
651 }
652
653 do {
654 /* It is very suspicious place. Now overlimit
655 * action is generated for not bounded classes
656 * only if link is completely congested.
657 * Though it is in agree with ancestor-only paradigm,
658 * it looks very stupid. Particularly,
659 * it means that this chunk of code will either
660 * never be called or result in strong amplification
661 * of burstiness. Dangerous, silly, and, however,
662 * no another solution exists.
663 */
664 cl = cl->borrow;
665 if (!cl) {
666 this_cl->qstats.overlimits++;
667 cbq_overlimit(this_cl);
668 return NULL;
669 }
670 if (cl->level > q->toplevel)
671 return NULL;
672 } while (cl->undertime != PSCHED_PASTPERFECT && q->now < cl->undertime);
673
674 cl->delayed = 0;
675 return cl;
676}
677
678static inline struct sk_buff *
679cbq_dequeue_prio(struct Qdisc *sch, int prio)
680{
681 struct cbq_sched_data *q = qdisc_priv(sch);
682 struct cbq_class *cl_tail, *cl_prev, *cl;
683 struct sk_buff *skb;
684 int deficit;
685
686 cl_tail = cl_prev = q->active[prio];
687 cl = cl_prev->next_alive;
688
689 do {
690 deficit = 0;
691
692 /* Start round */
693 do {
694 struct cbq_class *borrow = cl;
695
696 if (cl->q->q.qlen &&
697 (borrow = cbq_under_limit(cl)) == NULL)
698 goto skip_class;
699
700 if (cl->deficit <= 0) {
701 /* Class exhausted its allotment per
702 * this round. Switch to the next one.
703 */
704 deficit = 1;
705 cl->deficit += cl->quantum;
706 goto next_class;
707 }
708
709 skb = cl->q->dequeue(cl->q);
710
711 /* Class did not give us any skb :-(
712 * It could occur even if cl->q->q.qlen != 0
713 * f.e. if cl->q == "tbf"
714 */
715 if (skb == NULL)
716 goto skip_class;
717
718 cl->deficit -= qdisc_pkt_len(skb);
719 q->tx_class = cl;
720 q->tx_borrowed = borrow;
721 if (borrow != cl) {
722#ifndef CBQ_XSTATS_BORROWS_BYTES
723 borrow->xstats.borrows++;
724 cl->xstats.borrows++;
725#else
726 borrow->xstats.borrows += qdisc_pkt_len(skb);
727 cl->xstats.borrows += qdisc_pkt_len(skb);
728#endif
729 }
730 q->tx_len = qdisc_pkt_len(skb);
731
732 if (cl->deficit <= 0) {
733 q->active[prio] = cl;
734 cl = cl->next_alive;
735 cl->deficit += cl->quantum;
736 }
737 return skb;
738
739skip_class:
740 if (cl->q->q.qlen == 0 || prio != cl->cpriority) {
741 /* Class is empty or penalized.
742 * Unlink it from active chain.
743 */
744 cl_prev->next_alive = cl->next_alive;
745 cl->next_alive = NULL;
746
747 /* Did cl_tail point to it? */
748 if (cl == cl_tail) {
749 /* Repair it! */
750 cl_tail = cl_prev;
751
752 /* Was it the last class in this band? */
753 if (cl == cl_tail) {
754 /* Kill the band! */
755 q->active[prio] = NULL;
756 q->activemask &= ~(1<<prio);
757 if (cl->q->q.qlen)
758 cbq_activate_class(cl);
759 return NULL;
760 }
761
762 q->active[prio] = cl_tail;
763 }
764 if (cl->q->q.qlen)
765 cbq_activate_class(cl);
766
767 cl = cl_prev;
768 }
769
770next_class:
771 cl_prev = cl;
772 cl = cl->next_alive;
773 } while (cl_prev != cl_tail);
774 } while (deficit);
775
776 q->active[prio] = cl_prev;
777
778 return NULL;
779}
780
781static inline struct sk_buff *
782cbq_dequeue_1(struct Qdisc *sch)
783{
784 struct cbq_sched_data *q = qdisc_priv(sch);
785 struct sk_buff *skb;
786 unsigned int activemask;
787
788 activemask = q->activemask & 0xFF;
789 while (activemask) {
790 int prio = ffz(~activemask);
791 activemask &= ~(1<<prio);
792 skb = cbq_dequeue_prio(sch, prio);
793 if (skb)
794 return skb;
795 }
796 return NULL;
797}
798
799static struct sk_buff *
800cbq_dequeue(struct Qdisc *sch)
801{
802 struct sk_buff *skb;
803 struct cbq_sched_data *q = qdisc_priv(sch);
804 psched_time_t now;
805
806 now = psched_get_time();
807
808 if (q->tx_class)
809 cbq_update(q);
810
811 q->now = now;
812
813 for (;;) {
814 q->wd_expires = 0;
815
816 skb = cbq_dequeue_1(sch);
817 if (skb) {
818 qdisc_bstats_update(sch, skb);
819 sch->q.qlen--;
820 return skb;
821 }
822
823 /* All the classes are overlimit.
824 *
825 * It is possible, if:
826 *
827 * 1. Scheduler is empty.
828 * 2. Toplevel cutoff inhibited borrowing.
829 * 3. Root class is overlimit.
830 *
831 * Reset 2d and 3d conditions and retry.
832 *
833 * Note, that NS and cbq-2.0 are buggy, peeking
834 * an arbitrary class is appropriate for ancestor-only
835 * sharing, but not for toplevel algorithm.
836 *
837 * Our version is better, but slower, because it requires
838 * two passes, but it is unavoidable with top-level sharing.
839 */
840
841 if (q->toplevel == TC_CBQ_MAXLEVEL &&
842 q->link.undertime == PSCHED_PASTPERFECT)
843 break;
844
845 q->toplevel = TC_CBQ_MAXLEVEL;
846 q->link.undertime = PSCHED_PASTPERFECT;
847 }
848
849 /* No packets in scheduler or nobody wants to give them to us :-(
850 * Sigh... start watchdog timer in the last case.
851 */
852
853 if (sch->q.qlen) {
854 qdisc_qstats_overlimit(sch);
855 if (q->wd_expires)
856 qdisc_watchdog_schedule(&q->watchdog,
857 now + q->wd_expires);
858 }
859 return NULL;
860}
861
862/* CBQ class maintanance routines */
863
864static void cbq_adjust_levels(struct cbq_class *this)
865{
866 if (this == NULL)
867 return;
868
869 do {
870 int level = 0;
871 struct cbq_class *cl;
872
873 cl = this->children;
874 if (cl) {
875 do {
876 if (cl->level > level)
877 level = cl->level;
878 } while ((cl = cl->sibling) != this->children);
879 }
880 this->level = level + 1;
881 } while ((this = this->tparent) != NULL);
882}
883
884static void cbq_normalize_quanta(struct cbq_sched_data *q, int prio)
885{
886 struct cbq_class *cl;
887 unsigned int h;
888
889 if (q->quanta[prio] == 0)
890 return;
891
892 for (h = 0; h < q->clhash.hashsize; h++) {
893 hlist_for_each_entry(cl, &q->clhash.hash[h], common.hnode) {
894 /* BUGGGG... Beware! This expression suffer of
895 * arithmetic overflows!
896 */
897 if (cl->priority == prio) {
898 cl->quantum = (cl->weight*cl->allot*q->nclasses[prio])/
899 q->quanta[prio];
900 }
901 if (cl->quantum <= 0 ||
902 cl->quantum > 32*qdisc_dev(cl->qdisc)->mtu) {
903 pr_warn("CBQ: class %08x has bad quantum==%ld, repaired.\n",
904 cl->common.classid, cl->quantum);
905 cl->quantum = qdisc_dev(cl->qdisc)->mtu/2 + 1;
906 }
907 }
908 }
909}
910
911static void cbq_sync_defmap(struct cbq_class *cl)
912{
913 struct cbq_sched_data *q = qdisc_priv(cl->qdisc);
914 struct cbq_class *split = cl->split;
915 unsigned int h;
916 int i;
917
918 if (split == NULL)
919 return;
920
921 for (i = 0; i <= TC_PRIO_MAX; i++) {
922 if (split->defaults[i] == cl && !(cl->defmap & (1<<i)))
923 split->defaults[i] = NULL;
924 }
925
926 for (i = 0; i <= TC_PRIO_MAX; i++) {
927 int level = split->level;
928
929 if (split->defaults[i])
930 continue;
931
932 for (h = 0; h < q->clhash.hashsize; h++) {
933 struct cbq_class *c;
934
935 hlist_for_each_entry(c, &q->clhash.hash[h],
936 common.hnode) {
937 if (c->split == split && c->level < level &&
938 c->defmap & (1<<i)) {
939 split->defaults[i] = c;
940 level = c->level;
941 }
942 }
943 }
944 }
945}
946
947static void cbq_change_defmap(struct cbq_class *cl, u32 splitid, u32 def, u32 mask)
948{
949 struct cbq_class *split = NULL;
950
951 if (splitid == 0) {
952 split = cl->split;
953 if (!split)
954 return;
955 splitid = split->common.classid;
956 }
957
958 if (split == NULL || split->common.classid != splitid) {
959 for (split = cl->tparent; split; split = split->tparent)
960 if (split->common.classid == splitid)
961 break;
962 }
963
964 if (split == NULL)
965 return;
966
967 if (cl->split != split) {
968 cl->defmap = 0;
969 cbq_sync_defmap(cl);
970 cl->split = split;
971 cl->defmap = def & mask;
972 } else
973 cl->defmap = (cl->defmap & ~mask) | (def & mask);
974
975 cbq_sync_defmap(cl);
976}
977
978static void cbq_unlink_class(struct cbq_class *this)
979{
980 struct cbq_class *cl, **clp;
981 struct cbq_sched_data *q = qdisc_priv(this->qdisc);
982
983 qdisc_class_hash_remove(&q->clhash, &this->common);
984
985 if (this->tparent) {
986 clp = &this->sibling;
987 cl = *clp;
988 do {
989 if (cl == this) {
990 *clp = cl->sibling;
991 break;
992 }
993 clp = &cl->sibling;
994 } while ((cl = *clp) != this->sibling);
995
996 if (this->tparent->children == this) {
997 this->tparent->children = this->sibling;
998 if (this->sibling == this)
999 this->tparent->children = NULL;
1000 }
1001 } else {
1002 WARN_ON(this->sibling != this);
1003 }
1004}
1005
1006static void cbq_link_class(struct cbq_class *this)
1007{
1008 struct cbq_sched_data *q = qdisc_priv(this->qdisc);
1009 struct cbq_class *parent = this->tparent;
1010
1011 this->sibling = this;
1012 qdisc_class_hash_insert(&q->clhash, &this->common);
1013
1014 if (parent == NULL)
1015 return;
1016
1017 if (parent->children == NULL) {
1018 parent->children = this;
1019 } else {
1020 this->sibling = parent->children->sibling;
1021 parent->children->sibling = this;
1022 }
1023}
1024
1025static void
1026cbq_reset(struct Qdisc *sch)
1027{
1028 struct cbq_sched_data *q = qdisc_priv(sch);
1029 struct cbq_class *cl;
1030 int prio;
1031 unsigned int h;
1032
1033 q->activemask = 0;
1034 q->pmask = 0;
1035 q->tx_class = NULL;
1036 q->tx_borrowed = NULL;
1037 qdisc_watchdog_cancel(&q->watchdog);
1038 hrtimer_cancel(&q->delay_timer);
1039 q->toplevel = TC_CBQ_MAXLEVEL;
1040 q->now = psched_get_time();
1041
1042 for (prio = 0; prio <= TC_CBQ_MAXPRIO; prio++)
1043 q->active[prio] = NULL;
1044
1045 for (h = 0; h < q->clhash.hashsize; h++) {
1046 hlist_for_each_entry(cl, &q->clhash.hash[h], common.hnode) {
1047 qdisc_reset(cl->q);
1048
1049 cl->next_alive = NULL;
1050 cl->undertime = PSCHED_PASTPERFECT;
1051 cl->avgidle = cl->maxidle;
1052 cl->deficit = cl->quantum;
1053 cl->cpriority = cl->priority;
1054 }
1055 }
1056 sch->q.qlen = 0;
1057}
1058
1059
1060static int cbq_set_lss(struct cbq_class *cl, struct tc_cbq_lssopt *lss)
1061{
1062 if (lss->change & TCF_CBQ_LSS_FLAGS) {
1063 cl->share = (lss->flags & TCF_CBQ_LSS_ISOLATED) ? NULL : cl->tparent;
1064 cl->borrow = (lss->flags & TCF_CBQ_LSS_BOUNDED) ? NULL : cl->tparent;
1065 }
1066 if (lss->change & TCF_CBQ_LSS_EWMA)
1067 cl->ewma_log = lss->ewma_log;
1068 if (lss->change & TCF_CBQ_LSS_AVPKT)
1069 cl->avpkt = lss->avpkt;
1070 if (lss->change & TCF_CBQ_LSS_MINIDLE)
1071 cl->minidle = -(long)lss->minidle;
1072 if (lss->change & TCF_CBQ_LSS_MAXIDLE) {
1073 cl->maxidle = lss->maxidle;
1074 cl->avgidle = lss->maxidle;
1075 }
1076 if (lss->change & TCF_CBQ_LSS_OFFTIME)
1077 cl->offtime = lss->offtime;
1078 return 0;
1079}
1080
1081static void cbq_rmprio(struct cbq_sched_data *q, struct cbq_class *cl)
1082{
1083 q->nclasses[cl->priority]--;
1084 q->quanta[cl->priority] -= cl->weight;
1085 cbq_normalize_quanta(q, cl->priority);
1086}
1087
1088static void cbq_addprio(struct cbq_sched_data *q, struct cbq_class *cl)
1089{
1090 q->nclasses[cl->priority]++;
1091 q->quanta[cl->priority] += cl->weight;
1092 cbq_normalize_quanta(q, cl->priority);
1093}
1094
1095static int cbq_set_wrr(struct cbq_class *cl, struct tc_cbq_wrropt *wrr)
1096{
1097 struct cbq_sched_data *q = qdisc_priv(cl->qdisc);
1098
1099 if (wrr->allot)
1100 cl->allot = wrr->allot;
1101 if (wrr->weight)
1102 cl->weight = wrr->weight;
1103 if (wrr->priority) {
1104 cl->priority = wrr->priority - 1;
1105 cl->cpriority = cl->priority;
1106 if (cl->priority >= cl->priority2)
1107 cl->priority2 = TC_CBQ_MAXPRIO - 1;
1108 }
1109
1110 cbq_addprio(q, cl);
1111 return 0;
1112}
1113
1114static int cbq_set_fopt(struct cbq_class *cl, struct tc_cbq_fopt *fopt)
1115{
1116 cbq_change_defmap(cl, fopt->split, fopt->defmap, fopt->defchange);
1117 return 0;
1118}
1119
1120static const struct nla_policy cbq_policy[TCA_CBQ_MAX + 1] = {
1121 [TCA_CBQ_LSSOPT] = { .len = sizeof(struct tc_cbq_lssopt) },
1122 [TCA_CBQ_WRROPT] = { .len = sizeof(struct tc_cbq_wrropt) },
1123 [TCA_CBQ_FOPT] = { .len = sizeof(struct tc_cbq_fopt) },
1124 [TCA_CBQ_OVL_STRATEGY] = { .len = sizeof(struct tc_cbq_ovl) },
1125 [TCA_CBQ_RATE] = { .len = sizeof(struct tc_ratespec) },
1126 [TCA_CBQ_RTAB] = { .type = NLA_BINARY, .len = TC_RTAB_SIZE },
1127 [TCA_CBQ_POLICE] = { .len = sizeof(struct tc_cbq_police) },
1128};
1129
1130static int cbq_opt_parse(struct nlattr *tb[TCA_CBQ_MAX + 1],
1131 struct nlattr *opt,
1132 struct netlink_ext_ack *extack)
1133{
1134 int err;
1135
1136 if (!opt) {
1137 NL_SET_ERR_MSG(extack, "CBQ options are required for this operation");
1138 return -EINVAL;
1139 }
1140
1141 err = nla_parse_nested_deprecated(tb, TCA_CBQ_MAX, opt,
1142 cbq_policy, extack);
1143 if (err < 0)
1144 return err;
1145
1146 if (tb[TCA_CBQ_WRROPT]) {
1147 const struct tc_cbq_wrropt *wrr = nla_data(tb[TCA_CBQ_WRROPT]);
1148
1149 if (wrr->priority > TC_CBQ_MAXPRIO) {
1150 NL_SET_ERR_MSG(extack, "priority is bigger than TC_CBQ_MAXPRIO");
1151 err = -EINVAL;
1152 }
1153 }
1154 return err;
1155}
1156
1157static int cbq_init(struct Qdisc *sch, struct nlattr *opt,
1158 struct netlink_ext_ack *extack)
1159{
1160 struct cbq_sched_data *q = qdisc_priv(sch);
1161 struct nlattr *tb[TCA_CBQ_MAX + 1];
1162 struct tc_ratespec *r;
1163 int err;
1164
1165 qdisc_watchdog_init(&q->watchdog, sch);
1166 hrtimer_init(&q->delay_timer, CLOCK_MONOTONIC, HRTIMER_MODE_ABS_PINNED);
1167 q->delay_timer.function = cbq_undelay;
1168
1169 err = cbq_opt_parse(tb, opt, extack);
1170 if (err < 0)
1171 return err;
1172
1173 if (!tb[TCA_CBQ_RTAB] || !tb[TCA_CBQ_RATE]) {
1174 NL_SET_ERR_MSG(extack, "Rate specification missing or incomplete");
1175 return -EINVAL;
1176 }
1177
1178 r = nla_data(tb[TCA_CBQ_RATE]);
1179
1180 q->link.R_tab = qdisc_get_rtab(r, tb[TCA_CBQ_RTAB], extack);
1181 if (!q->link.R_tab)
1182 return -EINVAL;
1183
1184 err = tcf_block_get(&q->link.block, &q->link.filter_list, sch, extack);
1185 if (err)
1186 goto put_rtab;
1187
1188 err = qdisc_class_hash_init(&q->clhash);
1189 if (err < 0)
1190 goto put_block;
1191
1192 q->link.sibling = &q->link;
1193 q->link.common.classid = sch->handle;
1194 q->link.qdisc = sch;
1195 q->link.q = qdisc_create_dflt(sch->dev_queue, &pfifo_qdisc_ops,
1196 sch->handle, NULL);
1197 if (!q->link.q)
1198 q->link.q = &noop_qdisc;
1199 else
1200 qdisc_hash_add(q->link.q, true);
1201
1202 q->link.priority = TC_CBQ_MAXPRIO - 1;
1203 q->link.priority2 = TC_CBQ_MAXPRIO - 1;
1204 q->link.cpriority = TC_CBQ_MAXPRIO - 1;
1205 q->link.allot = psched_mtu(qdisc_dev(sch));
1206 q->link.quantum = q->link.allot;
1207 q->link.weight = q->link.R_tab->rate.rate;
1208
1209 q->link.ewma_log = TC_CBQ_DEF_EWMA;
1210 q->link.avpkt = q->link.allot/2;
1211 q->link.minidle = -0x7FFFFFFF;
1212
1213 q->toplevel = TC_CBQ_MAXLEVEL;
1214 q->now = psched_get_time();
1215
1216 cbq_link_class(&q->link);
1217
1218 if (tb[TCA_CBQ_LSSOPT])
1219 cbq_set_lss(&q->link, nla_data(tb[TCA_CBQ_LSSOPT]));
1220
1221 cbq_addprio(q, &q->link);
1222 return 0;
1223
1224put_block:
1225 tcf_block_put(q->link.block);
1226
1227put_rtab:
1228 qdisc_put_rtab(q->link.R_tab);
1229 return err;
1230}
1231
1232static int cbq_dump_rate(struct sk_buff *skb, struct cbq_class *cl)
1233{
1234 unsigned char *b = skb_tail_pointer(skb);
1235
1236 if (nla_put(skb, TCA_CBQ_RATE, sizeof(cl->R_tab->rate), &cl->R_tab->rate))
1237 goto nla_put_failure;
1238 return skb->len;
1239
1240nla_put_failure:
1241 nlmsg_trim(skb, b);
1242 return -1;
1243}
1244
1245static int cbq_dump_lss(struct sk_buff *skb, struct cbq_class *cl)
1246{
1247 unsigned char *b = skb_tail_pointer(skb);
1248 struct tc_cbq_lssopt opt;
1249
1250 opt.flags = 0;
1251 if (cl->borrow == NULL)
1252 opt.flags |= TCF_CBQ_LSS_BOUNDED;
1253 if (cl->share == NULL)
1254 opt.flags |= TCF_CBQ_LSS_ISOLATED;
1255 opt.ewma_log = cl->ewma_log;
1256 opt.level = cl->level;
1257 opt.avpkt = cl->avpkt;
1258 opt.maxidle = cl->maxidle;
1259 opt.minidle = (u32)(-cl->minidle);
1260 opt.offtime = cl->offtime;
1261 opt.change = ~0;
1262 if (nla_put(skb, TCA_CBQ_LSSOPT, sizeof(opt), &opt))
1263 goto nla_put_failure;
1264 return skb->len;
1265
1266nla_put_failure:
1267 nlmsg_trim(skb, b);
1268 return -1;
1269}
1270
1271static int cbq_dump_wrr(struct sk_buff *skb, struct cbq_class *cl)
1272{
1273 unsigned char *b = skb_tail_pointer(skb);
1274 struct tc_cbq_wrropt opt;
1275
1276 memset(&opt, 0, sizeof(opt));
1277 opt.flags = 0;
1278 opt.allot = cl->allot;
1279 opt.priority = cl->priority + 1;
1280 opt.cpriority = cl->cpriority + 1;
1281 opt.weight = cl->weight;
1282 if (nla_put(skb, TCA_CBQ_WRROPT, sizeof(opt), &opt))
1283 goto nla_put_failure;
1284 return skb->len;
1285
1286nla_put_failure:
1287 nlmsg_trim(skb, b);
1288 return -1;
1289}
1290
1291static int cbq_dump_fopt(struct sk_buff *skb, struct cbq_class *cl)
1292{
1293 unsigned char *b = skb_tail_pointer(skb);
1294 struct tc_cbq_fopt opt;
1295
1296 if (cl->split || cl->defmap) {
1297 opt.split = cl->split ? cl->split->common.classid : 0;
1298 opt.defmap = cl->defmap;
1299 opt.defchange = ~0;
1300 if (nla_put(skb, TCA_CBQ_FOPT, sizeof(opt), &opt))
1301 goto nla_put_failure;
1302 }
1303 return skb->len;
1304
1305nla_put_failure:
1306 nlmsg_trim(skb, b);
1307 return -1;
1308}
1309
1310static int cbq_dump_attr(struct sk_buff *skb, struct cbq_class *cl)
1311{
1312 if (cbq_dump_lss(skb, cl) < 0 ||
1313 cbq_dump_rate(skb, cl) < 0 ||
1314 cbq_dump_wrr(skb, cl) < 0 ||
1315 cbq_dump_fopt(skb, cl) < 0)
1316 return -1;
1317 return 0;
1318}
1319
1320static int cbq_dump(struct Qdisc *sch, struct sk_buff *skb)
1321{
1322 struct cbq_sched_data *q = qdisc_priv(sch);
1323 struct nlattr *nest;
1324
1325 nest = nla_nest_start_noflag(skb, TCA_OPTIONS);
1326 if (nest == NULL)
1327 goto nla_put_failure;
1328 if (cbq_dump_attr(skb, &q->link) < 0)
1329 goto nla_put_failure;
1330 return nla_nest_end(skb, nest);
1331
1332nla_put_failure:
1333 nla_nest_cancel(skb, nest);
1334 return -1;
1335}
1336
1337static int
1338cbq_dump_stats(struct Qdisc *sch, struct gnet_dump *d)
1339{
1340 struct cbq_sched_data *q = qdisc_priv(sch);
1341
1342 q->link.xstats.avgidle = q->link.avgidle;
1343 return gnet_stats_copy_app(d, &q->link.xstats, sizeof(q->link.xstats));
1344}
1345
1346static int
1347cbq_dump_class(struct Qdisc *sch, unsigned long arg,
1348 struct sk_buff *skb, struct tcmsg *tcm)
1349{
1350 struct cbq_class *cl = (struct cbq_class *)arg;
1351 struct nlattr *nest;
1352
1353 if (cl->tparent)
1354 tcm->tcm_parent = cl->tparent->common.classid;
1355 else
1356 tcm->tcm_parent = TC_H_ROOT;
1357 tcm->tcm_handle = cl->common.classid;
1358 tcm->tcm_info = cl->q->handle;
1359
1360 nest = nla_nest_start_noflag(skb, TCA_OPTIONS);
1361 if (nest == NULL)
1362 goto nla_put_failure;
1363 if (cbq_dump_attr(skb, cl) < 0)
1364 goto nla_put_failure;
1365 return nla_nest_end(skb, nest);
1366
1367nla_put_failure:
1368 nla_nest_cancel(skb, nest);
1369 return -1;
1370}
1371
1372static int
1373cbq_dump_class_stats(struct Qdisc *sch, unsigned long arg,
1374 struct gnet_dump *d)
1375{
1376 struct cbq_sched_data *q = qdisc_priv(sch);
1377 struct cbq_class *cl = (struct cbq_class *)arg;
1378 __u32 qlen;
1379
1380 cl->xstats.avgidle = cl->avgidle;
1381 cl->xstats.undertime = 0;
1382 qdisc_qstats_qlen_backlog(cl->q, &qlen, &cl->qstats.backlog);
1383
1384 if (cl->undertime != PSCHED_PASTPERFECT)
1385 cl->xstats.undertime = cl->undertime - q->now;
1386
1387 if (gnet_stats_copy_basic(qdisc_root_sleeping_running(sch),
1388 d, NULL, &cl->bstats) < 0 ||
1389 gnet_stats_copy_rate_est(d, &cl->rate_est) < 0 ||
1390 gnet_stats_copy_queue(d, NULL, &cl->qstats, qlen) < 0)
1391 return -1;
1392
1393 return gnet_stats_copy_app(d, &cl->xstats, sizeof(cl->xstats));
1394}
1395
1396static int cbq_graft(struct Qdisc *sch, unsigned long arg, struct Qdisc *new,
1397 struct Qdisc **old, struct netlink_ext_ack *extack)
1398{
1399 struct cbq_class *cl = (struct cbq_class *)arg;
1400
1401 if (new == NULL) {
1402 new = qdisc_create_dflt(sch->dev_queue, &pfifo_qdisc_ops,
1403 cl->common.classid, extack);
1404 if (new == NULL)
1405 return -ENOBUFS;
1406 }
1407
1408 *old = qdisc_replace(sch, new, &cl->q);
1409 return 0;
1410}
1411
1412static struct Qdisc *cbq_leaf(struct Qdisc *sch, unsigned long arg)
1413{
1414 struct cbq_class *cl = (struct cbq_class *)arg;
1415
1416 return cl->q;
1417}
1418
1419static void cbq_qlen_notify(struct Qdisc *sch, unsigned long arg)
1420{
1421 struct cbq_class *cl = (struct cbq_class *)arg;
1422
1423 cbq_deactivate_class(cl);
1424}
1425
1426static unsigned long cbq_find(struct Qdisc *sch, u32 classid)
1427{
1428 struct cbq_sched_data *q = qdisc_priv(sch);
1429
1430 return (unsigned long)cbq_class_lookup(q, classid);
1431}
1432
1433static void cbq_destroy_class(struct Qdisc *sch, struct cbq_class *cl)
1434{
1435 struct cbq_sched_data *q = qdisc_priv(sch);
1436
1437 WARN_ON(cl->filters);
1438
1439 tcf_block_put(cl->block);
1440 qdisc_put(cl->q);
1441 qdisc_put_rtab(cl->R_tab);
1442 gen_kill_estimator(&cl->rate_est);
1443 if (cl != &q->link)
1444 kfree(cl);
1445}
1446
1447static void cbq_destroy(struct Qdisc *sch)
1448{
1449 struct cbq_sched_data *q = qdisc_priv(sch);
1450 struct hlist_node *next;
1451 struct cbq_class *cl;
1452 unsigned int h;
1453
1454#ifdef CONFIG_NET_CLS_ACT
1455 q->rx_class = NULL;
1456#endif
1457 /*
1458 * Filters must be destroyed first because we don't destroy the
1459 * classes from root to leafs which means that filters can still
1460 * be bound to classes which have been destroyed already. --TGR '04
1461 */
1462 for (h = 0; h < q->clhash.hashsize; h++) {
1463 hlist_for_each_entry(cl, &q->clhash.hash[h], common.hnode) {
1464 tcf_block_put(cl->block);
1465 cl->block = NULL;
1466 }
1467 }
1468 for (h = 0; h < q->clhash.hashsize; h++) {
1469 hlist_for_each_entry_safe(cl, next, &q->clhash.hash[h],
1470 common.hnode)
1471 cbq_destroy_class(sch, cl);
1472 }
1473 qdisc_class_hash_destroy(&q->clhash);
1474}
1475
1476static int
1477cbq_change_class(struct Qdisc *sch, u32 classid, u32 parentid, struct nlattr **tca,
1478 unsigned long *arg, struct netlink_ext_ack *extack)
1479{
1480 int err;
1481 struct cbq_sched_data *q = qdisc_priv(sch);
1482 struct cbq_class *cl = (struct cbq_class *)*arg;
1483 struct nlattr *opt = tca[TCA_OPTIONS];
1484 struct nlattr *tb[TCA_CBQ_MAX + 1];
1485 struct cbq_class *parent;
1486 struct qdisc_rate_table *rtab = NULL;
1487
1488 err = cbq_opt_parse(tb, opt, extack);
1489 if (err < 0)
1490 return err;
1491
1492 if (tb[TCA_CBQ_OVL_STRATEGY] || tb[TCA_CBQ_POLICE]) {
1493 NL_SET_ERR_MSG(extack, "Neither overlimit strategy nor policing attributes can be used for changing class params");
1494 return -EOPNOTSUPP;
1495 }
1496
1497 if (cl) {
1498 /* Check parent */
1499 if (parentid) {
1500 if (cl->tparent &&
1501 cl->tparent->common.classid != parentid) {
1502 NL_SET_ERR_MSG(extack, "Invalid parent id");
1503 return -EINVAL;
1504 }
1505 if (!cl->tparent && parentid != TC_H_ROOT) {
1506 NL_SET_ERR_MSG(extack, "Parent must be root");
1507 return -EINVAL;
1508 }
1509 }
1510
1511 if (tb[TCA_CBQ_RATE]) {
1512 rtab = qdisc_get_rtab(nla_data(tb[TCA_CBQ_RATE]),
1513 tb[TCA_CBQ_RTAB], extack);
1514 if (rtab == NULL)
1515 return -EINVAL;
1516 }
1517
1518 if (tca[TCA_RATE]) {
1519 err = gen_replace_estimator(&cl->bstats, NULL,
1520 &cl->rate_est,
1521 NULL,
1522 qdisc_root_sleeping_running(sch),
1523 tca[TCA_RATE]);
1524 if (err) {
1525 NL_SET_ERR_MSG(extack, "Failed to replace specified rate estimator");
1526 qdisc_put_rtab(rtab);
1527 return err;
1528 }
1529 }
1530
1531 /* Change class parameters */
1532 sch_tree_lock(sch);
1533
1534 if (cl->next_alive != NULL)
1535 cbq_deactivate_class(cl);
1536
1537 if (rtab) {
1538 qdisc_put_rtab(cl->R_tab);
1539 cl->R_tab = rtab;
1540 }
1541
1542 if (tb[TCA_CBQ_LSSOPT])
1543 cbq_set_lss(cl, nla_data(tb[TCA_CBQ_LSSOPT]));
1544
1545 if (tb[TCA_CBQ_WRROPT]) {
1546 cbq_rmprio(q, cl);
1547 cbq_set_wrr(cl, nla_data(tb[TCA_CBQ_WRROPT]));
1548 }
1549
1550 if (tb[TCA_CBQ_FOPT])
1551 cbq_set_fopt(cl, nla_data(tb[TCA_CBQ_FOPT]));
1552
1553 if (cl->q->q.qlen)
1554 cbq_activate_class(cl);
1555
1556 sch_tree_unlock(sch);
1557
1558 return 0;
1559 }
1560
1561 if (parentid == TC_H_ROOT)
1562 return -EINVAL;
1563
1564 if (!tb[TCA_CBQ_WRROPT] || !tb[TCA_CBQ_RATE] || !tb[TCA_CBQ_LSSOPT]) {
1565 NL_SET_ERR_MSG(extack, "One of the following attributes MUST be specified: WRR, rate or link sharing");
1566 return -EINVAL;
1567 }
1568
1569 rtab = qdisc_get_rtab(nla_data(tb[TCA_CBQ_RATE]), tb[TCA_CBQ_RTAB],
1570 extack);
1571 if (rtab == NULL)
1572 return -EINVAL;
1573
1574 if (classid) {
1575 err = -EINVAL;
1576 if (TC_H_MAJ(classid ^ sch->handle) ||
1577 cbq_class_lookup(q, classid)) {
1578 NL_SET_ERR_MSG(extack, "Specified class not found");
1579 goto failure;
1580 }
1581 } else {
1582 int i;
1583 classid = TC_H_MAKE(sch->handle, 0x8000);
1584
1585 for (i = 0; i < 0x8000; i++) {
1586 if (++q->hgenerator >= 0x8000)
1587 q->hgenerator = 1;
1588 if (cbq_class_lookup(q, classid|q->hgenerator) == NULL)
1589 break;
1590 }
1591 err = -ENOSR;
1592 if (i >= 0x8000) {
1593 NL_SET_ERR_MSG(extack, "Unable to generate classid");
1594 goto failure;
1595 }
1596 classid = classid|q->hgenerator;
1597 }
1598
1599 parent = &q->link;
1600 if (parentid) {
1601 parent = cbq_class_lookup(q, parentid);
1602 err = -EINVAL;
1603 if (!parent) {
1604 NL_SET_ERR_MSG(extack, "Failed to find parentid");
1605 goto failure;
1606 }
1607 }
1608
1609 err = -ENOBUFS;
1610 cl = kzalloc(sizeof(*cl), GFP_KERNEL);
1611 if (cl == NULL)
1612 goto failure;
1613
1614 err = tcf_block_get(&cl->block, &cl->filter_list, sch, extack);
1615 if (err) {
1616 kfree(cl);
1617 return err;
1618 }
1619
1620 if (tca[TCA_RATE]) {
1621 err = gen_new_estimator(&cl->bstats, NULL, &cl->rate_est,
1622 NULL,
1623 qdisc_root_sleeping_running(sch),
1624 tca[TCA_RATE]);
1625 if (err) {
1626 NL_SET_ERR_MSG(extack, "Couldn't create new estimator");
1627 tcf_block_put(cl->block);
1628 kfree(cl);
1629 goto failure;
1630 }
1631 }
1632
1633 cl->R_tab = rtab;
1634 rtab = NULL;
1635 cl->q = qdisc_create_dflt(sch->dev_queue, &pfifo_qdisc_ops, classid,
1636 NULL);
1637 if (!cl->q)
1638 cl->q = &noop_qdisc;
1639 else
1640 qdisc_hash_add(cl->q, true);
1641
1642 cl->common.classid = classid;
1643 cl->tparent = parent;
1644 cl->qdisc = sch;
1645 cl->allot = parent->allot;
1646 cl->quantum = cl->allot;
1647 cl->weight = cl->R_tab->rate.rate;
1648
1649 sch_tree_lock(sch);
1650 cbq_link_class(cl);
1651 cl->borrow = cl->tparent;
1652 if (cl->tparent != &q->link)
1653 cl->share = cl->tparent;
1654 cbq_adjust_levels(parent);
1655 cl->minidle = -0x7FFFFFFF;
1656 cbq_set_lss(cl, nla_data(tb[TCA_CBQ_LSSOPT]));
1657 cbq_set_wrr(cl, nla_data(tb[TCA_CBQ_WRROPT]));
1658 if (cl->ewma_log == 0)
1659 cl->ewma_log = q->link.ewma_log;
1660 if (cl->maxidle == 0)
1661 cl->maxidle = q->link.maxidle;
1662 if (cl->avpkt == 0)
1663 cl->avpkt = q->link.avpkt;
1664 if (tb[TCA_CBQ_FOPT])
1665 cbq_set_fopt(cl, nla_data(tb[TCA_CBQ_FOPT]));
1666 sch_tree_unlock(sch);
1667
1668 qdisc_class_hash_grow(sch, &q->clhash);
1669
1670 *arg = (unsigned long)cl;
1671 return 0;
1672
1673failure:
1674 qdisc_put_rtab(rtab);
1675 return err;
1676}
1677
1678static int cbq_delete(struct Qdisc *sch, unsigned long arg)
1679{
1680 struct cbq_sched_data *q = qdisc_priv(sch);
1681 struct cbq_class *cl = (struct cbq_class *)arg;
1682
1683 if (cl->filters || cl->children || cl == &q->link)
1684 return -EBUSY;
1685
1686 sch_tree_lock(sch);
1687
1688 qdisc_purge_queue(cl->q);
1689
1690 if (cl->next_alive)
1691 cbq_deactivate_class(cl);
1692
1693 if (q->tx_borrowed == cl)
1694 q->tx_borrowed = q->tx_class;
1695 if (q->tx_class == cl) {
1696 q->tx_class = NULL;
1697 q->tx_borrowed = NULL;
1698 }
1699#ifdef CONFIG_NET_CLS_ACT
1700 if (q->rx_class == cl)
1701 q->rx_class = NULL;
1702#endif
1703
1704 cbq_unlink_class(cl);
1705 cbq_adjust_levels(cl->tparent);
1706 cl->defmap = 0;
1707 cbq_sync_defmap(cl);
1708
1709 cbq_rmprio(q, cl);
1710 sch_tree_unlock(sch);
1711
1712 cbq_destroy_class(sch, cl);
1713 return 0;
1714}
1715
1716static struct tcf_block *cbq_tcf_block(struct Qdisc *sch, unsigned long arg,
1717 struct netlink_ext_ack *extack)
1718{
1719 struct cbq_sched_data *q = qdisc_priv(sch);
1720 struct cbq_class *cl = (struct cbq_class *)arg;
1721
1722 if (cl == NULL)
1723 cl = &q->link;
1724
1725 return cl->block;
1726}
1727
1728static unsigned long cbq_bind_filter(struct Qdisc *sch, unsigned long parent,
1729 u32 classid)
1730{
1731 struct cbq_sched_data *q = qdisc_priv(sch);
1732 struct cbq_class *p = (struct cbq_class *)parent;
1733 struct cbq_class *cl = cbq_class_lookup(q, classid);
1734
1735 if (cl) {
1736 if (p && p->level <= cl->level)
1737 return 0;
1738 cl->filters++;
1739 return (unsigned long)cl;
1740 }
1741 return 0;
1742}
1743
1744static void cbq_unbind_filter(struct Qdisc *sch, unsigned long arg)
1745{
1746 struct cbq_class *cl = (struct cbq_class *)arg;
1747
1748 cl->filters--;
1749}
1750
1751static void cbq_walk(struct Qdisc *sch, struct qdisc_walker *arg)
1752{
1753 struct cbq_sched_data *q = qdisc_priv(sch);
1754 struct cbq_class *cl;
1755 unsigned int h;
1756
1757 if (arg->stop)
1758 return;
1759
1760 for (h = 0; h < q->clhash.hashsize; h++) {
1761 hlist_for_each_entry(cl, &q->clhash.hash[h], common.hnode) {
1762 if (arg->count < arg->skip) {
1763 arg->count++;
1764 continue;
1765 }
1766 if (arg->fn(sch, (unsigned long)cl, arg) < 0) {
1767 arg->stop = 1;
1768 return;
1769 }
1770 arg->count++;
1771 }
1772 }
1773}
1774
1775static const struct Qdisc_class_ops cbq_class_ops = {
1776 .graft = cbq_graft,
1777 .leaf = cbq_leaf,
1778 .qlen_notify = cbq_qlen_notify,
1779 .find = cbq_find,
1780 .change = cbq_change_class,
1781 .delete = cbq_delete,
1782 .walk = cbq_walk,
1783 .tcf_block = cbq_tcf_block,
1784 .bind_tcf = cbq_bind_filter,
1785 .unbind_tcf = cbq_unbind_filter,
1786 .dump = cbq_dump_class,
1787 .dump_stats = cbq_dump_class_stats,
1788};
1789
1790static struct Qdisc_ops cbq_qdisc_ops __read_mostly = {
1791 .next = NULL,
1792 .cl_ops = &cbq_class_ops,
1793 .id = "cbq",
1794 .priv_size = sizeof(struct cbq_sched_data),
1795 .enqueue = cbq_enqueue,
1796 .dequeue = cbq_dequeue,
1797 .peek = qdisc_peek_dequeued,
1798 .init = cbq_init,
1799 .reset = cbq_reset,
1800 .destroy = cbq_destroy,
1801 .change = NULL,
1802 .dump = cbq_dump,
1803 .dump_stats = cbq_dump_stats,
1804 .owner = THIS_MODULE,
1805};
1806
1807static int __init cbq_module_init(void)
1808{
1809 return register_qdisc(&cbq_qdisc_ops);
1810}
1811static void __exit cbq_module_exit(void)
1812{
1813 unregister_qdisc(&cbq_qdisc_ops);
1814}
1815module_init(cbq_module_init)
1816module_exit(cbq_module_exit)
1817MODULE_LICENSE("GPL");
1/*
2 * net/sched/sch_cbq.c Class-Based Queueing discipline.
3 *
4 * This program is free software; you can redistribute it and/or
5 * modify it under the terms of the GNU General Public License
6 * as published by the Free Software Foundation; either version
7 * 2 of the License, or (at your option) any later version.
8 *
9 * Authors: Alexey Kuznetsov, <kuznet@ms2.inr.ac.ru>
10 *
11 */
12
13#include <linux/module.h>
14#include <linux/slab.h>
15#include <linux/types.h>
16#include <linux/kernel.h>
17#include <linux/string.h>
18#include <linux/errno.h>
19#include <linux/skbuff.h>
20#include <net/netlink.h>
21#include <net/pkt_sched.h>
22
23
24/* Class-Based Queueing (CBQ) algorithm.
25 =======================================
26
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
30
31 [2] Sally Floyd, "Notes on CBQ and Guaranteed Service", 1995
32
33 [3] Sally Floyd, "Notes on Class-Based Queueing: Setting
34 Parameters", 1996
35
36 [4] Sally Floyd and Michael Speer, "Experimental Results
37 for Class-Based Queueing", 1998, not published.
38
39 -----------------------------------------------------------------------
40
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:
45
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
53
54 delay_i <= ([MTU/(W*r_i)]*W*r + W*r + k*MTU)/B
55
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.
58
59
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).
64
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. */
71
72struct cbq_sched_data;
73
74
75struct cbq_class {
76 struct Qdisc_class_common common;
77 struct cbq_class *next_alive; /* next class with backlog in this priority band */
78
79/* Parameters */
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
85 unsigned char police;
86#endif
87
88 u32 defmap;
89
90 /* Link-sharing scheduler parameters */
91 long maxidle; /* Class parameters: see below. */
92 long offtime;
93 long minidle;
94 u32 avpkt;
95 struct qdisc_rate_table *R_tab;
96
97 /* Overlimit strategy parameters */
98 void (*overlimit)(struct cbq_class *cl);
99 psched_tdiff_t penalty;
100
101 /* General scheduler (WRR) parameters */
102 long allot;
103 long quantum; /* Allotment per WRR round */
104 long weight; /* Relative allotment: see below */
105
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;
111 parent otherwise */
112 struct cbq_class *sibling; /* Sibling chain */
113 struct cbq_class *children; /* Pointer to children chain */
114
115 struct Qdisc *q; /* Elementary queueing discipline */
116
117
118/* Variables */
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.
124 */
125
126 psched_time_t last; /* Last end of service */
127 psched_time_t undertime;
128 long avgidle;
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;
135
136 struct tcf_proto *filter_list;
137
138 int refcnt;
139 int filters;
140
141 struct cbq_class *defaults[TC_PRIO_MAX + 1];
142};
143
144struct 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];
148
149 struct cbq_class link;
150
151 unsigned int activemask;
152 struct cbq_class *active[TC_CBQ_MAXPRIO + 1]; /* List of all classes
153 with backlog */
154
155#ifdef CONFIG_NET_CLS_ACT
156 struct cbq_class *rx_class;
157#endif
158 struct cbq_class *tx_class;
159 struct cbq_class *tx_borrowed;
160 int tx_len;
161 psched_time_t now; /* Cached timestamp */
162 psched_time_t now_rt; /* Cached real time */
163 unsigned int pmask;
164
165 struct hrtimer delay_timer;
166 struct qdisc_watchdog watchdog; /* Watchdog timer,
167 started when CBQ has
168 backlog, but cannot
169 transmit just now */
170 psched_tdiff_t wd_expires;
171 int toplevel;
172 u32 hgenerator;
173};
174
175
176#define L2T(cl, len) qdisc_l2t((cl)->R_tab, len)
177
178static inline struct cbq_class *
179cbq_class_lookup(struct cbq_sched_data *q, u32 classid)
180{
181 struct Qdisc_class_common *clc;
182
183 clc = qdisc_class_find(&q->clhash, classid);
184 if (clc == NULL)
185 return NULL;
186 return container_of(clc, struct cbq_class, common);
187}
188
189#ifdef CONFIG_NET_CLS_ACT
190
191static struct cbq_class *
192cbq_reclassify(struct sk_buff *skb, struct cbq_class *this)
193{
194 struct cbq_class *cl;
195
196 for (cl = this->tparent; cl; cl = cl->tparent) {
197 struct cbq_class *new = cl->defaults[TC_PRIO_BESTEFFORT];
198
199 if (new != NULL && new != this)
200 return new;
201 }
202 return NULL;
203}
204
205#endif
206
207/* Classify packet. The procedure is pretty complicated, but
208 * it allows us to combine link sharing and priority scheduling
209 * transparently.
210 *
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
214 * to the split node.
215 */
216
217static struct cbq_class *
218cbq_classify(struct sk_buff *skb, struct Qdisc *sch, int *qerr)
219{
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;
226
227 /*
228 * Step 1. If skb->priority points to one of our classes, use it.
229 */
230 if (TC_H_MAJ(prio ^ sch->handle) == 0 &&
231 (cl = cbq_class_lookup(q, prio)) != NULL)
232 return cl;
233
234 *qerr = NET_XMIT_SUCCESS | __NET_XMIT_BYPASS;
235 for (;;) {
236 int result = 0;
237 defmap = head->defaults;
238
239 /*
240 * Step 2+n. Apply classifier.
241 */
242 if (!head->filter_list ||
243 (result = tc_classify_compat(skb, head->filter_list, &res)) < 0)
244 goto fallback;
245
246 cl = (void *)res.class;
247 if (!cl) {
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];
252
253 if (cl == NULL || cl->level >= head->level)
254 goto fallback;
255 }
256
257#ifdef CONFIG_NET_CLS_ACT
258 switch (result) {
259 case TC_ACT_QUEUED:
260 case TC_ACT_STOLEN:
261 *qerr = NET_XMIT_SUCCESS | __NET_XMIT_STOLEN;
262 case TC_ACT_SHOT:
263 return NULL;
264 case TC_ACT_RECLASSIFY:
265 return cbq_reclassify(skb, cl);
266 }
267#endif
268 if (cl->level == 0)
269 return cl;
270
271 /*
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.
275 */
276 head = cl;
277 }
278
279fallback:
280 cl = head;
281
282 /*
283 * Step 4. No success...
284 */
285 if (TC_H_MAJ(prio) == 0 &&
286 !(cl = head->defaults[prio & TC_PRIO_MAX]) &&
287 !(cl = head->defaults[TC_PRIO_BESTEFFORT]))
288 return head;
289
290 return cl;
291}
292
293/*
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.
297 */
298
299static inline void cbq_activate_class(struct cbq_class *cl)
300{
301 struct cbq_sched_data *q = qdisc_priv(cl->qdisc);
302 int prio = cl->cpriority;
303 struct cbq_class *cl_tail;
304
305 cl_tail = q->active[prio];
306 q->active[prio] = cl;
307
308 if (cl_tail != NULL) {
309 cl->next_alive = cl_tail->next_alive;
310 cl_tail->next_alive = cl;
311 } else {
312 cl->next_alive = cl;
313 q->activemask |= (1<<prio);
314 }
315}
316
317/*
318 * Unlink class from active chain.
319 * Note that this same procedure is done directly in cbq_dequeue*
320 * during round-robin procedure.
321 */
322
323static void cbq_deactivate_class(struct cbq_class *this)
324{
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];
329
330 do {
331 cl = cl_prev->next_alive;
332 if (cl == this) {
333 cl_prev->next_alive = cl->next_alive;
334 cl->next_alive = NULL;
335
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);
341 return;
342 }
343 }
344 return;
345 }
346 } while ((cl_prev = cl) != q->active[prio]);
347}
348
349static void
350cbq_mark_toplevel(struct cbq_sched_data *q, struct cbq_class *cl)
351{
352 int toplevel = q->toplevel;
353
354 if (toplevel > cl->level && !(qdisc_is_throttled(cl->q))) {
355 psched_time_t now;
356 psched_tdiff_t incr;
357
358 now = psched_get_time();
359 incr = now - q->now_rt;
360 now = q->now + incr;
361
362 do {
363 if (cl->undertime < now) {
364 q->toplevel = cl->level;
365 return;
366 }
367 } while ((cl = cl->borrow) != NULL && toplevel > cl->level);
368 }
369}
370
371static int
372cbq_enqueue(struct sk_buff *skb, struct Qdisc *sch)
373{
374 struct cbq_sched_data *q = qdisc_priv(sch);
375 int uninitialized_var(ret);
376 struct cbq_class *cl = cbq_classify(skb, sch, &ret);
377
378#ifdef CONFIG_NET_CLS_ACT
379 q->rx_class = cl;
380#endif
381 if (cl == NULL) {
382 if (ret & __NET_XMIT_BYPASS)
383 sch->qstats.drops++;
384 kfree_skb(skb);
385 return ret;
386 }
387
388#ifdef CONFIG_NET_CLS_ACT
389 cl->q->__parent = sch;
390#endif
391 ret = qdisc_enqueue(skb, cl->q);
392 if (ret == NET_XMIT_SUCCESS) {
393 sch->q.qlen++;
394 cbq_mark_toplevel(q, cl);
395 if (!cl->next_alive)
396 cbq_activate_class(cl);
397 return ret;
398 }
399
400 if (net_xmit_drop_count(ret)) {
401 sch->qstats.drops++;
402 cbq_mark_toplevel(q, cl);
403 cl->qstats.drops++;
404 }
405 return ret;
406}
407
408/* Overlimit actions */
409
410/* TC_CBQ_OVL_CLASSIC: (default) penalize leaf class by adding offtime */
411
412static void cbq_ovl_classic(struct cbq_class *cl)
413{
414 struct cbq_sched_data *q = qdisc_priv(cl->qdisc);
415 psched_tdiff_t delay = cl->undertime - q->now;
416
417 if (!cl->delayed) {
418 delay += cl->offtime;
419
420 /*
421 * Class goes to sleep, so that it will have no
422 * chance to work avgidle. Let's forgive it 8)
423 *
424 * BTW cbq-2.0 has a crap in this
425 * place, apparently they forgot to shift it by cl->ewma_log.
426 */
427 if (cl->avgidle < 0)
428 delay -= (-cl->avgidle) - ((-cl->avgidle) >> cl->ewma_log);
429 if (cl->avgidle < cl->minidle)
430 cl->avgidle = cl->minidle;
431 if (delay <= 0)
432 delay = 1;
433 cl->undertime = q->now + delay;
434
435 cl->xstats.overactions++;
436 cl->delayed = 1;
437 }
438 if (q->wd_expires == 0 || q->wd_expires > delay)
439 q->wd_expires = delay;
440
441 /* Dirty work! We must schedule wakeups based on
442 * real available rate, rather than leaf rate,
443 * which may be tiny (even zero).
444 */
445 if (q->toplevel == TC_CBQ_MAXLEVEL) {
446 struct cbq_class *b;
447 psched_tdiff_t base_delay = q->wd_expires;
448
449 for (b = cl->borrow; b; b = b->borrow) {
450 delay = b->undertime - q->now;
451 if (delay < base_delay) {
452 if (delay <= 0)
453 delay = 1;
454 base_delay = delay;
455 }
456 }
457
458 q->wd_expires = base_delay;
459 }
460}
461
462/* TC_CBQ_OVL_RCLASSIC: penalize by offtime classes in hierarchy, when
463 * they go overlimit
464 */
465
466static void cbq_ovl_rclassic(struct cbq_class *cl)
467{
468 struct cbq_sched_data *q = qdisc_priv(cl->qdisc);
469 struct cbq_class *this = cl;
470
471 do {
472 if (cl->level > q->toplevel) {
473 cl = NULL;
474 break;
475 }
476 } while ((cl = cl->borrow) != NULL);
477
478 if (cl == NULL)
479 cl = this;
480 cbq_ovl_classic(cl);
481}
482
483/* TC_CBQ_OVL_DELAY: delay until it will go to underlimit */
484
485static void cbq_ovl_delay(struct cbq_class *cl)
486{
487 struct cbq_sched_data *q = qdisc_priv(cl->qdisc);
488 psched_tdiff_t delay = cl->undertime - q->now;
489
490 if (test_bit(__QDISC_STATE_DEACTIVATED,
491 &qdisc_root_sleeping(cl->qdisc)->state))
492 return;
493
494 if (!cl->delayed) {
495 psched_time_t sched = q->now;
496 ktime_t expires;
497
498 delay += cl->offtime;
499 if (cl->avgidle < 0)
500 delay -= (-cl->avgidle) - ((-cl->avgidle) >> cl->ewma_log);
501 if (cl->avgidle < cl->minidle)
502 cl->avgidle = cl->minidle;
503 cl->undertime = q->now + delay;
504
505 if (delay > 0) {
506 sched += delay + cl->penalty;
507 cl->penalized = sched;
508 cl->cpriority = TC_CBQ_MAXPRIO;
509 q->pmask |= (1<<TC_CBQ_MAXPRIO);
510
511 expires = ktime_set(0, 0);
512 expires = ktime_add_ns(expires, PSCHED_TICKS2NS(sched));
513 if (hrtimer_try_to_cancel(&q->delay_timer) &&
514 ktime_to_ns(ktime_sub(
515 hrtimer_get_expires(&q->delay_timer),
516 expires)) > 0)
517 hrtimer_set_expires(&q->delay_timer, expires);
518 hrtimer_restart(&q->delay_timer);
519 cl->delayed = 1;
520 cl->xstats.overactions++;
521 return;
522 }
523 delay = 1;
524 }
525 if (q->wd_expires == 0 || q->wd_expires > delay)
526 q->wd_expires = delay;
527}
528
529/* TC_CBQ_OVL_LOWPRIO: penalize class by lowering its priority band */
530
531static void cbq_ovl_lowprio(struct cbq_class *cl)
532{
533 struct cbq_sched_data *q = qdisc_priv(cl->qdisc);
534
535 cl->penalized = q->now + cl->penalty;
536
537 if (cl->cpriority != cl->priority2) {
538 cl->cpriority = cl->priority2;
539 q->pmask |= (1<<cl->cpriority);
540 cl->xstats.overactions++;
541 }
542 cbq_ovl_classic(cl);
543}
544
545/* TC_CBQ_OVL_DROP: penalize class by dropping */
546
547static void cbq_ovl_drop(struct cbq_class *cl)
548{
549 if (cl->q->ops->drop)
550 if (cl->q->ops->drop(cl->q))
551 cl->qdisc->q.qlen--;
552 cl->xstats.overactions++;
553 cbq_ovl_classic(cl);
554}
555
556static psched_tdiff_t cbq_undelay_prio(struct cbq_sched_data *q, int prio,
557 psched_time_t now)
558{
559 struct cbq_class *cl;
560 struct cbq_class *cl_prev = q->active[prio];
561 psched_time_t sched = now;
562
563 if (cl_prev == NULL)
564 return 0;
565
566 do {
567 cl = cl_prev->next_alive;
568 if (now - cl->penalized > 0) {
569 cl_prev->next_alive = cl->next_alive;
570 cl->next_alive = NULL;
571 cl->cpriority = cl->priority;
572 cl->delayed = 0;
573 cbq_activate_class(cl);
574
575 if (cl == q->active[prio]) {
576 q->active[prio] = cl_prev;
577 if (cl == q->active[prio]) {
578 q->active[prio] = NULL;
579 return 0;
580 }
581 }
582
583 cl = cl_prev->next_alive;
584 } else if (sched - cl->penalized > 0)
585 sched = cl->penalized;
586 } while ((cl_prev = cl) != q->active[prio]);
587
588 return sched - now;
589}
590
591static enum hrtimer_restart cbq_undelay(struct hrtimer *timer)
592{
593 struct cbq_sched_data *q = container_of(timer, struct cbq_sched_data,
594 delay_timer);
595 struct Qdisc *sch = q->watchdog.qdisc;
596 psched_time_t now;
597 psched_tdiff_t delay = 0;
598 unsigned int pmask;
599
600 now = psched_get_time();
601
602 pmask = q->pmask;
603 q->pmask = 0;
604
605 while (pmask) {
606 int prio = ffz(~pmask);
607 psched_tdiff_t tmp;
608
609 pmask &= ~(1<<prio);
610
611 tmp = cbq_undelay_prio(q, prio, now);
612 if (tmp > 0) {
613 q->pmask |= 1<<prio;
614 if (tmp < delay || delay == 0)
615 delay = tmp;
616 }
617 }
618
619 if (delay) {
620 ktime_t time;
621
622 time = ktime_set(0, 0);
623 time = ktime_add_ns(time, PSCHED_TICKS2NS(now + delay));
624 hrtimer_start(&q->delay_timer, time, HRTIMER_MODE_ABS);
625 }
626
627 qdisc_unthrottled(sch);
628 __netif_schedule(qdisc_root(sch));
629 return HRTIMER_NORESTART;
630}
631
632#ifdef CONFIG_NET_CLS_ACT
633static int cbq_reshape_fail(struct sk_buff *skb, struct Qdisc *child)
634{
635 struct Qdisc *sch = child->__parent;
636 struct cbq_sched_data *q = qdisc_priv(sch);
637 struct cbq_class *cl = q->rx_class;
638
639 q->rx_class = NULL;
640
641 if (cl && (cl = cbq_reclassify(skb, cl)) != NULL) {
642 int ret;
643
644 cbq_mark_toplevel(q, cl);
645
646 q->rx_class = cl;
647 cl->q->__parent = sch;
648
649 ret = qdisc_enqueue(skb, cl->q);
650 if (ret == NET_XMIT_SUCCESS) {
651 sch->q.qlen++;
652 if (!cl->next_alive)
653 cbq_activate_class(cl);
654 return 0;
655 }
656 if (net_xmit_drop_count(ret))
657 sch->qstats.drops++;
658 return 0;
659 }
660
661 sch->qstats.drops++;
662 return -1;
663}
664#endif
665
666/*
667 * It is mission critical procedure.
668 *
669 * We "regenerate" toplevel cutoff, if transmitting class
670 * has backlog and it is not regulated. It is not part of
671 * original CBQ description, but looks more reasonable.
672 * Probably, it is wrong. This question needs further investigation.
673 */
674
675static inline void
676cbq_update_toplevel(struct cbq_sched_data *q, struct cbq_class *cl,
677 struct cbq_class *borrowed)
678{
679 if (cl && q->toplevel >= borrowed->level) {
680 if (cl->q->q.qlen > 1) {
681 do {
682 if (borrowed->undertime == PSCHED_PASTPERFECT) {
683 q->toplevel = borrowed->level;
684 return;
685 }
686 } while ((borrowed = borrowed->borrow) != NULL);
687 }
688#if 0
689 /* It is not necessary now. Uncommenting it
690 will save CPU cycles, but decrease fairness.
691 */
692 q->toplevel = TC_CBQ_MAXLEVEL;
693#endif
694 }
695}
696
697static void
698cbq_update(struct cbq_sched_data *q)
699{
700 struct cbq_class *this = q->tx_class;
701 struct cbq_class *cl = this;
702 int len = q->tx_len;
703
704 q->tx_class = NULL;
705
706 for ( ; cl; cl = cl->share) {
707 long avgidle = cl->avgidle;
708 long idle;
709
710 cl->bstats.packets++;
711 cl->bstats.bytes += len;
712
713 /*
714 * (now - last) is total time between packet right edges.
715 * (last_pktlen/rate) is "virtual" busy time, so that
716 *
717 * idle = (now - last) - last_pktlen/rate
718 */
719
720 idle = q->now - cl->last;
721 if ((unsigned long)idle > 128*1024*1024) {
722 avgidle = cl->maxidle;
723 } else {
724 idle -= L2T(cl, len);
725
726 /* true_avgidle := (1-W)*true_avgidle + W*idle,
727 * where W=2^{-ewma_log}. But cl->avgidle is scaled:
728 * cl->avgidle == true_avgidle/W,
729 * hence:
730 */
731 avgidle += idle - (avgidle>>cl->ewma_log);
732 }
733
734 if (avgidle <= 0) {
735 /* Overlimit or at-limit */
736
737 if (avgidle < cl->minidle)
738 avgidle = cl->minidle;
739
740 cl->avgidle = avgidle;
741
742 /* Calculate expected time, when this class
743 * will be allowed to send.
744 * It will occur, when:
745 * (1-W)*true_avgidle + W*delay = 0, i.e.
746 * idle = (1/W - 1)*(-true_avgidle)
747 * or
748 * idle = (1 - W)*(-cl->avgidle);
749 */
750 idle = (-avgidle) - ((-avgidle) >> cl->ewma_log);
751
752 /*
753 * That is not all.
754 * To maintain the rate allocated to the class,
755 * we add to undertime virtual clock,
756 * necessary to complete transmitted packet.
757 * (len/phys_bandwidth has been already passed
758 * to the moment of cbq_update)
759 */
760
761 idle -= L2T(&q->link, len);
762 idle += L2T(cl, len);
763
764 cl->undertime = q->now + idle;
765 } else {
766 /* Underlimit */
767
768 cl->undertime = PSCHED_PASTPERFECT;
769 if (avgidle > cl->maxidle)
770 cl->avgidle = cl->maxidle;
771 else
772 cl->avgidle = avgidle;
773 }
774 cl->last = q->now;
775 }
776
777 cbq_update_toplevel(q, this, q->tx_borrowed);
778}
779
780static inline struct cbq_class *
781cbq_under_limit(struct cbq_class *cl)
782{
783 struct cbq_sched_data *q = qdisc_priv(cl->qdisc);
784 struct cbq_class *this_cl = cl;
785
786 if (cl->tparent == NULL)
787 return cl;
788
789 if (cl->undertime == PSCHED_PASTPERFECT || q->now >= cl->undertime) {
790 cl->delayed = 0;
791 return cl;
792 }
793
794 do {
795 /* It is very suspicious place. Now overlimit
796 * action is generated for not bounded classes
797 * only if link is completely congested.
798 * Though it is in agree with ancestor-only paradigm,
799 * it looks very stupid. Particularly,
800 * it means that this chunk of code will either
801 * never be called or result in strong amplification
802 * of burstiness. Dangerous, silly, and, however,
803 * no another solution exists.
804 */
805 cl = cl->borrow;
806 if (!cl) {
807 this_cl->qstats.overlimits++;
808 this_cl->overlimit(this_cl);
809 return NULL;
810 }
811 if (cl->level > q->toplevel)
812 return NULL;
813 } while (cl->undertime != PSCHED_PASTPERFECT && q->now < cl->undertime);
814
815 cl->delayed = 0;
816 return cl;
817}
818
819static inline struct sk_buff *
820cbq_dequeue_prio(struct Qdisc *sch, int prio)
821{
822 struct cbq_sched_data *q = qdisc_priv(sch);
823 struct cbq_class *cl_tail, *cl_prev, *cl;
824 struct sk_buff *skb;
825 int deficit;
826
827 cl_tail = cl_prev = q->active[prio];
828 cl = cl_prev->next_alive;
829
830 do {
831 deficit = 0;
832
833 /* Start round */
834 do {
835 struct cbq_class *borrow = cl;
836
837 if (cl->q->q.qlen &&
838 (borrow = cbq_under_limit(cl)) == NULL)
839 goto skip_class;
840
841 if (cl->deficit <= 0) {
842 /* Class exhausted its allotment per
843 * this round. Switch to the next one.
844 */
845 deficit = 1;
846 cl->deficit += cl->quantum;
847 goto next_class;
848 }
849
850 skb = cl->q->dequeue(cl->q);
851
852 /* Class did not give us any skb :-(
853 * It could occur even if cl->q->q.qlen != 0
854 * f.e. if cl->q == "tbf"
855 */
856 if (skb == NULL)
857 goto skip_class;
858
859 cl->deficit -= qdisc_pkt_len(skb);
860 q->tx_class = cl;
861 q->tx_borrowed = borrow;
862 if (borrow != cl) {
863#ifndef CBQ_XSTATS_BORROWS_BYTES
864 borrow->xstats.borrows++;
865 cl->xstats.borrows++;
866#else
867 borrow->xstats.borrows += qdisc_pkt_len(skb);
868 cl->xstats.borrows += qdisc_pkt_len(skb);
869#endif
870 }
871 q->tx_len = qdisc_pkt_len(skb);
872
873 if (cl->deficit <= 0) {
874 q->active[prio] = cl;
875 cl = cl->next_alive;
876 cl->deficit += cl->quantum;
877 }
878 return skb;
879
880skip_class:
881 if (cl->q->q.qlen == 0 || prio != cl->cpriority) {
882 /* Class is empty or penalized.
883 * Unlink it from active chain.
884 */
885 cl_prev->next_alive = cl->next_alive;
886 cl->next_alive = NULL;
887
888 /* Did cl_tail point to it? */
889 if (cl == cl_tail) {
890 /* Repair it! */
891 cl_tail = cl_prev;
892
893 /* Was it the last class in this band? */
894 if (cl == cl_tail) {
895 /* Kill the band! */
896 q->active[prio] = NULL;
897 q->activemask &= ~(1<<prio);
898 if (cl->q->q.qlen)
899 cbq_activate_class(cl);
900 return NULL;
901 }
902
903 q->active[prio] = cl_tail;
904 }
905 if (cl->q->q.qlen)
906 cbq_activate_class(cl);
907
908 cl = cl_prev;
909 }
910
911next_class:
912 cl_prev = cl;
913 cl = cl->next_alive;
914 } while (cl_prev != cl_tail);
915 } while (deficit);
916
917 q->active[prio] = cl_prev;
918
919 return NULL;
920}
921
922static inline struct sk_buff *
923cbq_dequeue_1(struct Qdisc *sch)
924{
925 struct cbq_sched_data *q = qdisc_priv(sch);
926 struct sk_buff *skb;
927 unsigned int activemask;
928
929 activemask = q->activemask & 0xFF;
930 while (activemask) {
931 int prio = ffz(~activemask);
932 activemask &= ~(1<<prio);
933 skb = cbq_dequeue_prio(sch, prio);
934 if (skb)
935 return skb;
936 }
937 return NULL;
938}
939
940static struct sk_buff *
941cbq_dequeue(struct Qdisc *sch)
942{
943 struct sk_buff *skb;
944 struct cbq_sched_data *q = qdisc_priv(sch);
945 psched_time_t now;
946 psched_tdiff_t incr;
947
948 now = psched_get_time();
949 incr = now - q->now_rt;
950
951 if (q->tx_class) {
952 psched_tdiff_t incr2;
953 /* Time integrator. We calculate EOS time
954 * by adding expected packet transmission time.
955 * If real time is greater, we warp artificial clock,
956 * so that:
957 *
958 * cbq_time = max(real_time, work);
959 */
960 incr2 = L2T(&q->link, q->tx_len);
961 q->now += incr2;
962 cbq_update(q);
963 if ((incr -= incr2) < 0)
964 incr = 0;
965 }
966 q->now += incr;
967 q->now_rt = now;
968
969 for (;;) {
970 q->wd_expires = 0;
971
972 skb = cbq_dequeue_1(sch);
973 if (skb) {
974 qdisc_bstats_update(sch, skb);
975 sch->q.qlen--;
976 qdisc_unthrottled(sch);
977 return skb;
978 }
979
980 /* All the classes are overlimit.
981 *
982 * It is possible, if:
983 *
984 * 1. Scheduler is empty.
985 * 2. Toplevel cutoff inhibited borrowing.
986 * 3. Root class is overlimit.
987 *
988 * Reset 2d and 3d conditions and retry.
989 *
990 * Note, that NS and cbq-2.0 are buggy, peeking
991 * an arbitrary class is appropriate for ancestor-only
992 * sharing, but not for toplevel algorithm.
993 *
994 * Our version is better, but slower, because it requires
995 * two passes, but it is unavoidable with top-level sharing.
996 */
997
998 if (q->toplevel == TC_CBQ_MAXLEVEL &&
999 q->link.undertime == PSCHED_PASTPERFECT)
1000 break;
1001
1002 q->toplevel = TC_CBQ_MAXLEVEL;
1003 q->link.undertime = PSCHED_PASTPERFECT;
1004 }
1005
1006 /* No packets in scheduler or nobody wants to give them to us :-(
1007 * Sigh... start watchdog timer in the last case.
1008 */
1009
1010 if (sch->q.qlen) {
1011 sch->qstats.overlimits++;
1012 if (q->wd_expires)
1013 qdisc_watchdog_schedule(&q->watchdog,
1014 now + q->wd_expires);
1015 }
1016 return NULL;
1017}
1018
1019/* CBQ class maintanance routines */
1020
1021static void cbq_adjust_levels(struct cbq_class *this)
1022{
1023 if (this == NULL)
1024 return;
1025
1026 do {
1027 int level = 0;
1028 struct cbq_class *cl;
1029
1030 cl = this->children;
1031 if (cl) {
1032 do {
1033 if (cl->level > level)
1034 level = cl->level;
1035 } while ((cl = cl->sibling) != this->children);
1036 }
1037 this->level = level + 1;
1038 } while ((this = this->tparent) != NULL);
1039}
1040
1041static void cbq_normalize_quanta(struct cbq_sched_data *q, int prio)
1042{
1043 struct cbq_class *cl;
1044 struct hlist_node *n;
1045 unsigned int h;
1046
1047 if (q->quanta[prio] == 0)
1048 return;
1049
1050 for (h = 0; h < q->clhash.hashsize; h++) {
1051 hlist_for_each_entry(cl, n, &q->clhash.hash[h], common.hnode) {
1052 /* BUGGGG... Beware! This expression suffer of
1053 * arithmetic overflows!
1054 */
1055 if (cl->priority == prio) {
1056 cl->quantum = (cl->weight*cl->allot*q->nclasses[prio])/
1057 q->quanta[prio];
1058 }
1059 if (cl->quantum <= 0 || cl->quantum>32*qdisc_dev(cl->qdisc)->mtu) {
1060 pr_warning("CBQ: class %08x has bad quantum==%ld, repaired.\n",
1061 cl->common.classid, cl->quantum);
1062 cl->quantum = qdisc_dev(cl->qdisc)->mtu/2 + 1;
1063 }
1064 }
1065 }
1066}
1067
1068static void cbq_sync_defmap(struct cbq_class *cl)
1069{
1070 struct cbq_sched_data *q = qdisc_priv(cl->qdisc);
1071 struct cbq_class *split = cl->split;
1072 unsigned int h;
1073 int i;
1074
1075 if (split == NULL)
1076 return;
1077
1078 for (i = 0; i <= TC_PRIO_MAX; i++) {
1079 if (split->defaults[i] == cl && !(cl->defmap & (1<<i)))
1080 split->defaults[i] = NULL;
1081 }
1082
1083 for (i = 0; i <= TC_PRIO_MAX; i++) {
1084 int level = split->level;
1085
1086 if (split->defaults[i])
1087 continue;
1088
1089 for (h = 0; h < q->clhash.hashsize; h++) {
1090 struct hlist_node *n;
1091 struct cbq_class *c;
1092
1093 hlist_for_each_entry(c, n, &q->clhash.hash[h],
1094 common.hnode) {
1095 if (c->split == split && c->level < level &&
1096 c->defmap & (1<<i)) {
1097 split->defaults[i] = c;
1098 level = c->level;
1099 }
1100 }
1101 }
1102 }
1103}
1104
1105static void cbq_change_defmap(struct cbq_class *cl, u32 splitid, u32 def, u32 mask)
1106{
1107 struct cbq_class *split = NULL;
1108
1109 if (splitid == 0) {
1110 split = cl->split;
1111 if (!split)
1112 return;
1113 splitid = split->common.classid;
1114 }
1115
1116 if (split == NULL || split->common.classid != splitid) {
1117 for (split = cl->tparent; split; split = split->tparent)
1118 if (split->common.classid == splitid)
1119 break;
1120 }
1121
1122 if (split == NULL)
1123 return;
1124
1125 if (cl->split != split) {
1126 cl->defmap = 0;
1127 cbq_sync_defmap(cl);
1128 cl->split = split;
1129 cl->defmap = def & mask;
1130 } else
1131 cl->defmap = (cl->defmap & ~mask) | (def & mask);
1132
1133 cbq_sync_defmap(cl);
1134}
1135
1136static void cbq_unlink_class(struct cbq_class *this)
1137{
1138 struct cbq_class *cl, **clp;
1139 struct cbq_sched_data *q = qdisc_priv(this->qdisc);
1140
1141 qdisc_class_hash_remove(&q->clhash, &this->common);
1142
1143 if (this->tparent) {
1144 clp = &this->sibling;
1145 cl = *clp;
1146 do {
1147 if (cl == this) {
1148 *clp = cl->sibling;
1149 break;
1150 }
1151 clp = &cl->sibling;
1152 } while ((cl = *clp) != this->sibling);
1153
1154 if (this->tparent->children == this) {
1155 this->tparent->children = this->sibling;
1156 if (this->sibling == this)
1157 this->tparent->children = NULL;
1158 }
1159 } else {
1160 WARN_ON(this->sibling != this);
1161 }
1162}
1163
1164static void cbq_link_class(struct cbq_class *this)
1165{
1166 struct cbq_sched_data *q = qdisc_priv(this->qdisc);
1167 struct cbq_class *parent = this->tparent;
1168
1169 this->sibling = this;
1170 qdisc_class_hash_insert(&q->clhash, &this->common);
1171
1172 if (parent == NULL)
1173 return;
1174
1175 if (parent->children == NULL) {
1176 parent->children = this;
1177 } else {
1178 this->sibling = parent->children->sibling;
1179 parent->children->sibling = this;
1180 }
1181}
1182
1183static unsigned int cbq_drop(struct Qdisc *sch)
1184{
1185 struct cbq_sched_data *q = qdisc_priv(sch);
1186 struct cbq_class *cl, *cl_head;
1187 int prio;
1188 unsigned int len;
1189
1190 for (prio = TC_CBQ_MAXPRIO; prio >= 0; prio--) {
1191 cl_head = q->active[prio];
1192 if (!cl_head)
1193 continue;
1194
1195 cl = cl_head;
1196 do {
1197 if (cl->q->ops->drop && (len = cl->q->ops->drop(cl->q))) {
1198 sch->q.qlen--;
1199 if (!cl->q->q.qlen)
1200 cbq_deactivate_class(cl);
1201 return len;
1202 }
1203 } while ((cl = cl->next_alive) != cl_head);
1204 }
1205 return 0;
1206}
1207
1208static void
1209cbq_reset(struct Qdisc *sch)
1210{
1211 struct cbq_sched_data *q = qdisc_priv(sch);
1212 struct cbq_class *cl;
1213 struct hlist_node *n;
1214 int prio;
1215 unsigned int h;
1216
1217 q->activemask = 0;
1218 q->pmask = 0;
1219 q->tx_class = NULL;
1220 q->tx_borrowed = NULL;
1221 qdisc_watchdog_cancel(&q->watchdog);
1222 hrtimer_cancel(&q->delay_timer);
1223 q->toplevel = TC_CBQ_MAXLEVEL;
1224 q->now = psched_get_time();
1225 q->now_rt = q->now;
1226
1227 for (prio = 0; prio <= TC_CBQ_MAXPRIO; prio++)
1228 q->active[prio] = NULL;
1229
1230 for (h = 0; h < q->clhash.hashsize; h++) {
1231 hlist_for_each_entry(cl, n, &q->clhash.hash[h], common.hnode) {
1232 qdisc_reset(cl->q);
1233
1234 cl->next_alive = NULL;
1235 cl->undertime = PSCHED_PASTPERFECT;
1236 cl->avgidle = cl->maxidle;
1237 cl->deficit = cl->quantum;
1238 cl->cpriority = cl->priority;
1239 }
1240 }
1241 sch->q.qlen = 0;
1242}
1243
1244
1245static int cbq_set_lss(struct cbq_class *cl, struct tc_cbq_lssopt *lss)
1246{
1247 if (lss->change & TCF_CBQ_LSS_FLAGS) {
1248 cl->share = (lss->flags & TCF_CBQ_LSS_ISOLATED) ? NULL : cl->tparent;
1249 cl->borrow = (lss->flags & TCF_CBQ_LSS_BOUNDED) ? NULL : cl->tparent;
1250 }
1251 if (lss->change & TCF_CBQ_LSS_EWMA)
1252 cl->ewma_log = lss->ewma_log;
1253 if (lss->change & TCF_CBQ_LSS_AVPKT)
1254 cl->avpkt = lss->avpkt;
1255 if (lss->change & TCF_CBQ_LSS_MINIDLE)
1256 cl->minidle = -(long)lss->minidle;
1257 if (lss->change & TCF_CBQ_LSS_MAXIDLE) {
1258 cl->maxidle = lss->maxidle;
1259 cl->avgidle = lss->maxidle;
1260 }
1261 if (lss->change & TCF_CBQ_LSS_OFFTIME)
1262 cl->offtime = lss->offtime;
1263 return 0;
1264}
1265
1266static void cbq_rmprio(struct cbq_sched_data *q, struct cbq_class *cl)
1267{
1268 q->nclasses[cl->priority]--;
1269 q->quanta[cl->priority] -= cl->weight;
1270 cbq_normalize_quanta(q, cl->priority);
1271}
1272
1273static void cbq_addprio(struct cbq_sched_data *q, struct cbq_class *cl)
1274{
1275 q->nclasses[cl->priority]++;
1276 q->quanta[cl->priority] += cl->weight;
1277 cbq_normalize_quanta(q, cl->priority);
1278}
1279
1280static int cbq_set_wrr(struct cbq_class *cl, struct tc_cbq_wrropt *wrr)
1281{
1282 struct cbq_sched_data *q = qdisc_priv(cl->qdisc);
1283
1284 if (wrr->allot)
1285 cl->allot = wrr->allot;
1286 if (wrr->weight)
1287 cl->weight = wrr->weight;
1288 if (wrr->priority) {
1289 cl->priority = wrr->priority - 1;
1290 cl->cpriority = cl->priority;
1291 if (cl->priority >= cl->priority2)
1292 cl->priority2 = TC_CBQ_MAXPRIO - 1;
1293 }
1294
1295 cbq_addprio(q, cl);
1296 return 0;
1297}
1298
1299static int cbq_set_overlimit(struct cbq_class *cl, struct tc_cbq_ovl *ovl)
1300{
1301 switch (ovl->strategy) {
1302 case TC_CBQ_OVL_CLASSIC:
1303 cl->overlimit = cbq_ovl_classic;
1304 break;
1305 case TC_CBQ_OVL_DELAY:
1306 cl->overlimit = cbq_ovl_delay;
1307 break;
1308 case TC_CBQ_OVL_LOWPRIO:
1309 if (ovl->priority2 - 1 >= TC_CBQ_MAXPRIO ||
1310 ovl->priority2 - 1 <= cl->priority)
1311 return -EINVAL;
1312 cl->priority2 = ovl->priority2 - 1;
1313 cl->overlimit = cbq_ovl_lowprio;
1314 break;
1315 case TC_CBQ_OVL_DROP:
1316 cl->overlimit = cbq_ovl_drop;
1317 break;
1318 case TC_CBQ_OVL_RCLASSIC:
1319 cl->overlimit = cbq_ovl_rclassic;
1320 break;
1321 default:
1322 return -EINVAL;
1323 }
1324 cl->penalty = ovl->penalty;
1325 return 0;
1326}
1327
1328#ifdef CONFIG_NET_CLS_ACT
1329static int cbq_set_police(struct cbq_class *cl, struct tc_cbq_police *p)
1330{
1331 cl->police = p->police;
1332
1333 if (cl->q->handle) {
1334 if (p->police == TC_POLICE_RECLASSIFY)
1335 cl->q->reshape_fail = cbq_reshape_fail;
1336 else
1337 cl->q->reshape_fail = NULL;
1338 }
1339 return 0;
1340}
1341#endif
1342
1343static int cbq_set_fopt(struct cbq_class *cl, struct tc_cbq_fopt *fopt)
1344{
1345 cbq_change_defmap(cl, fopt->split, fopt->defmap, fopt->defchange);
1346 return 0;
1347}
1348
1349static const struct nla_policy cbq_policy[TCA_CBQ_MAX + 1] = {
1350 [TCA_CBQ_LSSOPT] = { .len = sizeof(struct tc_cbq_lssopt) },
1351 [TCA_CBQ_WRROPT] = { .len = sizeof(struct tc_cbq_wrropt) },
1352 [TCA_CBQ_FOPT] = { .len = sizeof(struct tc_cbq_fopt) },
1353 [TCA_CBQ_OVL_STRATEGY] = { .len = sizeof(struct tc_cbq_ovl) },
1354 [TCA_CBQ_RATE] = { .len = sizeof(struct tc_ratespec) },
1355 [TCA_CBQ_RTAB] = { .type = NLA_BINARY, .len = TC_RTAB_SIZE },
1356 [TCA_CBQ_POLICE] = { .len = sizeof(struct tc_cbq_police) },
1357};
1358
1359static int cbq_init(struct Qdisc *sch, struct nlattr *opt)
1360{
1361 struct cbq_sched_data *q = qdisc_priv(sch);
1362 struct nlattr *tb[TCA_CBQ_MAX + 1];
1363 struct tc_ratespec *r;
1364 int err;
1365
1366 err = nla_parse_nested(tb, TCA_CBQ_MAX, opt, cbq_policy);
1367 if (err < 0)
1368 return err;
1369
1370 if (tb[TCA_CBQ_RTAB] == NULL || tb[TCA_CBQ_RATE] == NULL)
1371 return -EINVAL;
1372
1373 r = nla_data(tb[TCA_CBQ_RATE]);
1374
1375 if ((q->link.R_tab = qdisc_get_rtab(r, tb[TCA_CBQ_RTAB])) == NULL)
1376 return -EINVAL;
1377
1378 err = qdisc_class_hash_init(&q->clhash);
1379 if (err < 0)
1380 goto put_rtab;
1381
1382 q->link.refcnt = 1;
1383 q->link.sibling = &q->link;
1384 q->link.common.classid = sch->handle;
1385 q->link.qdisc = sch;
1386 q->link.q = qdisc_create_dflt(sch->dev_queue, &pfifo_qdisc_ops,
1387 sch->handle);
1388 if (!q->link.q)
1389 q->link.q = &noop_qdisc;
1390
1391 q->link.priority = TC_CBQ_MAXPRIO - 1;
1392 q->link.priority2 = TC_CBQ_MAXPRIO - 1;
1393 q->link.cpriority = TC_CBQ_MAXPRIO - 1;
1394 q->link.ovl_strategy = TC_CBQ_OVL_CLASSIC;
1395 q->link.overlimit = cbq_ovl_classic;
1396 q->link.allot = psched_mtu(qdisc_dev(sch));
1397 q->link.quantum = q->link.allot;
1398 q->link.weight = q->link.R_tab->rate.rate;
1399
1400 q->link.ewma_log = TC_CBQ_DEF_EWMA;
1401 q->link.avpkt = q->link.allot/2;
1402 q->link.minidle = -0x7FFFFFFF;
1403
1404 qdisc_watchdog_init(&q->watchdog, sch);
1405 hrtimer_init(&q->delay_timer, CLOCK_MONOTONIC, HRTIMER_MODE_ABS);
1406 q->delay_timer.function = cbq_undelay;
1407 q->toplevel = TC_CBQ_MAXLEVEL;
1408 q->now = psched_get_time();
1409 q->now_rt = q->now;
1410
1411 cbq_link_class(&q->link);
1412
1413 if (tb[TCA_CBQ_LSSOPT])
1414 cbq_set_lss(&q->link, nla_data(tb[TCA_CBQ_LSSOPT]));
1415
1416 cbq_addprio(q, &q->link);
1417 return 0;
1418
1419put_rtab:
1420 qdisc_put_rtab(q->link.R_tab);
1421 return err;
1422}
1423
1424static int cbq_dump_rate(struct sk_buff *skb, struct cbq_class *cl)
1425{
1426 unsigned char *b = skb_tail_pointer(skb);
1427
1428 NLA_PUT(skb, TCA_CBQ_RATE, sizeof(cl->R_tab->rate), &cl->R_tab->rate);
1429 return skb->len;
1430
1431nla_put_failure:
1432 nlmsg_trim(skb, b);
1433 return -1;
1434}
1435
1436static int cbq_dump_lss(struct sk_buff *skb, struct cbq_class *cl)
1437{
1438 unsigned char *b = skb_tail_pointer(skb);
1439 struct tc_cbq_lssopt opt;
1440
1441 opt.flags = 0;
1442 if (cl->borrow == NULL)
1443 opt.flags |= TCF_CBQ_LSS_BOUNDED;
1444 if (cl->share == NULL)
1445 opt.flags |= TCF_CBQ_LSS_ISOLATED;
1446 opt.ewma_log = cl->ewma_log;
1447 opt.level = cl->level;
1448 opt.avpkt = cl->avpkt;
1449 opt.maxidle = cl->maxidle;
1450 opt.minidle = (u32)(-cl->minidle);
1451 opt.offtime = cl->offtime;
1452 opt.change = ~0;
1453 NLA_PUT(skb, TCA_CBQ_LSSOPT, sizeof(opt), &opt);
1454 return skb->len;
1455
1456nla_put_failure:
1457 nlmsg_trim(skb, b);
1458 return -1;
1459}
1460
1461static int cbq_dump_wrr(struct sk_buff *skb, struct cbq_class *cl)
1462{
1463 unsigned char *b = skb_tail_pointer(skb);
1464 struct tc_cbq_wrropt opt;
1465
1466 opt.flags = 0;
1467 opt.allot = cl->allot;
1468 opt.priority = cl->priority + 1;
1469 opt.cpriority = cl->cpriority + 1;
1470 opt.weight = cl->weight;
1471 NLA_PUT(skb, TCA_CBQ_WRROPT, sizeof(opt), &opt);
1472 return skb->len;
1473
1474nla_put_failure:
1475 nlmsg_trim(skb, b);
1476 return -1;
1477}
1478
1479static int cbq_dump_ovl(struct sk_buff *skb, struct cbq_class *cl)
1480{
1481 unsigned char *b = skb_tail_pointer(skb);
1482 struct tc_cbq_ovl opt;
1483
1484 opt.strategy = cl->ovl_strategy;
1485 opt.priority2 = cl->priority2 + 1;
1486 opt.pad = 0;
1487 opt.penalty = cl->penalty;
1488 NLA_PUT(skb, TCA_CBQ_OVL_STRATEGY, sizeof(opt), &opt);
1489 return skb->len;
1490
1491nla_put_failure:
1492 nlmsg_trim(skb, b);
1493 return -1;
1494}
1495
1496static int cbq_dump_fopt(struct sk_buff *skb, struct cbq_class *cl)
1497{
1498 unsigned char *b = skb_tail_pointer(skb);
1499 struct tc_cbq_fopt opt;
1500
1501 if (cl->split || cl->defmap) {
1502 opt.split = cl->split ? cl->split->common.classid : 0;
1503 opt.defmap = cl->defmap;
1504 opt.defchange = ~0;
1505 NLA_PUT(skb, TCA_CBQ_FOPT, sizeof(opt), &opt);
1506 }
1507 return skb->len;
1508
1509nla_put_failure:
1510 nlmsg_trim(skb, b);
1511 return -1;
1512}
1513
1514#ifdef CONFIG_NET_CLS_ACT
1515static int cbq_dump_police(struct sk_buff *skb, struct cbq_class *cl)
1516{
1517 unsigned char *b = skb_tail_pointer(skb);
1518 struct tc_cbq_police opt;
1519
1520 if (cl->police) {
1521 opt.police = cl->police;
1522 opt.__res1 = 0;
1523 opt.__res2 = 0;
1524 NLA_PUT(skb, TCA_CBQ_POLICE, sizeof(opt), &opt);
1525 }
1526 return skb->len;
1527
1528nla_put_failure:
1529 nlmsg_trim(skb, b);
1530 return -1;
1531}
1532#endif
1533
1534static int cbq_dump_attr(struct sk_buff *skb, struct cbq_class *cl)
1535{
1536 if (cbq_dump_lss(skb, cl) < 0 ||
1537 cbq_dump_rate(skb, cl) < 0 ||
1538 cbq_dump_wrr(skb, cl) < 0 ||
1539 cbq_dump_ovl(skb, cl) < 0 ||
1540#ifdef CONFIG_NET_CLS_ACT
1541 cbq_dump_police(skb, cl) < 0 ||
1542#endif
1543 cbq_dump_fopt(skb, cl) < 0)
1544 return -1;
1545 return 0;
1546}
1547
1548static int cbq_dump(struct Qdisc *sch, struct sk_buff *skb)
1549{
1550 struct cbq_sched_data *q = qdisc_priv(sch);
1551 struct nlattr *nest;
1552
1553 nest = nla_nest_start(skb, TCA_OPTIONS);
1554 if (nest == NULL)
1555 goto nla_put_failure;
1556 if (cbq_dump_attr(skb, &q->link) < 0)
1557 goto nla_put_failure;
1558 nla_nest_end(skb, nest);
1559 return skb->len;
1560
1561nla_put_failure:
1562 nla_nest_cancel(skb, nest);
1563 return -1;
1564}
1565
1566static int
1567cbq_dump_stats(struct Qdisc *sch, struct gnet_dump *d)
1568{
1569 struct cbq_sched_data *q = qdisc_priv(sch);
1570
1571 q->link.xstats.avgidle = q->link.avgidle;
1572 return gnet_stats_copy_app(d, &q->link.xstats, sizeof(q->link.xstats));
1573}
1574
1575static int
1576cbq_dump_class(struct Qdisc *sch, unsigned long arg,
1577 struct sk_buff *skb, struct tcmsg *tcm)
1578{
1579 struct cbq_class *cl = (struct cbq_class *)arg;
1580 struct nlattr *nest;
1581
1582 if (cl->tparent)
1583 tcm->tcm_parent = cl->tparent->common.classid;
1584 else
1585 tcm->tcm_parent = TC_H_ROOT;
1586 tcm->tcm_handle = cl->common.classid;
1587 tcm->tcm_info = cl->q->handle;
1588
1589 nest = nla_nest_start(skb, TCA_OPTIONS);
1590 if (nest == NULL)
1591 goto nla_put_failure;
1592 if (cbq_dump_attr(skb, cl) < 0)
1593 goto nla_put_failure;
1594 nla_nest_end(skb, nest);
1595 return skb->len;
1596
1597nla_put_failure:
1598 nla_nest_cancel(skb, nest);
1599 return -1;
1600}
1601
1602static int
1603cbq_dump_class_stats(struct Qdisc *sch, unsigned long arg,
1604 struct gnet_dump *d)
1605{
1606 struct cbq_sched_data *q = qdisc_priv(sch);
1607 struct cbq_class *cl = (struct cbq_class *)arg;
1608
1609 cl->qstats.qlen = cl->q->q.qlen;
1610 cl->xstats.avgidle = cl->avgidle;
1611 cl->xstats.undertime = 0;
1612
1613 if (cl->undertime != PSCHED_PASTPERFECT)
1614 cl->xstats.undertime = cl->undertime - q->now;
1615
1616 if (gnet_stats_copy_basic(d, &cl->bstats) < 0 ||
1617 gnet_stats_copy_rate_est(d, &cl->bstats, &cl->rate_est) < 0 ||
1618 gnet_stats_copy_queue(d, &cl->qstats) < 0)
1619 return -1;
1620
1621 return gnet_stats_copy_app(d, &cl->xstats, sizeof(cl->xstats));
1622}
1623
1624static int cbq_graft(struct Qdisc *sch, unsigned long arg, struct Qdisc *new,
1625 struct Qdisc **old)
1626{
1627 struct cbq_class *cl = (struct cbq_class *)arg;
1628
1629 if (new == NULL) {
1630 new = qdisc_create_dflt(sch->dev_queue,
1631 &pfifo_qdisc_ops, cl->common.classid);
1632 if (new == NULL)
1633 return -ENOBUFS;
1634 } else {
1635#ifdef CONFIG_NET_CLS_ACT
1636 if (cl->police == TC_POLICE_RECLASSIFY)
1637 new->reshape_fail = cbq_reshape_fail;
1638#endif
1639 }
1640 sch_tree_lock(sch);
1641 *old = cl->q;
1642 cl->q = new;
1643 qdisc_tree_decrease_qlen(*old, (*old)->q.qlen);
1644 qdisc_reset(*old);
1645 sch_tree_unlock(sch);
1646
1647 return 0;
1648}
1649
1650static struct Qdisc *cbq_leaf(struct Qdisc *sch, unsigned long arg)
1651{
1652 struct cbq_class *cl = (struct cbq_class *)arg;
1653
1654 return cl->q;
1655}
1656
1657static void cbq_qlen_notify(struct Qdisc *sch, unsigned long arg)
1658{
1659 struct cbq_class *cl = (struct cbq_class *)arg;
1660
1661 if (cl->q->q.qlen == 0)
1662 cbq_deactivate_class(cl);
1663}
1664
1665static unsigned long cbq_get(struct Qdisc *sch, u32 classid)
1666{
1667 struct cbq_sched_data *q = qdisc_priv(sch);
1668 struct cbq_class *cl = cbq_class_lookup(q, classid);
1669
1670 if (cl) {
1671 cl->refcnt++;
1672 return (unsigned long)cl;
1673 }
1674 return 0;
1675}
1676
1677static void cbq_destroy_class(struct Qdisc *sch, struct cbq_class *cl)
1678{
1679 struct cbq_sched_data *q = qdisc_priv(sch);
1680
1681 WARN_ON(cl->filters);
1682
1683 tcf_destroy_chain(&cl->filter_list);
1684 qdisc_destroy(cl->q);
1685 qdisc_put_rtab(cl->R_tab);
1686 gen_kill_estimator(&cl->bstats, &cl->rate_est);
1687 if (cl != &q->link)
1688 kfree(cl);
1689}
1690
1691static void cbq_destroy(struct Qdisc *sch)
1692{
1693 struct cbq_sched_data *q = qdisc_priv(sch);
1694 struct hlist_node *n, *next;
1695 struct cbq_class *cl;
1696 unsigned int h;
1697
1698#ifdef CONFIG_NET_CLS_ACT
1699 q->rx_class = NULL;
1700#endif
1701 /*
1702 * Filters must be destroyed first because we don't destroy the
1703 * classes from root to leafs which means that filters can still
1704 * be bound to classes which have been destroyed already. --TGR '04
1705 */
1706 for (h = 0; h < q->clhash.hashsize; h++) {
1707 hlist_for_each_entry(cl, n, &q->clhash.hash[h], common.hnode)
1708 tcf_destroy_chain(&cl->filter_list);
1709 }
1710 for (h = 0; h < q->clhash.hashsize; h++) {
1711 hlist_for_each_entry_safe(cl, n, next, &q->clhash.hash[h],
1712 common.hnode)
1713 cbq_destroy_class(sch, cl);
1714 }
1715 qdisc_class_hash_destroy(&q->clhash);
1716}
1717
1718static void cbq_put(struct Qdisc *sch, unsigned long arg)
1719{
1720 struct cbq_class *cl = (struct cbq_class *)arg;
1721
1722 if (--cl->refcnt == 0) {
1723#ifdef CONFIG_NET_CLS_ACT
1724 spinlock_t *root_lock = qdisc_root_sleeping_lock(sch);
1725 struct cbq_sched_data *q = qdisc_priv(sch);
1726
1727 spin_lock_bh(root_lock);
1728 if (q->rx_class == cl)
1729 q->rx_class = NULL;
1730 spin_unlock_bh(root_lock);
1731#endif
1732
1733 cbq_destroy_class(sch, cl);
1734 }
1735}
1736
1737static int
1738cbq_change_class(struct Qdisc *sch, u32 classid, u32 parentid, struct nlattr **tca,
1739 unsigned long *arg)
1740{
1741 int err;
1742 struct cbq_sched_data *q = qdisc_priv(sch);
1743 struct cbq_class *cl = (struct cbq_class *)*arg;
1744 struct nlattr *opt = tca[TCA_OPTIONS];
1745 struct nlattr *tb[TCA_CBQ_MAX + 1];
1746 struct cbq_class *parent;
1747 struct qdisc_rate_table *rtab = NULL;
1748
1749 if (opt == NULL)
1750 return -EINVAL;
1751
1752 err = nla_parse_nested(tb, TCA_CBQ_MAX, opt, cbq_policy);
1753 if (err < 0)
1754 return err;
1755
1756 if (cl) {
1757 /* Check parent */
1758 if (parentid) {
1759 if (cl->tparent &&
1760 cl->tparent->common.classid != parentid)
1761 return -EINVAL;
1762 if (!cl->tparent && parentid != TC_H_ROOT)
1763 return -EINVAL;
1764 }
1765
1766 if (tb[TCA_CBQ_RATE]) {
1767 rtab = qdisc_get_rtab(nla_data(tb[TCA_CBQ_RATE]),
1768 tb[TCA_CBQ_RTAB]);
1769 if (rtab == NULL)
1770 return -EINVAL;
1771 }
1772
1773 if (tca[TCA_RATE]) {
1774 err = gen_replace_estimator(&cl->bstats, &cl->rate_est,
1775 qdisc_root_sleeping_lock(sch),
1776 tca[TCA_RATE]);
1777 if (err) {
1778 if (rtab)
1779 qdisc_put_rtab(rtab);
1780 return err;
1781 }
1782 }
1783
1784 /* Change class parameters */
1785 sch_tree_lock(sch);
1786
1787 if (cl->next_alive != NULL)
1788 cbq_deactivate_class(cl);
1789
1790 if (rtab) {
1791 qdisc_put_rtab(cl->R_tab);
1792 cl->R_tab = rtab;
1793 }
1794
1795 if (tb[TCA_CBQ_LSSOPT])
1796 cbq_set_lss(cl, nla_data(tb[TCA_CBQ_LSSOPT]));
1797
1798 if (tb[TCA_CBQ_WRROPT]) {
1799 cbq_rmprio(q, cl);
1800 cbq_set_wrr(cl, nla_data(tb[TCA_CBQ_WRROPT]));
1801 }
1802
1803 if (tb[TCA_CBQ_OVL_STRATEGY])
1804 cbq_set_overlimit(cl, nla_data(tb[TCA_CBQ_OVL_STRATEGY]));
1805
1806#ifdef CONFIG_NET_CLS_ACT
1807 if (tb[TCA_CBQ_POLICE])
1808 cbq_set_police(cl, nla_data(tb[TCA_CBQ_POLICE]));
1809#endif
1810
1811 if (tb[TCA_CBQ_FOPT])
1812 cbq_set_fopt(cl, nla_data(tb[TCA_CBQ_FOPT]));
1813
1814 if (cl->q->q.qlen)
1815 cbq_activate_class(cl);
1816
1817 sch_tree_unlock(sch);
1818
1819 return 0;
1820 }
1821
1822 if (parentid == TC_H_ROOT)
1823 return -EINVAL;
1824
1825 if (tb[TCA_CBQ_WRROPT] == NULL || tb[TCA_CBQ_RATE] == NULL ||
1826 tb[TCA_CBQ_LSSOPT] == NULL)
1827 return -EINVAL;
1828
1829 rtab = qdisc_get_rtab(nla_data(tb[TCA_CBQ_RATE]), tb[TCA_CBQ_RTAB]);
1830 if (rtab == NULL)
1831 return -EINVAL;
1832
1833 if (classid) {
1834 err = -EINVAL;
1835 if (TC_H_MAJ(classid ^ sch->handle) ||
1836 cbq_class_lookup(q, classid))
1837 goto failure;
1838 } else {
1839 int i;
1840 classid = TC_H_MAKE(sch->handle, 0x8000);
1841
1842 for (i = 0; i < 0x8000; i++) {
1843 if (++q->hgenerator >= 0x8000)
1844 q->hgenerator = 1;
1845 if (cbq_class_lookup(q, classid|q->hgenerator) == NULL)
1846 break;
1847 }
1848 err = -ENOSR;
1849 if (i >= 0x8000)
1850 goto failure;
1851 classid = classid|q->hgenerator;
1852 }
1853
1854 parent = &q->link;
1855 if (parentid) {
1856 parent = cbq_class_lookup(q, parentid);
1857 err = -EINVAL;
1858 if (parent == NULL)
1859 goto failure;
1860 }
1861
1862 err = -ENOBUFS;
1863 cl = kzalloc(sizeof(*cl), GFP_KERNEL);
1864 if (cl == NULL)
1865 goto failure;
1866
1867 if (tca[TCA_RATE]) {
1868 err = gen_new_estimator(&cl->bstats, &cl->rate_est,
1869 qdisc_root_sleeping_lock(sch),
1870 tca[TCA_RATE]);
1871 if (err) {
1872 kfree(cl);
1873 goto failure;
1874 }
1875 }
1876
1877 cl->R_tab = rtab;
1878 rtab = NULL;
1879 cl->refcnt = 1;
1880 cl->q = qdisc_create_dflt(sch->dev_queue, &pfifo_qdisc_ops, classid);
1881 if (!cl->q)
1882 cl->q = &noop_qdisc;
1883 cl->common.classid = classid;
1884 cl->tparent = parent;
1885 cl->qdisc = sch;
1886 cl->allot = parent->allot;
1887 cl->quantum = cl->allot;
1888 cl->weight = cl->R_tab->rate.rate;
1889
1890 sch_tree_lock(sch);
1891 cbq_link_class(cl);
1892 cl->borrow = cl->tparent;
1893 if (cl->tparent != &q->link)
1894 cl->share = cl->tparent;
1895 cbq_adjust_levels(parent);
1896 cl->minidle = -0x7FFFFFFF;
1897 cbq_set_lss(cl, nla_data(tb[TCA_CBQ_LSSOPT]));
1898 cbq_set_wrr(cl, nla_data(tb[TCA_CBQ_WRROPT]));
1899 if (cl->ewma_log == 0)
1900 cl->ewma_log = q->link.ewma_log;
1901 if (cl->maxidle == 0)
1902 cl->maxidle = q->link.maxidle;
1903 if (cl->avpkt == 0)
1904 cl->avpkt = q->link.avpkt;
1905 cl->overlimit = cbq_ovl_classic;
1906 if (tb[TCA_CBQ_OVL_STRATEGY])
1907 cbq_set_overlimit(cl, nla_data(tb[TCA_CBQ_OVL_STRATEGY]));
1908#ifdef CONFIG_NET_CLS_ACT
1909 if (tb[TCA_CBQ_POLICE])
1910 cbq_set_police(cl, nla_data(tb[TCA_CBQ_POLICE]));
1911#endif
1912 if (tb[TCA_CBQ_FOPT])
1913 cbq_set_fopt(cl, nla_data(tb[TCA_CBQ_FOPT]));
1914 sch_tree_unlock(sch);
1915
1916 qdisc_class_hash_grow(sch, &q->clhash);
1917
1918 *arg = (unsigned long)cl;
1919 return 0;
1920
1921failure:
1922 qdisc_put_rtab(rtab);
1923 return err;
1924}
1925
1926static int cbq_delete(struct Qdisc *sch, unsigned long arg)
1927{
1928 struct cbq_sched_data *q = qdisc_priv(sch);
1929 struct cbq_class *cl = (struct cbq_class *)arg;
1930 unsigned int qlen;
1931
1932 if (cl->filters || cl->children || cl == &q->link)
1933 return -EBUSY;
1934
1935 sch_tree_lock(sch);
1936
1937 qlen = cl->q->q.qlen;
1938 qdisc_reset(cl->q);
1939 qdisc_tree_decrease_qlen(cl->q, qlen);
1940
1941 if (cl->next_alive)
1942 cbq_deactivate_class(cl);
1943
1944 if (q->tx_borrowed == cl)
1945 q->tx_borrowed = q->tx_class;
1946 if (q->tx_class == cl) {
1947 q->tx_class = NULL;
1948 q->tx_borrowed = NULL;
1949 }
1950#ifdef CONFIG_NET_CLS_ACT
1951 if (q->rx_class == cl)
1952 q->rx_class = NULL;
1953#endif
1954
1955 cbq_unlink_class(cl);
1956 cbq_adjust_levels(cl->tparent);
1957 cl->defmap = 0;
1958 cbq_sync_defmap(cl);
1959
1960 cbq_rmprio(q, cl);
1961 sch_tree_unlock(sch);
1962
1963 BUG_ON(--cl->refcnt == 0);
1964 /*
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().
1967 */
1968
1969 return 0;
1970}
1971
1972static struct tcf_proto **cbq_find_tcf(struct Qdisc *sch, unsigned long arg)
1973{
1974 struct cbq_sched_data *q = qdisc_priv(sch);
1975 struct cbq_class *cl = (struct cbq_class *)arg;
1976
1977 if (cl == NULL)
1978 cl = &q->link;
1979
1980 return &cl->filter_list;
1981}
1982
1983static unsigned long cbq_bind_filter(struct Qdisc *sch, unsigned long parent,
1984 u32 classid)
1985{
1986 struct cbq_sched_data *q = qdisc_priv(sch);
1987 struct cbq_class *p = (struct cbq_class *)parent;
1988 struct cbq_class *cl = cbq_class_lookup(q, classid);
1989
1990 if (cl) {
1991 if (p && p->level <= cl->level)
1992 return 0;
1993 cl->filters++;
1994 return (unsigned long)cl;
1995 }
1996 return 0;
1997}
1998
1999static void cbq_unbind_filter(struct Qdisc *sch, unsigned long arg)
2000{
2001 struct cbq_class *cl = (struct cbq_class *)arg;
2002
2003 cl->filters--;
2004}
2005
2006static void cbq_walk(struct Qdisc *sch, struct qdisc_walker *arg)
2007{
2008 struct cbq_sched_data *q = qdisc_priv(sch);
2009 struct cbq_class *cl;
2010 struct hlist_node *n;
2011 unsigned int h;
2012
2013 if (arg->stop)
2014 return;
2015
2016 for (h = 0; h < q->clhash.hashsize; h++) {
2017 hlist_for_each_entry(cl, n, &q->clhash.hash[h], common.hnode) {
2018 if (arg->count < arg->skip) {
2019 arg->count++;
2020 continue;
2021 }
2022 if (arg->fn(sch, (unsigned long)cl, arg) < 0) {
2023 arg->stop = 1;
2024 return;
2025 }
2026 arg->count++;
2027 }
2028 }
2029}
2030
2031static const struct Qdisc_class_ops cbq_class_ops = {
2032 .graft = cbq_graft,
2033 .leaf = cbq_leaf,
2034 .qlen_notify = cbq_qlen_notify,
2035 .get = cbq_get,
2036 .put = cbq_put,
2037 .change = cbq_change_class,
2038 .delete = cbq_delete,
2039 .walk = cbq_walk,
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,
2045};
2046
2047static struct Qdisc_ops cbq_qdisc_ops __read_mostly = {
2048 .next = NULL,
2049 .cl_ops = &cbq_class_ops,
2050 .id = "cbq",
2051 .priv_size = sizeof(struct cbq_sched_data),
2052 .enqueue = cbq_enqueue,
2053 .dequeue = cbq_dequeue,
2054 .peek = qdisc_peek_dequeued,
2055 .drop = cbq_drop,
2056 .init = cbq_init,
2057 .reset = cbq_reset,
2058 .destroy = cbq_destroy,
2059 .change = NULL,
2060 .dump = cbq_dump,
2061 .dump_stats = cbq_dump_stats,
2062 .owner = THIS_MODULE,
2063};
2064
2065static int __init cbq_module_init(void)
2066{
2067 return register_qdisc(&cbq_qdisc_ops);
2068}
2069static void __exit cbq_module_exit(void)
2070{
2071 unregister_qdisc(&cbq_qdisc_ops);
2072}
2073module_init(cbq_module_init)
2074module_exit(cbq_module_exit)
2075MODULE_LICENSE("GPL");