From 6fe1c7a5556807e9d7154a2d2fb938d8a9e47e5f Mon Sep 17 00:00:00 2001 From: Patrick McHardy Date: Sat, 5 Jul 2008 23:21:31 -0700 Subject: net-sched: add dynamically sized qdisc class hash helpers Currently all qdiscs which allow to create classes uses a fixed sized hash table with size 16 to hash the classes. This causes a large bottleneck when using thousands of classes and unbound filters. Add helpers for dynamically sized class hashes to fix this. The following patches will convert the qdiscs to use them. Signed-off-by: Patrick McHardy Signed-off-by: David S. Miller --- include/net/sch_generic.h | 42 ++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 42 insertions(+) (limited to 'include') diff --git a/include/net/sch_generic.h b/include/net/sch_generic.h index a87fc0312ed..073f2580b83 100644 --- a/include/net/sch_generic.h +++ b/include/net/sch_generic.h @@ -167,6 +167,48 @@ extern void qdisc_unlock_tree(struct net_device *dev); extern struct Qdisc noop_qdisc; extern struct Qdisc_ops noop_qdisc_ops; +struct Qdisc_class_common +{ + u32 classid; + struct hlist_node hnode; +}; + +struct Qdisc_class_hash +{ + struct hlist_head *hash; + unsigned int hashsize; + unsigned int hashmask; + unsigned int hashelems; +}; + +static inline unsigned int qdisc_class_hash(u32 id, u32 mask) +{ + id ^= id >> 8; + id ^= id >> 4; + return id & mask; +} + +static inline struct Qdisc_class_common * +qdisc_class_find(struct Qdisc_class_hash *hash, u32 id) +{ + struct Qdisc_class_common *cl; + struct hlist_node *n; + unsigned int h; + + h = qdisc_class_hash(id, hash->hashmask); + hlist_for_each_entry(cl, n, &hash->hash[h], hnode) { + if (cl->classid == id) + return cl; + } + return NULL; +} + +extern int qdisc_class_hash_init(struct Qdisc_class_hash *); +extern void qdisc_class_hash_insert(struct Qdisc_class_hash *, struct Qdisc_class_common *); +extern void qdisc_class_hash_remove(struct Qdisc_class_hash *, struct Qdisc_class_common *); +extern void qdisc_class_hash_grow(struct Qdisc *, struct Qdisc_class_hash *); +extern void qdisc_class_hash_destroy(struct Qdisc_class_hash *); + extern void dev_init_scheduler(struct net_device *dev); extern void dev_shutdown(struct net_device *dev); extern void dev_activate(struct net_device *dev); -- cgit v1.2.3