svn commit: r226920 - in user/attilio/vmcontention/sys/amd64: amd64
include
Attilio Rao
attilio at FreeBSD.org
Sun Oct 30 00:57:56 UTC 2011
Author: attilio
Date: Sun Oct 30 00:57:56 2011
New Revision: 226920
URL: http://svn.freebsd.org/changeset/base/226920
Log:
Reimplement the splay tree used for idle page table pages using
md_page iterators. Additively, embed the left and right pointers as an
union with the pv_list as the page table pages don't need reverse
mapping. This way, this code is no longer using the root and left
iterators from the vm_page itself and once the red/black algorithm for
cached pages will be implemented will allow removing completely the
extra two pointers from vm_page.
Implementation notes: it is interesting to note that now
pmap_vmpage_splay() is just a copy&paste of the vm_page_splay(),
but working on the md_page iterators. This is necessary because in the
end the vm_page_splay() will be completely removed.
Also, note that pv_list iterator is renamed in a more "common" way
because of problems with macro expansions.
Outlined, discussed and reviewed by: jeff
Modified:
user/attilio/vmcontention/sys/amd64/amd64/pmap.c
user/attilio/vmcontention/sys/amd64/include/pmap.h
Modified: user/attilio/vmcontention/sys/amd64/amd64/pmap.c
==============================================================================
--- user/attilio/vmcontention/sys/amd64/amd64/pmap.c Sat Oct 29 23:53:58 2011 (r226919)
+++ user/attilio/vmcontention/sys/amd64/amd64/pmap.c Sun Oct 30 00:57:56 2011 (r226920)
@@ -265,6 +265,7 @@ static boolean_t pmap_try_insert_pv_entr
static void pmap_update_pde(pmap_t pmap, vm_offset_t va, pd_entry_t *pde,
pd_entry_t newpde);
static void pmap_update_pde_invalidate(vm_offset_t va, pd_entry_t newpde);
+static vm_page_t pmap_vmpage_splay(vm_pindex_t pindex, vm_page_t root);
static vm_page_t pmap_allocpde(pmap_t pmap, vm_offset_t va, int flags);
static vm_page_t pmap_allocpte(pmap_t pmap, vm_offset_t va, int flags);
@@ -1461,20 +1462,20 @@ pmap_insert_pt_page(pmap_t pmap, vm_page
PMAP_LOCK_ASSERT(pmap, MA_OWNED);
root = pmap->pm_root;
if (root == NULL) {
- mpte->left = NULL;
- mpte->right = NULL;
+ mpte->md.pv_left = NULL;
+ mpte->md.pv_right = NULL;
} else {
- root = vm_page_splay(mpte->pindex, root);
+ root = pmap_vmpage_splay(mpte->pindex, root);
if (mpte->pindex < root->pindex) {
- mpte->left = root->left;
- mpte->right = root;
- root->left = NULL;
+ mpte->md.pv_left = root->md.pv_left;
+ mpte->md.pv_right = root;
+ root->md.pv_left = NULL;
} else if (mpte->pindex == root->pindex)
panic("pmap_insert_pt_page: pindex already inserted");
else {
- mpte->right = root->right;
- mpte->left = root;
- root->right = NULL;
+ mpte->md.pv_right = root->md.pv_right;
+ mpte->md.pv_left = root;
+ root->md.pv_right = NULL;
}
}
pmap->pm_root = mpte;
@@ -1493,7 +1494,7 @@ pmap_lookup_pt_page(pmap_t pmap, vm_offs
PMAP_LOCK_ASSERT(pmap, MA_OWNED);
if ((mpte = pmap->pm_root) != NULL && mpte->pindex != pindex) {
- mpte = vm_page_splay(pindex, mpte);
+ mpte = pmap_vmpage_splay(pindex, mpte);
if ((pmap->pm_root = mpte)->pindex != pindex)
mpte = NULL;
}
@@ -1512,18 +1513,24 @@ pmap_remove_pt_page(pmap_t pmap, vm_page
PMAP_LOCK_ASSERT(pmap, MA_OWNED);
if (mpte != pmap->pm_root) {
- root = vm_page_splay(mpte->pindex, pmap->pm_root);
+ root = pmap_vmpage_splay(mpte->pindex, pmap->pm_root);
KASSERT(mpte == root,
("pmap_remove_pt_page: mpte %p is missing from pmap %p",
mpte, pmap));
}
- if (mpte->left == NULL)
- root = mpte->right;
+ if (mpte->md.pv_left == NULL)
+ root = mpte->md.pv_right;
else {
- root = vm_page_splay(mpte->pindex, mpte->left);
- root->right = mpte->right;
+ root = pmap_vmpage_splay(mpte->pindex, mpte->md.pv_left);
+ root->md.pv_right = mpte->md.pv_right;
}
pmap->pm_root = root;
+
+ /*
+ * Reinitialize the pv_list which could be dirty now because of the
+ * splay tree work.
+ */
+ TAILQ_INIT(&mpte->md.pv_list);
}
/*
@@ -1599,6 +1606,61 @@ _pmap_unwire_pte_hold(pmap_t pmap, vm_of
}
/*
+ * Implements Sleator and Tarjan's top-down splay algorithm. Returns
+ * the vm_page containing the given pindex. If, however, that
+ * pindex is not found in the pmap, returns a vm_page that is
+ * adjacent to the pindex, coming before or after it.
+ */
+static vm_page_t
+pmap_vmpage_splay(vm_pindex_t pindex, vm_page_t root)
+{
+ struct vm_page dummy;
+ vm_page_t lefttreemax, righttreemin, y;
+
+ if (root == NULL)
+ return (root);
+ lefttreemax = righttreemin = &dummy;
+ for (;; root = y) {
+ if (pindex < root->pindex) {
+ if ((y = root->md.pv_left) == NULL)
+ break;
+ if (pindex < y->pindex) {
+ /* Rotate right. */
+ root->md.pv_left = y->md.pv_right;
+ y->md.pv_right = root;
+ root = y;
+ if ((y = root->md.pv_left) == NULL)
+ break;
+ }
+ /* Link into the new root's right tree. */
+ righttreemin->md.pv_left = root;
+ righttreemin = root;
+ } else if (pindex > root->pindex) {
+ if ((y = root->md.pv_right) == NULL)
+ break;
+ if (pindex > y->pindex) {
+ /* Rotate left. */
+ root->md.pv_right = y->md.pv_left;
+ y->md.pv_left = root;
+ root = y;
+ if ((y = root->md.pv_right) == NULL)
+ break;
+ }
+ /* Link into the new root's left tree. */
+ lefttreemax->md.pv_right = root;
+ lefttreemax = root;
+ } else
+ break;
+ }
+ /* Assemble the new root. */
+ lefttreemax->md.pv_right = root->md.pv_left;
+ righttreemin->md.pv_left = root->md.pv_right;
+ root->md.pv_left = dummy.md.pv_right;
+ root->md.pv_right = dummy.md.pv_left;
+ return (root);
+}
+
+/*
* After removing a page table entry, this routine is used to
* conditionally free the page, and manage the hold/wire counts.
*/
@@ -2105,7 +2167,7 @@ pmap_collect(pmap_t locked_pmap, struct
TAILQ_FOREACH(m, &vpq->pl, pageq) {
if ((m->flags & PG_MARKER) != 0 || m->hold_count || m->busy)
continue;
- TAILQ_FOREACH_SAFE(pv, &m->md.pv_list, pv_list, next_pv) {
+ TAILQ_FOREACH_SAFE(pv, &m->md.pv_list, pv_next, next_pv) {
va = pv->pv_va;
pmap = PV_PMAP(pv);
/* Avoid deadlock and lock recursion. */
@@ -2129,7 +2191,7 @@ pmap_collect(pmap_t locked_pmap, struct
pmap_unuse_pt(pmap, va, *pde, &free);
pmap_invalidate_page(pmap, va);
pmap_free_zero_pages(free);
- TAILQ_REMOVE(&m->md.pv_list, pv, pv_list);
+ TAILQ_REMOVE(&m->md.pv_list, pv, pv_next);
free_pv_entry(pmap, pv);
if (pmap != locked_pmap)
PMAP_UNLOCK(pmap);
@@ -2277,9 +2339,9 @@ pmap_pvh_remove(struct md_page *pvh, pma
pv_entry_t pv;
mtx_assert(&vm_page_queue_mtx, MA_OWNED);
- TAILQ_FOREACH(pv, &pvh->pv_list, pv_list) {
+ TAILQ_FOREACH(pv, &pvh->pv_list, pv_next) {
if (pmap == PV_PMAP(pv) && va == pv->pv_va) {
- TAILQ_REMOVE(&pvh->pv_list, pv, pv_list);
+ TAILQ_REMOVE(&pvh->pv_list, pv, pv_next);
break;
}
}
@@ -2312,7 +2374,7 @@ pmap_pv_demote_pde(pmap_t pmap, vm_offse
pv = pmap_pvh_remove(pvh, pmap, va);
KASSERT(pv != NULL, ("pmap_pv_demote_pde: pv not found"));
m = PHYS_TO_VM_PAGE(pa);
- TAILQ_INSERT_TAIL(&m->md.pv_list, pv, pv_list);
+ TAILQ_INSERT_TAIL(&m->md.pv_list, pv, pv_next);
/* Instantiate the remaining NPTEPG - 1 pv entries. */
va_last = va + NBPDR - PAGE_SIZE;
do {
@@ -2353,7 +2415,7 @@ pmap_pv_promote_pde(pmap_t pmap, vm_offs
pv = pmap_pvh_remove(&m->md, pmap, va);
KASSERT(pv != NULL, ("pmap_pv_promote_pde: pv not found"));
pvh = pa_to_pvh(pa);
- TAILQ_INSERT_TAIL(&pvh->pv_list, pv, pv_list);
+ TAILQ_INSERT_TAIL(&pvh->pv_list, pv, pv_next);
/* Free the remaining NPTEPG - 1 pv entries. */
va_last = va + NBPDR - PAGE_SIZE;
do {
@@ -2405,7 +2467,7 @@ pmap_insert_entry(pmap_t pmap, vm_offset
mtx_assert(&vm_page_queue_mtx, MA_OWNED);
pv = get_pv_entry(pmap, FALSE);
pv->pv_va = va;
- TAILQ_INSERT_TAIL(&m->md.pv_list, pv, pv_list);
+ TAILQ_INSERT_TAIL(&m->md.pv_list, pv, pv_next);
}
/*
@@ -2421,7 +2483,7 @@ pmap_try_insert_pv_entry(pmap_t pmap, vm
if (pv_entry_count < pv_entry_high_water &&
(pv = get_pv_entry(pmap, TRUE)) != NULL) {
pv->pv_va = va;
- TAILQ_INSERT_TAIL(&m->md.pv_list, pv, pv_list);
+ TAILQ_INSERT_TAIL(&m->md.pv_list, pv, pv_next);
return (TRUE);
} else
return (FALSE);
@@ -2441,7 +2503,7 @@ pmap_pv_insert_pde(pmap_t pmap, vm_offse
(pv = get_pv_entry(pmap, TRUE)) != NULL) {
pv->pv_va = va;
pvh = pa_to_pvh(pa);
- TAILQ_INSERT_TAIL(&pvh->pv_list, pv, pv_list);
+ TAILQ_INSERT_TAIL(&pvh->pv_list, pv, pv_next);
return (TRUE);
} else
return (FALSE);
@@ -2878,7 +2940,7 @@ pmap_remove_all(vm_page_t m)
vm_page_dirty(m);
pmap_unuse_pt(pmap, pv->pv_va, *pde, &free);
pmap_invalidate_page(pmap, pv->pv_va);
- TAILQ_REMOVE(&m->md.pv_list, pv, pv_list);
+ TAILQ_REMOVE(&m->md.pv_list, pv, pv_next);
free_pv_entry(pmap, pv);
PMAP_UNLOCK(pmap);
}
@@ -3279,7 +3341,7 @@ pmap_enter(pmap_t pmap, vm_offset_t va,
if (pv == NULL)
pv = get_pv_entry(pmap, FALSE);
pv->pv_va = va;
- TAILQ_INSERT_TAIL(&m->md.pv_list, pv, pv_list);
+ TAILQ_INSERT_TAIL(&m->md.pv_list, pv, pv_next);
pa |= PG_MANAGED;
} else if (pv != NULL)
free_pv_entry(pmap, pv);
@@ -3959,7 +4021,7 @@ pmap_page_exists_quick(pmap_t pmap, vm_p
("pmap_page_exists_quick: page %p is not managed", m));
rv = FALSE;
vm_page_lock_queues();
- TAILQ_FOREACH(pv, &m->md.pv_list, pv_list) {
+ TAILQ_FOREACH(pv, &m->md.pv_list, pv_next) {
if (PV_PMAP(pv) == pmap) {
rv = TRUE;
break;
@@ -3970,7 +4032,7 @@ pmap_page_exists_quick(pmap_t pmap, vm_p
}
if (!rv && loops < 16) {
pvh = pa_to_pvh(VM_PAGE_TO_PHYS(m));
- TAILQ_FOREACH(pv, &pvh->pv_list, pv_list) {
+ TAILQ_FOREACH(pv, &pvh->pv_list, pv_next) {
if (PV_PMAP(pv) == pmap) {
rv = TRUE;
break;
@@ -4018,7 +4080,7 @@ pmap_pvh_wired_mappings(struct md_page *
pv_entry_t pv;
mtx_assert(&vm_page_queue_mtx, MA_OWNED);
- TAILQ_FOREACH(pv, &pvh->pv_list, pv_list) {
+ TAILQ_FOREACH(pv, &pvh->pv_list, pv_next) {
pmap = PV_PMAP(pv);
PMAP_LOCK(pmap);
pte = pmap_pte(pmap, pv->pv_va);
@@ -4140,7 +4202,7 @@ pmap_remove_pages(pmap_t pmap)
if ((tpte & PG_PS) != 0) {
pmap_resident_count_dec(pmap, NBPDR / PAGE_SIZE);
pvh = pa_to_pvh(tpte & PG_PS_FRAME);
- TAILQ_REMOVE(&pvh->pv_list, pv, pv_list);
+ TAILQ_REMOVE(&pvh->pv_list, pv, pv_next);
if (TAILQ_EMPTY(&pvh->pv_list)) {
for (mt = m; mt < &m[NBPDR / PAGE_SIZE]; mt++)
if (TAILQ_EMPTY(&mt->md.pv_list))
@@ -4158,7 +4220,7 @@ pmap_remove_pages(pmap_t pmap)
}
} else {
pmap_resident_count_dec(pmap, 1);
- TAILQ_REMOVE(&m->md.pv_list, pv, pv_list);
+ TAILQ_REMOVE(&m->md.pv_list, pv, pv_next);
if (TAILQ_EMPTY(&m->md.pv_list)) {
pvh = pa_to_pvh(VM_PAGE_TO_PHYS(m));
if (TAILQ_EMPTY(&pvh->pv_list))
@@ -4230,7 +4292,7 @@ pmap_is_modified_pvh(struct md_page *pvh
mtx_assert(&vm_page_queue_mtx, MA_OWNED);
rv = FALSE;
- TAILQ_FOREACH(pv, &pvh->pv_list, pv_list) {
+ TAILQ_FOREACH(pv, &pvh->pv_list, pv_next) {
pmap = PV_PMAP(pv);
PMAP_LOCK(pmap);
pte = pmap_pte(pmap, pv->pv_va);
@@ -4300,7 +4362,7 @@ pmap_is_referenced_pvh(struct md_page *p
mtx_assert(&vm_page_queue_mtx, MA_OWNED);
rv = FALSE;
- TAILQ_FOREACH(pv, &pvh->pv_list, pv_list) {
+ TAILQ_FOREACH(pv, &pvh->pv_list, pv_next) {
pmap = PV_PMAP(pv);
PMAP_LOCK(pmap);
pte = pmap_pte(pmap, pv->pv_va);
@@ -4339,7 +4401,7 @@ pmap_remove_write(vm_page_t m)
return;
vm_page_lock_queues();
pvh = pa_to_pvh(VM_PAGE_TO_PHYS(m));
- TAILQ_FOREACH_SAFE(pv, &pvh->pv_list, pv_list, next_pv) {
+ TAILQ_FOREACH_SAFE(pv, &pvh->pv_list, pv_next, next_pv) {
pmap = PV_PMAP(pv);
PMAP_LOCK(pmap);
va = pv->pv_va;
@@ -4348,7 +4410,7 @@ pmap_remove_write(vm_page_t m)
(void)pmap_demote_pde(pmap, pde, va);
PMAP_UNLOCK(pmap);
}
- TAILQ_FOREACH(pv, &m->md.pv_list, pv_list) {
+ TAILQ_FOREACH(pv, &m->md.pv_list, pv_next) {
pmap = PV_PMAP(pv);
PMAP_LOCK(pmap);
pde = pmap_pde(pmap, pv->pv_va);
@@ -4398,7 +4460,7 @@ pmap_ts_referenced(vm_page_t m)
("pmap_ts_referenced: page %p is not managed", m));
pvh = pa_to_pvh(VM_PAGE_TO_PHYS(m));
vm_page_lock_queues();
- TAILQ_FOREACH_SAFE(pv, &pvh->pv_list, pv_list, pvn) {
+ TAILQ_FOREACH_SAFE(pv, &pvh->pv_list, pv_next, pvn) {
pmap = PV_PMAP(pv);
PMAP_LOCK(pmap);
va = pv->pv_va;
@@ -4431,9 +4493,9 @@ pmap_ts_referenced(vm_page_t m)
if ((pv = TAILQ_FIRST(&m->md.pv_list)) != NULL) {
pvf = pv;
do {
- pvn = TAILQ_NEXT(pv, pv_list);
- TAILQ_REMOVE(&m->md.pv_list, pv, pv_list);
- TAILQ_INSERT_TAIL(&m->md.pv_list, pv, pv_list);
+ pvn = TAILQ_NEXT(pv, pv_next);
+ TAILQ_REMOVE(&m->md.pv_list, pv, pv_next);
+ TAILQ_INSERT_TAIL(&m->md.pv_list, pv, pv_next);
pmap = PV_PMAP(pv);
PMAP_LOCK(pmap);
pde = pmap_pde(pmap, pv->pv_va);
@@ -4483,7 +4545,7 @@ pmap_clear_modify(vm_page_t m)
return;
vm_page_lock_queues();
pvh = pa_to_pvh(VM_PAGE_TO_PHYS(m));
- TAILQ_FOREACH_SAFE(pv, &pvh->pv_list, pv_list, next_pv) {
+ TAILQ_FOREACH_SAFE(pv, &pvh->pv_list, pv_next, next_pv) {
pmap = PV_PMAP(pv);
PMAP_LOCK(pmap);
va = pv->pv_va;
@@ -4514,7 +4576,7 @@ pmap_clear_modify(vm_page_t m)
}
PMAP_UNLOCK(pmap);
}
- TAILQ_FOREACH(pv, &m->md.pv_list, pv_list) {
+ TAILQ_FOREACH(pv, &m->md.pv_list, pv_next) {
pmap = PV_PMAP(pv);
PMAP_LOCK(pmap);
pde = pmap_pde(pmap, pv->pv_va);
@@ -4549,7 +4611,7 @@ pmap_clear_reference(vm_page_t m)
("pmap_clear_reference: page %p is not managed", m));
vm_page_lock_queues();
pvh = pa_to_pvh(VM_PAGE_TO_PHYS(m));
- TAILQ_FOREACH_SAFE(pv, &pvh->pv_list, pv_list, next_pv) {
+ TAILQ_FOREACH_SAFE(pv, &pvh->pv_list, pv_next, next_pv) {
pmap = PV_PMAP(pv);
PMAP_LOCK(pmap);
va = pv->pv_va;
@@ -4571,7 +4633,7 @@ pmap_clear_reference(vm_page_t m)
}
PMAP_UNLOCK(pmap);
}
- TAILQ_FOREACH(pv, &m->md.pv_list, pv_list) {
+ TAILQ_FOREACH(pv, &m->md.pv_list, pv_next) {
pmap = PV_PMAP(pv);
PMAP_LOCK(pmap);
pde = pmap_pde(pmap, pv->pv_va);
Modified: user/attilio/vmcontention/sys/amd64/include/pmap.h
==============================================================================
--- user/attilio/vmcontention/sys/amd64/include/pmap.h Sat Oct 29 23:53:58 2011 (r226919)
+++ user/attilio/vmcontention/sys/amd64/include/pmap.h Sun Oct 30 00:57:56 2011 (r226920)
@@ -240,10 +240,20 @@ struct pv_entry;
struct pv_chunk;
struct md_page {
- TAILQ_HEAD(,pv_entry) pv_list;
- int pat_mode;
+ union {
+ TAILQ_HEAD(,pv_entry) pvi_list;
+ struct {
+ vm_page_t pii_left;
+ vm_page_t pii_right;
+ } pvi_siters;
+ } pv_structs;
+ int pat_mode;
};
+#define pv_list pv_structs.pvi_list
+#define pv_left pv_structs.pvi_siters.pii_left
+#define pv_right pv_structs.pvi_siters.pii_right
+
/*
* The kernel virtual address (KVA) of the level 4 page table page is always
* within the direct map (DMAP) region.
@@ -282,7 +292,7 @@ extern struct pmap kernel_pmap_store;
*/
typedef struct pv_entry {
vm_offset_t pv_va; /* virtual address for mapping */
- TAILQ_ENTRY(pv_entry) pv_list;
+ TAILQ_ENTRY(pv_entry) pv_next;
} *pv_entry_t;
/*
More information about the svn-src-user
mailing list