summaryrefslogtreecommitdiff
path: root/src/lib
diff options
context:
space:
mode:
authordimitri staessens <dimitri.staessens@intec.ugent.be>2017-01-20 12:59:17 +0100
committerdimitri staessens <dimitri.staessens@intec.ugent.be>2017-01-21 09:55:10 +0100
commit9c92dd66d5e7fab3a3e243abbad9a20b29891fee (patch)
tree819ed39b4cb7b1dd2fb82f62f516bb9fd24e8432 /src/lib
parent82d947a8321737108f545a25f91d7d50d10e831d (diff)
downloadouroboros-9c92dd66d5e7fab3a3e243abbad9a20b29891fee.tar.gz
ouroboros-9c92dd66d5e7fab3a3e243abbad9a20b29891fee.zip
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.
Diffstat (limited to 'src/lib')
-rw-r--r--src/lib/CMakeLists.txt1
-rw-r--r--src/lib/rib.c1097
-rw-r--r--src/lib/tests/CMakeLists.txt1
-rw-r--r--src/lib/tests/rib_test.c222
4 files changed, 1321 insertions, 0 deletions
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 <dimitri.staessens@intec.ugent.be>
+ * Sander Vrijders <sander.vrijders@intec.ugent.be>
+ *
+ * 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 <ouroboros/config.h>
+#include <ouroboros/errno.h>
+#include <ouroboros/list.h>
+#include <ouroboros/rib.h>
+#include <ouroboros/rqueue.h>
+#include <ouroboros/bitmap.h>
+#include <ouroboros/crc32.h>
+#include <ouroboros/time_utils.h>
+
+#include "sha3.h"
+#include "btree.h"
+
+#include <pthread.h>
+#include <string.h>
+#include <assert.h>
+#include <stdlib.h>
+#include <stdio.h>
+
+#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 <dimitri.staessens@intec.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., 675 Mass Ave, Cambridge, MA 02139, USA.
+ */
+
+#include <ouroboros/config.h>
+#include <ouroboros/time_utils.h>
+#include <ouroboros/rib.h>
+#include <ouroboros/rqueue.h>
+#include <ouroboros/errno.h>
+
+#include <stdio.h>
+#include <stdlib.h>
+#include <string.h>
+
+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;
+}