Add runall.sh test

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

Fix alignment of test names

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

Align the summary result

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

Add verbose mode

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

Print reader duration

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

Delay reader in loops, not us

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

Add -c option for read-side C.S. length to tests

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

fix runtests.sh

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

runtests include mutex test

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

Add test mutex

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

Add set affinity -a option to tests

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

Unlikely for tests

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

Add i586 i686 to Makefile

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

Update readme

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

Add Makefile and Makefile64 architecture autodetection

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

Make sure the rwlock and per thread lock could detect races

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

Fix deadlock in qsbr code

Readers must go offline because they unregister.

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

Fix qsbr urcu implementation

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

Update makefiles

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

Add missing void to function declaration

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

Use more lightweight timer mechanism in test

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

Remove unneeded signal-based MB from QSBR rcu

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

Fix signal handler installation

The signal handler is not being set in conformance with the sigaction
manpage. Because of this, it is probably not set at all. Valgrind also
generates an error. This patch fixes this.

Signed-off-by: Pierre-Marc Fournier <pierre-marc.fournier@polymtl.ca>
Signed-off-by: Mathieu Desnoyers <mathieu.desnoyers@polymtl.ca>

Add missing urcu-qsbr

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

Add runtests.sh

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

Add mb urcu flavor test

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

Add perthread lock scaling test

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

Move test start time closer to enable

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

Add rwlock scalability test

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

Add scalability qsbr test

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

Modify test_urcu to make more suitable for scalability benchmark

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

Add number of reader/writers parameters to tests

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

Add QSBR RCU timing tests

urcu-qsbr can be used for QSBR-based RCU.

Currently not built as a full-blown library .so, but could.

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

update test timings for writer

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

Add per thread lock test case

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

Another ooo mem isched update

really just to simplify the LTL formula.

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

Update isched ooomem model

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

Update ooo isched test

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

Use nicer LTL formula with eventually for ooomem model

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

Add speculative execution (prefetch) to model

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

Fix comment on top of oomem two writes model

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

Add Intel ipi urcu model run results

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

Add multiple arch support (alpha, intel, powerpc)

A simple define controls the architecture tested.

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

Verification run #1, ipi and no-ipi results

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

Model used for ipi verification run #1

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

Configuration for remote barrier formal verif run

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

Update spin model

- Add memory poisoning to the ooo insn sched section.
- Put pointer update into ooo insn sched section.

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

Use define SLAB_SIZE in promela model

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

urcu model wmb/read barrier depend

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

Add .gitignore entries to reduce 'git status' chatter

Add some entries to .gitignore files to reduce chatter from "git status".

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

catch urcu-paulmck.spin to my local version

The attached patch catches the repository up to my local version.
This adds the following:

o       Checking for no-progress cycles.

o       Allow enabling and disabling of update-side signal-mediated
        broadcast memory barriers via #define statements.

o       Enabling only those update-side signal-mediated broadcast
        memory barriers that are required for correctness.

This version assumes that synchronize_rcu() is locally ordered, for
example, with smp_mb() calls between each pair of major statements.
Please note that smp_mb() is -not- assumed within the loops nor
immediately before the second counter flip.

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

sync_core to smp_mb transition

- move sync_core to smp_mb in urcu.c, update comments.
- cpuid clashes with -fPIC because it clobbers ebx. Use mb() if ___PIC__ is
  defined.

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

Fix standard (no remote barrier) parity flip bug

A bug was introduced when moving from statically assigning the parity to wait
for on the update side (first even, then odd) to a model trying to deal the
single flip test case. It occurs that when busy-looping, the parity flip
occurred when it should not.

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

Special-case reader/writer busy-loop for signals in progress

The reader may choose to always ignore signal requests or to busy-loop always
waiting for signal requests. Those are much less interesting wrt progress. Add
progress statements in those loops.

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

Fix single flip test

