Merged in dstaesse/ouroboros/be-rib (pull request #350)

Be rib

11 files changed, 1471 insertions, 2 deletions

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/fqueue.h b/include/ouroboros/fqueue.h
index d34665d6..254648e6 100644
--- a/include/ouroboros/fqueue.h
+++ b/include/ouroboros/fqueue.h
@@ -59,4 +59,4 @@ int          flow_event_wait(flow_set_t *            set,
                              fqueue_t *              fq,
                              const struct timespec * timeout);
 
-#endif /* OUROBOROS_SELECT_H */
+#endif /* OUROBOROS_FQUEUE_H */
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/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   <sander.vrijders@intec.ugent.be>
+ *    Dimitri Staessens <dimitri.staessens@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
+ */
+
+#ifndef OUROBOROS_LIB_RIB_H
+#define OUROBOROS_LIB_RIB_H
+
+#include <sys/types.h>
+#include <stdbool.h>
+
+#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 <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
+ */
+
+#ifndef OUROBOROS_RQUEUE_H
+#define OUROBOROS_RQUEUE_H
+
+#include <stdbool.h>
+#include <stdint.h>
+#include <time.h>
+
+#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/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);
 
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);
+}
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;
+}