Nksingh (None.delete@this.none.non) on January 9, 2020 1:17 pm wrote:
> Michael S (already5chosen.delete@this.yahoo.com) on January 7, 2020 1:35 am wrote:
> > Can you point me to explanation of how SRW locks are implemented under the hood?
> > "No additional memory" is intriguing and right now (still sort of morning here, not
> > the time of day when I am able to think) I can't figure out how they did it.
> > Or, may be, you could give us a short explanation right here?
> >
>
> It is helpful to understand mcs locks (aka queued spinlocks). https://lwn.net/Articles/590243/
>
> The key is that only the list of waiting threads needs to be tracked, which can be done as a list of
> linked "wait block" elements on the waiting threads' stacks. When the lock is held and there are waiters,
> the lock points at the last element added to the linked list. This list can be maintained using compare
> and swap operations with guaranteed forward progress for adding elements to the list.
>
> The mcs lock is described as a spinning lock, but instead of the waiter spinning, the waiter can
> block and the lock releaser can wake up the waiter based on information stored in the wait block.
> Recent versions of NT use a wake threads by ID kernel primitive to wake up a thread. In practice
> on NT, we spin for a while before blocking, so it's really like an mcs lock with blocking added.


Thank you.

I finally found a time to read it.
There are still a few questions:
1. The article describes a MCS lock as a record that consists from pointer + integer. How does Microsoft's implementation compress it into into single pointer-sized word? By requiring alignment (needed anyway for atomicity) and using LS bit for 'Locked' flag?
On WIn64 there are several more bits available in the MS part of the pointer value, but SRW locks exist on Win32 as well, so I'd guess that implementation does not rely on availability of MS bits.

2. As you said, infinite spinning described in the article is appropriate for kernel locking, but for user-mode locking one wants to spin 1 time (or, may be a few times, say 20) and then switch to blocking/waiting/sleeping. As you say, in this situation there is no problem of space, since all housekeeping is done on waiter's stack. But I suppose that you don't want to use heavy operations like CreateEvent() during each and every wait. So there should be some sort of predefined synchronization object, probably one per thread, that is placed in known location (somewhere in TLS?) and shared by all SRW locks of given process. Is it a correct description?

3. When releaser found out that there are waiter(s), how does it know if the first waiter in line is still spinning (and thus doesn't need to be awoken) or already blocked==waiting==sleeping?

>
> Compared to a critical section, an srw lock exclusive uncontended acquire
> should be about the same. The release should also be about the same.
>

If uncontended case is as fast as critical section then it could be said that SRW obsoletes critical sections for all users except those few who need nested enter/leave or use advanced features like manual control of spin count or TryEnter.
Or am I missing something?