Hi all,

I would like if possible a review of this approach to win32 condvars.
It is based on the ACE implementation (http://www.cs.wustl.edu/
~schmidt/win32-cv-1.html) but I tried to get rid of most concurrent
accesses to the "number of waiters" variable and of the critical
section protecting it.  To achieve this I made the following changes:

* I force the mutex to be held during signal and broadcast.

* I make signal synchronous (so, more expensive) as a tradeoff for
making broadcast cheaper.

Together, this two conditions ensure that the thread with the mutex
protects the signaled thread(s) against other threads.

Any observation is welcome!

#include <windows.h>
#include <limits.h>

typedef CRITICAL_SECTION QemuMutex;
static inline void qemu_mutex_lock(QemuMutex *mutex) {
    EnterCriticalSection(mutex);
}
static inline void qemu_mutex_unlock(QemuMutex *mutex) {
    LeaveCriticalSection(mutex);
}

typedef struct QemuCond QemuCond;
void qemu_cond_init(QemuCond *cond);
void qemu_cond_destroy(QemuCond *cond);
void qemu_cond_signal(QemuCond *cond);
void qemu_cond_broadcast(QemuCond *cond);
void qemu_cond_wait(QemuCond *cond, QemuMutex *mutex);

struct QemuCond {
    LONG waiters, target;
    HANDLE sema;
    HANDLE continue_event;
};

void qemu_cond_init(QemuCond *cond)
{
    memset(cond, 0, sizeof(*cond));

    cond->sema = CreateSemaphore(NULL, 0, LONG_MAX, NULL);
    cond->continue_event = CreateEvent(NULL,    /* security */
                                       FALSE,   /* auto-reset */
                                       FALSE,   /* not signaled */
                                       NULL);   /* name */
}

void qemu_cond_signal(QemuCond *cond)
{
    DWORD result;

    /*
     * Signal only when there are waiters.  cond->waiters is
     * incremented by pthread_cond_wait under the external lock,
     * so we are safe about that.
     */
    if (cond->waiters == 0) {
        return;
    }

    /*
     * Waiting threads decrement it outside the external lock,
     * but only if another thread is signaling/broadcasting and
     * has the mutex.  So, it also cannot be decremented
     * concurrently with this particular access.
     */
    cond->target = cond->waiters - 1;
    result = SignalObjectAndWait(cond->sema, cond->continue_event,
                                 INFINITE, FALSE);
}

void qemu_cond_broadcast(QemuCond *cond)
{
    BOOLEAN result;
    if (cond->waiters == 0) {
        return;
    }

    cond->target = 0;
    result = ReleaseSemaphore(cond->sema, cond->waiters, NULL);
    WaitForSingleObject(cond->continue_event, INFINITE);
}

void qemu_cond_wait(QemuCond *cond, QemuMutex *mutex)
{
    /*
     * This access is protected under the mutex.
     */
    cond->waiters++;
    qemu_mutex_unlock(mutex);
    WaitForSingleObject(cond->sema, INFINITE);

    /*
     * Decrease waiters count.  The mutex is not taken, so we have
     * to do this atomically.
     *
     * All waiters contend for the mutex at the end of this function
     * until the signaling thread relinquishes it.  To ensure
     * each waiter consumes exactly one slice of the semaphore,
     * the signaling thread stops until it is told by the last
     * waiter that it can go on.
     */
    if (InterlockedDecrement(&cond->waiters) == cond->target) {
        SetEvent(cond->continue_event);
    }

    qemu_mutex_lock(mutex);
}

Paolo Bonzini <bonzini@gnu.org> writes:

> I would like if possible a review of this approach to win32 condvars.

> void qemu_cond_signal(QemuCond *cond)
> {
>     DWORD result;
>     if (cond->waiters == 0) {
>         return;
>     }
>     cond->target = cond->waiters - 1;
>     result = SignalObjectAndWait(cond->sema, cond->continue_event,
>                                  INFINITE, FALSE);
> }
>
> void qemu_cond_broadcast(QemuCond *cond)
> {
>     BOOLEAN result;
>     if (cond->waiters == 0) {
>         return;
>     }
>
>     cond->target = 0;
>     result = ReleaseSemaphore(cond->sema, cond->waiters, NULL);
>     WaitForSingleObject(cond->continue_event, INFINITE);
> }
>
> void qemu_cond_wait(QemuCond *cond, QemuMutex *mutex)
> {
>     cond->waiters++;
>     qemu_mutex_unlock(mutex);
>     WaitForSingleObject(cond->sema, INFINITE);
>
>     if (InterlockedDecrement(&cond->waiters) == cond->target) {
>         SetEvent(cond->continue_event);
>     }
>
>     qemu_mutex_lock(mutex);
> }

Consider:

1. Thread A calls qemu_cond_wait, sets cond->waiters==1 and blocks in
WaitForSingleObject

2. Thread B calls qemu_cond_signal, sees cond->waiters==1, sets
cond->target==0, triggers the semaphore and waits for
cond->continue_event

3. Thread C calls qemu_cond_wait, sets cond->waiters==2 and blocks in
WaitForSingleObject

Now we have a problem. There are two possible outcomes here, both of
which are problematic.

4a. Thread C is now woken, since the semaphore is signalled [Stolen
wakeup]

4b.Thread C stays sleeping, but thread B is woken as expected. Thread B
decrements cond->waiters to 1, but sees cond->target==0, so does not
signal cond->continue_event [Signalling thread does not return]

Why not just use the implementation from boost?

Anthony
-- 
Author of C++ Concurrency in Action     http://www.stdthread.co.uk/book/
just::thread C++0x thread library             http://www.stdthread.co.uk
Just Software Solutions Ltd       http://www.justsoftwaresolutions.co.uk
15 Carrallack Mews, St Just, Cornwall, TR19 7UL, UK. Company No. 5478976

Anthony Williams <anthony.ajw@gmail.com> writes:

> Consider:
>
> 1. Thread A calls qemu_cond_wait, sets cond->waiters==1 and blocks in
> WaitForSingleObject
>
> 2. Thread B calls qemu_cond_signal, sees cond->waiters==1, sets
> cond->target==0, triggers the semaphore and waits for
> cond->continue_event
>
> 3. Thread C calls qemu_cond_wait, sets cond->waiters==2 and blocks in
> WaitForSingleObject

This can't happen if the mutex is held across the signal call, as per
Paolo's original post. 

Anthony
-- 
Author of C++ Concurrency in Action     http://www.stdthread.co.uk/book/
just::thread C++0x thread library             http://www.stdthread.co.uk
Just Software Solutions Ltd       http://www.justsoftwaresolutions.co.uk
15 Carrallack Mews, St Just, Cornwall, TR19 7UL, UK. Company No. 5478976