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