From nobody Fri Jul 28 16:43:27 2023 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 4RCD3M6qCWz4pF38; Fri, 28 Jul 2023 16:43:27 +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 4RCD3M650Bz3q7Z; Fri, 28 Jul 2023 16:43:27 +0000 (UTC) (envelope-from git@FreeBSD.org) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=freebsd.org; s=dkim; t=1690562607; 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=It2VEol8jKPssxVXqAq7SK/bPNfLlDRt1SV2y1x4uUg=; b=Ljx6meRx5CE86JiKZCS1BRw/hVnpRIvDR+M/iSEwtpsLKYEepkwXqJGS6WIFeIt13ssI/g kqMiLjmr4m1xpnBXaBIBMY2YK5/IjFYf4S50oTVjH7KD1PNx7KvylxakSZCoj813JI7gcr ouavN0Tvk28OoRngWCZ28ciVT9BdY5gvzsB0zbbY0AhjgnMQT8WWaBGUzqEKI2x5cRYrNk ad7WSZQD+tAZh4LxHOgOKt6ts2oGY6YGfu+MnN3XiU34YrCLfYbvmijwkPJguo4nvyTKQw OD2KvELzBkmajHuoEl1t6pzuX00UpSXSxtohWcezzzj0pkEE3GtQWbCjQ5PV9A== ARC-Message-Signature: i=1; a=rsa-sha256; c=relaxed/relaxed; d=freebsd.org; s=dkim; t=1690562607; 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=It2VEol8jKPssxVXqAq7SK/bPNfLlDRt1SV2y1x4uUg=; b=a/ZNPSvaU5rYYSnF0WIKLR/JV01L9GL6rjbX0gPIgG1DJs9pwsz6hDYwnMLsAJLeXeVgOg QIKxBzQ/Fm3Pf9MtzxK4eZ4JqYqOiweHQGMcoyfmYZqusCqlgUZhdmy+DKDHX4Wzcu4H08 z/vWs96S/KORkqYyuLS9+g5oURo4zbh23y2a8ZXZIaU7duGzKeM7BhGj3EWIEqMK4WIMVf VGFWyLtU+1GxfokpwvR9o2B57Nw7gIbSey74oQk29lOQy58uFOtA3FbhkEAZwaLwpgXU7o ip9mk4EUHUQ8mz61NkEKCX5VHkN7eFv0+nWTXoIF6jHQcrN9SrD8DvBfhu4lXg== ARC-Authentication-Results: i=1; mx1.freebsd.org; none ARC-Seal: i=1; s=dkim; d=freebsd.org; t=1690562607; a=rsa-sha256; cv=none; b=lcIwzrI/ldcXMeZsKW9TgY+HpdKk8wXwuyvnY2IIPZXhlW2zxVvvMo96mnw6WjUM2JGRTq KhGo++W99NFlf945y1CCoTzBzXed72Tv/t5aaxZ34L+qnGvuWoCFN+e9Gxre48UUOcUN7I eh6BTZ/yh2sBuH2dx54tnL5olRAs+388WpWnMI57qzhjRiNJwn5p5kdQ3UjympVwpX+IkX T0WlwiKMsavUCquBsBHbairMBvvgjdWQu1SRusdQpvg2mQMXThAdPMArrWkJanGNKAMG4K VKrLdIHYWCGWQm2cv829uKMLyxEdIhBXU/eO1MY18+s1MXnwtpkPHxSUIJ3f+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 4RCD3M583Fzy4j; Fri, 28 Jul 2023 16:43:27 +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 36SGhRo6025306; Fri, 28 Jul 2023 16:43:27 GMT (envelope-from git@gitrepo.freebsd.org) Received: (from git@localhost) by gitrepo.freebsd.org (8.17.1/8.17.1/Submit) id 36SGhR9N025305; Fri, 28 Jul 2023 16:43:27 GMT (envelope-from git) Date: Fri, 28 Jul 2023 16:43:27 GMT Message-Id: <202307281643.36SGhR9N025305@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: 2d2bcba7ba70 - main - Every path in a radix trie ends with a leaf or a NULL. By replacing NULL (non-leaf) pointers with NULL leaves, there is a NULL test removed from every iteration of an index-based search loop. 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: Sender: owner-dev-commits-src-all@freebsd.org X-BeenThere: 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: 2d2bcba7ba70141388729ed49674b36fd01146c5 Auto-Submitted: auto-generated The branch main has been updated by dougm: URL: https://cgit.FreeBSD.org/src/commit/?id=2d2bcba7ba70141388729ed49674b36fd01146c5 commit 2d2bcba7ba70141388729ed49674b36fd01146c5 Author: Doug Moore AuthorDate: 2023-07-28 16:39:52 +0000 Commit: Doug Moore CommitDate: 2023-07-28 16:39:52 +0000 Every path in a radix trie ends with a leaf or a NULL. By replacing NULL (non-leaf) pointers with NULL leaves, there is a NULL test removed from every iteration of an index-based search loop. This speeds up radix trie searches by few percent. If there are any radix tries that are not initialized with the init() function, but instead depend on zeroing everything being proper initialization, this will break those tries. Reviewed by: alc, kib Tested by: pho (as part of a larger change) Differential Revision: https://reviews.freebsd.org/D41171 --- sys/kern/subr_pctrie.c | 175 ++++++++++++++++++------------------- sys/sys/_pctrie.h | 7 +- sys/sys/pctrie.h | 14 ++- sys/vm/_vm_radix.h | 7 +- sys/vm/vm_radix.c | 231 +++++++++++++++++++++++++------------------------ sys/vm/vm_radix.h | 14 ++- 6 files changed, 235 insertions(+), 213 deletions(-) diff --git a/sys/kern/subr_pctrie.c b/sys/kern/subr_pctrie.c index 4cd7f4b085ba..6d45d9762a78 100644 --- a/sys/kern/subr_pctrie.c +++ b/sys/kern/subr_pctrie.c @@ -79,9 +79,8 @@ typedef uint32_t pn_popmap_t; _Static_assert(sizeof(pn_popmap_t) <= sizeof(int), "pn_popmap_t too wide"); -/* Flag bits stored in node pointers. */ -#define PCTRIE_ISLEAF 0x1 -#define PCTRIE_FLAGS 0x1 +/* Set of all flag bits stored in node pointers. */ +#define PCTRIE_FLAGS (PCTRIE_ISLEAF) #define PCTRIE_PAD PCTRIE_FLAGS /* Returns one unit associated with specified level. */ @@ -140,7 +139,7 @@ pctrie_node_get(struct pctrie *ptree, pctrie_alloc_t allocfn, uint64_t index, */ if (node->pn_popmap != 0) { pctrie_node_store(&node->pn_child[ffs(node->pn_popmap) - 1], - NULL, PCTRIE_UNSERIALIZED); + PCTRIE_NULL, PCTRIE_UNSERIALIZED); node->pn_popmap = 0; } node->pn_owner = pctrie_trimkey(index, clevel + 1); @@ -165,7 +164,8 @@ pctrie_node_put(struct pctrie *ptree, struct pctrie_node *node, if ((node->pn_popmap & (1 << slot)) != 0) continue; KASSERT(smr_unserialized_load(&node->pn_child[slot], true) == - NULL, ("pctrie_node_put: node %p has a child", node)); + PCTRIE_NULL, + ("pctrie_node_put: node %p has a child", node)); } #endif freefn(ptree, node); @@ -320,12 +320,13 @@ pctrie_reclaim_allnodes_int(struct pctrie *ptree, struct pctrie_node *node, slot = ffs(node->pn_popmap) - 1; child = pctrie_node_load(&node->pn_child[slot], NULL, PCTRIE_UNSERIALIZED); - KASSERT(child != NULL, ("%s: bad popmap slot %d in node %p", + KASSERT(child != PCTRIE_NULL, + ("%s: bad popmap slot %d in node %p", __func__, slot, node)); if (!pctrie_isleaf(child)) pctrie_reclaim_allnodes_int(ptree, child, freefn); node->pn_popmap ^= 1 << slot; - pctrie_node_store(&node->pn_child[slot], NULL, + pctrie_node_store(&node->pn_child[slot], PCTRIE_NULL, PCTRIE_UNSERIALIZED); } pctrie_node_put(ptree, node, freefn); @@ -341,7 +342,9 @@ pctrie_zone_init(void *mem, int size __unused, int flags __unused) node = mem; node->pn_popmap = 0; - memset(node->pn_child, 0, sizeof(node->pn_child)); + for (int i = 0; i < nitems(node->pn_child); i++) + pctrie_node_store(&node->pn_child[i], PCTRIE_NULL, + PCTRIE_UNSERIALIZED); return (0); } @@ -360,7 +363,7 @@ int pctrie_insert(struct pctrie *ptree, uint64_t *val, pctrie_alloc_t allocfn) { uint64_t index, newind; - struct pctrie_node *leaf, *node, *tmp; + struct pctrie_node *leaf, *node, *parent; smr_pctnode_t *parentp; int slot; uint16_t clev; @@ -373,29 +376,32 @@ pctrie_insert(struct pctrie *ptree, uint64_t *val, pctrie_alloc_t allocfn) * will never be used. */ node = pctrie_root_load(ptree, NULL, PCTRIE_LOCKED); - if (node == NULL) { - ptree->pt_root = (uintptr_t)leaf; - return (0); - } - for (parentp = (smr_pctnode_t *)&ptree->pt_root;; node = tmp) { + parent = NULL; + for (;;) { if (pctrie_isleaf(node)) { + if (node == PCTRIE_NULL) { + if (parent == NULL) + ptree->pt_root = leaf; + else + pctrie_addnode(parent, index, + parent->pn_clev, leaf, + PCTRIE_LOCKED); + return (0); + } newind = *pctrie_toval(node); if (newind == index) panic("%s: key %jx is already present", __func__, (uintmax_t)index); break; - } else if (pctrie_keybarr(node, index)) { + } + if (pctrie_keybarr(node, index)) { newind = node->pn_owner; break; } slot = pctrie_slot(index, node->pn_clev); - parentp = &node->pn_child[slot]; - tmp = pctrie_node_load(parentp, NULL, PCTRIE_LOCKED); - if (tmp == NULL) { - pctrie_addnode(node, index, node->pn_clev, leaf, - PCTRIE_LOCKED); - return (0); - } + parent = node; + node = pctrie_node_load(&node->pn_child[slot], NULL, + PCTRIE_LOCKED); } /* @@ -403,15 +409,17 @@ pctrie_insert(struct pctrie *ptree, uint64_t *val, pctrie_alloc_t allocfn) * Setup the new intermediate node and add the 2 children: the * new object and the older edge or object. */ + parentp = (parent != NULL) ? &parent->pn_child[slot]: + (smr_pctnode_t *)&ptree->pt_root; clev = pctrie_keydiff(newind, index); - tmp = pctrie_node_get(ptree, allocfn, index, clev); - if (tmp == NULL) + parent = pctrie_node_get(ptree, allocfn, index, clev); + if (parent == NULL) return (ENOMEM); /* These writes are not yet visible due to ordering. */ - pctrie_addnode(tmp, index, clev, leaf, PCTRIE_UNSERIALIZED); - pctrie_addnode(tmp, newind, clev, node, PCTRIE_UNSERIALIZED); + pctrie_addnode(parent, index, clev, leaf, PCTRIE_UNSERIALIZED); + pctrie_addnode(parent, newind, clev, node, PCTRIE_UNSERIALIZED); /* Synchronize to make the above visible. */ - pctrie_node_store(parentp, tmp, PCTRIE_LOCKED); + pctrie_node_store(parentp, parent, PCTRIE_LOCKED); return (0); } @@ -428,10 +436,9 @@ _pctrie_lookup(struct pctrie *ptree, uint64_t index, smr_t smr, int slot; node = pctrie_root_load(ptree, smr, access); - while (node != NULL) { + for (;;) { if (pctrie_isleaf(node)) { - m = pctrie_toval(node); - if (*m == index) + if ((m = pctrie_toval(node)) != NULL && *m == index) return (m); break; } @@ -499,10 +506,9 @@ pctrie_lookup_ge(struct pctrie *ptree, uint64_t index) */ node = pctrie_root_load(ptree, NULL, PCTRIE_LOCKED); succ = NULL; - while (node != NULL) { + for (;;) { if (pctrie_isleaf(node)) { - m = pctrie_toval(node); - if (*m >= index) + if ((m = pctrie_toval(node)) != NULL && *m >= index) return (m); break; } @@ -580,10 +586,9 @@ pctrie_lookup_le(struct pctrie *ptree, uint64_t index) */ node = pctrie_root_load(ptree, NULL, PCTRIE_LOCKED); pred = NULL; - while (node != NULL) { + for (;;) { if (pctrie_isleaf(node)) { - m = pctrie_toval(node); - if (*m <= index) + if ((m = pctrie_toval(node)) != NULL && *m <= index) return (m); break; } @@ -626,66 +631,54 @@ pctrie_lookup_le(struct pctrie *ptree, uint64_t index) void pctrie_remove(struct pctrie *ptree, uint64_t index, pctrie_free_t freefn) { - struct pctrie_node *node, *parent, *tmp; + struct pctrie_node *child, *node, *parent; uint64_t *m; int slot; - node = pctrie_root_load(ptree, NULL, PCTRIE_LOCKED); - if (pctrie_isleaf(node)) { - m = pctrie_toval(node); - if (*m != index) - panic("%s: invalid key found", __func__); - pctrie_root_store(ptree, NULL, PCTRIE_LOCKED); - return; - } - parent = NULL; + node = NULL; + child = pctrie_root_load(ptree, NULL, PCTRIE_LOCKED); for (;;) { - if (node == NULL) - panic("pctrie_remove: impossible to locate the key"); - slot = pctrie_slot(index, node->pn_clev); - tmp = pctrie_node_load(&node->pn_child[slot], NULL, - PCTRIE_LOCKED); - if (pctrie_isleaf(tmp)) { - m = pctrie_toval(tmp); - if (*m != index) - panic("%s: invalid key found", __func__); - KASSERT((node->pn_popmap & (1 << slot)) != 0, - ("%s: bad popmap slot %d in node %p", - __func__, slot, node)); - node->pn_popmap ^= 1 << slot; - pctrie_node_store(&node->pn_child[slot], NULL, - PCTRIE_LOCKED); - if (!powerof2(node->pn_popmap)) - break; - KASSERT(node->pn_popmap != 0, - ("%s: bad popmap all zeroes", __func__)); - slot = ffs(node->pn_popmap) - 1; - tmp = pctrie_node_load(&node->pn_child[slot], - NULL, PCTRIE_LOCKED); - KASSERT(tmp != NULL, - ("%s: bad popmap slot %d in node %p", - __func__, slot, node)); - if (parent == NULL) - pctrie_root_store(ptree, tmp, PCTRIE_LOCKED); - else { - slot = pctrie_slot(index, parent->pn_clev); - KASSERT(pctrie_node_load( - &parent->pn_child[slot], NULL, - PCTRIE_LOCKED) == node, - ("%s: invalid child value", __func__)); - pctrie_node_store(&parent->pn_child[slot], tmp, - PCTRIE_LOCKED); - } - /* - * The child is still valid and we can not zero the - * pointer until all SMR references are gone. - */ - pctrie_node_put(ptree, node, freefn); + if (pctrie_isleaf(child)) break; - } parent = node; - node = tmp; + node = child; + slot = pctrie_slot(index, node->pn_clev); + child = pctrie_node_load(&node->pn_child[slot], NULL, + PCTRIE_LOCKED); + } + if ((m = pctrie_toval(child)) == NULL || *m != index) + panic("%s: key not found", __func__); + if (node == NULL) { + pctrie_root_store(ptree, PCTRIE_NULL, PCTRIE_LOCKED); + return; + } + KASSERT((node->pn_popmap & (1 << slot)) != 0, + ("%s: bad popmap slot %d in node %p", + __func__, slot, node)); + node->pn_popmap ^= 1 << slot; + pctrie_node_store(&node->pn_child[slot], PCTRIE_NULL, PCTRIE_LOCKED); + if (!powerof2(node->pn_popmap)) + return; + KASSERT(node->pn_popmap != 0, ("%s: bad popmap all zeroes", __func__)); + slot = ffs(node->pn_popmap) - 1; + child = pctrie_node_load(&node->pn_child[slot], NULL, PCTRIE_LOCKED); + KASSERT(child != PCTRIE_NULL, + ("%s: bad popmap slot %d in node %p", __func__, slot, node)); + if (parent == NULL) + pctrie_root_store(ptree, child, PCTRIE_LOCKED); + else { + slot = pctrie_slot(index, parent->pn_clev); + KASSERT(node == + pctrie_node_load(&parent->pn_child[slot], NULL, + PCTRIE_LOCKED), ("%s: invalid child value", __func__)); + pctrie_node_store(&parent->pn_child[slot], child, + PCTRIE_LOCKED); } + /* + * The child is still valid and we can not zero the + * pointer until all SMR references are gone. + */ + pctrie_node_put(ptree, node, freefn); } /* @@ -699,9 +692,9 @@ pctrie_reclaim_allnodes(struct pctrie *ptree, pctrie_free_t freefn) struct pctrie_node *root; root = pctrie_root_load(ptree, NULL, PCTRIE_LOCKED); - if (root == NULL) + if (root == PCTRIE_NULL) return; - pctrie_root_store(ptree, NULL, PCTRIE_UNSERIALIZED); + pctrie_root_store(ptree, PCTRIE_NULL, PCTRIE_UNSERIALIZED); if (!pctrie_isleaf(root)) pctrie_reclaim_allnodes_int(ptree, root, freefn); } diff --git a/sys/sys/_pctrie.h b/sys/sys/_pctrie.h index b7947889e176..bc2f6a781066 100644 --- a/sys/sys/_pctrie.h +++ b/sys/sys/_pctrie.h @@ -33,11 +33,16 @@ #ifndef __SYS_PCTRIE_H_ #define __SYS_PCTRIE_H_ +/* + * Radix tree node. + */ +struct pctrie_node; + /* * Radix tree root. */ struct pctrie { - uintptr_t pt_root; + struct pctrie_node *pt_root; }; #endif /* !__SYS_PCTRIE_H_ */ diff --git a/sys/sys/pctrie.h b/sys/sys/pctrie.h index 1968cb521fd6..687236cdd872 100644 --- a/sys/sys/pctrie.h +++ b/sys/sys/pctrie.h @@ -135,18 +135,24 @@ void pctrie_remove(struct pctrie *ptree, uint64_t key, size_t pctrie_node_size(void); int pctrie_zone_init(void *mem, int size, int flags); +/* + * Each search path in the trie terminates at a leaf, which is a pointer to a + * value marked with a set 1-bit. A leaf may be associated with a null pointer + * to indicate no value there. + */ +#define PCTRIE_ISLEAF 0x1 +#define PCTRIE_NULL (struct pctrie_node *)PCTRIE_ISLEAF + static __inline void pctrie_init(struct pctrie *ptree) { - - ptree->pt_root = 0; + ptree->pt_root = PCTRIE_NULL; } static __inline bool pctrie_is_empty(struct pctrie *ptree) { - - return (ptree->pt_root == 0); + return (ptree->pt_root == PCTRIE_NULL); } /* diff --git a/sys/vm/_vm_radix.h b/sys/vm/_vm_radix.h index 77e364d1d238..26f112ee3ee8 100644 --- a/sys/vm/_vm_radix.h +++ b/sys/vm/_vm_radix.h @@ -33,11 +33,16 @@ #ifndef __VM_RADIX_H_ #define __VM_RADIX_H_ +/* + * Radix tree node. + */ +struct vm_radix_node; + /* * Radix tree root. */ struct vm_radix { - uintptr_t rt_root; + struct vm_radix_node *rt_root; }; #endif /* !__VM_RADIX_H_ */ diff --git a/sys/vm/vm_radix.c b/sys/vm/vm_radix.c index 6504d5031460..3c4ea9568108 100644 --- a/sys/vm/vm_radix.c +++ b/sys/vm/vm_radix.c @@ -103,9 +103,8 @@ typedef uint32_t rn_popmap_t; _Static_assert(sizeof(rn_popmap_t) <= sizeof(int), "rn_popmap_t too wide"); -/* Flag bits stored in node pointers. */ -#define VM_RADIX_ISLEAF 0x1 -#define VM_RADIX_FLAGS 0x1 +/* Set of all flag bits stored in node pointers. */ +#define VM_RADIX_FLAGS (VM_RADIX_ISLEAF) #define VM_RADIX_PAD VM_RADIX_FLAGS /* Returns one unit associated with specified level. */ @@ -165,7 +164,7 @@ vm_radix_node_get(vm_pindex_t index, uint16_t clevel) */ if (rnode->rn_popmap != 0) { vm_radix_node_store(&rnode->rn_child[ffs(rnode->rn_popmap) - 1], - NULL, UNSERIALIZED); + VM_RADIX_NULL, UNSERIALIZED); rnode->rn_popmap = 0; } rnode->rn_owner = vm_radix_trimkey(index, clevel + 1); @@ -189,7 +188,8 @@ vm_radix_node_put(struct vm_radix_node *rnode) if ((rnode->rn_popmap & (1 << slot)) != 0) continue; KASSERT(smr_unserialized_load(&rnode->rn_child[slot], true) == - NULL, ("vm_radix_node_put: rnode %p has a child", rnode)); + VM_RADIX_NULL, + ("vm_radix_node_put: rnode %p has a child", rnode)); } #endif uma_zfree_smr(vm_radix_node_zone, rnode); @@ -344,17 +344,34 @@ vm_radix_reclaim_allnodes_int(struct vm_radix_node *rnode) slot = ffs(rnode->rn_popmap) - 1; child = vm_radix_node_load(&rnode->rn_child[slot], UNSERIALIZED); - KASSERT(child != NULL, ("%s: bad popmap slot %d in rnode %p", + KASSERT(child != VM_RADIX_NULL, + ("%s: bad popmap slot %d in rnode %p", __func__, slot, rnode)); if (!vm_radix_isleaf(child)) vm_radix_reclaim_allnodes_int(child); rnode->rn_popmap ^= 1 << slot; - vm_radix_node_store(&rnode->rn_child[slot], NULL, + vm_radix_node_store(&rnode->rn_child[slot], VM_RADIX_NULL, UNSERIALIZED); } vm_radix_node_put(rnode); } +/* + * radix node zone initializer. + */ +static int +vm_radix_zone_init(void *mem, int size, int flags) +{ + struct vm_radix_node *rnode; + + rnode = mem; + rnode->rn_popmap = 0; + for (int i = 0; i < nitems(rnode->rn_child); i++) + vm_radix_node_store(&rnode->rn_child[i], VM_RADIX_NULL, + UNSERIALIZED); + return (0); +} + #ifndef UMA_MD_SMALL_ALLOC void vm_radix_reserve_kva(void); /* @@ -387,8 +404,8 @@ vm_radix_zinit(void) { vm_radix_node_zone = uma_zcreate("RADIX NODE", - sizeof(struct vm_radix_node), NULL, NULL, NULL, NULL, - VM_RADIX_PAD, UMA_ZONE_VM | UMA_ZONE_SMR | UMA_ZONE_ZINIT); + sizeof(struct vm_radix_node), NULL, NULL, vm_radix_zone_init, NULL, + VM_RADIX_PAD, UMA_ZONE_VM | UMA_ZONE_SMR); vm_radix_smr = uma_zone_get_smr(vm_radix_node_zone); } @@ -400,7 +417,7 @@ int vm_radix_insert(struct vm_radix *rtree, vm_page_t page) { vm_pindex_t index, newind; - struct vm_radix_node *leaf, *rnode, *tmp; + struct vm_radix_node *leaf, *parent, *rnode; smrnode_t *parentp; int slot; uint16_t clev; @@ -413,29 +430,30 @@ vm_radix_insert(struct vm_radix *rtree, vm_page_t page) * will never be used. */ rnode = vm_radix_root_load(rtree, LOCKED); - if (rnode == NULL) { - rtree->rt_root = (uintptr_t)leaf; - return (0); - } - for (parentp = (smrnode_t *)&rtree->rt_root;; rnode = tmp) { + parent = NULL; + for (;;) { if (vm_radix_isleaf(rnode)) { + if (rnode == VM_RADIX_NULL) { + if (parent == NULL) + rtree->rt_root = leaf; + else + vm_radix_addnode(parent, index, + parent->rn_clev, leaf, LOCKED); + return (0); + } newind = vm_radix_topage(rnode)->pindex; if (newind == index) panic("%s: key %jx is already present", __func__, (uintmax_t)index); break; - } else if (vm_radix_keybarr(rnode, index)) { + } + if (vm_radix_keybarr(rnode, index)) { newind = rnode->rn_owner; break; } slot = vm_radix_slot(index, rnode->rn_clev); - parentp = &rnode->rn_child[slot]; - tmp = vm_radix_node_load(parentp, LOCKED); - if (tmp == NULL) { - vm_radix_addnode(rnode, index, rnode->rn_clev, leaf, - LOCKED); - return (0); - } + parent = rnode; + rnode = vm_radix_node_load(&rnode->rn_child[slot], LOCKED); } /* @@ -443,15 +461,17 @@ vm_radix_insert(struct vm_radix *rtree, vm_page_t page) * Setup the new intermediate node and add the 2 children: the * new object and the older edge or object. */ + parentp = (parent != NULL) ? &parent->rn_child[slot]: + (smrnode_t *)&rtree->rt_root; clev = vm_radix_keydiff(newind, index); - tmp = vm_radix_node_get(index, clev); - if (tmp == NULL) + parent = vm_radix_node_get(index, clev); + if (parent == NULL) return (ENOMEM); /* These writes are not yet visible due to ordering. */ - vm_radix_addnode(tmp, index, clev, leaf, UNSERIALIZED); - vm_radix_addnode(tmp, newind, clev, rnode, UNSERIALIZED); + vm_radix_addnode(parent, index, clev, leaf, UNSERIALIZED); + vm_radix_addnode(parent, newind, clev, rnode, UNSERIALIZED); /* Serializing write to make the above visible. */ - vm_radix_node_store(parentp, tmp, LOCKED); + vm_radix_node_store(parentp, parent, LOCKED); return (0); } @@ -468,10 +488,10 @@ _vm_radix_lookup(struct vm_radix *rtree, vm_pindex_t index, int slot; rnode = vm_radix_root_load(rtree, access); - while (rnode != NULL) { + for (;;) { if (vm_radix_isleaf(rnode)) { - m = vm_radix_topage(rnode); - if (m->pindex == index) + if ((m = vm_radix_topage(rnode)) != NULL && + m->pindex == index) return (m); break; } @@ -540,10 +560,10 @@ vm_radix_lookup_ge(struct vm_radix *rtree, vm_pindex_t index) */ rnode = vm_radix_root_load(rtree, LOCKED); succ = NULL; - while (rnode != NULL) { + for (;;) { if (vm_radix_isleaf(rnode)) { - m = vm_radix_topage(rnode); - if (m->pindex >= index) + if ((m = vm_radix_topage(rnode)) != NULL && + m->pindex >= index) return (m); break; } @@ -619,10 +639,10 @@ vm_radix_lookup_le(struct vm_radix *rtree, vm_pindex_t index) */ rnode = vm_radix_root_load(rtree, LOCKED); pred = NULL; - while (rnode != NULL) { + for (;;) { if (vm_radix_isleaf(rnode)) { - m = vm_radix_topage(rnode); - if (m->pindex <= index) + if ((m = vm_radix_topage(rnode)) != NULL && + m->pindex <= index) return (m); break; } @@ -662,63 +682,52 @@ vm_radix_lookup_le(struct vm_radix *rtree, vm_pindex_t index) vm_page_t vm_radix_remove(struct vm_radix *rtree, vm_pindex_t index) { - struct vm_radix_node *rnode, *parent, *tmp; + struct vm_radix_node *child, *parent, *rnode; vm_page_t m; int slot; - rnode = vm_radix_root_load(rtree, LOCKED); - if (vm_radix_isleaf(rnode)) { - m = vm_radix_topage(rnode); - if (m->pindex != index) - return (NULL); - vm_radix_root_store(rtree, NULL, LOCKED); - return (m); - } - parent = NULL; + rnode = NULL; + child = vm_radix_root_load(rtree, LOCKED); for (;;) { - if (rnode == NULL) - return (NULL); - slot = vm_radix_slot(index, rnode->rn_clev); - tmp = vm_radix_node_load(&rnode->rn_child[slot], LOCKED); - if (vm_radix_isleaf(tmp)) { - m = vm_radix_topage(tmp); - if (m->pindex != index) - return (NULL); - KASSERT((rnode->rn_popmap & (1 << slot)) != 0, - ("%s: bad popmap slot %d in rnode %p", - __func__, slot, rnode)); - rnode->rn_popmap ^= 1 << slot; - vm_radix_node_store( - &rnode->rn_child[slot], NULL, LOCKED); - if (!powerof2(rnode->rn_popmap)) - return (m); - KASSERT(rnode->rn_popmap != 0, - ("%s: bad popmap all zeroes", __func__)); - slot = ffs(rnode->rn_popmap) - 1; - tmp = vm_radix_node_load(&rnode->rn_child[slot], LOCKED); - KASSERT(tmp != NULL, - ("%s: bad popmap slot %d in rnode %p", - __func__, slot, rnode)); - if (parent == NULL) - vm_radix_root_store(rtree, tmp, LOCKED); - else { - slot = vm_radix_slot(index, parent->rn_clev); - KASSERT(vm_radix_node_load( - &parent->rn_child[slot], LOCKED) == rnode, - ("%s: invalid child value", __func__)); - vm_radix_node_store(&parent->rn_child[slot], - tmp, LOCKED); - } - /* - * The child is still valid and we can not zero the - * pointer until all smr references are gone. - */ - vm_radix_node_put(rnode); - return (m); - } + if (vm_radix_isleaf(child)) + break; parent = rnode; - rnode = tmp; + rnode = child; + slot = vm_radix_slot(index, rnode->rn_clev); + child = vm_radix_node_load(&rnode->rn_child[slot], LOCKED); + } + if ((m = vm_radix_topage(child)) == NULL || m->pindex != index) + return (NULL); + if (rnode == NULL) { + vm_radix_root_store(rtree, VM_RADIX_NULL, LOCKED); + return (m); + } + KASSERT((rnode->rn_popmap & (1 << slot)) != 0, + ("%s: bad popmap slot %d in rnode %p", __func__, slot, rnode)); + rnode->rn_popmap ^= 1 << slot; + vm_radix_node_store(&rnode->rn_child[slot], VM_RADIX_NULL, LOCKED); + if (!powerof2(rnode->rn_popmap)) + return (m); + KASSERT(rnode->rn_popmap != 0, ("%s: bad popmap all zeroes", __func__)); + slot = ffs(rnode->rn_popmap) - 1; + child = vm_radix_node_load(&rnode->rn_child[slot], LOCKED); + KASSERT(child != VM_RADIX_NULL, + ("%s: bad popmap slot %d in rnode %p", __func__, slot, rnode)); + if (parent == NULL) + vm_radix_root_store(rtree, child, LOCKED); + else { + slot = vm_radix_slot(index, parent->rn_clev); + KASSERT(rnode == + vm_radix_node_load(&parent->rn_child[slot], LOCKED), + ("%s: invalid child value", __func__)); + vm_radix_node_store(&parent->rn_child[slot], child, LOCKED); } + /* + * The child is still valid and we can not zero the + * pointer until all smr references are gone. + */ + vm_radix_node_put(rnode); + return (m); } /* @@ -732,9 +741,9 @@ vm_radix_reclaim_allnodes(struct vm_radix *rtree) struct vm_radix_node *root; root = vm_radix_root_load(rtree, LOCKED); - if (root == NULL) + if (root == VM_RADIX_NULL) return; - vm_radix_root_store(rtree, NULL, UNSERIALIZED); + vm_radix_root_store(rtree, VM_RADIX_NULL, UNSERIALIZED); if (!vm_radix_isleaf(root)) vm_radix_reclaim_allnodes_int(root); } @@ -746,36 +755,34 @@ vm_radix_reclaim_allnodes(struct vm_radix *rtree) vm_page_t vm_radix_replace(struct vm_radix *rtree, vm_page_t newpage) { - struct vm_radix_node *rnode, *tmp; + struct vm_radix_node *leaf, *parent, *rnode; vm_page_t m; vm_pindex_t index; int slot; + leaf = vm_radix_toleaf(newpage); index = newpage->pindex; rnode = vm_radix_root_load(rtree, LOCKED); - if (rnode == NULL) - panic("%s: replacing page on an empty trie", __func__); - if (vm_radix_isleaf(rnode)) { - m = vm_radix_topage(rnode); - if (m->pindex != index) - panic("%s: original replacing root key not found", - __func__); - rtree->rt_root = (uintptr_t)vm_radix_toleaf(newpage); - return (m); - } + parent = NULL; for (;;) { - slot = vm_radix_slot(index, rnode->rn_clev); - tmp = vm_radix_node_load(&rnode->rn_child[slot], LOCKED); - if (vm_radix_isleaf(tmp)) { - m = vm_radix_topage(tmp); - if (m->pindex != index) - break; - vm_radix_node_store(&rnode->rn_child[slot], - vm_radix_toleaf(newpage), LOCKED); - return (m); - } else if (tmp == NULL || vm_radix_keybarr(tmp, index)) + if (vm_radix_isleaf(rnode)) { + if ((m = vm_radix_topage(rnode)) != NULL && + m->pindex == index) { + if (parent == NULL) + rtree->rt_root = leaf; + else + vm_radix_node_store( + &parent->rn_child[slot], leaf, + LOCKED); + return (m); + } + break; + } + if (vm_radix_keybarr(rnode, index)) break; - rnode = tmp; + slot = vm_radix_slot(index, rnode->rn_clev); + parent = rnode; + rnode = vm_radix_node_load(&rnode->rn_child[slot], LOCKED); } panic("%s: original replacing page not found", __func__); } diff --git a/sys/vm/vm_radix.h b/sys/vm/vm_radix.h index b478cf4b734b..becfbaedccf5 100644 --- a/sys/vm/vm_radix.h +++ b/sys/vm/vm_radix.h @@ -48,18 +48,24 @@ vm_page_t vm_radix_remove(struct vm_radix *rtree, vm_pindex_t index); vm_page_t vm_radix_replace(struct vm_radix *rtree, vm_page_t newpage); void vm_radix_zinit(void); +/* + * Each search path in the trie terminates at a leaf, which is a pointer to a + * page marked with a set 1-bit. A leaf may be associated with a null pointer + * to indicate no page there. + */ +#define VM_RADIX_ISLEAF 0x1 +#define VM_RADIX_NULL (struct vm_radix_node *)VM_RADIX_ISLEAF + static __inline void vm_radix_init(struct vm_radix *rtree) { - - rtree->rt_root = 0; + rtree->rt_root = VM_RADIX_NULL; } static __inline bool vm_radix_is_empty(struct vm_radix *rtree) { - - return (rtree->rt_root == 0); + return (rtree->rt_root == VM_RADIX_NULL); } #endif /* _KERNEL */