[PATCH memory-model 1/4] tools/memory-model: Make read_foo_diagnostic() more clearly diagnostic

[PATCH memory-model 1/4] tools/memory-model: Make read_foo_diagnostic() more clearly diagnostic

[Paul E. McKenney]

The current definition of read_foo_diagnostic() in the "Lock Protection
With Lockless Diagnostic Access" section returns a value, which could
be use for any purpose.  This could mislead people into incorrectly
using data_race() in cases where READ_ONCE() is required.  This commit
therefore makes read_foo_diagnostic() simply print the value read.

Reported-by: Manfred Spraul <manfred@colorfullife.com>
Signed-off-by: Paul E. McKenney <paulmck@kernel.org>
---
 tools/memory-model/Documentation/access-marking.txt | 4 ++--
 1 file changed, 2 insertions(+), 2 deletions(-)

diff --git a/tools/memory-model/Documentation/access-marking.txt b/tools/memory-model/Documentation/access-marking.txt
index 1ab189f51f55d..58bff26198767 100644
--- a/tools/memory-model/Documentation/access-marking.txt
+++ b/tools/memory-model/Documentation/access-marking.txt
@@ -259,9 +259,9 @@ diagnostic purposes.  The code might look as follows:
 		return ret;
 	}
 
-	int read_foo_diagnostic(void)
+	void read_foo_diagnostic(void)
 	{
-		return data_race(foo);
+		pr_info("Current value of foo: %d\n", data_race(foo));
 	}
 
 The reader-writer lock prevents the compiler from introducing concurrency
-- 
2.31.1.189.g2e36527f23

[PATCH memory-model 2/4] tools/memory-model: Add example for heuristic lockless reads

[Paul E. McKenney]

This commit adds example code for heuristic lockless reads, based loosely
on the sem_lock() and sem_unlock() functions.

Reported-by: Manfred Spraul <manfred@colorfullife.com>
[ paulmck: Update per Manfred Spraul and Hillf Danton feedback. ]
Signed-off-by: Paul E. McKenney <paulmck@kernel.org>
---
 .../Documentation/access-marking.txt          | 94 +++++++++++++++++++
 1 file changed, 94 insertions(+)

diff --git a/tools/memory-model/Documentation/access-marking.txt b/tools/memory-model/Documentation/access-marking.txt
index 58bff26198767..be7d507997cf8 100644
--- a/tools/memory-model/Documentation/access-marking.txt
+++ b/tools/memory-model/Documentation/access-marking.txt
@@ -319,6 +319,100 @@ of the ASSERT_EXCLUSIVE_WRITER() is to allow KCSAN to check for a buggy
 concurrent lockless write.
 
 
+Lock-Protected Writes With Heuristic Lockless Reads
+---------------------------------------------------
+
+For another example, suppose that the code can normally make use of
+a per-data-structure lock, but there are times when a global lock
+is required.  These times are indicated via a global flag.  The code
+might look as follows, and is based loosely on nf_conntrack_lock(),
+nf_conntrack_all_lock(), and nf_conntrack_all_unlock():
+
+	bool global_flag;
+	DEFINE_SPINLOCK(global_lock);
+	struct foo {
+		spinlock_t f_lock;
+		int f_data;
+	};
+
+	/* All foo structures are in the following array. */
+	int nfoo;
+	struct foo *foo_array;
+
+	void do_something_locked(struct foo *fp)
+	{
+		bool gf = true;
+
+		/* IMPORTANT: Heuristic plus spin_lock()! */
+		if (!data_race(global_flag)) {
+			spin_lock(&fp->f_lock);
+			if (!smp_load_acquire(&global_flag)) {
+				do_something(fp);
+				spin_unlock(&fp->f_lock);
+				return;
+			}
+			spin_unlock(&fp->f_lock);
+		}
+		spin_lock(&global_lock);
+		/* Lock held, thus global flag cannot change. */
+		if (!global_flag) {
+			spin_lock(&fp->f_lock);
+			spin_unlock(&global_lock);
+			gf = false;
+		}
+		do_something(fp);
+		if (fg)
+			spin_unlock(&global_lock);
+		else
+			spin_lock(&fp->f_lock);
+	}
+
+	void begin_global(void)
+	{
+		int i;
+
+		spin_lock(&global_lock);
+		WRITE_ONCE(global_flag, true);
+		for (i = 0; i < nfoo; i++) {
+			/* Wait for pre-existing local locks. */
+			spin_lock(&fp->f_lock);
+			spin_unlock(&fp->f_lock);
+		}
+	}
+
+	void end_global(void)
+	{
+		smp_store_release(&global_flag, false);
+		/* Pre-existing global lock acquisitions will recheck. */
+		spin_unlock(&global_lock);
+	}
+
+All code paths leading from the do_something_locked() function's first
+read from global_flag acquire a lock, so endless load fusing cannot
+happen.
+
+If the value read from global_flag is true, then global_flag is rechecked
+while holding global_lock, which prevents global_flag from changing.
+If this recheck finds that global_flag is now false, the acquisition
+of ->f_lock prior to the release of global_lock will result in any subsequent
+begin_global() invocation waiting to acquire ->f_lock.
+
+On the other hand, if the value read from global_flag is false, then
+global_flag, then rechecking under ->f_lock combined with synchronization
+with begin_global() guarantees than any erroneous read will cause the
+do_something_locked() function's first do_something() invocation to happen
+before begin_global() returns.  The combination of the smp_load_acquire()
+in do_something_locked() and the smp_store_release() in end_global()
+guarantees that either the do_something_locked() function's first
+do_something() invocation happens after the call to end_global() or that
+do_something_locked() acquires global_lock() and rechecks under the lock.
+
+For this to work, only those foo structures in foo_array[] may be
+passed to do_something_locked().  The reason for this is that the
+synchronization with begin_global() relies on momentarily locking each
+and every foo structure.
+
+
 Lockless Reads and Writes
 -------------------------
 
-- 
2.31.1.189.g2e36527f23

[PATCH memory-model 3/4] tools/memory-model: Heuristics using data_race() must handle all values

[Paul E. McKenney]

From: Manfred Spraul <manfred@colorfullife.com>

Data loaded for use by some sorts of heuristics can tolerate the
occasional erroneous value.  In this case the loads may use data_race()
to give the compiler full freedom to optimize while also informing KCSAN
of the intent.  However, for this to work, the heuristic needs to be
able to tolerate any erroneous value that could possibly arise.  This
commit therefore adds a paragraph spelling this out.

Signed-off-by: Manfred Spraul <manfred@colorfullife.com>
Signed-off-by: Paul E. McKenney <paulmck@kernel.org>
---
 tools/memory-model/Documentation/access-marking.txt | 5 +++++
 1 file changed, 5 insertions(+)

diff --git a/tools/memory-model/Documentation/access-marking.txt b/tools/memory-model/Documentation/access-marking.txt
index be7d507997cf8..fe4ad6d12d24c 100644
--- a/tools/memory-model/Documentation/access-marking.txt
+++ b/tools/memory-model/Documentation/access-marking.txt
@@ -126,6 +126,11 @@ consistent errors, which in turn are quite capable of breaking heuristics.
 Therefore use of data_race() should be limited to cases where some other
 code (such as a barrier() call) will force the occasional reload.
 
+Note that this use case requires that the heuristic be able to handle
+any possible error.  In contrast, if the heuristics might be fatally
+confused by one or more of the possible erroneous values, use READ_ONCE()
+instead of data_race().
+
 In theory, plain C-language loads can also be used for this use case.
 However, in practice this will have the disadvantage of causing KCSAN
 to generate false positives because KCSAN will have no way of knowing
-- 
2.31.1.189.g2e36527f23

[PATCH memory-model 4/4] tools/memory-model: Document data_race(READ_ONCE())

[Paul E. McKenney]

It is possible to cause KCSAN to ignore marked accesses by applying
__no_kcsan to the function or applying data_race() to the marked accesses.
These approaches allow the developer to restrict compiler optimizations
while also causing KCSAN to ignore diagnostic accesses.

This commit therefore updates the documentation accordingly.

Signed-off-by: Paul E. McKenney <paulmck@kernel.org>
---
 .../Documentation/access-marking.txt          | 49 +++++++++++++------
 1 file changed, 35 insertions(+), 14 deletions(-)

diff --git a/tools/memory-model/Documentation/access-marking.txt b/tools/memory-model/Documentation/access-marking.txt
index fe4ad6d12d24c..a3dcc32e27b44 100644
--- a/tools/memory-model/Documentation/access-marking.txt
+++ b/tools/memory-model/Documentation/access-marking.txt
@@ -37,7 +37,9 @@ compiler's use of code-motion and common-subexpression optimizations.
 Therefore, if a given access is involved in an intentional data race,
 using READ_ONCE() for loads and WRITE_ONCE() for stores is usually
 preferable to data_race(), which in turn is usually preferable to plain
-C-language accesses.
+C-language accesses.  It is permissible to combine #2 and #3, for example,
+data_race(READ_ONCE(a)), which will both restrict compiler optimizations
+and disable KCSAN diagnostics.
 
 KCSAN will complain about many types of data races involving plain
 C-language accesses, but marking all accesses involved in a given data
@@ -86,6 +88,10 @@ that fail to exclude the updates.  In this case, it is important to use
 data_race() for the diagnostic reads because otherwise KCSAN would give
 false-positive warnings about these diagnostic reads.
 
