kotlinx-coroutines-core/common/src/internal/Atomic.kt

/*
 * Copyright 2016-2020 JetBrains s.r.o. Use of this source code is governed by the Apache 2.0 license.
 */
@file:Suppress("NO_EXPLICIT_VISIBILITY_IN_API_MODE")

package kotlinx.coroutines.internal

import kotlinx.atomicfu.atomic
import kotlinx.coroutines.*
import kotlin.jvm.*
import kotlin.native.concurrent.*

/**
 * The most abstract operation that can be in process. Other threads observing an instance of this
 * class in the fields of their object shall invoke [perform] to help.
 *
 * @suppress **This is unstable API and it is subject to change.**
 */
public abstract class OpDescriptor {
    /**
     * Returns `null` is operation was performed successfully or some other
     * object that indicates the failure reason.
     */
    abstract fun perform(affected: Any?): Any?

    /**
     * Returns reference to atomic operation that this descriptor is a part of or `null`
     * if not a part of any [AtomicOp].
     */
    abstract val atomicOp: AtomicOp<*>?

    override fun toString(): String = "$classSimpleName@$hexAddress" // debug

    fun isEarlierThan(that: OpDescriptor): Boolean {
        val thisOp = atomicOp ?: return false
        val thatOp = that.atomicOp ?: return false
        return thisOp.opSequence < thatOp.opSequence
    }
}

@SharedImmutable
private val NO_DECISION: Any = Symbol("NO_DECISION")

/**
 * Descriptor for multi-word atomic operation.
 * Based on paper
 * ["A Practical Multi-Word Compare-and-Swap Operation"](https://www.cl.cam.ac.uk/research/srg/netos/papers/2002-casn.pdf)
 * by Timothy L. Harris, Keir Fraser and Ian A. Pratt.
 *
 * Note: parts of atomic operation must be globally ordered. Otherwise, this implementation will produce
 * `StackOverflowError`.
 *
 * @suppress **This is unstable API and it is subject to change.**
 */
public abstract class AtomicOp<in T> : OpDescriptor() {
    private val _consensus = atomic<Any?>(NO_DECISION)

    val isDecided: Boolean get() = _consensus.value !== NO_DECISION

    /**
     * Sequence number of this multi-word operation for deadlock resolution.
     * An operation with lower number aborts itself with (using [RETRY_ATOMIC] error symbol) if it encounters
     * the need to help the operation with higher sequence number and then restarts
     * (using higher `opSequence` to ensure progress).
     * Simple operations that cannot get into the deadlock always return zero here.
     *
     * See https://github.com/Kotlin/kotlinx.coroutines/issues/504
     */
    open val opSequence: Long get() = 0L

    override val atomicOp: AtomicOp<*> get() = this

    fun decide(decision: Any?): Any? {
        assert { decision !== NO_DECISION }
        val current = _consensus.value
        if (current !== NO_DECISION) return current
        if (_consensus.compareAndSet(NO_DECISION, decision)) return decision
        return _consensus.value
    }

    abstract fun prepare(affected: T): Any? // `null` if Ok, or failure reason

    abstract fun complete(affected: T, failure: Any?) // failure != null if failed to prepare op

    // returns `null` on success
    @Suppress("UNCHECKED_CAST")
    final override fun perform(affected: Any?): Any? {
        // make decision on status
        var decision = this._consensus.value
        if (decision === NO_DECISION) {
            decision = decide(prepare(affected as T))
        }
        // complete operation
        complete(affected as T, decision)
        return decision
    }
}

/**
 * A part of multi-step atomic operation [AtomicOp].
 *
 * @suppress **This is unstable API and it is subject to change.**
 */
public abstract class AtomicDesc {
    lateinit var atomicOp: AtomicOp<*> // the reference to parent atomicOp, init when AtomicOp is created
    abstract fun prepare(op: AtomicOp<*>): Any? // returns `null` if prepared successfully
    abstract fun complete(op: AtomicOp<*>, failure: Any?) // decision == null if success
}

/**
 * It is returned as an error by [AtomicOp] implementations when they detect potential deadlock
 * using [AtomicOp.opSequence] numbers.
 */
@JvmField
@SharedImmutable
internal val RETRY_ATOMIC: Any = Symbol("RETRY_ATOMIC")