OSDN Git Service

libitm: Fixed conversion to C++11 atomics.
[pf3gnuchains/gcc-fork.git] / libitm / config / posix / rwlock.cc
1 /* Copyright (C) 2008, 2009, 2011 Free Software Foundation, Inc.
2    Contributed by Richard Henderson <rth@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
27 namespace GTM HIDDEN {
28
29 // Initialize a new RW lock.
30 // ??? Move this back to the header file when constexpr is implemented.
31
32 gtm_rwlock::gtm_rwlock()
33   : mutex (PTHREAD_MUTEX_INITIALIZER),
34     c_readers (PTHREAD_COND_INITIALIZER),
35     c_writers (PTHREAD_COND_INITIALIZER),
36     c_confirmed_writers (PTHREAD_COND_INITIALIZER),
37     summary (0),
38     a_readers (0),
39     w_readers (0),
40     w_writers (0)
41 { }
42
43 gtm_rwlock::~gtm_rwlock()
44 {
45   pthread_mutex_destroy (&this->mutex);
46   pthread_cond_destroy (&this->c_readers);
47   pthread_cond_destroy (&this->c_writers);
48 }
49
50 // Acquire a RW lock for reading.
51
52 void
53 gtm_rwlock::read_lock (gtm_thread *tx)
54 {
55   // Fast path: first announce our intent to read, then check for conflicting
56   // intents to write.  The fence ensure that this happens in exactly this
57   // order.
58   tx->shared_state.store (0, memory_order_relaxed);
59   atomic_thread_fence (memory_order_seq_cst);
60   unsigned int sum = this->summary.load (memory_order_relaxed);
61   if (likely(!(sum & (a_writer | w_writer))))
62     return;
63
64   // There seems to be an active, waiting, or confirmed writer, so enter the
65   // mutex-based slow path. To try to keep the number of readers small that
66   // the writer will see, we clear our read flag right away before entering
67   // the critical section. Otherwise, the writer would have to wait for us to
68   // get into the critical section. (Note that for correctness, this only has
69   // to happen before we leave the slow path and before we wait for any
70   // writer).
71   // ??? Add a barrier to enforce early visibility of this?
72   tx->shared_state.store(-1, memory_order_relaxed);
73
74   pthread_mutex_lock (&this->mutex);
75
76   // Read summary again after acquiring the mutex because it might have
77   // changed during waiting for the mutex to become free.
78   sum = this->summary.load (memory_order_relaxed);
79
80   // If there is a writer waiting for readers, wake it up. Only do that if we
81   // might be the last reader that could do the wake-up, otherwise skip the
82   // wake-up but decrease a_readers to show that we have entered the slow path.
83   // This has to happen before we wait for any writers or upgraders.
84   // See write_lock_generic() for further explanations.
85   if (this->a_readers > 0)
86     {
87       this->a_readers--;
88       if (this->a_readers == 0)
89         pthread_cond_signal(&this->c_confirmed_writers);
90     }
91
92   // If there is an active or waiting writer, we must wait.
93   while (sum & (a_writer | w_writer))
94     {
95       this->summary.store (sum | w_reader, memory_order_relaxed);
96       this->w_readers++;
97       pthread_cond_wait (&this->c_readers, &this->mutex);
98       sum = this->summary.load (memory_order_relaxed);
99       if (--this->w_readers == 0)
100         sum &= ~w_reader;
101     }
102
103   // Otherwise we can acquire the lock for read.
104   tx->shared_state.store(0, memory_order_relaxed);
105
106   pthread_mutex_unlock(&this->mutex);
107 }
108
109
110 // Acquire a RW lock for writing. Generic version that also works for
111 // upgrades.
112 // Note that an upgrade might fail (and thus waste previous work done during
113 // this transaction) if there is another thread that tried to go into serial
114 // mode earlier (i.e., upgrades do not have higher priority than pure writers).
115 // However, this seems rare enough to not consider it further as we need both
116 // a non-upgrade writer and a writer to happen to switch to serial mode
117 // concurrently. If we'd want to handle this, a writer waiting for readers
118 // would have to coordinate with later arriving upgrades and hand over the
119 // lock to them, including the the reader-waiting state. We can try to support
120 // this if this will actually happen often enough in real workloads.
121
122 bool
123 gtm_rwlock::write_lock_generic (gtm_thread *tx)
124 {
125   pthread_mutex_lock (&this->mutex);
126
127   unsigned int sum = this->summary.load (memory_order_relaxed);
128
129   // If there is an active writer, wait.
130   while (sum & a_writer)
131     {
132       if (tx != 0)
133         {
134           // If this is an upgrade, we must not wait for other writers or
135           // upgrades that already have gone in
136           pthread_mutex_unlock (&this->mutex);
137           return false;
138         }
139
140       this->summary.store (sum | w_writer, memory_order_relaxed);
141       this->w_writers++;
142       pthread_cond_wait (&this->c_writers, &this->mutex);
143       sum = this->summary.load (memory_order_relaxed);
144       if (--this->w_writers == 0)
145         sum &= ~w_writer;
146     }
147
148   // Otherwise we can acquire the lock for write. As a writer, we have
149   // priority, so we don't need to take this back.
150   this->summary.store (sum | a_writer, memory_order_relaxed);
151
152   // We still need to wait for active readers to finish. The barrier makes
153   // sure that we first set our write intent and check for active readers
154   // after that, in strictly this order (similar to the barrier in the fast
155   // path of read_lock()).
156   atomic_thread_fence(memory_order_seq_cst);
157
158   // If this is an upgrade, we are not a reader anymore.
159   if (tx != 0)
160     tx->shared_state.store(-1, memory_order_relaxed);
161
162   // Count the number of active readers to be able to decrease the number of
163   // wake-ups and wait calls that are necessary.
164   //
165   // This number is an upper bound of the number of readers that actually
166   // are still active and which we need to wait for:
167   // - We set our write flag before checking the reader flags, and readers
168   //   check our write flag after clearing their read flags in read_unlock().
169   //   Therefore, they will enter the slow path whenever we have seen them.
170   // - Readers will have cleared their read flags before leaving the slow
171   //   path in read_lock() (prevents lost wake-ups), and before waiting for
172   //   any writer (prevents deadlocks).
173   //
174   // However, this number is also just a lower bound of the number of readers
175   // that will actually enter the slow path in read_unlock() or read_lock():
176   // - Because the read flag is cleared outside of a critical section, writers
177   //   can see it as cleared while the reader still goes into the slow path.
178   //
179   // Therefore, readers can skip (lower bound - 1) wake-ups, but we do need
180   // the following loop to check that the readers that we wanted to wait for
181   // are actually those that entered the slow path so far (and either skipped
182   // or sent a wake-up).
183   //
184   // ??? Do we need to optimize further? (The writer could publish a list of
185   // readers that it suspects to be active. Readers could check this list and
186   // only decrement a_readers if they are in this list.)
187   for (;;)
188     {
189       // ??? Keep a list of active readers that we saw and update it on the
190       // next retry instead? This might reduce the number of cache misses that
191       // we get when checking reader flags.
192       int readers = 0;
193       for (gtm_thread *it = gtm_thread::list_of_threads; it != 0;
194           it = it->next_thread)
195         {
196           // Don't count ourself if this is an upgrade.
197           if (it->shared_state.load(memory_order_relaxed) != (gtm_word)-1)
198             readers++;
199         }
200
201       // If we have not seen any readers, we will not wait.
202       if (readers == 0)
203         break;
204
205       // We've seen a number of readers, so we publish this number and wait.
206       this->a_readers = readers;
207       pthread_cond_wait (&this->c_confirmed_writers, &this->mutex);
208     }
209
210   pthread_mutex_unlock (&this->mutex);
211   return true;
212 }
213
214 // Acquire a RW lock for writing.
215
216 void
217 gtm_rwlock::write_lock ()
218 {
219   write_lock_generic (0);
220 }
221
222
223 // Upgrade a RW lock that has been locked for reading to a writing lock.
224 // Do this without possibility of another writer incoming.  Return false
225 // if this attempt fails (i.e. another thread also upgraded).
226
227 bool
228 gtm_rwlock::write_upgrade (gtm_thread *tx)
229 {
230   return write_lock_generic (tx);
231 }
232
233
234 // Release a RW lock from reading.
235
236 void
237 gtm_rwlock::read_unlock (gtm_thread *tx)
238 {
239   // We only need release memory order here because of privatization safety
240   // (this ensures that marking the transaction as inactive happens after
241   // any prior data accesses by this transaction, and that neither the
242   // compiler nor the hardware order this store earlier).
243   // ??? We might be able to avoid this release here if the compiler can't
244   // merge the release fence with the subsequent seq_cst fence.
245   tx->shared_state.store (-1, memory_order_release);
246   // We need this seq_cst fence here to avoid lost wake-ups.  Furthermore,
247   // the privatization safety implementation in gtm_thread::try_commit()
248   // relies on the existence of this seq_cst fence.
249   atomic_thread_fence (memory_order_seq_cst);
250   unsigned int sum = this->summary.load (memory_order_relaxed);
251   if (likely(!(sum & (a_writer | w_writer))))
252     return;
253
254   // There is a writer, either active or waiting for other readers or writers.
255   // Thus, enter the mutex-based slow path.
256   pthread_mutex_lock (&this->mutex);
257
258   // If there is a writer waiting for readers, wake it up. Only do that if we
259   // might be the last reader that could do the wake-up, otherwise skip the
260   // wake-up and decrease a_readers to publish that we have entered the slow
261   // path but skipped the wake-up.
262   if (this->a_readers > 0)
263     {
264       this->a_readers--;
265       if (this->a_readers == 0)
266         pthread_cond_signal(&this->c_confirmed_writers);
267     }
268
269   // We don't need to wake up any writers waiting for other writers. Active
270   // writers will take care of that.
271
272   pthread_mutex_unlock (&this->mutex);
273 }
274
275
276 // Release a RW lock from writing.
277
278 void
279 gtm_rwlock::write_unlock ()
280 {
281   pthread_mutex_lock (&this->mutex);
282
283   unsigned int sum = this->summary.load (memory_order_relaxed);
284   this->summary.store (sum & ~a_writer, memory_order_relaxed);
285
286   // If there is a waiting writer, wake it.
287   if (unlikely (sum & w_writer))
288     pthread_cond_signal (&this->c_writers);
289
290   // If there are waiting readers, wake them.
291   else if (unlikely (sum & w_reader))
292     pthread_cond_broadcast (&this->c_readers);
293
294   pthread_mutex_unlock (&this->mutex);
295 }
296
297 } // namespace GTM