[RFC, PATCH] state machine based rcu

[Manfred Spraul]

This is a multi-part message in MIME format.Hi all,

I've written a prove of concept patch that implements some ideas that 
Paul and I have discussed in the last few days:
Attached is both a patch and a copy of the rcuclassic.c file, the patch 
is probably fully unreadable because it's rewriting 80% of the code.
Unfortunately, the patch removes the new debug features that Ingo just 
added, they must be added back...

The patch boots qemu with 8 cpus, although there is a random crash 
somewhere [memory overwritten by 0xcc]

>>>>

Right now, each cpu locally decides what it does, the only
global thing is the bitmap that keeps track of grace periods.
What this grace period means is defined by the cpu: it's possible
that some cpus interpret a grace period as the sign for
calling the rcu callbacks, other cpus just interpret it as the
sign that it should look for the next grace period.

The patch reverses that: Now there is a global state.
The system is either collecting pointers for the next grace
period, or it's waiting for a grace period to complete.
All cpus do the same thing.

Additionally, the patch removes the cpu bitmask:
Since all cpus must do something and the only thing that
is tested for is an empty bitmask, the bitmask can be replaced
with an integer that counts the outstanding cpus.
This could be an atomic_t.
(right now, the bitmasks are still there, but just for debugging).
If needed, a slow path can reconstruct the bitmap on the fly.
{for_each_online_cpu(i) if (rcu_pending(i) {do_something()} }

The patch is work in progress:
- NMIs do not work yet, they cause deadlocks.
- synchronize_sched() and call_rcu_sched() are broken.
- some debug printks are left inside.
- The counters could be made hierarchical for better scalability.
- the nohz code is not tested.

The patch is against tip/rcu.
---
include/linux/hardirq.h    |    4 +-
include/linux/rcuclassic.h |  179 +++++---
include/linux/rcucpumask.h |  154 +++++++
kernel/Makefile            |    2 +-
kernel/rcuclassic.c        | 1081 
++++++++++++++++++++++++--------------------
kernel/rcucpumask.c        |  119 +++++
6 files changed, 984 insertions(+), 555 deletions(-)
create mode 100644 include/linux/rcucpumask.h
create mode 100644 kernel/rcucpumask.c