Read-write Mutex

[fvasco]

Is it in the roadmap?

[elizarov]

It is on my to-do list, but not for the short-term. It is really up for grabs. This is a great feature for someone, who wants to figure how to write low-level lock-free implementations for kotlinx.coroutines primitives, to go ahead, study Mutex implementation, and figure out how to abstract (reuse) parts of that to implement ReadWriteMutex. It would be a pity if I write it myself and deprive someone else from this great learning opportunity.

[bobvawter]

Here's a basic implementation of the 80% case for ReadWriteMutex built on top of Mutex where you just want to execute coroutines as readers or writers.

https://gist.github.com/bobvawter/4ff642d5996dfccb228425909f303306

[fvasco]

The proposed implementation misses of support for "select" clause.

[elizarov]

Adding "select" in not a critical problem. I have a different concern here -- stateLock approach does not seem efficient to me for a core synchronization primitive. The act of acquiring read lock should be fully lock-free for scalability purposes, so that it scales to multi-core machines where a lot of threads can be acquiring and releasing read lock concurrently.

[bobvawter]

@elizarov If you agree with the general design of that ReadWriteMutex API, I can work on making the implementation more like Mutex (using an atomic queue of operations), adding additional state-management methods (e.g. tryReadLock()), and then put together a PR in the next couple of weeks.

Two questions before I start:

• Should state-change functions like readLock() accept an owner argument?
• If a user were to pass the same object twice to readLock(owner:Any?), should that call succeed?

I can see arguments for owner representing a specific actor (possibly reentrant or concurrent), or for owner representing a specific read operation. The former would look like some internal structure similar to ConcurrentMap<Any, Int> and the latter just a ConcurrentSet<Any>.

[jcornaz]

@elizarov, I don't understand your statement:

The act of acquiring read lock should be fully lock-free

How is it possible to guarantee that there will never be a write-lock and a read-lock open at the same time without locking something when we acquire a read-lock ?

I am not aware of other algorithms than theses two: https://en.wikipedia.org/wiki/Readers%E2%80%93writer_lock#Implementation

And neither of them alow to acquire a readlock in a lock-free manner.

Here my current read-write mutex implementation: https://gist.github.com/jcornaz/e94ee6a3a139ddd33c20554b0380d30f

[jcornaz]

After a second thought I think I now understand how it can be lock free to acquire a read-lock (if there is no write-lock open).

I drafted a first implementation here : https://github.com/jcornaz/kotlinx.coroutines/blob/c2f6831c3d8aa81c3b6c9e9da753873153e2b8a9/core/kotlinx-coroutines-core/src/main/kotlin/kotlinx/coroutines/experimental/sync/ReadWriteMutex.kt
(EDIT: This implementation suffer a critical issue allowing to acquire a read lock, when a write lock is active)

This implementation still suffer some problems that I'll address before creating a PR.

But, could you tell me what interface you prefer?

Choice 1:

interface ReadWriteMutex {
  val isReadLocked: Boolean
  val isWriteLocked: Boolean

  fun tryLockRead(): Boolean
  fun tryLockWrite(): Boolean

  suspend fun lockRead()
  fun unlockRead()

  suspend fun lockWrite()
  fun unlockWrite()
}

Choice 2:

interface Lock {
   fun unlock()
}

interface ReadWriteMutex {

  val isReadLocked: Boolean
  val isWriteLocked: Boolean

  fun tryLockRead(): Lock?
  fun tryLockWrite(): Lock?

  suspend fun lockRead(): Lock
  suspend fun lockWrite(): Lock
}

The first interface looks more like the Mutex interface. But it's less safe, because one could call unlockRead() without calling lockRead() before. The second interface make possible to address this issue, but would be less consistent with the Mutex interface.

Note 1: I know there is no select clause yet. I will try to add them.
Note 2: This is not possible to specify owner yet. Should I address it too ?

[jcornaz]

Here would be my implementation using the second interface:
https://github.com/jcornaz/kotlinx.coroutines/blob/feature/readwrite-mutex/core/kotlinx-coroutines-core/src/main/kotlin/kotlinx/coroutines/experimental/sync/ReadWriteMutex.kt

If you agree with the concept, I'll try to implement select clauses, add comments and prepare a pull request.

[fvasco]

Regardless of final choice I consider better to unify interfaces.

I like solution 2 but I suspect it requires some extra allocation.
Moreover using a Mutex force me to store locally both Mutex and Lock instances.

I suggest a "Choice 3" opposite to the first.

Choice 3:

interface ReadWriteMutex {
    val read: Mutex
    val write: Mutex
}

comparison:

rwMutex.lockRead()
rwMutex.read.lock()

Plus: choice 3 is compatible with regular mutex.

[jcornaz]

Thanks @fvasco, this is a very good proposition and would be my preferred choice too.

I'll try do it that way

[elizarov]

I like @fvasco API proposal, too. Please, send PR when you are done.

As a side note, we are considering to move "stack overflow prevention" logic that is currently complicating implementation of a regular (exlusive) Mutex into Unconfined dispatcher. It should make Mutex (and ReadWriteMutex) implementation simpler and faster for a typical case of a default dispatcher, while still being free from stack overflow problem under Unconfined dispatcher. See #80 for details.

[Dmitry-Borodin]

@fvasco please clarify whether you are working on it. Since this issue is still with "up for grabs" label, and it is not clear, whether it make sense to work on it.

[fvasco]

Hi @Dmitry-Borodin
sorry for misunderstanding,
I'm considering this job assigned to @jcornaz

I'll try do it that way

Any news?