object_rb_tree is a red black tree which is used to de-duplicate oid. So that objects with the same oid in the cluster will be read only once when doing cluster snapshot.
When user sends cluster snapshot command, collie will: 1. parse vdis 2. save readonly object's id into object_rb_tree, duplicate id will be saved only once 3. for each oid in object_rb_tree, read the object and save to farm object_rb_tree has 5 public interfaces: 1. get_obj_nr() returns current object number in the tree 2. obj_tree_insert() insert a object id into the tree 3. free_obj_tree() free memory 4. print_obj_tree() print each node of tree for debug 5. parse_obj() foreach node in the tree, read object from cluster and call the function. just like parse_vdi() in common.c Signed-off-by: Kai Zhang <[email protected]> --- collie/Makefile.am | 3 +- collie/farm/farm.h | 38 +++++++++++ collie/farm/object_rb_tree.c | 148 ++++++++++++++++++++++++++++++++++++++++++ 3 files changed, 188 insertions(+), 1 deletions(-) create mode 100644 collie/farm/farm.h create mode 100644 collie/farm/object_rb_tree.c diff --git a/collie/Makefile.am b/collie/Makefile.am index 3fba2dd..7922c68 100644 --- a/collie/Makefile.am +++ b/collie/Makefile.am @@ -23,7 +23,8 @@ INCLUDES = -I$(top_builddir)/include -I$(top_srcdir)/include sbin_PROGRAMS = collie -collie_SOURCES = collie.c common.c treeview.c vdi.c node.c cluster.c +collie_SOURCES = farm/object_rb_tree.c \ + collie.c common.c treeview.c vdi.c node.c cluster.c if BUILD_TRACE collie_SOURCES += debug.c diff --git a/collie/farm/farm.h b/collie/farm/farm.h new file mode 100644 index 0000000..3d08396 --- /dev/null +++ b/collie/farm/farm.h @@ -0,0 +1,38 @@ +#ifndef FARM_H +#define FARM_H + +#include <stdio.h> +#include <stdlib.h> +#include <stdint.h> +#include <inttypes.h> +#include <memory.h> +#include <sys/types.h> +#include <sys/stat.h> +#include <fcntl.h> +#include <errno.h> +#include <sys/mman.h> +#include <linux/limits.h> + +#include "collie.h" +#include "sheepdog_proto.h" +#include "sheep.h" +#include "logger.h" +#include "strbuf.h" +#include "sha1.h" + +enum obj_type { + OBJECT = 1, + VDI, +}; + +/* object_rb_tree.c */ +int get_obj_nr(void); +void obj_tree_insert(uint64_t oid, enum obj_type type, int nr_copies); +void free_obj_tree(void); +void print_obj_tree(void); +typedef int (*obj_parser_func_t)(uint64_t oid, enum obj_type type, + int nr_copies, void *buf, + size_t size, void *data); +int parse_obj(obj_parser_func_t func, void *data); + +#endif diff --git a/collie/farm/object_rb_tree.c b/collie/farm/object_rb_tree.c new file mode 100644 index 0000000..d82817c --- /dev/null +++ b/collie/farm/object_rb_tree.c @@ -0,0 +1,148 @@ +/* + * Copyright (C) 2013 Zelin.io + * + * Kai Zhang <[email protected]> + * + * 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. + * + * You should have received a copy of the GNU General Public License + * along with this program. If not, see <http://www.gnu.org/licenses/>. + */ + +#include "farm.h" +#include "rbtree.h" + +struct obj_rb_entry { + uint64_t oid; + enum obj_type type; + int nr_copies; + struct rb_node node; + struct list_head list; +}; + +struct obj_rb_tree { + int nr_objs; + struct rb_root root; + struct list_head list; +}; + +static struct obj_rb_tree obj_tree = { + .nr_objs = 0, + .root = RB_ROOT, + .list = LIST_HEAD_INIT(obj_tree.list) +}; + +static struct obj_rb_entry *do_insert(struct rb_root *root, + struct obj_rb_entry *new) +{ + struct rb_node **p = &root->rb_node; + struct rb_node *parent = NULL; + struct obj_rb_entry *entry; + + while (*p) { + parent = *p; + entry = rb_entry(parent, struct obj_rb_entry, node); + + if (new->oid < entry->oid) + p = &(*p)->rb_left; + else if (new->oid > entry->oid) + p = &(*p)->rb_right; + else + return entry; /* already has this entry */ + } + rb_link_node(&new->node, parent, p); + rb_insert_color(&new->node, root); + + return NULL; /* insert sucessfully */ +} + +static struct obj_rb_entry *cached_entry; +void obj_tree_insert(uint64_t oid, enum obj_type type, int nr_copies) +{ + struct rb_root *root = &obj_tree.root; + struct obj_rb_entry *p = NULL; + + if (!cached_entry) + cached_entry = xzalloc(sizeof(*cached_entry)); + cached_entry->oid = oid; + cached_entry->type = type; + cached_entry->nr_copies = nr_copies; + rb_init_node(&cached_entry->node); + p = do_insert(root, cached_entry); + if (!p) { + list_add(&cached_entry->list, &obj_tree.list); + obj_tree.nr_objs++; + cached_entry = NULL; + } +} + +void print_obj_tree(void) +{ + struct rb_node *p = rb_first(&obj_tree.root); + struct obj_rb_entry *entry; + printf("nr_objs: %d\n", obj_tree.nr_objs); + + while (p) { + entry = rb_entry(p, struct obj_rb_entry, node); + printf("Obj id: %"PRIu64"\n", entry->oid); + p = rb_next(p); + } +} + +void free_obj_tree(void) +{ + struct obj_rb_entry *entry, *next; + list_for_each_entry_safe(entry, next, &obj_tree.list, list) { + free(entry); + } + if (cached_entry) + free(cached_entry); +} + +int get_obj_nr() +{ + return obj_tree.nr_objs; +} + +int parse_obj(obj_parser_func_t func, void *data) +{ + struct rb_node *p = rb_first(&obj_tree.root); + struct obj_rb_entry *entry; + uint64_t oid; + void *obj_buf = xmalloc(SD_DATA_OBJ_SIZE); + void *vdi_buf = xmalloc(SD_INODE_SIZE); + void *buf; + size_t size; + int ret = -1; + + while (p) { + entry = rb_entry(p, struct obj_rb_entry, node); + oid = entry->oid; + if (entry->type == OBJECT) { + buf = obj_buf; + size = SD_DATA_OBJ_SIZE; + } else if (entry->type == VDI) { + buf = vdi_buf; + size = SD_INODE_SIZE; + } else { + sd_eprintf("unknow object type %d", entry->type); + goto out; + } + + if (sd_read_object(oid, buf, size, 0, true) < 0) + goto out; + + if (func(oid, entry->type, entry->nr_copies, + buf, size, data) < 0) + goto out; + + p = rb_next(p); + } + ret = 0; +out: + free(obj_buf); + free(vdi_buf); + return ret; +} -- 1.7.1 -- sheepdog mailing list [email protected] http://lists.wpkg.org/mailman/listinfo/sheepdog
