rculfhash: implement iterator debugging config option

Building liburcu with --enable-cds-lfht-iter-debug and rebuilding
application to match the ABI change allows finding cases where the
hash table iterator is re-purposed to be used on a different hash
table while still being used to iterate on a hash table.

This is a common programming mistake that happens often enough
to justify creating a debugging mode to track this automatically.

Signed-off-by: Mathieu Desnoyers <mathieu.desnoyers@efficios.com>

diff --git a/README.md b/README.md
index 7a33cd7ea044c138618d886f50325661ff757105..601703bdf6209af39c9e27e47a9d0c9d3e2d6b13 100644 (file)
--- a/README.md
+++ b/README.md
@@ -410,6 +410,20 @@ systems can be disabled with:
 theoretically yielding slightly better performance.
 
 
 theoretically yielding slightly better performance.
 
 

+### Usage of `--enable-cds-lfht-iter-debug`
+
+By default the library is configured with extra debugging checks for
+lock-free hash table iterator traversal disabled.
+
+Building liburcu with --enable-cds-lfht-iter-debug and rebuilding
+application to match the ABI change allows finding cases where the hash
+table iterator is re-purposed to be used on a different hash table while
+still being used to iterate on a hash table.
+
+This option alters the rculfhash ABI. Make sure to compile both library
+and application with matching configuration.
+
+

 Make targets
 ------------
 
 Make targets
 ------------
 

diff --git a/configure.ac b/configure.ac
index 4d1a1dfe659beffbbaf9f24a39dac775ca4348c6..017da5a552508718201642785f0fb9d1b0c80450 100644 (file)
--- a/configure.ac
+++ b/configure.ac
@@ -29,6 +29,7 @@ AH_TEMPLATE([CONFIG_RCU_TLS], [TLS provided by the compiler.])
 AH_TEMPLATE([CONFIG_RCU_HAVE_CLOCK_GETTIME], [clock_gettime() is detected.])
 AH_TEMPLATE([CONFIG_RCU_FORCE_SYS_MEMBARRIER], [Require the operating system to support the membarrier system call for default and bulletproof flavors.])
 AH_TEMPLATE([CONFIG_RCU_DEBUG], [Enable internal debugging self-checks. Introduce performance penalty.])
 AH_TEMPLATE([CONFIG_RCU_HAVE_CLOCK_GETTIME], [clock_gettime() is detected.])
 AH_TEMPLATE([CONFIG_RCU_FORCE_SYS_MEMBARRIER], [Require the operating system to support the membarrier system call for default and bulletproof flavors.])
 AH_TEMPLATE([CONFIG_RCU_DEBUG], [Enable internal debugging self-checks. Introduce performance penalty.])

+AH_TEMPLATE([CONFIG_CDS_LFHT_ITER_DEBUG], [Enable extra debugging checks for lock-free hash table iterator traversal. Alters the rculfhash ABI. Make sure to compile both library and application with matching configuration.])

 
 # Allow requiring the operating system to support the membarrier system
 # call. Applies to default and bulletproof flavors.
 
 # Allow requiring the operating system to support the membarrier system
 # call. Applies to default and bulletproof flavors.


@@ -268,6 +269,13 @@ AS_IF([test "x$enable_rcu_debug" = "xyes"], [
        AC_DEFINE([CONFIG_RCU_DEBUG], [1])
 ])
 
        AC_DEFINE([CONFIG_RCU_DEBUG], [1])
 ])
 

+# rculfhash iterator debugging
+AC_ARG_ENABLE([cds-lfht-iter-debug],
+      AS_HELP_STRING([--enable-cds-lfht-iter-debug], [Enable extra debugging checks for lock-free hash table iterator traversal. Alters the rculfhash ABI. Make sure to compile both library and application with matching configuration.]))
+AS_IF([test "x$enable_cds_lfht_iter_debug" = "xyes"], [
+       AC_DEFINE([CONFIG_CDS_LFHT_ITER_DEBUG], [1])
+])
+

 # From the sched_setaffinity(2)'s man page:
 # ~~~~
 # The CPU affinity system calls were introduced in Linux kernel 2.5.8.
 # From the sched_setaffinity(2)'s man page:
 # ~~~~
 # The CPU affinity system calls were introduced in Linux kernel 2.5.8.


