From a0ea1751683d7fb242b9a8076b05058f21dfe052 Mon Sep 17 00:00:00 2001 From: Sander Vrijders Date: Fri, 14 Sep 2018 09:47:39 +0200 Subject: ipcpd: Simplify routing algorithm selection Previously there was a separate function per routing algorithm selection, when in fact the algorithms all take as input a graph and output a routing table, making it possible to place them in a single function. Signed-off-by: Sander Vrijders Signed-off-by: Dimitri Staessens --- src/ipcpd/normal/pol/graph.c | 127 +++++++++++++++++++------------------- src/ipcpd/normal/pol/graph.h | 10 +-- src/ipcpd/normal/pol/link_state.c | 37 +++++------ 3 files changed, 85 insertions(+), 89 deletions(-) diff --git a/src/ipcpd/normal/pol/graph.c b/src/ipcpd/normal/pol/graph.c index f3c053ab..544f0403 100644 --- a/src/ipcpd/normal/pol/graph.c +++ b/src/ipcpd/normal/pol/graph.c @@ -547,27 +547,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 +574,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 +597,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 +682,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 +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..59bae616 100644 --- a/src/ipcpd/normal/pol/link_state.c +++ b/src/ipcpd/normal/pol/link_state.c @@ -101,30 +101,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 +496,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 +899,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; -- cgit v1.2.3