Date: Thu, 16 Sep 2010 20:33:07 +0300 From: Andrey Simonenko <simon@comsys.ntu-kpi.kiev.ua> To: Matthew Fleming <mdf356@gmail.com> Cc: freebsd-hackers@freebsd.org Subject: Re: Questions about mutex implementation in kern/kern_mutex.c Message-ID: <20100916173307.GA1994@pm513-1.comsys.ntu-kpi.kiev.ua> In-Reply-To: <AANLkTimJV-oB_uTSbUTtbSrR5fXgWGk00dEV7L-Gobrf@mail.gmail.com> References: <20100915134415.GA23727@pm513-1.comsys.ntu-kpi.kiev.ua> <AANLkTimJV-oB_uTSbUTtbSrR5fXgWGk00dEV7L-Gobrf@mail.gmail.com>
next in thread | previous in thread | raw e-mail | index | archive | help
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.
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).
>
> 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.
>
> > 2. Let there is a default (sleep) mutex and adaptive mutexes is enabled.
> > A thread tries to obtain lock quickly and fails, _mtx_lock_sleep()
> > is called, it gets the address of the current mutex's owner thread
> > and checks whether that owner thread is running (on another CPU).
> > How does _mtx_lock_sleep() know that that thread still exists
> > (lines 311-337 in kern_mutex.c)?
> >
> > When adaptive mutexes was implemented there was explicit locking
> > around adaptive mutexes code. When turnstile in mutex code was
> > implemented that's locking logic was changed.
>
> It appears that it's possible for the thread pointer to be recycled
> between fetching the value of owner and looking at TD_IS_RUNNING. On
> actual hardware, this race is unlikely to occur due to the time it
> takes for a thread to release a lock and perform all of thread exit
> code before the struct thread is returned to the uma zone. However,
> even once returned to the uma zone on many FreeBSD implementations the
> access is safe as the address of the thread is still dereferenceable,
> due to the implementation of uma zones.
I checked exactly this scenario, that's why asked this question to verify
my understanding.
>
> > 3. Why there is no any memory barrier in mtx_init()? If another thread
> > (on another CPU) finds that mutex is initialized using mtx_initialized()
> > then it can mtx_lock() it and mtx_lock() it second time, as a result
> > mtx_recurse field will be increased, but its value still can be
> > uninitialized on architecture with relaxed memory ordering model.
>
> It seems to me that it's generally a programming error to rely on the
> return of mtx_initialized(), as there is no serialization with e.g. a
> thread calling mtx_destroy(). A fully correct serialization model
> would require that a single thread initialize the mtx and then create
> any worker threads that will use the mtx.
I agree that this should not happen in practice. Another thread can get
a pointer to just initialized mutex and begin to work with it, so
mtx_initialized() is not a requirement. I just want to say that when
mtx_init() is finished, it does not mean that just initialized mutex by
one thread is ready to be used by another thread.
Thank you for answers.
Want to link to this message? Use this URL: <https://mail-archive.FreeBSD.org/cgi/mid.cgi?20100916173307.GA1994>