OSDN Git Service

3471049083e03e3e1bee18ad6fa56eaac0e0adad
[pf3gnuchains/gcc-fork.git] / 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.  Note that direct assignment to
40       // an atomic object is memory_order_seq_cst.
41       tx->shared_state = 0;
42       if (likely(writers == 0))
43         return;
44
45       // There seems to be an active, waiting, or confirmed writer, so enter
46       // the futex-based slow path.
47
48       // Before waiting, we clear our read intent check whether there are any
49       // writers that might potentially wait for readers. If so, wake them.
50       // We need the barrier here for the same reason that we need it in
51       // read_unlock().
52       // TODO Potentially too many wake-ups. See comments in read_unlock().
53       tx->shared_state = -1;
54       if (writer_readers > 0)
55         {
56           writer_readers = 0;
57           futex_wake(&writer_readers, 1);
58         }
59
60       // Signal that there are waiting readers and wait until there is no
61       // writer anymore.
62       // TODO Spin here on writers for a while. Consider whether we woke
63       // any writers before?
64       while (writers)
65         {
66           // An active writer. Wait until it has finished. To avoid lost
67           // wake-ups, we need to use Dekker-like synchronization.
68           // Note that we cannot reset readers to zero when we see that there
69           // are no writers anymore after the barrier because this pending
70           // store could then lead to lost wake-ups at other readers.
71           readers = 1;
72           atomic_thread_fence(memory_order_acq_rel);
73           if (writers)
74             futex_wait(&readers, 1);
75         }
76
77       // And we try again to acquire a read lock.
78     }
79 }
80
81
82 // Acquire a RW lock for writing. Generic version that also works for
83 // upgrades.
84 // Note that an upgrade might fail (and thus waste previous work done during
85 // this transaction) if there is another thread that tried to go into serial
86 // mode earlier (i.e., upgrades do not have higher priority than pure writers).
87 // However, this seems rare enough to not consider it further as we need both
88 // a non-upgrade writer and a writer to happen to switch to serial mode
89 // concurrently. If we'd want to handle this, a writer waiting for readers
90 // would have to coordinate with later arriving upgrades and hand over the
91 // lock to them, including the the reader-waiting state. We can try to support
92 // this if this will actually happen often enough in real workloads.
93
94 bool
95 gtm_rwlock::write_lock_generic (gtm_thread *tx)
96 {
97   // Try to acquire the write lock.
98   unsigned int w;
99   if (unlikely((w = __sync_val_compare_and_swap(&writers, 0, 1)) != 0))
100     {
101       // If this is an upgrade, we must not wait for other writers or
102       // upgrades.
103       if (tx != 0)
104         return false;
105
106       // There is already a writer. If there are no other waiting writers,
107       // switch to contended mode.
108       // Note that this is actually an atomic exchange, not a TAS. Also,
109       // it's only guaranteed to have acquire semantics, whereas we need a
110       // full barrier to make the Dekker-style synchronization work. However,
111       // we rely on the xchg being a full barrier on the architectures that we
112       // consider here.
113       // ??? Use C++0x atomics as soon as they are available.
114       if (w != 2)
115         w = __sync_lock_test_and_set(&writers, 2);
116       while (w != 0)
117         {
118           futex_wait(&writers, 2);
119           w = __sync_lock_test_and_set(&writers, 2);
120         }
121     }
122
123   // We have acquired the writer side of the R/W lock. Now wait for any
124   // readers that might still be active.
125   // We don't need an extra barrier here because the CAS and the xchg
126   // operations have full barrier semantics already.
127
128   // If this is an upgrade, we are not a reader anymore. This is only safe to
129   // do after we have acquired the writer lock.
130   // TODO In the worst case, this requires one wait/wake pair for each
131   // active reader. Reduce this!
132   if (tx != 0)
133     tx->shared_state = ~(typeof tx->shared_state)0;
134
135   for (gtm_thread *it = gtm_thread::list_of_threads; it != 0;
136       it = it->next_thread)
137     {
138       // Use a loop here to check reader flags again after waiting.
139       while (it->shared_state != ~(typeof it->shared_state)0)
140         {
141           // An active reader. Wait until it has finished. To avoid lost
142           // wake-ups, we need to use Dekker-like synchronization.
143           // Note that we can reset writer_readers to zero when we see after
144           // the barrier that the reader has finished in the meantime;
145           // however, this is only possible because we are the only writer.
146           // TODO Spin for a while on this reader flag.
147           writer_readers = 1;
148           __sync_synchronize();
149           if (it->shared_state != ~(typeof it->shared_state)0)
150             futex_wait(&writer_readers, 1);
151           else
152             writer_readers = 0;
153         }
154     }
155
156   return true;
157 }
158
159 // Acquire a RW lock for writing.
160
161 void
162 gtm_rwlock::write_lock ()
163 {
164   write_lock_generic (0);
165 }
166
167
168 // Upgrade a RW lock that has been locked for reading to a writing lock.
169 // Do this without possibility of another writer incoming.  Return false
170 // if this attempt fails (i.e. another thread also upgraded).
171
172 bool
173 gtm_rwlock::write_upgrade (gtm_thread *tx)
174 {
175   return write_lock_generic (tx);
176 }
177
178
179 // Release a RW lock from reading.
180
181 void
182 gtm_rwlock::read_unlock (gtm_thread *tx)
183 {
184   tx->shared_state = ~(typeof tx->shared_state)0;
185
186   // If there is a writer waiting for readers, wake it up. We need the barrier
187   // to avoid lost wake-ups.
188   // ??? We might not be the last active reader, so the wake-up might happen
189   // too early. How do we avoid this without slowing down readers too much?
190   // Each reader could scan the list of txns for other active readers but
191   // this can result in many cache misses. Use combining instead?
192   // TODO Sends out one wake-up for each reader in the worst case.
193   __sync_synchronize();
194   if (unlikely(writer_readers > 0))
195     {
196       writer_readers = 0;
197       futex_wake(&writer_readers, 1);
198     }
199 }
200
201
202 // Release a RW lock from writing.
203
204 void
205 gtm_rwlock::write_unlock ()
206 {
207   // This is supposed to be a full barrier.
208   if (__sync_fetch_and_sub(&writers, 1) == 2)
209     {
210       // There might be waiting writers, so wake them.
211       writers = 0;
212       if (futex_wake(&writers, 1) == 0)
213         {
214           // If we did not wake any waiting writers, we might indeed be the
215           // last writer (this can happen because write_lock_generic()
216           // exchanges 0 or 1 to 2 and thus might go to contended mode even if
217           // no other thread holds the write lock currently). Therefore, we
218           // have to wake up readers here as well.
219           futex_wake(&readers, INT_MAX);
220         }
221       return;
222     }
223   // No waiting writers, so wake up all waiting readers.
224   // Because the fetch_and_sub is a full barrier already, we don't need
225   // another barrier here (as in read_unlock()).
226   if (readers > 0)
227     {
228       readers = 0;
229       futex_wake(&readers, INT_MAX);
230     }
231 }
232
233 } // namespace GTM