From: Peter Zijlstra <peterz@infradead.org> To: Waiman Long <waiman.long@hp.com> 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, 1 Apr 2015 23:03:17 +0200 [thread overview] Message-ID: <20150401210317.GZ27490@worktop.programming.kicks-ass.net> (raw) In-Reply-To: <551C4E02.8030806@hp.com> On Wed, Apr 01, 2015 at 03:58:58PM -0400, Waiman Long wrote: > On 04/01/2015 02:48 PM, Peter Zijlstra wrote: > 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. Right, that's broken. So we need to do something else to limit the lookup, because without that break, a lookup that needs to iterate the entire array in order to determine -ENOENT, which is expensive. So my alternative proposal is that IFF we can guarantee that every lookup will succeed -- the entry we're looking for is always there, we don't need the break on empty but can probe until we find the entry. This will be bound in cost to the same number if probes we required for insertion and avoids the full array scan. Now I think we can indeed do this, if as said earlier we do not clear the bucket on insert if the cmpxchg succeeds, in that case the unlock will observe _Q_SLOW_VAL and do the lookup, the lookup will then find the entry. And we then need the unlock to clear the entry. Does that explain this? Or should I try again with code?
WARNING: multiple messages have this Message-ID (diff)
From: Peter Zijlstra <peterz@infradead.org> To: Waiman Long <waiman.long@hp.com> Cc: linux-arch@vger.kernel.org, riel@redhat.com, x86@kernel.org, kvm@vger.kernel.org, konrad.wilk@oracle.com, scott.norton@hp.com, raghavendra.kt@linux.vnet.ibm.com, paolo.bonzini@gmail.com, oleg@redhat.com, linux-kernel@vger.kernel.org, mingo@redhat.com, david.vrabel@citrix.com, hpa@zytor.com, luto@amacapital.net, xen-devel@lists.xenproject.org, tglx@linutronix.de, paulmck@linux.vnet.ibm.com, torvalds@linux-foundation.org, boris.ostrovsky@oracle.com, virtualization@lists.linux-foundation.org, doug.hatch@hp.com Subject: Re: [PATCH 8/9] qspinlock: Generic paravirt support Date: Wed, 1 Apr 2015 23:03:17 +0200 [thread overview] Message-ID: <20150401210317.GZ27490@worktop.programming.kicks-ass.net> (raw) In-Reply-To: <551C4E02.8030806@hp.com> On Wed, Apr 01, 2015 at 03:58:58PM -0400, Waiman Long wrote: > On 04/01/2015 02:48 PM, Peter Zijlstra wrote: > 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. Right, that's broken. So we need to do something else to limit the lookup, because without that break, a lookup that needs to iterate the entire array in order to determine -ENOENT, which is expensive. So my alternative proposal is that IFF we can guarantee that every lookup will succeed -- the entry we're looking for is always there, we don't need the break on empty but can probe until we find the entry. This will be bound in cost to the same number if probes we required for insertion and avoids the full array scan. Now I think we can indeed do this, if as said earlier we do not clear the bucket on insert if the cmpxchg succeeds, in that case the unlock will observe _Q_SLOW_VAL and do the lookup, the lookup will then find the entry. And we then need the unlock to clear the entry. Does that explain this? Or should I try again with code?
next prev parent reply other threads:[~2015-04-01 21:03 UTC|newest] Thread overview: 135+ 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 ` 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 ` Peter Zijlstra 2015-03-16 13:16 ` Peter Zijlstra 2015-03-16 13:16 ` [PATCH 2/9] qspinlock, x86: Enable x86-64 to use " Peter Zijlstra 2015-03-16 13:16 ` Peter Zijlstra 2015-03-16 13:16 ` Peter Zijlstra 2015-03-16 13:16 ` [PATCH 3/9] qspinlock: Add pending bit Peter Zijlstra 2015-03-16 13:16 ` Peter Zijlstra 2015-03-16 13:16 ` 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 ` Peter Zijlstra 2015-03-16 13:16 ` Peter Zijlstra 2015-03-16 13:16 ` [PATCH 5/9] qspinlock: Optimize for smaller NR_CPUS Peter Zijlstra 2015-03-16 13:16 ` Peter Zijlstra 2015-03-16 13:16 ` 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 ` Peter Zijlstra 2015-03-16 13:16 ` 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 ` Peter Zijlstra 2015-03-16 13:16 ` Peter Zijlstra 2015-03-16 13:16 ` [PATCH 8/9] qspinlock: Generic paravirt support Peter Zijlstra 2015-03-16 13:16 ` Peter Zijlstra 2015-03-18 20:50 ` Waiman Long 2015-03-19 10:12 ` Peter Zijlstra 2015-03-19 10:12 ` Peter Zijlstra 2015-03-19 10:12 ` Peter Zijlstra 2015-03-19 12:25 ` Peter Zijlstra 2015-03-19 12:25 ` Peter Zijlstra 2015-03-19 13:43 ` Peter Zijlstra 2015-03-19 13:43 ` Peter Zijlstra 2015-03-19 13:43 ` Peter Zijlstra 2015-03-19 23:25 ` Waiman Long 2015-03-19 23:25 ` Waiman Long 2015-03-19 23:25 ` Waiman Long 2015-04-01 16:20 ` Waiman Long 2015-04-01 16:20 ` Waiman Long 2015-04-01 16:20 ` Waiman Long 2015-04-01 17:12 ` Peter Zijlstra 2015-04-01 17:12 ` Peter Zijlstra 2015-04-01 17:12 ` Peter Zijlstra 2015-04-01 17:42 ` Peter Zijlstra 2015-04-01 17:42 ` Peter Zijlstra 2015-04-01 18:17 ` Peter Zijlstra 2015-04-01 18:17 ` Peter Zijlstra 2015-04-01 18:54 ` Waiman Long 2015-04-01 18:54 ` Waiman Long 2015-04-01 18:48 ` Peter Zijlstra 2015-04-01 18:48 ` Peter Zijlstra 2015-04-01 19:58 ` Waiman Long 2015-04-01 21:03 ` Peter Zijlstra 2015-04-01 21:03 ` Peter Zijlstra [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 17:20 ` Peter Zijlstra 2015-04-02 19:48 ` Peter Zijlstra 2015-04-02 19:48 ` Peter Zijlstra 2015-04-03 3:39 ` Waiman Long 2015-04-03 3:39 ` Waiman Long 2015-04-03 3:39 ` Waiman Long 2015-04-03 13:43 ` Peter Zijlstra 2015-04-03 13:43 ` Peter Zijlstra 2015-04-03 13:43 ` Peter Zijlstra 2015-04-02 19:48 ` Peter Zijlstra 2015-04-02 17:20 ` Peter Zijlstra 2015-04-02 16:28 ` Waiman Long 2015-04-02 16:28 ` Waiman Long 2015-04-01 19:58 ` Waiman Long 2015-04-01 19:58 ` Waiman Long 2015-04-01 18:48 ` Peter Zijlstra 2015-04-01 18:54 ` Waiman Long 2015-04-01 18:17 ` Peter Zijlstra 2015-04-01 17:42 ` Peter Zijlstra 2015-04-01 20:10 ` Waiman Long 2015-04-01 20:10 ` Waiman Long 2015-04-01 20:10 ` Waiman Long 2015-03-19 12:25 ` Peter Zijlstra 2015-03-18 20:50 ` Waiman Long 2015-03-16 13:16 ` Peter Zijlstra 2015-03-16 13:16 ` [PATCH 9/9] qspinlock, x86, kvm: Implement KVM support for paravirt qspinlock Peter Zijlstra 2015-03-16 13:16 ` [PATCH 9/9] qspinlock,x86,kvm: " Peter Zijlstra 2015-03-16 13:16 ` [PATCH 9/9] qspinlock, x86, kvm: " Peter Zijlstra 2015-03-19 2:45 ` Waiman Long 2015-03-19 10:01 ` Peter Zijlstra 2015-03-19 10:01 ` [PATCH 9/9] qspinlock,x86,kvm: " Peter Zijlstra 2015-03-19 10:01 ` Peter Zijlstra 2015-03-19 21:08 ` [PATCH 9/9] qspinlock, x86, kvm: " Waiman Long 2015-03-19 21:08 ` [PATCH 9/9] qspinlock,x86,kvm: " Waiman Long 2015-03-19 21:08 ` [PATCH 9/9] qspinlock, x86, kvm: " Waiman Long 2015-03-20 7:43 ` Raghavendra K T 2015-03-20 7:43 ` [PATCH 9/9] qspinlock,x86,kvm: " Raghavendra K T 2015-03-20 7:43 ` [PATCH 9/9] qspinlock, x86, kvm: " Raghavendra K T 2015-03-19 2:45 ` Waiman Long 2015-03-16 14:08 ` [PATCH 0/9] qspinlock stuff -v15 David Vrabel 2015-03-16 14:08 ` [Xen-devel] " David Vrabel 2015-03-16 14:08 ` David Vrabel 2015-03-16 14:08 ` David Vrabel 2015-03-16 14:08 ` David Vrabel 2015-03-18 20:36 ` Waiman Long 2015-03-18 20:36 ` Waiman Long 2015-03-18 20:36 ` Waiman Long 2015-03-19 18:01 ` [Xen-devel] " David Vrabel 2015-03-19 18:01 ` David Vrabel 2015-03-19 18:01 ` David Vrabel 2015-03-19 18:32 ` Peter Zijlstra 2015-03-19 18:32 ` Peter Zijlstra 2015-03-19 18:32 ` Peter Zijlstra 2015-03-19 18:01 ` David Vrabel 2015-03-25 19:47 ` Konrad Rzeszutek Wilk 2015-03-26 20:21 ` Peter Zijlstra 2015-03-26 20:21 ` Peter Zijlstra 2015-03-26 20:21 ` Peter Zijlstra 2015-03-27 14:07 ` Konrad Rzeszutek Wilk 2015-03-27 14:07 ` Konrad Rzeszutek Wilk 2015-03-27 14:07 ` Konrad Rzeszutek Wilk 2015-03-30 16:41 ` Waiman Long 2015-03-30 16:41 ` Waiman Long 2015-03-30 16:41 ` Waiman Long 2015-03-30 16:25 ` Waiman Long 2015-03-30 16:25 ` Waiman Long 2015-03-30 16:29 ` Peter Zijlstra 2015-03-30 16:29 ` Peter Zijlstra 2015-03-30 16:43 ` Waiman Long 2015-03-30 16:43 ` Waiman Long 2015-03-30 16:43 ` Waiman Long 2015-03-30 16:29 ` Peter Zijlstra 2015-03-30 16:25 ` Waiman Long 2015-03-25 19:47 ` Konrad Rzeszutek Wilk 2015-03-25 19:47 ` Konrad Rzeszutek Wilk 2015-03-27 6:40 ` Raghavendra K T 2015-03-27 6:40 ` Raghavendra K T 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=20150401210317.GZ27490@worktop.programming.kicks-ass.net \ --to=peterz@infradead.org \ --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=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=waiman.long@hp.com \ --cc=x86@kernel.org \ --cc=xen-devel@lists.xenproject.org \ /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: linkBe sure your reply has a Subject: header at the top and a blank line before the message body.
This is an external index of several public inboxes, see mirroring instructions on how to clone and mirror all data and code used by this external index.