From 133e59cfad8700d3fb71484ff574ab9fdc73299e Mon Sep 17 00:00:00 2001
From: GalaxyGorilla <sascha@netdef.org>
Date: Tue, 13 Oct 2020 11:53:04 +0000
Subject: [PATCH] ospfd: Add support for reverse SPF (P2P only)

A reverse SPF is important in the context of TI-LFA, e.g. for
computing so called Q spaces. In case the weights of the links are
symmetric there is no difference to the 'normal' SPF and hence this
patch is really just needed for the case with asymmetric link
weights.

Signed-off-by: GalaxyGorilla <sascha@netdef.org>
---
 ospfd/ospf_spf.c    | 59 ++++++++++++++++++++++++++++++++++++++++++++-
 ospfd/ospf_ti_lfa.c |  6 ++++-
 ospfd/ospfd.h       |  3 +++
 3 files changed, 66 insertions(+), 2 deletions(-)

diff --git a/ospfd/ospf_spf.c b/ospfd/ospf_spf.c
index 6023b85a57..3a5647ee9f 100644
--- a/ospfd/ospf_spf.c
+++ b/ospfd/ospf_spf.c
@@ -1099,6 +1099,51 @@ static int ospf_spf_is_protected_link(struct ospf_area *area,
 	return 0;
 }
 
+/*
+ * For TI-LFA we need the reverse SPF for Q spaces. The reverse SPF is created
+ * by honoring the weight of the reverse 'edge', e.g. the edge from W to V, and
+ * NOT the weight of the 'edge' from V to W as usual. Hence we need to find the
+ * corresponding link in the LSA of W and extract the particular weight.
+ *
+ * TODO: Only P2P supported by now!
+ */
+static uint16_t get_reverse_distance(struct vertex *v,
+				     struct router_lsa_link *l,
+				     struct ospf_lsa *w_lsa)
+{
+	uint8_t *p, *lim;
+	struct router_lsa_link *w_link;
+	uint16_t distance = 0;
+
+	p = ((uint8_t *)w_lsa->data) + OSPF_LSA_HEADER_SIZE + 4;
+	lim = ((uint8_t *)w_lsa->data) + ntohs(w_lsa->data->length);
+
+	while (p < lim) {
+		w_link = (struct router_lsa_link *)p;
+		p += (OSPF_ROUTER_LSA_LINK_SIZE
+		      + (w_link->m[0].tos_count * OSPF_ROUTER_LSA_TOS_SIZE));
+
+		/* Only care about P2P with link ID equal to V's router id */
+		if (w_link->m[0].type == LSA_LINK_TYPE_POINTOPOINT
+		    && w_link->link_id.s_addr == v->id.s_addr) {
+			distance = ntohs(w_link->m[0].metric);
+			break;
+		}
+	}
+
+	/*
+	 * This might happen if the LSA for W is not complete yet. In this
+	 * case we take the weight of the 'forward' link from V. When the LSA
+	 * for W is completed the reverse SPF is run again anyway.
+	 */
+	if (distance == 0)
+		distance = ntohs(l->m[0].metric);
+
+	zlog_debug("%s: reversed distance is %u", __func__, distance);
+
+	return distance;
+}
+
 /*
  * RFC2328 16.1 (2).
  * v is on the SPF tree. Examine the links in v's LSA. Update the list of
@@ -1114,6 +1159,7 @@ static void ospf_spf_next(struct vertex *v, struct ospf_area *area,
 	struct router_lsa_link *l = NULL;
 	struct in_addr *r;
 	int type = 0, lsa_pos = -1, lsa_pos_next = 0;
+	uint16_t link_distance;
 
 	/*
 	 * If this is a router-LSA, and bit V of the router-LSA (see Section
@@ -1202,8 +1248,19 @@ static void ospf_spf_next(struct vertex *v, struct ospf_area *area,
 				continue;
 			}
 
+			/*
+			 * For TI-LFA we might need the reverse SPF.
+			 * Currently only works with P2P!
+			 */
+			if (type == LSA_LINK_TYPE_POINTOPOINT
+			    && area->spf_reversed)
+				link_distance =
+					get_reverse_distance(v, l, w_lsa);
+			else
+				link_distance = ntohs(l->m[0].metric);
+
 			/* step (d) below */
-			distance = v->distance + ntohs(l->m[0].metric);
+			distance = v->distance + link_distance;
 		} else {
 			/* In case of V is Network-LSA. */
 			r = (struct in_addr *)p;
diff --git a/ospfd/ospf_ti_lfa.c b/ospfd/ospf_ti_lfa.c
index 61c278575c..b0a10845c5 100644
--- a/ospfd/ospf_ti_lfa.c
+++ b/ospfd/ospf_ti_lfa.c
@@ -249,11 +249,15 @@ static void ospf_ti_lfa_generate_q_spaces(struct ospf_area *area,
 	new_rtrs = route_table_init();
 
 	/*
-	 * Generate a new SPF tree for this vertex,
+	 * Generate a new (reversed!) SPF tree for this vertex,
 	 * dry run true, root node false
 	 */
+	area->spf_reversed = true;
 	ospf_spf_calculate(area, dest->lsa_p, new_table, new_rtrs, true, false);
 
+	/* Reset the flag for reverse SPF */
+	area->spf_reversed = false;
+
 	q_space->root = area->spf;
 	q_space->vertex_list = area->spf_vertex_list;
 	q_space->label_stack = NULL;
diff --git a/ospfd/ospfd.h b/ospfd/ospfd.h
index 420e6f22eb..ad8f561610 100644
--- a/ospfd/ospfd.h
+++ b/ospfd/ospfd.h
@@ -525,6 +525,9 @@ struct ospf_area {
 	/* Statistics field. */
 	uint32_t spf_calculation; /* SPF Calculation Count. */
 
+	/* reverse SPF (used for TI-LFA Q spaces) */
+	bool spf_reversed;
+
 	/* Time stamps. */
 	struct timeval ts_spf; /* SPF calculation time stamp. */
 
-- 
2.39.5