[sheepdog] [PATCH v4 6/7] add traverse_btree() to list and check vdi

Robin Dong robin.k.dong at gmail.com
Fri Nov 1 11:03:41 CET 2013


Add framework about traverse of B-tree for vdi_list() and vdi_check()

Signed-off-by: Robin Dong <sanbai at taobao.com>
---
 dog/vdi.c                |  106 +++++++++++++++++++++++++++++++++++++--------
 include/sheepdog_proto.h |   10 ++++
 lib/sd_inode.c           |   53 ++++++++++++++++++-----
 3 files changed, 138 insertions(+), 31 deletions(-)

diff --git a/dog/vdi.c b/dog/vdi.c
index 4fe2b37..ac18d40 100644
--- a/dog/vdi.c
+++ b/dog/vdi.c
@@ -85,14 +85,37 @@ static void vdi_show_progress(uint64_t done, uint64_t total)
 	return show_progress(done, total, false);
 }
 
-/*
- * Get the number of objects.
- *
- * 'my_objs' means the number objects which belongs to this vdi.  'cow_objs'
- * means the number of the other objects.
- */
-static void stat_data_objs(const struct sd_inode *inode, uint64_t *my_objs,
-			   uint64_t *cow_objs)
+struct stat_arg {
+	uint64_t *my;
+	uint64_t *cow;
+	uint32_t vid;
+};
+
+static void stat_cb(void *data, enum btree_node_type type, void *arg)
+{
+	struct sd_extent *ext;
+	struct stat_arg *sarg = arg;
+	uint64_t *my = sarg->my;
+	uint64_t *cow = sarg->cow;
+
+	if (type == BTREE_EXT) {
+		ext = (struct sd_extent *)data;
+		if (ext->vdi_id == sarg->vid)
+			(*my)++;
+		else if (ext->vdi_id != 0)
+			(*cow)++;
+	}
+}
+
+static void stat_data_objs_btree(const struct sd_inode *inode,
+				 uint64_t *my_objs, uint64_t *cow_objs)
+{
+	struct stat_arg arg = {my_objs, cow_objs, inode->vdi_id};
+	traverse_btree(dog_bnode_reader, inode, stat_cb, &arg);
+}
+
+static void stat_data_objs_array(const struct sd_inode *inode,
+				 uint64_t *my_objs, uint64_t *cow_objs)
 {
 	int nr;
 	uint64_t my, cow, *p;
@@ -141,12 +164,27 @@ static void stat_data_objs(const struct sd_inode *inode, uint64_t *my_objs,
 	*cow_objs = cow;
 }
 
+/*
+ * Get the number of objects.
+ *
+ * 'my_objs' means the number objects which belongs to this vdi.  'cow_objs'
+ * means the number of the other objects.
+ */
+static void stat_data_objs(const struct sd_inode *inode, uint64_t *my_objs,
+			   uint64_t *cow_objs)
+{
+	if (inode->store_policy == 0)
+		stat_data_objs_array(inode, my_objs, cow_objs);
+	else
+		stat_data_objs_btree(inode, my_objs, cow_objs);
+}
+
 static void print_vdi_list(uint32_t vid, const char *name, const char *tag,
 			   uint32_t snapid, uint32_t flags,
 			   const struct sd_inode *i, void *data)
 {
 	bool is_clone = false;
-	uint64_t my_objs, cow_objs;
+	uint64_t my_objs = 0, cow_objs = 0;
 	time_t ti;
 	struct tm tm;
 	char dbuf[128];
@@ -1702,6 +1740,30 @@ static void queue_vdi_check_work(const struct sd_inode *inode, uint64_t oid,
 	}
 }
 
+struct check_arg {
+	const struct sd_inode *inode;
+	uint64_t *done;
+	struct work_queue *wq;
+};
+
+static void check_cb(void *data, enum btree_node_type type, void *arg)
+{
+	struct sd_extent *ext;
+	struct check_arg *carg = arg;
+	uint64_t oid;
+
+	if (type == BTREE_EXT) {
+		ext = (struct sd_extent *)data;
+		if (ext->vdi_id) {
+			oid = vid_to_data_oid(ext->vdi_id, ext->idx);
+			*(carg->done) = (uint64_t)ext->idx * SD_DATA_OBJ_SIZE;
+			vdi_show_progress(*(carg->done), carg->inode->vdi_size);
+			queue_vdi_check_work(carg->inode, oid, carg->done,
+					     carg->wq);
+		}
+	}
+}
+
 int do_vdi_check(const struct sd_inode *inode)
 {
 	uint32_t max_idx;
@@ -1720,17 +1782,23 @@ int do_vdi_check(const struct sd_inode *inode)
 
 	queue_vdi_check_work(inode, vid_to_vdi_oid(inode->vdi_id), NULL, wq);
 
-	max_idx = count_data_objs(inode);
-	vdi_show_progress(done, inode->vdi_size);
-	for (uint32_t idx = 0; idx < max_idx; idx++) {
-		vid = INODE_GET_VID(inode, idx);
-		if (vid) {
-			oid = vid_to_data_oid(vid, idx);
-			queue_vdi_check_work(inode, oid, &done, wq);
-		} else {
-			done += SD_DATA_OBJ_SIZE;
-			vdi_show_progress(done, inode->vdi_size);
+	if (inode->store_policy == 0) {
+		max_idx = count_data_objs(inode);
+		vdi_show_progress(done, inode->vdi_size);
+		for (uint32_t idx = 0; idx < max_idx; idx++) {
+			vid = INODE_GET_VID(inode, idx);
+			if (vid) {
+				oid = vid_to_data_oid(vid, idx);
+				queue_vdi_check_work(inode, oid, &done, wq);
+			} else {
+				done += SD_DATA_OBJ_SIZE;
+				vdi_show_progress(done, inode->vdi_size);
+			}
 		}
+	} else {
+		struct check_arg arg = {inode, &done, wq};
+		traverse_btree(dog_bnode_reader, inode, check_cb, &arg);
+		vdi_show_progress(inode->vdi_size, inode->vdi_size);
 	}
 
 	work_queue_wait(wq);
diff --git a/include/sheepdog_proto.h b/include/sheepdog_proto.h
index d6337b5..eee2734 100644
--- a/include/sheepdog_proto.h
+++ b/include/sheepdog_proto.h
@@ -252,6 +252,12 @@ struct sd_extent_header {
 	uint32_t entries;
 };
 
+enum btree_node_type {
+	BTREE_HEAD = 1,
+	BTREE_EXT,
+	BTREE_IDX,
+};
+
 typedef int (*write_node_fn)(uint64_t id, void *mem, unsigned int len,
 				uint64_t offset, uint32_t flags, int copies,
 				int copy_policy, bool create, bool direct);
@@ -280,6 +286,10 @@ extern int sd_inode_write_vid(write_node_fn writer, struct sd_inode *inode,
 extern uint32_t sd_inode_get_meta_size(struct sd_inode *inode, size_t size);
 extern void sd_inode_copy_vdis(struct sd_inode *oldi, struct sd_inode *newi);
 
+typedef void (*btree_cb_fn)(void *data, enum btree_node_type type, void *arg);
+extern void traverse_btree(read_node_fn reader, const struct sd_inode *inode,
+			   btree_cb_fn fn, void *arg);
+
 /* 64 bit FNV-1a non-zero initial basis */
 #define FNV1A_64_INIT ((uint64_t) 0xcbf29ce484222325ULL)
 #define FNV_64_PRIME ((uint64_t) 0x100000001b3ULL)
diff --git a/lib/sd_inode.c b/lib/sd_inode.c
index 256b7f9..2e67d2d 100644
--- a/lib/sd_inode.c
+++ b/lib/sd_inode.c
@@ -132,25 +132,23 @@ static int index_comp(void *a, void *b)
 		return 0;
 }
 
-/* dump the information of B-tree */
-static void dump_btree(read_node_fn reader, struct sd_inode *inode)
+/* traverse whole btree and do call-back-function */
+void traverse_btree(read_node_fn reader, const struct sd_inode *inode,
+		    btree_cb_fn fn, void *arg)
 {
-#ifdef DEBUG
 	struct sd_extent_header *header = EXT_HEADER(inode->data_vdi_id);
 	struct sd_extent_header *leaf_node = NULL;
 	struct sd_extent *last, *iter;
 	struct sd_extent_idx *last_idx, *iter_idx;
 	void *tmp;
 
-	sd_info("btree> header: %u %u %u", header->magic,
-			header->entries, header->depth);
-
+	fn(header, BTREE_HEAD, arg);
 	if (header->depth == 1) {
 		last = LAST_EXT(inode->data_vdi_id);
 		iter = FIRST_EXT(inode->data_vdi_id);
 
 		while (iter != last) {
-			sd_info("btree> ext: %d, %u", iter->idx, iter->vdi_id);
+			fn(iter, BTREE_EXT, arg);
 			iter++;
 		}
 	} else if (header->depth == 2) {
@@ -163,14 +161,12 @@ static void dump_btree(read_node_fn reader, struct sd_inode *inode)
 			reader(iter_idx->oid, &tmp,
 					SD_INODE_DATA_INDEX_SIZE, 0);
 
-			sd_info("btree> %p idx: %d, %lu, %u",
-					iter_idx, iter_idx->idx, iter_idx->oid,
-					leaf_node->entries);
+			fn(iter_idx, BTREE_IDX, arg);
+			fn(leaf_node, BTREE_HEAD, arg);
 			last = LAST_EXT(leaf_node);
 			iter = FIRST_EXT(leaf_node);
 			while (iter != last) {
-				sd_info("btree> ext in: %d, %u",
-						iter->idx, iter->vdi_id);
+				fn(iter, BTREE_EXT, arg);
 				iter++;
 			}
 			iter_idx++;
@@ -179,6 +175,38 @@ static void dump_btree(read_node_fn reader, struct sd_inode *inode)
 		free(leaf_node);
 	} else
 		panic("This B-tree not support depth %u", header->depth);
+}
+
+#ifdef DEBUG
+static void dump_cb(void *data, enum btree_node_type type, void *arg)
+{
+	struct sd_extent_header *header;
+	struct sd_extent *ext;
+	struct sd_extent_idx *idx;
+
+	switch (type) {
+	case BTREE_HEAD:
+		header = (struct sd_extent_header *)data;
+		sd_info("btree> HEAD: magic %u entries %u depth %u",
+			header->magic, header->entries, header->depth);
+		break;
+	case BTREE_EXT:
+		ext = (struct sd_extent *)data;
+		sd_info("btree> EXT: idx %u vdi_id %u", ext->idx, ext->vdi_id);
+		break;
+	case BTREE_IDX:
+		idx = (struct sd_extent_idx *)data;
+		sd_info("btree> IDX: idx %u oid %lu", idx->idx, idx->oid);
+		break;
+	}
+}
+#endif
+
+/* dump the information of B-tree */
+static void dump_btree(read_node_fn reader, struct sd_inode *inode)
+{
+#ifdef DEBUG
+	traverse_btree(reader, inode, dump_cb, NULL);
 #endif
 }
 
@@ -621,3 +649,4 @@ void sd_inode_copy_vdis(struct sd_inode *oldi, struct sd_inode *newi)
 {
 	memcpy(newi->data_vdi_id, oldi->data_vdi_id, sizeof(newi->data_vdi_id));
 }
+
-- 
1.7.1




More information about the sheepdog mailing list