[PATCH] HFSC - initialize parent's cl_cfmin properly in init_vf()

[PATCH] HFSC - initialize parent's cl_cfmin properly in init_vf()

[Michal Soltys]

Consider following hierarchy:

      A(u)
     /  \
    X    Y(u)

A and Y have upperlimit curve defined, X - doesn't. We'll assume that no
realtime curve is present in either of the classes, for the sake of
simplicity.

Assume that Y is constantly backlogged, and then a new traffic gets
assigned to X - 1st packet will trigger set_active() and init_vf().

The problem: although init_vf() will properly add X to A's cftree, A's
cfmin will never be updated. The reason for that is - cftree_insert()
only inserts, but doesn't really care for that variable. On the other
hand, last condition in init_vf() function will never be true, thus
update_cfmin(cl->cl_parent) will not be called as X has no upperlimit
curve, and all three cl_f, cl_myf, cl_cfmin are always 0 for X.

When some packet from Y gets dequeued, it will update cl_cfmin()
accordingly, and X's packets will get dequeued in a bursty fashion.

The best way to experience the practical effects of this bug: create the
above hierarchy in highly assymetric fashion - e.g.:

#tc qdisc add dev eth0 root handle 1:0 hfsc default 301
#tc class add dev eth0 parent 1:0 classid 1:300 hfsc ls m2 90mbit ul m2 90mbit

#tc class add dev eth0 parent 1:300 classid 1:301 hfsc ls m2 99950kbit
#tc class add dev eth0 parent 1:300 classid 1:302 hfsc ls m2 50kbit ul m2 50kbit

...and then assign ssh session to 1:301, making sure 1:302 is constantly
backlogged. Do ls -alR / or edit some file, the effect will be evident.

The problem naturally extends to any hierarchy of classes, where some of
the leafs have no upperlimit curve. Realtime curve can help a bit - but
update_vf() doesn't call update_cfmin() unconditionally either, so we're
left on the mercy of other classes to do so.

Furthermore, each time such a class becomes passive - the problem will
reappear once we become backlogged again.

The fix is very simple - init_vf() should always call update_cfmin() at
the end of the for loop. It seems it's not necessary to make update_vf()
do the same - init_vf() will guarantee the call on the beginning of
every new backlog period, and the further calls are only necessary if
cl_f changes.


Michal Soltys (1):
  net/sched/sch_hfsc.c: initialize parent's cl_cfmin properly in init_vf()

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

-- 
1.7.2.1

[PATCH] net/sched/sch_hfsc.c: initialize parent's cl_cfmin properly in init_vf()

[Michal Soltys]

This patch fixes init_vf() function, so on each new backlog period parent's
cl_cfmin is properly updated (including further propgation towards the root),
even if the activated leaf has no upperlimit curve defined.

Signed-off-by: Michal Soltys <soltys@ziu.info>
---
 net/sched/sch_hfsc.c |    2 +-
 1 files changed, 1 insertions(+), 1 deletions(-)

diff --git a/net/sched/sch_hfsc.c b/net/sched/sch_hfsc.c
index abd904b..4749609 100644
--- a/net/sched/sch_hfsc.c
+++ b/net/sched/sch_hfsc.c
@@ -761,8 +761,8 @@ init_vf(struct hfsc_class *cl, unsigned int len)
 		if (f != cl->cl_f) {
 			cl->cl_f = f;
 			cftree_update(cl);
-			update_cfmin(cl->cl_parent);
 		}
+		update_cfmin(cl->cl_parent);
 	}
 }
 
-- 
1.7.2.1

Re: [PATCH] net/sched/sch_hfsc.c: initialize parent's cl_cfmin properly in init_vf()

[David Miller]

From: Michal Soltys <soltys@ziu.info>
Date: Mon, 30 Aug 2010 23:34:10 +0200

