From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S1752226AbdJDVWz (ORCPT ); Wed, 4 Oct 2017 17:22:55 -0400 Received: from mx0a-001b2d01.pphosted.com ([148.163.156.1]:51730 "EHLO mx0a-001b2d01.pphosted.com" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S1751888AbdJDVVe (ORCPT ); Wed, 4 Oct 2017 17:21:34 -0400 From: "Paul E. McKenney" To: linux-kernel@vger.kernel.org Cc: mingo@kernel.org, jiangshanlai@gmail.com, dipankar@in.ibm.com, akpm@linux-foundation.org, mathieu.desnoyers@efficios.com, josh@joshtriplett.org, tglx@linutronix.de, peterz@infradead.org, rostedt@goodmis.org, dhowells@redhat.com, edumazet@google.com, fweisbec@gmail.com, oleg@redhat.com, Alan Stern , "Paul E. McKenney" Subject: [PATCH tip/core/rcu 06/16] memory-barriers: Rework multicopy-atomicity section Date: Wed, 4 Oct 2017 14:21:16 -0700 X-Mailer: git-send-email 2.5.2 In-Reply-To: <20171004212051.GA8411@linux.vnet.ibm.com> References: <20171004212051.GA8411@linux.vnet.ibm.com> X-TM-AS-GCONF: 00 x-cbid: 17100421-0044-0000-0000-0000039A5ED3 X-IBM-SpamModules-Scores: X-IBM-SpamModules-Versions: BY=3.00007843; HX=3.00000241; KW=3.00000007; PH=3.00000004; SC=3.00000233; SDB=6.00926530; UDB=6.00466099; IPR=6.00706743; BA=6.00005620; NDR=6.00000001; ZLA=6.00000005; ZF=6.00000009; ZB=6.00000000; ZP=6.00000000; ZH=6.00000000; ZU=6.00000002; MB=3.00017394; XFM=3.00000015; UTC=2017-10-04 21:21:32 X-IBM-AV-DETECTION: SAVI=unused REMOTE=unused XFE=unused x-cbparentid: 17100421-0045-0000-0000-000007C96DE2 Message-Id: <1507152086-9791-6-git-send-email-paulmck@linux.vnet.ibm.com> X-Proofpoint-Virus-Version: vendor=fsecure engine=2.50.10432:,, definitions=2017-10-04_09:,, signatures=0 X-Proofpoint-Spam-Details: rule=outbound_notspam policy=outbound score=0 spamscore=0 suspectscore=1 malwarescore=0 phishscore=0 adultscore=0 bulkscore=0 classifier=spam adjust=0 reason=mlx scancount=1 engine=8.0.1-1707230000 definitions=main-1710040296 Sender: linux-kernel-owner@vger.kernel.org List-ID: X-Mailing-List: linux-kernel@vger.kernel.org From: Alan Stern Signed-off-by: Alan Stern Signed-off-by: Paul E. McKenney --- Documentation/memory-barriers.txt | 58 ++++++++++++++++++++------------------- 1 file changed, 30 insertions(+), 28 deletions(-) diff --git a/Documentation/memory-barriers.txt b/Documentation/memory-barriers.txt index b6882680247e..7deee1441640 100644 --- a/Documentation/memory-barriers.txt +++ b/Documentation/memory-barriers.txt @@ -1343,13 +1343,13 @@ MULTICOPY ATOMICITY Multicopy atomicity is a deeply intuitive notion about ordering that is not always provided by real computer systems, namely that a given store -is visible at the same time to all CPUs, or, alternatively, that all -CPUs agree on the order in which all stores took place. However, use of -full multicopy atomicity would rule out valuable hardware optimizations, -so a weaker form called ``other multicopy atomicity'' instead guarantees -that a given store is observed at the same time by all -other- CPUs. The -remainder of this document discusses this weaker form, but for brevity -will call it simply ``multicopy atomicity''. +becomes visible at the same time to all CPUs, or, alternatively, that all +CPUs agree on the order in which all stores become visible. However, +support of full multicopy atomicity would rule out valuable hardware +optimizations, so a weaker form called ``other multicopy atomicity'' +instead guarantees only that a given store becomes visible at the same +time to all -other- CPUs. The remainder of this document discusses this +weaker form, but for brevity will call it simply ``multicopy atomicity''. The following example demonstrates multicopy atomicity: @@ -1360,24 +1360,26 @@ The following example demonstrates multicopy atomicity: STORE Y=r1 LOAD X -Suppose that CPU 2's load from X returns 1 which it then stores to Y and -that CPU 3's load from Y returns 1. This indicates that CPU 2's load -from X in some sense follows CPU 1's store to X and that CPU 2's store -to Y in some sense preceded CPU 3's load from Y. The question is then -"Can CPU 3's load from X return 0?" +Suppose that CPU 2's load from X returns 1, which it then stores to Y, +and CPU 3's load from Y returns 1. This indicates that CPU 1's store +to X precedes CPU 2's load from X and that CPU 2's store to Y precedes +CPU 3's load from Y. In addition, the memory barriers guarantee that +CPU 2 executes its load before its store, and CPU 3 loads from Y before +it loads from X. The question is then "Can CPU 3's load from X return 0?" -Because CPU 3's load from X in some sense came after CPU 2's load, it +Because CPU 3's load from X in some sense comes after CPU 2's load, it is natural to expect that CPU 3's load from X must therefore return 1. -This expectation is an example of multicopy atomicity: if a load executing -on CPU A follows a load from the same variable executing on CPU B, then -an understandable but incorrect expectation is that CPU A's load must -either return the same value that CPU B's load did, or must return some -later value. - -In the Linux kernel, the above use of a general memory barrier compensates -for any lack of multicopy atomicity. Therefore, in the above example, -if CPU 2's load from X returns 1 and its load from Y returns 0, and CPU 3's -load from Y returns 1, then CPU 3's load from X must also return 1. +This expectation follows from multicopy atomicity: if a load executing +on CPU B follows a load from the same variable executing on CPU A (and +CPU A did not originally store the value which it read), then on +multicopy-atomic systems, CPU B's load must return either the same value +that CPU A's load did or some later value. However, the Linux kernel +does not require systems to be multicopy atomic. + +The use of a general memory barrier in the example above compensates +for any lack of multicopy atomicity. In the example, if CPU 2's load +from X returns 1 and CPU 3's load from Y returns 1, then CPU 3's load +from X must indeed also return 1. However, dependencies, read barriers, and write barriers are not always able to compensate for non-multicopy atomicity. For example, suppose @@ -1396,11 +1398,11 @@ this example, it is perfectly legal for CPU 2's load from X to return 1, CPU 3's load from Y to return 1, and its load from X to return 0. The key point is that although CPU 2's data dependency orders its load -and store, it does not guarantee to order CPU 1's store. Therefore, -if this example runs on a non-multicopy-atomic system where CPUs 1 and 2 -share a store buffer or a level of cache, CPU 2 might have early access -to CPU 1's writes. A general barrier is therefore required to ensure -that all CPUs agree on the combined order of CPU 1's and CPU 2's accesses. +and store, it does not guarantee to order CPU 1's store. Thus, if this +example runs on a non-multicopy-atomic system where CPUs 1 and 2 share a +store buffer or a level of cache, CPU 2 might have early access to CPU 1's +writes. General barriers are therefore required to ensure that all CPUs +agree on the combined order of multiple accesses. General barriers can compensate not only for non-multicopy atomicity, but can also generate additional ordering that can ensure that -all- -- 2.5.2