| Message ID | 1485365191-26692-2-git-send-email-sergey.dyasli@citrix.com (mailing list archive) |
|---|---|
| State | New, archived |
| Headers | show |
>>> On 25.01.17 at 18:26, <sergey.dyasli@citrix.com> wrote: > @@ -1283,19 +1284,36 @@ static int construct_vmcs(struct vcpu *v) > return 0; > } > > -int vmx_read_guest_msr(u32 msr, u64 *val) > +static int vmx_msr_entry_key_cmp(const void *key, const void *elt) > { > - struct vcpu *curr = current; > - unsigned int i, msr_count = curr->arch.hvm_vmx.msr_count; > + const u32 *msr = key; > + const struct vmx_msr_entry *entry = elt; > + > + if ( *msr > entry->index ) > + return 1; > + if ( *msr < entry->index ) > + return -1; > + return 0; > +} > + > +struct vmx_msr_entry *vmx_find_guest_msr(const u32 msr) > +{ > + const struct vcpu *curr = current; > + const unsigned int msr_count = curr->arch.hvm_vmx.msr_count; > const struct vmx_msr_entry *msr_area = curr->arch.hvm_vmx.msr_area; I'm not convinced the latter two local variables are particularly useful. I'm also not convinced constifying non-pointed-to types is all that useful (which also applies to the function parameter). But I'll leave the decision whether to accept this to the VM maintainers of course. > +static int vmx_msr_entry_cmp(const void *a, const void *b) > +{ > + const struct vmx_msr_entry *l = a, *r = b; > + > + if ( l->index > r->index ) > + return 1; > + if ( l->index < r->index ) > + return -1; > + return 0; > +} I'd prefer if there was just a single compare function, even if that requires widening the key for the bsearch() invocation. Alternatively ... > @@ -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. Jan
On 31/01/17 11:29, Jan Beulich wrote: >>>> On 25.01.17 at 18:26, <sergey.dyasli@citrix.com> 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. ~Andrew
>>> On 31.01.17 at 12:49, <andrew.cooper3@citrix.com> wrote: > On 31/01/17 11:29, Jan Beulich wrote: >>>>> On 25.01.17 at 18:26, <sergey.dyasli@citrix.com> 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
On 31/01/17 11:54, Jan Beulich wrote: >>>> On 31.01.17 at 12:49, <andrew.cooper3@citrix.com> wrote: >> On 31/01/17 11:29, Jan Beulich wrote: >>>>>> On 25.01.17 at 18:26, <sergey.dyasli@citrix.com> 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. ~Andrew
>>> On 31.01.17 at 13:06, <andrew.cooper3@citrix.com> wrote: > On 31/01/17 11:54, Jan Beulich wrote: >>>>> On 31.01.17 at 12:49, <andrew.cooper3@citrix.com> wrote: >>> On 31/01/17 11:29, Jan Beulich wrote: >>>>>>> On 25.01.17 at 18:26, <sergey.dyasli@citrix.com> 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). Jan
On Tue, 2017-01-31 at 05:43 -0700, Jan Beulich wrote: > > > > > > > > > > > > > On 31.01.17 at 13:06, <andrew.cooper3@citrix.com> wrote: > > On 31/01/17 11:54, Jan Beulich wrote: > > > > > > > > > > > > > > > > > > > > > > > > On 31.01.17 at 12:49, <andrew.cooper3@citrix.com> wrote: > > > > On 31/01/17 11:29, Jan Beulich wrote: > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > On 25.01.17 at 18:26, <sergey.dyasli@citrix.com> 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
>>> On 01.02.17 at 10:38, <sergey.dyasli@citrix.com> wrote: > On Tue, 2017-01-31 at 05:43 -0700, Jan Beulich wrote: >> > >> > > >> > > > >> > > > On 31.01.17 at 13:06, <andrew.cooper3@citrix.com> wrote: >> > On 31/01/17 11:54, Jan Beulich wrote: >> > > >> > > > >> > > > > >> > > > > > >> > > > > > On 31.01.17 at 12:49, <andrew.cooper3@citrix.com> wrote: >> > > > On 31/01/17 11:29, Jan Beulich wrote: >> > > > > >> > > > > > >> > > > > > > >> > > > > > > > >> > > > > > > > On 25.01.17 at 18:26, <sergey.dyasli@citrix.com> 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
On Wed, 2017-02-01 at 03:19 -0700, Jan Beulich wrote: > > > > > > > > > > > > > On 01.02.17 at 10:38, <sergey.dyasli@citrix.com> wrote: > > On Tue, 2017-01-31 at 05:43 -0700, Jan Beulich wrote: > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > On 31.01.17 at 13:06, <andrew.cooper3@citrix.com> wrote: > > > > On 31/01/17 11:54, Jan Beulich wrote: > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > On 31.01.17 at 12:49, <andrew.cooper3@citrix.com> wrote: > > > > > > On 31/01/17 11:29, Jan Beulich wrote: > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > On 25.01.17 at 18:26, <sergey.dyasli@citrix.com> 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
>>> On 01.02.17 at 11:43, <sergey.dyasli@citrix.com> wrote: > On Wed, 2017-02-01 at 03:19 -0700, Jan Beulich wrote: >> > >> > > >> > > > >> > > > On 01.02.17 at 10:38, <sergey.dyasli@citrix.com> wrote: >> > On Tue, 2017-01-31 at 05:43 -0700, Jan Beulich wrote: >> > > >> > > > >> > > > >> > > > > >> > > > > >> > > > > > >> > > > > > >> > > > > > On 31.01.17 at 13:06, <andrew.cooper3@citrix.com> wrote: >> > > > On 31/01/17 11:54, Jan Beulich wrote: >> > > > > >> > > > > >> > > > > > >> > > > > > >> > > > > > > >> > > > > > > >> > > > > > > > >> > > > > > > > >> > > > > > > > On 31.01.17 at 12:49, <andrew.cooper3@citrix.com> wrote: >> > > > > > On 31/01/17 11:29, Jan Beulich wrote: >> > > > > > > >> > > > > > > >> > > > > > > > >> > > > > > > > >> > > > > > > > > >> > > > > > > > > >> > > > > > > > > > >> > > > > > > > > > >> > > > > > > > > > On 25.01.17 at 18:26, <sergey.dyasli@citrix.com> 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
diff --git a/xen/arch/x86/hvm/vmx/vmcs.c b/xen/arch/x86/hvm/vmx/vmcs.c index 59ef199..d04de8d 100644 --- a/xen/arch/x86/hvm/vmx/vmcs.c +++ b/xen/arch/x86/hvm/vmx/vmcs.c @@ -24,6 +24,7 @@ #include <xen/event.h> #include <xen/kernel.h> #include <xen/keyhandler.h> +#include <xen/sort.h> #include <xen/vm_event.h> #include <asm/current.h> #include <asm/cpufeature.h> @@ -1283,19 +1284,36 @@ static int construct_vmcs(struct vcpu *v) return 0; } -int vmx_read_guest_msr(u32 msr, u64 *val) +static int vmx_msr_entry_key_cmp(const void *key, const void *elt) { - struct vcpu *curr = current; - unsigned int i, msr_count = curr->arch.hvm_vmx.msr_count; + const u32 *msr = key; + const struct vmx_msr_entry *entry = elt; + + if ( *msr > entry->index ) + return 1; + if ( *msr < entry->index ) + return -1; + return 0; +} + +struct vmx_msr_entry *vmx_find_guest_msr(const u32 msr) +{ + const struct vcpu *curr = current; + const unsigned int msr_count = curr->arch.hvm_vmx.msr_count; const struct vmx_msr_entry *msr_area = curr->arch.hvm_vmx.msr_area; - for ( i = 0; i < msr_count; i++ ) + return bsearch(&msr, msr_area, msr_count, sizeof(struct vmx_msr_entry), + vmx_msr_entry_key_cmp); +} + +int vmx_read_guest_msr(u32 msr, u64 *val) +{ + const struct vmx_msr_entry *ent; + + if ( (ent = vmx_find_guest_msr(msr)) != NULL ) { - if ( msr_area[i].index == msr ) - { - *val = msr_area[i].data; + *val = ent->data; return 0; - } } return -ESRCH; @@ -1303,22 +1321,37 @@ int vmx_read_guest_msr(u32 msr, u64 *val) int vmx_write_guest_msr(u32 msr, u64 val) { - struct vcpu *curr = current; - unsigned int i, msr_count = curr->arch.hvm_vmx.msr_count; - struct vmx_msr_entry *msr_area = curr->arch.hvm_vmx.msr_area; + struct vmx_msr_entry *ent; - for ( i = 0; i < msr_count; i++ ) + if ( (ent = vmx_find_guest_msr(msr)) != NULL ) { - if ( msr_area[i].index == msr ) - { - msr_area[i].data = val; + ent->data = val; return 0; - } } return -ESRCH; } +static void vmx_msr_entry_swap(void *a, void *b, int size) +{ + struct vmx_msr_entry *l = a, *r = b, tmp; + + tmp = *l; + *l = *r; + *r = tmp; +} + +static int vmx_msr_entry_cmp(const void *a, const void *b) +{ + const struct vmx_msr_entry *l = a, *r = b; + + if ( l->index > r->index ) + return 1; + if ( l->index < r->index ) + return -1; + return 0; +} + int vmx_add_msr(u32 msr, int type) { struct vcpu *curr = current; @@ -1351,9 +1384,17 @@ int vmx_add_msr(u32 msr, int type) __vmwrite(VM_EXIT_MSR_LOAD_ADDR, virt_to_maddr(*msr_area)); } - for ( idx = 0; idx < *msr_count; idx++ ) - if ( (*msr_area)[idx].index == msr ) + if ( type == VMX_GUEST_MSR ) + { + if ( vmx_find_guest_msr(msr) != NULL ) return 0; + } + else + { + for ( idx = 0; idx < *msr_count; idx++ ) + if ( (*msr_area)[idx].index == msr ) + return 0; + } if ( *msr_count == (PAGE_SIZE / sizeof(struct vmx_msr_entry)) ) return -ENOSPC; @@ -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); } else { diff --git a/xen/include/asm-x86/hvm/vmx/vmcs.h b/xen/include/asm-x86/hvm/vmx/vmcs.h index 6c3d7ba..d01099e 100644 --- a/xen/include/asm-x86/hvm/vmx/vmcs.h +++ b/xen/include/asm-x86/hvm/vmx/vmcs.h @@ -589,6 +589,7 @@ enum vmx_insn_errno void vmx_disable_intercept_for_msr(struct vcpu *v, u32 msr, int type); void vmx_enable_intercept_for_msr(struct vcpu *v, u32 msr, int type); +struct vmx_msr_entry *vmx_find_guest_msr(const u32 msr); int vmx_read_guest_msr(u32 msr, u64 *val); int vmx_write_guest_msr(u32 msr, u64 val); int vmx_add_msr(u32 msr, int type);
Currently there can be up to 256 entries in a guest's MSR array and all entries are stored in the order they were added. Such design requires to perform a linear scan of the whole array in order to find the MSR with required index which can be a costly operation. To avoid that, reuse the existing code for heap sort and binary search and optimize existing functions which deal with guest's MSR arrays. This way the time complexity of searching for required MSR reduces from linear to logarithmic. Signed-off-by: Sergey Dyasli <sergey.dyasli@citrix.com> --- xen/arch/x86/hvm/vmx/vmcs.c | 80 +++++++++++++++++++++++++++++--------- xen/include/asm-x86/hvm/vmx/vmcs.h | 1 + 2 files changed, 63 insertions(+), 18 deletions(-)