LFQ: Fix unpaired lock/unlock

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

Remove urcu defer lfq from makefile (non existent)

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

lock-free queue with RCU-based garbage collection

A lock-free queue example using RCU to avoid the need for double-word
compare-and-swap and, at the same time, to implement efficient garbage
collection.  I tested it lightly, and I don't think it's fully ready
for inclusion.  It does need the previous two patches to avoid deadlocks,
so I did test it somewhat. :-)

See individual files for detailed comments on how it works.

Cc: Paul E. McKenney <paulmck@linux.vnet.ibm.com>

centralize definition of BITS_PER_LONG

Use __SIZEOF_LONG__, defined by GCC 4.3 or later, or _LP64, defined
by GCC 3.4 or later.

Signed-off-by: Paolo Bonzini <pbonzini@redhat.com>
Signed-off-by: Mathieu Desnoyers <mathieu.desnoyers@efficios.com>

avoid multiple evaluation of STORE_SHARED argument

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

support compiling on unknown architectures

The new defaults mean that, for example, ia64 support comes for free.

[edit by Mathieu Desnoyers]

defaults -> generic

Signed-off-by: Paolo Bonzini <pbonzini@redhat.com>
Signed-off-by: Mathieu Desnoyers <mathieu.desnoyers@efficios.com>

add Alpha support

And you already know what needs to be special-cased for Alpha...

[edit by Mathieu Desnoyers]

defaults -> generic

Signed-off-by: Paolo Bonzini <pbonzini@redhat.com>
Signed-off-by: Mathieu Desnoyers <mathieu.desnoyers@efficios.com>

move whether atomic byte/short exists to uatomic_arch_*.h

And add more generic implementations to uatomic_defaults.h.

Signed-off-by: Paolo Bonzini <pbonzini@redhat.com>
Signed-off-by: Mathieu Desnoyers <mathieu.desnoyers@efficios.com>

use uatomic_generic.h for common fallback implementations

And now, really remove the code for S390/SPARC, using the fallback
implementation of uatomic_generic.h

Signed-off-by: Paolo Bonzini <pbonzini@redhat.com>
Signed-off-by: Mathieu Desnoyers <mathieu.desnoyers@efficios.com>

add uatomic_generic.h, use it for common definitions

uatomic_generic.h can be included by uatomic_arch_*.h to provide useful
default definitions.  uatomic_arch_*.h can define whatever builtins
it wants to override, then uatomic_generic.h will provide what is not
already defined, as follows:

- uatomic_cmpxchg will use __sync_val_compare_and_swap builtins;

- uatomic_add_return will use __sync_fetch_and_add if uatomic_arch_*.h
did not provide a definition of uatomic_cmpxchg.  If it did, we assume
__sync builtins are buggy or otherwise undesirable on this platform,
so uatomic_generic.h will implement uatomic_add_return in terms of
uatomic_cmpxchg too.

- uatomic_xchg is like uatomic_add_return.  However, since GCC does
not provide an adequate builtin, it needs to use a compare-and-swap
loop using __sync_bool_compare_and_swap if uatomic_cmpxchg is not
provided.

- uatomic_sub_return/uatomic_add/uatomic_sub will be implemented
in terms of uatomic_add_return;

- uatomic_inc/uatomic_dec will be implemented in terms of uatomic_add.

After this patch, uatomic_generic.h is already used for the latter two
categories.  The next patch will use uatomic_generic.h whenever there is
no assembly code involved, or otherwise it makes no difference to use
uatomic_generic.h.  We keep custom per-arch macros to provide support for
compilers back to early GCC 3.x versions; however future ports may
not have this limitation.

The hunk in tests/test_uatomic.c is only needed for bisectability
and will be removed later.

[edit by Mathieu Desnoyers]

Fixed Makefile.am conflict.

Signed-off-by: Paolo Bonzini <pbonzini@redhat.com>
Signed-off-by: Mathieu Desnoyers <mathieu.desnoyers@efficios.com>

