From owner-freebsd-threads@FreeBSD.ORG Wed Dec 21 15:28:28 2011 Return-Path: Delivered-To: freebsd-threads@freebsd.org Received: from mx1.freebsd.org (mx1.freebsd.org [IPv6:2001:4f8:fff6::34]) by hub.freebsd.org (Postfix) with ESMTP id 6203F106564A; Wed, 21 Dec 2011 15:28:28 +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 1EB858FC0A; Wed, 21 Dec 2011 15:28:28 +0000 (UTC) Received: from bigwig.baldwin.cx (bigwig.baldwin.cx [96.47.65.170]) by cyrus.watson.org (Postfix) with ESMTPSA id AE7A446B09; Wed, 21 Dec 2011 10:28:27 -0500 (EST) Received: from jhbbsd.localnet (unknown [209.249.190.124]) by bigwig.baldwin.cx (Postfix) with ESMTPSA id 3513AB93A; Wed, 21 Dec 2011 10:28:27 -0500 (EST) From: John Baldwin To: "Dag-Erling =?utf-8?q?Sm=C3=B8rgrav?=" Date: Wed, 21 Dec 2011 10:28:26 -0500 User-Agent: KMail/1.13.5 (FreeBSD/8.2-CBSD-20110714-p8; KDE/4.5.5; amd64; ; ) References: <73233.1324389741@critter.freebsd.dk> <86hb0ut1hq.fsf@ds4.des.no> In-Reply-To: <86hb0ut1hq.fsf@ds4.des.no> MIME-Version: 1.0 Content-Type: Text/Plain; charset="utf-8" Content-Transfer-Encoding: quoted-printable Message-Id: <201112211028.26780.jhb@freebsd.org> X-Greylist: Sender succeeded SMTP AUTH, not delayed by milter-greylist-4.2.7 (bigwig.baldwin.cx); Wed, 21 Dec 2011 10:28:27 -0500 (EST) Cc: Poul-Henning Kamp , freebsd-arch@freebsd.org, freebsd-threads@freebsd.org Subject: Re: [Patch] C1X threading support X-BeenThere: freebsd-threads@freebsd.org X-Mailman-Version: 2.1.5 Precedence: list List-Id: Threading on FreeBSD List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , X-List-Received-Date: Wed, 21 Dec 2011 15:28:28 -0000 On Wednesday, December 21, 2011 9:58:57 am Dag-Erling Sm=C3=B8rgrav wrote: > "Poul-Henning Kamp" writes: > > There is no way this can be impossible on a platform which can > > implement a mutex in the first place: > > > > > > mtx_lock(l) > > { > > atomic_magic_lock(l->lock_field) > > l->id =3D thread_id; > > } >=20 > OK >=20 > > mtx_unlock(l) > > { > > assert(l->id =3D=3D thread_id); > > l->id =3D NULL; > > atomic_magic_unlock(l->lock_field) > > } >=20 > susceptible to race conditions How so? Assume that atomic_magic_unlock() uses a release barrier on the store to l->lock_field such that the write to l->id will post to all CPUs before the write to l->lock_field. > > mtx_assert_held(l) > > { > > assert(l->lock-field !=3D 0); > > assert(l->id =3D=3D thread_id); > > } >=20 > susceptible to race conditions How so? While the current thread holds the lock, it is always coherent with the lock's state (it can't read "stale" values because it is the last thread to write to the lock, and if the thread migrates to another CPU, the mechanics of migrating to another CPU will use sufficient barriers that the new CPU will see all the writes done by this thread). Given that, if you hold the lock, the assertions will never fail while the current thread holds the lock. Similarly, the current thread will always see at least the newest values it wrote to the lock (it may also possibly see writes by another thread/CPU to the lock since it last wrote to the lock, but these are not guaranteed). However, that is sufficient to ensure that least one of the above assertions will fail if the current thread does not hold the lock. Recall that the last tokens it writes to the lock when it releases the lock is to clear both the lock_field and id fields. After such writes, mtx_assert_held() will fail. If another thread acquires the lock and the CPU only sees the first write to lock_field, then the first assertion will not trip, but the second one will (the thread will never see the old value where it thinks 'l->id' is itself as it is guaranteed to see a value that is at least as new as it's last write (which set it to NULL), and no other thread is going to set 'l->id' to this thread's ID). Keep in mind, all that you have to guarantee for an assertion of this type is that the observed state will match the 'locked by current thread' state when the mutex is locked and will look like something else when the mutex isn't locked by this thread. The observed state can be stale, but the assertion will still work correctly as it does not depend on the specific details of the non-owned state, merely that it is not equal to the locked staet. We use this same practice to use non-atomic ops on the mtx_recursed field in our in-kernel mutex implementation as well as it is altered only=20 while the main lock field is locked by the current thread. > The canonical solution is to use some low-level lock primitive (worst > case, a critical section) to protect the mutex structure, but then you > need some way for mtx_lock() to sleep if the mutex is held and some way > for mtx_unlock() to wake sleepers. You also need to lock the mutex > structure in mtx_assert_held(), unless l->id is atomic. l->id is not required to be atomic I believe, but it is not hard to make that true. On many platforms pointers do fit in a word and thus their loads and stores are atomic. You could also use a cookie for the thread id that is an atomic type if your pointers are not atomic (just assign a unique integer id to each thread on thread creation, etc.). =2D-=20 John Baldwin