Document: rculfhash destroy and resize side-effect in 0.7

Document that destroy puts thread online with QSBR.

Document that resize puts thread online with QSBR, and that it should
not be called with RCU read-side lock held.

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

Add "sparc" host cpu to configure.ac

Some sparc Debian setups advertise a "sparc" host cpu (rather than
sparc64).

In all cases, I think it should be safe to add a "sparc" entry to
userspace RCU configure.ac upstream, e.g.

        [sparc], [ARCHTYPE="sparc64"],

in the event someone would launch the build on an environment not
supporting sparc v9, the build would fail because the 32-bit compiler
would not be able to generate sparc v9 instructions (unless
explicitely instructed to do so by the -m32 -Wa,-Av9a flags).

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

Fix: tests/api.h use cpuset.h

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

Fix hurd-i386: move cpuset tests outside of sched_setaffinity conditional

Comment about introduction of cpuset.h within urcu tests:

> Unfortunately it doesn't work, because sched_setaffinity is for now
> just a fail-stub on hurd-i386, and thus configure considers it as
> missing, and thus the CPU_SET test is disabled completely.
>
> I however guess you could just disable defining your own cpu_set_t
> when !HAVE_SCHED_SETAFFINITY, since it is probably used only for using
> sched_setaffinity.

Fix by moving cpu_set_t, CPU_SET and CPU_ZERO tests outside of the
sched_setaffinity conditional.

Reported-by: Samuel Thibault <sthibault@debian.org>
Signed-off-by: Mathieu Desnoyers <mathieu.desnoyers@efficios.com>

Fix tests: finer-grained use of CPU_SET, CPU_ZERO and cpu_set_t

Noticed build failure at
https://buildd.debian.org/status/package.php?p=liburcu :

Tail of log for liburcu on hurd-i386:

test_urcu.c:110:0: warning: "CPU_SET" redefined [enabled by default]
In file included from /usr/include/pthread/pthread.h:50:0,
                 from /usr/include/pthread.h:2,
                 from test_urcu.c:26:
/usr/include/sched.h:80:0: note: this is the location of the previous definition
make[3]: *** [test_urcu.o] Error 1
make[2]: *** [all-recursive] Error 1
make[1]: *** [all] Error 2
dh_auto_build: make -j1 returned exit code 2
make: *** [build-arch] Error 2
dpkg-buildpackage: error: debian/rules build-arch gave error exit status 2
make[3]: Entering directory `/build/buildd-liburcu_0.7.6-1-hurd-i386-wGBAtt/liburcu-0.7.6/tests'
  CC     test_urcu.o
make[3]: Leaving directory `/build/buildd-liburcu_0.7.6-1-hurd-i386-wGBAtt/liburcu-0.7.6/tests'
make[2]: Leaving directory `/build/buildd-liburcu_0.7.6-1-hurd-i386-wGBAtt/liburcu-0.7.6'

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

Test for CPU_SET

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

Fix build on architectures with HAVE_SCHED_GETCPU but without HAVE_SYSCONF

Noticed on: https://buildd.debian.org/status/package.php?p=liburcu

Tail of log for liburcu on kfreebsd-amd64:

  CC     urcu.lo
In file included from urcu.c:450:0:
urcu-call-rcu-impl.h:145:12: error: static declaration of 'sched_getcpu' follows non-static declaration
In file included from /usr/include/sched.h:43:0,
                 from /usr/include/pthread.h:20,
                 from urcu.c:30:
/usr/include/x86_64-kfreebsd-gnu/bits/sched.h:65:12: note: previous declaration of 'sched_getcpu' was here
make[3]: *** [urcu.lo] Error 1
make[3]: Leaving directory `/build/buildd-liburcu_0.7.6-1-kfreebsd-amd64-nnkICd/liburcu-0.7.6'
make[2]: *** [all-recursive] Error 1
make[2]: Leaving directory `/build/buildd-liburcu_0.7.6-1-kfreebsd-amd64-nnkICd/liburcu-0.7.6'
make[1]: *** [all] Error 2
make[1]: Leaving directory `/build/buildd-liburcu_0.7.6-1-kfreebsd-amd64-nnkICd/liburcu-0.7.6'
dh_auto_build: make -j1 returned exit code 2
make: *** [build-arch] Error 2

