OSDN Git Service

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