LKML Archive on lore.kernel.org
help / color / mirror / Atom feed
From: Waiman Long <waiman.long@hp.com>
To: Peter Zijlstra <peterz@infradead.org>
Cc: tglx@linutronix.de, mingo@redhat.com, hpa@zytor.com,
	paolo.bonzini@gmail.com, konrad.wilk@oracle.com,
	boris.ostrovsky@oracle.com, paulmck@linux.vnet.ibm.com,
	riel@redhat.com, torvalds@linux-foundation.org,
	raghavendra.kt@linux.vnet.ibm.com, david.vrabel@citrix.com,
	oleg@redhat.com, scott.norton@hp.com, doug.hatch@hp.com,
	linux-arch@vger.kernel.org, x86@kernel.org,
	linux-kernel@vger.kernel.org,
	virtualization@lists.linux-foundation.org,
	xen-devel@lists.xenproject.org, kvm@vger.kernel.org,
	luto@amacapital.net
Subject: Re: [PATCH 8/9] qspinlock: Generic paravirt support
Date: Wed, 01 Apr 2015 15:58:58 -0400	[thread overview]
Message-ID: <551C4E02.8030806@hp.com> (raw)
In-Reply-To: <20150401184858.GA9791@dyad.arnhem.chello.nl>

On 04/01/2015 02:48 PM, Peter Zijlstra wrote:
> On Wed, Apr 01, 2015 at 02:54:45PM -0400, Waiman Long wrote:
>> On 04/01/2015 02:17 PM, Peter Zijlstra wrote:
>>> On Wed, Apr 01, 2015 at 07:42:39PM +0200, Peter Zijlstra wrote:
>>>>> Hohumm.. time to think more I think ;-)
>>>> So bear with me, I've not really pondered this well so it could be full
>>>> of holes (again).
>>>>
>>>> After the cmpxchg(&l->locked, _Q_LOCKED_VAL, _Q_SLOW_VAL) succeeds the
>>>> spin_unlock() must do the hash lookup, right? We can make the lookup
>>>> unhash.
>>>>
>>>> If the cmpxchg() fails the unlock will not do the lookup and we must
>>>> unhash.
>>> The idea being that the result is that any lookup is guaranteed to find
>>> an entry, which reduces our worst case lookup cost to whatever the worst
>>> case insertion cost was.
>>>
>> I think it doesn't matter who did the unhashing. Multiple independent locks
>> can be hashed to the same value. Since they can be unhashed independently,
>> there is no way to know whether you have checked all the possible buckets.
> oh but the crux is that you guarantee a lookup will find an entry. it will
> never need to iterate the entire array.

I am sorry that I don't quite get what you mean here. My point is that 
in the hashing step, a cpu will need to scan an empty bucket to put the 
lock in. In the interim, an previously used bucket before the empty one 
may get freed. In the lookup step for that lock, the scanning will stop 
because of an empty bucket in front of the target one.

-Longman

  reply	other threads:[~2015-04-01 19:59 UTC|newest]

