]>
Commit | Line | Data |
---|---|---|
8d9254fc | 1 | /* Copyright (C) 2011-2020 Free Software Foundation, Inc. |
0a35513e AH |
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 | |
799142bf TR |
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)) | |
0a35513e AH |
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(). | |
799142bf TR |
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) | |
0a35513e | 57 | { |
799142bf | 58 | writer_readers.store (0, memory_order_relaxed); |
0a35513e AH |
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? | |
799142bf | 66 | while (writers.load (memory_order_relaxed)) |
0a35513e AH |
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. | |
799142bf TR |
73 | readers.store (1, memory_order_relaxed); |
74 | atomic_thread_fence (memory_order_seq_cst); | |
75 | if (writers.load (memory_order_relaxed)) | |
0a35513e | 76 | futex_wait(&readers, 1); |
0d23faac TR |
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 | } | |
0a35513e AH |
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 | ||
122 | bool | |
123 | gtm_rwlock::write_lock_generic (gtm_thread *tx) | |
124 | { | |
e89137ce TR |
125 | // Try to acquire the write lock. Relaxed MO is fine because of the |
126 | // additional fence below. | |
799142bf | 127 | int w = 0; |
e89137ce | 128 | if (unlikely (!writers.compare_exchange_strong (w, 1, memory_order_relaxed))) |
0a35513e AH |
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, | |
799142bf TR |
136 | // switch to contended mode. We need seq_cst memory order to make the |
137 | // Dekker-style synchronization work. | |
0a35513e | 138 | if (w != 2) |
e89137ce | 139 | w = writers.exchange (2, memory_order_relaxed); |
0a35513e AH |
140 | while (w != 0) |
141 | { | |
142 | futex_wait(&writers, 2); | |
e89137ce | 143 | w = writers.exchange (2, memory_order_relaxed); |
0a35513e AH |
144 | } |
145 | } | |
e89137ce TR |
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); | |
0a35513e AH |
150 | |
151 | // We have acquired the writer side of the R/W lock. Now wait for any | |
152 | // readers that might still be active. | |
0a35513e AH |
153 | // TODO In the worst case, this requires one wait/wake pair for each |
154 | // active reader. Reduce this! | |
0a35513e AH |
155 | for (gtm_thread *it = gtm_thread::list_of_threads; it != 0; |
156 | it = it->next_thread) | |
157 | { | |
610e3901 TR |
158 | if (it == tx) |
159 | continue; | |
0a35513e | 160 | // Use a loop here to check reader flags again after waiting. |
799142bf TR |
161 | while (it->shared_state.load (memory_order_relaxed) |
162 | != ~(typeof it->shared_state)0) | |
0a35513e | 163 | { |
629e4729 TR |
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 | } | |
0a35513e AH |
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. | |
799142bf TR |
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) | |
0a35513e AH |
187 | futex_wait(&writer_readers, 1); |
188 | else | |
799142bf | 189 | writer_readers.store (0, memory_order_relaxed); |
0a35513e AH |
190 | } |
191 | } | |
192 | ||
193 | return true; | |
194 | } | |
195 | ||
196 | // Acquire a RW lock for writing. | |
197 | ||
198 | void | |
199 | gtm_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 | ||
209 | bool | |
210 | gtm_rwlock::write_upgrade (gtm_thread *tx) | |
211 | { | |
212 | return write_lock_generic (tx); | |
213 | } | |
214 | ||
215 | ||
610e3901 TR |
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 | ||
219 | void | |
220 | gtm_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 | ||
0a35513e AH |
228 | // Release a RW lock from reading. |
229 | ||
230 | void | |
231 | gtm_rwlock::read_unlock (gtm_thread *tx) | |
232 | { | |
799142bf TR |
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. | |
0a35513e AH |
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. | |
799142bf TR |
250 | atomic_thread_fence (memory_order_seq_cst); |
251 | if (unlikely (writer_readers.load (memory_order_relaxed) > 0)) | |
0a35513e | 252 | { |
799142bf TR |
253 | // No additional barrier needed here (see write_unlock()). |
254 | writer_readers.store (0, memory_order_relaxed); | |
0a35513e AH |
255 | futex_wake(&writer_readers, 1); |
256 | } | |
257 | } | |
258 | ||
259 | ||
260 | // Release a RW lock from writing. | |
261 | ||
262 | void | |
263 | gtm_rwlock::write_unlock () | |
264 | { | |
e89137ce TR |
265 | // Release MO so that we synchronize with subsequent writers. |
266 | if (writers.exchange (0, memory_order_release) == 2) | |
0a35513e | 267 | { |
e89137ce TR |
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) | |
999bcff5 | 273 | return; |
e89137ce TR |
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. | |
0a35513e | 279 | } |
e89137ce TR |
280 | // This fence is required because we do Dekker-like synchronization here. |
281 | atomic_thread_fence (memory_order_seq_cst); | |
0a35513e | 282 | // No waiting writers, so wake up all waiting readers. |
799142bf | 283 | if (readers.load (memory_order_relaxed) > 0) |
0a35513e | 284 | { |
799142bf TR |
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); | |
0a35513e AH |
290 | futex_wake(&readers, INT_MAX); |
291 | } | |
292 | } | |
293 | ||
294 | } // namespace GTM |