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

[Yang Shi <shy828301@gmail.com>]

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