The single flip test requires to keep track of parity evolution across the loop
iterations. Keep it as a local variable so we don't end up adding unexisting
dependencies.

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

Fix urcu controldataflow model remote barriers

Need to split the pointer read from the data access to allow the writer to issue
a memory barrier (actually more than one) to let the single flip race occur.

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

Document update in urcu.spin header

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

Add extended urcu model with ooo mem and instruction scheduling

Here is the new model I worked on for the past weeks. It models :

- out-of-order memory accesses.
- instruction scheduling by the CPU on the write and read sides.

The model as committed in the repository at

formal-model/urcu-controldataflow

models the urcu with memory barriers on the read-side. It works exactly
as expected. mb() on the read-side is enabled when we have this in
the DEFINES file :

//#define REMOTE_BARRIERS   (commented out)

To run all tests, just fire :

make
(with spin 5.1.7 here. 5.2.0 has a bug with arrays of size 1)

Verification summary
asserts.log:State-vector 64 byte, depth reached 2801, errors: 0
urcu_free.log:State-vector 88 byte, depth reached 3302, errors: 0
urcu_free_no_mb.log:State-vector 88 byte, depth reached 24407, errors: 1
urcu_free_single_flip.log:State-vector 88 byte, depth reached 2904, errors: 1
urcu_progress_reader.log:State-vector 80 byte, depth reached 3353, errors: 0
urcu_progress_writer_error.log:State-vector 80 byte, depth reached 8035, errors: 1
urcu_progress_writer.log:State-vector 80 byte, depth reached 3348, errors: 0

However, I still have a problem modeling the signal-based barriers.

(remove comment from the define)

make urcu_free_single_flip should generate an error (just like it does
with the reader-mb() case), but it does not. I think it's caused by
added serialization due to the writer waiting on the reader barriers.

Normally, this model should behave similarly to yours : it should honor
the barrier requests before each read-side instruction IIF the
instruction execution order is in program order.

I'm pretty sure I missed something obvious, but I think it's time I
share the model I have with you so you might help me spot what I missed.
It may be as simple as an incorrect instruction scheduling dependency
too.

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

Support gcc which does not support constructor attribute

- Add call to urcu_init from reader thread registration.
- Try to move the constructor and destructor attribute to the prototype, in case
  gcc has problems with these attributes used with the function definition.

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

Fix opensuse powerpc build

I gave this code a spin on a G5 (PPC970) OpenSuse 10.3 system and
encountered same issues that should fix fot tyou next update.

The liburcu make system sis not set up for biarch (32-/64-bit) builds on
PPC. SLES10/OpenSUSE-10.3 is a default 32-bit, 64-bit capable system. To
build a 64-bit you need to insert -m64 for all compiles and link
operations. Also for 64-bit make install should move liburcu.so
to /usr/lib64 not /usr/lib. This is required to FSB complience. Is
worked around this by copying Makefile to Makefile64 and made the
required changes there.

For SLES11 we changed to to a 64-bit default and 32-bit capable system.
In either case you need to be able to build both 32-/64-bit liburcu.so
on same systems and need to insure that make install is appropriate.

Also I found that __SIZEOF_LONG__ was not defined and resulted in a
sigill on PPC64. I suspect this is XLC specific and you need solution
that works for GCC builds as well.

I have attached a patch that implement these change for your review.
With this patch I can build liburcu and run the tests successfully.

Finally when I build 32-bit (default for OpenSUSE 10) I get a unhandled
SIGUSER1. I ran out of weekend before I could figure that out.

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

Document thread registration in urcu.h

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

Document rcu_register_thread in README

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

Update ooo mem model comments

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

Remove old memory models

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

Update out of order memory models to include instruction scheduling

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

Move reader barrier within if statement for outermost nesting

Innermost nesting levels do not need this barrier. Slight runtime cost when
compiling with reader barriers in place. Does not change anything when using the
signal-based scheme.

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

Use sync_core() in the write side to match current formal verif model

