[PATCH] kernel32: implement condition variables
Marcus Meissner
marcus at jet.franken.de
Mon Jan 21 15:52:13 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, not the most performance
wise best thing.
Adobe Lightroom approved(tm). :)
Ciao, Marcus
---
dlls/kernel32/kernel32.spec | 4 +
dlls/kernel32/sync.c | 179 +++++++++++++++++++++++++++++++++++++++++++
dlls/kernel32/tests/sync.c | 21 ++---
3 files changed, 195 insertions(+), 9 deletions(-)
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..31fe0c7 100644
--- a/dlls/kernel32/sync.c
+++ b/dlls/kernel32/sync.c
@@ -2299,3 +2299,182 @@ __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. This avoids needs for 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)\n", variable);*/
+
+ /* Get a lock on the list head, using bit 0 */
+ 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 longer. */
+
+ oldvar = InterlockedCompareExchangePointer (&variable->Ptr, (void*)((DWORD_PTR)var|1), var);
+ if (oldvar == var)
+ break;
+ /* failed locking, retry. */
+ } 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)\n", variable);*/
+
+ /* 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 longer. */
+
+ oldvar = InterlockedCompareExchangePointer (&variable->Ptr, (void*)1, var);
+ if (oldvar == var)
+ break;
+ /* failed locking, retry. */
+ } 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 unlocked, 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. */
+ } while (1);
+
+ /* Attach ourselves to the end of the list, for fairness. */
+ 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;
+ /* If we had a first entry in the list of waiters, restore it now and unlock the list.
+ * If we did not have one yet, the line above this comment
+ * will have unlocked the list already. */
+ if (var)
+ variable->Ptr = var;
+
+ RtlLeaveCriticalSection(crit);
+
+ res = WaitForSingleObject(myevent, timeout);
+
+ /* Get a lock on the list head again */
+ 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. */
+ } while (1);
+
+ unlocked = FALSE;
+ if (var) {
+ /* Try to remove our entry ... this should only ever happen in the timeout case,
+ * but * do so in all cases to be safe. */
+ 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) {
+ if (xvar == (struct _condvar_intern **)&variable->Ptr)
+ unlocked = TRUE;
+ *xvar = yvar->next;
+ break;
+ }
+ xvar = &yvar->next;
+ }
+ }
+ if (!unlocked)
+ variable->Ptr = var;
+
+ CloseHandle (myevent);
+ RtlEnterCriticalSection(crit);
+
+ if (res == WAIT_TIMEOUT) {
+ ret = FALSE;
+ /* expected from caller, but not set by WaitForSingleObject */
+ SetLastError(ERROR_TIMEOUT);
+ }
+ return ret;
+}
diff --git a/dlls/kernel32/tests/sync.c b/dlls/kernel32/tests/sync.c
index 0ab82f0..a570367 100644
--- a/dlls/kernel32/tests/sync.c
+++ b/dlls/kernel32/tests/sync.c
@@ -1253,12 +1253,12 @@ static LONG condvar_producer_sleepcnt,condvar_consumer_sleepcnt;
#define BUFFER_SIZE 5
static DWORD WINAPI condvar_producer(LPVOID x) {
- DWORD sleepinterval = 50;
+ DWORD sleepinterval = 5;
while (1) {
Sleep(sleepinterval);
- if (sleepinterval > 10)
- sleepinterval -= 10;
+ if (sleepinterval > 1)
+ sleepinterval -= 1;
EnterCriticalSection(&buffercrit);
while ((bufferlen == BUFFER_SIZE) && !condvar_stop) {
@@ -1282,7 +1282,7 @@ static DWORD WINAPI condvar_producer(LPVOID x) {
static DWORD WINAPI condvar_consumer(LPVOID x) {
DWORD *cnt = (DWORD*)x;
- DWORD sleepinterval = 10;
+ DWORD sleepinterval = 1;
while (1) {
EnterCriticalSection(&buffercrit);
@@ -1303,7 +1303,7 @@ static DWORD WINAPI condvar_consumer(LPVOID x) {
LeaveCriticalSection(&buffercrit);
pWakeConditionVariable(&buffernotfull);
Sleep(sleepinterval);
- if (sleepinterval < 50) sleepinterval += 10;
+ if (sleepinterval < 5) sleepinterval += 1;
}
return 0;
}
@@ -1316,8 +1316,7 @@ static void test_condvars(void)
if (!pInitializeConditionVariable) {
/* function is not yet in XP, only in newer Windows */
- /* and not yet implemented in Wine for some days/weeks */
- todo_wine win_skip("no condition variable support.\n");
+ win_skip("no condition variable support.\n");
return;
}
@@ -1328,8 +1327,10 @@ static void test_condvars(void)
* pInitializeConditionVariable(&buffernotfull);
*/
pInitializeConditionVariable(&buffernotempty);
-
InitializeCriticalSection(&buffercrit);
+
+ /* Larger Test: consumer/producer example */
+
bufferlen = totalproduced = totalconsumed = cnt1 = cnt2 = cnt3 = 0;
hp1 = CreateThread(NULL, 0, condvar_producer, NULL, 0, &dummy);
@@ -1349,7 +1350,9 @@ static void test_condvars(void)
pWakeAllConditionVariable (&buffernotfull);
pWakeAllConditionVariable (&buffernotempty);
- ok(buffernotfull.Ptr == NULL, "buffernotfull.Ptr is %p\n", buffernotfull.Ptr);
+ /* (mostly an implementation detail)
+ * ok(buffernotfull.Ptr == NULL, "buffernotfull.Ptr is %p\n", buffernotfull.Ptr);
+ */
WaitForSingleObject(hp1, 1000);
WaitForSingleObject(hp2, 1000);
--
1.7.10.4
More information about the wine-patches
mailing list