2 * net/sched/sch_htb.c Hierarchical token bucket, feed tree version
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.
9 * Authors: Martin Devera, <devik@cdi.cz>
11 * Credits (in time order) for older HTB versions:
12 * Ondrej Kraus, <krauso@barr.cz>
13 * found missing INIT_QDISC(htb)
14 * Vladimir Smelhaus, Aamer Akhter, Bert Hubert
15 * helped a lot to locate nasty class stall bug
16 * Andi Kleen, Jamal Hadi, Bert Hubert
17 * code review and helpful comments on shaping
18 * Tomasz Wrona, <tw@eter.tym.pl>
19 * created test case so that I was able to fix nasty bug
20 * and many others. thanks.
22 * $Id: sch_htb.c,v 1.1.1.1 2005/04/11 02:51:14 jack Exp $
24 #include <linux/config.h>
25 #include <linux/module.h>
26 #include <asm/uaccess.h>
27 #include <asm/system.h>
28 #include <asm/bitops.h>
29 #include <linux/types.h>
30 #include <linux/kernel.h>
31 #include <linux/version.h>
32 #include <linux/sched.h>
33 #include <linux/string.h>
35 #include <linux/socket.h>
36 #include <linux/sockios.h>
38 #include <linux/errno.h>
39 #include <linux/interrupt.h>
40 #include <linux/if_ether.h>
41 #include <linux/inet.h>
42 #include <linux/netdevice.h>
43 #include <linux/etherdevice.h>
44 #include <linux/notifier.h>
46 #include <net/route.h>
47 #include <linux/skbuff.h>
48 #include <linux/list.h>
49 #include <linux/compiler.h>
51 #include <net/pkt_sched.h>
52 #include <linux/rbtree.h>
56 ========================================================================
57 HTB is like TBF with multiple classes. It is also similar to CBQ because
58 it allows to assign priority to each class in hierarchy.
59 In fact it is another implementation of Floyd's formal sharing.
62 Each class is assigned level. Leaf has ALWAYS level 0 and root
63 classes have level TC_HTB_MAXDEPTH-1. Interior nodes has level
64 one less than their parent.
67 #define HTB_HSIZE 16 /* classid hash size */
68 #define HTB_EWMAC 2 /* rate average over HTB_EWMAC*HTB_HSIZE sec */
69 #define HTB_DEBUG 1 /* compile debugging support (activated by tc tool) */
70 #define HTB_RATECM 1 /* whether to use rate computer */
71 #define HTB_HYSTERESIS 1/* whether to use mode hysteresis for speedup */
72 #define HTB_QLOCK(S) spin_lock_bh(&(S)->dev->queue_lock)
73 #define HTB_QUNLOCK(S) spin_unlock_bh(&(S)->dev->queue_lock)
74 #define HTB_VER 0x30007 /* major must be matched with number suplied by TC as version */
76 #if HTB_VER >> 16 != TC_HTB_PROTOVER
77 #error "Mismatched sch_htb.c and pkt_sch.h"
80 /* temporary debug defines to be removed after beta stage */
82 #define DEVIK_MSTART(N)
84 /* debugging support; S is subsystem, these are defined:
89 4 - dequeue one prio DRR part
90 5 - dequeue class accounting
91 6 - class overlimit status computation
96 12 - fast dequeue cache
98 L is level; 0 = none, 1 = basic info, 2 = detailed, 3 = full
99 q->debug uint32 contains 16 2-bit fields one for subsystem starting
103 #define HTB_DBG(S,L,FMT,ARG...) if (((q->debug>>(2*S))&3) >= L) \
104 printk(KERN_DEBUG FMT,##ARG)
105 #define HTB_CHCL(cl) BUG_TRAP((cl)->magic == HTB_CMAGIC)
107 #define HTB_ARGQ struct htb_sched *q,
111 #define HTB_CMAGIC 0xFEFAFEF1
112 #define htb_safe_rb_erase(N,R) do { BUG_TRAP((N)->rb_color != -1); \
113 if ((N)->rb_color == -1) break; \
115 (N)->rb_color = -1; } while (0)
117 #define HTB_DBG(S,L,FMT,ARG...)
121 #define htb_safe_rb_erase(N,R) rb_erase(N,R)
125 /* used internaly to keep status of single class */
127 HTB_CANT_SEND, /* class can't send and can't borrow */
128 HTB_MAY_BORROW, /* class can't send but may borrow */
129 HTB_CAN_SEND /* class can send */
132 /* interior & leaf nodes; props specific to leaves are marked L: */
138 /* general class parameters */
140 struct tc_stats stats; /* generic stats */
141 struct tc_htb_xstats xstats;/* our special stats */
142 int refcnt; /* usage count of this class */
145 /* rate measurement counters */
146 unsigned long rate_bytes,sum_bytes;
147 unsigned long rate_packets,sum_packets;
151 int level; /* our level (see above) */
152 struct htb_class *parent; /* parent class */
153 struct list_head hlist; /* classid hash list item */
154 struct list_head sibling; /* sibling list item */
155 struct list_head children; /* children list */
158 struct htb_class_leaf {
163 int deficit[TC_HTB_MAXDEPTH];
164 struct list_head drop_list;
166 struct htb_class_inner {
167 rb_root_t feed[TC_HTB_NUMPRIO]; /* feed trees */
168 rb_node_t *ptr[TC_HTB_NUMPRIO]; /* current class ptr */
171 rb_node_t node[TC_HTB_NUMPRIO]; /* node for self or feed tree */
172 rb_node_t pq_node; /* node for event queue */
173 unsigned long pq_key; /* the same type as jiffies global */
175 int prio_activity; /* for which prios are we active */
176 enum htb_cmode cmode; /* current mode of the class */
178 /* class attached filters */
179 struct tcf_proto *filter_list;
182 int warned; /* only one warning about non work conserving .. */
184 /* token bucket parameters */
185 struct qdisc_rate_table *rate; /* rate table of the class itself */
186 struct qdisc_rate_table *ceil; /* ceiling rate (limits borrows too) */
187 long buffer,cbuffer; /* token bucket depth/rate */
188 long mbuffer; /* max wait time */
189 long tokens,ctokens; /* current number of tokens */
190 psched_time_t t_c; /* checkpoint time */
193 /* TODO: maybe compute rate when size is too large .. or drop ? */
194 static __inline__ long L2T(struct htb_class *cl,struct qdisc_rate_table *rate,
197 int slot = size >> rate->rate.cell_log;
202 return rate->data[slot];
207 struct list_head root; /* root classes list */
208 struct list_head hash[HTB_HSIZE]; /* hashed by classid */
209 struct list_head drops[TC_HTB_NUMPRIO]; /* active leaves (for drops) */
211 /* self list - roots of self generating tree */
212 rb_root_t row[TC_HTB_MAXDEPTH][TC_HTB_NUMPRIO];
213 int row_mask[TC_HTB_MAXDEPTH];
214 rb_node_t *ptr[TC_HTB_MAXDEPTH][TC_HTB_NUMPRIO];
216 /* self wait list - roots of wait PQs per row */
217 rb_root_t wait_pq[TC_HTB_MAXDEPTH];
219 /* time of nearest event per level (row) */
220 unsigned long near_ev_cache[TC_HTB_MAXDEPTH];
222 /* whether we hit non-work conserving class during this dequeue; we use */
223 int nwc_hit; /* this to disable mindelay complaint in dequeue */
225 int defcls; /* class where unclassified flows go to */
226 u32 debug; /* subsystem debug levels */
228 /* filters for qdisc itself */
229 struct tcf_proto *filter_list;
232 int rate2quantum; /* quant = rate / rate2quantum */
233 psched_time_t now; /* cached dequeue time */
234 struct timer_list timer; /* send delay timer */
236 struct timer_list rttim; /* rate computer timer */
237 int recmp_bucket; /* which hash bucket to recompute next */
240 /* non shaped skbs; let them go directly thru */
241 struct sk_buff_head direct_queue;
242 int direct_qlen; /* max qlen of above */
247 /* compute hash of size HTB_HSIZE for given handle */
248 static __inline__ int htb_hash(u32 h)
251 #error "Declare new hash for your HTB_HSIZE"
253 h ^= h>>8; /* stolen from cbq_hash */
258 /* find class in global hash table using given handle */
259 static __inline__ struct htb_class *htb_find(u32 handle, struct Qdisc *sch)
261 struct htb_sched *q = (struct htb_sched *)sch->data;
263 if (TC_H_MAJ(handle) != sch->handle)
266 list_for_each (p,q->hash+htb_hash(handle)) {
267 struct htb_class *cl = list_entry(p,struct htb_class,hlist);
268 if (cl->classid == handle)
275 * htb_classify - classify a packet into class
277 * It returns NULL if the packet should be dropped or -1 if the packet
278 * should be passed directly thru. In all other cases leaf class is returned.
279 * We allow direct class selection by classid in priority. The we examine
280 * filters in qdisc and in inner nodes (if higher filter points to the inner
281 * node). If we end up with classid MAJOR:0 we enqueue the skb into special
282 * internal fifo (direct). These packets then go directly thru. If we still
283 * have no valid leaf we try to use MAJOR:default leaf. It still unsuccessfull
284 * then finish and return direct queue.
286 #define HTB_DIRECT (struct htb_class*)-1
287 static struct htb_class *htb_classify(struct sk_buff *skb, struct Qdisc *sch)
289 struct htb_sched *q = (struct htb_sched *)sch->data;
290 struct htb_class *cl;
291 struct tcf_result res;
292 struct tcf_proto *tcf;
295 /* allow to select class by setting skb->priority to valid classid;
296 note that nfmark can be used too by attaching filter fw with no
298 if (skb->priority == sch->handle)
299 return HTB_DIRECT; /* X:0 (direct flow) selected */
300 if ((cl = htb_find(skb->priority,sch)) != NULL)
303 tcf = q->filter_list;
304 while (tcf && (result = tc_classify(skb, tcf, &res)) >= 0) {
305 #ifdef CONFIG_NET_CLS_POLICE
306 if (result == TC_POLICE_SHOT)
309 if ((cl = (void*)res.class) == NULL) {
310 if (res.classid == sch->handle)
311 return HTB_DIRECT; /* X:0 (direct flow) */
312 if ((cl = htb_find(res.classid,sch)) == NULL)
313 break; /* filter selected invalid classid */
316 return cl; /* we hit leaf; return it */
318 /* we have got inner class; apply inner filter chain */
319 tcf = cl->filter_list;
321 /* classification failed; try to use default class */
322 cl = htb_find(TC_H_MAKE(TC_H_MAJ(sch->handle),q->defcls),sch);
323 if (!cl || cl->level)
324 return HTB_DIRECT; /* bad default .. this is safe bet */
329 static void htb_next_rb_node(rb_node_t **n);
330 #define HTB_DUMTREE(root,memb) if(root) { \
331 rb_node_t *n = (root)->rb_node; \
332 while (n->rb_left) n = n->rb_left; \
334 struct htb_class *cl = rb_entry(n, struct htb_class, memb); \
335 printk(" %x",cl->classid); htb_next_rb_node (&n); \
338 static void htb_debug_dump (struct htb_sched *q)
341 printk(KERN_DEBUG "htb*g j=%lu\n",jiffies);
343 for (i=TC_HTB_MAXDEPTH-1;i>=0;i--) {
344 printk(KERN_DEBUG "htb*r%d m=%x",i,q->row_mask[i]);
345 for (p=0;p<TC_HTB_NUMPRIO;p++) {
346 if (!q->row[i][p].rb_node) continue;
348 HTB_DUMTREE(q->row[i]+p,node[p]);
353 for (i = 0; i < HTB_HSIZE; i++) {
355 list_for_each (l,q->hash+i) {
356 struct htb_class *cl = list_entry(l,struct htb_class,hlist);
357 long diff = PSCHED_TDIFF_SAFE(q->now, cl->t_c, (u32)cl->mbuffer, 0);
358 printk(KERN_DEBUG "htb*c%x m=%d t=%ld c=%ld pq=%lu df=%ld ql=%d "
360 cl->classid,cl->cmode,cl->tokens,cl->ctokens,
361 cl->pq_node.rb_color==-1?0:cl->pq_key,diff,
362 cl->level?0:cl->un.leaf.q->q.qlen,cl->prio_activity);
364 for (p=0;p<TC_HTB_NUMPRIO;p++) {
365 if (!cl->un.inner.feed[p].rb_node) continue;
366 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);
367 HTB_DUMTREE(cl->un.inner.feed+p,node[p]);
375 * htb_add_to_id_tree - adds class to the round robin list
377 * Routine adds class to the list (actually tree) sorted by classid.
378 * Make sure that class is not already on such list for given prio.
380 static void htb_add_to_id_tree (HTB_ARGQ rb_root_t *root,
381 struct htb_class *cl,int prio)
383 rb_node_t **p = &root->rb_node, *parent = NULL;
384 HTB_DBG(7,3,"htb_add_id_tree cl=%X prio=%d\n",cl->classid,prio);
386 if (cl->node[prio].rb_color != -1) { BUG_TRAP(0); return; }
389 struct htb_class *x = rb_entry(*p,struct htb_class,node[prio]);
394 struct htb_class *c; parent = *p;
395 c = rb_entry(parent, struct htb_class, node[prio]);
397 if (cl->classid > c->classid)
398 p = &parent->rb_right;
400 p = &parent->rb_left;
402 rb_link_node(&cl->node[prio], parent, p);
403 rb_insert_color(&cl->node[prio], root);
407 * htb_add_to_wait_tree - adds class to the event queue with delay
409 * The class is added to priority event queue to indicate that class will
410 * change its mode in cl->pq_key microseconds. Make sure that class is not
411 * already in the queue.
413 static void htb_add_to_wait_tree (struct htb_sched *q,
414 struct htb_class *cl,long delay,int debug_hint)
416 rb_node_t **p = &q->wait_pq[cl->level].rb_node, *parent = NULL;
417 HTB_DBG(7,3,"htb_add_wt cl=%X key=%lu\n",cl->classid,cl->pq_key);
419 if (cl->pq_node.rb_color != -1) { BUG_TRAP(0); return; }
421 if ((delay <= 0 || delay > cl->mbuffer) && net_ratelimit())
422 printk(KERN_ERR "HTB: suspicious delay in wait_tree d=%ld cl=%X h=%d\n",delay,cl->classid,debug_hint);
425 cl->pq_key = jiffies + PSCHED_US2JIFFIE(delay);
426 if (cl->pq_key == jiffies)
429 /* update the nearest event cache */
430 if (q->near_ev_cache[cl->level] - cl->pq_key < 0x80000000)
431 q->near_ev_cache[cl->level] = cl->pq_key;
434 struct htb_class *c; parent = *p;
435 c = rb_entry(parent, struct htb_class, pq_node);
436 if (cl->pq_key - c->pq_key < 0x80000000)
437 p = &parent->rb_right;
439 p = &parent->rb_left;
441 rb_link_node(&cl->pq_node, parent, p);
442 rb_insert_color(&cl->pq_node, &q->wait_pq[cl->level]);
447 * htb_next_rb_node - finds next node in binary tree
449 * When we are past last key we return NULL.
450 * Average complexity is 2 steps per call.
452 static void htb_next_rb_node(rb_node_t **n)
455 if ((*n)->rb_right) {
457 while ((*n)->rb_left)
461 while ((p = (*n)->rb_parent) != NULL) {
462 if (p->rb_left == *n) break;
469 * htb_add_class_to_row - add class to its row
471 * The class is added to row at priorities marked in mask.
472 * It does nothing if mask == 0.
474 static inline void htb_add_class_to_row(struct htb_sched *q,
475 struct htb_class *cl,int mask)
477 HTB_DBG(7,2,"htb_addrow cl=%X mask=%X rmask=%X\n",
478 cl->classid,mask,q->row_mask[cl->level]);
480 q->row_mask[cl->level] |= mask;
482 int prio = ffz(~mask);
483 mask &= ~(1 << prio);
484 htb_add_to_id_tree(HTB_PASSQ q->row[cl->level]+prio,cl,prio);
489 * htb_remove_class_from_row - removes class from its row
491 * The class is removed from row at priorities marked in mask.
492 * It does nothing if mask == 0.
494 static __inline__ void htb_remove_class_from_row(struct htb_sched *q,
495 struct htb_class *cl,int mask)
500 int prio = ffz(~mask);
501 mask &= ~(1 << prio);
502 if (q->ptr[cl->level][prio] == cl->node+prio)
503 htb_next_rb_node(q->ptr[cl->level]+prio);
504 htb_safe_rb_erase(cl->node + prio,q->row[cl->level]+prio);
505 if (!q->row[cl->level][prio].rb_node)
508 HTB_DBG(7,2,"htb_delrow cl=%X mask=%X rmask=%X maskdel=%X\n",
509 cl->classid,mask,q->row_mask[cl->level],m);
510 q->row_mask[cl->level] &= ~m;
514 * htb_activate_prios - creates active classe's feed chain
516 * The class is connected to ancestors and/or appropriate rows
517 * for priorities it is participating on. cl->cmode must be new
518 * (activated) mode. It does nothing if cl->prio_activity == 0.
520 static void htb_activate_prios(struct htb_sched *q,struct htb_class *cl)
522 struct htb_class *p = cl->parent;
523 long m,mask = cl->prio_activity;
524 HTB_DBG(7,2,"htb_act_prios cl=%X mask=%lX cmode=%d\n",cl->classid,mask,cl->cmode);
527 while (cl->cmode == HTB_MAY_BORROW && p && mask) {
529 m = mask; while (m) {
533 if (p->un.inner.feed[prio].rb_node)
534 /* parent already has its feed in use so that
535 reset bit in mask as parent is already ok */
536 mask &= ~(1 << prio);
538 htb_add_to_id_tree(HTB_PASSQ p->un.inner.feed+prio,cl,prio);
540 HTB_DBG(7,3,"htb_act_pr_aft p=%X pact=%X mask=%lX pmode=%d\n",
541 p->classid,p->prio_activity,mask,p->cmode);
542 p->prio_activity |= mask;
543 cl = p; p = cl->parent;
546 if (cl->cmode == HTB_CAN_SEND && mask)
547 htb_add_class_to_row(q,cl,mask);
551 * htb_deactivate_prios - remove class from feed chain
553 * cl->cmode must represent old mode (before deactivation). It does
554 * nothing if cl->prio_activity == 0. Class is removed from all feed
557 static void htb_deactivate_prios(struct htb_sched *q, struct htb_class *cl)
559 struct htb_class *p = cl->parent;
560 long m,mask = cl->prio_activity;
561 HTB_DBG(7,2,"htb_deact_prios cl=%X mask=%lX cmode=%d\n",cl->classid,mask,cl->cmode);
564 while (cl->cmode == HTB_MAY_BORROW && p && mask) {
570 if (p->un.inner.ptr[prio] == cl->node+prio)
571 htb_next_rb_node(p->un.inner.ptr + prio);
573 htb_safe_rb_erase(cl->node + prio,p->un.inner.feed + prio);
575 if (!p->un.inner.feed[prio].rb_node)
578 HTB_DBG(7,3,"htb_deact_pr_aft p=%X pact=%X mask=%lX pmode=%d\n",
579 p->classid,p->prio_activity,mask,p->cmode);
580 p->prio_activity &= ~mask;
581 cl = p; p = cl->parent;
584 if (cl->cmode == HTB_CAN_SEND && mask)
585 htb_remove_class_from_row(q,cl,mask);
589 * htb_class_mode - computes and returns current class mode
591 * It computes cl's mode at time cl->t_c+diff and returns it. If mode
592 * is not HTB_CAN_SEND then cl->pq_key is updated to time difference
593 * from now to time when cl will change its state.
594 * Also it is worth to note that class mode doesn't change simply
595 * at cl->{c,}tokens == 0 but there can rather be hysteresis of
596 * 0 .. -cl->{c,}buffer range. It is meant to limit number of
597 * mode transitions per time unit. The speed gain is about 1/6.
599 static __inline__ enum htb_cmode
600 htb_class_mode(struct htb_class *cl,long *diff)
604 if ((toks = (cl->ctokens + *diff)) < (
605 #ifdef HTB_HYSTERESIS
606 cl->cmode != HTB_CANT_SEND ? -cl->cbuffer :
610 return HTB_CANT_SEND;
612 if ((toks = (cl->tokens + *diff)) >= (
613 #ifdef HTB_HYSTERESIS
614 cl->cmode == HTB_CAN_SEND ? -cl->buffer :
620 return HTB_MAY_BORROW;
624 * htb_change_class_mode - changes classe's mode
626 * This should be the only way how to change classe's mode under normal
627 * cirsumstances. Routine will update feed lists linkage, change mode
628 * and add class to the wait event queue if appropriate. New mode should
629 * be different from old one and cl->pq_key has to be valid if changing
630 * to mode other than HTB_CAN_SEND (see htb_add_to_wait_tree).
633 htb_change_class_mode(struct htb_sched *q, struct htb_class *cl, long *diff)
635 enum htb_cmode new_mode = htb_class_mode(cl,diff);
638 HTB_DBG(7,1,"htb_chging_clmode %d->%d cl=%X\n",cl->cmode,new_mode,cl->classid);
640 if (new_mode == cl->cmode)
643 if (cl->prio_activity) { /* not neccessary: speed optimization */
644 if (cl->cmode != HTB_CANT_SEND)
645 htb_deactivate_prios(q,cl);
646 cl->cmode = new_mode;
647 if (new_mode != HTB_CANT_SEND)
648 htb_activate_prios(q,cl);
650 cl->cmode = new_mode;
654 * htb_activate - inserts leaf cl into appropriate active feeds
656 * Routine learns (new) priority of leaf and activates feed chain
657 * for the prio. It can be called on already active leaf safely.
658 * It also adds leaf into droplist.
660 static __inline__ void htb_activate(struct htb_sched *q,struct htb_class *cl)
662 BUG_TRAP(!cl->level && cl->un.leaf.q && cl->un.leaf.q->q.qlen);
664 if (!cl->prio_activity) {
665 cl->prio_activity = 1 << (cl->un.leaf.aprio = cl->un.leaf.prio);
666 htb_activate_prios(q,cl);
667 list_add_tail(&cl->un.leaf.drop_list,q->drops+cl->un.leaf.aprio);
672 * htb_deactivate - remove leaf cl from active feeds
674 * Make sure that leaf is active. In the other words it can't be called
675 * with non-active leaf. It also removes class from the drop list.
677 static __inline__ void
678 htb_deactivate(struct htb_sched *q,struct htb_class *cl)
680 BUG_TRAP(cl->prio_activity);
682 htb_deactivate_prios(q,cl);
683 cl->prio_activity = 0;
684 list_del_init(&cl->un.leaf.drop_list);
687 static int htb_enqueue(struct sk_buff *skb, struct Qdisc *sch)
689 struct htb_sched *q = (struct htb_sched *)sch->data;
690 struct htb_class *cl = htb_classify(skb,sch);
693 if (cl == HTB_DIRECT || !cl) {
694 /* enqueue to helper queue */
695 if (q->direct_queue.qlen < q->direct_qlen && cl) {
696 __skb_queue_tail(&q->direct_queue, skb);
702 return NET_XMIT_DROP;
704 } else if (cl->un.leaf.q->enqueue(skb, cl->un.leaf.q) != NET_XMIT_SUCCESS) {
708 return NET_XMIT_DROP;
710 cl->stats.packets++; cl->stats.bytes += skb->len;
717 sch->stats.packets++; sch->stats.bytes += skb->len;
718 HTB_DBG(1,1,"htb_enq_ok cl=%X skb=%p\n",cl?cl->classid:0,skb);
720 return NET_XMIT_SUCCESS;
723 /* TODO: requeuing packet charges it to policers again !! */
724 static int htb_requeue(struct sk_buff *skb, struct Qdisc *sch)
726 struct htb_sched *q = (struct htb_sched *)sch->data;
727 struct htb_class *cl = htb_classify(skb,sch);
729 if (cl == HTB_DIRECT || !cl) {
730 /* enqueue to helper queue */
731 if (q->direct_queue.qlen < q->direct_qlen && cl) {
732 __skb_queue_tail(&q->direct_queue, skb);
737 return NET_XMIT_DROP;
739 } else if (cl->un.leaf.q->ops->requeue(skb, cl->un.leaf.q) != NET_XMIT_SUCCESS) {
742 return NET_XMIT_DROP;
747 HTB_DBG(1,1,"htb_req_ok cl=%X skb=%p\n",cl?cl->classid:0,skb);
748 return NET_XMIT_SUCCESS;
751 static void htb_timer(unsigned long arg)
753 struct Qdisc *sch = (struct Qdisc*)arg;
754 sch->flags &= ~TCQ_F_THROTTLED;
756 netif_schedule(sch->dev);
760 #define RT_GEN(D,R) R+=D-(R/HTB_EWMAC);D=0
761 static void htb_rate_timer(unsigned long arg)
763 struct Qdisc *sch = (struct Qdisc*)arg;
764 struct htb_sched *q = (struct htb_sched *)sch->data;
767 /* lock queue so that we can muck with it */
769 HTB_DBG(10,1,"htb_rttmr j=%ld\n",jiffies);
771 q->rttim.expires = jiffies + HZ;
772 add_timer(&q->rttim);
774 /* scan and recompute one bucket at time */
775 if (++q->recmp_bucket >= HTB_HSIZE)
777 list_for_each (p,q->hash+q->recmp_bucket) {
778 struct htb_class *cl = list_entry(p,struct htb_class,hlist);
779 HTB_DBG(10,2,"htb_rttmr_cl cl=%X sbyte=%lu spkt=%lu\n",
780 cl->classid,cl->sum_bytes,cl->sum_packets);
781 RT_GEN (cl->sum_bytes,cl->rate_bytes);
782 RT_GEN (cl->sum_packets,cl->rate_packets);
789 * htb_charge_class - charges ammount "bytes" to leaf and ancestors
791 * Routine assumes that packet "bytes" long was dequeued from leaf cl
792 * borrowing from "level". It accounts bytes to ceil leaky bucket for
793 * leaf and all ancestors and to rate bucket for ancestors at levels
794 * "level" and higher. It also handles possible change of mode resulting
795 * from the update. Note that mode can also increase here (MAY_BORROW to
796 * CAN_SEND) because we can use more precise clock that event queue here.
797 * In such case we remove class from event queue first.
799 static void htb_charge_class(struct htb_sched *q,struct htb_class *cl,
803 enum htb_cmode old_mode;
804 HTB_DBG(5,1,"htb_chrg_cl cl=%X lev=%d len=%d\n",cl->classid,level,bytes);
806 #define HTB_ACCNT(T,B,R) toks = diff + cl->T; \
807 if (toks > cl->B) toks = cl->B; \
808 toks -= L2T(cl, cl->R, bytes); \
809 if (toks <= -cl->mbuffer) toks = 1-cl->mbuffer; \
814 diff = PSCHED_TDIFF_SAFE(q->now, cl->t_c, (u32)cl->mbuffer, 0);
816 if (diff > cl->mbuffer || diff < 0 || PSCHED_TLESS(q->now, cl->t_c)) {
818 printk(KERN_ERR "HTB: bad diff in charge, cl=%X diff=%lX now=%Lu then=%Lu j=%lu\n",
820 (unsigned long long) q->now,
821 (unsigned long long) cl->t_c,
826 if (cl->level >= level) {
827 if (cl->level == level) cl->xstats.lends++;
828 HTB_ACCNT (tokens,buffer,rate);
830 cl->xstats.borrows++;
831 cl->tokens += diff; /* we moved t_c; update tokens */
833 HTB_ACCNT (ctokens,cbuffer,ceil);
835 HTB_DBG(5,2,"htb_chrg_clp cl=%X diff=%ld tok=%ld ctok=%ld\n",cl->classid,diff,cl->tokens,cl->ctokens);
837 old_mode = cl->cmode; diff = 0;
838 htb_change_class_mode(q,cl,&diff);
839 if (old_mode != cl->cmode) {
840 if (old_mode != HTB_CAN_SEND)
841 htb_safe_rb_erase(&cl->pq_node,q->wait_pq+cl->level);
842 if (cl->cmode != HTB_CAN_SEND)
843 htb_add_to_wait_tree (q,cl,diff,1);
847 /* update rate counters */
848 cl->sum_bytes += bytes; cl->sum_packets++;
851 /* update byte stats except for leaves which are already updated */
853 cl->stats.bytes += bytes;
861 * htb_do_events - make mode changes to classes at the level
863 * Scans event queue for pending events and applies them. Returns jiffies to
864 * next pending event (0 for no event in pq).
866 static long htb_do_events(struct htb_sched *q,int level)
869 HTB_DBG(8,1,"htb_do_events l=%d root=%p rmask=%X\n",
870 level,q->wait_pq[level].rb_node,q->row_mask[level]);
871 for (i = 0; i < 500; i++) {
872 struct htb_class *cl;
874 rb_node_t *p = q->wait_pq[level].rb_node;
876 while (p->rb_left) p = p->rb_left;
878 cl = rb_entry(p, struct htb_class, pq_node);
879 if (cl->pq_key - (jiffies+1) < 0x80000000) {
880 HTB_DBG(8,3,"htb_do_ev_ret delay=%ld\n",cl->pq_key - jiffies);
881 return cl->pq_key - jiffies;
883 htb_safe_rb_erase(p,q->wait_pq+level);
884 diff = PSCHED_TDIFF_SAFE(q->now, cl->t_c, (u32)cl->mbuffer, 0);
886 if (diff > cl->mbuffer || diff < 0 || PSCHED_TLESS(q->now, cl->t_c)) {
888 printk(KERN_ERR "HTB: bad diff in events, cl=%X diff=%lX now=%Lu then=%Lu j=%lu\n",
890 (unsigned long long) q->now,
891 (unsigned long long) cl->t_c,
896 htb_change_class_mode(q,cl,&diff);
897 if (cl->cmode != HTB_CAN_SEND)
898 htb_add_to_wait_tree (q,cl,diff,2);
901 printk(KERN_WARNING "htb: too many events !\n");
906 * htb_lookup_leaf - returns next leaf class in DRR order
908 * Find leaf where current feed pointers points to.
910 static struct htb_class *
911 htb_lookup_leaf(rb_root_t *tree,int prio,rb_node_t **pptr)
917 } stk[TC_HTB_MAXDEPTH],*sp = stk;
919 sp->root = tree->rb_node;
922 for (i = 0; i < 65535; i++) {
923 if (!*sp->pptr) { /* we are at right end; rewind & go up */
924 *sp->pptr = sp->root;
925 while ((*sp->pptr)->rb_left)
926 *sp->pptr = (*sp->pptr)->rb_left;
929 BUG_TRAP(*sp->pptr); if(!*sp->pptr) return NULL;
930 htb_next_rb_node (sp->pptr);
933 struct htb_class *cl;
934 cl = rb_entry(*sp->pptr,struct htb_class,node[prio]);
938 (++sp)->root = cl->un.inner.feed[prio].rb_node;
939 sp->pptr = cl->un.inner.ptr+prio;
946 /* dequeues packet at given priority and level; call only if
947 you are sure that there is active class at prio/level */
948 static struct sk_buff *
949 htb_dequeue_tree(struct htb_sched *q,int prio,int level)
951 struct sk_buff *skb = NULL;
952 //struct htb_sched *q = (struct htb_sched *)sch->data;
953 struct htb_class *cl,*start;
954 /* look initial class up in the row */
956 start = cl = htb_lookup_leaf (q->row[level]+prio,prio,q->ptr[level]+prio);
959 BUG_TRAP(cl && cl->un.leaf.q->q.qlen); if (!cl) return NULL;
960 HTB_DBG(4,1,"htb_deq_tr prio=%d lev=%d cl=%X defic=%d\n",
961 prio,level,cl->classid,cl->un.leaf.deficit[level]);
963 if (likely((skb = cl->un.leaf.q->dequeue(cl->un.leaf.q)) != NULL))
966 printk(KERN_WARNING "htb: class %X isn't work conserving ?!\n",cl->classid);
970 htb_next_rb_node((level?cl->parent->un.inner.ptr:q->ptr[0])+prio);
971 cl = htb_lookup_leaf (q->row[level]+prio,prio,q->ptr[level]+prio);
972 } while (cl != start);
976 if (likely(skb != NULL)) {
977 if ((cl->un.leaf.deficit[level] -= skb->len) < 0) {
978 HTB_DBG(4,2,"htb_next_cl oldptr=%p quant_add=%d\n",
979 level?cl->parent->un.inner.ptr[prio]:q->ptr[0][prio],cl->un.leaf.quantum);
980 cl->un.leaf.deficit[level] += cl->un.leaf.quantum;
981 htb_next_rb_node((level?cl->parent->un.inner.ptr:q->ptr[0])+prio);
983 /* this used to be after charge_class but this constelation
984 gives us slightly better performance */
985 if (!cl->un.leaf.q->q.qlen)
986 htb_deactivate (q,cl);
988 htb_charge_class (q,cl,level,skb->len);
995 static void htb_delay_by(struct Qdisc *sch,long delay)
997 struct htb_sched *q = (struct htb_sched *)sch->data;
998 if (netif_queue_stopped(sch->dev)) return;
999 if (delay <= 0) delay = 1;
1000 if (unlikely(delay > 5*HZ)) {
1001 if (net_ratelimit())
1002 printk(KERN_INFO "HTB delay %ld > 5sec\n", delay);
1005 del_timer(&q->timer);
1006 q->timer.expires = jiffies + delay;
1007 add_timer(&q->timer);
1008 sch->flags |= TCQ_F_THROTTLED;
1009 sch->stats.overlimits++;
1010 HTB_DBG(3,1,"htb_deq t_delay=%ld\n",delay);
1013 static struct sk_buff *htb_dequeue(struct Qdisc *sch)
1015 struct sk_buff *skb = NULL;
1016 struct htb_sched *q = (struct htb_sched *)sch->data;
1020 HTB_DBG(3,1,"htb_deq dircnt=%d qlen=%d\n",skb_queue_len(&q->direct_queue),
1023 /* try to dequeue direct packets as high prio (!) to minimize cpu work */
1024 if ((skb = __skb_dequeue(&q->direct_queue)) != NULL) {
1025 sch->flags &= ~TCQ_F_THROTTLED;
1031 if (!sch->q.qlen) goto fin;
1032 PSCHED_GET_TIME(q->now);
1036 for (level = 0; level < TC_HTB_MAXDEPTH; level++) {
1037 /* common case optimization - skip event handler quickly */
1041 if (jiffies - q->near_ev_cache[level] < 0x80000000 || 0) {
1042 delay = htb_do_events(q,level);
1043 q->near_ev_cache[level] += delay ? delay : HZ;
1045 delay = q->near_ev_cache[level] - jiffies;
1047 if (delay && min_delay > delay)
1051 m = ~q->row_mask[level];
1052 while (m != (int)(-1)) {
1055 skb = htb_dequeue_tree(q,prio,level);
1056 if (likely(skb != NULL)) {
1058 sch->flags &= ~TCQ_F_THROTTLED;
1067 if (!q->nwc_hit && min_delay >= 5*HZ && net_ratelimit()) {
1068 printk(KERN_ERR "HTB: mindelay=%ld, report it please !\n",min_delay);
1072 htb_delay_by (sch,min_delay);
1075 HTB_DBG(3,1,"htb_deq_end %s j=%lu skb=%p\n",sch->dev->name,jiffies,skb);
1080 /* try to drop from each class (by prio) until one succeed */
1081 static int htb_drop(struct Qdisc* sch)
1083 struct htb_sched *q = (struct htb_sched *)sch->data;
1086 for (prio = TC_HTB_NUMPRIO - 1; prio >= 0; prio--) {
1087 struct list_head *p;
1088 list_for_each (p,q->drops+prio) {
1089 struct htb_class *cl = list_entry(p,struct htb_class,
1091 if (cl->un.leaf.q->ops->drop &&
1092 cl->un.leaf.q->ops->drop(cl->un.leaf.q)) {
1094 if (!cl->un.leaf.q->q.qlen)
1095 htb_deactivate (q,cl);
1103 /* reset all classes */
1104 /* always caled under BH & queue lock */
1105 static void htb_reset(struct Qdisc* sch)
1107 struct htb_sched *q = (struct htb_sched *)sch->data;
1109 HTB_DBG(0,1,"htb_reset sch=%p, handle=%X\n",sch,sch->handle);
1111 for (i = 0; i < HTB_HSIZE; i++) {
1112 struct list_head *p;
1113 list_for_each (p,q->hash+i) {
1114 struct htb_class *cl = list_entry(p,struct htb_class,hlist);
1116 memset(&cl->un.inner,0,sizeof(cl->un.inner));
1119 qdisc_reset(cl->un.leaf.q);
1120 INIT_LIST_HEAD(&cl->un.leaf.drop_list);
1122 cl->prio_activity = 0;
1123 cl->cmode = HTB_CAN_SEND;
1125 cl->pq_node.rb_color = -1;
1126 memset(cl->node,255,sizeof(cl->node));
1131 sch->flags &= ~TCQ_F_THROTTLED;
1132 del_timer(&q->timer);
1133 __skb_queue_purge(&q->direct_queue);
1135 memset(q->row,0,sizeof(q->row));
1136 memset(q->row_mask,0,sizeof(q->row_mask));
1137 memset(q->wait_pq,0,sizeof(q->wait_pq));
1138 memset(q->ptr,0,sizeof(q->ptr));
1139 for (i = 0; i < TC_HTB_NUMPRIO; i++)
1140 INIT_LIST_HEAD(q->drops+i);
1143 static int htb_init(struct Qdisc *sch, struct rtattr *opt)
1145 struct htb_sched *q = (struct htb_sched*)sch->data;
1146 struct rtattr *tb[TCA_HTB_INIT];
1147 struct tc_htb_glob *gopt;
1150 printk(KERN_INFO "HTB init, kernel part version %d.%d\n",
1151 HTB_VER >> 16,HTB_VER & 0xffff);
1153 if (!opt || rtattr_parse(tb, TCA_HTB_INIT, RTA_DATA(opt), RTA_PAYLOAD(opt)) ||
1154 tb[TCA_HTB_INIT-1] == NULL ||
1155 RTA_PAYLOAD(tb[TCA_HTB_INIT-1]) < sizeof(*gopt)) {
1156 printk(KERN_ERR "HTB: hey probably you have bad tc tool ?\n");
1159 gopt = RTA_DATA(tb[TCA_HTB_INIT-1]);
1160 if (gopt->version != HTB_VER >> 16) {
1161 printk(KERN_ERR "HTB: need tc/htb version %d (minor is %d), you have %d\n",
1162 HTB_VER >> 16,HTB_VER & 0xffff,gopt->version);
1165 memset(q,0,sizeof(*q));
1166 q->debug = gopt->debug;
1167 HTB_DBG(0,1,"htb_init sch=%p handle=%X r2q=%d\n",sch,sch->handle,gopt->rate2quantum);
1169 INIT_LIST_HEAD(&q->root);
1170 for (i = 0; i < HTB_HSIZE; i++)
1171 INIT_LIST_HEAD(q->hash+i);
1172 for (i = 0; i < TC_HTB_NUMPRIO; i++)
1173 INIT_LIST_HEAD(q->drops+i);
1175 init_timer(&q->timer);
1176 skb_queue_head_init(&q->direct_queue);
1178 q->direct_qlen = sch->dev->tx_queue_len;
1179 if (q->direct_qlen < 2) /* some devices have zero tx_queue_len */
1181 q->timer.function = htb_timer;
1182 q->timer.data = (unsigned long)sch;
1185 init_timer(&q->rttim);
1186 q->rttim.function = htb_rate_timer;
1187 q->rttim.data = (unsigned long)sch;
1188 q->rttim.expires = jiffies + HZ;
1189 add_timer(&q->rttim);
1191 if ((q->rate2quantum = gopt->rate2quantum) < 1)
1192 q->rate2quantum = 1;
1193 q->defcls = gopt->defcls;
1199 static int htb_dump(struct Qdisc *sch, struct sk_buff *skb)
1201 struct htb_sched *q = (struct htb_sched*)sch->data;
1202 unsigned char *b = skb->tail;
1204 struct tc_htb_glob gopt;
1205 HTB_DBG(0,1,"htb_dump sch=%p, handle=%X\n",sch,sch->handle);
1208 gopt.direct_pkts = q->direct_pkts;
1213 gopt.version = HTB_VER;
1214 gopt.rate2quantum = q->rate2quantum;
1215 gopt.defcls = q->defcls;
1216 gopt.debug = q->debug;
1217 rta = (struct rtattr*)b;
1218 RTA_PUT(skb, TCA_OPTIONS, 0, NULL);
1219 RTA_PUT(skb, TCA_HTB_INIT, sizeof(gopt), &gopt);
1220 rta->rta_len = skb->tail - b;
1221 sch->stats.qlen = sch->q.qlen;
1222 RTA_PUT(skb, TCA_STATS, sizeof(sch->stats), &sch->stats);
1227 skb_trim(skb, skb->tail - skb->data);
1231 static int htb_dump_class(struct Qdisc *sch, unsigned long arg,
1232 struct sk_buff *skb, struct tcmsg *tcm)
1235 struct htb_sched *q = (struct htb_sched*)sch->data;
1237 struct htb_class *cl = (struct htb_class*)arg;
1238 unsigned char *b = skb->tail;
1240 struct tc_htb_opt opt;
1242 HTB_DBG(0,1,"htb_dump_class handle=%X clid=%X\n",sch->handle,cl->classid);
1245 tcm->tcm_parent = cl->parent ? cl->parent->classid : TC_H_ROOT;
1246 tcm->tcm_handle = cl->classid;
1247 if (!cl->level && cl->un.leaf.q) {
1248 tcm->tcm_info = cl->un.leaf.q->handle;
1249 cl->stats.qlen = cl->un.leaf.q->q.qlen;
1252 rta = (struct rtattr*)b;
1253 RTA_PUT(skb, TCA_OPTIONS, 0, NULL);
1255 memset (&opt,0,sizeof(opt));
1257 opt.rate = cl->rate->rate; opt.buffer = cl->buffer;
1258 opt.ceil = cl->ceil->rate; opt.cbuffer = cl->cbuffer;
1259 opt.quantum = cl->un.leaf.quantum; opt.prio = cl->un.leaf.prio;
1260 opt.level = cl->level;
1261 RTA_PUT(skb, TCA_HTB_PARMS, sizeof(opt), &opt);
1262 rta->rta_len = skb->tail - b;
1265 cl->stats.bps = cl->rate_bytes/(HTB_EWMAC*HTB_HSIZE);
1266 cl->stats.pps = cl->rate_packets/(HTB_EWMAC*HTB_HSIZE);
1269 cl->xstats.tokens = cl->tokens;
1270 cl->xstats.ctokens = cl->ctokens;
1271 RTA_PUT(skb, TCA_STATS, sizeof(cl->stats), &cl->stats);
1272 RTA_PUT(skb, TCA_XSTATS, sizeof(cl->xstats), &cl->xstats);
1277 skb_trim(skb, b - skb->data);
1281 static int htb_graft(struct Qdisc *sch, unsigned long arg, struct Qdisc *new,
1284 struct htb_class *cl = (struct htb_class*)arg;
1286 if (cl && !cl->level) {
1287 if (new == NULL && (new = qdisc_create_dflt(sch->dev,
1288 &pfifo_qdisc_ops)) == NULL)
1291 if ((*old = xchg(&cl->un.leaf.q, new)) != NULL) {
1292 /* TODO: is it correct ? Why CBQ doesn't do it ? */
1293 sch->q.qlen -= (*old)->q.qlen;
1296 sch_tree_unlock(sch);
1302 static struct Qdisc * htb_leaf(struct Qdisc *sch, unsigned long arg)
1304 struct htb_class *cl = (struct htb_class*)arg;
1305 return (cl && !cl->level) ? cl->un.leaf.q : NULL;
1308 static unsigned long htb_get(struct Qdisc *sch, u32 classid)
1311 struct htb_sched *q = (struct htb_sched *)sch->data;
1313 struct htb_class *cl = htb_find(classid,sch);
1314 HTB_DBG(0,1,"htb_get clid=%X q=%p cl=%p ref=%d\n",classid,q,cl,cl?cl->refcnt:0);
1317 return (unsigned long)cl;
1320 static void htb_destroy_filters(struct tcf_proto **fl)
1322 struct tcf_proto *tp;
1324 while ((tp = *fl) != NULL) {
1326 tp->ops->destroy(tp);
1330 static void htb_destroy_class(struct Qdisc* sch,struct htb_class *cl)
1332 struct htb_sched *q = (struct htb_sched *)sch->data;
1333 HTB_DBG(0,1,"htb_destrycls clid=%X ref=%d\n", cl?cl->classid:0,cl?cl->refcnt:0);
1335 BUG_TRAP(cl->un.leaf.q);
1336 sch->q.qlen -= cl->un.leaf.q->q.qlen;
1337 qdisc_destroy(cl->un.leaf.q);
1339 qdisc_put_rtab(cl->rate);
1340 qdisc_put_rtab(cl->ceil);
1342 #ifdef CONFIG_NET_ESTIMATOR
1343 qdisc_kill_estimator(&cl->stats);
1345 htb_destroy_filters (&cl->filter_list);
1347 while (!list_empty(&cl->children))
1348 htb_destroy_class (sch,list_entry(cl->children.next,
1349 struct htb_class,sibling));
1351 /* note: this delete may happen twice (see htb_delete) */
1352 list_del(&cl->hlist);
1353 list_del(&cl->sibling);
1355 if (cl->prio_activity)
1356 htb_deactivate (q,cl);
1358 if (cl->cmode != HTB_CAN_SEND)
1359 htb_safe_rb_erase(&cl->pq_node,q->wait_pq+cl->level);
1364 /* always caled under BH & queue lock */
1365 static void htb_destroy(struct Qdisc* sch)
1367 struct htb_sched *q = (struct htb_sched *)sch->data;
1368 HTB_DBG(0,1,"htb_destroy q=%p\n",q);
1370 del_timer_sync (&q->timer);
1372 del_timer_sync (&q->rttim);
1374 while (!list_empty(&q->root))
1375 htb_destroy_class (sch,list_entry(q->root.next,
1376 struct htb_class,sibling));
1378 htb_destroy_filters(&q->filter_list);
1379 __skb_queue_purge(&q->direct_queue);
1383 static int htb_delete(struct Qdisc *sch, unsigned long arg)
1385 struct htb_sched *q = (struct htb_sched *)sch->data;
1386 struct htb_class *cl = (struct htb_class*)arg;
1387 HTB_DBG(0,1,"htb_delete q=%p cl=%X ref=%d\n",q,cl?cl->classid:0,cl?cl->refcnt:0);
1389 // TODO: why don't allow to delete subtree ? references ? does
1390 // tc subsys quarantee us that in htb_destroy it holds no class
1391 // refs so that we can remove children safely there ?
1392 if (!list_empty(&cl->children) || cl->filter_cnt)
1397 /* delete from hash and active; remainder in destroy_class */
1398 list_del_init(&cl->hlist);
1399 if (cl->prio_activity)
1400 htb_deactivate (q,cl);
1402 if (--cl->refcnt == 0)
1403 htb_destroy_class(sch,cl);
1405 sch_tree_unlock(sch);
1409 static void htb_put(struct Qdisc *sch, unsigned long arg)
1412 struct htb_sched *q = (struct htb_sched *)sch->data;
1414 struct htb_class *cl = (struct htb_class*)arg;
1415 HTB_DBG(0,1,"htb_put q=%p cl=%X ref=%d\n",q,cl?cl->classid:0,cl?cl->refcnt:0);
1417 if (--cl->refcnt == 0)
1418 htb_destroy_class(sch,cl);
1421 static int htb_change_class(struct Qdisc *sch, u32 classid,
1422 u32 parentid, struct rtattr **tca, unsigned long *arg)
1425 struct htb_sched *q = (struct htb_sched *)sch->data;
1426 struct htb_class *cl = (struct htb_class*)*arg,*parent;
1427 struct rtattr *opt = tca[TCA_OPTIONS-1];
1428 struct qdisc_rate_table *rtab = NULL, *ctab = NULL;
1429 struct rtattr *tb[TCA_HTB_RTAB];
1430 struct tc_htb_opt *hopt;
1432 /* extract all subattrs from opt attr */
1433 if (!opt || rtattr_parse(tb, TCA_HTB_RTAB, RTA_DATA(opt), RTA_PAYLOAD(opt)) ||
1434 tb[TCA_HTB_PARMS-1] == NULL ||
1435 RTA_PAYLOAD(tb[TCA_HTB_PARMS-1]) < sizeof(*hopt))
1438 parent = parentid == TC_H_ROOT ? NULL : htb_find (parentid,sch);
1440 hopt = RTA_DATA(tb[TCA_HTB_PARMS-1]);
1441 HTB_DBG(0,1,"htb_chg cl=%p, clid=%X, opt/prio=%d, rate=%u, buff=%d, quant=%d\n", cl,cl?cl->classid:0,(int)hopt->prio,hopt->rate.rate,hopt->buffer,hopt->quantum);
1442 rtab = qdisc_get_rtab(&hopt->rate, tb[TCA_HTB_RTAB-1]);
1443 ctab = qdisc_get_rtab(&hopt->ceil, tb[TCA_HTB_CTAB-1]);
1444 if (!rtab || !ctab) goto failure;
1446 if (!cl) { /* new class */
1447 /* check for valid classid */
1448 if (!classid || TC_H_MAJ(classid^sch->handle) || htb_find(classid,sch))
1451 /* check maximal depth */
1452 if (parent && parent->parent && parent->parent->level < 2) {
1453 printk(KERN_ERR "htb: tree is too deep\n");
1457 if ((cl = kmalloc(sizeof(*cl), GFP_KERNEL)) == NULL)
1460 memset(cl, 0, sizeof(*cl));
1462 INIT_LIST_HEAD(&cl->sibling);
1463 INIT_LIST_HEAD(&cl->hlist);
1464 INIT_LIST_HEAD(&cl->children);
1465 INIT_LIST_HEAD(&cl->un.leaf.drop_list);
1467 cl->magic = HTB_CMAGIC;
1471 if (parent && !parent->level) {
1472 /* turn parent into inner node */
1473 sch->q.qlen -= parent->un.leaf.q->q.qlen;
1474 qdisc_destroy (parent->un.leaf.q);
1475 if (parent->prio_activity)
1476 htb_deactivate (q,parent);
1478 /* remove from evt list because of level change */
1479 if (parent->cmode != HTB_CAN_SEND) {
1480 htb_safe_rb_erase(&parent->pq_node,q->wait_pq /*+0*/);
1481 parent->cmode = HTB_CAN_SEND;
1483 parent->level = (parent->parent ? parent->parent->level
1484 : TC_HTB_MAXDEPTH) - 1;
1485 memset (&parent->un.inner,0,sizeof(parent->un.inner));
1487 /* leaf (we) needs elementary qdisc */
1488 if (!(cl->un.leaf.q = qdisc_create_dflt(sch->dev, &pfifo_qdisc_ops)))
1489 cl->un.leaf.q = &noop_qdisc;
1491 cl->classid = classid; cl->parent = parent;
1493 /* set class to be in HTB_CAN_SEND state */
1494 cl->tokens = hopt->buffer;
1495 cl->ctokens = hopt->cbuffer;
1496 cl->mbuffer = 60000000; /* 1min */
1497 PSCHED_GET_TIME(cl->t_c);
1498 cl->cmode = HTB_CAN_SEND;
1500 /* attach to the hash list and parent's family */
1501 list_add_tail(&cl->hlist, q->hash+htb_hash(classid));
1502 list_add_tail(&cl->sibling, parent ? &parent->children : &q->root);
1506 for (i = 0; i < TC_HTB_NUMPRIO; i++) cl->node[i].rb_color = -1;
1507 cl->pq_node.rb_color = -1;
1510 } else sch_tree_lock(sch);
1512 /* it used to be a nasty bug here, we have to check that node
1513 is really leaf before changing cl->un.leaf ! */
1515 cl->un.leaf.quantum = rtab->rate.rate / q->rate2quantum;
1516 if (!hopt->quantum && cl->un.leaf.quantum < 1000) {
1517 printk(KERN_WARNING "HTB: quantum of class %X is small. Consider r2q change.", cl->classid);
1518 cl->un.leaf.quantum = 1000;
1520 if (!hopt->quantum && cl->un.leaf.quantum > 200000) {
1521 printk(KERN_WARNING "HTB: quantum of class %X is big. Consider r2q change.", cl->classid);
1522 cl->un.leaf.quantum = 200000;
1525 cl->un.leaf.quantum = hopt->quantum;
1526 if ((cl->un.leaf.prio = hopt->prio) >= TC_HTB_NUMPRIO)
1527 cl->un.leaf.prio = TC_HTB_NUMPRIO - 1;
1530 cl->buffer = hopt->buffer;
1531 cl->cbuffer = hopt->cbuffer;
1532 if (cl->rate) qdisc_put_rtab(cl->rate); cl->rate = rtab;
1533 if (cl->ceil) qdisc_put_rtab(cl->ceil); cl->ceil = ctab;
1534 sch_tree_unlock(sch);
1536 *arg = (unsigned long)cl;
1540 if (rtab) qdisc_put_rtab(rtab);
1541 if (ctab) qdisc_put_rtab(ctab);
1545 static struct tcf_proto **htb_find_tcf(struct Qdisc *sch, unsigned long arg)
1547 struct htb_sched *q = (struct htb_sched *)sch->data;
1548 struct htb_class *cl = (struct htb_class *)arg;
1549 struct tcf_proto **fl = cl ? &cl->filter_list : &q->filter_list;
1550 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);
1554 static unsigned long htb_bind_filter(struct Qdisc *sch, unsigned long parent,
1557 struct htb_sched *q = (struct htb_sched *)sch->data;
1558 struct htb_class *cl = htb_find (classid,sch);
1559 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);
1560 /*if (cl && !cl->level) return 0;
1561 The line above used to be there to prevent attaching filters to
1562 leaves. But at least tc_index filter uses this just to get class
1563 for other reasons so that we have to allow for it.
1565 19.6.2002 As Werner explained it is ok - bind filter is just
1566 another way to "lock" the class - unlike "get" this lock can
1567 be broken by class during destroy IIUC.
1573 return (unsigned long)cl;
1576 static void htb_unbind_filter(struct Qdisc *sch, unsigned long arg)
1578 struct htb_sched *q = (struct htb_sched *)sch->data;
1579 struct htb_class *cl = (struct htb_class *)arg;
1580 HTB_DBG(0,2,"htb_unbind q=%p cl=%p fref=%d\n",q,cl,cl?cl->filter_cnt:q->filter_cnt);
1587 static void htb_walk(struct Qdisc *sch, struct qdisc_walker *arg)
1589 struct htb_sched *q = (struct htb_sched *)sch->data;
1595 for (i = 0; i < HTB_HSIZE; i++) {
1596 struct list_head *p;
1597 list_for_each (p,q->hash+i) {
1598 struct htb_class *cl = list_entry(p,struct htb_class,hlist);
1599 if (arg->count < arg->skip) {
1603 if (arg->fn(sch, (unsigned long)cl, arg) < 0) {
1612 static struct Qdisc_class_ops htb_class_ops =
1629 struct Qdisc_ops htb_qdisc_ops =
1634 sizeof(struct htb_sched),
1644 NULL /* htb_change */,
1650 int init_module(void)
1652 return register_qdisc(&htb_qdisc_ops);
1655 void cleanup_module(void)
1657 unregister_qdisc(&htb_qdisc_ops);
1659 MODULE_LICENSE("GPL");