@@ -508,6 +516,10 @@ PPRINT_PROP_BOOL([Require membarrier], $value)
 test "x$enable_rcu_debug" = "xyes" && value=1 || value=0
 PPRINT_PROP_BOOL([Internal debugging], $value)
 
 test "x$enable_rcu_debug" = "xyes" && value=1 || value=0
 PPRINT_PROP_BOOL([Internal debugging], $value)
 

+# rculfhash iterator debug enabled/disabled
+test "x$enable_cds_lfht_iter_debug" = "xyes" && value=1 || value=0
+PPRINT_PROP_BOOL([Lock-free hash table iterator debugging], $value)
+

 PPRINT_PROP_BOOL([Multi-flavor support], 1)
 
 report_bindir="`eval eval echo $bindir`"
 PPRINT_PROP_BOOL([Multi-flavor support], 1)
 
 report_bindir="`eval eval echo $bindir`"

diff --git a/include/urcu/config.h.in b/include/urcu/config.h.in
index 9f2aa99716c6c20415190dae80c28f4b514bbfb0..15012679f333b273da9b91e3038db5bc35a5be42 100644 (file)
--- a/include/urcu/config.h.in
+++ b/include/urcu/config.h.in
@@ -33,3 +33,7 @@
 
 /* Expose multi-flavor support */
 #define CONFIG_RCU_MULTIFLAVOR 1
 
 /* Expose multi-flavor support */
 #define CONFIG_RCU_MULTIFLAVOR 1

+
+/* Enable extra debugging checks for lock-free hash table iterator
+   traversal. */
+#undef CONFIG_CDS_LFHT_ITER_DEBUG

diff --git a/include/urcu/rculfhash.h b/include/urcu/rculfhash.h
index 292fc0d9fc9c0fadcdd370864fe6ca249140a298..cbf513ec848c37744bb084a72ff66dd19f8c1816 100644 (file)
--- a/include/urcu/rculfhash.h
+++ b/include/urcu/rculfhash.h
@@ -27,6 +27,7 @@
  * _after_ including your URCU flavor.
  */
 
  * _after_ including your URCU flavor.
  */
 

+#include <urcu/config.h>

 #include <stdint.h>
 #include <pthread.h>
 #include <urcu/compiler.h>
 #include <stdint.h>
 #include <pthread.h>
 #include <urcu/compiler.h>


@@ -35,6 +36,8 @@
 extern "C" {
 #endif
 
 extern "C" {
 #endif
 

+struct cds_lfht;
+

 /*
  * cds_lfht_node: Contains the next pointers and reverse-hash
  * value required for lookup and traversal of the hash table.
 /*
  * cds_lfht_node: Contains the next pointers and reverse-hash
  * value required for lookup and traversal of the hash table.


@@ -65,6 +68,18 @@ struct cds_lfht_node {
 /* cds_lfht_iter: Used to track state while traversing a hash chain. */
 struct cds_lfht_iter {
        struct cds_lfht_node *node, *next;
 /* cds_lfht_iter: Used to track state while traversing a hash chain. */
 struct cds_lfht_iter {
        struct cds_lfht_node *node, *next;

+       /*
+        * For debugging purposes, build both API users and rculfhash
+        * library with CDS_LFHT_ITER_DEBUG defined. This enables extra
+        * consistency checks for calls to a cds_lfht_next() or
+        * cds_lfht_next_duplicate() after the iterator has been
+        * re-purposed to iterate on a different hash table. This is a
+        * common programming mistake when performing hash table lookup
+        * nested in a hash table traversal.
+        */
+#ifdef CONFIG_CDS_LFHT_ITER_DEBUG
+       struct cds_lfht *lfht;
+#endif

 };
 
 static inline
 };
 
 static inline


@@ -73,7 +88,6 @@ struct cds_lfht_node *cds_lfht_iter_get_node(struct cds_lfht_iter *iter)
        return iter->node;
 }
 
        return iter->node;
 }
 

