[sheepdog] [RFC PATCH 1/3] make rbtree more typesafe
Liu Yuan
namei.unix at gmail.com
Thu Sep 26 07:06:57 CEST 2013
On Thu, Sep 26, 2013 at 03:12:09AM +0900, MORITA Kazutaka wrote:
> From: MORITA Kazutaka <morita.kazutaka at lab.ntt.co.jp>
>
> This patch adds more strict type checking to rbtree functions and
> forbids inserting invalid rb nodes into the rb root.
>
> Signed-off-by: MORITA Kazutaka <morita.kazutaka at lab.ntt.co.jp>
> ---
> dog/dog.c | 6 +-
> dog/dog.h | 4 +-
> dog/farm/farm.c | 21 +++----
> dog/farm/object_tree.c | 32 ++++------
> dog/node.c | 14 ++---
> dog/trace.c | 7 ++-
> dog/vdi.c | 10 +--
> include/compiler.h | 5 ++
> include/internal_proto.h | 2 +
> include/rbtree.h | 142 +++++++++++++++++++++++++++---------------
> include/sheep.h | 48 +++++++-------
> include/sockfd_cache.h | 2 +-
> lib/event.c | 10 +--
> lib/rbtree.c | 22 +++----
> lib/sockfd_cache.c | 34 +++++-----
> sheep/cluster.h | 8 +--
> sheep/cluster/corosync.c | 6 +-
> sheep/cluster/local.c | 8 +--
> sheep/cluster/zookeeper.c | 28 +++++----
> sheep/group.c | 75 +++++++++++-----------
> sheep/md.c | 52 ++++++++--------
> sheep/object_cache.c | 15 ++---
> sheep/object_list_cache.c | 37 +++++------
> sheep/ops.c | 7 +--
> sheep/recovery.c | 2 +-
> sheep/sheep_priv.h | 2 +-
> sheep/vdi.c | 21 ++++---
> sheepfs/volume.c | 17 ++---
> tests/unit/dog/mock_dog.c | 4 +-
> tests/unit/mock/mock.c | 6 +-
> tests/unit/mock/mock.h | 6 +-
> tests/unit/sheep/mock_group.c | 6 +-
> tests/unit/sheep/test_hash.c | 41 ++++++------
> 33 files changed, 377 insertions(+), 323 deletions(-)
>
> diff --git a/dog/dog.c b/dog/dog.c
> index 16298ad..832cea8 100644
> --- a/dog/dog.c
> +++ b/dog/dog.c
> @@ -49,8 +49,8 @@ static void usage(const struct command *commands, int status);
> uint32_t sd_epoch;
>
> int sd_nodes_nr;
> -struct rb_root sd_vroot = RB_ROOT;
> -struct rb_root sd_nroot = RB_ROOT;
> +struct rb_vnode_root sd_vroot = RB_ROOT_INITIALIZER(vnode_cmp);
> +struct rb_node_root sd_nroot = RB_ROOT_INITIALIZER(node_cmp);
>
> int update_node_list(int max_nodes)
> {
> @@ -95,7 +95,7 @@ int update_node_list(int max_nodes)
> struct sd_node *n = xmalloc(sizeof(*n));
>
> *n = buf[i];
> - rb_insert(&sd_nroot, n, rb, node_cmp);
> + rb_insert(n, &sd_nroot);
> }
>
> nodes_to_vnodes(&sd_nroot, &sd_vroot);
> diff --git a/dog/dog.h b/dog/dog.h
> index 8c54c10..9d59b96 100644
> --- a/dog/dog.h
> +++ b/dog/dog.h
> @@ -55,8 +55,8 @@ extern bool raw_output;
> extern bool verbose;
>
> extern uint32_t sd_epoch;
> -extern struct rb_root sd_vroot;
> -extern struct rb_root sd_nroot;
> +extern struct rb_vnode_root sd_vroot;
> +extern struct rb_node_root sd_nroot;
> extern int sd_nodes_nr;
>
> bool is_current(const struct sd_inode *i);
> diff --git a/dog/farm/farm.c b/dog/farm/farm.c
> index 0204d1a..ff0e74e 100644
> --- a/dog/farm/farm.c
> +++ b/dog/farm/farm.c
> @@ -30,7 +30,6 @@ struct vdi_entry {
> uint8_t nr_copies;
> struct rb_node rb;
> };
> -static struct rb_root last_vdi_tree = RB_ROOT;
>
> struct snapshot_work {
> struct trunk_entry entry;
> @@ -45,13 +44,16 @@ static int vdi_cmp(const struct vdi_entry *e1, const struct vdi_entry *e2)
> return strcmp(e1->name, e2->name);
> }
>
> +static RB_ROOT(, struct vdi_entry, rb) last_vdi_tree =
> + RB_ROOT_INITIALIZER(vdi_cmp);
> +
> static struct vdi_entry *find_vdi(const char *name)
> {
> struct vdi_entry key = {};
>
> pstrcpy(key.name, sizeof(key.name), name);
>
> - return rb_search(&last_vdi_tree, &key, rb, vdi_cmp);
> + return rb_search(&key, &last_vdi_tree);
> }
>
> static struct vdi_entry *new_vdi(const char *name, uint64_t vdi_size,
> @@ -78,7 +80,7 @@ static void insert_vdi(struct sd_inode *new)
> new->vdi_id,
> new->snap_id,
> new->nr_copies);
> - rb_insert(&last_vdi_tree, vdi, rb, vdi_cmp);
> + rb_insert(vdi, &last_vdi_tree);
> } else if (vdi->snap_id < new->snap_id) {
> vdi->vdi_size = new->vdi_size;
> vdi->vdi_id = new->vdi_id;
> @@ -91,7 +93,7 @@ static int create_active_vdis(void)
> {
> struct vdi_entry *vdi;
> uint32_t new_vid;
> - rb_for_each_entry(vdi, &last_vdi_tree, rb) {
> + rb_for_each_entry(vdi, &last_vdi_tree) {
> if (do_vdi_create(vdi->name,
> vdi->vdi_size,
> vdi->vdi_id, &new_vid,
> @@ -101,15 +103,6 @@ static int create_active_vdis(void)
> return 0;
> }
>
> -static void free_vdi_list(void)
> -{
> - struct vdi_entry *vdi;
> - rb_for_each_entry(vdi, &last_vdi_tree, rb) {
> - rb_erase(&vdi->rb, &last_vdi_tree);
> - free(vdi);
> - }
> -}
> -
> char *get_object_directory(void)
> {
> return farm_object_dir;
> @@ -414,6 +407,6 @@ int farm_load_snapshot(uint32_t idx, const char *tag)
>
> ret = 0;
> out:
> - free_vdi_list();
> + rb_destroy(&last_vdi_tree);
> return ret;
> }
> diff --git a/dog/farm/object_tree.c b/dog/farm/object_tree.c
> index c624fea..0485eaf 100644
> --- a/dog/farm/object_tree.c
> +++ b/dog/farm/object_tree.c
> @@ -20,15 +20,6 @@ struct object_tree_entry {
> struct rb_node node;
> };
>
> -struct object_tree {
> - int nr_objs;
> - struct rb_root root;
> -};
> -
> -static struct object_tree tree = {
> - .nr_objs = 0,
> - .root = RB_ROOT,
> -};
> static struct object_tree_entry *cached_entry;
>
> static int object_tree_cmp(const struct object_tree_entry *a,
> @@ -37,15 +28,18 @@ static int object_tree_cmp(const struct object_tree_entry *a,
> return intcmp(a->oid, b->oid);
> }
>
> -static struct object_tree_entry *do_insert(struct rb_root *root,
> - struct object_tree_entry *new)
> -{
> - return rb_insert(root, new, node, object_tree_cmp);
> -}
> +struct object_tree {
> + int nr_objs;
> + RB_ROOT(, struct object_tree_entry, node) root;
> +};
> +
> +static struct object_tree tree = {
> + .nr_objs = 0,
> + .root = RB_ROOT_INITIALIZER(object_tree_cmp),
> +};
>
> 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)
> @@ -53,7 +47,7 @@ void object_tree_insert(uint64_t oid, int nr_copies)
> cached_entry->oid = oid;
> cached_entry->nr_copies = nr_copies;
> rb_init_node(&cached_entry->node);
> - p = do_insert(root, cached_entry);
> + p = rb_insert(cached_entry, &tree.root);
> if (!p) {
> tree.nr_objs++;
> cached_entry = NULL;
> @@ -65,13 +59,13 @@ void object_tree_print(void)
> struct object_tree_entry *entry;
> printf("nr_objs: %d\n", tree.nr_objs);
>
> - rb_for_each_entry(entry, &tree.root, node)
> + rb_for_each_entry(entry, &tree.root)
> printf("Obj id: %"PRIx64"\n", entry->oid);
> }
>
> void object_tree_free(void)
> {
> - rb_destroy(&tree.root, struct object_tree_entry, node);
> + rb_destroy(&tree.root);
> free(cached_entry);
> }
>
> @@ -86,7 +80,7 @@ int for_each_object_in_tree(int (*func)(uint64_t oid, int nr_copies,
> struct object_tree_entry *entry;
> int ret = -1;
>
> - rb_for_each_entry(entry, &tree.root, node) {
> + rb_for_each_entry(entry, &tree.root) {
> if (func(entry->oid, entry->nr_copies, data) < 0)
> goto out;
> }
> diff --git a/dog/node.c b/dog/node.c
> index 052739c..0d2d4a5 100644
> --- a/dog/node.c
> +++ b/dog/node.c
> @@ -34,7 +34,7 @@ static int node_list(int argc, char **argv)
>
> if (!raw_output)
> printf(" Id Host:Port V-Nodes Zone\n");
> - rb_for_each_entry(n, &sd_nroot, rb) {
> + rb_for_each_entry(n, &sd_nroot) {
> const char *host = addr_to_str(n->nid.addr, n->nid.port);
>
> printf(raw_output ? "%d %s %d %u\n" : "%4d %-20s\t%2d%11u\n",
> @@ -53,7 +53,7 @@ static int node_info(int argc, char **argv)
> if (!raw_output)
> printf("Id\tSize\tUsed\tAvail\tUse%%\n");
>
> - rb_for_each_entry(n, &sd_nroot, rb) {
> + rb_for_each_entry(n, &sd_nroot) {
> struct sd_req req;
> struct sd_rsp *rsp = (struct sd_rsp *)&req;
>
> @@ -195,7 +195,7 @@ static int node_recovery(int argc, char **argv)
> " Progress\n");
> }
>
> - rb_for_each_entry(n, &sd_nroot, rb) {
> + rb_for_each_entry(n, &sd_nroot) {
> struct sd_req req;
> struct sd_rsp *rsp = (struct sd_rsp *)&req;
> struct recovery_state state;
> @@ -233,12 +233,12 @@ static int node_recovery(int argc, char **argv)
> return EXIT_SUCCESS;
> }
>
> -static struct sd_node *idx_to_node(struct rb_root *nroot, int idx)
> +static struct sd_node *idx_to_node(struct rb_node_root *nroot, int idx)
> {
> - struct sd_node *n = rb_entry(rb_first(nroot), struct sd_node, rb);
> + struct sd_node *n = rb_first(nroot);
>
> while (idx--)
> - n = rb_entry(rb_next(&n->rb), struct sd_node, rb);
> + n = rb_next(n, nroot);
>
> return n;
> }
> @@ -355,7 +355,7 @@ static int md_info(int argc, char **argv)
> if (!node_cmd_data.all_nodes)
> return node_md_info(&sd_nid);
>
> - rb_for_each_entry(n, &sd_nroot, rb) {
> + rb_for_each_entry(n, &sd_nroot) {
> fprintf(stdout, "Node %d:\n", i++);
> ret = node_md_info(&n->nid);
> if (ret != EXIT_SUCCESS)
> diff --git a/dog/trace.c b/dog/trace.c
> index 806a3dd..9346849 100644
> --- a/dog/trace.c
> +++ b/dog/trace.c
> @@ -252,8 +252,6 @@ struct graph_stat_entry {
> uint16_t nr_calls;
> };
>
> -static struct rb_root stat_tree_root;
> -
> static LIST_HEAD(stat_list);
>
> static int graph_stat_cmp(const struct graph_stat_entry *a,
> @@ -262,12 +260,15 @@ static int graph_stat_cmp(const struct graph_stat_entry *a,
> return strcmp(a->fname, b->fname);
> }
>
> +static RB_ROOT(, struct graph_stat_entry, rb) stat_tree_root =
> + RB_ROOT_INITIALIZER(graph_stat_cmp);
> +
> static struct graph_stat_entry *
> stat_tree_insert(struct graph_stat_entry *new)
> {
> struct graph_stat_entry *entry;
>
> - entry = rb_insert(&stat_tree_root, new, rb, graph_stat_cmp);
> + entry = rb_insert(new, &stat_tree_root);
> if (entry) {
> entry->duration += new->duration;
> entry->nr_calls++;
> diff --git a/dog/vdi.c b/dog/vdi.c
> index a465e6a..402945c 100644
> --- a/dog/vdi.c
> +++ b/dog/vdi.c
> @@ -320,7 +320,7 @@ static void parse_objs(uint64_t oid, obj_parser_func_t func, void *data, unsigne
> char *buf;
>
> buf = xzalloc(size);
> - rb_for_each_entry(n, &sd_nroot, rb) {
> + rb_for_each_entry(n, &sd_nroot) {
> struct sd_req hdr;
> struct sd_rsp *rsp = (struct sd_rsp *)&hdr;
>
> @@ -922,8 +922,8 @@ static int do_track_object(uint64_t oid, uint8_t nr_copies)
>
> nr_logs = rsp->data_length / sizeof(struct epoch_log);
> for (i = nr_logs - 1; i >= 0; i--) {
> - struct rb_root vroot = RB_ROOT;
> - struct rb_root nroot = RB_ROOT;
> + struct rb_vnode_root vroot = RB_ROOT_INITIALIZER(vnode_cmp);
> + struct rb_node_root nroot = RB_ROOT_INITIALIZER(node_cmp);
>
> printf("\nobj %"PRIx64" locations at epoch %d, copies = %d\n",
> oid, logs[i].epoch, nr_copies);
> @@ -942,7 +942,7 @@ static int do_track_object(uint64_t oid, uint8_t nr_copies)
> continue;
> }
> for (int k = 0; k < logs[i].nr_nodes; k++)
> - rb_insert(&nroot, &logs[i].nodes[k], rb, node_cmp);
> + rb_insert(&logs[i].nodes[k], &nroot);
> nodes_to_vnodes(&nroot, &vroot);
> oid_to_vnodes(oid, &vroot, nr_copies, vnode_buf);
> for (j = 0; j < nr_copies; j++) {
> @@ -950,7 +950,7 @@ static int do_track_object(uint64_t oid, uint8_t nr_copies)
>
> printf("%s\n", addr_to_str(n->addr, n->port));
> }
> - rb_destroy(&vroot, struct sd_vnode, rb);
> + rb_destroy(&vroot);
> }
>
> free(logs);
> diff --git a/include/compiler.h b/include/compiler.h
> index 324dacf..a071bd8 100644
> --- a/include/compiler.h
> +++ b/include/compiler.h
> @@ -29,6 +29,11 @@
> const typeof(((type *)0)->member) *__mptr = (ptr); \
> (type *)((char *)__mptr - offsetof(type, member)); })
>
> +#define offset_container_of(ptr, type, offset) \
> + (type *)((char *)(ptr) - (offset))
> +#define offset_member_of(ptr, type, offset) \
> + (type *)((char *)(ptr) + (offset))
> +
> #define likely(x) __builtin_expect(!!(x), 1)
> #define unlikely(x) __builtin_expect(!!(x), 0)
>
> diff --git a/include/internal_proto.h b/include/internal_proto.h
> index 59c6e2a..c46b5a1 100644
> --- a/include/internal_proto.h
> +++ b/include/internal_proto.h
> @@ -143,6 +143,8 @@ struct sd_node {
> uint64_t space;
> };
>
> +RB_ROOT(rb_node_root, struct sd_node, rb);
> +
> /*
> * A joining sheep multicasts the local cluster info. Then, the existing nodes
> * reply the latest cluster info which is unique among all of the nodes.
> diff --git a/include/rbtree.h b/include/rbtree.h
> index 6aba6ad..a395cf5 100644
> --- a/include/rbtree.h
> +++ b/include/rbtree.h
> @@ -12,7 +12,7 @@ struct rb_node {
> struct rb_node *rb_left __attribute__ ((aligned (8)));
> };
>
> -struct rb_root {
> +struct __rb_root {
> struct rb_node *rb_node;
> };
>
> @@ -33,15 +33,38 @@ static inline void rb_set_color(struct rb_node *rb, int color)
> rb->rb_parent_color = (rb->rb_parent_color & ~1) | color;
> }
>
> -#define RB_ROOT { .rb_node = NULL }
> -static inline void INIT_RB_ROOT(struct rb_root *root)
> -{
> - root->rb_node = NULL;
> +#define RB_ROOT_INITIALIZER(compar) { .cmp = compar }
> +
> +#define RB_ROOT(name, type, member) \
> +struct name { \
> + struct __rb_root r; \
> + int (*cmp)(const type *, const type *); \
> + \
> + /* The below fields are used only at compile time */ \
> + type *t; \
> + char o[offsetof(type, member)]; \
> }
We do better provide two helpers
RB_ROOT_STRUCT(name, type, member) as a named struct
RB_ROOT(type, member) as a unamed struct that is delcared inside a strct.
Thanks
Yuan
More information about the sheepdog
mailing list