From 6e1481035fcdd30fd7cc0e2650ad2e51cabb8d9d Mon Sep 17 00:00:00 2001
From: Owain Ainsworth <oga@cvs.openbsd.org>
Date: Tue, 2 Jun 2009 23:00:20 +0000
Subject: Instead of the global hash table with the terrible hashfunction and a
 global lock, switch the uvm object pages to being kept in a per-object
 RB_TREE. Right now this is approximately the same speed, but cleaner. When
 biglock usage is reduced this will improve concurrency due to lock
 contention..

ok beck@ art@. Thanks to jasper for the speed testing.
---
 sys/arch/amd64/amd64/pmap.c |  10 +--
 sys/arch/hppa/hppa/pmap.c   |  10 +--
 sys/arch/i386/i386/pmap.c   |  11 ++-
 sys/arch/i386/i386/pmapae.c |   8 +--
 sys/kern/vfs_biomem.c       |   4 +-
 sys/uvm/uvm.h               |   8 +--
 sys/uvm/uvm_aobj.c          |   6 +-
 sys/uvm/uvm_device.c        |   6 +-
 sys/uvm/uvm_init.c          |   3 +-
 sys/uvm/uvm_map.c           |  10 ++-
 sys/uvm/uvm_object.h        |  14 ++--
 sys/uvm/uvm_page.c          | 162 +++++---------------------------------------
 sys/uvm/uvm_page.h          |   6 +-
 sys/uvm/uvm_vnode.c         |  12 ++--
 14 files changed, 64 insertions(+), 206 deletions(-)

