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)

24 files changed, 440 insertions, 323 deletions

diff --git a/sys/net/if.c b/sys/net/if.c
index 42e3c57..6cf8852 100644
--- a/sys/net/if.c
+++ b/sys/net/if.c
@@ -831,8 +831,7 @@ if_clone_list(ifcr)
 	return (error);
 }
 
-#define	equal(a1, a2) \
-  (bcmp((caddr_t)(a1), (caddr_t)(a2), ((struct sockaddr *)(a1))->sa_len) == 0)
+#define	equal(a1, a2)	(bcmp((a1), (a2), ((a1))->sa_len) == 0)
 
 /*
  * Locate an interface based on a complete address.
@@ -912,7 +911,7 @@ ifa_ifwithnet(addr)
 	 * so do that if we can.
 	 */
 	if (af == AF_LINK) {
-	    register struct sockaddr_dl *sdl = (struct sockaddr_dl *)addr;
+	    struct sockaddr_dl *sdl = (struct sockaddr_dl *)addr;
 	    if (sdl->sdl_index && sdl->sdl_index <= if_index)
 		return (ifaddr_byindex(sdl->sdl_index));
 	}
@@ -1049,18 +1048,21 @@ link_rtrequest(cmd, rt, info)
 	register struct rtentry *rt;
 	struct rt_addrinfo *info;
 {
-	register struct ifaddr *ifa;
+	register struct ifaddr *ifa, *oifa;
 	struct sockaddr *dst;
 	struct ifnet *ifp;
 
+	RT_LOCK_ASSERT(rt);
+
 	if (cmd != RTM_ADD || ((ifa = rt->rt_ifa) == 0) ||
 	    ((ifp = ifa->ifa_ifp) == 0) || ((dst = rt_key(rt)) == 0))
 		return;
 	ifa = ifaof_ifpforaddr(dst, ifp);
 	if (ifa) {
-		IFAFREE(rt->rt_ifa);
 		IFAREF(ifa);		/* XXX */
+		oifa = rt->rt_ifa;
 		rt->rt_ifa = ifa;
+		IFAFREE(oifa);
 		if (ifa->ifa_rtrequest && ifa->ifa_rtrequest != link_rtrequest)
 			ifa->ifa_rtrequest(cmd, rt, info);
 	}
diff --git a/sys/net/if_disc.c b/sys/net/if_disc.c
index cfc0432..a392d5f 100644
--- a/sys/net/if_disc.c
+++ b/sys/net/if_disc.c
@@ -194,6 +194,8 @@ discoutput(struct ifnet *ifp, struct mbuf *m, struct sockaddr *dst,
 static void
 discrtrequest(int cmd, struct rtentry *rt, struct rt_addrinfo *info)
 {
+	RT_LOCK_ASSERT(rt);
+
 	if (rt)
 		rt->rt_rmx.rmx_mtu = DSMTU;
 }
diff --git a/sys/net/if_faith.c b/sys/net/if_faith.c
index 761f151..8a9cb7c 100644
--- a/sys/net/if_faith.c
+++ b/sys/net/if_faith.c
@@ -270,6 +270,8 @@ faithrtrequest(cmd, rt, info)
 	struct rtentry *rt;
 	struct rt_addrinfo *info;
 {
+	RT_LOCK_ASSERT(rt);
+
 	if (rt) {
 		rt->rt_rmx.rmx_mtu = rt->rt_ifp->if_mtu; /* for ISO */
 		/*
@@ -371,7 +373,7 @@ faithprefix(in6)
 	else
 		ret = 0;
 	if (rt)
-		RTFREE(rt);
+		RTFREE_LOCKED(rt);
 	return ret;
 }
 #endif
diff --git a/sys/net/if_loop.c b/sys/net/if_loop.c
index f9c806b..52c8d1c 100644
--- a/sys/net/if_loop.c
+++ b/sys/net/if_loop.c
@@ -355,6 +355,8 @@ lortrequest(cmd, rt, info)
 	struct rtentry *rt;
 	struct rt_addrinfo *info;
 {
+	RT_LOCK_ASSERT(rt);
+
 	if (rt) {
 		rt->rt_rmx.rmx_mtu = rt->rt_ifp->if_mtu; /* for ISO */
 		/*
diff --git a/sys/net/if_stf.c b/sys/net/if_stf.c
index e8ed1ca..93fa212 100644
--- a/sys/net/if_stf.c
+++ b/sys/net/if_stf.c
@@ -718,6 +718,7 @@ stf_rtrequest(cmd, rt, info)
 	struct rtentry *rt;
 	struct rt_addrinfo *info;
 {
+	RT_LOCK_ASSERT(rt);
 
 	if (rt)
 		rt->rt_rmx.rmx_mtu = IPV6_MMTU;
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 */
diff --git a/sys/net/route.h b/sys/net/route.h
index 869e49d..bec78bd 100644
--- a/sys/net/route.h
+++ b/sys/net/route.h
@@ -113,7 +113,10 @@ struct rtentry {
 		    struct rtentry *);
 					/* output routine for this (rt,if) */
 	struct	rtentry *rt_parent; 	/* cloning parent of this route */
-	struct	mtx *rt_mtx;		/* mutex for routing entry */
+#ifdef _KERNEL
+	/* XXX ugly, user apps use this definition but don't have a mtx def */
+	struct	mtx rt_mtx;		/* mutex for routing entry */
+#endif
 };
 
 /*
@@ -256,18 +259,26 @@ struct rt_addrinfo {
 
 #ifdef _KERNEL
 
-#define	RT_LOCK_INIT(rt) \
-    mtx_init((rt)->rt_mtx, "rtentry", NULL, MTX_DEF | MTX_DUPOK)
-#define	RT_LOCK(rt)		mtx_lock((rt)->rt_mtx)
-#define	RT_UNLOCK(rt)		mtx_unlock((rt)->rt_mtx)
-#define	RT_LOCK_DESTROY(rt)	mtx_destroy((rt)->rt_mtx)
+#define	RT_LOCK_INIT(_rt) \
+	mtx_init(&(_rt)->rt_mtx, "rtentry", NULL, MTX_DEF | MTX_DUPOK)
+#define	RT_LOCK(_rt)		mtx_lock(&(_rt)->rt_mtx)
+#define	RT_UNLOCK(_rt)		mtx_unlock(&(_rt)->rt_mtx)
+#define	RT_LOCK_DESTROY(_rt)	mtx_destroy(&(_rt)->rt_mtx)
+#define	RT_LOCK_ASSERT(_rt)	mtx_assert(&(_rt)->rt_mtx, MA_OWNED)
 
-#define	RTFREE(rt) \
-	do { \
-		if ((rt)->rt_refcnt <= 1) \
-			rtfree(rt); \
-		else \
-			(rt)->rt_refcnt--; \
+#define	RTFREE_LOCKED(_rt) do {				\
+		if ((_rt)->rt_refcnt <= 1)		\
+			rtfree(_rt);			\
+		else {					\
+			(_rt)->rt_refcnt--;		\
+			RT_UNLOCK(_rt);			\
+		}					\
+		/* guard against invalid refs */	\
+		_rt = 0;				\
+	} while (0)
+#define	RTFREE(_rt) do {				\
+		RT_LOCK(_rt);				\
+		RTFREE_LOCKED(_rt);			\
 	} while (0)
 
 extern struct radix_node_head *rt_tables[AF_MAX+1];
@@ -281,16 +292,16 @@ void	 rt_ifmsg(struct ifnet *);
 void	 rt_missmsg(int, struct rt_addrinfo *, int, int);
 void	 rt_newaddrmsg(int, struct ifaddr *, int, struct rtentry *);
 void	 rt_newmaddrmsg(int, struct ifmultiaddr *);
-int	 rt_setgate(struct rtentry *, struct sockaddr *, struct sockaddr *);
 void	 rtalloc(struct route *);
+int	 rt_setgate(struct rtentry *, struct sockaddr *, struct sockaddr *);
 void	 rtalloc_ign(struct route *, u_long);
-struct rtentry *
-	 rtalloc1(struct sockaddr *, int, u_long);
+/* NB: the rtentry is returned locked */
+struct rtentry *rtalloc1(struct sockaddr *, int, u_long);
 void	 rtfree(struct rtentry *);
 int	 rtinit(struct ifaddr *, int, int);
 int	 rtioctl(u_long, caddr_t);
 void	 rtredirect(struct sockaddr *, struct sockaddr *,
-	    struct sockaddr *, int, struct sockaddr *, struct rtentry **);
+	    struct sockaddr *, int, struct sockaddr *);
 int	 rtrequest(int, struct sockaddr *,
 	    struct sockaddr *, struct sockaddr *, int, struct rtentry **);
 int	 rtrequest1(int, struct rt_addrinfo *, struct rtentry **);
