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.

3 files changed, 274 insertions, 28 deletions

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 <ouroboros/list.h>
 
 #include "graph.h"
+#include "ipcp.h"
 
 #include <assert.h>
 #include <pthread.h>
 #include <stdlib.h>
+#include <limits.h>
+
+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 <inttypes.h>
 
-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);
 }