lp:urcu

Author: Olivier Dion
Author Date: 2023-08-22 20:23:17 UTC

uatomic/x86: Remove redundant memory barriers

When liburcu is configured to _not_ use atomic builtins, the
implementation of atomic operations is done using inline assembler for
each architecture.

Because we control the emitted assembler, we know whether specific
operations (e.g. lock; cmpxchg) already have an implicit memory barrier.
In those cases, emitting an explicit cmm_smp_mb() before/after the
operation is redundant and hurts performance.

Remove those redundant barriers on x86.

Change-Id: Ic1f6cfe9c2afe250946549cf6187f8fa88f5b009
Signed-off-by: Olivier Dion <odion@efficios.com>
Signed-off-by: Mathieu Desnoyers <mathieu.desnoyers@efficios.com>

Author: Sergey Fedorov
Author Date: 2024-01-05 10:44:18 UTC

ppc.h: use mftb on ppc

Older versions of GNU as do not support mftbl. The issue affects Darwin
PowerPC, as well as some older versions of NetBSD and Linux. Since mftb
is equivalent and universally understood, just use that.

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

Author: Sergey Fedorov
Author Date: 2024-01-05 10:44:18 UTC

ppc.h: use mftb on ppc

Older versions of GNU as do not support mftbl. The issue affects Darwin
PowerPC, as well as some older versions of NetBSD and Linux. Since mftb
is equivalent and universally understood, just use that.

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

Author: Mathieu Desnoyers
Author Date: 2023-02-14 15:49:33 UTC

Version 0.12.5

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

Author: Mathieu Desnoyers
Author Date: 2016-08-24 20:02:02 UTC

RCU Judy Array (rcuja) implementation

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

Author: Mathieu Desnoyers
Author Date: 2022-01-05 20:06:19 UTC

Version 0.11.4

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

Author: Mathieu Desnoyers
Author Date: 2020-04-22 12:55:50 UTC

Version 0.9.7

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

Author: Mathieu Desnoyers
Author Date: 2020-04-22 12:53:57 UTC

Version 0.10.3

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

Author: Mathieu Desnoyers
Author Date: 2018-01-23 20:16:37 UTC

Version 0.8.11

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

Author: Mathieu Desnoyers
Author Date: 2016-04-26 21:04:56 UTC

Version 0.7.17

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

Author: Mathieu Desnoyers
Author Date: 2015-05-04 17:38:34 UTC

Fix: rcuja merge fixes

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

Author: Mathieu Desnoyers
Author Date: 2014-11-13 21:17:00 UTC

Fix: call rcu should call internal RCU API

Because call rcu implementation is included within RCU flavors, calling
the RCU API goes through the API for non-LGPL code (this is a special
case for the RCU flavor implementation c file). Since this is clearly
LGPL code, we can use the inline versions.

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

Author: Mathieu Desnoyers
Author Date: 2014-11-13 21:14:36 UTC

Fix: memory leak in urcu-checker

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

Author: Mathieu Desnoyers
Author Date: 2014-10-24 11:26:55 UTC

waitqueue: add in_waitqueue field

Using the waitqueue node next pointer to figure out if the node is
within the queue worked when wfstack was used to implement the queue
stack, but unfortunately it does not keep the same semantic with
lfstack: indeed, the bottom of stack is indicated by a NULL pointer too.

Keep this state in a separate field instead to eliminate coupling
between workqueue, waitqueue and lfstack.

Note that it is OK for a worker to see "in_waitqueue" as temporarily
false when the wait node has just been pop'd from the waitqueue. It's
the opposite that we never want to happen: a worker should never see
"in_waitqueue" as false when the node is actually in the waitqueue,
because it would cause queue corruption.

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

Author: Mathieu Desnoyers
Author Date: 2013-11-11 21:50:15 UTC

Test fix: 0.6 branch does not have tls-compat.h

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

Author: Mathieu Desnoyers
Author Date: 2013-08-25 18:22:15 UTC

Implement DQ unit test

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

Author: Mathieu Desnoyers
Author Date: 2013-06-07 21:29:39 UTC

rcuja: cleanup

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

Author: Mathieu Desnoyers
Author Date: 2012-10-09 04:12:47 UTC

Revert "spinlock model: Simplify state-space"

This reverts commit a9227ee907160443d0e4b1639b274ab9278d92fa.

Need to study impact on progress.

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

