Re: [PATCH 12/21] kernel32: conditional variable support (try 6)

[Marcus Meissner]

Hmm,

THis should have been patch 0021 instead of 0012 , please disregard.

Ciao, Marcus
On Wed, Jan 01, 2014 at 07:44:16PM +0100, Marcus Meissner wrote:
> Hi,
>
> Additional tightening and cleaning of comments.
>
> After Alexandres last guidance ("no global allocation")
> and some hours of hair pulling I now did a implementation
> with just a linked list of waiters.
>
> variable->Ptr points to the head of this list.
>
> The bit 0 of variable->Ptr is used for atomic locking of
> the list and also its content, avoiding need for a lock variable.
>
> Small issues:
> We are busy waiting on the bit 0 lock, not the most performance
> wise best thing.
>
> Ciao, Marcus
> ---
>  dlls/kernel32/kernel32.spec |    4 ++
>  dlls/kernel32/sync.c        |  151 +++++++++++++++++++++++++++++++++++++++++++
>  2 files changed, 155 insertions(+)
>
> diff --git a/dlls/kernel32/kernel32.spec b/dlls/kernel32/kernel32.spec
> index 7779a75..e8d2bf0 100644
> --- a/dlls/kernel32/kernel32.spec
> +++ b/dlls/kernel32/kernel32.spec
> @@ -750,6 +750,7 @@
>  @ stdcall InitOnceComplete(ptr long ptr)
>  @ stdcall InitOnceExecuteOnce(ptr ptr ptr ptr)
>  @ stdcall InitOnceInitialize(ptr) ntdll.RtlRunOnceInitialize
> +@ stdcall InitializeConditionVariable(ptr)
>  @ stdcall InitializeCriticalSection(ptr)
>  @ stdcall InitializeCriticalSectionAndSpinCount(ptr long)
>  @ stdcall InitializeCriticalSectionEx(ptr long long)
> @@ -1194,6 +1195,7 @@
>  @ stdcall SignalObjectAndWait(long long long long)
>  @ stdcall SizeofResource(long long)
>  @ stdcall Sleep(long)
> +@ stdcall SleepConditionVariableCS(ptr ptr long)
>  @ stdcall SleepEx(long long)
>  @ stdcall SuspendThread(long)
>  @ stdcall SwitchToFiber(ptr)
> @@ -1263,6 +1265,8 @@
>  @ stdcall WaitForSingleObjectEx(long long long)
>  @ stdcall WaitNamedPipeA (str long)
>  @ stdcall WaitNamedPipeW (wstr long)
> +@ stdcall WakeAllConditionVariable (ptr)
> +@ stdcall WakeConditionVariable (ptr)
>  @ stdcall WerRegisterFile(wstr long long)
>  @ stdcall WerRegisterMemoryBlock(ptr long)
>  @ stdcall WerRegisterRuntimeExceptionModule(wstr ptr)
> diff --git a/dlls/kernel32/sync.c b/dlls/kernel32/sync.c
> index 3c9e42a..34f39cd 100644
> --- a/dlls/kernel32/sync.c
> +++ b/dlls/kernel32/sync.c
> @@ -2327,3 +2327,154 @@ __ASM_STDCALL_FUNC(InterlockedDecrement, 4,
>                    "ret $4")
>
> #endif  /* __i386__ */
> +
> +/* See http://locklessinc.com/articles/mutex_cv_futex/ for a futex implementation
> + * See http://www.cs.wustl.edu/~schmidt/win32-cv-1.html for various implementations
> + * of pthread_cond_* with Win32 primitives.
> + * See glibc/nptl/DESIGN-condvar.txt for the glibc implementation
> + *
> + * This implementation uses a linked list as waiter queue, and the list
> + * and its content is locked for access via bit 0 of variable->Ptr.
> + * The actual waiting is done using a Win32 Event.
> + */ 
> +
> +struct _condvar_intern {
> +    struct _condvar_intern *next;
> +    HANDLE                 event;
> +};
> +
> +/**********************************************************************
> + *           InitializeConditionVariable     (KERNEL32.@)
> + */
> +VOID WINAPI InitializeConditionVariable(PCONDITION_VARIABLE variable)
> +{
> +    variable->Ptr = NULL;
> +}
> +
> +/*
> + * We lock the condition variable by setting bit 0 in variable->Ptr
> + * atomically. We busy loop until we succeed and return the current value.
> + * We also lock the empty list (NULL).
> + * 
> + * List unlocking is done with "variable->Ptr = <retvalue>"
> + */
> +static struct _condvar_intern*
> +_lock_list (PCONDITION_VARIABLE variable) {
> +    struct _condvar_intern *oldvar, *var;
> +
> +    do {
> +        __asm__ __volatile__("":::"memory");
> +        var = variable->Ptr;
> +        if ((DWORD_PTR)var & 1) continue; /* locked already, retry. */
> +
> +        oldvar = InterlockedCompareExchangePointer (&variable->Ptr, (void*)((DWORD_PTR)var|1), var);
> +        if (oldvar == var)
> +            break;
> +         /* failed atomic locking, retry. */
> +    } while (1);
> +    return var;
> +}
> +
> +/**********************************************************************
> + *           WakeConditionVariable     (KERNEL32.@)
> + */
> +VOID WINAPI WakeConditionVariable(PCONDITION_VARIABLE variable)
> +{
> +    struct _condvar_intern *var;
> +
> +    if (!variable->Ptr)
> +        return;
> +
> +    var = _lock_list (variable);
> +    if (!var) {
> +        variable->Ptr = NULL;
> +        return;
> +    }
> +
> +    /* remove and wake up the first entry */
> +    NtSetEvent (var->event, NULL);
> +
> +    variable->Ptr = var->next;
> +}
> +
> +/**********************************************************************
> + *           WakeAllConditionVariable     (KERNEL32.@)
> + */
> +VOID WINAPI WakeAllConditionVariable(PCONDITION_VARIABLE variable)
> +{
> +    struct _condvar_intern *var;
> +
> +    if (!variable->Ptr)
> +        return;
> +
> +    var = _lock_list (variable);
> +
> +    /* dequeue the whole waiter chain and wake it up */
> +    while (var) {
> +        NtSetEvent (var->event, NULL);
> +        var = var->next;
> +    }
> +
> +    variable->Ptr = NULL;
> +}
> +
> +/**********************************************************************
> + *           SleepConditionVariableCS     (KERNEL32.@)
> + */
> +BOOL WINAPI SleepConditionVariableCS(PCONDITION_VARIABLE variable,
> +    LPCRITICAL_SECTION crit, DWORD timeout
> +)
> +{
> +    struct _condvar_intern myself;
> +    struct _condvar_intern **xvar, *var;
> +    BOOL ret = TRUE;
> +    OBJECT_ATTRIBUTES   attr;
> +    DWORD res;
> +
> +    attr.Length                   = sizeof(attr);
> +    attr.RootDirectory            = 0;
> +    attr.Attributes               = OBJ_INHERIT;
> +    attr.ObjectName               = NULL;
> +    attr.SecurityDescriptor       = NULL;
> +    attr.SecurityQualityOfService = NULL;
> +
> +    NtCreateEvent (&myself.event, EVENT_ALL_ACCESS, &attr, NotificationEvent, 0);
> +    myself.next = NULL;
> +
> +    var = _lock_list (variable);
> +    /* Attach our stack based struct to the end of the list.
> +     * (at the end for fairness)
> +     */
> +    xvar = &var;
> +    while (*xvar)
> +        xvar = &(*xvar)->next;
> +    *xvar = &myself;
> +    variable->Ptr = var;
> +
> +    RtlLeaveCriticalSection(crit);
> +
> +    res = WaitForSingleObject(myself.event, timeout);
> +
> +    var = _lock_list (variable);
> +
> +    /* Remove our entry */
> +    xvar = (struct _condvar_intern **)&var;
> +    while (*xvar) {
> +       if (*xvar == &myself) {
> +           *xvar = (*xvar)->next;
> +           break;
> +        }
> +        xvar = &(*xvar)->next;
> +    }
> +    variable->Ptr = var;
> +
> +    CloseHandle (myself.event);
> +    RtlEnterCriticalSection(crit);
> +
> +    if (res == WAIT_TIMEOUT) {
> +        ret = FALSE;
> +        /* expected from caller, but not set by WaitForSingleObject */
> +        SetLastError(ERROR_TIMEOUT);
> +    }
> +    return ret;
> +}
> -- 
> 1.7.10.4