mach-defpager: replace the magic typecast with a hash table

Previously, the mach-defpager used a "magic typecast" for object
lookups.  It renamed the port to the address of the associated object,
and upon receiving a message it would cast the port name back to a
pointer.

While this might seem like an optimization, it actually makes the port
handling in the kernel less efficient.  Ports with small continuous
names are stored in an array, while other ports get spilled in a splay
tree.

Replace the linked list of default_port_t objects with a hash table.
Do not rename the ports, rather use the hash table to lookup objects
associated with ports.

* mach-defpager/default_pager.c (struct pager_port): Replace queue
with hash table, remove count, move type declaration to priv.h.
(pager_port_list_init): Adjust accordingly.
(pager_port_list_insert): Likewise.
(pager_port_list_delete): Likewise.
(destroy_paging_partition): Replace queue_iterate with HURD_IHASH_ITERATE.
(S_default_pager_objects): Likewise.
(S_default_pager_object_pages): Likewise.
(seqnos_memory_object_create): Do not rename the port but store it in
the hash table.
(S_default_pager_object_create): Likewise.
* mach-defpager/priv.h (struct dstruct): Add fast-removal pointer.
(pnameof): Remove obsolete macro definition.
(dnameof): Likewise.
* mach-defpager/mig-decls.h (begin_using_default_pager): Replace the
magic typecast with a hash table lookup.
* mach-defpager/Makefile (HURDLIBS): Add ihash.

4 files changed, 45 insertions, 67 deletions

diff --git a/mach-defpager/Makefile b/mach-defpager/Makefile
index c8e33c52..09debeda 100644
--- a/mach-defpager/Makefile
+++ b/mach-defpager/Makefile
@@ -29,6 +29,7 @@ OBJS 	:= $(SRCS:.c=.o) \
 		       memory_object default_pager memory_object_default exc) \
 	   default_pager_replyUser.o
 
+HURDLIBS:= ihash
 OTHERLIBS:= -lpthread
 LDFLAGS += -static
 
diff --git a/mach-defpager/default_pager.c b/mach-defpager/default_pager.c
index eb444a6b..f514ea6b 100644
--- a/mach-defpager/default_pager.c
+++ b/mach-defpager/default_pager.c
@@ -38,10 +38,13 @@
 #include <mach/default_pager_types.h>
 
 #include <pthread.h>
+#include <stddef.h>
 
 #include <device/device_types.h>
 #include <device/device.h>
 
+#include <hurd/ihash.h>
+
 #include "queue.h"
 #include "wiring.h"
 #include "kalloc.h"
@@ -1781,25 +1784,14 @@ default_has_page(ds, offset)
 #define	dstruct_unlock(ds)
 #endif	/* PARALLEL */
 
-/*
- * List of all pagers.  A specific pager is
- * found directly via its port, this list is
- * only used for monitoring purposes by the
- * default_pager_object* calls
- */
-struct pager_port {
-	queue_head_t	queue;
-	pthread_mutex_t	lock;
-	int		count;	/* saves code */
-	queue_head_t	leak_queue;
-} all_pagers;
+struct pager_port all_pagers;
 
 #define pager_port_list_init()					\
 {								\
 	pthread_mutex_init(&all_pagers.lock, NULL);		\
-	queue_init(&all_pagers.queue);				\
+	hurd_ihash_init (&all_pagers.htable,			\
+			 offsetof (struct dstruct, htable_locp)); \
 	queue_init(&all_pagers.leak_queue);			\
-	all_pagers.count = 0;					\
 }
 
 void pager_port_list_insert(port, ds)
@@ -1807,8 +1799,9 @@ void pager_port_list_insert(port, ds)
 	default_pager_t	ds;
 {
 	pthread_mutex_lock(&all_pagers.lock);
-	queue_enter(&all_pagers.queue, ds, default_pager_t, links);
-	all_pagers.count++;
+	hurd_ihash_add (&all_pagers.htable,
+			(hurd_ihash_key_t) port,
+			(hurd_ihash_value_t) ds);
 	pthread_mutex_unlock(&all_pagers.lock);
 }
 
