pkt_sched: Destroy gen estimators under rtnl_lock().

pkt_sched: Destroy gen estimators under rtnl_lock().

gen_kill_estimator() requires rtnl_lock() protection, and since it is called in qdisc ->destroy() too, this has to go back from RCU callback to qdisc_destroy().

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

From: Jarek Poplawski <[email protected]>
Date: Mon, 11 Aug 2008 22:53:57 +0200

Quoted 6 lines

pkt_sched: Destroy gen estimators under rtnl_lock().

gen_kill_estimator() requires rtnl_lock() protection, and since it is called in qdisc ->destroy() too, this has to go back from RCU callback to qdisc_destroy().

Quoted 1 line

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

We can't do this. And at a minimum, the final ->reset() must occur in the RCU callback, otherwise asynchronous threads of execution could queue packets into this dying qdisc and such packets would leak forever.

Quoted 11 lines

From: Jarek Poplawski <[email protected]>
Date: Mon, 11 Aug 2008 22:53:57 +0200

Quoted 7 lines

pkt_sched: Destroy gen estimators under rtnl_lock().

gen_kill_estimator() requires rtnl_lock() protection, and since it is called in qdisc ->destroy() too, this has to go back from RCU callback to qdisc_destroy().

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

Quoted 4 lines

We can't do this. And at a minimum, the final ->reset() must occur in the RCU callback, otherwise asynchronous threads of execution could queue packets into this dying qdisc and such packets would leak forever.

Could you explain this more? I've thought this synchronize_rcu() is just to prevent this (and what these comments talk about?):

Those comments are out of date and I need to update them. In fact this whole loop is now largely pointless.

The rcu_dereference() on dev_queue->qdisc happens before the QDISC_RUNNING bit is set.

We no longer resample the qdisc under any kind of lock. Because we no longer have a top-level lock that synchronizes the setting of dev_queue->qdisc

Rather, the lock we use for calling ->enqueue() and ->dequeue() is inside of the root qdisc itself.

That's why all of the real destruction has to occur in the RCU handler.

Anyways, this is part of the problem I think is causing the crash the Intel folks are triggering.

We sample the qdisc in dev_queue_xmit() or wherever, then we attach that to the per-cpu ->output_queue to process it via qdisc_run() in the software interrupt handler.

The RCU quiesce period extends to the next scheduling point and this is enough if we do normal direct softirq processing of this qdisc.

But if it gets postponed into ksoftirqd... the RCU will pass too early.

I'm still thinking about how to fix this without avoiding RCU and without adding new synchronization primitives.

Of course I've to miss something, but I still don't get it: after synchronize_rcu() in dev_deactivate() we are sure anyone in dev_queue_xmit() rcu block has to see the change to noop_qdisc(), so it can only lose packets and not really enqueue().

IMHO the only problem is this __netif_schedule(), which could be done with dev_queues instead of Qdiscs with proper dereferencing there. (BTW, I think we need rcu_read_lock() instead of the _bh() version in dev_queue_xmit() to match this with rcu_call() or synchronize_rcu().)

The synchronization object is the qdisc. So we can't resample the qdisc after scheduling it, because then the qdisc attached to the netdev_queue can change and we'd be holding the root lock for the wrong qdisc object.

The qdisc pointer traverses to the softirq handler, which can be run in a process context (via ksoftirqd), and this pointer gets there via the per-cpu ->output_queue.

Quoted 4 lines · David Miller

The qdisc pointer traverses to the softirq handler, which can be run in a process context (via ksoftirqd), and this pointer gets there via the per-cpu ->output_queue.

Here are two possible solutions:

1) The active way: smp_call_function and forcibly remove the qdiscs in question from each output_queue.

2) The passive way: Make dev_deactive call yield() until no qdisc's are on an output_queue. This assumes there is some sort of dead flag detection on the output_queue side so it doesn't keep going forever.

So, just like one of Jarek's patches, we should simply change dev_queue->qdisc into dev_queue->qdisc_sleeping and that should take care of the bulk of the issues.

Shouldn't it?

Hmmm... maybe we have to sample __QDISC_STATE_SCHED too.

Quoted 1 line

Hmmm... maybe we have to sample __QDISC_STATE_SCHED too.

You need this too for the ones which aren't running but sitting on output_queue. Either you'll have to forcibly remove them as I outlined earlier, or just wait for them to expire naturally.

The latter would seem more suitable since we're waiting anyway.

From: Herbert Xu <[email protected]>
Date: Wed, 13 Aug 2008 14:30:19 +1000

Quoted 8 lines

Quoted 4 lines · David Miller

The qdisc pointer traverses to the softirq handler, which can be run in a process context (via ksoftirqd), and this pointer gets there via the per-cpu ->output_queue.

Here are two possible solutions:

Quoted 7 lines

1) The active way: smp_call_function and forcibly remove the qdiscs in question from each output_queue.

2) The passive way: Make dev_deactive call yield() until no qdisc's are on an output_queue. This assumes there is some sort of dead flag detection on the output_queue side so it doesn't keep going forever.

Yes, we'll need some kind of dead flag it seems.

Another thing we can do is, in the yield loop, grabbing the __QDISC_STATE_RUNNING bit.

But actually, I think Jarek has a point.

The existing loop there in dev_deactivate() should work _iff_ we make it look at the proper qdisc.

This is another case where I didn't transform things correctly. The old code worked on dev->state since that's where we kept what used to be __LINK_STATE_QDISC_RUNNING.

But now that state is kept in the qdisc itself. But we just zapped the active qdisc, so the old one is in ->qdisc_sleeping not ->qdisc.

So, just like one of Jarek's patches, we should simply change dev_queue->qdisc into dev_queue->qdisc_sleeping and that should take care of the bulk of the issues.

Shouldn't it?

Hmmm... maybe we have to sample __QDISC_STATE_SCHED too.

Quoted 5 lines

So, just like one of Jarek's patches, we should simply change dev_queue->qdisc into dev_queue->qdisc_sleeping and that should take care of the bulk of the issues.

Shouldn't it?

If we don't change anything in __netif_schedule() I doubt it's enough. And if this old way of waiting for "outstanding qdisc-less" calls was really needed we should probably wait for both qdisc and qdisc_sleeping then.

Quoted 1 line

Hmmm... maybe we have to sample __QDISC_STATE_SCHED too.

We could probably even think of using this flag napi_disable() way.

From: Jarek Poplawski <[email protected]>
Date: Wed, 13 Aug 2008 06:13:17 +0000

Quoted 11 lines · David Miller

Quoted 5 lines

So, just like one of Jarek's patches, we should simply change dev_queue->qdisc into dev_queue->qdisc_sleeping and that should take care of the bulk of the issues.

Shouldn't it?

If we don't change anything in __netif_schedule() I doubt it's enough. And if this old way of waiting for "outstanding qdisc-less" calls was really needed we should probably wait for both qdisc and qdisc_sleeping then.

I think if we check both RUNNING and SCHED bits, we'll be OK.

Quoted 3 lines

Quoted 1 line

Hmmm... maybe we have to sample __QDISC_STATE_SCHED too.

We could probably even think of using this flag napi_disable() way.

Here (in dev_deactivate), ->qdisc is going to now be &noop_qdisc or similar. Asynchronous contexts can run into that thing as much as they want :-)

Thats why I still think a "common" RCU with rcu_dereference() (from dev_queue pointer)

in net_tx_action() should be enough: after synchronize_rcu() in dev_deactivate() we are sure any qdisc_run(), from dev_queue_xmit() or net_tx_action() can only see and lock noop_qdisc. Any activities on qdisc_sleeping can't happen so no need to wait for this. There could be some skbs enqueued just before synchronize, and they could be ->reset() and ->destroy() just after, even without rcu_call().

