summaryrefslogtreecommitdiff
path: root/sys
diff options
context:
space:
mode:
Diffstat (limited to 'sys')
-rw-r--r--sys/arch/amd64/amd64/pmap.c18
-rw-r--r--sys/arch/hppa/hppa/pmap.c10
-rw-r--r--sys/arch/i386/i386/pmap.c19
-rw-r--r--sys/arch/i386/i386/pmapae.c20
-rw-r--r--sys/kern/vfs_biomem.c4
-rw-r--r--sys/uvm/uvm_aobj.c13
-rw-r--r--sys/uvm/uvm_device.c6
-rw-r--r--sys/uvm/uvm_init.c8
-rw-r--r--sys/uvm/uvm_map.c9
-rw-r--r--sys/uvm/uvm_object.h16
-rw-r--r--sys/uvm/uvm_page.c176
-rw-r--r--sys/uvm/uvm_page.h21
-rw-r--r--sys/uvm/uvm_vnode.c30
13 files changed, 93 insertions, 257 deletions
diff --git a/sys/arch/amd64/amd64/pmap.c b/sys/arch/amd64/amd64/pmap.c
index b6ff88bef80..d7dfac863d5 100644
--- a/sys/arch/amd64/amd64/pmap.c
+++ b/sys/arch/amd64/amd64/pmap.c
@@ -1,4 +1,4 @@
-/* $OpenBSD: pmap.c,v 1.49 2009/06/16 16:42:40 ariane Exp $ */
+/* $OpenBSD: pmap.c,v 1.50 2009/08/06 15:28:14 oga Exp $ */
/* $NetBSD: pmap.c,v 1.3 2003/05/08 18:13:13 thorpej Exp $ */
/*
@@ -567,7 +567,7 @@ pmap_bootstrap(paddr_t first_avail, paddr_t max_pa)
kpm = pmap_kernel();
for (i = 0; i < PTP_LEVELS - 1; i++) {
kpm->pm_obj[i].pgops = NULL;
- TAILQ_INIT(&kpm->pm_obj[i].memq);
+ RB_INIT(&kpm->pm_obj[i].memt);
kpm->pm_obj[i].uo_npages = 0;
kpm->pm_obj[i].uo_refs = 1;
kpm->pm_ptphint[i] = NULL;
@@ -832,10 +832,10 @@ pmap_freepage(struct pmap *pmap, struct vm_page *ptp, int level,
obj = &pmap->pm_obj[lidx];
pmap->pm_stats.resident_count--;
if (pmap->pm_ptphint[lidx] == ptp)
- pmap->pm_ptphint[lidx] = TAILQ_FIRST(&obj->memq);
+ pmap->pm_ptphint[lidx] = RB_ROOT(&obj->memt);
ptp->wire_count = 0;
uvm_pagerealloc(ptp, NULL, 0);
- TAILQ_INSERT_TAIL(pagelist, ptp, listq);
+ TAILQ_INSERT_TAIL(pagelist, ptp, pageq);
}
void
@@ -1019,7 +1019,7 @@ pmap_create(void)
/* init uvm_object */
for (i = 0; i < PTP_LEVELS - 1; i++) {
pmap->pm_obj[i].pgops = NULL; /* not a mappable object */
- TAILQ_INIT(&pmap->pm_obj[i].memq);
+ RB_INIT(&pmap->pm_obj[i].memt);
pmap->pm_obj[i].uo_npages = 0;
pmap->pm_obj[i].uo_refs = 1;
pmap->pm_ptphint[i] = NULL;
@@ -1091,7 +1091,7 @@ pmap_destroy(struct pmap *pmap)
*/
for (i = 0; i < PTP_LEVELS - 1; i++) {
- while ((pg = TAILQ_FIRST(&pmap->pm_obj[i].memq)) != NULL) {
+ while ((pg = RB_ROOT(&pmap->pm_obj[i].memt)) != NULL) {
KASSERT((pg->pg_flags & PG_BUSY) == 0);
pg->wire_count = 0;
@@ -1537,7 +1537,7 @@ pmap_do_remove(struct pmap *pmap, vaddr_t sva, vaddr_t eva, int flags)
PMAP_MAP_TO_HEAD_UNLOCK();
while ((ptp = TAILQ_FIRST(&empty_ptps)) != NULL) {
- TAILQ_REMOVE(&empty_ptps, ptp, listq);
+ TAILQ_REMOVE(&empty_ptps, ptp, pageq);
uvm_pagefree(ptp);
}
@@ -1609,7 +1609,7 @@ pmap_do_remove(struct pmap *pmap, vaddr_t sva, vaddr_t eva, int flags)
PMAP_MAP_TO_HEAD_UNLOCK();
while ((ptp = TAILQ_FIRST(&empty_ptps)) != NULL) {
- TAILQ_REMOVE(&empty_ptps, ptp, listq);
+ TAILQ_REMOVE(&empty_ptps, ptp, pageq);
uvm_pagefree(ptp);
}
}
@@ -1682,7 +1682,7 @@ pmap_page_remove(struct vm_page *pg)
pmap_tlb_shootwait();
while ((ptp = TAILQ_FIRST(&empty_ptps)) != NULL) {
- TAILQ_REMOVE(&empty_ptps, ptp, listq);
+ TAILQ_REMOVE(&empty_ptps, ptp, pageq);
uvm_pagefree(ptp);
}
}
diff --git a/sys/arch/hppa/hppa/pmap.c b/sys/arch/hppa/hppa/pmap.c
index a2829a528c6..90c0d57273d 100644
--- a/sys/arch/hppa/hppa/pmap.c
+++ b/sys/arch/hppa/hppa/pmap.c
@@ -1,4 +1,4 @@
-/* $OpenBSD: pmap.c,v 1.141 2009/07/29 18:31:11 kettenis Exp $ */
+/* $OpenBSD: pmap.c,v 1.142 2009/08/06 15:28:14 oga Exp $ */
/*
* Copyright (c) 1998-2004 Michael Shalayeff
@@ -235,7 +235,7 @@ pmap_pde_release(struct pmap *pmap, vaddr_t va, struct vm_page *ptp)
pmap_pde_set(pmap, va, 0);
pmap->pm_stats.resident_count--;
if (pmap->pm_ptphint == ptp)
- pmap->pm_ptphint = TAILQ_FIRST(&pmap->pm_obj.memq);
+ pmap->pm_ptphint = RB_ROOT(&pmap->pm_obj.memt);
ptp->wire_count = 0;
#ifdef DIAGNOSTIC
if (ptp->pg_flags & PG_BUSY)
@@ -471,7 +471,7 @@ pmap_bootstrap(vstart)
bzero(kpm, sizeof(*kpm));
simple_lock_init(&kpm->pm_lock);
kpm->pm_obj.pgops = NULL;
- TAILQ_INIT(&kpm->pm_obj.memq);
+ RB_INIT(&kpm->pm_obj.memt);
kpm->pm_obj.uo_npages = 0;
kpm->pm_obj.uo_refs = 1;
kpm->pm_space = HPPA_SID_KERNEL;
@@ -657,7 +657,7 @@ pmap_create()
simple_lock_init(&pmap->pm_lock);
pmap->pm_obj.pgops = NULL; /* currently not a mappable object */
- TAILQ_INIT(&pmap->pm_obj.memq);
+ RB_INIT(&pmap->pm_obj.memt);
pmap->pm_obj.uo_npages = 0;
pmap->pm_obj.uo_refs = 1;
@@ -699,7 +699,7 @@ pmap_destroy(pmap)
return;
#ifdef DIAGNOSTIC
- while ((pg = TAILQ_FIRST(&pmap->pm_obj.memq))) {
+ while ((pg = RB_ROOT(&pmap->pm_obj.memt))) {
pt_entry_t *pde, *epde;
struct vm_page *sheep;
struct pv_entry *haggis;
diff --git a/sys/arch/i386/i386/pmap.c b/sys/arch/i386/i386/pmap.c
index 00cd9bf142d..a553b083971 100644
--- a/sys/arch/i386/i386/pmap.c
+++ b/sys/arch/i386/i386/pmap.c
@@ -1,4 +1,4 @@
-/* $OpenBSD: pmap.c,v 1.143 2009/07/25 12:55:39 miod Exp $ */
+/* $OpenBSD: pmap.c,v 1.144 2009/08/06 15:28:14 oga Exp $ */
/* $NetBSD: pmap.c,v 1.91 2000/06/02 17:46:37 thorpej Exp $ */
/*
@@ -805,7 +805,7 @@ pmap_bootstrap(vaddr_t kva_start)
kpm = pmap_kernel();
simple_lock_init(&kpm->pm_obj.vmobjlock);
kpm->pm_obj.pgops = NULL;
- TAILQ_INIT(&kpm->pm_obj.memq);
+ RB_INIT(&kpm->pm_obj.memt);
kpm->pm_obj.uo_npages = 0;
kpm->pm_obj.uo_refs = 1;
bzero(&kpm->pm_list, sizeof(kpm->pm_list)); /* pm_list not used */
@@ -1424,7 +1424,7 @@ pmap_drop_ptp(struct pmap *pm, vaddr_t va, struct vm_page *ptp,
pm->pm_stats.resident_count--;
/* update hint */
if (pm->pm_ptphint == ptp)
- pm->pm_ptphint = TAILQ_FIRST(&pm->pm_obj.memq);
+ pm->pm_ptphint = RB_ROOT(&pm->pm_obj.memt);
ptp->wire_count = 0;
/* Postpone free to after shootdown. */
uvm_pagerealloc(ptp, NULL, 0);
@@ -1461,7 +1461,7 @@ pmap_pinit(struct pmap *pmap)
/* init uvm_object */
simple_lock_init(&pmap->pm_obj.vmobjlock);
pmap->pm_obj.pgops = NULL; /* currently not a mappable object */
- TAILQ_INIT(&pmap->pm_obj.memq);
+ RB_INIT(&pmap->pm_obj.memt);
pmap->pm_obj.uo_npages = 0;
pmap->pm_obj.uo_refs = 1;
pmap->pm_stats.wired_count = 0;
@@ -1533,8 +1533,7 @@ pmap_destroy(struct pmap *pmap)
simple_unlock(&pmaps_lock);
/* Free any remaining PTPs. */
- while (!TAILQ_EMPTY(&pmap->pm_obj.memq)) {
- pg = TAILQ_FIRST(&pmap->pm_obj.memq);
+ while ((pg = RB_ROOT(&pmap->pm_obj.memt)) != NULL) {
pg->wire_count = 0;
uvm_pagefree(pg);
}
@@ -2009,7 +2008,7 @@ pmap_do_remove(struct pmap *pmap, vaddr_t sva, vaddr_t eva, int flags)
/* If PTP is no longer being used, free it. */
if (ptp && ptp->wire_count <= 1) {
pmap_drop_ptp(pmap, va, ptp, ptes);
- TAILQ_INSERT_TAIL(&empty_ptps, ptp, listq);
+ TAILQ_INSERT_TAIL(&empty_ptps, ptp, pageq);
}
if (!shootall)
@@ -2023,7 +2022,7 @@ pmap_do_remove(struct pmap *pmap, vaddr_t sva, vaddr_t eva, int flags)
pmap_unmap_ptes(pmap);
PMAP_MAP_TO_HEAD_UNLOCK();
while ((ptp = TAILQ_FIRST(&empty_ptps)) != NULL) {
- TAILQ_REMOVE(&empty_ptps, ptp, listq);
+ TAILQ_REMOVE(&empty_ptps, ptp, pageq);
uvm_pagefree(ptp);
}
}
@@ -2080,7 +2079,7 @@ pmap_page_remove(struct vm_page *pg)
if (pve->pv_ptp && --pve->pv_ptp->wire_count <= 1) {
pmap_drop_ptp(pve->pv_pmap, pve->pv_va,
pve->pv_ptp, ptes);
- TAILQ_INSERT_TAIL(&empty_ptps, pve->pv_ptp, listq);
+ TAILQ_INSERT_TAIL(&empty_ptps, pve->pv_ptp, pageq);
}
pmap_tlb_shootpage(pve->pv_pmap, pve->pv_va);
@@ -2093,7 +2092,7 @@ pmap_page_remove(struct vm_page *pg)
pmap_tlb_shootwait();
while ((ptp = TAILQ_FIRST(&empty_ptps)) != NULL) {
- TAILQ_REMOVE(&empty_ptps, ptp, listq);
+ TAILQ_REMOVE(&empty_ptps, ptp, pageq);
uvm_pagefree(ptp);
}
}
diff --git a/sys/arch/i386/i386/pmapae.c b/sys/arch/i386/i386/pmapae.c
index ed75721ad3c..8b17da23f22 100644
--- a/sys/arch/i386/i386/pmapae.c
+++ b/sys/arch/i386/i386/pmapae.c
@@ -1,4 +1,4 @@
-/* $OpenBSD: pmapae.c,v 1.19 2009/06/16 16:42:41 ariane Exp $ */
+/* $OpenBSD: pmapae.c,v 1.20 2009/08/06 15:28:14 oga Exp $ */
/*
* Copyright (c) 2006 Michael Shalayeff
@@ -1449,18 +1449,18 @@ pmap_remove_pae(struct pmap *pmap, vaddr_t sva, vaddr_t eva)
pmap->pm_stats.resident_count--;
if (pmap->pm_ptphint == ptp)
pmap->pm_ptphint =
- TAILQ_FIRST(&pmap->pm_obj.memq);
+ RB_ROOT(&pmap->pm_obj.memt);
ptp->wire_count = 0;
/* Postpone free to after shootdown. */
uvm_pagerealloc(ptp, NULL, 0);
- TAILQ_INSERT_TAIL(&empty_ptps, ptp, listq);
+ TAILQ_INSERT_TAIL(&empty_ptps, ptp, pageq);
}
}
pmap_tlb_shootnow(cpumask);
pmap_unmap_ptes_pae(pmap); /* unlock pmap */
PMAP_MAP_TO_HEAD_UNLOCK();
while ((ptp = TAILQ_FIRST(&empty_ptps)) != NULL) {
- TAILQ_REMOVE(&empty_ptps, ptp, listq);
+ TAILQ_REMOVE(&empty_ptps, ptp, pageq);
uvm_pagefree(ptp);
}
return;
@@ -1542,11 +1542,11 @@ pmap_remove_pae(struct pmap *pmap, vaddr_t sva, vaddr_t eva)
pmap->pm_stats.resident_count--;
if (pmap->pm_ptphint == ptp) /* update hint? */
pmap->pm_ptphint =
- TAILQ_FIRST(&pmap->pm_obj.memq);
+ RB_ROOT(&pmap->pm_obj.memt);
ptp->wire_count = 0;
/* Postpone free to after shootdown. */
uvm_pagerealloc(ptp, NULL, 0);
- TAILQ_INSERT_TAIL(&empty_ptps, ptp, listq);
+ TAILQ_INSERT_TAIL(&empty_ptps, ptp, pageq);
}
}
@@ -1554,7 +1554,7 @@ pmap_remove_pae(struct pmap *pmap, vaddr_t sva, vaddr_t eva)
pmap_unmap_ptes_pae(pmap);
PMAP_MAP_TO_HEAD_UNLOCK();
while ((ptp = TAILQ_FIRST(&empty_ptps)) != NULL) {
- TAILQ_REMOVE(&empty_ptps, ptp, listq);
+ TAILQ_REMOVE(&empty_ptps, ptp, pageq);
uvm_pagefree(ptp);
}
}
@@ -1660,12 +1660,12 @@ pmap_page_remove_pae(struct vm_page *pg)
/* update hint? */
if (pve->pv_pmap->pm_ptphint == pve->pv_ptp)
pve->pv_pmap->pm_ptphint =
- TAILQ_FIRST(&pve->pv_pmap->pm_obj.memq);
+ RB_ROOT(&pve->pv_pmap->pm_obj.memt);
pve->pv_ptp->wire_count = 0;
/* Postpone free to after shootdown. */
uvm_pagerealloc(pve->pv_ptp, NULL, 0);
TAILQ_INSERT_TAIL(&empty_ptps, pve->pv_ptp,
- listq);
+ pageq);
}
}
pmap_unmap_ptes_pae(pve->pv_pmap); /* unlocks pmap */
@@ -1676,7 +1676,7 @@ pmap_page_remove_pae(struct vm_page *pg)
PMAP_HEAD_TO_MAP_UNLOCK();
pmap_tlb_shootnow(cpumask);
while ((ptp = TAILQ_FIRST(&empty_ptps)) != NULL) {
- TAILQ_REMOVE(&empty_ptps, ptp, listq);
+ TAILQ_REMOVE(&empty_ptps, ptp, pageq);
uvm_pagefree(ptp);
}
}
diff --git a/sys/kern/vfs_biomem.c b/sys/kern/vfs_biomem.c
index 89ab5f4d114..6b7aaa8d5e2 100644
--- a/sys/kern/vfs_biomem.c
+++ b/sys/kern/vfs_biomem.c
@@ -1,4 +1,4 @@
-/* $OpenBSD: vfs_biomem.c,v 1.9 2009/06/25 15:49:26 thib Exp $ */
+/* $OpenBSD: vfs_biomem.c,v 1.10 2009/08/06 15:28:14 oga Exp $ */
/*
* Copyright (c) 2007 Artur Grabowski <art@openbsd.org>
*
@@ -64,7 +64,7 @@ buf_mem_init(vsize_t size)
buf_object = &buf_object_store;
buf_object->pgops = NULL;
- TAILQ_INIT(&buf_object->memq);
+ RB_INIT(&buf_object->memt);
buf_object->uo_npages = 0;
buf_object->uo_refs = 1;
}
diff --git a/sys/uvm/uvm_aobj.c b/sys/uvm/uvm_aobj.c
index cc5a075e77f..4dd1c82e0a3 100644
--- a/sys/uvm/uvm_aobj.c
+++ b/sys/uvm/uvm_aobj.c
@@ -1,4 +1,4 @@
-/* $OpenBSD: uvm_aobj.c,v 1.46 2009/07/22 21:05:37 oga Exp $ */
+/* $OpenBSD: uvm_aobj.c,v 1.47 2009/08/06 15:28:14 oga Exp $ */
/* $NetBSD: uvm_aobj.c,v 1.39 2001/02/18 21:19:08 chs Exp $ */
/*
@@ -144,7 +144,7 @@ struct pool uao_swhash_elt_pool;
*/
struct uvm_aobj {
- struct uvm_object u_obj; /* has: lock, pgops, memq, #pages, #refs */
+ struct uvm_object u_obj; /* has: lock, pgops, memt, #pages, #refs */
int u_pages; /* number of pages in entire object */
int u_flags; /* the flags (see uvm_aobj.h) */
int *u_swslots; /* array of offset->swapslot mappings */
@@ -523,7 +523,7 @@ uao_create(vsize_t size, int flags)
*/
simple_lock_init(&aobj->u_obj.vmobjlock);
aobj->u_obj.pgops = &aobj_pager;
- TAILQ_INIT(&aobj->u_obj.memq);
+ RB_INIT(&aobj->u_obj.memt);
aobj->u_obj.uo_npages = 0;
/*
@@ -667,7 +667,7 @@ uao_detach_locked(struct uvm_object *uobj)
* Release swap resources then free the page.
*/
uvm_lock_pageq();
- while((pg = TAILQ_FIRST(&uobj->memq)) != NULL) {
+ while((pg = RB_ROOT(&uobj->memt)) != NULL) {
if (pg->pg_flags & PG_BUSY) {
atomic_setbits_int(&pg->pg_flags, PG_WANTED);
uvm_unlock_pageq();
@@ -702,11 +702,6 @@ uao_detach_locked(struct uvm_object *uobj)
* or block.
* => if PGO_ALLPAGE is set, then all pages in the object are valid targets
* for flushing.
- * => NOTE: we rely on the fact that the object's memq is a TAILQ and
- * that new pages are inserted on the tail end of the list. thus,
- * we can make a complete pass through the object in one go by starting
- * at the head and working towards the tail (new pages are put in
- * front of us).
* => NOTE: we are allowed to lock the page queues, so the caller
* must not be holding the lock on them [e.g. pagedaemon had
* better not call us with the queues locked]
diff --git a/sys/uvm/uvm_device.c b/sys/uvm/uvm_device.c
index 53b28c095e5..27e079934b3 100644
--- a/sys/uvm/uvm_device.c
+++ b/sys/uvm/uvm_device.c
@@ -1,4 +1,4 @@
-/* $OpenBSD: uvm_device.c,v 1.35 2009/06/16 23:54:57 oga Exp $ */
+/* $OpenBSD: uvm_device.c,v 1.36 2009/08/06 15:28:14 oga Exp $ */
/* $NetBSD: uvm_device.c,v 1.30 2000/11/25 06:27:59 chs Exp $ */
/*
@@ -245,7 +245,7 @@ udv_attach(void *arg, vm_prot_t accessprot, voff_t off, vsize_t size)
simple_lock_init(&udv->u_obj.vmobjlock);
udv->u_obj.pgops = &uvm_deviceops;
- TAILQ_INIT(&udv->u_obj.memq);
+ RB_INIT(&udv->u_obj.memt);
udv->u_obj.uo_npages = 0;
udv->u_obj.uo_refs = 1;
udv->u_flags = 0;
@@ -305,7 +305,7 @@ again:
uobj,uobj->uo_refs,0,0);
return;
}
- KASSERT(uobj->uo_npages == 0 && TAILQ_EMPTY(&uobj->memq));
+ KASSERT(uobj->uo_npages == 0 && RB_EMPTY(&uobj->memt));
/*
* is it being held? if so, wait until others are done.
diff --git a/sys/uvm/uvm_init.c b/sys/uvm/uvm_init.c
index 76931227928..69502ec87b3 100644
--- a/sys/uvm/uvm_init.c
+++ b/sys/uvm/uvm_init.c
@@ -1,4 +1,4 @@
-/* $OpenBSD: uvm_init.c,v 1.24 2009/06/16 23:54:58 oga Exp $ */
+/* $OpenBSD: uvm_init.c,v 1.25 2009/08/06 15:28:14 oga Exp $ */
/* $NetBSD: uvm_init.c,v 1.14 2000/06/27 17:29:23 mrg Exp $ */
/*
@@ -143,12 +143,10 @@ uvm_init(void)
uvm_km_page_init();
/*
- * the VM system is now up! now that malloc is up we can resize the
- * <obj,off> => <page> hash table for general use and enable paging
- * of kernel objects.
+ * the VM system is now up! now that malloc is up we can
+ * enable paging of kernel objects.
*/
- uvm_page_rehash();
uao_create(VM_MAX_KERNEL_ADDRESS - VM_MIN_KERNEL_ADDRESS,
UAO_FLAG_KERNSWAP);
diff --git a/sys/uvm/uvm_map.c b/sys/uvm/uvm_map.c
index 1710efb09a3..e418e9bbeb6 100644
--- a/sys/uvm/uvm_map.c
+++ b/sys/uvm/uvm_map.c
@@ -1,4 +1,4 @@
-/* $OpenBSD: uvm_map.c,v 1.119 2009/07/25 12:55:40 miod Exp $ */
+/* $OpenBSD: uvm_map.c,v 1.120 2009/08/06 15:28:14 oga Exp $ */
/* $NetBSD: uvm_map.c,v 1.86 2000/11/27 08:40:03 chs Exp $ */
/*
@@ -3823,13 +3823,12 @@ uvm_object_printit(uobj, full, pr)
return;
}
(*pr)(" PAGES <pg,offset>:\n ");
- for (pg = TAILQ_FIRST(&uobj->memq);
- pg != NULL;
- pg = TAILQ_NEXT(pg, listq), cnt++) {
+ RB_FOREACH(pg, uvm_objtree, &uobj->memt) {
(*pr)("<%p,0x%llx> ", pg, (long long)pg->offset);
if ((cnt % 3) == 2) {
(*pr)("\n ");
}
+ cnt++;
}
if ((cnt % 3) != 2) {
(*pr)("\n");
@@ -3886,7 +3885,7 @@ uvm_page_printit(pg, full, pr)
uobj = pg->uobject;
if (uobj) {
(*pr)(" checking object list\n");
- TAILQ_FOREACH(tpg, &uobj->memq, listq) {
+ RB_FOREACH(tpg, uvm_objtree, &uobj->memt) {
if (tpg == pg) {
break;
}
diff --git a/sys/uvm/uvm_object.h b/sys/uvm/uvm_object.h
index 44a16bfd7c1..b1b9366fe57 100644
--- a/sys/uvm/uvm_object.h
+++ b/sys/uvm/uvm_object.h
@@ -1,4 +1,4 @@
-/* $OpenBSD: uvm_object.h,v 1.14 2009/06/17 00:13:59 oga Exp $ */
+/* $OpenBSD: uvm_object.h,v 1.15 2009/08/06 15:28:14 oga Exp $ */
/* $NetBSD: uvm_object.h,v 1.11 2001/03/09 01:02:12 chs Exp $ */
/*
@@ -47,11 +47,11 @@
*/
struct uvm_object {
- simple_lock_data_t vmobjlock; /* lock on memq */
- struct uvm_pagerops *pgops; /* pager ops */
- struct pglist memq; /* pages in this object */
- int uo_npages; /* # of pages in memq */
- int uo_refs; /* reference count */
+ simple_lock_data_t vmobjlock; /* lock on memt */
+ struct uvm_pagerops *pgops; /* pager ops */
+ RB_HEAD(uvm_objtree, vm_page) memt; /* pages in object */
+ int uo_npages; /* # of pages in memt */
+ int uo_refs; /* reference count */
};
/*
@@ -83,6 +83,10 @@ struct uvm_object {
extern struct uvm_pagerops uvm_vnodeops;
extern struct uvm_pagerops uvm_deviceops;
+/* For object trees */
+int uvm_pagecmp(struct vm_page *, struct vm_page *);
+RB_PROTOTYPE(uvm_objtree, vm_page, objt, uvm_pagecmp)
+
#define UVM_OBJ_IS_VNODE(uobj) \
((uobj)->pgops == &uvm_vnodeops)
diff --git a/sys/uvm/uvm_page.c b/sys/uvm/uvm_page.c
index 76ca752bea1..2faa524de07 100644
--- a/sys/uvm/uvm_page.c
+++ b/sys/uvm/uvm_page.c
@@ -1,4 +1,4 @@
-/* $OpenBSD: uvm_page.c,v 1.94 2009/07/26 21:26:10 deraadt Exp $ */
+/* $OpenBSD: uvm_page.c,v 1.95 2009/08/06 15:28:14 oga Exp $ */
/* $NetBSD: uvm_page.c,v 1.44 2000/11/27 08:40:04 chs Exp $ */
/*
@@ -82,6 +82,17 @@
#include <uvm/uvm.h>
/*
+ * for object trees
+ */
+RB_GENERATE(uvm_objtree, vm_page, objt, uvm_pagecmp);
+
+int
+uvm_pagecmp(struct vm_page *a, struct vm_page *b)
+{
+ return (a->offset < b->offset ? -1 : a->offset > b->offset);
+}
+
+/*
* global vars... XXXCDC: move to uvm. structure.
*/
@@ -118,14 +129,6 @@ static vaddr_t virtual_space_start;
static vaddr_t virtual_space_end;
/*
- * we use a hash table with only one bucket during bootup. we will
- * later rehash (resize) the hash table once the allocator is ready.
- * we static allocate the one bootstrap bucket below...
- */
-
-static struct pglist uvm_bootbucket;
-
-/*
* History
*/
UVMHIST_DECL(pghist);
@@ -142,10 +145,10 @@ static void uvm_pageremove(struct vm_page *);
*/
/*
- * uvm_pageinsert: insert a page in the object and the hash table
+ * uvm_pageinsert: insert a page in the object
*
* => caller must lock object
- * => caller must lock page queues
+ * => caller must lock page queues XXX questionable
* => call should have already set pg's object and offset pointers
* and bumped the version counter
*/
@@ -153,22 +156,17 @@ static void uvm_pageremove(struct vm_page *);
__inline static void
uvm_pageinsert(struct vm_page *pg)
{
- struct pglist *buck;
UVMHIST_FUNC("uvm_pageinsert"); UVMHIST_CALLED(pghist);
KASSERT((pg->pg_flags & PG_TABLED) == 0);
- mtx_enter(&uvm.hashlock);
- buck = &uvm.page_hash[uvm_pagehash(pg->uobject,pg->offset)];
- TAILQ_INSERT_TAIL(buck, pg, hashq); /* put in hash */
- mtx_leave(&uvm.hashlock);
-
- TAILQ_INSERT_TAIL(&pg->uobject->memq, pg, listq); /* put in object */
+ /* XXX should we check duplicates? */
+ RB_INSERT(uvm_objtree, &pg->uobject->memt, pg);
atomic_setbits_int(&pg->pg_flags, PG_TABLED);
pg->uobject->uo_npages++;
}
/*
- * uvm_page_remove: remove page from object and hash
+ * uvm_page_remove: remove page from object
*
* => caller must lock object
* => caller must lock page queues
@@ -177,23 +175,10 @@ uvm_pageinsert(struct vm_page *pg)
static __inline void
uvm_pageremove(struct vm_page *pg)
{
- struct pglist *buck;
UVMHIST_FUNC("uvm_pageremove"); UVMHIST_CALLED(pghist);
KASSERT(pg->pg_flags & PG_TABLED);
- mtx_enter(&uvm.hashlock);
- buck = &uvm.page_hash[uvm_pagehash(pg->uobject,pg->offset)];
- TAILQ_REMOVE(buck, pg, hashq);
- mtx_leave(&uvm.hashlock);
-
-#ifdef UBC
- if (pg->uobject->pgops == &uvm_vnodeops) {
- uvm_pgcnt_vnode--;
- }
-#endif
-
- /* object should be locked */
- TAILQ_REMOVE(&pg->uobject->memq, pg, listq);
+ RB_REMOVE(uvm_objtree, &pg->uobject->memt, pg);
atomic_clearbits_int(&pg->pg_flags, PG_TABLED);
pg->uobject->uo_npages--;
@@ -236,18 +221,6 @@ uvm_page_init(vaddr_t *kvm_startp, vaddr_t *kvm_endp)
simple_lock_init(&uvm.pageqlock);
mtx_init(&uvm.fpageqlock, IPL_VM);
- /*
- * init the <obj,offset> => <page> hash table. for now
- * we just have one bucket (the bootstrap bucket). later on we
- * will allocate new buckets as we dynamically resize the hash table.
- */
-
- uvm.page_nhash = 1; /* 1 bucket */
- uvm.page_hashmask = 0; /* mask for hash function */
- uvm.page_hash = &uvm_bootbucket; /* install bootstrap bucket */
- TAILQ_INIT(uvm.page_hash); /* init hash table */
- mtx_init(&uvm.hashlock, IPL_VM); /* init hash table lock */
-
/*
* allocate vm_page structures.
*/
@@ -742,97 +715,9 @@ uvm_page_physload(paddr_t start, paddr_t end, paddr_t avail_start,
* done!
*/
- if (!preload)
- uvm_page_rehash();
-
- return;
-}
-
-/*
- * uvm_page_rehash: reallocate hash table based on number of free pages.
- */
-
-void
-uvm_page_rehash(void)
-{
- int freepages, lcv, bucketcount, oldcount;
- struct pglist *newbuckets, *oldbuckets;
- struct vm_page *pg;
- size_t newsize, oldsize;
-
- /*
- * compute number of pages that can go in the free pool
- */
-
- freepages = 0;
- for (lcv = 0 ; lcv < vm_nphysseg ; lcv++)
- freepages +=
- (vm_physmem[lcv].avail_end - vm_physmem[lcv].avail_start);
-
- /*
- * compute number of buckets needed for this number of pages
- */
-
- bucketcount = 1;
- while (bucketcount < freepages)
- bucketcount = bucketcount * 2;
-
- /*
- * compute the size of the current table and new table.
- */
-
- oldbuckets = uvm.page_hash;
- oldcount = uvm.page_nhash;
- oldsize = round_page(sizeof(struct pglist) * oldcount);
- newsize = round_page(sizeof(struct pglist) * bucketcount);
-
- /*
- * allocate the new buckets
- */
-
- newbuckets = (struct pglist *) uvm_km_alloc(kernel_map, newsize);
- if (newbuckets == NULL) {
- printf("uvm_page_physrehash: WARNING: could not grow page "
- "hash table\n");
- return;
- }
- for (lcv = 0 ; lcv < bucketcount ; lcv++)
- TAILQ_INIT(&newbuckets[lcv]);
-
- /*
- * now replace the old buckets with the new ones and rehash everything
- */
-
- mtx_enter(&uvm.hashlock);
- uvm.page_hash = newbuckets;
- uvm.page_nhash = bucketcount;
- uvm.page_hashmask = bucketcount - 1; /* power of 2 */
-
- /* ... and rehash */
- for (lcv = 0 ; lcv < oldcount ; lcv++) {
- while ((pg = TAILQ_FIRST(&oldbuckets[lcv])) != NULL) {
- TAILQ_REMOVE(&oldbuckets[lcv], pg, hashq);
- TAILQ_INSERT_TAIL(
- &uvm.page_hash[uvm_pagehash(pg->uobject, pg->offset)],
- pg, hashq);
- }
- }
- mtx_leave(&uvm.hashlock);
-
- /*
- * free old bucket array if is not the boot-time table
- */
-
- if (oldbuckets != &uvm_bootbucket)
- uvm_km_free(kernel_map, (vaddr_t) oldbuckets, oldsize);
-
- /*
- * done
- */
return;
}
-
#ifdef DDB /* XXXCDC: TMP TMP TMP DEBUG DEBUG DEBUG */
void uvm_page_physdump(void); /* SHUT UP GCC */
@@ -843,8 +728,8 @@ uvm_page_physdump(void)
{
int lcv;
- printf("rehash: physical memory config [segs=%d of %d]:\n",
- vm_nphysseg, VM_PHYSSEG_MAX);
+ printf("uvm_page_physdump: physical memory config [segs=%d of %d]:\n",
+ vm_nphysseg, VM_PHYSSEG_MAX);
for (lcv = 0 ; lcv < vm_nphysseg ; lcv++)
printf("0x%llx->0x%llx [0x%llx->0x%llx]\n",
(long long)vm_physmem[lcv].start,
@@ -858,7 +743,6 @@ uvm_page_physdump(void)
case VM_PSTRAT_BIGFIRST: printf("BIGFIRST\n"); break;
default: printf("<<UNKNOWN>>!!!!\n");
}
- printf("number of buckets = %d\n", uvm.page_nhash);
}
#endif
@@ -875,7 +759,7 @@ uvm_shutdown(void)
*
* => return null if no pages free
* => wake up pagedaemon if number of free pages drops below low water mark
- * => if obj != NULL, obj must be locked (to put in hash)
+ * => if obj != NULL, obj must be locked (to put in tree)
* => if anon != NULL, anon must be locked (to put in anon)
* => only one of obj or anon can be non-null
* => caller must activate/deactivate page if it is not wired.
@@ -1090,7 +974,7 @@ uvm_pagerealloc(struct vm_page *pg, struct uvm_object *newobj, voff_t newoff)
/*
* uvm_pagefree: free page
*
- * => erase page's identity (i.e. remove from hash/object)
+ * => erase page's identity (i.e. remove from object)
* => put page on free list
* => caller must lock owning object (either anon or uvm_object)
* => caller must lock page queues
@@ -1475,19 +1359,11 @@ PHYS_TO_VM_PAGE(paddr_t pa)
struct vm_page *
uvm_pagelookup(struct uvm_object *obj, voff_t off)
{
- struct vm_page *pg;
- struct pglist *buck;
-
- mtx_enter(&uvm.hashlock);
- buck = &uvm.page_hash[uvm_pagehash(obj,off)];
+ /* XXX if stack is too much, handroll */
+ struct vm_page pg;
- TAILQ_FOREACH(pg, buck, hashq) {
- if (pg->uobject == obj && pg->offset == off) {
- break;
- }
- }
- mtx_leave(&uvm.hashlock);
- return(pg);
+ pg.offset = off;
+ return (RB_FIND(uvm_objtree, &obj->memt, &pg));
}
/*
diff --git a/sys/uvm/uvm_page.h b/sys/uvm/uvm_page.h
index 366535db35c..531ff9d0fcd 100644
--- a/sys/uvm/uvm_page.h
+++ b/sys/uvm/uvm_page.h
@@ -1,4 +1,4 @@
-/* $OpenBSD: uvm_page.h,v 1.39 2009/06/17 00:13:59 oga Exp $ */
+/* $OpenBSD: uvm_page.h,v 1.40 2009/08/06 15:28:14 oga Exp $ */
/* $NetBSD: uvm_page.h,v 1.19 2000/12/28 08:24:55 chs Exp $ */
/*
@@ -83,16 +83,8 @@
*
* A small structure is kept for each resident
* page, indexed by page number. Each structure
- * is an element of several lists:
- *
- * A hash table bucket used to quickly
- * perform object/offset lookups
- *
- * A list of all pages for a given object,
- * so they can be quickly deactivated at
- * time of deallocation.
- *
- * An ordered list of pages due for pageout.
+ * contains a list used for manipulating pages, and
+ * a tree structure for in object/offset lookups
*
* In addition, the structure contains the object
* and offset to which this page belongs (for pageout),
@@ -109,8 +101,7 @@
struct vm_page {
TAILQ_ENTRY(vm_page) pageq; /* queue info for FIFO
* queue or free list (P) */
- TAILQ_ENTRY(vm_page) hashq; /* hash table links (O)*/
- TAILQ_ENTRY(vm_page) listq; /* pages in same object (O)*/
+ RB_ENTRY(vm_page) objt; /* object tree (O)*/
struct vm_anon *uanon; /* anon (O,P) */
struct uvm_object *uobject; /* object (O,P) */
@@ -242,7 +233,6 @@ void uvm_page_own(struct vm_page *, char *);
#if !defined(PMAP_STEAL_MEMORY)
boolean_t uvm_page_physget(paddr_t *);
#endif
-void uvm_page_rehash(void);
void uvm_pageidlezero(void);
void uvm_pageactivate(struct vm_page *);
@@ -309,9 +299,6 @@ int vm_physseg_find(paddr_t, int *);
#define uvm_lock_fpageq() mtx_enter(&uvm.fpageqlock);
#define uvm_unlock_fpageq() mtx_leave(&uvm.fpageqlock);
-#define uvm_pagehash(obj,off) \
- (((unsigned long)obj+(unsigned long)atop(off)) & uvm.page_hashmask)
-
#define UVM_PAGEZERO_TARGET (uvmexp.free)
#define VM_PAGE_TO_PHYS(entry) ((entry)->phys_addr)
diff --git a/sys/uvm/uvm_vnode.c b/sys/uvm/uvm_vnode.c
index 15130e95ded..207237eb3a4 100644
--- a/sys/uvm/uvm_vnode.c
+++ b/sys/uvm/uvm_vnode.c
@@ -1,4 +1,4 @@
-/* $OpenBSD: uvm_vnode.c,v 1.68 2009/07/22 21:05:37 oga Exp $ */
+/* $OpenBSD: uvm_vnode.c,v 1.69 2009/08/06 15:28:14 oga Exp $ */
/* $NetBSD: uvm_vnode.c,v 1.36 2000/11/24 20:34:01 chs Exp $ */
/*
@@ -271,7 +271,7 @@ uvn_attach(void *arg, vm_prot_t accessprot)
* now set up the uvn.
*/
uvn->u_obj.pgops = &uvm_vnodeops;
- TAILQ_INIT(&uvn->u_obj.memq);
+ RB_INIT(&uvn->u_obj.memt);
uvn->u_obj.uo_npages = 0;
uvn->u_obj.uo_refs = 1; /* just us... */
oldflags = uvn->u_flags;
@@ -438,11 +438,7 @@ uvn_detach(struct uvm_object *uobj)
if (uvn->u_flags & UVM_VNODE_WRITEABLE) {
LIST_REMOVE(uvn, u_wlist);
}
-#ifdef DIAGNOSTIC
- if (!TAILQ_EMPTY(&uobj->memq))
- panic("uvn_deref: vnode VM object still has pages afer "
- "syncio/free flush");
-#endif
+ KASSERT(RB_EMPTY(&uobj->memt));
oldflags = uvn->u_flags;
uvn->u_flags = 0;
simple_unlock(&uobj->vmobjlock);
@@ -559,7 +555,7 @@ uvm_vnp_terminate(struct vnode *vp)
while (uvn->u_obj.uo_npages) {
#ifdef DEBUG
struct vm_page *pp;
- TAILQ_FOREACH(pp, &uvn->u_obj.memq, listq) {
+ RB_FOREACH(pp, uvm_objtree, &uvn->u_obj.memt) {
if ((pp->pg_flags & PG_BUSY) == 0)
panic("uvm_vnp_terminate: detected unbusy pg");
}
@@ -669,11 +665,6 @@ uvm_vnp_terminate(struct vnode *vp)
* or block.
* => if PGO_ALLPAGE is set, then all pages in the object are valid targets
* for flushing.
- * => NOTE: we rely on the fact that the object's memq is a TAILQ and
- * that new pages are inserted on the tail end of the list. thus,
- * we can make a complete pass through the object in one go by starting
- * at the head and working towards the tail (new pages are put in
- * front of us).
* => NOTE: we are allowed to lock the page queues, so the caller
* must not be holding the lock on them [e.g. pagedaemon had
* better not call us with the queues locked]
@@ -692,19 +683,6 @@ uvm_vnp_terminate(struct vnode *vp)
* object we need to wait for the other PG_BUSY pages to clear
* off (i.e. we need to do an iosync). also note that once a
* page is PG_BUSY it must stay in its object until it is un-busyed.
- *
- * note on page traversal:
- * we can traverse the pages in an object either by going down the
- * linked list in "uobj->memq", or we can go over the address range
- * by page doing hash table lookups for each address. depending
- * on how many pages are in the object it may be cheaper to do one
- * or the other. we set "by_list" to true if we are using memq.
- * if the cost of a hash lookup was equal to the cost of the list
- * traversal we could compare the number of pages in the start->stop
- * range to the total number of pages in the object. however, it
- * seems that a hash table lookup is more expensive than the linked
- * list traversal, so we multiply the number of pages in the
- * start->stop range by a penalty which we define below.
*/
#define UVN_HASH_PENALTY 4 /* XXX: a guess */
generated by cgit v1.2.3 (git 2.25.1) at 2024-12-01 01:00:37 +0000