Implement routing priorities. Every route inserted has a priority assigned

and the one route with the lowest number wins. This will be used by the
routing daemons to resolve the synchronisations issue in case of conflicts.
The nasty bits of this are in the multipath code. If no priority is specified
the kernel will choose an appropriate priority.

Looked at by a few people at n2k8 code is much older

12 files changed, 179 insertions, 94 deletions

diff --git a/sys/kern/vfs_subr.c b/sys/kern/vfs_subr.c
index 5638d013a07..6dbd5d14323 100644
--- a/sys/kern/vfs_subr.c
+++ b/sys/kern/vfs_subr.c
@@ -1,4 +1,4 @@
-/*	$OpenBSD: vfs_subr.c,v 1.164 2008/05/06 17:19:40 thib Exp $	*/
+/*	$OpenBSD: vfs_subr.c,v 1.165 2008/05/07 05:14:21 claudio Exp $	*/
 /*	$NetBSD: vfs_subr.c,v 1.53 1996/04/22 01:39:13 christos Exp $	*/
 
 /*
@@ -1424,7 +1424,7 @@ vfs_hang_addrlist(struct mount *mp, struct netexport *nep,
 		}
 	}
 	rn = (*rnh->rnh_addaddr)((caddr_t)saddr, (caddr_t)smask, rnh,
-		np->netc_rnodes);
+		np->netc_rnodes, 0);
 	if (rn == 0 || np != (struct netcred *)rn) { /* already exists */
 		error = EPERM;
 		goto out;
diff --git a/sys/net/pf_table.c b/sys/net/pf_table.c
index eebe03bcb7e..207a4f5a6c9 100644
--- a/sys/net/pf_table.c
+++ b/sys/net/pf_table.c
@@ -1,4 +1,4 @@
-/*	$OpenBSD: pf_table.c,v 1.72 2007/12/20 20:07:41 reyk Exp $	*/
+/*	$OpenBSD: pf_table.c,v 1.73 2008/05/07 05:14:21 claudio Exp $	*/
 
 /*
  * Copyright (c) 2002 Cedric Berger
@@ -988,9 +988,9 @@ pfr_route_kentry(struct pfr_ktable *kt, struct pfr_kentry *ke)
 	s = splsoftnet();
 	if (KENTRY_NETWORK(ke)) {
 		pfr_prepare_network(&mask, ke->pfrke_af, ke->pfrke_net);
-		rn = rn_addroute(&ke->pfrke_sa, &mask, head, ke->pfrke_node);
+		rn = rn_addroute(&ke->pfrke_sa, &mask, head, ke->pfrke_node, 0);
 	} else
-		rn = rn_addroute(&ke->pfrke_sa, NULL, head, ke->pfrke_node);
+		rn = rn_addroute(&ke->pfrke_sa, NULL, head, ke->pfrke_node, 0);
 	splx(s);
 
 	return (rn == NULL ? -1 : 0);
diff --git a/sys/net/radix.c b/sys/net/radix.c
index 5847d511fee..116d68e2b69 100644
--- a/sys/net/radix.c
+++ b/sys/net/radix.c
@@ -1,4 +1,4 @@
-/*	$OpenBSD: radix.c,v 1.21 2006/06/18 11:47:45 pascoe Exp $	*/
+/*	$OpenBSD: radix.c,v 1.22 2008/05/07 05:14:21 claudio Exp $	*/
 /*	$NetBSD: radix.c,v 1.20 2003/08/07 16:32:56 agc Exp $	*/
 
 /*
@@ -51,6 +51,8 @@
 #endif
 
 #ifndef SMALL_KERNEL
+#include <sys/socket.h>
+#include <net/route.h>
 #include <net/radix_mpath.h>
 #endif
 
@@ -503,13 +505,13 @@ rn_new_radix_mask(struct radix_node *tt, struct radix_mask *next)
 
 struct radix_node *
 rn_addroute(void *v_arg, void *n_arg, struct radix_node_head *head,
-    struct radix_node treenodes[2])
+    struct radix_node treenodes[2], u_int8_t prio)
 {
 	caddr_t v = (caddr_t)v_arg, netmask = (caddr_t)n_arg;
 	struct radix_node *t, *x = NULL, *tt;
 	struct radix_node *saved_tt, *top = head->rnh_treetop;
 	short b = 0, b_leaf = 0;
-	int keyduplicated;
+	int keyduplicated, prioinv = 0;
 	caddr_t mmask;
 	struct radix_mask *m, **mp;
 
@@ -536,19 +538,38 @@ rn_addroute(void *v_arg, void *n_arg, struct radix_node_head *head,
 #ifndef SMALL_KERNEL
 			/* permit multipath, if enabled for the family */
 			if (rn_mpath_capable(head) && netmask == tt->rn_mask) {
+				int mid;
 				/*
 				 * Try to insert the new node in the middle
 				 * of the list of any preexisting multipaths,
 				 * to reduce the number of path disruptions
 				 * that occur as a result of an insertion,
 				 * per RFC2992.
+				 * Additionally keep the list sorted by route
+				 * priority.
 				 */
-				int mid = rn_mpath_count(tt) / 2;
+				tt = rn_mpath_prio(tt, prio);
+				if (((struct rtentry *)tt)->rt_priority !=
+				    prio) {
+					/*
+					 * rn_mpath_prio returns the previous
+					 * element if no element with the 
+					 * requested priority exists. It could
+					 * be that the previous element comes
+					 * with a bigger priority.
+					 */
+					if (((struct rtentry *)tt)->
+					    rt_priority > prio)
+						prioinv = 1;
+					t = tt;
+					break;
+				}
+
+				mid = rn_mpath_count(tt) / 2;
 				do {
 					t = tt;
-					tt = tt->rn_dupedkey;
-				} while (tt && t->rn_mask == tt->rn_mask
-				    && --mid > 0);
+					tt = rn_mpath_next(tt);
+				} while (tt && --mid > 0);
 				break;
 			}
 #endif
