[PATCH] kernel32: conditional variable support (try 6)

[Marcus Meissner]

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 f2f039b..4bfbceb 100644
--- a/dlls/kernel32/kernel32.spec
+++ b/dlls/kernel32/kernel32.spec
@@ -745,6 +745,7 @@
 @ stdcall IdnToUnicode(long wstr long ptr long)
 @ stdcall InitAtomTable(long)
 @ stdcall InitializeSRWLock(ptr)
+@ stdcall InitializeConditionVariable(ptr)
 @ stdcall InitializeCriticalSection(ptr)
 @ stdcall InitializeCriticalSectionAndSpinCount(ptr long)
 @ stdcall InitializeCriticalSectionEx(ptr long long)
@@ -1188,6 +1189,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)
@@ -1257,6 +1259,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 f8c951b..441c54c 100644
--- a/dlls/kernel32/sync.c
+++ b/dlls/kernel32/sync.c
@@ -2299,3 +2299,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