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

[Sergey Dyasli <sergey.dyasli@xxxxxxxxxx>]

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

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.

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