Add qdisc->ops->peek() support.

I think we really need a peek operation since most qdiscs do have some internal priorization. The question is whether all qdiscs need it; I tend to think no. Plugging two non-work-conserving qdiscs together doesn't make much sense, so we could just prevent this. This means we would only need to add ->peek support to the work-conserving qdiscs, which looks pretty easy in all cases. We actually don't even have to prevent plugging two non-work-conserving qdiscs, the ones that need the peek operation could just check whether the inner qdisc supports it.

Just as a demonstration how easy adding a peek operation to the work-conserving qdiscs actually is. It doesn't need to keep or change any internal state in many cases thanks to the guarantee that the packet will either be dequeued or, if another packet arrives, the upper qdisc will immediately ->peek again to reevaluate the state.

So here is my try (I hope I didn't miss Patrick's intentions to much).

PATCH 6/6 adds my simple idea not to prevent even nonsense configs. It is optional.

PS: after this patchset only netem_enqueue() needs qdisc->requeue(), but I hope this won't take too long.

Quoted 4 lines · Jarek Poplawski

So here is my try (I hope I didn't miss Patrick's intentions to much).

PATCH 6/6 adds my simple idea not to prevent even nonsense configs. It is optional.

These patches look good to me. About 6/6, I'm still thinking we might want to prevent certain kinds of nonsensical configurations for simplicity. Its a bit similar to the multiq stuff, a lot of these complications came from the fact that non-work-conserving qdiscs, which require a global view, are treated similar to work- conserving ones. I don't have a good scheme worked out though, so for now using your patch seems OK too.

Quoted 2 lines

PS: after this patchset only netem_enqueue() needs qdisc->requeue(), but I hope this won't take too long.

Assuming work-conserving qdiscs are used with netem, the currently code will always send out a reorder packet immediately. This behaviour is trivial to implement without ->requeue. The problematic case is non-work-conserving inner qdiscs, but that doesn't seem important at all since you'd usually add it as parent of netem, which still works.

Jarek Poplawski wrote:

Quoted 2 lines

PS: after this patchset only netem_enqueue() needs qdisc->requeue(), but I hope this won't take too long.

Assuming work-conserving qdiscs are used with netem, the currently code will always send out a reorder packet immediately. This behaviour is trivial to implement without ->requeue. The problematic case is non-work-conserving inner qdiscs, but that doesn't seem important at all since you'd usually add it as parent of netem, which still works.

Patrick McHardy wrote, On 10/16/2008 02:38 PM:

Quoted 1 line

Jarek Poplawski wrote:

...

Quoted 8 lines

Quoted 2 lines

PS: after this patchset only netem_enqueue() needs qdisc->requeue(), but I hope this won't take too long.

Assuming work-conserving qdiscs are used with netem, the currently code will always send out a reorder packet immediately. This behaviour is trivial to implement without ->requeue. The problematic case is non-work-conserving inner qdiscs, but that doesn't seem important at all since you'd usually add it as parent of netem, which still works.

How about something like this (example only)?

Quoted 13 lines · Jarek Poplawski

Patrick McHardy wrote, On 10/16/2008 02:38 PM:

Quoted 1 line

Jarek Poplawski wrote:

...

Quoted 8 lines

Quoted 2 lines

PS: after this patchset only netem_enqueue() needs qdisc->requeue(), but I hope this won't take too long.

Assuming work-conserving qdiscs are used with netem, the currently code will always send out a reorder packet immediately. This behaviour is trivial to implement without ->requeue. The problematic case is non-work-conserving inner qdiscs, but that doesn't seem important at all since you'd usually add it as parent of netem, which still works.

net/sched/sch_netem.c static int netem_enqueue(struct sk_buff *skb, struct Qdisc *sch) · line 238

Quoted 9 lines

How about something like this (example only)?

net/sched/sch_netem.c +3 -1

