[sheepdog] [PATCH v6 6/9] add traverse_btree() to list and check vdi
Liu Yuan
namei.unix at gmail.com
Mon Nov 11 09:55:29 CET 2013
On Mon, Nov 11, 2013 at 02:55:32PM +0800, Robin Dong wrote:
> 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 | 55 +++++++++++++++++++-----
> 3 files changed, 139 insertions(+), 31 deletions(-)
>
> diff --git a/dog/vdi.c b/dog/vdi.c
> index 4fe2b37..4e403db 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 26c9a3a..9111ca1 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 */
It would be better to explicitly describe 'whole tree' as 'the whole tree that
include all the inode, bnode, data objects'
Thanks
Yuan
More information about the sheepdog
mailing list