diff --git a/sys/arch/amd64/amd64/pmap.c b/sys/arch/amd64/amd64/pmap.c
index fb46e417f84..747f1820a79 100644
--- a/sys/arch/amd64/amd64/pmap.c
+++ b/sys/arch/amd64/amd64/pmap.c
@@ -1,4 +1,4 @@
-/*	$OpenBSD: pmap.c,v 1.43 2009/06/01 17:42:33 ariane Exp $	*/
+/*	$OpenBSD: pmap.c,v 1.44 2009/06/02 23:00:18 oga Exp $	*/
 /*	$NetBSD: pmap.c,v 1.3 2003/05/08 18:13:13 thorpej Exp $	*/
 
 /*
@@ -566,7 +566,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;
@@ -831,7 +831,7 @@ 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, fq.queues.listq);
@@ -1018,7 +1018,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;
@@ -1092,7 +1092,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;
diff --git a/sys/arch/hppa/hppa/pmap.c b/sys/arch/hppa/hppa/pmap.c
index 03a83de24d6..e6f4229fdac 100644
--- a/sys/arch/hppa/hppa/pmap.c
+++ b/sys/arch/hppa/hppa/pmap.c
@@ -1,4 +1,4 @@
-/*	$OpenBSD: pmap.c,v 1.134 2008/10/01 19:13:01 kettenis Exp $	*/
+/*	$OpenBSD: pmap.c,v 1.135 2009/06/02 23:00:18 oga Exp $	*/
 
 /*
  * Copyright (c) 1998-2004 Michael Shalayeff
@@ -232,7 +232,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)
@@ -463,7 +463,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;
@@ -649,7 +649,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;
 
@@ -690,7 +690,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 91fd6edb555..80392600813 100644
--- a/sys/arch/i386/i386/pmap.c
+++ b/sys/arch/i386/i386/pmap.c
@@ -1,4 +1,4 @@
-/*	$OpenBSD: pmap.c,v 1.137 2009/06/01 17:42:33 ariane Exp $	*/
+/*	$OpenBSD: pmap.c,v 1.138 2009/06/02 23:00:19 oga Exp $	*/
 /*	$NetBSD: pmap.c,v 1.91 2000/06/02 17:46:37 thorpej Exp $	*/
 
 /*
@@ -818,7 +818,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 */
@@ -1437,7 +1437,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);
@@ -1474,7 +1474,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;
@@ -1582,8 +1582,7 @@ pmap_release(struct pmap *pmap)
 	 * 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) {
 #ifdef DIAGNOSTIC
 		if (pg->pg_flags & PG_BUSY)
 			panic("pmap_release: busy page table page");
diff --git a/sys/arch/i386/i386/pmapae.c b/sys/arch/i386/i386/pmapae.c
index b13ff7c9463..aeee7c19f66 100644
--- a/sys/arch/i386/i386/pmapae.c
+++ b/sys/arch/i386/i386/pmapae.c
@@ -1,4 +1,4 @@
-/*	$OpenBSD: pmapae.c,v 1.16 2009/06/01 17:42:33 ariane Exp $	*/
+/*	$OpenBSD: pmapae.c,v 1.17 2009/06/02 23:00:19 oga Exp $	*/
 
 /*
  * Copyright (c) 2006 Michael Shalayeff
@@ -1449,7 +1449,7 @@ 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);
@@ -1543,7 +1543,7 @@ 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);
@@ -1661,7 +1661,7 @@ 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);
diff --git a/sys/kern/vfs_biomem.c b/sys/kern/vfs_biomem.c
index 708c06f4d61..2aa8ac9ee51 100644
--- a/sys/kern/vfs_biomem.c
+++ b/sys/kern/vfs_biomem.c
@@ -1,4 +1,4 @@
-/*	$OpenBSD: vfs_biomem.c,v 1.5 2009/04/22 13:12:26 art Exp $ */
+/*	$OpenBSD: vfs_biomem.c,v 1.6 2009/06/02 23:00:19 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.h b/sys/uvm/uvm.h
index 087add79376..cc29e56497e 100644
--- a/sys/uvm/uvm.h
+++ b/sys/uvm/uvm.h
@@ -1,4 +1,4 @@
-/*	$OpenBSD: uvm.h,v 1.33 2009/06/01 17:42:33 ariane Exp $	*/
+/*	$OpenBSD: uvm.h,v 1.34 2009/06/02 23:00:19 oga Exp $	*/
 /*	$NetBSD: uvm.h,v 1.24 2000/11/27 08:40:02 chs Exp $	*/
 
 /*
@@ -121,12 +121,6 @@ struct uvm {
 	struct proc *aiodoned_proc;
 	struct mutex aiodoned_lock;
 
-		/* page hash */
-	struct pglist *page_hash;	/* page hash table (vp/off->page) */
-	int page_nhash;			/* number of buckets */
-	int page_hashmask;		/* hash mask */
-	struct mutex hashlock;		/* lock on page_hash array */
-
 	/* static kernel map entry pool */
 	vm_map_entry_t kentry_free;	/* free page pool */
 	simple_lock_data_t kentry_lock;
diff --git a/sys/uvm/uvm_aobj.c b/sys/uvm/uvm_aobj.c
index ad2509f3bc2..9726d616819 100644
--- a/sys/uvm/uvm_aobj.c
+++ b/sys/uvm/uvm_aobj.c
@@ -1,4 +1,4 @@
-/*	$OpenBSD: uvm_aobj.c,v 1.40 2009/06/01 19:54:02 oga Exp $	*/
+/*	$OpenBSD: uvm_aobj.c,v 1.41 2009/06/02 23:00:19 oga Exp $	*/
 /*	$NetBSD: uvm_aobj.c,v 1.39 2001/02/18 21:19:08 chs Exp $	*/
 
 /*
@@ -521,7 +521,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;
 
 	/*
@@ -665,7 +665,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();
diff --git a/sys/uvm/uvm_device.c b/sys/uvm/uvm_device.c
index 1013f46d20a..a3743490068 100644
--- a/sys/uvm/uvm_device.c
+++ b/sys/uvm/uvm_device.c
@@ -1,4 +1,4 @@
-/*	$OpenBSD: uvm_device.c,v 1.32 2009/05/12 20:49:56 oga Exp $	*/
+/*	$OpenBSD: uvm_device.c,v 1.33 2009/06/02 23:00:19 oga Exp $	*/
 /*	$NetBSD: uvm_device.c,v 1.30 2000/11/25 06:27:59 chs Exp $	*/
 
 /*
@@ -227,7 +227,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;
@@ -287,7 +287,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 192a781a74f..9d606516ee1 100644
--- a/sys/uvm/uvm_init.c
+++ b/sys/uvm/uvm_init.c
@@ -1,4 +1,4 @@
-/*	$OpenBSD: uvm_init.c,v 1.21 2009/05/02 12:54:42 oga Exp $	*/
+/*	$OpenBSD: uvm_init.c,v 1.22 2009/06/02 23:00:19 oga Exp $	*/
 /*	$NetBSD: uvm_init.c,v 1.14 2000/06/27 17:29:23 mrg Exp $	*/
 
 /*
@@ -148,7 +148,6 @@ uvm_init(void)
 	 * 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 1b6f3262986..13ff91d9c72 100644
--- a/sys/uvm/uvm_map.c
+++ b/sys/uvm/uvm_map.c
@@ -1,4 +1,4 @@
-/*	$OpenBSD: uvm_map.c,v 1.111 2009/06/01 17:42:33 ariane Exp $	*/
+/*	$OpenBSD: uvm_map.c,v 1.112 2009/06/02 23:00:19 oga Exp $	*/
 /*	$NetBSD: uvm_map.c,v 1.86 2000/11/27 08:40:03 chs Exp $	*/
 
 /* 
@@ -3820,9 +3820,8 @@ uvm_object_printit(uobj, full, pr)
 		return;
 	}
 	(*pr)("  PAGES <pg,offset>:\n  ");
-	for (pg = TAILQ_FIRST(&uobj->memq);
-	     pg != NULL;
-	     pg = TAILQ_NEXT(pg, fq.queues.listq), cnt++) {
+	RB_FOREACH(pg, uobj_pgs, &uobj->memt) {
+		cnt++;
 		(*pr)("<%p,0x%llx> ", pg, (long long)pg->offset);
 		if ((cnt % 3) == 2) {
 			(*pr)("\n  ");
@@ -3883,8 +3882,7 @@ uvm_page_printit(pg, full, pr)
 			uobj = pg->uobject;
 			if (uobj) {
 				(*pr)("  checking object list\n");
-				TAILQ_FOREACH(tpg, &uobj->memq,
-				    fq.queues.listq) {
+				RB_FOREACH(pg, uobj_pgs, &uobj->memt) {
 					if (tpg == pg) {
 						break;
 					}
diff --git a/sys/uvm/uvm_object.h b/sys/uvm/uvm_object.h
index 5992700e11d..f5caf2c09c9 100644
--- a/sys/uvm/uvm_object.h
+++ b/sys/uvm/uvm_object.h
@@ -1,4 +1,4 @@
-/*	$OpenBSD: uvm_object.h,v 1.10 2007/04/11 12:10:42 art Exp $	*/
+/*	$OpenBSD: uvm_object.h,v 1.11 2009/06/02 23:00:19 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 memq */
+	struct uvm_pagerops		*pgops;		/* pager ops */
+	RB_HEAD(uobj_pgs, vm_page)	memt;		/* pages in obj */
+	int				uo_npages;	/* # of pages in memq */
+	int				uo_refs;	/* reference count */
 };
 
 /*
@@ -93,6 +93,8 @@ extern struct uvm_pagerops uvm_deviceops;
 	((uobj)->pgops == &uvm_vnodeops &&				\
 	 ((struct vnode *)uobj)->v_flag & VTEXT)
 
+int	uvm_pagecmp(struct vm_page *, struct vm_page *);
+RB_PROTOTYPE(uobj_pgs, vm_page, fq.queues.tree, uvm_pagecmp);
 
 #endif /* _KERNEL */
 
