libports: use protected payloads to optimize the object lookup

* NEWS: Mention protected payloads.
* libports/Makefile (SRCS): Add `port-deref-deferred.c'.
* libports/create-internal.c (_ports_create_port_internal): Set the
protected payload to the objects address.
* libports/import-port.c (ports_import_port): Likewise.
* libports/reallocate-from-external.c (ports_reallocate_from_external):
Likewise.
* libports/reallocate-port.c (ports_reallocate_port): Likewise.
* libports/transfer-right.c (ports_transfer_right): Likewise.
* libports/manage-multithread.c (ports_manage_port_operations_multithread):
Use the protected payload for the object lookup if provided.  Add
thread pool management calls.
* libports/manage-one-thread.c (ports_manage_port_operations_one_thread):
Likewise.
* libports/destroy-right.c (ports_destroy_right): Defer the
dereferencing of outstanding send rights to avoid a port_info
use-after-free.
* libports/port-deref-deferred.c: New file.
* libports/port-deref-deferred.h: Likewise.
* libports/ports.h (struct port_bucket): New field `threadpool'.
(ports_lookup_payload): Check `port_right'.

14 files changed, 375 insertions, 20 deletions

diff --git a/libports/Makefile b/libports/Makefile
index f49cb9fd..b8b82eea 100644
--- a/libports/Makefile
+++ b/libports/Makefile
@@ -36,7 +36,7 @@ SRCS = create-bucket.c create-class.c \
  interrupt-operation.c interrupt-on-notify.c interrupt-notified-rpcs.c \
  dead-name.c create-port.c import-port.c default-uninhibitable-rpcs.c \
  claim-right.c transfer-right.c create-port-noinstall.c create-internal.c \
- interrupted.c extern-inline.c
+ interrupted.c extern-inline.c port-deref-deferred.c
 
 installhdrs = ports.h
 
diff --git a/libports/complete-deallocate.c b/libports/complete-deallocate.c
index 0d852f57..e3123b26 100644
--- a/libports/complete-deallocate.c
+++ b/libports/complete-deallocate.c
@@ -27,7 +27,7 @@ _ports_complete_deallocate (struct port_info *pi)
 {
   assert ((pi->flags & PORT_HAS_SENDRIGHTS) == 0);
 
-  if (pi->port_right)
+  if (MACH_PORT_VALID (pi->port_right))
     {
       struct references result;
 
@@ -37,7 +37,9 @@ _ports_complete_deallocate (struct port_info *pi)
         {
           /* A reference was reacquired through a hash table lookup.
              It's fine, we didn't touch anything yet. */
-          pthread_mutex_unlock (&_ports_htable_lock);
+          /* XXX: This really shouldn't happen.  */
+          assert (! "reacquired reference w/o send rights");
+          pthread_rwlock_unlock (&_ports_htable_lock);
           return;
         }
 
diff --git a/libports/create-bucket.c b/libports/create-bucket.c
index 2c5f1b65..82c00a4b 100644
--- a/libports/create-bucket.c
+++ b/libports/create-bucket.c
@@ -48,5 +48,6 @@ ports_create_bucket ()
 
   hurd_ihash_init (&ret->htable, offsetof (struct port_info, hentry));
   ret->rpcs = ret->flags = ret->count = 0;
+  _ports_threadpool_init (&ret->threadpool);
   return ret;
 }
diff --git a/libports/create-internal.c b/libports/create-internal.c
index 2d85931c..d79dc78f 100644
--- a/libports/create-internal.c
+++ b/libports/create-internal.c
@@ -99,7 +99,11 @@ _ports_create_port_internal (struct port_class *class,
   bucket->count++;
   class->count++;
   pthread_mutex_unlock (&_ports_lock);
-  
+
+  /* This is an optimization.  It may fail.  */
+  mach_port_set_protected_payload (mach_task_self (), port,
+				   (unsigned long) pi);
+
   if (install)
     {
       err = mach_port_move_member (mach_task_self (), pi->port_right,
diff --git a/libports/destroy-right.c b/libports/destroy-right.c
index 448b3798..276255f4 100644
--- a/libports/destroy-right.c
+++ b/libports/destroy-right.c
@@ -1,5 +1,5 @@
 /*
-   Copyright (C) 1995, 1996, 1999 Free Software Foundation, Inc.
+   Copyright (C) 1995, 1996, 1999, 2014 Free Software Foundation, Inc.
    Written by Michael I. Bushnell.
 
    This file is part of the GNU Hurd.
@@ -22,30 +22,62 @@
 #include <hurd/ihash.h>
 #include <assert.h>
 
+#include <pthread.h>
+#include <error.h>
+#include <time.h>
+#include <unistd.h>
+
 error_t
 ports_destroy_right (void *portstruct)
 {
   struct port_info *pi = portstruct;
+  mach_port_t port_right;
+  int defer = 0;
   error_t err;
 
-  if (pi->port_right != MACH_PORT_NULL)
+  pthread_mutex_lock (&_ports_lock);
+  port_right = pi->port_right;
+  pi->port_right = MACH_PORT_DEAD;
+
+  if (pi->flags & PORT_HAS_SENDRIGHTS)
+    {
+      pi->flags &= ~PORT_HAS_SENDRIGHTS;
+
+      /* There are outstanding send rights, so we might get more
+         messages.  Attached to the messages is a reference to the
+         port_info object.  Of course we destroyed the receive right
+         these were send to above, but the message could already have
+         been dequeued to userspace.
+
+         Previously, those messages would have carried an stale name,
+         which would have caused a hash table lookup failure.
+         However, stale payloads results in port_info use-after-free.
+         Therefore, we cannot release the reference here, but defer
+         that instead until all currently running threads have gone
+         through a quiescent state.  */
+      defer = 1;
+    }
+
+  if (MACH_PORT_VALID (port_right))
     {
+      mach_port_clear_protected_payload (mach_task_self (), port_right);
+
       pthread_rwlock_wrlock (&_ports_htable_lock);
       hurd_ihash_locp_remove (&_ports_htable, pi->ports_htable_entry);
       hurd_ihash_locp_remove (&pi->bucket->htable, pi->hentry);
       pthread_rwlock_unlock (&_ports_htable_lock);
-      err = mach_port_mod_refs (mach_task_self (), pi->port_right,
-				MACH_PORT_RIGHT_RECEIVE, -1);
-      assert_perror (err);
-
-      pi->port_right = MACH_PORT_NULL;
+    }
+  pthread_mutex_unlock (&_ports_lock);
 
-      if (pi->flags & PORT_HAS_SENDRIGHTS)
-	{
-	  pi->flags &= ~PORT_HAS_SENDRIGHTS;
-	  ports_port_deref (pi);
-	}
+  if (MACH_PORT_VALID (port_right))
+    {
+      err = mach_port_mod_refs (mach_task_self (), port_right,
+                                MACH_PORT_RIGHT_RECEIVE, -1);
+      assert_perror (err);
     }
 
+  if (defer)
+    _ports_port_deref_deferred (pi);
+
   return 0;
 }
diff --git a/libports/import-port.c b/libports/import-port.c
index c337c856..2c638e18 100644
--- a/libports/import-port.c
+++ b/libports/import-port.c
@@ -93,7 +93,11 @@ ports_import_port (struct port_class *class, struct port_bucket *bucket,
   bucket->count++;
   class->count++;
   pthread_mutex_unlock (&_ports_lock);
-  
+
+  /* This is an optimization.  It may fail.  */
+  mach_port_set_protected_payload (mach_task_self (), port,
+				   (unsigned long) pi);
+
   mach_port_move_member (mach_task_self (), port, bucket->portset);
 
   if (stat.mps_srights)
diff --git a/libports/manage-multithread.c b/libports/manage-multithread.c
index 58814d2e..dcb6905d 100644
--- a/libports/manage-multithread.c
+++ b/libports/manage-multithread.c
@@ -167,7 +167,21 @@ ports_manage_port_operations_multithread (struct port_bucket *bucket,
       outp->RetCodeType = RetCodeType;
       outp->RetCode = MIG_BAD_ID;
 
-      pi = ports_lookup_port (bucket, inp->msgh_local_port, 0);
+      if (MACH_MSGH_BITS_LOCAL (inp->msgh_bits) ==
+	  MACH_MSG_TYPE_PROTECTED_PAYLOAD)
+	pi = ports_lookup_payload (bucket, inp->msgh_protected_payload, NULL);
+      else
+	{
+	  pi = ports_lookup_port (bucket, inp->msgh_local_port, 0);
+	  if (pi)
+	    {
+	      inp->msgh_bits = MACH_MSGH_BITS (
+		MACH_MSGH_BITS_REMOTE (inp->msgh_bits),
+		MACH_MSG_TYPE_PROTECTED_PAYLOAD);
+	      inp->msgh_protected_payload = (unsigned long) pi;
+	    }
+	}
+
       if (pi)
 	{
 	  error_t err = ports_begin_rpc (pi, inp->msgh_id, &link);
@@ -203,10 +217,19 @@ ports_manage_port_operations_multithread (struct port_bucket *bucket,
   void *
   thread_function (void *arg)
     {
+      struct ports_thread thread;
       int master = (int) arg;
       int timeout;
       error_t err;
 
+      int synchronized_demuxer (mach_msg_header_t *inp,
+				mach_msg_header_t *outheadp)
+      {
+	int r = internal_demuxer (inp, outheadp);
+	_ports_thread_quiescent (&bucket->threadpool, &thread);
+	return r;
+      }
+
       adjust_priority (__atomic_load_n (&totalthreads, __ATOMIC_RELAXED));
 
       if (hook)
@@ -217,10 +240,13 @@ ports_manage_port_operations_multithread (struct port_bucket *bucket,
       else
 	timeout = thread_timeout;
 
+      _ports_thread_online (&bucket->threadpool, &thread);
+
     startover:
 
       do
-	err = mach_msg_server_timeout (internal_demuxer, 0, bucket->portset,
+	err = mach_msg_server_timeout (synchronized_demuxer,
+				       0, bucket->portset,
 				       timeout ? MACH_RCV_TIMEOUT : 0,
 				       timeout);
       while (err != MACH_RCV_TIMED_OUT);
@@ -240,6 +266,7 @@ ports_manage_port_operations_multithread (struct port_bucket *bucket,
 	    }
 	  __atomic_sub_fetch (&totalthreads, 1, __ATOMIC_RELAXED);
 	}
+      _ports_thread_offline (&bucket->threadpool, &thread);
       return NULL;
     }
 
diff --git a/libports/manage-one-thread.c b/libports/manage-one-thread.c
index cbd2df7d..192907ac 100644
--- a/libports/manage-one-thread.c
+++ b/libports/manage-one-thread.c
@@ -25,6 +25,7 @@ ports_manage_port_operations_one_thread (struct port_bucket *bucket,
 					 ports_demuxer_type demuxer,
 					 int timeout)
 {
+  struct ports_thread thread;
   error_t err;
 
   int 
@@ -57,7 +58,21 @@ ports_manage_port_operations_one_thread (struct port_bucket *bucket,
       outp->RetCodeType = RetCodeType;
       outp->RetCode = MIG_BAD_ID;
 
-      pi = ports_lookup_port (bucket, inp->msgh_local_port, 0);
+      if (MACH_MSGH_BITS_LOCAL (inp->msgh_bits) ==
+	  MACH_MSG_TYPE_PROTECTED_PAYLOAD)
+	pi = ports_lookup_payload (bucket, inp->msgh_protected_payload, NULL);
+      else
+	{
+	  pi = ports_lookup_port (bucket, inp->msgh_local_port, 0);
+	  if (pi)
+	    {
+	      inp->msgh_bits = MACH_MSGH_BITS (
+		MACH_MSGH_BITS_REMOTE (inp->msgh_bits),
+		MACH_MSG_TYPE_PROTECTED_PAYLOAD);
+	      inp->msgh_protected_payload = (unsigned long) pi;
+	    }
+	}
+
       if (pi)
 	{
 	  err = ports_begin_rpc (pi, inp->msgh_id, &link);
@@ -83,6 +98,7 @@ ports_manage_port_operations_one_thread (struct port_bucket *bucket,
 	  status = 1;
 	}
 
+      _ports_thread_quiescent (&bucket->threadpool, &thread);
       return status;
     }
 
@@ -93,8 +109,10 @@ ports_manage_port_operations_one_thread (struct port_bucket *bucket,
      zero.  */
   timeout = 0;
 
+  _ports_thread_online (&bucket->threadpool, &thread);
   do
     err = mach_msg_server_timeout (internal_demuxer, 0, bucket->portset, 
 				   timeout ? MACH_RCV_TIMEOUT : 0, timeout);
   while (err != MACH_RCV_TIMED_OUT);
+  _ports_thread_offline (&bucket->threadpool, &thread);
 }
diff --git a/libports/port-deref-deferred.c b/libports/port-deref-deferred.c
new file mode 100644
index 00000000..2580e913
--- /dev/null
+++ b/libports/port-deref-deferred.c
@@ -0,0 +1,161 @@
+/* Delayed deallocation of port_info objects.
+
+   Copyright (C) 2015 Free Software Foundation, Inc.
+
+   Written by Justus Winter <4winter@informatik.uni-hamburg.de>
+
+   This file is part of the GNU Hurd.
+
+   The GNU Hurd is free software; you can redistribute it and/or
+   modify it under the terms of the GNU General Public License as
+   published by the Free Software Foundation; either version 2, or (at
+   your option) any later version.
+
+   The GNU Hurd is distributed in the hope that it will be useful, but
+   WITHOUT ANY WARRANTY; without even the implied warranty of
+   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
+   General Public License for more details.
+
+   You should have received a copy of the GNU General Public License
+   along with the GNU Hurd.  If not, see <http://www.gnu.org/licenses/>.  */
+
+#include <assert.h>
+#include <pthread.h>
+#include "ports.h"
+
+/*
+ * A threadpool has a color indicating which threads belong to the old
+ * generation.
+ */
+#define COLOR_BLACK	0
+#define COLOR_WHITE	1
+#define COLOR_INVALID	~0U
+
+static inline int
+valid_color (unsigned int c)
+{
+  return c == COLOR_BLACK || c == COLOR_WHITE;
+}
+
+static inline unsigned int
+flip_color (unsigned int c)
+{
+  assert (valid_color (c));
+  return ! c;
+}
+
+/* Initialize the thread pool.  */
+void
+_ports_threadpool_init (struct ports_threadpool *pool)
+{
+  pthread_spin_init (&pool->lock, PTHREAD_PROCESS_PRIVATE);
+  pool->color = COLOR_BLACK;
+  pool->old_threads = 0;
+  pool->old_objects = NULL;
+  pool->young_threads = 0;
+  pool->young_objects = NULL;
+}
+
+/* Turn all young objects and threads into old ones.  */
+static inline void
+flip_generations (struct ports_threadpool *pool)
+{
+  assert (pool->old_threads == 0);
+  pool->old_threads = pool->young_threads;
+  pool->old_objects = pool->young_objects;
+  pool->young_threads = 0;
+  pool->young_objects = NULL;
+  pool->color = flip_color (pool->color);
+}
+
+/* Called by a thread to join a thread pool.  */
+void
+_ports_thread_online (struct ports_threadpool *pool,
+		      struct ports_thread *thread)
+{
+  pthread_spin_lock (&pool->lock);
+  thread->color = flip_color (pool->color);
+  pool->young_threads += 1;
+  pthread_spin_unlock (&pool->lock);
+}
+
+struct pi_list
+{
+  struct pi_list *next;
+  struct port_info *pi;
+};
+
+/* Called by a thread that enters its quiescent period.  */
+void
+_ports_thread_quiescent (struct ports_threadpool *pool,
+			 struct ports_thread *thread)
+{
+  struct pi_list *free_list = NULL, *p;
+  assert (valid_color (thread->color));
+
+  pthread_spin_lock (&pool->lock);
+  if (thread->color == pool->color)
+    {
+      pool->old_threads -= 1;
+      pool->young_threads += 1;
+      thread->color = flip_color (thread->color);
+
+      if (pool->old_threads == 0)
+	{
+	  free_list = pool->old_objects;
+	  flip_generations (pool);
+	}
+    }
+  pthread_spin_unlock (&pool->lock);
+
+  for (p = free_list; p;)
+    {
+      struct pi_list *old = p;
+      p = p->next;
+
+      ports_port_deref (old->pi);
+      free (old);
+    }
+}
+
+/* Called by a thread to leave a thread pool.  */
+void
+_ports_thread_offline (struct ports_threadpool *pool,
+		       struct ports_thread *thread)
+{
+  assert (valid_color (thread->color));
+
+ retry:
+  pthread_spin_lock (&pool->lock);
+  if (thread->color == pool->color)
+    {
+      pthread_spin_unlock (&pool->lock);
+      _ports_thread_quiescent (pool, thread);
+      goto retry;
+    }
+  thread->color = COLOR_INVALID;
+  pool->young_threads -= 1;
+  pthread_spin_unlock (&pool->lock);
+}
+
+/* Schedule an object for deallocation.  */
+void
+_ports_port_deref_deferred (struct port_info *pi)
+{
+  struct ports_threadpool *pool = &pi->bucket->threadpool;
+
+  struct pi_list *pl = malloc (sizeof *pl);
+  if (pl == NULL)
+    return;
+  pl->pi = pi;
+
+  pthread_spin_lock (&pool->lock);
+  pl->next = pool->young_objects;
+  pool->young_objects = pl;
+  if (pool->old_threads == 0)
+    {
+      assert (pool->old_objects == NULL);
+      flip_generations (pool);
+    }
+  pthread_spin_unlock (&pool->lock);
+}
diff --git a/libports/port-deref-deferred.h b/libports/port-deref-deferred.h
new file mode 100644
index 00000000..1589cb20
--- /dev/null
+++ b/libports/port-deref-deferred.h
@@ -0,0 +1,89 @@
+/* Delayed deallocation of port_info objects.
+
+   Copyright (C) 2015 Free Software Foundation, Inc.
+
+   Written by Justus Winter <4winter@informatik.uni-hamburg.de>
+
+   This file is part of the GNU Hurd.
+
+   The GNU Hurd is free software; you can redistribute it and/or
+   modify it under the terms of the GNU General Public License as
+   published by the Free Software Foundation; either version 2, or (at
+   your option) any later version.
+
+   The GNU Hurd is distributed in the hope that it will be useful, but
+   WITHOUT ANY WARRANTY; without even the implied warranty of
+   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
+   General Public License for more details.
+
+   You should have received a copy of the GNU General Public License
+   along with the GNU Hurd.  If not, see <http://www.gnu.org/licenses/>.  */
+
+#ifndef	_HURD_PORTS_DEREF_DEFERRED_
+#define	_HURD_PORTS_DEREF_DEFERRED_
+
+#include <pthread.h>
+
+/* A list of port_info objects.  */
+struct pi_list;
+
+/* We use protected payloads to look up objects without taking a lock.
+   A complication arises if we destroy an object using
+   ports_destroy_right.  To avoid payloads from becoming stale (and
+   resulting in invalid memory accesses when being interpreted as
+   pointer), we delay the deallocation of those object until all
+   threads running at the time of the objects destruction are done
+   with whatever they were doing and entered a quiescent period.  */
+struct ports_threadpool
+{
+  /* Access to the threadpool object is serialized by this lock.  */
+  pthread_spinlock_t lock;
+
+  /* We maintain two sets of objects and threads.  Each thread and the
+     threadpool itself has a color.  If a thread has the same color as
+     the thread pool, it belongs to the old generation.  */
+  unsigned int color;
+
+  /* The number of old threads.  When an old thread enters its
+     quiescent period, it decrements OLD_THREADS and flips its color
+     (hence becoming a young thread).  */
+  size_t old_threads;
+
+  /* A list of old objects.  Once OLD_THREADS drops to zero, they are
+     deallocated, and all young threads and objects become old threads
+     and objects.  */
+  struct pi_list *old_objects;
+
+  /* The number of young threads.  Any thread joining or leaving the
+     thread group must be a young thread.  */
+  size_t young_threads;
+
+  /* The list of young objects.  Any object being marked for delayed
+     deallocation is added to this list.  */
+  struct pi_list *young_objects;
+};
+
+/* Per-thread state.  */
+struct ports_thread
+{
+  unsigned int color;
+};
+
+/* Initialize the thread pool.  */
+void _ports_threadpool_init (struct ports_threadpool *);
+
+/* Called by a thread to join a thread pool.  */
+void _ports_thread_online (struct ports_threadpool *, struct ports_thread *);
+
+/* Called by a thread that enters its quiescent period.  */
+void _ports_thread_quiescent (struct ports_threadpool *, struct ports_thread *);
+
+/* Called by a thread to leave a thread pool.  */
+void _ports_thread_offline (struct ports_threadpool *, struct ports_thread *);
+
+struct port_info;
+
+/* Schedule an object for deallocation.  */
+void _ports_port_deref_deferred (struct port_info *);
+
+#endif	/* _HURD_PORTS_DEREF_DEFERRED_ */
diff --git a/libports/ports.h b/libports/ports.h
index f02edb42..9299bc40 100644
--- a/libports/ports.h
+++ b/libports/ports.h
@@ -29,6 +29,8 @@
 #include <pthread.h>
 #include <refcount.h>
 
+#include "port-deref-deferred.h"
+
 #ifdef PORTS_DEFINE_EI
 #define PORTS_EI
 #else
@@ -73,6 +75,7 @@ struct port_bucket
   int rpcs;
   int flags;
   int count;
+  struct ports_threadpool threadpool;
 };
 /* FLAGS above are the following: */
 #define PORT_BUCKET_INHIBITED	PORTS_INHIBITED
@@ -262,6 +265,9 @@ ports_lookup_payload (struct port_bucket *bucket,
 {
   struct port_info *pi = (struct port_info *) payload;
 
+  if (pi && ! MACH_PORT_VALID (pi->port_right))
+    pi = NULL;
+
   if (pi && bucket && pi->bucket != bucket)
     pi = NULL;
 
diff --git a/libports/reallocate-from-external.c b/libports/reallocate-from-external.c
index 7205bd9b..d0fae1a9 100644
--- a/libports/reallocate-from-external.c
+++ b/libports/reallocate-from-external.c
@@ -71,6 +71,10 @@ ports_reallocate_from_external (void *portstruct, mach_port_t receive)
   pthread_mutex_unlock (&_ports_lock);
   assert_perror (err);
 
+  /* This is an optimization.  It may fail.  */
+  mach_port_set_protected_payload (mach_task_self (), pi->port_right,
+				   (unsigned long) pi);
+
   mach_port_move_member (mach_task_self (), receive, pi->bucket->portset);
   
   if (stat.mps_srights)
diff --git a/libports/reallocate-port.c b/libports/reallocate-port.c
index cc534eb4..4e859a1f 100644
--- a/libports/reallocate-port.c
+++ b/libports/reallocate-port.c
@@ -59,6 +59,10 @@ ports_reallocate_port (void *portstruct)
   pthread_mutex_unlock (&_ports_lock);
   assert_perror (err);
 
+  /* This is an optimization.  It may fail.  */
+  mach_port_set_protected_payload (mach_task_self (), pi->port_right,
+				   (unsigned long) pi);
+
   err = mach_port_move_member (mach_task_self (), pi->port_right, 
 			       pi->bucket->portset);
   assert_perror (err);
diff --git a/libports/transfer-right.c b/libports/transfer-right.c
index 776a8d2b..64de7f79 100644
--- a/libports/transfer-right.c
+++ b/libports/transfer-right.c
@@ -91,6 +91,9 @@ ports_transfer_right (void *tostruct,
       err = hurd_ihash_add (&topi->bucket->htable, port, topi);
       pthread_rwlock_unlock (&_ports_htable_lock);
       assert_perror (err);
+      /* This is an optimization.  It may fail.  */
+      mach_port_set_protected_payload (mach_task_self (), port,
+				       (unsigned long) topi);
       if (topi->bucket != frompi->bucket)
         {
 	  err = mach_port_move_member (mach_task_self (), port,