Re: [Xen-devel] [PATCH 3/9] x86/vmx: Factor locate_msr_entry() out of vmx_find_msr() and vmx_add_msr()

[Roger Pau Monné <roger.pau@xxxxxxxxxx>]

On Tue, May 22, 2018 at 12:20:40PM +0100, Andrew Cooper wrote:
> Instead of having multiple algorithms searching the MSR lists, implement a
> single one.  It has the semantics required by vmx_add_msr(), to identify the
> position in which an MSR should live, if it isn't already present.
> 
> There will be a marginal improvement for vmx_find_msr() by avoiding the
> function pointer calls to vmx_msr_entry_key_cmp(), and a major improvement for
> vmx_add_msr() by using a binary search instead of a linear search.
> 
> Signed-off-by: Andrew Cooper <andrew.cooper3@xxxxxxxxxx>
> ---
> CC: Jan Beulich <JBeulich@xxxxxxxx>
> CC: Jun Nakajima <jun.nakajima@xxxxxxxxx>
> CC: Kevin Tian <kevin.tian@xxxxxxxxx>
> CC: Wei Liu <wei.liu2@xxxxxxxxxx>
> CC: Roger Pau Monné <roger.pau@xxxxxxxxxx>
> ---
>  xen/arch/x86/hvm/vmx/vmcs.c | 42 ++++++++++++++++++++++++++++--------------
>  1 file changed, 28 insertions(+), 14 deletions(-)
> 
> diff --git a/xen/arch/x86/hvm/vmx/vmcs.c b/xen/arch/x86/hvm/vmx/vmcs.c
> index f557857..e4acdc1 100644
> --- a/xen/arch/x86/hvm/vmx/vmcs.c
> +++ b/xen/arch/x86/hvm/vmx/vmcs.c
> @@ -1276,24 +1276,36 @@ static int construct_vmcs(struct vcpu *v)
>      return 0;
>  }
>  
> -static int vmx_msr_entry_key_cmp(const void *key, const void *elt)
> +/*
> + * Search an MSR list looking for an MSR entry, or the slot in which it 
> should
> + * live (to keep the data sorted) if an entry is not found.
> + *
> + * The return pointer is guarenteed to be bounded by start and end.  However,
> + * it may point at end, and may be invalid for the caller to dereference.
> + */
> +static struct vmx_msr_entry *locate_msr_entry(
> +    struct vmx_msr_entry *start, struct vmx_msr_entry *end, uint32_t msr)
>  {
> -    const u32 *msr = key;
> -    const struct vmx_msr_entry *entry = elt;
> +    while ( start < end )
> +    {
> +        struct vmx_msr_entry *mid = start + (end - start) / 2;
>  
> -    if ( *msr > entry->index )
> -        return 1;
> -    if ( *msr < entry->index )
> -        return -1;
> +        if ( msr < mid->index )
> +            end = mid;
> +        else if ( msr > mid->index )
> +            start = mid + 1;
> +        else
> +            return mid;
> +    }

This is basically an open coded version of bsearch, isn't there anyway
to adapt the current bsearch so that it could be used for both
vmx_find_msr and vmx_add_msr?

I know there will be a performance penalty for using a function
pointer for the comparator function, but this looks like code
duplication to me.

Thanks, Roger.

_______________________________________________
Xen-devel mailing list
Xen-devel@xxxxxxxxxxxxxxxxxxxx
https://lists.xenproject.org/mailman/listinfo/xen-devel