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

[Andrew Cooper <andrew.cooper3@xxxxxxxxxx>]

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.

~Andrew

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