Remove no longer valid route entries.

ok claudio@

5 files changed, 132 insertions, 33 deletions

diff --git a/usr.sbin/ospfd/ospfd.c b/usr.sbin/ospfd/ospfd.c
index b135c55cf55..0cf43983da7 100644
--- a/usr.sbin/ospfd/ospfd.c
+++ b/usr.sbin/ospfd/ospfd.c
@@ -1,4 +1,4 @@
-/*	$OpenBSD: ospfd.c,v 1.7 2005/03/07 10:28:14 claudio Exp $ */
+/*	$OpenBSD: ospfd.c,v 1.8 2005/03/08 20:12:18 norby Exp $ */
 
 /*
  * Copyright (c) 2005 Claudio Jeker <claudio@openbsd.org>
@@ -372,7 +372,13 @@ main_dispatch_rde(int fd, short event, void *bula)
 		switch (imsg.hdr.type) {
 		case IMSG_KROUTE_CHANGE:
 			if (kr_change(imsg.data))
-				log_warn("main_dispatch_rde: error changing route");
+				log_warn("main_dispatch_rde: error changing "
+				    "route");
+			break;
+		case IMSG_KROUTE_DELETE:
+			if (kr_delete(imsg.data))
+				log_warn("main_dispatch_rde: error deleting "
+				    "route");
 			break;
 		default:
 			log_debug("main_dispatch_rde: error handling imsg %d",
diff --git a/usr.sbin/ospfd/ospfd.h b/usr.sbin/ospfd/ospfd.h
index f449f8513e3..3496c29bdc8 100644
--- a/usr.sbin/ospfd/ospfd.h
+++ b/usr.sbin/ospfd/ospfd.h
@@ -1,4 +1,4 @@
-/*	$OpenBSD: ospfd.h,v 1.12 2005/03/07 10:28:14 claudio Exp $ */
+/*	$OpenBSD: ospfd.h,v 1.13 2005/03/08 20:12:18 norby Exp $ */
 
 /*
  * Copyright (c) 2004 Esben Norby <norby@openbsd.org>
@@ -223,6 +223,16 @@ enum spf_state {
 	SPF_HOLDQUEUE
 };
 
+enum dst_type {
+	DT_NET,
+	DT_RTR
+};
+
+static const char * const dst_type_names[] = {
+	"Network",
+	"Router"
+};
+
 enum path_type {
 	PT_INTRA_AREA,
 	PT_INTER_AREA,
@@ -233,8 +243,8 @@ enum path_type {
 static const char * const path_type_names[] = {
 	"Intra-Area",
 	"Inter-Area",
-	"Type 1 external",
-	"Type 2 external"
+	"Type 1 ext",
+	"Type 2 ext"
 };
 
 /* lsa list used in RDE and OE */
