git: 2c10bacdf402 - main - rangeset: add next() iteration

The branch main has been updated by dougm:

URL: https://cgit.FreeBSD.org/src/commit/?id=2c10bacdf402c1cf246302303b4dbdce21bf9692

commit 2c10bacdf402c1cf246302303b4dbdce21bf9692
Author:     Doug Moore <dougm@FreeBSD.org>
AuthorDate: 2024-06-06 18:42:31 +0000
Commit:     Doug Moore <dougm@FreeBSD.org>
CommitDate: 2024-06-06 18:42:31 +0000

    rangeset: add next() iteration
    
    Add a method rangeset_next to find the first range that starts at or
    after a given value. Use it to rewrite pmap_pkru_same and
    pmap_bti_same to avoid walking a page at a time over pages in no
    range.
    
    Reviewed by:    andrew, kib
    Differential Revision:  https://reviews.freebsd.org/D45511
---
 sys/amd64/amd64/pmap.c   | 26 +++++++++++++-------------
 sys/arm64/arm64/pmap.c   | 23 ++++++++++++-----------
 sys/kern/subr_rangeset.c |  8 ++++++++
 sys/sys/rangeset.h       |  5 +++++
 4 files changed, 38 insertions(+), 24 deletions(-)

diff --git a/sys/amd64/amd64/pmap.c b/sys/amd64/amd64/pmap.c
index 2f3119aede67..4d4ecc8ea4e2 100644
--- a/sys/amd64/amd64/pmap.c
+++ b/sys/amd64/amd64/pmap.c
@@ -11448,7 +11448,7 @@ pmap_pkru_deassign_all(pmap_t pmap)
 static bool
 pmap_pkru_same(pmap_t pmap, vm_offset_t sva, vm_offset_t eva)
 {
-	struct pmap_pkru_range *ppr, *prev_ppr;
+	struct pmap_pkru_range *next_ppr, *ppr;
 	vm_offset_t va;
 
 	PMAP_LOCK_ASSERT(pmap, MA_OWNED);
@@ -11457,19 +11457,19 @@ pmap_pkru_same(pmap_t pmap, vm_offset_t sva, vm_offset_t eva)
 	    sva >= VM_MAXUSER_ADDRESS)
 		return (true);
 	MPASS(eva <= VM_MAXUSER_ADDRESS);
-	for (va = sva; va < eva; prev_ppr = ppr) {
-		ppr = rangeset_lookup(&pmap->pm_pkru, va);
-		if (va == sva)
-			prev_ppr = ppr;
-		else if ((ppr == NULL) ^ (prev_ppr == NULL))
+	ppr = rangeset_lookup(&pmap->pm_pkru, sva);
+	if (ppr == NULL) {
+		ppr = rangeset_next(&pmap->pm_pkru, sva);
+		return (ppr == NULL ||
+		    ppr->pkru_rs_el.re_start >= eva);
+	}
+	while ((va = ppr->pkru_rs_el.re_end) < eva) {
+		next_ppr = rangeset_next(&pmap->pm_pkru, va);
+		if (next_ppr == NULL ||
+		    va != next_ppr->pkru_rs_el.re_start ||
+		    ppr->pkru_keyidx != next_ppr->pkru_keyidx)
 			return (false);
-		if (ppr == NULL) {
-			va += PAGE_SIZE;
-			continue;
-		}
-		if (prev_ppr->pkru_keyidx != ppr->pkru_keyidx)
-			return (false);
-		va = ppr->pkru_rs_el.re_end;
+		ppr = next_ppr;
 	}
 	return (true);
 }
diff --git a/sys/arm64/arm64/pmap.c b/sys/arm64/arm64/pmap.c
index 8ac7b8f6a135..92c1c824ba4e 100644
--- a/sys/arm64/arm64/pmap.c
+++ b/sys/arm64/arm64/pmap.c
@@ -9274,7 +9274,7 @@ pmap_bti_deassign_all(pmap_t pmap)
 static bool
 pmap_bti_same(pmap_t pmap, vm_offset_t sva, vm_offset_t eva)
 {
-	struct rs_el *prev_rs, *rs;
+	struct rs_el *next_rs, *rs;
 	vm_offset_t va;
 
 	PMAP_LOCK_ASSERT(pmap, MA_OWNED);
@@ -9286,17 +9286,18 @@ pmap_bti_same(pmap_t pmap, vm_offset_t sva, vm_offset_t eva)
 	if (pmap->pm_bti == NULL || ADDR_IS_KERNEL(sva))
 		return (true);
 	MPASS(!ADDR_IS_KERNEL(eva));
-	for (va = sva; va < eva; prev_rs = rs) {
-		rs = rangeset_lookup(pmap->pm_bti, va);
-		if (va == sva)
-			prev_rs = rs;
-		else if ((rs == NULL) ^ (prev_rs == NULL))
+	rs = rangeset_lookup(pmap->pm_bti, sva);
+	if (rs == NULL) {
+		rs = rangeset_next(pmap->pm_bti, sva);
+		return (rs == NULL ||
+			rs->re_start >= eva);
+	}
+	while ((va = rs->re_end) < eva) {
+		next_rs = rangeset_next(pmap->pm_bti, va);
+		if (next_rs == NULL ||
+		    va != next_rs->re_start)
 			return (false);
-		if (rs == NULL) {
-			va += PAGE_SIZE;
-			continue;
-		}
-		va = rs->re_end;
+		rs = next_rs;
 	}
 	return (true);
 }
diff --git a/sys/kern/subr_rangeset.c b/sys/kern/subr_rangeset.c
index 84c71a583192..0a675b4a2fce 100644
--- a/sys/kern/subr_rangeset.c
+++ b/sys/kern/subr_rangeset.c
@@ -260,6 +260,14 @@ rangeset_lookup(struct rangeset *rs, uint64_t place)
 	return (r);
 }
 
+void *
+rangeset_next(struct rangeset *rs, uint64_t place)
+{
+
+	rangeset_check(rs);
+	return (RANGESET_PCTRIE_LOOKUP_GE(&rs->rs_trie, place));
+}
+
 int
 rangeset_copy(struct rangeset *dst_rs, struct rangeset *src_rs)
 {
diff --git a/sys/sys/rangeset.h b/sys/sys/rangeset.h
index a9fc0ad885c8..3225819c4794 100644
--- a/sys/sys/rangeset.h
+++ b/sys/sys/rangeset.h
@@ -74,6 +74,11 @@ int	rangeset_remove_pred(struct rangeset *rs, uint64_t start,
  */
 void	*rangeset_lookup(struct rangeset *rs, uint64_t place);
 
+/*
+ * Finds the first range that begins at or after place.
+ */
+void	*rangeset_next(struct rangeset *rs, uint64_t place);
+
 /*
  * Copies src_rs entries into dst_rs.  dst_rs must be empty.
  * Leaves dst_rs empty on failure.