diff options
Diffstat (limited to 'src/ipcpd/normal/pol')
| -rw-r--r-- | src/ipcpd/normal/pol/alternate_pff.c | 403 | ||||
| -rw-r--r-- | src/ipcpd/normal/pol/alternate_pff.h | 61 | ||||
| -rw-r--r-- | src/ipcpd/normal/pol/flat.c | 87 | ||||
| -rw-r--r-- | src/ipcpd/normal/pol/flat.h | 36 | ||||
| -rw-r--r-- | src/ipcpd/normal/pol/graph.c | 695 | ||||
| -rw-r--r-- | src/ipcpd/normal/pol/graph.h | 68 | ||||
| -rw-r--r-- | src/ipcpd/normal/pol/link_state.c | 1022 | ||||
| -rw-r--r-- | src/ipcpd/normal/pol/link_state.h | 41 | ||||
| -rw-r--r-- | src/ipcpd/normal/pol/simple_pff.c | 187 | ||||
| -rw-r--r-- | src/ipcpd/normal/pol/simple_pff.h | 57 | ||||
| -rw-r--r-- | src/ipcpd/normal/pol/tests/CMakeLists.txt | 34 | ||||
| -rw-r--r-- | src/ipcpd/normal/pol/tests/graph_test.c | 300 |
12 files changed, 0 insertions, 2991 deletions
diff --git a/src/ipcpd/normal/pol/alternate_pff.c b/src/ipcpd/normal/pol/alternate_pff.c deleted file mode 100644 index 38937297..00000000 --- a/src/ipcpd/normal/pol/alternate_pff.c +++ /dev/null @@ -1,403 +0,0 @@ -/* - * Ouroboros - Copyright (C) 2016 - 2019 - * - * Policy for PFF with alternate next hops - * - * Dimitri Staessens <dimitri.staessens@ugent.be> - * Sander Vrijders <sander.vrijders@ugent.be> - * - * This program is free software; you can redistribute it and/or modify - * it under the terms of the GNU General Public License version 2 as - * published by the Free Software Foundation. - * - * This program is distributed in the hope that it will be useful, - * but WITHOUT ANY WARRANTY; without even the implied warranty of - * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the - * GNU General Public License for more details. - * - * You should have received a copy of the GNU General Public License - * along with this program; if not, write to the Free Software - * Foundation, Inc., http://www.fsf.org/about/contact/. - */ - -#define _POSIX_C_SOURCE 200112L - -#include "config.h" - -#include <ouroboros/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/normal/pol/alternate_pff.h b/src/ipcpd/normal/pol/alternate_pff.h deleted file mode 100644 index 3bfbb886..00000000 --- a/src/ipcpd/normal/pol/alternate_pff.h +++ /dev/null @@ -1,61 +0,0 @@ -/* - * Ouroboros - Copyright (C) 2016 - 2019 - * - * Policy for PFF with alternate next hops - * - * Dimitri Staessens <dimitri.staessens@ugent.be> - * Sander Vrijders <sander.vrijders@ugent.be> - * - * This program is free software; you can redistribute it and/or modify - * it under the terms of the GNU General Public License version 2 as - * published by the Free Software Foundation. - * - * This program is distributed in the hope that it will be useful, - * but WITHOUT ANY WARRANTY; without even the implied warranty of - * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the - * GNU General Public License for more details. - * - * You should have received a copy of the GNU General Public License - * along with this program; if not, write to the Free Software - * Foundation, Inc., http://www.fsf.org/about/contact/. - */ - -#ifndef OUROBOROS_IPCPD_NORMAL_ALTERNATE_PFF_H -#define OUROBOROS_IPCPD_NORMAL_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_NORMAL_ALTERNATE_PFF_H */ diff --git a/src/ipcpd/normal/pol/flat.c b/src/ipcpd/normal/pol/flat.c deleted file mode 100644 index 157885f9..00000000 --- a/src/ipcpd/normal/pol/flat.c +++ /dev/null @@ -1,87 +0,0 @@ -/* - * Ouroboros - Copyright (C) 2016 - 2019 - * - * Policy for flat addresses in a distributed way - * - * Dimitri Staessens <dimitri.staessens@ugent.be> - * Sander Vrijders <sander.vrijders@ugent.be> - * - * This program is free software; you can redistribute it and/or modify - * it under the terms of the GNU General Public License version 2 as - * published by the Free Software Foundation. - * - * This program is distributed in the hope that it will be useful, - * but WITHOUT ANY WARRANTY; without even the implied warranty of - * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the - * GNU General Public License for more details. - * - * You should have received a copy of the GNU General Public License - * along with this program; if not, write to the Free Software - * Foundation, Inc., http://www.fsf.org/about/contact/. - */ - -#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/normal/pol/flat.h b/src/ipcpd/normal/pol/flat.h deleted file mode 100644 index 9df3de51..00000000 --- a/src/ipcpd/normal/pol/flat.h +++ /dev/null @@ -1,36 +0,0 @@ -/* - * Ouroboros - Copyright (C) 2016 - 2019 - * - * Policy for flat addresses in a distributed way - * - * Dimitri Staessens <dimitri.staessens@ugent.be> - * Sander Vrijders <sander.vrijders@ugent.be> - * - * This program is free software; you can redistribute it and/or modify - * it under the terms of the GNU General Public License version 2 as - * published by the Free Software Foundation. - * - * This program is distributed in the hope that it will be useful, - * but WITHOUT ANY WARRANTY; without even the implied warranty of - * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the - * GNU General Public License for more details. - * - * You should have received a copy of the GNU General Public License - * along with this program; if not, write to the Free Software - * Foundation, Inc., http://www.fsf.org/about/contact/. - */ - -#ifndef OUROBOROS_IPCPD_NORMAL_FLAT_H -#define OUROBOROS_IPCPD_NORMAL_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_NORMAL_FLAT_H */ diff --git a/src/ipcpd/normal/pol/graph.c b/src/ipcpd/normal/pol/graph.c deleted file mode 100644 index 6c93bb62..00000000 --- a/src/ipcpd/normal/pol/graph.c +++ /dev/null @@ -1,695 +0,0 @@ -/* - * Ouroboros - Copyright (C) 2016 - 2019 - * - * Undirected graph structure - * - * Dimitri Staessens <dimitri.staessens@ugent.be> - * Sander Vrijders <sander.vrijders@ugent.be> - * - * This program is free software; you can redistribute it and/or modify - * it under the terms of the GNU General Public License version 2 as - * published by the Free Software Foundation. - * - * This program is distributed in the hope that it will be useful, - * but WITHOUT ANY WARRANTY; without even the implied warranty of - * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the - * GNU General Public License for more details. - * - * You should have received a copy of the GNU General Public License - * along with this program; if not, write to the Free Software - * Foundation, Inc., http://www.fsf.org/about/contact/. - */ - -#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 normal 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/normal/pol/graph.h b/src/ipcpd/normal/pol/graph.h deleted file mode 100644 index 131e9eca..00000000 --- a/src/ipcpd/normal/pol/graph.h +++ /dev/null @@ -1,68 +0,0 @@ -/* - * Ouroboros - Copyright (C) 2016 - 2019 - * - * Undirected graph structure - * - * Dimitri Staessens <dimitri.staessens@ugent.be> - * Sander Vrijders <sander.vrijders@ugent.be> - * - * This program is free software; you can redistribute it and/or modify - * it under the terms of the GNU General Public License version 2 as - * published by the Free Software Foundation. - * - * This program is distributed in the hope that it will be useful, - * but WITHOUT ANY WARRANTY; without even the implied warranty of - * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the - * GNU General Public License for more details. - * - * You should have received a copy of the GNU General Public License - * along with this program; if not, write to the Free Software - * Foundation, Inc., http://www.fsf.org/about/contact/. - */ - -#ifndef OUROBOROS_IPCPD_NORMAL_GRAPH_H -#define OUROBOROS_IPCPD_NORMAL_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_NORMAL_GRAPH_H */ diff --git a/src/ipcpd/normal/pol/link_state.c b/src/ipcpd/normal/pol/link_state.c deleted file mode 100644 index d8f0e263..00000000 --- a/src/ipcpd/normal/pol/link_state.c +++ /dev/null @@ -1,1022 +0,0 @@ -/* - * Ouroboros - Copyright (C) 2016 - 2019 - * - * Link state routing policy - * - * Dimitri Staessens <dimitri.staessens@ugent.be> - * Sander Vrijders <sander.vrijders@ugent.be> - * - * This program is free software; you can redistribute it and/or modify - * it under the terms of the GNU General Public License version 2 as - * published by the Free Software Foundation. - * - * This program is distributed in the hope that it will be useful, - * but WITHOUT ANY WARRANTY; without even the implied warranty of - * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the - * GNU General Public License for more details. - * - * You should have received a copy of the GNU General Public License - * along with this program; if not, write to the Free Software - * Foundation, Inc., http://www.fsf.org/about/contact/. - */ - -#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(©); - - /* 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/normal/pol/link_state.h b/src/ipcpd/normal/pol/link_state.h deleted file mode 100644 index 3fcb03ff..00000000 --- a/src/ipcpd/normal/pol/link_state.h +++ /dev/null @@ -1,41 +0,0 @@ -/* - * Ouroboros - Copyright (C) 2016 - 2019 - * - * Link state routing policy - * - * Dimitri Staessens <dimitri.staessens@ugent.be> - * Sander Vrijders <sander.vrijders@ugent.be> - * - * This program is free software; you can redistribute it and/or modify - * it under the terms of the GNU General Public License version 2 as - * published by the Free Software Foundation. - * - * This program is distributed in the hope that it will be useful, - * but WITHOUT ANY WARRANTY; without even the implied warranty of - * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the - * GNU General Public License for more details. - * - * You should have received a copy of the GNU General Public License - * along with this program; if not, write to the Free Software - * Foundation, Inc., http://www.fsf.org/about/contact/. - */ - -#ifndef OUROBOROS_IPCPD_NORMAL_POL_LINK_STATE_H -#define OUROBOROS_IPCPD_NORMAL_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_NORMAL_POL_LINK_STATE_H */ diff --git a/src/ipcpd/normal/pol/simple_pff.c b/src/ipcpd/normal/pol/simple_pff.c deleted file mode 100644 index 4338c53c..00000000 --- a/src/ipcpd/normal/pol/simple_pff.c +++ /dev/null @@ -1,187 +0,0 @@ -/* - * Ouroboros - Copyright (C) 2016 - 2019 - * - * Simple PDU Forwarding Function - * - * Dimitri Staessens <dimitri.staessens@ugent.be> - * Sander Vrijders <sander.vrijders@ugent.be> - * - * This program is free software; you can redistribute it and/or modify - * it under the terms of the GNU General Public License version 2 as - * published by the Free Software Foundation. - * - * This program is distributed in the hope that it will be useful, - * but WITHOUT ANY WARRANTY; without even the implied warranty of - * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the - * GNU General Public License for more details. - * - * You should have received a copy of the GNU General Public License - * along with this program; if not, write to the Free Software - * Foundation, Inc., http://www.fsf.org/about/contact/. - */ - -#define _POSIX_C_SOURCE 200112L - -#include "config.h" - -#include <ouroboros/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/normal/pol/simple_pff.h b/src/ipcpd/normal/pol/simple_pff.h deleted file mode 100644 index 08504e4e..00000000 --- a/src/ipcpd/normal/pol/simple_pff.h +++ /dev/null @@ -1,57 +0,0 @@ -/* - * Ouroboros - Copyright (C) 2016 - 2019 - * - * Simple policy for PFF - * - * Dimitri Staessens <dimitri.staessens@ugent.be> - * Sander Vrijders <sander.vrijders@ugent.be> - * - * This program is free software; you can redistribute it and/or modify - * it under the terms of the GNU General Public License version 2 as - * published by the Free Software Foundation. - * - * This program is distributed in the hope that it will be useful, - * but WITHOUT ANY WARRANTY; without even the implied warranty of - * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the - * GNU General Public License for more details. - * - * You should have received a copy of the GNU General Public License - * along with this program; if not, write to the Free Software - * Foundation, Inc., http://www.fsf.org/about/contact/. - */ - -#ifndef OUROBOROS_IPCPD_NORMAL_SIMPLE_PFF_H -#define OUROBOROS_IPCPD_NORMAL_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_NORMAL_SIMPLE_PFF_H */ diff --git a/src/ipcpd/normal/pol/tests/CMakeLists.txt b/src/ipcpd/normal/pol/tests/CMakeLists.txt deleted file mode 100644 index d0652533..00000000 --- a/src/ipcpd/normal/pol/tests/CMakeLists.txt +++ /dev/null @@ -1,34 +0,0 @@ -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/normal/pol/tests/graph_test.c b/src/ipcpd/normal/pol/tests/graph_test.c deleted file mode 100644 index a312c1a8..00000000 --- a/src/ipcpd/normal/pol/tests/graph_test.c +++ /dev/null @@ -1,300 +0,0 @@ -/* - * Ouroboros - Copyright (C) 2016 - 2019 - * - * Test of the graph structure - * - * Dimitri Staessens <dimitri.staessens@ugent.be> - * Sander Vrijders <sander.vrijders@ugent.be> - * - * This program is free software; you can redistribute it and/or modify - * it under the terms of the GNU General Public License version 2 as - * published by the Free Software Foundation. - * - * This program is distributed in the hope that it will be useful, - * but WITHOUT ANY WARRANTY; without even the implied warranty of - * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the - * GNU General Public License for more details. - * - * You should have received a copy of the GNU General Public License - * along with this program; if not, write to the Free Software - * Foundation, Inc., http://www.fsf.org/about/contact/. - */ - -#define _POSIX_C_SOURCE 200112L - -#include <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; -} |