diff --git a/usr.sbin/ospfd/rde.c b/usr.sbin/ospfd/rde.c
index 5d79486695c..5ff81983993 100644
--- a/usr.sbin/ospfd/rde.c
+++ b/usr.sbin/ospfd/rde.c
@@ -1,4 +1,4 @@
-/*	$OpenBSD: rde.c,v 1.7 2005/02/27 08:21:15 norby Exp $ */
+/*	$OpenBSD: rde.c,v 1.8 2005/03/08 20:12:18 norby Exp $ */
 
 /*
  * Copyright (c) 2004, 2005 Claudio Jeker <claudio@openbsd.org>
@@ -159,6 +159,7 @@ rde_shutdown(void)
 {
 	stop_spf_timer(rdeconf);
 	cand_list_clr();
+	rt_clear();
 
 	msgbuf_write(&ibuf_ospfe->w);
 	msgbuf_clear(&ibuf_ospfe->w);
@@ -473,7 +474,7 @@ rde_router_id(void)
 }
 
 void
-rde_send_kroute(struct rt_node *r)
+rde_send_change_kroute(struct rt_node *r)
 {
 	struct kroute	 kr;
 
@@ -485,6 +486,19 @@ rde_send_kroute(struct rt_node *r)
 	imsg_compose(ibuf_main, IMSG_KROUTE_CHANGE, 0, 0, -1, &kr, sizeof(kr));
 }
 
+void
+rde_send_delete_kroute(struct rt_node *r)
+{
+	struct kroute	 kr;
+
+	bzero(&kr, sizeof(kr));
+	kr.prefix.s_addr = r->prefix.s_addr;
+	kr.nexthop.s_addr = r->nexthop.s_addr;
+	kr.prefixlen = r->prefixlen;
+
+	imsg_compose(ibuf_main, IMSG_KROUTE_DELETE, 0, 0, -1, &kr, sizeof(kr));
+}
+
 LIST_HEAD(rde_nbr_head, rde_nbr);
 
 struct nbr_table {
diff --git a/usr.sbin/ospfd/rde.h b/usr.sbin/ospfd/rde.h
index 72ca6893b2a..0500862180c 100644
--- a/usr.sbin/ospfd/rde.h
+++ b/usr.sbin/ospfd/rde.h
@@ -1,4 +1,4 @@
-/*	$OpenBSD: rde.h,v 1.5 2005/02/27 08:21:15 norby Exp $ */
+/*	$OpenBSD: rde.h,v 1.6 2005/03/08 20:12:18 norby Exp $ */
 
 /*
  * Copyright (c) 2004, 2005 Esben Norby <norby@openbsd.org>
@@ -58,10 +58,13 @@ struct rde_nbr {
 struct rt_node {
 	RB_ENTRY(rt_node)	 entry;
 	struct in_addr		 prefix;
-	u_int8_t		 prefixlen;
 	struct in_addr		 nexthop;
-	enum path_type		 p_type;
+	struct in_addr		 area;
 	u_int32_t		 cost;
+	enum path_type		 p_type;
+	enum dst_type		 d_type;
+	u_int8_t		 prefixlen;
+	bool			 invalid;
 };
 
 /* rde.c */
@@ -70,7 +73,8 @@ int		 rde_imsg_compose_parent(int, pid_t, void *, u_int16_t);
 int		 rde_imsg_compose_ospfe(int, u_int32_t, pid_t, void *,
 		     u_int16_t);
 u_int32_t	 rde_router_id(void);
-void		 rde_send_kroute(struct rt_node *);
+void		 rde_send_change_kroute(struct rt_node *);
+void		 rde_send_delete_kroute(struct rt_node *);
 void		 rde_nbr_del(struct rde_nbr *);
 int		 rde_nbr_loading(struct area *);
 struct rde_nbr	*rde_nbr_self(struct area *);
diff --git a/usr.sbin/ospfd/rde_spf.c b/usr.sbin/ospfd/rde_spf.c
index 280a6f58d3e..609afb550d2 100644
--- a/usr.sbin/ospfd/rde_spf.c
+++ b/usr.sbin/ospfd/rde_spf.c
@@ -1,4 +1,4 @@
-/*	$OpenBSD: rde_spf.c,v 1.2 2005/03/02 16:17:04 norby Exp $ */
+/*	$OpenBSD: rde_spf.c,v 1.3 2005/03/08 20:12:18 norby Exp $ */
 
 /*
  * Copyright (c) 2005 Esben Norby <norby@openbsd.org>
@@ -30,7 +30,7 @@
 
 extern struct ospfd_conf	*rdeconf;
 TAILQ_HEAD(, vertex)		 cand_list;
-RB_HEAD(rt_tree, rt_node)	rt_tree, rt;
+RB_HEAD(rt_tree, rt_node)	 rt;
 RB_PROTOTYPE(rt_tree, rt_node, entry, rt_compare)
 RB_GENERATE(rt_tree, rt_node, entry, rt_compare)
 struct vertex			*spf_root = NULL;
@@ -39,9 +39,11 @@ void	 spf_dump(struct area *);	/* XXX */
 void	 rt_dump(void);			/* XXX */
 void	 cand_list_dump(void);		/* XXX */
 void	 calc_next_hop(struct vertex *, struct vertex *);
-void	 rt_update(struct in_addr, u_int8_t, struct in_addr, u_int32_t, u_int8_t);
+void	 rt_update(struct in_addr, u_int8_t, struct in_addr, u_int32_t,
+	     struct in_addr, u_int8_t, u_int8_t);
+void	 rt_invalidate(void);
 bool	 linked(struct vertex *, struct vertex *);
