This this patch is mangled I appologize, this is my first try sending

a patch directly to netdev.
The patch below is my attempt to resolve the issue found with qdisc_run

only checking the state of queue zero before running.  This approach

essentially makes the qdisc layer smart enough to do it's own check to

see if a hw queue is stopped instead of relying on other calls to check

beforehand.
I have been able to verify functionality for most qdiscs with the

exceptions of netem, red, sfq, and tbf.  I am not familiar with the

operation of these qdiscs and so I am not certain how to avoid the high

drop rate I am currently seeing when using these qdiscs.
The main advantages of this patch can be seen using a netperf UDP_STREAM

test to a slow interface with multiple queues and a qdisc such as pfifo,

bfifo, or prio.  For my testing I used an 82575 with 4 queues on a

system with 8 cpus.  When any queue other than 0 was used in the old

method the cpu utilization for one core would go to 100%, using this new

approach the cpu utilization for all queues was at the same level queue

0 was with the old approach.
---

This patch changes the behavior of the sch->dequeue to only

dequeue a packet if the queue it is bound for is not currently

stopped.  This functionality is provided via a new op called

smart_dequeue.
Signed-off-by: Alexander Duyck <alexander.h.duyck@intel.com>

---
 include/net/pkt_sched.h   |    5 --

 include/net/sch_generic.h |   27 ++++++++++

 net/sched/sch_atm.c       |   22 ++++++++

 net/sched/sch_blackhole.c |    1

 net/sched/sch_cbq.c       |  118 ++++++++++++++++++++++++++++++++++++++++++++-

 net/sched/sch_dsmark.c    |   47 ++++++++++++++++++

 net/sched/sch_fifo.c      |    2 +

 net/sched/sch_generic.c   |   30 +++++++++--

 net/sched/sch_gred.c      |   34 +++++++++++++

 net/sched/sch_hfsc.c      |   86 ++++++++++++++++++++++++++++++++-

 net/sched/sch_htb.c       |   82 ++++++++++++++++++++++++++++++-

 net/sched/sch_multiq.c    |   45 ++++++++++...
[ message continues ]

Alexander Duyck wrote, On 09/18/2008 08:43 AM:
I think, these changes make sense only if they don't add more then give,

and two dequeues (and still no way to kill requeue) is IMHO too much.

(I mean the maintenance.) As far as I can see it's mainly for HFSC's

qdisc_peek_len(), anyway this looks like main issue to me.
Below a few small doubts. (I need to find some time for details yet.)

BTW, this patch needs a checkpatch run.
---

diff --git a/include/net/pkt_sched.h b/include/net/pkt_sched.h

index b786a5b..4082f39 100644

--- a/include/net/pkt_sched.h

+++ b/include/net/pkt_sched.h

@@ -90,10 +90,7 @@ extern void __qdisc_run(struct Qdisc *q);
 static inline void qdisc_run(struct Qdisc *q)

 {

-	struct netdev_queue *txq = q->dev_queue;

-

-	if (!netif_tx_queue_stopped(txq) &&
I think, there is no reason to do a full dequeue try each time instead

of this check, even if we save on requeuing now. We could try to save

the result of the last dequeue, e.g. a number or some mask of a few

tx_queues which prevented dequeuing, and check for the change of state

only. (Or alternatively, what I mentioned before: a flag set with the

full stop or freeze.)
-	    !test_and_set_bit(__QDISC_STATE_RUNNING, &q->state))

+	if (!test_and_set_bit(__QDISC_STATE_RUNNING, &q->state))

 		__qdisc_run(q);

 }
diff --git a/include/net/sch_generic.h b/include/net/sch_generic.h

index e556962..4400a18 100644

--- a/include/net/sch_generic.h

+++ b/include/net/sch_generic.h

...

+static inline struct sk_buff *__qdisc_smart_dequeue(struct Qdisc *sch,

+						    struct sk_buff_head *list)

+{

+	struct sk_buff *skb = skb_peek(list);
Since success is much more likely here, __skb_dequeue() with

__skb_queue_head() on fail looks better to me.
Of course, it's a matter of taste, but (if we really need these two

dequeues) maybe qdisc_dequeue_smart() would be more in line with

qdisc_dequeue_head()? (And similarly smart names below.)
+	struct netdev_queue *txq;

+

+	if (!skb)

+		retu...
[ message continues ]

Alexander, I guess you've seen my last messages/patches in this thread

and noticed that this __netif_schedule() problem is present both in

this RFC patch and sch_multiq: if skb isn't dequeued because of inner

