[GHC] #4154: Deadlock in Chan module

[GHC]

#4154: Deadlock in Chan module
-------------------------------------+-------------------------------------
        Reporter:  NeilMitchell      |                Owner:  (none)
            Type:  bug               |               Status:  closed
        Priority:  high              |            Milestone:  8.4.1
       Component:  libraries/base    |              Version:  6.12.3
      Resolution:  fixed             |             Keywords:
Operating System:  Unknown/Multiple  |         Architecture:
 Type of failure:  Incorrect result  |  Unknown/Multiple
  at runtime                         |            Test Case:
      Blocked By:                    |             Blocking:
 Related Tickets:                    |  Differential Rev(s):
       Wiki Page:                    |
-------------------------------------+-------------------------------------

Comment (by osa1):

 > Is it possible to define instead of isEmptyChan some non-blocking
 version of
 > readChan with tryTakeMVar and tryPutMVar?

 I think this can't work. A `readChan` is actually two `takeMVar`s.
 Implementation of `tryReadChan` has to use `tryTakeMVar`s, otherwise you
 can't
 avoid being blocked in some cases.

 So these two MVars that need to be taken to be able to read something off
 a
 chan need to be taken with `tryReadChan`.

 First `tryTakeMVar` would only succeed if the queue is empty. The trouble
 is in
 the case where the chan has enough stuff but currently some other thread
 is
 busy actually reading the contents (and updating the read-end) you'd get a
 `Nothing`, even though if you actually do `readChan` you'd get blocked for
 a
 very short amount of time because chan has enough contents. So this
 implementation would return `Nothing` in some cases when there is enough
 contents in the chan.


 Now suppose that you use `tryReadMVar` to read the read-end. Suppose that
 right
 after you read the read-end another thread does `readChan`, and takes the
 read-end MVar. Now there's a race condition between your thread and the
 other
 thread. The loser needs to re-take the read-end. Furthermore, if your
 thread
 was the only thread you can't update the read-end, because you didn't take
 it
 (remember that in this scenario we use `tryReadMVar` instead of
 `tryTakeMVar`).

 So neither `tryTakeMVar` nor `tryReadMVar` gives you a race-free
 implementation
 of `tryReadChan`. I hope this makes sense.

 (Another problem with both implementations is that you have no guarantees
 that
 you'll be able to read the contents. For example if chan has enough
 contents
 but a million threads are running `readChan` in parallel you may not be
 able to
 read anything with `tryReadChan`)

 `MVar`-based implementation is cute but has this limitation. (it also
 doesn't
 scale as number of writers and readers increase)

--
Ticket URL: <http://ghc.haskell.org/trac/ghc/ticket/4154#comment:12>
GHC <http://www.haskell.org/ghc/>
The Glasgow Haskell Compiler