Page MenuHomeFreeBSD
Files F137743028

D45627.id139946.diff
No OneTemporary
Actions

D45627.id139946.diff
View Options

Index: sys/amd64/amd64/pmap.c
===================================================================
--- sys/amd64/amd64/pmap.c
+++ sys/amd64/amd64/pmap.c
@@ -7667,6 +7667,7 @@
pmap_enter_object(pmap_t pmap, vm_offset_t start, vm_offset_t end,
vm_page_t m_start, vm_prot_t prot)
{
+ struct pctrie_iter iter;
struct rwlock *lock;
vm_offset_t va;
vm_page_t m, mpte;
@@ -7677,7 +7678,8 @@
psize = atop(end - start);
mpte = NULL;
- m = m_start;
+ m = VM_RADIX_PCTRIE_ITER_START(&iter,
+ &m_start->object->rtree.rt_trie, m_start->pindex);
lock = NULL;
PMAP_LOCK(pmap);
while (m != NULL && (diff = m->pindex - m_start->pindex) < psize) {
@@ -7686,11 +7688,12 @@
m->psind == 1 && pmap_ps_enabled(pmap) &&
((rv = pmap_enter_2mpage(pmap, va, m, prot, &lock)) ==
KERN_SUCCESS || rv == KERN_NO_SPACE))
- m = &m[NBPDR / PAGE_SIZE - 1];
- else
+ m = VM_RADIX_PCTRIE_ITER_STEP(&iter, NBPDR / PAGE_SIZE);
+ else {
mpte = pmap_enter_quick_locked(pmap, va, m, prot,
mpte, &lock);
- m = TAILQ_NEXT(m, listq);
+ m = VM_RADIX_PCTRIE_ITER_STEP(&iter, 1);
+ }
}
if (lock != NULL)
rw_wunlock(lock);
Index: sys/kern/subr_pctrie.c
===================================================================
--- sys/kern/subr_pctrie.c
+++ sys/kern/subr_pctrie.c
@@ -901,6 +901,90 @@
callback, keyoff, arg));
}
+/*
+ * Find the least leaf in the tree rooted at node and return it.
+ */
+static uint64_t *
+pctrie_iter_find_min(struct pctrie_iter *iter, struct pctrie_node *node)
+{
+ uint64_t *m;
+ int slot;
+
+ /* Descend to the least leaf of the subtrie. */
+ while (!pctrie_isleaf(node)) {
+ slot = ffs(node->pn_popmap) - 1;
+ iter->path[iter->top++] = node;
+ node = pctrie_node_load(&node->pn_child[slot], NULL,
+ PCTRIE_LOCKED);
+ }
+ m = pctrie_toval(node);
+ iter->index = *m;
+ return (m);
+}
+
+/*
+ * Find the first leaf with value at least 'step' greater than the previous
+ * leaf.
+ */
+uint64_t *
+pctrie_iter_step(struct pctrie_iter *iter, uint64_t step)
+{
+ struct pctrie_node *node;
+ uint64_t index = iter->index + step - 1;
+ int slot;
+
+ /* Climb the path to find a node with a descendant > index. */
+ do {
+ if (iter->top == 0)
+ return (NULL);
+ node = iter->path[--iter->top];
+ slot = pctrie_slot(node, index) + 1;
+ } while ((node->pn_popmap >> slot) == 0);
+
+ /* Step to the least child with a descendant > index. */
+ slot += ffs(node->pn_popmap >> slot) - 1;
+ iter->top++;
+ node = pctrie_node_load(&node->pn_child[slot], NULL, PCTRIE_LOCKED);
+ return (pctrie_iter_find_min(iter, node));
+}
+
+/*
+ * Find first leaf >= index, and initialize iter with the path to the parent of
+ * that leaf.
+ */
+uint64_t *
+pctrie_iter_start(struct pctrie_iter *iter,
+ struct pctrie *ptree, uint64_t index)
+{
+ struct pctrie_node *node;
+ uint64_t *m;
+ int slot;
+
+ iter->top = 0;
+ node = pctrie_root_load(ptree, NULL, PCTRIE_LOCKED);
+ if (index != 0) {
+ /* Seek a node that matches index. */
+ while (!pctrie_isleaf(node) &&
+ !pctrie_keybarr(node, index, &slot)) {
+ iter->path[iter->top++] = node;
+ node = pctrie_node_load(&node->pn_child[slot], NULL,
+ PCTRIE_LOCKED);
+ }
+
+ /*
+ * If no such node was found, and instead the path leads only to
+ * nodes < index, return the least value > index.
+ */
+ if (pctrie_isleaf(node) ?
+ (m = pctrie_toval(node)) == NULL || *m < index :
+ node->pn_owner < index) {
+ iter->index = index;
+ return (pctrie_iter_step(iter, 1));
+ }
+ }
+ return (pctrie_iter_find_min(iter, node));
+}
+
/*
* Replace an existing value in the trie with another one.
* Panics if there is not an old value in the trie at the new value's index.
Index: sys/sys/pctrie.h
===================================================================
--- sys/sys/pctrie.h
+++ sys/sys/pctrie.h
@@ -240,6 +240,21 @@
} \
\
static __inline __unused struct type * \
+name##_PCTRIE_ITER_STEP(struct pctrie_iter *iter, int64_t step) \
+{ \
+ return name##_PCTRIE_VAL2PTR( \
+ pctrie_iter_step(iter, step)); \
+} \
+ \
+static __inline __unused struct type * \
+name##_PCTRIE_ITER_START(struct pctrie_iter *iter, \
+ struct pctrie *ptree, int64_t index) \
+{ \
+ return name##_PCTRIE_VAL2PTR( \
+ pctrie_iter_start(iter, ptree, index)); \
+} \
+ \
+static __inline __unused struct type * \
name##_PCTRIE_REPLACE(struct pctrie *ptree, struct type *ptr) \
{ \
\
@@ -295,6 +310,10 @@
pctrie_cb_t callback, int keyoff, void *arg);
struct pctrie_node *pctrie_reclaim_resume_cb(struct pctrie_node **pnode,
pctrie_cb_t callback, int keyoff, void *arg);
+struct pctrie_iter;
+uint64_t *pctrie_iter_step(struct pctrie_iter *iter, uint64_t step);
+uint64_t *pctrie_iter_start(struct pctrie_iter *iter,
+ struct pctrie *ptree, uint64_t index);
uint64_t *pctrie_remove_lookup(struct pctrie *ptree, uint64_t index,
struct pctrie_node **killnode);
uint64_t *pctrie_replace(struct pctrie *ptree, uint64_t *newval);
@@ -343,5 +362,11 @@
#define PCTRIE_COUNT (1 << PCTRIE_WIDTH)
+struct pctrie_iter {
+ struct pctrie_node *path[sizeof(uint64_t) * NBBY / PCTRIE_WIDTH];
+ uint64_t index;
+ int top;
+};
+
#endif /* _KERNEL */
#endif /* !_SYS_PCTRIE_H_ */

File Metadata

Mime Type
text/plain
Expires
Wed, Nov 26, 9:39 AM (14 h, 1 m)
Storage Engine
blob
Storage Format
Raw Data
Storage Handle
26209109
Default Alt Text
D45627.id139946.diff (5 KB)

Event Timeline