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

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

On Thu, Aug 30, 2012 at 09:30:19PM +0900, Takuya Yoshikawa wrote:
> find_highest_vector() and count_vectors():
>  - Instead of using magic values, define and use proper interfaces
>    to access registers.
> 
> 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 __fls(), not fls(), since we have checked the value passed to it
>    is not zero.
> 
>  - 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>
> ---
>  arch/x86/kvm/lapic.c |   35 +++++++++++++++++++++++------------
>  1 files changed, 23 insertions(+), 12 deletions(-)
> 
> diff --git a/arch/x86/kvm/lapic.c b/arch/x86/kvm/lapic.c
> index 18d149d..e44b8ab 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)
> @@ -78,6 +79,11 @@ static inline void apic_set_reg(struct kvm_lapic *apic, int reg_off, u32 val)
>  	*((u32 *) (apic->regs + reg_off)) = val;
>  }
>  
> +static u32 apic_read_reg(int reg_off, void *bitmap)
> +{
> +	return *((u32 *)(bitmap + reg_off));
> +}
> +

Contrast with apic_set_reg which gets apic,
add fact that all callers invoke REG_POS and you will
see this is a bad API.

I played with some APIs but in the end it's
probably better to just open-code this.

As a bonus, open-coding will avoid the need
for cast above, which is good: casts make code more
fragile.

>  static inline int apic_test_and_set_vector(int vec, void *bitmap)
>  {
>  	return test_and_set_bit(VEC_POS(vec), (bitmap) + REG_POS(vec));
> @@ -208,25 +214,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 = apic_read_reg(REG_POS(vec), bitmap);
> +		if (reg)
> +			return __fls(reg) + 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 = apic_read_reg(REG_POS(vec), bitmap);
> +		count += hweight32(reg);
> +	}
> +
>  	return count;
>  }
>  
> -- 
> 1.7.5.4