Re: [QUESTION] Linux memory model: control dependency with bitfield

Re: [QUESTION] Linux memory model: control dependency with bitfield

[Paul E. McKenney]

On Mon, Jan 09, 2023 at 09:14:19AM -0800, Yang Shi wrote:
> Hi Paul,
> 
> Hope this email finds you are doing well. I recently ran into a
> problem which might be related to control dependency of the memory
> model. Conceptually, the code does (from copy_present_pte()):
> 
> acquire mmap_lock
> spin_lock
> ...
> clear bit (a bit in page flags)
> ...
> VM_BUG_ON(test bit)
> ...
> spin_unlock
> release mmap_lock
> 
> 
> IIUC there is control dependency between the "clear bit" and
> "VM_BUG_ON" since VM_BUG_ON simply tests the bit then raises the BUG.
> They do touch the overlapping address (the page flags from the same
> struct page), but they are bit field operations. Per the memory model
> documentation, the order is not guaranteed for bit field operations
> IIRC.
> 
> And there are not any implicit barriers between clear bit and test
> bit, so the question is whether an explicit barrier, for example,
> smp_mb__after_atomic() is required after clear bit to guarantee it
> works as expected?

I am not familiar with this code, so I will stick with LKMM
clarifications.

First, please don't forget any protection and ordering that might be
provided by the two locks held across this code.

Second, a control dependency extends from a READ_ONCE() or stronger
(clear_bit() included) to a later store.  Please note "store", not
"load".  If you need to order an earlier READ_ONCE() or clear_bit()
with a later load, you will need acquire semantics (smp_load_acquire(),
for example) or an explicit barrier such as smp_rmb().  Use of acquire
semantics almost always gets you code that is more readable.

Does that help?

Also CCing linux-mm@kvack.org in case someone with better understanding
of that code has advice.

							Thanx, Paul

Re: [QUESTION] Linux memory model: control dependency with bitfield

[Yang Shi]

On Mon, Jan 9, 2023 at 9:31 AM Paul E. McKenney <paulmck@kernel.org> wrote:
>
> On Mon, Jan 09, 2023 at 09:14:19AM -0800, Yang Shi wrote:
> > Hi Paul,
> >
> > Hope this email finds you are doing well. I recently ran into a
> > problem which might be related to control dependency of the memory
> > model. Conceptually, the code does (from copy_present_pte()):
> >
> > acquire mmap_lock
> > spin_lock
> > ...
> > clear bit (a bit in page flags)
> > ...
> > VM_BUG_ON(test bit)
> > ...
> > spin_unlock
> > release mmap_lock
> >
> >
> > IIUC there is control dependency between the "clear bit" and
> > "VM_BUG_ON" since VM_BUG_ON simply tests the bit then raises the BUG.
> > They do touch the overlapping address (the page flags from the same
> > struct page), but they are bit field operations. Per the memory model
> > documentation, the order is not guaranteed for bit field operations
> > IIRC.
> >
> > And there are not any implicit barriers between clear bit and test
> > bit, so the question is whether an explicit barrier, for example,
> > smp_mb__after_atomic() is required after clear bit to guarantee it
> > works as expected?
>
> I am not familiar with this code, so I will stick with LKMM
> clarifications.

Yeah, sure. This is why I tried to generalize the code.

>
> First, please don't forget any protection and ordering that might be
> provided by the two locks held across this code.

Yes, but for this case I just care about the code between clear bit
and VM_BUG_ON.

>
> Second, a control dependency extends from a READ_ONCE() or stronger
> (clear_bit() included) to a later store.  Please note "store", not
> "load".  If you need to order an earlier READ_ONCE() or clear_bit()

So you mean:

clear bit
...
if (test bit) {
    load_1
    store_1
    load_2
    store_2
}

The dependency reaches to the first store?

> with a later load, you will need acquire semantics (smp_load_acquire(),
> for example) or an explicit barrier such as smp_rmb().  Use of acquire
> semantics almost always gets you code that is more readable.

Does the load acquire have to pair with a smp_store_release()?
smp_mb__after_stomic() is not needed because it is too strong and the
weaker barrier is good enough, right?

>
> Does that help?

Yeah, sure. Thanks.

>
> Also CCing linux-mm@kvack.org in case someone with better understanding
> of that code has advice.
>
>                                                         Thanx, Paul

Re: [QUESTION] Linux memory model: control dependency with bitfield

[Paul E. McKenney]

On Mon, Jan 09, 2023 at 02:08:35PM -0800, Yang Shi wrote:
> On Mon, Jan 9, 2023 at 9:31 AM Paul E. McKenney <paulmck@kernel.org> wrote:
> >
> > On Mon, Jan 09, 2023 at 09:14:19AM -0800, Yang Shi wrote:
> > > Hi Paul,
> > >
> > > Hope this email finds you are doing well. I recently ran into a
> > > problem which might be related to control dependency of the memory
> > > model. Conceptually, the code does (from copy_present_pte()):
> > >
> > > acquire mmap_lock
> > > spin_lock
> > > ...
> > > clear bit (a bit in page flags)
> > > ...
> > > VM_BUG_ON(test bit)
> > > ...
> > > spin_unlock
> > > release mmap_lock
> > >
> > >
> > > IIUC there is control dependency between the "clear bit" and
> > > "VM_BUG_ON" since VM_BUG_ON simply tests the bit then raises the BUG.
> > > They do touch the overlapping address (the page flags from the same
> > > struct page), but they are bit field operations. Per the memory model
> > > documentation, the order is not guaranteed for bit field operations
> > > IIRC.
> > >
> > > And there are not any implicit barriers between clear bit and test
> > > bit, so the question is whether an explicit barrier, for example,
> > > smp_mb__after_atomic() is required after clear bit to guarantee it
> > > works as expected?
> >
> > I am not familiar with this code, so I will stick with LKMM
> > clarifications.
> 
> Yeah, sure. This is why I tried to generalize the code.
> 
> > First, please don't forget any protection and ordering that might be
> > provided by the two locks held across this code.
> 
> Yes, but for this case I just care about the code between clear bit
> and VM_BUG_ON.

Fair enough!

> > Second, a control dependency extends from a READ_ONCE() or stronger
> > (clear_bit() included) to a later store.  Please note "store", not
> > "load".  If you need to order an earlier READ_ONCE() or clear_bit()
> 
> So you mean:
> 
> clear bit
> ...
> if (test bit) {
>     load_1
>     store_1
>     load_2
>     store_2
> }
> 
> The dependency reaches to the first store?

It reaches both stores, but neither load.

That means that your example might well execute as if it had instead
been written as follows:

	load_1
	load_2
	if (test bit) {
		store_1
		store_2
	}

Assuming that you mean the test_bit() function.  If you instead mean
a C-language statement that tests a bit, then the compiler can do all
sorts of things to you.  The compiler can also do interesting things
to you if the stores are plain C-language stores instead of something
like WRITE_ONCE().

> > with a later load, you will need acquire semantics (smp_load_acquire(),
> > for example) or an explicit barrier such as smp_rmb().  Use of acquire
> > semantics almost always gets you code that is more readable.
> 
> Does the load acquire have to pair with a smp_store_release()?
> smp_mb__after_stomic() is not needed because it is too strong and the
> weaker barrier is good enough, right?

It needs to pair with some type of applicable ordering, but yes,
smp_store_release() is a good one.

							Thanx, Paul

> > Does that help?
> 
> Yeah, sure. Thanks.
> 
> >
> > Also CCing linux-mm@kvack.org in case someone with better understanding
> > of that code has advice.
> >
> >                                                         Thanx, Paul

