SEO
vBulletin Search Engine Optimization
| |||||||
| Register | FAQ | Members List | Calendar | Search | Today's Posts | Mark Forums Read |
02-22-2008, 12:03 PM
| ||||
| ||||
 Re: use splay trees instead of lists for vm mappings do you have numbers for performance diff? like before and after for 3 make builds? i also suspect that a rb tree may be better too. On 1/11/06, Mike Belopuhov <mkb@crypt.org.ru> wrote: > 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 */      |
Linear Mode
