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

["Jan Beulich" <JBeulich@xxxxxxxx>]

>>> 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)).

Jan


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