diff --git a/sys/net/rtsock.c b/sys/net/rtsock.c
index 4af77ec..201e4a9 100644
--- a/sys/net/rtsock.c
+++ b/sys/net/rtsock.c
@@ -351,6 +351,7 @@ route_output(m, so)
 		saved_nrt = 0;
 		error = rtrequest1(RTM_ADD, &info, &saved_nrt);
 		if (error == 0 && saved_nrt) {
+			RT_LOCK(saved_nrt);
 			rt_setmetrics(rtm->rtm_inits,
 				&rtm->rtm_rmx, &saved_nrt->rt_rmx);
 			saved_nrt->rt_rmx.rmx_locks &= ~(rtm->rtm_inits);
@@ -358,6 +359,7 @@ route_output(m, so)
 				(rtm->rtm_inits & rtm->rtm_rmx.rmx_locks);
 			saved_nrt->rt_refcnt--;
 			saved_nrt->rt_genmask = info.rti_info[RTAX_GENMASK];
+			RT_UNLOCK(saved_nrt);
 		}
 		break;
 
@@ -365,6 +367,7 @@ route_output(m, so)
 		saved_nrt = 0;
 		error = rtrequest1(RTM_DELETE, &info, &saved_nrt);
 		if (error == 0) {
+			RT_LOCK(saved_nrt);
 			rt = saved_nrt;
 			goto report;
 		}
@@ -382,12 +385,14 @@ route_output(m, so)
 		RADIX_NODE_HEAD_UNLOCK(rnh);
 		if (rt == NULL)		/* XXX looks bogus */
 			senderr(ESRCH);
+		RT_LOCK(rt);
 		rt->rt_refcnt++;
 
 		switch(rtm->rtm_type) {
 
 		case RTM_GET:
 		report:
+			RT_LOCK_ASSERT(rt);
 			info.rti_info[RTAX_DST] = rt_key(rt);
 			info.rti_info[RTAX_GATEWAY] = rt->rt_gateway;
 			info.rti_info[RTAX_NETMASK] = rt_mask(rt);
@@ -413,6 +418,7 @@ route_output(m, so)
 				struct rt_msghdr *new_rtm;
 				R_Malloc(new_rtm, struct rt_msghdr *, len);
 				if (new_rtm == 0) {
+					RT_UNLOCK(rt);
 					senderr(ENOBUFS);
 				}
 				Bcopy(rtm, new_rtm, rtm->rtm_msglen);
@@ -438,12 +444,14 @@ route_output(m, so)
 			     !sa_equal(info.rti_info[RTAX_IFA],
 				       rt->rt_ifa->ifa_addr))) {
 				if ((error = rt_getifa(&info)) != 0) {
+					RT_UNLOCK(rt);
 					senderr(error);
 				}
 			}
 			if (info.rti_info[RTAX_GATEWAY] != NULL &&
 			    (error = rt_setgate(rt, rt_key(rt),
 					info.rti_info[RTAX_GATEWAY])) != 0) {
+				RT_UNLOCK(rt);
 				senderr(error);
 			}
 			if ((ifa = info.rti_ifa) != NULL) {
@@ -474,6 +482,7 @@ route_output(m, so)
 				(rtm->rtm_inits & rtm->rtm_rmx.rmx_locks);
 			break;
 		}
+		RT_UNLOCK(rt);
 		break;
 
 	default:
diff --git a/sys/netinet/if_atm.c b/sys/netinet/if_atm.c
index 82c95bf..5a9e53e 100644
--- a/sys/netinet/if_atm.c
+++ b/sys/netinet/if_atm.c
@@ -325,8 +325,10 @@ atmresolve(struct rtentry *rt, struct mbuf *m, struct sockaddr *dst,
 		    (rt->rt_flags & RTF_LLINFO) == 0 ||
 		    /* XXX: are we using LLINFO? */
 		    rt->rt_gateway->sa_family != AF_LINK) {
+			RT_UNLOCK(rt);
 			goto bad;
 		}
+		RT_UNLOCK(rt);
 	}
 
 	/*
diff --git a/sys/netinet/if_ether.c b/sys/netinet/if_ether.c
index 239c616..4cc1d4e 100644
--- a/sys/netinet/if_ether.c
+++ b/sys/netinet/if_ether.c
@@ -105,11 +105,13 @@ struct llinfo_arp {
 static	LIST_HEAD(, llinfo_arp) llinfo_arp;
 
 static struct	ifqueue arpintrq;
-static int	arp_inuse, arp_allocated, arpinit_done;
+static int	arp_allocated;
+static int	arpinit_done;
 
 static int	arp_maxtries = 5;
 static int	useloopback = 1; /* use loopback interface for local traffic */
 static int	arp_proxyall = 0;
+static struct callout arp_callout;
 
 SYSCTL_INT(_net_link_ether_inet, OID_AUTO, maxtries, CTLFLAG_RW,
 	   &arp_maxtries, 0, "");
