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