Re: [QUESTION] Linux memory model: control dependency with bitfield

[Yang Shi]

On Mon, Jan 9, 2023 at 3:11 PM Paul E. McKenney <paulmck@kernel.org> wrote:
>
> On Mon, Jan 09, 2023 at 02:08:35PM -0800, Yang Shi wrote:
> > On Mon, Jan 9, 2023 at 9:31 AM Paul E. McKenney <paulmck@kernel.org> wrote:
> > >
> > > On Mon, Jan 09, 2023 at 09:14:19AM -0800, Yang Shi wrote:
> > > > Hi Paul,
> > > >
> > > > Hope this email finds you are doing well. I recently ran into a
> > > > problem which might be related to control dependency of the memory
> > > > model. Conceptually, the code does (from copy_present_pte()):
> > > >
> > > > acquire mmap_lock
> > > > spin_lock
> > > > ...
> > > > clear bit (a bit in page flags)
> > > > ...
> > > > VM_BUG_ON(test bit)
> > > > ...
> > > > spin_unlock
> > > > release mmap_lock
> > > >
> > > >
> > > > IIUC there is control dependency between the "clear bit" and
> > > > "VM_BUG_ON" since VM_BUG_ON simply tests the bit then raises the BUG.
> > > > They do touch the overlapping address (the page flags from the same
> > > > struct page), but they are bit field operations. Per the memory model
> > > > documentation, the order is not guaranteed for bit field operations
> > > > IIRC.
> > > >
> > > > And there are not any implicit barriers between clear bit and test
> > > > bit, so the question is whether an explicit barrier, for example,
> > > > smp_mb__after_atomic() is required after clear bit to guarantee it
> > > > works as expected?
> > >
> > > I am not familiar with this code, so I will stick with LKMM
> > > clarifications.
> >
> > Yeah, sure. This is why I tried to generalize the code.
> >
> > > First, please don't forget any protection and ordering that might be
> > > provided by the two locks held across this code.
> >
> > Yes, but for this case I just care about the code between clear bit
> > and VM_BUG_ON.
>
> Fair enough!
>
> > > Second, a control dependency extends from a READ_ONCE() or stronger
> > > (clear_bit() included) to a later store.  Please note "store", not
> > > "load".  If you need to order an earlier READ_ONCE() or clear_bit()
> >
> > So you mean:
> >
> > clear bit
> > ...
> > if (test bit) {
> >     load_1
> >     store_1
> >     load_2
> >     store_2
> > }
> >
> > The dependency reaches to the first store?
>
> It reaches both stores, but neither load.
>
> That means that your example might well execute as if it had instead
> been written as follows:
>
>         load_1
>         load_2
>         if (test bit) {
>                 store_1
>                 store_2
>         }
>
> Assuming that you mean the test_bit() function.  If you instead mean
> a C-language statement that tests a bit, then the compiler can do all
> sorts of things to you.  The compiler can also do interesting things
> to you if the stores are plain C-language stores instead of something
> like WRITE_ONCE().

It is a test_bit() function. Is it possible clear_bit() is reordered
with test_bit(), or test_bit() doesn't see the result from
clear_bit()?

>
> > > with a later load, you will need acquire semantics (smp_load_acquire(),
> > > for example) or an explicit barrier such as smp_rmb().  Use of acquire
> > > semantics almost always gets you code that is more readable.
> >
> > Does the load acquire have to pair with a smp_store_release()?
> > smp_mb__after_stomic() is not needed because it is too strong and the
> > weaker barrier is good enough, right?
>
> It needs to pair with some type of applicable ordering, but yes,
> smp_store_release() is a good one.

So, it should look like IIUC:

clear_bit()
smp_load_acquire()
...
if (test_bit()) {
    smp_store_release()
    load_1
    store_1
    load_2
    store_2
}

>
>                                                         Thanx, Paul
>
> > > Does that help?
> >
> > Yeah, sure. Thanks.
> >
> > >
> > > Also CCing linux-mm@kvack.org in case someone with better understanding
> > > of that code has advice.
> > >
> > >                                                         Thanx, Paul

Re: [QUESTION] Linux memory model: control dependency with bitfield

[Paul E. McKenney]

On Mon, Jan 09, 2023 at 03:44:54PM -0800, Yang Shi wrote:
> On Mon, Jan 9, 2023 at 3:11 PM Paul E. McKenney <paulmck@kernel.org> wrote:
> > On Mon, Jan 09, 2023 at 02:08:35PM -0800, Yang Shi wrote:
> > > On Mon, Jan 9, 2023 at 9:31 AM Paul E. McKenney <paulmck@kernel.org> wrote:
> > > > On Mon, Jan 09, 2023 at 09:14:19AM -0800, Yang Shi wrote:
> > > > > Hi Paul,
> > > > >
> > > > > Hope this email finds you are doing well. I recently ran into a
> > > > > problem which might be related to control dependency of the memory
> > > > > model. Conceptually, the code does (from copy_present_pte()):
> > > > >
> > > > > acquire mmap_lock
> > > > > spin_lock
> > > > > ...
> > > > > clear bit (a bit in page flags)
> > > > > ...
> > > > > VM_BUG_ON(test bit)
> > > > > ...
> > > > > spin_unlock
> > > > > release mmap_lock
> > > > >
> > > > >
> > > > > IIUC there is control dependency between the "clear bit" and
> > > > > "VM_BUG_ON" since VM_BUG_ON simply tests the bit then raises the BUG.
> > > > > They do touch the overlapping address (the page flags from the same
> > > > > struct page), but they are bit field operations. Per the memory model
> > > > > documentation, the order is not guaranteed for bit field operations
> > > > > IIRC.
> > > > >
> > > > > And there are not any implicit barriers between clear bit and test
> > > > > bit, so the question is whether an explicit barrier, for example,
> > > > > smp_mb__after_atomic() is required after clear bit to guarantee it
> > > > > works as expected?
> > > >
> > > > I am not familiar with this code, so I will stick with LKMM
> > > > clarifications.
> > >
> > > Yeah, sure. This is why I tried to generalize the code.
> > >
> > > > First, please don't forget any protection and ordering that might be
> > > > provided by the two locks held across this code.
> > >
> > > Yes, but for this case I just care about the code between clear bit
> > > and VM_BUG_ON.
> >
> > Fair enough!
> >
> > > > Second, a control dependency extends from a READ_ONCE() or stronger
> > > > (clear_bit() included) to a later store.  Please note "store", not
> > > > "load".  If you need to order an earlier READ_ONCE() or clear_bit()
> > >
> > > So you mean:
> > >
> > > clear bit
> > > ...
> > > if (test bit) {
> > >     load_1
> > >     store_1
> > >     load_2
> > >     store_2
> > > }
> > >
> > > The dependency reaches to the first store?
> >
> > It reaches both stores, but neither load.
> >
> > That means that your example might well execute as if it had instead
> > been written as follows:
> >
> >         load_1
> >         load_2
> >         if (test bit) {
> >                 store_1
> >                 store_2
> >         }
> >
> > Assuming that you mean the test_bit() function.  If you instead mean
> > a C-language statement that tests a bit, then the compiler can do all
> > sorts of things to you.  The compiler can also do interesting things
> > to you if the stores are plain C-language stores instead of something
> > like WRITE_ONCE().
> 
> It is a test_bit() function. Is it possible clear_bit() is reordered
> with test_bit(), or test_bit() doesn't see the result from
> clear_bit()?

