diff mbox series

[1/8] membarrier: Document why membarrier() works

Message ID b648efcb72feb257b9fe004bd132f581805ec0d6.1623813516.git.luto@kernel.org (mailing list archive)
State New
Headers show
Series membarrier cleanups | expand

Commit Message

Andy Lutomirski June 16, 2021, 3:21 a.m. UTC
We had a nice comment at the top of membarrier.c explaining why membarrier
worked in a handful of scenarios, but that consisted more of a list of
things not to forget than an actual description of the algorithm and why it
should be expected to work.

Add a comment explaining my understanding of the algorithm.  This exposes a
couple of implementation issues that I will hopefully fix up in subsequent
patches.

Cc: Mathieu Desnoyers <mathieu.desnoyers@efficios.com>
Cc: Nicholas Piggin <npiggin@gmail.com>
Cc: Peter Zijlstra <peterz@infradead.org>
Signed-off-by: Andy Lutomirski <luto@kernel.org>
---
 kernel/sched/membarrier.c | 55 +++++++++++++++++++++++++++++++++++++++
 1 file changed, 55 insertions(+)

Comments

Nicholas Piggin June 16, 2021, 4 a.m. UTC | #1
Excerpts from Andy Lutomirski's message of June 16, 2021 1:21 pm:
> We had a nice comment at the top of membarrier.c explaining why membarrier
> worked in a handful of scenarios, but that consisted more of a list of
> things not to forget than an actual description of the algorithm and why it
> should be expected to work.
> 
> Add a comment explaining my understanding of the algorithm.  This exposes a
> couple of implementation issues that I will hopefully fix up in subsequent
> patches.
> 
> Cc: Mathieu Desnoyers <mathieu.desnoyers@efficios.com>
> Cc: Nicholas Piggin <npiggin@gmail.com>
> Cc: Peter Zijlstra <peterz@infradead.org>
> Signed-off-by: Andy Lutomirski <luto@kernel.org>
> ---
>  kernel/sched/membarrier.c | 55 +++++++++++++++++++++++++++++++++++++++
>  1 file changed, 55 insertions(+)
> 
> diff --git a/kernel/sched/membarrier.c b/kernel/sched/membarrier.c
> index b5add64d9698..3173b063d358 100644
> --- a/kernel/sched/membarrier.c
> +++ b/kernel/sched/membarrier.c
> @@ -7,6 +7,61 @@
>  #include "sched.h"
>  

Precisely describing the orderings is great, not a fan of the style of the
comment though.

