Big refactoring of the radix code (mainly rn_addroute but also part

of rn_delete was changed). The mpath code gets a much better
rn_mpath_next() function that allows looping through the dupedkey list
based on prio, any or only active routes. This solves the issues seen
with failed deletes of down routes.
Commit this now so that it gets tested. Both sthen@ and blambert@ agree.

6 files changed, 651 insertions, 504 deletions

diff --git a/sys/net/radix.c b/sys/net/radix.c
index 6cc35c6ade9..9830ff2112c 100644
--- a/sys/net/radix.c
+++ b/sys/net/radix.c
@@ -1,4 +1,4 @@
-/*	$OpenBSD: radix.c,v 1.39 2014/01/22 10:17:59 claudio Exp $	*/
+/*	$OpenBSD: radix.c,v 1.40 2014/05/27 19:38:15 claudio Exp $	*/
 /*	$NetBSD: radix.c,v 1.20 2003/08/07 16:32:56 agc Exp $	*/
 
 /*
@@ -71,6 +71,13 @@ struct radix_node *rn_newpair(void *, int, struct radix_node[2]);
 
 static inline struct radix_node *rn_search(void *, struct radix_node *);
 struct radix_node *rn_search_m(void *, struct radix_node *, void *);
+int rn_add_dupedkey(struct radix_node *, struct radix_node_head *,
+    struct radix_node [2], u_int8_t);
+void rn_fixup_nodes(struct radix_node *);
+static inline struct radix_node *rn_lift_node(struct radix_node *);
+void rn_add_radix_mask(struct radix_node *, int);
+int rn_del_radix_mask(struct radix_node *);
+static inline void rn_swap_nodes(struct radix_node *, struct radix_node *);
 
 /*
  * The data structure for the keys is a radix tree with one way
@@ -167,6 +174,7 @@ rn_refines(void *m_arg, void *n_arg)
 	return (!masks_are_equal);
 }
 
+/* return a perfect match if m_arg is set, else do a regular rn_match */
 struct radix_node *
 rn_lookup(void *v_arg, void *m_arg, struct radix_node_head *head)
 {
@@ -201,10 +209,15 @@ rn_satisfies_leaf(char *trial, struct radix_node *leaf, int skip)
 		cp3 = rn_ones;
 	else
 		length = min(length, *(u_char *)cp3);
-	cplim = cp + length; cp3 += skip; cp2 += skip;
-	for (cp += skip; cp < cplim; cp++, cp2++, cp3++)
+	cplim = cp + length;
+	cp += skip;
+	cp2 += skip;
+	cp3 += skip;
+	while (cp < cplim) {
 		if ((*cp ^ *cp2) & *cp3)
 			return 0;
+		cp++, cp2++, cp3++;
+	}
 	return 1;
 }
 
@@ -395,7 +408,7 @@ rn_addmask(void *n_arg, int search, int skip)
 	if (skip == 0)
 		skip = 1;
 	if (mlen <= skip)
-		return (mask_rnhead->rnh_nodes);
+		return (mask_rnhead->rnh_nodes);	/* rn_zero root node */
 	if (skip > 1)
 		memcpy(addmask_key + 1, rn_ones + 1, skip - 1);
 	if ((m0 = mlen) > skip)
@@ -495,388 +508,556 @@ rn_new_radix_mask(struct radix_node *tt, struct radix_mask *next)
 	return m;
 }
 
-struct radix_node *
-rn_addroute(void *v_arg, void *n_arg, struct radix_node_head *head,
-    struct radix_node treenodes[2], u_int8_t prio)
+/*
+ * Find the point where the rn_mklist needs to be changed.
+ */
+static inline struct radix_node *
+rn_lift_node(struct radix_node *t)
 {
-	caddr_t v = v_arg;
-	caddr_t netmask = n_arg;
-	struct radix_node *top = head->rnh_treetop;
-	struct radix_node *t, *tt, *tm = NULL, *x;
-	struct radix_node *saved_tt;
-	short b = 0, b_leaf = 0;
-	int keyduplicated, prioinv = -1;
-	caddr_t mmask;
-	struct radix_mask *m, **mp;
-
-	/*
-	 * In dealing with non-contiguous masks, there may be
-	 * many different routes which have the same mask.
-	 * We will find it useful to have a unique pointer to
-	 * the mask to speed avoiding duplicate references at
-	 * nodes and possibly save time in calculating indices.
-	 */
-	if (netmask)  {
-		if ((tm = rn_addmask(netmask, 0, top->rn_off)) == 0)
-			return (0);
-		b_leaf = tm->rn_b;
-		b = -1 - tm->rn_b;
-		netmask = tm->rn_key;
-	}
+	struct radix_node *x = t;
+	int b = -1 - t->rn_b;
 
-	saved_tt = tt = rn_insert(v, head, &keyduplicated, treenodes);
-
-	/*
-	 * Deal with duplicated keys: attach node to previous instance
-	 */
-	if (keyduplicated) {
-		for (t = tt; tt; t = tt, tt = tt->rn_dupedkey) {
-#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.
-				 */
-				prioinv = 0;
-				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;
-				}
+	/* rewind possible dupedkey list to head */
+	while (t->rn_b < 0)
+		t = t->rn_p;
 
-				mid = rn_mpath_active_count(tt) / 2;
-				do {
-					t = tt;
-					tt = rn_mpath_next(tt, 0);
-				} while (tt && --mid > 0);
-				break;
-			}
-#endif
-			if (tt->rn_mask == netmask)
-				return (0);
-			if (netmask == 0 ||
-			    (tt->rn_mask &&
-			     ((b_leaf < tt->rn_b) || /* index(netmask) > node */
-			       rn_refines(netmask, tt->rn_mask) ||
-			       rn_lexobetter(netmask, tt->rn_mask))))
-				break;
-		}
-		/*
-		 * If the mask is not duplicated, we wouldn't
-		 * find it among possible duplicate key entries
-		 * anyway, so the above test doesn't hurt.
-		 *
-		 * We sort the masks for a duplicated key the same way as
-		 * in a masklist -- most specific to least specific.
-		 * This may require the unfortunate nuisance of relocating
-		 * the head of the list.
-		 *
-		 * We also reverse, or doubly link the list through the
-		 * parent pointer.
-		 */
-		if (tt == saved_tt && prioinv) {
-			struct	radix_node *xx;
-			/* link in at head of list */
-			(tt = treenodes)->rn_dupedkey = t;
-			tt->rn_flags = t->rn_flags;
-			tt->rn_p = xx = t->rn_p;
-			t->rn_p = tt;
-			if (xx->rn_l == t)
-				xx->rn_l = tt;
-			else
-				xx->rn_r = tt;
-			saved_tt = tt;
-		} else if (prioinv == 1) {
-			(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;
-			tt->rn_p = t;
-			if (tt->rn_dupedkey)
-				tt->rn_dupedkey->rn_p = tt;
-		}
-		tt->rn_key = (caddr_t) v;
-		tt->rn_b = -1;
-		tt->rn_flags = RNF_ACTIVE;
-	}
+	/* can't lift node above head of dupedkey list, give up */
+	if (b > t->rn_b)
+		return (NULL);
 