@@ -233,7 +233,9 @@ static int netem_enqueue(struct sk_buff *skb, struct Qdisc *sch)
 		 */
 		cb->time_to_send = psched_get_time();
 		q->counter = 0;
-		ret = q->qdisc->ops->requeue(skb, q->qdisc);
+		q->qdisc->flags |= TCQ_F_REQUEUE;
+		ret = qdisc_equeue(skb, q->qdisc);
+		q->qdisc->flags &= ~TCQ_F_REQUEUE;

Well, the inner qdisc would still need to logic to order packets apprioriately.

Its probably not that hard, but as I said, I don't
think its necessary at all. It only makes a difference with a non-work-conserving inner qdisc, but a lot of the functionality of netem requires the inner tfifo anyways and rate-limiting is usually done on top of netem. So I would suggest so either hard-wire the tfifo qdisc or at least make the assumption that inner qdiscs are work-conserving.

Quoted 10 lines · Patrick McHardy

net/sched/sch_netem.c static int netem_enqueue(struct sk_buff *skb, struct Qdisc *sch) · line 238

Quoted 8 lines

net/sched/sch_netem.c +3 -1

@@ -233,7 +233,9 @@ static int netem_enqueue(struct sk_buff *skb, struct Qdisc *sch)
 		 */
 		cb->time_to_send = psched_get_time();
 		q->counter = 0;
-		ret = q->qdisc->ops->requeue(skb, q->qdisc);
+		q->qdisc->flags |= TCQ_F_REQUEUE;
+		ret = qdisc_equeue(skb, q->qdisc);
+		q->qdisc->flags &= ~TCQ_F_REQUEUE;

Well, the inner qdisc would still need to logic to order packets apprioriately.

I'm not sure I was understood: the idea is to do something like in this example in tfifo_enqueue() in all leaf qdiscs like fifo etc. too, so to redirect their ->enqueue() to their ->requeue() which usually is qdisc_requeue() (or to it directly if needed).

Quoted 7 lines

Its probably not that hard, but as I said, I don't
think its necessary at all. It only makes a difference with a non-work-conserving inner qdisc, but a lot of the functionality of netem requires the inner tfifo anyways and rate-limiting is usually done on top of netem. So I would suggest so either hard-wire the tfifo qdisc or at least make the assumption that inner qdiscs are work-conserving.

Of course, I can do it like this, but wouldn't it break backward compatibility for some users?

Quoted 12 lines · Jarek Poplawski

Quoted 10 lines · Patrick McHardy

Review static int netem_enqueue(struct sk_buff *skb, struct Qdisc *sch) · line 238

Quoted 8 lines

(quoted diff) +3 -1

@@ -233,7 +233,9 @@ static int netem_enqueue(struct sk_buff *skb, struct Qdisc *sch)
 		 */
 		cb->time_to_send = psched_get_time();
 		q->counter = 0;
-		ret = q->qdisc->ops->requeue(skb, q->qdisc);
+		q->qdisc->flags |= TCQ_F_REQUEUE;
+		ret = qdisc_equeue(skb, q->qdisc);
+		q->qdisc->flags &= ~TCQ_F_REQUEUE;

Well, the inner qdisc would still need to logic to order packets apprioriately.

Quoted 4 lines

I'm not sure I was understood: the idea is to do something like in this example in tfifo_enqueue() in all leaf qdiscs like fifo etc. too, so to redirect their ->enqueue() to their ->requeue() which usually is qdisc_requeue() (or to it directly if needed).

Yes, I misunderstood this, I though the intention was to get rid of requeue entirely.

Quoted 7 lines

Quoted 7 lines

Its probably not that hard, but as I said, I don't
think its necessary at all. It only makes a difference with a non-work-conserving inner qdisc, but a lot of the functionality of netem requires the inner tfifo anyways and rate-limiting is usually done on top of netem. So I would suggest so either hard-wire the tfifo qdisc or at least make the assumption that inner qdiscs are work-conserving.

