Merged in sandervrijders/ouroboros/be-dijkstra (pull request #416)

ipcpd: normal: Add routing table calculation

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;
+}