-	/*
-	 * Put mask in tree.
-	 */
-	if (netmask) {
-		tt->rn_mask = netmask;
-		tt->rn_b = tm->rn_b;
-		tt->rn_flags |= tm->rn_flags & RNF_NORMAL;
-	}
-	t = saved_tt->rn_p;
-	if (keyduplicated)
-		goto on2;
-	b_leaf = -1 - t->rn_b;
-	if (t->rn_r == saved_tt)
-		x = t->rn_l;
-	else
-		x = t->rn_r;
-	/* Promote general routes from below */
-	if (x->rn_b < 0) {
-	    struct	radix_node *xx = NULL;
-	    for (mp = &t->rn_mklist; x; xx = x, x = x->rn_dupedkey) {
-		if (xx && xx->rn_mklist && xx->rn_mask == x->rn_mask &&
-		    x->rn_mklist == 0) {
-			/* multipath route, bump refcount on first mklist */
-			x->rn_mklist = xx->rn_mklist;
-			x->rn_mklist->rm_refs++;
-		}
-		if (x->rn_mask && (x->rn_b >= b_leaf) && x->rn_mklist == 0) {
-			*mp = m = rn_new_radix_mask(x, 0);
-			if (m)
-				mp = &m->rm_mklist;
-		}
-	    }
-	} else if (x->rn_mklist) {
-		/*
-		 * Skip over masks whose index is > that of new node
-		 */
-		for (mp = &x->rn_mklist; (m = *mp); mp = &m->rm_mklist)
-			if (m->rm_b >= b_leaf)
-				break;
-		t->rn_mklist = m;
-		*mp = 0;
-	}
-on2:
-	/* Add new route to highest possible ancestor's list */
-	if ((netmask == 0) || (b > t->rn_b ))
-		return tt; /* can't lift at all */
-	b_leaf = tt->rn_b;
 	do {
 		x = t;
 		t = t->rn_p;
-	} while (b <= t->rn_b && x != top);
+	} while (b <= t->rn_b && x != t);
+
+	return (x);
+}
+
+void
+rn_add_radix_mask(struct radix_node *tt, int keyduplicated)
+{
+	caddr_t netmask, mmask;
+	struct radix_node *x;
+	struct radix_mask *m, **mp;
+	int b_leaf = tt->rn_b;
+
+	/* Add new route to highest possible ancestor's list */
+	if (tt->rn_mask == NULL)
+		return; /* can't lift at all */
+	x = rn_lift_node(tt);
+	if (x == NULL)
+		return; /* didn't lift either */
+
 	/*
 	 * Search through routes associated with node to
 	 * insert new route according to index.
 	 * Need same criteria as when sorting dupedkeys to avoid
 	 * double loop on deletion.
 	 */
+	netmask = tt->rn_mask;
 	for (mp = &x->rn_mklist; (m = *mp); mp = &m->rm_mklist) {
 		if (m->rm_b < b_leaf)
 			continue;
 		if (m->rm_b > b_leaf)
 			break;
 		if (m->rm_flags & RNF_NORMAL) {
-			mmask = m->rm_leaf->rn_mask;
 			if (keyduplicated) {
 				if (m->rm_leaf->rn_p == tt)
 					/* new route is better */
 					m->rm_leaf = tt;
 #ifdef DIAGNOSTIC
 				else {
-					for (t = m->rm_leaf; t;
-						t = t->rn_dupedkey)
+					struct radix_node *t;
+
+					for (t = m->rm_leaf;
+					    t && t->rn_mklist == m;
+					    t = t->rn_dupedkey)
 						if (t == tt)
 							break;
 					if (t == NULL) {
 						log(LOG_ERR, "Non-unique "
 						    "normal route on dupedkey, "
 						    "mask not entered\n");
-						return tt;
+						return;
 					}
 				}
 #endif
 				m->rm_refs++;
 				tt->rn_mklist = m;
-				return tt;
+				return;
 			} else if (tt->rn_flags & RNF_NORMAL) {
 				log(LOG_ERR, "Non-unique normal route,"
 				    " mask not entered\n");
-				return tt;
+				return;
 			}
+			mmask = m->rm_leaf->rn_mask;
 		} else
 			mmask = m->rm_mask;
 		if (mmask == netmask) {
 			m->rm_refs++;
 			tt->rn_mklist = m;
-			return tt;
+			return;
 		}
 		if (rn_refines(netmask, mmask) || rn_lexobetter(netmask, mmask))
 			break;
 	}
 	*mp = rn_new_radix_mask(tt, *mp);
-	return tt;
+}
+
+int
+rn_add_dupedkey(struct radix_node *saved_tt, struct radix_node_head *head,
+    struct radix_node *tt, u_int8_t prio)
+{
+	caddr_t netmask = tt->rn_mask;
+	struct radix_node *x = saved_tt, *xp;
+#ifndef SMALL_KERNEL
+	struct radix_node *dupedkey_tt = NULL;
+#endif
+	int before = -1;
+	int b_leaf = 0;
+
+	if (netmask)
+		b_leaf = tt->rn_b;
+
+	for (xp = x; x; xp = x, x = x->rn_dupedkey) {
+#ifndef SMALL_KERNEL
+		/* permit multipath, if enabled for the family */
+		if (rn_mpath_capable(head) && netmask == x->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.
+			 */
+			before = 0;
+
+			dupedkey_tt = x;
+			x = rn_mpath_prio(x, prio);
+			if (((struct rtentry *)x)->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 *)x)->rt_priority > prio)
+					before = 1;
+				xp = x;
+				break;
+			}
+
+			mid = rn_mpath_active_count(x) / 2;
+			do {
+				xp = x;
+				x = rn_mpath_next(x, RMP_MODE_BYPRIO);
+			} while (x && --mid > 0);
+			break;
+		}
+#endif
+		if (x->rn_mask == netmask)
+			return (-1);
+		if (netmask == NULL ||
+		    (x->rn_mask &&
+		     ((b_leaf < x->rn_b) || /* index(netmask) > node */
+		       rn_refines(netmask, x->rn_mask) ||
+		       rn_lexobetter(netmask, x->rn_mask))))
+			break;
+	}
+	/*
+	 * If the mask is not duplicated, we wouldn't
+	 * find it among possible duplicate key entries
+	 * anyway, so the above test doesn't hurt.
+	 *
+	 * We sort the masks for a duplicated key the same way as
+	 * in a masklist -- most specific to least specific.
+	 * This may require the unfortunate nuisance of relocating
+	 * the head of the list.
+	 *
+	 * We also reverse, or doubly link the list through the
+	 * parent pointer.
+	 */
+
+	if ((x == saved_tt && before) || before == 1)
+		before = 1;
+	else
+		before = 0;
+	rn_link_dupedkey(tt, xp, before);
+
+
+#ifndef SMALL_KERNEL
+	/* adjust the flags of the possible multipath chain */
+	if (!dupedkey_tt)
+		dupedkey_tt = tt;
+	if (rn_mpath_capable(head))
+		rn_mpath_adj_mpflag(dupedkey_tt, prio);
+#endif
+	return (0);
+}
+
+/*
+ * Insert tt after x or in place of x if before is true.
+ */
+void
+rn_link_dupedkey(struct radix_node *tt, struct radix_node *x, int before)
+{
+	if (before) {
+		if (x->rn_p->rn_b > 0) {
+			/* link in at head of list */
+			tt->rn_dupedkey = x;
+			tt->rn_flags = x->rn_flags;
+			tt->rn_p = x->rn_p;
+			x->rn_p = tt;
+			if (tt->rn_p->rn_l == x)
+				tt->rn_p->rn_l = tt;
+			else
+				tt->rn_p->rn_r = tt;
+		} else {
+			tt->rn_dupedkey = x;
+			x->rn_p->rn_dupedkey = tt;
+			tt->rn_p = x->rn_p;
+			x->rn_p = tt;
+		}
+	} else {
+		tt->rn_dupedkey = x->rn_dupedkey;
+		x->rn_dupedkey = tt;
+		tt->rn_p = x;
+		if (tt->rn_dupedkey)
+			tt->rn_dupedkey->rn_p = tt;
+	}
+}
+
+/*
+ * This function ensures that routes are properly promoted upwards.
+ * It adjusts the rn_mklist of the parent node to make sure overlapping
+ * routes can be found.
+ *
+ * There are two cases:
+ * - leaf nodes with possible rn_dupedkey list
+ * - internal nodes with maybe their own mklist
+ * If the mask of the route is bigger than the current branch bit then
+ * a rn_mklist entrie needs to be made.
+ */
+void
+rn_fixup_nodes(struct radix_node *tt)
+{
+	struct radix_node *tp, *x;
+	struct radix_mask *m, **mp;
+	int b_leaf;
+
+	tp = tt->rn_p;
+	if (tp->rn_r == tt)
+		x = tp->rn_l;
+	else
+		x = tp->rn_r;
+
+	b_leaf = -1 - tp->rn_b;
+	if (x->rn_b < 0) {	/* x is a leaf node */
+		struct	radix_node *xx = NULL;
+
+		for (mp = &tp->rn_mklist; x; xx = x, x = x->rn_dupedkey) {
+			if (xx && xx->rn_mklist && xx->rn_mask == x->rn_mask &&
+			    x->rn_mklist == 0) {
+				/* multipath route */
+				x->rn_mklist = xx->rn_mklist;
+				x->rn_mklist->rm_refs++;
+			}
+			if (x->rn_mask && (x->rn_b >= b_leaf) &&
+			    x->rn_mklist == 0) {
+				*mp = m = rn_new_radix_mask(x, 0);
+				if (m)
+					mp = &m->rm_mklist;
+			}
+		}
+	} else if (x->rn_mklist) {	/* x is an internal node */
+		/*
+		 * Skip over masks whose index is > that of new node
+		 */
+		for (mp = &x->rn_mklist; (m = *mp); mp = &m->rm_mklist)
+			if (m->rm_b >= b_leaf)
+				break;
+		tp->rn_mklist = m;
+		*mp = 0;
+	}
 }
 
 struct radix_node *