>  /*
> + * The basic principle behind the regular memory barrier mode of membarrier()
> + * is as follows.  For each CPU, membarrier() operates in one of two
> + * modes.

membarrier(2) is called by one CPU, and it iterates over target CPUs, 
and for each of them it...

> Either it sends an IPI or it does not. If membarrier() sends an
> + * IPI, then we have the following sequence of events:
> + *
> + * 1. membarrier() does smp_mb().
> + * 2. membarrier() does a store (the IPI request payload) that is observed by
> + *    the target CPU.
> + * 3. The target CPU does smp_mb().
> + * 4. The target CPU does a store (the completion indication) that is observed
> + *    by membarrier()'s wait-for-IPIs-to-finish request.
> + * 5. membarrier() does smp_mb().
> + *
> + * So all pre-membarrier() local accesses are visible after the IPI on the
> + * target CPU and all pre-IPI remote accesses are visible after
> + * membarrier(). IOW membarrier() has synchronized both ways with the target
> + * CPU.
> + *
> + * (This has the caveat that membarrier() does not interrupt the CPU that it's
> + * running on at the time it sends the IPIs. However, if that is the CPU on
> + * which membarrier() starts and/or finishes, membarrier() does smp_mb() and,
> + * if not, then membarrier() scheduled, and scheduling had better include a
> + * full barrier somewhere for basic correctness regardless of membarrier.)
> + *
> + * If membarrier() does not send an IPI, this means that membarrier() reads
> + * cpu_rq(cpu)->curr->mm and that the result is not equal to the target
> + * mm.

If membarrier(2) reads cpu_rq(target)->curr->mm and finds it != 
current->mm, this means it doesn't send an IPI. "Had read" even would at 
least make it past tense. I know what you mean, it just sounds backwards as
worded.

> Let's assume for now that tasks never change their mm field.  The
> + * sequence of events is:
> + *
> + * 1. Target CPU switches away from the target mm (or goes lazy or has never
> + *    run the target mm in the first place). This involves smp_mb() followed
> + *    by a write to cpu_rq(cpu)->curr.
> + * 2. membarrier() does smp_mb(). (This is NOT synchronized with any action
> + *    done by the target.)
> + * 3. membarrier() observes the value written in step 1 and does *not* observe
> + *    the value written in step 5.
> + * 4. membarrier() does smp_mb().
> + * 5. Target CPU switches back to the target mm and writes to
> + *    cpu_rq(cpu)->curr. (This is NOT synchronized with any action on
> + *    membarrier()'s part.)
> + * 6. Target CPU executes smp_mb()
> + *
> + * All pre-schedule accesses on the remote CPU are visible after membarrier()
> + * because they all precede the target's write in step 1 and are synchronized
> + * to the local CPU by steps 3 and 4.  All pre-membarrier() accesses on the
> + * local CPU are visible on the remote CPU after scheduling because they
> + * happen before the smp_mb(); read in steps 2 and 3 and that read preceeds
> + * the target's smp_mb() in step 6.
> + *
> + * However, tasks can change their ->mm, e.g., via kthread_use_mm().  So
> + * tasks that switch their ->mm must follow the same rules as the scheduler
> + * changing rq->curr, and the membarrier() code needs to do both dereferences
> + * carefully.

I would prefer the memory accesses and barriers and post-conditions made 
in a more precise style like the rest of the comments. I think it's a 
good idea to break down the higher level choices, and treat a single 
target CPU at a time, but it can be done in the same style

   p = rcu_dereference(rq->curr);
   if (p->mm == current->mm)
     // IPI case
   else
     // No IPI case

   // IPI case:
   ...

   // No IPI case:
   ...

> + *
> + *
>   * For documentation purposes, here are some membarrier ordering
>   * scenarios to keep in mind:

And I think it really needs to be integrated somehow with the rest of 
the comments that follow. For example your IPI case and the A/B cases
are treating the same subject, just with slightly different levels of 
detail.

Thanks,
Nick
Peter Zijlstra June 16, 2021, 7:30 a.m. UTC | #2
On Wed, Jun 16, 2021 at 02:00:37PM +1000, Nicholas Piggin wrote:
> Excerpts from Andy Lutomirski's message of June 16, 2021 1:21 pm:
> > We had a nice comment at the top of membarrier.c explaining why membarrier
> > worked in a handful of scenarios, but that consisted more of a list of
> > things not to forget than an actual description of the algorithm and why it
> > should be expected to work.
> > 
> > Add a comment explaining my understanding of the algorithm.  This exposes a
> > couple of implementation issues that I will hopefully fix up in subsequent
> > patches.
> > 
> > Cc: Mathieu Desnoyers <mathieu.desnoyers@efficios.com>
> > Cc: Nicholas Piggin <npiggin@gmail.com>
> > Cc: Peter Zijlstra <peterz@infradead.org>
> > Signed-off-by: Andy Lutomirski <luto@kernel.org>
> > ---
> >  kernel/sched/membarrier.c | 55 +++++++++++++++++++++++++++++++++++++++
> >  1 file changed, 55 insertions(+)
> > 
> > diff --git a/kernel/sched/membarrier.c b/kernel/sched/membarrier.c
> > index b5add64d9698..3173b063d358 100644
> > --- a/kernel/sched/membarrier.c
> > +++ b/kernel/sched/membarrier.c
> > @@ -7,6 +7,61 @@
> >  #include "sched.h"
> >  
> 
> Precisely describing the orderings is great, not a fan of the style of the
> comment though.

I'm with Nick on that; I can't read it :/ It only makes things more
confusing. If you want precision, English (or any natural language) is
your enemy.

To describe ordering use the diagrams and/or litmus tests.
Andy Lutomirski June 17, 2021, 11:45 p.m. UTC | #3
On 6/16/21 12:30 AM, Peter Zijlstra wrote:
> On Wed, Jun 16, 2021 at 02:00:37PM +1000, Nicholas Piggin wrote:
>> Excerpts from Andy Lutomirski's message of June 16, 2021 1:21 pm:
>>> We had a nice comment at the top of membarrier.c explaining why membarrier
>>> worked in a handful of scenarios, but that consisted more of a list of
>>> things not to forget than an actual description of the algorithm and why it
>>> should be expected to work.
>>>
>>> Add a comment explaining my understanding of the algorithm.  This exposes a
>>> couple of implementation issues that I will hopefully fix up in subsequent
>>> patches.
>>>
>>> Cc: Mathieu Desnoyers <mathieu.desnoyers@efficios.com>
>>> Cc: Nicholas Piggin <npiggin@gmail.com>
>>> Cc: Peter Zijlstra <peterz@infradead.org>
>>> Signed-off-by: Andy Lutomirski <luto@kernel.org>
>>> ---
>>>  kernel/sched/membarrier.c | 55 +++++++++++++++++++++++++++++++++++++++
>>>  1 file changed, 55 insertions(+)
>>>
>>> diff --git a/kernel/sched/membarrier.c b/kernel/sched/membarrier.c
>>> index b5add64d9698..3173b063d358 100644
>>> --- a/kernel/sched/membarrier.c
>>> +++ b/kernel/sched/membarrier.c
>>> @@ -7,6 +7,61 @@
>>>  #include "sched.h"
>>>  
>>
>> Precisely describing the orderings is great, not a fan of the style of the
>> comment though.
> 
> I'm with Nick on that; I can't read it :/ It only makes things more
> confusing. If you want precision, English (or any natural language) is
> your enemy.
> 
> To describe ordering use the diagrams and/or litmus tests.
> 

I made some changes.  Maybe it's better now.
diff mbox series

Patch

diff --git a/kernel/sched/membarrier.c b/kernel/sched/membarrier.c
index b5add64d9698..3173b063d358 100644
--- a/kernel/sched/membarrier.c
+++ b/kernel/sched/membarrier.c
@@ -7,6 +7,61 @@ 
 #include "sched.h"
 
 /*
+ * The basic principle behind the regular memory barrier mode of membarrier()
+ * is as follows.  For each CPU, membarrier() operates in one of two
+ * modes.  Either it sends an IPI or it does not. If membarrier() sends an
+ * IPI, then we have the following sequence of events:
+ *
+ * 1. membarrier() does smp_mb().
+ * 2. membarrier() does a store (the IPI request payload) that is observed by
+ *    the target CPU.
+ * 3. The target CPU does smp_mb().
+ * 4. The target CPU does a store (the completion indication) that is observed
+ *    by membarrier()'s wait-for-IPIs-to-finish request.
+ * 5. membarrier() does smp_mb().
+ *
+ * So all pre-membarrier() local accesses are visible after the IPI on the
+ * target CPU and all pre-IPI remote accesses are visible after
+ * membarrier(). IOW membarrier() has synchronized both ways with the target
+ * CPU.
+ *
+ * (This has the caveat that membarrier() does not interrupt the CPU that it's
+ * running on at the time it sends the IPIs. However, if that is the CPU on
+ * which membarrier() starts and/or finishes, membarrier() does smp_mb() and,
+ * if not, then membarrier() scheduled, and scheduling had better include a
+ * full barrier somewhere for basic correctness regardless of membarrier.)
+ *
+ * If membarrier() does not send an IPI, this means that membarrier() reads
+ * cpu_rq(cpu)->curr->mm and that the result is not equal to the target
+ * mm.  Let's assume for now that tasks never change their mm field.  The
+ * sequence of events is:
+ *
+ * 1. Target CPU switches away from the target mm (or goes lazy or has never
+ *    run the target mm in the first place). This involves smp_mb() followed
+ *    by a write to cpu_rq(cpu)->curr.
+ * 2. membarrier() does smp_mb(). (This is NOT synchronized with any action
+ *    done by the target.)
+ * 3. membarrier() observes the value written in step 1 and does *not* observe
+ *    the value written in step 5.
+ * 4. membarrier() does smp_mb().
+ * 5. Target CPU switches back to the target mm and writes to
+ *    cpu_rq(cpu)->curr. (This is NOT synchronized with any action on
+ *    membarrier()'s part.)
+ * 6. Target CPU executes smp_mb()
+ *
+ * All pre-schedule accesses on the remote CPU are visible after membarrier()
+ * because they all precede the target's write in step 1 and are synchronized
+ * to the local CPU by steps 3 and 4.  All pre-membarrier() accesses on the
+ * local CPU are visible on the remote CPU after scheduling because they
+ * happen before the smp_mb(); read in steps 2 and 3 and that read preceeds
+ * the target's smp_mb() in step 6.
+ *
+ * However, tasks can change their ->mm, e.g., via kthread_use_mm().  So
+ * tasks that switch their ->mm must follow the same rules as the scheduler
+ * changing rq->curr, and the membarrier() code needs to do both dereferences
+ * carefully.
+ *
+ *
  * For documentation purposes, here are some membarrier ordering
  * scenarios to keep in mind:
  *