Fix: change order of _cds_lfht_new_with_alloc parameters The "flavor" parameter should come before the "alloc" parameter to match the order of cds_lfht_new_with_flavor_alloc() parameters. Signed-off-by: Mathieu Desnoyers <mathieu.desnoyers@efficios.com> Change-Id: Ia704a0fd9cb90af966464e25e6202fed1a952eed
Add support for custom memory allocators for rculfhash The current implementation of rculfhash relies on calloc() to allocate memory for its buckets. This can in some cases lead to latency spikes when accessing the hash table, which can be avoided by using an optimized custom memory allocator. However, there is currently no way of replacing the default allocator with a custom one. This commit allows custom allocators to be used during the table initialization. The default behavior of the hash table remains unaffected, by using the stdlib calloc() and free(), if no custom allocator is given. Signed-off-by: Xenofon Foukas <fon1989@gmail.com> Signed-off-by: Mathieu Desnoyers <mathieu.desnoyers@efficios.com> Change-Id: Id9a405e5dc42e5564ff8623394c86056a4d1ff48
cleanup: use an enum for the error states of nr_cpus_mask Using an enum with labels for error states instead of literal values will make the code easier to read and understand. Change-Id: I4558e17ccb45ab40515bb516af840b2852ee8fc3 Signed-off-by: Michael Jeanson <mjeanson@efficios.com> Signed-off-by: Mathieu Desnoyers <mathieu.desnoyers@efficios.com>
rculfhash: Only pass integral types to atomic builtins Clang expects the pointers passed to atomic builtins to be integral. Fix this by casting nodes address to uintptr_t *. Change-Id: Ifb8833c493df849a542a22f0bb2baeeb85be0297 Signed-off-by: Olivier Dion <odion@efficios.com> Signed-off-by: Mathieu Desnoyers <mathieu.desnoyers@efficios.com>
Complete removal of urcu-signal flavor This commit completes removal of the urcu-signal flavor. Users can migrate to liburcu-memb with a kernel implementing the membarrier(2) system call to have similar read-side performance without requiring use of a reserved signal, and with improved grace period performance. Signed-off-by: Mathieu Desnoyers <mathieu.desnoyers@efficios.com> Change-Id: I75b9171e705b9b2ef4c8eeabe6164e5587816fb4
urcu/annotate: Add CMM annotation The CMM annotation is highly experimental and not meant to be used by user for now, even though it is exposed in the public API since some parts of the liburcu public API require those annotations. The main primitive is the cmm_annotate_t which denotes a group of memory operations associated with a memory barrier. A group follows a state machine, starting from the `CMM_ANNOTATE_VOID' state. The following are the only valid transitions: CMM_ANNOTATE_VOID -> CMM_ANNOTATE_MB (acquire & release MB) CMM_ANNOTATE_VOID -> CMM_ANNOTATE_LOAD (acquire memory) CMM_ANNOTATE_LOAD -> CMM_ANNOTATE_MB (acquire MB) The macro `cmm_annotate_define(name)' can be used to create an annotation object on the stack. The rest of the `cmm_annotate_*' macros can be used to change the state of the group after validating that the transition is allowed. Some of these macros also inject TSAN annotations to help it understand the flow of events in the program since it does not currently support thread fence. Sometime, a single memory access does not need to be associated with a group. In the case, the acquire/release macros variant without the `group' infix can be used to annotate memory accesses. Note that TSAN can not be used on the liburcu-signal flavor. This is because TSAN hijacks calls to sigaction(3) and places its own handler that will deliver the signal to the application at a synchronization point. Thus, the usage of TSAN on the signal flavor is undefined behavior. However, there's at least one known behavior which is a deadlock between readers that want to unregister them-self by locking the `rcu_registry_lock' while a synchronize RCU is made on the writer side which has already locked that mutex until all the registered readers execute a memory barrier in a signal handler defined by liburcu-signal. However, TSAN will not call the registered handler while waiting on the mutex. Therefore, the writer spin infinitely on pthread_kill(3p) because the reader simply never complete the handshake. See the deadlock minimal reproducer below. Deadlock reproducer: ``` #include <poll.h> #include <signal.h> #include <pthread.h> #define SIGURCU SIGUSR1 static pthread_mutex_t rcu_registry_lock = PTHREAD_MUTEX_INITIALIZER; static int need_mb = 0; static void *reader_side(void *nil) { (void) nil; pthread_mutex_lock(&rcu_registry_lock); pthread_mutex_unlock(&rcu_registry_lock); return NULL; } static void writer_side(pthread_t reader) { __atomic_store_n(&need_mb, 1, __ATOMIC_RELEASE); while (__atomic_load_n(&need_mb, __ATOMIC_ACQUIRE)) { pthread_kill(reader, SIGURCU); (void) poll(NULL, 0, 1); } pthread_mutex_unlock(&rcu_registry_lock); pthread_join(reader, NULL); } static void sigrcu_handler(int signo, siginfo_t *siginfo, void *context) { (void) signo; (void) siginfo; (void) context; __atomic_store_n(&need_mb, 0, __ATOMIC_SEQ_CST); } static void install_signal(void) { struct sigaction act; act.sa_sigaction = sigrcu_handler; act.sa_flags = SA_SIGINFO | SA_RESTART; sigemptyset(&act.sa_mask); (void) sigaction(SIGURCU, &act, NULL); } int main(void) { pthread_t th; install_signal(); pthread_mutex_lock(&rcu_registry_lock); pthread_create(&th, NULL, reader_side, NULL); writer_side(th); return 0; } ``` Change-Id: I9c234bb311cc0f82ea9dbefdf4fee07047ab93f9 Co-authored-by: Mathieu Desnoyers <mathieu.desnoyers@efficios.com> Signed-off-by: Olivier Dion <odion@efficios.com> Signed-off-by: Mathieu Desnoyers <mathieu.desnoyers@efficios.com>
src: use SPDX identifiers The SPDX identifiers [1] are a legally binding shorthand, which can be used instead of the full boiler plate text. This is another step towards implementing the full REUSE spec [2] to help with copyright and licensing audits and compliance. This will reduce a lot a manual work required for the licensing audit required in Debian on each update. [1] https://spdx.org/ids-how [2] https://reuse.software/tutorial/ Change-Id: Ia28ed8c14984ac9acd140ef544fd6e09b96fb03b Signed-off-by: Michael Jeanson <mjeanson@efficios.com> Signed-off-by: Mathieu Desnoyers <mathieu.desnoyers@efficios.com>
Fix: rculfhash: urcu_die() takes positive error value Found by Coverity: ** CID 1504537: Error handling issues (NEGATIVE_RETURNS) /src/rculfhash.c: 1934 in do_auto_resize_destroy_cb() Signed-off-by: Mathieu Desnoyers <mathieu.desnoyers@efficios.com> Change-Id: I6c130fc18fc36da8d0ed13188cc9415e7ee6104b
Fix: auto-resize hash table destroy deadlock Fix a deadlock for auto-resize hash tables when cds_lfht_destroy is called with RCU read-side lock held. Example stack track of a hang: Thread 2 (Thread 0x7f21ba876700 (LWP 26114)): #0 syscall () at ../sysdeps/unix/sysv/linux/x86_64/syscall.S:38 #1 0x00007f21beba7aa0 in futex (val3=0, uaddr2=0x0, timeout=0x0, val=-1, op=0, uaddr=0x7f21bedac308 <urcu_memb_gp+8>) at ../include/urcu/futex.h:81 #2 futex_noasync (timeout=0x0, uaddr2=0x0, val3=0, val=-1, op=0, uaddr=0x7f21bedac308 <urcu_memb_gp+8>) at ../include/urcu/futex.h:90 #3 wait_gp () at urcu.c:265 #4 wait_for_readers (input_readers=input_readers@entry=0x7f21ba8751b0, cur_snap_readers=cur_snap_readers@entry=0x0, qsreaders=qsreaders@entry=0x7f21ba8751c0) at urcu.c:357 #5 0x00007f21beba8339 in urcu_memb_synchronize_rcu () at urcu.c:498 #6 0x00007f21be99f93f in fini_table (last_order=<optimized out>, first_order=13, ht=0x5651cec75400) at rculfhash.c:1489 #7 _do_cds_lfht_shrink (new_size=<optimized out>, old_size=<optimized out>, ht=0x5651cec75400) at rculfhash.c:2001 #8 _do_cds_lfht_resize (ht=ht@entry=0x5651cec75400) at rculfhash.c:2023 #9 0x00007f21be99fa26 in do_resize_cb (work=0x5651e20621a0) at rculfhash.c:2063 #10 0x00007f21be99dbfd in workqueue_thread (arg=0x5651cec74a00) at workqueue.c:234 #11 0x00007f21bd7c06db in start_thread (arg=0x7f21ba876700) at pthread_create.c:463 #12 0x00007f21bd4e961f in clone () at ../sysdeps/unix/sysv/linux/x86_64/clone.S:95 Thread 1 (Thread 0x7f21bf285300 (LWP 26098)): #0 syscall () at ../sysdeps/unix/sysv/linux/x86_64/syscall.S:38 #1 0x00007f21be99d8b7 in futex (val3=0, uaddr2=0x0, timeout=0x0, val=-1, op=0, uaddr=0x5651d8b38584) at ../include/urcu/futex.h:81 #2 futex_async (timeout=0x0, uaddr2=0x0, val3=0, val=-1, op=0, uaddr=0x5651d8b38584) at ../include/urcu/futex.h:113 #3 futex_wait (futex=futex@entry=0x5651d8b38584) at workqueue.c:135 #4 0x00007f21be99e2c8 in urcu_workqueue_wait_completion (completion=completion@entry=0x5651d8b38580) at workqueue.c:423 #5 0x00007f21be99e3f9 in urcu_workqueue_flush_queued_work (workqueue=0x5651cec74a00) at workqueue.c:452 #6 0x00007f21be9a0c83 in cds_lfht_destroy (ht=0x5651d8b2fcf0, attr=attr@entry=0x0) at rculfhash.c:1906 This deadlock is easy to reproduce when rapidly adding a large number of entries in the cds_lfht, removing them, and calling cds_lfht_destroy(). The deadlock will occur if the call to cds_lfht_destroy() takes place while a resize of the hash table is ongoing. Fix this by moving the teardown of the lfht worker thread to libcds library destructor, so it does not have to wait on synchronize_rcu from a resize callback from within a read-side critical section. As a consequence, the atfork callbacks are left registered within each urcu flavor for which a resizeable hash table is created until the end of the executable lifetime. The other part of the fix is to move the hash table destruction to the worker thread for auto-resize hash tables. This prevents having to wait for resize callbacks from RCU read-side critical section. This is guaranteed by the fact that the worker thread serializes previously queued resize callbacks before the destroy callback. Signed-off-by: Mathieu Desnoyers <mathieu.desnoyers@efficios.com> Change-Id: If8b1c3c8063dc7b9846dc5c3fc452efd917eab4d
rculfhash: Include rculfhash-internal.h from local directory Use double quotes rather than angle brackets to include this local header file. This fixes build scenarios where the liburcu build is used from cmake. Signed-off-by: Mathieu Desnoyers <mathieu.desnoyers@efficios.com> Change-Id: Iad6c9765ecc409c8df3a659975c97a3c068d5c0a
Disable signals in URCU background threads Applications using signalfd depend on signals being blocked in all threads of the process, otherwise threads with unblocked signals can receive them and starve the signalfd. While some threads in URCU do block signals (e.g. workqueue worker for rculfhash), the call_rcu, defer_rcu, and rculfhash partition_resize_helper threads do not. Always block all signals before creating threads, and only unblock SIGRCU when registering a urcu-signal thread. Restore the SIGRCU signal to its pre-registration blocked state on unregistration. For rculfhash, cds_lfht_worker_init can be removed, because its only effect is to block all signals except SIGRCU. Blocking all signals is already done by the workqueue code, and unbloking SIGRCU is now done by the urcu signal flavor thread regisration. Co-developed-by: Eric Wong <normalperson@yhbt.net> Signed-off-by: Eric Wong <normalperson@yhbt.net> Signed-off-by: Mathieu Desnoyers <mathieu.desnoyers@efficios.com> Change-Id: If78346b15bdc287417b992a8963098c6ea0dc7d2
fix: sysconf(_SC_NPROCESSORS_CONF) can be less than max cpu id We rely on sysconf(_SC_NPROCESSORS_CONF) to get the maximum possible number of CPUs that can be attached to the system for the lifetime of an application. As such we expect that the highest possible CPU id would be one less than the number returned by sysconf(_SC_NPROCESSORS_CONF) which is unfortunatly not always the case and can vary across libc implementations and versions. Glibc up to 2.35 will count the number of "cpuX" directories in "/sys/devices/system/cpu" which doesn't include CPUS that were hot-unplugged. This information is however provided by the Linux kernel in "/sys/devices/system/cpu/possible" in the form of a mask listing all the CPUs that could possibly be hot-plugged in the system. This patch replaces sysconf(_SC_NPROCESSORS_CONF) with an internal function that first tries parsing the possible CPU mask to extract the highest possible value and if this fails fallback to the previous behavior. Change-Id: I68dfed42ebbab02728a02eeefd4a395a22bb1bea Signed-off-by: Michael Jeanson <mjeanson@efficios.com> Signed-off-by: Mathieu Desnoyers <mathieu.desnoyers@efficios.com>
Fix: Use %lu rather than %ld to print count In ht_count_del function, the type of count variable is defined as unsigned long, so use %lu rather than %ld to print it. Signed-off-by: yaowenbin1 <yaowenbin1@huawei.com> Signed-off-by: Mathieu Desnoyers <mathieu.desnoyers@efficios.com> Change-Id: Ie2701fa0a8170b05532429b34e0f798e6f27139b
rculfhash: introduce cds_lfht_node_init_deleted Allow initializing lfht node to "removed" state to allow querying whether the node is published in a hash table before it is added to the hash table and after it has been removed from the hash table. Signed-off-by: Mathieu Desnoyers <mathieu.desnoyers@efficios.com> Change-Id: I6e364a3ea076f33e34b4c63c7b23be22b35e9bb1
Add `urcu_posix_assert()` as `assert()` replacement This macro acts like the regular `assert()` macro unless NDEBUG is defined in which case it consumes the expression and becomes a no-op. This consumption trick (see `_urcu_use_expression()` macro) prevents the compiler from warning about unused variables even when assert() are removed by the NDEBUG define. This macro is also used for the existing `urcu_assert_debug()` macro. The implementation of `_urcu_use_expression()` is inspired by the Babeltrace 2 approach. See `BT_USE_EXPR()` macro and documentation in Babeltrace commit [1]: commit 1778c2a4134647150b199b2b57130817144446b0 Author: Philippe Proulx <eeppeliteloop@gmail.com> Date: Tue Apr 21 11:15:42 2020 -0400 lib: assign a unique ID to each pre/postcond. and report it on failure All assertion macros are moved to the new urcu/assert.h file. Link: https://github.com/efficios/babeltrace/commit/1778c2a4134647150b199b2b57130817144446b0 [1] Signed-off-by: Francis Deslauriers <francis.deslauriers@efficios.com> Signed-off-by: Mathieu Desnoyers <mathieu.desnoyers@efficios.com> Change-Id: If60ce2d3f45ea8f5ec1dbb92fb43f83fd9f8102b
cleanup: explicitly mark unused parameters (-Wunused-parameter) Add the 'unused' attribute to function parameters that are unused to allow turning on -Wunused-parameter and distinguish unused parameters that are actual errors. Change-Id: Ie585e37f9d38718543a31aee2e7ab3428cdfd0a5 Signed-off-by: Michael Jeanson <mjeanson@efficios.com> Signed-off-by: Mathieu Desnoyers <mathieu.desnoyers@efficios.com>
cleanup: all functions have declarations (-Wmissing-prototypes) Make sure that all non-static functions have a declaration. Change-Id: Ie1596ad4ba876183862e51508c8bd7fc0451fc5e Signed-off-by: Michael Jeanson <mjeanson@efficios.com> Signed-off-by: Mathieu Desnoyers <mathieu.desnoyers@efficios.com>
Static arch and uatomic headers Replace the somewhat hackish symlinking of architecture specific headers at configure time with compile time detection using compiler defines. This would allow sharing headers in a multi-arch environment and reduce the build system complexity. Change-Id: I4900a18dab70bb0e51d1a8500581a445acd44cdf Signed-off-by: Michael Jeanson <mjeanson@efficios.com> Signed-off-by: Mathieu Desnoyers <mathieu.desnoyers@efficios.com>
cds_lfht_is_node_deleted parameter can be marked const Mark the cds_lfht_node pointer parameter of cds_lfht_is_node_deleted as const. The fact that this parameter is mutable makes it harder to use liburcu in const-correct code. Signed-off-by: Jérémie Galarneau <jeremie.galarneau@efficios.com> Signed-off-by: Mathieu Desnoyers <mathieu.desnoyers@efficios.com>
Fix: provide errno as argument to urcu_die() commit 1a990de3add "Fix: rculfhash worker needs to unblock to SIGRCU" provides "ret" (-1) as argument to urcu_die(), but should rather provide errno. Reported by Coverity: ** CID 1405700: Error handling issues (NEGATIVE_RETURNS) /src/rculfhash.c: 2171 in cds_lfht_worker_init() Signed-off-by: Mathieu Desnoyers <mathieu.desnoyers@efficios.com>