Re: new semapahore implementation using atomics and futexes

[Martin Pieuchot]

On 09/05/18(Wed) 14:19, Paul Irofti wrote:
> > [...]
> > I'd prefer if we could teach each other how stuff really work :o)
> 
> Frankly someone else will have to enlighten me (or us) if we really
> need to do this.

That's what guenther@ and visa@ did.  So I believe you should move
forward and commit this.  Make sure the archs list contain all the
new shiny FUTEX archs and don't forget the *_compat.c version :)

With all of that ok mpi@.

> diff --git lib/librthread/Makefile lib/librthread/Makefile
> index 4c3e127491d..5dfb140290e 100644
> --- lib/librthread/Makefile
> +++ lib/librthread/Makefile
> @@ -30,12 +30,19 @@ SRCS= rthread.c \
>   rthread_rwlock.c \
>   rthread_rwlockattr.c \
>   rthread_sched.c \
> - rthread_sem.c \
>   rthread_sig.c \
>   rthread_stack.c \
>   rthread_spin_lock.c \
>   sched_prio.c
>  
> +# Architectures that implement atomics
> +.if ${MACHINE_ARCH} == "amd64" || ${MACHINE_ARCH} == "i386" || \
> +${MACHINE_ARCH} == "mips64" || ${MACHINE_ARCH} == "mips64el"
> +SRCS+=   rthread_sem_atomic.c
> +.else
> +SRCS+=   rthread_sem.c
> +.endif
> +
>  SRCDIR= ${.CURDIR}/../libpthread
>  .include "${SRCDIR}/man/Makefile.inc"
>  .include 
> diff --git lib/librthread/rthread_sem_atomic.c 
> lib/librthread/rthread_sem_atomic.c
> new file mode 100644
> index 000..c2de5d25de2
> --- /dev/null
> +++ lib/librthread/rthread_sem_atomic.c
> @@ -0,0 +1,429 @@
> +/*   $OpenBSD$ */
> +/*
> + * Copyright (c) 2004,2005,2013 Ted Unangst 
> + * Copyright (c) 2018 Paul Irofti 
> + * All Rights Reserved.
> + *
> + * Permission to use, copy, modify, and distribute this software for any
> + * purpose with or without fee is hereby granted, provided that the above
> + * copyright notice and this permission notice appear in all copies.
> + *
> + * THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES
> + * WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF
> + * MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR
> + * ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES
> + * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN
> + * ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF
> + * OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE.
> + */
> +
> +#include 
> +#include 
> +#include 
> +#include 
> +#include 
> +#include 
> +
> +#include 
> +#include 
> +#include 
> +#include 
> +#include 
> +#include 
> +#include 
> +#include 
> +
> +#include 
> +
> +#include "rthread.h"
> +#include "cancel.h"  /* in libc/include */
> +#include "synch.h"
> +
> +#define SHARED_IDENT ((void *)-1)
> +
> +/* SHA256_DIGEST_STRING_LENGTH includes nul */
> +/* "/tmp/" + sha256 + ".sem" */
> +#define SEM_PATH_SIZE (5 + SHA256_DIGEST_STRING_LENGTH + 4)
> +
> +/* long enough to be hard to guess */
> +#define SEM_RANDOM_NAME_LEN  10
> +
> +/*
> + * Size of memory to be mmap()'ed by named semaphores.
> + * Should be >= SEM_PATH_SIZE and page-aligned.
> + */
> +#define SEM_MMAP_SIZE_thread_pagesize
> +
> +/*
> + * Internal implementation of semaphores
> + */
> +int
> +_sem_wait(sem_t sem, int can_eintr, const struct timespec *abstime,
> +int *delayed_cancel)
> +{
> + int r = 0;
> + int v, ov;
> +
> + atomic_inc_int(>waitcount);
> + for (;;) {
> + while ((v = sem->value) > 0) {
> + ov = atomic_cas_uint(>value, v, v - 1);
> + if (ov == v) {
> + membar_enter_after_atomic();
> + atomic_dec_int(>waitcount);
> + return 0;
> + }
> + }
> + if (r)
> + break;
> +
> + r = _twait(>value, 0, CLOCK_REALTIME, abstime);
> + /* ignore interruptions other than cancelation */
> + if ((r == ECANCELED && *delayed_cancel == 0) ||
> + (r == EINTR && !can_eintr) || r == EAGAIN)
> + r = 0;
> + }
> + atomic_dec_int(>waitcount);
> +
> + return r;
> +}
> +
> +/* always increment count */
> +int
> +_sem_post(sem_t sem)
> +{
> + membar_exit_before_atomic();
> + atomic_inc_int(>value);
> + _wake(>value, 1);
> + return 0;
> +}
> +
> +/*
> + * exported semaphores
> + */
> +int
> +sem_init(sem_t *semp, int pshared, unsigned int value)
> +{
> + sem_t sem;
> +
> + if (value > SEM_VALUE_MAX) {
> + errno = EINVAL;
> + return (-1);
> + }
> +
> + if (pshared) {
> + errno = EPERM;
> + return (-1);
> +#ifdef notyet
> + char name[SEM_RANDOM_NAME_LEN];
> + sem_t *sempshared;
> + int i;
> +
> + for (;;) {
> + for (i = 0; i < SEM_RANDOM_NAME_LEN - 1; i++)
> + name[i] = arc4random_uniform(255) + 1;
> + 

Re: new semapahore implementation using atomics and futexes

[Martin Pieuchot]

On 09/05/18(Wed) 13:07, Paul Irofti wrote:
> On Wed, May 09, 2018 at 11:33:06AM +0200, Martin Pieuchot wrote:
> > On 09/05/18(Wed) 11:43, Paul Irofti wrote:
> > [...] 
> > Then the writer uses atomic operations to increment/decrement `waitcount'
> > but is it enough to have the reader, see the updated value?
> 
> On x86 I think it is guaranteed. Not sure about others or if we need
> membars here too. Visa said membars are not needed in this case for
> mips.

Good, what about other archs?

> > What if the
> > check is done before the atomic operation has been performed?
> 
> Then we should probably wrap the for (;;;) loop in atomic increments and
> decrements.

That's would be better, but then...

> atomic_inc_int(>waitcount);
> for (;;) {
> while ((v = sem->value) > 0) {
> ov = atomic_cas_uint(>value, v, v - 1);
> if (ov == v) {
> membar_enter_after_atomic();
  ^
...don't forget to break or decrease `waitcount' here :)
> return 0;
> }
> }
> if (r)
> break;
> 
> r = _twait(>value, 0, CLOCK_REALTIME, abstime);
> /* ignore interruptions other than cancelation */
> if ((r == ECANCELED && *delayed_cancel == 0) ||
> (r == EINTR && !can_eintr) || r == EAGAIN)
> r = 0;
> }
> atomic_dec_int(>waitcount);
> 
> 
> > Worst
> > what if the cache of the reader doesn't contain the last value?
> 
> The way to be absolutely sure is to also do an atomic operation when
> reading the waitcount in sem_destroy.
> 
> If we decide to be that paranoid, we should do the same for
> sem_getvalue() :)

