cachepc-linux

Fork of AMDESE/linux with modifications for CachePC side-channel attack
git clone https://git.sinitax.com/sinitax/cachepc-linux
Log | Files | Refs | README | LICENSE | sfeed.txt

access-marking.txt (20927B)


      1MARKING SHARED-MEMORY ACCESSES
      2==============================
      3
      4This document provides guidelines for marking intentionally concurrent
      5normal accesses to shared memory, that is "normal" as in accesses that do
      6not use read-modify-write atomic operations.  It also describes how to
      7document these accesses, both with comments and with special assertions
      8processed by the Kernel Concurrency Sanitizer (KCSAN).  This discussion
      9builds on an earlier LWN article [1].
     10
     11
     12ACCESS-MARKING OPTIONS
     13======================
     14
     15The Linux kernel provides the following access-marking options:
     16
     171.	Plain C-language accesses (unmarked), for example, "a = b;"
     18
     192.	Data-race marking, for example, "data_race(a = b);"
     20
     213.	READ_ONCE(), for example, "a = READ_ONCE(b);"
     22	The various forms of atomic_read() also fit in here.
     23
     244.	WRITE_ONCE(), for example, "WRITE_ONCE(a, b);"
     25	The various forms of atomic_set() also fit in here.
     26
     27
     28These may be used in combination, as shown in this admittedly improbable
     29example:
     30
     31	WRITE_ONCE(a, b + data_race(c + d) + READ_ONCE(e));
     32
     33Neither plain C-language accesses nor data_race() (#1 and #2 above) place
     34any sort of constraint on the compiler's choice of optimizations [2].
     35In contrast, READ_ONCE() and WRITE_ONCE() (#3 and #4 above) restrict the
     36compiler's use of code-motion and common-subexpression optimizations.
     37Therefore, if a given access is involved in an intentional data race,
     38using READ_ONCE() for loads and WRITE_ONCE() for stores is usually
     39preferable to data_race(), which in turn is usually preferable to plain
     40C-language accesses.  It is permissible to combine #2 and #3, for example,
     41data_race(READ_ONCE(a)), which will both restrict compiler optimizations
     42and disable KCSAN diagnostics.
     43
     44KCSAN will complain about many types of data races involving plain
     45C-language accesses, but marking all accesses involved in a given data
     46race with one of data_race(), READ_ONCE(), or WRITE_ONCE(), will prevent
     47KCSAN from complaining.  Of course, lack of KCSAN complaints does not
     48imply correct code.  Therefore, please take a thoughtful approach
     49when responding to KCSAN complaints.  Churning the code base with
     50ill-considered additions of data_race(), READ_ONCE(), and WRITE_ONCE()
     51is unhelpful.
     52
     53In fact, the following sections describe situations where use of
     54data_race() and even plain C-language accesses is preferable to
     55READ_ONCE() and WRITE_ONCE().
     56
     57
     58Use of the data_race() Macro
     59----------------------------
     60
     61Here are some situations where data_race() should be used instead of
     62READ_ONCE() and WRITE_ONCE():
     63
     641.	Data-racy loads from shared variables whose values are used only
     65	for diagnostic purposes.
     66
     672.	Data-racy reads whose values are checked against marked reload.
     68
     693.	Reads whose values feed into error-tolerant heuristics.
     70
     714.	Writes setting values that feed into error-tolerant heuristics.
     72
     73
     74Data-Racy Reads for Approximate Diagnostics
     75
     76Approximate diagnostics include lockdep reports, monitoring/statistics
     77(including /proc and /sys output), WARN*()/BUG*() checks whose return
     78values are ignored, and other situations where reads from shared variables
     79are not an integral part of the core concurrency design.
     80
     81In fact, use of data_race() instead READ_ONCE() for these diagnostic
     82reads can enable better checking of the remaining accesses implementing
     83the core concurrency design.  For example, suppose that the core design
     84prevents any non-diagnostic reads from shared variable x from running
     85concurrently with updates to x.  Then using plain C-language writes
     86to x allows KCSAN to detect reads from x from within regions of code
     87that fail to exclude the updates.  In this case, it is important to use
     88data_race() for the diagnostic reads because otherwise KCSAN would give
     89false-positive warnings about these diagnostic reads.
     90
     91If it is necessary to both restrict compiler optimizations and disable
     92KCSAN diagnostics, use both data_race() and READ_ONCE(), for example,
     93data_race(READ_ONCE(a)).
     94
     95In theory, plain C-language loads can also be used for this use case.
     96However, in practice this will have the disadvantage of causing KCSAN
     97to generate false positives because KCSAN will have no way of knowing
     98that the resulting data race was intentional.
     99
    100
    101Data-Racy Reads That Are Checked Against Marked Reload
    102
    103The values from some reads are not implicitly trusted.  They are instead
    104fed into some operation that checks the full value against a later marked
    105load from memory, which means that the occasional arbitrarily bogus value
    106is not a problem.  For example, if a bogus value is fed into cmpxchg(),
    107all that happens is that this cmpxchg() fails, which normally results
    108in a retry.  Unless the race condition that resulted in the bogus value
    109recurs, this retry will with high probability succeed, so no harm done.
    110
    111However, please keep in mind that a data_race() load feeding into
    112a cmpxchg_relaxed() might still be subject to load fusing on some
    113architectures.  Therefore, it is best to capture the return value from
    114the failing cmpxchg() for the next iteration of the loop, an approach
    115that provides the compiler much less scope for mischievous optimizations.
    116Capturing the return value from cmpxchg() also saves a memory reference
    117in many cases.
    118
    119In theory, plain C-language loads can also be used for this use case.
    120However, in practice this will have the disadvantage of causing KCSAN
    121to generate false positives because KCSAN will have no way of knowing
    122that the resulting data race was intentional.
    123
    124
    125Reads Feeding Into Error-Tolerant Heuristics
    126
    127Values from some reads feed into heuristics that can tolerate occasional
    128errors.  Such reads can use data_race(), thus allowing KCSAN to focus on
    129the other accesses to the relevant shared variables.  But please note
    130that data_race() loads are subject to load fusing, which can result in
    131consistent errors, which in turn are quite capable of breaking heuristics.
    132Therefore use of data_race() should be limited to cases where some other
    133code (such as a barrier() call) will force the occasional reload.
    134
    135Note that this use case requires that the heuristic be able to handle
    136any possible error.  In contrast, if the heuristics might be fatally
    137confused by one or more of the possible erroneous values, use READ_ONCE()
    138instead of data_race().
    139
    140In theory, plain C-language loads can also be used for this use case.
    141However, in practice this will have the disadvantage of causing KCSAN
    142to generate false positives because KCSAN will have no way of knowing
    143that the resulting data race was intentional.
    144
    145
    146Writes Setting Values Feeding Into Error-Tolerant Heuristics
    147
    148The values read into error-tolerant heuristics come from somewhere,
    149for example, from sysfs.  This means that some code in sysfs writes
    150to this same variable, and these writes can also use data_race().
    151After all, if the heuristic can tolerate the occasional bogus value
    152due to compiler-mangled reads, it can also tolerate the occasional
    153compiler-mangled write, at least assuming that the proper value is in
    154place once the write completes.
    155
    156Plain C-language stores can also be used for this use case.  However,
    157in kernels built with CONFIG_KCSAN_ASSUME_PLAIN_WRITES_ATOMIC=n, this
    158will have the disadvantage of causing KCSAN to generate false positives
    159because KCSAN will have no way of knowing that the resulting data race
    160was intentional.
    161
    162
    163Use of Plain C-Language Accesses
    164--------------------------------
    165
    166Here are some example situations where plain C-language accesses should
    167used instead of READ_ONCE(), WRITE_ONCE(), and data_race():
    168
    1691.	Accesses protected by mutual exclusion, including strict locking
    170	and sequence locking.
    171
    1722.	Initialization-time and cleanup-time accesses.	This covers a
    173	wide variety of situations, including the uniprocessor phase of
    174	system boot, variables to be used by not-yet-spawned kthreads,
    175	structures not yet published to reference-counted or RCU-protected
    176	data structures, and the cleanup side of any of these situations.
    177
    1783.	Per-CPU variables that are not accessed from other CPUs.
    179
    1804.	Private per-task variables, including on-stack variables, some
    181	fields in the task_struct structure, and task-private heap data.
    182
    1835.	Any other loads for which there is not supposed to be a concurrent
    184	store to that same variable.
    185
    1866.	Any other stores for which there should be neither concurrent
    187	loads nor concurrent stores to that same variable.
    188
    189	But note that KCSAN makes two explicit exceptions to this rule
    190	by default, refraining from flagging plain C-language stores:
    191
    192	a.	No matter what.  You can override this default by building
    193		with CONFIG_KCSAN_ASSUME_PLAIN_WRITES_ATOMIC=n.
    194
    195	b.	When the store writes the value already contained in
    196		that variable.	You can override this default by building
    197		with CONFIG_KCSAN_REPORT_VALUE_CHANGE_ONLY=n.
    198
    199	c.	When one of the stores is in an interrupt handler and
    200		the other in the interrupted code.  You can override this
    201		default by building with CONFIG_KCSAN_INTERRUPT_WATCHER=y.
    202
    203Note that it is important to use plain C-language accesses in these cases,
    204because doing otherwise prevents KCSAN from detecting violations of your
    205code's synchronization rules.
    206
    207
    208ACCESS-DOCUMENTATION OPTIONS
    209============================
    210
    211It is important to comment marked accesses so that people reading your
    212code, yourself included, are reminded of the synchronization design.
    213However, it is even more important to comment plain C-language accesses
    214that are intentionally involved in data races.  Such comments are
    215needed to remind people reading your code, again, yourself included,
    216of how the compiler has been prevented from optimizing those accesses
    217into concurrency bugs.
    218
    219It is also possible to tell KCSAN about your synchronization design.
    220For example, ASSERT_EXCLUSIVE_ACCESS(foo) tells KCSAN that any
    221concurrent access to variable foo by any other CPU is an error, even
    222if that concurrent access is marked with READ_ONCE().  In addition,
    223ASSERT_EXCLUSIVE_WRITER(foo) tells KCSAN that although it is OK for there
    224to be concurrent reads from foo from other CPUs, it is an error for some
    225other CPU to be concurrently writing to foo, even if that concurrent
    226write is marked with data_race() or WRITE_ONCE().
    227
    228Note that although KCSAN will call out data races involving either
    229ASSERT_EXCLUSIVE_ACCESS() or ASSERT_EXCLUSIVE_WRITER() on the one hand
    230and data_race() writes on the other, KCSAN will not report the location
    231of these data_race() writes.
    232
    233
    234EXAMPLES
    235========
    236
    237As noted earlier, the goal is to prevent the compiler from destroying
    238your concurrent algorithm, to help the human reader, and to inform
    239KCSAN of aspects of your concurrency design.  This section looks at a
    240few examples showing how this can be done.
    241
    242
    243Lock Protection With Lockless Diagnostic Access
    244-----------------------------------------------
    245
    246For example, suppose a shared variable "foo" is read only while a
    247reader-writer spinlock is read-held, written only while that same
    248spinlock is write-held, except that it is also read locklessly for
    249diagnostic purposes.  The code might look as follows:
    250
    251	int foo;
    252	DEFINE_RWLOCK(foo_rwlock);
    253
    254	void update_foo(int newval)
    255	{
    256		write_lock(&foo_rwlock);
    257		foo = newval;
    258		do_something(newval);
    259		write_unlock(&foo_rwlock);
    260	}
    261
    262	int read_foo(void)
    263	{
    264		int ret;
    265
    266		read_lock(&foo_rwlock);
    267		do_something_else();
    268		ret = foo;
    269		read_unlock(&foo_rwlock);
    270		return ret;
    271	}
    272
    273	void read_foo_diagnostic(void)
    274	{
    275		pr_info("Current value of foo: %d\n", data_race(foo));
    276	}
    277
    278The reader-writer lock prevents the compiler from introducing concurrency
    279bugs into any part of the main algorithm using foo, which means that
    280the accesses to foo within both update_foo() and read_foo() can (and
    281should) be plain C-language accesses.  One benefit of making them be
    282plain C-language accesses is that KCSAN can detect any erroneous lockless
    283reads from or updates to foo.  The data_race() in read_foo_diagnostic()
    284tells KCSAN that data races are expected, and should be silently
    285ignored.  This data_race() also tells the human reading the code that
    286read_foo_diagnostic() might sometimes return a bogus value.
    287
    288If it is necessary to suppress compiler optimization and also detect
    289buggy lockless writes, read_foo_diagnostic() can be updated as follows:
    290
    291	void read_foo_diagnostic(void)
    292	{
    293		pr_info("Current value of foo: %d\n", data_race(READ_ONCE(foo)));
    294	}
    295
    296Alternatively, given that KCSAN is to ignore all accesses in this function,
    297this function can be marked __no_kcsan and the data_race() can be dropped:
    298
    299	void __no_kcsan read_foo_diagnostic(void)
    300	{
    301		pr_info("Current value of foo: %d\n", READ_ONCE(foo));
    302	}
    303
    304However, in order for KCSAN to detect buggy lockless writes, your kernel
    305must be built with CONFIG_KCSAN_ASSUME_PLAIN_WRITES_ATOMIC=n.  If you
    306need KCSAN to detect such a write even if that write did not change
    307the value of foo, you also need CONFIG_KCSAN_REPORT_VALUE_CHANGE_ONLY=n.
    308If you need KCSAN to detect such a write happening in an interrupt handler
    309running on the same CPU doing the legitimate lock-protected write, you
    310also need CONFIG_KCSAN_INTERRUPT_WATCHER=y.  With some or all of these
    311Kconfig options set properly, KCSAN can be quite helpful, although
    312it is not necessarily a full replacement for hardware watchpoints.
    313On the other hand, neither are hardware watchpoints a full replacement
    314for KCSAN because it is not always easy to tell hardware watchpoint to
    315conditionally trap on accesses.
    316
    317
    318Lock-Protected Writes With Lockless Reads
    319-----------------------------------------
    320
    321For another example, suppose a shared variable "foo" is updated only
    322while holding a spinlock, but is read locklessly.  The code might look
    323as follows:
    324
    325	int foo;
    326	DEFINE_SPINLOCK(foo_lock);
    327
    328	void update_foo(int newval)
    329	{
    330		spin_lock(&foo_lock);
    331		WRITE_ONCE(foo, newval);
    332		ASSERT_EXCLUSIVE_WRITER(foo);
    333		do_something(newval);
    334		spin_unlock(&foo_wlock);
    335	}
    336
    337	int read_foo(void)
    338	{
    339		do_something_else();
    340		return READ_ONCE(foo);
    341	}
    342
    343Because foo is read locklessly, all accesses are marked.  The purpose
    344of the ASSERT_EXCLUSIVE_WRITER() is to allow KCSAN to check for a buggy
    345concurrent lockless write.
    346
    347
    348Lock-Protected Writes With Heuristic Lockless Reads
    349---------------------------------------------------
    350
    351For another example, suppose that the code can normally make use of
    352a per-data-structure lock, but there are times when a global lock
    353is required.  These times are indicated via a global flag.  The code
    354might look as follows, and is based loosely on nf_conntrack_lock(),
    355nf_conntrack_all_lock(), and nf_conntrack_all_unlock():
    356
    357	bool global_flag;
    358	DEFINE_SPINLOCK(global_lock);
    359	struct foo {
    360		spinlock_t f_lock;
    361		int f_data;
    362	};
    363
    364	/* All foo structures are in the following array. */
    365	int nfoo;
    366	struct foo *foo_array;
    367
    368	void do_something_locked(struct foo *fp)
    369	{
    370		/* This works even if data_race() returns nonsense. */
    371		if (!data_race(global_flag)) {
    372			spin_lock(&fp->f_lock);
    373			if (!smp_load_acquire(&global_flag)) {
    374				do_something(fp);
    375				spin_unlock(&fp->f_lock);
    376				return;
    377			}
    378			spin_unlock(&fp->f_lock);
    379		}
    380		spin_lock(&global_lock);
    381		/* global_lock held, thus global flag cannot be set. */
    382		spin_lock(&fp->f_lock);
    383		spin_unlock(&global_lock);
    384		/*
    385		 * global_flag might be set here, but begin_global()
    386		 * will wait for ->f_lock to be released.
    387		 */
    388		do_something(fp);
    389		spin_unlock(&fp->f_lock);
    390	}
    391
    392	void begin_global(void)
    393	{
    394		int i;
    395
    396		spin_lock(&global_lock);
    397		WRITE_ONCE(global_flag, true);
    398		for (i = 0; i < nfoo; i++) {
    399			/*
    400			 * Wait for pre-existing local locks.  One at
    401			 * a time to avoid lockdep limitations.
    402			 */
    403			spin_lock(&fp->f_lock);
    404			spin_unlock(&fp->f_lock);
    405		}
    406	}
    407
    408	void end_global(void)
    409	{
    410		smp_store_release(&global_flag, false);
    411		spin_unlock(&global_lock);
    412	}
    413
    414All code paths leading from the do_something_locked() function's first
    415read from global_flag acquire a lock, so endless load fusing cannot
    416happen.
    417
    418If the value read from global_flag is true, then global_flag is
    419rechecked while holding ->f_lock, which, if global_flag is now false,
    420prevents begin_global() from completing.  It is therefore safe to invoke
    421do_something().
    422
    423Otherwise, if either value read from global_flag is true, then after
    424global_lock is acquired global_flag must be false.  The acquisition of
    425->f_lock will prevent any call to begin_global() from returning, which
    426means that it is safe to release global_lock and invoke do_something().
    427
    428For this to work, only those foo structures in foo_array[] may be passed
    429to do_something_locked().  The reason for this is that the synchronization
    430with begin_global() relies on momentarily holding the lock of each and
    431every foo structure.
    432
    433The smp_load_acquire() and smp_store_release() are required because
    434changes to a foo structure between calls to begin_global() and
    435end_global() are carried out without holding that structure's ->f_lock.
    436The smp_load_acquire() and smp_store_release() ensure that the next
    437invocation of do_something() from do_something_locked() will see those
    438changes.
    439
    440
    441Lockless Reads and Writes
    442-------------------------
    443
    444For another example, suppose a shared variable "foo" is both read and
    445updated locklessly.  The code might look as follows:
    446
    447	int foo;
    448
    449	int update_foo(int newval)
    450	{
    451		int ret;
    452
    453		ret = xchg(&foo, newval);
    454		do_something(newval);
    455		return ret;
    456	}
    457
    458	int read_foo(void)
    459	{
    460		do_something_else();
    461		return READ_ONCE(foo);
    462	}
    463
    464Because foo is accessed locklessly, all accesses are marked.  It does
    465not make sense to use ASSERT_EXCLUSIVE_WRITER() in this case because
    466there really can be concurrent lockless writers.  KCSAN would
    467flag any concurrent plain C-language reads from foo, and given
    468CONFIG_KCSAN_ASSUME_PLAIN_WRITES_ATOMIC=n, also any concurrent plain
    469C-language writes to foo.
    470
    471
    472Lockless Reads and Writes, But With Single-Threaded Initialization
    473------------------------------------------------------------------
    474
    475For yet another example, suppose that foo is initialized in a
    476single-threaded manner, but that a number of kthreads are then created
    477that locklessly and concurrently access foo.  Some snippets of this code
    478might look as follows:
    479
    480	int foo;
    481
    482	void initialize_foo(int initval, int nkthreads)
    483	{
    484		int i;
    485
    486		foo = initval;
    487		ASSERT_EXCLUSIVE_ACCESS(foo);
    488		for (i = 0; i < nkthreads; i++)
    489			kthread_run(access_foo_concurrently, ...);
    490	}
    491
    492	/* Called from access_foo_concurrently(). */
    493	int update_foo(int newval)
    494	{
    495		int ret;
    496
    497		ret = xchg(&foo, newval);
    498		do_something(newval);
    499		return ret;
    500	}
    501
    502	/* Also called from access_foo_concurrently(). */
    503	int read_foo(void)
    504	{
    505		do_something_else();
    506		return READ_ONCE(foo);
    507	}
    508
    509The initialize_foo() uses a plain C-language write to foo because there
    510are not supposed to be concurrent accesses during initialization.  The
    511ASSERT_EXCLUSIVE_ACCESS() allows KCSAN to flag buggy concurrent unmarked
    512reads, and the ASSERT_EXCLUSIVE_ACCESS() call further allows KCSAN to
    513flag buggy concurrent writes, even if:  (1) Those writes are marked or
    514(2) The kernel was built with CONFIG_KCSAN_ASSUME_PLAIN_WRITES_ATOMIC=y.
    515
    516
    517Checking Stress-Test Race Coverage
    518----------------------------------
    519
    520When designing stress tests it is important to ensure that race conditions
    521of interest really do occur.  For example, consider the following code
    522fragment:
    523
    524	int foo;
    525
    526	int update_foo(int newval)
    527	{
    528		return xchg(&foo, newval);
    529	}
    530
    531	int xor_shift_foo(int shift, int mask)
    532	{
    533		int old, new, newold;
    534
    535		newold = data_race(foo); /* Checked by cmpxchg(). */
    536		do {
    537			old = newold;
    538			new = (old << shift) ^ mask;
    539			newold = cmpxchg(&foo, old, new);
    540		} while (newold != old);
    541		return old;
    542	}
    543
    544	int read_foo(void)
    545	{
    546		return READ_ONCE(foo);
    547	}
    548
    549If it is possible for update_foo(), xor_shift_foo(), and read_foo() to be
    550invoked concurrently, the stress test should force this concurrency to
    551actually happen.  KCSAN can evaluate the stress test when the above code
    552is modified to read as follows:
    553
    554	int foo;
    555
    556	int update_foo(int newval)
    557	{
    558		ASSERT_EXCLUSIVE_ACCESS(foo);
    559		return xchg(&foo, newval);
    560	}
    561
    562	int xor_shift_foo(int shift, int mask)
    563	{
    564		int old, new, newold;
    565
    566		newold = data_race(foo); /* Checked by cmpxchg(). */
    567		do {
    568			old = newold;
    569			new = (old << shift) ^ mask;
    570			ASSERT_EXCLUSIVE_ACCESS(foo);
    571			newold = cmpxchg(&foo, old, new);
    572		} while (newold != old);
    573		return old;
    574	}
    575
    576
    577	int read_foo(void)
    578	{
    579		ASSERT_EXCLUSIVE_ACCESS(foo);
    580		return READ_ONCE(foo);
    581	}
    582
    583If a given stress-test run does not result in KCSAN complaints from
    584each possible pair of ASSERT_EXCLUSIVE_ACCESS() invocations, the
    585stress test needs improvement.  If the stress test was to be evaluated
    586on a regular basis, it would be wise to place the above instances of
    587ASSERT_EXCLUSIVE_ACCESS() under #ifdef so that they did not result in
    588false positives when not evaluating the stress test.
    589
    590
    591REFERENCES
    592==========
    593
    594[1] "Concurrency bugs should fear the big bad data-race detector (part 2)"
    595    https://lwn.net/Articles/816854/
    596
    597[2] "Who's afraid of a big bad optimizing compiler?"
    598    https://lwn.net/Articles/793253/