From dae15c284248d49079ad5f8a3d8ff30e217f419e Mon Sep 17 00:00:00 2001 From: Dimitri Staessens Date: Thu, 25 Jul 2019 12:50:46 +0200 Subject: build: Refactor normal to unicast This completes the renaming of the normal IPCP to the unicast IPCP in the sources, to get everything consistent with the documentation. Signed-off-by: Dimitri Staessens Signed-off-by: Sander Vrijders --- src/ipcpd/unicast/pol/alternate_pff.c | 403 +++++++++++ src/ipcpd/unicast/pol/alternate_pff.h | 61 ++ src/ipcpd/unicast/pol/flat.c | 87 +++ src/ipcpd/unicast/pol/flat.h | 36 + src/ipcpd/unicast/pol/graph.c | 695 +++++++++++++++++++ src/ipcpd/unicast/pol/graph.h | 68 ++ src/ipcpd/unicast/pol/link_state.c | 1022 ++++++++++++++++++++++++++++ src/ipcpd/unicast/pol/link_state.h | 41 ++ src/ipcpd/unicast/pol/simple_pff.c | 187 +++++ src/ipcpd/unicast/pol/simple_pff.h | 57 ++ src/ipcpd/unicast/pol/tests/CMakeLists.txt | 34 + src/ipcpd/unicast/pol/tests/graph_test.c | 300 ++++++++ 12 files changed, 2991 insertions(+) create mode 100644 src/ipcpd/unicast/pol/alternate_pff.c create mode 100644 src/ipcpd/unicast/pol/alternate_pff.h create mode 100644 src/ipcpd/unicast/pol/flat.c create mode 100644 src/ipcpd/unicast/pol/flat.h create mode 100644 src/ipcpd/unicast/pol/graph.c create mode 100644 src/ipcpd/unicast/pol/graph.h create mode 100644 src/ipcpd/unicast/pol/link_state.c create mode 100644 src/ipcpd/unicast/pol/link_state.h create mode 100644 src/ipcpd/unicast/pol/simple_pff.c create mode 100644 src/ipcpd/unicast/pol/simple_pff.h create mode 100644 src/ipcpd/unicast/pol/tests/CMakeLists.txt create mode 100644 src/ipcpd/unicast/pol/tests/graph_test.c (limited to 'src/ipcpd/unicast/pol') 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 + * Sander Vrijders + * + * 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 +#include +#include + +#include +#include +#include + +#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 + * Sander Vrijders + * + * 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 + * Sander Vrijders + * + * 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 +#include +#include +#include + +#include "ipcp.h" +#include "flat.h" + +#include +#include +#include +#include +#include + +#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 + * Sander Vrijders + * + * 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 + * Sander Vrijders + * + * 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 +#include +#include + +#include "graph.h" +#include "ipcp.h" + +#include +#include +#include +#include +#include + +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 + * Sander Vrijders + * + * 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 +#include + +#include + +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 + * Sander Vrijders + * + * 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 +#include +#include +#include +#include +#include +#include +#include +#include +#include + +#include "comp.h" +#include "connmgr.h" +#include "graph.h" +#include "ipcp.h" +#include "link_state.h" +#include "pff.h" + +#include +#include +#include +#include +#include + +#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(©); + + /* 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, ©); + } + + pthread_rwlock_unlock(&ls.db_lock); + + list_for_each_safe(p, h, ©) { + 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 + * Sander Vrijders + * + * 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 + * Sander Vrijders + * + * 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 +#include + +#include +#include + +#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 + * Sander Vrijders + * + * 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 + * Sander Vrijders + * + * 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 + +#include +#include +#include + +#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; +} -- cgit v1.2.3