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