: Remove unnecessary tx_lock

There is no need for tx_locking if you are already netif stopped (transmit path will never be entered).
With this change under high speed forwarding i see anywhere between 2-4Kpps improvement on a 2 CPU environment with twoo e1000s tied to different CPUs forwarding between each other. Actually the performance improvement should be attributed to the use of TX_WAKE_THRESHOLD - more drivers should use that technique.

cheers,
jamal

-----

index da62db8..559e334 100644
@@ -3517,11 +3517,8 @@ #endif
 #define TX_WAKE_THRESHOLD 32
 	if (unlikely(cleaned && netif_queue_stopped(netdev) &&
 	             netif_carrier_ok(netdev))) {
-		spin_lock(&tx_ring->tx_lock);
-		if (netif_queue_stopped(netdev) &&
-		    (E1000_DESC_UNUSED(tx_ring) >= TX_WAKE_THRESHOLD))
+		if (E1000_DESC_UNUSED(tx_ring) >= TX_WAKE_THRESHOLD)
 			netif_wake_queue(netdev);
-		spin_unlock(&tx_ring->tx_lock);
 	}
 
 	if (adapter->detect_tx_hung) {

Looks good to me.

Even if we get it wrong and wake up something that we shouldn't have, the xmit function will simply bail out and stop the queue for us.

Since this is exceedingly unlikely we should drop the locks rather than bother about it.

Cheers,

Visit Openswan at http://www.openswan.org/
Email: Herbert Xu ~{PmV>HI~} <[email protected]>
Home Page: http://gondor.apana.org.au/~herbert/
PGP Key: http://gondor.apana.org.au/~herbert/pubkey.txt

Infact thats close to what i was seeing. setup is:
eth0 tied to cpu 0
eth1 tied to cpu1

--> eth0 -- forward --> eth1
--> eth1 -- forward --> eth0

Take the example of eth1:
* It is actually being fed packets by cpu0 but is tied to cpu1.

The stop happens in cpu0 (99.99999% of the time) and the wake happens in cpu1 (100% of the time)[1]. The wakes on most occasions dont even get to run tx softirq on cpu1 since there is constant activity already happening on cpu0. So that lock being grabbed was causing a collision on the tx path which caused a requeue which caused a reschedule on cpu0 - all this unnecessarily.

I should say that the fact that e1000 does its pruning of descriptors only on the tx path makes the locking unnecessary when stopped.

cheers,
jamal

[1] As you may know this comes from testing your qdisc_is_running change. I was hoping to induce a DOS attack such that a cpuX is busy processing packets from another CPU (eg eth1 on cpu1) so that it forgets to process its own receive path ;-> This is a theoretical possibility with that change ;-> Clearly i failed given the % above ;->

jamal, thanks for the investigation, but this doesn't look so good to me.

I followed the example of tg3 when attempting to optimize this code. For the normal case we remove a lock acquisition. Jamals case is not normal. :-)

we specifically added this lock originally to fix a problem we saw where the netif_stop and netif_start would race, and we would end up with a queue that was stopped, and no way to restart it because we didn't have any more TX packets to clean up (even if we DID get an interrupt from a receive)

I think that would be nice, but I still think the current driver solution is a good stable solution that has made it through several rounds of testing here, not to mention is in the tg3.c code. Unless someone can come up with a way to avoid the race between start and stop *inside* the start and stop code (which would be ideal) then I think we have to have a solution like this in the driver.

Jesse

Yep, I agree that the lock is necessary. The reason is that hard_start_xmit and xmit_completion can be running concurrently and they can miss each other and cause the tx ring to be stopped forever.

In the case of tg3's hard_start_xmit, after stopping the queue, we need to check if we should wake the queue right away in case xmit_completion just finished cleaning the tx ring and just missed the queue_stopped condition. Because the netif_wake_queue can be called in 2 places, you need the lock. Without the lock, the queue can be waken up at the wrong time and may cause hard_start_xmit to be called with an empty tx ring.

Logic is you are stopped, the tx path can _never_ be entered by the core. If it is you have a bug somewhere else.
Tx and rx do run concurently but not when you are stopped.

Is this to protect against some hardware bug?

Yes in your case you need to hold the lock but not in the e1000 case. I dont understand though why you need to check for wake in the tx path.

cheers,
jamal

tg3_start_xmit()

	if (tx_ring_empty)
				<-  tg3_tx()
		netif_stop_queue()

At the arrow, tg3_tx() can come in and clean up the entire ring but will not see that the queue is stopped and therefore will not call netif_wake_queue(). As a result, the tx_queue is stopped forever.

Good point. I missed that. However, this only goes to show that even the current code (e1000 that is, I haven't checked tg3) is also unsafe.

Why? Because the tx_lock is only taken in e1000_clean_tx_irq if the queue is stopped. As you can see in your diagram above, the queue could well be awake at the point where e1000_clean_tx_irq runs.

So we need to fix e1000 anyway.

Cheers,

Visit Openswan at http://www.openswan.org/
Email: Herbert Xu ~{PmV>HI~} <[email protected]>
Home Page: http://gondor.apana.org.au/~herbert/
PGP Key: http://gondor.apana.org.au/~herbert/pubkey.txt

Here is a fix that also gets rid of the tx_lock on the wake up side. Please scrutinise this as much as you can. Jamal, please run this through your performance test to see if it has a similar effect as your original patch.

A similar patch is needed for tg3.

[NETDRV] e1000: Fix potential tx wake up race

Jamal posted a patch which improved e1000 TX performance. That in turn spawned a discussion on potential tx wake up races caused by the change. During that discussion, Michael Chan posted the following scenario (redrawn by me for e1000):

CPU0 CPU1
e1000_xmit_frame

	tx_lock
	if (tx_ring_empty)
					e1000_clean_tx_irq
						if (netif_queue_stopped)
							tx_lock
							netif_wake_queue
							tx_unlock
		netif_stop_queue
	tx_unlock

As you can see, even with the locks around netif_wake_queue this still allows the race to occur because the netif_wake_queue code path is conditional on netif_queue_stopped.

So here is a patch that uses the memory barriers rather than spin locks to solve the problem.

First of all I've made netif_wake_queue independent of netif_queue_stopped. This means that we operate on the stopped bit only once which closes a race window.

Furthermore, netif_wake_queue itself is already a memory barrier because it does a test_and_clear_bit. This means that if the other side can observe the netif_wake_queue then it can observe the extra room we've made on the
queue.

On the e1000_xmit_frame side, I've changed netif_stop_queue into a new function netif_test_and_stop_queue which does test_and_set_bit. This means that it also is a full memory barrier.

In order to close the race then, we simply recheck the tx queue size if netif_test_and_stop_queue returns 0 indicating that the queue was previously started. There are two possibilities:

1) netif_wake_queue is about to occur. In this case it doesn't really matter what we do as netif_wake_queue will always wake the queue for us. In the worst case, it'll wake up the queue with too little room but that's really uncommon and we can cope with that anyway.

2) netif_wake_queue has just occured. Because it is a memory barrier, when we recheck the queue size we're guaranteed to see the new indices which means that we'll see the extra room it has made for us. As a result we'll simply restart the queue.

The one wart in the patch is that we now have an unconditional atomic operation in e1000_clean_tx_irq (netif_wake_queue). If anyone can think of a way to get rid of it without opening up the race, please let us know.

Cheers,

Visit Openswan at http://www.openswan.org/
Email: Herbert Xu ~{PmV>HI~} <[email protected]>
Home Page: http://gondor.apana.org.au/~herbert/
PGP Key: http://gondor.apana.org.au/~herbert/pubkey.txt
--

index 627f224..a22c01f 100644
@@ -2861,6 +2861,34 @@ e1000_transfer_dhcp_info(struct e1000_ad
 	return 0;
 }
 
+static int __e1000_maybe_stop_tx(struct net_device *netdev, int size)
+{
+	struct e1000_adapter *adapter = netdev_priv(netdev);
+	struct e1000_tx_ring *tx_ring = adapter->tx_ring;
+
+	if (unlikely(netif_test_and_stop_queue(netdev)))
+		return -EBUSY;
+
+	/* netif_test_and_stop_queue acts as a memory barrier.
+	 * We need to check again in a case another CPU has just
+	 * made room available.
+	 */
+	if (likely(E1000_DESC_UNUSED(tx_ring) < size))
+		return -EBUSY;
+
+	/* A reprieve! */
+	netif_start_queue(netdev);
+	return 0;
+}
+
+static inline int e1000_maybe_stop_tx(struct net_device *netdev,
+				      struct e1000_tx_ring *tx_ring, int size)
+{
+	if (likely(E1000_DESC_UNUSED(tx_ring) >= size))
+		return 0;
+	return __e1000_maybe_stop_tx(netdev, size);
+}
+
 #define TXD_USE_COUNT(S, X) (((S) >> (X)) + 1 )
 static int
 e1000_xmit_frame(struct sk_buff *skb, struct net_device *netdev)

