[NET_SCHED 00/06]: Fix endless dequeue loops

[NET_SCHED 00/06]: Fix endless dequeue loops

[Patrick McHardy]

These patches fix endless qdisc dequeue loops caused by inaccurate
qlen counters that can be triggered quite easily when changing
things while packets are queued. Please read the individual changelog
entries for details.

I've split them into very small pieces for easier review in case we
want to put them in 2.6.19. The problem has always been present, so
it doesn't seem to affect many people.

Martin, can you please review the HTB parts? Thanks.


PS: If anyone wants to suggest a nicer name for qdisc_tree_decrease_qlen
I'll gladly send new patches :)


 include/net/sch_generic.h |    4 +++-
 net/sched/sch_api.c       |   38 ++++++++++++++++++++++++++++++++------
 net/sched/sch_atm.c       |    5 +++--
 net/sched/sch_cbq.c       |   10 ++++++----
 net/sched/sch_dsmark.c    |    7 ++++---
 net/sched/sch_generic.c   |    7 +++++--
 net/sched/sch_hfsc.c      |   26 ++++++++++++++++++--------
 net/sched/sch_htb.c       |   38 +++++++++++++++++++++++++++-----------
 net/sched/sch_netem.c     |    5 +++--
 net/sched/sch_prio.c      |   14 ++++++++++----
 net/sched/sch_red.c       |   14 +++++++++-----
 net/sched/sch_sfq.c       |    3 +++
 net/sched/sch_tbf.c       |   14 +++++++++-----
 13 files changed, 132 insertions(+), 53 deletions(-)

Patrick McHardy:
      [NET_SCHED]: sch_htb: perform qlen adjustment immediately in ->delete
      [NET_SCHED]: Set parent classid in default qdiscs
      [NET_SCHED]: Fix endless loops caused by inaccurate qlen counters (part 1)
      [NET_SCHED]: Fix endless loops (part 2): "simple" qdiscs
      [NET_SCHED]: Fix endless loops (part 3): HFSC
      [NET_SCHED]: Fix endless loops (part 4): HTB

[NET_SCHED 01/06]: sch_htb: perform qlen adjustment immediately in ->delete

[Patrick McHardy]

[NET_SCHED]: sch_htb: perform qlen adjustment immediately in ->delete

qlen adjustment should happen immediately in ->delete and not in the
class destroy function because the reference count will not hit zero in
->delete (sch_api holds a reference) but in ->put. Since the qdisc
lock is released between deletion of the class and final destruction
this creates an externally visible error in the qlen counter.

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

---
commit 28ceb9f1cece3e1fa989a96a99dc76dc44d5629b
tree 568ab7acb7b9c6d1783c5e4a23edd83ee0381e22
parent 808dbbb6bb61173bf52946a28f99089d2efa4c55
author Patrick McHardy <kaber@trash.net> Sun, 19 Nov 2006 06:55:10 +0100
committer Patrick McHardy <kaber@trash.net> Sun, 19 Nov 2006 06:55:10 +0100

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

diff --git a/net/sched/sch_htb.c b/net/sched/sch_htb.c
index 4b52fa7..08fa4d0 100644
--- a/net/sched/sch_htb.c
+++ b/net/sched/sch_htb.c
@@ -1269,9 +1269,9 @@ static void htb_destroy_filters(struct t
 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);
-		sch->q.qlen -= cl->un.leaf.q->q.qlen;
 		qdisc_destroy(cl->un.leaf.q);
 	}
 	qdisc_put_rtab(cl->rate);
