net/sched/sch_htb.c

   1 /* vim: ts=8 sw=8
   2  * net/sched/sch_htb.c  Hierarchical token bucket, feed tree version
   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:     Martin Devera, <devik@cdi.cz>
  10  *
  11  * Credits (in time order) for older HTB versions:
  12  *              Stef Coene <stef.coene@docum.org>
  13  *                      HTB support at LARTC mailing list
  14  *              Ondrej Kraus, <krauso@barr.cz>
  15  *                      found missing INIT_QDISC(htb)
  16  *              Vladimir Smelhaus, Aamer Akhter, Bert Hubert
  17  *                      helped a lot to locate nasty class stall bug
  18  *              Andi Kleen, Jamal Hadi, Bert Hubert
  19  *                      code review and helpful comments on shaping
  20  *              Tomasz Wrona, <tw@eter.tym.pl>
  21  *                      created test case so that I was able to fix nasty bug
  22  *              Wilfried Weissmann
  23  *                      spotted bug in dequeue code and helped with fix
  24  *              Jiri Fojtasek
  25  *                      fixed requeue routine
  26  *              and many others. thanks.
  27  *
  28  * $Id: sch_htb.c,v 1.25 2003/12/07 11:08:25 devik Exp devik $
  29  */
  30 #include <linux/config.h>
  31 #include <linux/module.h>
  32 #include <asm/uaccess.h>
  33 #include <asm/system.h>
  34 #include <linux/bitops.h>
  35 #include <linux/types.h>
  36 #include <linux/kernel.h>
  37 #include <linux/sched.h>
  38 #include <linux/string.h>
  39 #include <linux/mm.h>
  40 #include <linux/socket.h>
  41 #include <linux/sockios.h>
  42 #include <linux/in.h>
  43 #include <linux/errno.h>
  44 #include <linux/interrupt.h>
  45 #include <linux/if_ether.h>
  46 #include <linux/inet.h>
  47 #include <linux/netdevice.h>
  48 #include <linux/etherdevice.h>
  49 #include <linux/notifier.h>
  50 #include <net/ip.h>
  51 #include <net/route.h>
  52 #include <linux/skbuff.h>
  53 #include <linux/list.h>
  54 #include <linux/compiler.h>
  55 #include <net/sock.h>
  56 #include <net/pkt_sched.h>
  57 #include <linux/rbtree.h>
  58
  59 /* HTB algorithm.
  60     Author: devik@cdi.cz
  61     ========================================================================
  62     HTB is like TBF with multiple classes. It is also similar to CBQ because
  63     it allows to assign priority to each class in hierarchy.
  64     In fact it is another implementation of Floyd's formal sharing.
  65
  66     Levels:
  67     Each class is assigned level. Leaf has ALWAYS level 0 and root
  68     classes have level TC_HTB_MAXDEPTH-1. Interior nodes has level
  69     one less than their parent.
  70 */
  71
  72 #define HTB_HSIZE 16    /* classid hash size */
  73 #define HTB_EWMAC 2     /* rate average over HTB_EWMAC*HTB_HSIZE sec */
  74 #define HTB_DEBUG 1     /* compile debugging support (activated by tc tool) */
  75 #define HTB_RATECM 1    /* whether to use rate computer */
  76 #define HTB_HYSTERESIS 1/* whether to use mode hysteresis for speedup */
  77 #define HTB_QLOCK(S) spin_lock_bh(&(S)->dev->queue_lock)
  78 #define HTB_QUNLOCK(S) spin_unlock_bh(&(S)->dev->queue_lock)
  79 #define HTB_VER 0x30011 /* major must be matched with number suplied by TC as version */
  80
  81 #if HTB_VER >> 16 != TC_HTB_PROTOVER
  82 #error "Mismatched sch_htb.c and pkt_sch.h"
  83 #endif
  84
  85 /* debugging support; S is subsystem, these are defined:
  86   0 - netlink messages
  87   1 - enqueue
  88   2 - drop & requeue
  89   3 - dequeue main
  90   4 - dequeue one prio DRR part
  91   5 - dequeue class accounting
  92   6 - class overlimit status computation
  93   7 - hint tree
  94   8 - event queue
  95  10 - rate estimator
  96  11 - classifier
  97  12 - fast dequeue cache
  98
  99  L is level; 0 = none, 1 = basic info, 2 = detailed, 3 = full
 100  q->debug uint32 contains 16 2-bit fields one for subsystem starting
 101  from LSB
 102  */
 103 #ifdef HTB_DEBUG
 104 #define HTB_DBG_COND(S,L) (((q->debug>>(2*S))&3) >= L)
 105 #define HTB_DBG(S,L,FMT,ARG...) if (HTB_DBG_COND(S,L)) \
 106         printk(KERN_DEBUG FMT,##ARG)
 107 #define HTB_CHCL(cl) BUG_TRAP((cl)->magic == HTB_CMAGIC)
 108 #define HTB_PASSQ q,
 109 #define HTB_ARGQ struct htb_sched *q,
 110 #define static
 111 #undef __inline__
 112 #define __inline__
 113 #undef inline
 114 #define inline
 115 #define HTB_CMAGIC 0xFEFAFEF1
 116 #define htb_safe_rb_erase(N,R) do { BUG_TRAP((N)->rb_color != -1); \
 117                 if ((N)->rb_color == -1) break; \
 118                 rb_erase(N,R); \
 119                 (N)->rb_color = -1; } while (0)
 120 #else
 121 #define HTB_DBG_COND(S,L) (0)
 122 #define HTB_DBG(S,L,FMT,ARG...)
 123 #define HTB_PASSQ
 124 #define HTB_ARGQ
 125 #define HTB_CHCL(cl)
 126 #define htb_safe_rb_erase(N,R) rb_erase(N,R)
 127 #endif
 128
 129
 130 /* used internaly to keep status of single class */
 131 enum htb_cmode {
 132     HTB_CANT_SEND,              /* class can't send and can't borrow */
 133     HTB_MAY_BORROW,             /* class can't send but may borrow */
 134     HTB_CAN_SEND                /* class can send */
 135 };
 136
 137 /* interior & leaf nodes; props specific to leaves are marked L: */
 138 struct htb_class
 139 {
 140 #ifdef HTB_DEBUG
 141         unsigned magic;
 142 #endif
 143     /* general class parameters */
 144     u32 classid;
 145     struct gnet_stats_basic bstats;
 146     struct gnet_stats_queue qstats;
 147     struct gnet_stats_rate_est rate_est;
 148     struct tc_htb_xstats xstats;/* our special stats */
 149     int refcnt;                 /* usage count of this class */
 150
 151 #ifdef HTB_RATECM
 152     /* rate measurement counters */
 153     unsigned long rate_bytes,sum_bytes;
 154     unsigned long rate_packets,sum_packets;
 155 #endif
 156
 157     /* topology */
 158     int level;                  /* our level (see above) */
 159     struct htb_class *parent;   /* parent class */
 160     struct list_head hlist;     /* classid hash list item */
 161     struct list_head sibling;   /* sibling list item */
 162     struct list_head children;  /* children list */
 163
 164     union {
 165             struct htb_class_leaf {
 166                     struct Qdisc *q;
 167                     int prio;
 168                     int aprio;
 169                     int quantum;
 170                     int deficit[TC_HTB_MAXDEPTH];
 171                     struct list_head drop_list;
 172             } leaf;
 173             struct htb_class_inner {
 174                     struct rb_root feed[TC_HTB_NUMPRIO]; /* feed trees */
 175                     struct rb_node *ptr[TC_HTB_NUMPRIO]; /* current class ptr */
 176             /* When class changes from state 1->2 and disconnects from
 177                parent's feed then we lost ptr value and start from the
 178               first child again. Here we store classid of the
 179               last valid ptr (used when ptr is NULL). */
 180               u32 last_ptr_id[TC_HTB_NUMPRIO];
 181             } inner;
 182     } un;
 183     struct rb_node node[TC_HTB_NUMPRIO]; /* node for self or feed tree */
 184     struct rb_node pq_node;              /* node for event queue */
 185     unsigned long pq_key;       /* the same type as jiffies global */
 186
 187     int prio_activity;          /* for which prios are we active */
 188     enum htb_cmode cmode;       /* current mode of the class */
 189
 190     /* class attached filters */
 191     struct tcf_proto *filter_list;
 192     int filter_cnt;
 193
 194     int warned;         /* only one warning about non work conserving .. */
 195
 196     /* token bucket parameters */
 197     struct qdisc_rate_table *rate;      /* rate table of the class itself */
 198     struct qdisc_rate_table *ceil;      /* ceiling rate (limits borrows too) */
 199     long buffer,cbuffer;                /* token bucket depth/rate */
 200     long mbuffer;                       /* max wait time */
 201     long tokens,ctokens;                /* current number of tokens */
 202     psched_time_t t_c;                  /* checkpoint time */
 203 };
 204
 205 /* TODO: maybe compute rate when size is too large .. or drop ? */
 206 static __inline__ long L2T(struct htb_class *cl,struct qdisc_rate_table *rate,
 207         int size)
 208 {
 209     int slot = size >> rate->rate.cell_log;
 210     if (slot > 255) {
 211         cl->xstats.giants++;
 212         slot = 255;
 213     }
 214     return rate->data[slot];
 215 }
 216
 217 struct htb_sched
 218 {
 219     struct list_head root;                      /* root classes list */
 220     struct list_head hash[HTB_HSIZE];           /* hashed by classid */
 221     struct list_head drops[TC_HTB_NUMPRIO];     /* active leaves (for drops) */
 222
 223     /* self list - roots of self generating tree */
 224     struct rb_root row[TC_HTB_MAXDEPTH][TC_HTB_NUMPRIO];
 225     int row_mask[TC_HTB_MAXDEPTH];
 226     struct rb_node *ptr[TC_HTB_MAXDEPTH][TC_HTB_NUMPRIO];
 227     u32 last_ptr_id[TC_HTB_MAXDEPTH][TC_HTB_NUMPRIO];
 228
 229     /* self wait list - roots of wait PQs per row */
 230     struct rb_root wait_pq[TC_HTB_MAXDEPTH];
 231
 232     /* time of nearest event per level (row) */
 233     unsigned long near_ev_cache[TC_HTB_MAXDEPTH];
 234
 235     /* cached value of jiffies in dequeue */
 236     unsigned long jiffies;
 237
 238     /* whether we hit non-work conserving class during this dequeue; we use */
 239     int nwc_hit;        /* this to disable mindelay complaint in dequeue */
 240
 241     int defcls;         /* class where unclassified flows go to */
 242     u32 debug;          /* subsystem debug levels */
 243
 244     /* filters for qdisc itself */
 245     struct tcf_proto *filter_list;
 246     int filter_cnt;
 247
 248     int rate2quantum;           /* quant = rate / rate2quantum */
 249     psched_time_t now;          /* cached dequeue time */
 250     struct timer_list timer;    /* send delay timer */
 251 #ifdef HTB_RATECM
 252     struct timer_list rttim;    /* rate computer timer */
 253     int recmp_bucket;           /* which hash bucket to recompute next */
 254 #endif
 255
 256     /* non shaped skbs; let them go directly thru */
 257     struct sk_buff_head direct_queue;
 258     int direct_qlen;  /* max qlen of above */
 259
 260     long direct_pkts;
 261 };
 262
 263 /* compute hash of size HTB_HSIZE for given handle */
 264 static __inline__ int htb_hash(u32 h)
 265 {
 266 #if HTB_HSIZE != 16
 267  #error "Declare new hash for your HTB_HSIZE"
 268 #endif
 269     h ^= h>>8;  /* stolen from cbq_hash */
 270     h ^= h>>4;
 271     return h & 0xf;
 272 }
 273
 274 /* find class in global hash table using given handle */
 275 static __inline__ struct htb_class *htb_find(u32 handle, struct Qdisc *sch)
 276 {
 277         struct htb_sched *q = qdisc_priv(sch);
 278         struct list_head *p;
 279         if (TC_H_MAJ(handle) != sch->handle)
 280                 return NULL;
 281
 282         list_for_each (p,q->hash+htb_hash(handle)) {
 283                 struct htb_class *cl = list_entry(p,struct htb_class,hlist);
 284                 if (cl->classid == handle)
 285                         return cl;
 286         }
 287         return NULL;
 288 }
 289
 290 /**
 291  * htb_classify - classify a packet into class
 292  *
 293  * It returns NULL if the packet should be dropped or -1 if the packet
 294  * should be passed directly thru. In all other cases leaf class is returned.
 295  * We allow direct class selection by classid in priority. The we examine
 296  * filters in qdisc and in inner nodes (if higher filter points to the inner
 297  * node). If we end up with classid MAJOR:0 we enqueue the skb into special
 298  * internal fifo (direct). These packets then go directly thru. If we still
 299  * have no valid leaf we try to use MAJOR:default leaf. It still unsuccessfull
 300  * then finish and return direct queue.
 301  */
 302 #define HTB_DIRECT (struct htb_class*)-1
 303 static inline u32 htb_classid(struct htb_class *cl)
 304 {
 305         return (cl && cl != HTB_DIRECT) ? cl->classid : TC_H_UNSPEC;
 306 }
 307
 308 static struct htb_class *htb_classify(struct sk_buff *skb, struct Qdisc *sch, int *qres)
 309 {
 310         struct htb_sched *q = qdisc_priv(sch);
 311         struct htb_class *cl;
 312         struct tcf_result res;
 313         struct tcf_proto *tcf;
 314         int result;
 315
 316         /* allow to select class by setting skb->priority to valid classid;
 317            note that nfmark can be used too by attaching filter fw with no
 318            rules in it */
 319         if (skb->priority == sch->handle)
 320                 return HTB_DIRECT;  /* X:0 (direct flow) selected */
 321         if ((cl = htb_find(skb->priority,sch)) != NULL && cl->level == 0)
 322                 return cl;
 323
 324         tcf = q->filter_list;
 325         while (tcf && (result = tc_classify(skb, tcf, &res)) >= 0) {
 326 #ifdef CONFIG_NET_CLS_ACT
 327                 int terminal = 0;
 328                 switch (result) {
 329                 case TC_ACT_SHOT: /* Stop and kfree */
 330                         *qres = NET_XMIT_DROP;
 331                         terminal = 1;
 332                         break;
 333                 case TC_ACT_QUEUED:
 334                 case TC_ACT_STOLEN:
 335                         terminal = 1;
 336                         break;
 337                 case TC_ACT_RECLASSIFY:  /* Things look good */
 338                 case TC_ACT_OK:
 339                 case TC_ACT_UNSPEC:
 340                 default:
 341                 break;
 342                 }
 343
 344                 if (terminal) {
 345                         kfree_skb(skb);
 346                         return NULL;
 347                 }
 348 #else
 349 #ifdef CONFIG_NET_CLS_POLICE
 350                 if (result == TC_POLICE_SHOT)
 351                         return NULL;
 352 #endif
 353 #endif
 354                 if ((cl = (void*)res.class) == NULL) {
 355                         if (res.classid == sch->handle)
 356                                 return HTB_DIRECT;  /* X:0 (direct flow) */
 357                         if ((cl = htb_find(res.classid,sch)) == NULL)
 358                                 break; /* filter selected invalid classid */
 359                 }
 360                 if (!cl->level)
 361                         return cl; /* we hit leaf; return it */
 362
 363                 /* we have got inner class; apply inner filter chain */
 364                 tcf = cl->filter_list;
 365         }
 366         /* classification failed; try to use default class */
 367         cl = htb_find(TC_H_MAKE(TC_H_MAJ(sch->handle),q->defcls),sch);
 368         if (!cl || cl->level)
 369                 return HTB_DIRECT; /* bad default .. this is safe bet */
 370         return cl;
 371 }
 372
 373 #ifdef HTB_DEBUG
 374 static void htb_next_rb_node(struct rb_node **n);
 375 #define HTB_DUMTREE(root,memb) if(root) { \
 376         struct rb_node *n = (root)->rb_node; \
 377         while (n->rb_left) n = n->rb_left; \
 378         while (n) { \
 379                 struct htb_class *cl = rb_entry(n, struct htb_class, memb); \
 380                 printk(" %x",cl->classid); htb_next_rb_node (&n); \
 381         } }
 382
 383 static void htb_debug_dump (struct htb_sched *q)
 384 {
 385         int i,p;
 386         printk(KERN_DEBUG "htb*g j=%lu lj=%lu\n",jiffies,q->jiffies);
 387         /* rows */
 388         for (i=TC_HTB_MAXDEPTH-1;i>=0;i--) {
 389                 printk(KERN_DEBUG "htb*r%d m=%x",i,q->row_mask[i]);
 390                 for (p=0;p<TC_HTB_NUMPRIO;p++) {
 391                         if (!q->row[i][p].rb_node) continue;
 392                         printk(" p%d:",p);
 393                         HTB_DUMTREE(q->row[i]+p,node[p]);
 394                 }
 395                 printk("\n");
 396         }
 397         /* classes */
 398         for (i = 0; i < HTB_HSIZE; i++) {
 399                 struct list_head *l;
 400                 list_for_each (l,q->hash+i) {
 401                         struct htb_class *cl = list_entry(l,struct htb_class,hlist);
 402                         long diff = PSCHED_TDIFF_SAFE(q->now, cl->t_c, (u32)cl->mbuffer);
 403                         printk(KERN_DEBUG "htb*c%x m=%d t=%ld c=%ld pq=%lu df=%ld ql=%d "
 404                                         "pa=%x f:",
 405                                 cl->classid,cl->cmode,cl->tokens,cl->ctokens,
 406                                 cl->pq_node.rb_color==-1?0:cl->pq_key,diff,
 407                                 cl->level?0:cl->un.leaf.q->q.qlen,cl->prio_activity);
 408                         if (cl->level)
 409                         for (p=0;p<TC_HTB_NUMPRIO;p++) {
 410                                 if (!cl->un.inner.feed[p].rb_node) continue;
 411                                 printk(" p%d a=%x:",p,cl->un.inner.ptr[p]?rb_entry(cl->un.inner.ptr[p], struct htb_class,node[p])->classid:0);
 412                                 HTB_DUMTREE(cl->un.inner.feed+p,node[p]);
 413                         }
 414                         printk("\n");
 415                 }
 416         }
 417 }
 418 #endif
 419 /**
 420  * htb_add_to_id_tree - adds class to the round robin list
 421  *
 422  * Routine adds class to the list (actually tree) sorted by classid.
 423  * Make sure that class is not already on such list for given prio.
 424  */
 425 static void htb_add_to_id_tree (HTB_ARGQ struct rb_root *root,
 426                 struct htb_class *cl,int prio)
 427 {
 428         struct rb_node **p = &root->rb_node, *parent = NULL;
 429         HTB_DBG(7,3,"htb_add_id_tree cl=%X prio=%d\n",cl->classid,prio);
 430 #ifdef HTB_DEBUG
 431         if (cl->node[prio].rb_color != -1) { BUG_TRAP(0); return; }
 432         HTB_CHCL(cl);
 433         if (*p) {
 434                 struct htb_class *x = rb_entry(*p,struct htb_class,node[prio]);
 435                 HTB_CHCL(x);
 436         }
 437 #endif
 438         while (*p) {
 439                 struct htb_class *c; parent = *p;
 440                 c = rb_entry(parent, struct htb_class, node[prio]);
 441                 HTB_CHCL(c);
 442                 if (cl->classid > c->classid)
 443                         p = &parent->rb_right;
 444                 else
 445                         p = &parent->rb_left;
 446         }
 447         rb_link_node(&cl->node[prio], parent, p);
 448         rb_insert_color(&cl->node[prio], root);
 449 }
 450
 451 /**
 452  * htb_add_to_wait_tree - adds class to the event queue with delay
 453  *
 454  * The class is added to priority event queue to indicate that class will
 455  * change its mode in cl->pq_key microseconds. Make sure that class is not
 456  * already in the queue.
 457  */
 458 static void htb_add_to_wait_tree (struct htb_sched *q,
 459                 struct htb_class *cl,long delay,int debug_hint)
 460 {
 461         struct rb_node **p = &q->wait_pq[cl->level].rb_node, *parent = NULL;
 462         HTB_DBG(7,3,"htb_add_wt cl=%X key=%lu\n",cl->classid,cl->pq_key);
 463 #ifdef HTB_DEBUG
 464         if (cl->pq_node.rb_color != -1) { BUG_TRAP(0); return; }
 465         HTB_CHCL(cl);
 466         if ((delay <= 0 || delay > cl->mbuffer) && net_ratelimit())
 467                 printk(KERN_ERR "HTB: suspicious delay in wait_tree d=%ld cl=%X h=%d\n",delay,cl->classid,debug_hint);
 468 #endif
 469         cl->pq_key = q->jiffies + PSCHED_US2JIFFIE(delay);
 470         if (cl->pq_key == q->jiffies)
 471                 cl->pq_key++;
 472
 473         /* update the nearest event cache */
 474         if (time_after(q->near_ev_cache[cl->level], cl->pq_key))
 475                 q->near_ev_cache[cl->level] = cl->pq_key;
 476
 477         while (*p) {
 478                 struct htb_class *c; parent = *p;
 479                 c = rb_entry(parent, struct htb_class, pq_node);
 480                 if (time_after_eq(cl->pq_key, c->pq_key))
 481                         p = &parent->rb_right;
 482                 else
 483                         p = &parent->rb_left;
 484         }
 485         rb_link_node(&cl->pq_node, parent, p);
 486         rb_insert_color(&cl->pq_node, &q->wait_pq[cl->level]);
 487 }
 488
 489 /**
 490  * htb_next_rb_node - finds next node in binary tree
 491  *
 492  * When we are past last key we return NULL.
 493  * Average complexity is 2 steps per call.
 494  */
 495 static void htb_next_rb_node(struct rb_node **n)
 496 {
 497         *n = rb_next(*n);
 498 }
 499
 500 /**
 501  * htb_add_class_to_row - add class to its row
 502  *
 503  * The class is added to row at priorities marked in mask.
 504  * It does nothing if mask == 0.
 505  */
 506 static inline void htb_add_class_to_row(struct htb_sched *q,
 507                 struct htb_class *cl,int mask)
 508 {
 509         HTB_DBG(7,2,"htb_addrow cl=%X mask=%X rmask=%X\n",
 510                         cl->classid,mask,q->row_mask[cl->level]);
 511         HTB_CHCL(cl);
 512         q->row_mask[cl->level] |= mask;
 513         while (mask) {
 514                 int prio = ffz(~mask);
 515                 mask &= ~(1 << prio);
 516                 htb_add_to_id_tree(HTB_PASSQ q->row[cl->level]+prio,cl,prio);
 517         }
 518 }
 519
 520 /**
 521  * htb_remove_class_from_row - removes class from its row
 522  *
 523  * The class is removed from row at priorities marked in mask.
 524  * It does nothing if mask == 0.
 525  */
 526 static __inline__ void htb_remove_class_from_row(struct htb_sched *q,
 527                 struct htb_class *cl,int mask)
 528 {
 529         int m = 0;
 530         HTB_CHCL(cl);
 531         while (mask) {
 532                 int prio = ffz(~mask);
 533                 mask &= ~(1 << prio);
 534                 if (q->ptr[cl->level][prio] == cl->node+prio)
 535                         htb_next_rb_node(q->ptr[cl->level]+prio);
 536                 htb_safe_rb_erase(cl->node + prio,q->row[cl->level]+prio);
 537                 if (!q->row[cl->level][prio].rb_node)
 538                         m |= 1 << prio;
 539         }
 540         HTB_DBG(7,2,"htb_delrow cl=%X mask=%X rmask=%X maskdel=%X\n",
 541                         cl->classid,mask,q->row_mask[cl->level],m);
 542         q->row_mask[cl->level] &= ~m;
 543 }
 544
 545 /**
 546  * htb_activate_prios - creates active classe's feed chain
 547  *
 548  * The class is connected to ancestors and/or appropriate rows
 549  * for priorities it is participating on. cl->cmode must be new
 550  * (activated) mode. It does nothing if cl->prio_activity == 0.
 551  */
 552 static void htb_activate_prios(struct htb_sched *q,struct htb_class *cl)
 553 {
 554         struct htb_class *p = cl->parent;
 555         long m,mask = cl->prio_activity;
 556         HTB_DBG(7,2,"htb_act_prios cl=%X mask=%lX cmode=%d\n",cl->classid,mask,cl->cmode);
 557         HTB_CHCL(cl);
 558
 559         while (cl->cmode == HTB_MAY_BORROW && p && mask) {
 560                 HTB_CHCL(p);
 561                 m = mask; while (m) {
 562                         int prio = ffz(~m);
 563                         m &= ~(1 << prio);
 564
 565                         if (p->un.inner.feed[prio].rb_node)
 566                                 /* parent already has its feed in use so that
 567                                    reset bit in mask as parent is already ok */
 568                                 mask &= ~(1 << prio);
 569
 570                         htb_add_to_id_tree(HTB_PASSQ p->un.inner.feed+prio,cl,prio);
 571                 }
 572                 HTB_DBG(7,3,"htb_act_pr_aft p=%X pact=%X mask=%lX pmode=%d\n",
 573                                 p->classid,p->prio_activity,mask,p->cmode);
 574                 p->prio_activity |= mask;
 575                 cl = p; p = cl->parent;
 576                 HTB_CHCL(cl);
 577         }
 578         if (cl->cmode == HTB_CAN_SEND && mask)
 579                 htb_add_class_to_row(q,cl,mask);
 580 }
 581
 582 /**
 583  * htb_deactivate_prios - remove class from feed chain
 584  *
 585  * cl->cmode must represent old mode (before deactivation). It does
 586  * nothing if cl->prio_activity == 0. Class is removed from all feed
 587  * chains and rows.
 588  */
 589 static void htb_deactivate_prios(struct htb_sched *q, struct htb_class *cl)
 590 {
 591         struct htb_class *p = cl->parent;
 592         long m,mask = cl->prio_activity;
 593         HTB_DBG(7,2,"htb_deact_prios cl=%X mask=%lX cmode=%d\n",cl->classid,mask,cl->cmode);
 594         HTB_CHCL(cl);
 595
 596         while (cl->cmode == HTB_MAY_BORROW && p && mask) {
 597                 m = mask; mask = 0;
 598                 while (m) {
 599                         int prio = ffz(~m);
 600                         m &= ~(1 << prio);
 601
 602                         if (p->un.inner.ptr[prio] == cl->node+prio) {
 603                                 /* we are removing child which is pointed to from
 604                                    parent feed - forget the pointer but remember
 605                                    classid */
 606                                 p->un.inner.last_ptr_id[prio] = cl->classid;
 607                                 p->un.inner.ptr[prio] = NULL;
 608                         }
 609
 610                         htb_safe_rb_erase(cl->node + prio,p->un.inner.feed + prio);
 611
 612                         if (!p->un.inner.feed[prio].rb_node)
 613                                 mask |= 1 << prio;
 614                 }
 615                 HTB_DBG(7,3,"htb_deact_pr_aft p=%X pact=%X mask=%lX pmode=%d\n",
 616                                 p->classid,p->prio_activity,mask,p->cmode);
 617                 p->prio_activity &= ~mask;
 618                 cl = p; p = cl->parent;
 619                 HTB_CHCL(cl);
 620         }
 621         if (cl->cmode == HTB_CAN_SEND && mask)
 622                 htb_remove_class_from_row(q,cl,mask);
 623 }
 624
 625 /**
 626  * htb_class_mode - computes and returns current class mode
 627  *
 628  * It computes cl's mode at time cl->t_c+diff and returns it. If mode
 629  * is not HTB_CAN_SEND then cl->pq_key is updated to time difference
 630  * from now to time when cl will change its state.
 631  * Also it is worth to note that class mode doesn't change simply
 632  * at cl->{c,}tokens == 0 but there can rather be hysteresis of
 633  * 0 .. -cl->{c,}buffer range. It is meant to limit number of
 634  * mode transitions per time unit. The speed gain is about 1/6.
 635  */
 636 static __inline__ enum htb_cmode
 637 htb_class_mode(struct htb_class *cl,long *diff)
 638 {
 639     long toks;
 640
 641     if ((toks = (cl->ctokens + *diff)) < (
 642 #if HTB_HYSTERESIS
 643             cl->cmode != HTB_CANT_SEND ? -cl->cbuffer :
 644 #endif
 645             0)) {
 646             *diff = -toks;
 647             return HTB_CANT_SEND;
 648     }
 649     if ((toks = (cl->tokens + *diff)) >= (
 650 #if HTB_HYSTERESIS
 651             cl->cmode == HTB_CAN_SEND ? -cl->buffer :
 652 #endif
 653             0))
 654             return HTB_CAN_SEND;
 655
 656     *diff = -toks;
 657     return HTB_MAY_BORROW;
 658 }
 659
 660 /**
 661  * htb_change_class_mode - changes classe's mode
 662  *
 663  * This should be the only way how to change classe's mode under normal
 664  * cirsumstances. Routine will update feed lists linkage, change mode
 665  * and add class to the wait event queue if appropriate. New mode should
 666  * be different from old one and cl->pq_key has to be valid if changing
 667  * to mode other than HTB_CAN_SEND (see htb_add_to_wait_tree).
 668  */
 669 static void
 670 htb_change_class_mode(struct htb_sched *q, struct htb_class *cl, long *diff)
 671 {
 672         enum htb_cmode new_mode = htb_class_mode(cl,diff);
 673
 674         HTB_CHCL(cl);
 675         HTB_DBG(7,1,"htb_chging_clmode %d->%d cl=%X\n",cl->cmode,new_mode,cl->classid);
 676
 677         if (new_mode == cl->cmode)
 678                 return;
 679
 680         if (cl->prio_activity) { /* not necessary: speed optimization */
 681                 if (cl->cmode != HTB_CANT_SEND)
 682                         htb_deactivate_prios(q,cl);
 683                 cl->cmode = new_mode;
 684                 if (new_mode != HTB_CANT_SEND)
 685                         htb_activate_prios(q,cl);
 686         } else
 687                 cl->cmode = new_mode;
 688 }
 689
 690 /**
 691  * htb_activate - inserts leaf cl into appropriate active feeds
 692  *
 693  * Routine learns (new) priority of leaf and activates feed chain
 694  * for the prio. It can be called on already active leaf safely.
 695  * It also adds leaf into droplist.
 696  */
 697 static __inline__ void htb_activate(struct htb_sched *q,struct htb_class *cl)
 698 {
 699         BUG_TRAP(!cl->level && cl->un.leaf.q && cl->un.leaf.q->q.qlen);
 700         HTB_CHCL(cl);
 701         if (!cl->prio_activity) {
 702                 cl->prio_activity = 1 << (cl->un.leaf.aprio = cl->un.leaf.prio);
 703                 htb_activate_prios(q,cl);
 704                 list_add_tail(&cl->un.leaf.drop_list,q->drops+cl->un.leaf.aprio);
 705         }
 706 }
 707
 708 /**
 709  * htb_deactivate - remove leaf cl from active feeds
 710  *
 711  * Make sure that leaf is active. In the other words it can't be called
 712  * with non-active leaf. It also removes class from the drop list.
 713  */
 714 static __inline__ void
 715 htb_deactivate(struct htb_sched *q,struct htb_class *cl)
 716 {
 717         BUG_TRAP(cl->prio_activity);
 718         HTB_CHCL(cl);
 719         htb_deactivate_prios(q,cl);
 720         cl->prio_activity = 0;
 721         list_del_init(&cl->un.leaf.drop_list);
 722 }
 723
 724 static int htb_enqueue(struct sk_buff *skb, struct Qdisc *sch)
 725 {
 726     int ret = NET_XMIT_SUCCESS;
 727     struct htb_sched *q = qdisc_priv(sch);
 728     struct htb_class *cl = htb_classify(skb,sch,&ret);
 729
 730
 731 #ifdef CONFIG_NET_CLS_ACT
 732     if (cl == HTB_DIRECT ) {
 733         if (q->direct_queue.qlen < q->direct_qlen ) {
 734             __skb_queue_tail(&q->direct_queue, skb);
 735             q->direct_pkts++;
 736         }
 737     } else if (!cl) {
 738             if (NET_XMIT_DROP == ret) {
 739                     sch->qstats.drops++;
 740             }
 741             return ret;
 742     }
 743 #else
 744     if (cl == HTB_DIRECT || !cl) {
 745         /* enqueue to helper queue */
 746         if (q->direct_queue.qlen < q->direct_qlen && cl) {
 747             __skb_queue_tail(&q->direct_queue, skb);
 748             q->direct_pkts++;
 749         } else {
 750             kfree_skb (skb);
 751             sch->qstats.drops++;
 752             return NET_XMIT_DROP;
 753         }
 754     }
 755 #endif
 756     else if (cl->un.leaf.q->enqueue(skb, cl->un.leaf.q) != NET_XMIT_SUCCESS) {
 757         sch->qstats.drops++;
 758         cl->qstats.drops++;
 759         return NET_XMIT_DROP;
 760     } else {
 761         cl->bstats.packets++; cl->bstats.bytes += skb->len;
 762         htb_activate (q,cl);
 763     }
 764
 765     sch->q.qlen++;
 766     sch->bstats.packets++; sch->bstats.bytes += skb->len;
 767     HTB_DBG(1,1,"htb_enq_ok cl=%X skb=%p\n",(cl && cl != HTB_DIRECT)?cl->classid:0,skb);
 768     return NET_XMIT_SUCCESS;
 769 }
 770
 771 /* TODO: requeuing packet charges it to policers again !! */
 772 static int htb_requeue(struct sk_buff *skb, struct Qdisc *sch)
 773 {
 774     struct htb_sched *q = qdisc_priv(sch);
 775     int ret =  NET_XMIT_SUCCESS;
 776     struct htb_class *cl = htb_classify(skb,sch, &ret);
 777     struct sk_buff *tskb;
 778
 779     if (cl == HTB_DIRECT || !cl) {
 780         /* enqueue to helper queue */
 781         if (q->direct_queue.qlen < q->direct_qlen && cl) {
 782             __skb_queue_head(&q->direct_queue, skb);
 783         } else {
 784             __skb_queue_head(&q->direct_queue, skb);
 785             tskb = __skb_dequeue_tail(&q->direct_queue);
 786             kfree_skb (tskb);
 787             sch->qstats.drops++;
 788             return NET_XMIT_CN;
 789         }
 790     } else if (cl->un.leaf.q->ops->requeue(skb, cl->un.leaf.q) != NET_XMIT_SUCCESS) {
 791         sch->qstats.drops++;
 792         cl->qstats.drops++;
 793         return NET_XMIT_DROP;
 794     } else
 795             htb_activate (q,cl);
 796
 797     sch->q.qlen++;
 798     sch->qstats.requeues++;
 799     HTB_DBG(1,1,"htb_req_ok cl=%X skb=%p\n",(cl && cl != HTB_DIRECT)?cl->classid:0,skb);
 800     return NET_XMIT_SUCCESS;
 801 }
 802
 803 static void htb_timer(unsigned long arg)
 804 {
 805     struct Qdisc *sch = (struct Qdisc*)arg;
 806     sch->flags &= ~TCQ_F_THROTTLED;
 807     wmb();
 808     netif_schedule(sch->dev);
 809 }
 810
 811 #ifdef HTB_RATECM
 812 #define RT_GEN(D,R) R+=D-(R/HTB_EWMAC);D=0
 813 static void htb_rate_timer(unsigned long arg)
 814 {
 815         struct Qdisc *sch = (struct Qdisc*)arg;
 816         struct htb_sched *q = qdisc_priv(sch);
 817         struct list_head *p;
 818
 819         /* lock queue so that we can muck with it */
 820         HTB_QLOCK(sch);
 821         HTB_DBG(10,1,"htb_rttmr j=%ld\n",jiffies);
 822
 823         q->rttim.expires = jiffies + HZ;
 824         add_timer(&q->rttim);
 825
 826         /* scan and recompute one bucket at time */
 827         if (++q->recmp_bucket >= HTB_HSIZE)
 828                 q->recmp_bucket = 0;
 829         list_for_each (p,q->hash+q->recmp_bucket) {
 830                 struct htb_class *cl = list_entry(p,struct htb_class,hlist);
 831                 HTB_DBG(10,2,"htb_rttmr_cl cl=%X sbyte=%lu spkt=%lu\n",
 832                                 cl->classid,cl->sum_bytes,cl->sum_packets);
 833                 RT_GEN (cl->sum_bytes,cl->rate_bytes);
 834                 RT_GEN (cl->sum_packets,cl->rate_packets);
 835         }
 836         HTB_QUNLOCK(sch);
 837 }
 838 #endif
 839
 840 /**
 841  * htb_charge_class - charges amount "bytes" to leaf and ancestors
 842  *
 843  * Routine assumes that packet "bytes" long was dequeued from leaf cl
 844  * borrowing from "level". It accounts bytes to ceil leaky bucket for
 845  * leaf and all ancestors and to rate bucket for ancestors at levels
 846  * "level" and higher. It also handles possible change of mode resulting
 847  * from the update. Note that mode can also increase here (MAY_BORROW to
 848  * CAN_SEND) because we can use more precise clock that event queue here.
 849  * In such case we remove class from event queue first.
 850  */
 851 static void htb_charge_class(struct htb_sched *q,struct htb_class *cl,
 852                 int level,int bytes)
 853 {
 854         long toks,diff;
 855         enum htb_cmode old_mode;
 856         HTB_DBG(5,1,"htb_chrg_cl cl=%X lev=%d len=%d\n",cl->classid,level,bytes);
 857
 858 #define HTB_ACCNT(T,B,R) toks = diff + cl->T; \
 859         if (toks > cl->B) toks = cl->B; \
 860         toks -= L2T(cl, cl->R, bytes); \
 861         if (toks <= -cl->mbuffer) toks = 1-cl->mbuffer; \
 862         cl->T = toks
 863
 864         while (cl) {
 865                 HTB_CHCL(cl);
 866                 diff = PSCHED_TDIFF_SAFE(q->now, cl->t_c, (u32)cl->mbuffer);
 867 #ifdef HTB_DEBUG
 868                 if (diff > cl->mbuffer || diff < 0 || PSCHED_TLESS(q->now, cl->t_c)) {
 869                         if (net_ratelimit())
 870                                 printk(KERN_ERR "HTB: bad diff in charge, cl=%X diff=%lX now=%Lu then=%Lu j=%lu\n",
 871                                        cl->classid, diff,
 872 #ifdef CONFIG_NET_SCH_CLK_GETTIMEOFDAY
 873                                        q->now.tv_sec * 1000000ULL + q->now.tv_usec,
 874                                        cl->t_c.tv_sec * 1000000ULL + cl->t_c.tv_usec,
 875 #else
 876                                        (unsigned long long) q->now,
 877                                        (unsigned long long) cl->t_c,
 878 #endif
 879                                        q->jiffies);
 880                         diff = 1000;
 881                 }
 882 #endif
 883                 if (cl->level >= level) {
 884                         if (cl->level == level) cl->xstats.lends++;
 885                         HTB_ACCNT (tokens,buffer,rate);
 886                 } else {
 887                         cl->xstats.borrows++;
 888                         cl->tokens += diff; /* we moved t_c; update tokens */
 889                 }
 890                 HTB_ACCNT (ctokens,cbuffer,ceil);
 891                 cl->t_c = q->now;
 892                 HTB_DBG(5,2,"htb_chrg_clp cl=%X diff=%ld tok=%ld ctok=%ld\n",cl->classid,diff,cl->tokens,cl->ctokens);
 893
 894                 old_mode = cl->cmode; diff = 0;
 895                 htb_change_class_mode(q,cl,&diff);
 896                 if (old_mode != cl->cmode) {
 897                         if (old_mode != HTB_CAN_SEND)
 898                                 htb_safe_rb_erase(&cl->pq_node,q->wait_pq+cl->level);
 899                         if (cl->cmode != HTB_CAN_SEND)
 900                                 htb_add_to_wait_tree (q,cl,diff,1);
 901                 }
 902
 903 #ifdef HTB_RATECM
 904                 /* update rate counters */
 905                 cl->sum_bytes += bytes; cl->sum_packets++;
 906 #endif
 907
 908                 /* update byte stats except for leaves which are already updated */
 909                 if (cl->level) {
 910                         cl->bstats.bytes += bytes;
 911                         cl->bstats.packets++;
 912                 }
 913                 cl = cl->parent;
 914         }
 915 }
 916
 917 /**
 918  * htb_do_events - make mode changes to classes at the level
 919  *
 920  * Scans event queue for pending events and applies them. Returns jiffies to
 921  * next pending event (0 for no event in pq).
 922  * Note: Aplied are events whose have cl->pq_key <= jiffies.
 923  */
 924 static long htb_do_events(struct htb_sched *q,int level)
 925 {
 926         int i;
 927         HTB_DBG(8,1,"htb_do_events l=%d root=%p rmask=%X\n",
 928                         level,q->wait_pq[level].rb_node,q->row_mask[level]);
 929         for (i = 0; i < 500; i++) {
 930                 struct htb_class *cl;
 931                 long diff;
 932                 struct rb_node *p = q->wait_pq[level].rb_node;
 933                 if (!p) return 0;
 934                 while (p->rb_left) p = p->rb_left;
 935
 936                 cl = rb_entry(p, struct htb_class, pq_node);
 937                 if (time_after(cl->pq_key, q->jiffies)) {
 938                         HTB_DBG(8,3,"htb_do_ev_ret delay=%ld\n",cl->pq_key - q->jiffies);
 939                         return cl->pq_key - q->jiffies;
 940                 }
 941                 htb_safe_rb_erase(p,q->wait_pq+level);
 942                 diff = PSCHED_TDIFF_SAFE(q->now, cl->t_c, (u32)cl->mbuffer);
 943 #ifdef HTB_DEBUG
 944                 if (diff > cl->mbuffer || diff < 0 || PSCHED_TLESS(q->now, cl->t_c)) {
 945                         if (net_ratelimit())
 946                                 printk(KERN_ERR "HTB: bad diff in events, cl=%X diff=%lX now=%Lu then=%Lu j=%lu\n",
 947                                        cl->classid, diff,
 948 #ifdef CONFIG_NET_SCH_CLK_GETTIMEOFDAY
 949                                        q->now.tv_sec * 1000000ULL + q->now.tv_usec,
 950                                        cl->t_c.tv_sec * 1000000ULL + cl->t_c.tv_usec,
 951 #else
 952                                        (unsigned long long) q->now,
 953                                        (unsigned long long) cl->t_c,
 954 #endif
 955                                        q->jiffies);
 956                         diff = 1000;
 957                 }
 958 #endif
 959                 htb_change_class_mode(q,cl,&diff);
 960                 if (cl->cmode != HTB_CAN_SEND)
 961                         htb_add_to_wait_tree (q,cl,diff,2);
 962         }
 963         if (net_ratelimit())
 964                 printk(KERN_WARNING "htb: too many events !\n");
 965         return HZ/10;
 966 }
 967
 968 /* Returns class->node+prio from id-tree where classe's id is >= id. NULL
 969    is no such one exists. */
 970 static struct rb_node *
 971 htb_id_find_next_upper(int prio,struct rb_node *n,u32 id)
 972 {
 973         struct rb_node *r = NULL;
 974         while (n) {
 975                 struct htb_class *cl = rb_entry(n,struct htb_class,node[prio]);
 976                 if (id == cl->classid) return n;
 977
 978                 if (id > cl->classid) {
 979                         n = n->rb_right;
 980                 } else {
 981                         r = n;
 982                         n = n->rb_left;
 983                 }
 984         }
 985         return r;
 986 }
 987
 988 /**
 989  * htb_lookup_leaf - returns next leaf class in DRR order
 990  *
 991  * Find leaf where current feed pointers points to.
 992  */
 993 static struct htb_class *
 994 htb_lookup_leaf(HTB_ARGQ struct rb_root *tree,int prio,struct rb_node **pptr,u32 *pid)
 995 {
 996         int i;
 997         struct {
 998                 struct rb_node *root;
 999                 struct rb_node **pptr;
1000                 u32 *pid;
1001         } stk[TC_HTB_MAXDEPTH],*sp = stk;
1002
1003         BUG_TRAP(tree->rb_node);
1004         sp->root = tree->rb_node;
1005         sp->pptr = pptr;
1006         sp->pid = pid;
1007
1008         for (i = 0; i < 65535; i++) {
1009                 HTB_DBG(4,2,"htb_lleaf ptr=%p pid=%X\n",*sp->pptr,*sp->pid);
1010
1011                 if (!*sp->pptr && *sp->pid) {
1012                         /* ptr was invalidated but id is valid - try to recover
1013                            the original or next ptr */
1014                         *sp->pptr = htb_id_find_next_upper(prio,sp->root,*sp->pid);
1015                 }
1016                 *sp->pid = 0; /* ptr is valid now so that remove this hint as it
1017                                  can become out of date quickly */
1018                 if (!*sp->pptr) { /* we are at right end; rewind & go up */
1019                         *sp->pptr = sp->root;
1020                         while ((*sp->pptr)->rb_left)
1021                                 *sp->pptr = (*sp->pptr)->rb_left;
1022                         if (sp > stk) {
1023                                 sp--;
1024                                 BUG_TRAP(*sp->pptr); if(!*sp->pptr) return NULL;
1025                                 htb_next_rb_node (sp->pptr);
1026                         }
1027                 } else {
1028                         struct htb_class *cl;
1029                         cl = rb_entry(*sp->pptr,struct htb_class,node[prio]);
1030                         HTB_CHCL(cl);
1031                         if (!cl->level)
1032                                 return cl;
1033                         (++sp)->root = cl->un.inner.feed[prio].rb_node;
1034                         sp->pptr = cl->un.inner.ptr+prio;
1035                         sp->pid = cl->un.inner.last_ptr_id+prio;
1036                 }
1037         }
1038         BUG_TRAP(0);
1039         return NULL;
1040 }
1041
1042 /* dequeues packet at given priority and level; call only if
1043    you are sure that there is active class at prio/level */
1044 static struct sk_buff *
1045 htb_dequeue_tree(struct htb_sched *q,int prio,int level)
1046 {
1047         struct sk_buff *skb = NULL;
1048         struct htb_class *cl,*start;
1049         /* look initial class up in the row */
1050         start = cl = htb_lookup_leaf (HTB_PASSQ q->row[level]+prio,prio,
1051                         q->ptr[level]+prio,q->last_ptr_id[level]+prio);
1052
1053         do {
1054 next:
1055                 BUG_TRAP(cl);
1056                 if (!cl) return NULL;
1057                 HTB_DBG(4,1,"htb_deq_tr prio=%d lev=%d cl=%X defic=%d\n",
1058                                 prio,level,cl->classid,cl->un.leaf.deficit[level]);
1059
1060                 /* class can be empty - it is unlikely but can be true if leaf
1061                    qdisc drops packets in enqueue routine or if someone used
1062                    graft operation on the leaf since last dequeue;
1063                    simply deactivate and skip such class */
1064                 if (unlikely(cl->un.leaf.q->q.qlen == 0)) {
1065                         struct htb_class *next;
1066                         htb_deactivate(q,cl);
1067
1068                         /* row/level might become empty */
1069                         if ((q->row_mask[level] & (1 << prio)) == 0)
1070                                 return NULL;
1071
1072                         next = htb_lookup_leaf (HTB_PASSQ q->row[level]+prio,
1073                                         prio,q->ptr[level]+prio,q->last_ptr_id[level]+prio);
1074
1075                         if (cl == start) /* fix start if we just deleted it */
1076                                 start = next;
1077                         cl = next;
1078                         goto next;
1079                 }
1080
1081                 if (likely((skb = cl->un.leaf.q->dequeue(cl->un.leaf.q)) != NULL))
1082                         break;
1083                 if (!cl->warned) {
1084                         printk(KERN_WARNING "htb: class %X isn't work conserving ?!\n",cl->classid);
1085                         cl->warned = 1;
1086                 }
1087                 q->nwc_hit++;
1088                 htb_next_rb_node((level?cl->parent->un.inner.ptr:q->ptr[0])+prio);
1089                 cl = htb_lookup_leaf (HTB_PASSQ q->row[level]+prio,prio,q->ptr[level]+prio,
1090                                 q->last_ptr_id[level]+prio);
1091
1092         } while (cl != start);
1093
1094         if (likely(skb != NULL)) {
1095                 if ((cl->un.leaf.deficit[level] -= skb->len) < 0) {
1096                         HTB_DBG(4,2,"htb_next_cl oldptr=%p quant_add=%d\n",
1097                                 level?cl->parent->un.inner.ptr[prio]:q->ptr[0][prio],cl->un.leaf.quantum);
1098                         cl->un.leaf.deficit[level] += cl->un.leaf.quantum;
1099                         htb_next_rb_node((level?cl->parent->un.inner.ptr:q->ptr[0])+prio);
1100                 }
1101                 /* this used to be after charge_class but this constelation
1102                    gives us slightly better performance */
1103                 if (!cl->un.leaf.q->q.qlen)
1104                         htb_deactivate (q,cl);
1105                 htb_charge_class (q,cl,level,skb->len);
1106         }
1107         return skb;
1108 }
1109
1110 static void htb_delay_by(struct Qdisc *sch,long delay)
1111 {
1112         struct htb_sched *q = qdisc_priv(sch);
1113         if (delay <= 0) delay = 1;
1114         if (unlikely(delay > 5*HZ)) {
1115                 if (net_ratelimit())
1116                         printk(KERN_INFO "HTB delay %ld > 5sec\n", delay);
1117                 delay = 5*HZ;
1118         }
1119         /* why don't use jiffies here ? because expires can be in past */
1120         mod_timer(&q->timer, q->jiffies + delay);
1121         sch->flags |= TCQ_F_THROTTLED;
1122         sch->qstats.overlimits++;
1123         HTB_DBG(3,1,"htb_deq t_delay=%ld\n",delay);
1124 }
1125
1126 static struct sk_buff *htb_dequeue(struct Qdisc *sch)
1127 {
1128         struct sk_buff *skb = NULL;
1129         struct htb_sched *q = qdisc_priv(sch);
1130         int level;
1131         long min_delay;
1132 #ifdef HTB_DEBUG
1133         int evs_used = 0;
1134 #endif
1135
1136         q->jiffies = jiffies;
1137         HTB_DBG(3,1,"htb_deq dircnt=%d qlen=%d\n",skb_queue_len(&q->direct_queue),
1138                         sch->q.qlen);
1139
1140         /* try to dequeue direct packets as high prio (!) to minimize cpu work */
1141         if ((skb = __skb_dequeue(&q->direct_queue)) != NULL) {
1142                 sch->flags &= ~TCQ_F_THROTTLED;
1143                 sch->q.qlen--;
1144                 return skb;
1145         }
1146
1147         if (!sch->q.qlen) goto fin;
1148         PSCHED_GET_TIME(q->now);
1149
1150         min_delay = LONG_MAX;
1151         q->nwc_hit = 0;
1152         for (level = 0; level < TC_HTB_MAXDEPTH; level++) {
1153                 /* common case optimization - skip event handler quickly */
1154                 int m;
1155                 long delay;
1156                 if (time_after_eq(q->jiffies, q->near_ev_cache[level])) {
1157                         delay = htb_do_events(q,level);
1158                         q->near_ev_cache[level] = q->jiffies + (delay ? delay : HZ);
1159 #ifdef HTB_DEBUG
1160                         evs_used++;
1161 #endif
1162                 } else
1163                         delay = q->near_ev_cache[level] - q->jiffies;
1164
1165                 if (delay && min_delay > delay)
1166                         min_delay = delay;
1167                 m = ~q->row_mask[level];
1168                 while (m != (int)(-1)) {
1169                         int prio = ffz (m);
1170                         m |= 1 << prio;
1171                         skb = htb_dequeue_tree(q,prio,level);
1172                         if (likely(skb != NULL)) {
1173                                 sch->q.qlen--;
1174                                 sch->flags &= ~TCQ_F_THROTTLED;
1175                                 goto fin;
1176                         }
1177                 }
1178         }
1179 #ifdef HTB_DEBUG
1180         if (!q->nwc_hit && min_delay >= 10*HZ && net_ratelimit()) {
1181                 if (min_delay == LONG_MAX) {
1182                         printk(KERN_ERR "HTB: dequeue bug (%d,%lu,%lu), report it please !\n",
1183                                         evs_used,q->jiffies,jiffies);
1184                         htb_debug_dump(q);
1185                 } else
1186                         printk(KERN_WARNING "HTB: mindelay=%ld, some class has "
1187                                         "too small rate\n",min_delay);
1188         }
1189 #endif
1190         htb_delay_by (sch,min_delay > 5*HZ ? 5*HZ : min_delay);
1191 fin:
1192         HTB_DBG(3,1,"htb_deq_end %s j=%lu skb=%p\n",sch->dev->name,q->jiffies,skb);
1193         return skb;
1194 }
1195
1196 /* try to drop from each class (by prio) until one succeed */
1197 static unsigned int htb_drop(struct Qdisc* sch)
1198 {
1199         struct htb_sched *q = qdisc_priv(sch);
1200         int prio;
1201
1202         for (prio = TC_HTB_NUMPRIO - 1; prio >= 0; prio--) {
1203                 struct list_head *p;
1204                 list_for_each (p,q->drops+prio) {
1205                         struct htb_class *cl = list_entry(p, struct htb_class,
1206                                                           un.leaf.drop_list);
1207                         unsigned int len;
1208                         if (cl->un.leaf.q->ops->drop &&
1209                                 (len = cl->un.leaf.q->ops->drop(cl->un.leaf.q))) {
1210                                 sch->q.qlen--;
1211                                 if (!cl->un.leaf.q->q.qlen)
1212                                         htb_deactivate (q,cl);
1213                                 return len;
1214                         }
1215                 }
1216         }
1217         return 0;
1218 }
1219
1220 /* reset all classes */
1221 /* always caled under BH & queue lock */
1222 static void htb_reset(struct Qdisc* sch)
1223 {
1224         struct htb_sched *q = qdisc_priv(sch);
1225         int i;
1226         HTB_DBG(0,1,"htb_reset sch=%p, handle=%X\n",sch,sch->handle);
1227
1228         for (i = 0; i < HTB_HSIZE; i++) {
1229                 struct list_head *p;
1230                 list_for_each (p,q->hash+i) {
1231                         struct htb_class *cl = list_entry(p,struct htb_class,hlist);
1232                         if (cl->level)
1233                                 memset(&cl->un.inner,0,sizeof(cl->un.inner));
1234                         else {
1235                                 if (cl->un.leaf.q)
1236                                         qdisc_reset(cl->un.leaf.q);
1237                                 INIT_LIST_HEAD(&cl->un.leaf.drop_list);
1238                         }
1239                         cl->prio_activity = 0;
1240                         cl->cmode = HTB_CAN_SEND;
1241 #ifdef HTB_DEBUG
1242                         cl->pq_node.rb_color = -1;
1243                         memset(cl->node,255,sizeof(cl->node));
1244 #endif
1245
1246                 }
1247         }
1248         sch->flags &= ~TCQ_F_THROTTLED;
1249         del_timer(&q->timer);
1250         __skb_queue_purge(&q->direct_queue);
1251         sch->q.qlen = 0;
1252         memset(q->row,0,sizeof(q->row));
1253         memset(q->row_mask,0,sizeof(q->row_mask));
1254         memset(q->wait_pq,0,sizeof(q->wait_pq));
1255         memset(q->ptr,0,sizeof(q->ptr));
1256         for (i = 0; i < TC_HTB_NUMPRIO; i++)
1257                 INIT_LIST_HEAD(q->drops+i);
1258 }
1259
1260 static int htb_init(struct Qdisc *sch, struct rtattr *opt)
1261 {
1262         struct htb_sched *q = qdisc_priv(sch);
1263         struct rtattr *tb[TCA_HTB_INIT];
1264         struct tc_htb_glob *gopt;
1265         int i;
1266 #ifdef HTB_DEBUG
1267         printk(KERN_INFO "HTB init, kernel part version %d.%d\n",
1268                           HTB_VER >> 16,HTB_VER & 0xffff);
1269 #endif
1270         if (!opt || rtattr_parse(tb, TCA_HTB_INIT, RTA_DATA(opt), RTA_PAYLOAD(opt)) ||
1271                         tb[TCA_HTB_INIT-1] == NULL ||
1272                         RTA_PAYLOAD(tb[TCA_HTB_INIT-1]) < sizeof(*gopt)) {
1273                 printk(KERN_ERR "HTB: hey probably you have bad tc tool ?\n");
1274                 return -EINVAL;
1275         }
1276         gopt = RTA_DATA(tb[TCA_HTB_INIT-1]);
1277         if (gopt->version != HTB_VER >> 16) {
1278                 printk(KERN_ERR "HTB: need tc/htb version %d (minor is %d), you have %d\n",
1279                                 HTB_VER >> 16,HTB_VER & 0xffff,gopt->version);
1280                 return -EINVAL;
1281         }
1282         q->debug = gopt->debug;
1283         HTB_DBG(0,1,"htb_init sch=%p handle=%X r2q=%d\n",sch,sch->handle,gopt->rate2quantum);
1284
1285         INIT_LIST_HEAD(&q->root);
1286         for (i = 0; i < HTB_HSIZE; i++)
1287                 INIT_LIST_HEAD(q->hash+i);
1288         for (i = 0; i < TC_HTB_NUMPRIO; i++)
1289                 INIT_LIST_HEAD(q->drops+i);
1290
1291         init_timer(&q->timer);
1292         skb_queue_head_init(&q->direct_queue);
1293
1294         q->direct_qlen = sch->dev->tx_queue_len;
1295         if (q->direct_qlen < 2) /* some devices have zero tx_queue_len */
1296                 q->direct_qlen = 2;
1297         q->timer.function = htb_timer;
1298         q->timer.data = (unsigned long)sch;
1299
1300 #ifdef HTB_RATECM
1301         init_timer(&q->rttim);
1302         q->rttim.function = htb_rate_timer;
1303         q->rttim.data = (unsigned long)sch;
1304         q->rttim.expires = jiffies + HZ;
1305         add_timer(&q->rttim);
1306 #endif
1307         if ((q->rate2quantum = gopt->rate2quantum) < 1)
1308                 q->rate2quantum = 1;
1309         q->defcls = gopt->defcls;
1310
1311         return 0;
1312 }
1313
1314 static int htb_dump(struct Qdisc *sch, struct sk_buff *skb)
1315 {
1316         struct htb_sched *q = qdisc_priv(sch);
1317         unsigned char    *b = skb->tail;
1318         struct rtattr *rta;
1319         struct tc_htb_glob gopt;
1320         HTB_DBG(0,1,"htb_dump sch=%p, handle=%X\n",sch,sch->handle);
1321         HTB_QLOCK(sch);
1322         gopt.direct_pkts = q->direct_pkts;
1323
1324 #ifdef HTB_DEBUG
1325         if (HTB_DBG_COND(0,2))
1326                 htb_debug_dump(q);
1327 #endif
1328         gopt.version = HTB_VER;
1329         gopt.rate2quantum = q->rate2quantum;
1330         gopt.defcls = q->defcls;
1331         gopt.debug = q->debug;
1332         rta = (struct rtattr*)b;
1333         RTA_PUT(skb, TCA_OPTIONS, 0, NULL);
1334         RTA_PUT(skb, TCA_HTB_INIT, sizeof(gopt), &gopt);
1335         rta->rta_len = skb->tail - b;
1336         HTB_QUNLOCK(sch);
1337         return skb->len;
1338 rtattr_failure:
1339         HTB_QUNLOCK(sch);
1340         skb_trim(skb, skb->tail - skb->data);
1341         return -1;
1342 }
1343
1344 static int htb_dump_class(struct Qdisc *sch, unsigned long arg,
1345         struct sk_buff *skb, struct tcmsg *tcm)
1346 {
1347 #ifdef HTB_DEBUG
1348         struct htb_sched *q = qdisc_priv(sch);
1349 #endif
1350         struct htb_class *cl = (struct htb_class*)arg;
1351         unsigned char    *b = skb->tail;
1352         struct rtattr *rta;
1353         struct tc_htb_opt opt;
1354
1355         HTB_DBG(0,1,"htb_dump_class handle=%X clid=%X\n",sch->handle,cl->classid);
1356
1357         HTB_QLOCK(sch);
1358         tcm->tcm_parent = cl->parent ? cl->parent->classid : TC_H_ROOT;
1359         tcm->tcm_handle = cl->classid;
1360         if (!cl->level && cl->un.leaf.q)
1361                 tcm->tcm_info = cl->un.leaf.q->handle;
1362
1363         rta = (struct rtattr*)b;
1364         RTA_PUT(skb, TCA_OPTIONS, 0, NULL);
1365
1366         memset (&opt,0,sizeof(opt));
1367
1368         opt.rate = cl->rate->rate; opt.buffer = cl->buffer;
1369         opt.ceil = cl->ceil->rate; opt.cbuffer = cl->cbuffer;
1370         opt.quantum = cl->un.leaf.quantum; opt.prio = cl->un.leaf.prio;
1371         opt.level = cl->level;
1372         RTA_PUT(skb, TCA_HTB_PARMS, sizeof(opt), &opt);
1373         rta->rta_len = skb->tail - b;
1374         HTB_QUNLOCK(sch);
1375         return skb->len;
1376 rtattr_failure:
1377         HTB_QUNLOCK(sch);
1378         skb_trim(skb, b - skb->data);
1379         return -1;
1380 }
1381
1382 static int
1383 htb_dump_class_stats(struct Qdisc *sch, unsigned long arg,
1384         struct gnet_dump *d)
1385 {
1386         struct htb_class *cl = (struct htb_class*)arg;
1387
1388 #ifdef HTB_RATECM
1389         cl->rate_est.bps = cl->rate_bytes/(HTB_EWMAC*HTB_HSIZE);
1390         cl->rate_est.pps = cl->rate_packets/(HTB_EWMAC*HTB_HSIZE);
1391 #endif
1392
1393         if (!cl->level && cl->un.leaf.q)
1394                 cl->qstats.qlen = cl->un.leaf.q->q.qlen;
1395         cl->xstats.tokens = cl->tokens;
1396         cl->xstats.ctokens = cl->ctokens;
1397
1398         if (gnet_stats_copy_basic(d, &cl->bstats) < 0 ||
1399             gnet_stats_copy_rate_est(d, &cl->rate_est) < 0 ||
1400             gnet_stats_copy_queue(d, &cl->qstats) < 0)
1401                 return -1;
1402
1403         return gnet_stats_copy_app(d, &cl->xstats, sizeof(cl->xstats));
1404 }
1405
1406 static int htb_graft(struct Qdisc *sch, unsigned long arg, struct Qdisc *new,
1407         struct Qdisc **old)
1408 {
1409         struct htb_class *cl = (struct htb_class*)arg;
1410
1411         if (cl && !cl->level) {
1412                 if (new == NULL && (new = qdisc_create_dflt(sch->dev,
1413                                         &pfifo_qdisc_ops)) == NULL)
1414                                         return -ENOBUFS;
1415                 sch_tree_lock(sch);
1416                 if ((*old = xchg(&cl->un.leaf.q, new)) != NULL) {
1417                         if (cl->prio_activity)
1418                                 htb_deactivate (qdisc_priv(sch),cl);
1419
1420                         /* TODO: is it correct ? Why CBQ doesn't do it ? */
1421                         sch->q.qlen -= (*old)->q.qlen;
1422                         qdisc_reset(*old);
1423                 }
1424                 sch_tree_unlock(sch);
1425                 return 0;
1426         }
1427         return -ENOENT;
1428 }
1429
1430 static struct Qdisc * htb_leaf(struct Qdisc *sch, unsigned long arg)
1431 {
1432         struct htb_class *cl = (struct htb_class*)arg;
1433         return (cl && !cl->level) ? cl->un.leaf.q : NULL;
1434 }
1435
1436 static unsigned long htb_get(struct Qdisc *sch, u32 classid)
1437 {
1438 #ifdef HTB_DEBUG
1439         struct htb_sched *q = qdisc_priv(sch);
1440 #endif
1441         struct htb_class *cl = htb_find(classid,sch);
1442         HTB_DBG(0,1,"htb_get clid=%X q=%p cl=%p ref=%d\n",classid,q,cl,cl?cl->refcnt:0);
1443         if (cl)
1444                 cl->refcnt++;
1445         return (unsigned long)cl;
1446 }
1447
1448 static void htb_destroy_filters(struct tcf_proto **fl)
1449 {
1450         struct tcf_proto *tp;
1451
1452         while ((tp = *fl) != NULL) {
1453                 *fl = tp->next;
1454                 tcf_destroy(tp);
1455         }
1456 }
1457
1458 static void htb_destroy_class(struct Qdisc* sch,struct htb_class *cl)
1459 {
1460         struct htb_sched *q = qdisc_priv(sch);
1461         HTB_DBG(0,1,"htb_destrycls clid=%X ref=%d\n", cl?cl->classid:0,cl?cl->refcnt:0);
1462         if (!cl->level) {
1463                 BUG_TRAP(cl->un.leaf.q);
1464                 sch->q.qlen -= cl->un.leaf.q->q.qlen;
1465                 qdisc_destroy(cl->un.leaf.q);
1466         }
1467         qdisc_put_rtab(cl->rate);
1468         qdisc_put_rtab(cl->ceil);
1469
1470         htb_destroy_filters (&cl->filter_list);
1471
1472         while (!list_empty(&cl->children))
1473                 htb_destroy_class (sch,list_entry(cl->children.next,
1474                                         struct htb_class,sibling));
1475
1476         /* note: this delete may happen twice (see htb_delete) */
1477         list_del(&cl->hlist);
1478         list_del(&cl->sibling);
1479
1480         if (cl->prio_activity)
1481                 htb_deactivate (q,cl);
1482
1483         if (cl->cmode != HTB_CAN_SEND)
1484                 htb_safe_rb_erase(&cl->pq_node,q->wait_pq+cl->level);
1485
1486         kfree(cl);
1487 }
1488
1489 /* always caled under BH & queue lock */
1490 static void htb_destroy(struct Qdisc* sch)
1491 {
1492         struct htb_sched *q = qdisc_priv(sch);
1493         HTB_DBG(0,1,"htb_destroy q=%p\n",q);
1494
1495         del_timer_sync (&q->timer);
1496 #ifdef HTB_RATECM
1497         del_timer_sync (&q->rttim);
1498 #endif
1499         /* This line used to be after htb_destroy_class call below
1500            and surprisingly it worked in 2.4. But it must precede it
1501            because filter need its target class alive to be able to call
1502            unbind_filter on it (without Oops). */
1503         htb_destroy_filters(&q->filter_list);
1504
1505         while (!list_empty(&q->root))
1506                 htb_destroy_class (sch,list_entry(q->root.next,
1507                                         struct htb_class,sibling));
1508
1509         __skb_queue_purge(&q->direct_queue);
1510 }
1511
1512 static int htb_delete(struct Qdisc *sch, unsigned long arg)
1513 {
1514         struct htb_sched *q = qdisc_priv(sch);
1515         struct htb_class *cl = (struct htb_class*)arg;
1516         HTB_DBG(0,1,"htb_delete q=%p cl=%X ref=%d\n",q,cl?cl->classid:0,cl?cl->refcnt:0);
1517
1518         // TODO: why don't allow to delete subtree ? references ? does
1519         // tc subsys quarantee us that in htb_destroy it holds no class
1520         // refs so that we can remove children safely there ?
1521         if (!list_empty(&cl->children) || cl->filter_cnt)
1522                 return -EBUSY;
1523
1524         sch_tree_lock(sch);
1525
1526         /* delete from hash and active; remainder in destroy_class */
1527         list_del_init(&cl->hlist);
1528         if (cl->prio_activity)
1529                 htb_deactivate (q,cl);
1530
1531         if (--cl->refcnt == 0)
1532                 htb_destroy_class(sch,cl);
1533
1534         sch_tree_unlock(sch);
1535         return 0;
1536 }
1537
1538 static void htb_put(struct Qdisc *sch, unsigned long arg)
1539 {
1540 #ifdef HTB_DEBUG
1541         struct htb_sched *q = qdisc_priv(sch);
1542 #endif
1543         struct htb_class *cl = (struct htb_class*)arg;
1544         HTB_DBG(0,1,"htb_put q=%p cl=%X ref=%d\n",q,cl?cl->classid:0,cl?cl->refcnt:0);
1545
1546         if (--cl->refcnt == 0)
1547                 htb_destroy_class(sch,cl);
1548 }
1549
1550 static int htb_change_class(struct Qdisc *sch, u32 classid,
1551                 u32 parentid, struct rtattr **tca, unsigned long *arg)
1552 {
1553         int err = -EINVAL;
1554         struct htb_sched *q = qdisc_priv(sch);
1555         struct htb_class *cl = (struct htb_class*)*arg,*parent;
1556         struct rtattr *opt = tca[TCA_OPTIONS-1];
1557         struct qdisc_rate_table *rtab = NULL, *ctab = NULL;
1558         struct rtattr *tb[TCA_HTB_RTAB];
1559         struct tc_htb_opt *hopt;
1560
1561         /* extract all subattrs from opt attr */
1562         if (!opt || rtattr_parse(tb, TCA_HTB_RTAB, RTA_DATA(opt), RTA_PAYLOAD(opt)) ||
1563                         tb[TCA_HTB_PARMS-1] == NULL ||
1564                         RTA_PAYLOAD(tb[TCA_HTB_PARMS-1]) < sizeof(*hopt))
1565                 goto failure;
1566
1567         parent = parentid == TC_H_ROOT ? NULL : htb_find (parentid,sch);
1568
1569         hopt = RTA_DATA(tb[TCA_HTB_PARMS-1]);
1570         HTB_DBG(0,1,"htb_chg cl=%p(%X), clid=%X, parid=%X, opt/prio=%d, rate=%u, buff=%d, quant=%d\n", cl,cl?cl->classid:0,classid,parentid,(int)hopt->prio,hopt->rate.rate,hopt->buffer,hopt->quantum);
1571         rtab = qdisc_get_rtab(&hopt->rate, tb[TCA_HTB_RTAB-1]);
1572         ctab = qdisc_get_rtab(&hopt->ceil, tb[TCA_HTB_CTAB-1]);
1573         if (!rtab || !ctab) goto failure;
1574
1575         if (!cl) { /* new class */
1576                 struct Qdisc *new_q;
1577                 /* check for valid classid */
1578                 if (!classid || TC_H_MAJ(classid^sch->handle) || htb_find(classid,sch))
1579                         goto failure;
1580
1581                 /* check maximal depth */
1582                 if (parent && parent->parent && parent->parent->level < 2) {
1583                         printk(KERN_ERR "htb: tree is too deep\n");
1584                         goto failure;
1585                 }
1586                 err = -ENOBUFS;
1587                 if ((cl = kmalloc(sizeof(*cl), GFP_KERNEL)) == NULL)
1588                         goto failure;
1589
1590                 memset(cl, 0, sizeof(*cl));
1591                 cl->refcnt = 1;
1592                 INIT_LIST_HEAD(&cl->sibling);
1593                 INIT_LIST_HEAD(&cl->hlist);
1594                 INIT_LIST_HEAD(&cl->children);
1595                 INIT_LIST_HEAD(&cl->un.leaf.drop_list);
1596 #ifdef HTB_DEBUG
1597                 cl->magic = HTB_CMAGIC;
1598 #endif
1599
1600                 /* create leaf qdisc early because it uses kmalloc(GFP_KERNEL)
1601                    so that can't be used inside of sch_tree_lock
1602                    -- thanks to Karlis Peisenieks */
1603                 new_q = qdisc_create_dflt(sch->dev, &pfifo_qdisc_ops);
1604                 sch_tree_lock(sch);
1605                 if (parent && !parent->level) {
1606                         /* turn parent into inner node */
1607                         sch->q.qlen -= parent->un.leaf.q->q.qlen;
1608                         qdisc_destroy (parent->un.leaf.q);
1609                         if (parent->prio_activity)
1610                                 htb_deactivate (q,parent);
1611
1612                         /* remove from evt list because of level change */
1613                         if (parent->cmode != HTB_CAN_SEND) {
1614                                 htb_safe_rb_erase(&parent->pq_node,q->wait_pq /*+0*/);
1615                                 parent->cmode = HTB_CAN_SEND;
1616                         }
1617                         parent->level = (parent->parent ? parent->parent->level
1618                                         : TC_HTB_MAXDEPTH) - 1;
1619                         memset (&parent->un.inner,0,sizeof(parent->un.inner));
1620                 }
1621                 /* leaf (we) needs elementary qdisc */
1622                 cl->un.leaf.q = new_q ? new_q : &noop_qdisc;
1623
1624                 cl->classid = classid; cl->parent = parent;
1625
1626                 /* set class to be in HTB_CAN_SEND state */
1627                 cl->tokens = hopt->buffer;
1628                 cl->ctokens = hopt->cbuffer;
1629                 cl->mbuffer = 60000000; /* 1min */
1630                 PSCHED_GET_TIME(cl->t_c);
1631                 cl->cmode = HTB_CAN_SEND;
1632
1633                 /* attach to the hash list and parent's family */
1634                 list_add_tail(&cl->hlist, q->hash+htb_hash(classid));
1635                 list_add_tail(&cl->sibling, parent ? &parent->children : &q->root);
1636 #ifdef HTB_DEBUG
1637                 {
1638                         int i;
1639                         for (i = 0; i < TC_HTB_NUMPRIO; i++) cl->node[i].rb_color = -1;
1640                         cl->pq_node.rb_color = -1;
1641                 }
1642 #endif
1643         } else sch_tree_lock(sch);
1644
1645         /* it used to be a nasty bug here, we have to check that node
1646            is really leaf before changing cl->un.leaf ! */
1647         if (!cl->level) {
1648                 cl->un.leaf.quantum = rtab->rate.rate / q->rate2quantum;
1649                 if (!hopt->quantum && cl->un.leaf.quantum < 1000) {
1650                         printk(KERN_WARNING "HTB: quantum of class %X is small. Consider r2q change.\n", cl->classid);
1651                         cl->un.leaf.quantum = 1000;
1652                 }
1653                 if (!hopt->quantum && cl->un.leaf.quantum > 200000) {
1654                         printk(KERN_WARNING "HTB: quantum of class %X is big. Consider r2q change.\n", cl->classid);
1655                         cl->un.leaf.quantum = 200000;
1656                 }
1657                 if (hopt->quantum)
1658                         cl->un.leaf.quantum = hopt->quantum;
1659                 if ((cl->un.leaf.prio = hopt->prio) >= TC_HTB_NUMPRIO)
1660                         cl->un.leaf.prio = TC_HTB_NUMPRIO - 1;
1661         }
1662
1663         cl->buffer = hopt->buffer;
1664         cl->cbuffer = hopt->cbuffer;
1665         if (cl->rate) qdisc_put_rtab(cl->rate); cl->rate = rtab;
1666         if (cl->ceil) qdisc_put_rtab(cl->ceil); cl->ceil = ctab;
1667         sch_tree_unlock(sch);
1668
1669         *arg = (unsigned long)cl;
1670         return 0;
1671
1672 failure:
1673         if (rtab) qdisc_put_rtab(rtab);
1674         if (ctab) qdisc_put_rtab(ctab);
1675         return err;
1676 }
1677
1678 static struct tcf_proto **htb_find_tcf(struct Qdisc *sch, unsigned long arg)
1679 {
1680         struct htb_sched *q = qdisc_priv(sch);
1681         struct htb_class *cl = (struct htb_class *)arg;
1682         struct tcf_proto **fl = cl ? &cl->filter_list : &q->filter_list;
1683         HTB_DBG(0,2,"htb_tcf q=%p clid=%X fref=%d fl=%p\n",q,cl?cl->classid:0,cl?cl->filter_cnt:q->filter_cnt,*fl);
1684         return fl;
1685 }
1686
1687 static unsigned long htb_bind_filter(struct Qdisc *sch, unsigned long parent,
1688         u32 classid)
1689 {
1690         struct htb_sched *q = qdisc_priv(sch);
1691         struct htb_class *cl = htb_find (classid,sch);
1692         HTB_DBG(0,2,"htb_bind q=%p clid=%X cl=%p fref=%d\n",q,classid,cl,cl?cl->filter_cnt:q->filter_cnt);
1693         /*if (cl && !cl->level) return 0;
1694           The line above used to be there to prevent attaching filters to
1695           leaves. But at least tc_index filter uses this just to get class
1696           for other reasons so that we have to allow for it.
1697           ----
1698           19.6.2002 As Werner explained it is ok - bind filter is just
1699           another way to "lock" the class - unlike "get" this lock can
1700           be broken by class during destroy IIUC.
1701          */
1702         if (cl)
1703                 cl->filter_cnt++;
1704         else
1705                 q->filter_cnt++;
1706         return (unsigned long)cl;
1707 }
1708
1709 static void htb_unbind_filter(struct Qdisc *sch, unsigned long arg)
1710 {
1711         struct htb_sched *q = qdisc_priv(sch);
1712         struct htb_class *cl = (struct htb_class *)arg;
1713         HTB_DBG(0,2,"htb_unbind q=%p cl=%p fref=%d\n",q,cl,cl?cl->filter_cnt:q->filter_cnt);
1714         if (cl)
1715                 cl->filter_cnt--;
1716         else
1717                 q->filter_cnt--;
1718 }
1719
1720 static void htb_walk(struct Qdisc *sch, struct qdisc_walker *arg)
1721 {
1722         struct htb_sched *q = qdisc_priv(sch);
1723         int i;
1724
1725         if (arg->stop)
1726                 return;
1727
1728         for (i = 0; i < HTB_HSIZE; i++) {
1729                 struct list_head *p;
1730                 list_for_each (p,q->hash+i) {
1731                         struct htb_class *cl = list_entry(p,struct htb_class,hlist);
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 struct Qdisc_class_ops htb_class_ops = {
1746         .graft          =       htb_graft,
1747         .leaf           =       htb_leaf,
1748         .get            =       htb_get,
1749         .put            =       htb_put,
1750         .change         =       htb_change_class,
1751         .delete         =       htb_delete,
1752         .walk           =       htb_walk,
1753         .tcf_chain      =       htb_find_tcf,
1754         .bind_tcf       =       htb_bind_filter,
1755         .unbind_tcf     =       htb_unbind_filter,
1756         .dump           =       htb_dump_class,
1757         .dump_stats     =       htb_dump_class_stats,
1758 };
1759
1760 static struct Qdisc_ops htb_qdisc_ops = {
1761         .next           =       NULL,
1762         .cl_ops         =       &htb_class_ops,
1763         .id             =       "htb",
1764         .priv_size      =       sizeof(struct htb_sched),
1765         .enqueue        =       htb_enqueue,
1766         .dequeue        =       htb_dequeue,
1767         .requeue        =       htb_requeue,
1768         .drop           =       htb_drop,
1769         .init           =       htb_init,
1770         .reset          =       htb_reset,
1771         .destroy        =       htb_destroy,
1772         .change         =       NULL /* htb_change */,
1773         .dump           =       htb_dump,
1774         .owner          =       THIS_MODULE,
1775 };
1776
1777 static int __init htb_module_init(void)
1778 {
1779     return register_qdisc(&htb_qdisc_ops);
1780 }
1781 static void __exit htb_module_exit(void)
1782 {
1783     unregister_qdisc(&htb_qdisc_ops);
1784 }
1785 module_init(htb_module_init)
1786 module_exit(htb_module_exit)
1787 MODULE_LICENSE("GPL");