[sheepdog] [PATCH] add helper to do linear search and removing key in an array
MORITA Kazutaka
morita.kazutaka at gmail.com
Mon Jun 17 19:05:16 CEST 2013
From: MORITA Kazutaka <morita.kazutaka at lab.ntt.co.jp>
This adds a type-safe version of lfind() and a helper to remove key in
an array, and simplifies complex manipulation of node arrays in the
cluster drivers.
This also fixes a memory boundary bug in do_leave_sheep().
Signed-off-by: MORITA Kazutaka <morita.kazutaka at lab.ntt.co.jp>
---
include/util.h | 36 ++++++++++++++++++++++++++++++++++++
sheep/cluster/corosync.c | 38 +++++++++++++-------------------------
sheep/cluster/local.c | 32 ++++++++++----------------------
sheep/cluster/shepherd.c | 19 +++++--------------
sheep/group.c | 18 ++++++------------
5 files changed, 70 insertions(+), 73 deletions(-)
diff --git a/include/util.h b/include/util.h
index 8fb1db2..983a4b8 100644
--- a/include/util.h
+++ b/include/util.h
@@ -8,6 +8,7 @@
#include <limits.h>
#include <stdint.h>
#include <unistd.h>
+#include <search.h>
#include <urcu/uatomic.h>
#include "bitops.h"
@@ -122,6 +123,41 @@ int atomic_create_and_write(const char *path, char *buf, size_t len);
__ret; \
})
+/* a type safe version of lfind() */
+#define xlfind(key, base, nmemb, compar) \
+({ \
+ typeof(&(base)[0]) __ret = NULL; \
+ if (nmemb > 0) { \
+ size_t __n = nmemb; \
+ assert(compar(key, key) == 0); \
+ assert(compar(base, base) == 0); \
+ __ret = lfind(key, base, &__n, sizeof(*(base)), \
+ (comparison_fn_t)compar); \
+ } \
+ __ret; \
+})
+
+/*
+ * Search 'key' in the array 'base' linearly and remove it if it found.
+ *
+ * If 'key' is found in 'base', this function increments *nmemb and returns
+ * true.
+ */
+#define xlremove(key, base, nmemb, compar) \
+({ \
+ bool __removed = false; \
+ typeof(&(base)[0]) __e; \
+ \
+ __e = xlfind(key, base, *(nmemb), compar); \
+ if (__e != NULL) { \
+ (*(nmemb))--; \
+ memmove(__e, __e + 1, \
+ sizeof(*(base)) * (*(nmemb) - (__e - (base)))); \
+ __removed = true; \
+ } \
+ __removed; \
+})
+
#ifdef assert
#undef assert
#endif
diff --git a/sheep/cluster/corosync.c b/sheep/cluster/corosync.c
index 767c826..2be978b 100644
--- a/sheep/cluster/corosync.c
+++ b/sheep/cluster/corosync.c
@@ -89,21 +89,17 @@ struct corosync_message {
uint8_t msg[0];
};
-static bool cpg_node_equal(struct cpg_node *a, struct cpg_node *b)
+static int cpg_node_cmp(struct cpg_node *a, struct cpg_node *b)
{
- return (a->nodeid == b->nodeid && a->pid == b->pid);
+ int cmp = memcmp(&a->nodeid, &b->nodeid, sizeof(a->nodeid));
+ if (cmp == 0)
+ cmp = memcmp(&a->pid, &b->pid, sizeof(a->pid));
+ return cmp;
}
-static inline int find_cpg_node(struct cpg_node *nodes, size_t nr_nodes,
- struct cpg_node *key)
+static bool cpg_node_equal(struct cpg_node *a, struct cpg_node *b)
{
- int i;
-
- for (i = 0; i < nr_nodes; i++)
- if (cpg_node_equal(nodes + i, key))
- return i;
-
- return -1;
+ return cpg_node_cmp(a, b) == 0;
}
static inline int find_sd_node(struct cpg_node *nodes, size_t nr_nodes,
@@ -127,16 +123,7 @@ static inline void add_cpg_node(struct cpg_node *nodes, size_t nr_nodes,
static inline void del_cpg_node(struct cpg_node *nodes, size_t nr_nodes,
struct cpg_node *deled)
{
- int idx;
-
- idx = find_cpg_node(nodes, nr_nodes, deled);
- if (idx < 0) {
- sd_dprintf("cannot find node");
- return;
- }
-
- nr_nodes--;
- memmove(nodes + idx, nodes + idx + 1, sizeof(*nodes) * (nr_nodes - idx));
+ xlremove(deled, nodes, &nr_nodes, cpg_node_cmp);
}
static int corosync_get_local_addr(uint8_t *addr)
@@ -293,7 +280,7 @@ static bool __corosync_dispatch_one(struct corosync_event *cevent)
{
enum cluster_join_result res;
struct sd_node entries[SD_MAX_NODES];
- int idx;
+ struct cpg_node *n;
switch (cevent->type) {
case COROSYNC_EVENT_TYPE_JOIN_REQUEST:
@@ -342,10 +329,11 @@ static bool __corosync_dispatch_one(struct corosync_event *cevent)
}
break;
case COROSYNC_EVENT_TYPE_LEAVE:
- idx = find_cpg_node(cpg_nodes, nr_cpg_nodes, &cevent->sender);
- if (idx < 0)
+ n = xlfind(&cevent->sender, cpg_nodes, nr_cpg_nodes,
+ cpg_node_cmp);
+ if (n == NULL)
break;
- cevent->sender.ent = cpg_nodes[idx].ent;
+ cevent->sender.ent = n->ent;
del_cpg_node(cpg_nodes, nr_cpg_nodes, &cevent->sender);
nr_cpg_nodes--;
diff --git a/sheep/cluster/local.c b/sheep/cluster/local.c
index 2d298d8..3c9048f 100644
--- a/sheep/cluster/local.c
+++ b/sheep/cluster/local.c
@@ -50,9 +50,14 @@ static char *lnode_to_str(struct local_node *lnode)
return s;
}
+static bool lnode_cmp(const struct local_node *a, const struct local_node *b)
+{
+ return node_cmp(&a->node, &b->node);
+}
+
static bool lnode_eq(const struct local_node *a, const struct local_node *b)
{
- return node_eq(&a->node, &b->node);
+ return lnode_cmp(a, b) == 0;
}
enum local_event_type {
@@ -240,22 +245,9 @@ static void shm_queue_init(void)
shm_queue_unlock();
}
-static struct local_node *find_lnode(struct local_node *key, size_t nr_lnodes,
- struct local_node *lnodes)
-{
- int i;
-
- for (i = 0; i < nr_lnodes; i++)
- if (lnode_eq(key, lnodes + i))
- return lnodes + i;
-
- panic("internal error");
-}
-
static void add_event(enum local_event_type type, struct local_node *lnode,
void *buf, size_t buf_len)
{
- int idx, i;
struct local_node *n;
struct local_event ev = {
.type = type,
@@ -274,21 +266,17 @@ static void add_event(enum local_event_type type, struct local_node *lnode,
ev.nr_lnodes++;
break;
case EVENT_LEAVE:
- n = find_lnode(lnode, ev.nr_lnodes, ev.lnodes);
- idx = n - ev.lnodes;
-
- ev.nr_lnodes--;
- memmove(n, n + 1, sizeof(*n) * (ev.nr_lnodes - idx));
+ xlremove(lnode, ev.lnodes, &ev.nr_lnodes, lnode_cmp);
break;
case EVENT_GATEWAY:
- n = find_lnode(lnode, ev.nr_lnodes, ev.lnodes);
+ n = xlfind(lnode, ev.lnodes, ev.nr_lnodes, lnode_cmp);
n->gateway = true;
break;
case EVENT_NOTIFY:
case EVENT_BLOCK:
break;
case EVENT_UPDATE_NODE:
- n = find_lnode(lnode, ev.nr_lnodes, ev.lnodes);
+ n = xlfind(lnode, ev.lnodes, ev.nr_lnodes, lnode_cmp);
n->node = lnode->node;
break;
case EVENT_JOIN_RESPONSE:
@@ -296,7 +284,7 @@ static void add_event(enum local_event_type type, struct local_node *lnode,
}
sd_dprintf("type = %d, sender = %s", ev.type, lnode_to_str(&ev.sender));
- for (i = 0; i < ev.nr_lnodes; i++)
+ for (int i = 0; i < ev.nr_lnodes; i++)
sd_dprintf("%d: %s", i, lnode_to_str(ev.lnodes + i));
shm_queue_push(&ev);
diff --git a/sheep/cluster/shepherd.c b/sheep/cluster/shepherd.c
index 7f65a4b..46ca5f9 100644
--- a/sheep/cluster/shepherd.c
+++ b/sheep/cluster/shepherd.c
@@ -431,7 +431,7 @@ static void msg_block_forward(struct sph_msg *rcv)
static void do_leave_sheep(void)
{
- int i, j, ret;
+ int ret;
struct sd_node sender;
ret = xread(sph_comm_fd, &sender, sizeof(sender));
@@ -442,16 +442,8 @@ static void do_leave_sheep(void)
sd_iprintf("removing node: %s", node_to_str(&sender));
- for (i = 0; i < nr_nodes; i++) {
- if (node_eq(&sender, &nodes[i])) {
- for (j = i; j < nr_nodes; j++)
- nodes[j] = nodes[j + 1];
-
- nr_nodes--;
-
- goto removed;
- }
- }
+ if (xlremove(&sender, nodes, &nr_nodes, node_cmp))
+ goto removed;
sd_iprintf("leave message from unknown node: %s",
node_to_str(&sender));
@@ -687,9 +679,8 @@ static void shepherd_unblock(void *msg, size_t msg_len)
static void shepherd_update_node(struct sd_node *node)
{
- for (int i = 0; i < nr_nodes; i++)
- if (node_eq(node, &nodes[i]))
- nodes[i] = *node;
+ struct sd_node *n = xlfind(node, nodes, nr_nodes, node_cmp);
+ *n = *nodes;
}
static struct cluster_driver cdrv_shepherd = {
diff --git a/sheep/group.c b/sheep/group.c
index f74ef10..0259f0b 100644
--- a/sheep/group.c
+++ b/sheep/group.c
@@ -373,18 +373,14 @@ static const struct sd_node *find_entry_epoch(const struct sd_node *entry,
uint32_t epoch)
{
struct sd_node nodes[SD_MAX_NODES];
- int nr, i;
+ int nr;
if (!epoch)
return NULL;
nr = epoch_log_read(epoch, nodes, sizeof(nodes));
- for (i = 0; i < nr; i++)
- if (node_eq(&nodes[i], entry))
- return entry;
-
- return NULL;
+ return xlfind(entry, nodes, nr, node_cmp);
}
/*
@@ -740,14 +736,12 @@ static struct vnode_info *alloc_old_vnode_info(const struct sd_node *joined,
size_t nr_nodes)
{
struct sd_node old_nodes[SD_MAX_NODES];
- size_t count = 0, i;
/* exclude the newly added one */
- for (i = 0; i < nr_nodes; i++) {
- if (!node_eq(nodes + i, joined))
- old_nodes[count++] = nodes[i];
- }
- return alloc_vnode_info(old_nodes, count);
+ memcpy(old_nodes, nodes, sizeof(*nodes) * nr_nodes);
+ xlremove(joined, old_nodes, &nr_nodes, node_cmp);
+
+ return alloc_vnode_info(old_nodes, nr_nodes);
}
static void setup_backend_store(const char *store, bool need_purge)
--
1.7.9.5
More information about the sheepdog
mailing list