ospfd: Modifying LSID generation algorithm

Description:
	This LSID alogithm added as per rcf2328 Appendex-E recommendation.
	This applies only for AS-external lsas and summary lsas.

	As an example of the algorithm, consider its operation when the
        following sequence of events occurs in a single router (Router A).

        (1) Router A wants to originate an AS-external-LSA for
            [10.0.0.0,255.255.255.0]:

            (a) A Link State ID of 10.0.0.0 is used.

        (2) Router A then wants to originate an AS-external-LSA for
            [10.0.0.0,255.255.0.0]:

            (a) The LSA for [10.0.0,0,255.255.255.0] is reoriginated using a
                new Link State ID of 10.0.0.255.

            (b) A Link State ID of 10.0.0.0 is used for
                [10.0.0.0,255.255.0.0].

        (3) Router A then wants to originate an AS-external-LSA for
            [10.0.0.0,255.0.0.0]:
            (a) The LSA for [10.0.0.0,255.255.0.0] is reoriginated using a
                new Link State ID of 10.0.255.255.

            (b) A Link State ID of 10.0.0.0 is used for
                [10.0.0.0,255.0.0.0].

            (c) The network [10.0.0.0,255.255.255.0] keeps its Link State ID
                of 10.0.0.255.

Signed-off-by: Rajesh Girada <rgirada@vmware.com>

3 files changed, 321 insertions, 101 deletions