@@ -140,7 +142,6 @@ arptimer(ignored_arg)
 	void *ignored_arg;
 {
 	struct llinfo_arp *la, *ola;
-	int s = splnet();
 
 	RADIX_NODE_HEAD_LOCK(rt_tables[AF_INET]);
 	la = LIST_FIRST(&llinfo_arp);
@@ -152,8 +153,8 @@ arptimer(ignored_arg)
 			arptfree(ola);		/* timer has expired, clear */
 	}
 	RADIX_NODE_HEAD_UNLOCK(rt_tables[AF_INET]);
-	splx(s);
-	timeout(arptimer, NULL, arpt_prune * hz);
+
+	callout_reset(&arp_callout, arpt_prune * hz, arptimer, NULL);
 }
 
 /*
@@ -165,16 +166,20 @@ arp_rtrequest(req, rt, info)
 	register struct rtentry *rt;
 	struct rt_addrinfo *info;
 {
-	register struct sockaddr *gate = rt->rt_gateway;
-	register struct llinfo_arp *la = (struct llinfo_arp *)rt->rt_llinfo;
+	register struct sockaddr *gate;
+	register struct llinfo_arp *la;
 	static struct sockaddr_dl null_sdl = {sizeof(null_sdl), AF_LINK};
 
+	RT_LOCK_ASSERT(rt);
+
 	if (!arpinit_done) {
 		arpinit_done = 1;
-		timeout(arptimer, (caddr_t)0, hz);
+		callout_reset(&arp_callout, hz, arptimer, NULL);
 	}
 	if (rt->rt_flags & RTF_GATEWAY)
 		return;
+	gate = rt->rt_gateway;
+	la = (struct llinfo_arp *)rt->rt_llinfo;
 	switch (req) {
 
 	case RTM_ADD:
@@ -208,7 +213,7 @@ arp_rtrequest(req, rt, info)
 	case RTM_RESOLVE:
 		if (gate->sa_family != AF_LINK ||
 		    gate->sa_len < sizeof(null_sdl)) {
-			log(LOG_DEBUG, "arp_rtrequest: bad gateway %s%s\n",
+			log(LOG_DEBUG, "%s: bad gateway %s%s\n", __func__,
 			    inet_ntoa(SIN(rt_key(rt))->sin_addr),
 			    (gate->sa_family != AF_LINK) ?
 			    " (!AF_LINK)": "");
@@ -222,14 +227,13 @@ arp_rtrequest(req, rt, info)
 		 * Case 2:  This route may come from cloning, or a manual route
 		 * add with a LL address.
 		 */
-		R_Malloc(la, struct llinfo_arp *, sizeof(*la));
+		R_Zalloc(la, struct llinfo_arp *, sizeof(*la));
 		rt->rt_llinfo = (caddr_t)la;
 		if (la == 0) {
-			log(LOG_DEBUG, "arp_rtrequest: malloc failed\n");
+			log(LOG_DEBUG, "%s: malloc failed\n", __func__);
 			break;
 		}
-		arp_inuse++, arp_allocated++;
-		Bzero(la, sizeof(*la));
+		arp_allocated++;
 		la->la_rt = rt;
 		rt->rt_flags |= RTF_LLINFO;
 		RADIX_NODE_HEAD_LOCK_ASSERT(rt_tables[AF_INET]);
@@ -280,7 +284,6 @@ arp_rtrequest(req, rt, info)
 	case RTM_DELETE:
 		if (la == 0)
 			break;
-		arp_inuse--;
 		RADIX_NODE_HEAD_LOCK_ASSERT(rt_tables[AF_INET]);
 		LIST_REMOVE(la, la_le);
 		rt->rt_llinfo = 0;
@@ -475,6 +478,7 @@ arpresolve(ifp, rt, m, dst, desten, rt0)
 		m_freem(la->la_hold);
 	la->la_hold = m;
 	if (rt->rt_expire) {
+		RT_LOCK(rt);
 		rt->rt_flags &= ~RTF_REJECT;
 		if (la->la_asked == 0 || rt->rt_expire != time_second) {
 			rt->rt_expire = time_second;
@@ -491,6 +495,7 @@ arpresolve(ifp, rt, m, dst, desten, rt0)
 			}
 
 		}
+		RT_UNLOCK(rt);
 	}
 	return (0);
 }
@@ -505,8 +510,9 @@ arpintr(struct mbuf *m)
 	struct arphdr *ar;
 
 	if (!arpinit_done) {
+		/* NB: this race should not matter */
 		arpinit_done = 1;
-		timeout(arptimer, (caddr_t)0, hz);
+		callout_reset(&arp_callout, hz, arptimer, NULL);
 	}
 	if (m->m_len < sizeof(struct arphdr) &&
 	    ((m = m_pullup(m, sizeof(struct arphdr))) == NULL)) {
@@ -736,9 +742,11 @@ match:
 			m->m_pkthdr.len += 8;
 			th->rcf = trld->trld_rcf;
 		}
+		RT_LOCK(rt);
 		if (rt->rt_expire)
 			rt->rt_expire = time_second + arpt_keep;
 		rt->rt_flags &= ~RTF_REJECT;
