[sheepdog] [PATCH v7 06/10] sheep: add traverse_btree() to list and check vdi
Robin Dong
robin.k.dong at gmail.com
Sat Nov 16 15:57:35 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 | 105 +++++++++++++++++++++++++++++++++++++--------
include/sheepdog_proto.h | 10 ++++
lib/sd_inode.c | 56 +++++++++++++++++++-----
3 files changed, 140 insertions(+), 31 deletions(-)
diff --git a/dog/vdi.c b/dog/vdi.c
index 3042577..6e2e94d 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,29 @@ 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, NULL, carg->wq);
+ }
+ }
+}
+
int do_vdi_check(const struct sd_inode *inode)
{
uint32_t max_idx;
@@ -1720,17 +1781,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 72a1e3a..56a606e 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 be9f904..c76a1bc 100644
--- a/lib/sd_inode.c
+++ b/lib/sd_inode.c
@@ -132,25 +132,24 @@ 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 the whole btree that include all the inode->data_vdi_id, bnode,
+ * data objects and call btree_cb_fn() */
+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 +162,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 +176,40 @@ 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
+ sd_info("btree> BEGIN");
+ traverse_btree(reader, inode, dump_cb, NULL);
+ sd_info("btree> END");
#endif
}
@@ -632,3 +663,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