[PATCH hurd 28/30] libports: use protected payloads to optimize the object lookup

[Justus Winter]

* 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 as the objects address if provided.
* 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 if a no-senders notification is dispatched.
(struct deferred_dereference, gc_loop, start_gc, defer_dereferencing):
Simple generational garbage collection of outstanding send rights.
---
 libports/complete-deallocate.c      |   2 +-
 libports/create-internal.c          |   6 +-
 libports/destroy-right.c            | 133 ++++++++++++++++++++++++++++++++++--
 libports/import-port.c              |   6 +-
 libports/manage-multithread.c       |  22 +++++-
 libports/manage-one-thread.c        |  22 +++++-
 libports/reallocate-from-external.c |   4 ++
 libports/reallocate-port.c          |   4 ++
 libports/transfer-right.c           |   3 +
 9 files changed, 193 insertions(+), 9 deletions(-)

diff --git a/libports/complete-deallocate.c b/libports/complete-deallocate.c
index 0d852f5..6799dfd 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;
 
diff --git a/libports/create-internal.c b/libports/create-internal.c
index 2d85931..d79dc78 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 448b379..c229d77 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,155 @@
 #include <hurd/ihash.h>
 #include <assert.h>
 
+#include <pthread.h>
+#include <error.h>
+#include <time.h>
+#include <unistd.h>
+
+/* To prevent protected payloads from becoming stale, we defer the
+   derefercing of port_info objects.  Consumes PI.  */
+static error_t defer_dereferencing (struct port_info *pi);
+
 error_t
 ports_destroy_right (void *portstruct)
 {
   struct port_info *pi = portstruct;
   error_t err;
 
+  mach_port_clear_protected_payload (mach_task_self (),
+                                    pi->port_right);
+
+  pthread_mutex_lock (&_ports_lock);
   if (pi->port_right != MACH_PORT_NULL)
     {
       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;
-
       if (pi->flags & PORT_HAS_SENDRIGHTS)
        {
          pi->flags &= ~PORT_HAS_SENDRIGHTS;
-         ports_port_deref (pi);
+
+         /* There are outstanding send rights, so we might get a
+            no-senders notification.  Attached to the notification
+            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 send and dequeued.
+
+            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.  */
+         defer_dereferencing (pi);
        }
+
+      pi->port_right = MACH_PORT_DEAD;
     }
+  pthread_mutex_unlock (&_ports_lock);
+
+  return 0;
+}
+
+/* Simple lock-less generational garbage collection.  */
+
+/* We maintain three lists of objects. Producers add objects to the
+   current generation G using defer_dereferencing.  G-1 holds old
+   objects, G-2 holds garbage. */
+static struct deferred_dereference
+{
+  struct deferred_dereference *next;
+  struct port_info *pi;        /* We hold a reference for these objects.  */
+} *generations[3];     /* Must be accessed using atomic
+                          operations.  */
+
+/* The current generation.  Must be accessed using atomic operations.  */
+static int generation;
+
+/* The garbage collection thread.  Does not return.  */
+static void *
+gc_loop (void *arg)
+{
+  while (1)
+    {
+      int old, garbage;
+      struct deferred_dereference *d;
+
+      sleep (5);
+
+      /* We are the only one updating generation, so this is safe.  */
+      old = generation;
+
+      /* Update generation.  */
+      __atomic_store_n (&generation, (old + 1) % 3, __ATOMIC_RELAXED);
+
+      /* This is the garbage generation.  As all writers are long
+        gone, we do not need to bother with atomic operations.  */
+      garbage = (old + 2) % 3;
+      d = generations[garbage];
+      generations[garbage] = NULL;
+      while (d != NULL)
+       {
+         struct deferred_dereference *next = d->next;
+
+         /* Get rid of our reference.  */
+         ports_port_deref (d->pi);
+
+         free (d);
+         d = next;
+       }
+    }
+
+  assert (! "reached");
+  return NULL;
+}
+
+/* Start the gc thread.  */
+static void
+start_gc (void)
+{
+  error_t err;
+  pthread_attr_t attr;
+  pthread_t thread;
+
+  pthread_attr_init (&attr);
+#define STACK_SIZE (64 * 1024)
+  pthread_attr_setstacksize (&attr, STACK_SIZE);
+#undef STACK_SIZE
+
+  err = pthread_create (&thread, &attr, gc_loop, NULL);
+  assert_perror (err);
+  err = pthread_detach (thread);
+  assert_perror (err);
+}
+
+/* Defer the derefercing of port_info objects.  Consumes PI.  */
+static error_t
+defer_dereferencing (struct port_info *pi)
+{
+  static pthread_once_t once = PTHREAD_ONCE_INIT;
+  int g;
+  struct deferred_dereference *d;
+  pthread_once (&once, start_gc);
+
+  d = malloc (sizeof *d);
+  if (d == NULL)
+    return ENOMEM;
+  d->pi = pi;
+
+ retry:
+  /* Append to the current generation. */
+  g = __atomic_load_n (&generation, __ATOMIC_RELAXED);
+
+  d->next = __atomic_load_n (&generations[g], __ATOMIC_RELAXED);
+  if (! __atomic_compare_exchange_n (&generations[g], &d->next, d,
+                                    0, __ATOMIC_RELAXED, __ATOMIC_RELAXED))
+    goto retry;
 
   return 0;
 }
diff --git a/libports/import-port.c b/libports/import-port.c
index c337c85..2c638e1 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 2067cba..90b3044 100644
--- a/libports/manage-multithread.c
+++ b/libports/manage-multithread.c
@@ -162,7 +162,27 @@ 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 = (struct port_info *) inp->msgh_protected_payload;
+         if (pi && pi->bucket == bucket)
+           ports_port_ref (pi);
+         else
+           pi = 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);
diff --git a/libports/manage-one-thread.c b/libports/manage-one-thread.c
index cbd2df7..58c0f36 100644
--- a/libports/manage-one-thread.c
+++ b/libports/manage-one-thread.c
@@ -57,7 +57,27 @@ 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 = (struct port_info *) inp->msgh_protected_payload;
+         if (pi && pi->bucket == bucket)
+           ports_port_ref (pi);
+         else
+           pi = 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);
diff --git a/libports/reallocate-from-external.c 
b/libports/reallocate-from-external.c
index 7205bd9..d0fae1a 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 cc534eb..4e859a1 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 776a8d2..64de7f7 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,
-- 
2.1.3