Date: Wed, 21 Dec 2011 10:28:26 -0500 From: John Baldwin <jhb@freebsd.org> To: "Dag-Erling =?utf-8?q?Sm=C3=B8rgrav?=" <des@des.no> Cc: Poul-Henning Kamp <phk@phk.freebsd.dk>, freebsd-arch@freebsd.org, freebsd-threads@freebsd.org Subject: Re: [Patch] C1X threading support Message-ID: <201112211028.26780.jhb@freebsd.org> In-Reply-To: <86hb0ut1hq.fsf@ds4.des.no> References: <73233.1324389741@critter.freebsd.dk> <86hb0ut1hq.fsf@ds4.des.no>
next in thread | previous in thread | raw e-mail | index | archive | help
On Wednesday, December 21, 2011 9:58:57 am Dag-Erling Sm=C3=B8rgrav wrote:
> "Poul-Henning Kamp" <phk@phk.freebsd.dk> 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
Want to link to this message? Use this URL: <https://mail-archive.FreeBSD.org/cgi/mid.cgi?201112211028.26780.jhb>