-u_int8_t	mask2prefixlen(in_addr_t);
+u_int8_t mask2prefixlen(in_addr_t);
 
 void
 spf_dump(struct area *area)
@@ -84,11 +86,11 @@ rt_dump(void)
 
 	RB_FOREACH(r, rt_tree, &rt) {
 		log_debug("net: %s/%d", inet_ntoa(r->prefix), r->prefixlen);
-		log_debug("   nexthop: %s   cost: %d   type: %s",
-		    inet_ntoa(r->nexthop), r->cost, path_type_names[r->p_type]);
+		log_debug("   nexthop: %s   cost: %d  ptype: %s   dtype: %s",
+		    inet_ntoa(r->nexthop), r->cost, path_type_names[r->p_type],
+		    dst_type_names[r->d_type]);
+		log_debug("                      area: %s", inet_ntoa(r->area));
 		i++;
-
-		rde_send_kroute(r);
 	}
 
 	log_debug("count: %d", i);
@@ -185,12 +187,10 @@ spf_calc(struct area *area)
 					continue;
 
 				if (d == w->cost) {
-					/* calc next hop */
 					calc_next_hop(w, v);
 				}
 
 				if (d < w->cost) {
-					/* calc next hop */
 					calc_next_hop(w, v);
 
 					w->cost = d;
@@ -204,7 +204,6 @@ spf_calc(struct area *area)
 					cand_list_add(w);
 					w->prev = v;
 
-					/* calc next hop */
 					calc_next_hop(w, v);
 				}
 			}
@@ -239,7 +238,8 @@ spf_calc(struct area *area)
 
 				rt_update(addr, mask2prefixlen(rtr_link->data),
 				    v->nexthop, v->cost +
-				    ntohs(rtr_link->metric), PT_INTRA_AREA);
+				    ntohs(rtr_link->metric), area->id,
+				    PT_INTRA_AREA, DT_NET);
 			}
 			break;
 		case LSA_TYPE_NETWORK:
@@ -249,7 +249,8 @@ spf_calc(struct area *area)
 
 			addr.s_addr = htonl(v->ls_id) & v->lsa->data.net.mask;
 			rt_update(addr, mask2prefixlen(v->lsa->data.net.mask),
-			    v->nexthop, v->cost, PT_INTRA_AREA);
+			    v->nexthop, v->cost, area->id, PT_INTRA_AREA,
+			    DT_NET);
 			break;
 		case LSA_TYPE_SUM_NETWORK:
 			if (rdeconf->flags & OSPF_RTR_B)
@@ -269,11 +270,14 @@ spf_calc(struct area *area)
 
 			addr.s_addr = htonl(v->ls_id) & v->lsa->data.sum.mask;
 			rt_update(addr, mask2prefixlen(v->lsa->data.sum.mask),
-			    v->nexthop, v->cost, PT_INTER_AREA);
+			    v->nexthop, v->cost, area->id, PT_INTER_AREA,
+			    DT_NET);
 			break;
 		case LSA_TYPE_SUM_ROUTER:
+			/* XXX */
 			break;
 		case LSA_TYPE_EXTERNAL:
+			/* XXX */
 			break;
 		default:
 			fatalx("spf_calc: invalid LSA type");
@@ -322,7 +326,29 @@ calc_next_hop(struct vertex *dst, struct vertex *parent)
 			}			
 			return;
 		case LSA_TYPE_NETWORK:
-			/* XXX TODO */
+			for (i = 0; i < lsa_num_links(parent); i++) {
+				rtr_link = get_rtr_link(parent, i);
+				switch (rtr_link->type) {
+				case LINK_TYPE_POINTTOPOINT:
+					/* ignore */
+					break;
+				case LINK_TYPE_TRANSIT_NET:
+					if ((htonl(dst->ls_id) &
+					    dst->lsa->data.net.mask) == 
+					    (rtr_link->data &
+					     dst->lsa->data.net.mask)) {
+						dst->nexthop.s_addr =
+						    rtr_link->data;
+					}
+					break;
+				case LINK_TYPE_STUB_NET:
+					break;
+
+				default:
+					fatalx("calc_next_hop: invalid link "
+					    "type");
+				}
+			}			
 			return;
 		default:
 			fatalx("calc_next_hop: invalid dst type");
