ipcpd: normal: Add Loop-Free Alternates routing

This adds the Loop-Free Alternates (LFA) policy. In case a link goes
down a LFA may be selected to route the SDUs on without causing loops
instead of the main hop that just went down.

8 files changed, 229 insertions, 56 deletions

diff --git a/include/ouroboros/ipcp.h b/include/ouroboros/ipcp.h
index 1b578fa2..3e682225 100644
--- a/include/ouroboros/ipcp.h
+++ b/include/ouroboros/ipcp.h
@@ -46,7 +46,8 @@ enum pol_addr_auth {
 };
 
 enum pol_routing {
-        ROUTING_LINK_STATE = 0
+        ROUTING_LINK_STATE = 0,
+        ROUTING_LINK_STATE_LFA
 };
 
 enum pol_pff {
diff --git a/src/ipcpd/normal/pol-routing-ops.h b/src/ipcpd/normal/pol-routing-ops.h
index 9804d5ad..aa968e9f 100644
--- a/src/ipcpd/normal/pol-routing-ops.h
+++ b/src/ipcpd/normal/pol-routing-ops.h
@@ -26,7 +26,7 @@
 #include "pff.h"
 
 struct pol_routing_ops {
-        int                (* init)(void);
+        int                (* init)(enum pol_routing pr);
 
         void               (* fini)(void);
 
diff --git a/src/ipcpd/normal/pol/graph.c b/src/ipcpd/normal/pol/graph.c
index 9e723737..eade23e0 100644
--- a/src/ipcpd/normal/pol/graph.c
+++ b/src/ipcpd/normal/pol/graph.c
@@ -379,37 +379,43 @@ static int get_min_vertex(struct graph *   graph,
         return index;
 }
 
-static struct vertex ** dijkstra(struct graph * graph,
-                                 uint64_t       src)
+static int dijkstra(struct graph *    graph,
+                    uint64_t          src,
+                    struct vertex *** nhops,
+                    int **            dist)
 {
-        int                dist[graph->nr_vertices];
         bool               used[graph->nr_vertices];
         struct list_head * p = NULL;
         int                i = 0;
         struct vertex *    v = NULL;
         struct edge *      e = NULL;
         int                alt;
-        struct vertex **   nhop;
 
-        nhop = malloc(sizeof(*nhop) * graph->nr_vertices);
-        if (nhop == NULL)
-                return NULL;
+        *nhops = malloc(sizeof(**nhops) * graph->nr_vertices);
+        if (*nhops == NULL)
+                return -1;
+
+        *dist = malloc(sizeof(**dist) * graph->nr_vertices);
+        if (*dist == NULL) {
+                free(*nhops);
+                return -1;
+        }
 
         /* Init the data structures */
         list_for_each(p, &graph->vertices) {
                 v = list_entry(p, struct vertex, next);
                 if (v->addr == src)
-                        dist[i] = 0;
+                        (*dist)[i] = 0;
                 else
-                        dist[i] = INT_MAX;
+                        (*dist)[i] = INT_MAX;
 
-                nhop[i] = NULL;
+                (*nhops)[i] = NULL;
                 used[i] = false;
                 i++;
         }
 
         /* Perform actual Dijkstra */
-        i = get_min_vertex(graph, dist, used, &v);
+        i = get_min_vertex(graph, *dist, used, &v);
         while (v != NULL) {
                 list_for_each(p, &v->edges) {
                         e = list_entry(p, struct edge, next);
@@ -423,19 +429,19 @@ static struct vertex ** dijkstra(struct graph * graph,
                          * Method could be extended to use a different
                          * weight for a different QoS cube.
                          */
-                        alt = dist[i] + 1;
-                        if (alt < dist[e->nb->index]) {
-                                dist[e->nb->index] = alt;
+                        alt = (*dist)[i] + 1;
+                        if (alt < (*dist)[e->nb->index]) {
+                                (*dist)[e->nb->index] = alt;
                                 if (v->addr == src)
-                                        nhop[e->nb->index] = e->nb;
+                                        (*nhops)[e->nb->index] = e->nb;
                                 else
-                                        nhop[e->nb->index] = nhop[i];
+                                        (*nhops)[e->nb->index] = (*nhops)[i];
                         }
                 }
-                i = get_min_vertex(graph, dist, used, &v);
+                i = get_min_vertex(graph, *dist, used, &v);
         }
 
-        return nhop;
+        return 0;
 }
 
 static void free_routing_table(struct list_head * table)
@@ -471,9 +477,10 @@ void graph_free_routing_table(struct graph *     graph,
         pthread_mutex_unlock(&graph->lock);
 }
 
-int graph_routing_table(struct graph *     graph,
-                        uint64_t           s_addr,
-                        struct list_head * table)
+static int graph_routing_table_simple(struct graph *     graph,
+                                      uint64_t           s_addr,
+                                      struct list_head * table,
+                                      int **             dist)
 {
         struct vertex **       nhops;
         struct list_head *     p;
@@ -482,14 +489,11 @@ int graph_routing_table(struct graph *     graph,
         struct routing_table * t;
         struct nhop *          n;
 
-        pthread_mutex_lock(&graph->lock);
-
         /* We need at least 2 vertices for a table */
         if (graph->nr_vertices < 2)
                 goto fail_vertices;
 
-        nhops = dijkstra(graph, s_addr);
-        if (nhops == NULL)
+        if (dijkstra(graph, s_addr, &nhops, dist))
                 goto fail_vertices;
 
         list_head_init(table);
@@ -523,8 +527,6 @@ int graph_routing_table(struct graph *     graph,
                 i++;
         }
 
-        pthread_mutex_unlock(&graph->lock);
-
         free(nhops);
 
         return 0;
@@ -535,6 +537,149 @@ int graph_routing_table(struct graph *     graph,
         free_routing_table(table);
         free(nhops);
  fail_vertices:
+        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)
+{
+        struct list_head * p = NULL;
+        struct nhop *      n;
+
+        n = malloc(sizeof(*n));
+        if (n == NULL)
+                return -1;
+
+        n->nhop = lfa;
+
+        list_for_each(p, table) {
+                struct routing_table * t =
+                        list_entry(p, struct routing_table, next);
+                if (t->dst == addr) {
+                        list_add_tail(&n->next, &t->nhops);
+                        return 0;
+                }
+        }
+
+        return -1;
+}
+
+int graph_routing_table_lfa(struct graph *     graph,
+                            uint64_t           s_addr,
+                            struct list_head * table)
+{
+        int *              s_dist;
+        int *              n_dist[AP_MAX_FLOWS];
+        uint64_t           addrs[AP_MAX_FLOWS];
+        int                n_index[AP_MAX_FLOWS];
+        struct list_head * p;
+        struct list_head * q;
+        struct vertex *    v;
+        struct edge *      e;
+        struct vertex **   nhops;
+        int                i = 0;
+        int                j = 0;
+        int                k;
+
+        assert(graph);
+        assert(table);
+
+        pthread_mutex_lock(&graph->lock);
+
+        for (j = 0; j < AP_MAX_FLOWS; j++) {
+                n_dist[i] = NULL;
+                n_index[i] = -1;
+                addrs[i] = -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);
+
+                if (v->addr != s_addr)
+                        continue;
+
+                /* Get the distances for every neighbor of the source. */
+                list_for_each(q, &v->edges) {
+                        e = list_entry(q, struct edge, next);
+
+                        addrs[i] = e->nb->addr;
+                        n_index[i] = e->nb->index;
+                        if (dijkstra(graph, e->nb->addr,
+                                     &nhops, &(n_dist[i++])))
+                                goto fail_dijkstra;
+
+                        free(nhops);
+                }
+
+                break;
+        }
+
+        /* 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);
+
+                if (v->addr == s_addr)
+                        continue;
+
+                /*
+                 * 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;
+                        }
+
+                        free(n_dist[j]);
+                }
+        }
+
+        pthread_mutex_unlock(&graph->lock);
+
+        free(s_dist);
+
+        return 0;
+
+ fail_add_lfa:
+        for (k = j; k < i; k++)
+                free(n_dist[k]);
+ fail_dijkstra:
+        free_routing_table(table);
+        free(s_dist);
+ fail_table_simple:
+        pthread_mutex_unlock(&graph->lock);
+
         return -1;
 }
diff --git a/src/ipcpd/normal/pol/graph.h b/src/ipcpd/normal/pol/graph.h
index 7340ecb9..66c8f780 100644
--- a/src/ipcpd/normal/pol/graph.h
+++ b/src/ipcpd/normal/pol/graph.h
@@ -56,6 +56,10 @@ int            graph_routing_table(struct graph *     graph,
                                    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 51d317bc..6330cf81 100644
--- a/src/ipcpd/normal/pol/link_state.c
+++ b/src/ipcpd/normal/pol/link_state.c
@@ -89,6 +89,10 @@ 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;
         fset_t *         mgmt_set;
@@ -103,6 +107,8 @@ struct {
         pthread_t        lsupdate;
         pthread_t        lsreader;
         pthread_t        listener;
+
+        rtable_fn_t      rtable;
 } ls;
 
 struct pol_routing_ops link_state_ops = {
@@ -388,7 +394,7 @@ static void * calculate_pff(void * o)
         instance = (struct routing_i *) o;
 
         while (true) {
-                if (graph_routing_table(ls.graph, ipcpi.dt_addr, &table)) {
+                if (ls.rtable(ls.graph, ipcpi.dt_addr, &table)) {
                         sleep(RECALC_TIME);
                         continue;
                 }
@@ -664,7 +670,7 @@ void link_state_routing_i_destroy(struct routing_i * instance)
         free(instance);
 }
 
-int link_state_init(void)
+int link_state_init(enum pol_routing pr)
 {
         struct conn_info info;
 
@@ -676,6 +682,17 @@ int link_state_init(void)
         info.pref_syntax  = PROTO_GPB;
         info.addr         = ipcpi.dt_addr;
 
+        switch (pr) {
+        case ROUTING_LINK_STATE:
+                ls.rtable = graph_routing_table;
+                break;
+        case ROUTING_LINK_STATE_LFA:
+                ls.rtable = graph_routing_table_lfa;
+                break;
+        default:
+                goto fail_graph;
+        }
+
         ls.graph = graph_create();
         if (ls.graph == NULL)
                 goto fail_graph;
diff --git a/src/ipcpd/normal/pol/link_state.h b/src/ipcpd/normal/pol/link_state.h
index 58f90d91..cfdeb09d 100644
--- a/src/ipcpd/normal/pol/link_state.h
+++ b/src/ipcpd/normal/pol/link_state.h
@@ -28,7 +28,7 @@
 
 #include "pol-routing-ops.h"
 
-int                link_state_init(void);
+int                link_state_init(enum pol_routing pr);
 
 void               link_state_fini(void);
 
diff --git a/src/ipcpd/normal/routing.c b/src/ipcpd/normal/routing.c
index afef23a2..909f74cc 100644
--- a/src/ipcpd/normal/routing.c
+++ b/src/ipcpd/normal/routing.c
@@ -33,13 +33,14 @@ int routing_init(enum pol_routing pr)
 {
         switch (pr) {
         case ROUTING_LINK_STATE:
+        case ROUTING_LINK_STATE_LFA:
                 r_ops = &link_state_ops;
                 break;
         default:
                 return -ENOTSUP;
         }
 
-        return r_ops->init();
+        return r_ops->init(pr);
 }
 
 struct routing_i * routing_i_create(struct pff * pff)
diff --git a/src/tools/irm/irm_ipcp_bootstrap.c b/src/tools/irm/irm_ipcp_bootstrap.c
index 9812f860..26b86a16 100644
--- a/src/tools/irm/irm_ipcp_bootstrap.c
+++ b/src/tools/irm/irm_ipcp_bootstrap.c
@@ -33,28 +33,29 @@
 #include "irm_ops.h"
 #include "irm_utils.h"
 
-#define NORMAL                "normal"
-#define SHIM_UDP              "shim-udp"
-#define SHIM_ETH_LLC          "shim-eth-llc"
-#define LOCAL                 "local"
-
-#define MD5                   "MD5"
-#define SHA3_224              "SHA3_224"
-#define SHA3_256              "SHA3_256"
-#define SHA3_384              "SHA3_384"
-#define SHA3_512              "SHA3_512"
-
-#define DEFAULT_ADDR_SIZE     4
-#define DEFAULT_FD_SIZE       2
-#define DEFAULT_DDNS          0
-#define DEFAULT_ADDR_AUTH     ADDR_AUTH_FLAT_RANDOM
-#define DEFAULT_ROUTING       ROUTING_LINK_STATE
-#define DEFAULT_PFF           PFF_SIMPLE
-#define DEFAULT_HASH_ALGO     DIR_HASH_SHA3_256
-#define FLAT_RANDOM_ADDR_AUTH "flat"
-#define LINK_STATE_ROUTING    "link_state"
-#define SIMPLE_PFF            "simple"
-#define ALTERNATE_PFF         "alternate"
+#define NORMAL                 "normal"
+#define SHIM_UDP               "shim-udp"
+#define SHIM_ETH_LLC           "shim-eth-llc"
+#define LOCAL                  "local"
+
+#define MD5                    "MD5"
+#define SHA3_224               "SHA3_224"
+#define SHA3_256               "SHA3_256"
+#define SHA3_384               "SHA3_384"
+#define SHA3_512               "SHA3_512"
+
+#define DEFAULT_ADDR_SIZE      4
+#define DEFAULT_FD_SIZE        2
+#define DEFAULT_DDNS           0
+#define DEFAULT_ADDR_AUTH      ADDR_AUTH_FLAT_RANDOM
+#define DEFAULT_ROUTING        ROUTING_LINK_STATE
+#define DEFAULT_PFF            PFF_SIMPLE
+#define DEFAULT_HASH_ALGO      DIR_HASH_SHA3_256
+#define FLAT_RANDOM_ADDR_AUTH  "flat"
+#define LINK_STATE_ROUTING     "link_state"
+#define LINK_STATE_LFA_ROUTING "lfa"
+#define SIMPLE_PFF             "simple"
+#define ALTERNATE_PFF          "alternate"
 
 static void usage(void)
 {
@@ -74,7 +75,8 @@ static void usage(void)
                "                [pff [PFF_POLICY] (default: %s)]\n"
                "                [hash [ALGORITHM] (default: %s)]\n"
                "where ADDRESS_POLICY = {"FLAT_RANDOM_ADDR_AUTH"}\n"
-               "      ROUTING_POLICY = {"LINK_STATE_ROUTING"}\n"
+               "      ROUTING_POLICY = {"LINK_STATE_ROUTING " "
+               LINK_STATE_LFA_ROUTING "}\n"
                "      PFF_POLICY = {" SIMPLE_PFF " " ALTERNATE_PFF "}\n"
                "      ALGORITHM = {" SHA3_224 " " SHA3_256 " "
                SHA3_384 " " SHA3_512 "}\n\n"
@@ -151,6 +153,9 @@ int do_bootstrap_ipcp(int argc, char ** argv)
                 } else if (matches(*argv, "routing") == 0) {
                         if (strcmp(LINK_STATE_ROUTING, *(argv + 1)) == 0)
                                 routing_type = ROUTING_LINK_STATE;
+                        else if (strcmp(LINK_STATE_LFA_ROUTING,
+                                        *(argv + 1)) == 0)
+                                routing_type = ROUTING_LINK_STATE_LFA;
                         else
                                 goto unknown_param;
                 } else if (matches(*argv, "pff") == 0) {