: Fix endless dequeue loops
Subsystems (4)
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
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
@@ -1269,9 +1269,9 @@ static void htb_destroy_filters(struct tstatic 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
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 ->deleteqlen adjustment should happen immediately in ->delete and not in the class destroy function because the reference count will not hit zero in ->delete (
sch_apiholds 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 <[email protected]>
Applied to net-2.6.20
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
@@ -174,7 +174,7 @@ extern void qdisc_reset(struct Qdisc *qdextern 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
@@ -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 *schDPRINTK ("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
@@ -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
@@ -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
@@ -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 *devif (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
@@ -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, unsiif (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
@@ -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
@@ -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
@@ -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
@@ -175,12 +175,14 @@ static void red_destroy(struct Qdisc *scqdisc_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
@@ -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
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 qdiscsSet 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 <[email protected]>
Applied to net-2.6.20, thanks Patrick.
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
@@ -60,6 +60,7 @@ struct Qdisc_class_opsint (*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_deviextern 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
@@ -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)
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
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.
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
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.
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
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_lookupbe 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)
In reply to Patrick McHardyFrom: 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]>.
Signed-off-by Patrick McHardy <[email protected]>
Applied to net-2.6.20, thanks a lot.
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
@@ -1687,7 +1687,7 @@ #endifsch_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
@@ -96,8 +96,8 @@ static int dsmark_graft(struct Qdisc *scsch_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
@@ -662,8 +662,8 @@ static int netem_graft(struct Qdisc *schsch_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
@@ -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
@@ -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
@@ -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
@@ -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
Quoted 12 lines · Patrick McHardy
[
NET_SCHED]: Fix endless loops (part 2): "simple" qdiscsConvert 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 operationSigned-off-by Patrick McHardy <[email protected]>---
...
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@@ -1687,7 +1687,7 @@ #endifsch_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
Quoted 17 lines · Jarek Poplawski
net/sched/sch_cbq.c #endif · line 1693
Quoted 13 lines
net/sched/sch_cbq.c +1
-1@@ -1687,7 +1687,7 @@ #endifsch_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_deleteorcbq_destroy_classsome treatment (aboutqdisc_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
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_deleteorcbq_destroy_classsome treatment (aboutqdisc_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.
Re: [NET_SCHED 04/06]: Fix endless loops (part 2): "simple" qdiscs
In reply to Patrick McHardyQuoted 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_deleteorcbq_destroy_classsome treatment (aboutqdisc_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.
Re: [NET_SCHED 04/06]: Fix endless loops (part 2): "simple" qdiscs
In reply to Patrick McHardyFrom: 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" qdiscsConvert 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 operationSigned-off-by Patrick McHardy <[email protected]>
Applied to net-2.6.20
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
@@ -957,11 +957,7 @@ hfsc_purge_queue(struct Qdisc *sch, struunsigned 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, unsigreturn 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
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): HFSCConvert 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 casesqdisc_tree_decrease_len()is needed.Signed-off-by Patrick McHardy <[email protected]>
Applied to net-2.6.20, thanks.
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
@@ -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 Qdireturn (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
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
@@ -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 Qdireturn (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
In reply to Patrick McHardyQuoted 8 lines · Patrick McHardy
[
NET_SCHED]: Fix endless loops (part 4): HTBConvert 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 <[email protected]>---
...
Quoted 18 lines
net/sched/sch_htb.c +1
-5@@ -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 Qdireturn (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_qlenI'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
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_qlenI'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
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.
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.
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_graftit was necessary because the class could be either active (qlen > 0) or inactive (qlen == 0). But sinceqdisc_tree_decrease_qlendoes 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
Quoted 11 lines · Martin Devera
Quoted 6 lines
In
htb_graftit was necessary because the class could be either active (qlen > 0) or inactive (qlen == 0). But sinceqdisc_tree_decrease_qlendoes 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_activityfor 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.
Re: [NET_SCHED 06/06]: Fix endless loops (part 4): HTB
In reply to Martin DeveraQuoted 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_graftit was necessary because the class could be either active (qlen > 0) or inactive (qlen == 0). But sinceqdisc_tree_decrease_qlendoes 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_activityfor 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 toBUG()). 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
In reply to Patrick McHardyFrom: Patrick McHardy <[email protected]>
Date: Mon, 20 Nov 2006 14:08:48 +0100 (MET)
Quoted 6 lines
[
NET_SCHED]: Fix endless loops (part 4): HTBConvert 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 <[email protected]>
Applied to net-2.6.20