The formal model we currently have assumes serialized instruction execution on
the write-side. Until we extend this model to allow out-of-order instruction
execution, add equivalent synchronization in the library code.

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

add sync_core primitive

Add sync_core() to serialize instruction execution on a core.

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

Add rewrite of rep_nop

Rewritten from scratch, OK for LGPL license.

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

Remove rep_nop() (GPL)

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

LGPLv2.1 relicensing statement

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

Apply MIT-style license to compiler.h

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

Rewrite of likely, unlikely, barrier and ACCESS_ONCE

compiler.h now licensed under MIT-style license.

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

Removing GPL likely, unlikely, ACCESS_ONCE and barrier

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

Create separate document for relicensing details

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

Fix some typos in PowerPC support code.

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

Remove bogus comment.

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

Implementation of xchg primitives derived from MIT license

See LICENSE for details.

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

Add Paul's URCU model

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

Fix arch_ppc precompiler error

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

Fix precompiler error in arch_*.h, add arch-api test

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

Add final license to test file, cleanup makefile

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

Remove automatically generated api.h from repository

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

Add missing urcu-static.h

This new file should be inly included in LGPL-compatible code.

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

LGPL relicensing part 2

Rewrote the non-trivial functions in arch_ppc.h and arch_x86.h.

Added complete header license declarations. Created LICENSE file to explain the
library licence.

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

LGPLv2.1 relicensing

Except the content of arch_x86.h and arch_ppc.h, everything that was not
LGPL-compatible has been either rewritten or was simply a trivial one-liner.

The only content which could still be non-LGPL licensable in this commit is :

arch_ppc.h: atomic_inc()
            __xchg_u32()
            get_cycles (maybe ?)

arch_x86.h: __xchg()

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

Add ACCESS_ONCE to _STORE_SHARED

We assume that the compiler does not reorder _STORE_SHARED across each other
and wrt _READ_SHARED. We therefore need to mark this access as volatile. The
compiler cannot reorder volatile accesses.

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

LGPL relicensing of IBM's contributions

Add comments noting IBM's permission to relicense its contributions to the
urcu.h and urcu.c files under the LGPLv2 license, or any later version.

Signed-off-by: Paul E. McKenney <paulmck@linux.vnet.ibm.com>
Reviewed-by: Steven L. Bennett <steven.bennett@us.ibm.com>

formal verif : move bits produced declarations closer to processes

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

Add no sync_core() test to ooo two writes model

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

Add instruction scheduling model using SSA model

As promised, here is a new model :-) So far the results are very good.

Basically, I model the dependencies between the instructions using a SSA
assignment. It behaves a bit like a Petri network, passing tokens
between the "instructions". When instructions have multiple dependencies
as input, they wait for all their input tokens to be ready before they
execute. It assumes we have an infinite number of registers available to
hold the variables, given this is an "abstract" architecture.

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

Add readme file

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

Remove arch.h

Created by build scripts.

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

Add missing arch.h

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

Add ooo mem instruction scheduling

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

Remove unneeded signal in the cache-coherent case

the "reader kick" signal is only needed to perform a smp_mc() on readers, which
is pointless in a cache-coherent arch.

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

Minor fix to userspace-rcu Makefile

Small update to the Makefile to allow it to clean up more completely.

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

Support kernels with broken signal delivery

Some Linux kernels seems to have problems sending _all_ the signals. Use a
workaround which re-sends the signal when we wait for it to be executed.

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

Add x86 and ppc arch definitions

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

change reader_data for reader_registry

> > In Figure 9, "reader_data" shouldn't be used as both a variable name
> > and a structure tag.  Furthermore, the text needs to explain what it
> > is.
>
> I will defer to Mathieu on this one, though it would certainly prevent
> using this code in a C++ program.
>

Yes, I've been lazy on the naming here. How about :

struct reader_registry {
        pthread_t tid;
        long *urcu_active_readers;
};

static struct reader_registry *registry;

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