pkt_sched: sch_netem: Limit packet re-ordering functionality to tfifo qdisc.

After introducing qdisc->ops->peek() method the only remaining user of qdisc->ops->requeue() is netem_enqueue() using this for packet re-ordering. According to Patrick McHardy: "a lot of the functionality of netem requires the inner tfifo anyways and rate-limiting is usually done on top of netem. So I would suggest so either hard-wire the tfifo qdisc or at least make the assumption that inner qdiscs are work- conserving." This patch tries the former.

Signed-off-by Jarek Poplawski <[email protected]>

From: Jarek Poplawski <[email protected]>
Date: Fri, 17 Oct 2008 22:12:10 +0200

Quoted 11 lines

pkt_sched: sch_netem: Limit packet re-ordering functionality to tfifo qdisc.

After introducing qdisc->ops->peek() method the only remaining user of qdisc->ops->requeue() is netem_enqueue() using this for packet re-ordering. According to Patrick McHardy: "a lot of the functionality of netem requires the inner tfifo anyways and rate-limiting is usually done on top of netem. So I would suggest so either hard-wire the tfifo qdisc or at least make the assumption that inner qdiscs are work- conserving." This patch tries the former.

Signed-off-by Jarek Poplawski <[email protected]>

This is an interesting patch.

But the thing that strikes me is this: Why don't we just let sch_netem do the reordering inside of itself entirely and just get rid of all of this ->requeue() business?

sch_netem is just a black box, like any other packet scheduler node in the tree, and so it can internally do the reordering with a self managed packet list or similar. All of this can be hidden inside of it's ->dequeue() with some pkt_sch watchdog timer that fires to prevent stale packets sitting in the reorder queue forever.

Anyways, just and idea and RFC, just like this patch ;-)

Quoted 13 lines · On Tue, 21 Oct 2008 16:36:05 -0700 (PDT) David Miller <[email protected]>…

From: Jarek Poplawski <[email protected]>
Date: Fri, 17 Oct 2008 22:12:10 +0200

Quoted 10 lines

pkt_sched: sch_netem: Limit packet re-ordering functionality to tfifo qdisc.

After introducing qdisc->ops->peek() method the only remaining user of qdisc->ops->requeue() is netem_enqueue() using this for packet re-ordering. According to Patrick McHardy: "a lot of the functionality of netem requires the inner tfifo anyways and rate-limiting is usually done on top of netem. So I would suggest so either hard-wire the tfifo qdisc or at least make the assumption that inner qdiscs are work- conserving." This patch tries the former.

Quoted 7 lines

Quoted 1 line

Signed-off-by Jarek Poplawski <[email protected]>

This is an interesting patch.

But the thing that strikes me is this: Why don't we just let sch_netem do the reordering inside of itself entirely and just get rid of all of this ->requeue() business?

Quoted 7 lines

sch_netem is just a black box, like any other packet scheduler node in the tree, and so it can internally do the reordering with a self managed packet list or similar. All of this can be hidden inside of it's ->dequeue() with some pkt_sch watchdog timer that fires to prevent stale packets sitting in the reorder queue forever.

Quoted 1 line

Anyways, just and idea and RFC, just like this patch ;-)

The problem is that jamal talked me into having netem as a classful qdisc, instead of doing its own rate control. People like to do use TBF as inner qdisc, and do reordering.

Quoted 9 lines · Stephen Hemminger

Quoted 6 lines · On Tue, 21 Oct 2008 16:36:05 -0700 (PDT) David Miller <[email protected]>…

sch_netem is just a black box, like any other packet scheduler node in the tree, and so it can internally do the reordering with a self managed packet list or similar. All of this can be hidden inside of it's ->dequeue() with some pkt_sch watchdog timer that fires to prevent stale packets sitting in the reorder queue forever.

Quoted 4 lines

Quoted 1 line

