?  search:
summary | log | graphiclog1 | graphiclog2 | commit | commitdiff | tree | refs | edit | fork
blame | history | raw | HEAD
Merge tag 'locks-v3.16-2' of git://git.samba.org/jlayton/linux
[linux/fpc-iii.git] / net / sched / sch_cbq.c
blobead526467ccae574d6afddb7a5146fc7507e68a9
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
72 struct cbq_sched_data;
73
74
75 struct 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_est64 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
144 struct cbq_sched_data {
145 struct Qdisc_class_hash clhash; /* Hash table of all classes */
146 int nclasses[TC_CBQ_MAXPRIO + 1];
147 unsigned int quanta[TC_CBQ_MAXPRIO + 1];
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
178 static inline struct cbq_class *
179 cbq_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
191 static struct cbq_class *
192 cbq_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
217 static struct cbq_class *
218 cbq_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)
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 * Step 3+n. If classifier selected a link sharing class,
274 * apply agency specific classifier.
275 * Repeat this procdure until we hit a leaf node.
276 */
277 head = cl;
278 }
279
280 fallback:
281 cl = head;
282
283 /*
284 * Step 4. No success...
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 * A packet has just been enqueued on the empty class.
296 * cbq_activate_class adds it to the tail of active class list
297 * of its priority band.
298 */
299
300 static 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 * Unlink class from active chain.
320 * Note that this same procedure is done directly in cbq_dequeue*
321 * during round-robin procedure.
322 */
323
324 static 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
350 static void
351 cbq_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
372 static int
373 cbq_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 /* Overlimit actions */
410
411 /* TC_CBQ_OVL_CLASSIC: (default) penalize leaf class by adding offtime */
412
413 static 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 * Class goes to sleep, so that it will have no
423 * chance to work avgidle. Let's forgive it 8)
424 *
425 * BTW cbq-2.0 has a crap in this
426 * place, apparently they forgot to shift it by cl->ewma_log.
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 /* Dirty work! We must schedule wakeups based on
443 * real available rate, rather than leaf rate,
444 * which may be tiny (even zero).
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 /* TC_CBQ_OVL_RCLASSIC: penalize by offtime classes in hierarchy, when
464 * they go overlimit
465 */
466
467 static 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 /* TC_CBQ_OVL_DELAY: delay until it will go to underlimit */
485
486 static 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 /* TC_CBQ_OVL_LOWPRIO: penalize class by lowering its priority band */
530
531 static 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
547 static 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
556 static 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
591 static 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
633 static 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
675 static inline void
676 cbq_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
697 static void
698 cbq_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
780 static inline struct cbq_class *
781 cbq_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
819 static inline struct sk_buff *
820 cbq_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
880 skip_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
911 next_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
922 static inline struct sk_buff *
923 cbq_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
940 static struct sk_buff *
941 cbq_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 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 /* All the classes are overlimit.
984 *
985 * It is possible, if:
986 *
987 * 1. Scheduler is empty.
988 * 2. Toplevel cutoff inhibited borrowing.
989 * 3. Root class is overlimit.
990 *
991 * Reset 2d and 3d conditions and retry.
992 *
993 * Note, that NS and cbq-2.0 are buggy, peeking
994 * an arbitrary class is appropriate for ancestor-only
995 * sharing, but not for toplevel algorithm.
996 *
997 * Our version is better, but slower, because it requires
998 * two passes, but it is unavoidable with top-level sharing.
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 /* No packets in scheduler or nobody wants to give them to us :-(
1010 * Sigh... start watchdog timer in the last case.
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 /* CBQ class maintanance routines */
1023
1024 static 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
1044 static 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 /* BUGGGG... Beware! This expression suffer of
1055 * arithmetic overflows!
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 ||
1062 cl->quantum > 32*qdisc_dev(cl->qdisc)->mtu) {
1063 pr_warn("CBQ: class %08x has bad quantum==%ld, repaired.\n",
1064 cl->common.classid, cl->quantum);
1065 cl->quantum = qdisc_dev(cl->qdisc)->mtu/2 + 1;
1066 }
1067 }
1068 }
1069 }
1070
1071 static void cbq_sync_defmap(struct cbq_class *cl)
1072 {
1073 struct cbq_sched_data *q = qdisc_priv(cl->qdisc);
1074 struct cbq_class *split = cl->split;
1075 unsigned int h;
1076 int i;
1077
1078 if (split == NULL)
1079 return;
1080
1081 for (i = 0; i <= TC_PRIO_MAX; i++) {
1082 if (split->defaults[i] == cl && !(cl->defmap & (1<<i)))
1083 split->defaults[i] = NULL;
1084 }
1085
1086 for (i = 0; i <= TC_PRIO_MAX; i++) {
1087 int level = split->level;
1088
1089 if (split->defaults[i])
1090 continue;
1091
1092 for (h = 0; h < q->clhash.hashsize; h++) {
1093 struct cbq_class *c;
1094
1095 hlist_for_each_entry(c, &q->clhash.hash[h],
1096 common.hnode) {
1097 if (c->split == split && c->level < level &&
1098 c->defmap & (1<<i)) {
1099 split->defaults[i] = c;
1100 level = c->level;
1101 }
1102 }
1103 }
1104 }
1105 }
1106
1107 static void cbq_change_defmap(struct cbq_class *cl, u32 splitid, u32 def, u32 mask)
1108 {
1109 struct cbq_class *split = NULL;
1110
1111 if (splitid == 0) {
1112 split = cl->split;
1113 if (!split)
1114 return;
1115 splitid = split->common.classid;
1116 }
1117
1118 if (split == NULL || split->common.classid != splitid) {
1119 for (split = cl->tparent; split; split = split->tparent)
1120 if (split->common.classid == splitid)
1121 break;
1122 }
1123
1124 if (split == NULL)
1125 return;
1126
1127 if (cl->split != split) {
1128 cl->defmap = 0;
1129 cbq_sync_defmap(cl);
1130 cl->split = split;
1131 cl->defmap = def & mask;
1132 } else
1133 cl->defmap = (cl->defmap & ~mask) | (def & mask);
1134
1135 cbq_sync_defmap(cl);
1136 }
1137
1138 static void cbq_unlink_class(struct cbq_class *this)
1139 {
1140 struct cbq_class *cl, **clp;
1141 struct cbq_sched_data *q = qdisc_priv(this->qdisc);
1142
1143 qdisc_class_hash_remove(&q->clhash, &this->common);
1144
1145 if (this->tparent) {
1146 clp = &this->sibling;
1147 cl = *clp;
1148 do {
1149 if (cl == this) {
1150 *clp = cl->sibling;
1151 break;
1152 }
1153 clp = &cl->sibling;
1154 } while ((cl = *clp) != this->sibling);
1155
1156 if (this->tparent->children == this) {
1157 this->tparent->children = this->sibling;
1158 if (this->sibling == this)
1159 this->tparent->children = NULL;
1160 }
1161 } else {
1162 WARN_ON(this->sibling != this);
1163 }
1164 }
1165
1166 static void cbq_link_class(struct cbq_class *this)
1167 {
1168 struct cbq_sched_data *q = qdisc_priv(this->qdisc);
1169 struct cbq_class *parent = this->tparent;
1170
1171 this->sibling = this;
1172 qdisc_class_hash_insert(&q->clhash, &this->common);
1173
1174 if (parent == NULL)
1175 return;
1176
1177 if (parent->children == NULL) {
1178 parent->children = this;
1179 } else {
1180 this->sibling = parent->children->sibling;
1181 parent->children->sibling = this;
1182 }
1183 }
1184
1185 static unsigned int cbq_drop(struct Qdisc *sch)
1186 {
1187 struct cbq_sched_data *q = qdisc_priv(sch);
1188 struct cbq_class *cl, *cl_head;
1189 int prio;
1190 unsigned int len;
1191
1192 for (prio = TC_CBQ_MAXPRIO; prio >= 0; prio--) {
1193 cl_head = q->active[prio];
1194 if (!cl_head)
1195 continue;
1196
1197 cl = cl_head;
1198 do {
1199 if (cl->q->ops->drop && (len = cl->q->ops->drop(cl->q))) {
1200 sch->q.qlen--;
1201 if (!cl->q->q.qlen)
1202 cbq_deactivate_class(cl);
1203 return len;
1204 }
1205 } while ((cl = cl->next_alive) != cl_head);
1206 }
1207 return 0;
1208 }
1209
1210 static void
1211 cbq_reset(struct Qdisc *sch)
1212 {
1213 struct cbq_sched_data *q = qdisc_priv(sch);
1214 struct cbq_class *cl;
1215 int prio;
1216 unsigned int h;
1217
1218 q->activemask = 0;
1219 q->pmask = 0;
1220 q->tx_class = NULL;
1221 q->tx_borrowed = NULL;
1222 qdisc_watchdog_cancel(&q->watchdog);
1223 hrtimer_cancel(&q->delay_timer);
1224 q->toplevel = TC_CBQ_MAXLEVEL;
1225 q->now = psched_get_time();
1226 q->now_rt = q->now;
1227
1228 for (prio = 0; prio <= TC_CBQ_MAXPRIO; prio++)
1229 q->active[prio] = NULL;
1230
1231 for (h = 0; h < q->clhash.hashsize; h++) {
1232 hlist_for_each_entry(cl, &q->clhash.hash[h], common.hnode) {
1233 qdisc_reset(cl->q);
1234
1235 cl->next_alive = NULL;
1236 cl->undertime = PSCHED_PASTPERFECT;
1237 cl->avgidle = cl->maxidle;
1238 cl->deficit = cl->quantum;
1239 cl->cpriority = cl->priority;
1240 }
1241 }
1242 sch->q.qlen = 0;
1243 }
1244
1245
1246 static int cbq_set_lss(struct cbq_class *cl, struct tc_cbq_lssopt *lss)
1247 {
1248 if (lss->change & TCF_CBQ_LSS_FLAGS) {
1249 cl->share = (lss->flags & TCF_CBQ_LSS_ISOLATED) ? NULL : cl->tparent;
1250 cl->borrow = (lss->flags & TCF_CBQ_LSS_BOUNDED) ? NULL : cl->tparent;
1251 }
1252 if (lss->change & TCF_CBQ_LSS_EWMA)
1253 cl->ewma_log = lss->ewma_log;
1254 if (lss->change & TCF_CBQ_LSS_AVPKT)
1255 cl->avpkt = lss->avpkt;
1256 if (lss->change & TCF_CBQ_LSS_MINIDLE)
1257 cl->minidle = -(long)lss->minidle;
1258 if (lss->change & TCF_CBQ_LSS_MAXIDLE) {
1259 cl->maxidle = lss->maxidle;
1260 cl->avgidle = lss->maxidle;
1261 }
1262 if (lss->change & TCF_CBQ_LSS_OFFTIME)
1263 cl->offtime = lss->offtime;
1264 return 0;
1265 }
1266
1267 static void cbq_rmprio(struct cbq_sched_data *q, struct cbq_class *cl)
1268 {
1269 q->nclasses[cl->priority]--;
1270 q->quanta[cl->priority] -= cl->weight;
1271 cbq_normalize_quanta(q, cl->priority);
1272 }
1273
1274 static void cbq_addprio(struct cbq_sched_data *q, struct cbq_class *cl)
1275 {
1276 q->nclasses[cl->priority]++;
1277 q->quanta[cl->priority] += cl->weight;
1278 cbq_normalize_quanta(q, cl->priority);
1279 }
1280
1281 static int cbq_set_wrr(struct cbq_class *cl, struct tc_cbq_wrropt *wrr)
1282 {
1283 struct cbq_sched_data *q = qdisc_priv(cl->qdisc);
1284
1285 if (wrr->allot)
1286 cl->allot = wrr->allot;
1287 if (wrr->weight)
1288 cl->weight = wrr->weight;
1289 if (wrr->priority) {
1290 cl->priority = wrr->priority - 1;
1291 cl->cpriority = cl->priority;
1292 if (cl->priority >= cl->priority2)
1293 cl->priority2 = TC_CBQ_MAXPRIO - 1;
1294 }
1295
1296 cbq_addprio(q, cl);
1297 return 0;
1298 }
1299
1300 static int cbq_set_overlimit(struct cbq_class *cl, struct tc_cbq_ovl *ovl)
1301 {
1302 switch (ovl->strategy) {
1303 case TC_CBQ_OVL_CLASSIC:
1304 cl->overlimit = cbq_ovl_classic;
1305 break;
1306 case TC_CBQ_OVL_DELAY:
1307 cl->overlimit = cbq_ovl_delay;
1308 break;
1309 case TC_CBQ_OVL_LOWPRIO:
1310 if (ovl->priority2 - 1 >= TC_CBQ_MAXPRIO ||
1311 ovl->priority2 - 1 <= cl->priority)
1312 return -EINVAL;
1313 cl->priority2 = ovl->priority2 - 1;
1314 cl->overlimit = cbq_ovl_lowprio;
1315 break;
1316 case TC_CBQ_OVL_DROP:
1317 cl->overlimit = cbq_ovl_drop;
1318 break;
1319 case TC_CBQ_OVL_RCLASSIC:
1320 cl->overlimit = cbq_ovl_rclassic;
1321 break;
1322 default:
1323 return -EINVAL;
1324 }
1325 cl->penalty = ovl->penalty;
1326 return 0;
1327 }
1328
1329 #ifdef CONFIG_NET_CLS_ACT
1330 static int cbq_set_police(struct cbq_class *cl, struct tc_cbq_police *p)
1331 {
1332 cl->police = p->police;
1333
1334 if (cl->q->handle) {
1335 if (p->police == TC_POLICE_RECLASSIFY)
1336 cl->q->reshape_fail = cbq_reshape_fail;
1337 else
1338 cl->q->reshape_fail = NULL;
1339 }
1340 return 0;
1341 }
1342 #endif
1343
1344 static int cbq_set_fopt(struct cbq_class *cl, struct tc_cbq_fopt *fopt)
1345 {
1346 cbq_change_defmap(cl, fopt->split, fopt->defmap, fopt->defchange);
1347 return 0;
1348 }
1349
1350 static const struct nla_policy cbq_policy[TCA_CBQ_MAX + 1] = {
1351 [TCA_CBQ_LSSOPT] = { .len = sizeof(struct tc_cbq_lssopt) },
1352 [TCA_CBQ_WRROPT] = { .len = sizeof(struct tc_cbq_wrropt) },
1353 [TCA_CBQ_FOPT] = { .len = sizeof(struct tc_cbq_fopt) },
1354 [TCA_CBQ_OVL_STRATEGY] = { .len = sizeof(struct tc_cbq_ovl) },
1355 [TCA_CBQ_RATE] = { .len = sizeof(struct tc_ratespec) },
1356 [TCA_CBQ_RTAB] = { .type = NLA_BINARY, .len = TC_RTAB_SIZE },
1357 [TCA_CBQ_POLICE] = { .len = sizeof(struct tc_cbq_police) },
1358 };
1359
1360 static int cbq_init(struct Qdisc *sch, struct nlattr *opt)
1361 {
1362 struct cbq_sched_data *q = qdisc_priv(sch);
1363 struct nlattr *tb[TCA_CBQ_MAX + 1];
1364 struct tc_ratespec *r;
1365 int err;
1366
1367 err = nla_parse_nested(tb, TCA_CBQ_MAX, opt, cbq_policy);
1368 if (err < 0)
1369 return err;
1370
1371 if (tb[TCA_CBQ_RTAB] == NULL || tb[TCA_CBQ_RATE] == NULL)
1372 return -EINVAL;
1373
1374 r = nla_data(tb[TCA_CBQ_RATE]);
1375
1376 if ((q->link.R_tab = qdisc_get_rtab(r, tb[TCA_CBQ_RTAB])) == NULL)
1377 return -EINVAL;
1378
1379 err = qdisc_class_hash_init(&q->clhash);
1380 if (err < 0)
1381 goto put_rtab;
1382
1383 q->link.refcnt = 1;
1384 q->link.sibling = &q->link;
1385 q->link.common.classid = sch->handle;
1386 q->link.qdisc = sch;
1387 q->link.q = qdisc_create_dflt(sch->dev_queue, &pfifo_qdisc_ops,
1388 sch->handle);
1389 if (!q->link.q)
1390 q->link.q = &noop_qdisc;
1391
1392 q->link.priority = TC_CBQ_MAXPRIO - 1;
1393 q->link.priority2 = TC_CBQ_MAXPRIO - 1;
1394 q->link.cpriority = TC_CBQ_MAXPRIO - 1;
1395 q->link.ovl_strategy = TC_CBQ_OVL_CLASSIC;
1396 q->link.overlimit = cbq_ovl_classic;
1397 q->link.allot = psched_mtu(qdisc_dev(sch));
1398 q->link.quantum = q->link.allot;
1399 q->link.weight = q->link.R_tab->rate.rate;
1400
1401 q->link.ewma_log = TC_CBQ_DEF_EWMA;
1402 q->link.avpkt = q->link.allot/2;
1403 q->link.minidle = -0x7FFFFFFF;
1404
1405 qdisc_watchdog_init(&q->watchdog, sch);
1406 hrtimer_init(&q->delay_timer, CLOCK_MONOTONIC, HRTIMER_MODE_ABS);
1407 q->delay_timer.function = cbq_undelay;
1408 q->toplevel = TC_CBQ_MAXLEVEL;
1409 q->now = psched_get_time();
1410 q->now_rt = q->now;
1411
1412 cbq_link_class(&q->link);
1413
1414 if (tb[TCA_CBQ_LSSOPT])
1415 cbq_set_lss(&q->link, nla_data(tb[TCA_CBQ_LSSOPT]));
1416
1417 cbq_addprio(q, &q->link);
1418 return 0;
1419
1420 put_rtab:
1421 qdisc_put_rtab(q->link.R_tab);
1422 return err;
1423 }
1424
1425 static int cbq_dump_rate(struct sk_buff *skb, struct cbq_class *cl)
1426 {
1427 unsigned char *b = skb_tail_pointer(skb);
1428
1429 if (nla_put(skb, TCA_CBQ_RATE, sizeof(cl->R_tab->rate), &cl->R_tab->rate))
1430 goto nla_put_failure;
1431 return skb->len;
1432
1433 nla_put_failure:
1434 nlmsg_trim(skb, b);
1435 return -1;
1436 }
1437
1438 static int cbq_dump_lss(struct sk_buff *skb, struct cbq_class *cl)
1439 {
1440 unsigned char *b = skb_tail_pointer(skb);
1441 struct tc_cbq_lssopt opt;
1442
1443 opt.flags = 0;
1444 if (cl->borrow == NULL)
1445 opt.flags |= TCF_CBQ_LSS_BOUNDED;
1446 if (cl->share == NULL)
1447 opt.flags |= TCF_CBQ_LSS_ISOLATED;
1448 opt.ewma_log = cl->ewma_log;
1449 opt.level = cl->level;
1450 opt.avpkt = cl->avpkt;
1451 opt.maxidle = cl->maxidle;
1452 opt.minidle = (u32)(-cl->minidle);
1453 opt.offtime = cl->offtime;
1454 opt.change = ~0;
1455 if (nla_put(skb, TCA_CBQ_LSSOPT, sizeof(opt), &opt))
1456 goto nla_put_failure;
1457 return skb->len;
1458
1459 nla_put_failure:
1460 nlmsg_trim(skb, b);
1461 return -1;
1462 }
1463
1464 static int cbq_dump_wrr(struct sk_buff *skb, struct cbq_class *cl)
1465 {
1466 unsigned char *b = skb_tail_pointer(skb);
1467 struct tc_cbq_wrropt opt;
1468
1469 memset(&opt, 0, sizeof(opt));
1470 opt.flags = 0;
1471 opt.allot = cl->allot;
1472 opt.priority = cl->priority + 1;
1473 opt.cpriority = cl->cpriority + 1;
1474 opt.weight = cl->weight;
1475 if (nla_put(skb, TCA_CBQ_WRROPT, sizeof(opt), &opt))
1476 goto nla_put_failure;
1477 return skb->len;
1478
1479 nla_put_failure:
1480 nlmsg_trim(skb, b);
1481 return -1;
1482 }
1483
1484 static int cbq_dump_ovl(struct sk_buff *skb, struct cbq_class *cl)
1485 {
1486 unsigned char *b = skb_tail_pointer(skb);
1487 struct tc_cbq_ovl opt;
1488
1489 opt.strategy = cl->ovl_strategy;
1490 opt.priority2 = cl->priority2 + 1;
1491 opt.pad = 0;
1492 opt.penalty = cl->penalty;
1493 if (nla_put(skb, TCA_CBQ_OVL_STRATEGY, sizeof(opt), &opt))
1494 goto nla_put_failure;
1495 return skb->len;
1496
1497 nla_put_failure:
1498 nlmsg_trim(skb, b);
1499 return -1;
1500 }
1501
1502 static int cbq_dump_fopt(struct sk_buff *skb, struct cbq_class *cl)
1503 {
1504 unsigned char *b = skb_tail_pointer(skb);
1505 struct tc_cbq_fopt opt;
1506
1507 if (cl->split || cl->defmap) {
1508 opt.split = cl->split ? cl->split->common.classid : 0;
1509 opt.defmap = cl->defmap;
1510 opt.defchange = ~0;
1511 if (nla_put(skb, TCA_CBQ_FOPT, sizeof(opt), &opt))
1512 goto nla_put_failure;
1513 }
1514 return skb->len;
1515
1516 nla_put_failure:
1517 nlmsg_trim(skb, b);
1518 return -1;
1519 }
1520
1521 #ifdef CONFIG_NET_CLS_ACT
1522 static int cbq_dump_police(struct sk_buff *skb, struct cbq_class *cl)
1523 {
1524 unsigned char *b = skb_tail_pointer(skb);
1525 struct tc_cbq_police opt;
1526
1527 if (cl->police) {
1528 opt.police = cl->police;
1529 opt.__res1 = 0;
1530 opt.__res2 = 0;
1531 if (nla_put(skb, TCA_CBQ_POLICE, sizeof(opt), &opt))
1532 goto nla_put_failure;
1533 }
1534 return skb->len;
1535
1536 nla_put_failure:
1537 nlmsg_trim(skb, b);
1538 return -1;
1539 }
1540 #endif
1541
1542 static int cbq_dump_attr(struct sk_buff *skb, struct cbq_class *cl)
1543 {
1544 if (cbq_dump_lss(skb, cl) < 0 ||
1545 cbq_dump_rate(skb, cl) < 0 ||
1546 cbq_dump_wrr(skb, cl) < 0 ||
1547 cbq_dump_ovl(skb, cl) < 0 ||
1548 #ifdef CONFIG_NET_CLS_ACT
1549 cbq_dump_police(skb, cl) < 0 ||
1550 #endif
1551 cbq_dump_fopt(skb, cl) < 0)
1552 return -1;
1553 return 0;
1554 }
1555
1556 static int cbq_dump(struct Qdisc *sch, struct sk_buff *skb)
1557 {
1558 struct cbq_sched_data *q = qdisc_priv(sch);
1559 struct nlattr *nest;
1560
1561 nest = nla_nest_start(skb, TCA_OPTIONS);
1562 if (nest == NULL)
1563 goto nla_put_failure;
1564 if (cbq_dump_attr(skb, &q->link) < 0)
1565 goto nla_put_failure;
1566 return nla_nest_end(skb, nest);
1567
1568 nla_put_failure:
1569 nla_nest_cancel(skb, nest);
1570 return -1;
1571 }
1572
1573 static int
1574 cbq_dump_stats(struct Qdisc *sch, struct gnet_dump *d)
1575 {
1576 struct cbq_sched_data *q = qdisc_priv(sch);
1577
1578 q->link.xstats.avgidle = q->link.avgidle;
1579 return gnet_stats_copy_app(d, &q->link.xstats, sizeof(q->link.xstats));
1580 }
1581
1582 static int
1583 cbq_dump_class(struct Qdisc *sch, unsigned long arg,
1584 struct sk_buff *skb, struct tcmsg *tcm)
1585 {
1586 struct cbq_class *cl = (struct cbq_class *)arg;
1587 struct nlattr *nest;
1588
1589 if (cl->tparent)
1590 tcm->tcm_parent = cl->tparent->common.classid;
1591 else
1592 tcm->tcm_parent = TC_H_ROOT;
1593 tcm->tcm_handle = cl->common.classid;
1594 tcm->tcm_info = cl->q->handle;
1595
1596 nest = nla_nest_start(skb, TCA_OPTIONS);
1597 if (nest == NULL)
1598 goto nla_put_failure;
1599 if (cbq_dump_attr(skb, cl) < 0)
1600 goto nla_put_failure;
1601 return nla_nest_end(skb, nest);
1602
1603 nla_put_failure:
1604 nla_nest_cancel(skb, nest);
1605 return -1;
1606 }
1607
1608 static int
1609 cbq_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
1630 static 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
1656 static 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
1663 static 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
1671 static 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
1683 static 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
1697 static 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 * Filters must be destroyed first because we don't destroy the
1709 * classes from root to leafs which means that filters can still
1710 * be bound to classes which have been destroyed already. --TGR '04
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
1724 static 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
1743 static int
1744 cbq_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 /* Check parent */
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 qdisc_put_rtab(rtab);
1785 return err;
1786 }
1787 }
1788
1789 /* Change class parameters */
1790 sch_tree_lock(sch);
1791
1792 if (cl->next_alive != NULL)
1793 cbq_deactivate_class(cl);
1794
1795 if (rtab) {
1796 qdisc_put_rtab(cl->R_tab);
1797 cl->R_tab = rtab;
1798 }
1799
1800 if (tb[TCA_CBQ_LSSOPT])
1801 cbq_set_lss(cl, nla_data(tb[TCA_CBQ_LSSOPT]));
1802
1803 if (tb[TCA_CBQ_WRROPT]) {
1804 cbq_rmprio(q, cl);
1805 cbq_set_wrr(cl, nla_data(tb[TCA_CBQ_WRROPT]));
1806 }
1807
1808 if (tb[TCA_CBQ_OVL_STRATEGY])
1809 cbq_set_overlimit(cl, nla_data(tb[TCA_CBQ_OVL_STRATEGY]));
1810
1811 #ifdef CONFIG_NET_CLS_ACT
1812 if (tb[TCA_CBQ_POLICE])
1813 cbq_set_police(cl, nla_data(tb[TCA_CBQ_POLICE]));
1814 #endif
1815
1816 if (tb[TCA_CBQ_FOPT])
1817 cbq_set_fopt(cl, nla_data(tb[TCA_CBQ_FOPT]));
1818
1819 if (cl->q->q.qlen)
1820 cbq_activate_class(cl);
1821
1822 sch_tree_unlock(sch);
1823
1824 return 0;
1825 }
1826
1827 if (parentid == TC_H_ROOT)
1828 return -EINVAL;
1829
1830 if (tb[TCA_CBQ_WRROPT] == NULL || tb[TCA_CBQ_RATE] == NULL ||
1831 tb[TCA_CBQ_LSSOPT] == NULL)
1832 return -EINVAL;
1833
1834 rtab = qdisc_get_rtab(nla_data(tb[TCA_CBQ_RATE]), tb[TCA_CBQ_RTAB]);
1835 if (rtab == NULL)
1836 return -EINVAL;
1837
1838 if (classid) {
1839 err = -EINVAL;
1840 if (TC_H_MAJ(classid ^ sch->handle) ||
1841 cbq_class_lookup(q, classid))
1842 goto failure;
1843 } else {
1844 int i;
1845 classid = TC_H_MAKE(sch->handle, 0x8000);
1846
1847 for (i = 0; i < 0x8000; i++) {
1848 if (++q->hgenerator >= 0x8000)
1849 q->hgenerator = 1;
1850 if (cbq_class_lookup(q, classid|q->hgenerator) == NULL)
1851 break;
1852 }
1853 err = -ENOSR;
1854 if (i >= 0x8000)
1855 goto failure;
1856 classid = classid|q->hgenerator;
1857 }
1858
1859 parent = &q->link;
1860 if (parentid) {
1861 parent = cbq_class_lookup(q, parentid);
1862 err = -EINVAL;
1863 if (parent == NULL)
1864 goto failure;
1865 }
1866
1867 err = -ENOBUFS;
1868 cl = kzalloc(sizeof(*cl), GFP_KERNEL);
1869 if (cl == NULL)
1870 goto failure;
1871
1872 if (tca[TCA_RATE]) {
1873 err = gen_new_estimator(&cl->bstats, &cl->rate_est,
1874 qdisc_root_sleeping_lock(sch),
1875 tca[TCA_RATE]);
1876 if (err) {
1877 kfree(cl);
1878 goto failure;
1879 }
1880 }
1881
1882 cl->R_tab = rtab;
1883 rtab = NULL;
1884 cl->refcnt = 1;
1885 cl->q = qdisc_create_dflt(sch->dev_queue, &pfifo_qdisc_ops, classid);
1886 if (!cl->q)
1887 cl->q = &noop_qdisc;
1888 cl->common.classid = classid;
1889 cl->tparent = parent;
1890 cl->qdisc = sch;
1891 cl->allot = parent->allot;
1892 cl->quantum = cl->allot;
1893 cl->weight = cl->R_tab->rate.rate;
1894
1895 sch_tree_lock(sch);
1896 cbq_link_class(cl);
1897 cl->borrow = cl->tparent;
1898 if (cl->tparent != &q->link)
1899 cl->share = cl->tparent;
1900 cbq_adjust_levels(parent);
1901 cl->minidle = -0x7FFFFFFF;
1902 cbq_set_lss(cl, nla_data(tb[TCA_CBQ_LSSOPT]));
1903 cbq_set_wrr(cl, nla_data(tb[TCA_CBQ_WRROPT]));
1904 if (cl->ewma_log == 0)
1905 cl->ewma_log = q->link.ewma_log;
1906 if (cl->maxidle == 0)
1907 cl->maxidle = q->link.maxidle;
1908 if (cl->avpkt == 0)
1909 cl->avpkt = q->link.avpkt;
1910 cl->overlimit = cbq_ovl_classic;
1911 if (tb[TCA_CBQ_OVL_STRATEGY])
1912 cbq_set_overlimit(cl, nla_data(tb[TCA_CBQ_OVL_STRATEGY]));
1913 #ifdef CONFIG_NET_CLS_ACT
1914 if (tb[TCA_CBQ_POLICE])
1915 cbq_set_police(cl, nla_data(tb[TCA_CBQ_POLICE]));
1916 #endif
1917 if (tb[TCA_CBQ_FOPT])
1918 cbq_set_fopt(cl, nla_data(tb[TCA_CBQ_FOPT]));
1919 sch_tree_unlock(sch);
1920
1921 qdisc_class_hash_grow(sch, &q->clhash);
1922
1923 *arg = (unsigned long)cl;
1924 return 0;
1925
1926 failure:
1927 qdisc_put_rtab(rtab);
1928 return err;
1929 }
1930
1931 static int cbq_delete(struct Qdisc *sch, unsigned long arg)
1932 {
1933 struct cbq_sched_data *q = qdisc_priv(sch);
1934 struct cbq_class *cl = (struct cbq_class *)arg;
1935 unsigned int qlen;
1936
1937 if (cl->filters || cl->children || cl == &q->link)
1938 return -EBUSY;
1939
1940 sch_tree_lock(sch);
1941
1942 qlen = cl->q->q.qlen;
1943 qdisc_reset(cl->q);
1944 qdisc_tree_decrease_qlen(cl->q, qlen);
1945
1946 if (cl->next_alive)
1947 cbq_deactivate_class(cl);
1948
1949 if (q->tx_borrowed == cl)
1950 q->tx_borrowed = q->tx_class;
1951 if (q->tx_class == cl) {
1952 q->tx_class = NULL;
1953 q->tx_borrowed = NULL;
1954 }
1955 #ifdef CONFIG_NET_CLS_ACT
1956 if (q->rx_class == cl)
1957 q->rx_class = NULL;
1958 #endif
1959
1960 cbq_unlink_class(cl);
1961 cbq_adjust_levels(cl->tparent);
1962 cl->defmap = 0;
1963 cbq_sync_defmap(cl);
1964
1965 cbq_rmprio(q, cl);
1966 sch_tree_unlock(sch);
1967
1968 BUG_ON(--cl->refcnt == 0);
1969 /*
1970 * This shouldn't happen: we "hold" one cops->get() when called
1971 * from tc_ctl_tclass; the destroy method is done from cops->put().
1972 */
1973
1974 return 0;
1975 }
1976
1977 static struct tcf_proto **cbq_find_tcf(struct Qdisc *sch, unsigned long arg)
1978 {
1979 struct cbq_sched_data *q = qdisc_priv(sch);
1980 struct cbq_class *cl = (struct cbq_class *)arg;
1981
1982 if (cl == NULL)
1983 cl = &q->link;
1984
1985 return &cl->filter_list;
1986 }
1987
1988 static unsigned long cbq_bind_filter(struct Qdisc *sch, unsigned long parent,
1989 u32 classid)
1990 {
1991 struct cbq_sched_data *q = qdisc_priv(sch);
1992 struct cbq_class *p = (struct cbq_class *)parent;
1993 struct cbq_class *cl = cbq_class_lookup(q, classid);
1994
1995 if (cl) {
1996 if (p && p->level <= cl->level)
1997 return 0;
1998 cl->filters++;
1999 return (unsigned long)cl;
2000 }
2001 return 0;
2002 }
2003
2004 static void cbq_unbind_filter(struct Qdisc *sch, unsigned long arg)
2005 {
2006 struct cbq_class *cl = (struct cbq_class *)arg;
2007
2008 cl->filters--;
2009 }
2010
2011 static void cbq_walk(struct Qdisc *sch, struct qdisc_walker *arg)
2012 {
2013 struct cbq_sched_data *q = qdisc_priv(sch);
2014 struct cbq_class *cl;
2015 unsigned int h;
2016
2017 if (arg->stop)
2018 return;
2019
2020 for (h = 0; h < q->clhash.hashsize; h++) {
2021 hlist_for_each_entry(cl, &q->clhash.hash[h], common.hnode) {
2022 if (arg->count < arg->skip) {
2023 arg->count++;
2024 continue;
2025 }
2026 if (arg->fn(sch, (unsigned long)cl, arg) < 0) {
2027 arg->stop = 1;
2028 return;
2029 }
2030 arg->count++;
2031 }
2032 }
2033 }
2034
2035 static const struct Qdisc_class_ops cbq_class_ops = {
2036 .graft = cbq_graft,
2037 .leaf = cbq_leaf,
2038 .qlen_notify = cbq_qlen_notify,
2039 .get = cbq_get,
2040 .put = cbq_put,
2041 .change = cbq_change_class,
2042 .delete = cbq_delete,
2043 .walk = cbq_walk,
2044 .tcf_chain = cbq_find_tcf,
2045 .bind_tcf = cbq_bind_filter,
2046 .unbind_tcf = cbq_unbind_filter,
2047 .dump = cbq_dump_class,
2048 .dump_stats = cbq_dump_class_stats,
2049 };
2050
2051 static struct Qdisc_ops cbq_qdisc_ops __read_mostly = {
2052 .next = NULL,
2053 .cl_ops = &cbq_class_ops,
2054 .id = "cbq",
2055 .priv_size = sizeof(struct cbq_sched_data),
2056 .enqueue = cbq_enqueue,
2057 .dequeue = cbq_dequeue,
2058 .peek = qdisc_peek_dequeued,
2059 .drop = cbq_drop,
2060 .init = cbq_init,
2061 .reset = cbq_reset,
2062 .destroy = cbq_destroy,
2063 .change = NULL,
2064 .dump = cbq_dump,
2065 .dump_stats = cbq_dump_stats,
2066 .owner = THIS_MODULE,
2067 };
2068
2069 static int __init cbq_module_init(void)
2070 {
2071 return register_qdisc(&cbq_qdisc_ops);
2072 }
2073 static void __exit cbq_module_exit(void)
2074 {
2075 unregister_qdisc(&cbq_qdisc_ops);
2076 }
2077 module_init(cbq_module_init)
2078 module_exit(cbq_module_exit)
2079 MODULE_LICENSE("GPL");
Linux with added FPC-III support