Skip site navigation (1)Skip section navigation (2)
Date:      Thu, 16 Sep 2010 14:16:05 -0400
From:      John Baldwin <jhb@freebsd.org>
To:        Andrey Simonenko <simon@comsys.ntu-kpi.kiev.ua>
Cc:        freebsd-hackers@freebsd.org, Matthew Fleming <mdf356@gmail.com>
Subject:   Re: Questions about mutex implementation in kern/kern_mutex.c
Message-ID:  <201009161416.05759.jhb@freebsd.org>
In-Reply-To: <20100916173307.GA1994@pm513-1.comsys.ntu-kpi.kiev.ua>
References:  <20100915134415.GA23727@pm513-1.comsys.ntu-kpi.kiev.ua> <AANLkTimJV-oB_uTSbUTtbSrR5fXgWGk00dEV7L-Gobrf@mail.gmail.com> <20100916173307.GA1994@pm513-1.comsys.ntu-kpi.kiev.ua>

next in thread | previous in thread | raw e-mail | index | archive | help
On Thursday, September 16, 2010 1:33:07 pm Andrey Simonenko wrote:
> On Wed, Sep 15, 2010 at 08:46:00AM -0700, Matthew Fleming wrote:
> > I'll take a stab at answering these...
> > 
> > On Wed, Sep 15, 2010 at 6:44 AM, Andrey Simonenko
> > <simon@comsys.ntu-kpi.kiev.ua> wrote:
> > > Hello,
> > >
> > > I have questions about mutex implementation in kern/kern_mutex.c
> > > and sys/mutex.h files (current versions of these files):
> > >
> > > 1. Is the following statement correct for a volatile pointer or integer
> > >  variable: if a volatile variable is updated by the compare-and-set
> > >  instruction (e.g. atomic_cmpset_ptr(&val, ...)), then the current
> > >  value of such variable can be read without any special instruction
> > >  (e.g. v = val)?
> > >
> > >  I checked Assembler code for a function with "v = val" and "val = v"
> > >  like statements generated for volatile variable and simple variable
> > >  and found differences: on ia64 "v = val" was implemented by ld.acq and
> > >  "val = v" was implemented by st.rel; on mips and sparc64 Assembler code
> > >  can have different order of lines for volatile and simple variable
> > >  (depends on the code of a function).
> > 
> > I think this depends somewhat on the hardware and what you mean by
> > "current" value.
> 
> "Current" value means that the value of a variable read by one thread
> is equal to the value of this variable successfully updated by another
> thread by the compare-and-set instruction.  As I understand from the kernel
> source code, atomic_cmpset_ptr() allows to update a variable in a way that
> all other CPUs will invalidate corresponding cache lines that contain
> the value of this variable.

That is not true.  It is likely true on x86, but it is certainly not true on
other architectures such as sparc64 where a write may be held in a store 
buffer for an indeterminate amount of time (and note that some lock releases 
are simple stores with a "rel" memory barrier).  All that we require is that 
if the value is stale, the atomic_cmpset() that attempts to set MTX_CONTESTED 
will fail.

> The mtx_owned(9) macro uses this property, mtx_owned() does not use anything
> special to compare the value of m->mtx_lock (volatile) with current thread
> pointer, all other functions that update m->mtx_lock of unowned mutex use
> compare-and-set instruction.  Also I cannot find anything special in
> generated Assembler code for volatile variables (except for ia64 where
> acquire loads and release stores are used).

No, mtx_owned() is just not harmed by the races it loses.  You can certainly 
read a stale value of mtx_lock in mtx_owned() if some other thread owns the 
lock or has just released the lock.  However, we don't care, because in both 
of those cases, mtx_owned() returns false.  What does matter is that 
mtx_owned() can only return true if we currently hold the mutex.  This works 
because 1) the same thread cannot call mtx_unlock() and mtx_owned() at the 
same time, and 2) even CPUs that hold writes in store buffers will snoop their 
store buffer for local reads on that CPU.  That is, a given CPU will never 
read a stale value of a memory word that is "older" than a write it has 
performed to that word.

> > If you want a value that is not in-flux, then something like
> > atomic_cmpset_ptr() setting to the current value is needed, so that
> > you force any other atomic_cmpset to fail.  However, since there is no
> > explicit lock involved, there is no strong meaning for "current" value
> > and a read that does not rely on a value cached in a register is
> > likely sufficient.  While the "volatile" keyword in C has no explicit
> > hardware meaning, it often means that a load from memory (or,
> > presumably, L1-L3 cache) is required.
> 
> The "volatile" keyword here and all questions are related to the base C
> compiler, current version and currently supported architectures in FreeBSD.
> Yes, here under "volatile" I want to say that the value of a variable is
> not cached in a register and it is referenced by its address in all
> commands.
> 
> There are some places in the kernel where a variable is updated in
> something like "do { v = value; } while (!atomic_cmpset_int(&value, ...));"
> and that variable is not "volatile", but the compiler generates correct
> Assembler code.  So "volatile" is not a requirement for all cases.

Hmm, I suspect that many of those places actually do use volatile.  The 
various lock cookies (mtx_lock, etc.) are declared volatile in the structure.  
Otherwise the compiler would be free to conclude that 'v = value;' is a loop 
invariant and move it out of the loop which would break.  Given that, the 
construct you referred to does in fact require 'value' to be volatile.

-- 
John Baldwin



Want to link to this message? Use this URL: <https://mail-archive.FreeBSD.org/cgi/mid.cgi?201009161416.05759.jhb>