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

["Jan Beulich" <JBeulich@xxxxxxxx>]

>>> On 01.02.17 at 10:38, <sergey.dyasli@xxxxxxxxxx> wrote:
> On Tue, 2017-01-31 at 05:43 -0700, Jan Beulich wrote:
>> > 
>> > > 
>> > > > 
>> > > > 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).
> 
> 1. Guest's MSR list is not sorted currently, which can be seen from
> lbr_info:
> 
>     MSR_IA32_LASTINTFROMIP          0x000001dd
>     MSR_IA32_LASTINTTOIP            0x000001de
>     MSR_C2_LASTBRANCH_TOS           0x000001c9
>     MSR_P4_LASTBRANCH_0_FROM_LIP    0x00000680

I don't understand: Your patch arranges for the list to be sorted,
doesn't it? All I'm questioning is the approach of how the sorting
is being done - what I'm trying to say is that I think you can do
without any sort() invocation, leveraging the fact that the list
you want to add to is already sorted (inductively, starting from a
zero length list, by always inserting at the right spot, the list will
always be sorted).

> 2. In the future there might be more MSRs in the list and a sorted list
> is a prerequisite for fast lookups. Time complexity of vmx_add_msr()
> is irrelevant since it's a "one shot" operation.

I've never said I'm against sorting.

Jan


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