-rn_delete(void *v_arg, void *netmask_arg, struct radix_node_head *head,
-    struct radix_node *rn)
+rn_addroute(void *v_arg, void *n_arg, struct radix_node_head *head,
+    struct radix_node treenodes[2], u_int8_t prio)
 {
 	caddr_t v = v_arg;
-	caddr_t netmask = netmask_arg;
 	struct radix_node *top = head->rnh_treetop;
-	struct radix_node *t, *p, *tm, *x, *tt;
-	struct radix_mask *m, *saved_m, **mp;
-	struct radix_node *dupedkey, *saved_tt;
-	int off = top->rn_off;
-	int b, vlen;
+	struct radix_node *tt, *saved_tt, *tm = NULL;
+	int keyduplicated;
 
-	vlen =  *(u_char *)v;
-	tt = rn_search(v, top);
-	saved_tt = tt;
-	if (memcmp(v + off, tt->rn_key + off, vlen - off))
-		return (0);
 	/*
-	 * Delete our route from mask lists.
+	 * In dealing with non-contiguous masks, there may be
+	 * many different routes which have the same mask.
+	 * We will find it useful to have a unique pointer to
+	 * the mask to speed avoiding duplicate references at
+	 * nodes and possibly save time in calculating indices.
 	 */
-	if (netmask) {
-		if ((tm = rn_addmask(netmask, 1, off)) == NULL)
+	if (n_arg)  {
+		if ((tm = rn_addmask(n_arg, 0, top->rn_off)) == 0)
 			return (0);
-		netmask = tm->rn_key;
-		while (tt->rn_mask != netmask)
-			if ((tt = tt->rn_dupedkey) == NULL)
-				return (0);
 	}
-#ifndef SMALL_KERNEL
-	if (rn) {
-		while (tt != rn)
-			if ((tt = tt->rn_dupedkey) == NULL)
-				return (0);
+
+	tt = rn_insert(v, head, &keyduplicated, treenodes);
+
+	if (keyduplicated) {
+		saved_tt = tt;
+		tt = treenodes;
+
+		tt->rn_key = v_arg;
+		tt->rn_b = -1;
+		tt->rn_flags = RNF_ACTIVE;
 	}
+
+	/* Put mask into the node. */
+	if (tm) {
+		tt->rn_mask = tm->rn_key;
+		tt->rn_b = tm->rn_b;
+		tt->rn_flags |= tm->rn_flags & RNF_NORMAL;
+	}
+
+	/* Either insert into dupedkey list or as a leaf node.  */
+	if (keyduplicated) {
+		if (rn_add_dupedkey(saved_tt, head, tt, prio))
+			return (NULL);
+	} else {
+		rn_fixup_nodes(tt);
+#ifndef SMALL_KERNEL
+		if (rn_mpath_capable(head))
+			rn_mpath_adj_mpflag(tt, prio);
 #endif
-	if (tt->rn_mask == NULL || (saved_m = m = tt->rn_mklist) == NULL)
-		goto on1;
+	}
+
+	/* finally insert a radix_mask element if needed */
+	rn_add_radix_mask(tt, keyduplicated);
+	return (tt);
+}
+
+/*
+ * Cleanup mask list, tt points to route that needs to be cleaned
+ */
+int
+rn_del_radix_mask(struct radix_node *tt)
+{
+	struct radix_node *x;
+	struct radix_mask *m, *saved_m, **mp;
+
+	/*
+	 * Cleanup mask list from possible references to this route.
+	 */
+	saved_m = m = tt->rn_mklist;
+	if (tt->rn_mask == NULL || m == NULL)
+		return (0);
+
 	if (tt->rn_flags & RNF_NORMAL) {
 		if (m->rm_leaf != tt && m->rm_refs == 0) {
 			log(LOG_ERR, "rn_delete: inconsistent normal "
 			    "annotation\n");
-			return (0);
+			return (-1);
 		}
 		if (m->rm_leaf != tt) {
 			if (--m->rm_refs >= 0)
-				goto on1;
+				return (0);
+			else 
+				log(LOG_ERR, "rn_delete: "
+				    "inconsistent mklist refcount\n");
 		}
-		/* tt is currently the head of the possible multipath chain */
+		/*
+		 * If we end up here tt should be m->rm_leaf and therefor
+		 * tt should be the head of a multipath chain.
+		 * If this is not the case the table is no longer consistent.
+		 */
 		if (m->rm_refs > 0) {
 			if (tt->rn_dupedkey == NULL ||
 			    tt->rn_dupedkey->rn_mklist != m) {
 				log(LOG_ERR, "rn_delete: inconsistent "
 				    "dupedkey list\n");
-				return (0);
+				return (-1);
 			}
 			m->rm_leaf = tt->rn_dupedkey;
 			--m->rm_refs;
-			goto on1;
+			return (0);
 		}
 		/* else tt is last and only route */
 	} else {
 		if (m->rm_mask != tt->rn_mask) {
 			log(LOG_ERR, "rn_delete: inconsistent annotation\n");
-			goto on1;
+			return (0);
 		}
 		if (--m->rm_refs >= 0)
-			goto on1;
+			return (0);
 	}
-	b = -1 - tt->rn_b;
-	t = saved_tt->rn_p;
-	if (b > t->rn_b)
-		goto on1; /* Wasn't lifted at all */
-	do {
-		x = t;
-		t = t->rn_p;
-	} while (b <= t->rn_b && x != top);
+
+	/*
+	 * No other references hold to the radix_mask remove it from
+	 * the tree.
+	 */
+	x = rn_lift_node(tt);
+	if (x == NULL)
+		return (0);	/* Wasn't lifted at all */
+
+	/* Finally eliminate the radix_mask from the tree */
 	for (mp = &x->rn_mklist; (m = *mp); mp = &m->rm_mklist)
 		if (m == saved_m) {
 			*mp = m->rm_mklist;
 			pool_put(&rtmask_pool, m);
 			break;
 		}
+
 	if (m == NULL) {
 		log(LOG_ERR, "rn_delete: couldn't find our annotation\n");
 		if (tt->rn_flags & RNF_NORMAL)
-			return (0); /* Dangling ref to us */
+			return (-1); /* Dangling ref to us */
 	}
-on1:
+
+	return (0);
+}
+
+/* swap two internal nodes and fixup the parent and child pointers */
+static inline void
+rn_swap_nodes(struct radix_node *from, struct radix_node *to)
+{
+	*to = *from;
+	if (from->rn_p->rn_l == from)
+		from->rn_p->rn_l = to;
+	else
+		from->rn_p->rn_r = to;
+
+	to->rn_l->rn_p = to;
+	to->rn_r->rn_p = to;
+}
+
+struct radix_node *
+rn_delete(void *v_arg, void *n_arg, struct radix_node_head *head,
+    struct radix_node *rn)
+{
+	caddr_t v = v_arg;
+	caddr_t netmask = n_arg;
+	struct radix_node *top = head->rnh_treetop;
+	struct radix_node *tt, *tp, *pp, *x;
+	struct radix_node *dupedkey_tt, *saved_tt;
+	int off = top->rn_off;
+	int vlen;
+
+	vlen =  *(u_char *)v;
+
 	/*
-	 * Eliminate us from tree
+	 * Implement a lookup similar to rn_lookup but we need to save
+	 * the radix leaf node (where th rn_dupedkey list starts) so
+	 * it is not possible to use rn_lookup.
 	 */
-	if (tt->rn_flags & RNF_ROOT)
+	tt = rn_search(v, top);
+	/* make sure the key is a perfect match */
+	if (memcmp(v + off, tt->rn_key + off, vlen - off))
 		return (0);
-	t = tt->rn_p;
-	dupedkey = saved_tt->rn_dupedkey;
-	if (dupedkey) {
-		/*
-		 * Here, tt is the deletion target, and
-		 * saved_tt is the head of the dupedkey chain.
-		 */
+
+	/*
+	 * Here, tt is the deletion target, and
+	 * saved_tt is the head of the dupedkey chain.
+	 * dupedkey_tt will point to the start of the multipath chain.
+	 */
+	saved_tt = tt;
+
+	/*
+	 * make tt point to the start of the rn_dupedkey list of multipath
+	 * routes.
+	 */
+	if (netmask) {
+		struct radix_node *tm;
+
+		if ((tm = rn_addmask(netmask, 1, off)) == NULL)
+			return (0);
+		netmask = tm->rn_key;
+		while (tt->rn_mask != netmask)
+			if ((tt = tt->rn_dupedkey) == NULL)
+				return (0);
+	}
+
+	KASSERT((tt->rn_flags & RNF_ROOT) == 0);
+
+	/* save start of multi path chain for later use */
+	dupedkey_tt = tt;
+
+#ifndef SMALL_KERNEL
+	/* if we got a hint use the hint from now on */
+	if (rn) 
+		tt = rn;
+#endif
+
+	/* remove possible radix_mask */
+	if (rn_del_radix_mask(tt))
+		return (0);
+
+	/*
+	 * Finally eliminate us from tree
+	 */
+	tp = tt->rn_p;
+	if (saved_tt->rn_dupedkey) {
 		if (tt == saved_tt) {
-			x = dupedkey;
-			x->rn_p = t;
-			if (t->rn_l == tt)
-				t->rn_l = x;
+			x = saved_tt->rn_dupedkey;
+			x->rn_p = tp;
+			if (tp->rn_l == tt)
+				tp->rn_l = x;
 			else
-				t->rn_r = x;
+				tp->rn_r = x;
 		} else {
 			x = saved_tt;
-			t->rn_dupedkey = tt->rn_dupedkey;
+			tp->rn_dupedkey = tt->rn_dupedkey;
 			if (tt->rn_dupedkey)
-				tt->rn_dupedkey->rn_p = t;
-		}
-		t = tt + 1;
-		if  (t->rn_flags & RNF_ACTIVE) {
-			*++x = *t;
-			p = t->rn_p;
-			if (p->rn_l == t)
-				p->rn_l = x;
-			else
-				p->rn_r = x;
-			x->rn_l->rn_p = x;
-			x->rn_r->rn_p = x;
+				tt->rn_dupedkey->rn_p = tp;
 		}
+
+		/*
+		 * We may be holding an active internal node in the tree.
+		 */
+		if  (tt[1].rn_flags & RNF_ACTIVE)
+			rn_swap_nodes(&tt[1], &x[1]);
+
+#ifndef SMALL_KERNEL
+		/* adjust the flags of the multipath chain */
+		if (rn_mpath_capable(head))
+			rn_mpath_adj_mpflag(dupedkey_tt,
+			    ((struct rtentry *)tt)->rt_priority);
+#endif
+		/* over and out */
 		goto out;
 	}
-	if (t->rn_l == tt)
-		x = t->rn_r;
+
+	/* non-rn_dupedkey case, remove tt and tp node from the tree */
+	if (tp->rn_l == tt)
+		x = tp->rn_r;
 	else
-		x = t->rn_l;
-	p = t->rn_p;
-	if (p->rn_r == t)
-		p->rn_r = x;
+		x = tp->rn_l;
+	pp = tp->rn_p;
+	if (pp->rn_r == tp)
+		pp->rn_r = x;
 	else
-		p->rn_l = x;
-	x->rn_p = p;
+		pp->rn_l = x;
+	x->rn_p = pp;
+
 	/*
-	 * Demote routes attached to us.
+	 * Demote routes attached to us (actually on the internal parent node).
 	 */
-	if (t->rn_mklist) {
+	if (tp->rn_mklist) {
+		struct radix_mask *m, **mp;
 		if (x->rn_b >= 0) {
 			for (mp = &x->rn_mklist; (m = *mp);)
 				mp = &m->rm_mklist;
-			*mp = t->rn_mklist;
+			*mp = tp->rn_mklist;
 		} else {
 			/* If there are any key,mask pairs in a sibling
 			   duped-key chain, some subset will appear sorted
 			   in the same order attached to our mklist */
-			for (m = t->rn_mklist; m && x; x = x->rn_dupedkey)
+			for (m = tp->rn_mklist; m && x; x = x->rn_dupedkey)
 				if (m == x->rn_mklist) {
 					struct radix_mask *mm = m->rm_mklist;
 					x->rn_mklist = 0;
@@ -896,22 +1077,18 @@ on1:
 				    "rn_delete: Orphaned Mask", m, x);
 		}
 	}
+
 	/*
 	 * We may be holding an active internal node in the tree.
+	 * If so swap our internal node (t) with the parent node (tp)
+	 * since that one was just removed from the tree.
 	 */
-	x = tt + 1;
-	if (t != x) {
-		*t = *x;
-		t->rn_l->rn_p = t;
-		t->rn_r->rn_p = t;
-		p = x->rn_p;
-		if (p->rn_l == x)
-			p->rn_l = t;
-		else
-			p->rn_r = t;
-	}
+	if (tp != &tt[1])
+		rn_swap_nodes(&tt[1], tp);
+
+	/* no rn_dupedkey list so no need to fixup multipath chains */
 out:
-	tt->rn_flags &= ~RNF_ACTIVE;
+	tt[0].rn_flags &= ~RNF_ACTIVE;
 	tt[1].rn_flags &= ~RNF_ACTIVE;
 	return (tt);
 }
diff --git a/sys/net/radix.h b/sys/net/radix.h
index f4474794ce1..cf8ff8a0108 100644
--- a/sys/net/radix.h
+++ b/sys/net/radix.h
@@ -1,4 +1,4 @@
-/*	$OpenBSD: radix.h,v 1.24 2014/01/22 10:17:59 claudio Exp $	*/
+/*	$OpenBSD: radix.h,v 1.25 2014/05/27 19:38:15 claudio Exp $	*/
 /*	$NetBSD: radix.h,v 1.8 1996/02/13 22:00:37 christos Exp $	*/
 
 /*
@@ -119,6 +119,8 @@ void	rn_init(void);
 int	rn_inithead(void **, int);
 int	rn_inithead0(struct radix_node_head *, int);
 int	rn_refines(void *, void *);
+void	rn_link_dupedkey(struct radix_node *, struct radix_node *, int);
+
 int	rn_walktree(struct radix_node_head *,
 	    int (*)(struct radix_node *, void *, u_int), void *);
 
diff --git a/sys/net/radix_mpath.c b/sys/net/radix_mpath.c
index 171b6605abf..3766ca598ca 100644
--- a/sys/net/radix_mpath.c
+++ b/sys/net/radix_mpath.c
@@ -1,4 +1,4 @@
-/*	$OpenBSD: radix_mpath.c,v 1.22 2014/01/22 10:17:59 claudio Exp $	*/
+/*	$OpenBSD: radix_mpath.c,v 1.23 2014/05/27 19:38:15 claudio Exp $	*/
 /*	$KAME: radix_mpath.c,v 1.13 2002/10/28 21:05:59 itojun Exp $	*/
 
 /*
@@ -38,7 +38,6 @@
 #include <sys/systm.h>
 #include <sys/malloc.h>
 #include <sys/socket.h>
-#define	M_DONTWAIT M_NOWAIT
 #include <sys/domain.h>
 #include <sys/syslog.h>
 #include <net/radix.h>
@@ -68,156 +67,99 @@ rn_mpath_capable(struct radix_node_head *rnh)
 }
 
 struct radix_node *
-rn_mpath_next(struct radix_node *rn, int all)
+rn_mpath_next(struct radix_node *rn, int mode)
 {
 	struct radix_node	*next;
-	struct rtentry		*rt = (struct rtentry *)rn;
+	struct rtentry		*nt, *rt = (struct rtentry *)rn;
 
 	if (!rn->rn_dupedkey)
 		return NULL;
 	next = rn->rn_dupedkey;
-	if (rn->rn_mask == next->rn_mask && (all ||
-	    rt->rt_priority == ((struct rtentry *)next)->rt_priority))
-		return next;
-	else
+
+	if (rn->rn_mask != next->rn_mask)
 		return NULL;
+
+	switch (mode) {
+	case RMP_MODE_BYPRIO:
+		/* scan all of the list until we find a match */
+		while (next) {
+			if (rn->rn_mask != next->rn_mask)
+				return NULL;
+			nt = (struct rtentry *)next;
+			if ((rt->rt_priority & RTP_MASK) ==
+			    (nt->rt_priority & RTP_MASK))
+				return next;
+			rn = next;
+			next = next->rn_dupedkey;
+		}
+		return NULL;
+	case RMP_MODE_ACTIVE:
+		nt = (struct rtentry *)next;
+		if (rt->rt_priority != nt->rt_priority)
+			return NULL;
+		break;
+	case RMP_MODE_ALL:
+		break;
+	}
+	return next;
+}
+
+struct rtentry *
+rt_mpath_next(struct rtentry *rt)
+{
+	struct radix_node *rn = (struct radix_node *)rt;
+
+	return ((struct rtentry *)rn_mpath_next(rn, RMP_MODE_ACTIVE));
 }
 
+/*
+ * return first route matching prio or the node just before.
+ */
 struct radix_node *
 rn_mpath_prio(struct radix_node *rn, u_int8_t prio)
 {
-	struct radix_node	*prev = rn;
+	struct radix_node	*hit = 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);
+		return (hit);
 
+	do {
 		rt = (struct rtentry *)rn;
 		if (rt->rt_priority == prio)
+			/* perfect match */
 			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);
+
+		/* list is sorted remember last more prefered (smaller) entry */
+		if (rt->rt_priority < prio)
+			hit = rn;
+	} while ((rn = rn_mpath_next(rn, RMP_MODE_ALL)) != NULL);
+
+	return (hit);
 }
 