> This patch fixes init_vf() function, so on each new backlog period parent's
> cl_cfmin is properly updated (including further propgation towards the root),
> even if the activated leaf has no upperlimit curve defined.
> 
> Signed-off-by: Michal Soltys <soltys@ziu.info>

Applied, thanks.

Re: [PATCH] net/sched/sch_hfsc.c: initialize parent's cl_cfmin properly in init_vf()

[Patrick McHardy]

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

Am 01.09.2010 23:30, schrieb David Miller:
> From: Michal Soltys <soltys@ziu.info>
> Date: Mon, 30 Aug 2010 23:34:10 +0200
> 
>> This patch fixes init_vf() function, so on each new backlog period parent's
>> cl_cfmin is properly updated (including further propgation towards the root),
>> even if the activated leaf has no upperlimit curve defined.
>>
>> Signed-off-by: Michal Soltys <soltys@ziu.info>
> 
> Applied, thanks.

For the record, the patch seems fine to me. The root cause seems to be
an optimization I introduced (pre-git, even history.git unfortunately)
in vttree_get_minvt() that wasn't present in the original version:

static struct hfsc_class *
vttree_get_minvt(struct hfsc_class *cl, u64 cur_time)
{
        /* if root-class's cfmin is bigger than cur_time nothing to do */
        if (cl->cl_cfmin > cur_time)
                return NULL;

I'd prefer to remove this check since it's obviously not correct and
might cause other problems. Michal, could you please test whether this
patch fixes the problem as well? Thanks!

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

diff --git a/net/sched/sch_hfsc.c b/net/sched/sch_hfsc.c
index 4749609..466518e 100644
--- a/net/sched/sch_hfsc.c
+++ b/net/sched/sch_hfsc.c
@@ -312,10 +312,6 @@ vttree_firstfit(struct hfsc_class *cl, u64 cur_time)
 static struct hfsc_class *
 vttree_get_minvt(struct hfsc_class *cl, u64 cur_time)
 {
-	/* if root-class's cfmin is bigger than cur_time nothing to do */
-	if (cl->cl_cfmin > cur_time)
-		return NULL;
-
 	while (cl->level > 0) {
 		cl = vttree_firstfit(cl, cur_time);
 		if (cl == NULL)

Re: [PATCH] net/sched/sch_hfsc.c: initialize parent's cl_cfmin properly in init_vf()

[Michal Soltys]

On 10-09-15 19:54, Patrick McHardy wrote:
> Am 01.09.2010 23:30, schrieb David Miller:
>>  From: Michal Soltys<soltys@ziu.info>
>>  Date: Mon, 30 Aug 2010 23:34:10 +0200
>>
>>>  This patch fixes init_vf() function, so on each new backlog period parent's
>>>  cl_cfmin is properly updated (including further propgation towards the root),
>>>  even if the activated leaf has no upperlimit curve defined.
>>>
>>>  Signed-off-by: Michal Soltys<soltys@ziu.info>
>>
>>  Applied, thanks.
>
> For the record, the patch seems fine to me. The root cause seems to be
> an optimization I introduced (pre-git, even history.git unfortunately)
> in vttree_get_minvt() that wasn't present in the original version:
>
> static struct hfsc_class *
> vttree_get_minvt(struct hfsc_class *cl, u64 cur_time)
> {
>          /* if root-class's cfmin is bigger than cur_time nothing to do */
>          if (cl->cl_cfmin>  cur_time)
>                  return NULL;
>
> I'd prefer to remove this check since it's obviously not correct and
> might cause other problems. Michal, could you please test whether this
> patch fixes the problem as well? Thanks!

Sure, will do. Although with a tad bit more complex scenario than from 
my cover email, I think there will still be problems. For example:

     A
    / \
   B   C(u2)
  / \
D   E(u1)

C and E are constantly backlogged, D becomes active. It will add itself 
to B's vt_tree, but won't update B's cl_cfmin (without my earlier fix). 
B is already active, its myf and cfmin didn't change, so neither did f. 
And so nothing will change for A either.

Now we try a dequeue. Without your old optimization (btw I think it's a 
good shortcut, if I didn't miss anything), A will choose min vt from B 
and C, if their f <= cur_time. B's f should be at this moment 0 (D has 
no upperlimit and became active), but it remained unchanged. So we have 
the same problem as previously. This would work with a trivial hierarchy 
though, such as:

     A
    / \
   B   C(u2)

But deeper scenarios seem problematic. Of course I'll do the actual 
tests to be sure.

A bit more constrained version from my patch (to limit update_cfmin() 
calls) could be:
                 f = max(cl->cl_myf, cl->cl_cfmin);
                 if (f != cl->cl_f) {
                         cl->cl_f = f;
                         cftree_update(cl);
                         update_cfmin(cl->cl_parent);
                 } else if (go_active)
                         update_cfmin(cl->cl_parent);

Re: [PATCH] net/sched/sch_hfsc.c: initialize parent's cl_cfmin properly in init_vf()

[Michal Soltys]

On Wed, Sep 15, 2010 at 11:42:57PM +0200, Michal Soltys wrote:
> On 10-09-15 19:54, Patrick McHardy wrote:
> >Am 01.09.2010 23:30, schrieb David Miller:
> >> From: Michal Soltys<soltys@ziu.info>
> >> Date: Mon, 30 Aug 2010 23:34:10 +0200
> >>
> >>> This patch fixes init_vf() function, so on each new backlog period parent's
> >>> cl_cfmin is properly updated (including further propgation towards the root),
> >>> even if the activated leaf has no upperlimit curve defined.
> >>>
> >>> Signed-off-by: Michal Soltys<soltys@ziu.info>
> >>
> >> Applied, thanks.
> >
> >For the record, the patch seems fine to me. The root cause seems to be
> >an optimization I introduced (pre-git, even history.git unfortunately)
> >in vttree_get_minvt() that wasn't present in the original version:
> >
> >static struct hfsc_class *
> >vttree_get_minvt(struct hfsc_class *cl, u64 cur_time)
> >{
> >         /* if root-class's cfmin is bigger than cur_time nothing to do */
> >         if (cl->cl_cfmin>  cur_time)
> >                 return NULL;
> >
> >I'd prefer to remove this check since it's obviously not correct and
> >might cause other problems. Michal, could you please test whether this
> >patch fixes the problem as well? Thanks!
> 
> Sure, will do. Although with a tad bit more complex scenario than
> from my cover email, I think there will still be problems.

Ok, did the tests. The results confirmed the earlier theory - namely, if I
removed my fix and your optimization, the only scenario it helped with was if
the leafs were directly attached to the root qdisc, eg.:

    root
    /  \
   A    B(u)

Here, making decision at root would go through childrens' 'vt's and 'f's times
and properly dequeue A without any delays.

Anything deeper though, like:

     |                / \
     A               A   B(u)
    / \             / \
   B   C(u)        C  D(u)

still cause problems - while the decision would go through 'vt's and 'f's - the
'f's are calculated as max(myf, cfmin), and cfmin won't be updated updwards
from the leafs that have no upperlimit.

Regarding your optimization - its results should be consistent with the first
vttree_firstfit() call (if cf_min is properly updated). I don't see how it
could cause any misbehaviour.

Speaking about hfsc, I have few other potential changes with reference to how
vt is handled and updated (especially cvtmin), but that's for different mail.

Additional 'if' condition (mentioned in previous mail) in my fix seemed to work
fine as well, namely:

diff --git a/net/sched/sch_hfsc.c b/net/sched/sch_hfsc.c
index 4749609..e9768b2 100644
--- a/net/sched/sch_hfsc.c
+++ b/net/sched/sch_hfsc.c
@@ -761,8 +761,9 @@ init_vf(struct hfsc_class *cl, unsigned int len)
 		if (f != cl->cl_f) {
 			cl->cl_f = f;
 			cftree_update(cl);
-		}
-		update_cfmin(cl->cl_parent);
+			update_cfmin(cl->cl_parent);
+		} else if (go_active)
+			update_cfmin(cl->cl_parent);
 	}
 }

Re: [PATCH] net/sched/sch_hfsc.c: initialize parent's cl_cfmin properly in init_vf()

[David Miller]

From: Patrick McHardy <kaber@trash.net>
Date: Wed, 15 Sep 2010 19:54:49 +0200

> Am 01.09.2010 23:30, schrieb David Miller:
>> From: Michal Soltys <soltys@ziu.info>
>> Date: Mon, 30 Aug 2010 23:34:10 +0200
>> 
>>> This patch fixes init_vf() function, so on each new backlog period parent's
>>> cl_cfmin is properly updated (including further propgation towards the root),
>>> even if the activated leaf has no upperlimit curve defined.
>>>
>>> Signed-off-by: Michal Soltys <soltys@ziu.info>
>> 
>> Applied, thanks.
> 
> For the record, the patch seems fine to me. The root cause seems to be
> an optimization I introduced (pre-git, even history.git unfortunately)
> in vttree_get_minvt() that wasn't present in the original version:
> 
> static struct hfsc_class *
> vttree_get_minvt(struct hfsc_class *cl, u64 cur_time)
> {
>         /* if root-class's cfmin is bigger than cur_time nothing to do */
>         if (cl->cl_cfmin > cur_time)
>                 return NULL;

Actually, the HFSC scheduler was added with this test present.
The function had a different name, actlist_get_minvt(), at the
time.  See commit:

commit 6e22ce74ea0666a869ce82f418ce78b5be089fb4
Author: Patrick McHardy <kaber@trash.net>
Date:   Wed Jan 28 20:15:03 2004 -0800

    [NET_SCHED]: Add HFSC packet scheduler.

in the history-2.6 GIT tree.

Re: [PATCH] net/sched/sch_hfsc.c: initialize parent's cl_cfmin properly in init_vf()

[Patrick McHardy]

Am 18.09.2010 01:41, schrieb David Miller:
> From: Patrick McHardy <kaber@trash.net>
> Date: Wed, 15 Sep 2010 19:54:49 +0200
> 
>> Am 01.09.2010 23:30, schrieb David Miller:
>>> From: Michal Soltys <soltys@ziu.info>
>>> Date: Mon, 30 Aug 2010 23:34:10 +0200
>>>
>>>> This patch fixes init_vf() function, so on each new backlog period parent's
>>>> cl_cfmin is properly updated (including further propgation towards the root),
>>>> even if the activated leaf has no upperlimit curve defined.
>>>>
>>>> Signed-off-by: Michal Soltys <soltys@ziu.info>
>>>
>>> Applied, thanks.
>>
>> For the record, the patch seems fine to me. The root cause seems to be
>> an optimization I introduced (pre-git, even history.git unfortunately)
>> in vttree_get_minvt() that wasn't present in the original version:
>>
>> static struct hfsc_class *
>> vttree_get_minvt(struct hfsc_class *cl, u64 cur_time)
>> {
>>         /* if root-class's cfmin is bigger than cur_time nothing to do */
>>         if (cl->cl_cfmin > cur_time)
>>                 return NULL;
> 
> Actually, the HFSC scheduler was added with this test present.
> The function had a different name, actlist_get_minvt(), at the
> time.  See commit:
> 
> commit 6e22ce74ea0666a869ce82f418ce78b5be089fb4
> Author: Patrick McHardy <kaber@trash.net>
> Date:   Wed Jan 28 20:15:03 2004 -0800
> 
>     [NET_SCHED]: Add HFSC packet scheduler.
> 
> in the history-2.6 GIT tree.

Indeed, what I meant to say was that I made this optimization
before HFSC was added to BitKeeper, so there's no changelog
present for this particular optimization.