[RFC]: net-sched 00/05: dynamically sized class hashes

[RFC]: net-sched 00/05: dynamically sized class hashes

[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.

Only RFC at this point because they haven't been tested thoroughly yet
and depend on the filter destruction fixes I sent this morning, but any
review (especially of 4/5, the htb_delete changes) is welcome.


 include/net/sch_generic.h |   41 +++++++++++++++
 net/sched/sch_api.c       |  104 ++++++++++++++++++++++++++++++++++++++
 net/sched/sch_cbq.c       |  114 +++++++++++++++++++++--------------------
 net/sched/sch_hfsc.c      |   90 ++++++++++++++++++---------------
 net/sched/sch_htb.c       |  123 +++++++++++++++++++++------------------------
 5 files changed, 310 insertions(+), 162 deletions(-)

Patrick McHardy (5):
      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 01/05: add dynamically sized qdisc class hash helpers

[Patrick McHardy]

net-sched: add dynamically sized qdisc class hash helpers

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

---
commit fe2579f858479ce266763ba861c87cd0371389af
tree fe574771047ca02df76c7ec07d70b9402278531a
parent 98cd24a4b3ac9ba234631803a05f96c3fddb500b
author Patrick McHardy <kaber@trash.net> Tue, 01 Jul 2008 14:02:55 +0200
committer Patrick McHardy <kaber@trash.net> Tue, 01 Jul 2008 14:02:55 +0200

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

diff --git a/include/net/sch_generic.h b/include/net/sch_generic.h
index a87fc03..0541d3c 100644
--- a/include/net/sch_generic.h
+++ b/include/net/sch_generic.h
@@ -167,6 +167,47 @@ 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 void *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/05: 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 894a1f0874e239e431ec524eb10782d577a0a6d3
tree 0ef83fbe4f09c1b4eab86cee111481ed33053de3
parent fe2579f858479ce266763ba861c87cd0371389af
author Patrick McHardy <kaber@trash.net> Tue, 01 Jul 2008 14:02:55 +0200
committer Patrick McHardy <kaber@trash.net> Tue, 01 Jul 2008 14:02:55 +0200

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

diff --git a/net/sched/sch_hfsc.c b/net/sched/sch_hfsc.c
index e817aa0..dc9bbe3 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,18 +1381,21 @@ static void
 hfsc_walk(struct Qdisc *sch, struct qdisc_walker *arg)
 {
 	struct hfsc_sched *q = qdisc_priv(sch);
+	struct Qdisc_class_common *clc;
+	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(clc, n, &q->clhash.hash[i], hnode) {
 			if (arg->count < arg->skip) {
 				arg->count++;
 				continue;
 			}
+			cl = container_of(clc, struct hfsc_class, cl_common);
 			if (arg->fn(sch, (unsigned long)cl, arg) < 0) {
 				arg->stop = 1;
 				return;
@@ -1433,21 +1427,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 +1452,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);
 
@@ -1519,12 +1515,16 @@ static void
 hfsc_reset_qdisc(struct Qdisc *sch)
 {
 	struct hfsc_sched *q = qdisc_priv(sch);
+	struct Qdisc_class_common *clc;
+	struct hlist_node *n;
 	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(clc, n, &q->clhash.hash[i], hnode) {
+			cl = container_of(clc, struct hfsc_class, cl_common);
 			hfsc_reset_class(cl);
+		}
 	}
 	__skb_queue_purge(&q->requeue);
 	q->eligible = RB_ROOT;
@@ -1537,17 +1537,25 @@ static void
 hfsc_destroy_qdisc(struct Qdisc *sch)
 {
 	struct hfsc_sched *q = qdisc_priv(sch);
-	struct hfsc_class *cl, *next;
+	struct Qdisc_class_common *clc;
+	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(clc, n, &q->clhash.hash[i], hnode) {
+			cl = container_of(clc, struct hfsc_class, cl_common);
 			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(clc, n, next, &q->clhash.hash[i],
+					  hnode) {
+			cl = container_of(clc, struct hfsc_class, cl_common);
 			hfsc_destroy_class(sch, cl);
+		}
 	}
+	qdisc_class_hash_destroy(&q->clhash);
 	__skb_queue_purge(&q->requeue);
 	qdisc_watchdog_cancel(&q->watchdog);
 }

net-sched 03/05: 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 1c1dd74775cc105566840b020475186ee321e6ec
tree 1bfbe6763e00238289b55d026ac50db305b4482f
parent 894a1f0874e239e431ec524eb10782d577a0a6d3
author Patrick McHardy <kaber@trash.net> Tue, 01 Jul 2008 14:02:56 +0200
committer Patrick McHardy <kaber@trash.net> Tue, 01 Jul 2008 14:02:56 +0200

 net/sched/sch_cbq.c |  114 ++++++++++++++++++++++++++-------------------------
 1 files changed, 58 insertions(+), 56 deletions(-)

diff --git a/net/sched/sch_cbq.c b/net/sched/sch_cbq.c
index 2a3c97f..6896bd0 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
@@ -1070,14 +1061,17 @@ static void cbq_adjust_levels(struct cbq_class *this)
 
 static void cbq_normalize_quanta(struct cbq_sched_data *q, int prio)
 {
+	struct Qdisc_class_common *clc;
+	struct hlist_node *n;
 	struct cbq_class *cl;
-	unsigned h;
+	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(clc, n, &q->clhash.hash[h], hnode) {
+			cl = container_of(clc, struct cbq_class, common);
 			/* BUGGGG... Beware! This expression suffer of
 			   arithmetic overflows!
 			 */
@@ -1086,7 +1080,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 +1108,13 @@ 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 Qdisc_class_common *clc;
+			struct hlist_node *n;
 			struct cbq_class *c;
 
-			for (c = q->classes[h]; c; c = c->next) {
+			hlist_for_each_entry(clc, n, &q->clhash.hash[h], hnode) {
+				c = container_of(clc, struct cbq_class, common);
 				if (c->split == split && c->level < level &&
 				    c->defmap&(1<<i)) {
 					split->defaults[i] = c;
@@ -1135,12 +1132,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 +1160,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 +1186,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;
@@ -1241,6 +1230,8 @@ static void
 cbq_reset(struct Qdisc* sch)
 {
 	struct cbq_sched_data *q = qdisc_priv(sch);
+	struct Qdisc_class_common *clc;
+	struct hlist_node *n;
 	struct cbq_class *cl;
 	int prio;
 	unsigned h;
@@ -1258,8 +1249,9 @@ 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(clc, n, &q->clhash.hash[h], hnode) {
+			cl = container_of(clc, struct cbq_class, common);
 			qdisc_reset(cl->q);
 
 			cl->next_alive = NULL;
@@ -1408,7 +1400,7 @@ static int cbq_init(struct Qdisc *sch, struct nlattr *opt)
 
 	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)))
@@ -1521,7 +1513,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 +1594,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 +1642,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 +1709,8 @@ static void
 cbq_destroy(struct Qdisc* sch)
 {
 	struct cbq_sched_data *q = qdisc_priv(sch);
+	struct Qdisc_class_common *clc;
+	struct hlist_node *n, *next;
 	struct cbq_class *cl;
 	unsigned h;
 
@@ -1727,18 +1722,20 @@ 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(clc, n, &q->clhash.hash[h], hnode) {
+			cl = container_of(clc, struct cbq_class, common);
 			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(clc, n, next, &q->clhash.hash[h],
+					  hnode) {
+			cl = container_of(clc, struct cbq_class, common);
 			cbq_destroy_class(sch, cl);
 		}
 	}
+	qdisc_class_hash_destroy(&q->clhash);
 }
 
 static void cbq_put(struct Qdisc *sch, unsigned long arg)
@@ -1781,7 +1778,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 +1881,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 +1914,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,19 +2008,21 @@ 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 Qdisc_class_common *clc;
+	struct hlist_node *n;
+	struct cbq_class *cl;
 	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(clc, n, &q->clhash.hash[h], hnode) {
 			if (arg->count < arg->skip) {
 				arg->count++;
 				continue;
 			}
+			cl = container_of(clc, struct cbq_class, common);
 			if (arg->fn(sch, (unsigned long)cl, arg) < 0) {
 				arg->stop = 1;
 				return;

net-sched 04/05: 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 class in hierarchical order, which
is not necessary if filters are destroyed in a seperate 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 9f2a43febc3ce5413407769c4f5fe3a36b713386
tree 7d0b8be1f29d8167635b67ecd5cb1e392b7e19a7
parent 1c1dd74775cc105566840b020475186ee321e6ec
author Patrick McHardy <kaber@trash.net> Tue, 01 Jul 2008 16:01:24 +0200
committer Patrick McHardy <kaber@trash.net> Tue, 01 Jul 2008 16:01:24 +0200

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

diff --git a/net/sched/sch_htb.c b/net/sched/sch_htb.c
index 0284791..879f0b6 100644
--- a/net/sched/sch_htb.c
+++ b/net/sched/sch_htb.c
@@ -1238,14 +1238,6 @@ static void htb_destroy_class(struct Qdisc *sch, struct htb_class *cl)
 
 	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);
 
@@ -1259,6 +1251,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 +1262,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,8 +1301,9 @@ 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);

net-sched 05/05: 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 5d491458d7476e787490cc7f52b37c853eb3d6fa
tree f6bbf00a12bc20cb209614922f0136720723b203
parent 9f2a43febc3ce5413407769c4f5fe3a36b713386
author Patrick McHardy <kaber@trash.net> Tue, 01 Jul 2008 16:05:12 +0200
committer Patrick McHardy <kaber@trash.net> Tue, 01 Jul 2008 16:05:12 +0200

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

diff --git a/net/sched/sch_htb.c b/net/sched/sch_htb.c
index 879f0b6..d5e4fdb 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,14 @@ 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 Qdisc_class_common *clc;
+	struct hlist_node *n;
+	struct htb_class *cl;
+	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(clc, n, &q->clhash.hash[i], hnode) {
+			cl = container_of(clc, struct htb_class, common);
 			if (cl->level)
 				memset(&cl->un.inner, 0, sizeof(cl->un.inner));
 			else {
@@ -1040,8 +1023,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 +1080,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 +1136,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);
@@ -1252,6 +1236,7 @@ static void htb_destroy(struct Qdisc *sch)
 {
 	struct htb_sched *q = qdisc_priv(sch);
 	struct hlist_node *n, *next;
+	struct Qdisc_class_common *clc;
 	struct htb_class *cl;
 	unsigned int i;
 
@@ -1262,14 +1247,20 @@ 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(clc, n, &q->clhash.hash[i], hnode) {
+			cl = container_of(clc, struct htb_class, common);
 			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(clc, n, next, &q->clhash.hash[i],
+					  hnode) {
+			cl = container_of(clc, struct htb_class, common);
 			htb_destroy_class(sch, cl);
+		}
 	}
+	qdisc_class_hash_destroy(&q->clhash);
 	__skb_queue_purge(&q->direct_queue);
 }
 
@@ -1289,7 +1280,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;
 	}
 
@@ -1301,8 +1292,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)
@@ -1396,7 +1387,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);
@@ -1431,7 +1421,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 */
@@ -1442,7 +1432,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 {
@@ -1460,13 +1450,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)
@@ -1489,6 +1479,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;
 
@@ -1545,20 +1537,21 @@ 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 Qdisc_class_common *clc;
+	struct hlist_node *n;
+	struct htb_class *cl;
+	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(clc, n, &q->clhash.hash[i], hnode) {
 			if (arg->count < arg->skip) {
 				arg->count++;
 				continue;
 			}
+			cl = container_of(clc, struct htb_class, common);
 			if (arg->fn(sch, (unsigned long)cl, arg) < 0) {
 				arg->stop = 1;
 				return;

Re: [RFC]: net-sched 00/05: dynamically sized class hashes

[David Miller]

From: Patrick McHardy <kaber@trash.net>
Date: Tue,  1 Jul 2008 16:34:11 +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.
> 
> Only RFC at this point because they haven't been tested thoroughly yet
> and depend on the filter destruction fixes I sent this morning, but any
> review (especially of 4/5, the htb_delete changes) is welcome.

These patches look fine to me.

I haven't investigated the correctness of the details of patch
4 yet, sorry :-)  Maybe someone else will be able to.

Re: [RFC]: net-sched 00/05: dynamically sized class hashes

[Martin Devera]

David Miller wrote:
> From: Patrick McHardy <kaber@trash.net>
> Date: Tue,  1 Jul 2008 16:34:11 +0200 (MEST)
> 
>> Only RFC at this point because they haven't been tested thoroughly yet
>> and depend on the filter destruction fixes I sent this morning, but any
>> review (especially of 4/5, the htb_delete changes) is welcome.
> 
> These patches look fine to me.
> 
> I haven't investigated the correctness of the details of patch
> 4 yet, sorry :-)  Maybe someone else will be able to.
> 

It seems ok to me. I even can't remember why to destroy in class order :-)
Interestingly, once you do this patch then children/siblings list-heads
are used only in htb_parent_last_child and to detect empty class.
Thus we could remove children/siblings lists altogether ane keep only
children counter.
I can't believe it is so simple, what do you think, Patrick ?

Martin

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

[Jarek Poplawski]

Patrick McHardy wrote, On 07/01/2008 04:34 PM:
...
> diff --git a/net/sched/sch_htb.c b/net/sched/sch_htb.c
> index 0284791..879f0b6 100644
> --- a/net/sched/sch_htb.c
> +++ b/net/sched/sch_htb.c
> @@ -1238,14 +1238,6 @@ static void htb_destroy_class(struct Qdisc *sch, struct htb_class *cl)
>  
>  	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);

I'll try to check this all more later, but this probably "ain't" good:
during deactivation a class can use a parent class, so there would be
a use after kfree if it's not "parents after children". IMHO, it's
better to do a separate version of htb_destroy_class() for
htb_destroy(), and skip there htb_deactivate(), tcf_destroy_chain()
and htb_safe_rb_erase() which are not needed at the moment.

Regards,
Jarek P.

>  
> @@ -1259,6 +1251,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 +1262,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,8 +1301,9 @@ 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);

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

[Patrick McHardy]

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

Jarek Poplawski wrote:
> Patrick McHardy wrote, On 07/01/2008 04:34 PM:
> ...
>> diff --git a/net/sched/sch_htb.c b/net/sched/sch_htb.c
>> index 0284791..879f0b6 100644
>> --- a/net/sched/sch_htb.c
>> +++ b/net/sched/sch_htb.c
>> @@ -1238,14 +1238,6 @@ static void htb_destroy_class(struct Qdisc *sch, struct htb_class *cl)
>>  
>>  	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);
> 
> I'll try to check this all more later, but this probably "ain't" good:
> during deactivation a class can use a parent class, so there would be
> a use after kfree if it's not "parents after children". IMHO, it's
> better to do a separate version of htb_destroy_class() for
> htb_destroy(), and skip there htb_deactivate(), tcf_destroy_chain()
> and htb_safe_rb_erase() which are not needed at the moment.

Good point.

Actually deactivation in htb_destroy_class is unnecessary, in
htb_delete() its done immediately anyway (as it should), in
htb_destroy() the entire qdisc is killed atomically and thus
there is no need for deactivation of single classes.

The tcf_destroy_chain() call is harmless since all filters are
already gone when going through qdisc_destroy(). Which leaves
htb_safe_rb_erase(), which looks like it should also be performed
in htb_delete() since otherwise the class will still be visible
in the rb tree in the period between dropping the lock in
htb_delete() and the final destruction in htb_put(). Similar
to deactivation, removal from the rb tree is unnecessary in
the qdisc_destroy() case.

Attached is a incremental patch and the full new patch that
makes these changes.


[-- Attachment #2: x --]
[-- Type: text/plain, Size: 755 bytes --]

diff --git a/net/sched/sch_htb.c b/net/sched/sch_htb.c
index 879f0b6..0d49930 100644
--- a/net/sched/sch_htb.c
+++ b/net/sched/sch_htb.c
@@ -1237,13 +1237,6 @@ static void htb_destroy_class(struct Qdisc *sch, struct htb_class *cl)
 	qdisc_put_rtab(cl->ceil);
 
 	tcf_destroy_chain(&cl->filter_list);
-
-	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);
 }
 
@@ -1308,6 +1301,9 @@ static int htb_delete(struct Qdisc *sch, unsigned long arg)
 	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);
 

