?  search:
summary | log | graphiclog1 | graphiclog2 | commit | commitdiff | tree | refs | edit | fork
blame | history | raw | HEAD
x86: mtrr_cleanup safe to get more spare regs now
[linux-2.6/mini2440.git] / net / sched / sch_cbq.c
blob8b06fa9004828c937e359df4c3c0d0c0bfa0ecf3
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/types.h>
15 #include <linux/kernel.h>
16 #include <linux/string.h>
17 #include <linux/errno.h>
18 #include <linux/skbuff.h>
19 #include <net/netlink.h>
20 #include <net/pkt_sched.h>
21
22
23 /* Class-Based Queueing (CBQ) algorithm.
24 =======================================
25
26 Sources: [1] Sally Floyd and Van Jacobson, "Link-sharing and Resource
27 Management Models for Packet Networks",
28 IEEE/ACM Transactions on Networking, Vol.3, No.4, 1995
29
30 [2] Sally Floyd, "Notes on CBQ and Guaranteed Service", 1995
31
32 [3] Sally Floyd, "Notes on Class-Based Queueing: Setting
33 Parameters", 1996
34
35 [4] Sally Floyd and Michael Speer, "Experimental Results
36 for Class-Based Queueing", 1998, not published.
37
38 -----------------------------------------------------------------------
39
40 Algorithm skeleton was taken from NS simulator cbq.cc.
41 If someone wants to check this code against the LBL version,
42 he should take into account that ONLY the skeleton was borrowed,
43 the implementation is different. Particularly:
44
45 --- The WRR algorithm is different. Our version looks more
46 reasonable (I hope) and works when quanta are allowed to be
47 less than MTU, which is always the case when real time classes
48 have small rates. Note, that the statement of [3] is
49 incomplete, delay may actually be estimated even if class
50 per-round allotment is less than MTU. Namely, if per-round
51 allotment is W*r_i, and r_1+...+r_k = r < 1
52
53 delay_i <= ([MTU/(W*r_i)]*W*r + W*r + k*MTU)/B
54
55 In the worst case we have IntServ estimate with D = W*r+k*MTU
56 and C = MTU*r. The proof (if correct at all) is trivial.
57
58
59 --- It seems that cbq-2.0 is not very accurate. At least, I cannot
60 interpret some places, which look like wrong translations
61 from NS. Anyone is advised to find these differences
62 and explain to me, why I am wrong 8).
63
64 --- Linux has no EOI event, so that we cannot estimate true class
65 idle time. Workaround is to consider the next dequeue event
66 as sign that previous packet is finished. This is wrong because of
67 internal device queueing, but on a permanently loaded link it is true.
68 Moreover, combined with clock integrator, this scheme looks
69 very close to an ideal solution. */
70
71 struct cbq_sched_data;
72
73
74 struct cbq_class
75 {
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 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 {
146 struct Qdisc_class_hash clhash; /* Hash table of all classes */
147 int nclasses[TC_CBQ_MAXPRIO+1];
148 unsigned quanta[TC_CBQ_MAXPRIO+1];
149
150 struct cbq_class link;
151
152 unsigned activemask;
153 struct cbq_class *active[TC_CBQ_MAXPRIO+1]; /* List of all classes
154 with backlog */
155
156 #ifdef CONFIG_NET_CLS_ACT
157 struct cbq_class *rx_class;
158 #endif
159 struct cbq_class *tx_class;
160 struct cbq_class *tx_borrowed;
161 int tx_len;
162 psched_time_t now; /* Cached timestamp */
163 psched_time_t now_rt; /* Cached real time */
164 unsigned pmask;
165
166 struct hrtimer delay_timer;
167 struct qdisc_watchdog watchdog; /* Watchdog timer,
168 started when CBQ has
169 backlog, but cannot
170 transmit just now */
171 psched_tdiff_t wd_expires;
172 int toplevel;
173 u32 hgenerator;
174 };
175
176
177 #define L2T(cl,len) qdisc_l2t((cl)->R_tab,len)
178
179 static __inline__ struct cbq_class *
180 cbq_class_lookup(struct cbq_sched_data *q, u32 classid)
181 {
182 struct Qdisc_class_common *clc;
183
184 clc = qdisc_class_find(&q->clhash, classid);
185 if (clc == NULL)
186 return NULL;
187 return container_of(clc, struct cbq_class, common);
188 }
189
190 #ifdef CONFIG_NET_CLS_ACT
191
192 static struct cbq_class *
193 cbq_reclassify(struct sk_buff *skb, struct cbq_class *this)
194 {
195 struct cbq_class *cl, *new;
196
197 for (cl = this->tparent; cl; cl = cl->tparent)
198 if ((new = cl->defaults[TC_PRIO_BESTEFFORT]) != 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 if ((cl = (void*)res.class) == NULL) {
246 if (TC_H_MAJ(res.classid))
247 cl = cbq_class_lookup(q, res.classid);
248 else if ((cl = defmap[res.classid&TC_PRIO_MAX]) == NULL)
249 cl = defmap[TC_PRIO_BESTEFFORT];
250
251 if (cl == NULL || cl->level >= head->level)
252 goto fallback;
253 }
254
255 #ifdef CONFIG_NET_CLS_ACT
256 switch (result) {
257 case TC_ACT_QUEUED:
258 case TC_ACT_STOLEN:
259 *qerr = NET_XMIT_SUCCESS | __NET_XMIT_STOLEN;
260 case TC_ACT_SHOT:
261 return NULL;
262 case TC_ACT_RECLASSIFY:
263 return cbq_reclassify(skb, cl);
264 }
265 #endif
266 if (cl->level == 0)
267 return cl;
268
269 /*
270 * Step 3+n. If classifier selected a link sharing class,
271 * apply agency specific classifier.
272 * Repeat this procdure until we hit a leaf node.
273 */
274 head = cl;
275 }
276
277 fallback:
278 cl = head;
279
280 /*
281 * Step 4. No success...
282 */
283 if (TC_H_MAJ(prio) == 0 &&
284 !(cl = head->defaults[prio&TC_PRIO_MAX]) &&
285 !(cl = head->defaults[TC_PRIO_BESTEFFORT]))
286 return head;
287
288 return cl;
289 }
290
291 /*
292 A packet has just been enqueued on the empty class.
293 cbq_activate_class adds it to the tail of active class list
294 of its priority band.
295 */
296
297 static __inline__ void cbq_activate_class(struct cbq_class *cl)
298 {
299 struct cbq_sched_data *q = qdisc_priv(cl->qdisc);
300 int prio = cl->cpriority;
301 struct cbq_class *cl_tail;
302
303 cl_tail = q->active[prio];
304 q->active[prio] = cl;
305
306 if (cl_tail != NULL) {
307 cl->next_alive = cl_tail->next_alive;
308 cl_tail->next_alive = cl;
309 } else {
310 cl->next_alive = cl;
311 q->activemask |= (1<<prio);
312 }
313 }
314
315 /*
316 Unlink class from active chain.
317 Note that this same procedure is done directly in cbq_dequeue*
318 during round-robin procedure.
319 */
320
321 static void cbq_deactivate_class(struct cbq_class *this)
322 {
323 struct cbq_sched_data *q = qdisc_priv(this->qdisc);
324 int prio = this->cpriority;
325 struct cbq_class *cl;
326 struct cbq_class *cl_prev = q->active[prio];
327
328 do {
329 cl = cl_prev->next_alive;
330 if (cl == this) {
331 cl_prev->next_alive = cl->next_alive;
332 cl->next_alive = NULL;
333
334 if (cl == q->active[prio]) {
335 q->active[prio] = cl_prev;
336 if (cl == q->active[prio]) {
337 q->active[prio] = NULL;
338 q->activemask &= ~(1<<prio);
339 return;
340 }
341 }
342 return;
343 }
344 } while ((cl_prev = cl) != q->active[prio]);
345 }
346
347 static void
348 cbq_mark_toplevel(struct cbq_sched_data *q, struct cbq_class *cl)
349 {
350 int toplevel = q->toplevel;
351
352 if (toplevel > cl->level && !(cl->q->flags&TCQ_F_THROTTLED)) {
353 psched_time_t now;
354 psched_tdiff_t incr;
355
356 now = psched_get_time();
357 incr = now - q->now_rt;
358 now = q->now + incr;
359
360 do {
361 if (cl->undertime < now) {
362 q->toplevel = cl->level;
363 return;
364 }
365 } while ((cl=cl->borrow) != NULL && toplevel > cl->level);
366 }
367 }
368
369 static int
370 cbq_enqueue(struct sk_buff *skb, struct Qdisc *sch)
371 {
372 struct cbq_sched_data *q = qdisc_priv(sch);
373 int uninitialized_var(ret);
374 struct cbq_class *cl = cbq_classify(skb, sch, &ret);
375
376 #ifdef CONFIG_NET_CLS_ACT
377 q->rx_class = cl;
378 #endif
379 if (cl == NULL) {
380 if (ret & __NET_XMIT_BYPASS)
381 sch->qstats.drops++;
382 kfree_skb(skb);
383 return ret;
384 }
385
386 #ifdef CONFIG_NET_CLS_ACT
387 cl->q->__parent = sch;
388 #endif
389 ret = qdisc_enqueue(skb, cl->q);
390 if (ret == NET_XMIT_SUCCESS) {
391 sch->q.qlen++;
392 sch->bstats.packets++;
393 sch->bstats.bytes += qdisc_pkt_len(skb);
394 cbq_mark_toplevel(q, cl);
395 if (!cl->next_alive)
396 cbq_activate_class(cl);
397 return ret;
398 }
399
400 if (net_xmit_drop_count(ret)) {
401 sch->qstats.drops++;
402 cbq_mark_toplevel(q, cl);
403 cl->qstats.drops++;
404 }
405 return ret;
406 }
407
408 static int
409 cbq_requeue(struct sk_buff *skb, struct Qdisc *sch)
410 {
411 struct cbq_sched_data *q = qdisc_priv(sch);
412 struct cbq_class *cl;
413 int ret;
414
415 if ((cl = q->tx_class) == NULL) {
416 kfree_skb(skb);
417 sch->qstats.drops++;
418 return NET_XMIT_CN;
419 }
420 q->tx_class = NULL;
421
422 cbq_mark_toplevel(q, cl);
423
424 #ifdef CONFIG_NET_CLS_ACT
425 q->rx_class = cl;
426 cl->q->__parent = sch;
427 #endif
428 if ((ret = cl->q->ops->requeue(skb, cl->q)) == 0) {
429 sch->q.qlen++;
430 sch->qstats.requeues++;
431 if (!cl->next_alive)
432 cbq_activate_class(cl);
433 return 0;
434 }
435 if (net_xmit_drop_count(ret)) {
436 sch->qstats.drops++;
437 cl->qstats.drops++;
438 }
439 return ret;
440 }
441
442 /* Overlimit actions */
443
444 /* TC_CBQ_OVL_CLASSIC: (default) penalize leaf class by adding offtime */
445
446 static void cbq_ovl_classic(struct cbq_class *cl)
447 {
448 struct cbq_sched_data *q = qdisc_priv(cl->qdisc);
449 psched_tdiff_t delay = cl->undertime - q->now;
450
451 if (!cl->delayed) {
452 delay += cl->offtime;
453
454 /*
455 Class goes to sleep, so that it will have no
456 chance to work avgidle. Let's forgive it 8)
457
458 BTW cbq-2.0 has a crap in this
459 place, apparently they forgot to shift it by cl->ewma_log.
460 */
461 if (cl->avgidle < 0)
462 delay -= (-cl->avgidle) - ((-cl->avgidle) >> cl->ewma_log);
463 if (cl->avgidle < cl->minidle)
464 cl->avgidle = cl->minidle;
465 if (delay <= 0)
466 delay = 1;
467 cl->undertime = q->now + delay;
468
469 cl->xstats.overactions++;
470 cl->delayed = 1;
471 }
472 if (q->wd_expires == 0 || q->wd_expires > delay)
473 q->wd_expires = delay;
474
475 /* Dirty work! We must schedule wakeups based on
476 real available rate, rather than leaf rate,
477 which may be tiny (even zero).
478 */
479 if (q->toplevel == TC_CBQ_MAXLEVEL) {
480 struct cbq_class *b;
481 psched_tdiff_t base_delay = q->wd_expires;
482
483 for (b = cl->borrow; b; b = b->borrow) {
484 delay = b->undertime - q->now;
485 if (delay < base_delay) {
486 if (delay <= 0)
487 delay = 1;
488 base_delay = delay;
489 }
490 }
491
492 q->wd_expires = base_delay;
493 }
494 }
495
496 /* TC_CBQ_OVL_RCLASSIC: penalize by offtime classes in hierarchy, when
497 they go overlimit
498 */
499
500 static void cbq_ovl_rclassic(struct cbq_class *cl)
501 {
502 struct cbq_sched_data *q = qdisc_priv(cl->qdisc);
503 struct cbq_class *this = cl;
504
505 do {
506 if (cl->level > q->toplevel) {
507 cl = NULL;
508 break;
509 }
510 } while ((cl = cl->borrow) != NULL);
511
512 if (cl == NULL)
513 cl = this;
514 cbq_ovl_classic(cl);
515 }
516
517 /* TC_CBQ_OVL_DELAY: delay until it will go to underlimit */
518
519 static void cbq_ovl_delay(struct cbq_class *cl)
520 {
521 struct cbq_sched_data *q = qdisc_priv(cl->qdisc);
522 psched_tdiff_t delay = cl->undertime - q->now;
523
524 if (test_bit(__QDISC_STATE_DEACTIVATED,
525 &qdisc_root_sleeping(cl->qdisc)->state))
526 return;
527
528 if (!cl->delayed) {
529 psched_time_t sched = q->now;
530 ktime_t expires;
531
532 delay += cl->offtime;
533 if (cl->avgidle < 0)
534 delay -= (-cl->avgidle) - ((-cl->avgidle) >> cl->ewma_log);
535 if (cl->avgidle < cl->minidle)
536 cl->avgidle = cl->minidle;
537 cl->undertime = q->now + delay;
538
539 if (delay > 0) {
540 sched += delay + cl->penalty;
541 cl->penalized = sched;
542 cl->cpriority = TC_CBQ_MAXPRIO;
543 q->pmask |= (1<<TC_CBQ_MAXPRIO);
544
545 expires = ktime_set(0, 0);
546 expires = ktime_add_ns(expires, PSCHED_US2NS(sched));
547 if (hrtimer_try_to_cancel(&q->delay_timer) &&
548 ktime_to_ns(ktime_sub(q->delay_timer.expires,
549 expires)) > 0)
550 q->delay_timer.expires = expires;
551 hrtimer_restart(&q->delay_timer);
552 cl->delayed = 1;
553 cl->xstats.overactions++;
554 return;
555 }
556 delay = 1;
557 }
558 if (q->wd_expires == 0 || q->wd_expires > delay)
559 q->wd_expires = delay;
560 }
561
562 /* TC_CBQ_OVL_LOWPRIO: penalize class by lowering its priority band */
563
564 static void cbq_ovl_lowprio(struct cbq_class *cl)
565 {
566 struct cbq_sched_data *q = qdisc_priv(cl->qdisc);
567
568 cl->penalized = q->now + cl->penalty;
569
570 if (cl->cpriority != cl->priority2) {
571 cl->cpriority = cl->priority2;
572 q->pmask |= (1<<cl->cpriority);
573 cl->xstats.overactions++;
574 }
575 cbq_ovl_classic(cl);
576 }
577
578 /* TC_CBQ_OVL_DROP: penalize class by dropping */
579
580 static void cbq_ovl_drop(struct cbq_class *cl)
581 {
582 if (cl->q->ops->drop)
583 if (cl->q->ops->drop(cl->q))
584 cl->qdisc->q.qlen--;
585 cl->xstats.overactions++;
586 cbq_ovl_classic(cl);
587 }
588
589 static psched_tdiff_t cbq_undelay_prio(struct cbq_sched_data *q, int prio,
590 psched_time_t now)
591 {
592 struct cbq_class *cl;
593 struct cbq_class *cl_prev = q->active[prio];
594 psched_time_t sched = now;
595
596 if (cl_prev == NULL)
597 return 0;
598
599 do {
600 cl = cl_prev->next_alive;
601 if (now - cl->penalized > 0) {
602 cl_prev->next_alive = cl->next_alive;
603 cl->next_alive = NULL;
604 cl->cpriority = cl->priority;
605 cl->delayed = 0;
606 cbq_activate_class(cl);
607
608 if (cl == q->active[prio]) {
609 q->active[prio] = cl_prev;
610 if (cl == q->active[prio]) {
611 q->active[prio] = NULL;
612 return 0;
613 }
614 }
615
616 cl = cl_prev->next_alive;
617 } else if (sched - cl->penalized > 0)
618 sched = cl->penalized;
619 } while ((cl_prev = cl) != q->active[prio]);
620
621 return sched - now;
622 }
623
624 static enum hrtimer_restart cbq_undelay(struct hrtimer *timer)
625 {
626 struct cbq_sched_data *q = container_of(timer, struct cbq_sched_data,
627 delay_timer);
628 struct Qdisc *sch = q->watchdog.qdisc;
629 psched_time_t now;
630 psched_tdiff_t delay = 0;
631 unsigned pmask;
632
633 now = psched_get_time();
634
635 pmask = q->pmask;
636 q->pmask = 0;
637
638 while (pmask) {
639 int prio = ffz(~pmask);
640 psched_tdiff_t tmp;
641
642 pmask &= ~(1<<prio);
643
644 tmp = cbq_undelay_prio(q, prio, now);
645 if (tmp > 0) {
646 q->pmask |= 1<<prio;
647 if (tmp < delay || delay == 0)
648 delay = tmp;
649 }
650 }
651
652 if (delay) {
653 ktime_t time;
654
655 time = ktime_set(0, 0);
656 time = ktime_add_ns(time, PSCHED_US2NS(now + delay));
657 hrtimer_start(&q->delay_timer, time, HRTIMER_MODE_ABS);
658 }
659
660 sch->flags &= ~TCQ_F_THROTTLED;
661 __netif_schedule(qdisc_root(sch));
662 return HRTIMER_NORESTART;
663 }
664
665 #ifdef CONFIG_NET_CLS_ACT
666 static int cbq_reshape_fail(struct sk_buff *skb, struct Qdisc *child)
667 {
668 struct Qdisc *sch = child->__parent;
669 struct cbq_sched_data *q = qdisc_priv(sch);
670 struct cbq_class *cl = q->rx_class;
671
672 q->rx_class = NULL;
673
674 if (cl && (cl = cbq_reclassify(skb, cl)) != NULL) {
675 int ret;
676
677 cbq_mark_toplevel(q, cl);
678
679 q->rx_class = cl;
680 cl->q->__parent = sch;
681
682 ret = qdisc_enqueue(skb, cl->q);
683 if (ret == NET_XMIT_SUCCESS) {
684 sch->q.qlen++;
685 sch->bstats.packets++;
686 sch->bstats.bytes += qdisc_pkt_len(skb);
687 if (!cl->next_alive)
688 cbq_activate_class(cl);
689 return 0;
690 }
691 if (net_xmit_drop_count(ret))
692 sch->qstats.drops++;
693 return 0;
694 }
695
696 sch->qstats.drops++;
697 return -1;
698 }
699 #endif
700
701 /*
702 It is mission critical procedure.
703
704 We "regenerate" toplevel cutoff, if transmitting class
705 has backlog and it is not regulated. It is not part of
706 original CBQ description, but looks more reasonable.
707 Probably, it is wrong. This question needs further investigation.
708 */
709
710 static __inline__ void
711 cbq_update_toplevel(struct cbq_sched_data *q, struct cbq_class *cl,
712 struct cbq_class *borrowed)
713 {
714 if (cl && q->toplevel >= borrowed->level) {
715 if (cl->q->q.qlen > 1) {
716 do {
717 if (borrowed->undertime == PSCHED_PASTPERFECT) {
718 q->toplevel = borrowed->level;
719 return;
720 }
721 } while ((borrowed=borrowed->borrow) != NULL);
722 }
723 #if 0
724 /* It is not necessary now. Uncommenting it
725 will save CPU cycles, but decrease fairness.
726 */
727 q->toplevel = TC_CBQ_MAXLEVEL;
728 #endif
729 }
730 }
731
732 static void
733 cbq_update(struct cbq_sched_data *q)
734 {
735 struct cbq_class *this = q->tx_class;
736 struct cbq_class *cl = this;
737 int len = q->tx_len;
738
739 q->tx_class = NULL;
740
741 for ( ; cl; cl = cl->share) {
742 long avgidle = cl->avgidle;
743 long idle;
744
745 cl->bstats.packets++;
746 cl->bstats.bytes += len;
747
748 /*
749 (now - last) is total time between packet right edges.
750 (last_pktlen/rate) is "virtual" busy time, so that
751
752 idle = (now - last) - last_pktlen/rate
753 */
754
755 idle = q->now - cl->last;
756 if ((unsigned long)idle > 128*1024*1024) {
757 avgidle = cl->maxidle;
758 } else {
759 idle -= L2T(cl, len);
760
761 /* true_avgidle := (1-W)*true_avgidle + W*idle,
762 where W=2^{-ewma_log}. But cl->avgidle is scaled:
763 cl->avgidle == true_avgidle/W,
764 hence:
765 */
766 avgidle += idle - (avgidle>>cl->ewma_log);
767 }
768
769 if (avgidle <= 0) {
770 /* Overlimit or at-limit */
771
772 if (avgidle < cl->minidle)
773 avgidle = cl->minidle;
774
775 cl->avgidle = avgidle;
776
777 /* Calculate expected time, when this class
778 will be allowed to send.
779 It will occur, when:
780 (1-W)*true_avgidle + W*delay = 0, i.e.
781 idle = (1/W - 1)*(-true_avgidle)
782 or
783 idle = (1 - W)*(-cl->avgidle);
784 */
785 idle = (-avgidle) - ((-avgidle) >> cl->ewma_log);
786
787 /*
788 That is not all.
789 To maintain the rate allocated to the class,
790 we add to undertime virtual clock,
791 necessary to complete transmitted packet.
792 (len/phys_bandwidth has been already passed
793 to the moment of cbq_update)
794 */
795
796 idle -= L2T(&q->link, len);
797 idle += L2T(cl, len);
798
799 cl->undertime = q->now + idle;
800 } else {
801 /* Underlimit */
802
803 cl->undertime = PSCHED_PASTPERFECT;
804 if (avgidle > cl->maxidle)
805 cl->avgidle = cl->maxidle;
806 else
807 cl->avgidle = avgidle;
808 }
809 cl->last = q->now;
810 }
811
812 cbq_update_toplevel(q, this, q->tx_borrowed);
813 }
814
815 static __inline__ struct cbq_class *
816 cbq_under_limit(struct cbq_class *cl)
817 {
818 struct cbq_sched_data *q = qdisc_priv(cl->qdisc);
819 struct cbq_class *this_cl = cl;
820
821 if (cl->tparent == NULL)
822 return cl;
823
824 if (cl->undertime == PSCHED_PASTPERFECT || q->now >= cl->undertime) {
825 cl->delayed = 0;
826 return cl;
827 }
828
829 do {
830 /* It is very suspicious place. Now overlimit
831 action is generated for not bounded classes
832 only if link is completely congested.
833 Though it is in agree with ancestor-only paradigm,
834 it looks very stupid. Particularly,
835 it means that this chunk of code will either
836 never be called or result in strong amplification
837 of burstiness. Dangerous, silly, and, however,
838 no another solution exists.
839 */
840 if ((cl = cl->borrow) == NULL) {
841 this_cl->qstats.overlimits++;
842 this_cl->overlimit(this_cl);
843 return NULL;
844 }
845 if (cl->level > q->toplevel)
846 return NULL;
847 } while (cl->undertime != PSCHED_PASTPERFECT && q->now < cl->undertime);
848
849 cl->delayed = 0;
850 return cl;
851 }
852
853 static __inline__ struct sk_buff *
854 cbq_dequeue_prio(struct Qdisc *sch, int prio)
855 {
856 struct cbq_sched_data *q = qdisc_priv(sch);
857 struct cbq_class *cl_tail, *cl_prev, *cl;
858 struct sk_buff *skb;
859 int deficit;
860
861 cl_tail = cl_prev = q->active[prio];
862 cl = cl_prev->next_alive;
863
864 do {
865 deficit = 0;
866
867 /* Start round */
868 do {
869 struct cbq_class *borrow = cl;
870
871 if (cl->q->q.qlen &&
872 (borrow = cbq_under_limit(cl)) == NULL)
873 goto skip_class;
874
875 if (cl->deficit <= 0) {
876 /* Class exhausted its allotment per
877 this round. Switch to the next one.
878 */
879 deficit = 1;
880 cl->deficit += cl->quantum;
881 goto next_class;
882 }
883
884 skb = cl->q->dequeue(cl->q);
885
886 /* Class did not give us any skb :-(
887 It could occur even if cl->q->q.qlen != 0
888 f.e. if cl->q == "tbf"
889 */
890 if (skb == NULL)
891 goto skip_class;
892
893 cl->deficit -= qdisc_pkt_len(skb);
894 q->tx_class = cl;
895 q->tx_borrowed = borrow;
896 if (borrow != cl) {
897 #ifndef CBQ_XSTATS_BORROWS_BYTES
898 borrow->xstats.borrows++;
899 cl->xstats.borrows++;
900 #else
901 borrow->xstats.borrows += qdisc_pkt_len(skb);
902 cl->xstats.borrows += qdisc_pkt_len(skb);
903 #endif
904 }
905 q->tx_len = qdisc_pkt_len(skb);
906
907 if (cl->deficit <= 0) {
908 q->active[prio] = cl;
909 cl = cl->next_alive;
910 cl->deficit += cl->quantum;
911 }
912 return skb;
913
914 skip_class:
915 if (cl->q->q.qlen == 0 || prio != cl->cpriority) {
916 /* Class is empty or penalized.
917 Unlink it from active chain.
918 */
919 cl_prev->next_alive = cl->next_alive;
920 cl->next_alive = NULL;
921
922 /* Did cl_tail point to it? */
923 if (cl == cl_tail) {
924 /* Repair it! */
925 cl_tail = cl_prev;
926
927 /* Was it the last class in this band? */
928 if (cl == cl_tail) {
929 /* Kill the band! */
930 q->active[prio] = NULL;
931 q->activemask &= ~(1<<prio);
932 if (cl->q->q.qlen)
933 cbq_activate_class(cl);
934 return NULL;
935 }
936
937 q->active[prio] = cl_tail;
938 }
939 if (cl->q->q.qlen)
940 cbq_activate_class(cl);
941
942 cl = cl_prev;
943 }
944
945 next_class:
946 cl_prev = cl;
947 cl = cl->next_alive;
948 } while (cl_prev != cl_tail);
949 } while (deficit);
950
951 q->active[prio] = cl_prev;
952
953 return NULL;
954 }
955
956 static __inline__ struct sk_buff *
957 cbq_dequeue_1(struct Qdisc *sch)
958 {
959 struct cbq_sched_data *q = qdisc_priv(sch);
960 struct sk_buff *skb;
961 unsigned activemask;
962
963 activemask = q->activemask&0xFF;
964 while (activemask) {
965 int prio = ffz(~activemask);
966 activemask &= ~(1<<prio);
967 skb = cbq_dequeue_prio(sch, prio);
968 if (skb)
969 return skb;
970 }
971 return NULL;
972 }
973
974 static struct sk_buff *
975 cbq_dequeue(struct Qdisc *sch)
976 {
977 struct sk_buff *skb;
978 struct cbq_sched_data *q = qdisc_priv(sch);
979 psched_time_t now;
980 psched_tdiff_t incr;
981
982 now = psched_get_time();
983 incr = now - q->now_rt;
984
985 if (q->tx_class) {
986 psched_tdiff_t incr2;
987 /* Time integrator. We calculate EOS time
988 by adding expected packet transmission time.
989 If real time is greater, we warp artificial clock,
990 so that:
991
992 cbq_time = max(real_time, work);
993 */
994 incr2 = L2T(&q->link, q->tx_len);
995 q->now += incr2;
996 cbq_update(q);
997 if ((incr -= incr2) < 0)
998 incr = 0;
999 }
1000 q->now += incr;
1001 q->now_rt = now;
1002
1003 for (;;) {
1004 q->wd_expires = 0;
1005
1006 skb = cbq_dequeue_1(sch);
1007 if (skb) {
1008 sch->q.qlen--;
1009 sch->flags &= ~TCQ_F_THROTTLED;
1010 return skb;
1011 }
1012
1013 /* All the classes are overlimit.
1014
1015 It is possible, if:
1016
1017 1. Scheduler is empty.
1018 2. Toplevel cutoff inhibited borrowing.
1019 3. Root class is overlimit.
1020
1021 Reset 2d and 3d conditions and retry.
1022
1023 Note, that NS and cbq-2.0 are buggy, peeking
1024 an arbitrary class is appropriate for ancestor-only
1025 sharing, but not for toplevel algorithm.
1026
1027 Our version is better, but slower, because it requires
1028 two passes, but it is unavoidable with top-level sharing.
1029 */
1030
1031 if (q->toplevel == TC_CBQ_MAXLEVEL &&
1032 q->link.undertime == PSCHED_PASTPERFECT)
1033 break;
1034
1035 q->toplevel = TC_CBQ_MAXLEVEL;
1036 q->link.undertime = PSCHED_PASTPERFECT;
1037 }
1038
1039 /* No packets in scheduler or nobody wants to give them to us :-(
1040 Sigh... start watchdog timer in the last case. */
1041
1042 if (sch->q.qlen) {
1043 sch->qstats.overlimits++;
1044 if (q->wd_expires)
1045 qdisc_watchdog_schedule(&q->watchdog,
1046 now + q->wd_expires);
1047 }
1048 return NULL;
1049 }
1050
1051 /* CBQ class maintanance routines */
1052
1053 static void cbq_adjust_levels(struct cbq_class *this)
1054 {
1055 if (this == NULL)
1056 return;
1057
1058 do {
1059 int level = 0;
1060 struct cbq_class *cl;
1061
1062 if ((cl = this->children) != NULL) {
1063 do {
1064 if (cl->level > level)
1065 level = cl->level;
1066 } while ((cl = cl->sibling) != this->children);
1067 }
1068 this->level = level+1;
1069 } while ((this = this->tparent) != NULL);
1070 }
1071
1072 static void cbq_normalize_quanta(struct cbq_sched_data *q, int prio)
1073 {
1074 struct cbq_class *cl;
1075 struct hlist_node *n;
1076 unsigned int h;
1077
1078 if (q->quanta[prio] == 0)
1079 return;
1080
1081 for (h = 0; h < q->clhash.hashsize; h++) {
1082 hlist_for_each_entry(cl, n, &q->clhash.hash[h], common.hnode) {
1083 /* BUGGGG... Beware! This expression suffer of
1084 arithmetic overflows!
1085 */
1086 if (cl->priority == prio) {
1087 cl->quantum = (cl->weight*cl->allot*q->nclasses[prio])/
1088 q->quanta[prio];
1089 }
1090 if (cl->quantum <= 0 || cl->quantum>32*qdisc_dev(cl->qdisc)->mtu) {
1091 printk(KERN_WARNING "CBQ: class %08x has bad quantum==%ld, repaired.\n", cl->common.classid, cl->quantum);
1092 cl->quantum = qdisc_dev(cl->qdisc)->mtu/2 + 1;
1093 }
1094 }
1095 }
1096 }
1097
1098 static void cbq_sync_defmap(struct cbq_class *cl)
1099 {
1100 struct cbq_sched_data *q = qdisc_priv(cl->qdisc);
1101 struct cbq_class *split = cl->split;
1102 unsigned h;
1103 int i;
1104
1105 if (split == NULL)
1106 return;
1107
1108 for (i=0; i<=TC_PRIO_MAX; i++) {
1109 if (split->defaults[i] == cl && !(cl->defmap&(1<<i)))
1110 split->defaults[i] = NULL;
1111 }
1112
1113 for (i=0; i<=TC_PRIO_MAX; i++) {
1114 int level = split->level;
1115
1116 if (split->defaults[i])
1117 continue;
1118
1119 for (h = 0; h < q->clhash.hashsize; h++) {
1120 struct hlist_node *n;
1121 struct cbq_class *c;
1122
1123 hlist_for_each_entry(c, n, &q->clhash.hash[h],
1124 common.hnode) {
1125 if (c->split == split && c->level < level &&
1126 c->defmap&(1<<i)) {
1127 split->defaults[i] = c;
1128 level = c->level;
1129 }
1130 }
1131 }
1132 }
1133 }
1134
1135 static void cbq_change_defmap(struct cbq_class *cl, u32 splitid, u32 def, u32 mask)
1136 {
1137 struct cbq_class *split = NULL;
1138
1139 if (splitid == 0) {
1140 if ((split = cl->split) == NULL)
1141 return;
1142 splitid = split->common.classid;
1143 }
1144
1145 if (split == NULL || split->common.classid != splitid) {
1146 for (split = cl->tparent; split; split = split->tparent)
1147 if (split->common.classid == splitid)
1148 break;
1149 }
1150
1151 if (split == NULL)
1152 return;
1153
1154 if (cl->split != split) {
1155 cl->defmap = 0;
1156 cbq_sync_defmap(cl);
1157 cl->split = split;
1158 cl->defmap = def&mask;
1159 } else
1160 cl->defmap = (cl->defmap&~mask)|(def&mask);
1161
1162 cbq_sync_defmap(cl);
1163 }
1164
1165 static void cbq_unlink_class(struct cbq_class *this)
1166 {
1167 struct cbq_class *cl, **clp;
1168 struct cbq_sched_data *q = qdisc_priv(this->qdisc);
1169
1170 qdisc_class_hash_remove(&q->clhash, &this->common);
1171
1172 if (this->tparent) {
1173 clp=&this->sibling;
1174 cl = *clp;
1175 do {
1176 if (cl == this) {
1177 *clp = cl->sibling;
1178 break;
1179 }
1180 clp = &cl->sibling;
1181 } while ((cl = *clp) != this->sibling);
1182
1183 if (this->tparent->children == this) {
1184 this->tparent->children = this->sibling;
1185 if (this->sibling == this)
1186 this->tparent->children = NULL;
1187 }
1188 } else {
1189 WARN_ON(this->sibling != this);
1190 }
1191 }
1192
1193 static void cbq_link_class(struct cbq_class *this)
1194 {
1195 struct cbq_sched_data *q = qdisc_priv(this->qdisc);
1196 struct cbq_class *parent = this->tparent;
1197
1198 this->sibling = this;
1199 qdisc_class_hash_insert(&q->clhash, &this->common);
1200
1201 if (parent == NULL)
1202 return;
1203
1204 if (parent->children == NULL) {
1205 parent->children = this;
1206 } else {
1207 this->sibling = parent->children->sibling;
1208 parent->children->sibling = this;
1209 }
1210 }
1211
1212 static unsigned int cbq_drop(struct Qdisc* sch)
1213 {
1214 struct cbq_sched_data *q = qdisc_priv(sch);
1215 struct cbq_class *cl, *cl_head;
1216 int prio;
1217 unsigned int len;
1218
1219 for (prio = TC_CBQ_MAXPRIO; prio >= 0; prio--) {
1220 if ((cl_head = q->active[prio]) == NULL)
1221 continue;
1222
1223 cl = cl_head;
1224 do {
1225 if (cl->q->ops->drop && (len = cl->q->ops->drop(cl->q))) {
1226 sch->q.qlen--;
1227 if (!cl->q->q.qlen)
1228 cbq_deactivate_class(cl);
1229 return len;
1230 }
1231 } while ((cl = cl->next_alive) != cl_head);
1232 }
1233 return 0;
1234 }
1235
1236 static void
1237 cbq_reset(struct Qdisc* sch)
1238 {
1239 struct cbq_sched_data *q = qdisc_priv(sch);
1240 struct cbq_class *cl;
1241 struct hlist_node *n;
1242 int prio;
1243 unsigned h;
1244
1245 q->activemask = 0;
1246 q->pmask = 0;
1247 q->tx_class = NULL;
1248 q->tx_borrowed = NULL;
1249 qdisc_watchdog_cancel(&q->watchdog);
1250 hrtimer_cancel(&q->delay_timer);
1251 q->toplevel = TC_CBQ_MAXLEVEL;
1252 q->now = psched_get_time();
1253 q->now_rt = q->now;
1254
1255 for (prio = 0; prio <= TC_CBQ_MAXPRIO; prio++)
1256 q->active[prio] = NULL;
1257
1258 for (h = 0; h < q->clhash.hashsize; h++) {
1259 hlist_for_each_entry(cl, n, &q->clhash.hash[h], common.hnode) {
1260 qdisc_reset(cl->q);
1261
1262 cl->next_alive = NULL;
1263 cl->undertime = PSCHED_PASTPERFECT;
1264 cl->avgidle = cl->maxidle;
1265 cl->deficit = cl->quantum;
1266 cl->cpriority = cl->priority;
1267 }
1268 }
1269 sch->q.qlen = 0;
1270 }
1271
1272
1273 static int cbq_set_lss(struct cbq_class *cl, struct tc_cbq_lssopt *lss)
1274 {
1275 if (lss->change&TCF_CBQ_LSS_FLAGS) {
1276 cl->share = (lss->flags&TCF_CBQ_LSS_ISOLATED) ? NULL : cl->tparent;
1277 cl->borrow = (lss->flags&TCF_CBQ_LSS_BOUNDED) ? NULL : cl->tparent;
1278 }
1279 if (lss->change&TCF_CBQ_LSS_EWMA)
1280 cl->ewma_log = lss->ewma_log;
1281 if (lss->change&TCF_CBQ_LSS_AVPKT)
1282 cl->avpkt = lss->avpkt;
1283 if (lss->change&TCF_CBQ_LSS_MINIDLE)
1284 cl->minidle = -(long)lss->minidle;
1285 if (lss->change&TCF_CBQ_LSS_MAXIDLE) {
1286 cl->maxidle = lss->maxidle;
1287 cl->avgidle = lss->maxidle;
1288 }
1289 if (lss->change&TCF_CBQ_LSS_OFFTIME)
1290 cl->offtime = lss->offtime;
1291 return 0;
1292 }
1293
1294 static void cbq_rmprio(struct cbq_sched_data *q, struct cbq_class *cl)
1295 {
1296 q->nclasses[cl->priority]--;
1297 q->quanta[cl->priority] -= cl->weight;
1298 cbq_normalize_quanta(q, cl->priority);
1299 }
1300
1301 static void cbq_addprio(struct cbq_sched_data *q, struct cbq_class *cl)
1302 {
1303 q->nclasses[cl->priority]++;
1304 q->quanta[cl->priority] += cl->weight;
1305 cbq_normalize_quanta(q, cl->priority);
1306 }
1307
1308 static int cbq_set_wrr(struct cbq_class *cl, struct tc_cbq_wrropt *wrr)
1309 {
1310 struct cbq_sched_data *q = qdisc_priv(cl->qdisc);
1311
1312 if (wrr->allot)
1313 cl->allot = wrr->allot;
1314 if (wrr->weight)
1315 cl->weight = wrr->weight;
1316 if (wrr->priority) {
1317 cl->priority = wrr->priority-1;
1318 cl->cpriority = cl->priority;
1319 if (cl->priority >= cl->priority2)
1320 cl->priority2 = TC_CBQ_MAXPRIO-1;
1321 }
1322
1323 cbq_addprio(q, cl);
1324 return 0;
1325 }
1326
1327 static int cbq_set_overlimit(struct cbq_class *cl, struct tc_cbq_ovl *ovl)
1328 {
1329 switch (ovl->strategy) {
1330 case TC_CBQ_OVL_CLASSIC:
1331 cl->overlimit = cbq_ovl_classic;
1332 break;
1333 case TC_CBQ_OVL_DELAY:
1334 cl->overlimit = cbq_ovl_delay;
1335 break;
1336 case TC_CBQ_OVL_LOWPRIO:
1337 if (ovl->priority2-1 >= TC_CBQ_MAXPRIO ||
1338 ovl->priority2-1 <= cl->priority)
1339 return -EINVAL;
1340 cl->priority2 = ovl->priority2-1;
1341 cl->overlimit = cbq_ovl_lowprio;
1342 break;
1343 case TC_CBQ_OVL_DROP:
1344 cl->overlimit = cbq_ovl_drop;
1345 break;
1346 case TC_CBQ_OVL_RCLASSIC:
1347 cl->overlimit = cbq_ovl_rclassic;
1348 break;
1349 default:
1350 return -EINVAL;
1351 }
1352 cl->penalty = ovl->penalty;
1353 return 0;
1354 }
1355
1356 #ifdef CONFIG_NET_CLS_ACT
1357 static int cbq_set_police(struct cbq_class *cl, struct tc_cbq_police *p)
1358 {
1359 cl->police = p->police;
1360
1361 if (cl->q->handle) {
1362 if (p->police == TC_POLICE_RECLASSIFY)
1363 cl->q->reshape_fail = cbq_reshape_fail;
1364 else
1365 cl->q->reshape_fail = NULL;
1366 }
1367 return 0;
1368 }
1369 #endif
1370
1371 static int cbq_set_fopt(struct cbq_class *cl, struct tc_cbq_fopt *fopt)
1372 {
1373 cbq_change_defmap(cl, fopt->split, fopt->defmap, fopt->defchange);
1374 return 0;
1375 }
1376
1377 static const struct nla_policy cbq_policy[TCA_CBQ_MAX + 1] = {
1378 [TCA_CBQ_LSSOPT] = { .len = sizeof(struct tc_cbq_lssopt) },
1379 [TCA_CBQ_WRROPT] = { .len = sizeof(struct tc_cbq_wrropt) },
1380 [TCA_CBQ_FOPT] = { .len = sizeof(struct tc_cbq_fopt) },
1381 [TCA_CBQ_OVL_STRATEGY] = { .len = sizeof(struct tc_cbq_ovl) },
1382 [TCA_CBQ_RATE] = { .len = sizeof(struct tc_ratespec) },
1383 [TCA_CBQ_RTAB] = { .type = NLA_BINARY, .len = TC_RTAB_SIZE },
1384 [TCA_CBQ_POLICE] = { .len = sizeof(struct tc_cbq_police) },
1385 };
1386
1387 static int cbq_init(struct Qdisc *sch, struct nlattr *opt)
1388 {
1389 struct cbq_sched_data *q = qdisc_priv(sch);
1390 struct nlattr *tb[TCA_CBQ_MAX + 1];
1391 struct tc_ratespec *r;
1392 int err;
1393
1394 err = nla_parse_nested(tb, TCA_CBQ_MAX, opt, cbq_policy);
1395 if (err < 0)
1396 return err;
1397
1398 if (tb[TCA_CBQ_RTAB] == NULL || tb[TCA_CBQ_RATE] == NULL)
1399 return -EINVAL;
1400
1401 r = nla_data(tb[TCA_CBQ_RATE]);
1402
1403 if ((q->link.R_tab = qdisc_get_rtab(r, tb[TCA_CBQ_RTAB])) == NULL)
1404 return -EINVAL;
1405
1406 err = qdisc_class_hash_init(&q->clhash);
1407 if (err < 0)
1408 goto put_rtab;
1409
1410 q->link.refcnt = 1;
1411 q->link.sibling = &q->link;
1412 q->link.common.classid = sch->handle;
1413 q->link.qdisc = sch;
1414 if (!(q->link.q = qdisc_create_dflt(qdisc_dev(sch), sch->dev_queue,
1415 &pfifo_qdisc_ops,
1416 sch->handle)))
1417 q->link.q = &noop_qdisc;
1418
1419 q->link.priority = TC_CBQ_MAXPRIO-1;
1420 q->link.priority2 = TC_CBQ_MAXPRIO-1;
1421 q->link.cpriority = TC_CBQ_MAXPRIO-1;
1422 q->link.ovl_strategy = TC_CBQ_OVL_CLASSIC;
1423 q->link.overlimit = cbq_ovl_classic;
1424 q->link.allot = psched_mtu(qdisc_dev(sch));
1425 q->link.quantum = q->link.allot;
1426 q->link.weight = q->link.R_tab->rate.rate;
1427
1428 q->link.ewma_log = TC_CBQ_DEF_EWMA;
1429 q->link.avpkt = q->link.allot/2;
1430 q->link.minidle = -0x7FFFFFFF;
1431
1432 qdisc_watchdog_init(&q->watchdog, sch);
1433 hrtimer_init(&q->delay_timer, CLOCK_MONOTONIC, HRTIMER_MODE_ABS);
1434 q->delay_timer.function = cbq_undelay;
1435 q->toplevel = TC_CBQ_MAXLEVEL;
1436 q->now = psched_get_time();
1437 q->now_rt = q->now;
1438
1439 cbq_link_class(&q->link);
1440
1441 if (tb[TCA_CBQ_LSSOPT])
1442 cbq_set_lss(&q->link, nla_data(tb[TCA_CBQ_LSSOPT]));
1443
1444 cbq_addprio(q, &q->link);
1445 return 0;
1446
1447 put_rtab:
1448 qdisc_put_rtab(q->link.R_tab);
1449 return err;
1450 }
1451
1452 static __inline__ int cbq_dump_rate(struct sk_buff *skb, struct cbq_class *cl)
1453 {
1454 unsigned char *b = skb_tail_pointer(skb);
1455
1456 NLA_PUT(skb, TCA_CBQ_RATE, sizeof(cl->R_tab->rate), &cl->R_tab->rate);
1457 return skb->len;
1458
1459 nla_put_failure:
1460 nlmsg_trim(skb, b);
1461 return -1;
1462 }
1463
1464 static __inline__ int cbq_dump_lss(struct sk_buff *skb, struct cbq_class *cl)
1465 {
1466 unsigned char *b = skb_tail_pointer(skb);
1467 struct tc_cbq_lssopt opt;
1468
1469 opt.flags = 0;
1470 if (cl->borrow == NULL)
1471 opt.flags |= TCF_CBQ_LSS_BOUNDED;
1472 if (cl->share == NULL)
1473 opt.flags |= TCF_CBQ_LSS_ISOLATED;
1474 opt.ewma_log = cl->ewma_log;
1475 opt.level = cl->level;
1476 opt.avpkt = cl->avpkt;
1477 opt.maxidle = cl->maxidle;
1478 opt.minidle = (u32)(-cl->minidle);
1479 opt.offtime = cl->offtime;
1480 opt.change = ~0;
1481 NLA_PUT(skb, TCA_CBQ_LSSOPT, sizeof(opt), &opt);
1482 return skb->len;
1483
1484 nla_put_failure:
1485 nlmsg_trim(skb, b);
1486 return -1;
1487 }
1488
1489 static __inline__ int cbq_dump_wrr(struct sk_buff *skb, struct cbq_class *cl)
1490 {
1491 unsigned char *b = skb_tail_pointer(skb);
1492 struct tc_cbq_wrropt opt;
1493
1494 opt.flags = 0;
1495 opt.allot = cl->allot;
1496 opt.priority = cl->priority+1;
1497 opt.cpriority = cl->cpriority+1;
1498 opt.weight = cl->weight;
1499 NLA_PUT(skb, TCA_CBQ_WRROPT, sizeof(opt), &opt);
1500 return skb->len;
1501
1502 nla_put_failure:
1503 nlmsg_trim(skb, b);
1504 return -1;
1505 }
1506
1507 static __inline__ int cbq_dump_ovl(struct sk_buff *skb, struct cbq_class *cl)
1508 {
1509 unsigned char *b = skb_tail_pointer(skb);
1510 struct tc_cbq_ovl opt;
1511
1512 opt.strategy = cl->ovl_strategy;
1513 opt.priority2 = cl->priority2+1;
1514 opt.pad = 0;
1515 opt.penalty = cl->penalty;
1516 NLA_PUT(skb, TCA_CBQ_OVL_STRATEGY, sizeof(opt), &opt);
1517 return skb->len;
1518
1519 nla_put_failure:
1520 nlmsg_trim(skb, b);
1521 return -1;
1522 }
1523
1524 static __inline__ int cbq_dump_fopt(struct sk_buff *skb, struct cbq_class *cl)
1525 {
1526 unsigned char *b = skb_tail_pointer(skb);
1527 struct tc_cbq_fopt opt;
1528
1529 if (cl->split || cl->defmap) {
1530 opt.split = cl->split ? cl->split->common.classid : 0;
1531 opt.defmap = cl->defmap;
1532 opt.defchange = ~0;
1533 NLA_PUT(skb, TCA_CBQ_FOPT, sizeof(opt), &opt);
1534 }
1535 return skb->len;
1536
1537 nla_put_failure:
1538 nlmsg_trim(skb, b);
1539 return -1;
1540 }
1541
1542 #ifdef CONFIG_NET_CLS_ACT
1543 static __inline__ int cbq_dump_police(struct sk_buff *skb, struct cbq_class *cl)
1544 {
1545 unsigned char *b = skb_tail_pointer(skb);
1546 struct tc_cbq_police opt;
1547
1548 if (cl->police) {
1549 opt.police = cl->police;
1550 opt.__res1 = 0;
1551 opt.__res2 = 0;
1552 NLA_PUT(skb, TCA_CBQ_POLICE, sizeof(opt), &opt);
1553 }
1554 return skb->len;
1555
1556 nla_put_failure:
1557 nlmsg_trim(skb, b);
1558 return -1;
1559 }
1560 #endif
1561
1562 static int cbq_dump_attr(struct sk_buff *skb, struct cbq_class *cl)
1563 {
1564 if (cbq_dump_lss(skb, cl) < 0 ||
1565 cbq_dump_rate(skb, cl) < 0 ||
1566 cbq_dump_wrr(skb, cl) < 0 ||
1567 cbq_dump_ovl(skb, cl) < 0 ||
1568 #ifdef CONFIG_NET_CLS_ACT
1569 cbq_dump_police(skb, cl) < 0 ||
1570 #endif
1571 cbq_dump_fopt(skb, cl) < 0)
1572 return -1;
1573 return 0;
1574 }
1575
1576 static int cbq_dump(struct Qdisc *sch, struct sk_buff *skb)
1577 {
1578 struct cbq_sched_data *q = qdisc_priv(sch);
1579 struct nlattr *nest;
1580
1581 nest = nla_nest_start(skb, TCA_OPTIONS);
1582 if (nest == NULL)
1583 goto nla_put_failure;
1584 if (cbq_dump_attr(skb, &q->link) < 0)
1585 goto nla_put_failure;
1586 nla_nest_end(skb, nest);
1587 return skb->len;
1588
1589 nla_put_failure:
1590 nla_nest_cancel(skb, nest);
1591 return -1;
1592 }
1593
1594 static int
1595 cbq_dump_stats(struct Qdisc *sch, struct gnet_dump *d)
1596 {
1597 struct cbq_sched_data *q = qdisc_priv(sch);
1598
1599 q->link.xstats.avgidle = q->link.avgidle;
1600 return gnet_stats_copy_app(d, &q->link.xstats, sizeof(q->link.xstats));
1601 }
1602
1603 static int
1604 cbq_dump_class(struct Qdisc *sch, unsigned long arg,
1605 struct sk_buff *skb, struct tcmsg *tcm)
1606 {
1607 struct cbq_class *cl = (struct cbq_class*)arg;
1608 struct nlattr *nest;
1609
1610 if (cl->tparent)
1611 tcm->tcm_parent = cl->tparent->common.classid;
1612 else
1613 tcm->tcm_parent = TC_H_ROOT;
1614 tcm->tcm_handle = cl->common.classid;
1615 tcm->tcm_info = cl->q->handle;
1616
1617 nest = nla_nest_start(skb, TCA_OPTIONS);
1618 if (nest == NULL)
1619 goto nla_put_failure;
1620 if (cbq_dump_attr(skb, cl) < 0)
1621 goto nla_put_failure;
1622 nla_nest_end(skb, nest);
1623 return skb->len;
1624
1625 nla_put_failure:
1626 nla_nest_cancel(skb, nest);
1627 return -1;
1628 }
1629
1630 static int
1631 cbq_dump_class_stats(struct Qdisc *sch, unsigned long arg,
1632 struct gnet_dump *d)
1633 {
1634 struct cbq_sched_data *q = qdisc_priv(sch);
1635 struct cbq_class *cl = (struct cbq_class*)arg;
1636
1637 cl->qstats.qlen = cl->q->q.qlen;
1638 cl->xstats.avgidle = cl->avgidle;
1639 cl->xstats.undertime = 0;
1640
1641 if (cl->undertime != PSCHED_PASTPERFECT)
1642 cl->xstats.undertime = cl->undertime - q->now;
1643
1644 if (gnet_stats_copy_basic(d, &cl->bstats) < 0 ||
1645 gnet_stats_copy_rate_est(d, &cl->rate_est) < 0 ||
1646 gnet_stats_copy_queue(d, &cl->qstats) < 0)
1647 return -1;
1648
1649 return gnet_stats_copy_app(d, &cl->xstats, sizeof(cl->xstats));
1650 }
1651
1652 static int cbq_graft(struct Qdisc *sch, unsigned long arg, struct Qdisc *new,
1653 struct Qdisc **old)
1654 {
1655 struct cbq_class *cl = (struct cbq_class*)arg;
1656
1657 if (cl) {
1658 if (new == NULL) {
1659 new = qdisc_create_dflt(qdisc_dev(sch), sch->dev_queue,
1660 &pfifo_qdisc_ops,
1661 cl->common.classid);
1662 if (new == NULL)
1663 return -ENOBUFS;
1664 } else {
1665 #ifdef CONFIG_NET_CLS_ACT
1666 if (cl->police == TC_POLICE_RECLASSIFY)
1667 new->reshape_fail = cbq_reshape_fail;
1668 #endif
1669 }
1670 sch_tree_lock(sch);
1671 *old = xchg(&cl->q, new);
1672 qdisc_tree_decrease_qlen(*old, (*old)->q.qlen);
1673 qdisc_reset(*old);
1674 sch_tree_unlock(sch);
1675
1676 return 0;
1677 }
1678 return -ENOENT;
1679 }
1680
1681 static struct Qdisc *
1682 cbq_leaf(struct Qdisc *sch, unsigned long arg)
1683 {
1684 struct cbq_class *cl = (struct cbq_class*)arg;
1685
1686 return cl ? cl->q : NULL;
1687 }
1688
1689 static void cbq_qlen_notify(struct Qdisc *sch, unsigned long arg)
1690 {
1691 struct cbq_class *cl = (struct cbq_class *)arg;
1692
1693 if (cl->q->q.qlen == 0)
1694 cbq_deactivate_class(cl);
1695 }
1696
1697 static unsigned long cbq_get(struct Qdisc *sch, u32 classid)
1698 {
1699 struct cbq_sched_data *q = qdisc_priv(sch);
1700 struct cbq_class *cl = cbq_class_lookup(q, classid);
1701
1702 if (cl) {
1703 cl->refcnt++;
1704 return (unsigned long)cl;
1705 }
1706 return 0;
1707 }
1708
1709 static void cbq_destroy_class(struct Qdisc *sch, struct cbq_class *cl)
1710 {
1711 struct cbq_sched_data *q = qdisc_priv(sch);
1712
1713 WARN_ON(cl->filters);
1714
1715 tcf_destroy_chain(&cl->filter_list);
1716 qdisc_destroy(cl->q);
1717 qdisc_put_rtab(cl->R_tab);
1718 gen_kill_estimator(&cl->bstats, &cl->rate_est);
1719 if (cl != &q->link)
1720 kfree(cl);
1721 }
1722
1723 static void
1724 cbq_destroy(struct Qdisc* sch)
1725 {
1726 struct cbq_sched_data *q = qdisc_priv(sch);
1727 struct hlist_node *n, *next;
1728 struct cbq_class *cl;
1729 unsigned h;
1730
1731 #ifdef CONFIG_NET_CLS_ACT
1732 q->rx_class = NULL;
1733 #endif
1734 /*
1735 * Filters must be destroyed first because we don't destroy the
1736 * classes from root to leafs which means that filters can still
1737 * be bound to classes which have been destroyed already. --TGR '04
1738 */
1739 for (h = 0; h < q->clhash.hashsize; h++) {
1740 hlist_for_each_entry(cl, n, &q->clhash.hash[h], common.hnode)
1741 tcf_destroy_chain(&cl->filter_list);
1742 }
1743 for (h = 0; h < q->clhash.hashsize; h++) {
1744 hlist_for_each_entry_safe(cl, n, next, &q->clhash.hash[h],
1745 common.hnode)
1746 cbq_destroy_class(sch, cl);
1747 }
1748 qdisc_class_hash_destroy(&q->clhash);
1749 }
1750
1751 static void cbq_put(struct Qdisc *sch, unsigned long arg)
1752 {
1753 struct cbq_class *cl = (struct cbq_class*)arg;
1754
1755 if (--cl->refcnt == 0) {
1756 #ifdef CONFIG_NET_CLS_ACT
1757 spinlock_t *root_lock = qdisc_root_sleeping_lock(sch);
1758 struct cbq_sched_data *q = qdisc_priv(sch);
1759
1760 spin_lock_bh(root_lock);
1761 if (q->rx_class == cl)
1762 q->rx_class = NULL;
1763 spin_unlock_bh(root_lock);
1764 #endif
1765
1766 cbq_destroy_class(sch, cl);
1767 }
1768 }
1769
1770 static int
1771 cbq_change_class(struct Qdisc *sch, u32 classid, u32 parentid, struct nlattr **tca,
1772 unsigned long *arg)
1773 {
1774 int err;
1775 struct cbq_sched_data *q = qdisc_priv(sch);
1776 struct cbq_class *cl = (struct cbq_class*)*arg;
1777 struct nlattr *opt = tca[TCA_OPTIONS];
1778 struct nlattr *tb[TCA_CBQ_MAX + 1];
1779 struct cbq_class *parent;
1780 struct qdisc_rate_table *rtab = NULL;
1781
1782 if (opt == NULL)
1783 return -EINVAL;
1784
1785 err = nla_parse_nested(tb, TCA_CBQ_MAX, opt, cbq_policy);
1786 if (err < 0)
1787 return err;
1788
1789 if (cl) {
1790 /* Check parent */
1791 if (parentid) {
1792 if (cl->tparent &&
1793 cl->tparent->common.classid != parentid)
1794 return -EINVAL;
1795 if (!cl->tparent && parentid != TC_H_ROOT)
1796 return -EINVAL;
1797 }
1798
1799 if (tb[TCA_CBQ_RATE]) {
1800 rtab = qdisc_get_rtab(nla_data(tb[TCA_CBQ_RATE]), tb[TCA_CBQ_RTAB]);
1801 if (rtab == NULL)
1802 return -EINVAL;
1803 }
1804
1805 /* Change class parameters */
1806 sch_tree_lock(sch);
1807
1808 if (cl->next_alive != NULL)
1809 cbq_deactivate_class(cl);
1810
1811 if (rtab) {
1812 rtab = xchg(&cl->R_tab, rtab);
1813 qdisc_put_rtab(rtab);
1814 }
1815
1816 if (tb[TCA_CBQ_LSSOPT])
1817 cbq_set_lss(cl, nla_data(tb[TCA_CBQ_LSSOPT]));
1818
1819 if (tb[TCA_CBQ_WRROPT]) {
1820 cbq_rmprio(q, cl);
1821 cbq_set_wrr(cl, nla_data(tb[TCA_CBQ_WRROPT]));
1822 }
1823
1824 if (tb[TCA_CBQ_OVL_STRATEGY])
1825 cbq_set_overlimit(cl, nla_data(tb[TCA_CBQ_OVL_STRATEGY]));
1826
1827 #ifdef CONFIG_NET_CLS_ACT
1828 if (tb[TCA_CBQ_POLICE])
1829 cbq_set_police(cl, nla_data(tb[TCA_CBQ_POLICE]));
1830 #endif
1831
1832 if (tb[TCA_CBQ_FOPT])
1833 cbq_set_fopt(cl, nla_data(tb[TCA_CBQ_FOPT]));
1834
1835 if (cl->q->q.qlen)
1836 cbq_activate_class(cl);
1837
1838 sch_tree_unlock(sch);
1839
1840 if (tca[TCA_RATE])
1841 gen_replace_estimator(&cl->bstats, &cl->rate_est,
1842 qdisc_root_sleeping_lock(sch),
1843 tca[TCA_RATE]);
1844 return 0;
1845 }
1846
1847 if (parentid == TC_H_ROOT)
1848 return -EINVAL;
1849
1850 if (tb[TCA_CBQ_WRROPT] == NULL || tb[TCA_CBQ_RATE] == NULL ||
1851 tb[TCA_CBQ_LSSOPT] == NULL)
1852 return -EINVAL;
1853
1854 rtab = qdisc_get_rtab(nla_data(tb[TCA_CBQ_RATE]), tb[TCA_CBQ_RTAB]);
1855 if (rtab == NULL)
1856 return -EINVAL;
1857
1858 if (classid) {
1859 err = -EINVAL;
1860 if (TC_H_MAJ(classid^sch->handle) || cbq_class_lookup(q, classid))
1861 goto failure;
1862 } else {
1863 int i;
1864 classid = TC_H_MAKE(sch->handle,0x8000);
1865
1866 for (i=0; i<0x8000; i++) {
1867 if (++q->hgenerator >= 0x8000)
1868 q->hgenerator = 1;
1869 if (cbq_class_lookup(q, classid|q->hgenerator) == NULL)
1870 break;
1871 }
1872 err = -ENOSR;
1873 if (i >= 0x8000)
1874 goto failure;
1875 classid = classid|q->hgenerator;
1876 }
1877
1878 parent = &q->link;
1879 if (parentid) {
1880 parent = cbq_class_lookup(q, parentid);
1881 err = -EINVAL;
1882 if (parent == NULL)
1883 goto failure;
1884 }
1885
1886 err = -ENOBUFS;
1887 cl = kzalloc(sizeof(*cl), GFP_KERNEL);
1888 if (cl == NULL)
1889 goto failure;
1890 cl->R_tab = rtab;
1891 rtab = NULL;
1892 cl->refcnt = 1;
1893 if (!(cl->q = qdisc_create_dflt(qdisc_dev(sch), sch->dev_queue,
1894 &pfifo_qdisc_ops, classid)))
1895 cl->q = &noop_qdisc;
1896 cl->common.classid = classid;
1897 cl->tparent = parent;
1898 cl->qdisc = sch;
1899 cl->allot = parent->allot;
1900 cl->quantum = cl->allot;
1901 cl->weight = cl->R_tab->rate.rate;
1902
1903 sch_tree_lock(sch);
1904 cbq_link_class(cl);
1905 cl->borrow = cl->tparent;
1906 if (cl->tparent != &q->link)
1907 cl->share = cl->tparent;
1908 cbq_adjust_levels(parent);
1909 cl->minidle = -0x7FFFFFFF;
1910 cbq_set_lss(cl, nla_data(tb[TCA_CBQ_LSSOPT]));
1911 cbq_set_wrr(cl, nla_data(tb[TCA_CBQ_WRROPT]));
1912 if (cl->ewma_log==0)
1913 cl->ewma_log = q->link.ewma_log;
1914 if (cl->maxidle==0)
1915 cl->maxidle = q->link.maxidle;
1916 if (cl->avpkt==0)
1917 cl->avpkt = q->link.avpkt;
1918 cl->overlimit = cbq_ovl_classic;
1919 if (tb[TCA_CBQ_OVL_STRATEGY])
1920 cbq_set_overlimit(cl, nla_data(tb[TCA_CBQ_OVL_STRATEGY]));
1921 #ifdef CONFIG_NET_CLS_ACT
1922 if (tb[TCA_CBQ_POLICE])
1923 cbq_set_police(cl, nla_data(tb[TCA_CBQ_POLICE]));
1924 #endif
1925 if (tb[TCA_CBQ_FOPT])
1926 cbq_set_fopt(cl, nla_data(tb[TCA_CBQ_FOPT]));
1927 sch_tree_unlock(sch);
1928
1929 qdisc_class_hash_grow(sch, &q->clhash);
1930
1931 if (tca[TCA_RATE])
1932 gen_new_estimator(&cl->bstats, &cl->rate_est,
1933 qdisc_root_sleeping_lock(sch), tca[TCA_RATE]);
1934
1935 *arg = (unsigned long)cl;
1936 return 0;
1937
1938 failure:
1939 qdisc_put_rtab(rtab);
1940 return err;
1941 }
1942
1943 static int cbq_delete(struct Qdisc *sch, unsigned long arg)
1944 {
1945 struct cbq_sched_data *q = qdisc_priv(sch);
1946 struct cbq_class *cl = (struct cbq_class*)arg;
1947 unsigned int qlen;
1948
1949 if (cl->filters || cl->children || cl == &q->link)
1950 return -EBUSY;
1951
1952 sch_tree_lock(sch);
1953
1954 qlen = cl->q->q.qlen;
1955 qdisc_reset(cl->q);
1956 qdisc_tree_decrease_qlen(cl->q, qlen);
1957
1958 if (cl->next_alive)
1959 cbq_deactivate_class(cl);
1960
1961 if (q->tx_borrowed == cl)
1962 q->tx_borrowed = q->tx_class;
1963 if (q->tx_class == cl) {
1964 q->tx_class = NULL;
1965 q->tx_borrowed = NULL;
1966 }
1967 #ifdef CONFIG_NET_CLS_ACT
1968 if (q->rx_class == cl)
1969 q->rx_class = NULL;
1970 #endif
1971
1972 cbq_unlink_class(cl);
1973 cbq_adjust_levels(cl->tparent);
1974 cl->defmap = 0;
1975 cbq_sync_defmap(cl);
1976
1977 cbq_rmprio(q, cl);
1978 sch_tree_unlock(sch);
1979
1980 if (--cl->refcnt == 0)
1981 cbq_destroy_class(sch, cl);
1982
1983 return 0;
1984 }
1985
1986 static struct tcf_proto **cbq_find_tcf(struct Qdisc *sch, unsigned long arg)
1987 {
1988 struct cbq_sched_data *q = qdisc_priv(sch);
1989 struct cbq_class *cl = (struct cbq_class *)arg;
1990
1991 if (cl == NULL)
1992 cl = &q->link;
1993
1994 return &cl->filter_list;
1995 }
1996
1997 static unsigned long cbq_bind_filter(struct Qdisc *sch, unsigned long parent,
1998 u32 classid)
1999 {
2000 struct cbq_sched_data *q = qdisc_priv(sch);
2001 struct cbq_class *p = (struct cbq_class*)parent;
2002 struct cbq_class *cl = cbq_class_lookup(q, classid);
2003
2004 if (cl) {
2005 if (p && p->level <= cl->level)
2006 return 0;
2007 cl->filters++;
2008 return (unsigned long)cl;
2009 }
2010 return 0;
2011 }
2012
2013 static void cbq_unbind_filter(struct Qdisc *sch, unsigned long arg)
2014 {
2015 struct cbq_class *cl = (struct cbq_class*)arg;
2016
2017 cl->filters--;
2018 }
2019
2020 static void cbq_walk(struct Qdisc *sch, struct qdisc_walker *arg)
2021 {
2022 struct cbq_sched_data *q = qdisc_priv(sch);
2023 struct cbq_class *cl;
2024 struct hlist_node *n;
2025 unsigned h;
2026
2027 if (arg->stop)
2028 return;
2029
2030 for (h = 0; h < q->clhash.hashsize; h++) {
2031 hlist_for_each_entry(cl, n, &q->clhash.hash[h], common.hnode) {
2032 if (arg->count < arg->skip) {
2033 arg->count++;
2034 continue;
2035 }
2036 if (arg->fn(sch, (unsigned long)cl, arg) < 0) {
2037 arg->stop = 1;
2038 return;
2039 }
2040 arg->count++;
2041 }
2042 }
2043 }
2044
2045 static const struct Qdisc_class_ops cbq_class_ops = {
2046 .graft = cbq_graft,
2047 .leaf = cbq_leaf,
2048 .qlen_notify = cbq_qlen_notify,
2049 .get = cbq_get,
2050 .put = cbq_put,
2051 .change = cbq_change_class,
2052 .delete = cbq_delete,
2053 .walk = cbq_walk,
2054 .tcf_chain = cbq_find_tcf,
2055 .bind_tcf = cbq_bind_filter,
2056 .unbind_tcf = cbq_unbind_filter,
2057 .dump = cbq_dump_class,
2058 .dump_stats = cbq_dump_class_stats,
2059 };
2060
2061 static struct Qdisc_ops cbq_qdisc_ops __read_mostly = {
2062 .next = NULL,
2063 .cl_ops = &cbq_class_ops,
2064 .id = "cbq",
2065 .priv_size = sizeof(struct cbq_sched_data),
2066 .enqueue = cbq_enqueue,
2067 .dequeue = cbq_dequeue,
2068 .requeue = cbq_requeue,
2069 .drop = cbq_drop,
2070 .init = cbq_init,
2071 .reset = cbq_reset,
2072 .destroy = cbq_destroy,
2073 .change = NULL,
2074 .dump = cbq_dump,
2075 .dump_stats = cbq_dump_stats,
2076 .owner = THIS_MODULE,
2077 };
2078
2079 static int __init cbq_module_init(void)
2080 {
2081 return register_qdisc(&cbq_qdisc_ops);
2082 }
2083 static void __exit cbq_module_exit(void)
2084 {
2085 unregister_qdisc(&cbq_qdisc_ops);
2086 }
2087 module_init(cbq_module_init)
2088 module_exit(cbq_module_exit)
2089 MODULE_LICENSE("GPL");
Support for the Chinese Samsung S3C2440 based development boards