[PATCH] kernel32: implement condition variables (try 5)
Marcus Meissner
marcus at jet.franken.de
Thu Jan 24 02:56:50 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.
This is a refresh of the previous patch with the locking code
refactored and more clean ups.
I think I now have it at the point where it cannot be more beautified.
Also adjusted the testsuite to have more turnaround in the short time.
Ciao, Marcus
---
dlls/kernel32/kernel32.spec | 4 ++
dlls/kernel32/sync.c | 150 +++++++++++++++++++++++++++++++++++++++++++
dlls/kernel32/tests/sync.c | 21 +++---
3 files changed, 166 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..df3c86a 100644
--- a/dlls/kernel32/sync.c
+++ b/dlls/kernel32/sync.c
@@ -2299,3 +2299,153 @@ __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;
+}
+
+/*
+ * We lock the condition variable by trying to set bit 0 in variable->Ptr
+ * atomically. We busy loop until we succeed and return the current value.
+ * We also lock the empty list (NULL).
+ */
+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; /* 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);
+ return var;
+}
+
+/**********************************************************************
+ * WakeConditionVariable (KERNEL32.@)
+ */
+VOID WINAPI WakeConditionVariable(PCONDITION_VARIABLE variable)
+{
+ struct _condvar_intern *var;
+
+ /*FIXME("(%p)\n", variable);*/
+ var = _lock_list (variable);
+ if (!var) { /* unlock the currently locked list */
+ variable->Ptr = NULL;
+ return;
+ }
+
+ NtSetEvent (var->event, NULL);
+ var->event = NULL;
+
+ variable->Ptr = var->next;
+}
+
+/**********************************************************************
+ * WakeAllConditionVariable (KERNEL32.@)
+ */
+VOID WINAPI WakeAllConditionVariable(PCONDITION_VARIABLE variable)
+{
+ struct _condvar_intern *var;
+
+ /*FIXME("(%p)\n", variable);*/
+ var = _lock_list (variable);
+ if (!var) {
+ variable->Ptr = NULL;
+ return;
+ }
+
+ /* dequeue the whole waiter chain for wake up */
+ while (var) {
+ NtSetEvent (var->event, NULL);
+ var->event = NULL;
+ var = var->next;
+ } while (var);
+
+ 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;
+ 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;
+
+ var = _lock_list (variable);
+ /* Attach ourselves to the end of the list, for fairness. */
+ xvar = &var;
+ while (*xvar)
+ xvar = &(*xvar)->next;
+ *xvar = &myself;
+ variable->Ptr = var;
+
+ RtlLeaveCriticalSection(crit);
+
+ res = WaitForSingleObject(myevent, timeout);
+
+ var = _lock_list (variable);
+ /* Remove our entry ... if still in the list */
+ xvar = (struct _condvar_intern **)&var;
+ while (*xvar) {
+ if (*xvar == &myself) {
+ *xvar = (*xvar)->next;
+ break;
+ }
+ xvar = &(*xvar)->next;
+ }
+ 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