Re: [Xen-devel] [PATCH 1/2] x86/VMX: introduce vmx_find_guest_msr()

["Jan Beulich" <JBeulich@xxxxxxxx>]

>>> On 31.01.17 at 13:06, <andrew.cooper3@xxxxxxxxxx> wrote:
> On 31/01/17 11:54, Jan Beulich wrote:
>>>>> On 31.01.17 at 12:49, <andrew.cooper3@xxxxxxxxxx> wrote:
>>> On 31/01/17 11:29, Jan Beulich wrote:
>>>>>>> On 25.01.17 at 18:26, <sergey.dyasli@xxxxxxxxxx> wrote:
>>>>>>>
>>>>> @@ -1369,6 +1410,9 @@ int vmx_add_msr(u32 msr, int type)
>>>>>          msr_area_elem->data = 0;
>>>>>          __vmwrite(VM_EXIT_MSR_STORE_COUNT, *msr_count);
>>>>>          __vmwrite(VM_ENTRY_MSR_LOAD_COUNT, *msr_count);
>>>>> +
>>>>> +        sort(*msr_area, *msr_count, sizeof(struct vmx_msr_entry),
>>>>> +             vmx_msr_entry_cmp, vmx_msr_entry_swap);
>>>> ... how about avoiding the sort() here altogether, by simply
>>>> going through the list linearly (which, being O(n), is still faster
>>>> than sort())? The more that there is a linear scan already
>>>> anyway. At which point it may then be beneficial to also keep
>>>> the host MSR array sorted.
>>> The entire point of sorting this list is to trade an O(n) search for
>>> O(log(n)) in every vmentry when fixing up the LBR MSR values.
>>>
>>> There should be no O(n) searches across the list after this patch.
>> And that's indeed not the case. But the sort() is O(n * log(n)).
> 
> I don't understand what point you are trying to make.
> 
> Adding MSRs to the list (turns out we have no remove yet) is a rare
> occurrence, and in practice, this LBR addition is the only one which
> happens at runtime rather than domain creation.
> 
> However, you cannot have an efficient fixup on vmenter if the list isn't
> sorted, and it is not possible to sort a list in less than O(n * log(n))
> in the general case.

True, but we're adding incrementally, i.e. the list is already sorted,
and it is already being walked linearly a few lines up from where the
sort() invocation is being added. Hence the addition can as well be
done without sort(), and then in O(n).

Jan


_______________________________________________
Xen-devel mailing list
Xen-devel@xxxxxxxxxxxxx
https://lists.xen.org/xen-devel