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 * 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
23 * spotted bug in dequeue code and helped with fix
25 * fixed requeue routine
26 * and many others. thanks.
28 * $Id: sch_htb.c,v 1.25 2003/12/07 11:08:25 devik Exp devik $
30 #include <linux/module.h>
31 #include <asm/uaccess.h>
32 #include <asm/system.h>
33 #include <linux/bitops.h>
34 #include <linux/types.h>
35 #include <linux/kernel.h>
36 #include <linux/sched.h>
37 #include <linux/string.h>
39 #include <linux/socket.h>
40 #include <linux/sockios.h>
42 #include <linux/errno.h>
43 #include <linux/interrupt.h>
44 #include <linux/if_ether.h>
45 #include <linux/inet.h>
46 #include <linux/netdevice.h>
47 #include <linux/etherdevice.h>
48 #include <linux/notifier.h>
50 #include <net/route.h>
51 #include <linux/skbuff.h>
52 #include <linux/list.h>
53 #include <linux/compiler.h>
55 #include <net/pkt_sched.h>
56 #include <linux/rbtree.h>
60 ========================================================================
61 HTB is like TBF with multiple classes. It is also similar to CBQ because
62 it allows to assign priority to each class in hierarchy.
63 In fact it is another implementation of Floyd's formal sharing.
66 Each class is assigned level. Leaf has ALWAYS level 0 and root
67 classes have level TC_HTB_MAXDEPTH-1. Interior nodes has level
68 one less than their parent.
71 #define HTB_HSIZE 16 /* classid hash size */
72 #define HTB_EWMAC 2 /* rate average over HTB_EWMAC*HTB_HSIZE sec */
73 #define HTB_RATECM 1 /* whether to use rate computer */
74 #define HTB_HYSTERESIS 1/* whether to use mode hysteresis for speedup */
75 #define HTB_QLOCK(S) spin_lock_bh(&(S)->dev->queue_lock)
76 #define HTB_QUNLOCK(S) spin_unlock_bh(&(S)->dev->queue_lock)
77 #define HTB_VER 0x30011 /* major must be matched with number suplied by TC as version */
79 #if HTB_VER >> 16 != TC_HTB_PROTOVER
80 #error "Mismatched sch_htb.c and pkt_sch.h"
83 /* used internaly to keep status of single class */
85 HTB_CANT_SEND, /* class can't send and can't borrow */
86 HTB_MAY_BORROW, /* class can't send but may borrow */
87 HTB_CAN_SEND /* class can send */
90 /* interior & leaf nodes; props specific to leaves are marked L: */
93 /* general class parameters */
95 struct gnet_stats_basic bstats;
96 struct gnet_stats_queue qstats;
97 struct gnet_stats_rate_est rate_est;
98 struct tc_htb_xstats xstats;/* our special stats */
99 int refcnt; /* usage count of this class */
102 /* rate measurement counters */
103 unsigned long rate_bytes,sum_bytes;
104 unsigned long rate_packets,sum_packets;
108 int level; /* our level (see above) */
109 struct htb_class *parent; /* parent class */
110 struct list_head hlist; /* classid hash list item */
111 struct list_head sibling; /* sibling list item */
112 struct list_head children; /* children list */
115 struct htb_class_leaf {
120 int deficit[TC_HTB_MAXDEPTH];
121 struct list_head drop_list;
123 struct htb_class_inner {
124 struct rb_root feed[TC_HTB_NUMPRIO]; /* feed trees */
125 struct rb_node *ptr[TC_HTB_NUMPRIO]; /* current class ptr */
126 /* When class changes from state 1->2 and disconnects from
127 parent's feed then we lost ptr value and start from the
128 first child again. Here we store classid of the
129 last valid ptr (used when ptr is NULL). */
130 u32 last_ptr_id[TC_HTB_NUMPRIO];
133 struct rb_node node[TC_HTB_NUMPRIO]; /* node for self or feed tree */
134 struct rb_node pq_node; /* node for event queue */
135 unsigned long pq_key; /* the same type as jiffies global */
137 int prio_activity; /* for which prios are we active */
138 enum htb_cmode cmode; /* current mode of the class */
140 /* class attached filters */
141 struct tcf_proto *filter_list;
144 int warned; /* only one warning about non work conserving .. */
146 /* token bucket parameters */
147 struct qdisc_rate_table *rate; /* rate table of the class itself */
148 struct qdisc_rate_table *ceil; /* ceiling rate (limits borrows too) */
149 long buffer,cbuffer; /* token bucket depth/rate */
150 psched_tdiff_t mbuffer; /* max wait time */
151 long tokens,ctokens; /* current number of tokens */
152 psched_time_t t_c; /* checkpoint time */
155 /* TODO: maybe compute rate when size is too large .. or drop ? */
156 static __inline__ long L2T(struct htb_class *cl,struct qdisc_rate_table *rate,
159 int slot = size >> rate->rate.cell_log;
164 return rate->data[slot];
169 struct list_head root; /* root classes list */
170 struct list_head hash[HTB_HSIZE]; /* hashed by classid */
171 struct list_head drops[TC_HTB_NUMPRIO]; /* active leaves (for drops) */
173 /* self list - roots of self generating tree */
174 struct rb_root row[TC_HTB_MAXDEPTH][TC_HTB_NUMPRIO];
175 int row_mask[TC_HTB_MAXDEPTH];
176 struct rb_node *ptr[TC_HTB_MAXDEPTH][TC_HTB_NUMPRIO];
177 u32 last_ptr_id[TC_HTB_MAXDEPTH][TC_HTB_NUMPRIO];
179 /* self wait list - roots of wait PQs per row */
180 struct rb_root wait_pq[TC_HTB_MAXDEPTH];
182 /* time of nearest event per level (row) */
183 unsigned long near_ev_cache[TC_HTB_MAXDEPTH];
185 /* cached value of jiffies in dequeue */
186 unsigned long jiffies;
188 /* whether we hit non-work conserving class during this dequeue; we use */
189 int nwc_hit; /* this to disable mindelay complaint in dequeue */
191 int defcls; /* class where unclassified flows go to */
193 /* filters for qdisc itself */
194 struct tcf_proto *filter_list;
197 int rate2quantum; /* quant = rate / rate2quantum */
198 psched_time_t now; /* cached dequeue time */
199 struct timer_list timer; /* send delay timer */
201 struct timer_list rttim; /* rate computer timer */
202 int recmp_bucket; /* which hash bucket to recompute next */
205 /* non shaped skbs; let them go directly thru */
206 struct sk_buff_head direct_queue;
207 int direct_qlen; /* max qlen of above */
212 /* compute hash of size HTB_HSIZE for given handle */
213 static __inline__ int htb_hash(u32 h)
216 #error "Declare new hash for your HTB_HSIZE"
218 h ^= h>>8; /* stolen from cbq_hash */
223 /* find class in global hash table using given handle */
224 static __inline__ struct htb_class *htb_find(u32 handle, struct Qdisc *sch)
226 struct htb_sched *q = qdisc_priv(sch);
228 if (TC_H_MAJ(handle) != sch->handle)
231 list_for_each (p,q->hash+htb_hash(handle)) {
232 struct htb_class *cl = list_entry(p,struct htb_class,hlist);
233 if (cl->classid == handle)
240 * htb_classify - classify a packet into class
242 * It returns NULL if the packet should be dropped or -1 if the packet
243 * should be passed directly thru. In all other cases leaf class is returned.
244 * We allow direct class selection by classid in priority. The we examine
245 * filters in qdisc and in inner nodes (if higher filter points to the inner
246 * node). If we end up with classid MAJOR:0 we enqueue the skb into special
247 * internal fifo (direct). These packets then go directly thru. If we still
248 * have no valid leaf we try to use MAJOR:default leaf. It still unsuccessfull
249 * then finish and return direct queue.
251 #define HTB_DIRECT (struct htb_class*)-1
252 static inline u32 htb_classid(struct htb_class *cl)
254 return (cl && cl != HTB_DIRECT) ? cl->classid : TC_H_UNSPEC;
257 static struct htb_class *htb_classify(struct sk_buff *skb, struct Qdisc *sch, int *qerr)
259 struct htb_sched *q = qdisc_priv(sch);
260 struct htb_class *cl;
261 struct tcf_result res;
262 struct tcf_proto *tcf;
265 /* allow to select class by setting skb->priority to valid classid;
266 note that nfmark can be used too by attaching filter fw with no
268 if (skb->priority == sch->handle)
269 return HTB_DIRECT; /* X:0 (direct flow) selected */
270 if ((cl = htb_find(skb->priority,sch)) != NULL && cl->level == 0)
273 *qerr = NET_XMIT_BYPASS;
274 tcf = q->filter_list;
275 while (tcf && (result = tc_classify(skb, tcf, &res)) >= 0) {
276 #ifdef CONFIG_NET_CLS_ACT
280 *qerr = NET_XMIT_SUCCESS;
284 #elif defined(CONFIG_NET_CLS_POLICE)
285 if (result == TC_POLICE_SHOT)
288 if ((cl = (void*)res.class) == NULL) {
289 if (res.classid == sch->handle)
290 return HTB_DIRECT; /* X:0 (direct flow) */
291 if ((cl = htb_find(res.classid,sch)) == NULL)
292 break; /* filter selected invalid classid */
295 return cl; /* we hit leaf; return it */
297 /* we have got inner class; apply inner filter chain */
298 tcf = cl->filter_list;
300 /* classification failed; try to use default class */
301 cl = htb_find(TC_H_MAKE(TC_H_MAJ(sch->handle),q->defcls),sch);
302 if (!cl || cl->level)
303 return HTB_DIRECT; /* bad default .. this is safe bet */
308 * htb_add_to_id_tree - adds class to the round robin list
310 * Routine adds class to the list (actually tree) sorted by classid.
311 * Make sure that class is not already on such list for given prio.
313 static void htb_add_to_id_tree (struct rb_root *root,
314 struct htb_class *cl,int prio)
316 struct rb_node **p = &root->rb_node, *parent = NULL;
319 struct htb_class *c; parent = *p;
320 c = rb_entry(parent, struct htb_class, node[prio]);
322 if (cl->classid > c->classid)
323 p = &parent->rb_right;
325 p = &parent->rb_left;
327 rb_link_node(&cl->node[prio], parent, p);
328 rb_insert_color(&cl->node[prio], root);
332 * htb_add_to_wait_tree - adds class to the event queue with delay
334 * The class is added to priority event queue to indicate that class will
335 * change its mode in cl->pq_key microseconds. Make sure that class is not
336 * already in the queue.
338 static void htb_add_to_wait_tree (struct htb_sched *q,
339 struct htb_class *cl,long delay)
341 struct rb_node **p = &q->wait_pq[cl->level].rb_node, *parent = NULL;
343 cl->pq_key = q->jiffies + PSCHED_US2JIFFIE(delay);
344 if (cl->pq_key == q->jiffies)
347 /* update the nearest event cache */
348 if (time_after(q->near_ev_cache[cl->level], cl->pq_key))
349 q->near_ev_cache[cl->level] = cl->pq_key;
352 struct htb_class *c; parent = *p;
353 c = rb_entry(parent, struct htb_class, pq_node);
354 if (time_after_eq(cl->pq_key, c->pq_key))
355 p = &parent->rb_right;
357 p = &parent->rb_left;
359 rb_link_node(&cl->pq_node, parent, p);
360 rb_insert_color(&cl->pq_node, &q->wait_pq[cl->level]);
364 * htb_next_rb_node - finds next node in binary tree
366 * When we are past last key we return NULL.
367 * Average complexity is 2 steps per call.
369 static void htb_next_rb_node(struct rb_node **n)
375 * htb_add_class_to_row - add class to its row
377 * The class is added to row at priorities marked in mask.
378 * It does nothing if mask == 0.
380 static inline void htb_add_class_to_row(struct htb_sched *q,
381 struct htb_class *cl,int mask)
383 q->row_mask[cl->level] |= mask;
385 int prio = ffz(~mask);
386 mask &= ~(1 << prio);
387 htb_add_to_id_tree(q->row[cl->level]+prio,cl,prio);
392 * htb_remove_class_from_row - removes class from its row
394 * The class is removed from row at priorities marked in mask.
395 * It does nothing if mask == 0.
397 static __inline__ void htb_remove_class_from_row(struct htb_sched *q,
398 struct htb_class *cl,int mask)
403 int prio = ffz(~mask);
404 mask &= ~(1 << prio);
405 if (q->ptr[cl->level][prio] == cl->node+prio)
406 htb_next_rb_node(q->ptr[cl->level]+prio);
407 rb_erase(cl->node + prio,q->row[cl->level]+prio);
408 if (!q->row[cl->level][prio].rb_node)
411 q->row_mask[cl->level] &= ~m;
415 * htb_activate_prios - creates active classe's feed chain
417 * The class is connected to ancestors and/or appropriate rows
418 * for priorities it is participating on. cl->cmode must be new
419 * (activated) mode. It does nothing if cl->prio_activity == 0.
421 static void htb_activate_prios(struct htb_sched *q,struct htb_class *cl)
423 struct htb_class *p = cl->parent;
424 long m,mask = cl->prio_activity;
426 while (cl->cmode == HTB_MAY_BORROW && p && mask) {
428 m = mask; while (m) {
432 if (p->un.inner.feed[prio].rb_node)
433 /* parent already has its feed in use so that
434 reset bit in mask as parent is already ok */
435 mask &= ~(1 << prio);
437 htb_add_to_id_tree(p->un.inner.feed+prio,cl,prio);
439 p->prio_activity |= mask;
440 cl = p; p = cl->parent;
443 if (cl->cmode == HTB_CAN_SEND && mask)
444 htb_add_class_to_row(q,cl,mask);
448 * htb_deactivate_prios - remove class from feed chain
450 * cl->cmode must represent old mode (before deactivation). It does
451 * nothing if cl->prio_activity == 0. Class is removed from all feed
454 static void htb_deactivate_prios(struct htb_sched *q, struct htb_class *cl)
456 struct htb_class *p = cl->parent;
457 long m,mask = cl->prio_activity;
460 while (cl->cmode == HTB_MAY_BORROW && p && mask) {
466 if (p->un.inner.ptr[prio] == cl->node+prio) {
467 /* we are removing child which is pointed to from
468 parent feed - forget the pointer but remember
470 p->un.inner.last_ptr_id[prio] = cl->classid;
471 p->un.inner.ptr[prio] = NULL;
474 rb_erase(cl->node + prio,p->un.inner.feed + prio);
476 if (!p->un.inner.feed[prio].rb_node)
480 p->prio_activity &= ~mask;
481 cl = p; p = cl->parent;
484 if (cl->cmode == HTB_CAN_SEND && mask)
485 htb_remove_class_from_row(q,cl,mask);
489 * htb_class_mode - computes and returns current class mode
491 * It computes cl's mode at time cl->t_c+diff and returns it. If mode
492 * is not HTB_CAN_SEND then cl->pq_key is updated to time difference
493 * from now to time when cl will change its state.
494 * Also it is worth to note that class mode doesn't change simply
495 * at cl->{c,}tokens == 0 but there can rather be hysteresis of
496 * 0 .. -cl->{c,}buffer range. It is meant to limit number of
497 * mode transitions per time unit. The speed gain is about 1/6.
499 static __inline__ enum htb_cmode
500 htb_class_mode(struct htb_class *cl,long *diff)
504 if ((toks = (cl->ctokens + *diff)) < (
506 cl->cmode != HTB_CANT_SEND ? -cl->cbuffer :
510 return HTB_CANT_SEND;
512 if ((toks = (cl->tokens + *diff)) >= (
514 cl->cmode == HTB_CAN_SEND ? -cl->buffer :
520 return HTB_MAY_BORROW;
524 * htb_change_class_mode - changes classe's mode
526 * This should be the only way how to change classe's mode under normal
527 * cirsumstances. Routine will update feed lists linkage, change mode
528 * and add class to the wait event queue if appropriate. New mode should
529 * be different from old one and cl->pq_key has to be valid if changing
530 * to mode other than HTB_CAN_SEND (see htb_add_to_wait_tree).
533 htb_change_class_mode(struct htb_sched *q, struct htb_class *cl, long *diff)
535 enum htb_cmode new_mode = htb_class_mode(cl,diff);
538 if (new_mode == cl->cmode)
541 if (cl->prio_activity) { /* not necessary: speed optimization */
542 if (cl->cmode != HTB_CANT_SEND)
543 htb_deactivate_prios(q,cl);
544 cl->cmode = new_mode;
545 if (new_mode != HTB_CANT_SEND)
546 htb_activate_prios(q,cl);
548 cl->cmode = new_mode;
552 * htb_activate - inserts leaf cl into appropriate active feeds
554 * Routine learns (new) priority of leaf and activates feed chain
555 * for the prio. It can be called on already active leaf safely.
556 * It also adds leaf into droplist.
558 static __inline__ void htb_activate(struct htb_sched *q,struct htb_class *cl)
560 BUG_TRAP(!cl->level && cl->un.leaf.q && cl->un.leaf.q->q.qlen);
562 if (!cl->prio_activity) {
563 cl->prio_activity = 1 << (cl->un.leaf.aprio = cl->un.leaf.prio);
564 htb_activate_prios(q,cl);
565 list_add_tail(&cl->un.leaf.drop_list,q->drops+cl->un.leaf.aprio);
570 * htb_deactivate - remove leaf cl from active feeds
572 * Make sure that leaf is active. In the other words it can't be called
573 * with non-active leaf. It also removes class from the drop list.
575 static __inline__ void
576 htb_deactivate(struct htb_sched *q,struct htb_class *cl)
578 BUG_TRAP(cl->prio_activity);
580 htb_deactivate_prios(q,cl);
581 cl->prio_activity = 0;
582 list_del_init(&cl->un.leaf.drop_list);
585 static int htb_enqueue(struct sk_buff *skb, struct Qdisc *sch)
588 struct htb_sched *q = qdisc_priv(sch);
589 struct htb_class *cl = htb_classify(skb,sch,&ret);
591 if (cl == HTB_DIRECT) {
592 /* enqueue to helper queue */
593 if (q->direct_queue.qlen < q->direct_qlen) {
594 __skb_queue_tail(&q->direct_queue, skb);
599 return NET_XMIT_DROP;
601 #ifdef CONFIG_NET_CLS_ACT
603 if (ret == NET_XMIT_BYPASS)
608 } else if (cl->un.leaf.q->enqueue(skb, cl->un.leaf.q) != NET_XMIT_SUCCESS) {
611 return NET_XMIT_DROP;
613 cl->bstats.packets++; cl->bstats.bytes += skb->len;
618 sch->bstats.packets++; sch->bstats.bytes += skb->len;
619 return NET_XMIT_SUCCESS;
622 /* TODO: requeuing packet charges it to policers again !! */
623 static int htb_requeue(struct sk_buff *skb, struct Qdisc *sch)
625 struct htb_sched *q = qdisc_priv(sch);
626 int ret = NET_XMIT_SUCCESS;
627 struct htb_class *cl = htb_classify(skb,sch, &ret);
628 struct sk_buff *tskb;
630 if (cl == HTB_DIRECT || !cl) {
631 /* enqueue to helper queue */
632 if (q->direct_queue.qlen < q->direct_qlen && cl) {
633 __skb_queue_head(&q->direct_queue, skb);
635 __skb_queue_head(&q->direct_queue, skb);
636 tskb = __skb_dequeue_tail(&q->direct_queue);
641 } else if (cl->un.leaf.q->ops->requeue(skb, cl->un.leaf.q) != NET_XMIT_SUCCESS) {
644 return NET_XMIT_DROP;
649 sch->qstats.requeues++;
650 return NET_XMIT_SUCCESS;
653 static void htb_timer(unsigned long arg)
655 struct Qdisc *sch = (struct Qdisc*)arg;
656 sch->flags &= ~TCQ_F_THROTTLED;
658 netif_schedule(sch->dev);
662 #define RT_GEN(D,R) R+=D-(R/HTB_EWMAC);D=0
663 static void htb_rate_timer(unsigned long arg)
665 struct Qdisc *sch = (struct Qdisc*)arg;
666 struct htb_sched *q = qdisc_priv(sch);
669 /* lock queue so that we can muck with it */
672 q->rttim.expires = jiffies + HZ;
673 add_timer(&q->rttim);
675 /* scan and recompute one bucket at time */
676 if (++q->recmp_bucket >= HTB_HSIZE)
678 list_for_each (p,q->hash+q->recmp_bucket) {
679 struct htb_class *cl = list_entry(p,struct htb_class,hlist);
681 RT_GEN (cl->sum_bytes,cl->rate_bytes);
682 RT_GEN (cl->sum_packets,cl->rate_packets);
689 * htb_charge_class - charges amount "bytes" to leaf and ancestors
691 * Routine assumes that packet "bytes" long was dequeued from leaf cl
692 * borrowing from "level". It accounts bytes to ceil leaky bucket for
693 * leaf and all ancestors and to rate bucket for ancestors at levels
694 * "level" and higher. It also handles possible change of mode resulting
695 * from the update. Note that mode can also increase here (MAY_BORROW to
696 * CAN_SEND) because we can use more precise clock that event queue here.
697 * In such case we remove class from event queue first.
699 static void htb_charge_class(struct htb_sched *q,struct htb_class *cl,
703 enum htb_cmode old_mode;
705 #define HTB_ACCNT(T,B,R) toks = diff + cl->T; \
706 if (toks > cl->B) toks = cl->B; \
707 toks -= L2T(cl, cl->R, bytes); \
708 if (toks <= -cl->mbuffer) toks = 1-cl->mbuffer; \
712 diff = PSCHED_TDIFF_SAFE(q->now, cl->t_c, (u32)cl->mbuffer);
713 if (cl->level >= level) {
714 if (cl->level == level) cl->xstats.lends++;
715 HTB_ACCNT (tokens,buffer,rate);
717 cl->xstats.borrows++;
718 cl->tokens += diff; /* we moved t_c; update tokens */
720 HTB_ACCNT (ctokens,cbuffer,ceil);
723 old_mode = cl->cmode; diff = 0;
724 htb_change_class_mode(q,cl,&diff);
725 if (old_mode != cl->cmode) {
726 if (old_mode != HTB_CAN_SEND)
727 rb_erase(&cl->pq_node,q->wait_pq+cl->level);
728 if (cl->cmode != HTB_CAN_SEND)
729 htb_add_to_wait_tree (q,cl,diff);
733 /* update rate counters */
734 cl->sum_bytes += bytes; cl->sum_packets++;
737 /* update byte stats except for leaves which are already updated */
739 cl->bstats.bytes += bytes;
740 cl->bstats.packets++;
747 * htb_do_events - make mode changes to classes at the level
749 * Scans event queue for pending events and applies them. Returns jiffies to
750 * next pending event (0 for no event in pq).
751 * Note: Aplied are events whose have cl->pq_key <= jiffies.
753 static long htb_do_events(struct htb_sched *q,int level)
757 for (i = 0; i < 500; i++) {
758 struct htb_class *cl;
760 struct rb_node *p = q->wait_pq[level].rb_node;
762 while (p->rb_left) p = p->rb_left;
764 cl = rb_entry(p, struct htb_class, pq_node);
765 if (time_after(cl->pq_key, q->jiffies)) {
766 return cl->pq_key - q->jiffies;
768 rb_erase(p,q->wait_pq+level);
769 diff = PSCHED_TDIFF_SAFE(q->now, cl->t_c, (u32)cl->mbuffer);
770 htb_change_class_mode(q,cl,&diff);
771 if (cl->cmode != HTB_CAN_SEND)
772 htb_add_to_wait_tree (q,cl,diff);
775 printk(KERN_WARNING "htb: too many events !\n");
779 /* Returns class->node+prio from id-tree where classe's id is >= id. NULL
780 is no such one exists. */
781 static struct rb_node *
782 htb_id_find_next_upper(int prio,struct rb_node *n,u32 id)
784 struct rb_node *r = NULL;
786 struct htb_class *cl = rb_entry(n,struct htb_class,node[prio]);
787 if (id == cl->classid) return n;
789 if (id > cl->classid) {
800 * htb_lookup_leaf - returns next leaf class in DRR order
802 * Find leaf where current feed pointers points to.
804 static struct htb_class *
805 htb_lookup_leaf(struct rb_root *tree,int prio,struct rb_node **pptr,u32 *pid)
809 struct rb_node *root;
810 struct rb_node **pptr;
812 } stk[TC_HTB_MAXDEPTH],*sp = stk;
814 BUG_TRAP(tree->rb_node);
815 sp->root = tree->rb_node;
819 for (i = 0; i < 65535; i++) {
820 if (!*sp->pptr && *sp->pid) {
821 /* ptr was invalidated but id is valid - try to recover
822 the original or next ptr */
823 *sp->pptr = htb_id_find_next_upper(prio,sp->root,*sp->pid);
825 *sp->pid = 0; /* ptr is valid now so that remove this hint as it
826 can become out of date quickly */
827 if (!*sp->pptr) { /* we are at right end; rewind & go up */
828 *sp->pptr = sp->root;
829 while ((*sp->pptr)->rb_left)
830 *sp->pptr = (*sp->pptr)->rb_left;
833 BUG_TRAP(*sp->pptr); if(!*sp->pptr) return NULL;
834 htb_next_rb_node (sp->pptr);
837 struct htb_class *cl;
838 cl = rb_entry(*sp->pptr,struct htb_class,node[prio]);
841 (++sp)->root = cl->un.inner.feed[prio].rb_node;
842 sp->pptr = cl->un.inner.ptr+prio;
843 sp->pid = cl->un.inner.last_ptr_id+prio;
850 /* dequeues packet at given priority and level; call only if
851 you are sure that there is active class at prio/level */
852 static struct sk_buff *
853 htb_dequeue_tree(struct htb_sched *q,int prio,int level)
855 struct sk_buff *skb = NULL;
856 struct htb_class *cl,*start;
857 /* look initial class up in the row */
858 start = cl = htb_lookup_leaf (q->row[level]+prio,prio,
859 q->ptr[level]+prio,q->last_ptr_id[level]+prio);
864 if (!cl) return NULL;
866 /* class can be empty - it is unlikely but can be true if leaf
867 qdisc drops packets in enqueue routine or if someone used
868 graft operation on the leaf since last dequeue;
869 simply deactivate and skip such class */
870 if (unlikely(cl->un.leaf.q->q.qlen == 0)) {
871 struct htb_class *next;
872 htb_deactivate(q,cl);
874 /* row/level might become empty */
875 if ((q->row_mask[level] & (1 << prio)) == 0)
878 next = htb_lookup_leaf (q->row[level]+prio,
879 prio,q->ptr[level]+prio,q->last_ptr_id[level]+prio);
881 if (cl == start) /* fix start if we just deleted it */
887 if (likely((skb = cl->un.leaf.q->dequeue(cl->un.leaf.q)) != NULL))
890 printk(KERN_WARNING "htb: class %X isn't work conserving ?!\n",cl->classid);
894 htb_next_rb_node((level?cl->parent->un.inner.ptr:q->ptr[0])+prio);
895 cl = htb_lookup_leaf (q->row[level]+prio,prio,q->ptr[level]+prio,
896 q->last_ptr_id[level]+prio);
898 } while (cl != start);
900 if (likely(skb != NULL)) {
901 if ((cl->un.leaf.deficit[level] -= skb->len) < 0) {
902 cl->un.leaf.deficit[level] += cl->un.leaf.quantum;
903 htb_next_rb_node((level?cl->parent->un.inner.ptr:q->ptr[0])+prio);
905 /* this used to be after charge_class but this constelation
906 gives us slightly better performance */
907 if (!cl->un.leaf.q->q.qlen)
908 htb_deactivate (q,cl);
909 htb_charge_class (q,cl,level,skb->len);
914 static void htb_delay_by(struct Qdisc *sch,long delay)
916 struct htb_sched *q = qdisc_priv(sch);
917 if (delay <= 0) delay = 1;
918 if (unlikely(delay > 5*HZ)) {
920 printk(KERN_INFO "HTB delay %ld > 5sec\n", delay);
923 /* why don't use jiffies here ? because expires can be in past */
924 mod_timer(&q->timer, q->jiffies + delay);
925 sch->flags |= TCQ_F_THROTTLED;
926 sch->qstats.overlimits++;
929 static struct sk_buff *htb_dequeue(struct Qdisc *sch)
931 struct sk_buff *skb = NULL;
932 struct htb_sched *q = qdisc_priv(sch);
936 q->jiffies = jiffies;
938 /* try to dequeue direct packets as high prio (!) to minimize cpu work */
939 if ((skb = __skb_dequeue(&q->direct_queue)) != NULL) {
940 sch->flags &= ~TCQ_F_THROTTLED;
945 if (!sch->q.qlen) goto fin;
946 PSCHED_GET_TIME(q->now);
948 min_delay = LONG_MAX;
950 for (level = 0; level < TC_HTB_MAXDEPTH; level++) {
951 /* common case optimization - skip event handler quickly */
954 if (time_after_eq(q->jiffies, q->near_ev_cache[level])) {
955 delay = htb_do_events(q,level);
956 q->near_ev_cache[level] = q->jiffies + (delay ? delay : HZ);
958 delay = q->near_ev_cache[level] - q->jiffies;
960 if (delay && min_delay > delay)
962 m = ~q->row_mask[level];
963 while (m != (int)(-1)) {
966 skb = htb_dequeue_tree(q,prio,level);
967 if (likely(skb != NULL)) {
969 sch->flags &= ~TCQ_F_THROTTLED;
974 htb_delay_by (sch,min_delay > 5*HZ ? 5*HZ : min_delay);
979 /* try to drop from each class (by prio) until one succeed */
980 static unsigned int htb_drop(struct Qdisc* sch)
982 struct htb_sched *q = qdisc_priv(sch);
985 for (prio = TC_HTB_NUMPRIO - 1; prio >= 0; prio--) {
987 list_for_each (p,q->drops+prio) {
988 struct htb_class *cl = list_entry(p, struct htb_class,
991 if (cl->un.leaf.q->ops->drop &&
992 (len = cl->un.leaf.q->ops->drop(cl->un.leaf.q))) {
994 if (!cl->un.leaf.q->q.qlen)
995 htb_deactivate (q,cl);
1003 /* reset all classes */
1004 /* always caled under BH & queue lock */
1005 static void htb_reset(struct Qdisc* sch)
1007 struct htb_sched *q = qdisc_priv(sch);
1010 for (i = 0; i < HTB_HSIZE; i++) {
1011 struct list_head *p;
1012 list_for_each (p,q->hash+i) {
1013 struct htb_class *cl = list_entry(p,struct htb_class,hlist);
1015 memset(&cl->un.inner,0,sizeof(cl->un.inner));
1018 qdisc_reset(cl->un.leaf.q);
1019 INIT_LIST_HEAD(&cl->un.leaf.drop_list);
1021 cl->prio_activity = 0;
1022 cl->cmode = HTB_CAN_SEND;
1026 sch->flags &= ~TCQ_F_THROTTLED;
1027 del_timer(&q->timer);
1028 __skb_queue_purge(&q->direct_queue);
1030 memset(q->row,0,sizeof(q->row));
1031 memset(q->row_mask,0,sizeof(q->row_mask));
1032 memset(q->wait_pq,0,sizeof(q->wait_pq));
1033 memset(q->ptr,0,sizeof(q->ptr));
1034 for (i = 0; i < TC_HTB_NUMPRIO; i++)
1035 INIT_LIST_HEAD(q->drops+i);
1038 static int htb_init(struct Qdisc *sch, struct rtattr *opt)
1040 struct htb_sched *q = qdisc_priv(sch);
1041 struct rtattr *tb[TCA_HTB_INIT];
1042 struct tc_htb_glob *gopt;
1044 if (!opt || rtattr_parse_nested(tb, TCA_HTB_INIT, opt) ||
1045 tb[TCA_HTB_INIT-1] == NULL ||
1046 RTA_PAYLOAD(tb[TCA_HTB_INIT-1]) < sizeof(*gopt)) {
1047 printk(KERN_ERR "HTB: hey probably you have bad tc tool ?\n");
1050 gopt = RTA_DATA(tb[TCA_HTB_INIT-1]);
1051 if (gopt->version != HTB_VER >> 16) {
1052 printk(KERN_ERR "HTB: need tc/htb version %d (minor is %d), you have %d\n",
1053 HTB_VER >> 16,HTB_VER & 0xffff,gopt->version);
1057 INIT_LIST_HEAD(&q->root);
1058 for (i = 0; i < HTB_HSIZE; i++)
1059 INIT_LIST_HEAD(q->hash+i);
1060 for (i = 0; i < TC_HTB_NUMPRIO; i++)
1061 INIT_LIST_HEAD(q->drops+i);
1063 init_timer(&q->timer);
1064 skb_queue_head_init(&q->direct_queue);
1066 q->direct_qlen = sch->dev->tx_queue_len;
1067 if (q->direct_qlen < 2) /* some devices have zero tx_queue_len */
1069 q->timer.function = htb_timer;
1070 q->timer.data = (unsigned long)sch;
1073 init_timer(&q->rttim);
1074 q->rttim.function = htb_rate_timer;
1075 q->rttim.data = (unsigned long)sch;
1076 q->rttim.expires = jiffies + HZ;
1077 add_timer(&q->rttim);
1079 if ((q->rate2quantum = gopt->rate2quantum) < 1)
1080 q->rate2quantum = 1;
1081 q->defcls = gopt->defcls;
1086 static int htb_dump(struct Qdisc *sch, struct sk_buff *skb)
1088 struct htb_sched *q = qdisc_priv(sch);
1089 unsigned char *b = skb->tail;
1091 struct tc_htb_glob gopt;
1093 gopt.direct_pkts = q->direct_pkts;
1095 gopt.version = HTB_VER;
1096 gopt.rate2quantum = q->rate2quantum;
1097 gopt.defcls = q->defcls;
1099 rta = (struct rtattr*)b;
1100 RTA_PUT(skb, TCA_OPTIONS, 0, NULL);
1101 RTA_PUT(skb, TCA_HTB_INIT, sizeof(gopt), &gopt);
1102 rta->rta_len = skb->tail - b;
1107 skb_trim(skb, skb->tail - skb->data);
1111 static int htb_dump_class(struct Qdisc *sch, unsigned long arg,
1112 struct sk_buff *skb, struct tcmsg *tcm)
1114 struct htb_class *cl = (struct htb_class*)arg;
1115 unsigned char *b = skb->tail;
1117 struct tc_htb_opt opt;
1120 tcm->tcm_parent = cl->parent ? cl->parent->classid : TC_H_ROOT;
1121 tcm->tcm_handle = cl->classid;
1122 if (!cl->level && cl->un.leaf.q)
1123 tcm->tcm_info = cl->un.leaf.q->handle;
1125 rta = (struct rtattr*)b;
1126 RTA_PUT(skb, TCA_OPTIONS, 0, NULL);
1128 memset (&opt,0,sizeof(opt));
1130 opt.rate = cl->rate->rate; opt.buffer = cl->buffer;
1131 opt.ceil = cl->ceil->rate; opt.cbuffer = cl->cbuffer;
1132 opt.quantum = cl->un.leaf.quantum; opt.prio = cl->un.leaf.prio;
1133 opt.level = cl->level;
1134 RTA_PUT(skb, TCA_HTB_PARMS, sizeof(opt), &opt);
1135 rta->rta_len = skb->tail - b;
1140 skb_trim(skb, b - skb->data);
1145 htb_dump_class_stats(struct Qdisc *sch, unsigned long arg,
1146 struct gnet_dump *d)
1148 struct htb_class *cl = (struct htb_class*)arg;
1151 cl->rate_est.bps = cl->rate_bytes/(HTB_EWMAC*HTB_HSIZE);
1152 cl->rate_est.pps = cl->rate_packets/(HTB_EWMAC*HTB_HSIZE);
1155 if (!cl->level && cl->un.leaf.q)
1156 cl->qstats.qlen = cl->un.leaf.q->q.qlen;
1157 cl->xstats.tokens = cl->tokens;
1158 cl->xstats.ctokens = cl->ctokens;
1160 if (gnet_stats_copy_basic(d, &cl->bstats) < 0 ||
1161 gnet_stats_copy_rate_est(d, &cl->rate_est) < 0 ||
1162 gnet_stats_copy_queue(d, &cl->qstats) < 0)
1165 return gnet_stats_copy_app(d, &cl->xstats, sizeof(cl->xstats));
1168 static int htb_graft(struct Qdisc *sch, unsigned long arg, struct Qdisc *new,
1171 struct htb_class *cl = (struct htb_class*)arg;
1173 if (cl && !cl->level) {
1174 if (new == NULL && (new = qdisc_create_dflt(sch->dev,
1175 &pfifo_qdisc_ops)) == NULL)
1178 if ((*old = xchg(&cl->un.leaf.q, new)) != NULL) {
1179 if (cl->prio_activity)
1180 htb_deactivate (qdisc_priv(sch),cl);
1182 /* TODO: is it correct ? Why CBQ doesn't do it ? */
1183 sch->q.qlen -= (*old)->q.qlen;
1186 sch_tree_unlock(sch);
1192 static struct Qdisc * htb_leaf(struct Qdisc *sch, unsigned long arg)
1194 struct htb_class *cl = (struct htb_class*)arg;
1195 return (cl && !cl->level) ? cl->un.leaf.q : NULL;
1198 static unsigned long htb_get(struct Qdisc *sch, u32 classid)
1200 struct htb_class *cl = htb_find(classid,sch);
1203 return (unsigned long)cl;
1206 static void htb_destroy_filters(struct tcf_proto **fl)
1208 struct tcf_proto *tp;
1210 while ((tp = *fl) != NULL) {
1216 static void htb_destroy_class(struct Qdisc* sch,struct htb_class *cl)
1218 struct htb_sched *q = qdisc_priv(sch);
1220 BUG_TRAP(cl->un.leaf.q);
1221 sch->q.qlen -= cl->un.leaf.q->q.qlen;
1222 qdisc_destroy(cl->un.leaf.q);
1224 qdisc_put_rtab(cl->rate);
1225 qdisc_put_rtab(cl->ceil);
1227 htb_destroy_filters (&cl->filter_list);
1229 while (!list_empty(&cl->children))
1230 htb_destroy_class (sch,list_entry(cl->children.next,
1231 struct htb_class,sibling));
1233 /* note: this delete may happen twice (see htb_delete) */
1234 list_del(&cl->hlist);
1235 list_del(&cl->sibling);
1237 if (cl->prio_activity)
1238 htb_deactivate (q,cl);
1240 if (cl->cmode != HTB_CAN_SEND)
1241 rb_erase(&cl->pq_node,q->wait_pq+cl->level);
1246 /* always caled under BH & queue lock */
1247 static void htb_destroy(struct Qdisc* sch)
1249 struct htb_sched *q = qdisc_priv(sch);
1251 del_timer_sync (&q->timer);
1253 del_timer_sync (&q->rttim);
1255 /* This line used to be after htb_destroy_class call below
1256 and surprisingly it worked in 2.4. But it must precede it
1257 because filter need its target class alive to be able to call
1258 unbind_filter on it (without Oops). */
1259 htb_destroy_filters(&q->filter_list);
1261 while (!list_empty(&q->root))
1262 htb_destroy_class (sch,list_entry(q->root.next,
1263 struct htb_class,sibling));
1265 __skb_queue_purge(&q->direct_queue);
1268 static int htb_delete(struct Qdisc *sch, unsigned long arg)
1270 struct htb_sched *q = qdisc_priv(sch);
1271 struct htb_class *cl = (struct htb_class*)arg;
1273 // TODO: why don't allow to delete subtree ? references ? does
1274 // tc subsys quarantee us that in htb_destroy it holds no class
1275 // refs so that we can remove children safely there ?
1276 if (!list_empty(&cl->children) || cl->filter_cnt)
1281 /* delete from hash and active; remainder in destroy_class */
1282 list_del_init(&cl->hlist);
1283 if (cl->prio_activity)
1284 htb_deactivate (q,cl);
1286 if (--cl->refcnt == 0)
1287 htb_destroy_class(sch,cl);
1289 sch_tree_unlock(sch);
1293 static void htb_put(struct Qdisc *sch, unsigned long arg)
1295 struct htb_class *cl = (struct htb_class*)arg;
1297 if (--cl->refcnt == 0)
1298 htb_destroy_class(sch,cl);
1301 static int htb_change_class(struct Qdisc *sch, u32 classid,
1302 u32 parentid, struct rtattr **tca, unsigned long *arg)
1305 struct htb_sched *q = qdisc_priv(sch);
1306 struct htb_class *cl = (struct htb_class*)*arg,*parent;
1307 struct rtattr *opt = tca[TCA_OPTIONS-1];
1308 struct qdisc_rate_table *rtab = NULL, *ctab = NULL;
1309 struct rtattr *tb[TCA_HTB_RTAB];
1310 struct tc_htb_opt *hopt;
1312 /* extract all subattrs from opt attr */
1313 if (!opt || rtattr_parse_nested(tb, TCA_HTB_RTAB, opt) ||
1314 tb[TCA_HTB_PARMS-1] == NULL ||
1315 RTA_PAYLOAD(tb[TCA_HTB_PARMS-1]) < sizeof(*hopt))
1318 parent = parentid == TC_H_ROOT ? NULL : htb_find (parentid,sch);
1320 hopt = RTA_DATA(tb[TCA_HTB_PARMS-1]);
1322 rtab = qdisc_get_rtab(&hopt->rate, tb[TCA_HTB_RTAB-1]);
1323 ctab = qdisc_get_rtab(&hopt->ceil, tb[TCA_HTB_CTAB-1]);
1324 if (!rtab || !ctab) goto failure;
1326 if (!cl) { /* new class */
1327 struct Qdisc *new_q;
1328 /* check for valid classid */
1329 if (!classid || TC_H_MAJ(classid^sch->handle) || htb_find(classid,sch))
1332 /* check maximal depth */
1333 if (parent && parent->parent && parent->parent->level < 2) {
1334 printk(KERN_ERR "htb: tree is too deep\n");
1338 if ((cl = kzalloc(sizeof(*cl), GFP_KERNEL)) == NULL)
1342 INIT_LIST_HEAD(&cl->sibling);
1343 INIT_LIST_HEAD(&cl->hlist);
1344 INIT_LIST_HEAD(&cl->children);
1345 INIT_LIST_HEAD(&cl->un.leaf.drop_list);
1347 /* create leaf qdisc early because it uses kmalloc(GFP_KERNEL)
1348 so that can't be used inside of sch_tree_lock
1349 -- thanks to Karlis Peisenieks */
1350 new_q = qdisc_create_dflt(sch->dev, &pfifo_qdisc_ops);
1352 if (parent && !parent->level) {
1353 /* turn parent into inner node */
1354 sch->q.qlen -= parent->un.leaf.q->q.qlen;
1355 qdisc_destroy (parent->un.leaf.q);
1356 if (parent->prio_activity)
1357 htb_deactivate (q,parent);
1359 /* remove from evt list because of level change */
1360 if (parent->cmode != HTB_CAN_SEND) {
1361 rb_erase(&parent->pq_node,q->wait_pq);
1362 parent->cmode = HTB_CAN_SEND;
1364 parent->level = (parent->parent ? parent->parent->level
1365 : TC_HTB_MAXDEPTH) - 1;
1366 memset (&parent->un.inner,0,sizeof(parent->un.inner));
1368 /* leaf (we) needs elementary qdisc */
1369 cl->un.leaf.q = new_q ? new_q : &noop_qdisc;
1371 cl->classid = classid; cl->parent = parent;
1373 /* set class to be in HTB_CAN_SEND state */
1374 cl->tokens = hopt->buffer;
1375 cl->ctokens = hopt->cbuffer;
1376 cl->mbuffer = PSCHED_JIFFIE2US(HZ*60); /* 1min */
1377 PSCHED_GET_TIME(cl->t_c);
1378 cl->cmode = HTB_CAN_SEND;
1380 /* attach to the hash list and parent's family */
1381 list_add_tail(&cl->hlist, q->hash+htb_hash(classid));
1382 list_add_tail(&cl->sibling, parent ? &parent->children : &q->root);
1383 } else sch_tree_lock(sch);
1385 /* it used to be a nasty bug here, we have to check that node
1386 is really leaf before changing cl->un.leaf ! */
1388 cl->un.leaf.quantum = rtab->rate.rate / q->rate2quantum;
1389 if (!hopt->quantum && cl->un.leaf.quantum < 1000) {
1390 printk(KERN_WARNING "HTB: quantum of class %X is small. Consider r2q change.\n", cl->classid);
1391 cl->un.leaf.quantum = 1000;
1393 if (!hopt->quantum && cl->un.leaf.quantum > 200000) {
1394 printk(KERN_WARNING "HTB: quantum of class %X is big. Consider r2q change.\n", cl->classid);
1395 cl->un.leaf.quantum = 200000;
1398 cl->un.leaf.quantum = hopt->quantum;
1399 if ((cl->un.leaf.prio = hopt->prio) >= TC_HTB_NUMPRIO)
1400 cl->un.leaf.prio = TC_HTB_NUMPRIO - 1;
1403 cl->buffer = hopt->buffer;
1404 cl->cbuffer = hopt->cbuffer;
1405 if (cl->rate) qdisc_put_rtab(cl->rate); cl->rate = rtab;
1406 if (cl->ceil) qdisc_put_rtab(cl->ceil); cl->ceil = ctab;
1407 sch_tree_unlock(sch);
1409 *arg = (unsigned long)cl;
1413 if (rtab) qdisc_put_rtab(rtab);
1414 if (ctab) qdisc_put_rtab(ctab);
1418 static struct tcf_proto **htb_find_tcf(struct Qdisc *sch, unsigned long arg)
1420 struct htb_sched *q = qdisc_priv(sch);
1421 struct htb_class *cl = (struct htb_class *)arg;
1422 struct tcf_proto **fl = cl ? &cl->filter_list : &q->filter_list;
1427 static unsigned long htb_bind_filter(struct Qdisc *sch, unsigned long parent,
1430 struct htb_sched *q = qdisc_priv(sch);
1431 struct htb_class *cl = htb_find (classid,sch);
1433 /*if (cl && !cl->level) return 0;
1434 The line above used to be there to prevent attaching filters to
1435 leaves. But at least tc_index filter uses this just to get class
1436 for other reasons so that we have to allow for it.
1438 19.6.2002 As Werner explained it is ok - bind filter is just
1439 another way to "lock" the class - unlike "get" this lock can
1440 be broken by class during destroy IIUC.
1446 return (unsigned long)cl;
1449 static void htb_unbind_filter(struct Qdisc *sch, unsigned long arg)
1451 struct htb_sched *q = qdisc_priv(sch);
1452 struct htb_class *cl = (struct htb_class *)arg;
1460 static void htb_walk(struct Qdisc *sch, struct qdisc_walker *arg)
1462 struct htb_sched *q = qdisc_priv(sch);
1468 for (i = 0; i < HTB_HSIZE; i++) {
1469 struct list_head *p;
1470 list_for_each (p,q->hash+i) {
1471 struct htb_class *cl = list_entry(p,struct htb_class,hlist);
1472 if (arg->count < arg->skip) {
1476 if (arg->fn(sch, (unsigned long)cl, arg) < 0) {
1485 static struct Qdisc_class_ops htb_class_ops = {
1490 .change = htb_change_class,
1491 .delete = htb_delete,
1493 .tcf_chain = htb_find_tcf,
1494 .bind_tcf = htb_bind_filter,
1495 .unbind_tcf = htb_unbind_filter,
1496 .dump = htb_dump_class,
1497 .dump_stats = htb_dump_class_stats,
1500 static struct Qdisc_ops htb_qdisc_ops = {
1502 .cl_ops = &htb_class_ops,
1504 .priv_size = sizeof(struct htb_sched),
1505 .enqueue = htb_enqueue,
1506 .dequeue = htb_dequeue,
1507 .requeue = htb_requeue,
1511 .destroy = htb_destroy,
1512 .change = NULL /* htb_change */,
1514 .owner = THIS_MODULE,
1517 static int __init htb_module_init(void)
1519 return register_qdisc(&htb_qdisc_ops);
1521 static void __exit htb_module_exit(void)
1523 unregister_qdisc(&htb_qdisc_ops);
1525 module_init(htb_module_init)
1526 module_exit(htb_module_exit)
1527 MODULE_LICENSE("GPL");