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.

2 files changed, 9 insertions, 10 deletions

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);