diff --git a/sys/uvm/uvm_page.c b/sys/uvm/uvm_page.c
index 47e7c91582f..76ba5b1fe45 100644
--- a/sys/uvm/uvm_page.c
+++ b/sys/uvm/uvm_page.c
@@ -1,4 +1,4 @@
-/*	$OpenBSD: uvm_page.c,v 1.83 2009/06/02 19:49:08 ariane Exp $	*/
+/*	$OpenBSD: uvm_page.c,v 1.84 2009/06/02 23:00:19 oga Exp $	*/
 /*	$NetBSD: uvm_page.c,v 1.44 2000/11/27 08:40:04 chs Exp $	*/
 
 /* 
@@ -117,14 +117,6 @@ boolean_t vm_page_zero_enable = FALSE;
 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
  */
@@ -142,7 +134,7 @@ 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
@@ -153,23 +145,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, fq.queues.hashq);	/* put in hash */
-	mtx_leave(&uvm.hashlock);
 
-	TAILQ_INSERT_TAIL(&pg->uobject->memq, pg,
-	    fq.queues.listq); /* put in object */
+	RB_INSERT(uobj_pgs, &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
@@ -178,23 +164,11 @@ 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, fq.queues.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, fq.queues.listq);
+	RB_REMOVE(uobj_pgs, &pg->uobject->memt, pg);
 
 	atomic_clearbits_int(&pg->pg_flags, PG_TABLED|PQ_AOBJ);
 	pg->uobject->uo_npages--;
