[sheepdog] [PATCH v6 08/16] collie/farm: implement object_tree

[Kai Zhang]

object_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_tree, duplicate id will be saved only once
3. for each oid in object_tree, read the object and save to farm

object_tree has 5 public interfaces:
1. object_tree_size()
   returns current object number in the tree
2. object_tree_insert()
   insert a object id into the tree
3. object_tree_free()
   free memory
4. object_tree_free()
   print each node of tree for debug
5. for_each_object_in_tree()
   foreach node in the tree, read object from cluster and call the function.

Signed-off-by: Kai Zhang <kyle at zelin.io>
---
 collie/Makefile.am        |    3 +-
 collie/farm/farm.h        |   33 +++++++++++
 collie/farm/object_tree.c |  133 +++++++++++++++++++++++++++++++++++++++++++++
 3 files changed, 168 insertions(+), 1 deletions(-)
 create mode 100644 collie/farm/farm.h
 create mode 100644 collie/farm/object_tree.c

diff --git a/collie/Makefile.am b/collie/Makefile.am
index 3fba2dd..3fdb147 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_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..6c47985
--- /dev/null
+++ b/collie/farm/farm.h
@@ -0,0 +1,33 @@
+#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"
+
+typedef int (*object_handler_func_t)(uint64_t oid, int nr_copies, void *buf,
+				     size_t size, void *data);
+
+/* object_tree.c */
+int object_tree_size(void);
+void object_tree_insert(uint64_t oid, int nr_copies);
+void object_tree_free(void);
+void object_tree_print(void);
+int for_each_object_in_tree(object_handler_func_t func, void *data);
+
+#endif
diff --git a/collie/farm/object_tree.c b/collie/farm/object_tree.c
new file mode 100644
index 0000000..f719af6
--- /dev/null
+++ b/collie/farm/object_tree.c
@@ -0,0 +1,133 @@
+/*
+ * Copyright (C) 2013 Zelin.io
+ *
+ * Kai Zhang <kyle at zelin.io>
+ *
+ * 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 object_tree_entry {
+	uint64_t oid;
+	int nr_copies;
+	struct rb_node node;
+	struct list_head list;
+};
+
+struct object_tree {
+	int nr_objs;
+	struct rb_root root;
+	struct list_head list;
+};
+
+static struct object_tree tree = {
+	.nr_objs = 0,
+	.root = RB_ROOT,
+	.list = LIST_HEAD_INIT(tree.list)
+};
+static struct object_tree_entry *cached_entry;
+
+static struct object_tree_entry *do_insert(struct rb_root *root,
+				      struct object_tree_entry *new)
+{
+	struct rb_node **p = &root->rb_node;
+	struct rb_node *parent = NULL;
+	struct object_tree_entry *entry;
+
+	while (*p) {
+		parent = *p;
+		entry = rb_entry(parent, struct object_tree_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 */
+}
+
+void object_tree_insert(uint64_t oid, int nr_copies)
+{
+	struct rb_root *root = &tree.root;
+	struct object_tree_entry *p = NULL;
+
+	if (!cached_entry)
+		cached_entry = xzalloc(sizeof(*cached_entry));
+	cached_entry->oid = oid;
+	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, &tree.list);
+		tree.nr_objs++;
+		cached_entry = NULL;
+	}
+}
+
+void object_tree_print(void)
+{
+	struct rb_node *p = rb_first(&tree.root);
+	struct object_tree_entry *entry;
+	printf("nr_objs: %d\n", tree.nr_objs);
+
+	while (p) {
+		entry = rb_entry(p, struct object_tree_entry, node);
+		printf("Obj id: %"PRIu64"\n", entry->oid);
+		p = rb_next(p);
+	}
+}
+
+void object_tree_free(void)
+{
+	struct object_tree_entry *entry, *next;
+	list_for_each_entry_safe(entry, next, &tree.list, list)
+		free(entry);
+
+	free(cached_entry);
+}
+
+int object_tree_size()
+{
+	return tree.nr_objs;
+}
+
+int for_each_object_in_tree(object_handler_func_t func, void *data)
+{
+	struct rb_node *p = rb_first(&tree.root);
+	struct object_tree_entry *entry;
+	uint64_t oid;
+	size_t size;
+	void *buf = xmalloc(max(SD_INODE_SIZE, SD_DATA_OBJ_SIZE));
+	int ret = -1;
+
+	while (p) {
+		entry = rb_entry(p, struct object_tree_entry, node);
+		oid = entry->oid;
+		size = get_objsize(oid);
+
+		if (sd_read_object(oid, buf, size, 0, true) < 0)
+			goto out;
+
+		if (func(oid, entry->nr_copies,
+			 buf, size, data) < 0)
+			goto out;
+
+		p = rb_next(p);
+	}
+	ret = 0;
+out:
+	free(buf);
+	return ret;
+}
-- 
1.7.1