From d7c76f85442125bcfef40f58b1c6fc1bd5ce4ffd Mon Sep 17 00:00:00 2001 From: Mathieu Desnoyers Date: Wed, 12 Dec 2018 21:15:32 -0500 Subject: [PATCH] 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 --- README.md | 14 ++++++++++++++ configure.ac | 12 ++++++++++++ include/urcu/config.h.in | 4 ++++ include/urcu/rculfhash.h | 16 +++++++++++++++- src/rculfhash.c | 34 +++++++++++++++++++++++++++++++++- 5 files changed, 78 insertions(+), 2 deletions(-) diff --git a/README.md b/README.md index 7a33cd7..601703b 100644 --- a/README.md +++ b/README.md @@ -410,6 +410,20 @@ systems can be disabled with: 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 ------------ diff --git a/configure.ac b/configure.ac index 4d1a1df..017da5a 100644 --- 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_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. @@ -268,6 +269,13 @@ AS_IF([test "x$enable_rcu_debug" = "xyes"], [ 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. @@ -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) +# 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`" diff --git a/include/urcu/config.h.in b/include/urcu/config.h.in index 9f2aa99..1501267 100644 --- 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 + +/* 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 292fc0d..cbf513e 100644 --- a/include/urcu/rculfhash.h +++ b/include/urcu/rculfhash.h @@ -27,6 +27,7 @@ * _after_ including your URCU flavor. */ +#include #include #include #include @@ -35,6 +36,8 @@ 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. @@ -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; + /* + * 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 @@ -73,7 +88,6 @@ struct cds_lfht_node *cds_lfht_iter_get_node(struct cds_lfht_iter *iter) return iter->node; } -struct cds_lfht; struct rcu_flavor_struct; /* diff --git a/src/rculfhash.c b/src/rculfhash.c index b63a0a6..8942c80 100644 --- 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); +#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. @@ -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) { - 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 @@ -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; + cds_lfht_iter_debug_set_ht(ht, iter); + 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; + cds_lfht_iter_debug_assert(ht == iter->lfht); 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; + cds_lfht_iter_debug_assert(ht == iter->lfht); 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) { + 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. -- 2.34.1