Treat multiple Router-LSAs originated by the same router as an

aggregate, as mandated by RFC5340.

OK claudio@

3 files changed, 70 insertions, 41 deletions

diff --git a/usr.sbin/ospf6d/rde.h b/usr.sbin/ospf6d/rde.h
index 95d1449ebba..c28beac5248 100644
--- a/usr.sbin/ospf6d/rde.h
+++ b/usr.sbin/ospf6d/rde.h
@@ -1,4 +1,4 @@
-/*	$OpenBSD: rde.h,v 1.18 2009/12/22 17:54:04 claudio Exp $ */
+/*	$OpenBSD: rde.h,v 1.19 2010/02/22 08:03:06 stsp Exp $ */
 
 /*
  * Copyright (c) 2004, 2005 Esben Norby <norby@openbsd.org>
@@ -149,6 +149,7 @@ void		 lsa_del(struct rde_nbr *, struct lsa_hdr *);
 void		 lsa_age(struct vertex *);
 struct vertex	*lsa_find(struct iface *, u_int16_t, u_int32_t, u_int32_t);
 struct vertex	*lsa_find_rtr(struct area *, u_int32_t);
+struct vertex	*lsa_find_rtr_frag(struct area *, u_int32_t, unsigned int);
 struct vertex	*lsa_find_tree(struct lsa_tree *, u_int16_t, u_int32_t, u_int32_t);
 u_int16_t	 lsa_num_links(struct vertex *);
 void		 lsa_snap(struct rde_nbr *, u_int32_t);
diff --git a/usr.sbin/ospf6d/rde_lsdb.c b/usr.sbin/ospf6d/rde_lsdb.c
index f057feb8e1a..e406946aaff 100644
--- a/usr.sbin/ospf6d/rde_lsdb.c
+++ b/usr.sbin/ospf6d/rde_lsdb.c
@@ -1,4 +1,4 @@
-/*	$OpenBSD: rde_lsdb.c,v 1.26 2009/03/29 19:18:20 stsp Exp $ */
+/*	$OpenBSD: rde_lsdb.c,v 1.27 2010/02/22 08:03:06 stsp Exp $ */
 
 /*
  * Copyright (c) 2004, 2005 Claudio Jeker <claudio@openbsd.org>
@@ -533,43 +533,62 @@ lsa_find_tree(struct lsa_tree *tree, u_int16_t type, u_int32_t ls_id,
 struct vertex *
 lsa_find_rtr(struct area *area, u_int32_t rtr_id)
 {
-	struct vertex	*v;
-	struct vertex	*r;
-
-	/* A router can originate multiple router LSAs,
-	 * differentiated by link state ID. Our job is
-	 * to find among those the LSA with the lowest
-	 * link state ID, because this is where the options
-	 * field and router-type bits come from. */
-
-	r = NULL;
-	/* XXX speed me up */
-	RB_FOREACH(v, lsa_tree, &area->lsa_tree) {
-		if (v->deleted)
-			continue;
+	return lsa_find_rtr_frag(area, rtr_id, 0);
+}
 
