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: Thu, 24 Oct 2019 12:38:56 -0700 From: Sean Christopherson <sean.j.christopherson@...el.com> To: Paolo Bonzini <pbonzini@...hat.com> Cc: James Hogan <jhogan@...nel.org>, Paul Mackerras <paulus@...abs.org>, Christian Borntraeger <borntraeger@...ibm.com>, Janosch Frank <frankja@...ux.ibm.com>, Radim Krčmář <rkrcmar@...hat.com>, Marc Zyngier <maz@...nel.org>, David Hildenbrand <david@...hat.com>, Cornelia Huck <cohuck@...hat.com>, Vitaly Kuznetsov <vkuznets@...hat.com>, Wanpeng Li <wanpengli@...cent.com>, Jim Mattson <jmattson@...gle.com>, Joerg Roedel <joro@...tes.org>, James Morse <james.morse@....com>, Julien Thierry <julien.thierry.kdev@...il.com>, Suzuki K Poulose <suzuki.poulose@....com>, linux-mips@...r.kernel.org, kvm-ppc@...r.kernel.org, kvm@...r.kernel.org, linux-arm-kernel@...ts.infradead.org, kvmarm@...ts.cs.columbia.edu, linux-kernel@...r.kernel.org Subject: Re: [PATCH v2 14/15] KVM: Terminate memslot walks via used_slots On Tue, Oct 22, 2019 at 05:53:27PM +0200, Paolo Bonzini wrote: > On 22/10/19 17:52, Sean Christopherson wrote: > > > > Anyways, I'm not at all opposed to adding comments, just want to make sure > > I'm not forgetting something. If it's ok with you, I'll comment the code > > and/or functions and reply here to refine them without having to respin > > the whole series. > > Yes, I agree this is better. Here's what I ended up with. I also added kvm_memslot_insert_back() to help document the purpose of incrementing used_slots, and renamed kvm_shift_memslots_forward()->kvm_memslot_move_backward() and kvm_shift_memslots_backward()->kvm_memslot_move_forward() because I was having trouble reconciling having the comments focus on the changed memslot while the names of the functions reflected what happens to the other memslots. /* * Delete a memslot by decrementing the number of used slots and shifting all * other entries in the array forward one spot. */ static inline void kvm_memslot_delete(struct kvm_memslots *slots, struct kvm_memory_slot *memslot) { struct kvm_memory_slot *mslots = slots->memslots; int i; if (WARN_ON(slots->id_to_index[memslot->id] == -1)) return; slots->used_slots--; for (i = slots->id_to_index[memslot->id]; i < slots->used_slots; i++) { mslots[i] = mslots[i + 1]; slots->id_to_index[mslots[i].id] = i; } mslots[i] = *memslot; slots->id_to_index[memslot->id] = -1; } /* * "Insert" a new memslot by incrementing the number of used slots. Returns * the new slot's initial index into the memslots array. */ static inline int kvm_memslot_insert_back(struct kvm_memslots *slots) { return slots->used_slots++; } /* * Move a changed memslot backwards in the array by shifting existing slots * with a higher GFN toward the front of the array. Note, the changed memslot * itself is not preserved in the array, i.e. not swapped at this time, only * its new index into the array is update. Returns the changed memslot's * current index into the memslots array. */ static inline int kvm_memslot_move_backward(struct kvm_memslots *slots, struct kvm_memory_slot *memslot) { struct kvm_memory_slot *mslots = slots->memslots; int i; if (WARN_ON_ONCE(slots->id_to_index[memslot->id] == -1) || WARN_ON_ONCE(!slots->used_slots)) return -1; for (i = slots->id_to_index[memslot->id]; i < slots->used_slots - 1; i++) { if (memslot->base_gfn > mslots[i + 1].base_gfn) break; WARN_ON_ONCE(memslot->base_gfn == mslots[i + 1].base_gfn); /* Shift the next memslot forward one and update its index. */ mslots[i] = mslots[i + 1]; slots->id_to_index[mslots[i].id] = i; } return i; } /* * Move a changed memslot forwards in the array by shifting existing slots with * a lower GFN toward the back of the array. Note, the changed memslot itself * is not preserved in the array, i.e. not swapped at this time, only its new * index into the array is updated. Returns the changed memslot's final index * into the memslots array. */ static inline int kvm_memslot_move_forward(struct kvm_memslots *slots, struct kvm_memory_slot *memslot, int start) { struct kvm_memory_slot *mslots = slots->memslots; int i; for (i = start; i > 0; i--) { if (memslot->base_gfn < mslots[i - 1].base_gfn) break; WARN_ON_ONCE(memslot->base_gfn == mslots[i - 1].base_gfn); /* Shift the next memslot back one and update its index. */ mslots[i] = mslots[i - 1]; slots->id_to_index[mslots[i].id] = i; } return i; } /* * Re-sort memslots based on their GFN to account for an added, deleted, or * moved memslot. Sorting memslots allows using a binary search during memslot * lookup. * * IMPORTANT: Slots are sorted from highest GFN to lowest GFN! I.e. the entry * at memslots[0] has the highest GFN. * * The sorting algorithm takes advantage of having initially sorted memslots * and knowing the position of the changed memslot. Sorting is also optimized * by not swapping the updated memslot and instead only shifting other memslots * and tracking the new index for the update memslot. Only once its final * index is known is the updated memslot copied into its position in the array. * * - When deleting a memslot, the deleted memslot simply needs to be moved to * the end of the array. * * - When creating a memslot, the algorithm "inserts" the new memslot at the * end of the array and then it forward to its correct location. * * - When moving a memslot, the algorithm first moves the updated memslot * backward to handle the scenario where the memslot's GFN was changed to a * lower value. update_memslots() then falls through and runs the same flow * as creating a memslot to move the memslot forward to handle the scenario * where its GFN was changed to a higher value. * * Note, slots are sorted from highest->lowest instead of lowest->highest for * historical reasons. Originally, invalid memslots where denoted by having * GFN=0, thus sorting from highest->lowest naturally sorted invalid memslots * to the end of the array. The current algorithm uses dedicated logic when * deleting a memslot and thus does not rely on invalid memslots having GFN=0. */ static void update_memslots(struct kvm_memslots *slots, struct kvm_memory_slot *memslot, enum kvm_mr_change change) { int i; if (change == KVM_MR_DELETE) { kvm_memslot_delete(slots, memslot); } else { if (change == KVM_MR_CREATE) i = kvm_memslot_insert_back(slots); else i = kvm_memslot_move_backward(slots, memslot); i = kvm_memslot_move_forward(slots, memslot, i); /* * Copy the memslot to its new position in memslots and update * its index accordingly. */ slots->memslots[i] = *memslot; slots->id_to_index[memslot->id] = i; } }
Powered by blists - more mailing lists