Linux Virtualization - May 2014 - [PATCH v10 03/19] qspinlock: Add pending bit

2014-05-13 15:47-0400, Waiman Long:
> On 05/12/2014 11:22 AM, Radim Kr?m?? wrote:
> >I think there is an unwanted scenario on virtual machines:
> >1) VCPU sets the pending bit and start spinning.
> >2) Pending VCPU gets descheduled.
> >     - we have PLE and lock holder isn't running [1]
> >     - the hypervisor randomly preempts us
> >3) Lock holder unlocks while pending VCPU is waiting in queue.
> >4) Subsequent lockers will see free lock with set pending bit and will
> >    loop in trylock's 'for (;;)'
> >     - the worst-case is lock starving [2]
> >     - PLE can save us from wasting whole timeslice
> >
> >Retry threshold is the easiest solution, regardless of its ugliness
[4].
> 
> Yes, that can be a real issue. Some sort of retry threshold, as you said,
> should be able to handle it.
> 
> BTW, the relevant patch should be 16/19 where the PV spinlock stuff should
> be discussed. This patch is perfectly fine.
Ouch, my apology to Peter didn't make it ... Agreed, I should have split
the comment under patches
 [06/19] (part quoted above; does not depend on PV),
 [16/19] (part quoted below) and
 [17/19] (general doubts).
> >Another minor design flaw is that formerly first VCPU gets appended to
> >the tail when it decides to queue;
> >is the performance gain worth it?
> >
> >Thanks.
> 
> Yes, the performance gain is worth it. The primary goal is to be not worse
> than ticket spinlock in light load situation which is the most common case.
> This feature is need to achieve that.
Ok.
I've seen merit in pvqspinlock even with slightly slower first-waiter,
so I would have happily sacrificed those horrible branches.
(I prefer elegant to optimized code, but I can see why we want to be
 strictly better than ticketlock.)
Peter mentioned that we are focusing on bare-metal patches, so I'll
withold my other paravirt rants until they are polished.

And to forcefully bring this thread a little bit on-topic:

Pending-bit is effectively a lock in a lock, so I was wondering why
don't we use more pending bits; advantages are the same, just diminished
by the probability of having an ideally contended lock:
 - waiter won't be blocked on RAM access if critical section (or more)
   ends sooner
 - some unlucky cacheline is not forgotten
 - faster unlock (no need for tail operations)
(- ?)
disadvantages are magnified:
 - increased complexity
 - intense cacheline sharing
   (I thought that this is the main disadvantage of ticketlock.)
(- ?)

One bit still improved performance, is it the best we got?

Thanks.

On Wed, May 14, 2014 at 06:51:24PM +0200, Radim Kr?m??
wrote:
> Ok.
> I've seen merit in pvqspinlock even with slightly slower first-waiter,
> so I would have happily sacrificed those horrible branches.
> (I prefer elegant to optimized code, but I can see why we want to be
>  strictly better than ticketlock.)
> Peter mentioned that we are focusing on bare-metal patches, so I'll
> withold my other paravirt rants until they are polished.
Well, paravirt must happen too, but comes later in this series, patch 3
which we're replying to is still very much in the bare metal part of the
series.

I've not had time yet to decode all that Waiman has done to make
paravirt work.

But as a general rule I like patches that start with something simple
and working and then optimize it, this series doesn't seem to quite
grasp that.
> And to forcefully bring this thread a little bit on-topic:
> 
> Pending-bit is effectively a lock in a lock, so I was wondering why
> don't we use more pending bits; advantages are the same, just
diminished
> by the probability of having an ideally contended lock:
>  - waiter won't be blocked on RAM access if critical section (or more)
>    ends sooner
>  - some unlucky cacheline is not forgotten
>  - faster unlock (no need for tail operations)
> (- ?)
> disadvantages are magnified:
>  - increased complexity
>  - intense cacheline sharing
>    (I thought that this is the main disadvantage of ticketlock.)
> (- ?)
> 
> One bit still improved performance, is it the best we got?
So, the advantage of one bit is that if we use a whole byte for 1 bit we
can avoid some atomic ops.

