From: Marco Elver <elver@google.com>
To: elver@google.com, "Paul E . McKenney" <paulmck@kernel.org>
Cc: Alexander Potapenko <glider@google.com>,
Boqun Feng <boqun.feng@gmail.com>, Borislav Petkov <bp@alien8.de>,
Dmitry Vyukov <dvyukov@google.com>,
Ingo Molnar <mingo@kernel.org>,
Josh Poimboeuf <jpoimboe@redhat.com>,
Mark Rutland <mark.rutland@arm.com>,
Peter Zijlstra <peterz@infradead.org>,
Thomas Gleixner <tglx@linutronix.de>,
Waiman Long <longman@redhat.com>, Will Deacon <will@kernel.org>,
kasan-dev@googlegroups.com, linux-arch@vger.kernel.org,
linux-doc@vger.kernel.org, linux-kbuild@vger.kernel.org,
linux-kernel@vger.kernel.org, linux-mm@kvack.org, x86@kernel.org
Subject: [PATCH -rcu/kcsan 09/23] kcsan: Document modeling of weak memory
Date: Tue, 5 Oct 2021 12:58:51 +0200 [thread overview]
Message-ID: <20211005105905.1994700-10-elver@google.com> (raw)
In-Reply-To: <20211005105905.1994700-1-elver@google.com>
Document how KCSAN models a subset of weak memory and the subset of
missing memory barriers it can detect as a result.
Signed-off-by: Marco Elver <elver@google.com>
---
Documentation/dev-tools/kcsan.rst | 72 +++++++++++++++++++++++++------
1 file changed, 59 insertions(+), 13 deletions(-)
diff --git a/Documentation/dev-tools/kcsan.rst b/Documentation/dev-tools/kcsan.rst
index 7db43c7c09b8..4fc3773fead9 100644
--- a/Documentation/dev-tools/kcsan.rst
+++ b/Documentation/dev-tools/kcsan.rst
@@ -204,17 +204,17 @@ Ultimately this allows to determine the possible executions of concurrent code,
and if that code is free from data races.
KCSAN is aware of *marked atomic operations* (``READ_ONCE``, ``WRITE_ONCE``,
-``atomic_*``, etc.), but is oblivious of any ordering guarantees and simply
-assumes that memory barriers are placed correctly. In other words, KCSAN
-assumes that as long as a plain access is not observed to race with another
-conflicting access, memory operations are correctly ordered.
-
-This means that KCSAN will not report *potential* data races due to missing
-memory ordering. Developers should therefore carefully consider the required
-memory ordering requirements that remain unchecked. If, however, missing
-memory ordering (that is observable with a particular compiler and
-architecture) leads to an observable data race (e.g. entering a critical
-section erroneously), KCSAN would report the resulting data race.
+``atomic_*``, etc.), and a subset of ordering guarantees implied by memory
+barriers. With ``CONFIG_KCSAN_WEAK_MEMORY=y``, KCSAN models load or store
+buffering, and can detect missing ``smp_mb()``, ``smp_wmb()``, ``smp_rmb()``,
+``smp_store_release()``, and all ``atomic_*`` operations with equivalent
+implied barriers.
+
+Note, KCSAN will not report all data races due to missing memory ordering,
+specifically where a memory barrier would be required to prohibit subsequent
+memory operation from reordering before the barrier. Developers should
+therefore carefully consider the required memory ordering requirements that
+remain unchecked.
Race Detection Beyond Data Races
--------------------------------
@@ -268,6 +268,52 @@ marked operations, if all accesses to a variable that is accessed concurrently
are properly marked, KCSAN will never trigger a watchpoint and therefore never
report the accesses.
+Modeling Weak Memory
+~~~~~~~~~~~~~~~~~~~~
+
+KCSAN's approach to detecting data races due to missing memory barriers is
+based on modeling access reordering (with ``CONFIG_KCSAN_WEAK_MEMORY=y``).
+Each plain memory access for which a watchpoint is set up, is also selected for
+simulated reordering within the scope of its function (at most 1 in-flight
+access).
+
+Once an access has been selected for reordering, it is checked along every
+other access until the end of the function scope. If an appropriate memory
+barrier is encountered, the access will no longer be considered for simulated
+reordering.
+
+When the result of a memory operation should be ordered by a barrier, KCSAN can
+then detect data races where the conflict only occurs as a result of a missing
+barrier. Consider the example::
+
+ int x, flag;
+ void T1(void)
+ {
+ x = 1; // data race!
+ WRITE_ONCE(flag, 1); // correct: smp_store_release(&flag, 1)
+ }
+ void T2(void)
+ {
+ while (!READ_ONCE(flag)); // correct: smp_load_acquire(&flag)
+ ... = x; // data race!
+ }
+
+When weak memory modeling is enabled, KCSAN can consider ``x`` in ``T1`` for
+simulated reordering. After the write of ``flag``, ``x`` is again checked for
+concurrent accesses: because ``T2`` is able to proceed after the write of
+``flag``, a data race is detected. With the correct barriers in place, ``x``
+would not be considered for reordering after the proper release of ``flag``,
+and no data race would be detected.
+
+Deliberate trade-offs in complexity but also practical limitations mean only a
+subset of data races due to missing memory barriers can be detected. Recall
+that watchpoints are only set up for plain accesses, and the only access type
+for which KCSAN simulates reordering. This means reordering of marked accesses
+is not modeled. Furthermore, with the currently available compiler support, the
+implementation is limited to modeling the effects of "buffering" (delaying
+accesses), since the runtime cannot "prefetch" accesses. One implication of
+this is that acquire operations do not require barrier instrumentation.
+
Key Properties
~~~~~~~~~~~~~~
@@ -290,8 +336,8 @@ Key Properties
4. **Detects Racy Writes from Devices:** Due to checking data values upon
setting up watchpoints, racy writes from devices can also be detected.
-5. **Memory Ordering:** KCSAN is *not* explicitly aware of the LKMM's ordering
- rules; this may result in missed data races (false negatives).
+5. **Memory Ordering:** KCSAN is aware of only a subset of LKMM ordering rules;
+ this may result in missed data races (false negatives).
6. **Analysis Accuracy:** For observed executions, due to using a sampling
strategy, the analysis is *unsound* (false negatives possible), but aims to
--
2.33.0.800.g4c38ced690-goog
next prev parent reply other threads:[~2021-10-05 11:00 UTC|newest]
Thread overview: 36+ messages / expand[flat|nested] mbox.gz Atom feed top
2021-10-05 10:58 [PATCH -rcu/kcsan 00/23] kcsan: Support detecting a subset of missing memory barriers Marco Elver
2021-10-05 10:58 ` [PATCH -rcu/kcsan 01/23] kcsan: Refactor reading of instrumented memory Marco Elver
2021-10-05 10:58 ` [PATCH -rcu/kcsan 02/23] kcsan: Remove redundant zero-initialization of globals Marco Elver
2021-10-05 10:58 ` [PATCH -rcu/kcsan 03/23] kcsan: Avoid checking scoped accesses from nested contexts Marco Elver
2021-10-05 10:58 ` [PATCH -rcu/kcsan 04/23] kcsan: Add core support for a subset of weak memory modeling Marco Elver
2021-10-05 12:52 ` Peter Zijlstra
2021-10-05 13:13 ` Marco Elver
2021-10-05 14:20 ` Peter Zijlstra
2021-10-05 10:58 ` [PATCH -rcu/kcsan 05/23] kcsan: Add core memory barrier instrumentation functions Marco Elver
2021-10-05 11:41 ` Peter Zijlstra
2021-10-05 11:45 ` Peter Zijlstra
2021-10-05 11:50 ` Marco Elver
2021-10-05 10:58 ` [PATCH -rcu/kcsan 06/23] kcsan, kbuild: Add option for barrier instrumentation only Marco Elver
2021-10-05 10:58 ` [PATCH -rcu/kcsan 07/23] kcsan: Call scoped accesses reordered in reports Marco Elver
2021-10-05 10:58 ` [PATCH -rcu/kcsan 08/23] kcsan: Show location access was reordered to Marco Elver
2021-10-05 10:58 ` Marco Elver [this message]
2021-10-05 10:58 ` [PATCH -rcu/kcsan 10/23] kcsan: test: Match reordered or normal accesses Marco Elver
2021-10-05 10:58 ` [PATCH -rcu/kcsan 11/23] kcsan: test: Add test cases for memory barrier instrumentation Marco Elver
2021-10-05 10:58 ` [PATCH -rcu/kcsan 12/23] kcsan: Ignore GCC 11+ warnings about TSan runtime support Marco Elver
2021-10-05 10:58 ` [PATCH -rcu/kcsan 13/23] kcsan: selftest: Add test case to check memory barrier instrumentation Marco Elver
2021-10-05 10:58 ` [PATCH -rcu/kcsan 14/23] locking/barriers, kcsan: Add instrumentation for barriers Marco Elver
2021-10-05 10:58 ` [PATCH -rcu/kcsan 15/23] locking/barriers, kcsan: Support generic instrumentation Marco Elver
2021-10-05 10:58 ` [PATCH -rcu/kcsan 16/23] locking/atomics, kcsan: Add instrumentation for barriers Marco Elver
2021-10-05 12:02 ` Peter Zijlstra
2021-10-05 12:16 ` Marco Elver
2021-10-05 10:58 ` [PATCH -rcu/kcsan 17/23] asm-generic/bitops, " Marco Elver
2021-10-05 10:59 ` [PATCH -rcu/kcsan 18/23] x86/barriers, kcsan: Use generic instrumentation for non-smp barriers Marco Elver
2021-10-05 10:59 ` [PATCH -rcu/kcsan 19/23] x86/qspinlock, kcsan: Instrument barrier of pv_queued_spin_unlock() Marco Elver
2021-10-05 10:59 ` [PATCH -rcu/kcsan 20/23] mm, kcsan: Enable barrier instrumentation Marco Elver
2021-10-05 10:59 ` [PATCH -rcu/kcsan 21/23] sched, kcsan: Enable memory " Marco Elver
2021-10-05 10:59 ` [PATCH -rcu/kcsan 22/23] objtool, kcsan: Add memory barrier instrumentation to whitelist Marco Elver
2021-10-05 10:59 ` [PATCH -rcu/kcsan 23/23] objtool, kcsan: Remove memory barrier instrumentation from noinstr Marco Elver
2021-10-05 14:37 ` Peter Zijlstra
2021-10-05 15:13 ` Marco Elver
2021-11-11 10:11 ` Marco Elver
2021-11-11 11:35 ` Peter Zijlstra
Reply instructions:
You may reply publicly to this message via plain-text email
using any one of the following methods:
* Save the following mbox file, import it into your mail client,
and reply-to-all from there: mbox
Avoid top-posting and favor interleaved quoting:
https://en.wikipedia.org/wiki/Posting_style#Interleaved_style
* Reply using the --to, --cc, and --in-reply-to
switches of git-send-email(1):
git send-email \
--in-reply-to=20211005105905.1994700-10-elver@google.com \
--to=elver@google.com \
--cc=boqun.feng@gmail.com \
--cc=bp@alien8.de \
--cc=dvyukov@google.com \
--cc=glider@google.com \
--cc=jpoimboe@redhat.com \
--cc=kasan-dev@googlegroups.com \
--cc=linux-arch@vger.kernel.org \
--cc=linux-doc@vger.kernel.org \
--cc=linux-kbuild@vger.kernel.org \
--cc=linux-kernel@vger.kernel.org \
--cc=linux-mm@kvack.org \
--cc=longman@redhat.com \
--cc=mark.rutland@arm.com \
--cc=mingo@kernel.org \
--cc=paulmck@kernel.org \
--cc=peterz@infradead.org \
--cc=tglx@linutronix.de \
--cc=will@kernel.org \
--cc=x86@kernel.org \
/path/to/YOUR_REPLY
https://kernel.org/pub/software/scm/git/docs/git-send-email.html
* If your mail client supports setting the In-Reply-To header
via mailto: links, try the mailto: link
Be sure your reply has a Subject: header at the top and a blank line
before the message body.
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for NNTP newsgroup(s).