+If it is necessary to both restrict compiler optimizations and disable
+KCSAN diagnostics, use both data_race() and READ_ONCE(), for example,
+data_race(READ_ONCE(a)).
+
 In theory, plain C-language loads can also be used for this use case.
 However, in practice this will have the disadvantage of causing KCSAN
 to generate false positives because KCSAN will have no way of knowing
@@ -279,19 +285,34 @@ tells KCSAN that data races are expected, and should be silently
 ignored.  This data_race() also tells the human reading the code that
 read_foo_diagnostic() might sometimes return a bogus value.
 
-However, please note that your kernel must be built with
-CONFIG_KCSAN_ASSUME_PLAIN_WRITES_ATOMIC=n in order for KCSAN to
-detect a buggy lockless write.  If you need KCSAN to detect such a
-write even if that write did not change the value of foo, you also
-need CONFIG_KCSAN_REPORT_VALUE_CHANGE_ONLY=n.  If you need KCSAN to
-detect such a write happening in an interrupt handler running on the
-same CPU doing the legitimate lock-protected write, you also need
-CONFIG_KCSAN_INTERRUPT_WATCHER=y.  With some or all of these Kconfig
-options set properly, KCSAN can be quite helpful, although it is not
-necessarily a full replacement for hardware watchpoints.  On the other
-hand, neither are hardware watchpoints a full replacement for KCSAN
-because it is not always easy to tell hardware watchpoint to conditionally
-trap on accesses.
+If it is necessary to suppress compiler optimization and also detect
+buggy lockless writes, read_foo_diagnostic() can be updated as follows:
+
+	void read_foo_diagnostic(void)
+	{
+		pr_info("Current value of foo: %d\n", data_race(READ_ONCE(foo)));
+	}
+
+Alternatively, given that KCSAN is to ignore all accesses in this function,
+this function can be marked __no_kcsan and the data_race() can be dropped:
+
+	void __no_kcsan read_foo_diagnostic(void)
+	{
+		pr_info("Current value of foo: %d\n", READ_ONCE(foo));
+	}
+
+However, in order for KCSAN to detect buggy lockless writes, your kernel
+must be built with CONFIG_KCSAN_ASSUME_PLAIN_WRITES_ATOMIC=n.  If you
+need KCSAN to detect such a write even if that write did not change
+the value of foo, you also need CONFIG_KCSAN_REPORT_VALUE_CHANGE_ONLY=n.
+If you need KCSAN to detect such a write happening in an interrupt handler
+running on the same CPU doing the legitimate lock-protected write, you
+also need CONFIG_KCSAN_INTERRUPT_WATCHER=y.  With some or all of these
+Kconfig options set properly, KCSAN can be quite helpful, although
+it is not necessarily a full replacement for hardware watchpoints.
+On the other hand, neither are hardware watchpoints a full replacement
+for KCSAN because it is not always easy to tell hardware watchpoint to
+conditionally trap on accesses.
 
 
 Lock-Protected Writes With Lockless Reads
-- 
2.31.1.189.g2e36527f23

Re: [PATCH memory-model 2/4] tools/memory-model: Add example for heuristic lockless reads

[Alan Stern]

On Wed, Jul 21, 2021 at 02:10:01PM -0700, Paul E. McKenney wrote:
> This commit adds example code for heuristic lockless reads, based loosely
> on the sem_lock() and sem_unlock() functions.
> 
> Reported-by: Manfred Spraul <manfred@colorfullife.com>
> [ paulmck: Update per Manfred Spraul and Hillf Danton feedback. ]
> Signed-off-by: Paul E. McKenney <paulmck@kernel.org>
> ---
>  .../Documentation/access-marking.txt          | 94 +++++++++++++++++++
>  1 file changed, 94 insertions(+)
> 
> diff --git a/tools/memory-model/Documentation/access-marking.txt b/tools/memory-model/Documentation/access-marking.txt
> index 58bff26198767..be7d507997cf8 100644
> --- a/tools/memory-model/Documentation/access-marking.txt
> +++ b/tools/memory-model/Documentation/access-marking.txt
> @@ -319,6 +319,100 @@ of the ASSERT_EXCLUSIVE_WRITER() is to allow KCSAN to check for a buggy
>  concurrent lockless write.
>  
>  
> +Lock-Protected Writes With Heuristic Lockless Reads
> +---------------------------------------------------
> +
> +For another example, suppose that the code can normally make use of
> +a per-data-structure lock, but there are times when a global lock
> +is required.  These times are indicated via a global flag.  The code
> +might look as follows, and is based loosely on nf_conntrack_lock(),
> +nf_conntrack_all_lock(), and nf_conntrack_all_unlock():
> +
> +	bool global_flag;
> +	DEFINE_SPINLOCK(global_lock);
> +	struct foo {
> +		spinlock_t f_lock;
> +		int f_data;
> +	};
> +
> +	/* All foo structures are in the following array. */
> +	int nfoo;
> +	struct foo *foo_array;
> +
> +	void do_something_locked(struct foo *fp)
> +	{
> +		bool gf = true;
> +
> +		/* IMPORTANT: Heuristic plus spin_lock()! */
> +		if (!data_race(global_flag)) {
> +			spin_lock(&fp->f_lock);
> +			if (!smp_load_acquire(&global_flag)) {
> +				do_something(fp);
> +				spin_unlock(&fp->f_lock);
> +				return;
> +			}
> +			spin_unlock(&fp->f_lock);
> +		}
> +		spin_lock(&global_lock);
> +		/* Lock held, thus global flag cannot change. */
> +		if (!global_flag) {

How can global_flag ever be true at this point?  The only line of code 
that sets it is in begin_global() below, it only runs while global_lock 
is held, and global_flag is set back to false before the lock is 
released.

> +			spin_lock(&fp->f_lock);
> +			spin_unlock(&global_lock);
> +			gf = false;
> +		}
> +		do_something(fp);
> +		if (fg)

Should be gf, not fg.

> +			spin_unlock(&global_lock);
> +		else
> +			spin_lock(&fp->f_lock);
> +	}
> +
> +	void begin_global(void)
> +	{
> +		int i;
> +
> +		spin_lock(&global_lock);
> +		WRITE_ONCE(global_flag, true);

Why does this need to be WRITE_ONCE?  It still races with the first read 
of global_flag above.

> +		for (i = 0; i < nfoo; i++) {
> +			/* Wait for pre-existing local locks. */
> +			spin_lock(&fp->f_lock);
> +			spin_unlock(&fp->f_lock);

Why not acquire all the locks here and release all of them in 
end_global()?  Then global_flag wouldn't need acquire-release 
sychronization.

> +		}
> +	}
> +
> +	void end_global(void)
> +	{
> +		smp_store_release(&global_flag, false);
> +		/* Pre-existing global lock acquisitions will recheck. */

What does that comment mean?  How can there be any pre-existing global 
lock acquisitions when we hold the lock right now?

> +		spin_unlock(&global_lock);
> +	}
> +
> +All code paths leading from the do_something_locked() function's first
> +read from global_flag acquire a lock, so endless load fusing cannot
> +happen.
> +
> +If the value read from global_flag is true, then global_flag is rechecked
> +while holding global_lock, which prevents global_flag from changing.
> +If this recheck finds that global_flag is now false, the acquisition

Again, how can't global_flag be false now?

Did you originally have in mind some sort of scheme in which 
begin_global() would release global_lock before returning and 
end_global() would acquire global_lock before clearing global_flag?  But 
I don't see how that could work without changes to do_something_locked().

> +of ->f_lock prior to the release of global_lock will result in any subsequent
> +begin_global() invocation waiting to acquire ->f_lock.
> +
> +On the other hand, if the value read from global_flag is false, then
> +global_flag, then rechecking under ->f_lock combined with synchronization
---^^^^^^^^^^^^^^^^^^

Typo?

> +with begin_global() guarantees than any erroneous read will cause the
> +do_something_locked() function's first do_something() invocation to happen
> +before begin_global() returns.  The combination of the smp_load_acquire()
> +in do_something_locked() and the smp_store_release() in end_global()
> +guarantees that either the do_something_locked() function's first
> +do_something() invocation happens after the call to end_global() or that
> +do_something_locked() acquires global_lock() and rechecks under the lock.

This last sentence also makes no sense unless you imagine dropping 
global_lock between begin_global() and end_global().

Alan

Re: [PATCH memory-model 2/4] tools/memory-model: Add example for heuristic lockless reads

[Manfred Spraul]

Hi Alan,

