Roman Elizarov | 8bd5254 | 2017-02-14 15:51:58 +0300 | [diff] [blame] | 1 | /* |
| 2 | * Copyright 2016-2017 JetBrains s.r.o. |
| 3 | * |
| 4 | * Licensed under the Apache License, Version 2.0 (the "License"); |
| 5 | * you may not use this file except in compliance with the License. |
| 6 | * You may obtain a copy of the License at |
| 7 | * |
| 8 | * http://www.apache.org/licenses/LICENSE-2.0 |
| 9 | * |
| 10 | * Unless required by applicable law or agreed to in writing, software |
| 11 | * distributed under the License is distributed on an "AS IS" BASIS, |
| 12 | * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. |
| 13 | * See the License for the specific language governing permissions and |
| 14 | * limitations under the License. |
| 15 | */ |
| 16 | |
Roman Elizarov | f8fc478 | 2017-02-22 10:35:08 +0300 | [diff] [blame] | 17 | package kotlinx.coroutines.experimental.sync |
Roman Elizarov | 8bd5254 | 2017-02-14 15:51:58 +0300 | [diff] [blame] | 18 | |
Roman Elizarov | aa461cf | 2018-04-11 13:20:29 +0300 | [diff] [blame] | 19 | import kotlinx.atomicfu.* |
Roman Elizarov | f8fc478 | 2017-02-22 10:35:08 +0300 | [diff] [blame] | 20 | import kotlinx.coroutines.experimental.* |
Roman Elizarov | 174c696 | 2017-02-28 17:36:51 +0300 | [diff] [blame] | 21 | import kotlinx.coroutines.experimental.internal.* |
Roman Elizarov | aa461cf | 2018-04-11 13:20:29 +0300 | [diff] [blame] | 22 | import kotlinx.coroutines.experimental.intrinsics.* |
| 23 | import kotlinx.coroutines.experimental.selects.* |
| 24 | import kotlin.coroutines.experimental.* |
| 25 | import kotlinx.coroutines.experimental.internalAnnotations.* |
Roman Elizarov | 8bd5254 | 2017-02-14 15:51:58 +0300 | [diff] [blame] | 26 | |
| 27 | /** |
| 28 | * Mutual exclusion for coroutines. |
| 29 | * |
| 30 | * Mutex has two states: _locked_ and _unlocked_. |
| 31 | * It is **non-reentrant**, that is invoking [lock] even from the same thread/coroutine that currently holds |
| 32 | * the lock still suspends the invoker. |
Vsevolod Tolstopyatov | a518edc | 2018-05-11 13:54:48 +0300 | [diff] [blame] | 33 | * |
| 34 | * JVM API note: |
| 35 | * Memory semantic of the [Mutex] is similar to `synchronized` block on JVM: |
| 36 | * An unlock on a [Mutex] happens-before every subsequent successful lock on that [Mutex]. |
| 37 | * Unsuccessful call to [tryLock] do not have any memory effects. |
Roman Elizarov | 8bd5254 | 2017-02-14 15:51:58 +0300 | [diff] [blame] | 38 | */ |
Roman Elizarov | f8fc478 | 2017-02-22 10:35:08 +0300 | [diff] [blame] | 39 | public interface Mutex { |
| 40 | /** |
Roman Elizarov | f8fc478 | 2017-02-22 10:35:08 +0300 | [diff] [blame] | 41 | * Returns `true` when this mutex is locked. |
| 42 | */ |
| 43 | public val isLocked: Boolean |
| 44 | |
| 45 | /** |
| 46 | * Tries to lock this mutex, returning `false` if this mutex is already locked. |
Roman Elizarov | 174c696 | 2017-02-28 17:36:51 +0300 | [diff] [blame] | 47 | * |
| 48 | * @param owner Optional owner token for debugging. When `owner` is specified (non-null value) and this mutex |
| 49 | * is already locked with the same token (same identity), this function throws [IllegalStateException]. |
Roman Elizarov | f8fc478 | 2017-02-22 10:35:08 +0300 | [diff] [blame] | 50 | */ |
Roman Elizarov | 174c696 | 2017-02-28 17:36:51 +0300 | [diff] [blame] | 51 | public fun tryLock(owner: Any? = null): Boolean |
Roman Elizarov | f8fc478 | 2017-02-22 10:35:08 +0300 | [diff] [blame] | 52 | |
| 53 | /** |
| 54 | * Locks this mutex, suspending caller while the mutex is locked. |
| 55 | * |
Roman Elizarov | d82b3a9 | 2017-06-23 21:52:08 +0300 | [diff] [blame] | 56 | * This suspending function is cancellable. If the [Job] of the current coroutine is cancelled or completed while this |
Roman Elizarov | f8fc478 | 2017-02-22 10:35:08 +0300 | [diff] [blame] | 57 | * function is suspended, this function immediately resumes with [CancellationException]. |
Roman Elizarov | a74eb5f | 2017-05-11 20:15:18 +0300 | [diff] [blame] | 58 | * |
| 59 | * *Cancellation of suspended lock invocation is atomic* -- when this function |
Roman Elizarov | f8fc478 | 2017-02-22 10:35:08 +0300 | [diff] [blame] | 60 | * throws [CancellationException] it means that the mutex was not locked. |
Roman Elizarov | a74eb5f | 2017-05-11 20:15:18 +0300 | [diff] [blame] | 61 | * As a side-effect of atomic cancellation, a thread-bound coroutine (to some UI thread, for example) may |
| 62 | * continue to execute even after it was cancelled from the same thread in the case when this lock operation |
| 63 | * was already resumed and the continuation was posted for execution to the thread's queue. |
Roman Elizarov | f8fc478 | 2017-02-22 10:35:08 +0300 | [diff] [blame] | 64 | * |
| 65 | * Note, that this function does not check for cancellation when it is not suspended. |
| 66 | * Use [yield] or [CoroutineScope.isActive] to periodically check for cancellation in tight loops if needed. |
Roman Elizarov | 174c696 | 2017-02-28 17:36:51 +0300 | [diff] [blame] | 67 | * |
Roman Elizarov | db0e22d | 2017-08-29 18:15:57 +0300 | [diff] [blame] | 68 | * This function can be used in [select] invocation with [onLock] clause. |
Roman Elizarov | 174c696 | 2017-02-28 17:36:51 +0300 | [diff] [blame] | 69 | * Use [tryLock] to try acquire lock without waiting. |
| 70 | * |
| 71 | * @param owner Optional owner token for debugging. When `owner` is specified (non-null value) and this mutex |
| 72 | * is already locked with the same token (same identity), this function throws [IllegalStateException]. |
Roman Elizarov | f8fc478 | 2017-02-22 10:35:08 +0300 | [diff] [blame] | 73 | */ |
Roman Elizarov | 174c696 | 2017-02-28 17:36:51 +0300 | [diff] [blame] | 74 | public suspend fun lock(owner: Any? = null) |
| 75 | |
| 76 | /** |
Roman Elizarov | db0e22d | 2017-08-29 18:15:57 +0300 | [diff] [blame] | 77 | * Clause for [select] expression of [lock] suspending function that selects when the mutex is locked. |
| 78 | * Additional parameter for the clause in the `owner` (see [lock]) and when the clause is selected |
| 79 | * the reference to this mutex is passed into the corresponding block. |
Roman Elizarov | 174c696 | 2017-02-28 17:36:51 +0300 | [diff] [blame] | 80 | */ |
Roman Elizarov | db0e22d | 2017-08-29 18:15:57 +0300 | [diff] [blame] | 81 | public val onLock: SelectClause2<Any?, Mutex> |
Roman Elizarov | f8fc478 | 2017-02-22 10:35:08 +0300 | [diff] [blame] | 82 | |
| 83 | /** |
Francesco Vasco | 14328d1 | 2017-07-26 15:31:15 +0200 | [diff] [blame] | 84 | * Checks mutex locked by owner |
| 85 | * |
| 86 | * @return `true` on mutex lock by owner, `false` if not locker or it is locked by different owner |
| 87 | */ |
| 88 | public fun holdsLock(owner: Any): Boolean |
| 89 | |
| 90 | /** |
Roman Elizarov | f8fc478 | 2017-02-22 10:35:08 +0300 | [diff] [blame] | 91 | * Unlocks this mutex. Throws [IllegalStateException] if invoked on a mutex that is not locked. |
Roman Elizarov | 174c696 | 2017-02-28 17:36:51 +0300 | [diff] [blame] | 92 | * |
| 93 | * @param owner Optional owner token for debugging. When `owner` is specified (non-null value) and this mutex |
| 94 | * was locked with the different token (by identity), this function throws [IllegalStateException]. |
Roman Elizarov | f8fc478 | 2017-02-22 10:35:08 +0300 | [diff] [blame] | 95 | */ |
Roman Elizarov | 174c696 | 2017-02-28 17:36:51 +0300 | [diff] [blame] | 96 | public fun unlock(owner: Any? = null) |
Roman Elizarov | f8fc478 | 2017-02-22 10:35:08 +0300 | [diff] [blame] | 97 | } |
| 98 | |
Francesco Vasco | e73899d | 2017-03-14 22:30:13 +0100 | [diff] [blame] | 99 | /** |
Roman Elizarov | fe64d7b | 2017-07-21 18:42:33 +0300 | [diff] [blame] | 100 | * Creates new [Mutex] instance. |
Francesco Vasco | f1a24b1 | 2017-07-31 09:13:30 +0200 | [diff] [blame] | 101 | * The mutex created is fair: lock is granted in first come, first served order. |
| 102 | * |
Roman Elizarov | fe64d7b | 2017-07-21 18:42:33 +0300 | [diff] [blame] | 103 | * @param locked initial state of the mutex. |
| 104 | */ |
Roman Elizarov | aa461cf | 2018-04-11 13:20:29 +0300 | [diff] [blame] | 105 | @Suppress("FunctionName") |
| 106 | public fun Mutex(locked: Boolean = false): Mutex = |
| 107 | MutexImpl(locked) |
Roman Elizarov | fe64d7b | 2017-07-21 18:42:33 +0300 | [diff] [blame] | 108 | |
| 109 | /** |
Roman Elizarov | c02ee11 | 2017-04-19 12:57:38 +0300 | [diff] [blame] | 110 | * Executes the given [action] under this mutex's lock. |
Francesco Vasco | 3a78aa2 | 2017-07-26 15:06:18 +0200 | [diff] [blame] | 111 | * |
| 112 | * @param owner Optional owner token for debugging. |
| 113 | * |
Francesco Vasco | e73899d | 2017-03-14 22:30:13 +0100 | [diff] [blame] | 114 | * @return the return value of the action. |
| 115 | */ |
Roman Elizarov | aa461cf | 2018-04-11 13:20:29 +0300 | [diff] [blame] | 116 | public suspend inline fun <T> Mutex.withLock(owner: Any? = null, action: () -> T): T { |
Francesco Vasco | 3a78aa2 | 2017-07-26 15:06:18 +0200 | [diff] [blame] | 117 | lock(owner) |
Roman Elizarov | c02ee11 | 2017-04-19 12:57:38 +0300 | [diff] [blame] | 118 | try { |
| 119 | return action() |
| 120 | } finally { |
Francesco Vasco | 3a78aa2 | 2017-07-26 15:06:18 +0200 | [diff] [blame] | 121 | unlock(owner) |
Roman Elizarov | c02ee11 | 2017-04-19 12:57:38 +0300 | [diff] [blame] | 122 | } |
| 123 | } |
| 124 | |
| 125 | /** |
Roman Elizarov | 537c359 | 2017-08-16 19:04:31 +0300 | [diff] [blame] | 126 | * @suppress: **Deprecated**: binary compatibility with old code |
| 127 | */ |
| 128 | @Deprecated("binary compatibility with old code", level = DeprecationLevel.HIDDEN) |
| 129 | public suspend fun <T> Mutex.withLock(owner: Any? = null, action: suspend () -> T): T = |
| 130 | withLock(owner) { action() } |
| 131 | |
| 132 | /** |
Roman Elizarov | c02ee11 | 2017-04-19 12:57:38 +0300 | [diff] [blame] | 133 | * @suppress: **Deprecated**: Use [withLock] |
| 134 | */ |
Francesco Vasco | 3a78aa2 | 2017-07-26 15:06:18 +0200 | [diff] [blame] | 135 | @Deprecated("Use `withLock(owner, action)", level = DeprecationLevel.HIDDEN) |
Roman Elizarov | 537c359 | 2017-08-16 19:04:31 +0300 | [diff] [blame] | 136 | public suspend fun <T> Mutex.withLock(action: suspend () -> T): T = |
| 137 | withLock { action() } |
Francesco Vasco | 3a78aa2 | 2017-07-26 15:06:18 +0200 | [diff] [blame] | 138 | |
| 139 | /** |
| 140 | * @suppress: **Deprecated**: Use [withLock] |
| 141 | */ |
Roman Elizarov | c02ee11 | 2017-04-19 12:57:38 +0300 | [diff] [blame] | 142 | @Deprecated("Use `withLock`", replaceWith = ReplaceWith("withLock(action)")) |
Roman Elizarov | 537c359 | 2017-08-16 19:04:31 +0300 | [diff] [blame] | 143 | public suspend fun <T> Mutex.withMutex(action: suspend () -> T): T = |
| 144 | withLock { action() } |
Francesco Vasco | e73899d | 2017-03-14 22:30:13 +0100 | [diff] [blame] | 145 | |
Roman Elizarov | 7753f8e | 2017-08-15 11:16:33 +0300 | [diff] [blame] | 146 | private val LOCK_FAIL = Symbol("LOCK_FAIL") |
| 147 | private val ENQUEUE_FAIL = Symbol("ENQUEUE_FAIL") |
| 148 | private val UNLOCK_FAIL = Symbol("UNLOCK_FAIL") |
| 149 | private val SELECT_SUCCESS = Symbol("SELECT_SUCCESS") |
| 150 | private val LOCKED = Symbol("LOCKED") |
| 151 | private val UNLOCKED = Symbol("UNLOCKED") |
| 152 | private val RESUME_QUIESCENT = Symbol("RESUME_QUIESCENT") |
| 153 | private val RESUME_ACTIVE = Symbol("RESUME_ACTIVE") |
| 154 | |
| 155 | private val EmptyLocked = Empty(LOCKED) |
| 156 | private val EmptyUnlocked = Empty(UNLOCKED) |
| 157 | |
| 158 | private class Empty( |
| 159 | @JvmField val locked: Any |
| 160 | ) { |
| 161 | override fun toString(): String = "Empty[$locked]" |
| 162 | } |
| 163 | |
Roman Elizarov | db0e22d | 2017-08-29 18:15:57 +0300 | [diff] [blame] | 164 | internal class MutexImpl(locked: Boolean) : Mutex, SelectClause2<Any?, Mutex> { |
Roman Elizarov | 174c696 | 2017-02-28 17:36:51 +0300 | [diff] [blame] | 165 | // State is: Empty | LockedQueue | OpDescriptor |
Roman Elizarov | 7753f8e | 2017-08-15 11:16:33 +0300 | [diff] [blame] | 166 | // shared objects while we have no waiters |
| 167 | private val _state = atomic<Any?>(if (locked) EmptyLocked else EmptyUnlocked) |
Roman Elizarov | 8bd5254 | 2017-02-14 15:51:58 +0300 | [diff] [blame] | 168 | |
Roman Elizarov | 11c140a | 2017-07-21 21:12:55 +0300 | [diff] [blame] | 169 | // resumeNext is: RESUME_QUIESCENT | RESUME_ACTIVE | ResumeReq |
Roman Elizarov | 7753f8e | 2017-08-15 11:16:33 +0300 | [diff] [blame] | 170 | private val _resumeNext = atomic<Any>(RESUME_QUIESCENT) |
Roman Elizarov | 8bd5254 | 2017-02-14 15:51:58 +0300 | [diff] [blame] | 171 | |
Roman Elizarov | 174c696 | 2017-02-28 17:36:51 +0300 | [diff] [blame] | 172 | public override val isLocked: Boolean get() { |
Roman Elizarov | 7753f8e | 2017-08-15 11:16:33 +0300 | [diff] [blame] | 173 | _state.loop { state -> |
Roman Elizarov | 8bd5254 | 2017-02-14 15:51:58 +0300 | [diff] [blame] | 174 | when (state) { |
Roman Elizarov | 174c696 | 2017-02-28 17:36:51 +0300 | [diff] [blame] | 175 | is Empty -> return state.locked !== UNLOCKED |
| 176 | is LockedQueue -> return true |
| 177 | is OpDescriptor -> state.perform(this) // help |
| 178 | else -> error("Illegal state $state") |
Roman Elizarov | 8bd5254 | 2017-02-14 15:51:58 +0300 | [diff] [blame] | 179 | } |
| 180 | } |
| 181 | } |
| 182 | |
Roman Elizarov | 7753f8e | 2017-08-15 11:16:33 +0300 | [diff] [blame] | 183 | // for tests ONLY |
Roman Elizarov | 174c696 | 2017-02-28 17:36:51 +0300 | [diff] [blame] | 184 | internal val isLockedEmptyQueueState: Boolean get() { |
Roman Elizarov | 7753f8e | 2017-08-15 11:16:33 +0300 | [diff] [blame] | 185 | val state = _state.value |
Roman Elizarov | 174c696 | 2017-02-28 17:36:51 +0300 | [diff] [blame] | 186 | return state is LockedQueue && state.isEmpty |
Roman Elizarov | 8bd5254 | 2017-02-14 15:51:58 +0300 | [diff] [blame] | 187 | } |
| 188 | |
Roman Elizarov | 174c696 | 2017-02-28 17:36:51 +0300 | [diff] [blame] | 189 | public override fun tryLock(owner: Any?): Boolean { |
Roman Elizarov | 7753f8e | 2017-08-15 11:16:33 +0300 | [diff] [blame] | 190 | _state.loop { state -> |
Roman Elizarov | 8bd5254 | 2017-02-14 15:51:58 +0300 | [diff] [blame] | 191 | when (state) { |
| 192 | is Empty -> { |
Roman Elizarov | 174c696 | 2017-02-28 17:36:51 +0300 | [diff] [blame] | 193 | if (state.locked !== UNLOCKED) return false |
Roman Elizarov | aa461cf | 2018-04-11 13:20:29 +0300 | [diff] [blame] | 194 | val update = if (owner == null) EmptyLocked else Empty( |
| 195 | owner |
| 196 | ) |
Roman Elizarov | 7753f8e | 2017-08-15 11:16:33 +0300 | [diff] [blame] | 197 | if (_state.compareAndSet(state, update)) return true |
Roman Elizarov | 174c696 | 2017-02-28 17:36:51 +0300 | [diff] [blame] | 198 | } |
| 199 | is LockedQueue -> { |
| 200 | check(state.owner !== owner) { "Already locked by $owner" } |
| 201 | return false |
| 202 | } |
| 203 | is OpDescriptor -> state.perform(this) // help |
| 204 | else -> error("Illegal state $state") |
| 205 | } |
| 206 | } |
| 207 | } |
| 208 | |
| 209 | public override suspend fun lock(owner: Any?) { |
| 210 | // fast-path -- try lock |
| 211 | if (tryLock(owner)) return |
| 212 | // slow-path -- suspend |
| 213 | return lockSuspend(owner) |
| 214 | } |
| 215 | |
Roman Elizarov | a74eb5f | 2017-05-11 20:15:18 +0300 | [diff] [blame] | 216 | private suspend fun lockSuspend(owner: Any?) = suspendAtomicCancellableCoroutine<Unit>(holdCancellability = true) sc@ { cont -> |
Roman Elizarov | 174c696 | 2017-02-28 17:36:51 +0300 | [diff] [blame] | 217 | val waiter = LockCont(owner, cont) |
Roman Elizarov | 7753f8e | 2017-08-15 11:16:33 +0300 | [diff] [blame] | 218 | _state.loop { state -> |
Roman Elizarov | 174c696 | 2017-02-28 17:36:51 +0300 | [diff] [blame] | 219 | when (state) { |
| 220 | is Empty -> { |
| 221 | if (state.locked !== UNLOCKED) { // try upgrade to queue & retry |
Roman Elizarov | 7753f8e | 2017-08-15 11:16:33 +0300 | [diff] [blame] | 222 | _state.compareAndSet(state, LockedQueue(state.locked)) |
Roman Elizarov | 8bd5254 | 2017-02-14 15:51:58 +0300 | [diff] [blame] | 223 | } else { |
| 224 | // try lock |
Roman Elizarov | 174c696 | 2017-02-28 17:36:51 +0300 | [diff] [blame] | 225 | val update = if (owner == null) EmptyLocked else Empty(owner) |
Roman Elizarov | 7753f8e | 2017-08-15 11:16:33 +0300 | [diff] [blame] | 226 | if (_state.compareAndSet(state, update)) { // locked |
Roman Elizarov | 8bd5254 | 2017-02-14 15:51:58 +0300 | [diff] [blame] | 227 | cont.resume(Unit) |
| 228 | return@sc |
| 229 | } |
| 230 | } |
| 231 | } |
Roman Elizarov | 174c696 | 2017-02-28 17:36:51 +0300 | [diff] [blame] | 232 | is LockedQueue -> { |
| 233 | val curOwner = state.owner |
| 234 | check(curOwner !== owner) { "Already locked by $owner" } |
Roman Elizarov | 7753f8e | 2017-08-15 11:16:33 +0300 | [diff] [blame] | 235 | if (state.addLastIf(waiter, { _state.value === state })) { |
Roman Elizarov | 8bd5254 | 2017-02-14 15:51:58 +0300 | [diff] [blame] | 236 | // added to waiter list! |
Roman Elizarov | a74eb5f | 2017-05-11 20:15:18 +0300 | [diff] [blame] | 237 | cont.initCancellability() // make it properly cancellable |
Vsevolod Tolstopyatov | 80a2947 | 2018-04-17 16:02:02 +0300 | [diff] [blame] | 238 | cont.removeOnCancellation(waiter) |
Roman Elizarov | 8bd5254 | 2017-02-14 15:51:58 +0300 | [diff] [blame] | 239 | return@sc |
| 240 | } |
| 241 | } |
Roman Elizarov | 174c696 | 2017-02-28 17:36:51 +0300 | [diff] [blame] | 242 | is OpDescriptor -> state.perform(this) // help |
| 243 | else -> error("Illegal state $state") |
Roman Elizarov | 8bd5254 | 2017-02-14 15:51:58 +0300 | [diff] [blame] | 244 | } |
| 245 | } |
| 246 | } |
| 247 | |
Roman Elizarov | db0e22d | 2017-08-29 18:15:57 +0300 | [diff] [blame] | 248 | override val onLock: SelectClause2<Any?, Mutex> |
| 249 | get() = this |
| 250 | |
| 251 | // registerSelectLock |
| 252 | @Suppress("PARAMETER_NAME_CHANGED_ON_OVERRIDE") |
| 253 | override fun <R> registerSelectClause2(select: SelectInstance<R>, owner: Any?, block: suspend (Mutex) -> R) { |
Roman Elizarov | 8bd5254 | 2017-02-14 15:51:58 +0300 | [diff] [blame] | 254 | while (true) { // lock-free loop on state |
Roman Elizarov | 174c696 | 2017-02-28 17:36:51 +0300 | [diff] [blame] | 255 | if (select.isSelected) return |
Roman Elizarov | 7753f8e | 2017-08-15 11:16:33 +0300 | [diff] [blame] | 256 | val state = _state.value |
Roman Elizarov | 8bd5254 | 2017-02-14 15:51:58 +0300 | [diff] [blame] | 257 | when (state) { |
| 258 | is Empty -> { |
Roman Elizarov | 174c696 | 2017-02-28 17:36:51 +0300 | [diff] [blame] | 259 | if (state.locked !== UNLOCKED) { // try upgrade to queue & retry |
Roman Elizarov | 7753f8e | 2017-08-15 11:16:33 +0300 | [diff] [blame] | 260 | _state.compareAndSet(state, LockedQueue(state.locked)) |
Roman Elizarov | 174c696 | 2017-02-28 17:36:51 +0300 | [diff] [blame] | 261 | } else { |
| 262 | // try lock |
| 263 | val failure = select.performAtomicTrySelect(TryLockDesc(this, owner)) |
| 264 | when { |
| 265 | failure == null -> { // success |
Roman Elizarov | db0e22d | 2017-08-29 18:15:57 +0300 | [diff] [blame] | 266 | block.startCoroutineUndispatched(receiver = this, completion = select.completion) |
Roman Elizarov | 174c696 | 2017-02-28 17:36:51 +0300 | [diff] [blame] | 267 | return |
| 268 | } |
| 269 | failure === ALREADY_SELECTED -> return // already selected -- bail out |
| 270 | failure === LOCK_FAIL -> {} // retry |
| 271 | else -> error("performAtomicTrySelect(TryLockDesc) returned $failure") |
| 272 | } |
| 273 | } |
| 274 | } |
| 275 | is LockedQueue -> { |
| 276 | check(state.owner !== owner) { "Already locked by $owner" } |
| 277 | val enqueueOp = TryEnqueueLockDesc(this, owner, state, select, block) |
| 278 | val failure = select.performAtomicIfNotSelected(enqueueOp) |
| 279 | when { |
| 280 | failure == null -> { // successfully enqueued |
Roman Elizarov | daa1d9d | 2017-03-02 19:00:50 +0300 | [diff] [blame] | 281 | select.disposeOnSelect(enqueueOp.node) |
Roman Elizarov | 174c696 | 2017-02-28 17:36:51 +0300 | [diff] [blame] | 282 | return |
| 283 | } |
| 284 | failure === ALREADY_SELECTED -> return // already selected -- bail out |
| 285 | failure === ENQUEUE_FAIL -> {} // retry |
| 286 | else -> error("performAtomicIfNotSelected(TryEnqueueLockDesc) returned $failure") |
| 287 | } |
| 288 | } |
| 289 | is OpDescriptor -> state.perform(this) // help |
| 290 | else -> error("Illegal state $state") |
| 291 | } |
| 292 | } |
| 293 | } |
| 294 | |
| 295 | private class TryLockDesc( |
| 296 | @JvmField val mutex: MutexImpl, |
| 297 | @JvmField val owner: Any? |
| 298 | ) : AtomicDesc() { |
| 299 | // This is Harris's RDCSS (Restricted Double-Compare Single Swap) operation |
Roman Elizarov | d82b3a9 | 2017-06-23 21:52:08 +0300 | [diff] [blame] | 300 | private inner class PrepareOp(private val op: AtomicOp<*>) : OpDescriptor() { |
Roman Elizarov | 174c696 | 2017-02-28 17:36:51 +0300 | [diff] [blame] | 301 | override fun perform(affected: Any?): Any? { |
| 302 | val update: Any = if (op.isDecided) EmptyUnlocked else op // restore if was already decided |
Roman Elizarov | 7753f8e | 2017-08-15 11:16:33 +0300 | [diff] [blame] | 303 | (affected as MutexImpl)._state.compareAndSet(this, update) |
Roman Elizarov | 174c696 | 2017-02-28 17:36:51 +0300 | [diff] [blame] | 304 | return null // ok |
| 305 | } |
| 306 | } |
| 307 | |
Roman Elizarov | d82b3a9 | 2017-06-23 21:52:08 +0300 | [diff] [blame] | 308 | override fun prepare(op: AtomicOp<*>): Any? { |
Roman Elizarov | 174c696 | 2017-02-28 17:36:51 +0300 | [diff] [blame] | 309 | val prepare = PrepareOp(op) |
Roman Elizarov | 7753f8e | 2017-08-15 11:16:33 +0300 | [diff] [blame] | 310 | if (!mutex._state.compareAndSet(EmptyUnlocked, prepare)) return LOCK_FAIL |
Roman Elizarov | 174c696 | 2017-02-28 17:36:51 +0300 | [diff] [blame] | 311 | return prepare.perform(mutex) |
| 312 | } |
| 313 | |
Roman Elizarov | d82b3a9 | 2017-06-23 21:52:08 +0300 | [diff] [blame] | 314 | override fun complete(op: AtomicOp<*>, failure: Any?) { |
Roman Elizarov | 174c696 | 2017-02-28 17:36:51 +0300 | [diff] [blame] | 315 | val update = if (failure != null) EmptyUnlocked else { |
| 316 | if (owner == null) EmptyLocked else Empty(owner) |
| 317 | } |
Roman Elizarov | 7753f8e | 2017-08-15 11:16:33 +0300 | [diff] [blame] | 318 | mutex._state.compareAndSet(op, update) |
Roman Elizarov | 174c696 | 2017-02-28 17:36:51 +0300 | [diff] [blame] | 319 | } |
| 320 | } |
| 321 | |
| 322 | private class TryEnqueueLockDesc<R>( |
| 323 | @JvmField val mutex: MutexImpl, |
| 324 | owner: Any?, |
| 325 | queue: LockedQueue, |
| 326 | select: SelectInstance<R>, |
Roman Elizarov | db0e22d | 2017-08-29 18:15:57 +0300 | [diff] [blame] | 327 | block: suspend (Mutex) -> R |
| 328 | ) : AddLastDesc<LockSelect<R>>(queue, LockSelect(owner, mutex, select, block)) { |
Roman Elizarov | 174c696 | 2017-02-28 17:36:51 +0300 | [diff] [blame] | 329 | override fun onPrepare(affected: LockFreeLinkedListNode, next: LockFreeLinkedListNode): Any? { |
Roman Elizarov | 7753f8e | 2017-08-15 11:16:33 +0300 | [diff] [blame] | 330 | if (mutex._state.value !== queue) return ENQUEUE_FAIL |
Roman Elizarov | 174c696 | 2017-02-28 17:36:51 +0300 | [diff] [blame] | 331 | return super.onPrepare(affected, next) |
| 332 | } |
| 333 | } |
| 334 | |
Francesco Vasco | 14328d1 | 2017-07-26 15:31:15 +0200 | [diff] [blame] | 335 | public override fun holdsLock(owner: Any) = |
| 336 | _state.value.let { state -> |
| 337 | when (state) { |
| 338 | is Empty -> state.locked === owner |
| 339 | is LockedQueue -> state.owner === owner |
| 340 | else -> false |
| 341 | } |
| 342 | } |
| 343 | |
Roman Elizarov | 174c696 | 2017-02-28 17:36:51 +0300 | [diff] [blame] | 344 | public override fun unlock(owner: Any?) { |
Roman Elizarov | 7753f8e | 2017-08-15 11:16:33 +0300 | [diff] [blame] | 345 | _state.loop { state -> |
Roman Elizarov | 174c696 | 2017-02-28 17:36:51 +0300 | [diff] [blame] | 346 | when (state) { |
| 347 | is Empty -> { |
| 348 | if (owner == null) |
| 349 | check(state.locked !== UNLOCKED) { "Mutex is not locked" } |
| 350 | else |
| 351 | check(state.locked === owner) { "Mutex is locked by ${state.locked} but expected $owner" } |
Roman Elizarov | 7753f8e | 2017-08-15 11:16:33 +0300 | [diff] [blame] | 352 | if (_state.compareAndSet(state, EmptyUnlocked)) return |
Roman Elizarov | 8bd5254 | 2017-02-14 15:51:58 +0300 | [diff] [blame] | 353 | } |
Roman Elizarov | 174c696 | 2017-02-28 17:36:51 +0300 | [diff] [blame] | 354 | is OpDescriptor -> state.perform(this) |
| 355 | is LockedQueue -> { |
| 356 | if (owner != null) |
| 357 | check(state.owner === owner) { "Mutex is locked by ${state.owner} but expected $owner" } |
Roman Elizarov | 8bd5254 | 2017-02-14 15:51:58 +0300 | [diff] [blame] | 358 | val waiter = state.removeFirstOrNull() |
| 359 | if (waiter == null) { |
| 360 | val op = UnlockOp(state) |
Roman Elizarov | 7753f8e | 2017-08-15 11:16:33 +0300 | [diff] [blame] | 361 | if (_state.compareAndSet(state, op) && op.perform(this) == null) return |
Roman Elizarov | 8bd5254 | 2017-02-14 15:51:58 +0300 | [diff] [blame] | 362 | } else { |
Roman Elizarov | 174c696 | 2017-02-28 17:36:51 +0300 | [diff] [blame] | 363 | val token = (waiter as LockWaiter).tryResumeLockWaiter() |
Roman Elizarov | 11c140a | 2017-07-21 21:12:55 +0300 | [diff] [blame] | 364 | if (token != null) { |
| 365 | // successfully resumed waiter that now is holding the lock |
| 366 | // we must immediately transfer ownership to the next waiter, because this coroutine |
| 367 | // might try to lock it again after unlock returns do to StackOverflow avoidance code |
| 368 | // and its attempts to take a lock must be queued. |
Roman Elizarov | 174c696 | 2017-02-28 17:36:51 +0300 | [diff] [blame] | 369 | state.owner = waiter.owner ?: LOCKED |
Roman Elizarov | 11c140a | 2017-07-21 21:12:55 +0300 | [diff] [blame] | 370 | // StackOverflow avoidance code |
| 371 | if (startResumeNext(waiter, token)) { |
| 372 | waiter.completeResumeLockWaiter(token) |
| 373 | finishResumeNext() |
| 374 | } |
Roman Elizarov | 8bd5254 | 2017-02-14 15:51:58 +0300 | [diff] [blame] | 375 | return |
| 376 | } |
| 377 | } |
| 378 | } |
Roman Elizarov | 174c696 | 2017-02-28 17:36:51 +0300 | [diff] [blame] | 379 | else -> error("Illegal state $state") |
Roman Elizarov | 8bd5254 | 2017-02-14 15:51:58 +0300 | [diff] [blame] | 380 | } |
| 381 | } |
| 382 | } |
| 383 | |
Roman Elizarov | 11c140a | 2017-07-21 21:12:55 +0300 | [diff] [blame] | 384 | private class ResumeReq( |
| 385 | @JvmField val waiter: LockWaiter, |
| 386 | @JvmField val token: Any |
| 387 | ) |
| 388 | |
| 389 | private fun startResumeNext(waiter: LockWaiter, token: Any): Boolean { |
Roman Elizarov | 7753f8e | 2017-08-15 11:16:33 +0300 | [diff] [blame] | 390 | _resumeNext.loop { resumeNext -> |
Roman Elizarov | 11c140a | 2017-07-21 21:12:55 +0300 | [diff] [blame] | 391 | when { |
| 392 | resumeNext === RESUME_QUIESCENT -> { |
| 393 | // this is never concurrent, because only one thread is holding mutex and trying to resume |
| 394 | // next waiter, so no need to CAS here |
Roman Elizarov | 7753f8e | 2017-08-15 11:16:33 +0300 | [diff] [blame] | 395 | _resumeNext.value = RESUME_ACTIVE |
Roman Elizarov | 11c140a | 2017-07-21 21:12:55 +0300 | [diff] [blame] | 396 | return true |
| 397 | } |
| 398 | resumeNext === RESUME_ACTIVE -> |
Roman Elizarov | 7753f8e | 2017-08-15 11:16:33 +0300 | [diff] [blame] | 399 | if (_resumeNext.compareAndSet(resumeNext, ResumeReq(waiter, token))) return false |
Roman Elizarov | 11c140a | 2017-07-21 21:12:55 +0300 | [diff] [blame] | 400 | else -> error("Cannot happen") |
| 401 | } |
| 402 | } |
| 403 | } |
| 404 | |
| 405 | private fun finishResumeNext() { |
Roman Elizarov | 7753f8e | 2017-08-15 11:16:33 +0300 | [diff] [blame] | 406 | // also a resumption loop to fulfill requests of inner resume invokes |
| 407 | _resumeNext.loop { resumeNext -> |
Roman Elizarov | 11c140a | 2017-07-21 21:12:55 +0300 | [diff] [blame] | 408 | when { |
| 409 | resumeNext === RESUME_ACTIVE -> |
Roman Elizarov | 7753f8e | 2017-08-15 11:16:33 +0300 | [diff] [blame] | 410 | if (_resumeNext.compareAndSet(resumeNext, RESUME_QUIESCENT)) return |
Roman Elizarov | 11c140a | 2017-07-21 21:12:55 +0300 | [diff] [blame] | 411 | resumeNext is ResumeReq -> { |
| 412 | // this is never concurrently, only one thread is finishing, so no need to CAS here |
Roman Elizarov | 7753f8e | 2017-08-15 11:16:33 +0300 | [diff] [blame] | 413 | _resumeNext.value = RESUME_ACTIVE |
Roman Elizarov | 11c140a | 2017-07-21 21:12:55 +0300 | [diff] [blame] | 414 | resumeNext.waiter.completeResumeLockWaiter(resumeNext.token) |
| 415 | } |
| 416 | else -> error("Cannot happen") |
| 417 | } |
| 418 | } |
| 419 | } |
| 420 | |
Roman Elizarov | 174c696 | 2017-02-28 17:36:51 +0300 | [diff] [blame] | 421 | override fun toString(): String { |
Roman Elizarov | 7753f8e | 2017-08-15 11:16:33 +0300 | [diff] [blame] | 422 | _state.loop { state -> |
Roman Elizarov | 174c696 | 2017-02-28 17:36:51 +0300 | [diff] [blame] | 423 | when (state) { |
| 424 | is Empty -> return "Mutex[${state.locked}]" |
| 425 | is OpDescriptor -> state.perform(this) |
| 426 | is LockedQueue -> return "Mutex[${state.owner}]" |
| 427 | else -> error("Illegal state $state") |
| 428 | } |
| 429 | } |
Roman Elizarov | 8bd5254 | 2017-02-14 15:51:58 +0300 | [diff] [blame] | 430 | } |
| 431 | |
Roman Elizarov | 174c696 | 2017-02-28 17:36:51 +0300 | [diff] [blame] | 432 | private class LockedQueue( |
| 433 | @JvmField var owner: Any |
| 434 | ) : LockFreeLinkedListHead() { |
| 435 | override fun toString(): String = "LockedQueue[$owner]" |
| 436 | } |
| 437 | |
| 438 | private abstract class LockWaiter( |
| 439 | @JvmField val owner: Any? |
Roman Elizarov | daa1d9d | 2017-03-02 19:00:50 +0300 | [diff] [blame] | 440 | ) : LockFreeLinkedListNode(), DisposableHandle { |
| 441 | final override fun dispose() { remove() } |
Roman Elizarov | 174c696 | 2017-02-28 17:36:51 +0300 | [diff] [blame] | 442 | abstract fun tryResumeLockWaiter(): Any? |
| 443 | abstract fun completeResumeLockWaiter(token: Any) |
| 444 | } |
| 445 | |
| 446 | private class LockCont( |
| 447 | owner: Any?, |
| 448 | @JvmField val cont: CancellableContinuation<Unit> |
| 449 | ) : LockWaiter(owner) { |
| 450 | override fun tryResumeLockWaiter() = cont.tryResume(Unit) |
| 451 | override fun completeResumeLockWaiter(token: Any) = cont.completeResume(token) |
| 452 | override fun toString(): String = "LockCont[$owner, $cont]" |
| 453 | } |
| 454 | |
| 455 | private class LockSelect<R>( |
| 456 | owner: Any?, |
Roman Elizarov | db0e22d | 2017-08-29 18:15:57 +0300 | [diff] [blame] | 457 | @JvmField val mutex: Mutex, |
Roman Elizarov | 174c696 | 2017-02-28 17:36:51 +0300 | [diff] [blame] | 458 | @JvmField val select: SelectInstance<R>, |
Roman Elizarov | db0e22d | 2017-08-29 18:15:57 +0300 | [diff] [blame] | 459 | @JvmField val block: suspend (Mutex) -> R |
Roman Elizarov | 174c696 | 2017-02-28 17:36:51 +0300 | [diff] [blame] | 460 | ) : LockWaiter(owner) { |
| 461 | override fun tryResumeLockWaiter(): Any? = if (select.trySelect(null)) SELECT_SUCCESS else null |
| 462 | override fun completeResumeLockWaiter(token: Any) { |
| 463 | check(token === SELECT_SUCCESS) |
Roman Elizarov | db0e22d | 2017-08-29 18:15:57 +0300 | [diff] [blame] | 464 | block.startCoroutine(receiver = mutex, completion = select.completion) |
Roman Elizarov | 174c696 | 2017-02-28 17:36:51 +0300 | [diff] [blame] | 465 | } |
Roman Elizarov | db0e22d | 2017-08-29 18:15:57 +0300 | [diff] [blame] | 466 | override fun toString(): String = "LockSelect[$owner, $mutex, $select]" |
Roman Elizarov | 174c696 | 2017-02-28 17:36:51 +0300 | [diff] [blame] | 467 | } |
Roman Elizarov | 8bd5254 | 2017-02-14 15:51:58 +0300 | [diff] [blame] | 468 | |
| 469 | // atomic unlock operation that checks that waiters queue is empty |
Roman Elizarov | 174c696 | 2017-02-28 17:36:51 +0300 | [diff] [blame] | 470 | private class UnlockOp( |
| 471 | @JvmField val queue: LockedQueue |
| 472 | ) : OpDescriptor() { |
| 473 | override fun perform(affected: Any?): Any? { |
Roman Elizarov | 3b558d4 | 2017-02-15 10:48:43 +0300 | [diff] [blame] | 474 | /* |
| 475 | Note: queue cannot change while this UnlockOp is in progress, so all concurrent attempts to |
| 476 | make a decision will reach it consistently. It does not matter what is a proposed |
Roman Elizarov | 174c696 | 2017-02-28 17:36:51 +0300 | [diff] [blame] | 477 | decision when this UnlockOp is no longer active, because in this case the following CAS |
Roman Elizarov | 3b558d4 | 2017-02-15 10:48:43 +0300 | [diff] [blame] | 478 | will fail anyway. |
| 479 | */ |
| 480 | val success = queue.isEmpty |
Roman Elizarov | 8bd5254 | 2017-02-14 15:51:58 +0300 | [diff] [blame] | 481 | val update: Any = if (success) EmptyUnlocked else queue |
Roman Elizarov | 7753f8e | 2017-08-15 11:16:33 +0300 | [diff] [blame] | 482 | (affected as MutexImpl)._state.compareAndSet(this@UnlockOp, update) |
Roman Elizarov | 3b558d4 | 2017-02-15 10:48:43 +0300 | [diff] [blame] | 483 | /* |
Roman Elizarov | 174c696 | 2017-02-28 17:36:51 +0300 | [diff] [blame] | 484 | `perform` invocation from the original `unlock` invocation may be coming too late, when |
Roman Elizarov | 3b558d4 | 2017-02-15 10:48:43 +0300 | [diff] [blame] | 485 | some other thread had already helped to complete it (either successfully or not). |
| 486 | That operation was unsuccessful if `state` was restored to this `queue` reference and |
| 487 | that is what is being checked below. |
| 488 | */ |
Roman Elizarov | 7753f8e | 2017-08-15 11:16:33 +0300 | [diff] [blame] | 489 | return if (affected._state.value === queue) UNLOCK_FAIL else null |
Roman Elizarov | 8bd5254 | 2017-02-14 15:51:58 +0300 | [diff] [blame] | 490 | } |
| 491 | } |
Francesco Vasco | e73899d | 2017-03-14 22:30:13 +0100 | [diff] [blame] | 492 | } |