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