If the various calls to test_bit() and clear_bit() are to the same
location, then they will not be reordered with each other.

If they are to different locations, they can be reordered.  But in that
case, they would not see each others' results anyway.

> > > > with a later load, you will need acquire semantics (smp_load_acquire(),
> > > > for example) or an explicit barrier such as smp_rmb().  Use of acquire
> > > > semantics almost always gets you code that is more readable.
> > >
> > > Does the load acquire have to pair with a smp_store_release()?
> > > smp_mb__after_stomic() is not needed because it is too strong and the
> > > weaker barrier is good enough, right?
> >
> > It needs to pair with some type of applicable ordering, but yes,
> > smp_store_release() is a good one.
> 
> So, it should look like IIUC:
> 
> clear_bit()
> smp_load_acquire()
> ...
> if (test_bit()) {
>     smp_store_release()
>     load_1
>     store_1
>     load_2
>     store_2
> }

Just so you know, smp_load_acquire() does a load and smp_store_release()
does a store.

Also, is this code executed by a single CPU/task?  If so, you need to
also consider the corresponding code executed by some other CPU/task.


                                                        Thanx, Paul

> > > > Does that help?
> > >
> > > Yeah, sure. Thanks.
> > >
> > > >
> > > > Also CCing linux-mm@kvack.org in case someone with better understanding
> > > > of that code has advice.
> > > >
> > > >                                                         Thanx, Paul

Re: [QUESTION] Linux memory model: control dependency with bitfield

[Yang Shi]

On Mon, Jan 9, 2023 at 4:04 PM Paul E. McKenney <paulmck@kernel.org> wrote:
>
> On Mon, Jan 09, 2023 at 03:44:54PM -0800, Yang Shi wrote:
> > On Mon, Jan 9, 2023 at 3:11 PM Paul E. McKenney <paulmck@kernel.org> wrote:
> > > On Mon, Jan 09, 2023 at 02:08:35PM -0800, Yang Shi wrote:
> > > > On Mon, Jan 9, 2023 at 9:31 AM Paul E. McKenney <paulmck@kernel.org> wrote:
> > > > > On Mon, Jan 09, 2023 at 09:14:19AM -0800, Yang Shi wrote:
> > > > > > Hi Paul,
> > > > > >
> > > > > > Hope this email finds you are doing well. I recently ran into a
> > > > > > problem which might be related to control dependency of the memory
> > > > > > model. Conceptually, the code does (from copy_present_pte()):
> > > > > >
> > > > > > acquire mmap_lock
> > > > > > spin_lock
> > > > > > ...
> > > > > > clear bit (a bit in page flags)
> > > > > > ...
> > > > > > VM_BUG_ON(test bit)
> > > > > > ...
> > > > > > spin_unlock
> > > > > > release mmap_lock
> > > > > >
> > > > > >
> > > > > > IIUC there is control dependency between the "clear bit" and
> > > > > > "VM_BUG_ON" since VM_BUG_ON simply tests the bit then raises the BUG.
> > > > > > They do touch the overlapping address (the page flags from the same
> > > > > > struct page), but they are bit field operations. Per the memory model
> > > > > > documentation, the order is not guaranteed for bit field operations
> > > > > > IIRC.
> > > > > >
> > > > > > And there are not any implicit barriers between clear bit and test
> > > > > > bit, so the question is whether an explicit barrier, for example,
> > > > > > smp_mb__after_atomic() is required after clear bit to guarantee it
> > > > > > works as expected?
> > > > >
> > > > > I am not familiar with this code, so I will stick with LKMM
> > > > > clarifications.
> > > >
> > > > Yeah, sure. This is why I tried to generalize the code.
> > > >
> > > > > First, please don't forget any protection and ordering that might be
> > > > > provided by the two locks held across this code.
> > > >
> > > > Yes, but for this case I just care about the code between clear bit
> > > > and VM_BUG_ON.
> > >
> > > Fair enough!
> > >
> > > > > Second, a control dependency extends from a READ_ONCE() or stronger
> > > > > (clear_bit() included) to a later store.  Please note "store", not
> > > > > "load".  If you need to order an earlier READ_ONCE() or clear_bit()
> > > >
> > > > So you mean:
> > > >
> > > > clear bit
> > > > ...
> > > > if (test bit) {
> > > >     load_1
> > > >     store_1
> > > >     load_2
> > > >     store_2
> > > > }
> > > >
> > > > The dependency reaches to the first store?
> > >
> > > It reaches both stores, but neither load.
> > >
> > > That means that your example might well execute as if it had instead
> > > been written as follows:
> > >
> > >         load_1
> > >         load_2
> > >         if (test bit) {
> > >                 store_1
> > >                 store_2
> > >         }
> > >
> > > Assuming that you mean the test_bit() function.  If you instead mean
> > > a C-language statement that tests a bit, then the compiler can do all
> > > sorts of things to you.  The compiler can also do interesting things
> > > to you if the stores are plain C-language stores instead of something
> > > like WRITE_ONCE().
> >
> > It is a test_bit() function. Is it possible clear_bit() is reordered
> > with test_bit(), or test_bit() doesn't see the result from
> > clear_bit()?
>
> If the various calls to test_bit() and clear_bit() are to the same
> location, then they will not be reordered with each other.
>
> If they are to different locations, they can be reordered.  But in that
> case, they would not see each others' results anyway.

Yeah, make sense.

>
> > > > > with a later load, you will need acquire semantics (smp_load_acquire(),
> > > > > for example) or an explicit barrier such as smp_rmb().  Use of acquire
> > > > > semantics almost always gets you code that is more readable.
> > > >
> > > > Does the load acquire have to pair with a smp_store_release()?
> > > > smp_mb__after_stomic() is not needed because it is too strong and the
> > > > weaker barrier is good enough, right?
> > >
> > > It needs to pair with some type of applicable ordering, but yes,
> > > smp_store_release() is a good one.
> >
> > So, it should look like IIUC:
> >
> > clear_bit()
> > smp_load_acquire()
> > ...
> > if (test_bit()) {
> >     smp_store_release()
> >     load_1
> >     store_1
> >     load_2
> >     store_2
> > }
>
> Just so you know, smp_load_acquire() does a load and smp_store_release()
> does a store.
>
> Also, is this code executed by a single CPU/task?  If so, you need to
> also consider the corresponding code executed by some other CPU/task.

The code could be executed by multiple tasks in parallel.

>
>
>                                                         Thanx, Paul
>
> > > > > Does that help?
> > > >
> > > > Yeah, sure. Thanks.
> > > >
> > > > >
> > > > > Also CCing linux-mm@kvack.org in case someone with better understanding
> > > > > of that code has advice.
> > > > >
> > > > >                                                         Thanx, Paul

Re: [QUESTION] Linux memory model: control dependency with bitfield

[Paul E. McKenney]

