Roman Elizarov | fadf8c8 | 2017-03-02 23:36:06 +0300 | [diff] [blame] | 1 | /* |
Roman Elizarov | 1f74a2d | 2018-06-29 19:19:45 +0300 | [diff] [blame^] | 2 | * Copyright 2016-2018 JetBrains s.r.o. Use of this source code is governed by the Apache 2.0 license. |
Roman Elizarov | fadf8c8 | 2017-03-02 23:36:06 +0300 | [diff] [blame] | 3 | */ |
| 4 | |
Roman Elizarov | ee7c0eb | 2017-02-16 15:29:28 +0300 | [diff] [blame] | 5 | package kotlinx.coroutines.experimental.internal |
| 6 | |
Roman Elizarov | 7753f8e | 2017-08-15 11:16:33 +0300 | [diff] [blame] | 7 | import kotlinx.atomicfu.atomic |
Roman Elizarov | ee7c0eb | 2017-02-16 15:29:28 +0300 | [diff] [blame] | 8 | |
| 9 | /** |
| 10 | * The most abstract operation that can be in process. Other threads observing an instance of this |
| 11 | * class in the fields of their object shall invoke [perform] to help. |
| 12 | * |
| 13 | * @suppress **This is unstable API and it is subject to change.** |
| 14 | */ |
| 15 | public abstract class OpDescriptor { |
| 16 | /** |
| 17 | * Returns `null` is operation was performed successfully or some other |
| 18 | * object that indicates the failure reason. |
| 19 | */ |
| 20 | abstract fun perform(affected: Any?): Any? |
| 21 | } |
| 22 | |
Roman Elizarov | 7753f8e | 2017-08-15 11:16:33 +0300 | [diff] [blame] | 23 | private val NO_DECISION: Any = Symbol("NO_DECISION") |
| 24 | |
Roman Elizarov | ee7c0eb | 2017-02-16 15:29:28 +0300 | [diff] [blame] | 25 | /** |
| 26 | * Descriptor for multi-word atomic operation. |
| 27 | * Based on paper |
Roman Elizarov | 7753f8e | 2017-08-15 11:16:33 +0300 | [diff] [blame] | 28 | * ["A Practical Multi-Word Compare-and-Swap Operation"](http://www.cl.cam.ac.uk/research/srgnetos/papers/2002-casn.pdf) |
Roman Elizarov | ee7c0eb | 2017-02-16 15:29:28 +0300 | [diff] [blame] | 29 | * by Timothy L. Harris, Keir Fraser and Ian A. Pratt. |
| 30 | * |
| 31 | * Note: parts of atomic operation must be globally ordered. Otherwise, this implementation will produce |
Roman Elizarov | aa461cf | 2018-04-11 13:20:29 +0300 | [diff] [blame] | 32 | * `StackOverflowError`. |
Roman Elizarov | ee7c0eb | 2017-02-16 15:29:28 +0300 | [diff] [blame] | 33 | * |
| 34 | * @suppress **This is unstable API and it is subject to change.** |
| 35 | */ |
Roman Elizarov | d82b3a9 | 2017-06-23 21:52:08 +0300 | [diff] [blame] | 36 | public abstract class AtomicOp<in T> : OpDescriptor() { |
Roman Elizarov | 7753f8e | 2017-08-15 11:16:33 +0300 | [diff] [blame] | 37 | private val _consensus = atomic<Any?>(NO_DECISION) |
Roman Elizarov | ee7c0eb | 2017-02-16 15:29:28 +0300 | [diff] [blame] | 38 | |
Roman Elizarov | 7753f8e | 2017-08-15 11:16:33 +0300 | [diff] [blame] | 39 | val isDecided: Boolean get() = _consensus.value !== NO_DECISION |
Roman Elizarov | ee7c0eb | 2017-02-16 15:29:28 +0300 | [diff] [blame] | 40 | |
Roman Elizarov | 1216e91 | 2017-02-22 09:57:06 +0300 | [diff] [blame] | 41 | fun tryDecide(decision: Any?): Boolean { |
Roman Elizarov | 7753f8e | 2017-08-15 11:16:33 +0300 | [diff] [blame] | 42 | check(decision !== NO_DECISION) |
| 43 | return _consensus.compareAndSet(NO_DECISION, decision) |
Roman Elizarov | 1216e91 | 2017-02-22 09:57:06 +0300 | [diff] [blame] | 44 | } |
| 45 | |
Roman Elizarov | 7753f8e | 2017-08-15 11:16:33 +0300 | [diff] [blame] | 46 | private fun decide(decision: Any?): Any? = if (tryDecide(decision)) decision else _consensus.value |
Roman Elizarov | 1216e91 | 2017-02-22 09:57:06 +0300 | [diff] [blame] | 47 | |
Roman Elizarov | d82b3a9 | 2017-06-23 21:52:08 +0300 | [diff] [blame] | 48 | abstract fun prepare(affected: T): Any? // `null` if Ok, or failure reason |
Roman Elizarov | 1216e91 | 2017-02-22 09:57:06 +0300 | [diff] [blame] | 49 | |
Roman Elizarov | d82b3a9 | 2017-06-23 21:52:08 +0300 | [diff] [blame] | 50 | abstract fun complete(affected: T, failure: Any?) // failure != null if failed to prepare op |
Roman Elizarov | ee7c0eb | 2017-02-16 15:29:28 +0300 | [diff] [blame] | 51 | |
| 52 | // returns `null` on success |
Roman Elizarov | d82b3a9 | 2017-06-23 21:52:08 +0300 | [diff] [blame] | 53 | @Suppress("UNCHECKED_CAST") |
Roman Elizarov | ee7c0eb | 2017-02-16 15:29:28 +0300 | [diff] [blame] | 54 | final override fun perform(affected: Any?): Any? { |
| 55 | // make decision on status |
Roman Elizarov | 7753f8e | 2017-08-15 11:16:33 +0300 | [diff] [blame] | 56 | var decision = this._consensus.value |
Vsevolod Tolstopyatov | 2cdbfd7 | 2018-04-22 18:26:14 +0300 | [diff] [blame] | 57 | if (decision === NO_DECISION) { |
Roman Elizarov | d82b3a9 | 2017-06-23 21:52:08 +0300 | [diff] [blame] | 58 | decision = decide(prepare(affected as T)) |
Vsevolod Tolstopyatov | 2cdbfd7 | 2018-04-22 18:26:14 +0300 | [diff] [blame] | 59 | } |
| 60 | |
Roman Elizarov | d82b3a9 | 2017-06-23 21:52:08 +0300 | [diff] [blame] | 61 | complete(affected as T, decision) |
Roman Elizarov | ee7c0eb | 2017-02-16 15:29:28 +0300 | [diff] [blame] | 62 | return decision |
| 63 | } |
| 64 | } |
| 65 | |
| 66 | /** |
| 67 | * A part of multi-step atomic operation [AtomicOp]. |
| 68 | * |
| 69 | * @suppress **This is unstable API and it is subject to change.** |
| 70 | */ |
| 71 | public abstract class AtomicDesc { |
Roman Elizarov | d82b3a9 | 2017-06-23 21:52:08 +0300 | [diff] [blame] | 72 | abstract fun prepare(op: AtomicOp<*>): Any? // returns `null` if prepared successfully |
| 73 | abstract fun complete(op: AtomicOp<*>, failure: Any?) // decision == null if success |
Roman Elizarov | ee7c0eb | 2017-02-16 15:29:28 +0300 | [diff] [blame] | 74 | } |