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

[Sergey Dyasli <sergey.dyasli@xxxxxxxxxx>]

On Wed, 2017-02-01 at 03:19 -0700, Jan Beulich wrote:
> > 
> > > 
> > > > 
> > > > 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).

You are right that the most effective way would be to use insertion sort.
However, this will require to write some
new code for it.  Since I'm not
convinced that performance is really critical here, the heap sort code
is simply
reused.

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

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