Date: Sun, 18 May 2025 03:14:18 GMT From: Doug Moore <dougm@FreeBSD.org> To: src-committers@FreeBSD.org, dev-commits-src-all@FreeBSD.org, dev-commits-src-main@FreeBSD.org Subject: git: 6fd6c29a236c - main - pctrie: use popmap in locked lookup_range Message-ID: <202505180314.54I3EIDX005210@gitrepo.freebsd.org>
next in thread | raw e-mail | index | archive | help
The branch main has been updated by dougm: URL: https://cgit.FreeBSD.org/src/commit/?id=6fd6c29a236c28c96c717662a2923d4a4674d0d3 commit 6fd6c29a236c28c96c717662a2923d4a4674d0d3 Author: Doug Moore <dougm@FreeBSD.org> AuthorDate: 2025-05-18 03:12:52 +0000 Commit: Doug Moore <dougm@FreeBSD.org> 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;
Want to link to this message? Use this URL: <https://mail-archive.FreeBSD.org/cgi/mid.cgi?202505180314.54I3EIDX005210>