Messages in this thread |  | | Date | Sat, 27 Jan 2018 15:46:51 -0800 | From | "Paul E. McKenney" <> | Subject | Re: [PATCH RFC 00/16] A new RCU implementation based on a fast consensus protocol |
| |
On Sat, Jan 27, 2018 at 09:57:03AM +0000, Lihao Liang wrote: > On Sat, Jan 27, 2018 at 7:57 AM, Paul E. McKenney > <paulmck@linux.vnet.ibm.com> wrote: > > On Sat, Jan 27, 2018 at 07:22:27AM +0000, Lihao Liang wrote: > >> On Thu, Jan 25, 2018 at 5:53 AM, Paul E. McKenney > >> <paulmck@linux.vnet.ibm.com> wrote: > >> > On Tue, Jan 23, 2018 at 03:59:25PM +0800, lianglihao@huawei.com wrote: > >> >> From: Lihao Liang <lianglihao@huawei.com> > >> >> > >> >> Dear Paul, > >> >> > >> >> This patch set implements a preemptive version of RCU (PRCU) based on the following paper: > >> >> > >> >> Fast Consensus Using Bounded Staleness for Scalable Read-mostly Synchronization. > >> >> Haibo Chen, Heng Zhang, Ran Liu, Binyu Zang, and Haibing Guan. > >> >> IEEE Transactions on Parallel and Distributed Systems (TPDS), 2016. > >> >> https://dl.acm.org/citation.cfm?id=3024114.3024143 > >> >> > >> >> We have also added preliminary callback-handling support. Thus, the current version > >> >> provides APIs prcu_read_lock(), prcu_read_unlock(), synchronize_prcu(), call_prcu(), > >> >> and prcu_barrier(). > >> >> > >> >> This is an experimental patch, so it would be good to have some feedback. > >> >> > >> >> Known shortcoming is that the grace-period version is incremented in synchronize_prcu(). > >> >> If call_prcu() or prcu_barrier() is called but there is no synchronized_prcu() invoked, > >> >> callbacks cannot be invoked. Later version should address this issue, e.g. adding a > >> >> grace-period expedition mechanism. Others include to use a a hierarchical structure, > >> >> taking into account the NUMA topology, to send IPI in synchronize_prcu(). > >> >> > >> >> We have tested the implementation using rcutorture on both an x86 and ARM64 machine. > >> >> PRCU passed 1h and 3h tests on all the newly added config files except PRCU07 reported BUG > >> >> in a 1h run. > >> >> > >> >> [ 1593.604201] ---[ end trace b3bae911bec86152 ]--- > >> >> [ 1594.629450] prcu-torture:torture_onoff task: offlining 14 > >> >> [ 1594.755553] smpboot: CPU 14 is now offline > >> >> [ 1594.757732] prcu-torture:torture_onoff task: offlined 14 > >> >> [ 1597.765149] prcu-torture:torture_onoff task: onlining 11 > >> >> [ 1597.766795] smpboot: Booting Node 0 Processor 11 APIC 0xb > >> >> [ 1597.804102] prcu-torture:torture_onoff task: onlined 11 > >> >> [ 1599.365098] prcu-torture: rtc: ffffffffb0277b90 ver: 66358 tfle: 0 rta: 66358 rtaf: 0 > >> >> rtf: 66349 rtmbe: 0 rtbe: 1 rtbke: 0 rtbre: 0 rtbf: 0 rtb: 0 nt: 2233418 > >> >> onoff: 191/191:199/199 34,199:59,5102 10403:0 (HZ=1000) barrier: 188/189:1 cbflood: 225 > >> >> [ 1599.367946] prcu-torture: !!! > >> >> [ 1599.367966] ------------[ cut here ]------------ > >> > > >> > The "rtbe: 1" indicates that your implementation of prcu_barrier() > >> > failed to wait for all preceding call_prcu() callbacks to be invoked. > >> > > >> > Does the immediately following "Reader Pipe:" list have any but the > >> > first two numbers non-zero? > >> > >> Yes. > > > > If the third or subsequent numbers are non-zero, that would indicate > > too-short grace periods. This would be a critical bug in PRCU. > > > >> >> We have also compared PRCU with TREE RCU using rcuperf with gp_exp set to true, that is > >> >> synchronize_rcu_expedited was tested. > >> >> > >> >> The rcuperf results are as follows (average grace-period duration in ms of ten 10min runs): > >> >> > >> >> 16*Intel Xeon CPU@2.4GHz, 16GB memory, Ubuntu Linux 3.13.0-47-generic > >> >> > >> >> CPUs 2 4 8 12 15 16 > >> >> PRCU 0.14 1.07 4.15 8.02 10.79 15.16 > >> >> TREE 49.30 104.75 277.55 390.82 620.82 1381.54 > >> >> > >> >> 64*Cortex-A72 CPU@2.4GHz, 130GB memory, Ubuntu Linux 4.10.0-21.23-generic > >> >> > >> >> CPUs 2 4 8 16 32 48 63 64 > >> >> PRCU 0.23 19.69 38.28 63.21 95.41 167.18 252.01 1841.44 > >> >> TREE 416.73 901.89 1060.86 743.00 920.66 1325.21 1646.20 23806.27 > >> > > >> > Well, at the very least, this is a bug report on either expedited RCU > >> > grace-period latency or on rcuperf's measurements, and thank you for that. > >> > I will look into this. In the meantime, could you please let me know > >> > exactly how you invoked rcuperf? > >> > >> We used the following command to invoke rcuperf: > >> > >> sudo ./kvm.sh --torture rcuperf --duration 10 --configs 10*TREE > >> > >> The actual script run-rcuperf.sh to run the experiments can be found > >> in the following email of this patch series: > >> > >> [PATCH RFC 15/16] rcutorture: Add scripts to run experiments > >> > >> Please let us know how it goes. > > > > Will do! > > > > As I said before, at the very least you have identified a performance bug > > in RCU expedited grace periods. > > > > I should add that we also tested the normal synchronize_rcu() on the > same x86 machine, and the rcuperf figures were about 10 times slower > than those of synchronize_rcu_expedited(). > > Is this expected for synchronize_rcu()?
Yes, this is a deliberate design decision. The goal of synchronize_rcu() is to minimize CPU overhead, which it does by aggressively batching concurrent requests -- and also by batching not-quite-so-concurrent requests. The other end of this tradeoff is that synchronize_rcu() has relatively high latency. In contrast, the goal of synchronize_rcu_expedited() is lower latency, with the penalty of higher CPU utilization and more disturbance of real-time workloads. Note that synchronize_prcu()'s use of IPIs disturbs real-time workloads in a manner similar to synchronize_rcu_expedited(), but that synchronize_prcu() further disturbs idle CPUs. In my experience, disturbing idle CPUs doesn't make the people with battery-powered systems very happy.
Thanx, Paul
> Best, > Lihao. > > > Thanx, Paul > > > >> Many thanks, > >> Lihao. > >> > >> > I have a few comments on some of your patches based on a quick scan > >> > through them. > >> > > >> > Thanx, Paul > >> > > >> >> Best wishes, > >> >> Lihao. > >> >> > >> >> > >> >> Lihao Liang (15): > >> >> rcutorture: Add PRCU rcu_torture_ops > >> >> rcutorture: Add PRCU test config files > >> >> rcuperf: Add PRCU rcu_perf_ops > >> >> rcuperf: Add PRCU test config files > >> >> rcuperf: Set gp_exp to true for tests to run > >> >> prcu: Implement call_prcu() API > >> >> prcu: Implement PRCU callback processing > >> >> prcu: Implement prcu_barrier() API > >> >> rcutorture: Test call_prcu() and prcu_barrier() > >> >> rcutorture: Add basic ARM64 support to run scripts > >> >> prcu: Add PRCU Kconfig parameter > >> >> prcu: Comment source code > >> >> rcuperf: Add config files with various CONFIG_NR_CPUS > >> >> rcutorture: Add scripts to run experiments > >> >> Add GPLv2 license > >> >> > >> >> Heng Zhang (1): > >> >> prcu: Add PRCU implementation > >> >> > >> >> include/linux/interrupt.h | 3 + > >> >> include/linux/prcu.h | 122 +++++ > >> >> include/linux/rcupdate.h | 1 + > >> >> init/Kconfig | 7 + > >> >> init/main.c | 2 + > >> >> kernel/rcu/Makefile | 1 + > >> >> kernel/rcu/prcu.c | 497 +++++++++++++++++++++ > >> >> kernel/rcu/rcuperf.c | 33 +- > >> >> kernel/rcu/rcutorture.c | 40 +- > >> >> kernel/rcu/tree.c | 1 + > >> >> kernel/sched/core.c | 2 + > >> >> kernel/time/timer.c | 2 + > >> >> kvm.sh | 452 +++++++++++++++++++ > >> >> run-rcuperf.sh | 26 ++ > >> >> .../testing/selftests/rcutorture/bin/functions.sh | 17 +- > >> >> .../selftests/rcutorture/configs/rcu/CFLIST | 5 + > >> >> .../selftests/rcutorture/configs/rcu/PRCU02 | 27 ++ > >> >> .../selftests/rcutorture/configs/rcu/PRCU02.boot | 1 + > >> >> .../selftests/rcutorture/configs/rcu/PRCU03 | 23 + > >> >> .../selftests/rcutorture/configs/rcu/PRCU03.boot | 2 + > >> >> .../selftests/rcutorture/configs/rcu/PRCU06 | 26 ++ > >> >> .../selftests/rcutorture/configs/rcu/PRCU06.boot | 5 + > >> >> .../selftests/rcutorture/configs/rcu/PRCU07 | 25 ++ > >> >> .../selftests/rcutorture/configs/rcu/PRCU07.boot | 2 + > >> >> .../selftests/rcutorture/configs/rcu/PRCU09 | 19 + > >> >> .../selftests/rcutorture/configs/rcu/PRCU09.boot | 1 + > >> >> .../selftests/rcutorture/configs/rcuperf/CFLIST | 1 + > >> >> .../selftests/rcutorture/configs/rcuperf/PRCU | 20 + > >> >> .../selftests/rcutorture/configs/rcuperf/PRCU-12 | 21 + > >> >> .../rcutorture/configs/rcuperf/PRCU-12.boot | 1 + > >> >> .../selftests/rcutorture/configs/rcuperf/PRCU-14 | 21 + > >> >> .../rcutorture/configs/rcuperf/PRCU-14.boot | 1 + > >> >> .../selftests/rcutorture/configs/rcuperf/PRCU-15 | 21 + > >> >> .../rcutorture/configs/rcuperf/PRCU-15.boot | 1 + > >> >> .../selftests/rcutorture/configs/rcuperf/PRCU-16 | 21 + > >> >> .../rcutorture/configs/rcuperf/PRCU-16.boot | 1 + > >> >> .../selftests/rcutorture/configs/rcuperf/PRCU-2 | 21 + > >> >> .../rcutorture/configs/rcuperf/PRCU-2.boot | 1 + > >> >> .../selftests/rcutorture/configs/rcuperf/PRCU-32 | 21 + > >> >> .../rcutorture/configs/rcuperf/PRCU-32.boot | 1 + > >> >> .../selftests/rcutorture/configs/rcuperf/PRCU-4 | 21 + > >> >> .../rcutorture/configs/rcuperf/PRCU-4.boot | 1 + > >> >> .../selftests/rcutorture/configs/rcuperf/PRCU-48 | 21 + > >> >> .../rcutorture/configs/rcuperf/PRCU-48.boot | 1 + > >> >> .../selftests/rcutorture/configs/rcuperf/PRCU-56 | 21 + > >> >> .../rcutorture/configs/rcuperf/PRCU-56.boot | 1 + > >> >> .../selftests/rcutorture/configs/rcuperf/PRCU-60 | 21 + > >> >> .../rcutorture/configs/rcuperf/PRCU-60.boot | 1 + > >> >> .../selftests/rcutorture/configs/rcuperf/PRCU-62 | 21 + > >> >> .../rcutorture/configs/rcuperf/PRCU-62.boot | 1 + > >> >> .../selftests/rcutorture/configs/rcuperf/PRCU-64 | 21 + > >> >> .../rcutorture/configs/rcuperf/PRCU-64.boot | 1 + > >> >> .../selftests/rcutorture/configs/rcuperf/PRCU-8 | 21 + > >> >> .../rcutorture/configs/rcuperf/PRCU-8.boot | 1 + > >> >> .../selftests/rcutorture/configs/rcuperf/PRCU.boot | 1 + > >> >> .../selftests/rcutorture/configs/rcuperf/TREE-12 | 21 + > >> >> .../selftests/rcutorture/configs/rcuperf/TREE-14 | 21 + > >> >> .../selftests/rcutorture/configs/rcuperf/TREE-15 | 21 + > >> >> .../selftests/rcutorture/configs/rcuperf/TREE-16 | 21 + > >> >> .../selftests/rcutorture/configs/rcuperf/TREE-2 | 21 + > >> >> .../selftests/rcutorture/configs/rcuperf/TREE-32 | 21 + > >> >> .../selftests/rcutorture/configs/rcuperf/TREE-4 | 21 + > >> >> .../selftests/rcutorture/configs/rcuperf/TREE-48 | 21 + > >> >> .../selftests/rcutorture/configs/rcuperf/TREE-56 | 21 + > >> >> .../selftests/rcutorture/configs/rcuperf/TREE-60 | 21 + > >> >> .../selftests/rcutorture/configs/rcuperf/TREE-62 | 21 + > >> >> .../selftests/rcutorture/configs/rcuperf/TREE-64 | 21 + > >> >> .../selftests/rcutorture/configs/rcuperf/TREE-8 | 21 + > >> >> 68 files changed, 1918 insertions(+), 5 deletions(-) > >> >> create mode 100644 include/linux/prcu.h > >> >> create mode 100644 kernel/rcu/prcu.c > >> >> create mode 100755 kvm.sh > >> >> create mode 100755 run-rcuperf.sh > >> >> create mode 100644 tools/testing/selftests/rcutorture/configs/rcu/PRCU02 > >> >> create mode 100644 tools/testing/selftests/rcutorture/configs/rcu/PRCU02.boot > >> >> create mode 100644 tools/testing/selftests/rcutorture/configs/rcu/PRCU03 > >> >> create mode 100644 tools/testing/selftests/rcutorture/configs/rcu/PRCU03.boot > >> >> create mode 100644 tools/testing/selftests/rcutorture/configs/rcu/PRCU06 > >> >> create mode 100644 tools/testing/selftests/rcutorture/configs/rcu/PRCU06.boot > >> >> create mode 100644 tools/testing/selftests/rcutorture/configs/rcu/PRCU07 > >> >> create mode 100644 tools/testing/selftests/rcutorture/configs/rcu/PRCU07.boot > >> >> create mode 100644 tools/testing/selftests/rcutorture/configs/rcu/PRCU09 > >> >> create mode 100644 tools/testing/selftests/rcutorture/configs/rcu/PRCU09.boot > >> >> create mode 100644 tools/testing/selftests/rcutorture/configs/rcuperf/PRCU > >> >> create mode 100644 tools/testing/selftests/rcutorture/configs/rcuperf/PRCU-12 > >> >> create mode 100644 tools/testing/selftests/rcutorture/configs/rcuperf/PRCU-12.boot > >> >> create mode 100644 tools/testing/selftests/rcutorture/configs/rcuperf/PRCU-14 > >> >> create mode 100644 tools/testing/selftests/rcutorture/configs/rcuperf/PRCU-14.boot > >> >> create mode 100644 tools/testing/selftests/rcutorture/configs/rcuperf/PRCU-15 > >> >> create mode 100644 tools/testing/selftests/rcutorture/configs/rcuperf/PRCU-15.boot > >> >> create mode 100644 tools/testing/selftests/rcutorture/configs/rcuperf/PRCU-16 > >> >> create mode 100644 tools/testing/selftests/rcutorture/configs/rcuperf/PRCU-16.boot > >> >> create mode 100644 tools/testing/selftests/rcutorture/configs/rcuperf/PRCU-2 > >> >> create mode 100644 tools/testing/selftests/rcutorture/configs/rcuperf/PRCU-2.boot > >> >> create mode 100644 tools/testing/selftests/rcutorture/configs/rcuperf/PRCU-32 > >> >> create mode 100644 tools/testing/selftests/rcutorture/configs/rcuperf/PRCU-32.boot > >> >> create mode 100644 tools/testing/selftests/rcutorture/configs/rcuperf/PRCU-4 > >> >> create mode 100644 tools/testing/selftests/rcutorture/configs/rcuperf/PRCU-4.boot > >> >> create mode 100644 tools/testing/selftests/rcutorture/configs/rcuperf/PRCU-48 > >> >> create mode 100644 tools/testing/selftests/rcutorture/configs/rcuperf/PRCU-48.boot > >> >> create mode 100644 tools/testing/selftests/rcutorture/configs/rcuperf/PRCU-56 > >> >> create mode 100644 tools/testing/selftests/rcutorture/configs/rcuperf/PRCU-56.boot > >> >> create mode 100644 tools/testing/selftests/rcutorture/configs/rcuperf/PRCU-60 > >> >> create mode 100644 tools/testing/selftests/rcutorture/configs/rcuperf/PRCU-60.boot > >> >> create mode 100644 tools/testing/selftests/rcutorture/configs/rcuperf/PRCU-62 > >> >> create mode 100644 tools/testing/selftests/rcutorture/configs/rcuperf/PRCU-62.boot > >> >> create mode 100644 tools/testing/selftests/rcutorture/configs/rcuperf/PRCU-64 > >> >> create mode 100644 tools/testing/selftests/rcutorture/configs/rcuperf/PRCU-64.boot > >> >> create mode 100644 tools/testing/selftests/rcutorture/configs/rcuperf/PRCU-8 > >> >> create mode 100644 tools/testing/selftests/rcutorture/configs/rcuperf/PRCU-8.boot > >> >> create mode 100644 tools/testing/selftests/rcutorture/configs/rcuperf/PRCU.boot > >> >> create mode 100644 tools/testing/selftests/rcutorture/configs/rcuperf/TREE-12 > >> >> create mode 100644 tools/testing/selftests/rcutorture/configs/rcuperf/TREE-14 > >> >> create mode 100644 tools/testing/selftests/rcutorture/configs/rcuperf/TREE-15 > >> >> create mode 100644 tools/testing/selftests/rcutorture/configs/rcuperf/TREE-16 > >> >> create mode 100644 tools/testing/selftests/rcutorture/configs/rcuperf/TREE-2 > >> >> create mode 100644 tools/testing/selftests/rcutorture/configs/rcuperf/TREE-32 > >> >> create mode 100644 tools/testing/selftests/rcutorture/configs/rcuperf/TREE-4 > >> >> create mode 100644 tools/testing/selftests/rcutorture/configs/rcuperf/TREE-48 > >> >> create mode 100644 tools/testing/selftests/rcutorture/configs/rcuperf/TREE-56 > >> >> create mode 100644 tools/testing/selftests/rcutorture/configs/rcuperf/TREE-60 > >> >> create mode 100644 tools/testing/selftests/rcutorture/configs/rcuperf/TREE-62 > >> >> create mode 100644 tools/testing/selftests/rcutorture/configs/rcuperf/TREE-64 > >> >> create mode 100644 tools/testing/selftests/rcutorture/configs/rcuperf/TREE-8 > >> >> > >> >> -- > >> >> 2.14.1.729.g59c0ea183 > >> >> > >> > > >> > > >
|  |