Re: [PATCH -v4] KVM: x86: lapic: Clean up find_highest_vector() and count_vectors()

["Michael S. Tsirkin" <mst@redhat.com>]

On Wed, Sep 05, 2012 at 07:30:01PM +0900, Takuya Yoshikawa wrote:
> find_highest_vector() and count_vectors():
>  - Instead of using magic values, define and use proper macros.
> 
> find_highest_vector():
>  - Remove likely() which is there only for historical reasons and not
>    doing correct branch predictions anymore.  Using such heuristics
>    to optimize this function is not worth it now.  Let CPUs predict
>    things instead.
> 
>  - Stop checking word[0] separately.  This was only needed for doing
>    likely() optimization.
> 
>  - Use for loop, not while, to iterate over the register array to make
>    the code clearer.
> 
> Note that we actually confirmed that the likely() did wrong predictions
> by inserting debug code.
> 
> Signed-off-by: Takuya Yoshikawa <yoshikawa.takuya@oss.ntt.co.jp>
> Cc: Michael S. Tsirkin <mst@redhat.com>

Looks like a nice cleanup.
Acked-by: Michael S. Tsirkin <mst@redhat.com>


> ---
>  arch/x86/kvm/lapic.c |   30 ++++++++++++++++++------------
>  1 files changed, 18 insertions(+), 12 deletions(-)
> 
> diff --git a/arch/x86/kvm/lapic.c b/arch/x86/kvm/lapic.c
> index 18d149d..8ace252 100644
> --- a/arch/x86/kvm/lapic.c
> +++ b/arch/x86/kvm/lapic.c
> @@ -66,6 +66,7 @@
>  #define APIC_DEST_NOSHORT		0x0
>  #define APIC_DEST_MASK			0x800
>  #define MAX_APIC_VECTOR			256
> +#define APIC_VECTORS_PER_REG		32
>  
>  #define VEC_POS(v) ((v) & (32 - 1))
>  #define REG_POS(v) (((v) >> 5) << 4)
> @@ -208,25 +209,30 @@ 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;
> +	int vec;
> +	u32 *reg;
>  
> -	while ((word_offset != 0) && (word[(--word_offset) << 2] == 0))
> -		continue;
> +	for (vec = MAX_APIC_VECTOR - APIC_VECTORS_PER_REG;
> +	     vec >= 0; vec -= APIC_VECTORS_PER_REG) {
> +		reg = bitmap + REG_POS(vec);
> +		if (*reg)
> +			return fls(*reg) - 1 + vec;
> +	}
>  
> -	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)
>  {
> -	u32 *word = bitmap;
> -	int word_offset;
> +	int vec;
> +	u32 *reg;
>  	u8 count = 0;
> -	for (word_offset = 0; word_offset < MAX_APIC_VECTOR >> 5; ++word_offset)
> -		count += hweight32(word[word_offset << 2]);
> +
> +	for (vec = 0; vec < MAX_APIC_VECTOR; vec += APIC_VECTORS_PER_REG) {
> +		reg = bitmap + REG_POS(vec);
> +		count += hweight32(*reg);
> +	}
> +
>  	return count;
>  }
>  
> -- 
> 1.7.5.4