Page MenuHomeFreeBSD
Files F162716543

D40936.id124419.diff
No OneTemporary
Actions

D40936.id124419.diff
View Options

Index: sys/kern/subr_pctrie.c
===================================================================
--- sys/kern/subr_pctrie.c
+++ sys/kern/subr_pctrie.c
@@ -472,211 +472,102 @@
}
/*
- * Look up the nearest entry at a position bigger than or equal to index,
+ * Returns the least value stored at a position greater than or equal to index
* assuming access is externally synchronized by a lock.
*/
uint64_t *
pctrie_lookup_ge(struct pctrie *ptree, uint64_t index)
{
- struct pctrie_node *stack[PCTRIE_LIMIT];
+ struct pctrie_node *nbr, *node;
uint64_t *m;
- struct pctrie_node *child, *node;
-#ifdef INVARIANTS
- int loops = 0;
-#endif
- unsigned tos;
int slot;
node = pctrie_root_load(ptree, NULL, PCTRIE_LOCKED);
- if (node == NULL)
- return (NULL);
- else if (pctrie_isleaf(node)) {
- m = pctrie_toval(node);
- if (*m >= index)
- return (m);
- else
- return (NULL);
- }
- tos = 0;
- for (;;) {
- /*
- * If the keys differ before the current bisection node,
- * then the search key might rollback to the earliest
- * available bisection node or to the smallest key
- * in the current node (if the owner is greater than the
- * search key).
- */
+ nbr = NULL;
+ while (node != NULL) {
+ if (pctrie_isleaf(node)) {
+ m = pctrie_toval(node);
+ if (*m >= index)
+ return (m);
+ break;
+ }
if (pctrie_keybarr(node, index)) {
- if (index > node->pn_owner) {
-ascend:
- KASSERT(++loops < 1000,
- ("pctrie_lookup_ge: too many loops"));
-
- /*
- * Pop nodes from the stack until either the
- * stack is empty or a node that could have a
- * matching descendant is found.
- */
- do {
- if (tos == 0)
- return (NULL);
- node = stack[--tos];
- } while (pctrie_slot(index,
- node->pn_clev) == (PCTRIE_COUNT - 1));
-
- /*
- * The following computation cannot overflow
- * because index's slot at the current level
- * is less than PCTRIE_COUNT - 1.
- */
- index = pctrie_trimkey(index,
- node->pn_clev);
- index += PCTRIE_UNITLEVEL(node->pn_clev);
- } else
- index = node->pn_owner;
- KASSERT(!pctrie_keybarr(node, index),
- ("pctrie_lookup_ge: keybarr failed"));
+ if (node->pn_owner >= index)
+ nbr = node;
+ break;
}
slot = pctrie_slot(index, node->pn_clev);
- child = pctrie_node_load(&node->pn_child[slot], NULL,
+ /* Save, if there are bits beyond the first slot + 1 bits. */
+ if (node->pn_popmap >> slot >> 1 != 0)
+ nbr = node;
+ node = pctrie_node_load(&node->pn_child[slot], NULL,
+ PCTRIE_LOCKED);
+ }
+ if (nbr == NULL)
+ return (NULL);
+ if (nbr != node) {
+ slot = pctrie_slot(index, nbr->pn_clev) + 1;
+ /* Find the first set bit beyond the first slot bits. */
+ slot += __builtin_ctz(nbr->pn_popmap >> slot);
+ nbr = pctrie_node_load(&nbr->pn_child[slot], NULL,
+ PCTRIE_LOCKED);
+ }
+ while (!pctrie_isleaf(nbr)) {
+ slot = __builtin_ctz(nbr->pn_popmap);
+ nbr = pctrie_node_load(&nbr->pn_child[slot], NULL,
PCTRIE_LOCKED);
- if (pctrie_isleaf(child)) {
- m = pctrie_toval(child);
- if (*m >= index)
- return (m);
- } else if (child != NULL)
- goto descend;
-
- /* Find the first set bit beyond the first slot+1 bits. */
- slot = ffs(node->pn_popmap & (-2 << slot)) - 1;
- if (slot < 0) {
- /*
- * A value or edge greater than the search slot is not
- * found in the current node; ascend to the next
- * higher-level node.
- */
- goto ascend;
- }
- child = pctrie_node_load(&node->pn_child[slot],
- NULL, PCTRIE_LOCKED);
- KASSERT(child != NULL, ("%s: bad popmap slot %d in node %p",
- __func__, slot, node));
- if (pctrie_isleaf(child))
- return (pctrie_toval(child));
- index = pctrie_trimkey(index, node->pn_clev + 1) +
- slot * PCTRIE_UNITLEVEL(node->pn_clev);
-descend:
- KASSERT(node->pn_clev > 0,
- ("pctrie_lookup_ge: pushing leaf's parent"));
- KASSERT(tos < PCTRIE_LIMIT,
- ("pctrie_lookup_ge: stack overflow"));
- stack[tos++] = node;
- node = child;
}
+ return (pctrie_toval(nbr));
}
/*
- * Look up the nearest entry at a position less than or equal to index,
+ * Returns the greatest value stored at a position less than or equal to index
* assuming access is externally synchronized by a lock.
*/
uint64_t *
pctrie_lookup_le(struct pctrie *ptree, uint64_t index)
{
- struct pctrie_node *stack[PCTRIE_LIMIT];
+ struct pctrie_node *nbr, *node;
uint64_t *m;
- struct pctrie_node *child, *node;
-#ifdef INVARIANTS
- int loops = 0;
-#endif
- unsigned tos;
int slot;
node = pctrie_root_load(ptree, NULL, PCTRIE_LOCKED);
- if (node == NULL)
- return (NULL);
- else if (pctrie_isleaf(node)) {
- m = pctrie_toval(node);
- if (*m <= index)
- return (m);
- else
- return (NULL);
- }
- tos = 0;
- for (;;) {
- /*
- * If the keys differ before the current bisection node,
- * then the search key might rollback to the earliest
- * available bisection node or to the largest key
- * in the current node (if the owner is smaller than the
- * search key).
- */
+ nbr = NULL;
+ while (node != NULL) {
+ if (pctrie_isleaf(node)) {
+ m = pctrie_toval(node);
+ if (*m <= index)
+ return (m);
+ break;
+ }
if (pctrie_keybarr(node, index)) {
- if (index > node->pn_owner) {
- index = node->pn_owner + PCTRIE_COUNT *
- PCTRIE_UNITLEVEL(node->pn_clev);
- } else {
-ascend:
- KASSERT(++loops < 1000,
- ("pctrie_lookup_le: too many loops"));
-
- /*
- * Pop nodes from the stack until either the
- * stack is empty or a node that could have a
- * matching descendant is found.
- */
- do {
- if (tos == 0)
- return (NULL);
- node = stack[--tos];
- } while (pctrie_slot(index,
- node->pn_clev) == 0);
-
- /*
- * The following computation cannot overflow
- * because index's slot at the current level
- * is greater than 0.
- */
- index = pctrie_trimkey(index,
- node->pn_clev);
- }
- index--;
- KASSERT(!pctrie_keybarr(node, index),
- ("pctrie_lookup_le: keybarr failed"));
+ if (node->pn_owner <= index)
+ nbr = node;
+ break;
}
slot = pctrie_slot(index, node->pn_clev);
- child = pctrie_node_load(&node->pn_child[slot], NULL,
+ /* Save, if there are bits among the first slot bits. */
+ if ((node->pn_popmap & ((1 << slot) - 1)) != 0)
+ nbr = node;
+ node = pctrie_node_load(&node->pn_child[slot], NULL,
PCTRIE_LOCKED);
- if (pctrie_isleaf(child)) {
- m = pctrie_toval(child);
- if (*m <= index)
- return (m);
- } else if (child != NULL)
- goto descend;
-
+ }
+ if (nbr == NULL)
+ return (NULL);
+ if (nbr != node) {
+ slot = pctrie_slot(index, nbr->pn_clev);
/* Find the last set bit among the first slot bits. */
- slot = fls(node->pn_popmap & ((1 << slot) - 1)) - 1;
- if (slot < 0) {
- /*
- * A value or edge smaller than the search slot is not
- * found in the current node; ascend to the next
- * higher-level node.
- */
- goto ascend;
- }
- child = pctrie_node_load(&node->pn_child[slot],
- NULL, PCTRIE_LOCKED);
- if (pctrie_isleaf(child))
- return (pctrie_toval(child));
- index = pctrie_trimkey(index, node->pn_clev + 1) +
- (slot + 1) * PCTRIE_UNITLEVEL(node->pn_clev) - 1;
-descend:
- KASSERT(node->pn_clev > 0,
- ("pctrie_lookup_le: pushing leaf's parent"));
- KASSERT(tos < PCTRIE_LIMIT,
- ("pctrie_lookup_le: stack overflow"));
- stack[tos++] = node;
- node = child;
+ slot = 8 * sizeof(int) - 1 -
+ __builtin_clz(nbr->pn_popmap & ((1 << slot) - 1));
+ nbr = pctrie_node_load(&nbr->pn_child[slot], NULL,
+ PCTRIE_LOCKED);
+ }
+ while (!pctrie_isleaf(nbr)) {
+ slot = 8 * sizeof(int) - 1 - __builtin_clz(nbr->pn_popmap);
+ nbr = pctrie_node_load(&nbr->pn_child[slot], NULL,
+ PCTRIE_LOCKED);
}
+ return (pctrie_toval(nbr));
}
/*
Index: sys/vm/vm_radix.c
===================================================================
--- sys/vm/vm_radix.c
+++ sys/vm/vm_radix.c
@@ -513,205 +513,100 @@
}
/*
- * Look up the nearest entry at a position greater than or equal to index.
+ * Returns the least value stored at a position greater than or equal to index
+ * assuming access is externally synchronized by a lock.
+ *
+ * Returns NULL if the all positions are less than index.
*/
vm_page_t
vm_radix_lookup_ge(struct vm_radix *rtree, vm_pindex_t index)
{
- struct vm_radix_node *stack[VM_RADIX_LIMIT];
+ struct vm_radix_node *nbr, *rnode;
vm_page_t m;
- struct vm_radix_node *child, *rnode;
-#ifdef INVARIANTS
- int loops = 0;
-#endif
- int slot, tos;
+ int slot;
rnode = vm_radix_root_load(rtree, LOCKED);
- if (rnode == NULL)
- return (NULL);
- else if (vm_radix_isleaf(rnode)) {
- m = vm_radix_topage(rnode);
- if (m->pindex >= index)
- return (m);
- else
- return (NULL);
- }
- tos = 0;
- for (;;) {
- /*
- * If the keys differ before the current bisection node,
- * then the search key might rollback to the earliest
- * available bisection node or to the smallest key
- * in the current node (if the owner is greater than the
- * search key).
- */
- if (vm_radix_keybarr(rnode, index)) {
- if (index > rnode->rn_owner) {
-ascend:
- KASSERT(++loops < 1000,
- ("vm_radix_lookup_ge: too many loops"));
-
- /*
- * Pop nodes from the stack until either the
- * stack is empty or a node that could have a
- * matching descendant is found.
- */
- do {
- if (tos == 0)
- return (NULL);
- rnode = stack[--tos];
- } while (vm_radix_slot(index,
- rnode->rn_clev) == (VM_RADIX_COUNT - 1));
-
- /*
- * The following computation cannot overflow
- * because index's slot at the current level
- * is less than VM_RADIX_COUNT - 1.
- */
- index = vm_radix_trimkey(index,
- rnode->rn_clev);
- index += VM_RADIX_UNITLEVEL(rnode->rn_clev);
- } else
- index = rnode->rn_owner;
- KASSERT(!vm_radix_keybarr(rnode, index),
- ("vm_radix_lookup_ge: keybarr failed"));
- }
- slot = vm_radix_slot(index, rnode->rn_clev);
- child = vm_radix_node_load(&rnode->rn_child[slot], LOCKED);
- if (vm_radix_isleaf(child)) {
- m = vm_radix_topage(child);
+ nbr = NULL;
+ while (rnode != NULL) {
+ if (vm_radix_isleaf(rnode)) {
+ m = vm_radix_topage(rnode);
if (m->pindex >= index)
return (m);
- } else if (child != NULL)
- goto descend;
-
- /* Find the first set bit beyond the first slot+1 bits. */
- slot = ffs(rnode->rn_popmap & (-2 << slot)) - 1;
- if (slot < 0) {
- /*
- * A page or edge greater than the search slot is not
- * found in the current node; ascend to the next
- * higher-level node.
- */
- goto ascend;
+ break;
}
- child = vm_radix_node_load(&rnode->rn_child[slot], LOCKED);
- KASSERT(child != NULL, ("%s: bad popmap slot %d in rnode %p",
- __func__, slot, rnode));
- if (vm_radix_isleaf(child))
- return (vm_radix_topage(child));
- index = vm_radix_trimkey(index, rnode->rn_clev + 1) +
- slot * VM_RADIX_UNITLEVEL(rnode->rn_clev);
-descend:
- KASSERT(rnode->rn_clev > 0,
- ("vm_radix_lookup_ge: pushing leaf's parent"));
- KASSERT(tos < VM_RADIX_LIMIT,
- ("vm_radix_lookup_ge: stack overflow"));
- stack[tos++] = rnode;
- rnode = child;
+ if (vm_radix_keybarr(rnode, index)) {
+ if (rnode->rn_owner >= index)
+ nbr = rnode;
+ break;
+ }
+ slot = vm_radix_slot(index, rnode->rn_clev);
+ /* Save, if there are bits beyond the first slot + 1 bits. */
+ if (rnode->rn_popmap >> slot >> 1 != 0)
+ nbr = rnode;
+ rnode = vm_radix_node_load(&rnode->rn_child[slot], LOCKED);
}
+ if (nbr == NULL)
+ return (NULL);
+ if (nbr != rnode) {
+ slot = vm_radix_slot(index, nbr->rn_clev) + 1;
+ /* Find the first set bit beyond the first slot bits. */
+ slot += __builtin_ctz(nbr->rn_popmap >> slot);
+ nbr = vm_radix_node_load(&nbr->rn_child[slot], LOCKED);
+ }
+ while (!vm_radix_isleaf(nbr)) {
+ slot = __builtin_ctz(nbr->rn_popmap);
+ nbr = vm_radix_node_load(&nbr->rn_child[slot], LOCKED);
+ }
+ return (vm_radix_topage(nbr));
}
/*
- * Look up the nearest entry at a position less than or equal to index.
+ * Returns the greatest value stored at a position less than or equal to index
+ * assuming access is externally synchronized by a lock.
+ *
+ * Returns NULL if the all positions are more than index.
*/
vm_page_t
vm_radix_lookup_le(struct vm_radix *rtree, vm_pindex_t index)
{
- struct vm_radix_node *stack[VM_RADIX_LIMIT];
+ struct vm_radix_node *nbr, *rnode;
vm_page_t m;
- struct vm_radix_node *child, *rnode;
-#ifdef INVARIANTS
- int loops = 0;
-#endif
- int slot, tos;
+ int slot;
rnode = vm_radix_root_load(rtree, LOCKED);
- if (rnode == NULL)
- return (NULL);
- else if (vm_radix_isleaf(rnode)) {
- m = vm_radix_topage(rnode);
- if (m->pindex <= index)
- return (m);
- else
- return (NULL);
- }
- tos = 0;
- for (;;) {
- /*
- * If the keys differ before the current bisection node,
- * then the search key might rollback to the earliest
- * available bisection node or to the largest key
- * in the current node (if the owner is smaller than the
- * search key).
- */
+ nbr = NULL;
+ while (rnode != NULL) {
+ if (vm_radix_isleaf(rnode)) {
+ m = vm_radix_topage(rnode);
+ if (m->pindex <= index)
+ return (m);
+ break;
+ }
if (vm_radix_keybarr(rnode, index)) {
- if (index > rnode->rn_owner) {
- index = rnode->rn_owner + VM_RADIX_COUNT *
- VM_RADIX_UNITLEVEL(rnode->rn_clev);
- } else {
-ascend:
- KASSERT(++loops < 1000,
- ("vm_radix_lookup_le: too many loops"));
-
- /*
- * Pop nodes from the stack until either the
- * stack is empty or a node that could have a
- * matching descendant is found.
- */
- do {
- if (tos == 0)
- return (NULL);
- rnode = stack[--tos];
- } while (vm_radix_slot(index,
- rnode->rn_clev) == 0);
-
- /*
- * The following computation cannot overflow
- * because index's slot at the current level
- * is greater than 0.
- */
- index = vm_radix_trimkey(index,
- rnode->rn_clev);
- }
- index--;
- KASSERT(!vm_radix_keybarr(rnode, index),
- ("vm_radix_lookup_le: keybarr failed"));
+ if (rnode->rn_owner <= index)
+ nbr = rnode;
+ break;
}
slot = vm_radix_slot(index, rnode->rn_clev);
- child = vm_radix_node_load(&rnode->rn_child[slot], LOCKED);
- if (vm_radix_isleaf(child)) {
- m = vm_radix_topage(child);
- if (m->pindex <= index)
- return (m);
- } else if (child != NULL)
- goto descend;
-
+ /* Save, if there are bits among the first slot bits. */
+ if ((rnode->rn_popmap & ((1 << slot) - 1)) != 0)
+ nbr = rnode;
+ rnode = vm_radix_node_load(&rnode->rn_child[slot], LOCKED);
+ }
+ if (nbr == NULL)
+ return (NULL);
+ if (nbr != rnode) {
+ slot = vm_radix_slot(index, nbr->rn_clev);
/* Find the last set bit among the first slot bits. */
- slot = fls(rnode->rn_popmap & ((1 << slot) - 1)) - 1;
- if (slot < 0) {
- /*
- * A page or edge smaller than the search slot is not
- * found in the current node; ascend to the next
- * higher-level node.
- */
- goto ascend;
- }
- child = vm_radix_node_load(&rnode->rn_child[slot], LOCKED);
- KASSERT(child != NULL, ("%s: bad popmap slot %d in rnode %p",
- __func__, slot, rnode));
- if (vm_radix_isleaf(child))
- return (vm_radix_topage(child));
- index = vm_radix_trimkey(index, rnode->rn_clev + 1) +
- (slot + 1) * VM_RADIX_UNITLEVEL(rnode->rn_clev) - 1;
-descend:
- KASSERT(rnode->rn_clev > 0,
- ("vm_radix_lookup_le: pushing leaf's parent"));
- KASSERT(tos < VM_RADIX_LIMIT,
- ("vm_radix_lookup_le: stack overflow"));
- stack[tos++] = rnode;
- rnode = child;
+ slot = 8 * sizeof(int) - 1 -
+ __builtin_clz(nbr->rn_popmap & ((1 << slot) - 1));
+ nbr = vm_radix_node_load(&nbr->rn_child[slot], LOCKED);
+ }
+ while (!vm_radix_isleaf(nbr)) {
+ slot = 8 * sizeof(int) - 1 - __builtin_clz(nbr->rn_popmap);
+ nbr = vm_radix_node_load(&nbr->rn_child[slot], LOCKED);
}
+ return (vm_radix_topage(nbr));
}
/*

File Metadata

Mime Type
text/plain
Expires
Fri, Jul 17, 2:41 AM (13 h, 36 m)
Storage Engine
blob
Storage Format
Raw Data
Storage Handle
35155888
Default Alt Text
D40936.id124419.diff (15 KB)

Event Timeline