linux-kernel - Re: [PATCH] locking/pvqspinlock: Hybrid PV queued/unfair locks

lists.openwall.net		lists / announce owl-users owl-dev john-users john-dev passwdqc-users yescrypt popa3d-users / oss-security kernel-hardening musl sabotage tlsify passwords / crypt-dev xvendor / Bugtraq Full-Disclosure linux-kernel linux-netdev linux-ext4 linux-hardening linux-cve-announce PHC
Open Source and information security mailing list archives

Hash Suite: Windows password security audit tool. GUI, reports in PDF.

[<prev] [next>] [<thread-prev] [thread-next>] [day] [month] [year] [list]

Message-ID: <20171107194142.GQ3165@worktop.lehotels.local>
Date:   Tue, 7 Nov 2017 20:41:42 +0100
From:   Peter Zijlstra <peterz@...radead.org>
To:     Waiman Long <longman@...hat.com>
Cc:     Ingo Molnar <mingo@...hat.com>, linux-kernel@...r.kernel.org,
        Paolo Bonzini <pbonzini@...hat.com>,
        Juergen Gross <jgross@...e.com>,
        Radim Krčmář <rkrcmar@...hat.com>,
        Boris Ostrovsky <boris.ostrovsky@...cle.com>
Subject: Re: [PATCH] locking/pvqspinlock: Hybrid PV queued/unfair locks

On Tue, Nov 07, 2017 at 11:39:02AM -0500, Waiman Long wrote:
> On 11/07/2017 07:58 AM, Peter Zijlstra wrote:
> > On Fri, Nov 03, 2017 at 11:35:31AM -0400, Waiman Long wrote:

> >> This patch combines the best attributes of an unfair lock and a
> >> pvqspinlock into a hybrid lock with 2 modes - queued mode & unfair
> >> mode. A lock waiter goes into the unfair mode when there are waiters
> >> in the wait queue but the pending bit isn't set. Otherwise, it will
> >> go into the queued mode waiting in the queue for its turn.

> > You forgot to test a starvation case. And you also forgot to describe
> > how they cannot happen. I really cannot remember how all this is
> > supposed to work.
> 
> Lock starvation shouldn't happen. The pending bit is set by the queue
> head to indicate its readiness before spinning on the lock. Once the
> pending bit is made visible to all the CPUs, no one can steal the lock
> and they will all queued up in the wait queue.

So the queue path of queued_spin_lock_slowpath() does
queued_spin_trylock() which, for PV, ends up being that
pv_queued_spin_steal_lock(), which you changed to spin util PENDING.

Now PENDING is set by pv_wait_head_or_lock(), but that is far after
queued_spin_trylock().

The way I'm reading this is that we'll never get there... because we'll
all be spinning in pv_queued_spin_steal_lock().

So how will we fail pv_queued_spin_steal_lock() in order to then end up
in pv_wait_head_or_lock() to set PENDING such that
pv_queued_spin_steal_lock() will fail?

The comment with your new pv_queued_spin_steal_lock() should very
clearly spell out how this works.

> I ran my locking microbenchmark on a 2-socket 36-core system (HT off)
> with # of locking threads equals to the number of vCPUs in a kvm VM. The
> table below show the the min/mean/max per-thread locking ops done in 5
> seconds:
> 
> #vCPUs    min/avg/max lockops
> 36            822,135/881,063/950,363
> 54            542,435/581,664/625,937
> 72            397,500/428,177/499,299
> 
> It is obvious that there was no lock starvation here.

It is however not obvious if that is the worst case; at the very least
you should compare to the test-and-set variant which has known
starvation. If this test doesn't show starvation with the test-and-set
then this test is bad.