summaryrefslogtreecommitdiffstats
path: root/sys/amd64
diff options
context:
space:
mode:
Diffstat (limited to 'sys/amd64')
-rw-r--r--sys/amd64/amd64/pmap.c151
-rw-r--r--sys/amd64/include/pmap.h16
2 files changed, 120 insertions, 47 deletions
diff --git a/sys/amd64/amd64/pmap.c b/sys/amd64/amd64/pmap.c
index c2debf7..c63d8f2 100644
--- a/sys/amd64/amd64/pmap.c
+++ b/sys/amd64/amd64/pmap.c
@@ -306,6 +306,7 @@ static boolean_t pmap_try_insert_pv_entry(pmap_t pmap, vm_offset_t va,
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_allocpte(pmap_t pmap, vm_pindex_t ptepindex,
struct rwlock **lockp);
@@ -1497,7 +1498,8 @@ pmap_free_zero_pages(vm_page_t free)
while (free != NULL) {
m = free;
- free = m->right;
+ free = (void *)m->object;
+ m->object = NULL;
/* Preserve the page's PG_ZERO setting. */
vm_page_free_toq(m);
}
@@ -1516,7 +1518,7 @@ pmap_add_delayed_free_list(vm_page_t m, vm_page_t *free, boolean_t set_PG_ZERO)
m->flags |= PG_ZERO;
else
m->flags &= ~PG_ZERO;
- m->right = *free;
+ m->object = (void *)*free;
*free = m;
}
@@ -1534,20 +1536,20 @@ pmap_insert_pt_page(pmap_t pmap, vm_page_t mpte)
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;
@@ -1566,7 +1568,7 @@ pmap_lookup_pt_page(pmap_t pmap, vm_offset_t va)
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;
}
@@ -1585,18 +1587,24 @@ pmap_remove_pt_page(pmap_t pmap, vm_page_t mpte)
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);
}
/*
@@ -1672,6 +1680,61 @@ _pmap_unwire_ptp(pmap_t pmap, vm_offset_t va, vm_page_t m, vm_page_t *free)
}
/*
+ * 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.
*/
@@ -2221,7 +2284,7 @@ reclaim_pv_chunk(pmap_t locked_pmap, struct rwlock **lockp)
if ((tpte & PG_A) != 0)
vm_page_aflag_set(m, PGA_REFERENCED);
CHANGE_PV_LIST_LOCK_TO_VM_PAGE(lockp, m);
- 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) &&
(m->flags & PG_FICTITIOUS) == 0) {
pvh = pa_to_pvh(VM_PAGE_TO_PHYS(m));
@@ -2273,7 +2336,7 @@ reclaim_pv_chunk(pmap_t locked_pmap, struct rwlock **lockp)
}
if (m_pc == NULL && free != NULL) {
m_pc = free;
- free = m_pc->right;
+ free = (void *)m_pc->object;
/* Recycle a freed page table page. */
m_pc->wire_count = 1;
atomic_add_int(&cnt.v_wire_count, 1);
@@ -2505,9 +2568,9 @@ pmap_pvh_remove(struct md_page *pvh, pmap_t pmap, vm_offset_t va)
pv_entry_t pv;
rw_assert(&pvh_global_lock, RA_LOCKED);
- 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;
}
}
@@ -2546,7 +2609,7 @@ pmap_pv_demote_pde(pmap_t pmap, vm_offset_t va, vm_paddr_t pa,
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. */
PV_STAT(atomic_add_long(&pv_entry_allocs, NPTEPG - 1));
va_last = va + NBPDR - PAGE_SIZE;
@@ -2564,7 +2627,7 @@ pmap_pv_demote_pde(pmap_t pmap, vm_offset_t va, vm_paddr_t pa,
m++;
KASSERT((m->oflags & VPO_UNMANAGED) == 0,
("pmap_pv_demote_pde: page %p is not managed", m));
- TAILQ_INSERT_TAIL(&m->md.pv_list, pv, pv_list);
+ TAILQ_INSERT_TAIL(&m->md.pv_list, pv, pv_next);
if (va == va_last)
goto out;
}
@@ -2612,7 +2675,7 @@ pmap_pv_promote_pde(pmap_t pmap, vm_offset_t va, vm_paddr_t pa,
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 {
@@ -2653,7 +2716,7 @@ pmap_try_insert_pv_entry(pmap_t pmap, vm_offset_t va, vm_page_t m,
if ((pv = get_pv_entry(pmap, NULL)) != NULL) {
pv->pv_va = va;
CHANGE_PV_LIST_LOCK_TO_VM_PAGE(lockp, m);
- 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);
@@ -2677,7 +2740,7 @@ pmap_pv_insert_pde(pmap_t pmap, vm_offset_t va, vm_paddr_t pa,
pv->pv_va = va;
CHANGE_PV_LIST_LOCK_TO_PHYS(lockp, pa);
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);
@@ -3156,7 +3219,7 @@ small_mappings:
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);
}
@@ -4295,7 +4358,7 @@ pmap_page_exists_quick(pmap_t pmap, vm_page_t m)
rw_rlock(&pvh_global_lock);
lock = VM_PAGE_TO_PV_LIST_LOCK(m);
rw_rlock(lock);
- 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;
@@ -4306,7 +4369,7 @@ pmap_page_exists_quick(pmap_t pmap, vm_page_t m)
}
if (!rv && loops < 16 && (m->flags & PG_FICTITIOUS) == 0) {
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;
@@ -4358,7 +4421,7 @@ pmap_pvh_wired_mappings(struct md_page *pvh, int count)
pv_entry_t pv;
rw_assert(&pvh_global_lock, RA_WLOCKED);
- 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);
@@ -4487,7 +4550,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 ((mt->aflags & PGA_WRITEABLE) != 0 &&
@@ -4506,7 +4569,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 ((m->aflags & PGA_WRITEABLE) != 0 &&
TAILQ_EMPTY(&m->md.pv_list) &&
(m->flags & PG_FICTITIOUS) == 0) {
@@ -4581,7 +4644,7 @@ pmap_is_modified_pvh(struct md_page *pvh)
rw_assert(&pvh_global_lock, RA_WLOCKED);
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);
@@ -4652,7 +4715,7 @@ pmap_is_referenced_pvh(struct md_page *pvh)
rw_assert(&pvh_global_lock, RA_WLOCKED);
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);
@@ -4693,7 +4756,7 @@ pmap_remove_write(vm_page_t m)
if ((m->flags & PG_FICTITIOUS) != 0)
goto small_mappings;
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;
@@ -4703,7 +4766,7 @@ pmap_remove_write(vm_page_t m)
PMAP_UNLOCK(pmap);
}
small_mappings:
- 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);
@@ -4756,7 +4819,7 @@ pmap_ts_referenced(vm_page_t m)
if ((m->flags & PG_FICTITIOUS) != 0)
goto small_mappings;
pvh = pa_to_pvh(VM_PAGE_TO_PHYS(m));
- 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;
@@ -4790,9 +4853,9 @@ small_mappings:
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);
@@ -4844,7 +4907,7 @@ pmap_clear_modify(vm_page_t m)
if ((m->flags & PG_FICTITIOUS) != 0)
goto small_mappings;
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;
@@ -4876,7 +4939,7 @@ pmap_clear_modify(vm_page_t m)
PMAP_UNLOCK(pmap);
}
small_mappings:
- 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);
@@ -4913,7 +4976,7 @@ pmap_clear_reference(vm_page_t m)
if ((m->flags & PG_FICTITIOUS) != 0)
goto small_mappings;
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;
@@ -4936,7 +4999,7 @@ pmap_clear_reference(vm_page_t m)
PMAP_UNLOCK(pmap);
}
small_mappings:
- 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);
diff --git a/sys/amd64/include/pmap.h b/sys/amd64/include/pmap.h
index 334d6c6..24fd2bc 100644
--- a/sys/amd64/include/pmap.h
+++ b/sys/amd64/include/pmap.h
@@ -235,10 +235,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.
@@ -277,7 +287,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;
/*
OpenPOWER on IntegriCloud