git: ac0572e66067 - main - radix_tree: compute slot from keybarr
- Go to: [ bottom of page ] [ top of archives ] [ this month ]
Date: Sun, 30 Jul 2023 20:21:05 UTC
The branch main has been updated by dougm:
URL: https://cgit.FreeBSD.org/src/commit/?id=ac0572e6606746aa0e9f39fb6439f9a20a455743
commit ac0572e6606746aa0e9f39fb6439f9a20a455743
Author: Doug Moore <dougm@FreeBSD.org>
AuthorDate: 2023-07-30 20:12:06 +0000
Commit: Doug Moore <dougm@FreeBSD.org>
CommitDate: 2023-07-30 20:12:06 +0000
radix_tree: compute slot from keybarr
The computation of keybarr(), the function that determines when a
search has failed at a non-leaf node, can be done in a way that
computes the 'slot' value when keybarr() fails, which is exactly when
slot() would next be invoked. Computing things this way saves space in
search loops.
This reduces the amd64 coding of the search loop in vm_radix_lookup
from 40 bytes to 28 bytes.
Reviewed by: alc
Tested by: pho (as part of a larger change)
Differential Revision: https://reviews.freebsd.org/D41235
---
sys/kern/subr_pctrie.c | 57 +++++++++++++++++++++-------------------------
sys/vm/vm_radix.c | 61 +++++++++++++++++++++-----------------------------
2 files changed, 51 insertions(+), 67 deletions(-)
diff --git a/sys/kern/subr_pctrie.c b/sys/kern/subr_pctrie.c
index c08e4b5910a5..c0e100173adc 100644
--- a/sys/kern/subr_pctrie.c
+++ b/sys/kern/subr_pctrie.c
@@ -99,19 +99,26 @@ static __inline void pctrie_node_store(smr_pctnode_t *p, void *val,
enum pctrie_access access);
/*
- * Return the position in the array for a given level.
+ * Map index to an array position for the children of node,
*/
static __inline int
-pctrie_slot(uint64_t index, uint16_t level)
+pctrie_slot(struct pctrie_node *node, uint64_t index)
{
- return ((index >> level) & PCTRIE_MASK);
+ return ((index >> node->pn_clev) & PCTRIE_MASK);
}
-/* Computes the key (index) with the low-order 'level' + 1 radix-digits zeroed. */
-static __inline uint64_t
-pctrie_trimkey(uint64_t index, uint16_t level)
+/*
+ * Returns true if index does not belong to the specified node. Otherwise,
+ * sets slot value, and returns false.
+ */
+static __inline bool
+pctrie_keybarr(struct pctrie_node *node, uint64_t index, int *slot)
{
- return (index & -((uint64_t)PCTRIE_COUNT << level));
+ index = (index - node->pn_owner) >> node->pn_clev;
+ if (index >= PCTRIE_COUNT)
+ return (true);
+ *slot = index;
+ return (false);
}
/*
@@ -151,7 +158,8 @@ pctrie_node_get(struct pctrie *ptree, pctrie_alloc_t allocfn, uint64_t index,
_Static_assert(sizeof(uint64_t) * NBBY <=
(1 << (sizeof(node->pn_clev) * NBBY)), "pn_clev too narrow");
node->pn_clev = rounddown(flsll(index ^ newind) - 1, PCTRIE_WIDTH);
- node->pn_owner = pctrie_trimkey(index, node->pn_clev);
+ node->pn_owner = PCTRIE_COUNT;
+ node->pn_owner = index & -(node->pn_owner << node->pn_clev);
return (node);
}
@@ -272,24 +280,13 @@ pctrie_addnode(struct pctrie_node *node, uint64_t index,
{
int slot;
- slot = pctrie_slot(index, node->pn_clev);
+ slot = pctrie_slot(node, index);
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));
}
-/*
- * Returns TRUE if it can be determined that key does not belong to the
- * specified node. Otherwise, returns FALSE.
- */
-static __inline bool
-pctrie_keybarr(struct pctrie_node *node, uint64_t idx)
-{
- idx = pctrie_trimkey(idx, node->pn_clev);
- return (idx != node->pn_owner);
-}
-
/*
* Internal helper for pctrie_reclaim_allnodes().
* This function is recursive.
@@ -377,11 +374,10 @@ pctrie_insert(struct pctrie *ptree, uint64_t *val, pctrie_alloc_t allocfn)
__func__, (uintmax_t)index);
break;
}
- if (pctrie_keybarr(node, index)) {
+ if (pctrie_keybarr(node, index, &slot)) {
newind = node->pn_owner;
break;
}
- slot = pctrie_slot(index, node->pn_clev);
parent = node;
node = pctrie_node_load(&node->pn_child[slot], NULL,
PCTRIE_LOCKED);
@@ -424,9 +420,8 @@ _pctrie_lookup(struct pctrie *ptree, uint64_t index, smr_t smr,
return (m);
break;
}
- if (pctrie_keybarr(node, index))
+ if (pctrie_keybarr(node, index, &slot))
break;
- slot = pctrie_slot(index, node->pn_clev);
node = pctrie_node_load(&node->pn_child[slot], smr, access);
}
return (NULL);
@@ -494,7 +489,7 @@ pctrie_lookup_ge(struct pctrie *ptree, uint64_t index)
return (m);
break;
}
- if (pctrie_keybarr(node, index)) {
+ if (pctrie_keybarr(node, index, &slot)) {
/*
* If all values in this subtree are > index, then the
* least value in this subtree is the answer.
@@ -503,7 +498,6 @@ pctrie_lookup_ge(struct pctrie *ptree, uint64_t index)
succ = node;
break;
}
- slot = pctrie_slot(index, node->pn_clev);
/*
* Just in case the next search step leads to a subtree of all
@@ -528,7 +522,7 @@ pctrie_lookup_ge(struct pctrie *ptree, uint64_t index)
* Take a step to the next bigger sibling of the node chosen
* last time. In that subtree, all values > index.
*/
- slot = pctrie_slot(index, succ->pn_clev) + 1;
+ slot = pctrie_slot(succ, index) + 1;
KASSERT((succ->pn_popmap >> slot) != 0,
("%s: no popmap siblings past slot %d in node %p",
__func__, slot, succ));
@@ -574,12 +568,11 @@ pctrie_lookup_le(struct pctrie *ptree, uint64_t index)
return (m);
break;
}
- if (pctrie_keybarr(node, index)) {
+ if (pctrie_keybarr(node, index, &slot)) {
if (node->pn_owner < index)
pred = node;
break;
}
- slot = pctrie_slot(index, node->pn_clev);
if ((node->pn_popmap & ((1 << slot) - 1)) != 0)
pred = node;
node = pctrie_node_load(&node->pn_child[slot], NULL,
@@ -588,7 +581,7 @@ pctrie_lookup_le(struct pctrie *ptree, uint64_t index)
if (pred == NULL)
return (NULL);
if (pred != node) {
- slot = pctrie_slot(index, pred->pn_clev);
+ slot = pctrie_slot(pred, index);
KASSERT((pred->pn_popmap & ((1 << slot) - 1)) != 0,
("%s: no popmap siblings before slot %d in node %p",
__func__, slot, pred));
@@ -624,7 +617,7 @@ pctrie_remove(struct pctrie *ptree, uint64_t index, pctrie_free_t freefn)
break;
parent = node;
node = child;
- slot = pctrie_slot(index, node->pn_clev);
+ slot = pctrie_slot(node, index);
child = pctrie_node_load(&node->pn_child[slot], NULL,
PCTRIE_LOCKED);
}
@@ -649,7 +642,7 @@ pctrie_remove(struct pctrie *ptree, uint64_t index, pctrie_free_t freefn)
if (parent == NULL)
pctrie_root_store(ptree, child, PCTRIE_LOCKED);
else {
- slot = pctrie_slot(index, parent->pn_clev);
+ slot = pctrie_slot(parent, index);
KASSERT(node ==
pctrie_node_load(&parent->pn_child[slot], NULL,
PCTRIE_LOCKED), ("%s: invalid child value", __func__));
diff --git a/sys/vm/vm_radix.c b/sys/vm/vm_radix.c
index f50f9e3605a1..c678bfe1baa7 100644
--- a/sys/vm/vm_radix.c
+++ b/sys/vm/vm_radix.c
@@ -126,20 +126,26 @@ static void vm_radix_node_store(smrnode_t *p, struct vm_radix_node *v,
enum vm_radix_access access);
/*
- * Return the position in the array for a given level.
+ * Map index to an array position for the children of rnode,
*/
static __inline int
-vm_radix_slot(vm_pindex_t index, uint16_t level)
+vm_radix_slot(struct vm_radix_node *rnode, vm_pindex_t index)
{
- return ((index >> level) & VM_RADIX_MASK);
+ return ((index >> rnode->rn_clev) & VM_RADIX_MASK);
}
-/* Computes the key (index) with the low-order 'level' + 1 radix-digits
- * zeroed. */
-static __inline vm_pindex_t
-vm_radix_trimkey(vm_pindex_t index, uint16_t level)
+/*
+ * Returns true if index does not belong to the specified rnode. Otherwise,
+ * sets slot value, and returns false.
+ */
+static __inline bool
+vm_radix_keybarr(struct vm_radix_node *rnode, vm_pindex_t index, int *slot)
{
- return (index & -((vm_pindex_t)VM_RADIX_COUNT << level));
+ index = (index - rnode->rn_owner) >> rnode->rn_clev;
+ if (index >= VM_RADIX_COUNT)
+ return (true);
+ *slot = index;
+ return (false);
}
/*
@@ -177,7 +183,8 @@ vm_radix_node_get(vm_pindex_t index, vm_pindex_t newind)
_Static_assert(sizeof(vm_pindex_t) * NBBY <=
(1 << (sizeof(rnode->rn_clev) * NBBY)), "rn_clev too narrow");
rnode->rn_clev = rounddown(flsll(index ^ newind) - 1, VM_RADIX_WIDTH);
- rnode->rn_owner = vm_radix_trimkey(index, rnode->rn_clev);
+ rnode->rn_owner = VM_RADIX_COUNT;
+ rnode->rn_owner = index & -(rnode->rn_owner << rnode->rn_clev);
return (rnode);
}
@@ -298,24 +305,13 @@ vm_radix_addnode(struct vm_radix_node *rnode, vm_pindex_t index,
{
int slot;
- slot = vm_radix_slot(index, rnode->rn_clev);
+ slot = vm_radix_slot(rnode, index);
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));
}
-/*
- * Returns TRUE if it can be determined that key does not belong to the
- * specified rnode. Otherwise, returns FALSE.
- */
-static __inline bool
-vm_radix_keybarr(struct vm_radix_node *rnode, vm_pindex_t idx)
-{
- idx = vm_radix_trimkey(idx, rnode->rn_clev);
- return (idx != rnode->rn_owner);
-}
-
/*
* Internal helper for vm_radix_reclaim_allnodes().
* This function is recursive.
@@ -432,11 +428,10 @@ vm_radix_insert(struct vm_radix *rtree, vm_page_t page)
__func__, (uintmax_t)index);
break;
}
- if (vm_radix_keybarr(rnode, index)) {
+ if (vm_radix_keybarr(rnode, index, &slot)) {
newind = rnode->rn_owner;
break;
}
- slot = vm_radix_slot(index, rnode->rn_clev);
parent = rnode;
rnode = vm_radix_node_load(&rnode->rn_child[slot], LOCKED);
}
@@ -479,9 +474,8 @@ _vm_radix_lookup(struct vm_radix *rtree, vm_pindex_t index,
return (m);
break;
}
- if (vm_radix_keybarr(rnode, index))
+ if (vm_radix_keybarr(rnode, index, &slot))
break;
- slot = vm_radix_slot(index, rnode->rn_clev);
rnode = vm_radix_node_load(&rnode->rn_child[slot], access);
}
return (NULL);
@@ -551,7 +545,7 @@ vm_radix_lookup_ge(struct vm_radix *rtree, vm_pindex_t index)
return (m);
break;
}
- if (vm_radix_keybarr(rnode, index)) {
+ if (vm_radix_keybarr(rnode, index, &slot)) {
/*
* If all pages in this subtree have pindex > index,
* then the page in this subtree with the least pindex
@@ -561,7 +555,6 @@ vm_radix_lookup_ge(struct vm_radix *rtree, vm_pindex_t index)
succ = rnode;
break;
}
- slot = vm_radix_slot(index, rnode->rn_clev);
/*
* Just in case the next search step leads to a subtree of all
@@ -585,7 +578,7 @@ vm_radix_lookup_ge(struct vm_radix *rtree, vm_pindex_t index)
* Take a step to the next bigger sibling of the node chosen
* last time. In that subtree, all pages have pindex > index.
*/
- slot = vm_radix_slot(index, succ->rn_clev) + 1;
+ slot = vm_radix_slot(succ, index) + 1;
KASSERT((succ->rn_popmap >> slot) != 0,
("%s: no popmap siblings past slot %d in node %p",
__func__, slot, succ));
@@ -630,12 +623,11 @@ vm_radix_lookup_le(struct vm_radix *rtree, vm_pindex_t index)
return (m);
break;
}
- if (vm_radix_keybarr(rnode, index)) {
+ if (vm_radix_keybarr(rnode, index, &slot)) {
if (rnode->rn_owner < index)
pred = rnode;
break;
}
- slot = vm_radix_slot(index, rnode->rn_clev);
if ((rnode->rn_popmap & ((1 << slot) - 1)) != 0)
pred = rnode;
rnode = vm_radix_node_load(&rnode->rn_child[slot], LOCKED);
@@ -643,7 +635,7 @@ vm_radix_lookup_le(struct vm_radix *rtree, vm_pindex_t index)
if (pred == NULL)
return (NULL);
if (pred != rnode) {
- slot = vm_radix_slot(index, pred->rn_clev);
+ slot = vm_radix_slot(pred, index);
KASSERT((pred->rn_popmap & ((1 << slot) - 1)) != 0,
("%s: no popmap siblings before slot %d in node %p",
__func__, slot, pred));
@@ -677,7 +669,7 @@ vm_radix_remove(struct vm_radix *rtree, vm_pindex_t index)
break;
parent = rnode;
rnode = child;
- slot = vm_radix_slot(index, rnode->rn_clev);
+ slot = vm_radix_slot(rnode, index);
child = vm_radix_node_load(&rnode->rn_child[slot], LOCKED);
}
if ((m = vm_radix_topage(child)) == NULL || m->pindex != index)
@@ -700,7 +692,7 @@ vm_radix_remove(struct vm_radix *rtree, vm_pindex_t index)
if (parent == NULL)
vm_radix_root_store(rtree, child, LOCKED);
else {
- slot = vm_radix_slot(index, parent->rn_clev);
+ slot = vm_radix_slot(parent, index);
KASSERT(rnode ==
vm_radix_node_load(&parent->rn_child[slot], LOCKED),
("%s: invalid child value", __func__));
@@ -762,9 +754,8 @@ vm_radix_replace(struct vm_radix *rtree, vm_page_t newpage)
}
break;
}
- if (vm_radix_keybarr(rnode, index))
+ if (vm_radix_keybarr(rnode, index, &slot))
break;
- slot = vm_radix_slot(index, rnode->rn_clev);
parent = rnode;
rnode = vm_radix_node_load(&rnode->rn_child[slot], LOCKED);
}