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

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 [email protected] -- and destroy all copies of this message and any attachments without reading or disclosing their contents. Thank you.

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

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.

From: Stephen Hemminger <[email protected]>
Date: Wed, 23 Dec 2009 10:13:09 -0800

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.

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

Sorry,
Jarek P.

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().

---

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

index c2bd74c..93c3b20 100644
@@ -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;
 }
 

From: Jarek Poplawski <[email protected]>
Date: Wed, 27 Jan 2010 09:59:52 +0000

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.

From: Jarek Poplawski <[email protected]>
Date: Wed, 27 Jan 2010 10:34:17 +0000

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.

From: Jarek Poplawski <[email protected]>
Date: Wed, 27 Jan 2010 12:17:46 +0000

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.

From: Jarek Poplawski <[email protected]>
Date: Wed, 27 Jan 2010 12:43:31 +0000

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.

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