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.

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;
+}