Overhaul routing table entry cleanup by introducing a new rtexpunge

routine that takes a locked routing table reference and removes all
references to the entry in the various data structures. This
eliminates instances of recursive locking and also closes races
where the lock on the entry had to be dropped prior to calling
rtrequest(RTM_DELETE).  This also cleans up confusion where the
caller held a reference to an entry that might have been reclaimed
(and in some cases used that reference).

Supported by:	FreeBSD Foundation

8 files changed, 134 insertions, 74 deletions

diff --git a/sys/net/route.c b/sys/net/route.c
index ea98172..75fcde9 100644
--- a/sys/net/route.c
+++ b/sys/net/route.c
@@ -230,7 +230,16 @@ rtfree(struct rtentry *rt)
 	 */
 	if (--rt->rt_refcnt > 0)
 		goto done;
-	/* XXX refcount==0? */
+
+	/*
+	 * On last reference give the "close method" a chance
+	 * to cleanup private state.  This also permits (for
+	 * IPv4 and IPv6) a chance to decide if the routing table
+	 * entry should be purged immediately or at a later time.
+	 * When an immediate purge is to happen the close routine
+	 * typically calls rtexpunge which clears the RTF_UP flag
+	 * on the entry so that the code below reclaims the storage.
+	 */
 	if (rt->rt_refcnt == 0 && rnh->rnh_close)
 		rnh->rnh_close((struct radix_node *)rt, rnh);
 
@@ -524,6 +533,95 @@ rt_getifa(struct rt_addrinfo *info)
 	return (error);
 }
 