On 7/23/21 4:08 AM, Alan Stern wrote:
> On Wed, Jul 21, 2021 at 02:10:01PM -0700, Paul E. McKenney wrote:
>> This commit adds example code for heuristic lockless reads, based loosely
>> on the sem_lock() and sem_unlock() functions.
>>
>> Reported-by: Manfred Spraul <manfred@colorfullife.com>
>> [ paulmck: Update per Manfred Spraul and Hillf Danton feedback. ]
>> Signed-off-by: Paul E. McKenney <paulmck@kernel.org>
>> ---
>>   .../Documentation/access-marking.txt          | 94 +++++++++++++++++++
>>   1 file changed, 94 insertions(+)
>>
>> diff --git a/tools/memory-model/Documentation/access-marking.txt b/tools/memory-model/Documentation/access-marking.txt
>> index 58bff26198767..be7d507997cf8 100644
>> --- a/tools/memory-model/Documentation/access-marking.txt
>> +++ b/tools/memory-model/Documentation/access-marking.txt
>> @@ -319,6 +319,100 @@ of the ASSERT_EXCLUSIVE_WRITER() is to allow KCSAN to check for a buggy
>>   concurrent lockless write.
>>   
>>   
>> +Lock-Protected Writes With Heuristic Lockless Reads
>> +---------------------------------------------------
>> +
>> +For another example, suppose that the code can normally make use of
>> +a per-data-structure lock, but there are times when a global lock
>> +is required.  These times are indicated via a global flag.  The code
>> +might look as follows, and is based loosely on nf_conntrack_lock(),
>> +nf_conntrack_all_lock(), and nf_conntrack_all_unlock():
>> +
>> +	bool global_flag;
>> +	DEFINE_SPINLOCK(global_lock);
>> +	struct foo {
>> +		spinlock_t f_lock;
>> +		int f_data;
>> +	};
>> +
>> +	/* All foo structures are in the following array. */
>> +	int nfoo;
>> +	struct foo *foo_array;
>> +
>> +	void do_something_locked(struct foo *fp)
>> +	{
>> +		bool gf = true;
>> +
>> +		/* IMPORTANT: Heuristic plus spin_lock()! */
>> +		if (!data_race(global_flag)) {
>> +			spin_lock(&fp->f_lock);
>> +			if (!smp_load_acquire(&global_flag)) {
>> +				do_something(fp);
>> +				spin_unlock(&fp->f_lock);
>> +				return;
>> +			}
>> +			spin_unlock(&fp->f_lock);
>> +		}
>> +		spin_lock(&global_lock);
>> +		/* Lock held, thus global flag cannot change. */
>> +		if (!global_flag) {
> How can global_flag ever be true at this point?  The only line of code
> that sets it is in begin_global() below, it only runs while global_lock
> is held, and global_flag is set back to false before the lock is
> released.

It can't be true. The code is a simplified version of the algorithm in 
ipc/sem.c.

For the ipc/sem.c, global_flag can remain true even after dropping 
global_lock.

When transferring the approach to nf_conntrack_core, I didn't notice 
that nf_conntrack doesn't need a persistent global_flag.

Thus the recheck after spin_lock(&global_lock) is not needed.


>> +			spin_lock(&fp->f_lock);
>> +			spin_unlock(&global_lock);
>> +			gf = false;
>> +		}
>> +		do_something(fp);
>> +		if (fg)
> Should be gf, not fg.
>
>> +			spin_unlock(&global_lock);
>> +		else
>> +			spin_lock(&fp->f_lock);
>> +	}
>> +
>> +	void begin_global(void)
>> +	{
>> +		int i;
>> +
>> +		spin_lock(&global_lock);
>> +		WRITE_ONCE(global_flag, true);
> Why does this need to be WRITE_ONCE?  It still races with the first read
> of global_flag above.
>
>> +		for (i = 0; i < nfoo; i++) {
>> +			/* Wait for pre-existing local locks. */
>> +			spin_lock(&fp->f_lock);
>> +			spin_unlock(&fp->f_lock);
> Why not acquire all the locks here and release all of them in
> end_global()?  Then global_flag wouldn't need acquire-release
> sychronization.

 From my understanding:
spin_lock contains preempt_count_add, thus you can't acquire more than 
255 spinlocks (actually 245, the warning limit is 10 below 255)

>> +		}
>> +	}
>> +
>> +	void end_global(void)
>> +	{
>> +		smp_store_release(&global_flag, false);
>> +		/* Pre-existing global lock acquisitions will recheck. */
> What does that comment mean?  How can there be any pre-existing global
> lock acquisitions when we hold the lock right now?

>> +		spin_unlock(&global_lock);
>> +	}
>> +
>> +All code paths leading from the do_something_locked() function's first
>> +read from global_flag acquire a lock, so endless load fusing cannot
>> +happen.
>> +
>> +If the value read from global_flag is true, then global_flag is rechecked
>> +while holding global_lock, which prevents global_flag from changing.
>> +If this recheck finds that global_flag is now false, the acquisition
> Again, how can't global_flag be false now?
>
> Did you originally have in mind some sort of scheme in which
> begin_global() would release global_lock before returning and
> end_global() would acquire global_lock before clearing global_flag?  But
> I don't see how that could work without changes to do_something_locked().
>
>> +of ->f_lock prior to the release of global_lock will result in any subsequent
>> +begin_global() invocation waiting to acquire ->f_lock.
>> +
>> +On the other hand, if the value read from global_flag is false, then
>> +global_flag, then rechecking under ->f_lock combined with synchronization
> ---^^^^^^^^^^^^^^^^^^
>
> Typo?
>
>> +with begin_global() guarantees than any erroneous read will cause the
>> +do_something_locked() function's first do_something() invocation to happen
>> +before begin_global() returns.  The combination of the smp_load_acquire()
>> +in do_something_locked() and the smp_store_release() in end_global()
>> +guarantees that either the do_something_locked() function's first
>> +do_something() invocation happens after the call to end_global() or that
>> +do_something_locked() acquires global_lock() and rechecks under the lock.
> This last sentence also makes no sense unless you imagine dropping
> global_lock between begin_global() and end_global().

ipc/sem.c does that and needs that, nf_conntrack doesn't use this.


--

     Manfred

Re: [PATCH memory-model 2/4] tools/memory-model: Add example for heuristic lockless reads

[Alan Stern]

On Fri, Jul 23, 2021 at 08:52:50AM +0200, Manfred Spraul wrote:
> Hi Alan,

Hi.

> On 7/23/21 4:08 AM, Alan Stern wrote:
> > On Wed, Jul 21, 2021 at 02:10:01PM -0700, Paul E. McKenney wrote:
> > > This commit adds example code for heuristic lockless reads, based loosely
> > > on the sem_lock() and sem_unlock() functions.
> > > 
> > > Reported-by: Manfred Spraul <manfred@colorfullife.com>
> > > [ paulmck: Update per Manfred Spraul and Hillf Danton feedback. ]
> > > Signed-off-by: Paul E. McKenney <paulmck@kernel.org>
> > > ---
> > >   .../Documentation/access-marking.txt          | 94 +++++++++++++++++++
> > >   1 file changed, 94 insertions(+)
> > > 
> > > diff --git a/tools/memory-model/Documentation/access-marking.txt b/tools/memory-model/Documentation/access-marking.txt
> > > index 58bff26198767..be7d507997cf8 100644
> > > --- a/tools/memory-model/Documentation/access-marking.txt
> > > +++ b/tools/memory-model/Documentation/access-marking.txt
> > > @@ -319,6 +319,100 @@ of the ASSERT_EXCLUSIVE_WRITER() is to allow KCSAN to check for a buggy
> > >   concurrent lockless write.
> > > +Lock-Protected Writes With Heuristic Lockless Reads
> > > +---------------------------------------------------
> > > +
> > > +For another example, suppose that the code can normally make use of
> > > +a per-data-structure lock, but there are times when a global lock
> > > +is required.  These times are indicated via a global flag.  The code
> > > +might look as follows, and is based loosely on nf_conntrack_lock(),
> > > +nf_conntrack_all_lock(), and nf_conntrack_all_unlock():
> > > +
> > > +	bool global_flag;
> > > +	DEFINE_SPINLOCK(global_lock);
> > > +	struct foo {
> > > +		spinlock_t f_lock;
> > > +		int f_data;
> > > +	};
> > > +
> > > +	/* All foo structures are in the following array. */
> > > +	int nfoo;
> > > +	struct foo *foo_array;
> > > +
> > > +	void do_something_locked(struct foo *fp)
> > > +	{
> > > +		bool gf = true;
> > > +
> > > +		/* IMPORTANT: Heuristic plus spin_lock()! */
> > > +		if (!data_race(global_flag)) {
> > > +			spin_lock(&fp->f_lock);
> > > +			if (!smp_load_acquire(&global_flag)) {
> > > +				do_something(fp);
> > > +				spin_unlock(&fp->f_lock);
> > > +				return;
> > > +			}
> > > +			spin_unlock(&fp->f_lock);
> > > +		}
> > > +		spin_lock(&global_lock);
> > > +		/* Lock held, thus global flag cannot change. */
> > > +		if (!global_flag) {
> > How can global_flag ever be true at this point?  The only line of code
> > that sets it is in begin_global() below, it only runs while global_lock
> > is held, and global_flag is set back to false before the lock is
> > released.
> 
> It can't be true. The code is a simplified version of the algorithm in
> ipc/sem.c.
> 
> For the ipc/sem.c, global_flag can remain true even after dropping
> global_lock.
> 
> When transferring the approach to nf_conntrack_core, I didn't notice that
> nf_conntrack doesn't need a persistent global_flag.
> 
> Thus the recheck after spin_lock(&global_lock) is not needed.

In fact, since global_flag is true if and only if global_lock is locked, 
perhaps it can be removed entirely and replaced with 
spin_is_locked(&global_lock).

> > > +			spin_lock(&fp->f_lock);
> > > +			spin_unlock(&global_lock);
> > > +			gf = false;
> > > +		}
> > > +		do_something(fp);
> > > +		if (fg)
> > Should be gf, not fg.
> > 
> > > +			spin_unlock(&global_lock);
> > > +		else
> > > +			spin_lock(&fp->f_lock);
> > > +	}
> > > +
> > > +	void begin_global(void)
> > > +	{
> > > +		int i;
> > > +
> > > +		spin_lock(&global_lock);
> > > +		WRITE_ONCE(global_flag, true);
> > Why does this need to be WRITE_ONCE?  It still races with the first read
> > of global_flag above.
> > 
> > > +		for (i = 0; i < nfoo; i++) {
> > > +			/* Wait for pre-existing local locks. */
> > > +			spin_lock(&fp->f_lock);
> > > +			spin_unlock(&fp->f_lock);
> > Why not acquire all the locks here and release all of them in
> > end_global()?  Then global_flag wouldn't need acquire-release
> > sychronization.
> 
> From my understanding:
> spin_lock contains preempt_count_add, thus you can't acquire more than 255
> spinlocks (actually 245, the warning limit is 10 below 255)

It might be worth mentioning this in a code comment.  Or in the 
accompanying text.

> > > +		}
> > > +	}
> > > +
> > > +	void end_global(void)
> > > +	{
> > > +		smp_store_release(&global_flag, false);
> > > +		/* Pre-existing global lock acquisitions will recheck. */
> > What does that comment mean?  How can there be any pre-existing global
> > lock acquisitions when we hold the lock right now?
> 
> > > +		spin_unlock(&global_lock);
> > > +	}
> > > +
> > > +All code paths leading from the do_something_locked() function's first
> > > +read from global_flag acquire a lock, so endless load fusing cannot
> > > +happen.
> > > +
> > > +If the value read from global_flag is true, then global_flag is rechecked
> > > +while holding global_lock, which prevents global_flag from changing.
> > > +If this recheck finds that global_flag is now false, the acquisition
> > Again, how can't global_flag be false now?
> > 
> > Did you originally have in mind some sort of scheme in which
> > begin_global() would release global_lock before returning and
> > end_global() would acquire global_lock before clearing global_flag?  But
> > I don't see how that could work without changes to do_something_locked().
> > 
> > > +of ->f_lock prior to the release of global_lock will result in any subsequent
> > > +begin_global() invocation waiting to acquire ->f_lock.
> > > +
> > > +On the other hand, if the value read from global_flag is false, then
> > > +global_flag, then rechecking under ->f_lock combined with synchronization
> > ---^^^^^^^^^^^^^^^^^^
> > 
> > Typo?
> > 
> > > +with begin_global() guarantees than any erroneous read will cause the
> > > +do_something_locked() function's first do_something() invocation to happen
> > > +before begin_global() returns.  The combination of the smp_load_acquire()
> > > +in do_something_locked() and the smp_store_release() in end_global()
> > > +guarantees that either the do_something_locked() function's first
> > > +do_something() invocation happens after the call to end_global() or that
> > > +do_something_locked() acquires global_lock() and rechecks under the lock.
> > This last sentence also makes no sense unless you imagine dropping
> > global_lock between begin_global() and end_global().
> 
> ipc/sem.c does that and needs that, nf_conntrack doesn't use this.

