?  search:
summary | log | graphiclog1 | graphiclog2 | commit | commitdiff | tree | refs | edit | fork
blame | history | raw | HEAD
net_sched: move TCQ_F_THROTTLED flag
[linux-2.6/linux-acpi-2.6/ibm-acpi-2.6.git] / net / sched / sch_cbq.c
blob25ed522b2891556427e5011c15b9f976c4585077
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 || cl->level >= head->level)
254 goto fallback;
255 }
256
257 #ifdef CONFIG_NET_CLS_ACT
258 switch (result) {
259 case TC_ACT_QUEUED:
260 case TC_ACT_STOLEN:
261 *qerr = NET_XMIT_SUCCESS | __NET_XMIT_STOLEN;
262 case TC_ACT_SHOT:
263 return NULL;
264 case TC_ACT_RECLASSIFY:
265 return cbq_reclassify(skb, cl);
266 }
267 #endif
268 if (cl->level == 0)
269 return cl;
270
271 /*
272 * Step 3+n. If classifier selected a link sharing class,
273 * apply agency specific classifier.
274 * Repeat this procdure until we hit a leaf node.
275 */
276 head = cl;
277 }
278
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;
356 psched_tdiff_t incr;
357
358 now = psched_get_time();
359 incr = now - q->now_rt;
360 now = q->now + incr;
361
362 do {
363 if (cl->undertime < now) {
364 q->toplevel = cl->level;
365 return;
366 }
367 } while ((cl = cl->borrow) != NULL && toplevel > cl->level);
368 }
369 }
370
371 static int
372 cbq_enqueue(struct sk_buff *skb, struct Qdisc *sch)
373 {
374 struct cbq_sched_data *q = qdisc_priv(sch);
375 int uninitialized_var(ret);
376 struct cbq_class *cl = cbq_classify(skb, sch, &ret);
377
378 #ifdef CONFIG_NET_CLS_ACT
379 q->rx_class = cl;
380 #endif
381 if (cl == NULL) {
382 if (ret & __NET_XMIT_BYPASS)
383 sch->qstats.drops++;
384 kfree_skb(skb);
385 return ret;
386 }
387
388 #ifdef CONFIG_NET_CLS_ACT
389 cl->q->__parent = sch;
390 #endif
391 ret = qdisc_enqueue(skb, cl->q);
392 if (ret == NET_XMIT_SUCCESS) {
393 sch->q.qlen++;
394 qdisc_bstats_update(sch, skb);
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 qdisc_bstats_update(sch, skb);
654 if (!cl->next_alive)
655 cbq_activate_class(cl);
656 return 0;
657 }
658 if (net_xmit_drop_count(ret))
659 sch->qstats.drops++;
660 return 0;
661 }
662
663 sch->qstats.drops++;
664 return -1;
665 }
666 #endif
667
668 /*
669 * It is mission critical procedure.
670 *
671 * We "regenerate" toplevel cutoff, if transmitting class
672 * has backlog and it is not regulated. It is not part of
673 * original CBQ description, but looks more reasonable.
674 * Probably, it is wrong. This question needs further investigation.
675 */
676
677 static inline void
678 cbq_update_toplevel(struct cbq_sched_data *q, struct cbq_class *cl,
679 struct cbq_class *borrowed)
680 {
681 if (cl && q->toplevel >= borrowed->level) {
682 if (cl->q->q.qlen > 1) {
683 do {
684 if (borrowed->undertime == PSCHED_PASTPERFECT) {
685 q->toplevel = borrowed->level;
686 return;
687 }
688 } while ((borrowed = borrowed->borrow) != NULL);
689 }
690 #if 0
691 /* It is not necessary now. Uncommenting it
692 will save CPU cycles, but decrease fairness.
693 */
694 q->toplevel = TC_CBQ_MAXLEVEL;
695 #endif
696 }
697 }
698
699 static void
700 cbq_update(struct cbq_sched_data *q)
701 {
702 struct cbq_class *this = q->tx_class;
703 struct cbq_class *cl = this;
704 int len = q->tx_len;
705
706 q->tx_class = NULL;
707
708 for ( ; cl; cl = cl->share) {
709 long avgidle = cl->avgidle;
710 long idle;
711
712 cl->bstats.packets++;
713 cl->bstats.bytes += len;
714
715 /*
716 * (now - last) is total time between packet right edges.
717 * (last_pktlen/rate) is "virtual" busy time, so that
718 *
719 * idle = (now - last) - last_pktlen/rate
720 */
721
722 idle = q->now - cl->last;
723 if ((unsigned long)idle > 128*1024*1024) {
724 avgidle = cl->maxidle;
725 } else {
726 idle -= L2T(cl, len);
727
728 /* true_avgidle := (1-W)*true_avgidle + W*idle,
729 * where W=2^{-ewma_log}. But cl->avgidle is scaled:
730 * cl->avgidle == true_avgidle/W,
731 * hence:
732 */
733 avgidle += idle - (avgidle>>cl->ewma_log);
734 }
735
736 if (avgidle <= 0) {
737 /* Overlimit or at-limit */
738
739 if (avgidle < cl->minidle)
740 avgidle = cl->minidle;
741
742 cl->avgidle = avgidle;
743
744 /* Calculate expected time, when this class
745 * will be allowed to send.
746 * It will occur, when:
747 * (1-W)*true_avgidle + W*delay = 0, i.e.
748 * idle = (1/W - 1)*(-true_avgidle)
749 * or
750 * idle = (1 - W)*(-cl->avgidle);
751 */
752 idle = (-avgidle) - ((-avgidle) >> cl->ewma_log);
753
754 /*
755 * That is not all.
756 * To maintain the rate allocated to the class,
757 * we add to undertime virtual clock,
758 * necessary to complete transmitted packet.
759 * (len/phys_bandwidth has been already passed
760 * to the moment of cbq_update)
761 */
762
763 idle -= L2T(&q->link, len);
764 idle += L2T(cl, len);
765
766 cl->undertime = q->now + idle;
767 } else {
768 /* Underlimit */
769
770 cl->undertime = PSCHED_PASTPERFECT;
771 if (avgidle > cl->maxidle)
772 cl->avgidle = cl->maxidle;
773 else
774 cl->avgidle = avgidle;
775 }
776 cl->last = q->now;
777 }
778
779 cbq_update_toplevel(q, this, q->tx_borrowed);
780 }
781
782 static inline struct cbq_class *
783 cbq_under_limit(struct cbq_class *cl)
784 {
785 struct cbq_sched_data *q = qdisc_priv(cl->qdisc);
786 struct cbq_class *this_cl = cl;
787
788 if (cl->tparent == NULL)
789 return cl;
790
791 if (cl->undertime == PSCHED_PASTPERFECT || q->now >= cl->undertime) {
792 cl->delayed = 0;
793 return cl;
794 }
795
796 do {
797 /* It is very suspicious place. Now overlimit
798 * action is generated for not bounded classes
799 * only if link is completely congested.
800 * Though it is in agree with ancestor-only paradigm,
801 * it looks very stupid. Particularly,
802 * it means that this chunk of code will either
803 * never be called or result in strong amplification
804 * of burstiness. Dangerous, silly, and, however,
805 * no another solution exists.
806 */
807 cl = cl->borrow;
808 if (!cl) {
809 this_cl->qstats.overlimits++;
810 this_cl->overlimit(this_cl);
811 return NULL;
812 }
813 if (cl->level > q->toplevel)
814 return NULL;
815 } while (cl->undertime != PSCHED_PASTPERFECT && q->now < cl->undertime);
816
817 cl->delayed = 0;
818 return cl;
819 }
820
821 static inline struct sk_buff *
822 cbq_dequeue_prio(struct Qdisc *sch, int prio)
823 {
824 struct cbq_sched_data *q = qdisc_priv(sch);
825 struct cbq_class *cl_tail, *cl_prev, *cl;
826 struct sk_buff *skb;
827 int deficit;
828
829 cl_tail = cl_prev = q->active[prio];
830 cl = cl_prev->next_alive;
831
832 do {
833 deficit = 0;
834
835 /* Start round */
836 do {
837 struct cbq_class *borrow = cl;
838
839 if (cl->q->q.qlen &&
840 (borrow = cbq_under_limit(cl)) == NULL)
841 goto skip_class;
842
843 if (cl->deficit <= 0) {
844 /* Class exhausted its allotment per
845 * this round. Switch to the next one.
846 */
847 deficit = 1;
848 cl->deficit += cl->quantum;
849 goto next_class;
850 }
851
852 skb = cl->q->dequeue(cl->q);
853
854 /* Class did not give us any skb :-(
855 * It could occur even if cl->q->q.qlen != 0
856 * f.e. if cl->q == "tbf"
857 */
858 if (skb == NULL)
859 goto skip_class;
860
861 cl->deficit -= qdisc_pkt_len(skb);
862 q->tx_class = cl;
863 q->tx_borrowed = borrow;
864 if (borrow != cl) {
865 #ifndef CBQ_XSTATS_BORROWS_BYTES
866 borrow->xstats.borrows++;
867 cl->xstats.borrows++;
868 #else
869 borrow->xstats.borrows += qdisc_pkt_len(skb);
870 cl->xstats.borrows += qdisc_pkt_len(skb);
871 #endif
872 }
873 q->tx_len = qdisc_pkt_len(skb);
874
875 if (cl->deficit <= 0) {
876 q->active[prio] = cl;
877 cl = cl->next_alive;
878 cl->deficit += cl->quantum;
879 }
880 return skb;
881
882 skip_class:
883 if (cl->q->q.qlen == 0 || prio != cl->cpriority) {
884 /* Class is empty or penalized.
885 * Unlink it from active chain.
886 */
887 cl_prev->next_alive = cl->next_alive;
888 cl->next_alive = NULL;
889
890 /* Did cl_tail point to it? */
891 if (cl == cl_tail) {
892 /* Repair it! */
893 cl_tail = cl_prev;
894
895 /* Was it the last class in this band? */
896 if (cl == cl_tail) {
897 /* Kill the band! */
898 q->active[prio] = NULL;
899 q->activemask &= ~(1<<prio);
900 if (cl->q->q.qlen)
901 cbq_activate_class(cl);
902 return NULL;
903 }
904
905 q->active[prio] = cl_tail;
906 }
907 if (cl->q->q.qlen)
908 cbq_activate_class(cl);
909
910 cl = cl_prev;
911 }
912
913 next_class:
914 cl_prev = cl;
915 cl = cl->next_alive;
916 } while (cl_prev != cl_tail);
917 } while (deficit);
918
919 q->active[prio] = cl_prev;
920
921 return NULL;
922 }
923
924 static inline struct sk_buff *
925 cbq_dequeue_1(struct Qdisc *sch)
926 {
927 struct cbq_sched_data *q = qdisc_priv(sch);
928 struct sk_buff *skb;
929 unsigned int activemask;
930
931 activemask = q->activemask & 0xFF;
932 while (activemask) {
933 int prio = ffz(~activemask);
934 activemask &= ~(1<<prio);
935 skb = cbq_dequeue_prio(sch, prio);
936 if (skb)
937 return skb;
938 }
939 return NULL;
940 }
941
942 static struct sk_buff *
943 cbq_dequeue(struct Qdisc *sch)
944 {
945 struct sk_buff *skb;
946 struct cbq_sched_data *q = qdisc_priv(sch);
947 psched_time_t now;
948 psched_tdiff_t incr;
949
950 now = psched_get_time();
951 incr = now - q->now_rt;
952
953 if (q->tx_class) {
954 psched_tdiff_t incr2;
955 /* Time integrator. We calculate EOS time
956 * by adding expected packet transmission time.
957 * If real time is greater, we warp artificial clock,
958 * so that:
959 *
960 * cbq_time = max(real_time, work);
961 */
962 incr2 = L2T(&q->link, q->tx_len);
963 q->now += incr2;
964 cbq_update(q);
965 if ((incr -= incr2) < 0)
966 incr = 0;
967 }
968 q->now += incr;
969 q->now_rt = now;
970
971 for (;;) {
972 q->wd_expires = 0;
973
974 skb = cbq_dequeue_1(sch);
975 if (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 NLA_PUT(skb, TCA_CBQ_RATE, sizeof(cl->R_tab->rate), &cl->R_tab->rate);
1430 return skb->len;
1431
1432 nla_put_failure:
1433 nlmsg_trim(skb, b);
1434 return -1;
1435 }
1436
1437 static int cbq_dump_lss(struct sk_buff *skb, struct cbq_class *cl)
1438 {
1439 unsigned char *b = skb_tail_pointer(skb);
1440 struct tc_cbq_lssopt opt;
1441
1442 opt.flags = 0;
1443 if (cl->borrow == NULL)
1444 opt.flags |= TCF_CBQ_LSS_BOUNDED;
1445 if (cl->share == NULL)
1446 opt.flags |= TCF_CBQ_LSS_ISOLATED;
1447 opt.ewma_log = cl->ewma_log;
1448 opt.level = cl->level;
1449 opt.avpkt = cl->avpkt;
1450 opt.maxidle = cl->maxidle;
1451 opt.minidle = (u32)(-cl->minidle);
1452 opt.offtime = cl->offtime;
1453 opt.change = ~0;
1454 NLA_PUT(skb, TCA_CBQ_LSSOPT, sizeof(opt), &opt);
1455 return skb->len;
1456
1457 nla_put_failure:
1458 nlmsg_trim(skb, b);
1459 return -1;
1460 }
1461
1462 static int cbq_dump_wrr(struct sk_buff *skb, struct cbq_class *cl)
1463 {
1464 unsigned char *b = skb_tail_pointer(skb);
1465 struct tc_cbq_wrropt opt;
1466
1467 opt.flags = 0;
1468 opt.allot = cl->allot;
1469 opt.priority = cl->priority + 1;
1470 opt.cpriority = cl->cpriority + 1;
1471 opt.weight = cl->weight;
1472 NLA_PUT(skb, TCA_CBQ_WRROPT, sizeof(opt), &opt);
1473 return skb->len;
1474
1475 nla_put_failure:
1476 nlmsg_trim(skb, b);
1477 return -1;
1478 }
1479
1480 static int cbq_dump_ovl(struct sk_buff *skb, struct cbq_class *cl)
1481 {
1482 unsigned char *b = skb_tail_pointer(skb);
1483 struct tc_cbq_ovl opt;
1484
1485 opt.strategy = cl->ovl_strategy;
1486 opt.priority2 = cl->priority2 + 1;
1487 opt.pad = 0;
1488 opt.penalty = cl->penalty;
1489 NLA_PUT(skb, TCA_CBQ_OVL_STRATEGY, sizeof(opt), &opt);
1490 return skb->len;
1491
1492 nla_put_failure:
1493 nlmsg_trim(skb, b);
1494 return -1;
1495 }
1496
1497 static int cbq_dump_fopt(struct sk_buff *skb, struct cbq_class *cl)
1498 {
1499 unsigned char *b = skb_tail_pointer(skb);
1500 struct tc_cbq_fopt opt;
1501
1502 if (cl->split || cl->defmap) {
1503 opt.split = cl->split ? cl->split->common.classid : 0;
1504 opt.defmap = cl->defmap;
1505 opt.defchange = ~0;
1506 NLA_PUT(skb, TCA_CBQ_FOPT, sizeof(opt), &opt);
1507 }
1508 return skb->len;
1509
1510 nla_put_failure:
1511 nlmsg_trim(skb, b);
1512 return -1;
1513 }
1514
1515 #ifdef CONFIG_NET_CLS_ACT
1516 static int cbq_dump_police(struct sk_buff *skb, struct cbq_class *cl)
1517 {
1518 unsigned char *b = skb_tail_pointer(skb);
1519 struct tc_cbq_police opt;
1520
1521 if (cl->police) {
1522 opt.police = cl->police;
1523 opt.__res1 = 0;
1524 opt.__res2 = 0;
1525 NLA_PUT(skb, TCA_CBQ_POLICE, sizeof(opt), &opt);
1526 }
1527 return skb->len;
1528
1529 nla_put_failure:
1530 nlmsg_trim(skb, b);
1531 return -1;
1532 }
1533 #endif
1534
1535 static int cbq_dump_attr(struct sk_buff *skb, struct cbq_class *cl)
1536 {
1537 if (cbq_dump_lss(skb, cl) < 0 ||
1538 cbq_dump_rate(skb, cl) < 0 ||
1539 cbq_dump_wrr(skb, cl) < 0 ||
1540 cbq_dump_ovl(skb, cl) < 0 ||
1541 #ifdef CONFIG_NET_CLS_ACT
1542 cbq_dump_police(skb, cl) < 0 ||
1543 #endif
1544 cbq_dump_fopt(skb, cl) < 0)
1545 return -1;
1546 return 0;
1547 }
1548
1549 static int cbq_dump(struct Qdisc *sch, struct sk_buff *skb)
1550 {
1551 struct cbq_sched_data *q = qdisc_priv(sch);
1552 struct nlattr *nest;
1553
1554 nest = nla_nest_start(skb, TCA_OPTIONS);
1555 if (nest == NULL)
1556 goto nla_put_failure;
1557 if (cbq_dump_attr(skb, &q->link) < 0)
1558 goto nla_put_failure;
1559 nla_nest_end(skb, nest);
1560 return skb->len;
1561
1562 nla_put_failure:
1563 nla_nest_cancel(skb, nest);
1564 return -1;
1565 }
1566
1567 static int
1568 cbq_dump_stats(struct Qdisc *sch, struct gnet_dump *d)
1569 {
1570 struct cbq_sched_data *q = qdisc_priv(sch);
1571
1572 q->link.xstats.avgidle = q->link.avgidle;
1573 return gnet_stats_copy_app(d, &q->link.xstats, sizeof(q->link.xstats));
1574 }
1575
1576 static int
1577 cbq_dump_class(struct Qdisc *sch, unsigned long arg,
1578 struct sk_buff *skb, struct tcmsg *tcm)
1579 {
1580 struct cbq_class *cl = (struct cbq_class *)arg;
1581 struct nlattr *nest;
1582
1583 if (cl->tparent)
1584 tcm->tcm_parent = cl->tparent->common.classid;
1585 else
1586 tcm->tcm_parent = TC_H_ROOT;
1587 tcm->tcm_handle = cl->common.classid;
1588 tcm->tcm_info = cl->q->handle;
1589
1590 nest = nla_nest_start(skb, TCA_OPTIONS);
1591 if (nest == NULL)
1592 goto nla_put_failure;
1593 if (cbq_dump_attr(skb, cl) < 0)
1594 goto nla_put_failure;
1595 nla_nest_end(skb, nest);
1596 return skb->len;
1597
1598 nla_put_failure:
1599 nla_nest_cancel(skb, nest);
1600 return -1;
1601 }
1602
1603 static int
1604 cbq_dump_class_stats(struct Qdisc *sch, unsigned long arg,
1605 struct gnet_dump *d)
1606 {
1607 struct cbq_sched_data *q = qdisc_priv(sch);
1608 struct cbq_class *cl = (struct cbq_class *)arg;
1609
1610 cl->qstats.qlen = cl->q->q.qlen;
1611 cl->xstats.avgidle = cl->avgidle;
1612 cl->xstats.undertime = 0;
1613
1614 if (cl->undertime != PSCHED_PASTPERFECT)
1615 cl->xstats.undertime = cl->undertime - q->now;
1616
1617 if (gnet_stats_copy_basic(d, &cl->bstats) < 0 ||
1618 gnet_stats_copy_rate_est(d, &cl->bstats, &cl->rate_est) < 0 ||
1619 gnet_stats_copy_queue(d, &cl->qstats) < 0)
1620 return -1;
1621
1622 return gnet_stats_copy_app(d, &cl->xstats, sizeof(cl->xstats));
1623 }
1624
1625 static int cbq_graft(struct Qdisc *sch, unsigned long arg, struct Qdisc *new,
1626 struct Qdisc **old)
1627 {
1628 struct cbq_class *cl = (struct cbq_class *)arg;
1629
1630 if (new == NULL) {
1631 new = qdisc_create_dflt(sch->dev_queue,
1632 &pfifo_qdisc_ops, cl->common.classid);
1633 if (new == NULL)
1634 return -ENOBUFS;
1635 } else {
1636 #ifdef CONFIG_NET_CLS_ACT
1637 if (cl->police == TC_POLICE_RECLASSIFY)
1638 new->reshape_fail = cbq_reshape_fail;
1639 #endif
1640 }
1641 sch_tree_lock(sch);
1642 *old = cl->q;
1643 cl->q = new;
1644 qdisc_tree_decrease_qlen(*old, (*old)->q.qlen);
1645 qdisc_reset(*old);
1646 sch_tree_unlock(sch);
1647
1648 return 0;
1649 }
1650
1651 static struct Qdisc *cbq_leaf(struct Qdisc *sch, unsigned long arg)
1652 {
1653 struct cbq_class *cl = (struct cbq_class *)arg;
1654
1655 return cl->q;
1656 }
1657
1658 static void cbq_qlen_notify(struct Qdisc *sch, unsigned long arg)
1659 {
1660 struct cbq_class *cl = (struct cbq_class *)arg;
1661
1662 if (cl->q->q.qlen == 0)
1663 cbq_deactivate_class(cl);
1664 }
1665
1666 static unsigned long cbq_get(struct Qdisc *sch, u32 classid)
1667 {
1668 struct cbq_sched_data *q = qdisc_priv(sch);
1669 struct cbq_class *cl = cbq_class_lookup(q, classid);
1670
1671 if (cl) {
1672 cl->refcnt++;
1673 return (unsigned long)cl;
1674 }
1675 return 0;
1676 }
1677
1678 static void cbq_destroy_class(struct Qdisc *sch, struct cbq_class *cl)
1679 {
1680 struct cbq_sched_data *q = qdisc_priv(sch);
1681
1682 WARN_ON(cl->filters);
1683
1684 tcf_destroy_chain(&cl->filter_list);
1685 qdisc_destroy(cl->q);
1686 qdisc_put_rtab(cl->R_tab);
1687 gen_kill_estimator(&cl->bstats, &cl->rate_est);
1688 if (cl != &q->link)
1689 kfree(cl);
1690 }
1691
1692 static void cbq_destroy(struct Qdisc *sch)
1693 {
1694 struct cbq_sched_data *q = qdisc_priv(sch);
1695 struct hlist_node *n, *next;
1696 struct cbq_class *cl;
1697 unsigned int h;
1698
1699 #ifdef CONFIG_NET_CLS_ACT
1700 q->rx_class = NULL;
1701 #endif
1702 /*
1703 * Filters must be destroyed first because we don't destroy the
1704 * classes from root to leafs which means that filters can still
1705 * be bound to classes which have been destroyed already. --TGR '04
1706 */
1707 for (h = 0; h < q->clhash.hashsize; h++) {
1708 hlist_for_each_entry(cl, n, &q->clhash.hash[h], common.hnode)
1709 tcf_destroy_chain(&cl->filter_list);
1710 }
1711 for (h = 0; h < q->clhash.hashsize; h++) {
1712 hlist_for_each_entry_safe(cl, n, next, &q->clhash.hash[h],
1713 common.hnode)
1714 cbq_destroy_class(sch, cl);
1715 }
1716 qdisc_class_hash_destroy(&q->clhash);
1717 }
1718
1719 static void cbq_put(struct Qdisc *sch, unsigned long arg)
1720 {
1721 struct cbq_class *cl = (struct cbq_class *)arg;
1722
1723 if (--cl->refcnt == 0) {
1724 #ifdef CONFIG_NET_CLS_ACT
1725 spinlock_t *root_lock = qdisc_root_sleeping_lock(sch);
1726 struct cbq_sched_data *q = qdisc_priv(sch);
1727
1728 spin_lock_bh(root_lock);
1729 if (q->rx_class == cl)
1730 q->rx_class = NULL;
1731 spin_unlock_bh(root_lock);
1732 #endif
1733
1734 cbq_destroy_class(sch, cl);
1735 }
1736 }
1737
1738 static int
1739 cbq_change_class(struct Qdisc *sch, u32 classid, u32 parentid, struct nlattr **tca,
1740 unsigned long *arg)
1741 {
1742 int err;
1743 struct cbq_sched_data *q = qdisc_priv(sch);
1744 struct cbq_class *cl = (struct cbq_class *)*arg;
1745 struct nlattr *opt = tca[TCA_OPTIONS];
1746 struct nlattr *tb[TCA_CBQ_MAX + 1];
1747 struct cbq_class *parent;
1748 struct qdisc_rate_table *rtab = NULL;
1749
1750 if (opt == NULL)
1751 return -EINVAL;
1752
1753 err = nla_parse_nested(tb, TCA_CBQ_MAX, opt, cbq_policy);
1754 if (err < 0)
1755 return err;
1756
1757 if (cl) {
1758 /* Check parent */
1759 if (parentid) {
1760 if (cl->tparent &&
1761 cl->tparent->common.classid != parentid)
1762 return -EINVAL;
1763 if (!cl->tparent && parentid != TC_H_ROOT)
1764 return -EINVAL;
1765 }
1766
1767 if (tb[TCA_CBQ_RATE]) {
1768 rtab = qdisc_get_rtab(nla_data(tb[TCA_CBQ_RATE]),
1769 tb[TCA_CBQ_RTAB]);
1770 if (rtab == NULL)
1771 return -EINVAL;
1772 }
1773
1774 if (tca[TCA_RATE]) {
1775 err = gen_replace_estimator(&cl->bstats, &cl->rate_est,
1776 qdisc_root_sleeping_lock(sch),
1777 tca[TCA_RATE]);
1778 if (err) {
1779 if (rtab)
1780 qdisc_put_rtab(rtab);
1781 return err;
1782 }
1783 }
1784
1785 /* Change class parameters */
1786 sch_tree_lock(sch);
1787
1788 if (cl->next_alive != NULL)
1789 cbq_deactivate_class(cl);
1790
1791 if (rtab) {
1792 qdisc_put_rtab(cl->R_tab);
1793 cl->R_tab = rtab;
1794 }
1795
1796 if (tb[TCA_CBQ_LSSOPT])
1797 cbq_set_lss(cl, nla_data(tb[TCA_CBQ_LSSOPT]));
1798
1799 if (tb[TCA_CBQ_WRROPT]) {
1800 cbq_rmprio(q, cl);
1801 cbq_set_wrr(cl, nla_data(tb[TCA_CBQ_WRROPT]));
1802 }
1803
1804 if (tb[TCA_CBQ_OVL_STRATEGY])
1805 cbq_set_overlimit(cl, nla_data(tb[TCA_CBQ_OVL_STRATEGY]));
1806
1807 #ifdef CONFIG_NET_CLS_ACT
1808 if (tb[TCA_CBQ_POLICE])
1809 cbq_set_police(cl, nla_data(tb[TCA_CBQ_POLICE]));
1810 #endif
1811
1812 if (tb[TCA_CBQ_FOPT])
1813 cbq_set_fopt(cl, nla_data(tb[TCA_CBQ_FOPT]));
1814
1815 if (cl->q->q.qlen)
1816 cbq_activate_class(cl);
1817
1818 sch_tree_unlock(sch);
1819
1820 return 0;
1821 }
1822
1823 if (parentid == TC_H_ROOT)
1824 return -EINVAL;
1825
1826 if (tb[TCA_CBQ_WRROPT] == NULL || tb[TCA_CBQ_RATE] == NULL ||
1827 tb[TCA_CBQ_LSSOPT] == NULL)
1828 return -EINVAL;
1829
1830 rtab = qdisc_get_rtab(nla_data(tb[TCA_CBQ_RATE]), tb[TCA_CBQ_RTAB]);
1831 if (rtab == NULL)
1832 return -EINVAL;
1833
1834 if (classid) {
1835 err = -EINVAL;
1836 if (TC_H_MAJ(classid ^ sch->handle) ||
1837 cbq_class_lookup(q, classid))
1838 goto failure;
1839 } else {
1840 int i;
1841 classid = TC_H_MAKE(sch->handle, 0x8000);
1842
1843 for (i = 0; i < 0x8000; i++) {
1844 if (++q->hgenerator >= 0x8000)
1845 q->hgenerator = 1;
1846 if (cbq_class_lookup(q, classid|q->hgenerator) == NULL)
1847 break;
1848 }
1849 err = -ENOSR;
1850 if (i >= 0x8000)
1851 goto failure;
1852 classid = classid|q->hgenerator;
1853 }
1854
1855 parent = &q->link;
1856 if (parentid) {
1857 parent = cbq_class_lookup(q, parentid);
1858 err = -EINVAL;
1859 if (parent == NULL)
1860 goto failure;
1861 }
1862
1863 err = -ENOBUFS;
1864 cl = kzalloc(sizeof(*cl), GFP_KERNEL);
1865 if (cl == NULL)
1866 goto failure;
1867
1868 if (tca[TCA_RATE]) {
1869 err = gen_new_estimator(&cl->bstats, &cl->rate_est,
1870 qdisc_root_sleeping_lock(sch),
1871 tca[TCA_RATE]);
1872 if (err) {
1873 kfree(cl);
1874 goto failure;
1875 }
1876 }
1877
1878 cl->R_tab = rtab;
1879 rtab = NULL;
1880 cl->refcnt = 1;
1881 cl->q = qdisc_create_dflt(sch->dev_queue, &pfifo_qdisc_ops, classid);
1882 if (!cl->q)
1883 cl->q = &noop_qdisc;
1884 cl->common.classid = classid;
1885 cl->tparent = parent;
1886 cl->qdisc = sch;
1887 cl->allot = parent->allot;
1888 cl->quantum = cl->allot;
1889 cl->weight = cl->R_tab->rate.rate;
1890
1891 sch_tree_lock(sch);
1892 cbq_link_class(cl);
1893 cl->borrow = cl->tparent;
1894 if (cl->tparent != &q->link)
1895 cl->share = cl->tparent;
1896 cbq_adjust_levels(parent);
1897 cl->minidle = -0x7FFFFFFF;
1898 cbq_set_lss(cl, nla_data(tb[TCA_CBQ_LSSOPT]));
1899 cbq_set_wrr(cl, nla_data(tb[TCA_CBQ_WRROPT]));
1900 if (cl->ewma_log == 0)
1901 cl->ewma_log = q->link.ewma_log;
1902 if (cl->maxidle == 0)
1903 cl->maxidle = q->link.maxidle;
1904 if (cl->avpkt == 0)
1905 cl->avpkt = q->link.avpkt;
1906 cl->overlimit = cbq_ovl_classic;
1907 if (tb[TCA_CBQ_OVL_STRATEGY])
1908 cbq_set_overlimit(cl, nla_data(tb[TCA_CBQ_OVL_STRATEGY]));
1909 #ifdef CONFIG_NET_CLS_ACT
1910 if (tb[TCA_CBQ_POLICE])
1911 cbq_set_police(cl, nla_data(tb[TCA_CBQ_POLICE]));
1912 #endif
1913 if (tb[TCA_CBQ_FOPT])
1914 cbq_set_fopt(cl, nla_data(tb[TCA_CBQ_FOPT]));
1915 sch_tree_unlock(sch);
1916
1917 qdisc_class_hash_grow(sch, &q->clhash);
1918
1919 *arg = (unsigned long)cl;
1920 return 0;
1921
1922 failure:
1923 qdisc_put_rtab(rtab);
1924 return err;
1925 }
1926
1927 static int cbq_delete(struct Qdisc *sch, unsigned long arg)
1928 {
1929 struct cbq_sched_data *q = qdisc_priv(sch);
1930 struct cbq_class *cl = (struct cbq_class *)arg;
1931 unsigned int qlen;
1932
1933 if (cl->filters || cl->children || cl == &q->link)
1934 return -EBUSY;
1935
1936 sch_tree_lock(sch);
1937
1938 qlen = cl->q->q.qlen;
1939 qdisc_reset(cl->q);
1940 qdisc_tree_decrease_qlen(cl->q, qlen);
1941
1942 if (cl->next_alive)
1943 cbq_deactivate_class(cl);
1944
1945 if (q->tx_borrowed == cl)
1946 q->tx_borrowed = q->tx_class;
1947 if (q->tx_class == cl) {
1948 q->tx_class = NULL;
1949 q->tx_borrowed = NULL;
1950 }
1951 #ifdef CONFIG_NET_CLS_ACT
1952 if (q->rx_class == cl)
1953 q->rx_class = NULL;
1954 #endif
1955
1956 cbq_unlink_class(cl);
1957 cbq_adjust_levels(cl->tparent);
1958 cl->defmap = 0;
1959 cbq_sync_defmap(cl);
1960
1961 cbq_rmprio(q, cl);
1962 sch_tree_unlock(sch);
1963
1964 BUG_ON(--cl->refcnt == 0);
1965 /*
1966 * This shouldn't happen: we "hold" one cops->get() when called
1967 * from tc_ctl_tclass; the destroy method is done from cops->put().
1968 */
1969
1970 return 0;
1971 }
1972
1973 static struct tcf_proto **cbq_find_tcf(struct Qdisc *sch, unsigned long arg)
1974 {
1975 struct cbq_sched_data *q = qdisc_priv(sch);
1976 struct cbq_class *cl = (struct cbq_class *)arg;
1977
1978 if (cl == NULL)
1979 cl = &q->link;
1980
1981 return &cl->filter_list;
1982 }
1983
1984 static unsigned long cbq_bind_filter(struct Qdisc *sch, unsigned long parent,
1985 u32 classid)
1986 {
1987 struct cbq_sched_data *q = qdisc_priv(sch);
1988 struct cbq_class *p = (struct cbq_class *)parent;
1989 struct cbq_class *cl = cbq_class_lookup(q, classid);
1990
1991 if (cl) {
1992 if (p && p->level <= cl->level)
1993 return 0;
1994 cl->filters++;
1995 return (unsigned long)cl;
1996 }
1997 return 0;
1998 }
1999
2000 static void cbq_unbind_filter(struct Qdisc *sch, unsigned long arg)
2001 {
2002 struct cbq_class *cl = (struct cbq_class *)arg;
2003
2004 cl->filters--;
2005 }
2006
2007 static void cbq_walk(struct Qdisc *sch, struct qdisc_walker *arg)
2008 {
2009 struct cbq_sched_data *q = qdisc_priv(sch);
2010 struct cbq_class *cl;
2011 struct hlist_node *n;
2012 unsigned int h;
2013
2014 if (arg->stop)
2015 return;
2016
2017 for (h = 0; h < q->clhash.hashsize; h++) {
2018 hlist_for_each_entry(cl, n, &q->clhash.hash[h], common.hnode) {
2019 if (arg->count < arg->skip) {
2020 arg->count++;
2021 continue;
2022 }
2023 if (arg->fn(sch, (unsigned long)cl, arg) < 0) {
2024 arg->stop = 1;
2025 return;
2026 }
2027 arg->count++;
2028 }
2029 }
2030 }
2031
2032 static const struct Qdisc_class_ops cbq_class_ops = {
2033 .graft = cbq_graft,
2034 .leaf = cbq_leaf,
2035 .qlen_notify = cbq_qlen_notify,
2036 .get = cbq_get,
2037 .put = cbq_put,
2038 .change = cbq_change_class,
2039 .delete = cbq_delete,
2040 .walk = cbq_walk,
2041 .tcf_chain = cbq_find_tcf,
2042 .bind_tcf = cbq_bind_filter,
2043 .unbind_tcf = cbq_unbind_filter,
2044 .dump = cbq_dump_class,
2045 .dump_stats = cbq_dump_class_stats,
2046 };
2047
2048 static struct Qdisc_ops cbq_qdisc_ops __read_mostly = {
2049 .next = NULL,
2050 .cl_ops = &cbq_class_ops,
2051 .id = "cbq",
2052 .priv_size = sizeof(struct cbq_sched_data),
2053 .enqueue = cbq_enqueue,
2054 .dequeue = cbq_dequeue,
2055 .peek = qdisc_peek_dequeued,
2056 .drop = cbq_drop,
2057 .init = cbq_init,
2058 .reset = cbq_reset,
2059 .destroy = cbq_destroy,
2060 .change = NULL,
2061 .dump = cbq_dump,
2062 .dump_stats = cbq_dump_stats,
2063 .owner = THIS_MODULE,
2064 };
2065
2066 static int __init cbq_module_init(void)
2067 {
2068 return register_qdisc(&cbq_qdisc_ops);
2069 }
2070 static void __exit cbq_module_exit(void)
2071 {
2072 unregister_qdisc(&cbq_qdisc_ops);
2073 }
2074 module_init(cbq_module_init)
2075 module_exit(cbq_module_exit)
2076 MODULE_LICENSE("GPL");
Linux 2.6 ibm-acpi/thinkpad-acpi driver git tree