lib: Add packing and unpacking RIB

The rib_pack function allows packing a subtree of the RIB for
dissemination. The options PACK_HASH_ROOT and PACK_HASH_ALL will add
the hashes for the root object of the packed subtree or every object
to the packed message respectively. Checking of the hashes is
currently only performed at the top level object, verifying the
complete operation.

The rib_unpack function unpacks a packed message and inserts its
contents in the RIB. The option UNPACK_CREATE flags that the unpack
operation is allowed to create new objects, else it will only update
existing objects. More advanced options could be added in the future.

The packed message structure uses Google Protocol Buffers, as defined
in ro.proto.

It adds tests for these functions to the rib_test.

4 files changed, 325 insertions, 30 deletions

diff --git a/src/lib/CMakeLists.txt b/src/lib/CMakeLists.txt
index 6959a820..6af50782 100644
--- a/src/lib/CMakeLists.txt
+++ b/src/lib/CMakeLists.txt
@@ -10,6 +10,7 @@ protobuf_generate_c(DIF_CONFIG_PROTO_SRCS DIF_CONFIG_PROTO_HDRS
   dif_config.proto)
 protobuf_generate_c(CDAP_PROTO_SRCS CDAP_PROTO_HDRS cdap.proto)
 protobuf_generate_c(CACEP_PROTO_SRCS CACEP_PROTO_HDRS cacep.proto)
+protobuf_generate_c(RO_PROTO_SRCS RO_PROTO_HDRS ro.proto)
 
 if(NOT APPLE)
   find_library(LIBRT_LIBRARIES rt)
@@ -52,7 +53,7 @@ set(SOURCE_FILES
 
 add_library(ouroboros SHARED ${SOURCE_FILES} ${IRM_PROTO_SRCS}
   ${IPCP_PROTO_SRCS} ${DIF_CONFIG_PROTO_SRCS}
-  ${CDAP_PROTO_SRCS} ${CACEP_PROTO_SRCS})
+  ${CDAP_PROTO_SRCS} ${CACEP_PROTO_SRCS} ${RO_PROTO_SRCS})
 
 target_link_libraries(ouroboros ${LIBRT_LIBRARIES}
   ${LIBPTHREAD_LIBRARIES} ${PROTOBUF_C_LIBRARY})
diff --git a/src/lib/rib.c b/src/lib/rib.c
index 6b27ad27..3839849c 100644
--- a/src/lib/rib.c
+++ b/src/lib/rib.c
@@ -33,6 +33,9 @@
 #include "sha3.h"
 #include "btree.h"
 
+#include "ro.pb-c.h"
+typedef RoMsg ro_msg_t;
+
 #include <pthread.h>
 #include <string.h>
 #include <assert.h>
