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>