+		RT_UNLOCK(rt);
 		la->la_asked = 0;
 		la->la_preempt = arp_maxtries;
 		if (la->la_hold) {
@@ -885,13 +893,16 @@ arptfree(la)
 {
 	register struct rtentry *rt = la->la_rt;
 	register struct sockaddr_dl *sdl;
+
 	if (rt == 0)
 		panic("arptfree");
 	if (rt->rt_refcnt > 0 && (sdl = SDL(rt->rt_gateway)) &&
 	    sdl->sdl_family == AF_LINK) {
 		sdl->sdl_alen = 0;
 		la->la_preempt = la->la_asked = 0;
+		RT_LOCK(rt);		/* XXX needed or move higher? */
 		rt->rt_flags &= ~RTF_REJECT;
+		RT_UNLOCK(rt);
 		return;
 	}
 	rtrequest(RTM_DELETE, rt_key(rt), (struct sockaddr *)0, rt_mask(rt),
@@ -906,15 +917,18 @@ arplookup(addr, create, proxy)
 	int create, proxy;
 {
 	register struct rtentry *rt;
-	static struct sockaddr_inarp sin = {sizeof(sin), AF_INET };
+	struct sockaddr_inarp sin;
 	const char *why = 0;
 
+	bzero(&sin, sizeof(sin));
+	sin.sin_len = sizeof(sin);
+	sin.sin_family = AF_INET;
 	sin.sin_addr.s_addr = addr;
-	sin.sin_other = proxy ? SIN_PROXY : 0;
+	if (proxy)
+		sin.sin_other = SIN_PROXY;
 	rt = rtalloc1((struct sockaddr *)&sin, create, 0UL);
 	if (rt == 0)
 		return (0);
-	rt->rt_refcnt--;
 
 	if (rt->rt_flags & RTF_GATEWAY)
 		why = "host is not on local network";
@@ -924,25 +938,32 @@ arplookup(addr, create, proxy)
 		why = "gateway route is not ours";
 
 	if (why) {
-		if (create) {
+#define	ISDYNCLONE(_rt) \
+	(((_rt)->rt_flags & (RTF_STATIC | RTF_WASCLONED)) == RTF_WASCLONED)
+		if (create)
 			log(LOG_DEBUG, "arplookup %s failed: %s\n",
 			    inet_ntoa(sin.sin_addr), why);
-			/*
-			 * If there are no references to this Layer 2 route,
-			 * and it is a cloned route, and not static, and
-			 * arplookup() is creating the route, then purge
-			 * it from the routing table as it is probably bogus.
-			 */
-			if (((rt->rt_flags & (RTF_STATIC | RTF_WASCLONED)) ==
-			    RTF_WASCLONED) && (rt->rt_refcnt == 0))
-				rtrequest(RTM_DELETE,
-				    (struct sockaddr *)rt_key(rt),
-				    rt->rt_gateway, rt_mask(rt),
-				    rt->rt_flags, 0);
+		/*
+		 * If there are no references to this Layer 2 route,
+		 * and it is a cloned route, and not static, and
+		 * 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);
 		return (0);
+#undef ISDYNCLONE
+	} else {
+		rt->rt_refcnt--;
+		RT_UNLOCK(rt);
+		return ((struct llinfo_arp *)rt->rt_llinfo);
 	}
-	return ((struct llinfo_arp *)rt->rt_llinfo);
 }
 
 void
@@ -964,7 +985,7 @@ arp_init(void)
 	arpintrq.ifq_maxlen = 50;
 	mtx_init(&arpintrq.ifq_mtx, "arp_inq", NULL, MTX_DEF);
 	LIST_INIT(&llinfo_arp);
+	callout_init(&arp_callout, CALLOUT_MPSAFE);
 	netisr_register(NETISR_ARP, arpintr, &arpintrq);
 }
-
 SYSINIT(arp, SI_SUB_PROTO_DOMAIN, SI_ORDER_ANY, arp_init, 0);
diff --git a/sys/netinet/in_pcb.c b/sys/netinet/in_pcb.c
index dc52d89..e094c8c 100644
--- a/sys/netinet/in_pcb.c
+++ b/sys/netinet/in_pcb.c
@@ -165,11 +165,9 @@ in_pcballoc(so, pcbinfo, td)
 #ifdef IPSEC
 	int error;
 #endif
-
-	inp = uma_zalloc(pcbinfo->ipi_zone, M_NOWAIT);
+	inp = uma_zalloc(pcbinfo->ipi_zone, M_NOWAIT | M_ZERO);
 	if (inp == NULL)
 		return (ENOBUFS);
-	bzero((caddr_t)inp, sizeof(*inp));
 	inp->inp_gencnt = ++pcbinfo->ipi_gencnt;
 	inp->inp_pcbinfo = pcbinfo;
 	inp->inp_socket = so;
@@ -678,7 +676,7 @@ in_pcbdetach(inp)
 	if (inp->inp_options)
 		(void)m_free(inp->inp_options);
 	if (inp->inp_route.ro_rt)
-		rtfree(inp->inp_route.ro_rt);
+		RTFREE(inp->inp_route.ro_rt);
 	ip_freemoptions(inp->inp_moptions);
 	inp->inp_vflag = 0;
 	INP_LOCK_DESTROY(inp);
@@ -865,16 +863,19 @@ in_losing(inp)
 	struct rt_addrinfo info;
 
 	if ((rt = inp->inp_route.ro_rt)) {
+		RT_LOCK(rt);
+		inp->inp_route.ro_rt = NULL;
 		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);
 		rt_missmsg(RTM_LOSING, &info, rt->rt_flags, 0);
-		if (rt->rt_flags & RTF_DYNAMIC)
+		if (rt->rt_flags & RTF_DYNAMIC) {
+			RT_UNLOCK(rt);		/* XXX refcnt? */
 			(void) rtrequest1(RTM_DELETE, &info, NULL);
-		inp->inp_route.ro_rt = NULL;
-		rtfree(rt);
+		} else
+			rtfree(rt);
 		/*
 		 * A new route can be allocated
 		 * the next time output is attempted.
@@ -892,7 +893,7 @@ in_rtchange(inp, errno)
 	int errno;
 {
 	if (inp->inp_route.ro_rt) {
-		rtfree(inp->inp_route.ro_rt);
+		RTFREE(inp->inp_route.ro_rt);
 		inp->inp_route.ro_rt = 0;
 		/*
 		 * A new route can be allocated the next time
diff --git a/sys/netinet/in_rmx.c b/sys/netinet/in_rmx.c
index 0c743b5..5092bb9 100644
--- a/sys/netinet/in_rmx.c
+++ b/sys/netinet/in_rmx.c
@@ -49,6 +49,7 @@
 #include <sys/socket.h>
 #include <sys/mbuf.h>
 #include <sys/syslog.h>
+#include <sys/callout.h>
 
 #include <net/if.h>
 #include <net/route.h>
@@ -124,14 +125,17 @@ 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);
 				ret = rn_addroute(v_arg, n_arg, head,
 						  treenodes);
+				RT_LOCK(rt2);
 			}
-			RTFREE(rt2);
+			RTFREE_LOCKED(rt2);
 		}
 	}
 
@@ -159,6 +163,7 @@ in_matroute(void *v_arg, struct radix_node_head *head)
 	struct radix_node *rn = rn_match(v_arg, head);
 	struct rtentry *rt = (struct rtentry *)rn;
 
+	/*XXX locking? */
 	if (rt && rt->rt_refcnt == 0) {		/* this is first reference */
 		if (rt->rt_flags & RTPRF_OURS) {
 			rt->rt_flags &= ~RTPRF_OURS;
@@ -190,6 +195,8 @@ in_clsroute(struct radix_node *rn, struct radix_node_head *head)
 {
 	struct rtentry *rt = (struct rtentry *)rn;
 
+	RT_LOCK_ASSERT(rt);
+
 	if (!(rt->rt_flags & RTF_UP))
 		return;			/* prophylactic measures */
 
@@ -207,10 +214,13 @@ 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);
 	}
 }
 
@@ -268,6 +278,7 @@ in_rtqkill(struct radix_node *rn, void *rock)
 
 #define RTQ_TIMEOUT	60*10	/* run no less than once every ten minutes */
 static int rtq_timeout = RTQ_TIMEOUT;
+static struct callout rtq_timer;
 
 static void
 in_rtqtimo(void *rock)
@@ -276,17 +287,14 @@ in_rtqtimo(void *rock)
 	struct rtqk_arg arg;
 	struct timeval atv;
 	static time_t last_adjusted_timeout = 0;
-	int s;
 
 	arg.found = arg.killed = 0;
 	arg.rnh = rnh;
 	arg.nextstop = time_second + rtq_timeout;
 	arg.draining = arg.updating = 0;
-	s = splnet();
 	RADIX_NODE_HEAD_LOCK(rnh);
 	rnh->rnh_walktree(rnh, in_rtqkill, &arg);
 	RADIX_NODE_HEAD_UNLOCK(rnh);
-	splx(s);
 
 	/*
 	 * Attempt to be somewhat dynamic about this:
@@ -311,16 +319,14 @@ in_rtqtimo(void *rock)
 #endif
 		arg.found = arg.killed = 0;
 		arg.updating = 1;
-		s = splnet();
 		RADIX_NODE_HEAD_LOCK(rnh);
 		rnh->rnh_walktree(rnh, in_rtqkill, &arg);
 		RADIX_NODE_HEAD_UNLOCK(rnh);
-		splx(s);
 	}
 
 	atv.tv_usec = 0;
 	atv.tv_sec = arg.nextstop - time_second;
-	timeout(in_rtqtimo, rock, tvtohz(&atv));
+	callout_reset(&rtq_timer, tvtohz(&atv), in_rtqtimo, rock);
 }
 
 void
@@ -328,17 +334,15 @@ in_rtqdrain(void)
 {
 	struct radix_node_head *rnh = rt_tables[AF_INET];
 	struct rtqk_arg arg;
-	int s;
+
 	arg.found = arg.killed = 0;
 	arg.rnh = rnh;
 	arg.nextstop = 0;
 	arg.draining = 1;
 	arg.updating = 0;
-	s = splnet();
 	RADIX_NODE_HEAD_LOCK(rnh);
 	rnh->rnh_walktree(rnh, in_rtqkill, &arg);
 	RADIX_NODE_HEAD_UNLOCK(rnh);
-	splx(s);
 }
 
 /*
@@ -359,6 +363,7 @@ in_inithead(void **head, int off)
 	rnh->rnh_addaddr = in_addroute;
 	rnh->rnh_matchaddr = in_matroute;
 	rnh->rnh_close = in_clsroute;
+	callout_init(&rtq_timer, CALLOUT_MPSAFE);
 	in_rtqtimo(rnh);	/* kick off timeout first time */
 	return 1;
 }
@@ -395,7 +400,9 @@ 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);
+		RT_UNLOCK(rt);
 		err = rtrequest(RTM_DELETE, (struct sockaddr *)rt_key(rt),
 				rt->rt_gateway, rt_mask(rt), rt->rt_flags, 0);
 		if (err) {
@@ -420,6 +427,6 @@ in_ifadown(struct ifaddr *ifa, int delete)
 	RADIX_NODE_HEAD_LOCK(rnh);
 	rnh->rnh_walktree(rnh, in_ifadownkill, &arg);
 	RADIX_NODE_HEAD_UNLOCK(rnh);
-	ifa->ifa_flags &= ~IFA_ROUTE;
+	ifa->ifa_flags &= ~IFA_ROUTE;		/* XXXlocking? */
 	return 0;
 }
diff --git a/sys/netinet/ip_flow.c b/sys/netinet/ip_flow.c
index f2e23ea..25b8fce 100644
--- a/sys/netinet/ip_flow.c
+++ b/sys/netinet/ip_flow.c
@@ -352,7 +352,9 @@ ipflow_create(const struct route *ro, struct mbuf *m)
 	 * Fill in the updated information.
 	 */
 	ipf->ipf_ro = *ro;
+	RT_LOCK(ro->ro_rt);
 	ro->ro_rt->rt_refcnt++;
+	RT_UNLOCK(ro->ro_rt);
 	ipf->ipf_timer = IPFLOW_TIMER;
 	/*
 	 * Insert into the approriate bucket of the flow table.
diff --git a/sys/netinet/ip_icmp.c b/sys/netinet/ip_icmp.c
index f4df251..1e485e3 100644
--- a/sys/netinet/ip_icmp.c
+++ b/sys/netinet/ip_icmp.c
@@ -427,7 +427,7 @@ icmp_input(m, off)
 				}
 			}
 			if (rt)
-				RTFREE(rt);
+				rtfree(rt);
 		}
 
 #endif
@@ -565,7 +565,7 @@ reflect:
 		rtredirect((struct sockaddr *)&icmpsrc,
 		  (struct sockaddr *)&icmpdst,
 		  (struct sockaddr *)0, RTF_GATEWAY | RTF_HOST,
-		  (struct sockaddr *)&icmpgw, (struct rtentry **)0);
+		  (struct sockaddr *)&icmpgw);
 		pfctlinput(PRC_REDIRECT_HOST, (struct sockaddr *)&icmpsrc);
 #ifdef IPSEC
 		key_sa_routechange((struct sockaddr *)&icmpsrc);
diff --git a/sys/netinet/ip_output.c b/sys/netinet/ip_output.c
index 41e0cc0..dc71879 100644
--- a/sys/netinet/ip_output.c
+++ b/sys/netinet/ip_output.c
@@ -1986,7 +1986,7 @@ ip_setmoptions(sopt, imop)
 				break;
 			}
 			ifp = ro.ro_rt->rt_ifp;
-			rtfree(ro.ro_rt);
+			RTFREE(ro.ro_rt);
 		}
 		else {
 			ifp = ip_multicast_if(&mreq.imr_interface, NULL);
diff --git a/sys/netinet6/icmp6.c b/sys/netinet6/icmp6.c
index d964b58..1373131 100644
--- a/sys/netinet6/icmp6.c
+++ b/sys/netinet6/icmp6.c
@@ -1160,9 +1160,8 @@ icmp6_mtudisc_update(ip6cp, validated)
 			rt->rt_rmx.rmx_mtu = mtu;
 		}
 	}
-	if (rt) { /* XXX: need braces to avoid conflict with else in RTFREE. */
-		RTFREE(rt);
-	}
+	if (rt)
+		rtfree(rt);
 }
 
 /*
@@ -2298,7 +2297,7 @@ icmp6_redirect_input(m, off)
 			    "ICMP6 redirect rejected; no route "
 			    "with inet6 gateway found for redirect dst: %s\n",
 			    icmp6_redirect_diag(&src6, &reddst6, &redtgt6)));
-			RTFREE(rt);
+			RTFREE_LOCKED(rt);
 			goto bad;
 		}
 
@@ -2310,7 +2309,7 @@ icmp6_redirect_input(m, off)
 				"%s\n",
 				ip6_sprintf(gw6),
 				icmp6_redirect_diag(&src6, &reddst6, &redtgt6)));
-			RTFREE(rt);
+			RTFREE_LOCKED(rt);
 			goto bad;
 		}
 	} else {
@@ -2320,7 +2319,7 @@ icmp6_redirect_input(m, off)
 			icmp6_redirect_diag(&src6, &reddst6, &redtgt6)));
 		goto bad;
 	}
-	RTFREE(rt);
+	RTFREE_LOCKED(rt);
 	rt = NULL;
     }
 	if (IN6_IS_ADDR_MULTICAST(&reddst6)) {
@@ -2395,8 +2394,7 @@ icmp6_redirect_input(m, off)
 		bcopy(&src6, &ssrc.sin6_addr, sizeof(struct in6_addr));
 		rtredirect((struct sockaddr *)&sdst, (struct sockaddr *)&sgw,
 			   (struct sockaddr *)NULL, RTF_GATEWAY | RTF_HOST,
-			   (struct sockaddr *)&ssrc,
-			   (struct rtentry **)NULL);
+			   (struct sockaddr *)&ssrc);
 	}
 	/* finally update cached route in each socket via pfctlinput */
     {
diff --git a/sys/netinet6/in6.c b/sys/netinet6/in6.c
index 945ab65..838df1e 100644
--- a/sys/netinet6/in6.c
+++ b/sys/netinet6/in6.c
@@ -175,32 +175,35 @@ in6_ifloop_request(int cmd, struct ifaddr *ifa)
 		    e);
 	}
 