@@ -574,7 +595,7 @@ rn_addroute(void *v_arg, void *n_arg, struct radix_node_head *head,
 		 * We also reverse, or doubly link the list through the
 		 * parent pointer.
 		 */
-		if (tt == saved_tt) {
+		if (tt == saved_tt && prioinv) {
 			struct	radix_node *xx = x;
 			/* link in at head of list */
 			(tt = treenodes)->rn_dupedkey = t;
@@ -587,6 +608,13 @@ rn_addroute(void *v_arg, void *n_arg, struct radix_node_head *head,
 				x->rn_r = tt;
 			saved_tt = tt;
 			x = xx;
+		} else if (prioinv) {
+			(tt = treenodes)->rn_dupedkey = t;
+			if (t->rn_p == NULL)
+				panic("rn_addroute: t->rn_p is NULL");
+			t->rn_p->rn_dupedkey = tt;
+			tt->rn_p = t->rn_p;
+			t->rn_p = tt;
 		} else {
 			(tt = treenodes)->rn_dupedkey = t->rn_dupedkey;
 			t->rn_dupedkey = tt;
@@ -690,28 +718,11 @@ rn_delete(void *v_arg, void *netmask_arg, struct radix_node_head *head,
 	struct radix_node *dupedkey, *saved_tt, *top;
 	caddr_t v, netmask;
 	int b, head_off, vlen;
-#ifndef SMALL_KERNEL
-	int mpath_enable = 0;
-#endif
 
 	v = v_arg;
 	netmask = netmask_arg;
 	x = head->rnh_treetop;
-#ifndef SMALL_KERNEL
-	if (rn) {
-		tt = rn;
-		/*
-		 * Is this route(rn) a rn->dupedkey chain? 
-		 */
-		if (rn_mpath_next(tt->rn_p))
-			mpath_enable = 1;
-		else
-			tt = rn_search(v, x);
-	} else
-		tt = rn_search(v, x);
-#else
 	tt = rn_search(v, x);
-#endif
 	head_off = x->rn_off;
 	vlen =  *(u_char *)v;
 	saved_tt = tt;
@@ -730,6 +741,13 @@ rn_delete(void *v_arg, void *netmask_arg, struct radix_node_head *head,
 			if ((tt = tt->rn_dupedkey) == 0)
 				return (0);
 	}
+#ifndef SMALL_KERNEL
+	if (rn) {
+		while (tt != rn)
+			if ((tt = tt->rn_dupedkey) == 0)
+				return (0);
+	}
+#endif
 	if (tt->rn_mask == 0 || (saved_m = m = tt->rn_mklist) == 0)
 		goto on1;
 	if (tt->rn_flags & RNF_NORMAL) {
@@ -791,14 +809,10 @@ on1:
 			else
 				t->rn_r = x;
 		} else {
-			/* find node in front of tt on the chain */
-			for (x = p = saved_tt; p && p->rn_dupedkey != tt;)
-				p = p->rn_dupedkey;
-			if (p) {
-				p->rn_dupedkey = tt->rn_dupedkey;
-				if (tt->rn_dupedkey)
-					tt->rn_dupedkey->rn_p = p;
-			} else log(LOG_ERR, "rn_delete: couldn't find us\n");
+			x = saved_tt;
+			t->rn_dupedkey = tt->rn_dupedkey;
+			if (tt->rn_dupedkey)
+				tt->rn_dupedkey->rn_p = t;
 		}
 		t = tt + 1;
 		if  (t->rn_flags & RNF_ACTIVE) {
@@ -820,16 +834,6 @@ on1:
 		}
 		goto out;
 	}
-#ifndef SMALL_KERNEL
-	if (mpath_enable) {
-		/*
-		 * my parent dupedkey is NULL
-		 * end of mpath route.
-		 */
-		t->rn_dupedkey = NULL;
-		goto out;
-	}
-#endif
 	if (t->rn_l == tt)
 		x = t->rn_r;
 	else
diff --git a/sys/net/radix.h b/sys/net/radix.h
index f3324f56f9a..9194ead7f13 100644
--- a/sys/net/radix.h
+++ b/sys/net/radix.h
@@ -1,4 +1,4 @@
-/*	$OpenBSD: radix.h,v 1.13 2006/06/16 15:50:28 claudio Exp $	*/
+/*	$OpenBSD: radix.h,v 1.14 2008/05/07 05:14:21 claudio Exp $	*/
 /*	$NetBSD: radix.h,v 1.8 1996/02/13 22:00:37 christos Exp $	*/
 
 /*
@@ -108,7 +108,8 @@ struct radix_node_head {
 	int	rnh_pktsize;		/* permit, but not require fixed keys */
 					/* add based on sockaddr */
 	struct	radix_node *(*rnh_addaddr)(void *v, void *mask,
-		     struct radix_node_head *head, struct radix_node nodes[]);
+		     struct radix_node_head *head, struct radix_node nodes[],
+		     u_int8_t prio);
 					/* remove based on sockaddr */
 	struct	radix_node *(*rnh_deladdr)(void *v, void *mask,
 		    struct radix_node_head *head, struct radix_node *rn);
@@ -141,7 +142,7 @@ int	rn_walktree(struct radix_node_head *,
 
 struct radix_node	*rn_addmask(void *, int, int);
 struct radix_node	*rn_addroute(void *, void *, struct radix_node_head *,
-			    struct radix_node [2]);
+			    struct radix_node [2], u_int8_t);
 struct radix_node	*rn_delete(void *, void *, struct radix_node_head *,
 			    struct radix_node *);
 struct radix_node	*rn_insert(void *, struct radix_node_head *, int *,
diff --git a/sys/net/radix_mpath.c b/sys/net/radix_mpath.c
index 1f72136f376..0c7b07b61ef 100644
--- a/sys/net/radix_mpath.c
+++ b/sys/net/radix_mpath.c
@@ -1,4 +1,4 @@
-/*	$OpenBSD: radix_mpath.c,v 1.10 2008/05/07 02:45:24 claudio Exp $	*/
+/*	$OpenBSD: radix_mpath.c,v 1.11 2008/05/07 05:14:21 claudio Exp $	*/
 /*	$KAME: radix_mpath.c,v 1.13 2002/10/28 21:05:59 itojun Exp $	*/
 
 /*
@@ -67,17 +67,45 @@ rn_mpath_capable(struct radix_node_head *rnh)
 struct radix_node *
 rn_mpath_next(struct radix_node *rn)
 {
-	struct radix_node *next;
+	struct radix_node	*next;
+	struct rtentry		*rt = (struct rtentry *)rn;
 
 	if (!rn->rn_dupedkey)
 		return NULL;
 	next = rn->rn_dupedkey;
-	if (rn->rn_mask == next->rn_mask)
+	if (rn->rn_mask == next->rn_mask &&
+	    rt->rt_priority == ((struct rtentry *)next)->rt_priority)
 		return next;
 	else
 		return NULL;
 }
 
+struct radix_node *
+rn_mpath_prio(struct radix_node *rn, u_int8_t prio)
+{
+	struct radix_node	*prev = rn;
+	struct rtentry		*rt;
+
+	if (prio == RTP_ANY)
+		return (rn);
+
+	while (rn) {
+		/* different netmask -> different route */
+		if (rn->rn_mask != prev->rn_mask)
+			return (prev);
+
+		rt = (struct rtentry *)rn;
+		if (rt->rt_priority == prio)
+			return (rn);
+		if (rt->rt_priority > prio)
+			/* list is sorted return last more prefered entry */
+			return (prev);
+		prev = rn;
+		rn = rn->rn_dupedkey;
+	}
+	return (prev);
+}
+
 int
 rn_mpath_count(struct radix_node *rn)
 {
@@ -90,10 +118,16 @@ rn_mpath_count(struct radix_node *rn)
 }
 
 struct rtentry *
-rt_mpath_matchgate(struct rtentry *rt, struct sockaddr *gate)
+rt_mpath_matchgate(struct rtentry *rt, struct sockaddr *gate, u_int8_t prio)
 {
 	struct radix_node *rn = (struct radix_node *)rt;
 
+	rn = rn_mpath_prio((struct radix_node *)rt, prio);
+	rt = (struct rtentry *)rn;
+	/* check if returned node has same priority */
+	if (prio != RTP_ANY && rt->rt_priority != prio)
+		return NULL;
+
 	/*
 	 * if gate is set it must be compared, if not set the route must be
 	 * a non-multipath one.
@@ -190,9 +224,10 @@ rt_mpath_conflict(struct radix_node_head *rnh, struct rtentry *rt,
 	}
 
  maskmatched:
-	if (!mpathok)
+	if (!mpathok && rt1->rt_priority == rt->rt_priority)
 		return EEXIST;
 
+	rn1 = rn_mpath_prio((struct radix_node *)rt1, rt->rt_priority);
 	/* key/mask were the same.  compare gateway for all multipaths */
 	do {
 		rt1 = (struct rtentry *)rn1;
@@ -206,6 +241,10 @@ rt_mpath_conflict(struct radix_node_head *rnh, struct rtentry *rt,
 		    rt1->rt_gateway->sa_len))
 			continue;
 
+		/* check the route priority */
+		if (rt1->rt_priority != rt->rt_priority)
+			continue;
+
 		/* all key/mask/gateway are the same.  conflicting entry. */
 		return EEXIST;
 	} while ((rn1 = rn_mpath_next(rn1)) != NULL);
diff --git a/sys/net/radix_mpath.h b/sys/net/radix_mpath.h
index cf75be8e134..46c39a9414b 100644
--- a/sys/net/radix_mpath.h
+++ b/sys/net/radix_mpath.h
@@ -1,4 +1,4 @@
-/*	$OpenBSD: radix_mpath.h,v 1.5 2006/06/18 11:47:45 pascoe Exp $	*/
+/*	$OpenBSD: radix_mpath.h,v 1.6 2008/05/07 05:14:21 claudio Exp $	*/
 /*	$KAME: radix_mpath.h,v 1.9 2004/03/30 11:21:49 keiichi Exp $	*/
 
 /*
@@ -46,11 +46,13 @@ struct rtentry;
 struct sockaddr;
 int	rn_mpath_capable(struct radix_node_head *);
 struct radix_node *rn_mpath_next(struct radix_node *);
+struct radix_node *rn_mpath_prio(struct radix_node *, u_int8_t);
 int	rn_mpath_count(struct radix_node *);
-struct rtentry *rt_mpath_matchgate(struct rtentry *, struct sockaddr *);
+struct rtentry *rt_mpath_matchgate(struct rtentry *, struct sockaddr *,
+	    u_int8_t);
 int	rt_mpath_conflict(struct radix_node_head *, struct rtentry *,
-	struct sockaddr *, int);
-void	rtalloc_mpath(struct route *, u_int32_t *, u_int tableid);
+	    struct sockaddr *, int);
+void	rtalloc_mpath(struct route *, u_int32_t *, u_int);
 int	rn_mpath_inithead(void **, int);
 #endif
 
diff --git a/sys/net/route.c b/sys/net/route.c
index 567d759463a..d357bad2c93 100644
--- a/sys/net/route.c
+++ b/sys/net/route.c
@@ -1,4 +1,4 @@
-/*	$OpenBSD: route.c,v 1.89 2008/05/07 02:45:24 claudio Exp $	*/
+/*	$OpenBSD: route.c,v 1.90 2008/05/07 05:14:21 claudio Exp $	*/
 /*	$NetBSD: route.c,v 1.14 1996/02/13 22:00:46 christos Exp $	*/
 
 /*
@@ -497,7 +497,7 @@ create:
 			info.rti_ifa = ifa;
 			info.rti_flags = flags;
 			rt = NULL;
-			error = rtrequest1(RTM_ADD, &info, &rt, 0);
+			error = rtrequest1(RTM_ADD, &info, RTP_DEFAULT, &rt, 0);
 			if (rt != NULL)
 				flags = rt->rt_flags;
 			stat = &rtstat.rts_dynamic;
@@ -554,7 +554,7 @@ rtdeletemsg(struct rtentry *rt, u_int tableid)
 	info.rti_info[RTAX_GATEWAY] = rt->rt_gateway;
 	info.rti_flags = rt->rt_flags;
 	ifp = rt->rt_ifp;
-	error = rtrequest1(RTM_DELETE, &info, &rt, tableid);
+	error = rtrequest1(RTM_DELETE, &info, rt->rt_priority, &rt, tableid);
 
 	rt_missmsg(RTM_DELETE, &info, info.rti_flags, ifp, error, tableid);
 
@@ -671,7 +671,7 @@ rtrequest(int req, struct sockaddr *dst, struct sockaddr *gateway,
 	info.rti_info[RTAX_DST] = dst;
 	info.rti_info[RTAX_GATEWAY] = gateway;
 	info.rti_info[RTAX_NETMASK] = netmask;
-	return (rtrequest1(req, &info, ret_nrt, tableid));
+	return (rtrequest1(req, &info, RTP_DEFAULT/*XXX*/, ret_nrt, tableid));
 }
 
 int