Otherwise, I think you would better send some code example with these flags, so we could be sure there is no misunderstanding around this.

pkt_sched: Fix queue quiescence testing in dev_deactivate().

From: Jarek Poplawski <[email protected]>
Date: Wed, 13 Aug 2008 06:53:03 +0000

Quoted 2 lines

Otherwise, I think you would better send some code example with these flags, so we could be sure there is no misunderstanding around this.

Here it my concrete proposal for a fix.

pkt_sched: Fix queue quiescence testing in dev_deactivate().

Based upon discussions with Jarek P. and Herbert Xu.

First, we're testing the wrong qdisc. We just reset the device queue qdiscs to &noop_qdisc and checking it's state is completely pointless here.

We want to wait until the previous qdisc that was sitting at the ->qdisc pointer is not busy any more. And that would be ->qdisc_sleeping.

Because of how we propagate the samples qdisc pointer down into qdisc_run and friends via per-cpu ->output_queue and netif_schedule, we have to wait also for the __QDISC_STATE_SCHED bit to clear as well.

Signed-off-by David S. Miller <[email protected]>

net/sched/sch_generic.c +6 -5

index 7cf83b3..4685746 100644
@@ -647,7 +647,7 @@ static void dev_deactivate_queue(struct net_device *dev,
 	}
 }
 
