urcu-defer: ensure callbacks will never be enqueued forever
Even if there are no further callbacks enqueued, ensure that after a 100ms
delay, the callback queue will be dealt with.
Required proper ordering of queue vs futex.
e.g.
The idea is to perform the "check for empty queue" between the
&defer_thread_futex decrement and the test in wait_defer. It skips the
futex call and proceed if the list is non-empty.
As I am drilling into the problem, it looks very much like an attempt to
implement efficient wait queues in userspace based on sys_futex().
/*
* Wake-up any waiting defer thread. Called from many concurrent
* threads.
*/
static void wake_up_defer(void)
{
if (unlikely(atomic_read(&defer_thread_futex) == -1)) {
atomic_set(&defer_thread_futex, 0);
futex(&defer_thread_futex, FUTEX_WAKE, 0,
NULL, NULL, 0);
}
}
/*
* Defer thread waiting. Single thread.
*/
static void wait_defer(void)
{
atomic_dec(&defer_thread_futex);
smp_mb(); /* Write futex before read queue */
if (rcu_defer_num_callbacks()) {
smp_mb(); /* Read queue before write futex */
/* Callbacks are queued, don't wait. */
atomic_set(&defer_thread_futex, 0);
} else {
smp_rmb(); /* Read queue before read futex */
if (atomic_read(&defer_thread_futex) == -1)
futex(&defer_thread_futex, FUTEX_WAIT, -1,
NULL, NULL, 0);
}
}
- defer thread:
* for (;;)
* wait_defer()
* sleep 100ms (wait for more callbacks to be enqueued)
* dequeue callbacks, execute them
The goal here is that if call_rcu() enqueues a callback (even if it
races with defer thread going to sleep), there should not be a
potentially infinite delay before it gets executed. Therefore, being
blocked in sys_futex while there is a callback to execute, without any
hope to be woken up unless another callback is queued, would not meet
that design requirement. I think that checking the number of queued
callbacks within wait_defer() as I propose here should address this
situation.
All synchronization between queue producer/consumer is performed by the write to
"head". Before this write, none of the queued data is visible from the consumer
point of view.
Therefore, just a single wmb() is required before writing to head to ensure
correct synchronization. This matches with the rmb() after reading head on the
consumer side.
Rename "reader" to "reclaimer", because urcu-reclaim keeps track of "reclaimer"
threads (rcu writers) and has its own reclaiming thread periodically performing
the batch reclamation.
Follow-up on 1a80f3: since now `0' for a gp counter means "offline", just
be sure that the global GP counter is never zero. To achieve that, let its
first value ever be one, and increment it 2 by 2 like previously done.
Note that it internaly uses the fact that signed integers wraps (which the
previous code already assumed anyways) but this is undefined behaviour in
C. Using unsigned longs would probably be more portable.
This way, setting the cpu online, marking a quiescent state is just a
matter of copying the global gp counter instead of incrementing it by one.
This saves one CPU instruction, and supposedly even register use for
architectures providing memory to memory copy operands.
Signed-off-by: Pierre Habouzit <madcoder@debian.org> Signed-off-by: Mathieu Desnoyers <mathieu.desnoyers@polymtl.ca>
Pierre Habouzit [Thu, 17 Sep 2009 12:30:19 +0000 (08:30 -0400)]
qsbr: save two full smp_mb() when the writer is also a reader.
Now that you've put the barriers before taking lock, and after releasing
it, one can expand the _rcu_thread_{on,off}line call, and optimize two
barrier calls away. (this is patch 1/2).
Signed-off-by: Pierre Habouzit <madcoder@debian.org> Signed-off-by: Mathieu Desnoyers <mathieu.desnoyers@polymtl.ca>
> That's an interesting paper for sure. I had one micro-optimization in
> mind when I read the paper for QSBR, you can decide that making a CPU
> offline can be done by writing 0 to the per thread counter, instead of
> reading the global counter. It saves a load from a shared variable,
> which probably helps in its tiny way.
>
In wait_for_quiescent_state, the test for Q.S. is :
while (rcu_gp_ongoing(index->rcu_reader_qs_gp) &&
(*index->rcu_reader_qs_gp - urcu_gp_ctr < 0))
cpu_relax();
where :
static inline int rcu_gp_ongoing(long *value)
{
if (value == NULL)
return 0;
return LOAD_SHARED(*value) & 1;
}
Your proposal would work for the rcu_gp_ongoing test, as it only checks
for the parity. Given this test is enough to guarantee that we skip the
reader thread, then yes, it seems to work just fine.
Proposed-by: Pierre Habouzit <madcoder@debian.org> Signed-off-by: Mathieu Desnoyers <mathieu.desnoyers@polymtl.ca>
qsbr urcu: make it safe to call rcu_sychronize from a registered thread
Actually, the proper way to deal with threads registered as readers but also
calling synchronize_rcu() is to mark them as offline while the synchronize is in
progress.
Else, since calling rcu_sychronize will increment urcu_gp_ctr, we will be
stupidly waiting for ourselves and deadlock.
Original-patch-from: Pierre Habouzit <madcoder@debian.org> Signed-off-by: Mathieu Desnoyers <mathieu.desnoyers@polymtl.ca>
urcu.c: declare noop urcu_init() function non-static
The RCU library is sometimes used in constructor context. In these cases,
because it is impossible to predict whether the liburcu constructor has already
been called, an explicit call to the urcu_init function must be made.
Declaring the noop version of the urcu_init() function as static breaks code
that calls urcu_init() explicitly when CONFIG_AVOID_SIGNALS is true. To prevent
this, this patch makes the declaration non-static.
With this flag, the kernel restarts automatically some system calls
that were interrupted by the signal. Without this flag, these system
calls would fail with errno = EINTR.
Even with this flag, the kernel cannot restart some system calls, and
developers should verify whether these system calls failed with EINTR
and restart them manually in that case. For the list of system calls
that cannot be restarted automatically, see signal(7).
Because of this, we cannot completely eliminate the side-effects of
liburcu on the application, but I think we should try our best and
set SA_RESTART.
Paul E. McKenney [Tue, 16 Jun 2009 18:26:36 +0000 (11:26 -0700)]
URCU's api_*.h
On Tue, Jun 16, 2009 at 07:09:11PM +0200, Jan Blunck wrote:
> I already did most of that for libkcompat. That was actually why I was
> asking if I should port that over.
Nevertheless, I offer the following patch to userspace-rcu to provide
a gcc-library version of the api_*.h files and to clean up the build a
bit.
Signed-off-by: Paul E. McKenney <paulmck@linux.vnet.ibm.com>
Jan Blunck [Tue, 16 Jun 2009 09:20:55 +0000 (11:20 +0200)]
Add S390 architecture specific headers
This implements atomic exchange and some other trivial operations like
barriers for the S390 architecture. All of this is based on the
"z/Architecture Principles of Operation" as released by IBM.
Note that api_s390.h is missing so urcutortures applications don't build.
projects / urcu.git / log
