[sheepdog] [PATCH] make qsort and bsearch type safe

MORITA Kazutaka morita.kazutaka at gmail.com
Thu May 16 06:39:06 CEST 2013


From: MORITA Kazutaka <morita.kazutaka at lab.ntt.co.jp>

This introduces wrappers around qsort and bsearch to make them type
safe.

Signed-off-by: MORITA Kazutaka <morita.kazutaka at lab.ntt.co.jp>
---
 include/sheep.h           |   25 +++++++++++++------------
 include/util.h            |   13 +++++++++++++
 lib/event.c               |    8 ++++----
 sheep/cluster/zookeeper.c |    2 +-
 sheep/group.c             |   10 +++++-----
 sheep/md.c                |    7 ++-----
 sheep/ops.c               |    7 +++----
 sheep/recovery.c          |   14 ++++++--------
 8 files changed, 47 insertions(+), 39 deletions(-)

diff --git a/include/sheep.h b/include/sheep.h
index 456fd07..2ce7678 100644
--- a/include/sheep.h
+++ b/include/sheep.h
@@ -233,13 +233,10 @@ static inline const char *sd_strerror(int err)
 	return descs[err];
 }
 
-static inline int node_id_cmp(const void *a, const void *b)
+static inline int node_id_cmp(const struct node_id *node1,
+			      const struct node_id *node2)
 {
-	const struct node_id *node1 = a;
-	const struct node_id *node2 = b;
-	int cmp;
-
-	cmp = memcmp(node1->addr, node2->addr, sizeof(node1->addr));
+	int cmp = memcmp(node1->addr, node2->addr, sizeof(node1->addr));
 	if (cmp != 0)
 		return cmp;
 
@@ -250,16 +247,20 @@ static inline int node_id_cmp(const void *a, const void *b)
 	return 0;
 }
 
-static inline bool node_eq(const struct sd_node *a, const struct sd_node *b)
+static inline int node_cmp(const struct sd_node *node1,
+			   const struct sd_node *node2)
 {
-	return node_id_cmp(&a->nid, &b->nid) == 0;
+	return node_id_cmp(&node1->nid, &node2->nid);
 }
 
-static inline int vnode_cmp(const void *a, const void *b)
+static inline bool node_eq(const struct sd_node *a, const struct sd_node *b)
 {
-	const struct sd_vnode *node1 = a;
-	const struct sd_vnode *node2 = b;
+	return node_cmp(a, b) == 0;
+}
 
+static inline int vnode_cmp(const struct sd_vnode *node1,
+			    const struct sd_vnode *node2)
+{
 	if (node1->id < node2->id)
 		return -1;
 	if (node1->id > node2->id)
@@ -297,7 +298,7 @@ static inline int nodes_to_vnodes(struct sd_node *nodes, int nr,
 	}
 
 	if (vnodes)
-		qsort(vnodes, nr_vnodes, sizeof(*vnodes), vnode_cmp);
+		typesafe_qsort(vnodes, nr_vnodes, vnode_cmp);
 
 	return nr_vnodes;
 }
diff --git a/include/util.h b/include/util.h
index 68eface..82d0d7e 100644
--- a/include/util.h
+++ b/include/util.h
@@ -113,6 +113,19 @@ int atomic_create_and_write(const char *path, char *buf, size_t len);
 
 #endif	/* NDEBUG */
 
+#define typesafe_qsort(base, nmemb, compar)				\
+({									\
+	assert(compar(base, base) == 0);				\
+	qsort(base, nmemb, sizeof(*(base)), (comparison_fn_t)compar);	\
+})
+
+#define typesafe_bsearch(key, base, nmemb, compar)			\
+({									\
+	(void) (key == base);						\
+	assert(compar(base, base) == 0);				\
+	bsearch(key, base, nmemb, sizeof(*(base)), (comparison_fn_t)compar); \
+})
+
 /* urcu helpers */
 
 /* Boolean data type which can be accessed by multiple threads */
diff --git a/lib/event.c b/lib/event.c
index becacd7..c47ca2c 100644
--- a/lib/event.c
+++ b/lib/event.c
@@ -171,12 +171,12 @@ void event_force_refresh(void)
 	event_loop_refresh = true;
 }
 