+/*
+ * Expunges references to a route that's about to be reclaimed.
+ * The route must be locked.
+ */
+int
+rtexpunge(struct rtentry *rt)
+{
+	struct radix_node *rn;
+	struct radix_node_head *rnh;
+	struct ifaddr *ifa;
+	int error = 0;
+
+	RT_LOCK_ASSERT(rt);
+#if 0
+	/*
+	 * We cannot assume anything about the reference count
+	 * because protocols call us in many situations; often
+	 * before unwinding references to the table entry.
+	 */
+	KASSERT(rt->rt_refcnt <= 1, ("bogus refcnt %ld", rt->rt_refcnt));
+#endif
+	/*
+	 * Find the correct routing tree to use for this Address Family
+	 */
+	rnh = rt_tables[rt_key(rt)->sa_family];
+	if (rnh == 0)
+		return (EAFNOSUPPORT);
+
+	RADIX_NODE_HEAD_LOCK(rnh);
+
+	/*
+	 * Remove the item from the tree; it should be there,
+	 * but when callers invoke us blindly it may not (sigh).
+	 */
+	rn = rnh->rnh_deladdr(rt_key(rt), rt_mask(rt), rnh);
+	if (rn == 0) {
+		error = ESRCH;
+		goto bad;
+	}
+	KASSERT((rn->rn_flags & (RNF_ACTIVE | RNF_ROOT)) == 0,
+		("unexpected flags 0x%x", rn->rn_flags));
+	KASSERT(rt == (struct rtentry *)rn,
+		("lookup mismatch, rt %p rn %p", rt, rn));
+
+	rt->rt_flags &= ~RTF_UP;
+
+	/*
+	 * Now search what's left of the subtree for any cloned
+	 * routes which might have been formed from this node.
+	 */
+	if ((rt->rt_flags & (RTF_CLONING | RTF_PRCLONING)) && rt_mask(rt))
+		rnh->rnh_walktree_from(rnh, rt_key(rt), rt_mask(rt),
+				       rt_fixdelete, rt);
+
+	/*
+	 * Remove any external references we may have.
+	 * This might result in another rtentry being freed if
+	 * we held its last reference.
+	 */
+	if (rt->rt_gwroute) {
+		struct rtentry *gwrt = rt->rt_gwroute;
+		RTFREE(gwrt);
+		rt->rt_gwroute = 0;
+	}
+
+	/*
+	 * Give the protocol a chance to keep things in sync.
+	 */
+	if ((ifa = rt->rt_ifa) && ifa->ifa_rtrequest) {
+		struct rt_addrinfo info;
+
+		bzero((caddr_t)&info, sizeof(info));
+		info.rti_flags = rt->rt_flags;
+		info.rti_info[RTAX_DST] = rt_key(rt);
+		info.rti_info[RTAX_GATEWAY] = rt->rt_gateway;
+		info.rti_info[RTAX_NETMASK] = rt_mask(rt);
+		ifa->ifa_rtrequest(RTM_DELETE, rt, &info);
+	}
+
+	/*
+	 * one more rtentry floating around that is not
+	 * linked to the routing table.
+	 */
+	rttrash++;
+bad:
+	RADIX_NODE_HEAD_UNLOCK(rnh);
+	return (error);
+}
+
 int
 rtrequest1(int req, struct rt_addrinfo *info, struct rtentry **ret_nrt)
 {
@@ -684,12 +782,8 @@ rtrequest1(int req, struct rt_addrinfo *info, struct rtentry **ret_nrt)
 			 */
 			rt2 = rtalloc1(dst, 0, RTF_PRCLONING);
 			if (rt2 && rt2->rt_parent) {
-				RT_UNLOCK(rt2);		/* XXX recursive lock */
-				rtrequest(RTM_DELETE,
-					  rt_key(rt2),
-					  rt2->rt_gateway,
-					  rt_mask(rt2), rt2->rt_flags, 0);
-				RTFREE(rt2);
+				rtexpunge(rt2);
+				RT_UNLOCK(rt2);
 				rn = rnh->rnh_addaddr(ndst, netmask,
 						      rnh, rt->rt_nodes);
 			} else if (rt2) {
@@ -936,8 +1030,7 @@ rt_setgate(struct rtentry *rt, struct sockaddr *dst, struct sockaddr *gate)
 		 * or a routing redirect, so try to delete it.
 		 */
 		if (rt_key(rt))
-			rtrequest(RTM_DELETE, rt_key(rt),
-			    rt->rt_gateway, rt_mask(rt), rt->rt_flags, 0);
+			rtexpunge(rt);
 		return EADDRNOTAVAIL;
 	}
 
@@ -995,6 +1088,7 @@ rt_setgate(struct rtentry *rt, struct sockaddr *dst, struct sockaddr *gate)
 	 * This is obviously mandatory when we get rt->rt_output().
 	 */
 	if (rt->rt_flags & RTF_GATEWAY) {
+		/* XXX LOR here */
 		rt->rt_gwroute = rtalloc1(gate, 1, RTF_PRCLONING);
 		if (rt->rt_gwroute == rt) {
 			RTFREE_LOCKED(rt->rt_gwroute);
@@ -1015,6 +1109,7 @@ rt_setgate(struct rtentry *rt, struct sockaddr *dst, struct sockaddr *gate)
 
 		arg.rnh = rnh;
 		arg.rt0 = rt;
+		/* XXX LOR here */
 		RADIX_NODE_HEAD_LOCK(rnh);
 		rnh->rnh_walktree_from(rnh, rt_key(rt), rt_mask(rt),
 				       rt_fixchange, &arg);
diff --git a/sys/net/route.h b/sys/net/route.h
index bec78bd..2c60780 100644
--- a/sys/net/route.h
+++ b/sys/net/route.h
@@ -297,6 +297,7 @@ int	 rt_setgate(struct rtentry *, struct sockaddr *, struct sockaddr *);
 void	 rtalloc_ign(struct route *, u_long);
 /* NB: the rtentry is returned locked */
 struct rtentry *rtalloc1(struct sockaddr *, int, u_long);
+int	 rtexpunge(struct rtentry *);
 void	 rtfree(struct rtentry *);
 int	 rtinit(struct ifaddr *, int, int);
 int	 rtioctl(u_long, caddr_t);
diff --git a/sys/netinet/if_ether.c b/sys/netinet/if_ether.c
index 4cc1d4e..d5916ba 100644
--- a/sys/netinet/if_ether.c
+++ b/sys/netinet/if_ether.c
@@ -949,14 +949,9 @@ arplookup(addr, create, proxy)
 		 * arplookup() is creating the route, then purge
 		 * it from the routing table as it is probably bogus.
 		 */
-		RT_UNLOCK(rt);
-		if (rt->rt_refcnt == 1 && ISDYNCLONE(rt)) {
-			rtrequest(RTM_DELETE,
-					(struct sockaddr *)rt_key(rt),
-					rt->rt_gateway, rt_mask(rt),
-					rt->rt_flags, 0);
-		}
-		RTFREE(rt);
+		if (rt->rt_refcnt == 1 && ISDYNCLONE(rt))
+			rtexpunge(rt);
+		RTFREE_LOCKED(rt);
 		return (0);
 #undef ISDYNCLONE
 	} else {
diff --git a/sys/netinet/in_pcb.c b/sys/netinet/in_pcb.c
index e094c8c..a1490c4 100644
--- a/sys/netinet/in_pcb.c
+++ b/sys/netinet/in_pcb.c
@@ -871,11 +871,9 @@ in_losing(inp)
 		info.rti_info[RTAX_GATEWAY] = rt->rt_gateway;
 		info.rti_info[RTAX_NETMASK] = rt_mask(rt);
 		rt_missmsg(RTM_LOSING, &info, rt->rt_flags, 0);
-		if (rt->rt_flags & RTF_DYNAMIC) {
-			RT_UNLOCK(rt);		/* XXX refcnt? */
-			(void) rtrequest1(RTM_DELETE, &info, NULL);
-		} else
-			rtfree(rt);
+		if (rt->rt_flags & RTF_DYNAMIC)
+			rtexpunge(rt);
+		RTFREE_LOCKED(rt);
 		/*
 		 * A new route can be allocated
 		 * the next time output is attempted.
diff --git a/sys/netinet/in_rmx.c b/sys/netinet/in_rmx.c
index baa8c71..39f5eed 100644
--- a/sys/netinet/in_rmx.c
+++ b/sys/netinet/in_rmx.c
@@ -125,17 +125,12 @@ in_addroute(void *v_arg, void *n_arg, struct radix_node_head *head,
 			    rt2->rt_flags & RTF_HOST &&
 			    rt2->rt_gateway &&
 			    rt2->rt_gateway->sa_family == AF_LINK) {
-				/* NB: must unlock to avoid recursion */
-				RT_UNLOCK(rt2);
-				rtrequest(RTM_DELETE,
-					  (struct sockaddr *)rt_key(rt2),
-					  rt2->rt_gateway, rt_mask(rt2),
-					  rt2->rt_flags, 0);
+				rtexpunge(rt2);
+				RTFREE_LOCKED(rt2);
 				ret = rn_addroute(v_arg, n_arg, head,
 						  treenodes);
-				RT_LOCK(rt2);
-			}
-			RTFREE_LOCKED(rt2);
+			} else
+				RTFREE_LOCKED(rt2);
 		}
 	}
 
