[PATCH] kernel32: implement condition variables
Marcus Meissner
marcus at jet.franken.de
Fri Jan 18 11:13:46 CST 2013
Hi,
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 issue:
We are busy waiting on the bit 0 lock.
Ciao, Marcus
---
dlls/kernel32/kernel32.spec | 4 +
dlls/kernel32/sync.c | 174 +++++++++++++++++++++++++++++++++++++++++++
2 files changed, 178 insertions(+)
diff --git a/dlls/kernel32/kernel32.spec b/dlls/kernel32/kernel32.spec
index 0bd1adc..69de820 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)
@@ -1187,6 +1188,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)
@@ -1256,6 +1258,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..e1987bc 100644
--- a/dlls/kernel32/sync.c
+++ b/dlls/kernel32/sync.c
@@ -2299,3 +2299,177 @@ __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 or access via bit 0 of variable->Ptr. This avoids needs for other global variables.
+ */
+
+struct _condvar_intern {
+ struct _condvar_intern *next;
+ HANDLE event;
+};
+
+/**********************************************************************
+ * InitializeConditionVariable (KERNEL32.@)
+ */
+VOID WINAPI InitializeConditionVariable(PCONDITION_VARIABLE variable)
+{
+ variable->Ptr = NULL;
+}
+
+/**********************************************************************
+ * WakeConditionVariable (KERNEL32.@)
+ */
+VOID WINAPI WakeConditionVariable(PCONDITION_VARIABLE variable)
+{
+ struct _condvar_intern *oldvar, *var;
+
+ /*FIXME("(%p) aka %p\n", variable, var);*/
+
+ /* Get a lock on the list head */
+ do {
+ __asm__ __volatile__("":::"memory");
+ var = variable->Ptr;
+ if (!var) return; /* Nothing to do */
+ if ((DWORD_PTR)var & 1) continue;/* Need to busy wait a bit. */
+
+ oldvar = InterlockedCompareExchangePointer (&variable->Ptr, (void*)((DWORD_PTR)var|1), var);
+ if (oldvar == var)
+ break;
+ } while (1);
+
+ NtSetEvent (var->event, NULL);
+ var->event = NULL;
+
+ variable->Ptr = var->next; /* unlock the list head */
+}
+
+/**********************************************************************
+ * WakeAllConditionVariable (KERNEL32.@)
+ */
+VOID WINAPI WakeAllConditionVariable(PCONDITION_VARIABLE variable)
+{
+ struct _condvar_intern *oldvar, *var;
+
+ /*FIXME("(%p) aka %p\n", variable, var);*/
+
+ /* Get a lock on the list head */
+ do {
+ __asm__ __volatile__("":::"memory");
+ var = variable->Ptr;
+ if (!var) return; /* Nothing to do */
+ if ((DWORD_PTR)var & 1) continue; /* Need to busy wait a bit. */
+
+ oldvar = InterlockedCompareExchangePointer (&variable->Ptr, (void*)1, var);
+ if (oldvar == var)
+ break;
+ /* failed locking, retry in busy loop. */
+ } while (1);
+
+ /* dequeue whole waiter chain for wake up */
+ while (var) {
+ NtSetEvent (var->event, NULL);
+ var->event = NULL;
+ var = var->next;
+ } while (var);
+
+ variable->Ptr = NULL; /* unlock list head */
+}
+
+/**********************************************************************
+ * SleepConditionVariableCS (KERNEL32.@)
+ */
+BOOL WINAPI SleepConditionVariableCS(PCONDITION_VARIABLE variable,
+ LPCRITICAL_SECTION crit, DWORD timeout
+)
+{
+ struct _condvar_intern myself;
+ struct _condvar_intern **xvar, *var, *oldvar;
+ BOOL ret = TRUE;
+ OBJECT_ATTRIBUTES attr;
+ HANDLE myevent;
+ DWORD res;
+
+
+ /*FIXME("(%p, %p, %d): semi-correct stub, var %p.\n", variable, crit, timeout, &myself);*/
+
+ 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);
+ myevent = myself.event;
+ myself.next = NULL;
+ /* Get a lock on the list head */
+ do {
+ __asm__ __volatile__("":::"memory");
+ var = variable->Ptr;
+ if ((DWORD_PTR)var & 1) continue; /* Need to busy wait a bit. */
+
+ oldvar = InterlockedCompareExchangePointer (&variable->Ptr, (void*)((DWORD_PTR)var|1), var);
+ if (oldvar == var)
+ break;
+ /* failed locking, retry in busy loop. */
+ } while (1);
+
+ /* Attach ourselves to the end of the list */
+ xvar = (struct _condvar_intern **)&variable->Ptr;
+ while (((DWORD_PTR)*xvar) & ~1) {
+ struct _condvar_intern *yvar = (struct _condvar_intern *)((DWORD_PTR)(*xvar)&~1);
+ xvar = &yvar->next;
+ }
+ *xvar = &myself;
+
+ variable->Ptr = var; /* unlock list head */
+
+ RtlLeaveCriticalSection(crit);
+
+ res = WaitForSingleObject(myevent, timeout);
+
+ /* Get a lock on the list head */
+ do {
+ __asm__ __volatile__("":::"memory");
+ var = variable->Ptr;
+ if (!var) break; /* Nothing to do */
+ if ((DWORD_PTR)var & 1) continue; /* Need to busy wait a bit. */
+
+ oldvar = InterlockedCompareExchangePointer (&variable->Ptr, (void*)((DWORD_PTR)var|1), var);
+ if (oldvar == var)
+ break;
+ /* failed locking, retry in busy loop. */
+ } while (1);
+
+ if (res == WAIT_TIMEOUT) {
+ xvar = (struct _condvar_intern **)&variable->Ptr;
+ while (((DWORD_PTR)*xvar) & ~1) {
+ struct _condvar_intern *yvar = (struct _condvar_intern *)((DWORD_PTR)(*xvar)&~1);
+ if (yvar == &myself) {
+ *xvar = yvar->next;
+ break;
+ }
+ xvar = &yvar->next;
+ }
+ /* If we did not overwrite the list head and so unlock the list,
+ * do it now. */
+ if ((DWORD_PTR)variable->Ptr & 1)
+ variable->Ptr = (void*)((DWORD_PTR)variable->Ptr & ~1);
+
+ ret = FALSE;
+ /* expected from caller, but not set by WaitForSingleObject */
+ SetLastError(ERROR_TIMEOUT);
+ } else
+ variable->Ptr = var;
+
+ RtlEnterCriticalSection(crit);
+ CloseHandle (myevent);
+
+ return ret;
+}
--
1.7.10.4
More information about the wine-patches
mailing list