-		if (v->type == LSA_TYPE_ROUTER &&
-		    v->adv_rtr == ntohl(rtr_id)) {
-			if (r == NULL)
-				r = v;
-			else if (v->ls_id < r->ls_id)
-				r = v;
+struct vertex *
+lsa_find_rtr_frag(struct area *area, u_int32_t rtr_id, unsigned int n)
+{
+	struct vertex	*v;
+	struct vertex	 key;
+	unsigned int	 i;
+
+	key.ls_id = 0;
+	key.adv_rtr = ntohl(rtr_id);
+	key.type = LSA_TYPE_ROUTER;
+
+	i = 0;
+	v = RB_NFIND(lsa_tree, &area->lsa_tree, &key);
+	while (v) {
+		if (v->type != LSA_TYPE_ROUTER ||
+		    v->adv_rtr != ntohl(rtr_id)) {
+			/* no more interesting LSAs */
+			v = NULL;
+			break;
 		}
+		if (!v->deleted) {
+			if (i >= n)
+				break;
+			i++;
+		}
+		v = RB_NEXT(lsa_tree, &area->lsa_tree, v);
 	}
 
-	if (r)
-		lsa_age(r);
+	if (v) {
+		if (i == n)
+			lsa_age(v);
+		else
+			v = NULL;
+	}
 
-	return (r);
+	return (v);
 }
 
 u_int16_t
 lsa_num_links(struct vertex *v)
 {
+	unsigned int	 n = 1;
+	u_int16_t	 nlinks = 0;
+
 	switch (v->type) {
 	case LSA_TYPE_ROUTER:
-		return ((ntohs(v->lsa->hdr.len) - sizeof(struct lsa_hdr) -
-		    sizeof(struct lsa_rtr)) / sizeof(struct lsa_rtr_link));
+		do {
+			nlinks += ((ntohs(v->lsa->hdr.len) -
+			    sizeof(struct lsa_hdr) - sizeof(struct lsa_rtr)) /
+			    sizeof(struct lsa_rtr_link));
+			v = lsa_find_rtr_frag(v->area, htonl(v->adv_rtr), n++);
+		} while (v);
+		return nlinks;
 	case LSA_TYPE_NETWORK:
 		return ((ntohs(v->lsa->hdr.len) - sizeof(struct lsa_hdr) -
 		    sizeof(struct lsa_net)) / sizeof(struct lsa_net_link));
diff --git a/usr.sbin/ospf6d/rde_spf.c b/usr.sbin/ospf6d/rde_spf.c
index 14b6ac35799..09db97737c2 100644
--- a/usr.sbin/ospf6d/rde_spf.c
+++ b/usr.sbin/ospf6d/rde_spf.c
@@ -1,4 +1,4 @@
-/*	$OpenBSD: rde_spf.c,v 1.20 2009/12/22 19:47:05 claudio Exp $ */
+/*	$OpenBSD: rde_spf.c,v 1.21 2010/02/22 08:03:06 stsp Exp $ */
 
 /*
  * Copyright (c) 2005 Esben Norby <norby@openbsd.org>
@@ -79,10 +79,6 @@ spf_calc(struct area *area)
 
 	/* calculate SPF tree */
 	do {
-		/* TODO: Treat multiple router LSAs originated by a single
-		 * router as one aggregate. We don't do this [yet],
-		 * but RFC5340 says we MUST do it. */
-
 		/* loop links */
 		for (i = 0; i < lsa_num_links(v); i++) {
 			switch (v->type) {
@@ -1039,20 +1035,33 @@ struct lsa_rtr_link *
 get_rtr_link(struct vertex *v, unsigned int idx)
 {
 	struct lsa_rtr_link	*rtr_link = NULL;
-	char			*buf = (char *)v->lsa;
+	unsigned int		 frag = 1;
+	unsigned int		 frag_nlinks;
+	unsigned int		 nlinks = 0;
 	unsigned int		 i;
 
 	if (v->type != LSA_TYPE_ROUTER)
 		fatalx("get_rtr_link: invalid LSA type");
 
-	/* number of links validated earlier by lsa_check() */
-	rtr_link = (struct lsa_rtr_link *)(buf + sizeof(v->lsa->hdr) +
-	    sizeof(struct lsa_rtr));
-	for (i = 0; i < lsa_num_links(v); i++) {
-		if (i == idx)
-			return (rtr_link);
-		rtr_link++;
-	}
+	/* Treat multiple Router-LSAs originated by the same router
+	 * as an aggregate. */
+	do {
+		/* number of links validated earlier by lsa_check() */
+		rtr_link = (struct lsa_rtr_link *)((char *)v->lsa +
+		    sizeof(v->lsa->hdr) + sizeof(struct lsa_rtr));
+		frag_nlinks = ((ntohs(v->lsa->hdr.len) -
+		    sizeof(struct lsa_hdr) - sizeof(struct lsa_rtr)) /
+		    sizeof(struct lsa_rtr_link));
+		if (nlinks + frag_nlinks > idx) {
+			for (i = 0; i < frag_nlinks; i++) {
+				if (i + nlinks == idx)
+					return (rtr_link);
+				rtr_link++;
+			}
+		}
+		nlinks += frag_nlinks;
+		v = lsa_find_rtr_frag(v->area, htonl(v->adv_rtr), frag++);
+	} while (v);
 
 	return (NULL);
 }