From owner-freebsd-hackers@FreeBSD.ORG Thu Sep 16 18:16:08 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 B14BC1065674 for ; Thu, 16 Sep 2010 18:16:08 +0000 (UTC) (envelope-from jhb@freebsd.org) Received: from cyrus.watson.org (cyrus.watson.org [65.122.17.42]) by mx1.freebsd.org (Postfix) with ESMTP id 7EFE88FC1C for ; Thu, 16 Sep 2010 18:16:08 +0000 (UTC) Received: from bigwig.baldwin.cx (66.111.2.69.static.nyinternet.net [66.111.2.69]) by cyrus.watson.org (Postfix) with ESMTPSA id D323646B52; Thu, 16 Sep 2010 14:16:07 -0400 (EDT) Received: from jhbbsd.localnet (smtp.hudson-trading.com [209.249.190.9]) by bigwig.baldwin.cx (Postfix) with ESMTPSA id 8A9128A03C; Thu, 16 Sep 2010 14:16:06 -0400 (EDT) From: John Baldwin To: Andrey Simonenko Date: Thu, 16 Sep 2010 14:16:05 -0400 User-Agent: KMail/1.13.5 (FreeBSD/7.3-CBSD-20100819; KDE/4.4.5; amd64; ; ) References: <20100915134415.GA23727@pm513-1.comsys.ntu-kpi.kiev.ua> <20100916173307.GA1994@pm513-1.comsys.ntu-kpi.kiev.ua> In-Reply-To: <20100916173307.GA1994@pm513-1.comsys.ntu-kpi.kiev.ua> MIME-Version: 1.0 Content-Type: Text/Plain; charset="iso-8859-1" Content-Transfer-Encoding: 7bit Message-Id: <201009161416.05759.jhb@freebsd.org> X-Greylist: Sender succeeded SMTP AUTH, not delayed by milter-greylist-4.0.1 (bigwig.baldwin.cx); Thu, 16 Sep 2010 14:16:06 -0400 (EDT) X-Virus-Scanned: clamav-milter 0.95.1 at bigwig.baldwin.cx X-Virus-Status: Clean X-Spam-Status: No, score=-2.6 required=4.2 tests=AWL,BAYES_00 autolearn=ham version=3.2.5 X-Spam-Checker-Version: SpamAssassin 3.2.5 (2008-06-10) on bigwig.baldwin.cx Cc: freebsd-hackers@freebsd.org, Matthew Fleming 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 18:16:08 -0000 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 > > 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