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         LONG *lock = (LONG *)&crit->LockSemaphore;
 186         while (!InterlockedCompareExchange( lock, 0, 1 ))
 187         {
 188             static const LONG zero;
 189             /* this may wait longer than specified in case of multiple wake-ups */
 190             if (RtlWaitOnAddress( lock, &zero, sizeof(LONG), &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         LONG *lock = (LONG *)&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 /******************************************************************************
 377  *      RtlEnterCriticalSection   (NTDLL.@)
 378  */
 379 NTSTATUS WINAPI RtlEnterCriticalSection( RTL_CRITICAL_SECTION *crit )
 380 {
 381     if (crit->SpinCount)
 382     {
 383         ULONG count;
 384
 385         if (RtlTryEnterCriticalSection( crit )) return STATUS_SUCCESS;
 386         for (count = crit->SpinCount; count > 0; count--)
 387         {
 388             if (crit->LockCount > 0) break;  /* more than one waiter, don't bother spinning */
 389             if (crit->LockCount == -1)       /* try again */
 390             {
 391                 if (InterlockedCompareExchange( &crit->LockCount, 0, -1 ) == -1) goto done;
 392             }
 393             YieldProcessor();
 394         }
 395     }
 396
 397     if (InterlockedIncrement( &crit->LockCount ))
 398     {
 399         if (crit->OwningThread == ULongToHandle(GetCurrentThreadId()))
 400         {
 401             crit->RecursionCount++;
 402             return STATUS_SUCCESS;
 403         }
 404
 405         /* Now wait for it */
 406         RtlpWaitForCriticalSection( crit );
 407     }
 408 done:
 409     crit->OwningThread   = ULongToHandle(GetCurrentThreadId());
 410     crit->RecursionCount = 1;
 411     return STATUS_SUCCESS;
 412 }
 413
 414
 415 /******************************************************************************
 416  *      RtlTryEnterCriticalSection   (NTDLL.@)
 417  */
 418 BOOL WINAPI RtlTryEnterCriticalSection( RTL_CRITICAL_SECTION *crit )
 419 {
 420     BOOL ret = FALSE;
 421     if (InterlockedCompareExchange( &crit->LockCount, 0, -1 ) == -1)
 422     {
 423         crit->OwningThread   = ULongToHandle(GetCurrentThreadId());
 424         crit->RecursionCount = 1;
 425         ret = TRUE;
 426     }
 427     else if (crit->OwningThread == ULongToHandle(GetCurrentThreadId()))
 428     {
 429         InterlockedIncrement( &crit->LockCount );
 430         crit->RecursionCount++;
 431         ret = TRUE;
 432     }
 433     return ret;
 434 }
 435
 436
 437 /******************************************************************************
 438  *      RtlIsCriticalSectionLocked   (NTDLL.@)
 439  */
 440 BOOL WINAPI RtlIsCriticalSectionLocked( RTL_CRITICAL_SECTION *crit )
 441 {
 442     return crit->RecursionCount != 0;
 443 }
 444
 445
 446 /******************************************************************************
 447  *      RtlIsCriticalSectionLockedByThread   (NTDLL.@)
 448  */
 449 BOOL WINAPI RtlIsCriticalSectionLockedByThread( RTL_CRITICAL_SECTION *crit )
 450 {
 451     return crit->OwningThread == ULongToHandle(GetCurrentThreadId()) &&
 452            crit->RecursionCount;
 453 }
 454
 455
 456 /******************************************************************************
 457  *      RtlLeaveCriticalSection   (NTDLL.@)
 458  */
 459 NTSTATUS WINAPI RtlLeaveCriticalSection( RTL_CRITICAL_SECTION *crit )
 460 {
 461     if (--crit->RecursionCount)
 462     {
 463         if (crit->RecursionCount > 0) InterlockedDecrement( &crit->LockCount );
 464         else ERR( "section %p is not acquired\n", crit );
 465     }
 466     else
 467     {
 468         crit->OwningThread = 0;
 469         if (InterlockedDecrement( &crit->LockCount ) >= 0)
 470         {
 471             /* someone is waiting */
 472             RtlpUnWaitCriticalSection( crit );
 473         }
 474     }
 475     return STATUS_SUCCESS;
 476 }
 477
 478 /******************************************************************
 479  *              RtlRunOnceExecuteOnce (NTDLL.@)
 480  */
 481 DWORD WINAPI RtlRunOnceExecuteOnce( RTL_RUN_ONCE *once, PRTL_RUN_ONCE_INIT_FN func,
 482                                     void *param, void **context )
 483 {
 484     DWORD ret = RtlRunOnceBeginInitialize( once, 0, context );
 485
 486     if (ret != STATUS_PENDING) return ret;
 487
 488     if (!func( once, param, context ))
 489     {
 490         RtlRunOnceComplete( once, RTL_RUN_ONCE_INIT_FAILED, NULL );
 491         return STATUS_UNSUCCESSFUL;
 492     }
 493
 494     return RtlRunOnceComplete( once, 0, context ? *context : NULL );
 495 }
 496
 497 struct srw_lock
 498 {
 499     short exclusive_waiters;
 500
 501     /* Number of shared owners, or -1 if owned exclusive.
 502      *
 503      * Sadly Windows has no equivalent to FUTEX_WAIT_BITSET, so in order to wake
 504      * up *only* exclusive or *only* shared waiters (and thus avoid spurious
 505      * wakeups), we need to wait on two different addresses.
 506      * RtlAcquireSRWLockShared() needs to know the values of "exclusive_waiters"
 507      * and "owners", but RtlAcquireSRWLockExclusive() only needs to know the
 508      * value of "owners", so the former can wait on the entire structure, and
 509      * the latter waits only on the "owners" member. Note then that "owners"
 510      * must not be the first element in the structure.
 511      */
 512     short owners;
 513 };
 514 C_ASSERT( sizeof(struct srw_lock) == 4 );
 515
 516 /***********************************************************************
 517  *              RtlInitializeSRWLock (NTDLL.@)
 518  *
 519  * NOTES
 520  *  Please note that SRWLocks do not keep track of the owner of a lock.
 521  *  It doesn't make any difference which thread for example unlocks an
 522  *  SRWLock (see corresponding tests). This implementation uses two
 523  *  keyed events (one for the exclusive waiters and one for the shared
 524  *  waiters) and is limited to 2^15-1 waiting threads.
 525  */
 526 void WINAPI RtlInitializeSRWLock( RTL_SRWLOCK *lock )
 527 {
 528     lock->Ptr = NULL;
 529 }
 530
 531 /***********************************************************************
 532  *              RtlAcquireSRWLockExclusive (NTDLL.@)
 533  *
 534  * NOTES
 535  *  Unlike RtlAcquireResourceExclusive this function doesn't allow
 536  *  nested calls from the same thread. "Upgrading" a shared access lock
 537  *  to an exclusive access lock also doesn't seem to be supported.
 538  */
 539 void WINAPI RtlAcquireSRWLockExclusive( RTL_SRWLOCK *lock )
 540 {
 541     union { RTL_SRWLOCK *rtl; struct srw_lock *s; LONG *l; } u = { lock };
 542
 543     InterlockedIncrement16( &u.s->exclusive_waiters );
 544
 545     for (;;)
 546     {
 547         union { struct srw_lock s; LONG l; } old, new;
 548         BOOL wait;
 549
 550         do
 551         {
 552             old.s = *u.s;
 553             new.s = old.s;
 554
 555             if (!old.s.owners)
 556             {
 557                 /* Not locked exclusive or shared. We can try to grab it. */
 558                 new.s.owners = -1;
 559                 --new.s.exclusive_waiters;
 560                 wait = FALSE;
 561             }
 562             else
 563             {
 564                 wait = TRUE;
 565             }
 566         } while (InterlockedCompareExchange( u.l, new.l, old.l ) != old.l);
 567
 568         if (!wait) return;
 569         RtlWaitOnAddress( &u.s->owners, &new.s.owners, sizeof(short), NULL );
 570     }
 571 }
 572
 573 /***********************************************************************
 574  *              RtlAcquireSRWLockShared (NTDLL.@)
 575  *
 576  * NOTES
 577  *   Do not call this function recursively - it will only succeed when
 578  *   there are no threads waiting for an exclusive lock!
 579  */
 580 void WINAPI RtlAcquireSRWLockShared( RTL_SRWLOCK *lock )
 581 {
 582     union { RTL_SRWLOCK *rtl; struct srw_lock *s; LONG *l; } u = { lock };
 583
 584     for (;;)
 585     {
 586         union { struct srw_lock s; LONG l; } old, new;
 587         BOOL wait;
 588
 589         do
 590         {
 591             old.s = *u.s;
 592             new = old;
 593
 594             if (old.s.owners != -1 && !old.s.exclusive_waiters)
 595             {
 596                 /* Not locked exclusive, and no exclusive waiters.
 597                  * We can try to grab it. */
 598                 ++new.s.owners;
 599                 wait = FALSE;
 600             }
 601             else
 602             {
 603                 wait = TRUE;
 604             }
 605         } while (InterlockedCompareExchange( u.l, new.l, old.l ) != old.l);
 606
 607         if (!wait) return;
 608         RtlWaitOnAddress( u.s, &new.s, sizeof(struct srw_lock), NULL );
 609     }
 610 }
 611
 612 /***********************************************************************
 613  *              RtlReleaseSRWLockExclusive (NTDLL.@)
 614  */
 615 void WINAPI RtlReleaseSRWLockExclusive( RTL_SRWLOCK *lock )
 616 {
 617     union { RTL_SRWLOCK *rtl; struct srw_lock *s; LONG *l; } u = { lock };
 618     union { struct srw_lock s; LONG l; } old, new;
 619
 620     do
 621     {
 622         old.s = *u.s;
 623         new = old;
 624
 625         if (old.s.owners != -1) ERR("Lock %p is not owned exclusive!\n", lock);
 626
 627         new.s.owners = 0;
 628     } while (InterlockedCompareExchange( u.l, new.l, old.l ) != old.l);
 629
 630     if (new.s.exclusive_waiters)
 631         RtlWakeAddressSingle( &u.s->owners );
 632     else
 633         RtlWakeAddressAll( u.s );
 634 }
 635
 636 /***********************************************************************
 637  *              RtlReleaseSRWLockShared (NTDLL.@)
 638  */
 639 void WINAPI RtlReleaseSRWLockShared( RTL_SRWLOCK *lock )
 640 {
 641     union { RTL_SRWLOCK *rtl; struct srw_lock *s; LONG *l; } u = { lock };
 642     union { struct srw_lock s; LONG l; } old, new;
 643
 644     do
 645     {
 646         old.s = *u.s;
 647         new = old;
 648
 649         if (old.s.owners == -1) ERR("Lock %p is owned exclusive!\n", lock);
 650         else if (!old.s.owners) ERR("Lock %p is not owned shared!\n", lock);
 651
 652         --new.s.owners;
 653     } while (InterlockedCompareExchange( u.l, new.l, old.l ) != old.l);
 654
 655     if (!new.s.owners)
 656         RtlWakeAddressSingle( &u.s->owners );
 657 }
 658
 659 /***********************************************************************
 660  *              RtlTryAcquireSRWLockExclusive (NTDLL.@)
 661  *
 662  * NOTES
 663  *  Similarly to AcquireSRWLockExclusive, recursive calls are not allowed
 664  *  and will fail with a FALSE return value.
 665  */
 666 BOOLEAN WINAPI RtlTryAcquireSRWLockExclusive( RTL_SRWLOCK *lock )
 667 {
 668     union { RTL_SRWLOCK *rtl; struct srw_lock *s; LONG *l; } u = { lock };
 669     union { struct srw_lock s; LONG l; } old, new;
 670     BOOLEAN ret;
 671
 672     do
 673     {
 674         old.s = *u.s;
 675         new.s = old.s;
 676
 677         if (!old.s.owners)
 678         {
 679             /* Not locked exclusive or shared. We can try to grab it. */
 680             new.s.owners = -1;
 681             ret = TRUE;
 682         }
 683         else
 684         {
 685             ret = FALSE;
 686         }
 687     } while (InterlockedCompareExchange( u.l, new.l, old.l ) != old.l);
 688
 689     return ret;
 690 }
 691
 692 /***********************************************************************
 693  *              RtlTryAcquireSRWLockShared (NTDLL.@)
 694  */
 695 BOOLEAN WINAPI RtlTryAcquireSRWLockShared( RTL_SRWLOCK *lock )
 696 {
 697     union { RTL_SRWLOCK *rtl; struct srw_lock *s; LONG *l; } u = { lock };
 698     union { struct srw_lock s; LONG l; } old, new;
 699     BOOLEAN ret;
 700
 701     do
 702     {
 703         old.s = *u.s;
 704         new.s = old.s;
 705
 706         if (old.s.owners != -1 && !old.s.exclusive_waiters)
 707         {
 708             /* Not locked exclusive, and no exclusive waiters.
 709              * We can try to grab it. */
 710             ++new.s.owners;
 711             ret = TRUE;
 712         }
 713         else
 714         {
 715             ret = FALSE;
 716         }
 717     } while (InterlockedCompareExchange( u.l, new.l, old.l ) != old.l);
 718
 719     return ret;
 720 }
 721
 722 /***********************************************************************
 723  *           RtlInitializeConditionVariable   (NTDLL.@)
 724  *
 725  * Initializes the condition variable with NULL.
 726  *
 727  * PARAMS
 728  *  variable [O] condition variable
 729  *
 730  * RETURNS
 731  *  Nothing.
 732  */
 733 void WINAPI RtlInitializeConditionVariable( RTL_CONDITION_VARIABLE *variable )
 734 {
 735     variable->Ptr = NULL;
 736 }
 737
 738 /***********************************************************************
 739  *           RtlWakeConditionVariable   (NTDLL.@)
 740  *
 741  * Wakes up one thread waiting on the condition variable.
 742  *
 743  * PARAMS
 744  *  variable [I/O] condition variable to wake up.
 745  *
 746  * RETURNS
 747  *  Nothing.
 748  *
 749  * NOTES
 750  *  The calling thread does not have to own any lock in order to call
 751  *  this function.
 752  */
 753 void WINAPI RtlWakeConditionVariable( RTL_CONDITION_VARIABLE *variable )
 754 {
 755     InterlockedIncrement( (LONG *)&variable->Ptr );
 756     RtlWakeAddressSingle( variable );
 757 }
 758
 759 /***********************************************************************
 760  *           RtlWakeAllConditionVariable   (NTDLL.@)
 761  *
 762  * See WakeConditionVariable, wakes up all waiting threads.
 763  */
 764 void WINAPI RtlWakeAllConditionVariable( RTL_CONDITION_VARIABLE *variable )
 765 {
 766     InterlockedIncrement( (LONG *)&variable->Ptr );
 767     RtlWakeAddressAll( variable );
 768 }
 769
 770 /***********************************************************************
 771  *           RtlSleepConditionVariableCS   (NTDLL.@)
 772  *
 773  * Atomically releases the critical section and suspends the thread,
 774  * waiting for a Wake(All)ConditionVariable event. Afterwards it enters
 775  * the critical section again and returns.
 776  *
 777  * PARAMS
 778  *  variable  [I/O] condition variable
 779  *  crit      [I/O] critical section to leave temporarily
 780  *  timeout   [I]   timeout
 781  *
 782  * RETURNS
 783  *  see NtWaitForKeyedEvent for all possible return values.
 784  */
 785 NTSTATUS WINAPI RtlSleepConditionVariableCS( RTL_CONDITION_VARIABLE *variable, RTL_CRITICAL_SECTION *crit,
 786                                              const LARGE_INTEGER *timeout )
 787 {
 788     int value = *(int *)&variable->Ptr;
 789     NTSTATUS status;
 790
 791     RtlLeaveCriticalSection( crit );
 792     status = RtlWaitOnAddress( &variable->Ptr, &value, sizeof(value), timeout );
 793     RtlEnterCriticalSection( crit );
 794     return status;
 795 }
 796
 797 /***********************************************************************
 798  *           RtlSleepConditionVariableSRW   (NTDLL.@)
 799  *
 800  * Atomically releases the SRWLock and suspends the thread,
 801  * waiting for a Wake(All)ConditionVariable event. Afterwards it enters
 802  * the SRWLock again with the same access rights and returns.
 803  *
 804  * PARAMS
 805  *  variable  [I/O] condition variable
 806  *  lock      [I/O] SRWLock to leave temporarily
 807  *  timeout   [I]   timeout
 808  *  flags     [I]   type of the current lock (exclusive / shared)
 809  *
 810  * RETURNS
 811  *  see NtWaitForKeyedEvent for all possible return values.
 812  *
 813  * NOTES
 814  *  the behaviour is undefined if the thread doesn't own the lock.
 815  */
 816 NTSTATUS WINAPI RtlSleepConditionVariableSRW( RTL_CONDITION_VARIABLE *variable, RTL_SRWLOCK *lock,
 817                                               const LARGE_INTEGER *timeout, ULONG flags )
 818 {
 819     int value = *(int *)&variable->Ptr;
 820     NTSTATUS status;
 821
 822     if (flags & RTL_CONDITION_VARIABLE_LOCKMODE_SHARED)
 823         RtlReleaseSRWLockShared( lock );
 824     else
 825         RtlReleaseSRWLockExclusive( lock );
 826
 827     status = RtlWaitOnAddress( &variable->Ptr, &value, sizeof(value), timeout );
 828
 829     if (flags & RTL_CONDITION_VARIABLE_LOCKMODE_SHARED)
 830         RtlAcquireSRWLockShared( lock );
 831     else
 832         RtlAcquireSRWLockExclusive( lock );
 833     return status;
 834 }
 835
 836 /* RtlWaitOnAddress() and RtlWakeAddress*(), hereafter referred to as "Win32
 837  * futexes", offer futex-like semantics with a variable set of address sizes,
 838  * but are limited to a single process. They are also fair—the documentation
 839  * specifies this, and tests bear it out.
 840  *
 841  * On Windows they are implemented using NtAlertThreadByThreadId and
 842  * NtWaitForAlertByThreadId, which manipulate a single flag (similar to an
 843  * auto-reset event) per thread. This can be tested by attempting to wake a
 844  * thread waiting in RtlWaitOnAddress() via NtAlertThreadByThreadId.
 845  */
 846
 847 struct futex_entry
 848 {
 849     struct list entry;
 850     const void *addr;
 851     DWORD tid;
 852 };
 853
 854 struct futex_queue
 855 {
 856     struct list queue;
 857     LONG lock;
 858 };
 859
 860 static struct futex_queue futex_queues[256];
 861
 862 static struct futex_queue *get_futex_queue( const void *addr )
 863 {
 864     ULONG_PTR val = (ULONG_PTR)addr;
 865
 866     return &futex_queues[(val >> 4) % ARRAY_SIZE(futex_queues)];
 867 }
 868
 869 static void spin_lock( LONG *lock )
 870 {
 871     while (InterlockedCompareExchange( lock, -1, 0 ))
 872         YieldProcessor();
 873 }
 874
 875 static void spin_unlock( LONG *lock )
 876 {
 877     InterlockedExchange( lock, 0 );
 878 }
 879
 880 static BOOL compare_addr( const void *addr, const void *cmp, SIZE_T size )
 881 {
 882     switch (size)
 883     {
 884         case 1:
 885             return (*(const UCHAR *)addr == *(const UCHAR *)cmp);
 886         case 2:
 887             return (*(const USHORT *)addr == *(const USHORT *)cmp);
 888         case 4:
 889             return (*(const ULONG *)addr == *(const ULONG *)cmp);
 890         case 8:
 891             return (*(const ULONG64 *)addr == *(const ULONG64 *)cmp);
 892     }
 893
 894     return FALSE;
 895 }
 896
 897 /***********************************************************************
 898  *           RtlWaitOnAddress   (NTDLL.@)
 899  */
 900 NTSTATUS WINAPI RtlWaitOnAddress( const void *addr, const void *cmp, SIZE_T size,
 901                                   const LARGE_INTEGER *timeout )
 902 {
 903     struct futex_queue *queue = get_futex_queue( addr );
 904     struct futex_entry entry;
 905     NTSTATUS ret;
 906
 907     TRACE("addr %p cmp %p size %#Ix timeout %s\n", addr, cmp, size, debugstr_timeout( timeout ));
 908
 909     if (size != 1 && size != 2 && size != 4 && size != 8)
 910         return STATUS_INVALID_PARAMETER;
 911
 912     entry.addr = addr;
 913     entry.tid = GetCurrentThreadId();
 914
 915     spin_lock( &queue->lock );
 916
 917     /* Do the comparison inside of the spinlock, to reduce spurious wakeups. */
 918
 919     if (!compare_addr( addr, cmp, size ))
 920     {
 921         spin_unlock( &queue->lock );
 922         return STATUS_SUCCESS;
 923     }
 924
 925     if (!queue->queue.next)
 926         list_init( &queue->queue );
 927     list_add_tail( &queue->queue, &entry.entry );
 928
 929     spin_unlock( &queue->lock );
 930
 931     ret = NtWaitForAlertByThreadId( NULL, timeout );
 932
 933     spin_lock( &queue->lock );
 934     /* We may have already been removed by a call to RtlWakeAddressSingle(). */
 935     if (entry.addr)
 936         list_remove( &entry.entry );
 937     spin_unlock( &queue->lock );
 938
 939     TRACE("returning %#x\n", ret);
 940
 941     if (ret == STATUS_ALERTED) ret = STATUS_SUCCESS;
 942     return ret;
 943 }
 944
 945 /***********************************************************************
 946  *           RtlWakeAddressAll    (NTDLL.@)
 947  */
 948 void WINAPI RtlWakeAddressAll( const void *addr )
 949 {
 950     struct futex_queue *queue = get_futex_queue( addr );
 951     unsigned int count = 0, i;
 952     struct futex_entry *entry;
 953     DWORD tids[256];
 954
 955     TRACE("%p\n", addr);
 956
 957     if (!addr) return;
 958
 959     spin_lock( &queue->lock );
 960
 961     if (!queue->queue.next)
 962         list_init(&queue->queue);
 963
 964     LIST_FOR_EACH_ENTRY( entry, &queue->queue, struct futex_entry, entry )
 965     {
 966         if (entry->addr == addr)
 967         {
 968             /* Try to buffer wakes, so that we don't make a system call while
 969              * holding a spinlock. */
 970             if (count < ARRAY_SIZE(tids))
 971                 tids[count++] = entry->tid;
 972             else
 973                 NtAlertThreadByThreadId( (HANDLE)(DWORD_PTR)entry->tid );
 974         }
 975     }
 976
 977     spin_unlock( &queue->lock );
 978
 979     for (i = 0; i < count; ++i)
 980         NtAlertThreadByThreadId( (HANDLE)(DWORD_PTR)tids[i] );
 981 }
 982
 983 /***********************************************************************
 984  *           RtlWakeAddressSingle (NTDLL.@)
 985  */
 986 void WINAPI RtlWakeAddressSingle( const void *addr )
 987 {
 988     struct futex_queue *queue = get_futex_queue( addr );
 989     struct futex_entry *entry;
 990     DWORD tid = 0;
 991
 992     TRACE("%p\n", addr);
 993
 994     if (!addr) return;
 995
 996     spin_lock( &queue->lock );
 997
 998     if (!queue->queue.next)
 999         list_init(&queue->queue);
1000
1001     LIST_FOR_EACH_ENTRY( entry, &queue->queue, struct futex_entry, entry )
1002     {
1003         if (entry->addr == addr)
1004         {
1005             /* Try to buffer wakes, so that we don't make a system call while
1006              * holding a spinlock. */
1007             tid = entry->tid;
1008
1009             /* Remove this entry from the queue, so that a simultaneous call to
1010              * RtlWakeAddressSingle() will not also wake it—two simultaneous
1011              * calls must wake at least two waiters if they exist. */
1012             entry->addr = NULL;
1013             list_remove( &entry->entry );
1014             break;
1015         }
1016     }
1017
1018     spin_unlock( &queue->lock );
1019
1020     if (tid) NtAlertThreadByThreadId( (HANDLE)(DWORD_PTR)tid );
1021 }