From nobody Mon Sep 09 21:52:03 2024 X-Original-To: dev-commits-src-all@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 4X2gXg4jPrz5VBHB; Mon, 09 Sep 2024 21:52:03 +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 4X2gXg3kZMz40M6; Mon, 9 Sep 2024 21:52:03 +0000 (UTC) (envelope-from git@FreeBSD.org) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=freebsd.org; s=dkim; t=1725918723; 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=+nOyMjnjLEMr3w0gAC0cA2SvI9RkQVuxGtY8NGB0Zms=; b=xTx7zynmrTJmuIXhooH0qsslMV3R5UlAOb0ou9BJFR52CMRWv9qrxXb3OyrZBtNulqeah+ RAp6cdU/FlfWA097dIHUItn5ESxAdZ9xdLm3WFd67xrrBWrCCBMUgqnNHHbRKdh/5zmMpE Ph4nh8sCQ0IsyKywuQiaYcIg7GCWKSpm/qJ7uNqdOX5hGim9BoNcBvwFrBGJvBbx45PhWs gucOjdF1ALMte3qZ1VtOga4i+OcB5kH4wfiXJEyi1dSB4hIwoGK8OrVzH35LXrhLeICRST MAzRDmXvrHKoK9JOjKurzuBK05r/ZJB2ubbf7UGbB1DAn2zgPAOn2/UsRiltqA== ARC-Seal: i=1; s=dkim; d=freebsd.org; t=1725918723; a=rsa-sha256; cv=none; b=HU8clWZQV0fHosjVt63fHfS2Crd7iUsKl2txHuR0ztHifAOsB4iVUL7stEQwyy127XhXKx gPDhl0OA8BeiqJsV8DstNGoothKCCszkbCYMkVNTgi+OySTJWOcHB8RID/mPyH3Boo3JlX vIrtEa8A61mXwDRX0ei4UpWYnxc6w7xLRoFhDL3jK7nenfjUGJRIvKU6yqTeTWg5a1VXbl MiLkPiG2ArOF8wWKTPNpPTzC2z28HtQ0JUvajAZvRXOs0h8YXYWnvxouoMLaCFCHB9a8xV lzuy6d196CktFAdo4gazht5bxQhSUHcswO/TAzF6AVoQkHA65xPpvsQujIxYdw== 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=1725918723; 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=+nOyMjnjLEMr3w0gAC0cA2SvI9RkQVuxGtY8NGB0Zms=; b=k5a8kh5DnjjnxXHMN9W04gjYxeSD79wLoLRTUPqJ2aJtC2sMbouz2AipdRwAlZt0q7ImTo mdo86P+rogY2Ajr924QCDss8LpSyCiNptM2ZtQthsA/P5AgnPfWyN2/glO4Db7wLrej59V 6JFGpJJDwWoeGvLMpVr87bsJxgD4MDioboAk9DoQmDnz59ODZ+HPgKVnX4BAuE5ibcX61M vc4+F9mbGzuZZzlnlDVNMKScY3yLKspZ2Fdfqnoe4iKTnyL/ZQir73YI0Rlq335OcgTJF/ G222wM2fgDwZs00kIiIa3GgkYyyKbNSjXUYdqtXRmXNK2YWcDrolByOgD3eJ8A== 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 4X2gXg3KtzzL8m; Mon, 9 Sep 2024 21:52:03 +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 489Lq3ed037139; Mon, 9 Sep 2024 21:52:03 GMT (envelope-from git@gitrepo.freebsd.org) Received: (from git@localhost) by gitrepo.freebsd.org (8.18.1/8.18.1/Submit) id 489Lq36Q037136; Mon, 9 Sep 2024 21:52:03 GMT (envelope-from git) Date: Mon, 9 Sep 2024 21:52:03 GMT Message-Id: <202409092152.489Lq36Q037136@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: 8aa2cd9d13d4 - main - rangeset: speed up range traversal List-Id: Commit messages for all branches of the src repository List-Archive: https://lists.freebsd.org/archives/dev-commits-src-all List-Help: List-Post: List-Subscribe: List-Unsubscribe: X-BeenThere: dev-commits-src-all@freebsd.org Sender: owner-dev-commits-src-all@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: 8aa2cd9d13d4b1a81ac313e9d3e214ec3a928430 Auto-Submitted: auto-generated The branch main has been updated by dougm: URL: https://cgit.FreeBSD.org/src/commit/?id=8aa2cd9d13d4b1a81ac313e9d3e214ec3a928430 commit 8aa2cd9d13d4b1a81ac313e9d3e214ec3a928430 Author: Doug Moore AuthorDate: 2024-09-09 21:50:14 +0000 Commit: Doug Moore 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.