Add equal-cost multipath routing policy

This adds an equal-cost multipath routing policy to Ouroboros, based
on Nick Aerts' code. When selected, flows will send packets over all
paths with equal cost (hop count). Path selection is round-robin. It
does not yet take into account flows that are down.

Signed-off-by: Dimitri Staessens <dimitri@ouroboros.rocks>
Signed-off-by: Sander Vrijders <sander@ouroboros.rocks>

13 files changed, 407 insertions, 16 deletions

diff --git a/src/ipcpd/unicast/CMakeLists.txt b/src/ipcpd/unicast/CMakeLists.txt
index d6ec4a93..c0c55519 100644
--- a/src/ipcpd/unicast/CMakeLists.txt
+++ b/src/ipcpd/unicast/CMakeLists.txt
@@ -45,11 +45,12 @@ set(SOURCE_FILES
   psched.c
   # Add policies last
   pol/pft.c
-  pol/alternate_pff.c
   pol/flat.c
   pol/link_state.c
   pol/graph.c
   pol/simple_pff.c
+  pol/alternate_pff.c
+  pol/multipath_pff.c
   )
 
 add_executable(ipcpd-unicast ${SOURCE_FILES} ${IPCP_SOURCES}
diff --git a/src/ipcpd/unicast/pff.c b/src/ipcpd/unicast/pff.c
index 4e380e05..19432972 100644
--- a/src/ipcpd/unicast/pff.c
+++ b/src/ipcpd/unicast/pff.c
@@ -28,6 +28,7 @@
 #include "pff.h"
 #include "pol-pff-ops.h"
 #include "pol/alternate_pff.h"
+#include "pol/multipath_pff.h"
 #include "pol/simple_pff.h"
 
 struct pff {
@@ -52,6 +53,10 @@ struct pff * pff_create(enum pol_pff pol)
                 log_dbg("Using simple PFF policy.");
                 pff->ops = &simple_pff_ops;
                 break;
+        case PFF_MULTIPATH:
+                log_dbg("Using multipath PFF policy.");
+                pff->ops = &multipath_pff_ops;
+                break;
         default:
                 goto err;
         }
diff --git a/src/ipcpd/unicast/pff.h b/src/ipcpd/unicast/pff.h
index a7b618dc..962ae594 100644
--- a/src/ipcpd/unicast/pff.h
+++ b/src/ipcpd/unicast/pff.h
@@ -31,7 +31,8 @@
 
 enum pol_pff {
         PFF_SIMPLE = 0,
-        PFF_ALTERNATE
+        PFF_ALTERNATE,
+        PFF_MULTIPATH
 };
 
 struct pff * pff_create(enum pol_pff pol);
diff --git a/src/ipcpd/unicast/pol/alternate_pff.c b/src/ipcpd/unicast/pol/alternate_pff.c
index 80c93f0e..f26bb047 100644
--- a/src/ipcpd/unicast/pol/alternate_pff.c
+++ b/src/ipcpd/unicast/pol/alternate_pff.c
@@ -27,13 +27,13 @@
 #include <ouroboros/errno.h>
 #include <ouroboros/list.h>
 
+#include "pft.h"
+#include "alternate_pff.h"
+
 #include <string.h>
 #include <assert.h>
 #include <pthread.h>
 
-#include "pft.h"
-#include "alternate_pff.h"
-
 struct nhop {
         struct list_head next;
         int              fd;
@@ -336,7 +336,7 @@ int alternate_flow_state_change(struct pff_i * pff_i,
                                 int            fd,
                                 bool           up)
 {
-        struct list_head * pos = NULL;
+        struct list_head * p;
         size_t             len;
         int *              fds;
         size_t             i;
@@ -358,8 +358,8 @@ int alternate_flow_state_change(struct pff_i * pff_i,
                 }
         }
 
-        list_for_each(pos, &pff_i->addrs) {
-                struct addr * e = list_entry(pos, struct addr, next);
+        list_for_each(p, &pff_i->addrs) {
+                struct addr * e = list_entry(p, struct addr, next);
                 if (pft_lookup(pff_i->pft, e->addr, &fds, &len)) {
                         pthread_rwlock_unlock(&pff_i->lock);
                         return -1;
diff --git a/src/ipcpd/unicast/pol/graph.c b/src/ipcpd/unicast/pol/graph.c
index e76a47fb..1e095ba4 100644
--- a/src/ipcpd/unicast/pol/graph.c
+++ b/src/ipcpd/unicast/pol/graph.c
@@ -5,6 +5,7 @@
  *
  *    Dimitri Staessens <dimitri.staessens@ugent.be>
  *    Sander Vrijders   <sander.vrijders@ugent.be>
+ *    Nick Aerts        <nick.aerts@ugent.be>
  *
  * This program is free software; you can redistribute it and/or modify
  * it under the terms of the GNU General Public License version 2 as
@@ -697,6 +698,112 @@ static int graph_routing_table_lfa(struct graph *     graph,
         return -1;
 }
 
+static int graph_routing_table_ecmp(struct graph *     graph,
+                                    uint64_t           s_addr,
+                                    struct list_head * table,
+                                    int **             dist)
+{
+        struct vertex **       nhops;
+        struct list_head *     p;
+        struct list_head *     h;
+        size_t                 i;
+        struct vertex *        v;
+        struct vertex *        src_v;
+        struct edge *          e;
+        struct routing_table * t;
+        struct nhop *          n;
+        struct list_head *     forwarding;
+
+        assert(graph);
+        assert(dist);
+
+        if (graph-> nr_vertices < 2)
+                goto fail_vertices;
+
+        forwarding = malloc(sizeof(*forwarding) * graph->nr_vertices);
+        if (forwarding == NULL)
+                goto fail_vertices;
+
+        for (i = 0; i < graph->nr_vertices; ++i)
+                list_head_init(&forwarding[i]);
+
+        if (dijkstra(graph, s_addr, &nhops, dist))
+                goto fail_dijkstra;
+
+        free(nhops);
+
+        src_v = find_vertex_by_addr(graph, s_addr);
+        if (src_v == NULL)
+                goto fail_dijkstra;
+
+        list_for_each(p, &src_v->edges) {
+                int * tmp_dist;
+
+                e = list_entry(p, struct edge, next);
+                if (dijkstra(graph, e->nb->addr, &nhops, &tmp_dist))
+                        goto fail_dijkstra;
+
+                free(nhops);
+
+                list_for_each(h, &graph->vertices) {
+                        v = list_entry(h, struct vertex, next);
+                        if (tmp_dist[v->index] + 1 == (*dist)[v->index]) {
+                                n = malloc(sizeof(*n));
+                                if (n == NULL) {
+                                        free(tmp_dist);
+                                        goto fail_dijkstra;
+                                }
+                                n->nhop = e->nb->addr;
+                                list_add_tail(&n->next, &forwarding[v->index]);
+                        }
+                }
+
+                free(tmp_dist);
+        }
+
+        list_head_init(table);
+        i = 0;
+        list_for_each(p, &graph->vertices) {
+                v = list_entry(p, struct vertex, next);
+                if (v->addr == s_addr) {
+                        ++i;
+                        continue;
+                }
+
+                t = malloc(sizeof(*t));
+                if (t == NULL)
+                        goto fail_t;
+
+                t->dst = v->addr;
+
+                list_head_init(&t->nhops);
+                if (&forwarding[i] != forwarding[i].nxt) {
+                        t->nhops.nxt = forwarding[i].nxt;
+                        t->nhops.prv = forwarding[i].prv;
+                        forwarding[i].prv->nxt = &t->nhops;
+                        forwarding[i].nxt->prv = &t->nhops;
+                }
+
+                list_add(&t->next, table);
+                ++i;
+        }
+
+        free(*dist);
+        *dist = NULL;
+        free(forwarding);
+
+        return 0;
+
+ fail_t:
+        free_routing_table(table);
+ fail_dijkstra:
+        free(forwarding);
+        free(*dist);
+ fail_vertices:
+        *dist = NULL;
+        return -1;
+}
+
 int graph_routing_table(struct graph *     graph,
                         enum routing_algo  algo,
                         uint64_t           s_addr,
@@ -719,6 +826,11 @@ int graph_routing_table(struct graph *     graph,
                 if (graph_routing_table_lfa(graph, s_addr, table, &s_dist))
                         goto fail_table;
                 break;
+
+        case ROUTING_ECMP:
+                if (graph_routing_table_ecmp(graph, s_addr, table, &s_dist))
+                        goto fail_table;
+                break;
         default:
                 log_err("Unsupported algorithm.");
                 goto fail_algo;
diff --git a/src/ipcpd/unicast/pol/graph.h b/src/ipcpd/unicast/pol/graph.h
index b6a9e891..473a5163 100644
--- a/src/ipcpd/unicast/pol/graph.h
+++ b/src/ipcpd/unicast/pol/graph.h
@@ -30,7 +30,8 @@
 
 enum routing_algo {
          ROUTING_SIMPLE = 0,
-         ROUTING_LFA
+         ROUTING_LFA,
+         ROUTING_ECMP
 };
 
 struct nhop {
diff --git a/src/ipcpd/unicast/pol/link_state.c b/src/ipcpd/unicast/pol/link_state.c
index e2656a98..5360f556 100644
--- a/src/ipcpd/unicast/pol/link_state.c
+++ b/src/ipcpd/unicast/pol/link_state.c
@@ -934,6 +934,10 @@ int link_state_init(enum pol_routing pr)
                 log_dbg("Using Loop-Free Alternates policy.");
                 ls.routing_algo = ROUTING_LFA;
                 break;
+        case ROUTING_LINK_STATE_ECMP:
+                log_dbg("Using Equal-Cost Multipath policy.");
+                ls.routing_algo = ROUTING_ECMP;
+                break;
         default:
                 goto fail_graph;
         }
@@ -974,8 +978,8 @@ int link_state_init(enum pol_routing pr)
         if (rib_reg(LSDB, &r_ops))
                 goto fail_rib_reg;
 
-        ls.db_len      = 0;
-        ls.nbs_len     = 0;
+        ls.db_len  = 0;
+        ls.nbs_len = 0;
 
         return 0;
 
diff --git a/src/ipcpd/unicast/pol/multipath_pff.c b/src/ipcpd/unicast/pol/multipath_pff.c
new file mode 100644
index 00000000..8f619006
--- /dev/null
+++ b/src/ipcpd/unicast/pol/multipath_pff.c
@@ -0,0 +1,198 @@
+/*
+ * Ouroboros - Copyright (C) 2016 - 2020
+ *
+ * Policy for PFF supporting multipath routing
+ *
+ *    Dimitri Staessens <dimitri.staessens@ugent.be>
+ *    Sander Vrijders   <sander.vrijders@ugent.be>
+ *    Nick Aerts        <nick.aerts@ugent.be>
+ *
+ * This program is free software; you can redistribute it and/or modify
+ * it under the terms of the GNU General Public License version 2 as
+ * published by the Free Software Foundation.
+ *
+ * This program is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+ * GNU General Public License for more details.
+ *
+ * You should have received a copy of the GNU General Public License
+ * along with this program; if not, write to the Free Software
+ * Foundation, Inc., http://www.fsf.org/about/contact/.
+ */
+
+#define _POSIX_C_SOURCE 200112L
+
+#include "config.h"
+
+#include <ouroboros/errno.h>
+
+#include "pft.h"
+#include "multipath_pff.h"
+
+#include <string.h>
+#include <assert.h>
+#include <pthread.h>
+
+struct pff_i {
+        struct pft *     pft;
+        pthread_rwlock_t lock;
+};
+
+struct pol_pff_ops multipath_pff_ops = {
+        .create            = multipath_pff_create,
+        .destroy           = multipath_pff_destroy,
+        .lock              = multipath_pff_lock,
+        .unlock            = multipath_pff_unlock,
+        .add               = multipath_pff_add,
+        .update            = multipath_pff_update,
+        .del               = multipath_pff_del,
+        .flush             = multipath_pff_flush,
+        .nhop              = multipath_pff_nhop,
+        .flow_state_change = NULL
+};
+
+struct pff_i * multipath_pff_create(void)
+{
+        struct pff_i * tmp;
+
+        tmp = malloc(sizeof(*tmp));
+        if (tmp == NULL)
+                return NULL;
+
+        if (pthread_rwlock_init(&tmp->lock, NULL)) {
+                free(tmp);
+                return NULL;
+        }
+
+        tmp->pft = pft_create(PFT_SIZE, false);
+        if (tmp->pft == NULL) {
+                pthread_rwlock_destroy(&tmp->lock);
+                free(tmp);
+                return NULL;
+        }
+
+        return tmp;
+}
+
+void multipath_pff_destroy(struct pff_i * pff_i)
+{
+        assert(pff_i);
+
+        pft_destroy(pff_i->pft);
+
+        pthread_rwlock_destroy(&pff_i->lock);
+        free(pff_i);
+}
+
+void multipath_pff_lock(struct pff_i * pff_i)
+{
+        pthread_rwlock_wrlock(&pff_i->lock);
+}
+
+void multipath_pff_unlock(struct pff_i * pff_i)
+{
+        pthread_rwlock_unlock(&pff_i->lock);
+}
+
+int multipath_pff_add(struct pff_i * pff_i,
+                      uint64_t       addr,
+                      int *          fds,
+                      size_t         len)
+{
+        int * tmp;
+
+        assert(pff_i);
+        assert(fds);
+        assert(len > 0);
+
+        tmp = malloc(len * sizeof(*tmp));
+        if (tmp == NULL)
+                return -ENOMEM;
+
+        memcpy(tmp,fds, len * sizeof(*tmp));
+
+        if (pft_insert(pff_i->pft, addr, tmp, len)) {
+                free(tmp);
+                return -1;
+        }
+
+        return 0;
+}
+
+int multipath_pff_update(struct pff_i * pff_i,
+                         uint64_t       addr,
+                         int *          fds,
+                         size_t         len)
+{
+        int * tmp;
+
+        assert(pff_i);
+        assert(fds);
+        assert(len > 0);
+
+        tmp = malloc(sizeof(*tmp));
+        if (fds == NULL)
+                return -ENOMEM;
+
+        memcpy(tmp,fds, len * sizeof(*tmp));
+
+        if (pft_delete(pff_i->pft, addr)) {
+                free(tmp);
+                return -1;
+        }
+
+        if (pft_insert(pff_i->pft, addr, fds, 1)) {
+                free(tmp);
+                return -1;
+        }
+
+        return 0;
+}
+
+int multipath_pff_del(struct pff_i * pff_i,
+                      uint64_t       addr)
+{
+        assert(pff_i);
+
+        if (pft_delete(pff_i->pft, addr))
+                return -1;
+
+        return 0;
+}
+
+void multipath_pff_flush(struct pff_i * pff_i)
+{
+        assert(pff_i);
+
+        pft_flush(pff_i->pft);
+}
+
+int multipath_pff_nhop(struct pff_i * pff_i,
+                       uint64_t       addr)
+{
+        int    fd;
+        int *  fds;
+        size_t len;
+
+        assert(pff_i);
+
+        pthread_rwlock_rdlock(&pff_i->lock);
+
+        if (pft_lookup(pff_i->pft, addr, &fds, &len)) {
+                pthread_rwlock_unlock(&pff_i->lock);
+                return -1;
+        }
+
+        fd = *fds;
+
+        assert(len > 0);
+
+        /* Rotate fds left. */
+        memcpy(fds, fds + 1, (len - 1) * sizeof(*fds));
+        fds[len - 1] = fd;
+
+        pthread_rwlock_unlock(&pff_i->lock);
+
+        return fd;
+}
diff --git a/src/ipcpd/unicast/pol/multipath_pff.h b/src/ipcpd/unicast/pol/multipath_pff.h
new file mode 100644
index 00000000..a8ee088f
--- /dev/null
+++ b/src/ipcpd/unicast/pol/multipath_pff.h
@@ -0,0 +1,58 @@
+/*
+ * Ouroboros - Copyright (C) 2016 - 2020
+ *
+ * Policy for PFF supporting multipath routing
+ *
+ *    Dimitri Staessens <dimitri.staessens@ugent.be>
+ *    Sander Vrijders   <sander.vrijders@ugent.be>
+ *    Nick Aerts        <nick.aerts@ugent.be>
+ *
+ * This program is free software; you can redistribute it and/or modify
+ * it under the terms of the GNU General Public License version 2 as
+ * published by the Free Software Foundation.
+ *
+ * This program is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+ * GNU General Public License for more details.
+ *
+ * You should have received a copy of the GNU General Public License
+ * along with this program; if not, write to the Free Software
+ * Foundation, Inc., http://www.fsf.org/about/contact/.
+ */
+
+#ifndef OUROBOROS_IPCPD_UNICAST_MULTIPATH_PFF_H
+#define OUROBOROS_IPCPD_UNICAST_MULTIPATH_PFF_H
+
+#include "pol-pff-ops.h"
+
+struct pff_i * multipath_pff_create(void);
+
+void multipath_pff_destroy(struct pff_i * pff_i);
+
+void           multipath_pff_lock(struct pff_i * pff_i);
+
+void           multipath_pff_unlock(struct pff_i * pff_i);
+
+int            multipath_pff_add(struct pff_i * pff_i,
+                                 uint64_t       addr,
+                                 int *          fds,
+                                 size_t         len);
+
+int            multipath_pff_update(struct pff_i * pff_i,
+                                    uint64_t       addr,
+                                    int *          fds,
+                                    size_t         len);
+
+int            multipath_pff_del(struct pff_i * pff_i,
+                                 uint64_t       addr);
+
+void multipath_pff_flush(struct pff_i * pff_i);
+
+/* Returns fd towards next hop */
+int            multipath_pff_nhop(struct pff_i * pff_i,
+                                  uint64_t       addr);
+
+struct pol_pff_ops multipath_pff_ops;
+
+#endif /* OUROBOROS_IPCPD_UNICAST_MULTIPATH_PFF_H */
diff --git a/src/ipcpd/unicast/pol/pft.c b/src/ipcpd/unicast/pol/pft.c
index 924efbe1..53acc08e 100644
--- a/src/ipcpd/unicast/pol/pft.c
+++ b/src/ipcpd/unicast/pol/pft.c
@@ -149,6 +149,7 @@ int pft_insert(struct pft * pft,
         struct list_head * p;
 
         assert(pft);
+        assert(len > 0);
 
         lookup_key = calc_key(pft, dst);
 
diff --git a/src/ipcpd/unicast/pol/simple_pff.c b/src/ipcpd/unicast/pol/simple_pff.c
index c5780703..5bd73d8a 100644
--- a/src/ipcpd/unicast/pol/simple_pff.c
+++ b/src/ipcpd/unicast/pol/simple_pff.c
@@ -26,14 +26,14 @@
 
 #include <ouroboros/errno.h>
 
-#include <assert.h>
-#include <pthread.h>
-
 #include "pft.h"
 #include "simple_pff.h"
 
+#include <assert.h>
+#include <pthread.h>
+
 struct pff_i {
-        struct pft *  pft;
+        struct pft *     pft;
         pthread_rwlock_t lock;
 };
 
@@ -101,6 +101,7 @@ int simple_pff_add(struct pff_i * pff_i,
         int * fds;
 
         assert(pff_i);
+        assert(fd);
         assert(len > 0);
 
         (void) len;
@@ -127,6 +128,7 @@ int simple_pff_update(struct pff_i * pff_i,
         int * fds;
 
         assert(pff_i);
+        assert(fd);
         assert(len > 0);
 
         (void) len;
diff --git a/src/ipcpd/unicast/routing.c b/src/ipcpd/unicast/routing.c
index 0794555e..0ac43f9f 100644
--- a/src/ipcpd/unicast/routing.c
+++ b/src/ipcpd/unicast/routing.c
@@ -43,6 +43,10 @@ int routing_init(enum pol_routing pr)
                 pff_type = PFF_ALTERNATE;
                 r_ops = &link_state_ops;
                 break;
+        case ROUTING_LINK_STATE_ECMP:
+                pff_type=PFF_MULTIPATH;
+                r_ops = &link_state_ops;
+                break;
         default:
                 return -ENOTSUP;
         }
diff --git a/src/tools/irm/irm_ipcp_bootstrap.c b/src/tools/irm/irm_ipcp_bootstrap.c
index 7b844ba7..84b6759a 100644
--- a/src/tools/irm/irm_ipcp_bootstrap.c
+++ b/src/tools/irm/irm_ipcp_bootstrap.c
@@ -78,6 +78,7 @@
 #define FLAT_RANDOM_ADDR_AUTH  "flat"
 #define LINK_STATE_ROUTING     "link_state"
 #define LINK_STATE_LFA_ROUTING "lfa"
+#define LINK_STATE_ECM_ROUTING "ecmp"
 
 static void usage(void)
 {
@@ -98,7 +99,7 @@ static void usage(void)
                "                [autobind]\n"
                "where ADDRESS_POLICY = {"FLAT_RANDOM_ADDR_AUTH"}\n"
                "      ROUTING_POLICY = {"LINK_STATE_ROUTING " "
-               LINK_STATE_LFA_ROUTING "}\n"
+               LINK_STATE_LFA_ROUTING " " LINK_STATE_ECM_ROUTING "}\n"
                "      ALGORITHM = {" SHA3_224 " " SHA3_256 " "
                SHA3_384 " " SHA3_512 "}\n\n"
                "if TYPE == " UDP "\n"
@@ -224,6 +225,9 @@ int do_bootstrap_ipcp(int     argc,
                         else if (strcmp(LINK_STATE_LFA_ROUTING,
                                         *(argv + 1)) == 0)
                                 routing_type = ROUTING_LINK_STATE_LFA;
+                        else if (strcmp(LINK_STATE_ECM_ROUTING,
+                                        *(argv + 1)) == 0)
+                                routing_type = ROUTING_LINK_STATE_ECMP;
                         else
                                 goto unknown_param;
                 } else {