On Wed, Jan 11, 2023 at 04:01:34PM -0800, Yang Shi wrote:
> On Mon, Jan 9, 2023 at 4:04 PM Paul E. McKenney <paulmck@kernel.org> wrote:
> >
> > On Mon, Jan 09, 2023 at 03:44:54PM -0800, Yang Shi wrote:
> > > On Mon, Jan 9, 2023 at 3:11 PM Paul E. McKenney <paulmck@kernel.org> wrote:
> > > > On Mon, Jan 09, 2023 at 02:08:35PM -0800, Yang Shi wrote:
> > > > > On Mon, Jan 9, 2023 at 9:31 AM Paul E. McKenney <paulmck@kernel.org> wrote:
> > > > > > On Mon, Jan 09, 2023 at 09:14:19AM -0800, Yang Shi wrote:
> > > > > > > Hi Paul,
> > > > > > >
> > > > > > > Hope this email finds you are doing well. I recently ran into a
> > > > > > > problem which might be related to control dependency of the memory
> > > > > > > model. Conceptually, the code does (from copy_present_pte()):
> > > > > > >
> > > > > > > acquire mmap_lock
> > > > > > > spin_lock
> > > > > > > ...
> > > > > > > clear bit (a bit in page flags)
> > > > > > > ...
> > > > > > > VM_BUG_ON(test bit)
> > > > > > > ...
> > > > > > > spin_unlock
> > > > > > > release mmap_lock
> > > > > > >
> > > > > > >
> > > > > > > IIUC there is control dependency between the "clear bit" and
> > > > > > > "VM_BUG_ON" since VM_BUG_ON simply tests the bit then raises the BUG.
> > > > > > > They do touch the overlapping address (the page flags from the same
> > > > > > > struct page), but they are bit field operations. Per the memory model
> > > > > > > documentation, the order is not guaranteed for bit field operations
> > > > > > > IIRC.
> > > > > > >
> > > > > > > And there are not any implicit barriers between clear bit and test
> > > > > > > bit, so the question is whether an explicit barrier, for example,
> > > > > > > smp_mb__after_atomic() is required after clear bit to guarantee it
> > > > > > > works as expected?
> > > > > >
> > > > > > I am not familiar with this code, so I will stick with LKMM
> > > > > > clarifications.
> > > > >
> > > > > Yeah, sure. This is why I tried to generalize the code.
> > > > >
> > > > > > First, please don't forget any protection and ordering that might be
> > > > > > provided by the two locks held across this code.
> > > > >
> > > > > Yes, but for this case I just care about the code between clear bit
> > > > > and VM_BUG_ON.
> > > >
> > > > Fair enough!
> > > >
> > > > > > Second, a control dependency extends from a READ_ONCE() or stronger
> > > > > > (clear_bit() included) to a later store.  Please note "store", not
> > > > > > "load".  If you need to order an earlier READ_ONCE() or clear_bit()
> > > > >
> > > > > So you mean:
> > > > >
> > > > > clear bit
> > > > > ...
> > > > > if (test bit) {
> > > > >     load_1
> > > > >     store_1
> > > > >     load_2
> > > > >     store_2
> > > > > }
> > > > >
> > > > > The dependency reaches to the first store?
> > > >
> > > > It reaches both stores, but neither load.
> > > >
> > > > That means that your example might well execute as if it had instead
> > > > been written as follows:
> > > >
> > > >         load_1
> > > >         load_2
> > > >         if (test bit) {
> > > >                 store_1
> > > >                 store_2
> > > >         }
> > > >
> > > > Assuming that you mean the test_bit() function.  If you instead mean
> > > > a C-language statement that tests a bit, then the compiler can do all
> > > > sorts of things to you.  The compiler can also do interesting things
> > > > to you if the stores are plain C-language stores instead of something
> > > > like WRITE_ONCE().
> > >
> > > It is a test_bit() function. Is it possible clear_bit() is reordered
> > > with test_bit(), or test_bit() doesn't see the result from
> > > clear_bit()?
> >
> > If the various calls to test_bit() and clear_bit() are to the same
> > location, then they will not be reordered with each other.
> >
> > If they are to different locations, they can be reordered.  But in that
> > case, they would not see each others' results anyway.
> 
> Yeah, make sense.
> 
> >
> > > > > > with a later load, you will need acquire semantics (smp_load_acquire(),
> > > > > > for example) or an explicit barrier such as smp_rmb().  Use of acquire
> > > > > > semantics almost always gets you code that is more readable.
> > > > >
> > > > > Does the load acquire have to pair with a smp_store_release()?
> > > > > smp_mb__after_stomic() is not needed because it is too strong and the
> > > > > weaker barrier is good enough, right?
> > > >
> > > > It needs to pair with some type of applicable ordering, but yes,
> > > > smp_store_release() is a good one.
> > >
> > > So, it should look like IIUC:
> > >
> > > clear_bit()
> > > smp_load_acquire()
> > > ...
> > > if (test_bit()) {
> > >     smp_store_release()
> > >     load_1
> > >     store_1
> > >     load_2
> > >     store_2
> > > }
> >
> > Just so you know, smp_load_acquire() does a load and smp_store_release()
> > does a store.
> >
> > Also, is this code executed by a single CPU/task?  If so, you need to
> > also consider the corresponding code executed by some other CPU/task.
> 
> The code could be executed by multiple tasks in parallel.

It is hard for me to tell you what to write without more information
about what you do and do not want to happen, but here is one possibility:

clear_bit(5, &my_bits);
if (test_bit_acquire(5, &my_bits)) {
	r1 = READ_ONCE(a);
	WRITE_ONCE(b, 1729);
	r2 = READ_ONCE(c);
	WRITE_ONCE(d, 65535);
}

This is of course a bit nonsensical because something somewhere would
need to set bit 5 in my_bits for the body of the "if" statement to ever
be executed.  I am assuming that this happens somewhere else.

The clear_bit() would be ordered before the test_bit_acquire() due to
their both accessing the same location.  The test_bit_acquire() would
be orderd before the body of that "if" statement due to the _acquire()
suffix.

Is that what you are looking for?  If not, what are you looking for?

                                                        Thanx, Paul

> > > > > > Does that help?
> > > > >
> > > > > Yeah, sure. Thanks.
> > > > >
> > > > > >
> > > > > > Also CCing linux-mm@kvack.org in case someone with better understanding
> > > > > > of that code has advice.
> > > > > >
> > > > > >                                                         Thanx, Paul

Re: [QUESTION] Linux memory model: control dependency with bitfield

[Yang Shi]