-	/*
-	 * Make sure rt_ifa be equal to IFA, the second argument of the
-	 * function.
-	 * We need this because when we refer to rt_ifa->ia6_flags in
-	 * ip6_input, we assume that the rt_ifa points to the address instead
-	 * of the loopback address.
-	 */
-	if (cmd == RTM_ADD && nrt && ifa != nrt->rt_ifa) {
-		IFAFREE(nrt->rt_ifa);
-		IFAREF(ifa);
-		nrt->rt_ifa = ifa;
-	}
-
-	/*
-	 * Report the addition/removal of the address to the routing socket.
-	 * XXX: since we called rtinit for a p2p interface with a destination,
-	 *      we end up reporting twice in such a case.  Should we rather
-	 *      omit the second report?
-	 */
 	if (nrt) {
+		RT_LOCK(nrt);
+		/*
+		 * Make sure rt_ifa be equal to IFA, the second argument of
+		 * the function.  We need this because when we refer to
+		 * rt_ifa->ia6_flags in ip6_input, we assume that the rt_ifa
+		 * points to the address instead of the loopback address.
+		 */
+		if (cmd == RTM_ADD && ifa != nrt->rt_ifa) {
+			IFAFREE(nrt->rt_ifa);
+			IFAREF(ifa);
+			nrt->rt_ifa = ifa;
+		}
+
+		/*
+		 * Report the addition/removal of the address to the routing
+		 * socket.
+		 *
+		 * XXX: since we called rtinit for a p2p interface with a
+		 *      destination, we end up reporting twice in such a case.
+		 *      Should we rather omit the second report?
+		 */
 		rt_newaddrmsg(cmd, ifa, e, nrt);
 		if (cmd == RTM_DELETE) {
-			RTFREE(nrt);
+			rtfree(nrt);
 		} else {
 			/* the cmd must be RTM_ADD here */
 			nrt->rt_refcnt--;
+			RT_UNLOCK(nrt);
 		}
 	}
 }
