--- linux-2.6.20-rc6.base/net/sched/sch_htb.c 2007-01-25 03:19:28.000000000 +0100 +++ linux-2.6.20-rc6/net/sched/sch_htb.c 2007-02-01 05:44:36.000000000 +0100 @@ -68,16 +68,37 @@ one less than their parent. */ -#define HTB_HSIZE 16 /* classid hash size */ -#define HTB_EWMAC 2 /* rate average over HTB_EWMAC*HTB_HSIZE sec */ -#define HTB_RATECM 1 /* whether to use rate computer */ +#define HTB_MAX_CLS (TC_H_MIN(-1)+1) +#define HTB_CLS_ARRAY_SIZE PAGE_SIZE +#define HTB_CLS_PER_ARRAY (HTB_CLS_ARRAY_SIZE / sizeof(void*)) +#define HTB_CLS_ARRAYS (HTB_MAX_CLS / HTB_CLS_PER_ARRAY) +#define HTB_CLS_ARRAY(CID) (CID / HTB_CLS_PER_ARRAY) +#define HTB_CLS_INDEX(CID) (CID & (HTB_CLS_PER_ARRAY-1)) + + #define HTB_HYSTERESIS 1 /* whether to use mode hysteresis for speedup */ -#define HTB_VER 0x30011 /* major must be matched with number suplied by TC as version */ +#define HTB_VER 0x30012 /* major must be matched with number suplied by TC as version */ #if HTB_VER >> 16 != TC_HTB_PROTOVER #error "Mismatched sch_htb.c and pkt_sch.h" #endif +/* Whether to use rate computer. This is only used for statistics output to + userspace (tc -s class show dev ...); if you do not care about that and + want the last bit of performance, disable this. */ +#define HTB_RATECM +#ifdef HTB_RATECM +/* Time between rate computation updates, in seconds, for each class. */ +#define HTB_RATECM_UPDATE_INTERVAL 16 +/* How many HTB_RATECM_UPDATE_INTERVAL intervals to average over when + computing the rate. If set to 1, the computed rate will be exactly the + observed rate of the last interval. If set to higher values, the computed + rate will converge slower, but also vary less with small, temporary changes + in traffic. +*/ +#define HTB_RATECM_AVERAGE_INTERVALS 2 +#endif + /* used internaly to keep status of single class */ enum htb_cmode { HTB_CANT_SEND, /* class can't send and can't borrow */ @@ -104,7 +125,7 @@ /* topology */ int level; /* our level (see above) */ struct htb_class *parent; /* parent class */ - struct hlist_node hlist; /* classid hash list item */ + struct list_head clist; /* classid list item */ struct list_head sibling; /* sibling list item */ struct list_head children; /* children list */ @@ -165,9 +186,13 @@ return rate->data[slot]; } +typedef struct htb_class* htb_cls_array[HTB_CLS_PER_ARRAY]; + struct htb_sched { - struct list_head root; /* root classes list */ - struct hlist_head hash[HTB_HSIZE]; /* hashed by classid */ + struct list_head root; /* root classes list */ + struct list_head clist; /* all classes list */ + /* all classes arrays for fast lookup */ + htb_cls_array* classes[HTB_CLS_ARRAYS]; struct list_head drops[TC_HTB_NUMPRIO];/* active leaves (for drops) */ /* self list - roots of self generating tree */ @@ -198,8 +223,10 @@ psched_time_t now; /* cached dequeue time */ struct timer_list timer; /* send delay timer */ #ifdef HTB_RATECM - struct timer_list rttim; /* rate computer timer */ - int recmp_bucket; /* which hash bucket to recompute next */ + struct timer_list rttim;/* rate computer timer */ + int clscnt; /* total number of classes */ + struct list_head *rtcur;/* current class to update rate timer for */ + int rtiter; /* current iteration (1..UPDATE_INTERVAL) */ #endif /* non shaped skbs; let them go directly thru */ @@ -209,32 +236,22 @@ long direct_pkts; }; -/* compute hash of size HTB_HSIZE for given handle */ -static inline int htb_hash(u32 h) -{ -#if HTB_HSIZE != 16 -#error "Declare new hash for your HTB_HSIZE" -#endif - h ^= h >> 8; /* stolen from cbq_hash */ - h ^= h >> 4; - return h & 0xf; -} - -/* find class in global hash table using given handle */ +/* find class in class arrays using given handle */ static inline struct htb_class *htb_find(u32 handle, struct Qdisc *sch) { struct htb_sched *q = qdisc_priv(sch); - struct hlist_node *p; - struct htb_class *cl; + htb_cls_array* a; + int minorid; if (TC_H_MAJ(handle) != sch->handle) return NULL; - hlist_for_each_entry(cl, p, q->hash + htb_hash(handle), hlist) { - if (cl->classid == handle) - return cl; - } - return NULL; + minorid = TC_H_MIN(handle); + a = q->classes[HTB_CLS_ARRAY(minorid)]; + if (a == NULL) + return NULL; + + return (*a)[HTB_CLS_INDEX(minorid)]; } /** @@ -689,13 +706,14 @@ } #ifdef HTB_RATECM -#define RT_GEN(D,R) R+=D-(R/HTB_EWMAC);D=0 +#define RT_GEN(R,S) R+=S-(R/HTB_RATECM_AVERAGE_INTERVALS);S=0 +/* recompute rate for approximately clscnt/UPDATE_INTERVAL classes */ static void htb_rate_timer(unsigned long arg) { struct Qdisc *sch = (struct Qdisc *)arg; struct htb_sched *q = qdisc_priv(sch); - struct hlist_node *p; struct htb_class *cl; + int cnt,done; /* lock queue so that we can muck with it */ @@ -704,14 +722,35 @@ q->rttim.expires = jiffies + HZ; add_timer(&q->rttim); - /* scan and recompute one bucket at time */ - if (++q->recmp_bucket >= HTB_HSIZE) - q->recmp_bucket = 0; - - hlist_for_each_entry(cl,p, q->hash + q->recmp_bucket, hlist) { - RT_GEN(cl->sum_bytes, cl->rate_bytes); - RT_GEN(cl->sum_packets, cl->rate_packets); + if (q->clscnt == 0) + goto done; + if (q->rtiter == HTB_RATECM_UPDATE_INTERVAL) + q->rtiter = 0; + if (q->rtiter == 0) + q->rtcur = q->clist.next; + q->rtiter++; + cnt = ((q->clscnt * q->rtiter) / HTB_RATECM_UPDATE_INTERVAL) - + ((q->clscnt * (q->rtiter-1)) / HTB_RATECM_UPDATE_INTERVAL); + done = 0; + for (;;) { + /* end of class list */ + if (q->rtcur == NULL) + break; + /* last iteration must continue until end */ + if ((done == cnt) && + (q->rtiter < HTB_RATECM_UPDATE_INTERVAL)) { + break; + } + cl = list_entry(q->rtcur, struct htb_class, clist); + RT_GEN(cl->rate_bytes, cl->sum_bytes); + RT_GEN(cl->rate_packets, cl->sum_packets); + done++; + q->rtcur = q->rtcur->next; + if (q->rtcur == &q->clist) + q->rtcur = NULL; } + +done: spin_unlock_bh(&sch->dev->queue_lock); } #endif @@ -1058,23 +1097,19 @@ { struct htb_sched *q = qdisc_priv(sch); int i; + struct list_head *p; - for (i = 0; i < HTB_HSIZE; i++) { - struct hlist_node *p; - struct htb_class *cl; - - hlist_for_each_entry(cl, p, q->hash + i, hlist) { - if (cl->level) - memset(&cl->un.inner, 0, sizeof(cl->un.inner)); - else { - if (cl->un.leaf.q) - qdisc_reset(cl->un.leaf.q); - INIT_LIST_HEAD(&cl->un.leaf.drop_list); - } - cl->prio_activity = 0; - cl->cmode = HTB_CAN_SEND; - + list_for_each(p, &q->clist) { + struct htb_class *cl = list_entry(p, struct htb_class, clist); + if (cl->level) + memset(&cl->un.inner, 0, sizeof(cl->un.inner)); + else { + if (cl->un.leaf.q) + qdisc_reset(cl->un.leaf.q); + INIT_LIST_HEAD(&cl->un.leaf.drop_list); } + cl->prio_activity = 0; + cl->cmode = HTB_CAN_SEND; } sch->flags &= ~TCQ_F_THROTTLED; del_timer(&q->timer); @@ -1109,8 +1144,7 @@ } INIT_LIST_HEAD(&q->root); - for (i = 0; i < HTB_HSIZE; i++) - INIT_HLIST_HEAD(q->hash + i); + INIT_LIST_HEAD(&q->clist); for (i = 0; i < TC_HTB_NUMPRIO; i++) INIT_LIST_HEAD(q->drops + i); @@ -1204,8 +1238,10 @@ struct htb_class *cl = (struct htb_class *)arg; #ifdef HTB_RATECM - cl->rate_est.bps = cl->rate_bytes / (HTB_EWMAC * HTB_HSIZE); - cl->rate_est.pps = cl->rate_packets / (HTB_EWMAC * HTB_HSIZE); + cl->rate_est.bps = cl->rate_bytes / + (HTB_RATECM_UPDATE_INTERVAL * HTB_RATECM_AVERAGE_INTERVALS); + cl->rate_est.pps = cl->rate_packets / + (HTB_RATECM_UPDATE_INTERVAL * HTB_RATECM_AVERAGE_INTERVALS); #endif if (!cl->level && cl->un.leaf.q) @@ -1310,6 +1346,7 @@ static void htb_destroy_class(struct Qdisc *sch, struct htb_class *cl) { struct htb_sched *q = qdisc_priv(sch); + int minorid = TC_H_MIN(cl->classid); if (!cl->level) { BUG_TRAP(cl->un.leaf.q); @@ -1325,7 +1362,7 @@ struct htb_class, sibling)); /* note: this delete may happen twice (see htb_delete) */ - hlist_del_init(&cl->hlist); + list_del(&cl->clist); list_del(&cl->sibling); if (cl->prio_activity) @@ -1334,6 +1371,7 @@ if (cl->cmode != HTB_CAN_SEND) htb_safe_rb_erase(&cl->pq_node, q->wait_pq + cl->level); + (*q->classes[HTB_CLS_ARRAY(minorid)])[HTB_CLS_INDEX(minorid)] = NULL; kfree(cl); } @@ -1341,6 +1379,7 @@ static void htb_destroy(struct Qdisc *sch) { struct htb_sched *q = qdisc_priv(sch); + int i; del_timer_sync(&q->timer); #ifdef HTB_RATECM @@ -1355,6 +1394,8 @@ while (!list_empty(&q->root)) htb_destroy_class(sch, list_entry(q->root.next, struct htb_class, sibling)); + for (i=0; iclasses[i]); __skb_queue_purge(&q->direct_queue); } @@ -1381,8 +1422,15 @@ sch_tree_lock(sch); - /* delete from hash and active; remainder in destroy_class */ - hlist_del_init(&cl->hlist); + /* delete from class list and active; remainder in destroy_class */ + if (q->rtcur == &cl->clist) { + q->rtcur = q->rtcur->next; + if (q->rtcur == &q->clist) + q->rtcur = NULL; + } + if (--q->clscnt == 0) + q->rtiter = 0; + list_del_init(&cl->clist); if (!cl->level) { qlen = cl->un.leaf.q->q.qlen; @@ -1422,6 +1470,7 @@ struct qdisc_rate_table *rtab = NULL, *ctab = NULL; struct rtattr *tb[TCA_HTB_RTAB]; struct tc_htb_opt *hopt; + int minorid = TC_H_MIN(classid); /* extract all subattrs from opt attr */ if (!opt || rtattr_parse_nested(tb, TCA_HTB_RTAB, opt) || @@ -1453,12 +1502,18 @@ goto failure; } err = -ENOBUFS; + if (q->classes[HTB_CLS_ARRAY(minorid)] == NULL) { + if ((q->classes[HTB_CLS_ARRAY(minorid)] = + kzalloc(sizeof(htb_cls_array), GFP_KERNEL)) + == NULL) + goto failure; + } if ((cl = kzalloc(sizeof(*cl), GFP_KERNEL)) == NULL) goto failure; cl->refcnt = 1; + INIT_LIST_HEAD(&cl->clist); INIT_LIST_HEAD(&cl->sibling); - INIT_HLIST_NODE(&cl->hlist); INIT_LIST_HEAD(&cl->children); INIT_LIST_HEAD(&cl->un.leaf.drop_list); RB_CLEAR_NODE(&cl->pq_node); @@ -1503,10 +1558,12 @@ PSCHED_GET_TIME(cl->t_c); cl->cmode = HTB_CAN_SEND; - /* attach to the hash list and parent's family */ - hlist_add_head(&cl->hlist, q->hash + htb_hash(classid)); + /* attach to the classes list+array and parent's family */ + list_add_tail(&cl->clist, &q->clist); list_add_tail(&cl->sibling, parent ? &parent->children : &q->root); + (*q->classes[HTB_CLS_ARRAY(minorid)])[HTB_CLS_INDEX(minorid)] = cl; + q->clscnt++; } else sch_tree_lock(sch); @@ -1602,26 +1659,22 @@ static void htb_walk(struct Qdisc *sch, struct qdisc_walker *arg) { struct htb_sched *q = qdisc_priv(sch); - int i; + struct list_head *p; if (arg->stop) return; - for (i = 0; i < HTB_HSIZE; i++) { - struct hlist_node *p; - struct htb_class *cl; - - hlist_for_each_entry(cl, p, q->hash + i, hlist) { - if (arg->count < arg->skip) { - arg->count++; - continue; - } - if (arg->fn(sch, (unsigned long)cl, arg) < 0) { - arg->stop = 1; - return; - } + list_for_each(p, &q->clist) { + struct htb_class *cl = list_entry(p, struct htb_class, clist); + if (arg->count < arg->skip) { arg->count++; + continue; + } + if (arg->fn(sch, (unsigned long)cl, arg) < 0) { + arg->stop = 1; + return; } + arg->count++; } }