git: 8aa2cd9d13d4 - main - rangeset: speed up range traversal
- Go to: [ bottom of page ] [ top of archives ] [ this month ]
Date: Mon, 09 Sep 2024 21:52:03 UTC
The branch main has been updated by dougm:
URL: https://cgit.FreeBSD.org/src/commit/?id=8aa2cd9d13d4b1a81ac313e9d3e214ec3a928430
commit 8aa2cd9d13d4b1a81ac313e9d3e214ec3a928430
Author: Doug Moore <dougm@FreeBSD.org>
AuthorDate: 2024-09-09 21:50:14 +0000
Commit: Doug Moore <dougm@FreeBSD.org>
CommitDate: 2024-09-09 21:50:14 +0000
rangeset: speed up range traversal
For rangeset-next search, use exact search rather than greater-than search.
Move a bit of the testing logic from the pmap code to the common rangeset code.
Reviewed by: kib (previous version)
Tested by: pho (previous version)
Differential Revision: https://reviews.freebsd.org/D46314
---
sys/amd64/amd64/pmap.c | 20 +++++++-------------
sys/arm64/arm64/pmap.c | 19 +++++++------------
sys/kern/subr_rangeset.c | 23 +++++++++++++++--------
sys/sys/rangeset.h | 14 +++++++++-----
4 files changed, 38 insertions(+), 38 deletions(-)
diff --git a/sys/amd64/amd64/pmap.c b/sys/amd64/amd64/pmap.c
index ff5c229b7652..48aef39e9663 100644
--- a/sys/amd64/amd64/pmap.c
+++ b/sys/amd64/amd64/pmap.c
@@ -11468,7 +11468,7 @@ pmap_pkru_deassign_all(pmap_t pmap)
static bool
pmap_pkru_same(pmap_t pmap, vm_offset_t sva, vm_offset_t eva, pt_entry_t *pte)
{
- struct pmap_pkru_range *next_ppr, *ppr;
+ struct pmap_pkru_range *ppr;
vm_offset_t va;
u_int keyidx;
@@ -11480,20 +11480,14 @@ pmap_pkru_same(pmap_t pmap, vm_offset_t sva, vm_offset_t eva, pt_entry_t *pte)
sva >= VM_MAXUSER_ADDRESS)
return (true);
MPASS(eva <= VM_MAXUSER_ADDRESS);
- 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);
- }
+ ppr = rangeset_containing(&pmap->pm_pkru, sva);
+ if (ppr == NULL)
+ return (rangeset_empty(&pmap->pm_pkru, sva, eva));
keyidx = ppr->pkru_keyidx;
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 ||
- keyidx != next_ppr->pkru_keyidx)
+ if ((ppr = rangeset_beginning(&pmap->pm_pkru, va)) == NULL ||
+ keyidx != ppr->pkru_keyidx)
return (false);
- ppr = next_ppr;
}
*pte |= X86_PG_PKU(keyidx);
return (true);
@@ -11509,7 +11503,7 @@ pmap_pkru_get(pmap_t pmap, vm_offset_t va)
(cpu_stdext_feature2 & CPUID_STDEXT2_PKU) == 0 ||
va >= VM_MAXUSER_ADDRESS)
return (0);
- ppr = rangeset_lookup(&pmap->pm_pkru, va);
+ ppr = rangeset_containing(&pmap->pm_pkru, va);
if (ppr != NULL)
return (X86_PG_PKU(ppr->pkru_keyidx));
return (0);
diff --git a/sys/arm64/arm64/pmap.c b/sys/arm64/arm64/pmap.c
index dc02e732568f..2fd45bdb6b95 100644
--- a/sys/arm64/arm64/pmap.c
+++ b/sys/arm64/arm64/pmap.c
@@ -9370,7 +9370,7 @@ pmap_bti_deassign_all(pmap_t pmap)
static bool
pmap_bti_same(pmap_t pmap, vm_offset_t sva, vm_offset_t eva, pt_entry_t *pte)
{
- struct rs_el *next_rs, *rs;
+ struct rs_el *rs;
vm_offset_t va;
PMAP_LOCK_ASSERT(pmap, MA_OWNED);
@@ -9388,18 +9388,12 @@ pmap_bti_same(pmap_t pmap, vm_offset_t sva, vm_offset_t eva, pt_entry_t *pte)
if (pmap->pm_bti == NULL)
return (true);
PMAP_ASSERT_STAGE1(pmap);
- rs = rangeset_lookup(pmap->pm_bti, sva);
- if (rs == NULL) {
- rs = rangeset_next(pmap->pm_bti, sva);
- return (rs == NULL ||
- rs->re_start >= eva);
- }
+ rs = rangeset_containing(pmap->pm_bti, sva);
+ if (rs == NULL)
+ return (rangeset_empty(pmap->pm_bti, sva, eva));
while ((va = rs->re_end) < eva) {
- next_rs = rangeset_next(pmap->pm_bti, va);
- if (next_rs == NULL ||
- va != next_rs->re_start)
+ if ((rs = rangeset_beginning(pmap->pm_bti, va)) == NULL)
return (false);
- rs = next_rs;
}
*pte |= ATTR_S1_GP;
return (true);
@@ -9415,7 +9409,8 @@ pmap_pte_bti(pmap_t pmap, vm_offset_t va)
return (0);
if (pmap == kernel_pmap)
return (ATTR_KERN_GP);
- if (pmap->pm_bti != NULL && rangeset_lookup(pmap->pm_bti, va) != NULL)
+ if (pmap->pm_bti != NULL &&
+ rangeset_containing(pmap->pm_bti, va) != NULL)
return (ATTR_S1_GP);
return (0);
}
diff --git a/sys/kern/subr_rangeset.c b/sys/kern/subr_rangeset.c
index ddb1839531ea..2edf295ab2ce 100644
--- a/sys/kern/subr_rangeset.c
+++ b/sys/kern/subr_rangeset.c
@@ -248,25 +248,32 @@ rangeset_remove_all(struct rangeset *rs)
}
void *
-rangeset_lookup(struct rangeset *rs, uint64_t place)
+rangeset_containing(struct rangeset *rs, uint64_t place)
{
struct rs_el *r;
rangeset_check(rs);
r = RANGESET_PCTRIE_LOOKUP_LE(&rs->rs_trie, place);
- if (r == NULL)
- return (NULL);
- if (r->re_end <= place)
- return (NULL);
- return (r);
+ if (r != NULL && place < r->re_end)
+ return (r);
+ return (NULL);
+}
+
+bool
+rangeset_empty(struct rangeset *rs, uint64_t start, uint64_t end)
+{
+ struct rs_el *r;
+
+ r = RANGESET_PCTRIE_LOOKUP_GE(&rs->rs_trie, start + 1);
+ return (r == NULL || r->re_start >= end);
}
void *
-rangeset_next(struct rangeset *rs, uint64_t place)
+rangeset_beginning(struct rangeset *rs, uint64_t place)
{
rangeset_check(rs);
- return (RANGESET_PCTRIE_LOOKUP_GE(&rs->rs_trie, place));
+ return (RANGESET_PCTRIE_LOOKUP(&rs->rs_trie, place));
}
int
diff --git a/sys/sys/rangeset.h b/sys/sys/rangeset.h
index 3225819c4794..b6beb669821d 100644
--- a/sys/sys/rangeset.h
+++ b/sys/sys/rangeset.h
@@ -69,15 +69,19 @@ int rangeset_remove_pred(struct rangeset *rs, uint64_t start,
uint64_t end, rs_pred_t pred);
/*
- * Really returns the pointer to the data with struct rs_el embedded
- * at the beginning.
+ * Finds the range that contains place, if any.
*/
-void *rangeset_lookup(struct rangeset *rs, uint64_t place);
+void *rangeset_containing(struct rangeset *rs, uint64_t place);
/*
- * Finds the first range that begins at or after place.
+ * Report whether no range begins between start and end.
*/
-void *rangeset_next(struct rangeset *rs, uint64_t place);
+bool rangeset_empty(struct rangeset *rs, uint64_t start, uint64_t end);
+
+/*
+ * Finds the range that begins at place, if any.
+ */
+void *rangeset_beginning(struct rangeset *rs, uint64_t place);
/*
* Copies src_rs entries into dst_rs. dst_rs must be empty.