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 Received: from bombadil.infradead.org (bombadil.infradead.org [198.137.202.133]) (using TLSv1.2 with cipher ECDHE-RSA-AES256-GCM-SHA384 (256/256 bits)) (No client certificate requested) by smtp.lore.kernel.org (Postfix) with ESMTPS id 81846C3ABC9 for ; Fri, 16 May 2025 13:18:04 +0000 (UTC) DKIM-Signature: v=1; a=rsa-sha256; q=dns/txt; c=relaxed/relaxed; d=lists.infradead.org; s=bombadil.20210309; h=Sender:List-Subscribe:List-Help :List-Post:List-Archive:List-Unsubscribe:List-Id:Content-Type:MIME-Version: References:In-Reply-To:Subject:Cc:To:From:Message-ID:Date:Reply-To: Content-Transfer-Encoding:Content-ID:Content-Description:Resent-Date: Resent-From:Resent-Sender:Resent-To:Resent-Cc:Resent-Message-ID:List-Owner; bh=Hv8SkidEBXrQXpGtrDlcKH7sGC3rLo1VBE5Ufxh9jOs=; b=is9btmDZWMFdgP2uDbBELnzveW N3iXveL6HNwRZicF5suTCyllhf8RkvbbXFdFMiQ0ZM98cWzDsmaj5EjS/5bPteyZ7+gm2E7pQgMDZ m9//oUNQNdal1AA3QUKL6mdl9z9EU/o5TtdJEorXUwIRRFf9QD/KTgryM+JjiTdC1n7IhPJAF6y53 MyPPkzymHwG1kRa2+TRd1ZP35bwBEeTcMv4VXW8jsZl5nhBvoC0YE+0vvCjMxaVpFZdzphrCKSZfO zPZDqwIG4gyQb+p8Grxn5oOjVgxr+pt1KrA6ZUWwqPRSV4j3TsMYVD/PC/cI7ndfskfobNx7shgoI I/q1UuEw==; Received: from localhost ([::1] helo=bombadil.infradead.org) by bombadil.infradead.org with esmtp (Exim 4.98.2 #2 (Red Hat Linux)) id 1uFuwl-00000003UO2-47sK; Fri, 16 May 2025 13:17:55 +0000 Received: from dfw.source.kernel.org ([2604:1380:4641:c500::1]) by bombadil.infradead.org with esmtps (Exim 4.98.2 #2 (Red Hat Linux)) id 1uFuuj-00000003U9O-05og for linux-arm-kernel@lists.infradead.org; Fri, 16 May 2025 13:15:50 +0000 Received: from smtp.kernel.org (transwarp.subspace.kernel.org [100.75.92.58]) by dfw.source.kernel.org (Postfix) with ESMTP id C44C25C148F; Fri, 16 May 2025 13:13:30 +0000 (UTC) Received: by smtp.kernel.org (Postfix) with ESMTPSA id B674BC4CEE4; Fri, 16 May 2025 13:15:47 +0000 (UTC) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/simple; d=kernel.org; s=k20201202; t=1747401347; bh=aIVuP15lLI18U0B27tPS187TYHrY2xiLduyapf9Ur+w=; h=Date:From:To:Cc:Subject:In-Reply-To:References:From; b=WNzvVjlXL2rom+TaLrRhnGLzOtPPIqPH2Sbaww3H4+/4s0Qab7I7VpvL7EcI1G/RF zmDbBDdnWAQtcWwrJe5DkLutsVGA0NpDDFFXf+3ZnXVgI+f6tI92fJD1EwVyMIfsW1 w+5RkzWnstATQtjzh8qEZyLM3Sqbv2fXqWqnHZdRn9fVXMCIQ7Pst+4XdkI8AZCesZ VYj45a3d2Gi4dFdKWQxiQ7dFXXCWJZbLBKW9Qq9bQua0ohw8+gKzOkOPaGcoE5tT/d 0jc/vxhwoXL1VzKAAeOKplXupXTuA+rtwdNxGTShHGod077hHA1Uwss0N62W9dIrbX uDO/SeJiH+5hQ== Received: from sofa.misterjones.org ([185.219.108.64] helo=goblin-girl.misterjones.org) by disco-boy.misterjones.org with esmtpsa (TLS1.3) tls TLS_ECDHE_RSA_WITH_AES_256_GCM_SHA384 (Exim 4.95) (envelope-from ) id 1uFuuf-00FYy4-Nm; Fri, 16 May 2025 14:15:45 +0100 Date: Fri, 16 May 2025 14:15:45 +0100 Message-ID: <867c2gg0hq.wl-maz@kernel.org> From: Marc Zyngier To: Vincent Donnefort Cc: oliver.upton@linux.dev, joey.gouly@arm.com, suzuki.poulose@arm.com, yuzenghui@huawei.com, catalin.marinas@arm.com, will@kernel.org, qperret@google.com, linux-arm-kernel@lists.infradead.org, kvmarm@lists.linux.dev, linux-kernel@vger.kernel.org, kernel-team@android.com Subject: Re: [PATCH v4 07/10] KVM: arm64: Convert pkvm_mappings to interval tree In-Reply-To: <20250509131706.2336138-8-vdonnefort@google.com> References: <20250509131706.2336138-1-vdonnefort@google.com> <20250509131706.2336138-8-vdonnefort@google.com> User-Agent: Wanderlust/2.15.9 (Almost Unreal) SEMI-EPG/1.14.7 (Harue) FLIM-LB/1.14.9 (=?UTF-8?B?R29qxY0=?=) APEL-LB/10.8 EasyPG/1.0.0 Emacs/30.1 (aarch64-unknown-linux-gnu) MULE/6.0 (HANACHIRUSATO) MIME-Version: 1.0 (generated by SEMI-EPG 1.14.7 - "Harue") Content-Type: text/plain; charset=US-ASCII X-SA-Exim-Connect-IP: 185.219.108.64 X-SA-Exim-Rcpt-To: vdonnefort@google.com, oliver.upton@linux.dev, joey.gouly@arm.com, suzuki.poulose@arm.com, yuzenghui@huawei.com, catalin.marinas@arm.com, will@kernel.org, qperret@google.com, linux-arm-kernel@lists.infradead.org, kvmarm@lists.linux.dev, linux-kernel@vger.kernel.org, kernel-team@android.com X-SA-Exim-Mail-From: maz@kernel.org X-SA-Exim-Scanned: No (on disco-boy.misterjones.org); SAEximRunCond expanded to false X-CRM114-Version: 20100106-BlameMichelson ( TRE 0.8.0 (BSD) ) MR-646709E3 X-CRM114-CacheID: sfid-20250516_061549_170696_80799FF4 X-CRM114-Status: GOOD ( 24.92 ) X-BeenThere: linux-arm-kernel@lists.infradead.org X-Mailman-Version: 2.1.34 Precedence: list List-Id: List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Sender: "linux-arm-kernel" Errors-To: linux-arm-kernel-bounces+linux-arm-kernel=archiver.kernel.org@lists.infradead.org On Fri, 09 May 2025 14:17:03 +0100, Vincent Donnefort wrote: > > 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 */ > }; > > int pkvm_pgtable_stage2_init(struct kvm_pgtable *pgt, struct kvm_s2_mmu *mmu, > diff --git a/arch/arm64/kvm/pkvm.c b/arch/arm64/kvm/pkvm.c > index 057874bbe3e1..6febddbec69e 100644 > --- a/arch/arm64/kvm/pkvm.c > +++ b/arch/arm64/kvm/pkvm.c > @@ -5,6 +5,7 @@ > */ > > #include > +#include > #include > #include > #include > @@ -256,80 +257,63 @@ static int __init finalize_pkvm(void) > } > device_initcall_sync(finalize_pkvm); > > -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 = rb_entry(node, struct pkvm_mapping, node); > - struct pkvm_mapping *b = 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; > } > > -static struct rb_node *find_first_mapping_node(struct rb_root *root, u64 gfn) > +static u64 __pkvm_mapping_end(struct pkvm_mapping *m) > { > - struct rb_node *node = root->rb_node, *prev = NULL; > - struct pkvm_mapping *mapping; > - > - while (node) { > - mapping = rb_entry(node, struct pkvm_mapping, node); > - if (mapping->gfn == gfn) > - return node; > - prev = node; > - node = (gfn < mapping->gfn) ? node->rb_left : node->rb_right; > - } > - > - return prev; > + return (m->gfn + 1) * PAGE_SIZE - 1; > } > > -/* > - * __tmp is updated to rb_next(__tmp) *before* entering the body of the loop to allow freeing > - * of __map inline. > - */ > +INTERVAL_TREE_DEFINE(struct pkvm_mapping, node, u64, __subtree_last, > + __pkvm_mapping_start, __pkvm_mapping_end, static, > + pkvm_mapping); > + > #define for_each_mapping_in_range_safe(__pgt, __start, __end, __map) \ > - for (struct rb_node *__tmp = find_first_mapping_node(&(__pgt)->pkvm_mappings, \ > - ((__start) >> PAGE_SHIFT)); \ > + for (struct pkvm_mapping *__tmp = pkvm_mapping_iter_first(&(__pgt)->pkvm_mappings, \ > + __start, __end - 1); \ > __tmp && ({ \ > - __map = rb_entry(__tmp, struct pkvm_mapping, node); \ > - __tmp = rb_next(__tmp); \ > + __map = __tmp; \ > + __tmp = pkvm_mapping_iter_next(__map, __start, __end - 1); \ > true; \ > }); \ > - ) \ > - if (__map->gfn < ((__start) >> PAGE_SHIFT)) \ > - continue; \ > - else if (__map->gfn >= ((__end) >> PAGE_SHIFT)) \ > - break; \ > - else > + ) The removal of the comment worries me a bit. Is this iterator still safe wrt freeing of the iterator in the loop? Thanks, M. -- Without deviation from the norm, progress is not possible.