Deadlock in IPv6 code while garbage collection on the rwlock protecting the routing tree.

Deadlock in IPv6 code while garbage collection on the rwlock protecting the routing tree.

[Akkipeddi, Srinivas]

I came across a deadlock scenario in the latest IPv6 code. I am trying
to fix this and any inputs are really appreciated. 

The deadlock happens when ROUTER-PREF is configured. This happens when
trying to do a write_lock_bh on the rwlock protecting the routing tree
during garbage collection.

The routing tree is read protected (read_lock_bh(&table->tb6_lock))
using the rwlock when performing a ip6_route_input or  ip6_route_output
( "ip6_pol_route"). During route selection (rt6_select), if a neighbor
solicit is sent (ndisc_send_ns), a dst_entry is allocated
(icmp6_dst_alloc calls dst_alloc). 
The garbage collection (fib6_run_gc) will be triggered if the number of
dst-entries is more than the threshold (dst_alloc). During garbage
collection, all the routing trees are cleaned up (fib6_clean_all). Here
we try to take write protect each routing tree (
write_lock_bh(&table->tb6_lock)). But one of the trees is already read
protected. 

The garbage collection is anyways triggered from "icmp6_dst_alloc" with
the call to fib6_force_start_gc. Since it is triggered, we might not
want to call the "fib6_run_gc" from dst_alloc for this case but there is
no way to figure this out in the "dst_alloc" routine.


Thanks
Srinivas

 



This email and any attachments may contain legally privileged and/or confidential information of Starent Networks, Corp. and is intended only for the individual or entity named in the message.  The information transmitted may not be used to create or change any contractual obligations of Starent Networks, Corp.  Any review, retransmission, dissemination or other use of, or taking of any action in reliance upon this e-mail and its attachments by persons or entities other than the intended recipient is prohibited. If you are not the intended recipient, please notify the sender immediately -- by replying to this message or by sending an email to postmaster@starentnetworks.com -- and destroy all copies of this message and any attachments without reading or disclosing their contents. Thank you.
 

Re: Deadlock in IPv6 code while garbage collection on the rwlock protecting the routing tree.

[Stephen Hemminger]

On Tue, 22 Dec 2009 16:57:05 -0500
"Akkipeddi, Srinivas" <sakkiped@starentnetworks.com> wrote:

> I came across a deadlock scenario in the latest IPv6 code. I am trying
> to fix this and any inputs are really appreciated. 
> 
> The deadlock happens when ROUTER-PREF is configured. This happens when
> trying to do a write_lock_bh on the rwlock protecting the routing tree
> during garbage collection.
> 
> The routing tree is read protected (read_lock_bh(&table->tb6_lock))
> using the rwlock when performing a ip6_route_input or  ip6_route_output
> ( "ip6_pol_route"). During route selection (rt6_select), if a neighbor
> solicit is sent (ndisc_send_ns), a dst_entry is allocated
> (icmp6_dst_alloc calls dst_alloc). 
> The garbage collection (fib6_run_gc) will be triggered if the number of
> dst-entries is more than the threshold (dst_alloc). During garbage
> collection, all the routing trees are cleaned up (fib6_clean_all). Here
> we try to take write protect each routing tree (
> write_lock_bh(&table->tb6_lock)). But one of the trees is already read
> protected. 
> 
> The garbage collection is anyways triggered from "icmp6_dst_alloc" with
> the call to fib6_force_start_gc. Since it is triggered, we might not
> want to call the "fib6_run_gc" from dst_alloc for this case but there is
> no way to figure this out in the "dst_alloc" routine.

Might just be easier to convert to spinlock and RCU.

-- 

Re: Deadlock in IPv6 code while garbage collection on the rwlock protecting the routing tree.

[Dave Johnson]