-struct cds_lfht;

 struct rcu_flavor_struct;
 
 /*
 struct rcu_flavor_struct;
 
 /*

diff --git a/src/rculfhash.c b/src/rculfhash.c
index b63a0a6c420652a6ce557b31e35602d10ed80793..8942c80ba8c6e8eb5f155cd49e10c22d8455ee23 100644 (file)
--- a/src/rculfhash.c
+++ b/src/rculfhash.c
@@ -380,6 +380,27 @@ static int cds_lfht_workqueue_atfork_nesting;
 static void cds_lfht_init_worker(const struct rcu_flavor_struct *flavor);
 static void cds_lfht_fini_worker(const struct rcu_flavor_struct *flavor);
 
 static void cds_lfht_init_worker(const struct rcu_flavor_struct *flavor);
 static void cds_lfht_fini_worker(const struct rcu_flavor_struct *flavor);
 

+#ifdef CONFIG_CDS_LFHT_ITER_DEBUG
+
+static
+void cds_lfht_iter_debug_set_ht(struct cds_lfht *ht, struct cds_lfht_iter *iter)
+{
+       iter->lfht = ht;
+}
+
+#define cds_lfht_iter_debug_assert(...)                assert(__VA_ARGS__)
+
+#else
+
+static
+void cds_lfht_iter_debug_set_ht(struct cds_lfht *ht, struct cds_lfht_iter *iter)
+{
+}
+
+#define cds_lfht_iter_debug_assert(...)
+
+#endif
+

 /*
  * Algorithm to reverse bits in a word by lookup table, extended to
  * 64-bit words.
 /*
  * Algorithm to reverse bits in a word by lookup table, extended to
  * 64-bit words.


@@ -1068,7 +1089,13 @@ void _cds_lfht_add(struct cds_lfht *ht,
                        if (unique_ret
                            && !is_bucket(next)
                            && clear_flag(iter)->reverse_hash == node->reverse_hash) {
                        if (unique_ret
                            && !is_bucket(next)
                            && clear_flag(iter)->reverse_hash == node->reverse_hash) {

-                               struct cds_lfht_iter d_iter = { .node = node, .next = iter, };
+                               struct cds_lfht_iter d_iter = {
+                                       .node = node,
+                                       .next = iter,
+#ifdef CONFIG_CDS_LFHT_ITER_DEBUG
+                                       .lfht = ht,
+#endif
+                               };

 
                                /*
                                 * uniquely adding inserts the node as the first
 
                                /*
                                 * uniquely adding inserts the node as the first


@@ -1600,6 +1627,8 @@ void cds_lfht_lookup(struct cds_lfht *ht, unsigned long hash,
        struct cds_lfht_node *node, *next, *bucket;
        unsigned long reverse_hash, size;
 
        struct cds_lfht_node *node, *next, *bucket;
        unsigned long reverse_hash, size;
 

+       cds_lfht_iter_debug_set_ht(ht, iter);
+

        reverse_hash = bit_reverse_ulong(hash);
 
        size = rcu_dereference(ht->size);
        reverse_hash = bit_reverse_ulong(hash);
 
        size = rcu_dereference(ht->size);


@@ -1637,6 +1666,7 @@ void cds_lfht_next_duplicate(struct cds_lfht *ht, cds_lfht_match_fct match,
        struct cds_lfht_node *node, *next;
        unsigned long reverse_hash;
 
        struct cds_lfht_node *node, *next;
        unsigned long reverse_hash;
 

+       cds_lfht_iter_debug_assert(ht == iter->lfht);

        node = iter->node;
        reverse_hash = node->reverse_hash;
        next = iter->next;
        node = iter->node;
        reverse_hash = node->reverse_hash;
        next = iter->next;


@@ -1668,6 +1698,7 @@ void cds_lfht_next(struct cds_lfht *ht, struct cds_lfht_iter *iter)
 {
        struct cds_lfht_node *node, *next;
 
 {
        struct cds_lfht_node *node, *next;
 

+       cds_lfht_iter_debug_assert(ht == iter->lfht);

        node = clear_flag(iter->next);
        for (;;) {
                if (caa_unlikely(is_end(node))) {
        node = clear_flag(iter->next);
        for (;;) {
                if (caa_unlikely(is_end(node))) {


@@ -1688,6 +1719,7 @@ void cds_lfht_next(struct cds_lfht *ht, struct cds_lfht_iter *iter)
 
 void cds_lfht_first(struct cds_lfht *ht, struct cds_lfht_iter *iter)
 {
 
 void cds_lfht_first(struct cds_lfht *ht, struct cds_lfht_iter *iter)
 {

+       cds_lfht_iter_debug_set_ht(ht, iter);

        /*
         * Get next after first bucket node. The first bucket node is the
         * first node of the linked list.
        /*
         * Get next after first bucket node. The first bucket node is the
         * first node of the linked list.