@@ -1334,6 +1334,11 @@ static int htb_delete(struct Qdisc *sch,
 	/* delete from hash and active; remainder in destroy_class */
 	hlist_del_init(&cl->hlist);
 
+	if (!cl->level) {
+		sch->q.qlen -= cl->un.leaf.q->q.qlen;
+		qdisc_reset(cl->un.leaf.q);
+	}
+
 	if (cl->prio_activity)
 		htb_deactivate(q, cl);
 

Re: [NET_SCHED 01/06]: sch_htb: perform qlen adjustment immediately in ->delete

[David Miller]

From: Patrick McHardy <kaber@trash.net>
Date: Mon, 20 Nov 2006 14:08:37 +0100 (MET)

> [NET_SCHED]: sch_htb: perform qlen adjustment immediately in ->delete
> 
> qlen adjustment should happen immediately in ->delete and not in the
> class destroy function because the reference count will not hit zero in
> ->delete (sch_api holds a reference) but in ->put. Since the qdisc
> lock is released between deletion of the class and final destruction
> this creates an externally visible error in the qlen counter.
> 
> Signed-off-by: Patrick McHardy <kaber@trash.net>

Applied to net-2.6.20

[NET_SCHED 02/06]: Set parent classid in default qdiscs

[Patrick McHardy]

[NET_SCHED]: Set parent classid in default qdiscs

Set parent classids in default qdiscs to allow walking up the tree
from outside the qdiscs. This is needed by the next patch.

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

---
commit 825dfe1f03e69f3c2b56e6bd6ceea7ffe23c65bf
tree 28592aa602dcd936add9fb2851c97c5a603dda85
parent 28ceb9f1cece3e1fa989a96a99dc76dc44d5629b
author Patrick McHardy <kaber@trash.net> Mon, 20 Nov 2006 13:42:53 +0100
committer Patrick McHardy <kaber@trash.net> Mon, 20 Nov 2006 13:42:53 +0100

 include/net/sch_generic.h |    2 +-
 net/sched/sch_atm.c       |    5 +++--
 net/sched/sch_cbq.c       |    8 +++++---
 net/sched/sch_dsmark.c    |    5 +++--
 net/sched/sch_generic.c   |    7 +++++--
 net/sched/sch_hfsc.c      |    8 +++++---
 net/sched/sch_htb.c       |    7 ++++---
 net/sched/sch_netem.c     |    3 ++-
 net/sched/sch_prio.c      |    3 ++-
 net/sched/sch_red.c       |    8 +++++---
 net/sched/sch_tbf.c       |    8 +++++---
 11 files changed, 40 insertions(+), 24 deletions(-)

diff --git a/include/net/sch_generic.h b/include/net/sch_generic.h
index b0e9108..660ff0a 100644
--- a/include/net/sch_generic.h
+++ b/include/net/sch_generic.h
@@ -174,7 +174,7 @@ extern void qdisc_reset(struct Qdisc *qd
 extern void qdisc_destroy(struct Qdisc *qdisc);
 extern struct Qdisc *qdisc_alloc(struct net_device *dev, struct Qdisc_ops *ops);
 extern struct Qdisc *qdisc_create_dflt(struct net_device *dev,
-				       struct Qdisc_ops *ops);
+				       struct Qdisc_ops *ops, u32 parentid);
 
 static inline void
 tcf_destroy(struct tcf_proto *tp)
diff --git a/net/sched/sch_atm.c b/net/sched/sch_atm.c
index dbf44da..edc7bb0 100644
--- a/net/sched/sch_atm.c
+++ b/net/sched/sch_atm.c
@@ -316,7 +316,7 @@ static int atm_tc_change(struct Qdisc *s
 	}
 	memset(flow,0,sizeof(*flow));
 	flow->filter_list = NULL;
-	if (!(flow->q = qdisc_create_dflt(sch->dev,&pfifo_qdisc_ops)))
+	if (!(flow->q = qdisc_create_dflt(sch->dev,&pfifo_qdisc_ops,classid)))
 		flow->q = &noop_qdisc;
 	DPRINTK("atm_tc_change: qdisc %p\n",flow->q);
 	flow->sock = sock;
@@ -576,7 +576,8 @@ static int atm_tc_init(struct Qdisc *sch
 
 	DPRINTK("atm_tc_init(sch %p,[qdisc %p],opt %p)\n",sch,p,opt);
 	p->flows = &p->link;
-	if(!(p->link.q = qdisc_create_dflt(sch->dev,&pfifo_qdisc_ops)))
+	if(!(p->link.q = qdisc_create_dflt(sch->dev,&pfifo_qdisc_ops,
+					   sch->handle)))
 		p->link.q = &noop_qdisc;
 	DPRINTK("atm_tc_init: link (%p) qdisc %p\n",&p->link,p->link.q);
 	p->link.filter_list = NULL;
diff --git a/net/sched/sch_cbq.c b/net/sched/sch_cbq.c
index bac881b..908b10d 100644
--- a/net/sched/sch_cbq.c
+++ b/net/sched/sch_cbq.c
@@ -1429,7 +1429,8 @@ static int cbq_init(struct Qdisc *sch, s
 	q->link.sibling = &q->link;
 	q->link.classid = sch->handle;
 	q->link.qdisc = sch;
-	if (!(q->link.q = qdisc_create_dflt(sch->dev, &pfifo_qdisc_ops)))
+	if (!(q->link.q = qdisc_create_dflt(sch->dev, &pfifo_qdisc_ops,
+					    sch->handle)))
 		q->link.q = &noop_qdisc;
 
 	q->link.priority = TC_CBQ_MAXPRIO-1;
@@ -1674,7 +1675,8 @@ static int cbq_graft(struct Qdisc *sch, 
 
 	if (cl) {
 		if (new == NULL) {
-			if ((new = qdisc_create_dflt(sch->dev, &pfifo_qdisc_ops)) == NULL)
+			if ((new = qdisc_create_dflt(sch->dev, &pfifo_qdisc_ops,
+						     cl->classid)) == NULL)
 				return -ENOBUFS;
 		} else {
 #ifdef CONFIG_NET_CLS_POLICE
@@ -1932,7 +1934,7 @@ #endif
 	cl->R_tab = rtab;
 	rtab = NULL;
 	cl->refcnt = 1;
-	if (!(cl->q = qdisc_create_dflt(sch->dev, &pfifo_qdisc_ops)))
+	if (!(cl->q = qdisc_create_dflt(sch->dev, &pfifo_qdisc_ops, classid)))
 		cl->q = &noop_qdisc;
 	cl->classid = classid;
 	cl->tparent = parent;
diff --git a/net/sched/sch_dsmark.c b/net/sched/sch_dsmark.c
index 11c8a21..7809073 100644
--- a/net/sched/sch_dsmark.c
+++ b/net/sched/sch_dsmark.c
@@ -88,7 +88,8 @@ static int dsmark_graft(struct Qdisc *sc
 		sch, p, new, old);
 
 	if (new == NULL) {
-		new = qdisc_create_dflt(sch->dev, &pfifo_qdisc_ops);
+		new = qdisc_create_dflt(sch->dev, &pfifo_qdisc_ops,
+					sch->handle);
 		if (new == NULL)
 			new = &noop_qdisc;
 	}
@@ -387,7 +388,7 @@ static int dsmark_init(struct Qdisc *sch
 	p->default_index = default_index;
 	p->set_tc_index = RTA_GET_FLAG(tb[TCA_DSMARK_SET_TC_INDEX-1]);
 
-	p->q = qdisc_create_dflt(sch->dev, &pfifo_qdisc_ops);
+	p->q = qdisc_create_dflt(sch->dev, &pfifo_qdisc_ops, sch->handle);
 	if (p->q == NULL)
 		p->q = &noop_qdisc;
 
diff --git a/net/sched/sch_generic.c b/net/sched/sch_generic.c
index 88c6a99..deafeb9 100644
--- a/net/sched/sch_generic.c
+++ b/net/sched/sch_generic.c
@@ -450,13 +450,15 @@ errout:
 	return ERR_PTR(-err);
 }
 
-struct Qdisc * qdisc_create_dflt(struct net_device *dev, struct Qdisc_ops *ops)
+struct Qdisc * qdisc_create_dflt(struct net_device *dev, struct Qdisc_ops *ops,
+				 unsigned int parentid)
 {
 	struct Qdisc *sch;
 	
 	sch = qdisc_alloc(dev, ops);
 	if (IS_ERR(sch))
 		goto errout;
+	sch->parent = parentid;
 
 	if (!ops->init || ops->init(sch, NULL) == 0)
 		return sch;
@@ -520,7 +522,8 @@ void dev_activate(struct net_device *dev
 	if (dev->qdisc_sleeping == &noop_qdisc) {
 		struct Qdisc *qdisc;
 		if (dev->tx_queue_len) {
-			qdisc = qdisc_create_dflt(dev, &pfifo_fast_ops);
+			qdisc = qdisc_create_dflt(dev, &pfifo_fast_ops,
+						  TC_H_ROOT);
 			if (qdisc == NULL) {
 				printk(KERN_INFO "%s: activation failed\n", dev->name);
 				return;
diff --git a/net/sched/sch_hfsc.c b/net/sched/sch_hfsc.c
index 6a6735a..1142d29 100644
--- a/net/sched/sch_hfsc.c
+++ b/net/sched/sch_hfsc.c
@@ -1138,7 +1138,7 @@ #endif
 	cl->classid   = classid;
 	cl->sched     = q;
 	cl->cl_parent = parent;
-	cl->qdisc = qdisc_create_dflt(sch->dev, &pfifo_qdisc_ops);
+	cl->qdisc = qdisc_create_dflt(sch->dev, &pfifo_qdisc_ops, classid);
 	if (cl->qdisc == NULL)
 		cl->qdisc = &noop_qdisc;
 	cl->stats_lock = &sch->dev->queue_lock;
@@ -1271,7 +1271,8 @@ hfsc_graft_class(struct Qdisc *sch, unsi
 	if (cl->level > 0)
 		return -EINVAL;
 	if (new == NULL) {
-		new = qdisc_create_dflt(sch->dev, &pfifo_qdisc_ops);
+		new = qdisc_create_dflt(sch->dev, &pfifo_qdisc_ops,
+					cl->classid);
 		if (new == NULL)
 			new = &noop_qdisc;
 	}
@@ -1514,7 +1515,8 @@ hfsc_init_qdisc(struct Qdisc *sch, struc
 	q->root.refcnt  = 1;
 	q->root.classid = sch->handle;
 	q->root.sched   = q;
-	q->root.qdisc = qdisc_create_dflt(sch->dev, &pfifo_qdisc_ops);
+	q->root.qdisc = qdisc_create_dflt(sch->dev, &pfifo_qdisc_ops,
+					  sch->handle);
 	if (q->root.qdisc == NULL)
 		q->root.qdisc = &noop_qdisc;
 	q->root.stats_lock = &sch->dev->queue_lock;
diff --git a/net/sched/sch_htb.c b/net/sched/sch_htb.c
index 08fa4d0..3b36e9d 100644
--- a/net/sched/sch_htb.c
+++ b/net/sched/sch_htb.c
@@ -1223,8 +1223,9 @@ static int htb_graft(struct Qdisc *sch, 
 	struct htb_class *cl = (struct htb_class *)arg;
 
 	if (cl && !cl->level) {
-		if (new == NULL && (new = qdisc_create_dflt(sch->dev,
-							    &pfifo_qdisc_ops))
+		if (new == NULL &&
+		    (new = qdisc_create_dflt(sch->dev, &pfifo_qdisc_ops,
+		    			     cl->classid))
 		    == NULL)
 			return -ENOBUFS;
 		sch_tree_lock(sch);
@@ -1415,7 +1416,7 @@ static int htb_change_class(struct Qdisc
 		/* create leaf qdisc early because it uses kmalloc(GFP_KERNEL)
 		   so that can't be used inside of sch_tree_lock
 		   -- thanks to Karlis Peisenieks */
-		new_q = qdisc_create_dflt(sch->dev, &pfifo_qdisc_ops);
+		new_q = qdisc_create_dflt(sch->dev, &pfifo_qdisc_ops, classid);
 		sch_tree_lock(sch);
 		if (parent && !parent->level) {
 			/* turn parent into inner node */
diff --git a/net/sched/sch_netem.c b/net/sched/sch_netem.c
index 0441876..90aeeb7 100644
--- a/net/sched/sch_netem.c
+++ b/net/sched/sch_netem.c
@@ -574,7 +574,8 @@ static int netem_init(struct Qdisc *sch,
 	q->timer.function = netem_watchdog;
 	q->timer.data = (unsigned long) sch;
 
-	q->qdisc = qdisc_create_dflt(sch->dev, &tfifo_qdisc_ops);
+	q->qdisc = qdisc_create_dflt(sch->dev, &tfifo_qdisc_ops,
+				     TC_H_MAKE(sch->handle, 1));
 	if (!q->qdisc) {
 		pr_debug("netem: qdisc create failed\n");
 		return -ENOMEM;
diff --git a/net/sched/sch_prio.c b/net/sched/sch_prio.c
index a5fa03c..3fc0c0f 100644
--- a/net/sched/sch_prio.c
+++ b/net/sched/sch_prio.c
@@ -230,7 +230,8 @@ static int prio_tune(struct Qdisc *sch, 
 	for (i=0; i<q->bands; i++) {
 		if (q->queues[i] == &noop_qdisc) {
 			struct Qdisc *child;
-			child = qdisc_create_dflt(sch->dev, &pfifo_qdisc_ops);
+			child = qdisc_create_dflt(sch->dev, &pfifo_qdisc_ops,
+						  TC_H_MAKE(sch->handle, i + 1));
 			if (child) {
 				sch_tree_lock(sch);
 				child = xchg(&q->queues[i], child);
diff --git a/net/sched/sch_red.c b/net/sched/sch_red.c
index d65cadd..ee66c5c 100644
--- a/net/sched/sch_red.c
+++ b/net/sched/sch_red.c
@@ -175,12 +175,14 @@ static void red_destroy(struct Qdisc *sc
 	qdisc_destroy(q->qdisc);
 }
 
-static struct Qdisc *red_create_dflt(struct net_device *dev, u32 limit)
+static struct Qdisc *red_create_dflt(struct Qdisc *sch, u32 limit)
 {
-	struct Qdisc *q = qdisc_create_dflt(dev, &bfifo_qdisc_ops);
+	struct Qdisc *q;
 	struct rtattr *rta;
 	int ret;
 
+	q = qdisc_create_dflt(sch->dev, &bfifo_qdisc_ops,
+			      TC_H_MAKE(sch->handle, 1));
 	if (q) {
 		rta = kmalloc(RTA_LENGTH(sizeof(struct tc_fifo_qopt)),
 		              GFP_KERNEL);
@@ -219,7 +221,7 @@ static int red_change(struct Qdisc *sch,
 	ctl = RTA_DATA(tb[TCA_RED_PARMS-1]);
 
 	if (ctl->limit > 0) {
-		child = red_create_dflt(sch->dev, ctl->limit);
+		child = red_create_dflt(sch, ctl->limit);
 		if (child == NULL)
 			return -ENOMEM;
 	}
diff --git a/net/sched/sch_tbf.c b/net/sched/sch_tbf.c
index d9a5d29..2562a60 100644
--- a/net/sched/sch_tbf.c
+++ b/net/sched/sch_tbf.c
@@ -273,12 +273,14 @@ static void tbf_reset(struct Qdisc* sch)
 	del_timer(&q->wd_timer);
 }
 
-static struct Qdisc *tbf_create_dflt_qdisc(struct net_device *dev, u32 limit)
+static struct Qdisc *tbf_create_dflt_qdisc(struct Qdisc *sch, u32 limit)
 {
-	struct Qdisc *q = qdisc_create_dflt(dev, &bfifo_qdisc_ops);
+	struct Qdisc *q;
         struct rtattr *rta;
 	int ret;
 
+	q = qdisc_create_dflt(sch->dev, &bfifo_qdisc_ops,
+			      TC_H_MAKE(sch->handle, 1));
 	if (q) {
 		rta = kmalloc(RTA_LENGTH(sizeof(struct tc_fifo_qopt)), GFP_KERNEL);
 		if (rta) {
@@ -341,7 +343,7 @@ static int tbf_change(struct Qdisc* sch,
 		goto done;
 
 	if (qopt->limit > 0) {
-		if ((child = tbf_create_dflt_qdisc(sch->dev, qopt->limit)) == NULL)
+		if ((child = tbf_create_dflt_qdisc(sch, qopt->limit)) == NULL)
 			goto done;
 	}
 

Re: [NET_SCHED 02/06]: Set parent classid in default qdiscs

[David Miller]

From: Patrick McHardy <kaber@trash.net>
Date: Mon, 20 Nov 2006 14:08:38 +0100 (MET)

> [NET_SCHED]: Set parent classid in default qdiscs
> 
> Set parent classids in default qdiscs to allow walking up the tree
> from outside the qdiscs. This is needed by the next patch.
> 
> Signed-off-by: Patrick McHardy <kaber@trash.net>

Applied to net-2.6.20, thanks Patrick.

[NET_SCHED 03/06]: Fix endless loops caused by inaccurate qlen counters (part 1)

[Patrick McHardy]

[NET_SCHED]: Fix endless loops caused by inaccurate qlen counters (part 1)

There are multiple problems related to qlen adjustment that can lead
to an upper qdisc getting out of sync with the real number of packets
queued, leading to endless dequeueing attempts by the upper layer code.

All qdiscs must maintain an accurate q.qlen counter. There are basically
two groups of operations affecting the qlen: operations that propagate
down the tree (enqueue, dequeue, requeue, drop, reset) beginning at the
root qdisc and operations only affecting a subtree or single qdisc
(change, graft, delete class). Since qlen changes during operations from
the second group don't propagate to ancestor qdiscs, their qlen values
become desynchronized.

This patch adds a function to propagate qlen changes up the qdisc tree,
optionally calling a callback function to perform qdisc-internal
maintenance when the child qdisc becomes empty. The follow-up patches
will convert all qdiscs to use this function where necessary.

Noticed by Timo Steinbach <tsteinbach@astaro.com>.

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

---
commit 42706d154c660ac3915cc0debcfa09339af29de3
tree 26dd1060dcfd2d0633d63297bb4f988d5f6c8ea8
parent 825dfe1f03e69f3c2b56e6bd6ceea7ffe23c65bf
author Patrick McHardy <kaber@trash.net> Mon, 20 Nov 2006 13:44:49 +0100
committer Patrick McHardy <kaber@trash.net> Mon, 20 Nov 2006 13:44:49 +0100

 include/net/sch_generic.h |    2 ++
 net/sched/sch_api.c       |   38 ++++++++++++++++++++++++++++++++------
 2 files changed, 34 insertions(+), 6 deletions(-)

diff --git a/include/net/sch_generic.h b/include/net/sch_generic.h
index 660ff0a..d61fb67 100644
--- a/include/net/sch_generic.h
+++ b/include/net/sch_generic.h
@@ -60,6 +60,7 @@ struct Qdisc_class_ops
 	int			(*graft)(struct Qdisc *, unsigned long cl,
 					struct Qdisc *, struct Qdisc **);
 	struct Qdisc *		(*leaf)(struct Qdisc *, unsigned long cl);
+	void			(*qlen_notify)(struct Qdisc *, unsigned long);
 
 	/* Class manipulation routines */
 	unsigned long		(*get)(struct Qdisc *, u32 classid);
@@ -172,6 +173,7 @@ extern void dev_activate(struct net_devi
 extern void dev_deactivate(struct net_device *dev);
 extern void qdisc_reset(struct Qdisc *qdisc);
 extern void qdisc_destroy(struct Qdisc *qdisc);
+extern void qdisc_tree_decrease_qlen(struct Qdisc *qdisc, unsigned int n);
 extern struct Qdisc *qdisc_alloc(struct net_device *dev, struct Qdisc_ops *ops);
 extern struct Qdisc *qdisc_create_dflt(struct net_device *dev,
 				       struct Qdisc_ops *ops, u32 parentid);
diff --git a/net/sched/sch_api.c b/net/sched/sch_api.c
index 0b64892..1c3c779 100644
--- a/net/sched/sch_api.c
+++ b/net/sched/sch_api.c
@@ -191,21 +191,27 @@ int unregister_qdisc(struct Qdisc_ops *q
    (root qdisc, all its children, children of children etc.)
  */
 
-struct Qdisc *qdisc_lookup(struct net_device *dev, u32 handle)
+static struct Qdisc *__qdisc_lookup(struct net_device *dev, u32 handle)
 {
 	struct Qdisc *q;
 
-	read_lock(&qdisc_tree_lock);
 	list_for_each_entry(q, &dev->qdisc_list, list) {
-		if (q->handle == handle) {
-			read_unlock(&qdisc_tree_lock);
+		if (q->handle == handle)
 			return q;
-		}
 	}
-	read_unlock(&qdisc_tree_lock);
 	return NULL;
 }
 
+struct Qdisc *qdisc_lookup(struct net_device *dev, u32 handle)
+{
+	struct Qdisc *q;
+
+	read_lock(&qdisc_tree_lock);
+	q = __qdisc_lookup(dev, handle);
+	read_unlock(&qdisc_tree_lock);
+	return q;
+}
+
 static struct Qdisc *qdisc_leaf(struct Qdisc *p, u32 classid)
 {
 	unsigned long cl;
@@ -348,6 +354,26 @@ dev_graft_qdisc(struct net_device *dev, 
 	return oqdisc;
 }
 
+void qdisc_tree_decrease_qlen(struct Qdisc *sch, unsigned int n)
+{
+	struct Qdisc_class_ops *cops;
+	unsigned long cl;
+	u32 parentid;
+
+	if (n == 0)
+		return;
+	while ((parentid = sch->parent)) {
+		sch = __qdisc_lookup(sch->dev, TC_H_MAJ(parentid));
+		cops = sch->ops->cl_ops;
+		if (cops->qlen_notify) {
+			cl = cops->get(sch, parentid);
+			cops->qlen_notify(sch, cl);
+			cops->put(sch, cl);
+		}
+		sch->q.qlen -= n;
+	}
+}
+EXPORT_SYMBOL(qdisc_tree_decrease_qlen);
 
 /* Graft qdisc "new" to class "classid" of qdisc "parent" or
    to device "dev".

Re: [NET_SCHED 03/06]: Fix endless loops caused by inaccurate qlen counters (part 1)

[Mika Penttilä]

> @@ -348,6 +354,26 @@ dev_graft_qdisc(struct net_device *dev, 
>  	return oqdisc;
>  }
>  
> +void qdisc_tree_decrease_qlen(struct Qdisc *sch, unsigned int n)
> +{
> +	struct Qdisc_class_ops *cops;
> +	unsigned long cl;
> +	u32 parentid;
> +
> +	if (n == 0)
> +		return;
> +	while ((parentid = sch->parent)) {
> +		sch = __qdisc_lookup(sch->dev, TC_H_MAJ(parentid));
> +		cops = sch->ops->cl_ops;
> +		if (cops->qlen_notify) {
> +			cl = cops->get(sch, parentid);
> +			cops->qlen_notify(sch, cl);
> +			cops->put(sch, cl);
> +		}
> +		sch->q.qlen -= n;
> +	}
> +}
> +EXPORT_SYMBOL(qdisc_tree_decrease_qlen);
>  
>   
Are you sure you didn't mean to :

+	while ((parentid = sch->parent)) {
+		sch = __qdisc_lookup(sch->dev, TC_H_MAJ(parentid));
+		cops = sch->ops->cl_ops;
+		if (!(sch->q.qlen -= n) && cops->qlen_notify) {    <----
+			cl = cops->get(sch, parentid);
+			cops->qlen_notify(sch, cl);
+			cops->put(sch, cl);
+		}
+	}


--Mika

Re: [NET_SCHED 03/06]: Fix endless loops caused by inaccurate qlen counters (part 1)

[Patrick McHardy]

Mika Penttilä wrote:
> Are you sure you didn't mean to :
> 
> +    while ((parentid = sch->parent)) {
> +        sch = __qdisc_lookup(sch->dev, TC_H_MAJ(parentid));
> +        cops = sch->ops->cl_ops;
> +        if (!(sch->q.qlen -= n) && cops->qlen_notify) {    <----


We could do that, currently the qdiscs check themselves.
The idea was mainly that they could be interested in
other changes as well, for example for recalculating
a deadline when the next packet in line changes.

Re: [NET_SCHED 03/06]: Fix endless loops caused by inaccurate qlen counters (part 1)

[Mika Penttilä]

Patrick McHardy wrote:
> Mika Penttilä wrote:
>   
>> Are you sure you didn't mean to :
>>
>> +    while ((parentid = sch->parent)) {
>> +        sch = __qdisc_lookup(sch->dev, TC_H_MAJ(parentid));
>> +        cops = sch->ops->cl_ops;
>> +        if (!(sch->q.qlen -= n) && cops->qlen_notify) {    <----
>>     
>
>
> We could do that, currently the qdiscs check themselves.
> The idea was mainly that they could be interested in
> other changes as well, for example for recalculating
> a deadline when the next packet in line changes.
>
>   
But you call the notify before the decrement, which seems odd...

--Mika

Re: [NET_SCHED 03/06]: Fix endless loops caused by inaccurate qlen counters (part 1)

[Patrick McHardy]

Mika Penttilä wrote:
> Patrick McHardy wrote:
> 
>> Mika Penttilä wrote:
>>  
>>
>>> Are you sure you didn't mean to :
>>>
>>> +    while ((parentid = sch->parent)) {
>>> +        sch = __qdisc_lookup(sch->dev, TC_H_MAJ(parentid));
>>> +        cops = sch->ops->cl_ops;
>>> +        if (!(sch->q.qlen -= n) && cops->qlen_notify) {    <----
>>>     
>>
>>
>>
>> We could do that, currently the qdiscs check themselves.
>> The idea was mainly that they could be interested in
>> other changes as well, for example for recalculating
>> a deadline when the next packet in line changes.
>>
>>   
> 
> But you call the notify before the decrement, which seems odd...


The notification notifies of changes in a _child_ qdisc of
the qdisc that is notified, which already has its counter
decremented. The qdisc's own counter is irrelevant for
the qdisc itself, it doesn't make any difference whether
it is decremented before or after the notification.

Re: [NET_SCHED 03/06]: Fix endless loops caused by inaccurate qlen counters (part 1)

[Mika Penttilä]

Patrick McHardy wrote:
> Mika Penttilä wrote:
>   
>> Patrick McHardy wrote:
>>
>>     
>>> Mika Penttilä wrote:
>>>  
>>>
>>>       
>>>> Are you sure you didn't mean to :
>>>>
>>>> +    while ((parentid = sch->parent)) {
>>>> +        sch = __qdisc_lookup(sch->dev, TC_H_MAJ(parentid));
>>>> +        cops = sch->ops->cl_ops;
>>>> +        if (!(sch->q.qlen -= n) && cops->qlen_notify) {    <----
>>>>     
>>>>         
>>>
>>> We could do that, currently the qdiscs check themselves.
>>> The idea was mainly that they could be interested in
>>> other changes as well, for example for recalculating
>>> a deadline when the next packet in line changes.
>>>
>>>   
>>>       
>> But you call the notify before the decrement, which seems odd...
>>     
>
>
> The notification notifies of changes in a _child_ qdisc of
> the qdisc that is notified, which already has its counter
> decremented. The qdisc's own counter is irrelevant for
> the qdisc itself, it doesn't make any difference whether
> it is decremented before or after the notification.
>
> -
>   
Has already decremented where? As I read it you notify parent and 
_after_ that decrement child's counter...
Also, shoudn't the return value of qdisc_lookup be check, I think it can 
return NULL for default qdiscs.

--Mika

Re: [NET_SCHED 03/06]: Fix endless loops caused by inaccurate qlen counters (part 1)

[Patrick McHardy]

Mika Penttilä wrote:
> Patrick McHardy wrote:
> 
>>
>> The notification notifies of changes in a _child_ qdisc of
>> the qdisc that is notified, which already has its counter
>> decremented. The qdisc's own counter is irrelevant for
>> the qdisc itself, it doesn't make any difference whether
>> it is decremented before or after the notification.
> 
> Has already decremented where? As I read it you notify parent and
> _after_ that decrement child's counter...

No, a qdisc is notified about a child, then has its own counter
decremented. The initial decrement of the first qdisc is done by
the caller.

In most cases it is actually done after the function call for
simplicity, but only when it doesn't matter - in all cases but
SFQ the call is done by a qdisc for its own child qdiscs, so
the first parent is the qdisc itself and it is known whether
it needs to be decremented in advance or now. All upper qdiscs
will always see the already decremented values for their childs.

> Also, shoudn't the return value of qdisc_lookup be check, I think it can
> return NULL for default qdiscs.

default qdiscs can't have children, so they are never looked up.

Re: [NET_SCHED 03/06]: Fix endless loops caused by inaccurate qlen counters (part 1)

[David Miller]

From: Patrick McHardy <kaber@trash.net>
Date: Mon, 20 Nov 2006 14:08:41 +0100 (MET)

> [NET_SCHED]: Fix endless loops caused by inaccurate qlen counters (part 1)
> 
> There are multiple problems related to qlen adjustment that can lead
> to an upper qdisc getting out of sync with the real number of packets
> queued, leading to endless dequeueing attempts by the upper layer code.
> 
> All qdiscs must maintain an accurate q.qlen counter. There are basically
> two groups of operations affecting the qlen: operations that propagate
> down the tree (enqueue, dequeue, requeue, drop, reset) beginning at the
> root qdisc and operations only affecting a subtree or single qdisc
> (change, graft, delete class). Since qlen changes during operations from
> the second group don't propagate to ancestor qdiscs, their qlen values
> become desynchronized.
> 
> This patch adds a function to propagate qlen changes up the qdisc tree,
> optionally calling a callback function to perform qdisc-internal
> maintenance when the child qdisc becomes empty. The follow-up patches
> will convert all qdiscs to use this function where necessary.
> 
> Noticed by Timo Steinbach <tsteinbach@astaro.com>.
> 
> Signed-off-by: Patrick McHardy <kaber@trash.net>

Applied to net-2.6.20, thanks a lot.

[NET_SCHED 04/06]: Fix endless loops (part 2): "simple" qdiscs

[Patrick McHardy]

[NET_SCHED]: Fix endless loops (part 2): "simple" qdiscs

Convert the "simple" qdiscs to use qdisc_tree_decrease_qlen() where
necessary:

- all graft operations
- destruction of old child qdiscs in prio, red and tbf change operation
- purging of queue in sfq change operation

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

---
commit 0ce9475d7baf678698eb70369f734b8feeb03e13
tree de989fa5b32c7f53e7b7b6aac686dc39bb1839bb
parent 42706d154c660ac3915cc0debcfa09339af29de3
author Patrick McHardy <kaber@trash.net> Mon, 20 Nov 2006 13:45:41 +0100
committer Patrick McHardy <kaber@trash.net> Mon, 20 Nov 2006 13:45:41 +0100

 net/sched/sch_cbq.c    |    2 +-
 net/sched/sch_dsmark.c |    2 +-
 net/sched/sch_netem.c  |    2 +-
 net/sched/sch_prio.c   |   11 ++++++++---
 net/sched/sch_red.c    |    6 ++++--
 net/sched/sch_sfq.c    |    3 +++
 net/sched/sch_tbf.c    |    6 ++++--
 7 files changed, 22 insertions(+), 10 deletions(-)

diff --git a/net/sched/sch_cbq.c b/net/sched/sch_cbq.c
index 908b10d..ba82dfa 100644
--- a/net/sched/sch_cbq.c
+++ b/net/sched/sch_cbq.c
@@ -1687,7 +1687,7 @@ #endif
 		sch_tree_lock(sch);
 		*old = cl->q;
 		cl->q = new;
-		sch->q.qlen -= (*old)->q.qlen;
+		qdisc_tree_decrease_qlen(*old, (*old)->q.qlen);
 		qdisc_reset(*old);
 		sch_tree_unlock(sch);
 
diff --git a/net/sched/sch_dsmark.c b/net/sched/sch_dsmark.c
index 7809073..e341fd9 100644
--- a/net/sched/sch_dsmark.c
+++ b/net/sched/sch_dsmark.c
@@ -96,8 +96,8 @@ static int dsmark_graft(struct Qdisc *sc
 
 	sch_tree_lock(sch);
 	*old = xchg(&p->q, new);
+	qdisc_tree_decrease_qlen(*old, (*old)->q.qlen);
 	qdisc_reset(*old);
-	sch->q.qlen = 0;
 	sch_tree_unlock(sch);
 
         return 0;
diff --git a/net/sched/sch_netem.c b/net/sched/sch_netem.c
index 90aeeb7..672c354 100644
--- a/net/sched/sch_netem.c
+++ b/net/sched/sch_netem.c
@@ -662,8 +662,8 @@ static int netem_graft(struct Qdisc *sch
 
 	sch_tree_lock(sch);
 	*old = xchg(&q->qdisc, new);
+	qdisc_tree_decrease_qlen(*old, (*old)->q.qlen);
 	qdisc_reset(*old);
-	sch->q.qlen = 0;
 	sch_tree_unlock(sch);
 
 	return 0;
diff --git a/net/sched/sch_prio.c b/net/sched/sch_prio.c
index 3fc0c0f..2567b4c 100644
--- a/net/sched/sch_prio.c
+++ b/net/sched/sch_prio.c
@@ -222,8 +222,10 @@ static int prio_tune(struct Qdisc *sch, 
 
 	for (i=q->bands; i<TCQ_PRIO_BANDS; i++) {
 		struct Qdisc *child = xchg(&q->queues[i], &noop_qdisc);
-		if (child != &noop_qdisc)
+		if (child != &noop_qdisc) {
+			qdisc_tree_decrease_qlen(child, child->q.qlen);
 			qdisc_destroy(child);
+		}
 	}
 	sch_tree_unlock(sch);
 
@@ -236,8 +238,11 @@ static int prio_tune(struct Qdisc *sch, 
 				sch_tree_lock(sch);
 				child = xchg(&q->queues[i], child);
 
-				if (child != &noop_qdisc)
+				if (child != &noop_qdisc) {
+					qdisc_tree_decrease_qlen(child,
+								 child->q.qlen);
 					qdisc_destroy(child);
+				}
 				sch_tree_unlock(sch);
 			}
 		}
@@ -295,7 +300,7 @@ static int prio_graft(struct Qdisc *sch,
 	sch_tree_lock(sch);
 	*old = q->queues[band];
 	q->queues[band] = new;
-	sch->q.qlen -= (*old)->q.qlen;
+	qdisc_tree_decrease_qlen(*old, (*old)->q.qlen);
 	qdisc_reset(*old);
 	sch_tree_unlock(sch);
 
diff --git a/net/sched/sch_red.c b/net/sched/sch_red.c
index ee66c5c..acddad0 100644
--- a/net/sched/sch_red.c
+++ b/net/sched/sch_red.c
@@ -229,8 +229,10 @@ static int red_change(struct Qdisc *sch,
 	sch_tree_lock(sch);
 	q->flags = ctl->flags;
 	q->limit = ctl->limit;
-	if (child)
+	if (child) {
+		qdisc_tree_decrease_qlen(q->qdisc, q->qdisc->q.qlen);
 		qdisc_destroy(xchg(&q->qdisc, child));
+	}
 
 	red_set_parms(&q->parms, ctl->qth_min, ctl->qth_max, ctl->Wlog,
 				 ctl->Plog, ctl->Scell_log,
@@ -308,8 +310,8 @@ static int red_graft(struct Qdisc *sch, 
 
 	sch_tree_lock(sch);
 	*old = xchg(&q->qdisc, new);
+	qdisc_tree_decrease_qlen(*old, (*old)->q.qlen);
 	qdisc_reset(*old);
-	sch->q.qlen = 0;
 	sch_tree_unlock(sch);
 	return 0;
 }
diff --git a/net/sched/sch_sfq.c b/net/sched/sch_sfq.c
index d0d6e59..459cda2 100644
--- a/net/sched/sch_sfq.c
+++ b/net/sched/sch_sfq.c
@@ -393,6 +393,7 @@ static int sfq_change(struct Qdisc *sch,
 {
 	struct sfq_sched_data *q = qdisc_priv(sch);
 	struct tc_sfq_qopt *ctl = RTA_DATA(opt);
+	unsigned int qlen;
 
 	if (opt->rta_len < RTA_LENGTH(sizeof(*ctl)))
 		return -EINVAL;
@@ -403,8 +404,10 @@ static int sfq_change(struct Qdisc *sch,
 	if (ctl->limit)
 		q->limit = min_t(u32, ctl->limit, SFQ_DEPTH);
 
+	qlen = sch->q.qlen;
 	while (sch->q.qlen >= q->limit-1)
 		sfq_drop(sch);
+	qdisc_tree_decrease_qlen(sch, qlen - sch->q.qlen);
 
 	del_timer(&q->perturb_timer);
 	if (q->perturb_period) {
diff --git a/net/sched/sch_tbf.c b/net/sched/sch_tbf.c
index 2562a60..23b7624 100644
--- a/net/sched/sch_tbf.c
+++ b/net/sched/sch_tbf.c
@@ -348,8 +348,10 @@ static int tbf_change(struct Qdisc* sch,
 	}
 
 	sch_tree_lock(sch);
-	if (child)
+	if (child) {
+		qdisc_tree_decrease_qlen(q->qdisc, q->qdisc->q.qlen);
 		qdisc_destroy(xchg(&q->qdisc, child));
+	}
 	q->limit = qopt->limit;
 	q->mtu = qopt->mtu;
 	q->max_size = max_size;
@@ -451,8 +453,8 @@ static int tbf_graft(struct Qdisc *sch, 
 
 	sch_tree_lock(sch);
 	*old = xchg(&q->qdisc, new);
+	qdisc_tree_decrease_qlen(*old, (*old)->q.qlen);
 	qdisc_reset(*old);
-	sch->q.qlen = 0;
 	sch_tree_unlock(sch);
 
 	return 0;

Re: [NET_SCHED 04/06]: Fix endless loops (part 2): "simple" qdiscs

[Jarek Poplawski]

On 20-11-2006 14:08, Patrick McHardy wrote:
> [NET_SCHED]: Fix endless loops (part 2): "simple" qdiscs
> 
> Convert the "simple" qdiscs to use qdisc_tree_decrease_qlen() where
> necessary:
> 
> - all graft operations
> - destruction of old child qdiscs in prio, red and tbf change operation
> - purging of queue in sfq change operation
> 
> Signed-off-by: Patrick McHardy <kaber@trash.net>
> 
> ---
...
>  net/sched/sch_cbq.c    |    2 +-
...
> diff --git a/net/sched/sch_cbq.c b/net/sched/sch_cbq.c
> index 908b10d..ba82dfa 100644
> --- a/net/sched/sch_cbq.c
> +++ b/net/sched/sch_cbq.c
> @@ -1687,7 +1687,7 @@ #endif
>  		sch_tree_lock(sch);
>  		*old = cl->q;
>  		cl->q = new;
> -		sch->q.qlen -= (*old)->q.qlen;
> +		qdisc_tree_decrease_qlen(*old, (*old)->q.qlen);
>  		qdisc_reset(*old);
>  		sch_tree_unlock(sch);
>

Hello,

Probably it is as usual something with my eyes but
it seems cbq needs in cbq_delete or cbq_destroy_class
some treatment (about qdisc_destroy) similar to htb.

Jarek P.

Re: [NET_SCHED 04/06]: Fix endless loops (part 2): "simple" qdiscs

[Patrick McHardy]

Jarek Poplawski wrote:
>>diff --git a/net/sched/sch_cbq.c b/net/sched/sch_cbq.c
>>index 908b10d..ba82dfa 100644
>>--- a/net/sched/sch_cbq.c
>>+++ b/net/sched/sch_cbq.c
>>@@ -1687,7 +1687,7 @@ #endif
>> 		sch_tree_lock(sch);
>> 		*old = cl->q;
>> 		cl->q = new;
>>-		sch->q.qlen -= (*old)->q.qlen;
>>+		qdisc_tree_decrease_qlen(*old, (*old)->q.qlen);
>> 		qdisc_reset(*old);
>> 		sch_tree_unlock(sch);
>>
> 
> 
> Hello,
> 
> Probably it is as usual something with my eyes but
> it seems cbq needs in cbq_delete or cbq_destroy_class
> some treatment (about qdisc_destroy) similar to htb.

No, you're right about this one, CBQ needs a few further fixes:

- deactivating of active classes when grafting

- purging of queue/q.qlen adjustment when deleting an active class

- deactivating of active classes when q.qlen drops to zero in ->drop()

- purging of queue and deactivating of active leaf classes
  when attaching a new child (presuming CBQ can only carry
  packets in leaf classes, I'm not sure about this)

and something HTB should do is to turn intermediate classes
into leaves again when their last child is deleted.

Are you interested in fixing this? :)

Re: [NET_SCHED 04/06]: Fix endless loops (part 2): "simple" qdiscs

[Jarek Poplawski]

On Fri, Nov 24, 2006 at 02:07:08PM +0100, Patrick McHardy wrote:
> Jarek Poplawski wrote:
...
> > Probably it is as usual something with my eyes but
> > it seems cbq needs in cbq_delete or cbq_destroy_class
> > some treatment (about qdisc_destroy) similar to htb.
> 
> No, you're right about this one, CBQ needs a few further fixes:
> 
> - deactivating of active classes when grafting
> 
> - purging of queue/q.qlen adjustment when deleting an active class
> 
> - deactivating of active classes when q.qlen drops to zero in ->drop()
> 
> - purging of queue and deactivating of active leaf classes
>   when attaching a new child (presuming CBQ can only carry
>   packets in leaf classes, I'm not sure about this)
> 
> and something HTB should do is to turn intermediate classes
> into leaves again when their last child is deleted.
> 
> Are you interested in fixing this? :)
 
Maybe someday I'll be capable enough! It looks
complicated enough to have some fun. At present
I don't even know how to use it... But I think,
you are just in the subject, so it would be at
least one point less for the future.

Jarek P.

Re: [NET_SCHED 04/06]: Fix endless loops (part 2): "simple" qdiscs

[Jarek Poplawski]

On Fri, Nov 24, 2006 at 02:07:08PM +0100, Patrick McHardy wrote:
> Jarek Poplawski wrote:
...
> > Probably it is as usual something with my eyes but
> > it seems cbq needs in cbq_delete or cbq_destroy_class
> > some treatment (about qdisc_destroy) similar to htb.
> 
> No, you're right about this one, CBQ needs a few further fixes:
> 
> - deactivating of active classes when grafting
> 
> - purging of queue/q.qlen adjustment when deleting an active class
> 
> - deactivating of active classes when q.qlen drops to zero in ->drop()
> 
> - purging of queue and deactivating of active leaf classes
>   when attaching a new child (presuming CBQ can only carry
>   packets in leaf classes, I'm not sure about this)
> 
> and something HTB should do is to turn intermediate classes
> into leaves again when their last child is deleted.
> 
> Are you interested in fixing this? :)

Oops! Sorry, I missed it again!

I've been frightened by the fame of cbq complexity
and I've simply never used it.
But after checking this points look rather trivial
so I've tried.

I'll soon send two patches proposals as separate
threads. The bad thing is I didn't have time to test 
or even learn how to test cbq, so I hope somebody
else would do it.

If any reworking will be needed or patching against
another version, let me know.

If you find it could be usable I'll be glad to do
more things like this. I'll also try to look closer
on cbq.

Regards,

Jarek P.

Re: [NET_SCHED 04/06]: Fix endless loops (part 2): "simple" qdiscs

[David Miller]

From: Patrick McHardy <kaber@trash.net>
Date: Mon, 20 Nov 2006 14:08:44 +0100 (MET)

> [NET_SCHED]: Fix endless loops (part 2): "simple" qdiscs
> 
> Convert the "simple" qdiscs to use qdisc_tree_decrease_qlen() where
> necessary:
> 
> - all graft operations
> - destruction of old child qdiscs in prio, red and tbf change operation
> - purging of queue in sfq change operation
> 
> Signed-off-by: Patrick McHardy <kaber@trash.net>

Applied to net-2.6.20

[NET_SCHED 05/06]: Fix endless loops (part 3): HFSC

[Patrick McHardy]

[NET_SCHED]: Fix endless loops (part 3): HFSC

Convert HFSC to use qdisc_tree_decrease_len() and add a callback
for deactivating a class when its child queue becomes empty.

All queue purging goes through hfsc_purge_queue(), which is used in
three cases: grafting, class creation (when a leaf class is turned
into an intermediate class by attaching a new class) and class
deletion. In all cases qdisc_tree_decrease_len() is needed.

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

---
commit 62ab4431af7bccd0a8cd9b1933fb03e78fd63252
tree 79911d570a56ac3752790808ae8139983253524a
parent 0ce9475d7baf678698eb70369f734b8feeb03e13
author Patrick McHardy <kaber@trash.net> Mon, 20 Nov 2006 13:46:23 +0100
committer Patrick McHardy <kaber@trash.net> Mon, 20 Nov 2006 13:46:23 +0100

 net/sched/sch_hfsc.c |   18 +++++++++++++-----
 1 files changed, 13 insertions(+), 5 deletions(-)

diff --git a/net/sched/sch_hfsc.c b/net/sched/sch_hfsc.c
index 1142d29..2d43744 100644
--- a/net/sched/sch_hfsc.c
+++ b/net/sched/sch_hfsc.c
@@ -957,11 +957,7 @@ hfsc_purge_queue(struct Qdisc *sch, stru
 	unsigned int len = cl->qdisc->q.qlen;
 
 	qdisc_reset(cl->qdisc);
-	if (len > 0) {
-		update_vf(cl, 0, 0);
-		set_passive(cl);
-		sch->q.qlen -= len;
-	}
+	qdisc_tree_decrease_qlen(cl->qdisc, len);
 }
 
 static void
@@ -1295,6 +1291,17 @@ hfsc_class_leaf(struct Qdisc *sch, unsig
 	return NULL;
 }
 
+static void
+hfsc_qlen_notify(struct Qdisc *sch, unsigned long arg)
+{
+	struct hfsc_class *cl = (struct hfsc_class *)arg;
+
+	if (cl->qdisc->q.qlen == 0) {
+		update_vf(cl, 0, 0);
+		set_passive(cl);
+	}
+}
+
 static unsigned long
 hfsc_get_class(struct Qdisc *sch, u32 classid)
 {
@@ -1779,6 +1786,7 @@ static struct Qdisc_class_ops hfsc_class
 	.delete		= hfsc_delete_class,
 	.graft		= hfsc_graft_class,
 	.leaf		= hfsc_class_leaf,
+	.qlen_notify	= hfsc_qlen_notify,
 	.get		= hfsc_get_class,
 	.put		= hfsc_put_class,
 	.bind_tcf	= hfsc_bind_tcf,

Re: [NET_SCHED 05/06]: Fix endless loops (part 3): HFSC

[David Miller]

From: Patrick McHardy <kaber@trash.net>
Date: Mon, 20 Nov 2006 14:08:46 +0100 (MET)

> [NET_SCHED]: Fix endless loops (part 3): HFSC
> 
> Convert HFSC to use qdisc_tree_decrease_len() and add a callback
> for deactivating a class when its child queue becomes empty.
> 
> All queue purging goes through hfsc_purge_queue(), which is used in
> three cases: grafting, class creation (when a leaf class is turned
> into an intermediate class by attaching a new class) and class
> deletion. In all cases qdisc_tree_decrease_len() is needed.
> 
> Signed-off-by: Patrick McHardy <kaber@trash.net>

Applied to net-2.6.20, thanks.

[NET_SCHED 06/06]: Fix endless loops (part 4): HTB

[Patrick McHardy]

[NET_SCHED]: Fix endless loops (part 4): HTB

Convert HTB to use qdisc_tree_decrease_len() and add a callback
for deactivating a class when its child queue becomes empty.

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

---
commit cc6f4de81d666f76192bee629473ff6fbd66286c
tree 237aa915ea3b619fb817e719821bb0667e19eafd
parent 62ab4431af7bccd0a8cd9b1933fb03e78fd63252
author Patrick McHardy <kaber@trash.net> Mon, 20 Nov 2006 13:50:11 +0100
committer Patrick McHardy <kaber@trash.net> Mon, 20 Nov 2006 13:50:11 +0100

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

diff --git a/net/sched/sch_htb.c b/net/sched/sch_htb.c
index 3b36e9d..215e68c 100644
--- a/net/sched/sch_htb.c
+++ b/net/sched/sch_htb.c
@@ -1230,11 +1230,7 @@ static int htb_graft(struct Qdisc *sch, 
 			return -ENOBUFS;
 		sch_tree_lock(sch);
 		if ((*old = xchg(&cl->un.leaf.q, new)) != NULL) {
-			if (cl->prio_activity)
-				htb_deactivate(qdisc_priv(sch), cl);
-
-			/* TODO: is it correct ? Why CBQ doesn't do it ? */
-			sch->q.qlen -= (*old)->q.qlen;
+			qdisc_tree_decrease_qlen(*old, (*old)->q.qlen);
 			qdisc_reset(*old);
 		}
 		sch_tree_unlock(sch);
@@ -1249,6 +1245,14 @@ static struct Qdisc *htb_leaf(struct Qdi
 	return (cl && !cl->level) ? cl->un.leaf.q : NULL;
 }
 
+static void htb_qlen_notify(struct Qdisc *sch, unsigned long arg)
+{
+	struct htb_class *cl = (struct htb_class *)arg;
+
+	if (cl->un.leaf.q->q.qlen == 0)
+		htb_deactivate(qdisc_priv(sch), cl);
+}
+
 static unsigned long htb_get(struct Qdisc *sch, u32 classid)
 {
 	struct htb_class *cl = htb_find(classid, sch);
@@ -1323,6 +1327,7 @@ static int htb_delete(struct Qdisc *sch,
 {
 	struct htb_sched *q = qdisc_priv(sch);
 	struct htb_class *cl = (struct htb_class *)arg;
+	unsigned int qlen;
 
 	// TODO: why don't allow to delete subtree ? references ? does
 	// tc subsys quarantee us that in htb_destroy it holds no class
@@ -1336,8 +1341,9 @@ static int htb_delete(struct Qdisc *sch,
 	hlist_del_init(&cl->hlist);
 
 	if (!cl->level) {
-		sch->q.qlen -= cl->un.leaf.q->q.qlen;
+		qlen = cl->un.leaf.q->q.qlen;
 		qdisc_reset(cl->un.leaf.q);
+		qdisc_tree_decrease_qlen(cl->un.leaf.q, qlen);
 	}
 
 	if (cl->prio_activity)
@@ -1419,8 +1425,11 @@ static int htb_change_class(struct Qdisc
 		new_q = qdisc_create_dflt(sch->dev, &pfifo_qdisc_ops, classid);
 		sch_tree_lock(sch);
 		if (parent && !parent->level) {
+			unsigned int qlen = parent->un.leaf.q->q.qlen;
+
 			/* turn parent into inner node */
-			sch->q.qlen -= parent->un.leaf.q->q.qlen;
+			qdisc_reset(parent->un.leaf.q);
+			qdisc_tree_decrease_qlen(parent->un.leaf.q, qlen);
 			qdisc_destroy(parent->un.leaf.q);
 			if (parent->prio_activity)
 				htb_deactivate(q, parent);
@@ -1568,6 +1577,7 @@ static void htb_walk(struct Qdisc *sch, 
 static struct Qdisc_class_ops htb_class_ops = {
 	.graft		=	htb_graft,
 	.leaf		=	htb_leaf,
+	.qlen_notify	=	htb_qlen_notify,
 	.get		=	htb_get,
 	.put		=	htb_put,
 	.change		=	htb_change_class,

Re: [NET_SCHED 06/06]: Fix endless loops (part 4): HTB

[Martin Devera]

Patrick McHardy wrote:

 > Martin, can you please review the HTB parts?

it seems all right to me :-) Good work!

--------- snip ---------

[NET_SCHED]: Fix endless loops (part 4): HTB

Convert HTB to use qdisc_tree_decrease_len() and add a callback
for deactivating a class when its child queue becomes empty.

Signed-off-by: Patrick McHardy <kaber@trash.net>
Acked-by: Martin Devera <devik@cdi.cz>

---
commit cc6f4de81d666f76192bee629473ff6fbd66286c
tree 237aa915ea3b619fb817e719821bb0667e19eafd
parent 62ab4431af7bccd0a8cd9b1933fb03e78fd63252
author Patrick McHardy <kaber@trash.net> Mon, 20 Nov 2006 13:50:11 +0100
committer Patrick McHardy <kaber@trash.net> Mon, 20 Nov 2006 13:50:11 +0100

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

diff --git a/net/sched/sch_htb.c b/net/sched/sch_htb.c
index 3b36e9d..215e68c 100644
--- a/net/sched/sch_htb.c
+++ b/net/sched/sch_htb.c
@@ -1230,11 +1230,7 @@ static int htb_graft(struct Qdisc *sch,
  			return -ENOBUFS;
  		sch_tree_lock(sch);
  		if ((*old = xchg(&cl->un.leaf.q, new)) != NULL) {
-			if (cl->prio_activity)
-				htb_deactivate(qdisc_priv(sch), cl);
-
-			/* TODO: is it correct ? Why CBQ doesn't do it ? */
-			sch->q.qlen -= (*old)->q.qlen;
+			qdisc_tree_decrease_qlen(*old, (*old)->q.qlen);
  			qdisc_reset(*old);
  		}
  		sch_tree_unlock(sch);
@@ -1249,6 +1245,14 @@ static struct Qdisc *htb_leaf(struct Qdi
  	return (cl && !cl->level) ? cl->un.leaf.q : NULL;
  }

+static void htb_qlen_notify(struct Qdisc *sch, unsigned long arg)
+{
+	struct htb_class *cl = (struct htb_class *)arg;
+
+	if (cl->un.leaf.q->q.qlen == 0)
+		htb_deactivate(qdisc_priv(sch), cl);
+}
+
  static unsigned long htb_get(struct Qdisc *sch, u32 classid)
  {
  	struct htb_class *cl = htb_find(classid, sch);
@@ -1323,6 +1327,7 @@ static int htb_delete(struct Qdisc *sch,
  {
  	struct htb_sched *q = qdisc_priv(sch);
  	struct htb_class *cl = (struct htb_class *)arg;
+	unsigned int qlen;

  	// TODO: why don't allow to delete subtree ? references ? does
  	// tc subsys quarantee us that in htb_destroy it holds no class
@@ -1336,8 +1341,9 @@ static int htb_delete(struct Qdisc *sch,
  	hlist_del_init(&cl->hlist);

  	if (!cl->level) {
-		sch->q.qlen -= cl->un.leaf.q->q.qlen;
+		qlen = cl->un.leaf.q->q.qlen;
  		qdisc_reset(cl->un.leaf.q);
+		qdisc_tree_decrease_qlen(cl->un.leaf.q, qlen);
  	}

  	if (cl->prio_activity)
@@ -1419,8 +1425,11 @@ static int htb_change_class(struct Qdisc
  		new_q = qdisc_create_dflt(sch->dev, &pfifo_qdisc_ops, classid);
  		sch_tree_lock(sch);
  		if (parent && !parent->level) {
+			unsigned int qlen = parent->un.leaf.q->q.qlen;
+
  			/* turn parent into inner node */
-			sch->q.qlen -= parent->un.leaf.q->q.qlen;
+			qdisc_reset(parent->un.leaf.q);
+			qdisc_tree_decrease_qlen(parent->un.leaf.q, qlen);
  			qdisc_destroy(parent->un.leaf.q);
  			if (parent->prio_activity)
  				htb_deactivate(q, parent);
@@ -1568,6 +1577,7 @@ static void htb_walk(struct Qdisc *sch,
  static struct Qdisc_class_ops htb_class_ops = {
  	.graft		=	htb_graft,
  	.leaf		=	htb_leaf,
+	.qlen_notify	=	htb_qlen_notify,
  	.get		=	htb_get,
  	.put		=	htb_put,
  	.change		=	htb_change_class,

Re: [NET_SCHED 06/06]: Fix endless loops (part 4): HTB

[Jarek Poplawski]

On 20-11-2006 14:08, Patrick McHardy wrote:
> [NET_SCHED]: Fix endless loops (part 4): HTB
> 
> Convert HTB to use qdisc_tree_decrease_len() and add a callback
> for deactivating a class when its child queue becomes empty.
> 
> Signed-off-by: Patrick McHardy <kaber@trash.net>
> 
> ---
... 
> diff --git a/net/sched/sch_htb.c b/net/sched/sch_htb.c
> index 3b36e9d..215e68c 100644
> --- a/net/sched/sch_htb.c
> +++ b/net/sched/sch_htb.c
> @@ -1230,11 +1230,7 @@ static int htb_graft(struct Qdisc *sch, 
>  			return -ENOBUFS;
>  		sch_tree_lock(sch);
>  		if ((*old = xchg(&cl->un.leaf.q, new)) != NULL) {
> -			if (cl->prio_activity)
> -				htb_deactivate(qdisc_priv(sch), cl);
> -
> -			/* TODO: is it correct ? Why CBQ doesn't do it ? */
> -			sch->q.qlen -= (*old)->q.qlen;
> +			qdisc_tree_decrease_qlen(*old, (*old)->q.qlen);
>  			qdisc_reset(*old);
>  		}
>  		sch_tree_unlock(sch);
> @@ -1249,6 +1245,14 @@ static struct Qdisc *htb_leaf(struct Qdi
>  	return (cl && !cl->level) ? cl->un.leaf.q : NULL;
>  }
>  
> +static void htb_qlen_notify(struct Qdisc *sch, unsigned long arg)
> +{
> +	struct htb_class *cl = (struct htb_class *)arg;
> +
> +	if (cl->un.leaf.q->q.qlen == 0)

Probably "if (cl->prio_activity)" is needed here.

> +		htb_deactivate(qdisc_priv(sch), cl);
> +}
> +

Regards,

Jarek P.

PS: from 00/06:
> PS: If anyone wants to suggest a nicer name for qdisc_tree_decrease_qlen
> I'll gladly send new patches :)

Increasing is nicer so maybe: qdisc_tree_increase_qlen?

Re: [NET_SCHED 06/06]: Fix endless loops (part 4): HTB

[Patrick McHardy]

Jarek Poplawski wrote:
>>+static void htb_qlen_notify(struct Qdisc *sch, unsigned long arg)
>>+{
>>+	struct htb_class *cl = (struct htb_class *)arg;
>>+
>>+	if (cl->un.leaf.q->q.qlen == 0)
> 
> 
> Probably "if (cl->prio_activity)" is needed here.


No, the function is only called for active leaf classes, which
always have prio_activity != 0.

> PS: from 00/06:
> 
>>PS: If anyone wants to suggest a nicer name for qdisc_tree_decrease_qlen
>>I'll gladly send new patches :)
> 
> 
> Increasing is nicer so maybe: qdisc_tree_increase_qlen?


But we're decreasing not increasing the qlen, so that doesn't seem
like a good choice :)

Re: [NET_SCHED 06/06]: Fix endless loops (part 4): HTB

[Jarek Poplawski]

On Thu, Nov 23, 2006 at 09:44:04AM +0100, Patrick McHardy wrote:
> Jarek Poplawski wrote:
> >>+static void htb_qlen_notify(struct Qdisc *sch, unsigned long arg)
> >>+{
> >>+	struct htb_class *cl = (struct htb_class *)arg;
> >>+
> >>+	if (cl->un.leaf.q->q.qlen == 0)
> > 
> > 
> > Probably "if (cl->prio_activity)" is needed here.
> 
> 
> No, the function is only called for active leaf classes, which
> always have prio_activity != 0.

So this was unnecessary in htb_graft? You should know better...

Jarek P. 

Re: [NET_SCHED 06/06]: Fix endless loops (part 4): HTB

[Patrick McHardy]

Jarek Poplawski wrote:
> On Thu, Nov 23, 2006 at 09:44:04AM +0100, Patrick McHardy wrote:
> 
>>Jarek Poplawski wrote:
>>
>>>>+static void htb_qlen_notify(struct Qdisc *sch, unsigned long arg)
>>>>+{
>>>>+	struct htb_class *cl = (struct htb_class *)arg;
>>>>+
>>>>+	if (cl->un.leaf.q->q.qlen == 0)
>>>
>>>
>>>Probably "if (cl->prio_activity)" is needed here.
>>
>>
>>No, the function is only called for active leaf classes, which
>>always have prio_activity != 0.
> 
> 
> So this was unnecessary in htb_graft? You should know better...

In htb_graft it was necessary because the class could be
either active (qlen > 0) or inactive (qlen == 0). But since
qdisc_tree_decrease_qlen does nothing in case of a decrease
of zero the callback is only called for active classes and
the check becomes unnecessary.

Re: [NET_SCHED 06/06]: Fix endless loops (part 4): HTB

[Martin Devera]

>>>>> +{
>>>>> +	struct htb_class *cl = (struct htb_class *)arg;
>>>>> +
>>>>> +	if (cl->un.leaf.q->q.qlen == 0)
>>>>
>>>> Probably "if (cl->prio_activity)" is needed here.
>>>
>>> No, the function is only called for active leaf classes, which
>>> always have prio_activity != 0.
>>
>> So this was unnecessary in htb_graft? You should know better...
> 
> In htb_graft it was necessary because the class could be
> either active (qlen > 0) or inactive (qlen == 0). But since
> qdisc_tree_decrease_qlen does nothing in case of a decrease
> of zero the callback is only called for active classes and
> the check becomes unnecessary.
> 

Patrick is right here. prio_activity for leaf is set in htb's enqueue
routines. The qlen callback is called when len changed and because
that zero test in htb's callback it is sure the subclass was nonempty
before.
The only problem might be if some subqdisc "creates" new packets,
then htb might deactivate non-active class (leading to BUG()).
IIRC no qdisc does it...
devik

Re: [NET_SCHED 06/06]: Fix endless loops (part 4): HTB

[Patrick McHardy]

Martin Devera wrote:
>> In htb_graft it was necessary because the class could be
>> either active (qlen > 0) or inactive (qlen == 0). But since
>> qdisc_tree_decrease_qlen does nothing in case of a decrease
>> of zero the callback is only called for active classes and
>> the check becomes unnecessary.
>>
> 
> Patrick is right here. prio_activity for leaf is set in htb's enqueue
> routines. The qlen callback is called when len changed and because
> that zero test in htb's callback it is sure the subclass was nonempty
> before.

BTW, I plan to remove the check for empty child qdiscs in
htb_dequeue_tree and the check for prio_activity after the
calls to qdisc_tree_decrease_len in htb_change_class as a
follow-up patch in 2.6.20, for now I kept them to be safe.

> The only problem might be if some subqdisc "creates" new packets,
> then htb might deactivate non-active class (leading to BUG()).
> IIRC no qdisc does it...

netem can duplicate packets, but it enqueues them at the root,
so it shouldn't be a problem. It might be preferable to do
something similar to qdisc_tree_decrease_qlen in that case to
make sure the packet really ends up in the netem qdisc, but for
now I just wanted to fix the endless loops.

Re: [NET_SCHED 06/06]: Fix endless loops (part 4): HTB

[Jarek Poplawski]

On Thu, Nov 23, 2006 at 10:32:27AM +0100, Martin Devera wrote:
> >>>>>+{
> >>>>>+	struct htb_class *cl = (struct htb_class *)arg;
> >>>>>+
> >>>>>+	if (cl->un.leaf.q->q.qlen == 0)
> >>>>
> >>>>Probably "if (cl->prio_activity)" is needed here.
> >>>
> >>>No, the function is only called for active leaf classes, which
> >>>always have prio_activity != 0.
> >>
> >>So this was unnecessary in htb_graft? You should know better...
> >
> >In htb_graft it was necessary because the class could be
> >either active (qlen > 0) or inactive (qlen == 0). But since
> >qdisc_tree_decrease_qlen does nothing in case of a decrease
> >of zero the callback is only called for active classes and
> >the check becomes unnecessary.
> >
> 
> Patrick is right here. prio_activity for leaf is set in htb's enqueue
> routines. The qlen callback is called when len changed and because
> that zero test in htb's callback it is sure the subclass was nonempty
> before.
> The only problem might be if some subqdisc "creates" new packets,
> then htb might deactivate non-active class (leading to BUG()).
> IIRC no qdisc does it...
> devik

I'm learning htb yet and was not sure whether leaf class
with non-zero qlen qdisc couldn't be deactivated for some
other reason. In such case the patch would change
"functionality", so my doubts.

Thanks very much for explanations to both authors of great
schedulers.

I'm very honored,

Jarek P. 

Re: [NET_SCHED 06/06]: Fix endless loops (part 4): HTB

[David Miller]

From: Patrick McHardy <kaber@trash.net>
Date: Mon, 20 Nov 2006 14:08:48 +0100 (MET)

> [NET_SCHED]: Fix endless loops (part 4): HTB
> 
> Convert HTB to use qdisc_tree_decrease_len() and add a callback
> for deactivating a class when its child queue becomes empty.
> 
> Signed-off-by: Patrick McHardy <kaber@trash.net>

Applied to net-2.6.20