dlls/ntdll/sync.c

   1 /*
   2  *      Process synchronisation
   3  *
   4  * Copyright 1996, 1997, 1998 Marcus Meissner
   5  * Copyright 1997, 1998, 1999 Alexandre Julliard
   6  * Copyright 1999, 2000 Juergen Schmied
   7  * Copyright 2003 Eric Pouech
   8  *
   9  * This library is free software; you can redistribute it and/or
  10  * modify it under the terms of the GNU Lesser General Public
  11  * License as published by the Free Software Foundation; either
  12  * version 2.1 of the License, or (at your option) any later version.
  13  *
  14  * This library is distributed in the hope that it will be useful,
  15  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  16  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  17  * Lesser General Public License for more details.
  18  *
  19  * You should have received a copy of the GNU Lesser General Public
  20  * License along with this library; if not, write to the Free Software
  21  * Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301, USA
  22  */
  23
  24 #include <limits.h>
  25 #include <string.h>
  26 #include <stdarg.h>
  27 #include <stdio.h>
  28 #include <stdlib.h>
  29 #include <time.h>
  30
  31 #include "ntstatus.h"
  32 #define WIN32_NO_STATUS
  33 #define NONAMELESSUNION
  34 #include "windef.h"
  35 #include "winternl.h"
  36 #include "wine/debug.h"
  37 #include "wine/list.h"
  38 #include "ntdll_misc.h"
  39
  40 WINE_DEFAULT_DEBUG_CHANNEL(sync);
  41 WINE_DECLARE_DEBUG_CHANNEL(relay);
  42
  43 static const char *debugstr_timeout( const LARGE_INTEGER *timeout )
  44 {
  45     if (!timeout) return "(infinite)";
  46     return wine_dbgstr_longlong( timeout->QuadPart );
  47 }
  48
  49 /******************************************************************
  50  *              RtlRunOnceInitialize (NTDLL.@)
  51  */
  52 void WINAPI RtlRunOnceInitialize( RTL_RUN_ONCE *once )
  53 {
  54     once->Ptr = NULL;
  55 }
  56
  57 /******************************************************************
  58  *              RtlRunOnceBeginInitialize (NTDLL.@)
  59  */
  60 DWORD WINAPI RtlRunOnceBeginInitialize( RTL_RUN_ONCE *once, ULONG flags, void **context )
  61 {
  62     if (flags & RTL_RUN_ONCE_CHECK_ONLY)
  63     {
  64         ULONG_PTR val = (ULONG_PTR)once->Ptr;
  65
  66         if (flags & RTL_RUN_ONCE_ASYNC) return STATUS_INVALID_PARAMETER;
  67         if ((val & 3) != 2) return STATUS_UNSUCCESSFUL;
  68         if (context) *context = (void *)(val & ~3);
  69         return STATUS_SUCCESS;
  70     }
  71
  72     for (;;)
  73     {
  74         ULONG_PTR next, val = (ULONG_PTR)once->Ptr;
  75
  76         switch (val & 3)
  77         {
  78         case 0:  /* first time */
  79             if (!InterlockedCompareExchangePointer( &once->Ptr,
  80                                                     (flags & RTL_RUN_ONCE_ASYNC) ? (void *)3 : (void *)1, 0 ))
  81                 return STATUS_PENDING;
  82             break;
  83
  84         case 1:  /* in progress, wait */
  85             if (flags & RTL_RUN_ONCE_ASYNC) return STATUS_INVALID_PARAMETER;
  86             next = val & ~3;
  87             if (InterlockedCompareExchangePointer( &once->Ptr, (void *)((ULONG_PTR)&next | 1),
  88                                                    (void *)val ) == (void *)val)
  89                 NtWaitForKeyedEvent( 0, &next, FALSE, NULL );
  90             break;
  91
  92         case 2:  /* done */
  93             if (context) *context = (void *)(val & ~3);
  94             return STATUS_SUCCESS;
  95
  96         case 3:  /* in progress, async */
  97             if (!(flags & RTL_RUN_ONCE_ASYNC)) return STATUS_INVALID_PARAMETER;
  98             return STATUS_PENDING;
  99         }
 100     }
 101 }
 102
 103 /******************************************************************
 104  *              RtlRunOnceComplete (NTDLL.@)
 105  */
 106 DWORD WINAPI RtlRunOnceComplete( RTL_RUN_ONCE *once, ULONG flags, void *context )
 107 {
 108     if ((ULONG_PTR)context & 3) return STATUS_INVALID_PARAMETER;
 109
 110     if (flags & RTL_RUN_ONCE_INIT_FAILED)
 111     {
 112         if (context) return STATUS_INVALID_PARAMETER;
 113         if (flags & RTL_RUN_ONCE_ASYNC) return STATUS_INVALID_PARAMETER;
 114     }
 115     else context = (void *)((ULONG_PTR)context | 2);
 116
 117     for (;;)
 118     {
 119         ULONG_PTR val = (ULONG_PTR)once->Ptr;
 120
 121         switch (val & 3)
 122         {
 123         case 1:  /* in progress */
 124             if (InterlockedCompareExchangePointer( &once->Ptr, context, (void *)val ) != (void *)val) break;
 125             val &= ~3;
 126             while (val)
 127             {
 128                 ULONG_PTR next = *(ULONG_PTR *)val;
 129                 NtReleaseKeyedEvent( 0, (void *)val, FALSE, NULL );
 130                 val = next;
 131             }
 132             return STATUS_SUCCESS;
 133
 134         case 3:  /* in progress, async */
 135             if (!(flags & RTL_RUN_ONCE_ASYNC)) return STATUS_INVALID_PARAMETER;
 136             if (InterlockedCompareExchangePointer( &once->Ptr, context, (void *)val ) != (void *)val) break;
 137             return STATUS_SUCCESS;
 138
 139         default:
 140             return STATUS_UNSUCCESSFUL;
 141         }
 142     }
 143 }
 144
 145
 146 /***********************************************************************
 147  * Critical sections
 148  ***********************************************************************/
 149
 150
 151 static void *no_debug_info_marker = (void *)(ULONG_PTR)-1;
 152
 153 static BOOL crit_section_has_debuginfo( const RTL_CRITICAL_SECTION *crit )
 154 {
 155     return crit->DebugInfo != NULL && crit->DebugInfo != no_debug_info_marker;
 156 }
 157
 158 static inline HANDLE get_semaphore( RTL_CRITICAL_SECTION *crit )
 159 {
 160     HANDLE ret = crit->LockSemaphore;
 161     if (!ret)
 162     {
 163         HANDLE sem;
 164         if (NtCreateSemaphore( &sem, SEMAPHORE_ALL_ACCESS, NULL, 0, 1 )) return 0;
 165         if (!(ret = InterlockedCompareExchangePointer( &crit->LockSemaphore, sem, 0 )))
 166             ret = sem;
 167         else
 168             NtClose(sem);  /* somebody beat us to it */
 169     }
 170     return ret;
 171 }
 172
 173 static inline NTSTATUS wait_semaphore( RTL_CRITICAL_SECTION *crit, int timeout )
 174 {
 175     LARGE_INTEGER time = {.QuadPart = timeout * (LONGLONG)-10000000};
 176
 177     /* debug info is cleared by MakeCriticalSectionGlobal */
 178     if (!crit_section_has_debuginfo( crit ))
 179     {
 180         HANDLE sem = get_semaphore( crit );
 181         return NtWaitForSingleObject( sem, FALSE, &time );
 182     }
 183     else
 184     {
 185         int *lock = (int *)&crit->LockSemaphore;
 186         while (!InterlockedCompareExchange( lock, 0, 1 ))
 187         {
 188             static const int zero;
 189             /* this may wait longer than specified in case of multiple wake-ups */
 190             if (RtlWaitOnAddress( lock, &zero, sizeof(int), &time ) == STATUS_TIMEOUT)
 191                 return STATUS_TIMEOUT;
 192         }
 193         return STATUS_WAIT_0;
 194     }
 195 }
 196
 197 /******************************************************************************
 198  *      RtlInitializeCriticalSection   (NTDLL.@)
 199  */
 200 NTSTATUS WINAPI RtlInitializeCriticalSection( RTL_CRITICAL_SECTION *crit )
 201 {
 202     return RtlInitializeCriticalSectionEx( crit, 0, 0 );
 203 }
 204
 205
 206 /******************************************************************************
 207  *      RtlInitializeCriticalSectionAndSpinCount   (NTDLL.@)
 208  */
 209 NTSTATUS WINAPI RtlInitializeCriticalSectionAndSpinCount( RTL_CRITICAL_SECTION *crit, ULONG spincount )
 210 {
 211     return RtlInitializeCriticalSectionEx( crit, spincount, 0 );
 212 }
 213
 214
 215 /******************************************************************************
 216  *      RtlInitializeCriticalSectionEx   (NTDLL.@)
 217  */
 218 NTSTATUS WINAPI RtlInitializeCriticalSectionEx( RTL_CRITICAL_SECTION *crit, ULONG spincount, ULONG flags )
 219 {
 220     if (flags & (RTL_CRITICAL_SECTION_FLAG_DYNAMIC_SPIN|RTL_CRITICAL_SECTION_FLAG_STATIC_INIT))
 221         FIXME("(%p,%u,0x%08x) semi-stub\n", crit, spincount, flags);
 222
 223     /* FIXME: if RTL_CRITICAL_SECTION_FLAG_STATIC_INIT is given, we should use
 224      * memory from a static pool to hold the debug info. Then heap.c could pass
 225      * this flag rather than initialising the process heap CS by hand. If this
 226      * is done, then debug info should be managed through Rtlp[Allocate|Free]DebugInfo
 227      * so (e.g.) MakeCriticalSectionGlobal() doesn't free it using HeapFree().
 228      */
 229     if (flags & RTL_CRITICAL_SECTION_FLAG_NO_DEBUG_INFO)
 230         crit->DebugInfo = no_debug_info_marker;
 231     else
 232     {
 233         crit->DebugInfo = RtlAllocateHeap( GetProcessHeap(), 0, sizeof(RTL_CRITICAL_SECTION_DEBUG ));
 234         if (crit->DebugInfo)
 235         {
 236             crit->DebugInfo->Type = 0;
 237             crit->DebugInfo->CreatorBackTraceIndex = 0;
 238             crit->DebugInfo->CriticalSection = crit;
 239             crit->DebugInfo->ProcessLocksList.Blink = &crit->DebugInfo->ProcessLocksList;
 240             crit->DebugInfo->ProcessLocksList.Flink = &crit->DebugInfo->ProcessLocksList;
 241             crit->DebugInfo->EntryCount = 0;
 242             crit->DebugInfo->ContentionCount = 0;
 243             memset( crit->DebugInfo->Spare, 0, sizeof(crit->DebugInfo->Spare) );
 244         }
 245     }
 246     crit->LockCount      = -1;
 247     crit->RecursionCount = 0;
 248     crit->OwningThread   = 0;
 249     crit->LockSemaphore  = 0;
 250     if (NtCurrentTeb()->Peb->NumberOfProcessors <= 1) spincount = 0;
 251     crit->SpinCount = spincount & ~0x80000000;
 252     return STATUS_SUCCESS;
 253 }
 254
 255
 256 /******************************************************************************
 257  *      RtlSetCriticalSectionSpinCount   (NTDLL.@)
 258  */
 259 ULONG WINAPI RtlSetCriticalSectionSpinCount( RTL_CRITICAL_SECTION *crit, ULONG spincount )
 260 {
 261     ULONG oldspincount = crit->SpinCount;
 262     if (NtCurrentTeb()->Peb->NumberOfProcessors <= 1) spincount = 0;
 263     crit->SpinCount = spincount;
 264     return oldspincount;
 265 }
 266
 267
 268 /******************************************************************************
 269  *      RtlDeleteCriticalSection   (NTDLL.@)
 270  */
 271 NTSTATUS WINAPI RtlDeleteCriticalSection( RTL_CRITICAL_SECTION *crit )
 272 {
 273     crit->LockCount      = -1;
 274     crit->RecursionCount = 0;
 275     crit->OwningThread   = 0;
 276     if (crit_section_has_debuginfo( crit ))
 277     {
 278         /* only free the ones we made in here */
 279         if (!crit->DebugInfo->Spare[0])
 280         {
 281             RtlFreeHeap( GetProcessHeap(), 0, crit->DebugInfo );
 282             crit->DebugInfo = NULL;
 283         }
 284     }
 285     else NtClose( crit->LockSemaphore );
 286     crit->LockSemaphore = 0;
 287     return STATUS_SUCCESS;
 288 }
 289
 290
 291 /******************************************************************************
 292  *      RtlpWaitForCriticalSection   (NTDLL.@)
 293  */
 294 NTSTATUS WINAPI RtlpWaitForCriticalSection( RTL_CRITICAL_SECTION *crit )
 295 {
 296     LONGLONG timeout = NtCurrentTeb()->Peb->CriticalSectionTimeout.QuadPart / -10000000;
 297
 298     /* Don't allow blocking on a critical section during process termination */
 299     if (RtlDllShutdownInProgress())
 300     {
 301         WARN( "process %s is shutting down, returning STATUS_SUCCESS\n",
 302               debugstr_w(NtCurrentTeb()->Peb->ProcessParameters->ImagePathName.Buffer) );
 303         return STATUS_SUCCESS;
 304     }
 305
 306     for (;;)
 307     {
 308         EXCEPTION_RECORD rec;
 309         NTSTATUS status = wait_semaphore( crit, 5 );
 310         timeout -= 5;
 311
 312         if ( status == STATUS_TIMEOUT )
 313         {
 314             const char *name = NULL;
 315             if (crit_section_has_debuginfo( crit )) name = (char *)crit->DebugInfo->Spare[0];
 316             if (!name) name = "?";
 317             ERR( "section %p %s wait timed out in thread %04x, blocked by %04x, retrying (60 sec)\n",
 318                  crit, debugstr_a(name), GetCurrentThreadId(), HandleToULong(crit->OwningThread) );
 319             status = wait_semaphore( crit, 60 );
 320             timeout -= 60;
 321
 322             if ( status == STATUS_TIMEOUT && TRACE_ON(relay) )
 323             {
 324                 ERR( "section %p %s wait timed out in thread %04x, blocked by %04x, retrying (5 min)\n",
 325                      crit, debugstr_a(name), GetCurrentThreadId(), HandleToULong(crit->OwningThread) );
 326                 status = wait_semaphore( crit, 300 );
 327                 timeout -= 300;
 328             }
 329         }
 330         if (status == STATUS_WAIT_0) break;
 331
 332         /* Throw exception only for Wine internal locks */
 333         if (!crit_section_has_debuginfo( crit ) || !crit->DebugInfo->Spare[0]) continue;
 334
 335         /* only throw deadlock exception if configured timeout is reached */
 336         if (timeout > 0) continue;
 337
 338         rec.ExceptionCode    = STATUS_POSSIBLE_DEADLOCK;
 339         rec.ExceptionFlags   = 0;
 340         rec.ExceptionRecord  = NULL;
 341         rec.ExceptionAddress = RtlRaiseException;  /* sic */
 342         rec.NumberParameters = 1;
 343         rec.ExceptionInformation[0] = (ULONG_PTR)crit;
 344         RtlRaiseException( &rec );
 345     }
 346     if (crit_section_has_debuginfo( crit )) crit->DebugInfo->ContentionCount++;
 347     return STATUS_SUCCESS;
 348 }
 349
 350
 351 /******************************************************************************
 352  *      RtlpUnWaitCriticalSection   (NTDLL.@)
 353  */
 354 NTSTATUS WINAPI RtlpUnWaitCriticalSection( RTL_CRITICAL_SECTION *crit )
 355 {
 356     NTSTATUS ret;
 357
 358     /* debug info is cleared by MakeCriticalSectionGlobal */
 359     if (!crit_section_has_debuginfo( crit ))
 360     {
 361         HANDLE sem = get_semaphore( crit );
 362         ret = NtReleaseSemaphore( sem, 1, NULL );
 363     }
 364     else
 365     {
 366         int *lock = (int *)&crit->LockSemaphore;
 367         InterlockedExchange( lock, 1 );
 368         RtlWakeAddressSingle( lock );
 369         ret = STATUS_SUCCESS;
 370     }
 371     if (ret) RtlRaiseStatus( ret );
 372     return ret;
 373 }
 374
 375
 376 static inline void small_pause(void)
 377 {
 378 #ifdef __i386__
 379     __asm__ __volatile__( "rep;nop" : : : "memory" );
 380 #else
 381     __asm__ __volatile__( "" : : : "memory" );
 382 #endif
 383 }
 384
 385 /******************************************************************************
 386  *      RtlEnterCriticalSection   (NTDLL.@)
 387  */
 388 NTSTATUS WINAPI RtlEnterCriticalSection( RTL_CRITICAL_SECTION *crit )
 389 {
 390     if (crit->SpinCount)
 391     {
 392         ULONG count;
 393
 394         if (RtlTryEnterCriticalSection( crit )) return STATUS_SUCCESS;
 395         for (count = crit->SpinCount; count > 0; count--)
 396         {
 397             if (crit->LockCount > 0) break;  /* more than one waiter, don't bother spinning */
 398             if (crit->LockCount == -1)       /* try again */
 399             {
 400                 if (InterlockedCompareExchange( &crit->LockCount, 0, -1 ) == -1) goto done;
 401             }
 402             small_pause();
 403         }
 404     }
 405
 406     if (InterlockedIncrement( &crit->LockCount ))
 407     {
 408         if (crit->OwningThread == ULongToHandle(GetCurrentThreadId()))
 409         {
 410             crit->RecursionCount++;
 411             return STATUS_SUCCESS;
 412         }
 413
 414         /* Now wait for it */
 415         RtlpWaitForCriticalSection( crit );
 416     }
 417 done:
 418     crit->OwningThread   = ULongToHandle(GetCurrentThreadId());
 419     crit->RecursionCount = 1;
 420     return STATUS_SUCCESS;
 421 }
 422
 423
 424 /******************************************************************************
 425  *      RtlTryEnterCriticalSection   (NTDLL.@)
 426  */
 427 BOOL WINAPI RtlTryEnterCriticalSection( RTL_CRITICAL_SECTION *crit )
 428 {
 429     BOOL ret = FALSE;
 430     if (InterlockedCompareExchange( &crit->LockCount, 0, -1 ) == -1)
 431     {
 432         crit->OwningThread   = ULongToHandle(GetCurrentThreadId());
 433         crit->RecursionCount = 1;
 434         ret = TRUE;
 435     }
 436     else if (crit->OwningThread == ULongToHandle(GetCurrentThreadId()))
 437     {
 438         InterlockedIncrement( &crit->LockCount );
 439         crit->RecursionCount++;
 440         ret = TRUE;
 441     }
 442     return ret;
 443 }
 444
 445
 446 /******************************************************************************
 447  *      RtlIsCriticalSectionLocked   (NTDLL.@)
 448  */
 449 BOOL WINAPI RtlIsCriticalSectionLocked( RTL_CRITICAL_SECTION *crit )
 450 {
 451     return crit->RecursionCount != 0;
 452 }
 453
 454
 455 /******************************************************************************
 456  *      RtlIsCriticalSectionLockedByThread   (NTDLL.@)
 457  */
 458 BOOL WINAPI RtlIsCriticalSectionLockedByThread( RTL_CRITICAL_SECTION *crit )
 459 {
 460     return crit->OwningThread == ULongToHandle(GetCurrentThreadId()) &&
 461            crit->RecursionCount;
 462 }
 463
 464
 465 /******************************************************************************
 466  *      RtlLeaveCriticalSection   (NTDLL.@)
 467  */
 468 NTSTATUS WINAPI RtlLeaveCriticalSection( RTL_CRITICAL_SECTION *crit )
 469 {
 470     if (--crit->RecursionCount)
 471     {
 472         if (crit->RecursionCount > 0) InterlockedDecrement( &crit->LockCount );
 473         else ERR( "section %p is not acquired\n", crit );
 474     }
 475     else
 476     {
 477         crit->OwningThread = 0;
 478         if (InterlockedDecrement( &crit->LockCount ) >= 0)
 479         {
 480             /* someone is waiting */
 481             RtlpUnWaitCriticalSection( crit );
 482         }
 483     }
 484     return STATUS_SUCCESS;
 485 }
 486
 487 /******************************************************************
 488  *              RtlRunOnceExecuteOnce (NTDLL.@)
 489  */
 490 DWORD WINAPI RtlRunOnceExecuteOnce( RTL_RUN_ONCE *once, PRTL_RUN_ONCE_INIT_FN func,
 491                                     void *param, void **context )
 492 {
 493     DWORD ret = RtlRunOnceBeginInitialize( once, 0, context );
 494
 495     if (ret != STATUS_PENDING) return ret;
 496
 497     if (!func( once, param, context ))
 498     {
 499         RtlRunOnceComplete( once, RTL_RUN_ONCE_INIT_FAILED, NULL );
 500         return STATUS_UNSUCCESSFUL;
 501     }
 502
 503     return RtlRunOnceComplete( once, 0, context ? *context : NULL );
 504 }
 505
 506 struct srw_lock
 507 {
 508     short exclusive_waiters;
 509
 510     /* Number of shared owners, or -1 if owned exclusive.
 511      *
 512      * Sadly Windows has no equivalent to FUTEX_WAIT_BITSET, so in order to wake
 513      * up *only* exclusive or *only* shared waiters (and thus avoid spurious
 514      * wakeups), we need to wait on two different addresses.
 515      * RtlAcquireSRWLockShared() needs to know the values of "exclusive_waiters"
 516      * and "owners", but RtlAcquireSRWLockExclusive() only needs to know the
 517      * value of "owners", so the former can wait on the entire structure, and
 518      * the latter waits only on the "owners" member. Note then that "owners"
 519      * must not be the first element in the structure.
 520      */
 521     short owners;
 522 };
 523 C_ASSERT( sizeof(struct srw_lock) == 4 );
 524
 525 /***********************************************************************
 526  *              RtlInitializeSRWLock (NTDLL.@)
 527  *
 528  * NOTES
 529  *  Please note that SRWLocks do not keep track of the owner of a lock.
 530  *  It doesn't make any difference which thread for example unlocks an
 531  *  SRWLock (see corresponding tests). This implementation uses two
 532  *  keyed events (one for the exclusive waiters and one for the shared
 533  *  waiters) and is limited to 2^15-1 waiting threads.
 534  */
 535 void WINAPI RtlInitializeSRWLock( RTL_SRWLOCK *lock )
 536 {
 537     lock->Ptr = NULL;
 538 }
 539
 540 /***********************************************************************
 541  *              RtlAcquireSRWLockExclusive (NTDLL.@)
 542  *
 543  * NOTES
 544  *  Unlike RtlAcquireResourceExclusive this function doesn't allow
 545  *  nested calls from the same thread. "Upgrading" a shared access lock
 546  *  to an exclusive access lock also doesn't seem to be supported.
 547  */
 548 void WINAPI RtlAcquireSRWLockExclusive( RTL_SRWLOCK *lock )
 549 {
 550     union { RTL_SRWLOCK *rtl; struct srw_lock *s; LONG *l; } u = { lock };
 551
 552     InterlockedIncrement16( &u.s->exclusive_waiters );
 553
 554     for (;;)
 555     {
 556         union { struct srw_lock s; LONG l; } old, new;
 557         BOOL wait;
 558
 559         do
 560         {
 561             old.s = *u.s;
 562             new.s = old.s;
 563
 564             if (!old.s.owners)
 565             {
 566                 /* Not locked exclusive or shared. We can try to grab it. */
 567                 new.s.owners = -1;
 568                 --new.s.exclusive_waiters;
 569                 wait = FALSE;
 570             }
 571             else
 572             {
 573                 wait = TRUE;
 574             }
 575         } while (InterlockedCompareExchange( u.l, new.l, old.l ) != old.l);
 576
 577         if (!wait) return;
 578         RtlWaitOnAddress( &u.s->owners, &new.s.owners, sizeof(short), NULL );
 579     }
 580 }
 581
 582 /***********************************************************************
 583  *              RtlAcquireSRWLockShared (NTDLL.@)
 584  *
 585  * NOTES
 586  *   Do not call this function recursively - it will only succeed when
 587  *   there are no threads waiting for an exclusive lock!
 588  */
 589 void WINAPI RtlAcquireSRWLockShared( RTL_SRWLOCK *lock )
 590 {
 591     union { RTL_SRWLOCK *rtl; struct srw_lock *s; LONG *l; } u = { lock };
 592
 593     for (;;)
 594     {
 595         union { struct srw_lock s; LONG l; } old, new;
 596         BOOL wait;
 597
 598         do
 599         {
 600             old.s = *u.s;
 601             new = old;
 602
 603             if (old.s.owners != -1 && !old.s.exclusive_waiters)
 604             {
 605                 /* Not locked exclusive, and no exclusive waiters.
 606                  * We can try to grab it. */
 607                 ++new.s.owners;
 608                 wait = FALSE;
 609             }
 610             else
 611             {
 612                 wait = TRUE;
 613             }
 614         } while (InterlockedCompareExchange( u.l, new.l, old.l ) != old.l);
 615
 616         if (!wait) return;
 617         RtlWaitOnAddress( u.s, &new.s, sizeof(struct srw_lock), NULL );
 618     }
 619 }
 620
 621 /***********************************************************************
 622  *              RtlReleaseSRWLockExclusive (NTDLL.@)
 623  */
 624 void WINAPI RtlReleaseSRWLockExclusive( RTL_SRWLOCK *lock )
 625 {
 626     union { RTL_SRWLOCK *rtl; struct srw_lock *s; LONG *l; } u = { lock };
 627     union { struct srw_lock s; LONG l; } old, new;
 628
 629     do
 630     {
 631         old.s = *u.s;
 632         new = old;
 633
 634         if (old.s.owners != -1) ERR("Lock %p is not owned exclusive!\n", lock);
 635
 636         new.s.owners = 0;
 637     } while (InterlockedCompareExchange( u.l, new.l, old.l ) != old.l);
 638
 639     if (new.s.exclusive_waiters)
 640         RtlWakeAddressSingle( &u.s->owners );
 641     else
 642         RtlWakeAddressAll( u.s );
 643 }
 644
 645 /***********************************************************************
 646  *              RtlReleaseSRWLockShared (NTDLL.@)
 647  */
 648 void WINAPI RtlReleaseSRWLockShared( RTL_SRWLOCK *lock )
 649 {
 650     union { RTL_SRWLOCK *rtl; struct srw_lock *s; LONG *l; } u = { lock };
 651     union { struct srw_lock s; LONG l; } old, new;
 652
 653     do
 654     {
 655         old.s = *u.s;
 656         new = old;
 657
 658         if (old.s.owners == -1) ERR("Lock %p is owned exclusive!\n", lock);
 659         else if (!old.s.owners) ERR("Lock %p is not owned shared!\n", lock);
 660
 661         --new.s.owners;
 662     } while (InterlockedCompareExchange( u.l, new.l, old.l ) != old.l);
 663
 664     if (!new.s.owners)
 665         RtlWakeAddressSingle( &u.s->owners );
 666 }
 667
 668 /***********************************************************************
 669  *              RtlTryAcquireSRWLockExclusive (NTDLL.@)
 670  *
 671  * NOTES
 672  *  Similarly to AcquireSRWLockExclusive, recursive calls are not allowed
 673  *  and will fail with a FALSE return value.
 674  */
 675 BOOLEAN WINAPI RtlTryAcquireSRWLockExclusive( RTL_SRWLOCK *lock )
 676 {
 677     union { RTL_SRWLOCK *rtl; struct srw_lock *s; LONG *l; } u = { lock };
 678     union { struct srw_lock s; LONG l; } old, new;
 679     BOOLEAN ret;
 680
 681     do
 682     {
 683         old.s = *u.s;
 684         new.s = old.s;
 685
 686         if (!old.s.owners)
 687         {
 688             /* Not locked exclusive or shared. We can try to grab it. */
 689             new.s.owners = -1;
 690             ret = TRUE;
 691         }
 692         else
 693         {
 694             ret = FALSE;
 695         }
 696     } while (InterlockedCompareExchange( u.l, new.l, old.l ) != old.l);
 697
 698     return ret;
 699 }
 700
 701 /***********************************************************************
 702  *              RtlTryAcquireSRWLockShared (NTDLL.@)
 703  */
 704 BOOLEAN WINAPI RtlTryAcquireSRWLockShared( RTL_SRWLOCK *lock )
 705 {
 706     union { RTL_SRWLOCK *rtl; struct srw_lock *s; LONG *l; } u = { lock };
 707     union { struct srw_lock s; LONG l; } old, new;
 708     BOOLEAN ret;
 709
 710     do
 711     {
 712         old.s = *u.s;
 713         new.s = old.s;
 714
 715         if (old.s.owners != -1 && !old.s.exclusive_waiters)
 716         {
 717             /* Not locked exclusive, and no exclusive waiters.
 718              * We can try to grab it. */
 719             ++new.s.owners;
 720             ret = TRUE;
 721         }
 722         else
 723         {
 724             ret = FALSE;
 725         }
 726     } while (InterlockedCompareExchange( u.l, new.l, old.l ) != old.l);
 727
 728     return ret;
 729 }
 730
 731 /***********************************************************************
 732  *           RtlInitializeConditionVariable   (NTDLL.@)
 733  *
 734  * Initializes the condition variable with NULL.
 735  *
 736  * PARAMS
 737  *  variable [O] condition variable
 738  *
 739  * RETURNS
 740  *  Nothing.
 741  */
 742 void WINAPI RtlInitializeConditionVariable( RTL_CONDITION_VARIABLE *variable )
 743 {
 744     variable->Ptr = NULL;
 745 }
 746
 747 /***********************************************************************
 748  *           RtlWakeConditionVariable   (NTDLL.@)
 749  *
 750  * Wakes up one thread waiting on the condition variable.
 751  *
 752  * PARAMS
 753  *  variable [I/O] condition variable to wake up.
 754  *
 755  * RETURNS
 756  *  Nothing.
 757  *
 758  * NOTES
 759  *  The calling thread does not have to own any lock in order to call
 760  *  this function.
 761  */
 762 void WINAPI RtlWakeConditionVariable( RTL_CONDITION_VARIABLE *variable )
 763 {
 764     InterlockedIncrement( (int *)&variable->Ptr );
 765     RtlWakeAddressSingle( variable );
 766 }
 767
 768 /***********************************************************************
 769  *           RtlWakeAllConditionVariable   (NTDLL.@)
 770  *
 771  * See WakeConditionVariable, wakes up all waiting threads.
 772  */
 773 void WINAPI RtlWakeAllConditionVariable( RTL_CONDITION_VARIABLE *variable )
 774 {
 775     InterlockedIncrement( (int *)&variable->Ptr );
 776     RtlWakeAddressAll( variable );
 777 }
 778
 779 /***********************************************************************
 780  *           RtlSleepConditionVariableCS   (NTDLL.@)
 781  *
 782  * Atomically releases the critical section and suspends the thread,
 783  * waiting for a Wake(All)ConditionVariable event. Afterwards it enters
 784  * the critical section again and returns.
 785  *
 786  * PARAMS
 787  *  variable  [I/O] condition variable
 788  *  crit      [I/O] critical section to leave temporarily
 789  *  timeout   [I]   timeout
 790  *
 791  * RETURNS
 792  *  see NtWaitForKeyedEvent for all possible return values.
 793  */
 794 NTSTATUS WINAPI RtlSleepConditionVariableCS( RTL_CONDITION_VARIABLE *variable, RTL_CRITICAL_SECTION *crit,
 795                                              const LARGE_INTEGER *timeout )
 796 {
 797     int value = *(int *)&variable->Ptr;
 798     NTSTATUS status;
 799
 800     RtlLeaveCriticalSection( crit );
 801     status = RtlWaitOnAddress( &variable->Ptr, &value, sizeof(value), timeout );
 802     RtlEnterCriticalSection( crit );
 803     return status;
 804 }
 805
 806 /***********************************************************************
 807  *           RtlSleepConditionVariableSRW   (NTDLL.@)
 808  *
 809  * Atomically releases the SRWLock and suspends the thread,
 810  * waiting for a Wake(All)ConditionVariable event. Afterwards it enters
 811  * the SRWLock again with the same access rights and returns.
 812  *
 813  * PARAMS
 814  *  variable  [I/O] condition variable
 815  *  lock      [I/O] SRWLock to leave temporarily
 816  *  timeout   [I]   timeout
 817  *  flags     [I]   type of the current lock (exclusive / shared)
 818  *
 819  * RETURNS
 820  *  see NtWaitForKeyedEvent for all possible return values.
 821  *
 822  * NOTES
 823  *  the behaviour is undefined if the thread doesn't own the lock.
 824  */
 825 NTSTATUS WINAPI RtlSleepConditionVariableSRW( RTL_CONDITION_VARIABLE *variable, RTL_SRWLOCK *lock,
 826                                               const LARGE_INTEGER *timeout, ULONG flags )
 827 {
 828     int value = *(int *)&variable->Ptr;
 829     NTSTATUS status;
 830
 831     if (flags & RTL_CONDITION_VARIABLE_LOCKMODE_SHARED)
 832         RtlReleaseSRWLockShared( lock );
 833     else
 834         RtlReleaseSRWLockExclusive( lock );
 835
 836     status = RtlWaitOnAddress( &variable->Ptr, &value, sizeof(value), timeout );
 837
 838     if (flags & RTL_CONDITION_VARIABLE_LOCKMODE_SHARED)
 839         RtlAcquireSRWLockShared( lock );
 840     else
 841         RtlAcquireSRWLockExclusive( lock );
 842     return status;
 843 }
 844
 845 /* RtlWaitOnAddress() and RtlWakeAddress*(), hereafter referred to as "Win32
 846  * futexes", offer futex-like semantics with a variable set of address sizes,
 847  * but are limited to a single process. They are also fair—the documentation
 848  * specifies this, and tests bear it out.
 849  *
 850  * On Windows they are implemented using NtAlertThreadByThreadId and
 851  * NtWaitForAlertByThreadId, which manipulate a single flag (similar to an
 852  * auto-reset event) per thread. This can be tested by attempting to wake a
 853  * thread waiting in RtlWaitOnAddress() via NtAlertThreadByThreadId.
 854  */
 855
 856 struct futex_entry
 857 {
 858     struct list entry;
 859     const void *addr;
 860     DWORD tid;
 861 };
 862
 863 struct futex_queue
 864 {
 865     struct list queue;
 866     LONG lock;
 867 };
 868
 869 static struct futex_queue futex_queues[256];
 870
 871 static struct futex_queue *get_futex_queue( const void *addr )
 872 {
 873     ULONG_PTR val = (ULONG_PTR)addr;
 874
 875     return &futex_queues[(val >> 4) % ARRAY_SIZE(futex_queues)];
 876 }
 877
 878 static void spin_lock( LONG *lock )
 879 {
 880     while (InterlockedCompareExchange( lock, -1, 0 ))
 881         YieldProcessor();
 882 }
 883
 884 static void spin_unlock( LONG *lock )
 885 {
 886     InterlockedExchange( lock, 0 );
 887 }
 888
 889 static BOOL compare_addr( const void *addr, const void *cmp, SIZE_T size )
 890 {
 891     switch (size)
 892     {
 893         case 1:
 894             return (*(const UCHAR *)addr == *(const UCHAR *)cmp);
 895         case 2:
 896             return (*(const USHORT *)addr == *(const USHORT *)cmp);
 897         case 4:
 898             return (*(const ULONG *)addr == *(const ULONG *)cmp);
 899         case 8:
 900             return (*(const ULONG64 *)addr == *(const ULONG64 *)cmp);
 901     }
 902
 903     return FALSE;
 904 }
 905
 906 /***********************************************************************
 907  *           RtlWaitOnAddress   (NTDLL.@)
 908  */
 909 NTSTATUS WINAPI RtlWaitOnAddress( const void *addr, const void *cmp, SIZE_T size,
 910                                   const LARGE_INTEGER *timeout )
 911 {
 912     struct futex_queue *queue = get_futex_queue( addr );
 913     struct futex_entry entry;
 914     NTSTATUS ret;
 915
 916     TRACE("addr %p cmp %p size %#Ix timeout %s\n", addr, cmp, size, debugstr_timeout( timeout ));
 917
 918     if (size != 1 && size != 2 && size != 4 && size != 8)
 919         return STATUS_INVALID_PARAMETER;
 920
 921     entry.addr = addr;
 922     entry.tid = GetCurrentThreadId();
 923
 924     spin_lock( &queue->lock );
 925
 926     /* Do the comparison inside of the spinlock, to reduce spurious wakeups. */
 927
 928     if (!compare_addr( addr, cmp, size ))
 929     {
 930         spin_unlock( &queue->lock );
 931         return STATUS_SUCCESS;
 932     }
 933
 934     if (!queue->queue.next)
 935         list_init( &queue->queue );
 936     list_add_tail( &queue->queue, &entry.entry );
 937
 938     spin_unlock( &queue->lock );
 939
 940     ret = NtWaitForAlertByThreadId( NULL, timeout );
 941
 942     spin_lock( &queue->lock );
 943     /* We may have already been removed by a call to RtlWakeAddressSingle(). */
 944     if (entry.addr)
 945         list_remove( &entry.entry );
 946     spin_unlock( &queue->lock );
 947
 948     TRACE("returning %#x\n", ret);
 949
 950     if (ret == STATUS_ALERTED) ret = STATUS_SUCCESS;
 951     return ret;
 952 }
 953
 954 /***********************************************************************
 955  *           RtlWakeAddressAll    (NTDLL.@)
 956  */
 957 void WINAPI RtlWakeAddressAll( const void *addr )
 958 {
 959     struct futex_queue *queue = get_futex_queue( addr );
 960     unsigned int count = 0, i;
 961     struct futex_entry *entry;
 962     DWORD tids[256];
 963
 964     TRACE("%p\n", addr);
 965
 966     if (!addr) return;
 967
 968     spin_lock( &queue->lock );
 969
 970     if (!queue->queue.next)
 971         list_init(&queue->queue);
 972
 973     LIST_FOR_EACH_ENTRY( entry, &queue->queue, struct futex_entry, entry )
 974     {
 975         if (entry->addr == addr)
 976         {
 977             /* Try to buffer wakes, so that we don't make a system call while
 978              * holding a spinlock. */
 979             if (count < ARRAY_SIZE(tids))
 980                 tids[count++] = entry->tid;
 981             else
 982                 NtAlertThreadByThreadId( (HANDLE)(DWORD_PTR)entry->tid );
 983         }
 984     }
 985
 986     spin_unlock( &queue->lock );
 987
 988     for (i = 0; i < count; ++i)
 989         NtAlertThreadByThreadId( (HANDLE)(DWORD_PTR)tids[i] );
 990 }
 991
 992 /***********************************************************************
 993  *           RtlWakeAddressSingle (NTDLL.@)
 994  */
 995 void WINAPI RtlWakeAddressSingle( const void *addr )
 996 {
 997     struct futex_queue *queue = get_futex_queue( addr );
 998     struct futex_entry *entry;
 999     DWORD tid = 0;
1000
1001     TRACE("%p\n", addr);
1002
1003     if (!addr) return;
1004
1005     spin_lock( &queue->lock );
1006
1007     if (!queue->queue.next)
1008         list_init(&queue->queue);
1009
1010     LIST_FOR_EACH_ENTRY( entry, &queue->queue, struct futex_entry, entry )
1011     {
1012         if (entry->addr == addr)
1013         {
1014             /* Try to buffer wakes, so that we don't make a system call while
1015              * holding a spinlock. */
1016             tid = entry->tid;
1017
1018             /* Remove this entry from the queue, so that a simultaneous call to
1019              * RtlWakeAddressSingle() will not also wake it—two simultaneous
1020              * calls must wake at least two waiters if they exist. */
1021             entry->addr = NULL;
1022             list_remove( &entry->entry );
1023             break;
1024         }
1025     }
1026
1027     spin_unlock( &queue->lock );
1028
1029     if (tid) NtAlertThreadByThreadId( (HANDLE)(DWORD_PTR)tid );
1030 }