I'd prefer if we could teach each other how stuff really work :o)

Re: new semapahore implementation using atomics and futexes

[Paul Irofti]

On Wed, May 09, 2018 at 11:33:06AM +0200, Martin Pieuchot wrote:
> On 09/05/18(Wed) 11:43, Paul Irofti wrote:
> > > [...] 
> > > I'm saying that increasing/decreasing `waitcount' now serves a single
> > > purpose: the check in sem_destroy().  However with your implementation
> > > this check is racy and adds two atomic operation on top of every
> > > syscall.  So my question is could you rewrite the check in sem_destroy()
> > > differently?
> > 
> > waitcount was used for the same purpose in the old (compat)
> > implementation. The ident bit did not matter all that much as any other
> > sem field could have been used instead.
> 
> In the old implementation `waitcount' is used to let decide if sem_post()
> needs to do a wakeup.  In that implementation the field is protected by a
> spinlock().
> 
> > I do not understand how the current implementation is racy.
> 
> If a thread is in the while() loop of _sem_wait() it is waiting, but you
> do not increment `waitcount'.


Because it is not actually waiting to be woken up. It is waiting to
decrement sem->value. Waiters lists the number of threads that are
blocked on the semaphore because sem->value is zero.
So there are no waiters at that point.

> Then the writer uses atomic operations to increment/decrement `waitcount'
> but is it enough to have the reader, see the updated value?

On x86 I think it is guaranteed. Not sure about others or if we need
membars here too. Visa said membars are not needed in this case for
mips.

> What if the
> check is done before the atomic operation has been performed?

Then we should probably wrap the for (;;;) loop in atomic increments and
decrements.


atomic_inc_int(>waitcount);
for (;;) {
while ((v = sem->value) > 0) {
ov = atomic_cas_uint(>value, v, v - 1);
if (ov == v) {
membar_enter_after_atomic();
return 0;
}
}
if (r)
break;

r = _twait(>value, 0, CLOCK_REALTIME, abstime);
/* ignore interruptions other than cancelation */
if ((r == ECANCELED && *delayed_cancel == 0) ||
(r == EINTR && !can_eintr) || r == EAGAIN)
r = 0;
}
atomic_dec_int(>waitcount);


> Worst
> what if the cache of the reader doesn't contain the last value?

The way to be absolutely sure is to also do an atomic operation when
reading the waitcount in sem_destroy.

If we decide to be that paranoid, we should do the same for
sem_getvalue() :)

> What I'm just saying is that, in my opinion, adding 2 atomic operations
> on top of the syscall is not worth it.

This might be so performance wise. But I am not sure about correctness.

> Why not check `sem->value' instead?

Because it can happen that sem->value is zero and no threads are
stuck in sem_wait() which means nobody is using the semaphore.
So I should be able to destroy it.

