From 102b3189f786194f1a78b53077cf9a4e100ee2e3 Mon Sep 17 00:00:00 2001
From: Mathieu Desnoyers <mathieu.desnoyers@efficios.com>
Date: Mon, 10 Jun 2013 22:05:50 -0400
Subject: [PATCH] rcuja: fix iteration and lookup below/above equal

- fix iteration on entirely filled uint64_t keyspace: we need to reserve
  UINT64_MAX as end-of-iteration marker.
- fix linear lookups below/above or equal: should not re-read the
  pointer.

Signed-off-by: Mathieu Desnoyers <mathieu.desnoyers@efficios.com>
---
 rcuja/rcuja.c | 24 ++++++++++--------------
 urcu/rcuja.h  | 14 +++++++++++---
 2 files changed, 21 insertions(+), 17 deletions(-)

diff --git a/rcuja/rcuja.c b/rcuja/rcuja.c
index a791d5b..a3acfbc 100644
--- a/rcuja/rcuja.c
+++ b/rcuja/rcuja.c
@@ -370,9 +370,9 @@ struct cds_ja_inode_flag *ja_linear_node_get_direction(const struct cds_ja_type
 	uint8_t nr_child;
 	uint8_t *values;
 	struct cds_ja_inode_flag **pointers;
-	struct cds_ja_inode_flag *ptr = NULL;
+	struct cds_ja_inode_flag *ptr, *match_ptr = NULL;
 	unsigned int i;
-	int match_idx = -1, match_v;
+	int match_v;
 
 	assert(type->type_class == RCU_JA_LINEAR || type->type_class == RCU_JA_POOL);
 	assert(dir == JA_LEFT || dir == JA_RIGHT);
@@ -400,24 +400,23 @@ struct cds_ja_inode_flag *ja_linear_node_get_direction(const struct cds_ja_type
 		if (dir == JA_LEFT) {
 			if ((int) v < n && (int) v > match_v) {
 				match_v = v;
-				match_idx = i;
+				match_ptr = ptr;
 			}
 		} else {
 			if ((int) v > n && (int) v < match_v) {
 				match_v = v;
-				match_idx = i;
+				match_ptr = ptr;
 			}
 		}
 	}
 
-	if (match_idx < 0) {
+	if (!match_ptr) {
 		return NULL;
 	}
 	assert(match_v >= 0 && match_v < JA_ENTRY_PER_NODE);
 
 	*result_key = (uint8_t) match_v;
-	ptr = rcu_dereference(pointers[match_idx]);
-	return ptr;
+	return match_ptr;
 }
 
 static
@@ -1784,7 +1783,7 @@ struct cds_ja_node *cds_ja_lookup(struct cds_ja *ja, uint64_t key)
 	unsigned int tree_depth, i;
 	struct cds_ja_inode_flag *node_flag;
 
-	if (caa_unlikely(key > ja->key_max))
+	if (caa_unlikely(key > ja->key_max || key == UINT64_MAX))
 		return NULL;
 	tree_depth = ja->tree_depth;
 	node_flag = rcu_dereference(ja->root);
@@ -1820,11 +1819,8 @@ struct cds_ja_node *cds_ja_lookup_inequality(struct cds_ja *ja, uint64_t key,
 
 	switch (mode) {
 	case JA_LOOKUP_BE:
-		if (caa_unlikely(key > ja->key_max))
-			return NULL;
-		break;
 	case JA_LOOKUP_AE:
-		if (caa_unlikely(key > ja->key_max))
+		if (caa_unlikely(key > ja->key_max || key == UINT64_MAX))
 			return NULL;
 		break;
 	default:
@@ -2202,7 +2198,7 @@ int _cds_ja_add(struct cds_ja *ja, uint64_t key,
 		**node_flag_ptr;
 	int ret;
 
-	if (caa_unlikely(key > ja->key_max)) {
+	if (caa_unlikely(key > ja->key_max || key == UINT64_MAX)) {
 		return -EINVAL;
 	}
 	tree_depth = ja->tree_depth;
@@ -2533,7 +2529,7 @@ int cds_ja_del(struct cds_ja *ja, uint64_t key,
 	int nr_snapshot;
 	int ret;
 
-	if (caa_unlikely(key > ja->key_max))
+	if (caa_unlikely(key > ja->key_max || key == UINT64_MAX))
 		return -EINVAL;
 	tree_depth = ja->tree_depth;
 
diff --git a/urcu/rcuja.h b/urcu/rcuja.h
index 164b05a..82e272b 100644
--- a/urcu/rcuja.h
+++ b/urcu/rcuja.h
@@ -56,6 +56,10 @@ void cds_ja_node_init(struct cds_ja_node *node)
 {
 }
 
+/*
+ * Note: key UINT64_MAX is reserved internally for iteration.
+ */
+
 /*
  * cds_ja_lookup - look up by key.
  * @ja: the Judy array.
@@ -202,7 +206,9 @@ int cds_ja_destroy(struct cds_ja *ja);
  */
 #define cds_ja_for_each_key_rcu(ja, key, pos)				\
 	for ((key) = 0;							\
-		((pos) = cds_ja_lookup_above_equal(ja, key, &(key))); )
+		((key) != UINT64_MAX ?					\
+			((pos) = cds_ja_lookup_above_equal(ja, key, &(key))) : 0); \
+		(key)++)
 
 /*
  * cds_ja_for_each_key_prev_rcu: Iterate over all keys in descending order.
@@ -216,8 +222,10 @@ int cds_ja_destroy(struct cds_ja *ja);
  * Safe against node removal during iteration.
  */
 #define cds_ja_for_each_key_prev_rcu(ja, key, pos)			\
-	for ((key) = UINT64_MAX;					\
-		((pos) = cds_ja_lookup_below_equal(ja, key, &(key))); )
+	for ((key) = UINT64_MAX - 1;					\
+		((key) != UINT64_MAX ?					\
+			((pos) = cds_ja_lookup_below_equal(ja, key, &(key))) : 0); \
+		(key)--)
 
 #ifdef __cplusplus
 }
-- 
2.34.1