From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: X-Spam-Checker-Version: SpamAssassin 3.4.0 (2014-02-07) on aws-us-west-2-korg-lkml-1.web.codeaurora.org X-Spam-Level: X-Spam-Status: No, score=-2.2 required=3.0 tests=HEADER_FROM_DIFFERENT_DOMAINS, MAILING_LIST_MULTI,SPF_HELO_NONE,SPF_PASS,USER_AGENT_SANE_1 autolearn=no autolearn_force=no version=3.4.0 Received: from mail.kernel.org (mail.kernel.org [198.145.29.99]) by smtp.lore.kernel.org (Postfix) with ESMTP id 1D5A6CA9EBC for ; Thu, 24 Oct 2019 19:39:03 +0000 (UTC) Received: from vger.kernel.org (vger.kernel.org [209.132.180.67]) by mail.kernel.org (Postfix) with ESMTP id ED46A2166E for ; Thu, 24 Oct 2019 19:39:02 +0000 (UTC) Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S2437079AbfJXTjC (ORCPT ); Thu, 24 Oct 2019 15:39:02 -0400 Received: from mga01.intel.com ([192.55.52.88]:58804 "EHLO mga01.intel.com" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S2436996AbfJXTi5 (ORCPT ); Thu, 24 Oct 2019 15:38:57 -0400 X-Amp-Result: UNKNOWN X-Amp-Original-Verdict: FILE UNKNOWN X-Amp-File-Uploaded: False Received: from fmsmga004.fm.intel.com ([10.253.24.48]) by fmsmga101.fm.intel.com with ESMTP/TLS/DHE-RSA-AES256-GCM-SHA384; 24 Oct 2019 12:38:57 -0700 X-ExtLoop1: 1 X-IronPort-AV: E=Sophos;i="5.68,225,1569308400"; d="scan'208";a="223680295" Received: from sjchrist-coffee.jf.intel.com (HELO linux.intel.com) ([10.54.74.41]) by fmsmga004.fm.intel.com with ESMTP; 24 Oct 2019 12:38:56 -0700 Date: Thu, 24 Oct 2019 12:38:56 -0700 From: Sean Christopherson To: Paolo Bonzini Cc: James Hogan , Paul Mackerras , Christian Borntraeger , Janosch Frank , Radim =?utf-8?B?S3LEjW3DocWZ?= , Marc Zyngier , David Hildenbrand , Cornelia Huck , Vitaly Kuznetsov , Wanpeng Li , Jim Mattson , Joerg Roedel , James Morse , Julien Thierry , Suzuki K Poulose , linux-mips@vger.kernel.org, kvm-ppc@vger.kernel.org, kvm@vger.kernel.org, linux-arm-kernel@lists.infradead.org, kvmarm@lists.cs.columbia.edu, linux-kernel@vger.kernel.org Subject: Re: [PATCH v2 14/15] KVM: Terminate memslot walks via used_slots Message-ID: <20191024193856.GA28043@linux.intel.com> References: <20191022003537.13013-1-sean.j.christopherson@intel.com> <20191022003537.13013-15-sean.j.christopherson@intel.com> <642f73ee-9425-0149-f4f4-f56be9ae5713@redhat.com> <20191022152827.GC2343@linux.intel.com> <625e511f-bd35-3b92-0c6d-550c10fc5827@redhat.com> <20191022155220.GD2343@linux.intel.com> <5c61c094-ee32-4dcf-b3ae-092eba0159c5@redhat.com> MIME-Version: 1.0 Content-Type: text/plain; charset=us-ascii Content-Disposition: inline In-Reply-To: <5c61c094-ee32-4dcf-b3ae-092eba0159c5@redhat.com> User-Agent: Mutt/1.5.24 (2015-08-30) Sender: linux-mips-owner@vger.kernel.org Precedence: bulk List-ID: X-Mailing-List: linux-mips@vger.kernel.org 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; } }