From 9656b08bd5c766c36ce3a83acc1d09ff97d7b06b Mon Sep 17 00:00:00 2001
From: dlg <dlg@openbsd.org>
Date: Thu, 11 Aug 2016 01:17:33 +0000
Subject: [PATCH] replace abuse of the static map entries RB_ENTRY pointers
 with an SLIST

free static entries are kept in a simple linked list, so use SLIST
to make this obvious. the RB_PARENT manipulations are ugly and
confusing.

ok kettenis@
---
 sys/uvm/uvm.h     |  4 ++--
 sys/uvm/uvm_map.c | 28 ++++++++++++----------------
 sys/uvm/uvm_map.h |  3 ++-
 3 files changed, 16 insertions(+), 19 deletions(-)

diff --git a/sys/uvm/uvm.h b/sys/uvm/uvm.h
index 5a6082d35db..3f08fd19a1f 100644
--- a/sys/uvm/uvm.h
+++ b/sys/uvm/uvm.h
@@ -1,4 +1,4 @@
-/*	$OpenBSD: uvm.h,v 1.60 2015/10/08 15:58:38 kettenis Exp $	*/
+/*	$OpenBSD: uvm.h,v 1.61 2016/08/11 01:17:33 dlg Exp $	*/
 /*	$NetBSD: uvm.h,v 1.24 2000/11/27 08:40:02 chs Exp $	*/
 
 /*
@@ -69,7 +69,7 @@ struct uvm {
 	struct mutex aiodoned_lock;
 
 	/* static kernel map entry pool */
-	vm_map_entry_t kentry_free;	/* free page pool */
+	SLIST_HEAD(, vm_map_entry) kentry_free; /* free page pool */
 
 	/* aio_done is locked by uvm.aiodoned_lock. */
 	TAILQ_HEAD(, buf) aio_done;		/* done async i/o reqs */
diff --git a/sys/uvm/uvm_map.c b/sys/uvm/uvm_map.c
index 41e63bddb96..afef0ba38cd 100644
--- a/sys/uvm/uvm_map.c
+++ b/sys/uvm/uvm_map.c
@@ -1,4 +1,4 @@
-/*	$OpenBSD: uvm_map.c,v 1.219 2016/07/30 16:43:44 kettenis Exp $	*/
+/*	$OpenBSD: uvm_map.c,v 1.220 2016/08/11 01:17:33 dlg Exp $	*/
 /*	$NetBSD: uvm_map.c,v 1.86 2000/11/27 08:40:03 chs Exp $	*/
 
 /*
@@ -1669,25 +1669,23 @@ uvm_mapent_alloc(struct vm_map *map, int flags)
 
 	if (map->flags & VM_MAP_INTRSAFE || cold) {
 		mtx_enter(&uvm_kmapent_mtx);
-		me = uvm.kentry_free;
-		if (me == NULL) {
+		if (SLIST_EMPTY(&uvm.kentry_free)) {
 			ne = km_alloc(PAGE_SIZE, &kv_page, &kp_dirty,
 			    &kd_nowait);
 			if (ne == NULL)
 				panic("uvm_mapent_alloc: cannot allocate map "
 				    "entry");
-			for (i = 0;
-			    i < PAGE_SIZE / sizeof(struct vm_map_entry) - 1;
-			    i++)
-				RB_LEFT(&ne[i], daddrs.addr_entry) = &ne[i + 1];
-			RB_LEFT(&ne[i], daddrs.addr_entry) = NULL;
-			me = ne;
+			for (i = 0; i < PAGE_SIZE / sizeof(*ne); i++) {
+				SLIST_INSERT_HEAD(&uvm.kentry_free,
+				    &ne[i], daddrs.addr_kentry);
+			}
 			if (ratecheck(&uvm_kmapent_last_warn_time,
 			    &uvm_kmapent_warn_rate))
 				printf("uvm_mapent_alloc: out of static "
 				    "map entries\n");
 		}
-		uvm.kentry_free = RB_LEFT(me, daddrs.addr_entry);
+		me = SLIST_FIRST(&uvm.kentry_free);
+		SLIST_REMOVE_HEAD(&uvm.kentry_free, daddrs.addr_kentry);
 		uvmexp.kmapent++;
 		mtx_leave(&uvm_kmapent_mtx);
 		me->flags = UVM_MAP_STATIC;
@@ -1725,8 +1723,7 @@ uvm_mapent_free(struct vm_map_entry *me)
 {
 	if (me->flags & UVM_MAP_STATIC) {
 		mtx_enter(&uvm_kmapent_mtx);
-		RB_LEFT(me, daddrs.addr_entry) = uvm.kentry_free;
-		uvm.kentry_free = me;
+		SLIST_INSERT_HEAD(&uvm.kentry_free, me, daddrs.addr_kentry);
 		uvmexp.kmapent--;
 		mtx_leave(&uvm_kmapent_mtx);
 	} else if (me->flags & UVM_MAP_KMEM) {
@@ -2795,11 +2792,10 @@ uvm_map_init(void)
 
 	/* now set up static pool of kernel map entries ... */
 	mtx_init(&uvm_kmapent_mtx, IPL_VM);
-	uvm.kentry_free = NULL;
+	SLIST_INIT(&uvm.kentry_free);
 	for (lcv = 0 ; lcv < MAX_KMAPENT ; lcv++) {
-		RB_LEFT(&kernel_map_entry[lcv], daddrs.addr_entry) =
-		    uvm.kentry_free;
-		uvm.kentry_free = &kernel_map_entry[lcv];
+		SLIST_INSERT_HEAD(&uvm.kentry_free,
+		    &kernel_map_entry[lcv], daddrs.addr_kentry);
 	}
 
 	/* initialize the map-related pools. */
diff --git a/sys/uvm/uvm_map.h b/sys/uvm/uvm_map.h
index 38604b577d6..103e5e4f40b 100644
--- a/sys/uvm/uvm_map.h
+++ b/sys/uvm/uvm_map.h
@@ -1,4 +1,4 @@
-/*	$OpenBSD: uvm_map.h,v 1.55 2015/09/09 23:33:37 kettenis Exp $	*/
+/*	$OpenBSD: uvm_map.h,v 1.56 2016/08/11 01:17:33 dlg Exp $	*/
 /*	$NetBSD: uvm_map.h,v 1.24 2001/02/18 21:19:08 chs Exp $	*/
 
 /*
@@ -161,6 +161,7 @@ union vm_map_object {
 struct vm_map_entry {
 	union {
 		RB_ENTRY(vm_map_entry)	addr_entry; /* address tree */
+		SLIST_ENTRY(vm_map_entry) addr_kentry;
 	} daddrs;
 
 	union {
-- 
2.20.1