Last missing piece in the equal cost multipath support for ospfd.

Send all possible nexthops to the parent process and correctly sync
the RIB, FIB and kernel routing table. Based on initial work by pyr@.
OK pyr@ norby@
PS: don't forget that you need to enable multipath support via a sysctl

4 files changed, 155 insertions, 77 deletions

diff --git a/usr.sbin/ospfd/kroute.c b/usr.sbin/ospfd/kroute.c
index b853cde88cd..b060e5b164c 100644
--- a/usr.sbin/ospfd/kroute.c
+++ b/usr.sbin/ospfd/kroute.c
@@ -1,4 +1,4 @@
-/*	$OpenBSD: kroute.c,v 1.52 2007/07/23 12:21:35 pyr Exp $ */
+/*	$OpenBSD: kroute.c,v 1.53 2007/09/25 11:25:41 claudio Exp $ */
 
 /*
  * Copyright (c) 2004 Esben Norby <norby@openbsd.org>
@@ -65,6 +65,8 @@ int	kr_redist_eval(struct kroute *, struct rroute *);
 void	kr_redistribute(struct kroute_node *);
 int	kroute_compare(struct kroute_node *, struct kroute_node *);
 int	kif_compare(struct kif_node *, struct kif_node *);
+int	kr_change_fib(struct kroute_node *, struct kroute *, int, int);
+int	kr_delete_fib(struct kroute_node *);
 
 struct kroute_node	*kroute_find(in_addr_t, u_int8_t);
 struct kroute_node	*kroute_matchgw(struct kroute_node *, struct in_addr);
@@ -164,18 +166,104 @@ kr_init(int fs)
 }
 
 int
-kr_change(struct kroute *kroute)
+kr_change_fib(struct kroute_node *kr, struct kroute *kroute, int krcount,
+    int action)
+{
+	int			 i;
+	struct kroute_node	*kn, *nkn;
+
+	if (action == RTM_ADD) {
+		/*
+		 * First remove all stale multipath routes.
+		 * This step must be skipped when the action is RTM_CHANGE
+		 * because it is already a single path route that will be
+		 * changed.
+		 */
+		for (kn = kr; kn != NULL; kn = nkn) {
+			for (i = 0; i < krcount; i++) {
+				if (kn->r.nexthop.s_addr ==
+				    kroute[i].nexthop.s_addr)
+					break;
+			}
+			nkn = kn->next;
+			if (i == krcount)
+				/* stale route */
+				if (kr_delete_fib(kn) == -1)
+					log_warnx("kr_delete_fib failed");
+			log_debug("kr_update_fib: before: %s%s",
+			    inet_ntoa(kn->r.nexthop),
+			    i == krcount ? " (deleted)" : "");
+		}
+	}
+
+	/*
+	 * now add or change the route
+	 */
+	for (i = 0; i < krcount; i++) {
+		/* nexthop within 127/8 -> ignore silently */
+		if ((kroute[i].nexthop.s_addr & htonl(IN_CLASSA_NET)) ==
+		    htonl(INADDR_LOOPBACK & IN_CLASSA_NET))
+			continue;
+
+		if (action == RTM_ADD && kr) {
+			for (kn = kr; kn != NULL; kn = kn->next) {
+				if (kn->r.nexthop.s_addr ==
+				    kroute[i].nexthop.s_addr)
+					break;
+			}
+
+			log_debug("kr_update_fib: after : %s%s",
+			     inet_ntoa(kroute[i].nexthop),
+			     kn == NULL ? " (added)" : "");
+
+			if (kn != NULL)
+				/* nexthop already present, skip it */
+				continue;
+		} else
+			/* modify first entry */
+			kn = kr;
+
+		/* send update */
+		if (send_rtmsg(kr_state.fd, action, &kroute[i]) == -1)
+			return (-1);
+
+		/* create new entry unless we are changing the first entry */
+		if (action == RTM_ADD)
+			if ((kn = calloc(1, sizeof(*kn))) == NULL)
+				fatal(NULL);
+
+		kn->r.prefix.s_addr = kroute[i].prefix.s_addr;
+		kn->r.prefixlen = kroute[i].prefixlen;
+		kn->r.nexthop.s_addr = kroute[i].nexthop.s_addr;
+		kn->r.flags = kroute[i].flags | F_OSPFD_INSERTED;
+		kn->r.ext_tag = kroute[i].ext_tag;
+		rtlabel_unref(kn->r.rtlabel);	/* for RTM_CHANGE */
+		kn->r.rtlabel = kroute[i].rtlabel;
+
+		if (action == RTM_ADD)
+			if (kroute_insert(kn) == -1) {
+				log_debug("kr_update_fib: cannot insert %s",
+				    inet_ntoa(kn->r.nexthop));
+				free(kn);
+			}
+		action = RTM_ADD;
+	}
+	return  (0);
+}
+
+int
+kr_change(struct kroute *kroute, int krcount)
 {
 	struct kroute_node	*kr;
 	int			 action = RTM_ADD;
 
 	kroute->rtlabel = rtlabel_tag2id(kroute->ext_tag);
 
-	if ((kr = kroute_find(kroute->prefix.s_addr, kroute->prefixlen)) !=
-	    NULL) {
-		if (!(kr->r.flags & F_KERNEL))
-			action = RTM_CHANGE;
-		else {	/* a non-ospf route already exists. not a problem */
+	kr = kroute_find(kroute->prefix.s_addr, kroute->prefixlen);
+
+	if (kr != NULL) {
+		if (kr->r.flags & F_KERNEL) {
+			/* a non-ospf route already exists. not a problem */
 			if (!(kr->r.flags & F_BGPD_INSERTED)) {
 				do {
 					kr->r.flags |= F_OSPFD_INSERTED;
@@ -194,45 +282,30 @@ kr_change(struct kroute *kroute)
 			 * - zero out ifindex (this is no longer relevant)
 			 */
 			action = RTM_CHANGE;
-			kr->r.flags = kroute->flags | F_OSPFD_INSERTED;
-			kr->r.ifindex = 0;
-			rtlabel_unref(kr->r.rtlabel);
-			kr->r.ext_tag = kroute->ext_tag;
-			kr->r.rtlabel = kroute->rtlabel;
-		}
+		} else if (kr->next == NULL)	/* single path OSPF route */
+			action = RTM_CHANGE;
 	}
 
-	/* nexthop within 127/8 -> ignore silently */
-	if ((kroute->nexthop.s_addr & htonl(IN_CLASSA_NET)) ==
-	    htonl(INADDR_LOOPBACK & IN_CLASSA_NET))
+	return (kr_change_fib(kr, kroute, krcount, action));
+}
+
+int
+kr_delete_fib(struct kroute_node *kr)
+{
+	if (!(kr->r.flags & F_OSPFD_INSERTED))
 		return (0);
 
-	/*
-	 * Ingnore updates that did not change the route.
-	 * Currently only the nexthop can change.
-	 */
-	if (kr && kr->r.nexthop.s_addr == kroute->nexthop.s_addr)
+	if (kr->r.flags & F_KERNEL) {
+		/* remove F_OSPFD_INSERTED flag, route still exists in kernel */
+		kr->r.flags &= ~F_OSPFD_INSERTED;
 		return (0);
+	}
 
-	if (send_rtmsg(kr_state.fd, action, kroute) == -1)
+	if (send_rtmsg(kr_state.fd, RTM_DELETE, &kr->r) == -1)
 		return (-1);
 
-	if (action == RTM_ADD) {
-		if ((kr = calloc(1, sizeof(struct kroute_node))) == NULL) {
-			log_warn("kr_change");
-			return (-1);
-		}
-		kr->r.prefix.s_addr = kroute->prefix.s_addr;
-		kr->r.prefixlen = kroute->prefixlen;
-		kr->r.nexthop.s_addr = kroute->nexthop.s_addr;
-		kr->r.flags = kroute->flags | F_OSPFD_INSERTED;
-		kr->r.ext_tag = kroute->ext_tag;
-		kr->r.rtlabel = kroute->rtlabel;
-
-		if (kroute_insert(kr) == -1)
-			free(kr);
-	} else
-		kr->r.nexthop.s_addr = kroute->nexthop.s_addr;
+	if (kroute_remove(kr) == -1)
+		return (-1);
 
 	return (0);
 }
@@ -240,30 +313,18 @@ kr_change(struct kroute *kroute)
 int
 kr_delete(struct kroute *kroute)
 {
-	struct kroute_node	*kr;
+	struct kroute_node	*kr, *nkr;
 
 	if ((kr = kroute_find(kroute->prefix.s_addr, kroute->prefixlen)) ==
 	    NULL)
 		return (0);
 
-	if (!(kr->r.flags & F_OSPFD_INSERTED))
-		return (0);
-
-	if (kr->r.flags & F_KERNEL) {
-		/* remove F_OSPFD_INSERTED flag, route still exists in kernel */
-		do {
-			kr->r.flags &= ~F_OSPFD_INSERTED;
-			kr = kr->next;
-		} while (kr);
-		return (0);
+	while (kr != NULL) {
+		nkr = kr->next;
+		if (kr_delete_fib(kr) == -1)
+			return (-1);
+		kr = nkr;
 	}
-
-	if (send_rtmsg(kr_state.fd, RTM_DELETE, kroute) == -1)
-		return (-1);
-
-	if (kroute_remove(kr) == -1)
-		return (-1);
-
 	return (0);
 }
 
@@ -279,6 +340,7 @@ void
 kr_fib_couple(void)
 {
 	struct kroute_node	*kr;
+	struct kroute_node	*kn;
 
 	if (kr_state.fib_sync == 1)	/* already coupled */
 		return;
@@ -287,7 +349,9 @@ kr_fib_couple(void)
 
 	RB_FOREACH(kr, kroute_tree, &krt)
 		if (!(kr->r.flags & F_KERNEL))
-			send_rtmsg(kr_state.fd, RTM_ADD, &kr->r);
+			for (kn = kr; kn != NULL; kn = kn->next) {
+				send_rtmsg(kr_state.fd, RTM_ADD, &kn->r);
+			}
 
 	log_info("kernel routing table coupled");
 }
@@ -296,13 +360,17 @@ void
 kr_fib_decouple(void)
 {
 	struct kroute_node	*kr;
+	struct kroute_node	*kn;
 
 	if (kr_state.fib_sync == 0)	/* already decoupled */
 		return;
 
-	RB_FOREACH(kr, kroute_tree, &krt)
+	RB_FOREACH(kr, kroute_tree, &krt) {
 		if (!(kr->r.flags & F_KERNEL))
-			send_rtmsg(kr_state.fd, RTM_DELETE, &kr->r);
+			for (kn = kr; kn != NULL; kn = kn->next) {
+				send_rtmsg(kr_state.fd, RTM_DELETE, &kn->r);
+			}
+	}
 
 	kr_state.fib_sync = 0;
 
@@ -966,7 +1034,7 @@ send_rtmsg(int fd, int action, struct kroute *kroute)
 	bzero(&hdr, sizeof(hdr));
 	hdr.rtm_version = RTM_VERSION;
 	hdr.rtm_type = action;
-	hdr.rtm_flags = RTF_PROTO2;
+	hdr.rtm_flags = RTF_PROTO2|RTF_MPATH;
 	if (action == RTM_CHANGE)	/* force PROTO2 reset the other flags */
 		hdr.rtm_fmask = RTF_PROTO2|RTF_PROTO1|RTF_REJECT|RTF_BLACKHOLE;
 	hdr.rtm_seq = kr_state.rtseq++;	/* overflow doesn't matter */
diff --git a/usr.sbin/ospfd/ospfd.c b/usr.sbin/ospfd/ospfd.c
index 38e1efbd6bf..cb8b9b5fff9 100644
--- a/usr.sbin/ospfd/ospfd.c
+++ b/usr.sbin/ospfd/ospfd.c
@@ -1,4 +1,4 @@
-/*	$OpenBSD: ospfd.c,v 1.49 2007/09/18 16:59:08 claudio Exp $ */
+/*	$OpenBSD: ospfd.c,v 1.50 2007/09/25 11:25:41 claudio Exp $ */
 
 /*
  * Copyright (c) 2005 Claudio Jeker <claudio@openbsd.org>
@@ -426,7 +426,7 @@ main_dispatch_rde(int fd, short event, void *bula)
 	struct imsgbuf  *ibuf = bula;
 	struct imsg	 imsg;
 	ssize_t		 n;
-	int		 shut = 0;
+	int		 count, shut = 0;
 
 	switch (event) {
 	case EV_READ:
@@ -453,7 +453,9 @@ main_dispatch_rde(int fd, short event, void *bula)
 
 		switch (imsg.hdr.type) {
 		case IMSG_KROUTE_CHANGE:
-			if (kr_change(imsg.data))
+			count = (imsg.hdr.len - IMSG_HEADER_SIZE) /
+			    sizeof(struct kroute);
+			if (kr_change(imsg.data, count))
 				log_warn("main_dispatch_rde: error changing "
 				    "route");
 			break;
diff --git a/usr.sbin/ospfd/ospfd.h b/usr.sbin/ospfd/ospfd.h
index b80ae3f7b44..0ef4258fe14 100644
--- a/usr.sbin/ospfd/ospfd.h
+++ b/usr.sbin/ospfd/ospfd.h
@@ -1,4 +1,4 @@
-/*	$OpenBSD: ospfd.h,v 1.69 2007/09/11 16:02:55 claudio Exp $ */
+/*	$OpenBSD: ospfd.h,v 1.70 2007/09/25 11:25:41 claudio Exp $ */
 
 /*
  * Copyright (c) 2004 Esben Norby <norby@openbsd.org>
@@ -600,7 +600,7 @@ u_int16_t	 iso_cksum(void *, u_int16_t, u_int16_t);
 /* kroute.c */
 int		 kif_init(void);
 int		 kr_init(int);
-int		 kr_change(struct kroute *);
+int		 kr_change(struct kroute *, int);
 int		 kr_delete(struct kroute *);
 void		 kr_shutdown(void);
 void		 kr_fib_couple(void);
diff --git a/usr.sbin/ospfd/rde.c b/usr.sbin/ospfd/rde.c
index 7949a087d12..35426f5b7b9 100644
--- a/usr.sbin/ospfd/rde.c
+++ b/usr.sbin/ospfd/rde.c
@@ -1,4 +1,4 @@
-/*	$OpenBSD: rde.c,v 1.69 2007/07/25 19:11:27 claudio Exp $ */
+/*	$OpenBSD: rde.c,v 1.70 2007/09/25 11:25:41 claudio Exp $ */
 
 /*
  * Copyright (c) 2004, 2005 Claudio Jeker <claudio@openbsd.org>
@@ -717,23 +717,31 @@ rde_router_id(void)
 void
 rde_send_change_kroute(struct rt_node *r)
 {
+	int			 krcount = 0;
 	struct kroute	 	 kr;
 	struct rt_nexthop	*rn;
+	struct buf		*wbuf;
+
+	if ((wbuf = imsg_create(ibuf_main, IMSG_KROUTE_CHANGE, 0, 0,
+	    sizeof(kr))) == NULL) {
+		return;
+	}
 
 	TAILQ_FOREACH(rn, &r->nexthop, entry) {
-		if (!rn->invalid)
-			break;
+		if (rn->invalid)
+			continue;
+		krcount++;
+
+		bzero(&kr, sizeof(kr));
+		kr.prefix.s_addr = r->prefix.s_addr;
+		kr.nexthop.s_addr = rn->nexthop.s_addr;
+		kr.prefixlen = r->prefixlen;
+		kr.ext_tag = r->ext_tag;
+		imsg_add(wbuf, &kr, sizeof(kr));
 	}
-	if (!rn)
+	if (krcount == 0)
 		fatalx("rde_send_change_kroute: no valid nexthop found");
-
-	bzero(&kr, sizeof(kr));
-	kr.prefix.s_addr = r->prefix.s_addr;
-	kr.nexthop.s_addr = rn->nexthop.s_addr;
-	kr.prefixlen = r->prefixlen;
-	kr.ext_tag = r->ext_tag;
-
-	imsg_compose(ibuf_main, IMSG_KROUTE_CHANGE, 0, 0, &kr, sizeof(kr));
+	imsg_close(ibuf_main, wbuf);
 }
 
 void