git: 014a45493865 - main - pctrie: add a locked pctrie_lookup_range

The branch main has been updated by dougm:

URL: https://cgit.FreeBSD.org/src/commit/?id=014a45493865f217c3c0ddd240c2260913ba7f76

commit 014a45493865f217c3c0ddd240c2260913ba7f76
Author:     Doug Moore <dougm@FreeBSD.org>
AuthorDate: 2025-04-30 17:11:34 +0000
Commit:     Doug Moore <dougm@FreeBSD.org>
CommitDate: 2025-04-30 17:11:34 +0000

    pctrie: add a locked pctrie_lookup_range
    
    Add a locked version of pctrie_lookup_range_unlocked.
    
    Reviewed by:    markj
    Differential Revision:  https://reviews.freebsd.org/D50088
---
 sys/kern/subr_pctrie.c | 48 ++++++++++++++++++++++++++++++++++++++----------
 sys/sys/pctrie.h       | 14 ++++++++++++++
 2 files changed, 52 insertions(+), 10 deletions(-)

diff --git a/sys/kern/subr_pctrie.c b/sys/kern/subr_pctrie.c
index feb29cf82330..be1d57b4931f 100644
--- a/sys/kern/subr_pctrie.c
+++ b/sys/kern/subr_pctrie.c
@@ -609,22 +609,19 @@ pctrie_iter_prev(struct pctrie_iter *it)
 
 /*
  * Returns the number of contiguous, non-NULL entries read into the value[]
- * array, without requiring an external lock.  These entries *may* never have
- * been in the pctrie all at one time, but for a series of times t0, t1, t2,
- * ..., with ti <= t(i+1), value[i] was in the trie at time ti.
+ * array, starting at index.
  */
-int
-pctrie_lookup_range_unlocked(struct pctrie *ptree, uint64_t index,
-    uint64_t *value[], int count, smr_t smr)
+static __always_inline int
+_pctrie_lookup_range(struct pctrie *ptree, uint64_t index, uint64_t *value[],
+    int count, smr_t smr, enum pctrie_access access)
 {
 	struct pctrie_node *parent, *node;
 	int base, end, i;
 
 	parent = NULL;
-	smr_enter(smr);
 	for (i = 0; i < count;) {
 		node = _pctrie_lookup_node(ptree, parent, index + i, &parent,
-		    smr, PCTRIE_SMR);
+		    smr, access);
 		value[i] = pctrie_match_value(node, index + i);
 		if (value[i] == NULL)
 			break;
@@ -635,7 +632,7 @@ pctrie_lookup_range_unlocked(struct pctrie *ptree, uint64_t index,
 		end = MIN(count, i + PCTRIE_COUNT - base);
 		while (i < end) {
 			node = pctrie_node_load(&parent->pn_child[base++],
-			    smr, PCTRIE_SMR);
+			    smr, access);
 			value[i] = pctrie_toval(node);
 			if (value[i] == NULL)
 				break;
@@ -644,10 +641,41 @@ pctrie_lookup_range_unlocked(struct pctrie *ptree, uint64_t index,
 		if (i < end)
 			break;
 	}
-	smr_exit(smr);
 	return (i);
 }
 
+/*
+ * Returns the number of contiguous, non-NULL entries read into the value[]
+ * array, starting at index, assuming access is externally synchronized by a
+ * lock.
+ */
+int
+pctrie_lookup_range(struct pctrie *ptree, uint64_t index,
+    uint64_t *value[], int count)
+{
+	return (_pctrie_lookup_range(ptree, index, value, count, NULL,
+	    PCTRIE_LOCKED));
+}
+
+/*
+ * Returns the number of contiguous, non-NULL entries read into the value[]
+ * array, starting at index, without requiring an external lock.  These entries
+ * *may* never have been in the pctrie all at one time, but for a series of
+ * times t0, t1, t2, ..., with ti <= t(i+1), value[i] was in the trie at time
+ * ti.
+ */
+int
+pctrie_lookup_range_unlocked(struct pctrie *ptree, uint64_t index,
+    uint64_t *value[], int count, smr_t smr)
+{
+	int res;
+
+	smr_enter(smr);
+	res = _pctrie_lookup_range(ptree, index, value, count, smr, PCTRIE_SMR);
+	smr_exit(smr);
+	return (res);
+}
+
 /*
  * Find first leaf >= index, and fill iter with the path to the parent of that
  * leaf.  Return NULL if there is no such leaf less than limit.
diff --git a/sys/sys/pctrie.h b/sys/sys/pctrie.h
index 01d9f34f11b9..0ccd4ec1e42e 100644
--- a/sys/sys/pctrie.h
+++ b/sys/sys/pctrie.h
@@ -215,6 +215,18 @@ name##_PCTRIE_LOOKUP(struct pctrie *ptree, uint64_t key)		\
 	return name##_PCTRIE_VAL2PTR(pctrie_lookup(ptree, key));	\
 }									\
 									\
+static __inline __unused int						\
+name##_PCTRIE_LOOKUP_RANGE(struct pctrie *ptree, uint64_t key,		\
+     struct type *value[], int count) 					\
+{									\
+	uint64_t **data = (uint64_t **)value;				\
+									\
+	count = pctrie_lookup_range(ptree, key, data, count);		\
+	for (int i = 0; i < count; i++)					\
+		value[i] = name##_PCTRIE_NZVAL2PTR(data[i]);		\
+	return (count);							\
+}									\
+									\
 static __inline __unused struct type *					\
 name##_PCTRIE_LOOKUP_LE(struct pctrie *ptree, uint64_t key)		\
 {									\
@@ -383,6 +395,8 @@ void		pctrie_insert_node(uint64_t *val, struct pctrie_node *parent,
 uint64_t	*pctrie_lookup(struct pctrie *ptree, uint64_t key);
 uint64_t	*pctrie_lookup_unlocked(struct pctrie *ptree, uint64_t key,
 		    smr_t smr);
+int		pctrie_lookup_range(struct pctrie *ptree,
+		    uint64_t index, uint64_t *value[], int count);
 int		pctrie_lookup_range_unlocked(struct pctrie *ptree,
 		    uint64_t index, uint64_t *value[], int count, smr_t smr);
 uint64_t	*pctrie_iter_lookup(struct pctrie_iter *it, uint64_t index);