git: 450a6690f557 - main - vm_radix: offer pctrie_iterator access
- Go to: [ bottom of page ] [ top of archives ] [ this month ]
Date: Thu, 19 Sep 2024 16:50:52 UTC
The branch main has been updated by dougm:
URL: https://cgit.FreeBSD.org/src/commit/?id=450a6690f557493bd33d8f3666b22ddc5150703b
commit 450a6690f557493bd33d8f3666b22ddc5150703b
Author: Doug Moore <dougm@FreeBSD.org>
AuthorDate: 2024-09-19 16:49:40 +0000
Commit: Doug Moore <dougm@FreeBSD.org>
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 <sys/kassert.h>
#include <machine/atomic.h>
+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.