Skip site navigation (1)Skip section navigation (2) 
Date:      Thu, 1 Aug 2019 03:55:59 +0000 (UTC)
From:      Justin Hibbits <jhibbits@FreeBSD.org>
To:        src-committers@freebsd.org, svn-src-all@freebsd.org, svn-src-head@freebsd.org
Subject:   svn commit: r350493 - in head/sys/powerpc: aim include
Message-ID:  <201908010355.x713txpp062924@repo.freebsd.org>
next in thread | raw e-mail | index | archive | help 
Author: jhibbits
Date: Thu Aug  1 03:55:58 2019
New Revision: 350493
URL: https://svnweb.freebsd.org/changeset/base/350493

Log:
  powerpc64/mmu: Use a SLIST for the PVO delete list, instead of a RB_TREE
  
  Summary:
  Although it's convenient to reuse the pvo_plist for deletion, RB_TREE
  insertion and removal is not free, and can result in a lot of extra work
  to rebalance the tree.  Instead, use a SLIST as a LIFO delete queue,
  which gives us almost free insertion, deletion, and traversal.
  
  Reviewed by:	luporl
  Differential Revision: https://reviews.freebsd.org/D21061

Modified:
  head/sys/powerpc/aim/mmu_oea64.c
  head/sys/powerpc/include/pmap.h

Modified: head/sys/powerpc/aim/mmu_oea64.c
==============================================================================
--- head/sys/powerpc/aim/mmu_oea64.c	Thu Aug  1 02:16:48 2019	(r350492)
+++ head/sys/powerpc/aim/mmu_oea64.c	Thu Aug  1 03:55:58 2019	(r350493)
@@ -2364,9 +2364,9 @@ void
 moea64_remove_pages(mmu_t mmu, pmap_t pm)
 {
 	struct pvo_entry *pvo, *tpvo;
-	struct pvo_tree tofree;
+	struct pvo_dlist tofree;
 
-	RB_INIT(&tofree);
+	SLIST_INIT(&tofree);
 
 	PMAP_LOCK(pm);
 	RB_FOREACH_SAFE(pvo, pvo_tree, &pm->pmap_pvo, tpvo) {
@@ -2379,13 +2379,14 @@ moea64_remove_pages(mmu_t mmu, pmap_t pm)
 		 * pass
 		 */
 		moea64_pvo_remove_from_pmap(mmu, pvo);
-		RB_INSERT(pvo_tree, &tofree, pvo);
+		SLIST_INSERT_HEAD(&tofree, pvo, pvo_dlink);
 	}
 	PMAP_UNLOCK(pm);
 
-	RB_FOREACH_SAFE(pvo, pvo_tree, &tofree, tpvo) {
+	while (!SLIST_EMPTY(&tofree)) {
+		pvo = SLIST_FIRST(&tofree);
+		SLIST_REMOVE_HEAD(&tofree, pvo_dlink);
 		moea64_pvo_remove_from_page(mmu, pvo);
-		RB_REMOVE(pvo_tree, &tofree, pvo);
 		free_pvo_entry(pvo);
 	}
 }
@@ -2397,7 +2398,7 @@ void
 moea64_remove(mmu_t mmu, pmap_t pm, vm_offset_t sva, vm_offset_t eva)
 {
 	struct  pvo_entry *pvo, *tpvo, key;
-	struct pvo_tree tofree;
+	struct pvo_dlist tofree;
 
 	/*
 	 * Perform an unsynchronized read.  This is, however, safe.
@@ -2407,7 +2408,7 @@ moea64_remove(mmu_t mmu, pmap_t pm, vm_offset_t sva, v
 
 	key.pvo_vaddr = sva;
 
-	RB_INIT(&tofree);
+	SLIST_INIT(&tofree);
 
 	PMAP_LOCK(pm);
 	for (pvo = RB_NFIND(pvo_tree, &pm->pmap_pvo, &key);
@@ -2420,13 +2421,14 @@ moea64_remove(mmu_t mmu, pmap_t pm, vm_offset_t sva, v
 		 * pass
 		 */
 		moea64_pvo_remove_from_pmap(mmu, pvo);
-		RB_INSERT(pvo_tree, &tofree, pvo);
+		SLIST_INSERT_HEAD(&tofree, pvo, pvo_dlink);
 	}
 	PMAP_UNLOCK(pm);
 
-	RB_FOREACH_SAFE(pvo, pvo_tree, &tofree, tpvo) {
+	while (!SLIST_EMPTY(&tofree)) {
+		pvo = SLIST_FIRST(&tofree);
+		SLIST_REMOVE_HEAD(&tofree, pvo_dlink);
 		moea64_pvo_remove_from_page(mmu, pvo);
-		RB_REMOVE(pvo_tree, &tofree, pvo);
 		free_pvo_entry(pvo);
 	}
 }

Modified: head/sys/powerpc/include/pmap.h
==============================================================================
--- head/sys/powerpc/include/pmap.h	Thu Aug  1 02:16:48 2019	(r350492)
+++ head/sys/powerpc/include/pmap.h	Thu Aug  1 03:55:58 2019	(r350493)
@@ -90,7 +90,10 @@ struct pvo_entry {
 #ifndef __powerpc64__
 	LIST_ENTRY(pvo_entry) pvo_olink;	/* Link to overflow entry */
 #endif
-	RB_ENTRY(pvo_entry) pvo_plink;	/* Link to pmap entries */
+	union {
+		RB_ENTRY(pvo_entry) pvo_plink;	/* Link to pmap entries */
+		SLIST_ENTRY(pvo_entry) pvo_dlink; /* Link to delete enty */
+	};
 	struct {
 #ifndef __powerpc64__
 		/* 32-bit fields */
@@ -106,6 +109,7 @@ struct pvo_entry {
 	uint64_t	pvo_vpn;		/* Virtual page number */
 };
 LIST_HEAD(pvo_head, pvo_entry);
+SLIST_HEAD(pvo_dlist, pvo_entry);
 RB_HEAD(pvo_tree, pvo_entry);
 int pvo_vaddr_compare(struct pvo_entry *, struct pvo_entry *);
 RB_PROTOTYPE(pvo_tree, pvo_entry, pvo_plink, pvo_vaddr_compare);

Want to link to this message? Use this URL: <https://mail-archive.FreeBSD.org/cgi/mid.cgi?201908010355.x713txpp062924>