Re: new semapahore implementation using atomics and futexes

[Martin Pieuchot]

On 09/05/18(Wed) 11:43, Paul Irofti wrote:
> > [...] 
> > I'm saying that increasing/decreasing `waitcount' now serves a single
> > purpose: the check in sem_destroy().  However with your implementation
> > this check is racy and adds two atomic operation on top of every
> > syscall.  So my question is could you rewrite the check in sem_destroy()
> > differently?
> 
> waitcount was used for the same purpose in the old (compat)
> implementation. The ident bit did not matter all that much as any other
> sem field could have been used instead.

In the old implementation `waitcount' is used to let decide if sem_post()
needs to do a wakeup.  In that implementation the field is protected by a
spinlock().

> I do not understand how the current implementation is racy.

If a thread is in the while() loop of _sem_wait() it is waiting, but you
do not increment `waitcount'.

Then the writer uses atomic operations to increment/decrement `waitcount'
but is it enough to have the reader, see the updated value?  What if the
check is done before the atomic operation has been performed?  Worst
what if the cache of the reader doesn't contain the last value?

What I'm just saying is that, in my opinion, adding 2 atomic operations
on top of the syscall is not worth it.

Why not check `sem->value' instead?

Re: new semapahore implementation using atomics and futexes

[Paul Irofti]

> > > > new file mode 100644
> > > > index 000..e5c8015d27c
> > > > --- /dev/null
> > > > +++ lib/librthread/rthread_sem_atomic.c
> > > 
> > > I'm not fan of the _atomic suffix.  What about rthread_semaphore.c?
> > 
> > I am not set on the name, but I do think rthread_semaphore is not a good
> > option as it only adds confusion. Why is one _sem and another
> > _semaphore? There is no info in that naming scheme.
> 
> I'm hoping that in the long run we get rid of all __thrsleep(2) based
> functions.  So I don't see a point of naming the file based on which
> underlying syscall it uses.
> 
> Maybe we should take the other approach and copy the existing
> implementation into a rthread_sem_compat.c and use rthread_sem.c for
> your new implementation.

That sounds a lot better to me. I will include this renaming in the
final diff as otherwise it gets harder to read.

> > > > +   for (;;) {
> > > > +   while ((v = sem->value) > 0) {
> > > > +   ov = atomic_cas_uint(>value, v, v - 1);
> > > > +   if (ov == v) {
> > > > +   membar_enter_after_atomic();
> > > > +   return 0;
> > > > +   }
> > > > +   }
> > > > +   if (r)
> > > > +   break;
> > > > +
> > > > +   atomic_inc_int(>waitcount);
> > > 
> > > Can you keep the destroy check without adding two atomic operations here?
> > 
> > I don't understand what you mean here. What destroy check? How can I get
> > rid of the atomic inc/dec? Should I do the operations without atomics?
> > Is that what you mean?
> 
> I'm saying that increasing/decreasing `waitcount' now serves a single
> purpose: the check in sem_destroy().  However with your implementation
> this check is racy and adds two atomic operation on top of every
> syscall.  So my question is could you rewrite the check in sem_destroy()
> differently?

waitcount was used for the same purpose in the old (compat)
implementation. The ident bit did not matter all that much as any other
sem field could have been used instead.

I do not understand how the current implementation is racy.

Let's say we have two threads, T0 and T1, and that waitcount equals 1.
T0 just came back from _twait() and is about to do a decrement of
waitcount. At the same time, T1 is about to call sem_destroy() on the
same semaphore.

If T0 decrements first, T1 succedes and all is well.
If T0 decrements last, T1 fails with EBUSY and the caller has to retry.
So again, if I am not mistaken all is well.

There might be a "race" between incrementing and destroying a semapahore
with 0 waitcount. But I don't think we have any control over that. With
atomics or without.

What my diff adds from the compat implementation is atomic increments
and decrements of waitcount. I did this in order to ensure that, for
example, two threads on two CPUs do not increment the counter at the
same time. And I think it is better like this than with the compat
implemnetation.


> 
> > > > +   }
> > > > +   sem->lock = _SPINLOCK_UNLOCKED;
> > > 
> > > `sem->lock' is no longer unused and can be #ifdef out.
> > 
> > Good catch!
> 
> But you forgot the thread_private.h diff in your new version :)
> 
> > > > +   //membar_exit_before_atomic();
> > > > +   //*sval = atomic_add_int_nv(>value, 0);
> > > 
> > > What does that mean?
> > 
> > I wasn't sure that I can do just a read of the semaphore value (without 
> > locking)
> > so I left the potential locking code commented out in case the review
> > process will point out that it is indeed needed.
> 
> 'struct pthread_mutex' has its `lock' member as first argument to help
> thinking about alignment for this reason.  I'd suggest you do the same
> ;)

I will remove that member when rthread_sem_compat.c will also be
removed from the tree. Otherwise I will need to create an ifdef maze.

