* Peng Zhang <zhangpeng.00@xxxxxxxxxxxxx> [240822 02:56]:
> Currently, xarray is used to manage memory attributes. The memory
> attributes management here is an interval problem. However, xarray is
> not suitable for handling interval problems. It may cause memory waste
> and is not efficient. Switching it to maple tree is more elegant. Using
> maple tree here has the following three advantages:
> 1. Less memory overhead.
> 2. More efficient interval operations.
> 3. Simpler code.
>
> This is the first user of the maple tree interface mas_find_range(),
> and it does not have any test cases yet, so its stability is unclear.
>
> Signed-off-by: Peng Zhang <zhangpeng.00@xxxxxxxxxxxxx>
> ---
> include/linux/kvm_host.h | 5 +++--
> virt/kvm/kvm_main.c | 47 ++++++++++++++--------------------------
> 2 files changed, 19 insertions(+), 33 deletions(-)
>
> I haven't tested this code yet, and I'm not very familiar with kvm, so I'd
> be happy if someone could help test it. This is just an RFC now. Any comments
> are welcome.
>
> diff --git a/include/linux/kvm_host.h b/include/linux/kvm_host.h
> index 79a6b1a63027..9b3351d88d64 100644
> --- a/include/linux/kvm_host.h
> +++ b/include/linux/kvm_host.h
> @@ -35,6 +35,7 @@
> #include <linux/interval_tree.h>
> #include <linux/rbtree.h>
> #include <linux/xarray.h>
> +#include <linux/maple_tree.h>
> #include <asm/signal.h>
>
> #include <linux/kvm.h>
> @@ -839,7 +840,7 @@ struct kvm {
> #endif
> #ifdef CONFIG_KVM_GENERIC_MEMORY_ATTRIBUTES
> /* Protected by slots_locks (for writes) and RCU (for reads) */
> - struct xarray mem_attr_array;
> + struct maple_tree mem_attr_mtree;
> #endif
> char stats_id[KVM_STATS_NAME_SIZE];
> };
> @@ -2410,7 +2411,7 @@ static inline void kvm_prepare_memory_fault_exit(struct kvm_vcpu *vcpu,
> #ifdef CONFIG_KVM_GENERIC_MEMORY_ATTRIBUTES
> static inline unsigned long kvm_get_memory_attributes(struct kvm *kvm, gfn_t gfn)
> {
> - return xa_to_value(xa_load(&kvm->mem_attr_array, gfn));
> + return xa_to_value(mtree_load(&kvm->mem_attr_mtree, gfn));
> }
>
> bool kvm_range_has_memory_attributes(struct kvm *kvm, gfn_t start, gfn_t end,
> diff --git a/virt/kvm/kvm_main.c b/virt/kvm/kvm_main.c
> index 92901656a0d4..9a99c334f4af 100644
> --- a/virt/kvm/kvm_main.c
> +++ b/virt/kvm/kvm_main.c
> @@ -10,6 +10,7 @@
> * Yaniv Kamay <yaniv@xxxxxxxxxxxx>
> */
>
> +#include "linux/maple_tree.h"
> #include <kvm/iodev.h>
>
> #include <linux/kvm_host.h>
> @@ -1159,7 +1160,8 @@ static struct kvm *kvm_create_vm(unsigned long type, const char *fdname)
> rcuwait_init(&kvm->mn_memslots_update_rcuwait);
> xa_init(&kvm->vcpu_array);
> #ifdef CONFIG_KVM_GENERIC_MEMORY_ATTRIBUTES
> - xa_init(&kvm->mem_attr_array);
> + mt_init_flags(&kvm->mem_attr_mtree, MT_FLAGS_LOCK_EXTERN);
> + mt_set_external_lock(&kvm->mem_attr_mtree, &kvm->slots_lock);
> #endif
>
> INIT_LIST_HEAD(&kvm->gpc_list);
> @@ -1356,7 +1358,9 @@ static void kvm_destroy_vm(struct kvm *kvm)
> cleanup_srcu_struct(&kvm->irq_srcu);
> cleanup_srcu_struct(&kvm->srcu);
> #ifdef CONFIG_KVM_GENERIC_MEMORY_ATTRIBUTES
> - xa_destroy(&kvm->mem_attr_array);
> + mutex_lock(&kvm->slots_lock);
> + __mt_destroy(&kvm->mem_attr_mtree);
> + mutex_unlock(&kvm->slots_lock);
> #endif
> kvm_arch_free_vm(kvm);
> preempt_notifier_dec();
> @@ -2413,30 +2417,20 @@ static u64 kvm_supported_mem_attributes(struct kvm *kvm)
> bool kvm_range_has_memory_attributes(struct kvm *kvm, gfn_t start, gfn_t end,
> unsigned long mask, unsigned long attrs)
> {
> - XA_STATE(xas, &kvm->mem_attr_array, start);
> - unsigned long index;
> + MA_STATE(mas, &kvm->mem_attr_mtree, start, start);
> void *entry;
>
> mask &= kvm_supported_mem_attributes(kvm);
> if (attrs & ~mask)
> return false;
>
> - if (end == start + 1)
> - return (kvm_get_memory_attributes(kvm, start) & mask) == attrs;
> -
> guard(rcu)();
> - if (!attrs)
> - return !xas_find(&xas, end - 1);
> -
> - for (index = start; index < end; index++) {
> - do {
> - entry = xas_next(&xas);
> - } while (xas_retry(&xas, entry));
>
> - if (xas.xa_index != index ||
> - (xa_to_value(entry) & mask) != attrs)
> + do {
> + entry = mas_find_range(&mas, end - 1);
> + if ((xa_to_value(entry) & mask) != attrs)
> return false;
> - }
> + } while (mas.last < end - 1);
Oh, a contiguous iterator.. This is what mas_find_range() was written
for.
This should work with the guard(rcu)(); call with the internal lock.
>
> return true;
> }
> @@ -2524,9 +2518,9 @@ static int kvm_vm_set_mem_attributes(struct kvm *kvm, gfn_t start, gfn_t end,
> .on_lock = kvm_mmu_invalidate_end,
> .may_block = true,
> };
> - unsigned long i;
> void *entry;
> int r = 0;
> + MA_STATE(mas, &kvm->mem_attr_mtree, start, end - 1);
>
> entry = attributes ? xa_mk_value(attributes) : NULL;
>
> @@ -2540,20 +2534,11 @@ static int kvm_vm_set_mem_attributes(struct kvm *kvm, gfn_t start, gfn_t end,
> * Reserve memory ahead of time to avoid having to deal with failures
> * partway through setting the new attributes.
> */
> - for (i = start; i < end; i++) {
> - r = xa_reserve(&kvm->mem_attr_array, i, GFP_KERNEL_ACCOUNT);
> - if (r)
> - goto out_unlock;
> - }
> -
> + r = mas_preallocate(&mas, entry, GFP_KERNEL_ACCOUNT);
> + if (r)
> + goto out_unlock;
> kvm_handle_gfn_range(kvm, &pre_set_range);
> -
> - for (i = start; i < end; i++) {
> - r = xa_err(xa_store(&kvm->mem_attr_array, i, entry,
> - GFP_KERNEL_ACCOUNT));
> - KVM_BUG_ON(r, kvm);
> - }
> -
> + mas_store_prealloc(&mas, entry);
I think you can just leave a spinlock and take it for this
preallocate/store?
> kvm_handle_gfn_range(kvm, &post_set_range);
>
> out_unlock:
> --
> 2.20.1
>
>
> --
> maple-tree mailing list
> maple-tree@xxxxxxxxxxxxxxxxxxx
> https://lists.infradead.org/mailman/listinfo/maple-tree
