[PATCH v3 1/2] kernelbase/tests: Relax tests for WaitOnAddress().

[Zebediah Figura]

Application should be expected to handle spurious wakeups, which the
following implementation will give in WakeByAddressSingle(). Avoid testing
that WakeByAddressSingle() only wakes one thread.

Signed-off-by: Zebediah Figura <z.figura12(a)gmail.com>
---
 dlls/kernelbase/tests/sync.c | 50 +++++++++++++++++++-----------------
 1 file changed, 26 insertions(+), 24 deletions(-)

diff --git a/dlls/kernelbase/tests/sync.c b/dlls/kernelbase/tests/sync.c
index 99cbbc43bc..eb1a20f11e 100644
--- a/dlls/kernelbase/tests/sync.c
+++ b/dlls/kernelbase/tests/sync.c
@@ -30,20 +30,24 @@ static BOOL (WINAPI *pWaitOnAddress)(volatile void *, void *, SIZE_T, DWORD);
 static void (WINAPI *pWakeByAddressAll)(void *);
 static void (WINAPI *pWakeByAddressSingle)(void *);
 
-static LONG64 address;
-static LONG64 compare;
+static LONG address;
 static DWORD WINAPI test_WaitOnAddress_func(void *arg)
 {
     BOOL ret = FALSE;
-    DWORD gle;
-    while (address == compare)
+    LONG compare;
+
+    do
     {
-        SetLastError(0xdeadbeef);
-        ret = pWaitOnAddress(&address, &compare, sizeof(compare), INFINITE);
-        gle = GetLastError();
-        ok(gle == 0xdeadbeef || broken(gle == ERROR_SUCCESS) /* Win 8 */, "got %d\n", gle);
-    }
-    ok(ret, "got %d\n", ret);
+        while (!(compare = address))
+        {
+            SetLastError(0xdeadbeef);
+            ret = pWaitOnAddress(&address, &compare, sizeof(compare), INFINITE);
+            ok(ret, "wait failed\n");
+            ok(GetLastError() == 0xdeadbeef || broken(GetLastError() == ERROR_SUCCESS) /* Win 8 */,
+                    "got error %d\n", GetLastError());
+        }
+    } while (InterlockedCompareExchange(&address, compare - 1, compare) != compare);
+
     return 0;
 }
 
@@ -51,6 +55,7 @@ static void test_WaitOnAddress(void)
 {
     DWORD gle, val, nthreads;
     HANDLE threads[8];
+    LONG compare;
     BOOL ret;
     int i;
 
@@ -64,8 +69,8 @@ static void test_WaitOnAddress(void)
     compare = 0;
     if (0) /* crash on Windows */
     {
-        ret = pWaitOnAddress(&address, NULL, 8, 0);
-        ret = pWaitOnAddress(NULL, &compare, 8, 0);
+        ret = pWaitOnAddress(&address, NULL, 4, 0);
+        ret = pWaitOnAddress(NULL, &compare, 4, 0);
     }
 
     /* invalid arguments */
@@ -111,15 +116,15 @@ static void test_WaitOnAddress(void)
 
     /* different address size */
     address = 0;
-    compare = 0xffff0000;
+    compare = 0xff00;
     SetLastError(0xdeadbeef);
-    ret = pWaitOnAddress(&address, &compare, 4, 0);
+    ret = pWaitOnAddress(&address, &compare, 2, 0);
     gle = GetLastError();
     ok(gle == 0xdeadbeef || broken(gle == ERROR_SUCCESS) /* Win 8 */, "got %d\n", gle);
     ok(ret, "got %d\n", ret);
 
     SetLastError(0xdeadbeef);
-    ret = pWaitOnAddress(&address, &compare, 2, 0);
+    ret = pWaitOnAddress(&address, &compare, 1, 0);
     gle = GetLastError();
     ok(gle == ERROR_TIMEOUT, "got %d\n", gle);
     ok(!ret, "got %d\n", ret);
@@ -128,38 +133,35 @@ static void test_WaitOnAddress(void)
     address = 0;
     compare = 1;
     SetLastError(0xdeadbeef);
-    ret = pWaitOnAddress(&address, &compare, 8, 0);
+    ret = pWaitOnAddress(&address, &compare, 4, 0);
     gle = GetLastError();
     ok(gle == 0xdeadbeef || broken(gle == ERROR_SUCCESS) /* Win 8 */, "got %d\n", gle);
     ok(ret, "got %d\n", ret);
 
     /* WakeByAddressAll */
     address = 0;
-    compare = 0;
     for (i = 0; i < ARRAY_SIZE(threads); i++)
         threads[i] = CreateThread(NULL, 0, test_WaitOnAddress_func, NULL, 0, NULL);
 
     Sleep(100);
-    address = ~0;
+    address = ARRAY_SIZE(threads);
     pWakeByAddressAll(&address);
     val = WaitForMultipleObjects(ARRAY_SIZE(threads), threads, TRUE, 5000);
     ok(val == WAIT_OBJECT_0, "got %d\n", val);
     for (i = 0; i < ARRAY_SIZE(threads); i++)
         CloseHandle(threads[i]);
+    ok(!address, "got unexpected value %s\n", wine_dbgstr_longlong(address));
 
     /* WakeByAddressSingle */
     address = 0;
     for (i = 0; i < ARRAY_SIZE(threads); i++)
-        threads[i] = CreateThread(NULL, 0, test_WaitOnAddress_func, NULL, 0, NULL);
+            threads[i] = CreateThread(NULL, 0, test_WaitOnAddress_func, NULL, 0, NULL);
 
     Sleep(100);
-    address = 1;
     nthreads = ARRAY_SIZE(threads);
+    address = ARRAY_SIZE(threads);
     while (nthreads)
     {
-        val = WaitForMultipleObjects(nthreads, threads, FALSE, 0);
-        ok(val == STATUS_TIMEOUT, "got %u\n", val);
-
         pWakeByAddressSingle(&address);
         val = WaitForMultipleObjects(nthreads, threads, FALSE, 2000);
         ok(val < WAIT_OBJECT_0 + nthreads, "got %u\n", val);
@@ -167,7 +169,7 @@ static void test_WaitOnAddress(void)
         memmove(&threads[val], &threads[val+1], (nthreads - val - 1) * sizeof(threads[0]));
         nthreads--;
     }
-
+    ok(!address, "got unexpected value %s\n", wine_dbgstr_longlong(address));
 }
 
 START_TEST(sync)
