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