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

["Jan Beulich" <JBeulich@xxxxxxxx>]

>>> On 01.02.17 at 11:43, <sergey.dyasli@xxxxxxxxxx> wrote:
> 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.

Which is - I think - more new code than simply leveraging the
existing linear scan over the array, recording the insertion
point, perhaps (since it's sorted already) bailing once an entry
with a higher numbered MSR is found, and memmov()ing any
higher numbered entries. Performance isn't the main aspect
here, but I don't think we should write slow code (even if that
code is being used rarely) when - with about the same amount
of effort/code - we can have a faster variant.

Jan

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