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