[-- Attachment #3: 04.diff --]
[-- Type: text/x-diff, Size: 3042 bytes --]

commit c5b52f74c6b35a570995472295a5dae9d3d3ca74
Author: Patrick McHardy <kaber@trash.net>
Date:   Wed Jul 2 12:10:36 2008 +0200

    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 class in hierarchical order, which
    is not necessary if filters are destroyed in a seperate 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>

diff --git a/net/sched/sch_htb.c b/net/sched/sch_htb.c
index 0284791..0d49930 100644
--- a/net/sched/sch_htb.c
+++ b/net/sched/sch_htb.c
@@ -1237,21 +1237,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 +1244,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 +1255,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 +1294,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);
 

Re: [RFC]: net-sched 00/05: dynamically sized class hashes

[Patrick McHardy]

Martin Devera wrote:
> David Miller wrote:
>> From: Patrick McHardy <kaber@trash.net>
>> Date: Tue,  1 Jul 2008 16:34:11 +0200 (MEST)
>>
>>> Only RFC at this point because they haven't been tested thoroughly yet
>>> and depend on the filter destruction fixes I sent this morning, but any
>>> review (especially of 4/5, the htb_delete changes) is welcome.
>>
>> These patches look fine to me.
>>
>> I haven't investigated the correctness of the details of patch
>> 4 yet, sorry :-)  Maybe someone else will be able to.
>>
> 
> It seems ok to me. I even can't remember why to destroy in class order :-)
> Interestingly, once you do this patch then children/siblings list-heads
> are used only in htb_parent_last_child and to detect empty class.
> Thus we could remove children/siblings lists altogether ane keep only
> children counter.
> I can't believe it is so simple, what do you think, Patrick ?

