From patchwork Wed Jan 13 13:00:44 2016 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Torvald Riegel X-Patchwork-Id: 566912 Return-Path: X-Original-To: incoming@patchwork.ozlabs.org Delivered-To: patchwork-incoming@bilbo.ozlabs.org Received: from sourceware.org (server1.sourceware.org [209.132.180.131]) (using TLSv1.2 with cipher ECDHE-RSA-AES256-GCM-SHA384 (256/256 bits)) (No client certificate requested) by ozlabs.org (Postfix) with ESMTPS id CBA2814031E for ; Thu, 14 Jan 2016 00:01:01 +1100 (AEDT) Authentication-Results: ozlabs.org; dkim=pass (1024-bit key; unprotected) header.d=gcc.gnu.org header.i=@gcc.gnu.org header.b=Hg2lfra2; dkim-atps=neutral DomainKey-Signature: a=rsa-sha1; c=nofws; d=gcc.gnu.org; h=list-id :list-unsubscribe:list-archive:list-post:list-help:sender :message-id:subject:from:to:date:content-type:mime-version; q= dns; s=default; b=dlVqy0WasUdesvzYO+CgcftzX17813bxVOfDf5v0Xk79HU EWtq30i/f8+IHdiut93cmpEsVgfWOqmjHdes9JPKYCZR5i+/9GE6AevjlLgp7BT3 CMMTzupexWFdCEdJpfr8bZdDpQyBEUFagQ9YhyHfoQWwKqO0xei5BciqwbLPQ= DKIM-Signature: v=1; a=rsa-sha1; c=relaxed; d=gcc.gnu.org; h=list-id :list-unsubscribe:list-archive:list-post:list-help:sender :message-id:subject:from:to:date:content-type:mime-version; s= default; bh=6Yz1WxyLBPxStbI/On8QcUeRArc=; b=Hg2lfra20Fn9oV45p6hY rUhpynx5RVseiuuiU/9pez/dD6c1VM1Ewn6RziIIfv6VyaFA59BIIgXLz4kSQeUs 2PFCYe/P3PGb3kJCaGknHy3vCcsJV0azqdudO1+17fyq0T0lttU+2/v6NWwaN1FC Wg3qazaQI7F1T5XM9QXaRX8= Received: (qmail 110241 invoked by alias); 13 Jan 2016 13:00:51 -0000 Mailing-List: contact gcc-patches-help@gcc.gnu.org; run by ezmlm Precedence: bulk List-Id: List-Unsubscribe: List-Archive: List-Post: List-Help: Sender: gcc-patches-owner@gcc.gnu.org Delivered-To: mailing list gcc-patches@gcc.gnu.org Received: (qmail 110220 invoked by uid 89); 13 Jan 2016 13:00:50 -0000 Authentication-Results: sourceware.org; auth=none X-Virus-Found: No X-Spam-SWARE-Status: No, score=-0.5 required=5.0 tests=BAYES_05, RP_MATCHES_RCVD, SPF_HELO_PASS autolearn=ham version=3.3.2 spammy=cancel, 1507, ensuring, 6188 X-HELO: mx1.redhat.com Received: from mx1.redhat.com (HELO mx1.redhat.com) (209.132.183.28) by sourceware.org (qpsmtpd/0.93/v0.84-503-g423c35a) with (AES256-GCM-SHA384 encrypted) ESMTPS; Wed, 13 Jan 2016 13:00:48 +0000 Received: from int-mx09.intmail.prod.int.phx2.redhat.com (int-mx09.intmail.prod.int.phx2.redhat.com [10.5.11.22]) by mx1.redhat.com (Postfix) with ESMTPS id 64004461C0 for ; Wed, 13 Jan 2016 13:00:47 +0000 (UTC) Received: from [10.36.5.13] (vpn1-5-13.ams2.redhat.com [10.36.5.13]) by int-mx09.intmail.prod.int.phx2.redhat.com (8.14.4/8.14.4) with ESMTP id u0DD0iqD020121 (version=TLSv1/SSLv3 cipher=DHE-RSA-AES256-SHA256 bits=256 verify=NO) for ; Wed, 13 Jan 2016 08:00:46 -0500 Message-ID: <1452690044.26597.334.camel@localhost.localdomain> Subject: [PATCH][committed] libitm: Fix privatization safety interaction with serial mode. From: Torvald Riegel To: GCC Patches Date: Wed, 13 Jan 2016 14:00:44 +0100 Mime-Version: 1.0 X-IsSubscribed: yes This patch fixes the interaction of privatization safety and serial mode. Specifically, previously serial mode was able to happen concurrently with other threads still being in the quiescence-based implementation of ensuring privatization safety; this is a bug because serial mode threads can modify the list of transactions (which privatization safety iterates over) and can change the current method group (priv safety depends on shared_state to have the context of the method group that the privatizing thread assumes to be still current). The fix delays making a transaction inactive to after it has ensured privatization safety. It becomes quasi-inactive before that (ie, it gets an always-most-recent snapshot) though. However, as a result of that, we now need to prevent deadlocks between transactions upgrading to serial mode and privatization safety: The upgrader must keep its snapshot most recent (or abort if it cannot) so that the still-active transactions that the upgrader waits for are not waiting in turn for the upgrader to update its snapshot. Tested on x86_64-linux. Committed as r232322. 2016-01-13 Torvald Riegel * beginend.cc (gtm_thread::trycommit): Fix privatization safety. * config/linux/rwlock.cc (gtm_rwlock::write_lock_generic): Likewise. * config/posix/rwlock.cc (gtm_rwlock::write_lock_generic): Likewise. * dispatch.h (abi_dispatch::snapshot_most_recent): New. * method-gl.cc (gl_wt_dispatch::snapshot_most_recent): New. * method-ml.cc (ml_wt_dispatch::snapshot_most_recent): New. * method-serial.cc (serial_dispatch::snapshot_most_recent): New. (serialirr_dispatch::snapshot_most_recent): New. (serialirr_onwrite_dispatch::snapshot_most_recent): New. commit 25e850205e37009a76fb37b52f9ce61ab1616995 Author: Torvald Riegel Date: Wed Jan 13 13:35:09 2016 +0100 libitm: Fix privatization safety interaction with serial mode. diff --git a/libitm/beginend.cc b/libitm/beginend.cc index c801dab..85fb4f1 100644 --- a/libitm/beginend.cc +++ b/libitm/beginend.cc @@ -568,8 +568,9 @@ GTM::gtm_thread::trycommit () gtm_word priv_time = 0; if (abi_disp()->trycommit (priv_time)) { - // The transaction is now inactive. Everything that we still have to do - // will not synchronize with other transactions anymore. + // The transaction is now finished but we will still access some shared + // data if we have to ensure privatization safety. + bool do_read_unlock = false; if (state & gtm_thread::STATE_SERIAL) { gtm_thread::serial_lock.write_unlock (); @@ -578,7 +579,27 @@ GTM::gtm_thread::trycommit () priv_time = 0; } else - gtm_thread::serial_lock.read_unlock (this); + { + // If we have to ensure privatization safety, we must not yet + // release the read lock and become inactive because (1) we still + // have to go through the list of all transactions, which can be + // modified by serial mode threads, and (2) we interpret each + // transactions' shared_state in the context of what we believe to + // be the current method group (and serial mode transactions can + // change the method group). Therefore, if we have to ensure + // privatization safety, delay becoming inactive but set a maximum + // snapshot time (we have committed and thus have an empty snapshot, + // so it will always be most recent). Use release MO so that this + // synchronizes with other threads observing our snapshot time. + if (priv_time) + { + do_read_unlock = true; + shared_state.store((~(typeof gtm_thread::shared_state)0) - 1, + memory_order_release); + } + else + gtm_thread::serial_lock.read_unlock (this); + } state = 0; // We can commit the undo log after dispatch-specific commit and after @@ -618,8 +639,11 @@ GTM::gtm_thread::trycommit () } } - // After ensuring privatization safety, we execute potentially - // privatizing actions (e.g., calling free()). User actions are first. + // After ensuring privatization safety, we are now truly inactive and + // thus can release the read lock. We will also execute potentially + // privatizing actions (e.g., calling free()). User actions are first. + if (do_read_unlock) + gtm_thread::serial_lock.read_unlock (this); commit_user_actions (); commit_allocations (false, 0); diff --git a/libitm/config/linux/rwlock.cc b/libitm/config/linux/rwlock.cc index 46a775f..381a553 100644 --- a/libitm/config/linux/rwlock.cc +++ b/libitm/config/linux/rwlock.cc @@ -158,6 +158,19 @@ gtm_rwlock::write_lock_generic (gtm_thread *tx) while (it->shared_state.load (memory_order_relaxed) != ~(typeof it->shared_state)0) { + // If this is an upgrade, we have to break deadlocks with + // privatization safety. This may fail on our side, in which + // case we need to cancel our attempt to upgrade. Also, we do not + // block but just spin so that we never have to be woken. + if (tx != 0) + { + if (!abi_disp()->snapshot_most_recent ()) + { + write_unlock (); + return false; + } + continue; + } // An active reader. Wait until it has finished. To avoid lost // wake-ups, we need to use Dekker-like synchronization. // Note that we can reset writer_readers to zero when we see after diff --git a/libitm/config/posix/rwlock.cc b/libitm/config/posix/rwlock.cc index bf58ec0..1e1eea8 100644 --- a/libitm/config/posix/rwlock.cc +++ b/libitm/config/posix/rwlock.cc @@ -200,6 +200,26 @@ gtm_rwlock::write_lock_generic (gtm_thread *tx) if (readers == 0) break; + // If this is an upgrade, we have to break deadlocks with + // privatization safety. This may fail on our side, in which + // case we need to cancel our attempt to upgrade. Also, we do not + // block using the convdar but just spin so that we never have to be + // woken. + // FIXME This is horribly inefficient -- but so is not being able + // to use futexes in this case. + if (tx != 0) + { + pthread_mutex_unlock (&this->mutex); + if (!abi_disp ()->snapshot_most_recent ()) + { + write_unlock (); + return false; + } + pthread_mutex_lock (&this->mutex); + continue; + } + + // We've seen a number of readers, so we publish this number and wait. this->a_readers = readers; pthread_cond_wait (&this->c_confirmed_writers, &this->mutex); diff --git a/libitm/dispatch.h b/libitm/dispatch.h index 0bf1a81..4ec5631 100644 --- a/libitm/dispatch.h +++ b/libitm/dispatch.h @@ -291,6 +291,10 @@ public: // Rolls back a transaction. Called on abort or after trycommit() returned // false. virtual void rollback(gtm_transaction_cp *cp = 0) = 0; + // Returns true iff the snapshot is most recent, which will be the case if + // this transaction cannot be the reason why other transactions cannot + // ensure privatization safety. + virtual bool snapshot_most_recent() = 0; // Return an alternative method that is compatible with the current // method but supports closed nesting. Return zero if there is none. diff --git a/libitm/method-gl.cc b/libitm/method-gl.cc index 87d01db..b2e2bca 100644 --- a/libitm/method-gl.cc +++ b/libitm/method-gl.cc @@ -338,6 +338,15 @@ public: } + virtual bool snapshot_most_recent() + { + // This is the same check as in validate() except that we do not restart + // on failure but simply return the result. + return o_gl_mg.orec.load(memory_order_relaxed) + == gtm_thr()->shared_state.load(memory_order_relaxed); + } + + CREATE_DISPATCH_METHODS(virtual, ) CREATE_DISPATCH_METHODS_MEM() diff --git a/libitm/method-ml.cc b/libitm/method-ml.cc index 1c2de70..723643a 100644 --- a/libitm/method-ml.cc +++ b/libitm/method-ml.cc @@ -604,6 +604,24 @@ public: tx->readlog.clear(); } + virtual bool snapshot_most_recent() + { + // This is the same code as in extend() except that we do not restart + // on failure but simply return the result, and that we don't validate + // if our snapshot is already most recent. + gtm_thread* tx = gtm_thr(); + gtm_word snapshot = o_ml_mg.time.load(memory_order_acquire); + if (snapshot == tx->shared_state.load(memory_order_relaxed)) + return true; + if (!validate(tx)) + return false; + + // Update our public snapshot time. Necessary so that we do not prevent + // other transactions from ensuring privatization safety. + tx->shared_state.store(snapshot, memory_order_release); + return true; + } + virtual bool supports(unsigned number_of_threads) { // Each txn can commit and fail and rollback once before checking for diff --git a/libitm/method-serial.cc b/libitm/method-serial.cc index 82d407d..1123e34 100644 --- a/libitm/method-serial.cc +++ b/libitm/method-serial.cc @@ -95,6 +95,7 @@ class serialirr_dispatch : public abi_dispatch virtual gtm_restart_reason begin_or_restart() { return NO_RESTART; } virtual bool trycommit(gtm_word& priv_time) { return true; } virtual void rollback(gtm_transaction_cp *cp) { abort(); } + virtual bool snapshot_most_recent() { return true; } virtual abi_dispatch* closed_nesting_alternative() { @@ -149,6 +150,7 @@ public: // Local undo will handle this. // trydropreference() need not be changed either. virtual void rollback(gtm_transaction_cp *cp) { } + virtual bool snapshot_most_recent() { return true; } CREATE_DISPATCH_METHODS(virtual, ) CREATE_DISPATCH_METHODS_MEM() @@ -210,6 +212,8 @@ class serialirr_onwrite_dispatch : public serialirr_dispatch if (tx->state & gtm_thread::STATE_IRREVOCABLE) abort(); } + + virtual bool snapshot_most_recent() { return true; } }; // This group is pure HTM with serial mode as a fallback. There is no