The entire reason for this in-word spinner is to amortize the cost of
hitting the external node cacheline.

So traditional locks like test-and-test and the ticket lock only ever
access the spinlock word itsef, this MCS style queueing lock has a
second (and, see my other rants in this thread, when done wrong more
than 2) cacheline to touch.

That said, all our benchmarking is pretty much for the cache-hot case,
so I'm not entirely convinced yet that the one pending bit makes up for
it, it does in the cache-hot case.

But... writing cache-cold benchmarks is _hard_ :/
-------------- next part --------------
A non-text attachment was scrubbed...
Name: not available
Type: application/pgp-signature
Size: 836 bytes
Desc: not available
URL:
<http://lists.linuxfoundation.org/pipermail/virtualization/attachments/20140514/d1bc1ad6/attachment.sig>

2014-05-14 19:00+0200, Peter Zijlstra:
> On Wed, May 14, 2014 at 06:51:24PM +0200, Radim Kr?m?? wrote:
> > Ok.
> > I've seen merit in pvqspinlock even with slightly slower
first-waiter,
> > so I would have happily sacrificed those horrible branches.
> > (I prefer elegant to optimized code, but I can see why we want to be
> >  strictly better than ticketlock.)
> > Peter mentioned that we are focusing on bare-metal patches, so
I'll
> > withold my other paravirt rants until they are polished.
(It was an ambiguous sentence, I have comments for later patches.)
> Well, paravirt must happen too, but comes later in this series, patch 3
> which we're replying to is still very much in the bare metal part of
the
> series.
(I think that bare metal spans the first 7 patches.)
> I've not had time yet to decode all that Waiman has done to make
> paravirt work.
> 
> But as a general rule I like patches that start with something simple
> and working and then optimize it, this series doesn't seem to quite
> grasp that.
> 
> > And to forcefully bring this thread a little bit on-topic:
> > 
> > Pending-bit is effectively a lock in a lock, so I was wondering why
> > don't we use more pending bits; advantages are the same, just
diminished
> > by the probability of having an ideally contended lock:
> >  - waiter won't be blocked on RAM access if critical section (or
more)
> >    ends sooner
> >  - some unlucky cacheline is not forgotten
> >  - faster unlock (no need for tail operations)
> > (- ?)
> > disadvantages are magnified:
> >  - increased complexity
> >  - intense cacheline sharing
> >    (I thought that this is the main disadvantage of ticketlock.)
> > (- ?)
> > 
> > One bit still improved performance, is it the best we got?
> 
> So, the advantage of one bit is that if we use a whole byte for 1 bit we
> can avoid some atomic ops.
> 
> The entire reason for this in-word spinner is to amortize the cost of
> hitting the external node cacheline.
Every pending CPU removes one length of the critical section from the
delay caused by cacheline propagation and really cold cache is
hundreds(?) of cycles, so we could burn some to ensure correctness and
still be waiting when the first pending CPU unlocks.
> So traditional locks like test-and-test and the ticket lock only ever
> access the spinlock word itsef, this MCS style queueing lock has a
> second (and, see my other rants in this thread, when done wrong more
> than 2) cacheline to touch.
> 
> That said, all our benchmarking is pretty much for the cache-hot case,
> so I'm not entirely convinced yet that the one pending bit makes up for
> it, it does in the cache-hot case.
Yeah, we probably use the faster pre-lock quite a lot.
Cover letter states that queue depth 1-3 is a bit slower than ticket
spinlock, so we might not be losing if we implemented a faster
in-word-lock of this capacity.  (Not that I'm a fan of the hybrid lock.)
> But... writing cache-cold benchmarks is _hard_ :/
Wouldn't clflush of the second cacheline before trying for the lock give
us a rough estimate?