remove compat_uatomic_cmpxchg #define from non-x86

This is unused everywhere except on x86.

Signed-off-by: Paolo Bonzini <pbonzini@redhat.com>
Signed-off-by: Mathieu Desnoyers <mathieu.desnoyers@efficios.com>

define sync_core for x86 PIC

Pushing/popping the reserved ebx register is surely less expensive
than a memory barrier.

Note that since ebx is a callee-save register, this is even safe for
signals (i.e. it would be safe even if we needed the value that cpuid
puts in %%ebx).

Signed-off-by: Paolo Bonzini <pbonzini@redhat.com>
Signed-off-by: Mathieu Desnoyers <mathieu.desnoyers@efficios.com>

add urcu/arch_generic.h

Most of the memory barrier definitions are shared between all
architectures, especially smp_* and mc/rmc/wmc.  Put them in
a common file.

[edit by Mathieu Desnoyers]

+ * arch_defaults.h: common definitions for multiple architectures.
 becomes
+ * arch_generic.h: common definitions for multiple architectures.

Signed-off-by: Paolo Bonzini <pbonzini@redhat.com>
Signed-off-by: Mathieu Desnoyers <mathieu.desnoyers@efficios.com>

use autoconf symbolic linking

Instead of copying.  This is less error-prone while developing and
lets Automake handle more stuff.

Signed-off-by: Paolo Bonzini <pbonzini@redhat.com>
Signed-off-by: Mathieu Desnoyers <mathieu.desnoyers@efficios.com>

use kernel style makefile output

A breath of fresh air.  Requires Automake 1.11, but the
patch degrades gracefully.

Signed-off-by: Paolo Bonzini <pbonzini@redhat.com>
Signed-off-by: Mathieu Desnoyers <mathieu.desnoyers@efficios.com>

update README for urcu-signal

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

list: new -> _new for c++ compatibility

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

rcuhlist: add head name fix

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

RCU list: add rcuhlist.h, add list_replace_rcu

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

tests: update writer cs len script for 64-core ppc

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

tests: update summary

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

urcu tests: add writer duration parameter

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

Update to version 0.4.1

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

urcu-static.h: use SYS_membarrier rather than __NR_membarrier

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

s390: fix arch_s390.h include of urcu/compiler.h

gcc -DHAVE_CONFIG_H -I. -I.. -I../urcu    -DTORTURE_URCU -I.. -I.. -g -O2 -c -o rcutorture_urcu-urcutorture.o `test -f 'urcutorture.c' || echo './'`urcutorture.c
/bin/sh ../libtool --tag=CC   --mode=link gcc -DTORTURE_URCU -I.. -I.. -g -O2 -lpthread  -o rcutorture_urcu rcutorture_urcu-urcutorture.o ../urcu.c ../urcu-pointer.c
gcc -DTORTURE_URCU -I.. -I.. -g -O2 -o rcutorture_urcu rcutorture_urcu-urcutorture.o ../urcu.c ../urcu-pointer.c  -lpthread
In file included from ../urcu-static.h:38,
                 from ../urcu.c:36:
../urcu/arch.h:31:22: error: compiler.h: No such file or directory
In file included from ../urcu/system.h:22,
                 from ../urcu/uatomic_arch.h:33,
                 from ../urcu-pointer.c:27:
../urcu/arch.h:31:22: error: compiler.h: No such file or directory
make[3]: *** [rcutorture_urcu] Error 1
make[3]: Leaving directory `/build/buildd-liburcu_0.4.0-1-s390-vwO9c1/liburcu-0.4.0/tests'
make[2]: *** [all-recursive] Error 1
make[2]: Leaving directory `/build/buildd-liburcu_0.4.0-1-s390-vwO9c1/liburcu-0.4.0'
make[1]: *** [all] Error 2
dh_auto_build: make -j1 returned exit code 2
make: *** [build] Error 2
dpkg-buildpackage: error: debian/rules build gave error exit status 2
make[1]: Leaving directory `/build/buildd-liburcu_0.4.0-1-s390-vwO9c1/liburcu-0.4.0'

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

README: discuss mutex vs RCU interaction

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

standardize rcu_gp_ongoing

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

rename rcu_old_gp_ongoing to rcu_gp_ongoing

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

update LOAD_SHARED/STORE_SHARED for need_mb.

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

urcu: use unsigned long instead of long

As it is currently designed, urcu scheme never overflows and we do not use the
upper "sign" bit. But, nevertheless, just in case we choose to do it differently
in the future, use an unsigned long type to allow:

- overflow
- defined used of 0x80000000

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

update version to 0.4.0

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

URCU: rename light/heavy barriers to slave/master

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

QSBR URCU: remove unused reader_barrier() declaration

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

Update comments

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

Internal cleanup

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

rename internal_rcu_lock() into mutex_lock/unlock(&rcu_gp_lock)

Cleanup.

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

Add SIGURCU backward compatibility

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

Update support for MEMBARRIER_QUERY

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

Support sys_membarrier v6 ABI

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

Add sys_membarrier() dynamic detection, old liburcu.so -> liburcu-signal.so

See updated README for library renaming details.

liburcu is now dynamically detecting if sys_membarrier is available, and using
urcu-mb as fall back.

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

urcu signal-based renames

reader_barrier renamed to smp_mb_light
force_mb_all_readers renamed to smp_mb_heavy

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

signal-based urcu: rename force_mb_all_threads -> force_mb_all_readers

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

Cleanup urcu-defer static header

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

API prefix standardization: urcu_ -> rcu_

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

version 0.3.4

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

Support earlier glibc sched_setaffinity

Signed-off-by: Mathieu Desnoyers <mathieu.desnoyers@polymtl.ca>
Signed-off-by: Pedro Alves <pedro@codesourcery.com>

Remove bogus ; from defines

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

version 0.3.3

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

Consider __NO_LWSYNC__

This is set by the gcc when the target does not support the lwsync
opcode. This is the case for e500 core based CPUs.

I haven't touch tests/api_ppc.h because I don't see any users.

Signed-off-by: Sebastian Andrzej Siewior <bigeasy@linutronix.de>
Signed-off-by: Mathieu Desnoyers <mathieu.desnoyers@polymtl.ca>

version 0.3.2

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

s390 uatomic: fix new compiler support

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

Add extern "C" to support linking userspace RCU library with C++ applications

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

s390 uatomic arch fix

    In file included from urcu-static.h:40,
                     from urcu.c:35:
    ./urcu/uatomic_arch.h: In function ‘_uatomic_exchange’:
    ./urcu/uatomic_arch.h:88: warning: dereferencing ‘void *’ pointer
    ./urcu/uatomic_arch.h:89: warning: dereferencing ‘void *’ pointer
    ./urcu/uatomic_arch.h:89: error: expected ‘:’ or ‘)’ before ‘(’ token
    ./urcu/uatomic_arch.h: In function ‘_uatomic_cmpxchg’:
    ./urcu/uatomic_arch.h:131: warning: dereferencing ‘void *’ pointer
    ./urcu/uatomic_arch.h:132: warning: dereferencing ‘void *’ pointer
    ./urcu/uatomic_arch.h:132: error: expected ‘:’ or ‘)’ before ‘(’ token

Use same hidden pointer technique used for x86.

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

Fix s390 uatomic ops new compiler support

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

s390 uatomic: short memory operand support for new compilers

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

s390: uatomic add missing xchg return

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

s390: uatomic add missing inline and other { }

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

update s390 ifdefs

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

s390: add block after label

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

sparc,ppc,s390: uatomic ops update

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

Update arch_s390.h, missing definitions

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

s390: fix config.h include

 gcc -DHAVE_CONFIG_H -I. -I./urcu -I./urcu -g -O2 -c urcu.c  -fPIC -DPIC -o
  .libs/urcu.o
In file included from urcu-static.h:38,
                 from urcu.c:35:
./urcu/arch.h:32:27: error: config/config.h: No such file or directory

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

Update version to 0.3.1

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

Support sparcv9 32-bit build

From: David Miller <davem@davemloft.net>
Subject: Re: [ltt-dev] Sparc64 support added to Userspace RCU

From: Mathieu Desnoyers <mathieu.desnoyers@polymtl.ca>
Date: Thu, 22 Oct 2009 15:57:53 -0400

> Feedback is welcome,

__sparc_v8__ does not mean 64-bit longs or pointers as implied here:

"v8" was the last 32-bit standard of the cpu architecture.

Otherwise looks fine.

Although this port won't be very useful until it can be built in
32-bit mode.  As most applications on sparc64 systems are still
32-bit.  Like on powerpc, people only rarely build things 64-bit on
sparc64.

You need to build with "-Wa,-Av9a" on the GCC command line for that
case so that the assembler allows the v9 instructions emitted by your
macros, even when building for 32-bit.

Hope this helps.

Signed-off-by: Mathieu Desnoyers <mathieu.desnoyers@polymtl.ca>
CC: David Miller <davem@davemloft.net>

Update readme

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

cross-compilation: use $host instead of $target

$target should be used only when building a compiler. It indicates
the target system for which the compiler will build executables.

$host is the variable that should be used to indicate the type of
system the package we are compiling now will run on.

Also, update the README to say to use --host instead of --target.

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

Update version to 0.3.0

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

urcu-defer: generate linker error if call_rcu() is used

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

update README for defer_rcu()

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

Mark defer_rcu() API as experimental.

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

Document urcu-defer usage with dlclose()

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

Add defer_rcu_ratelimit()

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

update readme for rcu_defer()

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

urcu-defer: remove call_rcu() API, replace by defer_rcu()

Ensure we do not expose an API different from the kernel with the same name and
different semantic.

defer_rcu() cannot be called from within a RCU read-side C.S..

call_rcu() should eventually be re-implemented with struct rcu_head, permitting
to be called from within a RCU read-side C.S.

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

Sparc64: complete and test implementation

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

Add basic sparc64 support

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

update version to 0.2.4

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

uatomic compat: complete i386 support

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

uatomic: update atomic set/read, use STORE_SHARED/LOAD_SHARED

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

version 2.2.3

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

Fix gcc-4.1 x86_64 compability

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

Remove ACLOCAL_AMFLAGS=-I m4 from Makefile.am

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

Fixes to allow building on Power

Add errno.h to a number of files, and remove build dependency on m4.

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

Using AM_PROG_MKDIR_P for compatibility

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

tests: change some top_builddir to top_srcdir

We didn't have problems with this error because the VPATH saved us.
But let's be clean anyway.

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

update README about futex

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

Use mkdir_p (old) for older automake support

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

Stay safe on i686 fence compatibility

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

Add AC_CONFIG_MACRO_DIR([m4]), re-add ACLOCAL_AMFLAGS

Fixes warning:
libtoolize: putting auxiliary files in AC_CONFIG_AUX_DIR, `config'.
libtoolize: copying file `config/ltmain.sh'
libtoolize: Consider adding `AC_CONFIG_MACRO_DIR([m4])' to configure.ac and
libtoolize: rerunning libtoolize, to keep the correct libtool macros in-tree.
libtoolize: Consider adding `-I m4' to ACLOCAL_AMFLAGS in Makefile.am.

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

Update Makefile.am

- remove aclocal -I m4
- fix api.h dependency

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

AC_PROG_MKDIR_P needed with automake 1.9

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

Update rcutorture: test all RCU flavors

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

Make urcu/config.h work.

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

Compat futex

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

move config.h to urcu/config.h and install it

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

Support for sys_futex autodetection

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

Remove whitespace

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

update readme

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

update readme

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

Update configure.ac

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