Anyways, just and idea and RFC, just like this patch ;-)

The problem is that jamal talked me into having netem as a classful qdisc, instead of doing its own rate control. People like to do use TBF as inner qdisc, and do reordering.

If it's only this kind of usage we could export tfifo and let use this as a TBF's (etc.) leaf. Of course, this would require changes in those people scripts.

Quoted 10 lines · Jarek Poplawski

Quoted 9 lines · Stephen Hemminger

Quoted 6 lines · On Tue, 21 Oct 2008 16:36:05 -0700 (PDT) David Miller <[email protected]>…

sch_netem is just a black box, like any other packet scheduler node in the tree, and so it can internally do the reordering with a self managed packet list or similar. All of this can be hidden inside of it's ->dequeue() with some pkt_sch watchdog timer that fires to prevent stale packets sitting in the reorder queue forever.

Quoted 8 lines

Quoted 4 lines

Quoted 1 line

Anyways, just and idea and RFC, just like this patch ;-)

The problem is that jamal talked me into having netem as a classful qdisc, instead of doing its own rate control. People like to do use TBF as inner qdisc, and do reordering.

If it's only this kind of usage we could export tfifo and let use this as a TBF's (etc.) leaf. Of course, this would require changes in those people scripts.

In that case we might as well teach them to use TBF as *parent* of netem (and I'd vote to do that and kill requeue).

But we can argue about this forever without any progress. The question is simple - should we enforce a reasonable qdisc structure and kill ->requeue or keep it around forever. Keep in mind that there is no loss of functionality by using TBF as parent and that we can do this gradually so users have a chance to fix their scripts, should anyone really use TBF as inner qdisc.

Quoted 7 lines · Patrick McHardy

Quoted 3 lines · Jarek Poplawski

If it's only this kind of usage we could export tfifo and let use this as a TBF's (etc.) leaf. Of course, this would require changes in those people scripts.

In that case we might as well teach them to use TBF as *parent* of netem (and I'd vote to do that and kill requeue).

Quoted 7 lines

But we can argue about this forever without any progress. The question is simple - should we enforce a reasonable qdisc structure and kill ->requeue or keep it around forever. Keep in mind that there is no loss of functionality by using TBF as parent and that we can do this gradually so users have a chance to fix their scripts, should anyone really use TBF as inner qdisc.

I'm not sure we think about the same: this tfifo idea doesn't need ->requeue() at all. This would go through TBF's or prio's (etc.) ->enqueue(), and only tfifo's ->enqueue(), if it's used as a leaf, checks the qdisc flag and can reorder.

But if it's useless, no problem. I can redo this patch without this qdisc flag.

Well, you're doing the work, so you decide. I'm undecided myself, the main issues I see are:

So actually I am decided :) I think netem shouldn't be classful.

From: Jarek Poplawski <[email protected]>
Date: Fri, 17 Oct 2008 22:12:10 +0200

Quoted 10 lines

pkt_sched: sch_netem: Limit packet re-ordering functionality to tfifo qdisc.

After introducing qdisc->ops->peek() method the only remaining user of qdisc->ops->requeue() is netem_enqueue() using this for packet re-ordering. According to Patrick McHardy: "a lot of the functionality of netem requires the inner tfifo anyways and rate-limiting is usually done on top of netem. So I would suggest so either hard-wire the tfifo qdisc or at least make the assumption that inner qdiscs are work- conserving." This patch tries the former.

Quoted 1 line

Signed-off-by Jarek Poplawski <[email protected]>

This is an interesting patch.

But the thing that strikes me is this: Why don't we just let sch_netem do the reordering inside of itself entirely and just get rid of all of this ->requeue() business?

sch_netem is just a black box, like any other packet scheduler node in the tree, and so it can internally do the reordering with a self managed packet list or similar. All of this can be hidden inside of it's ->dequeue() with some pkt_sch watchdog timer that fires to prevent stale packets sitting in the reorder queue forever.

Anyways, just and idea and RFC, just like this patch ;-)