tx_queue stopped state check, there is missing __netif_schedule()

before exit from qdisc_run().
Jarek P.

--

On Fri, Sep 19, 2008 at 05:16:32PM +0200, Jarek Poplawski wrote:
Hmm... probably false alarm. It seems there have to be same wake_queue

after all.
Sorry,

Jarek P.

--

Actually most of that is handled in the fact that netif_tx_wake_queue

will call __netif_schedule when it decides to wake up a queue that has

been stopped.  Putting it in skb_dequeue is unnecessary, and the way

you did it would cause issues because you should be scheduling the root

qdisc, not the one currently doing the dequeue.
My bigger concern is the fact one queue is back to stopping all queues.

By using one global XOFF state, you create head-of-line blocking.  I can

see the merit in this approach but the problem is for multiqueue the

queues really should be independent.  What your change does is reduce the

benefit of having multiqueue by throwing in a new state which pretty much

matches what netif_stop/wake_queue used to do in the 2.6.26 version of tx

multiqueue.
Also changing dequeue_skb will likely cause additional issues for

several qdiscs as it doesn't report anything up to parent queues, as a

result you will end up with qdiscs like prio acting more like multiq

because they won't know if a queue is empty, stopped, or throttled.

Also I believe this will cause a panic on pfifo_fast and several other

qdiscs because some check to see if there are packets in the queue and

if so dequeue with the assumption that they will get a packet out.  You

will need to add checks for this to resolve this issue.
The one thing I liked about my approach was that after I was done you

could have prio as a parent of multiq leaves or multiq as the parent of

prio leaves and all the hardware queues would receive the packets in the

same order as the result.
Thanks,
Alex

--

On Fri, Sep 19, 2008 at 09:26:29AM -0700, Duyck, Alexander H wrote:
Do you mean netif_tx_stop_all_queues() and then netif_tx_wake_queue()
I really can't get your point. Don't you mean skb_dequeue()?
I'm not against your approach, but I'd like to be sure these

complications are really worth of it. Of course, if my proposal, the

first take of 3 patches, doesn't work as you predict (and I doubt),

then we can forget about it.
Thanks,

Jarek P.

--

You're right.  I misread it as skb_dequeue.  The problem is though you

are still relying on q->requeue which last I knew was only being used

a few qdiscs.  In addition you will still be taking the cpu hit for the

dequeue/requeue on several qdiscs which can't use q->requeue without

Well when you get some testing done let me know.  The main areas I am

concerned with are:
1.  CPU utilization stays the same regardless of which queue used.

2.  Maintain current qdisc behavior on a per hw queue basis.

3.  Avoid head-of-line blocking where it applies

        for example: prio band 0 not blocked by band 1, or 1 by 2, etc..

                                or

                         multiq not blocked on any band due to 1 band blocked
As long as all 3 criteria are met I would be happy with any solution

provided.
Thanks,
Alex

--

I'm not sure I understand your point. No qdisc will use any new

q->requeue. All qdisc do dequeue, but on tx fail an skb isn't requeued

back, but queued by qdisc_restart() in a private list (of root qdisc),

and then tried before any new dequeuing. There will be no cpu hit,

