Mercurial > hg > CbC > CbC_gcc
comparison libitm/method-ml.cc @ 111:04ced10e8804
gcc 7
author | kono |
---|---|
date | Fri, 27 Oct 2017 22:46:09 +0900 |
parents | |
children | 84e7813d76e9 |
comparison
equal
deleted
inserted
replaced
68:561a7518be6b | 111:04ced10e8804 |
---|---|
1 /* Copyright (C) 2012-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 | |
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 | |
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 | |
84 { | |
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 }; | |
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); | |
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); | |
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. | |
177 ml_mg::orec_iterator oi(addr, len); | |
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. | |
183 gtm_word o = o_ml_mg.orecs[oi.get()].load(memory_order_relaxed); | |
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. | |
209 if (unlikely (!o_ml_mg.orecs[oi.get()].compare_exchange_strong( | |
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(); | |
226 e->orec = o_ml_mg.orecs + oi.get(); | |
227 e->value = o; | |
228 } | |
229 oi.advance(); | |
230 } | |
231 while (!oi.reached_end()); | |
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 | |
309 ml_mg::orec_iterator oi(addr, len); | |
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. | |
317 gtm_word o = o_ml_mg.orecs[oi.get()].load(memory_order_acquire); | |
318 | |
319 if (likely (!ml_mg::is_more_recent_or_locked(o, snapshot))) | |
320 { | |
321 success: | |
322 gtm_rwlog_entry *e = tx->readlog.push(); | |
323 e->orec = o_ml_mg.orecs + oi.get(); | |
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 } | |
341 oi.advance(); | |
342 } | |
343 while (!oi.reached_end()); | |
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(); | |
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); | |
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 | |
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 | |
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 | |
656 ml_wt_dispatch() : abi_dispatch(false, true, false, false, 0, &o_ml_mg) | |
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 } |