From 988355d5bb62405f3bd3fbaade1f26ba4b2c274e Mon Sep 17 00:00:00 2001 From: dimitri staessens Date: Tue, 31 Jan 2017 19:55:59 +0100 Subject: 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. --- include/ouroboros/rib.h | 54 +++++---- src/lib/CMakeLists.txt | 3 +- src/lib/rib.c | 281 ++++++++++++++++++++++++++++++++++++++++++----- src/lib/ro.proto | 32 ++++++ src/lib/tests/rib_test.c | 39 +++++++ 5 files changed, 359 insertions(+), 50 deletions(-) create mode 100644 src/lib/ro.proto diff --git a/include/ouroboros/rib.h b/include/ouroboros/rib.h index 1d0661a7..50747498 100644 --- a/include/ouroboros/rib.h +++ b/include/ouroboros/rib.h @@ -25,40 +25,54 @@ #define OUROBOROS_LIB_RIB_H #include +#include #include #define RIB_ROOT "" -int rib_init(void); +#define PACK_HASH_ROOT 0x0001 +#define PACK_HASH_ALL 0x0002 -void rib_fini(void); +#define UNPACK_CREATE 0x0001 -int rib_add(const char * parent, - const char * name); +int rib_init(void); -int rib_del(char * path); +void rib_fini(void); -ssize_t rib_read(const char * path, - void * data, - size_t len); +int rib_add(const char * parent, + const char * name); -int rib_write(const char * path, - const void * data, +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); -int rib_put(const char * path, - void * data, - size_t len); +bool rib_has(const char * path); + +ssize_t rib_children(const char * path, + char *** children); -bool rib_has(const char * path); +char * rib_path_append(char * path, + const char * name); -ssize_t rib_children(const char * path, - char *** children); +char * rib_name_gen(void * data, + size_t len); -char * rib_path_append(char * path, - const char * name); +ssize_t rib_pack(const char * path, + uint8_t ** buf, + uint32_t flags); -char * rib_name_gen(void * data, - size_t len); +int rib_unpack(uint8_t * packed, + size_t len, + uint32_t flags); #endif /* OUROBOROS_LIB_RIB_H */ 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 #include #include @@ -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 + * Sander Vrijders + * + * 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"); -- cgit v1.2.3