Skip to contentSkip to conversation

: Fix endless dequeue loops

PATCH Applied Patrick McHardy 5 participants 31 messages Nov 20, 2006 – Nov 30, 2006

Subsystems (4)
lore
Share & tools
lore
#0 lore raw

cover : Fix endless dequeue loops

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

#1 lore raw

PATCH 1/6 : sch_htb: perform qlen adjustment immediately in ->delete

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

---
commit 28ceb9f1cece3e1fa989a96a99dc76dc44d5629b
tree 568ab7acb7b9c6d1783c5e4a23edd83ee0381e22
parent 808dbbb6bb61173bf52946a28f99089d2efa4c55
author Patrick McHardy <[email protected]> Sun, 19 Nov 2006 06:55:10 +0100 committer Patrick McHardy <[email protected]> Sun, 19 Nov 2006 06:55:10 +0100

 net/sched/sch_htb.c |    7 ++++++-
 1 files changed, 6 insertions(+), 1 deletions(-)
net/sched/sch_htb.c +6 -1
index 4b52fa7..08fa4d0 100644
@@ -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);
 
maintainer Applied
#2 lore raw

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

From: Patrick McHardy <[email protected]>
Date: Mon, 20 Nov 2006 14:08:37 +0100 (MET)

Quoted 9 lines

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

Applied to net-2.6.20

#3 lore raw

PATCH 2/6 : Set parent classid in default qdiscs

In reply to 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.

---
commit 825dfe1f03e69f3c2b56e6bd6ceea7ffe23c65bf
tree 28592aa602dcd936add9fb2851c97c5a603dda85
parent 28ceb9f1cece3e1fa989a96a99dc76dc44d5629b
author Patrick McHardy <[email protected]> Mon, 20 Nov 2006 13:42:53 +0100 committer Patrick McHardy <[email protected]> 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(-)
include/net/sch_generic.h +1 -1
index b0e9108..660ff0a 100644
@@ -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)
net/sched/sch_atm.c +3 -2
index dbf44da..edc7bb0 100644
@@ -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;
net/sched/sch_cbq.c +5 -3
index bac881b..908b10d 100644
@@ -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;
net/sched/sch_dsmark.c +3 -2
index 11c8a21..7809073 100644
@@ -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;
 
net/sched/sch_generic.c +5 -2
index 88c6a99..deafeb9 100644
@@ -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;
net/sched/sch_hfsc.c +5 -3
index 6a6735a..1142d29 100644
@@ -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;
net/sched/sch_htb.c +4 -3
index 08fa4d0..3b36e9d 100644
@@ -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 */
net/sched/sch_netem.c +2 -1
index 0441876..90aeeb7 100644
@@ -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;
net/sched/sch_prio.c +2 -1
index a5fa03c..3fc0c0f 100644
@@ -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);
net/sched/sch_red.c +5 -3
index d65cadd..ee66c5c 100644
@@ -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;
 	}
net/sched/sch_tbf.c +5 -3
index d9a5d29..2562a60 100644
@@ -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;
 	}
 
maintainer Applied
#4 lore raw

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

From: Patrick McHardy <[email protected]>
Date: Mon, 20 Nov 2006 14:08:38 +0100 (MET)

Quoted 6 lines

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

Applied to net-2.6.20, thanks Patrick.

#5 lore raw

PATCH 3/6 : Fix endless loops caused by inaccurate qlen counters (part 1)

In reply to 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 <[email protected]>.

---
commit 42706d154c660ac3915cc0debcfa09339af29de3
tree 26dd1060dcfd2d0633d63297bb4f988d5f6c8ea8
parent 825dfe1f03e69f3c2b56e6bd6ceea7ffe23c65bf
author Patrick McHardy <[email protected]> Mon, 20 Nov 2006 13:44:49 +0100 committer Patrick McHardy <[email protected]> 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(-)
include/net/sch_generic.h +2 -0
index 660ff0a..d61fb67 100644
@@ -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);
net/sched/sch_api.c +32 -6
index 0b64892..1c3c779 100644
@@ -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".
#6 lore raw

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