+/*
+ * Adjust the RTF_MPATH flag for the part of the rn_dupedkey chain
+ * that matches the prio.
+ */
 void
-rn_mpath_reprio(struct radix_node *rn, int newprio)
+rn_mpath_adj_mpflag(struct radix_node *rn, u_int8_t prio)
 {
-	struct radix_node	*prev = rn->rn_p;
-	struct radix_node	*next = rn->rn_dupedkey;
-	struct radix_node	*t, *tt, *saved_tt, *head;
-	struct rtentry		*rt = (struct rtentry *)rn;
-	int			 mid, oldprio, prioinv = 0;
-
-	oldprio = rt->rt_priority;
-	rt->rt_priority = newprio;
+	struct rtentry *rt = (struct rtentry *)rn;
 
-	/* same prio, no change needed */
-	if (oldprio == newprio)
+	prio &= RTP_MASK;
+	rt = rt_mpath_matchgate(rt, NULL, prio);
+	rn = (struct radix_node *)rt;
+	
+	if (!rn)
 		return;
-	if (rn_mpath_next(rn, 1) == NULL) {
-		/* no need to move node, route is alone */
-		if (prev->rn_mask != rn->rn_mask)
-			return;
-		/* ... or route is last and prio gets bigger */
-		if (oldprio < newprio)
-			return;
-	}
-
-	/* remove node from dupedkey list and reinsert at correct place */
-	if (prev->rn_dupedkey == rn) {
-		prev->rn_dupedkey = next;
-		if (next)
-			next->rn_p = prev;
-		else
-			next = prev;
-	} else {
-		if (next == NULL)
-			panic("next == NULL");
-		next->rn_p = prev;
-		if (prev->rn_l == rn)
-			prev->rn_l = next;
-		else
-			prev->rn_r = next;
-	}
-
-	/* re-insert rn at the right spot, so first rewind to the head */
-	for (tt = next; tt->rn_p->rn_dupedkey == tt; tt = tt->rn_p)
-		;
-	saved_tt = tt;
-
-	/*
-	 * Stolen from radix.c rn_addroute().
-	 * This is nasty code with a certain amount of magic and dragons.
-	 * t is the element where the re-priorized rn is inserted -- before
-	 * or after depending on prioinv. saved_tt points to the head of the
-	 * dupedkey chain and tt is a bit of a helper
-	 *
-	 * First we skip with tt to the start of the mpath group then we
-	 * search the right spot to enter our node.
-	 */
-	for (; tt; tt = tt->rn_dupedkey)
-		if (rn->rn_mask == tt->rn_mask)
-			break;
-	head = tt; /* store current head entry for rn_mklist check */
-
-	tt = rn_mpath_prio(tt, newprio);
-	if (((struct rtentry *)tt)->rt_priority != newprio) {
-		if (((struct rtentry *)tt)->rt_priority > newprio)
-			prioinv = 1;
-		t = tt;
-	} else {
-		mid = rn_mpath_active_count(tt) / 2;
-		do {
-			t = tt;
-			tt = rn_mpath_next(tt, 0);
-		} while (tt && --mid > 0);
-	}
-
-	/* insert rn before or after t depending on prioinv, tt and saved_tt */
-	if (tt == saved_tt && prioinv) {
-		/* link in at head of list */
-		rn->rn_dupedkey = tt;
-		rn->rn_p = tt->rn_p;
-		tt->rn_p = rn;
-		if (rn->rn_p->rn_l == tt)
-			rn->rn_p->rn_l = rn;
-		else
-			rn->rn_p->rn_r = rn;
-	} else if (prioinv == 1) {
-		rn->rn_dupedkey = t;
-		t->rn_p->rn_dupedkey = rn;
-		rn->rn_p = t->rn_p;
-		t->rn_p = rn;
-	} else {
-		rn->rn_dupedkey = t->rn_dupedkey;
-		t->rn_dupedkey = rn;
-		rn->rn_p = t;
-		if (rn->rn_dupedkey)
-			rn->rn_dupedkey->rn_p = rn;
-	}
-
-	if (rn->rn_mklist && rn->rn_flags & RNF_NORMAL) {
-		/* the rn_mklist needs to be fixed if the best route changed */
-		if (rn->rn_mklist->rm_leaf != rn) {
-			if (rn->rn_mklist->rm_leaf->rn_p == rn)
-				/* changed route is now best */
-				rn->rn_mklist->rm_leaf = rn;
-		} else {
-			if (rn->rn_dupedkey != head)
-				/* rn moved behind head, so head is new head */
-				rn->rn_mklist->rm_leaf = head;
+	if (rn_mpath_next(rn, RMP_MODE_BYPRIO)) {
+		while (rn != NULL) {
+			((struct rtentry *)rn)->rt_flags |= RTF_MPATH;
+			rn = rn_mpath_next(rn, RMP_MODE_BYPRIO);
 		}
-	}
+	} else
+		rt->rt_flags &= ~RTF_MPATH;
 }
 
 int
@@ -226,11 +168,16 @@ rn_mpath_active_count(struct radix_node *rn)
 	int i;
 
 	i = 1;
-	while ((rn = rn_mpath_next(rn, 0)) != NULL)
+	while ((rn = rn_mpath_next(rn, RMP_MODE_ACTIVE)) != NULL)
 		i++;
 	return i;
 }
 