@@ -1816,8 +1809,8 @@ void pager_port_list_delete(ds)
 	default_pager_t ds;
 {
 	pthread_mutex_lock(&all_pagers.lock);
-	queue_remove(&all_pagers.queue, ds, default_pager_t, links);
-	all_pagers.count--;
+	hurd_ihash_locp_remove (&all_pagers.htable,
+				ds->htable_locp);
 	pthread_mutex_unlock(&all_pagers.lock);
 }
 
@@ -1864,7 +1857,8 @@ dprintf("Partition x%x (id x%x) for %s, all_ok %d\n", part, id, name, all_ok);
 	pthread_mutex_lock(&part->p_lock);
 
 	pthread_mutex_lock(&all_pagers.lock);
-	queue_iterate(&all_pagers.queue, entry, default_pager_t, links) {
+	HURD_IHASH_ITERATE (&all_pagers.htable, val) {
+		entry = (default_pager_t) val;
 
 		dstruct_lock(entry);
 
@@ -2238,7 +2232,6 @@ seqnos_memory_object_create(old_pager, seqno, new_pager, new_size,
 	vm_size_t	new_page_size;
 {
 	default_pager_t	ds;
-	kern_return_t			kr;
 
 	assert(old_pager == default_pager_default_port);
 	assert(MACH_PORT_VALID(new_pager_request));
@@ -2246,24 +2239,6 @@ seqnos_memory_object_create(old_pager, seqno, new_pager, new_size,
 	assert(new_page_size == vm_page_size);
 
 	ds = pager_port_alloc(new_size);
-rename_it:
-	kr = mach_port_rename(	default_pager_self,
-				new_pager, (mach_port_t)pnameof(ds));
-	if (kr != KERN_SUCCESS) {
-		default_pager_t	ds1;
-
-		if (kr != KERN_NAME_EXISTS)
-			panic("%s m_o_create", my_name);
-		ds1 = (default_pager_t) kalloc(sizeof *ds1);
-		*ds1 = *ds;
-		pthread_mutex_lock(&all_pagers.lock);
-		queue_enter(&all_pagers.leak_queue, ds, default_pager_t, links);
-		pthread_mutex_unlock(&all_pagers.lock);
-		ds = ds1;
-		goto rename_it;
-	}
-
-	new_pager = (mach_port_t) pnameof(ds);
 
 	/*
 	 *	Set up associations between these ports
@@ -3195,23 +3170,14 @@ S_default_pager_object_create (mach_port_t pager,
 		return KERN_INVALID_ARGUMENT;
 
 	ds = pager_port_alloc(size);
-rename_it:
-	port = (mach_port_t) pnameof(ds);
-	result = mach_port_allocate_name(default_pager_self,
-				    MACH_PORT_RIGHT_RECEIVE, port);
-	if (result != KERN_SUCCESS) {
-		default_pager_t	ds1;
-
-		if (result != KERN_NAME_EXISTS) return (result);
-
-		ds1 = (default_pager_t) kalloc(sizeof *ds1);
-		*ds1 = *ds;
-		pthread_mutex_lock(&all_pagers.lock);
-		queue_enter(&all_pagers.leak_queue, ds, default_pager_t, links);
-		pthread_mutex_unlock(&all_pagers.lock);
-		ds = ds1;
-		goto rename_it;
-	}
+	result = mach_port_allocate (default_pager_self,
+				     MACH_PORT_RIGHT_RECEIVE,
+				     &port);
+	if (result != KERN_SUCCESS)
+	  {
+	    kfree ((char *) ds, sizeof *ds);
+	    return result;
+	  }
 
 	/*
 	 *	Set up associations between these ports
@@ -3285,7 +3251,7 @@ S_default_pager_objects (mach_port_t pager,
 	/*
 	 * We will send no more than this many
 	 */
-	actual = all_pagers.count;
+	actual = all_pagers.htable.nr_items;
 	pthread_mutex_unlock(&all_pagers.lock);
 
 	if (opotential < actual) {
@@ -3327,7 +3293,8 @@ S_default_pager_objects (mach_port_t pager,
 	pthread_mutex_lock(&all_pagers.lock);
 
 	num_pagers = 0;
-	queue_iterate(&all_pagers.queue, entry, default_pager_t, links) {
+	HURD_IHASH_ITERATE (&all_pagers.htable, val) {
+		entry = (default_pager_t) val;
 
 		mach_port_t		port;
 		vm_size_t		size;
@@ -3505,7 +3472,8 @@ S_default_pager_object_pages (mach_port_t pager,
 		default_pager_t		entry;
 
 		pthread_mutex_lock(&all_pagers.lock);
-		queue_iterate(&all_pagers.queue, entry, default_pager_t, links) {
+		HURD_IHASH_ITERATE (&all_pagers.htable, val) {
+			entry = (default_pager_t) val;
 			dstruct_lock(entry);
 			if (entry->pager_name == object) {
 				pthread_mutex_unlock(&all_pagers.lock);
diff --git a/mach-defpager/mig-decls.h b/mach-defpager/mig-decls.h
index f63fef20..8118d61a 100644
--- a/mach-defpager/mig-decls.h
+++ b/mach-defpager/mig-decls.h
@@ -27,11 +27,8 @@
 static inline struct dstruct * __attribute__ ((unused))
 begin_using_default_pager (mach_port_t port)
 {
-  if (! MACH_PORT_VALID(port)
-      || ((default_pager_t) dnameof(port))->pager != (port))
-    return DEFAULT_PAGER_NULL;
-
-  return (default_pager_t) dnameof(port);
+  return (default_pager_t) hurd_ihash_find (&all_pagers.htable,
+                                            (hurd_ihash_key_t) port);
 }
 
 #endif /* __MACH_DEFPAGER_MIG_DECLS_H__ */
diff --git a/mach-defpager/priv.h b/mach-defpager/priv.h
index 20711b2c..36845657 100644
--- a/mach-defpager/priv.h
+++ b/mach-defpager/priv.h
@@ -29,6 +29,7 @@
 
 #include <mach.h>
 #include <queue.h>
+#include <hurd/ihash.h>
 
 /*
  * Bitmap allocation.
@@ -150,6 +151,7 @@ typedef struct dpager	*dpager_t;
  * Mapping between pager port and paging object.
  */
 struct dstruct {
+	hurd_ihash_locp_t htable_locp;	/* for the ihash table */
 	queue_chain_t	links;		/* Link in pager-port list */
 
 	pthread_mutex_t	lock;		/* Lock for the structure */
@@ -180,9 +182,19 @@ struct dstruct {
 typedef struct dstruct *	default_pager_t;
 #define	DEFAULT_PAGER_NULL	((default_pager_t)0)
 
-/* given a data structure return a good port-name to associate it to */
-#define	pnameof(_x_)	(((vm_offset_t) (_x_)) + 1)
-/* reverse, assumes no-odd-pointers */
-#define	dnameof(_x_)	(((vm_offset_t) (_x_)) & ~1)
+/*
+ * List of all pagers.  A specific pager is
+ * found directly via its port, this list is
+ * only used for monitoring purposes by the
+ * default_pager_object* calls
+ */
+struct pager_port {
+	struct hurd_ihash	htable;
+	pthread_mutex_t	lock;
+	queue_head_t	leak_queue;
+};
+
+/* The list of pagers.  */
+extern struct pager_port all_pagers;
 
 #endif /* __MACH_DEFPAGER_PRIV_H__ */