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.

4 files changed, 19 insertions, 20 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);