Adding upstream version 8.4.4.upstream/8.4.4upstream

Signed-off-by: Daniel Baumann <daniel.baumann@progress-linux.org>

1 files changed, 646 insertions, 0 deletions

diff --git a/lib/cspf.c b/lib/cspf.c
new file mode 100644
index 0000000..ef3e7c2
--- /dev/null
+++ b/lib/cspf.c
@@ -0,0 +1,646 @@
+/*
+ * Constraints Shortest Path First algorithms - cspf.c
+ *
+ * Author: Olivier Dugeon <olivier.dugeon@orange.com>
+ *
+ * Copyright (C) 2022 Orange http://www.orange.com
+ *
+ * This file is part of Free Range Routing (FRR).
+ *
+ * FRR is free software; you can redistribute it and/or modify it
+ * under the terms of the GNU General Public License as published by the
+ * Free Software Foundation; either version 2, or (at your option) any
+ * later version.
+ *
+ * FRR is distributed in the hope that it will be useful, but
+ * WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
+ * General Public License for more details.
+ *
+ * You should have received a copy of the GNU General Public License along
+ * with this program; see the file COPYING; if not, write to the Free Software
+ * Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA
+ */
+
+#include <zebra.h>
+
+#include "if.h"
+#include "linklist.h"
+#include "log.h"
+#include "hash.h"
+#include "memory.h"
+#include "prefix.h"
+#include "table.h"
+#include "stream.h"
+#include "printfrr.h"
+#include "link_state.h"
+#include "cspf.h"
+
+/* Link State Memory allocation */
+DEFINE_MTYPE_STATIC(LIB, PCA, "Path Computation Algorithms");
+
+/**
+ * Create new Constrained Path. Memory is dynamically allocated.
+ *
+ * @param key	Vertex key of the destination of this path
+ *
+ * @return	Pointer to a new Constrained Path structure
+ */
+static struct c_path *cpath_new(uint64_t key)
+{
+	struct c_path *path;
+
+	/* Sanity Check */
+	if (key == 0)
+		return NULL;
+
+	path = XCALLOC(MTYPE_PCA, sizeof(struct c_path));
+	path->dst = key;
+	path->status = IN_PROGRESS;
+	path->edges = list_new();
+	path->weight = MAX_COST;
+
+	return path;
+}
+
+/**
+ * Copy src Constrained Path into dst Constrained Path. A new Constrained Path
+ * structure is dynamically allocated if dst is NULL. If src is NULL, the
+ * function return the dst disregarding if it is NULL or not.
+ *
+ * @param dest	Destination Constrained Path structure
+ * @param src	Source Constrained Path structure
+ *
+ * @return	Pointer to the destination Constrained Path structure
+ */
+static struct c_path *cpath_copy(struct c_path *dest, const struct c_path *src)
+{
+	struct c_path *new_path;
+
+	if (!src)
+		return dest;
+
+	if (!dest) {
+		new_path = XCALLOC(MTYPE_PCA, sizeof(struct c_path));
+	} else {
+		new_path = dest;
+		if (dest->edges)
+			list_delete(&new_path->edges);
+	}
+
+	new_path->dst = src->dst;
+	new_path->weight = src->weight;
+	new_path->edges = list_dup(src->edges);
+	new_path->status = src->status;
+
+	return new_path;
+}
+
+/**
+ * Delete Constrained Path structure. Previous allocated memory is freed.
+ *
+ * @param path	Constrained Path structure to be deleted
+ */
+static void cpath_del(struct c_path *path)
+{
+	if (!path)
+		return;
+
+	if (path->edges)
+		list_delete(&path->edges);
+
+	XFREE(MTYPE_PCA, path);
+	path = NULL;
+}
+
+/**
+ * Replace the list of edges in the next Constrained Path by the list of edges
+ * in the current Constrained Path.
+ *
+ * @param next_path	next Constrained Path structure
+ * @param cur_path	current Constrained Path structure
+ */
+static void cpath_replace(struct c_path *next_path, struct c_path *cur_path)
+{
+
+	if (next_path->edges)
+		list_delete(&next_path->edges);
+
+	next_path->edges = list_dup(cur_path->edges);
+}
+
+/**
+ * Create a new Visited Node structure from the provided Vertex. Structure is
+ * dynamically allocated.
+ *
+ * @param vertex	Vertex structure
+ *
+ * @return		Pointer to the new Visited Node structure
+ */
+static struct v_node *vnode_new(struct ls_vertex *vertex)
+{
+	struct v_node *vnode;
+
+	if (!vertex)
+		return NULL;
+
+	vnode = XCALLOC(MTYPE_PCA, sizeof(struct v_node));
+	vnode->vertex = vertex;
+	vnode->key = vertex->key;
+
+	return vnode;
+}
+
+/**
+ * Delete Visited Node structure. Previous allocated memory is freed.
+ *
+ * @param vnode		Visited Node structure to be deleted
+ */
+static void vnode_del(struct v_node *vnode)
+{
+	if (!vnode)
+		return;
+
+	XFREE(MTYPE_PCA, vnode);
+	vnode = NULL;
+}
+
+/**
+ * Search Vertex in TED by IPv4 address. The function search vertex by browsing
+ * the subnets table. It allows to find not only vertex by router ID, but also
+ * vertex by interface IPv4 address.
+ *
+ * @param ted	Traffic Engineering Database
+ * @param ipv4	IPv4 address
+ *
+ * @return	Vertex if found, NULL otherwise
+ */
+static struct ls_vertex *get_vertex_by_ipv4(struct ls_ted *ted,
+					    struct in_addr ipv4)
+{
+	struct ls_subnet *subnet;
+	struct prefix p;
+
+	p.family = AF_INET;
+	p.u.prefix4 = ipv4;
+
+	frr_each (subnets, &ted->subnets, subnet) {
+		if (subnet->key.family != AF_INET)
+			continue;
+		p.prefixlen = subnet->key.prefixlen;
+		if (prefix_same(&subnet->key, &p))
+			return subnet->vertex;
+	}
+
+	return NULL;
+}
+
+/**
+ * Search Vertex in TED by IPv6 address. The function search vertex by browsing
+ * the subnets table. It allows to find not only vertex by router ID, but also
+ * vertex by interface IPv6 address.
+ *
+ * @param ted	Traffic Engineering Database
+ * @param ipv6	IPv6 address
+ *
+ * @return	Vertex if found, NULL otherwise
+ */
+static struct ls_vertex *get_vertex_by_ipv6(struct ls_ted *ted,
+					    struct in6_addr ipv6)
+{
+	struct ls_subnet *subnet;
+	struct prefix p;
+
+	p.family = AF_INET6;
+	p.u.prefix6 = ipv6;
+
+	frr_each (subnets, &ted->subnets, subnet) {
+		if (subnet->key.family != AF_INET6)
+			continue;
+		p.prefixlen = subnet->key.prefixlen;
+		if (prefix_cmp(&subnet->key, &p) == 0)
+			return subnet->vertex;
+	}
+
+	return NULL;
+}
+
+struct cspf *cspf_new(void)
+{
+	struct cspf *algo;
+
+	/* Allocate New CSPF structure */
+	algo = XCALLOC(MTYPE_PCA, sizeof(struct cspf));
+
+	/* Initialize RB-Trees */
+	processed_init(&algo->processed);
+	visited_init(&algo->visited);
+	pqueue_init(&algo->pqueue);
+
+	algo->path = NULL;
+	algo->pdst = NULL;
+
+	return algo;
+}
+
+struct cspf *cspf_init(struct cspf *algo, const struct ls_vertex *src,
+		       const struct ls_vertex *dst, struct constraints *csts)
+{
+	struct cspf *new_algo;
+	struct c_path *psrc;
+
+	if (!csts)
+		return NULL;
+
+	if (!algo)
+		new_algo = cspf_new();
+	else
+		new_algo = algo;
+
+	/* Initialize Processed Path and Priority Queue with Src & Dst */
+	if (src) {
+		psrc = cpath_new(src->key);
+		psrc->weight = 0;
+		processed_add(&new_algo->processed, psrc);
+		pqueue_add(&new_algo->pqueue, psrc);
+		new_algo->path = psrc;
+	}
+	if (dst) {
+		new_algo->pdst = cpath_new(dst->key);
+		processed_add(&new_algo->processed, new_algo->pdst);
+	}
+
+	memcpy(&new_algo->csts, csts, sizeof(struct constraints));
+
+	return new_algo;
+}
+
+struct cspf *cspf_init_v4(struct cspf *algo, struct ls_ted *ted,
+			  const struct in_addr src, const struct in_addr dst,
+			  struct constraints *csts)
+{
+	struct ls_vertex *vsrc;
+	struct ls_vertex *vdst;
+	struct cspf *new_algo;
+
+	/* Sanity Check */
+	if (!ted)
+		return algo;
+
+	if (!algo)
+		new_algo = cspf_new();
+	else
+		new_algo = algo;
+
+	/* Got Source and Destination Vertex from TED */
+	vsrc = get_vertex_by_ipv4(ted, src);
+	vdst = get_vertex_by_ipv4(ted, dst);
+	csts->family = AF_INET;
+
+	return cspf_init(new_algo, vsrc, vdst, csts);
+}
+
+struct cspf *cspf_init_v6(struct cspf *algo, struct ls_ted *ted,
+			  const struct in6_addr src, const struct in6_addr dst,
+			  struct constraints *csts)
+{
+	struct ls_vertex *vsrc;
+	struct ls_vertex *vdst;
+	struct cspf *new_algo;
+
+	/* Sanity Check */
+	if (!ted)
+		return algo;
+
+	if (!algo)
+		new_algo = cspf_new();
+	else
+		new_algo = algo;
+
+	/* Got Source and Destination Vertex from TED */
+	vsrc = get_vertex_by_ipv6(ted, src);
+	vdst = get_vertex_by_ipv6(ted, dst);
+	csts->family = AF_INET6;
+
+	return cspf_init(new_algo, vsrc, vdst, csts);
+}
+
+void cspf_clean(struct cspf *algo)
+{
+	struct c_path *path;
+	struct v_node *vnode;
+
+	if (!algo)
+		return;
+
+	/* Normally, Priority Queue is empty. Clean it in case of. */
+	if (pqueue_count(&algo->pqueue)) {
+		frr_each_safe (pqueue, &algo->pqueue, path) {
+			pqueue_del(&algo->pqueue, path);
+		}
+	}
+
+	/* Empty Processed Path tree and associated Path */
+	if (processed_count(&algo->processed)) {
+		frr_each_safe (processed, &algo->processed, path) {
+			processed_del(&algo->processed, path);
+			cpath_del(path);
+		}
+	}
+
+	/* Empty visited Vertex tree and associated Node */
+	if (visited_count(&algo->visited)) {
+		frr_each_safe (visited, &algo->visited, vnode) {
+			visited_del(&algo->visited, vnode);
+			vnode_del(vnode);
+		}
+	}
+
+	memset(&algo->csts, 0, sizeof(struct constraints));
+	algo->path = NULL;
+	algo->pdst = NULL;
+}
+
+void cspf_del(struct cspf *algo)
+{
+	if (!algo)
+		return;
+
+	/* Empty Priority Queue and Processes Path */
+	cspf_clean(algo);
+
+	/* Then, reset Priority Queue, Processed Path and Visited RB-Tree */
+	pqueue_fini(&algo->pqueue);
+	processed_fini(&algo->processed);
+	visited_fini(&algo->visited);
+
+	XFREE(MTYPE_PCA, algo);
+	algo = NULL;
+}
+
+/**
+ * Prune Edge if constraints are not met by testing Edge Attributes against
+ * given constraints and cumulative cost of the given constrained path.
+ *
+ * @param path	On-going Computed Path with cumulative cost constraints
+ * @param edge	Edge to be validate against Constraints
+ * @param csts	Constraints for this path
+ *
+ * @return	True if Edge should be prune, false if Edge is valid
+ */
+static bool prune_edge(const struct c_path *path, const struct ls_edge *edge,
+		       const struct constraints *csts)
+{
+	struct ls_vertex *dst;
+	struct ls_attributes *attr;
+
+	/* Check that Path, Edge and Constraints are valid */
+	if (!path || !edge || !csts)
+		return true;
+
+	/* Check that Edge has a valid destination */
+	if (!edge->destination)
+		return true;
+	dst = edge->destination;
+
+	/* Check that Edge has valid attributes */
+	if (!edge->attributes)
+		return true;
+	attr = edge->attributes;
+
+	/* Check that Edge belongs to the requested Address Family and type */
+	if (csts->family == AF_INET) {
+		if (IPV4_NET0(attr->standard.local.s_addr))
+			return true;
+		if (csts->type == SR_TE)
+			if (!CHECK_FLAG(attr->flags, LS_ATTR_ADJ_SID) ||
+			    !CHECK_FLAG(dst->node->flags, LS_NODE_SR))
+				return true;
+	}
+	if (csts->family == AF_INET6) {
+		if (IN6_IS_ADDR_UNSPECIFIED(&attr->standard.local6))
+			return true;
+		if (csts->type == SR_TE)
+			if (!CHECK_FLAG(attr->flags, LS_ATTR_ADJ_SID6) ||
+			    !CHECK_FLAG(dst->node->flags, LS_NODE_SR))
+				return true;
+	}
+
+	/*
+	 * Check that total cost, up to this edge, respects the initial
+	 * constraints
+	 */
+	switch (csts->ctype) {
+	case CSPF_METRIC:
+		if (!CHECK_FLAG(attr->flags, LS_ATTR_METRIC))
+			return true;
+		if ((attr->metric + path->weight) > csts->cost)
+			return true;
+		break;
+
+	case CSPF_TE_METRIC:
+		if (!CHECK_FLAG(attr->flags, LS_ATTR_TE_METRIC))
+			return true;
+		if ((attr->standard.te_metric + path->weight) > csts->cost)
+			return true;
+		break;
+
+	case CSPF_DELAY:
+		if (!CHECK_FLAG(attr->flags, LS_ATTR_DELAY))
+			return true;
+		if ((attr->extended.delay + path->weight) > csts->cost)
+			return true;
+		break;
+	}
+
+	/* If specified, check that Edge meet Bandwidth constraint */
+	if (csts->bw > 0.0) {
+		if (attr->standard.max_bw < csts->bw ||
+		    attr->standard.max_rsv_bw < csts->bw ||
+		    attr->standard.unrsv_bw[csts->cos] < csts->bw)
+			return true;
+	}
+
+	/* All is fine. We can consider this Edge valid, so not to be prune */
+	return false;
+}
+
+/**
+ * Relax constraints of the current path up to the destination vertex of the
+ * provided Edge. This function progress in the network topology by validating
+ * the next vertex on the computed path. If Vertex has not already been visited,
+ * list of edges of the current path is augmented with this edge if the new cost
+ * is lower than prior path up to this vertex. Current path is re-inserted in
+ * the Priority Queue with its new cost i.e. current cost + edge cost.
+ *
+ * @param algo	CSPF structure
+ * @param edge	Next Edge to be added to the current computed path
+ *
+ * @return	True if current path reach destination, false otherwise
+ */
+static bool relax_constraints(struct cspf *algo, struct ls_edge *edge)
+{
+
+	struct c_path pkey = {};
+	struct c_path *next_path;
+	struct v_node vnode = {};
+	uint32_t total_cost = MAX_COST;
+
+	/* Verify that we have a current computed path */
+	if (!algo->path)
+		return false;
+
+	/* Verify if we have not visited the next Vertex to avoid loop */
+	vnode.key = edge->destination->key;
+	if (visited_member(&algo->visited, &vnode)) {
+		return false;
+	}
+
+	/*
+	 * Get Next Computed Path from next vertex key
+	 * or create a new one if it has not yet computed.
+	 */
+	pkey.dst = edge->destination->key;
+	next_path = processed_find(&algo->processed, &pkey);
+	if (!next_path) {
+		next_path = cpath_new(pkey.dst);
+		processed_add(&algo->processed, next_path);
+	}
+
+	/*
+	 * Add or update the Computed Path in the Priority Queue if total cost
+	 * is lower than cost associated to this next Vertex. This could occurs
+	 * if we process a Vertex that as not yet been visited in the Graph
+	 * or if we found a shortest path up to this Vertex.
+	 */
+	switch (algo->csts.ctype) {
+	case CSPF_METRIC:
+		total_cost = edge->attributes->metric + algo->path->weight;
+		break;
+	case CSPF_TE_METRIC:
+		total_cost = edge->attributes->standard.te_metric +
+			     algo->path->weight;
+		break;
+	case CSPF_DELAY:
+		total_cost =
+			edge->attributes->extended.delay + algo->path->weight;
+		break;
+	default:
+		break;
+	}
+	if (total_cost < next_path->weight) {
+		/*
+		 * It is not possible to directly update the q_path in the
+		 * Priority Queue. Indeed, if we modify the path weight, the
+		 * Priority Queue must be re-ordered. So, we need fist to remove
+		 * the q_path if it is present in the Priority Queue, then,
+		 * update the Path, in particular the Weight, and finally
+		 * (re-)insert it in the Priority Queue.
+		 */
+		struct c_path *path;
+		frr_each_safe (pqueue, &algo->pqueue, path) {
+			if (path->dst == pkey.dst) {
+				pqueue_del(&algo->pqueue, path);
+				break;
+			}
+		}
+		next_path->weight = total_cost;
+		cpath_replace(next_path, algo->path);
+		listnode_add(next_path->edges, edge);
+		pqueue_add(&algo->pqueue, next_path);
+	}
+
+	/* Return True if we reach the destination */
+	return (next_path->dst == algo->pdst->dst);
+}
+
+struct c_path *compute_p2p_path(struct cspf *algo, struct ls_ted *ted)
+{
+	struct listnode *node;
+	struct ls_vertex *vertex;
+	struct ls_edge *edge;
+	struct c_path *optim_path;
+	struct v_node *vnode;
+	uint32_t cur_cost;
+
+	optim_path = cpath_new(0xFFFFFFFFFFFFFFFF);
+	optim_path->status = FAILED;
+
+	/* Check that all is correctly initialized */
+	if (!algo)
+		return optim_path;
+
+	if (!algo->csts.ctype)
+		return optim_path;
+
+	if (!algo->pdst) {
+		optim_path->status = NO_DESTINATION;
+		return optim_path;
+	}
+
+	if (!algo->path) {
+		optim_path->status = NO_SOURCE;
+		return optim_path;
+	}
+
+	if (algo->pdst->dst == algo->path->dst) {
+		optim_path->status = SAME_SRC_DST;
+		return optim_path;
+	}
+
+	optim_path->dst = algo->pdst->dst;
+	optim_path->status = IN_PROGRESS;
+
+	/*
+	 * Process all Connected Vertex until priority queue becomes empty.
+	 * Connected Vertices are added into the priority queue when
+	 * processing the next Connected Vertex: see relax_constraints()
+	 */
+	cur_cost = MAX_COST;
+	while (pqueue_count(&algo->pqueue) != 0) {
+		/* Got shortest current Path from the Priority Queue */
+		algo->path = pqueue_pop(&algo->pqueue);
+
+		/* Add destination Vertex of this path to the visited RB Tree */
+		vertex = ls_find_vertex_by_key(ted, algo->path->dst);
+		if (!vertex)
+			continue;
+		vnode = vnode_new(vertex);
+		visited_add(&algo->visited, vnode);
+
+		/* Process all outgoing links from this Vertex */
+		for (ALL_LIST_ELEMENTS_RO(vertex->outgoing_edges, node, edge)) {
+			/*
+			 * Skip Connected Edges that must be prune i.e.
+			 * Edges that not satisfy the given constraints,
+			 * in particular the Bandwidth, TE Metric and Delay.
+			 */
+			if (prune_edge(algo->path, edge, &algo->csts))
+				continue;
+
+			/*
+			 * Relax constraints and check if we got a shorter
+			 * candidate path
+			 */
+			if (relax_constraints(algo, edge) &&
+			    algo->pdst->weight < cur_cost) {
+				cur_cost = algo->pdst->weight;
+				cpath_copy(optim_path, algo->pdst);
+				optim_path->status = SUCCESS;
+			}
+		}
+	}
+
+	/*
+	 * The priority queue is empty => all the possible (vertex, path)
+	 * elements have been explored. The optim_path contains the optimal
+	 * path if it exists. Otherwise an empty path with status failed is
+	 * returned.
+	 */
+	if (optim_path->status == IN_PROGRESS ||
+	    listcount(optim_path->edges) == 0)
+		optim_path->status = FAILED;
+	cspf_clean(algo);
+
+	return optim_path;
+}