Re: new semapahore implementation using atomics and futexes

[Martin Pieuchot]

On 07/05/18(Mon) 14:01, Paul Irofti wrote:
> > > > > The reason we need this is to make semaphores safe for asynchronous
> > > > > signals.
> > 
> > Could you describe with words what is currently broken and how the
> > version below fixes it?
> 
> POSIX dictates that sem_post() needs to be async-safe here[0] and is
> thus included in the list of safe functions to call from within a signal
> handler here[1].
> 
> The old semaphore implementation is using spinlocks and __thrsleep to
> synchronize between threads. 
> 
> Let's say there are two threads: T0 and T1 and the semaphore has V=0.
> T1 calls sem_wait() and it will now sleep (spinlock) until someone else
> sem_post()'s. Let's say T0 sends a signal to T1 and exits.
> The signal handler calls sem_post() which is meant to unblock T1 by
> incrementing V. With the old semaphore implementation we we are now in a
> deadlock as sem_post spinlocks on the same lock.
> 
> The implementation I am proposing does not suffer from this defect as it
> uses futexes to resolve locking and thus sem_post does not need to spin.
> Besides fixing this defect and making us POSIX compliant, this should
> also improve performance as there should be less context switching and
> thus less time spent in the kernel.

Nice!

> > >   The barriers bit is mostly from visa@, thanks!
> > > 
> > >   tb@ found offlineimap faulting because the futex syscall returned EAGAIN
> > >   and sem_wait exited. Loop again on EAGAIN.
> > > 
> > >   Debug printfs are for future debugging.
> > > 
> > > Martin, is handling EAGAIN like this correct?
> > 
> > I don't know, what is it supposed to do? 
> 
> It is supposed to recall _twait is the futex syscall returned EAGAIN.

Yes, it is correct.  If the semaphore value changed between the read and
the syscall you should try to swap it again.

> > > new file mode 100644
> > > index 000..e5c8015d27c
> > > --- /dev/null
> > > +++ lib/librthread/rthread_sem_atomic.c
> > 
> > I'm not fan of the _atomic suffix.  What about rthread_semaphore.c?
> 
> I am not set on the name, but I do think rthread_semaphore is not a good
> option as it only adds confusion. Why is one _sem and another
> _semaphore? There is no info in that naming scheme.

I'm hoping that in the long run we get rid of all __thrsleep(2) based
functions.  So I don't see a point of naming the file based on which
underlying syscall it uses.

Maybe we should take the other approach and copy the existing
implementation into a rthread_sem_compat.c and use rthread_sem.c for
your new implementation.

> > > + for (;;) {
> > > + while ((v = sem->value) > 0) {
> > > + ov = atomic_cas_uint(>value, v, v - 1);
> > > + if (ov == v) {
> > > + membar_enter_after_atomic();
> > > + return 0;
> > > + }
> > > + }
> > > + if (r)
> > > + break;
> > > +
> > > + atomic_inc_int(>waitcount);
> > 
> > Can you keep the destroy check without adding two atomic operations here?
> 
> I don't understand what you mean here. What destroy check? How can I get
> rid of the atomic inc/dec? Should I do the operations without atomics?
> Is that what you mean?

I'm saying that increasing/decreasing `waitcount' now serves a single
purpose: the check in sem_destroy().  However with your implementation
this check is racy and adds two atomic operation on top of every
syscall.  So my question is could you rewrite the check in sem_destroy()
differently?

> > > + }
> > > + sem->lock = _SPINLOCK_UNLOCKED;
> > 
> > `sem->lock' is no longer unused and can be #ifdef out.
> 
> Good catch!

But you forgot the thread_private.h diff in your new version :)

> > > + //membar_exit_before_atomic();
> > > + //*sval = atomic_add_int_nv(>value, 0);
> > 
> > What does that mean?
> 
> I wasn't sure that I can do just a read of the semaphore value (without 
> locking)
> so I left the potential locking code commented out in case the review
> process will point out that it is indeed needed.

'struct pthread_mutex' has its `lock' member as first argument to help
thinking about alignment for this reason.  I'd suggest you do the same
;)

Re: new semapahore implementation using atomics and futexes

[Paul Irofti]

> > > > The reason we need this is to make semaphores safe for asynchronous
> > > > signals.
> 
> Could you describe with words what is currently broken and how the
> version below fixes it?

POSIX dictates that sem_post() needs to be async-safe here[0] and is
thus included in the list of safe functions to call from within a signal
handler here[1].

The old semaphore implementation is using spinlocks and __thrsleep to
synchronize between threads. 

Let's say there are two threads: T0 and T1 and the semaphore has V=0.
T1 calls sem_wait() and it will now sleep (spinlock) until someone else
sem_post()'s. Let's say T0 sends a signal to T1 and exits.
The signal handler calls sem_post() which is meant to unblock T1 by
incrementing V. With the old semaphore implementation we we are now in a
deadlock as sem_post spinlocks on the same lock.