On Wed, Jan 11, 2023 at 4:15 PM Paul E. McKenney <paulmck@kernel.org> wrote:
>
> On Wed, Jan 11, 2023 at 04:01:34PM -0800, Yang Shi wrote:
> > On Mon, Jan 9, 2023 at 4:04 PM Paul E. McKenney <paulmck@kernel.org> wrote:
> > >
> > > On Mon, Jan 09, 2023 at 03:44:54PM -0800, Yang Shi wrote:
> > > > On Mon, Jan 9, 2023 at 3:11 PM Paul E. McKenney <paulmck@kernel.org> wrote:
> > > > > On Mon, Jan 09, 2023 at 02:08:35PM -0800, Yang Shi wrote:
> > > > > > On Mon, Jan 9, 2023 at 9:31 AM Paul E. McKenney <paulmck@kernel.org> wrote:
> > > > > > > On Mon, Jan 09, 2023 at 09:14:19AM -0800, Yang Shi wrote:
> > > > > > > > Hi Paul,
> > > > > > > >
> > > > > > > > Hope this email finds you are doing well. I recently ran into a
> > > > > > > > problem which might be related to control dependency of the memory
> > > > > > > > model. Conceptually, the code does (from copy_present_pte()):
> > > > > > > >
> > > > > > > > acquire mmap_lock
> > > > > > > > spin_lock
> > > > > > > > ...
> > > > > > > > clear bit (a bit in page flags)
> > > > > > > > ...
> > > > > > > > VM_BUG_ON(test bit)
> > > > > > > > ...
> > > > > > > > spin_unlock
> > > > > > > > release mmap_lock
> > > > > > > >
> > > > > > > >
> > > > > > > > IIUC there is control dependency between the "clear bit" and
> > > > > > > > "VM_BUG_ON" since VM_BUG_ON simply tests the bit then raises the BUG.
> > > > > > > > They do touch the overlapping address (the page flags from the same
> > > > > > > > struct page), but they are bit field operations. Per the memory model
> > > > > > > > documentation, the order is not guaranteed for bit field operations
> > > > > > > > IIRC.
> > > > > > > >
> > > > > > > > And there are not any implicit barriers between clear bit and test
> > > > > > > > bit, so the question is whether an explicit barrier, for example,
> > > > > > > > smp_mb__after_atomic() is required after clear bit to guarantee it
> > > > > > > > works as expected?
> > > > > > >
> > > > > > > I am not familiar with this code, so I will stick with LKMM
> > > > > > > clarifications.
> > > > > >
> > > > > > Yeah, sure. This is why I tried to generalize the code.
> > > > > >
> > > > > > > First, please don't forget any protection and ordering that might be
> > > > > > > provided by the two locks held across this code.
> > > > > >
> > > > > > Yes, but for this case I just care about the code between clear bit
> > > > > > and VM_BUG_ON.
> > > > >
> > > > > Fair enough!
> > > > >
> > > > > > > Second, a control dependency extends from a READ_ONCE() or stronger
> > > > > > > (clear_bit() included) to a later store.  Please note "store", not
> > > > > > > "load".  If you need to order an earlier READ_ONCE() or clear_bit()
> > > > > >
> > > > > > So you mean:
> > > > > >
> > > > > > clear bit
> > > > > > ...
> > > > > > if (test bit) {
> > > > > >     load_1
> > > > > >     store_1
> > > > > >     load_2
> > > > > >     store_2
> > > > > > }
> > > > > >
> > > > > > The dependency reaches to the first store?
> > > > >
> > > > > It reaches both stores, but neither load.
> > > > >
> > > > > That means that your example might well execute as if it had instead
> > > > > been written as follows:
> > > > >
> > > > >         load_1
> > > > >         load_2
> > > > >         if (test bit) {
> > > > >                 store_1
> > > > >                 store_2
> > > > >         }
> > > > >
> > > > > Assuming that you mean the test_bit() function.  If you instead mean
> > > > > a C-language statement that tests a bit, then the compiler can do all
> > > > > sorts of things to you.  The compiler can also do interesting things
> > > > > to you if the stores are plain C-language stores instead of something
> > > > > like WRITE_ONCE().
> > > >
> > > > It is a test_bit() function. Is it possible clear_bit() is reordered
> > > > with test_bit(), or test_bit() doesn't see the result from
> > > > clear_bit()?
> > >
> > > If the various calls to test_bit() and clear_bit() are to the same
> > > location, then they will not be reordered with each other.
> > >
> > > If they are to different locations, they can be reordered.  But in that
> > > case, they would not see each others' results anyway.
> >
> > Yeah, make sense.
> >
> > >
> > > > > > > with a later load, you will need acquire semantics (smp_load_acquire(),
> > > > > > > for example) or an explicit barrier such as smp_rmb().  Use of acquire
> > > > > > > semantics almost always gets you code that is more readable.
> > > > > >
> > > > > > Does the load acquire have to pair with a smp_store_release()?
> > > > > > smp_mb__after_stomic() is not needed because it is too strong and the
> > > > > > weaker barrier is good enough, right?
> > > > >
> > > > > It needs to pair with some type of applicable ordering, but yes,
> > > > > smp_store_release() is a good one.
> > > >
> > > > So, it should look like IIUC:
> > > >
> > > > clear_bit()
> > > > smp_load_acquire()
> > > > ...
> > > > if (test_bit()) {
> > > >     smp_store_release()
> > > >     load_1
> > > >     store_1
> > > >     load_2
> > > >     store_2
> > > > }
> > >
> > > Just so you know, smp_load_acquire() does a load and smp_store_release()
> > > does a store.
> > >
> > > Also, is this code executed by a single CPU/task?  If so, you need to
> > > also consider the corresponding code executed by some other CPU/task.
> >
> > The code could be executed by multiple tasks in parallel.
>
> It is hard for me to tell you what to write without more information
> about what you do and do not want to happen, but here is one possibility:
>
> clear_bit(5, &my_bits);
> if (test_bit_acquire(5, &my_bits)) {
>         r1 = READ_ONCE(a);
>         WRITE_ONCE(b, 1729);
>         r2 = READ_ONCE(c);
>         WRITE_ONCE(d, 65535);
> }
>
> This is of course a bit nonsensical because something somewhere would
> need to set bit 5 in my_bits for the body of the "if" statement to ever
> be executed.  I am assuming that this happens somewhere else.
>
> The clear_bit() would be ordered before the test_bit_acquire() due to
> their both accessing the same location.  The test_bit_acquire() would
> be orderd before the body of that "if" statement due to the _acquire()
> suffix.
>
> Is that what you are looking for?  If not, what are you looking for?

Sorry for the late reply. I think the _acquire() should be something
I'm looking for. I just figured out a stable reproducer for my
problem, so I will collect more debug information and try some debug
patch with _acquire(). Hopefully I could get more clear picture next
week.

Thanks a lot.

>
>                                                         Thanx, Paul
>
> > > > > > > Does that help?
> > > > > >
> > > > > > Yeah, sure. Thanks.
> > > > > >
> > > > > > >
> > > > > > > Also CCing linux-mm@kvack.org in case someone with better understanding
> > > > > > > of that code has advice.
> > > > > > >
> > > > > > >                                                         Thanx, Paul

Re: [QUESTION] Linux memory model: control dependency with bitfield

[Paul E. McKenney]

