summaryrefslogtreecommitdiff
path: root/src/ipcpd/unicast/pol
diff options
context:
space:
mode:
Diffstat (limited to 'src/ipcpd/unicast/pol')
-rw-r--r--src/ipcpd/unicast/pol/alternate_pff.c403
-rw-r--r--src/ipcpd/unicast/pol/alternate_pff.h61
-rw-r--r--src/ipcpd/unicast/pol/flat.c87
-rw-r--r--src/ipcpd/unicast/pol/flat.h36
-rw-r--r--src/ipcpd/unicast/pol/graph.c695
-rw-r--r--src/ipcpd/unicast/pol/graph.h68
-rw-r--r--src/ipcpd/unicast/pol/link_state.c1022
-rw-r--r--src/ipcpd/unicast/pol/link_state.h41
-rw-r--r--src/ipcpd/unicast/pol/simple_pff.c187
-rw-r--r--src/ipcpd/unicast/pol/simple_pff.h57
-rw-r--r--src/ipcpd/unicast/pol/tests/CMakeLists.txt34
-rw-r--r--src/ipcpd/unicast/pol/tests/graph_test.c300
12 files changed, 2991 insertions, 0 deletions
diff --git a/src/ipcpd/unicast/pol/alternate_pff.c b/src/ipcpd/unicast/pol/alternate_pff.c
new file mode 100644
index 00000000..38937297
--- /dev/null
+++ b/src/ipcpd/unicast/pol/alternate_pff.c
@@ -0,0 +1,403 @@
+/*
+ * Ouroboros - Copyright (C) 2016 - 2019
+ *
+ * Policy for PFF with alternate next hops
+ *
+ * Dimitri Staessens <[email protected]>
+ * Sander Vrijders <[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/hashtable.h>
+#include <ouroboros/errno.h>
+#include <ouroboros/list.h>
+
+#include <string.h>
+#include <assert.h>
+#include <pthread.h>
+
+#include "alternate_pff.h"
+
+struct nhop {
+ struct list_head next;
+ int fd;
+};
+
+struct addr {
+ struct list_head next;
+ uint64_t addr;
+};
+
+struct pff_i {
+ struct htable * table;
+
+ struct list_head addrs;
+
+ struct list_head nhops_down;
+
+ pthread_rwlock_t lock;
+};
+
+struct pol_pff_ops alternate_pff_ops = {
+ .create = alternate_pff_create,
+ .destroy = alternate_pff_destroy,
+ .lock = alternate_pff_lock,
+ .unlock = alternate_pff_unlock,
+ .add = alternate_pff_add,
+ .update = alternate_pff_update,
+ .del = alternate_pff_del,
+ .flush = alternate_pff_flush,
+ .nhop = alternate_pff_nhop,
+ .flow_state_change = alternate_flow_state_change
+};
+
+static int add_addr(struct pff_i * pff_i,
+ uint64_t addr)
+{
+ struct addr * a;
+
+ a = malloc(sizeof(*a));
+ if (a == NULL)
+ return -1;
+
+ a->addr = addr;
+
+ list_add(&a->next, &(pff_i->addrs));
+
+ return 0;
+}
+
+static void del_addr(struct pff_i * pff_i,
+ uint64_t addr)
+{
+ struct list_head * pos = NULL;
+ struct list_head * n = NULL;
+
+ list_for_each_safe(pos, n, &(pff_i->addrs)) {
+ struct addr * e = list_entry(pos, struct addr, next);
+ if (e->addr == addr) {
+ list_del(&e->next);
+ free(e);
+ return;
+ }
+ }
+}
+
+static void del_addrs(struct pff_i * pff_i)
+{
+ struct list_head * pos = NULL;
+ struct list_head * n = NULL;
+
+ list_for_each_safe(pos, n, &(pff_i->addrs)) {
+ struct addr * e = list_entry(pos, struct addr, next);
+ list_del(&e->next);
+ free(e);
+ }
+}
+
+static void del_nhops_down(struct pff_i * pff_i)
+{
+ struct list_head * pos = NULL;
+ struct list_head * n = NULL;
+
+ list_for_each_safe(pos, n, &(pff_i->nhops_down)) {
+ struct nhop * e = list_entry(pos, struct nhop, next);
+ list_del(&e->next);
+ free(e);
+ }
+}
+
+static int del_nhop_down(struct pff_i * pff_i,
+ int fd)
+{
+ struct list_head * pos = NULL;
+ struct list_head * n = NULL;
+
+ list_for_each_safe(pos, n, &(pff_i->nhops_down)) {
+ struct nhop * e = list_entry(pos, struct nhop, next);
+ if (e->fd == fd) {
+ list_del(&e->next);
+ free(e);
+ return 0;
+ }
+ }
+
+ return -1;
+}
+
+static int add_nhop_down(struct pff_i * pff_i,
+ int fd)
+{
+ struct nhop * nhop;
+
+ nhop = malloc(sizeof(*nhop));
+ if (nhop == NULL)
+ return -1;
+
+ nhop->fd = fd;
+
+ list_add(&nhop->next, &(pff_i->nhops_down));
+
+ return 0;
+}
+
+static bool nhops_down_has(struct pff_i * pff_i,
+ int fd)
+{
+ struct list_head * pos = NULL;
+
+ list_for_each(pos, &pff_i->nhops_down) {
+ struct nhop * e = list_entry(pos, struct nhop, next);
+ if (e->fd == fd)
+ return true;
+ }
+
+ return false;
+}
+
+static int add_to_htable(struct pff_i * pff_i,
+ uint64_t addr,
+ int * fd,
+ size_t len)
+{
+ int * val;
+
+ assert(pff_i);
+ assert(len > 0);
+
+ val = malloc(sizeof(*val) * (len + 1));
+ if (val == NULL)
+ goto fail_malloc;
+
+ memcpy(val, fd, len * sizeof(*val));
+ /* Put primary hop again at the end */
+ val[len] = val[0];
+
+ if (htable_insert(pff_i->table, addr, val, len))
+ goto fail_insert;
+
+ return 0;
+
+ fail_insert:
+ free(val);
+ fail_malloc:
+ return -1;
+}
+
+struct pff_i * alternate_pff_create(void)
+{
+ struct pff_i * tmp;
+
+ tmp = malloc(sizeof(*tmp));
+ if (tmp == NULL)
+ goto fail_malloc;
+
+ if (pthread_rwlock_init(&tmp->lock, NULL))
+ goto fail_lock;
+
+ tmp->table = htable_create(PFT_SIZE, false);
+ if (tmp->table == NULL)
+ goto fail_table;
+
+ list_head_init(&tmp->nhops_down);
+ list_head_init(&tmp->addrs);
+
+ return tmp;
+
+ fail_table:
+ pthread_rwlock_destroy(&tmp->lock);
+ fail_lock:
+ free(tmp);
+ fail_malloc:
+ return NULL;
+}
+
+void alternate_pff_destroy(struct pff_i * pff_i)
+{
+ assert(pff_i);
+
+ htable_destroy(pff_i->table);
+ del_nhops_down(pff_i);
+ del_addrs(pff_i);
+ pthread_rwlock_destroy(&pff_i->lock);
+ free(pff_i);
+}
+
+void alternate_pff_lock(struct pff_i * pff_i)
+{
+ pthread_rwlock_wrlock(&pff_i->lock);
+}
+
+void alternate_pff_unlock(struct pff_i * pff_i)
+{
+ pthread_rwlock_unlock(&pff_i->lock);
+}
+
+int alternate_pff_add(struct pff_i * pff_i,
+ uint64_t addr,
+ int * fd,
+ size_t len)
+{
+ assert(pff_i);
+ assert(len > 0);
+
+ if (add_to_htable(pff_i, addr, fd, len))
+ return -1;
+
+ if (add_addr(pff_i, addr)) {
+ htable_delete(pff_i->table, addr);
+ return -1;
+ }
+
+ return 0;
+}
+
+int alternate_pff_update(struct pff_i * pff_i,
+ uint64_t addr,
+ int * fd,
+ size_t len)
+{
+ assert(pff_i);
+ assert(len > 0);
+
+ if (htable_delete(pff_i->table, addr))
+ return -1;
+
+ if (add_to_htable(pff_i, addr, fd, len))
+ return -1;
+
+ return 0;
+}
+
+int alternate_pff_del(struct pff_i * pff_i,
+ uint64_t addr)
+{
+ assert(pff_i);
+
+ del_addr(pff_i, addr);
+
+ if (htable_delete(pff_i->table, addr))
+ return -1;
+
+ return 0;
+}
+
+void alternate_pff_flush(struct pff_i * pff_i)
+{
+ assert(pff_i);
+
+ htable_flush(pff_i->table);
+
+ del_nhops_down(pff_i);
+
+ del_addrs(pff_i);
+}
+
+int alternate_pff_nhop(struct pff_i * pff_i,
+ uint64_t addr)
+{
+ int fd = -1;
+ size_t len;
+ void * el;
+
+ assert(pff_i);
+
+ pthread_rwlock_rdlock(&pff_i->lock);
+
+ if (htable_lookup(pff_i->table, addr, &el, &len)) {
+ pthread_rwlock_unlock(&pff_i->lock);
+ return -1;
+ }
+
+ fd = *((int *) el);
+
+ pthread_rwlock_unlock(&pff_i->lock);
+
+ return fd;
+}
+
+int alternate_flow_state_change(struct pff_i * pff_i,
+ int fd,
+ bool up)
+{
+ struct list_head * pos = NULL;
+ size_t len;
+ void * el;
+ int * fds;
+ size_t i;
+ int tmp;
+
+ assert(pff_i);
+
+ pthread_rwlock_wrlock(&pff_i->lock);
+
+ if (up) {
+ if (del_nhop_down(pff_i, fd)) {
+ pthread_rwlock_unlock(&pff_i->lock);
+ return -1;
+ }
+ } else {
+ if (add_nhop_down(pff_i, fd)) {
+ pthread_rwlock_unlock(&pff_i->lock);
+ return -1;
+ }
+ }
+
+ list_for_each(pos, &pff_i->addrs) {
+ struct addr * e = list_entry(pos, struct addr, next);
+ if (htable_lookup(pff_i->table, e->addr, &el, &len)) {
+ pthread_rwlock_unlock(&pff_i->lock);
+ return -1;
+ }
+
+ fds = (int *) el;
+
+ if (up) {
+ /* It is using an alternate */
+ if (fds[len] == fd && fds[0] != fd) {
+ for (i = 0 ; i < len; i++) {
+ /* Found the primary */
+ if (fds[i] == fd) {
+ tmp = fds[0];
+ fds[0] = fds[i];
+ fds[i] = tmp;
+ break;
+ }
+ }
+ }
+ } else {
+ /* Need to switch to a (different) alternate */
+ if (fds[0] == fd) {
+ for (i = 1; i < len; i++) {
+ /* Usable alternate */
+ if (!nhops_down_has(pff_i, fds[i])) {
+ tmp = fds[0];
+ fds[0] = fds[i];
+ fds[i] = tmp;
+ break;
+ }
+ }
+ }
+ }
+ }
+
+ pthread_rwlock_unlock(&pff_i->lock);
+
+ return 0;
+}
diff --git a/src/ipcpd/unicast/pol/alternate_pff.h b/src/ipcpd/unicast/pol/alternate_pff.h
new file mode 100644
index 00000000..7bdf26de
--- /dev/null
+++ b/src/ipcpd/unicast/pol/alternate_pff.h
@@ -0,0 +1,61 @@
+/*
+ * Ouroboros - Copyright (C) 2016 - 2019
+ *
+ * Policy for PFF with alternate next hops
+ *
+ * Dimitri Staessens <[email protected]>
+ * Sander Vrijders <[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_ALTERNATE_PFF_H
+#define OUROBOROS_IPCPD_UNICAST_ALTERNATE_PFF_H
+
+#include "pol-pff-ops.h"
+
+struct pff_i * alternate_pff_create(void);
+
+void alternate_pff_destroy(struct pff_i * pff_i);
+
+void alternate_pff_lock(struct pff_i * pff_i);
+
+void alternate_pff_unlock(struct pff_i * pff_i);
+
+int alternate_pff_add(struct pff_i * pff_i,
+ uint64_t addr,
+ int * fd,
+ size_t len);
+
+int alternate_pff_update(struct pff_i * pff_i,
+ uint64_t addr,
+ int * fd,
+ size_t len);
+
+int alternate_pff_del(struct pff_i * pff_i,
+ uint64_t addr);
+
+void alternate_pff_flush(struct pff_i * pff_i);
+
+/* Returns fd towards next hop */
+int alternate_pff_nhop(struct pff_i * pff_i,
+ uint64_t addr);
+
+int alternate_flow_state_change(struct pff_i * pff_i,
+ int fd,
+ bool up);
+
+struct pol_pff_ops alternate_pff_ops;
+
+#endif /* OUROBOROS_IPCPD_UNICAST_ALTERNATE_PFF_H */
diff --git a/src/ipcpd/unicast/pol/flat.c b/src/ipcpd/unicast/pol/flat.c
new file mode 100644
index 00000000..157885f9
--- /dev/null
+++ b/src/ipcpd/unicast/pol/flat.c
@@ -0,0 +1,87 @@
+/*
+ * Ouroboros - Copyright (C) 2016 - 2019
+ *
+ * Policy for flat addresses in a distributed way
+ *
+ * Dimitri Staessens <[email protected]>
+ * Sander Vrijders <[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/.
+ */
+
+#if defined(__linux__) || defined(__CYGWIN__)
+#define _DEFAULT_SOURCE
+#else
+#define _POSIX_C_SOURCE 200112L
+#endif
+
+#define OUROBOROS_PREFIX "flat-addr-auth"
+
+#include <ouroboros/logs.h>
+#include <ouroboros/errno.h>
+#include <ouroboros/time_utils.h>
+#include <ouroboros/utils.h>
+
+#include "ipcp.h"
+#include "flat.h"
+
+#include <time.h>
+#include <stdlib.h>
+#include <math.h>
+#include <string.h>
+#include <assert.h>
+
+#define NAME_LEN 8
+
+struct {
+ uint8_t addr_size;
+} flat;
+
+#define INVALID_ADDRESS 0
+
+struct pol_addr_auth_ops flat_ops = {
+ .init = flat_init,
+ .fini = flat_fini,
+ .address = flat_address
+};
+
+int flat_init(const void * info)
+{
+ flat.addr_size = *((uint8_t *) info);
+
+ if (flat.addr_size != 4) {
+ log_err("Flat address policy mandates 4 byte addresses.");
+ return -1;
+ }
+
+ return 0;
+}
+
+int flat_fini(void)
+{
+ return 0;
+}
+
+uint64_t flat_address(void)
+{
+ struct timespec t;
+ uint32_t addr;
+
+ clock_gettime(CLOCK_REALTIME, &t);
+ srand(t.tv_nsec);
+
+ addr = (rand() % (RAND_MAX - 1) + 1) & 0xFFFFFFFF;
+
+ return addr;
+}
diff --git a/src/ipcpd/unicast/pol/flat.h b/src/ipcpd/unicast/pol/flat.h
new file mode 100644
index 00000000..64aa9ce0
--- /dev/null
+++ b/src/ipcpd/unicast/pol/flat.h
@@ -0,0 +1,36 @@
+/*
+ * Ouroboros - Copyright (C) 2016 - 2019
+ *
+ * Policy for flat addresses in a distributed way
+ *
+ * Dimitri Staessens <[email protected]>
+ * Sander Vrijders <[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_FLAT_H
+#define OUROBOROS_IPCPD_UNICAST_FLAT_H
+
+#include "pol-addr-auth-ops.h"
+
+int flat_init(const void * info);
+
+int flat_fini(void);
+
+uint64_t flat_address(void);
+
+struct pol_addr_auth_ops flat_ops;
+
+#endif /* OUROBOROS_IPCPD_UNICAST_FLAT_H */
diff --git a/src/ipcpd/unicast/pol/graph.c b/src/ipcpd/unicast/pol/graph.c
new file mode 100644
index 00000000..499dc2de
--- /dev/null
+++ b/src/ipcpd/unicast/pol/graph.c
@@ -0,0 +1,695 @@
+/*
+ * Ouroboros - Copyright (C) 2016 - 2019
+ *
+ * Undirected graph structure
+ *
+ * Dimitri Staessens <[email protected]>
+ * Sander Vrijders <[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/.
+ */
+
+#if defined(__linux__) || defined(__CYGWIN__)
+#define _DEFAULT_SOURCE
+#else
+#define _POSIX_C_SOURCE 200112L
+#endif
+
+#define OUROBOROS_PREFIX "graph"
+
+#include <ouroboros/logs.h>
+#include <ouroboros/errno.h>
+#include <ouroboros/list.h>
+
+#include "graph.h"
+#include "ipcp.h"
+
+#include <assert.h>
+#include <pthread.h>
+#include <stdlib.h>
+#include <limits.h>
+#include <string.h>
+
+struct edge {
+ struct list_head next;
+ struct vertex * nb;
+ qosspec_t qs;
+ int announced;
+};
+
+struct vertex {
+ struct list_head next;
+ uint64_t addr;
+ struct list_head edges;
+ int index;
+};
+
+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)
+{
+ struct list_head * p = NULL;
+
+ list_for_each(p, &vertex->edges) {
+ struct edge * e = list_entry(p, struct edge, next);
+ if (e->nb->addr == dst_addr)
+ return e;
+ }
+
+ return NULL;
+}
+
+static struct vertex * find_vertex_by_addr(struct graph * graph,
+ uint64_t addr)
+{
+ struct list_head * p = NULL;
+
+ list_for_each(p, &graph->vertices) {
+ struct vertex * e = list_entry(p, struct vertex, next);
+ if (e->addr == addr)
+ return e;
+ }
+
+ return NULL;
+}
+
+static struct edge * add_edge(struct vertex * vertex,
+ struct vertex * nb)
+{
+ struct edge * edge;
+
+ edge = malloc(sizeof(*edge));
+ if (edge == NULL)
+ return NULL;
+
+ list_head_init(&edge->next);
+ edge->nb = nb;
+ edge->announced = 0;
+
+ list_add(&edge->next, &vertex->edges);
+
+ return edge;
+}
+
+static void del_edge(struct edge * edge)
+{
+ list_del(&edge->next);
+ free(edge);
+}
+
+static struct vertex * add_vertex(struct graph * graph,
+ uint64_t addr)
+{
+ struct vertex * vertex;
+ struct list_head * p;
+ int i = 0;
+
+ vertex = malloc(sizeof(*vertex));
+ if (vertex == NULL)
+ return NULL;
+
+ list_head_init(&vertex->next);
+ list_head_init(&vertex->edges);
+ vertex->addr = addr;
+
+ /* Keep them ordered on address. */
+ list_for_each(p, &graph->vertices) {
+ struct vertex * v = list_entry(p, struct vertex, next);
+ if (v->addr > addr)
+ break;
+ i++;
+ }
+
+ vertex->index = i;
+
+ list_add_tail(&vertex->next, p);
+
+ /* Increase the index of the vertices to the right. */
+ list_for_each(p, &graph->vertices) {
+ struct vertex * v = list_entry(p, struct vertex, next);
+ if (v->addr > addr)
+ v->index++;
+ }
+
+ graph->nr_vertices++;
+
+ return vertex;
+}
+
+static void del_vertex(struct graph * graph,
+ struct vertex * vertex)
+{
+ struct list_head * p = NULL;
+ struct list_head * n = NULL;
+
+ list_del(&vertex->next);
+
+ /* Decrease the index of the vertices to the right. */
+ list_for_each(p, &graph->vertices) {
+ struct vertex * v = list_entry(p, struct vertex, next);
+ if (v->addr > vertex->addr)
+ v->index--;
+ }
+
+ list_for_each_safe(p, n, &vertex->edges) {
+ struct edge * e = list_entry(p, struct edge, next);
+ del_edge(e);
+ }
+
+ free(vertex);
+
+ graph->nr_vertices--;
+}
+
+struct graph * graph_create(void)
+{
+ struct graph * graph;
+
+ graph = malloc(sizeof(*graph));
+ if (graph == NULL)
+ return NULL;
+
+ if (pthread_mutex_init(&graph->lock, NULL)) {
+ free(graph);
+ return NULL;
+ }
+
+ graph->nr_vertices = 0;
+ list_head_init(&graph->vertices);
+
+ return graph;
+}
+
+void graph_destroy(struct graph * graph)
+{
+ struct list_head * p = NULL;
+ struct list_head * n = NULL;
+
+ assert(graph);
+
+ pthread_mutex_lock(&graph->lock);
+
+ list_for_each_safe(p, n, &graph->vertices) {
+ struct vertex * e = list_entry(p, struct vertex, next);
+ del_vertex(graph, e);
+ }
+
+ pthread_mutex_unlock(&graph->lock);
+
+ pthread_mutex_destroy(&graph->lock);
+
+ free(graph);
+}
+
+int graph_update_edge(struct graph * graph,
+ uint64_t s_addr,
+ uint64_t d_addr,
+ qosspec_t qs)
+{
+ struct vertex * v;
+ struct edge * e;
+ struct vertex * nb;
+ struct edge * nb_e;
+
+ assert(graph);
+
+ pthread_mutex_lock(&graph->lock);
+
+ v = find_vertex_by_addr(graph, s_addr);
+ if (v == NULL) {
+ v = add_vertex(graph, s_addr);
+ if (v == NULL) {
+ pthread_mutex_unlock(&graph->lock);
+ log_err("Failed to add vertex.");
+ return -ENOMEM;
+ }
+ }
+
+ nb = find_vertex_by_addr(graph, d_addr);
+ if (nb == NULL) {
+ nb = add_vertex(graph, d_addr);
+ if (nb == NULL) {
+ if (list_is_empty(&v->edges))
+ del_vertex(graph, v);
+ pthread_mutex_unlock(&graph->lock);
+ log_err("Failed to add vertex.");
+ return -ENOMEM;
+ }
+ }
+
+ e = find_edge_by_addr(v, d_addr);
+ if (e == NULL) {
+ e = add_edge(v, nb);
+ if (e == NULL) {
+ if (list_is_empty(&v->edges))
+ del_vertex(graph, v);
+ if (list_is_empty(&nb->edges))
+ del_vertex(graph, nb);
+ pthread_mutex_unlock(&graph->lock);
+ log_err("Failed to add edge.");
+ return -ENOMEM;
+ }
+ }
+
+ e->announced++;
+ e->qs = qs;
+
+ nb_e = find_edge_by_addr(nb, s_addr);
+ if (nb_e == NULL) {
+ nb_e = add_edge(nb, v);
+ if (nb_e == NULL) {
+ if (--e->announced == 0)
+ del_edge(e);
+ if (list_is_empty(&v->edges))
+ del_vertex(graph, v);
+ if (list_is_empty(&nb->edges))
+ del_vertex(graph, nb);
+ pthread_mutex_unlock(&graph->lock);
+ log_err("Failed to add edge.");
+ return -ENOMEM;
+ }
+ }
+
+ nb_e->announced++;
+ nb_e->qs = qs;
+
+ pthread_mutex_unlock(&graph->lock);
+
+ return 0;
+}
+
+int graph_del_edge(struct graph * graph,
+ uint64_t s_addr,
+ uint64_t d_addr)
+{
+ struct vertex * v;
+ struct edge * e;
+ struct vertex * nb;
+ struct edge * nb_e;
+
+ assert(graph);
+
+ pthread_mutex_lock(&graph->lock);
+
+ v = find_vertex_by_addr(graph, s_addr);
+ if (v == NULL) {
+ pthread_mutex_unlock(&graph->lock);
+ log_err("No such source vertex.");
+ return -1;
+ }
+
+ nb = find_vertex_by_addr(graph, d_addr);
+ if (nb == NULL) {
+ pthread_mutex_unlock(&graph->lock);
+ log_err("No such destination vertex.");
+ return -1;
+ }
+
+ e = find_edge_by_addr(v, d_addr);
+ if (e == NULL) {
+ pthread_mutex_unlock(&graph->lock);
+ log_err("No such source edge.");
+ return -1;
+ }
+
+ nb_e = find_edge_by_addr(nb, s_addr);
+ if (nb_e == NULL) {
+ pthread_mutex_unlock(&graph->lock);
+ log_err("No such destination edge.");
+ return -1;
+ }
+
+ if (--e->announced == 0)
+ del_edge(e);
+ if (--nb_e->announced == 0)
+ del_edge(nb_e);
+
+ /* Removing vertex if it was the last edge */
+ if (list_is_empty(&v->edges))
+ del_vertex(graph, v);
+ if (list_is_empty(&nb->edges))
+ del_vertex(graph, nb);
+
+ pthread_mutex_unlock(&graph->lock);
+
+ return 0;
+}
+
+static int get_min_vertex(struct graph * graph,
+ int * dist,
+ bool * used,
+ struct vertex ** v)
+{
+ int min = INT_MAX;
+ int index = -1;
+ int i = 0;
+ struct list_head * p = NULL;
+
+ *v = NULL;
+
+ list_for_each(p, &graph->vertices) {
+ if (!used[i] && dist[i] < min) {
+ min = dist[i];
+ index = i;
+ *v = list_entry(p, struct vertex, next);
+ }
+
+ i++;
+ }
+
+ if (index != -1)
+ used[index] = true;
+
+ return index;
+}
+
+static int dijkstra(struct graph * graph,
+ uint64_t src,
+ struct vertex *** nhops,
+ int ** dist)
+{
+ bool * used;
+ struct list_head * p = NULL;
+ int i = 0;
+ struct vertex * v = NULL;
+ struct edge * e = NULL;
+ int alt;
+
+ *nhops = malloc(sizeof(**nhops) * graph->nr_vertices);
+ if (*nhops == NULL)
+ goto fail_pnhops;
+
+ *dist = malloc(sizeof(**dist) * graph->nr_vertices);
+ if (*dist == NULL)
+ goto fail_pdist;
+
+ used = malloc(sizeof(*used) * graph->nr_vertices);
+ if (used == NULL)
+ goto fail_used;
+
+ /* Init the data structures */
+ memset(used, 0, sizeof(*used) * graph->nr_vertices);
+ memset(*nhops, 0, sizeof(**nhops) * graph->nr_vertices);
+ memset(*dist, 0, sizeof(**dist) * graph->nr_vertices);
+
+ list_for_each(p, &graph->vertices) {
+ v = list_entry(p, struct vertex, next);
+ (*dist)[i++] = (v->addr == src) ? 0 : INT_MAX;
+ }
+
+ /* Perform actual Dijkstra */
+ i = get_min_vertex(graph, *dist, used, &v);
+ while (v != NULL) {
+ list_for_each(p, &v->edges) {
+ e = list_entry(p, struct edge, next);
+
+ /* Only include it if both sides announced it. */
+ if (e->announced != 2)
+ 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)[e->nb->index]) {
+ (*dist)[e->nb->index] = alt;
+ if (v->addr == src)
+ (*nhops)[e->nb->index] = e->nb;
+ else
+ (*nhops)[e->nb->index] = (*nhops)[i];
+ }
+ }
+ i = get_min_vertex(graph, *dist, used, &v);
+ }
+
+ free(used);
+
+ return 0;
+
+ fail_used:
+ free(*dist);
+ fail_pdist:
+ free(*nhops);
+ fail_pnhops:
+ return -1;
+
+}
+
+static void free_routing_table(struct list_head * table)
+{
+ struct list_head * h;
+ struct list_head * p;
+ struct list_head * q;
+ struct list_head * i;
+
+ list_for_each_safe(p, h, table) {
+ struct routing_table * t =
+ list_entry(p, struct routing_table, next);
+ list_for_each_safe(q, i, &t->nhops) {
+ struct nhop * n =
+ list_entry(q, struct nhop, next);
+ list_del(&n->next);
+ free(n);
+ }
+ list_del(&t->next);
+ free(t);
+ }
+}
+
+void graph_free_routing_table(struct graph * graph,
+ struct list_head * table)
+{
+ assert(table);
+
+ pthread_mutex_lock(&graph->lock);
+
+ free_routing_table(table);
+
+ pthread_mutex_unlock(&graph->lock);
+}
+
+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;
+ int i = 0;
+ struct vertex * v;
+ struct routing_table * t;
+ struct nhop * n;
+
+ /* We need at least 2 vertices for a table */
+ if (graph->nr_vertices < 2)
+ goto fail_vertices;
+
+ if (dijkstra(graph, s_addr, &nhops, dist))
+ goto fail_vertices;
+
+ list_head_init(table);
+
+ /* Now construct the routing table from the nhops. */
+ list_for_each(p, &graph->vertices) {
+ v = list_entry(p, struct vertex, next);
+
+ /* This is the src */
+ if (nhops[i] == NULL) {
+ i++;
+ continue;
+ }
+
+ t = malloc(sizeof(*t));
+ if (t == NULL)
+ goto fail_t;
+
+ list_head_init(&t->nhops);
+
+ n = malloc(sizeof(*n));
+ if (n == NULL)
+ goto fail_n;
+
+ t->dst = v->addr;
+ n->nhop = nhops[i]->addr;
+
+ list_add(&n->next, &t->nhops);
+ list_add(&t->next, table);
+
+ i++;
+ }
+
+ free(nhops);
+
+ return 0;
+
+ fail_n:
+ free(t);
+ fail_t:
+ free_routing_table(table);
+ free(nhops);
+ free(*dist);
+ fail_vertices:
+ *dist = NULL;
+ return -1;
+}
+
+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;
+ }
+ }
+
+ free(n);
+
+ return -1;
+}
+
+int graph_routing_table(struct graph * graph,
+ enum routing_algo algo,
+ uint64_t s_addr,
+ struct list_head * table)
+{
+ int * s_dist;
+ int * n_dist[PROG_MAX_FLOWS];
+ uint64_t addrs[PROG_MAX_FLOWS];
+ int n_index[PROG_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);
+
+ /* Get the simple next hops routing table. */
+ if (graph_routing_table_simple(graph, s_addr, table, &s_dist))
+ goto fail_table_simple;
+
+ /* Possibly augment the routing table. */
+ switch (algo) {
+ case ROUTING_SIMPLE:
+ break;
+ case ROUTING_LFA:
+ for (j = 0; j < PROG_MAX_FLOWS; j++) {
+ n_dist[j] = NULL;
+ n_index[j] = -1;
+ addrs[j] = -1;
+ }
+
+ 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;
+ }
+ }
+
+ for (j = 0; j < i; j++)
+ free(n_dist[j]);
+
+ break;
+ default:
+ log_err("Unsupported algorithm.");
+ goto fail_algo;
+ }
+
+ 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);
+ fail_algo:
+ free(s_dist);
+ fail_table_simple:
+ pthread_mutex_unlock(&graph->lock);
+
+ return -1;
+}
diff --git a/src/ipcpd/unicast/pol/graph.h b/src/ipcpd/unicast/pol/graph.h
new file mode 100644
index 00000000..06a2bd0d
--- /dev/null
+++ b/src/ipcpd/unicast/pol/graph.h
@@ -0,0 +1,68 @@
+/*
+ * Ouroboros - Copyright (C) 2016 - 2019
+ *
+ * Undirected graph structure
+ *
+ * Dimitri Staessens <[email protected]>
+ * Sander Vrijders <[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_GRAPH_H
+#define OUROBOROS_IPCPD_UNICAST_GRAPH_H
+
+#include <ouroboros/list.h>
+#include <ouroboros/qos.h>
+
+#include <inttypes.h>
+
+enum routing_algo {
+ ROUTING_SIMPLE = 0,
+ ROUTING_LFA
+};
+
+struct nhop {
+ struct list_head next;
+ uint64_t nhop;
+};
+
+struct routing_table {
+ struct list_head next;
+ uint64_t dst;
+ struct list_head nhops;
+};
+
+struct graph * graph_create(void);
+
+void graph_destroy(struct graph * graph);
+
+int graph_update_edge(struct graph * graph,
+ uint64_t s_addr,
+ uint64_t d_addr,
+ qosspec_t qs);
+
+int graph_del_edge(struct graph * graph,
+ uint64_t s_addr,
+ uint64_t d_addr);
+
+int graph_routing_table(struct graph * graph,
+ enum routing_algo algo,
+ uint64_t s_addr,
+ struct list_head * table);
+
+void graph_free_routing_table(struct graph * graph,
+ struct list_head * table);
+
+#endif /* OUROBOROS_IPCPD_UNICAST_GRAPH_H */
diff --git a/src/ipcpd/unicast/pol/link_state.c b/src/ipcpd/unicast/pol/link_state.c
new file mode 100644
index 00000000..d8f0e263
--- /dev/null
+++ b/src/ipcpd/unicast/pol/link_state.c
@@ -0,0 +1,1022 @@
+/*
+ * Ouroboros - Copyright (C) 2016 - 2019
+ *
+ * Link state routing policy
+ *
+ * Dimitri Staessens <[email protected]>
+ * Sander Vrijders <[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/.
+ */
+
+#if defined(__linux__) || defined(__CYGWIN__)
+#define _DEFAULT_SOURCE
+#else
+#define _POSIX_C_SOURCE 200112L
+#endif
+
+#include "config.h"
+
+#define OUROBOROS_PREFIX "link-state-routing"
+
+#include <ouroboros/endian.h>
+#include <ouroboros/dev.h>
+#include <ouroboros/errno.h>
+#include <ouroboros/fccntl.h>
+#include <ouroboros/fqueue.h>
+#include <ouroboros/list.h>
+#include <ouroboros/logs.h>
+#include <ouroboros/notifier.h>
+#include <ouroboros/rib.h>
+#include <ouroboros/utils.h>
+
+#include "comp.h"
+#include "connmgr.h"
+#include "graph.h"
+#include "ipcp.h"
+#include "link_state.h"
+#include "pff.h"
+
+#include <assert.h>
+#include <stdlib.h>
+#include <inttypes.h>
+#include <string.h>
+#include <pthread.h>
+
+#define RECALC_TIME 4
+#define LS_UPDATE_TIME 15
+#define LS_TIMEO 60
+#define LS_ENTRY_SIZE 104
+#define LSDB "lsdb"
+
+#ifndef CLOCK_REALTIME_COARSE
+#define CLOCK_REALTIME_COARSE CLOCK_REALTIME
+#endif
+
+struct lsa {
+ uint64_t d_addr;
+ uint64_t s_addr;
+ uint64_t seqno;
+} __attribute__((packed));
+
+struct routing_i {
+ struct list_head next;
+
+ struct pff * pff;
+ pthread_t calculator;
+
+ bool modified;
+ pthread_mutex_t lock;
+};
+
+/* TODO: link weight support. */
+struct adjacency {
+ struct list_head next;
+
+ uint64_t dst;
+ uint64_t src;
+
+ uint64_t seqno;
+
+ time_t stamp;
+};
+
+enum nb_type {
+ NB_DT = 0,
+ NB_MGMT
+};
+
+struct nb {
+ struct list_head next;
+
+ uint64_t addr;
+ int fd;
+ enum nb_type type;
+};
+
+struct {
+ struct list_head nbs;
+ size_t nbs_len;
+ fset_t * mgmt_set;
+
+ struct list_head db;
+ size_t db_len;
+
+ pthread_rwlock_t db_lock;
+
+ struct graph * graph;
+
+ pthread_t lsupdate;
+ pthread_t lsreader;
+ pthread_t listener;
+
+ struct list_head routing_instances;
+ pthread_mutex_t routing_i_lock;
+
+ enum routing_algo routing_algo;
+} ls;
+
+struct pol_routing_ops link_state_ops = {
+ .init = link_state_init,
+ .fini = link_state_fini,
+ .routing_i_create = link_state_routing_i_create,
+ .routing_i_destroy = link_state_routing_i_destroy
+};
+
+static int str_adj(struct adjacency * adj,
+ char * buf,
+ size_t len)
+{
+ char tmbuf[64];
+ char srcbuf[64];
+ char dstbuf[64];
+ char seqnobuf[64];
+ struct tm * tm;
+
+ if (len < LS_ENTRY_SIZE)
+ return -1;
+
+ tm = localtime(&adj->stamp);
+ strftime(tmbuf, sizeof(tmbuf), "%F %T", tm); /* 19 chars */
+
+ sprintf(srcbuf, "%" PRIu64, adj->src);
+ sprintf(dstbuf, "%" PRIu64, adj->dst);
+ sprintf(seqnobuf, "%" PRIu64, adj->seqno);
+
+ sprintf(buf, "src: %20s\ndst: %20s\nseqno: %18s\nupd: %20s\n",
+ srcbuf, dstbuf, seqnobuf, tmbuf);
+
+ return LS_ENTRY_SIZE;
+}
+
+static struct adjacency * get_adj(const char * path)
+{
+ struct list_head * p;
+ char entry[RIB_PATH_LEN + 1];
+
+ assert(path);
+
+ list_for_each(p, &ls.db) {
+ struct adjacency * a = list_entry(p, struct adjacency, next);
+ sprintf(entry, "%" PRIu64 ".%" PRIu64, a->src, a->dst);
+ if (strcmp(entry, path) == 0)
+ return a;
+ }
+
+ return NULL;
+}
+
+static int lsdb_getattr(const char * path,
+ struct stat * st)
+{
+ struct adjacency * adj;
+ struct timespec now;
+
+ clock_gettime(CLOCK_REALTIME_COARSE, &now);
+
+ pthread_rwlock_rdlock(&ls.db_lock);
+
+ adj = get_adj(path);
+ if (adj != NULL) {
+ st->st_mtime = adj->stamp;
+ st->st_size = LS_ENTRY_SIZE;
+ } else {
+ st->st_mtime = now.tv_sec;
+ st->st_size = 0;
+ }
+
+ st->st_mode = S_IFREG | 0755;
+ st->st_nlink = 1;
+ st->st_uid = getuid();
+ st->st_gid = getgid();
+
+ pthread_rwlock_unlock(&ls.db_lock);
+
+ return 0;
+}
+
+static int lsdb_read(const char * path,
+ char * buf,
+ size_t len)
+{
+ struct adjacency * a;
+ int size;
+
+ pthread_rwlock_rdlock(&ls.db_lock);
+
+ if (ls.db_len + ls.nbs_len == 0)
+ goto fail;
+
+ a = get_adj(path);
+ if (a == NULL)
+ goto fail;
+
+ size = str_adj(a, buf, len);
+ if (size < 0)
+ goto fail;
+
+ pthread_rwlock_unlock(&ls.db_lock);
+ return size;
+
+ fail:
+ pthread_rwlock_unlock(&ls.db_lock);
+ return -1;
+}
+
+static int lsdb_readdir(char *** buf)
+{
+ struct list_head * p;
+ char entry[RIB_PATH_LEN + 1];
+ ssize_t idx = 0;
+
+ pthread_rwlock_rdlock(&ls.db_lock);
+
+ if (ls.db_len + ls.nbs_len == 0) {
+ pthread_rwlock_unlock(&ls.db_lock);
+ return 0;
+ }
+
+ *buf = malloc(sizeof(**buf) * (ls.db_len + ls.nbs_len));
+ if (*buf == NULL) {
+ pthread_rwlock_unlock(&ls.db_lock);
+ return -ENOMEM;
+ }
+
+ list_for_each(p, &ls.nbs) {
+ struct nb * nb = list_entry(p, struct nb, next);
+ char * str = (nb->type == NB_DT ? "dt." : "mgmt.");
+ sprintf(entry, "%s%" PRIu64, str, nb->addr);
+ (*buf)[idx] = malloc(strlen(entry) + 1);
+ if ((*buf)[idx] == NULL) {
+ while (idx-- > 0)
+ free((*buf)[idx]);
+ free(buf);
+ pthread_rwlock_unlock(&ls.db_lock);
+ return -ENOMEM;
+ }
+
+ strcpy((*buf)[idx], entry);
+
+ idx++;
+ }
+
+ list_for_each(p, &ls.db) {
+ struct adjacency * a = list_entry(p, struct adjacency, next);
+ sprintf(entry, "%" PRIu64 ".%" PRIu64, a->src, a->dst);
+ (*buf)[idx] = malloc(strlen(entry) + 1);
+ if ((*buf)[idx] == NULL) {
+ ssize_t j;
+ for (j = 0; j < idx; ++j)
+ free(*buf[j]);
+ free(buf);
+ pthread_rwlock_unlock(&ls.db_lock);
+ return -ENOMEM;
+ }
+
+ strcpy((*buf)[idx], entry);
+
+ idx++;
+ }
+
+ pthread_rwlock_unlock(&ls.db_lock);
+
+ return idx;
+}
+
+static struct rib_ops r_ops = {
+ .read = lsdb_read,
+ .readdir = lsdb_readdir,
+ .getattr = lsdb_getattr
+};
+
+static int lsdb_add_nb(uint64_t addr,
+ int fd,
+ enum nb_type type)
+{
+ struct list_head * p;
+ struct nb * nb;
+
+ pthread_rwlock_wrlock(&ls.db_lock);
+
+ list_for_each(p, &ls.nbs) {
+ struct nb * el = list_entry(p, struct nb, next);
+ if (el->addr == addr && el->type == type) {
+ log_dbg("Already know %s neighbor %" PRIu64 ".",
+ type == NB_DT ? "dt" : "mgmt", addr);
+ if (el->fd != fd) {
+ log_warn("Existing neighbor assigned new fd.");
+ el->fd = fd;
+ }
+ pthread_rwlock_unlock(&ls.db_lock);
+ return -EPERM;
+ }
+
+ if (addr > el->addr)
+ break;
+ }
+
+ nb = malloc(sizeof(*nb));
+ if (nb == NULL) {
+ pthread_rwlock_unlock(&ls.db_lock);
+ return -ENOMEM;
+ }
+
+ nb->addr = addr;
+ nb->fd = fd;
+ nb->type = type;
+
+ list_add_tail(&nb->next, p);
+
+ ++ls.nbs_len;
+
+ log_dbg("Type %s neighbor %" PRIu64 " added.",
+ nb->type == NB_DT ? "dt" : "mgmt", addr);
+
+ pthread_rwlock_unlock(&ls.db_lock);
+
+ return 0;
+}
+
+static int lsdb_del_nb(uint64_t addr,
+ int fd)
+{
+ struct list_head * p;
+ struct list_head * h;
+
+ pthread_rwlock_wrlock(&ls.db_lock);
+
+ list_for_each_safe(p, h, &ls.nbs) {
+ struct nb * nb = list_entry(p, struct nb, next);
+ if (nb->addr == addr && nb->fd == fd) {
+ list_del(&nb->next);
+ --ls.nbs_len;
+ pthread_rwlock_unlock(&ls.db_lock);
+ log_dbg("Type %s neighbor %" PRIu64 " deleted.",
+ nb->type == NB_DT ? "dt" : "mgmt", addr);
+ free(nb);
+ return 0;
+ }
+ }
+
+ pthread_rwlock_unlock(&ls.db_lock);
+
+ return -EPERM;
+}
+
+static int nbr_to_fd(uint64_t addr)
+{
+ struct list_head * p;
+
+ pthread_rwlock_rdlock(&ls.db_lock);
+
+ list_for_each(p, &ls.nbs) {
+ struct nb * nb = list_entry(p, struct nb, next);
+ if (nb->addr == addr && nb->type == NB_DT) {
+ pthread_rwlock_unlock(&ls.db_lock);
+ return nb->fd;
+ }
+ }
+
+ pthread_rwlock_unlock(&ls.db_lock);
+
+ return -1;
+}
+
+static void calculate_pff(struct routing_i * instance)
+{
+ int fd;
+ struct list_head table;
+ struct list_head * p;
+ struct list_head * q;
+ int fds[PROG_MAX_FLOWS];
+
+ if (graph_routing_table(ls.graph, ls.routing_algo,
+ ipcpi.dt_addr, &table))
+ return;
+
+ pff_lock(instance->pff);
+
+ pff_flush(instance->pff);
+
+ /* Calculate forwarding table from routing table. */
+ list_for_each(p, &table) {
+ int i = 0;
+ struct routing_table * t =
+ list_entry(p, struct routing_table, next);
+
+ list_for_each(q, &t->nhops) {
+ struct nhop * n = list_entry(q, struct nhop, next);
+
+ fd = nbr_to_fd(n->nhop);
+ if (fd == -1)
+ continue;
+
+ fds[i++] = fd;
+ }
+ if (i > 0)
+ pff_add(instance->pff, t->dst, fds, i);
+ }
+
+ pff_unlock(instance->pff);
+
+ graph_free_routing_table(ls.graph, &table);
+}
+
+static void set_pff_modified(bool calc)
+{
+ struct list_head * p;
+
+ pthread_mutex_lock(&ls.routing_i_lock);
+ list_for_each(p, &ls.routing_instances) {
+ struct routing_i * inst =
+ list_entry(p, struct routing_i, next);
+ pthread_mutex_lock(&inst->lock);
+ inst->modified = true;
+ pthread_mutex_unlock(&inst->lock);
+ if (calc)
+ calculate_pff(inst);
+ }
+ pthread_mutex_unlock(&ls.routing_i_lock);
+}
+
+static int lsdb_add_link(uint64_t src,
+ uint64_t dst,
+ uint64_t seqno,
+ qosspec_t * qs)
+{
+ struct list_head * p;
+ struct adjacency * adj;
+ struct timespec now;
+ int ret = -1;
+
+ clock_gettime(CLOCK_REALTIME_COARSE, &now);
+
+ pthread_rwlock_wrlock(&ls.db_lock);
+
+ list_for_each(p, &ls.db) {
+ struct adjacency * a = list_entry(p, struct adjacency, next);
+ if (a->dst == dst && a->src == src) {
+ if (a->seqno < seqno) {
+ a->stamp = now.tv_sec;
+ a->seqno = seqno;
+ ret = 0;
+ }
+ pthread_rwlock_unlock(&ls.db_lock);
+ return ret;
+ }
+
+ if (a->dst > dst || (a->dst == dst && a->src > src))
+ break;
+ }
+
+ adj = malloc(sizeof(*adj));
+ if (adj == NULL) {
+ pthread_rwlock_unlock(&ls.db_lock);
+ return -ENOMEM;
+ }
+
+ adj->dst = dst;
+ adj->src = src;
+ adj->seqno = seqno;
+ adj->stamp = now.tv_sec;
+
+ list_add_tail(&adj->next, p);
+
+ ls.db_len++;
+
+ if (graph_update_edge(ls.graph, src, dst, *qs))
+ log_warn("Failed to add edge to graph.");
+
+ pthread_rwlock_unlock(&ls.db_lock);
+
+ set_pff_modified(true);
+
+ return 0;
+}
+
+static int lsdb_del_link(uint64_t src,
+ uint64_t dst)
+{
+ struct list_head * p;
+ struct list_head * h;
+
+ pthread_rwlock_wrlock(&ls.db_lock);
+
+ list_for_each_safe(p, h, &ls.db) {
+ struct adjacency * a = list_entry(p, struct adjacency, next);
+ if (a->dst == dst && a->src == src) {
+ list_del(&a->next);
+ if (graph_del_edge(ls.graph, src, dst))
+ log_warn("Failed to delete edge from graph.");
+
+ ls.db_len--;
+
+ pthread_rwlock_unlock(&ls.db_lock);
+ set_pff_modified(false);
+ free(a);
+ return 0;
+ }
+ }
+
+ pthread_rwlock_unlock(&ls.db_lock);
+
+ return -EPERM;
+}
+
+static void * periodic_recalc_pff(void * o)
+{
+ bool modified;
+ struct routing_i * inst = (struct routing_i *) o;
+
+ while (true) {
+ pthread_mutex_lock(&inst->lock);
+ modified = inst->modified;
+ inst->modified = false;
+ pthread_mutex_unlock(&inst->lock);
+
+ if (modified)
+ calculate_pff(inst);
+ sleep(RECALC_TIME);
+ }
+
+ return (void *) 0;
+}
+
+static void send_lsm(uint64_t src,
+ uint64_t dst,
+ uint64_t seqno)
+{
+ struct lsa lsm;
+ struct list_head * p;
+
+ lsm.d_addr = hton64(dst);
+ lsm.s_addr = hton64(src);
+ lsm.seqno = hton64(seqno);
+
+ list_for_each(p, &ls.nbs) {
+ struct nb * nb = list_entry(p, struct nb, next);
+ if (nb->type == NB_MGMT)
+ flow_write(nb->fd, &lsm, sizeof(lsm));
+ }
+}
+
+/* replicate the lsdb to a mgmt neighbor */
+static void lsdb_replicate(int fd)
+{
+ struct list_head * p;
+ struct list_head * h;
+ struct list_head copy;
+
+ list_head_init(&copy);
+
+ /* Lock the lsdb, copy the lsms and send outside of lock. */
+ pthread_rwlock_rdlock(&ls.db_lock);
+
+ list_for_each(p, &ls.db) {
+ struct adjacency * adj;
+ struct adjacency * cpy;
+ adj = list_entry(p, struct adjacency, next);
+ cpy = malloc(sizeof(*cpy));
+ if (cpy == NULL) {
+ log_warn("Failed to replicate full lsdb.");
+ break;
+ }
+
+ cpy->dst = adj->dst;
+ cpy->src = adj->src;
+ cpy->seqno = adj->seqno;
+
+ list_add_tail(&cpy->next, &copy);
+ }
+
+ pthread_rwlock_unlock(&ls.db_lock);
+
+ list_for_each_safe(p, h, &copy) {
+ struct lsa lsm;
+ struct adjacency * adj;
+ adj = list_entry(p, struct adjacency, next);
+ lsm.d_addr = hton64(adj->dst);
+ lsm.s_addr = hton64(adj->src);
+ lsm.seqno = hton64(adj->seqno);
+ list_del(&adj->next);
+ free(adj);
+ flow_write(fd, &lsm, sizeof(lsm));
+ }
+}
+
+static void * lsupdate(void * o)
+{
+ struct list_head * p;
+ struct list_head * h;
+ struct timespec now;
+
+ (void) o;
+
+ while (true) {
+ clock_gettime(CLOCK_REALTIME_COARSE, &now);
+
+ pthread_rwlock_rdlock(&ls.db_lock);
+
+ pthread_cleanup_push((void (*) (void *)) pthread_rwlock_unlock,
+ (void *) &ls.db_lock);
+
+ list_for_each_safe(p, h, &ls.db) {
+ struct adjacency * adj;
+ adj = list_entry(p, struct adjacency, next);
+ if (now.tv_sec - adj->stamp > LS_TIMEO) {
+ list_del(&adj->next);
+ log_dbg("%" PRIu64 " - %" PRIu64" timed out.",
+ adj->src, adj->dst);
+ if (graph_del_edge(ls.graph, adj->src,
+ adj->dst))
+ log_err("Failed to del edge.");
+ free(adj);
+ continue;
+ }
+
+ if (adj->src == ipcpi.dt_addr) {
+ adj->seqno++;
+ send_lsm(adj->src, adj->dst, adj->seqno);
+ adj->stamp = now.tv_sec;
+ }
+ }
+
+ pthread_cleanup_pop(true);
+
+ sleep(LS_UPDATE_TIME);
+ }
+
+ return (void *) 0;
+}
+
+static void * ls_conn_handle(void * o)
+{
+ struct conn conn;
+
+ (void) o;
+
+ while (true) {
+ if (connmgr_wait(COMPID_MGMT, &conn)) {
+ log_err("Failed to get next MGMT connection.");
+ continue;
+ }
+
+ /* NOTE: connection acceptance policy could be here. */
+
+ notifier_event(NOTIFY_MGMT_CONN_ADD, &conn);
+ }
+
+ return 0;
+}
+
+
+static void forward_lsm(uint8_t * buf,
+ size_t len,
+ int in_fd)
+{
+ struct list_head * p;
+
+ pthread_rwlock_rdlock(&ls.db_lock);
+
+ pthread_cleanup_push((void (*))(void *) pthread_rwlock_unlock,
+ &ls.db_lock);
+
+ list_for_each(p, &ls.nbs) {
+ struct nb * nb = list_entry(p, struct nb, next);
+ if (nb->type == NB_MGMT && nb->fd != in_fd)
+ flow_write(nb->fd, buf, len);
+ }
+
+ pthread_cleanup_pop(true);
+}
+
+static void * lsreader(void * o)
+{
+ fqueue_t * fq;
+ int ret;
+ uint8_t buf[sizeof(struct lsa)];
+ int fd;
+ qosspec_t qs;
+ struct lsa * msg;
+ size_t len;
+
+ (void) o;
+
+ memset(&qs, 0, sizeof(qs));
+
+ fq = fqueue_create();
+ if (fq == NULL)
+ return (void *) -1;
+
+ pthread_cleanup_push((void (*) (void *)) fqueue_destroy,
+ (void *) fq);
+
+ while (true) {
+ ret = fevent(ls.mgmt_set, fq, NULL);
+ if (ret < 0) {
+ log_warn("Event error: %d.", ret);
+ continue;
+ }
+
+ while ((fd = fqueue_next(fq)) >= 0) {
+ if (fqueue_type(fq) != FLOW_PKT)
+ continue;
+
+ len = flow_read(fd, buf, sizeof(*msg));
+ if (len <= 0 || len != sizeof(*msg))
+ continue;
+
+ msg = (struct lsa *) buf;
+
+ if (lsdb_add_link(ntoh64(msg->s_addr),
+ ntoh64(msg->d_addr),
+ ntoh64(msg->seqno),
+ &qs))
+ continue;
+
+ forward_lsm(buf, len, fd);
+ }
+ }
+
+ pthread_cleanup_pop(true);
+
+ return (void *) 0;
+}
+
+static void flow_event(int fd,
+ bool up)
+{
+
+ struct list_head * p;
+
+ log_dbg("Notifying routing instances of flow event.");
+
+ pthread_mutex_lock(&ls.routing_i_lock);
+
+ list_for_each(p, &ls.routing_instances) {
+ struct routing_i * ri = list_entry(p, struct routing_i, next);
+ pff_flow_state_change(ri->pff, fd, up);
+ }
+
+ pthread_mutex_unlock(&ls.routing_i_lock);
+}
+
+static void handle_event(void * self,
+ int event,
+ const void * o)
+{
+ /* FIXME: Apply correct QoS on graph */
+ struct conn * c;
+ qosspec_t qs;
+ int flags;
+
+ (void) self;
+
+ c = (struct conn *) o;
+
+ memset(&qs, 0, sizeof(qs));
+
+ switch (event) {
+ case NOTIFY_DT_CONN_ADD:
+ pthread_rwlock_rdlock(&ls.db_lock);
+ send_lsm(ipcpi.dt_addr, c->conn_info.addr, 0);
+ pthread_rwlock_unlock(&ls.db_lock);
+
+ if (lsdb_add_nb(c->conn_info.addr, c->flow_info.fd, NB_DT))
+ log_dbg("Failed to add neighbor to LSDB.");
+
+ if (lsdb_add_link(ipcpi.dt_addr, c->conn_info.addr, 0, &qs))
+ log_dbg("Failed to add new adjacency to LSDB.");
+ break;
+ case NOTIFY_DT_CONN_DEL:
+ flow_event(c->flow_info.fd, false);
+
+ if (lsdb_del_nb(c->conn_info.addr, c->flow_info.fd))
+ log_dbg("Failed to delete neighbor from LSDB.");
+
+ if (lsdb_del_link(ipcpi.dt_addr, c->conn_info.addr))
+ log_dbg("Local link was not in LSDB.");
+ break;
+ case NOTIFY_DT_CONN_QOS:
+ log_dbg("QoS changes currently unsupported.");
+ break;
+ case NOTIFY_DT_CONN_UP:
+ flow_event(c->flow_info.fd, true);
+ break;
+ case NOTIFY_DT_CONN_DOWN:
+ flow_event(c->flow_info.fd, false);
+ break;
+ case NOTIFY_MGMT_CONN_ADD:
+ fccntl(c->flow_info.fd, FLOWGFLAGS, &flags);
+ fccntl(c->flow_info.fd, FLOWSFLAGS, flags | FLOWFRNOPART);
+ fset_add(ls.mgmt_set, c->flow_info.fd);
+ if (lsdb_add_nb(c->conn_info.addr, c->flow_info.fd, NB_MGMT))
+ log_warn("Failed to add mgmt neighbor to LSDB.");
+ /* replicate the entire lsdb */
+ lsdb_replicate(c->flow_info.fd);
+ break;
+ case NOTIFY_MGMT_CONN_DEL:
+ fset_del(ls.mgmt_set, c->flow_info.fd);
+ if (lsdb_del_nb(c->conn_info.addr, c->flow_info.fd))
+ log_warn("Failed to delete mgmt neighbor from LSDB.");
+ break;
+ default:
+ break;
+ }
+}
+
+struct routing_i * link_state_routing_i_create(struct pff * pff)
+{
+ struct routing_i * tmp;
+
+ assert(pff);
+
+ tmp = malloc(sizeof(*tmp));
+ if (tmp == NULL)
+ goto fail_tmp;
+
+ tmp->pff = pff;
+ tmp->modified = false;
+
+ if (pthread_mutex_init(&tmp->lock, NULL))
+ goto fail_instance_lock_init;
+
+ if (pthread_create(&tmp->calculator, NULL,
+ periodic_recalc_pff, tmp))
+ goto fail_pthread_create_lsupdate;
+
+ pthread_mutex_lock(&ls.routing_i_lock);
+
+ list_add(&tmp->next, &ls.routing_instances);
+
+ pthread_mutex_unlock(&ls.routing_i_lock);
+
+ return tmp;
+
+ fail_pthread_create_lsupdate:
+ pthread_mutex_destroy(&tmp->lock);
+ fail_instance_lock_init:
+ free(tmp);
+ fail_tmp:
+ return NULL;
+}
+
+void link_state_routing_i_destroy(struct routing_i * instance)
+{
+ assert(instance);
+
+ pthread_mutex_lock(&ls.routing_i_lock);
+
+ list_del(&instance->next);
+
+ pthread_mutex_unlock(&ls.routing_i_lock);
+
+ pthread_cancel(instance->calculator);
+
+ pthread_join(instance->calculator, NULL);
+
+ pthread_mutex_destroy(&instance->lock);
+
+ free(instance);
+}
+
+int link_state_init(enum pol_routing pr)
+{
+ struct conn_info info;
+
+ memset(&info, 0, sizeof(info));
+
+ strcpy(info.comp_name, LS_COMP);
+ strcpy(info.protocol, LS_PROTO);
+ info.pref_version = 1;
+ info.pref_syntax = PROTO_GPB;
+ info.addr = ipcpi.dt_addr;
+
+ switch (pr) {
+ case ROUTING_LINK_STATE:
+ log_dbg("Using link state routing policy.");
+ ls.routing_algo = ROUTING_SIMPLE;
+ break;
+ case ROUTING_LINK_STATE_LFA:
+ log_dbg("Using Loop-Free Alternates policy.");
+ ls.routing_algo = ROUTING_LFA;
+ break;
+ default:
+ goto fail_graph;
+ }
+
+ ls.graph = graph_create();
+ if (ls.graph == NULL)
+ goto fail_graph;
+
+ if (notifier_reg(handle_event, NULL))
+ goto fail_notifier_reg;
+
+ if (pthread_rwlock_init(&ls.db_lock, NULL))
+ goto fail_db_lock_init;
+
+ if (pthread_mutex_init(&ls.routing_i_lock, NULL))
+ goto fail_routing_i_lock_init;
+
+ if (connmgr_comp_init(COMPID_MGMT, &info))
+ goto fail_connmgr_comp_init;
+
+ ls.mgmt_set = fset_create();
+ if (ls.mgmt_set == NULL)
+ goto fail_fset_create;
+
+ list_head_init(&ls.db);
+ list_head_init(&ls.nbs);
+ list_head_init(&ls.routing_instances);
+
+ if (pthread_create(&ls.lsupdate, NULL, lsupdate, NULL))
+ goto fail_pthread_create_lsupdate;
+
+ if (pthread_create(&ls.lsreader, NULL, lsreader, NULL))
+ goto fail_pthread_create_lsreader;
+
+ if (pthread_create(&ls.listener, NULL, ls_conn_handle, NULL))
+ goto fail_pthread_create_listener;
+
+ if (rib_reg(LSDB, &r_ops))
+ goto fail_rib_reg;
+
+ ls.db_len = 0;
+ ls.nbs_len = 0;
+
+ return 0;
+
+ fail_rib_reg:
+ pthread_cancel(ls.listener);
+ pthread_join(ls.listener, NULL);
+ fail_pthread_create_listener:
+ pthread_cancel(ls.lsreader);
+ pthread_join(ls.lsreader, NULL);
+ fail_pthread_create_lsreader:
+ pthread_cancel(ls.lsupdate);
+ pthread_join(ls.lsupdate, NULL);
+ fail_pthread_create_lsupdate:
+ fset_destroy(ls.mgmt_set);
+ fail_fset_create:
+ connmgr_comp_fini(COMPID_MGMT);
+ fail_connmgr_comp_init:
+ pthread_mutex_destroy(&ls.routing_i_lock);
+ fail_routing_i_lock_init:
+ pthread_rwlock_destroy(&ls.db_lock);
+ fail_db_lock_init:
+ notifier_unreg(handle_event);
+ fail_notifier_reg:
+ graph_destroy(ls.graph);
+ fail_graph:
+ return -1;
+}
+
+void link_state_fini(void)
+{
+ struct list_head * p;
+ struct list_head * h;
+
+ rib_unreg(LSDB);
+
+ pthread_cancel(ls.listener);
+ pthread_join(ls.listener, NULL);
+
+ pthread_cancel(ls.lsreader);
+ pthread_join(ls.lsreader, NULL);
+
+ pthread_cancel(ls.lsupdate);
+ pthread_join(ls.lsupdate, NULL);
+
+ fset_destroy(ls.mgmt_set);
+
+ connmgr_comp_fini(COMPID_MGMT);
+
+ graph_destroy(ls.graph);
+
+ pthread_rwlock_wrlock(&ls.db_lock);
+
+ list_for_each_safe(p, h, &ls.db) {
+ struct adjacency * a = list_entry(p, struct adjacency, next);
+ list_del(&a->next);
+ free(a);
+ }
+
+ pthread_rwlock_unlock(&ls.db_lock);
+
+ pthread_rwlock_destroy(&ls.db_lock);
+
+ pthread_mutex_destroy(&ls.routing_i_lock);
+
+ notifier_unreg(handle_event);
+}
diff --git a/src/ipcpd/unicast/pol/link_state.h b/src/ipcpd/unicast/pol/link_state.h
new file mode 100644
index 00000000..a7b44b4e
--- /dev/null
+++ b/src/ipcpd/unicast/pol/link_state.h
@@ -0,0 +1,41 @@
+/*
+ * Ouroboros - Copyright (C) 2016 - 2019
+ *
+ * Link state routing policy
+ *
+ * Dimitri Staessens <[email protected]>
+ * Sander Vrijders <[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_POL_LINK_STATE_H
+#define OUROBOROS_IPCPD_UNICAST_POL_LINK_STATE_H
+
+#define LS_COMP "Management"
+#define LS_PROTO "LSP"
+
+#include "pol-routing-ops.h"
+
+int link_state_init(enum pol_routing pr);
+
+void link_state_fini(void);
+
+struct routing_i * link_state_routing_i_create(struct pff * pff);
+
+void link_state_routing_i_destroy(struct routing_i * instance);
+
+struct pol_routing_ops link_state_ops;
+
+#endif /* OUROBOROS_IPCPD_UNICAST_POL_LINK_STATE_H */
diff --git a/src/ipcpd/unicast/pol/simple_pff.c b/src/ipcpd/unicast/pol/simple_pff.c
new file mode 100644
index 00000000..4338c53c
--- /dev/null
+++ b/src/ipcpd/unicast/pol/simple_pff.c
@@ -0,0 +1,187 @@
+/*
+ * Ouroboros - Copyright (C) 2016 - 2019
+ *
+ * Simple PDU Forwarding Function
+ *
+ * Dimitri Staessens <[email protected]>
+ * Sander Vrijders <[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/hashtable.h>
+#include <ouroboros/errno.h>
+
+#include <assert.h>
+#include <pthread.h>
+
+#include "simple_pff.h"
+
+struct pff_i {
+ struct htable * table;
+ pthread_rwlock_t lock;
+};
+
+struct pol_pff_ops simple_pff_ops = {
+ .create = simple_pff_create,
+ .destroy = simple_pff_destroy,
+ .lock = simple_pff_lock,
+ .unlock = simple_pff_unlock,
+ .add = simple_pff_add,
+ .update = simple_pff_update,
+ .del = simple_pff_del,
+ .flush = simple_pff_flush,
+ .nhop = simple_pff_nhop,
+ .flow_state_change = NULL
+};
+
+struct pff_i * simple_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->table = htable_create(PFT_SIZE, false);
+ if (tmp->table == NULL) {
+ pthread_rwlock_destroy(&tmp->lock);
+ free(tmp);
+ return NULL;
+ }
+
+ return tmp;
+}
+
+void simple_pff_destroy(struct pff_i * pff_i)
+{
+ assert(pff_i);
+
+ htable_destroy(pff_i->table);
+
+ pthread_rwlock_destroy(&pff_i->lock);
+ free(pff_i);
+}
+
+void simple_pff_lock(struct pff_i * pff_i)
+{
+ pthread_rwlock_wrlock(&pff_i->lock);
+}
+
+void simple_pff_unlock(struct pff_i * pff_i)
+{
+ pthread_rwlock_unlock(&pff_i->lock);
+}
+
+int simple_pff_add(struct pff_i * pff_i,
+ uint64_t addr,
+ int * fd,
+ size_t len)
+{
+ int * val;
+
+ assert(pff_i);
+ assert(len > 0);
+
+ (void) len;
+
+ val = malloc(sizeof(*val));
+ if (val == NULL)
+ return -ENOMEM;
+
+ *val = fd[0];
+
+ if (htable_insert(pff_i->table, addr, val, 1)) {
+ free(val);
+ return -1;
+ }
+
+ return 0;
+}
+
+int simple_pff_update(struct pff_i * pff_i,
+ uint64_t addr,
+ int * fd,
+ size_t len)
+{
+ int * val;
+
+ assert(pff_i);
+ assert(len > 0);
+
+ (void) len;
+
+ val = malloc(sizeof(*val));
+ if (val == NULL)
+ return -ENOMEM;
+ *val = fd[0];
+
+ if (htable_delete(pff_i->table, addr)) {
+ free(val);
+ return -1;
+ }
+
+ if (htable_insert(pff_i->table, addr, val, 1)) {
+ free(val);
+ return -1;
+ }
+
+ return 0;
+}
+
+int simple_pff_del(struct pff_i * pff_i,
+ uint64_t addr)
+{
+ assert(pff_i);
+
+ if (htable_delete(pff_i->table, addr))
+ return -1;
+
+ return 0;
+}
+
+void simple_pff_flush(struct pff_i * pff_i)
+{
+ assert(pff_i);
+
+ htable_flush(pff_i->table);
+}
+
+int simple_pff_nhop(struct pff_i * pff_i,
+ uint64_t addr)
+{
+ void * j;
+ size_t len;
+ int fd = -1;
+
+ assert(pff_i);
+
+ pthread_rwlock_rdlock(&pff_i->lock);
+
+ if (!htable_lookup(pff_i->table, addr, &j, &len))
+ fd = *((int *) j);
+
+ pthread_rwlock_unlock(&pff_i->lock);
+
+ return fd;
+}
diff --git a/src/ipcpd/unicast/pol/simple_pff.h b/src/ipcpd/unicast/pol/simple_pff.h
new file mode 100644
index 00000000..02c09a58
--- /dev/null
+++ b/src/ipcpd/unicast/pol/simple_pff.h
@@ -0,0 +1,57 @@
+/*
+ * Ouroboros - Copyright (C) 2016 - 2019
+ *
+ * Simple policy for PFF
+ *
+ * Dimitri Staessens <[email protected]>
+ * Sander Vrijders <[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_SIMPLE_PFF_H
+#define OUROBOROS_IPCPD_UNICAST_SIMPLE_PFF_H
+
+#include "pol-pff-ops.h"
+
+struct pff_i * simple_pff_create(void);
+
+void simple_pff_destroy(struct pff_i * pff_i);
+
+void simple_pff_lock(struct pff_i * pff_i);
+
+void simple_pff_unlock(struct pff_i * pff_i);
+
+int simple_pff_add(struct pff_i * pff_i,
+ uint64_t addr,
+ int * fd,
+ size_t len);
+
+int simple_pff_update(struct pff_i * pff_i,
+ uint64_t addr,
+ int * fd,
+ size_t len);
+
+int simple_pff_del(struct pff_i * pff_i,
+ uint64_t addr);
+
+void simple_pff_flush(struct pff_i * pff_i);
+
+/* Returns fd towards next hop */
+int simple_pff_nhop(struct pff_i * pff_i,
+ uint64_t addr);
+
+struct pol_pff_ops simple_pff_ops;
+
+#endif /* OUROBOROS_IPCPD_UNICAST_SIMPLE_PFF_H */
diff --git a/src/ipcpd/unicast/pol/tests/CMakeLists.txt b/src/ipcpd/unicast/pol/tests/CMakeLists.txt
new file mode 100644
index 00000000..d0652533
--- /dev/null
+++ b/src/ipcpd/unicast/pol/tests/CMakeLists.txt
@@ -0,0 +1,34 @@
+get_filename_component(CURRENT_SOURCE_PARENT_DIR
+ ${CMAKE_CURRENT_SOURCE_DIR} DIRECTORY)
+get_filename_component(CURRENT_BINARY_PARENT_DIR
+ ${CMAKE_CURRENT_BINARY_DIR} DIRECTORY)
+
+include_directories(${CMAKE_CURRENT_SOURCE_DIR})
+include_directories(${CMAKE_CURRENT_BINARY_DIR})
+
+include_directories(${CURRENT_SOURCE_PARENT_DIR})
+include_directories(${CURRENT_BINARY_PARENT_DIR})
+
+include_directories(${CMAKE_SOURCE_DIR}/include)
+include_directories(${CMAKE_BINARY_DIR}/include)
+
+get_filename_component(PARENT_PATH ${CMAKE_CURRENT_SOURCE_DIR} DIRECTORY)
+get_filename_component(PARENT_DIR ${PARENT_PATH} NAME)
+
+create_test_sourcelist(${PARENT_DIR}_tests test_suite.c
+ # Add new tests here
+ graph_test.c
+ )
+
+add_executable(${PARENT_DIR}_test EXCLUDE_FROM_ALL ${${PARENT_DIR}_tests})
+target_link_libraries(${PARENT_DIR}_test ouroboros-common)
+
+add_dependencies(check ${PARENT_DIR}_test)
+
+set(tests_to_run ${${PARENT_DIR}_tests})
+remove(tests_to_run test_suite.c)
+
+foreach (test ${tests_to_run})
+ get_filename_component(test_name ${test} NAME_WE)
+ add_test(${test_name} ${C_TEST_PATH}/${PARENT_DIR}_test ${test_name})
+endforeach (test)
diff --git a/src/ipcpd/unicast/pol/tests/graph_test.c b/src/ipcpd/unicast/pol/tests/graph_test.c
new file mode 100644
index 00000000..a312c1a8
--- /dev/null
+++ b/src/ipcpd/unicast/pol/tests/graph_test.c
@@ -0,0 +1,300 @@
+/*
+ * Ouroboros - Copyright (C) 2016 - 2019
+ *
+ * Test of the graph structure
+ *
+ * Dimitri Staessens <[email protected]>
+ * Sander Vrijders <[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 <ouroboros/utils.h>
+
+#include <stdio.h>
+#include <stdlib.h>
+#include <string.h>
+
+#include "graph.c"
+
+struct graph * graph;
+struct list_head table;
+qosspec_t qs;
+
+int graph_test_entries(int entries)
+{
+ struct list_head * p;
+ int i = 0;
+
+ if (graph_routing_table(graph, ROUTING_SIMPLE, 1, &table)) {
+ printf("Failed to get routing table.\n");
+ return -1;
+ }
+
+ list_for_each(p, &table)
+ i++;
+
+ if (i != entries) {
+ printf("Wrong number of entries.\n");
+ graph_free_routing_table(graph, &table);
+ return -1;
+ }
+
+ graph_free_routing_table(graph, &table);
+
+ return 0;
+}
+
+int graph_test_double_link(void)
+{
+ struct list_head * p;
+ int i = 0;
+
+ if (graph_routing_table(graph, ROUTING_SIMPLE, 1, &table)) {
+ printf("Failed to get routing table.\n");
+ return -1;
+ }
+
+ list_for_each(p, &table)
+ i++;
+
+ if (i != 2) {
+ printf("Wrong number of entries.\n");
+ graph_free_routing_table(graph, &table);
+ return -1;
+ }
+
+ list_for_each(p, &table) {
+ struct routing_table * t =
+ list_entry(p, struct routing_table, next);
+ struct nhop * n =
+ list_first_entry(&t->nhops, struct nhop, next);
+
+ if ((t->dst != 2 && n->nhop != 2) ||
+ (t->dst != 3 && n->nhop != 2)) {
+ printf("Wrong routing entry.\n");
+ graph_free_routing_table(graph, &table);
+ return -1;
+ }
+ }
+
+ graph_free_routing_table(graph, &table);
+
+ return 0;
+}
+
+int graph_test_single_link(void)
+{
+ struct list_head * p;
+ int i = 0;
+
+ if (graph_routing_table(graph, ROUTING_SIMPLE, 1, &table)) {
+ printf("Failed to get routing table.\n");
+ return -1;
+ }
+
+ list_for_each(p, &table)
+ i++;
+
+ if (i != 1) {
+ printf("Wrong number of entries.\n");
+ graph_free_routing_table(graph, &table);
+ return -1;
+ }
+
+ list_for_each(p, &table) {
+ struct routing_table * t =
+ list_entry(p, struct routing_table, next);
+ struct nhop * n =
+ list_first_entry(&t->nhops, struct nhop, next);
+
+ if (t->dst != 2 && n->nhop != 2) {
+ printf("Wrong routing entry.\n");
+ graph_free_routing_table(graph, &table);
+ return -1;
+ }
+ }
+
+ graph_free_routing_table(graph, &table);
+
+ return 0;
+}
+
+int graph_test(int argc,
+ char ** argv)
+{
+ int nhop;
+ int dst;
+ struct list_head * p;
+
+ (void) argc;
+ (void) argv;
+
+ memset(&qs, 0, sizeof(qs));
+
+ graph = graph_create();
+ if (graph == NULL) {
+ printf("Failed to create graph.\n");
+ return -1;
+ }
+
+ graph_destroy(graph);
+
+ graph = graph_create();
+ if (graph == NULL) {
+ printf("Failed to create graph.\n");
+ return -1;
+ }
+
+ if (graph_update_edge(graph, 1, 2, qs)) {
+ printf("Failed to add edge.\n");
+ graph_destroy(graph);
+ return -1;
+ }
+
+ if (graph_update_edge(graph, 2, 1, qs)) {
+ printf("Failed to add edge.\n");
+ graph_destroy(graph);
+ return -1;
+ }
+
+ if (graph_test_single_link()) {
+ graph_destroy(graph);
+ return -1;
+ }
+
+ if (graph_update_edge(graph, 2, 3, qs)) {
+ printf("Failed to add edge.\n");
+ graph_destroy(graph);
+ return -1;
+ }
+
+ if (graph_update_edge(graph, 3, 2, qs)) {
+ printf("Failed to add edge.\n");
+ graph_destroy(graph);
+ return -1;
+ }
+
+
+ if (graph_test_double_link()) {
+ graph_destroy(graph);
+ return -1;
+ }
+
+ if (graph_del_edge(graph, 2, 3)) {
+ printf("Failed to delete edge.\n");
+ graph_destroy(graph);
+ return -1;
+ }
+
+ if (graph_del_edge(graph, 3, 2)) {
+ printf("Failed to delete edge.\n");
+ graph_destroy(graph);
+ return -1;
+ }
+
+ if (graph_test_single_link()) {
+ graph_destroy(graph);
+ return -1;
+ }
+
+ graph_update_edge(graph, 2, 3, qs);
+ graph_update_edge(graph, 3, 2, qs);
+ graph_update_edge(graph, 1, 3, qs);
+ graph_update_edge(graph, 3, 1, qs);
+
+ if (graph_test_entries(2)) {
+ graph_destroy(graph);
+ return -1;
+ }
+
+ graph_update_edge(graph, 3, 4, qs);
+ graph_update_edge(graph, 4, 3, qs);
+ graph_update_edge(graph, 4, 5, qs);
+ graph_update_edge(graph, 5, 4, qs);
+
+ if (graph_test_entries(4)) {
+ graph_destroy(graph);
+ return -1;
+ }
+
+ graph_update_edge(graph, 2, 6, qs);
+ graph_update_edge(graph, 6, 2, qs);
+ graph_update_edge(graph, 6, 7, qs);
+ graph_update_edge(graph, 7, 6, qs);
+ graph_update_edge(graph, 3, 7, qs);
+ graph_update_edge(graph, 7, 3, qs);
+
+ if (graph_test_entries(6)) {
+ graph_destroy(graph);
+ return -1;
+ }
+
+ if (graph_routing_table(graph, ROUTING_SIMPLE, 1, &table)) {
+ printf("Failed to get routing table.\n");
+ return -1;
+ }
+
+ list_for_each(p, &table) {
+ struct routing_table * t =
+ list_entry(p, struct routing_table, next);
+ struct nhop * n =
+ list_first_entry(&t->nhops, struct nhop, next);
+
+ dst = t->dst;
+ nhop = n->nhop;
+
+ if (dst == 3 && nhop != 3) {
+ printf("Wrong entry.");
+ graph_free_routing_table(graph, &table);
+ return -1;
+ }
+
+ if (dst == 2 && nhop != 2) {
+ printf("Wrong entry.");
+ graph_free_routing_table(graph, &table);
+ return -1;
+ }
+
+ if (dst == 6 && nhop != 2) {
+ printf("Wrong entry.");
+ graph_free_routing_table(graph, &table);
+ return -1;
+ }
+
+ if (dst == 4 && nhop != 3) {
+ printf("Wrong entry.");
+ graph_free_routing_table(graph, &table);
+ return -1;
+ }
+
+ if (dst == 5 && nhop != 3) {
+ printf("Wrong entry.");
+ graph_free_routing_table(graph, &table);
+ return -1;
+ }
+
+ if (dst == 7 && nhop != 3) {
+ printf("Wrong entry.");
+ graph_free_routing_table(graph, &table);
+ return -1;
+ }
+ }
+
+ graph_free_routing_table(graph, &table);
+
+ return 0;
+}
generated by cgit v1.2.3 (git 2.39.1) at 2024-11-28 22:42:45 +0000