[PATCH] hfsc: ensure class is added to eltree exactly once

[PATCH] hfsc: ensure class is added to eltree exactly once

[Florian Westphal]

Intent is to insert the class into the eligible tree when first packet
is enqueued (its removed from list when class becomes empty again).

Checking for a size of 1 is problematic:

1. child qdisc might have segmented the skb, in which backlog can transition
from 0 to a value > 1.

In this case we can't dequeue anymore as this class is not in the tree.

2. some qdiscs like fq_codel can purge their backlogs when internal
limits are hit and update the parent qlen via qdisc_tree_reduce_backlog(),
so its possible that we end up with a length of 1 after enqueue for a class
that was already on the active list.

If this happens, we add the same class twice (which then results
in qdisc dequeue soft lockup).

Fix it by testing the length before we attempt to enqueue to child qdisc,
if enqueue operation is successful and old qlen was 0, then the
class was not yet inserted into eltree.

Cc: Miroslav Kratochvil <exa.exa@gmail.com>
Signed-off-by: Florian Westphal <fw@strlen.de>
---
 This was found while looking at Miroslav Kratochvil bug report
 but I don't think this fixes his case (I could trigger the 2nd case
 above w. fq_codel+really_stupid_config_knobs but I got softlockup
 which did not match his report).

diff --git a/net/sched/sch_hfsc.c b/net/sched/sch_hfsc.c
index d783d7c..0854be3 100644
--- a/net/sched/sch_hfsc.c
+++ b/net/sched/sch_hfsc.c
@@ -1583,6 +1583,7 @@ hfsc_enqueue(struct sk_buff *skb, struct Qdisc *sch)
 {
 	struct hfsc_class *cl;
 	int uninitialized_var(err);
+	unsigned int qlen;
 
 	cl = hfsc_classify(skb, sch, &err);
 	if (cl == NULL) {
@@ -1592,6 +1593,7 @@ hfsc_enqueue(struct sk_buff *skb, struct Qdisc *sch)
 		return err;
 	}
 
+	qlen = cl->qdisc->q.qlen;
 	err = qdisc_enqueue(skb, cl->qdisc);
 	if (unlikely(err != NET_XMIT_SUCCESS)) {
 		if (net_xmit_drop_count(err)) {
@@ -1601,7 +1603,7 @@ hfsc_enqueue(struct sk_buff *skb, struct Qdisc *sch)
 		return err;
 	}
 
-	if (cl->qdisc->q.qlen == 1)
+	if (qlen == 0)
 		set_active(cl, qdisc_pkt_len(skb));
 
 	sch->q.qlen++;
-- 
2.7.3

Re: [PATCH] hfsc: ensure class is added to eltree exactly once

[Eric Dumazet]

On Tue, 2016-05-31 at 12:12 +0200, Florian Westphal wrote:
> Intent is to insert the class into the eligible tree when first packet
> is enqueued (its removed from list when class becomes empty again).
> 
> Checking for a size of 1 is problematic:
> 
> 1. child qdisc might have segmented the skb, in which backlog can transition
> from 0 to a value > 1.
> 
> In this case we can't dequeue anymore as this class is not in the tree.
> 
> 2. some qdiscs like fq_codel can purge their backlogs when internal
> limits are hit and update the parent qlen via qdisc_tree_reduce_backlog(),
> so its possible that we end up with a length of 1 after enqueue for a class
> that was already on the active list.
> 
> If this happens, we add the same class twice (which then results
> in qdisc dequeue soft lockup).
> 
> Fix it by testing the length before we attempt to enqueue to child qdisc,
> if enqueue operation is successful and old qlen was 0, then the
> class was not yet inserted into eltree.
> 
> Cc: Miroslav Kratochvil <exa.exa@gmail.com>
> Signed-off-by: Florian Westphal <fw@strlen.de>
> ---
>  This was found while looking at Miroslav Kratochvil bug report
>  but I don't think this fixes his case (I could trigger the 2nd case
>  above w. fq_codel+really_stupid_config_knobs but I got softlockup
>  which did not match his report).
> 
> diff --git a/net/sched/sch_hfsc.c b/net/sched/sch_hfsc.c
> index d783d7c..0854be3 100644
> --- a/net/sched/sch_hfsc.c
> +++ b/net/sched/sch_hfsc.c
> @@ -1583,6 +1583,7 @@ hfsc_enqueue(struct sk_buff *skb, struct Qdisc *sch)
>  {
>  	struct hfsc_class *cl;
>  	int uninitialized_var(err);
> +	unsigned int qlen;
>  
>  	cl = hfsc_classify(skb, sch, &err);
>  	if (cl == NULL) {
> @@ -1592,6 +1593,7 @@ hfsc_enqueue(struct sk_buff *skb, struct Qdisc *sch)
>  		return err;
>  	}
>  
> +	qlen = cl->qdisc->q.qlen;
>  	err = qdisc_enqueue(skb, cl->qdisc);
>  	if (unlikely(err != NET_XMIT_SUCCESS)) {
>  		if (net_xmit_drop_count(err)) {
> @@ -1601,7 +1603,7 @@ hfsc_enqueue(struct sk_buff *skb, struct Qdisc *sch)
>  		return err;
>  	}
>  
> -	if (cl->qdisc->q.qlen == 1)
> +	if (qlen == 0)
>  		set_active(cl, qdisc_pkt_len(skb));
>  
>  	sch->q.qlen++;

Well, I am not sure HFSC can deal with non work conserving qdisc
anyway ?

Call to set_active(cl, qdisc_pkt_len(skb)); would tell you that HFSC
does not expect another packet than @skb being the next dequeued one.

If you want to make HFSC generic, you would need a lot more changes.

Re: [PATCH] hfsc: ensure class is added to eltree exactly once

[Florian Westphal]

Eric Dumazet <eric.dumazet@gmail.com> wrote:
> > diff --git a/net/sched/sch_hfsc.c b/net/sched/sch_hfsc.c
> > index d783d7c..0854be3 100644
> > --- a/net/sched/sch_hfsc.c
> > +++ b/net/sched/sch_hfsc.c
> > @@ -1583,6 +1583,7 @@ hfsc_enqueue(struct sk_buff *skb, struct Qdisc *sch)
> >  {
> >  	struct hfsc_class *cl;
> >  	int uninitialized_var(err);
> > +	unsigned int qlen;
> >  
> >  	cl = hfsc_classify(skb, sch, &err);
> >  	if (cl == NULL) {
> > @@ -1592,6 +1593,7 @@ hfsc_enqueue(struct sk_buff *skb, struct Qdisc *sch)
> >  		return err;
> >  	}
> >  
> > +	qlen = cl->qdisc->q.qlen;
> >  	err = qdisc_enqueue(skb, cl->qdisc);
> >  	if (unlikely(err != NET_XMIT_SUCCESS)) {
> >  		if (net_xmit_drop_count(err)) {
> > @@ -1601,7 +1603,7 @@ hfsc_enqueue(struct sk_buff *skb, struct Qdisc *sch)
> >  		return err;
> >  	}
> >  
> > -	if (cl->qdisc->q.qlen == 1)
> > +	if (qlen == 0)
> >  		set_active(cl, qdisc_pkt_len(skb));
> >  
> >  	sch->q.qlen++;
> 
> Well, I am not sure HFSC can deal with non work conserving qdisc
> anyway ?

As long as child qdisc dequeue() returns an skb if qlen > 0 it should
work.

> Call to set_active(cl, qdisc_pkt_len(skb)); would tell you that HFSC
> does not expect another packet than @skb being the next dequeued one.

Good point.  I'll look into it in more detail but AFAIU this "only"
means we might overshoot a defined realtime/deadline criterion,
I don't (yet) see how it could explain Miroslavs bug report.

> If you want to make HFSC generic, you would need a lot more changes.

Could you elaborate?

I'm not interested in e.g. tbf leaves (makes no sense to me), but I
think it should play nice with netem, sfq, codel, fq_codel, fq, ...

I don't see any problems with fq_codel + hfsc unless I deliberately
misconfigure fq_codel (setting extremely low mem limit, e.g. 32kbyte).

Re: [PATCH] hfsc: ensure class is added to eltree exactly once

[Eric Dumazet]

On Wed, 2016-06-01 at 01:00 +0200, Florian Westphal wrote:
> Eric Dumazet <eric.dumazet@gmail.com> wrote:
> > > diff --git a/net/sched/sch_hfsc.c b/net/sched/sch_hfsc.c
> > > index d783d7c..0854be3 100644
> > > --- a/net/sched/sch_hfsc.c
> > > +++ b/net/sched/sch_hfsc.c
> > > @@ -1583,6 +1583,7 @@ hfsc_enqueue(struct sk_buff *skb, struct Qdisc *sch)
> > >  {
> > >  	struct hfsc_class *cl;
> > >  	int uninitialized_var(err);
> > > +	unsigned int qlen;
> > >  
> > >  	cl = hfsc_classify(skb, sch, &err);
> > >  	if (cl == NULL) {
> > > @@ -1592,6 +1593,7 @@ hfsc_enqueue(struct sk_buff *skb, struct Qdisc *sch)
> > >  		return err;
> > >  	}
> > >  
> > > +	qlen = cl->qdisc->q.qlen;
> > >  	err = qdisc_enqueue(skb, cl->qdisc);
> > >  	if (unlikely(err != NET_XMIT_SUCCESS)) {
> > >  		if (net_xmit_drop_count(err)) {
> > > @@ -1601,7 +1603,7 @@ hfsc_enqueue(struct sk_buff *skb, struct Qdisc *sch)
> > >  		return err;
> > >  	}
> > >  
> > > -	if (cl->qdisc->q.qlen == 1)
> > > +	if (qlen == 0)
> > >  		set_active(cl, qdisc_pkt_len(skb));
> > >  
> > >  	sch->q.qlen++;
> > 
> > Well, I am not sure HFSC can deal with non work conserving qdisc
> > anyway ?
> 
> As long as child qdisc dequeue() returns an skb if qlen > 0 it should
> work.

Generally speaking, a non work conserving qdisc could return NULL if it
decides to drop all packet(s) that were sitting in the queue.

Say we add a 'max sojourn time' on skbs, as yet another anti-bloat
features, in a Codel variant/extension.

HFSC does check this and eventually complains ( qdisc_warn_nonwc()),
but all its precise computations are probably wrong.

> > Call to set_active(cl, qdisc_pkt_len(skb)); would tell you that HFSC
> > does not expect another packet than @skb being the next dequeued one.
> 
> Good point.  I'll look into it in more detail but AFAIU this "only"
> means we might overshoot a defined realtime/deadline criterion,
> I don't (yet) see how it could explain Miroslavs bug report.


> > If you want to make HFSC generic, you would need a lot more changes.
> 
> Could you elaborate?

HFSC is based on packet lengths and realtime/deadline constraints.

With lazy packet lengths (if the attached children qdisc reorder
packets), this all becomes fuzzy. Which might be OK or not.

We are not helping users by silently making such decisions.
Maybe they prefer to be warned so that they can fix their setup. 

> 
> I'm not interested in e.g. tbf leaves (makes no sense to me), but I
> think it should play nice with netem, sfq, codel, fq_codel, fq, ...
> 
> I don't see any problems with fq_codel + hfsc unless I deliberately
> misconfigure fq_codel (setting extremely low mem limit, e.g. 32kbyte).

That is pure luck, then. I would not be surprised that HTB + nonwc qdisc
would actually crash in some cases.

Re: [PATCH] hfsc: ensure class is added to eltree exactly once

[Florian Westphal]

Eric Dumazet <eric.dumazet@gmail.com> wrote:
> On Wed, 2016-06-01 at 01:00 +0200, Florian Westphal wrote:
> Generally speaking, a non work conserving qdisc could return NULL if it
> decides to drop all packet(s) that were sitting in the queue.
> 
> Say we add a 'max sojourn time' on skbs, as yet another anti-bloat
> features, in a Codel variant/extension.
>
> HFSC does check this and eventually complains ( qdisc_warn_nonwc()),
> but all its precise computations are probably wrong.

Right, this is already a problem when using hfsc with silly fq_codel config
(we can end up with underflow on sch->q.qlen, i.e. hfsc
ends up thinking it has 0xffffffff packets in class while fq_codel has 0).

> > > If you want to make HFSC generic, you would need a lot more changes.
> > 
> > Could you elaborate?
> 
> HFSC is based on packet lengths and realtime/deadline constraints.
> 
> With lazy packet lengths (if the attached children qdisc reorder
> packets), this all becomes fuzzy. Which might be OK or not.
> 
> We are not helping users by silently making such decisions.
> Maybe they prefer to be warned so that they can fix their setup.

Seems that limits us to pfifo or prio+pfifo only...

> > I'm not interested in e.g. tbf leaves (makes no sense to me), but I
> > think it should play nice with netem, sfq, codel, fq_codel, fq, ...
> > 
> > I don't see any problems with fq_codel + hfsc unless I deliberately
> > misconfigure fq_codel (setting extremely low mem limit, e.g. 32kbyte).
> 
> That is pure luck, then. I would not be surprised that HTB + nonwc qdisc
> would actually crash in some cases.

Ugh.  I think that using codel, sfq, fq_codel etc. should just work
when used with htb or hfsc.

Using tbf and friends should at least not crash kernel (it would
be nice if we could complain and/or reject at config time though).

Thanks for your input, I see this isn't easy to resolve.