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.

1 files changed, 231 insertions, 6 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;
+}