net-sched 00/06: dynamically sized class hashes v2

net-sched 00/06: dynamically sized class hashes v2

[Patrick McHardy]

These patches add support for dynamically sized class hash tables
to remove a major bottleneck in qdisc filters with many classes
when filters are not bound to classes and convert CBQ, HTB and HFSC
to use them.

Changes since the last posting are mostly suggestions from Martin
Devera and Jarek Poplawski:

- fix missing qdisc hash initialization in CBQ
- use classes directly in hlist iteration instead of Qdisc_class_common
- change qdisc_class_find to return Qdisc_class_common * instead of void *
- new patch to remove child and sibling lists from HTB
- all patches are tested now and considered ready for merging :)

The patches need the two filter destruction fixes that went into
net-2.6.git to apply cleanly, so they won't apply until net-2.6.git
is merged into net-next-2.6.git.


 include/net/sch_generic.h |   42 +++++++++++++
 net/sched/sch_api.c       |  104 ++++++++++++++++++++++++++++++++
 net/sched/sch_cbq.c       |  112 +++++++++++++++++------------------
 net/sched/sch_hfsc.c      |   81 ++++++++++++-------------
 net/sched/sch_htb.c       |  145 ++++++++++++++++++---------------------------
 5 files changed, 299 insertions(+), 185 deletions(-)

Patrick McHardy (6):
      net-sched: add dynamically sized qdisc class hash helpers
      net-sched: sch_hfsc: use dynamic class hash helpers
      net-sched: sch_cbq: use dynamic class hash helpers
      net-sched: sch_htb: move hash and sibling list removal to htb_delete
      net-sched: sch_htb: use dynamic class hash helpers
      net-sched: sch_htb: remove child and sibling lists

net-sched 01/06: add dynamically sized qdisc class hash helpers

[Patrick McHardy]

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 <kaber@trash.net>

---
commit ba0c034039d0c4a76c38cd1d252a4e6a5a65333d
tree 6bf49094e76c1fea2594a404c718ffa2aa652d9a
parent dbe4e4f34c356cd31cf9bc8972c0eb4eadebe920
author Patrick McHardy <kaber@trash.net> Thu, 03 Jul 2008 16:58:45 +0200
committer Patrick McHardy <kaber@trash.net> Thu, 03 Jul 2008 16:58:45 +0200

 include/net/sch_generic.h |   42 ++++++++++++++++++
 net/sched/sch_api.c       |  104 +++++++++++++++++++++++++++++++++++++++++++++
 2 files changed, 146 insertions(+), 0 deletions(-)

diff --git a/include/net/sch_generic.h b/include/net/sch_generic.h
index a87fc03..073f258 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);
diff --git a/net/sched/sch_api.c b/net/sched/sch_api.c
index 10f01ad..e9ebc7a 100644
--- a/net/sched/sch_api.c
+++ b/net/sched/sch_api.c
@@ -316,6 +316,110 @@ void qdisc_watchdog_cancel(struct qdisc_watchdog *wd)
 }
 EXPORT_SYMBOL(qdisc_watchdog_cancel);
 
+struct hlist_head *qdisc_class_hash_alloc(unsigned int n)
+{
+	unsigned int size = n * sizeof(struct hlist_head), i;
+	struct hlist_head *h;
+
+	if (size <= PAGE_SIZE)
+		h = kmalloc(size, GFP_KERNEL);
+	else
+		h = (struct hlist_head *)
+			__get_free_pages(GFP_KERNEL, get_order(size));
+
+	if (h != NULL) {
+		for (i = 0; i < n; i++)
+			INIT_HLIST_HEAD(&h[i]);
+	}
+	return h;
+}
+
+static void qdisc_class_hash_free(struct hlist_head *h, unsigned int n)
+{
+	unsigned int size = n * sizeof(struct hlist_head);
+
+	if (size <= PAGE_SIZE)
+		kfree(h);
+	else
+		free_pages((unsigned long)h, get_order(size));
+}
+
+void qdisc_class_hash_grow(struct Qdisc *sch, struct Qdisc_class_hash *clhash)
+{
+	struct Qdisc_class_common *cl;
+	struct hlist_node *n, *next;
+	struct hlist_head *nhash, *ohash;
+	unsigned int nsize, nmask, osize;
+	unsigned int i, h;
+
+	/* Rehash when load factor exceeds 0.75 */
+	if (clhash->hashelems * 4 <= clhash->hashsize * 3)
+		return;
+	nsize = clhash->hashsize * 2;
+	nmask = nsize - 1;
+	nhash = qdisc_class_hash_alloc(nsize);
+	if (nhash == NULL)
+		return;
+
+	ohash = clhash->hash;
+	osize = clhash->hashsize;
+
+	sch_tree_lock(sch);
+	for (i = 0; i < osize; i++) {
+		hlist_for_each_entry_safe(cl, n, next, &ohash[i], hnode) {
+			h = qdisc_class_hash(cl->classid, nmask);
+			hlist_add_head(&cl->hnode, &nhash[h]);
+		}
+	}
+	clhash->hash     = nhash;
+	clhash->hashsize = nsize;
+	clhash->hashmask = nmask;
+	sch_tree_unlock(sch);
+
+	qdisc_class_hash_free(ohash, osize);
+}
+EXPORT_SYMBOL(qdisc_class_hash_grow);
+
+int qdisc_class_hash_init(struct Qdisc_class_hash *clhash)
+{
+	unsigned int size = 4;
+
+	clhash->hash = qdisc_class_hash_alloc(size);
+	if (clhash->hash == NULL)
+		return -ENOMEM;
+	clhash->hashsize  = size;
+	clhash->hashmask  = size - 1;
+	clhash->hashelems = 0;
+	return 0;
+}
+EXPORT_SYMBOL(qdisc_class_hash_init);
+
+void qdisc_class_hash_destroy(struct Qdisc_class_hash *clhash)
+{
+	qdisc_class_hash_free(clhash->hash, clhash->hashsize);
+}
+EXPORT_SYMBOL(qdisc_class_hash_destroy);
+
+void qdisc_class_hash_insert(struct Qdisc_class_hash *clhash,
+			     struct Qdisc_class_common *cl)
+{
+	unsigned int h;
+
+	INIT_HLIST_NODE(&cl->hnode);
+	h = qdisc_class_hash(cl->classid, clhash->hashmask);
+	hlist_add_head(&cl->hnode, &clhash->hash[h]);
+	clhash->hashelems++;
+}
+EXPORT_SYMBOL(qdisc_class_hash_insert);
+
+void qdisc_class_hash_remove(struct Qdisc_class_hash *clhash,
+			     struct Qdisc_class_common *cl)
+{
+	hlist_del(&cl->hnode);
+	clhash->hashelems--;
+}
+EXPORT_SYMBOL(qdisc_class_hash_remove);
+
 /* Allocate an unique handle from space managed by kernel */
 
 static u32 qdisc_alloc_handle(struct net_device *dev)

net-sched 02/06: sch_hfsc: use dynamic class hash helpers

[Patrick McHardy]

net-sched: sch_hfsc: use dynamic class hash helpers

Signed-off-by: Patrick McHardy <kaber@trash.net>

---
commit d0d016e7dea2408ca6f795fe987f6abae3e5f526
tree 2844dbdc1b13151534c574b97849c84aee02cdd8
parent ba0c034039d0c4a76c38cd1d252a4e6a5a65333d
author Patrick McHardy <kaber@trash.net> Thu, 03 Jul 2008 16:58:46 +0200
committer Patrick McHardy <kaber@trash.net> Thu, 03 Jul 2008 16:58:46 +0200

 net/sched/sch_hfsc.c |   81 +++++++++++++++++++++++++-------------------------
 1 files changed, 40 insertions(+), 41 deletions(-)

