From nobody Thu Sep 19 16:50:52 2024 X-Original-To: dev-commits-src-main@mlmmj.nyi.freebsd.org Received: from mx1.freebsd.org (mx1.freebsd.org [IPv6:2610:1c1:1:606c::19:1]) by mlmmj.nyi.freebsd.org (Postfix) with ESMTP id 4X8hNY0szzz5XJKq; Thu, 19 Sep 2024 16:50:53 +0000 (UTC) (envelope-from git@FreeBSD.org) Received: from mxrelay.nyi.freebsd.org (mxrelay.nyi.freebsd.org [IPv6:2610:1c1:1:606c::19:3]) (using TLSv1.3 with cipher TLS_AES_256_GCM_SHA384 (256/256 bits) key-exchange X25519 server-signature RSA-PSS (4096 bits) server-digest SHA256 client-signature RSA-PSS (4096 bits) client-digest SHA256) (Client CN "mxrelay.nyi.freebsd.org", Issuer "R11" (verified OK)) by mx1.freebsd.org (Postfix) with ESMTPS id 4X8hNY0Nrxz3y1P; Thu, 19 Sep 2024 16:50:53 +0000 (UTC) (envelope-from git@FreeBSD.org) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=freebsd.org; s=dkim; t=1726764653; h=from:from:reply-to:subject:subject:date:date:message-id:message-id: to:to:cc:mime-version:mime-version:content-type:content-type: content-transfer-encoding:content-transfer-encoding; bh=7BaregfzyCdVy9HRaflFlXIV74IdTQtEYiIkLWNp/yE=; b=X805nB1/o3B2wRlMhymJ3XFjvSn+JWltDTV4kYznOIMXkiFyNIIdb11zZitkuKX872MUWS 2Ul/4DNvpy9PaVf5wB47gFNF/AVnvaVRNyOIXheZs5jWZy7BOKYkzf+eDkp0177Qr8Rc6Q sblLQaZxmlyyeRPtHKbiKrlvJWPLQeXk88FBislO0Ei6g35Bgu930UsI7k+zxEIXzq/cTd UZbA2z53uaiU+RLWepjYoXrOOB1VNXRoiOJtqbwta9qVlrrARREyLCiPpQqyoZ6Jir+Pb+ ZWFEaREEMFSap4c+M4X+aF2avAwqMX1oHtLtLVaUJT03VxwqzRwCqzCXMHOo8g== ARC-Seal: i=1; s=dkim; d=freebsd.org; t=1726764653; a=rsa-sha256; cv=none; b=yo3QMIbWZf047B0Xp7t8esw5NhAnyXnzrREGsL069X2s1wUG7lf1wMiM0FNFqFIJN8cdAh bFp50S48kjnvIHA3363/tGlJAwcYOH91g2IdGDk/1oC1FrcdzwNQ/QNvVoKMwbJgNWJGPP UxRnk8VZn9WxQhJQ3D+P0lVYd0RT6Vn5LRP6kts3NE9vUlDiAobrhgmKuoVQ+wiEmyKF7+ AD1ltq9U92RJO/yTETaja36jr/zkQEn8u/kx5dxxGg/qlzfcML76d0ZUNl9ucSKRu8UP5r jL06D+/vTibVUTWz8snqqY9k6eAS/PtBMD3a75pY9qNMyQgTDpUehpvHnJBN2Q== ARC-Authentication-Results: i=1; mx1.freebsd.org; none ARC-Message-Signature: i=1; a=rsa-sha256; c=relaxed/relaxed; d=freebsd.org; s=dkim; t=1726764653; h=from:from:reply-to:subject:subject:date:date:message-id:message-id: to:to:cc:mime-version:mime-version:content-type:content-type: content-transfer-encoding:content-transfer-encoding; bh=7BaregfzyCdVy9HRaflFlXIV74IdTQtEYiIkLWNp/yE=; b=p0fjVVgFNJjLHOmVHLAJG2ZSreEK5E+L5Is5nvneoU41Lbwb4drSJj43sBPzStG7nWc6DZ 2M1ooQuIcSvdRPI9bzgGp1XUBRVfdx0RrgF5gtnnA0d7o5c7i9jL35p8P3MJaUVk7aJq9n JncL0CxeJHum33qC0WjtQOV+vvHwxnh7s1dosJcCen/JcWVRtXULKa0YMSbzPk71Z5Lqv0 bDKIHVPYs1HmjV9T09mxAUgUYVCMROZnGpaDIBbP1bvdNPiz9MucgSmxbXqHZjEA/qGQhG 0EtjTSKEmCfyZcPPIYVIEmdq+vaHsNmmUrPu556NFqcoH1suo+hmBtUgOHf3lw== Received: from gitrepo.freebsd.org (gitrepo.freebsd.org [IPv6:2610:1c1:1:6068::e6a:5]) (using TLSv1.3 with cipher TLS_AES_256_GCM_SHA384 (256/256 bits) key-exchange X25519 server-signature RSA-PSS (4096 bits) server-digest SHA256) (Client did not present a certificate) by mxrelay.nyi.freebsd.org (Postfix) with ESMTPS id 4X8hNY003bz1CcK; Thu, 19 Sep 2024 16:50:52 +0000 (UTC) (envelope-from git@FreeBSD.org) Received: from gitrepo.freebsd.org ([127.0.1.44]) by gitrepo.freebsd.org (8.18.1/8.18.1) with ESMTP id 48JGoq9U085692; Thu, 19 Sep 2024 16:50:52 GMT (envelope-from git@gitrepo.freebsd.org) Received: (from git@localhost) by gitrepo.freebsd.org (8.18.1/8.18.1/Submit) id 48JGoqn5085689; Thu, 19 Sep 2024 16:50:52 GMT (envelope-from git) Date: Thu, 19 Sep 2024 16:50:52 GMT Message-Id: <202409191650.48JGoqn5085689@gitrepo.freebsd.org> To: src-committers@FreeBSD.org, dev-commits-src-all@FreeBSD.org, dev-commits-src-main@FreeBSD.org From: Doug Moore Subject: git: 450a6690f557 - main - vm_radix: offer pctrie_iterator access List-Id: Commit messages for the main branch of the src repository List-Archive: https://lists.freebsd.org/archives/dev-commits-src-main List-Help: List-Post: List-Subscribe: List-Unsubscribe: X-BeenThere: dev-commits-src-main@freebsd.org Sender: owner-dev-commits-src-main@FreeBSD.org MIME-Version: 1.0 Content-Type: text/plain; charset=utf-8 Content-Transfer-Encoding: 8bit X-Git-Committer: dougm X-Git-Repository: src X-Git-Refname: refs/heads/main X-Git-Reftype: branch X-Git-Commit: 450a6690f557493bd33d8f3666b22ddc5150703b Auto-Submitted: auto-generated The branch main has been updated by dougm: URL: https://cgit.FreeBSD.org/src/commit/?id=450a6690f557493bd33d8f3666b22ddc5150703b commit 450a6690f557493bd33d8f3666b22ddc5150703b Author: Doug Moore AuthorDate: 2024-09-19 16:49:40 +0000 Commit: Doug Moore CommitDate: 2024-09-19 16:49:40 +0000 vm_radix: offer pctrie_iterator access Add to the vm_radix and vm_page interfaces methods to use pctrie iterators with vm_radix tries. Reviewed by: markj Differential Revision: https://reviews.freebsd.org/D46663 --- sys/vm/vm_page.c | 58 +++++++++++++++++++++++++ sys/vm/vm_page.h | 5 +++ sys/vm/vm_radix.h | 123 ++++++++++++++++++++++++++++++++++++++++++++++++++++-- 3 files changed, 183 insertions(+), 3 deletions(-) diff --git a/sys/vm/vm_page.c b/sys/vm/vm_page.c index d21cc38f5e39..ba32a9eb9e63 100644 --- a/sys/vm/vm_page.c +++ b/sys/vm/vm_page.c @@ -1706,6 +1706,48 @@ vm_page_lookup(vm_object_t object, vm_pindex_t pindex) return (vm_radix_lookup(&object->rtree, pindex)); } +/* + * vm_page_iter_init: + * + * Initialize iterator for vm pages. + */ +void +vm_page_iter_init(struct pctrie_iter *pages, vm_object_t object) +{ + + VM_OBJECT_ASSERT_LOCKED(object); + vm_radix_iter_init(pages, &object->rtree); +} + +/* + * vm_page_iter_init: + * + * Initialize iterator for vm pages. + */ +void +vm_page_iter_limit_init(struct pctrie_iter *pages, vm_object_t object, + vm_pindex_t limit) +{ + + VM_OBJECT_ASSERT_LOCKED(object); + vm_radix_iter_limit_init(pages, &object->rtree, limit); +} + +/* + * vm_page_iter_lookup: + * + * Returns the page associated with the object/offset pair specified, and + * stores the path to its position; if none is found, NULL is returned. + * + * The iter pctrie must be locked. + */ +vm_page_t +vm_page_iter_lookup(struct pctrie_iter *pages, vm_pindex_t pindex) +{ + + return (vm_radix_iter_lookup(pages, pindex)); +} + /* * vm_page_lookup_unlocked: * @@ -1790,6 +1832,22 @@ vm_page_find_least(vm_object_t object, vm_pindex_t pindex) return (m); } +/* + * vm_page_iter_lookup_ge: + * + * Returns the page associated with the object with least pindex + * greater than or equal to the parameter pindex, or NULL. Initializes the + * iterator to point to that page. + * + * The iter pctrie must be locked. + */ +vm_page_t +vm_page_iter_lookup_ge(struct pctrie_iter *pages, vm_pindex_t pindex) +{ + + return (vm_radix_iter_lookup_ge(pages, pindex)); +} + /* * Returns the given page's successor (by pindex) within the object if it is * resident; if none is found, NULL is returned. diff --git a/sys/vm/vm_page.h b/sys/vm/vm_page.h index 07a6c98c8ee8..a69155e50723 100644 --- a/sys/vm/vm_page.h +++ b/sys/vm/vm_page.h @@ -471,6 +471,7 @@ extern struct mtx_padalign pa_lock[]; #include #include +struct pctrie_iter; /* * Each pageable resident page falls into one of five lists: @@ -642,6 +643,7 @@ void vm_page_deactivate_noreuse(vm_page_t); void vm_page_dequeue(vm_page_t m); void vm_page_dequeue_deferred(vm_page_t m); vm_page_t vm_page_find_least(vm_object_t, vm_pindex_t); +vm_page_t vm_page_iter_lookup_ge(struct pctrie_iter *, vm_pindex_t); void vm_page_free_invalid(vm_page_t); vm_page_t vm_page_getfake(vm_paddr_t paddr, vm_memattr_t memattr); void vm_page_initfake(vm_page_t m, vm_paddr_t paddr, vm_memattr_t memattr); @@ -651,6 +653,9 @@ int vm_page_insert (vm_page_t, vm_object_t, vm_pindex_t); void vm_page_invalid(vm_page_t m); void vm_page_launder(vm_page_t m); vm_page_t vm_page_lookup(vm_object_t, vm_pindex_t); +void vm_page_iter_init(struct pctrie_iter *, vm_object_t); +void vm_page_iter_limit_init(struct pctrie_iter *, vm_object_t, vm_pindex_t); +vm_page_t vm_page_iter_lookup(struct pctrie_iter *, vm_pindex_t); vm_page_t vm_page_lookup_unlocked(vm_object_t, vm_pindex_t); vm_page_t vm_page_next(vm_page_t m); void vm_page_pqbatch_drain(void); diff --git a/sys/vm/vm_radix.h b/sys/vm/vm_radix.h index dcacf1a5d3fc..f2e297b10641 100644 --- a/sys/vm/vm_radix.h +++ b/sys/vm/vm_radix.h @@ -56,8 +56,8 @@ vm_radix_is_empty(struct vm_radix *rtree) return (pctrie_is_empty(&rtree->rt_trie)); } -PCTRIE_DEFINE_SMR(VM_RADIX, vm_page, pindex, vm_radix_node_alloc, vm_radix_node_free, - vm_radix_smr); +PCTRIE_DEFINE_SMR(VM_RADIX, vm_page, pindex, vm_radix_node_alloc, + vm_radix_node_free, vm_radix_smr); /* * Inserts the key-value pair into the trie. @@ -111,6 +111,49 @@ vm_radix_lookup_unlocked(struct vm_radix *rtree, vm_pindex_t index) return (VM_RADIX_PCTRIE_LOOKUP_UNLOCKED(&rtree->rt_trie, index)); } +/* + * Initialize an iterator for vm_radix. + */ +static __inline void +vm_radix_iter_init(struct pctrie_iter *pages, struct vm_radix *rtree) +{ + pctrie_iter_init(pages, &rtree->rt_trie); +} + +/* + * Initialize an iterator for vm_radix. + */ +static __inline void +vm_radix_iter_limit_init(struct pctrie_iter *pages, struct vm_radix *rtree, + vm_pindex_t limit) +{ + pctrie_iter_limit_init(pages, &rtree->rt_trie, limit); +} + +/* + * Returns the value stored at the index. + * Requires that access be externally synchronized by a lock. + * + * If the index is not present, NULL is returned. + */ +static __inline vm_page_t +vm_radix_iter_lookup(struct pctrie_iter *pages, vm_pindex_t index) +{ + return (VM_RADIX_PCTRIE_ITER_LOOKUP(pages, index)); +} + +/* + * Returns the value stored 'stride' steps beyond the current position. + * Requires that access be externally synchronized by a lock. + * + * If the index is not present, NULL is returned. + */ +static __inline vm_page_t +vm_radix_iter_stride(struct pctrie_iter *pages, int stride) +{ + return (VM_RADIX_PCTRIE_ITER_STRIDE(pages, stride)); +} + /* * Returns the page with the least pindex that is greater than or equal to the * specified pindex, or NULL if there are no such pages. @@ -146,7 +189,7 @@ vm_radix_remove(struct vm_radix *rtree, vm_pindex_t index) } /* - * Remove and free all the nodes from the radix tree. + * Reclaim all the interior nodes from the radix tree. */ static __inline void vm_radix_reclaim_allnodes(struct vm_radix *rtree) @@ -154,6 +197,80 @@ vm_radix_reclaim_allnodes(struct vm_radix *rtree) VM_RADIX_PCTRIE_RECLAIM(&rtree->rt_trie); } +/* + * Initialize an iterator pointing to the page with the least pindex that is + * greater than or equal to the specified pindex, or NULL if there are no such + * pages. Return the page. + * + * Requires that access be externally synchronized by a lock. + */ +static __inline vm_page_t +vm_radix_iter_lookup_ge(struct pctrie_iter *pages, vm_pindex_t index) +{ + return (VM_RADIX_PCTRIE_ITER_LOOKUP_GE(pages, index)); +} + +/* + * Update the iterator to point to the page with the least pindex that is 'jump' + * or more greater than or equal to the current pindex, or NULL if there are no + * such pages. Return the page. + * + * Requires that access be externally synchronized by a lock. + */ +static __inline vm_page_t +vm_radix_iter_jump(struct pctrie_iter *pages, vm_pindex_t jump) +{ + return (VM_RADIX_PCTRIE_ITER_JUMP_GE(pages, jump)); +} + +/* + * Update the iterator to point to the page with the least pindex that is one or + * more greater than the current pindex, or NULL if there are no such pages. + * Return the page. + * + * Requires that access be externally synchronized by a lock. + */ +static __inline vm_page_t +vm_radix_iter_step(struct pctrie_iter *pages) +{ + return (VM_RADIX_PCTRIE_ITER_STEP_GE(pages)); +} + +/* + * Update the iterator to point to the page with the pindex that is one greater + * than the current pindex, or NULL if there is no such page. Return the page. + * + * Requires that access be externally synchronized by a lock. + */ +static __inline vm_page_t +vm_radix_iter_next(struct pctrie_iter *pages) +{ + return (VM_RADIX_PCTRIE_ITER_NEXT(pages)); +} + +/* + * Update the iterator to point to the page with the pindex that is one less + * than the current pindex, or NULL if there is no such page. Return the page. + * + * Requires that access be externally synchronized by a lock. + */ +static __inline vm_page_t +vm_radix_iter_prev(struct pctrie_iter *pages) +{ + return (VM_RADIX_PCTRIE_ITER_PREV(pages)); +} + +/* + * Return the current page. + * + * Requires that access be externally synchronized by a lock. + */ +static __inline vm_page_t +vm_radix_iter_page(struct pctrie_iter *pages) +{ + return (VM_RADIX_PCTRIE_ITER_VALUE(pages)); +} + /* * Replace an existing page in the trie with another one. * Panics if there is not an old page in the trie at the new page's index.