diff options
author | Dimitri Staessens <dimitri@ouroboros.rocks> | 2021-12-04 15:35:36 +0100 |
---|---|---|
committer | Sander Vrijders <sander@ouroboros.rocks> | 2021-12-06 17:52:08 +0100 |
commit | 11d2ecc140486949c8d81e984137263ca48d5799 (patch) | |
tree | 3b9a61015cb86e75fa7284fb1f3e66d7b326025e /src/ipcpd/unicast/pff | |
parent | b8ffe155228dd05f8097422349e8e6525288bbdb (diff) | |
download | ouroboros-11d2ecc140486949c8d81e984137263ca48d5799.tar.gz ouroboros-11d2ecc140486949c8d81e984137263ca48d5799.zip |
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 <dimitri@ouroboros.rocks>
Signed-off-by: Sander Vrijders <sander@ouroboros.rocks>
Diffstat (limited to 'src/ipcpd/unicast/pff')
-rw-r--r-- | src/ipcpd/unicast/pff/alternate.c | 400 | ||||
-rw-r--r-- | src/ipcpd/unicast/pff/alternate.h | 61 | ||||
-rw-r--r-- | src/ipcpd/unicast/pff/multipath.c | 198 | ||||
-rw-r--r-- | src/ipcpd/unicast/pff/multipath.h | 58 | ||||
-rw-r--r-- | src/ipcpd/unicast/pff/ops.h | 63 | ||||
-rw-r--r-- | src/ipcpd/unicast/pff/pft.c | 223 | ||||
-rw-r--r-- | src/ipcpd/unicast/pff/pft.h | 55 | ||||
-rw-r--r-- | src/ipcpd/unicast/pff/simple.c | 190 | ||||
-rw-r--r-- | src/ipcpd/unicast/pff/simple.h | 57 | ||||
-rw-r--r-- | src/ipcpd/unicast/pff/tests/CMakeLists.txt | 34 | ||||
-rw-r--r-- | src/ipcpd/unicast/pff/tests/pft_test.c | 126 |
11 files changed, 1465 insertions, 0 deletions
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 <dimitri@ouroboros.rocks> + * Sander Vrijders <sander@ouroboros.rocks> + * + * This program is free software; you can redistribute it and/or modify + * it under the terms of the GNU General Public License version 2 as + * published by the Free Software Foundation. + * + * This program is distributed in the hope that it will be useful, + * but WITHOUT ANY WARRANTY; without even the implied warranty of + * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the + * GNU General Public License for more details. + * + * You should have received a copy of the GNU General Public License + * along with this program; if not, write to the Free Software + * Foundation, Inc., http://www.fsf.org/about/contact/. + */ + +#define _POSIX_C_SOURCE 200112L + +#include "config.h" + +#include <ouroboros/errno.h> +#include <ouroboros/list.h> + +#include "pft.h" +#include "alternate.h" + +#include <string.h> +#include <assert.h> +#include <pthread.h> + +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 <dimitri@ouroboros.rocks> + * Sander Vrijders <sander@ouroboros.rocks> + * + * 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 <dimitri@ouroboros.rocks> + * Sander Vrijders <sander@ouroboros.rocks> + * Nick Aerts <nick.aerts@ugent.be> + * + * This program is free software; you can redistribute it and/or modify + * it under the terms of the GNU General Public License version 2 as + * published by the Free Software Foundation. + * + * This program is distributed in the hope that it will be useful, + * but WITHOUT ANY WARRANTY; without even the implied warranty of + * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the + * GNU General Public License for more details. + * + * You should have received a copy of the GNU General Public License + * along with this program; if not, write to the Free Software + * Foundation, Inc., http://www.fsf.org/about/contact/. + */ + +#define _POSIX_C_SOURCE 200112L + +#include "config.h" + +#include <ouroboros/errno.h> + +#include "pft.h" +#include "multipath.h" + +#include <string.h> +#include <assert.h> +#include <pthread.h> + +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 <dimitri@ouroboros.rocks> + * Sander Vrijders <sander@ouroboros.rocks> + * Nick Aerts <nick.aerts@ugent.be> + * + * This program is free software; you can redistribute it and/or modify + * it under the terms of the GNU General Public License version 2 as + * published by the Free Software Foundation. + * + * This program is distributed in the hope that it will be useful, + * but WITHOUT ANY WARRANTY; without even the implied warranty of + * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the + * GNU General Public License for more details. + * + * You should have received a copy of the GNU General Public License + * along with this program; if not, write to the Free Software + * Foundation, Inc., http://www.fsf.org/about/contact/. + */ + +#ifndef OUROBOROS_IPCPD_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 <dimitri@ouroboros.rocks> + * Sander Vrijders <sander@ouroboros.rocks> + * + * 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 <stdbool.h> + +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 <dimitri@ouroboros.rocks> + * Sander Vrijders <sander@ouroboros.rocks> + * + * 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 <ouroboros/list.h> +#include <ouroboros/errno.h> +#include <ouroboros/hash.h> + +#include "pft.h" + +#include <assert.h> +#include <string.h> + +/* store <len> 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 <dimitri@ouroboros.rocks> + * Sander Vrijders <sander@ouroboros.rocks> + * + * 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 <stdint.h> +#include <stdbool.h> +#include <stdlib.h> + +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 <dimitri@ouroboros.rocks> + * Sander Vrijders <sander@ouroboros.rocks> + * + * This program is free software; you can redistribute it and/or modify + * it under the terms of the GNU General Public License version 2 as + * published by the Free Software Foundation. + * + * This program is distributed in the hope that it will be useful, + * but WITHOUT ANY WARRANTY; without even the implied warranty of + * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the + * GNU General Public License for more details. + * + * You should have received a copy of the GNU General Public License + * along with this program; if not, write to the Free Software + * Foundation, Inc., http://www.fsf.org/about/contact/. + */ + +#define _POSIX_C_SOURCE 200112L + +#include "config.h" + +#include <ouroboros/errno.h> + +#include "pft.h" +#include "simple.h" + +#include <assert.h> +#include <pthread.h> + +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 <dimitri@ouroboros.rocks> + * Sander Vrijders <sander@ouroboros.rocks> + * + * 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 <dimitri@ouroboros.rocks> + * Sander Vrijders <sander@ouroboros.rocks> + * + * 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 <stdio.h> + +#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; +} |