@@ -238,6 +241,8 @@ static int rnode_add_child(struct rnode * node,
                            struct rnode * child)
 {
         struct child * c;
+        struct list_head * p;
+        struct child * n;
 
         assert(node);
         assert(child);
@@ -247,7 +252,14 @@ static int rnode_add_child(struct rnode * node,
                 return -ENOMEM;
 
         c->node = child;
-        list_add(&c->next, &node->children);
+
+        list_for_each(p, &node->children) {
+                n = list_entry(p, struct child, next);
+                if (strcmp(n->node->name, child->name) > 0)
+                        break;
+        }
+
+        list_add(&c->next, p);
 
         ++node->chlen;
 
@@ -280,6 +292,8 @@ static struct rnode * rnode_create(struct rnode *  parent,
         struct rnode * node;
         char * parent_path;
 
+        uint32_t crc = 0;
+
         assert(name);
 
         node = malloc(sizeof(*node));
@@ -327,6 +341,9 @@ static struct rnode * rnode_create(struct rnode *  parent,
 
         node->chlen = 0;
 
+        crc32(&crc, node->path, strlen(node->path));
+        btree_insert(rib.idx, crc, node);
+
         branch_hash(node);
         rnode_throw_event(node, RO_CREATE);
 
@@ -338,6 +355,8 @@ static void destroy_rnode(struct rnode * node)
         struct list_head * p;
         struct list_head * h;
 
+        uint32_t crc = 0;
+
         assert(node);
 
         if (node != rib.root) {
@@ -353,6 +372,9 @@ static void destroy_rnode(struct rnode * node)
                 free(s);
         }
 
+        crc32(&crc, node->path, strlen(node->path));
+        btree_remove(rib.idx, crc);
+
         free(node->path);
         if (node->data != NULL)
                 free(node->data);
@@ -375,9 +397,9 @@ static void destroy_rtree(struct rnode * node)
         destroy_rnode(node);
 }
 
-static int rnode_update(struct rnode *  node,
-                        uint8_t *       data,
-                        size_t          len)
+static void rnode_update(struct rnode *  node,
+                         uint8_t *       data,
+                         size_t          len)
 {
         assert(node);
         assert(!(data == NULL && len != 0));
@@ -392,8 +414,6 @@ static int rnode_update(struct rnode *  node,
         rnode_throw_event(node, RO_MODIFY);
 
         branch_hash(node);
-
-        return 0;
 }
 
 static struct rn_sub * rnode_get_sub(struct rnode *   node,
@@ -470,10 +490,6 @@ 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);
@@ -481,6 +497,10 @@ int rib_init(void)
                 return -1;
         }
 
+        rib.root = rnode_create(NULL, "");
+        if (rib.root == NULL)
+                return -ENOMEM;
+
         rib.sids = bmp_create(32, 1);
         if (rib.sids == NULL) {
                 btree_destroy(rib.idx);
@@ -518,13 +538,13 @@ void rib_fini(void)
         if (rib.root == NULL)
                 return;
 
-        btree_destroy(rib.idx);
-
         bmp_destroy(rib.sids);
 
         destroy_rtree(rib.root);
         rib.root = NULL;
 
+        btree_destroy(rib.idx);
+
         pthread_rwlock_destroy(&rib.lock);
 }
 
@@ -534,8 +554,6 @@ int rib_add(const char * path,
         struct rnode * parent;
         struct rnode * node;
 
-        uint32_t crc = 0;
-
         if (name == NULL)
                 return -EINVAL;
 
@@ -553,10 +571,6 @@ int rib_add(const char * path,
                 return -ENOMEM;
         }
 
-        crc32(&crc, node->path, strlen(node->path));
-
-        btree_insert(rib.idx, crc, node);
-
         pthread_rwlock_unlock(&rib.lock);
 
         return 0;
@@ -565,7 +579,6 @@ int rib_add(const char * path,
 int rib_del(char * path)
 {
         struct rnode * node;
-        uint32_t crc = 0;
 
         if (path == NULL)
                 return -EINVAL;
@@ -578,10 +591,6 @@ int rib_del(char * path)
                 return -EINVAL;
         }
 
-        crc32(&crc, node->path, strlen(node->path));
-
-        btree_remove(rib.idx, crc);
-
         destroy_rtree(node);
 
         pthread_rwlock_unlock(&rib.lock);
@@ -634,7 +643,6 @@ int rib_write(const char * path,
               size_t       len)
 {
         struct rnode * node;
-        int            ret = -1;
 
         uint8_t * cdata;
 
@@ -651,11 +659,11 @@ int rib_write(const char * path,
 
         node = find_rnode_by_path(path);
         if (node != NULL)
-                ret = rnode_update(node, cdata, len);
+                rnode_update(node, cdata, len);
 
         pthread_rwlock_unlock(&rib.lock);
 
-        return ret;
+        return 0;
 }
 
 int rib_put(const char * path,
@@ -663,7 +671,6 @@ int rib_put(const char * path,
             size_t       len)
 {
         struct rnode * node;
-        int            ret = -1;
 
         if (path == NULL)
                 return -EINVAL;
@@ -672,11 +679,11 @@ int rib_put(const char * path,
 
         node = find_rnode_by_path(path);
         if (node != NULL)
-                ret = rnode_update(node, (uint8_t *) data, len);
+                rnode_update(node, (uint8_t *) data, len);
 
         pthread_rwlock_unlock(&rib.lock);
 
-        return ret;
+        return 0;
 }
 
 bool rib_has(const char * path)
@@ -1162,3 +1169,219 @@ char * rib_name_gen(void *       data,
 
         return name;
 }
+
+static ro_msg_t * rnode_pack(struct rnode * node,
+                             uint32_t       flags,
+                             bool           root)
+{
+        ro_msg_t * msg;
+
+        assert(node);
+
+        if (node->parent == NULL)
+                return NULL;
+
+        msg = malloc(sizeof(*msg));
+        if (msg == NULL)
+                return NULL;
+
+        ro_msg__init(msg);
+
+        msg->name = node->name;
+        if (root) {
+                assert(node->parent->path);
+                msg->parent = node->parent->path;
+        }
+
+        if ((root && (flags & PACK_HASH_ROOT)) ||
+            (flags & PACK_HASH_ALL)) {
+                msg->has_hash  = true;
+                msg->hash.data = node->sha3;
+                msg->hash.len  = sha3_256_hash_size;
+        }
+
+        if (node->data != NULL) {
+                msg->has_data  = true;
+                msg->data.data = node->data;
+                msg->data.len  = node->len;
+        }
+
+        if (node->chlen > 0) {
+                int n = 0;
+                struct list_head * p;
+                ro_msg_t ** msgs = malloc(sizeof(*msgs) * node->chlen);
+                if (msgs == NULL) {
+                        free(msg);
+                        return NULL;
+                }
+
+                msg->n_children = node->chlen;
+                list_for_each(p, &node->children) {
+                        struct child * c = list_entry(p, struct child, next);
+                        msgs[n] = rnode_pack(c->node, flags, false);
+                        if (msgs[n++] == NULL) {
+                                int i;
+                                for (i = 0; i < n; ++i)
+                                        free(msgs[i]);
+                                free(msgs);
+                                free(msg);
+                                return NULL;
+                        }
+                }
+                msg->children = msgs;
+        }
+
+        return msg;
+}
+
+static void free_ro_msg(ro_msg_t * msg)
+{
+        size_t n = 0;
+        while (n < msg->n_children)
+                free_ro_msg(msg->children[n++]);
+
+        free(msg->children);
+        free(msg);
+}
+
+ssize_t rib_pack(const char *   path,
+                 uint8_t **     buf,
+                 uint32_t       flags)
+{
+        struct rnode * node;
+        ro_msg_t * msg;
+        ssize_t len;
+
+        if (path == NULL)
+                return -EINVAL;
+
+        pthread_rwlock_rdlock(&rib.lock);
+
+        node = find_rnode_by_path(path);
+        if (node == NULL) {
+                pthread_rwlock_unlock(&rib.lock);
+                return -EPERM;
+        }
+
+        msg = rnode_pack(node, flags, true);
+
+        pthread_rwlock_unlock(&rib.lock);
+
+        if (msg == NULL) {
+                free_ro_msg(msg);
+                return -EPERM;
+        }
+
+        len = ro_msg__get_packed_size(msg);
+        if (len == 0) {
+                free_ro_msg(msg);
+                return 0;
+        }
+
+        *buf = malloc(len);
+        if (*buf == NULL) {
+                free_ro_msg(msg);
+                return -ENOMEM;
+        }
+
+        ro_msg__pack(msg, *buf);
+
+        free_ro_msg(msg);
+
+        return len;
+}
+
+static struct rnode * rnode_get_child(struct rnode * node,
+                                      const char *   name)
+{
+        struct list_head * p;
+
+        list_for_each(p, &node->children) {
+                struct child * c = list_entry(p, struct child, next);
+                if (strcmp(c->node->name, name) == 0)
+                        return c->node;
+        }
+
+        return NULL;
+}
+
+static int rnode_unpack(ro_msg_t *     msg,
+                        struct rnode * parent,
+                        uint32_t       flags)
+{
+        struct rnode * node;
+
+        size_t i;
+
+        assert(msg);
+        assert(parent);
+
+        node = rnode_get_child(parent, msg->name);
+        if (node == NULL) {
+                if (flags & UNPACK_CREATE)
+                        node = rnode_create(parent, msg->name);
+                else
+                        return -EPERM;
+        }
+
+        if (node == NULL)
+                return -ENOMEM;
+
+        /* Unpack in reverse order for faster insertion */
+        i = msg->n_children;
+        while (i > 0)
+                rnode_unpack(msg->children[--i], node, flags);
+
+        if (msg->has_data) {
+                uint8_t * data = malloc(msg->data.len);
+                if (data == NULL)
+                        return -ENOMEM;
+
+                memcpy(data, msg->data.data, msg->data.len);
+                rnode_update(node, data, msg->data.len);
+        }
+
+        return 0;
+}
+
+int rib_unpack(uint8_t * packed,
+               size_t    len,
+               uint32_t  flags)
+{
+        ro_msg_t * msg;
+        struct rnode * root;
+        int ret;
+
+        if (packed == NULL)
+                return -EINVAL;
+
+        msg = ro_msg__unpack(NULL, len, packed);
+        if (msg == NULL)
+                return -EPERM;
+
+        assert(msg->parent);
+
+        pthread_rwlock_wrlock(&rib.lock);
+
+        root = find_rnode_by_path(msg->parent);
+        if (root == NULL) {
+                pthread_rwlock_unlock(&rib.lock);
+                return -EPERM;
+        }
+
+        ret = rnode_unpack(msg, root, flags);
+
+        pthread_rwlock_unlock(&rib.lock);
+
+        if (ret == 0 && msg->has_hash) {
+                root = rnode_get_child(root, msg->name);
+                if (memcmp(msg->hash.data, root->sha3, sha3_256_hash_size))
+                        ret = -EFAULT;
+        }
+
+        ro_msg__free_unpacked(msg, NULL);
+
+        free(packed);
+
+        return ret;
+}
diff --git a/src/lib/ro.proto b/src/lib/ro.proto
new file mode 100644
index 00000000..379ccd27
--- /dev/null
+++ b/src/lib/ro.proto
@@ -0,0 +1,32 @@
+/*
+ * Ouroboros - Copyright (C) 2016 - 2017
+ *
+ * RIB object message
+ *
+ *    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
+ */
+
+syntax = "proto2";
+
+message ro_msg {
+        required string name     = 1;
+        optional string parent   = 2;
+        optional bytes  data     = 3;
+        optional bytes  hash     = 4;
+        repeated ro_msg children = 5;
+}
\ No newline at end of file
diff --git a/src/lib/tests/rib_test.c b/src/lib/tests/rib_test.c
index bad01083..efc35d63 100644
--- a/src/lib/tests/rib_test.c
+++ b/src/lib/tests/rib_test.c
@@ -49,6 +49,9 @@ int rib_test(int     argc,
         char ** kids;
         ssize_t ch;
 
+        uint8_t * buf;
+        ssize_t   buf_len;
+
         struct timespec t = {0, 100 * BILLION};
 
         (void) argc;
@@ -198,6 +201,42 @@ int rib_test(int     argc,
 
         free(addr_name);
 
+        buf_len = rib_pack("/static_info", &buf, PACK_HASH_ALL);
+        if (buf_len < 0) {
+                printf("Failed pack.\n");
+                rib_fini();
+                return -1;
+        }
+
+        if (rib_del("/static_info")) {
+                printf("Failed to delete.\n");
+                rib_fini();
+                return -1;
+        }
+
+        if (rib_unpack(buf, buf_len, UNPACK_CREATE)) {
+                printf("Failed to unpack.\n");
+                rib_fini();
+                return -1;
+        }
+
+        if (!rib_has("/static_info")) {
+                printf("Failed to find unpacked element.\n");
+                rib_fini();
+                return -1;
+        }
+
+        ch = rib_children("/static_info", &kids);
+        if (ch != 2) {
+                printf("Wrong number of children returned.\n");
+                rib_fini();
+                return -1;
+        }
+
+        while (ch > 0)
+                free(kids[--ch]);
+        free(kids);
+
         set = ro_set_create();
         if (set == NULL) {
                 printf("Failed to create ro_set.\n");