Given all these issues, it seems like this patch needs to be re-written.

Alan Stern

Re: [PATCH memory-model 2/4] tools/memory-model: Add example for heuristic lockless reads

[Manfred Spraul]

Hi Alan,

On 7/23/21 3:05 PM, Alan Stern wrote:
> On Fri, Jul 23, 2021 at 08:52:50AM +0200, Manfred Spraul wrote:
>> Hi Alan,
> Hi.
>
>> On 7/23/21 4:08 AM, Alan Stern wrote:
>>> On Wed, Jul 21, 2021 at 02:10:01PM -0700, Paul E. McKenney wrote:
>>>> This commit adds example code for heuristic lockless reads, based loosely
>>>> on the sem_lock() and sem_unlock() functions.
>>>>
>>>> Reported-by: Manfred Spraul <manfred@colorfullife.com>
>>>> [ paulmck: Update per Manfred Spraul and Hillf Danton feedback. ]
>>>> Signed-off-by: Paul E. McKenney <paulmck@kernel.org>
>>>> ---
>>>>    .../Documentation/access-marking.txt          | 94 +++++++++++++++++++
>>>>    1 file changed, 94 insertions(+)
>>>>
>>>> diff --git a/tools/memory-model/Documentation/access-marking.txt b/tools/memory-model/Documentation/access-marking.txt
>>>> index 58bff26198767..be7d507997cf8 100644
>>>> --- a/tools/memory-model/Documentation/access-marking.txt
>>>> +++ b/tools/memory-model/Documentation/access-marking.txt
>>>> @@ -319,6 +319,100 @@ of the ASSERT_EXCLUSIVE_WRITER() is to allow KCSAN to check for a buggy
>>>>    concurrent lockless write.
>>>> +Lock-Protected Writes With Heuristic Lockless Reads
>>>> +---------------------------------------------------
>>>> +
>>>> +For another example, suppose that the code can normally make use of
>>>> +a per-data-structure lock, but there are times when a global lock
>>>> +is required.  These times are indicated via a global flag.  The code
>>>> +might look as follows, and is based loosely on nf_conntrack_lock(),
>>>> +nf_conntrack_all_lock(), and nf_conntrack_all_unlock():
>>>> +
>>>> +	bool global_flag;
>>>> +	DEFINE_SPINLOCK(global_lock);
>>>> +	struct foo {
>>>> +		spinlock_t f_lock;
>>>> +		int f_data;
>>>> +	};
>>>> +
>>>> +	/* All foo structures are in the following array. */
>>>> +	int nfoo;
>>>> +	struct foo *foo_array;
>>>> +
>>>> +	void do_something_locked(struct foo *fp)
>>>> +	{
>>>> +		bool gf = true;
>>>> +
>>>> +		/* IMPORTANT: Heuristic plus spin_lock()! */
>>>> +		if (!data_race(global_flag)) {
>>>> +			spin_lock(&fp->f_lock);
>>>> +			if (!smp_load_acquire(&global_flag)) {
>>>> +				do_something(fp);
>>>> +				spin_unlock(&fp->f_lock);
>>>> +				return;
>>>> +			}
>>>> +			spin_unlock(&fp->f_lock);
>>>> +		}
>>>> +		spin_lock(&global_lock);
>>>> +		/* Lock held, thus global flag cannot change. */
>>>> +		if (!global_flag) {
>>> How can global_flag ever be true at this point?  The only line of code
>>> that sets it is in begin_global() below, it only runs while global_lock
>>> is held, and global_flag is set back to false before the lock is
>>> released.
>> It can't be true. The code is a simplified version of the algorithm in
>> ipc/sem.c.
>>
>> For the ipc/sem.c, global_flag can remain true even after dropping
>> global_lock.
>>
>> When transferring the approach to nf_conntrack_core, I didn't notice that
>> nf_conntrack doesn't need a persistent global_flag.
>>
>> Thus the recheck after spin_lock(&global_lock) is not needed.
> In fact, since global_flag is true if and only if global_lock is locked,
> perhaps it can be removed entirely and replaced with
> spin_is_locked(&global_lock).

I try to avoid spin_is_locked():

- spin_is_locked() is no memory barrier

- spin_lock() is an acquire memory barrier - for the read part. There is 
no barrier at all related to the write part.

With an explicit variable, the memory barriers can be controlled much 
better - and it is guaranteed to work in the same way on all architectures.


--

     Manfred

Re: [PATCH memory-model 2/4] tools/memory-model: Add example for heuristic lockless reads

[Paul E. McKenney]

On Thu, Jul 22, 2021 at 10:08:46PM -0400, Alan Stern wrote:
> On Wed, Jul 21, 2021 at 02:10:01PM -0700, Paul E. McKenney wrote:
> > This commit adds example code for heuristic lockless reads, based loosely
> > on the sem_lock() and sem_unlock() functions.
> > 
> > Reported-by: Manfred Spraul <manfred@colorfullife.com>
> > [ paulmck: Update per Manfred Spraul and Hillf Danton feedback. ]
> > Signed-off-by: Paul E. McKenney <paulmck@kernel.org>
> > ---
> >  .../Documentation/access-marking.txt          | 94 +++++++++++++++++++
> >  1 file changed, 94 insertions(+)
> > 
> > diff --git a/tools/memory-model/Documentation/access-marking.txt b/tools/memory-model/Documentation/access-marking.txt
> > index 58bff26198767..be7d507997cf8 100644
> > --- a/tools/memory-model/Documentation/access-marking.txt
> > +++ b/tools/memory-model/Documentation/access-marking.txt
> > @@ -319,6 +319,100 @@ of the ASSERT_EXCLUSIVE_WRITER() is to allow KCSAN to check for a buggy
> >  concurrent lockless write.
> >  
> >  
> > +Lock-Protected Writes With Heuristic Lockless Reads
> > +---------------------------------------------------
> > +
> > +For another example, suppose that the code can normally make use of
> > +a per-data-structure lock, but there are times when a global lock
> > +is required.  These times are indicated via a global flag.  The code
> > +might look as follows, and is based loosely on nf_conntrack_lock(),
> > +nf_conntrack_all_lock(), and nf_conntrack_all_unlock():
> > +
> > +	bool global_flag;
> > +	DEFINE_SPINLOCK(global_lock);
> > +	struct foo {
> > +		spinlock_t f_lock;
> > +		int f_data;
> > +	};
> > +
> > +	/* All foo structures are in the following array. */
> > +	int nfoo;
> > +	struct foo *foo_array;
> > +
> > +	void do_something_locked(struct foo *fp)
> > +	{
> > +		bool gf = true;
> > +
> > +		/* IMPORTANT: Heuristic plus spin_lock()! */
> > +		if (!data_race(global_flag)) {
> > +			spin_lock(&fp->f_lock);
> > +			if (!smp_load_acquire(&global_flag)) {
> > +				do_something(fp);
> > +				spin_unlock(&fp->f_lock);
> > +				return;
> > +			}
> > +			spin_unlock(&fp->f_lock);
> > +		}
> > +		spin_lock(&global_lock);
> > +		/* Lock held, thus global flag cannot change. */
> > +		if (!global_flag) {
> 
> How can global_flag ever be true at this point?  The only line of code 
> that sets it is in begin_global() below, it only runs while global_lock 
> is held, and global_flag is set back to false before the lock is 
> released.

Good point.  The fact that wwe hold global_lock means that global_flag
cannot be set, which means that we can unconditionally acquire the
per-foo lock and release global_lock.

> > +			spin_lock(&fp->f_lock);
> > +			spin_unlock(&global_lock);
> > +			gf = false;
> > +		}
> > +		do_something(fp);
> > +		if (fg)
> 
> Should be gf, not fg.

And we can also eliminate gf and its typo.

> > +			spin_unlock(&global_lock);
> > +		else
> > +			spin_lock(&fp->f_lock);
> > +	}
> > +
> > +	void begin_global(void)
> > +	{
> > +		int i;
> > +
> > +		spin_lock(&global_lock);
> > +		WRITE_ONCE(global_flag, true);
> 
> Why does this need to be WRITE_ONCE?  It still races with the first read 
> of global_flag above.

But also with the smp_load_acquire() of global_flag, right?

> > +		for (i = 0; i < nfoo; i++) {
> > +			/* Wait for pre-existing local locks. */
> > +			spin_lock(&fp->f_lock);
> > +			spin_unlock(&fp->f_lock);
> 
> Why not acquire all the locks here and release all of them in 
> end_global()?  Then global_flag wouldn't need acquire-release 
> sychronization.

As suggested later in this thread, I have added a comment.

> > +		}
> > +	}
> > +
> > +	void end_global(void)
> > +	{
> > +		smp_store_release(&global_flag, false);
> > +		/* Pre-existing global lock acquisitions will recheck. */
> 
> What does that comment mean?  How can there be any pre-existing global 
> lock acquisitions when we hold the lock right now?

I have removed this comment.  The last shred of reason for it went away
with the gf local variable.

> > +		spin_unlock(&global_lock);
> > +	}
> > +
> > +All code paths leading from the do_something_locked() function's first
> > +read from global_flag acquire a lock, so endless load fusing cannot
> > +happen.
> > +
> > +If the value read from global_flag is true, then global_flag is rechecked
> > +while holding global_lock, which prevents global_flag from changing.
> > +If this recheck finds that global_flag is now false, the acquisition
> 
> Again, how can't global_flag be false now?
> 
> Did you originally have in mind some sort of scheme in which 
> begin_global() would release global_lock before returning and 
> end_global() would acquire global_lock before clearing global_flag?  But 
> I don't see how that could work without changes to do_something_locked().

I was thinking along those lines, but I clearly wasn't thinking very
clearly.  :-/

> > +of ->f_lock prior to the release of global_lock will result in any subsequent
> > +begin_global() invocation waiting to acquire ->f_lock.
> > +
> > +On the other hand, if the value read from global_flag is false, then
> > +global_flag, then rechecking under ->f_lock combined with synchronization
> ---^^^^^^^^^^^^^^^^^^
> 
> Typo?

Good catch, and I took care of this by rewriting this paragraph.

Likely introducing other typos in the process, but so it goes.

> > +with begin_global() guarantees than any erroneous read will cause the
> > +do_something_locked() function's first do_something() invocation to happen
> > +before begin_global() returns.  The combination of the smp_load_acquire()
> > +in do_something_locked() and the smp_store_release() in end_global()
> > +guarantees that either the do_something_locked() function's first
> > +do_something() invocation happens after the call to end_global() or that
> > +do_something_locked() acquires global_lock() and rechecks under the lock.
> 
> This last sentence also makes no sense unless you imagine dropping 
> global_lock between begin_global() and end_global().

Agreed.

						Thanx, Paul

Re: [PATCH memory-model 2/4] tools/memory-model: Add example for heuristic lockless reads

[Paul E. McKenney]

On Fri, Jul 23, 2021 at 09:05:54AM -0400, Alan Stern wrote:
> On Fri, Jul 23, 2021 at 08:52:50AM +0200, Manfred Spraul wrote:
> > Hi Alan,
> 
> Hi.
> 
> > On 7/23/21 4:08 AM, Alan Stern wrote:
> > > On Wed, Jul 21, 2021 at 02:10:01PM -0700, Paul E. McKenney wrote:
> > > > This commit adds example code for heuristic lockless reads, based loosely
> > > > on the sem_lock() and sem_unlock() functions.
> > > > 
> > > > Reported-by: Manfred Spraul <manfred@colorfullife.com>
> > > > [ paulmck: Update per Manfred Spraul and Hillf Danton feedback. ]
> > > > Signed-off-by: Paul E. McKenney <paulmck@kernel.org>
> > > > ---
> > > >   .../Documentation/access-marking.txt          | 94 +++++++++++++++++++
> > > >   1 file changed, 94 insertions(+)
> > > > 
> > > > diff --git a/tools/memory-model/Documentation/access-marking.txt b/tools/memory-model/Documentation/access-marking.txt
> > > > index 58bff26198767..be7d507997cf8 100644
> > > > --- a/tools/memory-model/Documentation/access-marking.txt
> > > > +++ b/tools/memory-model/Documentation/access-marking.txt
> > > > @@ -319,6 +319,100 @@ of the ASSERT_EXCLUSIVE_WRITER() is to allow KCSAN to check for a buggy
> > > >   concurrent lockless write.
> > > > +Lock-Protected Writes With Heuristic Lockless Reads
> > > > +---------------------------------------------------
> > > > +
> > > > +For another example, suppose that the code can normally make use of
> > > > +a per-data-structure lock, but there are times when a global lock
> > > > +is required.  These times are indicated via a global flag.  The code
> > > > +might look as follows, and is based loosely on nf_conntrack_lock(),
> > > > +nf_conntrack_all_lock(), and nf_conntrack_all_unlock():
> > > > +
> > > > +	bool global_flag;
> > > > +	DEFINE_SPINLOCK(global_lock);
> > > > +	struct foo {
> > > > +		spinlock_t f_lock;
> > > > +		int f_data;
> > > > +	};
> > > > +
> > > > +	/* All foo structures are in the following array. */
> > > > +	int nfoo;
> > > > +	struct foo *foo_array;
> > > > +
> > > > +	void do_something_locked(struct foo *fp)
> > > > +	{
> > > > +		bool gf = true;
> > > > +
> > > > +		/* IMPORTANT: Heuristic plus spin_lock()! */
> > > > +		if (!data_race(global_flag)) {
> > > > +			spin_lock(&fp->f_lock);
> > > > +			if (!smp_load_acquire(&global_flag)) {
> > > > +				do_something(fp);
> > > > +				spin_unlock(&fp->f_lock);
> > > > +				return;
> > > > +			}
> > > > +			spin_unlock(&fp->f_lock);
> > > > +		}
> > > > +		spin_lock(&global_lock);
> > > > +		/* Lock held, thus global flag cannot change. */
> > > > +		if (!global_flag) {
> > > How can global_flag ever be true at this point?  The only line of code
> > > that sets it is in begin_global() below, it only runs while global_lock
> > > is held, and global_flag is set back to false before the lock is
> > > released.
> > 
> > It can't be true. The code is a simplified version of the algorithm in
> > ipc/sem.c.
> > 
> > For the ipc/sem.c, global_flag can remain true even after dropping
> > global_lock.
> > 
> > When transferring the approach to nf_conntrack_core, I didn't notice that
> > nf_conntrack doesn't need a persistent global_flag.
> > 
> > Thus the recheck after spin_lock(&global_lock) is not needed.
> 
> In fact, since global_flag is true if and only if global_lock is locked, 
> perhaps it can be removed entirely and replaced with 
> spin_is_locked(&global_lock).
> 
> > > > +			spin_lock(&fp->f_lock);
> > > > +			spin_unlock(&global_lock);
> > > > +			gf = false;
> > > > +		}
> > > > +		do_something(fp);
> > > > +		if (fg)
> > > Should be gf, not fg.
> > > 
> > > > +			spin_unlock(&global_lock);
> > > > +		else
> > > > +			spin_lock(&fp->f_lock);
> > > > +	}
> > > > +
> > > > +	void begin_global(void)
> > > > +	{
> > > > +		int i;
> > > > +
> > > > +		spin_lock(&global_lock);
> > > > +		WRITE_ONCE(global_flag, true);
> > > Why does this need to be WRITE_ONCE?  It still races with the first read
> > > of global_flag above.
> > > 
> > > > +		for (i = 0; i < nfoo; i++) {
> > > > +			/* Wait for pre-existing local locks. */
> > > > +			spin_lock(&fp->f_lock);
> > > > +			spin_unlock(&fp->f_lock);
> > > Why not acquire all the locks here and release all of them in
> > > end_global()?  Then global_flag wouldn't need acquire-release
> > > sychronization.
> > 
> > From my understanding:
> > spin_lock contains preempt_count_add, thus you can't acquire more than 255
> > spinlocks (actually 245, the warning limit is 10 below 255)
> 
> It might be worth mentioning this in a code comment.  Or in the 
> accompanying text.

As noted earlier, done.

> > > > +		}
> > > > +	}
> > > > +
> > > > +	void end_global(void)
> > > > +	{
> > > > +		smp_store_release(&global_flag, false);
> > > > +		/* Pre-existing global lock acquisitions will recheck. */
> > > What does that comment mean?  How can there be any pre-existing global
> > > lock acquisitions when we hold the lock right now?
> > 
> > > > +		spin_unlock(&global_lock);
> > > > +	}
> > > > +
> > > > +All code paths leading from the do_something_locked() function's first
> > > > +read from global_flag acquire a lock, so endless load fusing cannot
> > > > +happen.
> > > > +
> > > > +If the value read from global_flag is true, then global_flag is rechecked
> > > > +while holding global_lock, which prevents global_flag from changing.
> > > > +If this recheck finds that global_flag is now false, the acquisition
> > > Again, how can't global_flag be false now?
> > > 
> > > Did you originally have in mind some sort of scheme in which
> > > begin_global() would release global_lock before returning and
> > > end_global() would acquire global_lock before clearing global_flag?  But
> > > I don't see how that could work without changes to do_something_locked().
> > > 
> > > > +of ->f_lock prior to the release of global_lock will result in any subsequent
> > > > +begin_global() invocation waiting to acquire ->f_lock.
> > > > +
> > > > +On the other hand, if the value read from global_flag is false, then
> > > > +global_flag, then rechecking under ->f_lock combined with synchronization
> > > ---^^^^^^^^^^^^^^^^^^
> > > 
> > > Typo?
> > > 
> > > > +with begin_global() guarantees than any erroneous read will cause the
> > > > +do_something_locked() function's first do_something() invocation to happen
> > > > +before begin_global() returns.  The combination of the smp_load_acquire()
> > > > +in do_something_locked() and the smp_store_release() in end_global()
> > > > +guarantees that either the do_something_locked() function's first
> > > > +do_something() invocation happens after the call to end_global() or that
> > > > +do_something_locked() acquires global_lock() and rechecks under the lock.
> > > This last sentence also makes no sense unless you imagine dropping
> > > global_lock between begin_global() and end_global().
> > 
> > ipc/sem.c does that and needs that, nf_conntrack doesn't use this.
> 
> Given all these issues, it seems like this patch needs to be re-written.

How about like this?

							Thanx, Paul

------------------------------------------------------------------------

Lock-Protected Writes With Heuristic Lockless Reads
---------------------------------------------------

For another example, suppose that the code can normally make use of
a per-data-structure lock, but there are times when a global lock
is required.  These times are indicated via a global flag.  The code
might look as follows, and is based loosely on nf_conntrack_lock(),
nf_conntrack_all_lock(), and nf_conntrack_all_unlock():

	bool global_flag;
	DEFINE_SPINLOCK(global_lock);
	struct foo {
		spinlock_t f_lock;
		int f_data;
	};

	/* All foo structures are in the following array. */
	int nfoo;
	struct foo *foo_array;

	void do_something_locked(struct foo *fp)
	{
		/* IMPORTANT: Heuristic plus spin_lock()! */
		if (!data_race(global_flag)) {
			spin_lock(&fp->f_lock);
			if (!smp_load_acquire(&global_flag)) {
				do_something(fp);
				spin_unlock(&fp->f_lock);
				return;
			}
			spin_unlock(&fp->f_lock);
		}
		spin_lock(&global_lock);
		/* global_lock held, thus global flag cannot be set. */
		spin_lock(&fp->f_lock);
		spin_unlock(&global_lock);
		/*
		 * global_flag might be set here, but begin_global()
		 * will wait for ->f_lock to be released.
		 */
		do_something(fp);
		spin_lock(&fp->f_lock);
}

	void begin_global(void)
	{
		int i;

		spin_lock(&global_lock);
		WRITE_ONCE(global_flag, true);
		for (i = 0; i < nfoo; i++) {
			/*
			 * Wait for pre-existing local locks.  One at
			 * a time to avoid lockdep limitations.
			 */
			spin_lock(&fp->f_lock);
			spin_unlock(&fp->f_lock);
		}
	}

	void end_global(void)
	{
		smp_store_release(&global_flag, false);
		spin_unlock(&global_lock);
	}

All code paths leading from the do_something_locked() function's first
read from global_flag acquire a lock, so endless load fusing cannot
happen.

If the value read from global_flag is true, then global_flag is
rechecked while holding ->f_lock, which, if global_flag is now false,
prevents begin_global() from completing.  It is therefore safe to invoke
do_something().

Otherwise, if either value read from global_flag is true, then after
global_lock is acquired global_flag must be false.  The acquisition of
->f_lock will prevent any call to begin_global() from returning, which
means that it is safe to release global_lock and invoke do_something().

For this to work, only those foo structures in foo_array[] may be passed
to do_something_locked().  The reason for this is that the synchronization
with begin_global() relies on momentarily holding the lock of each and
every foo structure.

Re: [PATCH memory-model 2/4] tools/memory-model: Add example for heuristic lockless reads

[Alan Stern]

On Fri, Jul 23, 2021 at 09:24:31AM -0700, Paul E. McKenney wrote:
> On Thu, Jul 22, 2021 at 10:08:46PM -0400, Alan Stern wrote:

> > > +	void do_something_locked(struct foo *fp)
> > > +	{
> > > +		bool gf = true;
> > > +
> > > +		/* IMPORTANT: Heuristic plus spin_lock()! */
> > > +		if (!data_race(global_flag)) {
> > > +			spin_lock(&fp->f_lock);
> > > +			if (!smp_load_acquire(&global_flag)) {

> > > +	void begin_global(void)
> > > +	{
> > > +		int i;
> > > +
> > > +		spin_lock(&global_lock);
> > > +		WRITE_ONCE(global_flag, true);
> > 
> > Why does this need to be WRITE_ONCE?  It still races with the first read 
> > of global_flag above.
> 
> But also with the smp_load_acquire() of global_flag, right?

What I'm curious about is why, given these two races, you notate one of 
them by changing a normal write to WRITE_ONCE and you notate the other 
by changing a normal read to a data_race() read.  Why not handle them 
both the same way?

Alan

Re: [PATCH memory-model 2/4] tools/memory-model: Add example for heuristic lockless reads

[Alan Stern]

On Fri, Jul 23, 2021 at 09:30:08AM -0700, Paul E. McKenney wrote:
> How about like this?
> 
> 							Thanx, Paul

Generally a lot better, but still at least one issue.

> ------------------------------------------------------------------------
> 
> Lock-Protected Writes With Heuristic Lockless Reads
> ---------------------------------------------------
> 
> For another example, suppose that the code can normally make use of
> a per-data-structure lock, but there are times when a global lock
> is required.  These times are indicated via a global flag.  The code
> might look as follows, and is based loosely on nf_conntrack_lock(),
> nf_conntrack_all_lock(), and nf_conntrack_all_unlock():
> 
> 	bool global_flag;
> 	DEFINE_SPINLOCK(global_lock);
> 	struct foo {
> 		spinlock_t f_lock;
> 		int f_data;
> 	};
> 
> 	/* All foo structures are in the following array. */
> 	int nfoo;
> 	struct foo *foo_array;
> 
> 	void do_something_locked(struct foo *fp)
> 	{
> 		/* IMPORTANT: Heuristic plus spin_lock()! */
> 		if (!data_race(global_flag)) {
> 			spin_lock(&fp->f_lock);
> 			if (!smp_load_acquire(&global_flag)) {
> 				do_something(fp);
> 				spin_unlock(&fp->f_lock);
> 				return;
> 			}
> 			spin_unlock(&fp->f_lock);
> 		}
> 		spin_lock(&global_lock);
> 		/* global_lock held, thus global flag cannot be set. */
> 		spin_lock(&fp->f_lock);
> 		spin_unlock(&global_lock);
> 		/*
> 		 * global_flag might be set here, but begin_global()
> 		 * will wait for ->f_lock to be released.
> 		 */
> 		do_something(fp);
> 		spin_lock(&fp->f_lock);

spin_unlock.

> }
> 
> 	void begin_global(void)
> 	{
> 		int i;
> 
> 		spin_lock(&global_lock);
> 		WRITE_ONCE(global_flag, true);
> 		for (i = 0; i < nfoo; i++) {
> 			/*
> 			 * Wait for pre-existing local locks.  One at
> 			 * a time to avoid lockdep limitations.
> 			 */
> 			spin_lock(&fp->f_lock);
> 			spin_unlock(&fp->f_lock);
> 		}
> 	}
> 
> 	void end_global(void)
> 	{
> 		smp_store_release(&global_flag, false);
> 		spin_unlock(&global_lock);
> 	}
> 
> All code paths leading from the do_something_locked() function's first
> read from global_flag acquire a lock, so endless load fusing cannot
> happen.
> 
> If the value read from global_flag is true, then global_flag is
> rechecked while holding ->f_lock, which, if global_flag is now false,
> prevents begin_global() from completing.  It is therefore safe to invoke
> do_something().
> 
> Otherwise, if either value read from global_flag is true, then after
> global_lock is acquired global_flag must be false.  The acquisition of
> ->f_lock will prevent any call to begin_global() from returning, which
> means that it is safe to release global_lock and invoke do_something().
> 
> For this to work, only those foo structures in foo_array[] may be passed
> to do_something_locked().  The reason for this is that the synchronization
> with begin_global() relies on momentarily holding the lock of each and
> every foo structure.

This doesn't mention the reason for the acquire-release
synchronization of global_flag.  It's needed because work done between
begin_global() and end_global() can affect a foo structure without
holding its private f_lock member, and we want all such work to be
visible to other threads when they call do_something_locked() later.

Alan

Re: [PATCH memory-model 2/4] tools/memory-model: Add example for heuristic lockless reads

[Paul E. McKenney]

On Fri, Jul 23, 2021 at 12:59:47PM -0400, Alan Stern wrote:
> On Fri, Jul 23, 2021 at 09:24:31AM -0700, Paul E. McKenney wrote:
> > On Thu, Jul 22, 2021 at 10:08:46PM -0400, Alan Stern wrote:
> 
> > > > +	void do_something_locked(struct foo *fp)
> > > > +	{
> > > > +		bool gf = true;
> > > > +
> > > > +		/* IMPORTANT: Heuristic plus spin_lock()! */
> > > > +		if (!data_race(global_flag)) {
> > > > +			spin_lock(&fp->f_lock);
> > > > +			if (!smp_load_acquire(&global_flag)) {
> 
> > > > +	void begin_global(void)
> > > > +	{
> > > > +		int i;
> > > > +
> > > > +		spin_lock(&global_lock);
> > > > +		WRITE_ONCE(global_flag, true);
> > > 
> > > Why does this need to be WRITE_ONCE?  It still races with the first read 
> > > of global_flag above.
> > 
> > But also with the smp_load_acquire() of global_flag, right?
> 
> What I'm curious about is why, given these two races, you notate one of 
> them by changing a normal write to WRITE_ONCE and you notate the other 
> by changing a normal read to a data_race() read.  Why not handle them 
> both the same way?

Because the code can tolerate the first read returning complete nonsense,
but needs the value from the second read to be exact at that point in
time.  (If the value changes immediately after being read, the fact that
->f_lock is held prevents begin_global() from completing.)

							Thanx, Paul

Re: [PATCH memory-model 2/4] tools/memory-model: Add example for heuristic lockless reads

[Alan Stern]

On Fri, Jul 23, 2021 at 10:30:10AM -0700, Paul E. McKenney wrote:
> On Fri, Jul 23, 2021 at 12:59:47PM -0400, Alan Stern wrote:
> > On Fri, Jul 23, 2021 at 09:24:31AM -0700, Paul E. McKenney wrote:
> > > On Thu, Jul 22, 2021 at 10:08:46PM -0400, Alan Stern wrote:
> > 
> > > > > +	void do_something_locked(struct foo *fp)
> > > > > +	{
> > > > > +		bool gf = true;
> > > > > +
> > > > > +		/* IMPORTANT: Heuristic plus spin_lock()! */
> > > > > +		if (!data_race(global_flag)) {
> > > > > +			spin_lock(&fp->f_lock);
> > > > > +			if (!smp_load_acquire(&global_flag)) {
> > 
> > > > > +	void begin_global(void)
> > > > > +	{
> > > > > +		int i;
> > > > > +
> > > > > +		spin_lock(&global_lock);
> > > > > +		WRITE_ONCE(global_flag, true);
> > > > 
> > > > Why does this need to be WRITE_ONCE?  It still races with the first read 
> > > > of global_flag above.
> > > 
> > > But also with the smp_load_acquire() of global_flag, right?
> > 
> > What I'm curious about is why, given these two races, you notate one of 
> > them by changing a normal write to WRITE_ONCE and you notate the other 
> > by changing a normal read to a data_race() read.  Why not handle them 
> > both the same way?
> 
> Because the code can tolerate the first read returning complete nonsense,
> but needs the value from the second read to be exact at that point in
> time.

In other words, if the second read races with the WRITE_ONCE, it needs to 
get either the value before the write or the value after the write; 
nothing else will do because it isn't a heuristic here.  Fair point.

>  (If the value changes immediately after being read, the fact that
> ->f_lock is held prevents begin_global() from completing.)

This seems like something worth explaining in the document.  That 
"IMPORTANT" comment doesn't really get the full point across.

Alan

Re: [PATCH memory-model 2/4] tools/memory-model: Add example for heuristic lockless reads

[Paul E. McKenney]

On Fri, Jul 23, 2021 at 02:11:38PM -0400, Alan Stern wrote:
> On Fri, Jul 23, 2021 at 10:30:10AM -0700, Paul E. McKenney wrote:
> > On Fri, Jul 23, 2021 at 12:59:47PM -0400, Alan Stern wrote:
> > > On Fri, Jul 23, 2021 at 09:24:31AM -0700, Paul E. McKenney wrote:
> > > > On Thu, Jul 22, 2021 at 10:08:46PM -0400, Alan Stern wrote:
> > > 
> > > > > > +	void do_something_locked(struct foo *fp)
> > > > > > +	{
> > > > > > +		bool gf = true;
> > > > > > +
> > > > > > +		/* IMPORTANT: Heuristic plus spin_lock()! */
> > > > > > +		if (!data_race(global_flag)) {
> > > > > > +			spin_lock(&fp->f_lock);
> > > > > > +			if (!smp_load_acquire(&global_flag)) {
> > > 
> > > > > > +	void begin_global(void)
> > > > > > +	{
> > > > > > +		int i;
> > > > > > +
> > > > > > +		spin_lock(&global_lock);
> > > > > > +		WRITE_ONCE(global_flag, true);
> > > > > 
> > > > > Why does this need to be WRITE_ONCE?  It still races with the first read 
> > > > > of global_flag above.
> > > > 
> > > > But also with the smp_load_acquire() of global_flag, right?
> > > 
> > > What I'm curious about is why, given these two races, you notate one of 
> > > them by changing a normal write to WRITE_ONCE and you notate the other 
> > > by changing a normal read to a data_race() read.  Why not handle them 
> > > both the same way?
> > 
> > Because the code can tolerate the first read returning complete nonsense,
> > but needs the value from the second read to be exact at that point in
> > time.
> 
> In other words, if the second read races with the WRITE_ONCE, it needs to 
> get either the value before the write or the value after the write; 
> nothing else will do because it isn't a heuristic here.  Fair point.
> 
> >  (If the value changes immediately after being read, the fact that
> > ->f_lock is held prevents begin_global() from completing.)
> 
> This seems like something worth explaining in the document.  That 
> "IMPORTANT" comment doesn't really get the full point across.

How about this comment instead?

	/* This works even if data_race() returns nonsense. */

							Thanx, Paul

Re: [PATCH memory-model 2/4] tools/memory-model: Add example for heuristic lockless reads

[Paul E. McKenney]

On Fri, Jul 23, 2021 at 01:08:20PM -0400, Alan Stern wrote:
> On Fri, Jul 23, 2021 at 09:30:08AM -0700, Paul E. McKenney wrote:
> > How about like this?
> > 
> > 							Thanx, Paul
> 
> Generally a lot better, but still at least one issue.
> 
> > ------------------------------------------------------------------------
> > 
> > Lock-Protected Writes With Heuristic Lockless Reads
> > ---------------------------------------------------
> > 
> > For another example, suppose that the code can normally make use of
> > a per-data-structure lock, but there are times when a global lock
> > is required.  These times are indicated via a global flag.  The code
> > might look as follows, and is based loosely on nf_conntrack_lock(),
> > nf_conntrack_all_lock(), and nf_conntrack_all_unlock():
> > 
> > 	bool global_flag;
> > 	DEFINE_SPINLOCK(global_lock);
> > 	struct foo {
> > 		spinlock_t f_lock;
> > 		int f_data;
> > 	};
> > 
> > 	/* All foo structures are in the following array. */
> > 	int nfoo;
> > 	struct foo *foo_array;
> > 
> > 	void do_something_locked(struct foo *fp)
> > 	{
> > 		/* IMPORTANT: Heuristic plus spin_lock()! */
> > 		if (!data_race(global_flag)) {
> > 			spin_lock(&fp->f_lock);
> > 			if (!smp_load_acquire(&global_flag)) {
> > 				do_something(fp);
> > 				spin_unlock(&fp->f_lock);
> > 				return;
> > 			}
> > 			spin_unlock(&fp->f_lock);
> > 		}
> > 		spin_lock(&global_lock);
> > 		/* global_lock held, thus global flag cannot be set. */
> > 		spin_lock(&fp->f_lock);
> > 		spin_unlock(&global_lock);
> > 		/*
> > 		 * global_flag might be set here, but begin_global()
> > 		 * will wait for ->f_lock to be released.
> > 		 */
> > 		do_something(fp);
> > 		spin_lock(&fp->f_lock);
> 
> spin_unlock.

Good eyes, fixed.

> > }
> > 
> > 	void begin_global(void)
> > 	{
> > 		int i;
> > 
> > 		spin_lock(&global_lock);
> > 		WRITE_ONCE(global_flag, true);
> > 		for (i = 0; i < nfoo; i++) {
> > 			/*
> > 			 * Wait for pre-existing local locks.  One at
> > 			 * a time to avoid lockdep limitations.
> > 			 */
> > 			spin_lock(&fp->f_lock);
> > 			spin_unlock(&fp->f_lock);
> > 		}
> > 	}
> > 
> > 	void end_global(void)
> > 	{
> > 		smp_store_release(&global_flag, false);
> > 		spin_unlock(&global_lock);
> > 	}
> > 
> > All code paths leading from the do_something_locked() function's first
> > read from global_flag acquire a lock, so endless load fusing cannot
> > happen.
> > 
> > If the value read from global_flag is true, then global_flag is
> > rechecked while holding ->f_lock, which, if global_flag is now false,
> > prevents begin_global() from completing.  It is therefore safe to invoke
> > do_something().
> > 
> > Otherwise, if either value read from global_flag is true, then after
> > global_lock is acquired global_flag must be false.  The acquisition of
> > ->f_lock will prevent any call to begin_global() from returning, which
> > means that it is safe to release global_lock and invoke do_something().
> > 
> > For this to work, only those foo structures in foo_array[] may be passed
> > to do_something_locked().  The reason for this is that the synchronization
> > with begin_global() relies on momentarily holding the lock of each and
> > every foo structure.
> 
> This doesn't mention the reason for the acquire-release
> synchronization of global_flag.  It's needed because work done between
> begin_global() and end_global() can affect a foo structure without
> holding its private f_lock member, and we want all such work to be
> visible to other threads when they call do_something_locked() later.

Like this added paragraph at the end?

	The smp_load_acquire() and smp_store_release() are required
	because changes to a foo structure between calls to begin_global()
	and end_global() are carried out without holding that structure's
	->f_lock.  The smp_load_acquire() and smp_store_release()
	ensure that the next invocation of do_something() from the call
	to do_something_locked() that acquires that ->f_lock will see
	those changes.

							Thanx, Paul

Re: [PATCH memory-model 2/4] tools/memory-model: Add example for heuristic lockless reads

[Alan Stern]

On Fri, Jul 23, 2021 at 01:28:11PM -0700, Paul E. McKenney wrote:
> On Fri, Jul 23, 2021 at 02:11:38PM -0400, Alan Stern wrote:
> > In other words, if the second read races with the WRITE_ONCE, it needs 
to
> > get either the value before the write or the value after the write;
> > nothing else will do because it isn't a heuristic here.  Fair point.
> >
> > >  (If the value changes immediately after being read, the fact that
> > > ->f_lock is held prevents begin_global() from completing.)
> >
> > This seems like something worth explaining in the document.  That
> > "IMPORTANT" comment doesn't really get the full point across.
>
> How about this comment instead?
>
>       /* This works even if data_race() returns nonsense. */

That's somewhat better.


On Fri, Jul 23, 2021 at 01:32:48PM -0700, Paul E. McKenney wrote:
> On Fri, Jul 23, 2021 at 01:08:20PM -0400, Alan Stern wrote:
> > This doesn't mention the reason for the acquire-release
> > synchronization of global_flag.  It's needed because work done between
> > begin_global() and end_global() can affect a foo structure without
> > holding its private f_lock member, and we want all such work to be
> > visible to other threads when they call do_something_locked() later.
> 
> Like this added paragraph at the end?
> 
> 	The smp_load_acquire() and smp_store_release() are required
> 	because changes to a foo structure between calls to begin_global()
> 	and end_global() are carried out without holding that structure's
> 	->f_lock.  The smp_load_acquire() and smp_store_release()
> 	ensure that the next invocation of do_something() from the call
> 	to do_something_locked() that acquires that ->f_lock will see
> 	those changes.

I'd shorten the last sentence:

	The smp_load_acquire() and smp_store_release() ensure that the
	next invocation of do_something() from do_something_locked()
	will see those changes.

Alan

Re: [PATCH memory-model 2/4] tools/memory-model: Add example for heuristic lockless reads

[Paul E. McKenney]

On Fri, Jul 23, 2021 at 05:03:47PM -0400, Alan Stern wrote:
> On Fri, Jul 23, 2021 at 01:28:11PM -0700, Paul E. McKenney wrote:
> > On Fri, Jul 23, 2021 at 02:11:38PM -0400, Alan Stern wrote:
> > > In other words, if the second read races with the WRITE_ONCE, it needs 
> to
> > > get either the value before the write or the value after the write;
> > > nothing else will do because it isn't a heuristic here.  Fair point.
> > >
> > > >  (If the value changes immediately after being read, the fact that
> > > > ->f_lock is held prevents begin_global() from completing.)
> > >
> > > This seems like something worth explaining in the document.  That
> > > "IMPORTANT" comment doesn't really get the full point across.
> >
> > How about this comment instead?
> >
> >       /* This works even if data_race() returns nonsense. */
> 
> That's somewhat better.
> 
> 
> On Fri, Jul 23, 2021 at 01:32:48PM -0700, Paul E. McKenney wrote:
> > On Fri, Jul 23, 2021 at 01:08:20PM -0400, Alan Stern wrote:
> > > This doesn't mention the reason for the acquire-release
> > > synchronization of global_flag.  It's needed because work done between
> > > begin_global() and end_global() can affect a foo structure without
> > > holding its private f_lock member, and we want all such work to be
> > > visible to other threads when they call do_something_locked() later.
> > 
> > Like this added paragraph at the end?
> > 
> > 	The smp_load_acquire() and smp_store_release() are required
> > 	because changes to a foo structure between calls to begin_global()
> > 	and end_global() are carried out without holding that structure's
> > 	->f_lock.  The smp_load_acquire() and smp_store_release()
> > 	ensure that the next invocation of do_something() from the call
> > 	to do_something_locked() that acquires that ->f_lock will see
> > 	those changes.
> 
> I'd shorten the last sentence:
> 
> 	The smp_load_acquire() and smp_store_release() ensure that the
> 	next invocation of do_something() from do_something_locked()
> 	will see those changes.

Sold!  ;-)

							Thanx, Paul

[PATCH v2 memory-model 2/4] tools/memory-model: Add example for heuristic lockless reads

[Paul E. McKenney]

This commit adds example code for heuristic lockless reads, based loosely
on the sem_lock() and sem_unlock() functions.

[ paulmck: Apply Alan Stern and Manfred Spraul feedback. ]

Reported-by: Manfred Spraul <manfred@colorfullife.com>
[ paulmck: Update per Manfred Spraul and Hillf Danton feedback. ]
Signed-off-by: Paul E. McKenney <paulmck@kernel.org>

diff --git a/tools/memory-model/Documentation/access-marking.txt b/tools/memory-model/Documentation/access-marking.txt
index 58bff26198767..d96fe20ed582a 100644
--- a/tools/memory-model/Documentation/access-marking.txt
+++ b/tools/memory-model/Documentation/access-marking.txt
@@ -319,6 +319,99 @@ of the ASSERT_EXCLUSIVE_WRITER() is to allow KCSAN to check for a buggy
 concurrent lockless write.
 
 
+Lock-Protected Writes With Heuristic Lockless Reads
+---------------------------------------------------
+
+For another example, suppose that the code can normally make use of
+a per-data-structure lock, but there are times when a global lock
+is required.  These times are indicated via a global flag.  The code
+might look as follows, and is based loosely on nf_conntrack_lock(),
+nf_conntrack_all_lock(), and nf_conntrack_all_unlock():
+
+	bool global_flag;
+	DEFINE_SPINLOCK(global_lock);
+	struct foo {
+		spinlock_t f_lock;
+		int f_data;
+	};
+
+	/* All foo structures are in the following array. */
+	int nfoo;
+	struct foo *foo_array;
+
+	void do_something_locked(struct foo *fp)
+	{
+		/* This works even if data_race() returns nonsense. */
+		if (!data_race(global_flag)) {
+			spin_lock(&fp->f_lock);
+			if (!smp_load_acquire(&global_flag)) {
+				do_something(fp);
+				spin_unlock(&fp->f_lock);
+				return;
+			}
+			spin_unlock(&fp->f_lock);
+		}
+		spin_lock(&global_lock);
+		/* global_lock held, thus global flag cannot be set. */
+		spin_lock(&fp->f_lock);
+		spin_unlock(&global_lock);
+		/*
+		 * global_flag might be set here, but begin_global()
+		 * will wait for ->f_lock to be released.
+		 */
+		do_something(fp);
+		spin_unlock(&fp->f_lock);
+	}
+
+	void begin_global(void)
+	{
+		int i;
+
+		spin_lock(&global_lock);
+		WRITE_ONCE(global_flag, true);
+		for (i = 0; i < nfoo; i++) {
+			/*
+			 * Wait for pre-existing local locks.  One at
+			 * a time to avoid lockdep limitations.
+			 */
+			spin_lock(&fp->f_lock);
+			spin_unlock(&fp->f_lock);
+		}
+	}
+
+	void end_global(void)
+	{
+		smp_store_release(&global_flag, false);
+		spin_unlock(&global_lock);
+	}
+
+All code paths leading from the do_something_locked() function's first
+read from global_flag acquire a lock, so endless load fusing cannot
+happen.
+
+If the value read from global_flag is true, then global_flag is
+rechecked while holding ->f_lock, which, if global_flag is now false,
+prevents begin_global() from completing.  It is therefore safe to invoke
+do_something().
+
+Otherwise, if either value read from global_flag is true, then after
+global_lock is acquired global_flag must be false.  The acquisition of
+->f_lock will prevent any call to begin_global() from returning, which
+means that it is safe to release global_lock and invoke do_something().
+
+For this to work, only those foo structures in foo_array[] may be passed
+to do_something_locked().  The reason for this is that the synchronization
+with begin_global() relies on momentarily holding the lock of each and
+every foo structure.
+
+The smp_load_acquire() and smp_store_release() are required because
+changes to a foo structure between calls to begin_global() and
+end_global() are carried out without holding that structure's ->f_lock.
+The smp_load_acquire() and smp_store_release() ensure that the next
+invocation of do_something() from do_something_locked() will see those
+changes.
+
+
 Lockless Reads and Writes
 -------------------------