@@ -202,6 +176,14 @@ uvm_pageremove(struct vm_page *pg)
 	pg->pg_version++;
 }
 
+int
+uvm_pagecmp(struct vm_page *a, struct vm_page *b)
+{
+	return (a->offset < b->offset ? -1 : a->offset > b->offset);
+}
+
+RB_GENERATE(uobj_pgs, vm_page, fq.queues.tree, uvm_pagecmp);
+
 /*
  * uvm_page_init: init the page system.   called from uvm_init().
  * 
@@ -234,18 +216,6 @@ uvm_page_init(vaddr_t *kvm_startp, vaddr_t *kvm_endp)
 	mtx_init(&uvm.fpageqlock, IPL_VM);
 	uvm_pmr_init();
 
-	/*
-	 * 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.
 	 */
@@ -743,97 +713,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, fq.queues.hashq);
-			TAILQ_INSERT_TAIL(
-			  &uvm.page_hash[uvm_pagehash(pg->uobject, pg->offset)],
-			  pg, fq.queues.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 */
@@ -859,7 +741,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
 
@@ -1002,7 +883,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
@@ -1400,19 +1281,10 @@ 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)];
+	struct vm_page find;
 
-	TAILQ_FOREACH(pg, buck, fq.queues.hashq) {
-		if (pg->uobject == obj && pg->offset == off) {
-			break;
-		}
-	}
-	mtx_leave(&uvm.hashlock);
-	return(pg);
+	find.offset = off;
+	return (RB_FIND(uobj_pgs, &obj->memt, &find));
 }
 
 /*
diff --git a/sys/uvm/uvm_page.h b/sys/uvm/uvm_page.h
index e7991dce4a0..3e779952495 100644
--- a/sys/uvm/uvm_page.h
+++ b/sys/uvm/uvm_page.h
@@ -1,4 +1,4 @@
-/*	$OpenBSD: uvm_page.h,v 1.33 2009/06/01 17:42:33 ariane Exp $	*/
+/*	$OpenBSD: uvm_page.h,v 1.34 2009/06/02 23:00:19 oga Exp $	*/
 /*	$NetBSD: uvm_page.h,v 1.19 2000/12/28 08:24:55 chs Exp $	*/
 
 /* 
@@ -108,7 +108,7 @@
 
 union vm_page_fq {
 	struct {
-		TAILQ_ENTRY(vm_page)	hashq;	/* hash table links (O)*/
+		RB_ENTRY(vm_page)	tree;	/* hash table links (O)*/
 		TAILQ_ENTRY(vm_page)	listq;	/* pages in same object (O)*/
 	}	queues;
 
@@ -122,7 +122,6 @@ struct vm_page {
 	union vm_page_fq	fq;		/* free and queue management */
 	TAILQ_ENTRY(vm_page)	pageq;		/* queue info for FIFO
 						 * queue or free list (P) */
-
 	struct vm_anon		*uanon;		/* anon (O,P) */
 	struct uvm_object	*uobject;	/* object (O,P) */
 	voff_t			offset;		/* offset into object (O,P) */
@@ -253,7 +252,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 *);
diff --git a/sys/uvm/uvm_vnode.c b/sys/uvm/uvm_vnode.c
index f52f6921336..6ea52aed027 100644
--- a/sys/uvm/uvm_vnode.c
+++ b/sys/uvm/uvm_vnode.c
@@ -1,4 +1,4 @@
-/*	$OpenBSD: uvm_vnode.c,v 1.60 2009/06/01 19:54:02 oga Exp $	*/
+/*	$OpenBSD: uvm_vnode.c,v 1.61 2009/06/02 23:00:19 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, fq.queues.listq) {
+		RB_FOREACH(pp, uobj_pgs, &uvn->u_obj.memt) {
 			if ((pp->pg_flags & PG_BUSY) == 0)
 				panic("uvm_vnp_terminate: detected unbusy pg");
 		}
-- 
cgit v1.2.3