[sheepdog] [PATCH 1/2] add helper macros to insert/search/iterate rbtree node
MORITA Kazutaka
morita.kazutaka at gmail.com
Thu Aug 22 05:39:45 CEST 2013
From: MORITA Kazutaka <morita.kazutaka at lab.ntt.co.jp>
Signed-off-by: MORITA Kazutaka <morita.kazutaka at lab.ntt.co.jp>
---
dog/farm/object_tree.c | 39 ++++++------------------
dog/trace.c | 33 +++++++--------------
include/rbtree.h | 72 +++++++++++++++++++++++++++++++++++++++++++++
lib/sockfd_cache.c | 52 +++++++-------------------------
sheep/cluster/zookeeper.c | 52 +++++++-------------------------
sheep/object_cache.c | 45 ++++++----------------------
sheep/object_list_cache.c | 54 ++++++++++------------------------
sheep/vdi.c | 56 ++++++++---------------------------
sheepfs/volume.c | 45 ++++++----------------------
9 files changed, 159 insertions(+), 289 deletions(-)
diff --git a/dog/farm/object_tree.c b/dog/farm/object_tree.c
index 53724e9..4be3c46 100644
--- a/dog/farm/object_tree.c
+++ b/dog/farm/object_tree.c
@@ -34,28 +34,16 @@ static struct object_tree tree = {
};
static struct object_tree_entry *cached_entry;
+static int object_tree_cmp(const struct object_tree_entry *a,
+ const struct object_tree_entry *b)
+{
+ return intcmp(a->oid, b->oid);
+}
+
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 */
+ return rb_insert(root, new, node, object_tree_cmp);
}
void object_tree_insert(uint64_t oid, int nr_copies)
@@ -78,15 +66,11 @@ void object_tree_insert(uint64_t oid, int nr_copies)
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);
+ rb_for_each_entry(entry, &tree.root, node)
printf("Obj id: %"PRIx64"\n", entry->oid);
- p = rb_next(p);
- }
}
void object_tree_free(void)
@@ -106,17 +90,12 @@ int object_tree_size(void)
int for_each_object_in_tree(int (*func)(uint64_t oid, int nr_copies,
void *data), void *data)
{
- struct rb_node *p = rb_first(&tree.root);
struct object_tree_entry *entry;
int ret = -1;
- while (p) {
- entry = rb_entry(p, struct object_tree_entry, node);
-
+ rb_for_each_entry(entry, &tree.root, node) {
if (func(entry->oid, entry->nr_copies, data) < 0)
goto out;
-
- p = rb_next(p);
}
ret = 0;
out:
diff --git a/dog/trace.c b/dog/trace.c
index ab51ca4..7c57c7d 100644
--- a/dog/trace.c
+++ b/dog/trace.c
@@ -258,34 +258,23 @@ static struct rb_root stat_tree_root;
static LIST_HEAD(stat_list);
+static int graph_stat_cmp(const struct graph_stat_entry *a,
+ const struct graph_stat_entry *b)
+{
+ return strcmp(a->fname, b->fname);
+}
+
static struct graph_stat_entry *
stat_tree_insert(struct graph_stat_entry *new)
{
- struct rb_node **p = &stat_tree_root.rb_node;
- struct rb_node *parent = NULL;
struct graph_stat_entry *entry;
- while (*p) {
- int cmp;
-
- parent = *p;
- entry = rb_entry(parent, struct graph_stat_entry, rb);
- cmp = strcmp(new->fname, entry->fname);
-
- if (cmp < 0)
- p = &(*p)->rb_left;
- else if (cmp > 0)
- p = &(*p)->rb_right;
- else {
- entry->duration += new->duration;
- entry->nr_calls++;
- return entry;
- }
+ entry = rb_insert(&stat_tree_root, new, rb, graph_stat_cmp);
+ if (entry) {
+ entry->duration += new->duration;
+ entry->nr_calls++;
}
- rb_link_node(&new->rb, parent, p);
- rb_insert_color(&new->rb, &stat_tree_root);
-
- return NULL; /* insert successfully */
+ return entry;
}
static void prepare_stat_tree(struct trace_graph_item *item)
diff --git a/include/rbtree.h b/include/rbtree.h
index 642d151..15f873a 100644
--- a/include/rbtree.h
+++ b/include/rbtree.h
@@ -80,4 +80,76 @@ static inline void rb_link_node(struct rb_node *node, struct rb_node *parent,
*rb_link = node;
}
+/*
+ * Search for a value in the rbtree. This returns NULL when the key is not
+ * found in the rbtree.
+ */
+#define rb_search(root, key, member, compar) \
+({ \
+ struct rb_node *__n = (root)->rb_node; \
+ typeof(key) __ret = NULL, __data; \
+ \
+ while (__n) { \
+ __data = rb_entry(__n, typeof(*key), member); \
+ int __cmp = compar(key, __data); \
+ \
+ if (__cmp < 0) \
+ __n = __n->rb_left; \
+ else if (__cmp > 0) \
+ __n = __n->rb_right; \
+ else { \
+ __ret = __data; \
+ break; \
+ } \
+ } \
+ __ret; \
+})
+
+/*
+ * Insert a new node into the rbtree. This returns NULL on success, or the
+ * existing node on error.
+ */
+#define rb_insert(root, new, member, compar) \
+({ \
+ struct rb_node **__n = &(root)->rb_node, *__parent = NULL; \
+ typeof(new) __old = NULL, __data; \
+ \
+ while (*__n) { \
+ __data = rb_entry(*__n, typeof(*new), member); \
+ int __cmp = compar(new, __data); \
+ \
+ __parent = *__n; \
+ if (__cmp < 0) \
+ __n = &((*__n)->rb_left); \
+ else if (__cmp > 0) \
+ __n = &((*__n)->rb_right); \
+ else { \
+ __old = __data; \
+ break; \
+ } \
+ } \
+ \
+ if (__old == NULL) { \
+ /* Add new node and rebalance tree. */ \
+ rb_link_node(&((new)->member), __parent, __n); \
+ rb_insert_color(&((new)->member), root); \
+ } \
+ \
+ __old; \
+})
+
+/* Iterate over a rbtree safe against removal of rbnode */
+#define rb_for_each(pos, root) \
+ pos = rb_first(root); \
+ for (struct rb_node *__n = rb_next(pos); \
+ pos && ({ __n = rb_next(pos); 1; }); \
+ pos = __n)
+
+/* Iterate over a rbtree of given type safe against removal of rbnode */
+#define rb_for_each_entry(pos, root, member) \
+ for (struct rb_node *__pos = rb_first(root), *__n; \
+ __pos && ({ __n = rb_next(__pos); 1; }) && \
+ ({ pos = rb_entry(__pos, typeof(*pos), member); 1; }); \
+ __pos = __n)
+
#endif /* __RBTREE_H_ */
diff --git a/lib/sockfd_cache.c b/lib/sockfd_cache.c
index c9404ea..5d0f2f2 100644
--- a/lib/sockfd_cache.c
+++ b/lib/sockfd_cache.c
@@ -72,53 +72,23 @@ struct sockfd_cache_entry {
struct sockfd_cache_fd *fds;
};
+static int sockfd_cache_cmp(const struct sockfd_cache_entry *a,
+ const struct sockfd_cache_entry *b)
+{
+ return node_id_cmp(&a->nid, &b->nid);
+}
+
static struct sockfd_cache_entry *
sockfd_cache_insert(struct sockfd_cache_entry *new)
{
- struct rb_node **p = &sockfd_cache.root.rb_node;
- struct rb_node *parent = NULL;
- struct sockfd_cache_entry *entry;
-
- while (*p) {
- int cmp;
-
- parent = *p;
- entry = rb_entry(parent, struct sockfd_cache_entry, rb);
- cmp = node_id_cmp(&new->nid, &entry->nid);
-
- if (cmp < 0)
- p = &(*p)->rb_left;
- else if (cmp > 0)
- p = &(*p)->rb_right;
- else
- return entry;
- }
- rb_link_node(&new->rb, parent, p);
- rb_insert_color(&new->rb, &sockfd_cache.root);
-
- return NULL; /* insert successfully */
+ return rb_insert(&sockfd_cache.root, new, rb, sockfd_cache_cmp);
}
static struct sockfd_cache_entry *sockfd_cache_search(const struct node_id *nid)
{
- struct rb_node *n = sockfd_cache.root.rb_node;
- struct sockfd_cache_entry *t;
-
- while (n) {
- int cmp;
-
- t = rb_entry(n, struct sockfd_cache_entry, rb);
- cmp = node_id_cmp(nid, &t->nid);
-
- if (cmp < 0)
- n = n->rb_left;
- else if (cmp > 0)
- n = n->rb_right;
- else
- return t; /* found it */
- }
+ struct sockfd_cache_entry key = { .nid = *nid };
- return NULL;
+ return rb_search(&sockfd_cache.root, &key, rb, sockfd_cache_cmp);
}
static inline int get_free_slot(struct sockfd_cache_entry *entry)
@@ -279,7 +249,6 @@ static struct work_queue *grow_wq;
static void do_grow_fds(struct work *work)
{
struct sockfd_cache_entry *entry;
- struct rb_node *p;
int old_fds_count, new_fds_count, new_size, i;
sd_debug("%d", fds_count);
@@ -287,8 +256,7 @@ static void do_grow_fds(struct work *work)
old_fds_count = fds_count;
new_fds_count = fds_count * 2;
new_size = sizeof(struct sockfd_cache_fd) * fds_count * 2;
- for (p = rb_first(&sockfd_cache.root); p; p = rb_next(p)) {
- entry = rb_entry(p, struct sockfd_cache_entry, rb);
+ rb_for_each_entry(entry, &sockfd_cache.root, rb) {
entry->fds = xrealloc(entry->fds, new_size);
for (i = old_fds_count; i < new_fds_count; i++) {
entry->fds[i].fd = -1;
diff --git a/sheep/cluster/zookeeper.c b/sheep/cluster/zookeeper.c
index 02149ec..3972ba0 100644
--- a/sheep/cluster/zookeeper.c
+++ b/sheep/cluster/zookeeper.c
@@ -80,51 +80,21 @@ static bool first_push = true;
static void zk_compete_master(void);
+static int zk_node_cmp(const struct zk_node *a, const struct zk_node *b)
+{
+ return node_id_cmp(&a->node.nid, &b->node.nid);
+}
+
static struct zk_node *zk_tree_insert(struct zk_node *new)
{
- struct rb_node **p = &zk_node_root.rb_node;
- struct rb_node *parent = NULL;
- struct zk_node *entry;
-
- while (*p) {
- int cmp;
-
- parent = *p;
- entry = rb_entry(parent, struct zk_node, rb);
-
- cmp = node_cmp(&new->node, &entry->node);
- if (cmp < 0)
- p = &(*p)->rb_left;
- else if (cmp > 0)
- p = &(*p)->rb_right;
- else
- /* already has this entry */
- return entry;
- }
- rb_link_node(&new->rb, parent, p);
- rb_insert_color(&new->rb, &zk_node_root);
- return NULL; /* insert successfully */
+ return rb_insert(&zk_node_root, new, rb, zk_node_cmp);
}
static struct zk_node *zk_tree_search_nolock(const struct node_id *nid)
{
- struct rb_node *n = zk_node_root.rb_node;
- struct zk_node *t;
+ struct zk_node key = { .node.nid = *nid };
- while (n) {
- int cmp;
-
- t = rb_entry(n, struct zk_node, rb);
- cmp = node_id_cmp(nid, &t->node.nid);
-
- if (cmp < 0)
- n = n->rb_left;
- else if (cmp > 0)
- n = n->rb_right;
- else
- return t; /* found it */
- }
- return NULL;
+ return rb_search(&zk_node_root, &key, rb, zk_node_cmp);
}
static inline struct zk_node *zk_tree_search(const struct node_id *nid)
@@ -481,14 +451,12 @@ static inline void zk_tree_destroy(void)
static inline void build_node_list(void)
{
- struct rb_node *n;
struct zk_node *zk;
nr_sd_nodes = 0;
- for (n = rb_first(&zk_node_root); n; n = rb_next(n)) {
- zk = rb_entry(n, struct zk_node, rb);
+ rb_for_each_entry(zk, &zk_node_root, rb)
sd_nodes[nr_sd_nodes++] = zk->node;
- }
+
sd_debug("nr_sd_nodes:%zu", nr_sd_nodes);
}
diff --git a/sheep/object_cache.c b/sheep/object_cache.c
index 51ecec7..3715a7c 100644
--- a/sheep/object_cache.c
+++ b/sheep/object_cache.c
@@ -102,6 +102,12 @@ static inline uint32_t entry_idx(const struct object_cache_entry *entry)
return entry->idx & ~CACHE_INDEX_MASK;
}
+static int object_cache_cmp(const struct object_cache_entry *a,
+ const struct object_cache_entry *b)
+{
+ return intcmp(entry_idx(a), entry_idx(b));
+}
+
static inline uint32_t object_cache_oid_to_idx(uint64_t oid)
{
uint32_t idx = data_oid_to_idx(oid);
@@ -199,48 +205,15 @@ static inline void unlock_entry(struct object_cache_entry *entry)
static struct object_cache_entry *
lru_tree_insert(struct rb_root *root, struct object_cache_entry *new)
{
- struct rb_node **p = &root->rb_node;
- struct rb_node *parent = NULL;
- struct object_cache_entry *entry;
- uint32_t idx = entry_idx(new);
-
- while (*p) {
- parent = *p;
- entry = rb_entry(parent, struct object_cache_entry, node);
-
- if (idx < entry_idx(entry))
- p = &(*p)->rb_left;
- else if (idx > entry_idx(entry))
- p = &(*p)->rb_right;
- else {
- /* already has this entry */
- return entry;
- }
- }
- rb_link_node(&new->node, parent, p);
- rb_insert_color(&new->node, root);
-
- return NULL; /* insert successfully */
+ return rb_insert(root, new, node, object_cache_cmp);
}
static struct object_cache_entry *lru_tree_search(struct rb_root *root,
uint32_t idx)
{
- struct rb_node *n = root->rb_node;
- struct object_cache_entry *t;
-
- while (n) {
- t = rb_entry(n, struct object_cache_entry, node);
-
- if (idx < entry_idx(t))
- n = n->rb_left;
- else if (idx > entry_idx(t))
- n = n->rb_right;
- else
- return t; /* found it */
- }
+ struct object_cache_entry key = { .idx = idx };
- return NULL;
+ return rb_search(root, &key, node, object_cache_cmp);
}
static void do_background_push(struct work *work)
diff --git a/sheep/object_list_cache.c b/sheep/object_list_cache.c
index 357784e..8717972 100644
--- a/sheep/object_list_cache.c
+++ b/sheep/object_list_cache.c
@@ -41,53 +41,31 @@ static struct objlist_cache obj_list_cache = {
.lock = SD_LOCK_INITIALIZER,
};
+static int objlist_cache_cmp(const struct objlist_cache_entry *a,
+ const struct objlist_cache_entry *b)
+{
+ return intcmp(a->oid, b->oid);
+}
+
static struct objlist_cache_entry *objlist_cache_rb_insert(struct rb_root *root,
struct objlist_cache_entry *new)
{
- struct rb_node **p = &root->rb_node;
- struct rb_node *parent = NULL;
- struct objlist_cache_entry *entry;
-
- while (*p) {
- parent = *p;
- entry = rb_entry(parent, struct objlist_cache_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 successfully */
+ return rb_insert(root, new, node, objlist_cache_cmp);
}
static int objlist_cache_rb_remove(struct rb_root *root, uint64_t oid)
{
- struct rb_node **p = &root->rb_node;
- struct rb_node *parent = NULL;
- struct objlist_cache_entry *entry;
+ struct objlist_cache_entry *entry, key = { .oid = oid };
- while (*p) {
- parent = *p;
- entry = rb_entry(parent, struct objlist_cache_entry, node);
-
- if (oid < entry->oid)
- p = &(*p)->rb_left;
- else if (oid > entry->oid)
- p = &(*p)->rb_right;
- else {
- list_del(&entry->list);
- rb_erase(parent, root);
- free(entry);
- return 0;
- }
- }
+ entry = rb_search(root, &key, node, objlist_cache_cmp);
+ if (!entry)
+ return -1;
+
+ list_del(&entry->list);
+ rb_erase(&entry->node, root);
+ free(entry);
- return -1; /* fail to remove */
+ return 0;
}
void objlist_cache_remove(uint64_t oid)
diff --git a/sheep/vdi.c b/sheep/vdi.c
index 9f5f2ab..4a180cb 100644
--- a/sheep/vdi.c
+++ b/sheep/vdi.c
@@ -22,48 +22,24 @@ static uint32_t max_copies;
static struct rb_root vdi_state_root = RB_ROOT;
static struct sd_lock vdi_state_lock = SD_LOCK_INITIALIZER;
+static int vdi_state_cmp(const struct vdi_state_entry *a,
+ const struct vdi_state_entry *b)
+{
+ return intcmp(a->vid, b->vid);
+}
+
static struct vdi_state_entry *vdi_state_search(struct rb_root *root,
uint32_t vid)
{
- struct rb_node *n = root->rb_node;
- struct vdi_state_entry *t;
-
- while (n) {
- t = rb_entry(n, struct vdi_state_entry, node);
-
- if (vid < t->vid)
- n = n->rb_left;
- else if (vid > t->vid)
- n = n->rb_right;
- else
- return t;
- }
+ struct vdi_state_entry key = { .vid = vid };
- return NULL;
+ return rb_search(root, &key, node, vdi_state_cmp);
}
static struct vdi_state_entry *vdi_state_insert(struct rb_root *root,
struct vdi_state_entry *new)
{
- struct rb_node **p = &root->rb_node;
- struct rb_node *parent = NULL;
- struct vdi_state_entry *entry;
-
- while (*p) {
- parent = *p;
- entry = rb_entry(parent, struct vdi_state_entry, node);
-
- if (new->vid < entry->vid)
- p = &(*p)->rb_left;
- else if (new->vid > entry->vid)
- 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 successfully */
+ return rb_insert(root, new, node, vdi_state_cmp);
}
static bool vid_is_snapshot(uint32_t vid)
@@ -165,13 +141,11 @@ int add_vdi_state(uint32_t vid, int nr_copies, bool snapshot)
int fill_vdi_state_list(void *data)
{
int nr = 0;
- struct rb_node *n;
struct vdi_state *vs = data;
struct vdi_state_entry *entry;
sd_read_lock(&vdi_state_lock);
- for (n = rb_first(&vdi_state_root); n; n = rb_next(n)) {
- entry = rb_entry(n, struct vdi_state_entry, node);
+ rb_for_each_entry(entry, &vdi_state_root, node) {
memset(vs, 0, sizeof(*vs));
vs->vid = entry->vid;
vs->nr_copies = entry->nr_copies;
@@ -948,16 +922,12 @@ out:
void clean_vdi_state(void)
{
- struct rb_node *current_node = rb_first(&vdi_state_root);
- struct vdi_state_entry *entry = NULL;
+ struct vdi_state_entry *entry;
sd_write_lock(&vdi_state_lock);
- while (current_node) {
- entry = rb_entry(current_node, struct vdi_state_entry, node);
- rb_erase(current_node, &vdi_state_root);
+ rb_for_each_entry(entry, &vdi_state_root, node) {
+ rb_erase(&entry->node, &vdi_state_root);
free(entry);
- entry = NULL;
- current_node = rb_first(&vdi_state_root);
}
INIT_RB_ROOT(&vdi_state_root);
sd_unlock(&vdi_state_lock);
diff --git a/sheepfs/volume.c b/sheepfs/volume.c
index 0558639..99aaf81 100644
--- a/sheepfs/volume.c
+++ b/sheepfs/volume.c
@@ -64,46 +64,21 @@ struct vdi_inode {
static struct rb_root vdi_inode_tree = RB_ROOT;
static struct sd_lock vdi_inode_tree_lock = SD_LOCK_INITIALIZER;
-static struct vdi_inode *vdi_inode_tree_insert(struct vdi_inode *new)
+static int vdi_inode_cmp(const struct vdi_inode *a, const struct vdi_inode *b)
{
- struct rb_node **p = &vdi_inode_tree.rb_node;
- struct rb_node *parent = NULL;
- struct vdi_inode *entry;
-
- while (*p) {
- parent = *p;
- entry = rb_entry(parent, struct vdi_inode, rb);
-
- if (new->vid < entry->vid)
- p = &(*p)->rb_left;
- else if (new->vid > entry->vid)
- p = &(*p)->rb_right;
- else
- return entry; /* already has this entry */
- }
- rb_link_node(&new->rb, parent, p);
- rb_insert_color(&new->rb, &vdi_inode_tree);
+ return intcmp(a->vid, b->vid);
+}
- return NULL; /* insert successfully */
+static struct vdi_inode *vdi_inode_tree_insert(struct vdi_inode *new)
+{
+ return rb_insert(&vdi_inode_tree, new, rb, vdi_inode_cmp);
}
static struct vdi_inode *vdi_inode_tree_search(uint32_t vid)
{
- struct rb_node *n = vdi_inode_tree.rb_node;
- struct vdi_inode *t;
-
- while (n) {
- t = rb_entry(n, struct vdi_inode, rb);
-
- if (vid < t->vid)
- n = n->rb_left;
- else if (vid > t->vid)
- n = n->rb_right;
- else
- return t; /* found it */
- }
+ struct vdi_inode key = { .vid = vid };
- return NULL;
+ return rb_search(&vdi_inode_tree, &key, rb, vdi_inode_cmp);
}
int create_volume_layout(void)
@@ -364,13 +339,11 @@ static int setup_socket_pool(int array[], int len)
int reset_socket_pool(void)
{
- struct rb_node *node;
struct vdi_inode *vdi;
int ret = 0;
sd_read_lock(&vdi_inode_tree_lock);
- for (node = rb_first(&vdi_inode_tree); node; node = rb_next(node)) {
- vdi = rb_entry(node, struct vdi_inode, rb);
+ rb_for_each_entry(vdi, &vdi_inode_tree, rb) {
destroy_socket_pool(vdi->socket_pool, SOCKET_POOL_SIZE);
if (setup_socket_pool(vdi->socket_pool,
SOCKET_POOL_SIZE) < 0) {
--
1.7.9.5
More information about the sheepdog
mailing list