git: 16e01c05c09e - main - radix_trie: avoid code duplication in insert
- Go to: [ bottom of page ] [ top of archives ] [ this month ]
Date: Sun, 09 Jul 2023 20:07:00 UTC
The branch main has been updated by dougm:
URL: https://cgit.FreeBSD.org/src/commit/?id=16e01c05c09e4223103fa36e4057f7ed3b92146b
commit 16e01c05c09e4223103fa36e4057f7ed3b92146b
Author: Doug Moore <dougm@FreeBSD.org>
AuthorDate: 2023-07-09 20:06:02 +0000
Commit: Doug Moore <dougm@FreeBSD.org>
CommitDate: 2023-07-09 20:06:02 +0000
radix_trie: avoid code duplication in insert
Two cases in the insert routine are written differently, when
they're really doing the same thing. Writing that case only once
saves 208 bytes in the compiled vm_radix_insert code and reduces
instructions executed by about 2%.
Reviewed by: alc
Tested by: pho
Differential Revision: https://reviews.freebsd.org/D40807
---
sys/kern/subr_pctrie.c | 51 ++++++++++++++++++--------------------------------
sys/vm/vm_radix.c | 50 ++++++++++++++++++-------------------------------
2 files changed, 36 insertions(+), 65 deletions(-)
diff --git a/sys/kern/subr_pctrie.c b/sys/kern/subr_pctrie.c
index cf09903556ec..ae8408a6e1ef 100644
--- a/sys/kern/subr_pctrie.c
+++ b/sys/kern/subr_pctrie.c
@@ -256,17 +256,16 @@ pctrie_toval(struct pctrie_node *node)
}
/*
- * Adds the val as a child of the provided node.
+ * Make 'child' a child of 'node'.
*/
static __inline void
-pctrie_addval(struct pctrie_node *node, uint64_t index, uint16_t clev,
- uint64_t *val, enum pctrie_access access)
+pctrie_addnode(struct pctrie_node *node, uint64_t index, uint16_t clev,
+ struct pctrie_node *child, enum pctrie_access access)
{
int slot;
slot = pctrie_slot(index, clev);
- pctrie_node_store(&node->pn_child[slot],
- pctrie_toleaf(val), access);
+ pctrie_node_store(&node->pn_child[slot], child, access);
node->pn_popmap ^= 1 << slot;
KASSERT((node->pn_popmap & (1 << slot)) != 0,
("%s: bad popmap slot %d in node %p", __func__, slot, node));
@@ -361,13 +360,13 @@ int
pctrie_insert(struct pctrie *ptree, uint64_t *val, pctrie_alloc_t allocfn)
{
uint64_t index, newind;
- struct pctrie_node *node, *tmp;
+ struct pctrie_node *leaf, *node, *tmp;
smr_pctnode_t *parentp;
- uint64_t *m;
int slot;
uint16_t clev;
index = *val;
+ leaf = pctrie_toleaf(val);
/*
* The owner of record for root is not really important because it
@@ -375,58 +374,44 @@ pctrie_insert(struct pctrie *ptree, uint64_t *val, pctrie_alloc_t allocfn)
*/
node = pctrie_root_load(ptree, NULL, PCTRIE_LOCKED);
if (node == NULL) {
- ptree->pt_root = (uintptr_t)pctrie_toleaf(val);
+ ptree->pt_root = (uintptr_t)leaf;
return (0);
}
- parentp = (smr_pctnode_t *)&ptree->pt_root;
- for (;;) {
+ for (parentp = (smr_pctnode_t *)&ptree->pt_root;; node = tmp) {
if (pctrie_isleaf(node)) {
- m = pctrie_toval(node);
- if (*m == index)
+ newind = *pctrie_toval(node);
+ if (newind == index)
panic("%s: key %jx is already present",
__func__, (uintmax_t)index);
- clev = pctrie_keydiff(*m, index);
- tmp = pctrie_node_get(ptree, allocfn, index, clev);
- if (tmp == NULL)
- return (ENOMEM);
- /* These writes are not yet visible due to ordering. */
- pctrie_addval(tmp, index, clev, val,
- PCTRIE_UNSERIALIZED);
- pctrie_addval(tmp, *m, clev, m, PCTRIE_UNSERIALIZED);
- /* Synchronize to make leaf visible. */
- pctrie_node_store(parentp, tmp, PCTRIE_LOCKED);
- return (0);
- } else if (pctrie_keybarr(node, index))
break;
+ } else 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_addval(node, index, node->pn_clev, val,
+ pctrie_addnode(node, index, node->pn_clev, leaf,
PCTRIE_LOCKED);
return (0);
}
- node = tmp;
}
/*
* A new node is needed because the right insertion level is reached.
* Setup the new intermediate node and add the 2 children: the
- * new object and the older edge.
+ * new object and the older edge or object.
*/
- newind = node->pn_owner;
clev = pctrie_keydiff(newind, index);
tmp = pctrie_node_get(ptree, allocfn, index, clev);
if (tmp == NULL)
return (ENOMEM);
- slot = pctrie_slot(newind, clev);
/* These writes are not yet visible due to ordering. */
- pctrie_addval(tmp, index, clev, val, PCTRIE_UNSERIALIZED);
- pctrie_node_store(&tmp->pn_child[slot], node, PCTRIE_UNSERIALIZED);
- tmp->pn_popmap ^= 1 << slot;
+ pctrie_addnode(tmp, index, clev, leaf, PCTRIE_UNSERIALIZED);
+ pctrie_addnode(tmp, newind, clev, node, PCTRIE_UNSERIALIZED);
/* Synchronize to make the above visible. */
pctrie_node_store(parentp, tmp, PCTRIE_LOCKED);
-
return (0);
}
diff --git a/sys/vm/vm_radix.c b/sys/vm/vm_radix.c
index d2cd2c2536fd..f6bdda70539b 100644
--- a/sys/vm/vm_radix.c
+++ b/sys/vm/vm_radix.c
@@ -281,17 +281,16 @@ vm_radix_topage(struct vm_radix_node *rnode)
}
/*
- * Adds the page as a child of the provided node.
+ * Make 'child' a child of 'rnode'.
*/
static __inline void
-vm_radix_addpage(struct vm_radix_node *rnode, vm_pindex_t index, uint16_t clev,
- vm_page_t page, enum vm_radix_access access)
+vm_radix_addnode(struct vm_radix_node *rnode, vm_pindex_t index, uint16_t clev,
+ struct vm_radix_node *child, enum vm_radix_access access)
{
int slot;
slot = vm_radix_slot(index, clev);
- vm_radix_node_store(&rnode->rn_child[slot],
- vm_radix_toleaf(page), access);
+ vm_radix_node_store(&rnode->rn_child[slot], child, access);
rnode->rn_popmap ^= 1 << slot;
KASSERT((rnode->rn_popmap & (1 << slot)) != 0,
("%s: bad popmap slot %d in rnode %p", __func__, slot, rnode));
@@ -401,13 +400,13 @@ int
vm_radix_insert(struct vm_radix *rtree, vm_page_t page)
{
vm_pindex_t index, newind;
- struct vm_radix_node *rnode, *tmp;
+ struct vm_radix_node *leaf, *rnode, *tmp;
smrnode_t *parentp;
- vm_page_t m;
int slot;
uint16_t clev;
index = page->pindex;
+ leaf = vm_radix_toleaf(page);
/*
* The owner of record for root is not really important because it
@@ -415,57 +414,44 @@ vm_radix_insert(struct vm_radix *rtree, vm_page_t page)
*/
rnode = vm_radix_root_load(rtree, LOCKED);
if (rnode == NULL) {
- rtree->rt_root = (uintptr_t)vm_radix_toleaf(page);
+ rtree->rt_root = (uintptr_t)leaf;
return (0);
}
- parentp = (smrnode_t *)&rtree->rt_root;
- for (;;) {
+ for (parentp = (smrnode_t *)&rtree->rt_root;; rnode = tmp) {
if (vm_radix_isleaf(rnode)) {
- m = vm_radix_topage(rnode);
- if (m->pindex == index)
+ newind = vm_radix_topage(rnode)->pindex;
+ if (newind == index)
panic("%s: key %jx is already present",
__func__, (uintmax_t)index);
- clev = vm_radix_keydiff(m->pindex, index);
- tmp = vm_radix_node_get(index, clev);
- if (tmp == NULL)
- return (ENOMEM);
- /* These writes are not yet visible due to ordering. */
- vm_radix_addpage(tmp, index, clev, page, UNSERIALIZED);
- vm_radix_addpage(tmp, m->pindex, clev, m, UNSERIALIZED);
- /* Synchronize to make leaf visible. */
- vm_radix_node_store(parentp, tmp, LOCKED);
- return (0);
- } else if (vm_radix_keybarr(rnode, index))
break;
+ } else 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_addpage(rnode, index, rnode->rn_clev, page,
+ vm_radix_addnode(rnode, index, rnode->rn_clev, leaf,
LOCKED);
return (0);
}
- rnode = tmp;
}
/*
* A new node is needed because the right insertion level is reached.
* Setup the new intermediate node and add the 2 children: the
- * new object and the older edge.
+ * new object and the older edge or object.
*/
- newind = rnode->rn_owner;
clev = vm_radix_keydiff(newind, index);
tmp = vm_radix_node_get(index, clev);
if (tmp == NULL)
return (ENOMEM);
- slot = vm_radix_slot(newind, clev);
/* These writes are not yet visible due to ordering. */
- vm_radix_addpage(tmp, index, clev, page, UNSERIALIZED);
- vm_radix_node_store(&tmp->rn_child[slot], rnode, UNSERIALIZED);
- tmp->rn_popmap ^= 1 << slot;
+ vm_radix_addnode(tmp, index, clev, leaf, UNSERIALIZED);
+ vm_radix_addnode(tmp, newind, clev, rnode, UNSERIALIZED);
/* Serializing write to make the above visible. */
vm_radix_node_store(parentp, tmp, LOCKED);
-
return (0);
}