From: Jarek Poplawski <[email protected]>
Date: Fri, 17 Oct 2008 22:12:10 +0200

Quoted 10 lines

pkt_sched: sch_netem: Limit packet re-ordering functionality to tfifo qdisc.

After introducing qdisc->ops->peek() method the only remaining user of qdisc->ops->requeue() is netem_enqueue() using this for packet re-ordering. According to Patrick McHardy: "a lot of the functionality of netem requires the inner tfifo anyways and rate-limiting is usually done on top of netem. So I would suggest so either hard-wire the tfifo qdisc or at least make the assumption that inner qdiscs are work- conserving." This patch tries the former.

Quoted 1 line

Signed-off-by Jarek Poplawski <[email protected]>

This is an interesting patch.

But the thing that strikes me is this: Why don't we just let sch_netem do the reordering inside of itself entirely and just get rid of all of this ->requeue() business?

Some general thoughts ...

We've never had any systematic checks for useful and non-useful combination of qdiscs, which is causing a lot of these complications. Think of all the multiq work that was required to make it work properly with non-work-conserving qdiscs - while at the same time, using a non-work-conserving qdisc (which require a global view) defeats basically all of the benefits.

So it would be really useful to come up with a systematic definition of valid combinations instead of trying handling lots of purely theoretical case that don't make sense. One more example - all the qdiscs implement ->drop(), yet its only needed by CBQ and it doesn't make any sense at all to use lets say HFSC as child of CBQ.

About this specific case - yes, it would break compatibility for users using f.i. TBF as child of netem. But if you look at the netem_enqueue() function, it in fact assumes that the inner qdisc is a tfifo, so we'd be breaking an already broken case. We can of course be nice and warn about it for a few releases, but I believe there is some real potential for simplification that makes it worth it.

BTW, I'm not sure if I'm expected to redo any patches in this thread. (Probably some things like this teql_peek() could be removed with ->requeue() killing.)

From: Jarek Poplawski <[email protected]>
Date: Fri, 17 Oct 2008 22:45:43 +0200

Quoted 3 lines

BTW, I'm not sure if I'm expected to redo any patches in this thread. (Probably some things like this teql_peek() could be removed with ->requeue() killing.)

In any event, you should resubmit these when I open the net-next-2.6 tree up in about a week or so.

It looks like Patrick is in agreement about these changes and they look mostly fine to me too, FWIW.

On Fri, Oct 17, 2008 at 04:12:03PM +0200, Patrick McHardy wrote:
...

Quoted 15 lines

Some general thoughts ...

We've never had any systematic checks for useful and non-useful combination of qdiscs, which is causing a lot of these complications. Think of all the multiq work that was required to make it work properly with non-work-conserving qdiscs - while at the same time, using a non-work-conserving qdisc (which require a global view) defeats basically all of the benefits.

So it would be really useful to come up with a systematic definition of valid combinations instead of trying handling lots of purely theoretical case that don't make sense. One more example - all the qdiscs implement ->drop(), yet its only needed by CBQ and it doesn't make any sense at all to use lets say HFSC as child of CBQ.

Quoted 7 lines

About this specific case - yes, it would break compatibility for users using f.i. TBF as child of netem. But if you look at the netem_enqueue() function, it in fact assumes that the inner qdisc is a tfifo, so we'd be breaking an already broken case. We can of course be nice and warn about it for a few releases, but I believe there is some real potential for simplification that makes it worth it.

I'm not sure this is all right: at least until there is not too much problems with some code (like with requeuing). We probably should try before this official ways like feature-removal-schedule.txt, and/or maybe some CONFIG_XXX_DEPRECATED things. But I don't persist with this.

BTW, I'm not sure if I'm expected to redo any patches in this thread. (Probably some things like this teql_peek() could be removed with ->requeue() killing.)