+/*
+ * return best matching route based on gateway and prio. If both are
+ * specified it acts as a lookup function to get the actual rt.
+ * If gate is NULL the first node matching the prio will be returned.
+ */
 struct rtentry *
 rt_mpath_matchgate(struct rtentry *rt, struct sockaddr *gate, u_int8_t prio)
 {
@@ -243,20 +190,13 @@ rt_mpath_matchgate(struct rtentry *rt, struct sockaddr *gate, u_int8_t prio)
 		if (prio != RTP_ANY &&
 		    (rt->rt_priority & RTP_MASK) != (prio & RTP_MASK))
 			continue;
-		/*
-		 * if gate is set it must be compared, if not set the route
-		 * must be a non-multipath one.
-		 */
-		if (!gate && !rn_mpath_next(rn, 0))
-			return rt;
+		/* if no gate is set we found a match */
 		if (!gate)
-			return NULL;
-		if (!rt->rt_gateway)
-			continue;
+			return rt;
 		if (rt->rt_gateway->sa_len == gate->sa_len &&
 		    !memcmp(rt->rt_gateway, gate, gate->sa_len))
 			break;
-	} while ((rn = rn_mpath_next(rn, 1)) != NULL);
+	} while ((rn = rn_mpath_next(rn, RMP_MODE_ALL)) != NULL);
 
 	return (struct rtentry *)rn;
 }