Yes, it looks like that would work. I'll give it a try :)

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

[Jarek Poplawski]

On Wed, Jul 02, 2008 at 12:11:06PM +0200, Patrick McHardy wrote:
...
> commit c5b52f74c6b35a570995472295a5dae9d3d3ca74
> Author: Patrick McHardy <kaber@trash.net>
> Date:   Wed Jul 2 12:10:36 2008 +0200
> 
>     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 class in hierarchical order, which

-     is not necessary if filters are destroyed in a seperate iteration
+     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>

I think this patch is OK.

Jarek P.

> 
> diff --git a/net/sched/sch_htb.c b/net/sched/sch_htb.c
> index 0284791..0d49930 100644
> --- a/net/sched/sch_htb.c
> +++ b/net/sched/sch_htb.c
> @@ -1237,21 +1237,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 +1244,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 +1255,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 +1294,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);
>  

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

[Patrick McHardy]

Jarek Poplawski wrote:
> On Wed, Jul 02, 2008 at 12:11:06PM +0200, Patrick McHardy wrote:
> ...
>> commit c5b52f74c6b35a570995472295a5dae9d3d3ca74
>> Author: Patrick McHardy <kaber@trash.net>
>> Date:   Wed Jul 2 12:10:36 2008 +0200
>>
>>     net-sched: sch_htb: move hash and sibling list removal to htb_delete
>>     
> I think this patch is OK.

