From mboxrd@z Thu Jan 1 00:00:00 1970 From: Marcelo Tosatti Subject: Re: [PATCH] KVM: x86: lapic: Fix the misuse of likely() in find_highest_vector() Date: Wed, 29 Aug 2012 16:10:57 -0300 Message-ID: <20120829191057.GA10834@amt.cnet> References: <20120824181549.e1535ae0.yoshikawa.takuya@oss.ntt.co.jp> <20120827202542.GA1414@amt.cnet> <20120828185756.c754f4b4.yoshikawa.takuya@oss.ntt.co.jp> Mime-Version: 1.0 Content-Type: text/plain; charset=us-ascii Cc: avi@redhat.com, kvm@vger.kernel.org To: Takuya Yoshikawa , "Michael S. Tsirkin" Return-path: Received: from mx1.redhat.com ([209.132.183.28]:15712 "EHLO mx1.redhat.com" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S1754528Ab2H2TLE (ORCPT ); Wed, 29 Aug 2012 15:11:04 -0400 Content-Disposition: inline In-Reply-To: <20120828185756.c754f4b4.yoshikawa.takuya@oss.ntt.co.jp> Sender: kvm-owner@vger.kernel.org List-ID: On Tue, Aug 28, 2012 at 06:57:56PM +0900, Takuya Yoshikawa wrote: > On Mon, 27 Aug 2012 17:25:42 -0300 > Marcelo Tosatti wrote: > > > On Fri, Aug 24, 2012 at 06:15:49PM +0900, Takuya Yoshikawa wrote: > > > Although returning -1 should be likely according to the likely(), > > > the ASSERT in apic_find_highest_irr() will be triggered in such a case. > > > It seems that this optimization is not working as expected. > > > > > > This patch simplifies the logic to mitigate this issue: search for the > > > first non-zero word in a for loop and then use __fls() if found. When > > > nothing found, we are out of the loop, so we can just return -1. > > > > Numbers please? > > > How about this? > (It would be great if someone help me understand why I got the numbers.) Michael, can you explain the reasoning? > Subject: [PATCH -v2] KVM: x86: lapic: Fix the misuse of likely() in find_highest_vector() > > Although returning -1 should be likely according to the likely(), not > all callers expect such a result: > > Call sites: > - apic_search_irr() > - apic_find_highest_irr() --> ASSERT(result == -1 || result >= 16); > - apic_clear_irr() > - apic_find_highest_isr() --> ASSERT(result == -1 || result >= 16); > > The likely() might have made sense if returning -1 in apic_clear_irr() > dominated the usage. But what I saw, by inserting counters in > find_highest_vector(), was not like that: > > When the guest was being booted up, the counter for the "likely" case > alone increased rapidly and exceeded 1,000,000. Then, after the guest > booted up, the other cases started to happen and the "likely"/"others" > ratio was between 1/4 to 1/3. Especially when ping from the guest to > host was running, this was very clear: > > * NOT FOUND : "likely" (return -1) > * WORD FOUND: "others" > * printed when counter % 1000 == 0 > > [ 3566.796755] KVM: find_highest_vector: WORD FOUND 1707000 > [ 3573.716623] KVM: find_highest_vector: WORD FOUND 1708000 > [ 3575.666378] KVM: find_highest_vector: WORD FOUND 1709000 > [ 3580.514253] KVM: find_highest_vector: NOT FOUND 1574000 > [ 3586.763738] KVM: find_highest_vector: WORD FOUND 1710000 > [ 3593.506674] KVM: find_highest_vector: WORD FOUND 1711000 > [ 3595.766714] KVM: find_highest_vector: WORD FOUND 1712000 > [ 3600.523654] KVM: find_highest_vector: NOT FOUND 1575000 > [ 3607.485739] KVM: find_highest_vector: WORD FOUND 1713000 > [ 3614.009400] KVM: find_highest_vector: WORD FOUND 1714000 > [ 3616.669787] KVM: find_highest_vector: WORD FOUND 1715000 > [ 3620.971443] KVM: find_highest_vector: NOT FOUND 1576000 > > This result shows that the likely() was not likely at all after the > guest booted up. > > This patch simplifies the code to mitigate this issue: search for the > first non-zero word in a for loop and then use __fls() if found. When > nothing found, we are out of the loop, so we can just return -1. > > With this patch applied, even when we see successive "not found", CPU > will predict things much better than us. > > Signed-off-by: Takuya Yoshikawa > --- > arch/x86/kvm/lapic.c | 18 ++++++++++-------- > 1 files changed, 10 insertions(+), 8 deletions(-) > > diff --git a/arch/x86/kvm/lapic.c b/arch/x86/kvm/lapic.c > index 18d149d..5eb4dde 100644 > --- a/arch/x86/kvm/lapic.c > +++ b/arch/x86/kvm/lapic.c > @@ -208,16 +208,18 @@ static unsigned int apic_lvt_mask[APIC_LVT_NUM] = { > > static int find_highest_vector(void *bitmap) > { > - u32 *word = bitmap; > - int word_offset = MAX_APIC_VECTOR >> 5; > + u32 *p = bitmap; > + u32 word; > + int word_offset; > > - while ((word_offset != 0) && (word[(--word_offset) << 2] == 0)) > - continue; > + for (word_offset = (MAX_APIC_VECTOR >> 5) - 1; > + word_offset >= 0; --word_offset) { > + word = p[word_offset << 2]; > + if (word) > + return __fls(word) + (word_offset << 5); > + } > > - if (likely(!word_offset && !word[0])) > - return -1; > - else > - return fls(word[word_offset << 2]) - 1 + (word_offset << 5); > + return -1; > } > > static u8 count_vectors(void *bitmap) > -- > 1.7.5.4 > > -- > To unsubscribe from this list: send the line "unsubscribe kvm" in > the body of a message to majordomo@vger.kernel.org > More majordomo info at http://vger.kernel.org/majordomo-info.html