diff --git a/ospfd/ospf_asbr.c b/ospfd/ospf_asbr.c
index 000c62e30..b9878ef7e 100644
--- a/ospfd/ospf_asbr.c
+++ b/ospfd/ospf_asbr.c
@@ -223,8 +223,15 @@ struct ospf_lsa *ospf_external_info_find_lsa(struct ospf *ospf,
 	id.s_addr = p->prefix.s_addr | (~mask.s_addr);
 	lsa = ospf_lsdb_lookup_by_id(ospf->lsdb, OSPF_AS_EXTERNAL_LSA, id,
 				     ospf->router_id);
-	if (lsa)
+	if (lsa) {
+		if (p->prefixlen == IPV4_MAX_BITLEN) {
+			al = (struct as_external_lsa *)lsa->data;
+
+			if (mask.s_addr != al->mask.s_addr)
+				return NULL;
+		}
 		return lsa;
+	}
 
 	lsa = ospf_lsdb_lookup_by_id(ospf->lsdb, OSPF_AS_EXTERNAL_LSA,
 				     p->prefix, ospf->router_id);
diff --git a/ospfd/ospf_lsa.c b/ospfd/ospf_lsa.c
index 6588d7020..39abf358e 100644
--- a/ospfd/ospf_lsa.c
+++ b/ospfd/ospf_lsa.c
@@ -53,6 +53,29 @@
 #include "ospfd/ospf_abr.h"
 #include "ospfd/ospf_errors.h"
 
+static struct ospf_lsa *ospf_handle_summarylsa_lsId_chg(struct ospf *ospf,
+							struct prefix_ipv4 *p,
+							uint8_t type,
+							uint32_t metric,
+							struct in_addr old_id);
+static struct ospf_lsa *
+ospf_summary_lsa_prepare_and_flood(struct prefix_ipv4 *p, uint32_t metric,
+				   struct ospf_area *area, struct in_addr id);
+static struct ospf_lsa *ospf_summary_lsa_refresh(struct ospf *ospf,
+						 struct ospf_lsa *lsa);
+static struct ospf_lsa *
+ospf_asbr_summary_lsa_prepare_and_flood(struct prefix_ipv4 *p, uint32_t metric,
+					struct ospf_area *area,
+					struct in_addr id);
+static struct ospf_lsa *ospf_summary_asbr_lsa_refresh(struct ospf *ospf,
+						      struct ospf_lsa *lsa);
+static struct ospf_lsa *ospf_handle_exnl_lsa_lsId_chg(struct ospf *ospf,
+						      struct external_info *ei,
+						      struct in_addr id);
+static struct ospf_lsa *
+ospf_exnl_lsa_prepare_and_flood(struct ospf *ospf, struct external_info *ei,
+				struct in_addr id);
+
 uint32_t get_metric(uint8_t *metric)
 {
 	uint32_t m;
@@ -1221,31 +1244,11 @@ static struct ospf_lsa *ospf_summary_lsa_new(struct ospf_area *area,
 }
 
 /* Originate Summary-LSA. */
-struct ospf_lsa *ospf_summary_lsa_originate(struct prefix_ipv4 *p,
-					    uint32_t metric,
-					    struct ospf_area *area)
+static struct ospf_lsa *
+ospf_summary_lsa_prepare_and_flood(struct prefix_ipv4 *p, uint32_t metric,
+				   struct ospf_area *area, struct in_addr id)
 {
 	struct ospf_lsa *new;
-	struct in_addr id;
-
-	if (area->ospf->gr_info.restart_in_progress) {
-		if (IS_DEBUG_OSPF(lsa, LSA_GENERATE))
-			zlog_debug(
-				"LSA[Type%d]: Graceful Restart in progress, don't originate",
-				OSPF_SUMMARY_LSA);
-		return NULL;
-	}
-
-	id = ospf_lsa_unique_id(area->ospf, area->lsdb, OSPF_SUMMARY_LSA, p);
-
-	if (id.s_addr == 0xffffffff) {
-		/* Maybe Link State ID not available. */
-		if (IS_DEBUG_OSPF(lsa, LSA_GENERATE))
-			zlog_debug(
-				"LSA[Type%d]: Link ID not available, can't originate",
-				OSPF_SUMMARY_LSA);
-		return NULL;
-	}
 
 	/* Create new summary-LSA instance. */
 	if (!(new = ospf_summary_lsa_new(area, (struct prefix *)p, metric, id)))
@@ -1270,6 +1273,97 @@ struct ospf_lsa *ospf_summary_lsa_originate(struct prefix_ipv4 *p,
 	return new;
 }
 
+static struct ospf_lsa *ospf_handle_summarylsa_lsId_chg(struct ospf *ospf,
+							struct prefix_ipv4 *p,
+							uint8_t type,
+							uint32_t metric,
+							struct in_addr old_id)
+{
+	struct ospf_lsa *lsa = NULL;
+	struct ospf_lsa *new = NULL;
+	struct summary_lsa *sl = NULL;
+	struct ospf_area *old_area = NULL;
+	struct prefix_ipv4 old_prefix;
+	uint32_t old_metric;
+	struct in_addr mask;
+	uint32_t metric_val;
+	char *metric_buf;
+
+	lsa = ospf_lsdb_lookup_by_id(ospf->lsdb, type, p->prefix,
+				     ospf->router_id);
+
+	if (!lsa) {
+		flog_warn(EC_OSPF_LSA_NULL, "(%s): LSA not found", __func__);
+		return NULL;
+	}
+
+	sl = (struct summary_lsa *)lsa->data;
+
+	old_area = lsa->area;
+	old_metric = GET_METRIC(sl->metric);
+	old_prefix.prefix = sl->header.id;
+	old_prefix.prefixlen = ip_masklen(sl->mask);
+	old_prefix.family = AF_INET;
+
+
+	/* change the mask */
+	masklen2ip(p->prefixlen, &mask);
+	sl->mask.s_addr = mask.s_addr;
+
+	/* Copy the metric*/
+	metric_val = htonl(metric);
+	metric_buf = (char *)&metric_val;
+	memcpy(sl->metric, metric_buf, sizeof(metric_val));
+
+	if (type == OSPF_SUMMARY_LSA) {
+		/*Refresh the LSA with new LSA*/
+		ospf_summary_lsa_refresh(ospf, lsa);
+
+		new = ospf_summary_lsa_prepare_and_flood(
+			&old_prefix, old_metric, old_area, old_id);
+	} else {
+		/*Refresh the LSA with new LSA*/
+		ospf_summary_asbr_lsa_refresh(ospf, lsa);
+
+		new = ospf_asbr_summary_lsa_prepare_and_flood(
+			&old_prefix, old_metric, old_area, old_id);
+	}
+
+	return new;
+}
+
+/* Originate Summary-LSA. */
+struct ospf_lsa *ospf_summary_lsa_originate(struct prefix_ipv4 *p,
+					    uint32_t metric,
+					    struct ospf_area *area)
+{
+	struct in_addr id;
+	enum lsid_status status;
+	struct ospf_lsa *new = NULL;
+
+	status = ospf_lsa_unique_id(area->ospf, area->lsdb, OSPF_SUMMARY_LSA, p,
+				    &id);
+
+	if (status == LSID_CHANGE) {
+		if (IS_DEBUG_OSPF(lsa, LSA_GENERATE))
+			zlog_debug("Link ID has to be changed.");
+
+		new = ospf_handle_summarylsa_lsId_chg(
+			area->ospf, p, OSPF_SUMMARY_LSA, metric, id);
+		return new;
+	} else if (status == LSID_NOT_AVAILABLE) {
+		/* Link State ID not available. */
+		if (IS_DEBUG_OSPF(lsa, LSA_GENERATE))
+			zlog_debug(
+				"LSA[Type5]: Link ID not available, can't originate");
+
+		return NULL;
+	}
+
+	new = ospf_summary_lsa_prepare_and_flood(p, metric, area, id);
+	return new;
+}
+
 static struct ospf_lsa *ospf_summary_lsa_refresh(struct ospf *ospf,
 						 struct ospf_lsa *lsa)
 {
@@ -1370,32 +1464,12 @@ static struct ospf_lsa *ospf_summary_asbr_lsa_new(struct ospf_area *area,
 }
 
 /* Originate summary-ASBR-LSA. */
-struct ospf_lsa *ospf_summary_asbr_lsa_originate(struct prefix_ipv4 *p,
-						 uint32_t metric,
-						 struct ospf_area *area)
+static struct ospf_lsa *
+ospf_asbr_summary_lsa_prepare_and_flood(struct prefix_ipv4 *p, uint32_t metric,
+					struct ospf_area *area,
+					struct in_addr id)
 {
 	struct ospf_lsa *new;
-	struct in_addr id;
-
-	if (area->ospf->gr_info.restart_in_progress) {
-		if (IS_DEBUG_OSPF(lsa, LSA_GENERATE))
-			zlog_debug(
-				"LSA[Type%d]: Graceful Restart in progress, don't originate",
-				OSPF_ASBR_SUMMARY_LSA);
-		return NULL;
-	}
-
-	id = ospf_lsa_unique_id(area->ospf, area->lsdb, OSPF_ASBR_SUMMARY_LSA,
-				p);
-
-	if (id.s_addr == 0xffffffff) {
-		/* Maybe Link State ID not available. */
-		if (IS_DEBUG_OSPF(lsa, LSA_GENERATE))
-			zlog_debug(
-				"LSA[Type%d]: Link ID not available, can't originate",
-				OSPF_ASBR_SUMMARY_LSA);
-		return NULL;
-	}
 
 	/* Create new summary-LSA instance. */
 	new = ospf_summary_asbr_lsa_new(area, (struct prefix *)p, metric, id);
@@ -1421,6 +1495,37 @@ struct ospf_lsa *ospf_summary_asbr_lsa_originate(struct prefix_ipv4 *p,
 	return new;
 }
 
+struct ospf_lsa *ospf_summary_asbr_lsa_originate(struct prefix_ipv4 *p,
+						 uint32_t metric,
+						 struct ospf_area *area)
+{
+	struct ospf_lsa *new;
+	struct in_addr id;
+	enum lsid_status status;
+
+	status = ospf_lsa_unique_id(area->ospf, area->lsdb,
+				    OSPF_ASBR_SUMMARY_LSA, p, &id);
+
+	if (status == LSID_CHANGE) {
+		if (IS_DEBUG_OSPF(lsa, LSA_GENERATE))
+			zlog_debug("Link ID has to be changed.");
+
+		new = ospf_handle_summarylsa_lsId_chg(
+			area->ospf, p, OSPF_ASBR_SUMMARY_LSA, metric, id);
+		return new;
+	} else if (status == LSID_NOT_AVAILABLE) {
+		/* Link State ID not available. */
+		if (IS_DEBUG_OSPF(lsa, LSA_GENERATE))
+			zlog_debug(
+				"LSA[Type5]: Link ID not available, can't originate");
+
+		return NULL;
+	}
+
+	new = ospf_asbr_summary_lsa_prepare_and_flood(p, metric, area, id);
+	return new;
+}
+
 static struct ospf_lsa *ospf_summary_asbr_lsa_refresh(struct ospf *ospf,
 						      struct ospf_lsa *lsa)
 {
@@ -1612,42 +1717,15 @@ static void ospf_external_lsa_body_set(struct stream *s,
 }
 
 /* Create new external-LSA. */
-static struct ospf_lsa *ospf_external_lsa_new(struct ospf *ospf,
-					      struct external_info *ei,
-					      struct in_addr *old_id)
+static struct ospf_lsa *
+ospf_exnl_lsa_prepare_and_flood(struct ospf *ospf, struct external_info *ei,
+				struct in_addr id)
 {
 	struct stream *s;
 	struct lsa_header *lsah;
 	struct ospf_lsa *new;
-	struct in_addr id;
 	int length;
 
-	if (ei == NULL) {
-		if (IS_DEBUG_OSPF(lsa, LSA_GENERATE))
-			zlog_debug(
-				"LSA[Type5]: External info is NULL, can't originate");
-		return NULL;
-	}
-
-	if (IS_DEBUG_OSPF(lsa, LSA_GENERATE))
-		zlog_debug("LSA[Type5]: Originate AS-external-LSA instance");
-
-	/* If old Link State ID is specified, refresh LSA with same ID. */
-	if (old_id)
-		id = *old_id;
-	/* Get Link State with unique ID. */
-	else {
-		id = ospf_lsa_unique_id(ospf, ospf->lsdb, OSPF_AS_EXTERNAL_LSA,
-					&ei->p);
-		if (id.s_addr == 0xffffffff) {
-			/* Maybe Link State ID not available. */
-			if (IS_DEBUG_OSPF(lsa, LSA_GENERATE))
-				zlog_debug(
-					"LSA[Type5]: Link ID not available, can't originate");
-			return NULL;
-		}
-	}
-
 	/* Create new stream for LSA. */
 	s = stream_new(OSPF_MAX_LSA_SIZE);
 	lsah = (struct lsa_header *)STREAM_DATA(s);
@@ -1677,6 +1755,99 @@ static struct ospf_lsa *ospf_external_lsa_new(struct ospf *ospf,
 	return new;
 }
 
+static struct ospf_lsa *ospf_handle_exnl_lsa_lsId_chg(struct ospf *ospf,
+						      struct external_info *ei,
+						      struct in_addr id)
+{
+	struct ospf_lsa *lsa;
+	struct as_external_lsa *al;
+	struct in_addr mask;
+	struct ospf_lsa *new;
+	struct external_info ei_summary;
+	struct external_info *ei_old;
+
+	lsa = ospf_lsdb_lookup_by_id(ospf->lsdb, OSPF_AS_EXTERNAL_LSA,
+				     ei->p.prefix, ospf->router_id);
+
+	if (!lsa) {
+		flog_warn(EC_OSPF_LSA_NULL, "(%s): LSA not found", __func__);
+		return NULL;
+	}
+
+	ei_old = ospf_external_info_check(ospf, lsa);
+
+	al = (struct as_external_lsa *)lsa->data;
+
+	if (!ei_old) {
+		/* eii_old pointer of LSA is NULL, this
+		 * must be external aggregate route.
+		 */
+		ei_summary.p.family = AF_INET;
+		ei_summary.p.prefix = al->header.id;
+		ei_summary.p.prefixlen = ip_masklen(al->mask);
+		ei_summary.tag = (unsigned long)ntohl(al->e[0].route_tag);
+		ei_old = &ei_summary;
+	}
+
+	/* change the mask */
+	masklen2ip(ei->p.prefixlen, &mask);
+	al->mask.s_addr = mask.s_addr;
+
+	/*Refresh the LSA with new LSA*/
+	ospf_external_lsa_refresh(ospf, lsa, ei, LSA_REFRESH_FORCE, 0);
+
+	/*Originate the old LSA with changed LSID*/
+	new = ospf_exnl_lsa_prepare_and_flood(ospf, ei_old, id);
+
+	return new;
+}
+
+static struct ospf_lsa *ospf_external_lsa_new(struct ospf *ospf,
+					      struct external_info *ei,
+					      struct in_addr *old_id)
+{
+	struct ospf_lsa *new;
+	struct in_addr id;
+	enum lsid_status status;
+
+	if (ei == NULL) {
+		if (IS_DEBUG_OSPF(lsa, LSA_GENERATE))
+			zlog_debug(
+				"LSA[Type5]: External info is NULL, can't originate");
+		return NULL;
+	}
+
+	if (IS_DEBUG_OSPF(lsa, LSA_GENERATE))
+		zlog_debug("LSA[Type5]: Originate AS-external-LSA instance");
+
+	/* If old Link State ID is specified, refresh LSA with same ID. */
+	if (old_id)
+		id = *old_id;
+	/* Get Link State with unique ID. */
+	else {
+		status = ospf_lsa_unique_id(ospf, ospf->lsdb,
+					    OSPF_AS_EXTERNAL_LSA, &ei->p, &id);
+
+		if (status == LSID_CHANGE) {
+			if (IS_DEBUG_OSPF(lsa, LSA_GENERATE))
+				zlog_debug("Link ID has to be changed.");
+
+			new = ospf_handle_exnl_lsa_lsId_chg(ospf, ei, id);
+			return new;
+		} else if (status == LSID_NOT_AVAILABLE) {
+			/* Link State ID not available. */
+			if (IS_DEBUG_OSPF(lsa, LSA_GENERATE))
+				zlog_debug(
+					"LSA[Type5]: Link ID not available, can't originate");
+			return NULL;
+		}
+	}
+
+	new = ospf_exnl_lsa_prepare_and_flood(ospf, ei, id);
+
+	return new;
+}
+
 /* As Type-7 */
 static void ospf_install_flood_nssa(struct ospf *ospf, struct ospf_lsa *lsa,
 				    struct external_info *ei)
@@ -3510,49 +3681,87 @@ int ospf_lsa_is_self_originated(struct ospf *ospf, struct ospf_lsa *lsa)
 }
 
 /* Get unique Link State ID. */
-struct in_addr ospf_lsa_unique_id(struct ospf *ospf, struct ospf_lsdb *lsdb,
-				  uint8_t type, struct prefix_ipv4 *p)
+enum lsid_status ospf_lsa_unique_id(struct ospf *ospf, struct ospf_lsdb *lsdb,
+				    uint8_t type, struct prefix_ipv4 *p,
+				    struct in_addr *id)
 {
 	struct ospf_lsa *lsa;
-	struct in_addr mask, id;
+	struct in_addr mask;
 
-	id = p->prefix;
+	*id = p->prefix;
 
 	/* Check existence of LSA instance. */
-	lsa = ospf_lsdb_lookup_by_id(lsdb, type, id, ospf->router_id);
+	lsa = ospf_lsdb_lookup_by_id(lsdb, type, *id, ospf->router_id);
 	if (lsa) {
 		struct as_external_lsa *al =
 			(struct as_external_lsa *)lsa->data;
+		/* Ref rfc2328,Appendex E.1
+		 * If router already originated the external lsa with lsid
+		 * as the current prefix, and the masklens are same then
+		 * terminate the LSID algorithem.
+		 */
 		if (ip_masklen(al->mask) == p->prefixlen) {
 			if (IS_DEBUG_OSPF(lsa, LSA_GENERATE))
 				zlog_debug(
-					"ospf_lsa_unique_id(): Can't get Link State ID for %pFX",
-					p);
+					"%s: Can't get Link State ID for %pFX",
+					__func__, p);
 			/*	  id.s_addr = 0; */
-			id.s_addr = 0xffffffff;
-			return id;
-		}
-		/* Masklen differs, then apply wildcard mask to Link State ID.
-		   */
-		else {
+			id->s_addr = 0xffffffff;
+			return LSID_NOT_AVAILABLE;
+		} else if (ip_masklen(al->mask) < p->prefixlen) {
+			/* Ref rfc2328,Appendex E.2
+			 * the current prefix masklen is greater than the
+			 * existing LSA, then generate the Link state ID,
+			 * by setting all host bits in prefix addressa and
+			 * originate.
+			 *
+			 * Eg: 1st Route : 10.0.0.0/16 - LSID:10.0.0.0
+			 *     2nd Route : 10.0.0.0/24 - LSID:10.0.0.255
+			 */
 			masklen2ip(p->prefixlen, &mask);
 
-			id.s_addr = p->prefix.s_addr | (~mask.s_addr);
-			lsa = ospf_lsdb_lookup_by_id(ospf->lsdb, type, id,
+			id->s_addr = p->prefix.s_addr | (~mask.s_addr);
+			lsa = ospf_lsdb_lookup_by_id(ospf->lsdb, type, *id,
 						     ospf->router_id);
 			if (lsa) {
 				if (IS_DEBUG_OSPF(lsa, LSA_GENERATE))
 					zlog_debug(
-						"ospf_lsa_unique_id(): Can't get Link State ID for %pFX",
-						p);
-				/* 	      id.s_addr = 0; */
-				id.s_addr = 0xffffffff;
-				return id;
+						"%s: Can't get Link State ID for %pFX",
+						__func__, p);
+				id->s_addr = 0xffffffff;
+				return LSID_NOT_AVAILABLE;
+			}
+		} else {
+			/* Ref rfc2328,Appendex E.3
+			 * the current prefix masklen is lesser than the
+			 * existing LSA,then the originated LSA has to be
+			 * refreshed by modifying masklen, cost and tag.
+			 * Originate the old route info with new LSID by
+			 * setting the host bits in prefix address.
+			 *
+			 * Eg: 1st Route : 10.0.0.0/24 - LSID:10.0.0.0
+			 *     2nd Route : 10.0.0.0/16 - ?
+			 * Since 2nd route mask len is less than firstone
+			 * LSID has to be changed.
+			 *     1st route LSID:10.0.0.255
+			 *     2nd route LSID:10.0.0.0
+			 */
+			id->s_addr = lsa->data->id.s_addr | (~al->mask.s_addr);
+			lsa = ospf_lsdb_lookup_by_id(ospf->lsdb, type, *id,
+						     ospf->router_id);
+			if (lsa && (ip_masklen(al->mask) != IPV4_MAX_BITLEN)) {
+				if (IS_DEBUG_OSPF(lsa, LSA_GENERATE))
+					zlog_debug(
+						"%s: Can't get Link State ID for %pFX",
+						__func__, p);
+				id->s_addr = 0xffffffff;
+				return LSID_NOT_AVAILABLE;
 			}
+			return LSID_CHANGE;
 		}
 	}
 
-	return id;
+	return LSID_AVAILABLE;
 }
 
 
diff --git a/ospfd/ospf_lsa.h b/ospfd/ospf_lsa.h
index a97957371..d04d11841 100644
--- a/ospfd/ospf_lsa.h
+++ b/ospfd/ospf_lsa.h
@@ -208,6 +208,8 @@ struct as_external_lsa {
 	} e[1];
 };
 
+enum lsid_status { LSID_AVAILABLE = 0, LSID_CHANGE, LSID_NOT_AVAILABLE };
+
 #include "ospfd/ospf_opaque.h"
 
 /* Macros. */
@@ -317,8 +319,10 @@ extern struct ospf_lsa *ospf_external_lsa_refresh(struct ospf *,
 						  struct ospf_lsa *,
 						  struct external_info *, int,
 						  bool aggr);
-extern struct in_addr ospf_lsa_unique_id(struct ospf *, struct ospf_lsdb *,
-					 uint8_t, struct prefix_ipv4 *);
+extern enum lsid_status ospf_lsa_unique_id(struct ospf *ospf,
+					   struct ospf_lsdb *lsdb,
+					   uint8_t type, struct prefix_ipv4 *p,
+					   struct in_addr *addr);
 extern void ospf_schedule_lsa_flood_area(struct ospf_area *, struct ospf_lsa *);
 extern void ospf_schedule_lsa_flush_area(struct ospf_area *, struct ospf_lsa *);