From: Cong Wang <hidden> Date: 2017-12-22 00:03:40
qdisc_reset() should always be called with qdisc spinlock
and with BH disabled, otherwise qdisc ->reset() could race
with TX BH.
Fixes: 7bbde83b1860 ("net: sched: drop qdisc_reset from dev_graft_qdisc")
Reported-by: Jakub Kicinski <redacted>
Cc: John Fastabend <john.fastabend@gmail.com>
Signed-off-by: Cong Wang <redacted>
---
net/sched/sch_generic.c | 5 ++++-
1 file changed, 4 insertions(+), 1 deletion(-)
From: Cong Wang <hidden> Date: 2017-12-22 00:03:44
__skb_array_empty() is only safe if array is never resized.
pfifo_fast_dequeue() is called in TX BH context and without
qdisc lock, so even after we disable BH on ->reset() path
we can still race with other CPU's.
Fixes: c5ad119fb6c0 ("net: sched: pfifo_fast use skb_array")
Reported-by: Jakub Kicinski <redacted>
Cc: John Fastabend <john.fastabend@gmail.com>
Signed-off-by: Cong Wang <redacted>
---
net/sched/sch_generic.c | 3 ---
1 file changed, 3 deletions(-)
From: John Fastabend <john.fastabend@gmail.com> Date: 2017-12-22 03:06:46
On 12/21/2017 04:03 PM, Cong Wang wrote:
quoted hunk
__skb_array_empty() is only safe if array is never resized.
pfifo_fast_dequeue() is called in TX BH context and without
qdisc lock, so even after we disable BH on ->reset() path
we can still race with other CPU's.
Fixes: c5ad119fb6c0 ("net: sched: pfifo_fast use skb_array")
Reported-by: Jakub Kicinski <redacted>
Cc: John Fastabend <john.fastabend@gmail.com>
Signed-off-by: Cong Wang <redacted>
---
net/sched/sch_generic.c | 3 ---
1 file changed, 3 deletions(-)
So this is a performance thing we don't want to grab the consumer lock on
empty bands. Which can be fairly common depending on traffic patterns.
Although its not logical IMO to have both reset and dequeue running at
the same time. Some skbs would get through others would get sent, sort
of a mess. I don't see how it can be an issue. The never resized bit
in the documentation is referring to resizing the ring size _not_ popping
off elements of the ring. array_empty just reads the consumer head.
The only ring resizing in pfifo fast should be at init and destroy where
enqueue/dequeue should be disconnected by then. Although based on the
trace I missed a case.
I think the right fix is to only call reset/destroy patterns after
waiting a grace period and for all tx_action calls in-flight to
complete. This is also better going forward for more complex qdiscs.
.John
OK first the cases to get to qdisc_reset that I've tracked
down are,
dev_shutdown()
qdisc_destroy()
dev_deactivate_many()
dev_qdisc_reset() <- for each txq
qdisc_reset()
chained calls from qdisc_reset ops
At the moment all the lockless qdiscs don't care about chained
calls so we can ignore that, but would be nice to keep in mind.
Next qdisc_reset() is doing a couple things calling the qdisc
ops reset call but also walking gso_skb and skb_bad_txq. The
'unlink' operations there are not safe to be called while an
enqueue/dequeue op is in-flight. Also pfifo_fast's reset op
is not safe to be called with enqueue/dequeue ops in-flight.
So I've made the assumption that qdisc_reset is _only_ ever
called after a qdisc is no longer attached on the enqueue
dev_xmit side and also any in-progress tx_action calls are
completed. For what its worth this has always been the assumption
AFAIK.
So those are the assumptions what did I miss?
The biggest gap I see is dev_deactivate_many() is supposed
to wait for all tx_action calls to complete, this bit:
/* Wait for outstanding qdisc_run calls. */
list_for_each_entry(dev, head, close_list) {
while (some_qdisc_is_busy(dev))
yield();
Where some_qdisc_is_busy in the lockless case only does
the following,
if (q->flags & TCQ_F_NOLOCK) {
val = test_bit(__QDISC_STATE_SCHED, &q->state);
Oops that only tells us something is scheduled nothing about
if something is running. Excerpt from tx_action side here
clear_bit(__QDISC_STATE_SCHED, &q->state);
qdisc_run(q);
For comparison here is the check in the qdisc locked branch of
some_qdisc_is_busy,
root_lock = qdisc_lock(q);
spin_lock_bh(root_lock);
val = (qdisc_is_running(q) ||
test_bit(__QDISC_STATE_SCHED, &q->state));
spin_unlock_bh(root_lock);
previously we had the qdisc_lock() to protect the bit clear and then in
the some_qdisc_is_busy case we still did a qdisc_is_running() call. The
easiest fix I see is add the qdisc_is_running() check to the TCQ_F_NOLOCK
case in some_qdisc_is_busy AND to be correct I guess we should set the
running bit before clearing the QDISC_STATE_SCHED bit to be correct.
Untested but perhaps as simple as,
From: Cong Wang <hidden> Date: 2017-12-22 20:31:35
On Thu, Dec 21, 2017 at 7:06 PM, John Fastabend
[off-list ref] wrote:
On 12/21/2017 04:03 PM, Cong Wang wrote:
quoted
__skb_array_empty() is only safe if array is never resized.
pfifo_fast_dequeue() is called in TX BH context and without
qdisc lock, so even after we disable BH on ->reset() path
we can still race with other CPU's.
Fixes: c5ad119fb6c0 ("net: sched: pfifo_fast use skb_array")
Reported-by: Jakub Kicinski <redacted>
Cc: John Fastabend <john.fastabend@gmail.com>
Signed-off-by: Cong Wang <redacted>
---
net/sched/sch_generic.c | 3 ---
1 file changed, 3 deletions(-)
So this is a performance thing we don't want to grab the consumer lock on
empty bands. Which can be fairly common depending on traffic patterns.
I understand why you had it, but it is just not safe. You don't want
to achieve performance gain by crashing system, right?
Although its not logical IMO to have both reset and dequeue running at
the same time. Some skbs would get through others would get sent, sort
of a mess. I don't see how it can be an issue. The never resized bit
in the documentation is referring to resizing the ring size _not_ popping
off elements of the ring. array_empty just reads the consumer head.
The only ring resizing in pfifo fast should be at init and destroy where
enqueue/dequeue should be disconnected by then. Although based on the
trace I missed a case.
Both pfifo_fast_reset() and pfifo_fast_dequeue() call
skb_array_consume_bh(), so there is no difference w.r.t. resizing.
And ->reset() is called in qdisc_graft() too. Let's say we have htb+pfifo_fast,
htb_graft() calls qdisc_replace() which calls qdisc_reset() on pfifo_fast,
so clearly pfifo_fast_reset() can run with pfifo_fast_dequeue()
concurrently.
I think the right fix is to only call reset/destroy patterns after
waiting a grace period and for all tx_action calls in-flight to
complete. This is also better going forward for more complex qdiscs.
But we don't even have rcu read lock in TX BH, do we?
Also, people certainly don't like yet another synchronize_net()...
OK first the cases to get to qdisc_reset that I've tracked
down are,
dev_shutdown()
qdisc_destroy()
dev_deactivate_many()
dev_qdisc_reset() <- for each txq
qdisc_reset()
chained calls from qdisc_reset ops
At the moment all the lockless qdiscs don't care about chained
calls so we can ignore that, but would be nice to keep in mind.
Next qdisc_reset() is doing a couple things calling the qdisc
ops reset call but also walking gso_skb and skb_bad_txq. The
'unlink' operations there are not safe to be called while an
enqueue/dequeue op is in-flight. Also pfifo_fast's reset op
is not safe to be called with enqueue/dequeue ops in-flight.
This is why I sent two patches instead just this one.
So I've made the assumption that qdisc_reset is _only_ ever
called after a qdisc is no longer attached on the enqueue
dev_xmit side and also any in-progress tx_action calls are
completed. For what its worth this has always been the assumption
AFAIK.
So those are the assumptions what did I miss?
Speaking of this, qdisc_reset() is also called in dev_deactivate_queue()
even before synchronize_net()...
The biggest gap I see is dev_deactivate_many() is supposed
to wait for all tx_action calls to complete, this bit:
In some_qdisc_is_busy() you hold qdisc spinlock for non-lockless
ones, I don't understand why you don't want it in dev_qdisc_reset().
From: John Fastabend <john.fastabend@gmail.com> Date: 2017-12-24 06:58:28
On 12/22/2017 12:31 PM, Cong Wang wrote:
On Thu, Dec 21, 2017 at 7:06 PM, John Fastabend
[off-list ref] wrote:
quoted
On 12/21/2017 04:03 PM, Cong Wang wrote:
quoted
__skb_array_empty() is only safe if array is never resized.
pfifo_fast_dequeue() is called in TX BH context and without
qdisc lock, so even after we disable BH on ->reset() path
we can still race with other CPU's.
Fixes: c5ad119fb6c0 ("net: sched: pfifo_fast use skb_array")
Reported-by: Jakub Kicinski <redacted>
Cc: John Fastabend <john.fastabend@gmail.com>
Signed-off-by: Cong Wang <redacted>
---
net/sched/sch_generic.c | 3 ---
1 file changed, 3 deletions(-)
So this is a performance thing we don't want to grab the consumer lock on
empty bands. Which can be fairly common depending on traffic patterns.
I understand why you had it, but it is just not safe. You don't want
to achieve performance gain by crashing system, right?
huh? So my point is the patch you submit here is not a
real fix but a work around. To peek the head of a consumer/producer ring
without a lock, _should_ be fine. This _should_ work as well with
consumer or producer operations happening at the same time. After some
digging the issue is in the ptr_ring code.
The peek code (what empty check calls) is the following,
static inline void *__ptr_ring_peek(struct ptr_ring *r)
{
if (likely(r->size))
return r->queue[r->consumer_head];
return NULL;
}
So what the splat is detecting is consumer head being 'out of bounds'.
This happens because ptr_ring_discard_one increments the consumer_head
and then checks to see if it overran the array size. If above peek
happens after the increment, but before the size check we get the
splat. There are two ways, as far as I can see, to fix this. First
do the check before incrementing the consumer head. Or the easier
fix,
@@ -438,7 +438,7 @@ static inline int ptr_ring_consume_batched_bh(struct
ptr_ring *r,
static inline void **__ptr_ring_init_queue_alloc(unsigned int size,
gfp_t gfp)
{
- return kcalloc(size, sizeof(void *), gfp);
+ return kcalloc(size + 1, sizeof(void *), gfp);
}
With Jakub's help (Thanks!) I was able to reproduce the original splat
and also verify the above removes it.
To be clear "resizing" a skb_array only refers to changing the actual
array size not adding/removing elements.
quoted
Although its not logical IMO to have both reset and dequeue running at
the same time. Some skbs would get through others would get sent, sort
of a mess. I don't see how it can be an issue. The never resized bit
in the documentation is referring to resizing the ring size _not_ popping
off elements of the ring. array_empty just reads the consumer head.
The only ring resizing in pfifo fast should be at init and destroy where
enqueue/dequeue should be disconnected by then. Although based on the
trace I missed a case.
Both pfifo_fast_reset() and pfifo_fast_dequeue() call
skb_array_consume_bh(), so there is no difference w.r.t. resizing.
Sorry not following.
And ->reset() is called in qdisc_graft() too. Let's say we have htb+pfifo_fast,
htb_graft() calls qdisc_replace() which calls qdisc_reset() on pfifo_fast,
so clearly pfifo_fast_reset() can run with pfifo_fast_dequeue()
concurrently.
Yes and this _should_ be perfectly fine for pfifo_fast. I'm wondering
though if this API can be cleaned up. What are the paths that do a reset
without a destroy.. Do we really need to have this pattern where reset
is called then later destroy. Seems destroy could do the entire cleanup
and this would simplify things. None of this has to do with the splat
though.
quoted
I think the right fix is to only call reset/destroy patterns after
waiting a grace period and for all tx_action calls in-flight to
complete. This is also better going forward for more complex qdiscs.
But we don't even have rcu read lock in TX BH, do we?
Also, people certainly don't like yet another synchronize_net()...
This needs a fix and is a _real_ bug, but removing __skb_array_empty()
doesn't help solve this at all. Will work on a fix after the holiday
break. The fix here is to ensure the destroy is not going to happen
while tx_action is in-flight. Can be done with qdisc_run and checking
correct bits in lockless case.
.John
From: Cong Wang <hidden> Date: 2017-12-27 18:30:14
On Sat, Dec 23, 2017 at 10:57 PM, John Fastabend
[off-list ref] wrote:
On 12/22/2017 12:31 PM, Cong Wang wrote:
quoted
I understand why you had it, but it is just not safe. You don't want
to achieve performance gain by crashing system, right?
huh? So my point is the patch you submit here is not a
real fix but a work around. To peek the head of a consumer/producer ring
without a lock, _should_ be fine. This _should_ work as well with
consumer or producer operations happening at the same time. After some
digging the issue is in the ptr_ring code.
The comments disagree with you:
/* Might be slightly faster than skb_array_empty below, but only safe if the
* array is never resized. Also, callers invoking this in a loop must take care
* to use a compiler barrier, for example cpu_relax().
*/
If the comments are right, you miss a barrier here too.
quoted hunk
The peek code (what empty check calls) is the following,
static inline void *__ptr_ring_peek(struct ptr_ring *r)
{
if (likely(r->size))
return r->queue[r->consumer_head];
return NULL;
}
So what the splat is detecting is consumer head being 'out of bounds'.
This happens because ptr_ring_discard_one increments the consumer_head
and then checks to see if it overran the array size. If above peek
happens after the increment, but before the size check we get the
splat. There are two ways, as far as I can see, to fix this. First
do the check before incrementing the consumer head. Or the easier
fix,
@@ -438,7 +438,7 @@ static inline int ptr_ring_consume_batched_bh(struct
ptr_ring *r,
static inline void **__ptr_ring_init_queue_alloc(unsigned int size,
gfp_t gfp)
{
- return kcalloc(size, sizeof(void *), gfp);
+ return kcalloc(size + 1, sizeof(void *), gfp);
}
With Jakub's help (Thanks!) I was able to reproduce the original splat
and also verify the above removes it.
To be clear "resizing" a skb_array only refers to changing the actual
array size not adding/removing elements.
I never look into the implementation, just simply trust the comments.
At least the comments above __skb_array_empty() need to improve.
quoted
quoted
Although its not logical IMO to have both reset and dequeue running at
the same time. Some skbs would get through others would get sent, sort
of a mess. I don't see how it can be an issue. The never resized bit
in the documentation is referring to resizing the ring size _not_ popping
off elements of the ring. array_empty just reads the consumer head.
The only ring resizing in pfifo fast should be at init and destroy where
enqueue/dequeue should be disconnected by then. Although based on the
trace I missed a case.
Both pfifo_fast_reset() and pfifo_fast_dequeue() call
skb_array_consume_bh(), so there is no difference w.r.t. resizing.
Sorry not following.
quoted
And ->reset() is called in qdisc_graft() too. Let's say we have htb+pfifo_fast,
htb_graft() calls qdisc_replace() which calls qdisc_reset() on pfifo_fast,
so clearly pfifo_fast_reset() can run with pfifo_fast_dequeue()
concurrently.
Yes and this _should_ be perfectly fine for pfifo_fast. I'm wondering
though if this API can be cleaned up. What are the paths that do a reset
without a destroy.. Do we really need to have this pattern where reset
is called then later destroy. Seems destroy could do the entire cleanup
and this would simplify things. None of this has to do with the splat
though.
I don't follow your point any more.
We are talking about ->reset() race with ->dequeue() which is the
cause of the bug, right?
If you expect ->reset() runs in parallel with ->dequeue() for pfifo_fast,
why did you even mention synchronize_net() from the beginning???
Also you changed the code too, to adjust rcu grace period.
quoted
quoted
I think the right fix is to only call reset/destroy patterns after
waiting a grace period and for all tx_action calls in-flight to
complete. This is also better going forward for more complex qdiscs.
But we don't even have rcu read lock in TX BH, do we?
Also, people certainly don't like yet another synchronize_net()...
This needs a fix and is a _real_ bug, but removing __skb_array_empty()
doesn't help solve this at all. Will work on a fix after the holiday
break. The fix here is to ensure the destroy is not going to happen
while tx_action is in-flight. Can be done with qdisc_run and checking
correct bits in lockless case.
Sounds like you missed a lot of things with your "lockless" patches....
First qdisc rcu callback, second rcu read lock in TX BH...
My quick one-line fix is to amend this bug before you going deeper
in this rabbit hole.
From: John Fastabend <john.fastabend@gmail.com> Date: 2017-12-27 23:53:50
On 12/27/2017 10:29 AM, Cong Wang wrote:
On Sat, Dec 23, 2017 at 10:57 PM, John Fastabend
[off-list ref] wrote:
quoted
On 12/22/2017 12:31 PM, Cong Wang wrote:
quoted
I understand why you had it, but it is just not safe. You don't want
to achieve performance gain by crashing system, right?
huh? So my point is the patch you submit here is not a
real fix but a work around. To peek the head of a consumer/producer ring
without a lock, _should_ be fine. This _should_ work as well with
consumer or producer operations happening at the same time. After some
digging the issue is in the ptr_ring code.
The comments disagree with you:
/* Might be slightly faster than skb_array_empty below, but only safe if the
* array is never resized. Also, callers invoking this in a loop must take care
* to use a compiler barrier, for example cpu_relax().
*/
If the comments are right, you miss a barrier here too.
The comment talks about resizing arrays not consumer/producer operations
so I think it is OK. We don't call skb_array_empty on the same skb_array
in a loop here, its different skb arrays. So probably don't need a barrier.
quoted
The peek code (what empty check calls) is the following,
static inline void *__ptr_ring_peek(struct ptr_ring *r)
{
if (likely(r->size))
return r->queue[r->consumer_head];
return NULL;
}
So what the splat is detecting is consumer head being 'out of bounds'.
This happens because ptr_ring_discard_one increments the consumer_head
and then checks to see if it overran the array size. If above peek
happens after the increment, but before the size check we get the
splat. There are two ways, as far as I can see, to fix this. First
do the check before incrementing the consumer head. Or the easier
fix,
@@ -438,7 +438,7 @@ static inline int ptr_ring_consume_batched_bh(struct
ptr_ring *r,
static inline void **__ptr_ring_init_queue_alloc(unsigned int size,
gfp_t gfp)
{
- return kcalloc(size, sizeof(void *), gfp);
+ return kcalloc(size + 1, sizeof(void *), gfp);
}
With Jakub's help (Thanks!) I was able to reproduce the original splat
and also verify the above removes it.
To be clear "resizing" a skb_array only refers to changing the actual
array size not adding/removing elements.
I never look into the implementation, just simply trust the comments.
At least the comments above __skb_array_empty() need to improve.
quoted
quoted
quoted
Although its not logical IMO to have both reset and dequeue running at
the same time. Some skbs would get through others would get sent, sort
of a mess. I don't see how it can be an issue. The never resized bit
in the documentation is referring to resizing the ring size _not_ popping
off elements of the ring. array_empty just reads the consumer head.
The only ring resizing in pfifo fast should be at init and destroy where
enqueue/dequeue should be disconnected by then. Although based on the
trace I missed a case.
Both pfifo_fast_reset() and pfifo_fast_dequeue() call
skb_array_consume_bh(), so there is no difference w.r.t. resizing.
Sorry not following.
quoted
And ->reset() is called in qdisc_graft() too. Let's say we have htb+pfifo_fast,
htb_graft() calls qdisc_replace() which calls qdisc_reset() on pfifo_fast,
so clearly pfifo_fast_reset() can run with pfifo_fast_dequeue()
concurrently.
Yes and this _should_ be perfectly fine for pfifo_fast. I'm wondering
though if this API can be cleaned up. What are the paths that do a reset
without a destroy.. Do we really need to have this pattern where reset
is called then later destroy. Seems destroy could do the entire cleanup
and this would simplify things. None of this has to do with the splat
though.
I don't follow your point any more.>
We are talking about ->reset() race with ->dequeue() which is the
cause of the bug, right?>
Yes. But it should be OK for qdiscs to have reset and dequeue run
in parallel. So the bug is in ptr_ring.
If you expect ->reset() runs in parallel with ->dequeue() for pfifo_fast,
why did you even mention synchronize_net() from the beginning???
A mistake probably I am tracking two separate issues. First this one
with skb_array out of bounds access and the tx_action being called
while destroy is in progress. When I was first looking at this I thought
the splat was from the tx_action issue so probably started talking
about how to sync destroy and tx_action paths. Either way it was
a mistake to mention in this thread.
Also you changed the code too, to adjust rcu grace period.
quoted
quoted
quoted
I think the right fix is to only call reset/destroy patterns after
waiting a grace period and for all tx_action calls in-flight to
complete. This is also better going forward for more complex qdiscs.
But we don't even have rcu read lock in TX BH, do we?
Also, people certainly don't like yet another synchronize_net()...
This needs a fix and is a _real_ bug, but removing __skb_array_empty()
doesn't help solve this at all. Will work on a fix after the holiday
break. The fix here is to ensure the destroy is not going to happen
while tx_action is in-flight. Can be done with qdisc_run and checking
correct bits in lockless case.
Sounds like you missed a lot of things with your "lockless" patches....
First qdisc rcu callback, second rcu read lock in TX BH...
A couple things yes. TX BH, ptr_ring bug, skb list free fixed in
another patch. I assume the qdisc rcu callbacks you talk about are
the TX BH or something else?
The other possible bug, still need to do analysis, is if we need to
add back the qdisc destroy rcu callback. Or if there is a grace period
in all cases. My guess is current code paths in pfifo fast don't have
an issue but future work will.
My quick one-line fix is to amend this bug before you going deeper
in this rabbit hole.
Nope its not a good fix and we are in net-next timeframe here so lets
fix the root cause in ptr_ring. Will post a patch in the next couple
days after PTO. Its minor issue and can wait.
.John
From: David Miller <davem@davemloft.net> Date: 2018-01-02 16:37:34
From: Cong Wang <redacted>
Date: Thu, 21 Dec 2017 16:03:30 -0800
__skb_array_empty() is only safe if array is never resized.
pfifo_fast_dequeue() is called in TX BH context and without
qdisc lock, so even after we disable BH on ->reset() path
we can still race with other CPU's.
Fixes: c5ad119fb6c0 ("net: sched: pfifo_fast use skb_array")
Reported-by: Jakub Kicinski <redacted>
Cc: John Fastabend <john.fastabend@gmail.com>
Signed-off-by: Cong Wang <redacted>
Based upon the discussion over this patch, this bug is ultimately fixed
by John's patch which adds a dummy element at the end of allocated
ptr_ring queues.
And I've just applied that.
From: David Miller <davem@davemloft.net> Date: 2018-01-02 16:39:15
From: Cong Wang <redacted>
Date: Thu, 21 Dec 2017 16:03:29 -0800
qdisc_reset() should always be called with qdisc spinlock
and with BH disabled, otherwise qdisc ->reset() could race
with TX BH.
Fixes: 7bbde83b1860 ("net: sched: drop qdisc_reset from dev_graft_qdisc")
Reported-by: Jakub Kicinski <redacted>
Cc: John Fastabend <john.fastabend@gmail.com>
Signed-off-by: Cong Wang <redacted>
There doesn't seem to be agreement over whether qdisc_reset() really
needs to run with the lock held. In fact, the general consensus is
that this really shouldn't run until a grace period had occurred and
therefore parallel TX paths cannot be running any longer.
In any event, this was supposed to work towards a bug fix which
ultimately was fixed instead with the ptr_ring change from John.
So this seems unnecessary now.
If you disagree, please repost with an updated commit message which
explains things further.
Thank you.