Stephen Hemminger writes:
> On Tue, 22 Dec 2009 16:57:05 -0500
> "Akkipeddi, Srinivas" <sakkiped@starentnetworks.com> wrote:
> 
> > I came across a deadlock scenario in the latest IPv6 code. I am trying
> > to fix this and any inputs are really appreciated. 
> > 
> > The deadlock happens when ROUTER-PREF is configured. This happens when
> > trying to do a write_lock_bh on the rwlock protecting the routing tree
> > during garbage collection.
> > 
> > The routing tree is read protected (read_lock_bh(&table->tb6_lock))
> > using the rwlock when performing a ip6_route_input or  ip6_route_output
> > ( "ip6_pol_route"). During route selection (rt6_select), if a neighbor
> > solicit is sent (ndisc_send_ns), a dst_entry is allocated
> > (icmp6_dst_alloc calls dst_alloc). 
> > The garbage collection (fib6_run_gc) will be triggered if the number of
> > dst-entries is more than the threshold (dst_alloc). During garbage
> > collection, all the routing trees are cleaned up (fib6_clean_all). Here
> > we try to take write protect each routing tree (
> > write_lock_bh(&table->tb6_lock)). But one of the trees is already read
> > protected. 
> > 
> > The garbage collection is anyways triggered from "icmp6_dst_alloc" with
> > the call to fib6_force_start_gc. Since it is triggered, we might not
> > want to call the "fib6_run_gc" from dst_alloc for this case but there is
> > no way to figure this out in the "dst_alloc" routine.
> 
> Might just be easier to convert to spinlock and RCU.

I don't think that would help.  You would still have a writer
contained within a reader issue.  This would also likely involve quite
a bit of copying given the amount of data the existing rwlock is
protecting and how frequent write locks may be needed.

The syncronize_rcu() call would have to be done from another thread
otherwise it would just stall forever because it would have been
called from a code path that holds a rcu read lock.

The area of uncertainty about how to fix this is because of the large
number of paths into the garbage collection code, one of which we hit
and resulted in this writer within reader deadlock.

It seems like the garbage collection cannot be done from within this
path and should only be done from an isolated path where it is
guaranteed to be called from a reader-free source.

Another possibility is to change the garbage collection to use a write
try lock and just not garbage collect from any tables it can't obtain.

-- 
Dave Johnson
Starent Networks

Re: Deadlock in IPv6 code while garbage collection on the rwlock protecting the routing tree.

[Stephen Hemminger]

On Wed, 23 Dec 2009 12:44:31 -0500
Dave Johnson <djohnson@starentnetworks.com> wrote:

> I don't think that would help.  You would still have a writer
> contained within a reader issue.  This would also likely involve quite
> a bit of copying given the amount of data the existing rwlock is
> protecting and how frequent write locks may be needed.

With RCU, you can safely acquire a spinlock inside rcu_read_lock
section.  The only issue is that the entry being modified might already
be in process of being deleted (ie. modifying a dead route).

Probably simpler to just get rid of rwlock entirely, go with a spinlock
for now.  Reader/writer locks are slower than spin locks and even if
lock is highly read contended, it is not held for long.

IPV6 routing table is using much simpler algorithms on the assumption
that IPV6 was going to solve the CIDR address explosion problem. That
assumption will probably not hold up, and having a trie (TRASH) version
of IPV6 routing table with RCU would be a good research project for
some graduate student.

-- 

Re: Deadlock in IPv6 code while garbage collection on the rwlock protecting the routing tree.

[David Miller]

From: Stephen Hemminger <shemminger@vyatta.com>
Date: Wed, 23 Dec 2009 10:13:09 -0800

> With RCU, you can safely acquire a spinlock inside rcu_read_lock
> section.  The only issue is that the entry being modified might already
> be in process of being deleted (ie. modifying a dead route).
> 
> Probably simpler to just get rid of rwlock entirely, go with a spinlock
> for now.  Reader/writer locks are slower than spin locks and even if
> lock is highly read contended, it is not held for long.
> 
> IPV6 routing table is using much simpler algorithms on the assumption
> that IPV6 was going to solve the CIDR address explosion problem. That
> assumption will probably not hold up, and having a trie (TRASH) version
> of IPV6 routing table with RCU would be a good research project for
> some graduate student.

This is all well and good, but meanwhile someone does need to
fix the deadlock originally reported here :-)

Re: Deadlock in IPv6 code while garbage collection on the rwlock protecting the routing tree.

[Jarek Poplawski]

On 23-01-2010 11:22, David Miller wrote:
> This is all well and good, but meanwhile someone does need to
> fix the deadlock originally reported here :-)

I hope I miss something ;-) but I can't see this deadlock; the
write_lock_bh(&table->tb6_lock) is taken from a timer in this case,
not from the thread holding read_lock_bh(&table->tb6_lock).