because each next try is only skb_peek() on this list, until tx queue
Alas this testing is both the weekest (I'm not going to do this), and

the strongest side of this solution, because it's mostly David's work

(my patch could be actually skipped without much impact). So, I hope,

you don't suggest this could be not enough tested or otherwise not the

best?!
Anyway, I don't insist on "my" solution. I simply think it's reasonable,

and it's not for private reasons, because I didn't even find this out.

I think, if it's so wrong you should have no problem to show this in

one little test. And maybe David changed his mind in the meantime and he

will choose your way even without this.
Thanks,

Jarek P.

--

It was me missing a piece.  I didn't look over the portion where Dave

changed requeue to always use the requeue list.  This breaks multiq

and we are right back to the head-of-line blocking.  Also I think patch

1 will break things since queueing a packet with skb->next already set
I didn't mean to insist on this if it is how it came across.  My main

concern is that I just don't want to break what I just got working.

Most of this requeue to q->requeue stuff will break multiq and

introduce head-of-line blocking.  When That happens it will fall back

into my lap to try to resolve it so that is why I want to avoid it in

the first place.
Anyway I'm out for the next two weeks with at least the first week of

that being without email access.  I hope I provided some valuable

input so that this can head in the right direction.
Thanks,
Alex
--

The thing is this was just meant to be a proof of concept for the most

part so I was doing a lot of cut and paste coding, and as a result the

size increased by a good amount.  I admit this could be cleaned up a

lot I just wanted to verify some things.
Also my ultimate goal wasn't to kill requeue completely as you can't

do that since in the case of TSO/GSO you will end up with SKBs which

require multiple transmit descriptors and therefore you will always

need an option to requeue.  The advantage with this approach is that

you don't incur the CPU cost, which is a significant savings when you

compare the requeue approach which was generating 13% cpu to the smart
I did run checkpatch on this.  Most of the errors are inherited from

the cut and paste and I didn't want to take the time to completely

rewrite the core qdisc functionality.  Other than those errors I

believe some were whitespace complaints as I was using tabs to the

start of my functions and then spaces to indent my function parameters
Once again if you have a suggestion on approach feel free to modify

the patch and see how it works for you.  My only concern is that there

are several qdiscs which won't give you the same packet twice and so
Right, but then we are getting back to the queue/requeue stuff.  If

you want feel free to make use of my patch to generate your own that

uses that approach.  I just don't like changing things unless I

absolutely have to and all I did is essentially tear apart

__skb_dequeue and place the bits inline with my testing for
For the most part I would agree with you, but for now I was only using

the flag as a part of the smart_dequeue process to flag the upper

queues so I didn't give it much thought.  It is yet another thing I

probably should have cleaned up but didn't get around to since this
Actually I could probably replace most of the skb_peek stuff with

calls to __qdisc_smart_dequeue instead and then just check for the
I probably won't be able to contribute to this for at least th...
[ message continues ]

Take 2:

I missed __netif_schedule() in my patch, so the update below.
But, because of this a little change of mind: there is no reason to

repeat __netif_schedule() if there is a full stop or freeze of all

queues, so it seems we need additional check for this anyway. I'll

send my proposal of this test soon.
Jarek P.
...
Actually, here is my suggestion: I think, that your obviously more

complex solution should be compared with something simple which IMHO

has similar feature, i.e. limited overhead of requeuing.
My proposal is to use partly David's idea of killing ->ops->requeue(),

for now only the first two patches, so don't requeue back to the

qdiscs, but leave qdisc->ops->requeue() for internal usage (like in

HFSC's qdisc_peek_len() hack). Additionaly I use your idea of early

checking the state of tx queue to make this even lighter after

possibly removing the entry check from qdisc_run().
I attach my patch at the end, after original David's two patches.
Thanks,

Jarek P.
---------------> patch 1/3

Subject: [PATCH 1/9]: pkt_sched: Make qdisc->gso_skb a list.

Date: Mon, 18 Aug 2008 01:36:47 -0700 (PDT)

From: David Miller <davem@davemloft.net>

To: netdev@vger.kernel.org

CC: jarkao2@gmail.com

Newsgroups: gmane.linux.network
pkt_sched: Make qdisc->gso_skb a list.
The idea is that we can use this to get rid of

->requeue().
Signed-off-by: David S. Miller <davem@davemloft.net>

---

 include/net/sch_generic.h |    2 +-

 net/sched/sch_generic.c   |   12 +++++++-----

 2 files changed, 8 insertions(+), 6 deletions(-)
diff --git a/include/net/sch_generic.h b/include/net/sch_generic.h

index 84d25f2..140c48b 100644

--- a/include/net/sch_generic.h

+++ b/include/net/sch_generic.h

@@ -52,7 +52,7 @@ struct Qdisc

 	u32			parent;

 	atomic_t		refcnt;

 	unsigned long		state;

-	struct sk_buff		*gso_skb;

+	struct sk_buff_head	requeue;

 	struct sk_buff_head	q;

 	struct netdev_queue	*dev_queue;

 	struct Qdisc		*next_sched;

diff --git ...
[ message continues ]

David,
After rethinking and reading Alexender's opinion I see this

change isn't needed so I withdraw this take 2.
Please, reconsider the first version of this patch (with your

2 patches), yet.
Thanks,

Jarek P.

--

Alas this time the changelog needs more details.
Sorry,

Jarek P.

-----------------> (take 2)
pkt_sched: Fix TX state checking in qdisc_run()
Current check wrongly uses the state of the first tx queue for all tx

queues in case of non-default qdiscs. This patch brings back per dev

__LINK_STATE_XOFF flag, which is set when all tx queues are stopped.

This check is needed in qdisc_run() to avoid useless __netif_schedule()

calls. The wrongness of this check was first noticed by Herbert Xu.
Signed-off-by: Jarek Poplawski <jarkao2@gmail.com>

---
 include/linux/netdevice.h |    7 ++++++-

 include/net/pkt_sched.h   |    4 +---

 2 files changed, 7 insertions(+), 4 deletions(-)
diff --git a/include/linux/netdevice.h b/include/linux/netdevice.h

index 488c56e..dc76e4b 100644

--- a/include/linux/netdevice.h

+++ b/include/linux/netdevice.h

@@ -271,6 +271,7 @@ struct header_ops {
 enum netdev_state_t

 {

+	__LINK_STATE_XOFF,

 	__LINK_STATE_START,

 	__LINK_STATE_PRESENT,

 	__LINK_STATE_NOCARRIER,

@@ -1043,6 +1044,7 @@ static inline void netif_tx_wake_queue(struct netdev_queue *dev_queue)

 static inline void netif_wake_queue(struct net_device *dev)

 {

 	netif_tx_wake_queue(netdev_get_tx_queue(dev, 0));

+	clear_bit(__LINK_STATE_XOFF, &dev->state);

 }
 static inline void netif_tx_wake_all_queues(struct net_device *dev)

@@ -1053,6 +1055,7 @@ static inline void netif_tx_wake_all_queues(struct net_device *dev)

 		struct netdev_queue *txq = netdev_get_tx_queue(dev, i);

 		netif_tx_wake_queue(txq);

 	}

+	clear_bit(__LINK_STATE_XOFF, &dev->state);

 }
 static inline void netif_tx_stop_queue(struct netdev_queue *dev_queue)

@@ -1069,6 +1072,7 @@ static inline void netif_tx_stop_queue(struct netdev_queue *dev_queue)

  */

 static inline void netif_stop_queue(struct net_device *dev)

 {

+	set_bit(__LINK_STATE_XOFF, &dev->state);

 	netif_tx_stop_queue(netdev_get_tx_queue(dev, 0));

 }
@@ -1076,6 +1080,7 @@ static inline void netif_tx_stop_all_queues(...
[ message continues ]

From: Jarek Poplawski <jarkao2@gmail.com>
I'm dropping this and the patches in the ->smart_requeue thread as well.
It simply isn't crystal clear how to proceed at this point.

--

David,
After reading Alexander's opinion I withdaw this patch (take 1 & 2)

as well.
Sorry,

Jarek P.

--

pkt_sched: Fix TX state checking in qdisc_run()
Current check wrongly uses the state of the first tx queue for all tx

queues. This patch brings back per dev __LINK_STATE_XOFF flag, which

is set when all tx queues are stopped. This check is needed in

qdisc_run() to avoid useless __netif_schedule() calls.
Signed-off-by: Jarek Poplawski <jarkao2@gmail.com>

---
 include/linux/netdevice.h |    7 ++++++-

 include/net/pkt_sched.h   |    4 +---

 2 files changed, 7 insertions(+), 4 deletions(-)
diff --git a/include/linux/netdevice.h b/include/linux/netdevice.h

index 488c56e..dc76e4b 100644

--- a/include/linux/netdevice.h

+++ b/include/linux/netdevice.h

@@ -271,6 +271,7 @@ struct header_ops {
 enum netdev_state_t

 {

+	__LINK_STATE_XOFF,

 	__LINK_STATE_START,

 	__LINK_STATE_PRESENT,

 	__LINK_STATE_NOCARRIER,

@@ -1043,6 +1044,7 @@ static inline void netif_tx_wake_queue(struct netdev_queue *dev_queue)

 static inline void netif_wake_queue(struct net_device *dev)

 {

 	netif_tx_wake_queue(netdev_get_tx_queue(dev, 0));

+	clear_bit(__LINK_STATE_XOFF, &dev->state);

 }
 static inline void netif_tx_wake_all_queues(struct net_device *dev)

@@ -1053,6 +1055,7 @@ static inline void netif_tx_wake_all_queues(struct net_device *dev)

 		struct netdev_queue *txq = netdev_get_tx_queue(dev, i);

 		netif_tx_wake_queue(txq);

 	}

+	clear_bit(__LINK_STATE_XOFF, &dev->state);

 }
 static inline void netif_tx_stop_queue(struct netdev_queue *dev_queue)

@@ -1069,6 +1072,7 @@ static inline void netif_tx_stop_queue(struct netdev_queue *dev_queue)

  */

 static inline void netif_stop_queue(struct net_device *dev)

 {

+	set_bit(__LINK_STATE_XOFF, &dev->state);

 	netif_tx_stop_queue(netdev_get_tx_queue(dev, 0));

 }
@@ -1076,6 +1080,7 @@ static inline void netif_tx_stop_all_queues(struct net_device *dev)

 {

 	unsigned int i;
+	set_bit(__LINK_STATE_XOFF, &dev->state);

 	for (i = 0; i < dev->num_tx_queues; i++) {

 		struct netdev_queue *txq = netdev_get...
[ message continues ]

...
Actually, here is my suggestion: I think, that your obviously more

complex solution should be compared with something simple which IMHO

has similar feature, i.e. limited overhead of requeuing.
My proposal is to use partly David's idea of killing ->ops->requeue(),

for now only the first two patches, so don't requeue back to the

qdiscs, but leave qdisc->ops->requeue() for internal usage (like in

HFSC's qdisc_peek_len() hack). Additionaly I use your idea of early

checking the state of tx queue to make this even lighter after

possibly removing the entry check from qdisc_run().
I attach my patch at the end, after original David's two patches.
Thanks,

Jarek P.
---------------> patch 1/3

Subject: [PATCH 1/9]: pkt_sched: Make qdisc->gso_skb a list.

Date: Mon, 18 Aug 2008 01:36:47 -0700 (PDT)

From: David Miller <davem@davemloft.net>

To: netdev@vger.kernel.org

CC: jarkao2@gmail.com

Newsgroups: gmane.linux.network
pkt_sched: Make qdisc->gso_skb a list.
The idea is that we can use this to get rid of

->requeue().
Signed-off-by: David S. Miller <davem@davemloft.net>

---

 include/net/sch_generic.h |    2 +-

 net/sched/sch_generic.c   |   12 +++++++-----

 2 files changed, 8 insertions(+), 6 deletions(-)
diff --git a/include/net/sch_generic.h b/include/net/sch_generic.h

index 84d25f2..140c48b 100644

--- a/include/net/sch_generic.h

+++ b/include/net/sch_generic.h

@@ -52,7 +52,7 @@ struct Qdisc

 	u32			parent;

 	atomic_t		refcnt;

 	unsigned long		state;

-	struct sk_buff		*gso_skb;

+	struct sk_buff_head	requeue;

 	struct sk_buff_head	q;

 	struct netdev_queue	*dev_queue;

 	struct Qdisc		*next_sched;

diff --git a/net/sched/sch_generic.c b/net/sched/sch_generic.c

index 6f96b7b..39d969e 100644

--- a/net/sched/sch_generic.c

+++ b/net/sched/sch_generic.c

@@ -45,7 +45,7 @@ static inline int qdisc_qlen(struct Qdisc *q)

 static inline int dev_requeue_skb(struct sk_buff *skb, struct Qdisc *q)

 {

 	if (unlikely(skb->next))

-		q->g...
[ message continues ]

From: Alexander Duyck <alexander.h.duyck@intel.com>
So what is the difference between qdisc->dequeue and qdisc->ops->dequeue?

The same applies to ->enqueue.
qdisc->{dequeue,enqueue} are given the value of ops->{dequeue,enqueue}

at the time of qdisc creation.  I can only see two reasons for their

existence:
1) We used to allow overriding ->enqueue and ->dequeue by certain

   modules.  I see no such use like this in the current tree.
2) For performance it's kept as a copy in the qdisc.
Either way, changing ->ops->dequeue into ->dequeue doesn't seem to be

correct, unless you have some explanation.
This is done in a few other places in your patch.
--

I redefined qdisc->dequeue to be set to smart_dequeue in sch_generic.c:

@@ -475,7 +491,7 @@ struct Qdisc *qdisc_alloc(struct netdev_queue *dev_queue,

       skb_queue_head_init(&sch->q);

       sch->ops = ops;

       sch->enqueue = ops->enqueue;

-       sch->dequeue = ops->dequeue;

+       sch->dequeue = ops->smart_dequeue;

       sch->dev_queue = dev_queue;

       dev_hold(qdisc_dev(sch));

       atomic_set(&sch->refcnt, 1);
Most of the changes from qdisc->dequeue to qdisc->ops->dequeue are to have the

standard dequeue call use nothing but standard dequeue calls in it's

path.  I needed

to maintain qdisc->ops->dequeue because there are several functions throughout

the qdisc code that require the ability to dequeue a packet regardless

of hw queue

state.
Thanks,
Alex

--

On Wed, Sep 17, 2008 at 11:43 PM, Alexander Duyck

Already off to mangling things.  I got Dave's email wrong..  Sorry to

all who reply and get a bad address warning, and I meant to say "If

this patch is mangled..".
Anyway if anyone decides to reply please make note of the bad address.
Thanks,
Alex

--