[ltt-dev] Review of rculfhash

[Paul E. McKenney]

Hello!

Cool stuff!!!  A few preliminary comments below, as always.  Followed by
a patch for one thing that I am confident in.

							Thanx, Paul

------------------------------------------------------------------------

urcu/rculfhash.h:

o	A comment for each structure is needed, perhaps somthing like
	the following:

	_cds_lfht_node: Contains the internal pointers and reverse-hash
		value required for traversal of the hash table.

	cds_lfht_node: Contains the full key and length required to check
		for an actual match, and also contains an rcu_head
		structure that is used by RCU to track a node through
		a given RCU grace period.  There is an instance
		of _cds_lfht_node enclosed as a field within each
		_cds_lfht_node structure.

	cds_lfht_iter: Used to track state while traversing a hash chain.

o	So the _cds_lfht_new() is not to be called by ordinary users,
	but the only call to it passes rcu_read_lock().  So the idea
	is to permit use of any of the predefined RCU implementations,
	and "void the warrantee" for any other usage?  ;-)

	Should there be an API member that returns whether or not
	a resize is in progress?  Or a callback that can be registered
	to be invoked when resizes start and finish?  This might allow
	users to have greater control over priorities.  (Note: This is
	speculation on my part.  Probably should demonstrated need
	for this before providing it.  Otherwise, gilded lilies and
	all that.)

o	Comment for cds_lfht_destroy() should state that attr may be
	NULL if the caller does not want/need to be informed of the
	value passed to cds_lfht_new().

o	Comment for cds_lfht_count_nodes() should say what approx_before,
	count, removed, and approx_after have to do with each other.
	For example, a node is either counted in *count or in
	*removed, but not both.  Probably no need to mention dummy
	nodes, as they are invisible to the caller.  As near as I can
	tell, *approx_before and *approx_after are both zero unless
	debugging.


rculfhash.c:

o	A comment for each structure is needed, perhaps somthing like
	the following:

	ht_items_count: Counters of additions and deletions used during
		stress testing.

	rcu_level: Array of pointers into the list.  Each element of
		this array is analogous to the hash-chain headers found
		in other types of hash tables.  Resizing a hash table
		involves creating a new rcu_level array that replaces
		the old array.

	rcu_table: Reference to current rcu_level array.  Includes
		size and desired new size if a resize operation is
		in progress.

	But why isn't the size kept with the array?  This would eliminate
	many of the memory barriers, for example, the cmm_smp_wmb()
	in init_table(), fini_table(), and the ones that should be
	there that is not in cds_lfht_lookup() &c.  Unless I am confused,
	the current code allows one size to be used on another array.
	(That said, not sure I yet understand the relationship of ->size
	and the various arrays.)

	cds_lfht: Top-level data structure representing a lock-free
		hash table.  Presumably defined in the .c file in
		order to make it be an opaque cookie to users.

	rcu_resize_work: ???

	partition_resize_work: ???

o	Cute trick for generating the bit-reversal table.  ;-)

o	fls_ulong(): Shouldn't the CAA_BITS_PER_lONG instead be
	CAA_BITS_PER_LONG?

o	What defines POISON_FREE?  I don't see anything but #ifdefs
	of it.

o	Any chance of a comment saying what CDS_LFHT_ACCOUNTING does?
	It seems to short-circuit ht_count_add() and ht_count_del().
	Appears to be debug-only checks of addition/deletion counts.

o	lookup_bucket()

o	ht_count_add() is interesting in that it does not appear to
	clear out ht->split_count[index].add.  The places that read it
	do not appear to mask the upper bits, either.  A comment
	explaining why this is legitimate?

	Ditto for ht_count_del().

o	cds_lfht_lookup() applies clear_flag() to the pointer twice.
	Unless I am missing something, the clear_flag() in the "if"
	statement in the loop can be omitted.

	Also, the ->next value returned does have its flag bits set.
	However, this seems to be necessary for cds_lfht_next_duplicate()
	to work correctly.

o	cds_lfht_next_duplicate() would be more clear if ->compare_fct()
	was ->is_different() or some such.  But I guess if that is an
	obstacle, you probably shouldn't be looking at this stuff in the
	first place.

	Need to document what happens if an insertion of a
	duplicate key happens between a cds_lfht_lookup() and a
	cds_lfht_next_duplicate().  Looks to me like they will be seen.


tests/test_urcu_hash.c:

o	test_compare() -- Why the return -1 if the keys are not equal in
	length, but then fail an assert if not equal to size of unsigned
	long?

------------------------------------------------------------------------

Fix CAA_BITS_PER_lONG typo

Should instead be CAA_BITS_PER_LONG.

Signed-off-by: Paul E. McKenney <paul.mckenney at linaro.org>

diff --git a/rculfhash.c b/rculfhash.c
index d786a3d..314cca8 100644
--- a/rculfhash.c
+++ b/rculfhash.c
@@ -454,7 +454,7 @@ unsigned int fls_u32(uint32_t x)
 
 unsigned int fls_ulong(unsigned long x)
 {
-#if (CAA_BITS_PER_lONG == 32)
+#if (CAA_BITS_PER_LONG == 32)
 	return fls_u32(x);
 #else
 	return fls_u64(x);