diff --git a/net/sched/sch_hfsc.c b/net/sched/sch_hfsc.c
index e817aa0..3a82672 100644
--- a/net/sched/sch_hfsc.c
+++ b/net/sched/sch_hfsc.c
@@ -113,7 +113,7 @@ enum hfsc_class_flags
 
 struct hfsc_class
 {
-	u32		classid;	/* class id */
+	struct Qdisc_class_common cl_common;
 	unsigned int	refcnt;		/* usage count */
 
 	struct gnet_stats_basic bstats;
@@ -134,7 +134,6 @@ struct hfsc_class
 	struct rb_node vt_node;		/* parent's vt_tree member */
 	struct rb_root cf_tree;		/* active children sorted by cl_f */
 	struct rb_node cf_node;		/* parent's cf_heap member */
-	struct list_head hlist;		/* hash list member */
 	struct list_head dlist;		/* drop list member */
 
 	u64	cl_total;		/* total work in bytes */
@@ -177,13 +176,11 @@ struct hfsc_class
 	unsigned long	cl_nactive;	/* number of active children */
 };
 
-#define HFSC_HSIZE	16
-
 struct hfsc_sched
 {
 	u16	defcls;				/* default class id */
 	struct hfsc_class root;			/* root class */
-	struct list_head clhash[HFSC_HSIZE];	/* class hash */
+	struct Qdisc_class_hash clhash;		/* class hash */
 	struct rb_root eligible;		/* eligible tree */
 	struct list_head droplist;		/* active leaf class list (for
 						   dropping) */
@@ -933,26 +930,16 @@ hfsc_adjust_levels(struct hfsc_class *cl)
 	} while ((cl = cl->cl_parent) != NULL);
 }
 
-static inline unsigned int
-hfsc_hash(u32 h)
-{
-	h ^= h >> 8;
-	h ^= h >> 4;
-
-	return h & (HFSC_HSIZE - 1);
-}
-
 static inline struct hfsc_class *
 hfsc_find_class(u32 classid, struct Qdisc *sch)
 {
 	struct hfsc_sched *q = qdisc_priv(sch);
-	struct hfsc_class *cl;
+	struct Qdisc_class_common *clc;
 
-	list_for_each_entry(cl, &q->clhash[hfsc_hash(classid)], hlist) {
-		if (cl->classid == classid)
-			return cl;
-	}
-	return NULL;
+	clc = qdisc_class_find(&q->clhash, classid);
+	if (clc == NULL)
+		return NULL;
+	return container_of(clc, struct hfsc_class, cl_common);
 }
 
 static void
