[STRAW MAN PATCH] sch_teql doesn't load-balance ppp(oatm) slaves

[STRAW MAN PATCH] sch_teql doesn't load-balance ppp(oatm) slaves

[David Woodhouse]

[-- Attachment #1: Type: text/plain, Size: 2351 bytes --]

ppp_xmit_process() loops, calling skb_dequeue() until it can no longer
push a frame to the channel. In the case of PPPoATM, it's only ever
going to fail to push a frame to the channel when sk->sk_sndbuf is
exceeded on the atm_vcc. We have a *huge* hidden queue there. (Reducing
the send buffer size to 4KiB with a hack in pppoatm_assign_vcc() didn't
fix the teql problem either.)

teql_dequeue() will *always* give up a skb when it's called, if there is
one. If there's *not*, and the tx queue becomes empty, then the device
for which teql_dequeue() was called is 'promoted' to the front of the
line (master->slaves). That device will receive the next packet that
comes in, even if there are other devices which are *also* idle and
waiting for packets. Whenever a new packet comes in, the *last* device
to call teql_dequeue() gets it.

I have a system with two ADSL lines, using PPPoATM and teql. Because of
the behaviour of teql described above, it only seems to use *one* of the
uplinks at a time. One link will be idle for seconds at a time, before
the ATM socket send buffer fills or we get lucky with timing and it
flips to the other device.

My simple 'fix' for this is as follows: if *another* device is already
waiting with its tx queue empty, then teql_dequeue() should *not* return
a new packet to its caller. It may not be the best fix — it may not even
be correct, but it's working and I finally get the full upload bandwidth
of both lines, rather than using only one at a time. The ISP lets me do
a 10-second dump of the traffic on my bonded lines, and I now see it
being properly interleaved between the two lines, making optimal use of
the two uplinks.

Anyone got better ideas?

--- net/sched/sch_teql.c~	2012-03-22 15:21:41.000000000 +0000
+++ net/sched/sch_teql.c	2012-03-22 16:42:28.684436315 +0000
@@ -100,6 +100,10 @@ teql_dequeue(struct Qdisc *sch)
 	struct netdev_queue *dat_queue;
 	struct sk_buff *skb;
 
+	if (dat->m->slaves && dat->m->slaves != sch &&
+	    !qdisc_peek_head(dat->m->slaves)) {
+		return NULL;
+	}
 	skb = __skb_dequeue(&dat->q);
 	dat_queue = netdev_get_tx_queue(dat->m->dev, 0);
 	if (skb == NULL) {

-- 
David Woodhouse                            Open Source Technology Centre
David.Woodhouse@intel.com                              Intel Corporation



[-- Attachment #2: smime.p7s --]
[-- Type: application/x-pkcs7-signature, Size: 5818 bytes --]

Re: [STRAW MAN PATCH] sch_teql doesn't load-balance ppp(oatm) slaves

[David Miller]

From: David Woodhouse <dwmw2@infradead.org>
Date: Thu, 22 Mar 2012 21:03:38 +0000

> teql_dequeue() will *always* give up a skb when it's called, if there is
> one. If there's *not*, and the tx queue becomes empty, then the device
> for which teql_dequeue() was called is 'promoted' to the front of the
> line (master->slaves). That device will receive the next packet that
> comes in, even if there are other devices which are *also* idle and
> waiting for packets. Whenever a new packet comes in, the *last* device
> to call teql_dequeue() gets it.

The teql master ->ndo_start_xmit() method is where the slave iteration
occurs, and it occurs on every successful transmit of a single packet.

But this cannot, and is documented not to, work when device stacking
is involved.

If you're dealing with (what amounts to) virtual devices, you cannot
use TEQL and must use something like drivers/net/eql.c

Re: [STRAW MAN PATCH] sch_teql doesn't load-balance ppp(oatm) slaves

[David Woodhouse]

[-- Attachment #1: Type: text/plain, Size: 2893 bytes --]

On Thu, 2012-03-22 at 23:03 -0400, David Miller wrote:
> From: David Woodhouse <dwmw2@infradead.org>
> Date: Thu, 22 Mar 2012 21:03:38 +0000
> 
> > teql_dequeue() will *always* give up a skb when it's called, if there is
> > one. If there's *not*, and the tx queue becomes empty, then the device
> > for which teql_dequeue() was called is 'promoted' to the front of the
> > line (master->slaves). That device will receive the next packet that
> > comes in, even if there are other devices which are *also* idle and
> > waiting for packets. Whenever a new packet comes in, the *last* device
> > to call teql_dequeue() gets it.
> 
> The teql master ->ndo_start_xmit() method is where the slave iteration
> occurs, and it occurs on every successful transmit of a single packet.

Thanks for the response.

I'd seen this in teql_master_xmit(), and it works *perfectly*, *if* we
let it do its job.

The only problem here is that the PPP code is greedily sucking up all
the packets it can, calling skb_dequeue() in a loop and not letting the
*other* device(s) get any of the packets. Even when it *doesn't* get a
packet because it's emptied the queue, it gets bumped to the front of
the slaves list again, so it'll get the *next* one!

Is it that behaviour which makes you say PPP is effectively a virtual
device for this purpose? I wonder if I should just *fix* that instead,
so that it behaves as like a real device.

It's a bad idea to have huge hidden queues (a whole wmem_default worth
of packets are in a hidden queue between ppp_generic and the ATM device,
ffs!) anyway, so perhaps if we just fix *that* within PPP, it should
work a bit better with TEQL?

The other odd thing that PPP does is call skb_dequeue, attempt to feed a
packet into the low-level driver, and then *requeue* the skb if that
fails. Which it *will* do, a lot of the time. So perhaps the PPP
low-level driver could have a method call to *ask* if it's able to
accept a new packet, to avoid that dequeue-and-requeue behaviour in
ppp_generic? I'll experiment with that.

> But this cannot, and is documented not to, work when device stacking
> is involved.
> 
> If you're dealing with (what amounts to) virtual devices, you cannot
> use TEQL and must use something like drivers/net/eql.c

I'd looked briefly at eql.c. I eventually found eql-1.2.tar.gz... with a
timestamp from a few months before I first encountered Linux in 1995, a
ZMAGIC binary in the tarball, and source code which probably hasn't
compiled for a decade... so then I figured I'd try TEQL a bit more
first :)

Having fixed up the userspace, eql.c *does* work OK — but it seems to be
fairly unloved, and mostly duplicates the functionality of TEQL. The
fact that it forgets its slaves when you take it down and up is a bit of
a PITA too. I think I'd be happier getting TEQL working.

-- 
dwmw2

[-- Attachment #2: smime.p7s --]
[-- Type: application/x-pkcs7-signature, Size: 5818 bytes --]

Re: [STRAW MAN PATCH] sch_teql doesn't load-balance ppp(oatm) slaves

[David Miller]

From: David Woodhouse <dwmw2@infradead.org>
Date: Sun, 25 Mar 2012 11:43:50 +0100

> It's a bad idea to have huge hidden queues (a whole wmem_default worth
> of packets are in a hidden queue between ppp_generic and the ATM device,
> ffs!) anyway, so perhaps if we just fix *that* within PPP, it should
> work a bit better with TEQL?

Yes, the ATM devices deep transmit queue is quite undesirable.

But I actually don't see how the problem arises yet, I need more
details.

PPP itself will always stop the queue, and return NETDEV_TX_OK on a
transmit attempt.  It may wake the queue back up before returning if
the downstream device (such as pppoatm) accepted the packet.

But in either case NETDEV_TX_OK is returned and this is what the teql
master transmit sees, and this takes the code path which advances the
slave pointer to the next device.

Therefore the next teql master transmit should try the next device in
the slave list, not the PPP device used in the previous call.

Re: [STRAW MAN PATCH] sch_teql doesn't load-balance ppp(oatm) slaves

[David Woodhouse]

[-- Attachment #1: Type: text/plain, Size: 5240 bytes --]

On Sun, 2012-03-25 at 17:36 -0400, David Miller wrote:
> From: David Woodhouse <dwmw2@infradead.org>
> Date: Sun, 25 Mar 2012 11:43:50 +0100
> 
> > It's a bad idea to have huge hidden queues (a whole wmem_default worth
> > of packets are in a hidden queue between ppp_generic and the ATM device,
> > ffs!) anyway, so perhaps if we just fix *that* within PPP, it should
> > work a bit better with TEQL?
> 
> Yes, the ATM devices deep transmit queue is quite undesirable.

Indeed, although I don't think it's the only cause of the problem I saw.

The first thing I tried was a hack in ppoatm_assign_vcc() to set the
socket's sk_sndbuf to 4KiB. It *seemed* to work, but only while all my
debugging printks in sch_teql were being spewed at 115200 baud over the
serial port. As soon as I hit SysRq-0 and the serial port delays went
away, I was back to bursts on one line then the other.

> But I actually don't see how the problem arises yet, I need more
> details.
>
> PPP itself will always stop the queue, and return NETDEV_TX_OK on a
> transmit attempt.  It may wake the queue back up before returning if
> the downstream device (such as pppoatm) accepted the packet.

It does indeed stop the queue. I think it then wakes it right back up
again in ppp_xmit_process(), *before* returning NETDEV_TX_OK. So the
offending calls to skb_dequeue() which are putting it back to the front
of the list are going to be from the softirq trying to feed the device.

I'll confirm that, then try fixing the PPP code so it doesn't stop and
immediately restart the queue. If it only stops the queue
*conditionally*, that may well fix the problem.

> But in either case NETDEV_TX_OK is returned and this is what the teql
> master transmit sees, and this takes the code path which advances the
> slave pointer to the next device.
> 
> Therefore the next teql master transmit should try the next device in
> the slave list, not the PPP device used in the previous call.

I instrumented everywhere that the 'next device' pointer (m->slaves) is
assigned in sch_teql. One of the printks you see below is in
teql_master_xmit(), and it's doing exactly what you say. And then
immediately afterwards you see the other printk in teql_dequeue(),
setting m->slaves right back to the original device again:

Mar 22 15:36:07 net1-173.woodhou.se kernel: [12612.673308] teql xmit cebca100 next cebca400
Mar 22 15:36:07 net1-173.woodhou.se kernel: [12612.677630] m->slaves becomes cebca100
Mar 22 15:36:07 net1-173.woodhou.se kernel: [12613.069589] teql xmit cebca100 next cebca400
Mar 22 15:36:07 net1-173.woodhou.se kernel: [12613.073884] m->slaves becomes cebca100
Mar 22 15:36:07 net1-173.woodhou.se kernel: [12613.113584] teql xmit cebca100 next cebca400
Mar 22 15:36:07 net1-173.woodhou.se kernel: [12613.117908] m->slaves becomes cebca100
Mar 22 15:36:08 net1-173.woodhou.se kernel: [12614.041113] teql xmit cebca100 next cebca400
Mar 22 15:36:08 net1-173.woodhou.se kernel: [12614.045411] m->slaves becomes cebca100
Mar 22 15:36:09 net1-173.woodhou.se kernel: [12614.258464] teql xmit cebca100 next cebca400
Mar 22 15:36:09 net1-173.woodhou.se kernel: [12614.262762] m->slaves becomes cebca100
Mar 22 15:36:09 net1-173.woodhou.se kernel: [12614.896259] teql xmit cebca100 next cebca400
Mar 22 15:36:09 net1-173.woodhou.se kernel: [12614.900559] m->slaves becomes cebca100
Mar 22 15:36:10 net1-173.woodhou.se kernel: [12616.129265] teql xmit cebca100 next cebca400
Mar 22 15:36:10 net1-173.woodhou.se kernel: [12616.133599] teql xmit cebca400 next cebca100
Mar 22 15:36:10 net1-173.woodhou.se kernel: [12616.137919] m->slaves becomes cebca100
Mar 22 15:36:10 net1-173.woodhou.se kernel: [12616.141673] m->slaves becomes cebca400
Mar 22 15:36:10 net1-173.woodhou.se kernel: [12616.148321] teql xmit cebca400 next cebca100
Mar 22 15:36:10 net1-173.woodhou.se kernel: [12616.152623] m->slaves becomes cebca400
Mar 22 15:36:10 net1-173.woodhou.se kernel: [12616.157979] teql xmit cebca400 next cebca100
Mar 22 15:36:10 net1-173.woodhou.se kernel: [12616.162276] m->slaves becomes cebca400
Mar 22 15:36:11 net1-173.woodhou.se kernel: [12616.172402] teql xmit cebca400 next cebca100
Mar 22 15:36:11 net1-173.woodhou.se kernel: [12616.176731] m->slaves becomes cebca400
Mar 22 15:36:13 net1-173.woodhou.se kernel: [12618.693948] teql xmit cebca400 next cebca100
Mar 22 15:36:13 net1-173.woodhou.se kernel: [12618.698275] m->slaves becomes cebca400
Mar 22 15:36:14 net1-173.woodhou.se kernel: [12619.263215] teql xmit cebca400 next cebca100
Mar 22 15:36:14 net1-173.woodhou.se kernel: [12619.267539] m->slaves becomes cebca400
Mar 22 15:36:14 net1-173.woodhou.se kernel: [12619.311534] teql xmit cebca400 next cebca100
Mar 22 15:36:14 net1-173.woodhou.se kernel: [12619.315828] m->slaves becomes cebca400
Mar 22 15:36:14 net1-173.woodhou.se kernel: [12619.645580] teql xmit cebca400 next cebca100

For the first few seconds it doesn't manage to send *any* packets out
the cebca400 queue. That queue gets marked as 'next', but never quite
makes it. And then it manages to flip, and for another few seconds it
sends *all* its packets out that queue, leaving the cebca100 queue idle.

-- 
dwmw2

[-- Attachment #2: smime.p7s --]
[-- Type: application/x-pkcs7-signature, Size: 5818 bytes --]

Re: [STRAW MAN PATCH] sch_teql doesn't load-balance ppp(oatm) slaves

[David Woodhouse]

[-- Attachment #1: Type: text/plain, Size: 2962 bytes --]

On Mon, 2012-03-26 at 09:32 +0100, David Woodhouse wrote:
> It does indeed stop the queue. I think it then wakes it right back up
> again in ppp_xmit_process(), *before* returning NETDEV_TX_OK. So the
> offending calls to skb_dequeue() which are putting it back to the front
> of the list are going to be from the softirq trying to feed the device.

A WARN_ON() in teql_dequeue() confirms that.

> I'll confirm that, then try fixing the PPP code so it doesn't stop and
> immediately restart the queue. If it only stops the queue
> *conditionally*, that may well fix the problem. 

Yes, this gives me my full upload bandwidth by spreading packets over
both lines correctly, without touching sch_teql.c.

It returns a value from ppp_xmit_process() which indicates whether the
queue should be stopped. It doesn't actually *remove* the call to
netif_wake_queue(), because other code paths (especially from
ppp_output_wakeup()) still need it to be there. But if the queue wasn't
stopped anyway, it's a no-op. So we just make ppp_start_xmit() stop the
queue based on the return value of ppp_xmit_process(), and it all works
nicely without any of the gratuitous softirq invocations which are a
waste of time in the normal case, and actively harmful with teql.

--- drivers/net/ppp/ppp_generic.c~	2012-01-26 00:39:32.000000000 +0000
+++ drivers/net/ppp/ppp_generic.c	2012-03-26 10:32:31.286744147 +0100
@@ -235,7 +235,7 @@ struct ppp_net {
 /* Prototypes. */
 static int ppp_unattached_ioctl(struct net *net, struct ppp_file *pf,
 			struct file *file, unsigned int cmd, unsigned long arg);
-static void ppp_xmit_process(struct ppp *ppp);
+static int ppp_xmit_process(struct ppp *ppp);
 static void ppp_send_frame(struct ppp *ppp, struct sk_buff *skb);
 static void ppp_push(struct ppp *ppp);
 static void ppp_channel_push(struct channel *pch);
@@ -968,9 +968,9 @@ ppp_start_xmit(struct sk_buff *skb, stru
 	proto = npindex_to_proto[npi];
 	put_unaligned_be16(proto, pp);
 
-	netif_stop_queue(dev);
 	skb_queue_tail(&ppp->file.xq, skb);
-	ppp_xmit_process(ppp);
+	if (!ppp_xmit_process(ppp))
+		netif_stop_queue(dev);
 	return NETDEV_TX_OK;
 
  outf:
@@ -1048,10 +1048,11 @@ static void ppp_setup(struct net_device
  * Called to do any work queued up on the transmit side
  * that can now be done.
  */
-static void
+static int
 ppp_xmit_process(struct ppp *ppp)
 {
 	struct sk_buff *skb;
+	int ret = 0;
 
 	ppp_xmit_lock(ppp);
 	if (!ppp->closing) {
@@ -1061,10 +1062,13 @@ ppp_xmit_process(struct ppp *ppp)
 			ppp_send_frame(ppp, skb);
 		/* If there's no work left to do, tell the core net
 		   code that we can accept some more. */
-		if (!ppp->xmit_pending && !skb_peek(&ppp->file.xq))
+		if (!ppp->xmit_pending && !skb_peek(&ppp->file.xq)) {
 			netif_wake_queue(ppp->dev);
+			ret = 1;
+		}
 	}
 	ppp_xmit_unlock(ppp);
+	return ret;
 }
 
 static inline struct sk_buff *


-- 
dwmw2

[-- Attachment #2: smime.p7s --]
[-- Type: application/x-pkcs7-signature, Size: 5818 bytes --]

[PATCH] ppp: Don't stop and restart queue on every TX packet

[David Woodhouse]

For every transmitted packet, ppp_start_xmit() will stop the netdev
queue and then, if appropriate, restart it. This causes the TX softirq
to run, entirely gratuitously.

This is "only" a waste of CPU time in the normal case, but it's actively
harmful when the PPP device is a TEQL slave — the wakeup will cause the
offending device to receive the next TX packet from the TEQL queue, when
it *should* have gone to the next slave in the list. We end up seeing
large bursts of packets on just *one* slave device, rather than using
the full available bandwidth over all slaves.

This patch fixes the problem by *not* unconditionally stopping the queue
in ppp_start_xmit(). It adds a return value from ppp_xmit_process()
which indicates whether the queue should be stopped or not.

It *doesn't* remove the call to netif_wake_queue() from
ppp_xmit_process(), because other code paths (especially from
ppp_output_wakeup()) need it there and it's messy to push it out to the
other callers to do it based on the return value. So we leave it in
place — it's a no-op in the case where the queue wasn't stopped, so it's
harmless in the TX path.

Signed-off-by: David Woodhouse <David.Woodhouse@intel.com>

--- drivers/net/ppp/ppp_generic.c~	2012-01-26 00:39:32.000000000 +0000
+++ drivers/net/ppp/ppp_generic.c	2012-03-26 10:32:31.286744147 +0100
@@ -235,7 +235,7 @@ struct ppp_net {
 /* Prototypes. */
 static int ppp_unattached_ioctl(struct net *net, struct ppp_file *pf,
 			struct file *file, unsigned int cmd, unsigned long arg);
-static void ppp_xmit_process(struct ppp *ppp);
+static int ppp_xmit_process(struct ppp *ppp);
 static void ppp_send_frame(struct ppp *ppp, struct sk_buff *skb);
 static void ppp_push(struct ppp *ppp);
 static void ppp_channel_push(struct channel *pch);
@@ -968,9 +968,9 @@ ppp_start_xmit(struct sk_buff *skb, stru
 	proto = npindex_to_proto[npi];
 	put_unaligned_be16(proto, pp);
 
-	netif_stop_queue(dev);
 	skb_queue_tail(&ppp->file.xq, skb);
-	ppp_xmit_process(ppp);
+	if (!ppp_xmit_process(ppp))
+		netif_stop_queue(dev);
 	return NETDEV_TX_OK;
 
  outf:
@@ -1048,10 +1048,11 @@ static void ppp_setup(struct net_device
  * Called to do any work queued up on the transmit side
  * that can now be done.
  */
-static void
+static int
 ppp_xmit_process(struct ppp *ppp)
 {
 	struct sk_buff *skb;
+	int ret = 0;
 
 	ppp_xmit_lock(ppp);
 	if (!ppp->closing) {
@@ -1061,10 +1062,13 @@ ppp_xmit_process(struct ppp *ppp)
 			ppp_send_frame(ppp, skb);
 		/* If there's no work left to do, tell the core net
 		   code that we can accept some more. */
-		if (!ppp->xmit_pending && !skb_peek(&ppp->file.xq))
+		if (!ppp->xmit_pending && !skb_peek(&ppp->file.xq)) {
 			netif_wake_queue(ppp->dev);
+			ret = 1;
+		}
 	}
 	ppp_xmit_unlock(ppp);
+	return ret;
 }
 
 static inline struct sk_buff *

-- 
David Woodhouse                            Open Source Technology Centre
David.Woodhouse@intel.com                              Intel Corporation

Re: [PATCH] ppp: Don't stop and restart queue on every TX packet

[David Miller]

From: David Woodhouse <dwmw2@infradead.org>
Date: Mon, 26 Mar 2012 11:03:42 +0100

> For every transmitted packet, ppp_start_xmit() will stop the netdev
> queue and then, if appropriate, restart it. This causes the TX softirq
> to run, entirely gratuitously.
> 
> This is "only" a waste of CPU time in the normal case, but it's actively
> harmful when the PPP device is a TEQL slave ― the wakeup will cause the
> offending device to receive the next TX packet from the TEQL queue, when
> it *should* have gone to the next slave in the list. We end up seeing
> large bursts of packets on just *one* slave device, rather than using
> the full available bandwidth over all slaves.
> 
> This patch fixes the problem by *not* unconditionally stopping the queue
> in ppp_start_xmit(). It adds a return value from ppp_xmit_process()
> which indicates whether the queue should be stopped or not.
> 
> It *doesn't* remove the call to netif_wake_queue() from
> ppp_xmit_process(), because other code paths (especially from
> ppp_output_wakeup()) need it there and it's messy to push it out to the
> other callers to do it based on the return value. So we leave it in
> place ― it's a no-op in the case where the queue wasn't stopped, so it's
> harmless in the TX path.
> 
> Signed-off-by: David Woodhouse <David.Woodhouse@intel.com>

Applied, thanks.  But:

> --- drivers/net/ppp/ppp_generic.c~	2012-01-26 00:39:32.000000000 +0000
> +++ drivers/net/ppp/ppp_generic.c	2012-03-26 10:32:31.286744147 +0100

Please -p1 root your patches in the future.

Re: [PATCH] ppp: Don't stop and restart queue on every TX packet

[David Woodhouse]

[-- Attachment #1: Type: text/plain, Size: 1702 bytes --]

On Tue, 2012-04-03 at 17:29 -0400, David Miller wrote:
> From: David Woodhouse <dwmw2@infradead.org>
> Date: Mon, 26 Mar 2012 11:03:42 +0100
> 
> > For every transmitted packet, ppp_start_xmit() will stop the netdev
> > queue and then, if appropriate, restart it. This causes the TX softirq
> > to run, entirely gratuitously.
> > 
> > This is "only" a waste of CPU time in the normal case, but it's actively
> > harmful when the PPP device is a TEQL slave ― the wakeup will cause the
> > offending device to receive the next TX packet from the TEQL queue, when
> > it *should* have gone to the next slave in the list. We end up seeing
> > large bursts of packets on just *one* slave device, rather than using
> > the full available bandwidth over all slaves.
> > 
> > This patch fixes the problem by *not* unconditionally stopping the queue
> > in ppp_start_xmit(). It adds a return value from ppp_xmit_process()
> > which indicates whether the queue should be stopped or not.
> > 
> > It *doesn't* remove the call to netif_wake_queue() from
> > ppp_xmit_process(), because other code paths (especially from
> > ppp_output_wakeup()) need it there and it's messy to push it out to the
> > other callers to do it based on the return value. So we leave it in
> > place ― it's a no-op in the case where the queue wasn't stopped, so it's
> > harmless in the TX path.
> > 
> > Signed-off-by: David Woodhouse <David.Woodhouse@intel.com>
> 
> Applied, thanks. 

Hmm. After going through the locking issues on wakeup, for the PPPoATM
patch I just sent, I think that the above has introduced a bug. I'll
send a patch with a full explanation in a few moments...

-- 
dwmw2

[-- Attachment #2: smime.p7s --]
[-- Type: application/x-pkcs7-signature, Size: 5818 bytes --]

ppp: Fix race condition with queue start/stop

[David Woodhouse]

Commit e675f0cc9a872fd152edc0c77acfed19bf28b81e ("ppp: Don't stop and
restart queue on every TX packet") introduced a race condition which
could leave the net queue stopped even when the channel is no longer
busy. By calling netif_stop_queue() from ppp_start_xmit(), based on the
return value from ppp_xmit_process() but *after* all the locks have been
dropped, we could potentially do so *after* the channel has actually
finished transmitting and attempted to re-wake the queue.

Fix this by moving the netif_stop_queue() into ppp_xmit_process() under
the xmit lock. I hadn't done this previously, because it gets called
from other places than ppp_start_xmit(). But I now think it's the better
option. The net queue *should* be stopped if the channel becomes
congested due to writes from pppd, anyway.

Signed-off-by: David Woodhouse <David.Woodhouse@intel.com>
---
 drivers/net/ppp/ppp_generic.c |   15 ++++++---------
 1 files changed, 6 insertions(+), 9 deletions(-)

diff --git a/drivers/net/ppp/ppp_generic.c b/drivers/net/ppp/ppp_generic.c
index 33f8c51..21d7151 100644
--- a/drivers/net/ppp/ppp_generic.c
+++ b/drivers/net/ppp/ppp_generic.c
@@ -235,7 +235,7 @@ struct ppp_net {
 /* Prototypes. */
 static int ppp_unattached_ioctl(struct net *net, struct ppp_file *pf,
 			struct file *file, unsigned int cmd, unsigned long arg);
-static int ppp_xmit_process(struct ppp *ppp);
+static void ppp_xmit_process(struct ppp *ppp);
 static void ppp_send_frame(struct ppp *ppp, struct sk_buff *skb);
 static void ppp_push(struct ppp *ppp);
 static void ppp_channel_push(struct channel *pch);
@@ -969,8 +969,7 @@ ppp_start_xmit(struct sk_buff *skb, struct net_device *dev)
 	put_unaligned_be16(proto, pp);
 
 	skb_queue_tail(&ppp->file.xq, skb);
-	if (!ppp_xmit_process(ppp))
-		netif_stop_queue(dev);
+	ppp_xmit_process(ppp);
 	return NETDEV_TX_OK;
 
  outf:
@@ -1048,11 +1047,10 @@ static void ppp_setup(struct net_device *dev)
  * Called to do any work queued up on the transmit side
  * that can now be done.
  */
-static int
+static void
 ppp_xmit_process(struct ppp *ppp)
 {
 	struct sk_buff *skb;
-	int ret = 0;
 
 	ppp_xmit_lock(ppp);
 	if (!ppp->closing) {
@@ -1062,13 +1060,12 @@ ppp_xmit_process(struct ppp *ppp)
 			ppp_send_frame(ppp, skb);
 		/* If there's no work left to do, tell the core net
 		   code that we can accept some more. */
-		if (!ppp->xmit_pending && !skb_peek(&ppp->file.xq)) {
+		if (!ppp->xmit_pending && !skb_peek(&ppp->file.xq))
 			netif_wake_queue(ppp->dev);
-			ret = 1;
-		}
+		else
+			netif_stop_queue(ppp->dev);
 	}
 	ppp_xmit_unlock(ppp);
-	return ret;
 }
 
 static inline struct sk_buff *
-- 
1.7.7.6



-- 
dwmw2

Re: ppp: Fix race condition with queue start/stop

[David Miller]

From: David Woodhouse <dwmw2@infradead.org>
Date: Sun, 08 Apr 2012 21:01:44 +0100

> Commit e675f0cc9a872fd152edc0c77acfed19bf28b81e ("ppp: Don't stop and
> restart queue on every TX packet") introduced a race condition which
> could leave the net queue stopped even when the channel is no longer
> busy. By calling netif_stop_queue() from ppp_start_xmit(), based on the
> return value from ppp_xmit_process() but *after* all the locks have been
> dropped, we could potentially do so *after* the channel has actually
> finished transmitting and attempted to re-wake the queue.
> 
> Fix this by moving the netif_stop_queue() into ppp_xmit_process() under
> the xmit lock. I hadn't done this previously, because it gets called
> from other places than ppp_start_xmit(). But I now think it's the better
> option. The net queue *should* be stopped if the channel becomes
> congested due to writes from pppd, anyway.
> 
> Signed-off-by: David Woodhouse <David.Woodhouse@intel.com>

Applied, thanks David.

Re: [STRAW MAN PATCH] sch_teql doesn't load-balance ppp(oatm) slaves

[David Woodhouse]

[-- Attachment #1: Type: text/plain, Size: 6940 bytes --]

On Sun, 2012-03-25 at 17:36 -0400, David Miller wrote:
> Yes, the ATM devices deep transmit queue is quite undesirable.

This should fix that, and while I'm at it should fix the gratuitous
running of ppp_output_wakeup() from a tasklet on *every* packet, when
it's almost never necessary. Some careful eyes over the locking issues
on that would be much appreciated. I've documented how I *think* it
works...

I'm tempted to rip out the atm_may_send() bit; there's not a lot of
point in checking against sk_sndbuf when we're limiting to two packets
anyway, is there? There's always been a problem here if sk_sndbuf was
set lower than the MTU of the interface; it would block for ever.

I'm running this now on my ADSL router. I can watch it working, keeping
precisely two packets in the queue at a time (one really in-flight and
one ready for the ATM driver). My leftover debugging in sch_teql is
triggering when the xmit returns NETDEV_TX_BUSY, and all seems to be
well.

--- net/atm/pppoatm.c~	2012-03-27 19:59:54.379565896 +0100
+++ net/atm/pppoatm.c	2012-03-27 20:03:02.676561017 +0100
@@ -62,10 +62,13 @@ struct pppoatm_vcc {
 	void (*old_pop)(struct atm_vcc *, struct sk_buff *);
 					/* keep old push/pop for detaching */
 	enum pppoatm_encaps encaps;
+	atomic_t inflight;
+	unsigned long blocked;
 	int flags;			/* SC_COMP_PROT - compress protocol */
 	struct ppp_channel chan;	/* interface to generic ppp layer */
 	struct tasklet_struct wakeup_tasklet;
 };
+#define BLOCKED 0
 
 /*
  * Header used for LLC Encapsulated PPP (4 bytes) followed by the LCP protocol
@@ -102,16 +105,31 @@ static void pppoatm_wakeup_sender(unsign
 static void pppoatm_pop(struct atm_vcc *atmvcc, struct sk_buff *skb)
 {
 	struct pppoatm_vcc *pvcc = atmvcc_to_pvcc(atmvcc);
+
 	pvcc->old_pop(atmvcc, skb);
+	smp_mb__before_atomic_dec();
+	atomic_dec(&pvcc->inflight);
+
 	/*
-	 * We don't really always want to do this since it's
-	 * really inefficient - it would be much better if we could
-	 * test if we had actually throttled the generic layer.
-	 * Unfortunately then there would be a nasty SMP race where
-	 * we could clear that flag just as we refuse another packet.
-	 * For now we do the safe thing.
+	 * We always used to run the wakeup tasklet unconditionally here, for
+	 * fear of race conditions where we clear the BLOCKED flag just as we
+	 * refuse another packet in pppoatm_send(). This was quite inefficient.
+	 *
+	 * In fact it's OK. The PPP core will only ever call pppoatm_send()
+	 * while holding the channel->downl lock. And ppp_output_wakeup() as
+	 * called by the tasklet will *also* grab that lock. So even if another
+	 * CPU is in pppoatm_send() right now, the tasklet isn't going to race
+	 * with it. The wakeup *will* happen after the other CPU is safely out
+	 * of pppoatm_send() again.
+	 *
+	 * So if the CPU in pppoatm_send() has already set the BLOCKED bit and
+	 * it about to return, that's fine. We trigger a wakeup which will
+	 * happen later. And if the CPU in pppoatm_send() *hasn't* set the
+	 * BLOCKED bit yet, that's fine too because of the double check in
+	 * pppoatm_may_send() which is commented there.
 	 */
-	tasklet_schedule(&pvcc->wakeup_tasklet);
+	if (test_and_clear_bit(BLOCKED, &pvcc->blocked))
+		tasklet_schedule(&pvcc->wakeup_tasklet);
 }
 
 /*
@@ -184,6 +202,54 @@ error:
 	ppp_input_error(&pvcc->chan, 0);
 }
 
+static inline int pppoatm_may_send(struct pppoatm_vcc *pvcc, int size)
+{
+	/*
+	 * We allow two packets in the queue. The one that's currently
+	 * in flight, and *one* queued up ready for the ATM device to
+	 * send immediately from its TX done IRQ. More than that is
+	 * unnecessary, since the PPP core is designed to feed us packets
+	 * with extremely low latency anyway.
+	 *
+	 * It's not clear that we need to bother with using atm_may_send()
+	 * to check we don't exceed sk->sk_sndbuf. If userspace sets a
+	 * value of sk_sndbuf which is lower than the MTU, we're going to
+	 * block for ever. But the code always did that before we introduced
+	 * the packet count limit, so... 
+	 */
+	if (atm_may_send(pvcc->atmvcc, size) &&
+	    atomic_inc_not_zero_hint(&pvcc->inflight, -2)) {
+		smp_mb__after_atomic_inc();
+		return 1;
+	}
+
+	smp_mb__before_clear_bit();
+	set_bit(BLOCKED, &pvcc->blocked);
+	smp_mb__after_clear_bit();
+	/*
+	 * We may have raced with pppoatm_pop(). If it ran for the
+	 * last packet in the queue, *just* before we set the BLOCKED
+	 * bit, then it might never run again and the channel could
+	 * remain permanently blocked. Cope with that race by checking
+	 * *again*. If it did run in that window, we'll have space on
+	 * the queue now and can return success. It's harmless to leave
+	 * the BLOCKED flag set, since it's only used as a trigger to
+	 * run the wakeup tasklet. 
+	 * If pppoatm_pop() is running but hasn't got as far as making
+	 * space on the queue yet, then it hasn't checked the BLOCKED
+	 * flag yet either, so we're safe in that case too. It'll issue
+	 * an "immediate" wakeup... where "immediate" actually involves
+	 * taking the PPP channel's ->downl lock, which is held by the
+	 * code path that calls pppoatm_send(), and is thus going to
+	 * wait for us to finish.
+	 */
+	if (atm_may_send(pvcc->atmvcc, size) &&
+	    atomic_inc_not_zero(&pvcc->inflight)) {
+		smp_mb__after_atomic_inc();
+		return 1;
+	}
+	return 0;
+}
 /*
  * Called by the ppp_generic.c to send a packet - returns true if packet
  * was accepted.  If we return false, then it's our job to call
@@ -207,7 +273,7 @@ static int pppoatm_send(struct ppp_chann
 			struct sk_buff *n;
 			n = skb_realloc_headroom(skb, LLC_LEN);
 			if (n != NULL &&
-			    !atm_may_send(pvcc->atmvcc, n->truesize)) {
+			    !pppoatm_may_send(pvcc, n->truesize)) {
 				kfree_skb(n);
 				goto nospace;
 			}
@@ -215,12 +281,12 @@ static int pppoatm_send(struct ppp_chann
 			skb = n;
 			if (skb == NULL)
 				return DROP_PACKET;
-		} else if (!atm_may_send(pvcc->atmvcc, skb->truesize))
+		} else if (!pppoatm_may_send(pvcc, skb->truesize))
 			goto nospace;
 		memcpy(skb_push(skb, LLC_LEN), pppllc, LLC_LEN);
 		break;
 	case e_vc:
-		if (!atm_may_send(pvcc->atmvcc, skb->truesize))
+		if (!pppoatm_may_send(pvcc, skb->truesize))
 			goto nospace;
 		break;
 	case e_autodetect:
@@ -285,6 +351,9 @@ static int pppoatm_assign_vcc(struct atm
 	if (pvcc == NULL)
 		return -ENOMEM;
 	pvcc->atmvcc = atmvcc;
+
+	/* Maximum is zero, so that we can use atomic_inc_not_zero() */
+	atomic_set(&pvcc->inflight, -2);
 	pvcc->old_push = atmvcc->push;
 	pvcc->old_pop = atmvcc->pop;
 	pvcc->encaps = (enum pppoatm_encaps) be.encaps;


-- 
David Woodhouse                            Open Source Technology Centre
David.Woodhouse@intel.com                              Intel Corporation



[-- Attachment #2: smime.p7s --]
[-- Type: application/x-pkcs7-signature, Size: 5818 bytes --]

Re: [STRAW MAN PATCH] sch_teql doesn't load-balance ppp(oatm) slaves

[Eric Dumazet]

On Tue, 2012-03-27 at 20:10 +0100, David Woodhouse wrote:
> On Sun, 2012-03-25 at 17:36 -0400, David Miller wrote:
> > Yes, the ATM devices deep transmit queue is quite undesirable.
> 
> This should fix that, and while I'm at it should fix the gratuitous
> running of ppp_output_wakeup() from a tasklet on *every* packet, when
> it's almost never necessary. Some careful eyes over the locking issues
> on that would be much appreciated. I've documented how I *think* it
> works...
> 
> I'm tempted to rip out the atm_may_send() bit; there's not a lot of
> point in checking against sk_sndbuf when we're limiting to two packets
> anyway, is there? There's always been a problem here if sk_sndbuf was
> set lower than the MTU of the interface; it would block for ever.
> 
> I'm running this now on my ADSL router. I can watch it working, keeping
> precisely two packets in the queue at a time (one really in-flight and
> one ready for the ATM driver). My leftover debugging in sch_teql is
> triggering when the xmit returns NETDEV_TX_BUSY, and all seems to be
> well.
> 
> --- net/atm/pppoatm.c~	2012-03-27 19:59:54.379565896 +0100
> +++ net/atm/pppoatm.c	2012-03-27 20:03:02.676561017 +0100
> @@ -62,10 +62,13 @@ struct pppoatm_vcc {
>  	void (*old_pop)(struct atm_vcc *, struct sk_buff *);
>  					/* keep old push/pop for detaching */
>  	enum pppoatm_encaps encaps;
> +	atomic_t inflight;
> +	unsigned long blocked;
>  	int flags;			/* SC_COMP_PROT - compress protocol */
>  	struct ppp_channel chan;	/* interface to generic ppp layer */
>  	struct tasklet_struct wakeup_tasklet;
>  };
> +#define BLOCKED 0
>  
>  /*
>   * Header used for LLC Encapsulated PPP (4 bytes) followed by the LCP protocol
> @@ -102,16 +105,31 @@ static void pppoatm_wakeup_sender(unsign
>  static void pppoatm_pop(struct atm_vcc *atmvcc, struct sk_buff *skb)
>  {
>  	struct pppoatm_vcc *pvcc = atmvcc_to_pvcc(atmvcc);
> +
>  	pvcc->old_pop(atmvcc, skb);
> +	smp_mb__before_atomic_dec();

I have no idea why you added all these barriers...

> +	atomic_dec(&pvcc->inflight);
> +
>  	/*

Re: [STRAW MAN PATCH] sch_teql doesn't load-balance ppp(oatm) slaves

[David Woodhouse]

[-- Attachment #1: Type: text/plain, Size: 1278 bytes --]

On Tue, 2012-03-27 at 21:55 +0200, Eric Dumazet wrote:
> I have no idea why you added all these barriers... 

Um, some of them snuck in while I was working it out, and then I
couldn't prove to myself that they *weren't* needed, so I left them.

We definitely need a write barrier in pppoatm_pop() after the change to
sk->sk_sndbuf (which happens in the old_pop routine) and the increment
of pvcc->inflight. Those changes must hit *before* the test/change of
the BLOCKED bit.

But there's an implicit barrier in test_and_clear_bit() which should
achieve that, so the specific barrier you highlight may well be
superfluous. I could have sworn I had a reason for it at the time, but
can't justify it now.

On the pppoatm_may_send() side, the change to the BLOCKED bit needs a
corresponding read barrier after it, to ensure that its subsequent
checks of sk->sndbuf and pvcc->inflight are looking at the data which
were written before the BLOCKED bit is tested in pppoatm_pop().

But I suppose we can probably dispense with the barrier *before* setting
the BLOCKED bit in pppoatm_may_send(), and the barriers after increasing
pvcc->inflight.

If it looks sane other than that, I can knock up a new patch with a
S-O-B. Thanks for reviewing...

-- 
dwmw2

[-- Attachment #2: smime.p7s --]
[-- Type: application/x-pkcs7-signature, Size: 5818 bytes --]

[PATCH] pppoatm: Fix excessive queue bloat

[David Woodhouse]

[-- Attachment #1: Type: text/plain, Size: 7951 bytes --]

We discovered that PPPoATM has an excessively deep transmit queue. A
queue the size of the default socket send buffer (wmem_default) is
maintained between the PPP generic core and the ATM device.

Fix it to queue a maximum of *two* packets. The one the ATM device is
currently working on, and one more for the ATM driver to process
immediately in its TX done interrupt handler. The PPP core is designed
to feed packets to the channel with minimal latency, so that really
ought to be enough to keep the ATM device busy.

While we're at it, fix the fact that we were triggering the wakeup
tasklet on *every* pppoatm_pop() call. The comment saying "this is
inefficient, but doing it right is too hard" turns out to be overly
pessimistic... I think :)

On machines like the Traverse Geos, with a slow Geode CPU and two
high-speed ADSL2+ interfaces, there were reports of extremely high CPU
usage which could partly be attributed to the extra wakeups.

(The wakeup handling could actually be made a whole lot easier if we
 stop checking sk->sk_sndbuf altogether. Given that we now only queue
 *two* packets ever, one wonders what the point is. As it is, you could
 already deadlock the thing by setting the sk_sndbuf to a value lower
 than the MTU of the device, and it'd just block for ever.)

Signed-off-by: David Woodhouse <David.Woodhouse@intel.com>

---

Seriously, this gets *much* easier if we just ditch the checks against
sk_sndbuf. We just wake up whenever decrementing ->inflight from zero.
Can I?

 net/atm/pppoatm.c |   95 +++++++++++++++++++++++++++++++++++++++++++++++-----
 1 files changed, 85 insertions(+), 10 deletions(-)

diff --git a/net/atm/pppoatm.c b/net/atm/pppoatm.c
index 614d3fc..68a02a9 100644
--- a/net/atm/pppoatm.c
+++ b/net/atm/pppoatm.c
@@ -62,12 +62,25 @@ struct pppoatm_vcc {
 	void (*old_pop)(struct atm_vcc *, struct sk_buff *);
 					/* keep old push/pop for detaching */
 	enum pppoatm_encaps encaps;
+	atomic_t inflight;
+	unsigned long blocked;
 	int flags;			/* SC_COMP_PROT - compress protocol */
 	struct ppp_channel chan;	/* interface to generic ppp layer */
 	struct tasklet_struct wakeup_tasklet;
 };
 
 /*
+ * We want to allow two packets in the queue. The one that's currently in
+ * flight, and *one* queued up ready for the ATM device to send immediately
+ * from its TX done IRQ. We want to be able to use atomic_inc_not_zero(), so
+ * inflight == -2 represents an empty queue, -1 one packet, and zero means
+ * there are two packets in the queue.
+ */
+#define NONE_INFLIGHT -2
+
+#define BLOCKED 0
+
+/*
  * Header used for LLC Encapsulated PPP (4 bytes) followed by the LCP protocol
  * ID (0xC021) used in autodetection
  */
@@ -102,16 +115,30 @@ static void pppoatm_wakeup_sender(unsigned long arg)
 static void pppoatm_pop(struct atm_vcc *atmvcc, struct sk_buff *skb)
 {
 	struct pppoatm_vcc *pvcc = atmvcc_to_pvcc(atmvcc);
+
 	pvcc->old_pop(atmvcc, skb);
+	atomic_dec(&pvcc->inflight);
+
 	/*
-	 * We don't really always want to do this since it's
-	 * really inefficient - it would be much better if we could
-	 * test if we had actually throttled the generic layer.
-	 * Unfortunately then there would be a nasty SMP race where
-	 * we could clear that flag just as we refuse another packet.
-	 * For now we do the safe thing.
+	 * We always used to run the wakeup tasklet unconditionally here, for
+	 * fear of race conditions where we clear the BLOCKED flag just as we
+	 * refuse another packet in pppoatm_send(). This was quite inefficient.
+	 *
+	 * In fact it's OK. The PPP core will only ever call pppoatm_send()
+	 * while holding the channel->downl lock. And ppp_output_wakeup() as
+	 * called by the tasklet will *also* grab that lock. So even if another
+	 * CPU is in pppoatm_send() right now, the tasklet isn't going to race
+	 * with it. The wakeup *will* happen after the other CPU is safely out
+	 * of pppoatm_send() again.
+	 *
+	 * So if the CPU in pppoatm_send() has already set the BLOCKED bit and
+	 * it about to return, that's fine. We trigger a wakeup which will
+	 * happen later. And if the CPU in pppoatm_send() *hasn't* set the
+	 * BLOCKED bit yet, that's fine too because of the double check in
+	 * pppoatm_may_send() which is commented there.
 	 */
-	tasklet_schedule(&pvcc->wakeup_tasklet);
+	if (test_and_clear_bit(BLOCKED, &pvcc->blocked))
+		tasklet_schedule(&pvcc->wakeup_tasklet);
 }
 
 /*
@@ -184,6 +211,51 @@ error:
 	ppp_input_error(&pvcc->chan, 0);
 }
 
+static inline int pppoatm_may_send(struct pppoatm_vcc *pvcc, int size)
+{
+	/*
+	 * It's not clear that we need to bother with using atm_may_send()
+	 * to check we don't exceed sk->sk_sndbuf. If userspace sets a
+	 * value of sk_sndbuf which is lower than the MTU, we're going to
+	 * block for ever. But the code always did that before we introduced
+	 * the packet count limit, so... 
+	 */
+	if (atm_may_send(pvcc->atmvcc, size) &&
+	    atomic_inc_not_zero_hint(&pvcc->inflight, NONE_INFLIGHT))
+		return 1;
+
+	/*
+	 * We use test_and_set_bit() rather than set_bit() here because
+	 * we need to ensure there's a memory barrier after it. The bit
+	 * *must* be set before we do the atomic_inc() on pvcc->inflight.
+	 * There's no smp_mb__after_set_bit(), so it's this or abuse
+	 * smp_mb__after_clear_bit().
+	 */
+	test_and_set_bit(BLOCKED, &pvcc->blocked);
+
+	/*
+	 * We may have raced with pppoatm_pop(). If it ran for the
+	 * last packet in the queue, *just* before we set the BLOCKED
+	 * bit, then it might never run again and the channel could
+	 * remain permanently blocked. Cope with that race by checking
+	 * *again*. If it did run in that window, we'll have space on
+	 * the queue now and can return success. It's harmless to leave
+	 * the BLOCKED flag set, since it's only used as a trigger to
+	 * run the wakeup tasklet. Another wakeup will never hurt. 
+	 * If pppoatm_pop() is running but hasn't got as far as making
+	 * space on the queue yet, then it hasn't checked the BLOCKED
+	 * flag yet either, so we're safe in that case too. It'll issue
+	 * an "immediate" wakeup... where "immediate" actually involves
+	 * taking the PPP channel's ->downl lock, which is held by the
+	 * code path that calls pppoatm_send(), and is thus going to
+	 * wait for us to finish.
+	 */
+	if (atm_may_send(pvcc->atmvcc, size) &&
+	    atomic_inc_not_zero(&pvcc->inflight))
+		return 1;
+
+	return 0;
+}
 /*
  * Called by the ppp_generic.c to send a packet - returns true if packet
  * was accepted.  If we return false, then it's our job to call
@@ -207,7 +279,7 @@ static int pppoatm_send(struct ppp_channel *chan, struct sk_buff *skb)
 			struct sk_buff *n;
 			n = skb_realloc_headroom(skb, LLC_LEN);
 			if (n != NULL &&
-			    !atm_may_send(pvcc->atmvcc, n->truesize)) {
+			    !pppoatm_may_send(pvcc, n->truesize)) {
 				kfree_skb(n);
 				goto nospace;
 			}
@@ -215,12 +287,12 @@ static int pppoatm_send(struct ppp_channel *chan, struct sk_buff *skb)
 			skb = n;
 			if (skb == NULL)
 				return DROP_PACKET;
-		} else if (!atm_may_send(pvcc->atmvcc, skb->truesize))
+		} else if (!pppoatm_may_send(pvcc, skb->truesize))
 			goto nospace;
 		memcpy(skb_push(skb, LLC_LEN), pppllc, LLC_LEN);
 		break;
 	case e_vc:
-		if (!atm_may_send(pvcc->atmvcc, skb->truesize))
+		if (!pppoatm_may_send(pvcc, skb->truesize))
 			goto nospace;
 		break;
 	case e_autodetect:
@@ -285,6 +357,9 @@ static int pppoatm_assign_vcc(struct atm_vcc *atmvcc, void __user *arg)
 	if (pvcc == NULL)
 		return -ENOMEM;
 	pvcc->atmvcc = atmvcc;
+
+	/* Maximum is zero, so that we can use atomic_inc_not_zero() */
+	atomic_set(&pvcc->inflight, NONE_INFLIGHT);
 	pvcc->old_push = atmvcc->push;
 	pvcc->old_pop = atmvcc->pop;
 	pvcc->encaps = (enum pppoatm_encaps) be.encaps;
-- 
1.7.7.6



-- 
dwmw2

[-- Attachment #2: smime.p7s --]
[-- Type: application/x-pkcs7-signature, Size: 5818 bytes --]

Re: [PATCH] pppoatm: Fix excessive queue bloat

[chas williams - CONTRACTOR]

On Sun, 08 Apr 2012 21:53:57 +0200
David Woodhouse <dwmw2@infradead.org> wrote:

> Seriously, this gets *much* easier if we just ditch the checks against
> sk_sndbuf. We just wake up whenever decrementing ->inflight from zero.
> Can I?

i dont know.  on a 'low' speed connection like queuing 2 packets might
be enough to keep something busy but imagine an interace like oc3 or
oc12.  i dont know anything running pppoatm on such an interface but it
seems like just dropping sk_sndbuf isnt right either.

sk_sndbuf is per vcc and that isnt right either since the transmit
limit is actually the atm device's transmit queue depth.  in your case,
since you are only using a single vcc, this problem does somewhat map
to a sk_sndbuf.  but sk_sndbuf counts bytes and not entries in a queue
which is typically the limit imposed by the hardware.

it makes me wonder if we dont need to add another stub to the atm
driver interface to check if the device can transmit instead of 'can we
queue on the vcc'.  atm_may_send() then would be changed to check to see
if a transmit queue entry is available and there is sk_sndbuf queue
space.  if a driver doesnt have this stub to check for queue space,
atm_may_send() can just assume there is a queue entry and we get the
previous default behavior.  what is the "queue depth" of your atm
device's transmit queue?
 
yes, the vcc->sk_sndbuf should be MAX(vcc->sk_sndbuf, pppoatm->MTU) but
since people dont often change the sk_sndbuf i guess no one has run
into this issue.   pppoatm (et al) should enforce this limit though.

Re: [PATCH] pppoatm: Fix excessive queue bloat

[David Woodhouse]

[-- Attachment #1: Type: text/plain, Size: 2662 bytes --]

On Tue, 2012-04-10 at 10:26 -0400, chas williams - CONTRACTOR wrote:
> On Sun, 08 Apr 2012 21:53:57 +0200
> David Woodhouse <dwmw2@infradead.org> wrote:
> 
> > Seriously, this gets *much* easier if we just ditch the checks against
> > sk_sndbuf. We just wake up whenever decrementing ->inflight from zero.
> > Can I?
> 
> i dont know.  on a 'low' speed connection like queuing 2 packets might
> be enough to keep something busy but imagine an interace like oc3 or
> oc12.  i dont know anything running pppoatm on such an interface but it
> seems like just dropping sk_sndbuf isnt right either.

That looks like a response to my patch, not to the question that you
cited. My patch reduces the buffering to MAX(vcc->sk_sndbuf, 2 packets)
so if there are issues with keeping faster devices busy, they'll happen
anyway with my patch. (My question was just whether we can ditch the
sk_sndbuf bit altogether, and just make it a hard-coded two packets.)

The limit of two packets was chosen on the basis that the PPP core is
designed to feed us new packets when we need them, with *low* latency.
So when the hardware finishes sending packet #1 and starts on packet #2,
we *should* be able to get a packet #3 into its queue by the time it
needs it.

But if that approach could really cause an issue with keeping faster
devices busy, perhaps the limit should be "x ms worth of packets" based
on the upload speed of the device, rather than a hard-coded 2?

Not that we *know* the upload speed of the device, for asymmetric
links... do we?

> sk_sndbuf is per vcc and that isnt right either since the transmit
> limit is actually the atm device's transmit queue depth.

Hm, I don't think that's a limit that I care about. You're talking about
the maximum number of packets that can be queued to the hardware at a
time. What I care about is the *minimum* number of packets that *need*
to be queued to the hardware, to ensure that it doesn't stall waiting
for us to replenish its queue.

Which is largely a factor of how well the PPP core does the job it was
*designed* to do, as I see it.

> what is the "queue depth" of your atm device's transmit queue?

We're still using MMIO for the Solos ADSL2+ devices at the moment, so
there's no descriptor ring. It used to have internal buffering which was
only limited by the device's internal memory — it would continue to
accept packets from the host until it had nowhere else to put them. I
got them to fix that in its firmware, so now it only has two or three
packets queued internally. But as far as the host is concerned, those
packets are *gone* already.

-- 
dwmw2

[-- Attachment #2: smime.p7s --]
[-- Type: application/x-pkcs7-signature, Size: 5818 bytes --]

Re: [PATCH] pppoatm: Fix excessive queue bloat

[David Miller]

From: chas williams - CONTRACTOR <chas@cmf.nrl.navy.mil>
Date: Tue, 10 Apr 2012 10:26:12 -0400

> On Sun, 08 Apr 2012 21:53:57 +0200
> David Woodhouse <dwmw2@infradead.org> wrote:
> 
>> Seriously, this gets *much* easier if we just ditch the checks against
>> sk_sndbuf. We just wake up whenever decrementing ->inflight from zero.
>> Can I?
> 
> i dont know.

Please do not take this discussion private, and off of the netdev list.

Now nobody else on the list can see your response and and reply to it.

Re: [PATCH] pppoatm: Fix excessive queue bloat

[David Miller]

From: David Miller <davem@davemloft.net>
Date: Fri, 13 Apr 2012 13:04:52 -0400 (EDT)

> From: chas williams - CONTRACTOR <chas@cmf.nrl.navy.mil>
> Date: Tue, 10 Apr 2012 10:26:12 -0400
> 
>> On Sun, 08 Apr 2012 21:53:57 +0200
>> David Woodhouse <dwmw2@infradead.org> wrote:
>> 
>>> Seriously, this gets *much* easier if we just ditch the checks against
>>> sk_sndbuf. We just wake up whenever decrementing ->inflight from zero.
>>> Can I?
>> 
>> i dont know.
> 
> Please do not take this discussion private, and off of the netdev list.
> 
> Now nobody else on the list can see your response and and reply to it.

My bad, you didn't do this, my apologies.

But for some reason your replies didn't show up in the patchwork
entry for this patch, maybe your email client fumbled up the Message-Ids
because that's what patchwork uses to match things up.

Re: [PATCH] pppoatm: Fix excessive queue bloat

[David Miller]

From: David Woodhouse <dwmw2@infradead.org>
Date: Sun, 08 Apr 2012 21:53:57 +0200

> We discovered that PPPoATM has an excessively deep transmit queue. A
> queue the size of the default socket send buffer (wmem_default) is
> maintained between the PPP generic core and the ATM device.
> 
> Fix it to queue a maximum of *two* packets. The one the ATM device is
> currently working on, and one more for the ATM driver to process
> immediately in its TX done interrupt handler. The PPP core is designed
> to feed packets to the channel with minimal latency, so that really
> ought to be enough to keep the ATM device busy.
> 
> While we're at it, fix the fact that we were triggering the wakeup
> tasklet on *every* pppoatm_pop() call. The comment saying "this is
> inefficient, but doing it right is too hard" turns out to be overly
> pessimistic... I think :)
> 
> On machines like the Traverse Geos, with a slow Geode CPU and two
> high-speed ADSL2+ interfaces, there were reports of extremely high CPU
> usage which could partly be attributed to the extra wakeups.
> 
> (The wakeup handling could actually be made a whole lot easier if we
>  stop checking sk->sk_sndbuf altogether. Given that we now only queue
>  *two* packets ever, one wonders what the point is. As it is, you could
>  already deadlock the thing by setting the sk_sndbuf to a value lower
>  than the MTU of the device, and it'd just block for ever.)
> 
> Signed-off-by: David Woodhouse <David.Woodhouse@intel.com>

Applied to net-next, thanks David.

I always considered the use of socket buffers to handle packets
moving around the ATM layers as a fundamental design error.

Although it's major surgery, fixing that up would be a much
appreciated contribution for someone suitably motivated :-)

[PATCH] pppoatm: Fix excessive queue bloat

[David Woodhouse]

[-- Attachment #1: Type: text/plain, Size: 7951 bytes --]

We discovered that PPPoATM has an excessively deep transmit queue. A
queue the size of the default socket send buffer (wmem_default) is
maintained between the PPP generic core and the ATM device.

Fix it to queue a maximum of *two* packets. The one the ATM device is
currently working on, and one more for the ATM driver to process
immediately in its TX done interrupt handler. The PPP core is designed
to feed packets to the channel with minimal latency, so that really
ought to be enough to keep the ATM device busy.

While we're at it, fix the fact that we were triggering the wakeup
tasklet on *every* pppoatm_pop() call. The comment saying "this is
inefficient, but doing it right is too hard" turns out to be overly
pessimistic... I think :)

On machines like the Traverse Geos, with a slow Geode CPU and two
high-speed ADSL2+ interfaces, there were reports of extremely high CPU
usage which could partly be attributed to the extra wakeups.

(The wakeup handling could actually be made a whole lot easier if we
 stop checking sk->sk_sndbuf altogether. Given that we now only queue
 *two* packets ever, one wonders what the point is. As it is, you could
 already deadlock the thing by setting the sk_sndbuf to a value lower
 than the MTU of the device, and it'd just block for ever.)

Signed-off-by: David Woodhouse <David.Woodhouse@intel.com>

---

Seriously, this gets *much* easier if we just ditch the checks against
sk_sndbuf. We just wake up whenever decrementing ->inflight from zero.
Can I?

 net/atm/pppoatm.c |   95 +++++++++++++++++++++++++++++++++++++++++++++++-----
 1 files changed, 85 insertions(+), 10 deletions(-)

diff --git a/net/atm/pppoatm.c b/net/atm/pppoatm.c
index 614d3fc..68a02a9 100644
--- a/net/atm/pppoatm.c
+++ b/net/atm/pppoatm.c
@@ -62,12 +62,25 @@ struct pppoatm_vcc {
 	void (*old_pop)(struct atm_vcc *, struct sk_buff *);
 					/* keep old push/pop for detaching */
 	enum pppoatm_encaps encaps;
+	atomic_t inflight;
+	unsigned long blocked;
 	int flags;			/* SC_COMP_PROT - compress protocol */
 	struct ppp_channel chan;	/* interface to generic ppp layer */
 	struct tasklet_struct wakeup_tasklet;
 };
 
 /*
+ * We want to allow two packets in the queue. The one that's currently in
+ * flight, and *one* queued up ready for the ATM device to send immediately
+ * from its TX done IRQ. We want to be able to use atomic_inc_not_zero(), so
+ * inflight == -2 represents an empty queue, -1 one packet, and zero means
+ * there are two packets in the queue.
+ */
+#define NONE_INFLIGHT -2
+
+#define BLOCKED 0
+
+/*
  * Header used for LLC Encapsulated PPP (4 bytes) followed by the LCP protocol
  * ID (0xC021) used in autodetection
  */
@@ -102,16 +115,30 @@ static void pppoatm_wakeup_sender(unsigned long arg)
 static void pppoatm_pop(struct atm_vcc *atmvcc, struct sk_buff *skb)
 {
 	struct pppoatm_vcc *pvcc = atmvcc_to_pvcc(atmvcc);
+
 	pvcc->old_pop(atmvcc, skb);
+	atomic_dec(&pvcc->inflight);
+
 	/*
-	 * We don't really always want to do this since it's
-	 * really inefficient - it would be much better if we could
-	 * test if we had actually throttled the generic layer.
-	 * Unfortunately then there would be a nasty SMP race where
-	 * we could clear that flag just as we refuse another packet.
-	 * For now we do the safe thing.
+	 * We always used to run the wakeup tasklet unconditionally here, for
+	 * fear of race conditions where we clear the BLOCKED flag just as we
+	 * refuse another packet in pppoatm_send(). This was quite inefficient.
+	 *
+	 * In fact it's OK. The PPP core will only ever call pppoatm_send()
+	 * while holding the channel->downl lock. And ppp_output_wakeup() as
+	 * called by the tasklet will *also* grab that lock. So even if another
+	 * CPU is in pppoatm_send() right now, the tasklet isn't going to race
+	 * with it. The wakeup *will* happen after the other CPU is safely out
+	 * of pppoatm_send() again.
+	 *
+	 * So if the CPU in pppoatm_send() has already set the BLOCKED bit and
+	 * it about to return, that's fine. We trigger a wakeup which will
+	 * happen later. And if the CPU in pppoatm_send() *hasn't* set the
+	 * BLOCKED bit yet, that's fine too because of the double check in
+	 * pppoatm_may_send() which is commented there.
 	 */
-	tasklet_schedule(&pvcc->wakeup_tasklet);
+	if (test_and_clear_bit(BLOCKED, &pvcc->blocked))
+		tasklet_schedule(&pvcc->wakeup_tasklet);
 }
 
 /*
@@ -184,6 +211,51 @@ error:
 	ppp_input_error(&pvcc->chan, 0);
 }
 
+static inline int pppoatm_may_send(struct pppoatm_vcc *pvcc, int size)
+{
+	/*
+	 * It's not clear that we need to bother with using atm_may_send()
+	 * to check we don't exceed sk->sk_sndbuf. If userspace sets a
+	 * value of sk_sndbuf which is lower than the MTU, we're going to
+	 * block for ever. But the code always did that before we introduced
+	 * the packet count limit, so... 
+	 */
+	if (atm_may_send(pvcc->atmvcc, size) &&
+	    atomic_inc_not_zero_hint(&pvcc->inflight, NONE_INFLIGHT))
+		return 1;
+
+	/*
+	 * We use test_and_set_bit() rather than set_bit() here because
+	 * we need to ensure there's a memory barrier after it. The bit
+	 * *must* be set before we do the atomic_inc() on pvcc->inflight.
+	 * There's no smp_mb__after_set_bit(), so it's this or abuse
+	 * smp_mb__after_clear_bit().
+	 */
+	test_and_set_bit(BLOCKED, &pvcc->blocked);
+
+	/*
+	 * We may have raced with pppoatm_pop(). If it ran for the
+	 * last packet in the queue, *just* before we set the BLOCKED
+	 * bit, then it might never run again and the channel could
+	 * remain permanently blocked. Cope with that race by checking
+	 * *again*. If it did run in that window, we'll have space on
+	 * the queue now and can return success. It's harmless to leave
+	 * the BLOCKED flag set, since it's only used as a trigger to
+	 * run the wakeup tasklet. Another wakeup will never hurt. 
+	 * If pppoatm_pop() is running but hasn't got as far as making
+	 * space on the queue yet, then it hasn't checked the BLOCKED
+	 * flag yet either, so we're safe in that case too. It'll issue
+	 * an "immediate" wakeup... where "immediate" actually involves
+	 * taking the PPP channel's ->downl lock, which is held by the
+	 * code path that calls pppoatm_send(), and is thus going to
+	 * wait for us to finish.
+	 */
+	if (atm_may_send(pvcc->atmvcc, size) &&
+	    atomic_inc_not_zero(&pvcc->inflight))
+		return 1;
+
+	return 0;
+}
 /*
  * Called by the ppp_generic.c to send a packet - returns true if packet
  * was accepted.  If we return false, then it's our job to call
@@ -207,7 +279,7 @@ static int pppoatm_send(struct ppp_channel *chan, struct sk_buff *skb)
 			struct sk_buff *n;
 			n = skb_realloc_headroom(skb, LLC_LEN);
 			if (n != NULL &&
-			    !atm_may_send(pvcc->atmvcc, n->truesize)) {
+			    !pppoatm_may_send(pvcc, n->truesize)) {
 				kfree_skb(n);
 				goto nospace;
 			}
@@ -215,12 +287,12 @@ static int pppoatm_send(struct ppp_channel *chan, struct sk_buff *skb)
 			skb = n;
 			if (skb == NULL)
 				return DROP_PACKET;
-		} else if (!atm_may_send(pvcc->atmvcc, skb->truesize))
+		} else if (!pppoatm_may_send(pvcc, skb->truesize))
 			goto nospace;
 		memcpy(skb_push(skb, LLC_LEN), pppllc, LLC_LEN);
 		break;
 	case e_vc:
-		if (!atm_may_send(pvcc->atmvcc, skb->truesize))
+		if (!pppoatm_may_send(pvcc, skb->truesize))
 			goto nospace;
 		break;
 	case e_autodetect:
@@ -285,6 +357,9 @@ static int pppoatm_assign_vcc(struct atm_vcc *atmvcc, void __user *arg)
 	if (pvcc == NULL)
 		return -ENOMEM;
 	pvcc->atmvcc = atmvcc;
+
+	/* Maximum is zero, so that we can use atomic_inc_not_zero() */
+	atomic_set(&pvcc->inflight, NONE_INFLIGHT);
 	pvcc->old_push = atmvcc->push;
 	pvcc->old_pop = atmvcc->pop;
 	pvcc->encaps = (enum pppoatm_encaps) be.encaps;
-- 
1.7.7.6



-- 
dwmw2

[-- Attachment #2: smime.p7s --]
[-- Type: application/x-pkcs7-signature, Size: 5818 bytes --]