-static int epoll_event_cmp(const void *_a, const void *_b)
+static int epoll_event_cmp(const struct epoll_event *_a, struct epoll_event *_b)
 {
 	struct event_info *a, *b;
 
-	a = (struct event_info *)((struct epoll_event *)_a)->data.ptr;
-	b = (struct event_info *)((struct epoll_event *)_b)->data.ptr;
+	a = (struct event_info *)_a->data.ptr;
+	b = (struct event_info *)_b->data.ptr;
 
 	/* we need sort event_info array in reverse order */
 	if (a->prio < b->prio)
@@ -194,7 +194,7 @@ static void do_event_loop(int timeout, bool sort_with_prio)
 refresh:
 	nr = epoll_wait(efd, events, nr_events, timeout);
 	if (sort_with_prio)
-		qsort(events, nr, sizeof(struct epoll_event), epoll_event_cmp);
+		typesafe_qsort(events, nr, epoll_event_cmp);
 
 	if (nr < 0) {
 		if (errno == EINTR)
diff --git a/sheep/cluster/zookeeper.c b/sheep/cluster/zookeeper.c
index 648bb7a..1cd39f7 100644
--- a/sheep/cluster/zookeeper.c
+++ b/sheep/cluster/zookeeper.c
@@ -85,7 +85,7 @@ static struct zk_node *zk_tree_insert(struct zk_node *new)
 		parent = *p;
 		entry = rb_entry(parent, struct zk_node, rb);
 
-		cmp = node_id_cmp(&new->node.nid, &entry->node.nid);
+		cmp = node_cmp(&new->node, &entry->node);
 		if (cmp < 0)
 			p = &(*p)->rb_left;
 		else if (cmp > 0)
diff --git a/sheep/group.c b/sheep/group.c
index 8fce4c6..bf1a2fd 100644
--- a/sheep/group.c
+++ b/sheep/group.c
@@ -130,8 +130,8 @@ bool have_enough_zones(void)
 
 static int get_node_idx(struct vnode_info *vnode_info, struct sd_node *ent)
 {
-	ent = bsearch(ent, vnode_info->nodes, vnode_info->nr_nodes,
-		      sizeof(*ent), node_id_cmp);
+	ent = typesafe_bsearch(ent, vnode_info->nodes, vnode_info->nr_nodes,
+			       node_cmp);
 	if (!ent)
 		return -1;
 
@@ -188,7 +188,7 @@ struct vnode_info *alloc_vnode_info(const struct sd_node *nodes,
 
 	vnode_info->nr_nodes = nr_nodes;
 	memcpy(vnode_info->nodes, nodes, sizeof(*nodes) * nr_nodes);
-	qsort(vnode_info->nodes, nr_nodes, sizeof(*nodes), node_id_cmp);
+	typesafe_qsort(vnode_info->nodes, nr_nodes, node_cmp);
 
 	recalculate_vnodes(vnode_info->nodes, nr_nodes);
 
@@ -578,8 +578,8 @@ static int cluster_wait_for_join_check(const struct sd_node *joined,
 		sd_eprintf("joining node epoch too small: %"
 			   PRIu32 " vs %" PRIu32, jm->epoch, local_epoch);
 
-		if (bsearch(joined, local_entries, nr_local_entries,
-			    sizeof(struct sd_node), node_id_cmp))
+		if (typesafe_bsearch(joined, local_entries, nr_local_entries,
+				     node_cmp))
 			return CJ_RES_FAIL;
 		return CJ_RES_JOIN_LATER;
 	}
diff --git a/sheep/md.c b/sheep/md.c
index 14d563d..7a3261c 100644
--- a/sheep/md.c
+++ b/sheep/md.c
@@ -82,11 +82,8 @@ static struct vdisk *oid_to_vdisk_from(struct vdisk *vds, int nr, uint64_t oid)
 	}
 }
 
-static int vdisk_cmp(const void *a, const void *b)
+static int vdisk_cmp(const struct vdisk *d1, const struct vdisk *d2)
 {
-	const struct vdisk *d1 = a;
-	const struct vdisk *d2 = b;
-
 	if (d1->id < d2->id)
 		return -1;
 	if (d1->id > d2->id)
@@ -116,7 +113,7 @@ static inline int disks_to_vdisks(struct disk *ds, int nmds, struct vdisk *vds)
 
 		d_iter++;
 	}
-	qsort(vds, nr_vdisks, sizeof(*vds), vdisk_cmp);
+	typesafe_qsort(vds, nr_vdisks, vdisk_cmp);
 
 	return nr_vdisks;
 }
diff --git a/sheep/ops.c b/sheep/ops.c
index 8ab9ac3..bff7f1d 100644
--- a/sheep/ops.c
+++ b/sheep/ops.c
@@ -687,12 +687,12 @@ static int cluster_recovery_completion(const struct sd_req *req,
 	 * to send notification
 	 */
 	for (i = 0; i < nr_recovereds; i++)
-		if (!node_id_cmp(&node->nid, &recovereds[i].nid)) {
+		if (!node_cmp(node, recovereds + i)) {
 			sd_dprintf("duplicate %s", node_to_str(node));
 			return SD_RES_SUCCESS;
 		}
 	recovereds[nr_recovereds++] = *node;
-	qsort(recovereds, nr_recovereds, sizeof(*recovereds), node_id_cmp);
+	typesafe_qsort(recovereds, nr_recovereds, node_cmp);
 
 	sd_dprintf("%s is recovered at epoch %d", node_to_str(node), epoch);
 	for (i = 0; i < nr_recovereds; i++)
@@ -705,8 +705,7 @@ static int cluster_recovery_completion(const struct sd_req *req,
 
 	if (vnode_info->nr_nodes == nr_recovereds) {
 		for (i = 0; i < nr_recovereds; ++i) {
-			if (node_id_cmp(&vnode_info->nodes[i].nid,
-					&recovereds[i].nid))
+			if (node_cmp(vnode_info->nodes + i, recovereds + i))
 				break;
 		}
 		if (i == nr_recovereds) {
diff --git a/sheep/recovery.c b/sheep/recovery.c
index 20e930f..cc61203 100644
--- a/sheep/recovery.c
+++ b/sheep/recovery.c
@@ -89,12 +89,10 @@ static void queue_recovery_work(struct recovery_info *rinfo);
 #define DEFAULT_LIST_BUFFER_SIZE (UINT64_C(1) << 22)
 static size_t list_buffer_size = DEFAULT_LIST_BUFFER_SIZE;
 
-static int obj_cmp(const void *oid1, const void *oid2)
+static int obj_cmp(const uint64_t *oid1, const uint64_t *oid2)
 {
-	const uint64_t hval1 = fnv_64a_buf((void *)oid1, sizeof(uint64_t),
-					   FNV1A_64_INIT);
-	const uint64_t hval2 = fnv_64a_buf((void *)oid2, sizeof(uint64_t),
-					   FNV1A_64_INIT);
+	const uint64_t hval1 = fnv_64a_buf(oid1, sizeof(*oid1), FNV1A_64_INIT);
+	const uint64_t hval2 = fnv_64a_buf(oid2, sizeof(*oid2), FNV1A_64_INIT);
 
 	if (hval1 < hval2)
 		return -1;
@@ -713,8 +711,8 @@ static void screen_object_list(struct recovery_list_work *rlw,
 		for (j = 0; j < nr_objs; j++) {
 			if (!vnode_is_local(vnodes[j]))
 				continue;
-			if (bsearch(&oids[i], rlw->oids, old_count,
-				    sizeof(uint64_t), obj_cmp))
+			if (typesafe_bsearch(&oids[i], rlw->oids, old_count,
+					     obj_cmp))
 				continue;
 
 			rlw->oids[rlw->count++] = oids[i];
@@ -728,7 +726,7 @@ static void screen_object_list(struct recovery_list_work *rlw,
 		}
 	}
 
-	qsort(rlw->oids, rlw->count, sizeof(uint64_t), obj_cmp);
+	typesafe_qsort(rlw->oids, rlw->count, obj_cmp);
 }
 
 /* Prepare the object list that belongs to this node */
-- 
1.7.9.5




More information about the sheepdog mailing list