diff options
-rw-r--r-- | debian/patches/0001-libports-use-protected-payloads-to-optimize-the-obje.patch | 594 | ||||
-rw-r--r-- | debian/patches/series | 1 |
2 files changed, 595 insertions, 0 deletions
diff --git a/debian/patches/0001-libports-use-protected-payloads-to-optimize-the-obje.patch b/debian/patches/0001-libports-use-protected-payloads-to-optimize-the-obje.patch new file mode 100644 index 00000000..8d42f790 --- /dev/null +++ b/debian/patches/0001-libports-use-protected-payloads-to-optimize-the-obje.patch @@ -0,0 +1,594 @@ +From b429bb6433e0331823c1927486c1c12f99c55a77 Mon Sep 17 00:00:00 2001 +From: Justus Winter <4winter@informatik.uni-hamburg.de> +Date: Sat, 23 Nov 2013 16:12:55 +0100 +Subject: [PATCH hurd] libports: use protected payloads to optimize the object + lookup + +* 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/Makefile | 2 +- + libports/complete-deallocate.c | 5 +- + libports/create-bucket.c | 1 + + libports/create-internal.c | 6 +- + libports/destroy-right.c | 56 +++++++++++---- + libports/import-port.c | 6 +- + libports/manage-multithread.c | 31 +++++++- + libports/manage-one-thread.c | 20 +++++- + libports/port-deref-deferred.c | 137 ++++++++++++++++++++++++++++++++++++ + libports/port-deref-deferred.h | 26 +++++++ + libports/ports.h | 11 +++ + libports/reallocate-from-external.c | 4 ++ + libports/reallocate-port.c | 4 ++ + libports/transfer-right.c | 3 + + 14 files changed, 292 insertions(+), 20 deletions(-) + create mode 100644 libports/port-deref-deferred.c + create mode 100644 libports/port-deref-deferred.h + +diff --git a/libports/Makefile b/libports/Makefile +index f49cb9f..b8b82ee 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 0d852f5..c81425e 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,8 @@ _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); ++ 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 2c5f1b6..82c00a4 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 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..276255f 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 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 58814d2..001a8bf 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, &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, &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, &thread); + return NULL; + } + +diff --git a/libports/manage-one-thread.c b/libports/manage-one-thread.c +index cbd2df7..fdb023d 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, &thread); + return status; + } + +@@ -93,8 +109,10 @@ ports_manage_port_operations_one_thread (struct port_bucket *bucket, + zero. */ + timeout = 0; + ++ _ports_thread_online (bucket, &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, &thread); + } +diff --git a/libports/port-deref-deferred.c b/libports/port-deref-deferred.c +new file mode 100644 +index 0000000..ddd2ac0 +--- /dev/null ++++ b/libports/port-deref-deferred.c +@@ -0,0 +1,137 @@ ++#include "ports.h" ++#include <assert.h> ++ ++#include <pthread.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; ++} ++ ++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; ++} ++ ++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); ++} ++ ++struct pi_list ++{ ++ struct pi_list *next; ++ struct port_info *pi; ++}; ++ ++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); ++} ++ ++void ++_ports_thread_online (struct port_bucket *bucket, ++ struct ports_thread *thread) ++{ ++ struct ports_threadpool *pool = &bucket->threadpool; ++ pthread_spin_lock (&pool->lock); ++ thread->color = flip_color (pool->color); ++ pool->young_threads += 1; ++ pthread_spin_unlock (&pool->lock); ++} ++ ++void ++_ports_thread_quiescent (struct port_bucket *bucket, ++ struct ports_thread *thread) ++{ ++ struct ports_threadpool *pool = &bucket->threadpool; ++ 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); ++ } ++} ++ ++void ++_ports_thread_offline (struct port_bucket *bucket, ++ struct ports_thread *thread) ++{ ++ struct ports_threadpool *pool = &bucket->threadpool; ++ assert (valid_color (thread->color)); ++ retry: ++ pthread_spin_lock (&pool->lock); ++ if (thread->color == pool->color) ++ { ++ pthread_spin_unlock (&pool->lock); ++ _ports_thread_quiescent (bucket, thread); ++ goto retry; ++ } ++ thread->color = COLOR_INVALID; ++ pool->young_threads -= 1; ++ pthread_spin_unlock (&pool->lock); ++} +diff --git a/libports/port-deref-deferred.h b/libports/port-deref-deferred.h +new file mode 100644 +index 0000000..6c208fd +--- /dev/null ++++ b/libports/port-deref-deferred.h +@@ -0,0 +1,26 @@ ++#ifndef _HURD_PORTS_DEREF_DEFERRED_ ++#define _HURD_PORTS_DEREF_DEFERRED_ ++ ++struct pi_list; ++ ++struct ports_threadpool ++{ ++ pthread_spinlock_t lock; ++ ++ unsigned int color; ++ ++ size_t old_threads; ++ struct pi_list *old_objects; ++ ++ size_t young_threads; ++ struct pi_list *young_objects; ++}; ++ ++struct ports_thread ++{ ++ unsigned int color; ++}; ++ ++void _ports_threadpool_init (struct ports_threadpool *); ++ ++#endif /* _HURD_PORTS_DEREF_DEFERRED_ */ +diff --git a/libports/ports.h b/libports/ports.h +index f02edb4..792e6a1 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; + +@@ -477,4 +483,9 @@ void _ports_complete_deallocate (struct port_info *); + error_t _ports_create_port_internal (struct port_class *, struct port_bucket *, + size_t, void *, int); + ++void _ports_port_deref_deferred (struct port_info *); ++void _ports_thread_online (struct port_bucket *, struct ports_thread *); ++void _ports_thread_quiescent (struct port_bucket *, struct ports_thread *); ++void _ports_thread_offline (struct port_bucket *, struct ports_thread *); ++ + #endif +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.4 + diff --git a/debian/patches/series b/debian/patches/series index 49de301c..5d895c59 100644 --- a/debian/patches/series +++ b/debian/patches/series @@ -46,3 +46,4 @@ merge-me-0002-startup-faster-reboots.patch thomas_term.patch ajoin.patch proc_disable_new_task_notifications.patch +0001-libports-use-protected-payloads-to-optimize-the-obje.patch |