From 4241dd5673566a61add85bd9eb52d4ae7db2750a 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: 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'. --- NEWS | 2 + libports/Makefile | 2 +- libports/complete-deallocate.c | 6 +- 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 | 161 ++++++++++++++++++++++++++++++++++++ libports/port-deref-deferred.h | 89 ++++++++++++++++++++ libports/ports.h | 6 ++ libports/reallocate-from-external.c | 4 + libports/reallocate-port.c | 4 + libports/transfer-right.c | 3 + 15 files changed, 377 insertions(+), 20 deletions(-) create mode 100644 libports/port-deref-deferred.c create mode 100644 libports/port-deref-deferred.h diff --git a/NEWS b/NEWS index b047aed2..18e14892 100644 --- a/NEWS +++ b/NEWS @@ -6,6 +6,8 @@ problems have been identified using static analysis and exercising tools, and have subsequently been fixed. The message dispatching code in the Hurd servers has been improved. +Among other things, we now make use of the protected payloads +introduced in GNU Mach 1.5. The embedded gz and bz2 decompressor code has been removed, libz and libbz2 is used instead. 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 #include +#include +#include +#include +#include + 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 . */ + +#include +#include +#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 . */ + +#ifndef _HURD_PORTS_DEREF_DEFERRED_ +#define _HURD_PORTS_DEREF_DEFERRED_ + +#include + +/* 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 #include +#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, -- cgit v1.2.3