Date: Wed, 21 Dec 2011 07:37:34 -0800 From: mdf@FreeBSD.org To: John Baldwin <jhb@freebsd.org> Cc: =?ISO-8859-1?Q?Dag=2DErling_Sm=F8rgrav?= <des@des.no>, Poul-Henning Kamp <phk@phk.freebsd.dk>, freebsd-threads@freebsd.org, Niall Douglas <s_sourceforge@nedprod.com>, freebsd-arch@freebsd.org Subject: Re: [Patch] C1X threading support Message-ID: <CAMBSHm93z=C30woYScFMRXtp_PxP8kznXQWG64ifR0ZT28QACw@mail.gmail.com> In-Reply-To: <201112211028.26780.jhb@freebsd.org> References: <73233.1324389741@critter.freebsd.dk> <86hb0ut1hq.fsf@ds4.des.no> <201112211028.26780.jhb@freebsd.org>
next in thread | previous in thread | raw e-mail | index | archive | help
2011/12/21 John Baldwin <jhb@freebsd.org>:
> On Wednesday, December 21, 2011 9:58:57 am Dag-Erling Sm=F8rgrav 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:
>> >
>> >
>> > =A0 =A0 mtx_lock(l)
>> > =A0 =A0 {
>> > =A0 =A0 =A0 =A0 =A0 =A0 atomic_magic_lock(l->lock_field)
>> > =A0 =A0 =A0 =A0 =A0 =A0 l->id =3D thread_id;
>> > =A0 =A0 }
>>
>> OK
>>
>> > =A0 =A0 mtx_unlock(l)
>> > =A0 =A0 {
>> > =A0 =A0 =A0 =A0 =A0 =A0 assert(l->id =3D=3D thread_id);
>> > =A0 =A0 =A0 =A0 =A0 =A0 l->id =3D NULL;
>> > =A0 =A0 =A0 =A0 =A0 =A0 atomic_magic_unlock(l->lock_field)
>> > =A0 =A0 }
>>
>> susceptible to race conditions
>
> How so? =A0Assume 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.
... which it has to do if the mutex is to do anything useful. Having
started on PPC assembly, the concept of 'acquire' and 'release'
semantics still make no sense to me. On PPC, the mutex code must
issue a sync before clearing the lock word, to guarantee all stores
performed before the lock is released are visible before any CPU can
see the lock is free. I assume that's the same thing as 'release'
semantics. If this isn't done then a CPU can read a value 'protected'
by the mutex and get wrong information, rendering the mutex
non-functional for memory protection but still function to (for some
reason) have only one thread executing a given section of code at a
time.
If this isn't possible on the hardware (i.e. no memory barrier
instructions) then the hardware cannot implement a mutex with useful
semantics at all. But note that one of PHK's complaints was that the
threaded memory model isn't well specified...
Cheers,
matthew
>> > =A0 =A0 mtx_assert_held(l)
>> > =A0 =A0 {
>> > =A0 =A0 =A0 =A0 =A0 =A0 assert(l->lock-field !=3D 0);
>> > =A0 =A0 =A0 =A0 =A0 =A0 assert(l->id =3D=3D thread_id);
>> > =A0 =A0 }
>>
>> susceptible to race conditions
>
> How so? =A0While 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. =A0Similarly, 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). =A0However, that is
> sufficient to ensure that least one of the above assertions will fail if
> the current thread does not hold the lock. =A0Recall that the last tokens
> it writes to the lock when it releases the lock is to clear both the
> lock_field and id fields. =A0 After such writes, mtx_assert_held() will
> fail. =A0If 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. =A0The observed state can be stale, bu=
t
> 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
> 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. =A0You 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. =A0On many platforms pointers do fit in a word and thus their
> loads and stores are atomic. =A0You could also use a cookie for the threa=
d
> 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.).
>
> --
> John Baldwin
> _______________________________________________
> freebsd-arch@freebsd.org mailing list
> http://lists.freebsd.org/mailman/listinfo/freebsd-arch
> To unsubscribe, send any mail to "freebsd-arch-unsubscribe@freebsd.org"
Want to link to this message? Use this URL: <https://mail-archive.FreeBSD.org/cgi/mid.cgi?CAMBSHm93z=C30woYScFMRXtp_PxP8kznXQWG64ifR0ZT28QACw>