Source-Changes-HG archive
[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index][Old Index]
[src/trunk]: src/sys/arch/i386 changed linked list in pmap_remove_pv to a spl...
details: https://anonhg.NetBSD.org/src/rev/a51dfb83706d
branches: trunk
changeset: 553933:a51dfb83706d
user: provos <provos%NetBSD.org@localhost>
date: Thu Oct 23 03:03:20 2003 +0000
description:
changed linked list in pmap_remove_pv to a splay tree; approved: fvdl@
diffstat:
sys/arch/i386/i386/pmap.c | 84 ++++++++++++++++++++++++----------------
sys/arch/i386/include/pmap.h | 4 +-
sys/arch/i386/include/vmparam.h | 7 ++-
3 files changed, 57 insertions(+), 38 deletions(-)
diffs (259 lines):
diff -r 2a671db0a6ca -r a51dfb83706d sys/arch/i386/i386/pmap.c
--- a/sys/arch/i386/i386/pmap.c Thu Oct 23 02:58:49 2003 +0000
+++ b/sys/arch/i386/i386/pmap.c Thu Oct 23 03:03:20 2003 +0000
@@ -1,4 +1,4 @@
-/* $NetBSD: pmap.c,v 1.157 2003/08/24 17:52:31 chs Exp $ */
+/* $NetBSD: pmap.c,v 1.158 2003/10/23 03:03:20 provos Exp $ */
/*
*
@@ -60,7 +60,7 @@
*/
#include <sys/cdefs.h>
-__KERNEL_RCSID(0, "$NetBSD: pmap.c,v 1.157 2003/08/24 17:52:31 chs Exp $");
+__KERNEL_RCSID(0, "$NetBSD: pmap.c,v 1.158 2003/10/23 03:03:20 provos Exp $");
#include "opt_cputype.h"
#include "opt_user_ldt.h"
@@ -388,6 +388,24 @@
#define PVE_HIWAT (PVE_LOWAT + (PVE_PER_PVPAGE * 2))
/* high water mark */
+static __inline int
+pv_compare(struct pv_entry *a, struct pv_entry *b)
+{
+ if (a->pv_pmap < b->pv_pmap)
+ return (-1);
+ else if (a->pv_pmap > b->pv_pmap)
+ return (1);
+ else if (a->pv_va < b->pv_va)
+ return (-1);
+ else if (a->pv_va > b->pv_va)
+ return (1);
+ else
+ return (0);
+}
+
+SPLAY_PROTOTYPE(pvtree, pv_entry, pv_next, pv_compare);
+SPLAY_GENERATE(pvtree, pv_entry, pv_next, pv_compare);
+
/*
* linked list of all non-kernel pmaps
*/
@@ -1199,7 +1217,7 @@
}
pv = pvpage->pvinfo.pvpi_pvfree;
KASSERT(pv);
- pvpage->pvinfo.pvpi_pvfree = pv->pv_next;
+ pvpage->pvinfo.pvpi_pvfree = pv->pv_next.spe_right;
pv_nfpvents--; /* took one from pool */
} else {
pv = NULL; /* need more of them */
@@ -1258,7 +1276,7 @@
pvpage->pvinfo.pvpi_nfree--; /* can't go to zero */
pv = pvpage->pvinfo.pvpi_pvfree;
KASSERT(pv);
- pvpage->pvinfo.pvpi_pvfree = pv->pv_next;
+ pvpage->pvinfo.pvpi_pvfree = pv->pv_next.spe_right;
pv_nfpvents--; /* took one from pool */
return(pv);
}
@@ -1319,7 +1337,7 @@
pvp->pvinfo.pvpi_pvfree = NULL;
pvp->pvinfo.pvpi_nfree = tofree;
for (lcv = 0 ; lcv < tofree ; lcv++) {
- pvp->pvents[lcv].pv_next = pvp->pvinfo.pvpi_pvfree;
+ pvp->pvents[lcv].pv_next.spe_right = pvp->pvinfo.pvpi_pvfree;
pvp->pvinfo.pvpi_pvfree = &pvp->pvents[lcv];
}
if (need_entry)
@@ -1355,7 +1373,7 @@
}
/* free it */
- pv->pv_next = pvp->pvinfo.pvpi_pvfree;
+ pv->pv_next.spe_right = pvp->pvinfo.pvpi_pvfree;
pvp->pvinfo.pvpi_pvfree = pv;
/*
@@ -1409,7 +1427,7 @@
simple_lock(&pvalloc_lock);
for ( /* null */ ; pvs != NULL ; pvs = nextpv) {
- nextpv = pvs->pv_next;
+ nextpv = pvs->pv_next.spe_right;
pmap_free_pv_doit(pvs);
}
@@ -1507,8 +1525,7 @@
pve->pv_va = va;
pve->pv_ptp = ptp; /* NULL for kernel pmap */
simple_lock(&pvh->pvh_lock); /* lock pv_head */
- pve->pv_next = pvh->pvh_list; /* add to ... */
- pvh->pvh_list = pve; /* ... locked list */
+ SPLAY_INSERT(pvtree, &pvh->pvh_root, pve); /* add to locked list */
simple_unlock(&pvh->pvh_lock); /* unlock, done! */
}
@@ -1528,18 +1545,18 @@
struct pmap *pmap;
vaddr_t va;
{
- struct pv_entry *pve, **prevptr;
-
- prevptr = &pvh->pvh_list; /* previous pv_entry pointer */
- pve = *prevptr;
- while (pve) {
- if (pve->pv_pmap == pmap && pve->pv_va == va) { /* match? */
- *prevptr = pve->pv_next; /* remove it! */
- break;
- }
- prevptr = &pve->pv_next; /* previous pointer */
- pve = pve->pv_next; /* advance */
- }
+ struct pv_entry tmp, *pve;
+
+ tmp.pv_pmap = pmap;
+ tmp.pv_va = va;
+
+ pve = SPLAY_FIND(pvtree, &pvh->pvh_root, &tmp);
+
+ if (pve == NULL)
+ return (NULL);
+
+ SPLAY_REMOVE(pvtree, &pvh->pvh_root, pve);
+
return(pve); /* return removed pve */
}
@@ -2217,7 +2234,7 @@
simple_unlock(&mdpg->mp_pvhead.pvh_lock);
if (pve) {
- pve->pv_next = pv_tofree;
+ pve->pv_next.spe_right = pv_tofree;
pv_tofree = pve;
}
@@ -2523,7 +2540,7 @@
struct vm_page *pg;
{
struct pv_head *pvh;
- struct pv_entry *pve, *npve, **prevptr, *killlist = NULL;
+ struct pv_entry *pve, *npve, *killlist = NULL;
pt_entry_t *ptes, opte;
int32_t cpumask = 0;
@@ -2536,7 +2553,7 @@
#endif
pvh = &pg->mdpage.mp_pvhead;
- if (pvh->pvh_list == NULL) {
+ if (SPLAY_ROOT(&pvh->pvh_root) == NULL) {
return;
}
@@ -2546,9 +2563,8 @@
/* XXX: needed if we hold head->map lock? */
simple_lock(&pvh->pvh_lock);
- for (prevptr = &pvh->pvh_list, pve = pvh->pvh_list;
- pve != NULL; pve = npve) {
- npve = pve->pv_next;
+ for (pve = SPLAY_MIN(pvtree, &pvh->pvh_root); pve != NULL; pve = npve) {
+ npve = SPLAY_NEXT(pvtree, &pvh->pvh_root, pve);
ptes = pmap_map_ptes(pve->pv_pmap); /* locks pmap */
#ifdef DIAGNOSTIC
@@ -2608,12 +2624,11 @@
}
}
pmap_unmap_ptes(pve->pv_pmap); /* unlocks pmap */
- *prevptr = npve; /* remove it */
- pve->pv_next = killlist; /* mark it for death */
+ SPLAY_REMOVE(pvtree, &pvh->pvh_root, pve); /* remove it */
+ pve->pv_next.spe_right = killlist; /* mark it for death */
killlist = pve;
}
pmap_free_pvs(NULL, killlist);
- pvh->pvh_list = NULL;
simple_unlock(&pvh->pvh_lock);
PMAP_HEAD_TO_MAP_UNLOCK();
pmap_tlb_shootnow(cpumask);
@@ -2663,7 +2678,7 @@
/* test to see if there is a list before bothering to lock */
pvh = &mdpg->mp_pvhead;
- if (pvh->pvh_list == NULL) {
+ if (SPLAY_ROOT(&pvh->pvh_root) == NULL) {
return(FALSE);
}
@@ -2672,8 +2687,9 @@
/* XXX: needed if we hold head->map lock? */
simple_lock(&pvh->pvh_lock);
- for (pve = pvh->pvh_list; pve != NULL && (*myattrs & testbits) == 0;
- pve = pve->pv_next) {
+ for (pve = SPLAY_MIN(pvtree, &pvh->pvh_root);
+ pve != NULL && (*myattrs & testbits) == 0;
+ pve = SPLAY_NEXT(pvtree, &pvh->pvh_root, pve)) {
ptes = pmap_map_ptes(pve->pv_pmap);
pte = ptes[x86_btop(pve->pv_va)];
pmap_unmap_ptes(pve->pv_pmap);
@@ -2728,7 +2744,7 @@
result = *myattrs & clearbits;
*myattrs &= ~clearbits;
- for (pve = pvh->pvh_list; pve != NULL; pve = pve->pv_next) {
+ SPLAY_FOREACH(pve, pvtree, &pvh->pvh_root) {
#ifdef DIAGNOSTIC
if (!pmap_valid_entry(pve->pv_pmap->pm_pdir[pdei(pve->pv_va)]))
panic("pmap_change_attrs: mapping without PTP "
diff -r 2a671db0a6ca -r a51dfb83706d sys/arch/i386/include/pmap.h
--- a/sys/arch/i386/include/pmap.h Thu Oct 23 02:58:49 2003 +0000
+++ b/sys/arch/i386/include/pmap.h Thu Oct 23 03:03:20 2003 +0000
@@ -1,4 +1,4 @@
-/* $NetBSD: pmap.h,v 1.75 2003/08/24 17:52:33 chs Exp $ */
+/* $NetBSD: pmap.h,v 1.76 2003/10/23 03:03:20 provos Exp $ */
/*
*
@@ -268,7 +268,7 @@
*/
struct pv_entry { /* locked by its list's pvh_lock */
- struct pv_entry *pv_next; /* next entry */
+ SPLAY_ENTRY(pv_entry) pv_next; /* next entry */
struct pmap *pv_pmap; /* the pmap */
vaddr_t pv_va; /* the virtual address */
struct vm_page *pv_ptp; /* the vm_page of the PTP */
diff -r 2a671db0a6ca -r a51dfb83706d sys/arch/i386/include/vmparam.h
--- a/sys/arch/i386/include/vmparam.h Thu Oct 23 02:58:49 2003 +0000
+++ b/sys/arch/i386/include/vmparam.h Thu Oct 23 03:03:20 2003 +0000
@@ -1,4 +1,4 @@
-/* $NetBSD: vmparam.h,v 1.54 2003/08/24 17:52:33 chs Exp $ */
+/* $NetBSD: vmparam.h,v 1.55 2003/10/23 03:03:20 provos Exp $ */
/*-
* Copyright (c) 1990 The Regents of the University of California.
@@ -37,6 +37,8 @@
#ifndef _VMPARAM_H_
#define _VMPARAM_H_
+#include <sys/tree.h>
+
/*
* Machine dependent constants for 386.
*/
@@ -143,7 +145,8 @@
struct pv_head {
struct simplelock pvh_lock; /* locks every pv on this list */
- struct pv_entry *pvh_list; /* head of list (locked by pvh_lock) */
+ SPLAY_HEAD(pvtree, pv_entry) pvh_root;
+ /* head of list (locked by pvh_lock) */
};
struct vm_page_md {
Home |
Main Index |
Thread Index |
Old Index