1/* Copyright (C) 2011-2017 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
29namespace GTM HIDDEN {
30
31// Acquire a RW lock for reading.
32
33void
34gtm_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 fence ensures that this happens
40 // in exactly this order.
41 tx->shared_state.store (0, memory_order_relaxed);
42 atomic_thread_fence (memory_order_seq_cst);
43 if (likely (writers.load (memory_order_relaxed) == 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.store (-1, memory_order_relaxed);
55 atomic_thread_fence (memory_order_seq_cst);
56 if (writer_readers.load (memory_order_relaxed) > 0)
57 {
58 writer_readers.store (0, memory_order_relaxed);
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.load (memory_order_relaxed))
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.store (1, memory_order_relaxed);
74 atomic_thread_fence (memory_order_seq_cst);
75 if (writers.load (memory_order_relaxed))
76 futex_wait(&readers, 1);
77 else
78 {
79 // There is no writer, actually. However, we can have enabled
80 // a futex_wait in other readers by previously setting readers
81 // to 1, so we have to wake them up because there is no writer
82 // that will do that. We don't know whether the wake-up is
83 // really necessary, but we can get lost wake-up situations
84 // otherwise.
85 // No additional barrier nor a nonrelaxed load is required due
86 // to coherency constraints. write_unlock() checks readers to
87 // see if any wake-up is necessary, but it is not possible that
88 // a reader's store prevents a required later writer wake-up;
89 // If the waking reader's store (value 0) is in modification
90 // order after the waiting readers store (value 1), then the
91 // latter will have to read 0 in the futex due to coherency
92 // constraints and the happens-before enforced by the futex
93 // (paragraph 6.10 in the standard, 6.19.4 in the Batty et al
94 // TR); second, the writer will be forced to read in
95 // modification order too due to Dekker-style synchronization
96 // with the waiting reader (see write_unlock()).
97 // ??? Can we avoid the wake-up if readers is zero (like in
98 // write_unlock())? Anyway, this might happen too infrequently
99 // to improve performance significantly.
100 readers.store (0, memory_order_relaxed);
101 futex_wake(&readers, INT_MAX);
102 }
103 }
104
105 // And we try again to acquire a read lock.
106 }
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
122bool
123gtm_rwlock::write_lock_generic (gtm_thread *tx)
124{
125 // Try to acquire the write lock. Relaxed MO is fine because of the
126 // additional fence below.
127 int w = 0;
128 if (unlikely (!writers.compare_exchange_strong (w, 1, memory_order_relaxed)))
129 {
130 // If this is an upgrade, we must not wait for other writers or
131 // upgrades.
132 if (tx != 0)
133 return false;
134
135 // There is already a writer. If there are no other waiting writers,
136 // switch to contended mode. We need seq_cst memory order to make the
137 // Dekker-style synchronization work.
138 if (w != 2)
139 w = writers.exchange (2, memory_order_relaxed);
140 while (w != 0)
141 {
142 futex_wait(&writers, 2);
143 w = writers.exchange (2, memory_order_relaxed);
144 }
145 }
146 // This fence is both required for the Dekker-like synchronization we do
147 // here and is the acquire MO required to make us synchronize-with prior
148 // writers.
149 atomic_thread_fence (memory_order_seq_cst);
150
151 // We have acquired the writer side of the R/W lock. Now wait for any
152 // readers that might still be active.
153 // TODO In the worst case, this requires one wait/wake pair for each
154 // active reader. Reduce this!
155 for (gtm_thread *it = gtm_thread::list_of_threads; it != 0;
156 it = it->next_thread)
157 {
158 if (it == tx)
159 continue;
160 // Use a loop here to check reader flags again after waiting.
161 while (it->shared_state.load (memory_order_relaxed)
162 != ~(typeof it->shared_state)0)
163 {
164 // If this is an upgrade, we have to break deadlocks with
165 // privatization safety. This may fail on our side, in which
166 // case we need to cancel our attempt to upgrade. Also, we do not
167 // block but just spin so that we never have to be woken.
168 if (tx != 0)
169 {
170 if (!abi_disp()->snapshot_most_recent ())
171 {
172 write_unlock ();
173 return false;
174 }
175 continue;
176 }
177 // An active reader. Wait until it has finished. To avoid lost
178 // wake-ups, we need to use Dekker-like synchronization.
179 // Note that we can reset writer_readers to zero when we see after
180 // the barrier that the reader has finished in the meantime;
181 // however, this is only possible because we are the only writer.
182 // TODO Spin for a while on this reader flag.
183 writer_readers.store (1, memory_order_relaxed);
184 atomic_thread_fence (memory_order_seq_cst);
185 if (it->shared_state.load (memory_order_relaxed)
186 != ~(typeof it->shared_state)0)
187 futex_wait(&writer_readers, 1);
188 else
189 writer_readers.store (0, memory_order_relaxed);
190 }
191 }
192
193 return true;
194}
195
196// Acquire a RW lock for writing.
197
198void
199gtm_rwlock::write_lock ()
200{
201 write_lock_generic (0);
202}
203
204
205// Upgrade a RW lock that has been locked for reading to a writing lock.
206// Do this without possibility of another writer incoming. Return false
207// if this attempt fails (i.e. another thread also upgraded).
208
209bool
210gtm_rwlock::write_upgrade (gtm_thread *tx)
211{
212 return write_lock_generic (tx);
213}
214
215
216// Has to be called iff the previous upgrade was successful and after it is
217// safe for the transaction to not be marked as a reader anymore.
218
219void
220gtm_rwlock::write_upgrade_finish (gtm_thread *tx)
221{
222 // We are not a reader anymore. This is only safe to do after we have
223 // acquired the writer lock.
224 tx->shared_state.store (-1, memory_order_release);
225}
226
227
228// Release a RW lock from reading.
229
230void
231gtm_rwlock::read_unlock (gtm_thread *tx)
232{
233 // We only need release memory order here because of privatization safety
234 // (this ensures that marking the transaction as inactive happens after
235 // any prior data accesses by this transaction, and that neither the
236 // compiler nor the hardware order this store earlier).
237 // ??? We might be able to avoid this release here if the compiler can't
238 // merge the release fence with the subsequent seq_cst fence.
239 tx->shared_state.store (-1, memory_order_release);
240
241 // If there is a writer waiting for readers, wake it up. We need the fence
242 // to avoid lost wake-ups. Furthermore, the privatization safety
243 // implementation in gtm_thread::try_commit() relies on the existence of
244 // this seq_cst fence.
245 // ??? We might not be the last active reader, so the wake-up might happen
246 // too early. How do we avoid this without slowing down readers too much?
247 // Each reader could scan the list of txns for other active readers but
248 // this can result in many cache misses. Use combining instead?
249 // TODO Sends out one wake-up for each reader in the worst case.
250 atomic_thread_fence (memory_order_seq_cst);
251 if (unlikely (writer_readers.load (memory_order_relaxed) > 0))
252 {
253 // No additional barrier needed here (see write_unlock()).
254 writer_readers.store (0, memory_order_relaxed);
255 futex_wake(&writer_readers, 1);
256 }
257}
258
259
260// Release a RW lock from writing.
261
262void
263gtm_rwlock::write_unlock ()
264{
265 // Release MO so that we synchronize with subsequent writers.
266 if (writers.exchange (0, memory_order_release) == 2)
267 {
268 // There might be waiting writers, so wake them. If we woke any thread,
269 // we assume it to indeed be a writer; waiting writers will never give
270 // up, so we can assume that they will take care of anything else such
271 // as waking readers.
272 if (futex_wake(&writers, 1) > 0)
273 return;
274 // If we did not wake any waiting writers, we might indeed be the last
275 // writer (this can happen because write_lock_generic() exchanges 0 or 1
276 // to 2 and thus might go to contended mode even if no other thread
277 // holds the write lock currently). Therefore, we have to fall through
278 // to the normal reader wake-up code.
279 }
280 // This fence is required because we do Dekker-like synchronization here.
281 atomic_thread_fence (memory_order_seq_cst);
282 // No waiting writers, so wake up all waiting readers.
283 if (readers.load (memory_order_relaxed) > 0)
284 {
285 // No additional barrier needed here. The previous load must be in
286 // modification order because of the coherency constraints. Late stores
287 // by a reader are not a problem because readers do Dekker-style
288 // synchronization on writers.
289 readers.store (0, memory_order_relaxed);
290 futex_wake(&readers, INT_MAX);
291 }
292}
293
294} // namespace GTM
295