On Fri, Jan 13, 2023 at 06:37:42PM -0800, Yang Shi wrote:
> On Wed, Jan 11, 2023 at 4:15 PM Paul E. McKenney <paulmck@kernel.org> wrote:
> >
> > On Wed, Jan 11, 2023 at 04:01:34PM -0800, Yang Shi wrote:
> > > On Mon, Jan 9, 2023 at 4:04 PM Paul E. McKenney <paulmck@kernel.org> wrote:
> > > >
> > > > On Mon, Jan 09, 2023 at 03:44:54PM -0800, Yang Shi wrote:
> > > > > On Mon, Jan 9, 2023 at 3:11 PM Paul E. McKenney <paulmck@kernel.org> wrote:
> > > > > > On Mon, Jan 09, 2023 at 02:08:35PM -0800, Yang Shi wrote:
> > > > > > > On Mon, Jan 9, 2023 at 9:31 AM Paul E. McKenney <paulmck@kernel.org> wrote:
> > > > > > > > On Mon, Jan 09, 2023 at 09:14:19AM -0800, Yang Shi wrote:
> > > > > > > > > Hi Paul,
> > > > > > > > >
> > > > > > > > > Hope this email finds you are doing well. I recently ran into a
> > > > > > > > > problem which might be related to control dependency of the memory
> > > > > > > > > model. Conceptually, the code does (from copy_present_pte()):
> > > > > > > > >
> > > > > > > > > acquire mmap_lock
> > > > > > > > > spin_lock
> > > > > > > > > ...
> > > > > > > > > clear bit (a bit in page flags)
> > > > > > > > > ...
> > > > > > > > > VM_BUG_ON(test bit)
> > > > > > > > > ...
> > > > > > > > > spin_unlock
> > > > > > > > > release mmap_lock
> > > > > > > > >
> > > > > > > > >
> > > > > > > > > IIUC there is control dependency between the "clear bit" and
> > > > > > > > > "VM_BUG_ON" since VM_BUG_ON simply tests the bit then raises the BUG.
> > > > > > > > > They do touch the overlapping address (the page flags from the same
> > > > > > > > > struct page), but they are bit field operations. Per the memory model
> > > > > > > > > documentation, the order is not guaranteed for bit field operations
> > > > > > > > > IIRC.
> > > > > > > > >
> > > > > > > > > And there are not any implicit barriers between clear bit and test
> > > > > > > > > bit, so the question is whether an explicit barrier, for example,
> > > > > > > > > smp_mb__after_atomic() is required after clear bit to guarantee it
> > > > > > > > > works as expected?
> > > > > > > >
> > > > > > > > I am not familiar with this code, so I will stick with LKMM
> > > > > > > > clarifications.
> > > > > > >
> > > > > > > Yeah, sure. This is why I tried to generalize the code.
> > > > > > >
> > > > > > > > First, please don't forget any protection and ordering that might be
> > > > > > > > provided by the two locks held across this code.
> > > > > > >
> > > > > > > Yes, but for this case I just care about the code between clear bit
> > > > > > > and VM_BUG_ON.
> > > > > >
> > > > > > Fair enough!
> > > > > >
> > > > > > > > Second, a control dependency extends from a READ_ONCE() or stronger
> > > > > > > > (clear_bit() included) to a later store.  Please note "store", not
> > > > > > > > "load".  If you need to order an earlier READ_ONCE() or clear_bit()
> > > > > > >
> > > > > > > So you mean:
> > > > > > >
> > > > > > > clear bit
> > > > > > > ...
> > > > > > > if (test bit) {
> > > > > > >     load_1
> > > > > > >     store_1
> > > > > > >     load_2
> > > > > > >     store_2
> > > > > > > }
> > > > > > >
> > > > > > > The dependency reaches to the first store?
> > > > > >
> > > > > > It reaches both stores, but neither load.
> > > > > >
> > > > > > That means that your example might well execute as if it had instead
> > > > > > been written as follows:
> > > > > >
> > > > > >         load_1
> > > > > >         load_2
> > > > > >         if (test bit) {
> > > > > >                 store_1
> > > > > >                 store_2
> > > > > >         }
> > > > > >
> > > > > > Assuming that you mean the test_bit() function.  If you instead mean
> > > > > > a C-language statement that tests a bit, then the compiler can do all
> > > > > > sorts of things to you.  The compiler can also do interesting things
> > > > > > to you if the stores are plain C-language stores instead of something
> > > > > > like WRITE_ONCE().
> > > > >
> > > > > It is a test_bit() function. Is it possible clear_bit() is reordered
> > > > > with test_bit(), or test_bit() doesn't see the result from
> > > > > clear_bit()?
> > > >
> > > > If the various calls to test_bit() and clear_bit() are to the same
> > > > location, then they will not be reordered with each other.
> > > >
> > > > If they are to different locations, they can be reordered.  But in that
> > > > case, they would not see each others' results anyway.
> > >
> > > Yeah, make sense.
> > >
> > > >
> > > > > > > > with a later load, you will need acquire semantics (smp_load_acquire(),
> > > > > > > > for example) or an explicit barrier such as smp_rmb().  Use of acquire
> > > > > > > > semantics almost always gets you code that is more readable.
> > > > > > >
> > > > > > > Does the load acquire have to pair with a smp_store_release()?
> > > > > > > smp_mb__after_stomic() is not needed because it is too strong and the
> > > > > > > weaker barrier is good enough, right?
> > > > > >
> > > > > > It needs to pair with some type of applicable ordering, but yes,
> > > > > > smp_store_release() is a good one.
> > > > >
> > > > > So, it should look like IIUC:
> > > > >
> > > > > clear_bit()
> > > > > smp_load_acquire()
> > > > > ...
> > > > > if (test_bit()) {
> > > > >     smp_store_release()
> > > > >     load_1
> > > > >     store_1
> > > > >     load_2
> > > > >     store_2
> > > > > }
> > > >
> > > > Just so you know, smp_load_acquire() does a load and smp_store_release()
> > > > does a store.
> > > >
> > > > Also, is this code executed by a single CPU/task?  If so, you need to
> > > > also consider the corresponding code executed by some other CPU/task.
> > >
> > > The code could be executed by multiple tasks in parallel.
> >
> > It is hard for me to tell you what to write without more information
> > about what you do and do not want to happen, but here is one possibility:
> >
> > clear_bit(5, &my_bits);
> > if (test_bit_acquire(5, &my_bits)) {
> >         r1 = READ_ONCE(a);
> >         WRITE_ONCE(b, 1729);
> >         r2 = READ_ONCE(c);
> >         WRITE_ONCE(d, 65535);
> > }
> >
> > This is of course a bit nonsensical because something somewhere would
> > need to set bit 5 in my_bits for the body of the "if" statement to ever
> > be executed.  I am assuming that this happens somewhere else.
> >
> > The clear_bit() would be ordered before the test_bit_acquire() due to
> > their both accessing the same location.  The test_bit_acquire() would
> > be orderd before the body of that "if" statement due to the _acquire()
> > suffix.
> >
> > Is that what you are looking for?  If not, what are you looking for?
> 
> Sorry for the late reply. I think the _acquire() should be something
> I'm looking for. I just figured out a stable reproducer for my
> problem, so I will collect more debug information and try some debug
> patch with _acquire(). Hopefully I could get more clear picture next
> week.

Glad it helped, but are you sure that it is just a memory-ordering
problem as opposed to an algorithmic bug?  I always have to ask...

						Thanx, Paul

Re: [QUESTION] Linux memory model: control dependency with bitfield

[Yang Shi]

