?  search:
summary | log | graphiclog1 | graphiclog2 | commit | commitdiff | tree | refs | edit | fork
blame | history | raw | HEAD
rbtree: move augmented rbtree functionality to rbtree_augmented.h
[linux-2.6.git] / net / sched / sch_cbq.c
blob564b9fc8efd3c8778ef8ba155cf17f79d92a9a80
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_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
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 = ktime_set(0, 0);
513 expires = ktime_add_ns(expires, PSCHED_TICKS2NS(sched));
514 if (hrtimer_try_to_cancel(&q->delay_timer) &&
515 ktime_to_ns(ktime_sub(
516 hrtimer_get_expires(&q->delay_timer),
517 expires)) > 0)
518 hrtimer_set_expires(&q->delay_timer, expires);
519 hrtimer_restart(&q->delay_timer);
520 cl->delayed = 1;
521 cl->xstats.overactions++;
522 return;
523 }
524 delay = 1;
525 }
526 if (q->wd_expires == 0 || q->wd_expires > delay)
527 q->wd_expires = delay;
528 }
529
530 /* TC_CBQ_OVL_LOWPRIO: penalize class by lowering its priority band */
531
532 static void cbq_ovl_lowprio(struct cbq_class *cl)
533 {
534 struct cbq_sched_data *q = qdisc_priv(cl->qdisc);
535
536 cl->penalized = q->now + cl->penalty;
537
538 if (cl->cpriority != cl->priority2) {
539 cl->cpriority = cl->priority2;
540 q->pmask |= (1<<cl->cpriority);
541 cl->xstats.overactions++;
542 }
543 cbq_ovl_classic(cl);
544 }
545
546 /* TC_CBQ_OVL_DROP: penalize class by dropping */
547
548 static void cbq_ovl_drop(struct cbq_class *cl)
549 {
550 if (cl->q->ops->drop)
551 if (cl->q->ops->drop(cl->q))
552 cl->qdisc->q.qlen--;
553 cl->xstats.overactions++;
554 cbq_ovl_classic(cl);
555 }
556
557 static psched_tdiff_t cbq_undelay_prio(struct cbq_sched_data *q, int prio,
558 psched_time_t now)
559 {
560 struct cbq_class *cl;
561 struct cbq_class *cl_prev = q->active[prio];
562 psched_time_t sched = now;
563
564 if (cl_prev == NULL)
565 return 0;
566
567 do {
568 cl = cl_prev->next_alive;
569 if (now - cl->penalized > 0) {
570 cl_prev->next_alive = cl->next_alive;
571 cl->next_alive = NULL;
572 cl->cpriority = cl->priority;
573 cl->delayed = 0;
574 cbq_activate_class(cl);
575
576 if (cl == q->active[prio]) {
577 q->active[prio] = cl_prev;
578 if (cl == q->active[prio]) {
579 q->active[prio] = NULL;
580 return 0;
581 }
582 }
583
584 cl = cl_prev->next_alive;
585 } else if (sched - cl->penalized > 0)
586 sched = cl->penalized;
587 } while ((cl_prev = cl) != q->active[prio]);
588
589 return sched - now;
590 }
591
592 static enum hrtimer_restart cbq_undelay(struct hrtimer *timer)
593 {
594 struct cbq_sched_data *q = container_of(timer, struct cbq_sched_data,
595 delay_timer);
596 struct Qdisc *sch = q->watchdog.qdisc;
597 psched_time_t now;
598 psched_tdiff_t delay = 0;
599 unsigned int pmask;
600
601 now = psched_get_time();
602
603 pmask = q->pmask;
604 q->pmask = 0;
605
606 while (pmask) {
607 int prio = ffz(~pmask);
608 psched_tdiff_t tmp;
609
610 pmask &= ~(1<<prio);
611
612 tmp = cbq_undelay_prio(q, prio, now);
613 if (tmp > 0) {
614 q->pmask |= 1<<prio;
615 if (tmp < delay || delay == 0)
616 delay = tmp;
617 }
618 }
619
620 if (delay) {
621 ktime_t time;
622
623 time = ktime_set(0, 0);
624 time = ktime_add_ns(time, PSCHED_TICKS2NS(now + delay));
625 hrtimer_start(&q->delay_timer, time, HRTIMER_MODE_ABS);
626 }
627
628 qdisc_unthrottled(sch);
629 __netif_schedule(qdisc_root(sch));
630 return HRTIMER_NORESTART;
631 }
632
633 #ifdef CONFIG_NET_CLS_ACT
634 static int cbq_reshape_fail(struct sk_buff *skb, struct Qdisc *child)
635 {
636 struct Qdisc *sch = child->__parent;
637 struct cbq_sched_data *q = qdisc_priv(sch);
638 struct cbq_class *cl = q->rx_class;
639
640 q->rx_class = NULL;
641
642 if (cl && (cl = cbq_reclassify(skb, cl)) != NULL) {
643 int ret;
644
645 cbq_mark_toplevel(q, cl);
646
647 q->rx_class = cl;
648 cl->q->__parent = sch;
649
650 ret = qdisc_enqueue(skb, cl->q);
651 if (ret == NET_XMIT_SUCCESS) {
652 sch->q.qlen++;
653 if (!cl->next_alive)
654 cbq_activate_class(cl);
655 return 0;
656 }
657 if (net_xmit_drop_count(ret))
658 sch->qstats.drops++;
659 return 0;
660 }
661
662 sch->qstats.drops++;
663 return -1;
664 }
665 #endif
666
667 /*
668 * It is mission critical procedure.
669 *
670 * We "regenerate" toplevel cutoff, if transmitting class
671 * has backlog and it is not regulated. It is not part of
672 * original CBQ description, but looks more reasonable.
673 * Probably, it is wrong. This question needs further investigation.
674 */
675
676 static inline void
677 cbq_update_toplevel(struct cbq_sched_data *q, struct cbq_class *cl,
678 struct cbq_class *borrowed)
679 {
680 if (cl && q->toplevel >= borrowed->level) {
681 if (cl->q->q.qlen > 1) {
682 do {
683 if (borrowed->undertime == PSCHED_PASTPERFECT) {
684 q->toplevel = borrowed->level;
685 return;
686 }
687 } while ((borrowed = borrowed->borrow) != NULL);
688 }
689 #if 0
690 /* It is not necessary now. Uncommenting it
691 will save CPU cycles, but decrease fairness.
692 */
693 q->toplevel = TC_CBQ_MAXLEVEL;
694 #endif
695 }
696 }
697
698 static void
699 cbq_update(struct cbq_sched_data *q)
700 {
701 struct cbq_class *this = q->tx_class;
702 struct cbq_class *cl = this;
703 int len = q->tx_len;
704
705 q->tx_class = NULL;
706
707 for ( ; cl; cl = cl->share) {
708 long avgidle = cl->avgidle;
709 long idle;
710
711 cl->bstats.packets++;
712 cl->bstats.bytes += len;
713
714 /*
715 * (now - last) is total time between packet right edges.
716 * (last_pktlen/rate) is "virtual" busy time, so that
717 *
718 * idle = (now - last) - last_pktlen/rate
719 */
720
721 idle = q->now - cl->last;
722 if ((unsigned long)idle > 128*1024*1024) {
723 avgidle = cl->maxidle;
724 } else {
725 idle -= L2T(cl, len);
726
727 /* true_avgidle := (1-W)*true_avgidle + W*idle,
728 * where W=2^{-ewma_log}. But cl->avgidle is scaled:
729 * cl->avgidle == true_avgidle/W,
730 * hence:
731 */
732 avgidle += idle - (avgidle>>cl->ewma_log);
733 }
734
735 if (avgidle <= 0) {
736 /* Overlimit or at-limit */
737
738 if (avgidle < cl->minidle)
739 avgidle = cl->minidle;
740
741 cl->avgidle = avgidle;
742
743 /* Calculate expected time, when this class
744 * will be allowed to send.
745 * It will occur, when:
746 * (1-W)*true_avgidle + W*delay = 0, i.e.
747 * idle = (1/W - 1)*(-true_avgidle)
748 * or
749 * idle = (1 - W)*(-cl->avgidle);
750 */
751 idle = (-avgidle) - ((-avgidle) >> cl->ewma_log);
752
753 /*
754 * That is not all.
755 * To maintain the rate allocated to the class,
756 * we add to undertime virtual clock,
757 * necessary to complete transmitted packet.
758 * (len/phys_bandwidth has been already passed
759 * to the moment of cbq_update)
760 */
761
762 idle -= L2T(&q->link, len);
763 idle += L2T(cl, len);
764
765 cl->undertime = q->now + idle;
766 } else {
767 /* Underlimit */
768
769 cl->undertime = PSCHED_PASTPERFECT;
770 if (avgidle > cl->maxidle)
771 cl->avgidle = cl->maxidle;
772 else
773 cl->avgidle = avgidle;
774 }
775 cl->last = q->now;
776 }
777
778 cbq_update_toplevel(q, this, q->tx_borrowed);
779 }
780
781 static inline struct cbq_class *
782 cbq_under_limit(struct cbq_class *cl)
783 {
784 struct cbq_sched_data *q = qdisc_priv(cl->qdisc);
785 struct cbq_class *this_cl = cl;
786
787 if (cl->tparent == NULL)
788 return cl;
789
790 if (cl->undertime == PSCHED_PASTPERFECT || q->now >= cl->undertime) {
791 cl->delayed = 0;
792 return cl;
793 }
794
795 do {
796 /* It is very suspicious place. Now overlimit
797 * action is generated for not bounded classes
798 * only if link is completely congested.
799 * Though it is in agree with ancestor-only paradigm,
800 * it looks very stupid. Particularly,
801 * it means that this chunk of code will either
802 * never be called or result in strong amplification
803 * of burstiness. Dangerous, silly, and, however,
804 * no another solution exists.
805 */
806 cl = cl->borrow;
807 if (!cl) {
808 this_cl->qstats.overlimits++;
809 this_cl->overlimit(this_cl);
810 return NULL;
811 }
812 if (cl->level > q->toplevel)
813 return NULL;
814 } while (cl->undertime != PSCHED_PASTPERFECT && q->now < cl->undertime);
815
816 cl->delayed = 0;
817 return cl;
818 }
819
820 static inline struct sk_buff *
821 cbq_dequeue_prio(struct Qdisc *sch, int prio)
822 {
823 struct cbq_sched_data *q = qdisc_priv(sch);
824 struct cbq_class *cl_tail, *cl_prev, *cl;
825 struct sk_buff *skb;
826 int deficit;
827
828 cl_tail = cl_prev = q->active[prio];
829 cl = cl_prev->next_alive;
830
831 do {
832 deficit = 0;
833
834 /* Start round */
835 do {
836 struct cbq_class *borrow = cl;
837
838 if (cl->q->q.qlen &&
839 (borrow = cbq_under_limit(cl)) == NULL)
840 goto skip_class;
841
842 if (cl->deficit <= 0) {
843 /* Class exhausted its allotment per
844 * this round. Switch to the next one.
845 */
846 deficit = 1;
847 cl->deficit += cl->quantum;
848 goto next_class;
849 }
850
851 skb = cl->q->dequeue(cl->q);
852
853 /* Class did not give us any skb :-(
854 * It could occur even if cl->q->q.qlen != 0
855 * f.e. if cl->q == "tbf"
856 */
857 if (skb == NULL)
858 goto skip_class;
859
860 cl->deficit -= qdisc_pkt_len(skb);
861 q->tx_class = cl;
862 q->tx_borrowed = borrow;
863 if (borrow != cl) {
864 #ifndef CBQ_XSTATS_BORROWS_BYTES
865 borrow->xstats.borrows++;
866 cl->xstats.borrows++;
867 #else
868 borrow->xstats.borrows += qdisc_pkt_len(skb);
869 cl->xstats.borrows += qdisc_pkt_len(skb);
870 #endif
871 }
872 q->tx_len = qdisc_pkt_len(skb);
873
874 if (cl->deficit <= 0) {
875 q->active[prio] = cl;
876 cl = cl->next_alive;
877 cl->deficit += cl->quantum;
878 }
879 return skb;
880
881 skip_class:
882 if (cl->q->q.qlen == 0 || prio != cl->cpriority) {
883 /* Class is empty or penalized.
884 * Unlink it from active chain.
885 */
886 cl_prev->next_alive = cl->next_alive;
887 cl->next_alive = NULL;
888
889 /* Did cl_tail point to it? */
890 if (cl == cl_tail) {
891 /* Repair it! */
892 cl_tail = cl_prev;
893
894 /* Was it the last class in this band? */
895 if (cl == cl_tail) {
896 /* Kill the band! */
897 q->active[prio] = NULL;
898 q->activemask &= ~(1<<prio);
899 if (cl->q->q.qlen)
900 cbq_activate_class(cl);
901 return NULL;
902 }
903
904 q->active[prio] = cl_tail;
905 }
906 if (cl->q->q.qlen)
907 cbq_activate_class(cl);
908
909 cl = cl_prev;
910 }
911
912 next_class:
913 cl_prev = cl;
914 cl = cl->next_alive;
915 } while (cl_prev != cl_tail);
916 } while (deficit);
917
918 q->active[prio] = cl_prev;
919
920 return NULL;
921 }
922
923 static inline struct sk_buff *
924 cbq_dequeue_1(struct Qdisc *sch)
925 {
926 struct cbq_sched_data *q = qdisc_priv(sch);
927 struct sk_buff *skb;
928 unsigned int activemask;
929
930 activemask = q->activemask & 0xFF;
931 while (activemask) {
932 int prio = ffz(~activemask);
933 activemask &= ~(1<<prio);
934 skb = cbq_dequeue_prio(sch, prio);
935 if (skb)
936 return skb;
937 }
938 return NULL;
939 }
940
941 static struct sk_buff *
942 cbq_dequeue(struct Qdisc *sch)
943 {
944 struct sk_buff *skb;
945 struct cbq_sched_data *q = qdisc_priv(sch);
946 psched_time_t now;
947 psched_tdiff_t incr;
948
949 now = psched_get_time();
950 incr = now - q->now_rt;
951
952 if (q->tx_class) {
953 psched_tdiff_t incr2;
954 /* Time integrator. We calculate EOS time
955 * by adding expected packet transmission time.
956 * If real time is greater, we warp artificial clock,
957 * so that:
958 *
959 * cbq_time = max(real_time, work);
960 */
961 incr2 = L2T(&q->link, q->tx_len);
962 q->now += incr2;
963 cbq_update(q);
964 if ((incr -= incr2) < 0)
965 incr = 0;
966 }
967 q->now += incr;
968 q->now_rt = now;
969
970 for (;;) {
971 q->wd_expires = 0;
972
973 skb = cbq_dequeue_1(sch);
974 if (skb) {
975 qdisc_bstats_update(sch, skb);
976 sch->q.qlen--;
977 qdisc_unthrottled(sch);
978 return skb;
979 }
980
981 /* All the classes are overlimit.
982 *
983 * It is possible, if:
984 *
985 * 1. Scheduler is empty.
986 * 2. Toplevel cutoff inhibited borrowing.
987 * 3. Root class is overlimit.
988 *
989 * Reset 2d and 3d conditions and retry.
990 *
991 * Note, that NS and cbq-2.0 are buggy, peeking
992 * an arbitrary class is appropriate for ancestor-only
993 * sharing, but not for toplevel algorithm.
994 *
995 * Our version is better, but slower, because it requires
996 * two passes, but it is unavoidable with top-level sharing.
997 */
998
999 if (q->toplevel == TC_CBQ_MAXLEVEL &&
1000 q->link.undertime == PSCHED_PASTPERFECT)
1001 break;
1002
1003 q->toplevel = TC_CBQ_MAXLEVEL;
1004 q->link.undertime = PSCHED_PASTPERFECT;
1005 }
1006
1007 /* No packets in scheduler or nobody wants to give them to us :-(
1008 * Sigh... start watchdog timer in the last case.
1009 */
1010
1011 if (sch->q.qlen) {
1012 sch->qstats.overlimits++;
1013 if (q->wd_expires)
1014 qdisc_watchdog_schedule(&q->watchdog,
1015 now + q->wd_expires);
1016 }
1017 return NULL;
1018 }
1019
1020 /* CBQ class maintanance routines */
1021
1022 static void cbq_adjust_levels(struct cbq_class *this)
1023 {
1024 if (this == NULL)
1025 return;
1026
1027 do {
1028 int level = 0;
1029 struct cbq_class *cl;
1030
1031 cl = this->children;
1032 if (cl) {
1033 do {
1034 if (cl->level > level)
1035 level = cl->level;
1036 } while ((cl = cl->sibling) != this->children);
1037 }
1038 this->level = level + 1;
1039 } while ((this = this->tparent) != NULL);
1040 }
1041
1042 static void cbq_normalize_quanta(struct cbq_sched_data *q, int prio)
1043 {
1044 struct cbq_class *cl;
1045 struct hlist_node *n;
1046 unsigned int h;
1047
1048 if (q->quanta[prio] == 0)
1049 return;
1050
1051 for (h = 0; h < q->clhash.hashsize; h++) {
1052 hlist_for_each_entry(cl, n, &q->clhash.hash[h], common.hnode) {
1053 /* BUGGGG... Beware! This expression suffer of
1054 * arithmetic overflows!
1055 */
1056 if (cl->priority == prio) {
1057 cl->quantum = (cl->weight*cl->allot*q->nclasses[prio])/
1058 q->quanta[prio];
1059 }
1060 if (cl->quantum <= 0 || cl->quantum>32*qdisc_dev(cl->qdisc)->mtu) {
1061 pr_warning("CBQ: class %08x has bad quantum==%ld, repaired.\n",
1062 cl->common.classid, cl->quantum);
1063 cl->quantum = qdisc_dev(cl->qdisc)->mtu/2 + 1;
1064 }
1065 }
1066 }
1067 }
1068
1069 static void cbq_sync_defmap(struct cbq_class *cl)
1070 {
1071 struct cbq_sched_data *q = qdisc_priv(cl->qdisc);
1072 struct cbq_class *split = cl->split;
1073 unsigned int h;
1074 int i;
1075
1076 if (split == NULL)
1077 return;
1078
1079 for (i = 0; i <= TC_PRIO_MAX; i++) {
1080 if (split->defaults[i] == cl && !(cl->defmap & (1<<i)))
1081 split->defaults[i] = NULL;
1082 }
1083
1084 for (i = 0; i <= TC_PRIO_MAX; i++) {
1085 int level = split->level;
1086
1087 if (split->defaults[i])
1088 continue;
1089
1090 for (h = 0; h < q->clhash.hashsize; h++) {
1091 struct hlist_node *n;
1092 struct cbq_class *c;
1093
1094 hlist_for_each_entry(c, n, &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
1106 static 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
1137 static 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
1165 static 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
1184 static 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
1209 static void
1210 cbq_reset(struct Qdisc *sch)
1211 {
1212 struct cbq_sched_data *q = qdisc_priv(sch);
1213 struct cbq_class *cl;
1214 struct hlist_node *n;
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, n, &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 opt.flags = 0;
1470 opt.allot = cl->allot;
1471 opt.priority = cl->priority + 1;
1472 opt.cpriority = cl->cpriority + 1;
1473 opt.weight = cl->weight;
1474 if (nla_put(skb, TCA_CBQ_WRROPT, sizeof(opt), &opt))
1475 goto nla_put_failure;
1476 return skb->len;
1477
1478 nla_put_failure:
1479 nlmsg_trim(skb, b);
1480 return -1;
1481 }
1482
1483 static int cbq_dump_ovl(struct sk_buff *skb, struct cbq_class *cl)
1484 {
1485 unsigned char *b = skb_tail_pointer(skb);
1486 struct tc_cbq_ovl opt;
1487
1488 opt.strategy = cl->ovl_strategy;
1489 opt.priority2 = cl->priority2 + 1;
1490 opt.pad = 0;
1491 opt.penalty = cl->penalty;
1492 if (nla_put(skb, TCA_CBQ_OVL_STRATEGY, sizeof(opt), &opt))
1493 goto nla_put_failure;
1494 return skb->len;
1495
1496 nla_put_failure:
1497 nlmsg_trim(skb, b);
1498 return -1;
1499 }
1500
1501 static int cbq_dump_fopt(struct sk_buff *skb, struct cbq_class *cl)
1502 {
1503 unsigned char *b = skb_tail_pointer(skb);
1504 struct tc_cbq_fopt opt;
1505
1506 if (cl->split || cl->defmap) {
1507 opt.split = cl->split ? cl->split->common.classid : 0;
1508 opt.defmap = cl->defmap;
1509 opt.defchange = ~0;
1510 if (nla_put(skb, TCA_CBQ_FOPT, sizeof(opt), &opt))
1511 goto nla_put_failure;
1512 }
1513 return skb->len;
1514
1515 nla_put_failure:
1516 nlmsg_trim(skb, b);
1517 return -1;
1518 }
1519
1520 #ifdef CONFIG_NET_CLS_ACT
1521 static int cbq_dump_police(struct sk_buff *skb, struct cbq_class *cl)
1522 {
1523 unsigned char *b = skb_tail_pointer(skb);
1524 struct tc_cbq_police opt;
1525
1526 if (cl->police) {
1527 opt.police = cl->police;
1528 opt.__res1 = 0;
1529 opt.__res2 = 0;
1530 if (nla_put(skb, TCA_CBQ_POLICE, sizeof(opt), &opt))
1531 goto nla_put_failure;
1532 }
1533 return skb->len;
1534
1535 nla_put_failure:
1536 nlmsg_trim(skb, b);
1537 return -1;
1538 }
1539 #endif
1540
1541 static int cbq_dump_attr(struct sk_buff *skb, struct cbq_class *cl)
1542 {
1543 if (cbq_dump_lss(skb, cl) < 0 ||
1544 cbq_dump_rate(skb, cl) < 0 ||
1545 cbq_dump_wrr(skb, cl) < 0 ||
1546 cbq_dump_ovl(skb, cl) < 0 ||
1547 #ifdef CONFIG_NET_CLS_ACT
1548 cbq_dump_police(skb, cl) < 0 ||
1549 #endif
1550 cbq_dump_fopt(skb, cl) < 0)
1551 return -1;
1552 return 0;
1553 }
1554
1555 static int cbq_dump(struct Qdisc *sch, struct sk_buff *skb)
1556 {
1557 struct cbq_sched_data *q = qdisc_priv(sch);
1558 struct nlattr *nest;
1559
1560 nest = nla_nest_start(skb, TCA_OPTIONS);
1561 if (nest == NULL)
1562 goto nla_put_failure;
1563 if (cbq_dump_attr(skb, &q->link) < 0)
1564 goto nla_put_failure;
1565 nla_nest_end(skb, nest);
1566 return skb->len;
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 nla_nest_end(skb, nest);
1602 return skb->len;
1603
1604 nla_put_failure:
1605 nla_nest_cancel(skb, nest);
1606 return -1;
1607 }
1608
1609 static int
1610 cbq_dump_class_stats(struct Qdisc *sch, unsigned long arg,
1611 struct gnet_dump *d)
1612 {
1613 struct cbq_sched_data *q = qdisc_priv(sch);
1614 struct cbq_class *cl = (struct cbq_class *)arg;
1615
1616 cl->qstats.qlen = cl->q->q.qlen;
1617 cl->xstats.avgidle = cl->avgidle;
1618 cl->xstats.undertime = 0;
1619
1620 if (cl->undertime != PSCHED_PASTPERFECT)
1621 cl->xstats.undertime = cl->undertime - q->now;
1622
1623 if (gnet_stats_copy_basic(d, &cl->bstats) < 0 ||
1624 gnet_stats_copy_rate_est(d, &cl->bstats, &cl->rate_est) < 0 ||
1625 gnet_stats_copy_queue(d, &cl->qstats) < 0)
1626 return -1;
1627
1628 return gnet_stats_copy_app(d, &cl->xstats, sizeof(cl->xstats));
1629 }
1630
1631 static int cbq_graft(struct Qdisc *sch, unsigned long arg, struct Qdisc *new,
1632 struct Qdisc **old)
1633 {
1634 struct cbq_class *cl = (struct cbq_class *)arg;
1635
1636 if (new == NULL) {
1637 new = qdisc_create_dflt(sch->dev_queue,
1638 &pfifo_qdisc_ops, cl->common.classid);
1639 if (new == NULL)
1640 return -ENOBUFS;
1641 } else {
1642 #ifdef CONFIG_NET_CLS_ACT
1643 if (cl->police == TC_POLICE_RECLASSIFY)
1644 new->reshape_fail = cbq_reshape_fail;
1645 #endif
1646 }
1647 sch_tree_lock(sch);
1648 *old = cl->q;
1649 cl->q = new;
1650 qdisc_tree_decrease_qlen(*old, (*old)->q.qlen);
1651 qdisc_reset(*old);
1652 sch_tree_unlock(sch);
1653
1654 return 0;
1655 }
1656
1657 static struct Qdisc *cbq_leaf(struct Qdisc *sch, unsigned long arg)
1658 {
1659 struct cbq_class *cl = (struct cbq_class *)arg;
1660
1661 return cl->q;
1662 }
1663
1664 static void cbq_qlen_notify(struct Qdisc *sch, unsigned long arg)
1665 {
1666 struct cbq_class *cl = (struct cbq_class *)arg;
1667
1668 if (cl->q->q.qlen == 0)
1669 cbq_deactivate_class(cl);
1670 }
1671
1672 static unsigned long cbq_get(struct Qdisc *sch, u32 classid)
1673 {
1674 struct cbq_sched_data *q = qdisc_priv(sch);
1675 struct cbq_class *cl = cbq_class_lookup(q, classid);
1676
1677 if (cl) {
1678 cl->refcnt++;
1679 return (unsigned long)cl;
1680 }
1681 return 0;
1682 }
1683
1684 static void cbq_destroy_class(struct Qdisc *sch, struct cbq_class *cl)
1685 {
1686 struct cbq_sched_data *q = qdisc_priv(sch);
1687
1688 WARN_ON(cl->filters);
1689
1690 tcf_destroy_chain(&cl->filter_list);
1691 qdisc_destroy(cl->q);
1692 qdisc_put_rtab(cl->R_tab);
1693 gen_kill_estimator(&cl->bstats, &cl->rate_est);
1694 if (cl != &q->link)
1695 kfree(cl);
1696 }
1697
1698 static void cbq_destroy(struct Qdisc *sch)
1699 {
1700 struct cbq_sched_data *q = qdisc_priv(sch);
1701 struct hlist_node *n, *next;
1702 struct cbq_class *cl;
1703 unsigned int h;
1704
1705 #ifdef CONFIG_NET_CLS_ACT
1706 q->rx_class = NULL;
1707 #endif
1708 /*
1709 * Filters must be destroyed first because we don't destroy the
1710 * classes from root to leafs which means that filters can still
1711 * be bound to classes which have been destroyed already. --TGR '04
1712 */
1713 for (h = 0; h < q->clhash.hashsize; h++) {
1714 hlist_for_each_entry(cl, n, &q->clhash.hash[h], common.hnode)
1715 tcf_destroy_chain(&cl->filter_list);
1716 }
1717 for (h = 0; h < q->clhash.hashsize; h++) {
1718 hlist_for_each_entry_safe(cl, n, next, &q->clhash.hash[h],
1719 common.hnode)
1720 cbq_destroy_class(sch, cl);
1721 }
1722 qdisc_class_hash_destroy(&q->clhash);
1723 }
1724
1725 static void cbq_put(struct Qdisc *sch, unsigned long arg)
1726 {
1727 struct cbq_class *cl = (struct cbq_class *)arg;
1728
1729 if (--cl->refcnt == 0) {
1730 #ifdef CONFIG_NET_CLS_ACT
1731 spinlock_t *root_lock = qdisc_root_sleeping_lock(sch);
1732 struct cbq_sched_data *q = qdisc_priv(sch);
1733
1734 spin_lock_bh(root_lock);
1735 if (q->rx_class == cl)
1736 q->rx_class = NULL;
1737 spin_unlock_bh(root_lock);
1738 #endif
1739
1740 cbq_destroy_class(sch, cl);
1741 }
1742 }
1743
1744 static int
1745 cbq_change_class(struct Qdisc *sch, u32 classid, u32 parentid, struct nlattr **tca,
1746 unsigned long *arg)
1747 {
1748 int err;
1749 struct cbq_sched_data *q = qdisc_priv(sch);
1750 struct cbq_class *cl = (struct cbq_class *)*arg;
1751 struct nlattr *opt = tca[TCA_OPTIONS];
1752 struct nlattr *tb[TCA_CBQ_MAX + 1];
1753 struct cbq_class *parent;
1754 struct qdisc_rate_table *rtab = NULL;
1755
1756 if (opt == NULL)
1757 return -EINVAL;
1758
1759 err = nla_parse_nested(tb, TCA_CBQ_MAX, opt, cbq_policy);
1760 if (err < 0)
1761 return err;
1762
1763 if (cl) {
1764 /* Check parent */
1765 if (parentid) {
1766 if (cl->tparent &&
1767 cl->tparent->common.classid != parentid)
1768 return -EINVAL;
1769 if (!cl->tparent && parentid != TC_H_ROOT)
1770 return -EINVAL;
1771 }
1772
1773 if (tb[TCA_CBQ_RATE]) {
1774 rtab = qdisc_get_rtab(nla_data(tb[TCA_CBQ_RATE]),
1775 tb[TCA_CBQ_RTAB]);
1776 if (rtab == NULL)
1777 return -EINVAL;
1778 }
1779
1780 if (tca[TCA_RATE]) {
1781 err = gen_replace_estimator(&cl->bstats, &cl->rate_est,
1782 qdisc_root_sleeping_lock(sch),
1783 tca[TCA_RATE]);
1784 if (err) {
1785 if (rtab)
1786 qdisc_put_rtab(rtab);
1787 return err;
1788 }
1789 }
1790
1791 /* Change class parameters */
1792 sch_tree_lock(sch);
1793
1794 if (cl->next_alive != NULL)
1795 cbq_deactivate_class(cl);
1796
1797 if (rtab) {
1798 qdisc_put_rtab(cl->R_tab);
1799 cl->R_tab = rtab;
1800 }
1801
1802 if (tb[TCA_CBQ_LSSOPT])
1803 cbq_set_lss(cl, nla_data(tb[TCA_CBQ_LSSOPT]));
1804
1805 if (tb[TCA_CBQ_WRROPT]) {
1806 cbq_rmprio(q, cl);
1807 cbq_set_wrr(cl, nla_data(tb[TCA_CBQ_WRROPT]));
1808 }
1809
1810 if (tb[TCA_CBQ_OVL_STRATEGY])
1811 cbq_set_overlimit(cl, nla_data(tb[TCA_CBQ_OVL_STRATEGY]));
1812
1813 #ifdef CONFIG_NET_CLS_ACT
1814 if (tb[TCA_CBQ_POLICE])
1815 cbq_set_police(cl, nla_data(tb[TCA_CBQ_POLICE]));
1816 #endif
1817
1818 if (tb[TCA_CBQ_FOPT])
1819 cbq_set_fopt(cl, nla_data(tb[TCA_CBQ_FOPT]));
1820
1821 if (cl->q->q.qlen)
1822 cbq_activate_class(cl);
1823
1824 sch_tree_unlock(sch);
1825
1826 return 0;
1827 }
1828
1829 if (parentid == TC_H_ROOT)
1830 return -EINVAL;
1831
1832 if (tb[TCA_CBQ_WRROPT] == NULL || tb[TCA_CBQ_RATE] == NULL ||
1833 tb[TCA_CBQ_LSSOPT] == NULL)
1834 return -EINVAL;
1835
1836 rtab = qdisc_get_rtab(nla_data(tb[TCA_CBQ_RATE]), tb[TCA_CBQ_RTAB]);
1837 if (rtab == NULL)
1838 return -EINVAL;
1839
1840 if (classid) {
1841 err = -EINVAL;
1842 if (TC_H_MAJ(classid ^ sch->handle) ||
1843 cbq_class_lookup(q, classid))
1844 goto failure;
1845 } else {
1846 int i;
1847 classid = TC_H_MAKE(sch->handle, 0x8000);
1848
1849 for (i = 0; i < 0x8000; i++) {
1850 if (++q->hgenerator >= 0x8000)
1851 q->hgenerator = 1;
1852 if (cbq_class_lookup(q, classid|q->hgenerator) == NULL)
1853 break;
1854 }
1855 err = -ENOSR;
1856 if (i >= 0x8000)
1857 goto failure;
1858 classid = classid|q->hgenerator;
1859 }
1860
1861 parent = &q->link;
1862 if (parentid) {
1863 parent = cbq_class_lookup(q, parentid);
1864 err = -EINVAL;
1865 if (parent == NULL)
1866 goto failure;
1867 }
1868
1869 err = -ENOBUFS;
1870 cl = kzalloc(sizeof(*cl), GFP_KERNEL);
1871 if (cl == NULL)
1872 goto failure;
1873
1874 if (tca[TCA_RATE]) {
1875 err = gen_new_estimator(&cl->bstats, &cl->rate_est,
1876 qdisc_root_sleeping_lock(sch),
1877 tca[TCA_RATE]);
1878 if (err) {
1879 kfree(cl);
1880 goto failure;
1881 }
1882 }
1883
1884 cl->R_tab = rtab;
1885 rtab = NULL;
1886 cl->refcnt = 1;
1887 cl->q = qdisc_create_dflt(sch->dev_queue, &pfifo_qdisc_ops, classid);
1888 if (!cl->q)
1889 cl->q = &noop_qdisc;
1890 cl->common.classid = classid;
1891 cl->tparent = parent;
1892 cl->qdisc = sch;
1893 cl->allot = parent->allot;
1894 cl->quantum = cl->allot;
1895 cl->weight = cl->R_tab->rate.rate;
1896
1897 sch_tree_lock(sch);
1898 cbq_link_class(cl);
1899 cl->borrow = cl->tparent;
1900 if (cl->tparent != &q->link)
1901 cl->share = cl->tparent;
1902 cbq_adjust_levels(parent);
1903 cl->minidle = -0x7FFFFFFF;
1904 cbq_set_lss(cl, nla_data(tb[TCA_CBQ_LSSOPT]));
1905 cbq_set_wrr(cl, nla_data(tb[TCA_CBQ_WRROPT]));
1906 if (cl->ewma_log == 0)
1907 cl->ewma_log = q->link.ewma_log;
1908 if (cl->maxidle == 0)
1909 cl->maxidle = q->link.maxidle;
1910 if (cl->avpkt == 0)
1911 cl->avpkt = q->link.avpkt;
1912 cl->overlimit = cbq_ovl_classic;
1913 if (tb[TCA_CBQ_OVL_STRATEGY])
1914 cbq_set_overlimit(cl, nla_data(tb[TCA_CBQ_OVL_STRATEGY]));
1915 #ifdef CONFIG_NET_CLS_ACT
1916 if (tb[TCA_CBQ_POLICE])
1917 cbq_set_police(cl, nla_data(tb[TCA_CBQ_POLICE]));
1918 #endif
1919 if (tb[TCA_CBQ_FOPT])
1920 cbq_set_fopt(cl, nla_data(tb[TCA_CBQ_FOPT]));
1921 sch_tree_unlock(sch);
1922
1923 qdisc_class_hash_grow(sch, &q->clhash);
1924
1925 *arg = (unsigned long)cl;
1926 return 0;
1927
1928 failure:
1929 qdisc_put_rtab(rtab);
1930 return err;
1931 }
1932
1933 static int cbq_delete(struct Qdisc *sch, unsigned long arg)
1934 {
1935 struct cbq_sched_data *q = qdisc_priv(sch);
1936 struct cbq_class *cl = (struct cbq_class *)arg;
1937 unsigned int qlen;
1938
1939 if (cl->filters || cl->children || cl == &q->link)
1940 return -EBUSY;
1941
1942 sch_tree_lock(sch);
1943
1944 qlen = cl->q->q.qlen;
1945 qdisc_reset(cl->q);
1946 qdisc_tree_decrease_qlen(cl->q, qlen);
1947
1948 if (cl->next_alive)
1949 cbq_deactivate_class(cl);
1950
1951 if (q->tx_borrowed == cl)
1952 q->tx_borrowed = q->tx_class;
1953 if (q->tx_class == cl) {
1954 q->tx_class = NULL;
1955 q->tx_borrowed = NULL;
1956 }
1957 #ifdef CONFIG_NET_CLS_ACT
1958 if (q->rx_class == cl)
1959 q->rx_class = NULL;
1960 #endif
1961
1962 cbq_unlink_class(cl);
1963 cbq_adjust_levels(cl->tparent);
1964 cl->defmap = 0;
1965 cbq_sync_defmap(cl);
1966
1967 cbq_rmprio(q, cl);
1968 sch_tree_unlock(sch);
1969
1970 BUG_ON(--cl->refcnt == 0);
1971 /*
1972 * This shouldn't happen: we "hold" one cops->get() when called
1973 * from tc_ctl_tclass; the destroy method is done from cops->put().
1974 */
1975
1976 return 0;
1977 }
1978
1979 static struct tcf_proto **cbq_find_tcf(struct Qdisc *sch, unsigned long arg)
1980 {
1981 struct cbq_sched_data *q = qdisc_priv(sch);
1982 struct cbq_class *cl = (struct cbq_class *)arg;
1983
1984 if (cl == NULL)
1985 cl = &q->link;
1986
1987 return &cl->filter_list;
1988 }
1989
1990 static unsigned long cbq_bind_filter(struct Qdisc *sch, unsigned long parent,
1991 u32 classid)
1992 {
1993 struct cbq_sched_data *q = qdisc_priv(sch);
1994 struct cbq_class *p = (struct cbq_class *)parent;
1995 struct cbq_class *cl = cbq_class_lookup(q, classid);
1996
1997 if (cl) {
1998 if (p && p->level <= cl->level)
1999 return 0;
2000 cl->filters++;
2001 return (unsigned long)cl;
2002 }
2003 return 0;
2004 }
2005
2006 static void cbq_unbind_filter(struct Qdisc *sch, unsigned long arg)
2007 {
2008 struct cbq_class *cl = (struct cbq_class *)arg;
2009
2010 cl->filters--;
2011 }
2012
2013 static void cbq_walk(struct Qdisc *sch, struct qdisc_walker *arg)
2014 {
2015 struct cbq_sched_data *q = qdisc_priv(sch);
2016 struct cbq_class *cl;
2017 struct hlist_node *n;
2018 unsigned int h;
2019
2020 if (arg->stop)
2021 return;
2022
2023 for (h = 0; h < q->clhash.hashsize; h++) {
2024 hlist_for_each_entry(cl, n, &q->clhash.hash[h], common.hnode) {
2025 if (arg->count < arg->skip) {
2026 arg->count++;
2027 continue;
2028 }
2029 if (arg->fn(sch, (unsigned long)cl, arg) < 0) {
2030 arg->stop = 1;
2031 return;
2032 }
2033 arg->count++;
2034 }
2035 }
2036 }
2037
2038 static const struct Qdisc_class_ops cbq_class_ops = {
2039 .graft = cbq_graft,
2040 .leaf = cbq_leaf,
2041 .qlen_notify = cbq_qlen_notify,
2042 .get = cbq_get,
2043 .put = cbq_put,
2044 .change = cbq_change_class,
2045 .delete = cbq_delete,
2046 .walk = cbq_walk,
2047 .tcf_chain = cbq_find_tcf,
2048 .bind_tcf = cbq_bind_filter,
2049 .unbind_tcf = cbq_unbind_filter,
2050 .dump = cbq_dump_class,
2051 .dump_stats = cbq_dump_class_stats,
2052 };
2053
2054 static struct Qdisc_ops cbq_qdisc_ops __read_mostly = {
2055 .next = NULL,
2056 .cl_ops = &cbq_class_ops,
2057 .id = "cbq",
2058 .priv_size = sizeof(struct cbq_sched_data),
2059 .enqueue = cbq_enqueue,
2060 .dequeue = cbq_dequeue,
2061 .peek = qdisc_peek_dequeued,
2062 .drop = cbq_drop,
2063 .init = cbq_init,
2064 .reset = cbq_reset,
2065 .destroy = cbq_destroy,
2066 .change = NULL,
2067 .dump = cbq_dump,
2068 .dump_stats = cbq_dump_stats,
2069 .owner = THIS_MODULE,
2070 };
2071
2072 static int __init cbq_module_init(void)
2073 {
2074 return register_qdisc(&cbq_qdisc_ops);
2075 }
2076 static void __exit cbq_module_exit(void)
2077 {
2078 unregister_qdisc(&cbq_qdisc_ops);
2079 }
2080 module_init(cbq_module_init)
2081 module_exit(cbq_module_exit)
2082 MODULE_LICENSE("GPL");
Linus' kernel tree