From owner-freebsd-hackers@FreeBSD.ORG Thu Sep 16 17:33:09 2010 Return-Path: Delivered-To: freebsd-hackers@freebsd.org Received: from mx1.freebsd.org (mx1.freebsd.org [IPv6:2001:4f8:fff6::34]) by hub.freebsd.org (Postfix) with ESMTP id 52D7F1065673 for ; Thu, 16 Sep 2010 17:33:09 +0000 (UTC) (envelope-from simon@comsys.ntu-kpi.kiev.ua) Received: from comsys.kpi.ua (comsys.kpi.ua [77.47.192.42]) by mx1.freebsd.org (Postfix) with ESMTP id CC2858FC16 for ; Thu, 16 Sep 2010 17:33:08 +0000 (UTC) Received: from pm513-1.comsys.kpi.ua ([10.18.52.101] helo=pm513-1.comsys.ntu-kpi.kiev.ua) by comsys.kpi.ua with esmtpsa (TLSv1:AES256-SHA:256) (Exim 4.63) (envelope-from ) id 1OwIKZ-00052m-8B; Thu, 16 Sep 2010 20:33:07 +0300 Received: by pm513-1.comsys.ntu-kpi.kiev.ua (Postfix, from userid 1001) id 9A4B81CC1E; Thu, 16 Sep 2010 20:33:07 +0300 (EEST) Date: Thu, 16 Sep 2010 20:33:07 +0300 From: Andrey Simonenko To: Matthew Fleming Message-ID: <20100916173307.GA1994@pm513-1.comsys.ntu-kpi.kiev.ua> References: <20100915134415.GA23727@pm513-1.comsys.ntu-kpi.kiev.ua> MIME-Version: 1.0 Content-Type: text/plain; charset=us-ascii Content-Disposition: inline In-Reply-To: User-Agent: Mutt/1.5.20 (2009-06-14) X-Authenticated-User: simon@comsys.ntu-kpi.kiev.ua X-Authenticator: plain X-Sender-Verify: SUCCEEDED (sender exists & accepts mail) X-Exim-Version: 4.63 (build at 06-Jan-2007 23:14:37) X-Date: 2010-09-16 20:33:07 X-Connected-IP: 10.18.52.101:59547 X-Message-Linecount: 121 X-Body-Linecount: 105 X-Message-Size: 6165 X-Body-Size: 5370 Cc: freebsd-hackers@freebsd.org Subject: Re: Questions about mutex implementation in kern/kern_mutex.c X-BeenThere: freebsd-hackers@freebsd.org X-Mailman-Version: 2.1.5 Precedence: list List-Id: Technical Discussions relating to FreeBSD List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , X-List-Received-Date: Thu, 16 Sep 2010 17:33:09 -0000 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 > 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.