| lists.openwall.net | lists / announce owl-users owl-dev john-users john-dev passwdqc-users yescrypt popa3d-users / oss-security kernel-hardening musl sabotage tlsify passwords / crypt-dev xvendor / Bugtraq Full-Disclosure linux-kernel linux-netdev linux-ext4 linux-hardening linux-cve-announce PHC | |
|
Open Source and information security mailing list archives
| ||
|
Date: Fri, 14 Nov 2014 11:58:46 +0100
From: Igor Mammedov <imammedo@...hat.com>
To: Paolo Bonzini <pbonzini@...hat.com>
Cc: linux-kernel@...r.kernel.org, kvm@...r.kernel.org
Subject: Re: [PATCH v2] kvm: memslots: replace heap sort with insertion sort
On Fri, 14 Nov 2014 10:57:10 +0100
Paolo Bonzini <pbonzini@...hat.com> wrote:
>
>
> On 14/11/2014 00:00, Igor Mammedov wrote:
> > memslots is a sorted array, when slot changes in it
> > with current heapsort it would take O(n log n) time
> > to update array, while using insertion sort like
> > algorithm on array with 1 item out of order will
> > take only O(n) time.
> >
> > Replace current heapsort with custom sort that
> > takes advantage of memslots usage pattern and known
> > position of changed slot.
> >
> > performance change of 128 memslots insersions with
> > gradually increasing size (the worst case):
> > heap sort custom sort
> > max: 249747 2500 cycles
> > with custom sort alg taking ~98% less then original
> > update time.
> >
> > Signed-off-by: Igor Mammedov <imammedo@...hat.com>
> > ---
> > v2:
> > - replace swap with slot shift, improves result 2x
> > - reprofile original/swap based and swapless 15 times
> > discarding spikes swap based takes ~5900 cycles max
> > and swapless ~2500 cycles.
> > ---
> > virt/kvm/kvm_main.c | 54
> > ++++++++++++++++++++++++++--------------------------- 1 file
> > changed, 26 insertions(+), 28 deletions(-)
> >
> > diff --git a/virt/kvm/kvm_main.c b/virt/kvm/kvm_main.c
> > index 25ffac9..49f896a 100644
> > --- a/virt/kvm/kvm_main.c
> > +++ b/virt/kvm/kvm_main.c
> > @@ -668,31 +668,35 @@ static int kvm_create_dirty_bitmap(struct
> > kvm_memory_slot *memslot) return 0;
> > }
> >
> > -static int cmp_memslot(const void *slot1, const void *slot2)
> > -{
> > - struct kvm_memory_slot *s1, *s2;
> > -
> > - s1 = (struct kvm_memory_slot *)slot1;
> > - s2 = (struct kvm_memory_slot *)slot2;
> > -
> > - if (s1->npages < s2->npages)
> > - return 1;
> > - if (s1->npages > s2->npages)
> > - return -1;
> > -
> > - return 0;
> > -}
> > -
> > /*
> > - * Sort the memslots base on its size, so the larger slots
> > - * will get better fit.
> > + * Insert memslot and re-sort memslots based on their size,
> > + * so the larger slots will get better fit. Sorting algorithm
> > + * takes advantage of having initially sorted array and
> > + * known changed memslot position.
> > */
> > -static void sort_memslots(struct kvm_memslots *slots)
> > +static void insert_memslot(struct kvm_memslots *slots,
> > + struct kvm_memory_slot *new)
> > {
> > - int i;
> > + int i = slots->id_to_index[new->id];
> > + struct kvm_memory_slot *old = id_to_memslot(slots,
> > new->id);
> > + struct kvm_memory_slot *mslots = slots->memslots;
> > +
>
> It is important to leave the "*old = *new" assignment here, see the
> comment in __kvm_set_memory_region:
>
> /*
> * We can re-use the old_memslots from above, the only
> difference
> * from the currently installed memslots is the invalid
> flag. This
> * will get overwritten by update_memslots anyway.
> */
>
> This small problem was already present in v1, but I didn't notice it
> yesterday. With the new code, we can add it inside this if:
>
> > + if (new->npages == old->npages)
> > + return;
>
> Do you agree? (No need to send v3).
yes, slot must be updated even if number of pages haven't changed,
since other fields could hold updated values.
>
> Paolo
>
> > - sort(slots->memslots, KVM_MEM_SLOTS_NUM,
> > - sizeof(struct kvm_memory_slot), cmp_memslot, NULL);
> > + while (1) {
> > + if (i < (KVM_MEM_SLOTS_NUM - 1) &&
> > + new->npages < mslots[i + 1].npages) {
> > + mslots[i] = mslots[i + 1];
> > + i++;
> > + } else if (i > 0 && new->npages > mslots[i -
> > 1].npages) {
> > + mslots[i] = mslots[i - 1];
> > + i--;
> > + } else {
> > + mslots[i] = *new;
> > + break;
> > + }
> > + }
> >
> > for (i = 0; i < KVM_MEM_SLOTS_NUM; i++)
> > slots->id_to_index[slots->memslots[i].id] = i;
> > @@ -702,13 +706,7 @@ static void update_memslots(struct
> > kvm_memslots *slots, struct kvm_memory_slot *new)
> > {
> > if (new) {
> > - int id = new->id;
> > - struct kvm_memory_slot *old = id_to_memslot(slots,
> > id);
> > - unsigned long npages = old->npages;
> > -
> > - *old = *new;
> > - if (new->npages != npages)
> > - sort_memslots(slots);
> > + insert_memslot(slots, new);
> > }
> > }
> >
> >
--
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majordomo@...r.kernel.org
More majordomo info at http://vger.kernel.org/majordomo-info.html
Please read the FAQ at http://www.tux.org/lkml/
Powered by blists - more mailing lists