Version:  2.0.40 2.2.26 2.4.37 2.6.39 3.0 3.1 3.2 3.3 3.4 3.5 3.6 3.7 3.8 3.9 3.10 3.11 3.12 3.13 3.14 3.15

Linux/net/sched/sch_cbq.c

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

This page was automatically generated by LXR 0.3.1 (source).  •  Linux is a registered trademark of Linus Torvalds  •  Contact us