]>
Commit | Line | Data |
---|---|---|
99dee823 | 1 | /* Copyright (C) 2012-2021 Free Software Foundation, Inc. |
31772c95 TR |
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 | ||
27 | using namespace GTM; | |
28 | ||
29 | namespace { | |
30 | ||
31 | // This group consists of all TM methods that synchronize via multiple locks | |
32 | // (or ownership records). | |
33 | struct ml_mg : public method_group | |
34 | { | |
35 | static const gtm_word LOCK_BIT = (~(gtm_word)0 >> 1) + 1; | |
36 | static const gtm_word INCARNATION_BITS = 3; | |
37 | static const gtm_word INCARNATION_MASK = 7; | |
38 | // Maximum time is all bits except the lock bit, the overflow reserve bit, | |
39 | // and the incarnation bits). | |
40 | static const gtm_word TIME_MAX = (~(gtm_word)0 >> (2 + INCARNATION_BITS)); | |
41 | // The overflow reserve bit is the MSB of the timestamp part of an orec, | |
42 | // so we can have TIME_MAX+1 pending timestamp increases before we overflow. | |
43 | static const gtm_word OVERFLOW_RESERVE = TIME_MAX + 1; | |
44 | ||
45 | static bool is_locked(gtm_word o) { return o & LOCK_BIT; } | |
46 | static gtm_word set_locked(gtm_thread *tx) | |
47 | { | |
48 | return ((uintptr_t)tx >> 1) | LOCK_BIT; | |
49 | } | |
50 | // Returns a time that includes the lock bit, which is required by both | |
51 | // validate() and is_more_recent_or_locked(). | |
52 | static gtm_word get_time(gtm_word o) { return o >> INCARNATION_BITS; } | |
53 | static gtm_word set_time(gtm_word time) { return time << INCARNATION_BITS; } | |
54 | static bool is_more_recent_or_locked(gtm_word o, gtm_word than_time) | |
55 | { | |
56 | // LOCK_BIT is the MSB; thus, if O is locked, it is larger than TIME_MAX. | |
57 | return get_time(o) > than_time; | |
58 | } | |
59 | static bool has_incarnation_left(gtm_word o) | |
60 | { | |
61 | return (o & INCARNATION_MASK) < INCARNATION_MASK; | |
62 | } | |
63 | static gtm_word inc_incarnation(gtm_word o) { return o + 1; } | |
64 | ||
65 | // The shared time base. | |
66 | atomic<gtm_word> time __attribute__((aligned(HW_CACHELINE_SIZE))); | |
67 | ||
68 | // The array of ownership records. | |
69 | atomic<gtm_word>* orecs __attribute__((aligned(HW_CACHELINE_SIZE))); | |
70 | char tailpadding[HW_CACHELINE_SIZE - sizeof(atomic<gtm_word>*)]; | |
71 | ||
e7f7330f TR |
72 | // Location-to-orec mapping. Stripes of 32B mapped to 2^16 orecs using |
73 | // multiplicative hashing. See Section 5.2.2 of Torvald Riegel's PhD thesis | |
74 | // for the background on this choice of hash function and parameters: | |
75 | // http://nbn-resolving.de/urn:nbn:de:bsz:14-qucosa-115596 | |
76 | // We pick the Mult32 hash because it works well with fewer orecs (i.e., | |
77 | // less space overhead and just 32b multiplication). | |
78 | // We may want to check and potentially change these settings once we get | |
79 | // better or just more benchmarks. | |
80 | static const gtm_word L2O_ORECS_BITS = 16; | |
81 | static const gtm_word L2O_ORECS = 1 << L2O_ORECS_BITS; | |
82 | // An iterator over the orecs covering the region [addr,addr+len). | |
83 | struct orec_iterator | |
31772c95 | 84 | { |
e7f7330f TR |
85 | static const gtm_word L2O_SHIFT = 5; |
86 | static const uint32_t L2O_MULT32 = 81007; | |
87 | uint32_t mult; | |
88 | size_t orec; | |
89 | size_t orec_end; | |
90 | orec_iterator (const void* addr, size_t len) | |
91 | { | |
92 | uint32_t a = (uintptr_t) addr >> L2O_SHIFT; | |
93 | uint32_t ae = ((uintptr_t) addr + len + (1 << L2O_SHIFT) - 1) | |
94 | >> L2O_SHIFT; | |
95 | mult = a * L2O_MULT32; | |
96 | orec = mult >> (32 - L2O_ORECS_BITS); | |
97 | // We can't really avoid this second multiplication unless we use a | |
98 | // branch instead or know more about the alignment of addr. (We often | |
99 | // know len at compile time because of instantiations of functions | |
100 | // such as _ITM_RU* for accesses of specific lengths. | |
101 | orec_end = (ae * L2O_MULT32) >> (32 - L2O_ORECS_BITS); | |
102 | } | |
103 | size_t get() { return orec; } | |
104 | void advance() | |
105 | { | |
106 | // We cannot simply increment orec because L2O_MULT32 is larger than | |
107 | // 1 << (32 - L2O_ORECS_BITS), and thus an increase of the stripe (i.e., | |
108 | // addr >> L2O_SHIFT) could increase the resulting orec index by more | |
109 | // than one; with the current parameters, we would roughly acquire a | |
110 | // fourth more orecs than necessary for regions covering more than orec. | |
111 | // Keeping mult around as extra state shouldn't matter much. | |
112 | mult += L2O_MULT32; | |
113 | orec = mult >> (32 - L2O_ORECS_BITS); | |
114 | } | |
115 | bool reached_end() { return orec == orec_end; } | |
116 | }; | |
31772c95 TR |
117 | |
118 | virtual void init() | |
119 | { | |
120 | // We assume that an atomic<gtm_word> is backed by just a gtm_word, so | |
121 | // starting with zeroed memory is fine. | |
122 | orecs = (atomic<gtm_word>*) xcalloc( | |
123 | sizeof(atomic<gtm_word>) * L2O_ORECS, true); | |
124 | // This store is only executed while holding the serial lock, so relaxed | |
125 | // memory order is sufficient here. | |
126 | time.store(0, memory_order_relaxed); | |
127 | } | |
128 | ||
129 | virtual void fini() | |
130 | { | |
131 | free(orecs); | |
132 | } | |
133 | ||
134 | // We only re-initialize when our time base overflows. Thus, only reset | |
135 | // the time base and the orecs but do not re-allocate the orec array. | |
136 | virtual void reinit() | |
137 | { | |
138 | // This store is only executed while holding the serial lock, so relaxed | |
139 | // memory order is sufficient here. Same holds for the memset. | |
140 | time.store(0, memory_order_relaxed); | |
c3684b7b MS |
141 | // The memset below isn't strictly kosher because it bypasses |
142 | // the non-trivial assignment operator defined by std::atomic. Using | |
143 | // a local void* is enough to prevent GCC from warning for this. | |
144 | void *p = orecs; | |
145 | memset(p, 0, sizeof(atomic<gtm_word>) * L2O_ORECS); | |
31772c95 TR |
146 | } |
147 | }; | |
148 | ||
149 | static ml_mg o_ml_mg; | |
150 | ||
151 | ||
152 | // The multiple lock, write-through TM method. | |
153 | // Maps each memory location to one of the orecs in the orec array, and then | |
154 | // acquires the associated orec eagerly before writing through. | |
155 | // Writes require undo-logging because we are dealing with several locks/orecs | |
156 | // and need to resolve deadlocks if necessary by aborting one of the | |
157 | // transactions. | |
158 | // Reads do time-based validation with snapshot time extensions. Incarnation | |
159 | // numbers are used to decrease contention on the time base (with those, | |
160 | // aborted transactions do not need to acquire a new version number for the | |
161 | // data that has been previously written in the transaction and needs to be | |
162 | // rolled back). | |
163 | // gtm_thread::shared_state is used to store a transaction's current | |
164 | // snapshot time (or commit time). The serial lock uses ~0 for inactive | |
165 | // transactions and 0 for active ones. Thus, we always have a meaningful | |
166 | // timestamp in shared_state that can be used to implement quiescence-based | |
167 | // privatization safety. | |
168 | class ml_wt_dispatch : public abi_dispatch | |
169 | { | |
170 | protected: | |
171 | static void pre_write(gtm_thread *tx, const void *addr, size_t len) | |
172 | { | |
173 | gtm_word snapshot = tx->shared_state.load(memory_order_relaxed); | |
174 | gtm_word locked_by_tx = ml_mg::set_locked(tx); | |
175 | ||
176 | // Lock all orecs that cover the region. | |
e7f7330f | 177 | ml_mg::orec_iterator oi(addr, len); |
31772c95 TR |
178 | do |
179 | { | |
180 | // Load the orec. Relaxed memory order is sufficient here because | |
181 | // either we have acquired the orec or we will try to acquire it with | |
182 | // a CAS with stronger memory order. | |
e7f7330f | 183 | gtm_word o = o_ml_mg.orecs[oi.get()].load(memory_order_relaxed); |
31772c95 TR |
184 | |
185 | // Check whether we have acquired the orec already. | |
186 | if (likely (locked_by_tx != o)) | |
187 | { | |
188 | // If not, acquire. Make sure that our snapshot time is larger or | |
189 | // equal than the orec's version to avoid masking invalidations of | |
190 | // our snapshot with our own writes. | |
191 | if (unlikely (ml_mg::is_locked(o))) | |
192 | tx->restart(RESTART_LOCKED_WRITE); | |
193 | ||
194 | if (unlikely (ml_mg::get_time(o) > snapshot)) | |
195 | { | |
196 | // We only need to extend the snapshot if we have indeed read | |
197 | // from this orec before. Given that we are an update | |
198 | // transaction, we will have to extend anyway during commit. | |
199 | // ??? Scan the read log instead, aborting if we have read | |
200 | // from data covered by this orec before? | |
201 | snapshot = extend(tx); | |
202 | } | |
203 | ||
204 | // We need acquire memory order here to synchronize with other | |
205 | // (ownership) releases of the orec. We do not need acq_rel order | |
206 | // because whenever another thread reads from this CAS' | |
207 | // modification, then it will abort anyway and does not rely on | |
208 | // any further happens-before relation to be established. | |
e7f7330f | 209 | if (unlikely (!o_ml_mg.orecs[oi.get()].compare_exchange_strong( |
31772c95 TR |
210 | o, locked_by_tx, memory_order_acquire))) |
211 | tx->restart(RESTART_LOCKED_WRITE); | |
212 | ||
213 | // We use an explicit fence here to avoid having to use release | |
214 | // memory order for all subsequent data stores. This fence will | |
215 | // synchronize with loads of the data with acquire memory order. | |
216 | // See post_load() for why this is necessary. | |
217 | // Adding require memory order to the prior CAS is not sufficient, | |
218 | // at least according to the Batty et al. formalization of the | |
219 | // memory model. | |
220 | atomic_thread_fence(memory_order_release); | |
221 | ||
222 | // We log the previous value here to be able to use incarnation | |
223 | // numbers when we have to roll back. | |
224 | // ??? Reserve capacity early to avoid capacity checks here? | |
225 | gtm_rwlog_entry *e = tx->writelog.push(); | |
e7f7330f | 226 | e->orec = o_ml_mg.orecs + oi.get(); |
31772c95 TR |
227 | e->value = o; |
228 | } | |
e7f7330f | 229 | oi.advance(); |
31772c95 | 230 | } |
e7f7330f | 231 | while (!oi.reached_end()); |
31772c95 TR |
232 | |
233 | // Do undo logging. We do not know which region prior writes logged | |
234 | // (even if orecs have been acquired), so just log everything. | |
235 | tx->undolog.log(addr, len); | |
236 | } | |
237 | ||
238 | static void pre_write(const void *addr, size_t len) | |
239 | { | |
240 | gtm_thread *tx = gtm_thr(); | |
241 | pre_write(tx, addr, len); | |
242 | } | |
243 | ||
244 | // Returns true iff all the orecs in our read log still have the same time | |
245 | // or have been locked by the transaction itself. | |
246 | static bool validate(gtm_thread *tx) | |
247 | { | |
248 | gtm_word locked_by_tx = ml_mg::set_locked(tx); | |
249 | // ??? This might get called from pre_load() via extend(). In that case, | |
250 | // we don't really need to check the new entries that pre_load() is | |
251 | // adding. Stop earlier? | |
252 | for (gtm_rwlog_entry *i = tx->readlog.begin(), *ie = tx->readlog.end(); | |
253 | i != ie; i++) | |
254 | { | |
255 | // Relaxed memory order is sufficient here because we do not need to | |
256 | // establish any new synchronizes-with relationships. We only need | |
257 | // to read a value that is as least as current as enforced by the | |
258 | // callers: extend() loads global time with acquire, and trycommit() | |
259 | // increments global time with acquire. Therefore, we will see the | |
260 | // most recent orec updates before the global time that we load. | |
261 | gtm_word o = i->orec->load(memory_order_relaxed); | |
262 | // We compare only the time stamp and the lock bit here. We know that | |
263 | // we have read only committed data before, so we can ignore | |
264 | // intermediate yet rolled-back updates presented by the incarnation | |
265 | // number bits. | |
266 | if (ml_mg::get_time(o) != ml_mg::get_time(i->value) | |
267 | && o != locked_by_tx) | |
268 | return false; | |
269 | } | |
270 | return true; | |
271 | } | |
272 | ||
273 | // Tries to extend the snapshot to a more recent time. Returns the new | |
274 | // snapshot time and updates TX->SHARED_STATE. If the snapshot cannot be | |
275 | // extended to the current global time, TX is restarted. | |
276 | static gtm_word extend(gtm_thread *tx) | |
277 | { | |
278 | // We read global time here, even if this isn't strictly necessary | |
279 | // because we could just return the maximum of the timestamps that | |
280 | // validate sees. However, the potential cache miss on global time is | |
281 | // probably a reasonable price to pay for avoiding unnecessary extensions | |
282 | // in the future. | |
283 | // We need acquire memory oder because we have to synchronize with the | |
284 | // increment of global time by update transactions, whose lock | |
285 | // acquisitions we have to observe (also see trycommit()). | |
286 | gtm_word snapshot = o_ml_mg.time.load(memory_order_acquire); | |
287 | if (!validate(tx)) | |
288 | tx->restart(RESTART_VALIDATE_READ); | |
289 | ||
290 | // Update our public snapshot time. Probably useful to decrease waiting | |
291 | // due to quiescence-based privatization safety. | |
292 | // Use release memory order to establish synchronizes-with with the | |
293 | // privatizers; prior data loads should happen before the privatizers | |
294 | // potentially modify anything. | |
295 | tx->shared_state.store(snapshot, memory_order_release); | |
296 | return snapshot; | |
297 | } | |
298 | ||
299 | // First pass over orecs. Load and check all orecs that cover the region. | |
300 | // Write to read log, extend snapshot time if necessary. | |
301 | static gtm_rwlog_entry* pre_load(gtm_thread *tx, const void* addr, | |
302 | size_t len) | |
303 | { | |
304 | // Don't obtain an iterator yet because the log might get resized. | |
305 | size_t log_start = tx->readlog.size(); | |
306 | gtm_word snapshot = tx->shared_state.load(memory_order_relaxed); | |
307 | gtm_word locked_by_tx = ml_mg::set_locked(tx); | |
308 | ||
e7f7330f | 309 | ml_mg::orec_iterator oi(addr, len); |
31772c95 TR |
310 | do |
311 | { | |
312 | // We need acquire memory order here so that this load will | |
313 | // synchronize with the store that releases the orec in trycommit(). | |
314 | // In turn, this makes sure that subsequent data loads will read from | |
315 | // a visible sequence of side effects that starts with the most recent | |
316 | // store to the data right before the release of the orec. | |
e7f7330f | 317 | gtm_word o = o_ml_mg.orecs[oi.get()].load(memory_order_acquire); |
31772c95 TR |
318 | |
319 | if (likely (!ml_mg::is_more_recent_or_locked(o, snapshot))) | |
320 | { | |
321 | success: | |
322 | gtm_rwlog_entry *e = tx->readlog.push(); | |
e7f7330f | 323 | e->orec = o_ml_mg.orecs + oi.get(); |
31772c95 TR |
324 | e->value = o; |
325 | } | |
326 | else if (!ml_mg::is_locked(o)) | |
327 | { | |
328 | // We cannot read this part of the region because it has been | |
329 | // updated more recently than our snapshot time. If we can extend | |
330 | // our snapshot, then we can read. | |
331 | snapshot = extend(tx); | |
332 | goto success; | |
333 | } | |
334 | else | |
335 | { | |
336 | // If the orec is locked by us, just skip it because we can just | |
337 | // read from it. Otherwise, restart the transaction. | |
338 | if (o != locked_by_tx) | |
339 | tx->restart(RESTART_LOCKED_READ); | |
340 | } | |
e7f7330f | 341 | oi.advance(); |
31772c95 | 342 | } |
e7f7330f | 343 | while (!oi.reached_end()); |
31772c95 TR |
344 | return &tx->readlog[log_start]; |
345 | } | |
346 | ||
347 | // Second pass over orecs, verifying that the we had a consistent read. | |
348 | // Restart the transaction if any of the orecs is locked by another | |
349 | // transaction. | |
350 | static void post_load(gtm_thread *tx, gtm_rwlog_entry* log) | |
351 | { | |
352 | for (gtm_rwlog_entry *end = tx->readlog.end(); log != end; log++) | |
353 | { | |
354 | // Check that the snapshot is consistent. We expect the previous data | |
355 | // load to have acquire memory order, or be atomic and followed by an | |
356 | // acquire fence. | |
357 | // As a result, the data load will synchronize with the release fence | |
358 | // issued by the transactions whose data updates the data load has read | |
359 | // from. This forces the orec load to read from a visible sequence of | |
360 | // side effects that starts with the other updating transaction's | |
361 | // store that acquired the orec and set it to locked. | |
362 | // We therefore either read a value with the locked bit set (and | |
363 | // restart) or read an orec value that was written after the data had | |
364 | // been written. Either will allow us to detect inconsistent reads | |
365 | // because it will have a higher/different value. | |
366 | // Also note that differently to validate(), we compare the raw value | |
367 | // of the orec here, including incarnation numbers. We must prevent | |
368 | // returning uncommitted data from loads (whereas when validating, we | |
369 | // already performed a consistent load). | |
370 | gtm_word o = log->orec->load(memory_order_relaxed); | |
371 | if (log->value != o) | |
372 | tx->restart(RESTART_VALIDATE_READ); | |
373 | } | |
374 | } | |
375 | ||
376 | template <typename V> static V load(const V* addr, ls_modifier mod) | |
377 | { | |
378 | // Read-for-write should be unlikely, but we need to handle it or will | |
379 | // break later WaW optimizations. | |
380 | if (unlikely(mod == RfW)) | |
381 | { | |
382 | pre_write(addr, sizeof(V)); | |
383 | return *addr; | |
384 | } | |
385 | if (unlikely(mod == RaW)) | |
386 | return *addr; | |
387 | // ??? Optimize for RaR? | |
388 | ||
389 | gtm_thread *tx = gtm_thr(); | |
390 | gtm_rwlog_entry* log = pre_load(tx, addr, sizeof(V)); | |
391 | ||
392 | // Load the data. | |
393 | // This needs to have acquire memory order (see post_load()). | |
394 | // Alternatively, we can put an acquire fence after the data load but this | |
395 | // is probably less efficient. | |
396 | // FIXME We would need an atomic load with acquire memory order here but | |
397 | // we can't just forge an atomic load for nonatomic data because this | |
398 | // might not work on all implementations of atomics. However, we need | |
399 | // the acquire memory order and we can only establish this if we link | |
400 | // it to the matching release using a reads-from relation between atomic | |
401 | // loads. Also, the compiler is allowed to optimize nonatomic accesses | |
402 | // differently than atomic accesses (e.g., if the load would be moved to | |
403 | // after the fence, we potentially don't synchronize properly anymore). | |
404 | // Instead of the following, just use an ordinary load followed by an | |
405 | // acquire fence, and hope that this is good enough for now: | |
406 | // V v = atomic_load_explicit((atomic<V>*)addr, memory_order_acquire); | |
407 | V v = *addr; | |
408 | atomic_thread_fence(memory_order_acquire); | |
409 | ||
410 | // ??? Retry the whole load if it wasn't consistent? | |
411 | post_load(tx, log); | |
412 | ||
413 | return v; | |
414 | } | |
415 | ||
416 | template <typename V> static void store(V* addr, const V value, | |
417 | ls_modifier mod) | |
418 | { | |
419 | if (likely(mod != WaW)) | |
420 | pre_write(addr, sizeof(V)); | |
421 | // FIXME We would need an atomic store here but we can't just forge an | |
422 | // atomic load for nonatomic data because this might not work on all | |
423 | // implementations of atomics. However, we need this store to link the | |
424 | // release fence in pre_write() to the acquire operation in load, which | |
425 | // is only guaranteed if we have a reads-from relation between atomic | |
426 | // accesses. Also, the compiler is allowed to optimize nonatomic accesses | |
427 | // differently than atomic accesses (e.g., if the store would be moved | |
428 | // to before the release fence in pre_write(), things could go wrong). | |
429 | // atomic_store_explicit((atomic<V>*)addr, value, memory_order_relaxed); | |
430 | *addr = value; | |
431 | } | |
432 | ||
433 | public: | |
434 | static void memtransfer_static(void *dst, const void* src, size_t size, | |
435 | bool may_overlap, ls_modifier dst_mod, ls_modifier src_mod) | |
436 | { | |
437 | gtm_rwlog_entry* log = 0; | |
438 | gtm_thread *tx = 0; | |
439 | ||
440 | if (src_mod == RfW) | |
441 | { | |
442 | tx = gtm_thr(); | |
443 | pre_write(tx, src, size); | |
444 | } | |
445 | else if (src_mod != RaW && src_mod != NONTXNAL) | |
446 | { | |
447 | tx = gtm_thr(); | |
448 | log = pre_load(tx, src, size); | |
449 | } | |
450 | // ??? Optimize for RaR? | |
451 | ||
452 | if (dst_mod != NONTXNAL && dst_mod != WaW) | |
453 | { | |
454 | if (src_mod != RfW && (src_mod == RaW || src_mod == NONTXNAL)) | |
455 | tx = gtm_thr(); | |
456 | pre_write(tx, dst, size); | |
457 | } | |
458 | ||
459 | // FIXME We should use atomics here (see store()). Let's just hope that | |
460 | // memcpy/memmove are good enough. | |
461 | if (!may_overlap) | |
462 | ::memcpy(dst, src, size); | |
463 | else | |
464 | ::memmove(dst, src, size); | |
465 | ||
466 | // ??? Retry the whole memtransfer if it wasn't consistent? | |
467 | if (src_mod != RfW && src_mod != RaW && src_mod != NONTXNAL) | |
468 | { | |
469 | // See load() for why we need the acquire fence here. | |
470 | atomic_thread_fence(memory_order_acquire); | |
471 | post_load(tx, log); | |
472 | } | |
473 | } | |
474 | ||
475 | static void memset_static(void *dst, int c, size_t size, ls_modifier mod) | |
476 | { | |
477 | if (mod != WaW) | |
478 | pre_write(dst, size); | |
479 | // FIXME We should use atomics here (see store()). Let's just hope that | |
480 | // memset is good enough. | |
481 | ::memset(dst, c, size); | |
482 | } | |
483 | ||
484 | virtual gtm_restart_reason begin_or_restart() | |
485 | { | |
486 | // We don't need to do anything for nested transactions. | |
487 | gtm_thread *tx = gtm_thr(); | |
488 | if (tx->parent_txns.size() > 0) | |
489 | return NO_RESTART; | |
490 | ||
491 | // Read the current time, which becomes our snapshot time. | |
492 | // Use acquire memory oder so that we see the lock acquisitions by update | |
493 | // transcations that incremented the global time (see trycommit()). | |
494 | gtm_word snapshot = o_ml_mg.time.load(memory_order_acquire); | |
495 | // Re-initialize method group on time overflow. | |
496 | if (snapshot >= o_ml_mg.TIME_MAX) | |
497 | return RESTART_INIT_METHOD_GROUP; | |
498 | ||
499 | // We don't need to enforce any ordering for the following store. There | |
500 | // are no earlier data loads in this transaction, so the store cannot | |
501 | // become visible before those (which could lead to the violation of | |
502 | // privatization safety). The store can become visible after later loads | |
503 | // but this does not matter because the previous value will have been | |
504 | // smaller or equal (the serial lock will set shared_state to zero when | |
505 | // marking the transaction as active, and restarts enforce immediate | |
506 | // visibility of a smaller or equal value with a barrier (see | |
507 | // rollback()). | |
508 | tx->shared_state.store(snapshot, memory_order_relaxed); | |
509 | return NO_RESTART; | |
510 | } | |
511 | ||
512 | virtual bool trycommit(gtm_word& priv_time) | |
513 | { | |
514 | gtm_thread* tx = gtm_thr(); | |
515 | ||
516 | // If we haven't updated anything, we can commit. | |
517 | if (!tx->writelog.size()) | |
518 | { | |
519 | tx->readlog.clear(); | |
d2653984 TR |
520 | // We still need to ensure privatization safety, unfortunately. While |
521 | // we cannot have privatized anything by ourselves (because we are not | |
522 | // an update transaction), we can have observed the commits of | |
523 | // another update transaction that privatized something. Because any | |
524 | // commit happens before ensuring privatization, our snapshot and | |
525 | // commit can thus have happened before ensuring privatization safety | |
526 | // for this commit/snapshot time. Therefore, before we can return to | |
527 | // nontransactional code that might use the privatized data, we must | |
528 | // ensure privatization safety for our snapshot time. | |
529 | // This still seems to be better than not allowing use of the | |
530 | // snapshot time before privatization safety has been ensured because | |
531 | // we at least can run transactions such as this one, and in the | |
532 | // meantime the transaction producing this commit time might have | |
533 | // finished ensuring privatization safety for it. | |
534 | priv_time = tx->shared_state.load(memory_order_relaxed); | |
31772c95 TR |
535 | return true; |
536 | } | |
537 | ||
538 | // Get a commit time. | |
539 | // Overflow of o_ml_mg.time is prevented in begin_or_restart(). | |
540 | // We need acq_rel here because (1) the acquire part is required for our | |
541 | // own subsequent call to validate(), and the release part is necessary to | |
542 | // make other threads' validate() work as explained there and in extend(). | |
543 | gtm_word ct = o_ml_mg.time.fetch_add(1, memory_order_acq_rel) + 1; | |
544 | ||
545 | // Extend our snapshot time to at least our commit time. | |
546 | // Note that we do not need to validate if our snapshot time is right | |
547 | // before the commit time because we are never sharing the same commit | |
548 | // time with other transactions. | |
549 | // No need to reset shared_state, which will be modified by the serial | |
550 | // lock right after our commit anyway. | |
551 | gtm_word snapshot = tx->shared_state.load(memory_order_relaxed); | |
552 | if (snapshot < ct - 1 && !validate(tx)) | |
553 | return false; | |
554 | ||
555 | // Release orecs. | |
556 | // See pre_load() / post_load() for why we need release memory order. | |
557 | // ??? Can we use a release fence and relaxed stores? | |
558 | gtm_word v = ml_mg::set_time(ct); | |
559 | for (gtm_rwlog_entry *i = tx->writelog.begin(), *ie = tx->writelog.end(); | |
560 | i != ie; i++) | |
561 | i->orec->store(v, memory_order_release); | |
562 | ||
563 | // We're done, clear the logs. | |
564 | tx->writelog.clear(); | |
565 | tx->readlog.clear(); | |
566 | ||
567 | // Need to ensure privatization safety. Every other transaction must | |
568 | // have a snapshot time that is at least as high as our commit time | |
569 | // (i.e., our commit must be visible to them). | |
570 | priv_time = ct; | |
571 | return true; | |
572 | } | |
573 | ||
574 | virtual void rollback(gtm_transaction_cp *cp) | |
575 | { | |
576 | // We don't do anything for rollbacks of nested transactions. | |
577 | // ??? We could release locks here if we snapshot writelog size. readlog | |
578 | // is similar. This is just a performance optimization though. Nested | |
579 | // aborts should be rather infrequent, so the additional save/restore | |
580 | // overhead for the checkpoints could be higher. | |
581 | if (cp != 0) | |
582 | return; | |
583 | ||
584 | gtm_thread *tx = gtm_thr(); | |
585 | gtm_word overflow_value = 0; | |
586 | ||
587 | // Release orecs. | |
588 | for (gtm_rwlog_entry *i = tx->writelog.begin(), *ie = tx->writelog.end(); | |
589 | i != ie; i++) | |
590 | { | |
591 | // If possible, just increase the incarnation number. | |
592 | // See pre_load() / post_load() for why we need release memory order. | |
593 | // ??? Can we use a release fence and relaxed stores? (Same below.) | |
594 | if (ml_mg::has_incarnation_left(i->value)) | |
595 | i->orec->store(ml_mg::inc_incarnation(i->value), | |
596 | memory_order_release); | |
597 | else | |
598 | { | |
599 | // We have an incarnation overflow. Acquire a new timestamp, and | |
600 | // use it from now on as value for each orec whose incarnation | |
601 | // number cannot be increased. | |
602 | // Overflow of o_ml_mg.time is prevented in begin_or_restart(). | |
603 | // See pre_load() / post_load() for why we need release memory | |
604 | // order. | |
605 | if (!overflow_value) | |
606 | // Release memory order is sufficient but required here. | |
607 | // In contrast to the increment in trycommit(), we need release | |
608 | // for the same reason but do not need the acquire because we | |
609 | // do not validate subsequently. | |
610 | overflow_value = ml_mg::set_time( | |
611 | o_ml_mg.time.fetch_add(1, memory_order_release) + 1); | |
612 | i->orec->store(overflow_value, memory_order_release); | |
613 | } | |
614 | } | |
615 | ||
616 | // We need this release fence to ensure that privatizers see the | |
617 | // rolled-back original state (not any uncommitted values) when they read | |
618 | // the new snapshot time that we write in begin_or_restart(). | |
619 | atomic_thread_fence(memory_order_release); | |
620 | ||
621 | // We're done, clear the logs. | |
622 | tx->writelog.clear(); | |
623 | tx->readlog.clear(); | |
624 | } | |
625 | ||
629e4729 TR |
626 | virtual bool snapshot_most_recent() |
627 | { | |
628 | // This is the same code as in extend() except that we do not restart | |
629 | // on failure but simply return the result, and that we don't validate | |
630 | // if our snapshot is already most recent. | |
631 | gtm_thread* tx = gtm_thr(); | |
632 | gtm_word snapshot = o_ml_mg.time.load(memory_order_acquire); | |
633 | if (snapshot == tx->shared_state.load(memory_order_relaxed)) | |
634 | return true; | |
635 | if (!validate(tx)) | |
636 | return false; | |
637 | ||
638 | // Update our public snapshot time. Necessary so that we do not prevent | |
639 | // other transactions from ensuring privatization safety. | |
640 | tx->shared_state.store(snapshot, memory_order_release); | |
641 | return true; | |
642 | } | |
643 | ||
31772c95 TR |
644 | virtual bool supports(unsigned number_of_threads) |
645 | { | |
646 | // Each txn can commit and fail and rollback once before checking for | |
647 | // overflow, so this bounds the number of threads that we can support. | |
648 | // In practice, this won't be a problem but we check it anyway so that | |
649 | // we never break in the occasional weird situation. | |
650 | return (number_of_threads * 2 <= ml_mg::OVERFLOW_RESERVE); | |
651 | } | |
652 | ||
653 | CREATE_DISPATCH_METHODS(virtual, ) | |
654 | CREATE_DISPATCH_METHODS_MEM() | |
655 | ||
b679c813 | 656 | ml_wt_dispatch() : abi_dispatch(false, true, false, false, 0, &o_ml_mg) |
31772c95 TR |
657 | { } |
658 | }; | |
659 | ||
660 | } // anon namespace | |
661 | ||
662 | static const ml_wt_dispatch o_ml_wt_dispatch; | |
663 | ||
664 | abi_dispatch * | |
665 | GTM::dispatch_ml_wt () | |
666 | { | |
667 | return const_cast<ml_wt_dispatch *>(&o_ml_wt_dispatch); | |
668 | } |