Rewrite the redistribute code. The previous implementation was stupid and

resulted in a major bottleneck if bgpd was used on the same box -- not clever
to do linear searches over 175k entries :(. This now moves the redistribute
code back into kroute duty and kills the linear list. Also default routes are
now redistributed without the need for a kernel default route.
OK norby@

5 files changed, 132 insertions, 171 deletions

diff --git a/usr.sbin/ospfd/kroute.c b/usr.sbin/ospfd/kroute.c
index ee85583ae32..406cc96c903 100644
--- a/usr.sbin/ospfd/kroute.c
+++ b/usr.sbin/ospfd/kroute.c
@@ -1,4 +1,4 @@
-/*	$OpenBSD: kroute.c,v 1.23 2006/01/12 15:00:48 claudio Exp $ */
+/*	$OpenBSD: kroute.c,v 1.24 2006/01/12 15:10:02 claudio Exp $ */
 
 /*
  * Copyright (c) 2004 Esben Norby <norby@openbsd.org>
@@ -75,6 +75,7 @@ struct kif_node		*kif_find(int);
 int			 kif_insert(struct kif_node *);
 int			 kif_remove(struct kif_node *);
 void			 kif_clear(void);
+int			 kif_validate(int);
 
 struct kroute_node	*kroute_match(in_addr_t);
 
@@ -331,10 +332,30 @@ kr_redistribute(int type, struct kroute *kr)
 {
 	u_int32_t	a;
 
+
+	if (type == IMSG_NETWORK_DEL) {
+		/* was the route redistributed? */
+		if (kr->flags & F_REDISTRIBUTED) {
+			/* remove redistributed flag */
+			kr->flags &= ~F_REDISTRIBUTED;
+			main_imsg_compose_rde(type, 0, kr,
+			    sizeof(struct kroute));
+		}
+		return;
+	}
+
+	/* Only non-ospfd routes are considered for redistribution. */
+	if (kr->flags & F_OSPFD_INSERTED)
+		return;
+
 	/* Dynamic routes are not redistributable. */
 	if (kr->flags & F_DYNAMIC)
 		return;
 
+	/* interface is not up and running so don't announce */
+	if (kr->flags & F_DOWN)
+		return;
+
 	/*
 	 * We consider the loopback net, multicast and experimental addresses
 	 * as not redistributable.
@@ -349,6 +370,12 @@ kr_redistribute(int type, struct kroute *kr)
 	if (kr->nexthop.s_addr == htonl(INADDR_LOOPBACK))
 		return;
 
+	/* Should we redistrubute this route? */
+	if (!ospf_redistribute(kr))
+		return;
+
+	/* Does not matter if we resend the kr, the RDE will cope. */
+	kr->flags |= F_REDISTRIBUTED;
 	main_imsg_compose_rde(type, 0, kr, sizeof(struct kroute));
 }
 
@@ -395,8 +422,18 @@ kroute_insert(struct kroute_node *kr)
 		return (-1);
 	}
 
-	if (kr->r.flags & F_KERNEL)
-		kr_redistribute(IMSG_NETWORK_ADD, &kr->r);
+	if (kr->r.flags & F_OSPFD_INSERTED) {
+		/* don't validate or redistribute ospf route */
+		kr->r.flags &= ~F_DOWN;
+		return (0);
+	}
+
+	if (kif_validate(kr->r.ifindex))
+		kr->r.flags &= ~F_DOWN;
+	else
+		kr->r.flags |= F_DOWN;
+
+	kr_redistribute(IMSG_NETWORK_ADD, &kr->r);
 
 	return (0);
 }
@@ -410,8 +447,7 @@ kroute_remove(struct kroute_node *kr)
 		return (-1);
 	}
 
-	if (kr->r.flags & F_KERNEL)
-		kr_redistribute(IMSG_NETWORK_DEL, &kr->r);
+	kr_redistribute(IMSG_NETWORK_DEL, &kr->r);
 
 	free(kr);
 	return (0);
@@ -482,20 +518,6 @@ kif_clear(void)
 		kif_remove(kif);
 }
 
