Re: Linux-kernel examples for LKMM recipes

[Alan Stern]

On Fri, 13 Oct 2017, Paul E. McKenney wrote:

> On Fri, Oct 13, 2017 at 03:44:07PM -0400, Alan Stern wrote:
> > On Wed, 11 Oct 2017, Paul E. McKenney wrote:
> > 
> > > This document lists the litmus-test patterns that we have been discussing,
> > > along with examples from the Linux kernel.  This is intended to feed into
> > > the recipes document.  All examples are from v4.13.
> > > 
> > > 0.	Single-variable SC.
> > > 
> > > 	a.	Within a single CPU, the use of the ->dynticks_nmi_nesting
> > > 		counter by rcu_nmi_enter() and rcu_nmi_exit() qualifies
> > > 		(see kernel/rcu/tree.c).  The counter is accessed by
> > > 		interrupts and NMIs as well as by process-level code.
> > > 		This counter can be accessed by other CPUs, but only
> > > 		for debug output.
> > 
> > I'm not sure that single-variable SC can really be represented by an 
> > example.  It gets used literally all over the kernel -- it's such a 
> > large part of the way we think about computer programs that we rely on 
> > it unconsciously.
> > 
> > For example, the very first function in the very first C source file 
> > in the kernel/ directory (namely, check_free_space() in kernel/acct.c) 
> > includes this code:
> > 
> >         if (acct->active) {
> >                 u64 suspend = sbuf.f_blocks * SUSPEND;
> >                 do_div(suspend, 100);
> > 
> > How do we know that the value which gets divided by 100 is
> > sbuf.f_blocks * SUSPEND and not the random garbage which was stored in
> > suspend's memory location before it was initialized?  Answer:
> > per-variable SC.
> > 
> > Okay, maybe that's not really applicable, since it doesn't involve
> > accesses to shared memory.  Here's an example that does.  
> > get_futex_key() in kernel/futex.c calls READ_ONCE(page->mapping) twice.  
> > How do we know that the value retrieved by the second call was not
> > stored _earlier_ than the value retrieved by the first call?  
> > Per-variable SC.
> > 
> > > 	b.	Between CPUs, I would put forward the ->dflags
> > > 		updates, but this is anything but simple.  But maybe
> > > 		OK for an illustration?
> > 
> > Pretty much any code that accesses the same shared variable twice on
> > the same CPU could be an example of per-variable SC.  But I don't think 
> > people would learn much by studying such examples.
> 
> Perhaps the recipes document should just baldly state that any execution
> having only one thread and/or having only one variable will be fully
> ordered?

That wouldn't be a bad idea.  (Although the part about only one thread 
should be pretty obvious.)

Also, you have to be a little careful because the ordering of the
execution may not always agree with the ordering of the source code.  
The compiler is allowed to evaluate the arguments to a function call,
for example, in any order it likes.

Alan