From a63edb8e9d3ba5eef03c1bbb454522ea7b369087 Mon Sep 17 00:00:00 2001
From: Dimitri Staessens <dimitri@ouroboros.rocks>
Date: Wed, 12 Feb 2020 22:31:16 +0100
Subject: ipcpd: Refactor graph to self-contain LFA
The LFA algorithm modifies the output of the simple routing algorithm,
but the output was mixed in the general call. This moves the LFA
subroutine to be self-contained. This makes for a cleaner entry point
when adding more routing algorithms.
Signed-off-by: Dimitri Staessens <dimitri@ouroboros.rocks>
Signed-off-by: Sander Vrijders <sander@ouroboros.rocks>
---
src/ipcpd/unicast/pol/graph.c | 158 +++++++++++++++++++++++-------------------
1 file changed, 86 insertions(+), 72 deletions(-)
(limited to 'src')
diff --git a/src/ipcpd/unicast/pol/graph.c b/src/ipcpd/unicast/pol/graph.c
index 379d6b95..d5c1a9e9 100644
--- a/src/ipcpd/unicast/pol/graph.c
+++ b/src/ipcpd/unicast/pol/graph.c
@@ -578,12 +578,11 @@ static int add_lfa_to_table(struct list_head * table,
return -1;
}
-int graph_routing_table(struct graph * graph,
- enum routing_algo algo,
- uint64_t s_addr,
- struct list_head * table)
+static int graph_routing_table_lfa(struct graph * graph,
+ uint64_t s_addr,
+ struct list_head * table,
+ int ** dist)
{
- int * s_dist;
int * n_dist[PROG_MAX_FLOWS];
uint64_t addrs[PROG_MAX_FLOWS];
int n_index[PROG_MAX_FLOWS];
@@ -592,83 +591,104 @@ int graph_routing_table(struct graph * graph,
struct vertex * v;
struct edge * e;
struct vertex ** nhops;
- int i = 0;
- int j = 0;
+ int i;
+ int j;
int k;
- assert(graph);
- assert(table);
-
- pthread_mutex_lock(&graph->lock);
+ if (graph_routing_table_lfa(graph, s_addr, table, dist))
+ goto fail_table;
- /* Get the simple next hops routing table. */
- if (graph_routing_table_simple(graph, s_addr, table, &s_dist))
- goto fail_table_simple;
+ for (j = 0; j < PROG_MAX_FLOWS; j++) {
+ n_dist[j] = NULL;
+ n_index[j] = -1;
+ addrs[j] = -1;
+ }
- /* Possibly augment the routing table. */
- switch (algo) {
- case ROUTING_SIMPLE:
- break;
- case ROUTING_LFA:
- for (j = 0; j < PROG_MAX_FLOWS; j++) {
- n_dist[j] = NULL;
- n_index[j] = -1;
- addrs[j] = -1;
- }
+ list_for_each(p, &graph->vertices) {
+ v = list_entry(p, struct vertex, next);
- list_for_each(p, &graph->vertices) {
- v = list_entry(p, struct vertex, next);
+ if (v->addr != s_addr)
+ continue;
- if (v->addr != s_addr)
- continue;
+ /*
+ * Get the distances for every neighbor
+ * of the source.
+ */
+ list_for_each(q, &v->edges) {
+ e = list_entry(q, struct edge, next);
- /*
- * Get the distances for every neighbor
- * of the source.
- */
- list_for_each(q, &v->edges) {
- e = list_entry(q, struct edge, next);
+ addrs[i] = e->nb->addr;
+ n_index[i] = e->nb->index;
+ if (dijkstra(graph, e->nb->addr,
+ &nhops, &(n_dist[i++])))
+ goto fail_dijkstra;
- addrs[i] = e->nb->addr;
- n_index[i] = e->nb->index;
- if (dijkstra(graph, e->nb->addr,
- &nhops, &(n_dist[i++])))
- goto fail_dijkstra;
+ free(nhops);
+ }
- free(nhops);
- }
+ break;
+ }
- break;
- }
+ /* Loop though all nodes to see if we have a LFA for them. */
+ list_for_each(p, &graph->vertices) {
+ v = list_entry(p, struct vertex, next);
- /* Loop though all nodes to see if we have a LFA for them. */
- list_for_each(p, &graph->vertices) {
- v = list_entry(p, struct vertex, next);
+ if (v->addr == s_addr)
+ continue;
- if (v->addr == s_addr)
+ /*
+ * Check for every neighbor if
+ * dist(neighbor, destination) <
+ * dist(neighbor, source) + dist(source, destination).
+ */
+ for (j = 0; j < i; j++) {
+ /* Exclude ourselves. */
+ if (addrs[j] == v->addr)
continue;
- /*
- * Check for every neighbor if
- * dist(neighbor, destination) <
- * dist(neighbor, source) + dist(source, destination).
- */
- for (j = 0; j < i; j++) {
- /* Exclude ourselves. */
- if (addrs[j] == v->addr)
- continue;
-
- if (n_dist[j][v->index] <
- s_dist[n_index[j]] + s_dist[v->index])
- if (add_lfa_to_table(table, v->addr,
- addrs[j]))
- goto fail_add_lfa;
- }
+ if (n_dist[j][v->index] <
+ *dist[n_index[j]] + *dist[v->index])
+ if (add_lfa_to_table(table, v->addr,
+ addrs[j]))
+ goto fail_add_lfa;
}
+ }
+
+ for (j = 0; j < i; j++)
+ free(n_dist[j]);
+
+ return 0;
+
+ fail_add_lfa:
+ for (k = j; k < i; k++)
+ free(n_dist[k]);
+ fail_dijkstra:
+ free_routing_table(table);
+ fail_table:
+ return -1;
+}
+
+int graph_routing_table(struct graph * graph,
+ enum routing_algo algo,
+ uint64_t s_addr,
+ struct list_head * table)
+{
+ int * s_dist;
+
+ assert(graph);
+ assert(table);
- for (j = 0; j < i; j++)
- free(n_dist[j]);
+ pthread_mutex_lock(&graph->lock);
+ switch (algo) {
+ case ROUTING_SIMPLE:
+ /* LFA uses the s_dist this returns. */
+ if (graph_routing_table_simple(graph, s_addr, table, &s_dist))
+ goto fail_table;
+ break;
+ case ROUTING_LFA:
+ if (graph_routing_table_lfa(graph, s_addr, table, &s_dist))
+ goto fail_table;
break;
default:
log_err("Unsupported algorithm.");
@@ -681,15 +701,9 @@ int graph_routing_table(struct graph * graph,
return 0;
- fail_add_lfa:
- for (k = j; k < i; k++)
- free(n_dist[k]);
- fail_dijkstra:
- free_routing_table(table);
fail_algo:
free(s_dist);
- fail_table_simple:
+ fail_table:
pthread_mutex_unlock(&graph->lock);
-
return -1;
}
--
cgit v1.2.3