From 11d2ecc140486949c8d81e984137263ca48d5799 Mon Sep 17 00:00:00 2001 From: Dimitri Staessens Date: Sat, 4 Dec 2021 15:35:36 +0100 Subject: ipcpd: Restructure policy code The policies were all in a single folder pol/, and have been moved to a folder per component/mechanism to keep things a bit more orderly. Signed-off-by: Dimitri Staessens Signed-off-by: Sander Vrijders --- src/ipcpd/unicast/CMakeLists.txt | 23 +- src/ipcpd/unicast/addr-auth.c | 58 ++ src/ipcpd/unicast/addr-auth.h | 37 + src/ipcpd/unicast/addr-auth/flat.c | 87 ++ src/ipcpd/unicast/addr-auth/flat.h | 36 + src/ipcpd/unicast/addr-auth/ops.h | 34 + src/ipcpd/unicast/addr_auth.c | 58 -- src/ipcpd/unicast/addr_auth.h | 37 - src/ipcpd/unicast/ca.c | 8 +- src/ipcpd/unicast/ca/mb-ecn.c | 296 +++++++ src/ipcpd/unicast/ca/mb-ecn.h | 56 ++ src/ipcpd/unicast/ca/nop.c | 98 +++ src/ipcpd/unicast/ca/nop.h | 52 ++ src/ipcpd/unicast/ca/ops.h | 58 ++ src/ipcpd/unicast/main.c | 2 +- src/ipcpd/unicast/pff.c | 12 +- src/ipcpd/unicast/pff/alternate.c | 400 +++++++++ src/ipcpd/unicast/pff/alternate.h | 61 ++ src/ipcpd/unicast/pff/multipath.c | 198 +++++ src/ipcpd/unicast/pff/multipath.h | 58 ++ src/ipcpd/unicast/pff/ops.h | 63 ++ src/ipcpd/unicast/pff/pft.c | 223 +++++ src/ipcpd/unicast/pff/pft.h | 55 ++ src/ipcpd/unicast/pff/simple.c | 190 +++++ src/ipcpd/unicast/pff/simple.h | 57 ++ src/ipcpd/unicast/pff/tests/CMakeLists.txt | 34 + src/ipcpd/unicast/pff/tests/pft_test.c | 126 +++ src/ipcpd/unicast/pol-addr-auth-ops.h | 34 - src/ipcpd/unicast/pol-ca-ops.h | 58 -- src/ipcpd/unicast/pol-pff-ops.h | 63 -- src/ipcpd/unicast/pol-routing-ops.h | 38 - src/ipcpd/unicast/pol/alternate_pff.c | 400 --------- src/ipcpd/unicast/pol/alternate_pff.h | 61 -- src/ipcpd/unicast/pol/ca-mb-ecn.c | 296 ------- src/ipcpd/unicast/pol/ca-mb-ecn.h | 56 -- src/ipcpd/unicast/pol/ca-nop.c | 98 --- src/ipcpd/unicast/pol/ca-nop.h | 52 -- src/ipcpd/unicast/pol/flat.c | 87 -- src/ipcpd/unicast/pol/flat.h | 36 - src/ipcpd/unicast/pol/graph.c | 849 ------------------- src/ipcpd/unicast/pol/graph.h | 69 -- src/ipcpd/unicast/pol/link_state.c | 1055 ------------------------ src/ipcpd/unicast/pol/link_state.h | 41 - src/ipcpd/unicast/pol/multipath_pff.c | 198 ----- src/ipcpd/unicast/pol/multipath_pff.h | 58 -- src/ipcpd/unicast/pol/pft.c | 223 ----- src/ipcpd/unicast/pol/pft.h | 55 -- src/ipcpd/unicast/pol/simple_pff.c | 190 ----- src/ipcpd/unicast/pol/simple_pff.h | 57 -- src/ipcpd/unicast/pol/tests/CMakeLists.txt | 35 - src/ipcpd/unicast/pol/tests/graph_test.c | 351 -------- src/ipcpd/unicast/pol/tests/pft_test.c | 126 --- src/ipcpd/unicast/routing.c | 4 +- src/ipcpd/unicast/routing/graph.c | 849 +++++++++++++++++++ src/ipcpd/unicast/routing/graph.h | 69 ++ src/ipcpd/unicast/routing/link-state.c | 1055 ++++++++++++++++++++++++ src/ipcpd/unicast/routing/link-state.h | 41 + src/ipcpd/unicast/routing/ops.h | 38 + src/ipcpd/unicast/routing/tests/CMakeLists.txt | 34 + src/ipcpd/unicast/routing/tests/graph_test.c | 351 ++++++++ 60 files changed, 4739 insertions(+), 4705 deletions(-) create mode 100644 src/ipcpd/unicast/addr-auth.c create mode 100644 src/ipcpd/unicast/addr-auth.h create mode 100644 src/ipcpd/unicast/addr-auth/flat.c create mode 100644 src/ipcpd/unicast/addr-auth/flat.h create mode 100644 src/ipcpd/unicast/addr-auth/ops.h delete mode 100644 src/ipcpd/unicast/addr_auth.c delete mode 100644 src/ipcpd/unicast/addr_auth.h create mode 100644 src/ipcpd/unicast/ca/mb-ecn.c create mode 100644 src/ipcpd/unicast/ca/mb-ecn.h create mode 100644 src/ipcpd/unicast/ca/nop.c create mode 100644 src/ipcpd/unicast/ca/nop.h create mode 100644 src/ipcpd/unicast/ca/ops.h create mode 100644 src/ipcpd/unicast/pff/alternate.c create mode 100644 src/ipcpd/unicast/pff/alternate.h create mode 100644 src/ipcpd/unicast/pff/multipath.c create mode 100644 src/ipcpd/unicast/pff/multipath.h create mode 100644 src/ipcpd/unicast/pff/ops.h create mode 100644 src/ipcpd/unicast/pff/pft.c create mode 100644 src/ipcpd/unicast/pff/pft.h create mode 100644 src/ipcpd/unicast/pff/simple.c create mode 100644 src/ipcpd/unicast/pff/simple.h create mode 100644 src/ipcpd/unicast/pff/tests/CMakeLists.txt create mode 100644 src/ipcpd/unicast/pff/tests/pft_test.c delete mode 100644 src/ipcpd/unicast/pol-addr-auth-ops.h delete mode 100644 src/ipcpd/unicast/pol-ca-ops.h delete mode 100644 src/ipcpd/unicast/pol-pff-ops.h delete mode 100644 src/ipcpd/unicast/pol-routing-ops.h delete mode 100644 src/ipcpd/unicast/pol/alternate_pff.c delete mode 100644 src/ipcpd/unicast/pol/alternate_pff.h delete mode 100644 src/ipcpd/unicast/pol/ca-mb-ecn.c delete mode 100644 src/ipcpd/unicast/pol/ca-mb-ecn.h delete mode 100644 src/ipcpd/unicast/pol/ca-nop.c delete mode 100644 src/ipcpd/unicast/pol/ca-nop.h delete mode 100644 src/ipcpd/unicast/pol/flat.c delete mode 100644 src/ipcpd/unicast/pol/flat.h delete mode 100644 src/ipcpd/unicast/pol/graph.c delete mode 100644 src/ipcpd/unicast/pol/graph.h delete mode 100644 src/ipcpd/unicast/pol/link_state.c delete mode 100644 src/ipcpd/unicast/pol/link_state.h delete mode 100644 src/ipcpd/unicast/pol/multipath_pff.c delete mode 100644 src/ipcpd/unicast/pol/multipath_pff.h delete mode 100644 src/ipcpd/unicast/pol/pft.c delete mode 100644 src/ipcpd/unicast/pol/pft.h delete mode 100644 src/ipcpd/unicast/pol/simple_pff.c delete mode 100644 src/ipcpd/unicast/pol/simple_pff.h delete mode 100644 src/ipcpd/unicast/pol/tests/CMakeLists.txt delete mode 100644 src/ipcpd/unicast/pol/tests/graph_test.c delete mode 100644 src/ipcpd/unicast/pol/tests/pft_test.c create mode 100644 src/ipcpd/unicast/routing/graph.c create mode 100644 src/ipcpd/unicast/routing/graph.h create mode 100644 src/ipcpd/unicast/routing/link-state.c create mode 100644 src/ipcpd/unicast/routing/link-state.h create mode 100644 src/ipcpd/unicast/routing/ops.h create mode 100644 src/ipcpd/unicast/routing/tests/CMakeLists.txt create mode 100644 src/ipcpd/unicast/routing/tests/graph_test.c (limited to 'src/ipcpd') diff --git a/src/ipcpd/unicast/CMakeLists.txt b/src/ipcpd/unicast/CMakeLists.txt index 07f12540..a14f4e44 100644 --- a/src/ipcpd/unicast/CMakeLists.txt +++ b/src/ipcpd/unicast/CMakeLists.txt @@ -31,7 +31,7 @@ endif () set(SOURCE_FILES # Add source files here - addr_auth.c + addr-auth.c ca.c connmgr.c dht.c @@ -44,15 +44,15 @@ set(SOURCE_FILES routing.c psched.c # Add policies last - pol/pft.c - pol/flat.c - pol/link_state.c - pol/graph.c - pol/simple_pff.c - pol/alternate_pff.c - pol/multipath_pff.c - pol/ca-mb-ecn.c - pol/ca-nop.c + addr-auth/flat.c + ca/mb-ecn.c + ca/nop.c + pff/simple.c + pff/alternate.c + pff/multipath.c + pff/pft.c + routing/link-state.c + routing/graph.c ) add_executable(ipcpd-unicast ${SOURCE_FILES} ${IPCP_SOURCES} @@ -66,7 +66,8 @@ endif () install(TARGETS ipcpd-unicast RUNTIME DESTINATION ${CMAKE_INSTALL_SBINDIR}) -add_subdirectory(pol/tests) +add_subdirectory(pff/tests) +add_subdirectory(routing/tests) if (NOT GNU) add_subdirectory(tests) diff --git a/src/ipcpd/unicast/addr-auth.c b/src/ipcpd/unicast/addr-auth.c new file mode 100644 index 00000000..4aff9361 --- /dev/null +++ b/src/ipcpd/unicast/addr-auth.c @@ -0,0 +1,58 @@ +/* + * Ouroboros - Copyright (C) 2016 - 2021 + * + * Address authority + * + * 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 OUROBOROS_PREFIX "addr_auth" + +#include + +#include "addr-auth.h" +#include "addr-auth/ops.h" +#include "addr-auth/flat.h" + +#include + +struct addr_auth_ops * ops; + +int addr_auth_init(enum pol_addr_auth type, + const void * info) +{ + switch (type) { + case ADDR_AUTH_FLAT_RANDOM: + ops = &flat_ops; + break; + default: + log_err("Unknown address authority type."); + return -1; + } + + return ops->init(info); +} + +uint64_t addr_auth_address(void) +{ + return ops->address(); +} + +int addr_auth_fini(void) +{ + return ops->fini(); +} diff --git a/src/ipcpd/unicast/addr-auth.h b/src/ipcpd/unicast/addr-auth.h new file mode 100644 index 00000000..d26d3eb7 --- /dev/null +++ b/src/ipcpd/unicast/addr-auth.h @@ -0,0 +1,37 @@ +/* + * Ouroboros - Copyright (C) 2016 - 2021 + * + * Address authority + * + * 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_ADDR_AUTH_H +#define OUROBOROS_IPCPD_UNICAST_ADDR_AUTH_H + +#include + +#include + +int addr_auth_init(enum pol_addr_auth type, + const void * info); + +int addr_auth_fini(void); + +uint64_t addr_auth_address(void); + +#endif /* OUROBOROS_IPCPD_UNICAST_ADDR_AUTH_H */ diff --git a/src/ipcpd/unicast/addr-auth/flat.c b/src/ipcpd/unicast/addr-auth/flat.c new file mode 100644 index 00000000..af245a5d --- /dev/null +++ b/src/ipcpd/unicast/addr-auth/flat.c @@ -0,0 +1,87 @@ +/* + * Ouroboros - Copyright (C) 2016 - 2021 + * + * 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 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/addr-auth/flat.h b/src/ipcpd/unicast/addr-auth/flat.h new file mode 100644 index 00000000..96642dcc --- /dev/null +++ b/src/ipcpd/unicast/addr-auth/flat.h @@ -0,0 +1,36 @@ +/* + * Ouroboros - Copyright (C) 2016 - 2021 + * + * 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 "ops.h" + +int flat_init(const void * info); + +int flat_fini(void); + +uint64_t flat_address(void); + +extern struct addr_auth_ops flat_ops; + +#endif /* OUROBOROS_IPCPD_UNICAST_FLAT_H */ diff --git a/src/ipcpd/unicast/addr-auth/ops.h b/src/ipcpd/unicast/addr-auth/ops.h new file mode 100644 index 00000000..e1069706 --- /dev/null +++ b/src/ipcpd/unicast/addr-auth/ops.h @@ -0,0 +1,34 @@ +/* + * Ouroboros - Copyright (C) 2016 - 2021 + * + * Address authority policy ops + * + * 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_ADDR_AUTH_OPS_H +#define OUROBOROS_IPCPD_UNICAST_ADDR_AUTH_OPS_H + +struct addr_auth_ops { + int (* init)(const void * info); + + int (* fini)(void); + + uint64_t (* address)(void); +}; + +#endif /* OUROBOROS_IPCPD_UNICAST_ADDR_AUTH_OPS_H */ diff --git a/src/ipcpd/unicast/addr_auth.c b/src/ipcpd/unicast/addr_auth.c deleted file mode 100644 index e508d0cb..00000000 --- a/src/ipcpd/unicast/addr_auth.c +++ /dev/null @@ -1,58 +0,0 @@ -/* - * Ouroboros - Copyright (C) 2016 - 2021 - * - * Address authority - * - * 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 OUROBOROS_PREFIX "addr_auth" - -#include - -#include "addr_auth.h" -#include "pol-addr-auth-ops.h" -#include "pol/flat.h" - -#include - -struct pol_addr_auth_ops * ops; - -int addr_auth_init(enum pol_addr_auth type, - const void * info) -{ - switch (type) { - case ADDR_AUTH_FLAT_RANDOM: - ops = &flat_ops; - break; - default: - log_err("Unknown address authority type."); - return -1; - } - - return ops->init(info); -} - -uint64_t addr_auth_address(void) -{ - return ops->address(); -} - -int addr_auth_fini(void) -{ - return ops->fini(); -} diff --git a/src/ipcpd/unicast/addr_auth.h b/src/ipcpd/unicast/addr_auth.h deleted file mode 100644 index d26d3eb7..00000000 --- a/src/ipcpd/unicast/addr_auth.h +++ /dev/null @@ -1,37 +0,0 @@ -/* - * Ouroboros - Copyright (C) 2016 - 2021 - * - * Address authority - * - * 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_ADDR_AUTH_H -#define OUROBOROS_IPCPD_UNICAST_ADDR_AUTH_H - -#include - -#include - -int addr_auth_init(enum pol_addr_auth type, - const void * info); - -int addr_auth_fini(void); - -uint64_t addr_auth_address(void); - -#endif /* OUROBOROS_IPCPD_UNICAST_ADDR_AUTH_H */ diff --git a/src/ipcpd/unicast/ca.c b/src/ipcpd/unicast/ca.c index ddeb2849..20cdc6be 100644 --- a/src/ipcpd/unicast/ca.c +++ b/src/ipcpd/unicast/ca.c @@ -25,12 +25,12 @@ #include #include "ca.h" -#include "pol-ca-ops.h" -#include "pol/ca-mb-ecn.h" -#include "pol/ca-nop.h" +#include "ca/ops.h" +#include "ca/mb-ecn.h" +#include "ca/nop.h" struct { - struct pol_ca_ops * ops; + struct ca_ops * ops; } ca; int ca_init(enum pol_cong_avoid pol) diff --git a/src/ipcpd/unicast/ca/mb-ecn.c b/src/ipcpd/unicast/ca/mb-ecn.c new file mode 100644 index 00000000..38305a39 --- /dev/null +++ b/src/ipcpd/unicast/ca/mb-ecn.c @@ -0,0 +1,296 @@ +/* + * Ouroboros - Copyright (C) 2016 - 2021 + * + * Multi-bit ECN Congestion Avoidance + * + * 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 200809L +#endif + +#include "config.h" + +#include +#include + +#include "mb-ecn.h" + +#include +#include +#include +#include + +/* congestion avoidance constants */ +#define CA_SHFT 5 /* Average over 32 pkts */ +#define CA_WND (1 << CA_SHFT) /* 32 pkts receiver wnd */ +#define CA_UPD (1 << (CA_SHFT - 2)) /* Update snd every 8 pkt */ +#define CA_SLOT 24 /* Initial slot = 16 ms */ +#define CA_INC 1UL << 16 /* ~4MiB/s^2 additive inc */ +#define CA_IWL 1UL << 16 /* Initial limit ~4MiB/s */ +#define CA_MINPS 8 /* Mimimum pkts / slot */ +#define CA_MAXPS 64 /* Maximum pkts / slot */ +#define ECN_Q_SHFT 4 +#define ts_to_ns(ts) ((size_t) ts.tv_sec * BILLION + ts.tv_nsec) + +struct mb_ecn_ctx { + uint16_t rx_ece; /* Level of congestion (upstream) */ + size_t rx_ctr; /* Receiver side packet counter */ + + uint16_t tx_ece; /* Level of congestion (downstream) */ + size_t tx_ctr; /* Sender side packet counter */ + size_t tx_wbc; /* Window byte count */ + size_t tx_wpc; /* Window packet count */ + size_t tx_wbl; /* Window byte limit */ + bool tx_cav; /* Congestion avoidance */ + size_t tx_mul; /* Slot size multiplier */ + size_t tx_inc; /* Additive increase */ + size_t tx_slot; +}; + +struct ca_ops mb_ecn_ca_ops = { + .ctx_create = mb_ecn_ctx_create, + .ctx_destroy = mb_ecn_ctx_destroy, + .ctx_update_snd = mb_ecn_ctx_update_snd, + .ctx_update_rcv = mb_ecn_ctx_update_rcv, + .ctx_update_ece = mb_ecn_ctx_update_ece, + .wnd_wait = mb_ecn_wnd_wait, + .calc_ecn = mb_ecn_calc_ecn, + .print_stats = mb_ecn_print_stats +}; + +void * mb_ecn_ctx_create(void) +{ + struct timespec now; + struct mb_ecn_ctx * ctx; + + ctx = malloc(sizeof(*ctx)); + if (ctx == NULL) + return NULL; + + clock_gettime(PTHREAD_COND_CLOCK, &now); + + memset(ctx, 0, sizeof(*ctx)); + + ctx->tx_mul = CA_SLOT; + ctx->tx_wbl = CA_IWL; + ctx->tx_inc = CA_INC; + ctx->tx_slot = ts_to_ns(now) >> ctx->tx_mul; + + return (void *) ctx; +} + +void mb_ecn_ctx_destroy(void * ctx) +{ + free(ctx); +} + +#define _slot_after(new, old) ((int64_t) (old - new) < 0) + +ca_wnd_t mb_ecn_ctx_update_snd(void * _ctx, + size_t len) +{ + struct timespec now; + size_t slot; + ca_wnd_t wnd; + struct mb_ecn_ctx * ctx = _ctx; + + clock_gettime(PTHREAD_COND_CLOCK, &now); + + slot = ts_to_ns(now) >> ctx->tx_mul; + + ctx->tx_ctr++; + ctx->tx_wpc++; + ctx->tx_wbc += len; + + if (ctx->tx_ctr > CA_WND) + ctx->tx_ece = 0; + + if (_slot_after(slot, ctx->tx_slot)) { + bool carry = false; /* may carry over if window increases */ + + ctx->tx_slot = slot; + + if (!ctx->tx_cav) { /* Slow start */ + if (ctx->tx_wbc > ctx->tx_wbl) + ctx->tx_wbl <<= 1; + } else { + if (ctx->tx_ece) /* Mult. Decrease */ + ctx->tx_wbl -= (ctx->tx_wbl * ctx->tx_ece) + >> (CA_SHFT + 8); + else /* Add. Increase */ + ctx->tx_wbl = ctx->tx_wbc + ctx->tx_inc; + } + + /* Window scaling */ + if (ctx->tx_wpc < CA_MINPS) { + size_t fact = 0; /* factor to scale the window up */ + size_t pkts = ctx->tx_wpc; + while (pkts < CA_MINPS) { + pkts <<= 1; + fact++; + } + ctx->tx_mul += fact; + ctx->tx_slot >>= fact; + if ((ctx->tx_slot & ((1 << fact) - 1)) == 0) { + carry = true; + ctx->tx_slot += 1; + } + ctx->tx_wbl <<= fact; + ctx->tx_inc <<= fact; + } else if (ctx->tx_wpc > CA_MAXPS) { + size_t fact = 0; /* factor to scale the window down */ + size_t pkts = ctx->tx_wpc; + while (pkts > CA_MAXPS) { + pkts >>= 1; + fact++; + } + ctx->tx_mul -= fact; + ctx->tx_slot <<= fact; + ctx->tx_wbl >>= fact; + ctx->tx_inc >>= fact; + } else { + ctx->tx_slot = slot; + } + + if (!carry) { + ctx->tx_wbc = 0; + ctx->tx_wpc = 0; + } + } + + if (ctx->tx_wbc > ctx->tx_wbl) + wnd.wait = ((ctx->tx_slot + 1) << ctx->tx_mul) - ts_to_ns(now); + else + wnd.wait = 0; + + return wnd; +} + +void mb_ecn_wnd_wait(ca_wnd_t wnd) +{ + if (wnd.wait > 0) { + struct timespec s = {0, 0}; + if (wnd.wait > BILLION) /* Don't care throttling < 1s */ + s.tv_sec = 1; + else + s.tv_nsec = wnd.wait; + + nanosleep(&s, NULL); + } +} + +bool mb_ecn_ctx_update_rcv(void * _ctx, + size_t len, + uint8_t ecn, + uint16_t * ece) +{ + struct mb_ecn_ctx* ctx = _ctx; + bool update; + + (void) len; + + if ((ctx->rx_ece | ecn) == 0) + return false; + + if (ecn == 0) { /* End of congestion */ + ctx->rx_ece >>= 2; + update = ctx->rx_ece == 0; + } else { + if (ctx->rx_ece == 0) { /* Start of congestion */ + ctx->rx_ece = ecn; + ctx->rx_ctr = 0; + update = true; + } else { /* Congestion update */ + ctx->rx_ece -= ctx->rx_ece >> CA_SHFT; + ctx->rx_ece += ecn; + update = (ctx->rx_ctr++ & (CA_UPD - 1)) == true; + } + } + + *ece = ctx->rx_ece; + + return update; +} + + +void mb_ecn_ctx_update_ece(void * _ctx, + uint16_t ece) +{ + struct mb_ecn_ctx* ctx = _ctx; + + ctx->tx_ece = ece; + ctx->tx_ctr = 0; + ctx->tx_cav = true; +} + +int mb_ecn_calc_ecn(int fd, + uint8_t * ecn, + qoscube_t qc, + size_t len) +{ + size_t q; + + (void) len; + (void) qc; + + q = ipcp_flow_queued(fd); + + *ecn |= (uint8_t) (q >> ECN_Q_SHFT); + + return 0; +} + +ssize_t mb_ecn_print_stats(void * _ctx, + char * buf, + size_t len) +{ + struct mb_ecn_ctx* ctx = _ctx; + char * regime; + + if (len < 1024) + return 0; + + if (!ctx->tx_cav) + regime = "Slow start"; + else if (ctx->tx_ece) + regime = "Multiplicative dec"; + else + regime = "Additive inc"; + + sprintf(buf, + "Congestion avoidance algorithm: %20s\n" + "Upstream congestion level: %20u\n" + "Upstream packet counter: %20zu\n" + "Downstream congestion level: %20u\n" + "Downstream packet counter: %20zu\n" + "Congestion window size (ns): %20" PRIu64 "\n" + "Packets in this window: %20zu\n" + "Bytes in this window: %20zu\n" + "Max bytes in this window: %20zu\n" + "Current congestion regime: %20s\n", + "Multi-bit ECN", + ctx->tx_ece, ctx->tx_ctr, + ctx->rx_ece, ctx->rx_ctr, (uint64_t) (1ULL << ctx->tx_mul), + ctx->tx_wpc, ctx->tx_wbc, ctx->tx_wbl, + regime); + + return strlen(buf); +} diff --git a/src/ipcpd/unicast/ca/mb-ecn.h b/src/ipcpd/unicast/ca/mb-ecn.h new file mode 100644 index 00000000..53f23179 --- /dev/null +++ b/src/ipcpd/unicast/ca/mb-ecn.h @@ -0,0 +1,56 @@ +/* + * Ouroboros - Copyright (C) 2016 - 2021 + * + * Multi-bit ECN Congestion Avoidance + * + * 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_CA_MB_ECN_H +#define OUROBOROS_IPCPD_UNICAST_CA_MB_ECN_H + +#include "ops.h" + +void * mb_ecn_ctx_create(void); + +void mb_ecn_ctx_destroy(void * ctx); + +ca_wnd_t mb_ecn_ctx_update_snd(void * ctx, + size_t len); + +bool mb_ecn_ctx_update_rcv(void * ctx, + size_t len, + uint8_t ecn, + uint16_t * ece); + +void mb_ecn_ctx_update_ece(void * ctx, + uint16_t ece); + +void mb_ecn_wnd_wait(ca_wnd_t wnd); + +int mb_ecn_calc_ecn(int fd, + uint8_t * ecn, + qoscube_t qc, + size_t len); + +ssize_t mb_ecn_print_stats(void * ctx, + char * buf, + size_t len); + +extern struct ca_ops mb_ecn_ca_ops; + +#endif /* OUROBOROS_IPCPD_UNICAST_CA_MB_ECN_H */ diff --git a/src/ipcpd/unicast/ca/nop.c b/src/ipcpd/unicast/ca/nop.c new file mode 100644 index 00000000..5be826d4 --- /dev/null +++ b/src/ipcpd/unicast/ca/nop.c @@ -0,0 +1,98 @@ +/* + * Ouroboros - Copyright (C) 2016 - 2021 + * + * Dummy Congestion Avoidance + * + * 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/. + */ + +#include "nop.h" + +#include + +struct ca_ops nop_ca_ops = { + .ctx_create = nop_ctx_create, + .ctx_destroy = nop_ctx_destroy, + .ctx_update_snd = nop_ctx_update_snd, + .ctx_update_rcv = nop_ctx_update_rcv, + .ctx_update_ece = nop_ctx_update_ece, + .wnd_wait = nop_wnd_wait, + .calc_ecn = nop_calc_ecn, + .print_stats = NULL +}; + +void * nop_ctx_create(void) +{ + return (void *) 1; +} + +void nop_ctx_destroy(void * ctx) +{ + (void) ctx; +} + +ca_wnd_t nop_ctx_update_snd(void * ctx, + size_t len) +{ + ca_wnd_t wnd; + + (void) ctx; + (void) len; + + memset(&wnd, 0, sizeof(wnd)); + + return wnd; +} + +void nop_wnd_wait(ca_wnd_t wnd) +{ + (void) wnd; +} + +bool nop_ctx_update_rcv(void * ctx, + size_t len, + uint8_t ecn, + uint16_t * ece) +{ + (void) ctx; + (void) len; + (void) ecn; + (void) ece; + + return false; +} + +void nop_ctx_update_ece(void * ctx, + uint16_t ece) +{ + (void) ctx; + (void) ece; +} + + +int nop_calc_ecn(int fd, + uint8_t * ecn, + qoscube_t qc, + size_t len) +{ + (void) fd; + (void) len; + (void) ecn; + (void) qc; + + return 0; +} diff --git a/src/ipcpd/unicast/ca/nop.h b/src/ipcpd/unicast/ca/nop.h new file mode 100644 index 00000000..25996552 --- /dev/null +++ b/src/ipcpd/unicast/ca/nop.h @@ -0,0 +1,52 @@ +/* + * Ouroboros - Copyright (C) 2016 - 2021 + * + * Dummy Congestion Avoidance + * + * 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_CA_NOP_H +#define OUROBOROS_IPCPD_UNICAST_CA_NOP_H + +#include "ops.h" + +void * nop_ctx_create(void); + +void nop_ctx_destroy(void * ctx); + +ca_wnd_t nop_ctx_update_snd(void * ctx, + size_t len); + +bool nop_ctx_update_rcv(void * ctx, + size_t len, + uint8_t ecn, + uint16_t * ece); + +void nop_ctx_update_ece(void * ctx, + uint16_t ece); + +void nop_wnd_wait(ca_wnd_t wnd); + +int nop_calc_ecn(int fd, + uint8_t * ecn, + qoscube_t qc, + size_t len); + +extern struct ca_ops nop_ca_ops; + +#endif /* OUROBOROS_IPCPD_UNICAST_CA_NOP_H */ diff --git a/src/ipcpd/unicast/ca/ops.h b/src/ipcpd/unicast/ca/ops.h new file mode 100644 index 00000000..ee0f028b --- /dev/null +++ b/src/ipcpd/unicast/ca/ops.h @@ -0,0 +1,58 @@ +/* + * Ouroboros - Copyright (C) 2016 - 2021 + * + * Congestion avoidance policy ops + * + * 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_CA_OPS_H +#define OUROBOROS_IPCPD_UNICAST_CA_OPS_H + +#include "ca.h" + +struct ca_ops { + void * (* ctx_create)(void); + + void (* ctx_destroy)(void * ctx); + + ca_wnd_t (* ctx_update_snd)(void * ctx, + size_t len); + + bool (* ctx_update_rcv)(void * ctx, + size_t len, + uint8_t ecn, + uint16_t * ece); + + void (* ctx_update_ece)(void * ctx, + uint16_t ece); + + void (* wnd_wait)(ca_wnd_t wnd); + + int (* calc_ecn)(int fd, + uint8_t * ecn, + qoscube_t qc, + size_t len); + + /* Optional, can be NULL */ + ssize_t (* print_stats)(void * ctx, + char * buf, + size_t len); + +}; + +#endif /* OUROBOROS_IPCPD_UNICAST_CA_OPS_H */ diff --git a/src/ipcpd/unicast/main.c b/src/ipcpd/unicast/main.c index 018dd1c6..873c6ce3 100644 --- a/src/ipcpd/unicast/main.c +++ b/src/ipcpd/unicast/main.c @@ -41,7 +41,7 @@ #include "common/connmgr.h" #include "common/enroll.h" -#include "addr_auth.h" +#include "addr-auth.h" #include "ca.h" #include "dir.h" #include "dt.h" diff --git a/src/ipcpd/unicast/pff.c b/src/ipcpd/unicast/pff.c index 03682184..192552b9 100644 --- a/src/ipcpd/unicast/pff.c +++ b/src/ipcpd/unicast/pff.c @@ -26,14 +26,14 @@ #include #include "pff.h" -#include "pol-pff-ops.h" -#include "pol/alternate_pff.h" -#include "pol/multipath_pff.h" -#include "pol/simple_pff.h" +#include "pff/ops.h" +#include "pff/alternate.h" +#include "pff/multipath.h" +#include "pff/simple.h" struct pff { - struct pol_pff_ops * ops; - struct pff_i * pff_i; + struct pff_ops * ops; + struct pff_i * pff_i; }; struct pff * pff_create(enum pol_pff pol) diff --git a/src/ipcpd/unicast/pff/alternate.c b/src/ipcpd/unicast/pff/alternate.c new file mode 100644 index 00000000..9f0a6279 --- /dev/null +++ b/src/ipcpd/unicast/pff/alternate.c @@ -0,0 +1,400 @@ +/* + * Ouroboros - Copyright (C) 2016 - 2021 + * + * 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 "pft.h" +#include "alternate.h" + +#include +#include +#include + +struct nhop { + struct list_head next; + int fd; +}; + +struct addr { + struct list_head next; + uint64_t addr; +}; + +struct pff_i { + struct pft * pft; + + struct list_head addrs; + + struct list_head nhops_down; + + pthread_rwlock_t lock; +}; + +struct 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 * p; + struct list_head * h; + + list_for_each_safe(p, h, &(pff_i->addrs)) { + struct addr * e = list_entry(p, 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 * p; + struct list_head * h; + + list_for_each_safe(p, h, &(pff_i->addrs)) { + struct addr * e = list_entry(p, struct addr, next); + list_del(&e->next); + free(e); + } +} + +static void del_nhops_down(struct pff_i * pff_i) +{ + struct list_head * p; + struct list_head * h; + + list_for_each_safe(p, h, &(pff_i->nhops_down)) { + struct nhop * e = list_entry(p, struct nhop, next); + list_del(&e->next); + free(e); + } +} + +static int del_nhop_down(struct pff_i * pff_i, + int fd) +{ + struct list_head * p; + struct list_head * h; + + list_for_each_safe(p, h, &(pff_i->nhops_down)) { + struct nhop * e = list_entry(p, 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_pft(struct pff_i * pff_i, + uint64_t addr, + int * fd, + size_t len) +{ + int * fds; + + assert(pff_i); + assert(len > 0); + + fds = malloc(sizeof(*fds) * (len + 1)); + if (fds == NULL) + goto fail_malloc; + + memcpy(fds, fd, len * sizeof(*fds)); + /* Put primary hop again at the end */ + fds[len] = fds[0]; + + if (pft_insert(pff_i->pft, addr, fds, len)) + goto fail_insert; + + return 0; + + fail_insert: + free(fds); + 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->pft = pft_create(PFT_SIZE, false); + if (tmp->pft == NULL) + goto fail_pft; + + list_head_init(&tmp->nhops_down); + list_head_init(&tmp->addrs); + + return tmp; + + fail_pft: + 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); + + pft_destroy(pff_i->pft); + 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_pft(pff_i, addr, fd, len)) + return -1; + + if (add_addr(pff_i, addr)) { + pft_delete(pff_i->pft, 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 (pft_delete(pff_i->pft, addr)) + return -1; + + if (add_to_pft(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 (pft_delete(pff_i->pft, addr)) + return -1; + + return 0; +} + +void alternate_pff_flush(struct pff_i * pff_i) +{ + assert(pff_i); + + pft_flush(pff_i->pft); + + del_nhops_down(pff_i); + + del_addrs(pff_i); +} + +int alternate_pff_nhop(struct pff_i * pff_i, + uint64_t addr) +{ + int fd; + size_t len; + int * fds; + + assert(pff_i); + + pthread_rwlock_rdlock(&pff_i->lock); + + if (pft_lookup(pff_i->pft, addr, &fds, &len)) { + pthread_rwlock_unlock(&pff_i->lock); + return -1; + } + + fd = *fds; + + 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 * p; + size_t len; + 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(p, &pff_i->addrs) { + struct addr * e = list_entry(p, struct addr, next); + if (pft_lookup(pff_i->pft, e->addr, &fds, &len)) { + pthread_rwlock_unlock(&pff_i->lock); + return -1; + } + + 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/pff/alternate.h b/src/ipcpd/unicast/pff/alternate.h new file mode 100644 index 00000000..294f48d9 --- /dev/null +++ b/src/ipcpd/unicast/pff/alternate.h @@ -0,0 +1,61 @@ +/* + * Ouroboros - Copyright (C) 2016 - 2021 + * + * 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 "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); + +extern struct pff_ops alternate_pff_ops; + +#endif /* OUROBOROS_IPCPD_UNICAST_ALTERNATE_PFF_H */ diff --git a/src/ipcpd/unicast/pff/multipath.c b/src/ipcpd/unicast/pff/multipath.c new file mode 100644 index 00000000..43135d27 --- /dev/null +++ b/src/ipcpd/unicast/pff/multipath.c @@ -0,0 +1,198 @@ +/* + * Ouroboros - Copyright (C) 2016 - 2021 + * + * Policy for PFF supporting multipath routing + * + * Dimitri Staessens + * Sander Vrijders + * Nick Aerts + * + * 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 "pft.h" +#include "multipath.h" + +#include +#include +#include + +struct pff_i { + struct pft * pft; + pthread_rwlock_t lock; +}; + +struct pff_ops multipath_pff_ops = { + .create = multipath_pff_create, + .destroy = multipath_pff_destroy, + .lock = multipath_pff_lock, + .unlock = multipath_pff_unlock, + .add = multipath_pff_add, + .update = multipath_pff_update, + .del = multipath_pff_del, + .flush = multipath_pff_flush, + .nhop = multipath_pff_nhop, + .flow_state_change = NULL +}; + +struct pff_i * multipath_pff_create(void) +{ + struct pff_i * tmp; + + tmp = malloc(sizeof(*tmp)); + if (tmp == NULL) + return NULL; + + if (pthread_rwlock_init(&tmp->lock, NULL)) { + free(tmp); + return NULL; + } + + tmp->pft = pft_create(PFT_SIZE, false); + if (tmp->pft == NULL) { + pthread_rwlock_destroy(&tmp->lock); + free(tmp); + return NULL; + } + + return tmp; +} + +void multipath_pff_destroy(struct pff_i * pff_i) +{ + assert(pff_i); + + pft_destroy(pff_i->pft); + + pthread_rwlock_destroy(&pff_i->lock); + free(pff_i); +} + +void multipath_pff_lock(struct pff_i * pff_i) +{ + pthread_rwlock_wrlock(&pff_i->lock); +} + +void multipath_pff_unlock(struct pff_i * pff_i) +{ + pthread_rwlock_unlock(&pff_i->lock); +} + +int multipath_pff_add(struct pff_i * pff_i, + uint64_t addr, + int * fds, + size_t len) +{ + int * tmp; + + assert(pff_i); + assert(fds); + assert(len > 0); + + tmp = malloc(len * sizeof(*tmp)); + if (tmp == NULL) + return -ENOMEM; + + memcpy(tmp,fds, len * sizeof(*tmp)); + + if (pft_insert(pff_i->pft, addr, tmp, len)) { + free(tmp); + return -1; + } + + return 0; +} + +int multipath_pff_update(struct pff_i * pff_i, + uint64_t addr, + int * fds, + size_t len) +{ + int * tmp; + + assert(pff_i); + assert(fds); + assert(len > 0); + + tmp = malloc(sizeof(*tmp)); + if (tmp == NULL) + return -ENOMEM; + + memcpy(tmp,fds, len * sizeof(*tmp)); + + if (pft_delete(pff_i->pft, addr)) { + free(tmp); + return -1; + } + + if (pft_insert(pff_i->pft, addr, tmp, 1)) { + free(tmp); + return -1; + } + + return 0; +} + +int multipath_pff_del(struct pff_i * pff_i, + uint64_t addr) +{ + assert(pff_i); + + if (pft_delete(pff_i->pft, addr)) + return -1; + + return 0; +} + +void multipath_pff_flush(struct pff_i * pff_i) +{ + assert(pff_i); + + pft_flush(pff_i->pft); +} + +int multipath_pff_nhop(struct pff_i * pff_i, + uint64_t addr) +{ + int fd; + int * fds; + size_t len; + + assert(pff_i); + + pthread_rwlock_rdlock(&pff_i->lock); + + if (pft_lookup(pff_i->pft, addr, &fds, &len)) { + pthread_rwlock_unlock(&pff_i->lock); + return -1; + } + + fd = *fds; + + assert(len > 0); + + /* Rotate fds left. */ + memcpy(fds, fds + 1, (len - 1) * sizeof(*fds)); + fds[len - 1] = fd; + + pthread_rwlock_unlock(&pff_i->lock); + + return fd; +} diff --git a/src/ipcpd/unicast/pff/multipath.h b/src/ipcpd/unicast/pff/multipath.h new file mode 100644 index 00000000..4a5bcefb --- /dev/null +++ b/src/ipcpd/unicast/pff/multipath.h @@ -0,0 +1,58 @@ +/* + * Ouroboros - Copyright (C) 2016 - 2021 + * + * Policy for PFF supporting multipath routing + * + * Dimitri Staessens + * Sander Vrijders + * Nick Aerts + * + * This program is free software; you can redistribute it and/or modify + * it under the terms of the GNU General Public License version 2 as + * published by the Free Software Foundation. + * + * This program is distributed in the hope that it will be useful, + * but WITHOUT ANY WARRANTY; without even the implied warranty of + * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the + * GNU General Public License for more details. + * + * You should have received a copy of the GNU General Public License + * along with this program; if not, write to the Free Software + * Foundation, Inc., http://www.fsf.org/about/contact/. + */ + +#ifndef OUROBOROS_IPCPD_UNICAST_MULTIPATH_PFF_H +#define OUROBOROS_IPCPD_UNICAST_MULTIPATH_PFF_H + +#include "ops.h" + +struct pff_i * multipath_pff_create(void); + +void multipath_pff_destroy(struct pff_i * pff_i); + +void multipath_pff_lock(struct pff_i * pff_i); + +void multipath_pff_unlock(struct pff_i * pff_i); + +int multipath_pff_add(struct pff_i * pff_i, + uint64_t addr, + int * fds, + size_t len); + +int multipath_pff_update(struct pff_i * pff_i, + uint64_t addr, + int * fds, + size_t len); + +int multipath_pff_del(struct pff_i * pff_i, + uint64_t addr); + +void multipath_pff_flush(struct pff_i * pff_i); + +/* Returns fd towards next hop */ +int multipath_pff_nhop(struct pff_i * pff_i, + uint64_t addr); + +extern struct pff_ops multipath_pff_ops; + +#endif /* OUROBOROS_IPCPD_UNICAST_MULTIPATH_PFF_H */ diff --git a/src/ipcpd/unicast/pff/ops.h b/src/ipcpd/unicast/pff/ops.h new file mode 100644 index 00000000..a46f3da8 --- /dev/null +++ b/src/ipcpd/unicast/pff/ops.h @@ -0,0 +1,63 @@ +/* + * Ouroboros - Copyright (C) 2016 - 2021 + * + * Pff policy ops + * + * 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_PFF_OPS_H +#define OUROBOROS_IPCPD_UNICAST_PFF_OPS_H + +#include + +struct pff_i; + +struct pff_ops { + struct pff_i * (* create)(void); + + void (* destroy)(struct pff_i * pff_i); + + void (* lock)(struct pff_i * pff_i); + + void (* unlock)(struct pff_i * pff_i); + + int (* add)(struct pff_i * pff_i, + uint64_t addr, + int * fd, + size_t len); + + int (* update)(struct pff_i * pff_i, + uint64_t addr, + int * fd, + size_t len); + + int (* del)(struct pff_i * pff_i, + uint64_t addr); + + void (* flush)(struct pff_i * pff_i); + + int (* nhop)(struct pff_i * pff_i, + uint64_t addr); + + /* Optional operation. */ + int (* flow_state_change)(struct pff_i * pff_i, + int fd, + bool up); +}; + +#endif /* OUROBOROS_IPCPD_UNICAST_PFF_OPS_H */ diff --git a/src/ipcpd/unicast/pff/pft.c b/src/ipcpd/unicast/pff/pft.c new file mode 100644 index 00000000..e42b4a98 --- /dev/null +++ b/src/ipcpd/unicast/pff/pft.c @@ -0,0 +1,223 @@ +/* + * Ouroboros - Copyright (C) 2016 - 2021 + * + * Packet forwarding table (PFT) with chaining on collisions + * + * 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 +#endif + +#include +#include +#include + +#include "pft.h" + +#include +#include + +/* store output fds for dst addr */ +struct pft_entry { + struct list_head next; + uint64_t dst; + int * fds; + size_t len; +}; + +struct pft { + struct list_head * buckets; + bool hash_key; + uint64_t buckets_size; +}; + +struct pft * pft_create(uint64_t buckets, + bool hash_key) +{ + struct pft * tmp; + unsigned int i; + + if (buckets == 0) + return NULL; + + buckets--; + buckets |= buckets >> 1; + buckets |= buckets >> 2; + buckets |= buckets >> 4; + buckets |= buckets >> 8; + buckets |= buckets >> 16; + buckets |= buckets >> 32; + buckets++; + + tmp = malloc(sizeof(*tmp)); + if (tmp == NULL) + return NULL; + + tmp->hash_key = hash_key; + tmp->buckets_size = buckets; + + tmp->buckets = malloc(buckets * sizeof(*tmp->buckets)); + if (tmp->buckets == NULL) { + free(tmp); + return NULL; + } + + for (i = 0; i < buckets; i++) + list_head_init(&(tmp->buckets[i])); + + return tmp; +} + +void pft_destroy(struct pft * pft) +{ + assert(pft); + assert(pft->buckets); + + pft_flush(pft); + free(pft->buckets); + free(pft); +} + +void pft_flush(struct pft * pft) +{ + unsigned int i; + struct list_head * p; + struct list_head * h; + struct pft_entry * entry; + + assert(pft); + + for (i = 0; i < pft->buckets_size; i++) { + list_for_each_safe(p, h, &(pft->buckets[i])) { + entry = list_entry(p, struct pft_entry, next); + list_del(&entry->next); + free(entry->fds); + free(entry); + } + } +} + +static uint64_t hash(uint64_t key) +{ + void * res; + uint64_t ret; + uint8_t keys[4]; + + memcpy(keys, &key, 4); + + mem_hash(HASH_MD5, &res, keys, 4); + + ret = (* (uint64_t *) res); + + free(res); + + return ret; +} + +static uint64_t calc_key(struct pft * pft, + uint64_t dst) +{ + if (pft->hash_key) + dst = hash(dst); + + return (dst & (pft->buckets_size - 1)); +} + +int pft_insert(struct pft * pft, + uint64_t dst, + int * fds, + size_t len) +{ + struct pft_entry * entry; + uint64_t lookup_key; + struct list_head * p; + + assert(pft); + assert(len > 0); + + lookup_key = calc_key(pft, dst); + + list_for_each(p, &(pft->buckets[lookup_key])) { + entry = list_entry(p, struct pft_entry, next); + if (entry->dst == dst) + return -EPERM; + } + + entry = malloc(sizeof(*entry)); + if (entry == NULL) + return -ENOMEM; + + entry->dst = dst; + entry->fds = fds; + entry->len = len; + + list_add(&entry->next, &(pft->buckets[lookup_key])); + + return 0; +} + +int pft_lookup(struct pft * pft, + uint64_t dst, + int ** fds, + size_t * len) +{ + struct pft_entry * entry; + struct list_head * p; + uint64_t lookup_key; + + assert(pft); + + lookup_key = calc_key(pft, dst); + + list_for_each(p, &(pft->buckets[lookup_key])) { + entry = list_entry(p, struct pft_entry, next); + if (entry->dst == dst) { + *fds = entry->fds; + *len = entry->len; + return 0; + } + } + + return -1; +} + +int pft_delete(struct pft * pft, + uint64_t dst) +{ + struct pft_entry * entry; + uint64_t lookup_key; + struct list_head * p; + struct list_head * h; + + assert(pft); + + lookup_key = calc_key(pft, dst); + + list_for_each_safe(p, h, &(pft->buckets[lookup_key])) { + entry = list_entry(p, struct pft_entry, next); + if (entry->dst == dst) { + list_del(&entry->next); + free(entry->fds); + free(entry); + return 0; + } + } + + return -1; +} diff --git a/src/ipcpd/unicast/pff/pft.h b/src/ipcpd/unicast/pff/pft.h new file mode 100644 index 00000000..011ad414 --- /dev/null +++ b/src/ipcpd/unicast/pff/pft.h @@ -0,0 +1,55 @@ +/* + * Ouroboros - Copyright (C) 2016 - 2021 + * + * Packet forwarding table (PFT) with chaining on collisions + * + * 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_PFT_H +#define OUROBOROS_PFT_H + +#include +#include +#include + +struct pft; + +/* Buckets is rounded up to the nearest power of 2 */ +struct pft * pft_create(uint64_t buckets, + bool hash_key); + +void pft_destroy(struct pft * table); + +void pft_flush(struct pft * table); + +/* Passes ownership of the block of memory */ +int pft_insert(struct pft * pft, + uint64_t dst, + int * fds, + size_t len); + +/* The block of memory returned is no copy */ +int pft_lookup(struct pft * pft, + uint64_t dst, + int ** fds, + size_t * len); + +int pft_delete(struct pft * pft, + uint64_t dst); + +#endif /* OUROBOROS_PFT_H */ diff --git a/src/ipcpd/unicast/pff/simple.c b/src/ipcpd/unicast/pff/simple.c new file mode 100644 index 00000000..a007bcec --- /dev/null +++ b/src/ipcpd/unicast/pff/simple.c @@ -0,0 +1,190 @@ +/* + * Ouroboros - Copyright (C) 2016 - 2021 + * + * 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 "pft.h" +#include "simple.h" + +#include +#include + +struct pff_i { + struct pft * pft; + pthread_rwlock_t lock; +}; + +struct 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->pft = pft_create(PFT_SIZE, false); + if (tmp->pft == NULL) { + pthread_rwlock_destroy(&tmp->lock); + free(tmp); + return NULL; + } + + return tmp; +} + +void simple_pff_destroy(struct pff_i * pff_i) +{ + assert(pff_i); + + pft_destroy(pff_i->pft); + + pthread_rwlock_destroy(&pff_i->lock); + free(pff_i); +} + +void 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 * fds; + + assert(pff_i); + assert(fd); + assert(len > 0); + + (void) len; + + fds = malloc(sizeof(*fds)); + if (fds == NULL) + return -ENOMEM; + + *fds = *fd; + + if (pft_insert(pff_i->pft, addr, fds, 1)) { + free(fds); + return -1; + } + + return 0; +} + +int simple_pff_update(struct pff_i * pff_i, + uint64_t addr, + int * fd, + size_t len) +{ + int * fds; + + assert(pff_i); + assert(fd); + assert(len > 0); + + (void) len; + + fds = malloc(sizeof(*fds)); + if (fds == NULL) + return -ENOMEM; + + *fds = *fd; + + if (pft_delete(pff_i->pft, addr)) { + free(fds); + return -1; + } + + if (pft_insert(pff_i->pft, addr, fds, 1)) { + free(fds); + return -1; + } + + return 0; +} + +int simple_pff_del(struct pff_i * pff_i, + uint64_t addr) +{ + assert(pff_i); + + if (pft_delete(pff_i->pft, addr)) + return -1; + + return 0; +} + +void simple_pff_flush(struct pff_i * pff_i) +{ + assert(pff_i); + + pft_flush(pff_i->pft); +} + +int simple_pff_nhop(struct pff_i * pff_i, + uint64_t addr) +{ + int * fds; + size_t len; + int fd = -1; + + assert(pff_i); + + pthread_rwlock_rdlock(&pff_i->lock); + + if (pft_lookup(pff_i->pft, addr, &fds, &len) == 0) + fd = *fds; + + pthread_rwlock_unlock(&pff_i->lock); + + return fd; +} diff --git a/src/ipcpd/unicast/pff/simple.h b/src/ipcpd/unicast/pff/simple.h new file mode 100644 index 00000000..e9083cf5 --- /dev/null +++ b/src/ipcpd/unicast/pff/simple.h @@ -0,0 +1,57 @@ +/* + * Ouroboros - Copyright (C) 2016 - 2021 + * + * 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 "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); + +extern struct pff_ops simple_pff_ops; + +#endif /* OUROBOROS_IPCPD_UNICAST_SIMPLE_PFF_H */ diff --git a/src/ipcpd/unicast/pff/tests/CMakeLists.txt b/src/ipcpd/unicast/pff/tests/CMakeLists.txt new file mode 100644 index 00000000..e7082372 --- /dev/null +++ b/src/ipcpd/unicast/pff/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 + pft_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/pff/tests/pft_test.c b/src/ipcpd/unicast/pff/tests/pft_test.c new file mode 100644 index 00000000..c48267eb --- /dev/null +++ b/src/ipcpd/unicast/pff/tests/pft_test.c @@ -0,0 +1,126 @@ +/* + * Ouroboros - Copyright (C) 2016 - 2021 + * + * Test of the hash table + * + * 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/. + */ + +#include "pft.c" + +#include + +#define TBL_SIZE 256 +#define INT_TEST 4 + +int pft_test(int argc, + char ** argv) +{ + struct pft * pft; + int i; + int * j; + size_t len; + + (void) argc; + (void) argv; + + pft = pft_create(TBL_SIZE, true); + if (pft == NULL) { + printf("Failed to create.\n"); + return -1; + } + + pft_destroy(pft); + + pft = pft_create(TBL_SIZE, false); + if (pft == NULL) { + printf("Failed to create.\n"); + return -1; + } + + for (i = 0; i < TBL_SIZE + INT_TEST + 2; i++) { + j = malloc(sizeof(*j)); + if (j == NULL) { + printf("Failed to malloc.\n"); + pft_destroy(pft); + return -1; + } + *j = i; + + if (pft_insert(pft, i, j, 1)) { + printf("Failed to insert.\n"); + pft_destroy(pft); + free(j); + return -1; + } + } + + if (pft_lookup(pft, INT_TEST, &j, &len)) { + printf("Failed to lookup.\n"); + pft_destroy(pft); + return -1; + } + + if (*j != INT_TEST) { + printf("Lookup returned wrong value (%d != %d).\n", + INT_TEST, *j); + pft_destroy(pft); + return -1; + } + + if (pft_lookup(pft, TBL_SIZE + INT_TEST, &j, &len)) { + printf("Failed to lookup.\n"); + pft_destroy(pft); + return -1; + } + + if (*j != TBL_SIZE + INT_TEST) { + printf("Lookup returned wrong value (%d != %d).\n", + INT_TEST, *j); + pft_destroy(pft); + return -1; + } + + if (pft_delete(pft, INT_TEST)) { + printf("Failed to delete.\n"); + pft_destroy(pft); + return -1; + } + + if (pft_lookup(pft, INT_TEST, &j, &len) == 0) { + printf("Failed to delete properly.\n"); + pft_destroy(pft); + return -1; + } + + if (pft_lookup(pft, TBL_SIZE + INT_TEST, &j, &len)) { + printf("Failed to lookup after deletion.\n"); + pft_destroy(pft); + return -1; + } + + if (*j != TBL_SIZE + INT_TEST) { + printf("Lookup returned wrong value (%d != %d).\n", + INT_TEST, *j); + pft_destroy(pft); + return -1; + } + + pft_destroy(pft); + + return 0; +} diff --git a/src/ipcpd/unicast/pol-addr-auth-ops.h b/src/ipcpd/unicast/pol-addr-auth-ops.h deleted file mode 100644 index 395a5675..00000000 --- a/src/ipcpd/unicast/pol-addr-auth-ops.h +++ /dev/null @@ -1,34 +0,0 @@ -/* - * Ouroboros - Copyright (C) 2016 - 2021 - * - * Address authority policy ops - * - * 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_ADDR_AUTH_OPS_H -#define OUROBOROS_IPCPD_UNICAST_POL_ADDR_AUTH_OPS_H - -struct pol_addr_auth_ops { - int (* init)(const void * info); - - int (* fini)(void); - - uint64_t (* address)(void); -}; - -#endif /* OUROBOROS_IPCPD_UNICAST_POL_ADDR_AUTH_OPS_H */ diff --git a/src/ipcpd/unicast/pol-ca-ops.h b/src/ipcpd/unicast/pol-ca-ops.h deleted file mode 100644 index 88f6cf61..00000000 --- a/src/ipcpd/unicast/pol-ca-ops.h +++ /dev/null @@ -1,58 +0,0 @@ -/* - * Ouroboros - Copyright (C) 2016 - 2021 - * - * Congestion avoidance policy ops - * - * 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_CA_OPS_H -#define OUROBOROS_IPCPD_UNICAST_POL_CA_OPS_H - -#include "ca.h" - -struct pol_ca_ops { - void * (* ctx_create)(void); - - void (* ctx_destroy)(void * ctx); - - ca_wnd_t (* ctx_update_snd)(void * ctx, - size_t len); - - bool (* ctx_update_rcv)(void * ctx, - size_t len, - uint8_t ecn, - uint16_t * ece); - - void (* ctx_update_ece)(void * ctx, - uint16_t ece); - - void (* wnd_wait)(ca_wnd_t wnd); - - int (* calc_ecn)(int fd, - uint8_t * ecn, - qoscube_t qc, - size_t len); - - /* Optional, can be NULL */ - ssize_t (* print_stats)(void * ctx, - char * buf, - size_t len); - -}; - -#endif /* OUROBOROS_IPCPD_UNICAST_POL_CA_OPS_H */ diff --git a/src/ipcpd/unicast/pol-pff-ops.h b/src/ipcpd/unicast/pol-pff-ops.h deleted file mode 100644 index 85615a1f..00000000 --- a/src/ipcpd/unicast/pol-pff-ops.h +++ /dev/null @@ -1,63 +0,0 @@ -/* - * Ouroboros - Copyright (C) 2016 - 2021 - * - * Pff policy ops - * - * 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_PFF_OPS_H -#define OUROBOROS_IPCPD_UNICAST_POL_PFF_OPS_H - -#include - -struct pff_i; - -struct pol_pff_ops { - struct pff_i * (* create)(void); - - void (* destroy)(struct pff_i * pff_i); - - void (* lock)(struct pff_i * pff_i); - - void (* unlock)(struct pff_i * pff_i); - - int (* add)(struct pff_i * pff_i, - uint64_t addr, - int * fd, - size_t len); - - int (* update)(struct pff_i * pff_i, - uint64_t addr, - int * fd, - size_t len); - - int (* del)(struct pff_i * pff_i, - uint64_t addr); - - void (* flush)(struct pff_i * pff_i); - - int (* nhop)(struct pff_i * pff_i, - uint64_t addr); - - /* Optional operation. */ - int (* flow_state_change)(struct pff_i * pff_i, - int fd, - bool up); -}; - -#endif /* OUROBOROS_IPCPD_UNICAST_POL_PFF_OPS_H */ diff --git a/src/ipcpd/unicast/pol-routing-ops.h b/src/ipcpd/unicast/pol-routing-ops.h deleted file mode 100644 index cea88582..00000000 --- a/src/ipcpd/unicast/pol-routing-ops.h +++ /dev/null @@ -1,38 +0,0 @@ -/* - * Ouroboros - Copyright (C) 2016 - 2021 - * - * Routing policy ops - * - * 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_ROUTING_OPS_H -#define OUROBOROS_IPCPD_UNICAST_POL_ROUTING_OPS_H - -#include "pff.h" - -struct pol_routing_ops { - int (* init)(enum pol_routing pr); - - void (* fini)(void); - - struct routing_i * (* routing_i_create)(struct pff * pff); - - void (* routing_i_destroy)(struct routing_i * instance); -}; - -#endif /* OUROBOROS_IPCPD_UNICAST_POL_ROUTING_OPS_H */ diff --git a/src/ipcpd/unicast/pol/alternate_pff.c b/src/ipcpd/unicast/pol/alternate_pff.c deleted file mode 100644 index 18d3dfed..00000000 --- a/src/ipcpd/unicast/pol/alternate_pff.c +++ /dev/null @@ -1,400 +0,0 @@ -/* - * Ouroboros - Copyright (C) 2016 - 2021 - * - * 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 "pft.h" -#include "alternate_pff.h" - -#include -#include -#include - -struct nhop { - struct list_head next; - int fd; -}; - -struct addr { - struct list_head next; - uint64_t addr; -}; - -struct pff_i { - struct pft * pft; - - 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 * p; - struct list_head * h; - - list_for_each_safe(p, h, &(pff_i->addrs)) { - struct addr * e = list_entry(p, 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 * p; - struct list_head * h; - - list_for_each_safe(p, h, &(pff_i->addrs)) { - struct addr * e = list_entry(p, struct addr, next); - list_del(&e->next); - free(e); - } -} - -static void del_nhops_down(struct pff_i * pff_i) -{ - struct list_head * p; - struct list_head * h; - - list_for_each_safe(p, h, &(pff_i->nhops_down)) { - struct nhop * e = list_entry(p, struct nhop, next); - list_del(&e->next); - free(e); - } -} - -static int del_nhop_down(struct pff_i * pff_i, - int fd) -{ - struct list_head * p; - struct list_head * h; - - list_for_each_safe(p, h, &(pff_i->nhops_down)) { - struct nhop * e = list_entry(p, 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_pft(struct pff_i * pff_i, - uint64_t addr, - int * fd, - size_t len) -{ - int * fds; - - assert(pff_i); - assert(len > 0); - - fds = malloc(sizeof(*fds) * (len + 1)); - if (fds == NULL) - goto fail_malloc; - - memcpy(fds, fd, len * sizeof(*fds)); - /* Put primary hop again at the end */ - fds[len] = fds[0]; - - if (pft_insert(pff_i->pft, addr, fds, len)) - goto fail_insert; - - return 0; - - fail_insert: - free(fds); - 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->pft = pft_create(PFT_SIZE, false); - if (tmp->pft == NULL) - goto fail_pft; - - list_head_init(&tmp->nhops_down); - list_head_init(&tmp->addrs); - - return tmp; - - fail_pft: - 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); - - pft_destroy(pff_i->pft); - 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_pft(pff_i, addr, fd, len)) - return -1; - - if (add_addr(pff_i, addr)) { - pft_delete(pff_i->pft, 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 (pft_delete(pff_i->pft, addr)) - return -1; - - if (add_to_pft(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 (pft_delete(pff_i->pft, addr)) - return -1; - - return 0; -} - -void alternate_pff_flush(struct pff_i * pff_i) -{ - assert(pff_i); - - pft_flush(pff_i->pft); - - del_nhops_down(pff_i); - - del_addrs(pff_i); -} - -int alternate_pff_nhop(struct pff_i * pff_i, - uint64_t addr) -{ - int fd; - size_t len; - int * fds; - - assert(pff_i); - - pthread_rwlock_rdlock(&pff_i->lock); - - if (pft_lookup(pff_i->pft, addr, &fds, &len)) { - pthread_rwlock_unlock(&pff_i->lock); - return -1; - } - - fd = *fds; - - 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 * p; - size_t len; - 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(p, &pff_i->addrs) { - struct addr * e = list_entry(p, struct addr, next); - if (pft_lookup(pff_i->pft, e->addr, &fds, &len)) { - pthread_rwlock_unlock(&pff_i->lock); - return -1; - } - - 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 deleted file mode 100644 index 9c7cc08f..00000000 --- a/src/ipcpd/unicast/pol/alternate_pff.h +++ /dev/null @@ -1,61 +0,0 @@ -/* - * Ouroboros - Copyright (C) 2016 - 2021 - * - * 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); - -extern struct pol_pff_ops alternate_pff_ops; - -#endif /* OUROBOROS_IPCPD_UNICAST_ALTERNATE_PFF_H */ diff --git a/src/ipcpd/unicast/pol/ca-mb-ecn.c b/src/ipcpd/unicast/pol/ca-mb-ecn.c deleted file mode 100644 index 7a88718f..00000000 --- a/src/ipcpd/unicast/pol/ca-mb-ecn.c +++ /dev/null @@ -1,296 +0,0 @@ -/* - * Ouroboros - Copyright (C) 2016 - 2021 - * - * Multi-bit ECN Congestion Avoidance - * - * 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 200809L -#endif - -#include "config.h" - -#include -#include - -#include "ca-mb-ecn.h" - -#include -#include -#include -#include - -/* congestion avoidance constants */ -#define CA_SHFT 5 /* Average over 32 pkts */ -#define CA_WND (1 << CA_SHFT) /* 32 pkts receiver wnd */ -#define CA_UPD (1 << (CA_SHFT - 2)) /* Update snd every 8 pkt */ -#define CA_SLOT 24 /* Initial slot = 16 ms */ -#define CA_INC 1UL << 16 /* ~4MiB/s^2 additive inc */ -#define CA_IWL 1UL << 16 /* Initial limit ~4MiB/s */ -#define CA_MINPS 8 /* Mimimum pkts / slot */ -#define CA_MAXPS 64 /* Maximum pkts / slot */ -#define ECN_Q_SHFT 4 -#define ts_to_ns(ts) ((size_t) ts.tv_sec * BILLION + ts.tv_nsec) - -struct mb_ecn_ctx { - uint16_t rx_ece; /* Level of congestion (upstream) */ - size_t rx_ctr; /* Receiver side packet counter */ - - uint16_t tx_ece; /* Level of congestion (downstream) */ - size_t tx_ctr; /* Sender side packet counter */ - size_t tx_wbc; /* Window byte count */ - size_t tx_wpc; /* Window packet count */ - size_t tx_wbl; /* Window byte limit */ - bool tx_cav; /* Congestion avoidance */ - size_t tx_mul; /* Slot size multiplier */ - size_t tx_inc; /* Additive increase */ - size_t tx_slot; -}; - -struct pol_ca_ops mb_ecn_ca_ops = { - .ctx_create = mb_ecn_ctx_create, - .ctx_destroy = mb_ecn_ctx_destroy, - .ctx_update_snd = mb_ecn_ctx_update_snd, - .ctx_update_rcv = mb_ecn_ctx_update_rcv, - .ctx_update_ece = mb_ecn_ctx_update_ece, - .wnd_wait = mb_ecn_wnd_wait, - .calc_ecn = mb_ecn_calc_ecn, - .print_stats = mb_ecn_print_stats -}; - -void * mb_ecn_ctx_create(void) -{ - struct timespec now; - struct mb_ecn_ctx * ctx; - - ctx = malloc(sizeof(*ctx)); - if (ctx == NULL) - return NULL; - - clock_gettime(PTHREAD_COND_CLOCK, &now); - - memset(ctx, 0, sizeof(*ctx)); - - ctx->tx_mul = CA_SLOT; - ctx->tx_wbl = CA_IWL; - ctx->tx_inc = CA_INC; - ctx->tx_slot = ts_to_ns(now) >> ctx->tx_mul; - - return (void *) ctx; -} - -void mb_ecn_ctx_destroy(void * ctx) -{ - free(ctx); -} - -#define _slot_after(new, old) ((int64_t) (old - new) < 0) - -ca_wnd_t mb_ecn_ctx_update_snd(void * _ctx, - size_t len) -{ - struct timespec now; - size_t slot; - ca_wnd_t wnd; - struct mb_ecn_ctx * ctx = _ctx; - - clock_gettime(PTHREAD_COND_CLOCK, &now); - - slot = ts_to_ns(now) >> ctx->tx_mul; - - ctx->tx_ctr++; - ctx->tx_wpc++; - ctx->tx_wbc += len; - - if (ctx->tx_ctr > CA_WND) - ctx->tx_ece = 0; - - if (_slot_after(slot, ctx->tx_slot)) { - bool carry = false; /* may carry over if window increases */ - - ctx->tx_slot = slot; - - if (!ctx->tx_cav) { /* Slow start */ - if (ctx->tx_wbc > ctx->tx_wbl) - ctx->tx_wbl <<= 1; - } else { - if (ctx->tx_ece) /* Mult. Decrease */ - ctx->tx_wbl -= (ctx->tx_wbl * ctx->tx_ece) - >> (CA_SHFT + 8); - else /* Add. Increase */ - ctx->tx_wbl = ctx->tx_wbc + ctx->tx_inc; - } - - /* Window scaling */ - if (ctx->tx_wpc < CA_MINPS) { - size_t fact = 0; /* factor to scale the window up */ - size_t pkts = ctx->tx_wpc; - while (pkts < CA_MINPS) { - pkts <<= 1; - fact++; - } - ctx->tx_mul += fact; - ctx->tx_slot >>= fact; - if ((ctx->tx_slot & ((1 << fact) - 1)) == 0) { - carry = true; - ctx->tx_slot += 1; - } - ctx->tx_wbl <<= fact; - ctx->tx_inc <<= fact; - } else if (ctx->tx_wpc > CA_MAXPS) { - size_t fact = 0; /* factor to scale the window down */ - size_t pkts = ctx->tx_wpc; - while (pkts > CA_MAXPS) { - pkts >>= 1; - fact++; - } - ctx->tx_mul -= fact; - ctx->tx_slot <<= fact; - ctx->tx_wbl >>= fact; - ctx->tx_inc >>= fact; - } else { - ctx->tx_slot = slot; - } - - if (!carry) { - ctx->tx_wbc = 0; - ctx->tx_wpc = 0; - } - } - - if (ctx->tx_wbc > ctx->tx_wbl) - wnd.wait = ((ctx->tx_slot + 1) << ctx->tx_mul) - ts_to_ns(now); - else - wnd.wait = 0; - - return wnd; -} - -void mb_ecn_wnd_wait(ca_wnd_t wnd) -{ - if (wnd.wait > 0) { - struct timespec s = {0, 0}; - if (wnd.wait > BILLION) /* Don't care throttling < 1s */ - s.tv_sec = 1; - else - s.tv_nsec = wnd.wait; - - nanosleep(&s, NULL); - } -} - -bool mb_ecn_ctx_update_rcv(void * _ctx, - size_t len, - uint8_t ecn, - uint16_t * ece) -{ - struct mb_ecn_ctx* ctx = _ctx; - bool update; - - (void) len; - - if ((ctx->rx_ece | ecn) == 0) - return false; - - if (ecn == 0) { /* End of congestion */ - ctx->rx_ece >>= 2; - update = ctx->rx_ece == 0; - } else { - if (ctx->rx_ece == 0) { /* Start of congestion */ - ctx->rx_ece = ecn; - ctx->rx_ctr = 0; - update = true; - } else { /* Congestion update */ - ctx->rx_ece -= ctx->rx_ece >> CA_SHFT; - ctx->rx_ece += ecn; - update = (ctx->rx_ctr++ & (CA_UPD - 1)) == true; - } - } - - *ece = ctx->rx_ece; - - return update; -} - - -void mb_ecn_ctx_update_ece(void * _ctx, - uint16_t ece) -{ - struct mb_ecn_ctx* ctx = _ctx; - - ctx->tx_ece = ece; - ctx->tx_ctr = 0; - ctx->tx_cav = true; -} - -int mb_ecn_calc_ecn(int fd, - uint8_t * ecn, - qoscube_t qc, - size_t len) -{ - size_t q; - - (void) len; - (void) qc; - - q = ipcp_flow_queued(fd); - - *ecn |= (uint8_t) (q >> ECN_Q_SHFT); - - return 0; -} - -ssize_t mb_ecn_print_stats(void * _ctx, - char * buf, - size_t len) -{ - struct mb_ecn_ctx* ctx = _ctx; - char * regime; - - if (len < 1024) - return 0; - - if (!ctx->tx_cav) - regime = "Slow start"; - else if (ctx->tx_ece) - regime = "Multiplicative dec"; - else - regime = "Additive inc"; - - sprintf(buf, - "Congestion avoidance algorithm: %20s\n" - "Upstream congestion level: %20u\n" - "Upstream packet counter: %20zu\n" - "Downstream congestion level: %20u\n" - "Downstream packet counter: %20zu\n" - "Congestion window size (ns): %20" PRIu64 "\n" - "Packets in this window: %20zu\n" - "Bytes in this window: %20zu\n" - "Max bytes in this window: %20zu\n" - "Current congestion regime: %20s\n", - "Multi-bit ECN", - ctx->tx_ece, ctx->tx_ctr, - ctx->rx_ece, ctx->rx_ctr, (uint64_t) (1ULL << ctx->tx_mul), - ctx->tx_wpc, ctx->tx_wbc, ctx->tx_wbl, - regime); - - return strlen(buf); -} diff --git a/src/ipcpd/unicast/pol/ca-mb-ecn.h b/src/ipcpd/unicast/pol/ca-mb-ecn.h deleted file mode 100644 index a90ae3e2..00000000 --- a/src/ipcpd/unicast/pol/ca-mb-ecn.h +++ /dev/null @@ -1,56 +0,0 @@ -/* - * Ouroboros - Copyright (C) 2016 - 2021 - * - * Multi-bit ECN Congestion Avoidance - * - * 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_CA_MB_ECN_H -#define OUROBOROS_IPCPD_UNICAST_CA_MB_ECN_H - -#include "pol-ca-ops.h" - -void * mb_ecn_ctx_create(void); - -void mb_ecn_ctx_destroy(void * ctx); - -ca_wnd_t mb_ecn_ctx_update_snd(void * ctx, - size_t len); - -bool mb_ecn_ctx_update_rcv(void * ctx, - size_t len, - uint8_t ecn, - uint16_t * ece); - -void mb_ecn_ctx_update_ece(void * ctx, - uint16_t ece); - -void mb_ecn_wnd_wait(ca_wnd_t wnd); - -int mb_ecn_calc_ecn(int fd, - uint8_t * ecn, - qoscube_t qc, - size_t len); - -ssize_t mb_ecn_print_stats(void * ctx, - char * buf, - size_t len); - -extern struct pol_ca_ops mb_ecn_ca_ops; - -#endif /* OUROBOROS_IPCPD_UNICAST_CA_MB_ECN_H */ diff --git a/src/ipcpd/unicast/pol/ca-nop.c b/src/ipcpd/unicast/pol/ca-nop.c deleted file mode 100644 index db908c5c..00000000 --- a/src/ipcpd/unicast/pol/ca-nop.c +++ /dev/null @@ -1,98 +0,0 @@ -/* - * Ouroboros - Copyright (C) 2016 - 2021 - * - * Dummy Congestion Avoidance - * - * 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/. - */ - -#include "ca-nop.h" - -#include - -struct pol_ca_ops nop_ca_ops = { - .ctx_create = nop_ctx_create, - .ctx_destroy = nop_ctx_destroy, - .ctx_update_snd = nop_ctx_update_snd, - .ctx_update_rcv = nop_ctx_update_rcv, - .ctx_update_ece = nop_ctx_update_ece, - .wnd_wait = nop_wnd_wait, - .calc_ecn = nop_calc_ecn, - .print_stats = NULL -}; - -void * nop_ctx_create(void) -{ - return (void *) 1; -} - -void nop_ctx_destroy(void * ctx) -{ - (void) ctx; -} - -ca_wnd_t nop_ctx_update_snd(void * ctx, - size_t len) -{ - ca_wnd_t wnd; - - (void) ctx; - (void) len; - - memset(&wnd, 0, sizeof(wnd)); - - return wnd; -} - -void nop_wnd_wait(ca_wnd_t wnd) -{ - (void) wnd; -} - -bool nop_ctx_update_rcv(void * ctx, - size_t len, - uint8_t ecn, - uint16_t * ece) -{ - (void) ctx; - (void) len; - (void) ecn; - (void) ece; - - return false; -} - -void nop_ctx_update_ece(void * ctx, - uint16_t ece) -{ - (void) ctx; - (void) ece; -} - - -int nop_calc_ecn(int fd, - uint8_t * ecn, - qoscube_t qc, - size_t len) -{ - (void) fd; - (void) len; - (void) ecn; - (void) qc; - - return 0; -} diff --git a/src/ipcpd/unicast/pol/ca-nop.h b/src/ipcpd/unicast/pol/ca-nop.h deleted file mode 100644 index 7b9d318f..00000000 --- a/src/ipcpd/unicast/pol/ca-nop.h +++ /dev/null @@ -1,52 +0,0 @@ -/* - * Ouroboros - Copyright (C) 2016 - 2021 - * - * Dummy Congestion Avoidance - * - * 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_CA_NOP_H -#define OUROBOROS_IPCPD_UNICAST_CA_NOP_H - -#include "pol-ca-ops.h" - -void * nop_ctx_create(void); - -void nop_ctx_destroy(void * ctx); - -ca_wnd_t nop_ctx_update_snd(void * ctx, - size_t len); - -bool nop_ctx_update_rcv(void * ctx, - size_t len, - uint8_t ecn, - uint16_t * ece); - -void nop_ctx_update_ece(void * ctx, - uint16_t ece); - -void nop_wnd_wait(ca_wnd_t wnd); - -int nop_calc_ecn(int fd, - uint8_t * ecn, - qoscube_t qc, - size_t len); - -extern struct pol_ca_ops nop_ca_ops; - -#endif /* OUROBOROS_IPCPD_UNICAST_CA_NOP_H */ diff --git a/src/ipcpd/unicast/pol/flat.c b/src/ipcpd/unicast/pol/flat.c deleted file mode 100644 index f869f761..00000000 --- a/src/ipcpd/unicast/pol/flat.c +++ /dev/null @@ -1,87 +0,0 @@ -/* - * Ouroboros - Copyright (C) 2016 - 2021 - * - * 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 deleted file mode 100644 index 21f7721a..00000000 --- a/src/ipcpd/unicast/pol/flat.h +++ /dev/null @@ -1,36 +0,0 @@ -/* - * Ouroboros - Copyright (C) 2016 - 2021 - * - * 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); - -extern 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 deleted file mode 100644 index 6ea5c507..00000000 --- a/src/ipcpd/unicast/pol/graph.c +++ /dev/null @@ -1,849 +0,0 @@ -/* - * Ouroboros - Copyright (C) 2016 - 2021 - * - * Undirected graph structure - * - * Dimitri Staessens - * Sander Vrijders - * Nick Aerts - * - * 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 vertex { - struct list_head next; - uint64_t addr; - struct list_head edges; - int index; -}; - -struct edge { - struct list_head next; - struct vertex * nb; - qosspec_t qs; - int announced; -}; - -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; - - assert(vertex); - - 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; - - assert(graph); - - 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; - - assert(vertex); - assert(nb); - - edge = malloc(sizeof(*edge)); - if (edge == NULL) - return NULL; - - edge->nb = nb; - edge->announced = 0; - - list_add(&edge->next, &vertex->edges); - - return edge; -} - -static void del_edge(struct edge * edge) -{ - assert(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; - - assert(graph); - - vertex = malloc(sizeof(*vertex)); - if (vertex == NULL) - return NULL; - - 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; - struct list_head * h; - - assert(graph); - assert(vertex); - - 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, h, &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; - - assert(v); - assert(graph); - assert(dist); - assert(used); - - *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; - - assert(graph); - assert(nhops); - assert(dist); - - *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; - - assert(table); - - 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; - - assert(graph); - assert(table); - assert(dist); - - /* 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; - struct nhop * n; - - assert(table); - - 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; -} - -static int graph_routing_table_lfa(struct graph * graph, - uint64_t s_addr, - struct list_head * table, - int ** 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; - int k; - - if (graph_routing_table_simple(graph, s_addr, table, dist)) - goto fail_table; - - 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] < - (*dist)[n_index[j]] + (*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]); - - return 0; - - fail_add_lfa: - for (k = j; k < i; k++) - free(n_dist[k]); - fail_dijkstra: - free_routing_table(table); - fail_table: - return -1; -} - -static int graph_routing_table_ecmp(struct graph * graph, - uint64_t s_addr, - struct list_head * table, - int ** dist) -{ - struct vertex ** nhops; - struct list_head * p; - struct list_head * h; - size_t i; - struct vertex * v; - struct vertex * src_v; - struct edge * e; - struct routing_table * t; - struct nhop * n; - struct list_head * forwarding; - - assert(graph); - assert(dist); - - if (graph-> nr_vertices < 2) - goto fail_vertices; - - forwarding = malloc(sizeof(*forwarding) * graph->nr_vertices); - if (forwarding == NULL) - goto fail_vertices; - - for (i = 0; i < graph->nr_vertices; ++i) - list_head_init(&forwarding[i]); - - if (dijkstra(graph, s_addr, &nhops, dist)) - goto fail_dijkstra; - - free(nhops); - - src_v = find_vertex_by_addr(graph, s_addr); - if (src_v == NULL) - goto fail_src_v; - - list_for_each(p, &src_v->edges) { - int * tmp_dist; - - e = list_entry(p, struct edge, next); - if (dijkstra(graph, e->nb->addr, &nhops, &tmp_dist)) - goto fail_src_v; - - free(nhops); - - list_for_each(h, &graph->vertices) { - v = list_entry(h, struct vertex, next); - if (tmp_dist[v->index] + 1 == (*dist)[v->index]) { - n = malloc(sizeof(*n)); - if (n == NULL) { - free(tmp_dist); - goto fail_src_v; - } - n->nhop = e->nb->addr; - list_add_tail(&n->next, &forwarding[v->index]); - } - } - - free(tmp_dist); - } - - list_head_init(table); - i = 0; - list_for_each(p, &graph->vertices) { - v = list_entry(p, struct vertex, next); - if (v->addr == s_addr) { - ++i; - continue; - } - - t = malloc(sizeof(*t)); - if (t == NULL) - goto fail_t; - - t->dst = v->addr; - - list_head_init(&t->nhops); - if (&forwarding[i] != forwarding[i].nxt) { - t->nhops.nxt = forwarding[i].nxt; - t->nhops.prv = forwarding[i].prv; - forwarding[i].prv->nxt = &t->nhops; - forwarding[i].nxt->prv = &t->nhops; - } - - list_add(&t->next, table); - ++i; - } - - free(*dist); - *dist = NULL; - free(forwarding); - - return 0; - - fail_t: - free_routing_table(table); - fail_src_v: - free(*dist); - fail_dijkstra: - free(forwarding); - fail_vertices: - *dist = NULL; - return -1; -} - -int graph_routing_table(struct graph * graph, - enum routing_algo algo, - uint64_t s_addr, - struct list_head * table) -{ - int * s_dist; - - assert(graph); - assert(table); - - pthread_mutex_lock(&graph->lock); - - switch (algo) { - case ROUTING_SIMPLE: - /* LFA uses the s_dist this returns. */ - if (graph_routing_table_simple(graph, s_addr, table, &s_dist)) - goto fail_table; - break; - case ROUTING_LFA: - if (graph_routing_table_lfa(graph, s_addr, table, &s_dist)) - goto fail_table; - break; - - case ROUTING_ECMP: - if (graph_routing_table_ecmp(graph, s_addr, table, &s_dist)) - goto fail_table; - break; - default: - log_err("Unsupported algorithm."); - goto fail_table; - } - - pthread_mutex_unlock(&graph->lock); - - free(s_dist); - - return 0; - - fail_table: - pthread_mutex_unlock(&graph->lock); - return -1; -} diff --git a/src/ipcpd/unicast/pol/graph.h b/src/ipcpd/unicast/pol/graph.h deleted file mode 100644 index 632cc5a0..00000000 --- a/src/ipcpd/unicast/pol/graph.h +++ /dev/null @@ -1,69 +0,0 @@ -/* - * Ouroboros - Copyright (C) 2016 - 2021 - * - * 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, - ROUTING_ECMP -}; - -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 deleted file mode 100644 index 08d39372..00000000 --- a/src/ipcpd/unicast/pol/link_state.c +++ /dev/null @@ -1,1055 +0,0 @@ -/* - * Ouroboros - Copyright (C) 2016 - 2021 - * - * 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 - -#include "common/comp.h" -#include "common/connmgr.h" -#include "graph.h" -#include "ipcp.h" -#include "link_state.h" -#include "pff.h" - -#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; - - assert(adj); - - 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_rib_getattr(const char * path, - struct rib_attr * attr) -{ - struct adjacency * adj; - struct timespec now; - char * entry; - - assert(path); - assert(attr); - - entry = strstr(path, RIB_SEPARATOR) + 1; - assert(entry); - - clock_gettime(CLOCK_REALTIME_COARSE, &now); - - pthread_rwlock_rdlock(&ls.db_lock); - - adj = get_adj(entry); - if (adj != NULL) { - attr->mtime = adj->stamp; - attr->size = LS_ENTRY_SIZE; - } else { - attr->mtime = now.tv_sec; - attr->size = 0; - } - - pthread_rwlock_unlock(&ls.db_lock); - - return 0; -} - -static int lsdb_rib_read(const char * path, - char * buf, - size_t len) -{ - struct adjacency * a; - char * entry; - int size; - - assert(path); - - entry = strstr(path, RIB_SEPARATOR) + 1; - assert(entry); - - pthread_rwlock_rdlock(&ls.db_lock); - - if (ls.db_len + ls.nbs_len == 0) - goto fail; - - a = get_adj(entry); - 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_rib_readdir(char *** buf) -{ - struct list_head * p; - char entry[RIB_PATH_LEN + 1]; - ssize_t idx = 0; - - assert(buf); - - 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_rib_read, - .readdir = lsdb_rib_readdir, - .getattr = lsdb_rib_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; - int fd; - - 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) { - fd = nb->fd; - pthread_rwlock_unlock(&ls.db_lock); - return 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]; - - assert(instance); - - 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; - - assert(qs); - - 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; - - assert(o); - - 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_wrlock(&ls.db_lock); - - pthread_cleanup_push(__cleanup_rwlock_unlock, &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(__cleanup_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 cleanup_fqueue(void * fq) -{ - fqueue_destroy((fqueue_t *) fq); -} - -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(cleanup_fqueue, 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; - - assert(o); - - c = (struct conn *) o; - - memset(&qs, 0, sizeof(qs)); - - switch (event) { - case NOTIFY_DT_CONN_ADD: - pthread_rwlock_rdlock(&ls.db_lock); - - pthread_cleanup_push(__cleanup_rwlock_unlock, &ls.db_lock); - - send_lsm(ipcpi.dt_addr, c->conn_info.addr, 0); - pthread_cleanup_pop(true); - - 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; - case ROUTING_LINK_STATE_ECMP: - log_dbg("Using Equal-Cost Multipath policy."); - ls.routing_algo = ROUTING_ECMP; - 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); - - notifier_unreg(handle_event); - - pthread_cancel(ls.listener); - pthread_cancel(ls.lsreader); - pthread_cancel(ls.lsupdate); - - pthread_join(ls.listener, NULL); - pthread_join(ls.lsreader, NULL); - 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); -} diff --git a/src/ipcpd/unicast/pol/link_state.h b/src/ipcpd/unicast/pol/link_state.h deleted file mode 100644 index 05b0ae5d..00000000 --- a/src/ipcpd/unicast/pol/link_state.h +++ /dev/null @@ -1,41 +0,0 @@ -/* - * Ouroboros - Copyright (C) 2016 - 2021 - * - * 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); - -extern struct pol_routing_ops link_state_ops; - -#endif /* OUROBOROS_IPCPD_UNICAST_POL_LINK_STATE_H */ diff --git a/src/ipcpd/unicast/pol/multipath_pff.c b/src/ipcpd/unicast/pol/multipath_pff.c deleted file mode 100644 index 0d759ec4..00000000 --- a/src/ipcpd/unicast/pol/multipath_pff.c +++ /dev/null @@ -1,198 +0,0 @@ -/* - * Ouroboros - Copyright (C) 2016 - 2021 - * - * Policy for PFF supporting multipath routing - * - * Dimitri Staessens - * Sander Vrijders - * Nick Aerts - * - * 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 "pft.h" -#include "multipath_pff.h" - -#include -#include -#include - -struct pff_i { - struct pft * pft; - pthread_rwlock_t lock; -}; - -struct pol_pff_ops multipath_pff_ops = { - .create = multipath_pff_create, - .destroy = multipath_pff_destroy, - .lock = multipath_pff_lock, - .unlock = multipath_pff_unlock, - .add = multipath_pff_add, - .update = multipath_pff_update, - .del = multipath_pff_del, - .flush = multipath_pff_flush, - .nhop = multipath_pff_nhop, - .flow_state_change = NULL -}; - -struct pff_i * multipath_pff_create(void) -{ - struct pff_i * tmp; - - tmp = malloc(sizeof(*tmp)); - if (tmp == NULL) - return NULL; - - if (pthread_rwlock_init(&tmp->lock, NULL)) { - free(tmp); - return NULL; - } - - tmp->pft = pft_create(PFT_SIZE, false); - if (tmp->pft == NULL) { - pthread_rwlock_destroy(&tmp->lock); - free(tmp); - return NULL; - } - - return tmp; -} - -void multipath_pff_destroy(struct pff_i * pff_i) -{ - assert(pff_i); - - pft_destroy(pff_i->pft); - - pthread_rwlock_destroy(&pff_i->lock); - free(pff_i); -} - -void multipath_pff_lock(struct pff_i * pff_i) -{ - pthread_rwlock_wrlock(&pff_i->lock); -} - -void multipath_pff_unlock(struct pff_i * pff_i) -{ - pthread_rwlock_unlock(&pff_i->lock); -} - -int multipath_pff_add(struct pff_i * pff_i, - uint64_t addr, - int * fds, - size_t len) -{ - int * tmp; - - assert(pff_i); - assert(fds); - assert(len > 0); - - tmp = malloc(len * sizeof(*tmp)); - if (tmp == NULL) - return -ENOMEM; - - memcpy(tmp,fds, len * sizeof(*tmp)); - - if (pft_insert(pff_i->pft, addr, tmp, len)) { - free(tmp); - return -1; - } - - return 0; -} - -int multipath_pff_update(struct pff_i * pff_i, - uint64_t addr, - int * fds, - size_t len) -{ - int * tmp; - - assert(pff_i); - assert(fds); - assert(len > 0); - - tmp = malloc(sizeof(*tmp)); - if (tmp == NULL) - return -ENOMEM; - - memcpy(tmp,fds, len * sizeof(*tmp)); - - if (pft_delete(pff_i->pft, addr)) { - free(tmp); - return -1; - } - - if (pft_insert(pff_i->pft, addr, tmp, 1)) { - free(tmp); - return -1; - } - - return 0; -} - -int multipath_pff_del(struct pff_i * pff_i, - uint64_t addr) -{ - assert(pff_i); - - if (pft_delete(pff_i->pft, addr)) - return -1; - - return 0; -} - -void multipath_pff_flush(struct pff_i * pff_i) -{ - assert(pff_i); - - pft_flush(pff_i->pft); -} - -int multipath_pff_nhop(struct pff_i * pff_i, - uint64_t addr) -{ - int fd; - int * fds; - size_t len; - - assert(pff_i); - - pthread_rwlock_rdlock(&pff_i->lock); - - if (pft_lookup(pff_i->pft, addr, &fds, &len)) { - pthread_rwlock_unlock(&pff_i->lock); - return -1; - } - - fd = *fds; - - assert(len > 0); - - /* Rotate fds left. */ - memcpy(fds, fds + 1, (len - 1) * sizeof(*fds)); - fds[len - 1] = fd; - - pthread_rwlock_unlock(&pff_i->lock); - - return fd; -} diff --git a/src/ipcpd/unicast/pol/multipath_pff.h b/src/ipcpd/unicast/pol/multipath_pff.h deleted file mode 100644 index 8168995e..00000000 --- a/src/ipcpd/unicast/pol/multipath_pff.h +++ /dev/null @@ -1,58 +0,0 @@ -/* - * Ouroboros - Copyright (C) 2016 - 2021 - * - * Policy for PFF supporting multipath routing - * - * Dimitri Staessens - * Sander Vrijders - * Nick Aerts - * - * This program is free software; you can redistribute it and/or modify - * it under the terms of the GNU General Public License version 2 as - * published by the Free Software Foundation. - * - * This program is distributed in the hope that it will be useful, - * but WITHOUT ANY WARRANTY; without even the implied warranty of - * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the - * GNU General Public License for more details. - * - * You should have received a copy of the GNU General Public License - * along with this program; if not, write to the Free Software - * Foundation, Inc., http://www.fsf.org/about/contact/. - */ - -#ifndef OUROBOROS_IPCPD_UNICAST_MULTIPATH_PFF_H -#define OUROBOROS_IPCPD_UNICAST_MULTIPATH_PFF_H - -#include "pol-pff-ops.h" - -struct pff_i * multipath_pff_create(void); - -void multipath_pff_destroy(struct pff_i * pff_i); - -void multipath_pff_lock(struct pff_i * pff_i); - -void multipath_pff_unlock(struct pff_i * pff_i); - -int multipath_pff_add(struct pff_i * pff_i, - uint64_t addr, - int * fds, - size_t len); - -int multipath_pff_update(struct pff_i * pff_i, - uint64_t addr, - int * fds, - size_t len); - -int multipath_pff_del(struct pff_i * pff_i, - uint64_t addr); - -void multipath_pff_flush(struct pff_i * pff_i); - -/* Returns fd towards next hop */ -int multipath_pff_nhop(struct pff_i * pff_i, - uint64_t addr); - -extern struct pol_pff_ops multipath_pff_ops; - -#endif /* OUROBOROS_IPCPD_UNICAST_MULTIPATH_PFF_H */ diff --git a/src/ipcpd/unicast/pol/pft.c b/src/ipcpd/unicast/pol/pft.c deleted file mode 100644 index e42b4a98..00000000 --- a/src/ipcpd/unicast/pol/pft.c +++ /dev/null @@ -1,223 +0,0 @@ -/* - * Ouroboros - Copyright (C) 2016 - 2021 - * - * Packet forwarding table (PFT) with chaining on collisions - * - * 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 -#endif - -#include -#include -#include - -#include "pft.h" - -#include -#include - -/* store output fds for dst addr */ -struct pft_entry { - struct list_head next; - uint64_t dst; - int * fds; - size_t len; -}; - -struct pft { - struct list_head * buckets; - bool hash_key; - uint64_t buckets_size; -}; - -struct pft * pft_create(uint64_t buckets, - bool hash_key) -{ - struct pft * tmp; - unsigned int i; - - if (buckets == 0) - return NULL; - - buckets--; - buckets |= buckets >> 1; - buckets |= buckets >> 2; - buckets |= buckets >> 4; - buckets |= buckets >> 8; - buckets |= buckets >> 16; - buckets |= buckets >> 32; - buckets++; - - tmp = malloc(sizeof(*tmp)); - if (tmp == NULL) - return NULL; - - tmp->hash_key = hash_key; - tmp->buckets_size = buckets; - - tmp->buckets = malloc(buckets * sizeof(*tmp->buckets)); - if (tmp->buckets == NULL) { - free(tmp); - return NULL; - } - - for (i = 0; i < buckets; i++) - list_head_init(&(tmp->buckets[i])); - - return tmp; -} - -void pft_destroy(struct pft * pft) -{ - assert(pft); - assert(pft->buckets); - - pft_flush(pft); - free(pft->buckets); - free(pft); -} - -void pft_flush(struct pft * pft) -{ - unsigned int i; - struct list_head * p; - struct list_head * h; - struct pft_entry * entry; - - assert(pft); - - for (i = 0; i < pft->buckets_size; i++) { - list_for_each_safe(p, h, &(pft->buckets[i])) { - entry = list_entry(p, struct pft_entry, next); - list_del(&entry->next); - free(entry->fds); - free(entry); - } - } -} - -static uint64_t hash(uint64_t key) -{ - void * res; - uint64_t ret; - uint8_t keys[4]; - - memcpy(keys, &key, 4); - - mem_hash(HASH_MD5, &res, keys, 4); - - ret = (* (uint64_t *) res); - - free(res); - - return ret; -} - -static uint64_t calc_key(struct pft * pft, - uint64_t dst) -{ - if (pft->hash_key) - dst = hash(dst); - - return (dst & (pft->buckets_size - 1)); -} - -int pft_insert(struct pft * pft, - uint64_t dst, - int * fds, - size_t len) -{ - struct pft_entry * entry; - uint64_t lookup_key; - struct list_head * p; - - assert(pft); - assert(len > 0); - - lookup_key = calc_key(pft, dst); - - list_for_each(p, &(pft->buckets[lookup_key])) { - entry = list_entry(p, struct pft_entry, next); - if (entry->dst == dst) - return -EPERM; - } - - entry = malloc(sizeof(*entry)); - if (entry == NULL) - return -ENOMEM; - - entry->dst = dst; - entry->fds = fds; - entry->len = len; - - list_add(&entry->next, &(pft->buckets[lookup_key])); - - return 0; -} - -int pft_lookup(struct pft * pft, - uint64_t dst, - int ** fds, - size_t * len) -{ - struct pft_entry * entry; - struct list_head * p; - uint64_t lookup_key; - - assert(pft); - - lookup_key = calc_key(pft, dst); - - list_for_each(p, &(pft->buckets[lookup_key])) { - entry = list_entry(p, struct pft_entry, next); - if (entry->dst == dst) { - *fds = entry->fds; - *len = entry->len; - return 0; - } - } - - return -1; -} - -int pft_delete(struct pft * pft, - uint64_t dst) -{ - struct pft_entry * entry; - uint64_t lookup_key; - struct list_head * p; - struct list_head * h; - - assert(pft); - - lookup_key = calc_key(pft, dst); - - list_for_each_safe(p, h, &(pft->buckets[lookup_key])) { - entry = list_entry(p, struct pft_entry, next); - if (entry->dst == dst) { - list_del(&entry->next); - free(entry->fds); - free(entry); - return 0; - } - } - - return -1; -} diff --git a/src/ipcpd/unicast/pol/pft.h b/src/ipcpd/unicast/pol/pft.h deleted file mode 100644 index 011ad414..00000000 --- a/src/ipcpd/unicast/pol/pft.h +++ /dev/null @@ -1,55 +0,0 @@ -/* - * Ouroboros - Copyright (C) 2016 - 2021 - * - * Packet forwarding table (PFT) with chaining on collisions - * - * 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_PFT_H -#define OUROBOROS_PFT_H - -#include -#include -#include - -struct pft; - -/* Buckets is rounded up to the nearest power of 2 */ -struct pft * pft_create(uint64_t buckets, - bool hash_key); - -void pft_destroy(struct pft * table); - -void pft_flush(struct pft * table); - -/* Passes ownership of the block of memory */ -int pft_insert(struct pft * pft, - uint64_t dst, - int * fds, - size_t len); - -/* The block of memory returned is no copy */ -int pft_lookup(struct pft * pft, - uint64_t dst, - int ** fds, - size_t * len); - -int pft_delete(struct pft * pft, - uint64_t dst); - -#endif /* OUROBOROS_PFT_H */ diff --git a/src/ipcpd/unicast/pol/simple_pff.c b/src/ipcpd/unicast/pol/simple_pff.c deleted file mode 100644 index 13944aed..00000000 --- a/src/ipcpd/unicast/pol/simple_pff.c +++ /dev/null @@ -1,190 +0,0 @@ -/* - * Ouroboros - Copyright (C) 2016 - 2021 - * - * 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 "pft.h" -#include "simple_pff.h" - -#include -#include - -struct pff_i { - struct pft * pft; - 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->pft = pft_create(PFT_SIZE, false); - if (tmp->pft == NULL) { - pthread_rwlock_destroy(&tmp->lock); - free(tmp); - return NULL; - } - - return tmp; -} - -void simple_pff_destroy(struct pff_i * pff_i) -{ - assert(pff_i); - - pft_destroy(pff_i->pft); - - pthread_rwlock_destroy(&pff_i->lock); - free(pff_i); -} - -void 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 * fds; - - assert(pff_i); - assert(fd); - assert(len > 0); - - (void) len; - - fds = malloc(sizeof(*fds)); - if (fds == NULL) - return -ENOMEM; - - *fds = *fd; - - if (pft_insert(pff_i->pft, addr, fds, 1)) { - free(fds); - return -1; - } - - return 0; -} - -int simple_pff_update(struct pff_i * pff_i, - uint64_t addr, - int * fd, - size_t len) -{ - int * fds; - - assert(pff_i); - assert(fd); - assert(len > 0); - - (void) len; - - fds = malloc(sizeof(*fds)); - if (fds == NULL) - return -ENOMEM; - - *fds = *fd; - - if (pft_delete(pff_i->pft, addr)) { - free(fds); - return -1; - } - - if (pft_insert(pff_i->pft, addr, fds, 1)) { - free(fds); - return -1; - } - - return 0; -} - -int simple_pff_del(struct pff_i * pff_i, - uint64_t addr) -{ - assert(pff_i); - - if (pft_delete(pff_i->pft, addr)) - return -1; - - return 0; -} - -void simple_pff_flush(struct pff_i * pff_i) -{ - assert(pff_i); - - pft_flush(pff_i->pft); -} - -int simple_pff_nhop(struct pff_i * pff_i, - uint64_t addr) -{ - int * fds; - size_t len; - int fd = -1; - - assert(pff_i); - - pthread_rwlock_rdlock(&pff_i->lock); - - if (pft_lookup(pff_i->pft, addr, &fds, &len) == 0) - fd = *fds; - - 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 deleted file mode 100644 index 2b22c130..00000000 --- a/src/ipcpd/unicast/pol/simple_pff.h +++ /dev/null @@ -1,57 +0,0 @@ -/* - * Ouroboros - Copyright (C) 2016 - 2021 - * - * 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); - -extern 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 deleted file mode 100644 index 34d80e8d..00000000 --- a/src/ipcpd/unicast/pol/tests/CMakeLists.txt +++ /dev/null @@ -1,35 +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 - pft_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 deleted file mode 100644 index 217c7eab..00000000 --- a/src/ipcpd/unicast/pol/tests/graph_test.c +++ /dev/null @@ -1,351 +0,0 @@ -/* - * Ouroboros - Copyright (C) 2016 - 2021 - * - * 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; -} - -static int distance_check(int dst, - int nhop, - enum routing_algo algo) -{ - (void) algo; - - /* Same distances for all algorithms at the moment. */ - if (dst == 2 && nhop != 2) { - printf("Wrong entry: 2.\n"); - return -1; - } - - if (dst == 3 && nhop != 3) { - printf("Wrong entry: 3.\n"); - return -1; - } - - if (dst == 4 && nhop != 3) { - printf("Wrong entry: 4.\n"); - return -1; - } - - if (dst == 5 && nhop != 3) { - printf("Wrong entry: 5.\n"); - return -1; - } - - if (dst == 6 && nhop != 2) { - printf("Wrong entry: 6.\n"); - return -1; - } - - if (dst == 7 && nhop != 3) { - printf("Wrong entry: 7.\n"); - return -1; - } - - 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"); - goto fail_graph; - } - - if (graph_del_edge(graph, 3, 2)) { - printf("Failed to delete edge.\n"); - goto fail_graph; - } - - if (graph_test_single_link()) - goto fail_graph; - - 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)) - goto fail_graph; - - 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)) - goto fail_graph; - - 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)) - goto fail_graph; - - - if (graph_routing_table(graph, ROUTING_SIMPLE, 1, &table)) { - printf("Failed to get routing table.\n"); - goto fail_graph; - } - - 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 (distance_check(dst, nhop, ROUTING_SIMPLE)) { - printf("Simple distance check failed.\n"); - goto fail_routing; - } - } - - graph_free_routing_table(graph, &table); - - if (graph_routing_table(graph, ROUTING_LFA, 1, &table)) { - printf("Failed to get routing table for LFA.\n"); - goto fail_graph; - } - - 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 (distance_check(dst, nhop, ROUTING_LFA)) { - printf("LFA distance check failed.\n"); - goto fail_routing; - } - } - - graph_free_routing_table(graph, &table); - - if (graph_routing_table(graph, ROUTING_ECMP, 1, &table)) { - printf("Failed to get routing table for ECMP.\n"); - goto fail_graph; - } - - 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 (distance_check(dst, nhop, ROUTING_LFA)) { - printf("LFA distance check failed.\n"); - goto fail_routing; - } - } - - graph_free_routing_table(graph, &table); - - graph_destroy(graph); - - return 0; - - fail_routing: - graph_free_routing_table(graph, &table); - fail_graph: - graph_destroy(graph); - return -1; -} diff --git a/src/ipcpd/unicast/pol/tests/pft_test.c b/src/ipcpd/unicast/pol/tests/pft_test.c deleted file mode 100644 index c48267eb..00000000 --- a/src/ipcpd/unicast/pol/tests/pft_test.c +++ /dev/null @@ -1,126 +0,0 @@ -/* - * Ouroboros - Copyright (C) 2016 - 2021 - * - * Test of the hash table - * - * 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/. - */ - -#include "pft.c" - -#include - -#define TBL_SIZE 256 -#define INT_TEST 4 - -int pft_test(int argc, - char ** argv) -{ - struct pft * pft; - int i; - int * j; - size_t len; - - (void) argc; - (void) argv; - - pft = pft_create(TBL_SIZE, true); - if (pft == NULL) { - printf("Failed to create.\n"); - return -1; - } - - pft_destroy(pft); - - pft = pft_create(TBL_SIZE, false); - if (pft == NULL) { - printf("Failed to create.\n"); - return -1; - } - - for (i = 0; i < TBL_SIZE + INT_TEST + 2; i++) { - j = malloc(sizeof(*j)); - if (j == NULL) { - printf("Failed to malloc.\n"); - pft_destroy(pft); - return -1; - } - *j = i; - - if (pft_insert(pft, i, j, 1)) { - printf("Failed to insert.\n"); - pft_destroy(pft); - free(j); - return -1; - } - } - - if (pft_lookup(pft, INT_TEST, &j, &len)) { - printf("Failed to lookup.\n"); - pft_destroy(pft); - return -1; - } - - if (*j != INT_TEST) { - printf("Lookup returned wrong value (%d != %d).\n", - INT_TEST, *j); - pft_destroy(pft); - return -1; - } - - if (pft_lookup(pft, TBL_SIZE + INT_TEST, &j, &len)) { - printf("Failed to lookup.\n"); - pft_destroy(pft); - return -1; - } - - if (*j != TBL_SIZE + INT_TEST) { - printf("Lookup returned wrong value (%d != %d).\n", - INT_TEST, *j); - pft_destroy(pft); - return -1; - } - - if (pft_delete(pft, INT_TEST)) { - printf("Failed to delete.\n"); - pft_destroy(pft); - return -1; - } - - if (pft_lookup(pft, INT_TEST, &j, &len) == 0) { - printf("Failed to delete properly.\n"); - pft_destroy(pft); - return -1; - } - - if (pft_lookup(pft, TBL_SIZE + INT_TEST, &j, &len)) { - printf("Failed to lookup after deletion.\n"); - pft_destroy(pft); - return -1; - } - - if (*j != TBL_SIZE + INT_TEST) { - printf("Lookup returned wrong value (%d != %d).\n", - INT_TEST, *j); - pft_destroy(pft); - return -1; - } - - pft_destroy(pft); - - return 0; -} diff --git a/src/ipcpd/unicast/routing.c b/src/ipcpd/unicast/routing.c index 1b13ae0e..b1e1ed77 100644 --- a/src/ipcpd/unicast/routing.c +++ b/src/ipcpd/unicast/routing.c @@ -26,9 +26,9 @@ #include "pff.h" #include "routing.h" -#include "pol/link_state.h" +#include "routing/link-state.h" -struct pol_routing_ops * r_ops; +struct routing_ops * r_ops; int routing_init(enum pol_routing pr) { diff --git a/src/ipcpd/unicast/routing/graph.c b/src/ipcpd/unicast/routing/graph.c new file mode 100644 index 00000000..6ea5c507 --- /dev/null +++ b/src/ipcpd/unicast/routing/graph.c @@ -0,0 +1,849 @@ +/* + * Ouroboros - Copyright (C) 2016 - 2021 + * + * Undirected graph structure + * + * Dimitri Staessens + * Sander Vrijders + * Nick Aerts + * + * 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 vertex { + struct list_head next; + uint64_t addr; + struct list_head edges; + int index; +}; + +struct edge { + struct list_head next; + struct vertex * nb; + qosspec_t qs; + int announced; +}; + +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; + + assert(vertex); + + 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; + + assert(graph); + + 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; + + assert(vertex); + assert(nb); + + edge = malloc(sizeof(*edge)); + if (edge == NULL) + return NULL; + + edge->nb = nb; + edge->announced = 0; + + list_add(&edge->next, &vertex->edges); + + return edge; +} + +static void del_edge(struct edge * edge) +{ + assert(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; + + assert(graph); + + vertex = malloc(sizeof(*vertex)); + if (vertex == NULL) + return NULL; + + 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; + struct list_head * h; + + assert(graph); + assert(vertex); + + 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, h, &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; + + assert(v); + assert(graph); + assert(dist); + assert(used); + + *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; + + assert(graph); + assert(nhops); + assert(dist); + + *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; + + assert(table); + + 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; + + assert(graph); + assert(table); + assert(dist); + + /* 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; + struct nhop * n; + + assert(table); + + 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; +} + +static int graph_routing_table_lfa(struct graph * graph, + uint64_t s_addr, + struct list_head * table, + int ** 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; + int k; + + if (graph_routing_table_simple(graph, s_addr, table, dist)) + goto fail_table; + + 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] < + (*dist)[n_index[j]] + (*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]); + + return 0; + + fail_add_lfa: + for (k = j; k < i; k++) + free(n_dist[k]); + fail_dijkstra: + free_routing_table(table); + fail_table: + return -1; +} + +static int graph_routing_table_ecmp(struct graph * graph, + uint64_t s_addr, + struct list_head * table, + int ** dist) +{ + struct vertex ** nhops; + struct list_head * p; + struct list_head * h; + size_t i; + struct vertex * v; + struct vertex * src_v; + struct edge * e; + struct routing_table * t; + struct nhop * n; + struct list_head * forwarding; + + assert(graph); + assert(dist); + + if (graph-> nr_vertices < 2) + goto fail_vertices; + + forwarding = malloc(sizeof(*forwarding) * graph->nr_vertices); + if (forwarding == NULL) + goto fail_vertices; + + for (i = 0; i < graph->nr_vertices; ++i) + list_head_init(&forwarding[i]); + + if (dijkstra(graph, s_addr, &nhops, dist)) + goto fail_dijkstra; + + free(nhops); + + src_v = find_vertex_by_addr(graph, s_addr); + if (src_v == NULL) + goto fail_src_v; + + list_for_each(p, &src_v->edges) { + int * tmp_dist; + + e = list_entry(p, struct edge, next); + if (dijkstra(graph, e->nb->addr, &nhops, &tmp_dist)) + goto fail_src_v; + + free(nhops); + + list_for_each(h, &graph->vertices) { + v = list_entry(h, struct vertex, next); + if (tmp_dist[v->index] + 1 == (*dist)[v->index]) { + n = malloc(sizeof(*n)); + if (n == NULL) { + free(tmp_dist); + goto fail_src_v; + } + n->nhop = e->nb->addr; + list_add_tail(&n->next, &forwarding[v->index]); + } + } + + free(tmp_dist); + } + + list_head_init(table); + i = 0; + list_for_each(p, &graph->vertices) { + v = list_entry(p, struct vertex, next); + if (v->addr == s_addr) { + ++i; + continue; + } + + t = malloc(sizeof(*t)); + if (t == NULL) + goto fail_t; + + t->dst = v->addr; + + list_head_init(&t->nhops); + if (&forwarding[i] != forwarding[i].nxt) { + t->nhops.nxt = forwarding[i].nxt; + t->nhops.prv = forwarding[i].prv; + forwarding[i].prv->nxt = &t->nhops; + forwarding[i].nxt->prv = &t->nhops; + } + + list_add(&t->next, table); + ++i; + } + + free(*dist); + *dist = NULL; + free(forwarding); + + return 0; + + fail_t: + free_routing_table(table); + fail_src_v: + free(*dist); + fail_dijkstra: + free(forwarding); + fail_vertices: + *dist = NULL; + return -1; +} + +int graph_routing_table(struct graph * graph, + enum routing_algo algo, + uint64_t s_addr, + struct list_head * table) +{ + int * s_dist; + + assert(graph); + assert(table); + + pthread_mutex_lock(&graph->lock); + + switch (algo) { + case ROUTING_SIMPLE: + /* LFA uses the s_dist this returns. */ + if (graph_routing_table_simple(graph, s_addr, table, &s_dist)) + goto fail_table; + break; + case ROUTING_LFA: + if (graph_routing_table_lfa(graph, s_addr, table, &s_dist)) + goto fail_table; + break; + + case ROUTING_ECMP: + if (graph_routing_table_ecmp(graph, s_addr, table, &s_dist)) + goto fail_table; + break; + default: + log_err("Unsupported algorithm."); + goto fail_table; + } + + pthread_mutex_unlock(&graph->lock); + + free(s_dist); + + return 0; + + fail_table: + pthread_mutex_unlock(&graph->lock); + return -1; +} diff --git a/src/ipcpd/unicast/routing/graph.h b/src/ipcpd/unicast/routing/graph.h new file mode 100644 index 00000000..632cc5a0 --- /dev/null +++ b/src/ipcpd/unicast/routing/graph.h @@ -0,0 +1,69 @@ +/* + * Ouroboros - Copyright (C) 2016 - 2021 + * + * 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, + ROUTING_ECMP +}; + +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/routing/link-state.c b/src/ipcpd/unicast/routing/link-state.c new file mode 100644 index 00000000..7ceb86a1 --- /dev/null +++ b/src/ipcpd/unicast/routing/link-state.c @@ -0,0 +1,1055 @@ +/* + * Ouroboros - Copyright (C) 2016 - 2021 + * + * 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 + +#include "common/comp.h" +#include "common/connmgr.h" +#include "graph.h" +#include "ipcp.h" +#include "link-state.h" +#include "pff.h" + +#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 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; + + assert(adj); + + 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_rib_getattr(const char * path, + struct rib_attr * attr) +{ + struct adjacency * adj; + struct timespec now; + char * entry; + + assert(path); + assert(attr); + + entry = strstr(path, RIB_SEPARATOR) + 1; + assert(entry); + + clock_gettime(CLOCK_REALTIME_COARSE, &now); + + pthread_rwlock_rdlock(&ls.db_lock); + + adj = get_adj(entry); + if (adj != NULL) { + attr->mtime = adj->stamp; + attr->size = LS_ENTRY_SIZE; + } else { + attr->mtime = now.tv_sec; + attr->size = 0; + } + + pthread_rwlock_unlock(&ls.db_lock); + + return 0; +} + +static int lsdb_rib_read(const char * path, + char * buf, + size_t len) +{ + struct adjacency * a; + char * entry; + int size; + + assert(path); + + entry = strstr(path, RIB_SEPARATOR) + 1; + assert(entry); + + pthread_rwlock_rdlock(&ls.db_lock); + + if (ls.db_len + ls.nbs_len == 0) + goto fail; + + a = get_adj(entry); + 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_rib_readdir(char *** buf) +{ + struct list_head * p; + char entry[RIB_PATH_LEN + 1]; + ssize_t idx = 0; + + assert(buf); + + 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_rib_read, + .readdir = lsdb_rib_readdir, + .getattr = lsdb_rib_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; + int fd; + + 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) { + fd = nb->fd; + pthread_rwlock_unlock(&ls.db_lock); + return 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]; + + assert(instance); + + 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; + + assert(qs); + + 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; + + assert(o); + + 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_wrlock(&ls.db_lock); + + pthread_cleanup_push(__cleanup_rwlock_unlock, &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(__cleanup_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 cleanup_fqueue(void * fq) +{ + fqueue_destroy((fqueue_t *) fq); +} + +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(cleanup_fqueue, 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; + + assert(o); + + c = (struct conn *) o; + + memset(&qs, 0, sizeof(qs)); + + switch (event) { + case NOTIFY_DT_CONN_ADD: + pthread_rwlock_rdlock(&ls.db_lock); + + pthread_cleanup_push(__cleanup_rwlock_unlock, &ls.db_lock); + + send_lsm(ipcpi.dt_addr, c->conn_info.addr, 0); + pthread_cleanup_pop(true); + + 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; + case ROUTING_LINK_STATE_ECMP: + log_dbg("Using Equal-Cost Multipath policy."); + ls.routing_algo = ROUTING_ECMP; + 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); + + notifier_unreg(handle_event); + + pthread_cancel(ls.listener); + pthread_cancel(ls.lsreader); + pthread_cancel(ls.lsupdate); + + pthread_join(ls.listener, NULL); + pthread_join(ls.lsreader, NULL); + 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); +} diff --git a/src/ipcpd/unicast/routing/link-state.h b/src/ipcpd/unicast/routing/link-state.h new file mode 100644 index 00000000..c6e573ff --- /dev/null +++ b/src/ipcpd/unicast/routing/link-state.h @@ -0,0 +1,41 @@ +/* + * Ouroboros - Copyright (C) 2016 - 2021 + * + * 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 "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); + +extern struct routing_ops link_state_ops; + +#endif /* OUROBOROS_IPCPD_UNICAST_POL_LINK_STATE_H */ diff --git a/src/ipcpd/unicast/routing/ops.h b/src/ipcpd/unicast/routing/ops.h new file mode 100644 index 00000000..1522ccd9 --- /dev/null +++ b/src/ipcpd/unicast/routing/ops.h @@ -0,0 +1,38 @@ +/* + * Ouroboros - Copyright (C) 2016 - 2021 + * + * Routing policy ops + * + * 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_ROUTING_OPS_H +#define OUROBOROS_IPCPD_UNICAST_ROUTING_OPS_H + +#include "pff.h" + +struct routing_ops { + int (* init)(enum pol_routing pr); + + void (* fini)(void); + + struct routing_i * (* routing_i_create)(struct pff * pff); + + void (* routing_i_destroy)(struct routing_i * instance); +}; + +#endif /* OUROBOROS_IPCPD_UNICAST_ROUTING_OPS_H */ diff --git a/src/ipcpd/unicast/routing/tests/CMakeLists.txt b/src/ipcpd/unicast/routing/tests/CMakeLists.txt new file mode 100644 index 00000000..d0652533 --- /dev/null +++ b/src/ipcpd/unicast/routing/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/routing/tests/graph_test.c b/src/ipcpd/unicast/routing/tests/graph_test.c new file mode 100644 index 00000000..217c7eab --- /dev/null +++ b/src/ipcpd/unicast/routing/tests/graph_test.c @@ -0,0 +1,351 @@ +/* + * Ouroboros - Copyright (C) 2016 - 2021 + * + * 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; +} + +static int distance_check(int dst, + int nhop, + enum routing_algo algo) +{ + (void) algo; + + /* Same distances for all algorithms at the moment. */ + if (dst == 2 && nhop != 2) { + printf("Wrong entry: 2.\n"); + return -1; + } + + if (dst == 3 && nhop != 3) { + printf("Wrong entry: 3.\n"); + return -1; + } + + if (dst == 4 && nhop != 3) { + printf("Wrong entry: 4.\n"); + return -1; + } + + if (dst == 5 && nhop != 3) { + printf("Wrong entry: 5.\n"); + return -1; + } + + if (dst == 6 && nhop != 2) { + printf("Wrong entry: 6.\n"); + return -1; + } + + if (dst == 7 && nhop != 3) { + printf("Wrong entry: 7.\n"); + return -1; + } + + 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"); + goto fail_graph; + } + + if (graph_del_edge(graph, 3, 2)) { + printf("Failed to delete edge.\n"); + goto fail_graph; + } + + if (graph_test_single_link()) + goto fail_graph; + + 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)) + goto fail_graph; + + 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)) + goto fail_graph; + + 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)) + goto fail_graph; + + + if (graph_routing_table(graph, ROUTING_SIMPLE, 1, &table)) { + printf("Failed to get routing table.\n"); + goto fail_graph; + } + + 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 (distance_check(dst, nhop, ROUTING_SIMPLE)) { + printf("Simple distance check failed.\n"); + goto fail_routing; + } + } + + graph_free_routing_table(graph, &table); + + if (graph_routing_table(graph, ROUTING_LFA, 1, &table)) { + printf("Failed to get routing table for LFA.\n"); + goto fail_graph; + } + + 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 (distance_check(dst, nhop, ROUTING_LFA)) { + printf("LFA distance check failed.\n"); + goto fail_routing; + } + } + + graph_free_routing_table(graph, &table); + + if (graph_routing_table(graph, ROUTING_ECMP, 1, &table)) { + printf("Failed to get routing table for ECMP.\n"); + goto fail_graph; + } + + 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 (distance_check(dst, nhop, ROUTING_LFA)) { + printf("LFA distance check failed.\n"); + goto fail_routing; + } + } + + graph_free_routing_table(graph, &table); + + graph_destroy(graph); + + return 0; + + fail_routing: + graph_free_routing_table(graph, &table); + fail_graph: + graph_destroy(graph); + return -1; +} -- cgit v1.2.3