From patchwork Tue Aug 28 09:57:56 2012 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Takuya Yoshikawa X-Patchwork-Id: 1379871 Return-Path: X-Original-To: patchwork-kvm@patchwork.kernel.org Delivered-To: patchwork-process-083081@patchwork1.kernel.org Received: from vger.kernel.org (vger.kernel.org [209.132.180.67]) by patchwork1.kernel.org (Postfix) with ESMTP id 6812F3FC71 for ; Tue, 28 Aug 2012 09:58:14 +0000 (UTC) Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S1752338Ab2H1J6K (ORCPT ); Tue, 28 Aug 2012 05:58:10 -0400 Received: from tama50.ecl.ntt.co.jp ([129.60.39.147]:53429 "EHLO tama50.ecl.ntt.co.jp" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S1752255Ab2H1J6J (ORCPT ); Tue, 28 Aug 2012 05:58:09 -0400 Received: from mfs6.rdh.ecl.ntt.co.jp (mfs6.rdh.ecl.ntt.co.jp [129.60.39.149]) by tama50.ecl.ntt.co.jp (8.13.8/8.13.8) with ESMTP id q7S9w52L016493; Tue, 28 Aug 2012 18:58:05 +0900 Received: from mfs6.rdh.ecl.ntt.co.jp (localhost.localdomain [127.0.0.1]) by mfs6.rdh.ecl.ntt.co.jp (Postfix) with ESMTP id 1CBC5E00D4; Tue, 28 Aug 2012 18:58:05 +0900 (JST) Received: from imail2.m.ecl.ntt.co.jp (imail2.m.ecl.ntt.co.jp [129.60.5.247]) by mfs6.rdh.ecl.ntt.co.jp (Postfix) with ESMTP id 10DCCE00D2; Tue, 28 Aug 2012 18:58:05 +0900 (JST) Received: from yshpad ([129.60.241.196]) by imail2.m.ecl.ntt.co.jp (8.13.8/8.13.8) with SMTP id q7S9w4OW009802; Tue, 28 Aug 2012 18:58:05 +0900 Date: Tue, 28 Aug 2012 18:57:56 +0900 From: Takuya Yoshikawa To: Marcelo Tosatti Cc: avi@redhat.com, kvm@vger.kernel.org Subject: Re: [PATCH] KVM: x86: lapic: Fix the misuse of likely() in find_highest_vector() Message-Id: <20120828185756.c754f4b4.yoshikawa.takuya@oss.ntt.co.jp> In-Reply-To: <20120827202542.GA1414@amt.cnet> References: <20120824181549.e1535ae0.yoshikawa.takuya@oss.ntt.co.jp> <20120827202542.GA1414@amt.cnet> X-Mailer: Sylpheed 3.1.0 (GTK+ 2.24.4; x86_64-pc-linux-gnu) Mime-Version: 1.0 Sender: kvm-owner@vger.kernel.org Precedence: bulk List-ID: X-Mailing-List: kvm@vger.kernel.org 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.) 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)