libitm/config/linux/rwlock.cc

   1 /* Copyright (C) 2011 Free Software Foundation, Inc.
   2    Contributed by Torvald Riegel <triegel@redhat.com>.
   3
   4    This file is part of the GNU Transactional Memory Library (libitm).
   5
   6    Libitm is free software; you can redistribute it and/or modify it
   7    under the terms of the GNU General Public License as published by
   8    the Free Software Foundation; either version 3 of the License, or
   9    (at your option) any later version.
  10
  11    Libitm is distributed in the hope that it will be useful, but WITHOUT ANY
  12    WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS
  13    FOR A PARTICULAR PURPOSE.  See the GNU General Public License for
  14    more details.
  15
  16    Under Section 7 of GPL version 3, you are granted additional
  17    permissions described in the GCC Runtime Library Exception, version
  18    3.1, as published by the Free Software Foundation.
  19
  20    You should have received a copy of the GNU General Public License and
  21    a copy of the GCC Runtime Library Exception along with this program;
  22    see the files COPYING3 and COPYING.RUNTIME respectively.  If not, see
  23    <http://www.gnu.org/licenses/>.  */
  24
  25 #include "libitm_i.h"
  26 #include "futex.h"
  27 #include <limits.h>
  28
  29 namespace GTM HIDDEN {
  30
  31 // Acquire a RW lock for reading.
  32
  33 void
  34 gtm_rwlock::read_lock (gtm_thread *tx)
  35 {
  36   for (;;)
  37     {
  38       // Fast path: first announce our intent to read, then check for
  39       // conflicting intents to write. The barrier makes sure that this
  40       // happens in exactly this order.
  41       tx->shared_state = 0;
  42       __sync_synchronize();
  43       if (likely(writers == 0))
  44         return;
  45
  46       // There seems to be an active, waiting, or confirmed writer, so enter
  47       // the futex-based slow path.
  48
  49       // Before waiting, we clear our read intent check whether there are any
  50       // writers that might potentially wait for readers. If so, wake them.
  51       // We need the barrier here for the same reason that we need it in
  52       // read_unlock().
  53       // TODO Potentially too many wake-ups. See comments in read_unlock().
  54       tx->shared_state = ~(typeof tx->shared_state)0;
  55       __sync_synchronize();
  56       if (writer_readers > 0)
  57         {
  58           writer_readers = 0;
  59           futex_wake(&writer_readers, 1);
  60         }
  61
  62       // Signal that there are waiting readers and wait until there is no
  63       // writer anymore.
  64       // TODO Spin here on writers for a while. Consider whether we woke
  65       // any writers before?
  66       while (writers)
  67         {
  68           // An active writer. Wait until it has finished. To avoid lost
  69           // wake-ups, we need to use Dekker-like synchronization.
  70           // Note that we cannot reset readers to zero when we see that there
  71           // are no writers anymore after the barrier because this pending
  72           // store could then lead to lost wake-ups at other readers.
  73           readers = 1;
  74           __sync_synchronize();
  75           if (writers)
  76             futex_wait(&readers, 1);
  77         }
  78
  79       // And we try again to acquire a read lock.
  80     }
  81 }
  82
  83
  84 // Acquire a RW lock for writing. Generic version that also works for
  85 // upgrades.
  86 // Note that an upgrade might fail (and thus waste previous work done during
  87 // this transaction) if there is another thread that tried to go into serial
  88 // mode earlier (i.e., upgrades do not have higher priority than pure writers).
  89 // However, this seems rare enough to not consider it further as we need both
  90 // a non-upgrade writer and a writer to happen to switch to serial mode
  91 // concurrently. If we'd want to handle this, a writer waiting for readers
  92 // would have to coordinate with later arriving upgrades and hand over the
  93 // lock to them, including the the reader-waiting state. We can try to support
  94 // this if this will actually happen often enough in real workloads.
  95
  96 bool
  97 gtm_rwlock::write_lock_generic (gtm_thread *tx)
  98 {
  99   // Try to acquire the write lock.
 100   unsigned int w;
 101   if (unlikely((w = __sync_val_compare_and_swap(&writers, 0, 1)) != 0))
 102     {
 103       // If this is an upgrade, we must not wait for other writers or
 104       // upgrades.
 105       if (tx != 0)
 106         return false;
 107
 108       // There is already a writer. If there are no other waiting writers,
 109       // switch to contended mode.
 110       // Note that this is actually an atomic exchange, not a TAS. Also,
 111       // it's only guaranteed to have acquire semantics, whereas we need a
 112       // full barrier to make the Dekker-style synchronization work. However,
 113       // we rely on the xchg being a full barrier on the architectures that we
 114       // consider here.
 115       // ??? Use C++0x atomics as soon as they are available.
 116       if (w != 2)
 117         w = __sync_lock_test_and_set(&writers, 2);
 118       while (w != 0)
 119         {
 120           futex_wait(&writers, 2);
 121           w = __sync_lock_test_and_set(&writers, 2);
 122         }
 123     }
 124
 125   // We have acquired the writer side of the R/W lock. Now wait for any
 126   // readers that might still be active.
 127   // We don't need an extra barrier here because the CAS and the xchg
 128   // operations have full barrier semantics already.
 129
 130   // If this is an upgrade, we are not a reader anymore. This is only safe to
 131   // do after we have acquired the writer lock.
 132   // TODO In the worst case, this requires one wait/wake pair for each
 133   // active reader. Reduce this!
 134   if (tx != 0)
 135     tx->shared_state = ~(typeof tx->shared_state)0;
 136
 137   for (gtm_thread *it = gtm_thread::list_of_threads; it != 0;
 138       it = it->next_thread)
 139     {
 140       // Use a loop here to check reader flags again after waiting.
 141       while (it->shared_state != ~(typeof it->shared_state)0)
 142         {
 143           // An active reader. Wait until it has finished. To avoid lost
 144           // wake-ups, we need to use Dekker-like synchronization.
 145           // Note that we can reset writer_readers to zero when we see after
 146           // the barrier that the reader has finished in the meantime;
 147           // however, this is only possible because we are the only writer.
 148           // TODO Spin for a while on this reader flag.
 149           writer_readers = 1;
 150           __sync_synchronize();
 151           if (it->shared_state != ~(typeof it->shared_state)0)
 152             futex_wait(&writer_readers, 1);
 153           else
 154             writer_readers = 0;
 155         }
 156     }
 157
 158   return true;
 159 }
 160
 161 // Acquire a RW lock for writing.
 162
 163 void
 164 gtm_rwlock::write_lock ()
 165 {
 166   write_lock_generic (0);
 167 }
 168
 169
 170 // Upgrade a RW lock that has been locked for reading to a writing lock.
 171 // Do this without possibility of another writer incoming.  Return false
 172 // if this attempt fails (i.e. another thread also upgraded).
 173
 174 bool
 175 gtm_rwlock::write_upgrade (gtm_thread *tx)
 176 {
 177   return write_lock_generic (tx);
 178 }
 179
 180
 181 // Release a RW lock from reading.
 182
 183 void
 184 gtm_rwlock::read_unlock (gtm_thread *tx)
 185 {
 186   tx->shared_state = ~(typeof tx->shared_state)0;
 187
 188   // If there is a writer waiting for readers, wake it up. We need the barrier
 189   // to avoid lost wake-ups.
 190   // ??? We might not be the last active reader, so the wake-up might happen
 191   // too early. How do we avoid this without slowing down readers too much?
 192   // Each reader could scan the list of txns for other active readers but
 193   // this can result in many cache misses. Use combining instead?
 194   // TODO Sends out one wake-up for each reader in the worst case.
 195   __sync_synchronize();
 196   if (unlikely(writer_readers > 0))
 197     {
 198       writer_readers = 0;
 199       futex_wake(&writer_readers, 1);
 200     }
 201 }
 202
 203
 204 // Release a RW lock from writing.
 205
 206 void
 207 gtm_rwlock::write_unlock ()
 208 {
 209   // This is supposed to be a full barrier.
 210   if (__sync_fetch_and_sub(&writers, 1) == 2)
 211     {
 212       // There might be waiting writers, so wake them.
 213       writers = 0;
 214       if (futex_wake(&writers, 1) == 0)
 215         {
 216           // If we did not wake any waiting writers, we might indeed be the
 217           // last writer (this can happen because write_lock_generic()
 218           // exchanges 0 or 1 to 2 and thus might go to contended mode even if
 219           // no other thread holds the write lock currently). Therefore, we
 220           // have to wake up readers here as well.
 221           futex_wake(&readers, INT_MAX);
 222         }
 223       return;
 224     }
 225   // No waiting writers, so wake up all waiting readers.
 226   // Because the fetch_and_sub is a full barrier already, we don't need
 227   // another barrier here (as in read_unlock()).
 228   if (readers > 0)
 229     {
 230       readers = 0;
 231       futex_wake(&readers, INT_MAX);
 232     }
 233 }
 234
 235 } // namespace GTM