Tail of log for liburcu on kfreebsd-i386:

  CC     urcu.lo
In file included from urcu.c:450:0:
urcu-call-rcu-impl.h:145:12: error: static declaration of 'sched_getcpu' follows non-static declaration
In file included from /usr/include/sched.h:43:0,
                 from /usr/include/pthread.h:20,
                 from urcu.c:30:
/usr/include/i386-kfreebsd-gnu/bits/sched.h:65:12: note: previous declaration of 'sched_getcpu' was here
make[3]: *** [urcu.lo] Error 1
make[3]: Leaving directory `/build/buildd-liburcu_0.7.6-1-kfreebsd-i386-sWzNKU/liburcu-0.7.6'
make[2]: *** [all-recursive] Error 1
make[2]: Leaving directory `/build/buildd-liburcu_0.7.6-1-kfreebsd-i386-sWzNKU/liburcu-0.7.6'
make[1]: *** [all] Error 2
make[1]: Leaving directory `/build/buildd-liburcu_0.7.6-1-kfreebsd-i386-sWzNKU/liburcu-0.7.6'
dh_auto_build: make -j1 returned exit code 2
make: *** [build-arch] Error 2

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

README: document that Clang 3.0 (based on LLVM 3.0) is supported

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

clang: silence "unused expression result" warning

CMM_STORE_SHARED(x, v) is a macro that really acts like an assignment
expression, e.g.:

  x = v;

but internally also has "mc" barriers (useful for cache-incoherent
architectures).

The issue here is that (x = v) can evaluate to "v", but very often we're
not interested to use the assignment expression result. When we have an
explicit assignment, the compiler won't complain that the result of this
expression is unused, but given that the added barrier requires that we
make this macro evaluate explicitly to a value, clang complains.

Fix this by adding "_v = _v" at the last line of the macro, thus
performing what would appear like an effect-less assignment, but
actually tricks clang into thinking we are evaluating to an assignment
expression, thus suppressing the warning.

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

rculfhash: add assertions on node alignment

I've had a report of someone running into issues with the RCU lock-free
hash table by embedding the struct cds_lfht_node into a packed structure
by mistake, thus not respecting alignment requirements stated in
urcu/rculfhash.h. Assertions on "replace" and "add" operations should
catch this, but I notice that we should add assertions on the
REMOVAL_OWNER_FLAG to cover all possible misalignments.

Acked-by: Paul E. McKenney <paulmck@linux.vnet.ibm.com>
Signed-off-by: Mathieu Desnoyers <mathieu.desnoyers@efficios.com>

uatomic: style fix

- Functions that don't take arguments should be "void" in C, otherwise
  those functions can take a variable number of arguments.

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

Version 0.7.6

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

Discourage use of pthread_atfork() for call_rcu handlers

Discourage use of glibc pthread_atfork() for call_rcu handlers due to
its inappropriate assumptions about single-threadedness while pthread
atfork handlers are executing. This results in hangs within the glibc
memory allocator.

Reviewed-by: Paul E. McKenney <paulmck@linux.vnet.ibm.com>
Signed-off-by: Mathieu Desnoyers <mathieu.desnoyers@efficios.com>

Fix call_rcu fork handling

Fix call_rcu fork handling by putting all call_rcu threads in a
quiescent state before fork (paused state), and unpausing them when the
parent returns from fork.

On the child, everything will run fine as long as we don't issue fork()
from a call_rcu callback.

Side-note: pthread_atfork is not appropriate when using with multithread
and malloc/free. The glibc malloc implementation sadly expects that all
malloc/free are executed from the context of a single thread while
pthread atfork handlers are running, which leads to interesting hang in
glibc.

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

test: fork handling

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

Fix TLS detection: test with linker, add --disable-compiler-tls

NetBSD 5.1 and older, as well as Darwin, succeed to compile code
containing TLS, but cannot link it. Test with linker in addition to
compiler for TLS support.

Also add a --disable-compiler-tls configure option to allow users to
force using the pthread getspecific fall back.

Fixes #288

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

Cleanup: cast pthread_self() return value to unsigned long

pthread_t can map to other things that unsigned long (e.g. pointer).
Cast it to unsigned long for debug printing and for debug delay random
value purposes.

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

Fallback mechanism not working on platform where TLS is unsupported

The CONFIG_RCU_TLS entry in config.h.in is defined by default to "TLS".
This has the unfortunate consequence of defining CONFIG_RCU_TLS on
platform where TLS is unsupported and effectively disabling the pthread
based fallback mechanism. This macro should be #undef by default and the
AX_TLS m4 macro will properly detect if TLS is supported.

Signed-off-by: Christian Babeux <christian.babeux@efficios.com>
Signed-off-by: Mathieu Desnoyers <mathieu.desnoyers@efficios.com>

Version 0.7.5

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

Fix: call_rcu list corruption on teardown

* Mathieu Desnoyers <mathieu.desnoyers@efficios.com> wrote:
> * Lai Jiangshan (laijs@cn.fujitsu.com) wrote:
> > test code:
> > ./tests/test_urcu_lfs 100 10 10
> >
> > bug produce rate > 60%
> >
> > {{{
> > I didn't see any bug when "./tests/test_urcu_lfs 10 10 10" Or
> +"./tests/test_urcu_lfs 100 100 10"
> > But I just test it about 5 times
> > }}}
> >
> > 4cores*1threads: Intel(R) Core(TM) i5 CPU         760
> > RCU_MB (no time to test for other rcu type)
> > test commit: 768fba83676f49eb73fd1d8ad452016a84c5ec2a
> >
> > I didn't see any bug when "./tests/test_urcu_mb 10 100 10"
> >
> > Sorry, I tried, but I failed to find out the root cause currently.
>
> I think I managed to narrow down the issue:
>
> 1) the master branch does not reproduce it, but commit
>    768fba83676f49eb73fd1d8ad452016a84c5ec2a repdroduces it about 50% of the
>    time.
>
> 2) the main change between 768fba83676f49eb73fd1d8ad452016a84c5ec2a and
>    current master (f94061a3df4c9eab9ac869a19e4228de54771fcb) is call_rcu
>    moving to wfcqueue.
>
> 3) the bug always arise, for me, at the end of the 10 seconds.
>    However, it might be simply due to the fact that most of the memory
>    get freed at the end of program execution.
>
> 4) I've been able to get a backtrace, and it looks like we have some
>    call_rcu callback-invokation threads still working while
>    call_rcu_data_free() is invoked. In the backtrace, call_rcu_data_free()
>    is nicely waiting for the next thread to stop, and during that time,
>    two callback-invokation threads are invoking callbacks (and one of
>    them triggers the segfault).
>
> So I expect that commit
>
> commit 5161f31e09ce33dd79afad8d08a2372fbf1c4fbe
> Author: Mathieu Desnoyers <mathieu.desnoyers@efficios.com>
> Date:   Tue Sep 25 10:50:49 2012 -0500
>
>     call_rcu: use wfcqueue, eliminate false-sharing
>
>     Eliminate false-sharing between call_rcu (enqueuer) and worker threads
>     on the queue head and tail.
>
>     Acked-by: Paul E. McKenney <paulmck@linux.vnet.ibm.com>
>     Signed-off-by: Mathieu Desnoyers <mathieu.desnoyers@efficios.com>
>
> Could have managed to fix the issue, or change the timing enough that it
> does not reproduces. I'll continue investigating.

The bug was in call rcu. It is not required for master, because we fixed
it while moving to wfcqueue.  We were erroneously writing to the head
field of the default call_rcu_data rather than tail.

The conditions to reproduce this bug:

1) setup per-cpu callback-invokation threads,
2) use call_rcu
3) call call_rcu_data_free() while there are still some pending
   callbacks that have not yet been executed by the callback-invokation
   threads,
4) we then get corruption due to the "default" callback invokation
   that walks through a corrupted queue.

This bug is fixed by commit 5161f31e09ce33dd79afad8d08a2372fbf1c4fbe in
the 0.7.x series. Commit 0b8ab7df078a6d8e1439b1db5849638892e1cc83 in the
0.7.x series explains the real motivation for moving call_rcu from
wfqueue to wfcqueue.

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

Ensure that read-side functions meet 10-line LGPL criterion

This commit ensures that all read-side functions meet the 10-line LGPL
criterion that permits them to be expanded directly into non-LGPL code,
without function-call instructions.  It also documents this as the
intent.

[ paulmck: Spelling fixes called out by Josh Triplett and name
change called out by Mathieu Desnoyers (_rcu_read_lock_help() ->
_rcu_read_lock_update(). ]

[ Mathieu Desnoyers: _rcu_read_unlock_help renamed to
  _rcu_read_unlock_update_and_wakeup, and spelling fix for
  preced -> precede. ]

Signed-off-by: Paul E. McKenney <paulmck@linux.vnet.ibm.com>
Signed-off-by: Mathieu Desnoyers <mathieu.desnoyers@efficios.com>

tls-compat.h: document sigaltstack(2) limitation

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

urcu: add notice to URCU_TLS() for it is not strictly async-signal-safe

Signed-off-by: Lai Jiangshan <laijs@cn.fujitsu.com>
Signed-off-by: Mathieu Desnoyers <mathieu.desnoyers@efficios.com>

Document sigaltstack(2) limitation

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

Documentation: update LICENSE file

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

Update version to 0.7.4

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

rculfhash API documentation: document destroy RCU read-lock constraint

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

Fix: rculfhash should be offline while waiting for resize to complete

Causes hang on destroy with urcu QSBR if destroy is called within a rcu
registered thread.

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

Add missing entry to gitignore

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

urcu: move busy-wait code and name it ___cds_wfq_node_sync_next()

This code which waits for a node's next pointer until it appears, will
be used many times, move it to a help function and name it
___cds_wfq_node_sync_next().

Signed-off-by: Lai Jiangshan <laijs@cn.fujitsu.com>
Signed-off-by: Mathieu Desnoyers <mathieu.desnoyers@efficios.com>

urcu: fix compat_futex_noasync()

This patch fix two critical problems in the compatibility fallback of
compact_futex_noasync():

1) compat_futex_cond is not bound to any @uaddr, it services all @uaddr,
   if you wakeup only one thread(pthread_cond_signal), the @uaddr of
   this waking thread and the @uaddr of the woken-up thread may be different.
   The woken-up thread will very probably go to sleep again
   because his own condition is not true.

   *And* this waking thread(FUTEX_WAKE) wake up NOTHING.

2) If the caller want to wake up all waiting threads, he will use INT_MAX
   for @val, and:
                for (i = 0; i < INT_MAX; i++)
                        pthread_cond_signal(&compat_futex_cond);
   becomes almost infinity loop.

Signed-off-by: Lai Jiangshan <laijs@cn.fujitsu.com>
Signed-off-by: Mathieu Desnoyers <mathieu.desnoyers@efficios.com>

urcu: add hint to DEFINE_URCU_TLS() for compound types

Just a hint.

Signed-off-by: Lai Jiangshan <laijs@cn.fujitsu.com>
Signed-off-by: Mathieu Desnoyers <mathieu.desnoyers@efficios.com>

Fix: CAA_BUILD_BUG_ON should refer to CAA_BUILD_BUG_ON_ZERO

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

Add MIPS support

[ Edit by Mathieu Desnoyers: add explanations about supported
MIPS architectures, extracted from conversation with Ralf Baechle:

* Supported architectures

Ralf Baechle (edited by Mathieu Desnoyers):

This code works on all MIPS architecture variants.  The memory barrier
instruction, SYNC, was introduced for MIPS II.  The original MIPS I
instruction set doesn't have SYNC nor SMP support in the processor
architecture itself so SMP required horrible kludges in the system
hardware.  I think it's safe to say that Linux/MIPS will never support
any of these MIPS I SMP systems.  In the unlikely case this happens
anyway, we have a (Linux) kernel emulation of the SYNC instruction.
Voila - full binary compatibility across all MIPS processors and the
oldest hardware pays the performance penalty.

* Choice of barrier for cmm_mb()/cmm_rmb()/cmm_wmb()

Ralf Baechle:
"RMI (aka Netlogic and now Broadcom) XLR processor cores can be
configured to permit LD-LD, LD-ST, ST-LD and ST-ST reordering; default
is only ST-ST reordering.  To allow Linux to eventually enable full
reordering cmm_mb(), cmm_rmb() and cmm_wmb() all should perform SYNC
and a compiler barrier."

* No-op choice for cmm_read_barrier_depends():

Ralf Baechle:
"Technically there is nothing in the MIPS architecture spec that would
keep a MIPS implementation from reordering as freely as an Alpha or
even more liberally.  In practice most do strong ordering.  However
there is no MIPS implementation that makes full use of all the rope
provided.  So in theory a paranoid implementation of
cmm_read_barrier_depends() for MIPS should perform a SYNC.  In reality
it's not necessary and no sane MIPS core designer would implement
something that would design a core that need a non-empty
cmm_read_barrier_depends().  The reason why my patch had an empty one
is that I was using the Alpha code as a template."

Mathieu Desnoyers:
Moreover, the Linux kernel chooses a no-op for MIPS
read_barrier_depends() implementation, so any MIPS architecture that
would be as weak as Alpha would break the Linux kernel before breaking
the userspace RCU library.

* No need to put ".set noreorder" in cmm_mb() inline assembly:

Ralf Baechle:
"Certain instructions such as SYNC won't get reordered." ]

Signed-off-by: Ralf Baechle <ralf@linux-mips.org>
CC: Paul McKenney <paulmck@linux.vnet.ibm.com>
Signed-off-by: Mathieu Desnoyers <mathieu.desnoyers@efficios.com>

Compatibility: remove bash-ismsm from test scripts

+= is not supported by all shells.

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

Fix inappropriate lib behavior: don't call exit()

Use abort() (implemented through the new urcu_die()) instead of exit(-1)
for unrecoverable errors.

Fixes #152

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

Fix: re-enable compatibility with autoconf < 2.64

> I tried to build the latest urcu (git master e51500) on a Centos 6.2 box, and got:
>
> jscott@dxi0-62:~/src/userspace-rcu$ make -j4
> CDPATH="${ZSH_VERSION+.}:" && cd . && /bin/sh /users/jscott/src/userspace-rcu/config/missing --run aclocal-1.11 -I
> +config
> CDPATH="${ZSH_VERSION+.}:" && cd . && /bin/sh /users/jscott/src/userspace-rcu/config/missing --run autoconf
>  cd . && /bin/sh /users/jscott/src/userspace-rcu/config/missing --run automake-1.11 --foreign
> configure:4010: error: possibly undefined macro: m4_ifnblank
>       If this token and others are legitimate, please use m4_pattern_allow.
>       See the Autoconf documentation.
> make: *** [configure] Error 1
> make: *** Waiting for unfinished jobs....
>
> Some digging showed that the macro m4_ifnblank requires autoconf 2.64. Centos 6.2 has autoconf 2.63. :(
>
> I just worked around it by reverting commit a767fd locally, then I can build fine.

Reported-by: John Steele Scott <toojays@toojays.net>
Signed-off-by: Mathieu Desnoyers <mathieu.desnoyers@efficios.com>

Fix c99 compatibility: use __asm__ and __volatile__ in public headers

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

Fix c99 compatibility: use __typeof__ instead of typeof in public headers

Reported-by: John Steele Scott <toojays@toojays.net>
Signed-off-by: Mathieu Desnoyers <mathieu.desnoyers@efficios.com>

warning fix: tests urcutorture for NetBSD 5

>   CC     rcutorture_urcu-urcutorture.o
> In file included from urcutorture.c:9:
> api.h: In function '__smp_thread_id':
> api.h:160: warning: cast from pointer to integer of different size
> api.h:160: warning: cast from pointer to integer of different size
> api.h: In function 'wait_thread':
> api.h:210: warning: cast from pointer to integer of different size
> api.h:210: warning: cast from pointer to integer of different size

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

Update version to 0.7.3

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

Fix tests: make dist lib dependency

Some test programs were depending in SOURCES on the CDS library. Change
this for a LDADD, which makes "make dist" work after a make clean.

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

Update README for OS supported, tests dependency

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

Add CodingStyle to tarball

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

Add coding style document

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

Test fix: test_perthreadlock uninitialized mutex

- Initialize the per thread mutexes. (fix)
- Remove unused count_reader/count_writer variables. (cleanup)

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

tests: support FreeBSD short "time" args

time(1) in FreeBSD does not have long argument name: change --append to
-a and --output to -o

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

freebsd 8.2 fix: define MAP_ANONYMOUS for compatibility

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

Update version to 0.7.2

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

Fix library compatibility

Commit 4d0d66bb795d1ed938e11a97a4e5f71326e20c71, implementing
tls-compat.h for pthread TLS compatibility, adds a prefix in front of
each TLS symbol (__tls_*). However, some of these symbols are exported
by the URCU library (e.g. rcu_reader_mb, defined in urcu.c as
"rcu_reader", which is overloaded by the urcu/map/urcu.h) to
applications. Therefore, this breaks binary compatibility with 0.6.x
versions of the library. This is not intended, and therefore is a bug,
so we remove this __tls_* prefix from the variables declared, defined
and referenced to through the tls-compat.h API for compilers supporting
"__thread".

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

Update version to 0.7.1

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

fix: uatomic_set return value compile fix for non-x86 arch.

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

Update version to 0.7.0

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

Cleanup: header comments coding style

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

Document uatomic operations

Document each atomic operation provided by urcu/uatomic.h, along with
their memory barrier guarantees.

Acked-by: Paul E. McKenney <paulmck@linux.vnet.ibm.com>
Signed-off-by: Mathieu Desnoyers <mathieu.desnoyers@efficios.com>

Update return value of "set" operations

To follow the way the Linux kernel implements atomic_set(), we change
some API functions so they don't return any value anymore.

This is now the case for:

uatomic_set()
rcu_set_pointer()
rcu_assign_pointer()

This API change is very minor. In all instances of the Linux kernel
using rcu_assign_pointer(), none currently care about its return value.

However, we keep ABI compatibility: rcu_set_pointer_sym() still returns
the "v" value, even though it is not used by its wrapper macro anymore.

Reviewed-by: Paul E. McKenney <paulmck@linux.vnet.ibm.com>
Signed-off-by: Mathieu Desnoyers <mathieu.desnoyers@efficios.com>

Fix mremap wrapper for NetBSD 5

NetBSD 5 implements a mremap with a different semantic. Rename our
wrapper symbol name so it does not clash with the NetBSD 5 symbol.
Eventually, we could envision doing a special-case that uses the NetBSD
5 version instead of the fallback, but let's first get it working before
going into optimization land.

Suggested-by: Marek Vavruša <marek.vavrusa@nic.cz>
Signed-off-by: Mathieu Desnoyers <mathieu.desnoyers@efficios.com>

Use urcu/tls-compat.h

Provides compatibility for OpenBSD, NetBSD and Darwin.

Suggested-by: Marek Vavruša <marek.vavrusa@nic.cz>
Signed-off-by: Mathieu Desnoyers <mathieu.desnoyers@efficios.com>

Implement urcu/tls-compat.h

Suggested-by: Marek Vavruša <marek.vavrusa@nic.cz>
Signed-off-by: Mathieu Desnoyers <mathieu.desnoyers@efficios.com>

Add TLS detection m4 macro

Will allow urcu to support OSes that require to use pthread TLS (and do
not provide __thread TLS support).

Suggested-by: Marek Vavruša <marek.vavrusa@nic.cz>
Signed-off-by: Mathieu Desnoyers <mathieu.desnoyers@efficios.com>

document concurrent data structures

Document the concurrent data structures provided by the userspace RCU
library.

Reviewed-by: Paul E. McKenney <paulmck@linux.vnet.ibm.com>
Signed-off-by: Mathieu Desnoyers <mathieu.desnoyers@efficios.com>

documentation: refer to rcu-api.txt

API.txt moved to userspace-rcu documentation rcu-api.txt.

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

Move API.txt to doc/rcu-api.txt, install in system doc/

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

rculfhash: document implied memory barriers

We choose to provide full memory barriers before and after successful
hash table update operations. Eventually, new API with weaker semantic
can be added, but let's make the basic API as fool-proof as possible.

Signed-off-by: Mathieu Desnoyers <mathieu.desnoyers@efficios.com>
Reviewed-by: "Paul E. McKenney" <paulmck@linux.vnet.ibm.com>

rculfhash: Ensure future-proof memory barrier semantic consistency

Use cmm_smp_mb__before_uatomic_or() prior to the uatomic_or() in
_rcu_lfht_del() to ensure correct memory barrier semantic when we relax
(in the future) the barrier implementation of some architectures.

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

API cleanup: use "uatomic_*" in cmm_smp_mb__ API

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

uatomic: add memory barrier API for and/or/add/sub/inc/sub

Implement:
cmm_smp_mb__before_and, cmm_smp_mb__after_and
cmm_smp_mb__before_or, cmm_smp_mb__after_or
cmm_smp_mb__before_add, cmm_smp_mb__after_add
cmm_smp_mb__before_sub, cmm_smp_mb__after_sub
cmm_smp_mb__before_inc, cmm_smp_mb__after_inc
cmm_smp_mb__before_dec, cmm_smp_mb__after_dec

For generic and x86.

These currently translate into simple compiler barriers on all
architectures, but the and/or/add/sub/inc/dec uatomics do not provide
memory ordering guarantees (only uatomic_add_return, uatomic_sub_return,
uatomic_xchg, and uatomic_cmpxchg provides full memory barrier
guarantees before and after the atomic operations).

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

rculfhash: add runhash.sh test script

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

rculfhash tests: add missing check

We need to check if test_ht is NULL.

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

rculfhash: fix: race between replace and del operations

Bug introduced by commit db00ccc36e7fb04ce8044fb1be7964acd1de6ae0

Here is the race:

Initially in hash table:  A

T0                                         T1
replace A by B
                                           del A
  read A->next
  -> check REMOVED flag, not set yet.
                                           read A->next
                                           -> check REMOVED flag, not set yet.
  cmpxchg A->next to set REMOVED flag
  -> cmpxchg succeeds
                                           uatomic_or to set REMOVED flag
                                           uatomic_xchg to atomically set the REMOVAL_OWNER flag
                                           -> first to set the flag.
  Replace returns node -> free(A)          Del success -> free(A)

With this race, we have a double-free.

The problem with the replace code is that it does not set the
"REMOVAL_OWNER" flag.

Test case to reproduce the bug:

test_urcu_hash 0 2 20 -A -s -M 1 -N 1 -O 1

(2 threads, doing replace/del, with a hash table that has only a single
key for all values). After just a couple of seconds, either the program
hangs, or, more often, it does:

*** glibc detected ***
/media/truecrypt1/compudj/doc/userspace-rcu/tests/.libs/test_urcu_hash:
malloc(): memory corruption (fast): 0x00007ffff3a29e25 ***

Program received signal SIGSEGV, Segmentation fault.

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

rculfhash: replace unneeded rcu_dereference by CMM_LOAD_SHARED

The difference between the two is that CMM_LOAD_SHARED() does not imply
a read barrier between the read and following uses of the data pointed
to by the pointer read.

All sites that only use the pointer load for its bits (never
dereference) don't need the read barrier implied by rcu_dereference.

Reviewed-by: "Paul E. McKenney" <paulmck@linux.vnet.ibm.com>
Signed-off-by: Mathieu Desnoyers <mathieu.desnoyers@efficios.com>

rculfhash: use do {} while (0) for dbg_printf()

found by clang(make CC=clang).

avoid empty statement.
-------------------------
if (condition)
        dbg_printf()  /* forget ";", but compiler say nothing if dbg_printf() is empty */
statement;
-------------------------

also add printf format check.
(we can use gcc extention "__printf(1, 2)" to declare a dummy inline function
to do the check, but I use "printf()" directly here)

Signed-off-by: Lai Jiangshan <laijs@cn.fujitsu.com>
Signed-off-by: Mathieu Desnoyers <mathieu.desnoyers@efficios.com>

rculfhash: cleanup typo

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

rculfhash: update API comments

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

rculfhash: update comments in implementation

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

rculfhash tests: add long hash chains tests

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

rculfhash tests: add uniqueness test

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

rculfhash test: print test name

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

rculfhash: stress requirement in documentation

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

rculfhash: fix typo

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

rculfhash tests: use array of callbacks to modularize

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

rculfhash tests: modularize tests

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

rculfhash: document ordering guarantees

What we actually provide are ordering guarantees.

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

rculfhash: document linearizability guarantees

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

rculfhash: update removal comment

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

Add missing files to .gitignore

Fixes #93

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

Fix out-of-tree build

Wildcards in automake seems to require that we prepent $(top_srcdir) to
get out-of-tree build to work.

Other non-wildcards work fine without the $(top_srcdir) prefix, so
leaving as-is.

Fixes #94

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

rculfhash: check malloc NULL pointer

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

Fix uatomic sign cast

Passing an unsigned int to uatomic_sub does not honor sign extend to
long, as we should be allowed by assume.

Fix this by introducing caa_cast_long_keep_sign(), which casts either to
long or unsigned long depending on the signedness of the argument
received. It is used in uatomic_sub before applying the "-" operator,
since this operator needs to operate on the "long" type size (since sign
extension might not be performed if the argument received is unsigned).

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

Remove unused jhash.h file

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

Fix: use known license text, fix incorrect FSF address

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

Fix: add missing sched.h include in rculfhash.c

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

Allow tests to run on architectures without per-cpu call_rcu support

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

Hash table test: FreeBSD compatibility fix

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

tests: define _GNU_SOURCE instead of __USE_GNU

Fixes the following warning:

In file included from urcutorture.c:9:0:
api.h:67:0: warning: "__USE_GNU" redefined [enabled by default]
/usr/include/features.h:304:0: note: this is the location of the previous definition

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

Merge branch 'urcu/ht-shrink'

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>

Define _GNU_SOURCE to access CPU_ZERO() macro in uClibc

Signed-off-by: Thomas Petazzoni <thomas.petazzoni@free-electrons.com>
Signed-off-by: Mathieu Desnoyers <mathieu.desnoyers@efficios.com>

Install ChangeLog and README into system's doc

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

Fix AC_LANG_SOURCE usage: only takes one parameter

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