From bb30c4f0488d5d444fd316d716f59c824a01540f Mon Sep 17 00:00:00 2001 From: Sander Vrijders Date: Thu, 23 Mar 2017 15:51:42 +0100 Subject: ipcpd: normal: Add routing table calculation This adds routing table calculation to the graph component. The routing instances can then periodically ask the graph component for the routing table, and update their PFFs accordingly. --- src/ipcpd/normal/graph.c | 237 +++++++++++++++++++++++++++++++++++++++++++-- src/ipcpd/normal/graph.h | 23 ++--- src/ipcpd/normal/routing.c | 42 ++++++-- 3 files changed, 274 insertions(+), 28 deletions(-) (limited to 'src') diff --git a/src/ipcpd/normal/graph.c b/src/ipcpd/normal/graph.c index 2a7dbd9a..2ae36918 100644 --- a/src/ipcpd/normal/graph.c +++ b/src/ipcpd/normal/graph.c @@ -28,10 +28,30 @@ #include #include "graph.h" +#include "ipcp.h" #include #include #include +#include + +struct edge { + struct list_head next; + struct vertex * nb; + qosspec_t qs; +}; + +struct vertex { + struct list_head next; + uint64_t addr; + struct list_head edges; +}; + +struct graph { + size_t nr_vertices; + struct list_head vertices; + pthread_mutex_t lock; +}; static struct edge * find_edge_by_addr(struct vertex * vertex, uint64_t dst_addr) @@ -40,7 +60,7 @@ static struct edge * find_edge_by_addr(struct vertex * vertex, list_for_each(p, &vertex->edges) { struct edge * e = list_entry(p, struct edge, next); - if (e->dst_addr == dst_addr) + if (e->nb->addr == dst_addr) return e; } @@ -62,7 +82,7 @@ static struct vertex * find_vertex_by_addr(struct graph * graph, } static int add_edge(struct vertex * vertex, - uint64_t dst_addr, + struct vertex * nb, qosspec_t qs) { struct edge * edge; @@ -72,7 +92,7 @@ static int add_edge(struct vertex * vertex, return -ENOMEM; list_head_init(&edge->next); - edge->dst_addr = dst_addr; + edge->nb = nb; edge->qs = qs; list_add(&edge->next, &vertex->edges); @@ -177,7 +197,8 @@ int graph_add_edge(struct graph * graph, qosspec_t qs) { struct vertex * v; - struct edge * e; + struct edge * e; + struct vertex * nb; assert(graph); @@ -198,7 +219,15 @@ int graph_add_edge(struct graph * graph, return -1; } - if (add_edge(v, d_addr, qs)) { + nb = find_vertex_by_addr(graph, d_addr); + if (nb == NULL) { + if (add_vertex(graph, d_addr)) { + pthread_mutex_unlock(&graph->lock); + return -ENOMEM; + } + } + + if (add_edge(v, nb, qs)) { pthread_mutex_unlock(&graph->lock); log_err("Failed to add edge."); return -1; @@ -247,7 +276,8 @@ int graph_del_edge(struct graph * graph, uint64_t d_addr) { struct vertex * v; - struct edge * e; + struct edge * e; + struct vertex * nb; assert(graph); @@ -260,6 +290,13 @@ int graph_del_edge(struct graph * graph, return -1; } + nb = find_vertex_by_addr(graph, d_addr); + if (nb == NULL) { + pthread_mutex_unlock(&graph->lock); + log_err("No such vertex."); + return -1; + } + e = find_edge_by_addr(v, d_addr); if (e == NULL) { pthread_mutex_unlock(&graph->lock); @@ -273,7 +310,195 @@ int graph_del_edge(struct graph * graph, if (list_is_empty(&v->edges)) del_vertex(graph, v); + if (list_is_empty(&nb->edges)) + del_vertex(graph, v); + pthread_mutex_unlock(&graph->lock); return 0; } + +static int get_min_vertex(struct vertex ** vertices, + int nr_vertices, + int * dist, + struct vertex ** v) +{ + int min = INT_MAX; + int index = -1; + int i; + + *v = NULL; + + for (i = 0; i < nr_vertices; i++) { + if (vertices[i] == NULL) + continue; + + if (dist[i] < min) { + *v = vertices[i]; + min = dist[i]; + index = i; + } + } + + vertices[index] = NULL; + + return index; +} + +static int get_vertex_number(struct vertex ** vertices, + int nr_vertices, + struct vertex * v) + +{ + int i; + + for (i = 0; i < nr_vertices; i++) { + if (vertices[i] == v) + return i; + } + + return -1; +} + +static int get_vertex_index(struct graph * graph, + struct vertex * v) + +{ + struct list_head * p = NULL; + struct vertex * vertex; + int i = 0; + + list_for_each(p, &graph->vertices) { + vertex = list_entry(p, struct vertex, next); + if (vertex == v) + return i; + i++; + } + + return -1; +} + +static struct vertex ** dijkstra(struct graph * graph, + uint64_t src) +{ + int dist[graph->nr_vertices]; + struct vertex * vertices[graph->nr_vertices]; + struct list_head * p = NULL; + int i = 0; + int j = 0; + struct vertex * v = NULL; + struct edge * e = NULL; + int alt; + struct vertex ** prev; + + prev = malloc(sizeof(*prev) * graph->nr_vertices); + if (prev == NULL) + return NULL; + + list_for_each(p, &graph->vertices) { + v = list_entry(p, struct vertex, next); + vertices[i] = v; + if (v->addr == src) + dist[i] = 0; + else + dist[i] = INT_MAX; + prev[i] = NULL; + i++; + } + + i = get_min_vertex(vertices, graph->nr_vertices, dist, &v); + while (v != NULL) { + list_for_each(p, &v->edges) { + e = list_entry(p, struct edge, next); + + j = get_vertex_number(vertices, + graph->nr_vertices, + e->nb); + if (j == -1) + continue; + + /* + * NOTE: Current weight is just hop count. + * Method could be extended to use a different + * weight for a different QoS cube. + */ + alt = dist[i] + 1; + if (alt < dist[j]) { + dist[j] = alt; + prev[j] = v; + } + } + } + + return prev; +} + +ssize_t graph_routing_table(struct graph * graph, + uint64_t s_addr, + struct routing_table *** table) +{ + struct vertex ** prevs; + struct list_head * p = NULL; + int i = 0; + int index = 0; + int j = 0; + int k = 0; + struct vertex * prev; + struct vertex * nhop; + struct vertex * v; + + pthread_mutex_lock(&graph->lock); + + prevs = dijkstra(graph, s_addr); + if (prevs == NULL) { + pthread_mutex_unlock(&graph->lock); + return -1; + } + + *table = malloc(sizeof(**table) * (graph->nr_vertices - 1)); + if (*table == NULL) { + pthread_mutex_unlock(&graph->lock); + free(prevs); + return -1; + } + + list_for_each(p, &graph->vertices) { + v = list_entry(p, struct vertex, next); + prev = prevs[i]; + nhop = v; + + /* This is the src */ + if (prev == NULL) { + i++; + continue; + } + + index = get_vertex_index(graph, prev); + while (prevs[index] != NULL) { + nhop = prev; + prev = prevs[index]; + index = get_vertex_index(graph, prev); + } + + (*table)[++j] = malloc(sizeof(***table)); + if ((*table)[j] == NULL) { + pthread_mutex_unlock(&graph->lock); + for (k = 0; k < j; ++k) + free((*table)[k]); + free(*table); + free(prevs); + return -1; + } + + (*table)[j]->dst = v->addr; + (*table)[j]->nhop = nhop->addr; + + i++; + } + + pthread_mutex_unlock(&graph->lock); + + free(prevs); + + return j; +} diff --git a/src/ipcpd/normal/graph.h b/src/ipcpd/normal/graph.h index 9653efd7..226092c7 100644 --- a/src/ipcpd/normal/graph.h +++ b/src/ipcpd/normal/graph.h @@ -28,22 +28,9 @@ #include -struct edge { - struct list_head next; - uint64_t dst_addr; - qosspec_t qs; -}; - -struct vertex { - struct list_head next; - uint64_t addr; - struct list_head edges; -}; - -struct graph { - size_t nr_vertices; - struct list_head vertices; - pthread_mutex_t lock; +struct routing_table { + uint64_t dst; + uint64_t nhop; }; struct graph * graph_create(void); @@ -64,4 +51,8 @@ int graph_del_edge(struct graph * graph, uint64_t s_addr, uint64_t d_addr); +ssize_t graph_routing_table(struct graph * graph, + uint64_t s_addr, + struct routing_table *** table); + #endif /* OUROBOROS_IPCPD_NORMAL_GRAPH_H */ diff --git a/src/ipcpd/normal/routing.c b/src/ipcpd/normal/routing.c index 70999951..3a72bf36 100644 --- a/src/ipcpd/normal/routing.c +++ b/src/ipcpd/normal/routing.c @@ -44,15 +44,11 @@ typedef Fso fso_t; #define BUF_SIZE 256 - -struct routing_table_entry { - struct list_head next; - uint64_t dst; - uint64_t nhop; -}; +#define RECALC_TIME 4 struct routing_i { struct pff * pff; + pthread_t calculator; }; struct { @@ -66,6 +62,34 @@ struct { pthread_t rib_listener; } routing; +static void * calculate_pff(void * o) +{ + struct routing_table ** table; + ssize_t i; + int j; + + (void) o; + + while (true) { + i = graph_routing_table(routing.graph, ipcpi.dt_addr, &table); + if (table != NULL) { + /* + * FIXME: Calculate address to fd here + * and fill in PFF + */ + } + + for (j = 0; j < i; j++) { + free(table[j]); + } + free(table); + + sleep(RECALC_TIME); + } + + return (void *) 0; +} + struct routing_i * routing_i_create(struct pff * pff) { struct routing_i * tmp; @@ -78,6 +102,8 @@ struct routing_i * routing_i_create(struct pff * pff) tmp->pff = pff; + pthread_create(&tmp->calculator, NULL, calculate_pff, NULL); + return tmp; } @@ -85,6 +111,10 @@ void routing_i_destroy(struct routing_i * instance) { assert(instance); + pthread_cancel(instance->calculator); + + pthread_join(instance->calculator, NULL); + free(instance); } -- cgit v1.2.3