From e43f8026923e57a5a61bff29254399fd68119f1d Mon Sep 17 00:00:00 2001 From: dimitri staessens Date: Fri, 20 Jan 2017 12:55:43 +0100 Subject: lib: Fix return value and typo in fqueue --- src/lib/dev.c | 2 +- 1 file changed, 1 insertion(+), 1 deletion(-) (limited to 'src') diff --git a/src/lib/dev.c b/src/lib/dev.c index 8cd8cd53..c62fea40 100644 --- a/src/lib/dev.c +++ b/src/lib/dev.c @@ -1094,7 +1094,7 @@ int flow_event_wait(struct flow_set * set, return -EINVAL; if (fq->fqsize > 0) - return 0; + return fq->fqsize; assert(!fq->next); -- cgit v1.2.3 From 82d947a8321737108f545a25f91d7d50d10e831d Mon Sep 17 00:00:00 2001 From: dimitri staessens Date: Fri, 20 Jan 2017 12:57:18 +0100 Subject: lib: Add move operation for lists Allows moving the elements of one linked list to another. Re-initializes the source list. --- include/ouroboros/list.h | 3 +++ src/lib/list.c | 11 +++++++++++ 2 files changed, 14 insertions(+) (limited to 'src') diff --git a/include/ouroboros/list.h b/include/ouroboros/list.h index 824e6684..5f246775 100644 --- a/include/ouroboros/list.h +++ b/include/ouroboros/list.h @@ -54,6 +54,9 @@ void list_add_tail(struct list_head * e, void list_del(struct list_head * e); +void list_move(struct list_head * dst, + struct list_head * src); + bool list_is_empty(struct list_head * h); #endif diff --git a/src/lib/list.c b/src/lib/list.c index 908d3b71..01fdf6e3 100644 --- a/src/lib/list.c +++ b/src/lib/list.c @@ -70,3 +70,14 @@ bool list_is_empty(struct list_head * h) { return h->nxt == h; } + +void list_move(struct list_head * dst, + struct list_head * src) +{ + dst->nxt = src->nxt; + dst->prv = src->prv; + dst->nxt->prv = src->nxt->prv; + dst->prv->nxt = src->prv->nxt; + + list_head_init(src); +} -- cgit v1.2.3 From 9c92dd66d5e7fab3a3e243abbad9a20b29891fee Mon Sep 17 00:00:00 2001 From: dimitri staessens Date: Fri, 20 Jan 2017 12:59:17 +0100 Subject: lib: Add new version of Resource Information Base The new RIB is implemented as a tree with doubly linked nodes (parents keep a link to each child, each child keeps a link to its parent). An index is kept in a btree using CRC32 hashes of the path name in the RIB. Nodes keep an SHA3-256 hash value that is unique for the entire subtree. This allows quick checks to see if two RIB subtrees are in sync. The event system for the RIB is based on the event system for flows (fqueue), but implemented completely in dynamic memory using linked lists. An initial test is performed for the RIB. This PR does not modify existing code to use the new RIB. --- include/ouroboros/config.h.in | 1 + include/ouroboros/rib.h | 61 +++ include/ouroboros/rqueue.h | 72 +++ src/lib/CMakeLists.txt | 1 + src/lib/rib.c | 1097 +++++++++++++++++++++++++++++++++++++++++ src/lib/tests/CMakeLists.txt | 1 + src/lib/tests/rib_test.c | 222 +++++++++ 7 files changed, 1455 insertions(+) create mode 100644 include/ouroboros/rib.h create mode 100644 include/ouroboros/rqueue.h create mode 100644 src/lib/rib.c create mode 100644 src/lib/tests/rib_test.c (limited to 'src') diff --git a/include/ouroboros/config.h.in b/include/ouroboros/config.h.in index 4b5943c5..5597bb0b 100644 --- a/include/ouroboros/config.h.in +++ b/include/ouroboros/config.h.in @@ -61,5 +61,6 @@ #define SOCKET_TIMEOUT 4000 #define CDAP_REPLY_TIMEOUT 1000 #define ENROLL_TIMEOUT 2000 +#define RIB_MAX_PATH_LEN 256 #endif diff --git a/include/ouroboros/rib.h b/include/ouroboros/rib.h new file mode 100644 index 00000000..5acf0330 --- /dev/null +++ b/include/ouroboros/rib.h @@ -0,0 +1,61 @@ +/* + * Ouroboros - Copyright (C) 2016 - 2017 + * + * Resource Information Base + * + * Sander Vrijders + * Dimitri Staessens + * + * This library is free software; you can redistribute it and/or + * modify it under the terms of the GNU Lesser General Public License + * version 2.1 as published by the Free Software Foundation. + * + * This library 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 + * Lesser General Public License for more details. + * + * You should have received a copy of the GNU Lesser General Public + * License along with this library; if not, write to the Free Software + * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA + * 02110-1301 USA + */ + +#ifndef OUROBOROS_LIB_RIB_H +#define OUROBOROS_LIB_RIB_H + +#include +#include + +#define RIB_ROOT "" + +int rib_init(void); + +void rib_fini(void); + +int rib_add(const char * parent, + const char * name); + +int rib_del(char * path); + +ssize_t rib_read(const char * path, + void * data, + size_t len); + +int rib_write(const char * path, + const void * data, + size_t len); + +int rib_put(const char * path, + void * data, + size_t len); + +bool rib_has(const char * path); + +char * rib_path_append(char * path, + const char * name); + +char * rib_name_gen(void * data, + size_t len); + +#endif /* OUROBOROS_LIB_RIB_H */ diff --git a/include/ouroboros/rqueue.h b/include/ouroboros/rqueue.h new file mode 100644 index 00000000..7bfbfa8f --- /dev/null +++ b/include/ouroboros/rqueue.h @@ -0,0 +1,72 @@ +/* + * Ouroboros - Copyright (C) 2016 - 2017 + * + * RIB event queues + * + * Dimitri Staessens + * Sander Vrijders + * + * This library is free software; you can redistribute it and/or + * modify it under the terms of the GNU Lesser General Public License + * version 2.1 as published by the Free Software Foundation. + * + * This library 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 + * Lesser General Public License for more details. + * + * You should have received a copy of the GNU Lesser General Public + * License along with this library; if not, write to the Free Software + * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA + * 02110-1301 USA + */ + +#ifndef OUROBOROS_RQUEUE_H +#define OUROBOROS_RQUEUE_H + +#include +#include +#include + +#define RO_READ 0x00000001 +#define RO_MODIFY 0x00000002 +#define RO_CREATE 0x00000004 +#define RO_DELETE 0x00000008 +#define RO_START 0x00000010 +#define RO_STOP 0x00000020 + +#define RO_NO_OPS 0x00000000 +#define RO_ALL_OPS 0xFFFFFFFF + +struct ro_set; + +struct rqueue; + +typedef struct ro_set ro_set_t; +typedef struct rqueue rqueue_t; + +ro_set_t * ro_set_create(void); + +void ro_set_destroy(ro_set_t * set); + +rqueue_t * rqueue_create(void); + +int rqueue_destroy(struct rqueue * rq); + +int ro_set_zero(ro_set_t * set); + +int ro_set_add(ro_set_t * set, + const char * path, + int32_t flags); + +int ro_set_del(ro_set_t * set, + const char * path); + +int32_t rqueue_next(rqueue_t * rq, + char * path); + +int rib_event_wait(ro_set_t * set, + rqueue_t * rq, + const struct timespec * timeout); + +#endif /* OUROBOROS_RQUEUE_H */ diff --git a/src/lib/CMakeLists.txt b/src/lib/CMakeLists.txt index 34ae6ae4..6959a820 100644 --- a/src/lib/CMakeLists.txt +++ b/src/lib/CMakeLists.txt @@ -40,6 +40,7 @@ set(SOURCE_FILES lockfile.c logs.c nsm.c + rib.c sha3.c shm_flow_set.c shm_rbuff.c diff --git a/src/lib/rib.c b/src/lib/rib.c new file mode 100644 index 00000000..4d1ae884 --- /dev/null +++ b/src/lib/rib.c @@ -0,0 +1,1097 @@ +/* + * Ouroboros - Copyright (C) 2016 - 2017 + * + * Resource Information Base + * + * Dimitri Staessens + * Sander Vrijders + * + * This library is free software; you can redistribute it and/or + * modify it under the terms of the GNU Lesser General Public License + * version 2.1 as published by the Free Software Foundation. + * + * This library 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 + * Lesser General Public License for more details. + * + * You should have received a copy of the GNU Lesser General Public + * License along with this library; if not, write to the Free Software + * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA + * 02110-1301 USA + */ + +#include +#include +#include +#include +#include +#include +#include +#include + +#include "sha3.h" +#include "btree.h" + +#include +#include +#include +#include +#include + +#define RIB_PATH_DLR "/" +#define RIB_BTREE_ORDER 64 +#define GEN_NAME_SIZE 8 + +struct revent { + struct list_head next; + + char * path; + int32_t flags; +}; + +struct rqueue { + struct list_head events; +}; + +struct ro_set { + uint32_t sid; +}; + +struct rn_ptr { + struct list_head next; + + struct rnode * node; +}; + +struct rib_sub { + struct list_head next; + + uint32_t sid; + + struct list_head rnodes; + + struct list_head events; + + pthread_cond_t cond; + pthread_mutex_t lock; +}; + +struct rn_sub { + struct list_head next; + + struct rib_sub * sub; + int32_t flags; +}; + +struct rnode { + char * path; + char * name; + + uint8_t * data; + size_t len; + + uint8_t sha3[sha3_256_hash_size]; + + struct rnode * parent; + + struct list_head children; + + struct list_head subs; +}; + +struct child { + struct list_head next; + + struct rnode * node; +}; + +struct rib { + struct rnode * root; + + struct btree * idx; + + pthread_rwlock_t lock; + + struct bmp * sids; + + struct list_head subs; + + pthread_rwlock_t s_lock; +} rib; + +static void rnode_hash(struct rnode * node) +{ + struct sha3_ctx ctx; + struct list_head * p; + + assert(node); + assert(node->path); + assert(node->name); + + rhash_sha3_256_init(&ctx); + + rhash_sha3_update(&ctx, (uint8_t *) node->path, strlen(node->path)); + + if (node->data != NULL) + rhash_sha3_update(&ctx, node->data, node->len); + + list_for_each(p, &node->children) { + struct child * c = list_entry(p, struct child, next); + rhash_sha3_update(&ctx, c->node->sha3, sha3_256_hash_size); + } + + rhash_sha3_final(&ctx, node->sha3); +} + +static void branch_hash(struct rnode * node) +{ + assert(node); + + do { + rnode_hash(node); + node = node->parent; + } while (node != NULL); +} + +static struct revent * revent_dup(struct revent * ev) +{ + struct revent * re; + + assert(ev); + assert(ev->path); + + re = malloc(sizeof(*re)); + if (re == NULL) + return NULL; + + re->path = strdup(ev->path); + if (re->path == NULL) { + free(re); + return NULL; + } + + re->flags = ev->flags; + + return re; +} + +/* defined below but needed here */ +static void rib_sub_del_rnode(struct rib_sub * sub, + struct rnode * node); + +static void rnode_notify_subs(struct rnode * node, + struct rnode * ch, + struct revent * ev) +{ + struct list_head * p; + + assert(node); + + list_for_each(p, &node->subs) { + struct rn_sub * s = list_entry(p, struct rn_sub, next); + if (s->flags & ev->flags) { + struct revent * e = revent_dup(ev); + list_add_tail(&e->next, &s->sub->events); + } + + if (ev->flags & RO_DELETE) + rib_sub_del_rnode(s->sub, ch); + } +} + +static int rnode_throw_event(struct rnode * node, + int32_t flags) +{ + struct revent * ev = malloc(sizeof(*ev)); + struct rnode * rn = node; + + assert(node); + assert(node->path); + + if (ev == NULL) + return -ENOMEM; + + list_head_init(&ev->next); + + ev->path = strdup(node->path); + if (ev->path == NULL) { + free(ev); + return -ENOMEM; + } + + ev->flags = flags; + + do { + rnode_notify_subs(rn, node, ev); + rn = rn->parent; + } while (rn != NULL); + + free(ev->path); + free(ev); + + return 0; +} + +static int rnode_add_child(struct rnode * node, + struct rnode * child) +{ + struct child * c; + + assert(node); + assert(child); + + c = malloc(sizeof(*c)); + if (c == NULL) + return -ENOMEM; + + c->node = child; + list_add(&c->next, &node->children); + + return 0; +} + +static void rnode_remove_child(struct rnode * node, + struct rnode * child) +{ + struct list_head * p; + struct list_head * h; + + assert(node); + assert(child); + + list_for_each_safe(p, h, &node->children) { + struct child * c = list_entry(p, struct child, next); + if (c->node == child) { + list_del(&c->next); + free(c); + return; + } + } +} + +static struct rnode * rnode_create(struct rnode * parent, + const char * name) +{ + struct rnode * node; + char * parent_path; + + assert(name); + + node = malloc(sizeof(*node)); + if (node == NULL) + return NULL; + + list_head_init(&node->children); + list_head_init(&node->subs); + + if (parent == NULL) + parent_path = ""; + else + parent_path = parent->path; + + node->path = malloc(strlen(parent_path) + + strlen(RIB_PATH_DLR) + + strlen(name) + + 1); + if (node->path == NULL) { + free(node); + return NULL; + } + + strcpy(node->path, parent_path); + node->name = node->path + strlen(parent_path); + if (parent != NULL) { + strcpy(node->name, RIB_PATH_DLR); + node->name += strlen(RIB_PATH_DLR); + } + + strcpy(node->name, name); + + if (parent != NULL) { + if (rnode_add_child(parent, node)) { + free(node->path); + free(node); + return NULL; + } + } + + node->data = NULL; + node->len = 0; + + node->parent = parent; + + branch_hash(node); + rnode_throw_event(node, RO_CREATE); + + return node; +} + +static void destroy_rnode(struct rnode * node) +{ + struct list_head * p; + struct list_head * h; + + assert(node); + + if (node != rib.root) { + rnode_remove_child(node->parent, node); + branch_hash(node->parent); + } + + rnode_throw_event(node, RO_DELETE); + + list_for_each_safe(p, h, &node->subs) { + struct rn_sub * s = list_entry(p, struct rn_sub, next); + list_del(&s->next); + free(s); + } + + free(node->path); + if (node->data != NULL) + free(node->data); + + free(node); +} + +static void destroy_rtree(struct rnode * node) +{ + struct list_head * p; + struct list_head * h; + + assert(node); + + list_for_each_safe(p, h, &node->children) { + struct child * c = list_entry(p, struct child, next); + destroy_rtree(c->node); + } + + destroy_rnode(node); +} + +static int rnode_update(struct rnode * node, + uint8_t * data, + size_t len) +{ + assert(node); + assert(!(data == NULL && len != 0)); + assert(!(data != NULL && len == 0)); + + if (node->data != NULL) + free(node->data); + + node->data = data; + node->len = len; + + rnode_throw_event(node, RO_MODIFY); + + branch_hash(node); + + return 0; +} + +static struct rn_sub * rnode_get_sub(struct rnode * node, + struct rib_sub * sub) +{ + struct list_head * p; + + list_for_each(p, &node->subs) { + struct rn_sub * r = list_entry(p, struct rn_sub, next); + if (r->sub == sub) + return r; + } + + return NULL; +} + +static int rnode_add_sub(struct rnode * node, + struct rib_sub * sub, + int32_t flags) +{ + struct rn_sub * rs; + + assert(node); + assert(sub); + + rs = rnode_get_sub(node, sub); + if (rs != NULL) + return -EPERM; + + rs = malloc(sizeof(*rs)); + if (rs == NULL) + return -ENOMEM; + + rs->sub = sub; + rs->flags = flags; + + list_add(&rs->next, &node->subs); + + return 0; +} + +static int rnode_del_sub(struct rnode * node, + struct rib_sub * sub) +{ + struct rn_sub * rs; + + assert(node); + assert(sub); + + rs = rnode_get_sub(node, sub); + if (rs == NULL) + return 0; + + list_del(&rs->next); + free(rs); + + return 0; +} + +static struct rnode * find_rnode_by_path(const char * path) +{ + uint32_t crc = 0; + + if (strcmp(path, RIB_ROOT) == 0) + return rib.root; + + crc32(&crc, path, strlen(path)); + + return (struct rnode *) btree_search(rib.idx, crc); +} + +int rib_init(void) +{ + if (rib.root != NULL) + return -EPERM; + + rib.root = rnode_create(NULL, ""); + if (rib.root == NULL) + return -ENOMEM; + + rib.idx = btree_create(RIB_BTREE_ORDER); + if (rib.idx == NULL) { + destroy_rtree(rib.root); + rib.root = NULL; + return -1; + } + + rib.sids = bmp_create(32, 1); + if (rib.sids == NULL) { + btree_destroy(rib.idx); + destroy_rtree(rib.root); + rib.root = NULL; + return -1; + } + + if (pthread_rwlock_init(&rib.lock, NULL)) { + bmp_destroy(rib.sids); + btree_destroy(rib.idx); + destroy_rtree(rib.root); + rib.root = NULL; + return -1; + } + + if (pthread_rwlock_init(&rib.s_lock, NULL)) { + pthread_rwlock_destroy(&rib.lock); + bmp_destroy(rib.sids); + btree_destroy(rib.idx); + destroy_rtree(rib.root); + rib.root = NULL; + return -1; + } + + list_head_init(&rib.subs); + + assert(rib.root); + + return 0; +} + +void rib_fini(void) +{ + if (rib.root == NULL) + return; + + btree_destroy(rib.idx); + + bmp_destroy(rib.sids); + + destroy_rtree(rib.root); + rib.root = NULL; + + pthread_rwlock_destroy(&rib.lock); +} + +int rib_add(const char * path, + const char * name) +{ + struct rnode * parent; + struct rnode * node; + + uint32_t crc = 0; + + if (name == NULL) + return -EINVAL; + + pthread_rwlock_wrlock(&rib.lock); + + parent = find_rnode_by_path(path); + if (parent == NULL) { + pthread_rwlock_unlock(&rib.lock); + return -EPERM; + } + + node = rnode_create(parent, name); + if (node == NULL) { + pthread_rwlock_unlock(&rib.lock); + return -ENOMEM; + } + + crc32(&crc, node->path, strlen(node->path)); + + btree_insert(rib.idx, crc, node); + + pthread_rwlock_unlock(&rib.lock); + + return 0; +} + +int rib_del(char * path) +{ + struct rnode * node; + uint32_t crc = 0; + + if (path == NULL) + return -EINVAL; + + pthread_rwlock_wrlock(&rib.lock); + + node = find_rnode_by_path(path); + if (node == NULL) { + pthread_rwlock_unlock(&rib.lock); + return -EINVAL; + } + + crc32(&crc, node->path, strlen(node->path)); + + btree_remove(rib.idx, crc); + + destroy_rtree(node); + + pthread_rwlock_unlock(&rib.lock); + + return 0; +} + +ssize_t rib_read(const char * path, + void * data, + size_t len) +{ + struct rnode * node; + ssize_t rlen; + + if (path == NULL || data == NULL) + return -EINVAL; + + pthread_rwlock_rdlock(&rib.lock); + + node = find_rnode_by_path(path); + if (node == NULL) { + pthread_rwlock_unlock(&rib.lock); + return -EPERM; + } + + if (len < node->len) { + pthread_rwlock_unlock(&rib.lock); + return -EFBIG; + } + + memcpy(data, node->data, node->len); + rlen = node->len; + + rnode_throw_event(node, RO_READ); + + pthread_rwlock_unlock(&rib.lock); + + return rlen; +} + +int rib_write(const char * path, + const void * data, + size_t len) +{ + struct rnode * node; + int ret = -1; + + uint8_t * cdata; + + if (path == NULL) + return -EINVAL; + + cdata = malloc(len); + if (cdata == NULL) + return -ENOMEM; + + memcpy(cdata, data, len); + + pthread_rwlock_rdlock(&rib.lock); + + node = find_rnode_by_path(path); + if (node != NULL) + ret = rnode_update(node, cdata, len); + + pthread_rwlock_unlock(&rib.lock); + + return ret; +} + +int rib_put(const char * path, + void * data, + size_t len) +{ + struct rnode * node; + int ret = -1; + + if (path == NULL) + return -EINVAL; + + pthread_rwlock_rdlock(&rib.lock); + + node = find_rnode_by_path(path); + if (node != NULL) + ret = rnode_update(node, (uint8_t *) data, len); + + pthread_rwlock_unlock(&rib.lock); + + return ret; +} + +bool rib_has(const char * path) +{ + struct rnode * node; + + assert(path); + + pthread_rwlock_rdlock(&rib.lock); + + node = find_rnode_by_path(path); + + pthread_rwlock_unlock(&rib.lock); + + return node != NULL; +} + +static struct rib_sub * rib_get_sub(uint32_t sid) +{ + struct list_head * p; + struct list_head * h; + + list_for_each_safe(p, h, &rib.subs) { + struct rib_sub * r = list_entry(p, struct rib_sub, next); + if (r->sid == sid) + return r; + } + + return 0; +} + +static struct rib_sub * rib_sub_create(uint32_t sid) +{ + struct rib_sub * sub = malloc(sizeof(*sub)); + if (sub == NULL) + return NULL; + + if (pthread_cond_init(&sub->cond, NULL)) { + free(sub); + return NULL; + } + + if (pthread_mutex_init(&sub->lock, NULL)) { + pthread_cond_destroy(&sub->cond); + free(sub); + return NULL; + } + + list_head_init(&sub->rnodes); + list_head_init(&sub->events); + + sub->sid = sid; + + return sub; +} + +static void rib_sub_zero(struct rib_sub * sub) +{ + struct list_head * p; + struct list_head * h; + + assert(sub); + + list_for_each_safe(p, h, &sub->rnodes) { + struct rn_ptr * r = list_entry(p, struct rn_ptr, next); + assert(r->node); + rnode_del_sub(r->node, sub); + list_del(&r->next); + free(r); + } + + list_for_each_safe(p, h, &sub->events) { + struct revent * r = list_entry(p, struct revent, next); + list_del(&r->next); + assert(r->path); + free(r->path); + free(r); + } +} + +static struct rn_ptr * rib_sub_get_rn_ptr(struct rib_sub * sub, + struct rnode * node) +{ + struct list_head * p; + + list_for_each(p, &sub->rnodes) { + struct rn_ptr * r = list_entry(p, struct rn_ptr, next); + assert(r->node); + if (r->node == node) + return r; + } + + return NULL; +} + +static int rib_sub_add_rnode(struct rib_sub * sub, + struct rnode * node) +{ + struct rn_ptr * rn; + + assert(sub); + assert(node); + + if (rib_sub_get_rn_ptr(sub, node) != NULL) + return 0; + + rn = malloc(sizeof(*rn)); + if (rn == NULL) + return -ENOMEM; + + rn->node = node; + + list_add(&rn->next, &sub->rnodes); + + return 0; +} + +static void rib_sub_del_rnode(struct rib_sub * sub, + struct rnode * node) +{ + struct rn_ptr * rn; + + assert(sub); + assert(node); + + rn = rib_sub_get_rn_ptr(sub, node); + if (rn == NULL) + return; + + list_del(&rn->next); + + free(rn); +} + +static void rib_sub_destroy(struct rib_sub * sub) +{ + assert(sub); + + rib_sub_zero(sub); + + free(sub); +} + +/* Event calls from rqueue.h. */ +ro_set_t * ro_set_create(void) +{ + ro_set_t * set; + struct rib_sub * sub; + + set = malloc(sizeof(*set)); + if (set == NULL) + return NULL; + + pthread_rwlock_wrlock(&rib.s_lock); + + set->sid = bmp_allocate(rib.sids); + if (!bmp_is_id_valid(rib.sids, set->sid)) { + pthread_rwlock_unlock(&rib.s_lock); + free(set); + return NULL; + } + + pthread_rwlock_unlock(&rib.s_lock); + + pthread_rwlock_wrlock(&rib.lock); + + sub = rib_sub_create(set->sid); + if (sub == NULL) { + pthread_rwlock_unlock(&rib.lock); + free(set); + return NULL; + } + + list_add(&sub->next, &rib.subs); + + pthread_rwlock_unlock(&rib.lock); + + return set; +} + +void ro_set_destroy(ro_set_t * set) +{ + struct rib_sub * sub = NULL; + + struct list_head * p; + struct list_head * h; + + pthread_rwlock_wrlock(&rib.lock); + + list_for_each_safe(p, h, &rib.subs) { + struct rib_sub * r = list_entry(p, struct rib_sub, next); + if (r->sid == set->sid) { + sub = r; + break; + } + } + + if (sub != NULL) + rib_sub_destroy(sub); + + pthread_rwlock_unlock(&rib.lock); + + pthread_rwlock_wrlock(&rib.s_lock); + + bmp_release(rib.sids, set->sid); + + pthread_rwlock_unlock(&rib.s_lock); + + free(set); +} + +rqueue_t * rqueue_create(void) +{ + rqueue_t * rq = malloc(sizeof(*rq)); + if (rq == NULL) + return NULL; + + list_head_init(&rq->events); + + return rq; +} + +int rqueue_destroy(struct rqueue * rq) +{ + struct list_head * p; + struct list_head * h; + + list_for_each_safe(p, h, &rq->events) { + struct revent * e = list_entry(p, struct revent, next); + list_del(&e->next); + free(e->path); + free(e); + } + + free(rq); + + return 0; +} + +int ro_set_zero(ro_set_t * set) +{ + struct rib_sub * sub; + + if (set == NULL) + return -EINVAL; + + pthread_rwlock_wrlock(&rib.lock); + + sub = rib_get_sub(set->sid); + + assert(sub); + + rib_sub_zero(sub); + + pthread_rwlock_unlock(&rib.lock); + + return 0; +} + +int ro_set_add(ro_set_t * set, + const char * path, + int32_t flags) +{ + struct rib_sub * sub; + struct rnode * node; + + if (set == NULL) + return -EINVAL; + + pthread_rwlock_wrlock(&rib.lock); + + sub = rib_get_sub(set->sid); + + assert(sub); + + node = find_rnode_by_path(path); + if (node == NULL) { + pthread_rwlock_unlock(&rib.lock); + return -1; + } + + if (rnode_add_sub(node, sub, flags)) { + pthread_rwlock_unlock(&rib.lock); + return -ENOMEM; + } + + if (rib_sub_add_rnode(sub, node)) { + pthread_rwlock_unlock(&rib.lock); + return -ENOMEM; + } + + pthread_rwlock_unlock(&rib.lock); + + return 0; +} + +int ro_set_del(ro_set_t * set, + const char * path) +{ + struct rib_sub * sub; + struct rnode * node; + + if (set == NULL) + return -EINVAL; + + pthread_rwlock_wrlock(&rib.lock); + + sub = rib_get_sub(set->sid); + + assert(sub); + + node = find_rnode_by_path(path); + if (node == NULL) { + pthread_rwlock_unlock(&rib.lock); + return -1; + } + + rnode_del_sub(node, sub); + + rib_sub_del_rnode(sub, node); + + pthread_rwlock_unlock(&rib.lock); + + return 0; +} + +int32_t rqueue_next(rqueue_t * rq, + char * path) +{ + struct revent * ev; + int32_t ret; + + if (list_is_empty(&rq->events)) + return -1; + + ev = list_first_entry(&rq->events, struct revent, next); + list_del(&ev->next); + + strcpy(path, ev->path); + ret = ev->flags; + + free(ev->path); + free(ev); + + return ret; +} + +int rib_event_wait(ro_set_t * set, + rqueue_t * rq, + const struct timespec * timeout) +{ + struct rib_sub * sub; + struct timespec abstime; + + ssize_t ret = 0; + + if (set == NULL || rq == NULL) + return -EINVAL; + + if (!list_is_empty(&rq->events)) + return 0; + + if (timeout != NULL) { + clock_gettime(PTHREAD_COND_CLOCK, &abstime); + ts_add(&abstime, timeout, &abstime); + } + + pthread_rwlock_rdlock(&rib.lock); + + sub = rib_get_sub(set->sid); + + pthread_rwlock_unlock(&rib.lock); + + pthread_mutex_lock(&sub->lock); + + while (list_is_empty(&sub->events) && ret != -ETIMEDOUT) { + if (timeout != NULL) + ret = -pthread_cond_timedwait(&sub->cond , + &sub->lock, + &abstime); + else + ret = -pthread_cond_wait(&sub->cond, &sub->lock); + } + + pthread_mutex_unlock(&sub->lock); + + pthread_rwlock_wrlock(&rib.lock); + + if (ret != -ETIMEDOUT) + list_move(&rq->events, &sub->events); + + pthread_rwlock_wrlock(&rib.lock); + + return ret; +} + +/* Path name management. */ +char * rib_path_append(char * path, + const char * name) +{ + char * pos; + + if (path == NULL || name == NULL || strstr(name, RIB_PATH_DLR)) + return NULL; + + pos = path + strlen(path); + memcpy(pos++, RIB_PATH_DLR, 1); + strcpy(pos, name); + + return path; +} + +char * rib_name_gen(void * data, + size_t len) +{ + uint32_t crc = 0; + char * name; + + if (data == NULL || len == 0) + return NULL; + + name= malloc(GEN_NAME_SIZE + 1); + if (name == NULL) + return NULL; + + crc32(&crc, data, len); + + sprintf(name, "%08x", crc); + + return name; +} diff --git a/src/lib/tests/CMakeLists.txt b/src/lib/tests/CMakeLists.txt index 72455aa2..e4ea3920 100644 --- a/src/lib/tests/CMakeLists.txt +++ b/src/lib/tests/CMakeLists.txt @@ -7,6 +7,7 @@ create_test_sourcelist(${PARENT_DIR}_tests test_suite.c btree_test.c crc32_test.c hashtable_test.c + rib_test.c sha3_test.c ) diff --git a/src/lib/tests/rib_test.c b/src/lib/tests/rib_test.c new file mode 100644 index 00000000..37503941 --- /dev/null +++ b/src/lib/tests/rib_test.c @@ -0,0 +1,222 @@ +/* + * Ouroboros - Copyright (C) 2016 - 2017 + * + * Test of the RIB + * + * Dimitri Staessens + * + * This program is free software; you can redistribute it and/or modify + * it under the terms of the GNU General Public License version 2 as + * published by the Free Software Foundation. + * + * This program is distributed in the hope that it will be useful, + * but WITHOUT ANY WARRANTY; without even the implied warranty of + * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the + * GNU General Public License for more details. + * + * You should have received a copy of the GNU General Public License + * along with this program; if not, write to the Free Software + * Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA. + */ + +#include +#include +#include +#include +#include + +#include +#include +#include + +int rib_test(int argc, + char ** argv) +{ + uint64_t * address; + + size_t addr_size = 8; + size_t addr_chk; + + char * addr_name; + + ro_set_t * set; + rqueue_t * rq; + + int ret; + + char tmp[RIB_MAX_PATH_LEN]; + + struct timespec t = {0, 100 * BILLION}; + + (void) argc; + (void) argv; + + address = malloc(sizeof(*address)); + if (address == NULL) + return -ENOMEM; + + if (rib_init()) { + printf("Failed to initialize rib.\n"); + return -1; + } + + rib_fini(); + + if (rib_init()) { + printf("Failed to re-initialize rib.\n"); + return -1; + } + + if (rib_add(RIB_ROOT, "static_info")) { + printf("Failed to add element to rib.\n"); + rib_fini(); + return -1; + } + + if (!rib_has("/static_info")) { + printf("Failed to find added element.\n"); + rib_fini(); + return -1; + } + + if (rib_add(RIB_ROOT, "dynamic_info")) { + printf("Failed to add element to rib.\n"); + rib_fini(); + return -1; + } + + if (rib_add("/static_info", "addr_size")) { + printf("Failed to add sub-element to rib.\n"); + rib_fini(); + return -1; + } + + if (rib_write("/static_info/addr_size", + &addr_size, sizeof(addr_size))) { + printf("Failed to add sub-element to rib.\n"); + rib_fini(); + return -1; + } + + if (rib_add("/static_info", "addresses")) { + printf("Failed to add sub-element to rib.\n"); + rib_fini(); + return -1; + } + + if (!rib_has("/static_info/addr_size")) { + printf("Failed to find added subelement.\n"); + rib_fini(); + return -1; + } + + if (rib_read("/static_info/addr_size", + &addr_chk, sizeof(addr_chk)) + != sizeof(addr_chk)) { + printf("Failed to read added element.\n"); + rib_fini(); + return -1; + } + + if (addr_chk != addr_size) { + printf("Failed to verify added element contents.\n"); + rib_fini(); + return -1; + } + + addr_size = 16; + + if (rib_write("/static_info/addr_size", + &addr_size, sizeof(addr_size))) { + printf("Failed to write into added element.\n"); + rib_fini(); + return -1; + } + + if (rib_read("/static_info/addr_size", + &addr_chk, sizeof(addr_chk)) + != sizeof(addr_chk)) { + printf("Failed to verify added element update size.\n"); + rib_fini(); + return -1; + } + + if (addr_chk != addr_size) { + printf("Failed to verify added element update size.\n"); + rib_fini(); + return -1; + } + + addr_name = rib_name_gen(address, sizeof(*address)); + if (addr_name == NULL) { + printf("Failed to create a name.\n"); + rib_fini(); + return -1; + } + + strcpy(tmp, "/dynamic_info"); + + if (rib_add(tmp, addr_name)) { + free(addr_name); + printf("Failed to add address.\n"); + rib_fini(); + return -1; + } + + rib_path_append(tmp, addr_name); + + if (rib_put(tmp, address, sizeof(*address))) { + free(addr_name); + printf("Failed to add address.\n"); + rib_fini(); + return -1; + } + + free(addr_name); + + set = ro_set_create(); + if (set == NULL) { + printf("Failed to create ro_set.\n"); + rib_fini(); + return -1; + } + + rq = rqueue_create(); + if (rq == NULL) { + printf("Failed to create rqueue.\n"); + ro_set_destroy(set); + rib_fini(); + return -1; + } + + if (ro_set_add(set, "/static_info", RO_ALL_OPS)) { + printf("Failed to add to rqueue.\n"); + ro_set_destroy(set); + rqueue_destroy(rq); + rib_fini(); + return -1; + } + + ret = rib_event_wait(set, rq, &t); + if (ret != -ETIMEDOUT) { + printf("Wait failed to timeout: %d.\n", ret); + ro_set_destroy(set); + rqueue_destroy(rq); + rib_fini(); + return -1; + } + + if (rib_del("/static_info")) { + printf("Failed to delete rib subtree.\n"); + rib_fini(); + return -1; + } + + ro_set_destroy(set); + + rqueue_destroy(rq); + + rib_fini(); + + return 0; +} -- cgit v1.2.3