@@ -223,7 +226,7 @@ in6_ifaddloop(struct ifaddr *ifa)
 	    (rt->rt_ifp->if_flags & IFF_LOOPBACK) == 0)
 		in6_ifloop_request(RTM_ADD, ifa);
 	if (rt)
-		rt->rt_refcnt--;
+		rtfree(rt);
 }
 
 /*
@@ -271,10 +274,13 @@ in6_ifremloop(struct ifaddr *ifa)
 		 * to a shared medium.
 		 */
 		rt = rtalloc1(ifa->ifa_addr, 0, 0);
-		if (rt != NULL && (rt->rt_flags & RTF_HOST) != 0 &&
-		    (rt->rt_ifp->if_flags & IFF_LOOPBACK) != 0) {
-			rt->rt_refcnt--;
-			in6_ifloop_request(RTM_DELETE, ifa);
+		if (rt != NULL) {
+			if ((rt->rt_flags & RTF_HOST) != 0 &&
+			    (rt->rt_ifp->if_flags & IFF_LOOPBACK) != 0) {
+				rtfree(rt);
+				in6_ifloop_request(RTM_DELETE, ifa);
+			} else
+				RT_UNLOCK(rt);
 		}
 	}
 }
diff --git a/sys/netinet6/in6_ifattach.c b/sys/netinet6/in6_ifattach.c
index 88e29c8..24df8fe 100644
--- a/sys/netinet6/in6_ifattach.c
+++ b/sys/netinet6/in6_ifattach.c
@@ -988,10 +988,14 @@ in6_ifdetach(ifp)
 	sin6.sin6_addr = in6addr_linklocal_allnodes;
 	sin6.sin6_addr.s6_addr16[1] = htons(ifp->if_index);
 	rt = rtalloc1((struct sockaddr *)&sin6, 0, 0UL);
-	if (rt && rt->rt_ifp == ifp) {
-		rtrequest(RTM_DELETE, (struct sockaddr *)rt_key(rt),
-			rt->rt_gateway, rt_mask(rt), rt->rt_flags, 0);
-		rtfree(rt);
+	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);
 	}
 }
 
diff --git a/sys/netinet6/in6_pcb.c b/sys/netinet6/in6_pcb.c
index f160661..36130ff 100644
--- a/sys/netinet6/in6_pcb.c
+++ b/sys/netinet6/in6_pcb.c
@@ -569,6 +569,7 @@ in6_selectsrc(dstsock, opts, mopts, ro, laddr, errorp)
 			if (IN6_IS_ADDR_MULTICAST(dst)) {
 				ro->ro_rt = rtalloc1(&((struct route *)ro)
 						     ->ro_dst, 0, 0UL);
+				RT_UNLOCK(ro->ro_rt);
 			} else {
 				rtalloc((struct route *)ro);
 			}
@@ -653,7 +654,7 @@ in6_pcbdetach(inp)
  	ip6_freepcbopts(inp->in6p_outputopts);
  	ip6_freemoptions(inp->in6p_moptions);
 	if (inp->in6p_route.ro_rt)
-		rtfree(inp->in6p_route.ro_rt);
+		RTFREE(inp->in6p_route.ro_rt);
 	/* Check and free IPv4 related resources in case of mapped addr */
 	if (inp->inp_options)
 		(void)m_free(inp->inp_options);
@@ -1038,16 +1039,19 @@ in6_losing(in6p)
 	struct rt_addrinfo info;
 
 	if ((rt = in6p->in6p_route.ro_rt) != NULL) {
+		RT_LOCK(rt);
+		in6p->in6p_route.ro_rt = NULL;
 		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);
 		rt_missmsg(RTM_LOSING, &info, rt->rt_flags, 0);