Quoted 17 lines
net/sched/sch_api.c +12 -0
@@ -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) {

net/sched/sch_api.c dev_graft_qdisc(struct net_device *dev, · line 378

Quoted 10 lines
net/sched/sch_api.c +8 -0
+			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

#7 lore raw

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

net/sched/sch_api.c dev_graft_qdisc(struct net_device *dev,

Quoted 6 lines · Mika Penttilä

Are you sure you didn't mean to :

net/sched/sch_api.c +4 -0
+    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.

#8 lore raw

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

Quoted 11 lines · Patrick McHardy

net/sched/sch_api.c dev_graft_qdisc(struct net_device *dev,

Quoted 7 lines · Mika Penttilä

Are you sure you didn't mean to :

net/sched/sch_api.c +4 -0
+    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) {    <----
Quoted 6 lines

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

#9 lore raw

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

Quoted 15 lines · Mika Penttilä
Quoted 13 lines · Patrick McHardy
Quoted 7 lines · Mika Penttilä

Are you sure you didn't mean to :

net/sched/sch_api.c +4 -0
+    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) {    <----
Quoted 8 lines
Quoted 6 lines

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.

#10 lore raw

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

Quoted 29 lines · Patrick McHardy
Quoted 16 lines · Mika Penttilä
Quoted 13 lines · Patrick McHardy
Quoted 8 lines · Mika Penttilä

Are you sure you didn't mean to :

net/sched/sch_api.c +4 -0
+    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) {    <----
Quoted 9 lines
Quoted 7 lines

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

Quoted 8 lines

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

#11 lore raw

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

Quoted 11 lines · Mika Penttilä
Quoted 6 lines · Patrick McHardy

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.

Quoted 2 lines

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.

maintainer Applied
#12 lore raw

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

In reply to Patrick McHardy

From: Patrick McHardy <[email protected]>
Date: Mon, 20 Nov 2006 14:08:41 +0100 (MET)

Quoted 14 lines

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

Quoted 8 lines

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 <[email protected]>.

Applied to net-2.6.20, thanks a lot.

#13 lore raw

PATCH 4/6 : Fix endless loops (part 2): "simple" qdiscs

In reply to 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

---
commit 0ce9475d7baf678698eb70369f734b8feeb03e13
tree de989fa5b32c7f53e7b7b6aac686dc39bb1839bb
parent 42706d154c660ac3915cc0debcfa09339af29de3
author Patrick McHardy <[email protected]> Mon, 20 Nov 2006 13:45:41 +0100 committer Patrick McHardy <[email protected]> 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(-)
net/sched/sch_cbq.c +1 -1
index 908b10d..ba82dfa 100644
@@ -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);
 
net/sched/sch_dsmark.c +1 -1
index 7809073..e341fd9 100644
@@ -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;
net/sched/sch_netem.c +1 -1
index 90aeeb7..672c354 100644
@@ -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;
net/sched/sch_prio.c +8 -3
index 3fc0c0f..2567b4c 100644
@@ -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);
 
net/sched/sch_red.c +4 -2
index ee66c5c..acddad0 100644
@@ -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;
 }
net/sched/sch_sfq.c +3 -0
index d0d6e59..459cda2 100644
@@ -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) {
net/sched/sch_tbf.c +4 -2
index 2562a60..23b7624 100644
@@ -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;
#14 lore raw

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

Quoted 12 lines · 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

---

...

Quoted 1 line
 net/sched/sch_cbq.c    |    2 +-

...

net/sched/sch_cbq.c #endif · line 1693

Quoted 13 lines
net/sched/sch_cbq.c +1 -1
index 908b10d..ba82dfa 100644
@@ -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.

#15 lore raw

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

Quoted 17 lines · Jarek Poplawski

net/sched/sch_cbq.c #endif · line 1693

Quoted 13 lines
net/sched/sch_cbq.c +1 -1
index 908b10d..ba82dfa 100644
@@ -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,

Quoted 3 lines

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? :)

#16 lore raw

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

Quoted 1 line · Patrick McHardy

Jarek Poplawski wrote:

...

Quoted 12 lines
Quoted 3 lines

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()

Quoted 8 lines

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

#17 lore raw

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

In reply to Patrick McHardy
Quoted 1 line · Patrick McHardy

Jarek Poplawski wrote:

...

Quoted 12 lines
Quoted 3 lines

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()

Quoted 8 lines

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

maintainer Applied
#18 lore raw

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

In reply to Patrick McHardy

From: Patrick McHardy <[email protected]>
Date: Mon, 20 Nov 2006 14:08:44 +0100 (MET)

Quoted 10 lines

