linux-kernel - [RFC, PATCH] state machine based rcu

lists.openwall.net		lists / announce owl-users owl-dev john-users john-dev passwdqc-users yescrypt popa3d-users / oss-security kernel-hardening musl sabotage tlsify passwords / crypt-dev xvendor / Bugtraq Full-Disclosure linux-kernel linux-netdev linux-ext4 linux-hardening linux-cve-announce PHC
Open Source and information security mailing list archives

Hash Suite: Windows password security audit tool. GUI, reports in PDF.

[<prev] [next>] [thread-next>] [day] [month] [year] [list]

Date:	Thu, 21 Aug 2008 17:27:37 +0200
From:	Manfred Spraul <manfred@...orfullife.com>
To:	Linux Kernel Mailing List <linux-kernel@...r.kernel.org>
CC:	paulmck@...ux.vnet.ibm.com
Subject: [RFC, PATCH] state machine based rcu

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

View attachment "0001-kernel-rcuclassic.c-state-machine-based-rcu-impleme.patch" of type "text/plain" (56790 bytes)

View attachment "rcuclassic.c" of type "text/plain" (25838 bytes)