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>
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.
14 /* INCLUDES *****************************************************************/
21 /* FUNCTIONS *****************************************************************/
24 #define InterlockedBitTestAndSetPointer(ptr,val) InterlockedBitTestAndSet64((PLONGLONG)ptr,(LONGLONG)val)
25 #define InterlockedAddPointer(ptr,val) InterlockedAdd64((PLONGLONG)ptr,(LONGLONG)val)
26 #define InterlockedAndPointer(ptr,val) InterlockedAnd64((PLONGLONG)ptr,(LONGLONG)val)
27 #define InterlockedOrPointer(ptr,val) InterlockedOr64((PLONGLONG)ptr,(LONGLONG)val)
29 #define InterlockedBitTestAndSetPointer(ptr,val) InterlockedBitTestAndSet((PLONG)ptr,(LONG)val)
30 #define InterlockedAddPointer(ptr,val) InterlockedAdd((PLONG)ptr,(LONG)val)
31 #define InterlockedAndPointer(ptr,val) InterlockedAnd((PLONG)ptr,(LONG)val)
32 #define InterlockedOrPointer(ptr,val) InterlockedOr((PLONG)ptr,(LONG)val)
35 #define RTL_SRWLOCK_OWNED_BIT 0
36 #define RTL_SRWLOCK_CONTENDED_BIT 1
37 #define RTL_SRWLOCK_SHARED_BIT 2
38 #define RTL_SRWLOCK_CONTENTION_LOCK_BIT 3
39 #define RTL_SRWLOCK_OWNED (1 << RTL_SRWLOCK_OWNED_BIT)
40 #define RTL_SRWLOCK_CONTENDED (1 << RTL_SRWLOCK_CONTENDED_BIT)
41 #define RTL_SRWLOCK_SHARED (1 << RTL_SRWLOCK_SHARED_BIT)
42 #define RTL_SRWLOCK_CONTENTION_LOCK (1 << RTL_SRWLOCK_CONTENTION_LOCK_BIT)
43 #define RTL_SRWLOCK_MASK (RTL_SRWLOCK_OWNED | RTL_SRWLOCK_CONTENDED | \
44 RTL_SRWLOCK_SHARED | RTL_SRWLOCK_CONTENTION_LOCK)
45 #define RTL_SRWLOCK_BITS 4
47 #if (__GNUC__ * 10000 + __GNUC_MINOR__ * 100 + __GNUC_PATCHLEVEL__ < 40300) || \
48 (__GNUC__ * 10000 + __GNUC_MINOR__ * 100 + __GNUC_PATCHLEVEL__ == 40303)
49 /* This macro will cause the code to assert if compiled with a buggy
50 version of GCC that doesn't align the wait blocks properly on the stack! */
51 #define ASSERT_SRW_WAITBLOCK(ptr) \
52 ASSERT(((ULONG_PTR)ptr & ((1 << RTL_SRWLOCK_BITS) - 1)) == 0)
54 #define ASSERT_SRW_WAITBLOCK(ptr) ((void)0)
57 typedef struct _RTLP_SRWLOCK_SHARED_WAKE
60 volatile struct _RTLP_SRWLOCK_SHARED_WAKE
*Next
;
61 } volatile RTLP_SRWLOCK_SHARED_WAKE
, *PRTLP_SRWLOCK_SHARED_WAKE
;
63 typedef struct _RTLP_SRWLOCK_WAITBLOCK
65 /* SharedCount is the number of shared acquirers. */
68 /* Last points to the last wait block in the chain. The value
69 is only valid when read from the first wait block. */
70 volatile struct _RTLP_SRWLOCK_WAITBLOCK
*Last
;
72 /* Next points to the next wait block in the chain. */
73 volatile struct _RTLP_SRWLOCK_WAITBLOCK
*Next
;
77 /* Wake is only valid for exclusive wait blocks */
79 /* The wake chain is only valid for shared wait blocks */
82 PRTLP_SRWLOCK_SHARED_WAKE SharedWakeChain
;
83 PRTLP_SRWLOCK_SHARED_WAKE LastSharedWake
;
88 } volatile RTLP_SRWLOCK_WAITBLOCK
, *PRTLP_SRWLOCK_WAITBLOCK
;
93 RtlpReleaseWaitBlockLockExclusive(IN OUT PRTL_SRWLOCK SRWLock
,
94 IN PRTLP_SRWLOCK_WAITBLOCK FirstWaitBlock
)
96 PRTLP_SRWLOCK_WAITBLOCK Next
;
99 /* NOTE: We're currently in an exclusive lock in contended mode. */
101 Next
= FirstWaitBlock
->Next
;
104 /* There's more blocks chained, we need to update the pointers
105 in the next wait block and update the wait block pointer. */
106 NewValue
= (LONG_PTR
)Next
| RTL_SRWLOCK_OWNED
| RTL_SRWLOCK_CONTENDED
;
107 if (!FirstWaitBlock
->Exclusive
)
109 /* The next wait block has to be an exclusive lock! */
110 ASSERT(Next
->Exclusive
);
112 /* Save the shared count */
113 Next
->SharedCount
= FirstWaitBlock
->SharedCount
;
115 NewValue
|= RTL_SRWLOCK_SHARED
;
118 Next
->Last
= FirstWaitBlock
->Last
;
122 /* Convert the lock to a simple lock. */
123 if (FirstWaitBlock
->Exclusive
)
124 NewValue
= RTL_SRWLOCK_OWNED
;
127 ASSERT(FirstWaitBlock
->SharedCount
> 0);
129 NewValue
= ((LONG_PTR
)FirstWaitBlock
->SharedCount
<< RTL_SRWLOCK_BITS
) |
130 RTL_SRWLOCK_SHARED
| RTL_SRWLOCK_OWNED
;
134 (void)_InterlockedExchange((PLONG
)&SRWLock
->Ptr
, NewValue
);
136 if (FirstWaitBlock
->Exclusive
)
138 (void)InterlockedOr(&FirstWaitBlock
->Wake
,
143 PRTLP_SRWLOCK_SHARED_WAKE WakeChain
, Next
;
145 /* If we were the first one to acquire the shared
146 lock, we now need to wake all others... */
147 WakeChain
= FirstWaitBlock
->SharedWakeChain
;
150 Next
= WakeChain
->Next
;
152 (void)InterlockedOr((PLONG
)&WakeChain
->Wake
,
156 } while (WakeChain
!= NULL
);
163 RtlpReleaseWaitBlockLockLastShared(IN OUT PRTL_SRWLOCK SRWLock
,
164 IN PRTLP_SRWLOCK_WAITBLOCK FirstWaitBlock
)
166 PRTLP_SRWLOCK_WAITBLOCK Next
;
169 /* NOTE: We're currently in a shared lock in contended mode. */
171 /* The next acquirer to be unwaited *must* be an exclusive lock! */
172 ASSERT(FirstWaitBlock
->Exclusive
);
174 Next
= FirstWaitBlock
->Next
;
177 /* There's more blocks chained, we need to update the pointers
178 in the next wait block and update the wait block pointer. */
179 NewValue
= (LONG_PTR
)Next
| RTL_SRWLOCK_OWNED
| RTL_SRWLOCK_CONTENDED
;
181 Next
->Last
= FirstWaitBlock
->Last
;
185 /* Convert the lock to a simple exclusive lock. */
186 NewValue
= RTL_SRWLOCK_OWNED
;
189 (void)_InterlockedExchange((PLONG
)&SRWLock
->Ptr
, NewValue
);
191 (void)InterlockedOr(&FirstWaitBlock
->Wake
,
198 RtlpReleaseWaitBlockLock(IN OUT PRTL_SRWLOCK SRWLock
)
200 InterlockedAndPointer(&SRWLock
->Ptr
,
201 ~RTL_SRWLOCK_CONTENTION_LOCK
);
205 static PRTLP_SRWLOCK_WAITBLOCK
207 RtlpAcquireWaitBlockLock(IN OUT PRTL_SRWLOCK SRWLock
)
210 PRTLP_SRWLOCK_WAITBLOCK WaitBlock
;
214 PrevValue
= InterlockedOrPointer(&SRWLock
->Ptr
,
215 RTL_SRWLOCK_CONTENTION_LOCK
);
217 if (!(PrevValue
& RTL_SRWLOCK_CONTENTION_LOCK
))
223 if (!(PrevValue
& RTL_SRWLOCK_CONTENDED
) ||
224 (PrevValue
& ~RTL_SRWLOCK_MASK
) == 0)
226 /* Too bad, looks like the wait block was removed in the
227 meanwhile, unlock again */
228 RtlpReleaseWaitBlockLock(SRWLock
);
232 WaitBlock
= (PRTLP_SRWLOCK_WAITBLOCK
)(PrevValue
& ~RTL_SRWLOCK_MASK
);
234 ASSERT_SRW_WAITBLOCK(WaitBlock
);
241 RtlpAcquireSRWLockExclusiveWait(IN OUT PRTL_SRWLOCK SRWLock
,
242 IN PRTLP_SRWLOCK_WAITBLOCK WaitBlock
)
244 LONG_PTR CurrentValue
;
248 CurrentValue
= *(volatile LONG_PTR
*)&SRWLock
->Ptr
;
249 if (!(CurrentValue
& RTL_SRWLOCK_SHARED
))
251 if (CurrentValue
& RTL_SRWLOCK_CONTENDED
)
253 if (WaitBlock
->Wake
!= 0)
255 /* Our wait block became the first one
256 in the chain, we own the lock now! */
262 /* The last wait block was removed and/or we're
263 finally a simple exclusive lock. This means we
264 don't need to wait anymore, we acquired the lock! */
276 RtlpAcquireSRWLockSharedWait(IN OUT PRTL_SRWLOCK SRWLock
,
277 IN OUT PRTLP_SRWLOCK_WAITBLOCK FirstWait OPTIONAL
,
278 IN OUT PRTLP_SRWLOCK_SHARED_WAKE WakeChain
)
280 if (FirstWait
!= NULL
)
282 while (WakeChain
->Wake
== 0)
289 LONG_PTR CurrentValue
;
293 CurrentValue
= *(volatile LONG_PTR
*)&SRWLock
->Ptr
;
294 if (CurrentValue
& RTL_SRWLOCK_SHARED
)
296 /* The RTL_SRWLOCK_OWNED bit always needs to be set when
297 RTL_SRWLOCK_SHARED is set! */
298 ASSERT(CurrentValue
& RTL_SRWLOCK_OWNED
);
300 if (CurrentValue
& RTL_SRWLOCK_CONTENDED
)
302 if (WakeChain
->Wake
!= 0)
304 /* Our wait block became the first one
305 in the chain, we own the lock now! */
311 /* The last wait block was removed and/or we're
312 finally a simple shared lock. This means we
313 don't need to wait anymore, we acquired the lock! */
326 RtlInitializeSRWLock(OUT PRTL_SRWLOCK SRWLock
)
334 RtlAcquireSRWLockShared(IN OUT PRTL_SRWLOCK SRWLock
)
336 __ALIGNED(16) RTLP_SRWLOCK_WAITBLOCK StackWaitBlock
;
337 RTLP_SRWLOCK_SHARED_WAKE SharedWake
;
338 LONG_PTR CurrentValue
, NewValue
;
339 PRTLP_SRWLOCK_WAITBLOCK First
, Shared
, FirstWait
;
343 CurrentValue
= *(volatile LONG_PTR
*)&SRWLock
->Ptr
;
345 if (CurrentValue
& RTL_SRWLOCK_SHARED
)
347 /* NOTE: It is possible that the RTL_SRWLOCK_OWNED bit is set! */
349 if (CurrentValue
& RTL_SRWLOCK_CONTENDED
)
351 /* There's other waiters already, lock the wait blocks and
352 increment the shared count */
353 First
= RtlpAcquireWaitBlockLock(SRWLock
);
358 if (First
->Exclusive
)
360 /* We need to setup a new wait block! Although
361 we're currently in a shared lock and we're acquiring
362 a shared lock, there are exclusive locks queued. We need
363 to wait until those are released. */
364 Shared
= First
->Last
;
366 if (Shared
->Exclusive
)
368 StackWaitBlock
.Exclusive
= FALSE
;
369 StackWaitBlock
.SharedCount
= 1;
370 StackWaitBlock
.Next
= NULL
;
371 StackWaitBlock
.Last
= &StackWaitBlock
;
372 StackWaitBlock
.SharedWakeChain
= &SharedWake
;
374 Shared
->Next
= &StackWaitBlock
;
375 First
->Last
= &StackWaitBlock
;
377 Shared
= &StackWaitBlock
;
378 FirstWait
= &StackWaitBlock
;
382 Shared
->LastSharedWake
->Next
= &SharedWake
;
383 Shared
->SharedCount
++;
389 Shared
->LastSharedWake
->Next
= &SharedWake
;
390 Shared
->SharedCount
++;
393 SharedWake
.Next
= NULL
;
396 Shared
->LastSharedWake
= &SharedWake
;
398 ASSERT_SRW_WAITBLOCK(Shared
);
400 RtlpReleaseWaitBlockLock(SRWLock
);
402 RtlpAcquireSRWLockSharedWait(SRWLock
,
406 /* Successfully incremented the shared count, we acquired the lock */
412 /* This is a fastest path, just increment the number of
413 current shared locks */
415 /* Since the RTL_SRWLOCK_SHARED bit is set, the RTL_SRWLOCK_OWNED bit also has
418 ASSERT(CurrentValue
& RTL_SRWLOCK_OWNED
);
420 NewValue
= (CurrentValue
>> RTL_SRWLOCK_BITS
) + 1;
421 NewValue
= (NewValue
<< RTL_SRWLOCK_BITS
) | (CurrentValue
& RTL_SRWLOCK_MASK
);
423 if (_InterlockedCompareExchange((PLONG
)&SRWLock
->Ptr
,
425 CurrentValue
) == CurrentValue
)
427 /* Successfully incremented the shared count, we acquired the lock */
434 if (CurrentValue
& RTL_SRWLOCK_OWNED
)
436 /* The resource is currently acquired exclusively */
437 if (CurrentValue
& RTL_SRWLOCK_CONTENDED
)
439 SharedWake
.Next
= NULL
;
442 /* There's other waiters already, lock the wait blocks and
443 increment the shared count. If the last block in the chain
444 is an exclusive lock, add another block. */
446 StackWaitBlock
.Exclusive
= FALSE
;
447 StackWaitBlock
.SharedCount
= 0;
448 StackWaitBlock
.Next
= NULL
;
449 StackWaitBlock
.Last
= &StackWaitBlock
;
450 StackWaitBlock
.SharedWakeChain
= &SharedWake
;
452 First
= RtlpAcquireWaitBlockLock(SRWLock
);
455 Shared
= First
->Last
;
456 if (Shared
->Exclusive
)
458 Shared
->Next
= &StackWaitBlock
;
459 First
->Last
= &StackWaitBlock
;
461 Shared
= &StackWaitBlock
;
462 FirstWait
= &StackWaitBlock
;
467 Shared
->LastSharedWake
->Next
= &SharedWake
;
470 ASSERT_SRW_WAITBLOCK(Shared
);
472 Shared
->SharedCount
++;
473 Shared
->LastSharedWake
= &SharedWake
;
475 RtlpReleaseWaitBlockLock(SRWLock
);
477 RtlpAcquireSRWLockSharedWait(SRWLock
,
481 /* Successfully incremented the shared count, we acquired the lock */
487 SharedWake
.Next
= NULL
;
490 /* We need to setup the first wait block. Currently an exclusive lock is
491 held, change the lock to contended mode. */
492 StackWaitBlock
.Exclusive
= FALSE
;
493 StackWaitBlock
.SharedCount
= 1;
494 StackWaitBlock
.Next
= NULL
;
495 StackWaitBlock
.Last
= &StackWaitBlock
;
496 StackWaitBlock
.SharedWakeChain
= &SharedWake
;
497 StackWaitBlock
.LastSharedWake
= &SharedWake
;
499 ASSERT_SRW_WAITBLOCK(&StackWaitBlock
);
501 NewValue
= (ULONG_PTR
)&StackWaitBlock
| RTL_SRWLOCK_OWNED
| RTL_SRWLOCK_CONTENDED
;
502 if (_InterlockedCompareExchange((PLONG
)&SRWLock
->Ptr
,
504 CurrentValue
) == CurrentValue
)
506 RtlpAcquireSRWLockSharedWait(SRWLock
,
510 /* Successfully set the shared count, we acquired the lock */
517 /* This is a fast path, we can simply try to set the shared count to 1 */
518 NewValue
= (1 << RTL_SRWLOCK_BITS
) | RTL_SRWLOCK_SHARED
| RTL_SRWLOCK_OWNED
;
520 /* The RTL_SRWLOCK_CONTENDED bit should never be set if neither the
521 RTL_SRWLOCK_SHARED nor the RTL_SRWLOCK_OWNED bit is set */
522 ASSERT(!(CurrentValue
& RTL_SRWLOCK_CONTENDED
));
524 if (_InterlockedCompareExchange((PLONG
)&SRWLock
->Ptr
,
526 CurrentValue
) == CurrentValue
)
528 /* Successfully set the shared count, we acquired the lock */
541 RtlReleaseSRWLockShared(IN OUT PRTL_SRWLOCK SRWLock
)
543 LONG_PTR CurrentValue
, NewValue
;
544 PRTLP_SRWLOCK_WAITBLOCK WaitBlock
;
549 CurrentValue
= *(volatile LONG_PTR
*)&SRWLock
->Ptr
;
551 if (CurrentValue
& RTL_SRWLOCK_SHARED
)
553 if (CurrentValue
& RTL_SRWLOCK_CONTENDED
)
555 /* There's a wait block, we need to wake a pending
556 exclusive acquirer if this is the last shared release */
557 WaitBlock
= RtlpAcquireWaitBlockLock(SRWLock
);
558 if (WaitBlock
!= NULL
)
560 LastShared
= (--WaitBlock
->SharedCount
== 0);
563 RtlpReleaseWaitBlockLockLastShared(SRWLock
,
566 RtlpReleaseWaitBlockLock(SRWLock
);
568 /* We released the lock */
574 /* This is a fast path, we can simply decrement the shared
575 count and store the pointer */
576 NewValue
= CurrentValue
>> RTL_SRWLOCK_BITS
;
580 NewValue
= (NewValue
<< RTL_SRWLOCK_BITS
) | RTL_SRWLOCK_SHARED
| RTL_SRWLOCK_OWNED
;
583 if (_InterlockedCompareExchange((PLONG
)&SRWLock
->Ptr
,
585 CurrentValue
) == CurrentValue
)
587 /* Successfully released the lock */
594 /* The RTL_SRWLOCK_SHARED bit has to be present now,
595 even in the contended case! */
596 RtlRaiseStatus(STATUS_RESOURCE_NOT_OWNED
);
606 RtlAcquireSRWLockExclusive(IN OUT PRTL_SRWLOCK SRWLock
)
608 __ALIGNED(16) RTLP_SRWLOCK_WAITBLOCK StackWaitBlock
;
609 PRTLP_SRWLOCK_WAITBLOCK First
, Last
;
611 if (InterlockedBitTestAndSetPointer(&SRWLock
->Ptr
,
612 RTL_SRWLOCK_OWNED_BIT
))
614 LONG_PTR CurrentValue
, NewValue
;
618 CurrentValue
= *(volatile LONG_PTR
*)&SRWLock
->Ptr
;
620 if (CurrentValue
& RTL_SRWLOCK_SHARED
)
622 /* A shared lock is being held right now. We need to add a wait block! */
624 if (CurrentValue
& RTL_SRWLOCK_CONTENDED
)
630 /* There are no wait blocks so far, we need to add ourselves as the first
631 wait block. We need to keep the shared count! */
632 StackWaitBlock
.Exclusive
= TRUE
;
633 StackWaitBlock
.SharedCount
= CurrentValue
>> RTL_SRWLOCK_BITS
;
634 StackWaitBlock
.Next
= NULL
;
635 StackWaitBlock
.Last
= &StackWaitBlock
;
636 StackWaitBlock
.Wake
= 0;
638 ASSERT_SRW_WAITBLOCK(&StackWaitBlock
);
640 NewValue
= (ULONG_PTR
)&StackWaitBlock
| RTL_SRWLOCK_SHARED
| RTL_SRWLOCK_CONTENDED
| RTL_SRWLOCK_OWNED
;
642 if (_InterlockedCompareExchange((PLONG
)&SRWLock
->Ptr
,
644 CurrentValue
) == CurrentValue
)
646 RtlpAcquireSRWLockExclusiveWait(SRWLock
,
649 /* Successfully acquired the exclusive lock */
656 if (CurrentValue
& RTL_SRWLOCK_OWNED
)
658 /* An exclusive lock is being held right now. We need to add a wait block! */
660 if (CurrentValue
& RTL_SRWLOCK_CONTENDED
)
663 StackWaitBlock
.Exclusive
= TRUE
;
664 StackWaitBlock
.SharedCount
= 0;
665 StackWaitBlock
.Next
= NULL
;
666 StackWaitBlock
.Last
= &StackWaitBlock
;
667 StackWaitBlock
.Wake
= 0;
669 ASSERT_SRW_WAITBLOCK(&StackWaitBlock
);
671 First
= RtlpAcquireWaitBlockLock(SRWLock
);
675 Last
->Next
= &StackWaitBlock
;
676 First
->Last
= &StackWaitBlock
;
678 RtlpReleaseWaitBlockLock(SRWLock
);
680 RtlpAcquireSRWLockExclusiveWait(SRWLock
,
683 /* Successfully acquired the exclusive lock */
689 /* There are no wait blocks so far, we need to add ourselves as the first
690 wait block. We need to keep the shared count! */
691 StackWaitBlock
.Exclusive
= TRUE
;
692 StackWaitBlock
.SharedCount
= 0;
693 StackWaitBlock
.Next
= NULL
;
694 StackWaitBlock
.Last
= &StackWaitBlock
;
695 StackWaitBlock
.Wake
= 0;
697 ASSERT_SRW_WAITBLOCK(&StackWaitBlock
);
699 NewValue
= (ULONG_PTR
)&StackWaitBlock
| RTL_SRWLOCK_OWNED
| RTL_SRWLOCK_CONTENDED
;
700 if (_InterlockedCompareExchange((PLONG
)&SRWLock
->Ptr
,
702 CurrentValue
) == CurrentValue
)
704 RtlpAcquireSRWLockExclusiveWait(SRWLock
,
707 /* Successfully acquired the exclusive lock */
714 if (!InterlockedBitTestAndSetPointer(&SRWLock
->Ptr
,
715 RTL_SRWLOCK_OWNED_BIT
))
717 /* We managed to get hold of a simple exclusive lock! */
731 RtlReleaseSRWLockExclusive(IN OUT PRTL_SRWLOCK SRWLock
)
733 LONG_PTR CurrentValue
, NewValue
;
734 PRTLP_SRWLOCK_WAITBLOCK WaitBlock
;
738 CurrentValue
= *(volatile LONG_PTR
*)&SRWLock
->Ptr
;
740 if (!(CurrentValue
& RTL_SRWLOCK_OWNED
))
742 RtlRaiseStatus(STATUS_RESOURCE_NOT_OWNED
);
745 if (!(CurrentValue
& RTL_SRWLOCK_SHARED
))
747 if (CurrentValue
& RTL_SRWLOCK_CONTENDED
)
749 /* There's a wait block, we need to wake the next pending
750 acquirer (exclusive or shared) */
751 WaitBlock
= RtlpAcquireWaitBlockLock(SRWLock
);
752 if (WaitBlock
!= NULL
)
754 RtlpReleaseWaitBlockLockExclusive(SRWLock
,
757 /* We released the lock */
763 /* This is a fast path, we can simply clear the RTL_SRWLOCK_OWNED
764 bit. All other bits should be 0 now because this is a simple
765 exclusive lock and no one is waiting. */
767 ASSERT(!(CurrentValue
& ~RTL_SRWLOCK_OWNED
));
770 if (_InterlockedCompareExchange((PLONG
)&SRWLock
->Ptr
,
772 CurrentValue
) == CurrentValue
)
774 /* We released the lock */
781 /* The RTL_SRWLOCK_SHARED bit must not be present now,
782 not even in the contended case! */
783 RtlRaiseStatus(STATUS_RESOURCE_NOT_OWNED
);