From e43fd05ba896ad5b4ac390f6097d6e6a06308f28 Mon Sep 17 00:00:00 2001 From: Sander Vrijders Date: Wed, 29 Mar 2017 14:42:37 +0200 Subject: ipcpd: normal: Make graph undirected This turns the directed graph into an undirected one. Only one side of the flow creates an FSDB entry. The graph structure creates an edge object for every vertex involved when an edge is updated or removed. --- src/ipcpd/normal/graph.c | 38 ++++++++++++++++++++++++++++++++------ src/ipcpd/normal/graph.h | 2 +- src/ipcpd/normal/routing.c | 4 ++++ 3 files changed, 37 insertions(+), 7 deletions(-) (limited to 'src/ipcpd') diff --git a/src/ipcpd/normal/graph.c b/src/ipcpd/normal/graph.c index 5fd6fcb6..5de7c15b 100644 --- a/src/ipcpd/normal/graph.c +++ b/src/ipcpd/normal/graph.c @@ -1,7 +1,7 @@ /* * Ouroboros - Copyright (C) 2016 - 2017 * - * Graph structure + * Undirected graph structure * * Dimitri Staessens * Sander Vrijders @@ -205,6 +205,7 @@ int graph_update_edge(struct graph * graph, struct vertex * v; struct edge * e; struct vertex * nb; + struct edge * nb_e; assert(graph); @@ -237,9 +238,9 @@ int graph_update_edge(struct graph * graph, e = add_edge(v, nb); if (e == NULL) { if (list_is_empty(&v->edges)) - del_vertex(graph, v); + del_vertex(graph, v); if (list_is_empty(&nb->edges)) - del_vertex(graph, v); + del_vertex(graph, nb); pthread_mutex_unlock(&graph->lock); log_err("Failed to add edge."); return -ENOMEM; @@ -248,6 +249,23 @@ int graph_update_edge(struct graph * graph, 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) { + 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->qs = qs; + pthread_mutex_unlock(&graph->lock); return 0; @@ -260,6 +278,7 @@ int graph_del_edge(struct graph * graph, struct vertex * v; struct edge * e; struct vertex * nb; + struct edge * nb_e; assert(graph); @@ -286,14 +305,21 @@ int graph_del_edge(struct graph * graph, return -1; } + nb_e = find_edge_by_addr(nb, s_addr); + if (nb_e == NULL) { + pthread_mutex_unlock(&graph->lock); + log_err("No such edge."); + return -1; + } + del_edge(e); + del_edge(nb_e); /* Removing vertex if it was the last edge */ if (list_is_empty(&v->edges)) - del_vertex(graph, v); - + del_vertex(graph, v); if (list_is_empty(&nb->edges)) - del_vertex(graph, v); + del_vertex(graph, nb); pthread_mutex_unlock(&graph->lock); diff --git a/src/ipcpd/normal/graph.h b/src/ipcpd/normal/graph.h index 70be8626..44496bc3 100644 --- a/src/ipcpd/normal/graph.h +++ b/src/ipcpd/normal/graph.h @@ -1,7 +1,7 @@ /* * Ouroboros - Copyright (C) 2016 - 2017 * - * Graph structure + * Undirected graph structure * * Dimitri Staessens * Sander Vrijders diff --git a/src/ipcpd/normal/routing.c b/src/ipcpd/normal/routing.c index bf736311..bd41b489 100644 --- a/src/ipcpd/normal/routing.c +++ b/src/ipcpd/normal/routing.c @@ -157,6 +157,10 @@ static int routing_neighbor_event(enum nb_event event, size_t len; uint8_t * data; + /* Only announce the flow if our address is bigger */ + if (ipcpi.dt_addr < conn.conn_info.addr) + return 0; + path[0] = '\0'; sprintf(fso_name, "%" PRIu64 "-%" PRIu64, ipcpi.dt_addr, conn.conn_info.addr); -- cgit v1.2.3 From d90c66cc6beba511f6bcc48a3ea3fc4e774b5ab8 Mon Sep 17 00:00:00 2001 From: Sander Vrijders Date: Wed, 29 Mar 2017 17:55:14 +0200 Subject: ipcpd: normal: Add graph regression test This adds a regression test for the graph component to test the routing table. --- src/ipcpd/normal/CMakeLists.txt | 2 +- src/ipcpd/normal/routing.c | 2 +- src/ipcpd/normal/tests/CMakeLists.txt | 34 +++++ src/ipcpd/normal/tests/graph_test.c | 240 ++++++++++++++++++++++++++++++++++ src/ipcpd/tests/CMakeLists.txt | 15 ++- 5 files changed, 285 insertions(+), 8 deletions(-) create mode 100644 src/ipcpd/normal/tests/CMakeLists.txt create mode 100644 src/ipcpd/normal/tests/graph_test.c (limited to 'src/ipcpd') diff --git a/src/ipcpd/normal/CMakeLists.txt b/src/ipcpd/normal/CMakeLists.txt index 06292c50..69615d0c 100644 --- a/src/ipcpd/normal/CMakeLists.txt +++ b/src/ipcpd/normal/CMakeLists.txt @@ -50,4 +50,4 @@ endif (CMAKE_BUILD_TYPE MATCHES Debug) install(TARGETS ipcpd-normal RUNTIME DESTINATION sbin) # Enable once ipcp-normal has tests -# add_subdirectory(tests) +add_subdirectory(tests) diff --git a/src/ipcpd/normal/routing.c b/src/ipcpd/normal/routing.c index bd41b489..cc6cdca8 100644 --- a/src/ipcpd/normal/routing.c +++ b/src/ipcpd/normal/routing.c @@ -92,7 +92,7 @@ static void * calculate_pff(void * o) table = NULL; n_table = graph_routing_table(routing.graph, ipcpi.dt_addr, &table); - if (table == NULL) { + if (n_table < 0) { sleep(RECALC_TIME); continue; } diff --git a/src/ipcpd/normal/tests/CMakeLists.txt b/src/ipcpd/normal/tests/CMakeLists.txt new file mode 100644 index 00000000..55ca425a --- /dev/null +++ b/src/ipcpd/normal/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) + +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/tests/graph_test.c b/src/ipcpd/normal/tests/graph_test.c new file mode 100644 index 00000000..3d433e34 --- /dev/null +++ b/src/ipcpd/normal/tests/graph_test.c @@ -0,0 +1,240 @@ +/* + * Ouroboros - Copyright (C) 2016 - 2017 + * + * 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., 675 Mass Ave, Cambridge, MA 02139, USA. + */ + +#include +#include + +#include +#include +#include + +#include "graph.c" + +struct graph * graph; +struct routing_table ** table; +ssize_t n_table; +qosspec_t qs; + +int graph_test_entries(int entries) +{ + n_table = graph_routing_table(graph, 1, &table); + + if (n_table != entries) { + printf("Wrong number of entries.\n"); + freepp(struct routing_table, table, n_table); + return -1; + } + + freepp(struct routing_table, table, n_table); + + return 0; +} + +int graph_test_double_link(void) +{ + n_table = graph_routing_table(graph, 1, &table); + if (n_table < 0 || table == NULL) { + printf("Failed to get routing table.\n"); + return -1; + } + + if (n_table != 2) { + printf("Wrong number of entries.\n"); + freepp(struct routing_table, table, n_table); + return -1; + } + + if ((table[0]->dst != 2 && table[0]->nhop != 2) || + (table[0]->dst != 3 && table[0]->nhop != 2)) { + printf("Wrong routing entry.\n"); + freepp(struct routing_table, table, n_table); + return -1; + } + + if ((table[1]->dst != 2 && table[1]->nhop != 2) || + (table[0]->dst != 3 && table[0]->nhop != 2)) { + printf("Wrong routing entry.\n"); + freepp(struct routing_table, table, n_table); + return -1; + } + + freepp(struct routing_table, table, n_table); + + return 0; +} + +int graph_test_single_link(void) +{ + n_table = graph_routing_table(graph, 1, &table); + if (n_table < 0 || table == NULL) { + printf("Failed to get routing table.\n"); + return -1; + } + + if (n_table != 1) { + printf("Wrong number of entries.\n"); + freepp(struct routing_table, table, n_table); + return -1; + } + + if (table[0]->dst != 2 && table[0]->nhop != 2) { + printf("Wrong routing entry.\n"); + freepp(struct routing_table, table, n_table); + return -1; + } + + freepp(struct routing_table, table, n_table); + + return 0; +} + +int graph_test(int argc, + char ** argv) +{ + int i; + int nhop; + int dst; + + (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_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_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_test_single_link()) { + graph_destroy(graph); + return -1; + } + + graph_update_edge(graph, 2, 3, qs); + graph_update_edge(graph, 1, 3, qs); + + if (graph_test_entries(2)) { + graph_destroy(graph); + return -1; + } + + graph_update_edge(graph, 3, 4, qs); + graph_update_edge(graph, 4, 5, qs); + + if (graph_test_entries(4)) { + graph_destroy(graph); + return -1; + } + + graph_update_edge(graph, 2, 6, qs); + graph_update_edge(graph, 6, 7, qs); + graph_update_edge(graph, 3, 7, qs); + + if (graph_test_entries(6)) { + graph_destroy(graph); + return -1; + } + + n_table = graph_routing_table(graph, 1, &table); + + for (i = 0; i < 6; i++) { + nhop = table[i]->nhop; + dst = table[i]->dst; + + if (dst == 3 && nhop != 3) { + printf("Wrong entry."); + freepp(struct routing_table, table, n_table); + return -1; + } + + if (dst == 2 && nhop != 2) { + printf("Wrong entry."); + freepp(struct routing_table, table, n_table); + return -1; + } + + if (dst == 6 && nhop != 2) { + printf("Wrong entry."); + freepp(struct routing_table, table, n_table); + return -1; + } + + if (dst == 4 && nhop != 3) { + printf("Wrong entry."); + freepp(struct routing_table, table, n_table); + return -1; + } + + if (dst == 5 && nhop != 3) { + printf("Wrong entry."); + freepp(struct routing_table, table, n_table); + return -1; + } + + if (dst == 7 && nhop != 3) { + printf("Wrong entry."); + freepp(struct routing_table, table, n_table); + return -1; + } + } + + freepp(struct routing_table, table, n_table); + + return 0; +} diff --git a/src/ipcpd/tests/CMakeLists.txt b/src/ipcpd/tests/CMakeLists.txt index 07430127..9b5eeaa1 100644 --- a/src/ipcpd/tests/CMakeLists.txt +++ b/src/ipcpd/tests/CMakeLists.txt @@ -12,20 +12,23 @@ include_directories(${CURRENT_BINARY_PARENT_DIR}) include_directories(${CMAKE_SOURCE_DIR}/include) include_directories(${CMAKE_BINARY_DIR}/include) -create_test_sourcelist(${src_folder}_tests test_suite.c +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 timerwheel_test.c ) -add_executable(${src_folder}_test EXCLUDE_FROM_ALL ${${src_folder}_tests}) -target_link_libraries(${src_folder}_test ouroboros) +add_executable(${PARENT_DIR}_test EXCLUDE_FROM_ALL ${${PARENT_DIR}_tests}) +target_link_libraries(${PARENT_DIR}_test ouroboros) -add_dependencies(check ${src_folder}_test) +add_dependencies(check ${PARENT_DIR}_test) -set(tests_to_run ${${src_folder}_tests}) +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}/${src_folder}_test ${test_name}) + add_test(${test_name} ${C_TEST_PATH}/${PARENT_DIR}_test ${test_name}) endforeach (test) -- cgit v1.2.3