Michael S (already5chosen.delete@this.yahoo.com) on January 14, 2020 2:07 am wrote:
> 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.

I think the article describes it wrong. I think "lock" itself (the shared structure) is only a single pointer, that's why mcs_spin_lock takes `struct mcs_spinlock **lock` and it updates that pointer. So the pointer is null when the lock is available.

So all the diagrams should not show any second 0/1 field in that "MCS lock" thing on the left.

That's consistent with the MCS paper I linked which only uses a pointer for the lock itself, but all the per-waiter nodes have both a next pointer and locked indicator.

I can't actually confirm this because it seems like MCS lock has ~zero actual uses in the kernel, unless I'm searching wrong.

>
> 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?

I don't know how Windows does it for SRW lock, but that's one approach. IIRC Windows CRITICAL_SECTION creates the waiter object lazily when there is contention.

Windows is a bit different than Linux in that you explicitly create the objects to wait on, e.g., via CreateEvent and you get a kernel handle. Futex is different in that you don't really need to create/register the futex: it just comes into existence when some futex call is made and (presumably) ceases to exist from the kernel's PoV when no one is waiting on it. Also, futex has coupling between the userspace control word (i.e., the kernel knows about it), but that's not the case on Windows with Event objects: the control word(s) you use in userspace are just used in userspace.

It is possible that SRW locks use a futex-like approach and don't use the Event mechanism. It would be pretty easy to check by looking at the user-mode assembly.

>
> 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?

Presumably the waiters can communicate that information via the control word in their node. E.g., they initially set the node to a spinning state, spin on it, and if that fails, they set it to a blocked state and sleep on their event (or whatever sleep mechanism they use).

Yes, these userspace state changes followed by system calls are racy, but that has to handled somehow anyways. On Windows, that often works because the events have memory: i.e., the waiter writes their control word, then blocks, and if the waker races in between those two events (sees the "waiting flag" set, and then calls wake on the event before the waiter actually slept), it still works because the event maintains the triggered state so the subsequent wait call is a no-op.

Other strategies are possible (e.g., a futex-like approach where the race is closed by letting the kernel also know about the control word).

>
> >
> > 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?

It seems like it. If we go by the Linux kernel example, acquire and release are just a CAS each, plus a really small amount of work to set up the stack-local node.

Note that some locks "just" have a plain store for unlock on x86, since that is enough to provide the release semantics - but this only works with very simple locks where waiters never modify the control word, so no info is lost by an unconditional write (or perhaps some type of lock where losing info can be tolerated [1]). Those locks might have roughly half the uncontended cost. I don't think it applies to CRITICAL_SECTION in Windows though.

---

[1] One could imagine a lock that uses the control word to indicate the usual stuff like "some waiters", and then the unlocker does first a check to see if the lock is in the uncontended state (i.e., just the "locked" bit set, no waiters indicated), and if so does a plain store, but if not falls back to the slower full handling path using CAS. Now there is a race between that check and the store, but maybe you "fix" that by having the waiters periodically wake up and check to see what's going on, or a separate thread that does that (e.g., checks for locks that are unlocked but have waiters), and newly arriving lockers can make that check too. Since this race may often be rare, maybe it doesn't happen often. Frankly this sounds terrible, but if you *really* want to cut out of one of the CAS operations you could try it.