-static bool some_qdisc_is_running(struct net_device *dev, int lock)
+static bool some_qdisc_is_busy(struct net_device *dev, int lock)
 {
 	unsigned int i;
 

@@ -658,13 +658,14 @@ static bool some_qdisc_is_running(struct net_device *dev, int lock)
 		int val;
 
 		dev_queue = netdev_get_tx_queue(dev, i);
-		q = dev_queue->qdisc;
+		q = dev_queue->qdisc_sleeping;
 		root_lock = qdisc_lock(q);
 
 		if (lock)
 			spin_lock_bh(root_lock);
 
-		val = test_bit(__QDISC_STATE_RUNNING, &q->state);
+		val = (test_bit(__QDISC_STATE_RUNNING, &q->state) ||
+		       test_bit(__QDISC_STATE_SCHED, &q->state));
 
 		if (lock)
 			spin_unlock_bh(root_lock);

@@ -689,14 +690,14 @@ void dev_deactivate(struct net_device *dev)
 
 	/* Wait for outstanding qdisc_run calls. */
 	do {
-		while (some_qdisc_is_running(dev, 0))
+		while (some_qdisc_is_busy(dev, 0))
 			yield();
 
 		/*
 		 * Double-check inside queue lock to ensure that all effects
 		 * of the queue run are visible when we return.
 		 */
-		running = some_qdisc_is_running(dev, 1);
+		running = some_qdisc_is_busy(dev, 1);
 
 		/*
 		 * The running flag should never be set at this point because

- isn't there possible some longer ping-pong between qdic_run() and net_tx_action() when dev_requeue_skb() would get it back to __netif_schedule() and so on (with NETDEV_TX_BUSY)?

- in net_tx_action() we can hit a place just after clear_bit() where none of these bits is set. Of course, hitting this 2 times in a row seems to be very unprobable, yet possible, and a lock isn't helpful here, so probably some change around this would make this nicer.

- isn't there possible some longer ping-pong between qdic_run() and net_tx_action() when dev_requeue_skb() would get it back to __netif_schedule() and so on (with NETDEV_TX_BUSY)?

Quoted 6 lines · Jarek Poplawski

- in net_tx_action() we can hit a place just after clear_bit() where none of these bits is set. Of course, hitting this 2 times in a row seems to be very unprobable, yet possible, and a lock isn't helpful here, so probably some change around this would make this nicer.

Quoted 3 lines

- isn't there possible some longer ping-pong between qdic_run() and net_tx_action() when dev_requeue_skb() would get it back to __netif_schedule() and so on (with NETDEV_TX_BUSY)?

Good point. I think we should add an aliveness check in both net_tx_action and qdisc_run. In fact the net_tx_action problem existed previously as well. But it is pretty darn unlikely.

Quoted 11 lines · Jarek Poplawski

Quoted 9 lines

- in net_tx_action() we can hit a place just after clear_bit() where none of these bits is set. Of course, hitting this 2 times in a row seems to be very unprobable, yet possible, and a lock isn't helpful here, so probably some change around this would make this nicer.

- isn't there possible some longer ping-pong between qdic_run() and net_tx_action() when dev_requeue_skb() would get it back to __netif_schedule() and so on (with NETDEV_TX_BUSY)?

Quoted 3 lines

Good point. I think we should add an aliveness check in both net_tx_action and qdisc_run. In fact the net_tx_action problem existed previously as well. But it is pretty darn unlikely.

Yes, it seems qdisc_reset() doesn't have to help with this, so probably there is needed some requeue counter or something...

From: Jarek Poplawski <[email protected]>
Date: Wed, 13 Aug 2008 10:50:52 +0000

Quoted 16 lines · Herbert Xu

Quoted 14 lines · Jarek Poplawski

Quoted 9 lines

- in net_tx_action() we can hit a place just after clear_bit() where none of these bits is set. Of course, hitting this 2 times in a row seems to be very unprobable, yet possible, and a lock isn't helpful here, so probably some change around this would make this nicer.

- isn't there possible some longer ping-pong between qdic_run() and net_tx_action() when dev_requeue_skb() would get it back to __netif_schedule() and so on (with NETDEV_TX_BUSY)?

Good point. I think we should add an aliveness check in both net_tx_action and qdisc_run. In fact the net_tx_action problem existed previously as well. But it is pretty darn unlikely.

Quoted 2 lines

Yes, it seems qdisc_reset() doesn't have to help with this, so probably there is needed some requeue counter or something...

Ok, so what I'm going to do is check in my patch and then try to figure out how to resolve this "both bits clear" scenerio.

net: Change handling of the __QDISC_STATE_SCHED flag in net_tx_action().

Change handling of the __QDISC_STATE_SCHED flag in net_tx_action() to enable proper control in dev_deactivate_queue(). Now, if this flag is seen as unset under root_lock means a qdisc can't be netif_scheduled.

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

Quoted 8 lines · Jarek Poplawski

net: Change handling of the __QDISC_STATE_SCHED flag in net_tx_action().

Change handling of the __QDISC_STATE_SCHED flag in net_tx_action() to enable proper control in dev_deactivate_queue(). Now, if this flag is seen as unset under root_lock means a qdisc can't be netif_scheduled.

Quoted 1 line

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

Well this probably works in practice but at least on paper it is vulnerable to live-lock if the net_tx_action side always gets to the trylock stage and loses to the waiting side.

An aliveness flag would be the safest.

I'm not sure of your point... This patch is only to fix my yesterday's doubt #1, and it doesn't introduce, I hope, any new live-lock vulnerabity. So, if you mean doubt #2, there is needed a separate patch, but I'm not sure there is a need to add a flag. I've thougt about a counter in a Qdisc for consecutive requeues with netif_schedule, so we could break after some limit. Of course, your idea could be simpler and better, but if I could only see some code...

Quoted 8 lines · Jarek Poplawski

I'm not sure of your point... This patch is only to fix my yesterday's doubt #1, and it doesn't introduce, I hope, any new live-lock vulnerabity. So, if you mean doubt #2, there is needed a separate patch, but I'm not sure there is a need to add a flag. I've thougt about a counter in a Qdisc for consecutive requeues with netif_schedule, so we could break after some limit. Of course, your idea could be simpler and better, but if I could only see some code...

What I mean is the extremely unlikely scenario of net_tx_action always failing on trylock because dev_deactivate has grabbed the lock to check whether net_tx_action has completed.

Quoted 10 lines · Herbert Xu

Quoted 8 lines · Jarek Poplawski

I'm not sure of your point... This patch is only to fix my yesterday's doubt #1, and it doesn't introduce, I hope, any new live-lock vulnerabity. So, if you mean doubt #2, there is needed a separate patch, but I'm not sure there is a need to add a flag. I've thougt about a counter in a Qdisc for consecutive requeues with netif_schedule, so we could break after some limit. Of course, your idea could be simpler and better, but if I could only see some code...

Quoted 3 lines

What I mean is the extremely unlikely scenario of net_tx_action always failing on trylock because dev_deactivate has grabbed the lock to check whether net_tx_action has completed.

Of course! I got it myself after responding and re-reading, sorry. So, this is yet another doubt, but I still wonder why you don't attach any code... (I'm currently trying to re-think this.)

On the other hand... such a flag would be probably for one thing only. And if we would have a "netif_scheduled_without_xmitting" counter this could probably make 2 in 1?

From: Jarek Poplawski <[email protected]>
Date: Thu, 14 Aug 2008 08:52:50 +0000

Quoted 3 lines

On the other hand... such a flag would be probably for one thing only. And if we would have a "netif_scheduled_without_xmitting" counter this could probably make 2 in 1?

Here is how I propose to plug this hole. The issue is that there is this potential gap where both bits are clear while there is a context that can reschedule the qdisc.

I thought about it some more, but there is still the dev_queue_xmit() context that can have a reference to the old qdisc, be about to take the qdisc lock and feed packets into it's ->enqueue().

That's why we need the RCU destruction still. dev_deactivate() really doesn't clear out all references to the qdisc fully.

It might be a better approach to work on making that simply not matter, and just rely on RCU or similar to defer destruction and any real state changes internally to the qdisc tree will simply use the root qdisc's lock to block out enqueue/dequeue/requeue calls.

In that kind of scheme dev_deactivate() just sets the RCU pointer and doesn't sit around waiting for anything.

So what's the issue with dev_queue_xmit? That should be taken care of by something like rcu_barrier_bh, no?

That's why I got rid of the "resample" code in these places and tried to move everything into RCU.

I think I see another way out of this:

1) Add __QDISC_STATE_DEACTIVATE.

2) Set it right before dev_deactivate() swaps resets the qdisc pointer.

3) Test it in dev_queue_xmit() et al. once the qdisc root lock is acquired, and drop lock and resample ->qdisc if __QDISC_STATE_DEACTIVATE is set.

Quoted 4 lines

I think I see another way out of this:

1) Add __QDISC_STATE_DEACTIVATE.

Quoted 6 lines

2) Set it right before dev_deactivate() swaps resets the qdisc pointer.

3) Test it in dev_queue_xmit() et al. once the qdisc root lock is acquired, and drop lock and resample ->qdisc if __QDISC_STATE_DEACTIVATE is set.

Yep this sounds good to me.

The test being added to __netif_schedule() is just a reminder that we have to address the "both bits clear" case somehow, likely with Jarko's patch which I unintentionally reimplemented :)

net/core/dev.c +2 -0

@@ -1790,6 +1793,8 @@ gso:
 	rcu_read_lock_bh();
 
 	txq = dev_pick_tx(dev, skb);
+
+resample_qdisc:
 	q = rcu_dereference(txq->qdisc);
 
 #ifdef CONFIG_NET_CLS_ACT

net/core/dev.c gso: · line 1811

Quoted 8 lines

net/core/dev.c +4 -0

@@ -1800,6 +1805,11 @@ gso:
 
 		spin_lock(root_lock);
 
+		if (unlikely(test_bit(__QDISC_STATE_DEACTIVATED, &q->state))) {
+			spin_unlock(root_lock);
+			goto resample_qdisc;
+		}

We could just drop the packet.

Ok, here is what I'll do as a rough plan:

1) Integrate this patch with your drop suggestion and ingress fixed up.

2) Integrate Jarek's patch that closes the "both bits clear" hole.

3) Add my bit that makes dev_deactivate() always take the spinlock so there is just one simple yield() loop.

And, finally, we can be at the point where we can get rid of the RCU deferral of qdisc_destroy().

Should be fun evening :-)

Quoted 12 lines

Ok, here is what I'll do as a rough plan:

1) Integrate this patch with your drop suggestion and ingress fixed up.

2) Integrate Jarek's patch that closes the "both bits clear" hole.

3) Add my bit that makes dev_deactivate() always take the spinlock so there is just one simple yield() loop.

Quoted 4 lines

And, finally, we can be at the point where we can get rid of the RCU deferral of qdisc_destroy().

Should be fun evening :-)

Worthy of a gold medal :)

All of this is now pushed to net-2.6 on kernel.org

Quoted 1 line

All of this is now pushed to net-2.6 on kernel.org

So i can build & test net-2.6 from git? :-)

From: Herbert Xu <[email protected]>
Date: Mon, 18 Aug 2008 11:36:33 +1000

Quoted 12 lines · David Miller

Quoted 10 lines

I think I see another way out of this:

1) Add __QDISC_STATE_DEACTIVATE.

2) Set it right before dev_deactivate() swaps resets the qdisc pointer.

3) Test it in dev_queue_xmit() et al. once the qdisc root lock is acquired, and drop lock and resample ->qdisc if __QDISC_STATE_DEACTIVATE is set.

Quoted 1 line

Yep this sounds good to me.

Here it is as a patch below.

The test being added to __netif_schedule() is just a reminder that we have to address the "both bits clear" case somehow, likely with Jarko's patch which I unintentionally reimplemented :)

include/net/sch_generic.h +1 -0

index a7abfda..757ab08 100644
@@ -27,6 +27,7 @@ enum qdisc_state_t
 {
 	__QDISC_STATE_RUNNING,
 	__QDISC_STATE_SCHED,
+	__QDISC_STATE_DEACTIVATED,
 };
 
 struct qdisc_size_table {

net/core/dev.c +10 -0

index 600bb23..b88f669 100644
@@ -1341,6 +1341,9 @@ static void dev_queue_xmit_nit(struct sk_buff *skb, struct net_device *dev)
 
 void __netif_schedule(struct Qdisc *q)
 {
+	if (unlikely(test_bit(__QDISC_STATE_DEACTIVATED, &q->state)))
+		return;
+
 	if (!test_and_set_bit(__QDISC_STATE_SCHED, &q->state)) {
 		struct softnet_data *sd;
 		unsigned long flags;

@@ -1790,6 +1793,8 @@ gso:
 	rcu_read_lock_bh();
 
 	txq = dev_pick_tx(dev, skb);
+
+resample_qdisc:
 	q = rcu_dereference(txq->qdisc);
 
 #ifdef CONFIG_NET_CLS_ACT

@@ -1800,6 +1805,11 @@ gso:
 
 		spin_lock(root_lock);
 
+		if (unlikely(test_bit(__QDISC_STATE_DEACTIVATED, &q->state))) {
+			spin_unlock(root_lock);
+			goto resample_qdisc;
+		}
+
 		rc = qdisc_enqueue_root(skb, q);
 		qdisc_run(q);
 

net/sched/sch_generic.c +6 -0

index 4685746..ff1c455 100644
@@ -597,6 +597,9 @@ static void transition_one_qdisc(struct net_device *dev,
 	struct Qdisc *new_qdisc = dev_queue->qdisc_sleeping;
 	int *need_watchdog_p = _need_watchdog;
 
+	if (!(new_qdisc->flags & TCQ_F_BUILTIN))
+		clear_bit(__QDISC_STATE_DEACTIVATED, &new_qdisc->state);
+
 	rcu_assign_pointer(dev_queue->qdisc, new_qdisc);
 	if (need_watchdog_p && new_qdisc != &noqueue_qdisc)
 		*need_watchdog_p = 1;

@@ -640,6 +643,9 @@ static void dev_deactivate_queue(struct net_device *dev,
 	if (qdisc) {
 		spin_lock_bh(qdisc_lock(qdisc));
 
+		if (!(qdisc->flags & TCQ_F_BUILTIN))
+			set_bit(__QDISC_STATE_DEACTIVATED, &qdisc->state);
+
 		dev_queue->qdisc = qdisc_default;
 		qdisc_reset(qdisc);
 

But, there is probably something other to bother here. I didn't get the final version of this patch nor I can see this on the list, but in your git there is this change to "goto out_kfree_skb", which seems to skip rcu_read_unlock_bh().

From: Herbert Xu <[email protected]>
Date: Mon, 18 Aug 2008 11:36:33 +1000

Quoted 11 lines · David Miller

Quoted 10 lines

I think I see another way out of this:

1) Add __QDISC_STATE_DEACTIVATE.

2) Set it right before dev_deactivate() swaps resets the qdisc pointer.

3) Test it in dev_queue_xmit() et al. once the qdisc root lock is acquired, and drop lock and resample ->qdisc if __QDISC_STATE_DEACTIVATE is set.

net/core/dev.c +2 -0

 	if (!test_and_set_bit(__QDISC_STATE_SCHED, &q->state)) {
 		struct softnet_data *sd;
 		unsigned long flags;

@@ -1790,6 +1793,8 @@ gso:
 	rcu_read_lock_bh();
 
 	txq = dev_pick_tx(dev, skb);
+
+resample_qdisc:
 	q = rcu_dereference(txq->qdisc);
 
 #ifdef CONFIG_NET_CLS_ACT

net/core/dev.c +0 -0

 		rc = qdisc_enqueue_root(skb, q);
 		qdisc_run(q);
 

Two little doubts below:

Quoted 6 lines

net/core/dev.c +0 -0

index 600bb23..b88f669 100644
@@ -1341,6 +1341,9 @@ static void dev_queue_xmit_nit(struct sk_buff *skb, struct net_device *dev)
 

net/core/dev.c static void dev_queue_xmit_nit(struct sk_buff *skb, struct net_device *dev) · line 1346

Quoted 5 lines

net/core/dev.c +3 -0

 void __netif_schedule(struct Qdisc *q)
 {
+	if (unlikely(test_bit(__QDISC_STATE_DEACTIVATED, &q->state)))
+		return;
+

Why I can't see this code in net-2.6? BTW, I guess it should be now moved to the current __netif_reschedule()?

OK, we now have this kfree_skb() with NET_XMIT_DROP here, but how is it better than qdisc_enque_root() on noop_qdisc? Or how can we have here anything else under both rcu lock and spin_lock() while this __QDISC_STATE_DEACTIVATED bit is set?

From: Jarek Poplawski <[email protected]>
Date: Mon, 18 Aug 2008 23:29:46 +0200

Quoted 8 lines

Two little doubts below:

Quoted 6 lines

net/core/dev.c +0 -0

index 600bb23..b88f669 100644
@@ -1341,6 +1341,9 @@ static void dev_queue_xmit_nit(struct sk_buff *skb, struct net_device *dev)
 

Quoted 8 lines

net/core/dev.c static void dev_queue_xmit_nit(struct sk_buff *skb, struct net_device *dev) · line 1346

Quoted 5 lines

net/core/dev.c +3 -0

 void __netif_schedule(struct Qdisc *q)
 {
+	if (unlikely(test_bit(__QDISC_STATE_DEACTIVATED, &q->state)))
+		return;
+

Why I can't see this code in net-2.6? BTW, I guess it should be now moved to the current __netif_reschedule()?

I deleted it, it's unnecessary with your "both bits clear" fix which I also added.

Quoted 11 lines

Quoted 8 lines

net/core/dev.c static void dev_queue_xmit_nit(struct sk_buff *skb, struct net_device *dev) · line 1345

Quoted 5 lines

void __netif_schedule(struct Qdisc *q)
{

net/core/dev.c +2 -0

+	if (unlikely(test_bit(__QDISC_STATE_DEACTIVATED, &q->state)))
+		return;

Why I can't see this code in net-2.6? BTW, I guess it should be now moved to the current __netif_reschedule()?

I deleted it, it's unnecessary with your "both bits clear" fix which I also added.

Herbert was concerned earlier with this:
"What I mean is the extremely unlikely scenario of net_tx_action always failing on trylock because dev_deactivate has grabbed the lock to check whether net_tx_action has completed."

So, I guess this could help here.

Quoted 17 lines

Quoted 11 lines

Quoted 8 lines

net/core/dev.c static void dev_queue_xmit_nit(struct sk_buff *skb, struct net_device *dev) · line 1345

Quoted 5 lines

void __netif_schedule(struct Qdisc *q)
{

net/core/dev.c +2 -0

+	if (unlikely(test_bit(__QDISC_STATE_DEACTIVATED, &q->state)))
+		return;

Why I can't see this code in net-2.6? BTW, I guess it should be now moved to the current __netif_reschedule()?

I deleted it, it's unnecessary with your "both bits clear" fix which I also added.

Herbert was concerned earlier with this:
"What I mean is the extremely unlikely scenario of net_tx_action always failing on trylock because dev_deactivate has grabbed the lock to check whether net_tx_action has completed."

Quoted 1 line

So, I guess this could help here.

Right. Even though the live-lock is an extremely unlikely event, as the aliveness flag check isn't on the fast path anyway I think we should keep it.

Every qdisc_run() will invoke __netif_schedule() so it is a fast path I think :-)

Quoted 3 lines · David Miller

Every qdisc_run() will invoke __netif_schedule() so it is a fast path I think :-)

Argh, I meant __netif_reschedule which shouldn't be the fast path.

Quoted 6 lines · David Miller

Quoted 3 lines

Every qdisc_run() will invoke __netif_schedule() so it is a fast path I think :-)

Argh, I meant __netif_reschedule which shouldn't be the fast path.

Nevermind, both paths call __netif_reschedule :)

OK, how about just moving it to the else clause in net_tx_action?

I just checked the following into net-2.6

From: Herbert Xu <[email protected]>
Date: Tue, 19 Aug 2008 20:58:15 +1000

Quoted 7 lines · Herbert Xu

Quoted 4 lines · David Miller

Quoted 2 lines

Every qdisc_run() will invoke __netif_schedule() so it is a fast path I think :-)

Argh, I meant __netif_reschedule which shouldn't be the fast path.

Nevermind, both paths call __netif_reschedule :)

Quoted 1 line

OK, how about just moving it to the else clause in net_tx_action?

I just checked the following into net-2.6

pkt_sched: Prevent livelock in TX queue running.

If dev_deactivate() is trying to quiesce the queue, it is theoretically possible for another cpu to livelock trying to process that queue. This happens because dev_deactivate() grabs the queue spinlock as it checks the queue state, whereas net_tx_action() does a trylock and reschedules the qdisc if it hits the lock.

This breaks the livelock by adding a check on __QDISC_STATE_DEACTIVATED to net_tx_action() when the trylock fails.

Based upon feedback from Herbert Xu and Jarek Poplawski.

Signed-off-by David S. Miller <[email protected]>

---
 net/core/dev.c |    4 +++-
 1 files changed, 3 insertions(+), 1 deletions(-)

net/core/dev.c +3 -1

index 8d13380..60c51f7 100644
@@ -1990,7 +1990,9 @@ static void net_tx_action(struct softirq_action *h)
 				qdisc_run(q);
 				spin_unlock(root_lock);
 			} else {
-				__netif_reschedule(q);
+				if (!test_bit(__QDISC_STATE_DEACTIVATED,
+					      &q->state))
+					__netif_reschedule(q);
 			}
 		}
 	}

I can miss something, but probably it's needed in __netif_reschedule()

yet. Here is a scenario:

cpu1 cpu2
dev_deactivate()
dev_deactivate_queue()
qdisc_reset()

				qdisc_run()
				qdisc_watchdog_schedule()
				(or hrtimer_restart in cbq)

Quoted 2 lines · Jarek Poplawski

I can miss something, but probably it's needed in __netif_reschedule()

No this is a genuine bug. However, it's also an old bug :) Even with the locking and RCU barrier it could have occured.

Quoted 9 lines

yet. Here is a scenario:

cpu1 cpu2
dev_deactivate()
dev_deactivate_queue()
qdisc_reset()

				qdisc_run()
				qdisc_watchdog_schedule()
				(or hrtimer_restart in cbq)

We should add an aliveness check before scheduling the timer. This is the slow path so adding a check shouldn't hurt.

pkt_sched: Fix qdisc_watchdog() vs. dev_deactivate() race

dev_deactivate() can skip rescheduling of a qdisc by qdisc_watchdog() or other timer calling netif_schedule() after dev_queue_deactivate(). We prevent this checking aliveness before scheduling the timer.

With feedback from Herbert Xu <[email protected]>

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

pkt_sched: Fix qdisc_watchdog() vs. dev_deactivate() race

dev_deactivate() can skip rescheduling of a qdisc by qdisc_watchdog() or other timer calling netif_schedule() after dev_queue_deactivate(). We prevent this checking aliveness before scheduling the timer.

With feedback from Herbert Xu <[email protected]>

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

---

 net/sched/sch_api.c |    3 +++
 net/sched/sch_cbq.c |    3 +++
 2 files changed, 6 insertions(+), 0 deletions(-)

net/sched/sch_api.c +3 -0

index ef0efec..6f2bc7f 100644
@@ -444,6 +444,9 @@ void qdisc_watchdog_schedule(struct qdisc_watchdog *wd, psched_time_t expires)
 {
 	ktime_t time;
 
+	if (test_bit(__QDISC_STATE_DEACTIVATED, &qdisc_root(wd->qdisc)->state))
+		return;
+
 	wd->qdisc->flags |= TCQ_F_THROTTLED;
 	time = ktime_set(0, 0);
 	time = ktime_add_ns(time, PSCHED_US2NS(expires));

net/sched/sch_cbq.c +3 -0

index 47ef492..c04d335 100644
@@ -521,6 +521,9 @@ static void cbq_ovl_delay(struct cbq_class *cl)
 	struct cbq_sched_data *q = qdisc_priv(cl->qdisc);
 	psched_tdiff_t delay = cl->undertime - q->now;
 
+	if (test_bit(__QDISC_STATE_DEACTIVATED, &qdisc_root(cl->qdisc)->state))
+		return;
+
 	if (!cl->delayed) {
 		psched_time_t sched = q->now;
 		ktime_t expires;

---------------> (take 2)

pkt_sched: Fix qdisc_watchdog() vs. dev_deactivate() race

dev_deactivate() can skip rescheduling of a qdisc by qdisc_watchdog() or other timer calling netif_schedule() after dev_queue_deactivate(). We prevent this checking aliveness before scheduling the timer. Since during deactivation the root qdisc is available only as qdisc_sleeping additional accessor qdisc_root_sleeping() is created.

With feedback from Herbert Xu <[email protected]>

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

Quoted 8 lines

include/net/sch_generic.h +0 -0

index 84d25f2..b1d2cfe 100644
@@ -193,6 +193,11 @@ static inline struct Qdisc *qdisc_root(struct Qdisc *qdisc)
 	return qdisc->dev_queue->qdisc;
 }
 

include/net/sch_generic.h static inline struct Qdisc *qdisc_root(struct Qdisc *qdisc) · line 199

Quoted 4 lines

include/net/sch_generic.h +4 -0

+static inline struct Qdisc *qdisc_root_sleeping(struct Qdisc *qdisc)
+{
+	return qdisc->dev_queue->qdisc_sleeping;
+}

When would we actually want the non-sleeping variant?

We need to check if something depends on &noop_qdisc returned in the similar state. Otherwise, there is a bit too much possibilities here, so it would be nice to simplify this all.

Actually, why do we even keep a netdev_queue pointer in a qdisc? A given qdisc can be used by multiple queues (which is why the lock was moved into the qdisc in the first place).

How about keeping a pointer directly to the root qdisc plus a pointer to the netdev (which seems to be the only other use for qdisc->dev_queue)? That way there won't be any confusion as to whether we want the sleeping or non-sleeping qdisc.

If I get a chance I'll work on this. But to be honest given Linus's temperment right now we're only going to be able to merge one-liners to fix these kinds of problems and anything more serious is going to be for net-next-2.6 only.

From: Herbert Xu <[email protected]>
Date: Thu, 21 Aug 2008 17:16:34 +1000

Quoted 8 lines

Actually, why do we even keep a netdev_queue pointer in a qdisc? A given qdisc can be used by multiple queues (which is why the lock was moved into the qdisc in the first place).

How about keeping a pointer directly to the root qdisc plus a pointer to the netdev (which seems to be the only other use for qdisc->dev_queue)? That way there won't be any confusion as to whether we want the sleeping or non-sleeping qdisc.

Not a bad idea at all.

The reason it's there is a left-over from earlier designs of my multiqueue stuff, I thought we'd always multiplex the qdiscs to be per-queue. But once Patrick showed me we couldn't do that, we now have shared qdiscs.

If I get a chance I'll work on this. But to be honest given Linus's temperment right now we're only going to be able to merge one-liners to fix these kinds of problems and anything more serious is going to be for net-next-2.6 only.

Probably it's too early in the morning,

BTW, it looks like currently we do this wrong: if it's really dectivated we're checking &noop_qdisc for this...

On Thu, Aug 21, 2008 at 08:27:21AM +0000, Jarek Poplawski wrote:
...

Quoted 1 line

Probably it's too early in the morning,

It's for sure...

Quoted 2 lines

BTW, it looks like currently we do this wrong: if it's really dectivated we're checking &noop_qdisc for this...

...and it's OK, yet.

From: Herbert Xu <[email protected]>
Date: Thu, 21 Aug 2008 17:16:34 +1000

Quoted 8 lines

Actually, why do we even keep a netdev_queue pointer in a qdisc? A given qdisc can be used by multiple queues (which is why the lock was moved into the qdisc in the first place).

How about keeping a pointer directly to the root qdisc plus a pointer to the netdev (which seems to be the only other use for qdisc->dev_queue)? That way there won't be any confusion as to whether we want the sleeping or non-sleeping qdisc.

Not a bad idea at all.

The reason it's there is a left-over from earlier designs of my multiqueue stuff, I thought we'd always multiplex the qdiscs to be per-queue. But once Patrick showed me we couldn't do that, we now have shared qdiscs.

I got to looking into this and we do need the qdisc->dev_queue member, see qdisc_run(). So it's not like we can get rid of it if we replace it with ->netdevdev and add a ->root_qdisc backpointer as well.

Quoted 4 lines

I got to looking into this and we do need the qdisc->dev_queue member, see qdisc_run(). So it's not like we can get rid of it if we replace it with ->netdevdev and add a ->root_qdisc backpointer as well.

That can't be right. Let's I've got a single qdisc shared by n queues. It makes no sense for qdisc_run to decide to whether it should process the qdisc depending on the status of a single one out of the n queues.

Well some kind of check has to be there.

I _did_ remove it during my initial implementation, and that turned into a reported performance regression.

Quoted 5 lines

Well some kind of check has to be there.

I _did_ remove it during my initial implementation, and that turned into a reported performance regression.

I see. How about looking at the queue that the head-of-qdisc packet maps to? That should be fairly cheap to compute.

This gets us back to the whole qdisc->ops->peek() discussion :)

And we don't have the qdisc lock here, taking it is undesirable, and if we do take it we have to transfer that lock down into __qdisc_run() which means adjusting all the other __qdisc_run() callers.

Quoted 4 lines

And we don't have the qdisc lock here, taking it is undesirable, and if we do take it we have to transfer that lock down into __qdisc_run() which means adjusting all the other __qdisc_run() callers.

Last I checked qdisc_run did run under the root lock...

Ok, so implementing ->peek() is the first step in dealing with this.

From: David Miller <[email protected]>
Date: Thu, 11 Sep 2008 04:47:17 -0700 (PDT)

Quoted 2 lines

Ok, so implementing ->peek() is the first step in dealing with this.

Ok, here's a first cut at this.

Most of it is simple and straightforward.

As usual, though, CBQ, HFSC, and HTB are complicated.

Most of the peek implementations just skb_peek() in their downstream queue or iterate over their prio array doing the same looking for a non-empty list.

But CBQ, HFSC, and HTB have complicated class iterators and internal time state machine things. I tried to do my best in these cases.

I didn't want these things firing off class watchdog timers and stuff like this. Just see if there is any packet ready now and return it.

The one exception is that I allow CBQ to advance it's time state machine.

Alas I'm still not sure how this whole peek idea is going to be implemented (dequeuing after peeking doesn't have to give us the same skb since in the meantime e.g. in HTB some other class with higher prio can get enough tokens etc., and if there is a break for transmit in the meantime with possible enqueuing, or we can deal with something like sch_multiq, which depends on the current state of the tx_queues, this all looks even more interesting).

From: Jarek Poplawski <[email protected]>
Date: Fri, 12 Sep 2008 08:02:49 +0000

Quoted 7 lines

Alas I'm still not sure how this whole peek idea is going to be implemented (dequeuing after peeking doesn't have to give us the same skb since in the meantime e.g. in HTB some other class with higher prio can get enough tokens etc., and if there is a break for transmit in the meantime with possible enqueuing, or we can deal with something like sch_multiq, which depends on the current state of the tx_queues, this all looks even more interesting).

That's a good point.

Well, once that is discussed and resolved, at least the patch I posted can be used as a base for implementation :-)

Quoted 2 lines

Well, once that is discussed and resolved, at least the patch I posted can be used as a base for implementation :-)

Well we should remember the skb returned by peek, and then return it on the next dequeue. If peek hasn't been called since the last dequeue then it's equivalent to the current dequeue.

This works for the two scenarios where we're planning to use peek since they'll both call dequeue immediately.

It'd even work if there was a large gap (i.e., a sleep) after the peek since we'd just peek again after waking up.

This requires state, for the unlink. And that unlink point could be several levels deep into the tree.

There is also currently no restriction on how a packet scheduler maintains it's queue of SKBs.

So, if the idea is to keep track of the skb_queue_head pointer to unlink from at the root, I don't think that's a good idea.

And then there are all of these complicated pieces of state the classful qdiscs modify when a SKB is removed from their visibility. So, the unlink isn't just a simple list delete operation. There are queue lengths that need to be updated, watchdog timers to manage, etc.

Quoted 5 lines

And then there are all of these complicated pieces of state the classful qdiscs modify when a SKB is removed from their visibility. So, the unlink isn't just a simple list delete operation. There are queue lengths that need to be updated, watchdog timers to manage, etc.

The decision really comes down to whether it's harder to requeue a seemingly arbitrary packet or whether it's harder to dequeue the packet that was last peeked.

My current opinion is that both operations are equally difficult. With the slight advantage for ->requeue() because all the complicated logic is already implemented :-)

Quoted 4 lines · David Miller

My current opinion is that both operations are equally difficult. With the slight advantage for ->requeue() because all the complicated logic is already implemented :-)

I'd agree with you if you haven't written the peek stuff :)

Now that peek exists, the dequeue stuff would be a lot simpler than requeue because the only non-trivial logic would be in the leaf qdiscs. All the complex/classful qdiscs would be trivial as they'd just write down the child qdisc that was peeked and then call dequeue on that child.

If I get it right peek + dequeue should do all current dequeue logic plus additionally write down the child qdisc or skb (leaves) info, plus, probably, some ifs btw., which looks like a bit of overhead, if we consider requeuing as something exceptional. Unless we don't - then of course something like this could be useful.

Quoted 6 lines · Jarek Poplawski

If I get it right peek + dequeue should do all current dequeue logic plus additionally write down the child qdisc or skb (leaves) info, plus, probably, some ifs btw., which looks like a bit of overhead, if we consider requeuing as something exceptional. Unless we don't - then of course something like this could be useful.

I don't see the overhead in writing down something that we alrady have. In any case, do you have an alternative solution to the current problem that qdisc_run looks at an arbitrary queue's status to decide whether it should process a qdisc that empties into n queues?

What if we were to push the check for netif_tx_queue_stopped further down into the qdisc layer so that the basic qdiscs such as pfifo_fast did their own peek and in the event that a queue is stopped it just returned NULL and set a flag bit? Basically this would mimic how we are currently handling throttled queues (TCQ_F_THROTTLED). Then in turn each parent could do a check on skb == NULL and set the same flag, or they could act like multiq and just skip over that leaf and move onto the next because it is stopped.

On the other hand, I wondered about a possibility of rehashing to other queues in some cases during requeuing, which would be impossible after such change.

Quoted 4 lines · Jarek Poplawski

On the other hand, I wondered about a possibility of rehashing to other queues in some cases during requeuing, which would be impossible after such change.

Why would you want to do that? Just because people have abused requeue in the psat doesn't mean that we need to support such abuses for perpetuity.

Well, it was only wondering, and probably you are right this is wrong. On the other hand, simple_tx_hash() choices are "probabilistic": user doesn't care if it goes through tx_queue #1 or #11. And here, in some cases, some tx_queues could be always full while other always empty, so some dynamic rehashing could be thought of, but I understand it's not trivial.

Quoted 7 lines · Jarek Poplawski

Well, it was only wondering, and probably you are right this is wrong. On the other hand, simple_tx_hash() choices are "probabilistic": user doesn't care if it goes through tx_queue #1 or #11. And here, in some cases, some tx_queues could be always full while other always empty, so some dynamic rehashing could be thought of, but I understand it's not trivial.

No that would be totally wrong. One of the important constraints on a TX hashing mechanism is to preserve packet ordering within a flow. If simple_tx_hash started placing the same packet in different queues then it would do the same thing to flows which is unacceptable.

Of course preserving a flow consistency is must-be here, but I think there are rehashing algorithms used in similar cases (sch_sfq) which take care for this. As a matter of fact, I've thought of requeuing as a best place to detect possible problems, but now I see that Alexander's proposal let's to do this simply by observing this TCQ_F_STOPPED flag [...]

On Mon, Sep 15, 2008 at 07:20:08AM +0000, Jarek Poplawski wrote:
...

Quoted 6 lines

Of course preserving a flow consistency is must-be here, but I think there are rehashing algorithms used in similar cases (sch_sfq) which take care for this. As a matter of fact, I've thought of requeuing as a best place to detect possible problems, but now I see that Alexander's proposal let's to do this simply by observing this TCQ_F_STOPPED flag [...]

Hmm... or maybe it doesn't? Since this is qdisc flag we don't know at the top which tx_queue is a problem at the bottom...

The only thing I really prefer about my solution as opposed to the solution Dave implemented was that it would mean only one dequeue instead of a peek followed by a dequeue. I figure the important thing is to push the discovery of us being stopped to as soon as possible in the process.

It will probably be a few days before I have a patch with my approach ready. I didn't realize how complex it would be to resolve this issue for CBQ, HTB, HFSC, etc. Also it is starting to look like I will probably need to implement another function to support this since it seems like the dequeue operations would need to be split into a multiqueue safe version, and a standard version to support some workarounds like those found in qdisc_peek_len() for HFSC.

On Mon, Sep 15, 2008 at 04:44:08PM -0700, Duyck, Alexander H wrote:
...

Quoted 11 lines

The only thing I really prefer about my solution as opposed to the solution Dave implemented was that it would mean only one dequeue instead of a peek followed by a dequeue. I figure the important thing is to push the discovery of us being stopped to as soon as possible in the process.

It will probably be a few days before I have a patch with my approach ready. I didn't realize how complex it would be to resolve this issue for CBQ, HTB, HFSC, etc. Also it is starting to look like I will probably need to implement another function to support this since it seems like the dequeue operations would need to be split into a multiqueue safe version, and a standard version to support some workarounds like those found in qdisc_peek_len() for HFSC.

Actually, looking at this HFSC now I start to doubt we need to complicate these things so much. If HFSC is OK with its simple hfsc_requeue() I doubt other qdiscs need much more, and we should reconsider David's idea to do the same on top, in dev_requeue_skb(). Qdiscs like multiq would probably never use this, and these above mentioned (not mq-optimized) qdiscs could be used with multiq if needed. Then, it seems, it would be enough to improve multiq as a "leaf" adding these dedicated operations and/or flags.

Thanks,
Jarek P.

In any case, do you have an alternative solution to the current problem that qdisc_run looks at an arbitrary queue's status to decide whether it should process a qdisc that empties into n queues?

Quoted 6 lines · Jarek Poplawski

If I get it right peek + dequeue should do all current dequeue logic plus additionally write down the child qdisc or skb (leaves) info, plus, probably, some ifs btw., which looks like a bit of overhead, if we consider requeuing as something exceptional. Unless we don't - then of course something like this could be useful.

I don't see the overhead in writing down something that we alrady have. In any case, do you have an alternative solution to the current problem that qdisc_run looks at an arbitrary queue's status to decide whether it should process a qdisc that empties into n queues?

Anyway, the main problem here was a high cpu load despite stopped queue. Are you sure this peek, which is almost full dequeue, can really help for this? BTW, since after current fix there were no later complains I guess it's just about full netif_stop or non-mq device.

The cpu utilization savings exist for case #1 only, and we can implement the bypass logic _perfectly_ as described above.

For #2 there is nothing to check, just do it and see what comes out of the qdisc.

Quoted 6 lines

The cpu utilization savings exist for case #1 only, and we can implement the bypass logic _perfectly_ as described above.

For #2 there is nothing to check, just do it and see what comes out of the qdisc.

Your analysis sounds perfect to me. And I'm sure happy to see this thread die as it's starting to take up a significant amount of space in my mailbox :)

Let's look at what actually matters for cpu utilization. These __qdisc_run() things are invoked in two situations where we might block on the hw queue being stopped:

1) When feeding packets into the qdisc in dev_queue_xmit().

Guess what? We _know_ the queue this packet is going to hit.

The only new thing we can possible trigger and be interested in at this specific point is if _this_ packet can be sent at this time.

And we can check that queue mapping after the qdisc_enqueue_root() call, so that multiq aware qdiscs can have made their changes.

2) When waking up a queue. And here we should schedule the qdisc_run _unconditionally_.

If the queue was full, it is extremely likely that new packets are bound for that device queue. There is no real savings to be had by doing this peek/requeue/dequeue stuff.

The cpu utilization savings exist for case #1 only, and we can implement the bypass logic _perfectly_ as described above.

For #2 there is nothing to check, just do it and see what comes out of the qdisc.

I would suggest adding an skb pointer argument to qdisc_run(). If it's NULL, unconditionally schedule __qdisc_run(). Else, only schedule if the TX queue indicated by skb_queue_mapping() is not stopped.

dev_queue_xmit() will use the "pass the skb" case, but only if qdisc_enqueue_root()'s return value doesn't indicate that there is a potential drop. On potential drop, we'll pass NULL to make sure we don't potentially reference a free'd SKB.

The other case in net_tx_action() can always pass NULL to qdisc_run().

...

Quoted 5 lines

Let's look at what actually matters for cpu utilization. These __qdisc_run() things are invoked in two situations where we might block on the hw queue being stopped:

1) When feeding packets into the qdisc in dev_queue_xmit().

Quoted 2 lines

2) When waking up a queue. And here we should schedule the qdisc_run _unconditionally_.

Quoted 5 lines

The cpu utilization savings exist for case #1 only, and we can implement the bypass logic _perfectly_ as described above.

For #2 there is nothing to check, just do it and see what comes out of the qdisc.

Right, unless __netif_schedule() wasn't done when waking up. I've thought about this because of another thread/patch around this problem, and got misled by dev_requeue_skb() scheduling. Now, I think this could be the main reason for this high load. Anyway, if we want to skip this check for #2 I think something like the patch below is needed.

Therefore it seems logical that what really needs to happen is that we simply pick some new local special token value for 'ret' so that we can handle that case. "-1" would probably work fine.

I also think the qdisc_run() test needs to be there. When the TX queue fills up, we will doing tons of completely useless work going:

Ok, here is the kind of thing I'm suggesting in all of this.

It gets rid of bouncing unnecessarily into __qdisc_run() when dev_queue_xmit()'s finally selected TXQ is stopped.

It also gets rid of the dev_requeue_skb() looping case Jarek discovered.

Going back to the case of prio, I think what we should do is to create a separate qdisc queue for each band. The qdisc selection should be done before the packet is queued, just as we do in the TX hashing case.

This works if you want it at the root, but what if you only wanted to prio at a leaf? I think that case has value too.

I tend to also disagree with another mentioned assertion. The one where having a shared qdisc sucks on SMP. It doesn't. The TX queue lock is held much longer than the qdisc lock.

Quoted 3 lines · David Miller

This works if you want it at the root, but what if you only wanted to prio at a leaf? I think that case has value too.

Good question :)

I think what we should do is to pass some token that rerepsents the TX queue that's being run down into the dequeue function.

Then each qdisc can decide which child to recursively dequeue based on that token (or ignore it for non-prio qdiscs such as HTB).

When the token reaches the leaf then we have two cases:
1) A prio-like qdisc that has separate queues based on priorities. In this case we dequeue the respective queue based on the token.

Quoted 4 lines

Then each qdisc can decide which child to recursively dequeue based on that token (or ignore it for non-prio qdiscs such as HTB).

I don't think HTB could be considered as a non-prio qdisc.

As matter of fact I can't figure out this idea of a prio at the root or leaf either. Could you explain in which point do you expect the gain? If it's about the locks, what kind of synchronization would be used to assure packets from lower prio queues (or qdiscs?) aren't sent to free tx queues, while higher prio wait on stopped ones?

Quoted 6 lines · Jarek Poplawski

Quoted 4 lines

Then each qdisc can decide which child to recursively dequeue based on that token (or ignore it for non-prio qdiscs such as HTB).

I don't think HTB could be considered as a non-prio qdisc.

It is non-prio in the sense that it has other criteria for deciding which child qdisc to enqueue into.

Quoted 5 lines

As matter of fact I can't figure out this idea of a prio at the root or leaf either. Could you explain in which point do you expect the gain? If it's about the locks, what kind of synchronization would be used to assure packets from lower prio queues (or qdiscs?) aren't sent to free tx queues, while higher prio wait on stopped ones?

It's very simple really. For a non-leaf prio you determine which child qdisc to enqueue into using the priority. For a leaf prio you determine which software queue to enqueue into based on the priority.

To put it another way, what I'm saying is that instead of duplicating the qdiscs as we do now for pfifo_fast, we should make the leaf qdiscs duplicate its software queues to match the hardware queues it's feeding into.

From: David Miller <[email protected]>
Date: Sat, 20 Sep 2008 22:35:38 -0700 (PDT)

Quoted 3 lines

Therefore it seems logical that what really needs to happen is that we simply pick some new local special token value for 'ret' so that we can handle that case. "-1" would probably work fine.

...

Quoted 2 lines

I also think the qdisc_run() test needs to be there. When the TX queue fills up, we will doing tons of completely useless work going:

Ok, here is the kind of thing I'm suggesting in all of this.

It gets rid of bouncing unnecessarily into __qdisc_run() when dev_queue_xmit()'s finally selected TXQ is stopped.

It also gets rid of the dev_requeue_skb() looping case Jarek discovered.

include/net/pkt_sched.h +1 -4

index b786a5b..4082f39 100644
@@ -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) &&
-	    !test_and_set_bit(__QDISC_STATE_RUNNING, &q->state))
+	if (!test_and_set_bit(__QDISC_STATE_RUNNING, &q->state))
 		__qdisc_run(q);
 }
 

net/core/dev.c +0 -0

index fdfc4b6..4654127 100644

net/core/dev.c +5 -0

+				txq = netdev_get_tx_queue(dev, map);
+			}
+
+			if (!txq || !netif_tx_queue_stopped(txq))
+				qdisc_run(q);
 		}
 		spin_unlock(root_lock);
 

net/sched/sch_generic.c +1 -1

index ec0a083..b6e6926 100644
@@ -117,7 +117,7 @@ static inline int handle_dev_cpu_collision(struct sk_buff *skb,
 static inline int qdisc_restart(struct Qdisc *q)
 {
 	struct netdev_queue *txq;
-	int ret = NETDEV_TX_BUSY;
+	int ret = -2;
 	struct net_device *dev;
 	spinlock_t *root_lock;
 	struct sk_buff *skb;

From: Jarek Poplawski <[email protected]>
Date: Sun, 21 Sep 2008 01:48:43 +0200

Quoted 7 lines · David Miller

...

Quoted 5 lines

Let's look at what actually matters for cpu utilization. These __qdisc_run() things are invoked in two situations where we might block on the hw queue being stopped:

1) When feeding packets into the qdisc in dev_queue_xmit().

...

Quoted 2 lines

Quoted 2 lines

2) When waking up a queue. And here we should schedule the qdisc_run _unconditionally_.

...

Quoted 6 lines

Quoted 5 lines

The cpu utilization savings exist for case #1 only, and we can implement the bypass logic _perfectly_ as described above.

For #2 there is nothing to check, just do it and see what comes out of the qdisc.

Quoted 6 lines

Right, unless __netif_schedule() wasn't done when waking up. I've thought about this because of another thread/patch around this problem, and got misled by dev_requeue_skb() scheduling. Now, I think this could be the main reason for this high load. Anyway, if we want to skip this check for #2 I think something like the patch below is needed.

Hmmm, looking at your patch....

It's only doing something new when the driver returns NETDEV_TX_BUSY from ->hard_start_xmit().

That _never_ happens in any sane driver. That case is for buggy devices that do not maintain their TX queue state properly. And in fact it's a case for which I advocate we just drop the packet instead of requeueing. :-)

Oh I see, you're concerned about that cases where qdisc_restart() ends up using the default initialization of the 'ret' variable.

Really, for the case where the driver actually returns NETDEV_TX_BUSY we _do_ want to unconditionally __netif_schedule(), since the device doesn't maintain it's queue state in the normal way.

Therefore it seems logical that what really needs to happen is that we simply pick some new local special token value for 'ret' so that we can handle that case. "-1" would probably work fine.

So I'm dropping your patch.

I also think the qdisc_run() test needs to be there. When the TX queue fills up, we will doing tons of completely useless work going:

1) ->dequeue
2) qdisc unlock
3) TXQ lock
4) test state
5) TXQ unlock
6) qdisc lock
7) ->requeue

for EVERY SINGLE packet that is generated towards that device.

That has to be expensive,

and I am still very much convinced that
this was the original regression cause that made me put that TXQ state test back into qdisc_run().

Quoted 4 lines

That _never_ happens in any sane driver. That case is for buggy devices that do not maintain their TX queue state properly. And in fact it's a case for which I advocate we just drop the packet instead of requeueing. :-)

OK, then let's do it! Why I can't see this in your new patch?

BTW, since this problem is strongly conected with the requeuing policy, I wonder why you seemingly lost interest in this. I tried to advocate for your simple, one level requeuing, but also Herbert's peek, and Alexander's early detection, after some polish(!), should make this initial test meaningless.

Quoted 3 lines

and I am still very much convinced that
this was the original regression cause that made me put that TXQ state test back into qdisc_run().

I doubt this: I've just looked at this Andrew Gallatin's report, and there is really a lot of net_tx_action, __netif_schedule, and guess
what: pfifo_fast_requeue in this oprofile...

From: Jarek Poplawski <[email protected]>
Date: Sun, 21 Sep 2008 11:57:06 +0200

Quoted 5 lines

BTW, since this problem is strongly conected with the requeuing policy, I wonder why you seemingly lost interest in this. I tried to advocate for your simple, one level requeuing, but also Herbert's peek, and Alexander's early detection, after some polish(!), should make this initial test meaningless.

Yes, thanks for reminding me about the the multiq qdisc head of line blocking thing.

I really don't like the requeue/peek patches, because they resulted in so much code duplication in the CBQ and other classful qdiscs.

Alexander's patch has similar code duplication issues.

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 you don't know what is going to pop out until you go in and check.

That's why I think you should reconsider this simple solution for now, until somebody proves this is wrong or something else is better.

From: Jarek Poplawski <[email protected]>
Date: Sun, 21 Sep 2008 13:15:51 +0200

Quoted 2 lines

That's why I think you should reconsider this simple solution for now, until somebody proves this is wrong or something else is better.

Ok, that sounds reasonable. I've added those three patches to net-next-2.6 and will push those out after some build tests.

OK, then we have to say B and try this all. BTW, I guess, after this change we could have similar effect as reported by Alexander Duyck while testing his solution for this problem, namely the higher drop rate in some cases, which I can only explain as: less time in requeuing more time for new enqueuing. Of course, if I'm right, this "bug" should be rather "fixed" with longer queues or some other throttle mechanism.

pkt_sched: Remove the tx queue state check in qdisc_run()

The current check wrongly uses the state of one (currently the first) tx queue for all tx queues in case of non-default qdiscs. This check mainly prevented requeuing loop with __netif_schedule(), but now it's controlled inside __qdisc_run(), while dequeuing. The wrongness of this check was first noticed by Herbert Xu.

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

Quoted 5 lines · David Miller

Well some kind of check has to be there.

I _did_ remove it during my initial implementation, and that turned into a reported performance regression.

I see. How about looking at the queue that the head-of-qdisc packet maps to? That should be fairly cheap to compute.