-void
-kif_update(struct kif *k)
-{
-	struct kif_node		*kif;
-
-	if ((kif = kif_find(k->ifindex)) == NULL) {
-		log_warnx("interface with index %u not found",
-		    k->ifindex);
-		return;
-	}
-
-	memcpy(&kif->k, k, sizeof(struct kif));
-}
-
 int
 kif_validate(int ifindex)
 {
@@ -606,6 +628,8 @@ void
 if_change(u_short ifindex, int flags, struct if_data *ifd)
 {
 	struct kif_node		*kif;
+	struct kroute_node	*kr;
+	int			 type;
 	u_int8_t		 reachable;
 
 	if ((kif = kif_find(ifindex)) == NULL) {
@@ -626,8 +650,21 @@ if_change(u_short ifindex, int flags, struct if_data *ifd)
 		return;		/* nothing changed wrt nexthop validity */
 
 	kif->k.nh_reachable = reachable;
+	type = reachable ? IMSG_NETWORK_ADD : IMSG_NETWORK_DEL;
+
+	/* notify ospfe about interface link state */
 	main_imsg_compose_ospfe(IMSG_IFINFO, 0, &kif->k, sizeof(kif->k));
-	main_imsg_compose_rde(IMSG_IFINFO, 0, &kif->k, sizeof(kif->k));
+
+	/* update redistribute list */
+	RB_FOREACH(kr, kroute_tree, &krt)
+		if (kr->r.ifindex == ifindex) {
+			if (reachable)
+				kr->r.flags &= ~F_DOWN;
+			else
+				kr->r.flags |= F_DOWN;
+
+			kr_redistribute(type, &kr->r);
+		}
 }
 
 void
@@ -777,8 +814,7 @@ fetchtable(void)
 			return (-1);
 		}
 
-		if (!(rtm->rtm_flags & RTF_PROTO1))
-			kr->r.flags = F_KERNEL;
+		kr->r.flags = F_KERNEL;
 
 		switch (sa->sa_family) {
 		case AF_INET:
@@ -1002,6 +1038,12 @@ dispatch_rtmsg(void)
 				if (kr->r.flags & F_KERNEL) {
 					kr->r.nexthop.s_addr = nexthop.s_addr;
 					kr->r.flags = flags;
+
+					if (kif_validate(kr->r.ifindex))
+						kr->r.flags &= ~F_DOWN;
+					else
+						kr->r.flags |= F_DOWN;
+
 					/* just readd, the RDE will care */
 					kr_redistribute(IMSG_NETWORK_ADD,
 					    &kr->r);
diff --git a/usr.sbin/ospfd/ospfd.c b/usr.sbin/ospfd/ospfd.c
index 174782bc31a..ba91d7c7523 100644
--- a/usr.sbin/ospfd/ospfd.c
+++ b/usr.sbin/ospfd/ospfd.c
@@ -1,4 +1,4 @@
-/*	$OpenBSD: ospfd.c,v 1.25 2005/12/29 13:58:49 claudio Exp $ */
+/*	$OpenBSD: ospfd.c,v 1.26 2006/01/12 15:10:02 claudio Exp $ */
 
 /*
  * Copyright (c) 2005 Claudio Jeker <claudio@openbsd.org>
@@ -34,6 +34,7 @@
 #include <pwd.h>
 #include <stdio.h>
 #include <stdlib.h>
+#include <string.h>
 #include <signal.h>
 #include <unistd.h>
 #include <util.h>
@@ -54,6 +55,7 @@ void	main_dispatch_ospfe(int, short, void *);
 void	main_dispatch_rde(int, short, void *);
 
 int	check_file_secrecy(int, const char *);
+void	ospf_redistribute_default(int);
 
 int	pipe_parent2ospfe[2];
 int	pipe_parent2rde[2];
@@ -240,6 +242,9 @@ main(int argc, char *argv[])
 	if (kr_init(!(conf->flags & OSPFD_FLAG_NO_FIB_UPDATE)) == -1)
 		fatalx("kr_init failed");
 
+	/* redistribute default */
+	ospf_redistribute_default(IMSG_NETWORK_ADD);
+
 	event_dispatch();
 
 	ospfd_shutdown();
@@ -466,3 +471,35 @@ imsg_event_add(struct imsgbuf *ibuf)
 	event_set(&ibuf->ev, ibuf->fd, ibuf->events, ibuf->handler, ibuf);
 	event_add(&ibuf->ev, NULL);
 }
+
+int
+ospf_redistribute(struct kroute *kr)
+{
+	/* stub area router? */
+	if ((conf->options & OSPF_OPTION_E) == 0)
+		return (0);
+
+	/* only allow 0.0.0.0/0 via REDISTRIBUTE_DEFAULT */
+	if (kr->prefix.s_addr == INADDR_ANY && kr->prefixlen == 0)
+		return (0);
+
+	if ((conf->redistribute_flags & REDISTRIBUTE_STATIC) &&
+	    (kr->flags & F_STATIC))
+		return (1);
+	if ((conf->redistribute_flags & REDISTRIBUTE_CONNECTED) &&
+	    (kr->flags & F_CONNECTED))
+		return (1);
+
+	return (0);
+}
+
+void
+ospf_redistribute_default(int type)
+{
+	struct kroute	kr;
+
+	bzero(&kr, sizeof(kr));
+	if (conf->redistribute_flags & REDISTRIBUTE_DEFAULT)
+		main_imsg_compose_rde(type, 0, &kr, sizeof(struct kroute));
+}
+
diff --git a/usr.sbin/ospfd/ospfd.h b/usr.sbin/ospfd/ospfd.h
index 92acb550782..fb599bf0af2 100644
--- a/usr.sbin/ospfd/ospfd.h
+++ b/usr.sbin/ospfd/ospfd.h
@@ -1,4 +1,4 @@
-/*	$OpenBSD: ospfd.h,v 1.40 2006/01/05 15:53:36 claudio Exp $ */
+/*	$OpenBSD: ospfd.h,v 1.41 2006/01/12 15:10:02 claudio Exp $ */
 
 /*
  * Copyright (c) 2004 Esben Norby <norby@openbsd.org>
@@ -53,6 +53,7 @@
 #define	F_STATIC		0x0020
 #define	F_DYNAMIC		0x0040
 #define	F_LONGER		0x0080
+#define	F_REDISTRIBUTED		0x0100
 
 #define REDISTRIBUTE_STATIC	0x01
 #define REDISTRIBUTE_CONNECTED	0x02
@@ -518,8 +519,6 @@ void		 kr_dispatch_msg(int, short, void *);
 void		 kr_show_route(struct imsg *);
 void		 kr_ifinfo(char *, pid_t);
 struct kif	*kif_findname(char *);
-void		 kif_update(struct kif *);
-int		 kif_validate(int);
 
 u_int8_t	mask2prefixlen(in_addr_t);
 in_addr_t	prefixlen2mask(u_int8_t);
@@ -527,6 +526,7 @@ in_addr_t	prefixlen2mask(u_int8_t);
 /* ospfd.c */
 void	main_imsg_compose_ospfe(int, pid_t, void *, u_int16_t);
 void	main_imsg_compose_rde(int, pid_t, void *, u_int16_t);
+int	ospf_redistribute(struct kroute *kr);
 
 /* printconf.c */
 void	print_config(struct ospfd_conf *);
diff --git a/usr.sbin/ospfd/rde.c b/usr.sbin/ospfd/rde.c
index b3cfe3d1204..186b2f2f07c 100644
--- a/usr.sbin/ospfd/rde.c
+++ b/usr.sbin/ospfd/rde.c
@@ -1,4 +1,4 @@
-/*	$OpenBSD: rde.c,v 1.36 2006/01/05 15:10:57 norby Exp $ */
+/*	$OpenBSD: rde.c,v 1.37 2006/01/12 15:10:02 claudio Exp $ */
 
 /*
  * Copyright (c) 2004, 2005 Claudio Jeker <claudio@openbsd.org>
@@ -56,11 +56,8 @@ int		 rde_req_list_exists(struct rde_nbr *, struct lsa_hdr *);
 void		 rde_req_list_del(struct rde_nbr *, struct lsa_hdr *);
 void		 rde_req_list_free(struct rde_nbr *);
 
-int		 rde_redistribute(struct kroute *);
-void		 rde_update_redistribute(int);
 struct lsa	*rde_asext_get(struct kroute *);
 struct lsa	*rde_asext_put(struct kroute *);
-void		 rde_asext_free(void);
 
 struct lsa	*orig_asext_lsa(struct kroute *, u_int16_t);
 struct lsa	*orig_sum_lsa(struct rt_node *, u_int8_t);
@@ -184,7 +181,6 @@ rde_shutdown(void)
 		area_del(a);
 	}
 	rde_nbr_free();
-	rde_asext_free();
 
 	msgbuf_clear(&ibuf_ospfe->w);
 	free(ibuf_ospfe);
@@ -566,7 +562,6 @@ rde_dispatch_parent(int fd, short event, void *bula)
 	struct lsa		*lsa;
 	struct vertex		*v;
 	struct kroute		 kr;
-	struct kif		 kif;
 	int			 n;
 
 	switch (event) {
@@ -620,18 +615,6 @@ rde_dispatch_parent(int fd, short event, void *bula)
 				lsa_merge(nbrself, lsa, v);
 			}
 			break;
-		case IMSG_IFINFO:
-			if (imsg.hdr.len != IMSG_HEADER_SIZE + sizeof(kif)) {
-				log_warnx("rde_dispatch: wrong imsg len");
-				break;
-			}
-			memcpy(&kif, imsg.data, sizeof(kif));
-
-			log_debug("IMSG_IFINFO: ifindex %i reachable %d",
-			    kif.ifindex, kif.nh_reachable);
-			kif_update(&kif);
-			rde_update_redistribute(kif.ifindex);
-			break;
 		default:
 			log_debug("rde_dispatch_parent: unexpected imsg %d",
 			    imsg.hdr.type);
@@ -921,145 +904,50 @@ rde_req_list_free(struct rde_nbr *nbr)
 /*
  * as-external LSA handling
  */
-LIST_HEAD(, rde_asext) rde_asext_list;
-
-int
-rde_redistribute(struct kroute *kr)
+struct lsa *
+rde_asext_get(struct kroute *kr)
 {
 	struct area	*area;
 	struct iface	*iface;
-	int		 rv = 0;
-
-	if (!(kr->flags & F_KERNEL))
-		return (0);
-
-	if ((rdeconf->options & OSPF_OPTION_E) == 0)
-		return (0);
-
-	if ((rdeconf->redistribute_flags & REDISTRIBUTE_DEFAULT) &&
-	    (kr->prefix.s_addr == INADDR_ANY && kr->prefixlen == 0))
-		return (1);
-
-	/* only allow 0.0.0.0/0 if REDISTRIBUTE_DEFAULT */
-	if (kr->prefix.s_addr == INADDR_ANY && kr->prefixlen == 0)
-		return (0);
-
-	if ((rdeconf->redistribute_flags & REDISTRIBUTE_STATIC) &&
-	    (kr->flags & F_STATIC))
-		rv = 1;
-	if ((rdeconf->redistribute_flags & REDISTRIBUTE_CONNECTED) &&
-	    (kr->flags & F_CONNECTED))
-		rv = 1;
-
-	/* route does not match redistribute_flags */
-	if (rv == 0)
-		return (0);
-
-	/* interface is not up and running so don't announce */
-	if (kif_validate(kr->ifindex) == 0)
-		return (0);
 
 	LIST_FOREACH(area, &rdeconf->area_list, entry)
 		LIST_FOREACH(iface, &area->iface_list, entry) {
 			if ((iface->addr.s_addr & iface->mask.s_addr) ==
 			    kr->prefix.s_addr && iface->mask.s_addr ==
-			    prefixlen2mask(kr->prefixlen))
-				rv = 0;	/* already announced as net LSA */
-		}
-
-	return (rv);
-}
-
-void
-rde_update_redistribute(int ifindex)
-{
-	struct rde_asext	*ae;
-	struct lsa		*lsa;
-	struct vertex		*v;
-	int			 wasused;
-
-	LIST_FOREACH(ae, &rde_asext_list, entry)
-		if (ae->kr.ifindex == ifindex) {
-			wasused = ae->used;
-			ae->used = rde_redistribute(&ae->kr);
-			if (ae->used)
-				lsa = orig_asext_lsa(&ae->kr, DEFAULT_AGE);
-			else if (wasused)
-				lsa = orig_asext_lsa(&ae->kr, MAX_AGE);
-			else
-				continue;
-
-			v = lsa_find(NULL, lsa->hdr.type,
-			    lsa->hdr.ls_id, lsa->hdr.adv_rtr);
-
-			lsa_merge(nbrself, lsa, v);
+			    prefixlen2mask(kr->prefixlen)) {
+				/* already announced as (stub) net LSA */
+				log_debug("rde_asext_get: %s/%d is net LSA",
+				    inet_ntoa(kr->prefix), kr->prefixlen);
+				return (NULL);
+			}
 		}
-}
-
-struct lsa *
-rde_asext_get(struct kroute *kr)
-{
-	struct rde_asext	*ae;
-	int			 wasused;
-
-	LIST_FOREACH(ae, &rde_asext_list, entry)
-		if (kr->prefix.s_addr == ae->kr.prefix.s_addr &&
-		    kr->prefixlen == ae->kr.prefixlen)
-			break;
 
-	if (ae == NULL) {
-		if ((ae = calloc(1, sizeof(*ae))) == NULL)
-			fatal("rde_asext_get");
-		LIST_INSERT_HEAD(&rde_asext_list, ae, entry);
-	}
-
-	memcpy(&ae->kr, kr, sizeof(ae->kr));
-
-	wasused = ae->used;
-	ae->used = rde_redistribute(kr);
-
-	if (ae->used)
-		/* update of seqnum is done by lsa_merge */
-		return (orig_asext_lsa(kr, DEFAULT_AGE));
-	else if (wasused)
-		/* lsa_merge will take care of removing the lsa from the db */
-		return (orig_asext_lsa(kr, MAX_AGE));
-	else
-		/* not in lsdb, superseded by a net lsa */
-		return (NULL);
+	/* update of seqnum is done by lsa_merge */
+	return (orig_asext_lsa(kr, DEFAULT_AGE));
 }
 
 struct lsa *
 rde_asext_put(struct kroute *kr)
 {
-	struct rde_asext	*ae;
-	int			 used;
-
-	LIST_FOREACH(ae, &rde_asext_list, entry)
-		if (kr->prefix.s_addr == ae->kr.prefix.s_addr &&
-		    kr->prefixlen == ae->kr.prefixlen) {
-			LIST_REMOVE(ae, entry);
-			used = ae->used;
-			free(ae);
-			if (used)
-				return (orig_asext_lsa(kr, MAX_AGE));
-			break;
-		}
-	return (NULL);
-}
+	struct area	*area;
+	struct iface	*iface;
 
-void
-rde_asext_free(void)
-{
-	struct rde_asext	*ae;
+	LIST_FOREACH(area, &rdeconf->area_list, entry)
+		LIST_FOREACH(iface, &area->iface_list, entry) {
+			if ((iface->addr.s_addr & iface->mask.s_addr) ==
+			    kr->prefix.s_addr && iface->mask.s_addr ==
+			    prefixlen2mask(kr->prefixlen)) {
+				/* already announced as (stub) net LSA */
+				log_debug("rde_asext_put: %s/%d is net LSA",
+				    inet_ntoa(kr->prefix), kr->prefixlen);
+				return (NULL);
+			}
+		}
 
-	while ((ae = LIST_FIRST(&rde_asext_list)) != NULL) {
-		LIST_REMOVE(ae, entry);
-		free(ae);
-	}
+	/* remove by reflooding with MAX_AGE */
+	return (orig_asext_lsa(kr, MAX_AGE));
 }
 
-
 /*
  * summary LSA stuff
  */
diff --git a/usr.sbin/ospfd/rde.h b/usr.sbin/ospfd/rde.h
index fb3023729fa..ed8b4ca8a43 100644
--- a/usr.sbin/ospfd/rde.h
+++ b/usr.sbin/ospfd/rde.h
@@ -1,4 +1,4 @@
-/*	$OpenBSD: rde.h,v 1.20 2005/08/08 12:22:48 claudio Exp $ */
+/*	$OpenBSD: rde.h,v 1.21 2006/01/12 15:10:02 claudio Exp $ */
 
 /*
  * Copyright (c) 2004, 2005 Esben Norby <norby@openbsd.org>
@@ -62,12 +62,6 @@ struct rde_nbr {
 	int				 self;
 };
 
-struct rde_asext {
-	LIST_ENTRY(rde_asext)	 entry;
-	struct kroute		 kr;
-	int			 used;
-};
-
 struct rt_node {
 	RB_ENTRY(rt_node)	 entry;
 	struct in_addr		 prefix;