Re: RFC: Lightweight synchronization mechanism for gnumach

[Agustina Arzille]

On 02/28/2016 02:01 PM, Justus Winter wrote:
> Hi :)
>
> thanks for your prototype.  I cannot comment on the primitive you
> implemented because I'm lacking the expertise, however
>
> Quoting Agustina Arzille (2016-02-28 02:53:12)
> > I've tested it in many scenarios, and seems to work fine. I've
> > benchmarked it as well, and it's far more faster than pthread
> > mutexes implemented with "mach_msg". I'm far from being an expert in
> > kernel programming, though, so so there's probably a few things that
> > I've overlooked.
> > [...]
> > +routine gsync_wait(
> > [...]
> > +simpleroutine gsync_wake(
> I'm curious why your mechanism is faster, because you implemented it
> using messages sent to the kernel using mach_msg, and not as traps.
> This is ok for a prototype of course, but you should look at how
> e.g. mach_port_deallocate is also available as a trap.
>
> Cheers,
> Justus

Hello, Justus.

Here's a rough comparison of how locking is implemented in libpthread,
and the futex prototype I posted.

pthread_mutex_lock:
- Acquire the mutex spin lock.
- If the mutex is unowned, set ourselves as owner, return.
- Else:
  - Enqueue ourselves in the waiters queue.
  - Unlock spin lock.
  - Block with "mach_msg"
  - Reaquire spin lock.
  - Test if we were actually awakened, or just timed out. [*]
  - If we did not time out, see if we have to "drain" the message sent,
    because it might have arrived just as we stopped blocking.
  - If we need to consume the message, block again in "mach_msg".
  - Set ourselves as owner, return.

pthread_mutex_unlock:
- Acquire the mutex spin lock.
- If there are no waiters, unlock spin lock and return.
- Dequeue a thread from the waiters queue.
- Unlock spin lock.
- Wake up thread with mach_msg.

Whereas, for a futex, the process is the following:

futex_lock:
- Do a compare-and-swap, and see if it's unowned. If it is, return.
- Else loop:
  - Do a compare-and-swap, and see if it's unowned. If it is, return.
  - Wait with gsync_wait for the futex to become free.

futex_unlock:
- Do an atomic-add on the futex.
- If there were waiters, wake one of them with gsync_wake.

There are a few things that are specific to pthreads that may slow things
down a bit, and make a raw futex call faster, but I think the reason for the
performance gain is the lower number of atomic operations (on average), and
also the lower number of syscalls (mach_msg) for the worst cases.

(As an aside, the implementation in libpthread doesn't account for signals
interrupting the wait in the step marked with a [*]. With the futex example
I posted earlier, handling such asynchronous interrupts is trivial).