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