From mboxrd@z Thu Jan 1 00:00:00 1970 From: paulmck@linux.vnet.ibm.com (Paul E. McKenney) Date: Tue, 1 Nov 2011 06:20:39 -0700 Subject: [ltt-dev] Review of rculfhash Message-ID: <20111101132039.GA3543@linux.vnet.ibm.com> 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 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);