X-Git-Url: http://git.lttng.org/?a=blobdiff_plain;f=rcuja%2Frcuja.c;h=0171f2d80ff5db9ef7f7588d3d7b586d46896ac8;hb=2514605a40babb8d02e05b9533974cc08adcf93c;hp=6c7c1e864f063a8adb9a657536622ef8f6cbe54c;hpb=354981c2381634c1e79872a98d979f2faebeee0e;p=urcu.git

diff --git a/rcuja/rcuja.c b/rcuja/rcuja.c
index 6c7c1e8..0171f2d 100644
--- a/rcuja/rcuja.c
+++ b/rcuja/rcuja.c
@@ -34,7 +34,6 @@
 #include <stdint.h>
 
 #include "rcuja-internal.h"
-#include "bitfield.h"
 
 #ifndef abs
 #define abs_int(a)	((int) (a) > 0 ? (int) (a) : -((int) (a)))
@@ -370,6 +369,43 @@ struct cds_ja_inode_flag *ja_linear_node_get_nth(const struct cds_ja_type *type,
 	return ptr;
 }
 
+static
+struct cds_ja_inode_flag *ja_linear_node_get_left(const struct cds_ja_type *type,
+		struct cds_ja_inode *node,
+		unsigned int n)
+{
+	uint8_t nr_child;
+	uint8_t *values;
+	struct cds_ja_inode_flag **pointers;
+	struct cds_ja_inode_flag *ptr;
+	unsigned int i, match_idx;
+	int match_v = -1;
+
+	assert(type->type_class == RCU_JA_LINEAR || type->type_class == RCU_JA_POOL);
+
+	nr_child = ja_linear_node_get_nr_child(type, node);
+	cmm_smp_rmb();	/* read nr_child before values and pointers */
+	assert(nr_child <= type->max_linear_child);
+	assert(type->type_class != RCU_JA_LINEAR || nr_child >= type->min_child);
+
+	values = &node->u.data[1];
+	for (i = 0; i < nr_child; i++) {
+		unsigned int v;
+
+		v = CMM_LOAD_SHARED(values[i]);
+		if (v < n && (int) v > match_v) {
+			match_v = v;
+			match_idx = i;
+		}
+	}
+	if (match_v < 0) {
+		return NULL;
+	}
+	pointers = (struct cds_ja_inode_flag **) align_ptr_size(&values[type->max_linear_child]);
+	ptr = rcu_dereference(pointers[match_idx]);
+	return ptr;
+}
+
 static
 void ja_linear_node_get_ith_pos(const struct cds_ja_type *type,
 		struct cds_ja_inode *node,
@@ -442,6 +478,42 @@ struct cds_ja_inode *ja_pool_node_get_ith_pool(const struct cds_ja_type *type,
 		&node->u.data[(unsigned int) i << type->pool_size_order];
 }
 
+static
+struct cds_ja_inode_flag *ja_pool_node_get_left(const struct cds_ja_type *type,
+		struct cds_ja_inode *node,
+		unsigned int n)
+{
+	unsigned int pool_nr;
+	int match_v = -1;
+	struct cds_ja_inode_flag *match_node_flag = NULL;
+
+	assert(type->type_class == RCU_JA_POOL);
+
+	for (pool_nr = 0; pool_nr < (1U << type->nr_pool_order); pool_nr++) {
+		struct cds_ja_inode *pool =
+			ja_pool_node_get_ith_pool(type,
+				node, pool_nr);
+		uint8_t nr_child =
+			ja_linear_node_get_nr_child(type, pool);
+		unsigned int j;
+
+		for (j = 0; j < nr_child; j++) {
+			struct cds_ja_inode_flag *iter;
+			uint8_t v;
+
+			ja_linear_node_get_ith_pos(type, pool,
+					j, &v, &iter);
+			if (!iter)
+				continue;
+			if (v < n && (int) v > match_v) {
+				match_v = v;
+				match_node_flag = iter;
+			}
+		}
+	}
+	return match_node_flag;
+}
+
 static
 struct cds_ja_inode_flag *ja_pigeon_node_get_nth(const struct cds_ja_type *type,
 		struct cds_ja_inode *node,
@@ -461,6 +533,30 @@ struct cds_ja_inode_flag *ja_pigeon_node_get_nth(const struct cds_ja_type *type,
 	return child_node_flag;
 }
 
+static
+struct cds_ja_inode_flag *ja_pigeon_node_get_left(const struct cds_ja_type *type,
+		struct cds_ja_inode *node,
+		unsigned int n)
+{
+	struct cds_ja_inode_flag **child_node_flag_ptr;
+	struct cds_ja_inode_flag *child_node_flag;
+	int i;
+
+	assert(type->type_class == RCU_JA_PIGEON);
+
+	/* n - 1 is first value left of n */
+	for (i = n - 1; i >= 0; i--) {
+		child_node_flag_ptr = &((struct cds_ja_inode_flag **) node->u.data)[i];
+		child_node_flag = rcu_dereference(*child_node_flag_ptr);
+		if (child_node_flag) {
+			dbg_printf("ja_pigeon_node_get_left child_node_flag %p\n",
+				child_node_flag);
+			return child_node_flag;
+		}
+	}
+	return NULL;
+}
+
 static
 struct cds_ja_inode_flag *ja_pigeon_node_get_ith_pos(const struct cds_ja_type *type,
 		struct cds_ja_inode *node,
@@ -503,6 +599,38 @@ struct cds_ja_inode_flag *ja_node_get_nth(struct cds_ja_inode_flag *node_flag,
 	}
 }
 
+static
+struct cds_ja_inode_flag *ja_node_get_left(struct cds_ja_inode_flag *node_flag,
+		unsigned int n)
+{
+	unsigned int type_index;
+	struct cds_ja_inode *node;
+	const struct cds_ja_type *type;
+
+	node = ja_node_ptr(node_flag);
+	assert(node != NULL);
+	type_index = ja_node_type(node_flag);
+	type = &ja_types[type_index];
+
+	switch (type->type_class) {
+	case RCU_JA_LINEAR:
+		return ja_linear_node_get_left(type, node, n);
+	case RCU_JA_POOL:
+		return ja_pool_node_get_left(type, node, n);
+	case RCU_JA_PIGEON:
+		return ja_pigeon_node_get_left(type, node, n);
+	default:
+		assert(0);
+		return (void *) -1UL;
+	}
+}
+
+static
+struct cds_ja_inode_flag *ja_node_get_rightmost(struct cds_ja_inode_flag *node_flag)
+{
+	return ja_node_get_left(node_flag, JA_ENTRY_PER_NODE);
+}
+
 static
 int ja_linear_node_set_nth(const struct cds_ja_type *type,
 		struct cds_ja_inode *node,
@@ -1610,6 +1738,85 @@ struct cds_hlist_head cds_ja_lookup(struct cds_ja *ja, uint64_t key)
 	return head;
 }
 
+struct cds_hlist_head cds_ja_lookup_lower_equal(struct cds_ja *ja, uint64_t key)
+{
+	int tree_depth, level;
+	struct cds_ja_inode_flag *node_flag, *cur_node_depth[JA_MAX_DEPTH];
+	struct cds_hlist_head head = { NULL };
+
+	if (caa_unlikely(key > ja->key_max || !key))
+		return head;
+
+	memset(cur_node_depth, 0, sizeof(cur_node_depth));
+	tree_depth = ja->tree_depth;
+	node_flag = rcu_dereference(ja->root);
+	cur_node_depth[0] = node_flag;
+
+	/* level 0: root node */
+	if (!ja_node_ptr(node_flag))
+		return head;
+
+	for (level = 1; level < tree_depth; level++) {
+		uint8_t iter_key;
+
+		iter_key = (uint8_t) (key >> (JA_BITS_PER_BYTE * (tree_depth - level - 1)));
+		node_flag = ja_node_get_nth(node_flag, NULL, iter_key);
+		if (!ja_node_ptr(node_flag))
+			break;
+		cur_node_depth[level] = node_flag;
+		dbg_printf("cds_ja_lookup iter key lookup %u finds node_flag %p\n",
+				(unsigned int) iter_key, node_flag);
+	}
+
+	if (level == tree_depth) {
+		/* Last level lookup succeded. We got an equal match. */
+		head.next = (struct cds_hlist_node *) node_flag;
+		return head;
+	}
+
+	/*
+	 * Find highest value left of current node.
+	 * Current node is cur_node_depth[level].
+	 * Start at current level. If we cannot find any key left of
+	 * ours, go one level up, seek highest value left of current
+	 * (recursively), and when we find one, get the rightmost child
+	 * of its rightmost child (recursively).
+	 */
+	for (; level > 0; level--) {
+		uint8_t iter_key;
+
+		iter_key = (uint8_t) (key >> (JA_BITS_PER_BYTE * (tree_depth - level - 1)));
+		node_flag = ja_node_get_left(cur_node_depth[level - 1],
+				iter_key);
+		/* If found left sibling, find rightmost child. */
+		if (ja_node_ptr(node_flag))
+			break;
+	}
+
+	if (!level) {
+		/* Reached the root and could not find a left sibling. */
+		return head;
+	}
+
+	level++;
+	/* Find rightmost child of rightmost child (recursively). */
+	for (; level < tree_depth; level++) {
+		node_flag = ja_node_get_rightmost(node_flag);
+		/* If found left sibling, find rightmost child. */
+		if (!ja_node_ptr(node_flag))
+			break;
+	}
+
+	if (level == tree_depth) {
+		/* Last level lookup succeded. We got a "lower than" match. */
+		head.next = (struct cds_hlist_node *) node_flag;
+		return head;
+	}
+
+	/* No match */
+	return head;
+}
+
 /*
  * We reached an unpopulated node. Create it and the children we need,
  * and then attach the entire branch to the current node. This may
@@ -2414,6 +2621,36 @@ void print_debug_fallback_distribution(struct cds_ja *ja)
 	}
 }
 
+static
+int ja_final_checks(struct cds_ja *ja)
+{
+	double fallback_ratio;
+	unsigned long na, nf, nr_fallback;
+	int ret = 0;
+
+	fallback_ratio = (double) uatomic_read(&ja->nr_fallback);
+	fallback_ratio /= (double) uatomic_read(&ja->nr_nodes_allocated);
+	nr_fallback = uatomic_read(&ja->nr_fallback);
+	if (nr_fallback)
+		fprintf(stderr,
+			"[warning] RCU Judy Array used %lu fallback node(s) (ratio: %g)\n",
+			uatomic_read(&ja->nr_fallback),
+			fallback_ratio);
+
+	na = uatomic_read(&ja->nr_nodes_allocated);
+	nf = uatomic_read(&ja->nr_nodes_freed);
+	dbg_printf("Nodes allocated: %lu, Nodes freed: %lu.\n", na, nf);
+	if (nr_fallback)
+		print_debug_fallback_distribution(ja);
+
+	if (na != nf) {
+		fprintf(stderr, "[error] Judy array leaked %ld nodes. Allocated: %lu, freed: %lu.\n",
+			(long) na - nf, na, nf);
+		ret = -1;
+	}
+	return ret;
+}
+
 /*
  * There should be no more concurrent add to the judy array while it is
  * being destroyed (ensured by the caller).
@@ -2437,15 +2674,7 @@ int cds_ja_destroy(struct cds_ja *ja,
 	flavor->barrier();
 
 	flavor->thread_online();
-	if (uatomic_read(&ja->nr_fallback))
-		fprintf(stderr,
-			"[warning] RCU Judy Array used %lu fallback node(s)\n",
-			uatomic_read(&ja->nr_fallback));
-	fprintf(stderr, "Nodes allocated: %lu, Nodes freed: %lu. Fallback ratio: %g\n",
-		uatomic_read(&ja->nr_nodes_allocated),
-		uatomic_read(&ja->nr_nodes_freed),
-		(double) uatomic_read(&ja->nr_fallback) / (double) uatomic_read(&ja->nr_nodes_allocated));
-	print_debug_fallback_distribution(ja);
+	ret = ja_final_checks(ja);
 	free(ja);
-	return 0;
+	return ret;
 }