SEO

Hi, the following diff (adapted from NetBSD) makes kernel store
memory page mappings in a splay tree.

This could potentially speed up some operations (forks, etc.)...
Although, the patch should be considered highly experimental.

Works for me without any trouble for.. around a hour


Index: sys/arch/i386/i386/pmap.c
================================================== =================
RCS file: /cvs/src/sys/arch/i386/i386/pmap.c,v
retrieving revision 1.87
diff -u -r1.87 pmap.c
--- sys/arch/i386/i386/pmap.c 2005/12/25 21:39:06 1.87
+++ sys/arch/i386/i386/pmap.c 2006/01/12 05:13:55
@@ -370,6 +370,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_node, pv_compare);
+SPLAY_GENERATE(pvtree, pv_entry, pv_node, pv_compare);
+
/*
* linked list of all non-kernel pmaps
*/
@@ -1232,7 +1250,7 @@
if (pv == NULL)
panic("pmap_alloc_pv: pvpi_nfree off");
#endif
- pvpage->pvinfo.pvpi_pvfree = pv->pv_next;
+ pvpage->pvinfo.pvpi_pvfree = SPLAY_RIGHT(pv, pv_node);
pv_nfpvents--; /* took one from pool */
} else {
pv = NULL; /* need more of them */
@@ -1295,7 +1313,7 @@
if (pv == NULL)
panic("pmap_alloc_pvpage: pvpi_nfree off");
#endif
- pvpage->pvinfo.pvpi_pvfree = pv->pv_next;
+ pvpage->pvinfo.pvpi_pvfree = SPLAY_RIGHT(pv, pv_node);

pv_nfpvents--; /* took one from pool */
return(pv);
@@ -1371,16 +1389,16 @@
for (idx = 0 ; idx < npg ; idx++) {
struct pv_head *pvhead = vm_physmem[lcv].pmseg.pvhead;

- if (pvhead->pvh_list == NULL)
+ if (SPLAY_ROOT(&pvhead->pvh_root) == NULL)
continue; /* spot check */
if (!simple_lock_try(&pvhead->pvh_lock))
continue;
- cpv = prevpv = pvhead->pvh_list;
+ cpv = prevpv = SPLAY_ROOT(&pvhead->pvh_root);
while (cpv) {
if (pmap_try_steal_pv(pvhead, cpv, prevpv))
break;
prevpv = cpv;
- cpv = cpv->pv_next;
+ cpv = SPLAY_RIGHT(cpv, pv_node);
}
simple_unlock(&pvhead->pvh_lock);
/* got one? break out of the loop! */
@@ -1458,10 +1476,10 @@
* now we need to remove the entry from the pvlist
*/

- if (cpv == pvh->pvh_list)
- pvh->pvh_list = cpv->pv_next;
+ if (cpv == SPLAY_ROOT(&pvh->pvh_root))
+ SPLAY_ROOT(&pvh->pvh_root) = SPLAY_RIGHT(cpv, pv_node);
else
- prevpv->pv_next = cpv->pv_next;
+ SPLAY_RIGHT(prevpv, pv_node) = SPLAY_RIGHT(cpv, pv_node);
return(TRUE);
}

@@ -1485,7 +1503,8 @@
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;
+ SPLAY_RIGHT(&pvp->pvents[lcv], pv_node) =
+ pvp->pvinfo.pvpi_pvfree;
pvp->pvinfo.pvpi_pvfree = &pvp->pvents[lcv];
}
if (need_entry)
@@ -1521,7 +1540,7 @@
}

/* free it */
- pv->pv_next = pvp->pvinfo.pvpi_pvfree;
+ SPLAY_RIGHT(pv, pv_node) = pvp->pvinfo.pvpi_pvfree;
pvp->pvinfo.pvpi_pvfree = pv;

/*
@@ -1575,7 +1594,7 @@
simple_lock(&pvalloc_lock);

for ( /* null */ ; pvs != NULL ; pvs = nextpv) {
- nextpv = pvs->pv_next;
+ nextpv = SPLAY_RIGHT(pvs, pv_node);
pmap_free_pv_doit(pvs);
}

@@ -1676,8 +1695,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 splay tree */
simple_unlock(&pvh->pvh_lock); /* unlock, done! */
}

@@ -1697,18 +1715,14 @@
struct pmap *pmap;
vaddr_t va;
{
- struct pv_entry *pve, **prevptr;
+ struct pv_entry tmp, *pve;

- 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 */
- }
+ 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 */
}

@@ -2435,7 +2449,7 @@
simple_unlock(&vm_physmem[bank].pmseg.pvhead[off].pvh_lock);

if (pve) {
- pve->pv_next = pv_tofree;
+ SPLAY_RIGHT(pve, pv_node) = pv_tofree;
pv_tofree = pve;
}

@@ -2729,7 +2743,7 @@
{
int bank, off;
struct pv_head *pvh;
- struct pv_entry *pve;
+ struct pv_entry *pve, *npve;
pt_entry_t *ptes, opte;
int32_t cpumask = 0;

@@ -2741,7 +2755,7 @@
}

pvh = &vm_physmem[bank].pmseg.pvhead[off];
- if (pvh->pvh_list == NULL) {
+ if (SPLAY_ROOT(&pvh->pvh_root) == NULL) {
return;
}

@@ -2751,7 +2765,8 @@
/* XXX: needed if we hold head->map lock? */
simple_lock(&pvh->pvh_lock);

- for (pve = pvh->pvh_list ; pve != NULL ; pve = 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
@@ -2825,9 +2840,9 @@
}
}
pmap_unmap_ptes(pve->pv_pmap); /* unlocks pmap */
+ SPLAY_REMOVE(pvtree, &pvh->pvh_root, pve); /* remove it */
}
- pmap_free_pvs(NULL, pvh->pvh_list);
- pvh->pvh_list = NULL;
+ pmap_free_pvs(NULL, SPLAY_ROOT(&pvh->pvh_root));
simple_unlock(&pvh->pvh_lock);
PMAP_HEAD_TO_MAP_UNLOCK();
pmap_tlb_shootnow(cpumask);
@@ -2875,7 +2890,7 @@

/* test to see if there is a list before bothering to lock */
pvh = &vm_physmem[bank].pmseg.pvhead[off];
- if (pvh->pvh_list == NULL) {
+ if (SPLAY_ROOT(&pvh->pvh_root) == NULL) {
return(FALSE);
}

@@ -2884,8 +2899,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[atop(pve->pv_va)];
pmap_unmap_ptes(pve->pv_pmap);
@@ -2938,7 +2954,7 @@
result = *myattrs & clearbits;
*myattrs = (*myattrs | setbits) & ~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 "
Index: sys/arch/i386/include/pmap.h
================================================== =================
RCS file: /cvs/src/sys/arch/i386/include/pmap.h,v
retrieving revision 1.40
diff -u -r1.40 pmap.h
--- sys/arch/i386/include/pmap.h 2005/11/23 16:51:28 1.40
+++ sys/arch/i386/include/pmap.h 2006/01/12 05:13:56
@@ -40,6 +40,8 @@
#ifndef _I386_PMAP_H_
#define _I386_PMAP_H_

+#include <sys/tree.h>
+
#include <machine/cpufunc.h>
#include <machine/pte.h>
#include <machine/segments.h>
@@ -289,11 +291,11 @@

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 tree (locked by pvh_lock) */
};

struct pv_entry { /* locked by its list's pvh_lock */
- struct pv_entry *pv_next; /* next entry */
+ SPLAY_ENTRY(pv_entry) pv_node; /* 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 */