On Fri, Jan 13, 2023 at 8:15 PM Paul E. McKenney <paulmck@kernel.org> wrote:
>
> On Fri, Jan 13, 2023 at 06:37:42PM -0800, Yang Shi wrote:
> > On Wed, Jan 11, 2023 at 4:15 PM Paul E. McKenney <paulmck@kernel.org> wrote:
> > >
> > > On Wed, Jan 11, 2023 at 04:01:34PM -0800, Yang Shi wrote:
> > > > On Mon, Jan 9, 2023 at 4:04 PM Paul E. McKenney <paulmck@kernel.org> wrote:
> > > > >
> > > > > On Mon, Jan 09, 2023 at 03:44:54PM -0800, Yang Shi wrote:
> > > > > > On Mon, Jan 9, 2023 at 3:11 PM Paul E. McKenney <paulmck@kernel.org> wrote:
> > > > > > > On Mon, Jan 09, 2023 at 02:08:35PM -0800, Yang Shi wrote:
> > > > > > > > On Mon, Jan 9, 2023 at 9:31 AM Paul E. McKenney <paulmck@kernel.org> wrote:
> > > > > > > > > On Mon, Jan 09, 2023 at 09:14:19AM -0800, Yang Shi wrote:
> > > > > > > > > > Hi Paul,
> > > > > > > > > >
> > > > > > > > > > Hope this email finds you are doing well. I recently ran into a
> > > > > > > > > > problem which might be related to control dependency of the memory
> > > > > > > > > > model. Conceptually, the code does (from copy_present_pte()):
> > > > > > > > > >
> > > > > > > > > > acquire mmap_lock
> > > > > > > > > > spin_lock
> > > > > > > > > > ...
> > > > > > > > > > clear bit (a bit in page flags)
> > > > > > > > > > ...
> > > > > > > > > > VM_BUG_ON(test bit)
> > > > > > > > > > ...
> > > > > > > > > > spin_unlock
> > > > > > > > > > release mmap_lock
> > > > > > > > > >
> > > > > > > > > >
> > > > > > > > > > IIUC there is control dependency between the "clear bit" and
> > > > > > > > > > "VM_BUG_ON" since VM_BUG_ON simply tests the bit then raises the BUG.
> > > > > > > > > > They do touch the overlapping address (the page flags from the same
> > > > > > > > > > struct page), but they are bit field operations. Per the memory model
> > > > > > > > > > documentation, the order is not guaranteed for bit field operations
> > > > > > > > > > IIRC.
> > > > > > > > > >
> > > > > > > > > > And there are not any implicit barriers between clear bit and test
> > > > > > > > > > bit, so the question is whether an explicit barrier, for example,
> > > > > > > > > > smp_mb__after_atomic() is required after clear bit to guarantee it
> > > > > > > > > > works as expected?
> > > > > > > > >
> > > > > > > > > I am not familiar with this code, so I will stick with LKMM
> > > > > > > > > clarifications.
> > > > > > > >
> > > > > > > > Yeah, sure. This is why I tried to generalize the code.
> > > > > > > >
> > > > > > > > > First, please don't forget any protection and ordering that might be
> > > > > > > > > provided by the two locks held across this code.
> > > > > > > >
> > > > > > > > Yes, but for this case I just care about the code between clear bit
> > > > > > > > and VM_BUG_ON.
> > > > > > >
> > > > > > > Fair enough!
> > > > > > >
> > > > > > > > > Second, a control dependency extends from a READ_ONCE() or stronger
> > > > > > > > > (clear_bit() included) to a later store.  Please note "store", not
> > > > > > > > > "load".  If you need to order an earlier READ_ONCE() or clear_bit()
> > > > > > > >
> > > > > > > > So you mean:
> > > > > > > >
> > > > > > > > clear bit
> > > > > > > > ...
> > > > > > > > if (test bit) {
> > > > > > > >     load_1
> > > > > > > >     store_1
> > > > > > > >     load_2
> > > > > > > >     store_2
> > > > > > > > }
> > > > > > > >
> > > > > > > > The dependency reaches to the first store?
> > > > > > >
> > > > > > > It reaches both stores, but neither load.
> > > > > > >
> > > > > > > That means that your example might well execute as if it had instead
> > > > > > > been written as follows:
> > > > > > >
> > > > > > >         load_1
> > > > > > >         load_2
> > > > > > >         if (test bit) {
> > > > > > >                 store_1
> > > > > > >                 store_2
> > > > > > >         }
> > > > > > >
> > > > > > > Assuming that you mean the test_bit() function.  If you instead mean
> > > > > > > a C-language statement that tests a bit, then the compiler can do all
> > > > > > > sorts of things to you.  The compiler can also do interesting things
> > > > > > > to you if the stores are plain C-language stores instead of something
> > > > > > > like WRITE_ONCE().
> > > > > >
> > > > > > It is a test_bit() function. Is it possible clear_bit() is reordered
> > > > > > with test_bit(), or test_bit() doesn't see the result from
> > > > > > clear_bit()?
> > > > >
> > > > > If the various calls to test_bit() and clear_bit() are to the same
> > > > > location, then they will not be reordered with each other.
> > > > >
> > > > > If they are to different locations, they can be reordered.  But in that
> > > > > case, they would not see each others' results anyway.
> > > >
> > > > Yeah, make sense.
> > > >
> > > > >
> > > > > > > > > with a later load, you will need acquire semantics (smp_load_acquire(),
> > > > > > > > > for example) or an explicit barrier such as smp_rmb().  Use of acquire
> > > > > > > > > semantics almost always gets you code that is more readable.
> > > > > > > >
> > > > > > > > Does the load acquire have to pair with a smp_store_release()?
> > > > > > > > smp_mb__after_stomic() is not needed because it is too strong and the
> > > > > > > > weaker barrier is good enough, right?
> > > > > > >
> > > > > > > It needs to pair with some type of applicable ordering, but yes,
> > > > > > > smp_store_release() is a good one.
> > > > > >
> > > > > > So, it should look like IIUC:
> > > > > >
> > > > > > clear_bit()
> > > > > > smp_load_acquire()
> > > > > > ...
> > > > > > if (test_bit()) {
> > > > > >     smp_store_release()
> > > > > >     load_1
> > > > > >     store_1
> > > > > >     load_2
> > > > > >     store_2
> > > > > > }
> > > > >
> > > > > Just so you know, smp_load_acquire() does a load and smp_store_release()
> > > > > does a store.
> > > > >
> > > > > Also, is this code executed by a single CPU/task?  If so, you need to
> > > > > also consider the corresponding code executed by some other CPU/task.
> > > >
> > > > The code could be executed by multiple tasks in parallel.
> > >
> > > It is hard for me to tell you what to write without more information
> > > about what you do and do not want to happen, but here is one possibility:
> > >
> > > clear_bit(5, &my_bits);
> > > if (test_bit_acquire(5, &my_bits)) {
> > >         r1 = READ_ONCE(a);
> > >         WRITE_ONCE(b, 1729);
> > >         r2 = READ_ONCE(c);
> > >         WRITE_ONCE(d, 65535);
> > > }
> > >
> > > This is of course a bit nonsensical because something somewhere would
> > > need to set bit 5 in my_bits for the body of the "if" statement to ever
> > > be executed.  I am assuming that this happens somewhere else.
> > >
> > > The clear_bit() would be ordered before the test_bit_acquire() due to
> > > their both accessing the same location.  The test_bit_acquire() would
> > > be orderd before the body of that "if" statement due to the _acquire()
> > > suffix.
> > >
> > > Is that what you are looking for?  If not, what are you looking for?
> >
> > Sorry for the late reply. I think the _acquire() should be something
> > I'm looking for. I just figured out a stable reproducer for my
> > problem, so I will collect more debug information and try some debug
> > patch with _acquire(). Hopefully I could get more clear picture next
> > week.
>
> Glad it helped, but are you sure that it is just a memory-ordering
> problem as opposed to an algorithmic bug?  I always have to ask...

I did ask myself the same question. But AFAICT, all modifications to
the flag (set and clear) are protected by page table lock.

>
>                                                 Thanx, Paul

Re: [QUESTION] Linux memory model: control dependency with bitfield

[Paul E. McKenney]

