From nobody Fri Dec 19 14:35:38 2025 Received: from mail-wm1-f73.google.com (mail-wm1-f73.google.com [209.85.128.73]) (using TLSv1.2 with cipher ECDHE-RSA-AES128-GCM-SHA256 (128/128 bits)) (No client certificate requested) by smtp.subspace.kernel.org (Postfix) with ESMTPS id D2C68267F74 for ; Tue, 20 May 2025 08:53:14 +0000 (UTC) Authentication-Results: smtp.subspace.kernel.org; arc=none smtp.client-ip=209.85.128.73 ARC-Seal: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1747731196; cv=none; b=BKZAuCSky/HtI9SeZ4XnaCwF7dh0PAftcyNySbbZI2JlkDPFgk1T4mF2Yee+gH8M82kw5pfbjmyhIf04XCuYqR8a6H+xrFbxn3C2+EIhpx8TaZ3AKvdBBqRQ/eWZVYQVVcZbeLpBl25WWjqbTGhmbG4ccLcFh/3QtA+UC7ayrxU= ARC-Message-Signature: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1747731196; c=relaxed/simple; bh=TEHmGZnOintA1J+nfRT2TgJJ3gdS4R+4jCcNr1BjZxM=; h=Date:In-Reply-To:Mime-Version:References:Message-ID:Subject:From: To:Cc:Content-Type; b=RgvyZ7MzQ92EEungURuPcC+LvDBPZXKRzi9VB60FvSxr4M+NYuw47zvmGMpR8y07Hl0LfrXClcaINJZfAFFRmVi0chFjapXrlJDhU4MnU3zfhFdHO9fevIb2xHF8o6pLIbWWpHxdNXaSGPWAFfIl2c02nOZP7EsKx+SXwKDlwWw= ARC-Authentication-Results: i=1; smtp.subspace.kernel.org; dmarc=pass (p=reject dis=none) header.from=google.com; spf=pass smtp.mailfrom=flex--vdonnefort.bounces.google.com; dkim=pass (2048-bit key) header.d=google.com header.i=@google.com header.b=2O3s1ndk; arc=none smtp.client-ip=209.85.128.73 Authentication-Results: smtp.subspace.kernel.org; dmarc=pass (p=reject dis=none) header.from=google.com Authentication-Results: smtp.subspace.kernel.org; spf=pass smtp.mailfrom=flex--vdonnefort.bounces.google.com Authentication-Results: smtp.subspace.kernel.org; dkim=pass (2048-bit key) header.d=google.com header.i=@google.com header.b="2O3s1ndk" Received: by mail-wm1-f73.google.com with SMTP id 5b1f17b1804b1-43d007b2c79so42103235e9.2 for ; Tue, 20 May 2025 01:53:14 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=google.com; s=20230601; t=1747731193; x=1748335993; darn=vger.kernel.org; h=cc:to:from:subject:message-id:references:mime-version:in-reply-to :date:from:to:cc:subject:date:message-id:reply-to; bh=RrWP6Zwi1iKiAKyg1cea1PjFAdTTJFrjdN8oFu8iy90=; b=2O3s1ndkcp7GM3O90omGfE6aifqJUslqVjtdfv8R0Mmux9CIhKExVA/k9T3i9UG4uf on2gHtW4Xgah+HdRUh+Pfp9HvBOWxDXL/9wIm581Y3dDkDriAALJmxhmaF7wvViCHlmV 6eJVbpHUU9Y3shXdL/7wz9webla2niCaSKfSZMJ6o8KdAkjs2046Tih4oa2/39R/aC6r NoOMYgenY0h5oiGeLCdkemcWkvsEvpC4C0sHDfyzEtToPfD5ynCenpx3UMOHZSMpT8dw 31EnqHxyzLqxIViDdYtieheEAlqySXgVfh3qEpxkwhbrMc2LcTuKcy4epqH8S6l/bZGZ 3m4Q== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20230601; t=1747731193; x=1748335993; h=cc:to:from:subject:message-id:references:mime-version:in-reply-to :date:x-gm-message-state:from:to:cc:subject:date:message-id:reply-to; bh=RrWP6Zwi1iKiAKyg1cea1PjFAdTTJFrjdN8oFu8iy90=; b=ZeIhwflj9YARCeeR9Vk3Rbq47lvYgylh2+gKANTo8BbYOiqbyHQji0EfF3pSe+qjeV 3CfiAYiF0rAqe53xTBMN80sWP4WDYugJ+OIQotlab8cuXWnQfKQyRXHNDxgXSvrUhCGK iLcYjQqrKLlCn8ud42lor9eOvUGbzFUVUKWGEwYl2LLNYS1iCpzg7VWPeRq3ltyXM+ZH +EaIVmaQMT5qQVXP84E0gvvNRiOqUd9Hfqs9h4kTxU58GT59T/y+poLjogmVS/v4Mm2q UeqL7q4e86bjTro40jJNDEpgKDvR4S2eEFNz4EAbVMjh1KxqPCSB8KD6RloauieoP0l5 GLfA== X-Forwarded-Encrypted: i=1; AJvYcCUAJZz/aXjNydo6shSN9387/p15JhCnWqLHcNkuJFy1AmKL0mGPLuxfgSrBwlEXmzETt9tCyOhXlyNWH1g=@vger.kernel.org X-Gm-Message-State: AOJu0Ywai7gcxe1a5iytWLh0phVtgZ/BXsjZ+h21OF8qBqguO5NfbI/X Cotn/lY3Q+NZrIcUpgTyWCah4MF5RBySwYLFM/rGrL9uyG6l912anVHacYnNUsP4EsVUN/daIoR 6WyWUblc/4V6xhCmZbwwtfQ== X-Google-Smtp-Source: AGHT+IEhnGx4Z5EioPu9R9SzxcAGfn72t0MQB9mOLaN9BEycLK0Unt6J+YjxJNJg9wU++DwSP7macxTmZ+HqWzf+ X-Received: from wmbep11.prod.google.com ([2002:a05:600c:840b:b0:43c:ef7b:ffac]) (user=vdonnefort job=prod-delivery.src-stubby-dispatcher) by 2002:a05:600c:3554:b0:442:cd13:f15d with SMTP id 5b1f17b1804b1-442fd67197dmr147790395e9.29.1747731193204; Tue, 20 May 2025 01:53:13 -0700 (PDT) Date: Tue, 20 May 2025 09:51:58 +0100 In-Reply-To: <20250520085201.3059786-1-vdonnefort@google.com> Precedence: bulk X-Mailing-List: linux-kernel@vger.kernel.org List-Id: List-Subscribe: List-Unsubscribe: Mime-Version: 1.0 References: <20250520085201.3059786-1-vdonnefort@google.com> X-Mailer: git-send-email 2.49.0.1143.g0be31eac6b-goog Message-ID: <20250520085201.3059786-8-vdonnefort@google.com> Subject: [PATCH v5 07/10] KVM: arm64: Convert pkvm_mappings to interval tree From: Vincent Donnefort To: maz@kernel.org, oliver.upton@linux.dev, joey.gouly@arm.com, suzuki.poulose@arm.com, yuzenghui@huawei.com, catalin.marinas@arm.com, will@kernel.org Cc: qperret@google.com, linux-arm-kernel@lists.infradead.org, kvmarm@lists.linux.dev, linux-kernel@vger.kernel.org, kernel-team@android.com, Vincent Donnefort Content-Transfer-Encoding: quoted-printable Content-Type: text/plain; charset="utf-8" From: Quentin Perret In preparation for supporting stage-2 huge mappings for np-guest, let's convert pgt.pkvm_mappings to an interval tree. No functional change intended. Suggested-by: Vincent Donnefort Signed-off-by: Quentin Perret Signed-off-by: Vincent Donnefort diff --git a/arch/arm64/include/asm/kvm_pgtable.h b/arch/arm64/include/asm/= kvm_pgtable.h index 6b9d274052c7..1b43bcd2a679 100644 --- a/arch/arm64/include/asm/kvm_pgtable.h +++ b/arch/arm64/include/asm/kvm_pgtable.h @@ -413,7 +413,7 @@ static inline bool kvm_pgtable_walk_lock_held(void) */ struct kvm_pgtable { union { - struct rb_root pkvm_mappings; + struct rb_root_cached pkvm_mappings; struct { u32 ia_bits; s8 start_level; diff --git a/arch/arm64/include/asm/kvm_pkvm.h b/arch/arm64/include/asm/kvm= _pkvm.h index d91bfcf2db56..da75d41c948c 100644 --- a/arch/arm64/include/asm/kvm_pkvm.h +++ b/arch/arm64/include/asm/kvm_pkvm.h @@ -173,6 +173,7 @@ struct pkvm_mapping { struct rb_node node; u64 gfn; u64 pfn; + u64 __subtree_last; /* Internal member for interval tree */ }; =20 int pkvm_pgtable_stage2_init(struct kvm_pgtable *pgt, struct kvm_s2_mmu *m= mu, diff --git a/arch/arm64/kvm/pkvm.c b/arch/arm64/kvm/pkvm.c index 057874bbe3e1..8a1a2faf66a8 100644 --- a/arch/arm64/kvm/pkvm.c +++ b/arch/arm64/kvm/pkvm.c @@ -5,6 +5,7 @@ */ =20 #include +#include #include #include #include @@ -256,80 +257,67 @@ static int __init finalize_pkvm(void) } device_initcall_sync(finalize_pkvm); =20 -static int cmp_mappings(struct rb_node *node, const struct rb_node *parent) +static u64 __pkvm_mapping_start(struct pkvm_mapping *m) { - struct pkvm_mapping *a =3D rb_entry(node, struct pkvm_mapping, node); - struct pkvm_mapping *b =3D rb_entry(parent, struct pkvm_mapping, node); - - if (a->gfn < b->gfn) - return -1; - if (a->gfn > b->gfn) - return 1; - return 0; + return m->gfn * PAGE_SIZE; } =20 -static struct rb_node *find_first_mapping_node(struct rb_root *root, u64 g= fn) +static u64 __pkvm_mapping_end(struct pkvm_mapping *m) { - struct rb_node *node =3D root->rb_node, *prev =3D NULL; - struct pkvm_mapping *mapping; - - while (node) { - mapping =3D rb_entry(node, struct pkvm_mapping, node); - if (mapping->gfn =3D=3D gfn) - return node; - prev =3D node; - node =3D (gfn < mapping->gfn) ? node->rb_left : node->rb_right; - } - - return prev; + return (m->gfn + 1) * PAGE_SIZE - 1; } =20 +INTERVAL_TREE_DEFINE(struct pkvm_mapping, node, u64, __subtree_last, + __pkvm_mapping_start, __pkvm_mapping_end, static, + pkvm_mapping); + /* - * __tmp is updated to rb_next(__tmp) *before* entering the body of the lo= op to allow freeing - * of __map inline. + * __tmp is updated to iter_first(pkvm_mappings) *before* entering the bod= y of the loop to allow + * freeing of __map inline. */ #define for_each_mapping_in_range_safe(__pgt, __start, __end, __map) \ - for (struct rb_node *__tmp =3D find_first_mapping_node(&(__pgt)->pkvm_map= pings, \ - ((__start) >> PAGE_SHIFT)); \ + for (struct pkvm_mapping *__tmp =3D pkvm_mapping_iter_first(&(__pgt)->pkv= m_mappings, \ + __start, __end - 1); \ __tmp && ({ \ - __map =3D rb_entry(__tmp, struct pkvm_mapping, node); \ - __tmp =3D rb_next(__tmp); \ + __map =3D __tmp; \ + __tmp =3D pkvm_mapping_iter_next(__map, __start, __end - 1); \ true; \ }); \ - ) \ - if (__map->gfn < ((__start) >> PAGE_SHIFT)) \ - continue; \ - else if (__map->gfn >=3D ((__end) >> PAGE_SHIFT)) \ - break; \ - else + ) =20 int pkvm_pgtable_stage2_init(struct kvm_pgtable *pgt, struct kvm_s2_mmu *m= mu, struct kvm_pgtable_mm_ops *mm_ops) { - pgt->pkvm_mappings =3D RB_ROOT; + pgt->pkvm_mappings =3D RB_ROOT_CACHED; pgt->mmu =3D mmu; =20 return 0; } =20 -void pkvm_pgtable_stage2_destroy(struct kvm_pgtable *pgt) +static int __pkvm_pgtable_stage2_unmap(struct kvm_pgtable *pgt, u64 start,= u64 end) { struct kvm *kvm =3D kvm_s2_mmu_to_kvm(pgt->mmu); pkvm_handle_t handle =3D kvm->arch.pkvm.handle; struct pkvm_mapping *mapping; - struct rb_node *node; + int ret; =20 if (!handle) - return; + return 0; =20 - node =3D rb_first(&pgt->pkvm_mappings); - while (node) { - mapping =3D rb_entry(node, struct pkvm_mapping, node); - kvm_call_hyp_nvhe(__pkvm_host_unshare_guest, handle, mapping->gfn); - node =3D rb_next(node); - rb_erase(&mapping->node, &pgt->pkvm_mappings); + for_each_mapping_in_range_safe(pgt, start, end, mapping) { + ret =3D kvm_call_hyp_nvhe(__pkvm_host_unshare_guest, handle, mapping->gf= n, 1); + if (WARN_ON(ret)) + return ret; + pkvm_mapping_remove(mapping, &pgt->pkvm_mappings); kfree(mapping); } + + return 0; +} + +void pkvm_pgtable_stage2_destroy(struct kvm_pgtable *pgt) +{ + __pkvm_pgtable_stage2_unmap(pgt, 0, ~(0ULL)); } =20 int pkvm_pgtable_stage2_map(struct kvm_pgtable *pgt, u64 addr, u64 size, @@ -357,28 +345,16 @@ int pkvm_pgtable_stage2_map(struct kvm_pgtable *pgt, = u64 addr, u64 size, swap(mapping, cache->mapping); mapping->gfn =3D gfn; mapping->pfn =3D pfn; - WARN_ON(rb_find_add(&mapping->node, &pgt->pkvm_mappings, cmp_mappings)); + pkvm_mapping_insert(mapping, &pgt->pkvm_mappings); =20 return ret; } =20 int pkvm_pgtable_stage2_unmap(struct kvm_pgtable *pgt, u64 addr, u64 size) { - struct kvm *kvm =3D kvm_s2_mmu_to_kvm(pgt->mmu); - pkvm_handle_t handle =3D kvm->arch.pkvm.handle; - struct pkvm_mapping *mapping; - int ret =3D 0; - - lockdep_assert_held_write(&kvm->mmu_lock); - for_each_mapping_in_range_safe(pgt, addr, addr + size, mapping) { - ret =3D kvm_call_hyp_nvhe(__pkvm_host_unshare_guest, handle, mapping->gf= n, 1); - if (WARN_ON(ret)) - break; - rb_erase(&mapping->node, &pgt->pkvm_mappings); - kfree(mapping); - } + lockdep_assert_held_write(&kvm_s2_mmu_to_kvm(pgt->mmu)->mmu_lock); =20 - return ret; + return __pkvm_pgtable_stage2_unmap(pgt, addr, addr + size); } =20 int pkvm_pgtable_stage2_wrprotect(struct kvm_pgtable *pgt, u64 addr, u64 s= ize) --=20 2.49.0.1143.g0be31eac6b-goog