@@ -2974,8 +3002,7 @@ #endif
 
 	/* need: count + 2 desc gap to keep tail from touching
 	 * head, otherwise try next time */
-	if (unlikely(E1000_DESC_UNUSED(tx_ring) < count + 2)) {
-		netif_stop_queue(netdev);
+	if (unlikely(e1000_maybe_stop_tx(netdev, tx_ring, count + 2))) {
 		spin_unlock_irqrestore(&tx_ring->tx_lock, flags);
 		return NETDEV_TX_BUSY;
 	}

@@ -3022,8 +3049,7 @@ #endif
 	netdev->trans_start = jiffies;
 
 	/* Make sure there is space in the ring for the next send. */
-	if (unlikely(E1000_DESC_UNUSED(tx_ring) < MAX_SKB_FRAGS + 2))
-		netif_stop_queue(netdev);
+	e1000_maybe_stop_tx(netdev, tx_ring, MAX_SKB_FRAGS + 2);
 
 	spin_unlock_irqrestore(&tx_ring->tx_lock, flags);
 	return NETDEV_TX_OK;

@@ -3515,14 +3541,9 @@ #endif
 	tx_ring->next_to_clean = i;
 
 #define TX_WAKE_THRESHOLD 32
-	if (unlikely(cleaned && netif_queue_stopped(netdev) &&
-	             netif_carrier_ok(netdev))) {
-		spin_lock(&tx_ring->tx_lock);
-		if (netif_queue_stopped(netdev) &&
-		    (E1000_DESC_UNUSED(tx_ring) >= TX_WAKE_THRESHOLD))
-			netif_wake_queue(netdev);
-		spin_unlock(&tx_ring->tx_lock);
-	}
+	if (unlikely(cleaned && netif_carrier_ok(netdev) &&
+		     E1000_DESC_UNUSED(tx_ring) >= TX_WAKE_THRESHOLD))
+		netif_wake_queue(netdev);
 
 	if (adapter->detect_tx_hung) {
 		/* Detect a transmit hang in hardware, this serializes the

index 75f02d8..b8714b4 100644
@@ -652,6 +652,15 @@ #endif
 	set_bit(__LINK_STATE_XOFF, &dev->state);
 }
 
+static inline int netif_test_and_stop_queue(struct net_device *dev)
+{
+#ifdef CONFIG_NETPOLL_TRAP
+	if (netpoll_trap())
+		return;
+#endif
+	return test_and_set_bit(__LINK_STATE_XOFF, &dev->state);
+}
+
 static inline int netif_queue_stopped(const struct net_device *dev)
 {
 	return test_bit(__LINK_STATE_XOFF, &dev->state);

Oops, I completely looked through netpoll_trap. Hmm, someone should really move the ifdef into netpoll_trap. Stephen?

BTW, who uses netpoll_set_trap anyway? There seems to be no user in the kernel tree. Where's Adrian Bunk :)

[NETDRV] e1000: Fix potential tx wake up race

Jamal posted a patch which improved e1000 TX performance. That in turn spawned a discussion on potential tx wake up races caused by the change. During that discussion, Michael Chan posted the following scenario (redrawn by me for e1000):

CPU0 CPU1
e1000_xmit_frame

	tx_lock
	if (tx_ring_empty)
					e1000_clean_tx_irq
						if (netif_queue_stopped)
							tx_lock
							netif_wake_queue
							tx_unlock
		netif_stop_queue
	tx_unlock

As you can see, even with the locks around netif_wake_queue this still allows the race to occur because the netif_wake_queue code path is conditional on netif_queue_stopped.

So here is a patch that uses the memory barriers rather than spin locks to solve the problem.

First of all I've made netif_wake_queue independent of netif_queue_stopped. This means that we operate on the stopped bit only once which closes a race window.

Furthermore, netif_wake_queue itself is already a memory barrier because it does a test_and_clear_bit. This means that if the other side can observe the netif_wake_queue then it can observe the extra room we've made on the
queue.

On the e1000_xmit_frame side, I've changed netif_stop_queue into a new function netif_test_and_stop_queue which does test_and_set_bit. This means that it also is a full memory barrier.

In order to close the race then, we simply recheck the tx queue size if netif_test_and_stop_queue returns 0 indicating that the queue was previously started. There are two possibilities:

1) netif_wake_queue is about to occur. In this case it doesn't really matter what we do as netif_wake_queue will always wake the queue for us. In the worst case, it'll wake up the queue with too little room but that's really uncommon and we can cope with that anyway.

2) netif_wake_queue has just occured. Because it is a memory barrier, when we recheck the queue size we're guaranteed to see the new indices which means that we'll see the extra room it has made for us. As a result we'll simply restart the queue.

The one wart in the patch is that we now have an unconditional atomic operation in e1000_clean_tx_irq (netif_wake_queue). If anyone can think of a way to get rid of it without opening up the race, please let us know.

Cheers,

Visit Openswan at http://www.openswan.org/
Email: Herbert Xu ~{PmV>HI~} <[email protected]>
Home Page: http://gondor.apana.org.au/~herbert/
PGP Key: http://gondor.apana.org.au/~herbert/pubkey.txt
--

index 627f224..a22c01f 100644
@@ -2861,6 +2861,34 @@ e1000_transfer_dhcp_info(struct e1000_ad
 	return 0;
 }
 
+static int __e1000_maybe_stop_tx(struct net_device *netdev, int size)
+{
+	struct e1000_adapter *adapter = netdev_priv(netdev);
+	struct e1000_tx_ring *tx_ring = adapter->tx_ring;
+
+	if (unlikely(netif_test_and_stop_queue(netdev)))
+		return -EBUSY;
+
+	/* netif_test_and_stop_queue acts as a memory barrier.
+	 * We need to check again in a case another CPU has just
+	 * made room available.
+	 */
+	if (likely(E1000_DESC_UNUSED(tx_ring) < size))
+		return -EBUSY;
+
+	/* A reprieve! */
+	netif_start_queue(netdev);
+	return 0;
+}
+
+static inline int e1000_maybe_stop_tx(struct net_device *netdev,
+				      struct e1000_tx_ring *tx_ring, int size)
+{
+	if (likely(E1000_DESC_UNUSED(tx_ring) >= size))
+		return 0;
+	return __e1000_maybe_stop_tx(netdev, size);
+}
+
 #define TXD_USE_COUNT(S, X) (((S) >> (X)) + 1 )
 static int
 e1000_xmit_frame(struct sk_buff *skb, struct net_device *netdev)

@@ -2974,8 +3002,7 @@ #endif
 
 	/* need: count + 2 desc gap to keep tail from touching
 	 * head, otherwise try next time */
-	if (unlikely(E1000_DESC_UNUSED(tx_ring) < count + 2)) {
-		netif_stop_queue(netdev);
+	if (unlikely(e1000_maybe_stop_tx(netdev, tx_ring, count + 2))) {
 		spin_unlock_irqrestore(&tx_ring->tx_lock, flags);
 		return NETDEV_TX_BUSY;
 	}

@@ -3022,8 +3049,7 @@ #endif
 	netdev->trans_start = jiffies;
 
 	/* Make sure there is space in the ring for the next send. */
-	if (unlikely(E1000_DESC_UNUSED(tx_ring) < MAX_SKB_FRAGS + 2))
-		netif_stop_queue(netdev);
+	e1000_maybe_stop_tx(netdev, tx_ring, MAX_SKB_FRAGS + 2);
 
 	spin_unlock_irqrestore(&tx_ring->tx_lock, flags);
 	return NETDEV_TX_OK;

@@ -3515,14 +3541,9 @@ #endif
 	tx_ring->next_to_clean = i;
 
 #define TX_WAKE_THRESHOLD 32
-	if (unlikely(cleaned && netif_queue_stopped(netdev) &&
-	             netif_carrier_ok(netdev))) {
-		spin_lock(&tx_ring->tx_lock);
-		if (netif_queue_stopped(netdev) &&
-		    (E1000_DESC_UNUSED(tx_ring) >= TX_WAKE_THRESHOLD))
-			netif_wake_queue(netdev);
-		spin_unlock(&tx_ring->tx_lock);
-	}
+	if (unlikely(cleaned && netif_carrier_ok(netdev) &&
+		     E1000_DESC_UNUSED(tx_ring) >= TX_WAKE_THRESHOLD))
+		netif_wake_queue(netdev);
 
 	if (adapter->detect_tx_hung) {
 		/* Detect a transmit hang in hardware, this serializes the

index 75f02d8..c4b0de0 100644
@@ -657,6 +657,15 @@ static inline int netif_queue_stopped(co
 	return test_bit(__LINK_STATE_XOFF, &dev->state);
 }
 
+static inline int netif_test_and_stop_queue(struct net_device *dev)
+{
+#ifdef CONFIG_NETPOLL_TRAP
+	if (netpoll_trap())
+		return netif_queue_stopped(dev);
+#endif
+	return test_and_set_bit(__LINK_STATE_XOFF, &dev->state);
+}
+
 static inline int netif_running(const struct net_device *dev)
 {
 	return test_bit(__LINK_STATE_START, &dev->state);

You sure you wanna wake him up? ;->

I still have my setup intact, so i will give this a whirl in about 3-4 hours. It does look promising - an atomic should be a lot cheaper than a lock. Thanks Herbert.

cheers,
jamal

Well it's not that good since the current code only takes the lock in exceptional circumstances while my patch does the atomic op unconditionally.

But then again the current code is wrong :)

Cheers,

Visit Openswan at http://www.openswan.org/
Email: Herbert Xu ~{PmV>HI~} <[email protected]>
Home Page: http://gondor.apana.org.au/~herbert/
PGP Key: http://gondor.apana.org.au/~herbert/pubkey.txt

yes, it would be nice to fix that. However, from a selfish angle, my worries are more about the overload case ;-> logically it is more likely you have a lot less CPU resources when overloaded than in the common case; actually now i have said "common" 100 times i understand Jesse better ;->.

indeed.

cheers,
jamal

I run a variety of tests and it looks good i.e performance wise, although lower than what i had before, certainly is an improvement over what was there before (by about 1kpps in forwarding). It would probably chew more CPU than the original driver (given the atomic) but as i said before i have no philosophical qualms with that since it performs better under stress ;->

Hardware is:
Dual via C3 1Ghz with a dual port e1000. The bottleneck is really the 32 bit PCI bus in most cases. I tried running single port, dual; low traffic, high traffic etc.

Interesting thing i noticed:
Under high speed forwarding test bidirectional (eth0<--forwarding-->eth1)

whenever __e1000_maybe_stop_tx() --> __netif_test_and_stop_queue() was called it was _guaranteed to find XOFF not set_. i.e 100% of the time.

This seems to actually happen on eth0 only (i think the two ports share the same PCI bridge and probably eth0 is biased?).

If you want me to try something else, send an incremental patch and i can do it tomorrow.

cheers,
jamal

Hardly surprising since you only have one CPU doing the actual sending.

The only time when this can happen is if we more than one CPU transmitted at the exatly same time.

Cheers,

Visit Openswan at http://www.openswan.org/
Email: Herbert Xu ~{PmV>HI~} <[email protected]>
Home Page: http://gondor.apana.org.au/~herbert/
PGP Key: http://gondor.apana.org.au/~herbert/pubkey.txt

Would it make a difference if we had more than one? qdisc_is_running ensures only one entering that region.

Did you mean to the same eth device?
Note: It is very highly likely - given the way i generate traffic - that two packets hit two different CPUs at the same time. But they will be to different ethernet devices.

cheers,
jamal

Good point. I can probably simplify the e1000 patch then.

Yes.

Cheers,

Visit Openswan at http://www.openswan.org/
Email: Herbert Xu ~{PmV>HI~} <[email protected]>
Home Page: http://gondor.apana.org.au/~herbert/
PGP Key: http://gondor.apana.org.au/~herbert/pubkey.txt

Sorry, I had a really shitty work day i didnt get around to it. I have 3 days off so will get it done either later today or tomorrow.

cheers,
jamal

I don't use netconsole. Jeff Moyer seems to be the main instigator of this.

In a lot of other drivers including tg3, waking the tx queue when there is not enough room in the tx ring is considered a bug and will trigger a BUG message:

BUG! Tx Ring full when queue awake!

May be David can explain why it is undesirable to wake up the queue when it is full?

Because it means that there was a race hole in the normal sleep/wakeup code. Some drivers just spin (see acenic.c) but that's ugly.

The real risk is that the transmit routine will decide it's busy, but at the same time an IRQ on another CPU will clean up the whole ring and make the queue available again. Then the transmit routine exits and says its busy, and the higher level will decide it is permanently stopped.

Stephen Hemminger <[email protected]>
"And in the Packet there writ down that doome"

From: Stephen Hemminger <[email protected]>
Date: Fri, 4 Aug 2006 11:08:29 -0700

Why does Michael ask all the difficult questions? :-)

Yes, it's meant to catch unintented races.

The queueing layer that calls ->hard_start_xmit() technically has no need to support NETDEV_TX_BUSY as a return value, since the device is able to prevent this.

If we could avoid NETDEV_TX_BUSY et al. from happening, the idea is that we could eliminate all of the requeueing logic in the packet scheduler layer. It is a pipe dream from many years ago.

But this may never be realized because now we have things like LLTX which can return NETDEV_TX_LOCKED which also requires a requeue. Also, several specialized devices can return NETDEV_TX_BUSY in ways which are hard to prevent. I'll reproduce Alexey's comments from qdisc_restart():

/* Device kicked us out :(
This is possible in three cases:

0. driver is locked
1. fastroute is enabled
2. device cannot determine busy state before start of transmission (f.e. dialout)
3. device is buggy (ppp)
*/

Hmmm, another remnant reference to fastroute which we should delete :-)

Doesnt this mean we need to hold the txlock longer to avoid the race? It will also mean we need to have a consistent programming model of the drivers (as an example: When is it not advisable to prune tx ring on the tx path? My gut feeling at the moment is i would rather have receive path do a lot of dirty work so as to prioritize transmit)

This section of the tx path is quiet hairy. Would a patch to make qdisc_restart more readable be a sensible thing to submit?

I noticed that the e1000 in some cases returns NETDEV_TX_OK even when it has stopped the queue. This results in wasted calls into the qdisc. It seems the tg3 is doing as well. I put a little counter and the amount of those useless calls that happen in incredible.
I was going to experiment with infact returning an additional code NETDEV_TX_BUSY_QUEUED which signals the core to just go away.

Still doable IMO - maybe a motivation for something to experiment with this long weekend.

cheers,
jamal

This is exactly the scenario where the current code can fail. It is also exactly the one that my patch addresses.

Actually it's OK. qdisc_restart will return after each NETDEV_TX_OK and its caller will check netif_queue_stopped before calling it again.

A precondition to eliminating it altogether is to eliminate lockless drivers which would be a very good thing :)

In fact that reminds me, because tg3 is no longer lockless, we can do a nicer bug fix for it than e1000 (it has the same bug).

Cheers,

Visit Openswan at http://www.openswan.org/
Email: Herbert Xu ~{PmV>HI~} <[email protected]>
Home Page: http://gondor.apana.org.au/~herbert/
PGP Key: http://gondor.apana.org.au/~herbert/pubkey.txt

So would the holding of the tx lock at the top layer/qdisc_restart level not help?

yes, of course ;->

Actually the stat i captured was not related to this, rather it was the number of times we entered qdisc_is_running and were unable to get a packet. I am using the simple pfifo so it cant be the scheduler refusing to give us a packet. I have a feeling it is just enthusiastic wake up of the tx softirq. Thoughts on this? I will add checks to be sure.

They have certainly complicated things.

cheers,
jamal

Yes it should so the corresponding fix for tg3 would be simpler.

Interesting. I can't really think of why it'd do that so some extra checks would really help.

Cheers,

Visit Openswan at http://www.openswan.org/
Email: Herbert Xu ~{PmV>HI~} <[email protected]>
Home Page: http://gondor.apana.org.au/~herbert/
PGP Key: http://gondor.apana.org.au/~herbert/pubkey.txt

I have to run for now but will do this tomorrow. Heres an example of what is saw (eth devices bound to different CPUs):

on entering eth1 qdisc_is_running:

14651764 times a packet was successfully dequeued and transmitted 9379699 times we got no packet at all and exited.

no packet implies the failure of the check:
if (((skb = dev->gso_skb)) || ((skb = q->dequeue(q)))) {

I know the qlen is >= 0 otherwise i will hit the BUG(). A qlen of 0 will be interesting to find as well.

cheers,
jamal

When the queue is woken it will always to qdisc_run regardless of whether there are packets queued so this might explain what you're seeing.

Anyway, I've changed the unconditional atomic op into a memory barrier instead. Let me know if this changes things for you.

I wonder if we could do the TX clean up within the transmission routine most of the time. Has anyone tried this before?

Cheers,

Visit Openswan at http://www.openswan.org/
Email: Herbert Xu ~{PmV>HI~} <[email protected]>
Home Page: http://gondor.apana.org.au/~herbert/
PGP Key: http://gondor.apana.org.au/~herbert/pubkey.txt
--

index 627f224..e7e1306 100644
@@ -2861,6 +2861,33 @@ e1000_transfer_dhcp_info(struct e1000_ad
 	return 0;
 }
 
+static int __e1000_maybe_stop_tx(struct net_device *netdev, int size)
+{
+	struct e1000_adapter *adapter = netdev_priv(netdev);
+	struct e1000_tx_ring *tx_ring = adapter->tx_ring;
+
+	netif_stop_queue(netdev);
+	smp_mb__after_netif_stop_queue();
+
+	/* We need to check again in a case another CPU has just
+	 * made room available.
+	 */
+	if (likely(E1000_DESC_UNUSED(tx_ring) < size))
+		return -EBUSY;
+
+	/* A reprieve! */
+	netif_start_queue(netdev);
+	return 0;
+}
+
+static inline int e1000_maybe_stop_tx(struct net_device *netdev,
+				      struct e1000_tx_ring *tx_ring, int size)
+{
+	if (likely(E1000_DESC_UNUSED(tx_ring) >= size))
+		return 0;
+	return __e1000_maybe_stop_tx(netdev, size);
+}
+
 #define TXD_USE_COUNT(S, X) (((S) >> (X)) + 1 )
 static int
 e1000_xmit_frame(struct sk_buff *skb, struct net_device *netdev)

@@ -2974,8 +3001,7 @@ #endif
 
 	/* need: count + 2 desc gap to keep tail from touching
 	 * head, otherwise try next time */
-	if (unlikely(E1000_DESC_UNUSED(tx_ring) < count + 2)) {
-		netif_stop_queue(netdev);
+	if (unlikely(e1000_maybe_stop_tx(netdev, tx_ring, count + 2))) {
 		spin_unlock_irqrestore(&tx_ring->tx_lock, flags);
 		return NETDEV_TX_BUSY;
 	}

@@ -3022,8 +3048,7 @@ #endif
 	netdev->trans_start = jiffies;
 
 	/* Make sure there is space in the ring for the next send. */
-	if (unlikely(E1000_DESC_UNUSED(tx_ring) < MAX_SKB_FRAGS + 2))
-		netif_stop_queue(netdev);
+	e1000_maybe_stop_tx(netdev, tx_ring, MAX_SKB_FRAGS + 2);
 
 	spin_unlock_irqrestore(&tx_ring->tx_lock, flags);
 	return NETDEV_TX_OK;

@@ -3515,13 +3540,14 @@ #endif
 	tx_ring->next_to_clean = i;
 
 #define TX_WAKE_THRESHOLD 32
-	if (unlikely(cleaned && netif_queue_stopped(netdev) &&
-	             netif_carrier_ok(netdev))) {
-		spin_lock(&tx_ring->tx_lock);
-		if (netif_queue_stopped(netdev) &&
-		    (E1000_DESC_UNUSED(tx_ring) >= TX_WAKE_THRESHOLD))
+	if (unlikely(cleaned && netif_carrier_ok(netdev) &&
+		     E1000_DESC_UNUSED(tx_ring) >= TX_WAKE_THRESHOLD)) {
+		/* Make sure that anybody stopping the queue after this
+		 * sees the new next_to_clean.
+		 */
+		smp_mb();
+		if (netif_queue_stopped(netdev))
 			netif_wake_queue(netdev);
-		spin_unlock(&tx_ring->tx_lock);
 	}
 
 	if (adapter->detect_tx_hung) {

index 75f02d8..7daaf71 100644
@@ -33,6 +33,7 @@ #ifdef __KERNEL__
 #include <asm/atomic.h>
 #include <asm/cache.h>
 #include <asm/byteorder.h>
+#include <asm/system.h>
 
 #include <linux/device.h>
 #include <linux/percpu.h>

@@ -652,6 +653,12 @@ #endif
 	set_bit(__LINK_STATE_XOFF, &dev->state);
 }
 
+static inline void smp_mb__after_netif_stop_queue(void)
+{
+	/* Need to add smp_mb__after_set_bit(). */
+	smp_mb();
+}
+
 static inline int netif_queue_stopped(const struct net_device *dev)
 {
 	return test_bit(__LINK_STATE_XOFF, &dev->state);

Hi Herbert,

Not sure what you mean with "most of the time" but a while a go I played around with a something like this for another driver. The tx path was cleaning up the tx ring at certain intervals while the tx irq-handler was not touching the ring unless it had become full. Actually the tx irq was disabled most of the time and ring manipulation became simpler.

Later I ended up throwing this away as it was causing some TCP connections to deadlock. If you let skb's sit in the tx-ring indefintely, the sk->sk_wmem_queued accounting will be inacurate and this was causing the TCP retransmit logic to deadlock.

Again, I'm not sure what you mean with "most of the time" but if you make sure the tx-ring is continously beeing cleaned-up, even tough no more packets are beeing generated, maybe it could work.

I hope this wasn't completely irrelevant..

Best regards,

        Programmer
        Edgar E. Iglesias <[email protected]> 46.46.272.1946

Yes that's exactly what I mean :)

Yes you need to clean the ring if the TX queue becomes empty or you'll risk dead locks.

What driver was this and did you do any performance measurements?

Cheers,

Visit Openswan at http://www.openswan.org/
Email: Herbert Xu ~{PmV>HI~} <[email protected]>
Home Page: http://gondor.apana.org.au/~herbert/
PGP Key: http://gondor.apana.org.au/~herbert/pubkey.txt

It was for the cris/eth_v10.c driver. Performance bumped with 20% for UDP if I remember correctly, TCP was much less. I'll try to dig up the numbers.

On UP non-preemptive kenrnels the tx-path used no interrupts and had no locks to manipulate the ring. But I am guessing that part of the performance win also came by freeing the skb's in chunks.

Best regards

        Programmer
        Edgar E. Iglesias <[email protected]> 46.46.272.1946

From: "Edgar E. Iglesias" <[email protected]>
Date: Sun, 6 Aug 2006 09:14:18 +0200

That's right, it's important to release TX SKBs in a timely. Doing it purely from ->hard_start_xmit() causes big problems, as you saw.

Increasingly I find that orphan'ing an SKB once it hits the real device for transmit is something to seriously consider.

Yes that certainly makes a lot of sense.

Actually, why do we charge the memory to the socket at all between the packet leaving the TCP stack and it entering the device? Most packets spend a tiny amount of time on this journey so it seems silly to do atomic operations as they leave the stack only to undo it when they enter the device.

The biggest reason packets spend a non-trivial amount of time on this journey is traffic shaping. In that case the memory is already accounted to the device anyway (in terms of queue length) so it would seem unfair to charge the socket as well.

So how about simply charging the socket for the retransmit queue as we do now and skip the caharge for packets leaving the stack?

For UDP it's different since it doesn't have a retransmit queue. However, I'm unsure how much of a positive effect the socket charge actually has for UDP.

Cheers,

Visit Openswan at http://www.openswan.org/
Email: Herbert Xu ~{PmV>HI~} <[email protected]>
Home Page: http://gondor.apana.org.au/~herbert/
PGP Key: http://gondor.apana.org.au/~herbert/pubkey.txt

It makes sense, but I see a problem with this. It will remove some of the control applications have on how much of their data gets queued on local queues. Small SNDBUF's are sometimes used to somewhat avoid/control latency.

For now, I think it's better to orphan the skb when it hits a real device for transmit, as David mentioned.

Best regards

        Programmer
        Edgar E. Iglesias <[email protected]> 46.46.272.1946

For UDP yes but does this really make sense for TCP?

Cheers,

Visit Openswan at http://www.openswan.org/
Email: Herbert Xu ~{PmV>HI~} <[email protected]>
Home Page: http://gondor.apana.org.au/~herbert/
PGP Key: http://gondor.apana.org.au/~herbert/pubkey.txt

I don't know :)

The flow may end up with SNDBUF worth of skbs on the socket transmit_queue + cwnd worth of skbs on the qdisc queue + full tx ring. In slow start we'll increase cwnd and won't se packet loss until the qdisc is full (which might be at 1000 pkts).

If the flow is locally limited, won't we end up with a very latent flow? where moste packets will be on the qdisc.

I agree that in general this is an effect of users having to large qdisc queues, but today maybe it is beeing somewhat avoided by apps setting small SNDBUF's. So I kind of agree with what you suggest but there might be risks.

Best regards

        Programmer
        Edgar E. Iglesias <[email protected]> 46.46.272.1946

For TCP, the packets stay on the transmit queue until they're acked. So all those packets on the qdisc queue (and tx ring) are still charged to the socket. The only difference is that right now we're double- charging the ones on the qdisc queue..

Cheers,

Visit Openswan at http://www.openswan.org/
Email: Herbert Xu ~{PmV>HI~} <[email protected]>
Home Page: http://gondor.apana.org.au/~herbert/
PGP Key: http://gondor.apana.org.au/~herbert/pubkey.txt

I see, then I guess this won't be a problem.

Thanks,

        Programmer
        Edgar E. Iglesias <[email protected]> 46.46.272.1946

From: Herbert Xu <[email protected]>
Date: Sun, 6 Aug 2006 17:36:55 +1000

Because it's easy to verify that it prevents all the possible DoS scenerios a user could play out.

I agree.

Again, total agreement.

UDP and other datagram protocols are a thorny case aren't they? :)

This has actually been a source of problems in the past, come to think of it. We used to have this bug in the output path where UDP could build a packet of size X that fit in the socket send buffer, but if we had to fragment this packet because "mtu < X" not all of the fragments would fit in the socket send buffer and we'd drop the entire packet :)

What happens now is we just try to strictly charge the first fragment to the socket's send buffer on fragmentation and then we only enfore lighter rules (allowing up to "2 * sk_sndbuf" to be used) as we charge for the rest of the frags.

You can see this logic in ip_append_data():

		if (transhdrlen) {
			skb = sock_alloc_send_skb(sk, 
					alloclen + hh_len + 15,
					(flags & MSG_DONTWAIT), &err);
		} else {
			skb = NULL;
			if (atomic_read(&sk->sk_wmem_alloc) <=
			    2 * sk->sk_sndbuf)
				skb = sock_wmalloc(sk, 
						   alloclen + hh_len + 15, 1,
						   sk->sk_allocation);
			if (unlikely(skb == NULL))
				err = -ENOBUFS;
		}

As you say these things are about to go out to the device, so it's kind of silly from that perspective, BUT... it does exist to a certain extent for application flow control, especially for these datagram apps.

I tried to see if there was any wisdom on this matter in TCP/IP Illustrated Volume 2, but BSD does the same thing we do.

That aligns with what i was thinking as well - i.e what i referred to as possibly enthusiasm on part of the tx softirq.
i.e if there was nothing queued, why is the softirq even woken up? Note, I observed this behavior to be a lot worse on systems that had very little traffic going out. Anyways, I hope to find out.

Will try it before end of day. Machine is about 20 minutes drive from where i am.

I actually have - as recently as last week when i was looking at the qdisc_is_running thing. Patch for e1000 attached.

One of the experiments i attempted was similar to the one described by [email protected]
I would only clean up on the rx path if netif_stopped and the rest happened in tx path. I tried variations of the above (ex: cleanup on tx path only if we exceed a threshold etc).

I did not see _any_ improvement for forwarding tests ;-> Infact at one point i think i saw a decrease in throughput, but it may have been within tolerance of experimental errors.

In the old days, both Robert and I did this with the tulip and it used to be an improvement. But now that i think about it, probably the reason was by doing so we reduced the EOT interrupts. Note, the NAPI approach on tulip allows that tx pruning to be done via interrupts. I liked that approach; but most people didnt and the e1000 and tg3 is what you see now.

My gut feeling is to let the cleaning happen in the receive path. The reason is that this leaves the tx path doing a lot less work. In a way this gives a pseudo higher-priority to the tx path at least for the case of forwarding where it is important for me to make sure the packet that i have sweated doing all the forwarding work on is going to go out. IOW, if the rx path gets very busy packets will end up being dropped on the receive path by virtue of DMA rings being filled up while the driver is busy - and that is an acceptable compromise.

cheers,
jamal

index d304297..270ec35 100644
@@ -183,6 +183,10 @@ struct e1000_tx_ring {
 	unsigned int size;
 	/* number of descriptors in the ring */
 	unsigned int count;
+	/* number of descriptors needed to wake up netdev */
+	unsigned int waket;
+	/* number of descriptors we allow to prune at a time */
+	unsigned int prunet;
 	/* next descriptor to associate a buffer with */
 	unsigned int next_to_use;
 	/* next descriptor to check for DD status bit */

index da62db8..c90d5c3 100644

err_up:
@@ -1371,6 +1372,11 @@ setup_tx_desc_die:

txdr->next_to_use = 0;
txdr->next_to_clean = 0;
+ /* hard-coding for now, but we should be able to
+ * use ethtool or module params in the future
+ */
+ txdr->prunet = txdr->count>>2;
+ txdr->waket = txdr->count>>3;
spin_lock_init(&txdr->tx_lock);

return 0;
@@ -2861,6 +2867,10 @@ e1000_transfer_dhcp_info(struct e1000_ad
return 0;
}

+static unsigned int
+e1000_prune_tx_ring(struct e1000_adapter *adapter,
+ struct e1000_tx_ring *tx_ring);
+
#define TXD_USE_COUNT(S, X) (((S) >> (X)) + 1 )
static int
e1000_xmit_frame(struct sk_buff *skb, struct net_device *netdev)
@@ -2980,6 +2990,14 @@ #endif
return NETDEV_TX_BUSY;
}

+#ifdef jamal
+ {
+ int fdesc = E1000_DESC_UNUSED(tx_ring);
+ if (unlikely(fdesc < tx_ring->waket))
+ e1000_prune_tx_ring(adapter,tx_ring);
+ }
+#endif
+
if (unlikely(adapter->hw.mac_type == e1000_82547)) {
if (unlikely(e1000_82547_fifo_workaround(adapter, skb))) {
netif_stop_queue(netdev);
@@ -3468,24 +3496,30 @@ quit_polling:
}

#endif
-/**
- * e1000_clean_tx_irq - Reclaim resources after transmit completes
- * @adapter: board private structure
- **/
+static inline void
+e1000_schedule_tx(struct net_device *netdev,
+ struct e1000_tx_ring *tx_ring)
+{
+ if (netif_carrier_ok(netdev)) {
+ if (E1000_DESC_UNUSED(tx_ring) >= tx_ring->waket)
+ netif_wake_queue(netdev);
+ }
+}

-static boolean_t -e1000_clean_tx_irq(struct e1000_adapter *adapter, +/*
+ * Must hold tx lock when invoking this .. +*/
+static unsigned int +e1000_prune_tx_ring(struct e1000_adapter *adapter,

                    struct e1000_tx_ring *tx_ring)

{
- struct net_device *netdev = adapter->netdev;
struct e1000_tx_desc *tx_desc, *eop_desc;
struct e1000_buffer *buffer_info;
unsigned int i, eop;
-#ifdef CONFIG_E1000_NAPI
- unsigned int count = 0;
-#endif
+ unsigned int count = 0, cleaned_count = 0;
boolean_t cleaned = FALSE;

+
i = tx_ring->next_to_clean;
eop = tx_ring->buffer_info[i].next_to_watch; eop_desc = E1000_TX_DESC(*tx_ring, eop);
@@ -3498,6 +3532,7 @@ #endif

e1000_unmap_and_free_tx_resource(adapter, buffer_info); memset(tx_desc, 0, sizeof(struct e1000_tx_desc));
+ cleaned_count++;

if (unlikely(++i == tx_ring->count)) i = 0;
}
@@ -3506,59 +3541,94 @@ #endif
eop = tx_ring->buffer_info[i].next_to_watch; eop_desc = E1000_TX_DESC(*tx_ring, eop);
#ifdef CONFIG_E1000_NAPI
-#define E1000_TX_WEIGHT 64
- /* weight of a sort for tx, to avoid endless transmit cleanup */
- if (count++ == E1000_TX_WEIGHT) break;
+ /* avoid endless transmit cleanup */
+ if (count++ == tx_ring->prunet) break;
#endif
}

tx_ring->next_to_clean = i;

-#define TX_WAKE_THRESHOLD 32
- if (unlikely(cleaned && netif_queue_stopped(netdev) &&
- netif_carrier_ok(netdev))) {
- spin_lock(&tx_ring->tx_lock);
- if (netif_queue_stopped(netdev) &&
- (E1000_DESC_UNUSED(tx_ring) >= TX_WAKE_THRESHOLD))
- netif_wake_queue(netdev);
- spin_unlock(&tx_ring->tx_lock);
- }
-
- if (adapter->detect_tx_hung) {
- /* Detect a transmit hang in hardware, this serializes the
- * check with the clearing of time_stamp and movement of i */
- adapter->detect_tx_hung = FALSE;
- if (tx_ring->buffer_info[eop].dma &&
- time_after(jiffies, tx_ring->buffer_info[eop].time_stamp +
- (adapter->tx_timeout_factor * HZ))
- && !(E1000_READ_REG(&adapter->hw, STATUS) &
- E1000_STATUS_TXOFF)) {
-
- /* detected Tx unit hang */
- DPRINTK(DRV, ERR, "Detected Tx Unit Hang\n"

-					"  Tx Queue             <%lu>\n"
-					"  TDH                  <%x>\n"
-					"  TDT                  <%x>\n"
-					"  next_to_use          <%x>\n"
-					"  next_to_clean        <%x>\n"
-					"buffer_info[next_to_clean]\n"
-					"  time_stamp           <%lx>\n"
-					"  next_to_watch        <%x>\n"
-					"  jiffies              <%lx>\n"
-					"  next_to_watch.status <%x>\n",

- (unsigned long)((tx_ring - adapter->tx_ring) /
- sizeof(struct e1000_tx_ring)),
- readl(adapter->hw.hw_addr + tx_ring->tdh),
- readl(adapter->hw.hw_addr + tx_ring->tdt),
- tx_ring->next_to_use,
- tx_ring->next_to_clean,
- tx_ring->buffer_info[eop].time_stamp,
- eop,
- jiffies,
- eop_desc->upper.fields.status);
- netif_stop_queue(netdev);
+ return cleaned_count;
+}
+
+static inline void +e1000_detect_tx_hung(struct e1000_adapter *adapter,
+ struct e1000_tx_ring *tx_ring)
+{
+ struct e1000_tx_desc *eop_desc;
+ struct net_device *netdev = adapter->netdev;
+ unsigned int i = tx_ring->next_to_clean;
+ unsigned int eop = tx_ring->buffer_info[i].next_to_watch;
+ eop_desc = E1000_TX_DESC(*tx_ring, eop);
+ /* Detect a transmit hang in hardware, this serializes the
+ * check with the clearing of time_stamp and movement of i */
+ adapter->detect_tx_hung = FALSE;
+ if (tx_ring->buffer_info[eop].dma &&
+ time_after(jiffies, tx_ring->buffer_info[eop].time_stamp +
+ (adapter->tx_timeout_factor * HZ))
+ && !(E1000_READ_REG(&adapter->hw, STATUS) &
+ E1000_STATUS_TXOFF)) {
+
+ /* detected Tx unit hang */
+ DPRINTK(DRV, ERR, "Detected Tx Unit Hang\n"

+				"  Tx Queue             <%lu>\n"
+				"  TDH                  <%x>\n"
+				"  TDT                  <%x>\n"
+				"  next_to_use          <%x>\n"
+				"  next_to_clean        <%x>\n"
+				"buffer_info[next_to_clean]\n"
+				"  time_stamp           <%lx>\n"
+				"  next_to_watch        <%x>\n"
+				"  jiffies              <%lx>\n"
+				"  next_to_watch.status <%x>\n",

+ (unsigned long)((tx_ring - adapter->tx_ring) /
+ sizeof(struct e1000_tx_ring)),
+ readl(adapter->hw.hw_addr + tx_ring->tdh),
+ readl(adapter->hw.hw_addr + tx_ring->tdt),
+ tx_ring->next_to_use,
+ tx_ring->next_to_clean,
+ tx_ring->buffer_info[eop].time_stamp,
+ eop,
+ jiffies,
+ eop_desc->upper.fields.status);
+
+ netif_stop_queue(netdev);
+ }
+}
+
+/**
+ * e1000_clean_tx_irq - Reclaim resources after transmit completes
+ * @adapter: board private structure
+ **/
+
+static boolean_t
+e1000_clean_tx_irq(struct e1000_adapter *adapter,
+ struct e1000_tx_ring *tx_ring)
+{
+ struct net_device *netdev = adapter->netdev;
+ boolean_t cleaned = FALSE;
+
+#ifdef jamal
+ spin_lock(&tx_ring->tx_lock);
+ {
+ int fdesc = E1000_DESC_UNUSED(tx_ring);
+ if (fdesc < tx_ring->prunet) {
+ if (e1000_prune_tx_ring(adapter,tx_ring))
+ cleaned = TRUE;
}
}
+ spin_unlock(&tx_ring->tx_lock);
+#else
+ if (e1000_prune_tx_ring(adapter,tx_ring))
+ cleaned = TRUE;
+#endif
+
+ if (unlikely(netif_queue_stopped(netdev) && cleaned))
+ e1000_schedule_tx(netdev, tx_ring);
+
+ if (unlikely(adapter->detect_tx_hung))
+ e1000_detect_tx_hung(adapter,tx_ring);
+
return cleaned;
}

BTW, if you notice in the attached patch i have:

+       /* number of descriptors needed to wake up netdev */
+       unsigned int waket;
+       /* number of descriptors we allow to prune at a time */
+       unsigned int prunet;

and:

+ /* hard-coding for now, but we should be able to
+ * use ethtool or module params in the future

+       */
+       txdr->prunet = txdr->count>>2;
+       txdr->waket = txdr->count>>3;

i.e the two thresholds are based on the tx ring sizes.

I didnt like TX_WAKE_THRESHOLD and E1000_TX_WEIGHT hardcoding. if i make the ring smaller then these values could be invalid. I also experimented with varying the two thresholds with varying traffic throughput - lets say results are still magical and i am still looking at it.

Q: Do you know the historical context of why TX_WAKE_THRESHOLD and E1000_TX_WEIGHT are hard-coded (and not for example related to the size of the ring)? Jesse?
Otherwise i would like to submit a patch for the above. eventually probably even allow the setting via ethtool.

cheers,
jamal

Yeah those are both created by me, interestingly up until a couple of releases ago we had neither.

To answer your question of context, I noticed very specific problems and fixed them with the simplest method that worked. I figure we can address it as time goes on (like we are now) with improvements.

As for specifics, for TX_WAKE_THRESHOLD, i noticed that we were starting the queue after every packet was cleaned, so when the ring went full there was a lot of queue thrash. tg3 seemed to fix it in a smart way and so I did a similar fix. Note we should have at least MAX_SKB_FRAGS (usually 32) + a few descriptors free before we should start the tx again, otherwise we run the risk of a maximum fragmented packet being unable to fit in the tx ring.

now, for E1000_TX_WEIGHT, that was more of an experiment as i noticed we could stay in transmit clean up forEVER (okay not literally) which would really violate our NAPI timeslice. I messed with some values and 64 didn't really seem like too bad a compromise (it does slow things down just a tad in the general case) while really helping a couple of tests where there were lots of outstanding transmits happening at the same time as lots of receives.

This need for a tx weight is yet another global (design) problem with NAPI enabled drivers, but someday I'll try to document some of the issues I've seen.

Jesse

On Sun, 2006-06-08 at 16:16 -0700, Jesse Brandeburg wrote:
[..]

indeed this is what used to happen and was bad.... So this is a huge improvement.
What happens now under steady state at high traffic transmits is, instead of 1, you see E1000_TX_WEIGHT in between queue sleep/wakes. I assume this is a given since E1000_TX_WEIGHT is higher than TX_WAKE_THRESHOLD. I am not sure if i can vouch for even more improvement by mucking around with values of E1000_TX_WEIGHT.

Can you please take a look at the patch i posted? I would like to submit that for inclusion. It does two things
a) make pruning available to be invoked from elsewhere (I tried to do it from the tx path but it gave me non-good results)
b) makes E1000_TX_WEIGHT and TX_WAKE_THRESHOLD relative to the size of the transmit ring. I think this is a sane thing to do.

You could either extract the bits or i could resend to you as two different patches. I have tested it and it works.

I noticed you check for that in the tx path.

Interesting. The only time i have seen the NAPI time slice kick in is in slow hardware or emulators (like UML).
I wonder if the pruning path could be made faster? What is the most consuming item? I realize there will be a substantial amount of cache misses. Maybe in addition to prunning E1000_TX_WEIGHT descriptors also fire a timer to clean up the rest (to avoid it being accounted for in the napi timeslice;->). Essentially i think you have some thing in the pruning path that needs to be optimized. Profiling and improving that would help.

The later are the kind of tests i am running. If you are a router or a busy server they apply. In slow machines a ping flood also applies etc.

oh yes, the Intel cabal - blame NAPI first;->
IMO, the problem is you are consuming too many cycles in the receive path. NAPI has to be fair to all netdevices and cant hog all the CPU because a certain netdevice uses too many cycles to process a packet.

I think it would be invaluable. Just dont jump to blame Canada^WNAPI conclusion because it distracts;

cheers,
jamal

Hi Jamal,

I have a question regarding your patch. In clean_tx_irq, it seems you dont clean the ring unless fdesc < tx_ring->prunet. Won't this cause deadlocks for local TCP connections if transmit goes quiet?

It seems to me as if this patch depends on the skb orphaning previously suggested on this thread. Please correct me if I'm wrong.

Best regards

        Programmer
        Edgar E. Iglesias <[email protected]> 46.46.272.1946

On Mon, 2006-07-08 at 17:21 +0200, Edgar E. Iglesias wrote:
[..]

I have not tested the TCP case; however, note that the specific part you reference is commented out. There are no deadlock issues in the case of forwarding (as in my testcases).

I did not quiet follow the ensuing discussion after your post:
These descriptors being pruned in the tx path happen only after the packets have been sent out on the wire. Why would this contribute to a deadlock but not when it happens on the receive path? It is true that tcp retransmit queue will still be referencing the skbs, but why is it any different because in one case it happens in the tx and in the other on the receive? Is there dependency on waking up the queue?

I didnt quiet follow that discussion I will go back and read it; you could also answer my questions above to make me understand better.

cheers,
jamal

Ok, I thought you wanted the code inside the ifdefs to be considered. If not, I guess there is no problem. Yes, the forwarding case does not suffer from any deadlocks issues that I am aware of.

No, the deadlock happens only if you don't prune the descriptors. If the host sends some data and then goes quite, fdesc < tx_ring->prunet might not be true for a long time and skbs will end up sitting in the tx ring indefinitely, charging the socket's sndbuf.

Best regards

        Programmer
        Edgar E. Iglesias <[email protected]> 46.46.272.1946

It does _not_ provide any performance improvements and at some point i decided i didnt want to add more variables to analyze, so i got rid of it; I would have had to hand edit the patch to totally remove it; so that why you still see the ifdefed out variant.

Note: I didnt get rid of the rx path pruning. i.e that is still on. It just prunes lesser descriptors with that change on the tx. So not very different from before.

I think i may be getting a gist now of the discussion after a re-read; while packets are still charged to TCP may have been transmitted they may sit on the tx ring forever. They will only be pruned if we had netif_stopped (and even that is not good enough with Jesse's threshold check) or if a new packet comes in destined for us.
Did i understand correctly? If yes, i didnt introduce this challenge it has always been there. I think i understand the suggestion now from Dave/Herbert to orphan those skbs...

cheers,
jamal

I'll give you an example.

A TCP flow sends X data and later waits for a response, host is now quietly waiting. Assume fdesc >= tx_ring->prunet, so we dont free any skbs, right?

Now assume that some part of X data gets lost, our retransmit timer hits and we want to retransmit but our socket is charged with too much data sitting on the nics tx-ring, so we don't send anything. By orphaning, those skbs won't charge the socket and the flow can retransmit.

Best regards

        Programmer
        Edgar E. Iglesias <[email protected]> 46.46.272.1946

Thanks - that matches my understanding.

I am hoping they will be freed by a tx interrupt that will force poll to happen. Or a new packet arrival etc. Just like before. Why do you see the two as different? (the tx path pruning is still going on as i noted before). If all you are looking for is a scheme to quickly free the skbs so that TCP doesnt get charged, I am not sure if this is the right one.

I understand that as well as the dilemma that TCP not being charged for skbs (if you decide to orphan) it holds in its retransmit queue ;-> Which is not a problem unless that queueu grows to be a huge one ;->

cheers,
jamal

I think we are out of sync :) My, fault I haven't been clear enough.

First of all, I don't think the patch with jamal undefined has any problems. I assumed wrongly from the start that you somehow wanted that part to go in aswell, sorry about that. As you say, the flow goes just as before.

Now, with jamal defined, I only see e1000_prune_tx_ring beeing called if fdesc < tx_ring->prunet or fdesc < tx_ring->waket. In other words, the freing of skbs is dependant on external events that might not become true if the host is quiet. Skb's could end up sitting on the ring indefinitely.

Sorry for the confusion.

        Programmer
        Edgar E. Iglesias <[email protected]> 46.46.272.1946

Imagine that, eh? ;->

Not just your transmit but also my receive is at fault ;-> (aka, I may not be listening as well as i should). Now two machines or CPUs you would think wont have this problem since they dont possess minds;->

Ok, thats the code that has been commented out, no? i.e there is no fdesc otherwise.

Yes, this has _always_ been true. In the patch i posted it merely converted things, example:

-#define E1000_TX_WEIGHT 64
- /* weight of a sort for tx, to avoid endless transmit
cleanup */

-               if (count++ == E1000_TX_WEIGHT) break;
+               /* avoid endless transmit cleanup */
+               if (count++ == tx_ring->prunet) break;

As you can see E1000_TX_WEIGHT threshold exists today and you are right if no TX interupts, packet arrivals or scheduled wakes happen the that descriptor that was not pruned will sit there forever (which is a bad thing for TCP). Are we in sync?
If yes, what is the likelihood they will sit there forever? I think perhaps some TX interupts will happen, no?

cheers,
jamal

Exactly.

Yep :)

with jamal undefined, absolutely. With jamal defined, TX interrupts will come but I couldnt find a way into e1000_prune_tx_ring unless fdesc met the conditions. Correct?

Best regards

        Programmer
        Edgar E. Iglesias <[email protected]> 46.46.272.1946

Forgive me since i am still missing something ..

Observe that the same threshold used in two different ways:

1) in tx path tx_ring->prunet is to check on when we should _start_ to prune.
2) on rx path tx_ring->prunet is to check when to _stop_ pruning.

i.e #1 is a preemptive action.

You seem to suggest doing it the way i was it made things worse?

Note that TX interrupts will happen as long as you dont prune some descriptors (I am assuming this, I havent checked the settings).

cheers,
jamal

I can see two calls to e1000_prune_tx_ring with jamal _defined_.

1. tx path
+#ifdef jamal
+ {
+ int fdesc = E1000_DESC_UNUSED(tx_ring);
+ if (unlikely(fdesc < tx_ring->waket))
+ e1000_prune_tx_ring(adapter,tx_ring);
+ }
+#endif

2. tx and rx path
+#ifdef jamal
+ spin_lock(&tx_ring->tx_lock);
+ {
+ int fdesc = E1000_DESC_UNUSED(tx_ring);
+ if (fdesc < tx_ring->prunet) {
+ if (e1000_prune_tx_ring(adapter,tx_ring))

+                               cleaned = TRUE;
                }
        }

+ spin_unlock(&tx_ring->tx_lock);
+#else
+ if (e1000_prune_tx_ring(adapter,tx_ring))
+ cleaned = TRUE;
+#endif

Assume a ring of 64 entries, prunet of 16, waket of 8. Now host sends 40 skbs and stops. tx-ring holds 40 skbs, has 24 free. TX interrupts hit you, you may even be receiveing packets but I don't see how you enter prune_tx_ring without more packets going out via hard_start_xmit? skb's will sit on the ring until more packets are sent from the quiet host.

As you can see, with jamal _undefined_ e1000_prune_tx_ring is called unconditionally and I beleive things will work ok.

I am not familiar with this code nor the hw so I'm probably missing something fundamental.

Best regards

        Programmer
        Edgar E. Iglesias <[email protected]> 46.46.272.1946

Ok, never mind - I think thats the source of our confusion. Just ignore those entries since they are ifdefed out (The second one i dont know how it made it in since there are no traces of it in my tree).

cheers,
jamal

we don't enable it right now, but you could use the TXQE (tx queue empty) interrupt to avoid the starvation case. I think it might flood you with TXQE interrupts however, so we'd probably have to figure out some way to turn it on occasionally.

Jesse

I think it may make sense to set on netif_stop and reset on wake. I take it "empty" means all the descriptors for sending are gone?

cheers,
jamal

I thought this code is only used for NAPI so as long as work was done it'll keep calling this.

One thing I'm not sure about though is the time between it decides that there is no work and the point where the interrupts are reenabled.

What if work arrives in that time and no work ever arrives after the interrupts are turned on again? Does that mean the work will sit there forever?

Cheers,

Visit Openswan at http://www.openswan.org/
Email: Herbert Xu ~{PmV>HI~} <[email protected]>
Home Page: http://gondor.apana.org.au/~herbert/
PGP Key: http://gondor.apana.org.au/~herbert/pubkey.txt

yes, you're correct.

e1000 only clears the interrupts when it reads ICR in e1000_intr (before scheduling napi poll) so any interrupts that occur while polling (and interrupts are disabled) will cause a new assertion once interrupts are re-enabled. Sometimes a little bit inefficient due to extra trips through poll, but guarantees never to miss an int. I'm open to creative ways to avoid this, but adding an I/O read in e1000_clean would be pretty yucky.

nope, see above.

The standard solution in Linux is to clear and recheck. So just before you reenable the interrupts you'd clear pending interrupts again and check for rx/tx work, if there is work then you just go back to polling.

Cheers,

Visit Openswan at http://www.openswan.org/
Email: Herbert Xu ~{PmV>HI~} <[email protected]>
Home Page: http://gondor.apana.org.au/~herbert/
PGP Key: http://gondor.apana.org.au/~herbert/pubkey.txt

Hi again Jamal,

Not sure if it is doable, but to I'll post the thoughts anyway.

Assuming you would get the code inside the jamal ifdefs working without deadlocks, you now have a tx_irq function which if fdesc >= tx_ring->prunet essentially just checks for hw lockups. Let's speculate and further assume you could do the detect_tx_hung from some other context (timer or whatever) then you end up having a tx_irq function which most of the time does nothing.

The next step could be to move the fdesc >= tx_ring->prunet logic into the transmit path and completely disable the tx_irq when the condition is not met.

Now you end up not taking the irq at all as long as fdesc >= tx_ring->prunet.

This was the logic I tried on the cris driver but ended up with deadlocks :)

Best regards

        Programmer
        Edgar E. Iglesias <[email protected]> 46.46.272.1946

Like i said in one of my earlier postings (first email i CCed you on), this specific test i assumed was as close to what you did. But if i understand what you describe as "deadlock" then we have a slightly different problem that can only be solved by orphaning the skbs that are determined to have been put on the DMA ring ....

cheers,
jamal

Looks good performance-wise; almost as good as the version i had. Certainly better than the original e1000 (of course i am talking about the overload case ;->).

Interesting thing to note:
only 0.001% of the time and only on one CPU was the
__e1000_maybe_stop_tx::netif_start_queue() ever hit.
I guess that is sufficient to convince someone of the possibility of a race ;-> Note, these C3s are damn slow CPUs by todays standards so i am suspecting that % will be higher with faster CPUs.

cheers,
jamal

The reason for this is _mostly_ not the tx softirq as i found out;-> It is actually a result of dev_queue_xmit.
The only way to tell if you can depart qdisc_is_running is by asking the qdisc for a packet. So if you have slow traffic, its guaranteed that you enter once to process a packet and the second time to find out that you have to go away ;->

In any case, heres a patch that i believe saves some cycles in case of a tx scheduling while some CPU is already processing the qdisc. Minimal testing.

cheers,
jamal

index d95e262..977e77e 100644
@@ -1092,7 +1092,8 @@ static void dev_queue_xmit_nit(struct sk
 
 void __netif_schedule(struct net_device *dev)
 {
-	if (!test_and_set_bit(__LINK_STATE_SCHED, &dev->state)) {
+	if (!test_bit(__LINK_STATE_QDISC_RUNNING, &dev->state) &&
+	    !test_and_set_bit(__LINK_STATE_SCHED, &dev->state)) {
 		unsigned long flags;
 		struct softnet_data *sd;
 

Is there a need for a schedule if that happens? i.e assuming that the clearing happens because there are no more packets to process. OTOH, if the other side sets the QDISC_RUNNING right after the test, then qdisc is running will be entered.

cheers,
jamal

CPU0 CPU1
__qdisc_run
netif_queue_stopped
netif_wake_queue
__netif_schedule
test_bit
clear_bit

So you may end up losing that wake event. The QDISC_RUNNING bit was originally designed to be used under the qdisc lock, so using it in a different contexts will require new synchronisation mechanisms.

Cheers,

Visit Openswan at http://www.openswan.org/
Email: Herbert Xu ~{PmV>HI~} <[email protected]>
Home Page: http://gondor.apana.org.au/~herbert/
PGP Key: http://gondor.apana.org.au/~herbert/pubkey.txt

Indeed you may.
I think what i was seeing is (motivating the patch to begin with) is:
if you got out of qdisc restart because driver returned TX_BUSY leading to a netif_queue_stopped then you will have rescheduled on CPU0. The only exception is the one example i mentioned in earlier email where a TX_OK is returned by e1000.

Agreed.

cheers,
jamal

Is the patch below making it in? As i pointed out in another email tests reveal it is good.

cheers,
jamal

I'll write up a proper description and submit it.

Cheers,

Visit Openswan at http://www.openswan.org/
Email: Herbert Xu ~{PmV>HI~} <[email protected]>
Home Page: http://gondor.apana.org.au/~herbert/
PGP Key: http://gondor.apana.org.au/~herbert/pubkey.txt

Do you mean the same race condition bug between tg3_start_xmit() and tg3_tx() that I brought up? I don't think tg3 has that problem. Did I miss something?

Yes it has the problem in two places. First of all the first netif_stop_queue in tg3_start_xmit doesn't take the tx_lock at all so it's obviously vulnerable.

The last netif_stop_queue is susceptible to a more subtle problem:

CPU0 CPU1
tg3_start_xmit
TX_BUFF_AVAIL <= threshold
tx_lock
tg3_tx
!netif_queue_stopped
netif_stop_queue
BUFF_AVAIL <= threshold
tx_cons = sw_idx
tx_unlock

Because netif_queue_stopped is *not* a memory barrier, it can float above the assignment to tx_cons. So even though netif_stop_queue *is* a memory barrier on x86, the second BUFF_AVAIL test can still fail to see the updated index.

The fix here is obviously to add a memory barrier in tg3_tx.

Cheers,

Visit Openswan at http://www.openswan.org/
Email: Herbert Xu ~{PmV>HI~} <[email protected]>
Home Page: http://gondor.apana.org.au/~herbert/
PGP Key: http://gondor.apana.org.au/~herbert/pubkey.txt

Oh, that first one near the top of tg3_start_xmit()? That condition is not supposed to happen and is a bug condition. But we can certainly add a spinlock to make it more correct.

You are absolutely right and I missed it. We should add a wmb() after the tx_cons update in tg3_tx(). Thanks.

A wmb() only prevents stores from passing stores. We need to prevent a load from passing a store so you need a full memory barrier (smp_mb).

Cheers,

Visit Openswan at http://www.openswan.org/
Email: Herbert Xu ~{PmV>HI~} <[email protected]>
Home Page: http://gondor.apana.org.au/~herbert/
PGP Key: http://gondor.apana.org.au/~herbert/pubkey.txt

Maybe the way NETDEV_TX_BUSY is implemented is wrong -- that is, it should be possible to return a result saying "we sent the packet, but the queue is now full". That would eliminate the atomic op that netif_queue_stop() performs and allow higher layers to merge the necessary barrier on the full case with the op on the tx lock. That way we could have lockless queue handling within the driver. This might need start/stop sequence counters, though.

-ben

"Time is of no importance, Mr. President, only life is important."
Don't Email: <[email protected]>.

From: Benjamin LaHaise <[email protected]>
Date: Tue, 8 Aug 2006 13:04:32 -0400

The driver ->hard_start_xmit() method is invoked with the queue unlocked, so this kind of scheme would not be workable.

While the queue is unlocked, another cpu could empty entries in the TX queue making it not-full, which invalidates this "queue is now full" return value the driver just gave.

We don't do things the way we do it now for fun, it's just the most reasonable scheme we've come up with given the locking constraints.

Looking at e1000, NETIF_F_LLTX is a waste -- the driver takes a spinlock almost immediately after entering. Taking the spinlock higher up in the network stack, preferably for multiple packets, would at least let the CPU deal with things sooner. tg3 doesn't use LLTX and thus holds the lock over hard_start_xmit(). bonding is atrocious and uses a read lock and unlock in many of the xmit routines. The only true lockless tx seems to be loopback.

Given that the vast majority of drivers are locked during their xmit routine, it is probably worth implementing at some point.

-ben

"Time is of no importance, Mr. President, only life is important."
Don't Email: <[email protected]>.

Your assessment is correct. However, that's not the issue here.

The problem here is that the TX clean function does not take the lock (nor do we want it to). It can thus come in while you're transmitting and empty the queue.

Cheers,

Visit Openswan at http://www.openswan.org/
Email: Herbert Xu ~{PmV>HI~} <[email protected]>
Home Page: http://gondor.apana.org.au/~herbert/
PGP Key: http://gondor.apana.org.au/~herbert/pubkey.txt

That can be solved with sequence numbers -- ie, we keep track of the number of packets queued to the hardware, as well as tracking the number of tx completions that have been reaped. Because those numbers are flushed to memory by other locks (barriers) taken during processing, the code in hard_start_xmit() and the actual tx completion reaping could be done without the atomic ops. The key thing is that the higher level code in the network stack calling dev->hard_start_xmit() would know that it needs to retry if the tx complete sequence changes. I'll ponder this a bit more and try to come up with some sample code.

-ben

"Time is of no importance, Mr. President, only life is important."
Don't Email: <[email protected]>.

Indeed - if you do it that way.
What about (actually e1000 is not exactly like this but closer than tg3 is):

tg3_start_xmit():

prepare skb
grab ring tx lock irq safe
put skb on ring
if (full-ring)
stop
release ring tx lock and restore flags blah

and in tg3_tx():

if likely(stopped) {
// essentially no lock needed here ....
prune tx ring
if prunned > threshold
wake
} else if not stopped {
// need a lock here ...
grab ring tx lock irq safe
prune tx ring
release ring tx lock
}

The above is safe to run tg3_start_xmit on one CPU and tg3_tx an another.

And you can then take advantage of asynchronous wakes and remove the paranoia checks you have on tx.

cheers,
jamal

The problem is that the !stopped case may be the common path for a lot of workloads so it'd be good to avoid taking the lock there if we can.

Cheers,

Visit Openswan at http://www.openswan.org/
Email: Herbert Xu ~{PmV>HI~} <[email protected]>
Home Page: http://gondor.apana.org.au/~herbert/
PGP Key: http://gondor.apana.org.au/~herbert/pubkey.txt

True.

Although i cant think of a clever way to do the inverse.... The heuristic i was using to avoid the lock on tx at pruning time was knowledge that tx was not being entered at all on stop.

cheers,
jamal

The whole point of doing things the way it is done in tg3 is to avoid taking the lock unless there is a need to stop the queue or wake the queue.

With a 511 entry send ring in tg3, filling the entire tx ring should not happen all the time. Even if we fill the tx ring constantly, the hysteresis effect of waking the queue only after the tx ring is 3/4 empty will make it uncommon to do stop_queue and wake_queue. So it is the right thing to do to optimize for the case where the ring is not full. The penalty is that we need some extra checking after stopping the queue which should be the uncommon case.

Jesse,

Well, the tg3 does try to netif_wake on the tx path as well; it would need to hold the lock;-> The e1000 doesnt.

I didnt see the need to hold the lock but i may be missing the "normal" case you refer to: I did the worst possible scenario and had transmit path running concurently on one CPU while receive was running on another (refer to the earlier explanation i posted).

The logic is you stop, the tx path will never be entered. If it is never entered, you will never have to protect on the rx path.

Of course if you call start after you stopped and there are still packets sitting on the tx ring or qdisc, they will stay forever until the next packet arrival. But if you do that you have a buggy driver. But i dont see where you call start in the e1000 - was this some old code?

You should not call start if you are stopped. Is there some peripheral code that does start?

cheers,
jamal