summaryrefslogtreecommitdiff
path: root/src/ipcpd/normal/pol
diff options
context:
space:
mode:
Diffstat (limited to 'src/ipcpd/normal/pol')
-rw-r--r--src/ipcpd/normal/pol/flat.c4
-rw-r--r--src/ipcpd/normal/pol/graph.c131
-rw-r--r--src/ipcpd/normal/pol/graph.h10
-rw-r--r--src/ipcpd/normal/pol/link_state.c41
-rw-r--r--src/ipcpd/normal/pol/tests/graph_test.c8
5 files changed, 101 insertions, 93 deletions
diff --git a/src/ipcpd/normal/pol/flat.c b/src/ipcpd/normal/pol/flat.c
index cab74159..89b7fff6 100644
--- a/src/ipcpd/normal/pol/flat.c
+++ b/src/ipcpd/normal/pol/flat.c
@@ -20,7 +20,11 @@
* Foundation, Inc., http://www.fsf.org/about/contact/.
*/
+#if defined(__linux__) || defined(__CYGWIN__)
+#define _DEFAULT_SOURCE
+#else
#define _POSIX_C_SOURCE 200112L
+#endif
#define OUROBOROS_PREFIX "flat-addr-auth"
diff --git a/src/ipcpd/normal/pol/graph.c b/src/ipcpd/normal/pol/graph.c
index f3c053ab..ec0917c5 100644
--- a/src/ipcpd/normal/pol/graph.c
+++ b/src/ipcpd/normal/pol/graph.c
@@ -20,7 +20,11 @@
* Foundation, Inc., http://www.fsf.org/about/contact/.
*/
+#if defined(__linux__) || defined(__CYGWIN__)
+#define _DEFAULT_SOURCE
+#else
#define _POSIX_C_SOURCE 200112L
+#endif
#define OUROBOROS_PREFIX "graph"
@@ -547,27 +551,6 @@ static int graph_routing_table_simple(struct graph * graph,
return -1;
}
-int graph_routing_table(struct graph * graph,
- uint64_t s_addr,
- struct list_head * table)
-{
- int ret = 0;
- int * dist;
-
- assert(graph);
- assert(table);
-
- pthread_mutex_lock(&graph->lock);
-
- ret = graph_routing_table_simple(graph, s_addr, table, &dist);
-
- free(dist);
-
- pthread_mutex_unlock(&graph->lock);
-
- return ret;
-}
-
static int add_lfa_to_table(struct list_head * table,
uint64_t addr,
uint64_t lfa)
@@ -595,9 +578,10 @@ static int add_lfa_to_table(struct list_head * table,
return -1;
}
-int graph_routing_table_lfa(struct graph * graph,
- uint64_t s_addr,
- struct list_head * table)
+int graph_routing_table(struct graph * graph,
+ enum routing_algo algo,
+ uint64_t s_addr,
+ struct list_head * table)
{
int * s_dist;
int * n_dist[PROG_MAX_FLOWS];
@@ -617,66 +601,82 @@ int graph_routing_table_lfa(struct graph * graph,
pthread_mutex_lock(&graph->lock);
- for (j = 0; j < PROG_MAX_FLOWS; j++) {
- n_dist[j] = NULL;
- n_index[j] = -1;
- addrs[j] = -1;
- }
-
/* Get the normal next hops routing table. */
if (graph_routing_table_simple(graph, s_addr, table, &s_dist))
goto fail_table_simple;
- list_for_each(p, &graph->vertices) {
- v = list_entry(p, struct vertex, next);
+ /* 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;
+ }
- if (v->addr != s_addr)
- continue;
+ list_for_each(p, &graph->vertices) {
+ v = list_entry(p, struct vertex, next);
- /* Get the distances for every neighbor of the source. */
- list_for_each(q, &v->edges) {
- e = list_entry(q, struct edge, next);
+ if (v->addr != s_addr)
+ continue;
- addrs[i] = e->nb->addr;
- n_index[i] = e->nb->index;
- if (dijkstra(graph, e->nb->addr,
- &nhops, &(n_dist[i++])))
- goto fail_dijkstra;
+ /*
+ * Get the distances for every neighbor
+ * of the source.
+ */
+ list_for_each(q, &v->edges) {
+ e = list_entry(q, struct edge, next);
- free(nhops);
- }
+ addrs[i] = e->nb->addr;
+ n_index[i] = e->nb->index;
+ if (dijkstra(graph, e->nb->addr,
+ &nhops, &(n_dist[i++])))
+ goto fail_dijkstra;
- break;
- }
+ free(nhops);
+ }
- /* 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);
+ break;
+ }
- if (v->addr == s_addr)
- continue;
+ /* 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);
- /*
- * 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)
+ if (v->addr == s_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;
+ /*
+ * 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;
+ }
}
+
+ for (j = 0; j < i; j++)
+ free(n_dist[j]);
+
+ break;
+ default:
+ log_err("Unsupported algorithm.");
+ goto fail_algo;
}
pthread_mutex_unlock(&graph->lock);
- for (j = 0; j < i; j++)
- free(n_dist[j]);
-
free(s_dist);
return 0;
@@ -686,6 +686,7 @@ int graph_routing_table_lfa(struct graph * graph,
free(n_dist[k]);
fail_dijkstra:
free_routing_table(table);
+ fail_algo:
free(s_dist);
fail_table_simple:
pthread_mutex_unlock(&graph->lock);
diff --git a/src/ipcpd/normal/pol/graph.h b/src/ipcpd/normal/pol/graph.h
index 13657fd0..7cd14ad6 100644
--- a/src/ipcpd/normal/pol/graph.h
+++ b/src/ipcpd/normal/pol/graph.h
@@ -28,6 +28,11 @@
#include <inttypes.h>
+enum routing_algo {
+ ROUTING_SIMPLE = 0,
+ ROUTING_LFA
+};
+
struct nhop {
struct list_head next;
uint64_t nhop;
@@ -53,13 +58,10 @@ int graph_del_edge(struct graph * graph,
uint64_t d_addr);
int graph_routing_table(struct graph * graph,
+ enum routing_algo algo,
uint64_t s_addr,
struct list_head * table);
-int graph_routing_table_lfa(struct graph * graph,
- uint64_t s_addr,
- struct list_head * table);
-
void graph_free_routing_table(struct graph * graph,
struct list_head * table);
diff --git a/src/ipcpd/normal/pol/link_state.c b/src/ipcpd/normal/pol/link_state.c
index 1c418ffc..e2e9eab5 100644
--- a/src/ipcpd/normal/pol/link_state.c
+++ b/src/ipcpd/normal/pol/link_state.c
@@ -20,7 +20,11 @@
* Foundation, Inc., http://www.fsf.org/about/contact/.
*/
+#if defined(__linux__) || defined(__CYGWIN__)
+#define _DEFAULT_SOURCE
+#else
#define _POSIX_C_SOURCE 200112L
+#endif
#include "config.h"
@@ -101,30 +105,26 @@ struct nb {
enum nb_type type;
};
-typedef int (* rtable_fn_t)(struct graph * graph,
- uint64_t s_addr,
- struct list_head * table);
-
struct {
- struct list_head nbs;
- size_t nbs_len;
- fset_t * mgmt_set;
+ struct list_head nbs;
+ size_t nbs_len;
+ fset_t * mgmt_set;
- struct list_head db;
- size_t db_len;
+ struct list_head db;
+ size_t db_len;
- pthread_rwlock_t db_lock;
+ pthread_rwlock_t db_lock;
- struct graph * graph;
+ struct graph * graph;
- pthread_t lsupdate;
- pthread_t lsreader;
- pthread_t listener;
+ pthread_t lsupdate;
+ pthread_t lsreader;
+ pthread_t listener;
- struct list_head routing_instances;
- pthread_mutex_t routing_i_lock;
+ struct list_head routing_instances;
+ pthread_mutex_t routing_i_lock;
- rtable_fn_t rtable;
+ enum routing_algo routing_algo;
} ls;
struct pol_routing_ops link_state_ops = {
@@ -500,7 +500,8 @@ static void calculate_pff(struct routing_i * instance)
struct list_head * q;
int fds[PROG_MAX_FLOWS];
- if (ls.rtable(ls.graph, ipcpi.dt_addr, &table))
+ if (graph_routing_table(ls.graph, ls.routing_algo,
+ ipcpi.dt_addr, &table))
return;
pff_lock(instance->pff);
@@ -902,11 +903,11 @@ int link_state_init(enum pol_routing pr)
switch (pr) {
case ROUTING_LINK_STATE:
log_dbg("Using link state routing policy.");
- ls.rtable = graph_routing_table;
+ ls.routing_algo = ROUTING_SIMPLE;
break;
case ROUTING_LINK_STATE_LFA:
log_dbg("Using Loop-Free Alternates policy.");
- ls.rtable = graph_routing_table_lfa;
+ ls.routing_algo = ROUTING_LFA;
break;
default:
goto fail_graph;
diff --git a/src/ipcpd/normal/pol/tests/graph_test.c b/src/ipcpd/normal/pol/tests/graph_test.c
index d226398c..8050f73a 100644
--- a/src/ipcpd/normal/pol/tests/graph_test.c
+++ b/src/ipcpd/normal/pol/tests/graph_test.c
@@ -39,7 +39,7 @@ int graph_test_entries(int entries)
struct list_head * p;
int i = 0;
- if (graph_routing_table(graph, 1, &table)) {
+ if (graph_routing_table(graph, ROUTING_SIMPLE, 1, &table)) {
printf("Failed to get routing table.\n");
return -1;
}
@@ -63,7 +63,7 @@ int graph_test_double_link(void)
struct list_head * p;
int i = 0;
- if (graph_routing_table(graph, 1, &table)) {
+ if (graph_routing_table(graph, ROUTING_SIMPLE, 1, &table)) {
printf("Failed to get routing table.\n");
return -1;
}
@@ -101,7 +101,7 @@ int graph_test_single_link(void)
struct list_head * p;
int i = 0;
- if (graph_routing_table(graph, 1, &table)) {
+ if (graph_routing_table(graph, ROUTING_SIMPLE, 1, &table)) {
printf("Failed to get routing table.\n");
return -1;
}
@@ -243,7 +243,7 @@ int graph_test(int argc,
return -1;
}
- if (graph_routing_table(graph, 1, &table)) {
+ if (graph_routing_table(graph, ROUTING_SIMPLE, 1, &table)) {
printf("Failed to get routing table.\n");
return -1;
}