Change the way way rn_mklists work (especially the RNF_NORMAL ones).

Until now RNF_NORMAL masks did not use the refcount because only one route
in a particular subtree could have this mask. With multipath routing this is
no longer correct. The result was wrong backtracking information beeing stored
in the radix tree and so cretain lookups ended up on the wrong multipath nodes.
Use rm_refs for RNF_NORMAL masks so that all multipath routes are able
to point to the same radix_mask entry. Additional logic ensures that rm_leaf
always points back to the head of the multipath rn_dupedkey chain.
Tested by dlg@, gollo@, david@, sthen@ and a few more
This can have my OK dlg@

2 files changed, 90 insertions, 13 deletions

diff --git a/sys/net/radix.c b/sys/net/radix.c
index cd704b9b0a3..dd6e6a8748f 100644
--- a/sys/net/radix.c
+++ b/sys/net/radix.c
@@ -1,4 +1,4 @@
-/*	$OpenBSD: radix.c,v 1.25 2008/12/29 21:24:19 claudio Exp $	*/
+/*	$OpenBSD: radix.c,v 1.26 2009/01/06 21:40:47 claudio Exp $	*/
 /*	$NetBSD: radix.c,v 1.20 2003/08/07 16:32:56 agc Exp $	*/
 
 /*
@@ -652,12 +652,20 @@ rn_addroute(void *v_arg, void *n_arg, struct radix_node_head *head,
 		x = t->rn_r;
 	/* Promote general routes from below */
 	if (x->rn_b < 0) {
-	    for (mp = &t->rn_mklist; x; x = x->rn_dupedkey)
+	    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
@@ -690,7 +698,28 @@ on2:
 			break;
 		if (m->rm_flags & RNF_NORMAL) {
 			mmask = m->rm_leaf->rn_mask;
-			if (tt->rn_flags & RNF_NORMAL) {
+			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)
+						if (t == tt)
+							break;
+					if (t == NULL) {
+						log(LOG_ERR, "Non-unique "
+						    "normal route on dupedkey, "
+						    "mask not entered\n");
+						return tt;
+					}
+				}
+#endif
+				m->rm_refs++;
+				tt->rn_mklist = m;
+				return tt;
+			} else if (tt->rn_flags & RNF_NORMAL) {
 				log(LOG_ERR, "Non-unique normal route,"
 				    " mask not entered\n");
 				return tt;
@@ -751,10 +780,28 @@ rn_delete(void *v_arg, void *netmask_arg, struct radix_node_head *head,
 	if (tt->rn_mask == 0 || (saved_m = m = tt->rn_mklist) == 0)
 		goto on1;
 	if (tt->rn_flags & RNF_NORMAL) {
-		if (m->rm_leaf != tt || m->rm_refs > 0) {
-			log(LOG_ERR, "rn_delete: inconsistent annotation\n");
-			return 0;  /* dangling ref could cause disaster */
+		if (m->rm_leaf != tt && m->rm_refs == 0) {
+			log(LOG_ERR, "rn_delete: inconsistent normal "
+			    "annotation\n");
+			return (0);
+		}
+		if (m->rm_leaf != tt) {
+			if (--m->rm_refs >= 0)
+				goto on1;
+		}
+		/* tt is currently the head of the possible multipath chain */
+		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);
+			}
+			m->rm_leaf = tt->rn_dupedkey;
+			--m->rm_refs;
+			goto on1;
 		}
+		/* else tt is last and only route */
 	} else {
 		if (m->rm_mask != tt->rn_mask) {
 			log(LOG_ERR, "rn_delete: inconsistent annotation\n");
@@ -862,6 +909,13 @@ on1:
 					x->rn_mklist = 0;
 					if (--(m->rm_refs) < 0)
 						MKFree(m);
+					else if (m->rm_flags & RNF_NORMAL)
+						/*
+						 * don't progress because this
+						 * a multipath route. Next
+						 * route will use the same m.
+						 */
+						mm = m;
 					m = mm;
 				}
 			if (m)
diff --git a/sys/net/radix_mpath.c b/sys/net/radix_mpath.c
index d2be140a598..5f5a86084e5 100644
--- a/sys/net/radix_mpath.c
+++ b/sys/net/radix_mpath.c
@@ -1,4 +1,4 @@
-/*	$OpenBSD: radix_mpath.c,v 1.14 2008/12/29 20:37:26 claudio Exp $	*/
+/*	$OpenBSD: radix_mpath.c,v 1.15 2009/01/06 21:40:47 claudio Exp $	*/
 /*	$KAME: radix_mpath.c,v 1.13 2002/10/28 21:05:59 itojun Exp $	*/
 
 /*
@@ -125,7 +125,7 @@ rn_mpath_reprio(struct radix_node *rn, int newprio)
 	if (oldprio == newprio)
 		return;
 	if (rn_mpath_next(rn, 1) == NULL) {
-		/* no need to move node route is alone */
+		/* no need to move node, route is alone */
 		if (prev->rn_mask != rn->rn_mask)
 			return;
 		/* ... or route is last and prio gets bigger */
@@ -150,9 +150,8 @@ rn_mpath_reprio(struct radix_node *rn, int newprio)
 			prev->rn_r = next;
 	}
 
-	/* re-insert rn at the right spot */
-	for (tt = next; tt->rn_p->rn_mask == rn->rn_mask;
-	    tt = tt->rn_p)
+	/* 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;
 
@@ -160,8 +159,17 @@ rn_mpath_reprio(struct radix_node *rn, int newprio)
 	 * 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. tt and saved_tt are just helpers.
+	 * 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;
+	next = tt->rn_dupedkey; /* store next 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)
@@ -175,6 +183,7 @@ rn_mpath_reprio(struct radix_node *rn, int newprio)
 		} 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;
@@ -196,15 +205,29 @@ rn_mpath_reprio(struct radix_node *rn, int newprio)
 		if (rn->rn_dupedkey)
 			rn->rn_dupedkey->rn_p = rn;
 	}
+
 #ifdef RN_DEBUG
 	/* readd at head of creation list */
-	for (t = rn_clist; t && t->rn_ybro != rn; t->rn_ybro)
+	for (t = rn_clist; t && t->rn_ybro != rn; t = t->rn_ybro)
 		;
 	if (t)
 		t->rn_ybro = rn->rn_ybro;
 	rn->rn_ybro = rn_clist;
 	rn_clist = rn;
 #endif
+
+	if (rn->rn_mklist) {
+		/* 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 != next)
+				/* rn moved behind next, next is new head */
+				rn->rn_mklist->rm_leaf = next;
+		}
+	}
 }
 
 int