Thread overview: 43+ messages / expand[flat|nested]  mbox.gz  Atom feed  top
2015-03-16 13:16 [PATCH 0/9] qspinlock stuff -v15 Peter Zijlstra
2015-03-16 13:16 ` [PATCH 1/9] qspinlock: A simple generic 4-byte queue spinlock Peter Zijlstra
2015-03-16 13:16 ` [PATCH 2/9] qspinlock, x86: Enable x86-64 to use " Peter Zijlstra
2015-03-16 13:16 ` [PATCH 3/9] qspinlock: Add pending bit Peter Zijlstra
2015-03-16 13:16 ` [PATCH 4/9] qspinlock: Extract out code snippets for the next patch Peter Zijlstra
2015-03-16 13:16 ` [PATCH 5/9] qspinlock: Optimize for smaller NR_CPUS Peter Zijlstra
2015-03-16 13:16 ` [PATCH 6/9] qspinlock: Use a simple write to grab the lock Peter Zijlstra
2015-03-16 13:16 ` [PATCH 7/9] qspinlock: Revert to test-and-set on hypervisors Peter Zijlstra
2015-03-16 13:16 ` [PATCH 8/9] qspinlock: Generic paravirt support Peter Zijlstra
     [not found]   ` <5509E51D.7040909@hp.com>
2015-03-19 10:12     ` Peter Zijlstra
2015-03-19 12:25       ` Peter Zijlstra
2015-03-19 13:43         ` Peter Zijlstra
2015-03-19 23:25         ` Waiman Long
2015-04-01 16:20         ` Waiman Long
2015-04-01 17:12           ` Peter Zijlstra
2015-04-01 17:42             ` Peter Zijlstra
2015-04-01 18:17               ` Peter Zijlstra
2015-04-01 18:54                 ` Waiman Long
2015-04-01 18:48                   ` Peter Zijlstra
2015-04-01 19:58                     ` Waiman Long [this message]
2015-04-01 21:03                       ` Peter Zijlstra
2015-04-02 16:28                         ` Waiman Long
2015-04-02 17:20                           ` Peter Zijlstra
2015-04-02 19:48                             ` Peter Zijlstra
2015-04-03  3:39                               ` Waiman Long
2015-04-03 13:43                               ` Peter Zijlstra
2015-04-01 20:10             ` Waiman Long
2015-03-16 13:16 ` [PATCH 9/9] qspinlock,x86,kvm: Implement KVM support for paravirt qspinlock Peter Zijlstra
     [not found]   ` <550A3863.2060808@hp.com>
2015-03-19 10:01     ` Peter Zijlstra
2015-03-19 21:08       ` Waiman Long
2015-03-20  7:43         ` Raghavendra K T
2015-03-16 14:08 ` [Xen-devel] [PATCH 0/9] qspinlock stuff -v15 David Vrabel
2015-03-18 20:36 ` Waiman Long
2015-03-19 18:01 ` [Xen-devel] " David Vrabel
2015-03-19 18:32   ` Peter Zijlstra
2015-03-25 19:47 ` Konrad Rzeszutek Wilk
2015-03-26 20:21   ` Peter Zijlstra
2015-03-27 14:07     ` Konrad Rzeszutek Wilk
2015-03-30 16:41       ` Waiman Long
2015-03-30 16:25   ` Waiman Long
2015-03-30 16:29     ` Peter Zijlstra
2015-03-30 16:43       ` Waiman Long
2015-03-27  6:40 ` Raghavendra K T

Reply instructions:

You may reply publicly to this message via plain-text email
using any one of the following methods:

* Save the following mbox file, import it into your mail client,
  and reply-to-all from there: mbox

  Avoid top-posting and favor interleaved quoting:
  https://en.wikipedia.org/wiki/Posting_style#Interleaved_style

* Reply using the --to, --cc, and --in-reply-to
  switches of git-send-email(1):

  git send-email \
    --in-reply-to=551C4E02.8030806@hp.com \
    --to=waiman.long@hp.com \
    --cc=boris.ostrovsky@oracle.com \
    --cc=david.vrabel@citrix.com \
    --cc=doug.hatch@hp.com \
    --cc=hpa@zytor.com \
    --cc=konrad.wilk@oracle.com \
    --cc=kvm@vger.kernel.org \
    --cc=linux-arch@vger.kernel.org \
    --cc=linux-kernel@vger.kernel.org \
    --cc=luto@amacapital.net \
    --cc=mingo@redhat.com \
    --cc=oleg@redhat.com \
    --cc=paolo.bonzini@gmail.com \
    --cc=paulmck@linux.vnet.ibm.com \
    --cc=peterz@infradead.org \
    --cc=raghavendra.kt@linux.vnet.ibm.com \
    --cc=riel@redhat.com \
    --cc=scott.norton@hp.com \
    --cc=tglx@linutronix.de \
    --cc=torvalds@linux-foundation.org \
    --cc=virtualization@lists.linux-foundation.org \
    --cc=x86@kernel.org \
    --cc=xen-devel@lists.xenproject.org \
    --subject='Re: [PATCH 8/9] qspinlock: Generic paravirt support' \
    /path/to/YOUR_REPLY

  https://kernel.org/pub/software/scm/git/docs/git-send-email.html

* If your mail client supports setting the In-Reply-To header
  via mailto: links, try the mailto: link

This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for NNTP newsgroup(s).