Re: [PATCH 12/21] kernel32: conditional variable support (try 6)
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
participants (1)
-
Marcus Meissner