Risk of deadlock? I don't think so, but...

[kjkrum]

At a glance, these four rules seem to be a recipe for deadlock:

1.3

onSubscribe, onNext, onError and onComplete signaled to a Subscriber MUST be signaled in a thread-safe manner—and if performed by multiple threads—use external synchronization.

2.7

A Subscriber MUST ensure that all calls on its Subscription take place from the same thread or provide for respective external synchronization.

3.2

The Subscription MUST allow the Subscriber to call Subscription.request synchronously from within onNext or onSubscribe.

3.10

While the Subscription is not cancelled, Subscription.request(long n) MAY synchronously call onNext on this (or other) subscriber(s).

request/onNext

If a Publisher thread locks the Subscriber per 1.3 and calls a version of onNext that attempts to lock the Subscription per 2.7, while a Subscriber thread locks the Subscription per 2.7 and calls a version of request that attempts to lock the Subscriber per 1.3, the threads will deadlock.

Do the synchronous calls allowed by 3.10 and 3.2 require external synchronization per 1.3 and 2.7?

I think the answer is "no", but the reason is subtle.

If request is called in multiple threads, the callers would synchronize on the Subscription. If request does not synchronize on the Subscriber when calling onNext, then there is no effective synchronization with callers of Subscriber methods that synchronize on the Subscriber. Are there any such callers?

• If the Publisher is synchronous, then the only callers of onNext will be the callers of request, which are effectively synchronized with each other.

• If the Publisher is asynchronous, then its implementation of request will probably not make synchronous calls to onNext in the first place.

This should be guaranteed:

X.1

A Subscription produced by an asynchronous Publisher MUST NOT synchronously call onNext from within request.

X.2

An asynchronous Subscriber MUST NOT synchronously call request from within onNext.

onSubscribe/request

I think it's safe for an asynchronous Subscriber to lock the Subscription in onSubscribe to synchronously call request, because although the caller of onSubscribe may hold the lock on the Subscriber, no Subscriber thread would be trying to obtain the locks in the opposite order at the time onSubscribe is called.

request/onError

I think it's safe for a Subscription produced by an asynchronous Publisher to lock the Subscriber in request to synchronously call onError (rule 3.9), because although the caller of request may hold the lock on the Subscription, no Publisher thread would be trying to obtain the locks in the opposite order. Again, the statefulness of Subscriber prevents the calls that could deadlock from occurring at the same time.

Assuming my "X" rules are followed, is there any other situation where a thread would try to lock both the Subscriber and the Subscription?

[akarnokd]

If a Publisher thread locks the Subscriber per 1.3 and calls a version of onNext that attempts to lock the Subscription per 2.7, while a Subscriber thread locks the Subscription per 2.7 and calls a version of request that attempts to lock the Subscriber per 1.3, the threads will deadlock.

None of the rules requires you to lock on these components because most logic around them can be and is achieved in a lock-free manner in the major 3 implementations. In RxJava specifically, there is a rule for the operators that one should not call onXXX while holding any lock because that may lead to deadlocks.

Do the synchronous calls allowed by 3.10 and 3.2 require external synchronization per 1.3 and 2.7?

In theory, no; in practice, yes. request implementation has to be thread-safe and reentrant-safe because a request may come at any time from any thread to the Publisher/Subscription. If it's the same thread, then you may end up with a recursive call between request and onNext which may lead to stack overflow. Often, the two safety requirement can be achieved via the same trampolining and non-blocking logic (queue-drain, atomic state changes, actor message queues).

Assuming my "X" rules are followed, is there any other situation where a thread would try to lock both the Subscriber and the Subscription?

The main idea of Reactive-Streams is the non-blocking backpressure, thus when we (I assume) think about our existing and proven implementations, we avoid thinking in locks around signals entirely.

[kjkrum]

@akarnokd What does "external synchronization" mean, then, if not the use of a lock? A lock-free (or in actuality, locks-hidden) approach may work, but is it spec-compliant and guaranteed interoperable with spec-compliant implementations?

[akarnokd]

How would a Subscriber from an external library know about which objects to lock on your particular implementation? What if someone uses a guard object internally instead of locking on the Subscription?

Synchronization in the spec doesn't mean Java's synchronized keyword but it refers to mean which by calls, events appear to be happening sequentially or in a serialized fashion (the database terminology, not the object-to-bytes fashion).

[kjkrum]

How would a Subscriber from an external library know about which objects to lock on your particular implementation?

The wording of the spec strongly implies that the objects to lock are the Subscriber and the Subscription.

What if someone uses a guard object internally instead of locking on the Subscription?

Then their implementation would be non-compliant.

The spec should say what it means, and "external synchronization" means something very specific. You are interpreting the spec as if it said that Subscriber and Subscription should be thread-safe. But the spec very clearly says that the burden of thread safety is on their callers.

Edit: I assume the spec was designed this way because only the caller knows whether synchronization is needed. An implementation that uses internal synchronization pays the price of synchronization even when used in only one thread. (Granted, the price of an uncontested lock is negligible.)

[viktorklang]

@kjkrum Thanks for asking this question which reveals that the external synchronization phrase needs to be in the glossary!

What is meant by external synchronization is that access needs to be coordinated outside of the spec so that from a spec point-of-view (to the observer) it is thread safe from a sequencing perspective.

Edit: To clarify, it does not mandate, suggest, or recommend using the JVM construct synchronized on anything or anywhere.

[kjkrum]

All right, thanks for clarifying. (And thanks for not biting my head off.)

[viktorklang]

@kjkrum You're most welcome. Thank you for pointing out this weakness in the documentation! :)

[ktoso]

Assign milestone 1.0.1?