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

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

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.

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

index abd904b..4749609 100644
@@ -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

From: Michal Soltys <[email protected]>
Date: Mon, 30 Aug 2010 23:34:10 +0200

Applied, thanks.

Am 01.09.2010 23:30, schrieb David Miller:

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!

index 4749609..466518e 100644
@@ -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)

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

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:

index 4749609..e9768b2 100644
@@ -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);
 	}
 }
 

From: Patrick McHardy <[email protected]>
Date: Wed, 15 Sep 2010 19:54:49 +0200

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 <[email protected]>
Date:   Wed Jan 28 20:15:03 2004 -0800

[NET_SCHED]: Add HFSC packet scheduler.

in the history-2.6 GIT tree.

Am 18.09.2010 01:41, schrieb David Miller:

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.