Thanks for your help.

Re: [RFC]: net-sched 00/05: dynamically sized class hashes

[Patrick McHardy]

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

Patrick McHardy wrote:
> Martin Devera wrote:
>> Interestingly, once you do this patch then children/siblings list-heads
>> are used only in htb_parent_last_child and to detect empty class.
>> Thus we could remove children/siblings lists altogether ane keep only
>> children counter.
>> I can't believe it is so simple, what do you think, Patrick ?
> 
> Yes, it looks like that would work. I'll give it a try :)

How about this, on top of my previous patches?



[-- Attachment #2: x --]
[-- Type: text/plain, Size: 2730 bytes --]

diff --git a/net/sched/sch_htb.c b/net/sched/sch_htb.c
index 4fc866d..bb1c210 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) */
 
@@ -1022,7 +1020,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;
@@ -1177,12 +1174,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;
 }
 
@@ -1266,7 +1260,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)) {
@@ -1285,7 +1279,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);
@@ -1380,8 +1374,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);
 
@@ -1427,8 +1420,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: [RFC]: net-sched 00/05: dynamically sized class hashes

[Martin Devera]

Patrick McHardy wrote:
> Patrick McHardy wrote:
>> Martin Devera wrote:
>>> Interestingly, once you do this patch then children/siblings list-heads
>>> are used only in htb_parent_last_child and to detect empty class.
>>> Thus we could remove children/siblings lists altogether ane keep only
>>> children counter.
>>> I can't believe it is so simple, what do you think, Patrick ?
>>
>> Yes, it looks like that would work. I'll give it a try :)
> 
> How about this, on top of my previous patches?

