Deadlock!

[zh217]

Hi,

I have found a situation where zmq-async would deadlock. The following code will do:

(ns debug.async.core
  (:import [org.zeromq ZMQ$Socket])
  (:require [com.keminglabs.zmq-async.core :refer [register-socket!]]
            [clojure.core.async :refer [chan close! go >! <!]]))

(defn deadlock!
  []
  (let [write-in (chan)
        read-in (chan)
        read-out (chan)]
    (register-socket! {:in write-in :socket-type :push
                       :configurator (fn [^ZMQ$Socket s]
                                       (.bind s "tcp://127.0.0.1:19999"))})
    (register-socket! {:in read-in :out read-out :socket-type :pull
                       :configurator (fn [^ZMQ$Socket s]
                                       (.connect s "tcp://127.0.0.1:19999"))})

    ;; This and the next go blocks just send message from one socket to another repeatedly
    (go
      (loop [c 0]
        (>! write-in (str "send " c))
        (recur (inc c))))
    (go
      (loop []
        (println (String. (<! read-out)))
        (recur)))

    ;; This loop opens and closes sockets repeatedly
    (loop [c 0]
      (println "open-close " c)
      (let [in (chan)]
        (register-socket! {:in in :socket-type :pub
                           :configurator (fn [^ZMQ$Socket s]
                                           )})
        (close! in)
        (recur (inc c))))))

I also have a rough idea why the deadlock happens: in the above code, first, we have a lot of incoming messages from ZMQ sockets, so it is expected that the zmq-loop will spend a lot of time on this line

(>!! async-control-chan [incoming-sock-id msg])

At the same time, we also have lots of requests for opening/closing sockets, so the async-loop will spend a lot of time putting commands to zmq sockets onto the queue

  (.put queue msg)

Now, once the queue gets full, the put to the queue will block. If, at the same time, zmq-loop wants to put into async-control-chan as above, that would block too since async-loop still tries to put message onto the queue. We have a deadlock.

I have also found out that it is of no use either: increasing the queue size , or: give the async-control-chan some buffer, as long as it is not a buffer that drops messages , or doing them both. Doing them both only delays the deadlock by a tiny bit.

Changing pool and alts!! to be deterministic in the sense that they will always take the control channel/socket first if that's available, together with sufficient buffer, may be able to avoid this deadlock. I will investigate further.

I guess the reason that people have not discovered this deadlock is that in real situations it happens rarely, since we don't usually create/close sockets at this speed.

[zh217]

Ok, it seems that the final loop is not needed: the following would deadlock too:

(ns debug.async.core
  (:import [org.zeromq ZMQ$Socket])
  (:require [com.keminglabs.zmq-async.core :refer [register-socket!]]
            [clojure.core.async :refer [chan close! go >! <! timeout]]))

(defn deadlock!
  []
  (let [write-in (chan)
        read-in (chan)
        read-out (chan)]
    (register-socket! {:in write-in :socket-type :push
                       :configurator (fn [^ZMQ$Socket s]
                                       (.bind s "tcp://127.0.0.1:19999"))})
    (register-socket! {:in read-in :out read-out :socket-type :pull
                       :configurator (fn [^ZMQ$Socket s]
                                       (.connect s "tcp://127.0.0.1:19999"))})

    ;; This and the next go blocks just send message from one socket to another repeatedly
    (go
      (loop [c 0]
        (>! write-in (str "send " c))
        ;; uncomment the following line makes the deadlock much harder to see --
        ;; actually it won't deadlock unless some crazy GC kicks in at the precise moment
        ;; (<! (timeout 100))
        (recur (inc c))))
    (go
      (loop []
        (println (String. (<! read-out)))
        (recur)))))

The reason being that sending and receiving messages are sufficient to trigger the two lines involved in the deadlock. The trick is to let the sending/receiving go really quickly: if we set a timeout between each send, it is much more difficult to see a deadlock.

[lynaghk]

Prioritizing control messages sounds like a reasonable strategy to me.
I know it's possible with core.async's alts!!. Are you suggesting that the zmq-async'spoll` function be rewritten to prioritize control messages?

Are we sure this will resolve the deadlock issue?

[zh217]

My strategy is the following:

1. prioritising alts!! for the control channel (only the control channel is prioritised, the rest are still chosen randomly)
2. prioritising poll for the control socket (again, only the control socket is prioritised)
3. give the control channel a tiny buffer.

I have a system which would deadlock every few minutes with the original code. With my modified code #5, it has been running for a few days and I am yet to see a deadlock.

Still, there is the theoretical possibility that this would still deadlock: that is, when both the control channel and the queue get filled up and the above two lines of code get executed at roughly the same time. This could happen on really slow computers when the following conditions are fulfilled:

