aboutsummaryrefslogtreecommitdiff
path: root/sys/vm/vm_radix.c
diff options
context:
space:
mode:
Diffstat (limited to 'sys/vm/vm_radix.c')
-rw-r--r--sys/vm/vm_radix.c78
1 files changed, 31 insertions, 47 deletions
diff --git a/sys/vm/vm_radix.c b/sys/vm/vm_radix.c
index 3c4ea9568108..f50f9e3605a1 100644
--- a/sys/vm/vm_radix.c
+++ b/sys/vm/vm_radix.c
@@ -107,10 +107,6 @@ _Static_assert(sizeof(rn_popmap_t) <= sizeof(int),
#define VM_RADIX_FLAGS (VM_RADIX_ISLEAF)
#define VM_RADIX_PAD VM_RADIX_FLAGS
-/* Returns one unit associated with specified level. */
-#define VM_RADIX_UNITLEVEL(lev) \
- ((vm_pindex_t)1 << ((lev) * VM_RADIX_WIDTH))
-
enum vm_radix_access { SMR, LOCKED, UNSERIALIZED };
struct vm_radix_node;
@@ -119,7 +115,7 @@ typedef SMR_POINTER(struct vm_radix_node *) smrnode_t;
struct vm_radix_node {
vm_pindex_t rn_owner; /* Owner of record. */
rn_popmap_t rn_popmap; /* Valid children. */
- uint8_t rn_clev; /* Current level. */
+ uint8_t rn_clev; /* Level * WIDTH. */
smrnode_t rn_child[VM_RADIX_COUNT]; /* Child nodes. */
};
@@ -135,21 +131,22 @@ static void vm_radix_node_store(smrnode_t *p, struct vm_radix_node *v,
static __inline int
vm_radix_slot(vm_pindex_t index, uint16_t level)
{
- return ((index >> (level * VM_RADIX_WIDTH)) & VM_RADIX_MASK);
+ return ((index >> level) & VM_RADIX_MASK);
}
-/* Computes the key (index) with the low-order 'level' radix-digits zeroed. */
+/* 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)
{
- return (index & -VM_RADIX_UNITLEVEL(level));
+ return (index & -((vm_pindex_t)VM_RADIX_COUNT << level));
}
/*
* Allocate a radix node.
*/
static struct vm_radix_node *
-vm_radix_node_get(vm_pindex_t index, uint16_t clevel)
+vm_radix_node_get(vm_pindex_t index, vm_pindex_t newind)
{
struct vm_radix_node *rnode;
@@ -167,8 +164,20 @@ vm_radix_node_get(vm_pindex_t index, uint16_t clevel)
VM_RADIX_NULL, UNSERIALIZED);
rnode->rn_popmap = 0;
}
- rnode->rn_owner = vm_radix_trimkey(index, clevel + 1);
- rnode->rn_clev = clevel;
+
+ /*
+ * From the highest-order bit where the indexes differ,
+ * compute the highest level in the trie where they differ. Then,
+ * compute the least index of this subtrie.
+ */
+ KASSERT(index != newind, ("%s: passing the same key value %jx",
+ __func__, (uintmax_t)index));
+ _Static_assert(sizeof(long long) >= sizeof(vm_pindex_t),
+ "vm_pindex_t too wide");
+ _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);
return (rnode);
}
@@ -284,12 +293,12 @@ vm_radix_topage(struct vm_radix_node *rnode)
* Make 'child' a child of 'rnode'.
*/
static __inline void
-vm_radix_addnode(struct vm_radix_node *rnode, vm_pindex_t index, uint16_t clev,
+vm_radix_addnode(struct vm_radix_node *rnode, vm_pindex_t index,
struct vm_radix_node *child, enum vm_radix_access access)
{
int slot;
- slot = vm_radix_slot(index, clev);
+ slot = vm_radix_slot(index, rnode->rn_clev);
vm_radix_node_store(&rnode->rn_child[slot], child, access);
rnode->rn_popmap ^= 1 << slot;
KASSERT((rnode->rn_popmap & (1 << slot)) != 0,
@@ -297,37 +306,14 @@ vm_radix_addnode(struct vm_radix_node *rnode, vm_pindex_t index, uint16_t clev,
}
/*
- * Returns the level where two keys differ.
- * It cannot accept 2 equal keys.
- */
-static __inline uint16_t
-vm_radix_keydiff(vm_pindex_t index1, vm_pindex_t index2)
-{
-
- KASSERT(index1 != index2, ("%s: passing the same key value %jx",
- __func__, (uintmax_t)index1));
- CTASSERT(sizeof(long long) >= sizeof(vm_pindex_t));
-
- /*
- * From the highest-order bit where the indexes differ,
- * compute the highest level in the trie where they differ.
- */
- return ((flsll(index1 ^ index2) - 1) / VM_RADIX_WIDTH);
-}
-
-/*
* 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)
{
-
- if (rnode->rn_clev < VM_RADIX_LIMIT) {
- idx = vm_radix_trimkey(idx, rnode->rn_clev + 1);
- return (idx != rnode->rn_owner);
- }
- return (false);
+ idx = vm_radix_trimkey(idx, rnode->rn_clev);
+ return (idx != rnode->rn_owner);
}
/*
@@ -420,7 +406,6 @@ vm_radix_insert(struct vm_radix *rtree, vm_page_t page)
struct vm_radix_node *leaf, *parent, *rnode;
smrnode_t *parentp;
int slot;
- uint16_t clev;
index = page->pindex;
leaf = vm_radix_toleaf(page);
@@ -437,8 +422,8 @@ vm_radix_insert(struct vm_radix *rtree, vm_page_t page)
if (parent == NULL)
rtree->rt_root = leaf;
else
- vm_radix_addnode(parent, index,
- parent->rn_clev, leaf, LOCKED);
+ vm_radix_addnode(parent, index, leaf,
+ LOCKED);
return (0);
}
newind = vm_radix_topage(rnode)->pindex;
@@ -463,13 +448,12 @@ vm_radix_insert(struct vm_radix *rtree, vm_page_t page)
*/
parentp = (parent != NULL) ? &parent->rn_child[slot]:
(smrnode_t *)&rtree->rt_root;
- clev = vm_radix_keydiff(newind, index);
- parent = vm_radix_node_get(index, clev);
+ parent = vm_radix_node_get(index, newind);
if (parent == NULL)
return (ENOMEM);
/* These writes are not yet visible due to ordering. */
- vm_radix_addnode(parent, index, clev, leaf, UNSERIALIZED);
- vm_radix_addnode(parent, newind, clev, rnode, UNSERIALIZED);
+ vm_radix_addnode(parent, index, leaf, UNSERIALIZED);
+ vm_radix_addnode(parent, newind, rnode, UNSERIALIZED);
/* Serializing write to make the above visible. */
vm_radix_node_store(parentp, parent, LOCKED);
return (0);
@@ -808,14 +792,14 @@ DB_SHOW_COMMAND(radixnode, db_show_radixnode)
rnode = (struct vm_radix_node *)addr;
db_printf("radixnode %p, owner %jx, children popmap %04x, level %u:\n",
(void *)rnode, (uintmax_t)rnode->rn_owner, rnode->rn_popmap,
- rnode->rn_clev);
+ rnode->rn_clev / VM_RADIX_WIDTH);
for (popmap = rnode->rn_popmap; popmap != 0; popmap ^= 1 << slot) {
slot = ffs(popmap) - 1;
tmp = vm_radix_node_load(&rnode->rn_child[slot], UNSERIALIZED);
db_printf("slot: %d, val: %p, page: %p, clev: %d\n",
slot, (void *)tmp,
vm_radix_isleaf(tmp) ? vm_radix_topage(tmp) : NULL,
- rnode->rn_clev);
+ rnode->rn_clev / VM_RADIX_WIDTH);
}
}
#endif /* DDB */
generated by cgit v1.2.3 (git 2.25.1) at 2024-06-30 06:43:33 +0000