> From: Andrew Cooper [mailto:andrew.coop...@citrix.com]
> Sent: Tuesday, May 22, 2018 7:21 PM
>
> 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.coop...@citrix.com>
Acked-by: Kevin Tian <kevin.t...@intel.com>, with one typo found:
> ---
> CC: Jan Beulich <jbeul...@suse.com>
> CC: Jun Nakajima <jun.nakaj...@intel.com>
> CC: Kevin Tian <kevin.t...@intel.com>
> CC: Wei Liu <wei.l...@citrix.com>
> CC: Roger Pau Monné <roger....@citrix.com>
> ---
> 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.
guaranteed
> 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;
> + }
>
> - return 0;
> + return start;
> }
>
> struct vmx_msr_entry *vmx_find_msr(uint32_t msr, enum
> vmx_msr_list_type type)
> {
> struct vcpu *curr = current;
> struct arch_vmx_struct *arch_vmx = &curr->arch.hvm_vmx;
> - struct vmx_msr_entry *start = NULL;
> + struct vmx_msr_entry *start = NULL, *ent, *end;
> unsigned int total;
>
> switch ( type )
> @@ -1315,8 +1327,10 @@ struct vmx_msr_entry *vmx_find_msr(uint32_t
> msr, enum vmx_msr_list_type type)
> if ( !start )
> return NULL;
>
> - return bsearch(&msr, start, total, sizeof(struct vmx_msr_entry),
> - vmx_msr_entry_key_cmp);
> + end = start + total;
> + ent = locate_msr_entry(start, end, msr);
> +
> + return ((ent < end) && (ent->index == msr)) ? ent : NULL;
> }
>
> int vmx_add_msr(uint32_t msr, enum vmx_msr_list_type type)
> @@ -1368,10 +1382,10 @@ int vmx_add_msr(uint32_t msr, enum
> vmx_msr_list_type type)
>
> start = *ptr;
> end = start + total;
> + ent = locate_msr_entry(start, end, msr);
>
> - for ( ent = start; ent < end && ent->index <= msr; ++ent )
> - if ( ent->index == msr )
> - return 0;
> + if ( (ent < end) && (ent->index == msr) )
> + return 0;
>
> if ( total == (PAGE_SIZE / sizeof(*ent)) )
> return -ENOSPC;
> --
> 2.1.4
_______________________________________________
Xen-devel mailing list
Xen-devel@lists.xenproject.org
https://lists.xenproject.org/mailman/listinfo/xen-devel
