?  search:
summary | log | graphiclog1 | graphiclog2 | commit | commitdiff | tree | refs | edit | fork
blame | history | raw | HEAD
uas: Remove protype hardware usb interface info
[linux-2.6/btrfs-unstable.git] / net / sched / sch_cbq.c
blob762a04bb8f6dcbe4627b579ff4081a4cf92adb11
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 unsigned int pmask;
163
164 struct hrtimer delay_timer;
165 struct qdisc_watchdog watchdog; /* Watchdog timer,
166 started when CBQ has
167 backlog, but cannot
168 transmit just now */
169 psched_tdiff_t wd_expires;
170 int toplevel;
171 u32 hgenerator;
172 };
173
174
175 #define L2T(cl, len) qdisc_l2t((cl)->R_tab, len)
176
177 static inline struct cbq_class *
178 cbq_class_lookup(struct cbq_sched_data *q, u32 classid)
179 {
180 struct Qdisc_class_common *clc;
181
182 clc = qdisc_class_find(&q->clhash, classid);
183 if (clc == NULL)
184 return NULL;
185 return container_of(clc, struct cbq_class, common);
186 }
187
188 #ifdef CONFIG_NET_CLS_ACT
189
190 static struct cbq_class *
191 cbq_reclassify(struct sk_buff *skb, struct cbq_class *this)
192 {
193 struct cbq_class *cl;
194
195 for (cl = this->tparent; cl; cl = cl->tparent) {
196 struct cbq_class *new = cl->defaults[TC_PRIO_BESTEFFORT];
197
198 if (new != NULL && new != this)
199 return new;
200 }
201 return NULL;
202 }
203
204 #endif
205
206 /* Classify packet. The procedure is pretty complicated, but
207 * it allows us to combine link sharing and priority scheduling
208 * transparently.
209 *
210 * Namely, you can put link sharing rules (f.e. route based) at root of CBQ,
211 * so that it resolves to split nodes. Then packets are classified
212 * by logical priority, or a more specific classifier may be attached
213 * to the split node.
214 */
215
216 static struct cbq_class *
217 cbq_classify(struct sk_buff *skb, struct Qdisc *sch, int *qerr)
218 {
219 struct cbq_sched_data *q = qdisc_priv(sch);
220 struct cbq_class *head = &q->link;
221 struct cbq_class **defmap;
222 struct cbq_class *cl = NULL;
223 u32 prio = skb->priority;
224 struct tcf_result res;
225
226 /*
227 * Step 1. If skb->priority points to one of our classes, use it.
228 */
229 if (TC_H_MAJ(prio ^ sch->handle) == 0 &&
230 (cl = cbq_class_lookup(q, prio)) != NULL)
231 return cl;
232
233 *qerr = NET_XMIT_SUCCESS | __NET_XMIT_BYPASS;
234 for (;;) {
235 int result = 0;
236 defmap = head->defaults;
237
238 /*
239 * Step 2+n. Apply classifier.
240 */
241 if (!head->filter_list ||
242 (result = tc_classify_compat(skb, head->filter_list, &res)) < 0)
243 goto fallback;
244
245 cl = (void *)res.class;
246 if (!cl) {
247 if (TC_H_MAJ(res.classid))
248 cl = cbq_class_lookup(q, res.classid);
249 else if ((cl = defmap[res.classid & TC_PRIO_MAX]) == NULL)
250 cl = defmap[TC_PRIO_BESTEFFORT];
251
252 if (cl == NULL)
253 goto fallback;
254 }
255 if (cl->level >= head->level)
256 goto fallback;
257 #ifdef CONFIG_NET_CLS_ACT
258 switch (result) {
259 case TC_ACT_QUEUED:
260 case TC_ACT_STOLEN:
261 *qerr = NET_XMIT_SUCCESS | __NET_XMIT_STOLEN;
262 case TC_ACT_SHOT:
263 return NULL;
264 case TC_ACT_RECLASSIFY:
265 return cbq_reclassify(skb, cl);
266 }
267 #endif
268 if (cl->level == 0)
269 return cl;
270
271 /*
272 * Step 3+n. If classifier selected a link sharing class,
273 * apply agency specific classifier.
274 * Repeat this procdure until we hit a leaf node.
275 */
276 head = cl;
277 }
278
279 fallback:
280 cl = head;
281
282 /*
283 * Step 4. No success...
284 */
285 if (TC_H_MAJ(prio) == 0 &&
286 !(cl = head->defaults[prio & TC_PRIO_MAX]) &&
287 !(cl = head->defaults[TC_PRIO_BESTEFFORT]))
288 return head;
289
290 return cl;
291 }
292
293 /*
294 * A packet has just been enqueued on the empty class.
295 * cbq_activate_class adds it to the tail of active class list
296 * of its priority band.
297 */
298
299 static inline void cbq_activate_class(struct cbq_class *cl)
300 {
301 struct cbq_sched_data *q = qdisc_priv(cl->qdisc);
302 int prio = cl->cpriority;
303 struct cbq_class *cl_tail;
304
305 cl_tail = q->active[prio];
306 q->active[prio] = cl;
307
308 if (cl_tail != NULL) {
309 cl->next_alive = cl_tail->next_alive;
310 cl_tail->next_alive = cl;
311 } else {
312 cl->next_alive = cl;
313 q->activemask |= (1<<prio);
314 }
315 }
316
317 /*
318 * Unlink class from active chain.
319 * Note that this same procedure is done directly in cbq_dequeue*
320 * during round-robin procedure.
321 */
322
323 static void cbq_deactivate_class(struct cbq_class *this)
324 {
325 struct cbq_sched_data *q = qdisc_priv(this->qdisc);
326 int prio = this->cpriority;
327 struct cbq_class *cl;
328 struct cbq_class *cl_prev = q->active[prio];
329
330 do {
331 cl = cl_prev->next_alive;
332 if (cl == this) {
333 cl_prev->next_alive = cl->next_alive;
334 cl->next_alive = NULL;
335
336 if (cl == q->active[prio]) {
337 q->active[prio] = cl_prev;
338 if (cl == q->active[prio]) {
339 q->active[prio] = NULL;
340 q->activemask &= ~(1<<prio);
341 return;
342 }
343 }
344 return;
345 }
346 } while ((cl_prev = cl) != q->active[prio]);
347 }
348
349 static void
350 cbq_mark_toplevel(struct cbq_sched_data *q, struct cbq_class *cl)
351 {
352 int toplevel = q->toplevel;
353
354 if (toplevel > cl->level && !(qdisc_is_throttled(cl->q))) {
355 psched_time_t now = psched_get_time();
356
357 do {
358 if (cl->undertime < now) {
359 q->toplevel = cl->level;
360 return;
361 }
362 } while ((cl = cl->borrow) != NULL && toplevel > cl->level);
363 }
364 }
365
366 static int
367 cbq_enqueue(struct sk_buff *skb, struct Qdisc *sch)
368 {
369 struct cbq_sched_data *q = qdisc_priv(sch);
370 int uninitialized_var(ret);
371 struct cbq_class *cl = cbq_classify(skb, sch, &ret);
372
373 #ifdef CONFIG_NET_CLS_ACT
374 q->rx_class = cl;
375 #endif
376 if (cl == NULL) {
377 if (ret & __NET_XMIT_BYPASS)
378 sch->qstats.drops++;
379 kfree_skb(skb);
380 return ret;
381 }
382
383 #ifdef CONFIG_NET_CLS_ACT
384 cl->q->__parent = sch;
385 #endif
386 ret = qdisc_enqueue(skb, cl->q);
387 if (ret == NET_XMIT_SUCCESS) {
388 sch->q.qlen++;
389 cbq_mark_toplevel(q, cl);
390 if (!cl->next_alive)
391 cbq_activate_class(cl);
392 return ret;
393 }
394
395 if (net_xmit_drop_count(ret)) {
396 sch->qstats.drops++;
397 cbq_mark_toplevel(q, cl);
398 cl->qstats.drops++;
399 }
400 return ret;
401 }
402
403 /* Overlimit actions */
404
405 /* TC_CBQ_OVL_CLASSIC: (default) penalize leaf class by adding offtime */
406
407 static void cbq_ovl_classic(struct cbq_class *cl)
408 {
409 struct cbq_sched_data *q = qdisc_priv(cl->qdisc);
410 psched_tdiff_t delay = cl->undertime - q->now;
411
412 if (!cl->delayed) {
413 delay += cl->offtime;
414
415 /*
416 * Class goes to sleep, so that it will have no
417 * chance to work avgidle. Let's forgive it 8)
418 *
419 * BTW cbq-2.0 has a crap in this
420 * place, apparently they forgot to shift it by cl->ewma_log.
421 */
422 if (cl->avgidle < 0)
423 delay -= (-cl->avgidle) - ((-cl->avgidle) >> cl->ewma_log);
424 if (cl->avgidle < cl->minidle)
425 cl->avgidle = cl->minidle;
426 if (delay <= 0)
427 delay = 1;
428 cl->undertime = q->now + delay;
429
430 cl->xstats.overactions++;
431 cl->delayed = 1;
432 }
433 if (q->wd_expires == 0 || q->wd_expires > delay)
434 q->wd_expires = delay;
435
436 /* Dirty work! We must schedule wakeups based on
437 * real available rate, rather than leaf rate,
438 * which may be tiny (even zero).
439 */
440 if (q->toplevel == TC_CBQ_MAXLEVEL) {
441 struct cbq_class *b;
442 psched_tdiff_t base_delay = q->wd_expires;
443
444 for (b = cl->borrow; b; b = b->borrow) {
445 delay = b->undertime - q->now;
446 if (delay < base_delay) {
447 if (delay <= 0)
448 delay = 1;
449 base_delay = delay;
450 }
451 }
452
453 q->wd_expires = base_delay;
454 }
455 }
456
457 /* TC_CBQ_OVL_RCLASSIC: penalize by offtime classes in hierarchy, when
458 * they go overlimit
459 */
460
461 static void cbq_ovl_rclassic(struct cbq_class *cl)
462 {
463 struct cbq_sched_data *q = qdisc_priv(cl->qdisc);
464 struct cbq_class *this = cl;
465
466 do {
467 if (cl->level > q->toplevel) {
468 cl = NULL;
469 break;
470 }
471 } while ((cl = cl->borrow) != NULL);
472
473 if (cl == NULL)
474 cl = this;
475 cbq_ovl_classic(cl);
476 }
477
478 /* TC_CBQ_OVL_DELAY: delay until it will go to underlimit */
479
480 static void cbq_ovl_delay(struct cbq_class *cl)
481 {
482 struct cbq_sched_data *q = qdisc_priv(cl->qdisc);
483 psched_tdiff_t delay = cl->undertime - q->now;
484
485 if (test_bit(__QDISC_STATE_DEACTIVATED,
486 &qdisc_root_sleeping(cl->qdisc)->state))
487 return;
488
489 if (!cl->delayed) {
490 psched_time_t sched = q->now;
491 ktime_t expires;
492
493 delay += cl->offtime;
494 if (cl->avgidle < 0)
495 delay -= (-cl->avgidle) - ((-cl->avgidle) >> cl->ewma_log);
496 if (cl->avgidle < cl->minidle)
497 cl->avgidle = cl->minidle;
498 cl->undertime = q->now + delay;
499
500 if (delay > 0) {
501 sched += delay + cl->penalty;
502 cl->penalized = sched;
503 cl->cpriority = TC_CBQ_MAXPRIO;
504 q->pmask |= (1<<TC_CBQ_MAXPRIO);
505
506 expires = ns_to_ktime(PSCHED_TICKS2NS(sched));
507 if (hrtimer_try_to_cancel(&q->delay_timer) &&
508 ktime_to_ns(ktime_sub(
509 hrtimer_get_expires(&q->delay_timer),
510 expires)) > 0)
511 hrtimer_set_expires(&q->delay_timer, expires);
512 hrtimer_restart(&q->delay_timer);
513 cl->delayed = 1;
514 cl->xstats.overactions++;
515 return;
516 }
517 delay = 1;
518 }
519 if (q->wd_expires == 0 || q->wd_expires > delay)
520 q->wd_expires = delay;
521 }
522
523 /* TC_CBQ_OVL_LOWPRIO: penalize class by lowering its priority band */
524
525 static void cbq_ovl_lowprio(struct cbq_class *cl)
526 {
527 struct cbq_sched_data *q = qdisc_priv(cl->qdisc);
528
529 cl->penalized = q->now + cl->penalty;
530
531 if (cl->cpriority != cl->priority2) {
532 cl->cpriority = cl->priority2;
533 q->pmask |= (1<<cl->cpriority);
534 cl->xstats.overactions++;
535 }
536 cbq_ovl_classic(cl);
537 }
538
539 /* TC_CBQ_OVL_DROP: penalize class by dropping */
540
541 static void cbq_ovl_drop(struct cbq_class *cl)
542 {
543 if (cl->q->ops->drop)
544 if (cl->q->ops->drop(cl->q))
545 cl->qdisc->q.qlen--;
546 cl->xstats.overactions++;
547 cbq_ovl_classic(cl);
548 }
549
550 static psched_tdiff_t cbq_undelay_prio(struct cbq_sched_data *q, int prio,
551 psched_time_t now)
552 {
553 struct cbq_class *cl;
554 struct cbq_class *cl_prev = q->active[prio];
555 psched_time_t sched = now;
556
557 if (cl_prev == NULL)
558 return 0;
559
560 do {
561 cl = cl_prev->next_alive;
562 if (now - cl->penalized > 0) {
563 cl_prev->next_alive = cl->next_alive;
564 cl->next_alive = NULL;
565 cl->cpriority = cl->priority;
566 cl->delayed = 0;
567 cbq_activate_class(cl);
568
569 if (cl == q->active[prio]) {
570 q->active[prio] = cl_prev;
571 if (cl == q->active[prio]) {
572 q->active[prio] = NULL;
573 return 0;
574 }
575 }
576
577 cl = cl_prev->next_alive;
578 } else if (sched - cl->penalized > 0)
579 sched = cl->penalized;
580 } while ((cl_prev = cl) != q->active[prio]);
581
582 return sched - now;
583 }
584
585 static enum hrtimer_restart cbq_undelay(struct hrtimer *timer)
586 {
587 struct cbq_sched_data *q = container_of(timer, struct cbq_sched_data,
588 delay_timer);
589 struct Qdisc *sch = q->watchdog.qdisc;
590 psched_time_t now;
591 psched_tdiff_t delay = 0;
592 unsigned int pmask;
593
594 now = psched_get_time();
595
596 pmask = q->pmask;
597 q->pmask = 0;
598
599 while (pmask) {
600 int prio = ffz(~pmask);
601 psched_tdiff_t tmp;
602
603 pmask &= ~(1<<prio);
604
605 tmp = cbq_undelay_prio(q, prio, now);
606 if (tmp > 0) {
607 q->pmask |= 1<<prio;
608 if (tmp < delay || delay == 0)
609 delay = tmp;
610 }
611 }
612
613 if (delay) {
614 ktime_t time;
615
616 time = ktime_set(0, 0);
617 time = ktime_add_ns(time, PSCHED_TICKS2NS(now + delay));
618 hrtimer_start(&q->delay_timer, time, HRTIMER_MODE_ABS);
619 }
620
621 qdisc_unthrottled(sch);
622 __netif_schedule(qdisc_root(sch));
623 return HRTIMER_NORESTART;
624 }
625
626 #ifdef CONFIG_NET_CLS_ACT
627 static int cbq_reshape_fail(struct sk_buff *skb, struct Qdisc *child)
628 {
629 struct Qdisc *sch = child->__parent;
630 struct cbq_sched_data *q = qdisc_priv(sch);
631 struct cbq_class *cl = q->rx_class;
632
633 q->rx_class = NULL;
634
635 if (cl && (cl = cbq_reclassify(skb, cl)) != NULL) {
636 int ret;
637
638 cbq_mark_toplevel(q, cl);
639
640 q->rx_class = cl;
641 cl->q->__parent = sch;
642
643 ret = qdisc_enqueue(skb, cl->q);
644 if (ret == NET_XMIT_SUCCESS) {
645 sch->q.qlen++;
646 if (!cl->next_alive)
647 cbq_activate_class(cl);
648 return 0;
649 }
650 if (net_xmit_drop_count(ret))
651 sch->qstats.drops++;
652 return 0;
653 }
654
655 sch->qstats.drops++;
656 return -1;
657 }
658 #endif
659
660 /*
661 * It is mission critical procedure.
662 *
663 * We "regenerate" toplevel cutoff, if transmitting class
664 * has backlog and it is not regulated. It is not part of
665 * original CBQ description, but looks more reasonable.
666 * Probably, it is wrong. This question needs further investigation.
667 */
668
669 static inline void
670 cbq_update_toplevel(struct cbq_sched_data *q, struct cbq_class *cl,
671 struct cbq_class *borrowed)
672 {
673 if (cl && q->toplevel >= borrowed->level) {
674 if (cl->q->q.qlen > 1) {
675 do {
676 if (borrowed->undertime == PSCHED_PASTPERFECT) {
677 q->toplevel = borrowed->level;
678 return;
679 }
680 } while ((borrowed = borrowed->borrow) != NULL);
681 }
682 #if 0
683 /* It is not necessary now. Uncommenting it
684 will save CPU cycles, but decrease fairness.
685 */
686 q->toplevel = TC_CBQ_MAXLEVEL;
687 #endif
688 }
689 }
690
691 static void
692 cbq_update(struct cbq_sched_data *q)
693 {
694 struct cbq_class *this = q->tx_class;
695 struct cbq_class *cl = this;
696 int len = q->tx_len;
697 psched_time_t now;
698
699 q->tx_class = NULL;
700 /* Time integrator. We calculate EOS time
701 * by adding expected packet transmission time.
702 */
703 now = q->now + L2T(&q->link, len);
704
705 for ( ; cl; cl = cl->share) {
706 long avgidle = cl->avgidle;
707 long idle;
708
709 cl->bstats.packets++;
710 cl->bstats.bytes += len;
711
712 /*
713 * (now - last) is total time between packet right edges.
714 * (last_pktlen/rate) is "virtual" busy time, so that
715 *
716 * idle = (now - last) - last_pktlen/rate
717 */
718
719 idle = now - cl->last;
720 if ((unsigned long)idle > 128*1024*1024) {
721 avgidle = cl->maxidle;
722 } else {
723 idle -= L2T(cl, len);
724
725 /* true_avgidle := (1-W)*true_avgidle + W*idle,
726 * where W=2^{-ewma_log}. But cl->avgidle is scaled:
727 * cl->avgidle == true_avgidle/W,
728 * hence:
729 */
730 avgidle += idle - (avgidle>>cl->ewma_log);
731 }
732
733 if (avgidle <= 0) {
734 /* Overlimit or at-limit */
735
736 if (avgidle < cl->minidle)
737 avgidle = cl->minidle;
738
739 cl->avgidle = avgidle;
740
741 /* Calculate expected time, when this class
742 * will be allowed to send.
743 * It will occur, when:
744 * (1-W)*true_avgidle + W*delay = 0, i.e.
745 * idle = (1/W - 1)*(-true_avgidle)
746 * or
747 * idle = (1 - W)*(-cl->avgidle);
748 */
749 idle = (-avgidle) - ((-avgidle) >> cl->ewma_log);
750
751 /*
752 * That is not all.
753 * To maintain the rate allocated to the class,
754 * we add to undertime virtual clock,
755 * necessary to complete transmitted packet.
756 * (len/phys_bandwidth has been already passed
757 * to the moment of cbq_update)
758 */
759
760 idle -= L2T(&q->link, len);
761 idle += L2T(cl, len);
762
763 cl->undertime = now + idle;
764 } else {
765 /* Underlimit */
766
767 cl->undertime = PSCHED_PASTPERFECT;
768 if (avgidle > cl->maxidle)
769 cl->avgidle = cl->maxidle;
770 else
771 cl->avgidle = avgidle;
772 }
773 if ((s64)(now - cl->last) > 0)
774 cl->last = 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
947 now = psched_get_time();
948
949 if (q->tx_class)
950 cbq_update(q);
951
952 q->now = now;
953
954 for (;;) {
955 q->wd_expires = 0;
956
957 skb = cbq_dequeue_1(sch);
958 if (skb) {
959 qdisc_bstats_update(sch, skb);
960 sch->q.qlen--;
961 qdisc_unthrottled(sch);
962 return skb;
963 }
964
965 /* All the classes are overlimit.
966 *
967 * It is possible, if:
968 *
969 * 1. Scheduler is empty.
970 * 2. Toplevel cutoff inhibited borrowing.
971 * 3. Root class is overlimit.
972 *
973 * Reset 2d and 3d conditions and retry.
974 *
975 * Note, that NS and cbq-2.0 are buggy, peeking
976 * an arbitrary class is appropriate for ancestor-only
977 * sharing, but not for toplevel algorithm.
978 *
979 * Our version is better, but slower, because it requires
980 * two passes, but it is unavoidable with top-level sharing.
981 */
982
983 if (q->toplevel == TC_CBQ_MAXLEVEL &&
984 q->link.undertime == PSCHED_PASTPERFECT)
985 break;
986
987 q->toplevel = TC_CBQ_MAXLEVEL;
988 q->link.undertime = PSCHED_PASTPERFECT;
989 }
990
991 /* No packets in scheduler or nobody wants to give them to us :-(
992 * Sigh... start watchdog timer in the last case.
993 */
994
995 if (sch->q.qlen) {
996 sch->qstats.overlimits++;
997 if (q->wd_expires)
998 qdisc_watchdog_schedule(&q->watchdog,
999 now + q->wd_expires);
1000 }
1001 return NULL;
1002 }
1003
1004 /* CBQ class maintanance routines */
1005
1006 static void cbq_adjust_levels(struct cbq_class *this)
1007 {
1008 if (this == NULL)
1009 return;
1010
1011 do {
1012 int level = 0;
1013 struct cbq_class *cl;
1014
1015 cl = this->children;
1016 if (cl) {
1017 do {
1018 if (cl->level > level)
1019 level = cl->level;
1020 } while ((cl = cl->sibling) != this->children);
1021 }
1022 this->level = level + 1;
1023 } while ((this = this->tparent) != NULL);
1024 }
1025
1026 static void cbq_normalize_quanta(struct cbq_sched_data *q, int prio)
1027 {
1028 struct cbq_class *cl;
1029 unsigned int h;
1030
1031 if (q->quanta[prio] == 0)
1032 return;
1033
1034 for (h = 0; h < q->clhash.hashsize; h++) {
1035 hlist_for_each_entry(cl, &q->clhash.hash[h], common.hnode) {
1036 /* BUGGGG... Beware! This expression suffer of
1037 * arithmetic overflows!
1038 */
1039 if (cl->priority == prio) {
1040 cl->quantum = (cl->weight*cl->allot*q->nclasses[prio])/
1041 q->quanta[prio];
1042 }
1043 if (cl->quantum <= 0 ||
1044 cl->quantum > 32*qdisc_dev(cl->qdisc)->mtu) {
1045 pr_warn("CBQ: class %08x has bad quantum==%ld, repaired.\n",
1046 cl->common.classid, cl->quantum);
1047 cl->quantum = qdisc_dev(cl->qdisc)->mtu/2 + 1;
1048 }
1049 }
1050 }
1051 }
1052
1053 static void cbq_sync_defmap(struct cbq_class *cl)
1054 {
1055 struct cbq_sched_data *q = qdisc_priv(cl->qdisc);
1056 struct cbq_class *split = cl->split;
1057 unsigned int h;
1058 int i;
1059
1060 if (split == NULL)
1061 return;
1062
1063 for (i = 0; i <= TC_PRIO_MAX; i++) {
1064 if (split->defaults[i] == cl && !(cl->defmap & (1<<i)))
1065 split->defaults[i] = NULL;
1066 }
1067
1068 for (i = 0; i <= TC_PRIO_MAX; i++) {
1069 int level = split->level;
1070
1071 if (split->defaults[i])
1072 continue;
1073
1074 for (h = 0; h < q->clhash.hashsize; h++) {
1075 struct cbq_class *c;
1076
1077 hlist_for_each_entry(c, &q->clhash.hash[h],
1078 common.hnode) {
1079 if (c->split == split && c->level < level &&
1080 c->defmap & (1<<i)) {
1081 split->defaults[i] = c;
1082 level = c->level;
1083 }
1084 }
1085 }
1086 }
1087 }
1088
1089 static void cbq_change_defmap(struct cbq_class *cl, u32 splitid, u32 def, u32 mask)
1090 {
1091 struct cbq_class *split = NULL;
1092
1093 if (splitid == 0) {
1094 split = cl->split;
1095 if (!split)
1096 return;
1097 splitid = split->common.classid;
1098 }
1099
1100 if (split == NULL || split->common.classid != splitid) {
1101 for (split = cl->tparent; split; split = split->tparent)
1102 if (split->common.classid == splitid)
1103 break;
1104 }
1105
1106 if (split == NULL)
1107 return;
1108
1109 if (cl->split != split) {
1110 cl->defmap = 0;
1111 cbq_sync_defmap(cl);
1112 cl->split = split;
1113 cl->defmap = def & mask;
1114 } else
1115 cl->defmap = (cl->defmap & ~mask) | (def & mask);
1116
1117 cbq_sync_defmap(cl);
1118 }
1119
1120 static void cbq_unlink_class(struct cbq_class *this)
1121 {
1122 struct cbq_class *cl, **clp;
1123 struct cbq_sched_data *q = qdisc_priv(this->qdisc);
1124
1125 qdisc_class_hash_remove(&q->clhash, &this->common);
1126
1127 if (this->tparent) {
1128 clp = &this->sibling;
1129 cl = *clp;
1130 do {
1131 if (cl == this) {
1132 *clp = cl->sibling;
1133 break;
1134 }
1135 clp = &cl->sibling;
1136 } while ((cl = *clp) != this->sibling);
1137
1138 if (this->tparent->children == this) {
1139 this->tparent->children = this->sibling;
1140 if (this->sibling == this)
1141 this->tparent->children = NULL;
1142 }
1143 } else {
1144 WARN_ON(this->sibling != this);
1145 }
1146 }
1147
1148 static void cbq_link_class(struct cbq_class *this)
1149 {
1150 struct cbq_sched_data *q = qdisc_priv(this->qdisc);
1151 struct cbq_class *parent = this->tparent;
1152
1153 this->sibling = this;
1154 qdisc_class_hash_insert(&q->clhash, &this->common);
1155
1156 if (parent == NULL)
1157 return;
1158
1159 if (parent->children == NULL) {
1160 parent->children = this;
1161 } else {
1162 this->sibling = parent->children->sibling;
1163 parent->children->sibling = this;
1164 }
1165 }
1166
1167 static unsigned int cbq_drop(struct Qdisc *sch)
1168 {
1169 struct cbq_sched_data *q = qdisc_priv(sch);
1170 struct cbq_class *cl, *cl_head;
1171 int prio;
1172 unsigned int len;
1173
1174 for (prio = TC_CBQ_MAXPRIO; prio >= 0; prio--) {
1175 cl_head = q->active[prio];
1176 if (!cl_head)
1177 continue;
1178
1179 cl = cl_head;
1180 do {
1181 if (cl->q->ops->drop && (len = cl->q->ops->drop(cl->q))) {
1182 sch->q.qlen--;
1183 if (!cl->q->q.qlen)
1184 cbq_deactivate_class(cl);
1185 return len;
1186 }
1187 } while ((cl = cl->next_alive) != cl_head);
1188 }
1189 return 0;
1190 }
1191
1192 static void
1193 cbq_reset(struct Qdisc *sch)
1194 {
1195 struct cbq_sched_data *q = qdisc_priv(sch);
1196 struct cbq_class *cl;
1197 int prio;
1198 unsigned int h;
1199
1200 q->activemask = 0;
1201 q->pmask = 0;
1202 q->tx_class = NULL;
1203 q->tx_borrowed = NULL;
1204 qdisc_watchdog_cancel(&q->watchdog);
1205 hrtimer_cancel(&q->delay_timer);
1206 q->toplevel = TC_CBQ_MAXLEVEL;
1207 q->now = psched_get_time();
1208
1209 for (prio = 0; prio <= TC_CBQ_MAXPRIO; prio++)
1210 q->active[prio] = NULL;
1211
1212 for (h = 0; h < q->clhash.hashsize; h++) {
1213 hlist_for_each_entry(cl, &q->clhash.hash[h], common.hnode) {
1214 qdisc_reset(cl->q);
1215
1216 cl->next_alive = NULL;
1217 cl->undertime = PSCHED_PASTPERFECT;
1218 cl->avgidle = cl->maxidle;
1219 cl->deficit = cl->quantum;
1220 cl->cpriority = cl->priority;
1221 }
1222 }
1223 sch->q.qlen = 0;
1224 }
1225
1226
1227 static int cbq_set_lss(struct cbq_class *cl, struct tc_cbq_lssopt *lss)
1228 {
1229 if (lss->change & TCF_CBQ_LSS_FLAGS) {
1230 cl->share = (lss->flags & TCF_CBQ_LSS_ISOLATED) ? NULL : cl->tparent;
1231 cl->borrow = (lss->flags & TCF_CBQ_LSS_BOUNDED) ? NULL : cl->tparent;
1232 }
1233 if (lss->change & TCF_CBQ_LSS_EWMA)
1234 cl->ewma_log = lss->ewma_log;
1235 if (lss->change & TCF_CBQ_LSS_AVPKT)
1236 cl->avpkt = lss->avpkt;
1237 if (lss->change & TCF_CBQ_LSS_MINIDLE)
1238 cl->minidle = -(long)lss->minidle;
1239 if (lss->change & TCF_CBQ_LSS_MAXIDLE) {
1240 cl->maxidle = lss->maxidle;
1241 cl->avgidle = lss->maxidle;
1242 }
1243 if (lss->change & TCF_CBQ_LSS_OFFTIME)
1244 cl->offtime = lss->offtime;
1245 return 0;
1246 }
1247
1248 static void cbq_rmprio(struct cbq_sched_data *q, struct cbq_class *cl)
1249 {
1250 q->nclasses[cl->priority]--;
1251 q->quanta[cl->priority] -= cl->weight;
1252 cbq_normalize_quanta(q, cl->priority);
1253 }
1254
1255 static void cbq_addprio(struct cbq_sched_data *q, struct cbq_class *cl)
1256 {
1257 q->nclasses[cl->priority]++;
1258 q->quanta[cl->priority] += cl->weight;
1259 cbq_normalize_quanta(q, cl->priority);
1260 }
1261
1262 static int cbq_set_wrr(struct cbq_class *cl, struct tc_cbq_wrropt *wrr)
1263 {
1264 struct cbq_sched_data *q = qdisc_priv(cl->qdisc);
1265
1266 if (wrr->allot)
1267 cl->allot = wrr->allot;
1268 if (wrr->weight)
1269 cl->weight = wrr->weight;
1270 if (wrr->priority) {
1271 cl->priority = wrr->priority - 1;
1272 cl->cpriority = cl->priority;
1273 if (cl->priority >= cl->priority2)
1274 cl->priority2 = TC_CBQ_MAXPRIO - 1;
1275 }
1276
1277 cbq_addprio(q, cl);
1278 return 0;
1279 }
1280
1281 static int cbq_set_overlimit(struct cbq_class *cl, struct tc_cbq_ovl *ovl)
1282 {
1283 switch (ovl->strategy) {
1284 case TC_CBQ_OVL_CLASSIC:
1285 cl->overlimit = cbq_ovl_classic;
1286 break;
1287 case TC_CBQ_OVL_DELAY:
1288 cl->overlimit = cbq_ovl_delay;
1289 break;
1290 case TC_CBQ_OVL_LOWPRIO:
1291 if (ovl->priority2 - 1 >= TC_CBQ_MAXPRIO ||
1292 ovl->priority2 - 1 <= cl->priority)
1293 return -EINVAL;
1294 cl->priority2 = ovl->priority2 - 1;
1295 cl->overlimit = cbq_ovl_lowprio;
1296 break;
1297 case TC_CBQ_OVL_DROP:
1298 cl->overlimit = cbq_ovl_drop;
1299 break;
1300 case TC_CBQ_OVL_RCLASSIC:
1301 cl->overlimit = cbq_ovl_rclassic;
1302 break;
1303 default:
1304 return -EINVAL;
1305 }
1306 cl->penalty = ovl->penalty;
1307 return 0;
1308 }
1309
1310 #ifdef CONFIG_NET_CLS_ACT
1311 static int cbq_set_police(struct cbq_class *cl, struct tc_cbq_police *p)
1312 {
1313 cl->police = p->police;
1314
1315 if (cl->q->handle) {
1316 if (p->police == TC_POLICE_RECLASSIFY)
1317 cl->q->reshape_fail = cbq_reshape_fail;
1318 else
1319 cl->q->reshape_fail = NULL;
1320 }
1321 return 0;
1322 }
1323 #endif
1324
1325 static int cbq_set_fopt(struct cbq_class *cl, struct tc_cbq_fopt *fopt)
1326 {
1327 cbq_change_defmap(cl, fopt->split, fopt->defmap, fopt->defchange);
1328 return 0;
1329 }
1330
1331 static const struct nla_policy cbq_policy[TCA_CBQ_MAX + 1] = {
1332 [TCA_CBQ_LSSOPT] = { .len = sizeof(struct tc_cbq_lssopt) },
1333 [TCA_CBQ_WRROPT] = { .len = sizeof(struct tc_cbq_wrropt) },
1334 [TCA_CBQ_FOPT] = { .len = sizeof(struct tc_cbq_fopt) },
1335 [TCA_CBQ_OVL_STRATEGY] = { .len = sizeof(struct tc_cbq_ovl) },
1336 [TCA_CBQ_RATE] = { .len = sizeof(struct tc_ratespec) },
1337 [TCA_CBQ_RTAB] = { .type = NLA_BINARY, .len = TC_RTAB_SIZE },
1338 [TCA_CBQ_POLICE] = { .len = sizeof(struct tc_cbq_police) },
1339 };
1340
1341 static int cbq_init(struct Qdisc *sch, struct nlattr *opt)
1342 {
1343 struct cbq_sched_data *q = qdisc_priv(sch);
1344 struct nlattr *tb[TCA_CBQ_MAX + 1];
1345 struct tc_ratespec *r;
1346 int err;
1347
1348 err = nla_parse_nested(tb, TCA_CBQ_MAX, opt, cbq_policy);
1349 if (err < 0)
1350 return err;
1351
1352 if (tb[TCA_CBQ_RTAB] == NULL || tb[TCA_CBQ_RATE] == NULL)
1353 return -EINVAL;
1354
1355 r = nla_data(tb[TCA_CBQ_RATE]);
1356
1357 if ((q->link.R_tab = qdisc_get_rtab(r, tb[TCA_CBQ_RTAB])) == NULL)
1358 return -EINVAL;
1359
1360 err = qdisc_class_hash_init(&q->clhash);
1361 if (err < 0)
1362 goto put_rtab;
1363
1364 q->link.refcnt = 1;
1365 q->link.sibling = &q->link;
1366 q->link.common.classid = sch->handle;
1367 q->link.qdisc = sch;
1368 q->link.q = qdisc_create_dflt(sch->dev_queue, &pfifo_qdisc_ops,
1369 sch->handle);
1370 if (!q->link.q)
1371 q->link.q = &noop_qdisc;
1372
1373 q->link.priority = TC_CBQ_MAXPRIO - 1;
1374 q->link.priority2 = TC_CBQ_MAXPRIO - 1;
1375 q->link.cpriority = TC_CBQ_MAXPRIO - 1;
1376 q->link.ovl_strategy = TC_CBQ_OVL_CLASSIC;
1377 q->link.overlimit = cbq_ovl_classic;
1378 q->link.allot = psched_mtu(qdisc_dev(sch));
1379 q->link.quantum = q->link.allot;
1380 q->link.weight = q->link.R_tab->rate.rate;
1381
1382 q->link.ewma_log = TC_CBQ_DEF_EWMA;
1383 q->link.avpkt = q->link.allot/2;
1384 q->link.minidle = -0x7FFFFFFF;
1385
1386 qdisc_watchdog_init(&q->watchdog, sch);
1387 hrtimer_init(&q->delay_timer, CLOCK_MONOTONIC, HRTIMER_MODE_ABS);
1388 q->delay_timer.function = cbq_undelay;
1389 q->toplevel = TC_CBQ_MAXLEVEL;
1390 q->now = psched_get_time();
1391
1392 cbq_link_class(&q->link);
1393
1394 if (tb[TCA_CBQ_LSSOPT])
1395 cbq_set_lss(&q->link, nla_data(tb[TCA_CBQ_LSSOPT]));
1396
1397 cbq_addprio(q, &q->link);
1398 return 0;
1399
1400 put_rtab:
1401 qdisc_put_rtab(q->link.R_tab);
1402 return err;
1403 }
1404
1405 static int cbq_dump_rate(struct sk_buff *skb, struct cbq_class *cl)
1406 {
1407 unsigned char *b = skb_tail_pointer(skb);
1408
1409 if (nla_put(skb, TCA_CBQ_RATE, sizeof(cl->R_tab->rate), &cl->R_tab->rate))
1410 goto nla_put_failure;
1411 return skb->len;
1412
1413 nla_put_failure:
1414 nlmsg_trim(skb, b);
1415 return -1;
1416 }
1417
1418 static int cbq_dump_lss(struct sk_buff *skb, struct cbq_class *cl)
1419 {
1420 unsigned char *b = skb_tail_pointer(skb);
1421 struct tc_cbq_lssopt opt;
1422
1423 opt.flags = 0;
1424 if (cl->borrow == NULL)
1425 opt.flags |= TCF_CBQ_LSS_BOUNDED;
1426 if (cl->share == NULL)
1427 opt.flags |= TCF_CBQ_LSS_ISOLATED;
1428 opt.ewma_log = cl->ewma_log;
1429 opt.level = cl->level;
1430 opt.avpkt = cl->avpkt;
1431 opt.maxidle = cl->maxidle;
1432 opt.minidle = (u32)(-cl->minidle);
1433 opt.offtime = cl->offtime;
1434 opt.change = ~0;
1435 if (nla_put(skb, TCA_CBQ_LSSOPT, sizeof(opt), &opt))
1436 goto nla_put_failure;
1437 return skb->len;
1438
1439 nla_put_failure:
1440 nlmsg_trim(skb, b);
1441 return -1;
1442 }
1443
1444 static int cbq_dump_wrr(struct sk_buff *skb, struct cbq_class *cl)
1445 {
1446 unsigned char *b = skb_tail_pointer(skb);
1447 struct tc_cbq_wrropt opt;
1448
1449 memset(&opt, 0, sizeof(opt));
1450 opt.flags = 0;
1451 opt.allot = cl->allot;
1452 opt.priority = cl->priority + 1;
1453 opt.cpriority = cl->cpriority + 1;
1454 opt.weight = cl->weight;
1455 if (nla_put(skb, TCA_CBQ_WRROPT, 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_ovl(struct sk_buff *skb, struct cbq_class *cl)
1465 {
1466 unsigned char *b = skb_tail_pointer(skb);
1467 struct tc_cbq_ovl opt;
1468
1469 opt.strategy = cl->ovl_strategy;
1470 opt.priority2 = cl->priority2 + 1;
1471 opt.pad = 0;
1472 opt.penalty = cl->penalty;
1473 if (nla_put(skb, TCA_CBQ_OVL_STRATEGY, sizeof(opt), &opt))
1474 goto nla_put_failure;
1475 return skb->len;
1476
1477 nla_put_failure:
1478 nlmsg_trim(skb, b);
1479 return -1;
1480 }
1481
1482 static int cbq_dump_fopt(struct sk_buff *skb, struct cbq_class *cl)
1483 {
1484 unsigned char *b = skb_tail_pointer(skb);
1485 struct tc_cbq_fopt opt;
1486
1487 if (cl->split || cl->defmap) {
1488 opt.split = cl->split ? cl->split->common.classid : 0;
1489 opt.defmap = cl->defmap;
1490 opt.defchange = ~0;
1491 if (nla_put(skb, TCA_CBQ_FOPT, sizeof(opt), &opt))
1492 goto nla_put_failure;
1493 }
1494 return skb->len;
1495
1496 nla_put_failure:
1497 nlmsg_trim(skb, b);
1498 return -1;
1499 }
1500
1501 #ifdef CONFIG_NET_CLS_ACT
1502 static int cbq_dump_police(struct sk_buff *skb, struct cbq_class *cl)
1503 {
1504 unsigned char *b = skb_tail_pointer(skb);
1505 struct tc_cbq_police opt;
1506
1507 if (cl->police) {
1508 opt.police = cl->police;
1509 opt.__res1 = 0;
1510 opt.__res2 = 0;
1511 if (nla_put(skb, TCA_CBQ_POLICE, 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 #endif
1521
1522 static int cbq_dump_attr(struct sk_buff *skb, struct cbq_class *cl)
1523 {
1524 if (cbq_dump_lss(skb, cl) < 0 ||
1525 cbq_dump_rate(skb, cl) < 0 ||
1526 cbq_dump_wrr(skb, cl) < 0 ||
1527 cbq_dump_ovl(skb, cl) < 0 ||
1528 #ifdef CONFIG_NET_CLS_ACT
1529 cbq_dump_police(skb, cl) < 0 ||
1530 #endif
1531 cbq_dump_fopt(skb, cl) < 0)
1532 return -1;
1533 return 0;
1534 }
1535
1536 static int cbq_dump(struct Qdisc *sch, struct sk_buff *skb)
1537 {
1538 struct cbq_sched_data *q = qdisc_priv(sch);
1539 struct nlattr *nest;
1540
1541 nest = nla_nest_start(skb, TCA_OPTIONS);
1542 if (nest == NULL)
1543 goto nla_put_failure;
1544 if (cbq_dump_attr(skb, &q->link) < 0)
1545 goto nla_put_failure;
1546 return nla_nest_end(skb, nest);
1547
1548 nla_put_failure:
1549 nla_nest_cancel(skb, nest);
1550 return -1;
1551 }
1552
1553 static int
1554 cbq_dump_stats(struct Qdisc *sch, struct gnet_dump *d)
1555 {
1556 struct cbq_sched_data *q = qdisc_priv(sch);
1557
1558 q->link.xstats.avgidle = q->link.avgidle;
1559 return gnet_stats_copy_app(d, &q->link.xstats, sizeof(q->link.xstats));
1560 }
1561
1562 static int
1563 cbq_dump_class(struct Qdisc *sch, unsigned long arg,
1564 struct sk_buff *skb, struct tcmsg *tcm)
1565 {
1566 struct cbq_class *cl = (struct cbq_class *)arg;
1567 struct nlattr *nest;
1568
1569 if (cl->tparent)
1570 tcm->tcm_parent = cl->tparent->common.classid;
1571 else
1572 tcm->tcm_parent = TC_H_ROOT;
1573 tcm->tcm_handle = cl->common.classid;
1574 tcm->tcm_info = cl->q->handle;
1575
1576 nest = nla_nest_start(skb, TCA_OPTIONS);
1577 if (nest == NULL)
1578 goto nla_put_failure;
1579 if (cbq_dump_attr(skb, cl) < 0)
1580 goto nla_put_failure;
1581 return nla_nest_end(skb, nest);
1582
1583 nla_put_failure:
1584 nla_nest_cancel(skb, nest);
1585 return -1;
1586 }
1587
1588 static int
1589 cbq_dump_class_stats(struct Qdisc *sch, unsigned long arg,
1590 struct gnet_dump *d)
1591 {
1592 struct cbq_sched_data *q = qdisc_priv(sch);
1593 struct cbq_class *cl = (struct cbq_class *)arg;
1594
1595 cl->qstats.qlen = cl->q->q.qlen;
1596 cl->xstats.avgidle = cl->avgidle;
1597 cl->xstats.undertime = 0;
1598
1599 if (cl->undertime != PSCHED_PASTPERFECT)
1600 cl->xstats.undertime = cl->undertime - q->now;
1601
1602 if (gnet_stats_copy_basic(d, &cl->bstats) < 0 ||
1603 gnet_stats_copy_rate_est(d, &cl->bstats, &cl->rate_est) < 0 ||
1604 gnet_stats_copy_queue(d, &cl->qstats) < 0)
1605 return -1;
1606
1607 return gnet_stats_copy_app(d, &cl->xstats, sizeof(cl->xstats));
1608 }
1609
1610 static int cbq_graft(struct Qdisc *sch, unsigned long arg, struct Qdisc *new,
1611 struct Qdisc **old)
1612 {
1613 struct cbq_class *cl = (struct cbq_class *)arg;
1614
1615 if (new == NULL) {
1616 new = qdisc_create_dflt(sch->dev_queue,
1617 &pfifo_qdisc_ops, cl->common.classid);
1618 if (new == NULL)
1619 return -ENOBUFS;
1620 } else {
1621 #ifdef CONFIG_NET_CLS_ACT
1622 if (cl->police == TC_POLICE_RECLASSIFY)
1623 new->reshape_fail = cbq_reshape_fail;
1624 #endif
1625 }
1626 sch_tree_lock(sch);
1627 *old = cl->q;
1628 cl->q = new;
1629 qdisc_tree_decrease_qlen(*old, (*old)->q.qlen);
1630 qdisc_reset(*old);
1631 sch_tree_unlock(sch);
1632
1633 return 0;
1634 }
1635
1636 static struct Qdisc *cbq_leaf(struct Qdisc *sch, unsigned long arg)
1637 {
1638 struct cbq_class *cl = (struct cbq_class *)arg;
1639
1640 return cl->q;
1641 }
1642
1643 static void cbq_qlen_notify(struct Qdisc *sch, unsigned long arg)
1644 {
1645 struct cbq_class *cl = (struct cbq_class *)arg;
1646
1647 if (cl->q->q.qlen == 0)
1648 cbq_deactivate_class(cl);
1649 }
1650
1651 static unsigned long cbq_get(struct Qdisc *sch, u32 classid)
1652 {
1653 struct cbq_sched_data *q = qdisc_priv(sch);
1654 struct cbq_class *cl = cbq_class_lookup(q, classid);
1655
1656 if (cl) {
1657 cl->refcnt++;
1658 return (unsigned long)cl;
1659 }
1660 return 0;
1661 }
1662
1663 static void cbq_destroy_class(struct Qdisc *sch, struct cbq_class *cl)
1664 {
1665 struct cbq_sched_data *q = qdisc_priv(sch);
1666
1667 WARN_ON(cl->filters);
1668
1669 tcf_destroy_chain(&cl->filter_list);
1670 qdisc_destroy(cl->q);
1671 qdisc_put_rtab(cl->R_tab);
1672 gen_kill_estimator(&cl->bstats, &cl->rate_est);
1673 if (cl != &q->link)
1674 kfree(cl);
1675 }
1676
1677 static void cbq_destroy(struct Qdisc *sch)
1678 {
1679 struct cbq_sched_data *q = qdisc_priv(sch);
1680 struct hlist_node *next;
1681 struct cbq_class *cl;
1682 unsigned int h;
1683
1684 #ifdef CONFIG_NET_CLS_ACT
1685 q->rx_class = NULL;
1686 #endif
1687 /*
1688 * Filters must be destroyed first because we don't destroy the
1689 * classes from root to leafs which means that filters can still
1690 * be bound to classes which have been destroyed already. --TGR '04
1691 */
1692 for (h = 0; h < q->clhash.hashsize; h++) {
1693 hlist_for_each_entry(cl, &q->clhash.hash[h], common.hnode)
1694 tcf_destroy_chain(&cl->filter_list);
1695 }
1696 for (h = 0; h < q->clhash.hashsize; h++) {
1697 hlist_for_each_entry_safe(cl, next, &q->clhash.hash[h],
1698 common.hnode)
1699 cbq_destroy_class(sch, cl);
1700 }
1701 qdisc_class_hash_destroy(&q->clhash);
1702 }
1703
1704 static void cbq_put(struct Qdisc *sch, unsigned long arg)
1705 {
1706 struct cbq_class *cl = (struct cbq_class *)arg;
1707
1708 if (--cl->refcnt == 0) {
1709 #ifdef CONFIG_NET_CLS_ACT
1710 spinlock_t *root_lock = qdisc_root_sleeping_lock(sch);
1711 struct cbq_sched_data *q = qdisc_priv(sch);
1712
1713 spin_lock_bh(root_lock);
1714 if (q->rx_class == cl)
1715 q->rx_class = NULL;
1716 spin_unlock_bh(root_lock);
1717 #endif
1718
1719 cbq_destroy_class(sch, cl);
1720 }
1721 }
1722
1723 static int
1724 cbq_change_class(struct Qdisc *sch, u32 classid, u32 parentid, struct nlattr **tca,
1725 unsigned long *arg)
1726 {
1727 int err;
1728 struct cbq_sched_data *q = qdisc_priv(sch);
1729 struct cbq_class *cl = (struct cbq_class *)*arg;
1730 struct nlattr *opt = tca[TCA_OPTIONS];
1731 struct nlattr *tb[TCA_CBQ_MAX + 1];
1732 struct cbq_class *parent;
1733 struct qdisc_rate_table *rtab = NULL;
1734
1735 if (opt == NULL)
1736 return -EINVAL;
1737
1738 err = nla_parse_nested(tb, TCA_CBQ_MAX, opt, cbq_policy);
1739 if (err < 0)
1740 return err;
1741
1742 if (cl) {
1743 /* Check parent */
1744 if (parentid) {
1745 if (cl->tparent &&
1746 cl->tparent->common.classid != parentid)
1747 return -EINVAL;
1748 if (!cl->tparent && parentid != TC_H_ROOT)
1749 return -EINVAL;
1750 }
1751
1752 if (tb[TCA_CBQ_RATE]) {
1753 rtab = qdisc_get_rtab(nla_data(tb[TCA_CBQ_RATE]),
1754 tb[TCA_CBQ_RTAB]);
1755 if (rtab == NULL)
1756 return -EINVAL;
1757 }
1758
1759 if (tca[TCA_RATE]) {
1760 err = gen_replace_estimator(&cl->bstats, &cl->rate_est,
1761 qdisc_root_sleeping_lock(sch),
1762 tca[TCA_RATE]);
1763 if (err) {
1764 qdisc_put_rtab(rtab);
1765 return err;
1766 }
1767 }
1768
1769 /* Change class parameters */
1770 sch_tree_lock(sch);
1771
1772 if (cl->next_alive != NULL)
1773 cbq_deactivate_class(cl);
1774
1775 if (rtab) {
1776 qdisc_put_rtab(cl->R_tab);
1777 cl->R_tab = rtab;
1778 }
1779
1780 if (tb[TCA_CBQ_LSSOPT])
1781 cbq_set_lss(cl, nla_data(tb[TCA_CBQ_LSSOPT]));
1782
1783 if (tb[TCA_CBQ_WRROPT]) {
1784 cbq_rmprio(q, cl);
1785 cbq_set_wrr(cl, nla_data(tb[TCA_CBQ_WRROPT]));
1786 }
1787
1788 if (tb[TCA_CBQ_OVL_STRATEGY])
1789 cbq_set_overlimit(cl, nla_data(tb[TCA_CBQ_OVL_STRATEGY]));
1790
1791 #ifdef CONFIG_NET_CLS_ACT
1792 if (tb[TCA_CBQ_POLICE])
1793 cbq_set_police(cl, nla_data(tb[TCA_CBQ_POLICE]));
1794 #endif
1795
1796 if (tb[TCA_CBQ_FOPT])
1797 cbq_set_fopt(cl, nla_data(tb[TCA_CBQ_FOPT]));
1798
1799 if (cl->q->q.qlen)
1800 cbq_activate_class(cl);
1801
1802 sch_tree_unlock(sch);
1803
1804 return 0;
1805 }
1806
1807 if (parentid == TC_H_ROOT)
1808 return -EINVAL;
1809
1810 if (tb[TCA_CBQ_WRROPT] == NULL || tb[TCA_CBQ_RATE] == NULL ||
1811 tb[TCA_CBQ_LSSOPT] == NULL)
1812 return -EINVAL;
1813
1814 rtab = qdisc_get_rtab(nla_data(tb[TCA_CBQ_RATE]), tb[TCA_CBQ_RTAB]);
1815 if (rtab == NULL)
1816 return -EINVAL;
1817
1818 if (classid) {
1819 err = -EINVAL;
1820 if (TC_H_MAJ(classid ^ sch->handle) ||
1821 cbq_class_lookup(q, classid))
1822 goto failure;
1823 } else {
1824 int i;
1825 classid = TC_H_MAKE(sch->handle, 0x8000);
1826
1827 for (i = 0; i < 0x8000; i++) {
1828 if (++q->hgenerator >= 0x8000)
1829 q->hgenerator = 1;
1830 if (cbq_class_lookup(q, classid|q->hgenerator) == NULL)
1831 break;
1832 }
1833 err = -ENOSR;
1834 if (i >= 0x8000)
1835 goto failure;
1836 classid = classid|q->hgenerator;
1837 }
1838
1839 parent = &q->link;
1840 if (parentid) {
1841 parent = cbq_class_lookup(q, parentid);
1842 err = -EINVAL;
1843 if (parent == NULL)
1844 goto failure;
1845 }
1846
1847 err = -ENOBUFS;
1848 cl = kzalloc(sizeof(*cl), GFP_KERNEL);
1849 if (cl == NULL)
1850 goto failure;
1851
1852 if (tca[TCA_RATE]) {
1853 err = gen_new_estimator(&cl->bstats, &cl->rate_est,
1854 qdisc_root_sleeping_lock(sch),
1855 tca[TCA_RATE]);
1856 if (err) {
1857 kfree(cl);
1858 goto failure;
1859 }
1860 }
1861
1862 cl->R_tab = rtab;
1863 rtab = NULL;
1864 cl->refcnt = 1;
1865 cl->q = qdisc_create_dflt(sch->dev_queue, &pfifo_qdisc_ops, classid);
1866 if (!cl->q)
1867 cl->q = &noop_qdisc;
1868 cl->common.classid = classid;
1869 cl->tparent = parent;
1870 cl->qdisc = sch;
1871 cl->allot = parent->allot;
1872 cl->quantum = cl->allot;
1873 cl->weight = cl->R_tab->rate.rate;
1874
1875 sch_tree_lock(sch);
1876 cbq_link_class(cl);
1877 cl->borrow = cl->tparent;
1878 if (cl->tparent != &q->link)
1879 cl->share = cl->tparent;
1880 cbq_adjust_levels(parent);
1881 cl->minidle = -0x7FFFFFFF;
1882 cbq_set_lss(cl, nla_data(tb[TCA_CBQ_LSSOPT]));
1883 cbq_set_wrr(cl, nla_data(tb[TCA_CBQ_WRROPT]));
1884 if (cl->ewma_log == 0)
1885 cl->ewma_log = q->link.ewma_log;
1886 if (cl->maxidle == 0)
1887 cl->maxidle = q->link.maxidle;
1888 if (cl->avpkt == 0)
1889 cl->avpkt = q->link.avpkt;
1890 cl->overlimit = cbq_ovl_classic;
1891 if (tb[TCA_CBQ_OVL_STRATEGY])
1892 cbq_set_overlimit(cl, nla_data(tb[TCA_CBQ_OVL_STRATEGY]));
1893 #ifdef CONFIG_NET_CLS_ACT
1894 if (tb[TCA_CBQ_POLICE])
1895 cbq_set_police(cl, nla_data(tb[TCA_CBQ_POLICE]));
1896 #endif
1897 if (tb[TCA_CBQ_FOPT])
1898 cbq_set_fopt(cl, nla_data(tb[TCA_CBQ_FOPT]));
1899 sch_tree_unlock(sch);
1900
1901 qdisc_class_hash_grow(sch, &q->clhash);
1902
1903 *arg = (unsigned long)cl;
1904 return 0;
1905
1906 failure:
1907 qdisc_put_rtab(rtab);
1908 return err;
1909 }
1910
1911 static int cbq_delete(struct Qdisc *sch, unsigned long arg)
1912 {
1913 struct cbq_sched_data *q = qdisc_priv(sch);
1914 struct cbq_class *cl = (struct cbq_class *)arg;
1915 unsigned int qlen;
1916
1917 if (cl->filters || cl->children || cl == &q->link)
1918 return -EBUSY;
1919
1920 sch_tree_lock(sch);
1921
1922 qlen = cl->q->q.qlen;
1923 qdisc_reset(cl->q);
1924 qdisc_tree_decrease_qlen(cl->q, qlen);
1925
1926 if (cl->next_alive)
1927 cbq_deactivate_class(cl);
1928
1929 if (q->tx_borrowed == cl)
1930 q->tx_borrowed = q->tx_class;
1931 if (q->tx_class == cl) {
1932 q->tx_class = NULL;
1933 q->tx_borrowed = NULL;
1934 }
1935 #ifdef CONFIG_NET_CLS_ACT
1936 if (q->rx_class == cl)
1937 q->rx_class = NULL;
1938 #endif
1939
1940 cbq_unlink_class(cl);
1941 cbq_adjust_levels(cl->tparent);
1942 cl->defmap = 0;
1943 cbq_sync_defmap(cl);
1944
1945 cbq_rmprio(q, cl);
1946 sch_tree_unlock(sch);
1947
1948 BUG_ON(--cl->refcnt == 0);
1949 /*
1950 * This shouldn't happen: we "hold" one cops->get() when called
1951 * from tc_ctl_tclass; the destroy method is done from cops->put().
1952 */
1953
1954 return 0;
1955 }
1956
1957 static struct tcf_proto **cbq_find_tcf(struct Qdisc *sch, unsigned long arg)
1958 {
1959 struct cbq_sched_data *q = qdisc_priv(sch);
1960 struct cbq_class *cl = (struct cbq_class *)arg;
1961
1962 if (cl == NULL)
1963 cl = &q->link;
1964
1965 return &cl->filter_list;
1966 }
1967
1968 static unsigned long cbq_bind_filter(struct Qdisc *sch, unsigned long parent,
1969 u32 classid)
1970 {
1971 struct cbq_sched_data *q = qdisc_priv(sch);
1972 struct cbq_class *p = (struct cbq_class *)parent;
1973 struct cbq_class *cl = cbq_class_lookup(q, classid);
1974
1975 if (cl) {
1976 if (p && p->level <= cl->level)
1977 return 0;
1978 cl->filters++;
1979 return (unsigned long)cl;
1980 }
1981 return 0;
1982 }
1983
1984 static void cbq_unbind_filter(struct Qdisc *sch, unsigned long arg)
1985 {
1986 struct cbq_class *cl = (struct cbq_class *)arg;
1987
1988 cl->filters--;
1989 }
1990
1991 static void cbq_walk(struct Qdisc *sch, struct qdisc_walker *arg)
1992 {
1993 struct cbq_sched_data *q = qdisc_priv(sch);
1994 struct cbq_class *cl;
1995 unsigned int h;
1996
1997 if (arg->stop)
1998 return;
1999
2000 for (h = 0; h < q->clhash.hashsize; h++) {
2001 hlist_for_each_entry(cl, &q->clhash.hash[h], common.hnode) {
2002 if (arg->count < arg->skip) {
2003 arg->count++;
2004 continue;
2005 }
2006 if (arg->fn(sch, (unsigned long)cl, arg) < 0) {
2007 arg->stop = 1;
2008 return;
2009 }
2010 arg->count++;
2011 }
2012 }
2013 }
2014
2015 static const struct Qdisc_class_ops cbq_class_ops = {
2016 .graft = cbq_graft,
2017 .leaf = cbq_leaf,
2018 .qlen_notify = cbq_qlen_notify,
2019 .get = cbq_get,
2020 .put = cbq_put,
2021 .change = cbq_change_class,
2022 .delete = cbq_delete,
2023 .walk = cbq_walk,
2024 .tcf_chain = cbq_find_tcf,
2025 .bind_tcf = cbq_bind_filter,
2026 .unbind_tcf = cbq_unbind_filter,
2027 .dump = cbq_dump_class,
2028 .dump_stats = cbq_dump_class_stats,
2029 };
2030
2031 static struct Qdisc_ops cbq_qdisc_ops __read_mostly = {
2032 .next = NULL,
2033 .cl_ops = &cbq_class_ops,
2034 .id = "cbq",
2035 .priv_size = sizeof(struct cbq_sched_data),
2036 .enqueue = cbq_enqueue,
2037 .dequeue = cbq_dequeue,
2038 .peek = qdisc_peek_dequeued,
2039 .drop = cbq_drop,
2040 .init = cbq_init,
2041 .reset = cbq_reset,
2042 .destroy = cbq_destroy,
2043 .change = NULL,
2044 .dump = cbq_dump,
2045 .dump_stats = cbq_dump_stats,
2046 .owner = THIS_MODULE,
2047 };
2048
2049 static int __init cbq_module_init(void)
2050 {
2051 return register_qdisc(&cbq_qdisc_ops);
2052 }
2053 static void __exit cbq_module_exit(void)
2054 {
2055 unregister_qdisc(&cbq_qdisc_ops);
2056 }
2057 module_init(cbq_module_init)
2058 module_exit(cbq_module_exit)
2059 MODULE_LICENSE("GPL");
(deprecated) Btrfs devel tree