-		if (rt->rt_flags & RTF_DYNAMIC)
+		if (rt->rt_flags & RTF_DYNAMIC) {
+			RT_UNLOCK(rt);		/* XXX refcnt? */
 			(void)rtrequest1(RTM_DELETE, &info, NULL);
-		in6p->in6p_route.ro_rt = NULL;
-		rtfree(rt);
+		} else
+			rtfree(rt);
 		/*
 		 * A new route can be allocated
 		 * the next time output is attempted.
@@ -1065,7 +1069,7 @@ in6_rtchange(inp, errno)
 	int errno;
 {
 	if (inp->in6p_route.ro_rt) {
-		rtfree(inp->in6p_route.ro_rt);
+		RTFREE(inp->in6p_route.ro_rt);
 		inp->in6p_route.ro_rt = 0;
 		/*
 		 * A new route can be allocated the next time
diff --git a/sys/netinet6/in6_rmx.c b/sys/netinet6/in6_rmx.c
index 14587bd..e9eba3c 100644
--- a/sys/netinet6/in6_rmx.c
+++ b/sys/netinet6/in6_rmx.c
@@ -82,6 +82,7 @@
 #include <sys/socketvar.h>
 #include <sys/mbuf.h>
 #include <sys/syslog.h>
+#include <sys/callout.h>
 
 #include <net/if.h>
 #include <net/route.h>
@@ -165,14 +166,17 @@ 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);
 				ret = rn_addroute(v_arg, n_arg, head,
 					treenodes);
+				RT_LOCK(rt2);
 			}
-			RTFREE(rt2);
+			RTFREE_LOCKED(rt2);
 		}
 	} else if (ret == NULL && rt->rt_flags & RTF_CLONING) {
 		struct rtentry *rt2;
@@ -198,7 +202,7 @@ in6_addroute(void *v_arg, void *n_arg, struct radix_node_head *head,
 			 && rt2->rt_ifp == rt->rt_ifp) {
 				ret = rt2->rt_nodes;
 			}
-			RTFREE(rt2);
+			RTFREE_LOCKED(rt2);
 		}
 	}
 	return ret;
@@ -251,6 +255,8 @@ in6_clsroute(struct radix_node *rn, struct radix_node_head *head)
 {
 	struct rtentry *rt = (struct rtentry *)rn;
 
+	RT_LOCK_ASSERT(rt);
+
 	if (!(rt->rt_flags & RTF_UP))
 		return;		/* prophylactic measures */
 
@@ -269,10 +275,13 @@ 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);
 	}
 }
 
@@ -331,6 +340,7 @@ in6_rtqkill(struct radix_node *rn, void *rock)
 
 #define RTQ_TIMEOUT	60*10	/* run no less than once every ten minutes */
 static int rtq_timeout = RTQ_TIMEOUT;
+static struct callout rtq_timer;
 
 static void
 in6_rtqtimo(void *rock)
@@ -339,17 +349,14 @@ in6_rtqtimo(void *rock)
 	struct rtqk_arg arg;
 	struct timeval atv;
 	static time_t last_adjusted_timeout = 0;
-	int s;
 
 	arg.found = arg.killed = 0;
 	arg.rnh = rnh;
 	arg.nextstop = time_second + rtq_timeout;
 	arg.draining = arg.updating = 0;
-	s = splnet();
 	RADIX_NODE_HEAD_LOCK(rnh);
 	rnh->rnh_walktree(rnh, in6_rtqkill, &arg);
 	RADIX_NODE_HEAD_UNLOCK(rnh);
-	splx(s);
 
 	/*
 	 * Attempt to be somewhat dynamic about this:
@@ -374,16 +381,14 @@ in6_rtqtimo(void *rock)
 #endif
 		arg.found = arg.killed = 0;
 		arg.updating = 1;
-		s = splnet();
 		RADIX_NODE_HEAD_LOCK(rnh);
 		rnh->rnh_walktree(rnh, in6_rtqkill, &arg);
 		RADIX_NODE_HEAD_UNLOCK(rnh);
-		splx(s);
 	}
 
 	atv.tv_usec = 0;
 	atv.tv_sec = arg.nextstop;
-	timeout(in6_rtqtimo, rock, tvtohz(&atv));
+	callout_reset(&rtq_timer, tvtohz(&atv), in6_rtqtimo, rock);
 }
 
 /*
@@ -393,6 +398,7 @@ struct mtuex_arg {
 	struct radix_node_head *rnh;
 	time_t nextstop;
 };
+static struct callout rtq_mtutimer;
 
 static int
 in6_mtuexpire(struct radix_node *rn, void *rock)
@@ -424,15 +430,12 @@ in6_mtutimo(void *rock)
 	struct radix_node_head *rnh = rock;
 	struct mtuex_arg arg;
 	struct timeval atv;
-	int s;
 
 	arg.rnh = rnh;
 	arg.nextstop = time_second + MTUTIMO_DEFAULT;
-	s = splnet();
 	RADIX_NODE_HEAD_LOCK(rnh);
 	rnh->rnh_walktree(rnh, in6_mtuexpire, &arg);
 	RADIX_NODE_HEAD_UNLOCK(rnh);
-	splx(s);
 
 	atv.tv_usec = 0;
 	atv.tv_sec = arg.nextstop;
@@ -440,7 +443,7 @@ in6_mtutimo(void *rock)
 		printf("invalid mtu expiration time on routing table\n");
 		arg.nextstop = time_second + 30;	/* last resort */
 	}
-	timeout(in6_mtutimo, rock, tvtohz(&atv));
+	callout_reset(&rtq_mtutimer, tvtohz(&atv), in6_mtutimo, rock);
 }
 
 #if 0
@@ -449,17 +452,15 @@ in6_rtqdrain()
 {
 	struct radix_node_head *rnh = rt_tables[AF_INET6];
 	struct rtqk_arg arg;
-	int s;
+
 	arg.found = arg.killed = 0;
 	arg.rnh = rnh;
 	arg.nextstop = 0;
 	arg.draining = 1;
 	arg.updating = 0;
-	s = splnet();
 	RADIX_NODE_HEAD_LOCK(rnh);
 	rnh->rnh_walktree(rnh, in6_rtqkill, &arg);
 	RADIX_NODE_HEAD_UNLOCK(rnh);
-	splx(s);
 }
 #endif
 
@@ -481,7 +482,9 @@ in6_inithead(void **head, int off)
 	rnh->rnh_addaddr = in6_addroute;
 	rnh->rnh_matchaddr = in6_matroute;
 	rnh->rnh_close = in6_clsroute;
+	callout_init(&rtq_timer, CALLOUT_MPSAFE);
 	in6_rtqtimo(rnh);	/* kick off timeout first time */
