From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S1753391AbdKGTlu (ORCPT ); Tue, 7 Nov 2017 14:41:50 -0500 Received: from merlin.infradead.org ([205.233.59.134]:36804 "EHLO merlin.infradead.org" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S1753176AbdKGTlt (ORCPT ); Tue, 7 Nov 2017 14:41:49 -0500 Date: Tue, 7 Nov 2017 20:41:42 +0100 From: Peter Zijlstra To: Waiman Long Cc: Ingo Molnar , linux-kernel@vger.kernel.org, Paolo Bonzini , Juergen Gross , Radim =?utf-8?B?S3LEjW3DocWZ?= , Boris Ostrovsky Subject: Re: [PATCH] locking/pvqspinlock: Hybrid PV queued/unfair locks Message-ID: <20171107194142.GQ3165@worktop.lehotels.local> References: <1509723331-10469-1-git-send-email-longman@redhat.com> <20171107125843.GM3165@worktop.lehotels.local> MIME-Version: 1.0 Content-Type: text/plain; charset=us-ascii Content-Disposition: inline In-Reply-To: User-Agent: Mutt/1.5.22.1 (2013-10-16) Sender: linux-kernel-owner@vger.kernel.org List-ID: X-Mailing-List: linux-kernel@vger.kernel.org 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.