@@ -434,8 +460,7 @@ spf_timer(int fd, short event, void *arg)
 {
 	struct ospfd_conf	*conf = arg;
 	struct area		*area;
-
-	log_debug("spf_timer:");
+	struct rt_node		*r;
 
 	switch (conf->spf_state) {
 	case SPF_IDLE:
@@ -445,10 +470,19 @@ spf_timer(int fd, short event, void *arg)
 		conf->spf_state = SPF_DELAY;
 		/* FALLTHROUGH */
 	case SPF_DELAY:
-		rt_clear();	/* XXX we should save to old rt! */
+		rt_invalidate();
+
 		LIST_FOREACH(area, &conf->area_list, entry) {
 			spf_calc(area);
 		}
+
+		RB_FOREACH(r, rt_tree, &rt) {
+			if (r->invalid)
+				rde_send_delete_kroute(r);
+			else
+				rde_send_change_kroute(r);
+		}
+
 		start_spf_holdtimer(rdeconf);
 		break;
 	case SPF_HOLD:
@@ -578,6 +612,18 @@ rt_remove(struct rt_node *r)
 }
 
 void
+rt_invalidate(void)
+{
+	struct rt_node	*r;
+
+	RB_FOREACH(r, rt_tree, &rt)
+		if (r->invalid)
+			rt_remove(r);
+		else
+			r->invalid = true;
+}
+
+void
 rt_clear(void)
 {
 	struct rt_node	*r;
@@ -588,10 +634,13 @@ rt_clear(void)
 
 void
 rt_update(struct in_addr prefix, u_int8_t prefixlen, struct in_addr nexthop,
-     u_int32_t cost, u_int8_t p_type)
+     u_int32_t cost, struct in_addr area, u_int8_t p_type, u_int8_t d_type)
 {
 	struct rt_node	*rte;
 
+	if (nexthop.s_addr == 0)	/* XXX remove */
+		fatalx("rt_update: invalid nexthop");
+
 	if ((rte = rt_find(prefix.s_addr, prefixlen)) == NULL) {
 		log_debug("rt_update: creating %s/%d", inet_ntoa(prefix),
 		    prefixlen);
@@ -601,19 +650,33 @@ rt_update(struct in_addr prefix, u_int8_t prefixlen, struct in_addr nexthop,
 		rte->prefixlen = prefixlen;
 		rte->nexthop.s_addr = nexthop.s_addr;
 		rte->cost = cost;
+		rte->area = area;
 		rte->p_type = p_type;
+		rte->d_type = d_type;
+		rte->invalid = false;
 
 		rt_insert(rte);
 	} else {
 		log_debug("rt_update: updating %s/%d", inet_ntoa(prefix),
 		    prefixlen);
 
-		/* XXX better route ? */
-		/* consider intra vs. inter */
-		if (cost < rte->cost) {
+		if (rte->invalid) {
+			/* invalidated entry - just update */
 			rte->nexthop.s_addr = nexthop.s_addr;
 			rte->cost = cost;
+			rte->area = area;
 			rte->p_type = p_type;
+			rte->invalid = false;
+		} else {
+			/* XXX better route ? */
+			/* consider intra vs. inter */
+			if (cost < rte->cost) {
+				rte->nexthop.s_addr = nexthop.s_addr;
+				rte->cost = cost;
+				rte->area = area;
+				rte->p_type = p_type;
+				rte->invalid = false;
+			}
 		}
 	}
 }
@@ -631,6 +694,7 @@ get_rtr_link(struct vertex *v, int idx)
 
 	off = sizeof(v->lsa->hdr) + sizeof(struct lsa_rtr);
 
+	/* nlinks validated earlier by lsa_check() */
 	nlinks = lsa_num_links(v);
 	for (i = 0; i < nlinks; i++) {
 		rtr_link = (struct lsa_rtr_link *)(buf + off);
@@ -657,6 +721,7 @@ get_net_link(struct vertex *v, int idx)
 
 	off = sizeof(v->lsa->hdr) + sizeof(u_int32_t);
 
+	/* nlinks validated earlier by lsa_check() */
 	nlinks = lsa_num_links(v);
 	for (i = 0; i < nlinks; i++) {
 		net_link = (struct lsa_net_link *)(buf + off);