Jarek P.

Re: Deadlock in IPv6 code while garbage collection on the rwlock protecting the routing tree.

[Jarek Poplawski]

On Tue, Jan 26, 2010 at 09:48:17AM +0000, Jarek Poplawski wrote:
> On 23-01-2010 11:22, David Miller wrote:
> > This is all well and good, but meanwhile someone does need to
> > fix the deadlock originally reported here :-)
> 
> I hope I miss something ;-) but I can't see this deadlock; the
> write_lock_bh(&table->tb6_lock) is taken from a timer in this case,
> not from the thread holding read_lock_bh(&table->tb6_lock).

I missed again! Yes, I can see this deadlock now.

Sorry,
Jarek P.

[PATCH] ipv6: Fix possible NULL dereference in icmp6_dst_alloc

[Jarek Poplawski]

While looking at the "Deadlock in IPv6 code while garbage collection
on the rwlock protecting the routing tree" reported by Srinivas
Akkipeddi I found there is possible a NULL pointer dereference in
icmp6_dst_alloc().

Signed-off-by: Jarek Poplawski <jarkao2@gmail.com>
---

 net/ipv6/route.c |    3 +--
 1 files changed, 1 insertions(+), 2 deletions(-)

diff --git a/net/ipv6/route.c b/net/ipv6/route.c
index c2bd74c..93c3b20 100644
--- a/net/ipv6/route.c
+++ b/net/ipv6/route.c
@@ -973,7 +973,7 @@ struct dst_entry *icmp6_dst_alloc(struct net_device *dev,
 	rt = ip6_dst_alloc(&net->ipv6.ip6_dst_ops);
 	if (unlikely(rt == NULL)) {
 		in6_dev_put(idev);
-		goto out;
+		return NULL;
 	}
 
 	dev_hold(dev);
@@ -1009,7 +1009,6 @@ struct dst_entry *icmp6_dst_alloc(struct net_device *dev,
 
 	fib6_force_start_gc(net);
 
-out:
 	return &rt->u.dst;
 }
 

Re: [PATCH] ipv6: Fix possible NULL dereference in icmp6_dst_alloc

[David Miller]

From: Jarek Poplawski <jarkao2@gmail.com>
Date: Wed, 27 Jan 2010 09:59:52 +0000

> While looking at the "Deadlock in IPv6 code while garbage collection
> on the rwlock protecting the routing tree" reported by Srinivas
> Akkipeddi I found there is possible a NULL pointer dereference in
> icmp6_dst_alloc().
> 
> Signed-off-by: Jarek Poplawski <jarkao2@gmail.com>

Jarek, if rt is NULL so is &rt->u.dst

That's two patches trying to fix this same non-problem in
two different places today :-)

Re: [PATCH] ipv6: Fix possible NULL dereference in icmp6_dst_alloc

[Jarek Poplawski]

On Wed, Jan 27, 2010 at 02:14:24AM -0800, David Miller wrote:
> From: Jarek Poplawski <jarkao2@gmail.com>
> Date: Wed, 27 Jan 2010 09:59:52 +0000
> 
> > While looking at the "Deadlock in IPv6 code while garbage collection
> > on the rwlock protecting the routing tree" reported by Srinivas
> > Akkipeddi I found there is possible a NULL pointer dereference in
> > icmp6_dst_alloc().
> > 
> > Signed-off-by: Jarek Poplawski <jarkao2@gmail.com>
> 
> Jarek, if rt is NULL so is &rt->u.dst
> 
> That's two patches trying to fix this same non-problem in
> two different places today :-)

Yes, great joke! :-\

