Locking for updates to routing table entries. Each rtentry gets a mutex

that covers updates to the contents.  Note this is separate from holding
a reference and/or locking the routing table itself.

Other/related changes:

o rtredirect loses the final parameter by which an rtentry reference
  may be returned; this was never used and added unwarranted complexity
  for locking.
o minor style cleanups to routing code (e.g. ansi-fy function decls)
o remove the logic to bump the refcnt on the parent of cloned routes,
  we assume the parent will remain as long as the clone; doing this avoids
  a circularity in locking during delete
o convert some timeouts to MPSAFE callouts

Notes:

1. rt_mtx in struct rtentry is guarded by #ifdef _KERNEL as user-level
   applications cannot/do-no know about mutex's.  Doing this requires
   that the mutex be the last element in the structure.  A better solution
   is to introduce an externalized version of struct rtentry but this is
   a major task because of the intertwining of rtentry and other data
   structures that are visible to user applications.
2. There are known LOR's that are expected to go away with forthcoming
   work to eliminate many held references.  If not these will be resolved
   prior to release.
3. ATM changes are untested.

Sponsored by:	FreeBSD Foundation
Obtained from:	BSD/OS (partly)

1 files changed, 203 insertions, 170 deletions

diff --git a/sys/net/route.c b/sys/net/route.c
index 675e0ee..a09fdf4 100644
--- a/sys/net/route.c
+++ b/sys/net/route.c
@@ -63,8 +63,7 @@ static void rt_maskedcopy(struct sockaddr *,
 static void rtable_init(void **);
 
 static void
-rtable_init(table)
-	void **table;
+rtable_init(void **table)
 {
 	struct domain *dom;
 	for (dom = domains; dom; dom = dom->dom_next)
@@ -84,50 +83,45 @@ route_init()
  * Packet routing routines.
  */
 void
-rtalloc(ro)
-	register struct route *ro;
+rtalloc(struct route *ro)
 {
 	rtalloc_ign(ro, 0UL);
 }
 
 void
-rtalloc_ign(ro, ignore)
-	register struct route *ro;
-	u_long ignore;
+rtalloc_ign(struct route *ro, u_long ignore)
 {
 	struct rtentry *rt;
-	int s;
 
 	if ((rt = ro->ro_rt) != NULL) {
 		if (rt->rt_ifp != NULL && rt->rt_flags & RTF_UP)
 			return;
-		/* XXX - We are probably always at splnet here already. */
-		s = splnet();
 		RTFREE(rt);
 		ro->ro_rt = NULL;
-		splx(s);
 	}
 	ro->ro_rt = rtalloc1(&ro->ro_dst, 1, ignore);
+	if (ro->ro_rt)
+		RT_UNLOCK(ro->ro_rt);
 }
 
 /*
  * Look up the route that matches the address given
  * Or, at least try.. Create a cloned route if needed.
+ *
+ * The returned route, if any, is locked.
  */
 struct rtentry *
-rtalloc1(dst, report, ignflags)
-	register struct sockaddr *dst;
-	int report;
-	u_long ignflags;
+rtalloc1(struct sockaddr *dst, int report, u_long ignflags)
 {
-	register struct radix_node_head *rnh = rt_tables[dst->sa_family];
-	register struct rtentry *rt;
-	register struct radix_node *rn;
-	struct rtentry *newrt = 0;
+	struct radix_node_head *rnh = rt_tables[dst->sa_family];
+	struct rtentry *rt;
+	struct radix_node *rn;
+	struct rtentry *newrt;
 	struct rt_addrinfo info;
 	u_long nflags;
-	int  s = splnet(), err = 0, msgtype = RTM_MISS;
+	int err = 0, msgtype = RTM_MISS;
 
+	newrt = 0;
 	/*
 	 * Look up the address in the table for that Address Family
 	 */
@@ -135,9 +129,10 @@ rtalloc1(dst, report, ignflags)
 		rtstat.rts_unreach++;
 		goto miss2;
 	}
+	bzero(&info, sizeof(info));
 	RADIX_NODE_HEAD_LOCK(rnh);
-	if ((rn = rnh->rnh_matchaddr((caddr_t)dst, rnh)) &&
-	    ((rn->rn_flags & RNF_ROOT) == 0)) {
+	if ((rn = rnh->rnh_matchaddr(dst, rnh)) &&
+	    (rn->rn_flags & RNF_ROOT) == 0) {
 		/*
 		 * If we find it and it's not the root node, then
 		 * get a refernce on the rtentry associated.
@@ -157,11 +152,14 @@ rtalloc1(dst, report, ignflags)
 				 * If the cloning didn't succeed, maybe
 				 * what we have will do. Return that.
 				 */
-				newrt = rt;
-				rt->rt_refcnt++;
+				newrt = rt;		/* existing route */
+				RT_LOCK(newrt);
+				newrt->rt_refcnt++;
 				goto miss;
 			}
-			if ((rt = newrt) && (rt->rt_flags & RTF_XRESOLVE)) {
+			KASSERT(newrt, ("no route and no error"));
+			RT_LOCK(newrt);
+			if (newrt->rt_flags & RTF_XRESOLVE) {
 				/*
 				 * If the new route specifies it be
 				 * externally resolved, then go do that.
@@ -170,18 +168,20 @@ rtalloc1(dst, report, ignflags)
 				goto miss;
 			}
 			/* Inform listeners of the new route. */
-			bzero(&info, sizeof(info));
-			info.rti_info[RTAX_DST] = rt_key(rt);
-			info.rti_info[RTAX_NETMASK] = rt_mask(rt);
-			info.rti_info[RTAX_GATEWAY] = rt->rt_gateway;
-			if (rt->rt_ifp != NULL) {
+			info.rti_info[RTAX_DST] = rt_key(newrt);
+			info.rti_info[RTAX_NETMASK] = rt_mask(newrt);
+			info.rti_info[RTAX_GATEWAY] = newrt->rt_gateway;
+			if (newrt->rt_ifp != NULL) {
 				info.rti_info[RTAX_IFP] =
-				    TAILQ_FIRST(&rt->rt_ifp->if_addrhead)->ifa_addr;
-				info.rti_info[RTAX_IFA] = rt->rt_ifa->ifa_addr;
+				    TAILQ_FIRST(&newrt->rt_ifp->if_addrhead)->ifa_addr;
+				info.rti_info[RTAX_IFA] = newrt->rt_ifa->ifa_addr;
 			}
-			rt_missmsg(RTM_ADD, &info, rt->rt_flags, 0);
-		} else
-			rt->rt_refcnt++;
+			rt_missmsg(RTM_ADD, &info, newrt->rt_flags, 0);
+		} else {
+			KASSERT(rt == newrt, ("locking wrong route"));
+			RT_LOCK(newrt);
+			newrt->rt_refcnt++;
+		}
 		RADIX_NODE_HEAD_UNLOCK(rnh);
 	} else {
 		/*
@@ -198,12 +198,12 @@ rtalloc1(dst, report, ignflags)
 			 * Authorities.
 			 * For a delete, this is not an error. (report == 0)
 			 */
-			bzero((caddr_t)&info, sizeof(info));
 			info.rti_info[RTAX_DST] = dst;
 			rt_missmsg(msgtype, &info, 0, err);
 		}
 	}
-	splx(s);
+	if (newrt)
+		RT_LOCK_ASSERT(newrt);
 	return (newrt);
 }
 
@@ -212,8 +212,7 @@ rtalloc1(dst, report, ignflags)
  * If the count gets low enough, take it out of the routing table
  */
 void
-rtfree(rt)
-	register struct rtentry *rt;
+rtfree(struct rtentry *rt)
 {
 	/*
 	 * find the tree for that address family
@@ -223,21 +222,24 @@ rtfree(rt)
 	if (rt == 0 || rnh == 0)
 		panic("rtfree");
 
+	RT_LOCK_ASSERT(rt);
+
 	/*
 	 * decrement the reference count by one and if it reaches 0,
 	 * and there is a close function defined, call the close function
 	 */
-	rt->rt_refcnt--;
-	if (rnh->rnh_close && rt->rt_refcnt == 0) {
+	if (--rt->rt_refcnt > 0)
+		goto done;
+	/* XXX refcount==0? */
+	if (rt->rt_refcnt == 0 && rnh->rnh_close)
 		rnh->rnh_close((struct radix_node *)rt, rnh);
-	}
 
 	/*
 	 * If we are no longer "up" (and ref == 0)
 	 * then we can free the resources associated
 	 * with the route.
 	 */
-	if (rt->rt_refcnt <= 0 && (rt->rt_flags & RTF_UP) == 0) {
+	if ((rt->rt_flags & RTF_UP) == 0) {
 		if (rt->rt_nodes->rn_flags & (RNF_ACTIVE | RNF_ROOT))
 			panic ("rtfree 2");
 		/*
@@ -245,22 +247,19 @@ rtfree(rt)
 		 * so it is represented in rttrash.. remove that now.
 		 */
 		rttrash--;
-
 #ifdef	DIAGNOSTIC
 		if (rt->rt_refcnt < 0) {
 			printf("rtfree: %p not freed (neg refs)\n", rt);
-			return;
+			goto done;
 		}
 #endif
-
 		/*
 		 * release references on items we hold them on..
 		 * e.g other routes and ifaddrs.
 		 */
 		if (rt->rt_ifa)
 			IFAFREE(rt->rt_ifa);
-		if (rt->rt_parent)
-			RTFREE(rt->rt_parent);
+		rt->rt_parent = NULL;		/* NB: no refcnt on parent */
 
 		/*
 		 * The key is separatly alloc'd so free it (see rt_setgate()).
@@ -272,8 +271,12 @@ rtfree(rt)
 		/*
 		 * and the rtentry itself of course
 		 */
+		RT_LOCK_DESTROY(rt);
 		Free(rt);
+		return;
 	}
+done:
+	RT_UNLOCK(rt);
 }
 
 /* compare two sockaddr structures */
@@ -284,15 +287,13 @@ rtfree(rt)
  * destination to go through the given gateway.
  * Normally called as a result of a routing redirect
  * message from the network layer.
- *
- * N.B.: must be called at splnet
- *
  */
 void
-rtredirect(dst, gateway, netmask, flags, src, rtp)
-	struct sockaddr *dst, *gateway, *netmask, *src;
-	int flags;
-	struct rtentry **rtp;
+rtredirect(struct sockaddr *dst,
+	struct sockaddr *gateway,
+	struct sockaddr *netmask,
+	int flags,
+	struct sockaddr *src)
 {
 	struct rtentry *rt;
 	int error = 0;
@@ -305,7 +306,7 @@ rtredirect(dst, gateway, netmask, flags, src, rtp)
 		error = ENETUNREACH;
 		goto out;
 	}
-	rt = rtalloc1(dst, 0, 0UL);
+	rt = rtalloc1(dst, 0, 0UL);	/* NB: rt is locked */
 	/*
 	 * If the redirect isn't from our current router for this dst,
 	 * it's either old or wrong.  If it redirects us to ourselves,
@@ -325,7 +326,7 @@ rtredirect(dst, gateway, netmask, flags, src, rtp)
 	 * which use routing redirects generated by smart gateways
 	 * to dynamically build the routing tables.
 	 */
-	if ((rt == 0) || (rt_mask(rt) && rt_mask(rt)->sa_len < 2))
+	if (rt == 0 || (rt_mask(rt) && rt_mask(rt)->sa_len < 2))
 		goto create;
 	/*
 	 * Don't listen to the redirect if it's
@@ -349,8 +350,10 @@ rtredirect(dst, gateway, netmask, flags, src, rtp)
 			info.rti_flags = flags;
 			rt = NULL;
 			error = rtrequest1(RTM_ADD, &info, &rt);
-			if (rt != NULL)
+			if (rt != NULL) {
+				RT_UNLOCK(rt);
 				flags = rt->rt_flags;
+			}
 			stat = &rtstat.rts_dynamic;
 		} else {
 			/*
@@ -368,12 +371,8 @@ rtredirect(dst, gateway, netmask, flags, src, rtp)
 	} else
 		error = EHOSTUNREACH;
 done:
-	if (rt) {
-		if (rtp && !error)
-			*rtp = rt;
-		else
-			rtfree(rt);
-	}
+	if (rt)
+		rtfree(rt);
 out:
 	if (error)
 		rtstat.rts_badredirect++;
@@ -391,9 +390,7 @@ out:
  * Routing table ioctl interface.
  */
 int
-rtioctl(req, data)
-	u_long req;
-	caddr_t data;
+rtioctl(u_long req, caddr_t data)
 {
 #ifdef INET
 	/* Multicast goop, grrr... */
@@ -404,11 +401,10 @@ rtioctl(req, data)
 }
 
 struct ifaddr *
-ifa_ifwithroute(flags, dst, gateway)
-	int flags;
-	struct sockaddr	*dst, *gateway;
+ifa_ifwithroute(int flags, struct sockaddr *dst, struct sockaddr *gateway)
 {
 	register struct ifaddr *ifa;
+
 	if ((flags & RTF_GATEWAY) == 0) {
 		/*
 		 * If we are adding a route to an interface,
@@ -438,6 +434,7 @@ ifa_ifwithroute(flags, dst, gateway)
 		if (rt == 0)
 			return (0);
 		--rt->rt_refcnt;
+		RT_UNLOCK(rt);
 		if ((ifa = rt->rt_ifa) == 0)
 			return (0);
 	}
@@ -463,10 +460,12 @@ struct rtfc_arg {
  * all the bits of info needed
  */
 int
-rtrequest(req, dst, gateway, netmask, flags, ret_nrt)
-	int req, flags;
-	struct sockaddr *dst, *gateway, *netmask;
-	struct rtentry **ret_nrt;
+rtrequest(int req,
+	struct sockaddr *dst,
+	struct sockaddr *gateway,
+	struct sockaddr *netmask,
+	int flags,
+	struct rtentry **ret_nrt)
 {
 	struct rt_addrinfo info;
 
@@ -490,8 +489,7 @@ rtrequest(req, dst, gateway, netmask, flags, ret_nrt)
 #define	flags	info->rti_flags
 
 int
-rt_getifa(info)
-	struct rt_addrinfo *info;
+rt_getifa(struct rt_addrinfo *info)
 {
 	struct ifaddr *ifa;
 	int error = 0;
@@ -527,12 +525,9 @@ rt_getifa(info)
 }
 
 int
-rtrequest1(req, info, ret_nrt)
-	int req;
-	struct rt_addrinfo *info;
-	struct rtentry **ret_nrt;
+rtrequest1(int req, struct rt_addrinfo *info, struct rtentry **ret_nrt)
 {
-	int s = splnet(); int error = 0;
+	int error = 0;
 	register struct rtentry *rt;
 	register struct radix_node *rn;
 	register struct radix_node_head *rnh;
@@ -543,10 +538,9 @@ rtrequest1(req, info, ret_nrt)
 	/*
 	 * Find the correct routing tree to use for this Address Family
 	 */
-	if ((rnh = rt_tables[dst->sa_family]) == 0) {
-		splx(s);
+	rnh = rt_tables[dst->sa_family];
+	if (rnh == 0)
 		return (EAFNOSUPPORT);
-	}
 	RADIX_NODE_HEAD_LOCK(rnh);
 	/*
 	 * If we are adding a host route then we don't want to put
@@ -562,11 +556,13 @@ rtrequest1(req, info, ret_nrt)
 		 * Remove the item from the tree and return it.
 		 * Complain if it is not there and do no more processing.
 		 */
-		if ((rn = rnh->rnh_deladdr(dst, netmask, rnh)) == 0)
+		rn = rnh->rnh_deladdr(dst, netmask, rnh);
+		if (rn == 0)
 			senderr(ESRCH);
 		if (rn->rn_flags & (RNF_ACTIVE | RNF_ROOT))
 			panic ("rtrequest delete");
 		rt = (struct rtentry *)rn;
+		RT_LOCK(rt);
 		rt->rt_refcnt++;
 		rt->rt_flags &= ~RTF_UP;
 
@@ -586,9 +582,9 @@ rtrequest1(req, info, ret_nrt)
 		 * we held its last reference.
 		 */
 		if (rt->rt_gwroute) {
-			rt = rt->rt_gwroute;
-			RTFREE(rt);
-			(rt = (struct rtentry *)rn)->rt_gwroute = 0;
+			struct rtentry *gwrt = rt->rt_gwroute;
+			RTFREE(gwrt);
+			rt->rt_gwroute = 0;
 		}
 
 		/*
@@ -608,16 +604,18 @@ rtrequest1(req, info, ret_nrt)
 		 * but it's up to it to free the rtentry as we won't be
 		 * doing it.
 		 */
-		if (ret_nrt)
+		if (ret_nrt) {
 			*ret_nrt = rt;
-		else
-			RTFREE(rt);
+			RT_UNLOCK(rt);
+		} else
+			RTFREE_LOCKED(rt);
 		break;
 
 	case RTM_RESOLVE:
 		if (ret_nrt == 0 || (rt = *ret_nrt) == 0)
 			senderr(EINVAL);
 		ifa = rt->rt_ifa;
+		/* XXX locking? */
 		flags = rt->rt_flags &
 		    ~(RTF_CLONING | RTF_PRCLONING | RTF_STATIC);
 		flags |= RTF_WASCLONED;
@@ -635,16 +633,18 @@ rtrequest1(req, info, ret_nrt)
 		ifa = info->rti_ifa;
 
 	makeroute:
-		R_Malloc(rt, struct rtentry *, sizeof(*rt));
+		R_Zalloc(rt, struct rtentry *, sizeof(*rt));
 		if (rt == 0)
 			senderr(ENOBUFS);
-		Bzero(rt, sizeof(*rt));
+		RT_LOCK_INIT(rt);
 		rt->rt_flags = RTF_UP | flags;
 		/*
 		 * Add the gateway. Possibly re-malloc-ing the storage for it
 		 * also add the rt_gwroute if possible.
 		 */
+		RT_LOCK(rt);
 		if ((error = rt_setgate(rt, dst, gateway)) != 0) {
+			RT_LOCK_DESTROY(rt);
 			Free(rt);
 			senderr(error);
 		}
@@ -652,7 +652,7 @@ rtrequest1(req, info, ret_nrt)
 		/*
 		 * point to the (possibly newly malloc'd) dest address.
 		 */
-		ndst = rt_key(rt);
+		ndst = (struct sockaddr *)rt_key(rt);
 
 		/*
 		 * make sure it contains the value we want (masked if needed).
@@ -670,10 +670,9 @@ rtrequest1(req, info, ret_nrt)
 		IFAREF(ifa);
 		rt->rt_ifa = ifa;
 		rt->rt_ifp = ifa->ifa_ifp;
-		/* XXX mtu manipulation will be done in rnh_addaddr -- itojun */
 
-		rn = rnh->rnh_addaddr((caddr_t)ndst, (caddr_t)netmask,
-					rnh, rt->rt_nodes);
+		/* XXX mtu manipulation will be done in rnh_addaddr -- itojun */
+		rn = rnh->rnh_addaddr(ndst, netmask, rnh, rt->rt_nodes);
 		if (rn == 0) {
 			struct rtentry *rt2;
 			/*
@@ -686,16 +685,15 @@ rtrequest1(req, info, ret_nrt)
 			rt2 = rtalloc1(dst, 0, RTF_PRCLONING);
 			if (rt2 && rt2->rt_parent) {
 				rtrequest(RTM_DELETE,
-					  (struct sockaddr *)rt_key(rt2),
+					  rt_key(rt2),
 					  rt2->rt_gateway,
 					  rt_mask(rt2), rt2->rt_flags, 0);
-				RTFREE(rt2);
-				rn = rnh->rnh_addaddr((caddr_t)ndst,
-						      (caddr_t)netmask,
+				RTFREE_LOCKED(rt2);
+				rn = rnh->rnh_addaddr(ndst, netmask,
 						      rnh, rt->rt_nodes);
 			} else if (rt2) {
 				/* undo the extra ref we got */
-				RTFREE(rt2);
+				RTFREE_LOCKED(rt2);
 			}
 		}
 
@@ -705,11 +703,11 @@ rtrequest1(req, info, ret_nrt)
 		 */
 		if (rn == 0) {
 			if (rt->rt_gwroute)
-				rtfree(rt->rt_gwroute);
-			if (rt->rt_ifa) {
+				RTFREE(rt->rt_gwroute);
+			if (rt->rt_ifa)
 				IFAFREE(rt->rt_ifa);
-			}
 			Free(rt_key(rt));
+			RT_LOCK_DESTROY(rt);
 			Free(rt);
 			senderr(EEXIST);
 		}
@@ -722,11 +720,22 @@ rtrequest1(req, info, ret_nrt)
 		 * are a clone (and increment the parent's references)
 		 */
 		if (req == RTM_RESOLVE) {
+			KASSERT(ret_nrt && *ret_nrt,
+				("no route to clone from"));
 			rt->rt_rmx = (*ret_nrt)->rt_rmx; /* copy metrics */
 			rt->rt_rmx.rmx_pksent = 0; /* reset packet counter */
 			if ((*ret_nrt)->rt_flags & (RTF_CLONING | RTF_PRCLONING)) {
-				rt->rt_parent = (*ret_nrt);
-				(*ret_nrt)->rt_refcnt++;
+				/*
+				 * NB: We do not bump the refcnt on the parent
+				 * entry under the assumption that it will
+				 * remain so long as we do.  This is
+				 * important when deleting the parent route
+				 * as this operation requires traversing
+				 * the tree to delete all clones and futzing
+				 * with refcnts requires us to double-lock
+				 * parent through this back reference.
+				 */
+				rt->rt_parent = *ret_nrt;
 			}
 		}
 
@@ -759,21 +768,23 @@ rtrequest1(req, info, ret_nrt)
 			*ret_nrt = rt;
 			rt->rt_refcnt++;
 		}
+		RT_UNLOCK(rt);
 		break;
 	default:
 		error = EOPNOTSUPP;
 	}
 bad:
 	RADIX_NODE_HEAD_UNLOCK(rnh);
-	splx(s);
 	return (error);
+#undef senderr
+}
+
 #undef dst
 #undef gateway
 #undef netmask
 #undef ifaaddr
 #undef ifpaddr
 #undef flags
-}
 
 /*
  * Called from rtrequest(RTM_DELETE, ...) to fix up the route's ``family''
@@ -783,9 +794,7 @@ bad:
  * the late parent (passed in as VP here) are themselves deleted.
  */
 static int
-rt_fixdelete(rn, vp)
-	struct radix_node *rn;
-	void *vp;
+rt_fixdelete(struct radix_node *rn, void *vp)
 {
 	struct rtentry *rt = (struct rtentry *)rn;
 	struct rtentry *rt0 = vp;
@@ -817,9 +826,7 @@ static int rtfcdebug = 0;
 #endif
 
 static int
-rt_fixchange(rn, vp)
-	struct radix_node *rn;
-	void *vp;
+rt_fixchange(struct radix_node *rn, void *vp)
 {
 	struct rtentry *rt = (struct rtentry *)rn;
 	struct rtfc_arg *ap = vp;
@@ -854,8 +861,7 @@ rt_fixchange(rn, vp)
 	 * There probably is a function somewhere which does this...
 	 * if not, there should be.
 	 */
-	len = imin(((struct sockaddr *)rt_key(rt0))->sa_len,
-		   ((struct sockaddr *)rt_key(rt))->sa_len);
+	len = imin(rt_key(rt0)->sa_len, rt_key(rt)->sa_len);
 
 	xk1 = (u_char *)rt_key(rt0);
 	xm1 = (u_char *)rt_mask(rt0);
@@ -863,8 +869,8 @@ rt_fixchange(rn, vp)
 
 	/* avoid applying a less specific route */
 	xmp = (u_char *)rt_mask(rt->rt_parent);
-	mlen = ((struct sockaddr *)rt_key(rt->rt_parent))->sa_len;
-	if (mlen > ((struct sockaddr *)rt_key(rt0))->sa_len) {
+	mlen = rt_key(rt->rt_parent)->sa_len;
+	if (mlen > rt_key(rt0)->sa_len) {
 #ifdef DEBUG
 		if (rtfcdebug)
 			printf("rt_fixchange: inserting a less "
@@ -906,31 +912,31 @@ rt_fixchange(rn, vp)
 #define ROUNDUP(a) (a>0 ? (1 + (((a) - 1) | (sizeof(long) - 1))) : sizeof(long))
 
 int
-rt_setgate(rt0, dst, gate)
-	struct rtentry *rt0;
-	struct sockaddr *dst, *gate;
+rt_setgate(struct rtentry *rt, struct sockaddr *dst, struct sockaddr *gate)
 {
+	/* XXX dst may be overwritten, can we move this to below */
+	struct radix_node_head *rnh = rt_tables[dst->sa_family];
 	caddr_t new, old;
 	int dlen = ROUNDUP(dst->sa_len), glen = ROUNDUP(gate->sa_len);
-	register struct rtentry *rt = rt0;
-	struct radix_node_head *rnh = rt_tables[dst->sa_family];
+
+	RT_LOCK_ASSERT(rt);
 
 	/*
 	 * A host route with the destination equal to the gateway
 	 * will interfere with keeping LLINFO in the routing
 	 * table, so disallow it.
 	 */
-	if (((rt0->rt_flags & (RTF_HOST|RTF_GATEWAY|RTF_LLINFO)) ==
+	if (((rt->rt_flags & (RTF_HOST|RTF_GATEWAY|RTF_LLINFO)) ==
 					(RTF_HOST|RTF_GATEWAY)) &&
-	    (dst->sa_len == gate->sa_len) &&
-	    (bcmp(dst, gate, dst->sa_len) == 0)) {
+	    dst->sa_len == gate->sa_len &&
+	    bcmp(dst, gate, dst->sa_len) == 0) {
 		/*
 		 * The route might already exist if this is an RTM_CHANGE
 		 * or a routing redirect, so try to delete it.
 		 */
-		if (rt_key(rt0))
-			rtrequest(RTM_DELETE, (struct sockaddr *)rt_key(rt0),
-			    rt0->rt_gateway, rt_mask(rt0), rt0->rt_flags, 0);
+		if (rt_key(rt))
+			rtrequest(RTM_DELETE, rt_key(rt),
+			    rt->rt_gateway, rt_mask(rt), rt->rt_flags, 0);
 		return EADDRNOTAVAIL;
 	}
 
@@ -945,12 +951,12 @@ rt_setgate(rt0, dst, gate)
 		R_Malloc(new, caddr_t, dlen + glen);
 		if (new == 0)
 			return ENOBUFS;
-		rt->rt_nodes->rn_key = new;
+		rt_key(rt) = new;
 	} else {
 		/*
 		 * otherwise just overwrite the old one
 		 */
-		new = rt->rt_nodes->rn_key;
+		new = (caddr_t)rt_key(rt);
 		old = 0;
 	}
 
@@ -966,6 +972,7 @@ rt_setgate(rt0, dst, gate)
 	if (old) {
 		Bcopy(dst, new, dlen);
 		Free(old);
+		dst = gate = 0;		/* XXX??? */
 	}
 
 	/*
@@ -989,10 +996,11 @@ rt_setgate(rt0, dst, gate)
 	if (rt->rt_flags & RTF_GATEWAY) {
 		rt->rt_gwroute = rtalloc1(gate, 1, RTF_PRCLONING);
 		if (rt->rt_gwroute == rt) {
-			RTFREE(rt->rt_gwroute);
+			RTFREE_LOCKED(rt->rt_gwroute);
 			rt->rt_gwroute = 0;
 			return EDQUOT; /* failure */
 		}
+		RT_UNLOCK(rt->rt_gwroute);
 	}
 
 	/*
@@ -1002,6 +1010,7 @@ rt_setgate(rt0, dst, gate)
 	 */
 	if (!(rt->rt_flags & RTF_HOST) && rt_mask(rt) != 0) {
 		struct rtfc_arg arg;
+
 		arg.rnh = rnh;
 		arg.rt0 = rt;
 		RADIX_NODE_HEAD_LOCK(rnh);
@@ -1014,8 +1023,7 @@ rt_setgate(rt0, dst, gate)
 }
 
 static void
-rt_maskedcopy(src, dst, netmask)
-	struct sockaddr *src, *dst, *netmask;
+rt_maskedcopy(struct sockaddr *src, struct sockaddr *dst, struct sockaddr *netmask)
 {
 	register u_char *cp1 = (u_char *)src;
 	register u_char *cp2 = (u_char *)dst;
@@ -1038,9 +1046,7 @@ rt_maskedcopy(src, dst, netmask)
  * for an interface.
  */
 int
-rtinit(ifa, cmd, flags)
-	register struct ifaddr *ifa;
-	int cmd, flags;
+rtinit(struct ifaddr *ifa, int cmd, int flags)
 {
 	register struct rtentry *rt;
 	register struct sockaddr *dst;
@@ -1112,19 +1118,23 @@ bad:
 		/*
 		 * notify any listening routing agents of the change
 		 */
+		RT_LOCK(rt);
 		rt_newaddrmsg(cmd, ifa, error, rt);
 		if (cmd == RTM_DELETE) {
 			/*
 			 * If we are deleting, and we found an entry, then
 			 * it's been removed from the tree.. now throw it away.
 			 */
-			RTFREE(rt);
-		} else if (cmd == RTM_ADD) {
-			/*
-			 * We just wanted to add it.. we don't actually
-			 * need a reference.
-			 */
-			rt->rt_refcnt--;
+			RTFREE_LOCKED(rt);
+		} else {
+			if (cmd == RTM_ADD) {
+				/*
+				 * We just wanted to add it.. we don't actually
+				 * need a reference.
+				 */
+				rt->rt_refcnt--;
+			}
+			RT_UNLOCK(rt);
 		}
 	}
 	if (m)
@@ -1132,55 +1142,78 @@ bad:
 	return (error);
 }
 
+/*
+ * Validate the route rt0 to the specified destination.  If the
+ * route is marked down try to find a new route.  If the route
+ * to the gateway is gone, try to setup a new route.  Otherwise,
+ * if the route is marked for packets to be rejected, enforce that.
+ *
+ * On return lrt contains the route to the destination and lrt0
+ * contains the route to the next hop.  Their values are meaningul
+ * ONLY if no error is returned.
+ *
+ * This routine is invoked on each layer 2 output path, prior to
+ * encapsulating outbound packets.
+ */
 int
-rt_check(lrt, lrt0, dst)
-	struct rtentry **lrt;
-	struct rtentry **lrt0;
-	struct sockaddr *dst;
+rt_check(struct rtentry **lrt, struct rtentry **lrt0, struct sockaddr *dst)
 {
+#define senderr(x) { error = x ; goto bad; }
 	struct rtentry *rt;
 	struct rtentry *rt0;
 	int error;
 
-	rt = *lrt;
 	rt0 = *lrt0;
-	error = 0;
-
 	rt = rt0;
-
-	if (rt != NULL) {
+	if (rt) {
+		/* NB: the locking here is tortuous... */
+		RT_LOCK(rt);
 		if ((rt->rt_flags & RTF_UP) == 0) {
-			rt0 = rt = rtalloc1(dst, 1, 0UL);
-			if (rt0 != NULL)
+			RT_UNLOCK(rt);
+			rt = rtalloc1(dst, 1, 0UL);
+			if (rt != NULL) {
 				rt->rt_refcnt--;
-			else
+				RT_UNLOCK(rt);
+			} else
 				senderr(EHOSTUNREACH);
+			rt0 = rt;
 		}
+		/* XXX BSD/OS checks dst->sa_family != AF_NS */
 		if (rt->rt_flags & RTF_GATEWAY) {
-			if (rt->rt_gwroute == NULL)
+			if (rt->rt_gwroute == 0)
 				goto lookup;
-
 			rt = rt->rt_gwroute;
+			RT_LOCK(rt);		/* NB: gwroute */
 			if ((rt->rt_flags & RTF_UP) == 0) {
-				rtfree(rt);
+				rtfree(rt);	/* unlock gwroute */
 				rt = rt0;
 			lookup:
-				rt->rt_gwroute = rtalloc1(rt->rt_gateway, 1, 0UL);
-				rt = rt->rt_gwroute;
-				if (rt == NULL)
+				RT_UNLOCK(rt0);
+				rt = rtalloc1(rt->rt_gateway, 1, 0UL);
+				RT_LOCK(rt0);
+				rt0->rt_gwroute = rt;
+				if (rt == 0) {
+					RT_UNLOCK(rt0);
 					senderr(EHOSTUNREACH);
+				}
 			}
+			RT_UNLOCK(rt0);
 		}
-		if (rt->rt_flags & RTF_REJECT)
-			if (rt->rt_rmx.rmx_expire == 0 ||
-				time_second < rt->rt_rmx.rmx_expire)
-				senderr(rt == rt0 ? EHOSTDOWN : EHOSTUNREACH);
+		/* XXX why are we inspecting rmx_expire? */
+		error = (rt->rt_flags & RTF_REJECT) &&
+			(rt->rt_rmx.rmx_expire == 0 ||
+				time_second < rt->rt_rmx.rmx_expire);
+		RT_UNLOCK(rt);
+		if (error)
+			senderr(rt == rt0 ? EHOSTDOWN : EHOSTUNREACH);
 	}
-
-bad:
-	*lrt = rt;
+	*lrt = rt;		/* NB: return unlocked */
 	*lrt0 = rt0;
+	return (0);
+bad:
+	/* NB: lrt and lrt0 should not be interpreted if error is non-zero */
 	return (error);
+#undef senderr
 }
 
 /* This must be before ip6_init2(), which is now SI_ORDER_MIDDLE */