reactos/lib/rtl/srw.c

   1 /*
   2  * COPYRIGHT:         See COPYING in the top level directory
   3  * PROJECT:           ReactOS system libraries
   4  * PURPOSE:           Slim Reader/Writer (SRW) Routines
   5  * PROGRAMMER:        Thomas Weidenmueller <w3seek@reactos.com>
   6  *
   7  * NOTES:             The algorithms used in this implementation
   8  *                    may be different from Vista's implementation.
   9  *                    Since applications should treat the RTL_SRWLOCK
  10  *                    structure as opaque data, it should not matter.
  11  *                    The algorithms are probably not as optimized.
  12  */
  13
  14 /* INCLUDES *****************************************************************/
  15
  16 #include <rtl.h>
  17
  18 #define NDEBUG
  19 #include <debug.h>
  20
  21 /* FIXME *********************************************************************/
  22
  23 /* FIXME: Interlocked functions that need to be made into a public header */
  24 FORCEINLINE
  25 LONG
  26 InterlockedAnd(IN OUT volatile LONG *Target,
  27                IN LONG Set)
  28 {
  29     LONG i;
  30     LONG j;
  31
  32     j = *Target;
  33     do {
  34         i = j;
  35         j = _InterlockedCompareExchange((PLONG)Target,
  36                                         i & Set,
  37                                         i);
  38
  39     } while (i != j);
  40
  41     return j;
  42 }
  43
  44 FORCEINLINE
  45 LONG
  46 InterlockedOr(IN OUT volatile LONG *Target,
  47               IN LONG Set)
  48 {
  49     LONG i;
  50     LONG j;
  51
  52     j = *Target;
  53     do {
  54         i = j;
  55         j = _InterlockedCompareExchange((PLONG)Target,
  56                                         i | Set,
  57                                         i);
  58
  59     } while (i != j);
  60
  61     return j;
  62 }
  63
  64 /* FUNCTIONS *****************************************************************/
  65
  66 #ifdef _WIN64
  67 #define InterlockedBitTestAndSetPointer(ptr,val) InterlockedBitTestAndSet64((PLONGLONG)ptr,(LONGLONG)val)
  68 #define InterlockedAddPointer(ptr,val) InterlockedAdd64((PLONGLONG)ptr,(LONGLONG)val)
  69 #define InterlockedAndPointer(ptr,val) InterlockedAnd64((PLONGLONG)ptr,(LONGLONG)val)
  70 #define InterlockedOrPointer(ptr,val) InterlockedOr64((PLONGLONG)ptr,(LONGLONG)val)
  71 #else
  72 #define InterlockedBitTestAndSetPointer(ptr,val) InterlockedBitTestAndSet((PLONG)ptr,(LONG)val)
  73 #define InterlockedAddPointer(ptr,val) InterlockedAdd((PLONG)ptr,(LONG)val)
  74 #define InterlockedAndPointer(ptr,val) InterlockedAnd((PLONG)ptr,(LONG)val)
  75 #define InterlockedOrPointer(ptr,val) InterlockedOr((PLONG)ptr,(LONG)val)
  76 #endif
  77
  78 #define RTL_SRWLOCK_OWNED_BIT   0
  79 #define RTL_SRWLOCK_CONTENDED_BIT   1
  80 #define RTL_SRWLOCK_SHARED_BIT  2
  81 #define RTL_SRWLOCK_CONTENTION_LOCK_BIT 3
  82 #define RTL_SRWLOCK_OWNED   (1 << RTL_SRWLOCK_OWNED_BIT)
  83 #define RTL_SRWLOCK_CONTENDED   (1 << RTL_SRWLOCK_CONTENDED_BIT)
  84 #define RTL_SRWLOCK_SHARED  (1 << RTL_SRWLOCK_SHARED_BIT)
  85 #define RTL_SRWLOCK_CONTENTION_LOCK (1 << RTL_SRWLOCK_CONTENTION_LOCK_BIT)
  86 #define RTL_SRWLOCK_MASK    (RTL_SRWLOCK_OWNED | RTL_SRWLOCK_CONTENDED | \
  87                              RTL_SRWLOCK_SHARED | RTL_SRWLOCK_CONTENTION_LOCK)
  88 #define RTL_SRWLOCK_BITS    4
  89
  90 #if defined(__GNUC__)
  91 /* This macro will cause the code to assert if compiled with a buggy
  92    version of GCC that doesn't align the wait blocks properly on the stack! */
  93 #define ASSERT_SRW_WAITBLOCK(ptr) \
  94     ASSERT(((ULONG_PTR)ptr & ((1 << RTL_SRWLOCK_BITS) - 1)) == 0)
  95 #else
  96 #define ASSERT_SRW_WAITBLOCK(ptr)
  97 #endif
  98
  99 typedef struct _RTLP_SRWLOCK_SHARED_WAKE
 100 {
 101     LONG Wake;
 102     volatile struct _RTLP_SRWLOCK_SHARED_WAKE *Next;
 103 } volatile RTLP_SRWLOCK_SHARED_WAKE, *PRTLP_SRWLOCK_SHARED_WAKE;
 104
 105 typedef struct _RTLP_SRWLOCK_WAITBLOCK
 106 {
 107     /* SharedCount is the number of shared acquirers. */
 108     LONG SharedCount;
 109
 110     /* Last points to the last wait block in the chain. The value
 111        is only valid when read from the first wait block. */
 112     volatile struct _RTLP_SRWLOCK_WAITBLOCK *Last;
 113
 114     /* Next points to the next wait block in the chain. */
 115     volatile struct _RTLP_SRWLOCK_WAITBLOCK *Next;
 116
 117     union
 118     {
 119         /* Wake is only valid for exclusive wait blocks */
 120         LONG Wake;
 121         /* The wake chain is only valid for shared wait blocks */
 122         struct
 123         {
 124             PRTLP_SRWLOCK_SHARED_WAKE SharedWakeChain;
 125             PRTLP_SRWLOCK_SHARED_WAKE LastSharedWake;
 126         };
 127     };
 128
 129     BOOLEAN Exclusive;
 130 } volatile RTLP_SRWLOCK_WAITBLOCK, *PRTLP_SRWLOCK_WAITBLOCK;
 131
 132
 133 static VOID
 134 NTAPI
 135 RtlpReleaseWaitBlockLockExclusive(IN OUT PRTL_SRWLOCK SRWLock,
 136                                   IN PRTLP_SRWLOCK_WAITBLOCK FirstWaitBlock)
 137 {
 138     PRTLP_SRWLOCK_WAITBLOCK Next;
 139     LONG_PTR NewValue;
 140
 141     /* NOTE: We're currently in an exclusive lock in contended mode. */
 142
 143     Next = FirstWaitBlock->Next;
 144     if (Next != NULL)
 145     {
 146         /* There's more blocks chained, we need to update the pointers
 147            in the next wait block and update the wait block pointer. */
 148         NewValue = (LONG_PTR)Next | RTL_SRWLOCK_OWNED | RTL_SRWLOCK_CONTENDED;
 149         if (!FirstWaitBlock->Exclusive)
 150         {
 151             /* The next wait block has to be an exclusive lock! */
 152             ASSERT(Next->Exclusive);
 153
 154             /* Save the shared count */
 155             Next->SharedCount = FirstWaitBlock->SharedCount;
 156
 157             NewValue |= RTL_SRWLOCK_SHARED;
 158         }
 159
 160         Next->Last = FirstWaitBlock->Last;
 161     }
 162     else
 163     {
 164         /* Convert the lock to a simple lock. */
 165         if (FirstWaitBlock->Exclusive)
 166             NewValue = RTL_SRWLOCK_OWNED;
 167         else
 168         {
 169             ASSERT(FirstWaitBlock->SharedCount > 0);
 170
 171             NewValue = ((LONG_PTR)FirstWaitBlock->SharedCount << RTL_SRWLOCK_BITS) |
 172                        RTL_SRWLOCK_SHARED | RTL_SRWLOCK_OWNED;
 173         }
 174     }
 175
 176     (void)_InterlockedExchange((PLONG)&SRWLock->Ptr, NewValue);
 177
 178     if (FirstWaitBlock->Exclusive)
 179     {
 180         (void)InterlockedOr(&FirstWaitBlock->Wake,
 181                             TRUE);
 182     }
 183     else
 184     {
 185         PRTLP_SRWLOCK_SHARED_WAKE WakeChain, Next;
 186
 187         /* If we were the first one to acquire the shared
 188            lock, we now need to wake all others... */
 189         WakeChain = FirstWaitBlock->SharedWakeChain;
 190         do
 191         {
 192             Next = WakeChain->Next;
 193
 194             (void)InterlockedOr((PLONG)&WakeChain->Wake,
 195                                 TRUE);
 196
 197             WakeChain = Next;
 198         } while (WakeChain != NULL);
 199     }
 200 }
 201
 202
 203 static VOID
 204 NTAPI
 205 RtlpReleaseWaitBlockLockLastShared(IN OUT PRTL_SRWLOCK SRWLock,
 206                                    IN PRTLP_SRWLOCK_WAITBLOCK FirstWaitBlock)
 207 {
 208     PRTLP_SRWLOCK_WAITBLOCK Next;
 209     LONG_PTR NewValue;
 210
 211     /* NOTE: We're currently in a shared lock in contended mode. */
 212
 213     /* The next acquirer to be unwaited *must* be an exclusive lock! */
 214     ASSERT(FirstWaitBlock->Exclusive);
 215
 216     Next = FirstWaitBlock->Next;
 217     if (Next != NULL)
 218     {
 219         /* There's more blocks chained, we need to update the pointers
 220            in the next wait block and update the wait block pointer. */
 221         NewValue = (LONG_PTR)Next | RTL_SRWLOCK_OWNED | RTL_SRWLOCK_CONTENDED;
 222
 223         Next->Last = FirstWaitBlock->Last;
 224     }
 225     else
 226     {
 227         /* Convert the lock to a simple exclusive lock. */
 228         NewValue = RTL_SRWLOCK_OWNED;
 229     }
 230
 231     (void)_InterlockedExchange((PLONG)&SRWLock->Ptr, NewValue);
 232
 233     (void)InterlockedOr(&FirstWaitBlock->Wake,
 234                         TRUE);
 235 }
 236
 237
 238 static VOID
 239 NTAPI
 240 RtlpReleaseWaitBlockLock(IN OUT PRTL_SRWLOCK SRWLock)
 241 {
 242     InterlockedAndPointer(&SRWLock->Ptr,
 243                           ~RTL_SRWLOCK_CONTENTION_LOCK);
 244 }
 245
 246
 247 static PRTLP_SRWLOCK_WAITBLOCK
 248 NTAPI
 249 RtlpAcquireWaitBlockLock(IN OUT PRTL_SRWLOCK SRWLock)
 250 {
 251     LONG_PTR PrevValue;
 252     PRTLP_SRWLOCK_WAITBLOCK WaitBlock;
 253
 254     while (1)
 255     {
 256         PrevValue = InterlockedOrPointer(&SRWLock->Ptr,
 257                                          RTL_SRWLOCK_CONTENTION_LOCK);
 258
 259         if (!(PrevValue & RTL_SRWLOCK_CONTENTION_LOCK))
 260             break;
 261
 262         YieldProcessor();
 263     }
 264
 265     if (!(PrevValue & RTL_SRWLOCK_CONTENDED) ||
 266         (PrevValue & ~RTL_SRWLOCK_MASK) == 0)
 267     {
 268         /* Too bad, looks like the wait block was removed in the
 269            meanwhile, unlock again */
 270         RtlpReleaseWaitBlockLock(SRWLock);
 271         return NULL;
 272     }
 273
 274     WaitBlock = (PRTLP_SRWLOCK_WAITBLOCK)(PrevValue & ~RTL_SRWLOCK_MASK);
 275
 276     ASSERT_SRW_WAITBLOCK(WaitBlock);
 277     return WaitBlock;
 278 }
 279
 280
 281 static VOID
 282 NTAPI
 283 RtlpAcquireSRWLockExclusiveWait(IN OUT PRTL_SRWLOCK SRWLock,
 284                                 IN PRTLP_SRWLOCK_WAITBLOCK WaitBlock)
 285 {
 286     LONG_PTR CurrentValue;
 287
 288     while (1)
 289     {
 290         CurrentValue = *(volatile LONG_PTR *)&SRWLock->Ptr;
 291         if (!(CurrentValue & RTL_SRWLOCK_SHARED))
 292         {
 293             if (CurrentValue & RTL_SRWLOCK_CONTENDED)
 294             {
 295                 if (WaitBlock->Wake != 0)
 296                 {
 297                     /* Our wait block became the first one
 298                        in the chain, we own the lock now! */
 299                     break;
 300                 }
 301             }
 302             else
 303             {
 304                 /* The last wait block was removed and/or we're
 305                    finally a simple exclusive lock. This means we
 306                    don't need to wait anymore, we acquired the lock! */
 307                 break;
 308             }
 309         }
 310
 311         YieldProcessor();
 312     }
 313 }
 314
 315
 316 static VOID
 317 NTAPI
 318 RtlpAcquireSRWLockSharedWait(IN OUT PRTL_SRWLOCK SRWLock,
 319                              IN OUT PRTLP_SRWLOCK_WAITBLOCK FirstWait  OPTIONAL,
 320                              IN OUT PRTLP_SRWLOCK_SHARED_WAKE WakeChain)
 321 {
 322     if (FirstWait != NULL)
 323     {
 324         while (WakeChain->Wake == 0)
 325         {
 326             YieldProcessor();
 327         }
 328     }
 329     else
 330     {
 331         LONG_PTR CurrentValue;
 332
 333         while (1)
 334         {
 335             CurrentValue = *(volatile LONG_PTR *)&SRWLock->Ptr;
 336             if (CurrentValue & RTL_SRWLOCK_SHARED)
 337             {
 338                 /* The RTL_SRWLOCK_OWNED bit always needs to be set when
 339                    RTL_SRWLOCK_SHARED is set! */
 340                 ASSERT(CurrentValue & RTL_SRWLOCK_OWNED);
 341
 342                 if (CurrentValue & RTL_SRWLOCK_CONTENDED)
 343                 {
 344                     if (WakeChain->Wake != 0)
 345                     {
 346                         /* Our wait block became the first one
 347                            in the chain, we own the lock now! */
 348                         break;
 349                     }
 350                 }
 351                 else
 352                 {
 353                     /* The last wait block was removed and/or we're
 354                        finally a simple shared lock. This means we
 355                        don't need to wait anymore, we acquired the lock! */
 356                     break;
 357                 }
 358             }
 359
 360             YieldProcessor();
 361         }
 362     }
 363 }
 364
 365
 366 VOID
 367 NTAPI
 368 RtlInitializeSRWLock(OUT PRTL_SRWLOCK SRWLock)
 369 {
 370     SRWLock->Ptr = NULL;
 371 }
 372
 373
 374 VOID
 375 NTAPI
 376 RtlAcquireSRWLockShared(IN OUT PRTL_SRWLOCK SRWLock)
 377 {
 378     __ALIGNED(16) RTLP_SRWLOCK_WAITBLOCK StackWaitBlock;
 379     RTLP_SRWLOCK_SHARED_WAKE SharedWake;
 380     LONG_PTR CurrentValue, NewValue;
 381     PRTLP_SRWLOCK_WAITBLOCK First, Shared, FirstWait;
 382
 383     while (1)
 384     {
 385         CurrentValue = *(volatile LONG_PTR *)&SRWLock->Ptr;
 386
 387         if (CurrentValue & RTL_SRWLOCK_SHARED)
 388         {
 389             /* NOTE: It is possible that the RTL_SRWLOCK_OWNED bit is set! */
 390
 391             if (CurrentValue & RTL_SRWLOCK_CONTENDED)
 392             {
 393                 /* There's other waiters already, lock the wait blocks and
 394                    increment the shared count */
 395                 First = RtlpAcquireWaitBlockLock(SRWLock);
 396                 if (First != NULL)
 397                 {
 398                     FirstWait = NULL;
 399
 400                     if (First->Exclusive)
 401                     {
 402                         /* We need to setup a new wait block! Although
 403                            we're currently in a shared lock and we're acquiring
 404                            a shared lock, there are exclusive locks queued. We need
 405                            to wait until those are released. */
 406                         Shared = First->Last;
 407
 408                         if (Shared->Exclusive)
 409                         {
 410                             StackWaitBlock.Exclusive = FALSE;
 411                             StackWaitBlock.SharedCount = 1;
 412                             StackWaitBlock.Next = NULL;
 413                             StackWaitBlock.Last = &StackWaitBlock;
 414                             StackWaitBlock.SharedWakeChain = &SharedWake;
 415
 416                             Shared->Next = &StackWaitBlock;
 417                             First->Last = &StackWaitBlock;
 418
 419                             Shared = &StackWaitBlock;
 420                             FirstWait = &StackWaitBlock;
 421                         }
 422                         else
 423                         {
 424                             Shared->LastSharedWake->Next = &SharedWake;
 425                             Shared->SharedCount++;
 426                         }
 427                     }
 428                     else
 429                     {
 430                         Shared = First;
 431                         Shared->LastSharedWake->Next = &SharedWake;
 432                         Shared->SharedCount++;
 433                     }
 434
 435                     SharedWake.Next = NULL;
 436                     SharedWake.Wake = 0;
 437
 438                     Shared->LastSharedWake = &SharedWake;
 439
 440                     ASSERT_SRW_WAITBLOCK(Shared);
 441
 442                     RtlpReleaseWaitBlockLock(SRWLock);
 443
 444                     RtlpAcquireSRWLockSharedWait(SRWLock,
 445                                                  FirstWait,
 446                                                  &SharedWake);
 447
 448                     /* Successfully incremented the shared count, we acquired the lock */
 449                     break;
 450                 }
 451             }
 452             else
 453             {
 454                 /* This is a fastest path, just increment the number of
 455                    current shared locks */
 456
 457                 /* Since the RTL_SRWLOCK_SHARED bit is set, the RTL_SRWLOCK_OWNED bit also has
 458                    to be set! */
 459
 460                 ASSERT(CurrentValue & RTL_SRWLOCK_OWNED);
 461
 462                 NewValue = (CurrentValue >> RTL_SRWLOCK_BITS) + 1;
 463                 NewValue = (NewValue << RTL_SRWLOCK_BITS) | (CurrentValue & RTL_SRWLOCK_MASK);
 464
 465                 if (_InterlockedCompareExchange((PLONG)&SRWLock->Ptr,
 466                                                 NewValue,
 467                                                 CurrentValue) == CurrentValue)
 468                 {
 469                     /* Successfully incremented the shared count, we acquired the lock */
 470                     break;
 471                 }
 472             }
 473         }
 474         else
 475         {
 476             if (CurrentValue & RTL_SRWLOCK_OWNED)
 477             {
 478                 /* The resource is currently acquired exclusively */
 479                 if (CurrentValue & RTL_SRWLOCK_CONTENDED)
 480                 {
 481                     SharedWake.Next = NULL;
 482                     SharedWake.Wake = 0;
 483
 484                     /* There's other waiters already, lock the wait blocks and
 485                        increment the shared count. If the last block in the chain
 486                        is an exclusive lock, add another block. */
 487
 488                     StackWaitBlock.Exclusive = FALSE;
 489                     StackWaitBlock.SharedCount = 0;
 490                     StackWaitBlock.Next = NULL;
 491                     StackWaitBlock.Last = &StackWaitBlock;
 492                     StackWaitBlock.SharedWakeChain = &SharedWake;
 493
 494                     First = RtlpAcquireWaitBlockLock(SRWLock);
 495                     if (First != NULL)
 496                     {
 497                         Shared = First->Last;
 498                         if (Shared->Exclusive)
 499                         {
 500                             Shared->Next = &StackWaitBlock;
 501                             First->Last = &StackWaitBlock;
 502
 503                             Shared = &StackWaitBlock;
 504                             FirstWait = &StackWaitBlock;
 505                         }
 506                         else
 507                         {
 508                             FirstWait = NULL;
 509                             Shared->LastSharedWake->Next = &SharedWake;
 510                         }
 511
 512                         ASSERT_SRW_WAITBLOCK(Shared);
 513
 514                         Shared->SharedCount++;
 515                         Shared->LastSharedWake = &SharedWake;
 516
 517                         RtlpReleaseWaitBlockLock(SRWLock);
 518
 519                         RtlpAcquireSRWLockSharedWait(SRWLock,
 520                                                      FirstWait,
 521                                                      &SharedWake);
 522
 523                         /* Successfully incremented the shared count, we acquired the lock */
 524                         break;
 525                     }
 526                 }
 527                 else
 528                 {
 529                     SharedWake.Next = NULL;
 530                     SharedWake.Wake = 0;
 531
 532                     /* We need to setup the first wait block. Currently an exclusive lock is
 533                        held, change the lock to contended mode. */
 534                     StackWaitBlock.Exclusive = FALSE;
 535                     StackWaitBlock.SharedCount = 1;
 536                     StackWaitBlock.Next = NULL;
 537                     StackWaitBlock.Last = &StackWaitBlock;
 538                     StackWaitBlock.SharedWakeChain = &SharedWake;
 539                     StackWaitBlock.LastSharedWake = &SharedWake;
 540
 541                     ASSERT_SRW_WAITBLOCK(&StackWaitBlock);
 542
 543                     NewValue = (ULONG_PTR)&StackWaitBlock | RTL_SRWLOCK_OWNED | RTL_SRWLOCK_CONTENDED;
 544                     if (_InterlockedCompareExchange((PLONG)&SRWLock->Ptr,
 545                                                     NewValue,
 546                                                     CurrentValue) == CurrentValue)
 547                     {
 548                         RtlpAcquireSRWLockSharedWait(SRWLock,
 549                                                      &StackWaitBlock,
 550                                                      &SharedWake);
 551
 552                         /* Successfully set the shared count, we acquired the lock */
 553                         break;
 554                     }
 555                 }
 556             }
 557             else
 558             {
 559                 /* This is a fast path, we can simply try to set the shared count to 1 */
 560                 NewValue = (1 << RTL_SRWLOCK_BITS) | RTL_SRWLOCK_SHARED | RTL_SRWLOCK_OWNED;
 561
 562                 /* The RTL_SRWLOCK_CONTENDED bit should never be set if neither the
 563                    RTL_SRWLOCK_SHARED nor the RTL_SRWLOCK_OWNED bit is set */
 564                 ASSERT(!(CurrentValue & RTL_SRWLOCK_CONTENDED));
 565
 566                 if (_InterlockedCompareExchange((PLONG)&SRWLock->Ptr,
 567                                                 NewValue,
 568                                                 CurrentValue) == CurrentValue)
 569                 {
 570                     /* Successfully set the shared count, we acquired the lock */
 571                     break;
 572                 }
 573             }
 574         }
 575
 576         YieldProcessor();
 577     }
 578 }
 579
 580
 581 VOID
 582 NTAPI
 583 RtlReleaseSRWLockShared(IN OUT PRTL_SRWLOCK SRWLock)
 584 {
 585     LONG_PTR CurrentValue, NewValue;
 586     PRTLP_SRWLOCK_WAITBLOCK WaitBlock;
 587     BOOLEAN LastShared;
 588
 589     while (1)
 590     {
 591         CurrentValue = *(volatile LONG_PTR *)&SRWLock->Ptr;
 592
 593         if (CurrentValue & RTL_SRWLOCK_SHARED)
 594         {
 595             if (CurrentValue & RTL_SRWLOCK_CONTENDED)
 596             {
 597                 /* There's a wait block, we need to wake a pending
 598                    exclusive acquirer if this is the last shared release */
 599                 WaitBlock = RtlpAcquireWaitBlockLock(SRWLock);
 600                 if (WaitBlock != NULL)
 601                 {
 602                     LastShared = (--WaitBlock->SharedCount == 0);
 603
 604                     if (LastShared)
 605                         RtlpReleaseWaitBlockLockLastShared(SRWLock,
 606                                                            WaitBlock);
 607                     else
 608                         RtlpReleaseWaitBlockLock(SRWLock);
 609
 610                     /* We released the lock */
 611                     break;
 612                 }
 613             }
 614             else
 615             {
 616                 /* This is a fast path, we can simply decrement the shared
 617                    count and store the pointer */
 618                 NewValue = CurrentValue >> RTL_SRWLOCK_BITS;
 619
 620                 if (--NewValue != 0)
 621                 {
 622                     NewValue = (NewValue << RTL_SRWLOCK_BITS) | RTL_SRWLOCK_SHARED | RTL_SRWLOCK_OWNED;
 623                 }
 624
 625                 if (_InterlockedCompareExchange((PLONG)&SRWLock->Ptr,
 626                                                 NewValue,
 627                                                 CurrentValue) == CurrentValue)
 628                 {
 629                     /* Successfully released the lock */
 630                     break;
 631                 }
 632             }
 633         }
 634         else
 635         {
 636             /* The RTL_SRWLOCK_SHARED bit has to be present now,
 637                even in the contended case! */
 638             RtlRaiseStatus(STATUS_RESOURCE_NOT_OWNED);
 639         }
 640
 641         YieldProcessor();
 642     }
 643 }
 644
 645
 646 VOID
 647 NTAPI
 648 RtlAcquireSRWLockExclusive(IN OUT PRTL_SRWLOCK SRWLock)
 649 {
 650     __ALIGNED(16) RTLP_SRWLOCK_WAITBLOCK StackWaitBlock;
 651     PRTLP_SRWLOCK_WAITBLOCK First, Last;
 652
 653     if (InterlockedBitTestAndSetPointer(&SRWLock->Ptr,
 654                                         RTL_SRWLOCK_OWNED_BIT))
 655     {
 656         LONG_PTR CurrentValue, NewValue;
 657
 658         while (1)
 659         {
 660             CurrentValue = *(volatile LONG_PTR *)&SRWLock->Ptr;
 661
 662             if (CurrentValue & RTL_SRWLOCK_SHARED)
 663             {
 664                 /* A shared lock is being held right now. We need to add a wait block! */
 665
 666                 if (CurrentValue & RTL_SRWLOCK_CONTENDED)
 667                 {
 668                     goto AddWaitBlock;
 669                 }
 670                 else
 671                 {
 672                     /* There are no wait blocks so far, we need to add ourselves as the first
 673                        wait block. We need to keep the shared count! */
 674                     StackWaitBlock.Exclusive = TRUE;
 675                     StackWaitBlock.SharedCount = CurrentValue >> RTL_SRWLOCK_BITS;
 676                     StackWaitBlock.Next = NULL;
 677                     StackWaitBlock.Last = &StackWaitBlock;
 678                     StackWaitBlock.Wake = 0;
 679
 680                     ASSERT_SRW_WAITBLOCK(&StackWaitBlock);
 681
 682                     NewValue = (ULONG_PTR)&StackWaitBlock | RTL_SRWLOCK_SHARED | RTL_SRWLOCK_CONTENDED | RTL_SRWLOCK_OWNED;
 683
 684                     if (_InterlockedCompareExchange((PLONG)&SRWLock->Ptr,
 685                                                     NewValue,
 686                                                     CurrentValue) == CurrentValue)
 687                     {
 688                         RtlpAcquireSRWLockExclusiveWait(SRWLock,
 689                                                         &StackWaitBlock);
 690
 691                         /* Successfully acquired the exclusive lock */
 692                         break;
 693                     }
 694                 }
 695             }
 696             else
 697             {
 698                 if (CurrentValue & RTL_SRWLOCK_OWNED)
 699                 {
 700                     /* An exclusive lock is being held right now. We need to add a wait block! */
 701
 702                     if (CurrentValue & RTL_SRWLOCK_CONTENDED)
 703                     {
 704 AddWaitBlock:
 705                         StackWaitBlock.Exclusive = TRUE;
 706                         StackWaitBlock.SharedCount = 0;
 707                         StackWaitBlock.Next = NULL;
 708                         StackWaitBlock.Last = &StackWaitBlock;
 709                         StackWaitBlock.Wake = 0;
 710
 711                         ASSERT_SRW_WAITBLOCK(&StackWaitBlock);
 712
 713                         First = RtlpAcquireWaitBlockLock(SRWLock);
 714                         if (First != NULL)
 715                         {
 716                             Last = First->Last;
 717                             Last->Next = &StackWaitBlock;
 718                             First->Last = &StackWaitBlock;
 719
 720                             RtlpReleaseWaitBlockLock(SRWLock);
 721
 722                             RtlpAcquireSRWLockExclusiveWait(SRWLock,
 723                                                             &StackWaitBlock);
 724
 725                             /* Successfully acquired the exclusive lock */
 726                             break;
 727                         }
 728                     }
 729                     else
 730                     {
 731                         /* There are no wait blocks so far, we need to add ourselves as the first
 732                            wait block. We need to keep the shared count! */
 733                         StackWaitBlock.Exclusive = TRUE;
 734                         StackWaitBlock.SharedCount = 0;
 735                         StackWaitBlock.Next = NULL;
 736                         StackWaitBlock.Last = &StackWaitBlock;
 737                         StackWaitBlock.Wake = 0;
 738
 739                         ASSERT_SRW_WAITBLOCK(&StackWaitBlock);
 740
 741                         NewValue = (ULONG_PTR)&StackWaitBlock | RTL_SRWLOCK_OWNED | RTL_SRWLOCK_CONTENDED;
 742                         if (_InterlockedCompareExchange((PLONG)&SRWLock->Ptr,
 743                                                         NewValue,
 744                                                         CurrentValue) == CurrentValue)
 745                         {
 746                             RtlpAcquireSRWLockExclusiveWait(SRWLock,
 747                                                             &StackWaitBlock);
 748
 749                             /* Successfully acquired the exclusive lock */
 750                             break;
 751                         }
 752                     }
 753                 }
 754                 else
 755                 {
 756                     if (!InterlockedBitTestAndSetPointer(&SRWLock->Ptr,
 757                                                          RTL_SRWLOCK_OWNED_BIT))
 758                     {
 759                         /* We managed to get hold of a simple exclusive lock! */
 760                         break;
 761                     }
 762                 }
 763             }
 764
 765             YieldProcessor();
 766         }
 767     }
 768 }
 769
 770
 771 VOID
 772 NTAPI
 773 RtlReleaseSRWLockExclusive(IN OUT PRTL_SRWLOCK SRWLock)
 774 {
 775     LONG_PTR CurrentValue, NewValue;
 776     PRTLP_SRWLOCK_WAITBLOCK WaitBlock;
 777
 778     while (1)
 779     {
 780         CurrentValue = *(volatile LONG_PTR *)&SRWLock->Ptr;
 781
 782         if (!(CurrentValue & RTL_SRWLOCK_OWNED))
 783         {
 784             RtlRaiseStatus(STATUS_RESOURCE_NOT_OWNED);
 785         }
 786
 787         if (!(CurrentValue & RTL_SRWLOCK_SHARED))
 788         {
 789             if (CurrentValue & RTL_SRWLOCK_CONTENDED)
 790             {
 791                 /* There's a wait block, we need to wake the next pending
 792                    acquirer (exclusive or shared) */
 793                 WaitBlock = RtlpAcquireWaitBlockLock(SRWLock);
 794                 if (WaitBlock != NULL)
 795                 {
 796                     RtlpReleaseWaitBlockLockExclusive(SRWLock,
 797                                                       WaitBlock);
 798
 799                     /* We released the lock */
 800                     break;
 801                 }
 802             }
 803             else
 804             {
 805                 /* This is a fast path, we can simply clear the RTL_SRWLOCK_OWNED
 806                    bit. All other bits should be 0 now because this is a simple
 807                    exclusive lock and no one is waiting. */
 808
 809                 ASSERT(!(CurrentValue & ~RTL_SRWLOCK_OWNED));
 810
 811                 NewValue = 0;
 812                 if (_InterlockedCompareExchange((PLONG)&SRWLock->Ptr,
 813                                                 NewValue,
 814                                                 CurrentValue) == CurrentValue)
 815                 {
 816                     /* We released the lock */
 817                     break;
 818                 }
 819             }
 820         }
 821         else
 822         {
 823             /* The RTL_SRWLOCK_SHARED bit must not be present now,
 824                not even in the contended case! */
 825             RtlRaiseStatus(STATUS_RESOURCE_NOT_OWNED);
 826         }
 827
 828         YieldProcessor();
 829     }
 830 }