Posix saftey wrt to the ebusy...
SenderX
mutex anytime its unlocked...
"It shall be safe to destroy an initialized mutex that is unlocked.
Attempting to destroy a locked mutex results in undefined behavior."
^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
and
"The [EBUSY] and [EINVAL] error checks, if implemented, act as if they were
performed immediately at the beginning of processing for the function and
shall cause an error return prior to modifying the state of the mutex
specified by mutex."
This part of the standard seems to be allowing for a race-condition to
happen wrt pthread_mutex_delete and ebusy...
Doesn't that statement render the following code safe, in the eyes of the
POSIX std?
pthread_mutex_lock( &AnyMutex );
pthread_mutex_unlock( &AnyMutex );
pthread_mutex_delete( &AnyMutex );
If it does, some sort of global locking or garbage collection would be
needed in order to strictly conform to the standard?
The reason I ask, is because I am trying to get my pthread implementation to
fully conform to POSIX std.
Sebastien Decugis
>pthread_mutex_lock( &AnyMutex );
>pthread_mutex_unlock( &AnyMutex );
>pthread_mutex_delete( &AnyMutex );
>
>
Assuming that you mean pthread_mutex_destroy, this code is correct IMHO.
I really don't understand what is the race condition you're seeing...
Seb.
SenderX
Yeah, pthread_mutex_destroy my bad... Need coffee!
> I really don't understand what is the race condition you're seeing...
http://groups.google.com/groups?selm=hxlJc.57685%24WX.9480%40attbi_s51
http://groups.google.com/groups?selm=OaVhc.4026%24cF6.188491%40attbi_s04&rnum=6
Alexander Terekhov
SenderX wrote: ...
pthread_mutex_destoy may (optionally) report EBUSY as an
indication of a bug -- violation of a precondition.
> The reason I ask, is because I am trying to get my pthread implementation to
> fully conform to POSIX std.
http://lists.boost.org/MailArchives/boost/msg67616.php
http://lists.boost.org/MailArchives/boost/msg67651.php
http://lists.boost.org/MailArchives/boost/msg67667.php
regards,
alexander.
Sebastien Decugis
>>I really don't understand what is the race condition you're seeing...
>>
>>
>
>http://groups.google.com/groups?selm=hxlJc.57685%24WX.9480%40attbi_s51
>http://groups.google.com/groups?selm=OaVhc.4026%24cF6.188491%40attbi_s04&rnum=6
>
>
thread... so it is not unlocked. It is safe to call
pthread_mutex_destroy when the mutex is free -- i.e. nobody (threads or
processes if the mutex is process-shared) owns it. And once the mutex is
destroyed, it cannot be locked again, even in another thread, before
being initialized again.
Sebastien.
--
-------------------------------
Sebastien DECUGIS
NPTL Test & Trace Project
http://nptl.bullopensource.org/
SenderX
"Alexander Terekhov" <tere...@web.de> wrote in message
news:41233CBC...@web.de...
--------
t0: thread A locks the mutex and decrements refcount to 2;
t1: thread B does m_lock_status.swap(1, msync::acq) on the
fast path and sees 1;
t2: thread A unlocks the mutex (doesn't enter slow path);
t3: thread B does mutex m_lock_status.swap(-1, msync::acq),
locks the mutex, decrements refcount to 1, does
m_lock_status.swap(0, msync::rel) and enters slow path
in unlock();
t4: thread A locks the mutex, decrements refcount to 0,
unlocks the mutex, and destroys it (including event);
t5: thread B goes BOOM.
-----------
If t4 would simply defer the call to the mutex dtor until t5, or any other
thread, has completely finished using it. Problem solved... No?
Alexander Terekhov
SenderX wrote:
[...]
> t4: thread A locks the mutex, decrements refcount to 0,
> unlocks the mutex, and destroys it (including event);
>
> t5: thread B goes BOOM.
> -----------
>
> If t4 would simply defer the call to the mutex dtor until t5, or any other
> thread, has completely finished using it. Problem solved... No?
Yeah, GC would solve it. Absent "real" GC, never deleting mutex
events (reuse is OK; the scheme can handle spurious wakes) is
the best approach. But "lock queue" ("token" based, with waiters
bit and allowing spurious wakes) kernel thing would be much-much
better, of course.
regards,
alexander.
Joe Seigh
SenderX wrote:
>
> --------
> t0: thread A locks the mutex and decrements refcount to 2;
>
> t1: thread B does m_lock_status.swap(1, msync::acq) on the
> fast path and sees 1;
>
> t2: thread A unlocks the mutex (doesn't enter slow path);
>
> t3: thread B does mutex m_lock_status.swap(-1, msync::acq),
> locks the mutex, decrements refcount to 1, does
> m_lock_status.swap(0, msync::rel) and enters slow path
> in unlock();
>
> t4: thread A locks the mutex, decrements refcount to 0,
> unlocks the mutex, and destroys it (including event);
>
> t5: thread B goes BOOM.
> -----------
>
> If t4 would simply defer the call to the mutex dtor until t5, or any other
> thread, has completely finished using it. Problem solved... No?
Ok, I see what you're getting at. You're talking about accessing some
synchronization object while not holding the mutex lock. Well, you
refcount the synchronization object. Increment the refcount before
releasing the mutex and decrement it after the synchronization operation.
That's the technique I use in the win32 condvar implementation I did.
Joe Seigh
Joe Seigh
"lock queue"? Futex stuff or something?
I was looking at the current futex condvar and barrier implementations.
They seem awfully fond of using mutexes. I think I can do all that
without internal mutexes.
Joe Seigh
Alexander Terekhov
Joe Seigh wrote:
[...]
> "lock queue"? Futex stuff or something?
Yeah. But sorta "refined" (with waiters bit, etc.)
mutex_lock:
WHILE
atomic_bit_test_set_cdacq(&lock, 1)
lock_queue_wait(&lock, 1) // wait if locked bit is set
mutex_unlock:
uintptr_t lock_queue;
IF atomic_decrement_rel(lock_queue = &lock)
THEN lock_queue_wake(lock_queue, 1)
mutex_dtor:
RETURN
For semas,
sema_lock:
WHILE // CAS/LL-SC
!atomic_decrement_if_binand_7FFFFFFF_is_not_zero_cdacq(&lock)
lock_queue_wait(&lock, 0) // wait if sem.value is zero
sema_unlock:
uintptr_t lock_queue;
IF atomic_increment_rel(lock_queue = &lock) > 0x80000000
THEN lock_queue_wake(lock_queue, 1)
sema_dtor:
RETURN
(try/timed operations omitted for brevity)
There shall be no requirement to "open/close" that park/unpark
mechanism (physical address shall be used as "wait token"). And
it shall be safe to pass an "invalid" (even unmapped/nonexistent)
queue-id/virtual address to a wake call... in worse case it would
result in spurious wakes but spurious wakes shall be allowed
anyway.
"cdacq" is "acq" but with control dependency. On many archs it
needs no barriers.
>
> I was looking at the current futex condvar
NPTL's condvar is nonconforming to begin with.
> and barrier implementations.
NTPL's barrier implementation is also totally brain-dead.
> They seem awfully fond of using mutexes. I think I can do all that
> without internal mutexes.
Yup.
regards,
alexander.
Alexander Terekhov
Alexander Terekhov wrote:
[...]
> mutex_unlock:
>
> uintptr_t lock_queue;
> IF atomic_decrement_rel(lock_queue = &lock)
> THEN lock_queue_wake(lock_queue, 1)
IF atomic_swap_rel(lock_queue = &lock, 0) < 0 // or > 1
THEN lock_queue_wake(lock_queue, 1)
would also work. lock_queue_wake() would have to set waiters bit,
not clear it (that's the case with decrement).
regards,
alexander.
Joe Seigh
Alexander Terekhov wrote:
>
> Joe Seigh wrote:
...
> >
> > I was looking at the current futex condvar
>
> NPTL's condvar is nonconforming to begin with.
In what way? I didn't go through it with that in mind.
>
> > and barrier implementations.
>
> NTPL's barrier implementation is also totally brain-dead.
>
> > They seem awfully fond of using mutexes. I think I can do all that
> > without internal mutexes.
>
> Yup.
>
I meant both barrier and condvar can be done lock-free. Though it probably
doesn't matter with barrier as it's pretty much guaranteed to block anyway.
Joe Seigh
Alexander Terekhov
Joe Seigh wrote:
[...]
> > NPTL's condvar is nonconforming to begin with.
>
> In what way? I didn't go through it with that in mind.
Your windows condvar had the same problem. pthread_cond_destroy()
must be synchronized with respect to unblocked waiters (your lovely
counting GC stuff aside for a moment ;-) ) if they can touch the
condvar on the "exit path" after being unblocked. SUS mandates it.
[...]
> I meant both barrier and condvar can be done lock-free.
Condvar is interesting. Excessive tricking around in the userspace
is not worth the effort. The overhead of calling the kernel with
user's mutex locked and letting the kernel to unlock it (relocking
can be done in the userspace) is rather small. It's more important
to optimize both pthread_cond_signal() and pthread_cond_broadcast().
Signalling with no {visible} waiters shall be inexpensive/fast and
wait-morphing shall be used by both.
> Though it probably
> doesn't matter with barrier as it's pretty much guaranteed to block anyway.
Sort of. I meant that it makes no sense to do anything at all in
the userspace as long as you're always going to enter the kernel.
regards,
alexander.
Joe Seigh
Alexander Terekhov wrote:
>
> Joe Seigh wrote:
> [...]
> > > NPTL's condvar is nonconforming to begin with.
> >
> > In what way? I didn't go through it with that in mind.
>
> Your windows condvar had the same problem. pthread_cond_destroy()
> must be synchronized with respect to unblocked waiters (your lovely
> counting GC stuff aside for a moment ;-) ) if they can touch the
> condvar on the "exit path" after being unblocked. SUS mandates it.
Well, my win32 condvar didn't claim to be Posix compliant though it
was easy enough to "fix" with GC.
>
> [...]
> > I meant both barrier and condvar can be done lock-free.
>
> Condvar is interesting. Excessive tricking around in the userspace
> is not worth the effort. The overhead of calling the kernel with
> user's mutex locked and letting the kernel to unlock it (relocking
> can be done in the userspace) is rather small. It's more important
> to optimize both pthread_cond_signal() and pthread_cond_broadcast().
> Signalling with no {visible} waiters shall be inexpensive/fast and
> wait-morphing shall be used by both.
You can do it without excessive tricking around using the current
futex interface. I should patent it and make money supplying an alternate
pthread library that performs better.
Joe Seigh
Alexander Terekhov
Joe Seigh wrote:
[...]
> You can do it without excessive tricking around using the current
Well, I can sign an NDA. I don't think that you can do it (i.e.
POSIX/SUS conforming condvar without excessive tricking around)
using the current futex interface.
regards,
alexander.
Joe Seigh
Your employer let's you sign NDA's with 3rd parties?
No excessive tricking around unless you call lock-free excessive
tricking around. No hints. I probably wouldn't actually
patent it but if Microsoft called me up to talk about preventing
"valuable" technology from falling into the hands of the "enemy",
I'd listen. :)
And it does seem that futex does have that problem Senderx has
been talking about, "token" not withstanding. So you do need
to GC futexes. RCU would be a good solution.
Joe Seigh
Alexander Terekhov
Joe Seigh wrote:
[...]
> > > You can do it without excessive tricking around using the current
> > > futex interface. I should patent it and make money supplying ...
> >
> > Well, I can sign an NDA. I don't think that you can do it (i.e.
> > POSIX/SUS conforming condvar without excessive tricking around)
> > using the current futex interface.
> >
>
> Your employer let's you sign NDA's with 3rd parties?
What does it have to do with my employer? I mean an NDA between you
and me (not my employer). It's your secret, oder?
regards,
alexander.
Joe Seigh
> And it does seem that futex does have that problem Senderx has
> been talking about, "token" not withstanding. So you do need
> to GC futexes. RCU would be a good solution.
>
condvars itself.
Out of curiosity, are there any compliant solutions that aren't
suboptimal, e.g. using a global kernel spin lock or something
like that? I have an non-suboptimal solution, though maybe
not the most elegant. I have a morbid interest in what the
self inflicted wounds from strict adherence to Posix look like.
Joe Seigh