-- 
2.20.1

[PATCH v3 2/2] ntdll: Add a futex-based implementation of WaitOnAddress().

[Zebediah Figura]

Signed-off-by: Zebediah Figura <z.figura12(a)gmail.com>
---
 dlls/ntdll/sync.c | 139 ++++++++++++++++++++++++++++++++++++++++++++++
 1 file changed, 139 insertions(+)

diff --git a/dlls/ntdll/sync.c b/dlls/ntdll/sync.c
index 62cb3cd5ec..851356182e 100644
--- a/dlls/ntdll/sync.c
+++ b/dlls/ntdll/sync.c
@@ -26,7 +26,11 @@
 
 #include <assert.h>
 #include <errno.h>
+#include <limits.h>
 #include <signal.h>
+#ifdef HAVE_SYS_SYSCALL_H
+#include <sys/syscall.h>
+#endif
 #ifdef HAVE_SYS_TIME_H
 # include <sys/time.h>
 #endif
@@ -63,6 +67,8 @@ HANDLE keyed_event = NULL;
 
 static const LARGE_INTEGER zero_timeout;
 
+#define TICKSPERSEC 10000000
+
 static inline int interlocked_dec_if_nonzero( int *dest )
 {
     int val, tmp;
@@ -74,6 +80,41 @@ static inline int interlocked_dec_if_nonzero( int *dest )
     return val;
 }
 
+
+#ifdef __linux__
+
+static int wait_op = 128; /*FUTEX_WAIT|FUTEX_PRIVATE_FLAG*/
+static int wake_op = 129; /*FUTEX_WAKE|FUTEX_PRIVATE_FLAG*/
+
+static inline int futex_wait( const int *addr, int val, struct timespec *timeout )
+{
+    return syscall( __NR_futex, addr, wait_op, val, timeout, 0, 0 );
+}
+
+static inline int futex_wake( const int *addr, int val )
+{
+    return syscall( __NR_futex, addr, wake_op, val, NULL, 0, 0 );
+}
+
+static inline int use_futexes(void)
+{
+    static int supported = -1;
+
+    if (supported == -1)
+    {
+        futex_wait( &supported, 10, NULL );
+        if (errno == ENOSYS)
+        {
+            wait_op = 0; /*FUTEX_WAIT*/
+            wake_op = 1; /*FUTEX_WAKE*/
+            futex_wait( &supported, 10, NULL );
+        }
+        supported = (errno != ENOSYS);
+    }
+    return supported;
+}
+#endif
+
 /* creates a struct security_descriptor and contained information in one contiguous piece of memory */
 NTSTATUS alloc_object_attributes( const OBJECT_ATTRIBUTES *attr, struct object_attributes **ret,
                                   data_size_t *ret_len )
@@ -1987,6 +2028,95 @@ static BOOL compare_addr( const void *addr, const void *cmp, SIZE_T size )
     return FALSE;
 }
 