The implementation I am proposing does not suffer from this defect as it
uses futexes to resolve locking and thus sem_post does not need to spin.
Besides fixing this defect and making us POSIX compliant, this should
also improve performance as there should be less context switching and
thus less time spent in the kernel.

[0] -- http://pubs.opengroup.org/onlinepubs/9699919799/functions/sem_post.html
[1] -- http://pubs.opengroup.org/onlinepubs/9699919799/functions/V2_chap02.html

> 
> > > > [...]
> > > Here is the same diff adapted to what happened in -current this week.
> > > All required bits are now in, so the current diff neatly contains just the
> > > implementation.
> > 
> > People started testing this, thank you!
> > 
> > Here is an updated diff that:
> > 
> >   Add barriers, debug printfs and handle EAGAIN.
> 
> You can't use printf() for this purpose.  Please use _rthread_debug()
> like the rest of the library :)  It also has the advantage of being
> enabled via the RTHREAD_DEBUG env variable.

OK.

> >   The barriers bit is mostly from visa@, thanks!
> > 
> >   tb@ found offlineimap faulting because the futex syscall returned EAGAIN
> >   and sem_wait exited. Loop again on EAGAIN.
> > 
> >   Debug printfs are for future debugging.
> > 
> > Martin, is handling EAGAIN like this correct?
> 
> I don't know, what is it supposed to do? 

It is supposed to recall _twait is the futex syscall returned EAGAIN.

> > new file mode 100644
> > index 000..e5c8015d27c
> > --- /dev/null
> > +++ lib/librthread/rthread_sem_atomic.c
> 
> I'm not fan of the _atomic suffix.  What about rthread_semaphore.c?

I am not set on the name, but I do think rthread_semaphore is not a good
option as it only adds confusion. Why is one _sem and another
_semaphore? There is no info in that naming scheme.

rthread_sem_futex?

> > +int
> > +_sem_wait(sem_t sem, int can_eintr, const struct timespec *abstime,
> > +int *delayed_cancel)
> > +{
> > +   int r = 0;
> > +   int v = sem->value, ov;
> 
> Reading `sem->value' here is superfluous.

Right, fixed.

> > +
> > +   for (;;) {
> > +   while ((v = sem->value) > 0) {
> > +   ov = atomic_cas_uint(>value, v, v - 1);
> > +   if (ov == v) {
> > +   membar_enter_after_atomic();
> > +   return 0;
> > +   }
> > +   }
> > +   if (r)
> > +   break;
> > +
> > +   atomic_inc_int(>waitcount);
> 
> Can you keep the destroy check without adding two atomic operations here?

I don't understand what you mean here. What destroy check? How can I get
rid of the atomic inc/dec? Should I do the operations without atomics?
Is that what you mean?

> > +   r = _twait(>value, 0, CLOCK_REALTIME, abstime);
> > +   /* ignore interruptions other than cancelation */
> > +   if ((r == ECANCELED && *delayed_cancel == 0) ||
> > +   (r == EINTR && !can_eintr) || r == EAGAIN)
> > +   r = 0;
> > +   atomic_dec_int(>waitcount);
> > +   }
> > +
> > +   return r;
> > +}
> > +
> > +/* always increment count */
> > +int
> > +_sem_post(sem_t sem)
> > +{
> 
> This function is called only once, so you can fold it in sem_post() :)

I did that first, but I soon found out that it is also called from _rthread.c

> > +   membar_exit_before_atomic();
> 
> Why is the membar needed here?  Does that mean we're missing two in 
> pthread_cond_signal() and pthread_cond_broadcast()?

We might. From what visa@ explained, non-x86 (mips in this case)
architectures do not ensure that one core sees what the other just wrote
and memory barriers are explicitly needed in that case.

> > +   }
> > +   sem->lock = _SPINLOCK_UNLOCKED;
> 
> `sem->lock' is no longer unused and can be #ifdef out.

Good catch!

> > +
> > +   //membar_exit_before_atomic();
> > +   //*sval = atomic_add_int_nv(>value, 0);
> 
> What does that mean?

I wasn't sure that I can do just a read of the semaphore value (without locking)
so I left the potential locking code commented out in case the review
process will point out that it is indeed 

Re: new semapahore implementation using atomics and futexes

[Martin Pieuchot]

On 30/04/18(Mon) 14:36, Paul Irofti wrote:
> On Sat, Apr 28, 2018 at 07:40:38PM +0300, Paul Irofti wrote:
> > On Sun, Apr 22, 2018 at 03:34:45PM +0300, Paul Irofti wrote:
> > > Here is a new semaphore implementation that uses atomic operations,
> > > where available, and futexes for locking. 

I'm happy to see more rthread internals based on futex(2).

> > > The reason we need this is to make semaphores safe for asynchronous
> > > signals.

Could you describe with words what is currently broken and how the
version below fixes it?

> > > [...]
> > Here is the same diff adapted to what happened in -current this week.
> > All required bits are now in, so the current diff neatly contains just the
> > implementation.
> 
> People started testing this, thank you!
> 
> Here is an updated diff that:
> 
>   Add barriers, debug printfs and handle EAGAIN.

You can't use printf() for this purpose.  Please use _rthread_debug()
like the rest of the library :)  It also has the advantage of being
enabled via the RTHREAD_DEBUG env variable.