@@ -1032,7 +1019,8 @@ hfsc_change_class(struct Qdisc *sch, u32 classid, u32 parentid,
 
 	if (cl != NULL) {
 		if (parentid) {
-			if (cl->cl_parent && cl->cl_parent->classid != parentid)
+			if (cl->cl_parent &&
+			    cl->cl_parent->cl_common.classid != parentid)
 				return -EINVAL;
 			if (cl->cl_parent == NULL && parentid != TC_H_ROOT)
 				return -EINVAL;
@@ -1091,8 +1079,8 @@ hfsc_change_class(struct Qdisc *sch, u32 classid, u32 parentid,
 	if (usc != NULL)
 		hfsc_change_usc(cl, usc, 0);
 
+	cl->cl_common.classid = classid;
 	cl->refcnt    = 1;
-	cl->classid   = classid;
 	cl->sched     = q;
 	cl->cl_parent = parent;
 	cl->qdisc = qdisc_create_dflt(sch->dev, &pfifo_qdisc_ops, classid);
@@ -1103,7 +1091,7 @@ hfsc_change_class(struct Qdisc *sch, u32 classid, u32 parentid,
 	cl->cf_tree = RB_ROOT;
 
 	sch_tree_lock(sch);
-	list_add_tail(&cl->hlist, &q->clhash[hfsc_hash(classid)]);
+	qdisc_class_hash_insert(&q->clhash, &cl->cl_common);
 	list_add_tail(&cl->siblings, &parent->children);
 	if (parent->level == 0)
 		hfsc_purge_queue(sch, parent);
@@ -1111,6 +1099,8 @@ hfsc_change_class(struct Qdisc *sch, u32 classid, u32 parentid,
 	cl->cl_pcvtoff = parent->cl_cvtoff;
 	sch_tree_unlock(sch);
 
+	qdisc_class_hash_grow(sch, &q->clhash);
+
 	if (tca[TCA_RATE])
 		gen_new_estimator(&cl->bstats, &cl->rate_est,
 				  &sch->dev->queue_lock, tca[TCA_RATE]);
@@ -1145,7 +1135,7 @@ hfsc_delete_class(struct Qdisc *sch, unsigned long arg)
 	hfsc_adjust_levels(cl->cl_parent);
 
 	hfsc_purge_queue(sch, cl);
-	list_del(&cl->hlist);
+	qdisc_class_hash_remove(&q->clhash, &cl->cl_common);
 
 	if (--cl->refcnt == 0)
 		hfsc_destroy_class(sch, cl);
@@ -1212,7 +1202,7 @@ hfsc_graft_class(struct Qdisc *sch, unsigned long arg, struct Qdisc *new,
 		return -EINVAL;
 	if (new == NULL) {
 		new = qdisc_create_dflt(sch->dev, &pfifo_qdisc_ops,
-					cl->classid);
+					cl->cl_common.classid);
 		if (new == NULL)
 			new = &noop_qdisc;
 	}
@@ -1345,8 +1335,9 @@ hfsc_dump_class(struct Qdisc *sch, unsigned long arg, struct sk_buff *skb,
 	struct hfsc_class *cl = (struct hfsc_class *)arg;
 	struct nlattr *nest;
 
-	tcm->tcm_parent = cl->cl_parent ? cl->cl_parent->classid : TC_H_ROOT;
-	tcm->tcm_handle = cl->classid;
+	tcm->tcm_parent = cl->cl_parent ? cl->cl_parent->cl_common.classid :
+					  TC_H_ROOT;
+	tcm->tcm_handle = cl->cl_common.classid;
 	if (cl->level == 0)
 		tcm->tcm_info = cl->qdisc->handle;
 
@@ -1390,14 +1381,16 @@ static void
 hfsc_walk(struct Qdisc *sch, struct qdisc_walker *arg)
 {
 	struct hfsc_sched *q = qdisc_priv(sch);
+	struct hlist_node *n;
 	struct hfsc_class *cl;
 	unsigned int i;
 
 	if (arg->stop)
 		return;
 
-	for (i = 0; i < HFSC_HSIZE; i++) {
-		list_for_each_entry(cl, &q->clhash[i], hlist) {
+	for (i = 0; i < q->clhash.hashsize; i++) {
+		hlist_for_each_entry(cl, n, &q->clhash.hash[i],
+				     cl_common.hnode) {
 			if (arg->count < arg->skip) {
 				arg->count++;
 				continue;
@@ -1433,21 +1426,22 @@ hfsc_init_qdisc(struct Qdisc *sch, struct nlattr *opt)
 {
 	struct hfsc_sched *q = qdisc_priv(sch);
 	struct tc_hfsc_qopt *qopt;
-	unsigned int i;
+	int err;
 
 	if (opt == NULL || nla_len(opt) < sizeof(*qopt))
 		return -EINVAL;
 	qopt = nla_data(opt);
 
 	q->defcls = qopt->defcls;
-	for (i = 0; i < HFSC_HSIZE; i++)
-		INIT_LIST_HEAD(&q->clhash[i]);
+	err = qdisc_class_hash_init(&q->clhash);
+	if (err < 0)
+		return err;
 	q->eligible = RB_ROOT;
 	INIT_LIST_HEAD(&q->droplist);
 	skb_queue_head_init(&q->requeue);
 
+	q->root.cl_common.classid = sch->handle;
 	q->root.refcnt  = 1;
-	q->root.classid = sch->handle;
 	q->root.sched   = q;
 	q->root.qdisc = qdisc_create_dflt(sch->dev, &pfifo_qdisc_ops,
 					  sch->handle);
@@ -1457,7 +1451,8 @@ hfsc_init_qdisc(struct Qdisc *sch, struct nlattr *opt)
 	q->root.vt_tree = RB_ROOT;
 	q->root.cf_tree = RB_ROOT;
 
-	list_add(&q->root.hlist, &q->clhash[hfsc_hash(q->root.classid)]);
+	qdisc_class_hash_insert(&q->clhash, &q->root.cl_common);
+	qdisc_class_hash_grow(sch, &q->clhash);
 
 	qdisc_watchdog_init(&q->watchdog, sch);
 
@@ -1520,10 +1515,11 @@ hfsc_reset_qdisc(struct Qdisc *sch)
 {
 	struct hfsc_sched *q = qdisc_priv(sch);
 	struct hfsc_class *cl;
+	struct hlist_node *n;
 	unsigned int i;
 
-	for (i = 0; i < HFSC_HSIZE; i++) {
-		list_for_each_entry(cl, &q->clhash[i], hlist)
+	for (i = 0; i < q->clhash.hashsize; i++) {
+		hlist_for_each_entry(cl, n, &q->clhash.hash[i], cl_common.hnode)
 			hfsc_reset_class(cl);
 	}
 	__skb_queue_purge(&q->requeue);
@@ -1537,17 +1533,20 @@ static void
 hfsc_destroy_qdisc(struct Qdisc *sch)
 {
 	struct hfsc_sched *q = qdisc_priv(sch);
-	struct hfsc_class *cl, *next;
+	struct hlist_node *n, *next;
+	struct hfsc_class *cl;
 	unsigned int i;
 
-	for (i = 0; i < HFSC_HSIZE; i++) {
-		list_for_each_entry(cl, &q->clhash[i], hlist)
+	for (i = 0; i < q->clhash.hashsize; i++) {
+		hlist_for_each_entry(cl, n, &q->clhash.hash[i], cl_common.hnode)
 			tcf_destroy_chain(&cl->filter_list);
 	}
-	for (i = 0; i < HFSC_HSIZE; i++) {
-		list_for_each_entry_safe(cl, next, &q->clhash[i], hlist)
+	for (i = 0; i < q->clhash.hashsize; i++) {
+		hlist_for_each_entry_safe(cl, n, next, &q->clhash.hash[i],
+					  cl_common.hnode)
 			hfsc_destroy_class(sch, cl);
 	}
+	qdisc_class_hash_destroy(&q->clhash);
 	__skb_queue_purge(&q->requeue);
 	qdisc_watchdog_cancel(&q->watchdog);
 }

net-sched 03/06: sch_cbq: use dynamic class hash helpers

[Patrick McHardy]

net-sched: sch_cbq: use dynamic class hash helpers

Signed-off-by: Patrick McHardy <kaber@trash.net>

---
commit 7ce0dc13a43a80bcce1dc862f35fddc9740aaf27
tree c7a1b94865e509d6ea36fbdc915b120fafc853d7
parent d0d016e7dea2408ca6f795fe987f6abae3e5f526
author Patrick McHardy <kaber@trash.net> Thu, 03 Jul 2008 16:58:46 +0200
committer Patrick McHardy <kaber@trash.net> Thu, 03 Jul 2008 16:58:46 +0200

 net/sched/sch_cbq.c |  112 +++++++++++++++++++++++++--------------------------
 1 files changed, 55 insertions(+), 57 deletions(-)

diff --git a/net/sched/sch_cbq.c b/net/sched/sch_cbq.c
index 2a3c97f..968b4c7 100644
--- a/net/sched/sch_cbq.c
+++ b/net/sched/sch_cbq.c
@@ -73,11 +73,10 @@ struct cbq_sched_data;
 
 struct cbq_class
 {
-	struct cbq_class	*next;		/* hash table link */
+	struct Qdisc_class_common common;
 	struct cbq_class	*next_alive;	/* next class with backlog in this priority band */
 
 /* Parameters */
-	u32			classid;
 	unsigned char		priority;	/* class priority */
 	unsigned char		priority2;	/* priority to be used after overlimit */
 	unsigned char		ewma_log;	/* time constant for idle time calculation */
@@ -144,7 +143,7 @@ struct cbq_class
 
 struct cbq_sched_data
 {
-	struct cbq_class	*classes[16];		/* Hash table of all classes */
+	struct Qdisc_class_hash	clhash;			/* Hash table of all classes */
 	int			nclasses[TC_CBQ_MAXPRIO+1];
 	unsigned		quanta[TC_CBQ_MAXPRIO+1];
 
@@ -177,23 +176,15 @@ struct cbq_sched_data
 
 #define L2T(cl,len)	qdisc_l2t((cl)->R_tab,len)
 
-
-static __inline__ unsigned cbq_hash(u32 h)
-{
-	h ^= h>>8;
-	h ^= h>>4;
-	return h&0xF;
-}
-
 static __inline__ struct cbq_class *
 cbq_class_lookup(struct cbq_sched_data *q, u32 classid)
 {
-	struct cbq_class *cl;
+	struct Qdisc_class_common *clc;
 
-	for (cl = q->classes[cbq_hash(classid)]; cl; cl = cl->next)
-		if (cl->classid == classid)
-			return cl;
-	return NULL;
+	clc = qdisc_class_find(&q->clhash, classid);
+	if (clc == NULL)
+		return NULL;
+	return container_of(clc, struct cbq_class, common);
 }
 
 #ifdef CONFIG_NET_CLS_ACT
@@ -1071,13 +1062,14 @@ static void cbq_adjust_levels(struct cbq_class *this)
 static void cbq_normalize_quanta(struct cbq_sched_data *q, int prio)
 {
 	struct cbq_class *cl;
-	unsigned h;
+	struct hlist_node *n;
+	unsigned int h;
 
 	if (q->quanta[prio] == 0)
 		return;
 
-	for (h=0; h<16; h++) {
-		for (cl = q->classes[h]; cl; cl = cl->next) {
+	for (h = 0; h < q->clhash.hashsize; h++) {
+		hlist_for_each_entry(cl, n, &q->clhash.hash[h], common.hnode) {
 			/* BUGGGG... Beware! This expression suffer of
 			   arithmetic overflows!
 			 */
@@ -1086,7 +1078,7 @@ static void cbq_normalize_quanta(struct cbq_sched_data *q, int prio)
 					q->quanta[prio];
 			}
 			if (cl->quantum <= 0 || cl->quantum>32*cl->qdisc->dev->mtu) {
-				printk(KERN_WARNING "CBQ: class %08x has bad quantum==%ld, repaired.\n", cl->classid, cl->quantum);
+				printk(KERN_WARNING "CBQ: class %08x has bad quantum==%ld, repaired.\n", cl->common.classid, cl->quantum);
 				cl->quantum = cl->qdisc->dev->mtu/2 + 1;
 			}
 		}
@@ -1114,10 +1106,12 @@ static void cbq_sync_defmap(struct cbq_class *cl)
 		if (split->defaults[i])
 			continue;
 
-		for (h=0; h<16; h++) {
+		for (h = 0; h < q->clhash.hashsize; h++) {
+			struct hlist_node *n;
 			struct cbq_class *c;
 
-			for (c = q->classes[h]; c; c = c->next) {
+			hlist_for_each_entry(c, n, &q->clhash.hash[h],
+					     common.hnode) {
 				if (c->split == split && c->level < level &&
 				    c->defmap&(1<<i)) {
 					split->defaults[i] = c;
@@ -1135,12 +1129,12 @@ static void cbq_change_defmap(struct cbq_class *cl, u32 splitid, u32 def, u32 ma
 	if (splitid == 0) {
 		if ((split = cl->split) == NULL)
 			return;
-		splitid = split->classid;
+		splitid = split->common.classid;
 	}
 
-	if (split == NULL || split->classid != splitid) {
+	if (split == NULL || split->common.classid != splitid) {
 		for (split = cl->tparent; split; split = split->tparent)
-			if (split->classid == splitid)
+			if (split->common.classid == splitid)
 				break;
 	}
 
@@ -1163,13 +1157,7 @@ static void cbq_unlink_class(struct cbq_class *this)
 	struct cbq_class *cl, **clp;
 	struct cbq_sched_data *q = qdisc_priv(this->qdisc);
 
-	for (clp = &q->classes[cbq_hash(this->classid)]; (cl = *clp) != NULL; clp = &cl->next) {
-		if (cl == this) {
-			*clp = cl->next;
-			cl->next = NULL;
-			break;
-		}
-	}
+	qdisc_class_hash_remove(&q->clhash, &this->common);
 
 	if (this->tparent) {
 		clp=&this->sibling;
@@ -1195,12 +1183,10 @@ static void cbq_unlink_class(struct cbq_class *this)
 static void cbq_link_class(struct cbq_class *this)
 {
 	struct cbq_sched_data *q = qdisc_priv(this->qdisc);
-	unsigned h = cbq_hash(this->classid);
 	struct cbq_class *parent = this->tparent;
 
 	this->sibling = this;
-	this->next = q->classes[h];
-	q->classes[h] = this;
+	qdisc_class_hash_insert(&q->clhash, &this->common);
 
 	if (parent == NULL)
 		return;
@@ -1242,6 +1228,7 @@ cbq_reset(struct Qdisc* sch)
 {
 	struct cbq_sched_data *q = qdisc_priv(sch);
 	struct cbq_class *cl;
+	struct hlist_node *n;
 	int prio;
 	unsigned h;
 
@@ -1258,8 +1245,8 @@ cbq_reset(struct Qdisc* sch)
 	for (prio = 0; prio <= TC_CBQ_MAXPRIO; prio++)
 		q->active[prio] = NULL;
 
-	for (h = 0; h < 16; h++) {
-		for (cl = q->classes[h]; cl; cl = cl->next) {
+	for (h = 0; h < q->clhash.hashsize; h++) {
+		hlist_for_each_entry(cl, n, &q->clhash.hash[h], common.hnode) {
 			qdisc_reset(cl->q);
 
 			cl->next_alive = NULL;
@@ -1406,9 +1393,13 @@ static int cbq_init(struct Qdisc *sch, struct nlattr *opt)
 	if ((q->link.R_tab = qdisc_get_rtab(r, tb[TCA_CBQ_RTAB])) == NULL)
 		return -EINVAL;
 
+	err = qdisc_class_hash_init(&q->clhash);
+	if (err < 0)
+		goto put_rtab;
+
 	q->link.refcnt = 1;
 	q->link.sibling = &q->link;
-	q->link.classid = sch->handle;
+	q->link.common.classid = sch->handle;
 	q->link.qdisc = sch;
 	if (!(q->link.q = qdisc_create_dflt(sch->dev, &pfifo_qdisc_ops,
 					    sch->handle)))
@@ -1441,6 +1432,10 @@ static int cbq_init(struct Qdisc *sch, struct nlattr *opt)
 
 	cbq_addprio(q, &q->link);
 	return 0;
+
+put_rtab:
+	qdisc_put_rtab(q->link.R_tab);
+	return err;
 }
 
 static __inline__ int cbq_dump_rate(struct sk_buff *skb, struct cbq_class *cl)
@@ -1521,7 +1516,7 @@ static __inline__ int cbq_dump_fopt(struct sk_buff *skb, struct cbq_class *cl)
 	struct tc_cbq_fopt opt;
 
 	if (cl->split || cl->defmap) {
-		opt.split = cl->split ? cl->split->classid : 0;
+		opt.split = cl->split ? cl->split->common.classid : 0;
 		opt.defmap = cl->defmap;
 		opt.defchange = ~0;
 		NLA_PUT(skb, TCA_CBQ_FOPT, sizeof(opt), &opt);
@@ -1602,10 +1597,10 @@ cbq_dump_class(struct Qdisc *sch, unsigned long arg,
 	struct nlattr *nest;
 
 	if (cl->tparent)
-		tcm->tcm_parent = cl->tparent->classid;
+		tcm->tcm_parent = cl->tparent->common.classid;
 	else
 		tcm->tcm_parent = TC_H_ROOT;
-	tcm->tcm_handle = cl->classid;
+	tcm->tcm_handle = cl->common.classid;
 	tcm->tcm_info = cl->q->handle;
 
 	nest = nla_nest_start(skb, TCA_OPTIONS);
@@ -1650,8 +1645,9 @@ static int cbq_graft(struct Qdisc *sch, unsigned long arg, struct Qdisc *new,
 
 	if (cl) {
 		if (new == NULL) {
-			if ((new = qdisc_create_dflt(sch->dev, &pfifo_qdisc_ops,
-						     cl->classid)) == NULL)
+			new = qdisc_create_dflt(sch->dev, &pfifo_qdisc_ops,
+						cl->common.classid);
+			if (new == NULL)
 				return -ENOBUFS;
 		} else {
 #ifdef CONFIG_NET_CLS_ACT
@@ -1716,6 +1712,7 @@ static void
 cbq_destroy(struct Qdisc* sch)
 {
 	struct cbq_sched_data *q = qdisc_priv(sch);
+	struct hlist_node *n, *next;
 	struct cbq_class *cl;
 	unsigned h;
 
@@ -1727,18 +1724,16 @@ cbq_destroy(struct Qdisc* sch)
 	 * classes from root to leafs which means that filters can still
 	 * be bound to classes which have been destroyed already. --TGR '04
 	 */
-	for (h = 0; h < 16; h++) {
-		for (cl = q->classes[h]; cl; cl = cl->next)
+	for (h = 0; h < q->clhash.hashsize; h++) {
+		hlist_for_each_entry(cl, n, &q->clhash.hash[h], common.hnode)
 			tcf_destroy_chain(&cl->filter_list);
 	}
-	for (h = 0; h < 16; h++) {
-		struct cbq_class *next;
-
-		for (cl = q->classes[h]; cl; cl = next) {
-			next = cl->next;
+	for (h = 0; h < q->clhash.hashsize; h++) {
+		hlist_for_each_entry_safe(cl, n, next, &q->clhash.hash[h],
+					  common.hnode)
 			cbq_destroy_class(sch, cl);
-		}
 	}
+	qdisc_class_hash_destroy(&q->clhash);
 }
 
 static void cbq_put(struct Qdisc *sch, unsigned long arg)
@@ -1781,7 +1776,8 @@ cbq_change_class(struct Qdisc *sch, u32 classid, u32 parentid, struct nlattr **t
 	if (cl) {
 		/* Check parent */
 		if (parentid) {
-			if (cl->tparent && cl->tparent->classid != parentid)
+			if (cl->tparent &&
+			    cl->tparent->common.classid != parentid)
 				return -EINVAL;
 			if (!cl->tparent && parentid != TC_H_ROOT)
 				return -EINVAL;
@@ -1883,7 +1879,7 @@ cbq_change_class(struct Qdisc *sch, u32 classid, u32 parentid, struct nlattr **t
 	cl->refcnt = 1;
 	if (!(cl->q = qdisc_create_dflt(sch->dev, &pfifo_qdisc_ops, classid)))
 		cl->q = &noop_qdisc;
-	cl->classid = classid;
+	cl->common.classid = classid;
 	cl->tparent = parent;
 	cl->qdisc = sch;
 	cl->allot = parent->allot;
@@ -1916,6 +1912,8 @@ cbq_change_class(struct Qdisc *sch, u32 classid, u32 parentid, struct nlattr **t
 		cbq_set_fopt(cl, nla_data(tb[TCA_CBQ_FOPT]));
 	sch_tree_unlock(sch);
 
+	qdisc_class_hash_grow(sch, &q->clhash);
+
 	if (tca[TCA_RATE])
 		gen_new_estimator(&cl->bstats, &cl->rate_est,
 				  &sch->dev->queue_lock, tca[TCA_RATE]);
@@ -2008,15 +2006,15 @@ static void cbq_unbind_filter(struct Qdisc *sch, unsigned long arg)
 static void cbq_walk(struct Qdisc *sch, struct qdisc_walker *arg)
 {
 	struct cbq_sched_data *q = qdisc_priv(sch);
+	struct cbq_class *cl;
+	struct hlist_node *n;
 	unsigned h;
 
 	if (arg->stop)
 		return;
 
-	for (h = 0; h < 16; h++) {
-		struct cbq_class *cl;
-
-		for (cl = q->classes[h]; cl; cl = cl->next) {
+	for (h = 0; h < q->clhash.hashsize; h++) {
+		hlist_for_each_entry(cl, n, &q->clhash.hash[h], common.hnode) {
 			if (arg->count < arg->skip) {
 				arg->count++;
 				continue;

net-sched 04/06: sch_htb: move hash and sibling list removal to htb_delete

[Patrick McHardy]

net-sched: sch_htb: move hash and sibling list removal to htb_delete

Hash list removal currently happens twice (once in htb_delete, once
in htb_destroy_class), which makes it harder to use the dynamically
sized class hash without adding special cases for HTB. The reason is
that qdisc destruction destroys classes in hierarchical order, which
is not necessary if filters are destroyed in a separate iteration
during qdisc destruction.

Adjust qdisc destruction to follow the same scheme as other hierarchical
qdiscs by first performing a filter destruction pass, then destroying
all classes in hash order.

Signed-off-by: Patrick McHardy <kaber@trash.net>

---
commit 3fcfd66ab1737d4bcb2158866d7b2b574b0099bf
tree 9146a96a6353464ef6a42706ad5bc4a7c8ce92d2
parent 7ce0dc13a43a80bcce1dc862f35fddc9740aaf27
author Patrick McHardy <kaber@trash.net> Thu, 03 Jul 2008 16:58:46 +0200
committer Patrick McHardy <kaber@trash.net> Thu, 03 Jul 2008 16:58:46 +0200

 net/sched/sch_htb.c |   40 +++++++++++++++++-----------------------
 1 files changed, 17 insertions(+), 23 deletions(-)

diff --git a/net/sched/sch_htb.c b/net/sched/sch_htb.c
index 0284791..d01fe3a 100644
--- a/net/sched/sch_htb.c
+++ b/net/sched/sch_htb.c
@@ -1226,8 +1226,6 @@ static void htb_parent_to_leaf(struct htb_sched *q, struct htb_class *cl,
 
 static void htb_destroy_class(struct Qdisc *sch, struct htb_class *cl)
 {
-	struct htb_sched *q = qdisc_priv(sch);
-
 	if (!cl->level) {
 		BUG_TRAP(cl->un.leaf.q);
 		qdisc_destroy(cl->un.leaf.q);
@@ -1237,21 +1235,6 @@ static void htb_destroy_class(struct Qdisc *sch, struct htb_class *cl)
 	qdisc_put_rtab(cl->ceil);
 
 	tcf_destroy_chain(&cl->filter_list);
-
-	while (!list_empty(&cl->children))
-		htb_destroy_class(sch, list_entry(cl->children.next,
-						  struct htb_class, sibling));
-
-	/* note: this delete may happen twice (see htb_delete) */
-	hlist_del_init(&cl->hlist);
-	list_del(&cl->sibling);
-
-	if (cl->prio_activity)
-		htb_deactivate(q, cl);
-
-	if (cl->cmode != HTB_CAN_SEND)
-		htb_safe_rb_erase(&cl->pq_node, q->wait_pq + cl->level);
-
 	kfree(cl);
 }
 
@@ -1259,6 +1242,9 @@ static void htb_destroy_class(struct Qdisc *sch, struct htb_class *cl)
 static void htb_destroy(struct Qdisc *sch)
 {
 	struct htb_sched *q = qdisc_priv(sch);
+	struct hlist_node *n, *next;
+	struct htb_class *cl;
+	unsigned int i;
 
 	qdisc_watchdog_cancel(&q->watchdog);
 	/* This line used to be after htb_destroy_class call below
@@ -1267,10 +1253,14 @@ static void htb_destroy(struct Qdisc *sch)
 	   unbind_filter on it (without Oops). */
 	tcf_destroy_chain(&q->filter_list);
 
-	while (!list_empty(&q->root))
-		htb_destroy_class(sch, list_entry(q->root.next,
-						  struct htb_class, sibling));
-
+	for (i = 0; i < HTB_HSIZE; i++) {
+		hlist_for_each_entry(cl, n, q->hash + i, hlist)
+			tcf_destroy_chain(&cl->filter_list);
+	}
+	for (i = 0; i < HTB_HSIZE; i++) {
+		hlist_for_each_entry_safe(cl, n, next, q->hash + i, hlist)
+			htb_destroy_class(sch, cl);
+	}
 	__skb_queue_purge(&q->direct_queue);
 }
 
@@ -1302,12 +1292,16 @@ static int htb_delete(struct Qdisc *sch, unsigned long arg)
 		qdisc_tree_decrease_qlen(cl->un.leaf.q, qlen);
 	}
 
-	/* delete from hash and active; remainder in destroy_class */
-	hlist_del_init(&cl->hlist);
+	/* delete from hash, sibling list and active */
+	hlist_del(&cl->hlist);
+	list_del(&cl->sibling);
 
 	if (cl->prio_activity)
 		htb_deactivate(q, cl);
 
+	if (cl->cmode != HTB_CAN_SEND)
+		htb_safe_rb_erase(&cl->pq_node, q->wait_pq + cl->level);
+
 	if (last_child)
 		htb_parent_to_leaf(q, cl, new_q);
 

net-sched 05/06: sch_htb: use dynamic class hash helpers

[Patrick McHardy]

net-sched: sch_htb: use dynamic class hash helpers

Signed-off-by: Patrick McHardy <kaber@trash.net>

---
commit e56e921c9ece0bd6f4201910292468f9c0e8f4de
tree e231093d86d28b8bff2549cbebaa185b16248c2c
parent 3fcfd66ab1737d4bcb2158866d7b2b574b0099bf
author Patrick McHardy <kaber@trash.net> Thu, 03 Jul 2008 16:58:47 +0200
committer Patrick McHardy <kaber@trash.net> Thu, 03 Jul 2008 16:58:47 +0200

 net/sched/sch_htb.c |  100 +++++++++++++++++++++------------------------------
 1 files changed, 42 insertions(+), 58 deletions(-)

diff --git a/net/sched/sch_htb.c b/net/sched/sch_htb.c
index d01fe3a..e7461a1 100644
--- a/net/sched/sch_htb.c
+++ b/net/sched/sch_htb.c
@@ -51,7 +51,6 @@
     one less than their parent.
 */
 
-#define HTB_HSIZE 16		/* classid hash size */
 static int htb_hysteresis __read_mostly = 0; /* whether to use mode hysteresis for speedup */
 #define HTB_VER 0x30011		/* major must be matched with number suplied by TC as version */
 
@@ -72,8 +71,8 @@ enum htb_cmode {
 
 /* interior & leaf nodes; props specific to leaves are marked L: */
 struct htb_class {
+	struct Qdisc_class_common common;
 	/* general class parameters */
-	u32 classid;
 	struct gnet_stats_basic bstats;
 	struct gnet_stats_queue qstats;
 	struct gnet_stats_rate_est rate_est;
@@ -83,7 +82,6 @@ struct htb_class {
 	/* topology */
 	int level;		/* our level (see above) */
 	struct htb_class *parent;	/* parent class */
-	struct hlist_node hlist;	/* classid hash list item */
 	struct list_head sibling;	/* sibling list item */
 	struct list_head children;	/* children list */
 
@@ -141,7 +139,7 @@ static inline long L2T(struct htb_class *cl, struct qdisc_rate_table *rate,
 
 struct htb_sched {
 	struct list_head root;	/* root classes list */
-	struct hlist_head hash[HTB_HSIZE];	/* hashed by classid */
+	struct Qdisc_class_hash clhash;
 	struct list_head drops[TC_HTB_NUMPRIO];/* active leaves (for drops) */
 
 	/* self list - roots of self generating tree */
@@ -176,32 +174,16 @@ struct htb_sched {
 	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 */
 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;
+	struct Qdisc_class_common *clc;
 
-	if (TC_H_MAJ(handle) != sch->handle)
+	clc = qdisc_class_find(&q->clhash, handle);
+	if (clc == NULL)
 		return NULL;
-
-	hlist_for_each_entry(cl, p, q->hash + htb_hash(handle), hlist) {
-		if (cl->classid == handle)
-			return cl;
-	}
-	return NULL;
+	return container_of(clc, struct htb_class, common);
 }
 
 /**
@@ -282,7 +264,7 @@ static void htb_add_to_id_tree(struct rb_root *root,
 		parent = *p;
 		c = rb_entry(parent, struct htb_class, node[prio]);
 
-		if (cl->classid > c->classid)
+		if (cl->common.classid > c->common.classid)
 			p = &parent->rb_right;
 		else
 			p = &parent->rb_left;
@@ -446,7 +428,7 @@ static void htb_deactivate_prios(struct htb_sched *q, struct htb_class *cl)
 				/* we are removing child which is pointed to from
 				   parent feed - forget the pointer but remember
 				   classid */
-				p->un.inner.last_ptr_id[prio] = cl->classid;
+				p->un.inner.last_ptr_id[prio] = cl->common.classid;
 				p->un.inner.ptr[prio] = NULL;
 			}
 
@@ -751,10 +733,10 @@ static struct rb_node *htb_id_find_next_upper(int prio, struct rb_node *n,
 	while (n) {
 		struct htb_class *cl =
 		    rb_entry(n, struct htb_class, node[prio]);
-		if (id == cl->classid)
+		if (id == cl->common.classid)
 			return n;
 
-		if (id > cl->classid) {
+		if (id > cl->common.classid) {
 			n = n->rb_right;
 		} else {
 			r = n;
@@ -864,7 +846,7 @@ next:
 		if (!cl->warned) {
 			printk(KERN_WARNING
 			       "htb: class %X isn't work conserving ?!\n",
-			       cl->classid);
+			       cl->common.classid);
 			cl->warned = 1;
 		}
 		q->nwc_hit++;
@@ -975,13 +957,12 @@ static unsigned int htb_drop(struct Qdisc *sch)
 static void htb_reset(struct Qdisc *sch)
 {
 	struct htb_sched *q = qdisc_priv(sch);
-	int i;
-
-	for (i = 0; i < HTB_HSIZE; i++) {
-		struct hlist_node *p;
-		struct htb_class *cl;
+	struct htb_class *cl;
+	struct hlist_node *n;
+	unsigned int i;
 
-		hlist_for_each_entry(cl, p, q->hash + i, hlist) {
+	for (i = 0; i < q->clhash.hashsize; i++) {
+		hlist_for_each_entry(cl, n, &q->clhash.hash[i], common.hnode) {
 			if (cl->level)
 				memset(&cl->un.inner, 0, sizeof(cl->un.inner));
 			else {
@@ -1040,8 +1021,9 @@ static int htb_init(struct Qdisc *sch, struct nlattr *opt)
 	}
 
 	INIT_LIST_HEAD(&q->root);
-	for (i = 0; i < HTB_HSIZE; i++)
-		INIT_HLIST_HEAD(q->hash + i);
+	err = qdisc_class_hash_init(&q->clhash);
+	if (err < 0)
+		return err;
 	for (i = 0; i < TC_HTB_NUMPRIO; i++)
 		INIT_LIST_HEAD(q->drops + i);
 
@@ -1096,8 +1078,8 @@ static int htb_dump_class(struct Qdisc *sch, unsigned long arg,
 	struct tc_htb_opt opt;
 
 	spin_lock_bh(&sch->dev->queue_lock);
-	tcm->tcm_parent = cl->parent ? cl->parent->classid : TC_H_ROOT;
-	tcm->tcm_handle = cl->classid;
+	tcm->tcm_parent = cl->parent ? cl->parent->common.classid : TC_H_ROOT;
+	tcm->tcm_handle = cl->common.classid;
 	if (!cl->level && cl->un.leaf.q)
 		tcm->tcm_info = cl->un.leaf.q->handle;
 
@@ -1152,7 +1134,7 @@ static int htb_graft(struct Qdisc *sch, unsigned long arg, struct Qdisc *new,
 	if (cl && !cl->level) {
 		if (new == NULL &&
 		    (new = qdisc_create_dflt(sch->dev, &pfifo_qdisc_ops,
-					     cl->classid))
+					     cl->common.classid))
 		    == NULL)
 			return -ENOBUFS;
 		sch_tree_lock(sch);
@@ -1253,14 +1235,16 @@ static void htb_destroy(struct Qdisc *sch)
 	   unbind_filter on it (without Oops). */
 	tcf_destroy_chain(&q->filter_list);
 
-	for (i = 0; i < HTB_HSIZE; i++) {
-		hlist_for_each_entry(cl, n, q->hash + i, hlist)
+	for (i = 0; i < q->clhash.hashsize; i++) {
+		hlist_for_each_entry(cl, n, &q->clhash.hash[i], common.hnode)
 			tcf_destroy_chain(&cl->filter_list);
 	}
-	for (i = 0; i < HTB_HSIZE; i++) {
-		hlist_for_each_entry_safe(cl, n, next, q->hash + i, hlist)
+	for (i = 0; i < q->clhash.hashsize; i++) {
+		hlist_for_each_entry_safe(cl, n, next, &q->clhash.hash[i],
+					  common.hnode)
 			htb_destroy_class(sch, cl);
 	}
+	qdisc_class_hash_destroy(&q->clhash);
 	__skb_queue_purge(&q->direct_queue);
 }
 
@@ -1280,7 +1264,7 @@ static int htb_delete(struct Qdisc *sch, unsigned long arg)
 
 	if (!cl->level && htb_parent_last_child(cl)) {
 		new_q = qdisc_create_dflt(sch->dev, &pfifo_qdisc_ops,
-						cl->parent->classid);
+						cl->parent->common.classid);
 		last_child = 1;
 	}
 
@@ -1292,8 +1276,8 @@ static int htb_delete(struct Qdisc *sch, unsigned long arg)
 		qdisc_tree_decrease_qlen(cl->un.leaf.q, qlen);
 	}
 
-	/* delete from hash, sibling list and active */
-	hlist_del(&cl->hlist);
+	/* delete from hash and active; remainder in destroy_class */
+	qdisc_class_hash_remove(&q->clhash, &cl->common);
 	list_del(&cl->sibling);
 
 	if (cl->prio_activity)
@@ -1390,7 +1374,6 @@ static int htb_change_class(struct Qdisc *sch, u32 classid,
 				  tca[TCA_RATE] ? : &est.nla);
 		cl->refcnt = 1;
 		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);
@@ -1425,7 +1408,7 @@ static int htb_change_class(struct Qdisc *sch, u32 classid,
 		/* leaf (we) needs elementary qdisc */
 		cl->un.leaf.q = new_q ? new_q : &noop_qdisc;
 
-		cl->classid = classid;
+		cl->common.classid = classid;
 		cl->parent = parent;
 
 		/* set class to be in HTB_CAN_SEND state */
@@ -1436,7 +1419,7 @@ static int htb_change_class(struct Qdisc *sch, u32 classid,
 		cl->cmode = HTB_CAN_SEND;
 
 		/* attach to the hash list and parent's family */
-		hlist_add_head(&cl->hlist, q->hash + htb_hash(classid));
+		qdisc_class_hash_insert(&q->clhash, &cl->common);
 		list_add_tail(&cl->sibling,
 			      parent ? &parent->children : &q->root);
 	} else {
@@ -1454,13 +1437,13 @@ static int htb_change_class(struct Qdisc *sch, u32 classid,
 		if (!hopt->quantum && cl->un.leaf.quantum < 1000) {
 			printk(KERN_WARNING
 			       "HTB: quantum of class %X is small. Consider r2q change.\n",
-			       cl->classid);
+			       cl->common.classid);
 			cl->un.leaf.quantum = 1000;
 		}
 		if (!hopt->quantum && cl->un.leaf.quantum > 200000) {
 			printk(KERN_WARNING
 			       "HTB: quantum of class %X is big. Consider r2q change.\n",
-			       cl->classid);
+			       cl->common.classid);
 			cl->un.leaf.quantum = 200000;
 		}
 		if (hopt->quantum)
@@ -1483,6 +1466,8 @@ static int htb_change_class(struct Qdisc *sch, u32 classid,
 	cl->ceil = ctab;
 	sch_tree_unlock(sch);
 
+	qdisc_class_hash_grow(sch, &q->clhash);
+
 	*arg = (unsigned long)cl;
 	return 0;
 
@@ -1539,16 +1524,15 @@ static void htb_unbind_filter(struct Qdisc *sch, unsigned long arg)
 static void htb_walk(struct Qdisc *sch, struct qdisc_walker *arg)
 {
 	struct htb_sched *q = qdisc_priv(sch);
-	int i;
+	struct htb_class *cl;
+	struct hlist_node *n;
+	unsigned int i;
 
 	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) {
+	for (i = 0; i < q->clhash.hashsize; i++) {
+		hlist_for_each_entry(cl, n, &q->clhash.hash[i], common.hnode) {
 			if (arg->count < arg->skip) {
 				arg->count++;
 				continue;

net-sched 06/06: sch_htb: remove child and sibling lists

[Patrick McHardy]

net-sched: sch_htb: remove child and sibling lists

Now that the qdisc isn't destroyed in hierarchical order anymore,
the only user of the child lists left is htb_parent_last_child().
This can be easily changed to use a counter of children to save
a few bytes.

Signed-off-by: Patrick McHardy <kaber@trash.net>

---
commit b65c685ee892935858c9c2ec6cce8d3ca3022b27
tree 119adf6a4c6755fffcf9def44c6e16a633535b5e
parent e56e921c9ece0bd6f4201910292468f9c0e8f4de
author Patrick McHardy <kaber@trash.net> Thu, 03 Jul 2008 16:58:47 +0200
committer Patrick McHardy <kaber@trash.net> Thu, 03 Jul 2008 16:58:47 +0200

 net/sched/sch_htb.c |   21 +++++++--------------
 1 files changed, 7 insertions(+), 14 deletions(-)

diff --git a/net/sched/sch_htb.c b/net/sched/sch_htb.c
index e7461a1..128a5ab 100644
--- a/net/sched/sch_htb.c
+++ b/net/sched/sch_htb.c
@@ -81,9 +81,8 @@ struct htb_class {
 
 	/* topology */
 	int level;		/* our level (see above) */
+	unsigned int children;
 	struct htb_class *parent;	/* parent class */
-	struct list_head sibling;	/* sibling list item */
-	struct list_head children;	/* children list */
 
 	union {
 		struct htb_class_leaf {
@@ -138,7 +137,6 @@ static inline long L2T(struct htb_class *cl, struct qdisc_rate_table *rate,
 }
 
 struct htb_sched {
-	struct list_head root;	/* root classes list */
 	struct Qdisc_class_hash clhash;
 	struct list_head drops[TC_HTB_NUMPRIO];/* active leaves (for drops) */
 
@@ -1020,7 +1018,6 @@ static int htb_init(struct Qdisc *sch, struct nlattr *opt)
 		return -EINVAL;
 	}
 
-	INIT_LIST_HEAD(&q->root);
 	err = qdisc_class_hash_init(&q->clhash);
 	if (err < 0)
 		return err;
@@ -1175,12 +1172,9 @@ static inline int htb_parent_last_child(struct htb_class *cl)
 	if (!cl->parent)
 		/* the root class */
 		return 0;
-
-	if (!(cl->parent->children.next == &cl->sibling &&
-		cl->parent->children.prev == &cl->sibling))
+	if (cl->parent->children > 1)
 		/* not the last child */
 		return 0;
-
 	return 1;
 }
 
@@ -1259,7 +1253,7 @@ static int htb_delete(struct Qdisc *sch, unsigned long arg)
 	// TODO: why don't allow to delete subtree ? references ? does
 	// tc subsys quarantee us that in htb_destroy it holds no class
 	// refs so that we can remove children safely there ?
-	if (!list_empty(&cl->children) || cl->filter_cnt)
+	if (cl->children || cl->filter_cnt)
 		return -EBUSY;
 
 	if (!cl->level && htb_parent_last_child(cl)) {
@@ -1278,7 +1272,7 @@ static int htb_delete(struct Qdisc *sch, unsigned long arg)
 
 	/* delete from hash and active; remainder in destroy_class */
 	qdisc_class_hash_remove(&q->clhash, &cl->common);
-	list_del(&cl->sibling);
+	cl->parent->children--;
 
 	if (cl->prio_activity)
 		htb_deactivate(q, cl);
@@ -1373,8 +1367,7 @@ static int htb_change_class(struct Qdisc *sch, u32 classid,
 				  &sch->dev->queue_lock,
 				  tca[TCA_RATE] ? : &est.nla);
 		cl->refcnt = 1;
-		INIT_LIST_HEAD(&cl->sibling);
-		INIT_LIST_HEAD(&cl->children);
+		cl->children = 0;
 		INIT_LIST_HEAD(&cl->un.leaf.drop_list);
 		RB_CLEAR_NODE(&cl->pq_node);
 
@@ -1420,8 +1413,8 @@ static int htb_change_class(struct Qdisc *sch, u32 classid,
 
 		/* attach to the hash list and parent's family */
 		qdisc_class_hash_insert(&q->clhash, &cl->common);
-		list_add_tail(&cl->sibling,
-			      parent ? &parent->children : &q->root);
+		if (parent)
+			parent->children++;
 	} else {
 		if (tca[TCA_RATE])
 			gen_replace_estimator(&cl->bstats, &cl->rate_est,

Re: net-sched 00/06: dynamically sized class hashes v2

[Patrick McHardy]

Jarek Poplawski wrote:
> On Thu, Jul 03, 2008 at 05:16:01PM +0200, Patrick McHardy wrote:
> ...
>   
>> The patches need the two filter destruction fixes that went into
>> net-2.6.git to apply cleanly, so they won't apply until net-2.6.git
>> is merged into net-next-2.6.git.
>>     
>
> Patrick, I just was about to write that some patches (1, 3, 5) give
> checkpatch warnings... (but no big deal).
>   

Yeah, for reference:

+struct Qdisc_class_common
+{

ERROR: open brace '{' following struct go on the same line

This is for consistency within the file.
---
WARNING: line over 80 characters
#68: FILE: include/net/sch_generic.h:207:
+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 *);

Header file, better grep output.
---
WARNING: line over 80 characters
#37: FILE: net/sched/sch_cbq.c:146:
+       struct Qdisc_class_hash clhash;                 /* Hash table of 
all classes */

Basically every line in that struct is over 80 characters
---
WARNING: line over 80 characters
#93: FILE: net/sched/sch_cbq.c:1081:
+                               printk(KERN_WARNING "CBQ: class %08x has 
bad quantum==%ld, repaired.\n", cl->common.classid, cl->quantum);

Already was longer .. I could have fixed this one though.
----
WARNING: line over 80 characters
#105: FILE: net/sched/sch_htb.c:431:
+                               p->un.inner.last_ptr_id[prio] = 
cl->common.classid;

One character overrun I think, but easier to read this way.
---
>
> I'll try to look at this later, but let's say: if I don't write
> means I'm OK with all these patches.
>
Thanks for the review so far.

> BTW: I wonder why cbq and htb have "common", while hfsc "cl_common"?

Consistency, HFSC uses cl_ as prefix for many (unfortunately
not all) class members.

Re: net-sched 00/06: dynamically sized class hashes v2

[Jarek Poplawski]

On Thu, Jul 03, 2008 at 05:16:01PM +0200, Patrick McHardy wrote:
...
> The patches need the two filter destruction fixes that went into
> net-2.6.git to apply cleanly, so they won't apply until net-2.6.git
> is merged into net-next-2.6.git.

Patrick, I just was about to write that some patches (1, 3, 5) give
checkpatch warnings... (but no big deal).

I'll try to look at this later, but let's say: if I don't write
means I'm OK with all these patches.

Thanks again,
Jarek P.

BTW: I wonder why cbq and htb have "common", while hfsc "cl_common"?

Re: net-sched 00/06: dynamically sized class hashes v2

[Jarek Poplawski]

On Thu, Jul 03, 2008 at 06:09:32PM +0200, Patrick McHardy wrote:
...
>> BTW: I wonder why cbq and htb have "common", while hfsc "cl_common"?
>
> Consistency, HFSC uses cl_ as prefix for many (unfortunately
> not all) class members.
>

BTW, BTW: I've just started to understand this "common" idea (I hope).
So if it's planned for some other (not searching) fields common for
classes, then of course, this name is quite sensible (maybe only a bit
too long for dereferencing).

Jarek P.

Re: net-sched 00/06: dynamically sized class hashes v2

[Patrick McHardy]

Jarek Poplawski wrote:
> BTW, BTW: I've just started to understand this "common" idea (I hope).
> So if it's planned for some other (not searching) fields common for
> classes, then of course, this name is quite sensible (maybe only a bit
> too long for dereferencing).
>   

Yes, child qdiscs, filter lists etc. would be a good start. I think we
should actually have at least two types of common structs, one for
hierarchical qdiscs, one for pseudo-classful like TBF, RED and netem.

I have some patches but they're a big mess so I seperated out the useful
stuff for now :)

net-sched 07/06: sch_htb: remove write-only qdisc filter_cnt

[Patrick McHardy]

[-- Attachment #1: Type: text/plain, Size: 0 bytes --]



[-- Attachment #2: 07.diff --]
[-- Type: text/x-diff, Size: 1726 bytes --]

commit 50ed378778be0c8d435163122827cf513882a707
Author: Patrick McHardy <kaber@trash.net>
Date:   Fri Jul 4 14:18:03 2008 +0200

    net-sched: sch_htb: remove write-only qdisc filter_cnt
    
    The filter_cnt is supposed to count filter references to a class.
    Since the qdisc can't be the target of a filter, it doesn't need
    a filter_cnt. In fact the counter is never decreased since cls_api
    considers a return value of zero a failure and doesn't unbind again.
    
    Signed-off-by: Patrick McHardy <kaber@trash.net>

diff --git a/net/sched/sch_htb.c b/net/sched/sch_htb.c
index 128a5ab..ee8b4ff 100644
--- a/net/sched/sch_htb.c
+++ b/net/sched/sch_htb.c
@@ -159,7 +159,6 @@ struct htb_sched {
 
 	/* filters for qdisc itself */
 	struct tcf_proto *filter_list;
-	int filter_cnt;
 
 	int rate2quantum;	/* quant = rate / rate2quantum */
 	psched_time_t now;	/* cached dequeue time */
@@ -1484,7 +1483,6 @@ static struct tcf_proto **htb_find_tcf(struct Qdisc *sch, unsigned long arg)
 static unsigned long htb_bind_filter(struct Qdisc *sch, unsigned long parent,
 				     u32 classid)
 {
-	struct htb_sched *q = qdisc_priv(sch);
 	struct htb_class *cl = htb_find(classid, sch);
 
 	/*if (cl && !cl->level) return 0;
@@ -1498,20 +1496,15 @@ static unsigned long htb_bind_filter(struct Qdisc *sch, unsigned long parent,
 	 */
 	if (cl)
 		cl->filter_cnt++;
-	else
-		q->filter_cnt++;
 	return (unsigned long)cl;
 }
 
 static void htb_unbind_filter(struct Qdisc *sch, unsigned long arg)
 {
-	struct htb_sched *q = qdisc_priv(sch);
 	struct htb_class *cl = (struct htb_class *)arg;
 
 	if (cl)
 		cl->filter_cnt--;
-	else
-		q->filter_cnt--;
 }
 
 static void htb_walk(struct Qdisc *sch, struct qdisc_walker *arg)

Re: net-sched 07/06: sch_htb: remove write-only qdisc filter_cnt

[Jarek Poplawski]

On Fri, Jul 04, 2008 at 02:20:03PM +0200, Patrick McHardy wrote:

> commit 50ed378778be0c8d435163122827cf513882a707
> Author: Patrick McHardy <kaber@trash.net>
> Date:   Fri Jul 4 14:18:03 2008 +0200
> 
>     net-sched: sch_htb: remove write-only qdisc filter_cnt
>     
>     The filter_cnt is supposed to count filter references to a class.
>     Since the qdisc can't be the target of a filter, it doesn't need
>     a filter_cnt. In fact the counter is never decreased since cls_api
>     considers a return value of zero a failure and doesn't unbind again.
>     
>     Signed-off-by: Patrick McHardy <kaber@trash.net>

...plus, of course, it's never checked. Good point and good patch (IMHO).

Regards,
Jarek P.

> 
> diff --git a/net/sched/sch_htb.c b/net/sched/sch_htb.c
> index 128a5ab..ee8b4ff 100644
> --- a/net/sched/sch_htb.c
> +++ b/net/sched/sch_htb.c
> @@ -159,7 +159,6 @@ struct htb_sched {
>  
>  	/* filters for qdisc itself */
>  	struct tcf_proto *filter_list;
> -	int filter_cnt;
>  
>  	int rate2quantum;	/* quant = rate / rate2quantum */
>  	psched_time_t now;	/* cached dequeue time */
> @@ -1484,7 +1483,6 @@ static struct tcf_proto **htb_find_tcf(struct Qdisc *sch, unsigned long arg)
>  static unsigned long htb_bind_filter(struct Qdisc *sch, unsigned long parent,
>  				     u32 classid)
>  {
> -	struct htb_sched *q = qdisc_priv(sch);
>  	struct htb_class *cl = htb_find(classid, sch);
>  
>  	/*if (cl && !cl->level) return 0;
> @@ -1498,20 +1496,15 @@ static unsigned long htb_bind_filter(struct Qdisc *sch, unsigned long parent,
>  	 */
>  	if (cl)
>  		cl->filter_cnt++;
> -	else
> -		q->filter_cnt++;
>  	return (unsigned long)cl;
>  }
>  
>  static void htb_unbind_filter(struct Qdisc *sch, unsigned long arg)
>  {
> -	struct htb_sched *q = qdisc_priv(sch);
>  	struct htb_class *cl = (struct htb_class *)arg;
>  
>  	if (cl)
>  		cl->filter_cnt--;
> -	else
> -		q->filter_cnt--;
>  }
>  
>  static void htb_walk(struct Qdisc *sch, struct qdisc_walker *arg)

Re: net-sched 00/06: dynamically sized class hashes v2

[David Miller]

From: Patrick McHardy <kaber@trash.net>
Date: Thu,  3 Jul 2008 17:16:01 +0200 (MEST)

> These patches add support for dynamically sized class hash tables
> to remove a major bottleneck in qdisc filters with many classes
> when filters are not bound to classes and convert CBQ, HTB and HFSC
> to use them.
> 
> Changes since the last posting are mostly suggestions from Martin
> Devera and Jarek Poplawski:
> 
> - fix missing qdisc hash initialization in CBQ
> - use classes directly in hlist iteration instead of Qdisc_class_common
> - change qdisc_class_find to return Qdisc_class_common * instead of void *
> - new patch to remove child and sibling lists from HTB
> - all patches are tested now and considered ready for merging :)
> 
> The patches need the two filter destruction fixes that went into
> net-2.6.git to apply cleanly, so they won't apply until net-2.6.git
> is merged into net-next-2.6.git.

I like it!

Applied and pushed out to net-next-2.6, thanks!

Re: net-sched 07/06: sch_htb: remove write-only qdisc filter_cnt

[David Miller]

From: Patrick McHardy <kaber@trash.net>
Date: Fri, 04 Jul 2008 14:20:03 +0200

>     net-sched: sch_htb: remove write-only qdisc filter_cnt
>     
>     The filter_cnt is supposed to count filter references to a class.
>     Since the qdisc can't be the target of a filter, it doesn't need
>     a filter_cnt. In fact the counter is never decreased since cls_api
>     considers a return value of zero a failure and doesn't unbind again.
>     
>     Signed-off-by: Patrick McHardy <kaber@trash.net>

Also applied, thanks Patrick.