From nobody Thu Jun 06 18:44:38 2024 X-Original-To: dev-commits-src-main@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 4VwCtH1wyWz5LLgf; Thu, 06 Jun 2024 18:44:39 +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 "R3" (verified OK)) by mx1.freebsd.org (Postfix) with ESMTPS id 4VwCtH145Hz4YGW; Thu, 6 Jun 2024 18:44:39 +0000 (UTC) (envelope-from git@FreeBSD.org) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=freebsd.org; s=dkim; t=1717699479; 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=8RAUr4jqnUsaCRof3mpY7sz1OL6FLBReiipzpaguU00=; b=adrQ6qBAgUL/QrzhxzB9ZOYYdCrhXPL5Stqqkms5uqK61v1vGfs+k7DvA9Q/AMZj1YEHFU xz5QB5TSjKAp9sSQMMmLKSkxrEKsHNeDsVndGvtqjwsEEy+wcWslaLwnWDEjj7GJTkHA8D meFMSJi25MV2eZZUHYuUusjum5SfaOICEfhXXLhkLZh6s2jwGGqcsucE4LGkibZxxlP7hC t8BBiFxx5T+PcJuMU3oZmrFGmyuNDzdsJfRtYGqV0D88z7SWtDjwt9n4K0wUNfU6T0OKIH JcdamMYeIs5gZtJj35IilqAu2oCq3F9W3pk4NMXTKjWBaeRrEAcQN5LowOLwmQ== ARC-Seal: i=1; s=dkim; d=freebsd.org; t=1717699479; a=rsa-sha256; cv=none; b=JhB3BhnSRmLt+nvz8LzHD9Fqw2ej+ZTJyn33zR7Zhnki8SrfpPIg4JWXRueuNRl565fmaW ZVn/ox5g0o4fGjXSMDAAhtnTpizBCZq0qpsjpria9eTWGJIyuKSHOn2ZpZ7UxoGh2bSI5C miDjgn4Jz9I70Y7+sXdjqSYvsjG+ejjnWvPyF3C8smULpPAlwwyOvQKtLOE0jj91W4j7Xy +I9EYt4GCwCCG1hhEz3t+vcutf2cdO0TZLcs+wUZ+YoMIMxOp9DRvfzlZwU2+KkH/t6RpY 64l5bPMMXWzGqb3miSskeG7oe+i2B/jWbKwW1uby45JsFD6lfJLAF3I8S5Zcew== 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=1717699479; 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=8RAUr4jqnUsaCRof3mpY7sz1OL6FLBReiipzpaguU00=; b=dho5BrvsybIFyQAp1TqPIiutfn4s0x85110xQ7r3FGDi37p737N5kmISJQCKNuhMD+pQn3 RZ03X9UuM4JjyKYIp5AlqB73/FAtbbu85iLy5vEPfD1R6+/RdJ7PtB79Ia/CcCWp49vdez aKktSStgMip32GFODB5mS5/yxHoZB5DuhVmQNfI0HuUyqT7wPC2ELG0Pn1Gub2a5znXEux 71KG2NQ1MmgTkxnj4R1LhDgYslfqiIAMrySrgp94IkuEnpl1rqXZvwwfP8qc9CM6FIEaS2 keKv+Q8YF4q3V1HTxI0TbLOzfgg1bdkCJpwXNblEoTV7zGmARoSh4gbtMJQw+w== 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 4VwCtH0YPNzxVn; Thu, 6 Jun 2024 18:44:39 +0000 (UTC) (envelope-from git@FreeBSD.org) Received: from gitrepo.freebsd.org ([127.0.1.44]) by gitrepo.freebsd.org (8.17.1/8.17.1) with ESMTP id 456IiclB042007; Thu, 6 Jun 2024 18:44:38 GMT (envelope-from git@gitrepo.freebsd.org) Received: (from git@localhost) by gitrepo.freebsd.org (8.17.1/8.17.1/Submit) id 456IicBR042004; Thu, 6 Jun 2024 18:44:38 GMT (envelope-from git) Date: Thu, 6 Jun 2024 18:44:38 GMT Message-Id: <202406061844.456IicBR042004@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: 2c10bacdf402 - main - rangeset: add next() iteration List-Id: Commit messages for the main branch of the src repository List-Archive: https://lists.freebsd.org/archives/dev-commits-src-main List-Help: List-Post: List-Subscribe: List-Unsubscribe: X-BeenThere: dev-commits-src-main@freebsd.org Sender: owner-dev-commits-src-main@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: 2c10bacdf402c1cf246302303b4dbdce21bf9692 Auto-Submitted: auto-generated The branch main has been updated by dougm: URL: https://cgit.FreeBSD.org/src/commit/?id=2c10bacdf402c1cf246302303b4dbdce21bf9692 commit 2c10bacdf402c1cf246302303b4dbdce21bf9692 Author: Doug Moore AuthorDate: 2024-06-06 18:42:31 +0000 Commit: Doug Moore 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.