@@ -720,8 +720,8 @@ rt_getifa(struct rt_addrinfo *info)
 }
 
 int
-rtrequest1(int req, struct rt_addrinfo *info, struct rtentry **ret_nrt,
-    u_int tableid)
+rtrequest1(int req, struct rt_addrinfo *info, u_int8_t prio,
+    struct rtentry **ret_nrt, u_int tableid)
 {
 	int			 s = splsoftnet(); int error = 0;
 	struct rtentry		*rt, *crt;
@@ -750,7 +750,7 @@ rtrequest1(int req, struct rt_addrinfo *info, struct rtentry **ret_nrt,
 		 */
 		if (rn_mpath_capable(rnh)) {
 			rt = rt_mpath_matchgate(rt,
-			    info->rti_info[RTAX_GATEWAY]);
+			    info->rti_info[RTAX_GATEWAY], prio);
 			rn = (struct radix_node *)rt;
 			if (!rt)
 				senderr(ESRCH);
@@ -823,6 +823,7 @@ makeroute:
 			senderr(ENOBUFS);
 		Bzero(rt, sizeof(*rt));
 		rt->rt_flags = RTF_UP | info->rti_flags;
+		rt->rt_priority = prio;	/* init routing priority */
 		LIST_INIT(&rt->rt_timer);
 		if (rt_setgate(rt, info->rti_info[RTAX_DST],
 		    info->rti_info[RTAX_GATEWAY], tableid)) {
@@ -868,14 +869,15 @@ makeroute:
 			rt->rt_parent->rt_refcnt++;
 		}
 		rn = rnh->rnh_addaddr((caddr_t)ndst,
-		    (caddr_t)info->rti_info[RTAX_NETMASK], rnh, rt->rt_nodes);
+		    (caddr_t)info->rti_info[RTAX_NETMASK], rnh, rt->rt_nodes,
+		    rt->rt_priority);
 		if (rn == NULL && (crt = rtalloc1(ndst, 0, tableid)) != NULL) {
 			/* overwrite cloned route */
 			if ((crt->rt_flags & RTF_CLONED) != 0) {
 				rtdeletemsg(crt, tableid);
 				rn = rnh->rnh_addaddr((caddr_t)ndst,
 				    (caddr_t)info->rti_info[RTAX_NETMASK],
-				    rnh, rt->rt_nodes);
+				    rnh, rt->rt_nodes, rt->rt_priority);
 			}
 			RTFREE(crt);
 		}