+	callout_init(&rtq_mtutimer, CALLOUT_MPSAFE);
 	in6_mtutimo(rnh);	/* kick off timeout first time */
 	return 1;
 }
diff --git a/sys/netinet6/in6_src.c b/sys/netinet6/in6_src.c
index 3dd2212..84e73d6 100644
--- a/sys/netinet6/in6_src.c
+++ b/sys/netinet6/in6_src.c
@@ -256,6 +256,7 @@ in6_selectsrc(dstsock, opts, mopts, ro, laddr, errorp)
 			if (IN6_IS_ADDR_MULTICAST(dst)) {
 				ro->ro_rt = rtalloc1(&((struct route *)ro)
 						     ->ro_dst, 0, 0UL);
+				RT_UNLOCK(ro->ro_rt);
 			} else {
 				rtalloc((struct route *)ro);
 			}
diff --git a/sys/netinet6/ip6_output.c b/sys/netinet6/ip6_output.c
index 14e54fd..ff7cf8b 100644
--- a/sys/netinet6/ip6_output.c
+++ b/sys/netinet6/ip6_output.c
@@ -707,6 +707,7 @@ skip_ipsec2:;
 			ia = ifatoia6(ro->ro_rt->rt_ifa);
 			ifp = ro->ro_rt->rt_ifp;
 			ro->ro_rt->rt_use++;
+			RT_UNLOCK(ro->ro_rt);
 		}
 
 		if ((flags & IPV6_FORWARDING) == 0)
@@ -2080,7 +2081,7 @@ ip6_setmoptions(optname, im6op, m)
 					break;
 				}
 				ifp = ro.ro_rt->rt_ifp;
-				rtfree(ro.ro_rt);
+				RTFREE(ro.ro_rt);
 			}
 		} else
 			ifp = ifnet_byindex(mreq->ipv6mr_interface);
diff --git a/sys/netinet6/nd6.c b/sys/netinet6/nd6.c
index 8fc4abf..7ef59c9 100644
--- a/sys/netinet6/nd6.c
+++ b/sys/netinet6/nd6.c
@@ -811,17 +811,18 @@ nd6_lookup(addr6, create, ifp)
 	sin6.sin6_scope_id = in6_addr2scopeid(ifp, addr6);
 #endif
 	rt = rtalloc1((struct sockaddr *)&sin6, create, 0UL);
-	if (rt && (rt->rt_flags & RTF_LLINFO) == 0) {
-		/*
-		 * This is the case for the default route.
-		 * If we want to create a neighbor cache for the address, we
-		 * should free the route for the destination and allocate an
-		 * interface route.
-		 */
-		if (create) {
-			RTFREE(rt);
+	if (rt) {
+		if ((rt->rt_flags & RTF_LLINFO) == 0 && create) {
+			/*
+			 * This is the case for the default route.
+			 * If we want to create a neighbor cache for the
+			 * address, we should free the route for the
+			 * destination and allocate an interface route.
+			 */
+			RTFREE_LOCKED(rt);
 			rt = 0;
 		}
+		RT_UNLOCK(rt);
 	}
 	if (!rt) {
 		if (create && ifp) {
@@ -1103,6 +1104,8 @@ nd6_rtrequest(req, rt, info)
 	struct ifnet *ifp = rt->rt_ifp;
 	struct ifaddr *ifa;
 
+	RT_LOCK_ASSERT(rt);
+
 	if ((rt->rt_flags & RTF_GATEWAY))
 		return;
 
@@ -1889,10 +1892,10 @@ nd6_output(ifp, origifp, m0, dst, rt0)
 	 */
 	if (rt) {
 		if ((rt->rt_flags & RTF_UP) == 0) {
-			if ((rt0 = rt = rtalloc1((struct sockaddr *)dst, 1, 0UL)) !=
-				NULL)
-			{
+			rt0 = rt = rtalloc1((struct sockaddr *)dst, 1, 0UL);
+			if (rt != NULL) {
 				rt->rt_refcnt--;
+				RT_UNLOCK(rt);
 				if (rt->rt_ifp != ifp) {
 					/* XXX: loop care? */
 					return nd6_output(ifp, origifp, m0,
@@ -1933,6 +1936,7 @@ nd6_output(ifp, origifp, m0, dst, rt0)
 			lookup: rt->rt_gwroute = rtalloc1(rt->rt_gateway, 1, 0UL);
 				if ((rt = rt->rt_gwroute) == 0)
 					senderr(EHOSTUNREACH);
+				RT_UNLOCK(rt);
 			}
 		}
 	}
diff --git a/sys/netinet6/nd6_rtr.c b/sys/netinet6/nd6_rtr.c
index 7714969..845c2fd 100644
--- a/sys/netinet6/nd6_rtr.c
+++ b/sys/netinet6/nd6_rtr.c
@@ -472,7 +472,6 @@ defrouter_addreq(new)
 {
 	struct sockaddr_in6 def, mask, gate;
 	struct rtentry *newrt = NULL;
-	int s;
 
 	Bzero(&def, sizeof(def));
 	Bzero(&mask, sizeof(mask));
@@ -483,15 +482,15 @@ defrouter_addreq(new)
 	def.sin6_family = mask.sin6_family = gate.sin6_family = AF_INET6;
 	gate.sin6_addr = new->rtaddr;
 
-	s = splnet();
 	(void)rtrequest(RTM_ADD, (struct sockaddr *)&def,
 		(struct sockaddr *)&gate, (struct sockaddr *)&mask,
 		RTF_GATEWAY, &newrt);
 	if (newrt) {
+		RT_LOCK(newrt);
 		nd6_rtmsg(RTM_ADD, newrt); /* tell user process */
 		newrt->rt_refcnt--;
+		RT_UNLOCK(newrt);
 	}
-	splx(s);
 	return;
 }
 
@@ -531,13 +530,12 @@ defrouter_addifreq(ifp)
 		    "defrouter_addifreq: failed to install a route to "
 		    "interface %s (errno = %d)\n",
 		    if_name(ifp), error));
-
-		if (newrt)	/* maybe unnecessary, but do it for safety */
-			newrt->rt_refcnt--;
 	} else {
 		if (newrt) {
+			RT_LOCK(newrt);
 			nd6_rtmsg(RTM_ADD, newrt);
 			newrt->rt_refcnt--;
+			RT_UNLOCK(newrt);
 		}
 	}
 }
@@ -1500,8 +1498,11 @@ nd6_prefix_onlink(pr)
 		    ip6_sprintf(&mask6.sin6_addr), rtflags, error));
 	}
 
-	if (rt != NULL)
+	if (rt != NULL) {
+		RT_LOCK(rt);
 		rt->rt_refcnt--;
+		RT_UNLOCK(rt);
+	}
 
 	return(error);
 }