On 23/05/18 17:39, Roger Pau Monné wrote:
> 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.coop...@citrix.com>
>> ---
>> 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.
>> 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.
A third use appears in a later patch. bsearch() doesn't have the
described property on a miss, which is necessary to maintain the lists.
~Andrew
_______________________________________________
Xen-devel mailing list
Xen-devel@lists.xenproject.org
https://lists.xenproject.org/mailman/listinfo/xen-devel
