From: Yuxuan Shui yshui@codeweavers.com
--- dlls/kernel32/tests/sync.c | 24 ++ dlls/ntdll/sync.c | 534 ++++++++++++++++++++++++++----------- 2 files changed, 403 insertions(+), 155 deletions(-)
diff --git a/dlls/kernel32/tests/sync.c b/dlls/kernel32/tests/sync.c index 60180194b7a..4eaec87c52f 100644 --- a/dlls/kernel32/tests/sync.c +++ b/dlls/kernel32/tests/sync.c @@ -2533,6 +2533,29 @@ static void test_srwlock_example(void) trace("number of total exclusive accesses is %ld\n", srwlock_protected_value); }
+static void test_srwlock_quirk(void) +{ + union { SRWLOCK *s; LONG *l; } u = { &srwlock_example }; + + if (!pInitializeSRWLock) { + /* function is not yet in XP, only in newer Windows */ + win_skip("no srw lock support.\n"); + return; + } + + *u.l = 0; + pReleaseSRWLockExclusive(&srwlock_example); + ok(*u.l == 0xffffffff, "expected 0xffffffff, got %lx\n", *u.l); + + *u.l = 1; + pReleaseSRWLockExclusive(&srwlock_example); + ok(*u.l == 0, "expected 0x0, got %lx\n", *u.l); + + *u.l = 0x10000; + pReleaseSRWLockExclusive(&srwlock_example); + ok(*u.l == 0xffff, "expected 0xffff, got %lx\n", *u.l); +} + static DWORD WINAPI alertable_wait_thread(void *param) { HANDLE *semaphores = param; @@ -2887,6 +2910,7 @@ START_TEST(sync) test_srwlock_base(&aligned_srwlock); test_srwlock_base(&unaligned_srwlock.lock); test_srwlock_example(); + test_srwlock_quirk(); test_alertable_wait(); test_apc_deadlock(); test_crit_section(); diff --git a/dlls/ntdll/sync.c b/dlls/ntdll/sync.c index fa64917029a..63c14d59daf 100644 --- a/dlls/ntdll/sync.c +++ b/dlls/ntdll/sync.c @@ -26,6 +26,8 @@ #include <stdarg.h> #include <stdio.h> #include <stdlib.h> +#include <stdint.h> +#include <assert.h> #include <time.h>
#include "ntstatus.h" @@ -471,24 +473,83 @@ DWORD WINAPI RtlRunOnceExecuteOnce( RTL_RUN_ONCE *once, PRTL_RUN_ONCE_INIT_FN fu return RtlRunOnceComplete( once, 0, context ? *context : NULL ); }
-struct srw_lock -{ - short exclusive_waiters; +/** + * The SRWLOCK is a tagged pointer, with the last 4 bits been the tag. + * The pointer part serves 2 roles: if there is no waiters on the lock, + * it counts the number of shared owners of the lock; otherwise, it + * points to the end of the waiter queue, which is a linked list of waiters. + * This also implies the pointer must be 16 byte aligned. + * + * There are a couple helper functions below to make accessing different parts + * of the SRWLOCK easier. + */ + +enum srwlock_tag { + SRWLOCK_TAG_LOCKED = 1, + SRWLOCK_TAG_HAS_WAITERS = 2, + /* Unknown purpose on Windows, but we use it to indicate the list + * is being modified. */ + SRWLOCK_TAG_LIST_LOCKED = 4, + /* Unclear purpose on Windows, might be indicating this lock has + * > 1 owners. */ + SRWLOCK_TAG_HAS_MULTIPLE_OWNERS = 8, +};
- /* Number of shared owners, or -1 if owned exclusive. - * - * Sadly Windows has no equivalent to FUTEX_WAIT_BITSET, so in order to wake - * up *only* exclusive or *only* shared waiters (and thus avoid spurious - * wakeups), we need to wait on two different addresses. - * RtlAcquireSRWLockShared() needs to know the values of "exclusive_waiters" - * and "owners", but RtlAcquireSRWLockExclusive() only needs to know the - * value of "owners", so the former can wait on the entire structure, and - * the latter waits only on the "owners" member. Note then that "owners" - * must not be the first element in the structure. +enum srwlock_waiter_state { + SRWLOCK_WAITER_STATE_IS_EXCLUSIVE = 1, + /* ???? = 2, */ + SRWLOCK_WAITER_STATE_NOTIFIED = 4, +}; +DECLSPEC_ALIGN(16) struct srwlock_waiter { + /* Note the prev pointer is uninitialized for the list head. */ + struct srwlock_waiter *prev; + struct srwlock_waiter *head; + struct srwlock_waiter *next; + DWORD thread_id; +#ifdef _WIN64 + DWORD padding; +#endif + /* When the first waiter appears, the shared owner counter store in + * SRWLOCK is transferred here, however only the lower 28 bits are kept. + * A special value 0xffffffff indicates this waiter is not at the + * head of the list, and 0xfffffffe indicates this waiter is at the head + * of the list, but the lock is held exclusively. */ - short owners; + DWORD num_owners; + + /* A bitflag of states, see `enum srwlock_waiter_state`. */ + DWORD state; }; -C_ASSERT( sizeof(struct srw_lock) == 4 ); + +const DWORD SRWLOCK_WAITER_IS_NOT_HEAD = 0xffffffff; +const DWORD SRWLOCK_WAITER_EXCLUSIVELY_LOCKED = 0xfffffffe; + +static inline struct srwlock_waiter *srwlock_get_waiter(RTL_SRWLOCK lock) { + uintptr_t ptr = (uintptr_t)lock.Ptr; + return (void *)(ptr & ~(uintptr_t)0xf); +} + +static inline size_t srwlock_get_shared_count(RTL_SRWLOCK lock) { + uintptr_t ptr = (uintptr_t)lock.Ptr; + return (size_t)((ptr & (uintptr_t)0xfffffff0) >> 4); +} + +static inline USHORT srwlock_get_tag(RTL_SRWLOCK lock) { + uintptr_t ptr = (uintptr_t)lock.Ptr; + return (USHORT)(ptr & (uintptr_t)0xf); +} + +static inline RTL_SRWLOCK srwlock_from_waiter(struct srwlock_waiter *waiter, USHORT tag) { + RTL_SRWLOCK lock; + lock.Ptr = (void *)((uintptr_t)waiter | (uintptr_t)tag); + return lock; +} + +static inline RTL_SRWLOCK srwlock_from_shared_owner_count(size_t count, USHORT tag) { + RTL_SRWLOCK lock; + lock.Ptr = (void *)(((uintptr_t)count << 4) | (uintptr_t)tag); + return lock; +}
/*********************************************************************** * RtlInitializeSRWLock (NTDLL.@) @@ -496,141 +557,208 @@ C_ASSERT( sizeof(struct srw_lock) == 4 ); * NOTES * Please note that SRWLocks do not keep track of the owner of a lock. * It doesn't make any difference which thread for example unlocks an - * SRWLock (see corresponding tests). This implementation uses two - * keyed events (one for the exclusive waiters and one for the shared - * waiters) and is limited to 2^15-1 waiting threads. + * SRWLock (see corresponding tests). */ void WINAPI RtlInitializeSRWLock( RTL_SRWLOCK *lock ) { lock->Ptr = NULL; }
-/*********************************************************************** - * RtlAcquireSRWLockExclusive (NTDLL.@) - * - * NOTES - * Unlike RtlAcquireResourceExclusive this function doesn't allow - * nested calls from the same thread. "Upgrading" a shared access lock - * to an exclusive access lock also doesn't seem to be supported. - */ -void WINAPI RtlAcquireSRWLockExclusive( RTL_SRWLOCK *lock ) +/* Transfer the ownership of the lock to the waiters at the front of the list, + * remove them from the list, and wake them up. Only one thread can call this + * function at any given time. */ +static void srwlock_transfer_ownership(RTL_SRWLOCK *lock) { - union { RTL_SRWLOCK *rtl; struct srw_lock *s; LONG *l; } u = { lock }; - - InterlockedIncrement16( &u.s->exclusive_waiters ); - - for (;;) - { - union { struct srw_lock s; LONG l; } old, new; - BOOL wait; + RTL_SRWLOCK old, new, read; + USHORT tag; + struct srwlock_waiter *last, *head, *last_up_to_date, *last_to_remove, + *new_head; + + TRACE("%p\n", lock); + + do { + old.Ptr = ReadAcquirePointer(&lock->Ptr); + tag = srwlock_get_tag(old); + last = srwlock_get_waiter(old); + + assert(!(tag & SRWLOCK_TAG_LIST_LOCKED)); + tag |= SRWLOCK_TAG_LIST_LOCKED; + new = srwlock_from_waiter(last, tag); + } while (InterlockedCompareExchangePointer(&lock->Ptr, new.Ptr, old.Ptr) != + old.Ptr); + + assert(tag & SRWLOCK_TAG_HAS_WAITERS); + old = new; + last = srwlock_get_waiter(old); + assert(last != NULL); + head = last->head; + assert(head != NULL); + last_up_to_date = last; /* the last waiter whose head pointer is up-to-date. */ + new_head = NULL; + assert(head->num_owners == 0 || + head->num_owners == SRWLOCK_WAITER_EXCLUSIVELY_LOCKED); + head->num_owners = 0; + last_to_remove = head; + do { + tag = srwlock_get_tag(old); + last = srwlock_get_waiter(old); + + /* Every time cmpxchg failed, new waiter could have been added + * to the end of the list. Which means we might have more waiters + * to wake, and more head pointers to update. */ + while (TRUE) { + struct srwlock_waiter *tmp = + ReadAcquirePointer((void **)&last_to_remove->next); + if (tmp != new_head) { + new_head = tmp; + last_up_to_date = last_to_remove; + } + if (!new_head) + break; + if (last_to_remove->state & SRWLOCK_WAITER_STATE_IS_EXCLUSIVE) { + new_head->num_owners = SRWLOCK_WAITER_EXCLUSIVELY_LOCKED; + break; + } + new_head->num_owners = last_to_remove->num_owners + 1; + if (new_head->num_owners > 1) + tag |= SRWLOCK_TAG_HAS_MULTIPLE_OWNERS; + if (new_head->state & SRWLOCK_WAITER_STATE_IS_EXCLUSIVE) + break; + last_to_remove = new_head; + }
- do - { - old.s = *u.s; - new.s = old.s; + while (last_up_to_date != last) { + last_up_to_date = ReadAcquirePointer((void **)&last_up_to_date->next); + last_up_to_date->head = new_head; + }
- if (!old.s.owners) - { - /* Not locked exclusive or shared. We can try to grab it. */ - new.s.owners = -1; - --new.s.exclusive_waiters; - wait = FALSE; - } + tag = SRWLOCK_TAG_LOCKED; + if (new_head) { + tag |= SRWLOCK_TAG_HAS_WAITERS; + if (new_head->num_owners > 1 && + new_head->num_owners != SRWLOCK_WAITER_EXCLUSIVELY_LOCKED) + tag |= SRWLOCK_TAG_HAS_MULTIPLE_OWNERS; + new = srwlock_from_waiter(last, tag); + } else { + if (last_to_remove->state & SRWLOCK_WAITER_STATE_IS_EXCLUSIVE) + new = srwlock_from_shared_owner_count(0, tag); else - { - wait = TRUE; - } - } while (InterlockedCompareExchange( u.l, new.l, old.l ) != old.l); + new = srwlock_from_shared_owner_count(last_to_remove->num_owners + 1, tag); + }
- if (!wait) return; - RtlWaitOnAddress( &u.s->owners, &new.s.owners, sizeof(short), NULL ); + read.Ptr = InterlockedCompareExchangePointer(&lock->Ptr, new.Ptr, old.Ptr); + if (read.Ptr == old.Ptr) + break; + old = read; + } while (TRUE); + + while (TRUE) { + /* waking up the waiter will invalidate the waiter's entry in + * the list. */ + struct srwlock_waiter *next = head->next; + InterlockedOr((LONG *)&head->state, SRWLOCK_WAITER_STATE_NOTIFIED); + RtlWakeAddressSingle(&head->state); + if (head == last_to_remove) + break; + head = next; } }
-/*********************************************************************** - * RtlAcquireSRWLockShared (NTDLL.@) +/** + * Add a new waiter to the SRWLOCK, and wait on it. The wait will be interrupted + * if the value stored in `lock` changes to something other than `expected`. * - * NOTES - * Do not call this function recursively - it will only succeed when - * there are no threads waiting for an exclusive lock! + * Returns TRUE if the lock is acquired, FALSE otherwise. */ -void WINAPI RtlAcquireSRWLockShared( RTL_SRWLOCK *lock ) +static BOOLEAN srwlock_wait(RTL_SRWLOCK *lock, DWORD waiter_state, + RTL_SRWLOCK expected) { - union { RTL_SRWLOCK *rtl; struct srw_lock *s; LONG *l; } u = { lock }; - - for (;;) - { - union { struct srw_lock s; LONG l; } old, new; - BOOL wait; + RTL_SRWLOCK new; + USHORT tag; + struct srwlock_waiter *prev = NULL, waiter = {0}; + + tag = srwlock_get_tag(expected); + TRACE("%p %p %p\n", lock, &waiter, expected.Ptr); + + waiter.state = waiter_state; + if (tag & SRWLOCK_TAG_HAS_WAITERS) { + prev = srwlock_get_waiter(expected); + if (!(tag & SRWLOCK_TAG_LIST_LOCKED)) + waiter.head = prev->head; + else + /* some other thread is modifying the list, they + * are responsible for setting our head pointer. */ + waiter.head = NULL; + waiter.prev = prev; + waiter.num_owners = SRWLOCK_WAITER_IS_NOT_HEAD; + } else { + waiter.head = &waiter; + waiter.num_owners = srwlock_get_shared_count(expected); + if (waiter.num_owners > 1) + tag |= SRWLOCK_TAG_HAS_MULTIPLE_OWNERS; + if (waiter.num_owners == 0) + waiter.num_owners = SRWLOCK_WAITER_EXCLUSIVELY_LOCKED; + tag |= SRWLOCK_TAG_HAS_WAITERS; + } + waiter.next = NULL;
- do + if (prev) { + if (InterlockedCompareExchangePointer((void **)&prev->next, + (void *)&waiter, NULL) != NULL) { - old.s = *u.s; - new = old; - - if (old.s.owners != -1 && !old.s.exclusive_waiters) - { - /* Not locked exclusive, and no exclusive waiters. - * We can try to grab it. */ - ++new.s.owners; - wait = FALSE; - } - else - { - wait = TRUE; - } - } while (InterlockedCompareExchange( u.l, new.l, old.l ) != old.l); - - if (!wait) return; - RtlWaitOnAddress( u.s, &new.s, sizeof(struct srw_lock), NULL ); + /* Someone else is also appending to the list, they have linked their + * node to `prev`, but hasn't changed lock->Ptr yet. So we wait for + * the lock to change and retry. */ + RtlWaitOnAddress(&lock->Ptr, &expected.Ptr, sizeof(expected.Ptr), + NULL); + return FALSE; + } } -} - -/*********************************************************************** - * RtlReleaseSRWLockExclusive (NTDLL.@) - */ -void WINAPI RtlReleaseSRWLockExclusive( RTL_SRWLOCK *lock ) -{ - union { RTL_SRWLOCK *rtl; struct srw_lock *s; LONG *l; } u = { lock }; - union { struct srw_lock s; LONG l; } old, new;
- do + /* Once we reach here, `prev->next` can't be changed by anyone but us. So + * if we fail to change lock->Ptr, we have to reset it so others can append + * to the list. */ + new = srwlock_from_waiter(&waiter, tag); + if (InterlockedCompareExchangePointer(&lock->Ptr, new.Ptr, expected.Ptr) != + expected.Ptr) { - old.s = *u.s; - new = old; + if (prev) + WriteReleasePointer((void **)&prev->next, NULL); + return FALSE; + }
- if (old.s.owners != -1) ERR("Lock %p is not owned exclusive!\n", lock); + RtlWakeAddressSingle(&lock->Ptr);
- new.s.owners = 0; - } while (InterlockedCompareExchange( u.l, new.l, old.l ) != old.l); + TRACE("waiting: %p, %p, %lu\n", lock, &waiter, waiter.num_owners); + do { + waiter_state = ReadAcquire((LONG *)&waiter.state); + if (waiter_state & SRWLOCK_WAITER_STATE_NOTIFIED) + break; + RtlWaitOnAddress(&waiter.state, &waiter_state, sizeof(DWORD), NULL); + } while (TRUE);
- if (new.s.exclusive_waiters) - RtlWakeAddressSingle( &u.s->owners ); - else - RtlWakeAddressAll( u.s ); + TRACE("acquired: %p\n", lock); + return TRUE; }
-/*********************************************************************** - * RtlReleaseSRWLockShared (NTDLL.@) - */ -void WINAPI RtlReleaseSRWLockShared( RTL_SRWLOCK *lock ) +static BOOLEAN srwlock_try_acquire_exclusive(RTL_SRWLOCK *lock, RTL_SRWLOCK *old) { - union { RTL_SRWLOCK *rtl; struct srw_lock *s; LONG *l; } u = { lock }; - union { struct srw_lock s; LONG l; } old, new; + RTL_SRWLOCK new; + USHORT tag;
- do - { - old.s = *u.s; - new = old; + do { + old->Ptr = ReadAcquirePointer(&lock->Ptr); + tag = srwlock_get_tag(*old);
- if (old.s.owners == -1) ERR("Lock %p is owned exclusive!\n", lock); - else if (!old.s.owners) ERR("Lock %p is not owned shared!\n", lock); + if (tag & SRWLOCK_TAG_LOCKED) + return FALSE;
- --new.s.owners; - } while (InterlockedCompareExchange( u.l, new.l, old.l ) != old.l); + new = srwlock_from_shared_owner_count(0, SRWLOCK_TAG_LOCKED); + } while (InterlockedCompareExchangePointer(&lock->Ptr, new.Ptr, old->Ptr) != + old->Ptr);
- if (!new.s.owners) - RtlWakeAddressSingle( &u.s->owners ); + RtlWakeAddressSingle(&lock->Ptr); + return TRUE; }
/*********************************************************************** @@ -642,28 +770,55 @@ void WINAPI RtlReleaseSRWLockShared( RTL_SRWLOCK *lock ) */ BOOLEAN WINAPI RtlTryAcquireSRWLockExclusive( RTL_SRWLOCK *lock ) { - union { RTL_SRWLOCK *rtl; struct srw_lock *s; LONG *l; } u = { lock }; - union { struct srw_lock s; LONG l; } old, new; - BOOLEAN ret; + RTL_SRWLOCK old; + return srwlock_try_acquire_exclusive(lock, &old); +}
- do - { - old.s = *u.s; - new.s = old.s; +/*********************************************************************** + * RtlAcquireSRWLockExclusive (NTDLL.@) + * + * NOTES + * Unlike RtlAcquireResourceExclusive this function doesn't allow + * nested calls from the same thread. "Upgrading" a shared access lock + * to an exclusive access lock also doesn't seem to be supported. + */ +void WINAPI RtlAcquireSRWLockExclusive( RTL_SRWLOCK *lock ) +{ + RTL_SRWLOCK old;
- if (!old.s.owners) - { - /* Not locked exclusive or shared. We can try to grab it. */ - new.s.owners = -1; - ret = TRUE; - } - else - { - ret = FALSE; - } - } while (InterlockedCompareExchange( u.l, new.l, old.l ) != old.l); + TRACE("%p\n", lock);
- return ret; + while (!srwlock_try_acquire_exclusive(lock, &old)) + if (srwlock_wait(lock, SRWLOCK_WAITER_STATE_IS_EXCLUSIVE, old)) + break; +} + +static BOOLEAN srwlock_try_acquire_shared(RTL_SRWLOCK *lock, RTL_SRWLOCK *old) +{ + RTL_SRWLOCK new; + USHORT tag; + size_t shared_count; + + do { + old->Ptr = ReadAcquirePointer(&lock->Ptr); + tag = srwlock_get_tag(*old); + shared_count = srwlock_get_shared_count(*old); + + if (tag & SRWLOCK_TAG_HAS_WAITERS) + return FALSE; + + if ((tag & SRWLOCK_TAG_LOCKED) && shared_count == 0) + return FALSE; + + /* No waiters to check, and the lock is either locked shared, or not + * locked at all. We can try to grab it. */ + new = srwlock_from_shared_owner_count(shared_count + 1, + tag | SRWLOCK_TAG_LOCKED); + } while (InterlockedCompareExchangePointer(&lock->Ptr, new.Ptr, + old->Ptr ) != old->Ptr); + + RtlWakeAddressSingle(&lock->Ptr); + return TRUE; }
/*********************************************************************** @@ -671,29 +826,98 @@ BOOLEAN WINAPI RtlTryAcquireSRWLockExclusive( RTL_SRWLOCK *lock ) */ BOOLEAN WINAPI RtlTryAcquireSRWLockShared( RTL_SRWLOCK *lock ) { - union { RTL_SRWLOCK *rtl; struct srw_lock *s; LONG *l; } u = { lock }; - union { struct srw_lock s; LONG l; } old, new; - BOOLEAN ret; + RTL_SRWLOCK old; + return srwlock_try_acquire_shared(lock, &old); +}
- do - { - old.s = *u.s; - new.s = old.s; +/*********************************************************************** + * RtlAcquireSRWLockShared (NTDLL.@) + * + * NOTES + * Do not call this function recursively - it will only succeed when + * there are no threads waiting for an exclusive lock! + */ +void WINAPI RtlAcquireSRWLockShared( RTL_SRWLOCK *lock ) +{ + RTL_SRWLOCK old;
- if (old.s.owners != -1 && !old.s.exclusive_waiters) - { - /* Not locked exclusive, and no exclusive waiters. - * We can try to grab it. */ - ++new.s.owners; - ret = TRUE; + TRACE("%p\n", lock); + + while (!srwlock_try_acquire_shared(lock, &old)) + if (srwlock_wait(lock, 0, old)) + break; +} + +/*********************************************************************** + * RtlReleaseSRWLockExclusive (NTDLL.@) + */ +void WINAPI RtlReleaseSRWLockExclusive( RTL_SRWLOCK *lock ) +{ + RTL_SRWLOCK old, new; + USHORT tag; + + TRACE("%p %p\n", lock, lock->Ptr); + + do { + old.Ptr = ReadAcquirePointer(&lock->Ptr); + tag = srwlock_get_tag(old); + if (tag & SRWLOCK_TAG_HAS_WAITERS) + return srwlock_transfer_ownership(lock); + + /* Looks weird but this is how Windows does it. */ + new.Ptr = (void *)((uintptr_t)old.Ptr - 1); + } while (InterlockedCompareExchangePointer(&lock->Ptr, new.Ptr, old.Ptr) != + old.Ptr); + + RtlWakeAddressSingle(&lock->Ptr); +} + +/*********************************************************************** + * RtlReleaseSRWLockShared (NTDLL.@) + */ +void WINAPI RtlReleaseSRWLockShared( RTL_SRWLOCK *lock ) +{ + RTL_SRWLOCK old, new; + USHORT tag; + size_t shared_count; + struct srwlock_waiter *last; + + TRACE("%p %p\n", lock, lock->Ptr); + + do { + old.Ptr = ReadAcquirePointer(&lock->Ptr); + tag = srwlock_get_tag(old); + shared_count = srwlock_get_shared_count(old); + last = srwlock_get_waiter(old); + + if (!(tag & SRWLOCK_TAG_LOCKED)) { + /* interestingly this check is only done for shared locks. */ + EXCEPTION_RECORD record; + record.ExceptionAddress = RtlReleaseSRWLockShared; + record.ExceptionCode = STATUS_RESOURCE_NOT_OWNED; + record.ExceptionFlags = 0; + record.ExceptionRecord = NULL; + record.NumberParameters = 0; + return RtlRaiseException(&record); } - else - { - ret = FALSE; + + if (tag & SRWLOCK_TAG_HAS_WAITERS) { + shared_count = InterlockedDecrement((LONG *)&last->head->num_owners); + if (shared_count == 0) + /* Only one thread reaches here. */ + srwlock_transfer_ownership(lock); + return; } - } while (InterlockedCompareExchange( u.l, new.l, old.l ) != old.l);
- return ret; + if (shared_count - 1 < 2) + tag &= ~SRWLOCK_TAG_HAS_MULTIPLE_OWNERS; + if (shared_count - 1 == 0) + tag &= ~SRWLOCK_TAG_LOCKED; + new = srwlock_from_shared_owner_count(shared_count - 1, tag); + } while (InterlockedCompareExchangePointer(&lock->Ptr, new.Ptr, old.Ptr) != + old.Ptr); + + RtlWakeAddressSingle(&lock->Ptr); }
/***********************************************************************