On Tue, Jan 17, 2023 at 01:28:19PM -0800, Yang Shi wrote:
> On Fri, Jan 13, 2023 at 8:15 PM Paul E. McKenney <paulmck@kernel.org> wrote:
> >
> > On Fri, Jan 13, 2023 at 06:37:42PM -0800, Yang Shi wrote:
> > > On Wed, Jan 11, 2023 at 4:15 PM Paul E. McKenney <paulmck@kernel.org> wrote:
> > > >
> > > > On Wed, Jan 11, 2023 at 04:01:34PM -0800, Yang Shi wrote:
> > > > > On Mon, Jan 9, 2023 at 4:04 PM Paul E. McKenney <paulmck@kernel.org> wrote:
> > > > > >
> > > > > > On Mon, Jan 09, 2023 at 03:44:54PM -0800, Yang Shi wrote:
> > > > > > > On Mon, Jan 9, 2023 at 3:11 PM Paul E. McKenney <paulmck@kernel.org> wrote:
> > > > > > > > On Mon, Jan 09, 2023 at 02:08:35PM -0800, Yang Shi wrote:
> > > > > > > > > On Mon, Jan 9, 2023 at 9:31 AM Paul E. McKenney <paulmck@kernel.org> wrote:
> > > > > > > > > > On Mon, Jan 09, 2023 at 09:14:19AM -0800, Yang Shi wrote:
> > > > > > > > > > > Hi Paul,
> > > > > > > > > > >
> > > > > > > > > > > Hope this email finds you are doing well. I recently ran into a
> > > > > > > > > > > problem which might be related to control dependency of the memory
> > > > > > > > > > > model. Conceptually, the code does (from copy_present_pte()):
> > > > > > > > > > >
> > > > > > > > > > > acquire mmap_lock
> > > > > > > > > > > spin_lock
> > > > > > > > > > > ...
> > > > > > > > > > > clear bit (a bit in page flags)
> > > > > > > > > > > ...
> > > > > > > > > > > VM_BUG_ON(test bit)
> > > > > > > > > > > ...
> > > > > > > > > > > spin_unlock
> > > > > > > > > > > release mmap_lock
> > > > > > > > > > >
> > > > > > > > > > >
> > > > > > > > > > > IIUC there is control dependency between the "clear bit" and
> > > > > > > > > > > "VM_BUG_ON" since VM_BUG_ON simply tests the bit then raises the BUG.
> > > > > > > > > > > They do touch the overlapping address (the page flags from the same
> > > > > > > > > > > struct page), but they are bit field operations. Per the memory model
> > > > > > > > > > > documentation, the order is not guaranteed for bit field operations
> > > > > > > > > > > IIRC.
> > > > > > > > > > >
> > > > > > > > > > > And there are not any implicit barriers between clear bit and test
> > > > > > > > > > > bit, so the question is whether an explicit barrier, for example,
> > > > > > > > > > > smp_mb__after_atomic() is required after clear bit to guarantee it
> > > > > > > > > > > works as expected?
> > > > > > > > > >
> > > > > > > > > > I am not familiar with this code, so I will stick with LKMM
> > > > > > > > > > clarifications.
> > > > > > > > >
> > > > > > > > > Yeah, sure. This is why I tried to generalize the code.
> > > > > > > > >
> > > > > > > > > > First, please don't forget any protection and ordering that might be
> > > > > > > > > > provided by the two locks held across this code.
> > > > > > > > >
> > > > > > > > > Yes, but for this case I just care about the code between clear bit
> > > > > > > > > and VM_BUG_ON.
> > > > > > > >
> > > > > > > > Fair enough!
> > > > > > > >
> > > > > > > > > > Second, a control dependency extends from a READ_ONCE() or stronger
> > > > > > > > > > (clear_bit() included) to a later store.  Please note "store", not
> > > > > > > > > > "load".  If you need to order an earlier READ_ONCE() or clear_bit()
> > > > > > > > >
> > > > > > > > > So you mean:
> > > > > > > > >
> > > > > > > > > clear bit
> > > > > > > > > ...
> > > > > > > > > if (test bit) {
> > > > > > > > >     load_1
> > > > > > > > >     store_1
> > > > > > > > >     load_2
> > > > > > > > >     store_2
> > > > > > > > > }
> > > > > > > > >
> > > > > > > > > The dependency reaches to the first store?
> > > > > > > >
> > > > > > > > It reaches both stores, but neither load.
> > > > > > > >
> > > > > > > > That means that your example might well execute as if it had instead
> > > > > > > > been written as follows:
> > > > > > > >
> > > > > > > >         load_1
> > > > > > > >         load_2
> > > > > > > >         if (test bit) {
> > > > > > > >                 store_1
> > > > > > > >                 store_2
> > > > > > > >         }
> > > > > > > >
> > > > > > > > Assuming that you mean the test_bit() function.  If you instead mean
> > > > > > > > a C-language statement that tests a bit, then the compiler can do all
> > > > > > > > sorts of things to you.  The compiler can also do interesting things
> > > > > > > > to you if the stores are plain C-language stores instead of something
> > > > > > > > like WRITE_ONCE().
> > > > > > >
> > > > > > > It is a test_bit() function. Is it possible clear_bit() is reordered
> > > > > > > with test_bit(), or test_bit() doesn't see the result from
> > > > > > > clear_bit()?
> > > > > >
> > > > > > If the various calls to test_bit() and clear_bit() are to the same
> > > > > > location, then they will not be reordered with each other.
> > > > > >
> > > > > > If they are to different locations, they can be reordered.  But in that
> > > > > > case, they would not see each others' results anyway.
> > > > >
> > > > > Yeah, make sense.
> > > > >
> > > > > >
> > > > > > > > > > with a later load, you will need acquire semantics (smp_load_acquire(),
> > > > > > > > > > for example) or an explicit barrier such as smp_rmb().  Use of acquire
> > > > > > > > > > semantics almost always gets you code that is more readable.
> > > > > > > > >
> > > > > > > > > Does the load acquire have to pair with a smp_store_release()?
> > > > > > > > > smp_mb__after_stomic() is not needed because it is too strong and the
> > > > > > > > > weaker barrier is good enough, right?
> > > > > > > >
> > > > > > > > It needs to pair with some type of applicable ordering, but yes,
> > > > > > > > smp_store_release() is a good one.
> > > > > > >
> > > > > > > So, it should look like IIUC:
> > > > > > >
> > > > > > > clear_bit()
> > > > > > > smp_load_acquire()
> > > > > > > ...
> > > > > > > if (test_bit()) {
> > > > > > >     smp_store_release()
> > > > > > >     load_1
> > > > > > >     store_1
> > > > > > >     load_2
> > > > > > >     store_2
> > > > > > > }
> > > > > >
> > > > > > Just so you know, smp_load_acquire() does a load and smp_store_release()
> > > > > > does a store.
> > > > > >
> > > > > > Also, is this code executed by a single CPU/task?  If so, you need to
> > > > > > also consider the corresponding code executed by some other CPU/task.
> > > > >
> > > > > The code could be executed by multiple tasks in parallel.
> > > >
> > > > It is hard for me to tell you what to write without more information
> > > > about what you do and do not want to happen, but here is one possibility:
> > > >
> > > > clear_bit(5, &my_bits);
> > > > if (test_bit_acquire(5, &my_bits)) {
> > > >         r1 = READ_ONCE(a);
> > > >         WRITE_ONCE(b, 1729);
> > > >         r2 = READ_ONCE(c);
> > > >         WRITE_ONCE(d, 65535);
> > > > }
> > > >
> > > > This is of course a bit nonsensical because something somewhere would
> > > > need to set bit 5 in my_bits for the body of the "if" statement to ever
> > > > be executed.  I am assuming that this happens somewhere else.
> > > >
> > > > The clear_bit() would be ordered before the test_bit_acquire() due to
> > > > their both accessing the same location.  The test_bit_acquire() would
> > > > be orderd before the body of that "if" statement due to the _acquire()
> > > > suffix.
> > > >
> > > > Is that what you are looking for?  If not, what are you looking for?
> > >
> > > Sorry for the late reply. I think the _acquire() should be something
> > > I'm looking for. I just figured out a stable reproducer for my
> > > problem, so I will collect more debug information and try some debug
> > > patch with _acquire(). Hopefully I could get more clear picture next
> > > week.
> >
> > Glad it helped, but are you sure that it is just a memory-ordering
> > problem as opposed to an algorithmic bug?  I always have to ask...
> 
> I did ask myself the same question. But AFAICT, all modifications to
> the flag (set and clear) are protected by page table lock.

Sounds good!  At least until further notice.  ;-)

							Thanx, Paul