(Btw, maybe it's a sign this might be more readable?)

Thanks,
Jarek P.

Re: [PATCH] ipv6: Fix possible NULL dereference in icmp6_dst_alloc

[David Miller]

From: Jarek Poplawski <jarkao2@gmail.com>
Date: Wed, 27 Jan 2010 10:34:17 +0000

> (Btw, maybe it's a sign this might be more readable?)

I welcome suggests that, tree wide, would make this harder
to misinterpret.

Re: [PATCH] ipv6: Fix possible NULL dereference in icmp6_dst_alloc

[Jarek Poplawski]

On Wed, Jan 27, 2010 at 03:04:16AM -0800, David Miller wrote:
> From: Jarek Poplawski <jarkao2@gmail.com>
> Date: Wed, 27 Jan 2010 10:34:17 +0000
> 
> > (Btw, maybe it's a sign this might be more readable?)
> 
> I welcome suggests that, tree wide, would make this harder
> to misinterpret.

If there is nothing better I still think this patch is right, except
better subject (Fix impossible NULL dereference in ... ;-).

Jarek P.

Re: [PATCH] ipv6: Fix possible NULL dereference in icmp6_dst_alloc

[David Miller]

From: Jarek Poplawski <jarkao2@gmail.com>
Date: Wed, 27 Jan 2010 12:17:46 +0000

> If there is nothing better I still think this patch is right, except
> better subject (Fix impossible NULL dereference in ... ;-).

Sorry, I'm not applying it, just like I didn't apply Krishna's similar
patch he posted earlier today.

Re: [PATCH] ipv6: Fix possible NULL dereference in icmp6_dst_alloc

[Jarek Poplawski]

On Wed, Jan 27, 2010 at 04:23:36AM -0800, David Miller wrote:
> From: Jarek Poplawski <jarkao2@gmail.com>
> Date: Wed, 27 Jan 2010 12:17:46 +0000
> 
> > If there is nothing better I still think this patch is right, except
> > better subject (Fix impossible NULL dereference in ... ;-).
> 
> Sorry, I'm not applying it, just like I didn't apply Krishna's similar
> patch he posted earlier today.

I've understood your decision and I'm OK with that; I'm only not sure
there is a better way (comments?) to make this code readable.

Jarek P. 

Re: [PATCH] ipv6: Fix possible NULL dereference in icmp6_dst_alloc

[David Miller]

From: Jarek Poplawski <jarkao2@gmail.com>
Date: Wed, 27 Jan 2010 12:43:31 +0000

> I'm only not sure there is a better way (comments?) to make this
> code readable.

You can make it more readable and even validate the invariant at the
same time by adding some kind of inline function if you wish.

static inline struct dst_entry *rtable_to_dst_entry(struct rtable *rt)
{
	BUILD_BUG_ON(rt != &rt->u.dst);

	/* Because "->u.dst" is the first member of struct rtable,
	 * this dereference is safe even when rt is NULL.
	 */
	return &rt->u.dst;
}

Something like that.

Re: [PATCH] ipv6: Fix possible NULL dereference in icmp6_dst_alloc

[Jarek Poplawski]

On Wed, Jan 27, 2010 at 05:14:10AM -0800, David Miller wrote:
> From: Jarek Poplawski <jarkao2@gmail.com>
> Date: Wed, 27 Jan 2010 12:43:31 +0000
> 
> > I'm only not sure there is a better way (comments?) to make this
> > code readable.
> 
> You can make it more readable and even validate the invariant at the
> same time by adding some kind of inline function if you wish.
> 
> static inline struct dst_entry *rtable_to_dst_entry(struct rtable *rt)
> {
> 	BUILD_BUG_ON(rt != &rt->u.dst);
> 
> 	/* Because "->u.dst" is the first member of struct rtable,
> 	 * this dereference is safe even when rt is NULL.
> 	 */
> 	return &rt->u.dst;
> }
> 
> Something like that.

Yes, it looks the most readable to me.

Thanks,
Jarek P.

Re: [PATCH] ipv6: Fix possible NULL dereference in icmp6_dst_alloc

[Atis Elsts]

> On Wed, Jan 27, 2010 at 03:04:16AM -0800, David Miller wrote:
>> From: Jarek Poplawski <jarkao2@gmail.com>
>> Date: Wed, 27 Jan 2010 10:34:17 +0000
>>
>> > (Btw, maybe it's a sign this might be more readable?)
>>
>> I welcome suggests that, tree wide, would make this harder
>> to misinterpret.

How about adding static inline functions for accessing the dst_entry
field in struct route via a cast? That way it would be immediately
obvious that invalid memory access is not going to happen. Like this:

static inline struct dst_entry *route_dst(struct rtable *rt)
{
	return (struct dst_entry *)rt;
}

static inline struct dst_entry *route6_dst(struct rt6_info *rt)
{
	return (struct dst_entry *)rt;
}

and so on...

Atis