1
2
3
4
5
6
7
8
9
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
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72struct cbq_sched_data;
73
74
75struct cbq_class {
76 struct Qdisc_class_common common;
77 struct cbq_class *next_alive;
78
79
80 unsigned char priority;
81 unsigned char priority2;
82 unsigned char ewma_log;
83 unsigned char ovl_strategy;
84#ifdef CONFIG_NET_CLS_ACT
85 unsigned char police;
86#endif
87
88 u32 defmap;
89
90
91 long maxidle;
92 long offtime;
93 long minidle;
94 u32 avpkt;
95 struct qdisc_rate_table *R_tab;
96
97
98 void (*overlimit)(struct cbq_class *cl);
99 psched_tdiff_t penalty;
100
101
102 long allot;
103 long quantum;
104 long weight;
105
106 struct Qdisc *qdisc;
107 struct cbq_class *split;
108 struct cbq_class *share;
109 struct cbq_class *tparent;
110 struct cbq_class *borrow;
111
112 struct cbq_class *sibling;
113 struct cbq_class *children;
114
115 struct Qdisc *q;
116
117
118
119 unsigned char cpriority;
120 unsigned char delayed;
121 unsigned char level;
122
123
124
125
126 psched_time_t last;
127 psched_time_t undertime;
128 long avgidle;
129 long deficit;
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;
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];
153
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;
162 psched_time_t now_rt;
163 unsigned int pmask;
164
165 struct hrtimer delay_timer;
166 struct qdisc_watchdog watchdog;
167
168
169
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
208
209
210
211
212
213
214
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
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
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)
254 goto fallback;
255 }
256 if (cl->level >= head->level)
257 goto fallback;
258#ifdef CONFIG_NET_CLS_ACT
259 switch (result) {
260 case TC_ACT_QUEUED:
261 case TC_ACT_STOLEN:
262 *qerr = NET_XMIT_SUCCESS | __NET_XMIT_STOLEN;
263 case TC_ACT_SHOT:
264 return NULL;
265 case TC_ACT_RECLASSIFY:
266 return cbq_reclassify(skb, cl);
267 }
268#endif
269 if (cl->level == 0)
270 return cl;
271
272
273
274
275
276
277 head = cl;
278 }
279
280fallback:
281 cl = head;
282
283
284
285
286 if (TC_H_MAJ(prio) == 0 &&
287 !(cl = head->defaults[prio & TC_PRIO_MAX]) &&
288 !(cl = head->defaults[TC_PRIO_BESTEFFORT]))
289 return head;
290
291 return cl;
292}
293
294
295
296
297
298
299
300static inline void cbq_activate_class(struct cbq_class *cl)
301{
302 struct cbq_sched_data *q = qdisc_priv(cl->qdisc);
303 int prio = cl->cpriority;
304 struct cbq_class *cl_tail;
305
306 cl_tail = q->active[prio];
307 q->active[prio] = cl;
308
309 if (cl_tail != NULL) {
310 cl->next_alive = cl_tail->next_alive;
311 cl_tail->next_alive = cl;
312 } else {
313 cl->next_alive = cl;
314 q->activemask |= (1<<prio);
315 }
316}
317
318
319
320
321
322
323
324static void cbq_deactivate_class(struct cbq_class *this)
325{
326 struct cbq_sched_data *q = qdisc_priv(this->qdisc);
327 int prio = this->cpriority;
328 struct cbq_class *cl;
329 struct cbq_class *cl_prev = q->active[prio];
330
331 do {
332 cl = cl_prev->next_alive;
333 if (cl == this) {
334 cl_prev->next_alive = cl->next_alive;
335 cl->next_alive = NULL;
336
337 if (cl == q->active[prio]) {
338 q->active[prio] = cl_prev;
339 if (cl == q->active[prio]) {
340 q->active[prio] = NULL;
341 q->activemask &= ~(1<<prio);
342 return;
343 }
344 }
345 return;
346 }
347 } while ((cl_prev = cl) != q->active[prio]);
348}
349
350static void
351cbq_mark_toplevel(struct cbq_sched_data *q, struct cbq_class *cl)
352{
353 int toplevel = q->toplevel;
354
355 if (toplevel > cl->level && !(qdisc_is_throttled(cl->q))) {
356 psched_time_t now;
357 psched_tdiff_t incr;
358
359 now = psched_get_time();
360 incr = now - q->now_rt;
361 now = q->now + incr;
362
363 do {
364 if (cl->undertime < now) {
365 q->toplevel = cl->level;
366 return;
367 }
368 } while ((cl = cl->borrow) != NULL && toplevel > cl->level);
369 }
370}
371
372static int
373cbq_enqueue(struct sk_buff *skb, struct Qdisc *sch)
374{
375 struct cbq_sched_data *q = qdisc_priv(sch);
376 int uninitialized_var(ret);
377 struct cbq_class *cl = cbq_classify(skb, sch, &ret);
378
379#ifdef CONFIG_NET_CLS_ACT
380 q->rx_class = cl;
381#endif
382 if (cl == NULL) {
383 if (ret & __NET_XMIT_BYPASS)
384 sch->qstats.drops++;
385 kfree_skb(skb);
386 return ret;
387 }
388
389#ifdef CONFIG_NET_CLS_ACT
390 cl->q->__parent = sch;
391#endif
392 ret = qdisc_enqueue(skb, cl->q);
393 if (ret == NET_XMIT_SUCCESS) {
394 sch->q.qlen++;
395 cbq_mark_toplevel(q, cl);
396 if (!cl->next_alive)
397 cbq_activate_class(cl);
398 return ret;
399 }
400
401 if (net_xmit_drop_count(ret)) {
402 sch->qstats.drops++;
403 cbq_mark_toplevel(q, cl);
404 cl->qstats.drops++;
405 }
406 return ret;
407}
408
409
410
411
412
413static void cbq_ovl_classic(struct cbq_class *cl)
414{
415 struct cbq_sched_data *q = qdisc_priv(cl->qdisc);
416 psched_tdiff_t delay = cl->undertime - q->now;
417
418 if (!cl->delayed) {
419 delay += cl->offtime;
420
421
422
423
424
425
426
427
428 if (cl->avgidle < 0)
429 delay -= (-cl->avgidle) - ((-cl->avgidle) >> cl->ewma_log);
430 if (cl->avgidle < cl->minidle)
431 cl->avgidle = cl->minidle;
432 if (delay <= 0)
433 delay = 1;
434 cl->undertime = q->now + delay;
435
436 cl->xstats.overactions++;
437 cl->delayed = 1;
438 }
439 if (q->wd_expires == 0 || q->wd_expires > delay)
440 q->wd_expires = delay;
441
442
443
444
445
446 if (q->toplevel == TC_CBQ_MAXLEVEL) {
447 struct cbq_class *b;
448 psched_tdiff_t base_delay = q->wd_expires;
449
450 for (b = cl->borrow; b; b = b->borrow) {
451 delay = b->undertime - q->now;
452 if (delay < base_delay) {
453 if (delay <= 0)
454 delay = 1;
455 base_delay = delay;
456 }
457 }
458
459 q->wd_expires = base_delay;
460 }
461}
462
463
464
465
466
467static void cbq_ovl_rclassic(struct cbq_class *cl)
468{
469 struct cbq_sched_data *q = qdisc_priv(cl->qdisc);
470 struct cbq_class *this = cl;
471
472 do {
473 if (cl->level > q->toplevel) {
474 cl = NULL;
475 break;
476 }
477 } while ((cl = cl->borrow) != NULL);
478
479 if (cl == NULL)
480 cl = this;
481 cbq_ovl_classic(cl);
482}
483
484
485
486static void cbq_ovl_delay(struct cbq_class *cl)
487{
488 struct cbq_sched_data *q = qdisc_priv(cl->qdisc);
489 psched_tdiff_t delay = cl->undertime - q->now;
490
491 if (test_bit(__QDISC_STATE_DEACTIVATED,
492 &qdisc_root_sleeping(cl->qdisc)->state))
493 return;
494
495 if (!cl->delayed) {
496 psched_time_t sched = q->now;
497 ktime_t expires;
498
499 delay += cl->offtime;
500 if (cl->avgidle < 0)
501 delay -= (-cl->avgidle) - ((-cl->avgidle) >> cl->ewma_log);
502 if (cl->avgidle < cl->minidle)
503 cl->avgidle = cl->minidle;
504 cl->undertime = q->now + delay;
505
506 if (delay > 0) {
507 sched += delay + cl->penalty;
508 cl->penalized = sched;
509 cl->cpriority = TC_CBQ_MAXPRIO;
510 q->pmask |= (1<<TC_CBQ_MAXPRIO);
511
512 expires = ns_to_ktime(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
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
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
668
669
670
671
672
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
690
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
715
716
717
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
727
728
729
730
731 avgidle += idle - (avgidle>>cl->ewma_log);
732 }
733
734 if (avgidle <= 0) {
735
736
737 if (avgidle < cl->minidle)
738 avgidle = cl->minidle;
739
740 cl->avgidle = avgidle;
741
742
743
744
745
746
747
748
749
750 idle = (-avgidle) - ((-avgidle) >> cl->ewma_log);
751
752
753
754
755
756
757
758
759
760
761 idle -= L2T(&q->link, len);
762 idle += L2T(cl, len);
763
764 cl->undertime = q->now + idle;
765 } else {
766
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
796
797
798
799
800
801
802
803
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
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
843
844
845 deficit = 1;
846 cl->deficit += cl->quantum;
847 goto next_class;
848 }
849
850 skb = cl->q->dequeue(cl->q);
851
852
853
854
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
883
884
885 cl_prev->next_alive = cl->next_alive;
886 cl->next_alive = NULL;
887
888
889 if (cl == cl_tail) {
890
891 cl_tail = cl_prev;
892
893
894 if (cl == cl_tail) {
895
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
954
955
956
957
958
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 q->now += incr;
966 } else {
967 if (now > q->now)
968 q->now = now;
969 }
970 q->now_rt = now;
971
972 for (;;) {
973 q->wd_expires = 0;
974
975 skb = cbq_dequeue_1(sch);
976 if (skb) {
977 qdisc_bstats_update(sch, skb);
978 sch->q.qlen--;
979 qdisc_unthrottled(sch);
980 return skb;
981 }
982
983
984
985
986
987
988
989
990
991
992
993
994
995
996
997
998
999
1000
1001 if (q->toplevel == TC_CBQ_MAXLEVEL &&
1002 q->link.undertime == PSCHED_PASTPERFECT)
1003 break;
1004
1005 q->toplevel = TC_CBQ_MAXLEVEL;
1006 q->link.undertime = PSCHED_PASTPERFECT;
1007 }
1008
1009
1010
1011
1012
1013 if (sch->q.qlen) {
1014 sch->qstats.overlimits++;
1015 if (q->wd_expires)
1016 qdisc_watchdog_schedule(&q->watchdog,
1017 now + q->wd_expires);
1018 }
1019 return NULL;
1020}
1021
1022
1023
1024static void cbq_adjust_levels(struct cbq_class *this)
1025{
1026 if (this == NULL)
1027 return;
1028
1029 do {
1030 int level = 0;
1031 struct cbq_class *cl;
1032
1033 cl = this->children;
1034 if (cl) {
1035 do {
1036 if (cl->level > level)
1037 level = cl->level;
1038 } while ((cl = cl->sibling) != this->children);
1039 }
1040 this->level = level + 1;
1041 } while ((this = this->tparent) != NULL);
1042}
1043
1044static void cbq_normalize_quanta(struct cbq_sched_data *q, int prio)
1045{
1046 struct cbq_class *cl;
1047 unsigned int h;
1048
1049 if (q->quanta[prio] == 0)
1050 return;
1051
1052 for (h = 0; h < q->clhash.hashsize; h++) {
1053 hlist_for_each_entry(cl, &q->clhash.hash[h], common.hnode) {
1054
1055
1056
1057 if (cl->priority == prio) {
1058 cl->quantum = (cl->weight*cl->allot*q->nclasses[prio])/
1059 q->quanta[prio];
1060 }
1061 if (cl->quantum <= 0 || cl->quantum>32*qdisc_dev(cl->qdisc)->mtu) {
1062 pr_warning("CBQ: class %08x has bad quantum==%ld, repaired.\n",
1063 cl->common.classid, cl->quantum);
1064 cl->quantum = qdisc_dev(cl->qdisc)->mtu/2 + 1;
1065 }
1066 }
1067 }
1068}
1069
1070static void cbq_sync_defmap(struct cbq_class *cl)
1071{
1072 struct cbq_sched_data *q = qdisc_priv(cl->qdisc);
1073 struct cbq_class *split = cl->split;
1074 unsigned int h;
1075 int i;
1076
1077 if (split == NULL)
1078 return;
1079
1080 for (i = 0; i <= TC_PRIO_MAX; i++) {
1081 if (split->defaults[i] == cl && !(cl->defmap & (1<<i)))
1082 split->defaults[i] = NULL;
1083 }
1084
1085 for (i = 0; i <= TC_PRIO_MAX; i++) {
1086 int level = split->level;
1087
1088 if (split->defaults[i])
1089 continue;
1090
1091 for (h = 0; h < q->clhash.hashsize; h++) {
1092 struct cbq_class *c;
1093
1094 hlist_for_each_entry(c, &q->clhash.hash[h],
1095 common.hnode) {
1096 if (c->split == split && c->level < level &&
1097 c->defmap & (1<<i)) {
1098 split->defaults[i] = c;
1099 level = c->level;
1100 }
1101 }
1102 }
1103 }
1104}
1105
1106static void cbq_change_defmap(struct cbq_class *cl, u32 splitid, u32 def, u32 mask)
1107{
1108 struct cbq_class *split = NULL;
1109
1110 if (splitid == 0) {
1111 split = cl->split;
1112 if (!split)
1113 return;
1114 splitid = split->common.classid;
1115 }
1116
1117 if (split == NULL || split->common.classid != splitid) {
1118 for (split = cl->tparent; split; split = split->tparent)
1119 if (split->common.classid == splitid)
1120 break;
1121 }
1122
1123 if (split == NULL)
1124 return;
1125
1126 if (cl->split != split) {
1127 cl->defmap = 0;
1128 cbq_sync_defmap(cl);
1129 cl->split = split;
1130 cl->defmap = def & mask;
1131 } else
1132 cl->defmap = (cl->defmap & ~mask) | (def & mask);
1133
1134 cbq_sync_defmap(cl);
1135}
1136
1137static void cbq_unlink_class(struct cbq_class *this)
1138{
1139 struct cbq_class *cl, **clp;
1140 struct cbq_sched_data *q = qdisc_priv(this->qdisc);
1141
1142 qdisc_class_hash_remove(&q->clhash, &this->common);
1143
1144 if (this->tparent) {
1145 clp = &this->sibling;
1146 cl = *clp;
1147 do {
1148 if (cl == this) {
1149 *clp = cl->sibling;
1150 break;
1151 }
1152 clp = &cl->sibling;
1153 } while ((cl = *clp) != this->sibling);
1154
1155 if (this->tparent->children == this) {
1156 this->tparent->children = this->sibling;
1157 if (this->sibling == this)
1158 this->tparent->children = NULL;
1159 }
1160 } else {
1161 WARN_ON(this->sibling != this);
1162 }
1163}
1164
1165static void cbq_link_class(struct cbq_class *this)
1166{
1167 struct cbq_sched_data *q = qdisc_priv(this->qdisc);
1168 struct cbq_class *parent = this->tparent;
1169
1170 this->sibling = this;
1171 qdisc_class_hash_insert(&q->clhash, &this->common);
1172
1173 if (parent == NULL)
1174 return;
1175
1176 if (parent->children == NULL) {
1177 parent->children = this;
1178 } else {
1179 this->sibling = parent->children->sibling;
1180 parent->children->sibling = this;
1181 }
1182}
1183
1184static unsigned int cbq_drop(struct Qdisc *sch)
1185{
1186 struct cbq_sched_data *q = qdisc_priv(sch);
1187 struct cbq_class *cl, *cl_head;
1188 int prio;
1189 unsigned int len;
1190
1191 for (prio = TC_CBQ_MAXPRIO; prio >= 0; prio--) {
1192 cl_head = q->active[prio];
1193 if (!cl_head)
1194 continue;
1195
1196 cl = cl_head;
1197 do {
1198 if (cl->q->ops->drop && (len = cl->q->ops->drop(cl->q))) {
1199 sch->q.qlen--;
1200 if (!cl->q->q.qlen)
1201 cbq_deactivate_class(cl);
1202 return len;
1203 }
1204 } while ((cl = cl->next_alive) != cl_head);
1205 }
1206 return 0;
1207}
1208
1209static void
1210cbq_reset(struct Qdisc *sch)
1211{
1212 struct cbq_sched_data *q = qdisc_priv(sch);
1213 struct cbq_class *cl;
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, &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 if (nla_put(skb, TCA_CBQ_RATE, sizeof(cl->R_tab->rate), &cl->R_tab->rate))
1429 goto nla_put_failure;
1430 return skb->len;
1431
1432nla_put_failure:
1433 nlmsg_trim(skb, b);
1434 return -1;
1435}
1436
1437static int cbq_dump_lss(struct sk_buff *skb, struct cbq_class *cl)
1438{
1439 unsigned char *b = skb_tail_pointer(skb);
1440 struct tc_cbq_lssopt opt;
1441
1442 opt.flags = 0;
1443 if (cl->borrow == NULL)
1444 opt.flags |= TCF_CBQ_LSS_BOUNDED;
1445 if (cl->share == NULL)
1446 opt.flags |= TCF_CBQ_LSS_ISOLATED;
1447 opt.ewma_log = cl->ewma_log;
1448 opt.level = cl->level;
1449 opt.avpkt = cl->avpkt;
1450 opt.maxidle = cl->maxidle;
1451 opt.minidle = (u32)(-cl->minidle);
1452 opt.offtime = cl->offtime;
1453 opt.change = ~0;
1454 if (nla_put(skb, TCA_CBQ_LSSOPT, sizeof(opt), &opt))
1455 goto nla_put_failure;
1456 return skb->len;
1457
1458nla_put_failure:
1459 nlmsg_trim(skb, b);
1460 return -1;
1461}
1462
1463static int cbq_dump_wrr(struct sk_buff *skb, struct cbq_class *cl)
1464{
1465 unsigned char *b = skb_tail_pointer(skb);
1466 struct tc_cbq_wrropt opt;
1467
1468 opt.flags = 0;
1469 opt.allot = cl->allot;
1470 opt.priority = cl->priority + 1;
1471 opt.cpriority = cl->cpriority + 1;
1472 opt.weight = cl->weight;
1473 if (nla_put(skb, TCA_CBQ_WRROPT, sizeof(opt), &opt))
1474 goto nla_put_failure;
1475 return skb->len;
1476
1477nla_put_failure:
1478 nlmsg_trim(skb, b);
1479 return -1;
1480}
1481
1482static int cbq_dump_ovl(struct sk_buff *skb, struct cbq_class *cl)
1483{
1484 unsigned char *b = skb_tail_pointer(skb);
1485 struct tc_cbq_ovl opt;
1486
1487 opt.strategy = cl->ovl_strategy;
1488 opt.priority2 = cl->priority2 + 1;
1489 opt.pad = 0;
1490 opt.penalty = cl->penalty;
1491 if (nla_put(skb, TCA_CBQ_OVL_STRATEGY, sizeof(opt), &opt))
1492 goto nla_put_failure;
1493 return skb->len;
1494
1495nla_put_failure:
1496 nlmsg_trim(skb, b);
1497 return -1;
1498}
1499
1500static int cbq_dump_fopt(struct sk_buff *skb, struct cbq_class *cl)
1501{
1502 unsigned char *b = skb_tail_pointer(skb);
1503 struct tc_cbq_fopt opt;
1504
1505 if (cl->split || cl->defmap) {
1506 opt.split = cl->split ? cl->split->common.classid : 0;
1507 opt.defmap = cl->defmap;
1508 opt.defchange = ~0;
1509 if (nla_put(skb, TCA_CBQ_FOPT, sizeof(opt), &opt))
1510 goto nla_put_failure;
1511 }
1512 return skb->len;
1513
1514nla_put_failure:
1515 nlmsg_trim(skb, b);
1516 return -1;
1517}
1518
1519#ifdef CONFIG_NET_CLS_ACT
1520static int cbq_dump_police(struct sk_buff *skb, struct cbq_class *cl)
1521{
1522 unsigned char *b = skb_tail_pointer(skb);
1523 struct tc_cbq_police opt;
1524
1525 if (cl->police) {
1526 opt.police = cl->police;
1527 opt.__res1 = 0;
1528 opt.__res2 = 0;
1529 if (nla_put(skb, TCA_CBQ_POLICE, sizeof(opt), &opt))
1530 goto nla_put_failure;
1531 }
1532 return skb->len;
1533
1534nla_put_failure:
1535 nlmsg_trim(skb, b);
1536 return -1;
1537}
1538#endif
1539
1540static int cbq_dump_attr(struct sk_buff *skb, struct cbq_class *cl)
1541{
1542 if (cbq_dump_lss(skb, cl) < 0 ||
1543 cbq_dump_rate(skb, cl) < 0 ||
1544 cbq_dump_wrr(skb, cl) < 0 ||
1545 cbq_dump_ovl(skb, cl) < 0 ||
1546#ifdef CONFIG_NET_CLS_ACT
1547 cbq_dump_police(skb, cl) < 0 ||
1548#endif
1549 cbq_dump_fopt(skb, cl) < 0)
1550 return -1;
1551 return 0;
1552}
1553
1554static int cbq_dump(struct Qdisc *sch, struct sk_buff *skb)
1555{
1556 struct cbq_sched_data *q = qdisc_priv(sch);
1557 struct nlattr *nest;
1558
1559 nest = nla_nest_start(skb, TCA_OPTIONS);
1560 if (nest == NULL)
1561 goto nla_put_failure;
1562 if (cbq_dump_attr(skb, &q->link) < 0)
1563 goto nla_put_failure;
1564 nla_nest_end(skb, nest);
1565 return skb->len;
1566
1567nla_put_failure:
1568 nla_nest_cancel(skb, nest);
1569 return -1;
1570}
1571
1572static int
1573cbq_dump_stats(struct Qdisc *sch, struct gnet_dump *d)
1574{
1575 struct cbq_sched_data *q = qdisc_priv(sch);
1576
1577 q->link.xstats.avgidle = q->link.avgidle;
1578 return gnet_stats_copy_app(d, &q->link.xstats, sizeof(q->link.xstats));
1579}
1580
1581static int
1582cbq_dump_class(struct Qdisc *sch, unsigned long arg,
1583 struct sk_buff *skb, struct tcmsg *tcm)
1584{
1585 struct cbq_class *cl = (struct cbq_class *)arg;
1586 struct nlattr *nest;
1587
1588 if (cl->tparent)
1589 tcm->tcm_parent = cl->tparent->common.classid;
1590 else
1591 tcm->tcm_parent = TC_H_ROOT;
1592 tcm->tcm_handle = cl->common.classid;
1593 tcm->tcm_info = cl->q->handle;
1594
1595 nest = nla_nest_start(skb, TCA_OPTIONS);
1596 if (nest == NULL)
1597 goto nla_put_failure;
1598 if (cbq_dump_attr(skb, cl) < 0)
1599 goto nla_put_failure;
1600 nla_nest_end(skb, nest);
1601 return skb->len;
1602
1603nla_put_failure:
1604 nla_nest_cancel(skb, nest);
1605 return -1;
1606}
1607
1608static int
1609cbq_dump_class_stats(struct Qdisc *sch, unsigned long arg,
1610 struct gnet_dump *d)
1611{
1612 struct cbq_sched_data *q = qdisc_priv(sch);
1613 struct cbq_class *cl = (struct cbq_class *)arg;
1614
1615 cl->qstats.qlen = cl->q->q.qlen;
1616 cl->xstats.avgidle = cl->avgidle;
1617 cl->xstats.undertime = 0;
1618
1619 if (cl->undertime != PSCHED_PASTPERFECT)
1620 cl->xstats.undertime = cl->undertime - q->now;
1621
1622 if (gnet_stats_copy_basic(d, &cl->bstats) < 0 ||
1623 gnet_stats_copy_rate_est(d, &cl->bstats, &cl->rate_est) < 0 ||
1624 gnet_stats_copy_queue(d, &cl->qstats) < 0)
1625 return -1;
1626
1627 return gnet_stats_copy_app(d, &cl->xstats, sizeof(cl->xstats));
1628}
1629
1630static int cbq_graft(struct Qdisc *sch, unsigned long arg, struct Qdisc *new,
1631 struct Qdisc **old)
1632{
1633 struct cbq_class *cl = (struct cbq_class *)arg;
1634
1635 if (new == NULL) {
1636 new = qdisc_create_dflt(sch->dev_queue,
1637 &pfifo_qdisc_ops, cl->common.classid);
1638 if (new == NULL)
1639 return -ENOBUFS;
1640 } else {
1641#ifdef CONFIG_NET_CLS_ACT
1642 if (cl->police == TC_POLICE_RECLASSIFY)
1643 new->reshape_fail = cbq_reshape_fail;
1644#endif
1645 }
1646 sch_tree_lock(sch);
1647 *old = cl->q;
1648 cl->q = new;
1649 qdisc_tree_decrease_qlen(*old, (*old)->q.qlen);
1650 qdisc_reset(*old);
1651 sch_tree_unlock(sch);
1652
1653 return 0;
1654}
1655
1656static struct Qdisc *cbq_leaf(struct Qdisc *sch, unsigned long arg)
1657{
1658 struct cbq_class *cl = (struct cbq_class *)arg;
1659
1660 return cl->q;
1661}
1662
1663static void cbq_qlen_notify(struct Qdisc *sch, unsigned long arg)
1664{
1665 struct cbq_class *cl = (struct cbq_class *)arg;
1666
1667 if (cl->q->q.qlen == 0)
1668 cbq_deactivate_class(cl);
1669}
1670
1671static unsigned long cbq_get(struct Qdisc *sch, u32 classid)
1672{
1673 struct cbq_sched_data *q = qdisc_priv(sch);
1674 struct cbq_class *cl = cbq_class_lookup(q, classid);
1675
1676 if (cl) {
1677 cl->refcnt++;
1678 return (unsigned long)cl;
1679 }
1680 return 0;
1681}
1682
1683static void cbq_destroy_class(struct Qdisc *sch, struct cbq_class *cl)
1684{
1685 struct cbq_sched_data *q = qdisc_priv(sch);
1686
1687 WARN_ON(cl->filters);
1688
1689 tcf_destroy_chain(&cl->filter_list);
1690 qdisc_destroy(cl->q);
1691 qdisc_put_rtab(cl->R_tab);
1692 gen_kill_estimator(&cl->bstats, &cl->rate_est);
1693 if (cl != &q->link)
1694 kfree(cl);
1695}
1696
1697static void cbq_destroy(struct Qdisc *sch)
1698{
1699 struct cbq_sched_data *q = qdisc_priv(sch);
1700 struct hlist_node *next;
1701 struct cbq_class *cl;
1702 unsigned int h;
1703
1704#ifdef CONFIG_NET_CLS_ACT
1705 q->rx_class = NULL;
1706#endif
1707
1708
1709
1710
1711
1712 for (h = 0; h < q->clhash.hashsize; h++) {
1713 hlist_for_each_entry(cl, &q->clhash.hash[h], common.hnode)
1714 tcf_destroy_chain(&cl->filter_list);
1715 }
1716 for (h = 0; h < q->clhash.hashsize; h++) {
1717 hlist_for_each_entry_safe(cl, next, &q->clhash.hash[h],
1718 common.hnode)
1719 cbq_destroy_class(sch, cl);
1720 }
1721 qdisc_class_hash_destroy(&q->clhash);
1722}
1723
1724static void cbq_put(struct Qdisc *sch, unsigned long arg)
1725{
1726 struct cbq_class *cl = (struct cbq_class *)arg;
1727
1728 if (--cl->refcnt == 0) {
1729#ifdef CONFIG_NET_CLS_ACT
1730 spinlock_t *root_lock = qdisc_root_sleeping_lock(sch);
1731 struct cbq_sched_data *q = qdisc_priv(sch);
1732
1733 spin_lock_bh(root_lock);
1734 if (q->rx_class == cl)
1735 q->rx_class = NULL;
1736 spin_unlock_bh(root_lock);
1737#endif
1738
1739 cbq_destroy_class(sch, cl);
1740 }
1741}
1742
1743static int
1744cbq_change_class(struct Qdisc *sch, u32 classid, u32 parentid, struct nlattr **tca,
1745 unsigned long *arg)
1746{
1747 int err;
1748 struct cbq_sched_data *q = qdisc_priv(sch);
1749 struct cbq_class *cl = (struct cbq_class *)*arg;
1750 struct nlattr *opt = tca[TCA_OPTIONS];
1751 struct nlattr *tb[TCA_CBQ_MAX + 1];
1752 struct cbq_class *parent;
1753 struct qdisc_rate_table *rtab = NULL;
1754
1755 if (opt == NULL)
1756 return -EINVAL;
1757
1758 err = nla_parse_nested(tb, TCA_CBQ_MAX, opt, cbq_policy);
1759 if (err < 0)
1760 return err;
1761
1762 if (cl) {
1763
1764 if (parentid) {
1765 if (cl->tparent &&
1766 cl->tparent->common.classid != parentid)
1767 return -EINVAL;
1768 if (!cl->tparent && parentid != TC_H_ROOT)
1769 return -EINVAL;
1770 }
1771
1772 if (tb[TCA_CBQ_RATE]) {
1773 rtab = qdisc_get_rtab(nla_data(tb[TCA_CBQ_RATE]),
1774 tb[TCA_CBQ_RTAB]);
1775 if (rtab == NULL)
1776 return -EINVAL;
1777 }
1778
1779 if (tca[TCA_RATE]) {
1780 err = gen_replace_estimator(&cl->bstats, &cl->rate_est,
1781 qdisc_root_sleeping_lock(sch),
1782 tca[TCA_RATE]);
1783 if (err) {
1784 if (rtab)
1785 qdisc_put_rtab(rtab);
1786 return err;
1787 }
1788 }
1789
1790
1791 sch_tree_lock(sch);
1792
1793 if (cl->next_alive != NULL)
1794 cbq_deactivate_class(cl);
1795
1796 if (rtab) {
1797 qdisc_put_rtab(cl->R_tab);
1798 cl->R_tab = rtab;
1799 }
1800
1801 if (tb[TCA_CBQ_LSSOPT])
1802 cbq_set_lss(cl, nla_data(tb[TCA_CBQ_LSSOPT]));
1803
1804 if (tb[TCA_CBQ_WRROPT]) {
1805 cbq_rmprio(q, cl);
1806 cbq_set_wrr(cl, nla_data(tb[TCA_CBQ_WRROPT]));
1807 }
1808
1809 if (tb[TCA_CBQ_OVL_STRATEGY])
1810 cbq_set_overlimit(cl, nla_data(tb[TCA_CBQ_OVL_STRATEGY]));
1811
1812#ifdef CONFIG_NET_CLS_ACT
1813 if (tb[TCA_CBQ_POLICE])
1814 cbq_set_police(cl, nla_data(tb[TCA_CBQ_POLICE]));
1815#endif
1816
1817 if (tb[TCA_CBQ_FOPT])
1818 cbq_set_fopt(cl, nla_data(tb[TCA_CBQ_FOPT]));
1819
1820 if (cl->q->q.qlen)
1821 cbq_activate_class(cl);
1822
1823 sch_tree_unlock(sch);
1824
1825 return 0;
1826 }
1827
1828 if (parentid == TC_H_ROOT)
1829 return -EINVAL;
1830
1831 if (tb[TCA_CBQ_WRROPT] == NULL || tb[TCA_CBQ_RATE] == NULL ||
1832 tb[TCA_CBQ_LSSOPT] == NULL)
1833 return -EINVAL;
1834
1835 rtab = qdisc_get_rtab(nla_data(tb[TCA_CBQ_RATE]), tb[TCA_CBQ_RTAB]);
1836 if (rtab == NULL)
1837 return -EINVAL;
1838
1839 if (classid) {
1840 err = -EINVAL;
1841 if (TC_H_MAJ(classid ^ sch->handle) ||
1842 cbq_class_lookup(q, classid))
1843 goto failure;
1844 } else {
1845 int i;
1846 classid = TC_H_MAKE(sch->handle, 0x8000);
1847
1848 for (i = 0; i < 0x8000; i++) {
1849 if (++q->hgenerator >= 0x8000)
1850 q->hgenerator = 1;
1851 if (cbq_class_lookup(q, classid|q->hgenerator) == NULL)
1852 break;
1853 }
1854 err = -ENOSR;
1855 if (i >= 0x8000)
1856 goto failure;
1857 classid = classid|q->hgenerator;
1858 }
1859
1860 parent = &q->link;
1861 if (parentid) {
1862 parent = cbq_class_lookup(q, parentid);
1863 err = -EINVAL;
1864 if (parent == NULL)
1865 goto failure;
1866 }
1867
1868 err = -ENOBUFS;
1869 cl = kzalloc(sizeof(*cl), GFP_KERNEL);
1870 if (cl == NULL)
1871 goto failure;
1872
1873 if (tca[TCA_RATE]) {
1874 err = gen_new_estimator(&cl->bstats, &cl->rate_est,
1875 qdisc_root_sleeping_lock(sch),
1876 tca[TCA_RATE]);
1877 if (err) {
1878 kfree(cl);
1879 goto failure;
1880 }
1881 }
1882
1883 cl->R_tab = rtab;
1884 rtab = NULL;
1885 cl->refcnt = 1;
1886 cl->q = qdisc_create_dflt(sch->dev_queue, &pfifo_qdisc_ops, classid);
1887 if (!cl->q)
1888 cl->q = &noop_qdisc;
1889 cl->common.classid = classid;
1890 cl->tparent = parent;
1891 cl->qdisc = sch;
1892 cl->allot = parent->allot;
1893 cl->quantum = cl->allot;
1894 cl->weight = cl->R_tab->rate.rate;
1895
1896 sch_tree_lock(sch);
1897 cbq_link_class(cl);
1898 cl->borrow = cl->tparent;
1899 if (cl->tparent != &q->link)
1900 cl->share = cl->tparent;
1901 cbq_adjust_levels(parent);
1902 cl->minidle = -0x7FFFFFFF;
1903 cbq_set_lss(cl, nla_data(tb[TCA_CBQ_LSSOPT]));
1904 cbq_set_wrr(cl, nla_data(tb[TCA_CBQ_WRROPT]));
1905 if (cl->ewma_log == 0)
1906 cl->ewma_log = q->link.ewma_log;
1907 if (cl->maxidle == 0)
1908 cl->maxidle = q->link.maxidle;
1909 if (cl->avpkt == 0)
1910 cl->avpkt = q->link.avpkt;
1911 cl->overlimit = cbq_ovl_classic;
1912 if (tb[TCA_CBQ_OVL_STRATEGY])
1913 cbq_set_overlimit(cl, nla_data(tb[TCA_CBQ_OVL_STRATEGY]));
1914#ifdef CONFIG_NET_CLS_ACT
1915 if (tb[TCA_CBQ_POLICE])
1916 cbq_set_police(cl, nla_data(tb[TCA_CBQ_POLICE]));
1917#endif
1918 if (tb[TCA_CBQ_FOPT])
1919 cbq_set_fopt(cl, nla_data(tb[TCA_CBQ_FOPT]));
1920 sch_tree_unlock(sch);
1921
1922 qdisc_class_hash_grow(sch, &q->clhash);
1923
1924 *arg = (unsigned long)cl;
1925 return 0;
1926
1927failure:
1928 qdisc_put_rtab(rtab);
1929 return err;
1930}
1931
1932static int cbq_delete(struct Qdisc *sch, unsigned long arg)
1933{
1934 struct cbq_sched_data *q = qdisc_priv(sch);
1935 struct cbq_class *cl = (struct cbq_class *)arg;
1936 unsigned int qlen;
1937
1938 if (cl->filters || cl->children || cl == &q->link)
1939 return -EBUSY;
1940
1941 sch_tree_lock(sch);
1942
1943 qlen = cl->q->q.qlen;
1944 qdisc_reset(cl->q);
1945 qdisc_tree_decrease_qlen(cl->q, qlen);
1946
1947 if (cl->next_alive)
1948 cbq_deactivate_class(cl);
1949
1950 if (q->tx_borrowed == cl)
1951 q->tx_borrowed = q->tx_class;
1952 if (q->tx_class == cl) {
1953 q->tx_class = NULL;
1954 q->tx_borrowed = NULL;
1955 }
1956#ifdef CONFIG_NET_CLS_ACT
1957 if (q->rx_class == cl)
1958 q->rx_class = NULL;
1959#endif
1960
1961 cbq_unlink_class(cl);
1962 cbq_adjust_levels(cl->tparent);
1963 cl->defmap = 0;
1964 cbq_sync_defmap(cl);
1965
1966 cbq_rmprio(q, cl);
1967 sch_tree_unlock(sch);
1968
1969 BUG_ON(--cl->refcnt == 0);
1970
1971
1972
1973
1974
1975 return 0;
1976}
1977
1978static struct tcf_proto **cbq_find_tcf(struct Qdisc *sch, unsigned long arg)
1979{
1980 struct cbq_sched_data *q = qdisc_priv(sch);
1981 struct cbq_class *cl = (struct cbq_class *)arg;
1982
1983 if (cl == NULL)
1984 cl = &q->link;
1985
1986 return &cl->filter_list;
1987}
1988
1989static unsigned long cbq_bind_filter(struct Qdisc *sch, unsigned long parent,
1990 u32 classid)
1991{
1992 struct cbq_sched_data *q = qdisc_priv(sch);
1993 struct cbq_class *p = (struct cbq_class *)parent;
1994 struct cbq_class *cl = cbq_class_lookup(q, classid);
1995
1996 if (cl) {
1997 if (p && p->level <= cl->level)
1998 return 0;
1999 cl->filters++;
2000 return (unsigned long)cl;
2001 }
2002 return 0;
2003}
2004
2005static void cbq_unbind_filter(struct Qdisc *sch, unsigned long arg)
2006{
2007 struct cbq_class *cl = (struct cbq_class *)arg;
2008
2009 cl->filters--;
2010}
2011
2012static void cbq_walk(struct Qdisc *sch, struct qdisc_walker *arg)
2013{
2014 struct cbq_sched_data *q = qdisc_priv(sch);
2015 struct cbq_class *cl;
2016 unsigned int h;
2017
2018 if (arg->stop)
2019 return;
2020
2021 for (h = 0; h < q->clhash.hashsize; h++) {
2022 hlist_for_each_entry(cl, &q->clhash.hash[h], common.hnode) {
2023 if (arg->count < arg->skip) {
2024 arg->count++;
2025 continue;
2026 }
2027 if (arg->fn(sch, (unsigned long)cl, arg) < 0) {
2028 arg->stop = 1;
2029 return;
2030 }
2031 arg->count++;
2032 }
2033 }
2034}
2035
2036static const struct Qdisc_class_ops cbq_class_ops = {
2037 .graft = cbq_graft,
2038 .leaf = cbq_leaf,
2039 .qlen_notify = cbq_qlen_notify,
2040 .get = cbq_get,
2041 .put = cbq_put,
2042 .change = cbq_change_class,
2043 .delete = cbq_delete,
2044 .walk = cbq_walk,
2045 .tcf_chain = cbq_find_tcf,
2046 .bind_tcf = cbq_bind_filter,
2047 .unbind_tcf = cbq_unbind_filter,
2048 .dump = cbq_dump_class,
2049 .dump_stats = cbq_dump_class_stats,
2050};
2051
2052static struct Qdisc_ops cbq_qdisc_ops __read_mostly = {
2053 .next = NULL,
2054 .cl_ops = &cbq_class_ops,
2055 .id = "cbq",
2056 .priv_size = sizeof(struct cbq_sched_data),
2057 .enqueue = cbq_enqueue,
2058 .dequeue = cbq_dequeue,
2059 .peek = qdisc_peek_dequeued,
2060 .drop = cbq_drop,
2061 .init = cbq_init,
2062 .reset = cbq_reset,
2063 .destroy = cbq_destroy,
2064 .change = NULL,
2065 .dump = cbq_dump,
2066 .dump_stats = cbq_dump_stats,
2067 .owner = THIS_MODULE,
2068};
2069
2070static int __init cbq_module_init(void)
2071{
2072 return register_qdisc(&cbq_qdisc_ops);
2073}
2074static void __exit cbq_module_exit(void)
2075{
2076 unregister_qdisc(&cbq_qdisc_ops);
2077}
2078module_init(cbq_module_init)
2079module_exit(cbq_module_exit)
2080MODULE_LICENSE("GPL");
2081