@@ -211,13 +206,7 @@ in_clsroute(struct radix_node *rn, struct radix_node_head *head)
 		rt->rt_flags |= RTPRF_OURS;
 		rt->rt_rmx.rmx_expire = time_second + rtq_reallyold;
 	} else {
-		/* NB: must unlock to avoid recursion */
-		RT_UNLOCK(rt);
-		rtrequest(RTM_DELETE,
-			  (struct sockaddr *)rt_key(rt),
-			  rt->rt_gateway, rt_mask(rt),
-			  rt->rt_flags, 0);
-		RT_LOCK(rt);
+		rtexpunge(rt);
 	}
 }
 
@@ -385,8 +374,8 @@ in_ifadownkill(struct radix_node *rn, void *xap)
 {
 	struct in_ifadown_arg *ap = xap;
 	struct rtentry *rt = (struct rtentry *)rn;
-	int err;
 
+	RT_LOCK(rt);
 	if (rt->rt_ifa == ap->ifa &&
 	    (ap->del || !(rt->rt_flags & RTF_STATIC))) {
 		/*
@@ -397,15 +386,11 @@ in_ifadownkill(struct radix_node *rn, void *xap)
 		 * the routes that rtrequest() would have in any case,
 		 * so that behavior is not needed there.
 		 */
-		RT_LOCK(rt);
 		rt->rt_flags &= ~(RTF_CLONING | RTF_PRCLONING);
+		rtexpunge(rt);
+		RTFREE_LOCKED(rt);
+	} else
 		RT_UNLOCK(rt);
-		err = rtrequest(RTM_DELETE, (struct sockaddr *)rt_key(rt),
-				rt->rt_gateway, rt_mask(rt), rt->rt_flags, 0);
-		if (err) {
-			log(LOG_WARNING, "in_ifadownkill: error %d\n", err);
-		}
-	}
 	return 0;
 }
 
