On 24/05/18 11:53, Roger Pau Monné wrote:
> On Wed, May 23, 2018 at 05:55:50PM +0100, Andrew Cooper wrote:
>> 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.
> I would consider adding a flag to the list of parameters so that
> bsearch returned the position where the item should be added in case
> of a miss. You could then wrap it inside of locate_msr_entry, or get
> rid of this helper altogether.
bsearch() is specified by POSIX, and C89/99, amongst other standards.
Changing its API is not something I'm going to do.
~Andrew
_______________________________________________
Xen-devel mailing list
Xen-devel@lists.xenproject.org
https://lists.xenproject.org/mailman/listinfo/xen-devel