@@ -341,28 +281,105 @@ rt_mpath_conflict(struct radix_node_head *rnh, struct rtentry *rt,
 	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;
-
-		/* sanity: no use in comparing the same thing */
-		if (rn1 == rn)
-			continue;
-
-		if (rt1->rt_gateway->sa_len != rt->rt_gateway->sa_len ||
-		    bcmp(rt1->rt_gateway, rt->rt_gateway,
-		    rt1->rt_gateway->sa_len))
-			continue;
-
+	if (rt_mpath_matchgate(rt1, rt->rt_gateway, rt->rt_priority))
 		/* all key/mask/gateway are the same.  conflicting entry. */
 		return EEXIST;
-	} while ((rn1 = rn_mpath_next(rn1, 0)) != NULL);
 
  different:
 	return 0;
 }
 
+void
+rn_mpath_reprio(struct radix_node *rn, int newprio)
+{
+	struct radix_node	*prev = rn->rn_p;
+	struct radix_node	*next = rn->rn_dupedkey;
+	struct radix_node	*t, *tt, *saved_tt, *head;
+	struct rtentry		*rt = (struct rtentry *)rn;
+	int			 mid, oldprio, prioinv = 0;
+
+	oldprio = rt->rt_priority;
+	rt->rt_priority = newprio;
+
+	/* same prio, no change needed */
+	if (oldprio == newprio)
+		return;
+	if (rn_mpath_next(rn, RMP_MODE_ALL) == NULL) {
+		/* no need to move node, route is alone */
+		if (prev->rn_mask != rn->rn_mask)
+			return;
+		/* ... or route is last and prio gets bigger */
+		if (oldprio < newprio)
+			return;
+	}
+
+	/* remove node from dupedkey list and reinsert at correct place */
+	if (prev->rn_dupedkey == rn) {
+		prev->rn_dupedkey = next;
+		if (next)
+			next->rn_p = prev;
+		else
+			next = prev;
+	} else {
+		if (next == NULL)
+			panic("next == NULL");
+		next->rn_p = prev;
+		if (prev->rn_l == rn)
+			prev->rn_l = next;
+		else
+			prev->rn_r = next;
+	}
+
+	/* re-insert rn at the right spot, so first rewind to the head */
+	for (tt = next; tt->rn_p->rn_dupedkey == tt; tt = tt->rn_p)
+		;
+	saved_tt = tt;
+
+	/*
+	 * Stolen from radix.c rn_addroute().
+	 * This is nasty code with a certain amount of magic and dragons.
+	 * t is the element where the re-priorized rn is inserted -- before
+	 * or after depending on prioinv. saved_tt points to the head of the
+	 * dupedkey chain and tt is a bit of a helper
+	 *
+	 * First we skip with tt to the start of the mpath group then we
+	 * search the right spot to enter our node.
+	 */
+	for (; tt; tt = tt->rn_dupedkey)
+		if (rn->rn_mask == tt->rn_mask)
+			break;
+	head = tt; /* store current head entry for rn_mklist check */
+
+	tt = rn_mpath_prio(tt, newprio);
+	if (((struct rtentry *)tt)->rt_priority != newprio) {
+		if (((struct rtentry *)tt)->rt_priority > newprio)
+			prioinv = 1;
+		t = tt;
+	} else {
+		mid = rn_mpath_active_count(tt) / 2;
+		do {
+			t = tt;
+			tt = rn_mpath_next(tt, RMP_MODE_ACTIVE);
+		} while (tt && --mid > 0);
+	}
+
+	/* insert rn before or after t depending on prioinv */
+	rn_link_dupedkey(rn, t, prioinv);
+
+	/* the rn_mklist needs to be fixed if the best route changed */
+	if (rn->rn_mklist && rn->rn_flags & RNF_NORMAL) {
+		if (rn->rn_mklist->rm_leaf != rn) {
+			if (rn->rn_mklist->rm_leaf->rn_p == rn)
+				/* changed route is now best */
+				rn->rn_mklist->rm_leaf = rn;
+		} else if (rn->rn_dupedkey != head) {
+			/* rn moved behind head, so head is new head */
+			rn->rn_mklist->rm_leaf = head;
+		}
+	}
+}
+
 /*
  * allocate a route, potentially using multipath to select the peer.
  */