Author: Mathieu Desnoyers
Author Date: 2012-02-22 00:06:52 UTC

RCU lock-free hash table: implement cds_lfht_is_node_deleted()

Some thoughts on how to use the RCU lock-free hash table brought me to
figure out that using the lock-free hash table along with a per-node
mutex is a quite interesting way to deal with lookup vs teardown
coherency.

A per-node lock can be used to protect concurrent modifications of an
entry from one another, as well as concurrent read vs modification. In
addition, if we ensure that each reader/updater of the node checks if
the node has been removed right after taking the mutex, and if we
perform the node removal from the hash table with the per-node mutex
held, we can ensure that readers/updaters will never access unlinked
data.

struct mynode {
 pthread_mutex_t mutex;
 struct cds_lfht node;
}

CPU A (lookup destroy and free) CPU B (lookup and read/modify)

                                          rcu_read_lock()
                                          mynode = caa_container_of(
                                                cds_lfht_lookup(...), ...);
                                          mutex_lock(&mynode->mutex);
                                          if (cds_lfht_is_node_deleted(
       &mynode->node))
                                               goto unlock;

                                          read/modify structure....

                                        unlock:
                                          mutex_unlock(&mynode->mutex);
                                          rcu_read_unlock()

rcu_read_lock()
mynode = caa_container_of(
        cds_lfht_lookup(...), ...);

mutex_lock(&mynode->mutex);

cds_lfht_del(ht, &mynode->node);

- perform extra teardown operations
  with side-effects, for which call_rcu
  delay is not appropriate

mutex_unlock(&mynode->mutex);
rcu_read_unlock()
call_rcu(free, mynode);

To perform this efficiently, we need an API function to return whether
the node previously looked-up has been deleted since then.

Signed-off-by: Mathieu Desnoyers <mathieu.desnoyers@efficios.com>
Acked-by: Paul E. McKenney <paulmck@linux.vnet.ibm.com>
CC: Lai Jiangshan <laijs@cn.fujitsu.com>
CC: Stephen Hemminger <shemminger@vyatta.com>

Author: Mathieu Desnoyers
Author Date: 2011-09-19 17:27:08 UTC

rculfhash: add TODO for resize worker threads

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

Author: Mathieu Desnoyers
Author Date: 2011-09-11 06:40:29 UTC

rbtree test: add missing call_rcu per-cpu threads teardown

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

Author: Mathieu Desnoyers
Author Date: 2011-09-05 11:15:30 UTC

Add no locking test option for glib hash

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

Author: Mathieu Desnoyers
Author Date: 2011-09-05 00:30:27 UTC

add test_lfs_baseline

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

Author: Mathieu Desnoyers
Author Date: 2011-09-05 00:27:56 UTC

Fix typo in makefile

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

Author: Mathieu Desnoyers
Author Date: 2011-09-03 20:23:24 UTC

rculfhash test: Check random pool size

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

Author: Mathieu Desnoyers
Author Date: 2011-08-17 10:07:44 UTC

Merge branch 'lfqueue-dev' into lfqueue-dev2

Author: Mathieu Desnoyers
Author Date: 2011-08-17 10:07:35 UTC

Merge branch 'master' into lfqueue-dev

Author: Mathieu Desnoyers
Author Date: 2010-03-22 19:09:44 UTC

rbtree test: show tree

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

Author: Mathieu Desnoyers
Author Date: 2010-03-01 20:15:19 UTC

LFQ: Fix unpaired lock/unlock

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

Author: Mathieu Desnoyers
Author Date: 2009-09-26 22:29:37 UTC

qsbr: only mark reader thread as being waited for in contended case

Signed-off-by: Mathieu Desnoyers <mathieu.desnoyers@polymtl.ca>

Author: Mathieu Desnoyers
Author Date: 2009-09-26 22:29:37 UTC

qsbr: only mark reader thread as being waited for in contended case

Signed-off-by: Mathieu Desnoyers <mathieu.desnoyers@polymtl.ca>

Author: Mathieu Desnoyers
Author Date: 2009-09-26 12:19:26 UTC

Add multiple reader queues to futex model

Signed-off-by: Mathieu Desnoyers <mathieu.desnoyers@polymtl.ca>

Author: Mathieu Desnoyers
Author Date: 2009-09-24 00:55:52 UTC

urcu-defer: fix futex wakeup value

Signed-off-by: Mathieu Desnoyers <mathieu.desnoyers@polymtl.ca>