diff --git a/sys/netinet6/in6_ifattach.c b/sys/netinet6/in6_ifattach.c
index 7e6f4c7..76de24d 100644
--- a/sys/netinet6/in6_ifattach.c
+++ b/sys/netinet6/in6_ifattach.c
@@ -904,16 +904,15 @@ in6_ifdetach(ifp)
 	sin6.sin6_family = AF_INET6;
 	sin6.sin6_addr = in6addr_linklocal_allnodes;
 	sin6.sin6_addr.s6_addr16[1] = htons(ifp->if_index);
+	/* XXX grab lock first to avoid LOR */
+	RADIX_NODE_HEAD_LOCK(rt_tables[AF_INET6]);
 	rt = rtalloc1((struct sockaddr *)&sin6, 0, 0UL);
 	if (rt) {
-		if (rt->rt_ifp == ifp) {
-			RT_UNLOCK(rt);
-			rtrequest(RTM_DELETE, (struct sockaddr *)rt_key(rt),
-			    rt->rt_gateway, rt_mask(rt), rt->rt_flags, 0);
-			RTFREE(rt);
-		} else
-			rtfree(rt);
+		if (rt->rt_ifp == ifp)
+			rtexpunge(rt);
+		RTFREE_LOCKED(rt);
 	}
+	RADIX_NODE_HEAD_UNLOCK(rt_tables[AF_INET6]);
 }
 
 void
diff --git a/sys/netinet6/in6_pcb.c b/sys/netinet6/in6_pcb.c
index eb62328..5c7f1f2 100644
--- a/sys/netinet6/in6_pcb.c
+++ b/sys/netinet6/in6_pcb.c
@@ -842,11 +842,9 @@ in6_losing(in6p)
 		info.rti_info[RTAX_GATEWAY] = rt->rt_gateway;
 		info.rti_info[RTAX_NETMASK] = rt_mask(rt);
 		rt_missmsg(RTM_LOSING, &info, rt->rt_flags, 0);
-		if (rt->rt_flags & RTF_DYNAMIC) {
-			RT_UNLOCK(rt);		/* XXX refcnt? */
-			(void)rtrequest1(RTM_DELETE, &info, NULL);
-		} else
-			rtfree(rt);
+		if (rt->rt_flags & RTF_DYNAMIC)
+			rtexpunge(rt);
+		RTFREE_LOCKED(rt);
 		/*
 		 * A new route can be allocated
 		 * the next time output is attempted.
diff --git a/sys/netinet6/in6_rmx.c b/sys/netinet6/in6_rmx.c
index 2853fe8..3384da0 100644
--- a/sys/netinet6/in6_rmx.c
+++ b/sys/netinet6/in6_rmx.c
@@ -167,17 +167,12 @@ in6_addroute(void *v_arg, void *n_arg, struct radix_node_head *head,
 				rt2->rt_flags & RTF_HOST &&
 				rt2->rt_gateway &&
 				rt2->rt_gateway->sa_family == AF_LINK) {
-				/* NB: must unlock to avoid recursion */
-				RT_UNLOCK(rt2);
-				rtrequest(RTM_DELETE,
-					  (struct sockaddr *)rt_key(rt2),
-					  rt2->rt_gateway,
-					  rt_mask(rt2), rt2->rt_flags, 0);
+				rtexpunge(rt2);
+				RTFREE_LOCKED(rt2);
 				ret = rn_addroute(v_arg, n_arg, head,
 					treenodes);
-				RT_LOCK(rt2);
-			}
-			RTFREE_LOCKED(rt2);
+			} else
+				RTFREE_LOCKED(rt2);
 		}
 	} else if (ret == NULL && rt->rt_flags & RTF_CLONING) {
 		struct rtentry *rt2;
@@ -276,13 +271,7 @@ in6_clsroute(struct radix_node *rn, struct radix_node_head *head)
 		rt->rt_flags |= RTPRF_OURS;
 		rt->rt_rmx.rmx_expire = time_second + rtq_reallyold;
 	} else {
-		/* NB: must unlock to avoid recursion */
-		RT_UNLOCK(rt);
-		rtrequest(RTM_DELETE,
-			  (struct sockaddr *)rt_key(rt),
-			  rt->rt_gateway, rt_mask(rt),
-			  rt->rt_flags, 0);
-		RT_LOCK(rt);
+		rtexpunge(rt);
 	}
 }