Questions about mutex implementation in kern/kern_mutex.c

[Andrey Simonenko]

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 at 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.