@@ -1046,7 +1048,7 @@ rtinit(struct ifaddr *ifa, int cmd, int flags)
 	 * change it to meet bsdi4 behavior.
 	 */
 	info.rti_info[RTAX_NETMASK] = ifa->ifa_netmask;
-	error = rtrequest1(cmd, &info, &nrt, 0);
+	error = rtrequest1(cmd, &info, RTP_CONNECTED, &nrt, 0);
 	if (cmd == RTM_DELETE && error == 0 && (rt = nrt) != NULL) {
 		rt_newaddrmsg(cmd, ifa, error, nrt);
 		if (rt->rt_refcnt <= 0) {
@@ -1389,8 +1391,7 @@ rt_if_remove_rtdelete(struct radix_node *rn, void *vifp)
 	if (rt->rt_ifp == ifp) {
 		int	cloning = (rt->rt_flags & RTF_CLONING);
 
-		if (rtrequest(RTM_DELETE, rt_key(rt), rt->rt_gateway,
-		    rt_mask(rt), 0, NULL, 0) == 0 && cloning)
+		if (rtdeletemsg(rt, 0) == 0 && cloning)
 			return (EAGAIN);
 	}
 
diff --git a/sys/net/route.h b/sys/net/route.h
index 83e156d09d4..56a5cb24eea 100644
--- a/sys/net/route.h
+++ b/sys/net/route.h
@@ -1,4 +1,4 @@
-/*	$OpenBSD: route.h,v 1.48 2008/04/23 10:55:14 norby Exp $	*/
+/*	$OpenBSD: route.h,v 1.49 2008/05/07 05:14:21 claudio Exp $	*/
 /*	$NetBSD: route.h,v 1.9 1996/02/13 22:00:49 christos Exp $	*/
 
 /*
@@ -112,7 +112,7 @@ struct rtentry {
 	u_int	rt_flags;		/* up/down?, host/net */
 	int	rt_refcnt;		/* # held references */
 	struct	ifnet *rt_ifp;		/* the answer: interface to use */
-	struct	ifaddr *rt_ifa;		/* the answer: interface to use */
+	struct	ifaddr *rt_ifa;		/* the answer: interface addr to use */
 	struct	sockaddr *rt_genmask;	/* for generation of cloned routes */
 	caddr_t	rt_llinfo;		/* pointer to link level info cache */
 	struct	rt_kmetrics rt_rmx;	/* metrics used by rx'ing protocols */
@@ -120,6 +120,7 @@ struct rtentry {
 	struct	rtentry *rt_parent;	/* If cloned, parent of this route. */
 	LIST_HEAD(, rttimer) rt_timer;  /* queue of timeouts for misc funcs */
 	u_int16_t rt_labelid;		/* route label ID */
+	u_int8_t rt_priority;		/* routing priority to use */
 };
 #define	rt_use	rt_rmx.rmx_pksent
 
@@ -140,7 +141,6 @@ struct rtentry {
 #define RTF_PROTO2	0x4000		/* protocol specific routing flag */
 #define RTF_PROTO1	0x8000		/* protocol specific routing flag */
 #define RTF_CLONED	0x10000		/* this is a cloned route */
-#define RTF_SOURCE	0x20000		/* this route has a source selector */
 #define RTF_MPATH	0x40000		/* multipath route or operation */
 #define RTF_JUMBO	0x80000		/* try to use jumbo frames */
 
@@ -151,9 +151,22 @@ struct rtentry {
 
 #ifndef _KERNEL
 /* obsoleted */
-#define	RTF_TUNNEL	0x100000	/* Tunnelling bit. */
+#define RTF_SOURCE	0x20000		/* this route has a source selector */
+#define RTF_TUNNEL	0x100000	/* Tunnelling bit. */
 #endif
 
+/* Routing priorities used by the different routing protocols */
+#define RTP_NONE	0	/* unset priority use sane default */
+#define RTP_CONNECTED	4	/* directly connected routes */
+#define RTP_STATIC	8	/* static routes */
+#define RTP_OSPF	16	/* OSPF routes */
+#define RTP_ISIS	20	/* IS-IS routes */
+#define RTP_RIP		24	/* RIP routes */
+#define RTP_BGP		32	/* BGP routes */
+#define RTP_DEFAULT	48	/* routes that have nothing set */
+#define RTP_MAX		63	/* maximum priority */
+#define RTP_ANY		64	/* any of the above */
+
 /*
  * Routing statistics.
  */
@@ -175,7 +188,7 @@ struct rt_msghdr {
 	u_short	rtm_hdrlen;	/* sizeof(rt_msghdr) to skip over the header */
 	u_short	rtm_index;	/* index for associated ifp */
 	u_short rtm_tableid;	/* routing table id */
-	u_char	rtm_prio;	/* routing priority */
+	u_char	rtm_priority;	/* routing priority */
 	u_char	rtm_pad;
 	int	rtm_addrs;	/* bitmask identifying sockaddrs in msg */
 	int	rtm_flags;	/* flags, incl. kern & message, e.g. DONE */
@@ -398,7 +411,8 @@ void	 rtredirect(struct sockaddr *, struct sockaddr *,
 int	 rtrequest(int, struct sockaddr *,
 			struct sockaddr *, struct sockaddr *, int,
 			struct rtentry **, u_int);
-int	 rtrequest1(int, struct rt_addrinfo *, struct rtentry **, u_int);
+int	 rtrequest1(int, struct rt_addrinfo *, u_int8_t, struct rtentry **,
+	     u_int);
 void	 rt_if_remove(struct ifnet *);
 
 struct radix_node_head	*rt_gettable(sa_family_t, u_int);
diff --git a/sys/net/rtsock.c b/sys/net/rtsock.c
index aadd17ff1f2..72d8b07446f 100644
--- a/sys/net/rtsock.c
+++ b/sys/net/rtsock.c
@@ -1,4 +1,4 @@
-/*	$OpenBSD: rtsock.c,v 1.69 2008/04/23 10:55:14 norby Exp $	*/
+/*	$OpenBSD: rtsock.c,v 1.70 2008/05/07 05:14:21 claudio Exp $	*/
 /*	$NetBSD: rtsock.c,v 1.18 1996/03/29 00:32:10 cgd Exp $	*/
 
 /*
@@ -186,6 +186,7 @@ route_output(struct mbuf *m, ...)
 	const char		*label;
 	va_list			 ap;
 	u_int			 tableid;
+	u_int8_t		 prio;
 
 	va_start(ap, m);
 	so = va_arg(ap, struct socket *);
@@ -262,6 +263,20 @@ route_output(struct mbuf *m, ...)
 		}
 	}
 
+	if (rtm->rtm_priority != 0) {
+		if (rtm->rtm_priority > RTP_MAX) {
+			dst = 0;
+			error = EINVAL;
+			goto flush;
+		}
+		prio = rtm->rtm_priority;
+	} else if (rtm->rtm_type == RTM_DELETE)
+		prio = RTP_ANY;
+	else if (rtm->rtm_flags & RTF_STATIC)
+		prio = RTP_STATIC;
+	else
+		prio = RTP_DEFAULT;
+
 	bzero(&info, sizeof(info));
 	info.rti_addrs = rtm->rtm_addrs;
 	rt_xaddrs(rtm->rtm_hdrlen + (caddr_t)rtm, len + (caddr_t)rtm, &info);
@@ -300,7 +315,8 @@ route_output(struct mbuf *m, ...)
 			error = EINVAL;
 			goto flush;
 		}
-		error = rtrequest1(rtm->rtm_type, &info, &saved_nrt, tableid);
+		error = rtrequest1(rtm->rtm_type, &info, prio, &saved_nrt,
+		    tableid);
 		if (error == 0 && saved_nrt) {
 			rt_setmetrics(rtm->rtm_inits, &rtm->rtm_rmx,
 			    &saved_nrt->rt_rmx);
@@ -310,7 +326,8 @@ route_output(struct mbuf *m, ...)
 		}
 		break;
 	case RTM_DELETE:
-		error = rtrequest1(rtm->rtm_type, &info, &saved_nrt, tableid);
+		error = rtrequest1(rtm->rtm_type, &info, prio, &saved_nrt,
+		    tableid);
 		if (error == 0) {
 			(rt = saved_nrt)->rt_refcnt++;
 			goto report;
@@ -339,8 +356,9 @@ route_output(struct mbuf *m, ...)
 		 * (no need to call rt_mpath_matchgate if gate == NULL)
 		 */
 		if (rn_mpath_capable(rnh) &&
-		    (rtm->rtm_type != RTM_GET || gate)) {
-			rt = rt_mpath_matchgate(rt, gate);
+		    (rtm->rtm_type != RTM_GET || gate ||
+		    rtm->rtm_priority != 0)) {
+			rt = rt_mpath_matchgate(rt, gate, prio);
 			rn = (struct radix_node *)rt;
 			if (!rt) {
 				error = ESRCH;
@@ -412,6 +430,7 @@ report:
 			    NULL);
 			rtm->rtm_flags = rt->rt_flags;
 			rtm->rtm_use = 0;
+			rtm->rtm_priority = rt->rt_priority;
 			rt_getmetrics(&rt->rt_rmx, &rtm->rtm_rmx);
 			rtm->rtm_addrs = info.rti_addrs;
 			break;
@@ -535,6 +554,7 @@ rt_setmetrics(u_long which, struct rt_metrics *in, struct rt_kmetrics *out)
 		out->rmx_mtu = in->rmx_mtu;
 	if (which & RTV_EXPIRE)
 		out->rmx_expire = in->rmx_expire;
+	/* RTV_PRIORITY handled befor */
 }
 
 void
@@ -916,6 +936,7 @@ sysctl_dumpentry(struct radix_node *rn, void *v)
 		struct rt_msghdr *rtm = (struct rt_msghdr *)w->w_tmem;
 
 		rtm->rtm_flags = rt->rt_flags;
+		rtm->rtm_priority = rt->rt_priority;
 		rt_getmetrics(&rt->rt_rmx, &rtm->rtm_rmx);
 		rtm->rtm_rmx.rmx_refcnt = rt->rt_refcnt;
 		rtm->rtm_index = rt->rt_ifp->if_index;
diff --git a/sys/netinet/in_pcb.c b/sys/netinet/in_pcb.c
index 88acbfa09ed..ae5c16d9994 100644
--- a/sys/netinet/in_pcb.c
+++ b/sys/netinet/in_pcb.c
@@ -1,4 +1,4 @@
-/*	$OpenBSD: in_pcb.c,v 1.93 2008/04/18 06:42:20 djm Exp $	*/
+/*	$OpenBSD: in_pcb.c,v 1.94 2008/05/07 05:14:21 claudio Exp $	*/
 /*	$NetBSD: in_pcb.c,v 1.25 1996/02/13 23:41:53 christos Exp $	*/
 
 /*
@@ -634,7 +634,7 @@ in_losing(inp)
 		info.rti_info[RTAX_NETMASK] = rt_mask(rt);
 		rt_missmsg(RTM_LOSING, &info, rt->rt_flags, rt->rt_ifp, 0, 0);
 		if (rt->rt_flags & RTF_DYNAMIC)
-			(void)rtrequest1(RTM_DELETE, &info,
+			(void)rtrequest1(RTM_DELETE, &info, rt->rt_priority,
 				(struct rtentry **)0, 0);
 		/*
 		 * A new route can be allocated
diff --git a/sys/netinet/ip_carp.c b/sys/netinet/ip_carp.c
index 72f2b858ff1..293ddc65718 100644
--- a/sys/netinet/ip_carp.c
+++ b/sys/netinet/ip_carp.c
@@ -1,4 +1,4 @@
-/*	$OpenBSD: ip_carp.c,v 1.163 2008/05/06 15:12:00 mcbride Exp $	*/
+/*	$OpenBSD: ip_carp.c,v 1.164 2008/05/07 05:14:21 claudio Exp $	*/
 
 /*
  * Copyright (c) 2002 Michael Shalayeff. All rights reserved.
@@ -420,11 +420,11 @@ carp_setroute(struct carp_softc *sc, int cmd)
 			bzero(&info, sizeof(info));
 			info.rti_info[RTAX_DST] = ifa->ifa_addr;
 			info.rti_flags = RTF_HOST;
-			error = rtrequest1(RTM_DELETE, &info, NULL, 0);
+			error = rtrequest1(RTM_DELETE, &info, RTP_CONNECTED,
+			    NULL, 0);
 			rt_missmsg(RTM_DELETE, &info, info.rti_flags, NULL,
 			    error, 0);
 
-
 			/* Check for our address on another interface */
 			/* XXX cries for proper API */
 			rnh = rt_gettable(ifa->ifa_addr->sa_family, 0);
@@ -461,7 +461,8 @@ carp_setroute(struct carp_softc *sc, int cmd)
 					info.rti_info[RTAX_DST] = ifa->ifa_addr;
 					info.rti_info[RTAX_GATEWAY] = ifa->ifa_addr;
 					info.rti_flags = RTF_UP | RTF_HOST;
-					error = rtrequest1(RTM_ADD, &info, NULL, 0);
+					error = rtrequest1(RTM_ADD, &info,
+					    RTP_CONNECTED, NULL, 0);
 					rt_missmsg(RTM_ADD, &info, info.rti_flags,
 					    &sc->sc_if, error, 0);
 				}
@@ -471,7 +472,7 @@ carp_setroute(struct carp_softc *sc, int cmd)
 						bzero(&info, sizeof(info));
 						info.rti_info[RTAX_DST] = &sa;
 						info.rti_info[RTAX_NETMASK] = ifa->ifa_netmask;
-						error = rtrequest1(RTM_DELETE, &info, NULL, 0);
+						error = rtrequest1(RTM_DELETE, &info, RTP_CONNECTED, NULL, 0);
 						rt_missmsg(RTM_DELETE, &info, info.rti_flags, NULL,
 						    error, 0);
 					}
@@ -485,7 +486,7 @@ carp_setroute(struct carp_softc *sc, int cmd)
 					info.rti_info[RTAX_NETMASK] = ifa->ifa_netmask;
 					info.rti_info[RTAX_LABEL] =
 					    (struct sockaddr *)&sa_rl;
-					error = rtrequest1(RTM_ADD, &info, NULL, 0);
+					error = rtrequest1(RTM_ADD, &info, RTP_CONNECTED, NULL, 0);
 					if (error == 0)
 						ifa->ifa_flags |= IFA_ROUTE;
 					rt_missmsg(RTM_ADD, &info, info.rti_flags,
diff --git a/sys/netinet6/in6.c b/sys/netinet6/in6.c
index 94f00a193a5..27015a5ce96 100644
--- a/sys/netinet6/in6.c
+++ b/sys/netinet6/in6.c
@@ -1,4 +1,4 @@
-/*	$OpenBSD: in6.c,v 1.73 2007/12/09 21:24:58 hshoexer Exp $	*/
+/*	$OpenBSD: in6.c,v 1.74 2008/05/07 05:14:21 claudio Exp $	*/
 /*	$KAME: in6.c,v 1.372 2004/06/14 08:14:21 itojun Exp $	*/
 
 /*
@@ -1105,7 +1105,8 @@ in6_update_ifa(ifp, ifra, ia)
 			    (struct sockaddr *)&ia->ia_addr;
 			/* XXX: we need RTF_CLONING to fake nd6_rtrequest */
 			info.rti_flags = RTF_UP | RTF_CLONING;
-			error = rtrequest1(RTM_ADD, &info, NULL, 0);
+			error = rtrequest1(RTM_ADD, &info, RTP_CONNECTED, NULL,
+			    0);
 			if (error)
 				goto cleanup;
 		} else {
@@ -1173,7 +1174,8 @@ in6_update_ifa(ifp, ifra, ia)
 			info.rti_info[RTAX_IFA] =
 			    (struct sockaddr *)&ia->ia_addr;
 			info.rti_flags = RTF_UP | RTF_CLONING;
-			error = rtrequest1(RTM_ADD, &info, NULL, 0);
+			error = rtrequest1(RTM_ADD, &info, RTP_CONNECTED,
+			    NULL, 0);
 			if (error)
 				goto cleanup;
 		} else {