From fbce7497ee5af800a1c350c73f3c3f103cb27a15 Mon Sep 17 00:00:00 2001 From: "Paul E. McKenney" Date: Tue, 24 Jun 2014 09:26:11 -0700 Subject: rcu: Parallelize and economize NOCB kthread wakeups An 80-CPU system with a context-switch-heavy workload can require so many NOCB kthread wakeups that the RCU grace-period kthreads spend several tens of percent of a CPU just awakening things. This clearly will not scale well: If you add enough CPUs, the RCU grace-period kthreads would get behind, increasing grace-period latency. To avoid this problem, this commit divides the NOCB kthreads into leaders and followers, where the grace-period kthreads awaken the leaders each of whom in turn awakens its followers. By default, the number of groups of kthreads is the square root of the number of CPUs, but this default may be overridden using the rcutree.rcu_nocb_leader_stride boot parameter. This reduces the number of wakeups done per grace period by the RCU grace-period kthread by the square root of the number of CPUs, but of course by shifting those wakeups to the leaders. In addition, because the leaders do grace periods on behalf of their respective followers, the number of wakeups of the followers decreases by up to a factor of two. Instead of being awakened once when new callbacks arrive and again at the end of the grace period, the followers are awakened only at the end of the grace period. For a numerical example, in a 4096-CPU system, the grace-period kthread would awaken 64 leaders, each of which would awaken its 63 followers at the end of the grace period. This compares favorably with the 79 wakeups for the grace-period kthread on an 80-CPU system. Reported-by: Rik van Riel Signed-off-by: Paul E. McKenney --- Documentation/kernel-parameters.txt | 7 +++++++ 1 file changed, 7 insertions(+) (limited to 'Documentation') diff --git a/Documentation/kernel-parameters.txt b/Documentation/kernel-parameters.txt index 910c3829f81d..770662c42c9f 100644 --- a/Documentation/kernel-parameters.txt +++ b/Documentation/kernel-parameters.txt @@ -2802,6 +2802,13 @@ bytes respectively. Such letter suffixes can also be entirely omitted. quiescent states. Units are jiffies, minimum value is one, and maximum value is HZ. + rcutree.rcu_nocb_leader_stride= [KNL] + Set the number of NOCB kthread groups, which + defaults to the square root of the number of + CPUs. Larger numbers reduces the wakeup overhead + on the per-CPU grace-period kthreads, but increases + that same overhead on each group's leader. + rcutree.qhimark= [KNL] Set threshold of queued RCU callbacks beyond which batch limiting is disabled. -- cgit v1.3-14-g43fede From 5726ce06ad6bcd8dd75a204d1465c99a2f897d3a Mon Sep 17 00:00:00 2001 From: "Paul E. McKenney" Date: Tue, 13 May 2014 10:14:51 -0700 Subject: documentation: Clarify wake-up/memory-barrier relationship This commit adds an example demonstrating that if a wake_up() doesn't actually wake something up, no memory ordering is provided. Reported-by: Peter Zijlstra Signed-off-by: Paul E. McKenney Reviewed-by: Josh Triplett Reviewed-by: Lai Jiangshan Acked-by: Peter Zijlstra --- Documentation/memory-barriers.txt | 15 +++++++++++++++ 1 file changed, 15 insertions(+) (limited to 'Documentation') diff --git a/Documentation/memory-barriers.txt b/Documentation/memory-barriers.txt index f1dc4a215593..a6ca533a73fc 100644 --- a/Documentation/memory-barriers.txt +++ b/Documentation/memory-barriers.txt @@ -1893,6 +1893,21 @@ between the STORE to indicate the event and the STORE to set TASK_RUNNING: STORE current->state LOAD event_indicated +To repeat, this write memory barrier is present if and only if something +is actually awakened. To see this, consider the following sequence of +events, where X and Y are both initially zero: + + CPU 1 CPU 2 + =============================== =============================== + X = 1; STORE event_indicated + smp_mb(); wake_up(); + Y = 1; wait_event(wq, Y == 1); + wake_up(); load from Y sees 1, no memory barrier + load from X might see 0 + +In contrast, if a wakeup does occur, CPU 2's load from X would be guaranteed +to see 1. + The available waker functions include: complete(); -- cgit v1.3-14-g43fede From 5e40ad7f6a038cfa42e0605764366d994701eab7 Mon Sep 17 00:00:00 2001 From: Pranith Kumar Date: Mon, 9 Jun 2014 11:51:23 -0400 Subject: documentation: Update reference, kerneltrap.org no longer works The kerneltrap.org site no longer works, so this commit updates it to a working reference, namely gmane. Signed-off-by: Pranith Kumar Signed-off-by: Paul E. McKenney Reviewed-by: Josh Triplett --- Documentation/RCU/RTFP.txt | 4 ++-- 1 file changed, 2 insertions(+), 2 deletions(-) (limited to 'Documentation') diff --git a/Documentation/RCU/RTFP.txt b/Documentation/RCU/RTFP.txt index 2f0fcb2112d2..f29bcbc463e7 100644 --- a/Documentation/RCU/RTFP.txt +++ b/Documentation/RCU/RTFP.txt @@ -2451,8 +2451,8 @@ lot of {Linux} into your technology!!!" ,month="February" ,year="2010" ,note="Available: -\url{http://kerneltrap.com/mailarchive/linux-netdev/2010/2/26/6270589} -[Viewed March 20, 2011]" +\url{http://thread.gmane.org/gmane.linux.network/153338} +[Viewed June 9, 2014]" ,annotation={ Use a pair of list_head structures to support RCU-protected resizable hash tables. -- cgit v1.3-14-g43fede From 128ea442b12ba63614dccc9b54726cf753aa4758 Mon Sep 17 00:00:00 2001 From: "Paul E. McKenney" Date: Thu, 19 Jun 2014 10:01:23 -0700 Subject: documentation: Add acquire/release barriers to pairing rules It is possible to pair acquire and release barriers with other barriers, so this commit adds them to the list in the SMP barrier pairing section. Reported-by: Lai Jiangshan Signed-off-by: Paul E. McKenney Reviewed-by: Tejun Heo Reviewed-by: Josh Triplett [ paulmck: Updated pairing discussion as suggested by Peter Zijlstra. ] --- Documentation/memory-barriers.txt | 12 ++++++++---- 1 file changed, 8 insertions(+), 4 deletions(-) (limited to 'Documentation') diff --git a/Documentation/memory-barriers.txt b/Documentation/memory-barriers.txt index a6ca533a73fc..a4de88fb55f0 100644 --- a/Documentation/memory-barriers.txt +++ b/Documentation/memory-barriers.txt @@ -757,10 +757,14 @@ SMP BARRIER PAIRING When dealing with CPU-CPU interactions, certain types of memory barrier should always be paired. A lack of appropriate pairing is almost certainly an error. -A write barrier should always be paired with a data dependency barrier or read -barrier, though a general barrier would also be viable. Similarly a read -barrier or a data dependency barrier should always be paired with at least an -write barrier, though, again, a general barrier is viable: +General barriers pair with each other, though they also pair with +most other types of barriers, albeit without transitivity. An acquire +barrier pairs with a release barrier, but both may also pair with other +barriers, including of course general barriers. A write barrier pairs +with a data dependency barrier, an acquire barrier, a release barrier, +a read barrier, or a general barrier. Similarly a read barrier or a +data dependency barrier pairs with a write barrier, an acquire barrier, +a release barrier, or a general barrier: CPU 1 CPU 2 =============== =============== -- cgit v1.3-14-g43fede From 9963185c04727769913a2758c0fcccb821c77098 Mon Sep 17 00:00:00 2001 From: "Paul E. McKenney" Date: Mon, 23 Jun 2014 11:52:59 -0700 Subject: documentation: Add pointer to percpu-ref for RCU and refcount Signed-off-by: Paul E. McKenney Reviewed-by: Josh Triplett Reviewed-by: Lai Jiangshan --- Documentation/RCU/rcuref.txt | 9 +++++++++ 1 file changed, 9 insertions(+) (limited to 'Documentation') diff --git a/Documentation/RCU/rcuref.txt b/Documentation/RCU/rcuref.txt index 141d531aa14b..613033ff2b9b 100644 --- a/Documentation/RCU/rcuref.txt +++ b/Documentation/RCU/rcuref.txt @@ -1,5 +1,14 @@ Reference-count design for elements of lists/arrays protected by RCU. + +Please note that the percpu-ref feature is likely your first +stop if you need to combine reference counts and RCU. Please see +include/linux/percpu-refcount.h for more information. However, in +those unusual cases where percpu-ref would consume too much memory, +please read on. + +------------------------------------------------------------------------ + Reference counting on elements of lists which are protected by traditional reader/writer spinlocks or semaphores are straightforward: -- cgit v1.3-14-g43fede