Yes, it is exactly what have been in my mind. It should work.
Only I'm wondering why I didn't do it this way in the first
version :-)

Re: [RFC]: net-sched 00/05: dynamically sized class hashes

[Patrick McHardy]

Martin Devera wrote:
> Patrick McHardy wrote:
>> Patrick McHardy wrote:
>>> Martin Devera wrote:
>>>> Interestingly, once you do this patch then children/siblings list-heads
>>>> are used only in htb_parent_last_child and to detect empty class.
>>>> Thus we could remove children/siblings lists altogether ane keep only
>>>> children counter.
>>>> I can't believe it is so simple, what do you think, Patrick ?
>>>
>>> Yes, it looks like that would work. I'll give it a try :)
>>
>> How about this, on top of my previous patches?
> 
> Yes, it is exactly what have been in my mind. It should work.

Thanks!

> Only I'm wondering why I didn't do it this way in the first
> version :-)

I'm guessing there was no working example of destroying
filters without walking the tree in hierarchical order.
All other qdiscs were buggy or non-existant at that time :)

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

[Jarek Poplawski]

A tiny update below...

On Wed, Jul 02, 2008 at 12:11:06PM +0200, Patrick McHardy wrote:
...
> commit c5b52f74c6b35a570995472295a5dae9d3d3ca74
> Author: Patrick McHardy <kaber@trash.net>
> Date:   Wed Jul 2 12:10:36 2008 +0200
> 
>     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 class in hierarchical order, which
+     that qdisc destruction destroys classes in hierarchical order, which
-     is not necessary if filters are destroyed in a seperate iteration
+     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>

