From nobody Sun May 18 03:14:18 2025 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 4b0Qs62Qcqz5wgvx; Sun, 18 May 2025 03:14:18 +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 4b0Qs61THCz3Djk; Sun, 18 May 2025 03:14:18 +0000 (UTC) (envelope-from git@FreeBSD.org) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=freebsd.org; s=dkim; t=1747538058; 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=uTQOSnpdrPKm53XyVoZQDBKgYYyFMwdSketccLojIe4=; b=o/4BaC9209JzumvxmmGCLYwJV5C/gTae/GUMntX5VKOy/8fGepqdT5m0sd1crn2Chhj4lk 9aIL0W5slsf+1OdQxx5fUYpzloL6hU8mweBX4XRhDCFRKNqA/dMxyln4TUiY+N1DALxorz 2l0zSvR5ohYPHLqFwsncmv/epCvyHGYLes2Di4c6uikwVHGq0ZY5ATupUXARDdcPUI55hp 4Ew2wnTcPRrSu0DYYcgrhtQmHv+Z1X28dVLcAxTdPuAZ0nfGbPwnDi2JNIjIpgxNm4qw8W ckSHxCEpSLaUC/5QVj0+uQ8Xvg66gytS9+4AXuw54+WklJSSMk74lHQjV2dguA== ARC-Message-Signature: i=1; a=rsa-sha256; c=relaxed/relaxed; d=freebsd.org; s=dkim; t=1747538058; 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=uTQOSnpdrPKm53XyVoZQDBKgYYyFMwdSketccLojIe4=; b=mKyBc/nbzZETRWiJuvmmCuy0Y/KC3c4krKvtJU3zlqJKgDuYbCOm6GKk4IXShw74ErfZh2 EMT/H9xFI3Iv2EVzeupUmWHjo4UE2ONv36H9h7+UGOT+ObEpeJfSYCxJ/+sQHne7CRmC22 9KWMR6aDtvC89IOThqmQ+3c0dRZWPrECTUf8UMQZPuBIx6exx1g0TEUB65tj6rVKKHwmTb uuXqBDVz74o6jyQuLJ/Z0CyodOU4btfvlK8tpllrTdelnIr+dpv8Qqn/rvbSF8G/5FQU6Q WUWgYCkR/sM2d03hNzxwvodVt/EgpCsdYHdePE/aytF1j0IOuxhbzDkCVHlqFQ== ARC-Seal: i=1; s=dkim; d=freebsd.org; t=1747538058; a=rsa-sha256; cv=none; b=Ikp6YnDG3K9dDbA8v58M8C071YiI0nin4MS8XUziJTW2Efp0aeMt6C20aAMgtYs82ozFOu yd3APGD6BTVoe9eOQ2/m9UJNdSawZXKqEznjEy722dr7vBkeaa5xny/JKHBIb+7F7n4RyV Zt4vw3FuQtiBtBs2RNRrxIezdO9Z+EiAD7ASCNL3PZyI1RD5M1Iiq5QqQbCl5YVxM3Gpfa K2ZvuFTGi4YEj/ezAYIBeim4up8Zullgu/PY1g6MPFu7/McWTyENAJrDTgYSkOqCDDnNua 5gY6Rh8ImILnUjuvc/keGGKIRzOlJry2OILsHS1xq9/S3JfRDv3day+aNXb5Nw== ARC-Authentication-Results: i=1; mx1.freebsd.org; none 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 4b0Qs60tR7z1Fpg; Sun, 18 May 2025 03:14:18 +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 54I3EIKT005213; Sun, 18 May 2025 03:14:18 GMT (envelope-from git@gitrepo.freebsd.org) Received: (from git@localhost) by gitrepo.freebsd.org (8.18.1/8.18.1/Submit) id 54I3EIDX005210; Sun, 18 May 2025 03:14:18 GMT (envelope-from git) Date: Sun, 18 May 2025 03:14:18 GMT Message-Id: <202505180314.54I3EIDX005210@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: 6fd6c29a236c - main - pctrie: use popmap in locked lookup_range 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: 6fd6c29a236c28c96c717662a2923d4a4674d0d3 Auto-Submitted: auto-generated The branch main has been updated by dougm: URL: https://cgit.FreeBSD.org/src/commit/?id=6fd6c29a236c28c96c717662a2923d4a4674d0d3 commit 6fd6c29a236c28c96c717662a2923d4a4674d0d3 Author: Doug Moore AuthorDate: 2025-05-18 03:12:52 +0000 Commit: Doug Moore CommitDate: 2025-05-18 03:12:52 +0000 pctrie: use popmap in locked lookup_range When lookup_range is invoked with a lock held, the popmap field of a level-0 parent node can be used to find the next null child (if any) of that parent, allowing null checks to be removed from the loop and for the compiler to perform some loop unrolling. Reviewed by: alc, kib Differential Revision: https://reviews.freebsd.org/D50389 --- sys/kern/subr_pctrie.c | 36 ++++++++++++++++++++++++++++++++---- 1 file changed, 32 insertions(+), 4 deletions(-) diff --git a/sys/kern/subr_pctrie.c b/sys/kern/subr_pctrie.c index 67566a2d1bfe..676e3595316a 100644 --- a/sys/kern/subr_pctrie.c +++ b/sys/kern/subr_pctrie.c @@ -630,16 +630,44 @@ _pctrie_lookup_range(struct pctrie *ptree, struct pctrie_node *node, base = (index + i) % PCTRIE_COUNT; if (base == 0 || parent == NULL || parent->pn_clev != 0) continue; - end = MIN(count, i + PCTRIE_COUNT - base); + + /* + * For PCTRIE_SMR, compute an upper bound on the number of + * children of this parent left to examine. For PCTRIE_LOCKED, + * compute the number of non-NULL children from base up to the + * first NULL child, if any, using the fact that pn_popmap has + * bits set for only the non-NULL children. + * + * The pn_popmap field is accessed only when a lock is held. + * To use it for PCTRIE_SMR here would require that we know that + * race conditions cannot occur if the tree is modified while + * accessed here. Guarantees about the visibility of changes to + * child pointers, enforced by memory barriers on the writing of + * pointers, are not present for the pn_popmap field, so that + * the popmap bit for a child page may, for an instant, + * misrepresent the nullness of the child page because an + * operation modifying the pctrie is in progress. + */ + end = (access == PCTRIE_SMR) ? PCTRIE_COUNT - base : + ffs((parent->pn_popmap >> base) + 1) - 1; + end = MIN(count, i + end); while (i < end) { node = pctrie_node_load(&parent->pn_child[base++], smr, access); - if ((val = pctrie_toval(node)) == NULL) + val = pctrie_toval(node); + if (access == PCTRIE_SMR && val == NULL) break; value[i++] = val; + KASSERT(val != NULL, + ("%s: null child written to range", __func__)); + } + if (access == PCTRIE_SMR) { + if (i < end) + break; + } else { + if (base < PCTRIE_COUNT) + break; } - if (i < end) - break; } if (parent_out != NULL) *parent_out = parent;