[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

Applied to net-2.6.20

#19 lore raw

PATCH 5/6 : Fix endless loops (part 3): HFSC

In reply to 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.

---
commit 62ab4431af7bccd0a8cd9b1933fb03e78fd63252
tree 79911d570a56ac3752790808ae8139983253524a
parent 0ce9475d7baf678698eb70369f734b8feeb03e13
author Patrick McHardy <[email protected]> Mon, 20 Nov 2006 13:46:23 +0100 committer Patrick McHardy <[email protected]> Mon, 20 Nov 2006 13:46:23 +0100

 net/sched/sch_hfsc.c |   18 +++++++++++++-----
 1 files changed, 13 insertions(+), 5 deletions(-)
net/sched/sch_hfsc.c +13 -5
index 1142d29..2d43744 100644
@@ -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,
maintainer Applied
#20 lore raw

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

From: Patrick McHardy <[email protected]>
Date: Mon, 20 Nov 2006 14:08:46 +0100 (MET)

Quoted 11 lines

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

Applied to net-2.6.20, thanks.

#21 lore raw

PATCH 6/6 : Fix endless loops (part 4): HTB

In reply to 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.

---
commit cc6f4de81d666f76192bee629473ff6fbd66286c
tree 237aa915ea3b619fb817e719821bb0667e19eafd
parent 62ab4431af7bccd0a8cd9b1933fb03e78fd63252
author Patrick McHardy <[email protected]> Mon, 20 Nov 2006 13:50:11 +0100 committer Patrick McHardy <[email protected]> Mon, 20 Nov 2006 13:50:11 +0100

 net/sched/sch_htb.c |   24 +++++++++++++++++-------
 1 files changed, 17 insertions(+), 7 deletions(-)
net/sched/sch_htb.c +17 -7
index 3b36e9d..215e68c 100644
@@ -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,
Acked-by on v1 6/6
#22 lore raw

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

Quoted 1 line · Patrick McHardy

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.

---
commit cc6f4de81d666f76192bee629473ff6fbd66286c
tree 237aa915ea3b619fb817e719821bb0667e19eafd
parent 62ab4431af7bccd0a8cd9b1933fb03e78fd63252
author Patrick McHardy <[email protected]> Mon, 20 Nov 2006 13:50:11 +0100 committer Patrick McHardy <[email protected]> Mon, 20 Nov 2006 13:50:11 +0100

 net/sched/sch_htb.c |   24 +++++++++++++++++-------
 1 files changed, 17 insertions(+), 7 deletions(-)
net/sched/sch_htb.c +17 -7
index 3b36e9d..215e68c 100644
@@ -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,
#23 lore raw

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

In reply to Patrick McHardy
Quoted 8 lines · 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.

---

...

Quoted 18 lines
net/sched/sch_htb.c +1 -5
index 3b36e9d..215e68c 100644
@@ -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);

net/sched/sch_htb.c static struct Qdisc *htb_leaf(struct Qdi · line 1252

Quoted 8 lines
net/sched/sch_htb.c +5 -0
@@ -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.

net/sched/sch_htb.c static struct Qdisc *htb_leaf(struct Qdi · line 1255

Quoted 3 lines
net/sched/sch_htb.c +3 -0
+		htb_deactivate(qdisc_priv(sch), cl);
+}
+

Regards,

Jarek P.

PS: from 00/06:

Quoted 2 lines

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?

#24 lore raw

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

Quoted 8 lines · Jarek Poplawski

net/sched/sch_htb.c static struct Qdisc *htb_leaf(struct Qdi · line 1252

Quoted 5 lines
net/sched/sch_htb.c +5 -0
+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.

Quoted 7 lines

PS: from 00/06:

Quoted 2 lines

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 :)

#25 lore raw

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

Quoted 11 lines · Patrick McHardy
Quoted 8 lines · Jarek Poplawski

net/sched/sch_htb.c static struct Qdisc *htb_leaf(struct Qdi · line 1252

Quoted 5 lines
net/sched/sch_htb.c +5 -0
+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.

Quoted 2 lines

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.

#26 lore raw

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

Quoted 14 lines · Jarek Poplawski
Quoted 12 lines · Patrick McHardy
Quoted 8 lines · Jarek Poplawski

net/sched/sch_htb.c static struct Qdisc *htb_leaf(struct Qdi · line 1252

Quoted 5 lines
net/sched/sch_htb.c +5 -0
+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.

Quoted 5 lines
Quoted 2 lines

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.

#27 lore raw

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

Quoted 10 lines
Quoted 10 lines
Quoted 9 lines
Quoted 6 lines

net/sched/sch_htb.c static struct Qdisc *htb_leaf(struct Qdi · line 1252

Quoted 4 lines
net/sched/sch_htb.c +4 -0
+{
+	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.

Quoted 8 lines
Quoted 1 line

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

#28 lore raw

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

Quoted 11 lines · Martin Devera
Quoted 6 lines

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.

Quoted 3 lines

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.

#29 lore raw

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

In reply to Martin Devera
Quoted 19 lines · Martin Devera
Quoted 10 lines
Quoted 10 lines
Quoted 9 lines
Quoted 6 lines

net/sched/sch_htb.c static struct Qdisc *htb_leaf(struct Qdi · line 1252

Quoted 4 lines
net/sched/sch_htb.c +4 -0
+{
+	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.

Quoted 8 lines
Quoted 1 line

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.

Quoted 8 lines

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.