summaryrefslogtreecommitdiff
diff options
context:
space:
mode:
-rw-r--r--include/ouroboros/config.h.in1
-rw-r--r--include/ouroboros/fqueue.h2
-rw-r--r--include/ouroboros/list.h3
-rw-r--r--include/ouroboros/rib.h61
-rw-r--r--include/ouroboros/rqueue.h72
-rw-r--r--src/lib/CMakeLists.txt1
-rw-r--r--src/lib/dev.c2
-rw-r--r--src/lib/list.c11
-rw-r--r--src/lib/rib.c1097
-rw-r--r--src/lib/tests/CMakeLists.txt1
-rw-r--r--src/lib/tests/rib_test.c222
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;
+}