+#ifdef __linux__
+/* We can't map addresses to futex directly, because an application can wait on
+ * 8 bytes, and we can't pass all 8 as the compare value to futex(). Instead we
+ * map all addresses to a small fixed table of futexes. This may result in
+ * spurious wakes, but the application is already expected to handle those. */
+
+static int addr_futex_table[256];
+
+static inline int *hash_addr( const void *addr )
+{
+    ULONG_PTR val = (ULONG_PTR)addr;
+
+    return &addr_futex_table[(val >> 2) & 255];
+}
+
+static inline NTSTATUS fast_wait_addr( const void *addr, const void *cmp, SIZE_T size,
+                                       const LARGE_INTEGER *timeout )
+{
+    int *futex;
+    int val;
+    LARGE_INTEGER now;
+    timeout_t diff;
+    struct timespec timespec;
+    int ret;
+
+    if (!use_futexes())
+        return STATUS_NOT_IMPLEMENTED;
+
+    futex = hash_addr( addr );
+
+    /* We must read the previous value of the futex before checking the value
+     * of the address being waited on. That way, if we receive a wake between
+     * now and waiting on the futex, we know that val will have changed.
+     * Use an atomic load so that memory accesses are ordered between this read
+     * and the increment below. */
+    val = interlocked_cmpxchg( futex, 0, 0 );
+    if (!compare_addr( addr, cmp, size ))
+        return STATUS_SUCCESS;
+
+    if (timeout)
+    {
+        if (timeout->QuadPart > 0)
+        {
+            NtQuerySystemTime( &now );
+            diff = timeout->QuadPart - now.QuadPart;
+        }
+        else
+            diff = -timeout->QuadPart;
+
+        timespec.tv_sec  = diff / TICKSPERSEC;
+        timespec.tv_nsec = (diff % TICKSPERSEC) * 100;
+
+        ret = futex_wait( futex, val, ×pec );
+    }
+    else
+        ret = futex_wait( futex, val, NULL );
+
+    if (ret == -1 && errno == ETIMEDOUT)
+        return STATUS_TIMEOUT;
+    return STATUS_SUCCESS;
+}
+
+static inline NTSTATUS fast_wake_addr( const void *addr )
+{
+    int *futex;
+
+    if (!use_futexes())
+        return STATUS_NOT_IMPLEMENTED;
+
+    futex = hash_addr( addr );
+
+    interlocked_xchg_add( futex, 1 );
+
+    futex_wake( futex, INT_MAX );
+    return STATUS_SUCCESS;
+}
+#else
+static inline NTSTATUS fast_wait_addr( const void *addr, const void *cmp, SIZE_T size,
+                                       const LARGE_INTEGER *timeout )
+{
+    return STATUS_NOT_IMPLEMENTED;
+}
+
+static inline NTSTATUS fast_wake_addr( const void *addr )
+{
+    return STATUS_NOT_IMPLEMENTED;
+}
+#endif
+
 /***********************************************************************
  *           RtlWaitOnAddress   (NTDLL.@)
  */
@@ -2005,6 +2135,9 @@ NTSTATUS WINAPI RtlWaitOnAddress( const void *addr, const void *cmp, SIZE_T size
     if (size != 1 && size != 2 && size != 4 && size != 8)
         return STATUS_INVALID_PARAMETER;
 
+    if ((ret = fast_wait_addr( addr, cmp, size, timeout )) != STATUS_NOT_IMPLEMENTED)
+        return ret;
+
     select_op.keyed_event.op     = SELECT_KEYED_EVENT_WAIT;
     select_op.keyed_event.handle = wine_server_obj_handle( keyed_event );
     select_op.keyed_event.key    = wine_server_client_ptr( addr );
@@ -2059,6 +2192,9 @@ NTSTATUS WINAPI RtlWaitOnAddress( const void *addr, const void *cmp, SIZE_T size
  */
 void WINAPI RtlWakeAddressAll( const void *addr )
 {
+    if (fast_wake_addr( addr ) != STATUS_NOT_IMPLEMENTED)
+        return;
+
     RtlEnterCriticalSection( &addr_section );
     while (NtReleaseKeyedEvent( 0, addr, 0, &zero_timeout ) == STATUS_SUCCESS) {}
     RtlLeaveCriticalSection( &addr_section );
@@ -2069,6 +2205,9 @@ void WINAPI RtlWakeAddressAll( const void *addr )
  */
 void WINAPI RtlWakeAddressSingle( const void *addr )
 {
+    if (fast_wake_addr( addr ) != STATUS_NOT_IMPLEMENTED)
+        return;
+
     RtlEnterCriticalSection( &addr_section );
     NtReleaseKeyedEvent( 0, addr, 0, &zero_timeout );
     RtlLeaveCriticalSection( &addr_section );
-- 
2.20.1