@@ -405,14 +422,10 @@ rtalloc_mpath(struct route *ro, u_int32_t *srcaddrp)
 	threshold = 1 + (0xffff / npaths);
 	while (hash > threshold && rn) {
 		/* stay within the multipath routes */
-		if (rn_mpath_next(rn, 0) == NULL)
-			break;
-		rn = rn->rn_dupedkey;
+		rn = rn_mpath_next(rn, RMP_MODE_ACTIVE);
 		hash -= threshold;
 	}
 
-	/* XXX try filling rt_gwroute and avoid unreachable gw  */
-
 	/* if gw selection fails, use the first match (default) */
 	if (!rn)
 		return;
diff --git a/sys/net/radix_mpath.h b/sys/net/radix_mpath.h
index 1b49416a14e..f8b642decf6 100644
--- a/sys/net/radix_mpath.h
+++ b/sys/net/radix_mpath.h
@@ -1,4 +1,4 @@
-/*	$OpenBSD: radix_mpath.h,v 1.11 2013/10/24 18:50:16 deraadt Exp $	*/
+/*	$OpenBSD: radix_mpath.h,v 1.12 2014/05/27 19:38:15 claudio Exp $	*/
 /*	$KAME: radix_mpath.h,v 1.9 2004/03/30 11:21:49 keiichi Exp $	*/
 
 /*
@@ -45,9 +45,13 @@ struct route;
 struct rtentry;
 struct sockaddr;
 int	rn_mpath_capable(struct radix_node_head *);
+#define RMP_MODE_ACTIVE	0
+#define RMP_MODE_ALL	1
+#define RMP_MODE_BYPRIO	2
 struct radix_node *rn_mpath_next(struct radix_node *, int);
 struct radix_node *rn_mpath_prio(struct radix_node *, u_int8_t);
 void	rn_mpath_reprio(struct radix_node *, int);
+void	rn_mpath_adj_mpflag(struct radix_node *, u_int8_t);
 int	rn_mpath_active_count(struct radix_node *);
 struct rtentry *rt_mpath_matchgate(struct rtentry *, struct sockaddr *,
 	    u_int8_t);
diff --git a/sys/net/route.c b/sys/net/route.c
index b9654695e8b..bfd2363ddd7 100644
--- a/sys/net/route.c
+++ b/sys/net/route.c
@@ -1,4 +1,4 @@
-/*	$OpenBSD: route.c,v 1.167 2014/05/27 09:39:58 mpi Exp $	*/
+/*	$OpenBSD: route.c,v 1.168 2014/05/27 19:38:15 claudio Exp $	*/
 /*	$NetBSD: route.c,v 1.14 1996/02/13 22:00:46 christos Exp $	*/
 
 /*
@@ -319,7 +319,7 @@ void
 rtalloc_noclone(struct route *ro)
 {
 	if (ro->ro_rt && ro->ro_rt->rt_ifp && (ro->ro_rt->rt_flags & RTF_UP))
-		return;				 /* XXX */
+		return;		/* cached route is still valid */
 	ro->ro_rt = rtalloc1(&ro->ro_dst, RT_REPORT | RT_NOCLONING,
 	    ro->ro_tableid);
 }
