lfstack: relax constraints on node re-use
authorMathieu Desnoyers <mathieu.desnoyers@efficios.com>
Tue, 22 Sep 2015 16:15:02 +0000 (12:15 -0400)
committerMathieu Desnoyers <mathieu.desnoyers@efficios.com>
Sat, 26 Sep 2015 15:13:13 +0000 (11:13 -0400)
commitf9b5c2b65a8a2605fc83e84e2c20e6f09033670d
treeb9264f5cd9ef259b74128cb2f575a2084fbc9bcc
parente15df1cc24bf510057fd0fc950eadf1c09575923
lfstack: relax constraints on node re-use

The documentation of the RCU-based synchronization technique in lfstack
is too strict. It currently states that the cds_lfs_node structure
cannot be overwritten before a grace period has passed. However, lfstack
pop only use the next pointer as the replacement value when doing the
cmpxchg on the head. After the node has been pop'd from the stack,
concurrent cmpxchg trying to pop that same node will necessarily fail as
long as there is a grace period before pop/pop_all and re-adding the
node into the stack.

It is therefore sufficient to wait for a grace period between:
1) pop/pop_all and
2) freeing the node (to ensure existence for concurrent pop trying to
   read node->next) or re-adding the node into the stack.

This node re-use constraint relaxation is only possible because we don't
care about node->next content read by concurrent pop: it will be simply
discarded by the cmpxchg on head. Be careful not to apply this relaxed
constraint to other data structures which care about the content of the
node's next pointer (e.g. wfstack).

This relaxed constraint allows implementing efficient free-lists (memory
allocation) with a lock-free allocation/free based on lfstack: it allows
re-using the memory backing the free-list node immediately after
allocation. The only requirement with respect to this use-case is to
wait for a grace period before putting the node back into the free-list.

Also update the test_urcu_lfs to poison the next pointer immediately
after pop/pop_all to make sure we test this relaxed constraint.

Signed-off-by: Mathieu Desnoyers <mathieu.desnoyers@efficios.com>
CC: Paul E. McKenney <paulmck@linux.vnet.ibm.com>
CC: Lai Jiangshan <jiangshanlai@gmail.com>
CC: lttng-dev@lists.lttng.org
CC: rp@svcs.cs.pdx.edu
tests/benchmark/test_urcu_lfs.c
urcu/lfstack.h
urcu/static/lfstack.h
This page took 0.031048 seconds and 4 git commands to generate.