1. there are lots of incoming messages from sockets
2. there are lots of messages put into the async-control-chan by registering lots of sockets (note that with the above fixes, only the puts when registering sockets matter, since before the other puts into the async-control-chan, either the queue will get less full, or the control will get less full).

I haven't seen this rather extreme situation happening, and registering lots of sockets really quickly is probably not something that should be encouraged.

[lynaghk]

Thanks for taking the time to write this up, I appreciate it and your other contributions.

This strategy sounds like a solid one to me.
The only question I have is about part 3, the control channel buffer.
Couldn't we put the buffer in either the async control channel or the queue?

Or we could make one of these drop puts when they're full.
(I don't like this option, but want to include it for completeness.)

Let me draw out a state diagram analysis of our situation and see if we can design a fix that never deadlocks.

[zh217]

I tried to reason about the situation more clearly. As a result, I don't think it is possible to rule out deadlocks with the current strategies. I also have some new ideas about how to avoid deadlocks completely (see the end).

Let A be the number of messages in async-control-channel, Q be the number of messages in the queue. We have 0 <= A <= A_MAX, 0 <= Q <= Q_MAX.

The two processes async-loop and zmq-loop run concurrently, that is, their operations are interleaved in arbitrary order except when they need to cooperate, by means of the async-control-channel and the queue.

The deadlock outlined above happens when:

1. A = A_MAX
2. Q = Q_MAX
3. when entering the zmq-loop, Q = 0 (this is due to our fixing strategy 2: if Q > 0, the control socket will be chosen and there will not be puts into the async-control-channel in the current iteration of the loop. We also see that strategy 2 is the most important strategy of the three: without it, the system only needs to satisfy the above two conditions to deadlock).

Now suppose that when entering the zmq-loop, Q = 0 and a message arrives from the zmq socket so the zmq-loop goes forward. Before it reaches the statement putting the message into the async-control-channel, an unreasonable amount of socket registration requests are received. Also, due to some very unlikely circumstances, the async-loop completes many iterations before the zmq-loop even reaches the put statement. So when zmq-loop reaches the put statement, A = A_MAX since those registrations just keep coming, and Q = Q_MAX since the async-loop goes too fast.

So deadlocks are not eliminated. But they are highly mitigated:

1. strategy 1 ensures that when A > 0, each async loop will try to reduce A without doing anything else
2. strategy 2 ensures that when Q > 0, each zmq loop will try to reduce Q without doing anything else

It also becomes clear why strategy 3 is helpful: omitting it amounts to setting A_MAX = 1. Similarly, reducing the queue size amounts to reducing Q_MAX.

Ok, the situation looks rather bleak, but maybe we can do better than this by introducing a bigger change: create a new channel (let's call it register-channel for now), and let register-socket put into this channel instead of async-control-channel. Then in async-loop, prioritise alts!! in the order: async-control-channel, register-channel, and the rest.

Now the only way for A to grow is via the zmq-loop, each iteration increasing A by at most one, and the only way for Q to grow is via the async-loop, each iteration increasing Q by at most one. And the loops just keep reducing A and Q when they are positive. The other channels may block external operations temporarily, but they will not block these two threads and hence no deadlocks. Here we can even afford to set A_MAX = 1, thereby getting rid of the buffer on the channel all together (maybe for performance reasons it is good to leave them there, I don't know).

[sjlnk]

The problem appears to be this:

• async-thread keeps getting input messages rapidly and passes them to zmq-thread.
• zmq-thread keeps receiving the output messages rapidly and passes them to async-thread.
• Depending on random chance async-thread processes either a message coming from user (input) or message coming from zmq-thread.
  • zmq-thread has to block until async-thread decides to process it's control message
  • Every time when async-thread decides to forward more than one message to zmq-thread per each message handled coming from zmq-thread (ratio more than 1:1) the queue starts filling up.
  • Random variation around this 1:1 ratio is guaranteed thus generating queue size.
  • Platform specific scheduler properties could always cause over 1:1.
  • No matter how big the queue is, it has a good chance to fill up (or computer runs out of memory)
  • When queue is full deadlock occurs because async-thread is waiting for zmq-thread to process it's
    input while zmq-thread is waiting for async-thread to process it's input

A prioritization logic can be implemented as already done by @zh217 but it seems a bit of a hack indeed. A better solution would be deadlock free design where messages are flowing only one way. Two way communication is not necessary nor recommended because it introduces risk of deadlocks. Two way communication also needlessly wastes cpu cycles. I'm going to work on this concept.

[sjlnk]

I have created a design with no possibility of deadlocks and it should theoretically have also better performance characteristics. I will release it soon after I polish it a little bit and write some tests for it.

[lynaghk]

@sjlnk A deadlock-free design sounds great. Look forward to seeing what you come up with!