@@ -328,7 +328,7 @@ void
 rtalloc(struct route *ro)
 {
 	if (ro->ro_rt && ro->ro_rt->rt_ifp && (ro->ro_rt->rt_flags & RTF_UP))
-		return;				 /* XXX */
+		return;		/* cached route is still valid */
 	ro->ro_rt = rtalloc1(&ro->ro_dst, RT_REPORT, ro->ro_tableid);
 }
 
@@ -780,7 +780,9 @@ rtrequest1(int req, struct rt_addrinfo *info, u_int8_t prio,
 			rt = rt_mpath_matchgate(rt,
 			    info->rti_info[RTAX_GATEWAY], prio);
 			rn = (struct radix_node *)rt;
-			if (!rt)
+			if (!rt ||
+			    (!info->rti_info[RTAX_GATEWAY] &&
+			    rt->rt_flags & RTF_MPATH))
 				senderr(ESRCH);
 		}
 #endif
@@ -815,15 +817,6 @@ rtrequest1(int req, struct rt_addrinfo *info, u_int8_t prio,
 			rt->rt_parent = NULL;
 		}
 
-#ifndef SMALL_KERNEL
-		if (rn_mpath_capable(rnh)) {
-			if ((rn = rnh->rnh_lookup(info->rti_info[RTAX_DST],
-			    info->rti_info[RTAX_NETMASK], rnh)) != NULL &&
-			    rt_mpath_next((struct rtentry *)rn) == NULL)
-				((struct rtentry *)rn)->rt_flags &= ~RTF_MPATH;
-		}
-#endif
-
 		rt->rt_flags &= ~RTF_UP;
 		if ((ifa = rt->rt_ifa) && ifa->ifa_rtrequest)
 			ifa->ifa_rtrequest(RTM_DELETE, rt);
@@ -1011,18 +1004,6 @@ rtrequest1(int req, struct rt_addrinfo *info, u_int8_t prio,
 			senderr(EEXIST);
 		}
 
-#ifndef SMALL_KERNEL
-		if (rn_mpath_capable(rnh) &&
-		    (rn = rnh->rnh_lookup(info->rti_info[RTAX_DST],
-		    info->rti_info[RTAX_NETMASK], rnh)) != NULL &&
-		    (rn = rn_mpath_prio(rn, prio)) != NULL) {
-			if (rt_mpath_next((struct rtentry *)rn) == NULL)
-				((struct rtentry *)rn)->rt_flags &= ~RTF_MPATH;
-			else
-				((struct rtentry *)rn)->rt_flags |= RTF_MPATH;
-		}
-#endif
-
 		if (ifa->ifa_rtrequest)
 			ifa->ifa_rtrequest(req, rt);
 		if (ret_nrt) {
@@ -1635,12 +1616,4 @@ rt_if_linkstate_change(struct radix_node *rn, void *arg, u_int id)
 
 	return (0);
 }
-
-struct rtentry *
-rt_mpath_next(struct rtentry *rt)
-{
-	struct radix_node *rn = (struct radix_node *)rt;
-
-	return ((struct rtentry *)rn_mpath_next(rn, 0));
-}
 #endif
diff --git a/sys/net/rtsock.c b/sys/net/rtsock.c
index e52e3504019..017ac635149 100644
--- a/sys/net/rtsock.c
+++ b/sys/net/rtsock.c
@@ -1,4 +1,4 @@
-/*	$OpenBSD: rtsock.c,v 1.145 2014/05/27 09:39:58 mpi Exp $	*/
+/*	$OpenBSD: rtsock.c,v 1.146 2014/05/27 19:38:15 claudio Exp $	*/
 /*	$NetBSD: rtsock.c,v 1.18 1996/03/29 00:32:10 cgd Exp $	*/
 
 /*
@@ -625,45 +625,23 @@ route_output(struct mbuf *m, ...)
 		 *
 		 * for RTM_GET, info.rti_info[RTAX_GATEWAY] is optional
 		 * even with multipath.
-		 * if it is NULL the first match is returned (no need to
-		 * call rt_mpath_matchgate).
 		 */
 		if (rn_mpath_capable(rnh)) {
-			/* first find correct priority bucket */
-			rn = rn_mpath_prio(rn, prio);
-			rt = (struct rtentry *)rn;
-			if (prio != RTP_ANY &&
-			    (rt->rt_priority & RTP_MASK) != prio) {
+			rt = rt_mpath_matchgate(rt,
+			    info.rti_info[RTAX_GATEWAY], prio);
+			if (!rt) {
 				error = ESRCH;
-				rt->rt_refcnt++;
 				goto flush;
 			}
 
-			/* if multipath routes */
-			if (rt_mpath_next(rt)) { /* XXX ignores down routes */
-				if (info.rti_info[RTAX_GATEWAY] != NULL) {
-					rt = rt_mpath_matchgate(rt,
-					    info.rti_info[RTAX_GATEWAY], prio);
-				} else if (rtm->rtm_type != RTM_GET) {
-					/*
-					 * only RTM_GET may use an empty
-					 * gateway  on multipath ...
-					 */
-					rt = NULL;
-				}
-			} else if ((info.rti_info[RTAX_GATEWAY] != NULL) &&
-			    (rtm->rtm_type == RTM_GET ||
-			     rtm->rtm_type == RTM_LOCK)) {
-				/*
-				 * ... but if a gateway is specified RTM_GET
-				 * and RTM_LOCK must match the gateway no matter
-				 * what.
-				 */
-				rt = rt_mpath_matchgate(rt,
-				    info.rti_info[RTAX_GATEWAY], prio);
-			}
-
-			if (!rt) {
+			/*
+			 * only RTM_GET may use an empty gateway
+			 * on multipath routes
+			 */
+			if (!info.rti_info[RTAX_GATEWAY] &&
+			    rt->rt_flags & RTF_MPATH &&
+			    rtm->rtm_type != RTM_GET) {
+				rt = NULL;
 				error = ESRCH;
 				goto flush;
 			}