summaryrefslogtreecommitdiff
diff options
context:
space:
mode:
Diffstat
-rw-r--r--include/ouroboros/ipcp.h3
-rw-r--r--src/ipcpd/unicast/CMakeLists.txt3
-rw-r--r--src/ipcpd/unicast/pff.c5
-rw-r--r--src/ipcpd/unicast/pff.h3
-rw-r--r--src/ipcpd/unicast/pol/alternate_pff.c12
-rw-r--r--src/ipcpd/unicast/pol/graph.c112
-rw-r--r--src/ipcpd/unicast/pol/graph.h3
-rw-r--r--src/ipcpd/unicast/pol/link_state.c8
-rw-r--r--src/ipcpd/unicast/pol/multipath_pff.c198
-rw-r--r--src/ipcpd/unicast/pol/multipath_pff.h58
-rw-r--r--src/ipcpd/unicast/pol/pft.c1
-rw-r--r--src/ipcpd/unicast/pol/simple_pff.c10
-rw-r--r--src/ipcpd/unicast/routing.c4
-rw-r--r--src/tools/irm/irm_ipcp_bootstrap.c6
14 files changed, 409 insertions, 17 deletions
diff --git a/include/ouroboros/ipcp.h b/include/ouroboros/ipcp.h
index 71607646..6494d9b7 100644
--- a/include/ouroboros/ipcp.h
+++ b/include/ouroboros/ipcp.h
@@ -51,7 +51,8 @@ enum pol_addr_auth {
enum pol_routing {
ROUTING_LINK_STATE = 0,
- ROUTING_LINK_STATE_LFA
+ ROUTING_LINK_STATE_LFA,
+ ROUTING_LINK_STATE_ECMP
};
enum pol_dir_hash {
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 <[email protected]>
* Sander Vrijders <[email protected]>
+ * Nick Aerts <[email protected]>
*
* 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 <[email protected]>
+ * Sander Vrijders <[email protected]>
+ * Nick Aerts <[email protected]>
+ *
+ * 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 <[email protected]>
+ * Sander Vrijders <[email protected]>
+ * Nick Aerts <[email protected]>
+ *
+ * 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 {
generated by cgit v1.2.3 (git 2.39.1) at 2024-11-28 20:42:09 +0000