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 Thu, May 24, 2018 at 11:59:07AM +0100, Andrew Cooper wrote:
> 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.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.
> >> 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.

Oh, didn't know that. In which case I agree. AFAICT there's no POSIX
specification for a function that could be used to add new entries
into a sorted array, so:

Reviewed-by: Roger Pau Monné <roger.pau@xxxxxxxxxx>

Thanks, Roger.

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