>   The barriers bit is mostly from visa@, thanks!
> 
>   tb@ found offlineimap faulting because the futex syscall returned EAGAIN
>   and sem_wait exited. Loop again on EAGAIN.
> 
>   Debug printfs are for future debugging.
> 
> Martin, is handling EAGAIN like this correct?

I don't know, what is it supposed to do? 

> new file mode 100644
> index 000..e5c8015d27c
> --- /dev/null
> +++ lib/librthread/rthread_sem_atomic.c

I'm not fan of the _atomic suffix.  What about rthread_semaphore.c?

> @@ -0,0 +1,445 @@
> +/*   $OpenBSD$ */
> +/*
> + * Copyright (c) 2004,2005,2013 Ted Unangst 
> + * Copyright (c) 2018 Paul Irofti 
> + * All Rights Reserved.
> + *
> + * Permission to use, copy, modify, and distribute this software for any
> + * purpose with or without fee is hereby granted, provided that the above
> + * copyright notice and this permission notice appear in all copies.
> + *
> + * THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES
> + * WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF
> + * MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR
> + * ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES
> + * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN
> + * ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF
> + * OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE.
> + */
> +
> +#include 
> +#include 
> +#include 
> +#include 
> +#include 
> +#include 
> +
> +#include 
> +#include 
> +#include 
> +#include 
> +#include 
> +#include 
> +#include 
> +#include 
> +
> +#include 
> +
> +#include "rthread.h"
> +#include "cancel.h"  /* in libc/include */
> +#include "synch.h"
> +
> +#ifdef SEM_ATOMIC_DEBUG
> +#define DPRINTF(x)   printf x
> +#else
> +#define DPRINTF(x)
> +#endif
> +
> +#define SHARED_IDENT ((void *)-1)
> +
> +/* SHA256_DIGEST_STRING_LENGTH includes nul */
> +/* "/tmp/" + sha256 + ".sem" */
> +#define SEM_PATH_SIZE (5 + SHA256_DIGEST_STRING_LENGTH + 4)
> +
> +/* long enough to be hard to guess */
> +#define SEM_RANDOM_NAME_LEN  10
> +
> +/*
> + * Size of memory to be mmap()'ed by named semaphores.
> + * Should be >= SEM_PATH_SIZE and page-aligned.
> + */
> +#define SEM_MMAP_SIZE_thread_pagesize
> +
> +/*
> + * Internal implementation of semaphores
> + */
> +int
> +_sem_wait(sem_t sem, int can_eintr, const struct timespec *abstime,
> +int *delayed_cancel)
> +{
> + int r = 0;
> + int v = sem->value, ov;

Reading `sem->value' here is superfluous.

> +
> + for (;;) {
> + while ((v = sem->value) > 0) {
> + ov = atomic_cas_uint(>value, v, v - 1);
> + if (ov == v) {
> + membar_enter_after_atomic();
> + return 0;
> + }
> + }
> + if (r)
> + break;
> +
> + atomic_inc_int(>waitcount);

Can you keep the destroy check without adding two atomic operations here?

> + r = _twait(>value, 0, CLOCK_REALTIME, abstime);
> + /* ignore interruptions other than cancelation */
> + if ((r == ECANCELED && *delayed_cancel == 0) ||
> + (r == EINTR && !can_eintr) || r == EAGAIN)
> + r = 0;
> + atomic_dec_int(>waitcount);
> + }
> +
> + return r;
> +}
> +
> +/* always increment count */
> +int
> +_sem_post(sem_t sem)
> +{

This function is called only once, so you can fold it in sem_post() :)

> + membar_exit_before_atomic();

Why is the membar needed here?  Does that mean we're missing two in 
pthread_cond_signal() and pthread_cond_broadcast()?

> + atomic_inc_int(>value);
> + _wake(>value, 1);
> + return 0;
> +}
> +
> +/*
> + * exported semaphores
> + */
> +int
> +sem_init(sem_t *semp, int pshared, unsigned 

Re: new semapahore implementation using atomics and futexes

[Paul Irofti]

On Sat, Apr 28, 2018 at 07:40:38PM +0300, Paul Irofti wrote:
> On Sun, Apr 22, 2018 at 03:34:45PM +0300, Paul Irofti wrote:
> > Hi,
> > 
> > Here is a new semaphore implementation that uses atomic operations,
> > where available, and futexes for locking. 
> > 
> > The reason we need this is to make semaphores safe for asynchronous
> > signals.
> > 
> > 
> > All posixsuite tests (semaphore and sigaction) pass with this.
> > They do not with our current implementation.  Unfortunately I can not
> > get our sem_timedwait regression test to work.
> > 
> >   regress/lib/libpthread/semaphore/sem_timedwait
> > 
> > My investigation so far suggests that the current implementation is
> > flawed because it does not respect ERESTART and treats EINTR as if it
> > would be equivalent to EAGAIN. The POSIX standard and other
> > implementations disagree with that: ERESTART should restart the
> > semaphore waiting and EINTR should exit the call. The above regression
> > test relies on our current EINTR abuse and I think that is why it fails.
> > I added a few helpful printfs to that test in my diff.
> > 
> > I hope future discussions at the Nantes hackathon will clarify this
> > issue.
> > 
> > 
> > Otherwise I have been running with this implementation for a couple of
> > weeks. LaTeX, octave, chrome, firefox, thunderbird, vim, mutt, vlc,
> > mplayer etc. run just fine.
> > 
> > I would like to get wider testing to see if there are any defects left
> > in the current version. 
> > 
> > 
> > I have also added all the changes in a fork on github.
> > 
> >   https://github.com/bulibuta/openbsd-src/tree/sem_atomicfutex
> > 
> > 
> > Please test and get back to me if you see any issues.
> > 
> > Thank you,
> > Paul
> 
> Here is the same diff adapted to what happened in -current this week.
> All required bits are now in, so the current diff neatly contains just the
> implementation.

People started testing this, thank you!

Here is an updated diff that:

  Add barriers, debug printfs and handle EAGAIN.

  The barriers bit is mostly from visa@, thanks!

  tb@ found offlineimap faulting because the futex syscall returned EAGAIN
  and sem_wait exited. Loop again on EAGAIN.

  Debug printfs are for future debugging.

Martin, is handling EAGAIN like this correct?

diff --git lib/librthread/Makefile lib/librthread/Makefile
index 4c3e127491d..5dfb140290e 100644
--- lib/librthread/Makefile
+++ lib/librthread/Makefile
@@ -30,12 +30,19 @@ SRCS=   rthread.c \
rthread_rwlock.c \
rthread_rwlockattr.c \
rthread_sched.c \
-   rthread_sem.c \
rthread_sig.c \
rthread_stack.c \
rthread_spin_lock.c \
sched_prio.c
 
+# Architectures that implement atomics
+.if ${MACHINE_ARCH} == "amd64" || ${MACHINE_ARCH} == "i386" || \
+${MACHINE_ARCH} == "mips64" || ${MACHINE_ARCH} == "mips64el"
+SRCS+= rthread_sem_atomic.c
+.else
+SRCS+= rthread_sem.c
+.endif
+
 SRCDIR= ${.CURDIR}/../libpthread
 .include "${SRCDIR}/man/Makefile.inc"
 .include 
diff --git lib/librthread/rthread_sem_atomic.c 
lib/librthread/rthread_sem_atomic.c
new file mode 100644
index 000..e5c8015d27c
--- /dev/null
+++ lib/librthread/rthread_sem_atomic.c
@@ -0,0 +1,445 @@
+/* $OpenBSD$ */
+/*
+ * Copyright (c) 2004,2005,2013 Ted Unangst 
+ * Copyright (c) 2018 Paul Irofti 
+ * All Rights Reserved.
+ *
+ * Permission to use, copy, modify, and distribute this software for any
+ * purpose with or without fee is hereby granted, provided that the above
+ * copyright notice and this permission notice appear in all copies.
+ *
+ * THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES
+ * WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF
+ * MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR
+ * ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES
+ * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN
+ * ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF
+ * OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE.
+ */
+
+#include 
+#include 
+#include 
+#include 
+#include 
+#include 
+
+#include 
+#include 
+#include 
+#include 
+#include 
+#include 
+#include 
+#include 
+
+#include 
+
+#include "rthread.h"
+#include "cancel.h"/* in libc/include */
+#include "synch.h"
+
+#ifdef SEM_ATOMIC_DEBUG
+#define DPRINTF(x) printf x
+#else
+#define DPRINTF(x)
+#endif
+
+#define SHARED_IDENT ((void *)-1)
+
+/* SHA256_DIGEST_STRING_LENGTH includes nul */
+/* "/tmp/" + sha256 + ".sem" */
+#define SEM_PATH_SIZE (5 + SHA256_DIGEST_STRING_LENGTH + 4)
+
+/* long enough to be hard to guess */
+#define SEM_RANDOM_NAME_LEN10
+
+/*
+ * Size of memory to be mmap()'ed by named semaphores.
+ * Should be >= SEM_PATH_SIZE and page-aligned.
+ */
+#define SEM_MMAP_SIZE  _thread_pagesize
+
+/*
+ * Internal implementation of semaphores
+ */
+int
+_sem_wait(sem_t sem, int 

Re: new semapahore implementation using atomics and futexes

[Paul Irofti]

On Sun, Apr 22, 2018 at 03:34:45PM +0300, Paul Irofti wrote:
> Hi,
> 
> Here is a new semaphore implementation that uses atomic operations,
> where available, and futexes for locking. 
> 
> The reason we need this is to make semaphores safe for asynchronous
> signals.
> 
> 
> All posixsuite tests (semaphore and sigaction) pass with this.
> They do not with our current implementation.  Unfortunately I can not
> get our sem_timedwait regression test to work.
> 
>   regress/lib/libpthread/semaphore/sem_timedwait
> 
> My investigation so far suggests that the current implementation is
> flawed because it does not respect ERESTART and treats EINTR as if it
> would be equivalent to EAGAIN. The POSIX standard and other
> implementations disagree with that: ERESTART should restart the
> semaphore waiting and EINTR should exit the call. The above regression
> test relies on our current EINTR abuse and I think that is why it fails.
> I added a few helpful printfs to that test in my diff.
> 
> I hope future discussions at the Nantes hackathon will clarify this
> issue.
> 
> 
> Otherwise I have been running with this implementation for a couple of
> weeks. LaTeX, octave, chrome, firefox, thunderbird, vim, mutt, vlc,
> mplayer etc. run just fine.
> 
> I would like to get wider testing to see if there are any defects left
> in the current version. 
> 
> 
> I have also added all the changes in a fork on github.
> 
>   https://github.com/bulibuta/openbsd-src/tree/sem_atomicfutex
> 
> 
> Please test and get back to me if you see any issues.
> 
> Thank you,
> Paul

Here is the same diff adapted to what happened in -current this week.
All required bits are now in, so the current diff neatly contains just the
implementation.


diff --git lib/librthread/Makefile lib/librthread/Makefile
index 4c3e127491d..5dfb140290e 100644
--- lib/librthread/Makefile
+++ lib/librthread/Makefile
@@ -30,12 +30,19 @@ SRCS=   rthread.c \
rthread_rwlock.c \
rthread_rwlockattr.c \
rthread_sched.c \
-   rthread_sem.c \
rthread_sig.c \
rthread_stack.c \
rthread_spin_lock.c \
sched_prio.c
 
+# Architectures that implement atomics
+.if ${MACHINE_ARCH} == "amd64" || ${MACHINE_ARCH} == "i386" || \
+${MACHINE_ARCH} == "mips64" || ${MACHINE_ARCH} == "mips64el"
+SRCS+= rthread_sem_atomic.c
+.else
+SRCS+= rthread_sem.c
+.endif
+
 SRCDIR= ${.CURDIR}/../libpthread
 .include "${SRCDIR}/man/Makefile.inc"
 .include 
diff --git lib/librthread/rthread_sem_atomic.c 
lib/librthread/rthread_sem_atomic.c
new file mode 100644
index 000..4fbc6cb8223
--- /dev/null
+++ lib/librthread/rthread_sem_atomic.c
@@ -0,0 +1,420 @@
+/* $OpenBSD$ */
+/*
+ * Copyright (c) 2004,2005,2013 Ted Unangst 
+ * Copyright (c) 2018 Paul Irofti 
+ * All Rights Reserved.
+ *
+ * Permission to use, copy, modify, and distribute this software for any
+ * purpose with or without fee is hereby granted, provided that the above
+ * copyright notice and this permission notice appear in all copies.
+ *
+ * THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES
+ * WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF
+ * MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR
+ * ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES
+ * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN
+ * ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF
+ * OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE.
+ */
+
+#include 
+#include 
+#include 
+#include 
+#include 
+#include 
+
+#include 
+#include 
+#include 
+#include 
+#include 
+#include 
+#include 
+#include 
+
+#include 
+
+#include "rthread.h"
+#include "cancel.h"/* in libc/include */
+#include "synch.h"
+
+#define SHARED_IDENT ((void *)-1)
+
+/* SHA256_DIGEST_STRING_LENGTH includes nul */
+/* "/tmp/" + sha256 + ".sem" */
+#define SEM_PATH_SIZE (5 + SHA256_DIGEST_STRING_LENGTH + 4)
+
+/* long enough to be hard to guess */
+#define SEM_RANDOM_NAME_LEN10
+
+/*
+ * Size of memory to be mmap()'ed by named semaphores.
+ * Should be >= SEM_PATH_SIZE and page-aligned.
+ */
+#define SEM_MMAP_SIZE  _thread_pagesize
+
+/*
+ * Internal implementation of semaphores
+ */
+int
+_sem_wait(sem_t sem, int can_eintr, const struct timespec *abstime,
+int *delayed_cancel)
+{
+   int r = 0;
+   int v = sem->value, ov;
+
+   for (;;) {
+   while ((v = sem->value) > 0) {
+   ov = atomic_cas_uint(>value, v, v - 1);
+   if (ov == v)
+   return 0;
+   }
+   if (r)
+   break;
+
+   atomic_inc_int(>waitcount);
+   r = _twait(>value, 0, CLOCK_REALTIME, abstime);
+   /* ignore interruptions other than cancelation */
+   if ((r == ECANCELED && *delayed_cancel