I still think the patch is OK, but this one little compile warning
(which, I guess, you've seen already...):

net/sched/sch_htb.c: In function 'htb_destroy_class':
net/sched/sch_htb.c:1215: warning: unused variable 'q'

Jarek P.

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

[Jarek Poplawski]

Patrick McHardy wrote, On 07/01/2008 04:34 PM:

> net-sched: sch_htb: use dynamic class hash helpers
> 
> Signed-off-by: Patrick McHardy <kaber@trash.net>

This patch also looks OK too me, except 2 tiny doubts below:

> diff --git a/net/sched/sch_htb.c b/net/sched/sch_htb.c
> index 879f0b6..d5e4fdb 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;

Hmm... isn't this variable name too "common"? Why not something more
meaningful like: id, node, head, info etc?

...
> @@ -975,13 +957,14 @@ 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 Qdisc_class_common *clc;
> +	struct hlist_node *n;
> +	struct htb_class *cl;
> +	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(clc, n, &q->clhash.hash[i], hnode) {
> +			cl = container_of(clc, struct htb_class, common);

Why not?:
		hlist_for_each_entry(cl, n, &q->clhash.hash[i], common.hnode) {

Of course, this is probably a matter of taste, so I don't persist...

Jarek P.

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

[Patrick McHardy]

Jarek Poplawski wrote:
> A tiny update below...
>
> On Wed, Jul 02, 2008 at 12:11:06PM +0200, Patrick McHardy wrote:
> ...
>   
> I still think the patch is OK, but this one little compile warning
> (which, I guess, you've seen already...):
>
> net/sched/sch_htb.c: In function 'htb_destroy_class':
> net/sched/sch_htb.c:1215: warning: unused variable 'q'


Yes, I already fixed that.

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

[Patrick McHardy]

Jarek Poplawski wrote:
> Patrick McHardy wrote, On 07/01/2008 04:34 PM:
>
>   
>> net-sched: sch_htb: use dynamic class hash helpers
>>
>> Signed-off-by: Patrick McHardy <kaber@trash.net>
>>     
>
> This patch also looks OK too me, except 2 tiny doubts below:
>
>   
>> diff --git a/net/sched/sch_htb.c b/net/sched/sch_htb.c
>> index 879f0b6..d5e4fdb 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;
>>     
>
> Hmm... isn't this variable name too "common"? Why not something more
> meaningful like: id, node, head, info etc?
>   
I couldn't come up with something better, your
suggestions are also not much more descriptive
in my opinion. I'm also hoping we can put more
stuff in there and so some consolidation later.

> ...
>   
>> @@ -975,13 +957,14 @@ 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 Qdisc_class_common *clc;
>> +	struct hlist_node *n;
>> +	struct htb_class *cl;
>> +	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(clc, n, &q->clhash.hash[i], hnode) {
>> +			cl = container_of(clc, struct htb_class, common);
>>     
>
> Why not?:
> 		hlist_for_each_entry(cl, n, &q->clhash.hash[i], common.hnode) {
>
> Of course, this is probably a matter of taste, so I don't persist...

Good point, that is nicer. I'll update the patches.

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

[Patrick McHardy]

Jarek Poplawski wrote:
>> +static inline void *qdisc_class_find(struct Qdisc_class_hash *hash, u32 id)
>>     
>
> Why not Qdisc_class_common *?
>   

I originally didn't use container_of but simply required
Qdisc_class_common to be the first element of the
class struct, this is a remnant of that. I'll change it,
thanks.

>> +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)
>>     
>
> With current init hashsize == 4 this will trigger after adding: 4th,
> 7th, 13th,... class. Maybe we could start with something higher?
>   

We could, but I don't think it makes any difference, for those
small numbers the rehashing is really cheap.

>> +		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]);
>>     
>
> With a large number of classes and changes this could probably give
> noticable delays, so maybe there would be reasonable to add a
> possibility of user defined, ungrowable hashsize as well?

I don't think its really going to be noticable (the numbers are not
*that* large), but I'll try to get some numbers.

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

[Jarek Poplawski]

A few tiny doubts below...

Patrick McHardy wrote, On 07/01/2008 04:34 PM:

> net-sched: add dynamically sized qdisc class hash helpers
> 
> Signed-off-by: Patrick McHardy <kaber@trash.net>
> 
> ---
> commit fe2579f858479ce266763ba861c87cd0371389af
> tree fe574771047ca02df76c7ec07d70b9402278531a
> parent 98cd24a4b3ac9ba234631803a05f96c3fddb500b
> author Patrick McHardy <kaber@trash.net> Tue, 01 Jul 2008 14:02:55 +0200
> committer Patrick McHardy <kaber@trash.net> Tue, 01 Jul 2008 14:02:55 +0200
> 
>  include/net/sch_generic.h |   41 ++++++++++++++++++
>  net/sched/sch_api.c       |  104 +++++++++++++++++++++++++++++++++++++++++++++
>  2 files changed, 145 insertions(+), 0 deletions(-)
> 
> diff --git a/include/net/sch_generic.h b/include/net/sch_generic.h
> index a87fc03..0541d3c 100644
> --- a/include/net/sch_generic.h
> +++ b/include/net/sch_generic.h
> @@ -167,6 +167,47 @@ 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;

?	u32			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 void *qdisc_class_find(struct Qdisc_class_hash *hash, u32 id)

Why not Qdisc_class_common *?

> +{
> +	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)

With current init hashsize == 4 this will trigger after adding: 4th,
7th, 13th,... class. Maybe we could start with something higher?

> +		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]);

With a large number of classes and changes this could probably give
noticable delays, so maybe there would be reasonable to add a
possibility of user defined, ungrowable hashsize as well?

Otherwise, it looks very nice to me.

Thanks,
Jarek P.

> +		}
> +	}
> +	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)